The O(√T) Regret Bound for Online Gradient Descent14 minWikiOpen in Colab
The O(√T) Regret Bound for Online Gradient Descent
Online gradient descent (OGD) is the workhorse of online convex optimization, and its guarantee — regret O(T) against any sequence of convex losses (Zinkevich, 2003) — is what makes online learning viable on streams. This page proves it from scratch. The whole argument is three short steps: a projection inequality, the definition of convexity, and a telescoping sum.
Setup and assumptions
A convex feasible set K⊆Rd with diameterD=maxx,y∈K∥x−y∥.
On round t the learner plays xt∈K, then a convex loss ft is revealed, with a (sub)gradient gt∈∂ft(xt) whose norm is bounded, ∥gt∥≤G.
OGD update with projection ΠK (Euclidean, hence non-expansive):
xt+1=ΠK(xt−ηgt).
The comparator is the best fixed action in hindsight, x⋆=argminx∈K∑t=1Tft(x), and
RegretT=t=1∑Tft(xt)−t=1∑Tft(x⋆).
Step 1: the projection inequality
Because Euclidean projection onto a convex set does not increase distances to points already in the set, ∥ΠK(y)−x⋆∥≤∥y−x⋆∥ for x⋆∈K. Apply it to y=xt−ηgt and expand the square:
Drop the non-positive −∥xT+1−x⋆∥2, bound ∥x1−x⋆∥2≤D2 and ∥gt∥2≤G2:
RegretT≤2ηD2+2ηG2T.(3)
Tuning the step size
The bound (3) is a sum of a term that shrinks with η and one that grows with it. Minimising over η (set the derivative −D2/2η2+G2T/2=0) gives
η⋆=GTD,RegretT≤DGT=O(T).
Since the average regret is RegretT/T≤DG/T→0, OGD asymptotically matches the best fixed decision — with no distributional assumption on the losses.
Refinements
Not knowing T (decaying step). Using ηt=GtD instead of a fixed η removes the need to know the horizon and still yields RegretT≤23DGT — the same rate, a slightly larger constant.
Strong convexity. If every ft is λ-strongly convex, the convexity step (2) gains an extra 2λ∥xt−x⋆∥2 term. Choosing ηt=λt1 makes the distance terms cancel more aggressively and yields
RegretT≤2λG2(1+lnT)=O(logT).
Online-to-batch. On i.i.d. data, averaging the iterates converts O(T) regret into an O(1/T) bound on excess risk. This is precisely why SGD converges at O(1/T).
Worked numeric example
Let D=2 (feasible set of radius 1), G=1 (unit-norm gradients), T=10,000. The optimal step is η⋆=D/(GT)=2/100=0.02, and the regret bound is
RegretT≤DGT=2⋅1⋅100=200,
so the average regret is at most 200/10,000=0.02 per round. Compare a learner that plays a fixed point x^=x⋆: it pays a constant gap δ=T1∑t[ft(x^)−ft(x⋆)]>0 every round, so its regret is δT — linear, and its average regret never vanishes. The notebook verifies OGD's empirical regret stays under the DGT curve while the fixed learner's grows linearly.