The Descent Lemma is the Whole Story

One inequality decides whether gradient descent converges, how fast, and when it quietly stops making progress. Everything else — momentum, step sizes, stochastic tricks — is negotiation with that inequality.

Start with the intuition

Gradient descent, at its heart, is a bet: if I stand on a landscape and take a small step in the direction of steepest descent, I will end up lower than I started. The bet works if the landscape does not surprise me — if it does not suddenly curl up under my feet in the direction I stepped. The mathematical way to say "will not surprise me" is a bound on how quickly the gradient can change. That bound is called L-smoothness, and it delivers a single inequality — the descent lemma — from which the entire success or failure of gradient descent can be read.

Once you internalize the descent lemma, everything else clicks: why the step size $1/L$ is not a numerical accident, why convergence is sublinear on convex problems and linear on strongly convex ones, why momentum can accelerate, and why the whole story unravels when the gradient has a jump discontinuity, when the landscape has saddles, or when the gradient is contaminated with noise.

The one inequality

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a differentiable function. Call it L-smooth if its gradient is Lipschitz continuous with constant $L$:

Here $\nabla f(x) \in \mathbb{R}^n$ is the gradient of $f$ at the point $x$, and $\|\cdot\|$ is the Euclidean norm. In plain terms: the gradient cannot rotate or grow faster than a linear rate $L$ as you move. Landscapes with bounded curvature satisfy this — when the Hessian $\nabla^2 f$ exists, the smallest valid $L$ equals the supremum over the domain of the largest absolute eigenvalue (the spectral norm) of $\nabla^2 f$. The absolute value matters: in the non-convex case the Hessian can have negative eigenvalues, and it is their magnitude that must stay bounded.

The descent lemma says that L-smoothness alone (no convexity!) forces $f$ to lie below a quadratic:

Read aloud: the value at $y$ is at most the linear (first-order Taylor) approximation at $x$, plus a quadratic correction whose curvature is $L$. The right-hand side is a paraboloid that touches $f$ at $x$ and sits above $f$ everywhere.

Why is this true? Apply the fundamental theorem of calculus along the segment from $x$ to $y$. Writing $\phi(t) = f(x + t(y-x))$ and differentiating under the integral,

Subtract $\langle \nabla f(x), y-x\rangle$ from both sides; inside the integral, apply Cauchy–Schwarz then the Lipschitz bound on the gradient:

That is the whole proof: one integral, one Cauchy–Schwarz, one Lipschitz bound. The load-bearing step is Cauchy–Schwarz combined with Lipschitz — without both, the quadratic bound would not close.

Step size 1/L is not a guess

Now plug in the gradient descent step $y = x - \eta \nabla f(x)$. Write $g = \nabla f(x)$ for brevity:

This right-hand side is minimized in $\eta$ at $\eta = 1/L$, and the guaranteed per-step decrease is

That is the "sufficient decrease" inequality. Every convergence proof for gradient descent begins here. And notice what the algebra tells you at the boundary: the coefficient $1 - L\eta/2$ turns negative when $\eta > 2/L$. Past $2/L$, the descent lemma no longer guarantees any decrease — you are stepping past the peak of the quadratic upper bound. On the pure quadratic $f(x) = \tfrac{L}{2} x^2$ with $\eta = 2.2/L$, iterates satisfy $x_{k+1} = (1 - \eta L) x_k = -1.2 \, x_k$, and diverge geometrically. When $L$ is not known a priori, backtracking (Armijo) line search estimates it adaptively — shrink the trial step until the sufficient-decrease inequality holds, which implicitly discovers a usable local $L$.

Convexity buys you a rate

Sufficient decrease alone tells you the gradient shrinks: assuming $f$ is bounded below, summing the inequality over $k$ steps gives $\sum_k \|\nabla f(x_k)\|^2 < \infty$, so $\|\nabla f(x_k)\| \to 0$. But small gradient does not mean small objective gap — on a saddle or a long plateau, $\|\nabla f\|$ can be tiny without you being anywhere near a minimum.

Convexity closes that gap. If $f$ is convex,

where $f^* = f(x^*)$ is the minimum. A careful telescoping argument (see any standard convex-optimization text) turns per-step decrease into

the celebrated $O(1/k)$ sublinear rate. In words: after $k$ steps, the guaranteed bound on the objective gap decays like $1/k$. This is order-optimal — there exist convex, L-smooth functions on which no better rate is possible from vanilla gradient descent. The constant is not sharp, though: the exact performance-estimation (PEP) bound for step $1/L$ is roughly $L\|x_0 - x^*\|^2/(4k+2)$, so the $1/(2k)$ constant above is loose by a factor of about $2$.

Strong convexity buys you linear rates

Add one more ingredient. Call $f$ $\mu$-strongly convex if

So $f$ sits above a paraboloid of curvature $\mu$. Combined with L-smoothness, $f$ is now sandwiched between two quadratics — curvature $\mu$ from below and curvature $L$ from above.

