Academics / Courses / DescriptionsCOMP_SCI 497: Learning Augmented Online Algorithms
VIEW ALL COURSE TIMES AND SESSIONS
Prerequisites
CS 336 or Any PhD studentDescription
In applications like routing, job scheduling, caching, etc., requests arrive sequentially, and the goal of the system is to handle requests as they arrive, while optimizing an appropriate overall objective. The field of online algorithms focuses on developing and analyzing such systems, and ensuring that they are "competitive" against the best solution in hindsight. While online algorithms have been developed for a wide variety of problems, the standard worst-case guarantees turn out to be insufficient in many applications. The question then is if we can use the "structure" in real world data to obtain better guarantees. Since structure is a problem-dependent notion, one general way to model it is to assume that there is a predictive model (possibly based on machine learning on past data) that can provide partial information about the problem instance, e.g., about upcoming requests. In this PhD-level course, we will see how to design algorithms that can exploit such "advice". We will consider a variety of online problems ranging from data structures and caching to online learning and bandits.
[The course will assume familiarity with the design and analysis of algorithms, probabilistic analysis, as well as notions such as approximation factors.]
- This course fulfills the Project or Technical Elective area.
REFERENCE TEXTBOOKS: N/A
REQUIRED TEXTBOOK: N/A
COURSE COORDINATORS: Prof. Aditya Bhaskara
COURSE INSTRUCTOR: Prof. Aditya Bhaskara