Two Answers on Heavy-Ball Dynamics
Abstract
We determine the worst-case behavior of the heavy-ball method on smooth strongly convex functions, first for Polyak's quadratic-optimal parameters and then for arbitrary constant parameters. For Polyak's tuning, the exact dimension-uniform exponential rate is the largest growth factor of an interpolable mixture of rotating geometric sequences. Four algebraic families determine this rate at every condition number. Two frequencies suffice, and one function in dimension five attains the rate at every horizon up to constant factors. We recover the sharp convergence threshold 9+4√5 of Badithela and Seiler. For general tunings, an exact linear feasibility criterion characterizes dimension-uniform linear convergence through the angle between the characteristic polynomials of the two extreme quadratics. This gives a continuous condition-number threshold and resolves the second heavy-ball riddle of Goujaud, Taylor and Dieuleveut. The regions between consecutive cycle tongues are Farey gaps, each containing convergent and divergent tunings. Regular portions of the threshold surface are analytic plateaus with fixed periodic frequency support. Every rational rotation number in a gap anchors a single-harmonic plateau; mixed-harmonic plateaus and an exact two-lag threshold point also occur. Along tongue edges, explicit multiplier inequalities and second-order expansions of competing Farey fans bound the transition from single-harmonic to mixed-harmonic extremals. The rate bounds and the extremal constructions follow from a common interpolation and separation argument that preserves initialization with zero momentum.
Related
- A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions
- Randomized average block coordinate descent method with heavy-ball momentum for tensor least squares problem under the t-product
- Sharp Initialization Guarantees for the Heavy-Ball Method
- Transformers with CoT Discover Heavy-Ball Acceleration Through Training
- Heavy-Ball Method under Randomized Schedules
BibTeX
@misc{pasechnyukvilensky2026answers,
title = {{Two Answers on Heavy-Ball Dynamics}},
author = {Dmitry Pasechnyuk-Vilensky and Martin Takáč},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09912},
eprint = {2610.09912},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09912},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Two Answers on Heavy-Ball Dynamics
AU - Dmitry Pasechnyuk-Vilensky
AU - Martin Takáč
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.09912
UR - https://arxiv.org/abs/2610.09912
AB - We determine the worst-case behavior of the heavy-ball method on smooth strongly convex functions, first for Polyak's quadratic-optimal parameters and then for arbitrary constant parameters. For Polyak's tuning, the exact dimension-uniform exponential rate is the largest growth factor of an interpolable mixture of rotating geometric sequences. Four algebraic families determine this rate at every condition number. Two frequencies suffice, and one function in dimension five attains the rate at every horizon up to constant factors. We recover the sharp convergence threshold 9+4√5 of Badithela and Seiler. For general tunings, an exact linear feasibility criterion characterizes dimension-uniform linear convergence through the angle between the characteristic polynomials of the two extreme quadratics. This gives a continuous condition-number threshold and resolves the second heavy-ball riddle of Goujaud, Taylor and Dieuleveut. The regions between consecutive cycle tongues are Farey gaps, each containing convergent and divergent tunings. Regular portions of the threshold surface are analytic plateaus with fixed periodic frequency support. Every rational rotation number in a gap anchors a single-harmonic plateau; mixed-harmonic plateaus and an exact two-lag threshold point also occur. Along tongue edges, explicit multiplier inequalities and second-order expansions of competing Farey fans bound the transition from single-harmonic to mixed-harmonic extremals. The rate bounds and the extremal constructions follow from a common interpolation and separation argument that preserves initialization with zero momentum.
ER -