Computer Science – Learning
Scientific paper
2011-08-16
Computer Science
Learning
16 pages. Earlier version of this work submitted (but rejected) to COLT 2011
Scientific paper
Stability is a general notion that quantifies the sensitivity of a learning algorithm's output to small change in the training dataset (e.g. deletion or replacement of a single training sample). Such conditions have recently been shown to be more powerful to characterize learnability in the general learning setting under i.i.d. samples where uniform convergence is not necessary for learnability, but where stability is both sufficient and necessary for learnability. We here show that similar stability conditions are also sufficient for online learnability, i.e. whether there exists a learning algorithm such that under any sequence of examples (potentially chosen adversarially) produces a sequence of hypotheses that has no regret in the limit with respect to the best hypothesis in hindsight. We introduce online stability, a stability condition related to uniform-leave-one-out stability in the batch setting, that is sufficient for online learnability. In particular we show that popular classes of online learners, namely algorithms that fall in the category of Follow-the-(Regularized)-Leader, Mirror Descent, gradient-based methods and randomized algorithms like Weighted Majority and Hedge, are guaranteed to have no regret if they have such online stability property. We provide examples that suggest the existence of an algorithm with such stability condition might in fact be necessary for online learnability. For the more restricted binary classification setting, we establish that such stability condition is in fact both sufficient and necessary. We also show that for a large class of online learnable problems in the general learning setting, namely those with a notion of sub-exponential covering, no-regret online algorithms that have such stability condition exists.
Bagnell Andrew J.
Ross Stephane
No associations
LandOfFree
Stability Conditions for Online Learnability 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 Stability Conditions for Online Learnability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability Conditions for Online Learnability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-194821