Score-Repellent Monte Carlo: Toward Efficient Non-Markovian Sampler with Constant Memory in General State Spaces

Riassunto Tecnico: Score-Repellent Monte Carlo (SRMC)

1. Il Problema: L'inefficienza dei campionatori Markoviani

I metodi classici di Markov Chain Monte Carlo (MCMC), pur essendo fondamentali per l'inferenza bayesiana e il modellamento generativo, soffrono spesso di problemi di esplorazione in spazi di stato complessi (es. distribuzioni multimodali o paesaggi energetici accidentati). Il limite principale dei campionatori standard è la loro natura "memoryless" (senza memoria): la catena può rimanere intrappolata in un sottomodulo (metastabilità), continuando a visitare ripetutamente le stesse regioni e producendo campioni fortemente correlati.

Sebbene esistano approcci non-Markoviani che utilizzano la storia delle visite per scoraggiare le ridondanze (come i Self-Repellent Random Walks), questi presentano due ostacoli critici:

1. Costo di memoria: In spazi discreti grandi, memorizzare la storia richiede una memoria che cresce esponenzialmente con la dimensione dello spazio ($\Omega(N)$).
2. Inapplicabilità in spazi continui: In domini continui, la misura empirica delle visite è un oggetto a dimensione infinita, rendendo impossibile il conteggio esatto delle visite.

2. Metodologia: Il framework SRMC

Gli autori propongono Score-Repellent Monte Carlo (SRMC), un framework che introduce una dipendenza dalla storia in modo efficiente e generalizzato.

Il concetto chiave: Invece di memorizzare dove il campionatore è stato (conteggio delle visite), SRMC memorizza la media mobile dei valori dello score (il gradiente del log-target) lungo la traiettoria.

Componenti tecniche:

• Storia a memoria costante: Si mantiene una variabile $\theta_n \in \mathbb{R}^d$ che rappresenta la media cumulativa degli score osservati:
  $$\theta_{n+1} = \theta_n + \gamma_{n+1}(s(X_{n+1}) - \theta_n)$$
  dove $s(x) = \nabla \log \pi(x)$ è lo score. Poiché $\theta$ ha la stessa dimensione dello spazio di stato ($d$), la memoria richiesta è $O(d)$, ovvero costante rispetto alla cardinalità dello spazio.
• Target surrogato (Exponential Score Tilt): La storia viene utilizzata per modificare il target originale $\pi(x)$ in una famiglia di distribuzioni surrogate $\pi_\theta(x)$:
  $$\pi_\theta(x) \propto \pi(x) \exp(-\alpha \theta^\top s(x))$$
  Il parametro $\alpha$ controlla la forza della "repulsione". Quando il campionatore visita ripetutamente una regione, lo score in quella zona si allinea con $\theta$, rendendo il termine esponenziale piccolo e "spingendo" la catena verso zone meno esplorate.
• Wrapper generico: SRMC può essere applicato come "wrapper" su qualsiasi kernel MCMC esistente (Metropolis-Hastings, Langevin, HMC), rendendolo estremamente versatile.

3. Contributi Chiave

1. Efficienza di Memoria: Passaggio da una memoria $\Omega(|X|)$ a una memoria $\Omega(d)$, rendendo il campionamento non-Markoviano praticabile in spazi ad altissima dimensionalità.
2. Analisi Teorica Rigorosa: Gli autori utilizzano la teoria dell'Approssimazione Stocastica (SA) per dimostrare che:
   • La sequenza converge quasi certamente al target originale ($\theta_n \to 0$).
   • Esiste un Teorema del Limite Centrale (CLT) che quantifica la varianza dell'estimatore.
   • In determinati regimi, la varianza asintotica diminuisce con la forza della repulsione seguendo un ordine $O(1/\alpha)$.
3. Versatilità: Il framework è dimostrato efficace sia in spazi continui (tramite gradienti e matrici Hessiane) che in spazi discreti (tramite operatori di Stein discreti).

4. Risultati Sperimentali

Il paper presenta prove su diversi scenari:

• Spazi Continui (Gaussiane e Regressione Logistica): SRMC riduce drasticamente l'errore quadratico medio (MSE) rispetto ai campionatori base (MALA, HMC). In contesti di regressione logistica bayesiana, si osserva una riduzione significativa della varianza anche considerando il costo computazionale aggiuntivo (CPU time).
• Esplorazione di Modi (CIFAR-10 EBM): In modelli basati sull'energia (EBM) addestrati su immagini CIFAR-10, il campionatore standard (ULA) rimane intrappolato in un singolo modo. SR-ULA, invece, riesce a scoprire tutti i modi (classi di immagini) molto più rapidamente.
• Modelli Discreti (Static MNIST): Su modelli discreti ad alta dimensionalità, SRMC migliora la diversità dei campioni (misurata tramite il Vendi Score) e riduce la divergenza KL, facilitando il "mode-hopping" (il salto tra diverse cifre).

5. Significatività e Conclusioni

La significatività di SRMC risiede nella sua capacità di unire i benefici della campionatura non-Markoviana con la scalabilità dei metodi Markoviani.

Mentre i metodi precedenti richiedevano un compromesso tra memoria e precisione, SRMC offre un meccanismo di feedback negativo che "deforma" il campo di drift locale per evitare zone sovra-esplorate, mantenendo un costo computazionale per iterazione contenuto e una memoria minima. Questo lo rende un candidato ideale per applicazioni moderne di Machine Learning dove si lavora con modelli generativi complessi e spazi di configurazione vasti.