Riepilogo Tecnico: Decomposizione della Dipendenza a Basso Rango tramite la Fattorizzazione Non Negativa Simmetrica Accelerata

Definizione del Problema

La Fattorizzazione Non Negativa Simmetrica (SymNMF) mira a decomporre una matrice di dipendenza simmetrica e non negativa per elemento $S \in \mathbb{R}^{n \times n}_+$ in un fattore a basso rango $H \in \mathbb{R}^{n \times k}_+$ (dove $k \ll n$) tale che $S \approx HH^\top$. Questa decomposizione rivela strutture di gruppo latenti dove i membri condividono modelli di dipendenza comuni, fungendo sia da clustering "soft" che da embedding appresi.

Il presente lavoro affronta il divario di scalabilità della SymNMF. Sebbene il metodo sia ben consolidato, la sua implementazione pratica su portafogli su larga scala (migliaia o milioni di strumenti) è stata ostacolata da:

1. Vincoli di Memoria: La formulazione standard dell'obiettivo richiede matrici intermedie esplicite $n \times n$, limitando i lavori precedenti a dimensioni moderate ($n \lesssim 10^4$).
2. Mancanza di Confronto Sistematico: Non esiste una valutazione esaustiva delle famiglie di solver su input reali e controllati su larga scala.
3. Sfide di Ottimizzazione: I metodi efficaci a scale moderate spesso falliscono nelle lunghe esecuzioni richieste per grandi $n$, in particolare a causa dell'interazione tra la gestione dei vincoli (proiezione vs. riparametrizzazione) e la memoria degli ottimizzatori adattivi.

Lo studio si concentra su due tipi specifici di input che rappresentano fattori di rischio finanziario:

• Matrici di Correlazione Assoluta di Pearson: Catturano la dipendenza attraverso l'intera distribuzione.
• Matrici di Dipendenza Coppia-Coppia di Coda (TPDM): Fondate sulla Teoria del Valore Estremo, catturano la dipendenza condizionata ad eventi estremi. Queste matrici presentano spesso uno spettro "piatto" e mal condizionato, dominato da un singolo fattore comune.

Metodologia

1. Riformulazione Efficiente della Memoria

Per consentire la scalabilità fino a $n \approx 10^6$, gli autori riformulano la funzione obiettivo utilizzando un'identità di traccia. La norma di Frobenius standard $\|S - HH^\top\|_F^2$ viene espansa in:
$$\|S\|_F^2 - 2 \text{tr}(H^\top SH) + \|H^\top H\|_F^2$$
Ciò elimina la necessità di formare la matrice residua $n \times n$ di $S - HH^\top$. Tutti gli intermedi sono ridotti a matrici $n \times k$ o $k \times k$. Questo cambiamento algebrico raddoppia approssimativamente il valore massimo di $n$ fattibile su una singola GPU (da $\sim 60.000$ a $\sim 130.000$ in FP32) e consente la distribuzione multi-nodo fino a $n = 10^6$.

2. Famiglie di Solver e Configurazioni

Lo studio valuta sette famiglie di algoritmi (oltre 30 configurazioni) attraverso tre paradigmi:

• Proiezione del Gradiente: Gradiente Proiettato (PGD), Gradiente Prossimale Accelerato (APG/FISTA).
• Metodi del Primo Ordine Adattivi: AdaGrad, RMSprop, Adam, NAdam, Adan e tre nuove estensioni introdotte in questo lavoro:
  • Piecewise AdaGrad: Resetta l'accumulatore in caso di stagnazione dell'obiettivo per prevenire la saturazione.
  • Row-Stochastic SVRG: Combina il sottocampionamento delle righe con snapshot periodici del gradiente completo per mantenere una crescita uniforme dell'accumulatore.
  • Block-SVRG AdaptGrow: Utilizza il campionamento di blocchi densi con crescita adattiva del batch (partendo da piccoli e crescendo verso il batch completo in caso di stagnazione) e snapshot ibridi SVRG per correggere l'eterogeneità dell'accumulatore per riga.
• Splitting/Discesa del Gradiente Speculare (Mirror Descent): Aggiornamenti Moltiplicativi (MU), ADMM, Block Coordinate Descent (HALS, ANLS) e Deep Unfolding (SymNMF-Net).

3. Gestione dei Vincoli

Il documento confronta due strategie per imporre $H \ge 0$:

• Spazio Proiettato: Clampaggio diretto di $H$ dopo gli aggiornamenti.
• Riparametrizzazione Softplus (Spazio Logaritmico): Ottimizzazione di una $\Theta$ non vincolata dove $H = \text{softplus}(\Theta)$.
  Gli autori riscontrano che la Softplus aiuta gli ottimizzatori a breve memoria (es. RMSprop) e i metodi del secondo ordine a piccole scale, ma corrompe gli accumulatori a lunga memoria (es. AdaGrad, Adam) man mano che le esecuzioni si prolungano, a causa della natura non stazionaria del gradiente della regola della catena. Di conseguenza, gli esperimenti su larga scala utilizzano lo spazio proiettato.

