Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm

Abstract

In this paper, we study a method to sample from a target distribution $\pi$ over ${\mathbb{R}}^d$ having a positive density with respect to the Lebesgue measure, known up to a normalisation factor. This method is based on the Euler discretization of the overdamped Langevin stochastic differential equation associated with $\pi$. For both constant and decreasing step sizes in the Euler discretization, we obtain non-asymptotic bounds for the convergence to the target distribution $\pi$ in total variation distance. A particular attention is paid to the dependency on the dimension $d$, to demonstrate the applicability of this method in the high dimensional setting. These bounds improve and extend the results of (Dalalyan 2014).

Cited by in corpus (69)

• Sampling Can Be Faster Than Optimization
• Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling
• Is There an Analog of Nesterov Acceleration for MCMC?
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• On stochastic gradient Langevin dynamics with dependent data streams: the fully non-convex case
• Langevin Monte Carlo and JKO splitting
• Complexity Results for MCMC derived from Quantitative Bounds
• On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Accelerating Langevin Sampling with Birth-death
• Analysis of Langevin Monte Carlo via convex optimization
• Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
• Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex optimization
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Exponential ergodicity of mirror-Langevin diffusions
• Mean-Field Neural ODEs via Relaxed Optimal Control
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Neural Bridge Sampling for Evaluating Safety-Critical Autonomous Systems
• The reproducing Stein kernel approach for post-hoc corrected sampling
• Nonasymptotic analysis of Stochastic Gradient Hamiltonian Monte Carlo under local conditions for nonconvex optimization
• On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms
• Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Global Non-convex Optimization with Discretized Diffusions
• Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates
• Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
• Replica Exchange for Non-Convex Optimization
• Scaling limit of the Stein variational gradient descent: the mean field regime
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• Accelerating proximal Markov chain Monte Carlo by using an explicit stabilised method
• On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Efficient Bayesian reduced rank regression using Langevin Monte Carlo approach
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part II: Theoretical Analysis
• Dimension-free convergence rates for gradient Langevin dynamics in RKHS
• Sampling normalizing constants in high dimensions using inhomogeneous diffusions
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence
• Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
• Implicit Langevin Algorithms for Sampling From Log-concave Densities
• Markov Chain Monte Carlo Methods, a survey with some frequent misunderstandings
• KALE Flow: A Relaxed KL Gradient Flow for Probabilities with Disjoint Support
• Random Coordinate Langevin Monte Carlo
• The Mirror Langevin Algorithm Converges with Vanishing Bias
• Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Laplacian Smoothing Stochastic Gradient Markov Chain Monte Carlo
• An Introduction to Hamiltonian Monte Carlo Method for Sampling
• Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections
• Accelerating MCMC Algorithms
• A Decentralized Approach to Bayesian Learning
• An approximation to steady-state of M/Ph/n+M queue
• The query complexity of sampling from strongly log-concave distributions in one dimension
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks
• A Langevinized Ensemble Kalman Filter for Large-Scale Static and Dynamic Learning
• Approximation of heavy-tailed distributions via stable-driven SDEs
• Central limit theorem and Self-normalized Cramér-type moderate deviation for Euler-Maruyama Scheme
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations
• Convergence Analysis of Schr{ö}dinger-F{ö}llmer Sampler without Convexity
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo
• Higher Order Generalization Error for First Order Discretization of Langevin Diffusion
• Aggregated Gradient Langevin Dynamics
• Mirrored Langevin Dynamics