Online Nonparametric Regression with General Loss Functions
This paper establishes minimax rates for online regression with arbitrary classes of functions and general losses. 1 We show that below a certain threshold for the complexity of the function class, the minimax rates dependon both thecurvatureof the lossfunction andthe sequentialcomplexities of theclass. Abovethis threshold, the curvatureof the loss does not affect the rates. Furthermore,for the case of square loss, our results point to the interesting phenomenon: whenever sequential and i.i.d. empirical entropies match, the rates for statistical and online learning are the same. In addition to the study of minimax regret, we derive a generic forecaster that enjoys the established optimal rates. We also provide a recipe for designing online prediction algorithms that can be computationally efficient for certain problems. We illustrate the techniques by deriving existing and new forecasters for the case of finite experts and for online linear regression.