Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions

Abstract

We obtain several quantitative bounds on the mixing properties of the Hamiltonian Monte Carlo (HMC) algorithm for a strongly log-concave target distribution $\pi$ on ${\mathbb{R}}^d$, showing that HMC mixes quickly in this setting. One of our main results is a dimension-free bound on the mixing of an "ideal" HMC chain, which is used to show that the usual leapfrog implementation of HMC can sample from $\pi$ using only $\mathcal{O}(d^{\frac{1}{4}})$ gradient evaluations. This dependence on dimension is sharp, and our results significantly extend and improve previous quantitative bounds on the mixing of HMC.

References in corpus (2)

• On the Geometric Ergodicity of Hamiltonian Monte Carlo
• On the convergence of Hamiltonian Monte Carlo

Cited by in corpus (38)

• Sampling Can Be Faster Than Optimization
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• NeuTra-lizing Bad Geometry in Hamiltonian Monte Carlo Using Neural Transport
• Coupling and Convergence for Hamiltonian Monte Carlo
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Is There an Analog of Nesterov Acceleration for MCMC?
• Unbiased Markov chain Monte Carlo with couplings
• Stacking for Non-mixing Bayesian Computations: The Curse and Blessing of Multimodal Posteriors
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo
• Complexity Results for MCMC derived from Quantitative Bounds
• Convergence of unadjusted Hamiltonian Monte Carlo for mean-field models
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Accelerating Langevin Sampling with Birth-death
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Does Hamiltonian Monte Carlo mix faster than a random walk on multimodal densities?
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Neural Bridge Sampling for Evaluating Safety-Critical Autonomous Systems
• Couplings for Andersen Dynamics
• Langevin Monte Carlo without smoothness
• Estimating Convergence of Markov chains with L-Lag Couplings
• Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
• Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
• Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
• An approach to large-scale Quasi-Bayesian inference with spike-and-slab priors
• Simple Conditions for Metastability of Continuous Markov Chains
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• Recycling intermediate steps to improve Hamiltonian Monte Carlo
• An Introduction to Hamiltonian Monte Carlo Method for Sampling
• Couplings for Multinomial Hamiltonian Monte Carlo
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Entropy-based adaptive Hamiltonian Monte Carlo
• Hamiltonian Monte Carlo Swindles