The Polynomial Stein Discrepancy for Assessing Moment Convergence

1. Enunciato del Problema

Nell'inferenza bayesiana, valutare la qualità dei campioni generati da algoritmi di campionamento approssimati (in particolare quelli distorti come Stochastic Gradient Langevin Dynamics, SGLD) rappresenta una critica "grande sfida".

• Limiti dei Metodi Esistenti:
  • Dimensione Effettiva del Campione (ESS): Non adatta per algoritmi asintoticamente distorti.
  • Kernel Stein Discrepancy (KSD): Attuale standard di riferimento. Tuttavia, soffre di complessità computazionale quadratica ($O(n^2)$) rispetto al numero di campioni, rendendola non fattibile per MCMC su larga scala.
  • Approssimazioni KSD a tempo lineare (FSSD, RFSD): Sebbene più veloci, spesso soffrono della maledizione della dimensionalità, richiedono un'estesa regolazione degli iperparametri (ad esempio, posizioni di test, mappe di caratteristiche) e, crucialmente, non riescono a rilevare la convergenza dei momenti.
• Il Divario Specifico: La KSD standard (utilizzando kernel IMQ) controlla la convergenza debole (metrica limitata-Lipschitz) ma non garantisce la convergenza nei momenti. Poiché i momenti (media, varianza) sono spesso le quantità di interesse primario nelle applicazioni di big data (dove il posteriore è spesso simile a una Gaussiana tramite il teorema di Bernstein-von Mises), l'incapacità di rilevare distorsioni nei momenti è un significativo svantaggio.

2. Metodologia: Polynomial Stein Discrepancy (PSD)

Gli autori propongono la Polynomial Stein Discrepancy (PSD), un'alternativa a tempo lineare alla KSD progettata specificamente per rilevare discrepanze nei primi $r$ momenti di una distribuzione.

Formulazione Principale

• Operatore di Stein: Utilizza l'operatore di Stein-Langevin del secondo ordine $A$ definito per una densità target $p(x)$:
  $$A g(x) = \Delta_x g(x) + \nabla_x g(x) \cdot \nabla_x \log p(x)$$
• Classe di Funzioni: Invece di uno Spazio di Hilbert a Kernel Riproduttivo (RKHS), la PSD vincola la classe di funzioni $\mathcal{G}$ allo span di polinomi di ordine $r$.
  $$\mathcal{G} = \text{span}\left\{ \prod_{i=1}^d x_i^{\alpha_i} : \sum \alpha_i \leq r \right\}$$
• Definizione della Discrepanza: La PSD è definita come il supremo dell'aspettativa dell'operatore di Stein su questa classe di polinomi, vincolata alla palla unitaria:
  $$\text{PSD} = \sup_{g \in \mathcal{G}, \|g\| \leq 1} \left| \mathbb{E}_{Q}[Ag(X)] \right|$$
• Soluzione in Forma Chiusa: Parametrizzando $g$ come una combinazione lineare di monomi con coefficienti $\beta$, l'ottimizzazione produce una soluzione in forma chiusa:
  $$\text{PSD} = \sqrt{\sum_{k=1}^J \bar{z}_k^2}$$
  dove $\bar{z}_k = \mathbb{E}_Q[A P_k(X)]$ e $P_k$ sono i monomi di base.
• Complessità Computazionale:
  • La PSD al quadrato può essere calcolata come una statistica V o statistica U.
  • La complessità è $O(nJ)$, dove $J = \binom{d+r}{d} - 1$.
  • Questo è lineare nel numero di campioni $n$, un miglioramento significativo rispetto all'$O(n^2)$ della KSD.
  • Per dimensioni molto elevate, una versione approssimata che esclude i termini di interazione può ridurre la complessità a $O(nd^r)$.

Test di Adattamento (Goodness-of-Fit)

• Il lavoro propone un test basato sul bootstrap per l'ipotesi nulla $H_0: Q = P$.
• A differenza dei test asintotici per le alternative KSD a tempo lineare (che richiedono la stima di una matrice di covarianza sotto $P$), il test di bootstrap PSD ricampiona i pesi dai dati osservati $Q$.
• Questo approccio evita la necessità di campionare dal target intrattabile $P$ e dimostra empiricamente una potenza statistica superiore rispetto alle approssimazioni asintotiche.

