COMS E6253: Advanced Topics in Computational Learning Theory
Spring 2012

General Information | Motivation | Prerequisites | Topics | Class Requirements | Readings | Scribe Notes |

General Information

Instructor: Rocco Servedio (517 CSB, office hours Fri 10-12). Email: rocco at cs dot columbia dot edu.
TA: Li-Yang Tan (office hours TBA; email liyang at cs dot etc)
Room: TBA
Time: Thurs 11:00-12:50

COMS E6253 is an advanced graduate course in computational learning theory. The focus of the course in 2012 will be on efficient (or as close to efficient as we know) algorithms for challenging Boolean function learning problems, with an emphasis on various noisy/agnostic learning problems.

The course can be used as a theory elective for the Ph.D. program in computer science, as a track elective course for MS students in the "Foundations of Computer Science" track or the "Machine Learning" track, or as a track elective for undergratuates in the "Foundations" track. Auditing the class requires the approval of the instructor.


We will study algorithms for learning Boolean functions from labeled examples. Our focus will be on state-of-the-art computationally efficient (or as close to efficient as we know how to get) and provably correct algorithms in well-defined learning models; our study will be carried out from a theoretical computer science perspective.

There is no single right way to theoretically model a complex phenomenon such as learning. In this course we will cover several different models of learning: these will include the standard (distribution-free) Probably Approximately Correct learning model; various models of learning under the uniform distribution (where the learner may or may not have query access to the unknown function being learned); and various models of learning from noisy examples. Within these frameworks we will study algorithms for learning functions like decision trees, DNF formulas, juntas, intersections of halfspaces, constant-depth circuits, and more. We'll see that in noisy learning models it can be challenging even to learn simple functions like conjunctions and parity functions (and we will give algorithms for these and other noisy learning problems).

Much of the course will have a complexity-theoretic flavor, and a central theme of the course will be the close connections which exist between techniques and ideas from computational complexity theory and efficient algorithms in computational learning theory.


COMS 4252 (Computational Learning Theory) is ideal preparation. Students who have not taken COMS 4252 but who have taken some related coursework (such as COMS 4772, COMS 4236, or COMS 4231 or equivalent courses elsewhere) may enroll with the instructor's permission; contact me if you have questions.

List of Topics

First unit: PAC learning.

Second unit: Uniform-distribution PAC learning.

Third unit: Learning with noise / agnostic learning.

Class Requirements

The requirements of the course are as follows:


There is no required textbook for the course. Pointers to required and recommended readings (papers and occasional book chapters), or hard copies when appropriate, will be made available to students as the semester progresses. Click here for the readings page; this page will be updated throughout the semester.

Scribe Notes

Scribe notes will be posted here as they are available.

Academic Honesty Policy

By taking the course, students are presumed to consent to the Computer Science departmental policy on academic honesty. This policy has been passed by the faculty of the Department and approved by the school deans. The policy will be enforced for all courses, including this one. You can find the text of the policy at For this course in particular, students should be sure to provide appropriate citations for all sources used in their project reports and scribe notes.