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

Résumé Technique : Un cadre de séparation de profil pour la convergence quantitative des échantillonneurs No-U-Turn

Énoncé du Problème
L'échantillonnage de Monte Carlo Hamiltonien (HMC) génère des propositions lointaines en simulant des trajectoires hamiltoniennes, mais son efficacité dépend de manière critique du temps d'intégration. Des trajectoires trop courtes produisent un mouvement minimal, tandis que des trajectoires trop longues retracent les régions déjà visitées, gaspillant ainsi de la puissance de calcul. L'échantillonneur No-U-Turn (NUTS) répond à cela en construisant de manière adaptative une orbite de saut de grenouille (leapfrog) et en la terminant lorsqu'un diagnostic de point final indique un « U-turn » (vecteurs de quantité de mouvement pointant vers le départ). Bien que NUTS soit central au succès pratique des systèmes de programmation probabiliste (par exemple, Stan, PyMC), sa règle d'arrêt récursive et dépendante de l'état a historiquement entravé le développement d'une théorie de mélange quantitative. Les limites non asymptotiques existantes pour NUTS reposent largement sur des structures cibles gaussiennes, où les diagnostics de U-turn aléatoires se concentrent autour d'une fonction sinus déterministe. Étendre ces résultats à des cibles générales fortement log-concaves reste un défi important en raison de la dépendance conjointe de la transition vis-à-vis du moment rafraîchi, des décisions de doublement aléatoires, des erreurs d'énergie numériques et de la règle de sélection spécifique.

Méthodologie
Cet article introduit un cadre de séparation de profil pour établir la convergence quantitative des variantes multinomiales et progressives-biaisées de NUTS sur des cibles $(m, L)$-fortement log-concaves satisfaisant la régularité de Hessian de Frobenius. La méthodologie centrale consiste à découpler le mécanisme d'arrêt adaptatif de l'analyse de mélange par les étapes suivantes :

1. Profil de U-Turn Stationnaire : L'auteur définit un objet déterministe au niveau de la population, le profil stationnaire $u(t) = \mathbb{E}[V_0^\top (X_t - X_0)]$, qui représente la moyenne d'équilibre des diagnostics de point final utilisés par NUTS. Pour des cibles générales, cela remplace les fonctions sinus explicites gaussiennes.
2. Séparation de Profil : Une condition suffisante est introduite où une profondeur spécifique $k^*$ est dite « séparée par le profil ». Cela exige que le profil $u(t)$ soit uniformément positif à toutes les durées dyadiques pré-terminales et uniformément négatif à la durée terminale candidate, avec une marge d'ordre $d/\sqrt{m}$.
3. Stabilité Intrinsèque des Diagnostics : Le cadre quantifie l'écart entre les diagnostics numériques pratiques (basés sur le saut de grenouille) et le profil de population exact. Cela implique de borner :
   • La concentration des diagnostics scalaires exacts autour de $u(t)$.
   • L'erreur numérique du saut de grenouille dans ces diagnostics.
   • L'échec des fenêtres d'énergie uniformes.
   • L'échec de la positivité sur des intervalles très courts.
4. Certification de la Profondeur Terminale : Sous l'hypothèse que la marge de séparation du profil dépasse les erreurs stochastiques et numériques combinées, l'auteur prouve que, lors d'un événement de haute probabilité, chaque réalisation des décisions de doublement aléatoires se termine à la même cardinalité $K^*$ via un véritable U-turn, strictement avant la limite de profondeur maximale.
5. Transfert de la Profondeur Terminale à la Conductance : Une fois une profondeur terminale et une fenêtre d'énergie communes certifiées, la transition NUTS est montrée comme contenant un mélange explicite de propositions de saut de grenouille à indice fixe. L'auteur utilise la symétrie du point initial des doubles de la décision aléatoire et les identités de l'équilibre détaillé pour construire des opérateurs positifs (projections orthogonales pour le multinomial, squelettes en deux étapes pour le progressif-biaisé) permettant l'application de l'isopérimétrie de Cheeger pour dériver des bornes de conductance restreintes.

Contributions Clés

