CS269: Machine Learning Theory
Monday/Wednesday, 2-4pm, Boelter 2760
Instructor: Jenn Wortman Vaughan
If you got here looking for lecture notes on learning theory, please see the Fall 2011 version of this course which has more up-to-date and accurate versions of the scribe notes here.

Recent Announcements

Course Overview

This course will provide a broad overview of the theoretical foundations underlying common machine learning algorithms. We will cover the following topics, though not necessarily in this order:

This course has no official prerequisites, but basic knowledge of probability and some level of comfort reading and writing mathematical proofs will be extremely useful. This course will count for credit for the AI major and minor field requirements for computer science Ph.D. students.

There is no required text book for this course. Lecture notes and papers of interest will be made available online. Additionally, some optional books that you might find useful are listed below.

Office hours for this course are by appointment only. Email Jenn to schedule an appointment.

Schedule & Lecture Notes

This schedule is tentative and likely to change as we get further into the material. Scribe notes for each lecture will be posted here as soon as they have been approved.

DISCLAIMER: While I have tried to carefully read over all of the scribe notes for this class, it is entirely possible that some of them contain errors. If you think you see an error, please email me and I will check it out.

Part 1: Classification and the PAC Model

Part 2: Online Learning in Adversarial Settings

Part 3: Some Practical Successes of Learning Theory

Part 4: New Topics and Project Presentations

Final projects will be due the second week of December.

Additional Reading

Students may find the following (completely optional) textbooks useful for exploring some of the topics that we cover in more depth:

You might also find it helpful to look through lecture notes and slides from similar courses that have been offered at other universities such as Avrim Blum's course at CMU or Rob Schapire's course at Princeton. Links to specific notes from other courses that are especially relevant to particular lectures are included in the schedule above.

Homework Policies and Grading

Coursework will involve two written homework assignments and one open-ended final project. Course grades will be based 40% on homeworks (20% each), 20% on class participation (including preparation of scribe notes), and 40% on the final project (which will include a written report and short presentation in class). There will be no in-class exams.

Homework assignments are available here:

Collaboration on the homework assignments is encouraged! Students are free to discuss the homework problems with anyone in the class under the following conditions:

  1. Each student must write down his or her solutions independently, and must understand the solutions he or she writes down. Talking over solutions is fine, but reading or copying another student's answers is not acceptable!
  2. Each student must write a list of all of his or her collaborators at the top of each assignment.

Start your assignments early so that they will be completed on time! Assignments submitted up to 24 hours late will be penalized 25%. No assignments will be accepted for credit more than 24 hours after the deadline. Final projects and scribe notes must be submitted on time.

Instructions for Preparing Scribe Notes

Since there is no single ideal text book for this course, students will take turns preparing "scribe notes" on each lecture that will be made available online. Your notes should be written in complete sentences, and should contain enough detail to be understandable even to students who were unable to attend class. Please be clear! If you have questions about the material that was covered, get in touch with me and we can arrange a time to chat.

If you are preparing notes for a Monday lecture, your first draft is due on Wednesday (two days later) at 2pm. I will then give you feedback and you will have until the following Wednesday to revise. If you are preparing notes for a Wednesday lecture, your first draft is due on Friday (two days later) at 2pm. I will give you feedback and you will have until the following Friday to revise. This schedule is tight, but the goal is to make the notes available as quickly as possible.

Notes must be prepared using this LaTeX template. Here is the source file for the September 27 lecture notes to use as an example. If you are new to LaTeX, many good tutorials can be found online. A good reference for many common symbols is available here, or try Detexify, a cool machine learning tool that automatically finds the symbols you need. If you are a Mac user and would like to install LaTeX on your own machine, I highly recommend the bundled version of TeXShop and MacTeX available here. Windows users can try MiKTeX. LaTeX is also installed on department-run linux machines.

Both the first draft and the revisions should be submitted to me by email. Please submit both a PDF and your tex source. There should be one submission per team.

Final Projects

These final project guidelines were distributed in class on October 11. The guidelines provide details on the types of projects you can pursue, as well as a list of key dates and milestones. Be sure to read the guidelines carefully and make a note of important deadlines!

Below are some suggestions for topics that could be explored in more detail for the final project. All of these would make good literature synthesis topics, and some might lead to ideas for research projects. Of course you are welcome to choose a topic that is not on the list.

The Multi-Armed Bandit Problem:

Domain Adaptation:

Privacy-Preserving Machine Learning:

Learning from a Crowd:

Reinforcement Learning:

Machine Learning for Finance:

A Different Twist on Learning for Finance:

New Twists on Clustering:

Try checking out recent publications from COLT (2010, 2009) or NIPS (2010, 2009) for additional ideas.