Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

Technische Samenvatting: Gedecentraliseerde Online Riemanniaanse Optimalisatie voorbij Hadamard-variëteiten

Probleemformulering
Dit artikel behandelt het probleem van gedecentraliseerde online Riemanniaanse optimalisatie over variëteiten die mogelijk een positieve kromming bezitten, waarmee de beperkende setting van Hadamard-variëteiten (die een niet-positieve kromming hebben) wordt uitgebreid. Het doel is dat een netwerk van $n$ agenten bij elke tijdstap $t$ gezamenlijk een globale objectieve functie $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ minimaliseert, waarbij elke agent $i$ alleen zijn lokale verliesfunctie $f_{i,t}$ waarneemt. De agenten opereren onder twee feedbackregimes:

1. Full Gradient Feedback: Agenten hebben toegang tot de exacte Riemanniaanse gradiënt van hun lokale functies.
2. Two-Point Bandit Feedback: Agenten ontvangen alleen functiewaarden op twee nabijgelegen punten, wat de constructie van gradiëntschatters vereist.

De beslissingsvariabelen en het comparatorpunt $x^*$ zijn beperkt tot een geodetisch convexe deelverzameling $\mathcal{X}$ van een Riemanniaanse variëteit $\mathcal{M}$. De primaire technische uitdagingen komen voort uit het gebrek aan globale convexiteit in positief gekromde ruimtes en de niet-lineariteit van de variëteit, wat de standaard consensusstappen die worden gebruikt in Euclidische gedecentraliseerde optimalisatie bemoeilijkt.

Methodologie
De auteurs stellen een verenigd kader voor dat steunt op drie kerncomponenten van de methodologie:

1. Krommingsbewuste Consensusstap:
   Het artikel maakt gebruik van een specifieke consensus-update regel gedefinieerd in de raakruimte:
   $$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)$$
   waarbij $y_{i,t+1}$ het resultaat is van de lokale gradiënt-update en projectie, $W$ een dubbel stochastische communicatiematrix is, en $s$ een consensus stapgrootte is. In tegenstelling tot eerdere werken die vertrouwen op de lineariteit van een omringende ruimte of de globale convexiteit van Hadamard-variëteiten, analyseert dit werk de lineaire variantiereductie van deze stap op algemene variëteiten met een begrensde sectieële kromming $K \in [K_{\min}, K_{\max}]$. De analyse optimaliseert de stapgrootte $s$ om de afweging tussen de door kromming verstoorde convexiteits- en gladheidseigenschappen te balanceren.

2. Full Information Algoritme (Algoritme 1):
   In de full gradient setting voert elke agent een Riemanniaanse gradiëntafdaling-stap uit, gevolgd door een projectie op de toelaatbare verzameling $\mathcal{X}$, en voert vervolgens de consensusstap uit zoals beschreven hierboven. De regret-analyse ontleedt de totale fout in een netwerkfout (het verschil tussen lokale variabelen en het globale Fréchet gemiddelde) en een lokale optimalisatiefout. De netwerkfout wordt begrensd met behulp van de lineaire variantiereductie-eigenschap die in de consensus-analyse is vastgesteld.

3. Bandit Feedback Algoritme (Algoritme 2) en Smoothing:
   Voor de two-point bandit setting maken de auteurs gebruik van een techniek van gerandomiseerde smoothing. Agenten samplen richtingen uniform uit de raakruimte-bol en evalueren de functie op twee punten die gescheiden zijn door een smoothing parameter $\delta$. Dit genereert een gradiëntschatter $g^\delta_{i,t}$.

   • Subconvexiteit Analyse: Omdat smoothing de strikte geodetische convexiteit vernietigt, stellen de auteurs vast dat de gesmoothte objectieve functie $\delta$-geodetisch subconvex is. Ze bewijzen dat de afwijking van perfecte convexiteit lineair wordt gecontroleerd door $\delta$.
   • Domein Inkrimping: Om haalbaarheid te garanderen bij het evalueren van punten nabij de grens, werkt het algoritme op een inkrimpend deelverzameling $(1-\tau)\mathcal{X}$ van het oorspronkelijke domein.

Belangrijkste Bijdragen
Het artikel levert de volgende specifieke technische bijdragen:

