Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds
We study the query complexity of finding approximate stationary points under higher-order smoothness using only function values or only gradients. Our results cover different dimensions, oracle models, randomization, and constraints. For constant dimension $d$ and $C^{p,β_p}$ objectives, with $ν:=p+β_p$, we give deterministic function-value gradient trapping algorithms with query complexities $O(\varepsilon^{-(d-1)})$ on $\mathbb R^d$ and $O(\varepsilon^{-(d-1)/ν})$ on $[0,1]^d$. High-order line integration enables gradient-only trapping. For two-dimensional $C^{1,1}$ objectives, randomized…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.02791
curl -X POST /api/v1/records/arxiv/2610.02791/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.02791/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'