3. Contributi Teorici Chiave

• Garanzia di Rilevamento dei Momenti (Proposizione 1):
  • Se il target $P$ è Gaussiano, $\text{PSD} = 0$ se e solo se i primi $r$ momenti della distribuzione del campione $Q$ corrispondono ai primi $r$ momenti di $P$.
  • Questo fornisce una giustificazione teorica rigorosa per l'uso della PSD specificamente per la convergenza dei momenti, una proprietà che la KSD standard non possiede.
• Potenza Asintotica (Corollario 3.0.2):
  • Nel limite di Bernstein-von Mises (regime di grandi dati dove il posteriore si avvicina a una Gaussiana), i test basati su PSD hanno una potenza asintotica che tende a 1 per il rilevamento di discrepanze nei primi $r$ momenti.
• Invarianza: Il metodo è invariante sotto trasformazioni lineari invertibili (ad esempio, whitening) quando applicato a target Gaussiani.

4. Risultati Sperimentali

Gli autori hanno valutato la PSD rispetto ai concorrenti: IMQ KSD (tempo quadratico), Gaussian KSD, FSSD (tempo lineare) e RFSD (tempo lineare).

• Potenza di Adattamento:
  • La PSD ha costantemente superato i concorrenti a tempo lineare (FSSD, RFSD) nel rilevare discrepanze nei momenti (varianza, curtosi).
  • Ad esempio, nel rilevare perturbazioni di varianza in dimensioni elevate ($d=20$), la PSD ha raggiunto una potenza statistica fino a 4 volte superiore rispetto ai concorrenti a tempo lineare e competitiva con la KSD a tempo quadratico.
  • La PSD con $r=4$ è stata l'unico metodo a raggiungere costantemente una potenza $\approx 1$ nel rilevare discrepanze di curtosi.
• Regolazione degli Iperparametri (SGLD):
  • In un compito di selezione della dimensione del passo per Stochastic Gradient Langevin Dynamics (SGLD), la PSD ($r=2,3,4$) ha correttamente identificato la dimensione del passo ottimale ($\epsilon=0.005$) che ha minimizzato la distorsione nella varianza posteriore, eguagliando le prestazioni della molto più lenta IMQ KSD.
• Efficienza Computazionale:
  • La PSD è ordini di grandezza più veloce della KSD.
  • Nell'esempio SGLD, la PSD è stata ~70 volte più veloce della KSD e ~7 volte più veloce della RFSD.
• Robustezza:
  • La PSD ha funzionato bene anche in contesti non Gaussiani (ad esempio, Regressione Logistica con prior di sparsità, Restricted Boltzmann Machines), sebbene la sua garanzia teorica sia più forte per target Gaussiani.

5. Significato e Impatto

• Scalabilità: La PSD colma il divario tra il rigore statistico della KSD e l'efficienza computazionale richiesta per l'inferenza bayesiana moderna su larga scala.
• Utilità Mirata: Affronta specificamente il "punto cieco" delle discrepanze di Stein esistenti: l'incapacità di rilevare distorsioni nei momenti. Questo è cruciale per algoritmi MCMC distorti dove la convergenza dei momenti è l'obiettivo primario.
• Praticità: Il metodo richiede una regolazione minima (solo l'ordine del polinomio $r$), ha un'interpretazione chiara (tracciamento di momenti specifici) ed è computazionalmente fattibile per dataset ad alta dimensionalità.
• Raccomandazione: Gli autori raccomandano l'uso di PSD con $r=2$ per i praticanti che utilizzano campionatori distorti (come SG-MCMC) per valutare efficientemente la qualità del campione e regolare gli iperparametri.

Conclusione

La Polynomial Stein Discrepancy offre un quadro innovativo a tempo lineare per valutare la qualità del campione nell'inferenza bayesiana. Sfruttando funzioni polinomiali all'interno del quadro di Stein, fornisce uno strumento teoricamente fondato, computazionalmente efficiente e statisticamente potente per rilevare la convergenza dei momenti, superando i limiti di scalabilità e regolazione dei metodi attuali di Kernel Stein Discrepancy.