Timezone: »

 
Poster
Online Learning: Random Averages, Combinatorial Parameters, and Learnability
Sasha Rakhlin · Karthik Sridharan · Ambuj Tewari

Tue Dec 07 12:00 AM -- 12:00 AM (PST) @ None #None

We develop a theory of online learning by defining several complexity measures. Among them 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. We apply these results to various learning problems. We provide a complete characterization of online learnability in the supervised setting.

Author Information

Sasha Rakhlin (University of Pennsylvania)
Karthik Sridharan (University of Pennsylvania)
Ambuj Tewari (University of Michigan)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors