Computer Science: Machine Learning Theory

CSC 482A/581B, Spring 2019

Lectures: Mondays and Thursdays 10:00am - 11:20am, DSB C108
Instructor: Nishant Mehta. Office hours: ECS 608, Mondays and Wednesdays, 4:30pm - 5:30pm.
TA: Yudi Santoso. Email: <lastname>@uvic.ca

Recommended textbooks:


**Graduate student project - due by 11:59pm PDT, Friday April 12th**


Sketch of the course
Given an i.i.d. sample of data points with accompanying labels, how well can a learning algorithm predict the labels of future data? How well can a learning algorithm perform if it instead predicts the label of each data point given all the previously observed labeled data points, and moreover, the sequence of data points might be devised by some adversary rather than being an i.i.d. sample? The first question lies at the heart of statistical learning theory, while the second comes from the area of online learning.

In this course we will look at core techniques for analyzing the performance of machine learning algorithms for problems in statistical learning, as well as the design aspects of good machine learning methods. We will also look at variants of learning problems, potentially including learning from data that has been corrupted by an adversary (which requires noise-tolerant learning), semi-supervised learning, and active learning. A smaller but significant component of this course will focus on various online learning settings, including prediction with expert advice and multi-armed bandit problems. We will study radically different tools to analyze online learning algorithms, and, if there is time, we will also look at recent connections that unify the analysis of statistical (i.i.d.) learning and online learning algorithms.

In the schedule below, any information about future lectures is just a rough guide and might change.

Lectures
Date Topics Lecture Notes and Problem Sets Additional reading
1/7 Course overview; Introduction; Mistake bound model Lecture 1
1/10 Halving algorithm; Learning linear separators Lecture 2
1/14 Perceptron; Consistency model; PAC learning Lectures 3 & 4 (SSBD): Section 3.1
1/17 Connections between learning models Intro to statistical learning theory (Boucheron, Bousquet, Lugosi).
(SSBD): Chapter 5 for No-Free-Lunch theorem
1/21 Agnostic learning; Error decompositions;
Concentration inequalities; Uniform convergence for finite classes		 Lectures 5 & 6 (SSBD): Chapter 4
1/24 Growth function, Uniform convergence for infinite classes Problem Set 1
1/28 VC dimension; Sauer's Lemma;
Uniform convergence for infinite classes under the realizability assumption		 Lectures 7 & 8
1/31 VC dimension; Sauer's Lemma
2/4 Uniform convergence for infinite classes under the realizability assumption
Lower bounds based on the VC dimension		 Lecture 9
2/7 Bounded differences inequality; Rademacher complexity
Bounds based on Rademacher complexity		 Lectures 10 & 11
(PS1 due Friday)
2/11 Connection to VC dimension; Properties of Rademacher complexity Problem Set 2
2/14 Support vector machines; Margin bounds Lecture 12
2/25 Weak and Strong Learnability; Boosting
Training error bound for AdaBoost		 Lecture 13
Problem Set 3 		Rob Schapire's lecture notes.
A short introduction to boosting (Freund and Schapire)
2/28 Compression schemes; Generalization error bounds for AdaBoost
Proof that weak learnability implies strong learnability		 Lecture 14
3/4 Margin bounds for AdaBoost Lecture 15
3/7 Prelude to PAC-Bayes: Occam bounds and Information theory Lecture 16
3/11 PAC-Bayesian bounds Lecture 17
3/14 Decision-theoretic online learning; Hedge
Analysis of Hedge		 Lecture 18
Problem Set 4
3/18 Game theory; Connection to AdaBoost Lecture 19
3/21 Prediction with expert advice
(maybe) Exp-concave loss functions		 Lecture 20
3/25 Stochastic multi-armed bandits; UCB
(Nishant at ALT! Guest lecture by Bingshan Hu)		 Lecture 21
3/28 Non-stochastic multi-armed bandits; EXP3 Lecture 22 Sébastien Bubeck and Nicolò Cesa-Bianchi's bandits monograph
4/1 Online convex optimization; Online gradient descent
Stochastic convex optimization; Online-to-batch conversion		 Kakade and Tewari's lecture notes
Lecture 23
4/4 Project presentations
?/? Project presentations
(Possibly scheduled outside of regular class time)