Variational Free Energy Pivot Selection for Pivoted Cholesky

Sintesi Tecnica: Selezione del Pivot basata sulla Variazione dell'Energia Libera Variazionale per il Cholesky con Pivot

Definizione del Problema
Le approssimazioni a basso rango di matrici simmetriche definite positive (SPD) sono fondamentali nell'algebra lineare numerica, in particolare nella regressione dei Processi Gaussiani (GP), dove la matrice kernel $K$ viene approssimata da una fattorizzazione di rango $r$ $\tilde{K} = LL^\top$. I metodi classici, come il Cholesky con pivot greedy e casuale (RPCholesky), selezionano i pivot sequenzialmente per minimizzare l'errore della norma di traccia del residuo ($\text{tr}(K - \tilde{K})$). Tuttavia, in molte applicazioni, la matrice $K$ non è valutata in isolamento, ma all'interno di un funzionale matriciale non lineare. Nello specifico, nella regressione GP, la qualità dell'approssimazione è determinata dall'Energia Libera Variazionale (VFE), indicata con $L(\tilde{K})$, che funge da limite inferiore sulla log-verosimiglianza marginale.

Il funzionale VFE combina tre termini distinti: un termine log-determinante (complessità), un termine quadratico di adattamento ai dati (data-fit) e un termine di penalità della traccia. Le esistenti regole di selezione dei pivot, che si basano esclusivamente sull'ampiezza dei diagonali del residuo, mirano solo all'errore della norma di traccia. Di conseguenza, trascurano le componenti log-determinante e di adattamento ai dati, portando potenzialmente a approssimazioni sistematicamente subottimali per l'obiettivo di inferenza specifico. Il documento affronta la domanda: Come dovrebbe essere eseguita la selezione dei pivot quando l'obiettivo è ottimizzare un funzionale matriciale piuttosto che un puro errore di approssimazione algebrica?

Metodologia
Gli autori propongono una nuova regola di selezione dei pivot, denominata $\Delta$-VFE pivoted Cholesky, che massimizza direttamente la variazione esatta a un passo della VFE del funzionale sotto aggiornamenti Cholesky-consistenti di rango 1.

1. Derivazione della Formula del Guadagno:
   Gli autori derivano un'espressione in forma chiusa per la variazione esatta $\Delta L$ della VFE $L(\tilde{K})$ indotta da un aggiornamento di rango 1 $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$. Utilizzando il Lemma del Determinante Matriciale e la formula di Sherman-Morrison, decompongono il guadagno in tre componenti additive:
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   dove:

   • $a = u^\top \Sigma_i^{-1} u$ rappresenta il contributo della complessità (termine log-determinante), misurando l'interazione dell'aggiornamento con la metrica inversa regolarizzata.
   • $b = u^\top \Sigma_i^{-1} y$ rappresenta il contributo dell'adattamento ai dati (data-fit), misurando l'allineamento tra la direzione dell'aggiornamento e il residuo della predizione corrente.
   • $\|u\|^2_2$ rappresenta il contributo della traccia (riduzione della varianza del residuo), che corrisponde all'esatta diminuzione della traccia a un passo anziché alla componente diagonale utilizzata nei metodi classici.

2. Aggiornamenti Cholesky-Consistenti:
   Per garantire che l'approssimazione rimanga una fattorizzazione Cholesky valida, il vettore di aggiornamento $u$ è limitato alla forma $u_p = t_p / \sqrt{(T_i)_{p,p}}$, dove $t_p$ è l' $p$-esimo colonna della matrice residua $T_i$. Questa restrizione assicura che il residuo rimanga semidefinito positivo e che l'elemento diagonale del pivot selezionato diventi zero.

