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

math.OCApr 4, 2026

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

Authors: Anja Surina, Arun Suggala, George Tsoukalas, Anton Kovsharov, Sergey Shirobokov, Francisco J. R. Ruiz, Pushmeet Kohli, Swarat Chaudhuri

Organizations: Google DeepMind

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 https://github.com/google-deepmind/formal-conjectures/pull/3675/commits/a13226b49fd3b897f4c409194f3bcbeb96a08515

Last-Iterate Convergence

Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.

See all 41 papers

A lower bound for stepsize-based acceleration of gradient descent
Aug 11, 2026Jianhao Ma, Yuxin ChenLearning Rate Scheduling Last-Iterate Convergence
Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania
Negative Stepsizes Make Gradient-Descent-Ascent Converge
May 2, 2025Henry Shugart, Jason M. AltschulerLearning Rate Scheduling Optimization Convergence Analysis
UPenn
Accelerating Min-Max Optimization via Power-Law Stepsizes
Jun 1, 2026Yue Wu, Weiqiang Zheng, Yang Cai +1Learning Rate Scheduling Last-Iterate Convergence
University of Southern California · Yale University

Aug 11, 2026J/K move · Enter open · S save

A lower bound for stepsize-based acceleration of gradient descent

Jianhao Ma, Yuxin Chen

Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania

Learning Rate Scheduling Last-Iterate Convergence Gradient Descent Accelerated Gradient Methods

Open paper AskPDF arXiv

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of

O(T^{-1})

(where

T

denotes the number of iterations) to

O\big(T^{-\log_2(1+\sqrt{2})}\big)

using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical

Ω(T^{-2})

benchmark for general first-order methods. In this work, we present a new lower bound of

Ω(T^{-1.9319})

for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal

O(T^{-2})

convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.

Abstract

Last-Iterate Convergence

Explore similar work

A lower bound for stepsize-based acceleration of gradient descent

Negative Stepsizes Make Gradient-Descent-Ascent Converge

Accelerating Min-Max Optimization via Power-Law Stepsizes