Nesterov accelerated gradient (NAG)

Momentum that takes the gradient at the look-ahead point θ + βv instead of at θ, so it brakes before overshooting. On smooth convex problems it reaches the optimal O(1/k²) rate; in PyTorch it is SGD(..., nesterov=True).

11 min read1130 wordsadvanced0 viewsupdated 2026-10-11

Definition

Nesterov accelerated gradient (NAG, Nesterov momentum) is momentum with one change: the gradient is evaluated at the point the velocity is about to carry you to, θt+βvt\theta_t+\beta v_t, rather than at the current point θt\theta_t. In the classical form, vt+1=βvt−η∇f(θt+βvt)v_{t+1}=\beta v_t-\eta\nabla f(\theta_t+\beta v_t) and θt+1=θt+vt+1\theta_{t+1}=\theta_t+v_{t+1}.

Heavy-ball momentum decides its next step from where it is, then adds the stored velocity. If the velocity is about to carry it over the valley floor, it finds out only one step later, after it has overshot. Nesterov's version first makes the momentum jump, looks at the gradient there, and corrects. When the jump would overshoot, the look-ahead gradient already points back, so the correction brakes the step before the damage is done.

Yurii Nesterov introduced the method in "A method for solving the convex programming problem with convergence rate O(1/k2)O(1/k^2)" (Soviet Mathematics Doklady, 1983). It was a result about worst-case complexity: for any convex function with an LL-Lipschitz gradient, gradient descent's error falls like 1/k1/k, and Nesterov's scheme achieves 1/k21/k^2, which matches the lower bound for methods that only use gradients. Deep learning adopted it three decades later. Bengio, Boulanger-Lewandowski and Pascanu (2012) rewrote it in the form that frameworks implement, and Sutskever, Martens, Dahl and Hinton ("On the importance of initialization and momentum in deep learning", ICML 2013) presented it as a small change to classical momentum and found it more stable at high momentum, especially for recurrent networks.

The update rule

vt+1=βvt−η ∇f(θt)⏟heavy ballvt+1=βvt−η ∇f(θt+βvt)⏟Nesterovθt+1=θt+vt+1\underbrace{v_{t+1}=\beta v_t-\eta\,\nabla f(\theta_t)}_{\text{heavy ball}}\qquad\qquad \underbrace{v_{t+1}=\beta v_t-\eta\,\nabla f(\theta_t+\beta v_t)}_{\text{Nesterov}}\qquad\qquad \theta_{t+1}=\theta_t+v_{t+1}
vtv_t
velocity in parameter units (the classical form), v0=0v_0=0
θt+βvt\theta_t+\beta v_t
the look-ahead point: where momentum alone would take you
β\beta
momentum coefficient, typically 0.90.9 to 0.990.99
η\eta
learning rate

Split the Nesterov step in two: a jump βvt\beta v_t to the look-ahead point, then an ordinary gradient step from there, −η∇f(θt+βvt)-\eta\nabla f(\theta_t+\beta v_t). Heavy ball makes the same jump but adds the gradient from the old point. The difference is a gradient correction: on a quadratic with Hessian HH, ∇f(θ+βv)−∇f(θ)=βHv\nabla f(\theta+\beta v)-\nabla f(\theta)=\beta Hv. In directions of high curvature the correction is large and opposes the velocity; in flat directions it is negligible.

At a glance

