mlsanityData to 14 Oct 2026

Min-Max Optimization Requires Exponentially Many Queries

arXiv 2605.13806 ↗First posted 13 May 2026cs.DS cs.CC cs.GTcited by 1

Not on the map. Why?

Abstract (arXiv)

We study the query complexity of min-max optimization of a nonconvex-nonconcave function f over [0,1]d × [0,1]d. We show that, given oracle access to f and to its gradient nabla f, any algorithm that finds an varepsilon-approximate stationary point must make a number of queries that is exponential in 1/varepsilon or d.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 25 of its 39 references that are in the map. First posted on arXiv 13 May 2026.

Builds on

25 of 39 references.

References · 25

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  3. 2023Nash Learning from Human Feedbackcited by 224
  4. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  5. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 144
  6. 2017Lower Bounds for Finding Stationary Points Icited by 126
  7. 2017Cycles in adversarial regularized learningcited by 124
  8. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  9. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  10. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  11. 2018Stable Opponent Shaping in Differentiable Gamescited by 49
  12. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
13 more
  1. 2020Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advancescited by 38
  2. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  3. 2014Inapproximability of Nash Equilibriumcited by 17
  4. 2020Newton-type Methods for Minimax Optimizationcited by 11
  5. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  6. 2025Safety Alignment of LMs via Non-cooperative Gamescited by 8
  7. 2022Pure-Circuit: Tight Inapproximability for PPADcited by 7
  8. 2024Improved Hardness Results for Min-Max Optimization with Coupled Constraintscited by 5
  9. 2025A Polynomial-Time Algorithm for Variational Inequalities under the Minty Conditioncited by 3
  10. 2021Subgradient Ellipsoid Method for Nonsmooth Convex Problemscited by 2
  11. 2026The Complexity of Min-Max Optimization with Product Constraintscited by 2
  12. 2022Newton and interior-point methods for (constrained) nonconvex-nonconcave minmax optimization with stability and instability guaranteescited by 1
  13. 2023Beyond first-order methods for non-convex non-concave min-max optimizationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026The Complexity of Min-Max Optimization for Quadratic Polynomialscited by 1