Pith. sign in

REVIEW 4 minor 80 references

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

T0 review · 0 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read For stochastic extragradient on monotone variational inequalities, reusing the same random sample in the extrapolation and update steps is not an innocuous implementation detail: it can turn an almost surely convergent method into one…

desk verdict A solid theory paper that cleanly separates same-sample from independent-sample stochastic extragradient, with checkable counterexamples; it deserves serious refereeing. read the letter →

arxiv 2608.06182 v1 pith:B3UJFLBD submitted 2026-08-06 math.OC cs.LG

TaeHo Yoon , Nicolas Loizou This is my paper · ORCID
classification math.OCcs.LG MSC 65K1590C3362L2090C1549J4047H05
keywords stochasticextragradientmonotonevariationalinequalitysame-samplesamplingindependent-samplerestrictedgapfunctionalmostsureconvergenceDSEGstep-sizesuniformLipschitzness
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

This paper studies two stochastic variants of the extragradient method for monotone variational inequalities: independent-sample SEG (I-SEG), which draws a fresh random operator evaluation for each of the two steps, and same-sample SEG (S-SEG), which reuses a single evaluation. The aim is to show that this implementation choice is not cosmetic. The paper proves that S-SEG requires stronger analytic hypotheses than I-SEG, that both methods admit a high-probability restricted-gap convergence theory on possibly unbounded domains, and that the asymmetric DSEG step-size rule guaranteeing almost sure convergence for I-SEG can still drive S-SEG to diverge almost surely on a uniformly Lipschitz stochastic monotone VIP with a unique solution. Read sympathetically, the paper's message is that the independence of the two samples is part of the mechanism of convergence, not a proof convenience.

What carries the argument

The recurring obstruction is the same-sample bias term $\langle F(\hat x_k;\xi_{i_k})-F(\hat x_k),x_k\rangle$, which the SEG identity of Lemma 3.1 forces into the recursion and which vanishes under expectation for I-SEG because the second sample is independent of $\hat x_k$, but not for S-SEG. The divergence counterexamples use linear rotation operators $F(x;\xi_1)=(\rho I+(1+\nu)J)x$ and $F(x;\xi_2)=(-\rho I+(1-\nu)J)x$, where $J=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$ is the $90^\circ$ rotation matrix; identifying $\mathbb R^2$ with $\mathbb C$ turns both recursions into scalar complex multiplications by $b_s(\gamma,\hat\gamma)$ for S-SEG and $c_{u,s}(\gamma,\hat\gamma)$ for I-SEG, and their log-modulus expansions at small step sizes expose positive versus negative quadratic drift. The DSEG step-size rule supplies the asymmetric decay rates whose insufficiency for S-SEG is established in Theorem 4.2.

What would settle it

Take the two-sample rotation operator $F(x;\xi_1)=(2I+J)x$, $F(x;\xi_2)=(-2I+J)x$ on $\mathbb R^2$, with $J$ the $90^\circ$ rotation, run S-SEG with DSEG step sizes $\hat\gamma_k=1/\log(k+k_0)$, $\gamma_k=\eta/(k+k_0)$ for fixed $0<\eta<1/10$ from any nonzero start, and track $\|x_k\|$ and the weighted average norm; Theorem 4.2 predicts both diverge almost surely, so observing a bounded trajectory over an extended horizon would contradict the paper's central separation claim.

Watch

Extended reading notes

Core claim

The central finding is a separation between I-SEG and S-SEG that is visible in assumptions, step-size rules, and dynamics. On a compact domain, S-SEG can fail to converge to the solution even when the mean operator is monotone and Lipschitz, the oracle is unbiased, and the variance is bounded, unless the individual sample operators are uniformly Lipschitz; I-SEG converges under the weaker conditions. On possibly unbounded domains, with symmetric square-summable step sizes $\hat\gamma_k=\gamma_k$ and $\gamma_k=\Theta((k+1)^{-\alpha})$ for $1/2<\alpha<1$, both variants attain restricted-gap error $O(N^{-(1-\alpha)})$ with high probability, where the restricted gap is $\mathrm{Err}_{x^\ast,D}(\hat x_N)=\max_{u\in X\cap B(x^\ast,D)}\langle F(u),\hat x_N-u\rangle$; the paper shows this high-probability form cannot generally be replaced by an unconditional expected-gap bound. Under the DSEG rule $\gamma_k=\eta/(k+k_0)$, $\hat\gamma_k=1/\log(k+k_0)$, I-SEG's last iterate converges almost surely while S-SEG, on an explicit uniformly Lipschitz monotone stochastic VIP with a unique solution, has both the last iterate and the weighted average diverging almost surely. Under quasi-strict monotonicity, S-SEG does converge almost surely, so the divergence is specific to the general monotone regime.

