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

Finish Convex Learning, Start SGD

SSBD Ch 12.2, Ch 13, Ch 14

 

13

M 10/22

 

 

 

14

W 10/24

 

 

 

15

M 10/29

 

 

 

16

W 10/31

 

 

 

17

M 11/5

 

 

 

18

W 11/7

 

 

 

 

M 11/12

No class: Remembrance Day

 

 

19

W 11/14

 

 

 

20

M 11/19

 

 

 

21

W 11/21

 

 

 

22

M 11/26

 

 

 

23

W 11/28

 

 

 

 

 

Past offerings of this class

·        CPSC 531H “Machine Learning Theory” Winter 2014