This course provides an introduction to the theoretical aspects of machine learning. Students will learn how and when machine learning is possible/impossible as well as various algorithms with theoretical guarantees under minimal assumptions. Specifically, the course offers formulation of learning environments (e.g., batch and online settings, stochastic and adversarial worlds with possibly limited feedback), fundamental limits of learning in these environments, various algorithms concerning sample efficiency, computational efficiency, and generality. Throughout, students will not only learn fundamental tools upholding the current understanding of machine learning systems in the research community but also develop skills of adapting these techniques to their own research needs such as developing new algorithms for large-scale, data-driven applications.
TuTh 9:30am-10:45am, Gould-Simpson 701
Piazza link; please self-enroll.
Gradescope entry code: WYENZ3
D2L course webpage: lecture video recordings are at “UA Tools” -> “Zoom”
We will be using Piazza to make important announcements and do Q&As. Some general rules:
Gould-Simpson 720
Office Hour: Wednesdays 11am-12pm on Zoom (link in D2L page)
There is no designated textbook for this course. Much of the course materials will be based on these books:
Understanding machine learning: from theory to algorithms by Shai Shalev-Shwartz and Shai Ben-David (SSBD)
A Modern Introduction to Online Learning by Francesco Orabona (O)
Bandit algorithms by Tor Lattimore and Csaba Szepesvari (LS)
Reinforcement Learning: Theory and Algorithms by Alekh Agarwal, Nan Jiang, Sham Kakade, and Wen Sun (AJKS)
The following monographs and books also provide good coverage of relevant materials:
Introduction to online optimization by Elad Hazan
Online learning and online convex optimization by Shai Shalev-Shwartz
Regret analysis of stochastic and nonstochastic multi-armed bandit problems by Sebastien Bubeck and Nicolo Cesa-Bianchi
Introduction to Multi-Armed Bandits by Alex Slivkins
Here are some excellent notes for probability review and linear algebra review from Stanford’s CS 229 course.
See also The matrix cookbook, The Probability and Statistics Cookbook, and Calculus cheatsheet (recommended by Prof. Kwang-Sung Jun).
This course has a theoretical / mathematical nature, so a large part of this course will be proof-based. For formal proof reading and writing, I recommend the book “How to Read and Do Proofs” by Daniel Solow. I also recommended watching the lecture Street Fighting Mathematics by Prof. Ryan O’Donnell for general introductions to approaching theory-ish problems.
We will be using the following scribe note LaTeX template file and style file. See also Prof. Rob Schapire’s suggestions on preparing scribe notes. Please sign up for one slot at the signup sheet.
Useful LaTeX resources: Learn LaTeX in 30 minutes by Overleaf; Introduction to LATEX by MIT Research Science Institute
CSC 535 Probabilistic Graphical Models by Kobus Barnard
ISTA 457/INFO 557 Neural Networks by Steven Bethard
CSC 665 Online Learning and Multi-armed Bandits by Kwang-Sung Jun
INFO 521 Introduction to Machine Learning by Clayton Morrison
CSC 665 Advanced Topics in Probabilistic Graphical Models by Jason Pacheco
CSC 580 Principles of Machine Learning by Carlos Scheidegger
MIS 601 Statistical Foundations of Machine Learning by Junming Yin
MATH 574M Statistical Machine Learning by Helen Zhang
CSC 696H: Topics in Reinforcement Learning Theory by Chicheng Zhang
There are many learning theory courses offered at other institutions. Many of them have good lecture materials and together offers a diverse set of perspectives of this field; here are just a few examples:
Foundations of Machine Learning and Data Science by Nina Balcan and Avrim Blum
Statistical Learning Theory by Peter Bartlett
Topics in Learning Theory by Daniel Hsu
Theoretical Machine Learning by Rob Schapire
Machine Learning Theory by Matus Telgarsky
Learning Theory by Sham Kakade and Ambuj Tewari