Convergence of Langevin MCMC in KL-divergence

Abstract

Langevin diffusion is a commonly used tool for sampling from a given distribution. In this work, we establish that when the target density $p^{\ast }$ is such that $\log p^{\ast }$ is $L$ smooth and $m$ strongly convex, discrete Langevin diffusion produces a distribution $p$ with $KL(p||p^{\ast })\le \epsilon$ in $\tilde{O}(\frac{d}{\epsilon })$ steps, where $d$ is the dimension of the sample space. We also study the convergence rate when the strong-convexity assumption is absent. By considering the Langevin diffusion as a gradient flow in the space of probability distributions, we obtain an elegant analysis that applies to the stronger property of convergence in KL-divergence and gives a conceptually simpler proof of the best-known convergence results in weaker metrics.

Cited by in corpus (52)

• Sampling Can Be Faster Than Optimization
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Is There an Analog of Nesterov Acceleration for MCMC?
• A Tutorial on Thompson Sampling
• 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
• On stochastic gradient Langevin dynamics with dependent data streams: the fully non-convex case
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Langevin Monte Carlo and JKO splitting
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Analysis of Langevin Monte Carlo via convex optimization
• 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
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Exponential ergodicity of mirror-Langevin diffusions
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Wasserstein Control of Mirror Langevin Monte Carlo
• Langevin Monte Carlo without smoothness
• Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
• Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm
• Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
• Efficient constrained sampling via the mirror-Langevin algorithm
• On Thompson Sampling with Langevin Algorithms
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
• Schr{ö}dinger-F{ö}llmer Sampler: Sampling without Ergodicity
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence
• Implicit Langevin Algorithms for Sampling From Log-concave Densities
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence
• The Wasserstein Proximal Gradient Algorithm
• A Langevinized Ensemble Kalman Filter for Large-Scale Static and Dynamic Learning
• A Proximal Algorithm for Sampling from Non-smooth Potentials
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev
• Dimension-free Information Concentration via Exp-Concavity
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• A Decentralized Approach to Bayesian Learning
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• Stochastic Approximate Gradient Descent via the Langevin Algorithm
• Mirrored Langevin Dynamics
• Convergence Analysis of Schr{ö}dinger-F{ö}llmer Sampler without Convexity
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo