Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation

Abstract

We study the role that a finite timescale separation parameter $\tau$ has on gradient descent-ascent in two-player 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$. Existing work analyzing the role of timescale separation in gradient descent-ascent has primarily focused on the edge cases of players sharing a learning rate ($\tau =1$) and the maximizing player approximately converging between each update of the minimizing player ($\tau \to \infty$). For the parameter choice of $\tau =1$, it is known that the learning dynamics are not guaranteed to converge to a game-theoretically meaningful equilibria in general. In contrast, Jin et al. (2020) showed that the stable critical points of gradient descent-ascent coincide with the set of strict local minmax equilibria as $\tau \to \infty$. In this work, we bridge the gap between past work by showing there exists a finite timescale separation parameter ${\tau }^{\ast }$ such that $x^{\ast }$ is a stable critical point of gradient descent-ascent for all $\tau \in ({\tau }^{\ast },\infty )$ if and only if it is a strict local minmax equilibrium. Moreover, we provide an explicit construction for computing ${\tau }^{\ast }$ along with corresponding convergence rates and results under deterministic and stochastic gradient feedback. 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, then there exists a finite timescale separation ${\tau }_0$ such that $x^{\ast }$ is unstable for all $\tau \in ({\tau }_0,\infty )$. Finally, we empirically demonstrate on the CIFAR-10 and CelebA datasets the significant impact timescale separation has on training performance.

References in corpus (13)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Which Training Methods for GANs do actually Converge?
• Unrolled Generative Adversarial Networks
• Certifying Some Distributional Robustness with Principled Adversarial Training
• The Numerics of GANs
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• Convergence of Learning Dynamics in Stackelberg Games
• Differentiable Game Mechanics
• A Closer Look at the Optimization Landscapes of Generative Adversarial Networks
• Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions

Cited by in corpus (4)

• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• On the Convergence and Optimality of Policy Gradient for Markov Coherent Risk
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain