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 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.
Introduction
Minimax optimization—the task of finding a point that minimizes a function with respect to one variable while maximizing it with respect to another ($\\min_x \\max_y f(x, y)$)—is the engine behind Generative Adversarial Networks (GANs), adversarial training, and robust optimization.
The most common way to solve these is Gradient Descent-Ascent (GDA). There are two primary variants:
- Sim-GDA: Both players update their parameters simultaneously based on the current state.
- Alt-GDA: One player updates, then the second player updates using the first player's newly calculated position.
Despite Alt-GDA being the "default" in popular GAN implementations, most theoretical research focuses on Sim-GDA because it is mathematically easier to analyze as a single operator. However, Sim-GDA is notoriously slow and often fails to converge even on simple bilinear problems. This paper bridges the gap between practice and theory, proving why Alt-GDA is superior and quantifying its speedup.
Methodology
The authors employ two primary theoretical frameworks to analyze Alt-GDA:
- Local Convergence Analysis: By analyzing the spectral radius of the Jacobian matrix of the update operators at the Nash equilibrium, the authors bound the convergence rate for Strongly Convex-Strongly Concave (SCSC) problems.
- Integral Quadratic Constraints (IQC): Borrowing from control theory, the authors use the IQC framework to automatically search for Lyapunov functions. This allows them to certify global convergence rates for a specific subclass of bilinearly-coupled minimax problems by solving a Semi-Definite Program (SDP).
Key Insights: Suppressing the Rotational Force
In minimax games, the interaction between players creates a "rotational" component in the gradient field. Sim-GDA tends to get "stuck" in these rotations, requiring tiny step sizes to converge or spiraling outward. Alt-GDA effectively "suppresses" this rotational force.
Beyond visualization, the paper provides a rigorous complexity result. For a problem with condition number $\\kappa$, Sim-GDA requires $O(\\kappa^2)$ iterations to converge. The authors prove Alt-GDA only needs $O(\\kappa)$ iterations. This matches the complexity of more "sophisticated" algorithms like Extra-Gradient (EG) or Optimistic GDA (OGDA).
Furthermore, the authors address the popular technique of "optimism" (using past gradients to stabilize training). They show that while optimism significantly helps Sim-GDA, it provides almost no benefit to Alt-GDA. This suggests that the act of alternating updates already provides the stabilization that optimism aims to achieve.
Empirical Results
The theoretical findings were validated across synthetic and real-world datasets:
- Synthetic Quadratic Games: In controlled environments, Alt-GDA converged significantly faster than Sim-GDA, matching the predicted $O(\\kappa)$ rate.
- GAN Training: On CIFAR-10 and SVHN, alternating updates led to faster training and better Fréchet Inception Distance (FID) scores. For example, in DCGAN training on CIFAR-10, Alt-GDA reached a stable FID score in roughly half the iterations required by Sim-GDA.
Conclusion and Future Work
This work provides the first theoretical proof that Alt-GDA is fundamentally faster than Sim-GDA by more than a constant factor in SCSC settings. While the strongest results apply to local convergence, the use of IQC offers a path toward global certificates. Future work remains in bridging these insights to the non-convex/non-concave regimes typical of deep learning and exploring the robustness of Alt-GDA to hyperparameter tuning in complex environments.
Summary updated