Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates stochastic extragradient (SEG) methods for monotone variational inequality problems, focusing on the less-explored same-sample SEG (S-SEG) variant. The authors demonstrate that S-SEG's convergence is sensitive to samplewise Lipschitz parameters, revealing that mean Lipschitzness and bounded variance are insufficient for ensuring convergence in compact sets. Additionally, they establish high-probability restricted-gap convergence for both SEG variants under relaxed assumptions and highlight the failure of certain step-size strategies that work for independent-sample SEG (I-SEG) but not for S-SEG, indicating a divergence risk in specific stochastic monotone VIPs.
S-SEG can diverge almost surely under conditions where I-SEG converges, revealing critical limitations in stochastic optimization strategies.
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.