Sintesi Tecnica: Approcci di Rilassamento Convesso per l'Optimal Transport ad Alta Dimensionalità

1. Enunciato del Problema

Il documento affronta le sfide computazionali e statistiche intrinseche nella risoluzione di problemi di Optimal Transport (OT) in alta dimensione. Sebbene l'OT sia un framework potente per confrontare distribuzioni di probabilità con fedeltà geometrica, la sua applicazione è ostacolata dalla "maledizione della dimensionalità". Nello specifico, il costo computazionale dei solutori OT standard cresce rapidamente con la dimensione del campione, e la complessità campionaria necessaria per stimare la distanza di Wasserstein scala esponenzialmente con la dimensione $d$. Le strategie di riduzione della dimensione esistenti, come le parametrizzazioni tramite reti neurali (che mancano di forti garanzie teoriche a causa dell'ottimizzazione non convessa) o le distanze di Wasserstein "sliced" (che approssimano ma non recuperano la vera distanza), spesso non forniscono una soluzione scalabile e teoricamente fondata per distribuzioni continue ad alta dimensione.

2. Metodologia

Gli autori propongono una famiglia di approcci di rilassamento convesso che sfruttano la località e la sparsità delle correlazioni all'interno di distribuzioni ad alta dimensione. Invece di ottimizzare sul piano di trasporto congiunto completo $\pi \in \mathcal{P}(X \times Y)$, i metodi approssimano il problema utilizzando marginali di ordine inferiore e statistiche di momenti sparsi.

2.1 Assunzioni Strutturali

L'approccio si basa sulla partizione delle coordinate $d$-dimensionali in $K$ cluster e sulla definizione di un grafo di riferimento $G$ che codifica la struttura di correlazione.

• Partizione dei Cluster: Le coordinate sono raggruppate in cluster $z_k = (x_k, y_k)$.
• Grafo di Riferimento: Un grafo $G$ con vertici che rappresentano i cluster e archi che rappresentano le interazioni a coppie. Il metodo assume che le dipendenze decadano con la distanza del grafo, permettendo approssimazioni sparse.

2.2 Framework di Rilassamento

Il documento introduce due livelli primari di rilassamento:

1. Rilassamento dei Marginali:

   • L'originale problema di OT viene rilassato imponendo vincoli solo sui marginali del piano di trasporto corrispondenti a singoli cluster ($\pi_k$) e a coppie di cluster connessi ($\pi_{ij}$) nel grafo $G$.
   • Positività: La non-negatività della misura globale è rilassata in vincoli di Semidefinitezza Positiva (PSD) sulla matrice a blocchi di questi marginali.
   • Formulazioni: Gli autori definiscono tre varianti:
     • $(OT_{mar})$: Include vincoli PSD e non-negatività (programmazione Doubly Non-Negative).
     • $(OT^1_{mar})$: Elimina il vincolo PSD globale, risultando in un problema di Programmazione Lineare (LP).
     • $(OT^2_{mar})$: Elimina il vincolo di non-negatività, risultando in un Programma Semidefinito (SDP) che può essere ulteriormente ridotto tramite conversione chordale.

2. Rilassamento dei Momenti dei Cluster:

   • Per gestire distribuzioni continue senza discretizzazione spaziale, i rilassamenti dei marginali vengono ulteriormente approssimati utilizzando rilassamenti dei momenti Sum-of-Squares (SOS).
   • Invece di ottimizzare su misure, le variabili sono matrici di momenti a dimensione finita ($M_k, M_{ij}$) derivate da una base polinomiale di grado $n$.
   • Innovazione Chiave: A differenza degli standard gerarchie SOS (ad esempio, Mula e Nouy [44]) che richiedono i momenti di tutti i monomi fino al grado $n$ (portando a una complessità di $O(d^{2n})$), questo metodo restringe la base ai cluster locali e agli archi del grafo di riferimento.
   • Complessità: L'SDP risultante coinvolge solo collezioni sparse di momenti. Se la dimensione del cluster e il grado di rilassamento sono fissi, la dimensione del problema scala linearmente con $d$ (specificamente $O(d)$) quando il grafo $G$ ha un tree-width limitato, risolvibile tramite decomposizione chordale.

2.3 Estrazione della Mappa di Trasporto

Le variabili duali del rilassamento SDP fornis spesso potenziali di Kantorovich approssimati. Limitando questi potenziali allo span della base polinomiale scelta, gli autori costruiscono una mappa di trasporto esplicita $\hat{T}(x) = x - \frac{1}{2}\nabla \hat{f}(x)$, offrendo un'alternativa interpretabile ai modelli generativi basati su reti neurali.

3. Contributi Chiave e Risultati Teorici

3.1 Modelli Gaussiani con Precisione Sparsa

Per misure Gaussiane $\mu = \mathcal{N}(m_1, \Sigma_1)$ e $\nu = \mathcal{N}(m_2, \Sigma_2)$ dove le matrici di precisione sono sparse rispetto a un grafo $G$:

