Metraipolis › archive › dc_04c87dc6b68f
Minimax Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions — arXiv:2610.05517
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.05517
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T13:05:58.565Z
- SHA-256 of the archived text
d4516b10f90c7411a4404aafc3cae44f72023ec5f7f5c52d8766d8dc30eb153b- Stable URL of this page
https://metraipolis.com/documento/dc_04c87dc6b68f
How to cite
Minimax Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions — arXiv:2610.05517 — arXiv (en), https://arxiv.org/abs/2610.05517 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_04c87dc6b68f (Metraipolis archive dc_04c87dc6b68f, sha256 d4516b10f90c7411a4404aafc3cae44f72023ec5f7f5c52d8766d8dc30eb153b)
BibTeX
@misc{dc04c87dc6b68f,
title = {Minimax Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions — arXiv:2610.05517},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.05517},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_04c87dc6b68f; sha256 d4516b10f90c7411a4404aafc3cae44f72023ec5f7f5c52d8766d8dc30eb153b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.05517. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study zeroth-order optimization of convex and strongly convex functions with Hölder smoothness of order $\beta>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^{-\beta/(\beta-1)}$ on the number of calls, where $d$ is the dimension and $\varepsilon$ the accuracy, and find the sharp power of $d$ under the stronger Hilbert--Schmidt smoothness for all $\beta>2$. An accelerated finite-difference method attains them in $O(\sqrt{\kappa}\log(1/\varepsilon))$ rounds for condition number $\kappa$, like Nesterov's method with exact gradients, and tolerates the optimal systematic and, up to logarithms, adversarial errors; rate-optimal methods need $\Omega(\log d)$ rounds. The same number of calls is attained when the Hessian grows at most linearly with the gradient and, for centered noise, without an upper bound on the Hessian, also in logarithmically many rounds. For convex functions, our lower bound improves the known one polynomially in $d$ and is tight at the curvature of the hard instances; the systematic level is again optimal. These bounds extend to general norms and constraints; on the $\ell_1$ ball, mirror descent needs calls nearly linear in $d$. Experiments confirm the theory.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.05517 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T11:21:31.906Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).