Stochastic Adaptive Gradient Descent Without Descent

Planteamiento del Problema
El artículo aborda el problema de optimización convexa estocástica:
$$\min_{x \in \mathbb{R}^d} f(x) = \min_{x \in \mathbb{R}^d} \mathbb{E}[f_\xi(x)]$$
donde $f$ es una función convexa, diferenciable y acotada inferiormente. El objetivo es encontrar un minimizador $x^\star$ utilizando un oráculo de gradiente estocástico $\nabla f_{\xi_k}$ sin requerir el ajuste cuidadoso de los hiperparámetros, específicamente el paso inicial $\lambda_0$. Mientras que el SGD (Descenso de Gradiente Estocástico) estándar requiere ajustar $\lambda_0$ para equilibrar la velocidad de convergencia y la estabilidad, y los métodos adaptativos existentes (como los de Malitsky y Mishchenko [2020]) a menudo retienen una dependencia de un parámetro ajustable $\alpha$ en el entorno estocástico, este trabajo busca un enfoque "libre de ajuste" (tuning-free) que se adapte a la geometría local de la función objetivo utilizando únicamente llamadas al oráculo de primer orden.

Metodología
Los autores proponen AdaSGD, una adaptación estocástica del método "Adaptive Gradient Descent Without Descent" (AdaGD). La innovación central reside en la regla de actualización del tamaño del paso, la cual evita el hiperparámetro $\alpha$ requerido por las adaptaciones estocásticas previas.

El algoritmo sigue la recursión estocástica estándar $x_{k+1} = x_k - \lambda_k \nabla f_{\xi_k}(x_k)$. El tamaño del paso $\lambda_k$ se actualiza basándose en la geometría local de la función. Una distincción clave de la AdaGD determinista y de los intentos estocásticos previos es la evaluación de la diferencia de gradientes. En lugar de utilizar el lote actual $\xi_k$ para ambos puntos (lo que introduciría sesgo o requeriría un segundo lote independiente $\zeta_k$), el método evalúa la diferencia de gradientes utilizando la variable aleatoria previa $\xi_{k-1}$:
$$\hat{L}_{k-1} = \frac{\|\nabla f_{\xi_{k-1}}(x_k) - \nabla f_{\xi_{k-1}}(x_{k-1})\|}{\|x_k - x_{k-1}\|}$$
Esto permite que el tamaño del paso se defina sin un parámetro de escala externo. El artículo propone tres variantes (V-I, V-II, V-III) para $k \ge 2$:
$$\lambda_k = \min \left( \frac{c_k}{2\sqrt{2}\hat{L}_{k-1}}, \frac{\lambda_{k-1}}{\sqrt{1 + \theta_{k-1}}} \right)$$
donde $\theta_{k-1} = \lambda_{k-1}/\lambda_{k-2}$ y $c_k$ es un factor de decaimiento (específicamente $c_k = 1$ para V-I, y $c_k = k^{1/2+\delta}$ para V-II y V-III con $0 < \delta < 1/2$). Se recomienda la V-III ya que proporciona las garantías teóricas más sólidas.

Análisis Teórico
El análisis de convergencia se basa en la construcción de una secuencia de Lyapunov $(T_k)$, inspirada en Malitsky y Mishchenko [2020] pero adaptada para el entorno estocástico. La secuencia se define como:
$$T_k = \|x_{k+1} - x^\star\|^2 + 2(\lambda_k(1+\theta_k))(f(x_k) - f^\star) + \frac{\|x_{k+1} - x_k\|^2}{2}$$
Los autores demuestran que bajo supuestos específicos (estructura de suma finita con gradientes Lipschitz, o iterados acotados), la secuencia $(T_k)$ converge casi seguramente.

