Accelerated and Stable Convergence with Anchored Generalized Optimistic Method

We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In the deterministic setting, GOMA achieves the optimal accelerated last-iterate rate $\mathcal{O}(1/k^2)$ on the squared gradient norm for monotone Lipschitz operators. In the stochastic setting with unbounded variance, a simplified single-call variant of GOMA achieves a last-iterate convergence rate of $\mathcal{O}(1/\sqrt{k})$ on the squared gradient norm. To the best of our knowledge, this is the first such guarantee for stochastic monotone Lipschitz VIs in the unconstrained setting without variance reduction or growing batches.

Many modern machine-learning systems are trained by balancing competing objectives rather than improving a single one: a generator against a critic in image-generating models, a model against an adversary, or agents adjusting their strategies in a game. Such problems are hard to solve. Standard methods often circle endlessly around a good solution instead of settling on it, and become even less reliable when the training signal is noisy, as it always is when learning from sampled data. We introduce GOMA, a simple and inexpensive method for these problems. It uses one lightweight update per step, making it cheap and well suited to streaming data, and adds a gentle pull toward its starting point that keeps training stable. We prove that GOMA converges as fast as theoretically possible without noise, and is the first of its kind to reliably converge under realistic, persistent noise.