Online Learning & Regret
Streaming statistics summarise a stream; online learning fits a model to it, one example at a time, without ever storing the whole dataset. This is the natural learning paradigm for streams — and, as we will see, the theory that justifies stochastic gradient descent itself. The framework is online convex optimization (OCO), developed in Stanford's CS229T and the online-learning literature.
The online learning game
Learning is framed as a repeated game between a learner and an (possibly adversarial) environment. On each round :
- The learner picks a point from a convex set (e.g. a weight vector).
- The environment reveals a convex loss function .
- The learner suffers loss and observes it (or its gradient).
Crucially, can be chosen after seeing , and the sequence need not come from any fixed distribution. It can drift, or even be adversarial. There is no i.i.d. assumption to lean on.
Regret: the right yardstick
You cannot measure an online learner by "distance to the true parameters" — there may be no fixed truth. Instead we measure regret: how much worse the learner did than the single best fixed decision in hindsight.
The comparator is the best single action chosen with full knowledge of the whole sequence. A learner is good if its regret is sublinear, , because then the average regret : over time the online learner does as well per round as the best fixed decision, despite seeing the data only once and in order.
Why sublinear regret is the goal
Linear regret () means a constant penalty every round forever — no learning. Sublinear regret like means the per-round penalty vanishes. It is a worst-case guarantee: it holds even against an adversary, with no distributional assumptions at all.
Online gradient descent
The simplest OCO algorithm is online gradient descent (OGD) (Zinkevich, 2003): take a gradient step on each round's loss, then project back into .
With a decaying step size — where bounds the diameter of and bounds the gradient norms — OGD achieves
That is the headline result: a single gradient step per example gives regret against any sequence of convex losses.
Online gradient descent: regret grows like √T
Every round an adversary picks a convex loss |x−yₜ|; OGD takes a subgradient step with ηₜ = c/√t. Its cumulative regret (teal) tracks the √T reference (dashed) — sublinear — so average regret Rₜ/T → 0 and OGD matches the best fixed decision in hindsight (the median). A fixed guess that never adapts (rose) pays linear regret. Raise c to step harder: too small converges slowly, too large jitters — both lift the curve.
If every loss is additionally -strongly convex, the guarantee sharpens to logarithmic regret with step size :
Curvature makes online learning dramatically easier — the same reason strongly convex batch problems converge faster.
Follow-the-regularized-leader
A second, unifying family is follow-the-regularized-leader (FTRL). The naive "follow-the-leader" strategy replays the best point on all losses so far, , but it is unstable. It can jump wildly round to round and incur linear regret. FTRL adds a strongly convex regularizer to stabilise the choice:
With and linearised losses, FTRL is online gradient descent; other regularizers yield mirror descent, exponentiated gradient, and AdaGrad-style per-coordinate adaptivity. FTRL is the template behind the online learners that power large-scale ad click-through-rate systems, precisely because it is stable and cheap to update.
Online-to-batch: why SGD works
Online learning is not just for streams — it explains batch stochastic optimization. Online-to-batch conversion says: run an online algorithm on i.i.d. samples with losses , then output the average iterate . Then the excess risk of is bounded by the average regret:
where is the population risk. Plugging in OGD's regret gives the familiar convergence rate of SGD.
The punchline
Stochastic gradient descent is online gradient descent on a shuffled dataset, and its convergence rate is just OGD's regret bound divided by . The online view is the deeper one: it needs no i.i.d. assumption, so it keeps working when the data is a genuine, possibly-drifting stream — the subject of the next lesson.
Python: an online linear classifier
import numpy as np
class OnlineLogReg:
"""Online gradient descent for logistic loss with η_t = c/√t."""
def __init__(self, dim, c=0.5):
self.w = np.zeros(dim)
self.c = c
self.t = 0
def predict_proba(self, x):
return 1.0 / (1.0 + np.exp(-self.w @ x))
def learn_one(self, x, y): # y in {0, 1}
self.t += 1
eta = self.c / np.sqrt(self.t) # decaying step → O(√T) regret
grad = (self.predict_proba(x) - y) * x # ∇ of logistic loss
self.w -= eta * grad
model = OnlineLogReg(dim=len(next_features))
for x, y in stream: # one pass, O(dim) memory
p = model.predict_proba(x) # predict first...
model.learn_one(x, y) # ...then learn from the label
Exercise
Online gradient descent achieves regret O(√T) on convex losses. What does this sublinear regret imply as T grows?
Need a hint?
Divide the regret by T — what happens to the average per-round regret?
Exercise
Via online-to-batch conversion, an online algorithm with O(√T) regret run on i.i.d. samples yields what convergence rate for the excess risk of the averaged iterate?
Need a hint?
Excess risk ≤ average regret = Regret_T / T. Substitute Regret_T = O(√T).
Key takeaways
- Online convex optimization frames learning as a round-by-round game with no i.i.d. assumption; success is measured by regret against the best fixed decision in hindsight.
- Sublinear regret () means average regret vanishes — the learner matches the best fixed action per round.
- Online gradient descent achieves regret for convex losses () and for strongly convex ones.
- FTRL stabilises "follow the leader" with a regularizer and generalises OGD, mirror descent, and AdaGrad.
- Online-to-batch converts regret bounds into generalization bounds. This is why SGD converges at .
Related concepts
- Gradient Descent Variants: the batch optimizers whose online cousins this lesson analyses
- Concept Drift & Adaptation: what happens when the stream's distribution itself changes
- From Batch to Streaming: the one-pass setting online learning is built for