Variational Free Energy Pivot Selection for Pivoted Cholesky

Resumen Técnico: Selección de Pivote de la Energía Libre Variacional para Cholesky con Pivoteo

Planteamiento del Problema
Las aproximaciones de bajo rango de matrices definidas positivas simétricas (SPD) son fundamentales en el álgebra lineal numérica, particularmente en la regresión de Procesos Gaussianos (GP), donde la matriz de kernel $K$ se aproxima mediante una factorización de rango-$r$ $\tilde{K} = LL^\top$. Los métodos clásicos, como el pivoteo codicioso (greedy) y el de Cholesky con pivoteo aleatorio (RPCholesky), seleccionan pivotes secuencialmente para minimizar el error de la norma de traza algebraica del residuo ($\text{tr}(K - \tilde{K})$). Sin embargo, en muchas aplicaciones, la matriz $K$ no se evalúa de forma aislada, sino dentro de un funcional matricial no lineal. Específicamente, en la regresión GP, la calidad de la aproximación está determinada por la Energía Libre Variacional (VFE), denotada como $L(\tilde{K})$, la cual sirve como un límite inferior en la log-verosimilitud marginal.

El funcional VFE combina tres términos distintos: un término de log-determinante (complejidad), un término cuadrático de ajuste de datos y un término de penalización de traza. Las reglas de selección de pivote existentes, que dependen únicamente de las magnitudes diagonales del residuo, apuntan solo al error de la norma de traza. En consecuencia, descuidan los componentes de log-determinante y de ajuste de datos, lo que puede conducir a aproximaciones sistemáticamente subóptimas para el objetivo de inferencia específico. El artículo aborda la pregunta: ¿Cómo debe realizarse la selección de pivotes cuando el objetivo es optimizar un funcional de matriz en lugar de un error de aproximación algebraica pura?

Metodología
Los autores proponen una nueva regla de selección de pivotes, denominada Cholesky con pivoteo $\Delta$-VFE, que maximiza directamente el cambio exacto de un paso en el funcional de la Energía Libre Variacional bajo actualizaciones de rango-1 consistentes con Cholesky.

1. Derivación de la Fórmula de Ganancia:
   Los autores derivan una expresión de forma cerrada para el cambio exacto $\Delta L$ en la VFE $L(\tilde{K})$ inducido por una actualización de rango-1 $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$. Utilizando el Lema del Determinante de Matrices y la fórmula de Sherman-Morrison, descomponen la ganancia en tres componentes aditivos:
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   donde:

   • $a = u^\top \Sigma_i^{-1} u$ representa la contribución de complejidad (término de log-determinante), midiendo la interacción de la actualización con la métrica inversa regularizada.
   • $b = u^\top \Sigma_i^{-1} y$ representa la contribución de ajuste de datos, midiendo la alineación entre la dirección de la actualización y el residuo de la predicción actual.
   • $\|u\|^2_2$ representa la contribución de traza (reducción de la varianza del residuo), que corresponde a la disminución exacta de la traza en un paso, en lugar del proxy diagonal utilizado en los métodos clásicos.

2. Actualizaciones Consistentes con Cholesky:
   Para asegurar que la aproximación siga siendo una factorización de Cholesky válida, el vector de actualización $u$ se restringe a la forma $u_p = t_p / \sqrt{(T_i)_{p,p}}$, donde $t_p$ es la $p$-ésima columna de la matriz de residuo $T_i$. Esta restricción asegura que el residuo permanezca semidefinido positivo y que la entrada diagonal del pivote seleccionado sea cero.

3. Realización Algorítmica:
   Evaluar $\Delta L$ para todos los $n$ candidatos en cada paso sería computacionalmente prohibitivo ($O(n^2r^2)$). Para mantener la eficiencia, el método emplea una estrategia de muestreo por lotes (batched sampling):

   • En cada iteración, un lote de $s$ pivotes candidatos se muestrea del conjunto de índices no utilizados.
   • La probabilidad de muestreo es proporcional a las entradas diagonales del residuo, idéntica a la distribución utilizada en RPCholesky.
   • La inversa regularizada $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$ se aplica a los vectores de manera eficiente utilizando la identidad de matrices de Woodbury y actualizaciones incrementales de una matriz auxiliar $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$.
   • Este enfoque permite la evaluación de la ganancia para $s$ candidatos con un costo total de $O(snr^2)$, igualando la complejidad asintótica de RPCholesky hasta el factor de lote $s$.

Contribuciones Clave

• Regla de Pivote Basada en el Objetivo: El artículo deriva el primer criterio de selección de pivote que maximiza explícitamente la ganancia por paso de la Energía Libre Variacional, en lugar del error de la norma de traza.
• Garantías Teóricas: Los autores demuestran que cualquier secuencia de actualizaciones de rango-1 consistentes con Cholesky produce una secuencia monótonamente no decreciente de valores de VFE. La regla propuesta selecciona el pivote que maximiza esta ganancia garantizada en cada paso.
• Eficiencia de Complejidad: El método logra la misma complejidad asintótica que el Cholesky con pivoteo aleatorio ($O(snr^2)$) aprovechando las actualizaciones incrementales de Woodbury y la evaluación de candidatos por lotes.
• Interpretación Jerárquica: El trabajo establece una jerarquía de tres niveles de reglas de pivote:
  1. Nivel 1: Codicioso/RPCholesky clásico (usa un proxy diagonal para la reducción de la traza).
  2. Nivel 2: Maximizador exacto de reducción de traza (usa la columna completa del residuo, ignora datos/complejidad).
  3. Nivel 3: $\Delta$-VFE (usa la columna completa del residuo, el vector de datos y la inversa regularizada para optimizar la VFE completa).

Resultados
Experimentos numéricos en los conjuntos de datos Abalone y QM7 demuestran lo siguiente:

• Optimización de VFE: $\Delta$-VFE logra consistentemente un límite más ajustado en la log-verosimilitud marginal (menor brecha de VFE relativa) en comparación con tanto el método codicioso como RPCholesky, particularmente en rangos bajos a moderados ($r \le 1024$).
• Calidad de la Aproximación: El método mantiene una calidad de aproximación de la norma de traza comparable a la de RPCholesky. No sacrifica la precisión de la aproximación del kernel estándar para ganar mejoras en la VFE.
• Desempeño Predictivo: En tareas de regresión GP, la mejora en la VFE se traduce en una reducción de los errores de predicción (RMSE y MAE) en rangos bajos a moderados.
• Sensibilidad al Tamaño del Lote: Aumentar el tamaño del lote $s$ produce rendimientos decrecientes en el desempeño, pero mejora consistentemente la brecha de VFE y la precisión predictiva. Incluso tamaños de lote pequeños (por ejemplo, $s=8$ o $s=16$) proporcionan ganancias sustanciales sobre RPCholesky.

Significancia
El artículo afirma que el método propuesto cierra la brecha entre la aproximación de matrices algebraicas y los objetivos de inferencia específicos de la tarea. Al derivar una ganancia exacta de forma cerrada para la VFE, los autores proporcionan una regla de pivote codiciosa que está explícitamente alineada con el objetivo de inferencia probabilística de los procesos gaussianos. Los resultados sugieren que para aplicaciones donde el funcional de la matriz incluye términos de ajuste de datos o de complejidad, optimizar únicamente el error de la norma de traza es insuficiente, y que la selección consciente del objetivo ofrece un rendimiento práctico superior sin incurrir en un sobrecosto computacional significativo. El método se presenta como una generalización directa de RPCholesky que incorpora información adicional sobre la función objetivo.