Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions

Abstract

We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to $e^{-f}$ where $f:{\mathbb{R}}^d\to \mathbb{R}$ is $\mu$-strongly convex and $L$-smooth (the condition number is $\kappa =L/\mu$). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is $O(\kappa )$, improving on the previous best bound of $O({\kappa }^{1.5})$; we complement this with an example where the relaxation time is $\Omega (\kappa )$. When implemented using a nearly optimal ODE solver, HMC returns an $\epsilon$-approximate point in $2$-Wasserstein distance using $\tilde{O}((\kappa d{)}^{0.5}{\epsilon }^{-1})$ gradient evaluations per step and $\tilde{O}((\kappa d{)}^{1.5}{\epsilon }^{-1})$ total time.

References in corpus (2)

• Underdamped Langevin MCMC: A non-asymptotic analysis
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions

Cited by in corpus (6)

• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Couplings for Multinomial Hamiltonian Monte Carlo
• 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