Heavy Ball

The heavy ball method, a momentum-based optimization algorithm, aims to accelerate convergence in solving large-scale optimization problems, particularly prevalent in machine learning. Current research focuses on analyzing its convergence rates under various conditions, including stochasticity, data heterogeneity, and different step-size and momentum parameter selection strategies, often within the context of stochastic gradient descent and its variants applied to neural networks. These investigations are crucial for improving the efficiency and robustness of training complex models, impacting fields like deep learning and federated learning where computational cost and data distribution are significant challenges. Understanding the implicit regularization properties of heavy ball methods is also a key area of ongoing research.

Papers

October 22, 2024

Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality
Sebastian Kassing, Simon Weissmann
Early Stage Convergence Lyapunov Function Non Convex Objective Universal Rate Convex Objective Heavy Ball

August 13, 2024

Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximation
Yanjie Dong, Haijun Zhang, Gang Wang, Shisheng Cui, Xiping Hu
Markov Decision Process Function Approximation Reinforcement Learning Task Critic Model Heavy Ball Stochastic Policy Gradient

June 6, 2024

Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance
Dimitris Oikonomou, Nicolas Loizou
Stochastic Gradient Descent Convergence Guarantee Residual Momentum Heavy Ball Real World Performance Stochastic Polyak

January 12, 2024

(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum
Anh Dang, Reza Babanezhad, Sharan Vaswani
Stochastic Gradient Descent Stochastic Gradient Low Rate ACCELERATION Strongly Convex Heavy Ball

December 22, 2023

Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise
Rui Pan, Yuxing Liu, Xiaoyu Wang, Tong Zhang
Gradient Noise Heavy Ball Accelerated Convergence Near Optimal Convergence

November 30, 2023

Communication-Efficient Heterogeneous Federated Learning with Generalized Heavy-Ball Momentum
Riccardo Zaccone, Carlo Masone, Marco Ciccone
Efficient Learning Heterogeneous Federated Learning Decentralized Data Heavy Ball

April 20, 2023

On the Effects of Data Heterogeneity on the Convergence Rates of Distributed Linear System Solvers
Boris Velasevic, Rohit Parasnis, Christopher G. Brinton, Navid Azizan
Mixed Effect Convergence Rate Data Heterogeneity Heavy Ball Projection Algorithm Consensus Problem Linear System Solver

February 15, 2023

Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption
Jun Liu, Ye Yuan
Stochastic Gradient Descent Stochastic Gradient Gradient Norm Saddle Point Heavy Ball Noisy Gradient

February 2, 2023

Implicit regularization in Heavy-ball momentum accelerated stochastic gradient descent
Avrajit Ghosh, He Lyu, Xitong Zhang, Rongrong Wang
Gradient Descent Stochastic Gradient Descent Implicit Regularization Heavy Ball

October 13, 2022

Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence
Diyuan Wu, Vyacheslav Kungurtsev, Marco Mondelli
Gradient Descent Mean Field Stochastic Way Structured Dropout Global Convergence Massive Connectivity Heavy Ball Mean Field Limit

August 8, 2022

Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural Networks
Xin Liu, Wei Tao, Wei Li, Dazhi Zhan, Jun Wang, Zhisong Pan
Neural Network Nesterov Momentum Accelerated Gradient Method Anderson Acceleration Heavy Ball Accelerated Convergence Momentum Method First Order Gradient

June 22, 2022

Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-\L{}ojasiewicz Functions when the Non-Convexity is Averaged-Out
Jun-Kun Wang, Chi-Heng Lin, Andre Wibisono, Bin Hu
Non Convex Optimization Anderson Acceleration Non Convexity Heavy Ball Momentum Method

June 15, 2022

On the fast convergence of minibatch heavy ball momentum
Raghu Bollapragada, Tyler Chen, Rachel Ward
Fast Convergence Transition Matrix Heavy Ball Momentum Method Kaczmarz Algorithm

May 30, 2022

Last-iterate convergence analysis of stochastic momentum methods for neural networks
Dongpo Xu, Jinlan Liu, Yinghua Lu, Jun Kong, Danilo Mandic
Neural Network Last Iterate Convergence Heavy Ball Momentum Method Gradient Momentum

January 20, 2022

Accelerated Gradient Flow: Risk, Stability, and Implicit Regularization
Yue Sheng, Alnur Ali
Optimization Purpose Core Stability High Quality Risk Description Implicit Regularization Accelerated Gradient Method Accelerated Gradient Heavy Ball

Heavy Ball

Papers

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

Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximation

Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance

(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum

Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise

Communication-Efficient Heterogeneous Federated Learning with Generalized Heavy-Ball Momentum

On the Effects of Data Heterogeneity on the Convergence Rates of Distributed Linear System Solvers

Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption

Implicit regularization in Heavy-ball momentum accelerated stochastic gradient descent

Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence

Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural Networks

Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-\L{}ojasiewicz Functions when the Non-Convexity is Averaged-Out

On the fast convergence of minibatch heavy ball momentum

Last-iterate convergence analysis of stochastic momentum methods for neural networks

Accelerated Gradient Flow: Risk, Stability, and Implicit Regularization