论文标题
自定义在线算法的ML预测
Customizing ML Predictions for Online Algorithms
论文作者
论文摘要
最近的一系列研究将ML建议纳入在线算法的设计中，以在典型情况下提高其性能。这些论文将ML算法视为黑框，然后重新设计在线算法以利用ML预测。在本文中，我们提出一个互补的问题：我们可以重新设计ML算法以提供更好的在线算法预测吗？我们在经典的租赁或购买问题的背景下探讨了这个问题，并表明将优化基准纳入ML损失功能会导致性能明显更好，同时在建议完全错误时保持最差的对抗性结果。我们通过理论界限和数值模拟支持这一发现。
A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a black-box, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rent-or-buy problem, and show that incorporating optimization benchmarks in ML loss functions leads to significantly better performance, while maintaining a worst-case adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations.
