Gradient-free stochastic optimization of derivatives under strong convexity

Abstract

We consider the problem of minimizing the $k$-th order partial derivative $f={\partial }_j^{k}g$ of an unknown function $g$ along a fixed coordinate direction $j$, based on noisy queries of $g$. Assuming that $g$ has Hölder regularity ${\hat{I}}^2+k$ for some ${\hat{I}}^2\ge 2$, that $f$ is strongly convex on a compact convex set $\hat{I}˜\subset {\mathbb{R}}^d$ and that $g$ and $f$ satisfy mild boundedness and Lipschitz regularity conditions on $\hat{I}˜$, we propose a kernel-based estimator of $\nabla f$ and analyze the projected stochastic gradient algorithm driven by this estimator. We obtain a non-asymptotic upper bound on the optimization error of the order $d^{(2{\hat{I}}^2+k-1)/({\hat{I}}^2+k)}{N}^{-({\hat{I}}^2-1)/({\hat{I}}^2+k)}$, where $N$ is the total number of queries. We also establish a minimax lower bound of the order $N^{-({\hat{I}}^2-1)/({\hat{I}}^2+k)}$ showing that this rate is optimal in $N$ over all sequential algorithms.