Stochastic Gradient and Mirror Descent

Intuition Beginner

Imagine you are trying to find the lowest point of a huge landscape, but the landscape is the average of millions of smaller bumpy surfaces — one per training example. Measuring the true downhill direction means touching all millions of bumps at once, which is far too slow. So you cheat. You pick one bump at random, feel its slope, and step against that. On its own this single slope is a poor guess at the true downhill direction. But averaged over many random picks, the guesses point the right way, and you drift toward the bottom. This is stochastic gradient descent, and it is how almost every large model is trained.

The price of cheating is noise. Each random slope wobbles around the true direction, so your path is jittery, like walking downhill in fog while someone keeps nudging you sideways. Two things tame the wobble. Averaging several random bumps before stepping — a mini-batch — gives a steadier guess. And shrinking your stride over time lets the early big strides cover ground while the later small strides stop you from bouncing around the bottom forever. Clever variants even remember old slopes to cancel the noise, restoring the fast steady progress of the slow exact method while keeping the cheap steps.

The second idea changes not what you measure but how you measure distance. Ordinary steps treat all directions the same, as if the world were flat. But some problems live on a special shape — a set of probabilities that must be positive and sum to one. There, "moving the same amount in every direction" is the wrong notion of a step. Mirror descent picks a distance ruler matched to the shape: you carry your point into a mirror world where stepping is easy, step there, and carry the result back. The famous case uses a ruler built from entropy, and its update multiplies each coordinate by a factor and renormalises — the multiplicative-weights rule behind many learning algorithms.

Why bother with a different ruler? Because the right ruler makes the cost of a problem grow far more slowly with the number of variables. With the flat ruler, working over $n$ probabilities costs like the square root of $n$. With the entropy ruler, it costs like the square root of the logarithm of $n$ — almost flat. Choosing the geometry, not just the step, is the whole point.

Visual Beginner

Picture two pictures. On the left, stochastic gradient descent: the true downhill path is a smooth curve, but the actual steps are a noisy zig-zag that nonetheless trends the same way, tightening as the strides shrink. On the right, mirror descent on a triangle of probabilities: an ordinary step would shoot off the triangle and need to be dragged back, while the entropy ruler bends the step to stay on the triangle naturally.

   stochastic gradient descent              mirror descent on the simplex
   (noisy steps, true trend)                (entropy ruler stays on the triangle)

   start *                                        /\
        \  .  noisy zig-zag                      /  \
         \. .  around the                       / x_t\        flat-ruler step
          .\.   true path                      /  |   \       leaves the triangle
           .\. .                              /   v    \      and must be dragged back
             \..  .                          / x_{t+1}  \
   min  ------>*  (tightens as steps shrink) /____________\  entropy step bends to stay on

idea	what it changes	effect
one random slope (SGD)	use a cheap noisy direction	fast cheap steps, jittery path
mini-batch	average a few slopes	steadier direction, less wobble
shrinking stride	step size goes to zero	stops bouncing near the bottom
variance reduction	reuse remembered slopes	cancels noise, fast steady progress
entropy ruler (mirror)	measure distance by entropy	cost grows like √(log n), not √n

Worked example Beginner

We average out noise by hand. Suppose the true slope at our point is the number $g=4$, but we can only see noisy readings: each reading equals $4$ plus a random nudge that is $+2$ half the time and $-2$ half the time. So a single reading is either $6$ or $2$, never exactly $4$.

Step 1. One reading is a poor guess. If we step against a single reading of $6$, we over-step; against a reading of $2$, we under-step. Either way we miss the true slope $4$.

Step 2. Average two readings. Take a mini-batch of two readings. The possible pairs are $(6,6)$, $(6,2)$, $(2,6)$, $(2,2)$, each with the same chance. Their averages are $6$, $4$, $4$, $2$. So two of the four times we land exactly on $4$, and the other two times we are off by only $2$ instead of by $2$ every time.

Step 3. Average four readings. With four readings the average clusters even tighter around $4$. The spread of a $k$-reading average shrinks like $1$ over the square root of $k$: four readings halve the wobble of one.

Step 4. A multiplicative-weights step. Now switch rulers. Say we have two choices with current weights $(0.5,0.5)$ and observed costs $(1,0)$ — the first choice did worse. The entropy update multiplies each weight by $e^{-\eta \text{cost}}$ with stride $\eta =1$: the new unnormalised weights are $(0.5\cdot e^{-1},0.5\cdot e^0)=(0.184,0.5)$. Renormalising to sum to one gives about $(0.269,0.731)$. The worse choice lost weight, the better choice gained, and the two still sum to one.

What this tells us. Noisy slopes are useless one at a time but reliable on average, and averaging more readings tightens the guess at a square-root rate. Switching to the entropy ruler turns a step into a multiply-and-renormalise rule that automatically keeps weights positive and summing to one.

Check your understanding Beginner

Formal definition Intermediate+

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be convex (notation from 44.01.01) with optimal value $f^{\star }$ and a minimiser $x^{\star }$ on a closed convex feasible set $C$. The subgradient inequality $g\in \partial f(x)\Rightarrow f(y)\ge f(x)+⟨g,y-x⟩$ and the subgradient method are as in 44.06.01.

