Resumen Técnico: Descomposición de Dependencia de Bajo Rango mediante Factorización de Matrices No Negativas Simétricas Acelerada

Planteamiento del Problema

La Factorización de Matrices No Negativas Simétricas (SymNMF) busca descomponer una matriz de dependencia simétrica y enteramente no negativa $S \in \mathbb{R}^{n \times n}_+$ en un factor de bajo rango $H \in \mathbb{R}^{n \times k}_+$ (donde $k \ll n$) tal que $S \approx HH^\top$. Esta descomposición revela estructuras de grupos latentes donde los miembros comparten patrones de dependencia comunes, sirviendo tanto como agrupamiento suave (soft clustering) como incrustaciones aprendidas (learned embeddings).

El artículo aborda la brecha de escalabilidad en SymNMF. Aunque el método está bien establecido, su despliegue práctico en carteras a gran escala (miles a millones de instrumentos) se ha visto dificultado por:

1. Restricciones de Memoria: La formulación estándar del objetivo requiere matrices intermedias explícitas de $n \times n$, lo que limita los trabajos previos a tamaños moderados ($n \lesssim 10^4$).
2. Falta de Comparación Sistemática: No existe una evaluación exhaustiva de las familias de optimizadores sobre entradas de verdad fundamental (ground-truth) realistas y controladas a gran escala.
3. Desafíos de Optimización: Los métodos efectivos a escalas moderadas suelen fallar en las ejecuciones prolongadas requeridas para $n$ grandes, particularmente debido a la interacción entre el manejo de restricciones (proyección vs. reparametrización) y la memoria del optimizador adaptativo.

El estudio se centra en dos tipos específicos de entradas que representan factores de riesgo financiero:

• Matrices de Correlación de Pearson Absoluta: Capturan la dependencia a través de la distribución completa.
• Matrices de Dependencia de Cola por Pares (TPDM): Basadas en la Teoría de Valores Extremos, capturan la dependencia condicionada a eventos extremos. Estas matrices suelen exhibir un espectro "plano" e mal condicionado, dominado por un único factor común.

Metodología

1. Reformulación Eficiente de Memoria

Para permitir la escalabilidad a $n \approx 10^6$, los autores reformulan la función objetivo utilizando una identidad de traza. La norma de Frobenius estándar $\|S - HH^\top\|_F^2$ se expande a:
$$\|S\|_F^2 - 2 \text{tr}(H^\top SH) + \|H^\top H\|_F^2$$
Esto elimina la necesidad de formar la matriz residual $n \times n$ de $S - HH^\top$. Todos los intermedios se reducen a matrices de $n \times k$ o $k \times k$. Este cambio algebraico aproximadamente duplica el $n$ máximo factible en una sola GPU (de $\sim 60,000$ a $\sim 130,000$ en FP32) y permite la distribución multinodo hasta $n = 10^6$.

2. Familias de Solvers y Configuraciones

El estudio evalúa siete familias de algoritmos (sobre 30 configuraciones) a través de tres paradigmas:

• Proyección de Gradiente: Gradiente Proyectado (PGD), Gradiente Proximal Acelerado (APG/FISTA).
• Adaptativos de Primer Orden: AdaGrad, RMSprop, Adam, NAdam, Adan, y tres extensiones novedosas introducidas en este trabajo:
  • AdaGrad por Partes (Piecewise AdaGrad): Reinicia el acumulador tras el estancamiento del objetivo para evitar la saturación.
  • SVRG Estocástico por Filas (Row-Stochastic SVRG): Combina el submuestreo de filas con instantáneas (snapshots) de gradiente completo periódicas para mantener un crecimiento uniforme del acumulador.
  • Block-SVRG AdaptGrow: Utiliza muestreo de bloques densos con crecimiento de lote adaptativo (comenzando pequeño y creciendo hacia el lote completo tras el estancamiento) y snapshots híbridos de SVRG para corregir la heterogeneidad del acumulador por fila.
• División/Descenso de Espejo (Splitting/Mirror Descent): Actualizaciones Multiplicativas (MU), ADMM, Descenso de Coordenadas de Bloque (HALS, ANLS) y Despliegue Profundo (SymNMF-Net).

3. Manejo de Restricciones

El artículo compara dos estrategias para imponer $H \ge 0$:

• Espacio Proyectado: Clampeado directo de $H$ después de las actualizaciones.
• Reparametrización Softplus (Espacio Logarítmico): Optimización de un $\Theta$ sin restricciones donde $H = \text{softplus}(\Theta)$.
  Los autores encuentran que el Softplus ayuda a los optimizadores de memoria corta (ej. RMSprop) y a los métodos de segundo orden a escalas pequeñas, pero corrompe los acumuladores de memoria larga (ej. AdaGrad, Adam) a medida que las ejecuciones se prolongan, debido a la naturaleza no estacionaria del gradiente de la regla de la cadena. Por consiguiente, los experimentos a gran escala utilizan el espacio proyectado.

