Online Learning and Regret Minimization — Mathematics Knowledge System

Overview

Online learning studies sequential decision-making: at each round t, an algorithm chooses x_t from a convex set X, then observes a loss function f_t and incurs loss f_t(x_t). The goal is to minimize regret -- the difference between total loss and the best fixed decision in hindsight: R_T = sum_{t=1}^T f_t(x_t) - min_{x in X} sum_{t=1}^T f_t(x). Key algorithms include Online Gradient Descent (OGD) and Follow The Regularized Leader (FTRL). The regret bounds O(sqrt(T)) are minimax optimal for adversarial (worst-case) sequences. Online learning connects to game theory (no-regret learning -> Nash equilibria), statistics (PAC learning), and stochastic optimization.

Intuition

Imagine investing in stocks. Each day you allocate your portfolio (x_t = weights), then see the day's returns (f_t). Regret measures how much worse your strategy is compared to the best fixed allocation in hindsight. A no-regret algorithm guarantees R_T/T -> 0 as T -> inf: your average loss approaches the best average in hindsight. This is achievable even against an adversary choosing f_t adversarially -- but only by making online decisions without knowing future f_t. The key insight: the minimax optimal regret is Theta(sqrt(T)) for general convex losses.

Formal Definition

Definition

Online convex optimization protocol: (1) Learner picks x_t in X (convex compact). (2) Adversary reveals f_t: X -> R (convex). (3) Learner incurs loss f_t(x_t). Regret: R_T = sum_{t=1}^T f_t(x_t) - min_{x in X} sum_{t=1}^T f_t(x). An algorithm is no-regret if R_T = o(T) (R_T/T -> 0). Online Gradient Descent (OGD): x_{t+1} = Pi_X(x_t - eta_t * nabla f_t(x_t)) where Pi_X is the projection onto X. FTRL: x_{t+1} = argmin_{x in X} {sum_{s=1}^t f_s(x) + (1/eta) R(x)} where R is a strongly convex regularizer.

R_T = \sum_{t=1}^T f_t(x_t) - \min_{x \in X} \sum_{t=1}^T f_t(x)

Regret definition

x_{t+1} = \Pi_X\!\left(x_t - \eta_t \nabla f_t(x_t)\right)

Online Gradient Descent (OGD)

R_T^{\mathrm{OGD}} \le \frac{D^2}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T \|\nabla f_t(x_t)\|^2 \le DG\sqrt{T}

OGD regret bound (D=diam(X), G=gradient bound)

x_{t+1} = \arg\min_{x\in X}\left\{\eta\sum_{s=1}^t f_s(x) + R(x)\right\}

Follow the Regularized Leader (FTRL)

Notation

Notation	Meaning
$R_T$	Regret at time T
$\Pi_X$	Projection onto feasible set X
$D = \mathrm{diam}(X)$	Diameter of feasible set X
$G$	Bound on gradient norms: \|\|nabla f_t(x)\|\| <= G

Theorems

Theorem 1: OGD Regret Bound

For Online Gradient Descent with step size eta_t = D/(G*sqrt(t)) and a convex feasible set X with diameter D, against convex functions with ||nabla f_t|| <= G: R_T <= D*G*sqrt(T). This bound is achieved regardless of the adversary's choice of f_t. The bound is minimax optimal: no online algorithm achieves better than Omega(D*G*sqrt(T)) in the worst case.

Theorem 2: No-Regret Implies Nash Equilibrium

In a two-player zero-sum game with mixed strategies, if both players use no-regret algorithms (R_T^i/T -> 0 for each player i), then the time-average strategies x-bar_T = (1/T) sum_t x_t^1 and y-bar_T = (1/T) sum_t y_t^2 converge to a Nash equilibrium of the game. More precisely, the pair (x-bar_T, y-bar_T) is an epsilon-Nash equilibrium with epsilon = (R_T^1 + R_T^2)/T -> 0.

Theorem 3: Adaptive Regret for Strongly Convex Losses