Definition (stochastic first-order oracle). A stochastic subgradient oracle at $x$ returns a random vector $\tilde{g}$ with

$$\mathbb{E}[\tilde{g}\mid x]\in \partial f(x),\mathbb{E}[\Vert \tilde{g}{\Vert }^2\mid x]\le B^2,$$

that is, $\tilde{g}$ is an unbiased estimate of some subgradient with bounded second moment $B^2$. The canonical instance is the finite-sum / expectation objective $f(x)={\mathbb{E}}_{\xi }[\ell (x;\xi )]$ or $f(x)=\frac{1}{m}{\sum }_{j=1}^m{\ell }_j(x)$, where drawing $\xi$ (or an index $j$) uniformly and returning ${\nabla }_x\ell (x;\xi )$ gives such an oracle; the unbiasedness is the sample-average / law-of-large-numbers fact of 37.02.02.

Definition (stochastic gradient descent). Choose $x_0\in C$ and step sizes ${\eta }_k>0$. With $P_C$ the Euclidean projection, stochastic gradient descent (SGD) generates

$$x_{k+1}=P_C(x_k-{\eta }_k{\tilde{g}}_k),\mathbb{E}[{\tilde{g}}_k\mid {\mathcal{F}}_k]\in \partial f(x_k),$$

where ${\mathcal{F}}_k=\sigma (x_0,{\tilde{g}}_0,\dots ,{\tilde{g}}_{k-1})$ is the history. The convergence object is the averaged iterate ${\bar{x}}_k=({\sum }_{i=0}^k{\eta }_i{)}^{-1}{\sum }_{i=0}^k{\eta }_i{x}_i$ (or the uniform average), not the last iterate.

Definition (mini-batch). A mini-batch oracle averages $b$ independent draws, $\tilde{g}=\frac{1}{b}{\sum }_{s=1}^b{\nabla }_x\ell (x;{\xi }_s)$; it is unbiased with second moment reduced to ${\sigma }^2/b+\Vert \nabla f(x){\Vert }^2$ when ${\sigma }^2$ is the per-sample variance, trading the per-iteration cost $b$ against a smaller noise term.

Definition (mirror map / distance-generating function). Let $\Vert \cdot \Vert$ be a norm with dual norm $\Vert \cdot {\Vert }_{\ast }$. A mirror map (or distance-generating function) on $C$ is a function $\Phi :\mathcal{D}\to \mathbb{R}$, with $C\subseteq \overline{\mathcal{D}}$, that is differentiable and $\sigma$-strongly convex with respect to $\Vert \cdot \Vert$:

$$\Phi (y)\ge \Phi (x)+⟨\nabla \Phi (x),y-x⟩+\frac{\sigma }{2}\Vert y-x{\Vert }^2.$$

Its Bregman divergence is

$$D_{\Phi }(x,y)=\Phi (x)-\Phi (y)-⟨\nabla \Phi (y),x-y⟩\ge \frac{\sigma }{2}\Vert x-y{\Vert }^2\ge 0.$$

Taking $\Phi (x)=\frac{1}{2}\Vert x{\Vert }_2^2$ ($\sigma =1$) recovers $D_{\Phi }(x,y)=\frac{1}{2}\Vert x-y{\Vert }_2^2$ and the Euclidean geometry of 44.06.01-44.06.02.

Definition (mirror descent). With a subgradient $g_k\in \partial f(x_k)$ (or a stochastic ${\tilde{g}}_k$) and step ${\eta }_k>0$, mirror descent is the proximal-mirror update

$$x_{k+1}=\arg \underset{x\in C}{\min }\{{\eta }_k⟨g_k,x⟩+D_{\Phi }(x,x_k)\},$$

equivalently the mirror step then Bregman projection $\nabla \Phi ({\hat{y}}_{k+1})=\nabla \Phi (x_k)-{\eta }_k{g}_k$ followed by $x_{k+1}=\arg {\min }_{x\in C}{D}_{\Phi }(x,{\hat{y}}_{k+1})$. The Euclidean map gives projected subgradient descent of 44.06.01; replacing $D_{\Phi }$ by a general Bregman distance is the non-Euclidean generalisation of the proximal step of 44.06.02.

Definition (entropic mirror map). On the probability simplex ${\Delta }_n=\{x\ge 0,{\sum }_i{x}_i=1\}$ take the negative entropy $\Phi (x)={\sum }_{i=1}^n{x}_i\log x_i$, which is $1$-strongly convex with respect to $\Vert \cdot {\Vert }_1$ (Pinsker). Its Bregman divergence is the Kullback-Leibler divergence $D_{\Phi }(x,y)={\sum }_i{x}_i\log (x_i/y_i)$, and the update becomes the exponentiated-gradient / multiplicative-weights rule

$$x_{k+1,i}=\frac{x_{k,i}\exp (-{\eta }_k{g}_{k,i})}{{\sum }_j{x}_{k,j}\exp (-{\eta }_k{g}_{k,j})}.$$

Counterexamples to common slips Intermediate+

