aiqbench analysis
This paper advances the theoretical understanding of stochastic extragradient methods by rigorously distinguishing between same-sample and independent-sample variants in solving monotone variational inequalities. The authors demonstrate critical convergence limitations for same-sample approaches under standard assumptions, establishing high-probability restricted-gap bounds where fundamental improvements are provably impossible. These findings clarify essential constraints on algorithm design for optimization tasks central to modern machine learning training dynamics.
On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities
arXiv:2608.06182v1 Announce Type: cross 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.
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.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2608.06182 [math.OC]
(or arXiv:2608.06182v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2608.06182 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 291 words
Related coverage
Exploding variance of means of exponentials: least-squares to the rescue – Machine Learning Research Blog
francisbach.com · Sep 27, 2026
Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
arXiv · Sep 23, 2026
A Statistical Formulation Gap for Nonlinear Multiscale Physics-Informed Learning
arXiv · Jul 20, 2026
Accelerated and Stable Convergence with Anchored Generalized Optimistic Method
arXiv · Aug 5, 2026