Riemannian Dueling Optimization

Este trabalho propõe e analisa algoritmos de otimização de duelos em variedades Riemannianas, introduzindo os métodos RDNGD e RDFW para lidar com funções geodesicamente suaves ou convexas em cenários com e sem projeção, demonstrando sua eficácia através de experimentos numéricos.

O essencial

Imagine que você está tentando encontrar o ponto mais baixo de uma montanha misteriosa no escuro total. Você não pode ver a paisagem, não pode sentir a inclinação do chão com os pés e nem sabe a altura exata onde está. A única coisa que você pode fazer é fazer uma pergunta a um "oráculo" (uma espécie de guia mágico): "Entre dois pontos que eu escolher, qual deles é mais baixo?"

O guia só responde "O ponto A" ou "O ponto B". Ele não diz quanto mais baixo é, nem para onde você deve andar.

Isso é o que os pesquisadores chamam de Otimização de Duelo (Dueling Optimization). É como um jogo de "mais quente, mais frio", mas onde você só sabe quem ganhou a rodada, não a pontuação.

O Problema: O Mundo não é Plano

Até agora, a maioria dos cientistas que estudavam esse jogo assumia que a montanha era plana e reta (como um campo de futebol). Eles criaram regras para descer essa montanha plana usando apenas comparações.

Mas a realidade é mais complexa. Muitas vezes, o "terreno" onde estamos tentando encontrar a solução não é plano.

• Exemplo 1: Imagine tentar endireitar uma foto tirada torta. O "caminho" para corrigir a imagem não é uma linha reta, mas sim uma rotação em um círculo (uma esfera).
• Exemplo 2: Em inteligência artificial, os dados muitas vezes vivem em formas geométricas estranhas e curvas, chamadas Variedades Riemannianas. É como tentar andar em uma superfície de uma bola ou de um tubo, onde as regras da geometria plana (como "a soma dos ângulos de um triângulo é 180 graus") não funcionam mais.

Se você tentar usar as regras do "campo de futebol" (espaço euclidiano) para descer uma "montanha em forma de bola" (espaço Riemanniano), você vai se perder ou ficar girando em círculos.

A Solução: O Guia Riemanniano

A equipe deste paper criou dois novos métodos (algoritmos) para navegar nessas montanhas curvas usando apenas a comparação "qual é melhor?". Eles chamam isso de Otimização de Duelo Riemanniana.

Pense neles como dois tipos de exploradores:

1. O Explorador "Passo a Passo" (RDNGD)

Este método é como um alpinista que dá passos curtos e calculados.

• Como funciona: O alpinista escolhe dois pontos ao seu redor (um para a esquerda, um para a direita, mas seguindo a curva da montanha). Ele pergunta ao guia qual dos dois é mais baixo.
• O Truque: Em vez de andar em linha reta (o que o tiraria da montanha), ele usa um "mapa mágico" (chamado Exponencial) para projetar seu passo para a frente, mantendo-se sempre na superfície curva.
• Resultado: Ele consegue descer a montanha curva com segurança, mesmo sem saber a altura exata, apenas sabendo qual direção é "mais para baixo".

2. O Explorador "Sem Mapa de Projeção" (RDFW)

Às vezes, a montanha tem limites muito estritos (como uma caverna com paredes de vidro). O método anterior exigia que o alpinista, se desse um passo errado, fosse "jogado de volta" para dentro da caverna (um processo chamado projeção), o que pode ser muito difícil de calcular em terrenos complexos.

• A Solução: Este novo método é como um explorador que nunca sai da caverna. Em vez de dar um passo e corrigir depois, ele pede ao guia: "Olhe para todos os pontos possíveis dentro da caverna e me diga qual deles parece mais promissor em relação à minha direção atual".
• O Truque: Ele usa uma "bússola de comparação" para encontrar o melhor caminho dentro dos limites, sem precisar calcular a projeção difícil. É como deslizar por um tobogã em vez de escalar uma parede.

Por que isso é importante? (Analogias do Mundo Real)

