Theoretical and Algorithmic Foundations of Online Learning
A major challenge for machine learning in the next decade is the development of methods that continuously predict and learn from a stream of data. The scale of data and the non-stationary nature of the environment make the prevalent ``learn from a batch of i.i.d. data'' paradigm of Statistical Learning inadequate. Despite the extensive literature on sequential prediction (online learning) methods, the theoretical understanding of the subject has been lacking, and the results have been obtained on a case-by-case basis. This stands in contrast to Statistical Learning, where the inherent complexities have been well-understood in the last forty years. In this talk, we focus on no-regret online learning and develop the relevant notions of complexity in a surprising parallel to Statistical Learning Theory. This non-constructive study of inherent complexity is then augmented with a recipe for developing efficient online learning algorithms via a notion of a relaxation. To demonstrate the utility of our approach, we develop a new family of randomized methods and new algorithms for a collaborative filtering problem. We then discuss extensions of our techniques beyond no-regret learning and outline a roadmap of further research directions.
Alexander Rakhlin is an Assistant Professor at the Department of Statistics and the Department of Computer and Information Science (secondary) at the University of Pennsylvania. He received his bachelors degrees in Mathematics and Computer Science from Cornell University, and doctoral degree from MIT. He was a postdoc at UC Berkeley EECS before joining UPenn, where he is a co-director of the Penn Research in Machine Learning (PRiML) center. His research is in machine learning, with an emphasis on statistics and computation. Alexander is a recipient of the NSF CAREER award, IBM Research Best Paper award, Machine Learning Journal award, and COLT Best Paper Award.