Riemannian Optimization for Hadamard Products of Low-Rank Matrices

Sintesi Tecnica: Ottimizzazione Riemanniana per Prodotti di Hadamard di Matrici a Basso Rango

Formulazione del Problema
Il documento affronta la sfida di modellare dati con una struttura moltiplicativa utilizzando il prodotto elemento per elemento (di Hadamard) di due matrici a basso rango. La matrice target $W \in \mathbb{R}^{m \times n}$ è modellata come:
$$W = (GH^\top) \circ (UV^\top)$$
dove $G, U \in \mathbb{R}^{m \times r_1, r_2}$ e $H, V \in \mathbb{R}^{n \times r_1, r_2}$. Sebbene questa formulazione offra un'efficienza di parametrizzazione superiore rispetto a una standard fattorizzazione di rango-$r_1r_2$ (richiedendo $(m+n)(r_1+r_2)$ parametri rispetto a $(m+n)r_1r_2$), essa introduce un panorama di ottimizzazione complesso. Nello specifico, il modello esibisce simmetrie che vanno oltre la standard invarianza di riparametrizzazione Lineare Generale (GL). Il prodotto $W$ rimane invariante sotto scalature accoppiate di righe e colonne tra le due coppie di fattori $(G, H)$ e $(U, V)$. Questi ulteriori gradi di libertà creano una geometria impegnativa che i metodi standard di discesa del gradiente euclideo faticano a navigare efficientemente.

I solver esistenti presentano limitazioni: la Discesa del Gradiente Alternata (AGD) ignora la specifica geometria e le simmetrie di scala, mentre la Discesa a Blocchi di Coordinate (BCD) è altamente efficace per le perdite di tipo minimi quadrati, ma manca di soluzioni in forma chiusa per perdite non quadratiche (ad esempio, predizione di link con link logistico o cross-entropy), limitandone l'applicabilità nella statistica robusta e in altri domini.

Metodologia
Gli autori propongono di formulare il problema di apprendimento come un compito di ottimizzazione su un varietà di quoziente riemanniana. Questo approccio tiene esplicitamente conto delle naturali invarianze del prodotto di Hadamard.

1. Geometria della Varietà: Gli autori definiscono la varietà di quoziente $\mathcal{M}$ fattorizzando il gruppo di simmetria completo $\mathcal{G}$, che include:

   • La standard invarianza di riparametrizzazione GL per ogni coppia di fattori.
   • Nuove simmetrie di scala cross-Hadamard, dove matrici diagonali invertibili scalano le righe e le colonne attraverso le due coppie di fattori in modo inverso.
     La varietà è costruita dallo spazio delle matrici a colonna completa modulo questa azione di gruppo.

2. Nuova Metrica Riemanniana: Un contributo critico è la derivazione di una metrica riemanniana a blocchi diagonali ($g_x$) derivata dal pullback del prodotto interno di Frobenius.

   • La metrica di pullback completa accoppia tutti i quattro blocchi di fattori, risultando in un sistema lineare denso e computazionalmente costoso.
   • La metrica proposta mantiene solo i blocchi diagonali del pullback, scartando i termini incrociati.
   • La metrica è definita tramite matrici di peso ($S$-blocchi) per ogni riga/colonna dei fattori. Ad esempio, il peso per la $i$-esima riga di $G$ è $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$, dove $Y = UV^\top$.
   • Invarianza: È dimostrato che la metrica è invariante sia sotto la riparametrizzazione GL che sotto le simmetrie di scala cross-Hadamard. Ciò garantisce che l'ottimizzatore sia insensibile alla distribuzione arbitraria dell'ampiezza tra i fattori.
   • Connessione con BCD: Le matrici di peso nella metrica proposta corrispondono esattamente alle matrici delle equazioni normali utilizzate negli aggiornamenti BCD. Pertanto, il gradiente riemanniano può essere interpretato come l'esecuzione di un passo BCD "soft" simultaneamente su tutte le righe per arbitrarie funzioni di perdita lisce.

