用决策理论提升机器学习预测驱动的算法性能
Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
- 基于确定性与随机性度量，量化预测误差对算法的影响
- 在滑雪租赁、搜索和合约调度问题中实现性能最优选择
- 帮助在无法直接比较的算法中选出最鲁棒的方案
我们系统研究了决策理论度量在带机器学习预测的算法设计与分析中的应用。提出基于确定性度量（如距离评估）和随机性度量的方法，前者用于衡量算法与理想解的接近程度，后者平衡算法性能与不完美预测带来的风险。该框架能全面刻画预测误差下的算法表现，从而在原本不可比的算法类中选出最优者。我们将方法应用于在线决策中的三个经典问题：滑雪租赁、一最大搜索和合约调度。
原文摘要 · Abstract (English)
We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, and stochastic measures that balance the trade-off between the algorithm's performance and the risk associated with the imperfect oracle. These approaches allow us to quantify the algorithm's performance across the full spectrum of the prediction error, and thus choose the best algorithm within an entire class of otherwise incomparable ones. We apply our framework to three well-known problems from online decision making, namely ski-rental, one-max search, and contract scheduling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。