Optimal Deterministic Oracle Complexity for Weakly Convex Optimization
We study the oracle complexity of finding $ε$-stationary points of $ρ$-weakly convex and $G$-Lipschitz functions, where stationarity is measured by the gradient of the Moreau envelope. We consider a first-order oracle that returns both the function value and the full subdifferential at every query point. We prove that every deterministic first-order algorithm requires $ Ω({ρG^2Δ}/{ε^4})$ oracle queries whenever $Δ\leq {G^2}/ρ$, where $f(\bz)-\inf f \leq Δ$. This lower bound matches the best known deterministic and stochastic first-order upper bounds, up to universal constants, and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.03246
curl -X POST /api/v1/records/arxiv/2608.03246/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.03246/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'