mlsanityData to 14 Oct 2026

The Complexity of Nonconvex-Strongly-Concave Minimax Optimization

arXiv 2103.15888 ↗First posted 29 Mar 2021math.OC cs.LG stat.MLcited by 45

Not on the map. Why?

Abstract (arXiv)

This paper studies the complexity for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) smooth minimax problems, in both general and averaged smooth finite-sum settings. We establish nontrivial lower complexity bounds of Omega(√kappaDelta Lε-2) and Omega(n+√nkappaDelta Lε-2) for the two settings, respectively, where kappa is the condition number, L is the smoothness constant, and Delta is the initial gap. Our result reveals substantial gaps between these limits and best-known upper bounds in the literature. To close these gaps, we introduce a generic acceleration scheme that deploys existing gradient-based methods to solve a sequence of crafted strongly-convex-strongly-concave subproblems. In the general setting, the complexity of our proposed algorithm nearly matches the lower bound; in particular, it removes an additional poly-logarithmic dependence on accuracy present in previous works. In the averaged smooth finite-sum setting, our proposed algorithm improves over previous algorithms by providing a nearly-tight dependence on the condition number.

Key facts. Cited by 45 papers in the map (data through 14 Oct 2026). Builds on 47 of its 78 references that are in the map. First posted on arXiv 29 Mar 2021.

Builds on

47 of 78 references.

References · 47

  1. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 337
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  7. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  8. 2017Lower Bounds for Finding Stationary Points Icited by 126
  9. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  10. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  11. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  12. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
35 more
  1. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  2. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
  3. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  4. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  5. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
  6. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  7. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  8. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  9. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 58
  10. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 58
  11. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  12. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 57
  13. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  14. 2018On the Convergence and Robustness of Training GANs with Regularized Optimal Transportcited by 51
  15. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  16. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  17. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  18. 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
  19. 2019Variance Reduction for Matrix Gamescited by 38
  20. 2018Robust Optimization over Multiple Domainscited by 34
  21. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
  22. 2020Recent Theoretical Advances in Non-Convex Optimizationcited by 30
  23. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  24. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  25. 2020Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problemscited by 26
  26. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  27. 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
  28. 2019Lower Bounds for Smooth Nonconvex Finite-Sum Optimizationcited by 20
  29. 2014Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theorycited by 17
  30. 2019SGD Learns One-Layer Networks in WGANscited by 16
  31. 2014A Lower Bound for the Optimization of Finite Sumscited by 13
  32. 2020Gradient Free Minimax Optimization: Variance Reduction and Faster Convergencecited by 11
  33. 2018Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexitycited by 7
  34. 2019A Stochastic Proximal Point Algorithm for Saddle-Point Problemscited by 6
  35. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 16; 2023: 6; 2024: 7; 2025: 3; 2026: 4.

45 papers.

Sort:

  1. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  2. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  3. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  4. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  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. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  9. 2021AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimizationcited by 13
  10. 2022Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimizationcited by 13
  11. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  12. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
33 more
  1. 2022Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximizationcited by 11
  2. 2022Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problemscited by 11
  3. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  4. 2022On Convergence of Gradient Descent Ascent: A Tight Local Analysiscited by 9
  5. 2021Minimax Optimization with Smooth Algorithmic Adversariescited by 8
  6. 2021Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domaincited by 8
  7. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 8
  8. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  9. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8
  10. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7
  11. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 7
  12. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  13. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  14. 2022An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimizationcited by 6
  15. 2023Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problemscited by 6
  16. 2021Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learningcited by 4
  17. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4
  18. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  19. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  20. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  21. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  22. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 3
  23. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  24. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  25. 2024Stochastic Compositional Minimax Optimization with Provable Convergence Guaranteescited by 1
  26. 2026Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimizationcited by 1
  27. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0
  28. 2023First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methodscited by 0
  29. 2024Completely Parameter-Free Single-Loop Algorithms for Nonconvex-Concave Minimax Problemscited by 0
  30. 2024Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problemscited by 0
  31. 2026Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimizationcited by 0
  32. 2026Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimizationcited by 0
  33. 2026Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimizationcited by 0