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 $\epsilon$ 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 perform at least as efficiently as and sometimes more efficiently 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 $\epsilon$ on the fly based on primal-dual averaging. NUTS can thus be used with no hand-tuning at all. NUTS is also suitable for applications such as BUGS-style automatic inference engines that require efficient "turnkey" sampling algorithms.
Introduction
Markov chain Monte Carlo (MCMC) methods are the workhorse of Bayesian statistics, but they often struggle with high-dimensional or highly correlated distributions. Standard methods like Metropolis-Hastings or Gibbs sampling tend to behave like "random walks," taking tiny, inefficient steps that require a vast number of iterations to explore the target space.
Hamiltonian Monte Carlo (HMC) addresses this by using physics-inspired dynamics—specifically, the gradients of the target distribution—to take long, directed leaps across the parameter space. However, HMC suffers from a significant "tuning problem." Users must manually specify the step size ($\epsilon$) and the number of steps ($L$). If $L$ is too small, HMC reverts to a slow random walk. If $L$ is too large, the sampler completes a loop and "U-turns," wasting computational effort only to end up back near its starting point. Finding the optimal value for $L$ usually requires expensive pilot runs and significant user expertise.
The NUTS Algorithm
The No-U-Turn Sampler (NUTS) is an extension of HMC that adaptively sets the path length $L$ for every single iteration, transforming HMC into a "turnkey" algorithm.
Recursive Doubling and the U-Turn Criterion
NUTS uses a recursive doubling algorithm to build a trajectory. It starts with a single step and then doubles the number of steps in each iteration (moving either forward or backward in "fictitious time" at random). This process continues until a "U-turn" condition is met. Essentially, the algorithm checks if the distance between the ends of the path is no longer increasing, signaling that further steps would likely lead the sampler back toward its starting point.
Maintaining Detailed Balance
Simply stopping a trajectory when a U-turn occurs would violate the mathematical requirements of MCMC (specifically, time-reversibility and detailed balance). NUTS overcomes this by building a balanced binary tree of candidate states. By using a slice sampling approach to select a new state from this tree, NUTS ensures that the transition remains theoretically sound while allowing for adaptive path lengths.
Automatic Step Size Tuning
To make the algorithm truly hand-tuning free, the authors implement a dual averaging scheme (based on Nesterov’s primal-dual averaging) to automatically tune the step size $\epsilon$ during the initial "burn-in" or "warm-up" phase. This ensures the sampler finds an efficient step size for the specific geometry of the target distribution without user intervention.
Evaluation and Results
The authors evaluated NUTS against standard HMC, Random-Walk Metropolis (RWM), and Gibbs sampling using four diverse target distributions:
- 250-dimensional Multivariate Normal (MVN): A synthetic distribution with strong correlations.
- Bayesian Logistic Regression (LR): Fit to the German credit dataset.
- Hierarchical Bayesian Logistic Regression (HLR): A complex, 300-dimensional hierarchical model.
- Stochastic Volatility (SV): A 3001-dimensional model used to analyze S&P 500 stock returns.
In head-to-head tests, NUTS performed as well as or better than standard HMC, even when HMC was given the advantage of being optimally hand-tuned by the researchers. On the highly correlated 250-D Normal and Stochastic Volatility models, NUTS achieved an effective sample size (ESS) per gradient evaluation roughly three times higher than the best-tuned HMC. While traditional methods like RWM and Gibbs sampling often struggle to move from their starting points in correlated spaces, NUTS explores the entire distribution efficiently.
Conclusion
By automating the selection of both $L$ and $\epsilon$, NUTS transforms HMC from a specialist tool into a general-purpose inference engine. Its efficiency and lack of required tuning have led to its adoption as the default sampler for Stan, a widely used probabilistic programming language. While it is limited to continuous variables and requires more memory than standard HMC (optimized to $O(\log L)$ in the paper's "Efficient NUTS" implementation), it represents a major leap forward in making sophisticated Bayesian inference accessible to a broader range of researchers.
Summary updated