Min-Max Optimization Requires Exponentially Many Queries
arXiv:2605.1380635.5
Predicted impact top 37% in DS · last 90 daysOriginality Highly original
AI Analysis
This provides a hardness result for the query complexity of min-max optimization, showing that the problem is intractable even with gradient access.
The paper proves that any algorithm for min-max optimization of a nonconvex-nonconcave function requires exponentially many queries (in 1/ε or d) to find an ε-approximate stationary point, establishing a fundamental lower bound.
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$.