Resumen Técnico: Métodos de Primer Orden Basados en Penalización para Optimización Bilevel con Estructuras Minimax y Problemas de Nivel Inferior Restringidos

Formulación del Problema

Este artículo aborda una clase de problemas de optimización bilevel donde tanto el problema de nivel superior como el de nivel inferior exhiben estructuras minimax. La formulación general se define como:
$$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$$
donde $(y_1, y_2)$ representa un punto de silla de la función de nivel inferior $\tilde{f}$. Los autores asumen propiedades estructurales específicas: $f$ y $\tilde{f}$ pueden descomponerse en componentes suaves y funciones convexas propias cerradas, con propiedades específicas de convexidad/concavidad respecto a sus variables respectivas (por ejemplo, $\tilde{f}$ es convexa en $y_1$ y cóncava en $y_2$).

Un subconjunto significativo de este trabajo se centra en problemas bilevel donde el nivel inferior es un problema de minimización convexa con restricciones de desigualdad no lineales convexas:
$$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$$
Bajo la condición de Slater, este problema restringido se reformula como un caso especial del marco general bilevel minimax mediante dualidad lagrangiana.

La literatura existente se centra en gran medida en la optimización bilevel donde el nivel inferior es una minimización de un solo objetivo (a menudo fuertemente convexa). Los métodos que dependen de hipergradientes o diferenciación implícita suelen fallar cuando el nivel inferior es meramente convexo, no convexo o posee una estructura minimax. Este trabajo busca llenar esa brecha desarrollando métodos de primer orden para el escenario de nivel inferior minimax sin requerir convexidad fuerte.

Metodología

El enfoque propuesto utiliza una reformulación de función de valor con penalización. El problema bilevel restringido se transforma en un problema minimax sin restricciones (o con restricciones más simples) introduciendo un parámetro de penalización $\rho$.

Entorno Determinista

1. Reformulación con Penalización: El problema original se reformula en un problema minimax de un solo nivel:
   $$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$$
   donde $P_\rho$ incorpora la función objetivo y el término de penalización $\rho(p(x_1, y_1) - d(x_1, y_2))$, que representa la brecha de dualidad del problema de nivel inferior.
2. Algoritmo: Los autores proponen un método de punto proximal inexacto. El bucle externo actualiza las variables primal-dual resolviendo una secuencia de subproblemas fuertemente convexos-fuertemente cóncavos (SCSC).
3. Solucionador de Subproblemas: Cada subproblema se resuelve utilizando un método óptimo de primer orden (específicamente, una variante del método de Lu y Mei [52] o Kovalev y Gasnikov [37]), denotado como OptFOM.
4. Complejidad: El método encuentra un punto KKT $\epsilon$-aproximado con una complejidad de oráculo de $\tilde{O}(\epsilon^{-4})$.

Entorno Estocástico

Cuando solo están disponibles oráculos de gradiente estocástico para los componentes suaves:

1. Algoritmo: El método de punto proximal determinista se adapta para utilizar un Método Primal-Dual Acelerado Estocástico (SAPD) (específicamente SAPD+ de Zhang et al. [75]) para resolver los subproblemas internos.
2. Convergencia: El método encuentra un punto "casi" KKT $\epsilon$-aproximado (donde la solución está dentro de una distancia $\epsilon$ de un punto KKT $\epsilon$-aproximado exacto) con una complejidad de oráculo estocástico de $\tilde{O}(\epsilon^{-9})$.

Aplicación a Problemas de Nivel Inferior Restringidos

Para el caso específico de optimización bilevel con un nivel inferior convexo restringido (Problema 4), los autores muestran que, bajo la condición de Slater, los multiplicadores de Lagrange están acotados dentro de un intervalo $[0, B]^l$. Esto permite reformular el problema restringido como el problema bilevel minimax general (Problema 1) introduciendo las variables duales como variables de optimización explícitas con restricciones de intervalo. Esta reformulación evita la necesidad de un parámetro de penalización interno, lo que conduce a límites de complejidad mejorados en comparación con trabajos anteriores.

Contribuciones Clave

1. Primeros Resultados de Complejidad para Minimax Bilevel: El artículo establece los primeros límites de complejidad para métodos de primer orden deterministas y estocásticos para optimización bilevel donde el nivel inferior es un problema minimax.
   • Complejidad determinista: $\tilde{O}(\epsilon^{-4})$.
   • Complejidad estocástica: $\tilde{O}(\epsilon^{-9})$.
2. Límites Mejorados para Problemas Bilevel Restringidos: Al reformular problemas bilevel con niveles inferiores convexos restringidos como instancias del marco minimax propuesto, los autores logran una complejidad de $\tilde{O}(\epsilon^{-4})$. Esto mejora los resultados existentes para niveles inferiores meramente convexos ($\tilde{O}(\epsilon^{-7})$ en [53]) y niveles inferiores fuertemente convexos ($\tilde{O}(\epsilon^{-6})$ en [51]). La mejora proviene de evitar el uso de un segundo parámetro de penalización para las restricciones internas, lo que anteriormente conducía a parámetros de suavidad más altos.
3. Validación Empírica:
   • Datos Sintéticos: En problemas bilevel lineales restringidos, el método propuesto demuestra velocidades de convergencia competitivas frente a métodos basados en penalización existentes (FOP y SMO), especialmente cuando la constante de Lipschitz se ajusta.
   • Aplicación del Mundo Real: El método se aplica al ajuste de hiperparámetros para Optimización Robusta Distribucionalmente (DRO) en aprendizaje profundo. En los conjuntos de datos CelebA y Waterbirds, el enfoque bilevel estocástico propuesto supera a los métodos DRO estándar en términos de precisión del grupo peor, manteniendo una precisión promedio comparable.

Resultados y Significado

El artículo afirma que el marco propuesto basado en penalización proporciona un enfoque unificado para manejar problemas bilevel con estructuras minimax, un escenario previamente inexplorado en la literatura en lo que respecta a la complejidad de primer orden.

• Significado Teórico: El trabajo cierra la brecha entre la optimización bilevel y la optimización minimax, proporcionando garantías rigurosas de convergencia sin depender de suposiciones de convexidad fuerte para el problema de nivel inferior. La reducción de la complejidad de $\tilde{O}(\epsilon^{-7})$ a $\tilde{O}(\epsilon^{-4})$ para niveles inferiores restringidos se presenta como un avance teórico significativo.
• Significado Práctico: La aplicación a DRO demuestra la utilidad del método en escenarios de aprendizaje automático que involucran desplazamientos de distribución y equidad grupal. Los resultados en los conjuntos de datos CelebA y Waterbirds muestran que el método puede manejar eficazmente el desafío de optimización del "grupo peor", logrando una mayor precisión del grupo peor que los métodos DRO de referencia.

Los autores reconocen limitaciones, incluida la necesidad de dominios factibles compactos, el uso de un espacio elevado para definiciones KKT y la alta complejidad del caso estocástico ($\tilde{O}(\epsilon^{-9})$), señalando que las técnicas de reducción de varianza podrían ser una dirección para trabajos futuros.