Mixing Of The No-u-turn Sampler And The Geometry Of Gaussian Concentration

In this talk, I will present new results on the mixing time of the No-U-Turn Sampler (NUTS). We show that when NUTS is initialized in the concentration region of the standard Gaussian measure, its mixing time scales as d^{1/4}, up to logarithmic factors, where d is the dimension – an estimate expected to be sharp. A key insight is that concentration of measure leads to uniformity in NUTS’ locally adapted transitions, which we formalize using an extension of a recently introduced coupling framework (see https://arxiv.org/abs/2308.04634) to a broader class of accept/reject chains. We interpret NUTS as one such chain, where the accept chain behaves more uniformly, making it easier to analyze. Additionally, I will discuss a previously unnoticed issue with NUTS’ path length adaptation, which we uncovered during the analysis. This is joint work with Stefan Oberdörster (Bonn). For more details, see our companion paper https://www.arxiv.org/abs/2410.06978.