Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

Abstract

We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution $\nu =e^{-f}$ on ${\mathbb{R}}^n$. We prove a convergence guarantee in Kullback-Leibler (KL) divergence assuming $\nu$ satisfies a log-Sobolev inequality and the Hessian of $f$ is bounded. Notably, we do not assume convexity or bounds on higher derivatives. We also prove convergence guarantees in Rényi divergence of order $q>1$ assuming the limit of ULA satisfies either the log-Sobolev or Poincaré inequality. We also prove a bound on the bias of the limiting distribution of ULA assuming third-order smoothness of $f$, without requiring isoperimetry.

v4: Updated discussion and added properties of biased limit v3: Simplified analysis of Rényi divergence, improved exposition, and added figures v2: Added analysis of Rényi divergence and Poincaré assumption

Cited by in corpus (26)

• A Non-Asymptotic Analysis for Stein Variational Gradient Descent
• Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Exponential ergodicity of mirror-Langevin diffusions
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm
• On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Efficient constrained sampling via the mirror-Langevin algorithm
• On Thompson Sampling with Langevin Algorithms
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence
• Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• The Mirror Langevin Algorithm Converges with Vanishing Bias
• Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
• Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
• Sampling From the Wasserstein Barycenter
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence
• The Wasserstein Proximal Gradient Algorithm
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev
• Privacy-Aware Rejection Sampling
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• A Decentralized Approach to Bayesian Learning
• Neural Variational Gradient Descent