COMS 4252

Introduction to Computational Learning Theory

Introduction

The question "Can machines think?" is one that has fascinated people for a long time (see here for an amusing non-technical perspective on this question by E.B. White). 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.


Quick Links

  • Courseworks: Has links to a range of resources including the Video Library (for course videos), the Ed Discussion board, and Gradescope.
  • Ed Discussion: Forum for asking questions about course material and homework assignments.
  • Gradescope: Submit assignments and view grades here. (You can set up Gradescope clicking the "Gradescope" module on Courseworks.)

General Information

Instructor: Rocco Servedio

Instruction modality: On campus, in Computer Science Building room 451; however, lectures will be recorded and recordings will be made available to all enrolled students through Courseworks.

Time: Mon/Wed 8:40am-9:55am Eastern Time

Course email (for administrative issues; use Ed Discussion for subject matter questions): coms4252columbiaf21 at gmail dot com


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. For more information, click on the "Lectures" tab above.

  • 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. Relation to computationally efficient learning.
  • The VC dimension and uniform convergence.
  • Weak versus strong learning: accuracy boosting algorithms.
  • PAC learning from noisy data. Malicious noise and random classification noise. Learning from Statistical Queries.
  • Computational hardness results for efficient learning based on cryptography.
  • Exact learning from membership and equivalence queries. Learning monotone DNF and learning finite automata.