证明了锚定梯度下降上升法的最后迭代收敛率可达到1/t
An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
- 提出新分析方法，突破原有收敛速率限制
- 在平滑凸凹问题下实现1/t的最优收敛率
- 由AI系统自主完成形式化证明，可信度高
本文研究锚定梯度下降上升算法在平滑凸凹极小极大问题中的最后迭代收敛性。此前工作表明，梯度范数平方的收敛率为$\mathcal{O}(1/t^{2-2p})$，其中$ p \in (1/2, 1)$，但是否能实现改进的精确$\mathcal{O}(1/t)$速率仍是未解之谜。本文正面解答此问题。该结论由具备在Lean中撰写形式化证明能力的AI系统自主发现。相关形式化证明代码可于https://github.com/google-deepmind/formal-conjectures/pull/3675/commits/a13226b49fd3b897f4c409194f3bcbeb96a08515获取。
原文摘要 · Abstract (English)
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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。