Paperlane

no. 12 · Tuesday 10 November 2026

The Optimal Rate Constant of Heavy-Ball Momentum on Smooth Strongly Convex Functions

Marcos Hernanz

math.OC · via cs.LG · code · 41 pp

Abstract

The heavy-ball method with a constant step size and a constant momentum parameter accelerates gradient descent on quadratics, but no choice of the two parameters does so on the class of smooth strongly convex functions. We determine how much faster than gradient descent it can be made on this class. Writing the best worst-case rate over all tunings as $1-c(κ)/κ$, where $κ$ is the condition number, we prove that $c(κ)$ tends to $8$ in every dimension of two or more. The lower bound on the rate holds for every tuning, because a tuning that is faster than $1-8/κ$ on quadratics follows a slowly decaying spiral on some function of two variables. The matching upper bound comes from an explicit tuning, with nearly the momentum of Polyak's tuning and a step size about $\sqrtκ/8$ times smaller, and from a Lyapunov function whose positivity is verified in exact arithmetic. Optimally tuned heavy-ball is therefore asymptotically four times faster than gradient descent on this class.

code
github.com/marcoshernanz/heavy-ball-optimal-rate
comments
41 pages, 1 figure. Code and exact certificates: https://github.com/marcoshernanz/heavy-ball-optimal-rate
fields
Optimization and Control
pdf ↗ page arXiv:2611.12310 ↗