A central problem in machine learning is to develop algorithms that have provable guarantees in terms of both running time and generalization error with respect to a small "training" set of data. Computational Learning Theory has traditionally focused on the first issue (the computational complexity of learning algorithms) while Statistical Learning Theory has focused on the second (robustness of a classifier). This course will cover the most exciting results from both Computational and Statistical Learning Theory. We will begin with fundamental topics (no machine learning background is required) and move rapidly towards recent developments in each subfield. For example, we will begin by studying the problem of classification in well-established models of learning such as PAC learning, online learning, mistake-bound learning and query learning among others. We will analyze efficient algorithms for learning concept classes within these models and also prove hardness results. The Statistical Learning Theory part of the course will address the problem of discovering probabilistic relationships among random variables derived from data. Topics include parametric and nonparametric methods for classification and regression as well as how to analyze properties such as minimax rates and consistency and persistency of estimators.
No background is required for this course other than a working knowledge of basic probability and mathematical maturity. Coursework includes four problem sets (1/2 of final grade), scribe notes (1/4 of final grade; the scribe notes should be a polished and thorough written version of the lecture), and a final paper presentation (1/4 of final grade).
Models of Learning: PAC, Exact, On-line, Mistake Bound, and relationships.
Learning by Polynomials: polynomial threshold functions, DNF formulas, decision trees, decision lists.
Generalization Error.
Learning a Halfspace: Perceptron, Winnow, Linear Programming.
Boosting: Definitions, Weak to Strong Learning, AdaBoost, Boosting with Branching Programs.
Uniform Distribution Learning: Fourier-based learning. Agnostic learning.
Regression.
Graphical Models.
Sparsity.
An (undergraduate) course in algorithms or complexity may be helpful. An Introduction to Computational Learning Theory by Kearns and Vazirani is a good reference book for topics to be covered here.
A nice survey of the Mistake Bound learning model by Avrim Blum.