Momentum and Nesterov Acceleration

Heavy ball, Nesterov's method, the estimate-sequence proof of the O(1/t^2) rate, and why acceleration is fragile.

Advanced OptimizationGraduate⏱ 1 day12 min readmomentumnesterovheavy ballaccelerationlyapunov

AssumesGradient Descent and Its Convergence Rates

The lower bound says that a first-order method can achieve $O(1/t^2)$ on convex smooth problems and $(1-1/\sqrt\kappa)^t$ under strong convexity, while plain gradient descent achieves only $O(1/t)$ and $(1-1/\kappa)^t$ . Momentum closes both gaps.

Run it: Gradient descent, momentum and SGDTrajectories and suboptimality curves for GD, Nesterov acceleration, heavy ball and SGD on a quadratic.

Heavy ball

DefinitionHeavy ball (Polyak momentum)

x_{t+1} = x_t - \eta\nabla f(x_t) + \beta(x_t - x_{t-1}), \qquad \beta\in[0,1).

Equivalently, with velocity $v_t = x_t - x_{t-1}$ : $v_{t+1} = \beta v_t - \eta\nabla f(x_t)$ and $x_{t+1} = x_t + v_{t+1}$ .

TheoremHeavy ball on a quadratic

Let $f(x) = \tfrac12x^\top Ax$ with $\mu I\preceq A\preceq LI$ , $\kappa = L/\mu$ . With