Extra cost over momentum
none: one gradient per step, one velocity tensor
Convex, L-smooth
f(xk)−f⋆≤2L ∥x0−x⋆∥2(k+1)2f(x_k)-f^\star\le\dfrac{2L\,\lVert x_0-x^\star\rVert^2}{(k+1)^2} (Beck and Teboulle's bound for the form below), versus L ∥x0−x⋆∥22k\dfrac{L\,\lVert x_0-x^\star\rVert^2}{2k} for gradient descent with step 1/L1/L
Strongly convex
error shrinks by about 1−1/κ1-1/\sqrt\kappa per step with η=1/L\eta=1/L, β=κ−1κ+1\beta=\frac{\sqrt\kappa-1}{\sqrt\kappa+1}; GD's 1−1/κ1-1/\kappa
Stability on a quadratic
ηλmax⁡<2(1+β)1+2β\eta\lambda_{\max}<\dfrac{2(1+\beta)}{1+2\beta} (1.361.36 at β=0.9\beta=0.9), much tighter than heavy ball's 2(1+β)2(1+\beta)
PyTorch
torch.optim.SGD(params, lr, momentum=0.9, nesterov=True) (dampening must be 0)
Adam variant
NAdam (Dozat, 2016): torch.optim.NAdam
f = ½(x² + 25y²), curvatures 1 and 25startminloss (log) vs step1e-81e-41060120step
t = 1|
Nesterov at t=1: θ = (−3.88, 0.40) → look-ahead θ+βv = (−3.77, −0.68); ∇f there = (−3.77, −17.00) vs ∇f(θ) = (−3.88, 10.00)
Stable for η < 0.1520 (heavy ball) and η < 0.0543 (Nesterov). Dashed violet: momentum jump; solid arrow: Nesterov's gradient at the look-ahead; dashed orange: the gradient heavy ball would use instead. Click a method to hide it.
fig.Nesterov (violet), heavy-ball momentum (orange) and plain GD (grey) on f = ½(x² + 25y²), all with η = 0.03, β = 0.9. The arrows split the current Nesterov step: dashed violet is the momentum jump to the look-ahead point, the solid arrow is the gradient step taken there, and the dashed orange arrow is the gradient step heavy ball would take instead. At t = 1 the look-ahead is (−3.77, −0.68), already past the floor, so its y-gradient is −17 instead of +10 and the step brakes. After 120 steps the losses are 5.4e-3 (GD), 6.0e-5 (heavy ball) and 3.8e-7 (Nesterov); the per-step rates are 0.970, 0.949 and 0.934. Set β = 0.95, η = 0.02: heavy ball stalls at 0.076, Nesterov reaches 6.6e-4. Push η past 0.054 and Nesterov diverges while heavy ball survives up to 0.152.

Why looking ahead damps oscillation

Restrict to one eigendirection of a quadratic, with curvature λ\lambda and a=ηλa=\eta\lambda. Writing θt+1\theta_{t+1} in terms of the two previous iterates gives two linear recurrences that differ in one factor:

HB:    θt+1=(1+β−a) θt−β θt−1NAG:    θt+1=(1−a)[(1+β) θt−β θt−1]\text{HB:}\;\;\theta_{t+1}=(1+\beta-a)\,\theta_t-\beta\,\theta_{t-1}\qquad\qquad \text{NAG:}\;\;\theta_{t+1}=(1-a)\big[(1+\beta)\,\theta_t-\beta\,\theta_{t-1}\big]
a=ηλa=\eta\lambda
step size measured in units of the local curvature
(1−a)(1-a)
NAG applies the gradient step to the extrapolated point (1+β)θt−βθt−1(1+\beta)\theta_t-\beta\theta_{t-1}, so the extrapolation itself gets shrunk

In heavy ball, the product of the two roots of the characteristic polynomial is β\beta whatever η\eta is, so the slowest mode can never contract faster than β\sqrt\beta per step: 0.949 at β=0.9\beta=0.9. In NAG the product is β(1−a)\beta(1-a), which shrinks in the high-curvature directions. Those directions are where oscillation lives, so they get damped more. The flat directions, with a≈0a\approx0, see the same acceleration as heavy ball.

The same factor (1−a)(1-a) explains the price. When a>1a>1 it is negative and amplifies the extrapolation, so NAG becomes unstable at a=2(1+β)/(1+2β)a=2(1+\beta)/(1+2\beta): 1.361.36 at β=0.9\beta=0.9, against 3.83.8 for heavy ball. On the figure's valley (λmax⁡=25\lambda_{\max}=25) that is η<0.054\eta<0.054 versus η<0.152\eta<0.152. Nesterov is the more stable choice at high β\beta and moderate η\eta, not at large η\eta.

The convex-optimization result

For a convex ff with LL-Lipschitz gradient, Nesterov's scheme uses a step 1/L1/L and a momentum coefficient that grows toward 1. One common form, with the simple schedule analysed by Su, Boyd and Candès (2014) in place of the original sequence used by Nesterov and by Beck and Teboulle's FISTA (2009), is:

yk=xk+k−1k+2 (xk−xk−1),xk+1=yk−1L ∇f(yk)⟹f(xk)−f⋆=O ⁣(L∥x0−x⋆∥2k2)y_k=x_k+\frac{k-1}{k+2}\,(x_k-x_{k-1}),\qquad x_{k+1}=y_k-\frac1L\,\nabla f(y_k)\qquad\Longrightarrow\qquad f(x_k)-f^\star=O\!\left(\frac{L\lVert x_0-x^\star\rVert^2}{k^2}\right)
yky_k
the look-ahead point: extrapolate along the last step, then take the gradient there
k−1k+2\tfrac{k-1}{k+2}
momentum schedule 0,14,25,12,⋯→10,\tfrac14,\tfrac25,\tfrac12,\dots\to1; no tuning of β\beta is needed
O(1/k2)O(1/k^2)
to reach error ε\varepsilon takes O(1/ε)O(1/\sqrt\varepsilon) steps instead of GD's O(1/ε)O(1/\varepsilon)

Nesterov also proved that no method which forms each iterate from a linear combination of past gradients can beat 1/k21/k^2 on this class in the worst case, so the rate is optimal. For μ\mu-strongly convex functions, a constant β=κ−1κ+1\beta=\frac{\sqrt\kappa-1}{\sqrt\kappa+1} with η=1/L\eta=1/L gives linear convergence at about 1−1/κ1-1/\sqrt\kappa per step. The figure's "η = 1/L" button applies exactly that: η=0.04\eta=0.04, β=0.667\beta=0.667, and the per-step rate reads 0.800, which is 1−1/251-1/\sqrt{25}.

Worked example: one look-ahead

The figure's setup: f=12(x2+25y2)f=\tfrac12(x^2+25y^2), θ0=(−4, 1.6)\theta_0=(-4,\,1.6), η=0.03\eta=0.03, β=0.9\beta=0.9, so ∇f=(x, 25y)\nabla f=(x,\,25y). Both methods start with v0=0v_0=0, so their first step is the same. Values computed by the figure's code.

Step 1 → step 2

  1. 1Step 1, both methods: v1=−0.03 (−4, 40)=(0.12, −1.2)v_1=-0.03\,(-4,\,40)=(0.12,\,-1.2), θ1=(−3.88, 0.4)\theta_1=(-3.88,\,0.4), loss 9.539.53.
  2. 2Heavy ball uses ∇f(θ1)=(−3.88, 10)\nabla f(\theta_1)=(-3.88,\,10). The yy-gradient is still positive, so it adds to the downward velocity: v2=0.9 (0.12,−1.2)−0.03 (−3.88,10)=(0.224, −1.38)v_2=0.9\,(0.12,-1.2)-0.03\,(-3.88,10)=(0.224,\,-1.38), θ2=(−3.656, −0.98)\theta_2=(-3.656,\,-0.98), loss 18.6918.69.
  3. 3Nesterov first jumps to the look-ahead θ1+0.9 v1=(−3.772, −0.68)\theta_1+0.9\,v_1=(-3.772,\,-0.68), which is already below the floor. There ∇f=(−3.772, −17)\nabla f=(-3.772,\,-17): the yy-gradient has flipped sign and opposes the velocity.
  4. 4v2=0.9 (0.12,−1.2)−0.03 (−3.772,−17)=(0.221, −0.57)v_2=0.9\,(0.12,-1.2)-0.03\,(-3.772,-17)=(0.221,\,-0.57), θ2=(−3.659, −0.17)\theta_2=(-3.659,\,-0.17), loss 7.057.05. The xx-progress is almost identical (the flat direction barely notices the look-ahead); the overshoot in yy is 0.17 instead of 0.98.
  5. 5Step 3: heavy ball swings on to y=−1.49y=-1.49 (loss 33.2), Nesterov sits at y=−0.171y=-0.171 with vy≈0v_y\approx0 (loss 6.00).
tplain GDheavy ballNesterov
27.2118.697.05
104.3512.80.103
400.7000.5410.0383
1205.35e-35.99e-53.81e-7
Loss after t steps, η = 0.03, β = 0.9

The form PyTorch implements

The classical form needs the gradient at θ+βv\theta+\beta v, but backprop gives the gradient at the current parameters. The fix (Bengio et al., 2012) is a change of variables: store the look-ahead point ϕt=θt+βvt\phi_t=\theta_t+\beta v_t as the parameters. Rewritten in ϕ\phi and in gradient units, the update needs only ∇f(ϕt)\nabla f(\phi_t):

bt+1=β bt+gt,ϕt+1=ϕt−η (gt+β bt+1),gt=∇f(ϕt)b_{t+1}=\beta\,b_t+g_t,\qquad \phi_{t+1}=\phi_t-\eta\,\big(g_t+\beta\,b_{t+1}\big),\qquad g_t=\nabla f(\phi_t)
bb
the momentum buffer, as in plain SGD momentum (initialised to g0g_0)
gt+βbt+1g_t+\beta b_{t+1}
the current gradient plus the momentum step that will follow: the next step is applied one step early
ϕ\phi
the parameters PyTorch stores and evaluates: the look-ahead sequence of the classical form

With a constant learning rate the two forms visit exactly the same look-ahead points (checked numerically to 10−1510^{-15} on the figure's valley). The parameters you evaluate and save in PyTorch are therefore the ϕ\phi's, not the θ\theta's, so their losses are not the ones in the table above: PyTorch's first iterate is the look-ahead (−3.772, −0.68)(-3.772,\,-0.68), not θ1=(−3.88, 0.4)\theta_1=(-3.88,\,0.4).

python
1import torch
2
3theta = torch.tensor([-4.0, 1.6], requires_grad=True)
4opt = torch.optim.SGD([theta], lr=0.03, momentum=0.9, nesterov=True) # dampening must stay 0
5
6def f(t):
7 return 0.5 * (t[0] ** 2 + 25 * t[1] ** 2)
8
9for step in range(3):
10 opt.zero_grad()
11 f(theta).backward()
12 opt.step() # buf = 0.9*buf + g ; theta -= lr * (g + 0.9*buf)
13 print(theta.detach())
14# ≈ (-3.772, -0.680) (-3.460, -0.683) (-3.083, -0.171)
15
16# Typical use: ResNet-style training
17# opt = torch.optim.SGD(model.parameters(), lr=0.1, momentum=0.9, nesterov=True, weight_decay=5e-4)
18# Adam with a Nesterov-style first moment:
19# opt = torch.optim.NAdam(model.parameters(), lr=2e-3)
Nesterov momentum in PyTorch; the printed iterates are the look-ahead points from the worked example

Use when

  • +Free: same memory and one gradient per step, exactly like heavy-ball momentum
  • +Damps oscillation in high-curvature directions, so high momentum (0.95 to 0.99) stays usable
  • +Provably optimal O(1/k2)O(1/k^2) rate on smooth convex problems, 1−1/κ1-1/\sqrt\kappa on strongly convex ones
  • +One flag in PyTorch: nesterov=True

Avoid when

  • −Smaller stable learning-rate range on quadratics: 2(1+β)/(1+2β)2(1+\beta)/(1+2\beta) instead of 2(1+β)2(1+\beta) in units of 1/λmax⁡1/\lambda_{\max}
  • −Theoretical acceleration is lost under stochastic gradients; gains in deep learning are modest
  • −The stored parameters are look-ahead points, which confuses hand-written implementations and comparisons
  • −Still no per-parameter scaling; badly scaled problems need adaptive methods

Check yourself

Momentum has just carried θ to a point where the next jump βv would overshoot the valley floor. What does Nesterov's gradient look like compared with heavy ball's?

Check yourself

Which statement about PyTorch's SGD(momentum=0.9, nesterov=True) is correct?

Remember

  • ✓NAG: v←βv−η∇f(θ+βv)v\leftarrow\beta v-\eta\nabla f(\theta+\beta v), θ←θ+v\theta\leftarrow\theta+v. Same cost as momentum, gradient taken at the look-ahead point.
  • ✓The look-ahead gradient corrects an overshoot one step early; on a quadratic the correction is βHv\beta Hv, large only in steep directions.
  • ✓Nesterov (1983): O(1/k2)O(1/k^2) on smooth convex functions, optimal for first-order methods; about 1−1/κ1-1/\sqrt\kappa per step when strongly convex.
  • ✓Sutskever et al. (2013) wrote it as a one-line change to classical momentum; PyTorch stores ϕ=θ+βv\phi=\theta+\beta v and steps with g+β bg+\beta\,b.
  • ✓Stability on a quadratic is tighter: ηλmax⁡<2(1+β)/(1+2β)\eta\lambda_{\max}<2(1+\beta)/(1+2\beta).
  • ✓In deep learning it is a cheap, mild improvement in stability at high momentum, not a guaranteed speed-up.
← back to Deep Learning roadmap