Optimal Regret in Online Prediction
Peter Bartlett
QUT and UC Berkeley

We consider the regret of an optimal strategy for an online prediction
problem. We show that it is closely related to the behavior of the
empirical minimizer in a stochastic process setting: it is the
maximum, over joint distributions of the adversary's action sequence,
of the difference between a sum of minimal expected losses and the
expected minimal empirical loss.  By using a symmetrization argument,
we show that the optimal regret is bounded by a measure of complexity
of the loss class that is closely related to Rademacher averages,
which is used in the analysis of prediction methods in probabilistic
settings.  For linear loss classes, this bound cannot be improved by
more than a factor of two, and reduces to convergence properties of
vector-valued martingales.

Joint work with Jake Abernethy, Alekh Agarwal, Sasha Rakhlin,
Karthik Sridharan and Ambuj Tewari.