Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization

Cet article établit la convergence asymptotique et la complexité en $\widetilde{O}(\epsilon^{-2})$ d'une famille d'algorithmes de majoration-minimisation par blocs pour l'optimisation non convexe sous contraintes sur des variétés de Riemann, tout en validant expérimentalement leur supériorité par rapport aux méthodes euclidiennes standards.

L'essentiel

🌍 L'Exploration de la Montagne : Une Méthode pour Trouver le Sommet (ou la Vallée)

Imaginez que vous êtes un randonneur perdu sur une immense montagne. Votre objectif est de trouver le point le plus bas de la vallée (le minimum d'énergie) ou le sommet le plus haut. Mais il y a un problème : le terrain est très accidenté, il y a des falaises, des lacs, et vous ne pouvez pas voir le paysage entier d'un seul coup. De plus, vous avez un sac à dos très lourd qui vous oblige à suivre des chemins spécifiques (ce sont les contraintes).

C'est exactement le problème que les mathématiciens et les informaticiens tentent de résoudre avec des algorithmes d'optimisation. Ce papier, écrit par Yuchen Li et ses collègues, propose une nouvelle façon intelligente de naviguer sur ce terrain difficile, en particulier quand le terrain n'est pas plat comme une table (espace euclidien), mais qu'il a la forme d'une sphère, d'un tore ou d'une surface complexe (ce qu'on appelle une variété de Riemann).

1. La Méthode "Majoration-Minimisation" (BMM) : Le Jeu du "Plus Petit que le Réel"

L'algorithme principal dont parle le papier s'appelle le Block Majorization-Minimization (BMM). Pour le comprendre, imaginons que vous devez ranger une pièce encombrée (votre fonction à optimiser), mais que c'est trop difficile de tout faire d'un coup.

• L'idée : Au lieu de tout ranger d'un coup, vous vous concentrez sur un seul coin de la pièce à la fois (un "bloc").
• La Magie (Majorisation) : Pour ce coin, vous ne regardez pas le vrai chaos, mais vous créez une carte simplifiée (un "surrogate") qui est toujours au-dessus du vrai désordre. C'est comme si vous dessiniez une enveloppe autour du tas de vêtements : cette enveloppe est plus haute que les vêtements, mais elle est facile à manipuler.
• L'Action (Minimisation) : Vous rangez ce coin en suivant la carte simplifiée. Comme la carte est au-dessus du vrai tas, en la descendant, vous êtes sûr de ne pas remonter le vrai tas.
• La Répétition : Vous passez au coin suivant, puis au suivant, et vous recommencez.

Le papier montre que cette méthode fonctionne même si le sol sous vos pieds est courbe (comme une sphère) et non plat.

2. Le Terrain Courbe : Pourquoi c'est compliqué ?

Dans la vie de tous les jours, nous pensons en lignes droites. Si vous voulez aller du point A au point B, vous tracez une ligne droite.
Mais imaginez que vous marchez sur la surface de la Terre (une sphère). La "ligne droite" n'existe pas ; vous devez suivre un arc de cercle (un grand cercle). C'est ce qu'on appelle la géométrie riemannienne.

Le papier explique comment adapter notre méthode de "rangement de pièce" pour qu'elle fonctionne sur ces surfaces courbes, comme :