• "SGD converges in the last iterate." In general it does not: with constant step the last iterate fluctuates in a noise ball forever. The averaged iterate ${\bar{x}}_k$ (or diminishing steps) is what converges; reporting $x_k$ alone can be badly off.

• "A biased gradient estimate is fine if it is close." The analysis uses $\mathbb{E}[{\tilde{g}}_k\mid {\mathcal{F}}_k]\in \partial f(x_k)$ to make the cross-term collapse to $f(x_k)-f^{\star }$ in expectation. A fixed bias does not average away and changes the fixed point; unbiasedness, not mere closeness, is the load-bearing hypothesis.

• "Mirror descent is just a change of variables in subgradient descent." The step $\nabla \Phi ({\hat{y}}_{k+1})=\nabla \Phi (x_k)-{\eta }_k{g}_k$ updates in the dual space ($\nabla \Phi$ is the mirror to the dual); the rate constant depends on the radius of $C$ measured by $\Phi$ and on $\sigma$ for the chosen norm, not on the Euclidean radius. Choosing $\Phi$ changes the dimension-dependence, which a coordinate change cannot.

Key theorem with proof Intermediate+

The stochastic and non-Euclidean analyses both rest on one Bregman recursion that generalises the fundamental inequality $(\ast )$ of 44.06.01; taking expectations or telescoping then reads off each rate.

Theorem (mirror-descent / stochastic fundamental inequality and the $O(1/\sqrt{k})$ rate). Let $f$ be convex and let $\Phi$ be a mirror map that is $\sigma$-strongly convex with respect to $\Vert \cdot \Vert$ on $C$. Run mirror descent $x_{k+1}=\arg {\min }_{x\in C}\{\eta ⟨g_k,x⟩+D_{\Phi }(x,x_k)\}$ with $g_k\in \partial f(x_k)$, $\Vert g_k{\Vert }_{\ast }\le B$, and constant step $\eta$. Then for every $x\in C$ and each $k$,

$$\eta (f(x_k)-f(x))\le D_{\Phi }(x,x_k)-D_{\Phi }(x,x_{k+1})+\frac{{\eta }^2{B}^2}{2\sigma }.\text{\hspace{1em}(∗)}$$

Consequently, with $D_{\Phi }(x^{\star },x_0)\le R^2$ and ${\bar{x}}_k=\frac{1}{k+1}{\sum }_{i=0}^k{x}_i$,

$$f({\bar{x}}_k)-f^{\star }\le \frac{R^2}{\eta (k+1)}+\frac{\eta B^2}{2\sigma },\text{and }\eta =\frac{R}{B}\sqrt{\frac{2\sigma }{k+1}}\text{ gives }f({\bar{x}}_k)-f^{\star }\le BR\sqrt{\frac{2}{\sigma (k+1)}}.\text{\hspace{1em}(∗∗)}$$

In the stochastic case $g_k={\tilde{g}}_k$ with $\mathbb{E}[{\tilde{g}}_k\mid {\mathcal{F}}_k]\in \partial f(x_k)$ and $\mathbb{E}\Vert {\tilde{g}}_k{\Vert }_{\ast }^2\le B^2$, the same bound holds for $\mathbb{E}[f({\bar{x}}_k)]-f^{\star }$.

Proof. Let $x_{k+1}$ minimise $\psi (x)=\eta ⟨g_k,x⟩+D_{\Phi }(x,x_k)$ over $C$. The optimality condition is $⟨\nabla \psi (x_{k+1}),x-x_{k+1}⟩\ge 0$ for all $x\in C$, and since ${\nabla }_x{D}_{\Phi }(x,x_k)=\nabla \Phi (x)-\nabla \Phi (x_k)$,

$$⟨\eta g_k+\nabla \Phi (x_{k+1})-\nabla \Phi (x_k),x-x_{k+1}⟩\ge 0\text{for all }x\in C.\text{\hspace{1em}(1)}$$

The three-point identity for any $x$ reads

$$⟨\nabla \Phi (x_{k+1})-\nabla \Phi (x_k),x-x_{k+1}⟩=D_{\Phi }(x,x_k)-D_{\Phi }(x,x_{k+1})-D_{\Phi }(x_{k+1},x_k),\text{\hspace{1em}(2)}$$

which is a direct expansion of the three Bregman terms. Substituting (2) into (1) gives, for every $x\in C$,

$$\eta ⟨g_k,x_{k+1}-x⟩\le D_{\Phi }(x,x_k)-D_{\Phi }(x,x_{k+1})-D_{\Phi }(x_{k+1},x_k).$$

Split $⟨g_k,x_{k+1}-x⟩=⟨g_k,x_k-x⟩+⟨g_k,x_{k+1}-x_k⟩$. The subgradient inequality gives $⟨g_k,x_k-x⟩\ge f(x_k)-f(x)$. For the remaining term, Fenchel-Young / Cauchy-Schwarz in the pair $(\Vert \cdot \Vert ,\Vert \cdot {\Vert }_{\ast })$ and $D_{\Phi }(x_{k+1},x_k)\ge \frac{\sigma }{2}\Vert x_{k+1}-x_k{\Vert }^2$ give

