Resumen Técnico: Métodos de Factibilidad Aleatorizada para Optimización Restringida con Tamaños de Paso Adaptativos

Formulación del Problema

El artículo aborda el problema de optimización restringida:
$$\min_{x} f(x) \quad \text{sujeto a} \quad x \in X \cap Y$$
donde $Y \subseteq \mathbb{R}^n$ es un conjunto cerrado y convexo que es "fácil de proyectar" (por ejemplo, bolas o cajas), y $X$ se define como la intersección de $m$ conjuntos de nivel inferior de funciones convexas:
$$X := \bigcap_{i=1}^m \{x \in \mathbb{R}^n \mid g_i(x) \leq 0\}$$
El desafío principal surge cuando $m$ es grande y proyectar sobre la intersección $X$ es computacionalmente intratable. Los autores consideran dos regímenes distintos para la función objetivo $f$:

1. Fuertemente convexa y Lipschitz-suave: $f$ tiene un minimizador único y gradientes suaves.
2. Convexa y posiblemente no suave: $f$ puede carecer de suavidad y de fuerte convexidad.

El objetivo es desarrollar algoritmos que minimicen $f$ asegurando la factibilidad con respecto a $X$ sin requerir una proyección completa sobre $X$ en cada iteración.

Metodología

El enfoque propuesto desacopla la minimización del objetivo de la satisfacción de las restricciones mediante un marco iterativo de dos pasos:

1. Actualizaciones de Factibilidad Aleatorizada (Algoritmo 1)

Para manejar las restricciones complejas $X$, los autores emplean un algoritmo de factibilidad aleatorizada basado en los pasos de Polyak. En lugar de proyectar sobre el conjunto completo $X$, el algoritmo:

• Muestrea un único índice de restricción $\omega_k$ uniformemente de $\{1, \dots, m\}$.
• Calcula un subgradiente de la función de violación de la restricción muestreada $g^+_{\omega_k}(x) = \max\{0, g_{\omega_k}(x)\}$.
• Realiza un paso de subgradiente con un tamaño de paso de Polyak escalado por un parámetro $\beta \in (0, 2)$.
• Proyecta el resultado de vuelta al conjunto "fácil" $Y$.
• Repite este proceso $N_k$ veces por cada iteración externa, donde $N_k$ puede ser determinista o aleatorio.

La salida de este bucle interno, $x_k$, sirve como una actualización de factibilidad que reduce la distancia al conjunto factible $X \cap Y$ de forma geométrica.

2. Minimización del Objetivo con Pasos Adaptativos

El bucle externo minimiza $f(x)$ utilizando la salida de las actualizaciones de factibilidad. El artículo propone dos estrategias específicas basadas en las propiedades de $f$:

• Caso (i): Fuertemente Convexa y Suave (Algoritmo 2)
  El método combina pasos de descenso de gradiente con las actualizaciones de factibilidad aleatorizadas. Los autores introducen un esquema de tamaño de paso adaptativo que no requiere el conocimiento previo de la constante de fuerte convexidad $\mu$ o la constante de Lipschitz $L$. El tamaño del paso se ajusta basándose en la norma del gradiente y una tolerancia objetivo $\epsilon$.

• Caso (ii): Convexa y No Suave (Algoritmos 3 y 4)
  Para objetivos no suaves, el artículo introduce un esquema adaptativo totalmente libre de parámetros basado en Distancia sobre Subgradientes Ponderados (DoWS), una variante del método DoWG.

  • Algoritmo 3 (DoWS): Asume que el conjunto factible $Y$ es acotado. Rastrea la distancia máxima de las iteraciones desde un punto inicial y acumula normas de subgradientes ponderados para determinar el tamaño del paso.
  • Algoritmo 4 (T-DoWS): Una variante "domesticada" (tamed) diseñada para conjuntos no acotados (por ejemplo, $Y = \mathbb{R}^n$). Modifica el escalamiento del tamaño del paso para asegurar que las iteraciones permanezcan acotadas bajo un supuesto de subnivel de $f$, eliminando la necesidad de la acotación a priori de $Y$.

Principales Contribuciones

1. Conexión Teórica de los Límites de Error y Multiplicadores Duales:
   Los autores establecen una conexión entre los límites de error globales y los multiplicadores duales de Lagrange bajo la condición de Slater Fuerte. Demuestran que existe un límite superior uniforme para los multiplicadores duales sin asumir la compacidad de $Y$, un resultado derivado de trabajos previos (Lewis & Pang, 1998; Bertsekas, 1999; Mangasarian, 1998) pero vinculado explícitamente aquí a la estructura de restricción específica.

