Lower Bounds for Nonconvex-PŁ Minimax Optimization
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.26799
curl -X POST /api/v1/records/arxiv/2608.26799/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.26799/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'