mlsanityData to 7 Oct 2026

Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods

arXiv 2202.07262 ↗First posted 15 Feb 2022math.OC cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

Stochastic Gradient Descent-Ascent (SGDA) is one of the most prominent algorithms for solving min-max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. The success of the method led to several advanced extensions of the classical SGDA, including variants with arbitrary sampling, variance reduction, coordinate randomization, and distributed variants with compression, which were extensively studied in the literature, especially during the last few years. In this paper, we propose a unified convergence analysis that covers a large variety of stochastic gradient descent-ascent methods, which so far have required different intuitions, have different applications and have been developed separately in various communities. A key to our unified framework is a parametric assumption on the stochastic estimates. Via our general theoretical framework, we either recover the sharpest known rates for the known special cases or tighten them. Moreover, to illustrate the flexibility of our approach we develop several new variants of SGDA such as a new variance-reduced method (L-SVRGDA), new distributed methods with compression (QSGDA, DIANA-SGDA, VR-DIANA-SGDA), and a new method with coordinate randomization (SEGA-SGDA). Although variants of the new methods are known for solving minimization problems, they were never considered or analyzed for solving min-max problems and VIPs. We also demonstrate the most important properties of the new methods through extensive numerical experiments.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). Builds on 59 of its 109 references that are in the map. First posted on arXiv 15 Feb 2022.

Builds on

59 of 109 references.

References · 59

  1. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  2. 2018Sparsified SGD with Memorycited by 373
  3. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  4. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  5. 2019SGD: General Analysis and Improved Ratescited by 206
  6. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  7. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  8. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  9. 2020On Biased Compression for Distributed Learningcited by 140
  10. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  11. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  12. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
38 more
  1. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  2. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  3. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  4. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  5. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  6. 2016Learning in games with continuous action sets and unknown payoff functionscited by 78
  7. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  8. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  9. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  10. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
  11. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  12. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  13. 2020Linearly Converging Error Compensated SGDcited by 61
  14. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  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. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  18. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  19. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  20. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  21. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  22. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  23. 2019Variance Reduction for Matrix Gamescited by 37
  24. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  25. 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 35
  26. 2019Revisiting Stochastic Extragradientcited by 35
  27. 2015A Three-Operator Splitting Scheme and its Optimization Applicationscited by 34
  28. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  29. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  30. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  31. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  32. 2020Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Gamescited by 26
  33. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  34. 2020Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexitiescited by 21
  35. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  36. 2017Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theorycited by 16
  37. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  38. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15

50 most cited of 59 All 59 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 14; 2024: 5; 2025: 7; 2026: 5.

37 papers.

Sort:

  1. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  2. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  3. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  4. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  5. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 13
  6. 2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
  7. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  8. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  9. 2025Sharpness-Aware Minimization: General Analysis and Improved Ratescited by 10
  10. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  11. 2023Balancing Act: Constraining Disparate Impact in Sparse Modelscited by 7
  12. 2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
25 more
  1. 2023CrossDF: Improving Cross-Domain Deepfake Detection with Deep Information Decompositioncited by 6
  2. 2024Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalitiescited by 5
  3. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  4. 2022Distributed Methods with Absolute Compression and Error Compensationcited by 4
  5. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  6. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  7. 2024Gradient-based Learning in State-based Potential Games for Self-Learning Production Systemscited by 3
  8. 2025Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problemscited by 3
  9. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  10. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 3
  11. 2023Distributed Extra-gradient with Optimal Complexity and Communication Guaranteescited by 2
  12. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 2
  13. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 2
  14. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1
  15. 2026On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisationcited by 1
  16. 2022Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Topcited by 0
  17. 2022SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalitiescited by 0
  18. 2023Unified analysis of SGD-type methodscited by 0
  19. 2023Omega: Optimistic EMA Gradientscited by 0
  20. 2023DePAint: A Decentralized Safe Multi-Agent Reinforcement Learning Algorithm considering Peak and Average Constraintscited by 0
  21. 2024Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimizationcited by 0
  22. 2025HOME-3: High-Order Momentum Estimator with Third-Power Gradient for Convex and Smooth Nonconvex Optimizationcited by 0
  23. 2025Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approachcited by 0
  24. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 0
  25. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0