mlsanityData to 14 Oct 2026

Stochastic Extragradient: General Analysis and Improved Rates

arXiv 2111.08611 ↗First posted 16 Nov 2021math.OC cs.LGcited by 31

Not on the map. Why?

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.

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

36 of 57 references.

References · 36

  1. 2017FeUdal Networks for Hierarchical Reinforcement Learningcited by 337
  2. 2019SGD: General Analysis and Improved Ratescited by 207
  3. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  4. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  5. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  6. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  7. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  8. 2020Minimax Estimation of Conditional Moment Modelscited by 83
  9. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
  10. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  11. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  12. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
24 more
  1. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
  2. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  3. 2016Connecting Generative Adversarial Networks and Actor-Critic Methodscited by 50
  4. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  5. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  6. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  7. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  8. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  9. 2019Revisiting Stochastic Extragradientcited by 35
  10. 2020Adversarial Example Gamescited by 34
  11. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  12. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  13. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  14. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  15. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  16. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  17. 2017Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theorycited by 16
  18. 2013On Optimal Probabilities in Stochastic Coordinate Descent Methodscited by 14
  19. 2014Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexitycited by 14
  20. 2018Nonconvex Variance Reduced Optimization with Arbitrary Samplingcited by 14
  21. 2013An Accelerated Randomized Kaczmarz Algorithmcited by 12
  22. 2018Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatchescited by 11
  23. 2019Convergence Analysis of Inexact Randomized Iterative Methodscited by 8
  24. 2019Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocolscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 8; 2024: 6; 2025: 4; 2026: 7.

31 papers.

Sort:

  1. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  2. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  3. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  4. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 14
  5. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  6. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  7. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  8. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  9. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  10. 2025Sharpness-Aware Minimization: General Analysis and Improved Ratescited by 10
  11. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  12. 2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
19 more
  1. 2024SDEs for Minimax Optimizationcited by 6
  2. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  3. 2022Distributed Methods with Absolute Compression and Error Compensationcited by 4
  4. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  5. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  6. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 4
  7. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 3
  8. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  9. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 3
  10. 2024Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicitycited by 1
  11. 2026Stochastic variance reduced extragradient methods for solving hierarchical variational inequalitiescited by 1
  12. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 1
  13. 2022SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalitiescited by 0
  14. 2023Unified analysis of SGD-type methodscited by 0
  15. 2023Omega: Optimistic EMA Gradientscited by 0
  16. 2024Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimizationcited by 0
  17. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
  18. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0
  19. 2026Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Findingcited by 0