Introduction to Computational Learning Theory
General Information |
Introduction | Topics |
| Grading | Readings
| Problem Sets
| Final Projects
| Schedule of Topics
| Lecture Notes
Instructor: Rocco Servedio.
Office: 517 CSB. Office hours: Fri 10-12.
Time: Tues/Thurs 8:40-9:55.
Course website (this page): http://www.cs.columbia.edu/~cs4252/
Course email (use for all course-related issues):
coms4252columbia2015 at gmail dot com.
The question "Can machines think?"
is one that has fascinated people for a long time;
for a non-technical perspective (you may need to be on the Columbia
network to access this resource). This is pretty close
to the question "Can machines learn?",
which has been studied from different points of view
by many researchers in computer science.
This course will give an introduction to some of the central
topics in computational learning theory, a field
which approaches the above question from a theoretical computer science
perspective. We will study
well-defined mathematical and computational
models of learning in which it is possible
to give precise and rigorous analyses of learning problems and
A big focus of the course will be the computational efficiency
of learning in these models. We'll develop computationally
efficient algorithms for certain learning problems, and will see
why efficient algorithms are not likely to exist for other
List of Topics
This is a preliminary list of core topics.
Other topics may be covered depending on how
the semester progresses. Most topics will take several lectures.
Introduction: what is computational learning theory (and why)?
Basic notions (learning models, concept classes).
The online mistake-bound learning model. Online algorithms for simple
learning problems (elimination, Perceptron, Winnow)
General algorithms and lower bounds for online learning
(halving algorithm, Weighted Majority algorithm, VC dimension)
The Probably Approximately Correct (PAC) learning model: definition
and examples. Online to PAC conversions.
- Occam's Razor: learning by finding a consistent hypothesis.
The VC dimension and uniform convergence.
Weak versus strong learning: boosting algorithms.
Computational hardness results for efficient learning based on cryptography.
PAC learning from noisy data. Malicious noise and
random classification noise. Learning from Statistical Queries.
Exact learning from membership and equivalence queries.
Learning monotone DNF and learning finite automata.
You should be familiar with the following topics:
Important: Big-O notation and basic analysis of algorithms.
Chapter 3 in "Introduction to Algorithms" by
Cormen, Leicerson, Rivest and Stein is sufficient background.
Important: Basic discrete math and probability. The course
Computer Science 3203 and the "Mathematical Background" section
(Appendix VIII) of CLRS are good sources here.
Important: You should be comfortable with
reading and writing proofs. You will encounter many proofs in class and
will be doing proofs on problem sets.
Chapter 0 of Sipser's book "Introduction to the Theory of Computation"
is a good source here.
Less important but helpful:
Some basic knowledge of the theory of NP-completeness (e.g. Chapter 7 of
Sipser or Chapter 34 of CLRS) and of elementary cryptography
(e.g. pages 881-887 of CLRS) would be helpful, but this knowledge
is not required --
the course will be self-contained with respect to these topics.
Grading and Requirements
The requirements of the course are as follows:
Biweekly problem sets (70% of grade). Your solutions must be typed
and prepared as LaTeX documents
(instructions will be given on how to use LaTeX.)
The biweekly problem sets will be due on Thursdays by 8:40am (start of class);
you must bring a hard copy to class and give it to the TA, and
also turn in an electronic copy to the course account coms4252columbia2015.
You are allowed a total of six late days for the semester.
Each late day is exactly 24 hours; late days
cannot be subdivided -- five minutes late counts as one late day.
Note also that problem sets cannot be subdivided with respect to late days
(i.e. you cannot use 1/6 of a late day on a 6-problem problem set by
handing in one problem one day late).
Late days over and beyond the allotted six late days will be
penalized at a rate of 10% of the initial grade per late day
(with the same system in place;
five minutes late for one problem counts as one late day for the entire set),
thus a problem set which is four days late would receive 60% of the points
that it would have received had it been turned in on time.
No problem sets will be accepted after two weeks have elapsed from
the initial due date. For
you must have your undergraduate advisor (for undergrads) or your
graduate advisor (for graduate students) contact me.
will be challenging; you are advised to start the problem
Final project (15% of grade).
For your final project, you will choose a research paper in computational
learning theory, read it, and submit a written report giving a clear
and coherent exposition in your own words of what you learned from
The paper can either be on some topic we touched on in class where you
want to learn the topic in more depth and detail, or on a CLT topic that
we didn't get to in class but you are interested in.
Final Projects will be due on Thursday, December 17;
more details are available on the
In-class evaluation (15% of grade). There will be an in-class
evaluation on the last day of class, Thursday, December 10.
It will be closed-book and closed-note, and will be cumulative --
anything that was covered this semester is fair game. The best way
to prepare for the evaluation is to go over course notes, readings,
and homework problems and solution sets.
You are encouraged to discuss the course material and the homework
with each other in small groups (2-3 people), but you must list all
partners on your problem set.
Discussion of homework problems may include
brainstorming and verbally discussing possible solution approaches, but must
not go as far as one person telling the others how to solve the problem.
In addition, each person must write up her/his solutions
independently; you may not look at another student's written solutions.
You may consult outside materials, but all materials used must be
appropriately acknowledged, and you must always write up your
solutions in your own words.
Violation of any portion of this policy will result
in a penalty to be assessed at the instructor's discretion. This may include
receiving a zero grade for the assignment in question AND a failing grade
for the whole course, even for the first infraction.
Students are expected to adhere to the Academic Honesty policy of the
Computer Science Department; this policy can be found in full
Please contact the instructor with any questions.
If you dispute the grade received for an assignment, you must
submit, in writing, a detailed and clearly stated
argument for what you believe is incorrect and why. This must be submitted
no later than the beginning of class 1 week after the assignment was returned.
(For example, if the assignment were returned to the class on Tuesday, your
regrade request would have to be submitted before the start of class
on the next Tuesday).
Requests for a re-grade after this time will not be accepted.
A written response will be
provided within one week indicating your final score.
Requests of re-grade of a specific problem may result in a regrade of
the entire assignment. This re-grade and written response is final.
Keep in mind that a re-grade request may result in the overall score
for an assignment being lowered.
"I therefore perused this Sheet with wonderful
Application, and in about a Day's time discovered that I could not
understand it." -- Henry Fielding, A Journey from This
World to the Next
The textbook for this course is:
This book is available for purchase on-line.
It's also available on reserve in the science and engineering
library, and is electronically available through the Columbia library
here (you will need to be signed in to access this).
Note that several topics which we'll cover
(particularly early in the semester) are not in the book.
A good source for material which we will cover in the first few weeks
of class are the following two papers:
- Avrim Blum's survey paper
"Online Algorithms in Machine Learning"
This has an overview of the online mistake-bound learning model, the Weighted
Majority algorithm, the online decision list learning algorithm, and much
- There are countless online sources where you can find expositions of the
Perceptron algorithm and proofs of convergence. The language tends to
vary from presentation to presentation; one which hews fairly closely
to the presentation we'll give in class can be found
A handy overview of Chernoff and Hoeffding bounds can be found
here (thanks to Clement Canonne for
For the unit on boosting, a good reference is Rob Schapire's survey paper
"The Boosting approach to machine learning: An overview".
The first three sections give a (very condensed) treatment of the
AdaBoost algorithm we'll cover in class, and later sections have good
overviews of more advanced material (this is a good starting point
for a project on boosting). Of course, the original paper on
Adaboost, "A decision-theoretic generalization of on-line learning and
an application to boosting", is a good sources as well.
Click here for a handy copy of the AdaBoost
Click here to get to the homework page.
Here is an anticipated schedule of topics. Note that the ordering
of some topics may change, and we may spend more or less than one lecture per