CSC 588: Machine Learning Theory - Spring 2023

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.

Syllabus

Here is the syallabus updated on 01/11/2023. Further adjustments will be available in D2L.

Logistics info

• Tuesdays and Thursdays, 9:30am-10:45am
• Please find other information from the D2L and the syllabus.

Instructor

• Kwang-Sung Jun
• k[lastname]@cs.arizona.edu
• Gould-Simpson Rm 746
• Office hour: Tuesdays 4-5pm

Textbook

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)

Other useful resources

• Here are some excellent notes for probability review and linear algebra review.
• You should have no difficulty in Python programming.
• You may also find The matrix cookbook, The Probability and Statistics Cookbook useful, and Calculus cheatsheet.

Schedule

The following is a rough schedule. Please see D2L for a more detailed and calibrated schedule.

#		Topics	Readings		Homework
1: 01/12		intro			HW1
2: 01/17		concentration of measure
3: 01/19		the statistical learning/PAC framework
4: 01/24		VC Theory
5: 01/26
6: 01/31		Rademacher complexity
7: 02/02		Support vector machine, kernel methods, margin bounds.			HW2
8: 02/07		.
9: 02/09		Model selection: Structural risk minimization
10: 02/14		Boosting
11: 02/16		.			HW3
12: 02/21		Backgrounds on convex functions
13: 02/23		Regularization and stability
14: 02/28		.
15: 03/02		Online classification
16: 03/07		(spring recess)
17: 03/09		.
18: 03/14		Online convex optimization (OCO)
19: 03/16		Follow the regularized leader
20: 03/21		Online mirror descent
21: 03/23		OCO for strongly-convex/exp-concave functions
22: 03/28		Prediction with expert advice
23: 03/30		.			HW4
22: 04/04		Adversarial multi-armed bandits
23: 04/06		Stochastic multi-armed bandits
24: 04/11		.
25: 04/13		Stochastic linear bandits
26: 04/18		.
27: 04/20		Online reinforcement learning in Markov decision processes
28: 04/25		.
29: 04/27		project presentation
30: 05/02		.
: 05/04		final project due
: 05/09		final exam