# Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality

arXiv: https://arxiv.org/abs/2410.16849 · HTML: https://mlsanity.com/paper/2410.16849/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 64 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 28 of 28)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Convergence rates for the stochastic gradient descent method for non-convex objective functions](https://mlsanity.com/paper/1904.01517/) (2019)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [iPiano: Inertial Proximal Algorithm for Non-Convex Optimization](https://mlsanity.com/paper/1404.4805/) (2014)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network](https://mlsanity.com/paper/2010.01618/) (2020)
- [Fast convex optimization via inertial dynamics with Hessian driven damping](https://mlsanity.com/paper/1601.07113/) (2016)
- [On minimal representations of shallow ReLU networks](https://mlsanity.com/paper/2108.05643/) (2021)
- [Provable non-accelerations of the heavy-ball method](https://mlsanity.com/paper/2307.11291/) (2023)
- [Convergence rates for the Heavy-Ball continuous dynamics for non-convex optimization, under Polyak-L ojasiewicz condition](https://mlsanity.com/paper/2107.10123/) (2021)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Local Convergence of the Heavy-ball Method and iPiano for Non-convex Optimization](https://mlsanity.com/paper/1606.09070/) (2016)
- [Non-monotone Behavior of the Heavy Ball Method](https://mlsanity.com/paper/1811.00658/) (2018)
- [Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry](https://mlsanity.com/paper/1703.09477/) (2017)
- [Nesterov acceleration in benignly non-convex landscapes](https://mlsanity.com/paper/2410.08395/) (2024)
- [Accelerated First-Order Methods: Differential Equations and Lyapunov Functions](https://mlsanity.com/paper/1903.05671/) (2019)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [A Multi-step Inertial Forward--Backward Splitting Method for Non-convex Optimization](https://mlsanity.com/paper/1606.02118/) (2016)
- [On the Lower Bound of Minimizing Polyak-Lojasiewicz Functions](https://mlsanity.com/paper/2212.13551/) (2022)
- [Inertial Newton Algorithms Avoiding Strict Saddle Points](https://mlsanity.com/paper/2111.04596/) (2021)
- [Gradient-Type Methods for Optimization Problems with Polyak-Lojasiewicz Condition: Early Stopping and Adaptivity to Inexactness Parameter](https://mlsanity.com/paper/2212.04226/) (2022)
- [Heavy Ball Momentum for Non-Strongly Convex Optimization](https://mlsanity.com/paper/2403.06930/) (2024)
- [Second-order growth, tilt stability, and metric regularity of the subdifferential](https://mlsanity.com/paper/1304.7385/) (2013)
- [Quadratic growth and critical point stability of semi-algebraic functions](https://mlsanity.com/paper/1309.1446/) (2013)

## Built on by (most cited first, 3 of 3)

- [Towards understanding Accelerated Stein Variational Gradient Flow -- Analysis of Generalized Bilinear Kernels for Gaussian target distributions](https://mlsanity.com/paper/2509.04008/) (2025)
- [Towards Understanding Momentum Acceleration in River-Valley Loss Landscape](https://mlsanity.com/paper/2609.30957/) (2026)
- [Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approach](https://mlsanity.com/paper/2605.14663/) (2026)

## Abstract (arXiv)

In this work, we analyze the convergence of Polyak's heavy ball method in both continuous and discrete time for non-convex C4-objective functions satisfying the Polyak-Lojasiewicz inequality. Under this weak assumption, we recover the asymptotic convergence rates originally derived by Polyak in [Polyak, U.S.S.R. Comput. Math. and Math. Phys., 1964] for strongly convex objectives. Our results demonstrate that the heavy ball method exhibits asymptotic local acceleration on this class of functions. In particular, in the discrete time setting, we prove local convergence of the iterates to a minimum once the method enters a sufficiently small neighborhood of the set of minima, for a broad range of hyperparameters, including aggressive choices for the momentum parameter and the step-size for which global convergence is known to fail. Instead of the usually employed Lyapunov-type arguments, our approach leverages a new differential geometric perspective of the Polyak-Lojasiewicz inequality proposed in [Rebjock and Boumal, Math. Program., 2025].