A Double-Inertial Variance-Reduced Proximal Alternating Method for Block-Structured Nonconvex Minimax Optimization

Resumo Técnico: Um Método Proximal Alternado de Variância Reduzida com Dupla Inércia para Otimização Minimax Não-Convexa com Estrutura em Blocos

Definição do Problema
O artigo aborda o problema de otimização minimax não-convexo–não-côncavo de soma finita:
$$\min_{x \in \mathbb{R}^{m_1}} \max_{y \in \mathbb{R}^{m_2}} \Psi(x, y) = H(x, y) + f(x) - g(y),$$
onde $H(x, y) = \frac{1}{N} \sum_{i=1}^N H_i(x, y)$ é uma soma finita suave, e $f, g$ são funções convexas próprias e semicontínuas inferiores (potencialmente funções indicadoras de conjuntos convexos). O problema surge em aplicações como treinamento adversarial, redes adversárias generativas (GANs) e decomposição tensorial robusta.

A análise é conduzida sob a condição da Desigualdade Variacional de Minty (MVI). Esta condição postula a existência de um ponto $z^* = (x^*, y^*)$ tal que, para todo $z = (x, y)$ no domínio e subgradientes $u, v$, a desigualdade $\langle \nabla_x H(x, y) + u, x - x^* \rangle + \langle -\nabla_y H(x, y) + v, y - y^* \rangle \geq 0$ é válida. Esta condição é mais fraca que a convexidade-concavidade, mas exclui ciclos e legitima o resíduo do gradiente proximal como uma medida de estacionariedade.

Metodologia: IiSminimaxPALM
Os autores propõem o IiSminimaxPALM (Inertial, Inertial, Stochastic, Minimax Proximal Alternating Linearized Minimization), um método proximal alternado linearizado de minimax estocástico, com inércia dupla e redução de variância.

• Mecanismo de Dupla Inércia: O algoritmo emprega dois tipos de inércia:
  1. Inércia de Consulta ($\beta$): Utilizada para extrapolar o ponto de consulta para a avaliação do gradiente.
  2. Inércia de Pós-Atualização ($\gamma$): Utilizada para extrapolar a iteração atualizada antes do próximo passo.
     Ao contrário de trabalhos anteriores, a análise não impõe um limite inferior para a inércia de pós-atualização $\gamma$ além de $[0, 1)$, cobrindo explicitamente o caso $\gamma = 0$.
• Redução de Variância: O método utiliza o estimador SAGA para atualizações de loop único e uma variante SARAH baseada em épocas.
• Atualizações Proximais Alternadas: O algoritmo alterna entre a minimização em relação a $x$ (usando um operador proximal para $f$) e a maximização em relação a $y$ (usando um operador proximal para $g$), incorporando gradientes estocásticos e termos inerciais.
• Análise Ancorada: A análise de convergência baseia-se em uma "âncora" no ponto de Minty $z^*$. Uma restrição técnica crítica é que o parâmetro do centro-proximal (inércia aplicada ao ponto âncora) é definido como zero ($\alpha = 0$) para os principais resultados de complexidade estocástica. O caso $\alpha > 0$ é identificado como um problema em aberto dentro da estrutura ancorada.

Principais Contribuições e Resultados

1. Limites de Complexidade:

   • Variante SAGA: O método alcança uma complexidade de avaliação de $N + O(N^2 L^2 D^2 / \varepsilon^2)$, onde $N$ é o número de componentes, $L$ é a constante de Lipschitz, $D$ é o diâmetro do domínio em torno do ponto de Minty, e $\varepsilon$ é a tolerância de estacionariedade.
   • Variante SARAH: Uma variante SARAH baseada em épocas alcança $O(\sqrt{N} L^4 D^2 / \varepsilon^2)$.
   • Otimalidade de $N^2$: O artigo prova que a escala $N^2$ para estimadores não enviesados de loop único é info-teoricamente ótima dentro da classe de análises do tipo âncora. Especificamente, qualquer estimador baseado em tabela não enviesado que atualiza $b$ entradas por iteração contrai a uma taxa não superior a $1 - b/N$. Consequentemente, nenhum tal estimador pode alcançar uma complexidade melhor que $\Omega(N^2)$ para esta classe.
   • Otimalidade de $\varepsilon^{-2}$: A escala $\varepsilon^{-2}$ é mostrada como class-ótima para $N=1$ via uma instância difícil não-convexa star-monotônica.
   • Conjectura: Os autores conjecturam que um limite inferior mais justo de $\sqrt{N} L \Delta / \varepsilon^2$ existe para a classe Minty, fornecendo um programa de construção no apêndice, embora o limite mais forte disponível atualmente se aplique a uma cadeia zero não-Minty não-convexa.

