CS7545-Machine Learning Theory

Georgia Tech

Course Information

Course Description

This course will study theoretical aspects of prediction and decision-making probelms, where our goal is to understand the mathematical underpinnings of machine learning. A primary objective of the class is to bring students to the frontiers of research and to prepare students to publish in this area. The course will cover, among other things, concentration inequalities, uniform deviation bounds, Vapnik-Chervonenkis Theory, Rademacher Complexity, margin bounds, boosting, some theoretical aspects of deep learning, online learning theory, regret minimization, multi-armed bandit algorithms, and connections to convex optimization. Along the way, we may dive into several related topics, including minimax equilibrium in games, calibration, sequential portfolio selection, option pricing, and differential privacy.

Prerequisites: Familiarity with the analysis of algorithms, probabilistic analysis, and several similar topics. CS7641 (Machine Learning) will be quite helpful but not strictly necessary. The material is going to be about 90% “theory” and thus potential students must have a strong mathematical background. We shall rely heavily on techniques from calculus, probability, and convex analysis, but many tools will be presented in lecture.

Coursework: There will be 5 problem sets throughout the semester.

Grade Breakdown:

Note: The final exam will be held on Wednesday, December 11, from 2:40-5:30pm.


Roughly half of the course will follow material from the following text:

Much of the material in online learning (aka regret minimization) is of my own taste, and I will present these topics how I enjoy. But for students that want reading material on this topic, there are several surveys released in the last several years that explore several many that we shall cover. I will link to them here, and will mention them in various lectures when appropriate:

Scribe Notes

Lecture Date Topic
1 19 Aug 2019 Introduction and and Linear Algebra Review
2 21 Aug 2019 Convex Analysis
3 26 Aug 2019 Convex Analysis and Deviation Bounds
4 28 Aug 2019 Chernoff Bounds

The Latex template for scribes is available here.


Homework Due Date
1 Sep 8 2019, 11:59 pm
2 Sep 30 2019, 2:00 pm

The Latex template for HW submissions is available here.

Previous offerings of the course: Fall 2018