Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems

Anthony Man-Cho So; Jiajin Li; Taoli Zheng

Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems

T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A simple quadratic perturbation makes the last iterate of stochastic EG and OGDA converge for constrained convex-concave minimax problems.

desk verdict Clean single-loop last-iterate rates for S-EG/S-OGDA under the plain bounded-variance oracle; the O(T^{-1/4}) known-horizon result is real and improves the comparable prior art. read the letter →

arxiv 2607.11056 v1 pith:C7W73THU submitted 2026-07-13 math.OC

Taoli Zheng , Jiajin Li , Anthony Man-Cho So This is my paper · ORCID

classification math.OC MSC 90C4790C1565K15

keywords last-iterateconvergencestochasticextragradientoptimisticgradientdescent-ascentconvex-concaveminimaxquadraticperturbationrestrictedprimal-dualgapanytimeratesvariationalinequalities

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Vanilla stochastic extragradient and optimistic gradient methods can fail to converge on even simple bilinear games because noise keeps the last iterate from settling. This paper shows that adding a small quadratic regularizer that makes the problem strongly convex-strongly concave, then running the same single-loop updates on the regularized problem, restores last-iterate convergence under ordinary bounded-variance stochastic gradients. When the total number of steps T is known in advance, a fixed perturbation of order T to the minus one-fourth yields an O(T to the minus one-fourth) guarantee on the restricted primal-dual gap; on compact domains that gap is the ordinary duality gap. When T is unknown, slowly diminishing perturbations and stepsizes still give an O(T to the minus one-fifth) rate, and in the unconstrained case the same method recovers an O(T to the minus one-fourth) rate on the gradient norm. The practical payoff is that practitioners can keep the simplest single-loop algorithms and still trust the final output rather than an average.

What carries the argument

The quadratic perturbation F_τ = F + (τ/2)‖x‖² - (τ/2)‖y‖², which renders the associated operator strongly monotone; last-iterate distance to the perturbed saddle is first controlled by a contraction-plus-noise recursion, then converted into a restricted primal-dual gap bound via uniform mean-square boundedness of the iterates.

What would settle it

On a compact bilinear game with additive bounded-variance noise, run PS-EG with the stated horizon-dependent schedule and check whether the empirical last-iterate duality gap decays faster than T to the minus one-fifth and matches the claimed T to the minus one-fourth order; a clear slower decay or divergence falsifies the rate.

Watch

Extended reading notes

Core claim

Under the standard bounded-variance stochastic oracle, both perturbed stochastic extragradient (PS-EG) and perturbed stochastic optimistic GDA (PS-OGDA) produce last iterates whose restricted primal-dual gap converges at rate O(T^{-1/4}) when the horizon is known and the perturbation is held fixed at order T^{-1/4}, and at rate O(T^{-1/5}) under diminishing perturbations when the horizon is unknown; the unrestricted gradient norm inherits the same rates in the unconstrained setting.

Load-bearing premise

The iterates must stay uniformly bounded in mean square so that the restricted gap on a fixed compact set controls the quality of the last iterate; that boundedness is proved only for the stepsize and perturbation schedules already used to obtain contraction.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The useful fact is simple: under the standard unbiased bounded-variance oracle, both PS-EG and PS-OGDA get last-iterate O(T^{-1/4}) on the restricted primal-dual gap when T is known, and O(T^{-1/5}) anytime on general closed convex sets. On compact domains the restricted gap is the ordinary gap. That improves the previous best comparable single-loop rates (~T^{-1/7} anchoring, T^{-1/6} with Hessian Lipschitz) without mini-batches or variance reduction.

What is new is not the quadratic perturbation itself (classical) but the full two-stage analysis that turns distance-to-perturbed-saddle into last-iterate restricted-gap guarantees for both EG and OGDA, covering non-compact domains and anytime schedules. The refined one-step recursions keep the negative quadratic terms that give contraction; the Chung-type lemmas are applied correctly; the conversion lemmas are explicit. The concurrent-work discussion is transparent and fair. The sharper unconstrained anytime gradient-norm rate for PS-EG via reference tracking is a nice extra that avoids the moving-saddle bookkeeping.

The only structural soft spot is the reliance on uniform mean-square boundedness (Lemma 5.4) to keep the comparison sets and M_R finite. Under the paper’s own schedules the error series are summable with T-independent sums, so the constants stay O(1) and the bias term is genuinely O(T^{-1/4}). No circularity. Rates remain slower than the multi-sample O(T^{-1/3}) unconstrained results, which the authors state clearly. Free parameters are just the usual schedule exponents and offsets; nothing is fitted.

