Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

1. Formulação do Problema

O artigo aborda a otimização da norma do operador generalizado e do quociente de Rayleigh generalizado extremo sob restrições de ordem zero (sem derivadas). Especificamente, o objetivo é resolver:
$$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$$
onde $A \in \mathbb{R}^{m \times d}$ e $B \in \mathbb{R}^{\ell \times d}$ são matrizes acessíveis apenas via avaliações diretas (acesso caixa-preta).

Principais Restrições e Desafios:

• Sem Adjoint/Sem Matriz: Os adjuntos $A^T$ e $B^T$ estão indisponíveis ou são inconsistentes com os operadores diretos (comum em códigos legados, solucionadores de EDP e tomografia).
• Bem-postura: $B$ deve ter posto coluna completo ($\text{rank}(B)=d$) para que $B^TB \succ 0$.
• Limitações dos Métodos Existentes: Métodos de ordem zero recentes de última geração (por exemplo, Bresch et al. [7–9]) dependem de amostragem no espaço tangente em uma esfera generalizada ($S^{d-1}_{B^TB}$). Isso requer conhecimento da métrica $B^TB$ ou de sua raiz quadrada para projetar direções de busca, o que é inviável em configurações estritas de caixa-preta.

2. Metodologia

O artigo propõe uma abordagem fundamentalmente diferente baseada em amostragem não restrita em toda a esfera unitária, em vez de espaços tangentes restritos.

A. Estratégia de Amostragem Não Restrita

Em vez de amostrar direções de busca $x_k$ a partir do espaço tangente da esfera generalizada (o que requer $B^TB$), o método amostra $x_k$ uniformemente a partir da esfera unitária padrão $S^{d-1}$:
$$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$$
Isso elimina a necessidade de projeções dependentes de métrica ou informações de adjunto.

B. Tamanho de Passo Ótimo via Solução de Forma Fechada

Para uma iteração atual $v_k$ e direção de busca $x_k$, o algoritmo busca um tamanho de passo ótimo $\tau_k$ para maximizar o objetivo ao longo do caminho de retração. A função objetivo ao longo do caminho torna-se um quociente de funções quadráticas:
$$s_k(\tau) = \frac{\|A(v_k + \tau x_k)\|^2}{\|B(v_k + \tau x_k)\|^2} = \frac{a_k + 2b_k\tau + c_k\tau^2}{d_k + 2e_k\tau + f_k\tau^2}$$
Os coeficientes ($a_k, \dots, f_k$) são computados usando apenas avaliações diretas de $A$ e $B$.

• Avanço Teórico: O artigo prova que encontrar o $\tau_k$ ótimo é equivalente a resolver um problema de autovalor generalizado 2D envolvendo matrizes de Gram $2 \times 2$, $M_k$ e $N_k$.
• Resultado: Uma solução de forma fechada para $\tau_k$ é derivada (Teorema 3.1), garantindo que o tamanho do passo seja ótimo para a direção aleatória específica, sem heurísticas de busca linear.

C. Framework de Otimização Riemanniana de Ordem Zero

O método constrói estimadores para quantidades de otimização Riemanniana usando apenas avaliações de função:

1. Estimador de Gradiente: Um estimador não tendencioso do gradiente Riemanniano é construído usando a direção aleatória $x_k$ e a lógica de tamanho de passo ótimo.
2. Estimador de Hessiana (Quase-Newton): O artigo deriva um estimador não tendencioso para a Hessiana Riemanniana (Corolário 3.3) usando momentos de quarta ordem da distribuição uniforme na esfera. Isso permite um Método Quase-Newton de Ordem Zero (Algoritmo 3).
3. Redução de Variância: Ao média $m$ amostras independentes (Algoritmo 2), a variância do estimador de gradiente é reduzida, acelerando a convergência.

3. Principais Contribuições