For strongly convex loss functions f_t (with strong convexity parameter mu), the OGD algorithm with step sizes eta_t = 1/(mu*t) achieves regret R_T <= (G^2/(2*mu)) * log T = O(log T). This logarithmic regret bound is much better than the O(sqrt(T)) bound for general convex losses, and matches the lower bound for strongly convex losses.

Worked Examples

1
t=1: x_1 = 0. Observe f_1(x) = x. Gradient: nabla f_1(x_1) = 1. Update: x_2 = Pi_{[-1,1]}(0 - (1/2)*1) = Pi_{[-1,1]}(-1/2) = -1/2.
$x_2 = -1/2$
2
t=2: x_2 = -1/2. Observe f_2(x) = -x. Gradient: nabla f_2(x_2) = -1. Update: x_3 = Pi_{[-1,1]}(-1/2 - (1/2)*(-1)) = Pi_{[-1,1]}(0) = 0.
$x_3 = 0$
3
Losses: f_1(x_1) + f_2(x_2) = 0 + (1/2) = 1/2.
4
Best fixed: min_{x in [-1,1]} {f_1(x)+f_2(x)} = min_{x in [-1,1]} {x + (-x)} = min 0 = 0. Regret = 1/2 - 0 = 1/2.
$R_2 = 1/2$

✓ Answer

After 2 rounds, total loss = 1/2, best fixed loss = 0. Regret = 1/2. Note: OGD oscillates between -1/2 and 0, tracking the adversarial sequence.

Practice Problems

Hardfree response

Explain why the minimax optimal regret for online convex optimization with general convex losses is Theta(sqrt(T)).

Common Mistakes

Common Mistake

Thinking online learning is the same as stochastic optimization.

Stochastic optimization assumes i.i.d. loss functions (f_t ~ distribution P) and uses the statistical structure to accelerate convergence. Online learning makes no distributional assumption -- it works against an adversary who can choose f_t based on the learner's history. Online learning results are worst-case (minimax) while stochastic optimization results exploit distributional structure. SGD is both: viewed online, it's a no-regret algorithm; viewed statistically, it minimizes expected loss.

Quiz

No-regret online learning (R_T/T -> 0) in a two-player zero-sum game implies:

Each player maximizes their own payoffTime-averaged strategies converge to a Nash equilibriumThe game has a unique equilibriumEach player's strategy is monotonically improving

Historical Background

Hannan's regret-minimizing algorithm (1957) predates the modern framework. Cesa-Bianchi and Lugosi's book (2006) formalized the field. Online gradient descent was analyzed by Zinkevich (2003). The reduction from online learning to game theory (no-regret dynamics -> Nash equilibria) was developed by Freund-Schapire (1996) and Hart-Mas-Colell (2000). Hazan's 2016 lecture notes and Shalev-Shwartz's 2012 survey are standard references.

1957
Hannan proves the first regret bound for sequential decision-making
James Hannan
1996
Freund-Schapire AdaBoost and multiplicative weights for online learning
Yoav Freund, Robert Schapire
2003
Zinkevich proves O(sqrt(T)) regret for Online Gradient Descent
Martin Zinkevich
2006
Cesa-Bianchi and Lugosi -- Prediction, Learning, and Games textbook
Nicolo Cesa-Bianchi, Gabor Lugosi

Summary

Online learning: sequential decisions x_t, then f_t revealed. Regret R_T = total loss - best fixed in hindsight.
OGD: x_{t+1} = Pi_X(x_t - eta * grad f_t(x_t)). Regret = O(sqrt(T)) for convex losses.
Strongly convex losses: OGD achieves O(log T) regret (much faster).
No-regret dynamics in games: time-averaged strategies converge to Nash equilibria.

References

BookCesa-Bianchi, N. and Lugosi, G. Prediction, Learning, and Games. Cambridge, 2006.
BookHazan, E. Introduction to Online Convex Optimization. MIT Press, 2022.
WebsiteWikipedia -- Online machine learning