Gradient Descent and Its Convergence Rates

Four complete convergence proofs — convex, strongly convex, non-smooth and non-convex — with the exact assumptions each one needs.

OptimizationAdvanced⏱ 1 day18 min readgradient descentconvergence ratesubgradientnon-convexlower bound

7 problems →

AssumesConvex Sets, Convex Functions, Smoothness and Strong Convexity

The algorithm is

x_{t+1} = x_t - \eta\,\nabla f(x_t),

and the question is how fast $f(x_t) - f^\star$ goes to zero. The answer depends entirely on which assumptions hold, and the four theorems below give four qualitatively different answers. The table is the summary.

Assumptions	Quantity bounded	Rate	Steps for $\eps$
convex, $L$ -smooth	$f(x_t)-f^\star$	$\dfrac{L\norm{x_0-x^\star}^2}{2t}$	$O(1/\eps)$
$\mu$ -strongly convex, $L$ -smooth	$f(x_t)-f^\star$	$\left(1-\tfrac1\kappa\right)^{t}\big(f(x_0)-f^\star\big)$	$O(\kappa\log(1/\eps))$
convex, $G$ -Lipschitz (non-smooth)	$f(\bar x_t)-f^\star$	$\dfrac{G\norm{x_0-x^\star}}{\sqrt t}$	$O(1/\eps^2)$
$L$ -smooth only	$\min_{s\le t}\norm{\nabla f(x_s)}$	$\sqrt{\dfrac{2L(f(x_0)-f^\star)}{t}}$	$O(1/\eps^2)$

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

The descent lemma applied

LemmaOne step decreases the objective

Let $f$ be $L$ -smooth and let $x^+ = x - \eta\nabla f(x)$ with $0 < \eta \le 1/L$ . Then

f(x^+) \le f(x) - \frac{\eta}{2}\norm{\nabla f(x)}_2^2 .

Assumptions

$L$ -smoothness only. No convexity is used, which is why this lemma is the starting point of the non-convex analysis as well. The step-size restriction $\eta \le 1/L$ is essential and is not a technical convenience — see the divergence proposition at the end of the page.

Convex and smooth: the $O(1/t)$ rate

TheoremGradient descent on convex smooth functions

Let $f$ be convex, $L$ -smooth, with a minimiser $x^\star$ . Run gradient descent with $\eta = 1/L$ . Then for all $t\ge1$ ,

f(x_t) - f^\star \le \frac{L\norm{x_0-x^\star}_2^2}{2t}.

Key idea

Step 1 is the move to internalise: the squared distance to the optimum acts as a potential function (a Lyapunov function), and each step decreases it by an amount proportional to the suboptimality. Telescoping then converts a per-step decrease into a rate. Every convergence proof in this section — including the momentum and stochastic ones — is an instance of the same template with a cleverer potential.

What this does not say

The $O(1/t)$ rate is sublinear: reaching $\eps$ takes $\Theta(1/\eps)$ steps, so three more digits of accuracy costs a thousand times more work. There is no contradiction with the linear rate below; the difference is entirely the presence of strong convexity. Also note that the bound depends on $\norm{x_0-x^\star}_2$ , so it is not scale-free, and it says nothing about $\norm{x_t-x^\star}$ — a convex smooth function can have a flat valley of near-minimisers far apart from each other.

Strongly convex and smooth: the linear rate

TheoremGradient descent on smooth strongly convex functions

Let $f$ be $\mu$ -strongly convex and $L$ -smooth, $\kappa = L/\mu$ , and run gradient descent with $\eta = 1/L$ . Then

f(x_t) - f^\star \le \left(1-\frac1\kappa\right)^t\big(f(x_0)-f^\star\big),

and consequently, by quadratic growth, $\norm{x_t-x^\star}_2^2 \le \frac2\mu\left(1-\frac1\kappa\right)^t\big(f(x_0)-f^\star\big)$ .

Non-convex and smooth: stationarity only

TheoremGradient descent on smooth non-convex functions

Let $f$ be $L$ -smooth and bounded below by $f^\star$ , and run gradient descent with $\eta = 1/L$ . Then

\min_{0\le s < t}\norm{\nabla f(x_s)}_2 \le \sqrt{\frac{2L\big(f(x_0)-f^\star\big)}{t}} .

What this does not say

Read the conclusion very carefully. It says: some iterate among the first $t$ has small gradient. It does not say

that the last iterate has small gradient (though the monotonicity of $f$ makes it plausible),
that any iterate is near a local minimum — a saddle point also has zero gradient,
that $f(x_t)$ is close to $\inf f$ — the iterates may converge to a strictly suboptimal stationary point,
that anything converges at all, in the sense of the iterates having a limit.

This is the strongest general statement available for smooth non-convex optimisation with a first-order method, and the gap between it and what practitioners want is the subject of the deep learning theory page. A concrete example of the gap: $f(x) = x^3 - 3x$ on $\R$ has a local minimum at $x=1$ and a local maximum at $x=-1$ ; started at $x_0 = -1$ , gradient descent stays there forever, satisfying the theorem exactly and finding nothing.

