When Gradient Descent Works, and When It Quietly Doesn't

A careful tour of the oldest optimization algorithm still in daily use — Cauchy introduced it in 1847 — : what it actually is, the two-line proof that it works on convex smooth problems, the sharp reasons it can fail elsewhere, and the modern conditions (Polyak-Łojasiewicz, overparameterization) that explain why we get away with it on neural networks anyway.

The one-line story

Gradient descent picks a direction and steps that way. The direction is the one in which the function looks steepest downhill at the point you're standing. Repeat.

That is genuinely all it is. Every subtlety — step size, momentum, adaptivity, all the training curves you've stared at — is downstream of that sentence.

The formalism. We want to minimize a differentiable function $f: \mathbb{R}^d \to \mathbb{R}$. Here $d$ is the dimension of the parameter space (weights of a network, say), and $\nabla f(x)$ is the gradient at point $x$ — the vector of partial derivatives, whose length tells you how fast $f$ is changing and whose direction points uphill. Given a starting point $x_0$ and a step size $\eta > 0$ (a positive real number, sometimes called the learning rate), the iteration is:

In words: at every step, look at the local uphill direction, turn around, and walk $\eta$-many units of that vector. The whole story of when gradient descent works is a story about matching $\eta$ to the local geometry of $f$.

The descent lemma, doing the actual work

Everything provable about vanilla gradient descent hangs on one inequality. Call it the descent lemma. It assumes $f$ is $L$-smooth, meaning its gradient doesn't change too fast:

Here $L$ is a positive constant — the Lipschitz constant of the gradient. Larger $L$ means the surface curves more sharply. For a quadratic $f(x) = \tfrac{1}{2} x^\top A x$, $L$ is the largest eigenvalue of $A$.

The descent lemma says: if $f$ is $L$-smooth, then for any two points $x, y$,

Read aloud: the function $f$ never sits above its own tangent plane by more than a quadratic bump of curvature $L$. That is a universal upper bound — a parabola we can always trust to be above the true landscape locally.

Plug in $y = x - \eta \nabla f(x)$, which is exactly one gradient step. The inner product collapses to $-\eta \|\nabla f(x)\|^2$, and the quadratic term is $\tfrac{L \eta^2}{2} \|\nabla f(x)\|^2$. So:

Read aloud: as long as we choose $\eta \le 2/L$, the parenthesis is nonnegative, and the function value strictly decreases whenever the gradient is nonzero. The maximum guaranteed drop happens at $\eta = 1/L$, giving:

That single inequality is the engine. Every quantitative guarantee below is squeezing it in a different way.

The convex, smooth case: where the theory is clean

Now assume additionally that $f$ is convex — every chord lies above the graph, equivalently $f(y) \ge f(x) + \langle \nabla f(x), y - x \rangle$ for all $x, y$. Combine convexity with the descent lemma, sum the resulting telescoping inequality over $k$ steps, and after a few lines of algebra (the load-bearing step is the identity $\|x_{k+1} - x^\star\|^2 = \|x_k - x^\star\|^2 - 2\eta \langle \nabla f(x_k), x_k - x^\star\rangle + \eta^2 \|\nabla f(x_k)\|^2$), you get:

Here $x^\star$ is any minimizer and $k$ is the number of iterations. In words: after $k$ steps, we're within $O(1/k)$ of the optimum. To get within $\varepsilon$, budget $O(1/\varepsilon)$ steps. This is the standard textbook $O(1/k)$ bound for gradient descent on $L$-smooth convex functions, and it is tight for the plain GD iteration — you cannot squeeze a better rate out of that exact update. The first-order lower bound, however, is $\Omega(1/k^2)$: no method that only queries gradients can beat $O(1/k^2)$, and that faster rate is attainable.

The way to attain it is Nesterov's accelerated gradient (1983), which mixes each step with momentum from the previous one and achieves $O(1/k^2)$ on the same class. That improvement is provable, sharp against the matching $\Omega(1/k^2)$ lower bound, and one of the crown jewels of the field.

If $f$ is additionally $\mu$-strongly convex — meaning it curves upward at least as fast as $\tfrac{\mu}{2}\|x\|^2$ from any point — then gradient descent with $\eta = 1/L$ contracts geometrically:

The ratio $\kappa = L/\mu$ is the condition number. Every $\kappa$ steps shrink the error by a constant factor (~1/e); halving it takes about $0.7\kappa$ steps. In words: gradient descent works, but its speed is set entirely by how eccentric the level sets are. Long, thin valleys are its enemy.

Where it breaks

Too big a step. If $\eta > 2/L$, the descent lemma's guarantee flips sign and we can climb. On a scalar quadratic $f(x) = \tfrac{L}{2} x^2$, one gradient step gives $x_{k+1} = (1 - \eta L) x_k$. If $\eta L > 2$, the multiplier has magnitude greater than 1 and iterates diverge geometrically. This is the boring failure mode, but the one everyone experiences first.

Non-smooth kinks. Consider $f(x) = |x|$. There is no gradient at $x=0$; there is a whole subdifferential, the interval $[-1, 1]$. Vanilla gradient descent with fixed step will bounce forever across the kink, never landing. The fix — subgradient methods with a shrinking step size $\eta_k = 1/\sqrt{k}$ — gets you $O(1/\sqrt{k})$ convergence, worse than smooth, and this is provably optimal for nonsmooth convex problems (the Nemirovski-Yudin lower bound from Problem Complexity and Method Efficiency in Optimization, 1983).

