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

Abraham Flaxman, Adam Tauman Kalai, H. Brendan McMahan

Browse the full SODA paper archive.