Improved regret guarantees for online smooth convex optimization with bandit feedback

The study of online convex optimization in the bandit setting was initiated by Klein-berg (2004) and Flaxman et al. (2005). Such a setting models a decision maker that has to make decisions in the face of adversari-ally chosen convex loss functions. Moreover, the only information the decision maker re-ceives are the losses. The identities of the loss functions themselves are not revealed. In this setting, we reduce the gap between the best known lower and upper bounds for the class of smooth convex functions, i.e. convex functions with a Lipschitz continuous gradi-ent. Building upon existing work on self-concordant regularizers and one-point gradi-ent estimation, we give the first algorithm whose expected regret is O(T 2/3), ignoring constant and logarithmic factors.