Load-bearing premise

All positive results rely on the noise model in which, for a fixed solution $x^\ast$, the conditional variance of the sampled operator grows at most like $\|x-x^\ast\|^2$ (for example $E[\|F(x)-F(x;\xi)\|^2 \mid \mathcal F]\le A\|x-x^\ast\|^2+\sigma^2$), and for S-SEG every sampled operator must also be uniformly Lipschitz; if the noise is heavier-tailed, the high-probability convergence event is not established.

Editorial extensions

If this is right

  • Switching an implementation from independent-sample to same-sample draws is a change of algorithm, not a variance-reduction shortcut; the same step sizes, domain, and problem class that guarantee convergence for I-SEG can fail for S-SEG.
  • With symmetric step sizes $\hat\gamma_k=\gamma_k=\Theta((k+1)^{-\alpha})$, $1/2<\alpha<1$, both SEG variants provide a quantitative restricted-gap rate $O(N^{-(1-\alpha)})$ with user-specified success probability on unbounded domains, removing the need for compactness or uniformly bounded variance in that regime.
  • The DSEG prescription of larger extrapolation steps and smaller update steps, with $\sum_k\gamma_k\hat\gamma_k=\infty$, $\sum_k\gamma_k^2<\infty$, and $\sum_k\gamma_k\hat\gamma_k^2<\infty$, rescues I-SEG but not S-SEG, so step-size rules validated for one sampling choice must be revalidated for the other.
  • Square summability of symmetric step sizes is load-bearing: with $\gamma_k=1/\sqrt{k+1}$, both I-SEG and S-SEG can have unbounded last-iterate and average-iterate norms almost surely.
  • Under quasi-strict monotonicity, S-SEG achieves almost sure last-iterate convergence, matching I-SEG; the divergence examples therefore live at the boundary between quasi-strict and merely monotone operators.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the paper's separation is right, then implementations that reuse a minibatch across the extrapolation and update steps should be expected to inherit S-SEG's instability; a direct test would run I-SEG versus a minibatch-reuse variant on the two rotation counterexamples and compare divergence times.
  • Theorem 3.12's limiting radius $R_\infty$ has unbounded support even under square-summable symmetric step sizes, so computing an average gap on a fixed ball from a single run can be misleading; one could estimate the full distribution of $R_\infty$ across runs to see the rare large-radius paths.
  • The same rotation-operator construction likely transfers to optimistic gradient and other single-call extragradient variants, which the paper names as future work; if the bias term reappears, the independence requirement would be a general phenomenon rather than an SEG-specific quirk.
  • The boundary the paper draws is inside the quadratic-growth noise model; whether a different step-size rule can rescue S-SEG for general monotone operators remains open, and one could test this by searching over step-size families on the Theorem 4.2 counterexample.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper studies stochastic extragradient (SEG) for monotone variational inequalities, contrasting independent-sample SEG (I-SEG) and same-sample SEG (S-SEG). It argues that the choice of sampling rule is not an innocuous implementation detail. The main positive results are high-probability conditional restricted-gap bounds for both variants on possibly unbounded domains under a generalized variance assumption (Theorems 3.3 and 3.4), complemented by counterexamples showing that square summability and the high-probability form cannot be removed (Theorems 3.9, 3.10, and 3.12). It also proves almost-sure last-iterate convergence of S-SEG under quasi-strict monotonicity (Theorem 4.1). The central separation is Theorem 4.2: for a uniformly Lipschitz monotone linear stochastic VIP in R^2, S-SEG with the DSEG step-size rule of Hsieh et al. diverges almost surely, both in the last iterate and in the weighted average, while I-SEG is known to converge under the same rule.

