The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. Ideally, we would like the algorithm's performance to depend on the quality of the best predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is the best. We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.
翻译:与预测有关的算法研究领域最近取得了成功,展示了如何将机器学习纳入算法设计,以便在预测正确时改进性能,同时保留最坏的保证。以前的大部分工作假设算法可以使用单一的预测器。然而,在实践中,有许多机器学习方法,往往具有无法比较的概括性保证,因此很难先验地选择最佳的方法。在这项工作中,我们考虑了算法可以使用多个预测器的假想,问题是如何最好地利用这些算法。理想的是,我们希望算法的性能取决于最佳预测器的质量。但是,利用更多的预测是有代价的,因为我们现在必须确定哪一种预测是最好的。我们研究如何使用多个预测器来处理一些基本问题,包括匹配、负载平衡和非负载排期,这些问题在单一预测器设置中已经很好地研究过。对于这些问题中的每一问题,我们都会引入利用多个预测器的新算法,并证明由此产生的性能的界限。