Online Learning: Random Averages, Combinatorial Parameters, and Learnability

Details Online Learning: Random Averages, Combinatorial Parameters, and Learnability Online Learning: Random Averages, Combinatorial Parameters, and Learnability

2010-06-06

arxiv.org/abs/1006.1138v2

Computer Science

Learning

Scientific paper

We study learnability in the online learning model. We define several complexity measures which capture the difficulty of learning in a sequential manner. Among these measures are analogues of Rademacher complexity, covering numbers and fat shattering dimension from statistical learning theory. Relationship among these complexity measures, their connection to online learning, and tools for bounding them are provided. In the setting of supervised learning, finiteness of the introduced scale-sensitive parameters is shown to be equivalent to learnability. The complexities we define also ensure uniform convergence non-i.i.d. data, extending the uniform Glivenko-Cantelli type results. We conclude by showing online learnability for an array of examples.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-366059