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 (10)

• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Is There an Analog of Nesterov Acceleration for MCMC?
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities

Cited by in corpus (12)

• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Couplings for Andersen Dynamics
• Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• Couplings for Multinomial Hamiltonian Monte Carlo
• Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
• An entropic approach for Hamiltonian Monte Carlo: the idealized case
• Entropy-based adaptive Hamiltonian Monte Carlo