Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity
Source: arxiv.org/abs/2611.05527
In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose $p^{th}$-order derivatives are Hölder continuous with degree $ν$ and parameter $H$, and that are uniformly convex with degree $q$ and parameter $σ$. When these orders match, namely, $q = p + ν$, we show that any deterministic algorithm with access to derivatives up to order $p$ requires $Ω\left(\left(\frac{H}σ\right)^{\frac{2}{3(p+ν)-2}}\log\frac{Δ_0}ε\right)$ oracle calls to reduce an initial optimality gap of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05527
curl -X POST /api/v1/records/arxiv/2611.05527/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05527/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'