We consider the problem of configuring generalpurpose
solvers to run efficiently on problem instances
drawn from an unknown distribution. The
goal of the configurator is to find a configuration
that runs fast on average on most instances, and
do so with the least amount of total work. It can
run a chosen solver on a random instance until
the solver finishes or a timeout is reached. We
propose LEAPSANDBOUNDS, an algorithm that
tests configurations on randomly selected problem
instances for longer and longer time. We
prove that the capped expected runtime of the
configuration returned by LEAPSANDBOUNDS
is close to the optimal expected runtime, while
our algorithm’s running time is near-optimal. Our
results show that LEAPSANDBOUNDS is more efficient
than the recent algorithm of Kleinberg et al.
(2017), which, to our knowledge, is the only other
algorithm configuration method with non-trivial
theoretical guarantees. Experimental results on
configuring a public SAT solver on a new benchmark
dataset also stand witness to the superiority
of our method.