Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

Résumé Technique : Optimisation Riemannienne en Ligne Décentralisée au-delà des Variétés de Hadamard

Formulation du Problème
Cet article traite du problème de l'optimisation riemannienne en ligne décentralisée sur des variétés qui peuvent posséder une courbure positive, étendant ainsi le cadre restrictif des variétés de Hadamard (qui ont une courbure non positive). L'objectif est qu'un réseau de $n$ agents minimise de manière collaborative une fonction objectif globale $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ à chaque étape $t$, où chaque agent $i$ n'observe que sa fonction de perte locale $f_{i,t}$. Les agents opèrent sous deux régimes de rétroaction :

1. Rétroaction par Gradient Complet : Les agents ont accès au gradient riemannien exact de leurs fonctions locales.
2. Rétroaction Bandit à Deux Points : Les agents ne reçoivent que des évaluations de la fonction en deux points proches, nécessitant la construction d'estimateurs de gradient.

Les variables de décision et le point de comparaison $x^*$ sont contraints dans un sous-ensemble géodésiquement convexe $\mathcal{X}$ d'une variété riemannienne $\mathcal{M}$. Les principaux défis techniques découlent de l'absence de convexité globale dans les espaces à courbure positive et de la non-linéarité de la variété, ce qui complique les étapes de consensus standard utilisées dans l'optimisation décentralisée euclidienne.

Méthodologie
Les auteurs proposent un cadre unifié qui repose sur trois composantes méthodologiques centrales :

1. Étape de Consensus Sensible à la Courbure :
   L'article utilise une règle de mise à jour de consensus spécifique définie dans l'espace tangent :
   $$x_{i,t+1} = \text{Exp}_{y_{i,t+1}}\left(s \sum_{j=1}^n w_{ij} \text{Log}_{y_{i,t+1}}(y_{j,t+1})\right)$$
   où $y_{i,t+1}$ est le résultat de la mise à jour du gradient local et de la projection, $W$ est une matrice de communication doublement stochastique, et $s$ est le pas de consensus. Contrairement aux travaux précédents qui reposent sur la linéarité d'un espace ambiant ou la convexité globale des variétés de Hadamard, ce travail analyse la réduction de la variance linéaire de cette étape sur des variétés générales avec une courbure sectionnelle bornée $K \in [K_{\min}, K_{\max}]$. L'analyse optimise le pas de consensus $s$ pour équilibrer le compromis entre les propriétés de convexité et de lissage déformées par la courbure.

2. Algorithme à Information Complète (Algorithme 1) :
   Dans le cadre du gradient complet, les agents effectuent une étape de descente de gradient riemannien suivie d'une projection sur l'ensemble réalisable $\mathcal{X}$, puis exécutent l'étape de consensus décrite ci-dessus. L'analyse du regret décompose l'erreur totale en une erreur de réseau (discrépance entre les variables locales et la moyenne de Fréchet globale) et une erreur d'optimisation locale. L'erreur de réseau est bornée en utilisant la propriété de réduction de variance linéaire établie dans l'analyse du consensus.

3. Algorithme de Rétroaction Bandit (Algorithme 2) et Lissage :
   Pour le cadre bandit à deux points, les auteurs emploient une technique de lissage randomisé. Les agents échantillonnent des directions uniformément dans la sphère de l'espace tangent et évaluent la fonction en deux points séparés par un paramètre de lissage $\delta$. Cela génère un estimateur de gradient $g^\delta_{i,t}$.

   • Analyse de la Subconvexité : Puisque le lissage détruit la convexité géodésique stricte, les auteurs établissent que l'objectif lissé est $\delta$-géodésiquement subconvexe. Ils prouvent que l'écart par rapport à une convexité parfaite est contrôlé linéairement par $\delta$.
   • Réduction de Domaine : Pour garantir la faisabilité lors de l'évaluation de points proches de la frontière, l'algorithme opère sur un sous-ensemble $(1-\tau)\mathcal{X}$ du domaine d'origine.

