Accelerated and Stable Convergence with Anchored Optimistic Method

Technical Summary: Accelerated and Stable Convergence with Anchored Optimistic Method

Problem Statement
The paper addresses the challenge of solving monotone variational inequality (VI) problems, which arise in min-max optimization, adversarial training, and multi-agent reinforcement learning. The specific goal is to find a solution $x^\star$ such that $G(x^\star) = 0$ for a monotone, $L$-Lipschitz operator $G$.

The authors highlight three critical limitations in existing first-order methods:

1. Computational Cost: Classical methods like the Extragradient (EG) method require two gradient evaluations per iteration, making them inefficient for online or stochastic settings where only a single gradient is available per step.
2. Stability in Stochastic Regimes: While optimistic methods (e.g., Popov's method) reduce the cost to a single gradient call, they often fail to converge in stochastic environments or exhibit oscillatory behavior without specific modifications.
3. Suboptimal Last-Iterate Rates: Existing methods often guarantee convergence only in an ergodic (average) sense. For last-iterate convergence (the actual final iterate), standard EG achieves a rate of $O(1/k)$ for the squared operator norm, which is not optimal compared to the known lower bound of $O(1/k^2)$. Furthermore, stochastic last-iterate guarantees typically rely on variance reduction techniques or growing batch sizes, which are impractical for constant-batch online learning.

Methodology: Generalized Optimistic Method with Anchoring (GOMA)
The authors propose GOMA, a family of algorithms that integrates two key mechanisms:

1. Two-Time-Scale Optimistic Updates: Building on the Generalized Optimistic Method (Mokhtari et al., 2020), GOMA employs distinct step sizes for the prediction (exploration) and correction (update) steps. This decoupling enhances stability.
2. Halpern-Type Anchoring: Inspired by the Halpern fixed-point iteration, GOMA introduces an anchoring term that pulls the iterates toward the initial point $x_0$. The update rule is defined as:
   $$\begin{aligned} y_k &= \beta_k x_0 + (1 - \beta_k)x_k - \gamma_k G(y_{k-1}) \\ x_{k+1} &= \beta_k x_0 + (1 - \beta_k)x_k - \eta_k G(y_k) \end{aligned}$$
   Here, $\beta_k$ is an anchoring coefficient that decays to zero (e.g., $\beta_k = \frac{2}{k+6}$), while $\gamma_k$ and $\eta_k$ are step sizes. The anchoring term effectively adds artificial strong monotonicity to the operator during the transient phase, accelerating convergence while asymptotically recovering the original problem.

The paper analyzes two parameter schedules:

• Case I: A fixed update step size $\eta^*$ with a scaled exploration step.
• Case II: A fixed exploration step size $\gamma^*$ with a scaled update step.

Key Contributions and Results

1. Deterministic Setting (Monotone Lipschitz Operators):

   • GOMA achieves an accelerated last-iterate convergence rate of $O(1/k^2)$ on the squared operator norm $\|G(x_k)\|^2$.
   • This rate matches the theoretical complexity lower bound for this class of operators.
   • The analysis provides explicit constants and demonstrates that GOMA achieves this optimal rate with a pseudo fixed-step size scheme, simplifying hyperparameter tuning compared to previous anchored methods like Anchored Popov.

2. Stochastic Setting (Unbounded Variance):

   • The authors introduce a simplified, single-call variant of GOMA (where $\gamma_k = 0$) specifically for stochastic settings. This variant evaluates the operator at an anchored interpolation between the current iterate and the initial point.
   • Under state-dependent noise assumptions (where the noise variance can grow with $\|G(x)\|^2$, i.e., unbounded variance), this variant achieves a last-iterate convergence rate of $O(1/\sqrt{k})$ on the squared operator norm.
   • Significance: To the best of the authors' knowledge, this is the first last-iterate guarantee for stochastic monotone Lipschitz VIs in the unconstrained setting that operates without variance reduction techniques or growing batch sizes. It maintains a constant batch size of one sample per iteration.

Comparison with Existing Work
The paper positions GOMA against several state-of-the-art methods:

• vs. Extragradient (EG) & FEG: While FEG achieves $O(1/k^2)$ in deterministic settings, its stochastic guarantees typically require growing batches or bounded variance. GOMA achieves robustness with a single call and constant batch size.
• vs. Variance-Reduced Methods (E-Halpern, RAIN++): These methods achieve faster rates (e.g., $O(1/k)$ or better) but rely on recursive variance reduction or large-batch snapshots. GOMA trades off the optimal rate for the ability to operate in constant-batch, unbounded-noise regimes without complex variance reduction machinery.
• vs. DSEG: While DSEG handles stochastic settings, it often fails to converge in non-affine problems or requires specific conditions that GOMA's anchoring mechanism overcomes.

Significance and Claims
The paper claims that GOMA occupies a distinctive point in the design space of VI algorithms. It is the only method that simultaneously guarantees:

• Last-iterate convergence in the squared operator norm.
• Single operator evaluation per iteration (single-call).
• Convergence under unbounded, state-dependent noise.
• Operation without variance reduction or growing batches.

While the stochastic rate of $O(1/\sqrt{k})$ (equivalent to $O(1/\epsilon^4)$ sample complexity) is slower than the optimal rates achieved by variance-reduced methods ($O(1/\epsilon^2)$), the authors argue that GOMA provides the first viable solution for scenarios where variance reduction is infeasible or where the noise structure is unbounded. The experiments confirm that GOMA is robust in both deterministic negative-comonotone settings and stochastic settings with multiplicative noise, outperforming baselines that diverge or stagnate under similar conditions.

Limitations and Future Directions
The authors acknowledge that closing the gap between GOMA's $O(1/\epsilon^4)$ complexity and the $O(1/\epsilon^2)$ lower bound without variance reduction remains an open question. Additionally, the current analysis is restricted to unconstrained problems; extending these guarantees to constrained settings (using the gap function) and broader operator classes (e.g., negative comonotone) are noted as future directions.