NoUTurnSampler

The No-U-Turn Sampler (NUTS) is a sampling algorithm for Bayesian inference that extends Hamiltonian Monte Carlo (HMC) by adaptively choosing the length of the simulated Hamiltonian trajectory. It removes the need to pre-specify how many leapfrog steps to take, instead terminating when the trajectory would begin to turn back toward its starting point, a No-U-Turn condition that improves efficiency and robustness.

During each iteration, NUTS draws a fresh momentum from a Gaussian distribution, integrates the Hamiltonian dynamics using the leapfrog method, and builds candidate states by expanding a binary tree of states. The tree is grown in both forward and backward time directions until the No-U-Turn criterion is satisfied. A Metropolis acceptance step is used to ensure detailed balance, and one of the leaf states is chosen as the next sample. The step size and mass matrix are typically adapted during a warmup phase via dual averaging and related schemes.

History and use: The No-U-Turn Sampler was introduced to provide automatic path-length tuning for HMC. It has become a standard component in modern probabilistic programming, most notably as the default sampler in Stan, and is also used in other frameworks such as PyMC3. The approach requires gradient information of the log-posterior and differentiable models.

Advantages and limitations: NUTS offers improved efficiency and reduces the manual tuning burden compared with fixed-length HMC, especially in high-dimensional problems. Its performance depends on accurate gradient calculations and proper mass-matrix adaptation; it can be computationally intensive per iteration due to gradient evaluations, and like other gradient-based samplers may struggle with highly multimodal or poorly scaled targets.