mlsanityData to 7 Oct 2026

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

arXiv 2107.00464 ↗First posted 30 Jun 2021math.OC cs.GT cs.LGcited by 18

Not on the map. Why?

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.

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

Builds on

30 of 60 references.

References · 30

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2015Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networkscited by 2,048
  3. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  4. 2017Training GANs with Optimismcited by 217
  5. 2019SGD: General Analysis and Improved Ratescited by 206
  6. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  7. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  8. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  9. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  10. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  11. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  12. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
18 more
  1. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
  2. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  3. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  4. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  5. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  6. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  7. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  8. 2019On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Gamescited by 35
  9. 2019Revisiting Stochastic Extragradientcited by 35
  10. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  11. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  12. 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
  13. 2019A Closer Look at the Optimization Landscapes of Generative Adversarial Networkscited by 25
  14. 2020Accelerating Smooth Games by Manipulating Spectral Shapescited by 18
  15. 2018A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methodscited by 14
  16. 2019On the Adaptivity of Stochastic Gradient-Based Optimizationcited by 7
  17. 2020Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ballcited by 6
  18. 2019Forward-backward-forward methods with variance reduction for stochastic variational inequalitiescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 3; 2024: 2; 2025: 3; 2026: 1.

18 papers.

Sort:

  1. 2022The Primacy Bias in Deep Reinforcement Learningcited by 242
  2. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  3. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  4. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  5. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  6. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  7. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  8. 2024SDEs for Minimax Optimizationcited by 6
  9. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  10. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4
  11. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  12. 2025Online Covariance Estimation in Nonsmooth Stochastic Approximationcited by 4
6 more
  1. 2021Randomized Stochastic Gradient Descent Ascentcited by 3
  2. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  3. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  4. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  5. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 2
  6. 2022When is Momentum Extragradient Optimal? A Polynomial-Based Analysiscited by 1