Metraipolis › archive › dc_13ee8ee7ae27
Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives — arXiv:2609.18678
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18678
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T15:42:49.097Z
- SHA-256 of the archived text
80be46ca5e07d5bf1cb3d9c435a9c1c04c9bf4b2fba6e08fd3d4eae3bac6b0fc- Stable URL of this page
https://metraipolis.com/documento/dc_13ee8ee7ae27
How to cite
Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives — arXiv:2609.18678 — arXiv (en), https://arxiv.org/abs/2609.18678 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_13ee8ee7ae27 (Metraipolis archive dc_13ee8ee7ae27, sha256 80be46ca5e07d5bf1cb3d9c435a9c1c04c9bf4b2fba6e08fd3d4eae3bac6b0fc)
BibTeX
@misc{dc13ee8ee7ae27,
title = {Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives — arXiv:2609.18678},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18678},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_13ee8ee7ae27; sha256 80be46ca5e07d5bf1cb3d9c435a9c1c04c9bf4b2fba6e08fd3d4eae3bac6b0fc},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18678. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider the problem of noisy gradient-free minimization of the k-th order partial derivative of a $\beta$-H{ö}lder function supported on a d-dimensional cube. We show that T ^{($\beta$+d+k)/(2$\beta$+d)} log(T )^{(\beta-k)/(2\beta+d)} is a non-asymptotic minimax rate of the T step cumulative regret for all $\beta$ \ge 0. In the special case k = 0, our results cover the problem of noisy gradient-free minimization of $\beta$-H{ö}lder functions, closing the existing gap between the known upper and lower bounds. We show that a minimizer of a suitably chosen local polynomial estimator is rate-optimal. The minimax optimal upper bound is achieved under the passive design, that is, when the query points are i.i.d. Thus, there is no advantage in considering sequential designs when it is only known that f is a $\beta$-H{ö}lder function with no additional property. We propose an algorithm feasible in polynomial time that constructs a proxy of the minimizer of the local polynomial estimator. The procedure requires computing the estimator on auxiliary random points. The resulting polynomial time algorithm matches the lower bound.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in math.ST).
Categorie arXiv: Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2609.18678 — 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-15T15:08:37.145Z dalla pagina https://arxiv.org/catchup/math.ST/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).