Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

Sintesi Tecnica: Ottimizzazione Riemanniana Online Decentralizzata Oltre le Manifold di Hadamard

Formulazione del Problema
Questo articolo affronta il problema dell'ottimizzazione Riemanniana online decentralizzata su varietà che possono possedere una curvatura positiva, estendendosi oltre l'impostazione restrittiva delle manifold di Hadamard (che hanno curvatura non positiva). L'obiettivo è far sì che una rete di $n$ agenti minimizzi collaborativamente una funzione obiettivo globale $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ ad ogni passo temporale $t$, dove ogni agente $i$ osserva solo la propria funzione di perdita locale $f_{i,t}$. Gli agenti operano sotto due regimi di feedback:

1. Feedback del Gradiente Completo: Gli agenti hanno accesso al gradiente Riemanniano esatto delle loro funzioni locali.
2. Feedback Bandit a Due Punti: Gli agenti ricevono solo valutazioni della funzione in due punti vicini, richiedendo la costruzione di stimatori del gradiente.

Le variabili decisionali e il punto di confronto $x^*$ sono vincolati a un sottoinsieme geodesicamente convesso $\mathcal{X}$ di una varietà Riemanniana $\mathcal{M}$. Le principali sfide tecniche derivano dalla mancanza di convessità globale negli spazi a curvatura positiva e dalla non linearità della varietà, che complica i classici passi di consenso utilizzati nell'ottimizzazione decentralizzata euclidea.

Metodologia
Gli autori propongono un framework unificato che si basa su tre componenti metodologiche fondamentali:

1. Passo di Consenso Sensibile alla Curvatura (Curvature-Aware Consensus Step):
   Il paper utilizza una specifica regola di aggiornamento del consenso definita nello spazio tangente:
   $$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)$$
   dove $y_{i,t+1}$ è il risultato dell'aggiornamento del gradiente locale e della proiezione, $W$ è una matrice di comunicazione a doppia stocasticità, e $s$ è il passo di consenso. A differenza dei lavori precedenti che si affidano alla linearità di uno spazio ambiente o alla convessità globale delle manifold di Hadamard, questo lavoro analizza la riduzione della varianza lineare di questo passo su varietà generali con curvatura sezionale limitata $K \in [K_{\min}, K_{\max}]$. L'analisi ottimizza il passo di consenso $s$ per bilanciare il compromesso tra le proprietà di convessità e di regolarità (smoothness) distorte dalla curvatura.

2. Algoritmo a Informazione Completa (Algoritmo 1):
   Nel setting del gradiente completo, gli agenti eseguono un passo di discesa del gradiente Riemanniano seguito da una proiezione sull'insieme ammissibile $\mathcal{X}$, e successivamente eseguono il passo di consenso descritto sopra. L'analisi del regret decompone l'errore totale in un errore di rete (discrepanza tra le variabili locali e la media di Fréchet globale) e un errore di ottimizzazione locale. L'errore di rete viene limitato utilizzando la proprietà di riduzione della varianza lineare stabilita nell'analisi del consenso.

3. Algoritmo di Feedback Bandit (Algoritmo 2) e Smoothing:
   Per il setting bandit a due punti, gli autori impiegano una tecnica di smoothing randomizzato. Gli agenti campionano direzioni uniformemente dalla sfera dello spazio tangente e valutano la funzione in due punti separati da un parametro di smoothing $\delta$. Questo genera uno stimatore del gradiente $g^\delta_{i,t}$.

   • Analisi della Subconvessità: Poiché lo smoothing distrugge la convessità geodesica stretta, gli autori stabiliscono che l'obiettivo smussato è $\delta$-geodesicamente subconvesso. Dimostrano che la deviazione dalla perfetta convessità è controllata linearmente da $\delta$.
   • Restrizione del Dominio (Domain Shrinkage): Per garantire la fattibilità durante la valutazione di punti vicino al bordo, l'algoritmo opera su un sottoinsieme restringente $(1-\tau)\mathcal{X}$ del dominio originale.

