Riemannian Optimization for Hadamard Products of Low-Rank Matrices

Résumé Technique : Optimisation Riemannienne pour les Produits de Hadamard de Matrices de Bas Rang

Formulation du Problème
L'article traite du défi consistant à modéliser des données possédant une structure multiplicative via le produit élémentaire (de Hadamard) de deux matrices de bas rang. La matrice cible $W \in \mathbb{R}^{m \times n}$ est modélisée comme :
$$W = (GH^\top) \circ (UV^\top)$$
où $G, U \in \mathbb{R}^{m \times r_1, r_2}$ et $H, V \in \mathbb{R}^{n \times r_1, r_2}$. Bien que cette formulation offre une efficacité de paramétrage par rapport à une factorisation standard de rang-$r_1r_2$ (nécessitant $(m+n)(r_1+r_2)$ paramètres contre $(m+n)r_1r_2$), elle introduit un paysage d'optimisation complexe. Spécifiquement, le modèle présente des symétries au-delà de l'invariance de reparamétrage de la classe Linéaire Générale (GL) standard. Le produit $W$ reste invariant sous des mises à l'échelle couplées des lignes et des colonnes entre les deux paires de facteurs $(G, H)$ et $(U, V)$. Ces degrés de liberté supplémentaires créent une géométrie complexe que les méthodes de descente de gradient euclidiennes standard peinent à naviguer efficacement.

Les solveurs existants font face à des limitations : la Descente de Gradient Alternée (AGD) ignore la géométrie spécifique et les symétries d'échelle, tandis que la Descente de Coordonnées par Blocs (BCD) est très efficace pour les pertes de type moindres carrés mais ne possède pas de solutions en forme close pour les pertes non quadratiques (par exemple, la prédiction de lien logistique ou l'entropie croisée), ce qui limite son applicabilité en statistiques robustes et dans d'autres domaines.

Méthodologie
Les auteurs proposent de formuler le problème d'apprentissage comme une tâche d'optimisation sur une variété quotient riemannienne. Cette approche tient compte explicitement des invariances naturelles du produit de Hadamard.

1. Géométrie de la Variété : Les auteurs définissent la variété quotient $\mathcal{M}$ en factorisant le groupe de symétrie complet $\mathcal{G}$, qui inclut :

   • L'invariance de reparamétrage GL standard pour chaque paire de facteurs.
   • De nouvelles symétries d'échelle de cross-Hadamard, où des matrices diagonales inversibles mettent à l'échelle les lignes et les colonnes à travers les deux paires de facteurs de manière inverse.
     La variété est construite à partir de l'espace des matrices de rang de colonne complet modulo cette action de groupe.

2. Nouvelle Métrique Riemannienne : Une contribution critique est la dérivation d'une métrique riemannienne bloc-diagonale ($g_x$) dérivée du pullback du produit de Frobenius.

   • Le pullback complet de la métrique couple les quatre blocs de facteurs, résultant en un système linéaire dense et coûteux en termes de calcul.
   • La métrique proposée ne conserve que les blocs diagonaux du pullback, écartant les termes croisés.
   • La métrique est définie via des matrices de poids ($S$-blocs) pour chaque ligne/colonne des facteurs. Par exemple, le poids pour la $i$-ème ligne de $G$ est $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$, où $Y = UV^\top$.
   • Invariance : La métrique est prouvée invariante sous les symétries de reparamétrage GL et de cross-Hadamard. Cela garantit que l'optimiseur est insensible à la répartition arbitraire des magnitudes entre les facteurs.
   • Connexion avec BCD : Les matrices de poids dans la métrique proposée correspondent exactement aux matrices d'équations normales utilisées dans les mises à jour BCD. Ainsi, le gradient riemannien peut être interprété comme effectuant une étape BCD "douce" simultanément sur toutes les lignes pour des fonctions de perte lisses arbitraires.

