mlsanityData to 7 Oct 2026

Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization

arXiv 2102.09468 ↗First posted 18 Feb 2021cs.LG math.OC stat.MLcited by 31

Not on the map. Why?

Abstract (arXiv)

Smooth minimax games often proceed by simultaneous or alternating gradient updates. Although algorithms with alternating updates are commonly used in practice, the majority of existing theoretical analyses focus on simultaneous algorithms for convenience of analysis. In this paper, we study alternating gradient descent-ascent (Alt-GDA) in minimax games and show that Alt-GDA is superior to its simultaneous counterpart~(Sim-GDA) in many settings. We prove that Alt-GDA achieves a near-optimal local convergence rate for strongly convex-strongly concave (SCSC) problems while Sim-GDA converges at a much slower rate. To our knowledge, this is the first result of any setting showing that Alt-GDA converges faster than Sim-GDA by more than a constant. We further adapt the theory of integral quadratic constraints (IQC) and show that Alt-GDA attains the same rate globally for a subclass of SCSC minimax problems. Empirically, we demonstrate that alternating updates speed up GAN training significantly and the use of optimism only helps for simultaneous algorithms.

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

Builds on

38 of 71 references.

References · 38

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2016Improved Techniques for Training GANscited by 2,938
  3. 2017Improved Training of Wasserstein GANscited by 2,223
  4. 2015Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networkscited by 2,048
  5. 2018Spectral Normalization for Generative Adversarial Networkscited by 1,618
  6. 2019On the Convergence of Adam and Beyondcited by 834
  7. 2017Training GANs with Optimismcited by 217
  8. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  9. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  10. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  11. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  12. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
26 more
  1. 2019Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Modelcited by 116
  2. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  3. 2017The Numerics of GANscited by 104
  4. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  5. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  6. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  7. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  8. 2018Negative Momentum for Improved Game Dynamicscited by 59
  9. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  10. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  11. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  12. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  13. 2019Differentiable Game Mechanicscited by 43
  14. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  15. 2019On Solving Minimax Optimization Locally: A Follow-the-Ridge Approachcited by 34
  16. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  17. 2019Competitive Gradient Descentcited by 32
  18. 2018Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexitycited by 28
  19. 2019Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascentcited by 28
  20. 2020Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problemscited by 26
  21. 2020Accelerating Smooth Games by Manipulating Spectral Shapescited by 18
  22. 2020Taming GANs with Lookahead-Minmaxcited by 16
  23. 2017First-order Methods Almost Always Avoid Saddle Pointscited by 14
  24. 2019Convergence of Gradient Methods on Bilinear Zero-Sum Gamescited by 12
  25. 2020On the Suboptimality of Negative Momentum for Minimax Optimizationcited by 11
  26. 2020A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraintscited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 3; 2024: 8; 2025: 7; 2026: 4.

31 papers.

Sort:

By area:

  1. 2024Scalable Reinforcement Post-Training Beyond Static Human Prompts: Evolving Alignment via Asymmetric Self-Playcited by 21
  2. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  3. 2024On PI Controllers for Updating Lagrange Multipliers in Constrained Optimizationcited by 12
  4. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  5. 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 9
  6. 2021Lyapunov Exponents for Diversity in Differentiable Gamescited by 8
  7. 2023Balancing Act: Constraining Disparate Impact in Sparse Modelscited by 7
  8. 2025Feasible Learningcited by 5
  9. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  10. 2022Similarity-based cooperative equilibriumcited by 3
  11. 2025Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Gamescited by 3
  12. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
19 more
  1. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  2. 2024Electroencephalogram Emotion Recognition via AUC Maximizationcited by 2
  3. 2025Provably Safe Model Updatescited by 2
  4. 2026Optimal Alternating Regret for Online Learning and Gamescited by 2
  5. 2022Recursive Reasoning in Minimax Games: A Level k Gradient Play Methodcited by 1
  6. 2023An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problemscited by 1
  7. 2024Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifoldcited by 1
  8. 2025Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguisecited by 1
  9. 2025Min-Max Optimization Is Strictly Easier Than Variational Inequalitiescited by 1
  10. 2026Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizescited by 1
  11. 2021GDA-AM: On the effectiveness of solving minimax optimization via Anderson Accelerationcited by 0
  12. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0
  13. 2023Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Sufficescited by 0
  14. 2024Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Stepscited by 0
  15. 2024Towards stable training of parallel continual learningcited by 0
  16. 2024Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approachcited by 0
  17. 2025Decoupled SGDA for Games with Intermittent Strategy Communicationcited by 0
  18. 2026Negative Momentum for Convex-Concave Optimizationcited by 0
  19. 2026Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approachcited by 0