# Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants

arXiv: https://arxiv.org/abs/1410.1628 · HTML: https://mlsanity.com/paper/1410.1628/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2014.

## Built on by (most cited first, 19 of 19)

- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Solving stochastic weak Minty variational inequalities without increasing batch size](https://mlsanity.com/paper/2302.09029/) (2023)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees](https://mlsanity.com/paper/2110.03313/) (2021)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers](https://mlsanity.com/paper/2106.13067/) (2021)
- [On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.06182/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)

## Abstract (arXiv)

We consider the stochastic variational inequality problem in which the map is expectation-valued in a component-wise sense. Much of the available convergence theory and rate statements for stochastic approximation schemes are limited to monotone maps. However, non-monotone stochastic variational inequality problems are not uncommon and are seen to arise from product pricing, fractional optimization problems, and subclasses of economic equilibrium problems. Motivated by the need to address a broader class of maps, we make the following contributions: (i) We present an extragradient-based stochastic approximation scheme and prove that the iterates converge to a solution of the original problem under either pseudomonotonicity requirements or a suitably defined acute angle condition. Such statements are shown to be generalizable to the stochastic mirror-prox framework; (ii) Under strong pseudomonotonicity, we show that the mean-squared error in the solution iterates produced by the extragradient SA scheme converges at the optimal rate of O(1/k) statements that were hitherto unavailable K in this regime. Notably, we optimize the initial steplength by obtaining an ε-infimum of a discontinuous nonconvex function. Similar statements are derived for mirror-prox generalizations and can accommodate monotone SVIs under a weak-sharpness requirement. Finally, both the asymptotics and the empirical rates of the schemes are studied on a set of variational problems where it is seen that the theoretically specified initial steplength leads to significant performance benefits.