Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions

Timofei Loginov, Darina Dvinskikh, Nazarii Tupitsa, Osman Osmanov, Yuriy Dorn, Alexander Gasnikov

arXivarxiv/2610.05517Oct 4, 2026math.OCscore 0

We study zeroth-order optimization of convex and strongly convex functions with Hölder smoothness of order $β>2$ from values corrupted by random noise with bias independent of the method's random directions, a Lipschitz systematic error and a bounded adversarial error. We measure the number of function evaluations (calls), of sequential rounds of parallel calls, and the largest tolerable systematic and adversarial errors. For strongly convex functions with a bounded Hessian, we prove a lower bound of order $d^2\varepsilon^{-β/(β-1)}$ on the number of calls, where $d$ is the dimension and…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.05517
curl -X POST /api/v1/records/arxiv/2610.05517/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.05517/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'