• Convergencia Casi Segura: El Teorema 3.2 establece que si los tamaños de paso son sumables al cuadrado ($\sum \lambda_k^2 < \infty$), la secuencia de Lyapunov converge. Esta condición se muestra válida en casos de convexidad fuerte, regresión lineal y sumas de funciones de cresta (ridge functions).
• Tasas de Convergencia: Para funciones con convexidad fuerte (Caso-1), el Teorema 3.4 deriva una tasa de convergencia de $O(1/k^{1/2+\delta})$ para el error esperado. Crucialmente, los factores exponenciales que gobiernan el comportamiento transitorio dependen de la razón $L^2/\mu^2$ (donde $L$ es la constante de suavidad y $\mu$ es el parámetro de convexidad fuerte) en lugar del tamaño de paso inicial $\lambda_0$. Esto contrasta con el SGD vanilla, donde el tamaño de paso inicial puede causar un crecimiento exponencial en el límite de error antes de la convergencia.

Contribuciones Clave

1. Adaptación Estocástica Libre de Ajuste: El artículo introduce una estrategia de tamaño de paso estocástico que elimina la necesidad de ajustar el parámetro $\alpha$ (o $\lambda_0$) requerido en la versión estocástica de AdaGD de Malitsky y Mishchenko [2020].
2. Garantías Teóricas: Los autores proporcionan pruebas de convergencia rigurosas y tasas bajo supuestos estándar (convexidad fuerte, gradientes Lipschitz) sin requerir conocimiento global de $L$ o $\mu$.
3. Robustez a la Inicialización: El método está diseñado de tal manera que elegir un tamaño de paso inicial pequeño es siempre seguro, evitando los problemas de sensibilidad comunes en otros métodos adaptativos.

Resultados Experimentales
Se realizaron experimentos numéricos en seis problemas de optimización convexa estocástica (regresión lineal/de cresta/logística/Poisson) utilizando datos sintéticos y reales (Diabetes, 2moons, w8a).

• Sensibilidad a $\lambda_0$: Los resultados demuestran que AdaSGD es significativamente menos sensible a la elección del tamaño de paso inicial $\lambda_0$ en comparación con el SGD vanilla, el SGD con decaimiento, Adagrad y el AdaGD-MM estocástico. Mientras que otros métodos requieren una búsqueda exhaustiva en una cuadrícula densa para encontrar un $\lambda_0$ óptimo, AdaSGD funciona consistentemente bien con un valor pequeño fijo (por ejemplo, $\lambda_0 = 10^{-3}$).
• Desempeño: En términos de desempeño de minimización (brecha de optimalidad), AdaSGD (específicamente las variantes V-II y V-III) logra resultados comparables a las líneas base optimamente ajustadas. Los autores señalan que, aunque la V-I a veces presenta dificultades con oscilaciones debido al ruido, el decaimiento introducido en V-II y V-III estabiliza el método.
• Costo: El método requiere una evaluación de gradiente estocástico adicional por iteración (para calcular $\nabla f_{\xi_{k-1}}(x_k)$), pero los autores argumentan que este costo se compensa con la eliminación de la búsqueda en cuadrícula requerida para el ajuste de hiperparámetros.

Significancia y Reivindicaciones
El artículo afirma que AdaSGD transfiere con éxito los beneficios del "Adaptive Gradient Descent Without Descent" determinista al entorno estocástico, una transición que intentos previos no lograron lograr sin reintroducir el ajuste de hiperparámetros. La contribución principal es un método que es "libre de ajuste" en la práctica: permite a los profesionales utilizar un tamaño de paso inicial pequeño y fijo sin sacrificar las tasas de convergencia o la estabilidad. Los autores enfatizan que, si bien el método no es estrictamente "libre de parámetros" (ya que depende de $\lambda_0$ para el valor inicial de la función de Lyapunov), la dependencia es lo suficientemente débil como para que valores pequeños sean universalmente efectivos, lo que hace que el método sea robusto y práctico para la optimización estocástica sin necesidad de una extensa búsqueda de hiperparámetros. El trabajo se mantiene enfocado en entornos convexos, señalando las extensiones no convexas como un desafío significativo para el futuro debido a la dependencia de las desigualdades de convexidad en la derivación.