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 $\mathrm{\nabla }f$, any algorithm that finds an $\epsilon$-approximate stationary point must make a number of queries that is exponential in $1\mathrm{/}\epsilon$ or $d$.