• Les variétés de Stiefel : Imaginez un ensemble de bâtons qui doivent rester parfaitement perpendiculaires les uns aux autres (comme les axes X, Y, Z d'un avion). C'est crucial pour la reconnaissance faciale ou l'analyse de données.
• Les espaces hyperboliques : Des terrains qui ressemblent à des selles de cheval, où les règles de la géométrie changent.

3. La Preuve de la Réussite : "On va y arriver !"

Les auteurs ne se contentent pas de dire "ça marche". Ils prouvent deux choses essentielles :

1. La Convergence (On arrive bien quelque part) : Peu importe où vous commencez votre randonnée (même si vous partez du mauvais côté de la montagne), si vous suivez cette méthode, vous finirez par vous stabiliser dans une zone "stationnaire". C'est-à-dire un endroit où, si vous bougez d'un petit pas dans n'importe quelle direction autorisée, vous ne descendez plus vraiment. C'est le meilleur endroit possible compte tenu des obstacles.
2. La Vitesse (Combien de temps ça prend ?) : Ils calculent exactement combien de pas (itérations) il faut pour atteindre un résultat précis.
   • L'analogie : C'est comme dire : "Pour atteindre une précision de 99%, il vous faudra environ 1000 pas".
   • Le papier montre que pour des problèmes complexes sur ces surfaces courbes, la méthode est très efficace (elle atteint la précision en un nombre de pas raisonnable, noté mathématiquement $\tilde{O}(\epsilon^{-2})$).

4. À quoi ça sert dans la vraie vie ?

Le papier ne reste pas dans la théorie. Il montre comment cette méthode améliore des technologies que nous utilisons peut-être sans le savoir :

• Le suivi de sous-espaces géodésiques : Imaginez suivre un objet qui se déplace dans un espace complexe (comme une caméra qui suit un visage qui tourne). La méthode permet de prédire le mouvement plus vite et plus précisément.
• L'estimation de probabilités optimistes : Dans la finance ou la météo, on essaie de prédire le futur. Cette méthode aide à trouver la meilleure estimation possible même quand les données sont bruitées ou incertaines.
• L'apprentissage de dictionnaires (CP-Dictionary Learning) : C'est comme apprendre à un ordinateur à reconnaître des motifs dans des images en décomposant l'image en blocs de base. Sur des surfaces courbes, cela permet de mieux compresser les données ou de mieux les analyser.
• L'ACP Robuste (Robust PCA) : Imaginez une photo de foule où quelqu'un a fait une tache de café géante. L'objectif est de retrouver la photo originale (le fond) et d'isoler la tache. Cette méthode le fait mieux que les anciennes techniques, même si la photo est très abîmée.

En Résumé

Ce papier est comme un guide de randonnée pour les mathématiciens. Il leur dit :

"Hé, si vous voulez résoudre des problèmes d'optimisation sur des terrains courbes et complexes, n'essayez pas de tout faire d'un coup. Utilisez notre méthode 'Block MM' : décomposez le problème, utilisez des cartes simplifiées pour avancer bloc par bloc, et vous arriverez au but plus vite et plus sûrement que jamais auparavant."

C'est une avancée majeure car elle rend ces calculs complexes plus rapides, plus fiables et applicables à une multitude de problèmes réels, de l'intelligence artificielle à l'analyse de données médicales.

Résumé technique

Voici un résumé technique détaillé du papier "Convergence and Complexity of Block Majorization-Minimization for Constrained Block-Riemannian Optimization" (Convergence et complexité de la minimisation par majorisation-bloc pour l'optimisation contrainte sur des variétés de Riemann).

1. Problématique

Le papier s'intéresse à la minimisation de fonctions objectives non-convexes et lisses définies sur un produit d'ensembles de contraintes, où chaque ensemble est un sous-ensemble fermé d'une variété de Riemann. Le problème est formulé comme suit :

$$\min_{\theta = [\theta^{(1)}, \dots, \theta^{(m)}]} f(\theta) \quad \text{sous } \theta^{(i)} \in \Theta^{(i)} \subseteq \mathcal{M}^{(i)}$$

où $\mathcal{M}^{(i)}$ sont des variétés de Riemann et $\Theta^{(i)}$ sont des ensembles de contraintes (qui peuvent être l'ensemble de la variété ou un sous-ensemble).

Défis principaux :

• Non-convexité : Il est généralement impossible de garantir la convergence vers un optimum global à partir d'une initialisation arbitraire. L'objectif est donc de garantir la convergence vers des points stationnaires.
• Géométrie : La présence de contraintes sur des variétés (ex: matrices orthogonales, matrices de rang fixe, espaces hyperboliques) rend les méthodes d'optimisation euclidiennes standard inapplicables ou inefficaces.
• Complexité itérative : Bien que la convergence asymptotique de certaines méthodes soit connue, les bornes de complexité (nombre d'itérations pour atteindre un point $\epsilon$-stationnaire) pour les méthodes par blocs sur des variétés étaient largement inconnues ou non établies dans la littérature.

2. Méthodologie : RBMM

Les auteurs proposent et analysent l'algorithme RBMM (Riemannian Block Majorization-Minimization), une généralisation de la méthode de Majorisation-Minimisation (MM) au cadre des variétés de Riemann avec plusieurs blocs de variables.

Principe de l'algorithme :
À chaque itération $n$, pour chaque bloc $i = 1, \dots, m$, l'algorithme :

1. Construit une fonction de majoration (surrogate) $g_n^{(i)}$ de la fonction objective partielle $f_n^{(i)}$ (où les autres blocs sont fixés).
2. Minimise cette fonction de majoration sur l'ensemble de contraintes $\Theta^{(i)}$ pour mettre à jour le bloc $\theta_n^{(i)}$.

Types de surrogates analysés :
L'analyse couvre trois familles de fonctions de majoration :

1. Surrogates g-lisses (Geodesically smooth) : Des fonctions qui satisfont une condition de lissité par rapport à la géométrie de la variété (gradient lipschitzien par rapport au transport parallèle).
2. Surrogates proximaux riemanniens : De la forme $g(\theta) = f(\theta) + \frac{\lambda}{2} d^2(\theta, \theta_{n-1})$, utilisant la distance géodésique $d$.
3. Surrogates proximaux euclidiens : De la forme $g(\theta) = f(\theta) + \frac{\lambda}{2} \|\theta - \theta_{n-1}\|^2$, utilisant la norme euclidienne de l'espace ambiant (applicable lorsque la variété est plongée dans un espace euclidien, comme les variétés de Stiefel).

Hypothèses clés :

• L'objectif est g-lisse.
• Les écarts d'optimalité (inexactitude de la résolution des sous-problèmes) sont sommables.
• Les ensembles de contraintes ont un rayon d'injectivité uniformément borné.
• Pour les résultats de complexité, des hypothèses supplémentaires sur la régularisation (écart de majoration quadratique) sont requises.

3. Contributions Clés

Ce travail apporte plusieurs avancées théoriques majeures :

1. Optimisation Contrainte sur Variétés : L'analyse s'applique à des problèmes où les contraintes $\Theta^{(i)}$ sont des sous-ensembles fermés de variétés, et non nécessairement les variétés entières. Cela inclut des cas où les contraintes ne sont pas géodésiquement convexes.
2. Convergence Asymptotique :
   • Preuve que RBMM converge asymptotiquement vers l'ensemble des points stationnaires pour un nombre quelconque de blocs ($m \ge 1$).
   • Cette convergence est établie même en présence de calculs inexacts (sous-problèmes résolus de manière approchée).
3. Complexité Itérative (Résultat Principal) :
   • Établissement de bornes de complexité pour atteindre un point $\epsilon$-stationnaire.
   • Pour les surrogates proximaux (riemanniens ou euclidiens) et les surrogates g-lisses avec un écart de majoration quadratique, la complexité est de $\tilde{O}(\epsilon^{-2})$.
   • C'est la première fois que de telles bornes sont établies pour des méthodes de type MM par blocs sur des variétés de Riemann.
4. Robustesse aux Calculs Inexacts : La théorie démontre que l'algorithme reste convergent même si les sous-problèmes de minimisation ne sont pas résolus exactement, à condition que l'erreur décroisse suffisamment vite.
5. Généralité : Le cadre unifie et étend de nombreux algorithmes existants (MM Riemannien, descente de gradient par blocs, estimation de vraisemblance optimiste, etc.).

4. Résultats et Applications

Les auteurs valident leur théorie sur plusieurs applications stylisées et classiques :

• Variétés de Stiefel (Frames orthogonales) :
  • Application aux problèmes de suivi de sous-espace contraint géodésiquement et à la décomposition CP de dictionnaires.
  • Démonstration que les méthodes utilisant des surrogates lisses au sens euclidien (faciles à calculer) satisfont les conditions de lissité géodésique sur les variétés de Stiefel, permettant d'obtenir la complexité $\tilde{O}(\epsilon^{-2})$.
• Variétés Hadamardiennes (Courbure négative ou nulle) :
  • Application à l'estimation de vraisemblance optimiste sous la distance de Fisher-Rao (variété des matrices définies positives).
  • Utilisation de surrogates proximaux riemanniens qui sont fortement convexes géodésiquement sur ces variétés.
• PCA Robuste (Robust PCA) :
  • Application à la décomposition de matrices en composantes de faible rang et creuses sur des variétés de rang fixe.
  • Bien que la complexité $\tilde{O}(\epsilon^{-2})$ ne soit pas garantie ici (car la distance euclidienne n'est pas g-lisse sur les variétés de rang fixe), la convergence asymptotique vers les points stationnaires est prouvée.

Validation Expérimentale :
Les expériences numériques montrent que l'algorithme RBMM converge plus rapidement que les algorithmes euclidiens standards appliqués naïvement aux problèmes riemanniens, tout en maintenant une précision élevée.

5. Signification et Impact

Ce papier est significatif pour plusieurs raisons :

• Comblement d'un vide théorique : Il fournit les premières garanties de complexité itérative pour des méthodes de type MM par blocs dans un cadre riemannien contraint.
• Unification : Il offre un cadre théorique unifié qui englobe des algorithmes variés (MM, proximal, gradient projeté) et permet d'analyser leur performance sous un même prisme.
• Praticité : En montrant que des surrogates simples (comme les proximaux euclidiens) peuvent être utilisés efficacement sur des variétés complexes (comme Stiefel) tout en garantissant des taux de convergence optimaux, l'article facilite l'implémentation d'algorithmes robustes pour l'apprentissage automatique moderne (traitement de données structurées, vision par ordinateur, statistiques sur variétés).
• Gestion de l'inexactitude : La prise en compte explicite des calculs inexacts rend l'algorithme plus applicable en pratique, où la résolution exacte de sous-problèmes sur des variétés peut être coûteuse ou impossible.

En résumé, ce travail établit des fondations théoriques solides pour l'optimisation non-convexe par blocs sur des variétés, garantissant à la fois la convergence et des taux de convergence quantifiables, tout en s'appliquant à une large gamme de problèmes pratiques en science des données.