mlsanityData to 7 Oct 2026

A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems

arXiv 2010.15768 ↗First posted 29 Oct 2020math.OC cs.LGcited by 57

Not on the map. Why?

Abstract (arXiv)

Nonconvex-concave min-max problem arises in many machine learning applications including minimizing a pointwise maximum of a set of nonconvex functions and robust adversarial training of neural networks. A popular approach to solve this problem is the gradient descent-ascent (GDA) algorithm which unfortunately can exhibit oscillation in case of nonconvexity. In this paper, we introduce a "smoothing" scheme which can be combined with GDA to stabilize the oscillation and ensure convergence to a stationary solution. We prove that the stabilized GDA algorithm can achieve an O(1/ε2) iteration complexity for minimizing the pointwise maximum of a finite collection of nonconvex functions. Moreover, the smoothed GDA algorithm achieves an O(1/ε4) iteration complexity for general nonconvex-concave problems. Extensions of this stabilized GDA algorithm to multi-block cases are presented. To the best of our knowledge, this is the first algorithm to achieve O(1/ε2) for a class of nonconvex-concave problem. We illustrate the practical efficiency of the stabilized GDA algorithm on robust training.

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 15; 2023: 10; 2024: 13; 2025: 7; 2026: 3.

57 papers.

Sort:

By area:

  1. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 50
  2. 2024Smooth Tchebycheff Scalarization for Multi-Objective Optimizationcited by 50
  3. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  4. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  5. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  6. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  7. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  8. 2022Stability Analysis and Generalization Bounds of Adversarial Trainingcited by 30
  9. 2024Continual Forgetting for Pre-trained Vision Modelscited by 29
  10. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  11. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  12. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
38 more
  1. 2023Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraintscited by 16
  2. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  3. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  4. 2022A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimizationcited by 12
  5. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  6. 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 11
  7. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  8. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 10
  9. 2021Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domaincited by 8
  10. 2023A first-order augmented Lagrangian method for constrained minimax optimizationcited by 8
  11. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  12. 2023Federated Compositional Deep AUC Maximizationcited by 8
  13. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7
  14. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  15. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  16. 2024In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminatescited by 7
  17. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  18. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 6
  19. 2022An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimizationcited by 6
  20. 2023Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimizationcited by 6
  21. 2023Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problemscited by 6
  22. 2025Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraintscited by 5
  23. 2021Low-rank Matrix Recovery With Unknown Correspondencecited by 4
  24. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  25. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  26. 2024Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functionscited by 4
  27. 2025Practical Continual Forgetting for Pre-trained Vision Modelscited by 4
  28. 2021Randomized Stochastic Gradient Descent Ascentcited by 3
  29. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  30. 2021Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimizationcited by 2
  31. 2025Rethinking Data Mixture for Large Language Models: A Comprehensive Survey and New Perspectivescited by 2
  32. 2023An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problemscited by 1
  33. 2024Inverse Design of Photonic Crystal Surface Emitting Lasers is a Sequence Modeling Problemcited by 1
  34. 2025Learning Generalized Hamiltonian Dynamics with Stability from Noisy Trajectory Datacited by 1
  35. 2026Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraintscited by 1
  36. 2026Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularitycited by 1
  37. 2021GDA-AM: On the effectiveness of solving minimax optimization via Anderson Accelerationcited by 0
  38. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0

50 most cited of 57 All 57 (JSON)