Tutorial DescriptionOnline learning is a well established learning paradigm which has both theoretical and practical appeals. The goal of online learning is to make a sequence of accurate predictions given knowledge of the correct answer to previous prediction tasks and possibly additional available information. The roots of online learning goes back to Hannan's work in the 50s. Online learning became of great interest to practitioners due the recent mergence of large scale web applications. Notable examples of web-based applications are online advertisement placement and online web ranking. The tutorial is targeted at people from all areas of machine learning and covers the formal foundations along with algorithmic and practical aspects of online learning. The goal is to provide a high-level, broad, and rigorous overview of the formal online framework. By the end of tutorial the attendees should have acquired enough knowledge to be able to pin-point an online algorithm that best matches an application they face.
The tutorial starts with a simple example of predicting the next element of a binary sequence. We then formally introduce the basic definitions of online learning and the notion of regret analysis. Next we describe the problem of predicting with experts advice by analyzing a few algorithms and contrasting them with an impossibility result. This basic setting is then re-examined in the context of online learning of general linear predictors. We give a recent analysis which reveals an underlying primal-dual apparatus for the analysis of online algorithms. We conclude the formal part of the tutorial with a description of extensions and generalizations of online learning tasks while underscoring connections to game theory, information theory, and reinforcement learning. We recap the tutorial with two complete examples that demonstrate the usage of online learning for portfolio selection and for text filtering.
SlidesA draft of the slides can be downloaded here: OLtutorial.pdf. Please visit this website for updates.
- Shai Shalev-Shwartz is a research assistant professor at the Toyota Technological Institute at Chicago. His Ph.D. thesis was entitled "Online Learning: Theory, Algorithms, and Applications". His work spans all aspects of online learning.
- Yoram Singer is a senior research scientist at Google. From 1999 through 2007 he was an associate professor at the Hebrew University of Jerusalem. He has published extensively in all areas of machine learning and in particular in the area of online learning. He has over 50 publications on online learning. To find his publications list in DBLP google the term yoram machine learning.
- Prediction Learning and Games. N. Cesa-Bianchi and G. Lugosi. Cambridge university press, 2006.
- Online learning: Theory, Algorithms, and Applications. S. Shalev-Shwartz. PhD Thesis, the Hebrew university, 2007.