Sharp First-Order Lower Bounds under $α$-Polyak-Lojasiewicz Conditions
We study first-order oracle complexity under the $α$-Polyak-Lojasiewicz condition $f(x)-f_\star\leq τ\|\nabla f(x)\|^α$ for $α\in[1,2]$. For $α<2$, we first show that global $L$-smoothness together with a global $α$-Polyak-Lojasiewicz inequality forces the objective to be constant. This motivates a nontrivial model in which smoothness remains global but the inequality is required only on the initial sublevel set. On this class, we establish sharp minimax lower bounds for every $α\in[1,2)$. Deterministic first-order methods require $Ω(Lτ^{2/α}\varepsilon^{-(2-α)/α})$ oracle calls, matching…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.28278
curl -X POST /api/v1/records/arxiv/2606.28278/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.28278/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'