COMS 4252: Introduction to Computational Learning Theory
Fall 2018


General Information | Introduction | Topics | Prerequisites | Grading, Requirements, and Academic Honesty | Readings | Problem Sets | Schedule of Topics | Link to Courseworks/Piazza | Notes from Lectures | Schedule of Deadlines

General Information

Instructor: Rocco Servedio. Office: CSB 450 (computer science department chair's office). Office hours: Fri 9-11
Instructional assistants: Emmanouil Vasileios Vlatakis Gkaragkounis, Sandip Sinha, Steven Shao. Emmanouil's OH: Tues 1-3pm in CSB 516. Sandip's OH: Thurs 4:30-6:30pm in TA room on 1st floor of Mudd. Steven's OH: Wed 12:30-2:30pm in TA room on 1st floor of Mudd.
Classroom: 451 Computer Science Building
Time: Tues/Thurs 8:40-9:55
Course website (this page):
Course email (use to contact teaching staff about any administrative issues): coms4252columbia2018 at gmail dot com


The question "Can machines think?" is one that has fascinated people for a long time; see here 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 learning algorithms. 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 problems.

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.


You should be familiar with the following topics:

Grading, Requirements and Academic Honesty

The requirements of the course are as follows:

Homework policy: You are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people), but you must list all discussion 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 writing up solutions together; each person MUST WRITE UP HIS/HER SOLUTIONS INDEPENDENTLY. You may not collaborate with another student on writing up solutions or even look at another student's written solutions. If your homework writeup resembles that of another student in a way which suggests that you have violated the above policy, you may be suspected of academic dishonesty.

You may consult certain outside materials, specifically lecture notes and videos of other classes, any textbooks, and research papers. You may not consult any other materials, including solved homework problems for this or any other class. For all outside materials used, you must provide a detailed acknowledgement of the precise materials used. Whether or not you consult outside materials, you must always write up your solutions in your own words. If your homework writeup resembles any outside source in a way which suggests that you have violated the above policy, you may be suspected of academic dishonesty.

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.

More generally, students are expected to adhere to the Academic Honesty policy of the Computer Science Department; this policy can be found in full here. Please contact the instructor with any questions.

Re-grade policy: 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.


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:

A handy overview of Chernoff and Hoeffding bounds can be found here (thanks to Clement Canonne for preparing this).

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 algorithm.


Lectures will often be cumulative, in the sense that most lectures will build on concepts and results that were covered in previous lectures; so if you fall significantly behind it can be difficult to catch up. You are advised to take careful notes during lectures and to review those notes between lectures.

Problem Sets

Click here to get to the homework page.

Schedule of Topics

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 topic.

Link to Courseworks/Piazza

Click here for Courseworks (from which you can access Piazza, the discussion forum for the class).

Notes from Lectures

You are strongly advised to take your own notes during lecture, and to cross-check them again these (unedited) notes of what was produced during class. Warning: the notes below were generated in real time and have not been edited. They may contain typos or other errors. They may also contain aesthetically displeasing color combinations.

  • Lecture #2, Thurs Sept 6 2018
  • Lecture #3, (scheduled for) Tues Sept 11 2018
  • Lecture #4, (scheduled for) Thurs Sept 13 2018 (The videos for Lectures 3 and 4 are available to anyone at Columbia at this link
  • Lecture #5, Tues Sept 18 2018
  • Lecture #6, Thurs Sept 20 2018
  • Lecture #7, Tues Sept 25 2018
  • Lecture #8, Thurs Sept 27 2018
  • Lecture #9, Tues Oct 2 2018
  • Lecture #10, Thurs Oct 4 2018
  • Lecture #11, (scheduled for) Tues Oct 9 2018
  • Lecture #12, Thurs Oct 11 2018
  • Lecture #13, Tues Oct 16 2018
  • Lecture #14, Tues Oct 23 2018
  • Lecture #15, Thurs Oct 25 2018
  • Lecture #16, Tues Oct 30 2018
  • Lecture #17, Thurs Nov 1 2018
  • Lecture #18, Thurs Nov 8 2018
  • Lecture #19, (scheduled for) Tues Nov 13 2018
  • Lecture #20, (scheduled for) Thurs Nov 18 2018
  • Lecture #21, Tues Nov 20 2018
  • Lecture #22, Tues Nov 27 2018
  • Lecture #23, Thurs Nov 29 2018
  • Lecture #24, Tues Dec 4 2018

    Schedule of Deadlines

    Click here for a handy overview of all course deadlines.