On the diffusion approximation of nonconvex stochastic gradient descent

Abstract

We study the Stochastic Gradient Descent (SGD) method in nonconvex optimization problems from the point of view of approximating diffusion processes. We prove rigorously that the diffusion process can approximate the SGD algorithm weakly using the weak form of master equation for probability evolution. In the small step size regime and the presence of omnidirectional noise, our weak approximating diffusion process suggests the following dynamics for the SGD iteration starting from a local minimizer (resp.~saddle point): it escapes in a number of iterations exponentially (resp.~almost linearly) dependent on the inverse stepsize. The results are obtained using the theory for random perturbations of dynamical systems (theory of large deviations for local minimizers and theory of exiting for unstable stationary points). In addition, we discuss the effects of batch size for the deep neural networks, and we find that small batch size is helpful for SGD algorithms to escape unstable stationary points and sharp minimizers. Our theory indicates that one should increase the batch size at later stage for the SGD to be trapped in flat minimizers for better generalization.

References in corpus (7)

• The Loss Surfaces of Multilayer Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• A Variational Perspective on Accelerated Methods in Optimization
• Train longer, generalize better: closing the generalization gap in large batch training of neural networks
• How to Escape Saddle Points Efficiently
• Deep Learning without Poor Local Minima
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization

Cited by in corpus (18)

• Don't Use Large Mini-Batches, Use Local SGD
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Fluctuation-dissipation relations for stochastic gradient descent
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Non-Gaussianity of Stochastic Gradient Noise
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Stochastic Training of Residual Networks: a Differential Equation Viewpoint
• An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• A convergence analysis of the perturbed compositional gradient flow: averaging principle and normal deviations
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• Borrowing From the Future: Addressing Double Sampling in Model-free Control
• Semi-groups of stochastic gradient descent and online principal component analysis: properties and diffusion approximations
• Continuous-time Models for Stochastic Optimization Algorithms
• Borrowing From the Future: An Attempt to Address Double Sampling
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization