Inversion-Free Natural Gradient Descent on Riemannian Manifolds

1. O Problema

O artigo aborda a otimização de funções objetivo definidas sobre famílias de distribuições de probabilidade paramétricas, onde os parâmetros residem em um espaço de Riemannian (uma variedade diferenciável) em vez de um espaço euclidiano padrão.

• Contexto: Métodos de otimização estatística, como Estimativa de Máxima Verossimilhança (MLE) e Inferência Variacional Bayesiana (VI), frequentemente envolvem parâmetros com restrições geométricas intrínsecas (ex: matrizes simétricas positivas definidas - SPD, matrizes com colunas ortonormais em variedades de Stiefel, ou distribuições gaussianas no espaço de Bures-Wasserstein).
• Desafios:
  • Geometria: Ignorar a estrutura geométrica do espaço de parâmetros pode levar a violações de restrições (ex: perda de positividade definida) ou a otimização ineficiente devido a escalas de parâmetros desalinhadas.
  • Custo Computacional: O método do Gradiente Natural (Natural Gradient Descent - NGD) é conhecido por sua eficiência, pois utiliza a Informação de Fisher (FIM) para pré-condicionar o gradiente. No entanto, o NGD padrão requer a inversão da FIM a cada iteração, o que tem complexidade cúbica ($O(d^3)$) e é proibitivo para dimensões altas.
  • Limitações de Trabalhos Anteriores: A maioria dos métodos existentes de NGD em variedades ou assume espaços euclidianos ou requer um espaço de imersão (embedding) que pode introduzir singularidades ou não capturar a geometria intrínseca corretamente.

2. Metodologia

Os autores propõem um método de Gradiente Natural Estocástico Livre de Inversão (Inversion-Free) adaptado para variedades de Riemannian. A abordagem combina a estimação online da inversa da FIM com operações geométricas intrínsecas.

• Formulação Intrínseca: A FIM é definida como uma forma bilinear no espaço tangente da variedade. O gradiente natural é o gradiente Riemanniano em relação à métrica de Fisher-Rao.
• Aproximação Online da Inversa da FIM:
  • Em vez de calcular e inverter a FIM explicitamente, o algoritmo mantém uma aproximação móvel da inversa da FIM ($H_s^{-1}$).
  • Utiliza-se a identidade de inversão de Sherman-Morrison para atualizar $H_s^{-1}$ incrementalmente com vetores de pontuação (score vectors) amostrados em cada iteração. Isso reduz a complexidade de atualização para quadrática ($O(d^2)$).
• Operações Geométricas (Transporte Vetorial):
  • Um desafio central em variedades é que os vetores de pontuação e a aproximação da FIM residem em espaços tangentes diferentes ($T_{\theta(s)}M$ e $T_{\theta(s-1)}M$).
  • O método emprega transporte vetorial (uma generalização do transporte paralelo) para mover a aproximação da inversa da FIM de um espaço tangente para outro antes da atualização.
  • O algoritmo segue três passos repetidos: (1) Transportar a aproximação da inversa; (2) Atualizar com novos vetores de pontuação; (3) Atualizar o parâmetro na variedade usando uma retração (retraction).
• Variante de Memória Limitada: Para problemas de alta dimensão, propõe-se uma variante que mantém apenas as $K$ mais recentes vetores de pontuação (janela deslizante), reduzindo a complexidade de armazenamento de quadrática para sub-quadrática.

3. Principais Contribuições

1. Método Intrínseco Livre de Inversão: Desenvolvimento de um algoritmo de gradiente natural estocástico que não requer um espaço de imersão euclidiano e evita a inversão matricial explícita, operando puramente na estrutura intrínseca da variedade.
2. Análise de Convergência Rigorosa:
   • Prova de taxas de convergência quase certas (almost-sure) para a distância quadrática ao minimizador local de $O(\log s / s^\alpha)$, onde $\alpha > 2/3$ é o expoente da taxa de aprendizado.
   • Estabelecimento de taxas de convergência para a aproximação da FIM, levando em conta os erros acumulados devido ao transporte vetorial e à curvatura da variedade (holonomia).
3. Generalização para Variedades Gerais: Diferente de trabalhos anteriores focados em subvariedades embutidas, este método aplica-se a variedades gerais, incluindo casos onde a FIM pode ser singular no espaço ambiente, mas é bem-comportada na variedade.
4. Validação Empírica: Demonstração da eficácia do método em dois cenários distintos:
   • Inferência Variacional Gaussiana: Utilizando a variedade de Bures-Wasserstein (BW), onde a divergência KL é geodésicamente convexa.
   • Fluxos Normalizantes (Normalizing Flows): Utilizando a variedade de Stiefel para impor restrições de ortogonalidade nas matrizes de peso.

4. Resultados

• Desempenho em Inferência Variacional (Gaussianas):
  • Em datasets como Ionosphere, Breast Cancer e Sonar, o método NGD aproximado (Inversion-Free) no espaço de Bures-Wasserstein (BW-NGD) superou tanto o Gradiente Descendente Riemanniano padrão quanto o NGD aproximado em parametrização euclidiana.
  • Em datasets maiores (Adult, Mushrooms), a versão euclidiana aproximada tornou-se instável e divergiu sem taxas de aprendizado extremamente pequenas, enquanto a versão BW-NGD manteve-se estável e convergiu para valores de ELBO (Evidence Lower Bound) comparáveis aos métodos exatos.
• Desempenho em Fluxos Normalizantes (Stiefel):
  • Na tarefa de classificação binária com redes neurais bayesianas usando fluxos de Sylvester (com restrições de ortogonalidade), o método NGD Riemanniano alcançou a menor bound negativa (melhor ajuste) em todos os datasets testados (German Credit, Woman Labor Force, Census), superando métodos de gradiente estocástico Riemanniano e métodos de gradiente natural extrínsecos.
• Estabilidade: A abordagem baseada em variedades (especialmente BW) demonstrou maior robustez e estabilidade numérica em comparação com abordagens euclidianas, permitindo o uso de taxas de aprendizado maiores.

5. Significado e Impacto

Este trabalho preenche uma lacuna importante entre a teoria de otimização em variedades e a prática de aprendizado de máquina estocástico.

• Viabilidade Computacional: Ao eliminar a necessidade de inversão matricial explícita, torna o Gradiente Natural viável para problemas de alta dimensão em geometrias complexas.
• Garantias Teóricas: As taxas de convergência provadas fornecem fundamentos teóricos sólidos para o uso de métodos de gradiente natural em contextos estocásticos não-euclidianos, algo que era escasso na literatura.
• Aplicabilidade Prática: A demonstração de que a geometria correta (como Bures-Wasserstein para covariâncias) melhora a estabilidade e a convergência em comparação com parametrizações euclidianas reforça a importância da geometria diferencial em modelos probabilísticos modernos.
• Futuro: O artigo sugere que essa metodologia pode ser estendida para espaços de medidas de probabilidade de dimensão infinita (espaço de Wasserstein), abrindo caminho para algoritmos baseados em partículas em otimização não paramétrica.

Em resumo, o artigo propõe uma solução eficiente, teoricamente fundamentada e empiricamente robusta para otimização estocástica em espaços de parâmetros com restrições geométricas complexas, superando as limitações de custo computacional e instabilidade dos métodos existentes.