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的性能。

0
下载
关闭预览

相关内容

专知会员服务
31+阅读 · 2021年6月12日
专知会员服务
50+阅读 · 2020年12月14日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
R工程化—Rest API 之plumber包
R语言中文社区
11+阅读 · 2018年12月25日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
7+阅读 · 2018年11月5日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
R工程化—Rest API 之plumber包
R语言中文社区
11+阅读 · 2018年12月25日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
7+阅读 · 2018年11月5日
Top
微信扫码咨询专知VIP会员