Resumen Técnico: Sobre el Extragradiente Estocástico de Muestra Única e Independiente para Inecuaciones Variacionales Monótonas

Planteamiento del Problema

Este trabajo investiga las propiedades de convergencia de los métodos de Extragradiente Estocástico (SEG) para resolver Problemas de Inecuación Variacional (VIP) monótonos. Un VIP busca un punto $x^* \in X$ tal que $\langle F(x^*), x - x^* \rangle \geq 0$ para todo $x \in X$, donde $F$ es un operador monótono. En el entorno estocástico, el operador $F$ se define como una suma finita $F(x) = \frac{1}{n} \sum_{i=1}^n F(x; \xi_i)$, y los algoritmos acceden a $F$ mediante muestras estocásticas.

El artículo se centra en dos variantes distintas de SEG:

1. SEG de Muestra Independiente (I-SEG): Utiliza índices aleatorios independientes $\xi_{i_k}$ y $\xi_{\hat{i}_k}$ para los pasos de extrapolación y actualización, respectivamente.
2. SEG de Muestra Única (S-SEG): Utiliza un índice aleatorio compartido $\xi_{i_k} = \xi_{\hat{i}_k}$ para ambos pasos.

Aunque el I-SEG posee una teoría de convergencia bien desarrollada, el S-SEG —una variante natural preferida en la práctica por su eficiencia computacional— ha recibido significativamente menos atención teórica. Los autores pretenden cerrar esta brecha analizando el S-SEG bajo supuestos mínimos y comparando su comportamiento fundamentalmente contra el I-SEG.

Metodología y Marco Teórico

El análisis se basa en supuestos estándar en optimización estocástica, incluyendo:

• Monotonía de la Media y Lipschitzianidad: El operador esperado $F$ es monótono y Lipschitz.
• Unbiasedness (No sesgo): Los operadores estocásticos son estimadores insesgados de la media.
• Límites de Varianza: El artículo utiliza tanto el supuesto estándar de Varianza Acotada (Supuesto 2.5) como el supuesto más general de Varianza Generalizada (Supuesto 2.6), que permite que la varianza crezca linealmente con la distancia a la solución.
• Lipschitzianidad Uniforme: Un supuesto más fuerte (Supuesto 2.3) que requiere que cada operador de muestra $F(\cdot; \xi_i)$ sea Lipschitz, lo cual es distinto de que el operador de la media sea Lipschitz.

Los autores emplean una combinación de análisis de alta probabilidad, teoremas de convergencia de martingalas (específicamente el teorema de los dos series de Kolmogorov) y la construcción de contraejemplos específicos para establecer tanto garantías de convergencia positivas como resultados de imposibilidad negativos. Un desafío técnico clave abordado es el término de sesgo $\langle F(\hat{x}_k; \xi_{i_k}) - F(\hat{x}_k), x_k \rangle$, el cual se anula en esperanza para I-SEG debido a la independencia, pero permanece distinto de cero para S-SEG.

Principales Contribuciones y Resultados

1. Sensibilidad a la Lipschitzianidad por Muestra

El artículo demuestra que el S-SEG es sensible a las propiedades Lipschitz de los operadores de muestra individuales, no solo a las del operador de la media.

• Resultado: Incluso en dominios compactos con varianza acotada y una solución única, el S-SEG puede fallar en converger si los operadores de muestra no son uniformemente Lipschitz (Supuesto 2.3).
• Evidencia: Se construye un contraejemplo (Proposición 3.2) donde el operador de la media es monótono y Lipschitz, pero los operadores de muestra presentan discontinuidades de salto. En este escenario, las iteraciones de S-SEG permanecen atrapadas en una región separada de la solución, mientras que el I-SEG convergería. Esto establece que el Supuesto 2.3 es un requisito sustantivo para S-SEG, no meramente un artefacto de la prueba.

2. Convergencia de la Función de Brecha de Alta Probabilidad en Dominios No Acotados

