Riemannian Optimization for Hadamard Products of Low-Rank Matrices

Resumen Técnico: Optimización Riemanniana para Productos de Hadamard de Matrices de Bajo Rango

Formulación del Problema
El artículo aborda el desafío de modelar datos con estructura multiplicativa mediante el producto elemento a elemento (Hadamard) de dos matrices de bajo rango. La matriz objetivo $W \in \mathbb{R}^{m \times n}$ se modela como:
$$W = (GH^\top) \circ (UV^\top)$$
donde $G, U \in \mathbb{R}^{m \times r_1, r_2}$ y $H, V \in \mathbb{R}^{n \times r_1, r_2}$. Si bien esta formulación ofrece eficiencia de parámetros en comparación con una factorización estándar de rango-$r_1r_2$ (requiriendo $(m+n)(r_1+r_2)$ parámetros frente a $(m+n)r_1r_2$), introduce un paisaje de optimización complejo. Específicamente, el modelo exhibe simetrías más allá de la invariancia de reparametrización de la Clase General Lineal (GL) estándar. El producto $W$ permanece invariante bajo escalamientos acoplados de filas y columnas entre los dos pares de factores. Estos grados de libertad adicionales crean una geometría desafiante que los métodos de descenso de gradiente euclidiano estándar luchan por navegar eficientemente.

Los solvers existentes enfrentan limitaciones: el Descenso de Gradiente Alternante (AGD) ignora la geometría específica y las simetrías de escala, mientras que el Descenso de Coordenadas por Bloques (BCD) es altamente efectivo para pérdidas de mínimos cuadrados, pero carece de soluciones en forma cerrada para pérdidas no cuadráticas (por ejemplo, predicción de enlace logístico o entropía cruzada), lo que limita su aplicabilidad en estadística robusta y otros dominios.

Metodología
Los autores proponen formular el problema de aprendizaje como una tarea de optimización en una variedad de cociente Riemanniana. Este enfoque tiene en cuenta explícitamente las invariancias naturales del producto de Hadamard.

1. Geometría de la Variedad: Los autores definen la variedad de cociente $\mathcal{M}$ factorizando el grupo de simetría completo $\mathcal{G}$, que incluye:

   • La invariancia de reparametrización GL estándar para cada par de factores.
   • Nuevas simetrías de escala de cruce de Hadamard, donde matrices diagonales invertibles escalan las filas y columnas a través de los dos pares de factores de forma inversa.
     La variedad se construye a partir del espacio de matrices de rango de columna completo módulo esta acción de grupo.

2. Métrica Riemanniana Novedosa: Una contribución crítica es la derivación de una métrica Riemanniana de bloques diagonales ($g_x$) derivada de la aplicación (pullback) del producto de Frobenius.

   • La métrica de aplicación completa acopla los cuatro bloques de factores, resultando en un sistema lineal denso y computacionalmente costoso.
   • La métrica propuesta retiene únicamente los bloques diagonales de la aplicación, descartando los términos cruzados.
   • La métrica se define a través de matrices de peso ($S$-bloques) para cada fila/columna de los factores. Por ejemplo, el peso para la $i$-ésima fila de $G$ es $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$, donde $Y = UV^\top$.
   • Invariancia: Se demuestra que la métrica es invariante bajo las simetrías de reparametrización GL y de escala de cruce de Hadamard. Esto asegura que el optimizador sea insensible a la división arbitraria de magnitudes entre los factores.
   • Conexión con BCD: Las matrices de peso en la métrica propuesta corresponden exactamente a las matrices de ecuaciones normales utilizadas en las actualizaciones de BCD. Por lo tanto, el gradiente Riemanniano puede interpretarse como la ejecución de un paso de BCD "suave" simultáneamente en todas las filas para funciones de pérdida suaves arbitrarias.

3. Algoritmo de Optimización (RGD): Los autores desarrollan un algoritmo de Descenso de Gradiente Riemanniano (RGD):

   • Cómputo del Gradiente: El gradiente Riemanniano se calcula resolviendo sistemas lineales independientes de $r \times r$ (uno por cada fila/columna) utilizando los $S$-bloques.
   • Tamaño de Paso: Se deriva un tamaño de paso de Cauchy de Gauss-Newton libre de ajuste (tuning-free). Este tamaño de paso es invariante bajo el grupo de simetría y no requiere ajuste de hiperparámetros.
   • Retracción: Se utiliza una retracción aditiva para mapear las actualizaciones de vuelta a la variedad.
   • Complejidad: El costo por iteración escala linealmente con el número de entradas observadas $N$ ($O(Nr)$) y polinómicamente con los rangos ($O((m+n)r^4)$), lo que lo hace eficiente para grandes conjuntos de datos.

Contribuciones Clave

1. Caracterización Geométrica: Descripción formal de la estructura de la variedad de cociente para productos de Hadamard, identificando tanto las simetrías GL como las de escala de cruce de Hadamard.
2. Métrica Invariante de Escala: Propuesta de una nueva métrica Riemanniana de bloques diagonales que respeta el grupo de simetría completo y desacopla la optimización en subproblemas independientes de filas/columnas.
3. Desarrollo de Algoritmos: Derivación de un algoritmo RGD con un tamaño de paso de Gauss-Newton libre de ajuste que soporta cualquier función de pérdida suave, a diferencia de BCD que está restringido a mínimos cuadrados.
4. Validación Empírica: Demostración de que el método alcanza un rendimiento comparable al de BCD en tareas de mínimos cuadrados, mientras que supera a este en objetivos no cuadráticos y logra resultados superiores en configuraciones específicas de rango de Hadamard.

Resultados Experimentales
Los autores evaluaron RGD en conjuntos de datos sintéticos y del mundo real:

• Pruebas de Estrés Sintéticas: En objetivos sintéticos de $2,000 \times 1,000$, RGD demostró:
  • Invariancia de Escala: El error de recuperación se mantuvo constante a través de variaciones de separación de escala diagonal ($\kappa_{scale}$), verificando empíricamente la propiedad de invariancia de la métrica. En contraste, AGD mostró sensibilidad a la escala.
  • Condicionamiento: RGD funcionó de manera comparable a BCD a través de variaciones en los números de condición de los factores, superando significativamente a AGD.
  • Robustez al Ruido: RGD convergió al nivel de ruido a la misma tasa que BCD, mientras que AGD se quedó rezagado.
• Conjuntos de Datos del Mundo Real:
  • Aproximación de Matriz Completa: En los conjuntos de datos Camera, Football y Les Misérables, RGD siguió de cerca a BCD en error relativo, confirmando que la métrica proporciona un precondicionamiento equivalente a BCD para pérdidas cuadráticas.
  • MovieLens-1M: En una tarea de completitud de matriz con un presupuesto de parámetros fijo ($r_1+r_2=6$), RGD logró el RMSE de validación (held-out) más bajo en todas las configuraciones de rango de Hadamard probadas. Notablemente, la configuración equilibrada $(3,3)$ superó a la casi vanilla $(1,5)$, sugiriendo que la capacidad de interacción de Hadamard ($r_1r_2$) contribuye a la precisión. RGD superó consistentemente a AGD y logró un RMSE menor que BCD en configuraciones genuinamente de Hadamard.

Significancia y Reivindicaciones
El artículo afirma cerrar la brecha entre la eficiencia de BCD para problemas de mínimos cuadrados y la flexibilidad de los métodos basados en gradiente para pérdidas suaves generales. Al elevar el problema a una variedad de cociente Riemanniana, los autores proporcionan un marco principista que maneja las complejas simetrías de los productos de Hadamard. El algoritmo RGD propuesto ofrece un método de optimización libre de ajuste y invariante de escala que escala linealmente con el tamaño de los datos. Los autores sostienen que este marco se extiende naturalmente a productos de $k$ matrices de bajo rango y es compatible con otros solvers de Riemann (por ejemplo, gradientes conjugados, métodos de región de confianza), ofreciendo una alternativa robusta a los solvers existentes.