Implicit Regularization in Perturbed Deep Matrix Factorization: Spectral Conditions and Stability

Résumé Technique : Régularisation Implicite dans la Factorisation de Matrices Profondes Perturbée

Énoncé du Problème
Les modèles d'apprentissage profond, en particulier ceux surparamétrés, généralisent souvent bien malgré la nature non convexe de leurs objectifs d'entraînement. Une explication prédominante est la « régularisation implicite », où l'algorithme d'optimisation (par exemple, la descente de gradient) induit un biais structurel vers des solutions spécifiques, telles que des matrices de faible rang, même sans régularisateurs explicites. Alors que le comportement de la descente de gradient dans la factorisation de matrices profondes sans bruit a été analysé, la stabilité de ce phénomène dans des conditions réalistes reste une question ouverte. Plus précisément, cet article examine comment le bruit additif (perturbations) dans la matrice cible de vérité terrain affecte la dynamique de régularisation implicite de la factorisation de matrices profondes. Le problème central est de déterminer si la « phase de faible rang » — une période transitoire où le rang effectif de l'itéré reste proche d'un rang cible $L$ — persiste lorsque la matrice cible $\mathbf{W}$ est corrompue par une matrice de bruit $\mathbf{E}$, résultant en une cible perturbée $\tilde{\mathbf{W}} = \mathbf{W} + \mathbf{E}$.

Méthodologie
Les auteurs analysent la dynamique de la descente de gradient appliquée au problème de factorisation de matrices profondes :
$$\min_{\mathbf{W}_1, \dots, \mathbf{W}_N} \|\mathbf{W}_N \cdots \mathbf{W}_1 - \tilde{\mathbf{W}}\|_F^2$$
où $\tilde{\mathbf{W}}$ est la matrice de vérité terrain symétrique perturbée. L'analyse se déroule en trois étapes :

1. Analyse Spectrale Sans Bruit : L'article revisite d'abord le cadre sans bruit pour dériver des conditions suffisantes explicites pour l'existence d'un « intervalle de faible rang » $[T_0, T_1]$ non vide. Cela implique l'analyse de la fonction $T(\lambda)$, qui représente le temps nécessaire pour qu'une valeur propre $\lambda$ soit récupérée. Les auteurs décomposent $T(\lambda)$ en composantes impliquant des termes logarithmiques et des fonctions plafond, prouvant que sous des conditions spécifiques de lacunes spectrales (grandes écarts entre les valeurs propres) et des choix appropriés d'initialisation/taille de pas, le temps de récupération des valeurs propres inférieures est strictement supérieur au temps de récupération des valeurs propres supérieures, créant ainsi une fenêtre où le rang effectif est stable.

2. Modélisation de la Perturbation et Convergence : L'étude modélise le bruit $\mathbf{E}$ comme une matrice gaussienne symétrique. En utilisant l'inégalité de Weyl et la théorie des perturbations matricielles, les auteurs bornent l'écart entre les valeurs propres de la matrice perturbée $\tilde{\mathbf{W}}$ et de la matrice vraie $\mathbf{W}$. Ils analysent la dynamique de la descente de gradient au niveau des valeurs propres individuelles, établissant des garanties de convergence pour le système perturbé. L'analyse quantifie comment la taille de la perturbation $\|\mathbf{E}\|$ affecte la complexité itérative et la récupération des valeurs propres non négatives.

3. Stabilité de la Régularisation Implicite : S'appuyant sur les résultats de convergence, les auteurs prouvent que la phase de faible rang persiste dans le cadre perturbé. Ils définissent un intervalle de faible rang perturbé $[\tilde{T}_0, \tilde{T}_1]$ et dérivent des bornes explicites sur le décalage de ces extrémités par rapport à l'intervalle sans bruit $[T_0, T_1]$. L'analyse repose sur le suivi du rang effectif $r(\mathbf{W}(k)) = \|\mathbf{W}(k)\|_* / \|\mathbf{W}(k)\|$ et la borne de l'erreur entre le rang effectif de l'itéré et l'approximation de rang $L$ de la cible sans bruit.

