Min-Max Optimization Requires Exponentially Many Queries

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 $\epsilon$-approximate stationary point must make a number of queries that is exponential in $1/\epsilon$ or $d$.