Published on Thu Aug 08 2019

How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design

Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, Ellen Vitercik

Algorithms often have tunable parameters that impact performance metrics. For many algorithms, no settings admit meaningful worst-case bounds. We provide a theory for deriving generalization guarantees that bound the difference between the algorithm's average performance over the training set and its expected performance.

0
0
0
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.

Sat Nov 14 2020
Artificial Intelligence
Data-driven Algorithm Design
Data driven algorithm design is an important aspect of modern data science. Most of this work comes with no performance guarantees. We survey recent work that helps put data-driven algorithm design on firm foundations.
1
0
1
Thu Apr 18 2019
Machine Learning
Semi-bandit Optimization in the Dispersed Setting
The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. We show that evaluating the loss function for one algorithm choice can sometimes reveal the loss for a range of similar algorithms. We develop online optimization algorithms capable of using this kind of extra information.
0
0
0
Mon Nov 23 2015
Machine Learning
A PAC Approach to Application-Specific Algorithm Selection
This paper adapts concepts from statistical and online learning theory to reason about application-specific algorithm selection. We present one framework that models algorithm selection as a statistical learning problem. We also study the online version of the algorithm selection problem.
0
0
0
Wed Nov 08 2017
Machine Learning
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Data-driven algorithm design is a crucial problem in modern data science. We present general techniques for online and private optimization of the sum of dispersed piecewise Lipschitz functions. We also give matching upper and lower bounds on the exponentiallyutility loss due to privacy.
0
0
0
Sun Jun 21 2020
Artificial Intelligence
Refined bounds for algorithm configuration: The knife-edge of dual class approximability
Automating algorithm configuration is growing increasingly necessary as algorithms come with more tunable parameters. How large should the training set be to ensure that aparameter's average empirical performance is close to its expected, future performance? We answer this question for algorithm configuration problems that exhibit a widely-
0
0
0
Thu Jul 09 2009
Neural Networks
Beyond No Free Lunch: Realistic Algorithms for Arbitrary Problem Classes
We show how the necessary and sufficient conditions for the NFL to apply can be reduced to the single requirement of the set of objective functions under consideration being closed under permutation. Then we provide a more refined definition of performance under which we show that revisiting algorithms are always trumped by enumerative
0
0
0