# Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 76 references that are in the map.
- First posted on arXiv 17 Dec 2021.

## Builds on (most cited first, 30 of 44)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games](https://mlsanity.com/paper/1906.00729/) (2019)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [Robust Optimization over Multiple Domains](https://mlsanity.com/paper/1805.07588/) (2018)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [Stochastic Hamiltonian Gradient Methods for Smooth Games](https://mlsanity.com/paper/2007.04202/) (2020)

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

- [Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective](https://mlsanity.com/paper/2212.08791/) (2022)
- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [Worst-case generation via minimax optimization in Wasserstein space](https://mlsanity.com/paper/2512.08176/) (2025)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Convergence of two-timescale gradient descent ascent dynamics: finite-dimensional and mean-field perspectives](https://mlsanity.com/paper/2501.17122/) (2025)
- [Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games](https://mlsanity.com/paper/2505.07642/) (2025)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Iterative Minimax Games with Coupled Linear Constraints](https://mlsanity.com/paper/2212.04672/) (2022)
- [Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices](https://mlsanity.com/paper/2305.17275/) (2023)

## Abstract (arXiv)

There are much recent interests in solving noncovnex min-max optimization problems due to its broad applications in many areas including machine learning, networked resource allocations, and distributed optimization. Perhaps, the most popular first-order method in solving min-max optimization is the so-called simultaneous (or single-loop) gradient descent-ascent algorithm due to its simplicity in implementation. However, theoretical guarantees on the convergence of this algorithm is very sparse since it can diverge even in a simple bilinear problem. In this paper, our focus is to characterize the finite-time performance (or convergence rates) of the continuous-time variant of simultaneous gradient descent-ascent algorithm. In particular, we derive the rates of convergence of this method under a number of different conditions on the underlying objective function, namely, two-sided Polyak-L ojasiewicz (PL), one-sided PL, nonconvex-strongly concave, and strongly convex-nonconcave conditions. Our convergence results improve the ones in prior works under the same conditions of objective functions. The key idea in our analysis is to use the classic singular perturbation theory and coupling Lyapunov functions to address the time-scale difference and interactions between the gradient descent and ascent dynamics. Our results on the behavior of continuous-time algorithm may be used to enhance the convergence properties of its discrete-time counterpart.