Gradient descent

Gradient descent is three lines of code and a lifetime of behaviour. This lesson does what most treatments skip: it solves the algorithm’s dynamics exactly on the one problem where that is possible — the quadratic — and shows that everything you observe on real losses (divergence past a learning-rate threshold, zig-zagging across ravines, the slow crawl along flat directions) is already present, and provable, there.

The update, and where it comes from

Around the current iterate $x_t$, first-order Taylor says $f(x_t + \delta) \approx f(x_t) + \nabla f(x_t)^\top \delta$. Among all steps of a fixed small length, the one that decreases this linear model fastest is $\delta \propto -\nabla f(x_t)$: the negative gradient is the direction of steepest descent. Committing to it with a step size (learning rate) $\eta$:

For an $L$-smooth function, the smoothness upper bound from the previous lesson turns this from a heuristic into a guarantee. Plugging the step into the quadratic upper bound gives the descent lemma:

which is strictly decreasing whenever $0 < \eta < 2/L$. There is the learning-rate ceiling, derived rather than tuned: step sizes are bounded by the sharpest curvature of the loss.

def gradient_descent(grad, x0, lr, steps):
    x = x0.copy()
    for _ in range(steps):
        x -= lr * grad(x)        # the entire algorithm
    return x

Exact dynamics on a quadratic

Take $f(x) = \tfrac{1}{2} x^\top H x$ with symmetric $H \succ 0$ (any smooth loss looks like this near a minimum — this is not a toy, it is the local model of every basin). The gradient is $Hx$, so the update is linear:

Diagonalize $H = Q \Lambda Q^\top$ and write the error in the eigenbasis, $z_t = Q^\top x_t$. The coordinates decouple — each curvature direction evolves independently:

Every question about gradient descent on this problem reduces to the scalar factor $\lvert 1 - \eta\lambda_i \rvert$:

• Convergence requires $\lvert 1 - \eta\lambda_i\rvert < 1$ for all $i$, i.e. $\eta < 2/\lambda_{\max}$. Exceed it and the stiffest direction oscillates with growing amplitude — the characteristic explode-in-one-axis divergence you can reproduce in the figure below.
• Speed is set by the slowest factor. With $\lambda$ ranging over $[\mu, L]$, the best constant step balances the two extremes:

For $\kappa = 100$ the rate is $0.98$: each iteration removes 2% of the remaining error, and you need roughly $\kappa \ln(1/\varepsilon)$ iterations — iteration count scales linearly with the condition number. That sentence is why feature standardization, batch normalization and second-order-ish methods exist.

The zig-zag, explained. In a ravine ($\kappa \gg 1$), any $\eta$ large enough to make progress along the flat direction is close to the stability limit of the steep one, so the steep coordinate’s factor $1 - \eta L$ is close to $-1$: it overshoots and flips sign every step. The trajectory bounces wall-to-wall across the ravine while creeping along it. You are watching the two eigenvalues disagree about the learning rate.

Three experiments worth actually doing before reading on:

1. Find the cliff. Quadratic, $\kappa = 10$. The theory says stability ends at $\eta = 2/L = 0.2$ (here $L = \kappa$ after scaling: watch for the readout’s DIVERGED). Sweep $\eta$ and locate the cliff — it is sharp, not gradual.
2. Feel the κ tax. Fix $\eta$ slightly below the cliff and raise $\kappa$ from 1 to 60. The loss line on the sparkline tilts toward horizontal: same algorithm, same code, 60× the iterations.
3. Meet your first local minimum. Switch to the two-wells surface and drag the start around $x \approx 0.04$ (the saddle). A few pixels left: the deep well. A few pixels right: the shallow one, and the loss curve flatlines at a higher value — gradient descent has converged, and it is not the answer. Which minimum you get is a property of the initialization, not the optimizer.

Beyond quadratics: what survives

On a general convex, $L$-smooth $f$ with $\eta = 1/L$, telescoping the descent lemma against the first-order convexity bound yields

and with $\mu$-strong convexity the geometric rate returns: $\lVert x_t - x^\star \rVert^2 \le \big(1 - \tfrac{\mu}{L}\big)^t \lVert x_0 - x^\star \rVert^2$. The quadratic analysis was not a special case after all — near any strict minimum it is the general case, with $H = \nabla^2 f(x^\star)$.

On non-convex $f$, the descent lemma still guarantees $\min_{s \le t} \lVert \nabla f(x_s) \rVert^2 \le \frac{2L\,(f(x_0) - f^\star)}{t}$ — you always find an (approximately) stationary point. What kind of stationary point, the lemma cannot say; that question owns the non-convex landscapes lesson.

Exercises