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

Samuel Gruffaz; Kyurae Kim; Fares Guehtar; Hadrien Duval-decaix; Pacôme Trautmann

stat.MLMar 19, 2026

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

Authors: Samuel Gruffaz, Kyurae Kim, Fares Guehtar, Hadrien Duval-decaix, Pacôme Trautmann

Organizations: Université Paris-Saclay, ENS Paris-Saclay, Centre Borelli, F-91190 Gif-sur-Yvette, France. · University of Pennsylvania

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.

Figures & tables

Figure 1: Scheme of a dynamic HMC algorithm

Figure 2: Scheme of the construction of the index set sampled with $\mathbf{p}_{h}$ , based on [ 25 , Figure 1]

Figure 3: Construction of probabilities

\mathbf{q}^{\textup{BPS}}_{h}

in the example of sampling

q_{0},p_{0}

and

\Phi_{h}^{\circ(3)}(q_{0},p_{0})

with

\mathbf{q}^{\textup{BPS}}_{h}(\cdot|\mathsf{I}-3,\Phi_{h}^{\circ(3)}(q_{0},p_{0}))

Figure 4: Lebesgue density related to the limit time distribution

\mathcal{L}_{\textup{time},T_{0},\infty}^{\textup{MUL}},\mathcal{L}_{\textup{time},T_{0},\infty}^{\textup{BPS}}

under the assumption of Proposition 2 .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: For an index set

\mathsf{I}=[-1:6]

, the multinouilli distribution

\text{Multinouilli}((q_{i})_{i\in\mathsf{I}})

with normalized weights

\sum_{i\in\mathsf{I}}q_{i}=1

is split into its maximal uniform part on

\mathsf{I}^{\text{last}}

, i.e.,

|\mathsf{I}^{\text{last}}|\min_{i\in\mathsf{I}^{\text{last}}}q_{i}\mathcal{U}(\mathsf{I}^{\text{last}})

(shown in blue) and the remaning part

(1-|\mathsf{I}^{\text{last}}|\min_{i\in\mathsf{I}^{\text{last}}}q_{i})\text{multinouilli}((a_{i})_{i\in\mathsf{I}})

with

a_{i}=q_{i}-\mathrm{1}_{\mathsf{I}^{\text{last}}}(i)\min_{i\in\mathsf{I}^{\text{last}}}q_{i}

. This principle is applied to

q_{i}=\mathbf{q}^{\textup{BPS}}_{h}(i|\mathsf{I},q,p)/\sum_{j\in\mathsf{I}}\mathbf{q}^{\textup{BPS}}_{h}(j|\mathsf{I},q,p)

for any

\mathsf{I}\sim\mathbf{p}_{h}(\cdot|q,p)

and

q,p\in\mathsf{D}_{\alpha}\times\mathsf{E}_{\alpha,r}

Figure 6: Graphs of the functions involved in ( 87 ).

Figure 7: Graphs of the functions involved in ( 85 ).

Explore similar work

Gaussian Invariant Markov Chain Monte Carlo
Jun 26, 2025Michalis K. Titsias, Angelos Alexopoulos, Siran Liu +1Markov Chain Monte Carlo Variance Reduction
Google DeepMind, UK · Athens University of Economics and Business, Greece · UCL, UK
Multirate Stein Variational Gradient Descent for Efficient Bayesian Sampling
Apr 5, 2026Arash SarsharStein Variational Gradient Descent Bayesian Inference
Department of Computer Engineering and Computer Science, California State University, Long Beach, 90840, CA, USA
Amortised Inference through One-Step Implicit Sampling
Oct 8, 2026Vincent Pauline, Kirill Tamogashev, Arran Carter +3Amortized Inference Posterior Sampling
Technical University of Munich · Munich Center for Machine Learning · University of Edinburgh +1

Jun 26, 2025J/K move · Enter open · S save

Gaussian Invariant Markov Chain Monte Carlo

Michalis K. Titsias, Angelos Alexopoulos, Siran Liu, Petros Dellaportas

Google DeepMind, UK · Athens University of Economics and Business, Greece · UCL, UK

Markov Chain Monte Carlo Variance Reduction

Open paper AskPDF arXiv

We develop sampling methods, which consist of Gaussian invariant versions of random walk Metropolis (RWM), Metropolis adjusted Langevin algorithm (MALA) and second order Hessian or Manifold MALA. Unlike standard RWM and MALA, we show that Gaussian invariant sampling can lead to ergodic estimators with improved statistical efficiency. This is due to a remarkable property of Gaussian invariance that allows us to obtain exact analytical solutions to the Poisson equation for Gaussian targets. These solutions can be used to construct efficient and easy to use control variates for variance reduction of estimators under any intractable target. We demonstrate the new samplers and estimators in several examples, including high dimensional targets in latent Gaussian models where we compare against several advanced methods and obtain state-of-the-art results. We also provide theoretical results regarding geometric ergodicity, and an optimal scaling analysis that shows the dependence of the optimal acceptance rate on the Gaussianity of the target.

Abstract

Explore similar work

Gaussian Invariant Markov Chain Monte Carlo

Multirate Stein Variational Gradient Descent for Efficient Bayesian Sampling

Amortised Inference through One-Step Implicit Sampling