Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Łojasiewicz Functions when the Non-Convexity is Averaged-Out
Preprint
Abstract
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-\L{}ojasiewicz (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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimizationMathematical Programming, 2023
- Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak–Łojasiewicz conditionJournal of Global Optimization, 2022
- Convergence rates of the Heavy-Ball method under the Łojasiewicz propertyMathematical Programming, 2022
- Loss landscapes and optimization in over-parameterized non-linear systems and neural networksApplied and Computational Harmonic Analysis, 2022
- Understanding the acceleration phenomenon via high-resolution differential equationsMathematical Programming, 2021
- Sparse optimization on measures with over-parameterized gradient descentMathematical Programming, 2021
- Analytical convergence regions of accelerated gradient descent in nonconvex optimization under Regularity ConditionAutomatica, 2020
- Non-monotone Behavior of the Heavy Ball MethodSpringer Proceedings in Mathematics & Statistics, 2020
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition2016
- iPiasco: Inertial Proximal Algorithm for Strongly Convex OptimizationJournal of Mathematical Imaging and Vision, 2015