$$\eta ⟨g_k,x_{k+1}-x_k⟩-D_{\Phi }(x_{k+1},x_k)\le \eta \Vert g_k{\Vert }_{\ast }\Vert x_{k+1}-x_k\Vert -\frac{\sigma }{2}\Vert x_{k+1}-x_k{\Vert }^2\le \frac{{\eta }^2\Vert g_k{\Vert }_{\ast }^2}{2\sigma },$$

the last step maximising the quadratic in $\Vert x_{k+1}-x_k\Vert$. Collecting terms and using $\Vert g_k{\Vert }_{\ast }\le B$ yields $(\ast )$.

Sum $(\ast )$ over $i=0,\dots ,k$ to telescope the Bregman differences; dropping the nonnegative $D_{\Phi }(x,x_{k+1})$ and using convexity $f({\bar{x}}_k)\le \frac{1}{k+1}{\sum }_{i}f(x_i)$,

$$\eta (k+1)(f({\bar{x}}_k)-f(x))\le D_{\Phi }(x,x_0)+(k+1)\frac{{\eta }^2{B}^2}{2\sigma }.$$

Putting $x=x^{\star }$, $D_{\Phi }(x^{\star },x_0)\le R^2$, dividing by $\eta (k+1)$, and optimising $\eta$ gives $(\ast \ast )$. In the stochastic case, take conditional expectation given ${\mathcal{F}}_k$: $\mathbb{E}[⟨{\tilde{g}}_k,x_k-x^{\star }⟩\mid {\mathcal{F}}_k]=⟨\mathbb{E}[{\tilde{g}}_k\mid {\mathcal{F}}_k],x_k-x^{\star }⟩\ge f(x_k)-f^{\star }$ by unbiasedness, and $\mathbb{E}\Vert {\tilde{g}}_k{\Vert }_{\ast }^2\le B^2$ bounds the noise term; the tower property over the telescoped sum reproduces $(\ast \ast )$ in expectation. $\square$

Bridge. This single Bregman recursion $(\ast )$ is the foundational reason both stochastic and non-Euclidean first-order methods converge, and it builds toward the strongly-convex $O(1/k)$ rate and the simplex dimension-dependence of the Advanced results, where the entropy map is read off $(\ast \ast )$ directly. This is exactly the non-Euclidean analogue of the fundamental inequality of 44.06.01: where that argument used the Euclidean distance as the Lyapunov quantity, here the Bregman divergence $D_{\Phi }$ plays the role, and the proof generalises projected subgradient descent to an arbitrary geometry with no loss of rate. The mirror update is dual to the proximal step of 44.06.02 — both minimise a linearised objective plus a divergence — and the central insight is that the rate constant $R^2/\sigma$, set by the geometry of $C$ rather than its Euclidean radius, is what the entropy map shrinks from $\sqrt{n}$ to $\sqrt{\log n}$. Putting these together, the stochastic and mirror generalisations share one recursion, and it appears again in the regret analysis of online convex optimization and in the variance-reduced methods that recover linear rates.

Exercises Intermediate+

Advanced results Master

Mirror descent is the update $x_{k+1}=\arg {\min }_{x\in C}\{{\eta }_k⟨g_k,x⟩+D_{\Phi }(x,x_k)\}$, and the results below extend the single recursion $(\ast )$ to the strongly-convex rate, the simplex dimension-dependence, variance reduction, and the regret viewpoint that unifies the stochastic and online settings.

Theorem 1 (rates of stochastic gradient descent). For convex $L$-Lipschitz $f$ (so $B=L$) and a stochastic oracle with $\mathbb{E}\Vert {\tilde{g}}_k{\Vert }^2\le B^2$, SGD with ${\eta }_k=R/(B\sqrt{k+1})$ (or constant $\eta =(R/B)\sqrt{2/(k+1)}$ on a fixed horizon) attains $\mathbb{E}[f({\bar{x}}_k)]-f^{\star }=O(BR/\sqrt{k})$. If $f$ is additionally $\alpha$-strongly convex, the step ${\eta }_k=2/(\alpha (k+1))$ with the weighted average ${\bar{x}}_k={\sum }_i(i+1)x_i/{\sum }_i(i+1)$ gives $\mathbb{E}[f({\bar{x}}_k)]-f^{\star }=O(B^2/(\alpha k))$ (Exercise 6) ^{[Bubeck, S. — Convex Optimization: Algorithms and Complexity (2015)]}. Both rates are minimax-optimal for the respective stochastic first-order classes, so SGD is the rate-optimal stochastic method; the only freedom is in the constant, which mini-batching and variance reduction improve.

