An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
This work provides a theoretical improvement in convergence analysis for optimization algorithms, addressing a specific open problem in the field.
The paper resolves the open problem of achieving an improved last-iterate convergence rate of O(1/t) for the Anchored Gradient Descent Ascent algorithm in smooth convex-concave min-max problems, discovered autonomously by an AI system that writes formal proofs in Lean.
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