CS7545-Machine Learning Theory, Fall 2018

Georgia Tech

Course Information

Course Description

This course will study theoretical aspects of prediction and decision-making problems, 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 inqualities, 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 Friday, December 7, from 2:40-5:30pm.

References:

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 releaseSd 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 20 Aug 2018 Introduction and norms
2 22 Aug 2018 Convex analysis
3 27 Aug 2018 Convex Analysis + Deviation Bounds
4 29 Aug 2018 Concentration Inequalities
5 05 Sep 2018 Martingales + Online Learning
6 10 Sep 2018 Multiplicative Weights
7 12 Sep 2018 EWA + Perceptron
8 17 Sep 2018 Perceptron + Game Theory
9 19 Sep 2018 Zero-sum Games + Boosting
10 26 Sep 2018 Boosting + Online Convex Optimization
11 01 Oct 2018 Online Convex Optimization
12 03 Oct 2018 Online Convex Optimization (Cont.)
13 10 Oct 2018 FTRL
14 15 Oct 2018 Multi-armed Bandits
15 17 Oct 2018 Stochastic Multi-Armed Bandits
16 22 Oct 2018 UCB algorithm
17 24 Oct 2018 Statistical Learning Theory
18 29 Oct 2018 Contextual Bandits
19 31 Oct 2018 Reinforcement Learning
20 05 Nov 2018 VC Dimension + Rademacher Complexity
21 07 Nov 2018 Growth Function and Massart’s Lemma
22 12 Nov 2018 Massart’s Lemma and Sauer’s Lemma
23 14 Nov 2018 VC-Dimension Upper & Lower Bounds
24 19 Nov 2018 Generalization Error + Margin Theory
25 26 Nov 2018 VC Dimension of Neural Networks
26 28 Nov 2018 Variational inference

The Latex template for scribes is available here.

Homeworks

Homework Due Date
1 Sep 10 2018, 2:00 pm
2 Sep 24 2018, 2:00 pm
3 Oct 17 2018, 2:00 pm
4 Nov 16 2018, 4:00 pm
5 Dec 2 2018, 11:59 pm

The Latex template for HW submissions is available here.