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.

本文研究任意函数类和一般损失的在线回归问题，并确定了最小极大率。结果表明，当函数类的复杂度低于某一阈值时，最小极大率取决于损失函数的曲率和序列复杂度。而当复杂度高于该阈值时，损失的曲率不再影响率。此外，对于平方损失，当顺序和独立同分布的经验熵匹配时，统计和在线学习的速率相同。我们还提供了一种通用的预测器，它具有确定的最优率，并提供了一种设计在线预测算法的方法，用于某些问题可以是计算量有效的。