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\"older regularity ${\beta+k}$ for some $\beta\ge 2$, that $f$ is strongly convex on a compact convex set $\Theta\subset\mathbb{R}^d$ and that $g$ and $f$ satisfy mild boundedness and Lipschitz regularity conditions on $\Theta$, 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\beta+k-1)/(\beta+k)}\,N^{-(\beta-1)/(\beta+k)}$, where $N$ is the total number of queries. We also establish a minimax lower bound of the order $N^{-(\beta-1)/(\beta+k)}$ showing that this rate is optimal in $N$ over all sequential algorithms.