Un Algorithme Adaptatif pour l'Optimisation Bilatérale sur les Variétés Riemanniennes

Informations Fondamentales

• ID de l'article: 2504.06042
• Titre: An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
• Auteurs: Xu Shi, Rufeng Xiao, Rujun Jiang (École des Sciences des Données, Université Fudan)
• Classification: math.OC (Optimisation et Contrôle)
• Conférence de Publication: NeurIPS 2025 (39ème Conférence sur les Systèmes de Traitement de l'Information Neuromorphe)
• Lien de l'article: https://arxiv.org/abs/2504.06042

Résumé

Les méthodes existantes pour résoudre les problèmes d'optimisation bilatérale riemannienne (RBO) nécessitent une connaissance préalable des informations du premier et du second ordre du problème ainsi que des paramètres de courbure de la variété riemannienne pour déterminer la taille du pas, ce qui impose des limitations pratiques lorsque les paramètres sont inconnus ou que leur calcul est infaisable. Cet article propose l'algorithme de descente de super-gradient riemannien adaptatif (AdaRHD) pour résoudre les problèmes RBO. À notre connaissance, AdaRHD est la première méthode en RBO à adopter une stratégie de taille de pas entièrement adaptative, éliminant le besoin de paramètres spécifiques au problème. Nous prouvons qu'AdaRHD atteint une complexité itérative O(1/ε) pour trouver un point ε-stationnaire, correspondant à la complexité des méthodes non-adaptatives existantes. De plus, nous prouvons que le remplacement de l'application exponentielle par une application de contraction maintient la même borne de complexité. Les expériences montrent qu'AdaRHD offre une robustesse supérieure tout en obtenant des performances comparables aux méthodes non-adaptatives existantes.

Contexte et Motivation de la Recherche

Contexte du Problème

Les problèmes d'optimisation bilatérale ont des applications très larges dans l'apprentissage automatique, notamment en apprentissage par renforcement, méta-apprentissage, optimisation d'hyperparamètres et apprentissage adversarial. L'optimisation bilatérale riemannienne (RBO) est une extension de l'optimisation bilatérale sur les variétés riemanniennes, dont la forme générale est:

$\min_{x \in \mathcal{M}_x} F(x) := f(x, y^*(x))$$\text{s.c. } y^*(x) = \arg\min_{y \in \mathcal{M}_y} g(x,y)$

où $\mathcal{M}_x, \mathcal{M}_y$ sont des variétés riemanniennes, $f,g$ sont des fonctions lisses, et $g(x,y)$ est géodésiquement fortement convexe par rapport à $y$.

Limitations des Méthodes Existantes

1. Dépendance aux paramètres: Les méthodes RBO existantes (telles que RHGD, RieBO, etc.) nécessitent une connaissance préalable des paramètres de forte convexité, des constantes de Lipschitz, des paramètres de courbure, etc. pour déterminer la taille du pas
2. Limitations pratiques: Ces paramètres sont souvent difficiles à estimer ou leur calcul est trop coûteux dans les applications réelles
3. Robustesse insuffisante: Les stratégies de taille de pas fixe sont sensibles à l'initialisation et aux conditions du problème

Motivation de la Recherche

La motivation centrale de cet article est de concevoir un algorithme RBO entièrement adaptatif capable de:

• Fonctionner sans connaissance préalable des paramètres spécifiques au problème
• Ajuster automatiquement la taille du pas pour s'adapter aux caractéristiques du problème
• Maintenir une complexité théorique comparable aux méthodes non-adaptatives
• Fournir une robustesse pratique supérieure

Contributions Principales

1. Premier algorithme RBO adaptatif: Proposition d'AdaRHD, le premier algorithme d'optimisation bilatérale riemannienne adoptant une stratégie de taille de pas entièrement adaptative, éliminant la dépendance à la forte convexité, aux constantes de Lipschitz et aux paramètres de courbure
2. Correspondance de la complexité théorique: Preuve qu'AdaRHD atteint une complexité itérative O(1/ε) pour trouver un point ε-stationnaire, correspondant à la complexité des méthodes non-adaptatives existantes
3. Extension par application de contraction: Preuve que le remplacement de l'application exponentielle par une application de contraction plus efficace en calcul maintient les mêmes garanties de complexité
4. Vérification expérimentale: Validation de l'efficacité et de la robustesse de l'algorithme sur plusieurs problèmes RBO, y compris l'apprentissage de super-représentation riemannienne et les problèmes d'optimisation robuste

Explication Détaillée de la Méthode

Définition de la Tâche

Considérons le problème d'optimisation bilatérale riemannienne:

• Problème de niveau supérieur: Minimiser $F(x) = f(x, y^*(x))$ sur la variété $\mathcal{M}_x$
• Problème de niveau inférieur: Pour un $x$ donné, résoudre $y^*(x) = \arg\min_y g(x,y)$ sur la variété $\mathcal{M}_y$
• Contraintes: $g(x,y)$ est géodésiquement fortement convexe par rapport à $y$, $f$ n'est pas requise d'être convexe

Technique Centrale: Super-Gradient Riemannien

Le super-gradient riemannien est défini comme: $G_F(x) = G_x f(x, y^*(x)) - G^2_{xy}g(x, y^*(x))[H^{-1}_y g(x, y^*(x))[G_y f(x, y^*(x))]]$

Puisque le calcul exact est difficile, on utilise un super-gradient riemannien approché: $\hat{G}_F(x, \hat{y}, \hat{v}) = G_x f(x, \hat{y}) - G^2_{xy}g(x, \hat{y})[\hat{v}]$

où $\hat{y}$ est une solution approchée du problème de niveau inférieur et $\hat{v}$ est une solution approchée du système linéaire.

Architecture de l'Algorithme AdaRHD

Algorithme 1: Étapes Principales d'AdaRHD

1. Résolution du problème de niveau inférieur: Utilisation de la descente de gradient adaptative
   • Mise à jour de la taille du pas: $b^2_{k+1} = b^2_k + \|G_y g(x_t, y^k_t)\|^2$
   • Mise à jour itérative: $y^{k+1}_t = \text{Exp}_{y^k_t}(-\frac{1}{b_{k+1}} G_y g(x_t, y^k_t))$
2. Résolution du système linéaire: Deux stratégies
   • Descente de gradient: Taille de pas adaptative similaire au problème de niveau inférieur
   • Gradient conjugué: Utilisation de la méthode du gradient conjugué dans l'espace tangent
3. Mise à jour de niveau supérieur: Descente de super-gradient adaptative
   • Mise à jour de la taille du pas: $a^2_{t+1} = a^2_t + \|\hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t)\|^2$
   • Mise à jour itérative: $x_{t+1} = \text{Exp}_{x_t}(-\frac{1}{a_{t+1}} \hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t))$

