Riemannian Dueling Optimization

Cet article propose et analyse des algorithmes d'optimisation par duel sur les variétés riemanniennes, à savoir la descente de gradient normalisé (RDNGD) et la méthode de Frank-Wolfe sans projection (RDFW), en établissant leurs complexités théoriques et en validant leur efficacité par des expériences numériques.

L'essentiel

Imaginez que vous essayez de trouver le point le plus bas d'une vallée immense et mystérieuse, mais vous avez un problème : vous êtes aveugle. Vous ne pouvez pas voir le terrain, vous ne pouvez pas mesurer la hauteur de l'endroit où vous vous tenez, et vous ne pouvez même pas sentir la pente sous vos pieds.

La seule information que vous avez, c'est un guide local qui vous pose une question très simple à chaque étape :

"Si vous faites un petit pas vers la gauche ou un petit pas vers la droite, quel côté vous semble plus bas ?"

C'est ce qu'on appelle l'optimisation par duel (ou "dueling optimization"). Vous ne connaissez pas les valeurs exactes, vous ne connaissez que les préférences : "A est mieux que B".

Jusqu'à récemment, les mathématiciens savaient bien gérer ce genre de jeu si le terrain était plat et simple (comme un champ de football). Mais dans le monde réel, le terrain est souvent bizarre : il peut être courbé, torsadé, ou avoir des formes complexes (comme une sphère, un tore, ou des espaces mathématiques exotiques). C'est ce qu'on appelle un manifold riemannien.

Voici ce que fait cette nouvelle recherche, expliquée simplement :

1. Le Problème : Naviguer dans un monde courbé sans boussole

Dans de nombreux domaines modernes (comme les robots qui apprennent à marcher, ou les systèmes de recommandation qui choisissent entre deux films), l'espace des solutions n'est pas plat.

• Exemple Robotique : Pour orienter une caméra, on tourne dans l'espace 3D. Ce n'est pas une ligne droite, c'est une rotation.
• Exemple IA : Parfois, pour bien classer des images, il faut travailler sur des formes géométriques très spécifiques (comme des matrices spéciales).

Les anciennes méthodes qui fonctionnaient sur des terrains plats échouent ici. Si vous essayez de marcher tout droit sur une sphère, vous finirez par vous perdre. De plus, comme on ne peut pas connaître la "valeur" exacte de la solution (le niveau de la vallée), on ne peut pas utiliser les méthodes classiques qui ont besoin de gradients (pentes précises).

