SGD — Convergence Under Every Standard Assumption

Convex, strongly convex and non-convex SGD; constant versus decaying steps; Robbins–Monro; and the difference between expected and high-probability guarantees.

SGDGraduate⏱ 1 day21 min readsgdstochastic approximationrobbins-monronoise floorvariance

7 problems →

AssumesGradient Descent and Its Convergence Rates · Modes of Convergence, LLN and CLT

Setup

DefinitionThe stochastic gradient oracle

x_{t+1} = x_t - \eta_t g_t,

where the oracle satisfies, conditional on the past $\mathcal{F}_t = \sigma(x_0,\dots,x_t)$ :

\begin{aligned} &\textbf{(A1) unbiasedness:} && \E[g_t \mid \mathcal{F}_t] = \nabla f(x_t);\\ &\textbf{(A2) bounded variance:} && \E\big[\norm{g_t - \nabla f(x_t)}_2^2 \mid \mathcal{F}_t\big] \le \sigma^2;\\ &\textbf{(A3) bounded second moment:} && \E\big[\norm{g_t}_2^2\mid\mathcal{F}_t\big] \le G^2 \quad\text{(used only for the non-smooth results)}. \end{aligned}

Assumptions

(A1) is what makes the method a stochastic approximation of gradient descent rather than a different algorithm. It holds exactly for uniform sampling from a finite training set, and it fails for importance sampling without reweighting, for asynchronous updates with stale gradients, and for gradient clipping — which is worth knowing, since clipping is standard practice in LLM training and the standard theorems do not cover it.

Run it: Gradient descent, momentum and SGDTrajectories and suboptimality curves for GD, Nesterov acceleration, heavy ball and SGD on a quadratic.

Convex case

TheoremSGD on convex Lipschitz functions

Let $f$ be convex with minimiser $x^\star$ , $\norm{x_0-x^\star}_2\le R$ , and assume (A1) and (A3). Run SGD for $T$ steps with constant $\eta = \frac{R}{G\sqrt T}$ and output $\bar x_T = \frac1T\sum_{t<T}x_t$ . Then

\E\big[f(\bar x_T)\big] - f^\star \le \frac{GR}{\sqrt T}.

Strongly convex case: the noise floor

TheoremConstant-step SGD on strongly convex smooth functions

Let $f$ be $\mu$ -strongly convex and $L$ -smooth, and assume (A1)–(A2). Run SGD with constant $\eta \le \frac{1}{2L}$ . Then

\E\norm{x_T-x^\star}_2^2 \le (1-\eta\mu)^T\norm{x_0-x^\star}_2^2 + \frac{\eta\sigma^2}{\mu}.

Key idea

Two terms, two behaviours. The first decays geometrically — this is the deterministic linear rate, unchanged. The second, $\eta\sigma^2/\mu$ , does not decay at all. Constant-step SGD does not converge to $x^\star$ ; it converges to a ball of radius $\sqrt{\eta\sigma^2/\mu}$ around it, and the radius shrinks only if you shrink $\eta$ . The trade is explicit: a larger step reaches the ball faster and the ball is bigger. This is the whole story behind learning-rate schedules, and it is visible directly in the SGD experiment as the flattening of the error curve.

TheoremSGD with decaying step size

Under the same assumptions, run SGD with $\eta_t = \frac{2}{\mu(t+\gamma)}$ for $\gamma = 4L^2/\mu^2$ . Then for all $T\ge1$ ,