This is for people who care about last-iterate stochastic VI / minimax under the weakest standard oracle. The math is solid enough that a serious editor should send it to referees. I would cite the known-horizon theorem and the anytime unconstrained corollary.

Referee Report

0 major / 4 minor

Summary. The paper studies last-iterate convergence of single-loop stochastic first-order methods for smooth convex-concave minimax problems under a standard bounded-variance oracle. Vanilla S-EG and S-OGDA can fail to converge last-iterate even on bilinear problems; the authors stabilize them by adding a quadratic perturbation that makes the problem strongly convex-strongly concave, then run S-EG/S-OGDA on the perturbed operator (PS-EG and PS-OGDA). Analysis proceeds in two stages: non-asymptotic distance bounds to the (possibly time-varying) perturbed saddle, followed by conversion to the restricted primal-dual gap (or gradient norm when unconstrained). With known horizon they obtain O(T^{-1/4}) last-iterate rates (Theorem 4.1, Corollary 4.1); with diminishing schedules they obtain O(T^{-1/5}) anytime rates on general closed convex sets (Theorem 4.2) and a sharper O(T^{-1/4}) anytime gradient-norm rate for unconstrained PS-EG via a reference-tracking argument (Theorem 4.3).

Significance. Last-iterate guarantees for stochastic EG/OGDA under the ordinary bounded-variance oracle remain limited, especially with constraints. The paper supplies simple single-loop algorithms that improve the previous best comparable constrained rate (roughly ~O(T^{-1/7})) to O(T^{-1/4}) when T is known, and that also cover non-compact domains and an anytime regime. The two-stage architecture (refined one-step recursions + Chung-type lemmas + conversion lemmas) is fully written out, the uniform second-moment bound needed for the restricted gap is controlled under the stated schedules, and the unconstrained reference-tracking argument for PS-EG is a clean technical contribution. The results are therefore a genuine advance for the standard oracle model.

minor comments (4)

Table 1 caption and the surrounding text correctly note that G_R coincides with the ordinary gap only when B_x = X and B_y = Y; a short explicit sentence in the introduction or abstract would further reduce the risk that readers over-claim the constrained rate for unbounded domains.
In the anytime analysis (Theorem 5.2 / Lemma 5.3) the Lyapunov function for PS-OGDA accumulates several (tau_t - tau_{t-1}) terms; a one-line remark that these remain summable under the chosen exponents would make the bookkeeping easier to follow.
Figure 1 is only described in the text; if the camera-ready version includes the actual plots, ensure the caption states the precise bilinear instance and noise model so the non-convergence of vanilla methods is reproducible.
A few typographical slips remain (e.g., "Metho ds", "stochas tic", missing spaces after commas in the arXiv header). They do not affect readability but should be cleaned.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: rates follow from standard monotonicity/Lipschitz assumptions and explicit recursions under chosen schedules.

full rationale

The paper's central claims (Theorems 4.1–4.3, Corollaries 4.1) are obtained by a transparent two-stage argument: (i) one-step recursions for PS-EG/PS-OGDA on the τ-perturbed operator (Lemmas 5.2–5.3) that exploit τ-strong monotonicity and bounded variance, followed by Chung-type lemmas that convert the recursions into distance bounds to the perturbed saddle (Theorems 5.1–5.2); (ii) conversion of those distance bounds into restricted primal-dual gap or gradient-norm guarantees via smoothness and the uniform second-moment bound (Lemmas 5.4–5.6). The perturbation level τ (or τ_t) and stepsizes are free parameters chosen by the analyst to balance contraction against bias; they are not fitted to data, nor are they defined in terms of the target gap. Uniform mean-square boundedness (Lemma 5.4) is proved from the same summable error series that appear under the stated schedules, so the constants that enter the gap conversion remain O(1) and do not presuppose the claimed rate. Self-citations are either classical VI facts (Korpelevich, Popov, Facchinei–Pang, Chung) or concurrent independent works; none of them is load-bearing for the exponents. No quantity is defined via the quantity later claimed as a prediction, and no uniqueness theorem is imported to force the method. Consequently the derivation is self-contained against the stated assumptions and exhibits no circular reduction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 2 invented entities

The central claims rest only on four standard structural assumptions of stochastic convex-concave minimax optimization plus the algorithmic choice of a quadratic perturbation whose size is set by the horizon or by a diminishing schedule. No data-fitted constants or new physical entities are introduced.

free parameters (2)

perturbation schedule exponents (α,β or δ)
Chosen by the analyst to balance contraction versus bias; not fitted to data but free design parameters that determine the final rate exponents.
stepsize prefactors η₀, τ₀ and offset b
Must satisfy explicit inequalities involving L and au; free within those inequalities and affect only hidden constants.

