mlsanityData to 7 Oct 2026

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

arXiv 2410.06978 ↗First posted 9 Oct 2024math.PR stat.MLcited by 3

Not on the map. Why?

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 23 of its 54 references that are in the map. First posted on arXiv 9 Oct 2024.

Builds on

23 of 54 references.

References · 23

  1. 2017A Conceptual Introduction to Hamiltonian Monte Carlocited by 207
  2. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  3. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  4. 2019Composable Effects for Flexible and Accelerated Probabilistic Programming in NumPyrocited by 187
  5. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 144
  6. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  7. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
  8. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  9. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
  10. 2013Hamiltonian Monte Carlo for Hierarchical Modelscited by 50
  11. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  12. 2018Coupling and Convergence for Hamiltonian Monte Carlocited by 36
11 more
  1. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  2. 2021Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlocited by 18
  3. 2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 12
  4. 2021Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimensioncited by 11
  5. 2020A general perspective on the Metropolis-Hastings kernelcited by 9
  6. 2024GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlocited by 9
  7. 2020Connecting the Dots: Numerical Randomized Hamiltonian Monte Carlo with State-Dependent Event Ratescited by 8
  8. 2022Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random stepscited by 8
  9. 2013Generalizing the No-U-Turn Sampler to Riemannian Manifoldscited by 5
  10. 2021The Apogee to Apogee Path Samplercited by 5
  11. 2023On the convergence of dynamic implementations of Hamiltonian Monte Carlo and No U-Turn Samplerscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025The Within-Orbit Adaptive Leapfrog No-U-Turn Samplercited by 2
  2. 2025On Accelerated Mixing of the No-U-turn Samplercited by 1
  3. 2026A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targetscited by 0