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$.
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Optimization and Control (math.OC) |
| Cite as: | arXiv:2605.13806 [cs.DS] |
| (or arXiv:2605.13806v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2605.13806 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Martino Bernasconi [view email]
[v1]
Wed, 13 May 2026 17:34:24 UTC (36 KB)