A PAC approach to application-specific algorithm selection

DOI10.1145/2840728.2840766MaRDI QIDQ2800559zbMATH OpenOpenAlexFDO

Authors Rishi Gupta, Tim Roughgarden

Publication date 15 April 2016

Published in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.07147

zbMATH Keywords

parameter tuningonline learningalgorithm selectionPAC learningmeta-algorithms

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) General topics in the theory of algorithms (68W01)

Abstract: 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.

Recommendations

• A PAC Approach to Application-Specific Algorithm Selection
• Algorithm survival analysis
• Learning dynamic algorithm portfolios
• The algorithm selection competitions 2015 and 2017
• Summary of algorithm selection problems based on meta-learning

Cited in

(11)

• scientific article; zbMATH DE number 5957329 (Why is no real title available?)
• Comments on: ``On learning and branching: a survey
• A PAC Approach to Application-Specific Algorithm Selection
• Learning dynamic algorithm portfolios
• Parameter selection of pocket extraction algorithm using interaction interface
• Modeling Decisions for Artificial Intelligence
• Algorithm survival analysis
• Learning to branch: generalization guarantees and limits of data-independent discretization
• \textsc{Alors}: an algorithm recommender system
• scientific article; zbMATH DE number 1966528 (Why is no real title available?)
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

This page was built for publication: A PAC approach to application-specific algorithm selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800559)