assumptions (5)

domain assumption F is convex-concave (Assumption 2.1)
Standard structural hypothesis for the VI formulation; used throughout the monotonicity arguments.
domain assumption Partial gradients of F are L-Lipschitz (Assumption 2.2)
Needed for the one-step progress inequalities of EG/OGDA.
domain assumption Solution set of the VI is nonempty (Assumption 2.3)
Guarantees existence of a reference saddle used in all distance bounds.
domain assumption Stochastic oracle is unbiased with uniformly bounded variance σ^{2} (Assumption 2.4)
The weakest standard noise model; all error terms are controlled by σ^{2}.
standard math Projection onto closed convex sets is non-expansive
Used in every recursive inequality (Lemma B.1).

invented entities (2)

perturbed operator W(u) = V(u) + au u and the associated PS-EG / PS-OGDA algorithms independent evidence
purpose: Induce strong monotonicity so that last-iterate contraction becomes possible under noise
Algorithmic construction rather than a new mathematical object; independent evidence is the derived rates themselves.
restricted primal-dual gap G_R over compact comparison sets B_x imes B_y independent evidence
purpose: Provide a finite stationarity measure when the feasible sets are unbounded
Standard device in unconstrained minimax analysis; the paper only specializes the radii via mean-square boundedness.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems." pith.science (2026). https://pith.science/paper/C7W73THU

@misc{pith2026260711056,
  author       = {Pith},
  title        = {Pith review of: Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C7W73THU}},
  note         = {Machine review of arXiv:2607.11056}
}

abstract

In this paper, we study last-iterate convergence of stochastic first-order methods for constrained smooth convex--concave minimax optimization under the standard bounded-variance stochastic oracle. A fundamental challenge is that the last iterates of vanilla stochastic extragradient (S-EG) and stochastic optimistic gradient descent--ascent (S-OGDA) may fail to converge in the presence of stochastic gradient noise, even for simple bilinear problems. To overcome this difficulty, we introduce a simple perturbation framework that regularizes the original convex--concave problem into a strongly convex--strongly concave one. Applying S-EG and S-OGDA to the perturbed problem yields two simple single-loop methods, referred to as perturbed S-EG (PS-EG) and perturbed S-OGDA (PS-OGDA). We establish last-iterate convergence by first deriving convergence in terms of the squared distance to the saddle point of the perturbed problem and then translating this estimate into guarantees for the restricted primal--dual gap. Based on this framework, we establish two types of convergence guarantees. When the optimization horizon is known \emph{a priori}, both PS-EG and PS-OGDA achieve an $\mathcal{O}(T^{-1/4})$ last-iterate convergence rate for the restricted primal--dual gap, which coincides with the standard primal--dual gap on compact feasible domains. When the optimization horizon is unknown, we develop an anytime variant based on diminishing perturbations and diminishing stepsizes. For general closed convex feasible sets, both PS-EG and PS-OGDA achieve an $\mathcal{O}(T^{-1/5})$ last-iterate convergence rate for the restricted primal--dual gap. Furthermore, in the unconstrained setting, PS-EG admits a sharper $\mathcal{O}(T^{-1/4})$ anytime convergence rate in terms of the gradient norm.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 6 linked inside Pith

[1]

Alacaoglu and J.-H

A. Alacaoglu and J.-H. Kim. Solving stochastic variational i nequalities without the bounded vari- ance assumption. arXiv preprint arXiv:2602.05531,

arXiv
[2]

Alacaoglu, Y

A. Alacaoglu, Y . Malitsky , and S. J. Wright. Towards weaker va riance assumptions for stochastic optimization. arXiv preprint arXiv:2504.09951,

arXiv
[3]

29 X. Cai, C. Song, C. Guzmán, and J. Diakonikolas. Stochastic h alpern iteration with variance reduc- tion for stochastic monotone inclusions. Advances in Neural Information Processing Systems , 35: 24766–24779, 2022a. Y . Cai and W. Zheng. Last-iterate convergence of anchored gr adient descent. arXiv preprint arXiv:2604.12235,

arXiv
[4]

Y . Cai, A. Oikonomou, and W. Zheng. Accelerated algorithms f or constrained nonconvex- nonconcave min-max optimization and comonotone inclusion . arXiv preprint arXiv:2206.05248, 2022b. Y . Cai, A. Oikonomou, and W. Zheng. Tight last-iterate conve rgence of the extragradient and the optimistic gradient descent-ascent algorithm for constra ined monotone v...

arXiv
[5]

Mertikopoulos, B

P . Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V . Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (g radient) mile. In Proceedings of the 6th International Conference on Learning Representations ( ICLR 2018),

