Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

Resumen Técnico: Optimización Riemanniana Online Descentralizada Más Allá de las Variedades de Hadamard

Formulación del Problema
Este artículo aborda el problema de la optimización riemanniana online descentralizada sobre variedades que pueden poseer curvatura positiva, extendiéndose más allá del restrictivo entorno de las variedades de Hadamard (que tienen curvatura no positiva). El objetivo es que una red de $n$ agentes minimice colaborativamente una función objetivo global $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ en cada paso de tiempo $t$, donde cada agente $i$ solo observa su función de pérdida local $f_{i,t}$. Los agentes operan bajo dos regímenes de retroalimentación:

1. Retroalimentación de Gradiente Completo: Los agentes tienen acceso al gradiente riemanniano exacto de sus funciones locales.
2. Retroalimentación de Bandidos de Dos Puntos: Los agentes solo reciben evaluaciones de la función en dos puntos cercanos, lo que requiere la construcción de estimadores de gradiente.

Las variables de decisión y el punto comparador $x^*$ están restringidos a un subconjunto geodesicamente convexo $\mathcal{X}$ de una variedad riemanniana $\mathcal{M}$. Los principales desafíos técnicos surgen de la falta de convexidad global en espacios de curvatura positiva y de la no linealidad de la variedad, lo que complica los pasos de consenso estándar utilizados en la optimización descentralizada euclídea.

Metodología
Los autores proponen un marco unificado que se basa en tres componentes metodológicos centrales:

1. Paso de Consenso Consciente de la Curvatura:
   El artículo utiliza una regla de actualización de consenso específica definida en el espacio 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)$$
   donde $y_{i,t+1}$ es el resultado de la actualización del gradiente local y la proyección, $W$ es una matriz de comunicación doblemente estocástica, y $s$ es el tamaño de paso de consenso. A diferencia de trabajos previos que dependen de la linealidad de un espacio ambiente o de la convexidad global de las variedades de Hadamard, este trabajo analiza la reducción de la varianza lineal de este paso en variedades generales con curvatura seccional acotada $K \in [K_{\min}, K_{\max}]$. El análisis optimiza el tamaño de paso $s$ para equilibrar la compensación entre las propiedades de convexidad y suavidad distorsionadas por la curvatura.

2. Algoritmo de Información Completa (Algoritmo 1):
   En el entorno de gradiente completo, los agentes realizan un paso de descenso de gradiente riemanniano seguido de una proyección sobre el conjunto factible $\mathcal{X}$, y luego ejecutan el paso de consenso descrito anteriormente. El análisis de regret se descompone en un error de red (discrepancia entre las variables locales y la media de Fréchet global) y un error de optimización local. El error de red se acota utilizando la propiedad de reducción de varianza lineal establecida en el análisis de consenso.

3. Algoritmo de Retroalimentación de Bandidos (Algoritmo 2) y Suavizado:
   Para el entorno de bandidos de dos puntos, los autores emplean una técnica de suavizado aleatorizado. Los agentes muestrean direcciones uniformemente de la esfera del espacio tangente y evalúan la función en dos puntos separados por un parámetro de suavizado $\delta$. Esto genera un estimador de gradiente $g^\delta_{i,t}$.

   • Análisis de Subconvexidad: Dado que el suavizado destruye la convexidad estricta, los autores establecen que la función objetivo suavizada es $\delta$-geodesicamente subconvexa. Demuestran que la desviación de la convexidad perfecta está controlada linealmente por $\delta$.
   • Reducción del Dominio: Para asegurar la factibilidad al evaluar puntos cerca del límite, el algoritmo opera en un subconjunto decreciente $(1-\tau)\mathcal{X}$ del dominio original.

Contribuciones Clave
El artículo realiza las siguientes contribuciones técnicas específicas:

• Reducción de la Varianza Lineal en Variedades Generales: Los autores establecen la convergencia lineal del paso de consenso para variedades con curvaturas tanto positivas como negativas (Teorema III.2). Esto se logra optimizando el tamaño de paso de consenso para gestionar la compensación entre la convexidad y la suavidad, un desafío que no está presente en el entorno de Hadamard donde la curvatura negativa refuerza naturalmente la convexidad.
• Regret $O(\sqrt{T})$ para Información Completa: Para variedades generales (potencialmente de curvatura positiva), el artículo demuestra un límite de regret estático de $O(\sqrt{T})$ para el algoritmo de descenso de gradiente descentralizado (Teorema IV.2). Esto coincide con la tasa óptima conocida en entornos euclídeos, demostrando que la descentralización y la curvatura positiva no degradan asintóticamente la tasa de regret.
• Primer $O(\sqrt{T})$ Regret para Retroalimentación de Bandidos: El artículo proporciona el primer límite de regret estático de $O(\sqrt{T})$ para la optimización riemanniana online descentralizada bajo retroalimentación de bandidos de dos puntos (Teorema V.2). Esto se logra mediante un estimador de gradiente computacionalmente eficiente y un análisis riguroso de la subconvexidad de los objetivos suavizados.
• Herramientas Geométricas Generalizadas: Los autores desarrollan y extienden desigualdades de comparación geométrica (Lemas VII.3–VII.4) válidas para variedades con límites de curvatura de signos arbitrarios, proporcionando constantes definidas explícitamente en términos de $K_{\min}$ y $K_{\max}$.

Resultados

• Límites Teóricos: Los límites de regret estático derivados son $O(\sqrt{T})$ tanto para el entorno de gradiente completo como para el de retroalimentación de bandidos de dos puntos. Las constantes en estos límites dependen de la curvatura de la variedad, la conectividad de la red (a través del segundo valor singular más grande de $W$) y el diámetro del dominio, pero la tasa asintótica con respecto al horizonte de tiempo $T$ permanece óptima.
• Experimentos Numéricos: Se realizaron experimentos en una esfera unitaria de 16 dimensiones (una variedad de curvatura positiva) con 50 agentes. Los resultados confirman que los algoritmos convergen, con el regret acumulado aumentando según lo esperado. Los experimentos muestran que tamaños de paso de consenso más grandes generalmente conducen a un menor regret debido a tasas de consenso más rápidas, y que el entorno de bandidos exhibe una convergencia más lenta que el entorno de información completa debido a la varianza de la estimación del gradiente.

Significancia
El artículo afirma su importancia al cerrar una brecha crítica en la comprensión teórica de la optimización descentralizada en espacios curvos.

• Más Allá de Hadamard: Las garantías teóricas previas para la optimización riemanniana descentralizada estaban mayormente restringidas a las variedades de Hadamard. Este trabajo extiende estas garantías a variedades con curvatura positiva, donde las distancias geodésicas no inducen estructuras globalmente convexas.
• Entorno de Bandidos: Aborda el área previamente inexplorada de la optimización riemanniana online descentralizada bajo retroalimentación de bandidos, proporcionando los primeros límites de regret sublineal para este entorno.
• Optimalidad: Los resultados demuestran que la tasa de regret fundamental $O(\sqrt{T})$ alcanzable en la optimización online descentralizada euclídea se preserva incluso en presencia de curvatura positiva y retroalimentación limitada, siempre que se empleen técnicas de consenso y suavizado conscientes de la curvatura.

Los autores señalan que, si bien los límites son óptimos en términos de $T$, el trabajo futuro podría investigar la dependencia específica de estos límites respecto a los parámetros de conectividad de red y curvatura, y diseñar algoritmos que sean demostrablemente óptimos con respecto a esos parámetros específicos.