Continuous-time Models for Stochastic Optimization Algorithms
arXiv:1810.02565
Abstract
We propose new continuous-time formulations for first-order stochastic optimization algorithms such as mini-batch gradient descent and variance-reduced methods. We exploit these continuous-time models, together with simple Lyapunov analysis as well as tools from stochastic calculus, in order to derive convergence bounds for various types of non-convex functions. Guided by such analysis, we show that the same Lyapunov arguments hold in discrete-time, leading to matching rates. In addition, we use these models and Ito calculus to infer novel insights on the dynamics of SGD, proving that a decreasing learning rate acts as time warping or, equivalently, as landscape stretching.
arXiv comment33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada
References in corpus (23)
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- Guaranteed Matrix Completion via Non-convex Factorization
- Three Factors Influencing Minima in SGD
- Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
- Gradient Descent Learns Linear Dynamical Systems
- Non-convex Finite-Sum Optimization Via SCSG Methods
- A Lyapunov Analysis of Momentum Methods in Optimization
- Simple, Efficient, and Neural Algorithms for Sparse Coding
- Escaping Saddles with Stochastic Gradients
- Stop Wasting My Gradients: Practical SVRG
- Direct Runge-Kutta Discretization Achieves Acceleration
- Acceleration via Symplectic Discretization of High-Resolution Differential Equations
- Gradient methods for convex minimization: better rates under weaker conditions
- NAIS-Net: Stable Deep Networks from Non-Autonomous Differential Equations
- On Symplectic Optimization
- A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
- On the diffusion approximation of nonconvex stochastic gradient descent
- Coupling Adaptive Batch Sizes with Learning Rates
- The Physical Systems Behind Optimization Algorithms
- Shadowing Properties of Optimization Algorithms
- Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
- Differential Equations for Modeling Asynchronous Algorithms