1. Certificat de l'Arrêt Indépendant de la Cible : L'article abstrait le mécanisme de profil déterministe des analyses gaussiennes vers la « séparation de profil », une condition applicable aux cibles générales fortement log-concaves. Cela fournit un certificat intrinsèque qui transfère les signes à chaque orbite complète et sous-arbre récursif inspecté par l'arbre de saut de grenouille pratique.
2. Théorème de Profondeur Terminale-à-Conductance : Un nouveau théorème établit qu'une fois une profondeur terminale commune certifiée, la transition NUTS adaptative peut être bornée par des estimations de mouvement à temps fixe. Cela sépare le problème de la trajectoire (prouver où le arbre s'arrête) du problème de mélange (prouver que le noyau traverse les coupes).
3. Opérateurs Positifs pour les Noyaux Non-Lents : L'auteur démontre que les noyaux originaux multinomiaux et progressifs-biaisés (sans la lénification artificielle) possèdent des propriétés spectrales positives. Le re-enracinement multinomial est montré comme étant une projection orthogonale, tandis que le squelette en deux étapes du noyau progressif-biaisé est semi-positif défini, permettant des arguments de conductance sans modifier l'échantillonneur.
4. Analyse Générale de Trajectoire et Numérique : Le travail fournit des identités d'équilibre pour les profils non linéaires, des inégalités de déplacement de moyenne quadratique et des bornes d'initialité-positivité universelles. Il établit la concentration des diagnostics exacts et des comparaisons déterministes de saut de grenouille-vers-flux sans nécessendre de bornes sur le Jacobien complet de l'Hamiltonien.
5. Routes de Vérification : L'article propose des routes de vérification spécifiques pour le certificat intrinsèque, incluant des représentations spectrales pour les produits non linéaires, des bornes perturbatives pour les cibles quasi-isotropes, et des conditions de l'adaptation de métrique pour supprimer l'anisotropie linéaire.

Résultats
Le théorème principal (Théorème 3.7) fournit des bornes de transition inconditionnelles pour le mélange en démarrage à chaud (warm-start). Soit $T^*$ la longueur de la trajectoire physique sélectionnée et $a^* = \sqrt{m}T^*$. Le nombre de transitions $n$ requis pour atteindre une erreur de variation totale $\epsilon$ est borné par :

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

où $\kappa = L/m$ est le nombre de condition et $\gamma$ se rapporte à la régularité de Hessian.

Concernant le travail de calcul, l'article distingue les transitions certifiées des non certifiées. Lors de l'événement de certification, le coût est proportionnel à la profondeur sélectionnée $K^*$. Sans restrictions supplémentaires sur la limite de profondeur maximale, la borne de travail déterministe inconditionnelle est proportionnelle à la limite maximale $K_{cap}$. Cependant, l'auteur fournit des bornes raffinées espérées et de haute probabilité qui interpolent entre $K^*$ et $K_{cap}$, retrouvant l'ordre déterministe $K^* n$ lorsque la limite est comparable à la profondeur certifiée.

Pour les cibles gaussiennes, le cadre retrouve la dépendance en dimension $\tilde{O}(d^{1/4})$ et caractérise explicitement les régimes « accélérés » et « piégés » identifiés dans la littérature antérieure spécifique aux gaussiennes, montrant que la séparation de profil récupère la dichotomie à deux échelles.

Signification et Revendications
L'article affirme fournir la première théorie de mélange quantitative pour le NUTS pratique sur des cibles générales fortement log-concaves qui ne repose pas sur la structure gaussienne ou sur des modifications artificielles (telles que la lénification ou les corrections de Metropolis). La contribution primaire est une réduction de la trajectoire au mélange, démontrant que le mécanisme d'arrêt adaptatif du NUTS pratique se comporte de manière suffisamment prévisible pour que les estimations de HMC à temps fixe deviennent utiles, à condition que le profil stationnaire soit séparé de zéro par les erreurs stochastiques et numériques combinées.

L'auteur souligne que les résultats sont globaux et inconditionnels concernant les bornes de transition, tandis que le travail de calcul est comptabilisé séparément pour refléter la réalité que les transitions non certifiées (courant jusqu'à la limite) font partie de la chaîne de Markov. Le cadre valide l'utilisation de métriques post-échauffement fixes pour éliminer l'anisotropie linéaire et fournit une base rigoureuse au succès empirique de NUTS dans des contextes de haute dimension non gaussiens. L'article ne prétend pas que la séparation de profil est nécessaire pour un mélange rapide, mais plutôt qu'elle est une condition suffisante qui unifie l'analyse de l'HMC adaptatif à travers une large classe de cibles.