On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
We study the query complexity of finding an an $\varepsilon$-stationary points of a one-dimensional non-convex function whose $p$-th derivative is $β_p$-Hölder continuous. We determine the optimal complexity for deterministic and randomized algorithms and for oracles that return only derivatives, only function values, or full local information. Randomness provably helps when only derivatives are available, function values help in all cases, and higher-order derivatives never do. Together with known results in higher dimensions, this shows how these benefits depend on the dimension. Our…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.16295
curl -X POST /api/v1/records/arxiv/2610.16295/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16295/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'