Theoretical Machine Learning

Course Description & Basic Information

Can the mechanism of learning be automated and implemented by a machine?

In this course we formally define and study various models that have been proposed for learning. The course will present and contrast the statistical, computational, game-theoretic and reinforcement models for learning. We will present and rigorously analyze some of the most successful algorithms in machine learning that are extensively used today. Likely topics include: intro to statistical learning theory and generalization error bounds; learning in adversarial settings and the on-line learning model; mathematical optimization in machine learning; learning with partial observability; control theory and reinforcement learning .

Textbook and readings


1. Introduction to Online Convex Optimization, by E. Hazan, available here

2. Prediction, Learning and Games, by N. Cesa-Bianchi and G. Lugosi

3. Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David

4. Boosting: Foundations and Algorithms, by R. E. Schapire and Y. Freund

5. Foundations of Machine Learning, by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar

6. Lecture Notes: Optimization for Machine Learning, by E. Hazan, available here

Previous courses with notes: course1 course2

Administrative Information

Lectures: Mon + Wed, 11:00-12:20 in COS building, room 105

Professor: Elad Hazan, CS building 409, Office hours: Mon+Wed 10:00-11:00, or by appointment.

Teaching Assistants:

Nataly Brukhim COS 217, office hours: Mon+Wed afternoon, 2-3pm

Edgar Minasyan COS 315, office hours: Tue+Thu afternoon, 2-3pm

Piazza channel:

Requirements: This is a graduate-level course that requires significant mathematical background.

Required background: probability, discrete math, calculus, analysis, linear algebra, algorithms and data structures, theory of computation / complexity theory

Recommended: linear programming, mathematical optimization, game theory

Attendance and the use of electronic devices: Attendance is expected at all lectures. The use of laptops and similar devices for note-taking is permitted.

Grading and collaboration

Grading: homework assignments (60%) and a final take home exam (40%). There will be 2-6 homework assignments, which will be given roughly every two to three weeks, and will each consist of a small number of problems (optional programming). Credit for all assignments is the same.

Additional credit is given for constructive participation in class and solution of occasional "bonus problems" presented in class. Points may be deducted for extensive no-show to class.

Turning in assignments and late policy: Coordinate submission of assignments with the TA. Every late day reduces the attainable credit for the exercise by 10%.

Scribe notes: These are optional, but are graded and give extra credit equal to one additional exercise. Every student that is interested will have the option of scribing.

Collaboration: Collaboration on the problem sets is allowed. Final exam is individual. The people you collaborated with on assignments should be clearly detailed: before the solution to each question, list all people that you collaborated with on that particular question.