Underdamped Langevin MCMC: A non-asymptotic analysis

2017/07/12 by Xiang Cheng, Cheng, Xiang, Niladri S. Chatterji +5 · 22 citations
Mathematics · Medicine · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Advanced Neuroimaging Techniques and Applications #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.1707.03663

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 ε error (in 2-Wasserstein distance) in O(√(d)/ε) steps. This is a significant improvement over the best known rate for overdamped Langevin MCMC, which is O(d/ε²) 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.

Citations

• Convergence of Langevin MCMC in KL-divergence

Cited by

• A Critical Review of Monte Carlo Algorithms Balancing Performance and Probabilistic Accuracy with AI Augmented Framework
• Weighted Stochastic Differential Equation to Implement Wasserstein-Fisher-Rao Gradient Flow
• Fast Riemannian-manifold Hamiltonian Monte Carlo for hierarchical Gaussian-process models
• Ergodicity of the underdamped mean-field Langevin dynamics
• Mirrored Langevin Dynamics
• Wasserstein Control of Mirror Langevin Monte Carlo
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• A Non-asymptotic Analysis for Learning and Applying a Preconditioner in MCMC
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Next-Generation AI-Native Wireless Communications: MCMC-Based Receiver Architectures for Unified Processing
• An Inertial Langevin Algorithm
• Almost sure contraction for diffusions on \mathbb R^d. Application to generalised Langevin diffusions
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly\n Logconcave Distributions
• Contractive kinetic Langevin samplers beyond global Lipschitz continuity
• An explicit splitting SAV scheme for the kinetic Langevin dynamics
• Regime-Switching Langevin Monte Carlo Algorithms
• Sampling by averaging: A multiscale approach to score estimation
• A general perspective on CBO methods with stochastic rate of information
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Stochastic Approximate Gradient Descent via the Langevin Algorithm
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave\n Densities
• Do we need equivariant models for molecule generation?

Related

• Underdamped Langevin MCMC with third order convergence
• Underdamped Langevin MCMC with third order convergence
• The shifted ODE method for underdamped Langevin MCMC
• Improved Discretization Analysis for Underdamped Langevin Monte Carlo
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm