A Profile-Separation Framework for Quantitative Convergence of No-U-Turn Samplers

Technical Summary: A Profile-Separation Framework for Quantitative Convergence of No-U-Turn Samplers

Problem Statement
Hamiltonian Monte Carlo (HMC) generates distant proposals by simulating Hamiltonian trajectories, but its efficiency is critically dependent on the integration time. Trajectories that are too short yield minimal movement, while those that are too long retrace visited regions, wasting computation. The No-U-Turn Sampler (NUTS) addresses this by adaptively constructing a leapfrog orbit and terminating it when endpoint diagnostics indicate a "U-turn" (momentum vectors pointing back toward the start). While NUTS is central to the practical success of probabilistic programming systems (e.g., Stan, PyMC), its state-dependent, recursive stopping rule has historically obstructed the development of a quantitative mixing theory. Existing non-asymptotic bounds for NUTS have largely relied on Gaussian target structures, where the random U-turn diagnostics concentrate around a deterministic sine function. Extending these results to general strongly log-concave targets remains a significant challenge due to the joint dependence of the transition on refreshed momentum, random doubling decisions, numerical energy errors, and the specific selection rule.

Methodology
This paper introduces a Profile-Separation Framework to establish quantitative convergence for multinomial and biased-progressive NUTS variants on $(m, L)$-strongly log-concave targets satisfying Frobenius Hessian regularity. The core methodology involves decoupling the adaptive stopping mechanism from the mixing analysis through the following steps:

1. Stationary U-Turn Profile: The author defines a deterministic population-level object, the stationary profile $u(t) = \mathbb{E}[V_0^\top (X_t - X_0)]$, which represents the equilibrium mean of the endpoint diagnostics used by NUTS. For general targets, this replaces the explicit Gaussian sine functions.
2. Profile Separation: A sufficient condition is introduced where a specific depth $k^*$ is "profile separated." This requires the profile $u(t)$ to be uniformly positive at all pre-terminal dyadic durations and uniformly negative at the candidate terminal duration, with a margin of order $d/\sqrt{m}$.
3. Intrinsic Diagnostic Stability: The framework quantifies the deviation between the practical numerical diagnostics (leapfrog-based) and the exact population profile. This involves bounding:
   • The concentration of exact scalar diagnostics around $u(t)$.
   • The leapfrog numerical error in these diagnostics.
   • The failure of uniform energy windows.
   • The failure of positivity on very short intervals.
4. Terminal-Depth Certification: Under the assumption that the profile separation margin exceeds the combined stochastic and numerical errors, the author proves that on a high-probability event, every realization of the random doubling decisions terminates at the same cardinality $K^*$ via a genuine U-turn, strictly before the maximum-depth cap.
5. Terminal-Depth-to-Conductance Transfer: Once a common terminal depth and energy window are certified, the NUTS transition is shown to contain an explicit mixture of fixed-index leapfrog proposals. The author utilizes the initial-point symmetry of random doubling and detailed-balance identities to construct positive operators (orthogonal projections for multinomial, two-step skeletons for biased-progressive) that allow the application of Cheeger isoperimetry to derive restricted conductance bounds.

Key Contributions

1. Target-Independent Stopping Certificate: The paper abstracts the deterministic-profile mechanism from Gaussian analyses into "profile separation," a condition applicable to general strongly log-concave targets. This provides an intrinsic certificate that transfers signs to every full orbit and recursive subtree inspected by the practical leapfrog tree.
2. Terminal-Depth-to-Conductance Theorem: A new theorem establishes that once a common terminal depth is certified, the adaptive NUTS transition can be bounded by fixed-time movement estimates. This separates the trajectory problem (proving where the tree stops) from the mixing problem (proving the kernel crosses cuts).
3. Positive Operators for Non-Lazy Kernels: The author demonstrates that the original multinomial and biased-progressive kernels (without artificial lazification) possess positive spectral properties. Multinomial re-rooting is shown to be an orthogonal projection, while the biased-progressive kernel's two-step skeleton is positive semidefinite, enabling conductance arguments without modifying the sampler.
4. General Trajectory and Numerical Analysis: The work provides equilibrium identities for nonlinear profiles, mean-square displacement inequalities, and universal initial-positivity bounds. It establishes concentration of exact diagnostics and deterministic leapfrog-to-flow comparisons without requiring bounds on the full Hamiltonian Jacobian.
5. Verification Routes: The paper offers specific verification routes for the intrinsic certificate, including spectral representations for nonlinear products, perturbative bounds for near-isotropic targets, and conditions for metric adaptation to remove linear anisotropy.

Results
The main theorem (Theorem 3.7) provides unconditional transition bounds for warm-start mixing. Let $T^*$ be the selected physical trajectory length and $a^* = \sqrt{m}T^*$. The number of transitions $n$ required to reach total variation error $\epsilon$ is bounded by:

• Multinomial NUTS: $\tilde{O}\left( (1 + a^{*2}\kappa^2(1+\gamma)^{4/3}) \log(M/\epsilon) \right)$
• Biased-Progressive NUTS: $\tilde{O}\left( (1 + a^{*4}\kappa^3(1+\gamma)^2) \log(M/\epsilon) \right)$

where $\kappa = L/m$ is the condition number and $\gamma$ relates to Hessian regularity.

Regarding computational work, the paper distinguishes between certified and uncertified transitions. On the certification event, the cost is proportional to the selected depth $K^*$. Without additional restrictions on the maximum depth cap, the unconditional deterministic work bound is proportional to the maximum cap $K_{cap}$. However, the author provides refined expected and high-probability bounds that interpolate between $K^*$ and $K_{cap}$, recovering deterministic order $K^* n$ when the cap is comparable to the certified depth.

For Gaussian targets, the framework recovers the dimension dependence $\tilde{O}(d^{1/4})$ and explicitly characterizes the "accelerated" and "trapped" regimes identified in prior Gaussian-specific literature, showing that profile separation recovers the two-scale dichotomy.

Significance and Claims
The paper claims to provide the first quantitative mixing theory for practical NUTS on general strongly log-concave targets that does not rely on Gaussian structure or artificial modifications (such as lazification or Metropolis corrections). The primary contribution is a trajectory-to-mixing reduction, demonstrating that the adaptive stopping mechanism of practical NUTS behaves predictably enough for fixed-time HMC estimates to become useful, provided the stationary profile is separated from zero by the combined stochastic and numerical errors.

The author emphasizes that the results are global and unconditional regarding the transition bounds, while computational work is accounted for separately to reflect the reality that uncertified transitions (running to the cap) remain part of the Markov chain. The framework validates the use of fixed post-warmup metrics to remove linear anisotropy and provides a rigorous foundation for the empirical success of NUTS in high-dimensional, non-Gaussian settings. The paper does not claim that profile separation is necessary for rapid mixing, but rather that it is a sufficient condition that unifies the analysis of adaptive HMC across a broad class of targets.