Spring 2019: CS 6501 - Learning Theory

Table of Contents

Course Description

Learning theory is a field that develops models for capturing learning phenomena and ultimately studies the efficiency and the limitations of learning algorithms in these frameworks. We will explore basic aspects of machine learning theory.

We will start with learning algorithms that use membership and equivalence queries, version spaces, and decision trees. We will then switch to the probably approximately correct (PAC) model of learning, Occam's razor, VC theory, and ultimately prove the fundamental theorem of learning theory.

From this point and on, we will cover, not necessarily in this order, the following topics. The relationship between weak and strong learning (boosting). Online learning and learning with expert advice in the mistake bound model, where we will see algorithms such as randomized halving, weighted majority, and winnow. We will also cover aspects of adversarial machine learning (poisoning and evasion attacks) and thus explore connections between machine learning and security.

Time permitting, there are further ideas for related interesting topics. For example, theoretical aspects of learning that are related to evolution and evolution seen as a learning process drawing results from evolutionary algorithms and Valiant's framework of evolvability, or active learning.

[Course Description] [Table of Contents] [Top]

Basic Information


The syllabus is available here.

Time and Location

Mondays, Wednesdays, and Fridays 1:00pm – 1:50pm, Olsson Hall 009.

Contact Information

Please see here.

Teaching Assistants

The graduate student Suya (fs5xz) will be a TA for this class this year.

Office Hours

We have office hours at the following times and places.

11:00am – 1:00pm, 414 Rice Hall (Dimitris)
2:00pm – 4:00pm, 414 Rice Hall (Dimitris)
2:00pm – 6:00pm, 436 Rice Hall (Suya)
Exceptions to the Regular Schedule of Office Hours

If you want to meet us outside of our office hours, the most reliable method is to send an email and arrange an appointment.

[Basic Information] [Table of Contents] [Top]

Homework Assignments

Assignment 1: Here. Announced on January 16. Due on January 30.

[Homework Assignments] [Table of Contents] [Top]

Final Projects

Graduate students should deliver a final project. This is optional for undergraduates.

In general I am open to discussion for various ideas regarding the final project. The route that I expect most people will take, is to form a group of 3-5 people, read a research paper and write a summary that will be about two pages long (11pt) and be distributed to the rest of their students in class. Depending on our pace as well as on the number of different groups of students that are formed for a final project we may or may not have oral presentations of these research papers. Another idea is for a group of people to implement a library with some algorithms that we saw in class and potentially run some experiments for that library. There are some other ideas; for example one can implement Shannon's mind reading machine. More information, as well as papers that people can choose from, will be provided soon.

Candidate Material


[Final Projects] [Table of Contents] [Top]

Learning Theory Class Resources

[Learning Theory Class Resources] [Table of Contents] [Top]

Assigned Readings

[Assigned Readings] [Table of Contents] [Top]

Optional Readings

[Optional Readings] [Table of Contents] [Top]

Additional Resources

[Additional Resources] [Table of Contents] [Top]

Class Log

Class 1 (Jan 14, 2019)

Introduction. Overview of the course by going through the syllabus.

Discuss the Coupon Collector's problem as an example of the kind of problems that we will be looking at in later parts of the course.

Discussion on basic terminology about machine learning.

Perhaps a good idea is to review Sections 1–2.4 (up to the weak law of large numbers) from the document Essentials on the Analysis of Randomized Algorithms. Also, have a look at Section 3 which discusses the Coupon Collector's problem.

For a general review on probability theory as well as a basic technique for proving bounds in randomized algorithms (which thus applies to learning theory as well), please have a look at the document Basic Tools and Techniques for Algorithms in Learning Theory.

Finally, the document Tools for Bounding Probabilities discusses bounds that we will use more frequently.

Assigned reading: The above three documents.

Class 2 (Jan 16, 2019)

Homework 1 announced. Due on Wed, Jan 30.

Terminology and basic notions in machine learning: hypothesis class (hypothesis space), concept class, hypothesis, concept (ground truth), instances, examples, symmetric difference.

Boolean functions and the class of functions that will be the workhorse for our course: conjunctions and monotone conjunctions.

Started the discussion of queries and concept learning from Dana Angluin's paper Queries and Concept Learning.

Class 3 (Jan 18, 2019)

We discussed the learnability of monotone conjunctions using equivalence and membership queries. We also discussed whether the algorithms extend to general conjunctions.

Here are notes from what was discussed in the class.

Monday, January 21, 2019

Martin Luther King day – no classes.

Class 4 (Jan 23, 2019)


Class 5 (Jan 25, 2019)


Class 6 (Jan 28, 2019)


Class 7 (Jan 30, 2019)


Class 8 (Feb 1, 2019)


Class 9 (Feb 4, 2019)


Class 10 (Feb 6, 2019)


Class 11 (Feb 8, 2019)


Class 12 (Feb 11, 2019)


Class 13 (Feb 13, 2019)


Class 14 (Feb 15, 2019)


Class 15 (Feb 18, 2019)


Class 16 (Feb 20, 2019)


Class 17 (Feb 22, 2019)


Class 18 (Feb 25, 2019)


Class 19 (Feb 27, 2019)


Class 20 (Mar 1, 2019)


Class 21 (Mar 4, 2019)


Class 22 (Mar 6, 2019)


Class 23 (Mar 8, 2019)


Monday, March 11, 2019

No class; Spring recess.

Wednesday, March 13, 2019

No class; Spring recess.

Friday, March 15, 2019

No class; Spring recess.

Class 24 (Mar 18, 2019)


Class 25 (Mar 20, 2019)


Class 26 (Mar 22, 2019)


Class 27 (Mar 25, 2019)


Class 28 (Mar 27, 2019)


Class 29 (Mar 29, 2019)


Class 30 (Apr 1, 2019)


Class 31 (Apr 3, 2019)


Class 32 (Apr 5, 2019)


Class 33 (Apr 8, 2019)


Class 34 (Apr 10, 2019)


Class 35 (Apr 12, 2019)


Class 36 (Apr 15, 2019)


Class 37 (Apr 17, 2019)


Class 38 (Apr 19, 2019)


Class 39 (Apr 22, 2019)


Class 40 (Apr 24, 2019)


Class 41 (Apr 26, 2019)


Class 42 (Apr 29, 2019)


Friday, May 3, 2019; 9:00am – 12:00pm

Final exam in Olsson Hall 009.

[Class Log] [Table of Contents] [Top]