Name
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 body of 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1137/15M1050276 | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
algorithm selection,parameter tuning,PAC learning,online learning,meta-algorithms | Statistical learning theory,Combinatorics,Computational problem,Stability (learning theory),Computer science,Ranging,Application domain,Artificial intelligence,Population-based incremental learning,Machine learning,Weighted Majority Algorithm,Binary number | Conference |
Volume | Issue | ISSN |
46 | 3 | 0097-5397 |
Citations | PageRank | References |
3 | 0.40 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rishi R. Gupta | 1 | 19 | 4.08 |
| Tim Roughgarden | 2 | 4177 | 353.32 |