# 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).

Source: https://www.mlfoundry.in/learn/nesterov-accelerated-gradient-nag  
Section: Deep Learning › Optimization Algorithms  
Level: advanced · 11 min read · updated 2026-10-11

**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, $\theta_t+\beta v_t$, rather than at the current point $\theta_t$. In the classical form, $v_{t+1}=\beta v_t-\eta\nabla f(\theta_t+\beta v_t)$ and $\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/k^2)$" (Soviet Mathematics Doklady, 1983). It was a result about worst-case complexity: for any convex function with an $L$-Lipschitz gradient, gradient descent's error falls like $1/k$, and Nesterov's scheme achieves $1/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

$$
\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}
$$

- $v_t$: velocity in parameter units (the classical form), $v_0=0$
- $\theta_t+\beta v_t$: the **look-ahead point**: where momentum alone would take you
- $\beta$: momentum coefficient, typically $0.9$ to $0.99$
- $\eta$: learning rate

Split the Nesterov step in two: a jump $\beta v_t$ to the look-ahead point, then an ordinary gradient step from there, $-\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 $H$, $\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(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 $\dfrac{L\,\lVert x_0-x^\star\rVert^2}{2k}$ for gradient descent with step $1/L$
- **Strongly convex:** error shrinks by about $1-1/\sqrt\kappa$ per step with $\eta=1/L$, $\beta=\frac{\sqrt\kappa-1}{\sqrt\kappa+1}$; GD's $1-1/\kappa$
- **Stability on a quadratic:** $\eta\lambda_{\max}<\dfrac{2(1+\beta)}{1+2\beta}$ ($1.36$ at $\beta=0.9$), much tighter than heavy ball's $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`

> Figure: 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=\eta\lambda$. Writing $\theta_{t+1}$ in terms of the two previous iterates gives two linear recurrences that differ in one factor:

$$
\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=\eta\lambda$: step size measured in units of the local curvature
- $(1-a)$: NAG applies the gradient step to the extrapolated point $(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 $\beta=0.9$. In NAG the product is $\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\approx0$, see the same acceleration as heavy ball.

The same factor $(1-a)$ explains the price. When $a>1$ it is negative and amplifies the extrapolation, so NAG becomes unstable at $a=2(1+\beta)/(1+2\beta)$: $1.36$ at $\beta=0.9$, against $3.8$ for heavy ball. On the figure's valley ($\lambda_{\max}=25$) that is $\eta<0.054$ versus $\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 $f$ with $L$-Lipschitz gradient, Nesterov's scheme uses a step $1/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:

$$
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)
$$

- $y_k$: the look-ahead point: extrapolate along the last step, then take the gradient there
- $\tfrac{k-1}{k+2}$: momentum schedule $0,\tfrac14,\tfrac25,\tfrac12,\dots\to1$; no tuning of $\beta$ is needed
- $O(1/k^2)$: to reach error $\varepsilon$ takes $O(1/\sqrt\varepsilon)$ steps instead of GD's $O(1/\varepsilon)$

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

> **Heavy ball can be faster; Nesterov is guaranteed:** On a quadratic, heavy ball with Polyak's tuning contracts at $(\sqrt\kappa-1)/(\sqrt\kappa+1)=0.667$ per step for $\kappa=25$, faster than tuned Nesterov's $0.800$. Nesterov's advantage is that its accelerated rate is **proven for every** smooth (strongly) convex function, while heavy ball's is only proven for quadratics and can fail elsewhere. Neither guarantee survives the noise and non-convexity of deep learning, where the practical gain is a modest, fairly consistent improvement in stability.

## Worked example: one look-ahead

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

**Step 1 → step 2**

1. Step 1, both methods: $v_1=-0.03\,(-4,\,40)=(0.12,\,-1.2)$, $\theta_1=(-3.88,\,0.4)$, loss $9.53$.
2. Heavy ball uses $\nabla f(\theta_1)=(-3.88,\,10)$. The $y$-gradient is still positive, so it **adds** to the downward velocity: $v_2=0.9\,(0.12,-1.2)-0.03\,(-3.88,10)=(0.224,\,-1.38)$, $\theta_2=(-3.656,\,-0.98)$, loss $18.69$.
3. Nesterov first jumps to the look-ahead $\theta_1+0.9\,v_1=(-3.772,\,-0.68)$, which is already below the floor. There $\nabla f=(-3.772,\,-17)$: the $y$-gradient has flipped sign and **opposes** the velocity.
4. $v_2=0.9\,(0.12,-1.2)-0.03\,(-3.772,-17)=(0.221,\,-0.57)$, $\theta_2=(-3.659,\,-0.17)$, loss $7.05$. The $x$-progress is almost identical (the flat direction barely notices the look-ahead); the overshoot in $y$ is 0.17 instead of 0.98.
5. Step 3: heavy ball swings on to $y=-1.49$ (loss 33.2), Nesterov sits at $y=-0.171$ with $v_y\approx0$ (loss 6.00).

Loss after t steps, η = 0.03, β = 0.9

| t | plain GD | heavy ball | Nesterov |
| --- | --- | --- | --- |
| 2 | 7.21 | 18.69 | 7.05 |
| 10 | 4.35 | 12.8 | 0.103 |
| 40 | 0.700 | 0.541 | 0.0383 |
| 120 | 5.35e-3 | 5.99e-5 | 3.81e-7 |

## The form PyTorch implements

The classical form needs the gradient at $\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 $\phi_t=\theta_t+\beta v_t$ as the parameters. Rewritten in $\phi$ and in gradient units, the update needs only $\nabla f(\phi_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)
$$

- $b$: the momentum buffer, as in plain SGD momentum (initialised to $g_0$)
- $g_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^{-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)$, not $\theta_1=(-3.88,\,0.4)$.

```python
import torch

theta = torch.tensor([-4.0, 1.6], requires_grad=True)
opt = torch.optim.SGD([theta], lr=0.03, momentum=0.9, nesterov=True)   # dampening must stay 0

def f(t):
    return 0.5 * (t[0] ** 2 + 25 * t[1] ** 2)

for step in range(3):
    opt.zero_grad()
    f(theta).backward()
    opt.step()          # buf = 0.9*buf + g ;  theta -= lr * (g + 0.9*buf)
    print(theta.detach())
# ≈ (-3.772, -0.680)   (-3.460, -0.683)   (-3.083, -0.171)

# Typical use: ResNet-style training
# opt = torch.optim.SGD(model.parameters(), lr=0.1, momentum=0.9, nesterov=True, weight_decay=5e-4)
# Adam with a Nesterov-style first moment:
# 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

> **Nesterov has a smaller stable learning rate:** Switching `nesterov=True` on with an unchanged recipe is usually harmless, because deep-learning learning rates sit far below the curvature limit. But on a quadratic the stability bound drops from $\eta\lambda_{\max}<3.8$ to $\eta\lambda_{\max}<1.36$ at $\beta=0.9$. A learning rate that was near the edge for heavy ball can diverge with Nesterov, as the figure shows at $\eta=0.06$.

> **The acceleration theory needs exact gradients:** The $O(1/k^2)$ and $1-1/\sqrt\kappa$ rates assume deterministic gradients. With mini-batch noise, momentum of either kind averages noise over about $1/(1-\beta)$ steps, but it cannot beat the noise floor, and accelerated methods can accumulate gradient errors. Do not expect a square-root speed-up in SGD training; expect slightly smoother, slightly more stable curves.

> **Where you meet it:** SGD with `nesterov=True` is a common setting for training image classifiers with SGD. The same look-ahead idea reappears in NAdam (Adam with a Nesterov-style first moment) and in accelerated proximal methods such as FISTA for sparse regression.

**Strengths**

- 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/k^2)$ rate on smooth convex problems, $1-1/\sqrt\kappa$ on strongly convex ones
- One flag in PyTorch: `nesterov=True`

**Limitations**

- Smaller stable learning-rate range on quadratics: $2(1+\beta)/(1+2\beta)$ instead of $2(1+\beta)$ in units of $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

**Question:** 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?

- A. The same, since both are evaluated at θ
- B. It already points back across the floor, so it opposes the velocity and brakes the step
- C. It is zero, because the look-ahead point is the minimum
- D. It is β times smaller

**Answer:** B. It already points back across the floor, so it opposes the velocity and brakes the step — Nesterov evaluates the gradient at $\theta+\beta v$, beyond the floor, where the slope has changed sign. In the worked example the $y$-gradient is $+10$ at $\theta_1$ but $-17$ at the look-ahead, so Nesterov's second step overshoots to $y=-0.17$ instead of $-0.98$.

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

- A. It computes two gradients per step, one at θ and one at θ + βv
- B. It stores the look-ahead point as the parameters and updates them with g + β·buf
- C. It requires dampening = β
- D. It is identical to nesterov=False whenever the learning rate is constant

**Answer:** B. It stores the look-ahead point as the parameters and updates them with g + β·buf — The change of variables $\phi=\theta+\beta v$ lets the update use only $\nabla f(\phi)$, the gradient backprop already gives: $b\leftarrow\beta b+g$, $\phi\leftarrow\phi-\eta(g+\beta b)$. Dampening must be 0, and the iterates differ from heavy ball's at any learning rate.

**Key points**

- NAG: $v\leftarrow\beta v-\eta\nabla f(\theta+\beta 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 $\beta Hv$, large only in steep directions.
- Nesterov (1983): $O(1/k^2)$ on smooth convex functions, optimal for first-order methods; about $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 $\phi=\theta+\beta v$ and steps with $g+\beta\,b$.
- Stability on a quadratic is tighter: $\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
