Advanced Topics in Computational Learning Theory
General Information |
Class Requirements |
Scribe Notes |
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)
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
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
may enroll with the instructor's permission; contact me if you have
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
- 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
The requirements of the course are as follows:
Students are expected to come to lecture and to participate (questions
- 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
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.
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 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.