Local Convergence Analysis of Gradient Descent Ascent with Finite Timescale Separation

Tanner Fiez, Lillian J RatliffICLR 2021 · OpenReview

Introduction

Training models like Generative Adversarial Networks (GANs) involves solving a zero-sum game: one player (the generator) tries to minimize a loss while another (the discriminator) tries to maximize it. The standard tool for this optimization is Gradient Descent-Ascent (GDA).

However, GDA is notoriously finicky in non-convex, non-concave settings. In many cases, the players oscillate endlessly or converge to "bad" critical points that lack true game-theoretic meaning. While researchers have long suspected that making the discriminator learn faster than the generator—a concept known as timescale separation—helps stabilize training, most theoretical proofs only worked if the discriminator was infinitely faster. This condition is impossible to implement in real-world code. This paper provides the first non-asymptotic analysis of GDA with a finite timescale separation, determining exactly how much faster one player needs to be to guarantee local stability and convergence.

Methods

The authors analyze the $\tau$-GDA algorithm, where the learning rate of player 2 is $\tau$ times the learning rate of player 1 ($\gamma_2 = \tau \gamma_1$).

Key technical contributions include:

  • Non-Asymptotic Construction of $\tau^*$: The authors derive a specific, computable threshold for the learning rate ratio. If $\tau > \tau^*$, GDA is guaranteed to be locally stable at a strict local minmax equilibrium.
  • Guard Maps: Borrowing tools from control theory, they use "guard maps" to track when the eigenvalues of the system's Jacobian cross into the stable region of the complex plane as $\tau$ varies.
  • Instability Analysis: They prove that for any critical point that is not a local minmax equilibrium, there exists a $\tau_0$ such that for all ratios larger than that, GDA will actively move away from that point, avoiding bad critical points.
  • Regularization Extension: They extend their analysis to GANs using gradient penalties, showing how these common heuristics interact with timescale separation to ensure convergence.

Key Insights

  • Stackelberg is the Goal: In non-convex games, the "Nash Equilibrium" (simultaneous play) is often too restrictive or non-existent. The "Stackelberg Equilibrium" (leader-follower) is a more natural fit for GDA with timescale separation, as the faster player effectively "follows" the slower player's moves.
  • The $\tau$ Threshold: Stability isn't a binary state. There is a specific "tipping point" for the learning rate ratio. Below this point, the system may oscillate; above it, the rotational dynamics vanish, and the system converges.
Phase portraits demonstrating how increasing the timescale separation parameter τ eliminates rotational dynamics and leads to stable convergence.
  • Regularization as a Bridge: Gradient penalties don't just "smooth" the landscape; they mathematically shift the game's structure so that the equilibrium becomes a differential Stackelberg equilibrium, making it "catchable" by GDA.
  • Oscillations Aren't Always Bad: Experiments show that some cyclic behavior can exist even as the system converges. A moderate $\tau$ (like 4 or 8) often converges faster than a massive $\tau$ that makes the system numerically ill-conditioned.

Key Results

The paper validates its theoretical findings using a simple Dirac-GAN for trajectory visualization, as well as CIFAR-10 and CelebA for evaluating GAN performance via the Frechet Inception Distance (FID) score.

  • Convergence Guarantee: The authors prove that $\tau$-GDA converges locally to $x^*$ if and only if $x^*$ is a strict local minmax equilibrium, provided $\tau$ is large enough.
  • Explicit Rates: The study provides a local convergence rate of $O((1 - \alpha/(4\beta))^{k/2})$, giving engineers a way to estimate training time.
Convergence rates showing the distance to the equilibrium over iterations for different timescale separations.
  • Empirical Gains: On CIFAR-10 and CelebA, using a timescale separation of $\tau=4$ or $\tau=8$ consistently resulted in lower (better) FID scores compared to the standard $\tau=1$ (shared learning rate). For example, on CelebA with $\mu=1$ regularization, $\tau=8$ achieved an FID of 8.0, while $\tau=1$ was stuck at 13.1.

Limitations and Future Work

  • Local vs. Global: The analysis is strictly local. It dictates behavior near an equilibrium but doesn't guarantee finding one from a random starting point (the "global convergence" problem).
  • Computational Complexity of $\tau^*$: While $\tau^*$ is efficiently computable for small matrices, calculating it for a deep neural network with millions of parameters involves high-dimensional Kronecker products, which is currently impractical.
  • Smoothness Requirements: The proofs require the objective function to be at least twice-continuously differentiable ($C^2$), which may not hold for all neural network architectures (e.g., those using certain non-smooth activations).
  • Future Direction: The authors suggest exploring how to adaptively tune $\tau$ during training rather than picking a fixed value.

Summary updated

Abstract

We study the role that a finite timescale separation parameter $\tau$ has on gradient descent-ascent in non-convex, non-concave zero-sum games where the learning rate of player 1 is denoted by $\gamma_1$ and the learning rate of player 2 is defined to be $\gamma_2=\tau\gamma_1$. We provide a non-asymptotic construction of the finite timescale separation parameter $\tau^{\ast}$ such that gradient descent-ascent locally converges to $x^{\ast}$ for all $\tau \in (\tau^{\ast}, \infty)$ if and only if it is a strict local minmax equilibrium. Moreover, we provide explicit local convergence rates given the finite timescale separation. The convergence results we present are complemented by a non-convergence result: given a critical point $x^{\ast}$ that is not a strict local minmax equilibrium, we present a non-asymptotic construction of a finite timescale separation $\tau_{0}$ such that gradient descent-ascent with timescale separation $\tau\in (\tau_0, \infty)$ does not converge to $x^{\ast}$. Finally, we extend the results to gradient penalty regularization methods for generative adversarial networks and empirically demonstrate on CIFAR-10 and CelebA the significant impact timescale separation has on training performance.
BibTeX
@inproceedings{fiez2021local,
  author = {Tanner Fiez and Lillian J Ratliff},
  title = {{Local Convergence Analysis of Gradient Descent Ascent with Finite Timescale Separation}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=AWOSz_mMAPx},
}
Figure