arxiv: 2605.13806 · v1 · submitted 2026-05-13 · 💻 cs.DS · cs.CC· cs.GT· cs.LG· math.OC

Recognition: 2 theorem links

· Lean Theorem

Min-Max Optimization Requires Exponentially Many Queries

Alexandros Hollender, Andrea Celli, Martino Bernasconi, Matteo Castiglioni

Authors on Pith no claims yet

Pith reviewed 2026-05-14 17:27 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.GTcs.LGmath.OC

keywords min-max optimizationquery complexitynonconvex-nonconcave functionsstationary pointslower boundsoracle complexity

0 comments

The pith

Any algorithm finding an ε-approximate stationary point in nonconvex-nonconcave min-max optimization requires exponentially many queries.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that solving min-max optimization for nonconvex-nonconcave functions over the unit hypercube demands an exponential number of queries to the function and gradient oracles. This holds for finding any ε-approximate stationary point, with the query count growing exponentially in 1/ε or in the dimension d. A reader would care because it shows that general min-max problems cannot be solved efficiently by querying f and ∇f alone, unlike convex cases. This forces a rethinking of algorithmic approaches for saddle-point problems in machine learning and game theory.

Core claim

In the oracle model where an algorithm has access to the value of f and its gradient ∇f, for any nonconvex-nonconcave f : [0,1]^{2d} → R, computing an ε-stationary point requires a number of queries exponential in 1/ε or d.

What carries the argument

A lower-bound construction consisting of nonconvex-nonconcave functions whose approximate stationary points are hidden in one of exponentially many local regions, forcing any querying algorithm to check most of them.

If this is right

No polynomial-query algorithm exists for general nonconvex-nonconcave min-max optimization.
The exponential dependence holds for both accuracy ε and dimension d.
The result applies specifically to exact oracle access to f and ∇f.
It implies hardness for finding approximate equilibria in certain continuous games.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Algorithms in practice must rely on additional function properties such as smoothness or partial convexity to succeed with fewer queries.
The bound may not hold if the oracle returns noisy estimates or if the function class is narrowed.
This hardness result connects to the challenge of training generative adversarial networks without structural assumptions.

Load-bearing premise

The function is an arbitrary nonconvex-nonconcave function and the algorithm receives exact f and gradient values at each query point.

What would settle it

Provide a nonconvex-nonconcave function together with a deterministic algorithm that locates an ε-approximate stationary point using only a polynomial number of queries in 1/ε and d.

Figures

Figures reproduced from arXiv: 2605.13806 by Alexandros Hollender, Andrea Celli, Martino Bernasconi, Matteo Castiglioni.

read the original abstract

