On the diffusion approximation of nonconvex stochastic gradient descent

By Wenqing Hu, Chris Junchi Li, Lei Li, Jian‐Guo Liu. 2017

157 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Don't Use Large Mini-Batches, Use Local SGD (2018, background): “The variance matrix Σpwq, following recent works [18, 19], for uniform sampling of mini-batch indices can be approximated as Σpwq « ` 1 B ́ 1 N ̆”
Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks (2019, background): “There are a number of works theoretically characterizing this particular noise distribution [19, 18, 38], and we leave analysis of this setting to future work.”
Interplay Between Optimization and Generalization of Stochastic Gradient Descent with Covariance Noise (2019, background): “The covariance of δ k is given by This result can be found in Hu et al. (2017); Hoffer et al. (2017).”
Understanding the acceleration phenomenon via high-resolution differential equations (2018, background): “[HLLL17] Wenqing Hu, Chris Junchi Li, Lei Li, and Jian-Guo Liu.”
A Diffusion Theory For Minima Selection: Stochastic Gradient Descent Escapes Sharp Minima Exponentially Fast (2020, result): “itative conclusions on batch size, learning rate, and sharpness. Zhu et al. (2019) reveals that anisotropic diffusion of SGD leads to ﬂat minima qualitatively better than isotropic diffusion of SGLD. Hu et al. (2019) quantitatively shows that the mean escape time of SGD exponentially depends on inve”
An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise (2019, unknown): “The covariance of δk is given by N −M M 1 N N∑ i=1 (∇L(θk)−∇`i(θk)) (∇L(θk)−∇`i(θk))> (3) This result can be found in Hu et al. (2017); Hoffer et al. (2017).”
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks (2019, methodology): “From this perspective, the SGD recursion in (5) can be seen as a first-order Euler-Maruyama discretization of the Langevin dynamics (see also (Li et al., 2017; Jastrzebski et al., 2017; Hu et al., 2017)), which is often referred to as the Unadjusted Langevin Algorithm (ULA) (Roberts & Stramer, 2002;”
Trainability and Accuracy of Artificial Neural Networks: An Interacting Particle System Approach (2018, background): “f f ; i ; j /dt: More precisely, [19, 25]: LEMMA 4.”
A Diffusion Theory for Deep Learning Dynamics: Stochastic Gradient Descent Escapes From Sharp Minima Exponentially Fast (2020, background): “Hu et al. (2019) theoretically shows that the escape dynamics of SGD exponentially depends on the inverse learning rate without direct empirical evidence of the exponential relation.”
Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability (2021, background): “…ensure that stability properties in expectation remain identical to those of a well-tuned implementation of synchronous SGD. Finally, a number of papers have attempted to mathematically model the propensity of SGD to “escape from sharp minima” (Hu et al., 2017; Zhu et al., 2019; Xie et al., 2021).”
Neural Networks as Interacting Particle Systems: Asymptotic Convexity of the Loss Landscape and Universal Scaling of the Approximation Error (2018, unknown): “Then we have [14,20] Proposition 3.1.”
Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks (2018, unknown): “In doing so, we give an exact rewriting of stochastic gradient descent as a stochastic differential equation with multiplicative noise, which has been studied previously [18, 19].”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Minima and Regularization Effects (2018, background): “In non-convex settings, the characterization of how SGD escapes from stationary points, including saddle points and local minima, was analyzed in [4, 10, 8].”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects (2018, background): “In non-convex settings, the characterization of how SGD escapes from stationary points, including saddle points and local minima, was analyzed in (Daneshmand et al., 2018; Jin et al., 2017; Hu et al., 2017).”