Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
arXiv:2102.09468
Abstract
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 \emph{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 \emph{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.
arXiv commentAISTATS 2022
References in corpus (19)
- Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
- GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
- Spectral Normalization for Generative Adversarial Networks
- On the Convergence of Adam and Beyond
- Improved Techniques for Training GANs
- The Numerics of GANs
- A Variational Inequality Perspective on Generative Adversarial Networks
- A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- First-order Methods Almost Always Avoid Saddle Points
- Stochastic Variance Reduction Methods for Policy Evaluation
- Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
- Differentiable Game Mechanics
- Linear Lower Bounds and Conditioning of Differentiable Games
- Accelerating Smooth Games by Manipulating Spectral Shapes
- Convergence of Gradient Methods on Bilinear Zero-Sum Games
- A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
- On the Suboptimality of Negative Momentum for Minimax Optimization
- DIPPA: An improved Method for Bilinear Saddle Point Problems