TTIC 31120: Computational and Statistical Learning Theory

This is a webpage for the Winter 2011 course "Computational and Statistical Learning Theory", taught at TTIC, and also open to all University of Chicago students.

Lectures: Monday and Wednesday 3-4:30pm at TTIC 530 (located at 6045 S. Kenwood Ave, fifth floor).

Instructor: Nati Srebro.
TA: Karthik Sridharan.

Course Description

We will discuss classic results and recent advances in statistical learning theory (mostly under the agnostic PAC model), touch on computational learning theory, and also explore the relationship with stochastic optimization, the oracle model of optimization, and online regret analysis. Our emphasis will be on developing a rigorous quantitative understanding of machine learning and acquiring techniques for analyzing and proving performance guarantees for learning methods.


Familiarity with Convex Optimization, Computational Complexity and background in Statistics can be helpful, but is not required.

Specific Topics:

We will try to touch

Requirements and Grading:

In order to receive a "B" a student is expected to complete the exercises, do a good job at scribing a lecture and display reasonable understanding on the quiz.
In order to receive an "A" a student is expected to complete the exercises, do a very good job scribing a lecture, successfully answer at least 1-2 Challenge Problems and present them to the instructor satisfactorily.

Lectures and Required Reading:

Lecture 1: Monday January 3rd
Required Reading: Section 1 of: S. Boucheron, O. Bousquet, and G. Lugosi, (2004), Concentration inequalities, Advanced Lectures in Machine Learning, Springer, pp. 208--240, 2004 Alternative reading : Lecture notes
Homework 1 out (due 5th Jan, 2010 (preferable), ultimate deadline 10th Jan, 2010)
Lecture 2: Wednesday January 5th
Lecture 4: Monday January 10th
Lecture 5: Wednesday January 13th
No Lecture on Monday January 17th (MLK Day)
Lecture 6: Wednesday January 19th, given by Karthik Homework 2 out (due January 31st)
Lecture 7: Monday January 24th
Lecture 8: Wednesday January 26th
Lecture 9: Monday January 31st Homework 3 out (due 16th Feb, 2011)
Homework 4 out (due 2nd March, 2011)
Homework 5 out (due 16th March, 2011)


Last modified: Thu Jan 27 15:09:06 Central Standard Time 2011