Variational Free Energy Pivot Selection for Pivoted Cholesky

Technische Samenvatting: Variational Free Energy Pivot Selectie voor Gepivoteerde Cholesky

Probleemstelling
Lage-rang benaderingen van symmetrische positief definiete (SPD) matrices zijn fundamenteel in de numerieke lineaire algebra, met name in Gaussian Process (GP) regressie, waarbij de kernelmatrix $K$ wordt benaderd door een rang-$r$ factorisatie $\tilde{K} = LL^\top$. Klassieke methoden, zoals greedy en randomly pivoted Cholesky (RPCholesky), selecteren pivots sequentieel om de algebraïsche spoor-norm fout van het residu ($\text{tr}(K - \tilde{K})$) te minimaliseren. Echter, in veel toepassingen wordt de matrix $K$ niet geïsoleerd geëvalueerd, maar binnen een niet-lineaire matrixfunctionaal. Specifiek in GP-regressie wordt de kwaliteit van de benadering bepa aspect door de Variational Free Energy (VFE), aangeduid als $L(\tilde{K})$, die dient als een ondergrens op de log-marginale waarschijnlijkheid.

De VFE-functionaal combineert drie afzonderlijke termen: een log-determinant term (complexiteit), een kwadratische data-fit term, en een spoor-strafterm (trace penalty). Bestaande pivot-selectieregels, die uitsluitend vertrouwen op de magnitude van de diagonale elementen van het residu, richten zich enkel op de spoor-norm fout. Bijgevolg verwaarlozen zij de log-determinant en de data-fit componenten, wat potentieel kan leiden tot systematisch suboptimale benaderingen voor het specifieke inferentie-objectief. Dit artikel behandelt de vraag: Hoe moet pivot-selectie worden uitgevoerd wanneer het doel is om een matrixfunctionaal te optimaliseren in plaats van louter de algebraïsche benaderingsfout?

Methodologie
De auteurs stellen een nieuwe pivot-selectieregel voor, getiteld $\Delta$-VFE gepivoteerde Cholesky, die direct de exacte één-stap verandering in de VFE-functionaal maximaliseert onder Cholesky-consistente rang-1 updates.

1. Afleiding van de Winstformule:
   De auteurs leiden een gesloten vorm af voor de exacte verandering $\Delta L$ in de VFE $L(\tilde{K})$ veroorzaakt door een rang-1 update $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$. Gebruikmakend van de Matrix Determinant Lemma en de Sherman-Morrison formule, ontleden zij de winst in drie additieve componenten:
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   waarbij:

   • $a = u^\top \Sigma_i^{-1} u$ de complexiteitsbijdrage (log-determinant term) vertegenwoordigt, die de interactie van de update met de geregulariseerde inverse metriek meet.
   • $b = u^\top \Sigma_i^{-1} y$ de data-fit bijdrage vertegenwoordigt, die de uitlijning tussen de update-richting en het huidige voorspellingsresidu meet.
   • $\|u\|^2_2$ de spoor-bijdrage (reductie van de residuele variantie) vertegenwoordigt, wat overeenkomt met de exacte één-stap spoor-afname in plaats van de diagonale proxy die in klassieke methoden wordt gebruikt.

2. Cholesky-consistente Updates:
   Om te garanderen dat de benadering een geldige Cholesky-factorisatie blijft, wordt de update-vector $u$ beperkt tot de vorm $u_p = t_p / \sqrt{(T_i)_{p,p}}$, waarbij $t_p$ de $p$-de kolom van de residumatrix $T_i$ is. Deze beperking zorgt ervoor dat het residu positief semi-definiet blijft en dat het diagonale element van de geselecteerde pivot nul wordt.

