A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

By Yuchen Zhang, Percy Liang, Moses Charikar. 2017

249 citations recorded by the source corpus.

We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for non-convex optimization. The algorithm performs stochastic gradient descent, where in each step it injects appropriately scaled Gaussian noise to the update. We analyze the algorithm's hitting time to an arbitrary subset of the parameter space. Two results follow from our general theory: First, we prove that for empirical risk minimization, if the empirical risk is point-wise close to the (smooth) population risk, then the algorithm achieves an approximate local minimum of the population risk in polynomial time, escaping suboptimal local minima that only exist in the empirical risk. Second, we show that SGLD improves on one of the best known learnability results for learning linear classifiers under the zero-one loss.

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

An Alternative View: When Does SGD Escape Local Minima? (2018, background): “For example, it is proved that noise helps to escape saddle points [7, 16], gives better generalization [9, 23], and also guarantees polynomial hitting time of good local minima under some assumptions [29].”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, methodology): “The convergence rate in Corollary 2 matches the state-of-the-art convergence rate of SAA (Zhang et al., 2017a).”
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks (2019, background): “This conﬂict becomes clearer in the light of the recent works that studied the local behavior of ULA [51, 60].”
Demystifying Dropout (2019, background): “Besides, a number of works (Ge et al., 2015; Jin et al., 2017; Zhang et al., 2017; Daneshmand et al., 2018) have theoretically justified that noise does be helpful for SGD to escape from saddle points.”
A Diffusion Theory For Minima Selection: Stochastic Gradient Descent Escapes Sharp Minima Exponentially Fast (2020, background): “arameters themselves. The density diffusion process of Stochastic Gradient Langevin Dynamics Preprint. Under review. (SGLD) has been well discussed by (Sato and Nakagawa, 2014; Raginsky et al., 2017; Zhang et al., 2017b; Xu et al., 2018). Wu et al. (2018) has studied the escape problems of SGD from ”
Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? (2018, background): “Other types of non-convex functions exist for which variants of SGD would converge to local optima (Zhang et al., 2017).”
On Learning Rates and Schrödinger Operators (2020, background): “The gradient noise is drawn from standard normal . rates [Hwa80, RRT17, ZLC17].”
Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints (2017, background): “Though the mixing time can be prohibitive in non-convex case, Zhang et al. (2017) recently show that hitting time of SGLD for small-loss region can be much better, and the Gaussian noise in SGLD helps to escape shallow local minima.”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects (2018, background): “This indicates that it is not sufficient to analyze SGD by treating it as an isotropic diffusion over landscape (Zhang et al., 2017; Mou et al., 2017).”
Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning (2019, methodology): “SG-MCMC with the traditional decreasing stepsize schedule in practice becomes trapped in a local mode, though injecting noise may help the sampler to escape in the asymptotic regime (Zhang et al., 2017).”
Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization (2018, background): “…hand, Theorem 1 does not guarantee that the proposed algorithm will converge to a neighborhood of a local minimum; however, we believe that we can also prove local convergence guarantees by us-ing the techniques provided in (Zhang et al., 2017; Tzen et al., 2018), which we leave as a future work.”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, background): “Noisy SGD [5] IFO ( , )-SSP, high probability Õ (Tgd −p) SGLD [23] IFO ( , )-SSP, high probability Õ ( Tgd p −4 )”
Escaping Saddles with Stochastic Gradients (2018, background): “1-factor compared to the best known convergence rate for perturbed SGD established by (Zhang et al., 2017), which requires O(d −4) iterations for an ( , )second-order stationary point.”