Kernel-based Methods for Bandit Convex Optimization
- 30 June 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (4), 1-35
- https://doi.org/10.1145/3453721
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 Õ( n 9.5 √ T )-regret, and we show that a simple variant of this algorithm can be run in poly( n log ( T ))-time per step (for polytopes with polynomially many constraints) at the cost of an additional poly( n ) T o(1) factor in the regret. These results improve upon the Õ( n 11 √ T -regret and exp (poly( T ))-time result of the first two authors and the log ( T ) poly( n ) √ T -regret and log( T ) poly( n ) -time result of Hazan and Li. Furthermore, we conjecture that another variant of the algorithm could achieve Õ( n 1.5 √ T )-regret, and moreover that this regret is unimprovable (the current best lower bound being Ω ( n √ 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 n 3 / ɛ 2 .Keywords
Funding Information
- Israel Science Foundation (715/16)
- European Research Council Starting Grant (803084/5)
This publication has 11 references indexed in Scilit:
- Efficient Inverse Maintenance and Faster Algorithms for Linear ProgrammingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends® in Machine Learning, 2012
- The geometry of logconcave functions and sampling algorithmsRandom Structures & Algorithms, 2006
- Fisher information inequalities and the central limit theoremProbability Theory and Related Fields, 2004
- Entropy jumps in the presence of a spectral gapDuke Mathematical Journal, 2003
- Sixty Years of Bernoulli ConvolutionsPublished by Springer Science and Business Media LLC ,2000
- Algorithms for approximate calculation of the minimum of a convex function from its valuesMathematical Notes, 1996
- Location of the Maximum on Unimodal SurfacesJournal of the ACM, 1965
- An Automatic Method for Finding the Greatest or Least Value of a FunctionThe Computer Journal, 1960
- On a Family of Symmetric Bernoulli ConvolutionsAmerican Journal of Mathematics, 1939