Timezone: »

 
Poster
Parameter-Free Online Learning via Model Selection
Dylan J Foster · Satyen Kale · Mehryar Mohri · Karthik Sridharan

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #63
in Posters Tue »
We introduce an efficient algorithmic framework for model selection in online learning, or parameter-free online learning. Our algorithms satisfy oracle inequalities in the adversarial online learning setting. Unlike previous work in this area that has focused on specific, highly structured function classes, such as nested balls in a Hilbert space, we propose a generic meta-algorithm framework that achieves oracle inequalities under minimal structural assumptions: we give the first computationally efficient algorithms that work in arbitrary Banach spaces under mild smoothness assumptions --- previous results only applied to Hilbert spaces. We further derive new oracle inequalities for various matrix classes, non-nested convex sets, and $\R^{d}$ with generic regularizers. Finally, we generalize these results by providing oracle inequalities for arbitrary non-linear classes in the contextual learning model; in particular, we give new algorithms for learning with multiple kernels. These results are all derived through a unified meta-algorithm scheme using a novel ``multi-scale'' algorithm for prediction with expert advice based on random playout, which may be of independent interest.
Keywords: Learning Theory · Online Learning
[ Paper]  [ Poster] 

Author Information

Dylan J Foster (Cornell University)
Satyen Kale (Google)
Mehryar Mohri (Courant Institute and Google)

Mehryar Mohri is a Professor of Computer Science and Mathematics at the Courant Institute of Mathematical Sciences and a Research Consultant at Google. Prior to these positions, he spent about ten years at AT&T Bell Labs, later AT&T Labs-Research, where he served for several years as a Department Head and a Technology Leader. His research interests cover a number of different areas: primarily machine learning, algorithms and theory, automata theory, speech processing, natural language processing, and also computational biology. His research in learning theory and algorithms has been used in a variety of applications. His work on automata theory and algorithms has served as the foundation for several applications in language processing, with several of his algorithms used in virtually all spoken-dialog and speech recognitions systems used in the United States. He has co-authored several software libraries widely used in research and academic labs. He is also co-author of the machine learning textbook Foundations of Machine Learning used in graduate courses on machine learning in several universities and corporate research laboratories.

Karthik Sridharan (Cornell University)

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

More from the Same Authors