2018
[6]

E. K. Ryu, K. Yuan, and W. Yin. Ode analysis of stochastic gradie nt methods with optimism and anchoring for minimax problems. arXiv preprint arXiv:1905.10899,

arXiv 1905
[7]

Sohrabi, J

M. Sohrabi, J. You, S. Lacoste-Julien, E. Gorbunov , and G. Gid el. Accelerated and stable conver- gence with anchored optimistic method. arXiv preprint arXiv:2606.21528,

arXiv
[8]

Surina, A

A. Surina, A. Suggala, G. Tsoukalas, A. Kovsharov , S. Shirobokov , F. J. Ruiz, P . Kohli, and S. Chaud- huri. An improved last-iterate convergence rate for anchor ed gradient descent ascent. arXiv preprint arXiv:2604.03782,

arXiv

Show all 13 references

[9]

Vankov , A

31 D. Vankov , A. Nedich, and L. Sankar. Last iterate convergence of popov method for non-monotone stochastic variational inequalities. In OPT 2023: Optimization for Machine Learning ,

2023
[10]

Local convergence

Appendix A Related Work In this appendix, we ﬁrst review related work according to two aspects: local convergence and last-iterate convergence rates. Local convergence. Although stochastic extragradient (S-EG) and stochastic o ptimistic gradient descent-ascent (S-OGDA) may div...

2019
[11]

Ito et al

and Ito et al. Ito et al. [2026]. The generalized optimistic methods with anchoring (GOMA) pr oposed in Sohrabi et al

2026
[12]

B Useful Lemmas We ﬁrst collect several auxiliary results that will be used th roughout the analysis

while attaining the same polynomial convergence rate. B Useful Lemmas We ﬁrst collect several auxiliary results that will be used th roughout the analysis. In particular, the projection inequality forms the basis for deriving the key r ecursive inequalities. We then present se...

2019
[13]

The second cla im follows from b ≥ 3 and elementary comparisons between T + b− 2 and T + b

Combining the two bounds proves the ﬁrst claim. The second cla im follows from b ≥ 3 and elementary comparisons between T + b− 2 and T + b. ⊔ ⊓ Lemma B.4 ([Chung, 1954, Lemma 1]) . Let{at}t≥ 0 be a sequence of nonnegative real numbers. 36 Suppose that, for some c > 0, r > 0, C...

1954

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.

[1] [1]

Alacaoglu and J.-H

A. Alacaoglu and J.-H. Kim. Solving stochastic variational i nequalities without the bounded vari- ance assumption. arXiv preprint arXiv:2602.05531,

arXiv

[2] [2]

Alacaoglu, Y

A. Alacaoglu, Y . Malitsky , and S. J. Wright. Towards weaker va riance assumptions for stochastic optimization. arXiv preprint arXiv:2504.09951,

arXiv

[3] [3]

29 X. Cai, C. Song, C. Guzmán, and J. Diakonikolas. Stochastic h alpern iteration with variance reduc- tion for stochastic monotone inclusions. Advances in Neural Information Processing Systems , 35: 24766–24779, 2022a. Y . Cai and W. Zheng. Last-iterate convergence of anchored gr adient descent. arXiv preprint arXiv:2604.12235,

arXiv

[4] [4]

Y . Cai, A. Oikonomou, and W. Zheng. Accelerated algorithms f or constrained nonconvex- nonconcave min-max optimization and comonotone inclusion . arXiv preprint arXiv:2206.05248, 2022b. Y . Cai, A. Oikonomou, and W. Zheng. Tight last-iterate conve rgence of the extragradient and the optimistic gradient descent-ascent algorithm for constra ined monotone v...

arXiv

[5] [5]

Mertikopoulos, B

P . Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V . Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (g radient) mile. In Proceedings of the 6th International Conference on Learning Representations ( ICLR 2018),

2018

[6] [6]

E. K. Ryu, K. Yuan, and W. Yin. Ode analysis of stochastic gradie nt methods with optimism and anchoring for minimax problems. arXiv preprint arXiv:1905.10899,

arXiv 1905

[7] [7]

Sohrabi, J

M. Sohrabi, J. You, S. Lacoste-Julien, E. Gorbunov , and G. Gid el. Accelerated and stable conver- gence with anchored optimistic method. arXiv preprint arXiv:2606.21528,

arXiv

[8] [8]

Surina, A

A. Surina, A. Suggala, G. Tsoukalas, A. Kovsharov , S. Shirobokov , F. J. Ruiz, P . Kohli, and S. Chaud- huri. An improved last-iterate convergence rate for anchor ed gradient descent ascent. arXiv preprint arXiv:2604.03782,

arXiv