The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science, and engineering, practitioners will often fix a family of parameterized algorithms and then optimize those parameters to obtain good performance on example instances from the application domain. In the online setting, we must choose algorithm parameters for each instance as they arrive, and our goal is to be competitive with the best fixed algorithm in hindsight. There are two major challenges in online data-driven algorithm design. First, it can be computationally expensive to evaluate the loss functions that map algorithm parameters to performance, which often require the learner to run a combinatorial algorithm to measure its performance. Second, the losses can be extremely volatile and have sharp discontinuities. However, we show that in many applications, evaluating the loss function for one algorithm choice can sometimes reveal the loss for a range of similar algorithms, essentially for free. We develop online optimization algorithms capable of using this kind of extra information by working in the semi-bandit feedback setting. Our algorithms achieve regret bounds that are essentially as good as algorithms under full-information feedback and are significantly more computationally efficient. We apply our semi-bandit results to obtain the first provable guarantees for data-driven algorithm design for linkage-based clustering and we improve the best regret bounds for designing greedy knapsack algorithms.


翻译:数据驱动算法设计的目标是利用机器学习和数据为特定应用领域获取高效算法。 在AI、科学和工程等许多领域,从业者往往会修复一组参数化算法,然后优化这些参数,以便从应用域的示例中取得良好的性能。在在线设置中,我们必须选择每个实例的算法参数,我们的目标是在后视中与最佳固定算法进行竞争。在在线数据驱动算法设计中存在两大挑战。首先,评估将算法参数映射为性能的亏损功能可能计算成本高昂,而这往往要求学习者运行组合式算法以衡量其性能。第二,损失可能是极不稳定的,并且具有剧烈的不连续性。然而,我们表明在许多应用中,对一个算法选择的损失函数的评估有时可以揭示一系列类似的固定算法的损失,基本上免费。我们开发在线优化算法,通过在半带式反馈环境中工作来使用这种额外信息。我们算法的错觉界限基本上是好的,因为根据全面驱动型算法设计算法,我们用最可靠的算法来改进了最有说服性的数据。

0
下载
关闭预览

相关内容

【DeepMind】强化学习教程,83页ppt
专知会员服务
158+阅读 · 2020年8月7日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
31+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年2月23日
Arxiv
0+阅读 · 2021年2月22日
VIP会员
相关VIP内容
【DeepMind】强化学习教程,83页ppt
专知会员服务
158+阅读 · 2020年8月7日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
31+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员