4. Criteri di Convergenza

Viene applicata uniformemente una rigorosa regola di arresto in tre parti:

1. Soglia di Perdita (Loss Gate): Errore quadratico normalizzato $E_t < 0.1$.
2. Condizione KKT: Norma del gradiente proiettato normalizzata per elemento $\|\nabla_{\text{proj}} f(H)\|_F / (nk) < \tau_g$.
3. Stagnazione: Miglioramento relativo dell'obiettivo al di sotto di una soglia.
   Ciò garantisce che le soluzioni non siano solo a bassa perdita, ma anche punti stazionari, evitando la convergenza falsa in valli piatte.

Risultati Chiave

Fase 1: Selezione dell'Algoritmo ($n \le 10^4$)

Su una singola GPU NVIDIA GB200, undici metodi sono confluiti in modo affidabile. Tuttavia, solo sei hanno soddisfatto le rigide soglie di efficienza (convergenza in $<4$ secondi a $n=10^4$):

• ADMM
• RMSprop
• Block-SVRG AdaptGrow
• AdaGrad
• Row-Stochastic SVRG
• Piecewise AdaGrad

Gli aggiornamenti moltiplicativi, il PGD standard e il deep unfolding non sono riusciti a convergere o sono stati significativamente più lenti. I metodi del secondo ordine (L-BFGS, Newton) sono falliti sugli spettri TPDM a causa di una cattiva approssimazione della curvatura o problemi di memoria.

Fase 2: Fattibilità su Larga Scala ($n = 10^5, 10^6$)

I sei metodi selezionati sono stati testati su cluster GPU multi-nodo (fino a 64 GPU).

• Dominanza della Famiglia AdaGrad: Cinque metodi della famiglia AdaGrad (AdaGrad, Piecewise, Row-Stoch SVRG, Block-SVRG AdaptGrow, RMSprop) sono riusciti a convergere a $n=10^6$. ADMM è stato omesso a questa scala per motivi di velocità.
• Dipendenza Spettrale: Il solver più veloce dipende dallo spettro della matrice:
  • Matrici di Correlazione (Spettro a Basso Rango Dominante): Il AdaGrad full-batch è il più veloce. Il problema presenta un netto gap segnale-rumore, permettendo esecuzioni brevi dove i passi full-batch sono efficienti.
  • TPDM (Spettro Piatto, Mal Condizionato): Block-SVRG AdaptGrow è il più veloce. Lo spettro è dominato da un fattore comune con gap quasi nulli, richiedendo esecuzioni lunghe. Il minor costo per iterazione della strategia di campionamento adattivo dei blocchi supera la necessità di più iterazioni.
• Prestazioni: A $n=10^6$, Block-SVRG AdaptGrow ha risolto il TPDM in circa 4 minuti (409 iterazioni), mentre AdaGrad ha risolto la correlazione in circa 2 minuti (72 iterazioni).

Baseline di Clustering

Il documento confronta lo Spherical K-means (applicato alle righe di $S$) come alternativa di etichettatura "hard".

• Efficienza: K-means è significativamente più veloce (meno iterazioni) quando esiste una struttura di cluster angolare.
• Degenerazione: K-means fallisce (silhouette $\approx 0$) quando la matrice collassa verso un singolo fattore comune (basso rango effettivo, $r_{\text{eff}} \to 1$), un regime comune nei TPDM su larga scala. In questi casi, la fattorizzazione "soft" fornita da SymNMF rimane necessaria.

Significato e Rivendicazioni

Il documento sostiene di colmare il divario tra la SymNMF teorica e l'applicazione pratica su larga scala nella stima del rischio finanziario. I suoi contributi primari sono:

1. Scalabilità: Dimostrare che la SymN_dense è trattabile fino a $n=10^6$ tramite la riformulazione dell'identità di traccia e la distribuzione multi-GPU, rimuovendo il collo di bottiglia della memoria $O(n^2)$.
2. Raccomandazioni sui Solver: Fornire una guida basata sui dati per la selezione del solver in base al tipo di input e alla scala. Identifica AdaGrad diagonale come il default per esecuzioni brevi e Block-SVRG AdaptGrow per esecuzioni lunghe e mal condizionate.
3. Innovazione Algoritmica: Introdurre e validare specifiche estensioni ingegneristiche (Piecewise AdaGrad, Block-SVRG AdaptGrow) che risolvono la tensione tra la memoria infinita di AdaGrad (buona per obiettivi stazionari) e la saturazione durante esecuzioni lunghe.
4. Gestione dei Vincoli: Caratterizzare il compromesso dipendente dalla scala tra proiezione e Softplus, sconsigliando l'uso di Softplus per metodi adattivi a lunga memoria.

Gli autori sottolineano che queste scoperte sono proprietà del panorama di ottimizzazione della SymNMF stessa, rendendole applicabili a qualsiasi problema con caratteristiche spettrali simili, non solo agli specifici input finanziari utilizzati.