'Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits'
---

Introduction
============

We study the problem of zero-order stochastic optimization, in which we aim to minimize an unknown strongly convex function via a sequential exploration of its function values, under measurement error, and a closely related problem of continuous (or continuum-armed) stochastic bandits. These problems have received significant attention in the literature, see [@agarwal2010; @agarwal2011; @BP2016; @bartlett2018simple; @belloni2015escaping; @bubeck2012regret; @bubeck2017kernel; @duchi2015; @dvurechensky2018accelerated; @flaxman2004; @hu2016bandit; @liang2014zeroth; @jamieson2012; @Locatelli; @malherbe2017global; @NS17; @rakhlin2011making; @saha2011; @Shalev-Shwartz2011; @Shamir13; @Shamir17; @wang2017stochastic], and are fundamental for many applications in which the derivatives of the function are either too expensive or impossible to compute. A principal goal of this paper is to exploit higher order smoothness properties of the underlying function in order to improve the performance of search algorithms. We derive upper bounds on the estimation error for a class of projected gradient-like algorithms, as well as close matching lower bounds, that characterize the role played by the number of iterations, the strong convexity parameter, the smoothness parameter, the number of variables, and the noise level.

Let $f: \mathbb{R}^d \rightarrow \mathbb{R}$ be the function that we wish to minimize over a closed convex subset ${\Theta}$ of 