2020

Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization

Defazio, Aaron

Understand

Momentum methods are now used pervasively within the machine learning community for training non-convex models such as deep neural networks.

Empirically, they out perform traditional stochastic gradient descent (SGD) approaches.
In this work we develop a Lyapunov analysis of SGD with momentum (SGD+M), by utilizing a equivalent rewriting of the method known as the stochastic primal averaging (SPA) form.
This analysis is much tighter than previous theory in the non-convex case, and due to this we are able to give precise insights into when SGD+M may out-perform SGD, and what hyper-parameter schedules will work and why.

Some methods of speeding up the convergence of iteration methods
B. T. Polyak · 1964
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Alex Krizhevsky · 2009
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course , volume 87
Yurii Nesterov · 2013
Earlier work this paper cites.
On the importance of initialization and momentum in deep learning
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton · 2013
Earlier work this paper cites.
Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm
Deanna Needell, Rachel Ward, and Nati Srebro · 2014
Earlier work this paper cites.
From averaging to acceleration, there is only a step-size
Nicolas Flammarion and Francis Bach · 2015
Earlier work this paper cites.
Global convergence of the heavy-ball method for convex optimization
Euhanna Ghadimi, Hamid Feyzmahdavian, and Mikael Johansson · 2015
Earlier work this paper cites.
ImageNet Large Scale Visual Recognition Challenge
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei · 2015
Earlier work this paper cites.
Adaptive averaging in accelerated descent dynamics
Walid Krichene, Alexandre Bayen, and Peter L Bartlett · 2016
Earlier work this paper cites.

Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization
Tianbao Yang, Qihang Lin, and Zhe Li · 2016
Cited alongside, same era.
On the influence of momentum acceleration on online learning
Kun Yuan, Bicheng Ying, and Ali H. Sayed · 2016
Cited alongside, same era.
Stochastic heavy ball
Sébastien Gadat, Fabien Panloup, and Sofiane Saadane · 2018
Cited alongside, same era.
Accelerating stochastic gradient descent for least squares regression
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford · 2018
Cited alongside, same era.
On the insufficiency of existing momentum schemes for stochastic optimization
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M. Kakade · 2018
Cited alongside, same era.
A unified analysis of stochastic momentum methods for deep learning
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang · 2018
Cited alongside, same era.
Accelerated linear convergence of stochastic momentum methods in wasserstein distances
Bugra Can, Mert Gürbüzbalaban, and Lingjiong Zhu · 2019
Cited alongside, same era.
On the curved geometry of accelerated optimization
Aaron Defazio · 2019
Cited alongside, same era.

Making the last iterate of sgd information theoretically optimal
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli · 2019
Later among the works it cites.
Momentum improves normalized sgd
Ashok Cutkosky and Harsh Mehta · 2020
Closest in time.
Factorial powers for stochastic optimization
Aaron Defazio and Robert M. Gower · 2020
Closest in time.
An improved analysis of stochastic gradient descent with momentum
Yanli Liu, Yuan Gao, and Wotao Yin · 2020
Closest in time.
Convergence of a stochastic gradient method with momentum for non-smooth non-convex optimization
Vien V. Mai and Mikael Johansson · 2020
Closest in time.
On the convergence of the stochastic heavy ball method
Othmane Sebbouh, Robert M. Gower, and Aaron Defazio · 2020
Closest in time.
Primal averaging: A new gradient evaluation step to attain the optimal individual convergence
W. Tao, Z. Pan, G. Wu, and Q. Tao · 2020
Closest in time.
On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization
Hao Yu, Rong Jin, and Sen Yang · 2020
Closest in time.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…