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 1012).
Email: rocco at cs dot columbia dot edu.
TA: LiYang Tan (office hours TBA; email liyang at cs dot etc)
Room: TBA
Time: Thurs 11:0012: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
We will study algorithms for learning Boolean functions from labeled examples.
Our focus will be on stateoftheart computationally efficient (or
as close to efficient as we know how to get) and provably correct
algorithms in welldefined 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 (distributionfree) 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, constantdepth 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 complexitytheoretic 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
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.
 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 lowweight
halfspaces in quasipolynomial time.
Second unit: Uniformdistribution PAC learning.
 Fourier analysis over the Boolean cube. The lowdegree algorithm.
Influence of variables.
Learning monotone functions in subexponential time.
 Learning constantdepth 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 thresholdofparities 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
The requirements of the course are as follows:

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.
 Inclass problems: At various points in the class
lectures I will designate certain questions/lemmas as "inclass problems."
These will be problems or lemmas that I will state but not solve/prove
in class. You are to choose one of these inclass problems
at some point in the semester and turn in a clear, detailed,
selfcontained 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, selfcontained 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
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
http://www.cs.columbia.edu/education/honesty.
For this course in particular, students should be sure to
provide appropriate citations for all sources used in their
project reports and scribe notes.