mlsanityData to 14 Oct 2026

Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems

arXiv 2211.13668 ↗First posted 24 Nov 2022math.OC cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider a class of nonconvex-nonconcave minimax problems, i.e., NC-PL minimax problems, whose objective functions satisfy the Polyak-L ojasiewicz (PL) condition with respect to the inner variable. We propose a zeroth-order alternating gradient descent ascent (ZO-AGDA) algorithm and a zeroth-order variance reduced alternating gradient descent ascent (ZO-VRAGDA) algorithm for solving NC-PL minimax problem under the deterministic and the stochastic setting, respectively. The total number of function value queries to obtain an ε-stationary point of ZO-AGDA and ZO-VRAGDA algorithm for solving NC-PL minimax problem is upper bounded by O(varepsilon-2) and O(varepsilon-3), respectively. To the best of our knowledge, they are the first two zeroth-order algorithms with the iteration complexity gurantee for solving NC-PL minimax problems.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 41 of its 61 references that are in the map. First posted on arXiv 24 Nov 2022.

Builds on

41 of 61 references.

References · 41

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Generative Adversarial Imitation Learningcited by 1,597
  3. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  4. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  5. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  6. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  7. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  8. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  9. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  10. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
  11. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  12. 2017Training GANs with Optimismcited by 217
29 more
  1. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  2. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  3. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  4. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  5. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  6. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  7. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  8. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  9. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  10. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  11. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  12. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 58
  13. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 57
  14. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  15. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  16. 2019Scaleable input gradient regularization for adversarial robustnesscited by 47
  17. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  18. 2019Differentiable Game Mechanicscited by 43
  19. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  20. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 38
  21. 2018Bandit learning in concave N-person gamescited by 35
  22. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  23. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 21
  24. 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20
  25. 2018Inexact SARAH Algorithm for Stochastic Optimizationcited by 12
  26. 2018SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithmscited by 11
  27. 2020Gradient Free Minimax Optimization: Variance Reduction and Faster Convergencecited by 11
  28. 2017Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parametercited by 8
  29. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7

Built on by

Cited by year (2026 to 14 Oct)

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

11 papers.

  1. 2023Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimizationcited by 6
  2. 2025Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithmcited by 5
  3. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  4. 2024Two trust region type algorithms for solving nonconvex-strongly concave minimax problemscited by 2
  5. 2023An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problemscited by 1
  6. 2024Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimizationcited by 1
  7. 2025A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz conditioncited by 1
  8. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0
  9. 2024Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problemscited by 0
  10. 2025A first-order method for constrained nonconvex-nonconcave minimax optimizationcited by 0
  11. 2026Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problemscited by 0