Lectures and reading

Resources for typing notes: def.tex scribe template file

Lecture 1: Introduction to learning theory

State of TML, Examples of ML problems, Statistical and Computational Learning models

Reading: chapters 1-2 in book 3, Alan Turing's paper on AI: https://www.csee.umbc.edu/courses/471/papers/turing.pdf

Lecture notes: notes

Lecture 2: Statistical learning theory

Review of basic definitions of statistical learning, agnostic statistical learnability of finite hypothesis classes and proof

Reading: chapters 3-4 in Shalev-Schwartz book

Lecture notes: notes

Lecture 3: More on statistical learning theory

Infinite hypothesis classes, discretization trick. Start of computational learning theory and efficient methods.

Reading: chapters 3-6 in Shalev-Schwartz book

Lecture notes: notes

Lecture 4: From statistical to computational learning

The online learning mode, multiplicative updates, weighted majority, randomized weighted majority, regret

Reading: chapter 1 in book 1

Lecture notes: notes

Lecture 5: HW solutions session (w. Nataly & Edgar)

Lecture 6: Online convex optimization

Regret minimization in continuous models, modeling power of convex relaxation, online shortest paths,

the Hedge algorithm, intro to convex analysis

Reading: chapter 1,2 in book 1, lectures on optimization

Lecture 7: Online gradient descent

Online gradient descent and its regret bound, application to online shortest paths for a surprising routing algorithm.

Examples of other applications: online spam filtering, online ranking, production

Reading: chapter 3 in Hazan book, lectures on optimization

Lecture 8: Strong convexity, log regret and fast rates

reading: chapter 3 in Hazan book, lectures on optimization

Lecture 9: No class, Yom Kippur

Lecture 10: Second order methods

Universal portfolio selection, Cover's algorithm, Online Newton Step

Reading: Chapter 4 in book 1

Lecture 11: Online Newton's method, start Regularization

Cont. of Online Newton Step, the importance of regularization

Reading: Chapters 4,5 in book 1

Lecture 12: RFTL, Regularization, Adaptive Regularization

The RFTL meta-algorithm and its analysis, AdaGrad algorithm and its guarantee

Reading: Chapter 5 in book 1

Lecture 13: Recommendation systems, projection-free methods

The Frank-Wolfe algorithm, projections and their computational cost,

Reading: Chapter 7 in book 1

Lecture 14: Gradient Descent without a Gradient (Bandit Convex Opt.)

Reading: Chapter 6 in book 1

Lecture 15: HW solutions session (w. Nataly & Edgar)

Lecture 16: Game theory, duality, regret and equilibrium

Reading: Chapter 8 in book 1

Lecture 17: Boosting (Xinyi Chen)

Reading: these notes

Lecture 18: From Online to Statistical learning (Naman Agarwal)

Reading: Chapter 9 in book 1

Lecture 19: Stability via randomization: follow-the-perturbed leader (Naman Agarwal)

Reading: Chapter 5.5 in book 1

Lecture 20: Introduction to Reinforcement Learning

Lecture notes: notes

Lecture 21: Function approximation and policy gradient methods

Lecture notes: notes

Lecture 22: Model-based RL and control

Lecture notes: notes

Lecture 23: Ask me anything!