mlsanityData to 13 Oct 2026

Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out

arXiv 2206.11872 ↗First posted 22 Jun 2022math.OC cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

Heavy Ball (HB) nowadays is one of the most popular momentum methods in non-convex optimization. It has been widely observed that incorporating the Heavy Ball dynamic in gradient-based methods accelerates the training process of modern machine learning models. However, the progress on establishing its theoretical foundation of acceleration is apparently far behind its empirical success. Existing provable acceleration results are of the quadratic or close-to-quadratic functions, as the current techniques of showing HB's acceleration are limited to the case when the Hessian is fixed. In this work, we develop some new techniques that help show acceleration beyond quadratics, which is achieved by analyzing how the change of the Hessian at two consecutive time points affects the convergence speed. Based on our technical results, a class of Polyak-Lojasiewicz (PL) optimization problems for which provable acceleration can be achieved via HB is identified. Moreover, our analysis demonstrates a benefit of adaptively setting the momentum parameter. (Update: 08/29/2023) Erratum is added in Appendix J. This is an updated version that fixes an issue in the previous version. An additional condition needs to be satisfied for the acceleration result of HB beyond quadratics in this work, which naturally holds when the dimension is one or, more broadly, when the Hessian is diagonal. We elaborate on the issue in Appendix J.

Key facts. Cited by 11 papers in the map (data through 13 Oct 2026). Builds on 32 of its 49 references that are in the map. First posted on arXiv 22 Jun 2022.

Builds on

32 of 49 references.

References · 32

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,950
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,093
  3. 2019On the Convergence of Adam and Beyondcited by 837
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 529
  5. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 305
  6. 2017The Marginal Value of Adaptive Gradient Methods in Machine Learningcited by 250
  7. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  8. 2019Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networkscited by 122
  9. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 118
  10. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  11. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  12. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
20 more
  1. 2019Implicit Regularization for Optimal Sparse Recoverycited by 79
  2. 2018Understanding the Acceleration Phenomenon via High-Resolution Differential Equationscited by 68
  3. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  4. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 60
  5. 2019Sparse Optimization on Measures with Over-parameterized Gradient Descentcited by 50
  6. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  7. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  8. 2015From Averaging to Acceleration, There is Only a Step-sizecited by 24
  9. 2018Acceleration through Optimistic No-Regret Dynamicscited by 22
  10. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  11. 2020A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Networkcited by 19
  12. 2019Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distancescited by 15
  13. 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 15
  14. 2019Generalized Momentum-Based Methods: A Hamiltonian Perspectivecited by 12
  15. 2021Convergence rates for the Heavy-Ball continuous dynamics for non-convex optimization, under Polyak-L ojasiewicz conditioncited by 11
  16. 2020Universal Average-Case Optimality of Polyak Momentumcited by 9
  17. 2021Non-asymptotic convergence bounds for Wasserstein approximation using point cloudscited by 9
  18. 2018Non-monotone Behavior of the Heavy Ball Methodcited by 8
  19. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  20. 2018Analytical Convergence Regions of Accelerated Gradient Descent in Nonconvex Optimization under Regularity Conditioncited by 3

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 3; 2024: 3; 2025: 1.

11 papers.

  1. 2022Compute-Efficient Deep Learning: Algorithmic Trends and Opportunitiescited by 38
  2. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  3. 2022Towards Understanding GD with Hard and Conjugate Pseudo-labels for Test-Time Adaptationcited by 9
  4. 2022Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Timecited by 7
  5. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 5
  6. 2025Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Gamescited by 3
  7. 2024Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequalitycited by 2
  8. 2022When is Momentum Extragradient Optimal? A Polynomial-Based Analysiscited by 1
  9. 2023Invex Programs: First Order Algorithms and Their Convergencecited by 1
  10. 2023Accelerated Optimization Landscape of Linear-Quadratic Regulatorcited by 0
  11. 2024(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentumcited by 0