Min-Max Optimization Requires Exponentially Many Queries
Min-max optimization of nonconvex-nonconcave functions over hypercubes requires exponentially many queries to find an epsilon-approximate stationary point, under standard oracle assumptions.
Excerpt
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$.
Read at source: https://arxiv.org/abs/2605.13806v1