Contributi Chiave
Il paper apporta i seguenti contributi tecnici specifici:

• Riduzione della Varianza Lineare su Varietà Generali: Gli autori stabiliscono la convergenza lineare del passo di consenso per varietà con sia curvatura positiva che negativa (Teorema III.2). Ciò viene ottenuto ottimizzando il passo di consenso per gestire il compromesso tra convessità e regolarità, una sfida non presente nel setting di Hadamard dove la curvatura negativa rinforza naturalmente la convessità.
• Regret $O(\sqrt{T})$ per l'Informazione Completa: Per le varietà generali (potenzialmente a curvatura positiva), il paper dimostra un limite di regret statico di $O(\sqrt{T})$ per l'algoritmo di discesa del gradiente decentralizzato (Teorema IV.2). Questo eguaglia il tasso ottimale noto nei setting euclidei, dimostrando che la decentralizzazione e la curvatura positiva non degradano asintoticamente il tasso di regret.
• Primo $O(\sqrt{T})$ Regret per il Feedback Bandit: Il paper fornisce il primo limite di regret statico di $O(\sqrt{T})$ per l'ottimizzazione Riemanniana online decentralizzata sotto feedback bandit a due punti (Teorema V.2). Ciò è reso possibile attraverso uno stimatore del gradiente computazionalmente efficiente e un'analisi rigorosa della subconvessità degli obiettivi smussati.
• Strumenti Geometrici Generalizzati: Gli autori sviluppano ed estendono le disuguaglianze di confronto geometrico (Lemmi VII.3–VII.4) valide per varietà con segni arbitrari di limiti di curvatura, fornendo costanti definite esplicitamente in termini di $K_{\min}$ e $K_{\max}$.

Risultati

• Limiti Teorici: I limiti di regret statico derivati sono $O(\sqrt{T})$ sia per il setting del gradiente completo che per quello del feedback bandit a due punti. Le costanti in questi limiti dipendono dalla curvatura della varietà, dalla connettività della rete (tramite il secondo valore singolare di $W$) e dal diametro del dominio, ma il tasso asintotico rispetto all'orizzonte temporale $T$ rimane ottimale.
• Esperimenti Numerici: Sono stati condotti esperimenti su una sfera unitaria a 16 dimensioni (una varietà a curvatura positiva) con 50 agenti. I risultati confermano che gli algoritmi convergono, con il regret cumulativo che aumenta come previsto. Gli esperimenti mostrano che passi di consenso più grandi portano generalmente a un regret inferiore grazie a tassi di consenso più rapidi, e che il setting bandit presenta una convergenza più lenta rispetto al setting a informazione completa a causa della varianza della stima del gradiente.

Significatività
Il paper rivendica la sua significatività nel colmare un vuoto critico nella comprensione teorica dell'ottimizzazione decentralizzata su spazi curvi.

• Oltre Hadamard: Le precedenti garanzie teoriche per l'ottimizzazione Riemanniana decentralizzata erano ampiamente limitate alle manifold di Hadamard. Questo lavoro estende tali garanzie alle varietà con curvatura positiva, dove le distanze geodesiche non inducono strutture globalmente convesse.
• Setting Bandit: Affronta l'area precedentemente inesplorata dell'ottimizzazione Riemanniana online decentralizzata sotto feedback bandit, fornendo i primi limiti di regret sublineari per questo setting.
• Ottimalità: I risultati dimostrano che il fondamentale tasso di regret $O(\sqrt{T})$ ottenibile nell'ottimizzazione online decentralizzata euclidea è preservato anche in presenza di curvatura positiva e feedback limitato, a condizione che vengano impiegate tecniche di smoothing e di consenso sensibili alla curvatura.

Gli autori osservano che, sebbene i limiti siano ottimali in termini di $T$, il lavoro futuro potrebbe investigare la specifica dipendenza di questi limiti dalla connettività della rete e dai parametri di curvatura, e progettare algoritmi provabilmente ottimali rispetto a tali specifici parametri.