Two Answers on Heavy-Ball Dynamics
math.OC, math.DS
Submitted: 2026-10-07
Updated: 2026-10-24
Comments: 77 pages, 9 figures, links to Lean formalization and source code
Code: https://github.com/dmivilensky/Heavy-Ball
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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 sqrt5 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.
Sources
- Open Problem: Two Riddles in Heavy-Ball Dynamics
- Construction of Periodic Counterexamples to the Discrete-Time Kalman Conjecture
- On the Necessity and Sufficiency of Discrete-Time O'Shea-Zames-Falb Multipliers
- Duality bounds for discrete-time Zames-Falb multipliers
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise