Convex Relaxations for the Optimization of Markov Processes

Sintesi Tecnica: Rilassamenti Convessi per l'Ottimizzazione di Processi di Markov

Enunciato del Problema
Il documento affronta il problema dell'ottimizzazione di un processo di Markov che interpola tra due distribuzioni di probabilità prescritte, $\mu$ e $\nu$, su uno spazio di stato $\Omega$, minimizzando un costo cumulativo. Il processo è definito da una sequenza di leggi intermedie $\{\rho_s\}_{s=0}^T$ e kernel di transizione di Markov $\{K_s\}_{s=0}^{T-1}$. L'obiettivo è minimizzare la somma dei costi a singolo step:
$$\inf \sum_{s=0}^{T-1} \int_{\Omega} \int_{\Omega} c_s(x, y) K_s(x, dy) d\rho_s(x)$$
soggetto ai vincoli iniziali e terminali ($\rho_0 = \mu, \rho_T = \nu$) e al vincolo di evoluzione di Markov ($\rho_{s+1} = (K_s)_* \rho_s$).

La principale sfida computazionale è la maledizione della dimensionalità. In spazi di stato ad alta dimensione, rappresentare la distribuzione congiunta completa degli stati consecutivi (il coupling $\pi_s$) è intrattabile. Il documento si concentra su scenari in cui i kernel di transizione ammissibili soddisfano vincoli specifici (ad esempio, vincoli di supporto, regole di aggiornamento locale) e dove la funzione di costo ammette una decomposizione locale.

Metodologia
Gli autori propongono un framework basato su formulazioni di sequential-coupling e rilassamenti convessi che sfruttano la località e le strutture di interazione sparsa.

1. Riformulazione Sequential-Coupling:
   Il problema viene riformulato dal passaggio dall'ottimizzazione dei kernel di transizione all'ottimizzazione di una sequenza di accoppiamenti congiunti $\pi_s(dx, dy) = \rho_s(dx)K_s(x, dy)$. I vincoli vengono riscritti in termini delle marginali di questi accoppiamenti. Le distribuzioni intermedie sono assorbite nei coupling, dove $\rho_{s+1}$ è la marginale destra di $\pi_s$ e la marginale sinistra di $\pi_{s+1}$.

2. Rilassamenti Convessi:
   Per evitare di rappresentare il coupling completo $\pi_s$, gli autori sviluppano due tipi di rilassamenti convessi che mantengono solo informazioni locali di basso ordine:

   • Rilassamento Marginale: Il coupling completo è sostituito dalle sue marginali locali su un insieme di cluster di coordinate $\mathcal{C}$ e coppie di cluster definiti da un grafo di cluster $\mathcal{G} = (\mathcal{C}, \mathcal{E})$. Il rilassamento impone:
     • Consistenza tra le marginali di cluster e di coppie di cluster.
     • Conservazione della massa attraverso i passi temporali (proiettata sulle coppie di cluster mantenute).
     • Vincoli di positività locale e globale (questi ultimi assicurano che le marginali locali possano essere estese a una misura globale non negativa, spesso tramite un vincolo Semidefinito Positivo (PSD) su una matrice di tipo momento).
     • Vincoli di ammissibilità proiettati sulle marginali locali.
   • Rilassamento dei Momenti di Cluster: Inveve delle marginali complete, il metodo utilizza un insieme finito di momenti rispetto a funzioni di base prescritte (ad esempio, monomi) sui cluster. Questo è adatto per spazi di stato continui. Le variabili decisionali sono matrici di momenti. I vincoli includono consistenza dei momenti, conservazione della massa e positività globale (vincoli PSD sulle matrici di momenti assemblate).

   Entrambi i framework risultano in problemi di ottimizzazione convessa (Programmi Lineari per stati finiti con vincoli affini, o Programmi Semidefiniti (SDP) per stati continui o vincoli generali). Questi forniscono limiti inferiori computabili per il problema originale e recuperano statistiche di basso ordine delle distribuzioni intermedie.

