Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

Resumen Técnico: Optimización Composicional Estocástica mediante Frank–Wolfe de Momento Híbrido

Formulación del Problema
Este trabajo aborda el problema de optimización composicional estocástica de minimizar objetivos de la forma:
$$\min_{x \in X} \phi(x) := F(f(x), x)$$
donde $X \subset \mathbb{R}^d$ es un conjunto convexo y compacto, $f: X \to \mathbb{R}^n$ es una aplicación interna accesible únicamente mediante consultas estocásticas ruidosas ($f(x) = \mathbb{E}_\xi[\tilde{f}(x; \xi)]$), y $F: \mathbb{R}^n \times X \to \mathbb{R}$ es una función externa determinista.

El desafío principal en el entorno estocástico es que los estimadores de inserción directa son sesgados debido a la desigualdad de Jensen ($\mathbb{E}[F(\tilde{f}(x; \xi), x)] \neq F(\mathbb{E}[\tilde{f}(x; \xi)], x)$). Aunque los métodos estocásticos existentes (por ejemplo, SCGD, NASA, SCSC) abordan este sesgo utilizando rastreadores basados en momento y la regla de la cadena, requieren fundamentalmente que la función externa $F$ sea continuamente diferenciable. Esta suposición excluye muchas aplicaciones críticas que involucran funciones externas no suaves, como el máximo robusto de pérdidas, el Valor en Riesgo Condicional (CVaR) y regularizadores de norma. Además, los métodos estocásticos existentes sin proyección (por ejemplo, LiNASA+ICG) también dependen de la suavidad de $F$.

Metodología
Los autores proponen el algoritmo Frank–Wolfe Estocástico de Momento Híbrido, el primer método sin proyección para problemas totalmente compuestos que maneja funciones externas no suaves. La innovación central reside en reemplazar la actualización basada en gradiente estándar con un Oráculo de Minimización Lineal Generalizado (GLMO) que opera sobre un sustituto afín estocástico.

El algoritmo mantiene dos rastreadores estocásticos en cada iteración $k$:

1. Rastreador Jacobiano ($V_k$): Un estimador de momento estilo Polyak para el Jacobiano $\nabla f(y_k)$.
2. Rastreador de Función ($z_k$): Un estimador para el valor de la función $f(y_k)$.

El algoritmo ofrece dos variantes para el rastreador de función para equilibrar el uso de memoria y las suposiciones:

• Variante I (Polyak): Sin memoria, pero requiere que la función interna $f$ sea Lipschitz continua.
• Variante II (Corregida por Taylor): Requiere almacenar la iteración anterior, pero elimina la suposición de Lipschitz en $f$ utilizando una extrapolación de Taylor de primer orden ($V_k(y_k - y_{k-1})$) para predecir el valor de la función, reduciendo el error de rastreo a un residuo cuadrático.

En cada paso, el algoritmo construye un sustituto afín $\tilde{l}_k(x) = z_k + V_k(x - y_k)$ y lo introduce en el GLMO:
$$x_{k+1} \in \arg\min_{x \in X} F(\tilde{l}_k(x), x)$$
Críticamente, el GLMO trata a $F$ como una caja negra, minimizándola directamente sobre la función interna linealizada sin requerir un subgradiente de $F$. Esto permite que el método maneje $F$ no suave (por ejemplo, normas $\ell_p$, funciones máximas) de manera eficiente, reduciendo a menudo la llamada al oráculo a un Programa Lineal (LP) o un Programa de Cono de Segundo Orden (SOCP).

Contribuciones Clave

1. Novedad Algorítmica: Introducción del primer algoritmo estocástico sin proyección para optimización totalmente compuesta con funciones externas no suaves.
2. Garantías Teóricas bajo Ruido de Cola Pesada: El análisis asume que el oráculo estocástico tiene momentos $r$-ésimos acotados ($r \in (1, 2]$), abarcando escenarios de ruido de cola pesada.
   • Caso No Convexo: El algoritmo logra una tasa de convergencia de $O(K^{-(r-1)/(3r-2)})$ en la brecha generalizada de Frank–Wolfe. Para varianza finita ($r=2$), esto produce $O(K^{-1/4})$, igualando el límite inferior minimax óptimo para métodos estocásticos sin proyección de muestra única bajo suavidad esperada.
   • Caso Convexo: Bajo suposiciones de convexidad conjunta, la tasa primal es $O(K^{-(r-1)/(2r-1)})$, recuperando $O(K^{-1/3})$ cuando $r=2$.
3. Interpolación Determinista: El algoritmo interpola sin problemas con el régimen determinista. Cuando el oráculo es exacto (ruido cero), establecer los parámetros de momento en 1 recupera el Método Básico determinista de Vladarean et al. [2023] con sus tasas óptimas ($O(1/K)$ para convexo, $\tilde{O}(1/\sqrt{K})$ para no convexo).
4. Aceleración: Bajo suposiciones de suavidad promedio $r$ más fuertes (o momentos de ruido de Hessiano acotados), el marco se integra con la reducción de varianza STORM o momento corregido por Hessiano para acelerar la tasa no convexa a $O(K^{-1/3})$ (en $r=2$).

Resultados y Experimentos
El artículo valida los hallazgos teóricos mediante experimentos numéricos en tres problemas del mundo real que presentan $F$ no suave y ruido de cola pesada:

• Regresión Escasa Minimax Robusta: Minimización de la pérdida del peor caso sobre subconjuntos de datos.
• Optimización de Carteras CVaR: Optimización aversa al riesgo sobre los rendimientos del S&P 500.
• Completado de Matrices Robusto: Uso de pérdida $\ell_1$ en el conjunto de datos MovieLens-100K.

Los resultados experimentales demuestran que el Frank–Wolfe composicional estocástico estándar (Vanilla SCFW) falla en converger debido al sesgo, y las variantes recortadas se estancan. En contraste, ambas variantes propuestas (Polyak y Taylor) logran la tasa de convergencia predicha de $O(K^{-1/4})$. Se muestra que la variante Taylor (Variante II) es teóricamente robusta incluso cuando la suposición de Lipschitz en $f$ no puede verificarse, aunque la variante Polyak se desempeña ligeramente mejor en regímenes donde la suposición se cumple.

Significado
El artículo afirma resolver un problema abierto identificado por Vladarean et al. [2023] con respecto a la extensión estocástica de los métodos sin proyección para la optimización totalmente compuesta. Al eliminar el requisito de suavidad en la función externa $F$, este trabajo permite la aplicación de la optimización sin proyección a una clase más amplia de problemas de aprendizaje aversos al riesgo, robustos y con restricciones de equidad. El método logra tasas de complejidad óptimas para métodos estocásticos sin proyección mientras mantiene la eficiencia computacional (requiriendo solo una llamada única al GLMO por iteración, a diferencia de métodos anteriores que requieren bucles internos costosos).