Statistical Learning Theory

Fall 2020

**E-mail:** prakash@cs.mcgill.ca

- A new lecture schedule has been posted. Please check below.
- I have posted notes below for the lecture on VC dimension on the 16th of September.
- I gave the lecture live on the 14th of September and it was recorded successfully. I have posted some notes below but everything in my notes is also in the book.
- The lecture by Prof. Oberman is recorded and is available from
myCourses. To see it look under
**Content**and**not**under lecture recordings. - Assignment 1 has been posted both here (see below) and on myCourses.
To find it in myCourses look under
**Content**and**not**under Assignments. The Assignments tab on myCourses is for submission of your solutions to assignment 1.**Assignments can be submitted until 11:00 pm.** - The course will be taught
**on campus**in Trottier 100 from 11:35 to 12:55 Mondays and Wednesdays. The lectures**will be recorded**. - This course is co-taught with Prof. Adam Oberman of the Department of Mathematics and Statistics and is cross listed as MATH 597.
- Here is the lecture schedule.
- Here is a course outline.
- The recommended textbooks for the course are
*Understanding Machine Learning*by Shai Shalev-Schwartz and Shai Ben-David and*Foundations of Machine Learning*by Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar; this book is available at Mohri's website. These books have not been ordered through the bookstore.

- Lecture Times: MW 11:35 - 12:55
- Lecture Place: Trottier 100
- Office Hours: MW 1:30 - 2:30 by Zoom
- Office: McConnell (North Wing) 105N
- TA and office hours:
- Vincent Luczkow Wed 2:30 - 3:30 by Zoom

- Basic probability notes from 2nd September.
- Notes on basics of PAC-learning.
- Notes on learning rectangles. For the 14th September lecture.
- Notes on learning bounds for the non-realizable case.
- Notes on learning bounds for the agnostic case.
- Notes on VC dimension from 16th September.
- Notes on the learning bound based on VC dimension from 21st September.
- Notes on Rademacher complexity.
- A short note explaining why swapping does not change the distribution of samples.
- 14th October lecture notes on online learning.
- 19th October lecture notes on the Perceptron algorithm.
- 2nd November lecture notes on RKHS.
- 4th November lecture notes on kernels.
- 23rd November lecture notes on metrics for spaces of probability distributions.
- 25th November lecture notes on toy KR duality.
- 30th November lecture notes on GANs.

- Video recording of the 14th October lecture.
- recording of the 19th October lecture.
- Video recording of the 2nd November lecture.
- Video recording of the 4th November lecture.
- Video recording of the 23rd November lecture.
- Video recording of the 30th November lecture.

- Assignment 1. Due on 18th September via myCourses. LaTeX is required.
- Assignment 1 solutions.
- Assignment 2. Due on 2nd October via myCourses.
- Assignment 2 solutions.
- Assignment 4. Due on 4th November at 11pm.
- Assignment 4 solutions.
- Assignment 6. Due on 2nd December.

Below are some suggestions for topics that could be explored in more detail for the final project, and a couple of examples of relevant papers for each topic. All of these would make good literature synthesis topic, though you should be prepared to find additional relevant papers on your own! (Google Scholar is a good place to start.) This list might also inspire ideas for research projects. Of course you are welcome to choose a topic that is not on the list.

Probabilistic bisimulation and metrics:

- Josée Desharnais, Abbas Edalat, and Prakash Panangaden. Bisimulation for labelled Markov processes. Information and Computation 179.2 (2002): 163-193.
- Josee Desharnais, Vineet Gupta, Radha Jagadeesan and Prakash Panangaden Metrics for Labelled Markov Processes, by Josee Desharnais, Vineet Gupta, Radhakrishnan Jagadeesan and Prakash Panangaden, Theoretical Computer Science, 318(3), pp. 323-354, June 2004.
- Metrics for Markov Decision Processes with Infinite State Spaces by Norm Ferns, Prakash Panangaden and Doina Precup. In UAI 2005.

Active Learning:

