program configurations on all inputs from a given set can incur a substantial (sometimes prohibitive) computational burden that can and typically should be avoided, given that poor performance often manifests across a range of inputs. Furthermore, there are situations in which candidate configurations can be discarded without completing runs that exceed a certain time bound, considering the performance measured for other configurations; such runs can be capped, or terminated when that time bound is reached or exceeded. 19

Note, too, the specification of alternative blocks of code that are central to the way a design space is constructed in PbO, necessarily leads to categorical parameters, or parameters with a discrete set of unordered values, and nested alternatives give rise to conditional parameters. Therefore, general methods for algorithm configuration used in the context of PbO must support categorical and conditional parameters, ruling out standard procedures for stochastic and numerical optimization.

Three classes of methods are specifically designed for carrying out algorithm-configuration tasks (see also Hoos13): Racing procedures iteratively evaluate target algorithm configurations on inputs from a given set, using statistical hypothesis tests to eliminate candidate configurations significantly outperformed by other configurations; model-free search procedures use suitably adapted search techniques, particularly stochastic local search methods (such as iterated local search) to explore potentially vast configuration spaces; and sequential model-based optimization (SMBO) methods build a response surface model that relates parameter settings to performance, using the model to iteratively identify promising parameter settings.

Racing procedures were originally introduced to solve model-selection problems in machine learning. 27 When adapted to the problem of selecting a program for a given task from a set of interchangeable candidates, where each candidate may correspond to a configuration of a parameterized algorithm, the key idea is to sequentially evaluate the candidates on a series

Pbo lets human
experts focus
on the creative
task of imagining
possible
mechanisms for
solving given
problems or
subproblems,
while the tedious
job of determining
what works best
in a given
use context
is performed
automatically.

of benchmark inputs and eliminate programs as soon as they fall too far behind the current incumbent, or the candidate with overall best performance at a given stage of the race. A line of work initiated by Birattari et al. in 2002 has more recently led to a procedure dubbed “Iterated F-Race” that is demonstrated effective at solving difficult algorithm-configuration tasks with up to 12 parameters4; there is some indication that Iterated F-Race may also be able to handle substantially more complex situations.

As of this writing, model-free search techniques, most notably the FocusedILS procedure of Hutter et al., 19 represent the state of the art in solving algorithm-configuration problems of the kind that arise in the PbO context. Along with BasicILS, another member of the ParamILS family of algorithm-configuration procedures, 19, 20 it is today the only method that supports categorical and conditional parameters, as well as capping. At the core of the ParamILS framework is Iterated Local Search, or ILS, a versatile, well-known stochastic local-search method that has been applied with great success to a range of difficult combinatorial problems (see, for example, Hoos and Stützle16). ILS iteratively performs phases of simple local search, designed to quickly reach or approach a locally optimal solution of a given problem instance, interspersed with so-called perturbation phases, to escape from local optima. Starting from a local optimum x, ILS performs one perturbation phase in each iteration, followed by a local search phase, with the aim of reaching (or approaching) a new local optimum x´. It then uses a so-called “acceptance criterion” to decide whether to continue the search process from x´ or revert to the previous local optimum, x. Applying this mechanism, ILS aims to solve a given problem instance by exploring the space of its locally optimal solutions. ParamILS performs iterated local search in the configuration space of a given parametric algorithm.

While BasicILS, the simplest variant of ParamILS, evaluates candidate configurations based on a fixed number of target algorithm runs, the more sophisticated FocusedILS procedure uses a heuristic mechanism to per-