# Min-Max Optimization Requires Exponentially Many Queries

arXiv: https://arxiv.org/abs/2605.13806 · HTML: https://mlsanity.com/paper/2605.13806/

## Key facts

- Cited by 1 papers 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 (most cited first, 25 of 25)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Minimaximalist Approach to Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2401.04056/) (2024)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Stable Opponent Shaping in Differentiable Games](https://mlsanity.com/paper/1811.08469/) (2018)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://mlsanity.com/paper/2006.08141/) (2020)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [Newton-type Methods for Minimax Optimization](https://mlsanity.com/paper/2006.14592/) (2020)
- [COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences](https://mlsanity.com/paper/2410.23223/) (2024)
- [Safety Alignment of LMs via Non-cooperative Games](https://mlsanity.com/paper/2512.20806/) (2025)
- [Pure-Circuit: Tight Inapproximability for PPAD](https://mlsanity.com/paper/2209.15149/) (2022)
- [Improved Hardness Results for Min-Max Optimization with Coupled Constraints](https://mlsanity.com/paper/2411.03248/) (2024)
- [A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition](https://mlsanity.com/paper/2504.03432/) (2025)
- [Subgradient Ellipsoid Method for Nonsmooth Convex Problems](https://mlsanity.com/paper/2106.13340/) (2021)
- [The Complexity of Min-Max Optimization with Product Constraints](https://mlsanity.com/paper/2602.04665/) (2026)
- [Newton and interior-point methods for (constrained) nonconvex-nonconcave minmax optimization with stability and instability guarantees](https://mlsanity.com/paper/2205.08038/) (2022)
- [Beyond first-order methods for non-convex non-concave min-max optimization](https://mlsanity.com/paper/2304.08389/) (2023)

## Built on by (most cited first, 1 of 1)

- [The Complexity of Min-Max Optimization for Quadratic Polynomials](https://mlsanity.com/paper/2606.17000/) (2026)

## 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.