Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients

Abstract

Hamiltonian Monte Carlo (HMC) is a state-of-the-art Markov chain Monte Carlo sampling algorithm for drawing samples from smooth probability densities over continuous spaces. We study the variant most widely used in practice, Metropolized HMC with the Störmer-Verlet or leapfrog integrator, and make two primary contributions. First, we provide a non-asymptotic upper bound on the mixing time of the Metropolized HMC with explicit choices of step-size and number of leapfrog steps. This bound gives a precise quantification of the faster convergence of Metropolized HMC relative to simpler MCMC algorithms such as the Metropolized random walk, or Metropolized Langevin algorithm. Second, we provide a general framework for sharpening mixing time bounds of Markov chains initialized at a substantial distance from the target distribution over continuous spaces. We apply this sharpening device to the Metropolized random walk and Langevin algorithms, thereby obtaining improved mixing time bounds from a non-warm initial distribution.

arXiv comment73 pages, 2 figures, fixed a mistake in the proof of Lemma 11, accepted in JMLR

References in corpus (13)

• General state space Markov chains and MCMC algorithms
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Sampling Can Be Faster Than Optimization
• On the Geometric Ergodicity of Hamiltonian Monte Carlo
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Convergence of Langevin MCMC in KL-divergence
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Optimizing The Integrator Step Size for Hamiltonian Monte Carlo
• On the convergence of Hamiltonian Monte Carlo
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Faster Hamiltonian Monte Carlo by Learning Leapfrog Scale: an offline randomized solution
• Nonconvex sampling with the Metropolis-adjusted Langevin algorithm

Cited by in corpus (10)

• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Neural Bridge Sampling for Evaluating Safety-Critical Autonomous Systems
• Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
• Entropy-based adaptive Hamiltonian Monte Carlo
• An entropic approach for Hamiltonian Monte Carlo: the idealized case