Non-Acceleration of the Heavy-Ball Method in 1D

Konstantinos Fotopoulos; Michael Helcig; Karl Deck; Jannis Alsbach

math.OCOct 18, 2026

Non-Acceleration of the Heavy-Ball Method in 1D

Authors: Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach

Organizations: Department of CS, ETH Zürich, Switzerland

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.

Figures & tables

Panel of Figure 1 — Figure 1. Augmented regions and binding constraints

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

$K$	$m$	$\Delta_{m}$	$A_{K,m}$	$q_{K,m}\cot(\pi/K)$	$A_{K,m}-q_{K,m}\cot(\pi/K)$
3	1	1	0.101657820	0.102961064	$-0.001303244$
4	1	1	0.205813010	0.205922128	$-0.000109119$
5	1	1	0.191293486	0.269555566	$-0.078262080$
5	2	3	$-0.041604599$	0.166594501	$-0.208199100$
6	1	1	0.152186257	0.308883193	$-0.156696936$
7	1	1	0.114644817	0.334312475	$-0.219667658$

Appendix

Table 1. Exhaustive verification of all primitive pure modes with

3\leq K\leq 9

, up to the reflection symmetry

m\leftrightarrow K-m

. Here

\Delta_{m}

is the unique integer in

\{1,\dots,K-1\}

satisfying

m\Delta_{m}\equiv 1\pmod{K}

, and

A_{K,m}:=p_{K,m}(1-p_{K,m})-q_{K,m}^{2}

. In every case,

A_{K,m}-q_{K,m}\cot(\pi/K)<0

, equivalently

\phi_{K,m}(\Delta_{m})>0

, so the corresponding pure mode is infeasible.

Momentum Methods

Momentum methods accelerate optimization by combining current gradients with information from past updates.

See all 58 papers

Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis
Sep 29, 2026Jiawei Zhang, Qitan Shi, Yuantao GuStochastic Optimization Stochastic Optimization Convergence
Tsinghua University
Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$
Jul 23, 2026Dawei Li, Xiaotian Jiang, Mingyi HongOptimization Convergence Analysis
University of Minnesota
Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima
Jul 13, 2023Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. BajwaNonconvex Optimization Accelerated Gradient Methods
Department of Electrical and Computer Engineering, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering, Management Science and Information Systems, and Statistics, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering and Statistics, Rutgers University–New Brunswick, NJ 08854 USA

Sep 29, 2026J/K move · Enter open · S save

Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis

Jiawei Zhang, Qitan Shi, Yuantao Gu

Tsinghua University

Stochastic Optimization Stochastic Optimization Convergence Nonconvex Stochastic Optimization Last-Iterate Convergence Gradient Descent

Open paper AskPDF arXiv

Polyak step size (PS) and Armijo line search (ALS) have received increasing attention in stochastic optimization, with encouraging empirical performance and theoretical guarantees. However, their convergence theory for stochastic heavy ball (SHB) methods remains limited. In this work, we develop a unified convergence analysis for SHB equipped with PS and ALS. To this end, we introduce a modified Armijo rule that closely parallels the Polyak step size, together with a decoupling analysis that isolates the historical dependence induced by momentum. For SHB with standard PS and ALS, we establish expected convergence for strongly convex, convex, and non-convex objectives without interpolation or restrictive conditions on the momentum parameter. Under interpolation or strong growth, we further strengthen the results to almost sure rates and last-iterate convergence. Moreover, for general settings beyond interpolation, we prove almost sure convergence to the exact optimum or to stationarity for SHB with diminishing variants of PS and ALS. These results provide a more comprehensive theoretical view of Polyak step size and Armijo line search for stochastic heavy ball methods.

Abstract

Momentum Methods

Explore similar work

Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis

Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension n≥4n\geq 4n≥4

Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$