A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

Abstract

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.

Correct two mistakes in the proofs of Lemma 3 and Lemma 5

References in corpus (2)

• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Efficient Learning of Linear Separators under Bounded Noise

Cited by in corpus (31)

• Escaping Saddles with Stochastic Gradients
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• An Alternative View: When Does SGD Escape Local Minima?
• Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Smoothed Geometry for Robust Attribution
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Learning with Non-Convex Truncated Losses by SGD
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
• The Impact of Local Geometry and Batch Size on Stochastic Gradient Descent for Nonconvex Problems
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
• Dimension-free convergence rates for gradient Langevin dynamics in RKHS
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Fast Convergence for Langevin Diffusion with Manifold Structure
• Stochastic Non-convex Optimization with Strong High Probability Second-order Convergence
• Information Theoretic Interpretation of Deep learning
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• SVGD: A Virtual Gradients Descent Method for Stochastic Optimization
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
• Not-So-Random Features
• Is the Skip Connection Provable to Reform the Neural Network Loss Landscape?