DATA 37200: Learning, Decisions, and Limits (Winter 2025)

Basic Information

Class Location: JCL 011
Class Time: Tu/Thu 12:30 to 1:50 pm
Instructor: Frederic Koehler and Haifeng Xu
TA: Aditya Prasad
Course Material: There will not be any official textbook, but the slides and links to reading materials will be posted on the course schedule after each lecture.

Learning Objectives: (1) Understand basic toolkits for online learning and online decision making, as a complement to offline learning paradigm; (2) Prepare students to understand state-of-the-art RL algorithms, such as RLHF and AlphaGo training.

Announcements


Course Description

This is a graduate course on theory of machine learning. While ML theory has multiple branches in general, this course is designed to cover basics of online learning, along with basics of reinforcement learning. It aims to establish the foundation for students who are interested in conducting research related to online decision making, learning, and optimization. The course will introduce formal formulations for fundamental problems/models in this space, describe basic algorithmic ideas for solving these models, rigorously discuss performances of these algorithms as well as these problems’ fundamental limits (e.g., minmax/lower bounds). En route, we will develop necessary toolkits for algorithm development and lower bound proofs.

Topics covered in this course, and tentative syllabus (up to small changes):

This is primarily a theory course, and lecture-based. That said, we will focus primarily on proofs over coding. Prerequisites include linear algebra (at the level of CMSC 25300 or its equivalent), algorithms (CMSC 27200 or its equivalent) and probability (STATS 25100 or its equivalent). If not sure, consult with the instructor. Note that no background on learning theory is required.

Lectures and Readings

Lec No. Lectures Readings
1 (Jan 7) Intro and MAB [slides] Various concentration inequalities and concentration for martingales
2 (Jan 9) UCB [slides] Chapter 1 of this MAB book
2-3 (Jan 14,16) MAB lower bound [slides] Chapter 2 of this MAB book

Homework

Due date Homework Note

Requirements and Grading

Grades consist of three components: (1) 3~4 proof-based assignments (30% ); (2) three in-class 30-mins quizzes (25%), with 30 mins each; (3) course project (45%). Notably, the quiz is expected to not be difficult, but rather some simple tests to see whether you are indeed on top of the key materials.

The project could be one of the following three categories: (A) Reproduce the proofs of existing paper(s); (B) Novel research and results; (C) something between A and B (we would encourage most of you to start in this category, which have some novelty yet is backed up by reproducing proofs)

There is no midterm or final for the course.

Late Homework Policy : Each student is allowed one late homework for at most two days from the due date. You may choose whichever homework to use this chance (or not use it). No additional late homework will be accepted.



Students with disabilities or learning needs

We thrive to create a learning experience that is as accessible as possible. If you anticipate any issues related to the format, materials, or requirements of this course, please meet with me outside of class so we can explore potential options. Students with disabilities may also wish to work with the UChicago Student Disability Services to discuss a range of options to removing barriers in this course, including official accommodations. Please visit their website for information on this process and to apply for services online: disabilities.uchicago.edu. If you have already been approved for accommodations through SDS, please send me your accommodation letter, and meet with me if needed, so we can develop an implementation plan together.