Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

Resumo Técnico: Aproximação Estocástica de Duas Escalas de Tempo Não-Expansiva

Enunciado do Problema
O artigo investiga as taxas de convergência da aproximação estocástica de duas escalas de tempo (TTSA) em um regime onde o mapa rápido é contrativo, mas o mapa lento reduzido é apenas não-expansivo. Este cenário surge em otimização minimax, desigualdades variacionais e aproximação estocástica com restrições. Diferente da TTSA contrativa, onde a variável lenta converge para um equilíbrio único, o caso não-expansivo apresenta um conjunto de pontos fixos potencialmente não-unitário. Consequentemente, a métrica de desempenho natural é o resíduo do ponto fixo $p(y) = h(y) - y$, em vez da distância a um ponto específico.

Trabalhos anteriores estabeleceram uma taxa de resíduo de média quadrática de última iteração de $O(k^{-1/4+\epsilon})$ para este regime. O artigo visa explicar a origem teórica deste expoente $1/4$ e determinar se modificações algorítmicas podem melhorá-lo.

Metodologia e Estrutura Teórica
Os autores decompõem a dinâmica do erro em dois componentes distintos: a convergência intrínseca da recursão lenta não-expansiva e o vazamento (leakage) dos erros de rastreamento rápido para o oráculo lento.

1. Agudeza da Barreira do Cronograma Fixo de KM:
   O artigo estabele-se primeiro que a escala de resíduo clássica de Krasnoselskii–Mann (KM), definida pelo inverso da soma $\sum \beta_i(1-\beta_i)$, é aguda para qualquer cronograma de passo de escala lenta $(\beta_k)$ fixo. Usando um exemplo de rotação planar, os autores provam um limite inferior de horizonte finito mostrando que nenhum update KM não-regularizado pode alcançar uma taxa de decaimento de resíduo de pior caso mais rápida do que esta escala para um dado cronograma. Isso implica que melhorar a taxa requer mudar o regime algorítmico ou a estrutura do oráculo, e não meramente refinar a análise do update KM padrão.

2. Diagnóstico do Expoente $1/4$:
   O artigo identifica o "vazamento de primeira ordem da variedade rápida" (first-order fast-manifold leakage) como a principal obstrução. Em uma TTSA bruta, o oráculo lento avalia o mapa no iterado rápido atual $X_k$, em vez do verdadeiro equilíbrio $x^*(Y_k)$. Devido à continuidade de Lipschitz do mapa lento na coordenada rápida, o erro $g(X_k, Y_k) - h(Y_k)$ é de primeira ordem no erro de rastreamento $\|X_k - x^*(Y_k)\|$.
   O próprio erro de rastreamento é governado por um balanço entre a variância estocástica rápida ($\alpha_k$) e o atraso determinístico atrás do alvo móvel ($(\beta_k/\alpha_k)^2$). Mesmo sob a condição de separação padrão $\beta_k^2/\alpha_k^3 \lesssim 1$, a combinação da escala KM aguda e este vazamento de primeira ordem resulta em uma complexidade de amostra total de $T^{-1/4+o(1)}$. Violar a condição de separação não melhora a taxa; apenas desloca o gargalo da variância estatística para o atraso do alvo móvel, que ainda entra como uma perturbação de primeira ordem.

3. Correção de Viés via Precondicionamento de Resíduo:
   Para superar o vazamento de primeira ordem, os autores introduzem um oráculo lento precondicionado pelo resíduo. Ao utilizar as derivadas dos mapas rápido e lento, eles constroem um termo de correção que cancela a dependência linear do erro de rastreamento rápido.
   Especificamente, se $A(y) = I - \nabla_x f(x^*(y), y)$ e $C(y) = \nabla_x g(x^*(y), y)$, o precondicionador é $P^*(y) = C(y)A(y)^{-1}$. O oráculo corrigido é definido como:
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   A expansão de Taylor mostra que esta correção reduz o viés do oráculo lento de primeira ordem ($O(\|e\|)$) para segunda ordem ($O(\|e\|^2)$), onde $e$ é o erro de rastreamento rápido.

Contribuições Principais e Resultados

O artigo apresenta três resultados teóricos principais, progredindo do diagnóstico do método bruto para algoritmos otimizados sob suposições de oráculo estruturado.

1. Limite Inferior de Cronograma Fixo:
   Os autores provam que, para qualquer cronograma de passo lento fixo, o resíduo de média quadrática da iteração KM não-regularizada não pode melhorar uniformemente a escala $(\sum \beta_i(1-\beta_i))^{-1}$. Isso confirma que o expoente $1/4$ no trabalho anterior não é um artefato de uma análise frouxa, mas uma consequência da escala KM aguda combinada com o vazamento de primeira ordem.

2. Algoritmo de Aninhamento com Correção de Viés ($T^{-1/3}$):
   Em um framework Tikhonov-KM aninhado, os autores aplicam o precondicionamento de resíduo.

   • Não Corrigido: O método aninhado com um oráculo bruto alcança uma taxa de amostra total de $T^{-1/4+o(1)}$.
   • Corrigido: Ao usar o oráculo precondicionado, o viés ao quadrado do oráculo lento torna-se $O(n^{-2})$ (onde $n$ é o número de amostras internas) em vez de $O(n^{-1})$. Esta mudança estrutural melhora a complexidade de amostra total para $T^{-1/3+o(1)}$.
   • Nota: Este resultado assume o acesso ao precondicionador exato $P^*(y)$ ou a um estimador que satisfaça condições específicas de precisão de produto.

3. Precondicionador Aprendido de Ciclo Único ($T^{-1/2}$):
   Para evitar o custo repetido de resoluções de loop interno no método aninhado, os autores propõem um algoritmo de ciclo único que rastreia o equilíbrio rápido, a variável lenta e a matriz precondicionadora online.

   • Este método mantém estimativas contínuas de $X_k$, $Y_k$ e $P_k$ usando observações de derivadas estocásticas.
   • Sob suposições de suavidade (diferenciabilidade dos mapas e acesso a oráculos de derivada), esta abordagem alcança uma taxa de amostra total de $T^{-1/2+o(1)}$ com $O(1)$ amostras primitivas por iteração.
   • Esta melhoria baseia-se na capacidade de aprender o precondicionador de vazamento online, amortizando efetivamente o custo da resolução interna.

Significância e Alegações
O artigo alega fornecer uma explicação teórica completa para o expoente $1/4$ na TTSA não-expansiva, atribuindo-o à interação entre a escala de resíduo KM aguda e o vazamento de primeira ordem da variedade rápida. A principal contribuição é demonstrar que esta barreira não é fundamental para a classe de problemas, mas específica para a estrutura do oráculo "bruto".

Ao introduzir um oráculo precondicionado pelo resíduo, os autores mostram que o vazamento pode ser reduzido para segunda ordem, melhorando assim as taxas de convergência. O resultado $T^{-1/3}$ serve como um certificado de que a correção de viés é eficaz, enquanto o resultado $T^{-1/2}$ demonstra que esses ganhos podem ser realizados em um cenário de ciclo único se a informação de derivada estiver disponível. Os autores enquadram explicitamente estes resultados como conquistas de "oráculo estruturado", observando que eles dependem de diferenciabilidade e acesso a informações relacionadas ao Jacobiano, distinguindo-os de métodos de ponto fixo não-expansivos de caixa-preta. O trabalho não pretende resolver o problema para oráculos de caixa-preta gerais, mas sim identificar a modificação estrutural específica (cancelamento de viés) necessária para acelerar a convergência na presença de suavidade.