Kernel-based methods for bandit convex optimization

DOI10.1145/3055399.3055403MaRDI QIDQ4977962zbMATH OpenOpenAlexFDO

Authors Sébastien Bubeck, Yin Tat Lee, Ronen Eldan

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.03084

zbMATH Keywords

convex optimizationmulti-armed banditonline learning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25) Probabilistic games; gambling (91A60)

Abstract: We consider the adversarial convex bandit problem and we build the first $mathrmpoly(T)$-time algorithm with $mathrmpoly(n)sqrtT$-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 $ildeO(n^{9.5}sqrtT)$-regret, and we show that a simple variant of this algorithm can be run in $mathrmpoly(nlog(T))$-time per step at the cost of an additional $mathrmpoly(n)T^{o(1)}$ factor in the regret. These results improve upon the $ildeO(n^{11}sqrtT)$-regret and $exp(mathrmpoly(T))$-time result of the first two authors, and the $log(T{)}^{mathrmpoly(n)}sqrtT$-regret and $log(T{)}^{mathrmpoly(n)}$-time result of Hazan and Li. Furthermore we conjecture that another variant of the algorithm could achieve $ildeO(n^{1.5}sqrtT)$-regret, and moreover that this regret is unimprovable (the current best lower bound being $Omega(nsqrtT)$ 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/epsilo{n}^2$.

Recommendations

• Kernel-based Methods for Bandit Convex Optimization
• Kernel estimation and model combination in a bandit problem with covariates
• Stochastic convex optimization with bandit feedback
• Bandit convex optimization in non-stationary environments
• Bandwidth selection in kernel empirical risk minimization via the gradient
• Optimizing Kernel Methods: A Unifying Variational Principle
• Optimal and robust kernel algorithms for passive stochastic approximation
• On convergence of kernel learning estimators

Cited in

(18)

• Exploratory distributions for convex functions
• Improved regret for zeroth-order adversarial bandit convex optimisation
• Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference
• Improved exploitation of higher order smoothness in derivative-free optimization
• Optimal multi-unit mechanisms with private demands
• Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
• Kernel-based Methods for Bandit Convex Optimization
• An accelerated method for derivative-free smooth stochastic convex optimization
• Technical note: Nonstationary stochastic optimization under \(L_{p,q} \)-variation measures
• Derivative-free optimization methods
• Stochastic convex optimization with bandit feedback
• Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
• Zeroth-order algorithms for nonconvex-strongly-concave minimax problems with improved complexities
• Distributed zeroth-order optimization: convergence rates that match centralized counterpart
• Adversarial bandits with knapsacks
• Bayesian design principles for frequentist sequential learning
• A simple and improved algorithm for noisy, convex, zeroth-order optimisation
• Statistical complexity and optimal algorithms for nonlinear ridge bandits

This page was built for publication: Kernel-based methods for bandit convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977962)