Regret Bound by Variation for Online Convex Optimization

Details Regret Bound by Variation for Online Convex Optimization Regret Bound by Variation for Online Convex Optimization

2011-11-28

arxiv.org/abs/1111.6337v2

Computer Science

Learning

Scientific paper

In citep{Hazan-2008-extract}, the authors showed that the regret of online linear optimization can be bounded by the total variation of the cost vectors. In this paper, we extend this result to general online convex optimization. We first analyze the limitations of the algorithm in \citep{Hazan-2008-extract} when applied it to online convex optimization. We then present two algorithms for online convex optimization whose regrets are bounded by the variation of cost functions. We finally consider the bandit setting, and present a randomized algorithm for online bandit convex optimization with a variation-based regret bound. We show that the regret bound for online bandit convex optimization is optimal when the variation of cost functions is independent of the number of trials.

Affiliated with

Also associated with

No associations

Rating

Regret Bound by Variation for Online Convex Optimization 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 Regret Bound by Variation for Online Convex Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Regret Bound by Variation for Online Convex Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66845