论文标题
通过预测的算法的学习预测
Learning Predictions for Algorithms with Predictions
论文作者
论文摘要
算法设计中迅速发展的范式是具有预测的算法领域，其中算法可以利用对问题的某些方面的可能性预测。尽管许多工作集中在使用预测来改善竞争比率，运行时间或其他绩效指标上，但努力减少了如何获得预测本身的问题，尤其是在关键的在线环境中。我们引入了一种学习预测因素的算法的一般设计方法：（1）确定性能度量对预测质量的功能依赖性，以及（2）应用在线学习中的技术来学习预测指标，调整稳健性的一致性权衡，并限制样本复杂性。我们通过将其应用于双方匹配，滑雪租赁，页面迁移和工作计划来证明我们的方法的有效性。在几种情况下，我们可以改善现有结果，同时利用更简单的分析，而在其他情况下，我们提供了第一个学习理论保证。
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.
