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

By Tianbao Yang, Qihang Lin, Zhe Li. 2016

131 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, background): “In [92] the authors analyzed mSGD for general Lipshitz continuous convex objective functions (with bounded variance) and proved the sublinear rateO(1/√k).”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, background): “Instead of considering a min-max problem, most of them contribute to the non-convex minimization problem [29, 70, 30, 63, 61, 44, 1, 2, 25, 24, 72, 24].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “In [206] the authors analyzed mSGD for general Lipshitz continuous convex objective functions (with bounded variance) and proved the sublinear rate O(1/ √ k).”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, result): “Yang et al. (2016) study the ASG method in the smooth strongly-convex setting, and show anO(1/ √ k) convergence rate when employed with a diminishing step-size and bounded gradient assumption, but the rates obtained are slower than those for SGD. Recent work establishes convergence guarantees for…”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, background): “[YLL16] provided a uniform analysis of SHB and accelerated stochastic gradient (ASG) showing O(1/ √ k) convergence rate for weakly convex stochastic optimization.”
Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data (2020, background): “The SGD, its momentum variants (Ghadimi and Lan (2013); Wright and Nocedal (1999); Wilson et al. (2016); Yang et al. (2016)), and its adaptive versions (AGMs) (Duchi et al. (2011); Kingma and Ba (2014); Zeiler (2012)) can readily distribute their computation to multiple processors due to their…”
Linearly convergent stochastic heavy ball method for minimizing generalization error (2017, background): “In [16] the authors analyzed SHB for general Lipshitz continuous convex objective functions (with bounded variance) and proved the sublinear rate O(1/ √ k).”
Stochastic Heavy ball (2016, background): “Finally, a recent work [YLL16] proposes a unified study of some stochastic momentum algorithms while assuming restrictive conditions on the noise of each gradient evaluation and on the constant step size used.”
Convergence Guarantees for RMSProp and ADAM in Non-Convex Optimization and an Empirical Comparison to Nesterov Acceleration (2018, background): “[45] Tianbao Yang, Qihang Lin, and Zhe Li.”
A Simple Convergence Proof of Adam and Adagrad (2020, unknown): “…values of N and β 1 , so that ˜ N ≈ N , and, In comparison, Theorem 3 by Yang et al. (2016) would give us, assuming now that α We observe an overall dependency in β 1 of the form O ((1 − β 1 ) − 2 ) for Theorem 3 by Yang et al. (2016) , which we improve to O ((1 − β 1 ) − 1 ) with our proof.”