arXiv:2411.08332cs.DScs.LG2024-11被引 2

用机器学习预测提升在线优化算法性能,准确时突破理论极限,错误时仍稳健。

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems

  • 基于预测与经典算法动态切换,应对凹目标在线打包问题。
  • 扩展对偶方法,解决凸目标在线覆盖问题,打破传统性能瓶颈。
  • 适合需实时决策且有预测能力的系统,如资源调度、在线广告。

近年来,学习增强型算法因机器学习预测器的发展而受到广泛关注,可为经典算法提供额外信息。这类预测在在线问题中尤为有效——决策需在未知未来的情况下做出,传统算法常面临性能上限的不可能性结果。学习增强型算法旨在谨慎利用外部建议:当预测准确时,突破经典不可能性限制;当预测错误时,仍保持与最优经典在线算法相当的性能。本文提出两类基础优化问题的学习增强框架:针对具有凹目标的在线打包问题,设计了一种简单但通用的策略,根据预测结果在建议与经典算法间切换;针对具有凸目标的在线覆盖问题,大幅扩展了Azar等人(FOCS 2016)的对偶方法及现有线性规划覆盖的增强框架,适用于更多新场景。实验表明,当预测准确时,算法可突破原有性能极限;即使预测错误,其表现仍与当前最优经典在线算法相当。

原文摘要 · Abstract (English)

Learning-augmented algorithms have been extensively studied across the computer science community in the recent years, driven by advances in machine learning predictors, which can provide additional information to augment classical algorithms. Such predictions are especially powerful in the context of online problems, where decisions have to be made without knowledge of the future, and which traditionally exhibits impossibility results bounding the performance of any online algorithm. The study of learning-augmented algorithms thus aims to use external advice prudently, to overcome classical impossibility results when the advice is accurate, and still perform comparably to the state-of-the-art online algorithms even when the advice is inaccurate. In this paper, we present learning-augmented algorithmic frameworks for two fundamental optimizations settings, extending and generalizing prior works. For online packing with concave objectives, we present a simple but overarching strategy that switches between the advice and the state-of-the-art online algorithm. For online covering with convex objectives, we greatly extend primal-dual methods for online convex covering programs by Azar et al. (FOCS 2016) and previous learning-augmented framework for online covering linear programs from the literature, to many new applications. We show that our algorithms break impossibility results when the advice is accurate, while maintaining comparable performance with state-of-the-art classical online algorithms even when the advice is erroneous.

在线算法学习增强凸优化预测

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。