Introduction to Computational Learning Theory (COMP SCI 639)

Fall 2020

This course will focus on developing the core concepts and techniques of computational learning theory. We will examine the inherent abilities and limitations of learning algorithms in well-defined learning models. Specifically, the course will focus on algorithmic problems in supervised learning. The goal of supervised learning is to infer a function from a set of labeled observations. We will study algorithms for learning Boolean functions from labeled examples in a number of models (including online mistake-bound learning, PAC learning, SQ learning, and learning with various types of noise).

Course Information


Mathematical maturity. Background in undergraduate algorithms.

Course Outline

Here is an outline of the course material:


Course Evaluation

Homework Assignments: There will be 4 homework assignments that will count for 60% of the grade. The assignments which will be proof-based, and are intended to be challenging. Collaboration and discussion among students is allowed, though students must write up their solutions independently.

Course Project: A part of the course (40% of the grade) is an independent project on a topic related to learning theory. Projects can be completed individually or in groups of two students.

The goal of the project is to become an expert in an area related to the class material, and potentially contribute to the state of the art. There are two aspects to the course project. The first is a literature review: Students must decide on a topic and a list of papers, understand these papers in depth, and write a survey presentation of the results in their own words. The second aspect is to identify a research problem/direction on the chosen topic, think about it, and describe the progress they make.

Students must consult with the instructor during the first half of the course for help in forming project teams, selecting a suitable project topic, and selecting a suitable set of research papers.

Students will be graded on the project proposal (5%), the progress report (5%), and the final report (30%).


The textbook for this course is:

An additional textbook (available online) we will use is: