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

Oct 18, 2026

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

Despite having an asymptotically optimal rate of convergence on convex quadratics, the acceleration of Polyak's heavy-ball method and a characterization of its dynamics within more general settings have remained long standing open problems. Recently, the work of Goujaud et al. [Math. Program. (2025)] made progress regarding acceleration in the context of smooth, strongly convex minimization: for a small enough inverse condition number, either the method does not accelerate on quadratics, or there exists a smooth strongly convex function such that heavy-ball cycles over the roots of unity. The constructed functions have two variables, thus leaving the question of acceleration over univariate functions open. In this work, we use a Fourier-based analysis to i) provide a proof for the non-acceleration of the heavy-ball method over the class of univariate smooth strongly convex functions. We also ii) provide a strict enlargement of the previous root-of-unity cycling region, with insights regarding the "fractional" sets of Goujaud et al. [arXiv:2502.19916], and iii) give a higher dimensional cycling instance which is not covered by root-of-unity cycling.
Aug 11, 2026

A lower bound for stepsize-based acceleration of gradient descent

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of O(T−1)O(T^{-1}) (where TT denotes the number of iterations) to O(T−log⁡2(1+2))O\big(T^{-\log_2(1+\sqrt{2})}\big) using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical Ω(T−2)Ω(T^{-2}) benchmark for general first-order methods. In this work, we present a new lower bound of Ω(T−1.9319)Ω(T^{-1.9319}) for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal O(T−2)O(T^{-2}) convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.
Sep 8, 2026

Silver Rate Is (Almost) Optimal for Gradient Descent

Gradient descent (GD) is one of the most fundamental algorithms in optimization. Yet even for smooth convex objectives, the optimal rate among predetermined nonnegative stepsize schedules has remained unresolved. Altschuler and Parrilo [Mathematical Programming, 2025] showed that their recursive silver stepsize schedule achieves an O(n−psil)O(n^{-p_{\mathrm{sil}}}) rate, where psil=log⁡2(1+2)≈1.2716p_{\mathrm{sil}}=\log_2(1+\sqrt2)\approx1.2716, improving upon the classical O(n−1)O(n^{-1}) rate of constant-step GD. Although the optimality of psilp_{\mathrm{sil}} has been well supported by numerical evidence for small nn, a matching lower bound has remained missing. In this paper, we prove an Ω(n−psil−o(1))Ω(n^{-p_{\mathrm{sil}}-o(1)}) lower bound for GD, showing that psilp_{\mathrm{sil}} is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent 2psil/(1+psil)≈1.11952p_{\mathrm{sil}}/(1+p_{\mathrm{sil}})\approx1.1195 of the known upper bound [Zhang, Lee, Du, and Chen, COLT 2025]. Building on the approaches of [Ma and Chen, 2026; Jung, Cho, and Yun, 2026], we select specific iterations as checkpoints at which the GD trajectory explores a new coordinate, and we couple these coordinates using a chain of local functions. Our main technical contribution is a local hard function that bends the GD trajectory between successive checkpoints, resulting in a sharpened lower bound. For each prescribed stepsize schedule, we maximize this bound over admissible checkpoint sets. A recursive analysis of this maximum then yields a lower bound matching the silver exponent for every such schedule.