• Lineaire Variantiereductie op Algemene Variëteiten: De auteurs stellen de lineaire convergentie van de consensusstap vast voor variëteiten met zowel positieve als negatieve kromming (Theorem III.2). Dit wordt bereikt door de consensus stapgrootte te optimaliseren om de afweging tussen convexiteit en gladheid te beheren, een uitdaging die niet aanwezig is in de Hadamard-setting waar negatieve kromming de convexiteit van nature versterkt.
• $O(\sqrt{T})$ Regret voor Full Information: Voor algemene variëteiten (mogelijk positief gekromd), bewijst het artikel een statische regret-grens van $O(\sqrt{T})$ voor het gedecentraliseerde gradiëntafdaling-algoritme (Theorem IV.2). Dit komt overeen met de optimale snelheid die bekend is in Euclidische settings, wat aantoont dat decentralisatie en positieve kromming de regret-snelheid asymptotisch niet verslechteren.
• Eerste $O(\sqrt{T})$ Regret voor Bandit Feedback: Het artikel biedt de eerste statische regret-grens van $O(\sqrt{T})$ voor gedecentraliseerde online Riemanniaanse optimalisatie onder two-point bandit feedback (Theorem V.2). Dit wordt bereikt met behulp van een computationeel efficiënte gradiëntschatter en een rigoureuze analyse van de subconvexiteit van gesmoothde objectieve functies.
• Gegeneraliseerde Geometrische Hulpmiddelen: De auteurs ontwikkelen en breiden geometrische vergelijkingsongelijkheden uit (Lemmas VII.3–VII.4) die geldig zijn voor variëteiten met willekeurige tekens van krommingsgrenzen, waarbij de constanten expliciet worden gedefinieerd in termen van $K_{\min}$ en $K_{\max}$.

Resultaten

• Theoretische Grenzen: De afgeleide statische regret-grenzen zijn $O(\sqrt{T})$ voor zowel de full gradient als de two-point bandit feedback settings. De constanten in deze grenzen zijn afhankelijk van de kromming van de variëteit, de netwerkconnectiviteit (via de tweede grootste singuliere waarde van $W$) en de diameter van het domein, maar de asymptotische snelheid met betrekking tot de tijdshorizon $T$ blijft optimaal.
• Numerieke Experimenten: Experimenten werden uitgevoerd op een 16-dimensionale eenheidsbol (een positief gekromde variëteit) met 50 agenten. De resultaten bevestigen dat de algoritmen convergeren, waarbij de cumulatieve regret zoals verwacht toeneemt. De experimenten laten zien dat grotere consensus stapgroottes over het algemeen leiden tot een lagere regret vanwege snellere consensus-snelheden, en dat de bandit-setting een tragere convergentie vertoont dan de full-information setting vanwege de variantie in de gradiëntschatting.

Betekenis
Het artikel claimt betekenis door een kritieke kloof te overbruggen in het theoretische begrip van gedecentraliseerde optimalisatie op gekromde ruimtes.

• Voorbij Hadamard: Eerdere theoretische garanties voor gedecentraliseerde Riemanniaanse optimalisatie waren grotendeels beperkt tot Hadamard-variëteiten. Dit werk breidt deze garanties uit naar variëteiten met positieve kromming, waar geodetische afstanden geen globaal convexe structuren induceren.
• Bandit Setting: Het adresseert het voorheen onverkende gebied van gedecentraliseerde Riemanniaanse optimalisatie onder bandit feedback, en biedt de eerste sublineaire regret-grenzen voor deze setting.
• Optimaliteit: De resultaten tonen aan dat de fundamentele $O(\sqrt{T})$ regret-snelheid die haalbaar is in Euclidische gedecentraliseerde online optimalisatie behouden blijft, zelfs in de aanwezigheid van positieve kromming en beperkte feedback, mits krommingsbewuste consensus en smoothing technieken worden toegepast.

De auteurs merken op dat hoewel de grenzen optimaal zijn in termen van $T$, toekomstig werk de specifieke afhankelijkheid van deze grenzen van netwerkconnectiviteit en krommingsparameters kan onderzoeken, en algoritmen kan ontwerpen die bewezen optimaal zijn met betrekking tot die specifieke parameters.