Customizing ML Predictions for Online Algorithms
Customizing ML Predictions for Online Algorithms
复制标题
DOI：
10.48550/arxiv.2205.08715
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Keerti Anand;Rong Ge;Debmalya Panigrahi
中科院分区：
文献类型：
--
作者：
Keerti Anand;Rong Ge;Debmalya Panigrahi
最近的一项研究将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.