# On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 60 references that are in the map.
- First posted on arXiv 30 Jun 2021.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks](https://mlsanity.com/paper/1511.06434/) (2015)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [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)
- [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 Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games](https://mlsanity.com/paper/1901.00838/) (2019)
- [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019)
- [Extragradient method with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1703.00260/) (2017)
- [Stochastic Hamiltonian Gradient Methods for Smooth Games](https://mlsanity.com/paper/2007.04202/) (2020)
- [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018)
- [A Closer Look at the Optimization Landscapes of Generative Adversarial Networks](https://mlsanity.com/paper/1906.04848/) (2019)
- [Accelerating Smooth Games by Manipulating Spectral Shapes](https://mlsanity.com/paper/2001.00602/) (2020)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [On the Adaptivity of Stochastic Gradient-Based Optimization](https://mlsanity.com/paper/1904.04480/) (2019)
- [Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball](https://mlsanity.com/paper/2006.07867/) (2020)
- [Forward-backward-forward methods with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1902.03355/) (2019)

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

- [The Primacy Bias in Deep Reinforcement Learning](https://mlsanity.com/paper/2205.07802/) (2022)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Solving stochastic weak Minty variational inequalities without increasing batch size](https://mlsanity.com/paper/2302.09029/) (2023)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (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)
- [Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization](https://mlsanity.com/paper/2206.08573/) (2022)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [Online Covariance Estimation in Nonsmooth Stochastic Approximation](https://mlsanity.com/paper/2502.05305/) (2025)
- [Randomized Stochastic Gradient Descent Ascent](https://mlsanity.com/paper/2111.13162/) (2021)
- [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)
- [Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization](https://mlsanity.com/paper/2210.17550/) (2022)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [When is Momentum Extragradient Optimal? A Polynomial-Based Analysis](https://mlsanity.com/paper/2211.04659/) (2022)

## Abstract (arXiv)

We study the stochastic bilinear minimax optimization problem, presenting an analysis of the same-sample Stochastic ExtraGradient (SEG) method with constant step size, and presenting variations of the method that yield favorable convergence. In sharp contrasts with the basic SEG method whose last iterate only contracts to a fixed neighborhood of the Nash equilibrium, SEG augmented with iteration averaging provably converges to the Nash equilibrium under the same standard settings, and such a rate is further improved by incorporating a scheduled restarting procedure. In the interpolation setting where noise vanishes at the Nash equilibrium, we achieve an optimal convergence rate up to tight constants. We present numerical experiments that validate our theoretical findings and demonstrate the effectiveness of the SEG method when equipped with iteration averaging and restarting.