We study the query complexity of min-max optimization of a nonconvex-nonconcave function $f$ over $[0,1]^d \times [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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a clean exponential lower bound on first-order queries needed for ε-stationary points in nonconvex-nonconcave min-max over the unit cube.

read the letter

The punchline is that any algorithm using first-order oracles needs an exponential number of queries in 1/ε or d to find an ε-stationary point for nonconvex-nonconcave min-max over [0,1]^d x [0,1]^d. This result is new in its focus on the nonconvex-nonconcave regime with exact gradient oracles. Earlier lower bounds often cover convex cases or different notions of optimality, so this one adds a specific constraint for the general setting. The paper does well by using a reduction or adversary construction that forces the algorithm to explore many potential stationary points, which aligns with how these problems can have complex landscapes. The argument appears solid based on the information available. It establishes the bound without relying on fitted parameters or circular definitions, which is good for a query complexity result. Soft spots are limited. The exponential dependence might be on the maximum of 1/ε and d, but the abstract says exponential in 1/ε or d, which is clear. One minor point is that the functions need to be verified as nonconvex-nonconcave, but assuming the construction works, it's fine. The result is for deterministic exact oracles, so it doesn't speak directly to noisy settings. This is useful for researchers studying the fundamental limits of optimization algorithms in min-max problems. It would be of interest to those designing or analyzing methods for GANs or other nonconvex games. A reader looking for theoretical barriers will find it relevant. I think it deserves peer review. The core claim is well-motivated and the approach is standard for the field, so it should get a fair look from referees.

Referee Report

0 major / 4 minor

Summary. The paper proves an information-theoretic lower bound for min-max optimization: any algorithm with oracle access to a nonconvex-nonconcave function f and its gradient ∇f over the domain [0,1]^d × [0,1]^d must make exponentially many queries (in 1/ε or in d) to find an ε-approximate stationary point.

Significance. If the result holds, it establishes a fundamental query-complexity barrier for first-order methods in the nonconvex-nonconcave regime, sharply separating it from the convex-concave case where polynomial-time algorithms exist. The information-theoretic argument via adversary construction is a clear strength and supplies a clean, falsifiable prediction about the number of queries required.

minor comments (4)

[Abstract] Abstract: the phrase 'exponential in 1/ε or d' is ambiguous; state explicitly whether the bound is Ω(exp(c/ε)) for some c>0, Ω(exp(c d)), or the maximum of the two.
[§2] §2 (Preliminaries): the precise definition of ε-approximate stationary point (e.g., whether it uses the gradient norm of the min-max or a different notion) should be stated before the lower-bound theorem.
Figure 1 (if present) or the hard-instance diagram: labels for the hidden parameter and the regions where gradients are uninformative would improve readability.
[Related Work] Related-work section: add a brief comparison to existing lower bounds for nonconvex minimization (e.g., Carmon et al.) to clarify the new technical contribution of the min-max adversary.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the information-theoretic lower bound, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in information-theoretic lower bound

full rationale

The paper establishes an exponential query lower bound for finding ε-approximate stationary points of nonconvex-nonconcave functions via a standard adversary/reduction argument over a carefully constructed function family. This is self-contained: the hardness follows directly from the oracle model (exact access to f and ∇f) and the requirement to distinguish stationary points, without any fitted parameters, self-definitional loops, or load-bearing self-citations that reduce the claim to its own inputs. The derivation does not rename known results or smuggle ansatzes; it is a direct information-theoretic argument.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard query-complexity assumptions and the definition of ε-stationary points; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption The function is defined over the compact domain [0,1]^d × [0,1]^d and admits a well-defined gradient oracle.
Required for the stationary-point notion and oracle access model stated in the abstract.

pith-pipeline@v0.9.0 · 5375 in / 1168 out tokens · 60075 ms · 2026-05-14T17:27:58.368989+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear
We show that, given oracle access to f and to its gradient ∇f, any algorithm that finds an ε-approximate stationary point must make a number of queries that is exponential in 1/ε or d.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
Theorem 5.1. There is a reduction from an instance of OraclePureCircuit... to SmoothBrouwer

Reference graph

Works this paper leans on

6 extracted references · 4 canonical work pages

[1]

An O(nlogn )sortingnetwork

[AKS83] MiklósAjtai,JánosKomlós,andEndreSzemerédi.“An O(nlogn )sortingnetwork”.In:Proceedings of the fifteenth annual ACM symposium on Theory of computing. 1983, pp. 1–9. [Ana+25] Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm, and Brian Hu Zhang. “A polynomial- time algorithm for variational inequalities under the Minty condition”. In:arXiv prepr...

work page arXiv 1983
[2]

On the Role of Constraints in the Complexity of Min-Max Optimization

[Ber+24] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Gabriele Farina. “On the Role of Constraints in the Complexity of Min-Max Optimization”. In:arXiv preprint arXiv:2411.03248 (2024). [Car+20] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. “Lower bounds for finding stationary points I”. In:Mathematical Programming184.1 (2020),...

work page arXiv 2024
[3]

Pure- Circuit: Tight Inapproximability for PPAD

[Del+24] Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. “Pure- Circuit: Tight Inapproximability for PPAD”. In:Journal of the ACM71.5 (2024), 31:1–31:48. [Dia25] Jelena Diakonikolas. “Open Problems in Optimization”. In:SIAG on Optimization Views and News33.1 (2025), pp. 1–12.url: https://siagoptimization.github.io/as...

work page arXiv 2024
[4]

Playing large games using simple strategies

[LMM03] Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. “Playing large games using simple strategies”. In:Proceedings of the 4th ACM Conference on Electronic Commerce. 2003, pp. 36–41. [Mad+18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. “Towards Deep Learning Models Resistant to Adversarial Attacks”....

2003
[5]

Cycles in adversarial regularized learning

[MPP18] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. “Cycles in adversarial regularized learning”. In:Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms. SIAM. 2018, pp. 2703–2717. [Mun+24] Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Y...

2018
[6]

Solving a class of non-convex min-max games using iterative first order methods

[Nou+19] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. “Solving a class of non-convex min-max games using iterative first order methods”. In:Advances in Neural Information Processing Systems32 (2019). [OLR21] Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. “Efficient search of first-order Nash equilibria in ...

work page arXiv 2019