Paper deep dive
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
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/10/2026, 2:18:10 AM
Summary
This paper establishes an improved last-iterate convergence rate of O(1/t) for the Anchored Gradient Descent Ascent (GDA) algorithm in smooth convex-concave min-max problems. By utilizing a novel parameter schedule and direct discrete-time analysis, the authors resolve an open problem regarding the optimality of the convergence rate, with the proof verified using an AI system capable of formalizing proofs in Lean.
Entities (4)
Relation Signals (2)
Anchored Gradient Descent Ascent → achievesconvergencerate → O(1/t)
confidence 100% · In this work, we resolve this question in the affirmative... proving that the algorithm does indeed achieve the O(1/t) convergence rate
Lean → usedforverificationof → Anchored Gradient Descent Ascent
confidence 95% · The Lean proof can be accessed at this link.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 this https URL
Tags
Links
- Source: https://arxiv.org/abs/2604.03782v1
- Canonical: https://arxiv.org/abs/2604.03782v1
Trouble viewing inline? Open PDF directly →
Full Text
26,160 characters extracted from source content.
Expand or collapse full text
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 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 (1/t2−2p)O(1/t^2-2p) for the squared gradient norm, where p∈(1/2,1)p∈(1/2,1), it remained an open problem whether the improved exact (1/t)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 this link. 1 Introduction In this work, we study the problem of finding Nash equilibria of min-max games of the form minxmaxyL(x,y), _x _yL(x,y), where L(⋅,y):ℝn→ℝL(·,y):R^n is convex and L(x,⋅):ℝm→ℝL(x,·):R^m is concave. Min-max games arise naturally across game theory, machine learning, and statistics, with practical applications ranging from training generative adversarial networks (Goodfellow et al., 2014) to adversarial robustness (Madry et al., 2018), reinforcement learning (Du et al., 2017), optimal transport (Alvarez-Melis et al., 2018), and fairness in classification (Agarwal et al., 2018). One of the most popular algorithms for solving such problems is Gradient Descent Ascent (GDA). At each step t, the algorithm updates the current value of the variables (xtx_t, yty_t) following the steepest descent (ascent) direction, i.e., xt+1=xt−αt∇xL(xt,yt),yt+1=yt+αt∇yL(xt,yt),x_t+1=x_t- _t _xL(x_t,y_t),\ y_t+1=y_t+ _t _yL(x_t,y_t), for some step size parameter αt>0 _t>0, typically set to the same value for both variables x and y. However, with non-negative step-sizes, GDA is known to exhibit oscillatory behavior, where the updates do not lead to convergence of x and y, even in simple bilinear games (Daskalakis et al., 2018; Shugart and Altschuler, 2025). To address this instability, various algorithmic modifications have been proposed, such as the Extragradient method (Korpelevich, 1976; Hsieh et al., 2019; Cai et al., 2022) and the Optimistic Gradient Descent Ascent algorithm (Popov, 1980; Golowich et al., 2020; Cai and Zheng, 2022; Gorbunov et al., 2022). While effective in the absence of stochasticity, these methods can be unstable in practical machine learning settings where we only have access to noisy stochastic gradients—often requiring expensive double-sampling to maintain unbiased estimates or suffering from noise accumulation. Recently, Anchored GDA (Ryu et al., 2019) has emerged as a compelling single-call alternative, providing natural variance reduction and stability in stochastic settings. Anchoring finds its heritage in Halpern iteration (Halpern, 1967) and modifies standard GDA by adding a term that pulls the current iterate toward a fixed “anchor” (often the starting point (x0,y0)(x_0,y_0)): xt+1=xt−αt∇xL(xt,yt)+βt(x0−xt),yt+1=yt+αt∇yL(xt,yt)+βt(y0−yt),x_t+1=x_t- _t _xL(x_t,y_t)+ _t(x_0-x_t), 8.0pt\ y_t+1=y_t+ _t _yL(x_t,y_t)+ _t(y_0-y_t), where βt _t is an anchoring parameter. While our work focuses on single-call Anchoring GDA, anchoring lineage also includes algorithms that require multiple gradient evaluations per iteration (Diakonikolas, 2020; Yoon and Ryu, 2021; Lee and Kim, 2021a, b; Chen and Luo, 2024). For a training horizon of t iterations, Ryu et al. (2019) established last-iterate convergence of Anchored GDA (see their Theorem 3), showing a rate of (1/t2−2p)O(1/t^2-2p) in the squared gradient norm for p∈(1/2,1)p∈(1/2,1), which is strictly slower than (1/t)O(1/t). The case p=1/2p=1/2 is not covered by their analysis, leaving open the following question: can Anchored GDA achieve the (1/t)O(1/t) convergence rate under the standard assumptions, or is the rate fundamentally slower, for instance (logct/t)O( ^ct/t) for some constant c>0c>0? In this work, we use an AI system to resolve this question by proving that the algorithm does indeed achieve the (1/t)O(1/t) convergence rate (see Section 4 for more information on AI contributions to the effort). 2 Preliminaries In this section, we recapitulate the Anchored GDA algorithm (Ryu et al., 2019). Notation. Let =ℝn×ℝmZ=R^n×R^m. Let L:→ℝL:Z be a continuously differentiable objective function. The goal is to find a saddle point z∗=(x∗,y∗)∈z^*=(x^*,y^*) such that: L(x∗,y)≤L(x∗,y∗)≤L(x,y∗)∀x∈ℝn,y∈ℝm.L(x^*,y)≤ L(x^*,y^*)≤ L(x,y^*) ∀ x ^n,y ^m. The gradient operator G:→G:Z is given by: G(z)=(∇xL(z),−∇yL(z)).G(z)=( _xL(z),- _yL(z)). Let ∥⋅∥\|·\| denote the L2L_2 norm. Assumptions. Throughout this paper, we assume the following: 1. Monotonicity: the operator G satisfies ⟨G(z)−G(w),z−w⟩≥0 G(z)-G(w),z-w ≥ 0 for all z,w∈z,w . 2. Smoothness (Lipschitz continuity): there exists a constant K>0K>0 such that ‖G(z)−G(w)‖≤K‖z−w‖\|G(z)-G(w)\|≤ K\|z-w\| for all z,w∈z,w . 3. Existence of a saddle point: there exists at least one solution z∗∈z^* such that G(z∗)=0G(z^*)=0. Algorithm: The Anchored GDA update rule modifies the standard gradient step with an anchoring term. Starting from an initial point z0∈Zz_0∈ Z, the update rule for iterates zt=(xt,yt)z_t=(x_t,y_t) is defined as: zt+1=zt−αtG(zt)+βt(z0−zt).z_t+1=z_t- _tG(z_t)+ _t(z_0-z_t). To prove the convergence rate of (1/t2−2p)O(1/t^2-2p) for p∈(1/2,1)p∈(1/2,1), Ryu et al. (2019) chose the parameter schedules as αt=1−p(t+1)p,βt=(1−p)γt+1, _t= 1-p(t+1)^p, _t= (1-p)γt+1, with γ≥2γ≥ 2. 3 Main Result To achieve the (1/t)O(1/t) convergence rate of Anchored GDA, we set different parameter schedules than those considered by Ryu et al. (2019): αt=1Kt+γ,βt=γt+γ, _t= 1K t+γ, _t= γt+γ, with γ≥2γ≥ 2. Theorem 3.1 (Last-Iterate Convergence). Under the assumptions outlined in Section 2 and the parameter schedules described above, for all t≥1t≥ 1, the squared gradient norm of the last iterate satisfies: ‖G(zt)‖2≤Ct,\|G(z_t)\|^2≤ Ct, where C=K2(E+γD)2C=K^2(E+γ D)^2, D=(12+1)‖z0−z⋆‖D=( 12+1)\|z_0-z \|, K is the Lipschitz constant, and E≥0E≥ 0 is a constant depending on γ, ‖z0−z⋆‖\|z_0-z \| and ‖z2−z1‖\|z_2-z_1\| (see Lemma 3.5 for precise definition). The proof holds for any saddle point z⋆z satisfying G(z⋆)=0G(z )=0; in particular, the result does not require uniqueness. The proof of Theorem 3.1 proceeds in three steps: • Boundedness of iterates: Bounding the distance of the iterates to the saddle point z⋆z . • Iterate stability: Bounding the differences between consecutive iterates. • Final convergence rate: Establishing the (1/t)O(1/t) rate for the squared gradient norm. Prior convergence guarantees (Ryu et al., 2019) were derived by modeling the algorithm as a continuous-time ordinary differential equation (ODE). In contrast, our proof departs from the continuous-time analysis by directly analyzing the discrete dynamics and establishing a recurrence relation for consecutive iterate differences. 3.1 Step 1: Bounded Iterates We first establish that the iterates remain within a bounded distance from the optimum z⋆z . Lemma 3.2. The squared distance to any optimum z⋆z satisfies: ‖zt+1−z⋆‖2≤(1−βt+1.5αt2K2)‖zt−z⋆‖2+(βt+2βt2)‖z0−z⋆‖2.\|z_t+1-z \|^2≤(1- _t+1.5 _t^2K^2)\|z_t-z \|^2+( _t+2 _t^2)\|z_0-z \|^2. Proof. Let u=zt−z⋆u=z_t-z and v=z0−z⋆v=z_0-z . From the algorithm update rule, we have zt+1−z⋆=zt−αtG(zt)+βt(z0−zt)−z∗=w−αtG(zt)z_t+1-z =z_t- _tG(z_t)+ _t(z_0-z_t)-z^*=w- _tG(z_t), where w=(1−βt)u+βtvw=(1- _t)u+ _tv. Taking the squared norm gives: ‖zt+1−z⋆‖2=‖w‖2−2αt⟨w,G(zt)⟩+αt2‖G(zt)‖2.\|z_t+1-z \|^2=\|w\|^2-2 _t w,G(z_t) + _t^2\|G(z_t)\|^2. Expanding the cross term yields: −2αt⟨w,G(zt)⟩=−2αt(1−βt)⟨u,G(zt)⟩−2αtβt⟨v,G(zt)⟩.-2 _t w,G(z_t) =-2 _t(1- _t) u,G(z_t) -2 _t _t v,G(z_t) . By monotonicity, ⟨u,G(zt)⟩≥0 u,G(z_t) ≥ 0, so the first term is non-positive. For the second term, we start with the non-negativity of the squared norm of the vector 2βtv+αtG(zt)2 _tv+ _tG(z_t). Expanding ‖2βtv+αtG(zt)‖2≥0\|2 _tv+ _tG(z_t)\|^2≥ 0 yields −4αtβt⟨v,G(zt)⟩≤4βt2‖v‖2+αt2‖G(zt)‖2-4 _t _t v,G(z_t) ≤ 4 _t^2\|v\|^2+ _t^2\|G(z_t)\|^2, which proves −2αtβt⟨v,G(zt)⟩≤2βt2‖v‖2+0.5αt2‖G(zt)‖2.-2 _t _t v,G(z_t) ≤ 2 _t^2\|v\|^2+0.5 _t^2\|G(z_t)\|^2. Finally, using the convexity of the squared norm we can expand ‖w‖2≤(1−βt)‖u‖2+βt‖v‖2\|w\|^2≤(1- _t)\|u\|^2+ _t\|v\|^2. Bounding ‖G(zt)‖2≤K2‖u‖2\|G(z_t)\|^2≤ K^2\|u\|^2 using Lipschitz continuity of G, and summing the terms completes the proof. ∎ Lemma 3.3. For all t≥0t≥ 0, and any optimum z⋆z , the sequence satisfies ‖zt−z⋆‖2≤12‖z0−z⋆‖2.\|z_t-z \|^2≤ 12\|z_0-z \|^2. Consequently, there exists a constant D=(12+1)‖z0−z⋆‖≥0D=( 12+1)\|z_0-z \|≥ 0 such that ‖zt−z0‖≤D\|z_t-z_0\|≤ D for all t. Proof. We proceed by induction on t. Assume ‖zt−z⋆‖2≤12‖z0−z⋆‖2\|z_t-z \|^2≤ 12\|z_0-z \|^2. Substituting this into Lemma 3.2, we require the multiplier of ‖z0−z⋆‖2\|z_0-z \|^2 to be less than or equal to 1212: 12(1−βt+1.5αt2K2)+(βt+2βt2)≤12⟹−11βt+18αt2K2+2βt2≤0.12(1- _t+1.5 _t^2K^2)+( _t+2 _t^2)≤ 12 -11 _t+18 _t^2K^2+2 _t^2≤ 0. Substituting the step size schedules αt2K2=1t+γ _t^2K^2= 1t+γ and βt=γt+γ _t= γt+γ, we get: −11γt+γ+18t+γ+2γ2(t+γ)2≤0⟹−11γ(t+γ)+18(t+γ)+2γ2≤0. -11γt+γ+ 18t+γ+ 2γ^2(t+γ)^2≤ 0 -11γ(t+γ)+18(t+γ)+2γ^2≤ 0. Given our assumption γ≥2γ≥ 2, inequality 18t+18γ≤11γt+9γ218t+18γ≤ 11γ t+9γ^2 holds for any t≥0t≥ 0 . The bound on the distance to the anchor ‖zt−z0‖\|z_t-z_0\| follows from the triangle inequality: ‖zt−z0‖≤‖zt−z⋆‖+‖z⋆−z0‖\|z_t-z_0\|≤\|z_t-z \|+\|z -z_0\|. ∎ 3.2 Step 2: Bounded Iterate Differences Next, we bound the magnitude of consecutive iterate differences dt=zt+1−ztd_t=z_t+1-z_t. Lemma 3.4. The difference between consecutive iterates can be written exactly as: zt+2−zt+1=A⋅(zt+1−zt)−αt+1(G(zt+1)−G(zt))+Eerr⋅(z0−zt),z_t+2-z_t+1=A·(z_t+1-z_t)- _t+1(G(z_t+1)-G(z_t))+E_err·(z_0-z_t), where A=1−βt+1−αt−αt+1αtA=1- _t+1- _t- _t+1 _t and Eerr=αt−αt+1αtβt+βt+1−βtE_err= _t- _t+1 _t _t+ _t+1- _t. Proof. From the algorithm’s update rule we have: zt+2=zt+1−αt+1G(zt+1)+βt+1(z0−zt+1).z_t+2=z_t+1- _t+1G(z_t+1)+ _t+1(z_0-z_t+1). Rearranging and introducing the gradient difference yields zt+2−zt+1=−αt+1(G(zt+1)−G(zt))−αt+1G(zt)+βt+1(z0−zt+1).z_t+2-z_t+1=- _t+1(G(z_t+1)-G(z_t))- _t+1G(z_t)+ _t+1(z_0-z_t+1). Substituting G(zt)G(z_t) in the expression with 1αt(zt−zt+1)+βtαt(z0−zt) 1 _t(z_t-z_t+1)+ _t _t(z_0-z_t) derived from the update rule zt+1=zt−αtG(zt)+βt(z0−zt)z_t+1=z_t- _tG(z_t)+ _t(z_0-z_t), and rewriting z0−zt+1=(z0−zt)−(zt+1−zt)z_0-z_t+1=(z_0-z_t)-(z_t+1-z_t), we obtain: zt+2−zt+1 z_t+2-z_t+1 =−αt+1(G(zt+1)−G(zt))+αt+1αt(zt+1−zt)−αt+1βtαt(z0−zt) =- _t+1(G(z_t+1)-G(z_t))+ _t+1 _t(z_t+1-z_t)- _t+1 _t _t(z_0-z_t) +βt+1(z0−zt)−βt+1(zt+1−zt). + _t+1(z_0-z_t)- _t+1(z_t+1-z_t). Grouping the terms by (zt+1−zt)(z_t+1-z_t) and (z0−zt)(z_0-z_t) gives: zt+2−zt+1=(αt+1αt−βt+1)(zt+1−zt)−αt+1(G(zt+1)−G(zt))+(βt+1−αt+1αtβt)(z0−zt).z_t+2-z_t+1= ( _t+1 _t- _t+1 )(z_t+1-z_t)- _t+1(G(z_t+1)-G(z_t))+ ( _t+1- _t+1 _t _t )(z_0-z_t). Using the identity αt+1αt=1−αt−αt+1αt _t+1 _t=1- _t- _t+1 _t, the coefficient of (zt+1−zt)(z_t+1-z_t) evaluates exactly to A: αt+1αt−βt+1=1−βt+1−αt−αt+1αt=A. _t+1 _t- _t+1=1- _t+1- _t- _t+1 _t=A. Applying the same identity to the coefficient of (z0−zt)(z_0-z_t) gives EerrE_err: βt+1−(1−αt−αt+1αt)βt=αt−αt+1αtβt+βt+1−βt=Eerr. _t+1- (1- _t- _t+1 _t ) _t= _t- _t+1 _t _t+ _t+1- _t=E_err. ∎ Lemma 3.5. There exists a constant E≥0E≥ 0 such that for all t≥1t≥ 1: ‖zt+1−zt‖≤Et+γ.\|z_t+1-z_t\|≤ Et+γ. Proof. Let dt=zt+1−ztd_t=z_t+1-z_t. By Lemma 3.4 and the triangle inequality, we have: ‖dt+1‖≤‖Adt−αt+1(G(zt+1)−G(zt))‖+|Eerr|‖z0−zt‖.\|d_t+1\|≤\|Ad_t- _t+1(G(z_t+1)-G(z_t))\|+|E_err|\|z_0-z_t\|. Expanding the squared norm of the first term yields: ‖Adt−αt+1(G(zt+1)−G(zt))‖2=A2‖dt‖2−2Aαt+1⟨G(zt+1)−G(zt),dt⟩+αt+12‖G(zt+1)−G(zt)‖2.\|Ad_t- _t+1(G(z_t+1)-G(z_t))\|^2=A^2\|d_t\|^2-2A _t+1 G(z_t+1)-G(z_t),d_t + _t+1^2\|G(z_t+1)-G(z_t)\|^2. By A≥0A≥ 0 and the monotonicity of G, the cross-term is non-positive. By the Lipschitz continuity of G, the squared gradient difference is bounded by K2‖dt‖2K^2\|d_t\|^2. This yields: ‖Adt−αt+1(G(zt+1)−G(zt))‖2≤(A2+αt+12K2)‖dt‖2.\|Ad_t- _t+1(G(z_t+1)-G(z_t))\|^2≤(A^2+ _t+1^2K^2)\|d_t\|^2. Taking the square root gives a contraction factor of A2+αt+12K2 A^2+ _t+1^2K^2. Substituting the parameter schedules, we can bound the contraction factor and the error coefficient for t≥1t≥ 1 and γ≥2γ≥ 2: A2+αt+12K2≤1−1.15t+1+γ,and|Eerr|≤γ(t+γ)2. A^2+ _t+1^2K^2≤ 1- 1.15t+1+γ, |E_err|≤ γ(t+γ)^2. In Appendix A, we provide a asymptotic argument for why the above two inequalities hold. We point the reader to the Lean proof for a detailed derivation of the non-asymptotic bounds. Since ‖z0−zt‖≤D\|z_0-z_t\|≤ D by Lemma 3.3, we obtain the recurrence relation: ‖dt+1‖≤(1−1.15t+1+γ)‖dt‖+γD(t+γ)2.\|d_t+1\|≤ (1- 1.15t+1+γ )\|d_t\|+ γ D(t+γ)^2. By induction, this sequence implies the existence of a constant E≥0E≥ 0 such that ‖dt‖≤Et+γ\|d_t\|≤ Et+γ for all t≥1t≥ 1. To establish this, let E=max(‖d1‖(1+γ),20γD)E= (\|d_1\|(1+γ),20γ D). For the base case t=1t=1, the condition is satisfied directly by E≥‖d1‖(1+γ)E≥\|d_1\|(1+γ). For the inductive step, assume ‖dt‖≤Et+γ\|d_t\|≤ Et+γ. Substituting this into the recurrence relation gives: ‖dt+1‖ \|d_t+1\| ≤(1−1.15t+1+γ)Et+γ+γD(t+γ)2 ≤ (1- 1.15t+1+γ ) Et+γ+ γ D(t+γ)^2 =t+γ−0.15t+1+γ⋅Et+γ+γD(t+γ)2. = t+γ-0.15t+1+γ· Et+γ+ γ D(t+γ)^2. To complete the induction, we must show ‖dt+1‖≤Et+1+γ\|d_t+1\|≤ Et+1+γ. We require: t+γ−0.15t+γE+γD(t+1+γ)(t+γ)2 t+γ-0.15t+γE+ γ D(t+1+γ)(t+γ)^2 ≤E, ≤ E, (1−0.15t+γ)E+γDt+γ(1+1t+γ) (1- 0.15t+γ )E+ γ Dt+γ (1+ 1t+γ ) ≤E. ≤ E. Subtracting (1−0.15t+γ)E (1- 0.15t+γ )E and multiplying by t+γt+γ on both sides gives: γD(1+1t+γ) γ D (1+ 1t+γ ) ≤0.15E. ≤ 0.15E. For t≥1t≥ 1 and γ≥2γ≥ 2, we have t+γ≥3t+γ≥ 3, which implies 1+1t+γ≤431+ 1t+γ≤ 43. Thus, setting E≥20γDE≥ 20γ D is sufficient to show this inequality holds, completing the proof. ∎ 3.3 Step 3: Last-Iterate Convergence Finally, we tie the bounded differences back to the gradient norm to establish the (1/t)O(1/t) rate. Proof of Theorem 3.1. By algebraically rearranging the algorithm’s update rule zt+1=zt−αtG(zt)+βt(z0−zt)z_t+1=z_t- _tG(z_t)+ _t(z_0-z_t), we can isolate the operator evaluated at the last iterate: αtG(zt)=(zt−zt+1)+βt(z0−zt). _tG(z_t)=(z_t-z_t+1)+ _t(z_0-z_t). Taking the norm and dividing by αt _t yields: ‖G(zt)‖≤1αt‖zt+1−zt‖+βtαt‖z0−zt‖.\|G(z_t)\|≤ 1 _t\|z_t+1-z_t\|+ _t _t\|z_0-z_t\|. We now substitute our explicit parameter schedules αt=1Kt+γ _t= 1K t+γ and βt=γt+γ _t= γt+γ: ‖G(zt)‖≤Kt+γ‖zt+1−zt‖+Kγt+γ‖z0−zt‖.\|G(z_t)\|≤ K t+γ\|z_t+1-z_t\|+ Kγ t+γ\|z_0-z_t\|. From Lemma 3.5, we have ‖zt+1−zt‖≤Et+γ\|z_t+1-z_t\|≤ Et+γ. From Lemma 3.3, we have ‖z0−zt‖≤D\|z_0-z_t\|≤ D. Substituting these bounds into the equation gives: ‖G(zt)‖≤KEt+γ+KγDt+γ=KE+KγDt+γ.\|G(z_t)\|≤ KE t+γ+ Kγ D t+γ= KE+Kγ D t+γ. Squaring both sides completes the proof: ‖G(zt)‖2≤(KE+KγD)2t+γ.\|G(z_t)\|^2≤ (KE+Kγ D)^2t+γ. ∎ 4 Note on AI Contribution and Formal Verification The proof presented in this manuscript was discovered by an AI agent for formal mathematics developed at Google DeepMind. We will release the details of the agent, as well as the specific way it was deployed in the present domain, in a later paper. We present a natural language version of the Lean proof for improved readability. Gemini 3.1 Pro was used as an assistant in the presentation and informalization. References A. Agarwal, A. Beygelzimer, M. Dudík, J. Langford, and H. Wallach (2018) A reductions approach to fair classification. In International conference on machine learning, p. 60–69. Cited by: §1. D. Alvarez-Melis, T. Jaakkola, and S. Jegelka (2018) Structured optimal transport. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, A. Storkey and F. Perez-Cruz (Eds.), Proceedings of Machine Learning Research, Vol. 84, p. 1771–1780. External Links: Link Cited by: §1. Y. Cai, A. Oikonomou, and W. Zheng (2022) Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. arXiv preprint arXiv:2204.09228. Cited by: §1. Y. Cai and W. Zheng (2022) Accelerated single-call methods for constrained min-max optimization. arXiv preprint arXiv:2210.03096. Cited by: §1. L. Chen and L. Luo (2024) Near-optimal algorithms for making the gradient small in stochastic minimax optimization. Journal of Machine Learning Research 25 (387), p. 1–44. External Links: Link Cited by: §1. C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng (2018) Training gans with optimism. In International Conference on Learning Representations (ICLR), Cited by: §1. J. Diakonikolas (2020) Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. In Proceedings of Thirty Third Conference on Learning Theory, J. Abernethy and S. Agarwal (Eds.), Proceedings of Machine Learning Research, Vol. 125, p. 1428–1451. Cited by: §1. S. S. Du, J. Chen, L. Li, L. Xiao, and D. Zhou (2017) Stochastic variance reduction methods for policy evaluation. In International conference on machine learning, p. 1049–1058. Cited by: §1. N. Golowich, S. Pattathil, and C. Daskalakis (2020) Tight last-iterate convergence rates for no-regret learning in multi-player games. arXiv preprint arXiv:2010.13724. Cited by: §1. I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio (2014) Generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1. E. Gorbunov, A. Taylor, and G. Gidel (2022) Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Advances in neural information processing systems 35, p. 21858–21870. Cited by: §1. B. Halpern (1967) Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society 73, p. 957–961. External Links: Link Cited by: §1. Y. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos (2019) On the convergence of single-call stochastic extra-gradient methods. Advances in Neural Information Processing Systems 32. Cited by: §1. G. M. Korpelevich (1976) The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody 12 (4), p. 747–756. Cited by: §1. S. Lee and D. Kim (2021a) Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. Advances in Neural Information Processing Systems 34, p. 22588–22600. Cited by: §1. S. Lee and D. Kim (2021b) Semi-anchored multi-step gradient descent ascent method for structured nonconvex-nonconcave composite minimax problems. arXiv preprint arXiv:2105.15042. Cited by: §1. A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu (2018) Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), Cited by: §1. L. D. Popov (1980) A modification of the arrow-hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR 28 (5), p. 845–848. Cited by: §1. E. K. Ryu, K. Yuan, and W. Yin (2019) ODE analysis of stochastic gradient methods with optimism and anchoring for minimax problems. arXiv preprint arXiv:1905.10899. Cited by: §1, §1, §2, §2, §3, §3. H. Shugart and J. M. Altschuler (2025) Negative stepsizes make gradient-descent-ascent converge. arXiv preprint arXiv:2505.01423. Cited by: §1. T. Yoon and E. K. Ryu (2021) Accelerated algorithms for smooth convex-concave minimax problems with o (1/kˆ 2) rate on squared gradient norm. In International conference on machine learning, p. 12098–12109. Cited by: §1. Appendix A Asymptotic Bounds for A and |Eerr||E_err| The asymptotic behavior of the terms A2+αt+12K2 A^2+ _t+1^2K^2 and |Eerr||E_err| can be characterized as t→∞t→∞. Let us expand the terms using Taylor series: αt+1αt _t+1 _t =t+γt+1+γ=1−12(t+γ)+(1t2), = t+γt+1+γ=1- 12(t+γ)+O ( 1t^2 ), βt+1 _t+1 =γt+1+γ=γt+γ+(1t2). = γt+1+γ= γt+γ+O ( 1t^2 ). Using A=αt+1αt−βt+1A= _t+1 _t- _t+1, we get A≈1−γ+1/2t+γA≈ 1- γ+1/2t+γ. Squaring this and adding αt+12K2=1t+1+γ≈1t+γ _t+1^2K^2= 1t+1+γ≈ 1t+γ yields: A2+αt+12K2 A^2+ _t+1^2K^2 ≈1−2γ+1t+γ+1t+γ=1−2γt+γ. ≈ 1- 2γ+1t+γ+ 1t+γ=1- 2γt+γ. Taking the square root and using the Taylor expansion gives a contraction factor of 1−γt+γ1- γt+γ. Because γ≥2γ≥ 2, this is less than the bound 1−1.15t+γ+11- 1.15t+γ+1 used in our proof. For the error term Eerr=(1−αt+1αt)βt+βt+1−βtE_err=(1- _t+1 _t) _t+ _t+1- _t, we can expand each part separately. First, using the Taylor expansion for the ratio, we have 1−αt+1αt 1- _t+1 _t =12(t+γ)−38(t+γ)2+(1t3). = 12(t+γ)- 38(t+γ)^2+O ( 1t^3 ). Multiplying by βt=γt+γ _t= γt+γ gives: (1−αt+1αt)βt (1- _t+1 _t ) _t =γ2(t+γ)2−3γ8(t+γ)3+(1t4). = γ2(t+γ)^2- 3γ8(t+γ)^3+O ( 1t^4 ). Next, for the difference βt+1−βt _t+1- _t, we have: βt+1−βt=−γ(t+γ)(t+1+γ)=−γ(t+γ)2+γ(t+γ)3+(1t4). _t+1- _t= -γ(t+γ)(t+1+γ)=- γ(t+γ)^2+ γ(t+γ)^3+O ( 1t^4 ). Summing these two parts yields: Eerr=−γ2(t+γ)2+5γ8(t+γ)3+(1t4), E_err=- γ2(t+γ)^2+ 5γ8(t+γ)^3+O ( 1t^4 ), confirming that |Eerr|≈γ2t2=(1/t2)|E_err|≈ γ2t^2=O(1/t^2).