\E\norm{x_T-x^\star}_2^2 \le \frac{C\sigma^2}{\mu^2 T} + \frac{C'\norm{x_0-x^\star}_2^2}{T^2}

for absolute constants $C,C'$ depending only on the ratio $L/\mu$ .

TheoremRobbins–Monro conditions

In the stochastic approximation setting, if the step sizes satisfy

\sum_{t=1}^\infty \eta_t = \infty \qquad\text{and}\qquad \sum_{t=1}^\infty\eta_t^2 < \infty,

then (under regularity conditions on $f$ and the noise) $x_t \to x^\star$ almost surely.

Quoted from Robbins and Monro; modern proofs go through supermartingale convergence. The two conditions have clean interpretations visible in the proofs above: $\sum\eta_t = \infty$ ensures the geometric-decay factor $\prod_t(1-\eta_t\mu)$ goes to zero, so the initial condition is forgotten; $\sum\eta_t^2<\infty$ ensures the accumulated noise $\sum_t\eta_t^2\sigma^2$ is finite, so the noise floor vanishes. $\eta_t = 1/t$ satisfies both; $\eta_t = 1/\sqrt t$ satisfies the first only; any constant $\eta$ satisfies the second only — and correspondingly has the floor computed above.

Non-convex case

TheoremSGD on smooth non-convex functions

Let $f$ be $L$ -smooth and bounded below by $f^\star$ , and assume (A1)–(A2). Run SGD for $T$ steps with constant $\eta = \min\left(\frac1L, \sqrt{\frac{2(f(x_0)-f^\star)}{L\sigma^2T}}\right)$ . Then

\frac1T\sum_{t=0}^{T-1}\E\norm{\nabla f(x_t)}_2^2 \le \frac{2\big(f(x_0)-f^\star\big)}{\eta T} + \eta L\sigma^2 \;\lesssim\; \sqrt{\frac{L\sigma^2\big(f(x_0)-f^\star\big)}{T}} .

What this does not say

Compare with the deterministic non-convex rate $O(1/T)$ for $\min_s\norm{\nabla f(x_s)}_2^2$ : noise costs a full square root. And the conclusion is still only about average squared gradient norm — it does not say the last iterate has small gradient, does not say any iterate is near a local minimum, and says nothing at all about $f(x_T)-\inf f$ . Every caveat from the deterministic non-convex theorem still applies, plus the new one that the guarantee is in expectation.

Mini-batching and the expectation/probability distinction

PropositionMini-batching reduces variance linearly

If $g_t^{(B)} = \frac1B\sum_{b=1}^B g_t^{(b)}$ with the $g_t^{(b)}$ conditionally i.i.d. unbiased with variance $\sigma^2$ , then $g_t^{(B)}$ is unbiased with conditional variance $\sigma^2/B$ . Consequently the noise floor of constant-step SGD becomes $\eta\sigma^2/(\mu B)$ and the non-convex rate becomes $\sqrt{L\sigma^2\Delta_0/(BT)}$ .

PropositionExpected error does not bound failure probability

A bound $\E[f(x_T)-f^\star]\le\epsilon$ implies only

\P\big(f(x_T)-f^\star > s\big)\le \frac{\epsilon}{s},

by Markov's inequality, and this is the best possible without further assumptions.

Key idea

For a $99\%$ confidence statement one needs $\epsilon \le s/100$ , i.e. a hundred-fold improvement in the expected error — a $10^4$ -fold increase in $T$ under the $1/\sqrt T$ rate. This is why high-probability bounds for SGD are a separate research programme rather than a corollary: getting $\P(\text{gap}>s)\le\delta$ with a $\log(1/\delta)$ dependence requires martingale concentration (Azuma or Freedman's inequality) applied to the noise sequence, and additional assumptions such as sub-Gaussian gradient noise. Reporting an in-expectation bound as though it were a high-confidence guarantee is a common and consequential error.

HeuristicThe SDE / diffusion approximation

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

As $\eta\to0$ with $t = \eta k$ held fixed, the SGD recursion resembles the Itô SDE

dX_t = -\nabla f(X_t)\,dt + \sqrt{\eta\,\Sigma(X_t)}\;dW_t,

where $\Sigma(x)$ is the gradient-noise covariance. Li, Tai and E make this precise as a weak approximation of order one in $\eta$ .

What this does not say

The approximation is genuinely useful for intuition — it explains why the stationary distribution depends on the ratio $\eta/B$ rather than on either separately, and it motivates linear learning-rate scaling rules. But its hypotheses are not satisfied in the regimes people invoke it for:

it requires $\eta$ small, and deep learning uses the largest stable $\eta$ ;
it assumes the noise is approximately Gaussian, whereas mini-batch gradient noise is often heavy-tailed;
it assumes $\Sigma$ varies slowly, whereas gradient noise covariance changes sharply across the loss landscape.

Statements of the form "SGD prefers flat minima because the SDE's stationary measure concentrates there" are heuristic arguments resting on these hypotheses, not theorems about SGD. They belong in the same category as the other plausible-but-unproven claims catalogued on the deep learning theory page.

Problems

Derive the constant-step SGD noise floorProof · Graduate · 1 hour SGD on convex Lipschitz objectivesProof · Intermediate · 30 min The non-convex SGD rateProof · Advanced · 1 hour Mini-batching and the compute budgetNumerical · Intermediate · 30 min Reading the Robbins–Monro conditions off the proofProof · Intermediate · 30 min Implement SGD and locate the noise floorCoding · Advanced · 3 hours Expected error does not give a high-probability guaranteeProof · Advanced · 30 min

References

PaperHerbert Robbins and Sutton Monro (1951). A stochastic approximation method
SurveyLéon Bottou, Frank E. Curtis and Jorge Nocedal (2018). Optimization Methods for Large-Scale Machine LearningThe clearest single account of the results on this page, with the constant-step noise floor made explicit.
PaperSaeed Ghadimi and Guanghui Lan (2013). Stochastic first- and zeroth-order methods for nonconvex stochastic programmingThe source of the non-convex SGD rate.
PaperAlexander Rakhlin, Ohad Shamir and Karthik Sridharan (2012). Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
PaperQianxiao Li, Cheng Tai and Weinan E (2017). Stochastic modified equations and adaptive stochastic gradient algorithmsMakes the SDE approximation precise, including the order of the approximation.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionThe stochastic gradient oracleThe three standard assumptions on the gradient estimator — unbiasedness, bounded variance, and independence across steps.
TheoremSGD on convex Lipschitz functionsproof includedWith a tuned constant step the averaged iterate attains expected suboptimality of order 1/sqrt T.
TheoremSGD on strongly convex smooth functions with constant stepproof includedThe error contracts geometrically to a noise floor proportional to the step size times the variance.
TheoremSGD with decaying step sizeproof includedWith step of order 1/(mu t) the expected error is of order sigma squared over mu squared t, with no floor.
TheoremRobbins–Monro conditionsSquare-summable but non-summable step sizes give almost sure convergence in the stochastic approximation setting.
TheoremSGD on smooth non-convex functionsproof includedThe expected squared gradient norm averaged over iterates is O(1/sqrt T) with a tuned constant step.
PropositionMini-batching reduces variance linearly, not the rateproof includedA batch of size B divides the gradient variance by B, which buys a constant factor and not a better exponent.
PropositionExpected error does not bound failure probabilityproof includedA bound on the expected gap gives only a Markov-type tail bound, which is far weaker than an exponential one.
HeuristicThe SDE / diffusion approximation of SGDIn a small-step limit SGD resembles a stochastic differential equation, a useful picture whose hypotheses rarely hold in practice.

Experiments

Gradient descent, momentum and SGD
Trajectories and suboptimality curves for GD, Nesterov acceleration, heavy ball and SGD on a quadratic.

Problems (7)

All problems