论文标题
用在线机器学习建议的度量任务系统
Metrical Task Systems with Online Machine Learned Advice
论文作者
论文摘要
机器学习算法旨在根据现有数据对未来进行准确的预测，而在线算法则试图在不了解未来的情况下绑定某些绩效指标（通常是竞争比率）。 Lykouris和Vassilvitskii证明，使用机器学习的预测器增强在线算法，只要预测指标适当准确，就可以降低竞争比率。 在这项工作中，我们将此想法应用于在线度量任务系统问题，该问题是由Borodin，Linial和Saks提出的，作为以在线方式进行动态系统处理任务的通用模型。我们专注于$ n $任务的特定类别统一任务系统，最佳确定性算法为$ O（n）$竞争性，最佳随机算法为$ O（\ log n）$竞争力。 通过在线算法访问机器学习的甲骨文，其绝对预测错误上面以$η_0$限制，我们构造了$θ（\ min（\ sqrt {η_0}，\ log n），\ log n））$竞争性算法，以构成统一的量化算法。我们还给出了$θ（\logη_0）$下限在任何随机算法的竞争比率上。
Machine learning algorithms are designed to make accurate predictions of the future based on existing data, while online algorithms seek to bound some performance measure (typically the competitive ratio) without knowledge of the future. Lykouris and Vassilvitskii demonstrated that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate. In this work we apply this idea to the Online Metrical Task System problem, which was put forth by Borodin, Linial, and Saks as a general model for dynamic systems processing tasks in an online fashion. We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(\log n)$ competitive. By giving an online algorithms access to a machine learned oracle with absolute predictive error bounded above by $η_0$, we construct a $Θ(\min(\sqrt{η_0}, \log n))$ competitive algorithm for the uniform case of the metrical task systems problem. We also give a $Θ(\log η_0)$ lower bound on the competitive ratio of any randomized algorithm.
