Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo

1. Problema e Contesto

Il lavoro affronta le sfide legate alla stima di aspettative $\nu(f) = \int f(x) \nu(dx)$ in statistica computazionale, dove il campionamento diretto dalla distribuzione target $\nu$ è impossibile o computazionalmente proibitivo (ad esempio, a causa di costanti di normalizzazione sconosciute).
Il metodo standard è il Markov Chain Monte Carlo (MCMC). Tuttavia, l'uso di algoritmi MCMC adattivi, che aggiornano i parametri di transizione basandosi sulla storia passata, introduce processi non markoviani. Questo complica notevolmente la teoria limite e richiede ipotesi tecniche forti (come l'adattamento decrescente o diminishing adaptation) per garantire la convergenza.

L'obiettivo specifico del paper è studiare le rate di convergenza quasi certe (almost sure convergence rates) per una classe specifica di algoritmi adattivi chiamati AIR (Adaptively Increasingly Rare). In questi algoritmi, l'adattamento dei parametri avviene sempre meno frequentemente nel tempo, il che permette di semplificare l'analisi matematica mantenendo buone prestazioni pratiche.

2. Metodologia

Gli autori sviluppano un'analisi teorica basata su tre pilastri fondamentali:

• Spazio degli stati aumentato: L'analisi viene condotta su uno spazio degli stati aumentato $\mathcal{Y} = \mathcal{X} \times \Phi$, dove $\Phi$ è uno spazio ausiliario. Questo approccio, ispirato da lavori recenti, permette di gestire problemi come la multimodalità della distribuzione target e include il caso classico non aumentato come sottocaso.
• Approssimazione Martingala e Equazione di Poisson: La strategia di prova principale si basa sulla decomposizione della somma di Monte Carlo utilizzando la soluzione dell'equazione di Poisson. La somma degli errori viene scomposta in:
  1. Una parte martingala ($M_n$).
  2. Un termine di resto ($R_m$) legato agli istanti di adattamento.
  3. Termini al bordo (iniziali e finali).
     La natura "rara" dell'adattamento (AIR) fa sì che molti termini complessi nella decomposizione si cancellino, eliminando la necessità di ipotesi tecniche come l'adattamento decrescente.
• Contrazione di Wasserstein: Al posto delle tradizionali ipotesi di ergodicità uniforme o geometrica, gli autori introducono una condizione di contrazione rispetto a una funzione simile alla distanza di Wasserstein ($W$). Assumono che i kernel di transizione $P_\gamma$ contraggano la distanza tra le distribuzioni in modo uniforme rispetto a un parametro $\gamma$.

3. Contributi Chiave

Il paper offre diversi contributi teorici significativi:

1. Rimozione di Ipotesi Tecniche: Dimostra che per gli algoritmi AIR, non è necessaria l'ipotesi di diminishing adaptation (adattamento decrescente) per ottenere leggi dei grandi numeri o rate di convergenza quasi certe. Questo è un vantaggio sostanziale rispetto alla teoria MCMC adattiva classica.
2. Quadro Generale di Contrazione: Fornisce risultati di convergenza basati su una contrazione di tipo Wasserstein, un quadro più generale che ricopre sia l'ergodicità uniforme che quella geometrica come casi particolari.
3. Rate di Convergenza Quasi Certi: Stabilisce limiti superiori per la velocità di convergenza delle somme di Monte Carlo normalizzate, mostrando che la convergenza è quasi certa con una velocità che si avvicina a quella della Legge dei Logaritmi Iterati (Law of the Iterated Logarithm).
4. Analisi del Regime "Piccolo $\beta$": Indaga il caso in cui la frequenza di adattamento è molto alta (piccolo $\beta$), mostrando che sotto condizioni aggiuntive (come l'adattamento "waning" e condizioni di Lipschitz uniformi), è possibile recuperare le stesse rate di convergenza ottimali ottenute per $\beta \ge 1$.

4. Risultati Principali

Sia $S_n f = \frac{1}{n} \sum_{j=1}^n f(X_j)$ la somma di Monte Carlo e $\nu(f)$ il valore atteso. Gli autori definiscono un fattore di normalizzazione $r(n)$.

• Teoremi di Convergenza: Sotto l'ipotesi di contrazione di Wasserstein (Assunzione 3.1) e condizioni sulla funzione di interesse (Lipschitziana e limitata o legata a una funzione di Lyapunov), dimostrano che:
  $$\lim_{n \to \infty} \frac{1}{r(n)} \left| \sum_{j=1}^n (f(X_j) - \nu(f)) \right| = 0 \quad \text{quasi certamente}.$$
  Dove $r(n)$ è scelto come $\sqrt{n}(\log n)^{1/2+\varepsilon}$ o $n^{1/2+\varepsilon}$.
• Comportamento del Cammino (Path-wise): Ne consegue che per quasi ogni traiettoria $\omega$, l'errore assoluto soddisfa:
  $$|S_n f(\omega) - \nu(f)| \le C(\omega) \frac{r(n)}{n}.$$
  Per $\varepsilon$ piccolo, il termine a destra decresce quasi come $1/\sqrt{n}$, che è la velocità ottimale attesa per variabili i.i.d.
• Casi Specifici (Sezione 4):
  • Ergodicità Uniforme: Se i kernel sono uniformemente ergodici, si ottiene la rate $O(n^{-1/2} (\log n)^{1/2+\varepsilon})$.
  • Ergodicità Geometrica: Se i kernel soddisfano condizioni di drift e minorizzazione, si ottengono rate simili, ma dipendenti dalla regolarità della funzione $f$ rispetto a una funzione di Lyapunov $V$.
  • Ergodicità di Harris Debole: Vengono trattati casi più generali basati su contrazioni deboli, estendendo la teoria a spazi di dimensione infinita o kernel complessi (es. pCN).

5. Significato e Impatto

Questo lavoro è significativo per la teoria MCMC adattiva per i seguenti motivi:

• Validazione Pratica degli Algoritmi AIR: Fornisce una giustificazione teorica rigorosa all'uso di strategie AIR, confermando che sacrificare la frequenza di adattamento non compromette la velocità di convergenza asintotica, ma semplifica drasticamente le condizioni necessarie per la prova.
• Generalità: L'uso della contrazione di Wasserstein permette di unificare diversi scenari di ergodicità (uniforme, geometrica, debole) sotto un'unica cornice teorica, rendendo i risultati applicabili a una vasta gamma di algoritmi moderni.
• Precisione delle Stime: Fornire limiti quasi certi (path-wise) invece di limiti in media (MSE) o distribuzionali (CLT) è cruciale per la pratica computazionale, poiché gli utenti eseguono solitamente una singola catena e necessitano di garanzie sulla singola traiettoria simulata.
• Ottimalità: Le rate ottenute sono vicine al limite inferiore teorico (Legge dei Logaritmi Iterati), suggerendo che gli algoritmi AIR sono efficienti quanto i metodi non adattivi o adattivi classici ottimali, ma con minori requisiti tecnici.

In sintesi, il paper stabilisce che gli algoritmi AIR offrono un compromesso ottimale tra flessibilità adattiva, semplicità analitica e prestazioni di convergenza quasi certe, rendendoli una scelta robusta per l'analisi bayesiana e computazionale avanzata.