3. Algorithme d'Optimisation (RGD) : Les auteurs développent un algorithme de Descente de Gradient Riemannien (RGD) :

   • Calcul du Gradient : Le gradient riemannien est calculé en résolvant des systèmes linéaires $r \times r$ indépendants (un par ligne/colonne) en utilisant les $S$-blocs.
   • Taille du Pas : Un pas de Cauchy de type Gauss-Newton sans réglage est dérivé. Ce pas est invariant sous le groupe de symétrie et ne nécessite aucun réglage d'hyperparamètre.
   • Rétraction : Une rétraction additive est utilisée pour ramener les mises à jour sur la variété.
   • Complexité : Le coût par itération évolue linéairement avec le nombre d'entrées observées $N$ ($O(Nr)$) et polynomialement avec les rangs ($O((m+n)r^4)$), ce qui le rend efficace pour de grands ensembles de données.

Contributions Clés

1. Caractérisation Géométrique : Description formelle de la structure de la variété quotient pour les produits de Hadamard, identifiant les symétries de reparamétrage GL et de cross-Hadamard.
2. Métrique Invariante d'Échelle : Proposition d'une nouvelle métrique riemannienne bloc-diagonale qui respecte le groupe de symétrie complet et découple l'optimisation en sous-problèmes indépendants de lignes/colonnes.
3. Développement d'Algorithme : Dérivation d'un algorithme RGD avec un pas de Gauss-Newton sans réglage qui supporte toute fonction de perte lisse, contrairement à la BCD qui est restreinte aux moindres carrés.
4. Validation Empirique : Démonstration que la méthode atteint des performances comparables à la BCD sur les tâches de moindres carrés tout en surpassant cette dernière sur les objectifs non quadratiques et en obtenant des résultats supérieurs dans des configurations spécifiques de rang de Hadamard.

Résultats Expérimentaux
Les auteurs ont évalué la RGD sur des données synthétiques et réelles :

• Tests de Stress Synthétiques : Sur des cibles synthétiques de $2\,000 \times 1\,000$, la RGD a démontré :
  • Invariance d'Échelle : L'erreur de récupération est restée constante à travers diverses séparations d'échelle diagonale ($\kappa_{scale}$), vérifiant empiriquement la propriété d'invariance de la métrique. En revanche, l'AGD a montré une sensibilité à l'échelle.
  • Conditionnement : La RGD a performé de manière comparable à la BCD à travers divers nombres de condition des facteurs, surpassant significativement l'AGD.
  • Robustesse au Bruit : La RGD a convergé vers le plancher de bruit au même rythme que la BCD, alors que l'AGD accusait un retard.
• Données Réelles :
  • Approximation de Matrice Complète : Sur les jeux de données Camera, Football et Les Misérables, la RGD a suivi étroitement la BCD en termes d'erreur relative, confirmant que la métrique fournit un préconditionnement équivalent à la BCD pour les pertes quadratiques.
  • MovieLens-1M : Dans une tâche de complétion de matrice avec un budget de paramètres fixe ($r_1+r_2=6$), la RGD a obtenu le RMSE de test le plus bas parmi toutes les configurations de rang de Hadamard testées. Notamment, la configuration équilibrée $(3,3)$ a surpassé la configuration quasi-vanilla $(1,5)$, suggérant que la capacité d'interaction de Hadamard ($r_1r_2$) contribue à la précision. La RGD a systématiquement surpassé l'AGD et a obtenu un RMSE inférieur à la BCD dans les configurations véritablement Hadamard.

Signification et Revendications
L'article prétend combler le fossé entre l'efficacité de la BCD pour les problèmes de moindres carrés et la flexibilité des méthodes basées sur le gradient pour les pertes lisses générales. En élevant le problème à une variété quotient riemannienne, les auteurs fournissent un cadre principled qui gère les symétries complexes des produits de Hadamard. L'algorithme RGD proposé offre une méthode d'optimisation sans réglage et invariante d'échelle qui passe à l'échelle linéairement avec la taille des données. Les auteurs affirment que ce cadre s'étend naturellement aux produits de $k$ matrices de bas rang et est compatible avec d'autres solveurs riemanniens (ex: gradients conjugués, méthodes de région de confiance), offrant une alternative robuste aux solveurs existants pour la modélisation de rang faible multiplicatif.