online learning and regret

Drop the comforting assumption that data is drawn independently from a fixed distribution. In online learning, examples arrive one at a time, possibly chosen by an adversary, and you must commit to a prediction before seeing each outcome. You cannot hope to be perfect, so you measure success by regret: how much worse your cumulative loss is than that of the single best fixed strategy you could have committed to in hindsight, had you known the whole sequence in advance.

Over T rounds, regret is your total loss minus the loss of the best fixed expert or decision in the comparison class. The goal is sublinear regret — regret growing slower than T — so that average regret vanishes and you become asymptotically as good as the best fixed choice. Canonical algorithms achieve this: multiplicative weights, or Hedge, gets regret on the order of the square root of T log N over N experts; online gradient descent and follow-the-regularized-leader achieve order root T for convex losses, with logarithmic regret under strong convexity. No statistical assumption on the data is needed — the bounds hold against arbitrary, even adversarial, sequences.

Regret minimization unifies online convex optimization, prediction with expert advice, bandits, and game-theoretic learning, where no-regret dynamics converge to equilibria. Online-to-batch conversion turns any low-regret online algorithm into a generalization bound in the i.i.d. setting, linking this framework back to statistical learning. The honest caveat: competing only with the best fixed comparator is a weak benchmark in highly non-stationary environments, motivating dynamic and adaptive regret notions.