Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

Resumo Técnico: Otimização Riemanniana Online Descentralizada Além de Variedades de Hadamard

Formulação do Problema
Este artigo aborda o problema da otimização riemanniana online descentralizada sobre variedades que podem possuir curvatura positiva, estendendo-se além do cenário restritivo das variedades de Hadamard (que possuem curvatura não positiva). O objetivo é que uma rede de $n$ agentes minimize colaborativamente uma função objetivo global $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ em cada passo de tempo $t$, onde cada agente $i$ observa apenas sua função de perda local $f_{i,t}$. Os agentes operam sob dois regimes de feedback:

1. Feedback de Gradiente Completo: Os agentes têm acesso ao gradiente riemanniano exato de suas funções locais.
2. Feedback Bandit de Dois Pontos: Os agentes recebem apenas avaliações da função em dois pontos próximos, exigindo a construção de estimadores de gradiente.

As variáveis de decisão e o ponto comparador $x^*$ estão restritos a um subconjunto geodesicamente convexo $\mathcal{X}$ de uma variedade riemanniana $\mathcal{M}$. Os principais desafios técnicos decorrem da falta de convexidade global em espaços de curvatura positiva e da não linearidade da variedade, o que complica os passos de consenso padrão utilizados na otimização descentralizada euclidiana.

Metodologia
Os autores propõem um framework unificado que se baseia em três componentes metodológicos principais:

1. Passo de Consenso Consciente da Curvatura:
   O artigo utiliza uma regra de atualização de consenso específica definida no espaço 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)$$
   onde $y_{i,t+1}$ é o resultado da atualização de gradiente local e projeção, $W$ é uma matriz de comunicação duplamente estocástica, e $s$ é o tamanho do passo de consenso. Diferente de trabalhos anteriores que dependem da linearidade de um espaço ambiente ou da convexidade global de variedades de Hadamard, este trabalho analisa a redução de variância linear deste passo em variedades gerais com curvatura seccional limitada $K \in [K_{\min}, K_{\max}]$. A análise otimiza o tamanho do passo $s$ para equilibrar o compromisso entre as propriedades de convexidade e suavidade distorcidas pela curvatura.

2. Algoritmo de Informação Completa (Algoritmo 1):
   No cenário de gradiente completo, os agentes realizam um passo de descida de gradiente riemanniano seguido por uma projeção no conjunto viável $\mathcal{X}$ e, em seguida, executam o passo de consenso descrito acima. A análise de regret decompõe o erro total em um erro de rede (discrepância entre as variáveis locais e a média de Fréchet global) e um erro de otimização local. O erro de rede é limitado usando a propriedade de redução de variância linear estabelecida na análise de consenso.

3. Algoritmo de Feedback Bandit (Algoritmo 2) e Suavização:
   Para o cenário bandit de dois pontos, os autores empregam uma técnica de suavização aleatória. Os agentes amostram direções uniformemente da esfera do espaço tangente e avaliam a função em dois pontos separados por um parâmetro de suavização $\delta$. Isso gera um estimador de gradiente $g^\delta_{i,t}$.

   • Análise de Subconvexidade: Como a suavização destrói a convexidade estrita, os autores estabelecem que o objetivo suavizado é $\delta$-geodesicamente subconvexo. Eles provam que o desvio da convexidade perfeita é controlado linearmente por $\delta$.
   • Encolhimento do Domínio: Para garantir a viabilidade ao avaliar pontos próximos à fronteira, o algoritmo opera em um subconjunto $(1-\tau)\mathcal{X}$ do domínio original.

Principais Contribuições
O artigo apresenta as seguintes contribuições técnicas específicas:

• Redução de Variância Linear em Variedades Gerais: Os autores estabelecem a convergência linear do passo de consenso para variedades com curvaturas tanto positiva quanto negativa (Teorema III.2). Isso é alcançado otimizando o tamanho do passo de consenso para gerenciar o compromisso entre convexidade e suavidade, um desafio que não está presente no cenário de Hadamard, onde a curvatura negativa reforça naturalmente a convexidade.
• Regret $O(\sqrt{T})$ para Informação Completa: Para variedades gerais (potencialmente de curvatura positiva), o artigo prova um limite de regret estático de $O(\sqrt{T})$ para o algoritmo de descida de gradiente descentralizado (Teorema IV.2). Isso iguala a taxa ótima conhecida em configurações euclidianas, demonstrando que a descentralização e a curvatura positiva não degradam assintoticamente a taxa de regret.
• Primeiro $O(\sqrt{T})$ Regret para Feedback Bandit: O artigo fornece o primeiro limite de regret estático de $O(\sqrt{T})$ para otimização riemanniana online descentralizada sob feedback bandit de dois pontos (Teorema V.2). Isso é alcançado usando um estimador de gradiente computacionalmente eficiente e uma análise rigorosa da subconvexidade dos objetivos suavizados.
• Ferramentas Geométricas Generalizadas: Os autores desenvolvem e estendem desigualdades de comparação geométrica (Lemmas VII.3–VII.4) válidas para variedades com limites de curvatura de sinais arbitrários, fornecendo constantes definidas explicitamente em termos de $K_{\min}$ e $K_{\max}$.

Resultos

• Limites Teóricos: Os limites de regret estático derivados são $O(\sqrt{T})$ para ambos os cenários de feedback de gradiente completo e de dois pontos bandit. As constantes nesses limites dependem da curvatura da variedade, da conectividade da rede (via segundo maior valor singular de $W$) e do diâmetro do domínio, mas a taxa assintótica em relação ao horizonte de tempo $T$ permanece ótima.
• Experimentos Numéricos: Experimentos foram conduzidos em uma esfera unitária de 16 dimensões (uma variedade de curvatura positiva) com 50 agentes. Os resultados confirmam que os algoritmos convergem, com o regret cumulativo aumentando conforme o esperado. Os experimentos mostram que tamanhos de passo de consenso maiores geralmente levam a um regret menor devido a taxas de consenso mais rápidas, e que o cenário bandit exibe uma convergência mais lenta do que o cenário de informação completa devido à variância da estimativa do gradiente.

Significância
O artigo afirma sua significância ao preencher uma lacuna crítica na compreensão teórica da otimização descentralizada em espaços curvos.

• Além de Hadamard: Garantias teóricas anteriores para otimização riemanniana descentralizada estavam amplamente restritas a variedades de Hadamard. Este trabalho estende essas garantias para variedades com curvatura positiva, onde as distâncias geodésicas não induzem estruturas globalmente convexas.
• Cenário Bandit: Ele aborda a área anteriormente inexplorada da otimização riemanniana descentralizada sob feedback bandit, fornecendo os primeiros limites de regret sublineares para este cenário.
• Otimalidade: Os resultados demonstram que a taxa fundamental de regret $O(\sqrt{T})$ alcançável na otimização online descentralizada euclidiana é preservada mesmo na presença de curvatura positiva e feedback limitado, desde que técnicas de consenso e suavização conscientes da curvatura sejam empregadas.

Os autores observam que, embora os limites sejam ótimos em termos de $T$, trabalhos futuros poderiam investigar a dependência específica desses limites em relação aos parâmetros de conectividade de rede e curvatura, e projetar algoritmos provadamente ótimos em relação a esses parâmetros específicos.