mlsanityData to 7 Oct 2026

A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems

arXiv 2006.02032 ↗First posted 3 Jun 2020math.OC cs.LGcited by 56

Not on the map. Why?

Abstract (arXiv)

Much recent research effort has been directed to the development of efficient algorithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and dual variables alternatively at each iteration. We show that it can find an varepsilon-stationary point of the objective function in Oleft( varepsilon -2 right) (resp. Oleft( varepsilon -4 right)) iterations under nonconvex-strongly concave (resp. nonconvex-concave) setting. Moreover, its gradient complexity to obtain an varepsilon-stationary point of the objective function is bounded by Oleft( varepsilon -2 right) (resp., Oleft( varepsilon -4 right)) under the strongly convex-nonconcave (resp., convex-nonconcave) setting. To the best of our knowledge, this is the first time that a simple and unified single-loop algorithm is developed for solving both nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. Moreover, the complexity results for solving the latter (strongly) convex-nonconcave minimax problems have never been obtained before in the literature. Numerical results show the efficiency of the proposed AGP algorithm. Furthermore, we extend the AGP algorithm by presenting a block alternating proximal gradient (BAPG) algorithm for solving more general multi-block nonsmooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. We can similarly establish the gradient complexity of the proposed algorithm under these four different settings.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 10; 2023: 10; 2024: 12; 2025: 8; 2026: 4.

56 papers.

Sort:

  1. 2024Smooth Tchebycheff Scalarization for Multi-Objective Optimizationcited by 50
  2. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  3. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  4. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  5. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  6. 2021Training Fair Models in Federated Learning without Data Privacy Infringementcited by 26
  7. 2021Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometrycited by 17
  8. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  9. 2022Robust Constrained Reinforcement Learningcited by 14
  10. 2022Distributed Distributionally Robust Optimization with Non-Convex Objectivescited by 14
  11. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  12. 2022Asynchronous Distributed Bilevel Optimizationcited by 13
38 more
  1. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  2. 2024Tri-Level Navigator: LLM-Empowered Tri-Level Learning for Time Series OOD Generalizationcited by 12
  3. 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 11
  4. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  5. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 10
  6. 2021Achieving Model Fairness in Vertical Federated Learningcited by 8
  7. 2023A first-order augmented Lagrangian method for constrained minimax optimizationcited by 8
  8. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  9. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7
  10. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  11. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  12. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 6
  13. 2022An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimizationcited by 6
  14. 2023Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problemscited by 6
  15. 2023Distributed Personalized Empirical Risk Minimizationcited by 6
  16. 2023Provably Convergent Federated Trilevel Learningcited by 6
  17. 2021A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimizationcited by 5
  18. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  19. 2021Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learningcited by 4
  20. 2023Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysiscited by 4
  21. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  22. 2024Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimizationcited by 3
  23. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  24. 2024Unlocking TriLevel Learning with Level-Wise Zeroth Order Constraints: Distributed Algorithms and Provable Non-Asymptotic Convergencecited by 3
  25. 2023Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problemscited by 2
  26. 2024Two trust region type algorithms for solving nonconvex-strongly concave minimax problemscited by 2
  27. 2024Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimizationcited by 2
  28. 2025Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Networkcited by 2
  29. 2023Decentralized Entropic Optimal Transport for Distributed Distribution Comparisoncited by 1
  30. 2023Mixture Weight Estimation and Model Prediction in Multi-source Multi-target Domain Adaptationcited by 1
  31. 2023An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problemscited by 1
  32. 2025A stochastic smoothing framework for nonconvex-nonconcave minEmax problems with applications to Wasserstein distributionally robust optimizationcited by 1
  33. 2025Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1
  34. 2025Enhancing Stability of Physics-Informed Neural Network Training Through Saddle-Point Reformulationcited by 1
  35. 2025EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimizationcited by 1
  36. 2021GDA-AM: On the effectiveness of solving minimax optimization via Anderson Accelerationcited by 0
  37. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0
  38. 2024Completely Parameter-Free Single-Loop Algorithms for Nonconvex-Concave Minimax Problemscited by 0

50 most cited of 56 All 56 (JSON)