Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization (2020-10-01T00:00:00.000000Z)

TL;DR

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, which is much tighter than previous theory in the non-convex case.

Abstract

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.

Authors

Aaron Defazio

6 papers

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

TL;DR

Abstract

Authors

References28 items

An Improved Analysis of Stochastic Gradient Descent with Momentum

On the convergence of the Stochastic Heavy Ball Method

Factorial Powers for Stochastic Optimization

Convergence of a Stochastic Gradient Method with Momentum for Nonsmooth Nonconvex Optimization

Momentum Improves Normalized SGD

Primal Averaging: A New Gradient Evaluation Step to Attain the Optimal Individual Convergence

On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization

Making the Last Iterate of SGD Information Theoretically Optimal

Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances

On the Curved Geometry of Accelerated Optimization

A Unified Analysis of Stochastic Momentum Methods for Deep Learning

On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization

Stochastic Heavy ball

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

On the influence of momentum acceleration on online learning

From Averaging to Acceleration, There is Only a Step-size

Global convergence of the Heavy-ball method for convex optimization

ImageNet Large Scale Visual Recognition Challenge

Introductory Lectures on Convex Optimization - A Basic Course

Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

On the importance of initialization and momentum in deep learning

Acceler-ating stochastic gradient descent for least squares regression

Adaptive Averaging in Accelerated Descent Dynamics

Learning Multiple Layers of Features from Tiny Images

Some methods of speeding up the convergence of iteration methods

c k is increased 10 fold,

e) As we show in Section 5, the most theoretically motivated choice is to actually change both η k and c k . This unfortunately also results in a spike in α k

(c) When η k is decreased 10 fold, a spike occurs in β k , after which α k drops 10 fold and β k drops back to it’s earlier value

Field of Study