The Role of Memory in Stochastic Optimization

Abstract

The choice of how to retain information about past gradients dramatically affects the convergence properties of state-of-the-art stochastic optimization methods, such as Heavy-ball, Nesterov's momentum, RMSprop and Adam. Building on this observation, we use stochastic differential equations (SDEs) to explicitly study the role of memory in gradient-based algorithms. We first derive a general continuous-time model that can incorporate arbitrary types of memory, for both deterministic and stochastic settings. We provide convergence guarantees for this SDE for weakly-quasi-convex and quadratically growing functions. We then demonstrate how to discretize this SDE to get a flexible discrete-time algorithm that can implement a board spectrum of memories ranging from short- to long-term. Not only does this algorithm increase the degrees of freedom in algorithmic choice for practitioners but it also comes with better stability properties than classical momentum in the convex stochastic setting. In particular, no iterate averaging is needed for convergence. Interestingly, our analysis also provides a novel interpretation of Nesterov's momentum as stable gradient amplification and highlights a possible reason for its unstable behavior in the (convex) stochastic setting. Furthermore, we discuss the use of long term memory for second-moment estimation in adaptive methods, such as Adam and RMSprop. Finally, we provide an extensive experimental study of the effect of different types of memory in both convex and nonconvex settings.

arXiv commentAccepted paper at the 35th Conference on Uncertainty in Artificial Intelligence (UAI), Tel Aviv, 2019

References in corpus (7)

• On the Convergence of Adam and Beyond
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Gradient Descent Learns Linear Dynamical Systems
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• Direct Runge-Kutta Discretization Achieves Acceleration
• The Physical Systems Behind Optimization Algorithms

Cited by in corpus (5)

• Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers
• On the Generalization of Stochastic Gradient Descent with Momentum
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models