Online Learning: Beyond Regret

Details Online Learning: Beyond Regret Online Learning: Beyond Regret

2010-11-14

arxiv.org/abs/1011.3168v2

Statistics

Machine Learning

Scientific paper

We study online learnability of a wide class of problems, extending the results of (Rakhlin, Sridharan, Tewari, 2010) to general notions of performance measure well beyond external regret. Our framework simultaneously captures such well-known notions as internal and general Phi-regret, learning with non-additive global cost functions, Blackwell's approachability, calibration of forecasters, adaptive regret, and more. We show that learnability in all these situations is due to control of the same three quantities: a martingale convergence term, a term describing the ability to perform well if future is known, and a generalization of sequential Rademacher complexity, studied in (Rakhlin, Sridharan, Tewari, 2010). Since we directly study complexity of the problem instead of focusing on efficient algorithms, we are able to improve and extend many known results which have been previously derived via an algorithmic construction.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455902