The O(√T) Regret Bound for Online Gradient DescentOpen 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)O(\sqrt{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\mathcal{K} \subseteq \mathbb{R}^d with diameter D=max⁡x,y∈K∥x−y∥D = \max_{x,y\in\mathcal{K}} \|x - y\|.
  • On round tt the learner plays xt∈Kx_t \in \mathcal{K}, then a convex loss ftf_t is revealed, with a (sub)gradient gt∈∂ft(xt)g_t \in \partial f_t(x_t) whose norm is bounded, ∥gt∥≤G\|g_t\| \le G.
  • OGD update with projection ΠK\Pi_{\mathcal K} (Euclidean, hence non-expansive):
xt+1=ΠK(xt−η gt).x_{t+1} = \Pi_{\mathcal{K}}\big(x_t - \eta\, g_t\big).
  • The comparator is the best fixed action in hindsight, x⋆=arg⁡min⁡x∈K∑t=1Tft(x)x^\star = \arg\min_{x\in\mathcal K}\sum_{t=1}^T f_t(x), and
RegretT=∑t=1Tft(xt)−∑t=1Tft(x⋆).\text{Regret}_T = \sum_{t=1}^{T} f_t(x_t) - \sum_{t=1}^{T} f_t(x^\star).

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⋆∥\|\Pi_{\mathcal K}(y) - x^\star\| \le \|y - x^\star\| for x⋆∈Kx^\star \in \mathcal K. Apply it to y=xt−ηgty = x_t - \eta g_t and expand the square:

∥xt+1−x⋆∥2≤∥xt−ηgt−x⋆∥2=∥xt−x⋆∥2−2η ⟨gt, xt−x⋆⟩+η2∥gt∥2.\|x_{t+1} - x^\star\|^2 \le \|x_t - \eta g_t - x^\star\|^2 = \|x_t - x^\star\|^2 - 2\eta\,\langle g_t,\, x_t - x^\star\rangle + \eta^2\|g_t\|^2.

Rearranging to isolate the inner product:

⟨gt, xt−x⋆⟩  ≤  ∥xt−x⋆∥2−∥xt+1−x⋆∥22η  +  η2∥gt∥2.(1)\langle g_t,\, x_t - x^\star\rangle \;\le\; \frac{\|x_t - x^\star\|^2 - \|x_{t+1} - x^\star\|^2}{2\eta} \;+\; \frac{\eta}{2}\|g_t\|^2. \tag{1}

Step 2: convexity turns loss gaps into inner products

By the definition of a (sub)gradient of a convex function, ft(x⋆)≥ft(xt)+⟨gt, x⋆−xt⟩f_t(x^\star) \ge f_t(x_t) + \langle g_t,\, x^\star - x_t\rangle, i.e.

ft(xt)−ft(x⋆)  ≤  ⟨gt, xt−x⋆⟩.(2)f_t(x_t) - f_t(x^\star) \;\le\; \langle g_t,\, x_t - x^\star\rangle. \tag{2}

This is the only place convexity is used, and it is what lets a first-order method bound a function-value regret.

Step 3: sum and telescope

Combine (2) and (1) and sum over t=1,…,Tt = 1,\dots,T. The distance terms telescope:

RegretT≤∑t=1T∥xt−x⋆∥2−∥xt+1−x⋆∥22η+η2∑t=1T∥gt∥2=∥x1−x⋆∥2−∥xT+1−x⋆∥22η+η2∑t=1T∥gt∥2.\text{Regret}_T \le \sum_{t=1}^T \frac{\|x_t - x^\star\|^2 - \|x_{t+1} - x^\star\|^2}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T \|g_t\|^2 = \frac{\|x_1 - x^\star\|^2 - \|x_{T+1}-x^\star\|^2}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T\|g_t\|^2.

Drop the non-positive −∥xT+1−x⋆∥2-\|x_{T+1}-x^\star\|^2, bound ∥x1−x⋆∥2≤D2\|x_1 - x^\star\|^2 \le D^2 and ∥gt∥2≤G2\|g_t\|^2 \le G^2:

  RegretT  ≤  D22η+η G2T2.  (3)\boxed{\;\text{Regret}_T \;\le\; \frac{D^2}{2\eta} + \frac{\eta\, G^2 T}{2}.\;} \tag{3}

Tuning the step size

The bound (3) is a sum of a term that shrinks with η\eta and one that grows with it. Minimising over η\eta (set the derivative −D2/2η2+G2T/2=0-D^2/2\eta^2 + G^2 T/2 = 0) gives

η⋆=DGT,RegretT  ≤  D G T  =  O(T).\eta^\star = \frac{D}{G\sqrt{T}}, \qquad \text{Regret}_T \;\le\; D\,G\,\sqrt{T} \;=\; O(\sqrt{T}).

Since the average regret is RegretT/T≤DG/T→0\text{Regret}_T/T \le DG/\sqrt{T} \to 0, OGD asymptotically matches the best fixed decision — with no distributional assumption on the losses.

Refinements

  • Not knowing TT (decaying step). Using ηt=DGt\eta_t = \dfrac{D}{G\sqrt{t}} instead of a fixed η\eta removes the need to know the horizon and still yields RegretT≤32DGT\text{Regret}_T \le \tfrac{3}{2} D G \sqrt{T} — the same rate, a slightly larger constant.
  • Strong convexity. If every ftf_t is λ\lambda-strongly convex, the convexity step (2) gains an extra λ2∥xt−x⋆∥2\tfrac{\lambda}{2}\|x_t - x^\star\|^2 term. Choosing ηt=1λt\eta_t = \tfrac{1}{\lambda t} makes the distance terms cancel more aggressively and yields
RegretT≤G22λ (1+ln⁡T)=O(log⁡T).\text{Regret}_T \le \frac{G^2}{2\lambda}\,(1 + \ln T) = O(\log T).
  • Online-to-batch. On i.i.d. data, averaging the iterates converts O(T)O(\sqrt T) regret into an O(1/T)O(1/\sqrt{T}) bound on excess risk. This is precisely why SGD converges at O(1/T)O(1/\sqrt T).

Worked numeric example

Let D=2D = 2 (feasible set of radius 1), G=1G = 1 (unit-norm gradients), T=10,000T = 10{,}000. The optimal step is η⋆=D/(GT)=2/100=0.02\eta^\star = D/(G\sqrt{T}) = 2/100 = 0.02, and the regret bound is

RegretT≤DGT=2⋅1⋅100=200,\text{Regret}_T \le D G \sqrt{T} = 2\cdot 1\cdot 100 = 200,

so the average regret is at most 200/10,000=0.02200/10{,}000 = 0.02 per round. Compare a learner that plays a fixed point x^≠x⋆\hat x \ne x^\star: it pays a constant gap δ=1T∑t[ft(x^)−ft(x⋆)]>0\delta = \tfrac1T\sum_t[f_t(\hat x)-f_t(x^\star)] > 0 every round, so its regret is δT\delta T — linear, and its average regret never vanishes. The notebook verifies OGD's empirical regret stays under the DGTDG\sqrt T curve while the fixed learner's grows linearly.

See also

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Referenced by
The O(√T) Regret Bound for Online…Online Learning & RegretGradient Descent Variants