Times: Monday and Wednesday, 3:30 – 4:45 pm
Location: MRDC building, room 2404
Instructor: Vidya K Muthukumar (firstname.lastname@example.org)
GTA: Hoang Nguyen (email@example.com)
UTA: Lyann Sun (firstname.lastname@example.org)
Office Hours: Instructor OH Wednesdays 12-1 pm, Groseclose 336
GTA OH Wednesdays 5-6 pm, Groseclose 304
UTA OH Tuesdays 12-1 pm, Groseclose 304
Prerequisites: ISYE 3133 (Optimization) and ISYE 2027 (Probability). Mathematical maturity and familiarity with proof-based arguments will be assumed.
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: 3% (released Aug 22, due Aug 29, covers course prerequisites)
- Homeworks (4 in total): 45%
- Two in-class midterms (tentative dates: Sep 26 and Oct 31): 30% in total
- Final exam (Dec 9, 2:40-5:30 pm): 20%
- Class participation (measured through Piazza): 2%
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)|
|22 Aug||Logistics and introduction||See posted lecture slides.|
|24 Aug||Review session on prerequisites||See Chapter 1 of supplementary notes.|
|29 Aug||Basics of prediction of an adversarial binary sequence||See Chapter 2 of supplementary notes.|
|31 Aug||Binary sequence prediction using expert advice: Deterministic algorithms||See Chapter 3 of supplementary notes.|
|7 Sep||Binary sequence prediction using expert advice: Randomized algorithms||See Chapter 3 of supplementary notes.|
|12 Sep||Prediction with expert advice and general loss functions||See Chapter 4 of supplementary notes.|
|14 Sep (asynchronous due to instructor travel)||Application: solving linear programs||See Chapter 5 of supplementary notes.|
|19 Sep||No class|
|21 Sep||No class|
|26 Sep||Application: solving linear programs (continued), zero-sum games|
|28 Sep||Review: Full-information online learning|
|3 Oct||In-class midterm 1|
|5 Oct||In-class midterm 1|
|10 Oct||Introduction to limited-information feedback; exploration-vs-exploitation|
|12 Oct||Limited-information feedback, randomized-greedy and Exp3|
|19 Oct||Limited-information feedback, UCB|
|24 Oct||Limited-information feedback, UCB and Thompson sampling|
|26 Oct||Limited-information feedback, Thompson sampling|
|31 Oct||Application: recommender systems|
|2 Nov||Application: recommender systems|
|7 Nov||Dynamic programming and optimal control|
|9 Nov||In-class midterm 2|
|14 Nov||Dynamic programming and optimal control|
|16 Nov||Basics of “simulation-based” RL|
|21 Nov||Basics of online RL and exploration|
|28 Nov||Value-based methods in RL|
|30 Nov||Policy-based methods in RL|
|5 Dec||LAST DAY OF CLASS: Review and summary of current research directions in online learning|
|9 Dec||Final exam (2:40-5:30 pm)|