Min-Max Optimization Requires Exponentially Many Queries

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$. --- Source: arXiv:2605.13806v1 - http://arxiv.org/abs/2605.13806v1 PDF: https://arxiv.org/pdf/2605.13806v1 Original Link: http://arxiv.org/abs/2605.13806v1...