The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo

Matthew D. Hoffman, Andrew Gelman

TL;DR

This paper introduces the No-U-Turn Sampler (NUTS), a novel Hamiltonian Monte Carlo (HMC) algorithm that automatically determines the optimal trajectory length, eliminating a key tuning parameter. Combined with an adaptive step-size tuning method, NUTS offers efficient and "turnkey" sampling for complex Bayesian models, outperforming standard HMC in many cases.

What Problem Does This Paper Address?

Markov Chain Monte Carlo (MCMC) methods, particularly Hamiltonian Monte Carlo (HMC), are powerful tools for Bayesian inference, offering faster convergence than simpler methods like random walk Metropolis or Gibbs sampling. However, HMC's performance is critically dependent on two user-defined parameters: the step size ($\epsilon$) and the number of steps ($L$) in the simulated Hamiltonian trajectory. Setting $L$ too small leads to inefficient random-walk behavior, while setting it too large wastes computational resources. Manually tuning these parameters is time-consuming and requires expertise, hindering HMC's widespread adoption, especially in automated inference systems. This paper addresses the challenge of making HMC more user-friendly and robust by removing the need for manual tuning of $L$ and providing an adaptive method for $\epsilon$.

Methods

The core innovation is the No-U-Turn Sampler (NUTS). NUTS builds upon HMC by using a recursive algorithm to construct a trajectory. Instead of a fixed number of steps $L$, NUTS simulates the Hamiltonian dynamics and stops when the trajectory begins to "double back" on itself, indicating that further simulation is unlikely to yield substantially new information. This "U-turn" criterion is formalized by examining the dot product between the momentum and the displacement from the initial position. NUTS constructs a binary tree of potential next states and samples from a subset of these states that satisfy certain conditions to ensure detailed balance.

To address the step-size parameter $\epsilon$, the authors propose an adaptation of Nesterov's primal-dual averaging algorithm. This method adaptively tunes $\epsilon$ on the fly during the sampling process, aiming for a target average acceptance rate. This dual averaging approach is applied during a burn-in phase, after which the step size is fixed.

Datasets

The authors evaluate their methods on four target distributions:

  • 250-dimensional multivariate normal (MVN): A synthetic dataset designed to have strong correlations.
  • Bayesian logistic regression (LR): A posterior distribution from fitting a logistic regression model to the German credit dataset.
  • Hierarchical Bayesian logistic regression (HLR): An extension of the logistic regression model with hierarchical priors.
  • Stochastic volatility (SV): A posterior distribution from a stochastic volatility model fit to S&P 500 index returns.

Key Insights and Ideas

  • Eliminating the $L$ parameter is crucial: The "U-turn" criterion provides an elegant and principled way to automatically determine an appropriate trajectory length for HMC, removing a significant barrier to its use.
  • Adaptive step-size tuning is essential for "turnkey" samplers: Combining NUTS with primal-dual averaging for $\epsilon$ makes the algorithm truly automatic, requiring no user intervention for tuning.
  • NUTS can explore high-dimensional spaces efficiently: The algorithm's ability to generate long, exploratory trajectories without getting stuck in random walks is key to its performance.
  • The "U-turn" criterion is a natural stopping point: This criterion effectively balances exploring the target distribution with avoiding redundant computations.

Key Results

  • NUTS performs as well as or better than tuned HMC: Empirically, NUTS achieves comparable or superior efficiency (measured by effective sample size per gradient evaluation) to well-tuned standard HMC.
  • NUTS can be up to three times more efficient than HMC: For certain problems (multivariate normal and stochastic volatility), NUTS outperforms HMC's best performance by a factor of three, even when HMC's simulation length is optimized.
  • Adaptive tuning works well: The dual averaging algorithm effectively tunes the step size $\epsilon$ for both NUTS and HMC, converging to reasonable values within a few hundred iterations for most problems.
  • NUTS handles correlated parameters effectively: Figure 7 demonstrates NUTS's superior ability to explore a highly correlated 250-dimensional space compared to random-walk Metropolis and Gibbs sampling.

Limitations and Future Work

  • Differentiability requirement: Like HMC, NUTS requires the target distribution to be differentiable with respect to the parameters. For models with discrete variables or complex constraints, other methods or extensions would be needed.
  • Computational cost: While NUTS is efficient, the cost of computing gradients still dominates. For extremely high-dimensional problems or computationally expensive gradient calculations, further optimizations might be necessary.
  • Future work: The authors suggest combining NUTS with Riemannian Manifold HMC (RMHMC) to adapt both trajectory lengths and mass matrices. They also envision NUTS being a core component of automated Bayesian inference systems like Stan.

Summary updated

Abstract

Hamiltonian Monte Carlo (HMC) is a Markov chain Monte Carlo (MCMC) algorithm that avoids the random walk behavior and sensitivity to correlated parameters that plague many MCMC methods by taking a series of steps informed by first-order gradient information. These features allow it to converge to high-dimensional target distributions much more quickly than simpler methods such as random walk Metropolis or Gibbs sampling. However, HMC's performance is highly sensitive to two user-specified parameters: a step size ε and a desired number of steps L. In particular, if L is too small then the algorithm exhibits undesirable random walk behavior, while if L is too large the algorithm wastes computation. We introduce the No-U-Turn Sampler (NUTS), an extension to HMC that eliminates the need to set a number of steps L. NUTS uses a recursive algorithm to build a set of likely candidate points that spans a wide swath of the target distribution, stopping automatically when it starts to double back and retrace its steps. Empirically, NUTS performs at least as efficiently as (and sometimes more effciently than) a well tuned standard HMC method, without requiring user intervention or costly tuning runs. We also derive a method for adapting the step size parameter ε on the fly based on primal-dual averaging. NUTS can thus be used with no hand-tuning at all, making it suitable for applications such as BUGS-style automatic inference engines that require efficient "turnkey" samplers.
BibTeX
@article{hoffman2014no,
  author = {Matthew D. Hoffman and Andrew Gelman},
  title = {{The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=bWgaUTU0wQ},
}
Figure