The No-U-turn Sampler (NUTS) is a MCMC sampling algorithm extending Hamiltonian Monte Carlo by a self-tuning mechanism for its integration times. It was developed by Andrew Gelman and Matt Hoffman to avoid the random walk behavior that plagues many MCMC methods like Random Walk Metropolis (RWM) or the Metropolis-adjusted Langevin Algorithm (MALA). Due to its superior empirical performance, NUTS has become the default sampler in many probabilistic programming languages such as STAN, PyMC3, and NumPyro, making it one of the most widely used samplers in Bayesian computation.
That Hamiltonian Monte Carlo (as a continuous-time Markov process)---when critically tuned---achieves acceleration under natural conditions was recently shown via the theory of variational hypocoercivity (see Lu and Wang 2022, Eberle and Lörler 2024). However, whether NUTS realizes critical tuning and hence acceleration had not been rigorously studied. In joint work with Nawaf Bou-Rabee (Rutgers, Flatiron), we develop a concentration of measure approach to analyze the self-tuning mechanism of NUTS. This led to the first quantitative mixing analysis of NUTS. In the first work, we focussed on high-dimensional standard Gaussian targets (which describes preconditioned NUTS in any Gaussian). The second work extends the concentration approach to all Gaussian targets and studies NUTS' ability to achieve acceleration. Notably, we uncover a remarkable ability of NUTS to identify critical tuning---but also reveal clear limitations.
Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration
with N. Bou-Rabee, preprint, 2024
On Accelerated Mixing of the No-U-turn Sampler
preprint, 2025
Metropolis-Hastings filters are commonly used in sampling to correct bias caused by discretization, e.g., of the overdamped Langevin diffusion in MALA or Hamiltonian flow in HMC. Even NUTS employs a closely related filter. Although analytic conductance methods accurately capture the implications of Metropolis-adjustment on mixing (see for instance Andrieu et al. 2024, Chen et al. 2022), probabilistic techniques did not yield sharp bounds. In joint work with Nawaf Bou-Rabee (Rutgers, Flatiron), we developed a novel coupling framework for Metropolis-adjusted chains in the high-acceptance regime that
yields sharp mixing guarantees for ballistically accelerated HMC,
substantially relaxes assumptions on initialization while retaining mixing guarantees previously only achievable under far stronger warm-start assumptions,
localizes the analysis to the region of state space actually relevant to the chain.
Mixing of Metropolis-adjusted Markov chains via couplings: The high acceptance regime
with N. Bou-Rabee, Electronic Journal of Probability, 2024
When gradients of the log-likelihood are not available, one resorts to gradient-free methods such as Hit-and-Run, a coordinate-free Gibbs sampler. While Hit-and-Run is well-studied (see for instance Lovász 1999, Chen and Eldan 2022, Ascolani et al. 2024), a coupling-based probabilistic analysis was missing. In joint work with Nawaf Bou-Rabee (Rutgers, Flatiron) and Andreas Eberle (Bonn), we gave a full coupling characterization of the Wasserstein mixing of Hit-and-Run in Gaussian targets. Notably, our analysis
rigorously demonstrates a surprising ability of Hit-and-Run to accelerate beyond the generally diffusive coordinate-bound Gibbs sampler in certain settings (for instance bivariate Gaussians),
extends to the randomized Kaczmarz algorithm, an optimization method for solving overdetermined linear systems, recovering previously known convergence results (Strohmer and Vershynin 2009).
Accelerated convergence in Hit-and-Run Monte Carlo and a coordinate-free randomized Kaczmarz algorithm
with N. Bou-Rabee & A. Eberle, Electronic Journal of Probability, 2025
Our analysis of Hit-and-Run showed a surprising resemblance between the challenges faced when implementing Hit-and-Run and the issues addressed by the self-tuning of NUTS. Based on this insight, in joint work with Nawaf Bou-Rabee (Rutgers, Flatiron), Bob Carpenter (Flatiron), and Sifan Liu (Duke), we developed the No-Under-Run Sampler (NURS), a NUTS-inspired high-performance implementation of Hit-and-Run. We further
provided tuning guidelines by connecting to Hit-and-Run and Random Walk Metropolis,
analyzed the Wasserstein mixing of NURS,
empirically illustrated the ability of NURS to sample challenging target distributions.
The No-Underrun Sampler: A Locally-Adaptive, Gradient-Free MCMC Method
with N. Bou-Rabee, B. Carpenter & S. Liu, preprint, 2025