mlsanityData to 14 Oct 2026

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

arXiv 2112.09579 ↗First posted 17 Dec 2021math.OC cs.GT cs.LGcited by 10

Not on the map. Why?

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.

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

44 of 76 references.

References · 44

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2016Adversarial Machine Learning at Scalecited by 936
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  5. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 206
  6. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
  7. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  8. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  9. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  10. 2017The Numerics of GANscited by 105
  11. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  12. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 95
32 more
  1. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  2. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  3. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  4. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  5. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  6. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 58
  7. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 57
  8. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  9. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 53
  10. 2017Communication-Efficient Algorithms for Decentralized and Stochastic Optimizationcited by 43
  11. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 42
  12. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  13. 2018An Exact Quantized Decentralized Gradient Descent Algorithmcited by 36
  14. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  15. 2018Robust Optimization over Multiple Domainscited by 34
  16. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  17. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
  18. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  19. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  20. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  21. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  22. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  23. 2017The Approximate Duality Gap Technique: A Unified Theory of First-Order Methodscited by 27
  24. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
  25. 2015Saddle-point dynamics: conditions for asymptotic stability of saddle pointscited by 18
  26. 2019Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximationcited by 18
  27. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 17
  28. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  29. 2021Improved Convergence Rate for a Distributed Two-Time-Scale Gradient Method under Random Quantizationcited by 5
  30. 2019Semi-Global Exponential Stability of Augmented Primal-Dual Gradient Dynamics for Constrained Convex Optimizationcited by 4
  31. 2021Convergence Rates of Distributed Consensus over Cluster Networks: A Two-Time-Scale Approachcited by 2
  32. 2021Convergence Rates of Decentralized Gradient Methods over Cluster Networkscited by 1

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 3; 2024: 1; 2025: 3.

10 papers.

  1. 2022Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspectivecited by 13
  2. 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 12
  3. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  4. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  5. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 5
  6. 2025Convergence of two-timescale gradient descent ascent dynamics: finite-dimensional and mean-field perspectivescited by 2
  7. 2025Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Gamescited by 2
  8. 2023An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problemscited by 1
  9. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0
  10. 2023Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Sufficescited by 0