Comp 236: Computational Learning Theory
Department of Computer Science
Tufts University
Fall 2015

  • (8/31) Pages under construction. Initial information posted below. We will follow a similar pattern to COMP 236 Spring 2013

What is this course about? Machine learning algorithms aim to "make sense of data", often developing some generalizations that are useful for future tasks, for example in classification, prediction, and control. Machine learning has matured and expanded over the last two decades and is now used extensively as a tool in many application areas. Increasingly, theory and analysis are used to guide the development of successful algorithms and systems.
Computational Learning Theory investigates such tasks and algorithms in a formal framework. The focus is to identify performance guarantees for algorithms in terms of computational complexity (how long it takes to run), data complexity (how much data is required), and convergence properties (how well does the result/output of the learning algorithm perform). Alternatively, when such guarantees do not exist, we might aim to show that learning is impossible by proving lower bounds on the amount of resources for any potential algorithm. Models vary from adversarial worst case scenarios, to statistical settings where a random process generates the data, and to interactive settings where the learner can control the flow of data.
The course will mix taught classes with seminar type reading of research papers of recent topics.

Syllabus: Probabilistic and adversarial models of machine learning. Development and analysis of machine learning principles and algorithms, their computational complexity, data complexity and convergence properties. Computational and cryptographic limitations on algorithms for machine learning. Core results and recent developments in this field.
Prerequisites: COMP 160; EE 104 or MATH 162; COMP 170 recommended but not required. Or permission of instructor.
Times and Location: (D+ Block) TR 10:30-11:45, Lane Hall 100A
Instructor: Roni Khardon
Office: Halligan 230
Office Hours: TBA
Phone: 1-617-627-5290

Activities & Grading


Policy on collaboration on homework assignments: You may discuss the problems and general ideas about their solutions with other students, and similarly you may consult other textbooks or the web. However, you must work out the details on your own and write the solution on your own. Every such collaboration (either getting help of giving help) and every use of text or electronic sources must be clearly cited and acknowledged in the submitted homework. Failure to follow these guidelines will result in disciplinary action for all parties involved. Any questions? for this and other issues concerning academic integrity please consult the booklet available from the office of the Dean of Student Affairs.


We will sample from different sources including some of the texts below (on reserve in library) and research and survey articles.

Schedule and Assignments

Type What Due Date
Lecture 1 Introduction to CLT