Abstract: The extension of classical online algorithms, when provided with ML predictions, is a new and active research area. In this area, the goal is to design learning augmented online algorithms that: (1) incorporate predictions in a black-box manner (without making assumptions regarding the quality of the predictions), (2) outperform any online algorithm when the predictions are accurate (3) maintain reasonable worst-case guarantees if the predictions are misleading. In this talk, I will show how to extend the primal-dual method for online algorithms in the learning augmented setting. Using this method, I will focus on how to design algorithms that use predictions for the ski rental problem, the online set cover problem, and (if time permits) the TCP-acknowledgment problem.
This is joint work with Ola Svensson and Ettiene Bamas.
Bio: I am a fifth (and final) year Ph.D. student at EPFL, advised by Rudiger Urbanke and Ola Svensson. My interests lie in the intersection of theoretical computer science and machine learning and, more specifically, online algorithms (matchings, clustering, etc.), learning augmented online algorithms (i.e., online algorithms with predictions), and recently active learning. During the last two summers, I was a Research Intern at Google Zurich hosted by Nikos Parotsidis and Ehsan Kazemi, and on May 2022, I co-organized ALPS 2022, a workshop on algorithms with predictions. Before moving to Switzerland, I completed my undergrad studies at the National Technical University of Athens, where I studied Computer and Electrical Engineering, and I was advised by Dimitris Fotakis.
The Data Science Deep Dive is free and open to the public. If you are interested in giving a talk, please email Mohammad Hajiesmaili or Adam Lechowicz. Note that in addition to being a public lecture series, the Data Science Deep Dive is also a seminar (CompSci 692K, Algorithms with Predictions Seminar) that can be taken for credit.