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倍的样本复杂度。