Optimization

Nesterov Accelerated Gradient

A momentum variant that evaluates the gradient at a look-ahead point, achieving the optimal first-order convergence rate for smooth convex problems.

Look before you leap

Standard momentum computes the gradient at the current point, then adds momentum. Nesterov accelerated gradient (NAG) first takes the momentum step to a look-ahead point, then computes the gradient there. This anticipatory correction reacts to upcoming curvature and reduces overshoot.

The update

Kronos motion — materials first

One common form: x_look = x_k + b * v_k; v_{k+1} = b * v_k - a * grad f(x_look); x_{k+1} = x_k + v_{k+1}. The gradient is evaluated at the look-ahead x_look rather than at x_k. When the velocity is about to carry the iterate past the minimum, the gradient at the look-ahead point pushes back sooner.

Optimal convergence

For smooth convex functions, NAG achieves an error that decreases as O(1/k^2) after k steps, compared with O(1/k) for plain gradient descent. This matches the lower bound for first-order methods that only use gradient information, so NAG is optimal in that class. For strongly convex problems it attains the sqrt(kappa) accelerated rate.

Interpretation

The look-ahead acts as a cheap correction to the momentum direction.
Nesterov's estimate-sequence analysis proves the accelerated rate rigorously.
In practice NAG is often marginally better than heavy-ball momentum and rarely worse.

Relation to modern optimizers

Nadam combines Nesterov look-ahead with Adam-style adaptive scaling. Accelerated proximal-gradient methods (FISTA) extend the same idea to composite objectives with a non-smooth regularizer, keeping the O(1/k^2) rate.

python

v = 0
for _ in range(iters):
    look = x + beta*v
    v = beta*v - lr*grad(look)
    x = x + v

Accelerated first-order methods are attractive when each gradient is expensive, as in simulation-driven optimization where every evaluation runs a physics solver.