Princeton University
Computer Science Department

Computer Science 511
Foundations of Machine Learning

Rob Schapire

Spring 2004


General Information | Schedule & Readings | Assignments | Final Project

Course Summary

Machine learning studies automatic methods for learning to make accurate predictions or useful decisions based on past observations. This course introduces the mathematical foundations of machine learning, including theoretical models of machine learning, and the design and analysis of learning algorithms. Topics include: bounds on the number of random examples needed to learn; learning from non-random examples in the on-line learning model (for instance, for investment portfolio selection); how to boost the accuracy of a weak learning algorithm; learning with queries; support-vector machines.

Here is a tentative list of topics. If time permits, additional topics may be added. (Bullets do not correspond precisely to lectures.)

Administrative Information


TTh, 11-12:20, Friend Center 009


Rob Schapire: 407 CS Building, x8-7726, schapire@cs
Office hours: by appointment (via email), or just stop by.


There is no TA for this course.

Graduate Coordinator:

Melissa Lawson: 310 CS Building, x8-5387, mml@cs


This class has no formal prerequisites.  However, it is assumed that students will have a general background in computer science (especially theoretical computer science), and an ability to solve mathematical problems rigorously.

(Suggested) Textbook

There is no textbook that perfectly fits the material in this course. However, the one that comes closest is An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani. I am not requiring this book, but if you want a text, this is the one that I would recommend.  We will cover about half of the material in this book.  I will also post other papers or notes for topics not in the book.

A list of other books for further background reading appears on the Schedule & Readings page, and are being placed on reserve at the Engineering Library.

Grading and workload

Grading will be based on homework assignments (65%) and a final project (35%). Homeworks will be given roughly every week or two, and will each consist of a small number of problems (no programming). For the final project, you can pick any topic you want for further study. Your project could involve implementing an algorithm, running experiments, doing further reading or trying to theoretically extend a result of interest. In all cases, the end product will be a written report. More details will be given later in the semester.  Grades may also be adjusted upward slightly based on regular, positive contributions to class discussions.

See the Assignments page for information on the late policy and collaboration policy.


As soon as possible, please join the course mailing list, especially if you are taking the course for credit.  To do so, click here, and follow the instructions for subscribing to the list.  To post to the list, send email to cos511@lists.cs.