Resumo Técnico: Descida de Coordenadas Coerente para Otimização de Ordem Zero Leve

Declaração do Problema

A otimização de Ordem Zero (ZO) é essencial para cenários onde a retropropagação está indisponível ou é computacionalmente proibitiva, como aprendizado em dispositivos com restrições de memória, ataques adversariais de caixa preta e aprendizado por reforço baseado em simulação. No entanto, os métodos ZO existentes enfrentam um trade-off fundamental entre eficiência de amostragem e variância:

• Diferenças Finitas (FD) Padrão: Fornecem estimativas de gradiente de baixa variância, mas são ineficientes em amostragem, exigindo $O(d)$ avaliações de função por passo para $d$ parâmetros.
• Métodos Randomizados (ex.: Estratégias Evolutivas, SPSA, Subespaço Aleatório): Reduzem os custos de consulta por passo, mas introduzem alta variância, frequentemente necessitando de taxas de aprendizado pequenas ou tamanhos de lote grandes que prejudicam a convergência em tempo real.

As abordagens atuais frequentemente dependem de descartar gradientes "desatualizados" (computados em iterações anteriores) como atrasos prejudiciais e assumem que os tamanhos de passo de diferenças finitas ($\epsilon$) devem ser minimizados para aproximar com precisão os gradientes verdadeiros. Este artigo desafia essas suposições.

Metodologia: Descida de Coordenadas Coerente (CoCD)

Os autores propõem a Descida de Coordenadas Coerente (CoCD), um otimizador ZO determinístico, eficiente em amostragem e consciente do orçamento. A CoCD opera com base em duas ideias centrais:

1. Coerência Temporal: As trajetórias de otimização exibem continuidade; os gradientes evoluem suavemente ao longo do tempo, limitados pela suavidade Lipschitz da função. Portanto, gradientes desatualizados não são meramente ruído, mas podem servir como aproximações gratuitas da geometria atual ("inicializações quentes").
2. Suavização Implícita da Paisagem: Contra-intuitivamente, tamanhos de passo de diferenças finitas maiores ($\epsilon$) podem melhorar a estabilidade da convergência ao suavizar implicitamente a paisagem de otimização, reduzindo a constante de suavidade efetiva ($L_\epsilon$).

Estrutura Algorítmica

A CoCD utiliza um buffer Primeiro a Entrar, Primeiro a Sair (FIFO) para manter uma estimativa global de gradiente $\hat{g} \in \mathbb{R}^n$.

• Atualizações Cíclicas: O algoritmo percorre as coordenadas ciclicamente. Em cada passo, ele realiza $B$ consultas de função (orçamento de computação) para atualizar coordenadas específicas usando estimativas frescas de diferenças finitas.
• Momento e Decaimento: Um fator global de decaimento de momento $\gamma \in [0, 1]$ é aplicado a todo o buffer antes das atualizações.
  • $\gamma = 1.0$: Preserva todos os gradientes históricos até serem ciclicamente atualizados (memória perfeita).
  • $\gamma = 0.0$: Limpa o buffer em cada passo, recuperando a Descida de Coordenadas Cíclica em Blocos (BCCD) padrão.
  • $0 < \gamma < 1$: Fornece uma "memória que desvanece", suprimindo exponencialmente gradientes muito antigos enquanto retém a história recente.
• Regra de Atualização: A direção de atualização é formada pela estimativa híbrida de gradiente $\hat{g}_t$, escalada pela taxa de aprendizado $\alpha$: $x_{t+1} = x_t - \alpha \cdot \hat{g}_t$.
• Implementação Eficiente: Para lidar com tensores estruturados (ex.: kernels de CNN) sem sobrecarga proibitiva de cópia de memória, a CoCD emprega um mecanismo de achatamento virtualizado usando um buffer de tensor 1D contíguo e operações no local, mantendo uma pegada de memória estrita de uma cópia do modelo.

Contribuições Teóricas

O artigo fornece fundamentação teórica rigorosa para a CoCD:

1. Equivalência à BCCD com Inicializações Quentes: Os autores provam que a CoCD é matematicamente equivalente à Descida de Coordenadas Cíclica em Blocos (BCCD) equipada com inicializações quentes de gradientes desatualizados. Isso permite uma análise formal de convergência.
2. Limites de Erro de Aproximação: O artigo deriva limites de erro mostrando que o erro de aproximação depende do produto da constante de suavidade efetiva ($L_\epsilon$) e do tamanho do passo ($\delta$). Crucialmente, demonstra que um $\epsilon$ maior reduz $L_\epsilon$, suavizando efetivamente a paisagem e permitindo tamanhos de passo maiores e históricos de gradiente mais longos sem sacrificar a estabilidade.
3. Garantias de Convergência: Sob a condição Polyak-Łojasiewicz (PŁ) e suposições leves, a CoCD alcança convergência linear comparável a métodos de primeira ordem, mesmo operando com estimativas de gradientes desatualizados. A análise mostra que, no caso de orçamento total ($B=n$), a CoCD recupera a taxa de convergência padrão da descida de gradiente.
4. Análise de Estabilidade: A análise teórica revela que o momento ($\gamma$) suprime exponencialmente o peso dos gradientes mais antigos, estabilizando a descida em paisagens não convexas.

Resultados Empíricos

Experimentos foram conduzidos em arquiteturas MLP, CNN e ResNet (até 270 mil parâmetros) em tarefas de regressão (SARCOS) e classificação (MNIST, CIFAR-10).

• Desempenho vs. BCCD: A CoCD supera significativamente a BCCD padrão ($\gamma=0$) tanto em eficiência de amostragem quanto em precisão final.
  • No CIFAR-10, a BCCD falhou em escapar do regime de palpite aleatório (10,13% de precisão), enquanto a CoCD alcançou 45,08% de precisão.
  • No SARCOS, a CoCD reduziu a perda final de 188,73 (BCCD) para 31,18.
• Estabilidade vs. Métodos Randomizados: Comparada a bases ZO randomizadas como SPSA e ZO-SGD, a CoCD exibiu estabilidade superior. Enquanto métodos randomizados divergiram na tarefa de regressão SARCOS, a CoCD estabilizou.
• Eficiência: A CoCD demonstrou velocidade superior em tempo real, executando aproximadamente 2x mais rápido que o ZO-SGD (8,1s vs. 15,7s por episódio) ao evitar a sobrecarga de amostragem gaussiana densa.
• Sensibilidade a Hiperparâmetros:
  • Raio de Suavização ($\epsilon$): Valores maiores de $\epsilon$ (ex.: $\epsilon=1.0$) melhoraram a estabilidade e o desempenho, validando a hipótese de suavização implícita.
  • Momento ($\gamma$): Valores mais altos de $\gamma$ consistentemente aceleraram a convergência e foram essenciais para a coerência em configurações de alta dimensão.

Significado e Alegações

O artigo alega que atualizações determinísticas e conscientes da estrutura oferecem uma alternativa superior à randomização para otimização ZO leve. Ao reenquadrar gradientes desatualizados como um ativo computacional em vez de um passivo, a CoCD preenche a lacuna entre eficiência heurística e rigor teórico.

As principais alegações incluem:

• Eficiência de Recursos: A CoCD alcança baixa complexidade de consultas ($O(1)$ por passo) sem a alta variância inerente a estimadores randomizados, tornando-a adequada para dispositivos de borda com restrições de memória.
• Insight Teórico: O trabalho fornece uma justificativa teórica contra-intuitiva para o uso de tamanhos de passo de diferenças finitas maiores para induzir suavização implícita, melhorando a convergência em paisagens não convexas.
• Impacto Prático: O método oferece um caminho viável para treinar modelos em dispositivos ou em cenários de caixa preta onde gradientes são inacessíveis, superando os métodos ZO existentes mais avançados em estabilidade e velocidade de convergência.

Os autores observam que a CoCD é atualmente mais eficaz para modelos de pequena a média escala e que trabalhos futuros focarão em estratégias de escalabilidade (ex.: paralelização por blocos) para sistemas maiores.