Contributions Clés

• Conditions Spectrales Explicites pour les Intervalles Sans Bruit : L'article fournit une dérivation rigoureuse de conditions spectrales suffisantes (impliquant les écarts de valeurs propres, l'échelle d'initialisation $\alpha$, et la taille de pas $\eta$) garantissant l'existence d'un intervalle de faible rang $[T_0, T_1]$ non vide dans le cas sans bruit. Cela clarifie la dépendance de la phase de faible rang vis-à-vis du spectre cible, qui était auparavant moins transparente.
• Stabilité Spectrale sous Perturbation : Les auteurs établissent que le comportement de régularisation implicite est stable sous des perturbations additives. Ils prouvent que la dynamique de la descente de gradient sur la matrice perturbée $\tilde{\mathbf{W}}$ présente toujours une phase de faible rang, à condition que la taille de la perturbation soit bornée.
• Bornes Quantitatives sur les Effets de Perturbation : Le travail fournit des bornes d'erreur explicites quantifiant :
  • Le décalage des extrémités de l'intervalle de faible rang ($\tilde{T}_0, \tilde{T}_1$) en fonction de $\|\mathbf{E}\|$.
  • L'erreur d'approximation du rang effectif par rapport à l'approximation de rang $L$ de la cible sans bruit.
  • L'erreur de récupération des valeurs propres non négatives.
• Garanties de Convergence : L'article prouve la convergence de la dynamique de la descente de gradient perturbée et quantifie la complexité itérative requise pour atteindre des niveaux de précision spécifiques en présence de bruit.

Résultats

• Constatations Théoriques : Les théorèmes principaux (Théorèmes 5.1–5.3) démontrent que pour une cible perturbée $\tilde{\mathbf{W}} = \mathbf{W} + \mathbf{E}$, le rang effectif des itérés de la descente de gradient reste proche de celui de la meilleure approximation de rang $L$ de la cible sans bruit $\mathbf{W}$ sur un intervalle de temps perturbé. Les bornes d'erreur sont linéaires en fonction de la taille de la perturbation $\|\mathbf{E}\|$. Plus précisément, l'article montre que l'intervalle de faible rang $[\tilde{T}_0, \tilde{T}_1]$ est une version décalée de $[T_0, T_1]$, avec une amplitude de décalage dépendante de $\|\mathbf{E}\|$, des écarts spectraux et de la taille de pas.
• Validation Numérique : Les expériences confirment les prédictions théoriques. La Figure 1 illustre que les plateaux de faible rang (régularisation implicite observable) apparaissent lorsque les écarts spectraux et les tailles de pas satisfont les conditions dérivées, et disparaissent lorsque ces conditions sont violées (par exemple, de grandes tailles de pas). La Figure 2 démontre que lorsque le niveau de bruit augmente, l'erreur d'approximation croît et les plateaux de faible rang se décalent dans le temps, ce qui est cohérent avec les bornes dérivées.

Signification
L'article prétend fournir la première analyse rigoureuse de la régularisation implicite dans la factorisation de matrices profondes sous perturbations additives. Sa signification réside dans le pont établi entre les modèles théoriques idéalisés sans bruit et les scénarios pratiques où les données sont bruyantes (par exemple, en raison d'erreurs de mesure ou de mécanismes de préservation de la vie privée comme la confidentialité différentielle). En prouvant que la phase de faible rang est robuste face à un bruit borné et en quantifiant la dégradation en fonction de la taille de la perturbation, ce travail offre une fondation théorique pour comprendre pourquoi les réseaux linéaires profonds peuvent toujours bien généraliser dans des environnements bruyants. Les résultats suggèrent que la structure spectrale de la matrice cible est un déterminant critique à la fois de l'existence et de la stabilité de la régularisation implicite.