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. This year we will focus on learning with state and decision making. 

Course 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, learning and control in dynamical systems.

Textbook and readings

Textbooks: 

Extra reading: 

Turing's paper on intelligence and the imitation game 

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

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

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

6. Reinforcement Learning: Theory and Algorithms (draft), by Alekh Agarwal, Nan Jiang, Sham M. Kakade

7. Introduction to Convex Geometry by Keith Ball 

Lecture notes from related courses: 

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

2. Lecture Notes on modern convex optimization, by A. Ben-Tal and A. Nemirovski, available here 

Mathematical background notes 

Notes by Ted Summers from previous years on background for students that have not taken the complete math requirements: 

notes on convex optimization and analysis  ;  part 2 of these notes  

Administrative Information

Lectures:  Tue, Thu, 13:30-15:00 in Friend center 006 

Professor: Elad Hazan, CS building 409, Office hours:  after class, or by appointment.

Teaching Assistants: 
Zhou Lu, Office hours:  Mon 1-2pm (COS 242)

Eshaan Nichani, Office hours: Wed 4-5pm  (Friend Center 010A)
 

Discussion channel: please see the canvas system for this course, which has an Ed channel.  

Requirements: This is a graduate-level proof-based 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. Food is not allowed, but hot/cold beverages are allowed.  

Grading and collaboration

Grading: homework assignments (60%), class participation (10%), and a final take home exam (30%). There will be 2-6 homework assignments, which will be roughly equally spaced, and will each consist of a small number of problems (optional programming). Credit for all assignments is the same.
Note this is a graduate level class, grading criteria and assignments can be changed at any time. 

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: Compulsory for this year, details TBD in class. 

Collaboration: Collaboration on the problem sets is allowed and unrestricted. 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.
LLM: using AI in any form is allowed for exercises and not allowed for the final exam.