Research
Min-Max Optimization Requires Exponentially Many Queries
arXiv:2605.13806v1 Announce Type: cross Abstract: We study the query complexity of min-max optimization of a nonconvex-nonconcave function f over [0,1]^d imes [0,1]^d. We show that, given oracle acces
arXiv:2605.13806v1 Announce Type: cross Abstract: We study the query complexity of min-max optimization of a nonconvex-nonconcave function f over [0,1]^d imes [0,1]^d. We show that, given oracle access to f and to its gradient nabla f, any algorithm that finds an arepsilon-approximate stationary point must make a number of queries that is exponential in 1/arepsilon or d.
Source: arXiv cs.LG | 2026-05-14