Points d'Innovation Technique

1. Stratégie de norme de gradient cumulée: Adoption de "l'inverse de la norme de gradient riemannien cumulée" comme taille de pas adaptative, sans nécessité de connaître les paramètres du problème
2. Adaptation à trois niveaux: Application de tailles de pas adaptatives au niveau supérieur, au niveau inférieur et au système linéaire, formant un cadre d'adaptation complet
3. Optimisation par application de contraction: Fourniture d'une version utilisant l'application de contraction à la place de l'application exponentielle, réduisant la complexité de calcul
4. Garanties théoriques: Analyse de convergence rigoureuse, traitant les défis techniques posés par la structure géométrique des variétés riemanniennes

Configuration Expérimentale

Ensembles de Données et Problèmes

1. Problèmes simples de similarité matricielle: Optimisation sur les variétés de Stiefel et les variétés SPD
   • Échelle de données: n=100 et n=1000
   • Configuration des paramètres: d=50, r=20, λ=0.01
2. Apprentissage profond de super-représentation: Ensemble de données AFEW de reconnaissance d'émotions
   • Architecture de réseau SPD à 3 couches
   • 7 catégories d'émotions, 1747 échantillons d'entraînement
   • Distribution de classes déséquilibrée
3. Problèmes d'optimisation robuste:
   • Problème de moyenne de Karcher robuste
   • Problème d'estimation du maximum de vraisemblance robuste

Méthodes de Comparaison

• RHGD-20/50: Descente de super-gradient riemannien, nombre maximal d'itérations du problème de niveau inférieur de 20/50
• AdaRHD-GD: AdaRHD utilisant la descente de gradient pour résoudre le système linéaire
• AdaRHD-CG: AdaRHD utilisant le gradient conjugué pour résoudre le système linéaire

Indicateurs d'Évaluation

• Valeur de la fonction objectif de niveau supérieur
• Erreur d'estimation du super-gradient
• Précision de validation
• Temps de convergence et nombre d'itérations

Résultats Expérimentaux

Résultats Principaux

Expériences sur problèmes simples:

• AdaRHD montre une vitesse de convergence plus rapide aux deux échelles de données
• Erreur d'estimation du super-gradient plus faible, particulièrement pour AdaRHD-CG
• Avantage en temps de calcul, particulièrement sur les problèmes à grande échelle

Analyse de robustesse:

• AdaRHD montre une robustesse significative sous différents paramètres de taille de pas initiale
• RHGD échoue avec des grands pas (5, 1, 0.5), tandis qu'AdaRHD converge toujours de manière stable
• AdaRHD-CG est le plus rapide pour atteindre 85% de précision de validation

Découvertes Clés

1. Avantage de robustesse: AdaRHD est insensible au choix de la taille de pas initiale, tandis que RHGD échoue complètement avec des pas inappropriés
2. Amélioration de l'efficacité: Bien qu'AdaRHD nécessite plus d'itérations externes, grâce à la stratégie adaptative, le temps de calcul total reste compétitif
3. Sélection de méthode: AdaRHD-CG surpasse AdaRHD-GD en précision et robustesse, mais ce dernier converge plus rapidement initialement

