Princeton University
Computer Science Department

Computer Science 511
Foundations of Machine Learning

Rob Schapire

Spring 2006


General Information | Schedule & Readings | Assignments | Final Project

How to prepare scribe notes

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, 1:30-2:50, Friend Center 008


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.  However, Aurélie Lozano (alozano@) and Miro Dudík (mdudik@) have graciously agreed to help me grade the homeworks.  You should only contact them if you have a question about how one of the homeworks was graded.  Otherwise, all questions should be sent directly to me.

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.


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.  We will cover about the first third of the book, namely, the first three chapters, all of which are available (free) from the Princeton library in their electronic course reserves.  To obtain these, log on here with user name "cos 511" (noting the lowercase lettering, as well as the space between "cos" and "511"); the password is the instructor's last name (all lowercase).

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).  Students will also be asked to prepare scribe notes for one class (see below).  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.

Students may also be asked to help in the grading of homework assignments.

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

Scribe notes

Because there is no perfect textbook for this course, students will be asked to take turns preparing "scribe notes" for posting on the course web site (specifically, on the Schedule and Readings page).  Each class, one student will be the designated "scribe", taking careful notes during class, writing them up, and sending them to me for posting on the web.  Here is more information on how to be a scribe.  I will not grade the scribe notes, but I will give credit for doing them (about equal to one problem set).


As soon as possible, please join the course mailing list by visiting and following the instructions for subscribing.  I will use this list for general announcements, such as last minute corrections to the homeworks, changes in due date, etc.  This list can also be used by students for discussing course material, general-interest questions about the homeworks, etc.  Of course, if your question is specific to your own work, you will probably want to contact me directly.

When signing up for the mailing list, please provide your name, especially if you are using a non-Princeton email address.  Email addresses that I cannot identify as legitimate will be removed from the list.

You can post to the list by sending mail to  (Note that you can only post to the list using the email address you used to subscribe to it.)