mlsanityData to 7 Oct 2026

On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

arXiv 1906.00331 ↗First posted 2 Jun 2019cs.LG math.OC stat.MLcited by 266

Not on the map. Why?

Abstract (arXiv)

We consider nonconvex-concave minimax problems, minx maxy ∈ Y f(x, y), where f is nonconvex in x but concave in y and Y is a convex and bounded set. One of the most popular algorithms for solving this problem is the celebrated gradient descent ascent (GDA) algorithm, which has been widely used in machine learning, control theory and economics. Despite the extensive convergence results for the convex-concave setting, GDA with equal stepsize can converge to limit cycles or even diverge in a general setting. In this paper, we present the complexity results on two-time-scale GDA for solving nonconvex-concave minimax problems, showing that the algorithm can find a stationary point of the function Phi(·) := maxy ∈ Y f(·, y) efficiently. To the best our knowledge, this is the first nonasymptotic analysis for two-time-scale GDA in this setting, shedding light on its superior practical performance in training generative adversarial networks (GANs) and other real applications.

Key facts. Cited by 266 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 46; 2022: 73; 2023: 53; 2024: 38; 2025: 33; 2026: 23.

266 papers.

Sort:

By area:

  1. 2021Distributionally Robust Federated Averagingcited by 104
  2. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  3. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  4. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  5. 2021Sig-Wasserstein GANs for Time Series Generationcited by 60
  6. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  7. 2024Smooth Tchebycheff Scalarization for Multi-Objective Optimizationcited by 50
  8. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  9. 2021Safe Reinforcement Learning Using Advantage-Based Interventioncited by 45
  10. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  11. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  12. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
38 more
  1. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  2. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  3. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  4. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  5. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  6. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 34
  7. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  8. 2021Direct Behavior Specification via Constrained Reinforcement Learningcited by 30
  9. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
  10. 2021A Stochastic Optimization Framework for Fair Risk Minimizationcited by 26
  11. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  12. 2022Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraintscited by 25
  13. 2022Fast Adversarial Training with Adaptive Step Sizecited by 24
  14. 2022Differentially Private SGDA for Minimax Problemscited by 23
  15. 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
  16. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  17. 2022Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergencecited by 21
  18. 2022What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?cited by 21
  19. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  20. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 19
  21. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  22. 2021Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometrycited by 17
  23. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  24. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  25. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  26. 2022Minimax AUC Fairness: Efficient Algorithm with Provable Convergencecited by 16
  27. 2022Stochastic Differentially Private and Fair Learningcited by 16
  28. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  29. 2021Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexitycited by 15
  30. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  31. 2023Reliable Off-Policy Learning for Dosage Combinationscited by 15
  32. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  33. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  34. 2022Robust Constrained Reinforcement Learningcited by 14
  35. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  36. 2022Distributed Distributionally Robust Optimization with Non-Convex Objectivescited by 14
  37. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  38. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13

50 most cited of 266 All 266 (JSON)