- Dasgupta. Two Faces of Active Learning. To appear in Theoretical Computer Science, 2011.
- Balcan, Beygelzimer, and Langford. Agnostic Active Learning. Journal of Computer and System Sciences, 2009.
- Dasgupta. Coarse Sample Complexity Bounds for Active Learning. NIPS, 2005.
- Dasgupta, Kalai, and Monteleoni. Analysis of Perceptron-Based Active Learning. COLT, 2005.

The Multi-Armed Bandit Problem:

- Abernethy, Hazan, and Rakhlin. Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization. COLT, 2008.
- Even-Dar, Mannor, and Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. JMLR, 2006.
- Auer, Cesa-Bianchi, Freund, and Schapire. The nonstochastic multiarmed bandit problem. SICOMP, 2002.
- Auer, Cesa-Bianchi, and Fischer. Finite time analysis of the multiarmed bandit problem. MLJ, 2002.

Domain Adaptation and/or Multi-Source Learning:

- Ben-David, Blitzer, Crammer, Kulesza, Pereira, and Vaughan. A Theory of Learning from Different Domains. MLJ, 2010.
- Mansour, Mohri, and Rostamizadeh. Domain adaptation: Learning bounds and algorithms. COLT, 2009.
- Crammer, Kearns, and Wortman. Learning from Multiple Sources. JMLR, 2008.

Privacy-Preserving Machine Learning:

- Chaudhuri, Monteleoni, Sarwate. Differentially Private Empirical Risk Minimization. JMLR, 2010.
- Kasiviswanathan, Lee, Nissim, Raskhodnikova, and Smith. What Can We Learn Privately? SICOMP, 2011.
- Blum, Ligett, and Roth. A Learning Theory Approach to Non-Interactive Database Privacy. STOC, 2008.

Learning Bounds for Reinforcement Learning:

- Li, Littman, and Walsh. Knows What It Knows: A Framework for Self-Aware Learning. ICML, 2008.
- Kearns and Singh. Near-Optimal Reinforcement Learning in Polynomial Time. MLJ, 2002.

Online Convex Optimization:

- Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. ICML, 2003.
- Elad Hazan: Introduction to Online Convex Optimization, book published
in the
*Foundations and Trends*series. You can download a free copy from the author's website. He also has a book chapter called The convex optimization approach to regret minimization.. - Kalai and Vempala. Efficient Algorithms for Online Decision Problems. Journal of Computer and System Sciences, 2005.

Clustering:

- Balcan, Blum, and Gupta. Approximate Clustering without the Approximation. SODA, 2009.
- Balcan, Blum, and Vempala. A Discriminative Framework for Clustering via Similarity Functions. STOC, 2008.

PAC-Bayes Bounds:

- McAllester. Some PAC-Bayes Theorems. MLJ, 1999.
- McAllester. PAC-Bayesian Stochastic Model Selection. MLJ, 2003.

Ranking:

- Agarwal and Niyogi. Generalization bounds for ranking algorithms via algorithmic stability. JMLR, 2009.
- Rudin and Schapire. Margin-Based Ranking and an Equivalence Between AdaBoost and RankBoost. JMLR, 2009.
- Freund, Iyer, Schapire, and Singer. An efficient boosting algorithm for combining preferences. JMLR, 2003.

Geometrical Ideas

- Essentially no barriers in neural network energy landscape by Draxler at al. From ICML 2018.
- On Characterizing the Capacity of Neural Networks using Algebraic Topology by William H. Guss and Ruslan Salakhutdinov.

GANs and metrics

- Generative adversarial nets by Ian J. Goodfellow et al. 2014
- Generative adversarial nets tutorial by Ian J. Goodfellow 2016 Wasserstein GAN by Martin Arjovsky, Soumith Chintala, and Leon Bottou 2017.

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offenses under the Code of Student Conduct and Disciplinary Procedures (see http://www.mcgill.ca/integrity for more information). Most importantly, work submitted for this course must represent your own efforts. Copying assignments or tests from any source, completely or partially, or allowing others to copy your work, will not be tolerated.

Every student has the right to submit written work that is to be graded, in English or in French.

Chaque étudiant a le droit de soumettre en français ou en anglais tout travail écrit.