An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
Not on the map. Why?
Abstract (arXiv)
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 O(1/t2-2p) for the squared gradient norm, where p ∈ (1/2, 1), it remained an open problem whether the improved exact 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
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 16 of its 20 references that are in the map. First posted on arXiv 4 Apr 2026.
Builds on
16 of 20 references.
References · 16
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
- 2018A Reductions Approach to Fair Classificationcited by 587
- 2017Training GANs with Optimismcited by 217
- 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
- 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
- 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
- 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
- 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
- 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
- 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
- 2017Structured Optimal Transportcited by 31
- 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
4 more
- 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
- 2019ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problemscited by 18
- 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 11
- 2021Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problemscited by 6
Built on by
Citing papers per year: 2026: 3.
3 papers.