Self-Certifying Transport MCMC via Dual Spectral-Gap Certificates

Sintesi Tecnica: MCMC a Trasporto Auto-Certificante tramite Certificati di Dual Gap Spettrale

1. Definizione del Problema

Il campionamento Markov Chain Monte Carlo (MCMC) rimane lo standard per il calcolo Bayesiano, eppure la verifica della convergenza è una sfida aperta. I professionisti si affidano a diagnostiche euristiche (ad esempio, $\hat{R}$, grafici a traccia, stime dell'efficacia del campione) che possono rilevare patologie ma non possono certificare rigorosamente la convergenza. Sebbene i limiti del gap spettrale forniscano teoricamente tali certificati, essi sono stati raramente praticabili perché richiedono un controllo rigoroso di quantità (come l'oscillazione dei pesi di importanza) che dipendono dalla distribuzione target ignota.

Questo problema è esacerbato dall'ascesa di proposte apprese e adattive, specificamente quelle che utilizzano flussi di normalizzazione per l'Independence Metropolis–Hastings (IMH). Sebbene questi flussi migliorino il mixing empirico, il kernel di transizione stesso diventa un oggetto appreso ad alta dimensionalità, rendendo difficile l'auditabilità. La domanda centrale affrontata è: Un processo di proposta appreso può certificare la propria convergenza?

2. Metodologia: Il Framework CerT-MCMC

Gli autori propongono CerT-MCMC, un framework che equipaggia il MCMC a trasporto appreso con certificati di convergenza automatici e rigorosi derivati dallo stesso flusso di normalizzazione utilizzato come proposta IMH.

Meccanismo Core:
Un flusso di normalizzazione $T_\phi$ mappa una riferimento Gaussiano $q_0$ verso un'approssimazione della distribuzione target $\pi$. Nello spazio latente $z$, la probabilità di accettazione IMH dipende dal rapporto di peso di importanza $w(z) = \pi_z(z)/q_0(z) = e^{r(z)}$, dove $r(z)$ è il residuo del log-peso. Se $T_\phi$ è perfetto, $r(z)$ è costante; altrimenti, l'oscillazione di $r(z)$ misura la qualità del trasporto. Il teorema di Mengersen–Tweedie afferma che il gap spettrale $\gamma$ del kernel IMH è limitato inferiormente da $2/(1 + e^C)$, dove $C = \text{osc}(r)$ è l'oscillazione del log-peso sul supporto della proposta.

Il framework sviluppa due certificati complementari per limitare questa oscillazione:

Certificato I: Il Certificato di Copertura (Covering Certificate)

• Approccio: Limita l'oscillazione sull'intero supporto della proposta utilizzando un argomento di copertura a campioni finiti. Aggiunge un termine di correzione Lipschitz all'intervallo dei campioni osservati per tenere conto delle lacune tra i punti di campionamento.
• Scalabilità: Il raggio di correzione scala come $O(n^{-1/D})$, dove $n$ è il numero di campioni di certificazione e $D$ è la dimensione.
• Limitazione: A causa della maledizione della dimensionalità, questo certificato diventa vacuo (non fornisce un limite utile) per dimensioni moderate ($D \gtrsim 6$) a dimensioni di campionamento pratiche. Gli autori dimostrano un limite inferiore mostrando che nessun algoritmo di valutazione puntuale può certificare l'oscillazione a supporto completo più velocemente di $\Omega(n^{-1/D})$.

Certificato II: Il Certificato del Core Quantilico (Quantile-Core Certificate)

• Approccio: Riconosce che per i flussi ben addestrati, $r(z)$ è altamente concentrato, con l'intera oscillazione guidata da outlier rari nei bordi; questo certificato restringe l'attenzione a un "core di residuo definito dai dati" $\tilde{G}_\rho$, che contiene la massa centrale $(1-2\rho)$ della proposta, definita dai quantili empirici di $r(z)$.
• Scalabilità: L'errore di probabilità del campione finito per la stima del quantile è $O(n^{-1/2})$, derivato dall'ineguaglianza di Dvoretzky–Kiefer–Wolfowitz, che è indipendente dalla dimensione ambiente $D$.
• Risultato: Fornisce un limite inferiore del gap spettrale computabile e ad alta confidenza per il kernel IMH ristretto a questo core. Le costanti di normalizzazione per i pesi ristretti si cancellano esattamente, permettendo al teorema di Mengersen–Tweedie di applicarsi direttamente.

