앵커드 그래디언트 디센트 어센트 알고리즘의 개선된 마지막 반복 수렴률

An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent

본 연구에서는 매끄러운 볼록-오목 최소-최대 문제에 대한 앵커드 그래디언트 디센트 어센트 알고리즘의 마지막 반복 수렴성을 분석합니다. 기존 연구에서는 제곱 그래디언트 노름에 대해 $ ext{O}(1/t^{2-2p})$의 마지막 반복 수렴률이 성립함을 보였으며, 여기서 $p ext{는 } (1/2, 1) ext{에 속합니다. 그러나, 개선된 정확한 $ ext{O}(1/t)$ 수렴률이 달성 가능한지에 대한 문제는 여전히 미해결 과제였습니다. 본 연구에서는 이 질문에 대해 긍정적인 답변을 제시합니다. 이 결과는 Lean으로 형식적 증명을 작성할 수 있는 AI 시스템에 의해 자율적으로 발견되었습니다. Lean 증명은 다음 링크에서 확인할 수 있습니다: https://github.com/google-deepmind/formal-conjectures/pull/3675/commits/a13226b49fd3b897f4c409194f3bcbeb96a08515

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