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

Technische Samenvatting: Een Profiel-Scheidingskader voor Kwantitatieve Convergentie van No-U-Turn Samplers

Probleemstelling
Hamiltonian Monte Carlo (HMC) genereert verre voorstellen door Hamiltonian-trajecten te simuleren, maar de efficiëntie ervan is kritiek afhankelijk van de integratietijd. Trajecten die te kort zijn, resulteren in minimale beweging, terwijl trajecten die te lang zijn, bezochte regio's opnieuw doorkruisen, wat rekenkracht verspilt. De No-U-Turn Sampler (NUTS) pakt dit aan door adaptief een leapfrog-baan te construeren en deze te termineren wanneer eindpuntdiagnostiek wijst op een "U-turn" (momentumvectoren die terugwijzen naar het startpunt). Hoewel NUTS centraal staat in het praktische succes van probabilistische programmeersystemen (bijv. Stan, PyMC), heeft de staat-afhankelijke, recursieve stopregel historisch gezien de ontwikkeling van een kwantitatieve mengtheorie belemmerd. Bestaande niet-asymptotische grenzen voor NUTS hebben grotendeels geleund op Gaussische doelstructuren, waarbij de willekeurige U-turn diagnostiek concentreert rond een deterministische sinusfunctie. Het uitbreiden van deze resultaten naar algemene sterk log-concaaf doelwitten blijft een aanzienlijke uitdaging vanwege de gezamenlijke afhankelijkheid van de transitie van verversde momentum, willekeurige verdubbelingsbeslissingen, numerieke energie-fouten en de specifieke selectieregel.

Methodologie
Dit artikel introduceert een Profiel-Scheidingskader om kwantitatieve convergentie vast te stellen voor multinomiale en gebiaste-progressieve NUTS-varianten op $(m, L)$-sterk log-concaaf doelwitten die voldoen aan Frobenius-Hessiaanse regulariteit. De kernmethodologie behelst het ontkoppelen van het adaptieve stopmechanisme van de menganalyse via de volgende stappen:

1. Stationair U-Turn Profiel: De auteur definieert een deterministisch populatie-niveau object, het stationaire profiel $u(t) = \mathbb{E}[V_0^\top (X_t - X_0)]$, dat de evenwichtsmediaan van de eindpuntdiagnostiek gebruikt door NUTS representeert. Voor algemene doelwitten vervangt dit de expliciete Gaussische sinusfuncties.
2. Profiel-Scheiding: Er wordt een voldoende voorwaarde geïntroduceerd waarbij een specifieke diepte $k^*$ "profiel-gescheiden" is. Dit vereist dat het profiel $u(t)$ uniform positief is bij alle pre-terminale dyadische duurders, en uniform negatief bij de kandidaat terminale duur, met een marge van de orde $d/\sqrt{m}$.
3. Intrinsieke Diagnostiek Stabiliteit: Het kader kwantificeert de afwijking tussen de praktische numerieke diagnostiek (gebaseerd op leapfrog) en het exacte populatieprofiel. Dit omvat het begrenzen van:
   • De concentratie van exacte scalaire diagnostiek rond $u(t)$.
   • De leapfrog numerieke fout in deze diagnostiek.
   • Het falen van uniforme energievensters.
   • Het falen van positiviteit op zeer korte intervallen.
4. Terminale-Diepte Certificering: Onder de aanname dat de profiel-scheidingsmarge de gecombineerde stochastische en numerieke fouten overstijgt, bewijst de auteur dat op een gebeurtenis met hoge waarschijnlijkheid elke realisatie van de willekeurige verdubbelingsbeslissingen termineert bij dezelfde cardinaliteit $K^*$ via een genuïne U-turn, strikt vóór de maximale diepte-cap.
5. Terminale-Diepte-naar-Conductance Transfer: Zodra een gemeenschappelijke terminale diepte en energievenster gecertificeerd zijn, wordt aangetoond dat de NUTS-transitie een expliciete mengeling bevat van fixed-index leapfrog-voorstellen. De auteur maakt gebruik van de initiële-punt symmetrie van willekeurige verdubbeling en detailed-balance identiteiten om positieve operatoren te construeren (orthogonale projecties voor multinomiaal, twee-stap skeletten voor gebiaste-progressief) die de toepassing van Cheeger isoperimetrie mogelijk maken om beperkte conductance-grenzen af te leiden.

Kernbijdragen

