Skip to content
conftrace_
2021 COLT COLT 2021

Improved Regret for Zeroth-Order Stochastic Convex Bandits

Abstract

We present an efficient algorithm for stochastic bandit convex optimisation with no assumptions on smoothness or strong convexity and for which the regret is bounded by O(d^(4.5) sqrt(n) polylog(n)), where n is the number of interactions and d is the dimension.

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization
🐣 Hot Topic Early Bird - zeroth-order optimization

Authors

Tor Lattimore, András György

Topics

Machine Learning > Optimization & Theory > Learning Theory Mathematics & Optimization > Optimization > Stochastic Methods Machine Learning > Optimization & Theory > Online Algorithms Machine Learning > Learning Types > Multi-Armed Bandits Mathematics & Optimization > Optimization > Convex Optimization

Keywords

stochastic optimization convex optimization regret bound bandit optimization zeroth-order optimization bandit algorithm convex bandit
Download PDF

More from COLT 2021

All COLT 2021 papers →
On the Minimal Error of Empirical Risk Minimization
**Paper retracted by author request (see pdf for retraction notice from the authors)** Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping
Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning
Mirror Descent and the Information Ratio
Structured Logconcave Sampling with a Restricted Gaussian Oracle
Stochastic Approximation for Online Tensorial Independent Component Analysis