How much data is sufficient to learn high-performing algorithms?
Authors:
Preprint
Abstract
Algorithms -- for example 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 training instances, that parameter setting -- ideally -- will perform well on previously unseen future instances. However, if the set of training instances is too small, average performance will not generalize to future performance. This raises the question: how large should this training 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 provide the first unified sample complexity framework for algorithm parameter configuration; prior research followed case-by-case analyses. We present example applications to diverse domains including biology, political science, economics, integer programming, and clustering.Keywords
All Related Versions
This publication has 29 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
- SCIP: solving constraint integer programsMathematical Programming Computation, 2009
- 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