Stochastic Zeroth-Order Method for Computing Generalized Rayleigh Quotients

Resumo Técnico: Método Estocástico de Ordem Zero para Computação de Quocientes de Rayleigh Generalizados

Enunciado do Problema
O artigo aborda a maximização do quociente de Rayleigh generalizado, definido como:
$$R(A, B) = \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\langle v, Av \rangle}{\langle v, Bv \rangle}$$
onde $A \in \mathbb{R}^{d \times d}$ e $B \in \text{Sym}^d_{\succ 0}$ (simétrica definida positiva). Este problema é fundamental na álgebra linear numérica, aparecendo em equivalência espectral, decomposições de valores singulares generalizados e análise de estabilidade de equações diferenciais parciais (via abscissa numérica).

Métodos convencionais para resolver este problema tipicamente dependem de produtos matriz-adjunto ($A^T$) e da computação explícita de $B^{-1}$. Os autores identificam duas limitações primárias nestas abordagens:

1. Custo Computacional e Estabilidade: Computar $B^{-1}$ ou realizar produtos matriz-vetor envolvendo-o é caro e propenso a imprecisões numéricas.
2. Desajuste de Adjunto (Adjoint Mismatch): Em aplicações como tomografia computadorizada, a transposta $A^T$ é frequentemente substituída por um operador aproximado e computacionalmente tratável. Este "desajuste de adjunto" leva a erros de reconstrução significativos, tornando métodos que exigem adjuntos exatos inadequados.

Metodologia
Os autores propõem um algoritmo riemanniano estocástico de ordem zero que opera diretamente na variedade $S^{d-1}_B = \{v \in \mathbb{R}^d : \langle v, Bv \rangle = 1\}$. O método evita computar $A^T$ ou $B^{-1}$ inteiramente, baseando-se apenas em produtos matriz-vetor com $A$ e $B$.

O algoritmo central (Algoritmo 1 para amostra única, Algoritmo 2 para múltiplas amostras) procede da seguinte forma:

1. Inicialização: Começa com um vetor aleatório $v_0$ na variedade.
2. Amostragem: Em cada iteração $k$, amostra uma direção aleatória $x_k$ do espaço tangente $T_{v_k} S^{d-1}_B$. Isto é alcançado projetando um vetor Gaussiano padrão no espaço tangente e normalizando-o.
3. Tamanho de Passo Ótimo: Em vez de usar um tamanho de passo fixo ou de retrocesso (backtracking), o algoritmo resolve analiticamente o problema de maximização unidimensional ao longo da direção amostrada:
   $$\tau_k = \arg\max_{\tau \in \mathbb{R}} r(A, B, v_k + \tau x_k)$$
   O Teorema 3.1 fornece uma solução de forma fechada para $\tau_k$ envolvendo apenas produtos internos de $v_k$ e $x_k$ com $A$ e $B$.
4. Atualização: O iterado é atualizado via o mapa de retração: $v_{k+1} = R_{v_k}(\tau_k x_k)$.

A variante de múltiplas amostras (Algoritmo 2) faz a média de múltiplas direções amostradas para reduzir a variância da estimativa do gradiente antes de computar o tamanho do passo.

Contribuições Teóricas
O artigo estabelece garantias de convergência rigorosas sob a condição de que a dimensão do subespaço próprio correspondente ao autovalor máximo, $\dim(G_{\max})$, é menor que $d-1$.

• Não Terminação: Os autores provam que, se $\dim(G_{\max}) < d-1$, o algoritmo não termina prematuramente (ou seja, o proxy de gradiente $b_k$ não se anula) com probabilidade um.
• Convergência para Maximizadores Globais: A sequência de valores do objetivo $r(A, B, v_k)$ converge quase certamente para o máximo global $R(A, B)$. Além disso, a sequência de iterados converge para o conjunto de maximizadores globais $G_{\max}$.
• Taxas de Convergência:
  • A norma do gradiente riemanniano desaparece a uma taxa sublinear de $O(1/n)$ com probabilidade um.
  • Especificamente, $\min_{k=0,\dots,n} \| \text{grad } f(v_k) \|^2 \leq \frac{C}{n+1}$, onde $C$ depende do número de condição de $B$ e da norma de $A$.
• Interpretação de Ordem Zero: O método é reinterpretado como um ascensão de gradiente riemanniano estocástico de ordem zero. Os autores mostram que a direção de atualização $b_k x_k$ serve como um estimador não enviesado do gradiente riemanniano (escalonado por $1/(d-1)$), ligando o método proposto a estruturas de otimização estocástica em variedades.

Resultados Numéricos
Experimentos numéricos extensos validam os achados teóricos e comparam o método proposto com alternativas de estado da arte:

• Comparação com ZO-RGA: O método proposto supera significativamente o ascensão de gradiente riemanniano de ordem zero estocástico (ZO-RGA) de [32], particularmente em altas dimensões ($d=100, 500$). A seleção analítica do tamanho do passo $\tau_k$ mostra-se superior aos tamanhos de passo constantes ou ao retrocesso de Armijo usados no ZO-RGA.
• Comparação com Gen-Oja: Em um problema de Karhunen-Loève, o método proposto converge mais rapidamente e produz aproximações de autofunções mais precisas do que tanto os métodos Gen-Oja determinísticos quanto os estocásticos.
• Robustez: O algoritmo demonstra robustez contra matrizes $B$ mal condicionadas, embora o tempo de convergência aumente com o número de condição $\kappa(B)$.
• Tamanho da Amostra ($m$): Aumentar o número de amostras $m$ (de 1 para 100) melhora significativamente a velocidade de convergência e reduz a variância, com custo adicional de tempo de execução mínimo devido à vetorização.
• Subproblema de Rayleigh-Ritz: Os autores comparam seu método com uma abordagem de Rayleigh-Ritz no subespaço gerado pelo iterado atual e $m$ amostras. Embora o método de Rayleigh-Ritz possa ser mais rápido para certas combinações de $m$ e $d$ grandes, o método proposto oferece um melhor equilíbrio entre complexidade computacional ($O(dm)$ vs. $O(d^2m)$) e velocidade de convergência.

Significância e Alegações
O artigo afirma introduzir um algoritmo "simples e eficiente" que resolve a maximização do quociente de Rayleigh generalizado sem exigir computações de adjunto ou inverso. Sua principal significância reside em:

1. Operação Livre de Adjunto: Fornece uma solução provadamente convergente para problemas onde $A^T$ não está disponível ou está desajustado, um cenário comum em problemas de imagem e inversão.
2. Rigor Teórico: Fornece a primeira análise de convergência para um método riemanniano estocástico de ordem zero aplicado especificamente ao quociente de Rayleigh generalizado, estabelecendo convergência quase certa para maximizadores globais e taxas sublineares.
3. Desempenho: Resultados empíricos demonstram que o método supera as linhas de base estocásticas e determinísticas existentes, particularmente em configurações de alta dimensão e ao lidar com matrizes mal condicionadas.

O trabalho estende um preprint anterior [41] ao generalizar a estrutura para geometria riemanniana e quocientes de Rayleigh generalizados, incorporando esclarecimentos adicionais e melhorias substanciais na análise de convergência.