Theory of Machine Learning, Spring 2021

CSCI 7000, APPM 5590, APPM 4490

University of Colorado, Boulder

Instructor: Bo Waggoner

Time: Tue/Thu 8:00am - 9:15am
Meets synchronously, remotely (BigBlueButton link is on Canvas page)

Office hours (on BigBlueButton, link in Canvas): Tuesday 9:15am - 10:30am; Thursday 4pm - 5pm

Course information and syllabus

Overview

Presents the underlying theory behind machine learning in proofs-based format. Answers fundamental questions about what learning means and what can be learned via formal models of statistical learning theory. Analyzes some important classes of machine learning methods. Specific topics may include the PAC framework, VC-dimension and Rademacher complexity. Recommended prerequisites: APPM 4440 and CSCI 5622.

The course will be similar to Prof. Stephen Becker's version.

Resources and Links

[SSS] Understanding Machine Learning by Shalev-Shwartz and Ben-David.
[Mohri] Foundations of Machine Learning by Mohri, Rostamizadeh, and Talwaker.
[OCO] Online Learning and Online Convex Optimization by Shalev-Shwartz.
[Hastie] The Elements of Statistical Learning by Hastie, Tibshirani, and Friedman.
[RW] Gaussian Processes for Machine Learning by Rasmussen and Williams.
[Murphy] Machine Learning: A Probabilistic Perspective by Murphy.
[SuttonBarto] Reinforcement Learning: An Introduction by Sutton and Barto.
Canvas page: https://canvas.colorado.edu/courses/71018.
Gradescope: https://www.gradescope.com/courses/239898.

Schedule

Thu, Jan 14: Intro, what is (theory of) ML? Estimating coin bias.
Reading:[SSS] Ch1 and Ch2 for next time.
HW: Sign up for Zulip.
Tue, Jan 19: Statistical learning setting, ERM, PAC setting. Papaya example from [SSS], axis-aligned rectangles.
Thu, Jan 21: PAC setting and variants; PAC-learnability of finite hypothesis classes.
Reading:[SSS] Ch3 and Ch4 for next time.
HW: homework 1 posted on Canvas, due Mon. Feb. 1 at 11:59pm to gradescope.
Tue, Jan 26: Uniform convergence, agnostic PAC learnability of finite classes.
Thu, Jan 28: Finish uniform convergence; begin bias-complexity tradeoff.
Reading:[SSS] Ch5 for next time.
Tue, Feb 2: Proof of no-free lunch theorem and bias-variance tradeoff.
Thu, Feb 4: Rademacher complexity.
Reading:[Mohri] Ch3.1 for next time.
HW: homework 2 posted on Canvas, due Mon. Feb. 15 at 11:59pm to gradescope.
Tue, Feb 9: More Rademacher complexity; generalization theorem.
Thu, Feb 11: Bounding RC using growth function; start VC-dimension.
Reading: [Mohri] Ch3.2, 3.3; [SSS] Ch6.
Tue, Feb 16: shattering, VC-dimension; bounding the growth function, Sauer's Lemma.
Thu, Feb 18: Sauer-Shelah and agnostic PAC-learnability of finite-VC classes; fundamental theorem of PAC learning; mention fat-shattering and pseudo-dimension; structural risk minimization.
Tue, Feb 23: Structural risk minimization; intro to online learning.
Thu, Feb 25: Online learning model; example settings; mistake-bounded learning; regret.
Reading: [OCO] Ch1, Ch2.

All about convexity.
Convex optimization; online convex optimization.
Follow the regularized leader (FTRL).
Littlestone dimension; online learnability.
Zero-sum games.
Boosting.