Stochastic Zeroth-Order Method for Computing Generalized Rayleigh Quotients

Resumen Técnico: Método Estocástico de Orden Cero para el Cálculo de Cocientes de Rayleigh Generalizados

Planteamiento del Problema
El artículo aborda la maximización del cociente 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}$$
donde $A \in \mathbb{R}^{d \times d}$ y $B \in \text{Sym}^d_{\succ 0}$ (simétrica definida positiva). Este problema es fundamental en el álgebra lineal numérica, apareciendo en la equivalencia espectral, las descomposiciones de valores singulares generalizados y el análisis de estabilidad de las ecuaciones diferenciales parciales (vía el abscisa numérica).

Los métodos convencionales para resolver este problema suelen depender de productos matriz-adjunto ($A^T$) y del cálculo explícito de $B^{-1}$. Los autores identifican dos limitaciones primarias en estos enfoques:

1. Costo Computacional y Estabilidad: Calcular $B^{-1}$ o realizar productos matriz-vector que involucren a este es costoso y propenso a imprecisiones numéricas.
2. Desajuste del Adjunto (Adjoint Mismatch): En aplicaciones como la tomografía computarizada, la transpuesta $A^T$ suele ser reemplazada por un operador aproximado y computacionalmente tratable. Este "desajuste del adjunto" conduce a errores de reconstrucción significativos, lo que hace que los métodos que requieren adjuntos exactos sean inadecuados.

Metodología
Los autores proponen un algoritmo riemanniano estocástico de orden cero que opera directamente sobre la variedad $S^{d-1}_B = \{v \in \mathbb{R}^d : \langle v, Bv \rangle = 1\}$. El método evita calcular $A^T$ o $B^{-1}$ por completo, basándose únicamente en productos matriz-vector con $A$ y $B$.

El algoritmo central (Algoritmo 1 para muestra única, Algoritmo 2 para muestras múltiples) procede de la siguiente manera:

1. Inicialización: Comenzar con un vector aleatorio $v_0$ en la variedad.
2. Muestreo: En cada iteración $k$, muestrear una dirección aleatoria $x_k$ del espacio tangente $T_{v_k} S^{d-1}_B$. Esto se logra proyectando un vector gaussiano estándar sobre el espacio tangente y normalizándolo.
3. Tamaño de Paso Óptimo: En lugar de utilizar un tamaño de paso fijo o de retroceso (backtracking), el algoritmo resuelve analíticamente el problema de maximización unidimensional a lo largo de la dirección muestreada:
   $$\tau_k = \arg\max_{\tau \in \mathbb{R}} r(A, B, v_k + \tau x_k)$$
   El Teorema 3.1 proporciona una solución de forma cerrada para $\tau_k$ que involucra únicamente productos internos de $v_k$ y $x_k$ con $A$ y $B$.
4. Actualización: La iteración se actualiza mediante el mapa de retracción: $v_{k+1} = R_{v_k}(\tau_k x_k)$.

La variante de muestras múltiples (Algoritmo 2) promedia múltiples direcciones muestreadas para reducir la varianza de la estimación del gradiente antes de calcular el tamaño del paso.

Contribuciones Teóricas
El artículo establece garantías de convergencia rigurosas bajo la condición de que la dimensión del subespacio propio correspondiente al autovalor máximo, $\dim(G_{\max})$, sea menor que $d-1$.

• No Terminación: Los autores demuestran que si $\dim(G_{\max}) < d-1$, el algoritmo no termina prematuramente (es decir, el proxy del gradiente $b_k$ no se anula) con probabilidad uno.
• Convergencia a los Maximizadores Globales: La secuencia de valores del objetivo $r(A, B, v_k)$ converge casi seguramente al máximo global $R(A, B)$. Además, la secuencia de iteraciones converge al conjunto de maximizadores globales $G_{\max}$.
• Tasas de Convergencia:
  • La norma del gradiente de Riemann se anula a una tasa sublineal de $O(1/n)$ con probabilidad uno.
  • Específicamente, $\min_{k=0,\dots,n} \| \text{grad } f(v_k) \|^2 \leq \frac{C}{n+1}$, donde $C$ depende del número de condición de $B$ y de la norma de $A$.
• Interpretación de Orden Cero: El método se reinterpreta como un ascenso de gradiente de Riemann estocástico de orden cero. Los autores muestran que la dirección de actualización $b_k x_k$ sirve como un estimador insesgado del gradiente de Riemann (escalado por $1/(d-1)$), vinculando el método propuesto con los marcos de optimización estocástica existentes en variedades.

Resultados Numéricos
Extensos experimentos numéricos validan los hallazgos teóricos y comparan el método propuesto con otras alternativas de vanguardia:

• Comparación con ZO-RGA: El método propuesto supera significativamente al ascenso de gradiente de Riemann de orden cero estocástico (ZO-RGA) de [32], particularmente en dimensiones altas ($d=100, 500$). La selección analítica del tamaño de paso $\tau_k$ resulta superior a los tamaños de paso constantes o al retroceso de Armijo utilizados en ZO-RGA.
• Comparación con Gen-Oja: En un problema de Karhunen-Loève, el método propuesto converge más rápido y produce aproximaciones de funciones propias más precisas que los métodos Gen-Oja tanto deterministas como estocásticos.
• Robustez: El algoritmo demuestra robustez frente a matrices $B$ mal condicionadas, aunque el tiempo de convergencia aumenta con el número de condición $\kappa(B)$.
• Tamaño de Muestra ($m$): Aumentar el número de muestras $m$ (de 1 a 100) mejora significativamente la velocidad de convergencia y reduce la varianza, con un costo de tiempo de ejecución adicional mínimo debido a la vectorización.
• Subproblema de Rayleigh-Ritz: Los autores comparan su método con un enfoque de Rayleigh-Ritz sobre el subespacio generado por la iteración actual y $m$ muestras. Si bien el método de Rayleigh-Ritz puede ser más rápido para ciertas combinaciones de $m$ y $d$ grandes, el método propuesto ofrece un mejor equilibrio entre la complejidad computacional ($O(dm)$ frente a $O(d^2m)$) y la velocidad de convergencia.

Significado y Reivindicaciones
El artículo afirma introducir un algoritmo "simple y eficiente" que resuelve la maximización del cociente de Rayleigh generalizado sin requerir cálculos de adjuntos o inversos. Su principal importancia radica en:

1. Operación Libre de Adjuntos: Proporciona una solución provablemente convergente para problemas donde $A^T$ no está disponible o presenta un desajuste, un escenario común en problemas de imagen e inversión.
2. Rigor Teórico: Proporciona el primer análisis de convergencia para un método de Riemann estocástico de orden cero aplicado específicamente al cociente de Rayleigh generalizado, estableciendo la convergencia casi segura a los maximizadores globales y tasas sublineales.
3. Rendimiento: Los resultados empíricos demuestran que el método supera a las líneas base estocásticas y deterministas existentes, particularmente en entornos de alta dimensión y al tratar con matrices mal condicionadas.

El trabajo extiende un preimpreso previo [41] al generalizar el marco a la geometría de Riemann y a los cocientes de Rayleigh generalizados, incorporando aclaraciones adicionales y mejoras sustanciales en el análisis de convergencia.