Self-Certifying Transport MCMC via Dual Spectral-Gap Certificates

Résumé Technique : CerT-MCMC via des Certificats de Gap Spectral Dual

1. Énoncé du Problème

L'échantillonnage de Monte Carlo par chaînes de Markov (MCMC) reste la norme pour le calcul bayésien, pourtant la vérification de la convergence demeure un défi ouvert. Les praticiens s'appuient sur des diagnostics heuristiques (par exemple, $\hat{R}$, les graphiques de trajectoire, les estimations de la taille d'échantillon effectif) qui peuvent détecter des pathologies mais ne peuvent pas certifier rigoureusement la convergence. Bien que les bornes de gap spectral fournissent théoriquement de tels certificats, elles ont rarement été pratiques car elles nécessitent un contrôle étroit de quantités (comme l'oscillation des poids d'importance) qui dépendent de la distribution cible inconnue.

Ce problème est exacerbé par l'essor des propositions apprises et adaptatives, spécifiquement celles utilisant des flux de normalisation pour l'Independence Metropolis–Hastings (IMH). Bien que ces flux améliorent le mélange empirique, le noyau de transition lui-même devient un objet de haute dimension appris, rendant l'auditabilité difficile. La question centrale abordée est la suivante : Un flux appris peut-il certifier sa propre convergence ?

2. Méthodologie : Le Cadre CerT-MCMC

Les auteurs proposent CerT-MCMC, un cadre qui équipe le MCMC à transport appris de certificats de convergence automatiques et rigoureux dérivés du même flux de normalisation utilisé comme proposition IMH.

Mécanisme Central :
Un flux de normalisation $T_\phi$ mappe une référence gaussienne $q_0$ vers une approximation de la distribution cible $\pi$. Dans l'espace latent $z$, la probabilité d'acceptation IMH dépend du rapport de poids d'importance $w(z) = \pi_z(z)/q_0(z) = e^{r(z)}$, où $r(z)$ est le résidu du log-poids. Si $T_\phi$ est parfait, $r(z)$ est constant ; sinon, l'oscillation de $r(z)$ mesure la qualité du transport. Le théorème de Mengersen–Tweedie stipule que le gap spectral $\gamma$ du noyau IMH est minoré par $2/(1 + e^C)$, où $C = \text{osc}(r)$ est l'oscillation du log-poids sur le support de la proposition.

Le cadre développe deux certificats complémentaires pour borner cette oscillation :

Certificat I : Le Certificat de Recouvrement (Covering Certificate)

• Approche : Borne l'oscillation sur l'ensemble du support de la proposition en utilisant un argument de recouvrement à échantillon fini. Il ajoute un terme de correction de Lipschitz à la plage des échantillons observés pour tenir compte des écarts entre les points d'échantillonnage.
• Échelle : Le rayon de correction évolue en $O(n^{-1/D})$, où $n$ est le nombre d'échantillons de certification et $D$ est la dimension.
• Limitation : En raison de la malédiction de la dimension, ce certificat devient vacue (ne fournit plus de borne utile) pour des dimensions modérées ($D \gtrsim 6$) avec des tailles d'échantillons pratiques. Les auteurs prouvent une borne inférieure montrant qu'aucun algorithme d'évaluation ponctuelle ne peut certifier l'oscillation sur support complet plus rapidement que $\Omega(n^{-1/D})$.

Certificat II : Le Certificat de Noyau de Quantile (Quantile-Core Certificate)

• Approche : Reconnaît que pour des flux bien entraînés, $r(z)$ est hautement concentré, l'oscillation complète étant pilotée par de rares valeurs aberrantes dans les queues de distribution. Ce certificat restreint l'attention à un « noyau de résidus défini par les données » $\tilde{G}_\rho$, contenant la masse centrale $(1-2\rho)$ de la proposition, définie par les quantiles empiriques de $r(z)$.
• Échelle : La marge de probabilité d'échantillon fini pour l'estimation du quantile est de $O(n^{-1/2})$, dérivée de l'inégalité de Dvoretzky–Kiefer–Wolfowitz, ce qui est indépendant de la dimension ambiante $D$.
• Résultat : Il fournit une borne inférieure de gap spectral de haute confiance pour le noyau IMH restreint à ce noyau. Les constantes de normalisation pour les poids restreints s'annulent exactement, permettant l'application directe du théorème de Mengersen–Tweedie.

Cadre de Double Certificat :
Les deux certificats sont complémentaires. Le Certificat I offre une garantie de pire cas sur support complet là où elle est traitable ($D \lesssim 5$). Le Certificat II offre une garantie de noyau à haute masse dans toutes les dimensions, rapportant honnêtement la fraction de queue non certifiée. Ensemble, ils forment une taxonomie de diagnostic distinguant :

1. Succès de certificat complet : Les deux sont non vacues.
2. Succès de certificat de noyau : Certificat II non vacue, Certificat I vacue (le flux est bon ; la preuve de recouvrement est le goulot d'étranglement).
3. Dégradation du transport : Certificat II non vacue mais faible (déclin réel de la qualité du flux).
4. Échec du transport : Certificat II vacue (mauvais flux).

3. Contributions Clés

1. Cadre CerT-MCMC : Un système fournissant des certificats de gap spectral automatiques et rigoureux pour le MCMC à transport appris en utilisant le flux de proposition lui-même.
2. Certificat de Recouvrement (I) : Formalise la barrière de recouvrement, prouvant une borne inférieure de pire cas $\Omega(n^{-1/D})$ pour la certification de support complet ponctuelle, motivant la nécessité d'une approche différente en hautes dimensions.
3. Certificat de Noyau de Quantile (II) : Développe un certificat indépendant de la dimension (marge de $O(n^{-1/2})$) qui borne l'oscillation sur un noyau de haute probabilité en utilisant des quantiles empiriques.
4. Validation Empirique : Démontre que le proxy de gap spectral du Certificat II suit l'efficacité de mélange réelle (taille d'échantillon effectif) à moins de 7 % près sur une régression logistique bayésienne ($D=20$).
5. Pouvoir Discriminant : Montre via des expériences de contrôle négatif que le Certificat II discrimine la qualité du flux par un facteur supérieur à $10\times$, alors que les taux d'acceptation standards ne diffèrent que de $1,15\times$.

4. Résultats Expérimentaux

Le cadre a été évalué sur :

• Cibles Synthétiques : Cibles "Banana" ($D=2$ à $20$). Le Certificat I est devenu vacue à $D \ge 6$, tandis que le Certificat II est resté non vacue et stable jusqu'à $D=10$, et a fourni une borne non vacue à $D=20$ même lorsque la capacité du flux se dégradait.
• Postérieurs d'Ingénierie Structurelle : Modèles "Sailboat" ($D=6$) et "Shear building" ($D=8$). Le Certificat I était vacue pour les deux, mais le Certificat II a révélé que le flux apprenait mieux la cible $D=8$ que la cible $D=6$, une distinction que le Certificat I a manquée.
• Régression Logistique sur Données Réelles : Jeu de données "Heart Disease" ($D=13$). Le Certificat II a produit un gap spectral fort ($\gamma \approx 0,64$), tandis que le Certificat I est resté faible.
• Contrôle Négatif : Comparaison de flux bien entraînés, sous-entraînés et mal spécifiés sur la cible "banana" ($D=10$). Le Certificat II a identifié avec succès les mauvais flux (faible $\gamma$) malgré des taux d'acceptation similaires.

5. Signification et Revendications

L'article affirme fournir le premier cadre de double certificat pour le MCMC à transport appris offrant des certificats de convergence automatiques et conscients de la dimension. Sa signification primaire réside dans :

• Calcul Bayésien Auditable : Transformer le transport appris d'un « accélérateur boîte noire » en un objet auditable où la même application qui propose des mouvements expose également la géométrie des résidus pour la certification de convergence.
• Distinction des Modes de Défaillance : Séparer explicitement les « limitations de la technique de preuve » (la barrière de recouvrement en haute dimension) des « échecs réels de transport ». Les diagnostics standards ne peuvent faire cette distinction.
• Utilité Pratique : Fournir une borne de gap spectral calculable qui suit l'efficacité de mélange empirique, offrant une alternative rigoureuse aux diagnostics heuristiques pour des problèmes de dimension modérée.

Les auteurs restent modestes quant aux limites : le certificat s'applique au noyau restreint plutôt qu'à la chaîne complète (bien que le noyau capture la vaste majorité de la masse), et le cadre est actuellement spécifique à l'Independence Metropolis–Hastings. Ils notent que pour des cibles de données réelles de très haute dimension ($D \ge 30$), un préconditionnement standard est souvent nécessaire avant que le flux puisse approximer efficacement la géométrie.