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 this https URL
Abstract (translated)
我们分析了锚定梯度下降上升算法在光滑凸凹极小极大问题中的最后迭代收敛性。先前工作已证明，当 $p \in (1/2, 1)$ 时，该算法关于平方梯度范数的最后迭代收敛率为 $\mathcal{O}(1/t^{2-2p})$，但更优的精确 $\mathcal{O}(1/t)$ 收敛率是否可达仍是一个未解问题。本研究肯定地回答了这一问题。该成果由一个能够用 Lean 语言撰写形式化证明的 AI 系统自主发现。Lean 证明可在此 https 链接获取。
URL
https://arxiv.org/abs/2604.03782
