Cost-sensitive spectral sampling algorithms for randomized block Kaczmarz methods

Resumen Técnico: Algoritmos de muestreo espectral sensibles al costo para métodos de Kaczmarz de bloques aleatorios

Planteamiento del problema
El artículo aborda el problema de diseño offline para los métodos de Kaczmarz de bloques aleatorios utilizados para resolver sistemas lineales consistentes $Ax=b$. Mientras que los métodos de Kaczmarz de bloques aleatorios proyectan las iteraciones sobre bloques de ecuaciones seleccionados aleatoriamente, su tasa de convergencia certificada depende fuertemente de la distribución de muestreo. Una restricción práctica crítica es que diferentes bloques de ecuaciones pueden incurrir en costos computacionales muy distintos (por ejemplo, debido al diseño de la memoria, la sobrecarga de comunicación o el tamaño del bloque).

Los enfoques existentes suelen prescribir heurísticas (proporcionales a la norma, basadas en pavimentación), se adaptan a los residuos actuales o optimizan cantidades libres de costo. El problema específico abordado aquí es: dada una colección finita y fija de bloques admisibles con costos positivos asociados, ¿qué distribución de probabilidad estática sobre estos bloques maximiza la tasa de convergencia exponencial certificada por unidad de trabajo computacional esperado?

Metodología y marco teórico
Los autores formalizan el problema representando cada bloque $B$ mediante su proyector ortogonal $P_B$ sobre el espacio fila del bloque y un costo $c_B$.

1. Certificado normalizado por trabajo: El certificado de convergencia estándar está gobernado por el autovalor más pequeño $\mu(p)$ del proyector esperado $H_p = \sum p_B P_B$ restringido al rango de $A^T$. El trabajo esperado por paso es $\bar{c}(p) = \sum p_B c_B$. El objetivo es maximizar la razón $\eta(p) = \mu(p) / \bar{c}(p)$.
2. Formulación de diseño óptimo: Al introducir un cambio de variable, $w_B = p_B / \bar{c}(p)$, el problema se transforma en maximizar el autovalor mínimo de una suma ponderada de proyectores escalados por costo $G_B/c_B$ (donde $G_B$ es el proyector restringido al espacio fila). Esto se identifica como un problema de diseño E-óptimo sensible al costo.
3. Programación Semidefinida (SDP): El problema se formula como un SDP:
   $$\max t \quad \text{s.t.} \quad \sum w_B G_B \succeq t I_r, \quad \sum w_B c_B = 1, \quad w_B \ge 0$$
   donde $r = \text{rank}(A)$.
4. Certificado dual: El artículo deriva una formulación dual que involucra un certificado de "dirección difícil". El valor óptimo $\eta^*$ es el mínimo, sobre matrices semidefinidas positivas de traza uno $Z$, del máximo de la eficiencia direccional normalizada por costo $\langle G_B, Z \rangle / c_B$ a través de la colección. Esto proporciona una brecha (gap) a posteriori rigurosa para cualquier diseño candidato.
5. Soporte disperso: Un teorema basado en el teorema de Carathéodory establece que existe un diseño óptimo con soporte en como máximo $r(r+1)/2 + 1$ bloques.

Contribuciones algorítmicas
El artículo propone dos algoritmos certificados para computar la distribución estática óptima:

1. Método de intercambio exacto: Un esquema de generación de columnas que mantiene un conjunto activo pequeño de bloques. Resuelve un SDP maestro restringido para encontrar una distribución candidata y un certificado dual, luego realiza un paso de "fijación de precios" (pricing) sobre la colección completa para identificar un nuevo bloque que mejore el certificado. Este método proporciona brechas de optimalidad rigurosas.
2. Diseño espectral de tipo Frank-Wolfe: Un método de gradiente condicional de primer orden aplicado al casco convexo normalizado por costo de los proyectores. Selecciona iterativamente el bloque con la mayor eficiencia direccional contra la dirección propia más débil actual (el supergradiente de la función de autovalor mínimo). Este método evita resolver SDPs restringidos y utiliza la misma cantidad tanto para la selección de bloques como para la certificación de la brecha.

Resultos y pruebas diagnósticas
El artículo presenta pruebas numéricas diagnósticas en lugar de comparativas a gran escala para aislar mecanismos específicos:

• Redundancia (Prueba A): En una colección con muchos bloques redundantes para unas pocas direcciones, el muestreo uniforme y basado en la norma funcionan mal porque desperdician masa de probabilidad en la redundancia. El diseño espectral concentra correctamente la masa en direcciones independientes, mejorando el certificado por un factor de $(N+1)/2$.
• Heterogeneidad de costos (Prueba B): En un entorno con bloques individuales (singletons) baratos y bloques grandes costosos, el diseño espectral ciego al costo (que ignora los costos) selecciona los bloques costosos, logrando una alta ganancia por iteración pero un desempeño pobre normalizado por trabajo. El diseño sensible al costo favorece correctamente a los bloques más baratos, produciendo un trabajo total significativamente menor para alcanzar un error objetivo.
• Caso no diagonal disperso (Prueba C): Utilizando una matriz dispersa con bloques de diversos tamaños y costos (modelados por una función de costo cúbica), el diseño sensible al costo también supera a los baselines de muestreo uniforme, basado en la norma y ciego al costo. La mediana empírica del trabajo observado en 20 ejecuciones coincidió estrechamente con el orden predicho por el certificado teórico normalizado por trabajo.

Significancia y afirmaciones
El artículo afirma proporcionar una perspectiva complementaria a la teoría de proyecciones aleatorias existente. No introduce un nuevo paso de proyección ni pretende optimizar la trayectoria exacta de media cuadrática. Su significancia radica en:

• Identificación Formal: Identificar explícitamente el problema de selección de bloques offline como un problema de diseño E-óptimo sensible al costo.
• Algoritmos Certificados: Proporcionar dos algoritmos con certificados a posteriori explícitos (brechas) que cuantifican qué tan cerca está una distribución estática de la tasa óptima normalizada por trabajo.
• Perspectiva Práctica: Demostrar que las heurísticas estándar (uniforme, basada en la norma) pueden ser sustancialmente subóptimas cuando la información del espacio fila es redundante o los costos de los bloques están desequilibrados.
• Alcance: El método se posiciona como una regla estática offline, más adecuada para escenarios donde una colección de bloques se reutiliza a través de muchos lados derechos, o donde los costos de los bloques varían significativamente. No está destinado a escenarios de resolución única donde el costo del diseño supera el costo de la resolución, ni pretende reemplazar los métodos adaptativos basados en residuos que resuelven un problema online diferente.