Times: Tuesday and Thursday, 9:30-10:45 am
Location: Groseclose 119
Instructor: Vidya K Muthukumar (vmuthukumar8@gatech.edu)
GTA: Krishna V Acharya (krishna.acharya@gatech.edu)
MTA: Lokranjan Lakshmikanthan (llakshmi3@gatech.edu)
Office Hours: Instructor OH Tuesdays 11 am-12 pm, Groseclose 336
GTA OH TBD
MTA OH TBD
Prerequisites: ISYE 3133 (Optimization) and ISYE 2027 (Probability). Mathematical maturity and familiarity with working with abstract mathematical notation will be assumed. A few elementary proof-based arguments will also be covered.
Brief description: At the heart of most machine learning applications today – like advertisement placement, movie recommendation, and node prediction in evolving networks – is an optimization engine trying to provide the best decision with the information observed thus far in time, i.e. the problem of online learning. To solve these problems, one must make online, real-time decisions and continuously improve the performance with the arrival of data and feedback from previous decisions. The course aims to provide a foundation for the development of such online methods and for their analysis. We will discuss fundamental principles for learning from an unknown environment, limited feedback, and learning with dynamic, long-term consequences.
Upon successful completion of this course, students will be able to:
- Understand where online learning is applicable in many real-world scenarios.
- Develop algorithms that combine partial information as best as possible to make online decisions.
- Understand how exploration of decision space and exploitation from historic data must be prioritized to be able to reach optimal decisions.
- Understand the dynamic-programming principle of sequential decision-making when decisions have long-term consequences, and appreciate principles for learning in such long-term environments.
Grading/Format: The course will be graded as follows:
- Assignment 0: 2% bonus (released Jan 9, due Jan 16, covers course prerequisites)
- Homeworks (4 in total): 50%
- Two in-class midterms (tentative dates: Feb 13 and March 26): 30% in total
- Final exam (April 29, 8-10:50 am): 20%
Lecture medium and study resources: All lectures will be in person and on the board (projected through tablet). I will record lectures and make the recording and accompanying handwritten notes available a few hours after lecture. These recordings are intended to be an accompaniment to in-person attendance rather than a substitute.
In addition to this, I also will provide supplemental type-written notes.
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 and exams. 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 | Additional resources guide (internally available on Canvas/Piazza) |
| 9 Jan | Logistics and introduction | Lecture recording and slides |
| 11 Jan | Review session on prerequisites | Lecture recording and notes, Chapter 1 of supplementary material |
| 16 Jan | Introduction to prediction of an adversarial binary sequence and the halving algorithm | Lecture recording and notes, Chapter 2 and Chapter 3 of supplementary material |
| 18 Jan | Binary sequence prediction: The halving algorithm and the weighted majority algorithm | Lecture recording and notes, Chapter 3 of supplementary material |
| 23 Jan | Binary sequence prediction: The randomized weighted majority algorithm | Lecture recording and notes, Chapter 3 of supplementary material |
| 25 Jan | Prediction with expert advice: General loss functions | Lecture recording and notes, Chapter 4 of supplementary material |
| 30 Jan | Prediction with expert advice: General loss functions (continued) | Lecture recording and notes, Chapter 4 of supplementary material |
| 1 Feb | Application: solving linear programs, continued | Lecture recording and notes, Chapter 5 of supplementary material |
| 6 Feb | Application: solving linear programs (continued) | Lecture recording and notes, Chapter 5 of supplementary material |
| 8 Feb | Review: Online sequence prediction | Lecture recording and notes |
| 13 Feb | In-class midterm 1 | |
| 15 Feb | Midterm 1 discussion | Lecture recording and notes, midterm solutions |
| 20 Feb | NO CLASS (instructor travel) | |
| 22 Feb | NO CLASS (instructor travel) | |
| 27 Feb | Limited-information feedback (bandits): Introduction and heuristics | Lecture recording and notes, Chapter 6 of supplementary material |
| 29 Feb | Bandits, pure-greedy and epsilon-greedy algorithms | Lecture recording and notes, Chapter 6 of supplementary material |
| 5 March | Bandits, UCB | Lecture recording and notes, Chapter 7 of supplementary material |
| 7 March | Bandits, UCB | Lecture recording and notes, Chapter 7 of supplementary material |
| 12 March | Bandits, UCB | Lecture recording and notes, Chapter 7 of supplementary material |
| 14 March | Bandits, Thompson sampling | Lecture recording and notes, Chapter 7 of supplementary material |
| 19 March | NO CLASS (Spring break) | |
| 21 March | NO CLASS (Spring break) | |
| 26 March | Review: Bandits | Lecture recording and notes |
| 28 March | In-class midterm 2 | |
| 2 April | Bandits, Thompson sampling and wrap-up | |
| 4 April | Dynamic programming and optimal control | |
| 9 April | Dynamic programming and optimal control, continued | |
| 11 April | A birds’ eye view of reinforcement learning | |
| 16 April | Fairness and ethical considerations in decision making | |
| 18 April | LAST DAY OF CLASS: Review and summary of current research directions in online learning | |
| 29 April | Final exam (8-10:50 am) |
Assignment schedule (tentative, subject to change)
| Assignment | Release date | Due date | Scope of homework |
| 0 | 9 Jan | 16 Jan | Prerequisites |
| 1 | 18 Jan | 7 Feb | Binary and general loss sequence prediction |
| 2 | 15 Feb | 1 March | General loss sequence prediction and LPs |
| 3 | 5 March | 5 April | Limited-information feedback (bandit) algorithms |
| 4 | 4 April | 19 April | Recommender systems and dynamic programming |