  A common challenge in computer experiments and related fields is to
efficiently explore the input space using a small number of samples, i.e., the
experimental design problem. Much of the recent focus in the computer
experiment literature, where modeling is often via Gaussian process (GP)
surrogates, has been on space-filling designs, via maximin distance, Latin
hypercube, etc. However, it is easy to demonstrate empirically that such
designs disappoint when the model hyperparameterization is unknown, and must be
estimated from data observed at the chosen design sites. This is true even when
the performance metric is prediction-based, or when the target of interest is
inherently or eventually sequential in nature, such as in blackbox (Bayesian)
optimization. Here we expose such inefficiencies, showing that in many cases
purely random design is superior to higher-powered alternatives. We then
propose a family of new schemes by reverse engineering the qualities of the
random designs which give the best estimates of GP lengthscales. Specifically,
we study the distribution of pairwise distances between design elements, and
develop a numerical scheme to optimize those distances for a given sample size
and dimension. We illustrate how our distance-based designs, and their hybrids
with more conventional space-filling schemes, outperform in both static
(one-shot design) and sequential settings.
