# Global convergence of the Heavy-ball method for convex optimization

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

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2014.

## Built on by (most cited first, 30 of 61)

- [The AdEMAMix Optimizer: Better, Faster, Older](https://mlsanity.com/paper/2409.03137/) (2024)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Fast Margin Maximization via Dual Acceleration](https://mlsanity.com/paper/2107.00595/) (2021)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [Provable Adaptivity of Adam under Non-uniform Smoothness](https://mlsanity.com/paper/2208.09900/) (2022)
- [Automatic differentiation of nonsmooth iterative algorithms](https://mlsanity.com/paper/2206.00457/) (2022)
- [Does Momentum Change the Implicit Regularization on Separable Data?](https://mlsanity.com/paper/2110.03891/) (2021)
- [On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions](https://mlsanity.com/paper/2402.03982/) (2024)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Revisiting Convergence of AdaGrad with Relaxed Assumptions](https://mlsanity.com/paper/2402.13794/) (2024)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [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)
- [Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization](https://mlsanity.com/paper/2106.03034/) (2021)
- [Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks](https://mlsanity.com/paper/2403.05293/) (2024)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization](https://mlsanity.com/paper/2110.09057/) (2021)
- [Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting](https://mlsanity.com/paper/2302.03550/) (2023)
- [High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noise](https://mlsanity.com/paper/2311.02000/) (2023)
- [The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods](https://mlsanity.com/paper/2102.07314/) (2021)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems](https://mlsanity.com/paper/2102.11755/) (2021)
- [Last-iterate convergence analysis of stochastic momentum methods for neural networks](https://mlsanity.com/paper/2205.14811/) (2022)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality](https://mlsanity.com/paper/2410.16849/) (2024)
- [FedUHB: Accelerating Federated Unlearning via Polyak Heavy Ball Method](https://mlsanity.com/paper/2411.11039/) (2024)
- [On the Effectiveness of the z-Transform Method in Quadratic Optimization](https://mlsanity.com/paper/2507.03404/) (2025)

## Abstract (arXiv)

This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesaro average of the iterates converges to the optimum at a rate of O(1/k) where k is the number of iterations. When the objective function is also strongly convex, we prove that the Heavy-ball iterates converge linearly to the unique optimum.