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