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

2026/03/19 by Samuel Gruffaz, Kyurae Kim, Fares Guehtar +2 · 1 voice
Computer Science · Mathematics · #Advanced Database Systems and Queries #Bayesian Methods and Mixture Models #Bayesian Modeling and Causal Inference #Convergence (economics) #Ergodicity #Gaussian #Logarithm #Mixing (physics) #Sampling (signal processing) #Scale (ratio) #cs.LG #math.PR #stat.ML

paper · pdf · doi:10.48550/arxiv.2603.18640

openalex publication_date 2026/03/19 · arxiv published 2026/03/19 · openalex created_date 2026/03/21 · arxiv updated 2026/04/14 · openalex updated_date 2026/07/28

Abstract

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(d^1/4) up to logarithmic factors, where d denotes the dimension. Nevertheless, the associated constants are strictly smaller for NUTS-BPS.

Citations

• On Accelerated Mixing of the No-U-turn Sampler
• The Within-Orbit Adaptive Leapfrog No-U-Turn Sampler
• A Review on Riemannian Metric Learning: Closer to You than You Imagine
• Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration
• Adaptive Stereographic MCMC
• Incorporating Local Step-Size Adaptivity into the No-U-Turn Sampler using Gibbs Self Tuning
• GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo
• On the convergence of dynamic implementations of Hamiltonian Monte Carlo and no U-turn samplers
• Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps
• Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
• The Barker proposal: combining robustness and efficiency in gradient-based MCMC
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Pyro: Deep Universal Probabilistic Programming
• Coupling and Convergence for Hamiltonian Monte Carlo
• On the convergence of Hamiltonian Monte Carlo
• A Conceptual Introduction to Hamiltonian Monte Carlo
• On the Geometric Ergodicity of Hamiltonian Monte Carlo
• The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
• An Improved Acceptance Procedure for the Hybrid Monte Carlo Algorithm
• Monte Carlo sampling methods using Markov chains and their applications

Discussions

• A related recent pre-print by Samuel and co-authors has theoretical backing for the empirical observation that BPS can be superior to multinomial selection rule: arxiv.org/abs/2603.18640. [bsky, 1 points, 0 comments]

Related

• Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration
• Is the NUTS algorithm correct?
• The Within-Orbit Adaptive Leapfrog No-U-Turn Sampler
• The Within-Orbit Adaptive Leapfrog No-U-Turn Sampler
• Incorporating Local Step-Size Adaptivity into the No-U-Turn Sampler using Gibbs Self Tuning