Automating algorithm configuration is growing increasingly necessary as algorithms come with more and more tunable parameters. It is common to tune parameters using machine learning, optimizing performance metrics such as runtime and solution quality. The training set consists of problem instances from the specific domain at hand. We investigate a fundamental question about these techniques: how large should the training set be to ensure that a parameter's average empirical performance over the training set is close to its expected, future performance? We answer this question for algorithm configuration problems that exhibit a widely-applicable structure: the algorithm's performance as a function of its parameters can be approximated by a "simple" function. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. On the flip side, if the approximation holds only under the L-p norm for p smaller than infinity, it is not possible to provide meaningful sample complexity bounds in the worst case. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science. Via experiments, we obtain sample complexity bounds that are up to 700 times smaller than the previously best-known bounds.


翻译:自动算法配置随着算法的参数越来越多而变得越来越必要。 使用机器学习来调整参数, 优化运行时间和溶液质量等性能衡量标准是常见的。 训练组由手头特定领域的问题案例组成。 我们调查有关这些技术的基本问题: 训练组的规模应该有多大才能确保参数在训练组中的平均实证性能接近预期, 未来的性能? 我们回答关于算法配置问题的问题, 显示一个广泛适用的结构: 算法作为参数函数的性能可以用一个“ 简单” 功能来比较。 我们显示, 如果这个近似值维持在L- 无限标准之下, 我们就能提供强大的样本复杂度。 在翻转一面, 如果接近点只维持在L- p 规范之下, 其精度小于其精度, 则不可能在最坏的情况下提供有意义的样本复杂度界限。 我们从经验角度评估了我们的参数界限, 这是计算机科学中最强大的工具之一。 我们的实验, 我们获得了比先前最著名的范围小700倍的样本复杂度。

0
下载
关闭预览

相关内容

【AAAI2021】对比聚类,Contrastive Clustering
专知会员服务
78+阅读 · 2021年1月30日
专知会员服务
20+阅读 · 2020年9月2日
因果图,Causal Graphs,52页ppt
专知会员服务
250+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
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日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年2月24日
VIP会员
相关VIP内容
【AAAI2021】对比聚类,Contrastive Clustering
专知会员服务
78+阅读 · 2021年1月30日
专知会员服务
20+阅读 · 2020年9月2日
因果图,Causal Graphs,52页ppt
专知会员服务
250+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
相关资讯
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日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员