Spring 2018: 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. The course will start with the notions of concept learning and version spaces and proceed to decision tree learning and artificial neural networks. 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. We will examine the relationship between weak and strong learning (boosting). Subsequently, we will move on to 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 theoretical aspects of learning that are related to evolution and evolution seen as a learning process drawing results from evolutionary algorithms and Valiant's evolvability framework. (This part of the course related to evolution can also be seen as a special type of local search optimization with PAC guarantees.) Time permitting we will cover additional models of learning such as active learning, or the computational approach to evolution by Adi Livnat and Christos Papadimitriou.

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

Basic Information


The syllabus is available here.

Time and Location

Mondays and Wednesdays, 3:30pm – 4:45pm, 340 Rice Hall.

Contact Information

Please see here.

Office Hours

I hold my office hours at the following times and places.

2:00pm – 3:00pm, 436 Rice Hall
1:00pm – 2:00pm, 414 Rice Hall
Exceptions to the Regular Schedule of Office Hours

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

Friday, January 26, 2018: No office hours this day.

Friday, February 16, 2018: Office hours only between 1:00pm – 1:30pm.

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

Homework Assignments

Assignment 1: Here. Due on January 31.

Assignment 2: Here. Due on February 7.

Assignment 3: Here. Due on February 21.

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

Learning Theory Class Resources

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

Optional Readings

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

Class Log

Class 1 (Jan 17, 2018)

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 22, 2018)

Basic terminology on machine learning.

Definition of concept learning and introduction to terminology with the EnjoySport example.

Partial ordering of the hypothesis space (most general to most specific).

Algorithm Find-S; execution of Find-S on our toy example.

Class 3 (Jan 24, 2018)

Definition of version spaces.

List-Then-Eliminate algorithm and output on our toy example.

General and specific boundaries of version spaces.

Version space representation theorem.

Candidate Elimination algorithm. (Just stated the idea.)

Class 4 (Jan 29, 2018)

Execution of the Candidate Elimination algorithm on our toy example.

Related discussion on convergence (no noise and realizability assumption), queries that learners should request, the Halving algorithm, as well as using partially learned concepts in order to make predictions.

Class 5 (Jan 31, 2018)

Discussed the solution for Homework 1.

Decision tree learning.

Entropy, information gain, and the basic algorithm (ID3) for learning decision trees.

Partial execution of the algorithm on a toy example.

Searching the hypothesis space: characteristics and contrasting the search of ID3 with the search performed by the Candidate-Elimination algorithm.

Bias in decision tree learning and Occam's razor.

Definition of overfitting.

Class 6 (Feb 5, 2018)

Handling overfitting. Reduced-Error Pruning and Rule Post-Pruning.

Partitioning original examples to: training set, validation set, test set.

Handling continuous-valued attributes. One needs only to examine boundary points for ID3.

Introduction to neural networks and discussion on the geometry of solutions of a perceptron. (We did not even discuss the training rule.)

Class 7 (Feb 7, 2018)

Perceptron and the perceptron update rule.

Unthresholded linear unit and the delta rule.

Full gradient descent and stochastic gradient descent.

Neurons using the sigmoid function.

Class 8 (Feb 12, 2018)

Backpropagation and derivation of the update rules.

Momentum and discussion on convergence and local minima.

Class 9 (Feb 14, 2018)

Final remarks on neural networks.

No Free Lunch Theorems.

Class 10 (Feb 19, 2018)

Introduction to PAC learning.

PAC learning axis-aligned rectangles in 2D.

Class 11 (Feb 21, 2018)

Discussion on various aspects related to PAC learning. For example, discussing issues that arise for the representation of concepts or hypotheses. Proper vs representation independent learning ('improper' learning). Definition of agnostic PAC learning. Efficient (agnostic or not) PAC learnability.

Discussion on Find-S for properly learning conjunctions. We will prove PAC learnability next time.

Class 12 (Feb 26, 2018)


Class 13 (Feb 28, 2018)

In-class midterm.

Mar 5, 2018

No class. Spring break.

Mar 7, 2018

No class. Spring break.

Class 14 (Mar 12, 2018)


Class 15 (Mar 14, 2018)


Class 16 (Mar 19, 2018)


Class 17 (Mar 21, 2018)


Class 18 (Mar 26, 2018)


Class 19 (Mar 28, 2018)


Class 20 (Apr 2, 2018)


Class 21 (Apr 4, 2018)


Class 22 (Apr 9, 2018)


Class 23 (Apr 11, 2018)


Class 24 (Apr 16, 2018)


Class 25 (Apr 18, 2018)


Class 26 (Apr 23, 2018)


Class 27 (Apr 25, 2018)


Class 28 (Apr 30, 2018)


Class 29 (Thursday, May 3, 2018; 9:00am – 12:00pm)

In-class final exam.

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