{"id":"arxiv/2608.26799","url":"https://arxiv.org/abs/2608.26799","tags":["math.OC"],"score":0,"title":"Lower Bounds for Nonconvex-PŁ Minimax Optimization","domain":"math.OC","source":"arxiv","authors":["Siyu Pan","Jiajin Li"],"reviews":0,"subject":"math.OC","summary":"We study the deterministic first-order oracle complexity of finding stationary points of the value function in smooth nonconvex-Polyak-Łojasiewicz (NC-PŁ) minimax optimization. We assume that the objective is jointly $\\ell$-smooth and satisfies the $μ$-PŁ condition in the dual variable, and that its value function $Φ(x):=\\max_y f(x;y)$ satisfies $Φ(0)-\\inf_xΦ(x)\\leqΔ$. When $κ:=\\ell/μ\\gtrsim 1$ and $0<ε^2\\lesssim\\ellΔ$, we prove that every deterministic first-order method requires $Ω(\\ellΔκ/ε^2)$ oracle queries in the worst case to find $x$ satisfying $\\|\\nablaΦ(x)\\|\\leqε$. This rate matches…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}