Contributions Clés
L'article apporte les contributions techniques spécifiques suivantes :

• Réduction de la Variance Linéaire sur des Variétés Générales : Les auteurs établissent la convergence linéaire de l'étape de consensus pour des variétés ayant des courbures tant positives que négatives (Théorème III.2). Ceci est réalisé en optimisant le pas de consensus pour gérer le compromis entre convexité et lissage, un défi qui n'est pas présent dans le cadre de Hadamard où la courbure négative renforce naturellement la convexité.
• Regret en $O(\sqrt{T})$ pour l'Information Complète : Pour les variétés générales (potentiellement à courbure positive), l'article prouve une borne de regret statique de $O(\sqrt{T})$ pour l'algorithme de descente de gradient décentralisé (Théorème IV.2). Cela correspond au taux optimal connu dans les contextes euclidiens, démontrant que la décentralisation et la courbure positive ne dégradent pas asymptotiquement le taux de regret.
• Premier Regret en $O(\sqrt{T})$ pour la Rétroaction Bandit : L'article fournit la première borne de regret statique de $O(\sqrt{T})$ pour l'optimisation riemannienne en ligne décentralisée sous rétroaction bandit à deux points (Théorème V.2). Ceci est obtenu grâce à un estimateur de gradient efficace sur le plan computationnel et une analyse rigoureuse de la subconvexité des objectifs lissés.
• Outils Géométriques Généralisés : Les auteurs développent et étendent des inégalités de comparaison géométrique (Lemmes VII.3–VII.4) valables pour des variétés avec des bornes de courbure de signes arbitraires, en fournissant des constantes explicitement définies en termes de $K_{\min}$ et $K_{\max}$.

Résultats

• Bornes Théoriques : Les bornes de regret statique dérivées sont de $O(\sqrt{T})$ pour les réglages de rétroaction à gradient complet et à deux points. Les constantes dans ces bornes dépendent de la courbure de la variété, de la connectivité du réseau (via la deuxième plus grande valeur singulière de $W$) et du diamètre du domaine, mais le taux asymptotique par rapport à l'horizon temporel $T$ reste optimal.
• Expériences Numériques : Des expériences ont été menées sur une sphère unité de dimension 16 (une variété à courbure positive) avec 50 agents. Les résultats confirment que les algorithmes convergent, le regret cumulé augmentant comme prévu. Les expériences montrent que des pas de consensus plus grands mènent généralement à un regret plus faible en raison de taux de consensus plus rapides, et que le réglage bandit présente une convergence plus lente que le réglage à information complète en raison de la variance de l'estimation du gradient.

Signification
L'article affirme son importance en comblant une lacune critique dans la compréhension théorique de l'optimisation décentralisée sur les espaces courbes.

• Au-delà de Hadamard : Les garanties théoriques antérieures pour l'optimisation riemannienne décentralisée étaient largement restreintes aux variétés de Hadamard. Ce travail étend ces garanties aux variétés possédant une courbure positive, où les distances géodésiques n'induisent pas de structures globalement convexes.
• Cadre Bandit : Il traite le domaine jusqu'alors inexploré de l'optimisation riemannienne en ligne décentralisée sous rétroaction bandit, fournissant les premières bornes de regret sous-linéaires pour ce cadre.
• Optimalité : Les résultats démontrent que le taux de regret fondamental de $O(\sqrt{T})$ atteignable dans l'optimisation en ligne décentralisée euclidienne est préservé même en présence de courbure positive et de rétroaction limitée, à condition d'employer des techniques de consensus et de lissage sensibles à la courbure.

Les auteurs notent que bien que les bornes soient optimales en termes de $T$, des travaux futurs pourraient investiguer la dépendance spécifique de ces bornes vis-à-vis des paramètres de connectivité de réseau et de courbure, et concevoir des algorithmes prouvés optimaux par rapport à ces paramètres spécifiques.