Sobre la convergencia del gradiente de varianza reducida estocástica para problemas inversos lineales

Información Básica

• ID del Artículo: 2510.14759
• Título: On the convergence of stochastic variance reduced gradient for linear inverse problems
• Autores: Bangti Jin, Zehui Zhou (Departamento de Matemáticas, Universidad China de Hong Kong)
• Clasificación: math.NA cs.NA math.OC
• Fecha de Publicación: 16 de octubre de 2025 (preimpresión arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.14759

Resumen

El método de gradiente de varianza reducida estocástica (SVRG) es una versión acelerada del descenso de gradiente estocástico basada en reducción de varianza, que muestra promesa en la resolución de problemas inversos a gran escala. Este artículo analiza SVRG y su versión regularizada que incorpora conocimiento previo, para resolver problemas inversos lineales en espacios de Hilbert. La investigación demuestra que, bajo un tamaño de paso constante apropiado y condiciones de regularidad, SVRG regularizado puede lograr una tasa de convergencia óptima con respecto al nivel de ruido, sin necesidad de ninguna regla de parada anticipada; SVRG estándar también es óptimo para problemas con soluciones no suaves bajo una regla de parada previa. El análisis se basa en recursiones de error explícitas y estimaciones previas apropiadas sobre actualizaciones de bucle interno respecto al punto de anclaje.

Antecedentes y Motivación de la Investigación

Descripción del Problema

Este artículo estudia problemas inversos lineales en espacios de Hilbert: $A_\dagger x = y_\dagger$

donde:

• $A_\dagger: X \to Y = Y_1 \times \cdots \times Y_n$ es el operador del sistema
• $x \in X$ es la señal desconocida, $y_\dagger \in Y$ son los datos exactos
• En la práctica solo se pueden obtener datos ruidosos $y^\delta = y_\dagger + \xi$, con nivel de ruido $\delta = \|\xi\|_Y$

Motivación de la Investigación

1. Necesidad de problemas a gran escala: Los problemas inversos lineales aparecen ampliamente en aplicaciones prácticas como tomografía computarizada y tomografía por emisión de positrones, con volúmenes de datos masivos
2. Limitaciones de métodos existentes: Los métodos iterativos tradicionales tienen baja eficiencia computacional en problemas a gran escala
3. Ventajas de SVRG: El método de gradiente de varianza reducida estocástica tiene excelente escalabilidad, pero su análisis teórico en problemas inversos aún no es completo
4. Necesidad de regularización: SVRG estándar requiere reglas de parada anticipada para lograr regularización, y la incorporación de conocimiento previo podría mejorar esta situación

Contribuciones Principales

1. Análisis teórico mejorado: Se establece una teoría de convergencia completa para SVRG y SVRG regularizado (rSVRG) en la resolución de problemas inversos lineales
2. Tasa de convergencia óptima: Se demuestra que ambos métodos pueden lograr la tasa de convergencia óptima $O(\delta^{2\nu/(1+2\nu)})$ bajo condiciones apropiadas
3. Propiedades de regularización: rSVRG posee un mecanismo de regularización intrínseco sin necesidad de parada anticipada; SVRG estándar también posee propiedades de regularización bajo parada previa
4. Convergencia en esperanza y casi segura: Se establecen simultáneamente tasas de convergencia en sentido de esperanza y casi seguro, extendiendo resultados previos
5. Relajación de condiciones: Las condiciones para convergencia óptima de SVRG son más relajadas en comparación con trabajos previos

Explicación Detallada del Método

Definición de la Tarea

Considere el problema de optimización: $J(x) = \frac{1}{2n}\|A_\dagger x - y^\delta\|_Y^2 = \frac{1}{n}\sum_{i=1}^n f_i(x)$ donde $f_i(x) = \frac{1}{2}\|A_{\dagger,i}x - y^\delta_i\|_{Y_i}^2$

Arquitectura del Algoritmo

SVRG Estándar (Algoritmo 1)

Inicialización: x₀^δ = x₀, frecuencia M, tamaño de paso {ηₖ}
para K = 0,1,... hacer
    Calcular gₖ = J'(x_{KM}^δ) = (1/n)A_†*(A_†x_{KM}^δ - y^δ)
    para t = 0,1,...,M-1 hacer
        Muestrear aleatoriamente i_{KM+t} ∈ {1,...,n}
        Actualizar x_{KM+t+1}^δ = x_{KM+t}^δ - η_{KM+t}(A*_{i_{KM+t}}A_{i_{KM+t}}(x_{KM+t}^δ - x_{KM}^δ) + gₖ)
    fin para
fin para

SVRG Regularizado (Algoritmo 2)

Reemplazar el operador $A_\dagger$ con un operador aproximado $A$, obtenido mediante descomposición de valores singulares truncada: $A(\cdot) = \sum_{j=1}^J \sigma_j\langle\phi_j, \cdot\rangle\psi_j$ donde se retienen los valores singulares principales que satisfacen $\sigma_j \geq a\delta^b$.

Suposiciones Principales (Suposición 2.1)

1. Condición de tamaño de paso: $\eta_j = c_0 \leq L^{-1}$, donde $L = \max_{1\leq i\leq n}\|A_i\|^2$
2. Condición de fuente: Existen $\nu > 0$ y $w \in N(A_\dagger)^\perp$ tales que $x_\dagger - x_0 = B_\dagger^\nu w$
3. Aproximación del operador: Cuando $a > 0$, $A$ se construye mediante SVD truncada, reteniendo valores singulares $\sigma_j \geq a\delta^b$

Puntos de Innovación Técnica

1. Estrategia de descomposición de error: El error se descompone en partes de sesgo y varianza, estimadas por separado con precisión
2. Análisis de punto de anclaje: Mediante el análisis del comportamiento de actualizaciones de bucle interno relativo al punto de anclaje, se establecen estimaciones previas clave
3. Marco unificado: Se proporciona un marco teórico unificado para tratar SVRG estándar y SVRG regularizado

Configuración Experimental

Conjuntos de Datos

Se utilizan tres problemas inversos estándar del paquete Regutools:

• s-phillips: Problema levemente mal planteado (mildly ill-posed)
• s-gravity: Problema severamente mal planteado (severely ill-posed)
• s-shaw: Problema severamente mal planteado (severely ill-posed)

Todos los problemas se discretizan en sistemas lineales de dimensión finita $n = m = 1000$.

Parámetros Experimentales

• Generación de solución exacta: $x_\dagger = \|(A_\dagger^*A_\dagger)^\nu x_e\|_{\ell^\infty}^{-1}(A_\dagger^*A_\dagger)^\nu x_e$
• Configuración de ruido: $y^\delta_i = y_{\dagger,i} + \epsilon\|y_\dagger\|_{\ell^\infty}\xi_i$, $\xi_i \sim \mathcal{N}(0,1)$
• Tamaño de paso: Método de Landweber usa $c_0 = \|A_\dagger\|^{-2}$, (r)SVRG usa $c_0 = O(c)$, donde $c = L^{-1}$
• Frecuencia: $M = 2n$
• Iteraciones máximas: $10^5$ rondas

Métodos de Comparación

• Método de Landweber (LM): Método clásico de regularización iterativa, usando criterio de discrepancia para parada
• SVRG estándar: Usando parada en el punto de error óptimo
• SVRG regularizado (rSVRG): Usando criterio de parada guiado por teoría

Resultados Experimentales

Resultado Teórico Principal (Teorema 2.1)

Bajo la Suposición 2.1, existen constantes $c^*$ independientes de $k,n,\delta$ tales que:

Tasa de convergencia en esperanza: