An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914446027259904 |
|---|---|
| author | Surina, Anja Suggala, Arun Tsoukalas, George Kovsharov, Anton Shirobokov, Sergey Ruiz, Francisco J. R. Kohli, Pushmeet Chaudhuri, Swarat |
| author_facet | Surina, Anja Suggala, Arun Tsoukalas, George Kovsharov, Anton Shirobokov, Sergey Ruiz, Francisco J. R. Kohli, Pushmeet Chaudhuri, Swarat |
| contents | 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 |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03782 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent Surina, Anja Suggala, Arun Tsoukalas, George Kovsharov, Anton Shirobokov, Sergey Ruiz, Francisco J. R. Kohli, Pushmeet Chaudhuri, Swarat Optimization and Control Artificial Intelligence 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 |
| title | An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent |
| topic | Optimization and Control Artificial Intelligence |
| url | https://arxiv.org/abs/2604.03782 |