Last-iterate convergence of anchored gradient descent–ascent

For smooth convex-concave objectives with a saddle point and monotone K-Lipschitz gradient operator, can anchored gradient descent-ascent attain squared-gradient residual O(1/t) at its last iterate? The schedule under study is αₜ=1/(K√(t+γ)), βₜ=γ/(t+γ), with γ≥2.

Why it matters and what counts as progress

Why it matters: The O(1/t) target closes the endpoint gap left by earlier anchored-gradient rates under the same smoothness and monotonicity assumptions.

What counts as progress: Prove the O(1/t) last-iterate rate under these assumptions, improve its constants, or weaken the assumptions without losing the rate.

How the problem developed

4 Apr 2026 · Convergence rate [1]
Autonomous Lean-capable AI system; paper by Anja Surina et al. Resolved affirmatively the open question whether anchored gradient descent–ascent attains an exact O(1/t) squared-gradient last-iterate rate for smooth convex-concave min-max problems.

AI contribution

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

For smooth convex-concave objectives with a monotone K-Lipschitz gradient operator and a saddle point, the schedule αₜ=1/(K√(t+γ)), βₜ=γ/(t+γ), γ≥2, gives squared-gradient residual O(1/t) at the last iterate of anchored gradient descent-ascent.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (Lean 4)

Human understandingFull