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

Abstract

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.

29 pages

References in corpus (1)

• Transportation cost-information inequalities and applications to random dynamical systems and diffusions

Cited by in corpus (78)

• The Marginal Value of Adaptive Gradient Methods in Machine Learning
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Sampling Can Be Faster Than Optimization
• Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning
• Underdamped Langevin MCMC: A non-asymptotic analysis
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Significance tests of feature relevance for a black-box learner
• Uncertainty in Gradient Boosting via Ensembles
• On the different regimes of Stochastic Gradient Descent
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• On stochastic gradient Langevin dynamics with dependent data streams: the fully non-convex case
• Non-Gaussianity of Stochastic Gradient Noise
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• Analysis of Langevin Monte Carlo via convex optimization
• Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Some models are useful, but how do we know which ones? Towards a unified Bayesian model taxonomy
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Exponential ergodicity of mirror-Langevin diffusions
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• Langevin Monte Carlo without smoothness
• An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
• Global Non-convex Optimization with Discretized Diffusions
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
• Replica Exchange for Non-Convex Optimization
• AMAGOLD: Amortized Metropolis Adjustment for Efficient Stochastic Gradient MCMC
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms
• SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems
• On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
• Theory III: Dynamics and Generalization in Deep Networks
• Statistical Estimation of the Poincar{é} constant and Application to Sampling Multimodal Distributions
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
• Generalized Energy Based Models
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• Acceleration and Averaging in Stochastic Mirror Descent Dynamics
• Fast Convergence for Langevin Diffusion with Manifold Structure
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Dimension-free convergence rates for gradient Langevin dynamics in RKHS
• Mini-batch Metropolis-Hastings MCMC with Reversible SGLD Proposal
• StochasticRank: Global Optimization of Scale-Free Discrete Functions
• SGLB: Stochastic Gradient Langevin Boosting
• Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
• Stochastic Gradient Langevin Dynamics Algorithms with Adaptive Drifts
• Statistical Inference with Local Optima
• SaaS: Speed as a Supervisor for Semi-supervised Learning
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• A fully data-driven approach to minimizing CVaR for portfolio of assets via SGLD with discontinuous updating
• Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning
• Information Theoretic Interpretation of Deep learning
• Data-Adaptive Discriminative Feature Localization with Statistically Guaranteed Interpretation
• A Unifying and Canonical Description of Measure-Preserving Diffusions
• Empirical bounds for functions with weak interactions
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
• Efficient Multimodal Sampling via Tempered Distribution Flow
• Stochastic Gradient Langevin with Delayed Gradients
• Continuous-time Models for Stochastic Optimization Algorithms
• A Functional Perspective on Learning Symmetric Functions with Neural Networks
• Adaptive Non-reversible Stochastic Gradient Langevin Dynamics
• Aggregated Gradient Langevin Dynamics
• Efficient Reinforced Feature Selection via Early Stopping Traverse Strategy
• One-dimensional System Arising in Stochastic Gradient Descent
• Convergence Analysis of Schr{ö}dinger-F{ö}llmer Sampler without Convexity
• The Effects of Invertibility on the Representational Complexity of Encoders in Variational Autoencoders
• Distribution-Dependent Analysis of Gibbs-ERM Principle