Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo

Abstract

We provide quantitative upper bounds on the total variation mixing time of the Markov chain corresponding to the unadjusted Hamiltonian Monte Carlo (uHMC) algorithm. For two general classes of models and fixed time discretization step size $h$, the mixing time is shown to depend only logarithmically on the dimension. Moreover, we provide quantitative upper bounds on the total variation distance between the invariant measure of the uHMC chain and the true target measure. As a consequence, we show that an $\epsilon$-accurate approximation of the target distribution $\mu$ in total variation distance can be achieved by uHMC for a broad class of models with $O\left(d^{3/4}{\epsilon }^{-1/2}\log (d/\epsilon )\right)$ gradient evaluations, and for mean field models with weak interactions with $O\left(d^{1/2}{\epsilon }^{-1/2}\log (d/\epsilon )\right)$ gradient evaluations. The proofs are based on the construction of successful couplings for uHMC that realize the upper bounds.

arXiv comment43 pages

References in corpus (13)

• Reflection couplings and contraction rates for diffusions
• Convergence of Numerical Time-Averaging and Stationary Measures via Poisson Equations
• Geometric integrators and the Hamiltonian Monte Carlo method
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Coupling and Convergence for Hamiltonian Monte Carlo
• Quantitative bounds for Markov chain convergence: Wasserstein and total variation distances
• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo
• Convergence of unadjusted Hamiltonian Monte Carlo for mean-field models
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms
• Two-scale coupling for preconditioned Hamiltonian Monte Carlo in infinite dimensions
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

Cited by in corpus (7)

• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo
• Contraction and Convergence Rates for Discretized Kinetic Langevin Dynamics
• Mixing of Metropolis-Adjusted Markov Chains via Couplings: The High Acceptance Regime
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithm
• An entropic approach for Hamiltonian Monte Carlo: the idealized case
• Randomized Runge-Kutta-Nyström Methods for Unadjusted Hamiltonian and Kinetic Langevin Monte Carlo