Online Learning and Regret Bounds
What it means to learn without assuming a data distribution, why regret against the best fixed predictor is the achievable guarantee, and what online convex optimisation delivers.
Statistical learning assumes data drawn independently from a fixed distribution and bounds the error on future draws from it. Online learning drops that assumption entirely: examples arrive one at a time, in any order, possibly chosen adversarially, and the learner must predict before seeing each label. Remarkably, useful guarantees survive.
The protocol and the guarantee
At each round the learner outputs a prediction, the true value is revealed, and a loss is incurred. There is no distribution to be right about, so the guarantee is comparative: regret against the best single predictor in a comparison class, chosen with hindsight.
Sublinear regret means the average per-round loss approaches that of the best fixed predictor. It does not claim the predictions are good in absolute terms; it claims the learner does asymptotically as well as anything fixed could have done on this exact sequence, which is a meaningful statement without any distributional assumption.
Online gradient descent
For convex losses over a bounded convex set, projected gradient descent with step size \(\eta_t \propto 1/\sqrt{t}\) achieves \(O(\sqrt{T})\) regret. For strongly convex losses, \(\eta_t \propto 1/t\) achieves \(O(\log T)\). These bounds are tight for their settings.
Two things are worth noticing. The algorithm is exactly the update everyone already uses, so the analysis describes standard practice rather than a special method. And the step size schedule is prescribed by the theory rather than tuned, which is unusual and is one of the few places where a learning rate schedule has a principled justification.
Follow the regularised leader generalises this: at each step, minimise the accumulated loss plus a regulariser. Choosing an entropic regulariser yields multiplicative weights and its logarithmic dependence on the number of experts, which is why online learning over a large hypothesis set is feasible at all.
Adaptive methods
AdaGrad scales the step size per coordinate by the inverse square root of accumulated squared gradients, which gives larger steps for rarely-updated features. In sparse high-dimensional problems this is a substantial improvement, and it was derived from online regret analysis rather than from optimisation heuristics. The adaptive optimisers used throughout deep learning descend from this line.
When it breaks
Regret against a fixed comparator is the wrong benchmark under drift. If the best predictor changes over time, competing with the best single one is competing with something no longer relevant. Dynamic and adaptive regret, measured against the best predictor in each window, are the appropriate notions and require different algorithms.
Convexity is doing real work. The bounds assume convex losses, and a neural network's loss is not. Online deep learning has the practice without the guarantees, and the theory is a source of intuition rather than of assurance.
Sublinear regret can still mean poor absolute performance. If every predictor in the class is bad on this sequence, matching the best of them is no achievement. The guarantee is relative and says nothing about whether the comparison class was adequate.
Adversarial robustness costs average-case performance. Algorithms designed for worst-case sequences are conservative on benign ones, so a method with the best regret bound is frequently not the best choice on ordinary data.
12 flashcards for this concept
Click a card to reveal the answer.