1. Amostragem Não Restrita em $S^{d-1}$:
   O artigo introduz um esquema de amostragem que opera na esfera unitária completa em vez do espaço tangente de uma esfera generalizada. Isso elimina a exigência de $B^TB$ ou seu adjunto, tornando o método aplicável a cenários estritos de caixa-preta onde métodos anteriores falhavam.

2. Tamanho de Passo Ótimo de Forma Fechada:
   Diferentemente de métodos padrão de ordem zero que usam tamanhos de passo fixos ou heurísticos, este trabalho deriva uma solução exata e de forma fechada para o tamanho de passo ótimo $\tau_k$ para o objetivo específico de quociente quadrático. Isso transforma o subproblema em um problema de autovalor generalizado 2D solucionável.

3. Estimação Não Tendenciosa da Hessiana:
   Os autores fornecem uma derivação principiante de um estimador não tendencioso para a Hessiana Riemanniana em um cenário sem derivadas. Isso permite a construção de um algoritmo de segunda ordem de ordem zero (Quase-Newton) que captura informações de curvatura sem derivadas explícitas.

4. Garantias Teóricas de Convergência:

   • Convergência Quase Certa: A sequência de iterações converge quase certamente para o autoespaço generalizado líder (Teorema 3.7).
   • Análise de Pontos Críticos: O artigo prova que a sequência de proxies de gradiente ($\alpha_k$) converge para zero quase certamente, garantindo que o algoritmo não fique preso em pontos críticos não ótimos (sob suposições espectrais leves).
   • Bem-Definição: É provado que o denominador no cálculo do tamanho de passo permanece não nulo quase certamente, garantindo que o algoritmo seja bem definido.

4. Resultados Numéricos

Experimentos foram conduzidos em matrizes gaussianas aleatórias sintéticas com dimensões de até $d=1000$.

• Desempenho vs. Estado da Arte:
  • Em baixas dimensões, o método proposto é comparável aos métodos recentes de amostragem em espaço tangente [9].
  • Em altas dimensões ($d \gg 10$), a amostragem em esfera não restrita supera significativamente os métodos de espaço tangente. Isso é atribuído ao espaço de busca maior e à evitação de operações de projeção caras (multiplicações matriz-matriz) exigidas pelos métodos de espaço tangente.
• Taxas de Convergência:
  • O método exibe convergência linear para o Erro de Quociente Relativo (RQE).
  • O resíduo quadrático mínimo (MSQR) para a equação de autovalor generalizada mostra uma taxa de convergência de $O(1/k)$, que é superior às taxas sublineares frequentemente observadas em métodos sem derivadas.
• Vantagem de Segunda Ordem:
  A variante Quase-Newton (Algoritmo 3) demonstra comportamento de convergência mais estrito e redução de erro mais rápida perto de pontos críticos em comparação com a variante de primeira ordem (Algoritmo 2), fechando efetivamente a lacuna de desempenho perto de ótimos.

5. Significado

Este trabalho representa um avanço significativo na otimização sem derivadas para problemas espectrais.

• Impacto Prático: Permite o cálculo de normas de operadores e quocientes de Rayleigh em cenários onde operadores adjuntos estão indisponíveis, inconsistentes ou são muito custosos para computar (por exemplo, códigos de simulação legados, solucionadores complexos de EDP).
• Impacto Teórico: Preenche a lacuna entre busca aleatória de ordem zero e otimização Riemanniana, fornecendo estimadores não tendenciosos tanto para gradientes quanto para Hessianas em variedades sem projeções de variedade explícitas.
• Eficiência Algorítmica: O tamanho de passo de forma fechada e a capacidade de operar sem projeções de espaço tangente tornam o algoritmo computacionalmente eficiente e escalável para problemas de alta dimensão.

Em resumo, Bresch generaliza métodos de ordem zero para lidar com quocientes de funções quadráticas substituindo a amostragem restrita de espaço tangente por amostragem de esfera não restrita, derivando tamanhos de passo exatos e estabelecendo um framework rigoroso de segunda ordem que supera as técnicas existentes de última geração em configurações de caixa-preta de alta dimensão.