Expected Improvement versus Predicted Value in Surrogate-Based Optimization
Surrogate-based optimization relies on so-called infill criteria (acquisition functions) to decide which point to evaluate next. When Kriging is used as the surrogate model of choice (also called Bayesian optimization), then one of the most frequently chosen criteria is expected improvement. Yet, we argue that the popularity of expected improvement largely relies on its theoretical properties rather than empirically validated performance. A few select results from the literature show evidence, that under certain conditions, expected improvement may perform worse than something as simple as the predicted value of a surrogate model. Both infill criteria are benchmarked in an extensive empirical study on the `BBOB' function set. Importantly, this investigation includes a detailed study of the impact of problem dimensionality on algorithm performance. The results support the hypothesis that exploration loses importance with increasing problem dimensionality. A statistical analysis reveals that the purely exploitative search with the predicted value criterion performs better on most problems of five or more dimensions. Possible reasons for these results are discussed. We give an in-depth guide for choosing between both infill criteria based on a priori knowledge about a given problem, its dimensionality, and the available evaluation budget.
READ FULL TEXT