General Information

Instructor: Rocco Servedio (517 CSC, office hours Wed 12:30-2:30). Email: rocco at cs dot columbia dot edu.
TA: Homin Lee (email: homin at cs dot columbia dot edu.)
Room: 253 Engineering Terrace
Time: Thurs 4:10-6:00pm

COMS E6253 is an advanced graduate course on efficient algorithms in computational learning theory. The course can be used as a theory elective for the Ph.D. program in computer science, as an 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" rack. Auditing the class requires the approval of the instructor. CVN students should contact the instructor before registering for the class.

Motivation

There is no single "right way" to model a complex phenomenon such as learning from a theoretical point of view. In this course we will cover several different models of learning: these will include online learning, learning from uniformly distributed random examples (the "uniform distribution PAC learning model"), and exact learning from queries. For each of these models we will study efficient algorithms for learning decision trees, Boolean formulas in Disjunctive Normal Form, intersections of halfspaces, and other interesting classes of functions.

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

The course will be roughly divided into three main units corresponding to three different learning models. As we will see, each of these models has its own "flavor" and set of techniques that are useful for designing efficient learning algorithms in that model. These models are the online mistake-bound model, the model of learning from uniform random examples, and the model of exact learning from membership and equivalence queries. Depending on time and student interest, there may be a fourth unit on state-of-the-art algorithms for learning in the presence of noise.

First unit: online mistake bound learning.

• Review of the online mistake-bound learning model and its connection to PAC learning.
• Learning decision trees in quasipolynomial time. Rank arguments.
• Learning halfspaces efficiently in the online mistake-bound model via convex optimization.
• Polynomial threshold functions (PTFs) and their connection to efficient online learning. Bounds on PTF degree.
• Learning DNF formulas in subexponential time via PTFs. Extremal polynomials and their application to PTF degree.
• Learning intersections of halfspaces in quasipolynomial time via PTFs. Rational functions and their application to PTF degree.
• Hardness results based on cryptography.

Second unit: learning from uniform random examples over {0,1}^n.

• Introduction to the model.
• Fourier analysis over the Boolean cube. The low-degree algorithm.
• Learning constant-depth circuits in quasipolynomial time.
• Learning decision trees in polynomial time with queries.
• The "discriminator lemma" and boosting.
• Application of boosting and the discriminator lemma: learning threshold-of-parities and DNF formulas in polynomial time with queries.
• Application of boosting and discriminator lemma: learning augmented constant-depth circuits in quasipolynomial time.
• Lower bounds for Statistical Query learning.

Unit #3: exact learning from membership and equivalence queries:

• Introduction to the model. Learning monotone DNF in polynomial time.
• Learning deterministic finite automata (DFAs) in polynomial time.
• Application of learning DFAs: learning log(n)-term DNF in polynomial time.
• Application of learning DFAs: learning intersections of halfspaces in polynomial time.
• The monotone theory: learning decision trees in polynomial time.
• Learning polynomials (interpolation).

• Learning parities in the presence of noise.
• Learning low-weight linear threshold functions in the presence of malicious noise by smooth boosting.
• Learning low-weight linear threshold functions in the presence of random classification noise by branching-program boosting.

Class Requirements

• Class participation: Students are expected to come to lecture and to participate (questions are encouraged!). CVN students who cannot physically attend class are expected to participate by email discussion with the instructor; contact the instructor for more details.
• Scribe notes: Each student will prepare scribe notes for one or more lectures during the semester. This should be a clear and readable exposition of the material covered in that lecture. I will provide a template and will give you feedback on your notes. You are encouraged to use outside sources (in particular, relevant papers) to make your notes as good as possible.
• 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 on projects in groups of up to three.
  The project is your chance to become an expert on some particular problem that interests you and hopefully contribute to what is known on this topic. In the first phase of the project, you will pick a general area and become familiar with the relevant literature. Then you will identify a specific research question or direction which you will investigate. Ideally, your project will lead to a new publishable research result in the topic you pursue, but this is not necessary in order to do a successful project.
  You will turn in a project proposal fairly early in the semester to identify the general area of your project, a progress report later in the semester, and ultimately a final report. I will work with you and give you feedback at each of these stages. Your final report should give a clear, self-contained exposition of what you have learned about your topic; it should also explain explain the specific 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.
• Class Presentation: Each student will give a brief presentation in class of their final project. CVN students should contact me and we will make suitable arrangements for your presentation.

Readings

Here are scribe notes for: