Online convex optimization in the bandit setting: gradient descent without a gradient

Abraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan

We consider a the general online convex optimization framework introduced by Zinkevich. In this setting, there is a sequence of convex functions. Each period, we must choose a sign…