Non-ergodic Convergence Analysis of Heavy-Ball Algorithms
Not on the map. Why?
Abstract (arXiv)
In this paper, we revisit the convergence of the Heavy-ball method, and present improved convergence complexity results in the convex setting. We provide the first non-ergodic O(1/k) rate result of the Heavy-ball algorithm with constant step size for coercive objective functions. For objective functions satisfying a relaxed strongly convex condition, the linear convergence is established under weaker assumptions on the step size and inertial parameter than made in the existing literature. We extend our results to multi-block version of the algorithm with both the cyclic and stochastic update rules. In addition, our results can also be extended to decentralized optimization, where the ergodic analysis is not applicable.
Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). First posted on arXiv 5 Nov 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 6; 2022: 1; 2023: 2; 2024: 1; 2025: 0; 2026: 4.
14 papers.
Sort:
- 2021Decentralized Federated Averagingcited by 114
- 2021Does Momentum Change the Implicit Regularization on Separable Data?cited by 22
- 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 14
- 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 14
- 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
- 2021Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimizationcited by 8
- 2021The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methodscited by 7
- 2021Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problemscited by 5
- 2023Blockchain-Based Federated Learning: Incentivizing Data Sharing and Penalizing Dishonest Behaviorcited by 5
- 2026Unified convergence analysis for gradient descent optimization methods in the training of deep neural networkscited by 1
- 2022DRSOM: A Dimension Reduced Second-Order Methodcited by 0
- 2026A Lower Bound for the Heavy-Ball Method on Smooth Convex Functionscited by 0
- 2026Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis29 Sep 2026
- 2026Continuous Optimization for p-adic Models21 Sep 2026
- 2026A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions8 Sep 2026
- 2026Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks5 Jul 2026
- 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond22 Mar 2024
- 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case20 Jul 2023
- 2023Blockchain-Based Federated Learning: Incentivizing Data Sharing and Penalizing Dishonest Behavior19 Jul 2023
- 2022DRSOM: A Dimension Reduced Second-Order Method30 Jul 2022
- 2021Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization18 Oct 2021
- 2021Does Momentum Change the Implicit Regularization on Separable Data?8 Oct 2021
- 2021Escaping Saddle Points Faster with Stochastic Momentum5 Jun 2021
- 2021Decentralized Federated Averaging23 Apr 2021
- 2021Decentralized Federated Averagingcited by 114
- 2021Does Momentum Change the Implicit Regularization on Separable Data?cited by 22
- 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 14
- 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 14
- 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
- 2021Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimizationcited by 8
- 2021The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methodscited by 7
- 2021Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problemscited by 5
- 2023Blockchain-Based Federated Learning: Incentivizing Data Sharing and Penalizing Dishonest Behaviorcited by 5
- 2026Unified convergence analysis for gradient descent optimization methods in the training of deep neural networkscited by 1
- 2022DRSOM: A Dimension Reduced Second-Order Methodcited by 0
- 2026A Lower Bound for the Heavy-Ball Method on Smooth Convex Functionscited by 0
12 most cited of 14 All 14 (JSON)
- 2026Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis29 Sep 2026
- 2026Continuous Optimization for p-adic Models21 Sep 2026
- 2026A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions8 Sep 2026
- 2026Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks5 Jul 2026
- 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond22 Mar 2024
- 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case20 Jul 2023
- 2023Blockchain-Based Federated Learning: Incentivizing Data Sharing and Penalizing Dishonest Behavior19 Jul 2023
- 2022DRSOM: A Dimension Reduced Second-Order Method30 Jul 2022
- 2021Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization18 Oct 2021
- 2021Does Momentum Change the Implicit Regularization on Separable Data?8 Oct 2021
- 2021Escaping Saddle Points Faster with Stochastic Momentum5 Jun 2021
- 2021Decentralized Federated Averaging23 Apr 2021
12 newest of 14 All 14 (JSON)