For best experience please turn on javascript and use a modern browser!
You are using a browser that is no longer supported by Microsoft. Please upgrade your browser. The site may not present itself correctly if you continue browsing.
Abstract at the OPTIMAL Conference, December 19, 2023 Speaker: Marek Eliáš (Bocconi University) Title: Learning-augmented algorithms with explicit predictors

Abstract:

In the field of algorithmic design, there has been recent progress in utilizing predictions from machine learning models applied to the input data (or historical data). These approaches have demonstrated an enhancement in performance when the predictions are accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this manuscript we focus on online problems; prior research in this context has generally treated the machine learning algorithm as a black-box with unspecified training methods. In contrast, in this work, we unpack the algorithm and examine the learning problem it gives rise to, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task at hand. Adopting this perspective, we turn our attention to a number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems we consider, we introduce new algorithms that take advantage of explicit learning algorithms which we carefully design towards optimizing the overall performance. We demonstrate the potential of our approach by deriving performance bounds that show improvement over those established in previous work.