2. Convergencia Lineal para Problemas Fuertemente Convexos:
   Para objetivos fuertemente convexos y suaves, el artículo demuestra la convergencia lineal en esperanza de los valores de la función objetivo hacia cualquier tolerancia prescrita $\epsilon$. Esto se logra mediante tamaños de paso adaptativos y una condición específica sobre el número de muestras de factibilidad $N_k$. A diferencia de trabajos anteriores, este resultado no asume a priori gradientes de las funciones de restricción acotados, sino que demuestra que están acotados casi seguramente.

3. Métodos Totalmente Libres de Parámetros para Problemas No Suaves:
   El artículo presenta el primer método totalmente libre de parámetros para resolver el problema (P) sin proyecciones, combinando DoWS con actualizaciones de factibilidad aleatorizadas.

   • Logra una tasa de peor caso de $O(1/\sqrt{T})$ en esperanza para objetivos convexos, posiblemente no suaves.
   • Introduce T-DoWS (Algoritmo 4), que garantiza iteraciones acotadas y tasas de convergencia óptimas incluso cuando el conjunto de restricciones $Y$ es no acotado, siempre que los conjuntos de subnivel de $f$ sean acotados.

4. Análisis de Estrategias de Muestreo Aleatorio:
   Los autores analizan el impacto del número de muestras de factibilidad $N_k$ por iteración. Muestran que la infeactibilidad de las iteraciones disminuye geométricamente casi seguramente. Proporcionan orientación teórica para elegir la distribución de $N_k$ (por ejemplo, Poisson, Binomial o crecimiento determinista) para lograr tasas de convergencia óptimas, demostando que las tasas óptimas pueden alcanzarse con cronogramas de crecimiento de tamaño de muestra específicos.

Resultados y Evaluación Empírica

Garantías Teóricas

• Caso Fuertemente Convexo: El algoritmo alcanza una precisión de $\epsilon$ en $O(\ln(1/\epsilon))$ iteraciones. La brecha de infeactibilidad decae geométricamente con el número de muestras $N_k$.
• Caso Convexo No Suave: Las iteraciones promediadas logran un límite de error esperado de $O(1/\sqrt{T})$ (hasta factores logarítmicos dependiendo de la relación del diámetro del conjunto con la estimación inicial). El límite de infeactibilidad depende de la distribución de muestreo y disminuye a una tasa de $O(1/T)$ bajo condiciones de muestreo específicas.

Simulaciones

Los autores validan sus métodos en tres tipos de problemas:

1. Programación Cuadrática con Restricciones Cuadráticas (QCQP): Demuestra convergencia lineal para el caso fuertemente convexo y un rendimiento competitivo para el caso no suave frente a Arrow-Hurwicz, Alt-GDA y ACVI.
2. Máquinas de Vectores de Soporte (SVM): Muestra que sus métodos libres de parámetros convergen sin requerir validación cruzada para el ajuste del tamaño del paso, a diferencia de los métodos de primal-dual que sufren una alta carga computacional en entornos online.
3. Regresión Logística con Restricciones de Equidad de Grupo (Group Fairness): Ilustra la capacidad de manejar restricciones de equidad complejas (modeladas como intersecciones de conjuntos de nivel inferior) mientras se alcanza una violación de factibilidad de cero y se converge al valor óptimo del objetivo.

En todas las simulaciones, los algoritmos propuestos (Algoritmos 2, 3 y 4) demuestran eficiencia computacional, particularmente en escenarios con un gran número de restricciones donde la proyección completa es inviable. Los métodos superan o igualan a las líneas base de vanguardia (ACVI, Arrow-Hurwicz) evitando la necesidad de ajuste de hiperparámetros o la resolución de subproblemas en cada iteración.

Significado y Reivindicaciones

El artículo afirma avanzar en el campo de la optimización restringida proporcionando algoritmos computacionalmente eficientes, teóricamente fundamentados y totalmente libres de parámetros para problemas con un gran número de restricciones.

• Novedad: Los autores afirman que esta es la primera vez que se estudia la combinación de DoWG (o su variante domesticada) con actualizaciones de factibilidad aleatorizada para la optimización sin proyecciones.
• Robustez: Los métodos no requieren el conocimiento de parámetros específicos del problema (constantes de fuerte convexidad, constantes de Lipschitz o valores óptimos), lo que los hace adecuados para aplicaciones prácticas donde dicha información no está disponible.
• Escalabilidad: Al utilizar actualizaciones de factibilidad aleatorizadas, los algoritmos evitan el cuello de botella computacional de proyectar sobre la intersección de muchas restricciones, escalando eficazmente a problemas de alta dimensión con miles de restricciones.

El trabajo cierra la brecha entre los métodos de factibilidad aleatorizada y los métodos de gradiente adaptativos, ofreciendo un marco unificado que se adapta tanto a objetivos suaves como no suaves, asegurando al mismo tiempo la factibilidad con un decaimiento geométrico.