3. Algoritmische Realisatie:
   Het evalueren van $\Delta L$ voor alle $n$ kandidaten bij elke stap zou computationeel onhaalbaar zijn ($O(n^2r^2)$). Om efficiëntie te behouden, maakt de methode gebruik van een batch-samplingstrategie:

   • In elke iteratie wordt een batch van $s$ kandidaat-pivots gesampled uit de verzameling van ongebruikte indices.
   • De sampling-waarschijnlijkheid is proportioneel aan de diagonale residuele elementen, identiek aan de distributie die in RPCholesky wordt gebruikt.
   • De geregulariseerde inverse $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$ wordt efficiënt toegepast op vectoren met behulp van de Woodbury-matrixidentiteit en incrementele updates van een hulpmatrix $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$.
   • Deze aanpak maakt het mogelijk om de winst voor $s$ kandidaten te evalueren met een totale kosten van $O(snr^2)$, wat de asymptotische complexiteit van RPCholesky evenaart tot de batch-factor $s$.

Belangrijkste Bijdragen

• Objectief-bewuste Pivot Regel: Het artikel levert de eerste pivot-selectiecriterium die expliciet de per-stap winst van de Variational Free Energy maximaliseert, in plaats van de spoor-norm fout.
• Theoretische Garanties: De auteurs bewijzen dat elke sequentie van Cholesky-consistente rang-1 updates een strikt niet-dalende sequentie van VFE-waarden oplevert. De voorgestelde regel selecteert de pivot die deze gegarandeerde winst in elke stap maximaliseert.
• Complexiteitsefficiëntie: De methode bereikt dezelfde asymptotische complexiteit als gerandomiseerde gepivoteerde Cholesky ($O(snr^2)$) door gebruik te maken van incrementele Woodbury-updates en batch-evaluatie van kandidaten.
• Hiërarchische Interpretatie: Het werk vestigt een drielaagse hiërarchie van pivot-regels:
  1. Niveau 1: Klassieke greedy/RPCholesky (gebruikt diagonale proxy voor spoor-reductie).
  2. Niveau 2: Exacte spoor-reductie maximizer (gebruikt volledige residu-kolom, negeert data/complexiteit).
  3. Niveau 3: $\Delta$-VFE (gebruikt volledige residu-kolom, data-vector en geregulariseerde inverse om de volledige VFE te optimaliseren).

Resultaten
Numerieke experimenten op de Abalone en QM7 datasets tonen het volgende aan:

• VFE Optimalisatie: $\Delta$-VFE bereikt consistent een nauwere grens op de log-marginale waarschijnlijkheid (kleinere relatieve VFE-kloof) vergeleken met zowel greedy als RPCholesky, met name bij lage tot matige rangen ($r \le 1024$).
• Benaderingskwaliteit: De methode behoudt een spoor-norm benaderingskwaliteit die vergelijkbaar is met RPCholesky. Het offert de standaard kernel-benaderingsnauwkeurigheid niet op om VFE-verbeteringen te verkrijgen.
• Voorspellende Prestaties: In GP-regressie taken vertaalt de verbeterde VFE zich naar verminderde voorspellingsfouten (RMSE en MAX) bij lage tot matige rangen.
• Batch-grootte Gevoeligheid: Het vergroten van de batch-grootte $s$ levert afnemende meeropbrengsten op, maar verbetert consequent de VFE-kloof en de voorspellende nauwkeurigheid. Zelfs kleine batch-groottes (bijv. $s=8$ of $s=16$) bieden substantiële winst ten opzichte van RPCholesky.

Betekenis
Het artikel beweert dat de voorgestelde methode de kloof overbrugt tussen algebraïsche matrixbenadering en taakspecifieke inferentie-objectieven. Door een exacte, gesloten vorm voor de winst van de VFE af te leiden, bieden de auteurs een greedy pivot-regel die expliciet is afgestemd op het probabilistische inferentie-doel van Gaussian processes. De resultaten suggereren dat voor toepassingen waar de matrixfunctionaal termen zoals data-fit of complexiteit bevat, het optimaliseren van enkel de spoor-norm fout onvoldoende is, en dat objectief-bewuste selectie superieure praktische prestaties oplevert zonder significante computationele overhead. De methode wordt gepresenteerd als een directe generalisatie van RPCholesky die extra informatie over de objectief-functie incorporeert.