This course will focus on theoretical aspects of Statistical Learning and Sequential Prediction. Until recently, these two subjects have been treated separately within the learning community. The course will follow a unified approach to analyzing learning in both scenarios. To make this happen, we shall bring together ideas from probability and statistics, game theory, algorithms, and optimization. It is this blend of ideas that makes the subject interesting for us, and we hope to convey the excitement. We shall try to make the course as self-contained as possible, and pointers to additional readings will be provided whenever necessary. Our target audience is graduate students with a solid background in probability and linear algebra.

“Learning” can be very loosely defined as the “ability to improve performance after observing data”. Over the past two decades, there has been an explosion of both applied and theoretical work on machine learning. Applications of learning methods are ubiquitous: they include systems for face detection and face recognition, prediction of stock markets and weather patterns, speech recognition, learning user’s search preferences, placement of relevant ads, and much more. The success of these applications has been paralleled by a well-developed theory. We shall call this latter branch of machine learning – “learning theory”.

Why should one care about machine learning? Many tasks that we would like computers to perform cannot be hard-coded. The programs have to adapt. The goal then is to encode, for a particular application, as much of the domain-specific knowledge as needed, and leave enough flexibility for the system to improve upon observing data.