🔢 mathematics

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

This paper investigates the convergence properties of stochastic extragradient methods for monotone variational inequalities by demonstrating that same-sample variants (S-SEG) are sensitive to samplewise Lipschitz parameters and can diverge almost surely even under conditions that guarantee convergence for independent-sample variants (I-SEG), while establishing high-probability restricted-gap convergence for both methods under relaxed assumptions.

Original authors: TaeHo Yoon, Nicolas Loizou

Published 2026-08-07

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: TaeHo Yoon, Nicolas Loizou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot to park your car in a massive, chaotic parking lot. You can't see the whole lot at once; you only get a glimpse of the ground right under your tires. This is the world of stochastic optimization, a branch of math that helps computers make smart decisions when they only have partial, noisy information. In this world, there's a classic problem called a Variational Inequality (VIP). Think of it as a game where you and an invisible opponent are trying to find a "truce point." If you move, the opponent moves too, and you want to find a spot where neither of you has an incentive to move again. This isn't just about parking; it's the math behind training AI, balancing power grids, and figuring out fair prices in complex markets.

To solve these problems, mathematicians use a strategy called the Extragradient method. Imagine you are walking toward the truce point. A normal walker would take a step, look at the ground, and take another step. But the Extragradient method is more cautious: it takes a "practice step" into the unknown, looks at what the ground looks like there, and then uses that new information to take its real step. This "look before you leap" approach is incredibly powerful. However, in the real world, the ground is slippery and unpredictable. Sometimes, you get a clear view of the ground (a "good" sample), and sometimes you get a blurry one (a "bad" sample). The big question researchers have been asking is: Does it matter if you use the same blurry view for both your practice step and your real step, or should you grab two different blurry views?

This paper, titled "On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities," dives deep into that exact question. The authors, TaeHo Yoon and Nicolas Loizou, act like detectives comparing two different driving styles. One style, called I-SEG, grabs two completely different, independent snapshots of the ground for the practice step and the real step. The other style, S-SEG, grabs just one snapshot and uses it for both. You might think using one snapshot is simpler and faster, but the authors prove that this simplicity comes with a hidden trap.

The paper reveals that while both methods work well in calm, predictable environments, they behave very differently when the terrain gets rough or the parking lot is infinitely large. The authors show that S-SEG is surprisingly fragile. They prove that if the "ground" (the mathematical operator) isn't perfectly smooth everywhere, S-SEG can get stuck in a loop or wander off into infinity, never finding the truce point. In fact, they constructed a specific mathematical example where S-SEG is guaranteed to fail, even though the problem looks solvable.

Perhaps the most surprising discovery is that a clever trick known as DSEG (using different step sizes for the practice and real steps), which successfully saves the independent method (I-SEG) from failing, does not save S-SEG. The authors demonstrate that even with this advanced steering mechanism, S-SEG can still spiral out of control and diverge almost surely. They also show that you cannot simply assume the "noise" in the data is small enough to ignore; for S-SEG, the noise needs to be perfectly uniform, a much stricter requirement than for I-SEG.

In short, the paper draws a sharp line in the sand. It proves that using the same sample for both steps isn't just a minor implementation detail; it fundamentally changes the rules of the game. While the independent method (I-SEG) is robust and can handle messy, unbounded problems with the right tricks, the same-sample method (S-SEG) is much more sensitive. It requires stricter conditions to work and can fail spectacularly where its independent cousin succeeds. The authors didn't just suggest this; they provided rigorous mathematical proofs and counterexamples to show exactly where and why these methods break, giving us a clear map of where these algorithms can be trusted and where they will crash.

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

Problem Statement

This work investigates the convergence properties of Stochastic Extragradient (SEG) methods for solving monotone Variational Inequality Problems (VIPs). A VIP seeks a point $x^* \in X$ such that $\langle F(x^*), x - x^* \rangle \geq 0$ for all $x \in X$ , where $F$ is a monotone operator. In the stochastic setting, the operator $F$ is defined as a finite sum $F(x) = \frac{1}{n} \sum_{i=1}^n F(x; \xi_i)$ , and algorithms access $F$ via stochastic samples.

The paper focuses on two distinct variants of SEG:

Independent-Sample SEG (I-SEG): Uses independent random indices $\xi_{i_k}$ and $\xi_{\hat{i}_k}$ for the extrapolation and update steps, respectively.
Same-Sample SEG (S-SEG): Uses a shared random index $\xi_{i_k} = \xi_{\hat{i}_k}$ for both steps.

While I-SEG has a well-developed convergence theory, S-SEG—a natural variant often preferred in practice for its computational efficiency—has received significantly less theoretical attention. The authors aim to bridge this gap by analyzing S-SEG under minimal assumptions and comparing its behavior fundamentally against I-SEG.

Methodology and Theoretical Framework

The analysis relies on standard assumptions in stochastic optimization, including:

