Résumé technique : Complétion de matrice inductive économe en échantillons avec bruit et informations latérales inexactes

1. Formulation du problème

L'article traite de la Complétion de Matrice Inductive (CMI), une variante de la complétion de matrice de faible rang où des informations a priori sur les espaces ligne et colonne de la matrice cible sont disponibles. L'objectif est de retrouver une matrice de rang $r$ de vérité terrain $L^\star \in \mathbb{R}^{n_1 \times n_2}$ à partir d'un sous-ensemble d'observations bruitées.

Le modèle d'observation est donné par :
$$M = P_\Omega(L^\star + E)$$
où $P_\Omega$ est la projection sur un ensemble d'entrées observées $\Omega$ (échantillonnées indépendamment avec une probabilité $p$), et $E$ est une matrice de bruit additif.

En CMI, l'utilisateur dispose de matrices d'informations latérales $X \in \mathbb{R}^{n_1 \times a_1}$ et $Y \in \mathbb{R}^{n_2 \times a_2}$, qui encodent des connaissances a priori sur les espaces colonne et ligne de $L^\star$.

• Informations latérales exactes : Les espaces colonne et ligne réels sont des sous-espaces des colonnes de $X$ et $Y$, respectivement. Cela permet de paramétrer $L^\star$ comme $L^\star = X Z^\star Y^\top$, où $Z^\star \in \mathbb{R}^{a_1 \times a_2}$ est une matrice de base de dimension inférieure.
• Informations latérales inexactes : Les sous-espaces d'informations latérales ne sont alignés avec les espaces réels qu'approximativement, caractérisés par un paramètre de déviation $\delta$ (mesuré via les angles principaux).

Le fossé : Des travaux antérieurs ont établi que la CMI avec des informations latérales exactes dans des contextes sans bruit atteint une complexité d'échantillonnage considérablement réduite (s'échelonnant sur les dimensions des caractéristiques $a_1, a_2$ plutôt que sur les dimensions ambiantes $n_1, n_2$). Cependant, dans des contextes bruyants, les méthodes existantes échouent soit à fournir des garanties d'erreur précises, soit exigent une complexité d'échantillonnage correspondant à la dimension ambiante, annulant ainsi les avantages des informations latérales. De plus, la plupart des garanties théoriques supposent des informations latérales exactes, ce qui est souvent irréaliste.

2. Méthodologie

Les auteurs proposent un algorithme de Descente de Gradient Projeté (DGP) avec Initialisation Spectrale pour résoudre le problème non convexe de la CMI.

Aperçu de l'algorithme

1. Paramétrisation : Au lieu d'estimer directement $L^\star$, l'algorithme estime des facteurs $A \in \mathbb{R}^{a_1 \times r}$ et $B \in \mathbb{R}^{a_2 \times r}$ tels que $Z \approx AB^\top$. La reconstruction est $\hat{L} = XAB^\top Y^\top$.
2. Fonction objectif : L'algorithme minimise une fonction de perte non convexe :
   $$f(A, B) = \frac{1}{2p} \| P_\Omega(XAB^\top Y^\top - M) \|_F^2 + \frac{1}{16} \| A^\top A - B^\top B \|_F^2$$
   Le deuxième terme agit comme un régularisateur d'équilibrage pour maintenir les valeurs singulières de $A$ et $B$ proches.
3. Initialisation : Une initialisation spectrale est effectuée en utilisant la SVD de rang $r$ de $\frac{1}{p} X^\top P_\Omega(M) Y$ pour fournir un point de départ proche de la vérité terrain.
4. Optimisation : L'algorithme effectue des étapes de descente de gradient suivies d'une projection sur un ensemble de contraintes qui impose l'incohérence (normes $\ell_{2,\infty}$ bornées).
   • Note : Les auteurs observent empiriquement que cette étape de projection est souvent inactive en pratique, mais elle est cruciale pour la preuve théorique.

Gestion des informations latérales inexactes

