Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives
Abstract
We consider the problem of noisy gradient-free minimization of the k-th order partial derivative of a β-Hölder function supported on a d-dimensional cube. We show that T ^{(β+d+k)/(2β+d)} log(T )^{(\beta-k)/(2\beta+d)} is a non-asymptotic minimax rate of the T step cumulative regret for all β \ge 0. In the special case k = 0, our results cover the problem of noisy gradient-free minimization of β-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 β-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.
Related
- From proximal alternating minimization techniques to composite proximal gradient
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
- A method for global minimization of nonconvex quadratic functions
- Optimality of Threshold Policies for Heat Storage Optimization and a Policy Gradient Algorithm
BibTeX
@misc{paquier2026minimax,
title = {{Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives}},
author = {Théo Paquier and Alexandre B Tsybakov and François Portier and Mohammadreza M Kalan},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18678},
eprint = {2609.18678},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05750153v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives
AU - Théo Paquier
AU - Alexandre B Tsybakov
AU - François Portier
AU - Mohammadreza M Kalan
PY - 2026
DA - 2026/09/15
PB - HAL
DO - 10.48550/arxiv.2609.18678
UR - https://hal.science/hal-05750153v1
AB - We consider the problem of noisy gradient-free minimization of the k-th order partial derivative of a β-Hölder function supported on a d-dimensional cube. We show that T ^{(β+d+k)/(2β+d)} log(T )^{(\beta-k)/(2\beta+d)} is a non-asymptotic minimax rate of the T step cumulative regret for all β \ge 0. In the special case k = 0, our results cover the problem of noisy gradient-free minimization of β-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 β-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.
ER -