2. La Solution : RDNGD (La marche à l'aveugle intelligente)

Les auteurs proposent une nouvelle méthode appelée RDNGD (Descente de Gradient Normalisé par Duel Riemannien).

L'analogie du "Pas de géant" :
Imaginez que vous êtes sur une colline courbée. Vous ne savez pas où est le bas.

1. Vous choisissez une direction au hasard (comme si vous regardiez au hasard).
2. Vous demandez à votre guide : "Si je fais un petit pas dans cette direction, est-ce que c'est mieux que si je fais un pas dans la direction opposée ?"
3. Le guide répond : "Oui, la direction A est meilleure."
4. Vous faites un pas dans la direction A.

Le génie de cette méthode, c'est qu'elle est conçue spécifiquement pour les terrains courbés. Elle utilise des outils mathématiques spéciaux (comme l'application exponentielle) pour s'assurer que vos pas restent toujours sur le terrain, même si celui-ci est tordu. Elle ne se contente pas de "tirer" dans une direction ; elle ajuste sa boussole en fonction de la courbure du monde.

3. Le Problème des "Murs" : La méthode RDFW

Parfois, vous ne pouvez pas juste marcher n'importe où. Il y a des contraintes. Par exemple, vous devez rester à l'intérieur d'une sphère, ou sur une surface spécifique.

• La méthode classique (Projection) : Vous marchez, vous heurtez un mur, et vous êtes "projeté" de force à l'intérieur. C'est comme si quelqu'un vous poussait violemment contre le mur. C'est efficace, mais parfois très coûteux en calcul (comme si le mur était en béton armé et que le calcul de la projection prenait des heures).
• La nouvelle méthode (RDFW - Frank-Wolfe) : Les auteurs proposent une méthode "sans projection". Au lieu de marcher et de se faire repousser, vous demandez au guide : "Quel est le point le plus bas que je peux atteindre en ligne droite depuis ici, sans sortir du terrain ?" Vous vous dirigez ensuite vers ce point. C'est comme si vous glissiez le long du mur au lieu de vous y cogner. C'est beaucoup plus rapide et élégant pour certains problèmes complexes.

4. Pourquoi est-ce important ? (Les applications réelles)

Pourquoi se soucier de tout cela ? Parce que cela change la donne pour des technologies de pointe :

• Le piratage de l'IA (Attaque sur les réseaux de neurones) : Imaginez un hacker qui veut tromper une IA (comme une voiture autonome) en modifiant très légèrement une image de panneau stop. Le hacker ne connaît pas la formule mathématique de l'IA (c'est une "boîte noire"). Il ne peut que demander à l'IA : "Est-ce que cette image modifiée est plus trompeuse que celle-ci ?". Avec cette nouvelle méthode, le hacker peut trouver le moyen parfait de tromper l'IA en utilisant uniquement ces comparaisons, même si l'espace des modifications est très complexe.
• Le nivellement de l'horizon (Horizon Leveling) : Prenez une photo prise avec un téléphone penché. L'horizon est de travers. Souvent, on ne sait pas de combien degrés il est penché. Mais on peut demander à un humain (ou à une IA) : "Est-ce que cette version corrigée de l'image semble plus droite que celle-là ?". La méthode permet de trouver la rotation parfaite pour redresser l'image en ne faisant que des comparaisons, sans avoir besoin de connaître l'angle exact au départ.

En résumé

Cette recherche est comme un nouveau GPS pour les explorateurs aveugles.

• Avant, on savait guider les aveugles sur des terrains plats en leur disant "gauche/droite".
• Maintenant, grâce à cette étude, on peut guider les aveugles sur des terrains courbés, dans des labyrinthes complexes, et même dans des espaces où il est interdit de sortir des sentiers battus.
• Le tout, sans jamais avoir besoin de voir la carte ou de mesurer la hauteur, juste en comparant deux chemins à la fois.

C'est une avancée majeure pour rendre les robots plus intelligents, les systèmes de recommandation plus précis, et les algorithmes d'IA plus robustes, même quand on n'a pas toutes les informations en main.

Résumé technique

1. Problématique et Contexte

L'optimisation par duel (dueling optimization) vise à minimiser une fonction objectif $f(x)$ en n'ayant accès qu'à un oracle de comparaison (ou oracle de préférence) entre deux points, sans connaître les valeurs de la fonction ni les gradients. Ce cadre est crucial dans des domaines comme les systèmes de recommandation, la robotique (apprentissage par préférences humaines) et l'apprentissage de représentations.

Cependant, la littérature existante se concentre principalement sur des espaces euclidiens non contraints. De nombreuses applications modernes, telles que les plongements hiérarchiques (espace hyperbolique), l'optimisation de trajectoires (groupes orthogonaux spéciaux $SO(3)$) ou l'apprentissage de matrices de projection (variété de Stiefel), opèrent naturellement sur des variétés riemanniennes ($M$). De plus, les solutions de ces problèmes sont souvent contraintes à des ensembles non convexes euclidiens mais géodésiquement convexes sur la variété.

Le problème central abordé est donc :
$$\min_{x \in X \subseteq M} f(x)$$
où $M$ est une variété riemannienne de dimension $d$, $X$ est un sous-ensemble, et l'accès à $f$ se fait uniquement via un oracle de comparaison $Q_f(x, y)$ qui retourne $1$ si $f(x) > f(y)$ et $-1$ sinon.

2. Méthodologie Proposée

Les auteurs proposent deux algorithmes principaux adaptés au cadre riemannien, en surmontant les défis liés à la courbure de la variété et à l'absence de gradients.

A. Riemannian Dueling Normalized Gradient Descent (RDNGD)

C'est la première méthode de descente de gradient normalisée pour l'optimisation par duel sur les variétés.

• Estimateur de Gradient : L'algorithme utilise une perturbation aléatoire sur la variété. Pour un point $x_k$ et un vecteur unitaire aléatoire $u$ dans l'espace tangent $T_{x_k}M$, l'estimateur est défini par :
  $$h_\nu(x_k) = Q_f(\text{Exp}_{x_k}(\nu u), \text{Exp}_{x_k}(-\nu u)) \cdot u$$
  où $\text{Exp}$ est l'application exponentielle et $\nu$ est le rayon de perturbation.
• Mise à jour : La mise à jour suit une géodésique dans la direction opposée à l'estimateur, suivie d'une projection sur l'ensemble contraint $X$ (si nécessaire) :
  $$x_{k+1} = P_X(\text{Exp}_{x_k}(-\eta_k h_\nu(x_k)))$$
• Gestion de la Courbure : Les auteurs établissent des bornes théoriques reliant cet estimateur biaisé au gradient normalisé, en tenant compte de la courbure sectionnelle de la variété (via des constantes dépendant de la courbure $\kappa$).
• Variantes :
  • RDNGD : Pour des fonctions $L$-lisses (géodésiquement) et convexes ou non.
  • RRDNGD (Recurrent) : Une version itérative par phases pour les fonctions fortement convexes, permettant une convergence linéaire en réduisant progressivement le sous-optimalité cible.

B. Riemannian Dueling Frank-Wolfe (RDFW)

Cette méthode est conçue pour les cas où la projection $P_X$ est trop coûteuse ou impossible à calculer.

• Approche sans projection : Au lieu de projeter, l'algorithme utilise un Oracle de Minimisation Linéaire (LMO). À chaque itération, il résout un sous-problème linéaire sur la variété :
  $$z_k = \arg\min_{z \in X} \langle \bar{h}_k, \text{Log}_{x_k}(z) \rangle$$
  où $\bar{h}_k$ est un estimateur de gradient moyen (batch) pour réduire le bruit.
• Mise à jour : Le point suivant est obtenu en se déplaçant le long de la géodésique reliant $x_k$ à $z_k$.
• Avantage : Évite les projections explicites tout en garantissant la faisabilité, ce qui est crucial pour des contraintes complexes comme les intervalles géodésiques sur les matrices définies positives.

3. Contributions Clés

1. Cadre Théorique Unifié : Première étude de l'optimisation par duel sur des variétés riemanniennes, couvrant des cas non contraints et contraints.
2. Complexité d'Itération et d'Oracle :
   • Pour RDNGD (non convexe) : Complexité $O(d \epsilon^{-2})$.
   • Pour RDNGD (convexe) : Complexité $O(d \epsilon^{-1})$.
   • Pour RRDNGD (fortement convexe) : Convergence linéaire avec complexité $O(d \log(1/\epsilon))$.
   • Pour RDFW (convexe, sans projection) : Complexité d'oracle $O(d \epsilon^{-2})$.
   • Note : Ces résultats améliorent les constantes et la dépendance dimensionnelle par rapport aux travaux euclidiens existants (ex: Saha et al., 2021).
3. Amélioration de l'Estimation de Gradient : Les auteurs prouvent que leur estimateur a une constante universelle $\hat{C}$ plus favorable ($\approx 1/\sqrt{2\pi}$) que les bornes précédentes, réduisant l'erreur d'estimation de la direction du gradient.
4. Analyse de la Sensibilité : Une analyse détaillée montre que les méthodes de type Frank-Wolfe sont plus sensibles au bruit des estimateurs de gradient que les méthodes de projection, justifiant l'utilisation de lots (batches) dans RDFW.

4. Résultats Expérimentaux

Les auteurs valident leurs algorithmes sur des données synthétiques et des applications réelles :

• Problèmes Synthétiques :
  • Maximisation du rapport de Rayleigh : RDNGD atteint des performances comparables à la descente de gradient d'ordre zéro (ZO-RGD) qui nécessite les valeurs de fonction, bien que RDNGD n'utilise que des comparaisons.
  • Moyenne de Karcher : Calcul de la moyenne géométrique de matrices définies positives. RDNGD converge efficacement.
  • Moyenne de Karcher Contrainte : RDFW résout le problème avec des contraintes d'intervalles géodésiques, un cas où la projection est coûteuse.
• Applications Réelles :
  • Attaque par Boîte Noire sur les DNN : Attaque d'un réseau VGG sur CIFAR-10. RDNGD génère des exemples adversariaux avec une efficacité de requête supérieure (10 échantillons vs 500 pour ZO-RGD) et une convergence plus rapide en temps CPU.
  • Nivellement de l'Horizon : Correction de l'orientation d'images via l'optimisation sur $SO(2)$. L'algorithme converge vers une solution précise en très peu d'itérations sans accès aux valeurs de perte.

5. Signification et Impact

Ce travail comble un vide majeur entre l'optimisation basée sur les préférences (dueling) et l'optimisation riemannienne. Il démontre que l'optimisation peut être menée de manière fiable sur des variétés complexes en utilisant uniquement des comparaisons binaires, ce qui est essentiel pour les applications où les valeurs de perte sont inaccessibles, non fiables ou subjectives.

Les résultats théoriques offrent des garanties de convergence robustes en tenant compte de la géométrie intrinsèque (courbure), et les résultats empiriques prouvent l'efficacité pratique, notamment dans des scénarios de haute dimension et de contraintes complexes où les méthodes existantes échouent ou sont trop coûteuses. Cela ouvre la voie à de nouvelles recherches sur les algorithmes accélérés et les méthodes Hessian-aware dans le contexte de l'optimisation par duel sur les variétés.