3. Realizzazione Algoritmica:
   Valutare $\Delta L$ per tutti i $n$ candidati ad ogni passo sarebbe computazionalmente proibitivo ($O(n^2r^2)$). Per mantenere l'efficienza, il metodo impiega una strategia di campionamento a lotti (batched sampling):

   • Ad ogni iterazione, un lotto di $s$ candidati pivot viene campionato dall'insieme degli indici non utilizzati.
   • La probabilità di campionamento è proporzionale agli elementi diagonali del residuo, identica alla distribuzione utilizzata in RPCholesky.
   • L'inversa regolarizzata $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$ viene applicata ai vettori in modo efficiente utilizzando l'identità di Woodbury incrementale e aggiornamenti incrementali a una matrice ausiliaria $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$.
   • Questo approccio permette di valutare il guadagno per $s$ candidati con un costo totale di $O(snr^2)$, eguagliando la complessità asintotica di RPCholesky fino al fattore del lotto $s$.

Contributi Chiave

• Regola di Pivot Consapevole dell'Obiettivo: Il documento deriva il primo criterio di selezione dei pivot che massimizza esplicitamente il guadagno per passo della VFE, invece dell'errore della norma di traccia.
• Garanzie Teoriche: Gli autori dimostrano che qualsiasi sequenza di aggiornamenti di rango 1 Cholesky-consistenti produce una sequenza monotonicamente non decrescente di valori VFE. La regola proposta seleziona il pivot che massimizza questo guadagno garantito ad ogni step.
• Efficienza della Complessità: Il metodo raggiunge la stessa complessità asintotica del Cholesky con pivot casuale ($O(snr^2)$) sfruttando gli aggiornamenti incrementali di Woodbury e la valutazione dei candidati a lotti.
• Interpretazione Gerarchica: Il lavoro stabilisce una gerarchia a tre livelli di regole per i pivot:
  1. Livello 1: Greedy/RPCholesky classico (utilizza un proxy diagonale per la riduzione della traccia).
  2. Livello 2: Massimizzatore esatto della riduzione della traccia (utilizza la colonna completa del residuo, ignora dati/complessità).
  3. Livello 3: $\Delta$-VFE (utilizza la colonna completa del residuo, il vettore dei dati e l'inversa regolarizzata per ottimizzare la VFE completa).

Risultati
Esperimenti numerici sui dataset Abalone e QM7 dimostrano quanto segue:

• Ottimizzazione della VFE: $\Delta$-VFE ottiene costantemente un limite più stretto sulla log-verosimiglianza marginale (gap VFE relativo minore) rispetto a sia al metodo greedy che a RPCholesky, particolarmente a ranghi bassi o moderati ($r \le 1024$).
• Qualità dell'Approssimazione: Il metodo mantiene una qualità di approssimazione della norma di traccia comparabile a RPCholesky. Non sacrifica l'accuratezza dell'approssimazione del kernel standard per ottenere miglioramenti della VFE.
• Performance Predittiva: Nella regressione GP, il miglioramento della VFE si traduce in una riduzione degli errori di predizione (RMSE e MAE) a ranghi bassi o moderati.
• Sensibilità della Dimensione del Lotto: L'aumento della dimensione del lotto $s$ produce rendimenti decrescenti in termini di performance, ma migliora costantemente il gap VFE e l'accuratezza predittiva. Anche piccoli lotti (ad esempio, $s=8$ o $s=16$) forniscono guadagni sostanziali rispetto a RPCholesky.

Significatività
Il documento sostiene che il metodo proposto colma il divario tra l'approssimazione matriciale algebrica e gli obiettivi di inferenza specifici del compito. Derivando un guadagno esatto in forma chiusa per la VFE, gli autori forniscono una regola di pivot greedy che è esplicitamente allineata con l'obiettivo di inferenza probabilistica dei processi gaussiani. I risultati suggeriscono che per applicazioni in cui il funzionale matriciale include termini di adattamento ai dati o di complessità, ottimizzare solo l'errore della norma di traccia è insufficiente, e una selezione consapevole dell'obiettivo produce prestazioni pratiche superiori senza incorrere in un carico computazionale significativo. Il metodo è presentato come una diretta generalizzazione di RPCholesky che incorpora informazioni aggiuntive sulla funzione obiettivo.