arXiv preprint ·
Non-Acceleration of the Heavy-Ball Method in 1D
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Corrected Block Sparse Spectral Optimization: Exact Models, Finite Identification, and Local Dynamics
When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
Adding Heavy-Ball Momentum to Distributed Constrained Optimization for Energy Resource Management Subject to Time-Delays and Quantization
Hybrid metaheuristics for architectural design optimization under small evaluation and wall-clock budgets
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.