Provably efficient algorithms are essential for solving nontrivial machine learning problems. The primary goal of computational learning theory is the development of a rich set of algorithmic tools for efficiently solving common classification tasks. In this course, we survey well-established models of learning and describe a variety of algorithms for learning concept classes within these models. Topics include PAC learning, online learning, halfspace-based learning, Fourier-based learning, boosting, learning with noise, random projection, and query learning. In addition, we describe how to apply results from cryptography and computational complexity to prove the intractability of various machine learning problems. No background is required for this course other than a working knowledge of basic probability and mathematical maturity. The class grade will be based on homework and a possible final project.
Models of Learning: PAC, Exact, On-line, Mistake Bound, and relationships. (1-2 Weeks)
Learning by Polynomials: polynomial threshold functions, DNF formulas, decision trees, decision lists, intersections of halfspaces. (2 Weeks)
Generalization Error: Occam's Razor, VC-Dimension. (1-2 Weeks)
Learning a Halfspace: Perceptron, Winnow, Boosting-Based Methods, Linear Programming. (2-3 Weeks)
Boosting: Definitions, Weak to Strong Learning, Schapire's Booster, AdaBoost, Boosting with Branching Programs, Smooth Boosting, Applications. (2 Weeks)
Uniform Distribution Learning: Fourier-based learning. Agnostic learning. (1-2 Weeks)
Hardness: Relationship to Cryptography, Pseudorandom function generators, NP-hardness of proper learning. (2 Weeks)
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.