Pour le cas inexact, les auteurs proposent un Schéma d'Interpolation. Ils introduisent un objectif pénalisé qui interpole entre la complétion de matrice standard (ignorant les informations latérales) et la CMI (imposant l'alignement des informations latérales) :
$$\tilde{f}(\tilde{A}, \tilde{B}) = \frac{1}{2p} \| P_\Omega(\tilde{A}\tilde{B}^\top - M) \|_F^2 + \frac{1}{16} \| \tilde{A}^\top \tilde{A} - \tilde{B}^\top \tilde{B} \|_F^2 + \lambda \| \tilde{A}\tilde{B}^\top - XX^\top \tilde{A}\tilde{B}^\top YY^\top \|_F^2$$
Ici, $\lambda$ contrôle l'intensité de la pénalité d'information latérale. Un $\lambda$ faible privilégie l'ajustement aux données (robuste à la mauvaise spécification), tandis qu'un $\lambda$ élevé impose la structure inductive (efficace pour de faibles tailles d'échantillons).

3. Contributions clés et résultats théoriques

A. Informations latérales exactes avec bruit

L'article établit que la CMI bruyante peut atteindre une complexité d'échantillonnage réduite régie par la taille effective du problème ($a_1, a_2$) plutôt que par la dimension ambiante ($n_1, n_2$).

• Complexité d'échantillonnage : L'algorithme réussit avec $n_1 n_2 p \gtrsim a \cdot \text{poly}(r, \log n)$, où $a = \max(a_1, a_2)$. Cela correspond à la complexité réduite de la CMI sans bruit.
• Erreur d'estimation : L'erreur d'estimation s'échelonne comme suit :
  $$\| \hat{L} - L^\star \|_F \lesssim \text{niveau de bruit} \times \sqrt{\frac{a}{p}}$$
  Cela unifie la complexité d'échantillonnage réduite de la CMI sans bruit avec les garanties d'erreur précises de la complétion de matrice bruyante.
• Cœur technique : La preuve repose sur l'établissement d'une Condition de Régularité pour la fonction de perte de la CMI à cette complexité d'échantillonnage réduite. Cette condition garantit que le paysage de perte possède une géométrie locale favorable (propriétés de type forte convexité) près de la vérité terrain, permettant une convergence linéaire.

B. Informations latérales inexactes

Les auteurs étendent l'analyse aux cas où les informations latérales sont imparfaites ($\delta > 0$).

• Complexité d'échantillonnage : L'exigence de complexité d'échantillonnage réduite ($n_1 n_2 p \gtrsim a \cdot \text{poly}(r, \log n)$) reste suffisante même avec des informations latérales inexactes.
• Bornes d'erreur : L'erreur d'estimation se dégrade gracieusement avec l'inexactitude $\delta$. Plus précisément, l'erreur inclut un terme supplémentaire proportionnel à $\delta$, qui s'avère être optimal en ordre.
• Interpolation : La formulation pénalisée proposée permet à la méthode de se prémunir contre la mauvaise spécification. Les résultats empiriques suggèrent que le choix d'un $\lambda$ intermédiaire (via validation croisée) peut surpasser à la fois la CMI pure et la complétion de matrice standard dans des régimes où la taille de l'échantillon est limitée mais les informations latérales sont bruyantes.

4. Validation expérimentale

Les auteurs valident leur théorie par :

1. Simulations synthétiques :
   • SI exacte : La CMI atteint une récupération exacte et une erreur d'estimation inférieure à celle de la complétion de matrice standard à des probabilités d'échantillonnage ($p$) significativement plus faibles.
   • SI inexacte : La CMI surpasse la MC standard à de faibles tailles d'échantillons, mais son erreur atteint un plateau lorsque $p$ augmente (limitée par $\delta$), tandis que la MC standard continue de s'améliorer.
   • Interpolation : Le schéma d'interpolation parvient à équilibrer ces compromis, atteignant une erreur inférieure à celle des deux extrêmes lorsque $\lambda$ est ajusté.
2. Données réelles (MovieLens 100K) :
   • En utilisant les données démographiques des utilisateurs et les genres de films comme informations latérales, la CMI surpasse considérablement la complétion de matrice non inductive lorsque l'ensemble d'entraînement est petit (par exemple, $m=5000$).
   • À mesure que la taille de l'échantillon augmente, les méthodes non inductives finissent par rattraper leur retard, ce qui est cohérent avec la prédiction théorique selon laquelle l'avantage de la CMI est plus prononcé dans les régimes à faible échantillon.

5. Importance et revendications

L'article prétend combler un fossé significatif dans la compréhension théorique de la Complétion de Matrice Inductive :

1. Unification : Il unifie les garanties de complexité d'échantillonnage réduite de la CMI sans bruit avec les garanties d'erreur précises de la complétion de matrice bruyante, démontrant que les informations latérales restent bénéfiques même en présence de bruit.
2. Robustesse : Il fournit les premières garanties théoriques pour la CMI avec des informations latérales inexactes, montrant que l'efficacité d'échantillonnage est préservée et que l'erreur est contrôlée par le niveau de mauvaise spécification.
3. Efficacité algorithmique : En utilisant une approche de descente de gradient projeté non convexe, l'article propose une méthode computationnellement efficace qui évite le coût computationnel élevé des relaxations convexes (comme la minimisation de la norme nucléaire) tout en maintenant l'optimalité statistique.

Les auteurs notent que, bien que l'étape de projection soit théoriquement nécessaire pour leurs preuves, elle est empiriquement redondante dans leurs expériences, laissant la question de savoir si des garanties comparables peuvent être prouvées pour une descente de gradient non projetée comme une direction de recherche ouverte. Ils soulignent également les garanties entrée par entrée et les informations latérales partielles comme des axes de recherche futurs.