A Unifying View of Anchoring via Operator-Side Tikhonov Regularization

Resumo Técnico: Uma Visão Unificadora de Ancoragem via Regularização de Tikhonov do Lado do Operador

Enunciado do Problema
O artigo aborda o problema de obter garantias de convergência de última iteração (last-iterate) aguçadas para métodos de ponto fixo e de equações monotônicas. Embora métodos clássicos como a iteração de Picard (para aplicações não expansivas) e o passo à frente (forward step, para operadores monotônicos) sejam fundamentais, eles frequentemente falham em convergir ou divergem sob condições meramente não expansivas ou monotônicas Lipschitz sem estrutura adicional (ex: cocoercividade). Variantes "ancoradas" existentes, como a iteração de Halpern, o Gradiente Extra Ancorado (EAG) e os métodos de Popov/OGDA ancorados, alcançam com sucesso taxas aceleradas de última iteração (ex: $O(1/k)$) ao adicionar um puxão evanescente em direção a um ponto de referência $x_0$. No entanto, o artigo argumenta que o posicionamento desses termos de âncora nas variantes existentes é frequentemente específico de cada algoritmo e conceitualmente opaco, carecendo de uma derivação unificada a partir do padrão de consulta do método base.

Metodologia: Regularização de Tikhonov do Lado do Operador
A contribuição central é um princípio de construção unificador denominado regularização de Tikhonov do lado do operador. Em vez de modificar a regra de atualização diretamente para inserir uma âncora, os autores propõem regularizar o operador consultado pelo método base.

1. A Construção:

   • Para um problema de ponto fixo com aplicação $T$, o método regulariza a aplicação para $T_k(x) = (1-\delta_k)T(x) + \delta_k x_0$.
   • Para uma equação monotônica com operador $F$, o método regulariza o deslocamento escalonado para $G_k(x) = \eta_k F(x) + \delta_k(x - x_0)$.
     Aqui, $\delta_k$ é uma sequência evanescente ($\delta_k \downarrow 0$) e $x_0$ é uma âncora fixa.

2. A Execução:
   O método base (Picard, Passo à Frente, Extragradiente ou Past Extragradient) é aplicado a este objeto regularizado móvel sem modificação.

   • Picard em $T_k$: Resulta na iteração de Halpern.
   • Passo à Frente em $G_k$: Resulta em um passo à frente ancorado estabilizado.
   • Extragradiente (EG) em $G_k$: Resulta em uma nova variante, Reg-EG, onde o segundo termo de âncora é avaliado no ponto de olhadinha (lookahead point) ($x_{k+1/2}$) em vez do iterado atual.
   • Past Extragradient (PEG) em $G_k$: Resulta em Reg-PEG, onde os termos de âncora são avaliados nos pontos de consulta do PEG passado e atual ($\tilde{x}_{k-1}$ e $\tilde{x}_k$).

3. Estrutura de Análise:
   A análise de convergência segue um padrão unificado de progresso–deriva–viés (progress–drift–bias):

   • Progresso: O operador regularizado é fortemente monotônico (ou contrativo), garantindo uma contração no potencial residual regularizado $E_k$.
   • Deriva (Drift): A análise limita a mudança no operador regularizado entre os passos ($G_{k-1}$ para $G_k$), tratando-a como um termo de deriva.
   • Viés (Bias): O passo final remove o viés da regularização para limitar o residual original ($\|T(x_k)-x_k\|$ ou $\|F(x_k)\|$).

Principais Contribuições e Resultados

1. Unificação da Ancoragem: O artigo demonstra que o posicionamento da âncora em várias variantes aceleradas não é arbitrário, mas sim sistematicamente determinado pelo padrão de consulta do método base quando aplicado ao operador regularizado. Isso fornece uma derivação intuitiva única para Halpern, Reg-EG e Reg-PEG.

2. Novas Variantes e Garantias:

   • Reg-Forward Step: O artigo estabelece que um passo à frente regularizado por Tikhonov sozinho estabiliza o método para operadores apenas monotônicos Lipschitz, alcançando uma taxa de norma de residual de última iteração de $O(LR/\sqrt{k})$. Esta é a primeira garantia desse tipo para um passo à frente de uma única chamada sem extragradiente ou mecanismos de consulta passada.
   • Reg-EG e Reg-PEG: O artigo introduz estas novas variantes regularizadas. Ambas alcançam uma taxa acelerada de norma de residual de última iteração de $O(LR/k)$ no cenário monotônico Lipschitz sem restrições.
   • Iteração de Halpern: O framework recupera a taxa conhecida de $O(1/k)$ para a iteração de Halpern em espaços normados gerais, fornecendo uma nova perspectiva de análise.

3. Posicionamentos Específicos de Âncora:

   • Em Reg-EG, a âncora é colocada no ponto de olhadinha ($x_{k+1/2}$), diferindo das variantes padrão de EG ancorado (como o EAG), onde a âncora está ligada ao deslocamento base ($x_0 - x_k$).
   • Em Reg-PEG, as âncoras seguem os pontos de consulta do operador ($\tilde{x}_{k-1}$ e $\tilde{x}_k$), distinguindo-se dos esquemas de Popov ancorados que aplicam âncoras aos iterados base.

Significância e Alegações
O artigo alega que esta perspectiva do lado do operador esclarece o mecanismo da "aceleração por ancoragem". Ele postula que a ancoragem não é meramente uma mudança estrutural no algoritmo, mas uma consequência de resolver um problema melhor condicionado (regularizado) enquanto se equilibra o progresso contra o viés da regularização.

Os autores enfatizam que esta visão:

• Fornece uma única derivação intuitiva que produz novas variantes ancoradas aceleradas de forma uniforme.
• Gera novos resultados (especificamente o Reg-Forward Step e as variantes específicas Reg-EG/PEG com seus distintos posicionamentos de âncora) que não foram previamente derivados através desta lente unificada.
• Mantém taxas aguçadas ($O(1/k)$ para variantes EG/PEG e $O(1/\sqrt{k})$ para o passo à frente) comparáveis ou correspondentes às melhores taxas conhecidas na literatura, mas derivadas através de um framework de prova comum.

O trabalho é apresentado como uma unificação teórica em um cenário simples, de valor único e sem restrições, com extensões para inclusões monotônicas e desigualdades variacionais observadas como direções naturais para o futuro.