State-Dependent Lyapunov Method for Rank-1 Matrix Factorization

1. Énoncé du problème

L'article examine les dynamiques de convergence de la Descente de Gradient (GD) appliquée au problème non convexe de la Factorisation de Matrice de Rang 1. L'objectif est de minimiser l'erreur de reconstruction :
$$\min_{A \in \mathbb{R}^{n \times 1}, B \in \mathbb{R}^{m \times 1}} R(A, B) = \frac{1}{2} \|BA^\top - X\|_F^2$$
où $X$ est une matrice cible.

Défis clés :

• Non-convexité : Le problème possède un continuum de minimiseurs globaux et un paysage complexe.
• Dynamiques discrètes : Alors que le flot de gradient (temps continu) préserve l'invariant de « balance » ($B^\top B - A^\top A$), la GD en temps discret ne le fait pas. Cela rend l'analyse de la convergence difficile, en particulier avec de grandes tailles de pas (régime de la limite de stabilité).
• Points stationnaires : L'ensemble des points stationnaires inclut non seulement les minimiseurs globaux, mais aussi un continuum de points de selle non minimiseurs (par exemple, où $A=B=0$ mais les composantes de bruit sont non nulles). Prouver que la GD évite ces ensembles non minimiseurs constitue un obstacle majeur.

2. Méthodologie : Cadre de Lyapunov dépendant de l'état

Les auteurs proposent une nouvelle approche basée sur des certificats ancrée dans un Cadre de Lyapunov dépendant de l'état. Au lieu de chercher une unique fonction de Lyapunov fixe (souvent impossible pour les problèmes non convexes à minimiseurs multiples), ils introduisent une famille paramétrée de certificats quadratiques.

A. Le mécanisme de certificat

L'objet central est un certificat quadratique paramétré $I(\delta; \cdot)$, où $\delta$ est un paramètre d'état qui évolue le long de la trajectoire.

• Forme : Pour la factorisation scalaire, le certificat est défini comme suit :
  $$I_{sc}(\delta; a, b) = \delta(a^2 + b^2) - \delta^2 ab + \delta^2 - 4$$
• Ensembles de niveau rétrécissants : La propriété clé est que pour une trajectoire commençant à l'intérieur d'un ensemble de niveau $\{I(\delta; \cdot) \leq 0\}$, une seule étape de GD avec une taille de pas $\eta < \delta$ mappe l'itéré suivant strictement à l'intérieur de l'ensemble de niveau.
• Paramètre d'état monotone : Ce mouvement « vers l'intérieur » force le paramètre d'état $\delta_t$ à augmenter de manière monotone ($\delta_{t+1} > \delta_t$). La trajectoire est piégée dans une séquence imbriquée d'ellipses rétrécissantes (ensembles de niveau) indexées par $\delta_t$.

B. Cadre théorique

L'article formalise cela via des axiomes structurels (A1–A7) pour une fonction de Lyapunov dépendante de l'état :

1. Définition positive et imbriquement : Les ensembles de niveau rétrécissent lorsque $\delta$ augmente.
2. Monotonie : La valeur du certificat diminue (ou reste non positive) après une étape de GD.
3. Unicité : Grâce à une analyse locale de Lagrange aux points stationnaires, les auteurs prouvent que sous ces axiomes, la forme quadratique $P(\delta)$ est uniquement déterminée. Cela explique pourquoi la forme algébrique spécifique du certificat émerge naturellement des dynamiques plutôt que d'être une construction ad hoc.

3. Contributions clés

1. Preuves de convergence pour la factorisation de rang 1

Les auteurs prouvent que pour presque toute initialisation dans une « région certifiée » (définie par $I(\delta_{init}) \leq 0$) :

• Régime pré-critique ($\eta < 1/\sigma$) : La trajectoire converge ponctuellement vers un minimiseur global.
  • Mécanisme : L'augmentation monotone de $\delta_t$ force la trajectoire vers une limite $\delta^*$. Si $\delta^* < 2$, les termes de reste dans la récursion forcent le résidu à zéro.
  • Gestion du continuum : Une contribution technique critique consiste à écarter la convergence vers le continuum de points stationnaires non minimiseurs. La frontière du certificat limite les limites non minimiseuses possibles à un ensemble fini. Combinée à une analyse d'instabilité locale et à un argument de couverture compacte, cela exclut les limites non minimiseuses pour presque toutes les initialisations.