Nonconvexity: saddle points and local minima. In the nonconvex world, "gradient equals zero" no longer means "minimum". It can mean local minimum, saddle, or maximum. The descent lemma still guarantees $f$ decreases, but it can only promise convergence to a stationary point — some $x$ with $\nabla f(x) = 0$. Whether that stationary point is any good is a separate question, and in general undecidable.

For nonconvex $L$-smooth $f$, the sharp guarantee is:

where $f^\star = f(x^\star)$ is the optimal value. In words: within $K$ steps, at least one iterate has small gradient — but "small gradient" is not "small loss". You could be sitting at a saddle. The good news: gradient descent from a random start almost surely does not converge to strict saddles (Lee, Simchowitz, Jordan, Recht, 2016), because the saddle's stable manifold has measure zero in initialization space. The bad news: "almost surely converges away from saddles" says nothing about how fast, and constructing pathological landscapes where GD spends exponential time near saddles is not hard (Du et al. 2017 gave explicit constructions).

A saddle, and why zero gradient is not enough

At $(0, 0)$ the gradient of $f(x, y) = x^2 - y^2$ is zero, so gradient descent declares victory. But we're at a saddle, not a minimum. The Hessian $\text{diag}(2, -2)$ has eigenvalues $+2$ and $-2$; the negative eigenvalue points to a direction of further decrease that first-order gradient descent cannot see. Second-order methods (or the noise in stochastic gradient descent) escape. Plain deterministic GD, initialized on the exact $y=0$ axis, sits there forever.

Why does it work on neural networks?

Deep learning loss surfaces are wildly nonconvex, high-dimensional, and full of saddles. By the previous section, gradient descent has no business converging to anything useful. And yet it does, routinely, on models with hundreds of billions of parameters. What's going on?

Two answers, both well-supported, neither complete.

Polyak-Łojasiewicz (PL) inequality. A function $f$ satisfies PL with constant $\mu > 0$ if:

In words: the squared gradient at any point is at least proportional to how far you are from the optimum. PL is strictly weaker than strong convexity — nonconvex functions can satisfy it — but it's just as good for convergence. Combine PL with the descent lemma and:

geometric convergence in loss, on a nonconvex function, with a two-line proof. And modern overparameterized networks provably satisfy PL locally around initialization (see the neural tangent kernel line of work, e.g. Du, Zhai, Poczos, Singh 2018; Liu, Zhu, Belkin 2022 for the general "PL near interpolation" story). The catch: the "local" is a ball whose radius depends on width, and the constants are terrible.

Overparameterization. When there are more parameters than data points, the loss landscape develops connected manifolds of global minima. Gradient descent, from most initializations, slides toward one of them along a nearly-monotone trajectory. There are no meaningful "bad local minima" to get stuck in because there is essentially one basin at the scales that matter.

Both stories are partial. Neither explains generalization. Both are active research; both have specific proved theorems attached; neither justifies the confident sentence "gradient descent works on neural networks" as a general theorem.

A working recipe

Distill the theory into three rules:

1. Scale the step to the local curvature. If you know $L$, use $\eta = 1/L$. If you don't, backtracking line search (halve $\eta$ until the descent lemma numerically holds) is a two-line safety net.
2. Momentum is almost free. Nesterov acceleration provably improves the rate on convex problems and empirically helps nonconvex ones. Adam and its cousins are messier to analyze but robust across scales.
3. Watch the gradient norm, not just the loss. A flat loss curve with small gradient means "converged to something stationary". A flat loss with large gradient means "step size too small" or "training instability". They demand opposite fixes.

Here is the entire algorithm, with backtracking that removes the need to know $L$ in advance:

def gradient_descent(f, grad_f, x0, eta0=1.0, beta=0.5, tol=1e-6, max_iter=10000):
    x, eta = x0.copy(), eta0
    for k in range(max_iter):
        g = grad_f(x)
        if (g @ g) ** 0.5 < tol:
            return x, k
        # backtracking: shrink eta until the descent lemma holds numerically
        while f(x - eta * g) > f(x) - 0.5 * eta * (g @ g):
            eta *= beta
        x = x - eta * g
        eta = min(eta / beta, eta0)  # grow again, cautiously
    return x, max_iter

That's it. Everything else — Adam, LAMB, Shampoo, K-FAC, sharpness-aware minimization — is a variation on "pick a better direction than $-\nabla f$" or "pick a better step size than $1/L$".

What is proved, what is open

Proved and tight: $O(1/k)$ for convex $L$-smooth, $O((1-\mu/L)^k)$ for strongly convex $L$-smooth, $O(1/k^2)$ for Nesterov-accelerated on the same class, and matching lower bounds for gradient-only methods. Proved but constants matter: PL-based geometric convergence for overparameterized networks near a good initialization. Sketched by experiment, not proved in generality: gradient descent finds good minima on real deep networks. Open beyond specific settings: quantitative saddle-escape rates for deterministic GD in high dimensions, and any clean theory of why the minimum SGD finds also generalizes.

Gradient descent works when the geometry cooperates and you match your step to it. It quietly doesn't when the landscape has kinks, cliffs, saddles, or long thin valleys — and it works anyway, unreasonably well, on the class of problems we most care about, for reasons we still only half understand.