Times: Tuesday and Thursday, 3:30-4:45 pm
Location: MoSE building, room 1224
Instructor: Vidya K Muthukumar (vmuthukumar8@gatech.edu)
Office Hours: Tuesday and Thursday 4:45-5:30 pm (after class), location TBD
Prerequisites: undergraduate probability (ECE3077 or equivalent), undergraduate linear algebra (MATH 2551 or equivalent). Mathematical maturity and familiarity with proof-based arguments will be assumed.
Brief description: In many applications of machine learning (ML), data is collected sequentially; moreover, decisions can impact performance both in the present and the future. This class will deal with the design of ML algorithms for real- time decision making, including reinforcement learning. Classical applications in engineering and modern applications in the ML pipeline will both be discussed, but the focus of the course will be foundational — on understanding design principles and the inner workings of algorithms for online decision-making.
Upon successful completion of this course, students will be able to:
- Understand and explain the basic design principles of any online algorithm under diverse assumptions on the environment and reward feedback mechanism.
- Understand how these principles relate to classical concepts in information theory, signal processing, communications, and control theory.
- Assess the efficacy of an online algorithm for an engineering/machine learning application based on its performance guarantees, tractability of implementation, scalability and assumptions made on the environment.
- Appreciate how online algorithms relate to other aspects of the machine learning pipeline.
Grading/Format: The course will be graded as follows:
- Homeworks (top 4/5): 45%
- Midterm (take-home, tentative dates March 13-14): 25%
- Course project: 30%
Piazza/Canvas: The primary mode of interactive communication in this course will be Piazza. Please sign up at the course page, and monitor Piazza for announcements regarding lecture, homeworks, midterm and project. As is standard, we will also use Canvas to keep track of assignments and share resources related to the class.
Resources and schedule
Lecture schedule (tentative, subject to change)
| Date | Topic | Resources |
| 7 Jan | Logistics and introduction | |
| 9 Jan | Review session on probability and basics of ML | Probability review notes ML review notes |
| 14 Jan | Basics of prediction of an adversarial sequence | Lecture note |
| 16 Jan | The multiplicative weights algorithm | Lecture note |
| 21 Jan | Decision-making using expert advice; application to linear programs | Lecture note |
| 23 Jan | No-regret through perturbation | Lecture note |
| 28 Jan | No-regret through perturbation | |
| 30 Jan | No-regret through perturbation, introduction to online linear optimization | |
| 4 Feb | Online linear optimization | |
| 6 Feb | Online convex optimization and stochastic optimization | |
| 11 Feb | Overview of adaptive methods in online learning | |
| 13 Feb | Online learning and zero-sum game theory | |
| 18 Feb | Introduction to limited-information feedback | |
| 20 Feb | Limited-information feedback and UCB | |
| 25 Feb | Wrapping up UCB; lower bounds | |
| 27 Feb | Thompson sampling algorithm, Part 1 | |
| 4 Mar | Thompson sampling algorithm, Part 2 | |
| 6 Mar | Structured bandits: Linear and Gaussian processes | |
| 11 Mar | Contextual bandits and adversarial bandits | |
| 13-14 Mar | Take-home midterm | |
| 17-21 Mar | No class (spring break) | |
| 25 Mar | Dynamic programming and optimal control | |
| 27 Mar | Tabular RL with a generative model | |
| 1 Apr | Model-based exploration in tabular RL | |
| 3 Apr | Value iteration and Q-learning | |
| 8 Apr | Policy-based methods | |
| 10 Apr | RL with function approximation, theory | |
| 15 Apr | RL with function approximation, practice | |
| 17 Apr | Miscellaneous topics in RL | |
| 22 Apr | LAST DAY OF CLASS: Poster presentations |
Homework schedule:
Submission due date and self-grade upload deadline are both 11:59 ET. Submission and self-grade upload will be done via Canvas.
| Rough set of topics | Upload date | Due date | Self-grade due date | |
| Homework 0 (optional) | Review of probability and linear algebra | 7 Jan | 14 Jan | N/A |
| Homework 1 | Basics of online prediction | Jan 17 | 4 Feb |