A PAC Approach to Application-Specific Algorithm Selection
This work addresses the theoretical gap in algorithm selection for application-specific problems, which is incremental as it builds on existing empirical and theoretical approaches.
The paper tackles the problem of selecting the best algorithm for a specific application domain by adapting concepts from statistical and online learning theory, showing conditions under which existing approaches are guaranteed to perform well and providing possibility and impossibility results for no-regret learning in online settings.
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.