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

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

2004-08-02

arxiv.org/abs/cs/0408007v1

Computer Science

Learning

12 pages

Scientific paper

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 signle point (from some feasible set) and pay a cost equal to the value of the next function on our chosen point. Zinkevich shows that, if the each function is revealed after the choice is made, then one can achieve vanishingly small regret relative the best single decision chosen in hindsight. We extend this to the bandit setting where we do not find out the entire functions but rather just their value at our chosen point. We show how to get vanishingly small regret in this setting. Our approach uses a simple approximation of the gradient that is computed from evaluating a function at a single (random) point. We show that this estimate is sufficient to mimic Zinkevich's gradient descent online analysis, with access to the gradient (only being able to evaluate the function at a single point).

Affiliated with

Also associated with

No associations

Rating

Online convex optimization in the bandit setting: gradient descent without a gradient does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Online convex optimization in the bandit setting: gradient descent without a gradient, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online convex optimization in the bandit setting: gradient descent without a gradient will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-307233