High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm

Abstract

We propose a Markov chain Monte Carlo (MCMC) algorithm based on third-order Langevin dynamics for sampling from distributions with log-concave and smooth densities. The higher-order dynamics allow for more flexible discretization schemes, and we develop a specific method that combines splitting with more accurate integration. For a broad class of $d$-dimensional distributions arising from generalized linear models, we prove that the resulting third-order algorithm produces samples from a distribution that is at most $\epsilon >0$ in Wasserstein distance from the target distribution in $O\left(\frac{d^{1/4}}{{\epsilon }^{1/2}}\right)$ steps. This result requires only Lipschitz conditions on the gradient. For general strongly convex potentials with $\alpha$-th order smoothness, we prove that the mixing time scales as $O\left(\frac{d^{1/4}}{{\epsilon }^{1/2}}+\frac{d^{1/2}}{{\epsilon }^{1/(\alpha -1)}}\right)$.

arXiv commentChanges from v1: improved algorithm with $O(d^{1/4}/{\epsilon }^{1/2})$ mixing time

References in corpus (10)

• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Sampling Can Be Faster Than Optimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Convergence of Langevin MCMC in KL-divergence
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• The Randomized Midpoint Method for Log-Concave Sampling
• Complexity of randomized algorithms for underdamped Langevin dynamics
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities

Cited by in corpus (12)

• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
• Accurate and robust splitting methods for the generalized Langevin equation with a positive Prony series memory kernel
• On the Generalised Langevin Equation for Simulated Annealing
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• A Decentralized Approach to Bayesian Learning
• Quasi-symplectic Langevin Variational Autoencoder
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo