Power Homotopy for Zeroth-Order Non-Convex Optimizations

Resumo Técnico: Homotopia de Potência para Otimizações Não Convexas de Ordem Zero

Definição do Problema
O artigo aborda o desafio da otimização de ordem zero (ZO) para problemas não convexos, onde a função objetivo $f: \mathbb{R}^d \to \mathbb{R}$ deve ser maximizada sem o acesso aos seus gradientes. Embora métodos existentes como o GS-PowerOpt utilizem o suavizamento Gaussiano transformado por potência para localizar ótimos globais, eles dependem de um raio de suavizamento $\sigma$ fixo. Os autores identificam uma limitação fundamental neste design de $\sigma$ fixo: um compromisso inerente entre exploração global e refinamento local. Um $\sigma$ grande facilita a exploração global e acelera a otimização do substituto (surrogate), mas distorce a localização do maximizador do substituto; inversamente, um $\sigma$ pequeno preserva a geometria local, mas gera sinais de gradiente fracos quando a iterante está longe de regiões de alto valor.

Metodologia: GS-PowerHP
Para resolver esse compromisso, os autores propõem o GS-PowerHP (Homotopia Gaussiana com Transformação de Potência), um algoritmo de ordem zero de ciclo único que integra a transformação de potência com um cronograma fundamentado de decaimento do raio de suavizamento.

1. Transformação da Objetivo: O método visa a objetivo substituta:
   $$F_{N,\sigma}(\mu) := \mathbb{E}_{x \sim \mathcal{N}(\mu, \sigma^2 I_d)}[e^{N f(x)}]$$
   onde $N$ é um parâmetro de potência e $\sigma$ é o raio de suavizamento.
2. Cronograma de Decaimento: Ao contrário do GS-PowerOpt, que utiliza um $\sigma$ fixo, o GS-PowerHP atualiza o raio de suavizamento em cada iteração $t$ de acordo com:
   $$\sigma_{t+1} = \sigma_0 \beta^{t+1} + b$$
   onde $\beta \in (0, 1)$ é um fator de decaimento e $b > 0$ é um limite inferior.
3. Regra de Atualização: O algoritmo realiza um passo de ascensão de gradiente estocástico:
   $$\mu_{t+1} = \mu_t + \alpha_t \hat{\nabla} F_{N,\sigma_{t+1}}(\mu_t)$$
   O estimador de gradiente é computado usando $K$ amostras extraídas de $\mathcal{N}(\mu_t, \sigma_{t+1}^2 I_d)$.
4. Mecanismo: A estratégia começa com um $\sigma$ maior para manter sinais de gradiente informativos durante a exploração global (quando $\mu_t$ está longe do ótimo) e diminui gradualmente $\sigma$ para melhorar o refinamento local à medida que a iterante se aproxima do maximizador.

Principais Contribuições

1. Insight Teórico: Os autores fornecem uma análise formal identificando o compromisso entre exploração e refinamento inerente ao mecanismo de $\sigma$ fixo do GS-PowerOpt. Eles demonstram que a complexidade de iteração escala inversamente com $\sigma^2$ (favorecendo $\sigma$ maior), enquanto o alinhamento entre o maximizador do substituto e o verdadeiro maximizador global melhora conforme $\sigma \to 0$ (favorecendo $\sigma$ menor).
2. Inovação Algorítmica: O GS-PowerHP é o primeiro método de ordem zero que combina explicitamente a transformação de potência com um mecanismo incremental de decaimento de $\sigma$.
3. Garantias de Convergência: O artigo estabelece resultados de convergência teórica (Corolários 1 e 3). Prova-se que, sob suposições brandas, o GS-PowerHP converge em expectativa para uma vizinhança arbitrariamente pequena do maximizador global. A taxa de convergência de tempo finito para estacionariedade de primeira ordem é mostrada como $O((d^2 \epsilon^{-1} b^{-2})^{\frac{2}{1-2\gamma}})$, validando que o cronograma de decaimento permite um progresso inicial mais rápido enquanto garante a precisão local no limite.
4. Superioridade Empírica: Experimentos extensivos demonstram que o GS-PowerHP supera consistentemente os baselines de $\sigma$ fixo (incluindo o GS-PowerOpt) e outros métodos de suavizamento de ordem zero (como ZOSGD, ZO-AdaMM e ZOSLGH).

Resultados Experimentais
Os autores avaliaram o GS-PowerHP em:

• Funções de Benchmark: Maximização das funções Ackley e Rastrigin em $d=100$ dimensões. O GS-PowerHP alcançou os valores de aptidão (fitness) mais altos entre os métodos de suavizamento e exigiu menos iterações para convergir em comparação ao GS-PowerOpt.
• Ataques Adversários (Black-Box): O método foi testado em ataques direcionados de "menor probabilidade" (least-likely targeted attacks) contra classificadores para MNIST, CIFAR-10 e ImageNet.
  • No ImageNet ($d=150.528$), o GS-PowerHP alcançou uma taxa de sucesso de 78%, uma melhoria substancial sobre o GS-PowerOpt (47%) e ZOSLGHd (67%), mantendo tamanhos de perturbação e similaridade de imagem comparáveis.
  • No MNIST e CIFAR-10, alcançou taxas de sucesso de 100% com normas de perturbação menores do que os algoritmos de suavizamento concorrentes.
• Estudos de Ablação: Experimentos em objetivos sintéticos e ataques direcionados confirmaram que o mecanismo de decaimento de $\sigma$ é o principal motor dos ganhos de desempenho, permitindo que o algoritmo equilibre exploração e refinamento de forma mais eficaz do que as variantes de $\sigma$ fixo.

Significância e Alegações
O artigo afirma que o GS-PowerHP representa um avanço significativo na otimização não convexa de ordem zero ao tratar o raio de suavizamento como um recurso computacional adaptável em vez de um hiperparametro estático. Os autores sustentam que esta abordagem resolve a tensão estrutural entre exploração e precisão encontrada em métodos anteriores de suavizamento por potência.

A significância do trabalho é destacada pelo seu desempenho robusto em configurações de altíssima dimensão (ex: ataques ao ImageNet), onde supera métodos de suavizamento existentes e oferece uma alternativa computacionalmente mais leve a métodos de adaptação de covariância como o CMA-ES (que requer a manutenção de uma matriz de covariância completa). Os autores concluem que a combinação da transformação de potência com o decaimento do tipo homotopia fornece tanto fortes garantias de convergência teórica quanto resultados empíricos superiores para tarefas desafiadoras de otimização black-box.