A burgeoning paradigm in algorithm design is the field of algorithms with predictions, in which algorithms can take advantage of a possibly-imperfect prediction of some aspect of the problem. While much work has focused on using predictions to improve competitive ratios, running times, or other performance measures, less effort has been devoted to the question of how to obtain the predictions themselves, especially in the critical online setting. We introduce a general design approach for algorithms that learn predictors: (1) identify a functional dependence of the performance measure on the prediction quality and (2) apply techniques from online learning to learn predictors, tune robustness-consistency trade-offs, and bound the sample complexity. We demonstrate the effectiveness of our approach by applying it to bipartite matching, ski-rental, page migration, and job scheduling. In several settings we improve upon multiple existing results while utilizing a much simpler analysis, while in the others we provide the first learning-theoretic guarantees.
翻译:算法设计中新兴的范式是算法的预测领域,在算法中,算法可以利用对问题某些方面的可能不完全的预测。虽然许多工作侧重于利用预测来改进竞争比率、运行时间或其他业绩计量,但对如何获得预测本身、特别是关键在线环境的预测作出了较少的努力。我们对学习预测者的算法采用了一般设计方法:(1) 确定业绩计量在功能上对预测质量的依赖性,(2) 应用在线学习技术来学习预测者、调整稳健性和一致性的取舍,并约束抽样复杂性。我们通过将预测应用到双边配对、滑雪-轮、页面迁移和工作时间安排上来证明我们的方法的有效性。在几种情况下,我们改进了多种现有结果,同时使用简单得多的分析,而在另一些情况下,我们提供了第一个学习理论的保证。