How much data is sufficient to learn high-performing algorithms?
  Generalization guarantees for data-driven algorithm design
  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.