The ratio $\kappa = L/\mu \ge 1$ is the condition number. Well-conditioned means $\kappa$ close to $1$ (nearly a perfect bowl); ill-conditioned means $\kappa$ huge (a long, thin valley). Gradient descent with step size $1/L$ satisfies

so after $k$ steps the gap is bounded by $\left(1 - 1/\kappa\right)^k (f(x_0) - f^*) \approx e^{-k/\kappa}(f(x_0) - f^*)$. To reach accuracy $\varepsilon$ you need $O(\kappa \log(1/\varepsilon))$ iterations. Linear in $\log$-accuracy is wonderful; linear in $\kappa$ is the price of ill-conditioning — and it is the reason ML practitioners obsess over preconditioning, normalization, and adaptive step sizes.

When strong convexity fails: Polyak–Łojasiewicz

Strong convexity is a strong assumption. Overparameterized neural networks, kernel ridge regression at interpolation, and countless practical problems fail it: the loss has flat directions where $\mu = 0$. A weaker but often-sufficient condition is the Polyak–Łojasiewicz (PL) inequality:

In plain terms: whenever you are not at the minimum, the gradient is big enough — its squared norm is proportional to how far above the minimum you sit. This does not require convexity; it merely requires that the gradient reveal the height. Under PL and L-smoothness, gradient descent with step size $1/L$ enjoys the same $(1 - \mu/L)^k$ linear rate as under strong convexity. Karimi, Nutini, and Schmidt (2016) collected these results in an influential paper, and Liu, Zhu, and Belkin (2020) showed PL holds locally around minima for sufficiently wide neural networks — one clean explanation of why gradient descent trains deep models despite gross non-convexity.

Where gradient descent honestly fails

Three canonical failure modes, in order of how much they damage the story.

1. Non-smooth objectives. If $f$ has a kink — think $f(x) = |x|$, hinge loss, or a ReLU-based composite — the descent lemma does not apply because there is no gradient at the kink. Subgradient methods work but achieve only $O(1/\sqrt{k})$ rates, and step sizes must shrink like $1/\sqrt{k}$ to converge. This is not a proof gap: Nemirovski–Yudin lower bounds (1983) show $O(1/\sqrt{k})$ is optimal for non-smooth Lipschitz-convex problems queried through subgradients.

2. Non-convex landscapes with saddles. In high dimensions, generic stationary points of non-convex functions are saddles, not local minima (Dauphin et al., 2014). Plain gradient descent converges to some stationary point but can take exponential time to escape a saddle in the worst case. Ge, Huang, Jin, and Yuan (2015) and Jin, Ge, Netrapalli, Kakade, and Jordan (2017) showed that perturbed gradient descent — inject a small isotropic noise burst when the gradient is small — escapes strict saddles in a number of iterations only polylogarithmic in dimension. The noise breaks the symmetry that would otherwise trap you. This is one reason SGD often outperforms full-batch GD on deep non-convex problems.

3. Stochastic gradients. SGD uses a noisy estimate $\tilde g_k$ of the true gradient. The descent lemma in expectation gains a variance term:

where $\sigma^2$ bounds the gradient-estimator variance. The variance term does not vanish as $\|\nabla f\| \to 0$, so a constant step size cannot drive $\mathbb{E}[f(x_k)] - f^*$ to zero — the iterates hover in a noise ball. You either shrink the step size on a schedule (recovering $O(1/\sqrt{k})$ convergence) or use variance-reduction tricks such as SVRG (Johnson and Zhang, 2013) to restore linear rates in the convex case.

Acceleration and its ceiling

Can we do better than $O(1/k)$ on convex L-smooth problems? Yes. Momentum has a long lineage — Polyak's heavy-ball method (1964) is the canonical precursor, adding an inertia term that speeds convergence but does not provably attain the optimal rate on general L-smooth convex problems. Nesterov's accelerated gradient method (1983) uses a momentum-like second sequence to achieve

an $O(1/k^2)$ rate that provably saturates the first-order lower bound. On strongly convex problems, acceleration reduces the condition-number dependence from $\kappa$ to $\sqrt{\kappa}$ — roughly, the difference between "hours" and "minutes" when $\kappa = 10^4$. And these rates are optimal in a precise sense: Nemirovski and Yudin (1983) proved lower bounds showing no first-order method — no algorithm that only queries $\nabla f$ at chosen points — can beat them in the worst case over L-smooth convex functions, provided the iteration count stays below roughly half the dimension. (Once $k$ reaches the dimension, methods like conjugate gradient exploit the finite-dimensional structure and do better.) Momentum is not a heuristic; it saturates a theoretical ceiling.

What to take away

Gradient descent works exactly when the descent lemma has bite: when the gradient is Lipschitz, when your step size respects that Lipschitz constant, and when the geometry (convexity, strong convexity, or PL) turns per-step decrease into a rate. It fails at kinks, at saddles, and under noise — but at each of those failure modes, there is an honest fix: subgradients for non-smoothness, perturbations for saddles, variance reduction for stochasticity. The descent lemma is not merely the first lemma in the theory; it is the theory. Everything else is bookkeeping around one integral, one Cauchy–Schwarz, one Lipschitz bound.