201819
Winter Term 1
General Information
Course Website: http://www.cs.ubc.ca/~nickhar/F18531
Lecture Time: Monday &
Wednesday 121: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.
Assignments:
·
Perhaps 45 over the term.
Rough plan of topics:
·
Definitely:
PAC learning, VC dimension, Perceptron, Multiplicative Weights, Online
Learning, Stochastic Gradient Descent, Multiplicative Weight Methods, Boosting,
Online Convex Optimization, Nonstochastic 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, epsrepresentative samples 
SSBD Ch 3 & 4 

4 
M 9/17 
NoFreeLunch
Theorem & Hoeffding Inequality 
SSBD Ch 5 & Appendix B 

5 
W 9/19 
VC
Dimension 
SSBD Ch 6 

6 
M 9/24 
The
Fundamental Theorem of Statistical Learning 
SSBD Ch 6 

7 
W 9/26 
Perceptron,
MarginPerceptron 
SSBD Ch 9 

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 
ConvexBoundedLipshitz Learning, Learning by Stochastic Optimization 
SSBD Ch 12.2, Ch 13, 

13 
M 10/22 
Gradient
Descent, Lipschitz case 
SSBD Ch 14 

14 
W 10/24 
SGD,
Strongly Convex case 
SSBD Ch 14 

15 
M 10/29 
Online
Learning, Weighted Majority 
SSBD Ch 21 

16 
W 10/31 
Randomized
Weighted Majority 
SSBD Ch 21 

17 
M 11/5 
Adversarial
Bandits, PSim 


18 
W 11/7 
PSim, Exp3 



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 


21 
W 11/21 
Mirror
Descent 


22 
M 11/26 
Neural
Nets 
SSBD Ch 20 

23 
W 11/28 
Boosting 
SSBD Ch 10 
Past offerings of this class