Mean Monotonicity and Lipschitzness: The expected operator $F$ is monotone and Lipschitz.
Unbiasedness: Stochastic operators are unbiased estimators of the mean.
Variance Bounds: The paper utilizes both the standard Bounded Variance assumption (Assumption 2.5) and the more general Generalized Variance assumption (Assumption 2.6), which allows variance to grow linearly with the distance to the solution.
Uniform Lipschitzness: A stronger assumption (Assumption 2.3) requiring each sample operator $F(\cdot; \xi_i)$ to be Lipschitz, distinct from the mean operator being Lipschitz.

The authors employ a combination of high-probability analysis, martingale convergence theorems (specifically Kolmogorov's two-series theorem), and the construction of specific counterexamples to establish both positive convergence guarantees and negative impossibility results. A key technical challenge addressed is the bias term $\langle F(\hat{x}_k; \xi_{i_k}) - F(\hat{x}_k), x_k \rangle$ , which vanishes in expectation for I-SEG due to independence but remains non-zero for S-SEG.

Key Contributions and Results

1. Sensitivity to Samplewise Lipschitzness

The paper demonstrates that S-SEG is sensitive to the Lipschitz properties of individual sample operators, not just the mean operator.

Result: Even on compact domains with bounded variance and a unique solution, S-SEG may fail to converge if the sample operators are not uniformly Lipschitz (Assumption 2.3).
Evidence: A counterexample (Proposition 3.2) is constructed where the mean operator is monotone and Lipschitz, but sample operators have jump discontinuities. In this setting, S-SEG iterates remain trapped in a region separated from the solution, whereas I-SEG would converge. This establishes that Assumption 2.3 is a substantive requirement for S-SEG, not merely an artifact of the proof.

2. High-Probability Gap Function Convergence on Unbounded Domains

For possibly unbounded domains, the authors establish high-probability convergence guarantees for both I-SEG and S-SEG under square-summable step-sizes ( $\sum \gamma_k^2 < \infty$ ).

Result: Under the Generalized Variance assumption (for I-SEG) and Uniform Lipschitzness (for S-SEG), both methods satisfy a conditional expected gap function bound on a high-probability event where iterates remain bounded.
Impossibility: The paper proves that these high-probability guarantees are essentially tight.
- Without square-summable step-sizes, both I-SEG and S-SEG can diverge almost surely (Theorems 3.9 and 3.10).
- Even with square-summable step-sizes, the iterates can escape any pre-specified bounded region with positive probability. Consequently, unconditional expected gap function convergence over a fixed bounded region cannot be guaranteed (Theorem 3.12). The limiting distribution of the iterates has unbounded support.

3. Fundamental Separation in Last-Iterate Convergence

The paper investigates almost-sure last-iterate convergence ( $x_k \to x^*$ ).

Quasi-Strict Monotonicity: Under the additional assumption of quasi-strict monotonicity (Assumption 2.8), both I-SEG and S-SEG converge almost surely to a solution with square-summable step-sizes (Theorem 4.1).
Failure of DSEG for S-SEG: A critical finding is that the Double Step-size Extragradient (DSEG) rule, which guarantees almost-sure last-iterate convergence for I-SEG on general monotone VIPs (without quasi-strict monotonicity), fails for S-SEG.
Evidence: The authors construct a stochastic monotone VIP with a unique solution where S-SEG, even when using DSEG step-sizes, diverges almost surely. Both the last iterate and the weighted average of iterates diverge to infinity (Theorem 4.2). This indicates that the independence of samples is a central mechanism for the convergence of DSEG, not just a proof convenience.

Significance and Claims

The paper claims to delineate the precise boundary between convergence and failure for the two principal variants of SEG. Its primary contributions are:

Clarification of S-SEG Requirements: It establishes that S-SEG requires stronger assumptions (uniform Lipschitzness of samples) than I-SEG, and that bounded variance alone is insufficient for convergence on compact sets.
Tightness of High-Probability Bounds: It shows that for unbounded domains, high-probability convergence is the strongest possible guarantee for SEG with symmetric step-sizes, as unconditional guarantees are generally impossible due to the unbounded support of the limiting distribution.
Fundamental Divergence of Variants: It proves that S-SEG and I-SEG are not interchangeable. Specifically, the DSEG step-size strategy, effective for I-SEG, cannot rescue S-SEG from divergence in the absence of quasi-strict monotonicity. This highlights that the sampling strategy (independent vs. same) fundamentally alters the algorithm's dynamics and convergence properties.

The authors conclude that while SEG is a foundational algorithm, the theoretical understanding of S-SEG lags behind I-SEG, and the two variants exhibit distinct behaviors that must be accounted for in algorithm design and analysis. The work does not propose new algorithms but rather provides a rigorous characterization of existing ones, identifying where current theoretical tools succeed and where they fundamentally fail.