Significance. If the results are correct, the paper makes a substantive contribution to the stochastic VIP literature. It identifies a genuine modeling distinction between S-SEG and I-SEG, supports it with a fully explicit counterexample family, and proves quantitative high-probability bounds under weaker assumptions than uniform variance. The negative results are particularly strong: they are not appeals to exotic pathologies but simple linear stochastic operators with two samples, and the divergence proof in Theorem 4.2 is backed by detailed complex-multiplier expansions and martingale convergence arguments. The paper also correctly isolates the role of uniform samplewise Lipschitzness for S-SEG, showing that it is not a proof artifact. The main limitation of the positive gap theory is its reliance on the quadratic-growth noise model (Assumption 2.6), but the central negative separation does not depend on that model, so the paper's main claim stands.

minor comments (4)
  1. [Theorem 3.3 (Section 3.2.1)] The sentence 'On this event Eδ, there exists a constant C>0 such that ...' introduces an unused constant; the subsequent display does not involve C. Please delete the clause or define the constant explicitly.
  2. [Proof of Theorem 4.2 (Section 4.2)] In the estimate following the analysis of T_N, the notation 'L_N^q' appears where the context requires '(log N)^q', and the symbol L_N is never defined. Please introduce L_N = log(N+k0) or write the bound directly as O((log N)^q).
  3. [Proposition 3.2, proof] The proof says 'This is an increasing function on R, so F is monotone', but F is defined only on X=[0,a]; the monotonicity statement should be restricted to the domain X.
  4. [Theorems 3.9 and 3.10] The same symbol \hat{x}_k denotes both the extrapolated iterate and the ergodic average in the statements and surrounding text; although the average is defined inline, please use a distinct notation such as \bar{x}_k for the averages to avoid ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central separation result is a constructed counterexample with self-contained proofs, and no prediction reduces by construction to its inputs.

full rationale

I checked the derivation chain of each claimed novelty, especially the strongest claim in Theorem 4.2. That theorem constructs an explicit linear stochastic VIP (Lemma 3.11 with ν=0 and ρ≥2 chosen so that q=η(ρ²−1)>1), verifies the DSEG summability conditions directly, and proves divergence by explicit complex-logarithm asymptotics with uniform remainder bounds. No constant is fitted to force the conclusion; q>1 is chosen, and all martingale and summation-by-parts steps are justified in the text. The same holds for the other negative results, Theorems 3.9, 3.10, and 3.12, which are counterexamples rather than fitted predictions. The positive high-probability gap theorems (Theorems 3.3 and 3.4) follow from Lemmas 3.6–3.8, which are standard supermartingale and stopping-time estimates; Assumption 2.6 is a stated modeling condition, not a derived output, and the paper explicitly frames its boundary as internal to that noise model. Proposition 2.11 is proved self-contained in Section 3.1.1. The self-citations that appear (e.g., to the authors' earlier S-SEG work and to single-call SEG work) are used as background context, not as load-bearing mathematical inputs; Theorem 4.1 uses the Robbins–Siegmund lemma and a countable-density argument, and Proposition 3.13 proves its gap bound in the present text even though it is motivated by the externally cited DSEG analysis of Hsieh et al. I find no step in which a quantity is defined in terms of the result it is supposed to establish, no fitted parameter renamed as a prediction, and no uniqueness theorem imported from the authors' own prior work to forbid alternatives. The derivation is self-contained against explicit assumptions and external standard tools, so the appropriate finding is no significant circularity.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new entities. The only free choices are constants inside explicit counterexamples, not fitted to data. The central theorems are self-contained given the stated assumptions and standard tools.

free parameters (3)
  • rho, nu in Lemma 3.11 counterexample family = rho=2, nu=0 for Theorems 3.9 and 3.12; rho=0, nu=2 for Theorem 3.10
    Chosen to make the second-order drift term in the logarithm of the iteration multiplier positive for S-SEG or I-SEG, so that the norm grows like N^{3/2} or like log N.
  • eta and rho in Theorem 4.2 = 0<eta<1/10, rho>=2 with eta(rho^2-1)>1
    Ensures the coefficient of gamma_k * gammaHat_k in the complex-log expansion exceeds the negative drift, so ||x_k|| ~ (log N)^{eta(rho^2-1)} diverges under DSEG step-sizes.
  • a in Proposition 3.2 = a>=2
    Domain [0,a] is large enough to contain the trapping set Y=[1,a] where S-SEG iterates remain separated from the unique solution.
assumptions (5)
  • domain assumption Assumptions 2.1, 2.2 and 2.3: mean monotonicity, mean Lipschitzness, and uniform samplewise Lipschitzness
    These define the problem class. Proposition 3.2 shows Assumption 2.3 cannot be replaced by Assumptions 2.2 and 2.5 for S-SEG; Theorems 3.4 and 4.1 invoke it directly.
  • domain assumption Assumption 2.4 unbiasedness and Assumption 2.6 generalized variance bound
    Used in Lemma 3.7 and Theorem 3.3; the entire high-probability theory is stated relative to this noise model. If the stochastic operator has heavier tails, the estimates fail.
  • domain assumption Assumption 2.8 quasi-strict monotonicity for Theorem 4.1
    Needed to turn summability of weighted inner products into existence of a limit point in the solution set.
  • standard math Standard stochastic approximation tools: Robbins-Siegmund supermartingale lemma, Kolmogorov two-series theorem, Kronecker's lemma, Ville's inequality
    Used in Lemma 3.6 and in the divergence proofs to convert summability of variances into almost sure convergence of random series.
  • standard math Nonexpansiveness of Euclidean projection and equivalence of Minty and Stampacchia forms for continuous monotone operators
    Used throughout the iterate estimates, e.g., Lemma 3.1 and Theorem 4.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities." pith.science (2026). https://pith.science/paper/B3UJFLBD

@misc{pith2026260806182,
  author       = {Pith},
  title        = {Pith review of: On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B3UJFLBD}},
  note         = {Machine review of arXiv:2608.06182}
}
read the original abstract

