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

arXiv: https://arxiv.org/abs/2009.14820 · HTML: https://mlsanity.com/paper/2009.14820/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2020.

## Built on by (most cited first, 10 of 10)

- [Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems](https://mlsanity.com/paper/2302.09831/) (2023)
- [On the Convergence and Optimality of Policy Gradient for Markov Coherent Risk](https://mlsanity.com/paper/2103.02827/) (2021)
- [Closed-Loop Data Transcription to an LDR via Minimaxing Rate Reduction](https://mlsanity.com/paper/2111.06636/) (2021)
- [Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity](https://mlsanity.com/paper/2101.01041/) (2021)
- [Accelerating Inexact HyperGradient Descent for Bilevel Optimization](https://mlsanity.com/paper/2307.00126/) (2023)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Reward-Free Policy Space Compression for Reinforcement Learning](https://mlsanity.com/paper/2202.11079/) (2022)
- [Dissecting adaptive methods in GANs](https://mlsanity.com/paper/2210.04319/) (2022)
- [On the Nash equilibrium of moment-matching GANs for stationary Gaussian processes](https://mlsanity.com/paper/2203.07136/) (2022)
- [Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems](https://mlsanity.com/paper/2207.12845/) (2022)

## Abstract (arXiv)

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 (τ rightarrow ∞). 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 τrightarrow∞. In this work, we bridge the gap between past work by showing there exists a finite timescale separation parameter τast such that xast is a stable critical point of gradient descent-ascent for all τ ∈ (τast, ∞) if and only if it is a strict local minmax equilibrium. Moreover, we provide an explicit construction for computing τ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 xast that is not a strict local minmax equilibrium, then there exists a finite timescale separation τ0 such that xast 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.