Theorem 2 (the simplex and the entropic dimension-dependence). On ${\Delta }_n$ with $f$ convex and $\Vert g{\Vert }_{\infty }\le L_{\infty }$, take the entropy map $\Phi (x)={\sum }_i{x}_i\log x_i$, $1$-strongly convex with respect to $\Vert \cdot {\Vert }_1$ (Pinsker), with $D_{\Phi }(x^{\star },x_0)=\mathrm{KL}(x^{\star }\Vert x_0)\le \log n$ for the uniform start. Then $(\ast \ast )$ gives $f({\bar{x}}_k)-f^{\star }\le L_{\infty }\sqrt{2\log n/(k+1)}=O\left(L_{\infty }\sqrt{\log n/k}\right)$ ^{[Nemirovski, A. & Yudin, D. — Problem Complexity and Method Efficiency in Optimization (1983)]}. Projected (Euclidean) subgradient descent on ${\Delta }_n$ achieves only $O(L_2\sqrt{1/k})$ with $L_2$ the ${\ell }_2$ subgradient bound, and since $L_{\infty }\le L_2\le \sqrt{n}{L}_{\infty }$ the worst-case ratio is $\sqrt{n/\log n}$ in favour of the entropic map. The improvement is the original motivation of the mirror-descent scheme: the rate constant tracks the prox-radius of $C$ in the intrinsic geometry, and entropy is the geometry of the simplex.

Theorem 3 (variance reduction recovers linear rates). For the finite sum $f=\frac{1}{m}{\sum }_{j=1}^m{f}_j$ with each $f_j$ convex $L$-smooth and $f$ $\alpha$-strongly convex, plain SGD with constant step converges only to a noise ball and with diminishing step only at $O(1/k)$. SVRG periodically computes a full gradient $\nabla f(\tilde{x})$ at a snapshot $\tilde{x}$ and uses the corrected estimate ${\tilde{g}}_k=\nabla f_j(x_k)-\nabla f_j(\tilde{x})+\nabla f(\tilde{x})$, which is unbiased and has variance $\to 0$ as $x_k,\tilde{x}\to x^{\star }$; SAG/SAGA maintain a running table of per-component gradients to the same effect. Each attains a linear rate $\mathbb{E}[f(x_k)-f^{\star }]\le (1-c/\kappa {)}^k(f(x_0)-f^{\star })$ with $\kappa =L/\alpha$, matching full-batch gradient descent in rate at $O(1)$ per-iteration cost amortised ^{[Bubeck, S. — Convex Optimization: Algorithms and Complexity (2015)]}. The variance term, not the bias, is what the snapshot cancels; once it vanishes the strongly-convex contraction of the deterministic method is restored.

Theorem 4 (regret and online convex optimization). In the online model, against any comparator $x\in C$, mirror descent on linearised losses satisfies ${\mathrm{Reg}}_T={\sum }_{t=1}^T⟨g_t,x_t-x⟩\le \frac{R^2}{\eta }+\frac{\eta B^{2}T}{2\sigma }$, optimised to ${\mathrm{Reg}}_T=O(BR\sqrt{T/\sigma })$; on the simplex with the entropy map this is the $O(L_{\infty }\sqrt{T\log n})$ regret of Hedge / multiplicative weights ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. Online-to-batch conversion (Exercise 8) turns any $O(\sqrt{T})$ regret into an $O(1/\sqrt{T})$ stochastic-optimization rate, so the offline rates of Theorem 1 and the online regret are the same statement read in two directions. The strongly-convex refinement uses ${\eta }_t=1/(\alpha t)$ to reach $O(\log T)$ regret, the online face of the $O(1/k)$ rate.

Synthesis. The single Bregman recursion $(\ast )$ is the foundational reason the entire stochastic and non-Euclidean theory coheres, and the central insight is that the Bregman divergence $D_{\Phi }$, not the Euclidean distance, is the Lyapunov quantity — this is exactly why the rate constant tracks the intrinsic geometry of $C$ and why the entropy map turns the simplex factor from $\sqrt{n}$ into $\sqrt{\log n}$. The stochastic rates of Theorem 1 are the in-expectation form of $(\ast \ast )$, with unbiasedness the load-bearing hypothesis that makes the cross-term collapse and the bounded second moment the noise floor; variance reduction is dual to this, cancelling precisely the noise term so the deterministic strongly-convex contraction reappears, and the foundational reason it works is that the snapshot correction leaves the estimate unbiased while driving its variance to zero. The regret viewpoint of Theorem 4 is not a separate theory but the same recursion summed against a fixed comparator, and online-to-batch conversion shows the offline $O(1/\sqrt{k})$ and the online $O(\sqrt{T})$ are one fact; putting these together, mirror descent generalises the projected subgradient method of 44.06.01 and is dual to the proximal-gradient method of 44.06.02, both being minimisers of a linearised objective plus a divergence, and the bridge to the rest of large-scale optimization is precisely the freedom to choose $\Phi$ — the geometry, not merely the step, is the design variable that powers large-scale machine-learning training.

Full proof set Master

Proposition 1 (three-point Bregman identity). For differentiable $\Phi$ and any $x,y,z$, $⟨\nabla \Phi (z)-\nabla \Phi (y),x-z⟩=D_{\Phi }(x,y)-D_{\Phi }(x,z)-D_{\Phi }(z,y)$.

Proof. This is Exercise 7; the computation expands the three divergences from the definition $D_{\Phi }(a,b)=\Phi (a)-\Phi (b)-⟨\nabla \Phi (b),a-b⟩$, cancels all $\Phi$ values, combines the two $\nabla \Phi (y)$ inner products into $⟨\nabla \Phi (y),z-x⟩$, and adds $⟨\nabla \Phi (z),x-z⟩$; the residual $⟨\nabla \Phi (y),(z-x)+(x-z)⟩$ vanishes, leaving $⟨\nabla \Phi (z)-\nabla \Phi (y),x-z⟩$. $\square$

