Nesterov Accelerated Gradient

Plain gradient steps where you stand; Nesterov steps where you are headed. That lookahead kills zigzags and squares the convergence speed.

Plain momentum zigzags six times across a stretched valley while Nesterov lookahead glides to the minimum in two arcs

Why Does This Exist?

Ill-conditioned valleys (condition number $10^3$ ) make gradient descent bounce wall to wall: each step overshoots across the narrow axis while crawling along the long one. Heavy-ball momentum helps but still evaluates gradients at stale positions and overshoots.

Nesterov fixes the staleness: step to the lookahead $y_k = x_k + \\beta_k(x_k - x_{k-1})$ , evaluate $\\nabla f(y_k)$ , then correct. Smooth convex rate jumps $O(1/k) \\to O(1/k^2)$ , optimal for first-order methods. It accelerates the descents in gradient descent variants toward the rates in convergence rates.

The one idea you need first

Momentum carries velocity $v_k = x_k - x_{k-1}$ . Heavy-ball steps $x_{k+1} = x_k - \\alpha\\nabla f(x_k) + \\beta v_k$ : gradient at the old spot plus inertia. Nesterov moves the gradient to the predicted spot.

Think of It Like This

Steering where the car will be

Heavy-ball steers from the rear-view mirror: gradient where you were, plus speed. Nesterov looks through the windshield at the predicted position and steers there.

On straight highways both work; in slaloms the mirror steers late and oscillates. Where it stops: lookahead assumes smooth roads. Potholes (nonsmooth kinks, stochastic noise) punish prediction and need smaller bets or proximal variants.

How It Actually Works

For $L$ -smooth convex $f$ : $y_k = x_k + \\frac{k-1}{k+2}(x_k - x_{k-1})$ , $x_{k+1} = y_k - \\frac{1}{L}\\nabla f(y_k)$ , giving $f(x_k) - f^\\star \\leq 2L\\|x_0-x^\\star\\|^2/(k+1)^2$ . Strongly convex variant restarts or fixes $\\beta = (\\sqrt{\\kappa}-1)/(\\sqrt{\\kappa}+1)$ for linear $1 - 1/\\sqrt{\\kappa}$ rate. Practical Nesterov (PyTorch NAG, AdamW+Nesterov) adapts the schedule; FISTA ports it to proximal $g$ (Lasso).

Worked example

Quadratic $f(x,y) = x^2 + 25y^2$ ( $\\kappa = 25$ ). Gradient descent with $\\alpha = 1/50$ : $x$ crawls ( $1 - 2/50 = 0.96$ per step, ~114 steps per digit) while $y$ bounces at the edge. Nesterov with $\\beta = 0.8$ : lookahead damps the $y$ overshoot first, then rides $x$ down, reaching $10^{-4}$ in about 30 steps versus 200+ plain. Two arcs replace six zigzags: the diagram's count is the mechanism, not decoration.

Code

1import numpy as np2
3def f_grad(p):4    return np.array([2 * p[0], 50 * p[1]])  # grad of x^2+25y^25
6x, v = np.array([5.0, 5.0]), np.zeros(2)7for k in range(1, 31):8    y = x + 0.8 * v  # lookahead9    x_new = y - (1 / 50) * f_grad(y)10    v, x = x_new - x, x_new11print(np.round(x, 3))  # -> ~[0. 0.]

Thirty lookahead steps park near zero where plain descent still bounces. The only change from heavy-ball is where the gradient is read.

Watch Out For

Running textbook schedule on noisy stochastic gradients

The $O(1/k^2)$ proof needs exact gradients; noisy SGD estimates make lookahead chase sampling noise and diverge at aggressive $\\beta$ . Loss explodes where deterministic Nesterov glides.

Dampen ( $\\beta \\leq 0.5$ ), grow batches, or use accelerated-variance-reduced variants. If Nesterov-SGD oscillates worse than SGD, noise is driving the wheel.

Skipping restarts on locally-strong bowls

Global $O(1/k^2)$ with local strong convexity wastes speed: scheduled Nesterov overshoots near the bottom and ripples. Gradient restarts (reset momentum when $\\nabla f \\cdot v > 0$ ) recover linear tail speed.

Restart adaptively. If the loss sawtooths late, momentum is stale, not small.

The Quick Version

Nesterov reads the gradient at the lookahead, not the position.
Smooth convex jumps $O(1/k)$ to $O(1/k^2)$ , optimal for first-order oracles.
Example $x^2+25y^2$ : ~30 steps versus 200+ plain.
Heavy-ball carries the past; Nesterov aims the gradient at the future.
FISTA extends it to proximal nonsmooth splits.
Dampen or restart under noise and local strong convexity.