1. Doelwit-Onafhankelijk Stopcertificaat: Het artikel abstraheert het deterministische profielmechanisme uit Gaussische analyses naar "profiel-scheiding", een voorwaarde die toepasbaar is op algemene sterk log-concaaf doelwitten. Dit biedt een intrinsiek certificaat dat tekens overdraagt aan elke volledige baan en elk recursief boom-substructuur die door de praktische leapfrog-boom wordt geïnspecteerd.
2. Terminale-Diepte-naar-Conductance Theorema: Een nieuw theorema stelt vast dat zodra een gemeenschappelijke terminale diepte gecertificeerd is, de adaptieve NUTS-transitie begrensd kan worden door fixed-time bewegingsschattingen. Dit scheidt het trajectprobleem (bewijzen waar de boom stopt) van het mengprobleem (bewijzen dat de kernel sneden kruist).
3. Positieve Operatoren voor Niet-Lazy Kernels: De auteur demonstreert dat de oorspronkelijke multinomiale en gebiaste-progressieve kernels (zonder kunstmatige lazificatie) positieve spectrale eigenschappen bezitten. Multinomiale re-rooting wordt getoond als een orthogonale projectie, terwijl de twee-stap skelet van de gebiaste-progressieve kernel positief semidefinitief is, wat conductance-argumenten mogelijk maakt zonder de sampler te modificeren.
4. Algemene Traject en Numerieke Analyse: Het werk levert evenwichtsidentiteiten voor niet-lineaire profielen, gemiddelde-kwadratische verplaatsingsongelijkheid en universele initiële-positiviteitsgrenzen. Het vestigt concentratie van exacte diagnostiek en deterministische leapfrog-naar-flow vergelijkingen zonder dat grenzen op de volledige Hamiltonian Jacobiaan vereist zijn.
5. Verificatieroutes: Het artikel biedt specifieke verificatieroutes voor het intrinsieke certificaat, inclusief spectrale representaties voor niet-lineaire producten, perturbatieve grenzen voor bijna-isotrope doelwitten, en voorwaarden voor metriek-adaptatie om lineaire anisotropie te verwijderen.

Resultaten
Het hoofdbestek (Theorem 3.7) levert onvoorwaardelijke transitiegrenzen voor warm-start mixing. Laat $T^*$ de geselecteerde fysieke trajectlengte zijn en $a^* = \sqrt{m}T^*$. Het aantal transities $n$ vereist om een totale variatie-fout $\epsilon$ te bereiken, wordt begrensd door:

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

waarbij $\kappa = L/m$ de conditiegetal is en $\gamma$ gerelateerd is aan de Hessian-regulariteit.

Wat betreft computationele arbeid, maakt het artikel onderscheid tussen gecertificeerde en ongecertificeerde transities. Op de certificeringsgebeurtenis is de kosten proportioneel aan de geselecteerde diepte $K^*$. Zonder aanvullende restricties op de maximale diepte-cap, is de onvoorwaardelijke deterministische werk-grens proportioneel aan de maximale cap $K_{cap}$. Echter, de auteur biedt verfijnde verwachte en hoog-waarschijnlijkheidsgrenzen die interpoleren tussen $K^*$ en $K_{cap}$, waarbij de deterministische orde $K^* n$ wordt hersteld wanneer de cap vergelijkbaar is met de gecertificeerde diepte.

Voor Gaussische doelwitten herstelt het kader de dimensie-afhankelijkheid $\tilde{O}(d^{1/4})$ en karakteriseert het expliciet de "geaccelereerde" en "gevangen" regimes geïdentificeerd in eerdere Gaussische-specifieke literatuur, waarbij wordt getoond dat profiel-scheiding de twee-schaal dichotomie herstelt.

Betekenis en Claims
Het artikel claimt de eerste kwantitatieve mengtheorie te bieden voor praktische NUTS op algemene sterk log-concaaf doelwitten die niet leunt op Gaussische structuur of kunstmatige modificaties (zoals lazificatie of Metropolis-correcties). De primaire bijdrage is een traject-naar-mixing reductie, die aantoont dat het adaptieve stopmechanisme van praktische NUTS voorspelbaar genoeg werkt zodat fixed-time HMC-schattingen bruikbaar worden, mits het stationaire profiel gescheiden is van nul door de gecombineerde stochastische en numerieke fouten.

De auteur benadrukt dat de resultaten globaal en onvoorwaardelijk zijn met betrekking tot de transitiegrenzen, terwijl computationele arbeid apart wordt behandeld om de realiteit te reflecteren dat ongecertificeerde transities (die naar de cap lopen) deel uitmaken van de Markov-keten. Het kader valideert het gebruik van vaste post-warmup metrieken om lineaire anisotropie te verwijderen en biedt een rigoureuze fundering voor het empirische succes van NUTS in hoog-dimensionale, niet-Gaussische omgevingen. Het artikel claimt niet dat profiel-scheiding noodzakelijk is voor snelle mixing, maar stelt dat het een voldoende voorwaarde is die de analyse van adaptieve HMC over een brede klasse van doelwitten verenigt.