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
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.
Next:
- All about convexity.
- Convex optimization; online convex optimization.
- Follow the regularized leader (FTRL).
- Littlestone dimension; online learnability.
- Zero-sum games.
- Boosting.