{"id":"arxiv/2605.13806","url":"https://arxiv.org/abs/2605.13806","tags":["cs.DS","cs.CC","cs.GT","cs.LG","math.OC"],"score":0,"title":"Min-Max Optimization Requires Exponentially Many Queries","domain":"cs.DS","source":"arxiv","authors":["Martino Bernasconi","Matteo Castiglioni","Andrea Celli","Alexandros Hollender"],"reviews":0,"subject":"cs.DS","summary":"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$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-13","reactions":{}}