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

Code

• github.com/fiezt/Finite-Learning-Ratio
  OfficialIn paperpytorch★ 2

Abstract

We study the role that a finite timescale separation parameter 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 _1 and the learning rate of player 2 is defined to be _2=_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 ( =1) and the maximizing player approximately converging between each update of the minimizing player ( ). For the parameter choice of =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 . In this work, we bridge the gap between past work by showing 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 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^ that is not a strict local minmax equilibrium, then there exists a finite timescale separation _0 such that x^ is unstable for all (_0, ). Finally, we empirically demonstrate on the CIFAR-10 and CelebA datasets the significant impact timescale separation has on training performance.

Reproductions