4. Criterios de Convergencia

Se aplica una regla de parada rigurosa de tres partes de forma uniforme:

1. Puerta de Pérdida (Loss Gate): Error cuadrático normalizado $E_t < 0.1$.
2. Condición KKT: Norma del gradiente proyectado normalizado por entrada $\|\nabla_{\text{proj}} f(H)\|_F / (nk) < \tau_g$.
3. Estancamiento: Mejora relativa del objetivo por debajo de un umbral.
   Esto asegura que las soluciones no sean solo de baja pérdida, sino también puntos estacionarios, evitando la convergencia falsa en valles planos.

Resultados Clave

Fase 1: Selección de Algoritmos ($n \le 10^4$)

En una sola GPU NVIDIA GB200, once métodos convergieron de manera fiable. Sin embargo, solo seis cumplieron con los estrictos umbrales de eficiencia (convergencia en $<4$ segundos con $n=10^4$):

• ADMM
• RMSprop
• Block-SVRG AdaptGrow
• AdaGrad
• Row-Stochastic SVRG
• Piecewise AdaGrad

Las actualizaciones multiplicativas, el PGD estándar y el despliegue profundo fallaron en converger o fueron significativamente más lentos. Los métodos de segundo orden (L-BFGS, Newton) fallaron en los espectros de TPDM debido a una mala aproximación de la curvatura o problemas de memoria.

Fase 2: Factibilidad a Gran Escala ($n = 10^5, \text{ } 10^6$)

Los seis métodos seleccionados fueron probados en clústeres de GPU multinodo (hasta 64 GPUs).

• Dominio de la Familia AdaGrad: Cinco métodos de la familia AdaGrad (AdaGrad, Piecewise, Row-Stoch SVRG, Block-SVRG AdaptGrow, RMSprop) convergieron con éxito en $n=10^6$. ADMM fue omitido a esta escala debido a su velocidad.
• Dependencia Espectral: El solver "más rápido" depende del espectro de la matriz:
  • Matrices de Correlación (Espectro de Bajo Rango Dominante): El AdaGrad de lote completo es el más rápido. El problema posee una brecha clara entre señal y ruido, permitiendo ejecuciones cortas donde los pasos de lote completo son eficientes.
  • TPDM (Espectro Plano e Mal Condicionado): Block-SVRG AdaptGrow es el más rápido. El espectro está dominado por un factor común con brechas cercanas a cero, lo que requiere ejecuciones largas. El menor costo por iteración de la estrategia de muestreo de bloques adaptativa compensa la necesidad de más iteraciones.
• Rendimiento: En $n=10^6$, Block-SVRG AdaptGrow resolvió TPDM en ~4 minutos (409 iteraciones), mientras que AdaGrad resolvió correlación en ~2 minutos (72 iteraciones).

Línea Base de Agrupamiento (Clustering)

El artículo compara el K-means Esférico (aplicado a las filas de $S$) como una alternativa de etiquetas duras (hard-label).

• Eficiencia: K-means es significativamente más rápido (menos iteraciones) cuando existe una estructura de clúster angular.
• Degeneración: K-means falla (silueta $\approx 0$) cuando la matriz colapsa hacia un único factor común (bajo rango efectivo, $r_{\text{eff}} \to 1$), un régimen común en las TPDM de gran escala. En estos casos, la factorización suave proporcionada por SymNMF sigue siendo necesaria.

Significancia y Reivindicaciones

El artículo afirma cerrar la brecha entre la SymNMF teórica y la aplicación práctica a gran escala en la estimación de riesgo financiero. Sus principales contribuciones son:

1. Escalabilidad: Demostrar que la SymNza densa es tratable hasta $n=10^6$ mediante la reformulación de la identidad de traza y la distribución multi-GPU, eliminando el cuello de botella de memoria $O(n^2)$.
2. Recomendaciones de Solvers: Proporcionar una guía basada en datos para la selección de solvers según el tipo de entrada y la escala. Identifica a AdaGrad diagonal como el predeterminado para ejecuciones cortas y a Block-SVRG AdaptGrow para ejecuciones largas y mal condicionadas.
3. Innovación Algorítmica: Introducir y validar extensiones de ingeniería específicas (Piecewise AdaGrad, Block-SVRG AdaptGrow) que resuelven la tensión entre la memoria infinita de AdaGrad (buena para objetivos estacionarios) y la saturación en ejecuciones largas.
4. Manejo de Restricciones: Caracterizar el compromiso dependiente de la escala entre la proyección y el Softplus, aconsejando no usar Softplus para métodos adaptativos de memoria larga a gran escala.

Los autores enfatizan que estos hallazgos son propiedades del propio paisaje de optimización de SymNMF, lo que los hace aplicables a cualquier problema con características espectrales similares, no solo a las entradas financieras específicas utilizadas.