3. Algoritmo di Ottimizzazione (RGD): Gli autori sviluppano un algoritmo di Discesa del Gradiente Riemanniano (RGD):

   • Calcolo del Gradiente: Il gradiente riemanniano viene calcolato risolvendo sistemi lineari indipendenti $r \times r$ (uno per ogni riga/colonna) utilizzando gli $S$-blocchi.
   • Dimensione del Passo: Viene derivata una dimensione del passo di Cauchy Gauss-Newton priva di parametri di tuning. Questa dimensione è invariante rispetto al gruppo di simmetria e non richiede la sintonizzazione di iperparametri.
   • Ritrazione: Viene utilizzata una ritrazione additiva per mappare gli aggiornamenti nuovamente sulla varietà.
   • Complessità: Il costo per iterazione scala linearmente con il numero di voci osservate $N$ ($O(Nr)$) e polinomialmente con i ranghi ($O((m+n)r^4)$), rendendolo efficiente per grandi dataset.

Contributi Chiave

1. Caratterizzazione Geometrica: Descrizione formale della struttura della varietà di quoziente per i prodotti di Hadamard, identificando sia le simmetrie GL che quelle di scala cross-Hadamard.
2. Metrica Invariante alla Scala: Proposta di una nuova metrica riemanniana a blocchi diagonali che rispetta l'intero gruppo di simmetria e decoppia l'ottimizzazione in problemi indipendenti per riga/colonna.
3. Sviluppo dell'Algoritmo: Derivazione di un algoritmo RGD con una dimensione del passo Gauss-Newton priva di tuning che supporta qualsiasi funzione di perdita liscia, a differenza di BCD che è limitata ai minimi quadrati.
4. Validazione Empirica: Dimostrazione che il metodo raggiunge prestazioni comparabili a BCD per compiti di minimi quadrati, pur essendo superiore per obiettivi non quadratici e ottenendo risultati migliori in specifiche configurazioni di rango di Hadamard.

Risultati Sperimentali
Gli autori hanno valutato RGD su dataset sintetici e reali:

• Stress Test Sintetici: Su target sintetici $2.000 \times 1.000$, RGD ha dimostrato:
  • Invarianza di Scala: L'errore di recupero è rimasto costante attraverso diverse separazioni di scala diagonale ($\kappa_{scale}$), verificando empiricamente la proprietà di invarianza della metrica. Al contrario, AGD ha mostrato sensibilità alla scalatura.
  • Condizionamento: RGD ha performato comparabilmente a BCD attraverso diversi numeri di condizionamento dei fattori, superando significativamente AGD.
  • Robustezza al Rumore: RGD è convergito al livello del rumore con lo stesso tasso di BCD, mentre AGord era in ritardo.
• Dataset Reali:
  • Approssimazione di Matrice Completa: Sui dataset Camera, Football e Les Misérables, RGD ha seguito da vicino BCD in termini di errore relativo, confermando che la metrica fornisce un precondizionamento equivalente a BCD per perdite quadratiche.
  • MovieLens-1M: In un compito di completamento di matrice con un budget di parametri fisso ($r_1+r_2=6$), RGD ha ottenuto il RMSE "held-out" più basso tra tutte le configurazioni di rango di Hadamard testate. Notevolmente, la configurazione bilanciata $(3,3)$ ha superato la quasi-vanilla $(1,5)$, suggerendo che la capacità di interazione di Hadamard ($r_1r_2$) contribuisce all'accuratezza. RGD ha costantemente superato AGD e ha ottenuto un RMSE inferiore rispetto a BCD in configurazioni genuinamente Hadamard.

Significatività e Rivendicazioni
Il documento sostiene di colmare il divario tra l'efficienza di BCD per i problemi di minimi quadrati e la flessibilità dei metodi basati sul gradiente per perdite lisce generali. Elevando il problema a una varietà di quoziente riemanniana, gli autori forniscono un quadro rigoroso che gestisce le complesse simmetrie dei prodotti di Hadamard. L'algoritmo RGD proposto offre un metodo di ottimizzazione privo di tuning e invariante alla scala che scala linearmente con la dimensione dei dati. Gli autori affermano che questo framework si estende naturalmente ai prodotti di $k$ matrici a basso rango ed è compatibile con altri solver riemanniani (ad esempio, gradienti coniugati, metodi trust-region), offrendo un'alternativa robusta agli attuali solver per la modellazione a basso rango moltiplicativa.