Underdamped Langevin MCMC: A non-asymptotic analysis

Abstract

We study the underdamped Langevin diffusion when the log of the target distribution is smooth and strongly concave. We present a MCMC algorithm based on its discretization and show that it achieves $\epsilon$ error (in 2-Wasserstein distance) in $\mathcal{O}(\sqrt{d}/\epsilon )$ steps. This is a significant improvement over the best known rate for overdamped Langevin MCMC, which is $\mathcal{O}(d/{\epsilon }^2)$ steps under the same smoothness/concavity assumptions. The underdamped Langevin MCMC scheme can be viewed as a version of Hamiltonian Monte Carlo (HMC) which has been observed to outperform overdamped Langevin MCMC methods in a number of application areas. We provide quantitative rates that support this empirical wisdom.

arXiv comment23 pages; Correction to Corollary 7

References in corpus (7)

• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• A Complete Recipe for Stochastic Gradient MCMC
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Couplings and quantitative contraction rates for Langevin dynamics
• Wasserstein contraction properties for hypoelliptic diffusions
• Exponential stability of slowly decaying solutions to the kinetic Fokker-Planck equation

Cited by in corpus (66)

• On the Random Batch Method for second order interacting particle systems
• Sampling Can Be Faster Than Optimization
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Coupling and Convergence for Hamiltonian Monte Carlo
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• 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
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Invertible Particle Flow-based Sequential MCMC with extension to Gaussian Mixture noise models
• Complexity of randomized algorithms for underdamped Langevin dynamics
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• Exponential ergodicity of mirror-Langevin diffusions
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• Couplings for Andersen Dynamics
• Wasserstein Control of Mirror Langevin Monte Carlo
• Langevin Monte Carlo without smoothness
• Nonasymptotic analysis of Stochastic Gradient Hamiltonian Monte Carlo under local conditions for nonconvex optimization
• Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
• Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie
• Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates
• Efficient constrained sampling via the mirror-Langevin algorithm
• Replica Exchange for Non-Convex Optimization
• On the Generalised Langevin Equation for Simulated Annealing
• Random batch methods (RBM) for interacting particle systems
• Constraint-Based Regularization of Neural Networks
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Uniform minorization condition and convergence bounds for discretizations of kinetic Langevin dynamics
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Stochastic gradient descent and fast relaxation to thermodynamic equilibrium: a stochastic control approach
• Generalized Energy Based Models
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence
• Acceleration and Averaging in Stochastic Mirror Descent Dynamics
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Implicit Langevin Algorithms for Sampling From Log-concave Densities
• Accelerated Flow for Probability Distributions
• Random Coordinate Underdamped Langevin Monte Carlo
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• A Unifying and Canonical Description of Measure-Preserving Diffusions
• The shifted ODE method for underdamped Langevin MCMC
• Ergodicity of the underdamped mean-field Langevin dynamics
• A Decentralized Approach to Bayesian Learning
• Non-asymptotic error bounds for scaled underdamped Langevin MCMC
• Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
• A Proximal Algorithm for Sampling from Non-smooth Potentials
• Piecewise deterministic sampling with splitting schemes
• Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited
• Mirrored Langevin Dynamics
• Distribution-Dependent Analysis of Gibbs-ERM Principle
• Stochastic Gradient Langevin with Delayed Gradients
• Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations
• Sharp spectral gap of adaptive Langevin dynamics
• Stochastic Approximate Gradient Descent via the Langevin Algorithm