mlsanityData to 7 Oct 2026

Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization

arXiv 2212.12978 ↗First posted 26 Dec 2022math.OC cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

Nonconvex-nonconcave minimax optimization has received intense attention over the last decade due to its broad applications in machine learning. Most existing algorithms rely on one-sided information, such as the convexity (resp. concavity) of the primal (resp. dual) functions, or other specific structures, such as the Polyak-Lojasiewicz (PL) and Kurdyka-Lojasiewicz (KL) conditions. However, verifying these regularity conditions is challenging in practice. To meet this challenge, we propose a novel universally applicable single-loop algorithm, the doubly smoothed gradient descent ascent method (DS-GDA), which naturally balances the primal and dual updates. That is, DS-GDA with the same hyperparameters is able to uniformly solve nonconvex-concave, convex-nonconcave, and nonconvex-nonconcave problems with one-sided KL properties, achieving convergence with O(ε-4) complexity. Sharper (even optimal) iteration complexity can be obtained when the KL exponent is known. Specifically, under the one-sided KL condition with exponent θ∈(0,1), DS-GDA converges with an iteration complexity of O(ε^-2max2θ,1). They all match the corresponding best results in the literature. Moreover, we show that DS-GDA is practically applicable to general nonconvex-nonconcave problems even without any regularity conditions, such as the PL condition, KL condition, or weak Minty variational inequalities condition. For various challenging nonconvex-nonconcave examples in the literature, including ``Forsaken'', ``Bilinearly-coupled minimax'', ``Sixth-order polynomial'', and ``PolarGame'', the proposed DS-GDA can all get rid of limit cycles. To the best of our knowledge, this is the first first-order algorithm to achieve convergence on all of these formidable problems.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 36 of its 62 references that are in the map. First posted on arXiv 26 Dec 2022.

Builds on

36 of 62 references.

References · 36

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2015Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)cited by 1,061
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  6. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  7. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  8. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  9. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  10. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  11. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  12. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
24 more
  1. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  2. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  3. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  4. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  5. 2020The limits of min-max optimization algorithms: convergence to spurious non-critical setscited by 50
  6. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  7. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  8. 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35
  9. 2019On Solving Minimax Optimization Locally: A Follow-the-Ridge Approachcited by 34
  10. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  11. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 33
  12. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  13. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  14. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  15. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  16. 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
  17. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  18. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 19
  19. 2022Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicitycited by 16
  20. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  21. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  22. 2021On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimizationcited by 9
  23. 2022On the Linear Convergence of Extra-Gradient Methods for Nonconvex-Nonconcave Minimax Problemscited by 7
  24. 2022STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Gamescited by 4

Built on by

Cited by year

Citing papers per year: 2024: 6; 2025: 5.

11 papers.

  1. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  2. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  3. 2025Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithmcited by 5
  4. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  5. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 4
  6. 2024Generative Conditional Distributions by Neural (Entropic) Optimal Transportcited by 1
  7. 2025A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz conditioncited by 1
  8. 2025EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimizationcited by 1
  9. 2024ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary pointscited by 0
  10. 2024Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problemscited by 0
  11. 2025A first-order method for constrained nonconvex-nonconcave minimax optimizationcited by 0