We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.

Figures

Figures reproduced from arXiv: 2608.06182 by the authors.

Figure 1
Figure 1. Trajectories of S-SEG and I-SEG on two different two-dimensional stochastic monotone VIPs defined in [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

80 extracted references · 64 canonical work pages

  1. [1]

    Lai, and Andre Wibisono

    Jacob Abernethy, Kevin A. Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization.international Conference on Algorithmic Learning Theory, 2021

    work page 2021

  2. [2]

    Solving stochastic variational inequalities without the bounded variance assumption.arXiv:2602.05531, 2026

    Ahmet Alacaoglu and Jun-Hyun Kim. Solving stochastic variational inequalities without the bounded variance assumption.arXiv:2602.05531, 2026

    work page arXiv 2026

  3. [3]

    Beyond the golden ratio for variational inequality algorithms

    Ahmet Alacaoglu, Axel B¨ ohm, and Yura Malitsky. Beyond the golden ratio for variational inequality algorithms. Journal of Machine Learning Research, 24(172):1–33, 2023

    work page 2023

  4. [4]

    Ahmet Alacaoglu, Volkan Cevher, and Stephen J. Wright. On the complexity of a simple primal-dual coordinate method.Mathematical Programming, 2025

    work page 2025

  5. [5]

    Towards weaker variance assumptions for stochastic opti- mization.arXiv:2504.09951, 2025

    Ahmet Alacaoglu, Yura Malitsky, and Stephen J Wright. Towards weaker variance assumptions for stochastic opti- mization.arXiv:2504.09951, 2025

    arXiv 2025

  6. [6]

    Sifting through the noise: Universal first-order methods for stochastic variational inequalities.Neural Information Processing Systems, 2021

    Kimon Antonakopoulos, Thomas Pethick, Ali Kavis, Panayotis Mertikopoulos, and Volkan Cevher. Sifting through the noise: Universal first-order methods for stochastic variational inequalities.Neural Information Processing Systems, 2021

    work page 2021

  7. [7]

    A tight and unified analysis of gradient- based methods for a whole spectrum of differentiable games.International Conference on Artificial Intelligence and Statistics, 2020

    Wa ¨ ıss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradient- based methods for a whole spectrum of differentiable games.International Conference on Artificial Intelligence and Statistics, 2020

    work page 2020

  8. [8]

    A universal algorithm for variational inequalities adaptive to smoothness and noise

    Francis Bach and Kfir Y Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. Conference on Learning Theory, 2019

    work page 2019

Show all 80 references
  1. [9]

    Decentralized local stochastic extra-gradient for variational inequalities.Neural Information Processing Systems, 2022

    Aleksandr Beznosikov, Pavel Dvurechenskii, Anastasiia Koloskova, Valentin Samokhin, Sebastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities.Neural Information Processing Systems, 2022

    2022

  2. [10]

    Stochastic gradient descent-ascent: Unified theory and new efficient methods.International Conference on Artificial Intelligence and Statistics, 2023

    Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods.International Conference on Artificial Intelligence and Statistics, 2023

    2023

  3. [11]

    Julius R. Blum. Approximation Methods which Converge with Probability one.The Annals of Mathematical Statistics, 25(2):382–386, 1954. 34

    1954

  4. [12]

    Solving nonconvex-nonconcave min-max problems exhibiting weak minty solutions.Transactions on Machine Learning Research, 2023

    Axel B¨ ohm. Solving nonconvex-nonconcave min-max problems exhibiting weak minty solutions.Transactions on Machine Learning Research, 2023

    2023

  5. [13]

    Bot ¸ and Enis Chenchene

    Radu I. Bot ¸ and Enis Chenchene. Extragradient method with flexible anchoring: Strong convergence and fast residual decay.SIAM Journal on Optimization, 36(3):1420–1445, 2026

    2026

  6. [14]

    Fast Optimistic Gradient Descent Ascent (OGDA) Method in Continuous and Discrete Time.Foundations of Computational Mathematics, 25(1):163–222, 2025

    Radu Ioan Bot ¸, Ern¨ o Robert Csetnek, and Dang-Khoa Nguyen. Fast Optimistic Gradient Descent Ascent (OGDA) Method in Continuous and Discrete Time.Foundations of Computational Mathematics, 25(1):163–222, 2025

    2025

  7. [15]

    Stochastic halpern iteration with variance reduction for stochastic monotone inclusions.Neural Information Processing Systems, 2022

    Xufeng Cai, Chaobing Song, Crist´ obal A Guzm´ an, and Jelena Diakonikolas. Stochastic halpern iteration with variance reduction for stochastic monotone inclusions.Neural Information Processing Systems, 2022

    2022

  8. [16]

    Accelerated single-call methods for constrained min-max optimization.International Conference on Learning Representations, 2023

    Yang Cai and Weiqiang Zheng. Accelerated single-call methods for constrained min-max optimization.International Conference on Learning Representations, 2023

    2023

  9. [17]

    Stochastic extragradient with flip-flop shuffling &amp; anchoring: Provable improvements.Neural Information Processing Systems, 2024

    Jiseok Chae, Chulhee Yun, and Donghwan Kim. Stochastic extragradient with flip-flop shuffling &amp; anchoring: Provable improvements.Neural Information Processing Systems, 2024

    2024

  10. [18]

    Reducing noise in GAN training with variance reduced extragradient.Neural Information Processing Systems, 2019

    Tatjana Chavdarova, Gauthier Gidel, Fran¸ cois Fleuret, and Simon Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient.Neural Information Processing Systems, 2019

    2019

  11. [19]

    Extragradient method for (L 0, L1)-Lipschitz root-finding problems.Neural Information Processing Systems, 2025

    Sayantan Choudhury and Nicolas Loizou. Extragradient method for (L 0, L1)-Lipschitz root-finding problems.Neural Information Processing Systems, 2025

    2025

  12. [20]

    Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragradient methods for struc- tured non-monotone variational inequalities: Improved analysis under weaker conditions.Neural Information Pro- cessing Systems, 2023

    2023

  13. [21]

    Shanbhag

    Shisheng Cui and Uday V. Shanbhag. On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems. In2016 IEEE 55th Conference on Decision and Control (CDC), pages 4510–4515, 2016

    2016

  14. [22]

    Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.Conference on Learning Theory, 2020

    Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.Conference on Learning Theory, 2020

    2020

  15. [23]

    Springer-Verlag, 2003

    Francisco Facchinei and Jong-Shi Pang.Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer-Verlag, 2003

    2003

  16. [24]

    A variational inequality perspective on generative adversarial networks.International conference on Learning Representations, 2019

    Gauthier Gidel, Hugo Berard, Ga¨ etan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks.International conference on Learning Representations, 2019

    2019

  17. [25]

    Negative momentum for improved game dynamics.International Conference on Artificial Intelligence and Statistics, 2019

    Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, R´ emi Le Priol, Gabriel Huang, Simon Lacoste- Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics.International Conference on Artificial Intelligence and Statistics, 2019

    2019

  18. [26]

    On stochastic approximation.Theory of Probability & Its Applications, 10(2):275–278, 1965

    EG Gladyshev. On stochastic approximation.Theory of Probability & Its Applications, 10(2):275–278, 1965

    1965

  19. [27]

    Tight last-iterate convergence rates for no-regret learning in multi-player games.Neural Information Processing Systems, 2020

    Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games.Neural Information Processing Systems, 2020

    2020

  20. [28]

    Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems.Conference on Learning Theory, 2020

    Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems.Conference on Learning Theory, 2020

    2020

  21. [29]

    Stochastic extragradient: General analysis and improved rates.International Conference on Artificial Intelligence and Statistics, 2022

    Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient: General analysis and improved rates.International Conference on Artificial Intelligence and Statistics, 2022

    2022

  22. [30]

    Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method:O(1/K) last-iterate convergence for monotone variational inequalities and connections with cocoercivity.International Conference on Artificial Intelli- gence and Statistics, 2022

    2022

  23. [31]

    Last-iterate convergence of optimistic gradient method for monotone variational inequalities.Neural Information Processing Systems, 2022

    Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities.Neural Information Processing Systems, 2022. 35

    2022

  24. [32]

    Fixed points of nonexpanding maps.Bulletin of the American Mathematical Society, 73(6): 957–961, 1967

    Benjamin Halpern. Fixed points of nonexpanding maps.Bulletin of the American Mathematical Society, 73(6): 957–961, 1967

    1967

  25. [33]

    On the convergence of single-call stochastic extra-gradient methods.Neural Information Processing Systems, 2019

    Yu-Guan Hsieh, Franck Iutzeler, J´ erˆ ome Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods.Neural Information Processing Systems, 2019

    2019

  26. [34]

    Explore aggressively, update conser- vatively: Stochastic extragradient methods with variable stepsize scaling.Neural Information Processing Systems, 2020

    Yu-Guan Hsieh, Franck Iutzeler, J´ erˆ ome Malick, and Panayotis Mertikopoulos. Explore aggressively, update conser- vatively: Stochastic extragradient methods with variable stepsize scaling.Neural Information Processing Systems, 2020

    2020

  27. [35]

    Solving variational inequalities with stochastic mirror-prox algorithm.Stochastic Systems, 1(1):17–58, 2011

    Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm.Stochastic Systems, 1(1):17–58, 2011

    2011

  28. [36]

    Shanbhag

    Aswin Kannan and Uday V. Shanbhag. Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants.Computational Optimization and Applications, 74(3):779–820, 2019

    2019

  29. [37]

    G. M. Korpelevich. The extragradient method for finding saddle points and other problems.Ekonomika i Matem- aticheskie Metody, 12(4):747–756, 1976

    1976

  30. [38]

    A class of gap functions for variational inequalities.Mathematical Pro- gramming, 64(1):53–79, 1994

    Torbj¨ orn Larsson and Michael Patriksson. A class of gap functions for variational inequalities.Mathematical Pro- gramming, 64(1):53–79, 1994

    1994

  31. [39]

    Fundamental benefit of alternating updates in minimax optimization

    Jaewook Lee, Hanseul Cho, and Chulhee Yun. Fundamental benefit of alternating updates in minimax optimization. International Conference on Machine Learning, 2024

    2024

  32. [40]

    Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems.Neural Information Processing Systems, 2021

    Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems.Neural Information Processing Systems, 2021

    2021

  33. [41]

    Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks.International Conference on Artificial Intelligence and Statistics, 2019

    Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks.International Conference on Artificial Intelligence and Statistics, 2019

    2019

  34. [42]

    On the convergence rate of the Halpern-iteration.Optimization Letters, 15(2):405–418, 2021

    Felix Lieder. On the convergence rate of the Halpern-iteration.Optimization Letters, 15(2):405–418, 2021

    2021

  35. [43]

    Stochastic Hamiltonian gradient methods for smooth games.International Conference on Machine Learning, 2020

    Nicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martineau, Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas. Stochastic Hamiltonian gradient methods for smooth games.International Conference on Machine Learning, 2020

    2020

  36. [44]

    Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity

    Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Neural Information Processing Systems, 2021

    2021

  37. [45]

    Golden ratio algorithms for variational inequalities.Mathematical Programming, 184(1):383–410, 2020

    Yura Malitsky. Golden ratio algorithms for variational inequalities.Mathematical Programming, 184(1):383–410, 2020

    2020

  38. [46]

    Foo, Vijay Chandrasekhar, and Georgios Piliouras

    Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, C.-S. Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile.International Conference on Learning Representations, 2019

    2019

  39. [47]

    The numerics of GANs.Neural Information Processing Systems, 2017

    Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of GANs.Neural Information Processing Systems, 2017

    2017

  40. [48]

    On the generalization of a direct method of the calculus of variations.Bulletin of the American Mathematical Society, 73(6):315–321, 1967

    George J Minty. On the generalization of a direct method of the calculus of variations.Bulletin of the American Mathematical Society, 73(6):315–321, 1967

    1967

  41. [49]

    Revisiting stochastic extragradient.International Conference on Artificial Intelligence and Statistics, 2020

    Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richt´ arik, and Yura Malitsky. Revisiting stochastic extragradient.International Conference on Artificial Intelligence and Statistics, 2020

    2020

  42. [50]

    Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach.International Conference on Artificial Intelligence and Statistics, 2020. 36

    2020

  43. [51]

    Ozdaglar, and Sarath Pattathil

    Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate ofO(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems.SIAM Journal on Optimization, 30(4): 3230–3251, 2020

    2020

  44. [52]

    Renato D. C. Monteiro and B. F. Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean.SIAM Journal on Optimization, 20(6):2755–2787, 2010

    2010

  45. [53]

    Nedi´ c and A

    A. Nedi´ c and A. Ozdaglar. Subgradient Methods for Saddle-Point Problems.Journal of Optimization Theory and Applications, 142(1):205–228, 2009

    2009

  46. [54]

    Nemirovski, A

    A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming.SIAM Journal on Optimization, 19(4):1574–1609, 2009

    2009

  47. [55]

    Arkadi Nemirovski. Prox-method with rate of convergenceO(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.SIAM Journal on Optimization, 15(1):229– 251, 2004

    2004

  48. [56]

    S Nemirovsky

    A. S Nemirovsky. Information-based complexity of linear operator equations.Journal of Complexity, 8(2):153–175, 1992

    1992

  49. [57]

    Dual extrapolation and its applications to solving variational inequalities and related problems

    Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319–344, 2007

    2007

  50. [58]

    Dealing with unbounded gradients in stochastic saddle-point optimization.Interna- tional Conference on Machine Learning, 2024

    Gergely Neu and Nneka Okolo. Dealing with unbounded gradients in stochastic saddle-point optimization.Interna- tional Conference on Machine Learning, 2024

    2024

  51. [59]

    L. D. Popov. A modification of the Arrow–Hurwicz method for search of saddle points.Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845–848, 1980

    1980

  52. [60]

    Optimization, learning, and games with predictable sequences.Neural Infor- mation Processing Systems, 2013

    Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences.Neural Infor- mation Processing Systems, 2013

    2013

  53. [61]

    A convergence theorem for non negative almost supermartingales and some applications

    Herbert Robbins and David Siegmund. A convergence theorem for non negative almost supermartingales and some applications. InOptimizing Methods in Statistics, pages 233–257. Elsevier, 1971

    1971

  54. [62]

    Tyrrell Rockafellar.Convex Analysis

    R. Tyrrell Rockafellar.Convex Analysis. Princeton University Press, 1970

    1970

  55. [63]

    A fast optimistic method for monotone variational inequalities.Proceedings of the 40th international conference on machine learning, 2023

    Michael Sedlmayer, Dang-Khoa Nguyen, and Radu Ioan Bot. A fast optimistic method for monotone variational inequalities.Proceedings of the 40th international conference on machine learning, 2023

    2023

  56. [64]

    Negative stepsizes make gradient-descent-ascent converge.arXiv:2505.01423, 2025

    Henry Shugart and Jason M Altschuler. Negative stepsizes make gradient-descent-ascent converge.arXiv:2505.01423, 2025

    2025 arXiv

  57. [65]

    M. V. Solodov and B. F. Svaiter. A hybrid approximate extragradient – proximal point algorithm using the enlarge- ment of a maximal monotone operator.Set-Valued Analysis, 7(4):323–345, 1999

    1999

  58. [66]

    Formes bilineaires coercitives sur les ensembles convexes.Comptes Rendus Academie Des Sciences Paris, 258:4413–4416, 1964

    Guido Stampacchia. Formes bilineaires coercitives sur les ensembles convexes.Comptes Rendus Academie Des Sciences Paris, 258:4413–4416, 1964

    1964

  59. [67]

    Extragradient-type methods withO(1/k) last-iterate convergence rates for co-hypomonotone in- clusions.Journal of Global Optimization, 89(1):197–221, 2024

    Quoc Tran-Dinh. Extragradient-type methods withO(1/k) last-iterate convergence rates for co-hypomonotone in- clusions.Journal of Global Optimization, 89(1):197–221, 2024

    2024

  60. [68]

    From Halpern’s fixed-point iterations to Nesterov’s accelerated interpretations for root-finding problems.Computational Optimization and Applications, 87(1):181–218, 2024

    Quoc Tran-Dinh. From Halpern’s fixed-point iterations to Nesterov’s accelerated interpretations for root-finding problems.Computational Optimization and Applications, 87(1):181–218, 2024

    2024

  61. [69]

    VFOSA: Variance-reduced fast operator splitting algorithms for generalized equations.Journal of Machine Learning Research, 26(254):1–68, 2025

    Quoc Tran-Dinh. VFOSA: Variance-reduced fast operator splitting algorithms for generalized equations.Journal of Machine Learning Research, 26(254):1–68, 2025

    2025

  62. [70]

    Halpern-type accelerated and splitting algorithms for monotone inclusions

    Quoc Tran-Dinh and Yang Luo. Halpern-type accelerated and splitting algorithms for monotone inclusions. arXiv:2110.08150, 2021

    2021 arXiv

  63. [71]

    A modified forward-backward splitting method for maximal monotone mappings.SIAM Journal on Control and Optimization, 38(2):431–446, 2000

    Paul Tseng. A modified forward-backward splitting method for maximal monotone mappings.SIAM Journal on Control and Optimization, 38(2):431–446, 2000. 37

    2000

  64. [72]

    Bertsekas

    Mengdi Wang and Dimitri P. Bertsekas. Stochastic first-order methods with random constraint projection.SIAM Journal on Optimization, 26(1):681–717, 2016

    2016

  65. [73]

    Jacobs, and Tom Goldstein

    Abhay Kumar Yadav, Sohil Shah, Zheng Xu, David W. Jacobs, and Tom Goldstein. Stabilizing adversarial nets with prediction methods.International Conference on Learning Representations, 2018

    2018

  66. [74]

    A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms.arXiv:2605.02231, 2026

    TaeHo Yoon and Benjamin Grimmer. A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms.arXiv:2605.02231, 2026

    2026 arXiv

  67. [75]

    TaeHo Yoon and Ernest K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems withO(1/k 2) rate on squared gradient norm.International Conference on Machine Learning, 2021

    2021

  68. [76]

    TaeHo Yoon and Ernest K. Ryu. Accelerated minimax algorithms flock together.SIAM Journal on Optimization, 35(1):180–209, 2025

    2025

  69. [77]

    Suh, and Ernest K

    TaeHo Yoon, Jaeyeon Kim, Jaewook J. Suh, and Ernest K. Ryu. Optimal acceleration for minimax and fixed-point problems is not unique.International Conference on Machine Learning, 2024

    2024

  70. [78]

    Ryu, and Benjamin Grimmer

    TaeHo Yoon, Ernest K. Ryu, and Benjamin Grimmer. H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms.arXiv:2511.14915, 2025

    2025

  71. [79]

    Shanbhag

    Farzad Yousefian, Angelia Nedi´ c, and Uday V. Shanbhag. On Stochastic Mirror-prox Algorithms for Stochastic Cartesian Variational Inequalities: Randomized Block Coordinate and Optimal Averaging Schemes.Set-Valued and Variational Analysis, 26(4):789–819, 2018

    2018

  72. [80]

    Dissipative gradient descent ascent method: A control theory inspired algorithm for min-max optimization.IEEE Control Systems Letters, 8:2009–2014, 2024

    Tianqi Zheng, Nicolas Loizou, Pengcheng You, and Enrique Mallada. Dissipative gradient descent ascent method: A control theory inspired algorithm for min-max optimization.IEEE Control Systems Letters, 8:2009–2014, 2024. 38

    2009

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.