mlsanityData to 14 Oct 2026

Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization

arXiv 2104.08708 ↗First posted 18 Apr 2021math.OC cs.LG stat.MLcited by 36

Not on the map. Why?

Abstract (arXiv)

We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of Omegaleft(√kappaε-2right) for deterministic oracles, where ε defines the level of approximate stationarity and kappa is the condition number. Our analysis shows that the upper bound achieved in (Lin et al., 2020b) is optimal in the ε and kappa dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of Omegaleft(√kappaε-2 + kappa1/3ε-4right). It suggests that there is a significant gap between the upper bound O(kappa3 ε-4) in (Lin et al., 2020a) and our lower bound in the condition number dependence.

Key facts. Cited by 36 papers in the map (data through 14 Oct 2026). Builds on 32 of its 56 references that are in the map. First posted on arXiv 18 Apr 2021.

Builds on

32 of 56 references.

References · 32

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  3. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  4. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  5. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  6. 2017Training GANs with Optimismcited by 217
  7. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  8. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  9. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  10. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  11. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  12. 2017Lower Bounds for Finding Stationary Points Icited by 126
20 more
  1. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  3. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  4. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  5. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  6. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
  7. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  8. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  9. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  10. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 58
  11. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  12. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 45
  13. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  14. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 38
  15. 2019On Solving Minimax Optimization Locally: A Follow-the-Ridge Approachcited by 34
  16. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  17. 2017Stabilizing Adversarial Nets With Prediction Methodscited by 14
  18. 2016On the Iteration Complexity of Oblivious First-Order Optimization Algorithmscited by 9
  19. 2019Accelerated methods for composite non-bilinear saddle point problemcited by 6
  20. 2020Linear Last-iterate Convergence in Constrained Saddle-point Optimizationcited by 5

Built on by

Cited by year (2026 to 14 Oct)

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

36 papers.

Sort:

  1. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 51
  2. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  3. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  4. 2021Universal Approximation Under Constraints is Possible with Transformerscited by 32
  5. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  6. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 16
  7. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  8. 2021AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimizationcited by 13
  9. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  10. 2022On Convergence of Gradient Descent Ascent: A Tight Local Analysiscited by 9
  11. 2021Minimax Optimization with Smooth Algorithmic Adversariescited by 8
  12. 2021Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domaincited by 8
24 more
  1. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 8
  2. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  3. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 7
  4. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  5. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  6. 2021Universal Regular Conditional Distributionscited by 4
  7. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
  8. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  9. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  10. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  11. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 3
  12. 2024Two trust region type algorithms for solving nonconvex-strongly concave minimax problemscited by 2
  13. 2024Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentumcited by 2
  14. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  15. 2024Stochastic Compositional Minimax Optimization with Provable Convergence Guaranteescited by 1
  16. 2026Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimizationcited by 1
  17. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0
  18. 2023First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methodscited by 0
  19. 2025Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexitycited by 0
  20. 2025Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Constructioncited by 0
  21. 2026The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimizationcited by 0
  22. 2026Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimizationcited by 0
  23. 2026Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimizationcited by 0
  24. 2026Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimizationcited by 0