Momentum and Nesterov Acceleration in Gradient Descent

Gradient descent responds to the current gradient and forgets everything before it. On a narrow valley, such as an ill-conditioned quadratic or a ravine in a neural loss surface, that memorylessness is expensive: the iterate crosses the valley repeatedly while making little progress along it, because the cross-valley component of the gradient is large and the along-valley component is small. Momentum fixes the geometry by keeping a running velocity, so that repeated gradients in a consistent direction accumulate and oscillating components cancel. The mechanism is a linear filter, the improvement is provable, and the proofs depend on assumptions that are easy to lose.

The velocity as an exponential moving average

The heavy-ball update keeps a velocity vector v and applies

v ← βv − η∇f(x), x ← x + v.

Written out, the velocity at iteration t is a geometrically weighted sum of all past gradients with weights β^(t−i). The sum of the weights is 1/(1−β), so a constant gradient g produces a steady-state velocity of −ηg/(1−β): momentum multiplies the effective step size by 1/(1−β). At β = 0.9 that factor is 10, which means the step size must be chosen jointly with the damping rather than transferred from a plain gradient-descent run. The memory horizon is the same number: the weights decay by a factor of e every 1/(1−β) steps, about 10 steps at β = 0.9, and the cost is one extra array of the same size as the parameters.

The filtering is the point. Decompose the gradient into a component that is consistent across iterations and a component that alternates. The consistent component accumulates with gain 1/(1−β); a component that alternates in sign every step accumulates with gain 1/(1+β), a factor of about 0.53 at β = 0.9. Momentum therefore amplifies the persistent signal by roughly 19-fold relative to the oscillating error. This ratio, not the raw speed-up, is the reason momentum helps on ill-conditioned problems: the damping parameter directly sets the selectivity of the filter, and it trades convergence speed against stability in the same operation.

Two different recursions that share a name

The heavy-ball method substitutes the velocity into the position as above. Nesterov’s accelerated scheme evaluates the gradient at an extrapolated point,

x_{k+1} = y_k − η∇f(y_k), y_{k+1} = x_{k+1} + β_k (x_{k+1} − x_k),

where the extrapolation coefficient β_k is time-varying, tending to (k−1)/(k+2) for the convex case, rather than the fixed constant of heavy ball. The distinction matters: for strongly convex quadratics both methods can achieve the same asymptotic rate with suitable constants, but for general smooth convex objectives only the Nesterov recursion attains the O(1/k²) rate, and the reason is that the extrapolation coefficient must decrease over time. Practical libraries that expose a momentum parameter are almost always implementing heavy ball, sometimes with a schedule, and the “Nesterov” option in those libraries typically refers to the gradient-at-extrapolated-point variant with a constant coefficient. The names have drifted from the mathematics.

The quadratic case, exactly

For a quadratic with condition number κ = L/μ, the heavy-ball recursion is a linear two-term recurrence whose convergence is governed by the roots of a quadratic characteristic polynomial. Making both roots as small as possible in magnitude gives

β* = ((√κ − 1)/(√κ + 1))², η* = 4/(√L + √μ)²,

with the resulting contraction factor approaching (√κ − 1)/(√κ + 1) per iteration. The comparison with plain gradient descent at η = 1/L, whose factor is 1 − 1/κ, is the sharpest available statement of what momentum buys. For κ = 100, the gradient-descent factor is 0.99 and the momentum factor is about 0.82; the gap widens with κ, and the iteration count to reach a fixed accuracy improves from roughly κ to roughly √κ in the dominant term. This is exactly the exponent that makes the method worth the parameter.

Two caveats come with the formula. The optimal parameters are derived for an exact quadratic, so applying them to a nonlinear objective means the true curvature changes between iterations; the usual fix is to set β slightly below the value the formula suggests. And the 4/(√L + √μ)² step size is roughly four times 1/L when μ is small, which is far outside the stable region for a plain gradient step; the step is only admissible because the velocity term is doing the stabilization. Choosing one of the two parameters without regard to the other is the most common way to make a momentum run diverge.

Acceleration as the discretisation of a differential equation

