Variational Free Energy Pivot Selection for Pivoted Cholesky

Résumé Technique : Sélection de Pivot par l'Énergie Libre Variationnelle pour le Cholesky Pivoté

Énoncé du Problème
Les approximations de rang faible de matrices définies positives symétriques (SPD) sont fondamentales en algèbre linéaire numérique, particulièrement dans la régression par Processus Gaussiens (GP) où la matrice noyau $K$ est approximée par une factorisation de rang $r$ $\tilde{K} = LL^\top$. Les méthodes classiques, telles que le Cholesky pivoté gourdi (greedy) et aléatoire (RPCholesky), sélectionnent les pivots séquentiellement pour minimiser l'erreur de norme de trace algébrique du résidu ($\text{tr}(K - \tilde{K})$). Cependant, dans de nombreuses applications, la matrice $K$ n'est pas évaluée de manière isolée mais au sein d'un fonctionnel matriciel non linéaire. Spécifiquement, dans la régression GP, la qualité de l'approximation est déterminée par l'Énergie Libre Variationnelle (VFE), notée $L(\tilde{K})$, qui sert de borne inférieure sur la log-vraisemblance marginale.

Le fonctionnel VFE combine trois termes distincts : un terme de log-déterminant (complexité), un terme quadratique d'ajustement aux données, et un terme de pénalité de trace. Les règles de sélection de pivots existantes, qui reposent uniquement sur les magnitudes diagonales du résidu, ciblent uniquement l'erreur de norme de trace. Par conséquent, elles négligent les composantes de log-déterminant et d'ajustement aux données, ce qui peut conduire à des approximations systématiquement sous-optimales pour l'objectif d'inférence spécifique. L'article répond à la question suivante : Comment la sélection de pivots doit-elle être effectuée lorsque l'objectif est d'optimiser un fonctionnel matriciel plutôt qu'une erreur d'approximation algébrique pure ?

Méthodologie
Les auteurs proposent une nouvelle règle de sélection de pivot, nommée Cholesky pivoté $\Delta$-VFE, qui maximise directement le changement exact d'une étape de la VFE induit par des mises à jour de rang 1 cohérentes avec Cholesky.

1. Dérivation de la Formule de Gain :
   Les auteurs dérivent une expression en forme close pour le changement exact $\Delta L$ de la VFE $L(\tilde{K})$ induit par une mise à jour de rang 1 $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$. En utilisant le Lemme du Déterminant de Matrice et la formule de Sherman-Morrison, ils décomposent le gain en trois composantes additives :
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   où :

   • $a = u^\top \Sigma_i^{-1} u$ représente la contribution de la complexité (terme de log-déterminant), mesurant l'interaction de la mise à jour avec la métrique inverse régularisée.
   • $b = u^\top \Sigma_i^{-1} y$ représente la contribution de l'ajustement aux données (data-fit), mesurant l'alignement entre la direction de la mise à jour et le résidu de prédiction actuel.
   • $\|u\|^2_2$ représente la contribution de la trace (réduction de la variance résiduelle), ce qui correspond à la réduction exacte de la trace en une étape plutôt qu'au proxy diagonal utilisé dans les méthodes classiques.

2. Mises à Jour Cohérentes avec Cholesky :
   Pour garantir que l'approximation reste une factorisation de Cholesky valide, le vecteur de mise à jour $u$ est restreint à la forme $u_p = t_p / \sqrt{(T_i)_{p,p}}$, où $t_p$ est la $p$-ième colonne de la matrice résiduelle $T_i$. Cette restriction garantit que le résidu reste semi-défini positif et que l'entrée diagonale du pivot sélectionné devient nulle.

