Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis

By Maxim Raginsky, Alexander Rakhlin, Matus Telgarsky. Annual Conference Computational Learning Theory, 2017

592 citations recorded by the source corpus.

Stochastic Gradient Langevin Dynamics (SGLD) is a popular variant of Stochastic Gradient Descent, where properly scaled isotropic Gaussian noise is added to an unbiased estimate of the gradient at each iteration. This modest change allows SGLD to escape local minima and suffices to guarantee asymptotic convergence to global minimizers for sufficiently regular non-convex objectives (Gelfand and Mitter, 1991). The present work provides a nonasymptotic analysis in the context of non-convex learning problems, giving finite-time guarantees for SGLD to find approximate minimizers of both empirical and population risks. As in the asymptotic setting, our analysis relates the discrete-time SGLD Markov chain to a continuous-time diffusion process. A new tool that drives the results is the use of weighted transportation cost inequalities to quantify the rate of convergence of SGLD to a stationary distribution in the Euclidean $2$-Wasserstein distance.

Subfields: Computational Mechanics, Radiology, Nuclear Medicine and Imaging, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/83dfd3b0e077d816e9f7506dd12552c18bbdb790

How researchers see this paper

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

In Computational Mechanics

In Radiology, Nuclear Medicine and Imaging

In Statistics and Probability

Citations in the corpus

Underdamped Langevin MCMC: A non-asymptotic analysis (2017, background): “Recently [6, 7] also analyzed convergence of overdamped Langevin MCMC with stochastic gradient updates.”
Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization (2018, methodology): “In order to bound the second term A 2 , we follow a similar strategy to (Raginsky et al., 2017), where we use H 1 and the following moment condition on π θ .”
Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints (2017, methodology): “Note that almost all existing discretization techniques for Langevin Dynamics induce errors polynomial in dimension (Raginsky et al., 2017; Bubeck et al., 2015).”
User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient (2017, background): “For a more in-depth analysis of the SGLD, we refer the reader to (Nagapetyan et al., 2017; Raginsky et al., 2017; Xu et al., 2017).”
Generalized Energy Based Models (2020, background): “For large k,Zk is an approximate sample from ν (Raginsky et al., 2017, Proposition 3.3).”
Interplay Between Optimization and Generalization of Stochastic Gradient Descent with Covariance Noise (2019, methodology): “Recently, the uniform stability has been investigated for Stochastic Gradient methods (Hardt et al., 2015) and also for Stochastic Gradient Langevin Dynamics (SGLD) (Mou et al., 2017; Raginsky et al., 2017a).”
On Learning Rates and Schrödinger Operators (2020, background): “The gradient noise is drawn from standard normal . rates [Hwa80, RRT17, ZLC17].”
Stochastic Gradient Markov Chain Monte Carlo (2019, background): “Most of this theory assumes strong-convexity of the log-target density (see Raginsky, Rakhlin, and Telgarsky 2017; Majka, Mijatović, and Szpruch 2020, for similar theory under different assumptions), which means that there exists strictly positive constants, 0 < m ≤ M, such that for all θ , and θ…”
Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices (2019, background): “There is a close interplay between sampling and optimization, either via optimization as a limit of sampling (annealing) [34, 55], or via sampling as optimization in the space of distributions [36, 62].”
Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, background): “A promising avenue towards this is that for typical conditions in practice such as small mini-batches or large learning rates, SGD converges to the steady-state distribution quickly [59].”
Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, background): “Concurrently, there has been steady progress for noisy variants of SGD, such as stochastic gradient Langevin dynamics (SGLD) [13, 25, 33] and its full-batch counterpart, the Langevin algorithm [13].”
Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning (2019, methodology): “Lemma 1 still applies even if Assumption 4 is not satisﬁed.”
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors (2017, background): “Raginsky et al. (2017) give conditions that suffice to imply that SGLD converges in distribution.”
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (2017, methodology): “Our approach is different from existing analyses on Langevin dynamics [10, 12, 8, 30, 27], which connect LMC to a continuous-time Langevin diffusion process, then study the mixing time of the later process.”
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks (2019, background): “Recent results on ULA (Raginsky et al., 2017; Xu et al., 2018) have shown that, the required number of iterations to achieve the invariant measure often grows exponentially with the dimension p.”
A Unified and General Framework for Continual Learning (2024, background): “…for the previously learned tasks: Equation (23) is nearly identical to Equation (17), with the only distinction being that Equation (17) incorporates an additional random noise perturbation, which helps the CL model escape local minima Raginsky et al. (2017) and saddle point Ge et al. (2015).”