Optimizing The Integrator Step Size for Hamiltonian Monte Carlo

Michael Betancourt, Simon Byrne, Mark GirolamiarXiv 2014 · DOI · arXiv

Abstract: Hamiltonian Monte Carlo can provide powerful inference in complex statistical problems, but ultimately its performance is sensitive to various tuning parameters. In this paper we use the underlying geometry of Hamiltonian Monte Carlo to construct a universal optimization criteria for tuning the step size of the symplectic integrator crucial to any implementation of the algorithm as well as diagnostics to monitor for any signs of invalidity. An immediate outcome of this result is that the suggested target average acceptance probability of 0.651 can be relaxed to $0.6 \lesssim a \lesssim 0.9$ with larger values more robust in practice.

Introduction

Hamiltonian Monte Carlo (HMC) has emerged as a premier algorithm for sampling from complex, high-dimensional probability distributions. By simulating the physical motion of a particle along a log-density surface, HMC generates distant proposals that maintain high acceptance rates. However, the efficiency of this simulation is highly dependent on the integrator step size ($\epsilon$).

Historically, practitioners have relied on a target acceptance rate of 0.651, a value derived from idealized, high-dimensional Gaussian models. This paper provides a more rigorous theoretical foundation for tuning $\epsilon$ by leveraging the symplectic geometry of the HMC algorithm. The authors demonstrate that the optimal tuning range is broader and more robust than previously thought, particularly when dealing with the non-ideal geometries encountered in real-world applications.

Theoretical Framework: Symplectic Geometry and Error Analysis

The core of the paper’s contribution lies in Backwards Error Analysis. While numerical integrators (like the leapfrog integrator) do not perfectly conserve the energy, or Hamiltonian ($H$), of the system, they do exactly follow a "modified Hamiltonian" ($\tilde{H}$). The difference between the true and modified Hamiltonians, denoted as $\Delta_\epsilon$, determines the acceptance probability of the HMC transition.

To analyze the computational cost associated with these errors, the authors employ several mathematical strategies:

  1. Cost Bounding: Using Jensen’s inequality, the authors "sandwich" the expected computational cost between a lower bound and a newly derived upper bound.
  2. Gaussian Approximation: Through a Gram-Charlier expansion, the authors show that for a wide class of target distributions, the error in the Hamiltonian ($\Delta_\epsilon$) is approximately Gaussian. This approximation simplifies the complex geometric integrals into a functional relationship between the step size and the average acceptance probability ($a$).

The Geometry of Optimal Tuning

The analysis reveals a "flat" cost curve, suggesting that HMC performance is relatively stable across a range of acceptance rates. While the lower bound of the cost function is indeed minimized at $a \approx 0.651$, the upper bound—which represents a more conservative estimate of efficiency—is minimized at $a \approx 0.801$.

This finding has significant practical implications. Aiming for a higher acceptance rate (e.g., 0.8) provides a buffer against the varying curvature of complex distributions. In regions of high curvature, a step size tuned for 0.651 might become unstable, whereas a step size tuned for 0.8 is more likely to remain valid. This robustness is critical for maintaining the integrity of the Markov chain in high-dimensional spaces.

Diagnostics and Divergences

A key conceptual shift presented in the paper is the treatment of numerical divergences. When the integrator step size is too large for the local geometry, the numerical simulation can become unstable, sending the particle toward infinity. Rather than viewing these as mere failures, the authors formalize divergences as a diagnostic tool. These events pinpoint specific regions of the parameter space where the local curvature is too high for the current tuning parameters, signaling the need for a smaller step size or a re-parameterization of the model (such as moving from a centered to a non-centered parameterization in hierarchical models).

Validation and Empirical Results

The theoretical bounds were validated using both analytic Gaussian targets and the notoriously difficult "Funnel" distribution. The Funnel distribution, characterized by a sharp neck with extreme curvature, serves as a benchmark for topological instability. The results confirmed that:

  • The relationship between step size, cost, and acceptance probability in high dimensions closely follows the theoretical predictions.
  • Increasing the target acceptance probability effectively mitigates divergences in regions of high curvature, though it cannot solve fundamental topological issues where the geometry is inherently non-smooth.

Conclusion

This work provides the theoretical justification for the tuning defaults used in modern probabilistic programming languages like Stan. By shifting the focus from a single point estimate (0.651) to a robust range ($0.6$ to $0.9$), the authors provide a framework that prioritizes stability without sacrificing significant efficiency. While the theory assumes a constant integration time, its principles have proven remarkably effective for dynamic integration algorithms like the No-U-Turn Sampler (NUTS), ensuring that HMC remains a reliable tool for modern statistical inference.

Summary updated

Abstract

Hamiltonian Monte Carlo can provide powerful inference in complex statistical problems, but ultimately its performance is sensitive to various tuning parameters. In this paper we use the underlying geometry of Hamiltonian Monte Carlo to construct a universal optimization criteria for tuning the step size of the symplectic integrator crucial to any implementation of the algorithm as well as diagnostics to monitor for any signs of invalidity. An immediate outcome of this result is that the suggested target average acceptance probability of 0.651 can be relaxed to $0.6 \lesssim a \lesssim 0.9$ with larger values more robust in practice.
BibTeX
@misc{betancourt2014optimizing,
  author = {Michael Betancourt and Simon Byrne and Mark Girolami},
  title = {{Optimizing The Integrator Step Size for Hamiltonian Monte Carlo}},
  year = {2014},
  eprint = {1411.6669},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1411.6669},
}
Figure