Framework a Doppio Certificato:
I due certificati sono complementari. Il Certificato I offre una garanzia worst-case a supporto completo dove è trattabile ($D \lesssim 5$). Il Certificato II offre una garanzia di un core ad alta massa in tutte le dimensioni, riportando onestamente la frazione di coda non certificata. Insieme, formano una tassonomia diagnostica che distingue tra:

1. Successo del certificato completo: Entrambi non vacui.
2. Successo del certificato del core: Certificato II non vacuo, Certificato I vacuo (il flusso è buono; il collo di bottiglia è la prova di copertura).
3. Degradazione del trasporto: Certificato II non vacuo ma debole (reale declino della qualità del flusso).
4. Fallimento del trasporto: Certificato II vacuo (flusso scarso).

3. Contributi Chiave

1. Framework CerT-MCMC: Un sistema che fornisce certificati di gap spettrale automatici e rigorosi per il MCMC a trasporto appreso utilizzando il medesimo flusso di proposta.
2. Certificato di Copertura (I): Formalizza la barriera di copertura, dimostrando un limite inferiore worst-case $\Omega(n^{-1/D})$ per la certificazione puntuale a supporto completo, motivando la necessità di un approccio diverso in dimensioni più elevate.
3. Certificato del Core Quantilico (II): Sviluppa un certificato indipendente dalla dimensione ($O(n^{-1/2})$ di slack) che limita l'oscillazione su un core ad alta probabilità utilizzando i quantili empirici.
4. Validazione Empirica: Dimostra che la proxy del gap spettrale dal Certificato II segue l'efficienza di mixing effettiva (Effective Sample Size) entro il 7% nella regressione logistica bayesiana ($D=20$).
5. Potere Discriminante: Mostra tramite esperimenti di controllo negativo che il Certificato II discrimina la qualità del flusso con un fattore superiore a $10\times$, mentre i tassi di accettazione standard differiscono solo di $1.15\times$.

4. Risultati Sperimentali

Il framework è stato valutato su:

• Target Sintetici: Target "Banana" ($D=2$ a $20$). Il Certificato I è diventato vacuo a $D \ge 6$, mentre il Certificato II è rimasto non vacuo e stabile fino a $D=10$, e ha fornito un limite non vacuo a $D=20$ anche quando la capacità del flusso è degradata.
• Posteriori di Ingegneria Strutturale: Modelli "Sailboat" ($D=6$) e "Shear building" ($D=8$). Il Certificato I era vacuo per entrambi, ma il Certificato II ha rivelato che il flusso ha appreso il target $D=8$ meglio del target $D=6$, una distinzione che il Certificato I ha mancato.
• Regressione Logistica su Dati Reali: Dataset "Heart Disease" ($D=13$). Il Certificato II ha prodotto un forte gap spettrale ($\gamma \approx 0.64$), mentre il Certificato I rimaneva debole.
• Controllo Negativo: Confronto tra flussi ben addestrati, sotto-addestrati e mal specificati sul target "Banana" ($D=10$). Il Certificato II ha identificato con successo i flussi poveri (basso $\gamma$) nonostante tassi di accettazione simili.

5. Significatività e Rivendicazioni

Il documento sostiene di fornire il primo framework a doppio certificato per il MCMC a trasporto appreso che offre certificati di convergenza automatici e consapevoli della dimensione. La sua importanza primaria risiede in:

• Calcolo Bayesiano Auditabile: Trasformare il trasporto appreso da un "acceleratore black-box" a un oggetto auditabile dove la stessa mappa che propone i movimenti espone anche la geometria del residuo per la certificazione della convergenza.
• Distinzione dei Modi di Fallimento: Separare esplicitamente i "limiti delle tecniche di prova" (la barriera di copertura in alte dimensioni) dal "reale fallimento del trasporto". Le diagnostiche standard non possono fare questa distinzione.
• Utilità Pratica: Fornire una proxy del gap spettrale computabile che traccia l'efficienza di mixing effettiva, offrendo un'alternativa rigorosa alle diagnostiche euristiche per problemi di media dimensionalità.

Gli autori rimangono modesti riguardo ai limiti: il certificato si applica al kernel ristretto al core piuttosto che alla catena completa (sebbene il core catturi la stragrande maggioranza della massa), e il framework è attualmente specifico per l'Independence Metropolis–Hastings. Notano che per target di dati reali ad altissima dimensionalità ($D \ge 30$), è spesso richiesto il pre-condizionamento standard prima che il flusso possa approssimare efficacementamente la geometria.