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

Abstract

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

References in corpus (1)

• A companion for the Kiefer--Wolfowitz--Blum stochastic approximation algorithm

Cited by in corpus (7)

• Improved Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandit
• Continuum-Armed Bandits: A Function Space Perspective
• About some works of Boris Polyak on convergence of gradient methods and their development
• Smooth Bandit Optimization: Generalization to Hölder Space
• Small errors in random zeroth-order optimization are imaginary
• Linearly Convergent Gradient-Free Methods for Minimization of Parabolic Approximation
• One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learning