Non-smooth convex: the subgradient method

DefinitionSubgradient

$g$ is a subgradient of a convex $f$ at $x$ if $f(y)\ge f(x)+\ip{g}{y-x}$ for all $y$ . The set of subgradients is the subdifferential $\partial f(x)$ , which is non-empty for convex $f$ on the interior of its domain and equals $\{\nabla f(x)\}$ where $f$ is differentiable.

TheoremSubgradient method

Let $f$ be convex and $G$ -Lipschitz (equivalently, $\norm{g}_2\le G$ for all $g\in\partial f(x)$ and all $x$ ), with minimiser $x^\star$ and $\norm{x_0-x^\star}_2\le R$ . Run $x_{t+1} = x_t - \eta g_t$ with $g_t\in\partial f(x_t)$ and fixed $\eta = \frac{R}{G\sqrt T}$ for a horizon $T$ . Then the average iterate $\bar x_T = \frac1T\sum_{t<T}x_t$ satisfies

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

Step size and lower bounds

PropositionDivergence above the threshold

Let $f(x) = \tfrac{L}{2}x^2$ on $\R$ , so $f$ is $L$ -smooth and $L$ -strongly convex. Gradient descent with step $\eta$ satisfies $x_{t} = (1-\eta L)^tx_0$ , hence converges if and only if $0<\eta<2/L$ , is stationary if $\eta = 2/L$ , and diverges if $\eta>2/L$ .

Key idea

The threshold $2/L$ is exact, not an artefact. It is also the reason "learning rate too high" produces divergence rather than slow progress: past the threshold the dynamics are unstable, and the failure is qualitative. In deep learning the empirical counterpart is the "edge of stability" phenomenon, where training settles at a sharpness $L \approx 2/\eta$ — the largest value compatible with stability. That is an empirical observation, discussed as such on the deep learning theory page.

TheoremLower bound for first-order methods

Consider any method that, at step $t$ , outputs a point in the affine span of $x_0,\nabla f(x_0),\dots,\nabla f(x_{t-1})$ .

For convex $L$ -smooth $f$ in dimension $d > t$ , there is an instance with $f(x_t)-f^\star \gtrsim \dfrac{L\norm{x_0-x^\star}_2^2}{(t+1)^2}$ .
For $\mu$ -strongly convex $L$ -smooth $f$ , there is an instance with $f(x_t)-f^\star \gtrsim \left(\dfrac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^{2t}\big(f(x_0)-f^\star\big)$ .

Quoted from Nesterov's lectures; the instances are quadratics built from a tridiagonal matrix that "reveals" only one new coordinate per gradient query. The consequences are important:

Plain gradient descent's $O(1/t)$ is not optimal; $O(1/t^2)$ is achievable and is attained by Nesterov acceleration.
The $\sqrt\kappa$ in the strongly convex lower bound is also achieved by acceleration, so the gap between $\kappa$ and $\sqrt\kappa$ closes exactly.
No first-order method can do better. Beating these rates requires a stronger oracle — second-order information, as in Newton's method, or structure beyond smoothness and convexity.

Problems

Prove the O(1/t) rate for gradient descentProof · Advanced · 1 hour Linear convergence under strong convexityProof · Intermediate · 30 min Non-convex gradient descent reaches an approximate stationary pointProof · Intermediate · 30 min The exact step-size threshold on a quadraticProof · Beginner · 15 min Why the subgradient method needs averagingProof · Advanced · 30 min Implement gradient descent and verify all four ratesCoding · Advanced · 3 hours Gradient descent with exact line search on a quadraticProof · Advanced · 1 hour

References

BookYurii Nesterov (2018). Lectures on Convex OptimizationThe source of the complexity framework and of the lower bounds quoted here.
SurveySébastien Bubeck (2015). Convex Optimization: Algorithms and Complexity
BookStephen Boyd and Lieven Vandenberghe (2004). Convex Optimization

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

LemmaOne step of gradient descent decreases the objectiveproof includedWith step size at most 1/L each gradient step reduces f by at least half the step times the squared gradient norm.
TheoremGradient descent on convex smooth functionsproof includedWith step 1/L the suboptimality after t steps is at most L times the initial squared distance over 2t.
TheoremGradient descent on smooth strongly convex functionsproof includedWith step 1/L the iterates converge geometrically at rate (1 - 1/kappa).
TheoremGradient descent on smooth non-convex functionsproof includedThe smallest gradient norm among the first t iterates is O(1/sqrt t); no statement about minima is possible.
TheoremSubgradient method on non-smooth convex functionsproof includedWith a fixed horizon and tuned step the averaged iterate attains O(1/sqrt t) suboptimality.
TheoremLower bound for first-order methodsNo method that only queries gradients can beat O(1/t^2) on convex smooth problems or (1 - 1/sqrt kappa)^t on strongly convex ones.
PropositionDivergence above the step-size thresholdproof includedOn a quadratic, gradient descent diverges precisely when the step exceeds 2/L.

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