Heavy-ball acceleration problem
Let and let denote the class of differentiable functions that are -strongly convex and have -Lipschitz continuous gradients. For fixed parameters and , the classical heavy-ball iteration is . Does there exist a choice of and , depending on and , for which this iteration has a uniform accelerated worst-case convergence rate over , with dependence on the condition number of accelerated order rather than the nonaccelerated order? The one-dimensional case asks the same question for .
References
- Non-Acceleration of the Heavy-Ball Method in 1D — arXiv — Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach
Source: arXiv
Progress summary
A 2026 preprint claims to settle the one-dimensional case by showing that heavy-ball cannot achieve acceleration there, while the higher-dimensional question remains open.
The problem asks whether classical heavy-ball momentum can achieve accelerated worst-case performance on smooth, strongly convex functions. Earlier work established cycling obstructions in dimension , but left the one-dimensional case open.
Known results
- Goujaud et al., 2023: for any parameters, either the quadratic worst-case rate is not accelerated or a smooth strongly convex example fails to converge; the construction has dimension at least .
- A 2025 paper reported numerical one-dimensional cycles but explicitly did not claim a proof.
2026 one-dimensional claim
Fotopoulos, Helcig, Deck, and Alsbach claim that Fourier analysis and projected root-of-unity cycles prove non-acceleration in one dimension and enlarge the cycling region. Two other 2026 preprints describe this as settling the scalar case, but the claim remains unverified; higher-dimensional behavior is not resolved.
Current status (as of October 2026): The one-dimensional obstruction is claimed but unverified, while the higher-dimensional acceleration question remains open.
Solutions 0
No solutions have been posted yet.