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.