Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions 2: Numerical integrators

Oren Mangoubi, Aaron SmithAISTATS 2019 · OpenReview

Abstract

We obtain quantitative bounds on the mixing properties of the Hamiltonian Monte Carlo (HMC) algorithm with target distributions in $d$-dimensional Euclidean space. This work provides the first such bounds for the practical implementation of HMC using the leapfrog integrator on strongly log-concave distributions. We show that HMC mixes quickly, requiring a number of gradient evaluations that scales with $d^{1/2}$, significantly outperforming the linear scaling ($d^1$) of the popular Langevin algorithm.

Introduction: Bridging Theory and Practice

Hamiltonian Monte Carlo (HMC) is a cornerstone of modern Bayesian statistics, favored for its ability to explore high-dimensional spaces more efficiently than simple random walks. By introducing auxiliary momentum variables and following Hamiltonian dynamics, HMC can make large moves in the state space while maintaining high acceptance rates. However, a significant gap has long existed between the "ideal" continuous-time version of HMC and the discrete-time numerical implementations used in practice.

Real-world implementations must use numerical integrators—most commonly the leapfrog method—to approximate these dynamics. While the "ideal" HMC (assuming perfect integration) was known to be fast, proving convergence for the numerical version on a broad class of distributions remained a challenge. This paper addresses this by analyzing the mixing time (the time to converge to the target distribution) for the unadjusted leapfrog integrator applied to strongly log-concave distributions.

Methodology: Coupling and Numerical Perturbation

The authors employ a coupling argument to bound the mixing time. This technique involves comparing two versions of the Markov chain: the "ideal" HMC trajectory and the "numerical" HMC trajectory produced by the leapfrog integrator. The goal is to prove that the numerical version stays "close enough" to the ideal version to inherit its rapid convergence properties.

Figure 1: Illustration of Hamiltonian Monte Carlo trajectories moving through the level sets of a target distribution. The points $X_i$ represent the state, while $p_i$ represent the momentum vectors that guide the trajectory.

The study focuses on distributions that satisfy two key mathematical conditions:

  1. Strong Log-Concavity: The "bowl" of the distribution is sufficiently steep, ensuring the Hessian eigenvalues are bounded below.
  2. Lipschitz Gradients: The "slope" of the log-density does not change too abruptly, meaning the Hessian eigenvalues are bounded above.

By treating the numerical error as a small perturbation of the ideal dynamics, the authors show that the chain still exhibits a mathematical "drift" toward the mode of the distribution. This ensures convergence even when the leapfrog integrator does not track the exact Hamiltonian path perfectly.

Key Results: The $d^{1/2}$ Advantage

The primary contribution of this work is the rigorous proof of HMC's superior scaling. The authors prove that the number of gradient evaluations needed to reach an error level $\epsilon$ (in Wasserstein-1 distance) is approximately $\tilde{O}(d^{1/2} \epsilon^{-1} (M_2/m_2)^{6.5})$, where $M_2/m_2$ is the condition number of the distribution.

This $d^{1/2}$ scaling is a significant "aha moment" for the field. In a 10,000-dimensional problem, this represents the difference between 10,000 steps (for the Langevin algorithm's $d^1$ scaling) and only 100 steps. To maintain this accuracy, the analysis shows that the leapfrog step size $\theta$ must scale inversely with the square root of the dimension ($\theta \approx d^{-1/2}$).

Discussion and Future Work

While these results provide a solid theoretical foundation for HMC, they rely on the assumption of strong log-concavity. Many real-world distributions are multi-modal or only weakly concave, where HMC's behavior may differ.

Furthermore, the authors describe their analysis as "blunt" because it treats the leapfrog integrator as a generic first-order approximation. It does not fully account for the integrator's symplectic properties, such as volume preservation and energy conservation. A more refined analysis that leverages these "physics-preserving" features could potentially lead to even tighter bounds. Future work may also explore the impact of preconditioning—transforming the space to make the distribution more isotropic—which is a common practical technique to further accelerate convergence.

Summary updated

Abstract

We obtain quantitative bounds on the mixing properties of the Hamiltonian Monte Carlo (HMC) algorithm with target distribution in d-dimensional Euclidean space, showing that HMC mixes quickly whene...
BibTeX
@inproceedings{mangoubi2019mixing,
  author = {Oren Mangoubi and Aaron Smith},
  title = {{Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions 2: Numerical integrators}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=R0FPTDV-ITI},
}
Figure