• Régime post-critique ($1/\sigma < \eta < 2/\sigma$) : La trajectoire ne converge pas vers un minimiseur mais s'effondre sur une variété terminale équilibrée ($A=B$, bruit $=0$). Sur cette variété, les dynamiques se réduisent à une application 1D qui exhibe une orbite périodique d'ordre 2 attractive (phénomène de limite de stabilité).

2. Extension à l'approximation de rang 1

L'article analyse le cas où $X = \text{diag}(1, \sigma)$ avec $\sigma \in (0, 1)$.

• Ils dérivent une famille de certificats à deux paramètres $I(\delta, \xi; \cdot)$ pour traiter séparément les blocs de signal et de bruit.
• Ils fournissent des preuves numériques suggérant l'existence d'une branche admissible continue $\xi(\delta)$, bien qu'une preuve rigoureuse reste ouverte.
• Contraste : Contrairement à la factorisation, l'approximation de rang 1 avec de grandes tailles de pas conduit à une divergence (les normes croissent sans borne), soulignant que le comportement de la limite de stabilité est spécifique à la structure de factorisation.

3. Généralisation aux pertes augmentées

Le cadre est montré comme s'étendant aux pertes scalaires augmentées quartiques $R(a,b) = \frac{1}{2}(ab-1)^2 + \mu(ab-1)^4$. Des expériences numériques confirment que le certificat reste prédictif pour certains $\mu$, suggérant la robustesse de la méthode au-delà de la perte quadratique exacte.

4. Résultats clés

• Théorème 1 (Factorisation scalaire/de rang 1) : Pour $\eta \in (0, 1/\sigma)$, si l'initialisation satisfait la condition de certificat, la GD converge vers un minimiseur global pour presque toute initialisation.
• Théorème 2 (Comportement post-critique) : Pour $\eta \in (1/\sigma, 2/\sigma)$, les trajectoires certifiées convergent vers la variété terminale équilibrée et exhibent des oscillations périodiques d'ordre 2 (limite de stabilité).
• Théorème 3 (Approximation de rang 1) : La convergence n'est garantie que sous des conditions plus strictes impliquant un seuil $\delta_{th}$. Crucialement, pour $\eta > 1$, les dynamiques d'approximation divergent, contrairement au cas de factorisation.
• Théorème d'unicité : Le certificat quadratique dépendant de l'état est la solution unique satisfaisant les axiomes structurels dérivés de la monotonie des dynamiques.

5. Signification et impact

• Au-delà des preuves ad hoc : L'article s'éloigne de la « devinette » de fonctions de Lyapunov. Il fournit une déduction axiomatique systématique montrant que le certificat est une nécessité structurelle des dynamiques de descente de gradient pour cette classe de problèmes.
• Résolution du problème du continuum : Il offre un mécanisme rigoureux pour gérer le continuum de points stationnaires non minimiseurs, un obstacle courant dans l'analyse de la factorisation de matrices de faible rang.
• Explication de la limite de stabilité (EoS) : Il fournit une explication géométrique des phénomènes EoS, montrant comment les trajectoires sont canalisées vers une variété terminale où elles se stabilisent dans des cycles stables plutôt que de diverger ou de converger vers un point fixe.
• Distinction entre factorisation et approximation : Le travail met en évidence une différence fondamentale dans la stabilité de la GD pour la factorisation de matrices (dynamiques bornées et structurées) par rapport à l'approximation de matrices (divergence potentielle) lors de l'utilisation de grandes tailles de pas.
• Validation numérique : Des expériences extensives valident les bornes théoriques, montrant que les certificats sont serrés pour un faible bruit et prédisent la transition vers des orbites périodiques d'ordre 2 et la divergence.

En résumé, cet article établit une puissante Méthode de Lyapunov dépendante de l'état qui unifie l'analyse de la convergence, de la stabilité et des phénomènes de limite de stabilité dans la factorisation de matrices de rang 1, fournissant à la fois des preuves rigoureuses et des insights géométriques profonds sur le comportement de la Descente de Gradient.