Analyse Théorique

Résultats de Complexité

Théorème 3.1: Sous les hypothèses standard, AdaRHD satisfait: $\frac{1}{T}\sum_{t=0}^{T-1} \|G_F(x_t)\|^2_{x_t} \leq \frac{C}{T} = O\left(\frac{1}{T}\right)$

Corollaire 3.1: Complexité pour atteindre un point ε-stationnaire:

• Nombre total d'itérations: T = O(1/ε)
• Complexité en gradient: $G_f = O(1/ε)$, $G_g = O(1/ε^2)$
• Complexité en produit Hessien-vecteur: O(1/ε²) pour AdaRHD-GD, Õ(1/ε) pour AdaRHD-CG

Défis Techniques

1. Structure géométrique: La courbure de la variété riemannienne introduit une complexité d'analyse supplémentaire
2. Inégalité triangulaire: Nécessité d'utiliser l'inégalité triangulaire spécifique aux variétés riemanniennes plutôt que ses homologues euclidiens
3. Analyse de taille de pas adaptative: La stratégie adaptative peut entraîner un comportement divergent initial, nécessitant un traitement théorique rigoureux

Travaux Connexes

Optimisation Bilatérale

• Optimisation bilatérale euclidienne: Méthodes AID, ITD, série de Neumann, gradient conjugué, etc.
• Méthodes adaptatives récentes: D-TFBO, etc.

Optimisation Riemannienne

• Méthodes classiques: Descente de gradient riemannien, gradient conjugué non-linéaire, gradient stochastique à variance réduite, etc.
• Méthodes adaptatives: RASA, RAMSGrad, Riemannian SAM, etc.

Optimisation Bilatérale Riemannienne

• RieBO/RieSBO: Optimisation bilatérale riemannienne déterministe et stochastique
• RHGD: Cadre de descente de super-gradient riemannien
• RF2SA: Méthode du premier ordre complètement aléatoire

Conclusion et Discussion

Conclusions Principales

1. AdaRHD est le premier algorithme d'optimisation bilatérale riemannienne entièrement adaptatif, éliminant la dépendance aux paramètres spécifiques au problème
2. Théoriquement, il atteint la même complexité O(1/ε) que les méthodes non-adaptatives
3. Les expériences valident l'efficacité de l'algorithme et ses avantages significatifs en robustesse

Limitations

1. Écart de complexité: Complexité en gradient et en produit Hessien-vecteur supérieure d'un facteur 1/ε par rapport aux méthodes non-adaptatives
2. Conditions d'hypothèse: Nécessité toujours requise de la forte convexité géodésique du problème de niveau inférieur
3. Algorithme à boucle simple vs double: Actuellement, seuls les algorithmes à double boucle sont considérés

Directions Futures

1. Algorithme à boucle simple: Conception d'algorithmes d'optimisation bilatérale riemannienne adaptatifs à boucle simple
2. Cadre stochastique: Extension à l'optimisation bilatérale riemannienne stochastique
3. Convexité faible: Traitement des objectifs de niveau inférieur géodésiquement convexes (non fortement convexes)
4. Optimisation de complexité: Exploration de stratégies adaptatives pour éliminer l'écart de 1/ε

Évaluation Approfondie

Avantages

1. Innovation théorique: Première réalisation d'une adaptation complète en RBO, analyse théorique rigoureuse
2. Valeur pratique: Amélioration significative de la robustesse et de la facilité d'utilisation de l'algorithme
3. Profondeur technique: Traitement réussi des défis techniques posés par la géométrie riemannienne
4. Expériences complètes: Vérification complète sur plusieurs scénarios d'application

Insuffisances

1. Coût de complexité: L'adaptabilité s'accompagne d'une complexité de calcul supplémentaire
2. Limitations d'hypothèse: Nécessité toujours de conditions d'hypothèse relativement fortes
3. Portée d'application: Principalement concentrée sur des variétés riemanniennes spécifiques

Impact

• Contribution académique: Progrès important dans le domaine d'intersection entre l'optimisation riemannienne et l'optimisation bilatérale
• Valeur pratique: Fourniture d'outils plus robustes pour l'optimisation bilatérale riemannienne dans les applications réelles
• Recherche ultérieure: Fondation pour les recherches ultérieures sur l'optimisation riemannienne adaptative

Scénarios d'Application

• Méta-apprentissage riemannien et recherche d'architecture neuronale
• Segmentation d'images et adaptation de rang faible
• Statistiques robustes et apprentissage automatique géométrique
• Toute application nécessitant une optimisation bilatérale sous contraintes de variétés

Cet article apporte une contribution importante au domaine de l'optimisation bilatérale riemannienne, réalisant pour la première fois une conception d'algorithme entièrement adaptative qui, tout en maintenant la complexité théorique, améliore significativement la praticité et la robustesse. Malgré un certain coût de complexité, son innovation théorique et sa valeur pratique en font un progrès important dans ce domaine.