How much data is sufficient to learn high-performing algorithms?
Authors:
Preprint
Abstract
Algorithms for scientific analysis typically have tunable parameters that significantly influence computational efficiency and solution quality. If a parameter setting leads to strong algorithmic performance on average over a set of typical problem instances, that parameter setting---ideally---will perform well in the future. However, if the set of typical problem instances is small, average performance will not generalize to future performance. This raises the question: how large should this set be? We answer this question for any algorithm satisfying an easy-to-describe, ubiquitous property: its performance is a piecewise-structured function of its parameters. We are the first to provide a unified sample complexity framework for algorithm parameter configuration; prior research followed case-by-case analyses. We present applications from diverse domains, including biology, political science, and economics.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Efficiency and budget balance in general quasi-linear domainsGames and Economic Behavior, 2019
- Robertsʼ Theorem with neutrality: A social welfare ordering approachGames and Economic Behavior, 2012
- Information-theoretic approaches to branching in searchDiscrete Optimization, 2011
- The RPR2 rounding technique for semidefinite programsJournal of Algorithms, 2006
- Large-scale comparison of protein sequence alignment algorithms with structure alignmentsProteins: Structure, Function, and Bioinformatics, 2000
- Amicable divorce: Dissolving a partnership with simple mechanismsJournal of Economic Theory, 1992
- Detecting homology of distantly related proteins with consensus sequencesJournal of Molecular Biology, 1987
- Progressive sequence alignment as a prerequisitetto correct phylogenetic treesJournal of Molecular Evolution, 1987
- An improved algorithm for matching biological sequencesJournal of Molecular Biology, 1982
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981