  Black box optimization requires specifying a search space to explore for
solutions, e.g. a d-dimensional compact space, and this choice is critical for
getting the best results at a reasonable budget. Unfortunately, determining a
high quality search space can be challenging in many applications. For example,
when tuning hyperparameters for machine learning pipelines on a new problem
given a limited budget, one must strike a balance between excluding potentially
promising regions and keeping the search space small enough to be tractable.
The goal of this work is to motivate -- through example applications in tuning
deep neural networks -- the problem of predicting the quality of search spaces
conditioned on budgets, as well as to provide a simple scoring method based on
a utility function applied to a probabilistic response surface model, similar
to Bayesian optimization. We show that the method we present can compute
meaningful budget-conditional scores in a variety of situations. We also
provide experimental evidence that accurate scores can be useful in
constructing and pruning search spaces. Ultimately, we believe scoring search
spaces should become standard practice in the experimental workflow for deep
learning.
