Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton

1. El Problema

En el álgebra lineal numérica aleatorizada (RandNLA) y el aprendizaje automático (ML), las técnicas de "sketching" (boceto) como el muestreo aleatorio y la proyección aleatoria se utilizan para reducir la complejidad computacional de matrices grandes ($n \times d$, con $n \gg d$). El objetivo es aproximar la matriz original $A$ mediante una matriz más pequeña $\tilde{A}$.

Sin embargo, en muchas aplicaciones críticas (optimización estocástica, estimadores estadísticos escalables, métodos de Newton), el objeto de interés no es la matriz $\tilde{A}$ en sí, sino su inversa (o la inversa de $\tilde{A}^\top \tilde{A} + C$).

• El Sesgo de Inversión (Inversion Bias): Aunque el muestreo aleatorio puede ser un estimador insesgado de $A^\top A$ (es decir, $E[\tilde{A}^\top \tilde{A}] = A^\top A$), la inversión es un operador no lineal. Por lo tanto, la inversa del boceto no es un estimador insesgado de la inversa real:
  $$E[(\tilde{A}^\top \tilde{A} + C)^{-1}] \neq (A^\top A + C)^{-1}$$
  Este fenómeno, conocido como sesgo de inversión, ha sido bien estudiado para proyecciones gaussianas densas (donde la corrección es conocida), pero existía una brecha teórica significativa para métodos de muestreo aleatorio (uniforme y basado en puntuaciones de apalancamiento o leverage scores) y proyecciones estructuradas (como SRHT). Los métodos anteriores de corrección para muestreo resultaban en límites de error vacíos o demasiado grandes para ser útiles en la práctica.

2. Metodología

Los autores emplean una combinación de Teoría de Matrices Aleatorias (RMT) no asintótica y técnicas de RandNLA para caracterizar y corregir este sesgo.

• Análisis de "Leave-One-Out": Utilizan un marco de análisis determinista equivalente y técnicas de perturbación de rango uno (lemas de Silverstein y Bai) para estudiar el comportamiento de la inversa de la matriz muestreada.
• Ecuación Autoconsistente: Derivan una ecuación autoconsistente que describe la expectativa condicional de la inversa muestreada. A diferencia de las proyecciones gaussianas donde el sesgo es un factor escalar simple, para el muestreo aleatorio, el sesgo depende de una matriz diagonal $D$ que varía según la distribución de muestreo y las puntuaciones de apalancamiento.
• Técnica de Desviación (Debiasing): Proponen una matriz de muestreo re-pesada ($\check{S}$) que corrige el sesgo. La corrección implica ajustar los pesos de las filas muestreadas utilizando las puntuaciones de apalancamiento exactas (o aproximadas) de la matriz original.
  • La fórmula de corrección para la matriz de muestreo $\check{S}$ es:
    $$\check{S} = \text{diag}\left\{ \sqrt{\frac{m}{m - \ell_i^C / \pi_i}} \right\} \cdot S$$
    Donde $\ell_i^C$ es la puntuación de apalancamiento y $\pi_i$ es la probabilidad de muestreo.
• Generalización: Demuestran que esta técnica funciona para:
  1. Muestreo uniforme.
  2. Muestreo basado en puntuaciones de apalancamiento exactas y aproximadas.
  3. Transformada de Hadamard Aleatoria Muestreada (SRHT).

3. Contribuciones Clave

1. Caracterización Precisa del Sesgo: Proporcionan la primera caracterización no vacua y precisa del sesgo de inversión para métodos de muestreo aleatorio general (Teorema 3.1). Muestran que el sesgo es más complejo que en las proyecciones gaussianas y depende de la relación entre la distribución de muestreo y las puntuaciones de apalancamiento.
2. Método de Corrección Eficiente: Presentan un enfoque de desviación (debiasing) que utiliza un re-pesado de la matriz de muestreo basado en puntuaciones de apalancamiento (Teorema 3.2).
   • Demuestran que para muestreo de apalancamiento aproximado y SRHT, la corrección compleja se reduce a un simple re-escalado escalar (multiplicar por $m/(m-d_{eff})$), lo cual es computacionalmente muy eficiente.
3. Convergencia Independiente del Problema para SSN: Aplican estos resultados al método de Newton Muestreado (Sub-sampled Newton - SSN). Establecen las primeras tasas de convergencia local independientes del problema para SSN con muestreo aleatorio, que coinciden casi exactamente con las tasas obtenidas por el método Newton Sketch con proyecciones gaussianas densas (Teorema 4.3).
4. Análisis de Fase de Transición: Identifican un comportamiento de transición de fase en el sesgo de inversión dependiendo de qué tan cerca esté la distribución de muestreo de la distribución exacta de apalancamiento (Corolario 3.4 y Figura 1).

4. Resultados

• Teóricos:
  • Se demuestra que la matriz inversa muestreada, tras aplicar la corrección propuesta, es un estimador $(\epsilon, \delta)$-insesgado de la inversa real.
  • Se establece que el método SSN desviado converge localmente con una tasa proporcional a $\frac{\rho_{max} d_{eff}}{m}$, eliminando la dependencia de constantes de condición del problema que limitaban a los métodos anteriores.
• Empíricos (Experimentos Numéricos):
  • Se probaron los métodos en problemas de regresión logística utilizando los conjuntos de datos MNIST y CIFAR-10.
  • Comparación: El método SSN desviado (específicamente con muestreo de apalancamiento de cresta aproximado, SSN-ARLev) superó consistentemente al método Newton-LESS (basado en proyecciones aleatorias dispersas) y a los métodos de primer orden (GD, SGD).
  • Eficiencia: Mientras que el tiempo de ejecución de Newton-LESS aumentaba significativamente con el tamaño del boceto ($m$), el tiempo del SSN desviado permaneció aproximadamente constante, logrando un mejor equilibrio entre "complejidad-convergencia".
  • Reducción de Sesgo: Los experimentos mostraron que la corrección escalar reduce drásticamente el sesgo de inversión, acercándose al rendimiento del muestreo exacto.

5. Significado e Impacto

• Puente Teórico-Práctico: Este trabajo cierra la brecha entre la teoría de matrices aleatorias y las aplicaciones prácticas de optimización de segundo orden. Proporciona garantías teóricas sólidas para el uso de muestreo aleatorio en métodos de Newton, que antes carecían de análisis de convergencia robustos independientes del problema.
• Eficiencia Computacional: Al demostrar que el muestreo aleatorio (que es mucho más barato que las proyecciones gaussianas densas o las transformadas de Hadamard completas) puede corregirse para eliminar el sesgo de inversión, habilita el uso de métodos de segundo orden escalables en conjuntos de datos masivos.
• Generalidad: La metodología no se limita a un tipo específico de muestreo, abarcando desde muestreo uniforme hasta técnicas avanzadas de apalancamiento y transformadas estructuradas, ofreciendo una solución unificada para el sesgo de inversión en RandNLA.

En resumen, el artículo demuestra que el sesgo de inversión en el muestreo aleatorio no es un defecto inherente insuperable, sino un fenómeno cuantificable y corregible, permitiendo que los métodos de optimización de segundo orden basados en muestreo alcancen el rendimiento teórico de los métodos basados en proyecciones gaussianas densas, pero con una fracción del costo computacional.