CPSC 531H: Machine Learning Theory

2018-19 Winter Term 1

General Information

Course Website: http://www.cs.ubc.ca/~nickhar/F18-531

Lecture Time: Monday & Wednesday 12-1:30pm

Lecture Room: DMP 101

Instructor: Prof. Nicholas Harvey, X851, nickhar@cs.ubc.ca

· Office Hours: Tuesdays/Thursdays, by appointment.

TA: Chris Liaw, cvliaw@cs.ubc.ca.

This is a graduate course on some theoretical aspects of machine learning. The emphasis is on foundations and on results with rigorous proofs. The viewpoint is much more computational than statistical.

Syllabus

Assignments:

· Assignment 1

· Assignment 2

· Perhaps 4-5 over the term.

Projects

Rough plan of topics:

· Definitely: PAC learning, VC dimension, Perceptron, Multiplicative Weights, Online Learning, Stochastic Gradient Descent, Multiplicative Weight Methods, Boosting, Online Convex Optimization, Non-stochastic Bandits (Exp3), Stochastic Bandits (UCB)

· Likely: Deep Neural Networks

· Possibly: Distribution Learning, Rademacher Complexity, Mirror Descent, Spectral clustering

Lectures

	Date	Topics	Readings	Notes
1	W 9/5	Intro and many definitions	SSBD Ch 1 & 2
2	M 9/10	Finite hypothesis classes, PAC learning	SSBD Ch 2 & 3
3	W 9/12	Agnostic PAC learning, eps-representative samples	SSBD Ch 3 & 4
4	M 9/17	No-Free-Lunch Theorem & Hoeffding Inequality	SSBD Ch 5 & Appendix B	Hoeffding’s Inequality No-Free-Lunch Theorem
5	W 9/19	VC Dimension	SSBD Ch 6
6	M 9/24	The Fundamental Theorem of Statistical Learning	SSBD Ch 6	PDF
7	W 9/26	Perceptron, Margin-Perceptron	SSBD Ch 9	PDF
8	M 10/1	Perception Generalization Bound, Kernel Perceptron, Validation	SSBD 11.2, 16.1 & 16.2
9	W 10/3	Convexity Overview Part 1	SSBD Ch 12.1
	M 10/8	No class: Thanksgiving
10	W 10/10	Convexity Overview Part 2	SSBD Ch 12.1
11	M 10/15	Convex Learning, Regularization	SSBD Ch 12.2, Ch 13
12	W 10/17	Convex-Bounded-Lipshitz Learning, Learning by Stochastic Optimization	SSBD Ch 12.2, Ch 13, Ch 14.5.1
13	M 10/22	Gradient Descent, Lipschitz case	SSBD Ch 14	PDF
14	W 10/24	SGD, Strongly Convex case	SSBD Ch 14	PDF
15	M 10/29	Online Learning, Weighted Majority	SSBD Ch 21	PDF
16	W 10/31	Randomized Weighted Majority	SSBD Ch 21	PDF
17	M 11/5	Adversarial Bandits, PSim		PDF
18	W 11/7	PSim, Exp3		PDF
	M 11/12	No class: Remembrance Day
19	W 11/14	Stochastic Bandits, Successive Elimination	Slivkins Ch 1
20	M 11/19	Fenchel Duality, Bregman Divergences		PDF
21	W 11/21	Mirror Descent		PDF
22	M 11/26	Neural Nets	SSBD Ch 20
23	W 11/28	Boosting	SSBD Ch 10	PDF

Past offerings of this class

· CPSC 531H “Machine Learning Theory” Winter 2014