How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design
Preprint
Abstract
Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly within the proof of a worst-case approximation ratio or runtime bound. Worst-case instances, however, may be rare or nonexistent in practice. A growing body of research has demonstrated that data-driven algorithm design can lead to significant improvements in performance. This approach uses a training set of problem instances sampled from an unknown, application-specific distribution and returns a parameter setting with strong average performance on the training set. We provide a broadly applicable theory for deriving generalization guarantees that bound the difference between the algorithm's average performance over the training set and its expected performance. Our results apply no matter how the parameters are tuned, be it via an automated or manual approach. The challenge is that for many types of algorithms, performance is a volatile function of the parameters: slightly perturbing the parameters can cause large changes in behavior. Prior research has proved generalization bounds by employing case-by-case analyses of greedy algorithms, clustering algorithms, integer programming algorithms, and selling mechanisms. We uncover a unifying structure which we use to prove extremely general guarantees, yet we recover the bounds from prior research. Our guarantees apply whenever an algorithm's performance is a piecewise-constant, -linear, or -- more generally -- piecewise-structured function of its parameters. Our theory also implies novel bounds for voting mechanisms and dynamic programming algorithms from computational biology.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm2020
- 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
- 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
- Parametric optimization of sequence alignmentAlgorithmica, 1994
- Progressive sequence alignment as a prerequisitetto correct phylogenetic treesJournal of Molecular Evolution, 1987
- An improved algorithm for matching biological sequencesJournal of Molecular Biology, 1982