3. Réalisation Algorithmique :
   L'évaluation de $\Delta L$ pour tous les $n$ candidats à chaque étape serait prohibitive en termes de calcul ($O(n^2r^2)$). Pour maintenir l'efficacité, la méthode utilise une stratégie d'échantillonnage par lots (batched sampling) :

   • À chaque itération, un lot de $s$ pivots candidats est échantillonné parmi l'ensemble des indices non utilisés.
   • La probabilité d'échantillonnage est proportionnelle aux entrées diagonales du résidu, identique à la distribution utilisée dans RPCholesky.
   • L'inverse régularisé $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$ est appliqué aux vecteurs efficacement en utilisant l'identité de Woodbury et des mises à jour incrémentielles d'une matrice auxiliaire $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$.
   • Cette approche permet l'évaluation du gain pour $s$ candidats avec un coût total de $O(snr^2)$, égalant la complexité asymptotique de RPCholesky à un facteur de lot $s$ près.

Contributions Clés

• Règle de Pivot Sensible à l'Objectif : L'article dérive le premier critère de sélection de pivot qui maximise explicitement le gain par étape de l'Énergie Libre Variationnelle, plutôt que l'erreur de norme de trace.
• Garanties Théoriques : Les auteurs prouvent que toute séquence de mises à jour de rang 1 cohérentes avec Cholesky produit une séquence de valeurs VFE monotone non décroissante. La règle proposée sélectionne le pivot qui maximise ce gain garanti à chaque étape.
• Efficacité de Complexité : La méthode atteint la même complexité asymptotique que le Cholesky pivoté aléatoire ($O(snr^2)$) en exploitant les mises à jour incrémentielles de Woodbury et l'évaluation par lots des candidats.
• Interprétation Hiérarchique : Le travail établie une hiérarchie à trois niveaux de règles de pivot :
  1. Niveau 1 : Cholesky classique/RPCholesky (utilise un proxy diagonal pour la réduction de trace).
  2. Niveau 2 : Maximiseur exact de réduction de trace (utilise la colonne résiduelle complète, ignore les données/complexité).
  3. Niveau 3 : $\Delta$-VFE (utilise la colonne résiduelle complète, le vecteur de données et l'inverse régularisé pour optimiser la VFE complète).

Résultats
Des expériences numériques sur les jeux de données Abalone et QM7 démontrent les points suivants :

• Optimisation de la VFE : $\Delta$-VFE atteint systématiquement une borne plus serrée sur la log-vraisemblance marginale (écart de VFE relatif plus faible) par rapport à Greedy et RPCholesky, particulièrement à des rangs faibles à modérés ($r \le 1024$).
• Qualité d'Approximation : La méthode maintient une qualité d'approximation de la norme de trace comparable à celle de RPCholesky. Elle ne sacrifie pas l'exactitude de l'approximation du noyau standard pour gagner en performance VFE.
• Performance Prédictive : Dans les tâches de régression GP, l'amélioration de la VFE se traduit par une réduction des erreurs de prédiction (RMSE et MAE) à des rangs faibles à modérés.
• Sensibilité de la Taille du Lot : Augmenter la taille du lot $s$ produit des rendements décroissants en termes de performance mais améliore systématiquement l'écart de VFE et la précision prédictive. Même de petits lots (ex: $s=8$ ou $s=16$) apportent des gains substantiels par rapport à RPCholesky.

Signification
L'article affirme que la méthode proposée comble le fossé entre l'approximation matricielle algébrique et les objectifs d'inférence spécifiques aux tâches. En dérivant un gain exact en forme close pour la VFE, les auteurs fournissent une règle de pivot gourdie qui est explicitement alignée avec l'objectif d'inférence probabiliste des processus gaussiens. Les résultats suggèrent que pour les applications où le fonctionnel matriciel inclut des termes d'ajustement aux données ou de complexité, l'optimisation seule de l'erreur de norme de trace est insuffisante, et qu'une sélection sensible à l'objectif offre des performances pratiques supérieures sans engendrer de surcharge de calcul significative. La méthode est présentée comme une généralisation directe de RPCholesky qui incorpore des informations supplémentaires sur la fonction objectif.