How can machine learning help traditional algorithm design and analysis? One idea is to equip online algorithms with some noisy predictions about the future. Recent work has shown that such "learning-augmented algorithms" can effectively interpolate between offline methods where the full input is known and worst-case online algorithms, resulting in a competitive ratio parameterized by the quality of the predictions.
In this talk, we expand on this work and show that the learning-augmented lens is powerful in and of itself. We first look at the classical secretary problem, and prove that different variants of this age-old problem can be thought of simply as different advice that is available to the algorithm. This view allows us to develop a single analysis to give tight bounds on competitive ratio for many of these variations.
We then turn from competitive ratio to running time, and show how that here too predictions can be helpful. Specifically, we consider the min weight perfect matching problem and show what kind of predictions can be used to improve the running time, effectively formalizing the "warm-start" problem.
Based on joint work with Michael Dinitz, Paul Duetting, Sungjin Im, Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Renato Paes Leme
REGISTER to attend.