Plain gradient descent crawls at O(1/k). Add a look-ahead — take the gradient not where you are but where momentum is about to carry you — and the error collapses at O(1/k²). On the constructed quadratic below, that is 87 steps to a tolerance plain descent needs 1091 for. And it is not just fast: it is provably the fastest a first-order method can be — it touches the theoretical floor. The blue team builds and witnesses it live; the red team pulls the look-ahead out and watches the acceleration die.
source Yu. Nesterov, A method for solving the convex programming problem with convergence rate O(1/k²), Soviet Math. Dokl. 27(2), 372–376 (1983) — no stable open link (AMBER). Constant-step realization & the 2L·R²/(k+1)² bound: Beck & Teboulle, FISTA, SIAM J. Imaging Sci. 2(1) 183–202 (2009). Rendered, not quoted.
Three lines. On an L-smooth convex f, with step 1/L and the momentum sequence tk+1=(1+√(1+4tk²))/2:
yk = xk + βk(xk−xk−1) ← look ahead
xk+1 = yk − (1/L)∇f(yk) ← gradient at the look-ahead
The single idea: ∇f is sampled at y, not x. That one move buys the whole speed-up and its guarantee f(xk)−f* ≤ 2L·R²/(k+1)². Live on the current problem:
the-momentum gave gradient descent a memory — a heavy ball that rolls through small bumps. Nesterov keeps the ball but peeks forward before choosing its push.
That peek is not one optimizer among many: it hits the first-order lower bound Ω(1/k²) (Nesterov). No method that sees only gradients can beat it. Every accelerated optimizer after it — FISTA, Adam's momentum, the schedules in deep-net training — aims at this ceiling. Each sphere is the next one's premise.
The blue team's live check: re-simulate NAG and GD on the fixed problem and confirm — NAG stays under the 1/k² bound at every step, halves error ~¼ per doubling, and beats GD to tolerance. If red pulls the look-ahead, this badge is where it shows.
A constructed, strictly-convex quadratic with a closed-form answer — so every optimum and rate is checkable to 1e-9, no fitting:
f(x) = ½ Σi λi xi² , λi log-spaced in [μ, L] , L=1
minimizer x* = 0 , f* = 0 , x0 = (1,…,1), R² = ‖x0−x*‖²
| ingredient | role |
|---|---|
| L (smoothness) | sets the safe step 1/L |
| μ (curvature) | κ=L/μ sets how long the 1/k² regime lasts |
| x* = 0, f* = 0 | known — the gap f(xk)−f* is exact |
| βk = (tk−1)/tk+1 | the look-ahead weight |
Feed these to the engine below and watch two error curves race on a log axis.
Both curves are simulated live from the same x0 and step 1/L — the only difference is where the gradient is sampled. Nothing is looked up.
What the machine proves on the default problem (κ=10⁴), each number recomputed, not asserted from memory:
The blue witness (left) re-verifies these live; the red team (right) tries to make them false.
Sharper still: on a pure quadratic, plain heavy-ball momentum also accelerates — the look-ahead's necessity only bites on general convex f (see graveyard). This instrument uses a quadratic for exactness, so it demonstrates the ceiling by removing acceleration entirely, which is the honest, provable break.
"Acceleration beats the limit — free speed." Cut. It matches the Ω(1/k²) first-order lower bound; you cannot do better with gradients alone (Nesterov). Optimal, not miraculous.
"NAG is faster because it takes bigger steps." Cut. Same step 1/L as GD — the speed is entirely the look-ahead, not the step size. The engine holds the step fixed to prove it.
"Momentum always helps and always converges." Kept, corrected. Heavy-ball momentum can diverge on some convex functions (Lessard, Recht & Packard, 2016). NAG's look-ahead is the fix that keeps the guarantee.
The red team's move: pull out the look-ahead — sample ∇f at x instead of y, dropping the extrapolation. The method degenerates to plain gradient descent; the O(1/k²) acceleration is lost and the error falls back to O(1/k). The blue witness (window 7) is watching.
Remove the look-ahead and NAG's curve drops onto GD's, breaching the 1/k² bound the witness checks — it recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.