Source-linked AI summary
The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
Matthew D. Hoffman, Andrew Gelman
TL;DR
HMC requires difficult tuning of its step size and trajectory length, limiting its practicality despite efficient sampling. NUTS removes the need to choose trajectory length and adapts step size automatically, matching or sometimes improving HMC efficiency without hand-tuning.
Problem
HMC requires expertise and preliminary runs to tune its step size and number of steps, especially the trajectory length L.
Method
NUTS extends HMC with automatic trajectory-length selection and dual averaging to adapt the step size during sampling.
Results
NUTS eliminates dependence on L while retaining, and sometimes improving, HMC’s efficient generation of effectively independent samples.
Takeaways & Limitations
With dual averaging, NUTS provides HMC efficiency without hand-tuning and is suitable for generic inference engines requiring user-independent sampling.
Takeaways & Limitations
NUTS applies only to unconstrained continuous variables whose target distribution is differentiable almost everywhere, with discrete variables requiring other handling.
Abstract
from arXiv · showhide
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 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 ε 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.
1. Introduction
Approximate inference is often necessary for hierarchical Bayesian models, but common MCMC methods can converge inefficiently because they explore parameter space through random walks. The paper introduces NUTS to remove HMC’s need to specify trajectory length and adds automatic step-size tuning, enabling sampling without hand-tuning.
- Motivation: Exact posterior inference in hierarchical Bayesian models is rarely tractable, making approximate inference methods necessary.MCMC methods provide generally applicable, asymptotically unbiased schemes for drawing correlated samples that converge to the target distribution.
- Motivation: Random-walk Metropolis and Gibbs sampling may converge unacceptably slowly in complicated, high-parameter models because they explore inefficiently.This limitation is attributed largely to inefficient random walks through parameter space.
- HMC limitations: HMC requires gradients of the log-posterior and user-specified values for step size ϵ and trajectory length L.Automatic differentiation can reduce the burden of computing gradients, but poor choices of either HMC parameter create problems.
- Contributions: NUTS is an HMC-like MCMC algorithm that eliminates the need to choose the problematic number-of-steps parameter L.This is the paper’s main contribution.
- Contributions: A new dual-averaging scheme automatically tunes the step size ϵ in both HMC and NUTS, allowing NUTS to run without hand-tuning.The scheme is attributed to Nesterov’s dual averaging method.
2. Hamiltonian Monte Carlo
Hamiltonian Monte Carlo augments model variables with Gaussian momenta and uses gradient-informed leapfrog dynamics to propose distant samples. Its performance depends strongly on step size ε and trajectory length L, which can cause inaccurate simulations, wasted computation, or random-walk behavior when poorly chosen.
- Augmented Hamiltonian system: HMC introduces an auxiliary momentum variable r_d for each model variable θ_d, with momenta independently drawn from a standard normal distribution.The augmented system combines position variables θ with momentum variables r.
- Sampling procedure: For each sample, HMC resamples momentum from a standard multivariate normal, simulates L leapfrog steps, and uses an acceptance probability based on the simulated system’s energy change.The momentum resampling can be interpreted as a Gibbs sampling update; negating the proposal momentum is theoretically required for time-reversibility but can be omitted when sampling only p(θ).
- Leapfrog dynamics: The leapfrog integrator updates momentum and position using gradients of the log joint density, while preserving volume because each coordinate update depends only on the others.The updates use step size ε and alternate half-steps for momentum with a full position step.
- Discretization error: If Hamiltonian dynamics were simulated exactly, acceptance would always be 1 because energy is conserved; discretization error instead depends on ε, scaling as ε^2 for large L and ε^3 when L = 1.Despite possible theoretical growth with L, leapfrog trajectories typically maintain high acceptance while producing proposals distant from the previous sample.
- Tuning challenges: HMC performance depends strongly on ε and L: overly large ε lowers acceptance, overly small ε wastes computation, small L causes random-walk behavior, and large L retraces trajectories.These choices directly affect simulation accuracy, computational efficiency, and mixing.
3. Eliminating the Need to Hand-Tune HMC
This section introduces NUTS, which removes the need to hand-tune HMC’s number of leapfrog steps by stopping when trajectories begin to double back, and presents dual-averaging schemes for adapting the step size ε. Together, these methods address HMC’s two main tuning parameters while retaining its ability to suppress random-walk behavior.
- Motivation: HMC requires expertise and preliminary runs to tune ε and L, with L especially difficult to select because no simple trajectory-length metric exists.Practitioners commonly rely on heuristics based on autocorrelation statistics from preliminary runs.
- No-U-Turn Sampler: NUTS eliminates the need to specify a fixed number L of leapfrog steps by automatically determining when further simulation would no longer increase distance from the starting position.Its stopping criterion is based on whether the trajectory begins moving back toward the initial position.
- No-U-Turn Sampler: NUTS recursively doubles trajectory length, choosing forward or backward directions at random and building a balanced binary tree of position-momentum states.The path grows from 1 to 2 to 4 steps and so on until the stopping condition is met.
- No-U-Turn Sampler: The recursive construction addresses the failure of a simple turn-back rule to guarantee time reversibility and convergence to the correct distribution.NUTS uses a recursive algorithm to overcome this issue.
- Step-size adaptation: Dual averaging adapts ε for both NUTS and HMC during burn-in, using vanishing adaptation while allowing rapid adjustment between transient and stationary regimes.The averaged iterates converge to a value where the target adaptation statistic converges to 0.
4. Empirical Evaluation
The evaluation tests dual-averaging step-size adaptation and compares automatically tuned NUTS with HMC across four target distributions. NUTS matches HMC on logistic regression and outperforms its best ESS by about threefold on the multivariate normal and stochastic volatility problems, while avoiding HMC’s simulation-length tuning burden.
- Step-size adaptation: Dual averaging usually coerced the acceptance statistic h toward its target δ, though it performed worse for stochastic volatility because that model needed a longer burn-in period.With δ = 0.65, the averaged step size roughly converged within a few hundred updates except for stochastic volatility.
- Efficiency comparison: NUTS produced effectively independent samples about as efficiently as HMC on both logistic regression problems.Efficiency was measured as ESS normalized by gradient evaluations.
- Efficiency comparison: On the multivariate normal and stochastic volatility problems, NUTS with δ = 0.6 outperformed HMC’s best ESS by about a factor of three.Figure 6 compares ESS per gradient evaluation across target δ values and HMC simulation lengths.
- HMC tuning burden: HMC’s best simulation lengths varied by about a factor of 100 across the four targets, from 0.17 for simple logistic regression to 17.62 for the multivariate normal.The passage states that finding a good HMC simulation length usually requires preliminary runs.
- Multivariate normal comparison: In a strongly correlated 250-dimensional multivariate normal, NUTS generated many effectively independent samples, whereas RWM had barely explored the space and Gibbs left regions unexplored.The comparison was visualized using samples projected onto the first two dimensions.
5. Discussion
NUTS eliminates HMC’s dependence on the number-of-steps parameter L while retaining, and sometimes improving, efficient generation of effectively independent samples. Combined with dual-averaging step-size adaptation, it enables efficient Bayesian inference with minimal human intervention, subject to continuous differentiable-variable constraints.
- Contributions: NUTS eliminates HMC’s dependence on the number-of-steps parameter L while retaining, and sometimes improving, efficient generation of effectively independent samples.
- Contributions: Dual averaging automatically adapts the shared step-size parameter ϵ for NUTS and HMC and could replace Robbins-Monro-based adaptive MCMC approaches.
- Limitations: NUTS and HMC apply to unconstrained continuous-valued variables with targets differentiable almost everywhere; discrete variables require marginalization or other algorithms.
- Limitations: With complex hard constraints, NUTS stops at zero-probability regions and samples from previously visited points, rather than wasting work before restarting.
- Practical implications: NUTS with dual averaging provides HMC efficiency without hand-tuning, making it suitable for generic inference engines and practitioners lacking HMC experience.
Appendix A. Estimating Effective Sample Size
Appendix A defines effective sample size as the number of independent samples matching an MCMC estimate’s mean variance and presents an autocorrelation-based estimator. It improves reliability by truncating noisy long-lag autocorrelations, while requiring a costly high-quality estimate of the target mean and variance.
- Effective sample size is the number of independent samples needed to match the MCMC estimate’s mean variance for a function f(θ).
- The method estimates ESS from the autocorrelation spectrum of f(θ) under the sampling distribution q.
- A separate 50,000-sample NUTS run with δ = 0.5 provides high-precision estimates of f’s mean and variance.Using the chain under evaluation can underestimate autocorrelation and overestimate effective samples when convergence or independent sampling is inadequate.
- Autocorrelations are truncated when they first fall below 0.05 because large-lag estimates are noisy and naive summation performs poorly.
- The estimator produced more reliable MCMC confidence intervals than CODA’s autoregressive approach, but required a costly high-quality target mean and variance estimate.Results were not sensitive to the precise cutoff value in the reported experiments.