Don't Fix What ain't Broke: Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization

Guodong Zhang, Yuanhao Wang, Laurent Lessard, Roger B. Grosse

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.

What Problem Does This Paper Address?

Minimax optimization, expressed as $\min_x \max_y f(x, y)$, is the engine behind some of the most exciting fields in machine learning, including Generative Adversarial Networks (GANs) and adversarial training. The most basic way to solve these is Gradient Descent-Ascent (GDA).

There are two ways to implement GDA:

  1. Simultaneous (Sim-GDA): Both players update their parameters at the same time using the current gradient.
  2. Alternating (Alt-GDA): Player 1 updates, then Player 2 updates using Player 1’s new parameters.

While practitioners almost exclusively use the alternating version, theorists have historically preferred the simultaneous version because it is easier to analyze as a single mathematical operator. However, Sim-GDA is notoriously "bad": it converges slowly and can even spiral out of control (diverge) in simple bilinear games. To fix this, researchers invented complex alternatives like Extra-Gradient (EG) or Optimistic GDA (OGDA). This paper asks: Is Alt-GDA actually a hidden gem that matches these complex algorithms without the extra overhead?

Figure 1: Comparison of trajectories for Sim-GDA (top) and Alt-GDA (bottom). Sim-GDA exhibits slow, spiraling convergence, while Alt-GDA suppresses these rotational forces to reach the equilibrium more directly.

Methods

The authors employ two primary mathematical frameworks to bridge the gap between theory and practice:

  • Local Convergence Analysis: They analyze the "spectral radius" (the largest eigenvalue) of the Jacobian matrix of the Alt-GDA update rule at the Nash equilibrium. Bounding this for alternating updates is mathematically difficult because it involves the composition of two different operators. They use a fine-grained analysis of complex eigenvalues to show how the sequential nature of Alt-GDA suppresses the "rotational forces" that cause Sim-GDA to fail.
  • Integral Quadratic Constraints (IQC): Borrowing a tool from control theory, the authors use IQCs to search for "Lyapunov functions"—mathematical energy functions that prove an algorithm will eventually settle down. This allows them to prove global convergence for a specific subclass of minimax problems.

Key Insights and Ideas

  • The Quadratic Speedup: The headline result is that Alt-GDA converges in $O(\kappa)$ iterations, while Sim-GDA takes $O(\kappa^2)$. In optimization, this is a massive difference—if a problem is poorly conditioned ($\kappa=100$), Alt-GDA could be 100 times faster.
  • Suppressing Rotation: Minimax problems often suffer from "rotational" behavior where the parameters circle the solution forever. The authors show that by using the "fresher" gradient from the first player's update, the second player effectively dampens this rotation.
  • Optimism is Redundant for Alternating Updates: A popular technique called "optimism" (used in OGDA) was thought to be necessary for fast convergence. The authors show that while optimism helps Sim-GDA, it provides almost no benefit to Alt-GDA. Essentially, the act of alternating is a form of optimism.
  • Bilinear Components are "Free": In Sim-GDA, the interaction term between players (the bilinear part) is what causes slow-down. In Alt-GDA, this term doesn't make the problem any harder than a standard minimization task.

Key Results

Numerical experiments confirmed that as the problem becomes harder (higher condition number $\kappa$), the number of iterations for Alt-GDA grows linearly, whereas for Sim-GDA, it grows quadratically. This confirms the theoretical $O(\kappa)$ vs $O(\kappa^2)$ gap.

Figure 3: Iterations to convergence vs. condition number. The log-log plot shows that Alt-GDA scales linearly with the condition number, while Sim-GDA scales quadratically, representing a significant efficiency gain.
  • Theoretical Optimality: Alt-GDA matches the iteration complexity of much more complex algorithms like Extra-Gradient (EG) and Optimistic GDA (OGDA).
  • Empirical Speedup: In GAN experiments on CIFAR-10, alternating updates reached lower FID scores (a measure of image quality) significantly faster than simultaneous updates.

Limitations and Future Work

While the local convergence (near the solution) is well-proven for general cases, the global convergence proof is currently limited to "bilinearly-coupled" problems. Proving global convergence for all strongly convex-strongly concave problems remains an open challenge. Additionally, while the authors show it works on non-convex GANs, the theoretical guarantee for the non-convex regime is still a "frontier" area. Future work could also explore how the noise inherent in mini-batch SGD affects these alternating dynamics.

Summary updated

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.
BibTeX
@inproceedings{zhang2022don,
  author = {Guodong Zhang and Yuanhao Wang and Laurent Lessard and Roger B. Grosse},
  title = {{Don't Fix What ain't Broke: Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=NRadyK-I2Hw},
}
Figure