2. Convergência Linear:

   • Sob monotonicidade forte do operador de sela (cobrindo problemas compostos fortemente convexos–fortemente côncavos), a variante determinística não-inercial converge R-linearmente com uma taxa certificada de $(1 + \eta \mu)^{-1}$.
   • Para a variante inercial, a convergência linear é preservada para parâmetros de inércia suficientemente pequenos ($\alpha \leq \eta \mu / 50$).
   • Para jogos quadráticos com acoplamento pequeno, toda a faixa prática de inércia é certificada para preservar a convergência linear e fornecer aceleração (taxa $1 - \Theta(\kappa^{-1/2})$), verificada via computação espectral exata.

3. Passo Adaptativo:

   • Um algoritmo de seleção de tamanho de passo adaptativo (backtracking) é proposto para determinar um tamanho de passo constante que satisfaça os requisitos teóricos sem conhecimento prévio das constantes do problema, mantendo as garantias de complexidade.

4. Experimentos Numéricos:

   • Os experimentos são conduzidos em um benchmark provadamente-Minty (um jogo não-convexo–não-côncavo onde a condição de Minty é provada analiticamente, não apenas amostrada).
   • Escalabilidade: A variante estocástica (IiSminimaxPALM) supera a linha de base determinística PALM por um fator de 9,6 a 14,1 em avaliações de oráculo para grandes $N$, devido à independência do custo por iteração em relação a $N$.
   • Inércia: Os experimentos confirmam a convergência para todas as configurações de inércia testadas, incluindo $\gamma = 0$ (previamente excluído por hipóteses de inércia não-zero em literatura relacionada) e $\alpha > 0$ (além do escopo teórico atual). Nos casos testados, a dupla inércia não gerou aceleração mensurável sobre o caso não-inercial, sugerindo que seu principal valor é a relaxação de hipóteses restritivas.

Significado e Alegações
O artigo afirma preencher uma lacuna na literatura ao desenvolver um método proximal alternado de coordenação em blocos, com redução de variância e inércia, sob a condição de MVI de Minty.

• Rigor Teórico: Fornece a primeira análise de complexidade para tais métodos sob condições de Minty, estabelecendo que a dependência $N^2$ para métodos de loop único não enviesados não é um artefato da análise, mas uma barreira info-teórica para essa classe específica de estimadores.
• Relaxação de Hipóteses: Ao provar a convergência para $\gamma = 0$ e $\alpha = 0$, o método remove suposições restritivas encontradas na literatura de proximal alternado inercial anterior.
• Problemas em Aberto: Os autores declaram modestamente que várias questões permanecem em aberto, incluindo:
  • A taxa de convergência linear estocástica para o variante proximal inercial sob a condição de dois lados de Polyak-Łojasiewicz (PL).
  • O caso do centro-proximal inercial ($\alpha > 0$) no principal teorema de complexidade estocástica.
  • Provar a conjectura do limite inferior $\sqrt{N}$ para a classe Minty.
  • Desenvolver salvaguardas adaptativas não-monótonas que detectem instabilidade de variância.

O trabalho conclui que, embora a redução de variância de loop único não enviesada sob condições de Minty seja limitada à complexidade $N^2$, métodos enviesados baseados em épocas (SARAH) alcançam a escala superior $\sqrt{N}$, e o método proposto oferece um framework robusto e teoricamente fundamentado para otimização minimax não-convexa–não-côncava.