Proposition 2 (mirror-descent fundamental inequality). Let $\Phi$ be $\sigma$-strongly convex with respect to $\Vert \cdot \Vert$, $g_k\in \partial f(x_k)$ with $\Vert g_k{\Vert }_{\ast }\le B$, and $x_{k+1}=\arg {\min }_{x\in C}\{\eta ⟨g_k,x⟩+D_{\Phi }(x,x_k)\}$. Then for all $x\in C$, $\eta (f(x_k)-f(x))\le D_{\Phi }(x,x_k)-D_{\Phi }(x,x_{k+1})+{\eta }^2{B}^2/(2\sigma )$.

Proof. The constrained optimality condition for the convex problem defining $x_{k+1}$ is $⟨\eta g_k+\nabla \Phi (x_{k+1})-\nabla \Phi (x_k),x-x_{k+1}⟩\ge 0$ for all $x\in C$. Rearranged, $\eta ⟨g_k,x_{k+1}-x⟩\le ⟨\nabla \Phi (x_{k+1})-\nabla \Phi (x_k),x-x_{k+1}⟩=D_{\Phi }(x,x_k)-D_{\Phi }(x,x_{k+1})-D_{\Phi }(x_{k+1},x_k)$ by Proposition 1 (with $z=x_{k+1}$, $y=x_k$). Write $\eta ⟨g_k,x_{k+1}-x⟩=\eta ⟨g_k,x_k-x⟩+\eta ⟨g_k,x_{k+1}-x_k⟩$. The subgradient inequality gives $\eta ⟨g_k,x_k-x⟩\ge \eta (f(x_k)-f(x))$. By the generalised Cauchy-Schwarz $⟨g_k,x_{k+1}-x_k⟩\le \Vert g_k{\Vert }_{\ast }\Vert x_{k+1}-x_k\Vert$ and strong convexity $D_{\Phi }(x_{k+1},x_k)\ge \frac{\sigma }{2}\Vert x_{k+1}-x_k{\Vert }^2$,

$$\eta ⟨g_k,x_{k+1}-x_k⟩-D_{\Phi }(x_{k+1},x_k)\le \underset{s\ge 0}{\max }(\eta Bs-\frac{\sigma }{2}{s}^2)=\frac{{\eta }^2{B}^2}{2\sigma }.$$

Combining the displayed inequalities, $\eta (f(x_k)-f(x))\le D_{\Phi }(x,x_k)-D_{\Phi }(x,x_{k+1})+{\eta }^2{B}^2/(2\sigma )$. $\square$

Proposition 3 ($O(1/\sqrt{k})$ averaged-iterate rate). Under Proposition 2 with constant $\eta$ and $D_{\Phi }(x^{\star },x_0)\le R^2$, $f({\bar{x}}_k)-f^{\star }\le R^2/(\eta (k+1))+\eta B^2/(2\sigma )$, minimised over $\eta$ at $f({\bar{x}}_k)-f^{\star }\le BR\sqrt{2/(\sigma (k+1))}$.

Proof. Sum Proposition 2 with $x=x^{\star }$ over $i=0,\dots ,k$: the Bregman terms telescope to $D_{\Phi }(x^{\star },x_0)-D_{\Phi }(x^{\star },x_{k+1})\le R^2$, so $\eta {\sum }_{i=0}^k(f(x_i)-f^{\star })\le R^2+(k+1){\eta }^2{B}^2/(2\sigma )$. Convexity gives $f({\bar{x}}_k)\le \frac{1}{k+1}{\sum }_{i}f(x_i)$, hence $\eta (k+1)(f({\bar{x}}_k)-f^{\star })\le R^2+(k+1){\eta }^2{B}^2/(2\sigma )$; divide by $\eta (k+1)$. Minimising $h(\eta )=R^2/(\eta (k+1))+\eta B^2/(2\sigma )$ over $\eta >0$: $h^{\prime }(\eta )=-R^2/({\eta }^2(k+1))+B^2/(2\sigma )=0$ gives $\eta =R\sqrt{2\sigma }/(B\sqrt{k+1})$, and $h$ at this $\eta$ is $2\sqrt{R^2{B}^2/(2\sigma (k+1))}=BR\sqrt{2/(\sigma (k+1))}$. $\square$

Proposition 4 (stochastic rate in expectation). With $g_k={\tilde{g}}_k$, $\mathbb{E}[{\tilde{g}}_k\mid {\mathcal{F}}_k]\in \partial f(x_k)$, $\mathbb{E}[\Vert {\tilde{g}}_k{\Vert }_{\ast }^2\mid {\mathcal{F}}_k]\le B^2$, the bound of Proposition 3 holds for $\mathbb{E}[f({\bar{x}}_k)]-f^{\star }$.

