Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

Resumen Técnico: Aproximación Estocástica de Dos Escalas Temporales No Expansiva

Planteamiento del Problema
El artículo investiga las tasas de convergencia de la aproximación estocástica de dos escalas temporales (TTSA, por sus siglas en inglés) en un régimen donde el mapa rápido es contractivo, pero el mapa lento reducido es solo no expansivo. Este entorno surge en la optimización minimax, las desigualdades variacionales y la aproximación estocástica con restricciones. A diferencia de la TTSA contractiva, donde la variable lenta converge a un equilibrio único, el caso no expansivo presenta un conjunto de puntos fijos potencialmente no unívoco. En consecuencia, la métrica de rendimiento natural es el residuo del punto fijo $p(y) = h(y) - y$ en lugar de la distancia a un punto específico.

Trabajos previos establecieron una tasa de residuo de media cuadrática de último iterado de $O(k^{-1/4+\epsilon})$ para este régimen. El artículo tiene como objetivo explicar el origen teórico de este exponente $1/4$ y determinar si las modificaciones algorítmicas pueden mejorarlo.

Metodología y Marco Teórico
Los autores descomponen la dinámica del error en dos componentes distintos: la convergencia intrínseca de la recursión no expansiva lenta y la filtración de los errores de seguimiento rápido hacia el oráculo lento.

1. Agudeza de la Barrera del Programador Fijo de KM:
   El artículo establece primero que la escala de residuo clásica de Krasnoselskii–Mann (KM), definida por el inverso de la suma $\sum \beta_i(1-\beta_i)$, es aguda para cualquier programación de paso lento $(\beta_k)$ fija. Utilizando un ejemplo de rotación planar, los autores demuestran un límite inferior de horizonte finito que muestra que ninguna actualización KM sin regularizar puede lograr una tasa de decaimiento de residuo peor que esta escala para una programación dada. Esto implica que mejorar la tasa requiere cambiar el régimen algorítmico o la estructura del oráculo, no simplemente refinar el análisis de la actualización KM estándar.

2. Diagnóstico del Exponente $1/4$:
   El artículo identifica la "filtración de primer orden del colector rápido" como la obstrucción principal. En la TTSA pura, el oráculo lento evalúa el mapa en la iteración rápida actual $X_k$ en lugar del equilibrio verdadero $x^*(Y_k)$. Debido a la continuidad de Lipschitz del mapa lento en la coordenada rápida, el error $g(X_k, Y_k) - h(Y_k)$ es de primer orden respecto al error de seguimiento $\|X_k - x^*(Y_k)\|$.
   El error de seguimiento está gobernado por un equilibrio entre la varianza estocástica rápida ($\alpha_k$) y el retraso determinista detrás del objetivo móvil ($(\beta_k/\alpha_k)^2$). Incluso bajo la condición de separación estándar $\beta_k^2/\alpha_k^3 \lesssim 1$, la combinación de la escala KM aguda y esta filtración de primer orden produce un total de complejidad de muestra de $T^{-1/4+o(1)}$. Violar la condición de separación no mejora la tasa; simplemente desplaza el cuello de botella de la varianza estadística al retraso del objetivo móvil, el cual sigue entrando como una perturbación de primer orden.

3. Corrección de Sesgo mediante Precondicionamiento de Residuo:
   Para superar la filtración de primer orden, los autores introducen un oráculo lento precondicionado por residuo. Al utilizar las derivadas de los mapas rápido y lento, construyen un término de corrección que cancela la dependencia lineal de la filtración del seguimiento rápido.
   Específicamente, si $A(y) = I - \nabla_x f(x^*(y), y)$ y $C(y) = \nabla_x g(x^*(y), y)$, el precondicionador es $P^*(y) = C(y)A(y)^{-1}$. El oráculo corregido se define como:
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   La expansión de Taylor muestra que esta corrección reduce el sesgo del oráculo lento de primer orden ($O(\|e\|$) a segundo orden ($O(\|e\|^2)$), donde $e$ es el error de seguimiento rápido.

Contribuciones Clave y Resultados

El artículo presenta tres resultados teóricos principales, progresando desde el diagnóstico del método bruto hasta algoritmos optimizados bajo supuestos de oráculo estructurado.

1. Límite Inferior de Programación Fija:
   Los autores demuestran que para cualquier programación de paso lento fija, el residuo de media cuadrática de la iteración KM no regularizada no puede mejorar uniformemente la escala $(\sum \beta_i(1-\beta_i))^{-1}$. Esto confirma que el exponente $1/4$ en el trabajo previo no es un artefacto de un análisis laxo, sino una consecuencia de la escala KM aguda combinada con la filtración de primer orden.

2. Algoritmo de Precondicionamiento de Residuo Anidado ($T^{-1/3}$):
   En un marco de Tikhonov-KM anidado, los autores aplican el precondicionamiento de residuo.

• Sin corregir: El método anidado con un oráculo bruto logra una tasa de muestra total de $T^{-1/4+o(1)}$.
• Corregido: Al usar el oráculo precondicionado, el sesgo al cuadrado del oráculo lento se convierte en $O(n^{-2})$ (donde $n$ es el número de muestras internas) en lugar de $O(n^{-1})$. Este cambio estructural mejora la complejidad de muestra total a $T^{-1/3+o(1)}$.
• Nota: Este resultado asume el acceso al precondicionador exacto $P^*(y)$ o a un estimador que satisfaga condiciones específicas de precisión de producto.

3. Precondicionador Aprendido de Bucle Único ($T^{-1/2}$):
   Para evitar el costo repetido de las resoluciones de bucle interno en el método anidado, los autores proponen un algoritmo de bucle único que rastrea el equilibrio rápido, la variable lenta y la matriz del precondicionador de forma online.

• Este método mantiene estimaciones continuas de $X_k$, $Y_k$ y $P_k$ utilizando observaciones de derivadas estocásticas.
• Bajo supuestos de suavidad (diferenciabilidad de los mapas y acceso a oráculos de derivadas), este enfoque logra una tasa de muestra total de $T^{-1/2+o(1)}$ con $O(1)$ muestras primitivas por iteración.
• Esta mejora depende de la capacidad de aprender el precondicionador de filtración de forma online, amortizando efectivamente el costo de la resolución interna.

Significancia y Reivindicaciones
El artículo afirma proporcionar una explicación teórica completa para el exponente $1/4$ en la TTSA no expansiva, atribuyéndolo a la interacción entre la escala de residuo KM aguda y la filtración de primer orden del colector rápido. La contribución principal es demostrar que esta barrera no es fundamental para la clase de problemas, sino específica de la estructura del oráculo "bruto".

Al introducir un oráculo precondicionado por residuo, los autores muestran que la filtración puede reducirse a segundo orden, mejorando así las tasas de convergencia. El resultado $T^{-1/3}$ sirve como un certificado de que la corrección de sesgo es efectiva, mientras que el resultado $T^{-1/2}$ demuestra que estas ganancias pueden realizarse en un entorno de bucle único si la información de la derivada está disponible. Los autores enmarcan explícitamente estos resultados como logros de "oráculo estructurado", señalando que dependen de la diferenciabilidad y el acceso a la información relacionada con la Jacobiana, lo que los distingue de los métodos de punto fijo no expansivos de caja negra. El trabajo no pretende resolver el problema para oráculos de caja negra generales, sino identificar la modificación estructural específica (cancelación de sesgo) necesaria para acelerar la convergencia en presencia de suavidad.