While I was performing tests for an upcoming paper on sequential design strategies, I came across the following interesting snippet. I was comparing different sequential design strategies with a standard Latin hypercube using the same number of samples, in order to assess the advantage of using sequential design over the most popular one-shot experimental design: the Latin hypercube. I used the Peaks function, which is a built-in matlab benchmark function, as a test case. The peaks function looks like this:


The Peaks function is the sum of several translated and scaled gaussian distributions. As can be seen on the figure, it is very nonlinear near the origin, but almost flat near the boundaries. It is therefore an excellent function to demonstrate the power of sequential design strategies.

The LOLA-Voronoi hybrid sequential design strategy, which is the default choice when using the SUMO Toolbox, was compared against other methods that are available in the toolbox, using Kriging as the model of choice because it internally uses gaussian basis functions and is therefore expected to model the Peaks function very efficiently. The tests showed that LOLA-Voronoi performed the best of all the methods, needing only 122 samples for an accuracy of 1%. However, how does it compare to a Latin hypercube?

the Latin hypercube used in the SUMO Toolbox is optimized using the algorithm described in:
V. R. Joseph and Y. Hung. Orthogonal-maximin latin hypercube designs. Statistica Sinica, 18:171-186, 2008.


It turns out that a Latin hypercube performs much worse than all of the sequential design strategies, save for random sampling. But what is even more surprising, is the effect that LOLA-Voronoi can have on a Latin hypercube. On average, a 150 sample Latin hypercube was needed to achieve the same accuracy as LOLA-Voronoi with 122 samples. However, if one generated a 145 sample Latin hypercube, augmented with one sample from LOLA-Voronoi, the average error drops below the one obtained from a 150 sample Latin hypercube! One run where the Latin hypercube achieved an error of 1,17% but one extra sample dropped the error to 0,4% is depicted below:

The Latin hypercube samples are drawn as circles, the additional LOLA-Voronoi sample as a square. It can be seen from the figure that the Latin hypercube does a nice job of covering up the design space quite evenly. However, there are some visible gaps, such as the one on the bottom left, the one on the top left and one where the LOLA-Voronoi sample is now located. The first two areas are relatively unimportant, as the peaks function behaves very linearly in these regions. However, the last area is of paramount importance, as it lies on a steep slope near the global optimum of the function. LOLA-Voronoi immediately identifies this region as both highly non-linear and undersampled.

This clearly illustrates that the surrogate modelling community might be giving way too much credit to the Latin hypercube design, especially since a lot of people don't even optimize their Latin hypercube, and just use a randomly generated one! Further tests will be performed to see if this problem also appears in other situations.