Heavy-ball method does not speed up solving 1D smooth convex problems

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

Machine Learning

Summary

Finding the fastest way to solve optimization problems is important for many fields. The heavy-ball method is a way to speed up solving such problems, especially when dealing with multi-dimensional quadratic functions. The authors show that in one-dimensional smooth, strongly convex problems, this method does not actually speed up the solution process. They use mathematical analysis to prove this and also explore more complex cycling behaviors of the method in higher dimensions.

What this means in practice

  • For optimization algorithm designers: Avoid using the heavy-ball method for accelerating univariate smooth strongly convex problems based on its proven non-acceleration in that setting.
  • For machine learning engineers: Recognize limits of the heavy-ball method’s acceleration in single-variable convex optimization tasks, and prefer other algorithms for faster convergence.

A theory result. No direct application yet.

Authors

Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach

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.