On Accelerated Mixing of the No-U-turn Sampler

2025/07/17 by Stefan Oberdörster, Oberdörster, Stefan
Computer Science · #Cellular Automata and Applications

paper · pdf · doi:10.48550/arxiv.2507.13259

Abstract

Recent progress on the theory of variational hypocoercivity established that Randomized Hamiltonian Monte Carlo -- at criticality -- can achieve pronounced acceleration in its convergence and hence sampling performance over diffusive dynamics. Manual critical tuning being unfeasible in practice has motivated automated algorithmic solutions, notably the No-U-turn Sampler. Beyond its empirical success, a rigorous study of this method's ability to achieve accelerated convergence has been missing. We initiate this investigation combining a concentration of measure approach to examine the automatic tuning mechanism with a coupling based mixing analysis for Hamiltonian Monte Carlo. In certain Gaussian target distributions, this yields a precise characterization of the sampler's behavior resulting, in particular, in rigorous mixing guarantees describing the algorithm's ability and limitations in achieving accelerated convergence.

Citations

• The Within-Orbit Adaptive Leapfrog No-U-Turn Sampler
• Convergence of non-reversible Markov processes via lifting and flow Poincaré inequality
• The No-Underrun Sampler: A Locally-Adaptive, Gradient-Free MCMC Method
• Space-time divergence lemmas and optimal non-reversible lifts of diffusions on Riemannian manifolds with boundary
• Hamiltonian Monte Carlo vs. event-chain Monte Carlo: an appraisal of sampling strategies beyond the diffusive regime
• Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration
• 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
• Non-reversible lifts of reversible diffusion processes and relaxation times
• On the convergence of dynamic implementations of Hamiltonian Monte Carlo and no U-turn samplers
• When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?
• Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps
• Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
• Composable Effects for Flexible and Accelerated Probabilistic Programming in NumPyro
• Programming With Models: Writing Statistical Algorithms for General Model Structures With NIMBLE
• The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
• Optimal tuning of the Hybrid Monte-Carlo Algorithm

Related

• The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
• Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration
• Generalizing the No-U-Turn Sampler to Riemannian Manifolds
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Randomized Hamiltonian Monte Carlo as Scaling Limit of the Bouncy Particle Sampler and Dimension-Free Convergence Rates