Source-linked AI summary
An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
Anja Surina, Arun Suggala, George Tsoukalas, Anton Kovsharov, Sergey Shirobokov, Francisco J. R. Ruiz, Pushmeet Kohli, Swarat Chaudhuri
TL;DR
The paper asks whether Anchored GDA can improve the prior O(1/t^{2-2p}) last-iterate squared-gradient guarantee to exact O(1/t) under standard assumptions. It directly analyzes the discrete dynamics, proves the improved rate, and reports that an AI system helped discover and formalize the result in Lean.
Problem
The open problem is whether Anchored GDA achieves exact O(1/t) last-iterate convergence for the squared gradient norm under standard assumptions.
Source: §1 · p. 2Method
The paper analyzes discrete iterate dynamics, derives a recurrence for consecutive differences, and connects bounded differences to the gradient norm.
Source: §3 · p. 3, §3.2 · p. 5, §3.3 · p. 6Results
Anchored GDA achieves the O(1/t) rate for the squared gradient norm under the stated assumptions and parameter schedules.
Source: §3 · p. 3Takeaways & Limitations
The result resolves the prior rate question affirmatively and was discovered with assistance from an AI system capable of formal Lean proofs.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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
1 Introduction
The paper studies Nash-equilibrium finding in convex-concave min-max games and asks whether Anchored GDA can attain an exact O(1/t) last-iterate rate. It answers affirmatively while addressing instability and noise concerns associated with standard and modified GDA methods.
Problem
- Min-max games seek Nash equilibria for objectives convex in x and concave in y, with applications in machine learning, statistics, and game theory.Examples include generative-adversarial training, adversarial robustness, reinforcement learning, optimal transport, and fairness in classification.Source: §1 · p. 1
Motivation
- Standard GDA can oscillate without converging even in simple bilinear games when using non-negative step sizes.The instability motivates algorithmic modifications for min-max optimization.Source: §1 · p. 1
- Extragradient and Optimistic GDA can become unstable with noisy stochastic gradients, requiring costly double-sampling or suffering noise accumulation.These methods are described as effective without stochasticity but problematic in practical noisy-gradient settings.Source: §1 · p. 1
Anchored GDA
- Anchored GDA adds a pull toward a fixed anchor, often the starting point, while retaining a single gradient call per iteration.Its anchoring mechanism provides variance reduction and stability in stochastic settings; related anchoring methods may require multiple gradient evaluations.Source: §1 · p. 2
Contribution
- Anchored GDA achieves the exact O(1/t) convergence rate for the squared gradient norm, resolving the open case left by prior O(1/t^{2-2p}) guarantees.The prior rate applied for p ∈ (1/2, 1), while the p = 1/2 case remained unresolved.Source: §1 · p. 2
2 Preliminaries
The paper formulates Anchored GDA for monotone, smooth operators with an existing saddle point and specifies the anchored update from an initial iterate. It also recalls the parameter schedules used in the earlier convergence analysis.
Notation
- The gradient operator maps the joint space Z = R^n × R^m to itself, and the analysis uses the L2 norm.The objective is continuously differentiable and the target is a saddle point z* in Z.Source: §2 · p. 2
Assumptions
- The analysis assumes a monotone, Lipschitz-continuous gradient operator and existence of at least one saddle point.The saddle-point condition is expressed as G(z*) = 0, and uniqueness is not required by the stated assumptions.Source: §2 · p. 2
Algorithm
- Anchored GDA starts from z0 and modifies the standard gradient step with an anchoring term in the iterate update.The iterates are represented as zt = (xt, yt).Source: §2 · p. 2
Prior schedule
- Earlier O(1/t^{2-2p}) guarantees used parameter schedules αt = (1 − p)/(t + 1)^p and βt = (1 − p)γ for p ∈ (1/2, 1).These schedules are recalled as part of the prior analysis of Anchored GDA.Source: §2 · p. 2
3 Main Result
The paper proves an O(1/t) last-iterate rate for Anchored GDA using distinct parameter schedules and a discrete-time analysis. The proof bounds iterates, controls consecutive differences, and connects these bounds to the gradient norm.
3 Main Result
- The schedules α_t = 1/(K√(t + γ)) and β_t = γ/(t + γ) differ from those used in prior analyses.The schedules are selected to obtain the improved rate.Source: §3 · p. 3
- Theorem 3.1 establishes an O(1/t) rate for the squared gradient norm of the last iterate under the stated assumptions and parameter schedules.The result holds for all t ≥1 and does not require a unique saddle point.Source: §3 · p. 3
- Unlike prior ODE-based analyses, the proof directly studies the discrete dynamics through a recurrence for consecutive iterate differences.This discrete recurrence is the bridge between stability estimates and last-iterate convergence.Source: §3 · p. 3
3.1 Step 1: Bounded Iterates
- The proof first bounds the distance of each iterate from any saddle point z⋆ and then bounds its distance from the anchor.The bounded-iterate step uses the algorithm update, monotonicity, convexity of the squared norm, and Lipschitz continuity.Source: §3.1 · pp. 3–4
3.2 Step 2: Bounded Iterate Differences
- Consecutive iterate differences satisfy ∥z_{t+1} − z_t∥ ≤ E/(t + γ), obtained from an exact difference recurrence and induction.The recurrence controls gradient differences using monotonicity and Lipschitz continuity, with γ ≥ 2 used in the non-asymptotic bounds.Source: §3.2 · pp. 4–5
3.3 Step 3: Last-Iterate Convergence
- The final step isolates G(z_t) from the update rule and substitutes the bounded iterate distance and consecutive-difference estimates to obtain the O(1/t) squared-gradient rate.The resulting gradient bound scales as 1/√(t + γ), which yields the stated squared-norm rate after squaring.Source: §3.3 · p. 6
4 Note on AI Contribution and Formal Verification
The proof was discovered by an AI agent for formal mathematics developed at Google DeepMind and is presented through a natural-language version of the Lean proof.
4 Note on AI Contribution and Formal Verification
- An AI agent discovered the proof, while Gemini 3.1 Pro assisted its presentation and informalization.The authors state that details of the agent and its deployment will be released in a later paper.Source: §4 · p. 6
A Asymptotic Bounds for A and |Eerr|
Taylor expansions characterize the asymptotic terms and show that the error magnitude decays as O(1/t^2). The resulting contraction factor is bounded by the factor used in the proof.
Asymptotic expansions
- The ratio terms are expanded with Taylor series to characterize their behavior as t → ∞.The expansions include the ratio, β_t, and the approximation t+1K2 ≈ 1/(t+γ).Source: A Asymptotic Bounds for A and |Eerr| · p. 8
Contraction factor
- The contraction factor is 1 − γ/(t+γ), which is below the proof’s bound 1 − 1.15/(t+γ+1) when γ ≥ 2.The comparison follows from taking the square root and applying a Taylor expansion.Source: A Asymptotic Bounds for A and |Eerr| · p. 8
Error decomposition
- The separate expansions of the ratio contribution and β_{t+1} − β_t combine to produce the stated Eerr expansion.The difference satisfies β_{t+1} − β_t = −γ/[(t+γ)(t+1+γ)] with its corresponding asymptotic expansion.Source: A Asymptotic Bounds for A and |Eerr| · p. 8
Asymptotic error bound
- |Eerr| ≈ γ^2/t^2 = O(1/t^2), confirming the error term’s asymptotic decay.The expansion gives Eerr = −γ^2/[2(t+γ)^2] + 5γ/[8(t+γ)^3] plus higher-order terms.Source: A Asymptotic Bounds for A and |Eerr| · p. 8