mlsanityData to 7 Oct 2026

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity

arXiv 2107.00052 ↗First posted 30 Jun 2021cs.LG cs.GT math.OCcited by 43

Not on the map. Why?

Abstract (arXiv)

Two of the most prominent algorithms for solving unconstrained smooth games are the classical stochastic gradient descent-ascent (SGDA) and the recently introduced stochastic consensus optimization (SCO) [Mescheder et al., 2017]. SGDA is known to converge to a stationary point for specific classes of games, but current convergence analyses require a bounded variance assumption. SCO is used successfully for solving large-scale adversarial problems, but its convergence guarantees are limited to its deterministic variant. In this work, we introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO under this condition for solving a class of stochastic variational inequality problems that are potentially non-monotone. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size, and we propose insightful stepsize-switching rules to guarantee convergence to the exact solution. In addition, our convergence guarantees hold under the arbitrary sampling paradigm, and as such, we give insights into the complexity of minibatching.

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

Builds on

43 of 82 references.

References · 43

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  3. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  5. 2017Training GANs with Optimismcited by 217
  6. 2019SGD: General Analysis and Improved Ratescited by 206
  7. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  8. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  9. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  10. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  11. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  12. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
31 more
  1. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  2. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  3. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  4. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 94
  5. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  6. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  7. 2016Learning in games with continuous action sets and unknown payoff functionscited by 78
  8. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  9. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  10. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
  11. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  12. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  13. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  14. 2016Connecting Generative Adversarial Networks and Actor-Critic Methodscited by 49
  15. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  16. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  17. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  18. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  19. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  20. 2019Revisiting Stochastic Extragradientcited by 35
  21. 2015A Three-Operator Splitting Scheme and its Optimization Applicationscited by 34
  22. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  23. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  24. 2020Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Gamescited by 26
  25. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  26. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  27. 2017Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theorycited by 16
  28. 2013On Optimal Probabilities in Stochastic Coordinate Descent Methodscited by 14
  29. 2019Convergence Analysis of Inexact Randomized Iterative Methodscited by 8
  30. 2021Stochastic Gradient Descent on Nonconvex Functions with General Noise Modelscited by 7
  31. 2014A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spacescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 10; 2023: 10; 2024: 10; 2025: 3; 2026: 7.

43 papers.

Sort:

  1. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  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. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 17
  7. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  8. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  9. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 13
  10. 2022Communication-Efficient Distributionally Robust Decentralized Learningcited by 10
  11. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  12. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
31 more
  1. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  2. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  3. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 8
  4. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  5. 2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
  6. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  7. 2024SDEs for Minimax Optimizationcited by 6
  8. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  9. 2024Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalitiescited by 5
  10. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  11. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  12. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  13. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  14. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  15. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 3
  16. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  17. 2023Distributed Extra-gradient with Optimal Complexity and Communication Guaranteescited by 2
  18. 2024An Inexact Halpern Iteration with Application to Distributionally Robust Optimizationcited by 2
  19. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 2
  20. 2024Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicitycited by 1
  21. 2024Solving Hidden Monotone Variational Inequalities with Surrogate Lossescited by 1
  22. 2022SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalitiescited by 0
  23. 2023Omega: Optimistic EMA Gradientscited by 0
  24. 2024Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimizationcited by 0
  25. 2025Multi-agent learning under uncertainty: Recurrence vs. concentrationcited by 0
  26. 2026PPEDCRF: Privacy-Preserving Enhanced Dynamic CRF for Location-Privacy Protection for Sequence Videos with Minimal Detection Degradationcited by 0
  27. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 0
  28. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0
  29. 2026Last-Iterate Guarantees for Learning in Co-coercive Gamescited by 0
  30. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
  31. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0