Non-Acceleration of the Heavy-Ball Method in 1D
Abstract
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.
Related
- Transformers with CoT Discover Heavy-Ball Acceleration Through Training
- 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
- Heavy-Ball Method under Randomized Schedules
BibTeX
@misc{fotopoulos2026nonacceleration,
title = {{Non-Acceleration of the Heavy-Ball Method in 1D}},
author = {Konstantinos Fotopoulos and Michael Helcig and Karl Deck and Jannis Alsbach},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25104},
eprint = {2610.25104},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25104},
}
RIS
TY - UNPB
TI - Non-Acceleration of the Heavy-Ball Method in 1D
AU - Konstantinos Fotopoulos
AU - Michael Helcig
AU - Karl Deck
AU - Jannis Alsbach
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25104
UR - https://arxiv.org/abs/2610.25104
AB - 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.
ER -