UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Exploiting higher order smoothness in derivative-free optimization and continuous bandits

Akhavan, A; Pontil, M; Tsybakov, AB; (2020) Exploiting higher order smoothness in derivative-free optimization and continuous bandits. In: NIPS'20: Proceedings of the 34th International Conference on Neural Information Processing Systems. (pp. pp. 9017-9027). ACM Green open access

[thumbnail of NeurIPS-2020-exploiting-higher-order-smoothness-in-derivative-free-optimization-and-continuous-bandits-Paper.pdf]
Preview
Text
NeurIPS-2020-exploiting-higher-order-smoothness-in-derivative-free-optimization-and-continuous-bandits-Paper.pdf - Accepted Version

Download (341kB) | Preview

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.

Type: Proceedings paper
Title: Exploiting higher order smoothness in derivative-free optimization and continuous bandits
Event: Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
Open access status: An open access version is available from UCL Discovery
Publisher version: https://dl.acm.org/doi/10.5555/3495724.3496480
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: cs.LG, cs.LG, math.OC, stat.ML
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10164238
Downloads since deposit
36Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item