Proof. The deterministic step of Proposition 2 uses $⟨g_k,x_k-x^{\star }⟩\ge f(x_k)-f^{\star }$ and $\Vert g_k{\Vert }_{\ast }\le B$. Replace these by conditional expectations: $\mathbb{E}[⟨{\tilde{g}}_k,x_k-x^{\star }⟩\mid {\mathcal{F}}_k]=⟨\mathbb{E}[{\tilde{g}}_k\mid {\mathcal{F}}_k],x_k-x^{\star }⟩\ge f(x_k)-f^{\star }$ since $x_k$ is ${\mathcal{F}}_k$-measurable and $\mathbb{E}[{\tilde{g}}_k\mid {\mathcal{F}}_k]$ is a subgradient, and the noise term is bounded by ${\eta }^2\mathbb{E}[\Vert {\tilde{g}}_k{\Vert }_{\ast }^2\mid {\mathcal{F}}_k]/(2\sigma )\le {\eta }^2{B}^2/(2\sigma )$. Thus $\eta \mathbb{E}[f(x_k)-f^{\star }\mid {\mathcal{F}}_k]\le \mathbb{E}[D_{\Phi }(x^{\star },x_k)-D_{\Phi }(x^{\star },x_{k+1})\mid {\mathcal{F}}_k]+{\eta }^2{B}^2/(2\sigma )$. Take total expectation, sum over $i\le k$ (the telescope survives by the tower property since $D_{\Phi }(x^{\star },x_{k+1})$ is integrable), and apply Jensen $\mathbb{E}f({\bar{x}}_k)\le \frac{1}{k+1}{\sum }_i\mathbb{E}f(x_i)$ to reach the stated bound. $\square$

Proposition 5 (entropy map is $1$-strongly convex in ${\ell }_1$; the simplex rate). On ${\Delta }_n$, $\Phi (x)={\sum }_i{x}_i\log x_i$ satisfies $D_{\Phi }(x,y)=\mathrm{KL}(x\Vert y)\ge \frac{1}{2}\Vert x-y{\Vert }_1^2$, and mirror descent with $\Vert g{\Vert }_{\infty }\le L_{\infty }$ attains $f({\bar{x}}_k)-f^{\star }\le L_{\infty }\sqrt{2\log n/(k+1)}$.

Proof. The Bregman divergence of the negative entropy is $D_{\Phi }(x,y)={\sum }_i{x}_i\log x_i-{\sum }_i{y}_i\log y_i-{\sum }_i(\log y_i+1)(x_i-y_i)$; on ${\Delta }_n$ the $+1$ terms sum to ${\sum }_i(x_i-y_i)=0$, leaving ${\sum }_i{x}_i\log (x_i/y_i)=\mathrm{KL}(x\Vert y)$. Pinsker's inequality $\mathrm{KL}(x\Vert y)\ge \frac{1}{2}\Vert x-y{\Vert }_1^2$ is exactly $1$-strong convexity of $\Phi$ with respect to $\Vert \cdot {\Vert }_1$ (so $\sigma =1$ and the dual norm is $\Vert \cdot {\Vert }_{\infty }$). The prox-radius is ${\sup }_{x\in {\Delta }_n}\mathrm{KL}(x\Vert x_0)$ at the uniform $x_0=(1/n,\dots ,1/n)$: $\mathrm{KL}(x\Vert x_0)={\sum }_i{x}_i\log (n{x}_i)=\log n-H(x)\le \log n$, since entropy $H(x)\ge 0$. Hence $R^2=\log n$, $B=L_{\infty }$, $\sigma =1$ in Proposition 3, giving $f({\bar{x}}_k)-f^{\star }\le L_{\infty }\sqrt{2\log n/(k+1)}$. $\square$

Proposition 6 (Euclidean mirror descent is projected subgradient descent). For $\Phi (x)=\frac{1}{2}\Vert x{\Vert }_2^2$, the mirror update equals $x_{k+1}=P_C(x_k-\eta g_k)$.

Proof. Here $D_{\Phi }(x,x_k)=\frac{1}{2}\Vert x-x_k{\Vert }_2^2$, so $x_{k+1}=\arg {\min }_{x\in C}\{\eta ⟨g_k,x⟩+\frac{1}{2}\Vert x-x_k{\Vert }^2\}$. Completing the square, $\eta ⟨g_k,x⟩+\frac{1}{2}\Vert x-x_k{\Vert }^2=\frac{1}{2}\Vert x-(x_k-\eta g_k){\Vert }^2+\text{const}$, whose constrained minimiser over $C$ is by definition the Euclidean projection $P_C(x_k-\eta g_k)$. The mirror scheme contains projected subgradient descent of 44.06.01 as the case $\Phi =\frac{1}{2}\Vert \cdot {\Vert }_2^2$, $\sigma =1$. $\square$

Connections Master

• Mirror descent generalises the projected subgradient method of 44.06.01: the Euclidean mirror map $\Phi =\frac{1}{2}\Vert \cdot {\Vert }_2^2$ reduces the Bregman fundamental inequality $(\ast )$ to that unit's recursion $\Vert x_{k+1}-x^{\star }{\Vert }^2\le \Vert x_k-x^{\star }{\Vert }^2-2\eta (f(x_k)-f^{\star })+{\eta }^2\Vert g_k{\Vert }^2$ and recovers the $O(1/\sqrt{k})$ rate, while the stochastic version randomises that unit's deterministic subgradient into an unbiased oracle and keeps the rate in expectation. The lower bound proved there caps the deterministic nonsmooth class, and SGD/mirror descent are the rate-optimal members of the stochastic and non-Euclidean refinements of it.

