An optimal algorithm for bandit convex optimization

2016/03/14 by Hazan, Elad, Li, Yuanzhi
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.1.6 #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1603.04350

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 O(√(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.

Related

• Risk-Averse Stochastic Convex Bandit
• Stochastic convex optimization with bandit feedback
• Second Order Methods for Bandit Optimization and Control
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization
• Bandit Convex Optimization: sqrtT Regret in One Dimension