An optimal algorithm for bandit convex optimization

Abstract

We consider the problem of online convex optimization against an arbitrary adversary with bandit feedback, known as bandit convex optimization. We give the first $\tilde{O}(\sqrt{T})$-regret algorithm for this setting based on a novel application of the ellipsoid method to online learning. This bound is known to be tight up to logarithmic factors. Our analysis introduces new tools in discrete convex geometry.

arXiv comment29 pages, 8 figures

References in corpus (1)

• Towards minimax policies for online linear optimization with bandit feedback

Cited by in corpus (14)

• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints
• Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs
• Improved Regret Bounds for Projection-free Bandit Convex Optimization
• Boosting One-Point Derivative-Free Online Optimization via Residual Feedback
• An efficient high-probability algorithm for Linear Bandits
• Distributed Zeroth-Order Stochastic Optimization in Time-varying Networks
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization
• Online learning with kernel losses
• Online Newton Step Algorithm with Estimated Gradient
• Minimax Regret for Bandit Convex Optimisation of Ridge Functions
• Recursive Exponential Weighting for Online Non-convex Optimization
• Minimizing Regret of Bandit Online Optimization in Unconstrained Action Spaces