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

arXiv: https://arxiv.org/abs/2102.09468 · HTML: https://mlsanity.com/paper/2102.09468/

## Key facts

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

## Builds on (most cited first, 30 of 38)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks](https://mlsanity.com/paper/1511.06434/) (2015)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model](https://mlsanity.com/paper/1907.04164/) (2019)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Off-Policy Evaluation via the Regularized Lagrangian](https://mlsanity.com/paper/2007.03438/) (2020)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020)
- [Differentiable Game Mechanics](https://mlsanity.com/paper/1905.04926/) (2019)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach](https://mlsanity.com/paper/1910.07512/) (2019)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Competitive Gradient Descent](https://mlsanity.com/paper/1905.12103/) (2019)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)

## Built on by (most cited first, 30 of 31)

- [Scalable Reinforcement Post-Training Beyond Static Human Prompts: Evolving Alignment via Asymmetric Self-Play](https://mlsanity.com/paper/2411.00062/) (2024)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [On PI Controllers for Updating Lagrange Multipliers in Constrained Optimization](https://mlsanity.com/paper/2406.04558/) (2024)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Lyapunov Exponents for Diversity in Differentiable Games](https://mlsanity.com/paper/2112.14570/) (2021)
- [Balancing Act: Constraining Disparate Impact in Sparse Models](https://mlsanity.com/paper/2310.20673/) (2023)
- [Feasible Learning](https://mlsanity.com/paper/2501.14912/) (2025)
- [Similarity-based cooperative equilibrium](https://mlsanity.com/paper/2211.14468/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games](https://mlsanity.com/paper/2505.19537/) (2025)
- [Provably Safe Model Updates](https://mlsanity.com/paper/2512.01899/) (2025)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Recursive Reasoning in Minimax Games: A Level k Gradient Play Method](https://mlsanity.com/paper/2210.16482/) (2022)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Electroencephalogram Emotion Recognition via AUC Maximization](https://mlsanity.com/paper/2408.08979/) (2024)
- [Optimal Alternating Regret for Online Learning and Games](https://mlsanity.com/paper/2608.24731/) (2026)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold](https://mlsanity.com/paper/2405.13392/) (2024)
- [Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise](https://mlsanity.com/paper/2509.22500/) (2025)
- [Min-Max Optimization Is Strictly Easier Than Variational Inequalities](https://mlsanity.com/paper/2511.03052/) (2025)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration](https://mlsanity.com/paper/2110.02457/) (2021)
- [Iterative Minimax Games with Coupled Linear Constraints](https://mlsanity.com/paper/2212.04672/) (2022)
- [Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices](https://mlsanity.com/paper/2305.17275/) (2023)
- [Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps](https://mlsanity.com/paper/2407.02689/) (2024)
- [Towards stable training of parallel continual learning](https://mlsanity.com/paper/2407.08214/) (2024)
- [Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach](https://mlsanity.com/paper/2410.14592/) (2024)
- [Decoupled SGDA for Games with Intermittent Strategy Communication](https://mlsanity.com/paper/2501.14652/) (2025)
- [Negative Momentum for Convex-Concave Optimization](https://mlsanity.com/paper/2604.17145/) (2026)

## 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.