Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization

Abstract

Recently, {\it stochastic momentum} methods have been widely adopted in training deep neural networks. However, their convergence analysis is still underexplored at the moment, in particular for non-convex optimization. This paper fills the gap between practice and theory by developing a basic convergence analysis of two stochastic momentum methods, namely stochastic heavy-ball method and the stochastic variant of Nesterov's accelerated gradient method. We hope that the basic convergence results developed in this paper can serve the reference to the convergence of stochastic momentum methods and also serve the baselines for comparison in future development of stochastic momentum methods. The novelty of convergence analysis presented in this paper is a unified framework, revealing more insights about the similarities and differences between different stochastic momentum methods and stochastic gradient method. The unified framework exhibits a continuous change from the gradient method to Nesterov's accelerated gradient method and finally the heavy-ball method incurred by a free parameter, which can help explain a similar change observed in the testing error convergence behavior for deep learning. Furthermore, our empirical results for optimizing deep neural networks demonstrate that the stochastic variant of Nesterov's accelerated gradient method achieves a good tradeoff (between speed of convergence in training error and robustness of convergence in testing error) among the three stochastic methods.

arXiv commentAdded some references and more empirical results

References in corpus (2)

• Stochastic Variance Reduction for Nonconvex Optimization
• Global convergence of the Heavy-ball method for convex optimization

Cited by in corpus (40)

• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Faster On-Device Training Using New Federated Momentum Algorithm
• A Simple Convergence Proof of Adam and Adagrad
• Adaptive Gradient Quantization for Data-Parallel SGD
• Linearly convergent stochastic heavy ball method for minimizing generalization error
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Differentially Private Accelerated Optimization Algorithms
• A High Probability Analysis of Adaptive SGD with Momentum
• Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data
• Convergence Analysis of Optimization Algorithms
• On the Generalization of Stochastic Gradient Descent with Momentum
• On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
• Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions
• Stochastic Heavy Ball
• Escaping Saddle Points Faster with Stochastic Momentum
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization
• The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods
• Provable Smoothness Guarantees for Black-Box Variational Inference
• A Stochastic Derivative Free Optimization Method with Momentum
• MixML: A Unified Analysis of Weakly Consistent Parallel Learning
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization
• Understanding and Detecting Convergence for Stochastic Gradient Descent with Momentum
• Training Generative Adversarial Networks with Adaptive Composite Gradient
• Large Batch Training Does Not Need Warmup
• Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems
• A Rule for Gradient Estimator Selection, with an Application to Variational Inference
• Variance-Reduced Accelerated First-order Methods: Central Limit Theorems and Confidence Statements
• AutoDrop: Training Deep Learning Models with Automatic Learning Rate Drop
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• On the Last Iterate Convergence of Momentum Methods
• Accelerate Distributed Stochastic Descent for Nonconvex Optimization with Momentum
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Rapidly Adapting Moment Estimation
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network