Sintesi Tecnica: Deep Unfolding Scalabile di Ottimizzatori Conici

Definizione del Problema

Il Deep Unfolding (DU) si è dimostrato efficace nell'accelerare gli ottimizzatori iterativi per vari domini, inclusi il compressed sensing e la robotica. Tuttavia, estendere il DU a programmi semidefiniti (SDP) su larga scala — comuni nelle applicazioni di robotica come il controllo della covarianza (covariance steering) — è stato ostacolato da due ostacoli specifici quando si srotola (unrolling) i solver conici basati su ADMM a aggiornamento completo (es. COSMO):

1. Collo di Bottiglia della Memoria nella Risoluzione di Sistemi Lineari: La backpropagazione attraverso la risoluzione del sistema lineare in ogni iterazione richiede tipicamente la formazione esplicita della matrice dei coefficienti. Per l'ADMM, ciò comporta il termine $A^\top A$. Anche se la matrice di vincolo $A$ è sparsa, $A^\top A$ è spesso densa, portando a una complessità di memoria di $O(n^2)$. Questo impedisce la scalabilità verso grandi dimensioni di problemi dove la fattorizzazione diretta esaurisce la memoria.
2. Instabilità Numerica nelle Proiezioni PSD: La proiezione sul cono semidefinito positivo (PSD) richiede una decomposizione in autovalori. La backpropagazione standard attraverso questa operazione coinvolge termini della forma $1/(\lambda_i - \lambda_j)$ nel gradiente. Quando gli autovalori coincidono (un evento frequente durante l'addestramento, specialmente con target di covarianza isotropi), questi termini causano instabilità numerica o gradienti indefiniti (NaN).

Metodologia

Gli autori propongono un framework di deep unfolding per il solver COSMO che affronta questi due ostacoli attraverso regole di backward personalizzate, consentendo l'apprendimento di policy di iperparametri e warm-start per problemi conici su larga scala.

1. Differenziazione Implicita Matrix-Free per la Risoluzione di Sistemi Lineari

Per evitare il costo di memoria $O(n^2)$ della formazione della matrice densa $A^\top A$, gli autori impiegano una regola di differenziazione implicita matrix-free per la risoluzione del sistema lineare basata sul gradiente coniugato (CG).

• Forward Pass: Il solver utilizza la modalità indiretta, risolvendo le equazioni normali ridotte $(P + \sigma I + A^\top D(\rho)A)\tilde{x} = \xi$ tramite CG, che si basa esclusivamente su prodotti matrice-vettore (matvecs).
• Backward Pass: Invece di srotolare le iterazioni CG o formare la densa Jacobiana, gli autori derivano una regola basata sul sistema aggiunto. Risolvendo il sistema aggiunto $M\tilde{\lambda} = -\nabla_{\tilde{x}}L$ utilizzando lo stesso metodo CG, il gradiente rispetto agli iperparametri $\rho$ viene calcolato come $\nabla_\rho L = (A\tilde{\lambda}) \odot (A\tilde{x})$.
• Risultato: Questo approccio non forma mai esplicitamente la densa matrice dei coefficienti, riducendo la complessità di memoria da $O(n^2)$ a $O(n + \text{nnz}(A))$ e consentendo la backpropagation a scale dove i metodi precedenti falliscono.

2. Regola di Backward Stabile per la Proiezione PSD

Per risolvere l'instabilità della decomposizione in autovalori sotto autovalori ripetuti, gli autori sostituiscono l'autograd standard con una regola di backward basata sulla rappresentazione di Dalečii–Krein (DK) della derivata di Fréchet.

• Meccanismo: La proiezione PSD è trattata come una funzione matriciale primaria $T = U f(\Lambda) U^\top$ con $f(x) = \max(x, 0)$. Il teorema DK fornisce una formula per la derivata dove il termine singolare $1/(\lambda_j - \lambda_i)$ è moltiplicato da un numeratore $f(\lambda_j) - f(\lambda_i)$.
• Stabilità: Quando gli autovalori coincidono ($\lambda_i = \lambda_j$), il numeratore svanisce alla stessa velocità del denominatore, risultando in una singolarità eliminabile definita dal limite $f'(\lambda_i)$. Ciò garantisce che il gradiente rimanga finito e ben definito anche con autovalori ripetuti.
• Efficienza: Questa regola riutilizza la decomposizione in autovalori calcolata nel forward pass, non comportando costi computazionali asintotici aggiuntivi rispetto agli approcci ingenui, a differenza di alternative come lo srotolamento delle iterazioni di Newton-Schulz.

Contributi Chiave

1. Differenziazione di Sistemi Lineari Scalabile: Una regola di differenziazione implicita matrix-free che riduce l'uso di memoria da $O(n^2)$ a $O(n)$, abilitando il deep unfolding di solver conici a aggiornamento completo su SDP su larga scala.
2. Proiezione PSD Numericamente Stabile: Una regola di backward basata sul teorema di Dalečii–Krein che rimane ben definita sotto autovalori ripetuti, un requisito critico per l'addestramento su covariance steering e altri problemi SDP.
3. Validazione Empirica: Una dimostrazione che queste regole permettono lo srotolamento del solver COSMO per apprendere policy di iperparametri leggeri e warm-starts. L'approccio appreso è valutato su SDP/SOCP standalone e come subroutine in la Programmazione Convessa Sequenziale (SCP) per il controllo della covarianza non lineare.

Risultati

Gli autori valutano il solver COSMO appreso rispetto al solver COSMO standard (con euristiche adattive) e al solver interior-point all'avanguardia Clarabel attraverso diverse classi di problemi:

• SDP e SOCP Standalone: La policy appresa ottiene accelerazioni significative a seconda della classe di problema:
  • SDP di Lovász $\vartheta$: Fino a 50.4× di accelerazione nel tempo di esecuzione (wall-clock time).
  • SDP Max-cut: 2.62× di accelerazione.
  • Filtri di Kalman Robusti: 4.91× di accelerazione.
  • LMI di Lyapunov: 1.16× di accelerazione.
• Covariance Steering Non Lineare (SCP): Quando utilizzato come subroutine in SCP per sistemi non lineari (dinamiche di doppio integratore e uniciclo), l'approccio appreso fornisce un'accelerazione di 30× rispetto al vanilla COSMO.
• Scalabilità della Memoria: Gli esperimenti mostrano che mentre i metodi baseline esauriscono la memoria GPU (24 GB) a $n \approx 20\text{--}50k$ variabili, il metodo matrix-free proposto scala linearmente, rimanendo sotto i 300 MB anche a $n=50k$.

Significato e Limitazioni

Il paper sostiene che questi contributi rendano possibile l'applicazione del deep unfolding alla ottimizzazione conica su larga scala, un dominio precedentemente limitato dai vincoli di memoria e stabilità numerica. Le policy apprese forniscono un'accelerazione sostanziale per applicazioni di robotica in tempo reale dove sono richiesti budget computazionali fissi.

Gli autori segnalano specifiche limitazioni:

• Scalabilità: Sebbene la risoluzione del sistema lineare sia matrix-free, la proiezione PSD richiede comunque una decomposizione in autovalori densa $O(p^3)$ per ogni blocco semidefinito di dimensione $p$. I guadagni di scalabilità si realizzano nel numero di variabili/vincoli, non nella dimensione del blocco stesso.
• Regime di Accuratezza: Il metodo punta a una precisione bassa-moderata ($\epsilon \approx 10^{-3}$), tipica del controllo in tempo reale. Non pretende di superare i solver interior-point (come Clarabel) a tolleranze molto strette, dove i metodi del primo ordine convergono lentamente.
• Overhead di Addestramento: Una policy separata viene addestrata per ogni famiglia di problemi, comportando un costo iniziale (circa 100 problemi per classe) che deve essere ammortizzato su molti calcoli. Il lavoro attuale non dimostra il trasferimento tra famiglie o la scalabilità a istanze sostanzialmente più grandi di quelle viste durante l'addestramento.