Local and Global Contraction Principles for MCMC Mixing

Sintesi Tecnica: Principi di Contrazione Locale e Globale per il Mixing MCMC

Enunciato del Problema
Il documento affronta l'analisi quantitativa dei tempi di mixing per gli algoritmi Markov Chain Monte Carlo (MCMC). Nello specifico, mira a stabilire limiti rigorosi sulla velocità con cui la distribuzione di una catena di Markov converge alla sua distribuzione stazionaria (o a una sua approssimazione controllata). Gli autori si concentrano su due distinti setting algoritmici in cui le analisi standard di convergenza incontrano limitazioni:

1. Langevin Monte Carlo Proiettato (P-LMC): Algoritmi che operano su domini convessi compatti con potenziali lisci potenzialmente non convessi.
2. Metropolis–Hastings Indipendente (IMH): Algoritmi in cui il peso di importanza $w = d\pi/dq$ (rapporto tra target e proposta) può essere illimitato, rendendo banali gli argomenti di contrazione globale.

La sfida centrale è fornire garanzie di convergenza che siano esplicite, applicabili a una vasta classe di divergenze (oltre la Variazione Totale) e robuste rispetto alla non convessità e ai pesi di importanza a code pesanti (heavy-tailed).

Metodologia
Gli autori sviluppano un framework basato sulle Strong Data-Processing Inequalities (SDPI) applicate alla divergenza $E_\gamma$ (nota anche come divergenza hockey-stick) per $\gamma \ge 1$. La divergenza $E_\gamma$ è definita come $E_\gamma(\mu\|\nu) = \sup_{A} \{\mu(A) - \gamma\nu(A)\}$.

L'intuizione teorica centrale è che la divergenza $E_\gamma$ funge da divergenza "maestra". Attraverso una rappresentazione integrale (Equazione 2 nel documento), il controllo dell'intero profilo di $E_\gamma(\mu\|\nu)$ e $E_\gamma(\nu\|\mu)$ permette di derivare limiti di convergenza per una vasta classe di divergenze $f$ (incluse KL, $\chi^2$ e divergenze di Rényi) e divergenze di Rényi.

Il documento impiega due distinti strategie di contrazione adattate alla geometria dei rispettivi algoritmi:

1. Contrazione Globale: Per P-LMC, gli autori decompongono il kernel di transizione in un passo di drift, un passo di smoothing gaussiano e una proiezione. Sfruttano il fatto che lo smoothing gaussiano su un insieme compatto induce una contrazione globale stretta nella divergenza $E_\gamma$.
2. Contrazione Locale: Per IMH con pesi illimitati, la contrazione globale fallisce perché la catena può rifiutare le proposte con probabilità prossima a 1. Gli autori introducono un coefficiente di contrazione locale definito su un "core" $C_R = \{w \le R\}$. Essi dimostrano che questo coefficiente locale controlla la probabilità di rifiuto puntuale sul core, mentre l'errore al di fuori del core è governato dal profilo della coda $H_R = \pi(w > R)$.

Contributi Chiave e Risultati

1. SDPI Globale per il Langevin Monte Carlo Proiettato (P-LMC)

• Gestione della Non Convessità: Gli autori dimostrano che per potenziali lisci su un insieme convesso compatto, P-LMC esibisce una convergenza esponenziale nella divergenza $E_\gamma$ per tutti i $\gamma \ge 1$. Fondamentalmente, questo risultato non richiede che il potenziale sia convesso.
• Coefficienti Espliciti: Il coefficiente di contrazione è derivato esplicitamente in base al diametro dell'insieme dopo il passo di drift ma prima dello smoothing gaussiano. Il tasso dipende dal rapporto tra questo diametro e la scala del rumore $\sqrt{\eta}$.
• Batching Arbitrario: Il framework accoglie schemi di campionamento random-batch arbitrari (es. campionamento di Poisson, campionamento senza reinserimento). Il tasso di convergenza è espresso come una media dei coefficienti di contrazione specifici per ogni batch, offrendo limiti più stretti rispetto alle assunzioni di liscezza worst-case quando la liscezza del batch varia.
• Trasferimento della Divergenza: Controllando sia i profili forward che reverse di $E_\gamma$, gli autori derivano limiti di convergenza espliciti per le divergenze KL, $\chi^2$ e di Rényi.

2. SDPI Locale per il Metropolis–Hastings Indipendente (IMH)

• Definizione del Coefficiente Locale: Per il core $C_R = \{w \le R\}$, gli autori definiscono un coefficiente di contrazione hockey-stick locale $\rho_\alpha(R)$. Dimostrano che, sotto una proposta non atomica, questo coefficiente upper-bounds direttamente la probabilità di rifiuto $r(x)$ per ogni $x \in C_R$.
• Limiti Adattivi alla Coda: Il limite di convergenza è formulato in termini del profilo della coda $H_R = \pi(w > R)$ e del tasso di contrazione locale. Il limite assume la forma:
  $$E_\gamma(\mu_k\|\pi) \lesssim (L+1) \left[ e^{-k H_R/R} + H_R \right]$$
  dove $L$ è la costante di warm-start.
• Regimi a Code Pesanti: A differenza di lavori precedenti che si basano su assunzioni di momenti finiti ($E_q[w^p] < \infty$), questa formulazione rimane efficace anche quando non esiste alcun momento finito di ordine $p > 1$. Gli autori dimostrano ciò con un esempio in cui $E_q[w^p] = \infty$ per ogni $p > 1$, eppure il loro limite basato sul profilo della coda fornisce un tasso di convergenza esplicito (seppur lento).
• Recupero dei Tassi Esistenti: Sotto assunzioni di warm-start e condizioni di momenti finiti, i limiti derivati recuperano i tassi polinomiali netti stabiliti in lavori precedenti (es. [DJKW24]).

Significatività e Rivendicazioni
Il documento sostiene di fornire una prospettiva strutturale unificata sul mixing MCMC attraverso la lente della divergenza $E_\gamma$ e dei principi di contrazione.

• Per P-LMC: Offre una "spiegazione pulita" del perché la contrazione globale funzioni su domini compatti: lo step di smoothing gaussiano contrae il profilo hockey-stick una volta che l'immagine pre-rumore ha un diametro limitato. Ciò consente garanzie di convergenza su potenziali non convessi dove le precedenti analisi di tempo di mixing strette (spesso limitate a contesti convessi) fallivano.
• Per IMH: Sposta l'analisi dalla ergodicità uniforme globale (che fallisce per pesi illimitati) a un framework di contrazione locale. Questo approccio scinde il comportamento di mixing sul core ad alta probabilità dal comportamento della coda, fornendo uno strumento più flessibile e adattivo per analizzare algoritmi con pesi di importanza a code pesanti.
• Vantaggio Metodologico: L'uso della divergenza $E_\gamma$ permette agli autori di dimostrare un singolo limite di "profilo completo" che implica la convergenza per una vasta classe di divergenze $f$, piuttosto che dimostrare risultati separati per le distanze TV, KL o $\chi^2$.

Gli autori mantengono la modestia riguardo l'ottimalità, notando che, sebbene i loro coefficienti di contrazione a singolo step siano stretti per specifici potenziali non convessi, i limiti multi-step potrebbero essere migliorati analizzando profili di SDPI non lineari che tracciano il livello di divergenza, piuttosto che applicare linearmente un singolo coefficiente worst-case. Identificano inoltre l'estensione di questo punto di vista a profili di contrazione non lineari per kernel più complessi (come MALA) come una direzione per il lavoro futuro.