This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.
翻译:本文利用机算学预测来设计网上转换问题的竞争性算法,目的是在预测准确(即一致性)的情况下改进竞争比率,同时保证最差的竞争性比率,而不论预测质量(即稳健)如何。我们把整体转换和分数转换问题的算法设计(也称为 " 1-最大搜索和单向交易问题 " )合并成一类在线阈值算法(OTA)。通过将预测纳入OTA的设计,我们实现了Pareto-最优化的一致性和稳健性权衡,即任何在线算法都无法为稳健保证提供更好的一致性保证。我们用比特币转换的数字实验来证明OTA的性能。