1. Atacar Redes Neurais (Segurança): Imagine que você é um hacker tentando enganar uma IA que reconhece fotos. Você não pode ver o "código" da IA (o gradiente). Você só pode mostrar duas fotos alteradas e perguntar: "Qual delas a IA acha que é um gato, e não um cachorro?". O novo método permite criar essas fotos enganosas (ataques) de forma muito mais eficiente, mesmo em espaços complexos onde as imagens "vivem".
2. Endireitar Fotos (Visão Computacional): Se você tira uma foto de um horizonte torto, o algoritmo precisa encontrar a rotação perfeita para endireitá-la. O "espaço" das rotações é uma esfera. O novo método ajuda a encontrar a rotação perfeita apenas comparando "esta foto parece mais reta do que aquela?", sem precisar calcular a matemática complexa de "quanto" está torta.
3. Robótica: Um robô precisa planejar um movimento. Às vezes, o melhor caminho não é uma linha reta, mas uma curva no espaço 3D. Usar apenas comparações de "qual movimento é mais suave" permite que o robô aprenda a se mover em ambientes complexos.

Em Resumo

Este trabalho é como escrever um novo manual de instruções para quem precisa descer montanhas curvas no escuro, usando apenas a dica "qual lado é mais baixo?".

• Antes: Só sabíamos descer montanhas planas com essa técnica.
• Agora: Conseguimos descer montanhas curvas, esferas e formas complexas, o que abre portas para melhorar desde a segurança de carros autônomos até a qualidade das fotos que tiramos com o celular.

É uma prova de que, mesmo com informações limitadas (apenas comparações), podemos navegar em mundos geometricamente complexos de forma inteligente e eficiente.

Resumo técnico

Resumo Técnico: Otimização Dueling Riemanniana

1. O Problema

A Otimização Dueling (Dueling Optimization) refere-se a um cenário onde o objetivo é minimizar uma função $f(x)$, mas o acesso aos valores da função ou aos seus gradientes é impossível. A única informação disponível provém de um oráculo de comparação (ou "dueling oracle"), que, dado dois pontos $x$ e $y$, retorna apenas qual deles possui um valor de função menor (ou maior), sem revelar os valores numéricos.

Enquanto trabalhos anteriores focaram em espaços euclidianos, muitas aplicações modernas ocorrem em variedades Riemannianas (espaços não euclidianos com curvatura), como:

• Sistemas de recomendação: Usam embeddings em espaços hiperbólicos.
• Robótica: Otimização de trajetórias em grupos ortogonais especiais (ex: $SO(3)$).
• Aprendizado de Representação: Matrizes de projeção em variedades de Stiefel.
• Ataques a Redes Neurais: Restrições de perturbação em esferas de alta dimensão.

O problema central abordado é:
$$\min_{x \in X \subseteq \mathcal{M}} f(x)$$
onde $\mathcal{M}$ é uma variedade Riemanniana e o acesso é restrito ao oráculo $Q_f(x, y) = 2 \cdot \mathbb{1}(f(x) > f(y)) - 1$.

2. Metodologia Proposta

Os autores propõem três algoritmos principais para lidar com diferentes cenários de restrição e propriedades da função, estendendo a lógica de estimativa de gradiente baseada em comparação para o domínio Riemanniano.

A. RDNGD (Riemannian Dueling Normalized Gradient Descent)

• Objetivo: Resolver problemas não convexos (suaves) e convexos (geodésicamente convexos) com projeção permitida.
• Mecanismo: Utiliza uma estimativa de direção de gradiente baseada em perturbação aleatória em duas pontas.
  • Amostra uma direção aleatória $u$ na esfera unitária do espaço tangente $T_x\mathcal{M}$.
  • Consulta o oráculo comparando os pontos $Exp_x(\nu u)$ e $Exp_x(-\nu u)$.
  • O estimador é definido como $h_\nu(x) = Q_f(Exp_x(\nu u), Exp_x(-\nu u)) \cdot u$.
• Atualização: Move-se ao longo da geodésica na direção oposta ao estimador e projeta de volta no conjunto viável $X$ (se necessário).
• Inovação: A análise teórica lida com a curvatura da variedade, provando que o estimador é aproximadamente alinhado com o gradiente normalizado, superando a falta de informação de magnitude.

B. RRDNGD (Riemannian Recurrent Dueling Normalized Gradient Descent)

• Objetivo: Resolver problemas onde a função é fortemente convexa (geodésica).
• Mecanismo: Um algoritmo em fases que reduz iterativamente o sub-ótimo da função. Em cada fase, executa o RDNGD para atingir uma precisão específica, reduzindo o raio de busca para a próxima fase.
• Resultado: Convergência linear (taxa logarítmica em relação à precisão $\epsilon$).

