mlsanityData to 14 Oct 2026

Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity

arXiv 2112.05604 ↗First posted 10 Dec 2021cs.LG math.OC stat.MLcited by 49

Not on the map. Why?

Abstract (arXiv)

Gradient descent ascent (GDA), the simplest single-loop algorithm for nonconvex minimax optimization, is widely used in practical applications such as generative adversarial networks (GANs) and adversarial training. Albeit its desirable simplicity, recent work shows inferior convergence rates of GDA in theory even assuming strong concavity of the objective on one side. This paper establishes new convergence results for two alternative single-loop algorithms -- alternating GDA and smoothed GDA -- under the mild assumption that the objective satisfies the Polyak-Lojasiewicz (PL) condition about one variable. We prove that, to find an ε-stationary point, (i) alternating GDA and its stochastic variant (without mini batch) respectively require O(kappa2 ε-2) and O(kappa4 ε-4) iterations, while (ii) smoothed GDA and its stochastic variant (without mini batch) respectively require O(kappa ε-2) and O(kappa2 ε-4) iterations. The latter greatly improves over the vanilla GDA and gives the hitherto best known complexity results among single-loop algorithms under similar settings. We further showcase the empirical efficiency of these algorithms in training GANs and robust nonlinear regression.

Key facts. Cited by 49 papers in the map (data through 14 Oct 2026). Builds on 54 of its 92 references that are in the map. First posted on arXiv 10 Dec 2021.

Builds on

54 of 92 references.

References · 54

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  4. 2018Which Training Methods for GANs do actually Converge?cited by 679
  5. 2017Deep Neural Networks as Gaussian Processescited by 622
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  7. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  8. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  9. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  10. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  11. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  12. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
38 more
  1. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  2. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  3. 2017Lower Bounds for Finding Stationary Points Icited by 126
  4. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  5. 2017The Numerics of GANscited by 105
  6. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  7. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  8. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  9. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  10. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  11. 2017Gradient descent GAN optimization is locally stablecited by 67
  12. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  13. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  14. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 58
  15. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 57
  16. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  17. 2020The limits of min-max optimization algorithms: convergence to spurious non-critical setscited by 50
  18. 2018On Gradient-Based Learning in Continuous Gamescited by 48
  19. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 45
  20. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  21. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  22. 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
  23. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  24. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 34
  25. 2019On Solving Minimax Optimization Locally: A Follow-the-Ridge Approachcited by 34
  26. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  27. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  28. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  29. 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
  30. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  31. 2020Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problemscited by 26
  32. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 24
  33. 2014On the Characterization of Local Nash Equilibria in Continuous Gamescited by 22
  34. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 21
  35. 2020Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Conditioncited by 19
  36. 2019SGD Learns One-Layer Networks in WGANscited by 16
  37. 2020On the Impossibility of Global Convergence in Multi-Loss Optimizationcited by 16
  38. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 16

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 13; 2023: 12; 2024: 11; 2025: 8; 2026: 5.

49 papers.

Sort:

By area:

  1. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  2. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 51
  3. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  4. 2023Robust Generalization against Photon-Limited Corruptions via Worst-Case Sharpness Minimizationcited by 29
  5. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  6. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  7. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 16
  8. 2022Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspectivecited by 13
  9. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  10. 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 12
  11. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 11
  12. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
37 more
  1. 2024Learning with Logical Constraints but without Shortcut Satisfactioncited by 10
  2. 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 8
  3. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  4. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 8
  5. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  6. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 7
  7. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  8. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  9. 2023Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimizationcited by 6
  10. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 5
  11. 2024Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oraclescited by 5
  12. 2023Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problemscited by 4
  13. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  14. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  15. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  16. 2024Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functionscited by 4
  17. 2024A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processescited by 4
  18. 2026Generative models for decision-making under distributional shiftcited by 4
  19. 2025Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Gamescited by 3
  20. 2023Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problemscited by 2
  21. 2023Zero-Shot Sharpness-Aware Quantization for Pre-trained Language Modelscited by 2
  22. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  23. 2024Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentumcited by 2
  24. 2025Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Gamescited by 2
  25. 2025Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimizationcited by 2
  26. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 2
  27. 2023An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problemscited by 1
  28. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  29. 2024Stochastic Compositional Minimax Optimization with Provable Convergence Guaranteescited by 1
  30. 2025A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz conditioncited by 1
  31. 2026Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraintscited by 1
  32. 2026Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimizationcited by 1
  33. 2024Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Stepscited by 0
  34. 2025Diffusion Stochastic Learning Over Adaptive Competing Networkscited by 0
  35. 2025A first-order method for constrained nonconvex-nonconcave minimax optimizationcited by 0
  36. 2026Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimizationcited by 0
  37. 2026Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimizationcited by 0