Resumo Técnico: Sobre o Extragradiente Estocástico de Amostra Única (Same-Sample) e de Amostras Independentes para Desigualdades Variacionais Monótonas

Formulação do Problema

Este trabalho investiga as propriedades de convergência dos métodos de Extragradiente Estocástico (SEG) para resolver Problemas de Desigualdade Variacional (VIP) monótonos. Um VIP busca um ponto $x^* \in X$ tal que $\langle F(x^*), x - x^* \rangle \geq 0$ para todo $x \in X$, onde $F$ é um operador monótono. No cenário estocástico, o operador $F$ é definido como uma soma finita $F(x) = \frac{1}{n} \sum_{i=1}^n F(x; \xi_i)$, e os algoritmos acessam $F$ por meio de amostras estocásticas.

O artigo foca em duas variantes distintas de SEG:

1. SEG de Amostras Independentes (I-SEG): Utiliza índices aleatórios independentes $\xi_{i_k}$ e $\xi_{\hat{i}_k}$ para as etapas de extrapolação e atualização, respectivamente.
2. SEG de Amostra Única (S-SEG): Utiliza um índice aleatório compartilhado $\xi_{i_k} = \xi_{\hat{i}_k}$ para ambas as etapas.

Embora o I-SEG possua uma teoria de convergência bem desenvolvida, o S-SEG — uma variante natural frequentemente preferida na prática por sua eficiência computacional — recebeu significativamente menos atenção teórica. Os autores visam preencher essa lacuna analisando o S-SEC sob suposições mínimas e comparando seu comportamento fundamentalmente contra o I-SEG.

Metodologia e Estrutura Teórica

A análise baseia-se em suposições padrão de otimização estocástica, incluindo:

• Monotonicidade de Média e Lipschitzianidade: O operador esperado $F$ é monótono e Lipschitz.
• Não Viesamento (Unbiasedness): Os operadores estocásticos são estimadores não viesados da média.
• Limites de Variância: O artigo utiliza tanto a suposição padrão de Variância Limitada (Suposição 2.5) quanto a suposição de Variância Generalizada (Suposição 2.6), que permite que a variância cresça linearmente com a distância até a solução.
• Lipschitzianidade Uniforme: Uma suposição mais forte (Suposição 2.3) exigindo que cada operador de amostra $F(\cdot; \xi_i)$ seja Lipschitz, distinta do fato de o operador médio ser Lipschitz.

Os autores empregam uma combinação de análise de alta probabilidade, teoremas de convergência de martingales (especificamente o teorema de dois séries de Kolmogorov) e a construção de contraexemplos específicos para estabelecer tanto garantias de convergência positivas quanto resultados de impossibilidade negativos. Um desafio técnico central abordado é o termo de viés $\langle F(\hat{x}_k; \xi_{i_k}) - F(\hat{x}_k), x_k \rangle$, que desaparece em esperança para o I-SEG devido à independência, mas permanece não nulo para o S-SEG.

Principais Contribuições e Resultados

1. Sensibilidade à Lipschitzianidade por Amostra

O artigo demonstra que o S-SEG é sensível às propriedades de Lipschitz dos operadores de amostra individuais, não apenas do operador médio.

• Resultado: Mesmo em domínios compactos com variância limitada e uma solução única, o S-SEG pode falhar em convergir se os operadores de amostra não forem uniformemente Lipschitz (Suposição 2.3).
• Evidência: Um contraexemplo (Proposição 3.2) é construído onde o operador médio é monótono e Lipschitz, mas os operadores de amostra possuem descontinuidades de salto. Neste cenário, as iteradas do S-SEG permanecem presas em uma região separada da solução, enquanto o I-SEG convergiria. Isso estabelece que a Suposição 2.3 é um requisito substantivo para o S-SEG, não meramente um artefato da prova.

2. Convergência da Função de Gap de Alta Probabilidade em Domínios Não Limitados

Para domínios possivelmente não limitados, os autores estabelecem garantias de convergência de alta probabilidade para ambos I-SEG e S-SEG sob tamanhos de passo somáveis ao quadrado ($\sum \gamma_k^2 < \infty$).

• Resultado: Sob a suposição de Variância Generalizada (para I-SEG) e Lipschitzianidade Uniforme (para S-SEG), ambos os métodos satisfazem um limite de função de gap condicional esperado em um evento de alta probabilidade onde as iteradas permanecem limitadas.
• Impossibilidade: O artigo prova que essas garantias de alta probabilidade são essencialmente apertadas.
  • Sem passos somáveis ao quadrado, tanto o I-SEG quanto o S-SEG podem divergir quase certamente (Teoremas 3.9 e 3.10).
  • Mesmo com passos somáveis ao quadrado, as iteradas podem escapar de qualquer região limitada pré-especificada com probabilidade positiva. Consequentemente, a convergência da função de gap esperada incondicional sobre uma região limitada fixa não pode ser garantida (Teorema 3.12). A distribuição limite das iteradas possui suporte ilimitado.

3. Separação Fundamental na Convergência da Última Iterada

O artigo investiga a convergência da última iterada quase certa ($x_k \to x^*$).

• Quase-Estrita Monotonicidade: Sob a suposição adicional de quase-estrita monotonicidade (Suposição 2.8), tanto o I-SEG quanto o S-SEG convergem quase certamente para uma solução com passos somáveis ao quadrado (Teorema 4.1).
• Falha do DSEG para S-SEG: Uma descoberta crítica é que a regra de Extragradiente de Passo Duplo (DSEG), que garante a convergência da última iterada quase certa para o I-SEG em VIPs monótonos gerais (sem quase-estrita monotonicidade), falha para o S-SEG.
• Evidência: Os autores constroem um VIP monótono estocástico com uma solução única onde o S-SEG, mesmo utilizando tamanhos de passo DSEG, diverge quase certamente. Tanto a última iterada quanto a média ponderada das iteradas divergem para o infinito (Teorema 4.2). Isso indica que a independência das amostras é um mecanismo central para a convergência do DSEG, não apenas uma conveniência de prova.

Significância e Alegações

O artigo afirma delinear o limite preciso entre convergência e falha para as duas principais variantes de SEG. Suas principais contribuições são:

1. Esclarecimento dos Requisitos do S-SEG: Estabelece que o S-SEG requer suposições mais fortes (Lipschitzianidade uniforme das amostras) do que o I-SEG, e que a variância limitada por si só é insuficiente para a convergência em conjuntos compactos.
2. Aperto dos Limites de Alta Probabilidade: Mostra que, para domínios não limitados, a convergência de alta probabilidade é a garantia mais forte possível para o SEG com passos simétricos, pois garantias incondicionais são geralmente impossíveis devido ao suporte ilimitado da distribuição limite.
3. Divergência Fundamental das Variantes: Prova que o S-SEG e o I-SEG não são intercambiáveis. Especificamente, a estratégia de tamanho de passo DSEG, eficaz para o I-SEG, não pode salvar o S-SEG da divergência na ausência de quase-estrita monotonicidade. Isso destaca que a estratégia de amostragem (independente vs. amostra única) altera fundamentalmente a dinâmica do algoritmo e suas propriedades de convergência.

Os autores concluem que, embora o SEG seja um algoritmo fundamental, a compreensão teórica do S-SEG está atrás do I-SEG, e as duas variantes exibem comportamentos distintos que devem ser levados em conta no design e análise de algoritmos. O trabalho não propõe novos algoritmos, mas fornece uma caracterização rigorosa dos existentes, identificando onde as ferramentas teóricas atuais têm sucesso e onde elas falham fundamentalmente.