\eta = \frac{4}{(\sqrt L+\sqrt\mu)^2}, \qquad \beta = \left(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^2,

the heavy-ball iterates satisfy $\norm{x_t - x^\star}_2 \le C\rho^t\norm{x_0-x^\star}_2$ with

\rho = \frac{\sqrt\kappa-1}{\sqrt\kappa+1} = 1 - \frac{2}{\sqrt\kappa+1}+O(\kappa^{-1}) .

Compare gradient descent's $1 - 2/(\kappa+1)$ .

Key idea

The mechanism is visible in the proof: gradient descent has one tunable parameter and must compromise between the $\lambda=\mu$ and $\lambda=L$ directions, giving a rate governed by $\kappa$ . Momentum has two, and they can be chosen so that the characteristic roots are complex with modulus $\sqrt\beta$ for every eigenvalue at once. The rate stops depending on which eigenvalue is worst, and the $\kappa$ becomes $\sqrt\kappa$ . This is exactly the same trick as Chebyshev acceleration of linear solvers, and the optimal $\rho$ is the Chebyshev value.

Nesterov's method

DefinitionNesterov accelerated gradient

With $y_0 = x_0$ and $\theta_0 = 1$ :

x_{t+1} = y_t - \frac1L\nabla f(y_t), \qquad y_{t+1} = x_{t+1} + \frac{t}{t+3}\big(x_{t+1}-x_t\big) .

The gradient is evaluated at the extrapolated point $y_t$ , not at $x_t$ — this is the difference from heavy ball, and it is what makes the convex (non-strongly-convex) analysis work.

TheoremNesterov acceleration for convex smooth functions

Let $f$ be convex and $L$ -smooth with minimiser $x^\star$ . Then Nesterov's method satisfies

f(x_t) - f^\star \le \frac{2L\norm{x_0-x^\star}_2^2}{(t+1)^2} .

TheoremNesterov acceleration under strong convexity

If $f$ is additionally $\mu$ -strongly convex, the constant-momentum variant with $\beta = \frac{\sqrt\kappa-1}{\sqrt\kappa+1}$ and $\eta = 1/L$ satisfies

f(x_t)-f^\star \le \left(1-\frac{1}{\sqrt\kappa}\right)^t\cdot\kappa\big(f(x_0)-f^\star\big) .

Quoted from Nesterov's lectures. Together with the lower bound, this settles the complexity of smooth strongly convex first-order optimisation: $\Theta(\sqrt\kappa\log(1/\eps))$ gradient queries.

Acceleration is fragile

PropositionHeavy ball can fail on a convex function

There exist $L$ -smooth, $\mu$ -strongly convex functions on $\R$ (piecewise quadratic with three distinct curvatures) for which heavy ball with the quadratic-optimal parameters does not converge, but enters a limit cycle.

Quoted from Lessard, Recht and Packard, who construct the example and explain it through a robust control analysis. The point is structural: the proof of the heavy-ball rate above used diagonalisation, which requires $f$ to be exactly quadratic. For general strongly convex $f$ the curvature changes between iterations, and the two-parameter tuning that made all eigendirections contract at $\sqrt\beta$ no longer applies.

What this does not say

Nesterov's method does have a proof for general convex and for general strongly convex $f$ , so it is not fragile in the same way. But neither method has a proof under the conditions that matter for deep learning: no convexity, stochastic gradients, and no global smoothness constant. The empirical fact that momentum helps in neural network training is real and robust; the accelerated rate is not established in that setting, and citing the $O(1/t^2)$ theorem as an explanation of why momentum helps in deep learning is an over-claim. See the deep learning theory page.

HeuristicThree interpretations of acceleration

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

None of these is a proof; each is a lens that makes the phenomenon less surprising.

Chebyshev / polynomial. After $t$ steps, any first-order method on a quadratic produces $x_t - x^\star = p_t(A)(x_0-x^\star)$ for some degree- $t$ polynomial $p_t$ with $p_t(0)=1$ . Minimising $\max_{\lambda\in[\mu,L]}|p_t(\lambda)|$ over such polynomials is a classical problem whose solution is the Chebyshev polynomial, with value $\approx 2\rho^t$ for $\rho = \frac{\sqrt\kappa-1}{\sqrt\kappa+1}$ . Acceleration is the algorithmic realisation of the optimal polynomial; gradient descent corresponds to the suboptimal $p_t(\lambda)=(1-\eta\lambda)^t$ .
Continuous time. As $\eta\to0$ Nesterov's method has the ODE limit $\ddot X + \frac3t\dot X + \nabla f(X)=0$ , a damped oscillator with vanishing friction. Su, Boyd and Candès showed this ODE has $f(X(t))-f^\star = O(1/t^2)$ , and the discrete rate is its discretisation. The $3/t$ damping is the continuous-time image of the $t/(t+3)$ momentum.
Momentum averages out oscillation. In the ill-conditioned directions gradient descent oscillates, and consecutive gradients partly cancel; the momentum buffer accumulates the consistent component and cancels the oscillating one. This is the picture the trajectory panel of the SGD experiment shows, and it is the least rigorous of the three — it explains heavy ball better than it explains Nesterov.

Problems

Heavy ball on a quadratic — the spectral analysisProof · Graduate · 3 hours The Nesterov potential functionProof · Graduate · 3 hours Acceleration as an optimal polynomialProof · Graduate · 1 hour Simulate and compare convergence ratesCoding · Intermediate · 1 hour

References

PaperYurii Nesterov (1983). A method of solving a convex programming problem with convergence rate O(1/k^2)
BookYurii Nesterov (2018). Lectures on Convex Optimization
PaperWeijie Su, Stephen Boyd and Emmanuel J. Candès (2016). A differential equation for modeling Nesterov's accelerated gradient method
PaperLaurent Lessard, Benjamin Recht and Andrew Packard (2016). Analysis and design of optimization algorithms via integral quadratic constraintsContains the heavy-ball non-convergence example quoted here.
PaperBoris T. Polyak (1964). Some methods of speeding up the convergence of iteration methods

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremHeavy ball on a quadraticproof includedOn a quadratic, optimally tuned heavy ball converges at rate 1 - 2/(sqrt kappa + 1), a square-root improvement over gradient descent.
TheoremNesterov acceleration for convex smooth functionsproof includedAn O(1/t^2) rate, matching the first-order lower bound.
TheoremNesterov acceleration under strong convexityA geometric rate with sqrt(kappa) in place of kappa.
PropositionHeavy ball can fail to converge on a convex functionThere is a smooth strongly convex function on which a fixed-momentum heavy ball cycles.
HeuristicInterpretations of accelerationThree readings of why momentum helps, none of which is a proof on its own.

Problems (5)

All problems