Para dominios posiblemente no acotados, los autores establecen garantías de convergencia de alta probabilidad para ambos, I-SEG y S-SEG, bajo tamaños de paso sumables al cuadrado ($\sum \gamma_k^2 < \infty$).

• Resultado: Bajo el supuesto de Varianza Generalizada (para I-SEG) y Lipschitzianidad Uniforme (para S-SEG), ambos métodos satisfacen un límite de la función de brecha esperada condicional en un evento de alta probabilidad donde las iteraciones permanecen acotadas.
• Imposibilidad: El artículo demuestra que estas garantías de alta probabilidad son esencialmente ajustadas.
  • Sin tamaños de paso sumables al cuadrado, tanto I-SEG como S-SEG pueden divergir casi seguramente (Teoremas 3.9 y 3.10).
  • Incluso con tamaños de paso sumables al cuadrado, las iteraciones pueden escapar de cualquier región acotada preespecificada con probabilidad positiva. Por consiguiente, no se puede garantizar la convergencia de la función de brecha esperada incondicional sobre una región acotada fija (Teorema 3.12). La distribución límite de las iteraciones tiene soporte no acotado.

3. Separación Fundamental en la Convergencia de la Última Iteración

El artículo investiga la convergencia de la última iteración casi segura ($x_k \to x^*$).

• Cuasi-Estricta Monotonía: Bajo el supuesto adicional de cuasi-estricta monotonía (Supuesto 2.8), tanto I-SEG como S-SEG convergen casi seguramente a una solución con tamaños de paso sumables al cuadrado (Teorema 4.1).
• Fallo de DSEG para S-SEG: Un hallazgo crítico es que la regla de Extragradiente de Tamaño de Paso Doble (DSEG), que garantiza la convergencia de la última iteración casi segura para I-SEG en VIPs monótonos generales (sin cuasi-estricta monotonía), falla para S-SEG.
• Evidencia: Los autores construyen un VIP monótono estocástico con una solución única donde el S-SEG, incluso utilizando tamaños de paso DSEG, diverge casi seguramente. Tanto la última iteración como el promedio ponderado de las iteraciones divergen al infinito (Teorema 4.2). Esto indica que la independencia de las muestras es un mecanismo central para la convergencia de DSEG, no solo una conveniencia de la prueba.

Significado y Reivindicaciones

El artículo pretende delinear la frontera precisa entre la convergencia y el fallo para las dos principales variantes de SEG. Sus contribuciones primarias son:

1. Clarificación de los Requisitos de S-SEG: Establece que el S-SEG requiere supuestos más fuertes (Lipschitzianidad uniforme de las muestras) que el I-SEG, y que la varianza acotada por sí sola es insuficiente para la convergencia en conjuntos compactos.
2. Ajuste de los Límites de Alta Probabilidad: Demuestra que, para dominios no acotados, la convergencia de alta probabilidad es la garantía más fuerte posible para SEG con tamaños de paso simétricos, ya que las garantías incondicionales son generalmente imposibles debido al soporte no acotado de la distribución límite.
3. Divergencia Fundamental de las Variantes: Prueba que S-SEG e I-SEG no son intercambiables. Específicamente, la estrategia de tamaño de paso DSEG, efectiva para I-SEG, no puede rescatar al S-SEG de la divergencia en ausencia de cuasi-estricta monotonía. Esto resalta que la estrategia de muestreo (independiente frente a única) altera fundamentalmente la dinámica y las propiedades de convergencia del algoritmo.

Los autores concluyen que, si bien el SEG es un algoritmo fundacional, la comprensión teórica del S-SEG está rezagada respecto al I-SEG, y ambas variantes exhiben comportamientos distintos que deben ser considerados en el diseño y análisis de algoritmos. El trabajo no propone nuevos algoritmos, sino que proporciona una caracterización rigurosa de los existentes, identificando dónde las herramientas teóricas actuales tienen éxito y dónde fallan fundamentalmente.