Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

Resumo Técnico: Descida de Espelho de Ordem Zero Determinística via Campos Vetoriais com Certificação A Posteriori

1. Definição do Problema
O artigo aborda o desafio de realizar otimização determinística de ordem zero (livre de derivadas) em dimensões moderadas, especificamente para objetivos onde os gradientes não estão disponíveis, são proibitivamente caros ou numericamente instáveis de computar (por exemplo, funções de matriz envolvendo log-determinantes ou entropia relativa quântica). O Descida de Espelho (Mirror Descent - MD) padrão oferece uma otimização sensível à geometria via divergências de Bregman, mas tradicionalmente depende de gradientes exatos. Métodos de otimização livre de derivadas (DFO) determinísticos existentes (ex: busca direta, modelos de região de confiança) operam tipicamente em geometria euclidiana e focam em medidas de estacionalidade em vez de garantias de valor de função da última iteração. Por outro modo, métodos de ordem zero aleatórios fornecem limites baseados em expectativa, mas carecem da reprodutibilidade e da certificação por execução (run-wise) exigidas para aplicações críticas de segurança ou auditáveis. O problema central é desenvolver um framework de ordem zero determinístico que preserve a geometria de Bregman, utilize apenas valores de função e forneça garantias explícitas e verificáveis de convergência da última iteração.

2. Metodologia
Os autores propõem um framework generalizado de Descida de Espelho impulsionada por $\Omega$ ($\Omega$-driven Mirror Descent). Em vez de usar o gradiente $\nabla f(x)$, o algoritmo emprega um campo vetorial geral $\Omega(x)$ construído deterministicamente a partir de valores de função.

• Regra de Atualização Generalizada: A atualização mapeia a iteração primal $x_j$ para o espaço dual via $\theta_j = \nabla \Phi(x_j)$, realiza um passo $\theta_{j+1} = \theta_j - \eta_j \Omega(x_j)$ e mapeia de volta para o espaço primal $x_{j+1} = (\nabla \Phi)^{-1}(\theta_{j+1})$.
• Certificação A Posteriori: A análise baseia-se em uma condição de suavidade relativa ao longo da trajetória (Equação 2.5): $\eta_j D_{f,\Omega}(x_{j+1} \| x_j) \leq D_\Phi(x_{j+1} \| x_j)$. Diferente das suposições globais, esta condição é verificada ao longo das iterações realizadas. Se satisfeita, ela produz garantias explícitas da última iteração.
• Estrela-Convexidade Generalizada de Vizinhança Perfurada: Para lidar com o erro de aproximação inerente aos oráculos de ordem zero, o artigo introduz uma condição de estrela-convexidade relaxada. Requer que $\langle \Omega(x), x - x^* \rangle \geq f(x) - f(x^*)$ ocorra apenas fora de uma pequena vizinhança $U$ do minimizador $x^*$. Isso isola um "piso de erro" explícito determinado pela resolução do oráculo de ordem zero.
• Instanciação Determinística: O framework é instanciado usando diferenças finitas centrais determinísticas em dimensões moderadas. O campo vetorial $\Omega(x)$ é construído usando $2d$ avaliações fora do centro (mais um valor central reutilizável).
• Dominância Cônica Robusta: Uma contribuição técnica fundamental é a prova de que o campo vetorial de diferença finita satisfaz a condição de estrela-convexidade necessária fora de um conjunto específico $V_{\epsilon, c}$. Isso é alcançado formulando o problema como um design de dominância cônica robusta, garantindo que uma única direção de proxy escalonada domine todas as direções verdadeiras admissíveis sobre um cone circular de incerteza.

3. Principais Contribuições

• Framework Unificado: O artigo estabelece um modelo geral de descida de espelho impulsionada por $\Omega$ que engloba vários algoritmos de informação-geométrica (incluindo atualizações generalizadas de Blahut–Arimoto) e esquemas determinísticos de diferença finita.
• Certificação por Trajetória: Fornece um mecanismo para certificados verificáveis por execução. Se a desigualdade de suavidade relativa for satisfeita ao longo de uma trajetória específica, o algoritmo garante um limite de valor de função da última iteração, independente de suposições de suavidade global.
• Análise de Piso de Erro Explícito: Para diferenças finitas determinísticas, os autores derivam um limite de convergência do tipo "taxa-mais-piso". O erro decai como $O(1/t)$ fora de uma vizinhança dependente da resolução, sendo o piso de erro explicitamente caracterizado pelo tamanho do passo da diferença finita $\epsilon$ e pelo número de condição do problema.
• Conexão Geométrica: O trabalho revela uma estrutura geométrica oculta que liga identidades de telescópio de Bregman, certificação determinística e geometria cônica robusta (especificamente dualidade de cone cônico de segunda ordem) no contexto de otimização de ordem zero.

4. Principais Resultados

• Teoremas 2.1 & 2.3: Sob a condição de suavidade relativa ao longo da trajetória e estrela-convexidade generalizada de vizinhança perfurada, o algoritmo garante:
  $$f(x_t) - f(x^*) \leq \max \left( \frac{D_\Phi(x^* \| x_1)}{\sum_{j=1}^{t-1} \eta_j}, \max_{x \in U} (f(x) - f(x^*)) \right)$$
  Este limite separa a taxa de convergência (impulsionada pela divergência de Bregman e tamanhos de passo) do erro de aproximação (impulsionado pela vizinhança $U$).
• Teoremas 6.4 & Corolário 6.6: Quando instanciado com diferenças finitas centrais determinísticas, mostra-se que o conjunto excepcional $V_{\epsilon, c}$ está contido dentro de uma bola euclidiana de raio proporcional a $\epsilon\sqrt{d}$. Isso resulta em um limite concreto onde o piso de erro é determinado pela variação do objetivo dentro desta vizinhança $\epsilon$.
• Viabilidade (Teorema 5.1): O artigo prova que, para tamanhos de passo suficientemente pequenos, a condição de suavidade relativa ao longo da trajetória é sempre viável, justificando o uso de busca de linha baseada em certificados.

5. Significância e Alegações
O artigo afirma preencher uma lacuna entre a otimização de ordem zero determinística e a descida de espelho sensível à geometria. Sua principal significância reside em:

1. Determinismo e Verificabilidade: Fornecer um framework adequado para aplicações que exigem reprodutibilidade e auditabilidade (ex: computação científica, design crítico de segurança), onde métodos estocásticos são insuficientes.
2. Flexibilidade Geométrica: Estender os benefícios da geometria de Bregman (crucial para problemas com restrições de simplex, entropia ou definição positiva) para configurações onde os gradientes não estão disponíveis.
3. Insight Teórico: Demonstrar que, para a descida de espelho de ordem zero, a suposição estrutural crítica para garantias da última iteração não é a convexidade clássica per se, mas uma condição de estrela-convexidade generalizada de vizinhança perfurada. Esta condição acomoda naturalmente os limites de resolução das aproximações de diferença finita.
4. Mudança Metodológica: Mover o foco de suposições globais para certificados a posteriori, ao longo da trajetória, permitindo que praticantes verifiquem garantias de convergência baseadas nos dados reais da execução, em vez de limites teóricos de pior caso.

Os autores posicionam este trabalho como um complemento às tradições de DFO existentes, oferecendo uma interface específica onde a geometria de Bregman é preservada, e fornecendo o primeiro certificado de estilo descida de espelho, verificável por trajetória, para valores de função da última iteração sob oráculos de apenas valores de função.