• Convergenza Esponenziale: Gli autori dimostrano che il rilassamento dei momenti dei cluster (specificamente di grado 1) raggiunge un tasso di convergenza esponenziale nell'errore di approssimazione all'aumentare del raggio di connettività $h$ del grafo di riferimento $G_h$. Il limite dell'errore è della forma $C d \rho^{-h}$.
• Complessità Campionaria Migliorata: Il limite dell'errore statistico per il rilassamento sparso è $O(\sqrt{d/N} + |E(G)|/N)$. Per grafi sparsi dove $|E(G)| = O(d)$, questo migliora il limite del rilassamento denso di $O(\sqrt{d/N} + d^2/N)$, dimostrando che sfruttare la sparsità riduce significativamente il numero di campioni richiesti.

3.2 Perturbazioni Locali di Misure Mean-Field

Per distribuzioni che sono perturbazioni locali di misure prodotto mean-field:

• Limiti di Approssimazione: Si dimostra che il rilassamento dei marginali cattura la geometria di ordine principale della distanza di Wasserstein, che corrisponde alla norma Sobolev negativa omogenea pesata.
• Errore Statistico: Sotto un grado di rilassamento fisso e dimensione del cluster limitata, l'errore statistico scala come $O(d N^{-1/2})$, implicando una complessità campionaria di $O(d^2 \epsilon^{-2})$. Questo è un miglioramento significativo rispetto alla dipendenza esponenziale da $d$ riscontrata nella stima standard di OT.

3.3 Limiti Statistici Generali

Per distribuzioni generali che soddisfano condizioni di coda Gaussiana uniforme, il documento stabilisce che l'errore statistico del SDP dei momenti dei cluster è governato dal numero di blocchi locali e dagli archi del grafo ($K + |E(G)|$) piuttosto che dalla dimensione ambiente $d$. Nel regime di grado fisso e sparsità, l'errore scala linearmente con $d$.

4. Risultati Numerici

Esperimenti estesi validano le affermazioni teoriche in diversi setting:

• Distribuzioni Gaussiane: Il rilassamento dei momenti dei cluster mostra una convergenza esponenziale rispetto al raggio di connettività $h$. Supera i solutori OT vanilla (Sinkhorn) e i baseline ICNN sia in accuratezza che in efficienza computazionale, mantenendo un basso errore relativo e tempi di esecuzione contenuti anche quando la dimensione $d$ aumenta fino a 1000.
• Misure Prodotto Non-Gaussiane (Beta): Il metodo mantiene un'alta accuratezza (errore relativo $\approx 10^{-3}$) per misure prodotto non Gaussiane, mentre i solutori OT vanilla degradano rapidamente con la dimensione.
• Modelli Ising: Per i modelli Ising discreti, il rilassamento dei marginali fornisce limiti inferiori stretti sul costo OT con tempi di esecuzione ordini di grandezza più veloci rispetto alle soluzioni LP esatte.
• Modellazione Generativa (Ginzburg-Landau & MNIST): Le mappe di trasporto estratte generano con successo campioni che corrispondono ai marginali target. Nei modelli Ginzburg-Landau, il metodo supera i normalizing flows, le ICNN e le mappe basate su Sinkhorn nella distanza di Wasserstein "sliced". Su MNIST (in uno spazio PCA a 6 dimensioni), il metodo produce campioni di cifre riconoscibili.

5. Significato e Rivendicazioni

Il documento afferma che i rilassamenti convessi basati su marginali e momenti dei cluster offrono una via promettente per la riduzione della dimensione nell'optimal transport ad alta dimensione.

• Scalabilità: Sfruttando le strutture locali e la sparsità, il metodo evita la complessità esponenziale dell'OT standard e delle gerarchie complete dei momenti, ottenendo una scalabilità lineare nella dimensione sia per l'errore che per il tempo di esecuzione sotto specifiche assunzioni strutturali.
• Garanzie Teoriche: A differenza degli approcci basati su reti neurali, il metodo proposto fornisce rigorosi limiti di approssimazione e di errore statistico, particolarmente per modelli Gaussiani sparsi e modelli di perturbazione mean-field.
• Interpretabilità: L'approccio fornisce mappe di trasporto esplicite derivate da potenziali polinomiali, fungendo da alternativa più semplice e interpretabile ai modelli generativi deep.
• Robustezza: I risultati empirici suggeriscono che il metodo è robusto anche in contesti non Gaussiani dove le garanzie teoriche sono meno esplicite, mantenendo prestazioni dove i metodi tradiziosi basati sulla discretizzazione falliscono.

Gli autori concludono che questi rilassamenti mitigano efficacemente la maledizione della dimensionalità, rendendo l'OT ad alta dimensione computazionalmente e statisticamente trattabile per una vasta classe di distribuzioni strutturate.