Benchmarking the Local Metamodel CMA-ES on the Noiseless BBOB'2013 Test Bed

Xin Yao, Dimo Brockhoff, Nikolaus Hansen, Projet Tao Inria, Dolphin Team2013

TL;DR

This paper introduces and benchmarks a "local metamodel" variant of the CMA-ES optimization algorithm (Imm-CMA). By building local quadratic approximations of the objective function, Imm-CMA significantly improves the efficiency of CMA-ES on expensive-to-evaluate problems, often outperforming other state-of-the-art optimizers.

What Problem Does This Paper Address?

Many real-world optimization problems involve objective functions that are computationally expensive to evaluate. This is common in areas like engineering design, scientific simulations, and hyperparameter tuning, where each function evaluation can take minutes, hours, or even days. Traditional optimization algorithms, like CMA-ES, rely on a large number of function evaluations to explore the search space and converge to a solution. When evaluations are costly, this becomes infeasible. The challenge is to develop optimization algorithms that can achieve good performance with a significantly reduced number of function evaluations.

Methods

The core innovation is the Local Metamodel CMA-ES (Imm-CMA). This algorithm builds upon the well-established CMA-ES (Covariance Matrix Adaptation Evolution Strategy), a powerful algorithm for continuous black-box optimization. The key modification is the introduction of a "surrogate-assisted procedure." Instead of directly evaluating candidate solutions on the expensive objective function, Imm-CMA:

  • Builds Local Quadratic Metamodels: For each candidate solution, it constructs a local quadratic approximation (a metamodel) of the objective function. This metamodel is built using a set of previously evaluated points and their corresponding function values.
  • Estimates Function Values: The metamodel is then used to estimate the function value of the candidate solution.
  • Rank-Based Adaptation: Crucially, CMA-ES primarily relies on the ranking of solutions, not their exact function values. Imm-CMA leverages this by using the metamodel to predict the ranking of candidate solutions.
  • Adaptive Acceptance Criterion: A novel aspect is the introduction of a "model-error" based acceptance criterion for the predicted ranking. This criterion is less strict than previous versions, allowing the algorithm to benefit more from the metamodels without being overly penalized by inaccuracies.
  • Efficient Metamodel Construction: The paper also details optimizations in how these metamodels are constructed, including using a smaller number of nearest neighbors from the database of evaluated points when the database is still small.

Datasets

The paper evaluates the Imm-CMA algorithm on the BBOB'2013 (Black-Box Optimization Benchmarking) test bed, specifically the "expensive setting." This benchmark suite consists of 24 diverse objective functions, ranging from simple unimodal functions to complex multimodal and ill-conditioned ones, designed to challenge optimization algorithms. The experiments were conducted in 2D and 20D search spaces.

Key Insights and Ideas

  • Metamodels Pay Off: The local metamodel approach significantly enhances CMA-ES's performance in expensive optimization scenarios. The ability to "predict" function values and rankings with reasonable accuracy dramatically reduces the need for costly direct evaluations.
  • Rank-Based Optimization is Key: The success of Imm-CMA highlights how well CMA-ES's rank-based update mechanism can be leveraged by surrogate models. The metamodels don't need to be perfect; they just need to provide a good enough ranking to guide the search.
  • Trade-offs Exist: While generally beneficial, the metamodeling approach can sometimes be detrimental. The paper notes a significant performance degradation on the "attractive sector function" (f6), suggesting that for certain function landscapes, the metamodel's inaccuracies can mislead the optimizer.
  • Efficiency Gains are Substantial: Imm-CMA often achieves comparable or better results than other advanced optimizers (like BFGS, NEWUOA, and saACM) with far fewer function evaluations, especially for higher dimensions.

Key Results

  • Improved Performance: Imm-CMA consistently outperforms the standard CMA-ES (without metamodeling) on most BBOB functions in the expensive setting.
  • Competitive with State-of-the-Art: The algorithm is competitive with, and often surpasses, other established optimizers like BFGS, NEWUOA, and saACM, particularly in terms of the number of function evaluations required.
  • Significant Speedup: For many functions, Imm-CMA reaches target precision levels with a factor of 2-5 fewer function evaluations compared to IPOP-CMA-ES without metamodeling. In some cases, the improvement is even more dramatic.
  • Specific Function Performance: Imm-CMA shows notable improvements on functions f1, f2, f7, f9, f10, f11, f12, f13, and f14.
  • Detrimental Effect on f6: The "attractive sector function" (f6) is an exception, where Imm-CMA is significantly slower than its non-metamodeling counterpart.

Limitations and Future Work

  • Function-Specific Performance: The paper acknowledges that the metamodeling approach is not universally beneficial and can degrade performance on certain functions (e.g., f6). Future work could explore adaptive strategies to decide when to use metamodels and when to rely on direct evaluations.
  • Metamodel Accuracy: While the rank-based nature of CMA-ES mitigates the need for perfect metamodel accuracy, further research into more robust and accurate metamodeling techniques could yield even greater improvements.
  • Parameter Tuning: The paper mentions that some parameters were tuned through experimentation. Investigating more automated or adaptive parameter tuning strategies for the metamodeling process could be beneficial.
  • Broader Benchmark Testing: While BBOB is a standard, testing Imm-CMA on a wider range of expensive-to-evaluate real-world problems would further validate its practical utility.

Summary updated

Abstract

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
BibTeX
@misc{yao2013benchmarking,
  author = {Xin Yao and Dimo Brockhoff and Nikolaus Hansen and Nikolaus Hansen and Projet Tao Inria and Dolphin Team},
  title = {{Benchmarking the Local Metamodel CMA-ES on the Noiseless BBOB'2013 Test Bed}},
  year = {2013},
}
Figure