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.

Motivation

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.

Prerequisites

List of Topics

First unit: PAC learning.

• PAC learning algorithms via PTF degree upper bounds. Learning decision trees in quasipolynomial time.
• Extremal polynomials and learning DNF in subexponential time.
• Rational functions and learning intersections (and general functions) of low-weight halfspaces in quasipolynomial time.

Second unit: Uniform-distribution PAC learning.

• Fourier analysis over the Boolean cube. The low-degree algorithm. Influence of variables. Learning monotone functions in subexponential time.
• Learning constant-depth circuits in quasipolynomial time.
• Noise sensitivity and learning intersections (and general functions) of halfspaces in polynomial time.
• Learning juntas faster than exhaustive search.
• Learning with membership queries. Learning decision trees in polynomial time.
• The "discriminator lemma" and boosting. Application of boosting and the discriminator lemma: learning threshold-of-parities and DNF formulas in polynomial time.

Third unit: Learning with noise / agnostic learning.

• Learning parity functions in the presence of random classification noise in subexponential time.
• Agnostic learning via the L_1 regression algorithm. Agnostically learning disjunctions and halfspaces.
• Connections between the noisy parity learning problem and other challenging learning problems.

Class Requirements

• Class participation: Students are expected to come to lecture and to participate (questions are encouraged!).

• Scribe notes: Each student will prepare scribe notes for one or more lectures during the semester. This should be a clear, detailed and readable exposition of the material covered in that lecture. You are encouraged to use outside sources (in particular, relevant papers) to make your notes as good as possible. A template will be provided.

• In-class problems: At various points in the class lectures I will designate certain questions/lemmas as "in-class problems." These will be problems or lemmas that I will state but not solve/prove in class. You are to choose one of these in-class problems at some point in the semester and turn in a clear, detailed, self-contained solution to the problem.

• Project: Each student will complete a research project on a topic in computational learning theory of your choice. Students can do solo projects or can work in teams of two.

  The project is your chance to become an expert on some particular learning problem that interests you (and is closely aligned with the flavor of the course), and hopefully to contribute to what is known about this topic. You will turn in a project proposal fairly early in the semester to identify the general area of your project, and ultimately a final report as described below.

  There are two aspects to the final project. The first is a literature review: this will involve identifying the relevant literature on your topic (typically one or two research papers), closely reading and understanding this literature, and writing up a presentation of the results you have learned in your own words. You are encouraged to use the scribe notes template for this portion of your project.

  The second aspect of the project is to identify a specific research question or direction on your chosen topic, think about it, and write up the results of your research. Ideally, your project will result in some research progress that could lead to a new publishable research result in the topic you pursue, but this is not a course requirement. All that you need to do for this portion of the project to be successful is come up with a research question/direction and give evidence of having made a real attempt to attack it.

  So to summarize the project requirements, your final project submission should (1) give a clear, self-contained exposition of what you have learned about your chosen topic -- as mentioned above, the class scribe notes format is fine for this portion; and (2) it should also explain explain the specific research problem you investigated, what you did to try to solve this problem, and what progress you made.

  Click here to get to the projects page, which lists some possible project topics.

• Class Presentation: Each student will give a brief presentation in class on his or her final project, and will distribute the scribe notes portion of his/her project to the class.

Readings

Scribe Notes

Academic Honesty Policy