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

We study the problem of zero-order optimization of a strongly convex\nfunction. The goal is to find the minimizer of the function by a sequential\nexploration of its values, under measurement noise. We study the impact of\nhigher order smoothness properties of the function on the optimization error\nand on the cumulative regret. To solve this problem we consider a randomized\napproximation of the projected gradient descent algorithm. The gradient is\nestimated by a randomized procedure involving two function evaluations and a\nsmoothing kernel. We derive upper bounds for this algorithm both in the\nconstrained and unconstrained settings and prove minimax lower bounds for any\nsequential search method. Our results imply that the zero-order algorithm is\nnearly optimal in terms of sample complexity and the problem parameters. Based\non this algorithm, we also propose an estimator of the minimum value of the\nfunction achieving almost sharp oracle behavior. We compare our results with\nthe state-of-the-art, highlighting a number of key improvements.\n