Online Nonparametric Regression with General Loss Functions
This work provides theoretical foundations for online learning with general losses, impacting researchers and practitioners in machine learning by clarifying when online and statistical rates differ, though it is incremental in extending existing minimax analysis.
The paper establishes minimax rates for online regression with arbitrary function classes and general loss functions, showing that rates depend on loss curvature and sequential complexities below a complexity threshold, but not above it, and revealing that for square loss, rates match statistical learning when sequential and i.i.d. entropies align.
This paper establishes minimax rates for online regression with arbitrary classes of functions and general losses. We show that below a certain threshold for the complexity of the function class, the minimax rates depend on both the curvature of the loss function and the sequential complexities of the class. Above this threshold, the curvature of 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.