Su, Boyd and Candès showed that in the continuous-time limit with step η → 0 and coefficient β_k = (k−1)/(k+2) = 1 − 3/(k+2), Nesterov’s scheme converges to the second-order ODE

ẍ + (3/t)ẋ + ∇f(x) = 0,

which is a damped oscillator whose damping coefficient 3/t decays with time: strong damping early, weak damping later. Heavy ball, in the same limit with a constant β, tends instead to a constant-damping equation ẍ + (1−β)√η ẋ + ∇f(x) = 0, whose convergence rate is different and slower. That is the mechanistic content of “acceleration”: the damping must decrease over time for the 1/k² rate, and a constant momentum coefficient cannot express that.

The ODE also explains the observed behaviour of accelerated runs. The oscillation amplitude decreases only as 1/t, so an accelerated iterate can cycle around the minimizer for many iterations with the objective barely improving in the worst case, and the function value along the trajectory is not monotone. Restart schemes, which reset the velocity or the extrapolation coefficient whenever the objective increases, recover monotonicity and often a better practical rate, because a restart returns the system to the strongly damped phase where progress is fast.

Why acceleration is fragile with noise

Everything above assumes exact gradients. Replace ∇f by a stochastic estimate and the amplification factor 1/(1−β) applies to the noise as well as the signal. For the unnormalised velocity recursion, the stationary variance of the velocity is σ²/(1−β²) where σ² is the gradient variance, so at β = 0.9 the velocity variance is about 5.3σ². The larger effective step then multiplies that amplified noise, and the noise floor described in stochastic gradient descent and step decay rises accordingly. Acceleration and stochastic gradients are therefore in tension: the theoretical rate assumes exact gradients and a known L, while the practical setting has neither, and the mitigations, such as a smaller β, gradient clipping or step decay, give back part of the theoretical gain. A related cost is the loss of knowledge of the problem’s constants. The accelerated schemes that come with a linear rate for strongly convex objectives need the strong convexity parameter μ in their coefficients, and μ is not directly measurable; estimating it from observed gradient changes is itself noisy, and the resulting schedule can be worse than a fixed coefficient. The pragmatic response is a fixed coefficient chosen from the small set of values that behave tolerably across problems, together with a decaying step size, which gives back the asymptotic rate while retaining most of the early progress. The same difficulty, that curvature is not available and must be inferred from differences of gradients, is what motivates the secant approximations of quasi-Newton methods, where a wrong estimate is at least not amplified by a factor of 1/(1−β).

A second fragility is the loss of the descent guarantee. With β > 0 the function value can increase for several consecutive iterations even with exact gradients. Any stopping rule or line search that assumes monotone decrease will mis-handle this: an Armijo search applied to the momentum direction requires the direction to be a descent direction for the current gradient, which momentum’s velocity is not. Practical implementations handle it with adaptive restart heuristics, criteria based on the gradient norm rather than the objective, or by treating the momentum recursion as a fixed sequence with no line search at all. Adaptive per-coordinate methods take a different route entirely, replacing the global velocity by per-coordinate scaling, as described in adaptive step sizes for coordinate-wise scaling. The three mechanisms (filtering in time, scaling per coordinate, estimating curvature) compose but do not substitute for one another, and the interaction between a temporal filter and per-coordinate scaling is not covered by the convergence guarantees of either alone.

Where the gain disappears

Momentum improves the constants and, in the convex smooth case, the exponent; it does not change the structure of the problem. If the objective is not smooth, the amplified velocity crosses the kinks near the non-differentiable points harder than a plain gradient step would, and subgradient methods with momentum require step decay for the same reasons as plain subgradient methods. If the condition number is already close to one, the quadratic formula gives β* ≈ 0 and there is nothing to gain. If the gradient is very noisy relative to the curvature, the amplified noise floor dominates the accelerated convergence term for essentially the whole run. The regime where momentum is unambiguously useful is therefore narrow and identifiable: smooth, ill-conditioned, and either deterministic or with a gradient noise level low enough that the amplification factor 1/(1−β) does not push the iterate outside the region where the local quadratic model holds.