Local Convergence Analysis of Gradient Descent Ascent with Finite Timescale Separation
Tanner Fiez, Lillian J. Ratliff · International Conference on Learning Representations · 2021
We study the role that a finite timescale separation parameter τ has on gradient descent-ascent in non-convex, non-concave zero-sum games where the learning rate of player 1 is denoted by γ1 and the learning rate of player 2 is defined to be γ2=τγ1. We show there exists a finite timescale separation parameter τ∗ such that x∗ is a stable critical point of gradient descent-ascent for all τ∈(τ∗,∞) if and only if it is a strict local minmax equilibrium. Moreover, we provide an explicit construction for computing τ∗ along with corresponding convergence rates. The convergence results we present are complemented by a non-convergence result: given a critical point x∗ that is not a strict local minmax equilibrium, there exists a finite timescale separation τ0 such that x∗ is unstable for all τ∈(τ0,∞). 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.