Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization
Whether exact scalar feedback intrinsically incurs the additional dimension $d$ paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a universal Lipschitz scale, the value only bound $O(d^2\log(d+1)\log(1/ε))$ and two-point bound $O(dε^{-2})$ yield the upper bound $\widetilde O\left(d\min\{d,ε^{-2}\}\right)$. By contrast, prior lower bounds for arbitrary randomized algorithms give only $Ω(\min\{d,ε^{-2}\})$, leaving a factor $d$ unexplained. We close this gap, up to logarithmic factors, for arbitrary adaptive randomized algorithms minimizing a convex…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.16558
curl -X POST /api/v1/records/arxiv/2607.16558/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.16558/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'