Machine Learning Theory

CS 7545 -- Georgia Tech

View on GitHub

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
5 04 Sep 2019 Martingale and Online Learning Intro
6 09 Sep 2019 Weighted Majority Algorithm
7 11 Sep 2019 Exponential Weights Algorithm
8 16 Sep 2019 Perceptron and Game Theory Intro
9 18 Sep 2019 Game Theory and Boosting
10 23 Sep 2019 Boosting
11 25 Sep 2019 Online Convex Optimization
12 30 Sep 2019 Online Convex Optimization
13 2 Oct 2019 SGD and Mirror Descent
14 7 Oct 2019 Mirror Descent Continued
15 9 Oct 2019 FTRL, Multi-Armed Bandits, & EXP3
16 21 Oct 2019 EXP3 and Stochastic Bandits
17 23 Oct 2019 Stochastic Bandits & UCB
18 28 Oct 2019 UCB Algorithm
19 30 Oct 2019 Stochastic Learning Theory
20 04 Nov 2019 VC Dimension & Rademacher complexity
21 06 Nov 2019 Rademacher complexity & Massart’s Lemma
22 11 Nov 2019 Massart’s Lemma & Sauer’s Lemma
23 13 Nov 2019 Sauers’s Lemma & VC Dim bounds
24 18 Nov 2019 Generalization Bounds & Neural Network
25 20 Nov 2019 Reinforcement Learning
26 25 Nov 2019 Margin Theory

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
3 Oct 29 2019,11:59 pm
4 Nov 14 2019,11:59 pm
5 Dec 3 2019,11:59 pm

The Latex template for HW submissions is available here.

Previous offerings of the course: Fall 2018