# Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration

arXiv: https://arxiv.org/abs/2410.06978 · HTML: https://mlsanity.com/paper/2410.06978/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 54 references that are in the map.
- First posted on arXiv 9 Oct 2024.

## Builds on (most cited first, 23 of 23)

- [A Conceptual Introduction to Hamiltonian Monte Carlo](https://mlsanity.com/paper/1701.02434/) (2017)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Composable Effects for Flexible and Accelerated Probabilistic Programming in NumPyro](https://mlsanity.com/paper/1912.11554/) (2019)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Hamiltonian Monte Carlo for Hierarchical Models](https://mlsanity.com/paper/1312.0906/) (2013)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimension](https://mlsanity.com/paper/2108.00682/) (2021)
- [A general perspective on the Metropolis-Hastings kernel](https://mlsanity.com/paper/2012.14881/) (2020)
- [GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo](https://mlsanity.com/paper/2404.15253/) (2024)
- [Connecting the Dots: Numerical Randomized Hamiltonian Monte Carlo with State-Dependent Event Rates](https://mlsanity.com/paper/2005.01285/) (2020)
- [Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps](https://mlsanity.com/paper/2209.12771/) (2022)
- [Generalizing the No-U-Turn Sampler to Riemannian Manifolds](https://mlsanity.com/paper/1304.1920/) (2013)
- [The Apogee to Apogee Path Sampler](https://mlsanity.com/paper/2112.08187/) (2021)
- [On the convergence of dynamic implementations of Hamiltonian Monte Carlo and No U-Turn Samplers](https://mlsanity.com/paper/2307.03460/) (2023)

## Built on by (most cited first, 5 of 5)

- [The Within-Orbit Adaptive Leapfrog No-U-Turn Sampler](https://mlsanity.com/paper/2506.18746/) (2025)
- [On Accelerated Mixing of the No-U-turn Sampler](https://mlsanity.com/paper/2507.13259/) (2025)
- [Algorithmic warm starts for Hamiltonian Monte Carlo](https://mlsanity.com/paper/2603.22741/) (2026)
- [A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targets](https://mlsanity.com/paper/2603.18640/) (2026)
- [Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2607.12902/) (2026)

## Abstract (arXiv)

We prove that the mixing time of the No-U-Turn Sampler (NUTS), when initialized in the concentration region of the canonical Gaussian measure, scales as d1/4, up to logarithmic factors, where d is the dimension. This scaling is expected to be sharp. This result is based on a coupling argument that leverages the geometric structure of the target distribution. Specifically, concentration of measure results in a striking uniformity in NUTS' locally adapted transitions, which holds with high probability. This uniformity is formalized by interpreting NUTS as an accept/reject Markov chain, where the mixing properties for the more uniform accept chain are analytically tractable. Additionally, our analysis uncovers a previously unnoticed issue with the path length adaptation procedure of NUTS, specifically related to looping behavior, which we address in detail.