A benchmark of kriging-based infill criteria for noisy optimization

Victor Picheny, Tobias Wagner, David Ginsbourger2015 · DOI

TL;DR

This paper benchmarks various "infill criteria" for optimizing functions that produce noisy outputs, a common challenge in real-world engineering and scientific problems. They found that no single method is universally best, but the Augmented Expected Improvement (AEI) criterion generally performs well, offering a good balance between exploration and exploitation.

What Problem Does This Paper Address?

Many real-world optimization problems involve simulations or experiments that are expensive to run and produce results with inherent noise. This noise makes it difficult to accurately assess the true performance of a design or parameter setting. Traditional optimization methods, which assume deterministic outputs, struggle in these noisy environments. Kriging, a statistical technique for building surrogate models, can be adapted for noisy data, but choosing the right strategy for deciding where to take the next noisy measurement (the "infill criterion") is crucial for efficient optimization. This paper aims to provide a comprehensive comparison of these kriging-based infill criteria for noisy optimization to guide practitioners.

Methods

The authors compare ten different kriging-based infill criteria. They first establish a unified framework for these criteria, which are essentially strategies for selecting the next point to evaluate. The core idea behind most of these criteria is to balance "exploration" (searching new, potentially promising areas of the design space) and "exploitation" (refining the search around the current best-known solution).

Key methods and concepts include:

  • Kriging: A Gaussian process regression technique used to build a statistical model of the objective function. They consider both Ordinary Kriging (OK) and Kriging with noisy observations.
  • Infill Criteria: These are functions that quantify the "utility" of evaluating a new point. Examples include:
  • Expected Improvement (EI): A classic criterion that aims to maximize the expected improvement over the current best solution.
  • Expected Improvement with Plugin (EI-plugin): Variants that use an estimate of the true minimum instead of the observed noisy minimum.
  • Augmented Expected Improvement (AEI): An EI variant that includes a penalty term to account for noise and encourage exploration.
  • Reinterpolation: A method that builds a separate, noise-free kriging model based on the predictions of a noisy model.
  • Expected Quantile Improvement (EQI): A criterion that uses quantiles of the kriging model to account for uncertainty.
  • Quantile Minimization: Directly minimizing the kriging quantile.
  • Benchmark Design: They created a benchmark using six analytical test functions with varying properties (unimodal/multimodal, different dimensions). These functions were made noisy by adding Gaussian noise. They systematically varied factors like noise level, budget (number of evaluations), initial design size, and covariance kernel.
  • Optimization of Infill Criteria: Since infill criteria themselves can be multimodal, they used a hybrid evolutionary algorithm and gradient descent (genoud) to find the maximum of the infill criterion at each step.

Datasets

The paper uses six widely-used analytical benchmark functions, which are standard in optimization research. These functions were modified to simulate noisy evaluations by adding Gaussian noise. The noise levels were set to 5%, 20%, and 50% of the objective function's standard deviation. The authors also created a benchmark setup by systematically varying parameters like the number of dimensions, noise levels, and evaluation budgets.

Key Insights and Ideas

  • No Silver Bullet: The most significant finding is that no single infill criterion consistently outperforms all others across all tested scenarios. The "best" method is problem-dependent.
  • AEI as a Strong Contender: The Augmented Expected Improvement (AEI) criterion emerged as a generally robust and effective choice, often performing well and rarely being among the worst. Its ability to balance exploration and exploitation, particularly through its penalization term for noise, seems key.
  • Plugin Strategies Can Be Tricky: Simple "plugin" strategies (like using the minimum observed noisy value as a proxy for the true minimum) can be problematic. Using the kriging mean as a plugin (as in AEI) or quantiles (as in EQI) appears more robust.
  • Limited Impact of Some Factors: Surprisingly, the choice of covariance kernel (Gaussian vs. Matérn) and the size of the initial design of experiments had a less significant impact on performance than expected. This suggests that the robustness of the kriging model and the infill criterion itself are more critical.
  • Noise is a Major Challenge: The performance of criteria varied significantly with noise levels, highlighting the difficulty of optimizing noisy functions.
  • Reinterpolation's Niche: The reinterpolation method, while designed for deterministic noise, showed good performance in some cases but struggled with higher noise levels, potentially due to its reliance on accurate covariance parameter estimation.

Key Results

  • AEI's Consistent Performance: AEI was frequently among the best methods and rarely performed poorly.
  • PI50 Outperforms PI90: The Expected Improvement with plugin using the kriging mean (PI50) generally outperformed the version using a high quantile (PI90), suggesting that using the mean is a more stable approach.
  • MQ10 vs. MQ50: Minimizing a low quantile (MQ10) was found to be better than minimizing the best predictor (MQ50), reinforcing the idea that considering uncertainty is beneficial.
  • RI's Exploratory Nature: The Reinterpolation (RI) criterion showed good performance in some scenarios, particularly with lower noise and budgets, due to its exploratory nature and avoidance of replications. However, its performance degraded with higher noise.
  • Random Search as Baseline: The study confirmed that most of the tested infill criteria significantly outperform random search, although some challenging scenarios (high noise, specific functions) showed that even advanced methods can struggle to beat random search.

Limitations and Future Work

  • Limited Scope of "Best": The authors acknowledge that their conclusions are specific to the benchmark setup and may not generalize to all noisy optimization problems. Different noise characteristics, function landscapes, or budget constraints could lead to different optimal criteria.
  • Covariance Parameter Estimation: The paper highlights that the quality of covariance parameter estimation is a well-known challenge in kriging and significantly impacts performance. While they used standard methods, further research into robust estimation techniques could be beneficial.
  • User Preference: The choice of infill criterion can also depend on user preferences, such as a desire to avoid replications (RI), enhance uncertainty reduction (EQ90), or ease implementation (MQ10, PI50).
  • Future Work: The authors suggest exploring scenarios with very large budgets and/or very small noise levels, as performance differences might become more pronounced. Investigating the impact of different noise distributions beyond Gaussian noise is also a potential avenue. Further research into the trade-offs between criterion complexity and performance is also warranted.

Summary updated

Abstract

Responses of many real-world problems can only be evaluated perturbed by noise. In order to make an efficient optimization of these problems possible, intelligent optimization strategies successfully coping with noisy evaluations are required. In this article, a comprehensive comparison of existing kriging-based methods for the optimization of noisy functions is provided. Ten methods are described using a unified formalism, and compared on analytical benchmark problems with different configurations (noise level, maximum number of observations, initial number of observations). It is found that the optimal method depends on the optimization problem, even though some criteria are consistently more efficient than others.
BibTeX
@misc{picheny2015benchmark,
  author = {Victor Picheny and Tobias Wagner and David Ginsbourger},
  title = {{A benchmark of kriging-based infill criteria for noisy optimization}},
  year = {2015},
  doi = {10.7892/boris.41521},
}
Figure