Lower Bounds for Nonconvex-Concave Minimax Optimization
We study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives $f$ that are jointly $L$-smooth in the primal and dual variables $(x,y)$, concave in $y$, and whose primal value function $Φ(x) := \max_{y\in\mathcal Y} f(x,y)$ satisfies the initial-gap condition $Φ(0)-\inf_{x\in\mathcal X}Φ(x)\le Δ_Φ$, with a bounded dual domain satisfying $\operatorname{diam}(\mathcal Y)\le D_{\mathcal Y}$. We measure stationarity by the norm of the gradient of the Moreau envelope of $Φ+ι_{\mathcal X}$ with parameter $1/(2L)$. We prove that…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.14233
curl -X POST /api/v1/records/arxiv/2609.14233/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.14233/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'