Nesterov acceleration
/ nyeh-STEH-roff /
A heavy ball rolling down a valley does not stop and re-decide at every point — its momentum carries it forward, smoothing out the small zig-zags and letting it pick up speed along the valley floor. Adding momentum to gradient descent borrows this intuition. Nesterov acceleration is a cleverer momentum: before measuring the slope, it first LOOKS AHEAD to where momentum is about to carry it, and computes the gradient there — like a skier who leans into the turn she sees coming rather than the one she is in.
Plain heavy-ball momentum keeps a velocity v and updates v_{k+1} = mu * v_k - alpha * grad f(x_k), then x_{k+1} = x_k + v_{k+1}, where mu (around 0.9) is the momentum coefficient. Nesterov's twist is to evaluate the gradient at the LOOK-AHEAD point x_k + mu * v_k (where momentum is already taking you) rather than at x_k: v_{k+1} = mu * v_k - alpha * grad f(x_k + mu * v_k), then x_{k+1} = x_k + v_{k+1}. That tiny change — a peek at the future position — lets the method correct its course sooner and damps overshooting. The payoff is dramatic on smooth convex problems: gradient descent converges at rate O(1/k), but Nesterov's accelerated gradient achieves O(1/k^2) — provably the best possible rate for first-order methods on this class (it matches a theoretical lower bound).
Acceleration matters because it speeds convergence essentially for free — the same gradients, almost the same cost per step, but a fundamentally faster RATE — and the momentum idea is built into nearly every deep-learning optimizer (SGD-with-momentum and Adam both carry a velocity term). The honest caveats: the clean O(1/k^2) guarantee is for the smooth, deterministic, convex setting; with stochastic mini-batch gradients the gradient noise muddies the look-ahead and the theoretical advantage erodes, though momentum still helps in practice. And acceleration can OVERSHOOT and oscillate on its way down (the heavy ball rolls past the bottom and back) — a feature that smooths progress but can look non-monotone, which is normal, not a bug.
On a smooth convex problem where plain gradient descent needs about 10,000 steps to reach a target accuracy, Nesterov's accelerated gradient reaches it in roughly 100 — because the error shrinks like 1/k^2 instead of 1/k, so to gain 100x accuracy you need only 10x more steps, not 100x.
Look ahead where momentum points, then correct — O(1/k^2) instead of O(1/k).
The optimal O(1/k^2) rate is a smooth-convex-DETERMINISTIC result; mini-batch gradient noise blurs the look-ahead and erodes the guarantee, though momentum still helps empirically. Accelerated methods can also overshoot and oscillate (a non-monotone descent), which is expected behaviour rather than a malfunction.