In global optimization, evaluating a target function is often computationally expensive—such as running a complex climate simulation or training a large deep learning model. To navigate this efficiently, practitioners rely on Bayesian Optimization. This approach builds a cheaper mathematical proxy, typically a Gaussian Process (GP) surrogate model, and uses a merit function (like Expected Improvement, or EI) to determine the most promising next point to sample.
However, this introduces a secondary problem: the merit function itself is notoriously difficult to optimize. It is typically "spiky," riddled with local optima, and traditionally searched using brute-force grids or random sampling. As the dimensionality of the problem increases, this search becomes a massive computational bottleneck. This paper addresses the irony of "surrogating the surrogate"—the need for a smart optimization strategy for the tool that is supposed to be doing the optimizing.
The Mixture Cross-Entropy Method (MCEM)
To replace slow, exhaustive grid searches, the authors propose a novel optimization loop based on the Cross-Entropy Method (CEM), enhanced with two key innovations:
- Mixture Proposals: Standard CEM fits a single Gaussian distribution to the "best" points found so far. Because merit functions are highly multimodal (containing many peaks), a single Gaussian often collapses onto a local peak too early. The authors extend CEM to use a Mixture of Gaussians, allowing the algorithm to track multiple promising regions of the search space simultaneously.
- Delaunay Triangulation Initialization: A major challenge with mixture models is determining where to place the initial components. Since merit functions usually peak in the "empty spaces" between known samples, the authors use Delaunay triangulation on the existing data points. They place the initial mixture components at the centers of these triangles (simplices), effectively targeting the gaps in current knowledge.
Benchmark Functions
The algorithm was evaluated on three classic synthetic optimization benchmarks, representing different landscape challenges in 2D, 10D, and 50D settings:
- Sphere Function: Smooth and unimodal (the baseline "easy" case).
- Rastrigin Function: Highly multimodal with a regular, grid-like structure.
- Ackley Function: Highly multimodal with a very flat outer region and a steep central hole.
Key Insights and Results
The Expected Improvement (EI) function is zero at every previously sampled point and positive elsewhere, creating a landscape full of narrow peaks. The mixture approach acts as an automatic tuning mechanism: it explores broadly at first and naturally phases out mixture components that fall into low-merit areas, eventually concentrating its budget on the global optimum.
Experimental results highlight several major advantages of the MCEM approach:
- Outperforming Brute Force: In 2D scenarios, the mixture method found better points than a standard grid search while requiring significantly fewer function evaluations.
- Scaling to High Dimensions: In 10D and 50D settings, the method significantly outperformed Latin Hypercube Sampling (LHS), the industry standard for searching merit functions.
- Robustness: On the notoriously difficult Ackley function, the mixture approach demonstrated outstanding robustness to budget reductions. Even with very few evaluations of the merit function, it consistently identified high-quality points to sample next.
- Superiority of Mixtures: The experiments confirmed that the mixture version is strictly superior to the single-Gaussian version when the underlying fitness function is multimodal.
Limitations and Future Work
While highly effective, the method has limitations. The most prominent is the curse of dimensionality in triangulation. Delaunay triangulation becomes computationally prohibitive as dimensions increase (typically failing above 6D). For the 10D and 50D tests, the authors had to rely on a simplified heuristic—sampling corners of the search space—rather than full triangulation.
Additionally, the process of removing ("killing") mixture components whose weights drop too low is currently handled by a simple threshold. The authors suggest that a more principled birth/death process, perhaps utilizing Reversible Jump MCMC, could make the algorithm even more robust. Finally, if GP hyperparameters are sampled via MCMC, future work could explore initializing mixture components based on the surrogate's covariance structure.
Summary updated