Abstract: Recently, learning-augmented algorithms have attracted growing interests. Such algorithms leverage machined learned (ML) advice to design competitive algorithms with the objective of improving the competitive ratio of classic online algorithms when the advice is accurate (i.e., consistency), while also providing a worst-case guarantee regardless of the advice quality (i.e., robustness). In this talk, I will focus on the online search problem that includes 1-max search and one-way trading as special cases. I will first show that the algorithmic design of the online search problem can be unified into the design of a class of online threshold-based algorithms. Then by incorporating ML advice into the design of the threshold function, the learning-augmented algorithm can achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency for a given robustness guarantee.
Bio: Bo Sun is a Postdoctoral Fellow in the Department of Computer Science and Engineering at The Chinese University of Hong Kong (CUHK). Prior to that, he was a Postdoctoral Fellow in the Department of Electronic and Computer Engineering at The Hong Kong University of Science and Technology (HKUST). He also obtained his Ph.D. from HKUST. His research focuses on optimization and decision-making under uncertainty to advance the efficiency, robustness, and sustainability of networked systems, such as energy-transport nexus, cloud/edge computing, and smart grids.
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.