Kernel-based Methods for Bandit Convex Optimization
Sébastien Bubecka b c, Yin Tat Leea d, Ronen Eldane f
- aMicrosoft Research, USA
- bMicrosoft Research
- cUSA
- d#N##TAB##TAB##TAB##TAB# Weizmann Institute of Science, Israel#N##TAB##TAB##TAB#
- eWeizmann Institute of Science, Israel
- fUniversity of Washington , USA
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We consider the adversarial convex bandit problem and we build the first poly(T)-time algorithm with poly(n) √T-regret for this problem. To do so we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, and (iii) a new annealing schedule for exponential weights (with increasing learning rate). The basic version of our algorithm achieves Õ(n9.5 #8730;T)-regret, and we show that a simple variant of this algorithm can be run in poly(n log(T))-time per step at the cost of an additional poly(n) To(1) factor in the regret. These results improve upon the Õ(n11 #8730;T)-regret and exp(poly(T))-time result of the first two authors, and the log(T)poly(n) #8730;T-regret and log(T)poly(n)-time result of Hazan and Li. Furthermore we conjecture that another variant of the algorithm could achieve Õ(n1.5 #8730;T)-regret, and moreover that this regret is unimprovable (the current best lower bound being Ω(n #8730;T) and it is achieved with linear functions). For the simpler situation of zeroth order stochastic convex optimization this corresponds to the conjecture that the optimal query complexity is of order n3 / ϵ2.
TL;DRThis work considers the adversarial convex bandit problem and builds the first poly(T)-time algorithm with poly(n) √T-regret for this problem, and introduces three new ideas in the derivative-free optimization literature: kernel methods, a generalization of Bernoulli convolutions, and a new annealing schedule for exponential weights. (Semantic Scholar)