• The proximal-gradient method of 44.06.02 and mirror descent are dual constructions: both minimise a linearised objective plus a regulariser — the Euclidean prox $\arg \min \{\eta ⟨\nabla f,x⟩+\frac{1}{2}\Vert x-x_k{\Vert }^2\}+g$ versus the Bregman prox $\arg \min \{\eta ⟨g_k,x⟩+D_{\Phi }(x,x_k)\}$ — so the mirror update is the non-Euclidean proximal step, and the Moreau-envelope smoothing of that unit corresponds to the strong convexity of $\Phi$ here. The composite mirror-prox and the proximal-gradient method meet in the Bregman proximal-gradient algorithm.

• Stochastic gradient descent rests on the unbiased-estimator mechanism formalised by the strong law of large numbers in 37.02.02: the sample-average gradient $\frac{1}{b}{\sum }_s\nabla \ell (x;{\xi }_s)$ converges to the true gradient $\nabla f(x)={\mathbb{E}}_{\xi }[\nabla \ell (x;\xi )]$, and the variance term $B^2$ in the rate is the second-moment quantity that unit's law controls; mini-batching is the finite-sample form of that convergence, and variance reduction engineers the error to vanish along the trajectory.

Historical & philosophical context Master

The stochastic-approximation idea — replacing an exact gradient by a noisy unbiased estimate and shrinking the step — originates with Herbert Robbins and Sutton Monro in 1951 ^{[Robbins & Monro 1951]}, whose convergence conditions $\sum {\eta }_k=\infty$, $\sum {\eta }_k^2<\infty$ are still the canonical diminishing-step regime; Kiefer and Wolfowitz (1952) extended it to gradient estimation by finite differences. Mirror descent is due to Arkadi Nemirovski and David Yudin, whose 1983 monograph introduced the prox-function / distance-generating-function scheme and proved that the geometry of the feasible set, not the Euclidean norm, governs the complexity — the demonstration that the entropy prox-function gives a $\sqrt{\log n}$ rather than $\sqrt{n}$ dependence on the simplex is theirs ^{[Nemirovski & Yudin 1983]}. The multiplicative-weights / exponentiated-gradient instance was rediscovered repeatedly across learning theory, notably by Littlestone and Warmuth (1994) for the weighted-majority algorithm and by Freund and Schapire (1997) for Hedge and boosting ^{[Freund & Schapire 1997]}. The modern synthesis — mirror descent as the canonical non-Euclidean and online method, the regret / online-to-batch viewpoint, and the SGD rates — is presented by Bubeck ^{[Bubeck 2015]} and by Beck ^{[Beck 2017]}, the source whose Bregman-prox formulation this unit follows. Variance reduction (SAG, SVRG, SAGA) was developed by Le Roux-Schmidt-Bach (2012), Johnson-Zhang (2013), and Defazio-Bach-Lacoste-Julien (2014).

Bibliography Master

@article{robbinsmonro1951,
  author  = {Robbins, Herbert and Monro, Sutton},
  title   = {A Stochastic Approximation Method},
  journal = {The Annals of Mathematical Statistics},
  volume  = {22},
  number  = {3},
  pages   = {400--407},
  year    = {1951}
}

@book{nemirovskiyudin1983,
  author    = {Nemirovski, Arkadi S. and Yudin, David B.},
  title     = {Problem Complexity and Method Efficiency in Optimization},
  publisher = {Wiley-Interscience},
  year      = {1983}
}

@article{bubeck2015convex,
  author  = {Bubeck, S\'ebastien},
  title   = {Convex Optimization: Algorithms and Complexity},
  journal = {Foundations and Trends in Machine Learning},
  volume  = {8},
  number  = {3-4},
  pages   = {231--357},
  year    = {2015}
}

@book{beck2017fom,
  author    = {Beck, Amir},
  title     = {First-Order Methods in Optimization},
  series    = {MOS-SIAM Series on Optimization},
  number    = {25},
  publisher = {SIAM},
  year      = {2017}
}

@article{freundschapire1997,
  author  = {Freund, Yoav and Schapire, Robert E.},
  title   = {A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting},
  journal = {Journal of Computer and System Sciences},
  volume  = {55},
  number  = {1},
  pages   = {119--139},
  year    = {1997}
}

@article{johnsonzhang2013svrg,
  author  = {Johnson, Rie and Zhang, Tong},
  title   = {Accelerating Stochastic Gradient Descent using Predictive Variance Reduction},
  journal = {Advances in Neural Information Processing Systems},
  volume  = {26},
  year    = {2013}
}

@article{bottoucurtisnocedal2018,
  author  = {Bottou, L\'eon and Curtis, Frank E. and Nocedal, Jorge},
  title   = {Optimization Methods for Large-Scale Machine Learning},
  journal = {SIAM Review},
  volume  = {60},
  number  = {2},
  pages   = {223--311},
  year    = {2018}
}