cs.LGNov 9, 2026

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

Authors: Marcos Hernanz

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(κ)/κ1-c(κ)/κ, where κκ is the condition number, we prove that c(κ)c(κ) tends to 88 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/κ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 κ/8\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.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Non-Acceleration of the Heavy-Ball Method in 1D

    Oct 18, 2026Konstantinos Fotopoulos, Michael Helcig, Karl Deck +1Momentum MethodsAccelerated Gradient Methods

  2. A lower bound for stepsize-based acceleration of gradient descent

    Aug 11, 2026Jianhao Ma, Yuxin ChenLearning Rate SchedulingLast-Iterate Convergence