# A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targets

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 46 references that are in the map.
- First posted on arXiv 19 Mar 2026.

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

- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [A Conceptual Introduction to Hamiltonian Monte Carlo](https://mlsanity.com/paper/1701.02434/) (2017)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [Geometric integrators and the Hamiltonian Monte Carlo method](https://mlsanity.com/paper/1711.05337/) (2017)
- [The Barker proposal: combining robustness and efficiency in gradient-based MCMC](https://mlsanity.com/paper/1908.11812/) (2019)
- [On the Geometric Ergodicity of Hamiltonian Monte Carlo](https://mlsanity.com/paper/1601.08057/) (2016)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [A Review on Riemannian Metric Learning: Closer to You than You Imagine](https://mlsanity.com/paper/2503.05321/) (2025)
- [GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo](https://mlsanity.com/paper/2404.15253/) (2024)
- [Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps](https://mlsanity.com/paper/2209.12771/) (2022)
- [Incorporating Local Step-Size Adaptivity into the No-U-Turn Sampler using Gibbs Self Tuning](https://mlsanity.com/paper/2408.08259/) (2024)
- [Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration](https://mlsanity.com/paper/2410.06978/) (2024)
- [On the convergence of dynamic implementations of Hamiltonian Monte Carlo and No U-Turn Samplers](https://mlsanity.com/paper/2307.03460/) (2023)
- [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)

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

- [Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2607.12902/) (2026)

## Abstract (arXiv)

The No-U-Turn Sampler (NUTS) is the computational workhorse of modern Bayesian software libraries, yet its qualitative and quantitative convergence guarantees were established only recently. A significant gap remains in the theoretical comparison of its two main variants: NUTS-mul and NUTS-BPS, which use multinomial sampling and biased progressive sampling, respectively, for index selection. In this paper, we address this gap in three contributions. First, we derive the first necessary conditions for geometric ergodicity for both variants. Second, we establish the first sufficient conditions for geometric ergodicity and ergodicity for NUTS-mul. Third, we obtain the first mixing time result for NUTS-BPS on a standard Gaussian distribution. Our results show that NUTS-mul and NUTS-BPS exhibit nearly identical qualitative behavior, with geometric ergodicity depending on the tail properties of the target distribution. However, they differ quantitatively in their convergence rates. More precisely, when initialized in the typical set of the canonical Gaussian measure, the mixing times of both NUTS-mul and NUTS-BPS scale as O(d1/4) up to logarithmic factors, where d denotes the dimension. Nevertheless, the associated constants are strictly smaller for NUTS-BPS.