CSC 588: Machine Learning Theory (Spring 2021)

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.

Logistics info

TuTh 9:30am-10:45am on Zoom (see D2L for meeting link)

Gradescope entry code: GEPJNE

D2L course webpage: lecture video recordings can be found at “UA Tools” -> “Panopto”


Piazza link access code: generalization


Chicheng Zhang

Gould-Simpson 720

Office Hour: Mondays 1-2pm (see D2L for meeting link) or by email appointment


There is no designated textbook for this course. Much of the course materials will be based on the following books (in the order of appearance in class schedule):

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)

The following set of surveys and books also provide a 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

Review for prerequisites

Here are some excellent notes for probability review and linear algebra review from Stanford’s CS 229 course.

Scribing and LaTeX

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 sign up sheet.

Some useful LaTeX resources: Learn LaTeX in 30 minutes by Overleaf; Introduction to LATEX by MIT Research Science Institute

Machine learning courses at UA

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

Learning theory courses at other institutions

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