A PAC Approach to Application-Specific Algorithm Selection
A PAC Approach to Application-Specific Algorithm Selection
复制标题
用于特定应用算法选择的 PAC 方法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Tim Roughgarden
中科院分区：
文献类型：
--
作者：
Rishi Gupta;Tim Roughgarden
计算问题的最佳算法通常取决于“相关输入”，这个概念取决于应用域，并且通常不违反正式表达。尽管有关于为给定应用程序域选择最佳算法的经验方法的大量文献，但对问题的理论分析却很少。本文将概念从统计和在线学习理论调整为有关应用程序特定算法选择的理由。我们的模型捕获了该问题的几种最先进的经验和理论方法，从自我完善算法到经验绩效模型，我们的结果确定了这些方法可以保证其表现良好的条件。我们提出了一个将算法选择作为统计学习问题建模的框架，我们在这里的工作表明，统计学习理论的维度概念在历史上用来衡量二进制和实数功能的类别的复杂性，这与更广泛的相关性算法上下文。我们还研究了算法选择问题的在线版本，并为存在无需重新学习算法提供了可能性和不可能的结果。
The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem. This paper adapts concepts from statistical and online learning theory to reason about application-specific algorithm selection. Our models capture several state-of-the-art empirical and theoretical approaches to the problem, ranging from self-improving algorithms to empirical performance models, and our results identify conditions under which these approaches are guaranteed to perform well. We present one framework that models algorithm selection as a statistical learning problem, and our work here shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context. We also study the online version of the algorithm selection problem, and give possibility and impossibility results for the existence of no-regret learning algorithms.
影响因子：
14.4
作者：
Hutter, Frank;Xu, Lin;Leyton-Brown, Kevin
通讯作者：
Leyton-Brown, Kevin