Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under $(L_0,L_1)$-Smoothness
For convex $(L_0,L_1)$-smooth functions, the curvature may grow together with the gradient norm. Therefore, even when $\|x^0-x^*\|\le R$, the gradient and the optimality gap at the starting point may be exponentially large in $L_1R$, and the bound $\sqrt{L_0R^2/\varepsilon}$, known for the accelerated method on functions with Lipschitz gradient, no longer describes the complexity of the problem. We determine the oracle complexity of this class for arbitrary deterministic first-order methods: for $L_0R^2/\varepsilon\ge1$, the optimal number of oracle calls $N$ satisfies…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.21461
curl -X POST /api/v1/records/arxiv/2610.21461/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.21461/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'