C. RDFW (Riemannian Dueling Frank-Wolfe)

• Objetivo: Resolver problemas convexos onde a projeção é proibida ou computacionalmente proibitiva (ex: matrizes definidas positivas com restrições complexas).
• Mecanismo: Substitui a projeção por um Oráculo de Minimização Linear (LMO).
  • Resolve um subproblema linear no espaço tangente: $\min_{z \in X} \langle \bar{h}_k, Log_x(z) \rangle$.
  • Usa um estimador de gradiente em batch (média de múltiplas direções) para reduzir a variância, crucial pois o LMO é sensível a ruídos na direção.
• Atualização: Move-se ao longo da geodésica do ponto atual para o ponto ótimo do subproblema linear.

3. Principais Contribuições

1. Primeiro Framework Teórico: Estabelecem o primeiro framework teórico para otimização dueling em variedades Riemannianas, preenchendo a lacuna entre otimização baseada em preferências e otimização geométrica.
2. Complexidade de Iteração e Oráculo:
   • Para funções suaves e não convexas: Complexidade $O(d \epsilon^{-2})$.
   • Para funções convexas: Complexidade $O(d \epsilon^{-1})$.
   • Para funções fortemente convexas: Complexidade $O(d \log(1/\epsilon))$.
   • Para o método sem projeção (RDFW): Complexidade $O(d \epsilon^{-2})$ em consultas ao oráculo.
3. Melhorias sobre o Estado da Arte Euclidiano: Ao reduzir os resultados para o caso euclidiano, os autores demonstram constantes melhores e dependências de dimensão mais favoráveis (eliminando fatores logarítmicos presentes em trabalhos anteriores como Saha et al., 2021).
4. Análise de Sensibilidade: Demonstram que métodos do tipo Frank-Wolfe são mais sensíveis ao ruído da estimativa de gradiente do que métodos de projeção, justificando o uso de batches maiores no RDFW.

4. Resultados Experimentais

Os algoritmos foram testados em dados sintéticos e aplicações reais:

• Problemas Sintéticos:

  • Maximização do Quociente de Rayleigh: RDNGD alcançou desempenho comparável ao método de gradiente de ordem zero (ZO-RGD) que usa valores de função, apesar de usar apenas comparações.
  • Média de Karcher (Matrizes Definidas Positivas): Convergência bem-sucedida para a média geométrica de matrizes.
  • Karcher com Restrições: O RDFW foi capaz de resolver o problema de média de Karcher com restrições de intervalo (onde a projeção é difícil), algo inédito com oráculos de comparação.

• Aplicações Reais:

  • Ataque a Redes Neurais (DNN): Em um cenário de "caixa preta" (black-box) no CIFAR-10, o RDNGD gerou exemplos adversariais com perturbações imperceptíveis. O método foi mais eficiente em tempo de CPU e requereu menos consultas (10 amostras vs. 500 do ZO-RGD) para atingir alta perda adversarial, demonstrando superioridade em cenários de oráculo restrito.
  • Nivelamento de Horizonte (Horizon Leveling): Em tarefas de visão computacional para corrigir a inclinação de imagens (otimização em $SO(2)$), o algoritmo convergiu para soluções precisas ($\sim 10^{-5}$) em poucas iterações, sem acesso a valores de função ou gradientes explícitos.

5. Significado e Impacto

Este trabalho é fundamental porque:

• Unifica Domínios: Conecta a otimização baseada em preferências (comum em aprendizado por reforço e sistemas de recomendação) com a otimização em variedades (essencial para geometria de dados e robótica).
• Viabilidade Prática: Demonstra que é possível otimizar em espaços complexos e restritos sem precisar de valores de função ou gradientes, o que é crucial em cenários onde o feedback humano é a única fonte de informação (ex: "qual imagem parece mais nivelada?").
• Robustez Geométrica: Fornece garantias teóricas que consideram a curvatura intrínseca do espaço, evitando erros de aproximação que ocorreriam ao tratar variedades como espaços euclidianos planos.

Em suma, o artigo oferece ferramentas teóricas e práticas robustas para otimização quando a informação é limitada a comparações binárias em espaços geométricos não triviais.