Resumo Técnico: Métodos de Primeira Ordem Baseados em Penalidade para Otimização Bi-nível com Estruturas Minimax e Problemas de Nível Inferior Constrained

Formulação do Problema

Este artigo aborda uma classe de problemas de otimização bi-nível onde tanto os problemas de nível superior quanto de nível inferior exibem estruturas minimax. A formulação geral é definida 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\}$$
onde $(y_1, y_2)$ representa um ponto de sela da função de nível inferior $\tilde{f}$. Os autores assumem propriedades estruturais específicas: $f$ e $\tilde{f}$ podem ser decompostos em componentes suaves e funções convexas próprias e fechadas, com propriedades específicas de convexidade/concavidade em relação às suas respectivas variáveis (por exemplo, $\tilde{f}$ é convexo em $y_1$ e côncavo em $y_2$).

Um subconjunto significativo deste trabalho foca em problemas bi-nível onde o nível inferior é um problema de minimização convexa com restrições de desigualdade não lineares 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\}$$
Sob a condição de Slater, este problema restrito é reformulado como um caso especial da estrutura geral bi-nível minimax via dualidade lagrangiana.

A literatura existente foca amplamente em otimização bi-nível onde o nível inferior é uma minimização de objetivo único (frequentemente estritamente convexa). Métodos que dependem de hipergradientes ou diferenciação implícita frequentemente falham quando o nível inferior é meramente convexo, não convexo ou possui uma estrutura minimax. Este trabalho visa preencher essa lacuna desenvolvendo métodos de primeira ordem para o cenário de nível inferior minimax sem exigir convexidade estrita.

Metodologia

A abordagem proposta utiliza uma reformulação por função de valor com penalidade. O problema bi-nível restrito é transformado em um problema minimax não restrito (ou com restrições mais simples) introduzindo um parâmetro de penalidade $\rho$.

Cenário Determinístico

1. Reformulação por Penalidade: O problema original é reformulado em um problema minimax de nível único:
   $$\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)$$
   onde $P_\rho$ incorpora a função objetivo e o termo de penalidade $\rho(p(x_1, y_1) - d(x_1, y_2))$, representando a lacuna de dualidade do problema de nível inferior.
2. Algoritmo: Os autores propõem um método de ponto proximal inexato. O loop externo atualiza as variáveis primal-dual resolvendo uma sequência de subproblemas estritamente convexos-estritamente côncavos (SCSC).
3. Solver de Subproblema: Cada subproblema é resolvido usando um método ótimo de primeira ordem (especificamente, uma variante do método de Lu e Mei [52] ou Kovalev e Gasnikov [37]), denotado como OptFOM.
4. Complexidade: O método encontra um ponto $\epsilon$-KKT com uma complexidade de oráculo de $\tilde{O}(\epsilon^{-4})$.

Cenário Estocástico

Quando apenas oráculos de gradiente estocástico estão disponíveis para os componentes suaves:

1. Algoritmo: O método de ponto proximal determinístico é adaptado para usar um Método Primal-Dual Acelerado Estocástico (SAPD) (especificamente SAPD+ de Zhang et al. [75]) para resolver os subproblemas internos.
2. Convergência: O método encontra um ponto "quase" $\epsilon$-KKT (onde a solução está dentro de uma distância $\epsilon$ de um ponto $\epsilon$-KKT exato) com uma complexidade de oráculo estocástico de $\tilde{O}(\epsilon^{-9})$.

Aplicação a Problemas de Nível Inferior Restritos

Para o caso específico de otimização bi-nível com um nível inferior convexo restrito (Problema 4), os autores mostram que, sob a condição de Slater, os multiplicadores de Lagrange são limitados dentro de uma caixa $[0, B]^l$. Isso permite que o problema restrito seja reformulado como o problema bi-nível minimax geral (Problema 1) introduzindo as variáveis duais como variáveis de otimização explícitas com restrições de caixa. Esta reformulação evita a necessidade de um parâmetro de penalidade interno, levando a limites de complexidade aprimorados em comparação com trabalhos anteriores.

Contribuições Principais

1. Primeiros Resultados de Complexidade para Minimax Bi-nível: O artigo estabelece os primeiros limites de complexidade para métodos de primeira ordem determinísticos e estocásticos para otimização bi-nível onde o nível inferior é um problema minimax.
   • Complexidade determinística: $\tilde{O}(\epsilon^{-4})$.
   • Complexidade estocástica: $\tilde{O}(\epsilon^{-9})$.
2. Limites Aprimorados para Problemas Bi-nível Restritos: Ao reformular problemas bi-nível com níveis inferiores convexos restritos como instâncias da estrutura minimax proposta, os autores alcançam uma complexidade de $\tilde{O}(\epsilon^{-4})$. Isso melhora os resultados existentes para níveis inferiores meramente convexos ($\tilde{O}(\epsilon^{-7})$ em [53]) e estritamente convexos ($\tilde{O}(\epsilon^{-6})$ em [51]). A melhoria decorre da evitação do uso de um segundo parâmetro de penalidade para as restrições internas, o que anteriormente levava a parâmetros de suavidade mais altos.
3. Validação Empírica:
   • Dados Sintéticos: Em problemas bi-nível lineares restritos, o método proposto demonstra velocidades de convergência competitivas contra métodos baseados em penalidade existentes (FOP e SMO), particularmente quando a constante de Lipschitz é ajustada.
   • Aplicação do Mundo Real: O método é aplicado ao ajuste de hiperparâmetros para Otimização Robusta Distribucionalmente (DRO) em aprendizado profundo. Nos conjuntos de dados CelebA e Waterbirds, a abordagem bi-nível estocástica proposta supera os métodos DRO padrão em termos de precisão do pior grupo, mantendo uma precisão média comparável.

Resultados e Significância

O artigo afirma que a estrutura proposta baseada em penalidade fornece uma abordagem unificada para lidar com problemas bi-nível com estruturas minimax, um cenário previamente inexplorado na literatura em relação à complexidade de primeira ordem.

• Significância Teórica: O trabalho preenche a lacuna entre otimização bi-nível e otimização minimax, fornecendo garantias rigorosas de convergência sem depender de suposições de convexidade estrita para o problema de nível inferior. A redução da complexidade de $\tilde{O}(\epsilon^{-7})$ para $\tilde{O}(\epsilon^{-4})$ para níveis inferiores restritos é apresentada como um avanço teórico significativo.
• Significância Prática: A aplicação ao DRO demonstra a utilidade do método em cenários de aprendizado de máquina envolvendo deslocamentos de distribuição e equidade de grupos. Os resultados nos conjuntos de dados CelebA e Waterbirds mostram que o método pode lidar efetivamente com o desafio de otimização do "pior grupo", alcançando maior precisão do pior grupo do que os métodos DRO de base.

Os autores reconhecem limitações, incluindo a exigência de domínios viáveis compactos, o uso de um espaço elevado para definições KKT e a alta complexidade do caso estocástico ($\tilde{O}(\epsilon^{-9})$), observando que técnicas de redução de variância poderiam ser uma direção para trabalhos futuros.