# Stochastic Extragradient: General Analysis and Improved Rates

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 57 references that are in the map.
- First posted on arXiv 16 Nov 2021.

## Builds on (most cited first, 30 of 36)

- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [Minimax Estimation of Conditional Moment Models](https://mlsanity.com/paper/2006.07201/) (2020)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Reducing Noise in GAN Training with Variance Reduced Extragradient](https://mlsanity.com/paper/1904.08598/) (2019)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Connecting Generative Adversarial Networks and Actor-Critic Methods](https://mlsanity.com/paper/1610.01945/) (2016)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization](https://mlsanity.com/paper/2006.11573/) (2020)
- [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019)
- [Adversarial Example Games](https://mlsanity.com/paper/2007.00720/) (2020)
- [Stochastic Hamiltonian Gradient Methods for Smooth Games](https://mlsanity.com/paper/2007.04202/) (2020)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities](https://mlsanity.com/paper/2103.04410/) (2021)
- [Last-iterate convergence rates for min-max optimization](https://mlsanity.com/paper/1906.02027/) (2019)
- [Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants](https://mlsanity.com/paper/1410.1628/) (2014)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory](https://mlsanity.com/paper/1706.01108/) (2017)
- [On Optimal Probabilities in Stochastic Coordinate Descent Methods](https://mlsanity.com/paper/1310.3438/) (2013)

## Built on by (most cited first, 30 of 31)

- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Solving stochastic weak Minty variational inequalities without increasing batch size](https://mlsanity.com/paper/2302.09029/) (2023)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2206.01095/) (2022)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Sharpness-Aware Minimization: General Analysis and Improved Rates](https://mlsanity.com/paper/2503.02225/) (2025)
- [Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems](https://mlsanity.com/paper/2210.09382/) (2022)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [SDEs for Minimax Optimization](https://mlsanity.com/paper/2402.12508/) (2024)
- [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025)
- [Distributed Methods with Absolute Compression and Error Compensation](https://mlsanity.com/paper/2203.02383/) (2022)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization](https://mlsanity.com/paper/2403.09090/) (2024)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Extragradient Method for (L0, L1)-Lipschitz Root-finding Problems](https://mlsanity.com/paper/2510.22421/) (2025)
- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity](https://mlsanity.com/paper/2410.20649/) (2024)
- [Stochastic variance reduced extragradient methods for solving hierarchical variational inequalities](https://mlsanity.com/paper/2602.13510/) (2026)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)
- [SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities](https://mlsanity.com/paper/2210.05994/) (2022)
- [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023)
- [Omega: Optimistic EMA Gradients](https://mlsanity.com/paper/2306.07905/) (2023)
- [Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2410.22297/) (2024)
- [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)

The Stochastic Extragradient (SEG) method is one of the most popular algorithms for solving min-max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. However, several important questions regarding the convergence properties of SEG are still open, including the sampling of stochastic gradients, mini-batching, convergence guarantees for the monotone finite-sum variational inequalities with possibly non-monotone terms, and others. To address these questions, in this paper, we develop a novel theoretical framework that allows us to analyze several variants of SEG in a unified manner. Besides standard setups, like Same-Sample SEG under Lipschitzness and monotonicity or Independent-Samples SEG under uniformly bounded variance, our approach allows us to analyze variants of SEG that were never explicitly considered in the literature before. Notably, we analyze SEG with arbitrary sampling which includes importance sampling and various mini-batching strategies as special cases. Our rates for the new variants of SEG outperform the current state-of-the-art convergence guarantees and rely on less restrictive assumptions.