GOMA achieves optimal last-iterate O(1/k²) convergence in deterministic monotone Lipschitz VIs and O(1/√k) in stochastic unbounded-variance settings without variance reduction.
An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
We analyze the last-iterate convergence of the Anchored Gradient Descent Ascent algorithm for smooth convex-concave min-max problems. While previous work established a last-iterate rate of $\mathcal{O}(1/t^{2-2p})$ for the squared gradient norm, where $p \in (1/2, 1)$, it remained an open problem whether the improved exact $\mathcal{O}(1/t)$ rate is achievable. In this work, we resolve this question in the affirmative. This result was discovered autonomously by an AI system capable of writing formal proofs in Lean. The Lean proof can be accessed at https://github.com/google-deepmind/formal-conjectures/pull/3675/commits/a13226b49fd3b897f4c409194f3bcbeb96a08515
years
2026 4representative citing papers
An LLM-based agent with Lean verification autonomously solved multiple open Erdős problems and OEIS conjectures in the first large-scale test.
Anchoring is realized as operator-side Tikhonov regularization before applying the base method, recovering Halpern iteration from Picard and producing new regularized forward-step, EG, and PEG variants with O(1/k) or O(1/sqrt(k)) residual rates under monotone Lipschitz assumptions.
Anchored gradient descent achieves O(1/sqrt(T)) last-iterate convergence for monotone inclusions 0 in F(z) + A(z) by extending prior unconstrained proofs.
citing papers explorer
-
Accelerated and Stable Convergence with Anchored Optimistic Method
GOMA achieves optimal last-iterate O(1/k²) convergence in deterministic monotone Lipschitz VIs and O(1/√k) in stochastic unbounded-variance settings without variance reduction.
-
Advancing Mathematics Research with AI-Driven Formal Proof Search
An LLM-based agent with Lean verification autonomously solved multiple open Erdős problems and OEIS conjectures in the first large-scale test.
-
A Unifying View of Anchoring via Operator-Side Tikhonov Regularization
Anchoring is realized as operator-side Tikhonov regularization before applying the base method, recovering Halpern iteration from Picard and producing new regularized forward-step, EG, and PEG variants with O(1/k) or O(1/sqrt(k)) residual rates under monotone Lipschitz assumptions.
-
Last-Iterate Convergence of Anchored Gradient Descent
Anchored gradient descent achieves O(1/sqrt(T)) last-iterate convergence for monotone inclusions 0 in F(z) + A(z) by extending prior unconstrained proofs.