3. Recupero della Dinamica:

   • Trasporto Ottimo Dinamico (Benamou–Brenier): Quando lo spazio di stato è convesso, il costo è cinetico ($\|x-y\|^2$) e non esistono vincoli sul kernel, il problema recupera la geodetica di Benamô–Brenier. Gli autori dimostrano che le variabili duali del problema rilassato approssimano i potenziali duali del problema di Benamô–Brenier. Differenziando questi potenziali, si può recuperare un campo di velocità approssimato, che induce un flusso e un corrispondente kernel di Markov.
   • Processi Vincolati Generali: Per vincoli generali (ad esempio, aggiornamenti single-spin nei modelli di Ising), il metodo adatta una famiglia parametrica di kernel (ad esempio, dinamica di Glauber) alle statistiche locali recuperate. Ciò avviene minimizzando l'errore quadratico tra le marginali del passo successivo previste (tramite il kernel parametrico) e le marginali recuperate dal rilassamento.

Contributi Chiave

• Formulazione: Il documento riclassifica l'ottimizzazione di processi di Markov in una formulazione di sequential-coupling e propone un framework di rilassamento convesso che scala verso alte dimensioni utilizzando informazioni locali sparse (marginali o momenti) anziché distribuzioni congiunte complete.
• Connessione con il Trasporto Ottimo Dinamico: Dimostra che il trasporto ottimo dinamico è un caso speciale di questo framework. Fondamentalmente, fornisce una procedura per recuperare il campo di velocità di Benamô–Brenier dal delle variabili duali del problema rilassato, colmando il divario tra rilassamenti statici e flussi dinamici.
• Generalizzazione alla Dinamica Vincolata: Il framework si estende oltre il trasporto non vincolato per gestire processi di Markov con vincoli rigidi. Gli autori illustrano questo adattando la dinamica di Glauber al trasporto tra modelli di Ising, convertendo le statistiche locali recuperate in un kernel di Markov implementabile.

Risultati
Il documento presenta esperimenti numerici che validano l'approccio:

• Trasporto Gaussiano: In un contesto gaussiano a 50 dimensioni, il rilassamento dei momenti recupera accuratamente medie, covarianze e campi di velocità affini intermedi. Il metodo si dimostra computazionalmente efficiente (risolto in secondi tramite SDP) e più accurato dei metodi basati su particelle (back-propagation) in termini di errore di covarianza lungo la traiettoria.
• Trasporto Ginzburg–Landau: Il metodo trasporta con successo una distribuzione gaussiana verso una distribuzione di Ginzburg–Landau non gaussiana in 10 dimensioni. La ricostruzione a massima entropia dai momenti recuperati cattura la deformazione graduale della distribuzione, incluse le correlazioni locali e a lungo raggio.
• Modelli di Ising: L'approccio gestisce il trasporto vincolato tra modelli di Ising ferromagnetici e antiferromagnetici (1D e 2D). Il rilassamento marginale (risolto come LP) recupera le marginali di spin locali, che vengono poi utilizzate per adattare la dinamica di Glauber tempo-inomogenea. La dinamica adattata riproduce con successo le marginali recuperate e genera traiettorie campionarie valide.

Significatività e Rivendicazioni
Il documento afferma che il suo framework offre un'alternativa trattabile all'ottimizzazione di processi di Markov ad alta dimensione evitando il costo esponenziale della rappresentazione completa dello stato. Esso fornisce:

1. Limiti Inferiori Computabili: I rilassamenti forniscono limiti inferiori rigorosi per il costo ottimale.
2. Statistiche Recuperabili: Il metodo recupera statistiche di basso ordine (medie, covarianze, momenti) delle leggi intermedie.
3. Ricostruzione Dinamica: A differenza dei metodi di trasporto statico, questo framework permette la ricostruzione della dinamica sottostante (campi di velocità o kernel di transizione) dal soluzione rilassata.
4. Versatilità: Unifica il trasporto ottimo dinamico e il controllo stocastico vincolato (come la dinamica di Glauber) sotto un unico ombrello di ottimizzazione convessa, applicabile sia a spazi di stato discreti che continui.

Gli autori notano con modestia che, sebbene il metodo recuperi statistiche locali e dinamiche approssimate, la preservazione esatta della località nelle distribuzioni intermedie rimane una questione teorica aperta, e il framework è attualmente limitato a specifici tipi di vincoli e strutture di costo.