Comparison of High-Dimensional Bayesian Optimization Algorithms on BBOB

Maria Laura Santoni, Elena Raponi, Renato De Leone, Carola DoerrarXiv 2023 · arXiv

TL;DR

High-dimensional Bayesian Optimization (HDBO) is a crowded field with many specialized algorithms but few head-to-head comparisons. This paper benchmarks five leading HDBO strategies against standard baselines, finding that trust-region approaches like TuRBO are currently the most robust and efficient, though performance varies significantly across different problem landscapes.

What Problem Does This Paper Address?

Bayesian Optimization (BO) is the gold standard for optimizing "expensive" black-box functions—problems where each evaluation might involve a day-long physics simulation or a costly lab experiment. However, standard BO hits a wall, known as the "curse of dimensionality," once the number of input variables exceeds about 15.

While researchers have proposed numerous HDBO algorithms to overcome this limit, there is no consensus on which approach works best. Most new algorithms are only compared against a few others, often on limited benchmarks. This paper aims to provide a comprehensive, unbiased "leveled ground" for HDBO by comparing five distinct algorithmic strategies across a wide range of problem types and dimensions.

Methods

The authors categorize HDBO strategies into five broad buckets and select a state-of-the-art representative for each:

  1. Variable Selection (SAASBO): Uses a sparsity-inducing prior to identify and focus on the most relevant dimensions.
  2. Additive Models (RDUCB): Assumes the objective function can be decomposed into a sum of lower-dimensional components.
  3. Linear Embeddings (PCA-BO): Projects the high-dimensional search space onto a linear, lower-dimensional manifold using Principal Component Analysis.
  4. Nonlinear Embeddings (KPCA-BO): Similar to PCA-BO, but uses kernel methods to find nonlinear manifolds.
  5. Trust Regions (TuRBO): Abandons the global surrogate model in favor of local "trust regions" to focus the search and avoid over-exploration.

These are compared against three baselines: Vanilla BO, CMA-ES (a popular evolutionary strategy), and Random Search.

Fig. 1. Illustration of the five different categories of BO-based algorithms for high-dimensional problems. The advantages and disadvantages of each category are listed, along with the algorithm chosen for our comparison.

Datasets

The study uses the BBOB (Black-Box Optimization Benchmarking) suite from the COCO environment. This suite consists of 24 noiseless functions that represent diverse landscape challenges, such as:

  • Separable functions
  • Ill-conditioned unimodal functions
  • Multimodal functions with weak or strong global structures

The algorithms were tested at increasing dimensionalities: 10D, 20D, 40D, and 60D, with a strictly limited evaluation budget of $10D + 50$ function calls.

Key Insights and Ideas

  • Trust Regions are the Current Frontrunner: TuRBO (specifically the single trust-region version, TuRBO1) emerged as the most consistently high-performing and computationally efficient algorithm across various dimensions and budgets.
  • The Prohibitive Cost of Sparsity: While SAASBO (Variable Selection) often finds high-quality solutions, it is extremely slow. In 10D, its average CPU time was over 5,000 seconds, compared to just ~10 seconds for TuRBO1.
  • Embeddings are "Sprinters": PCA-BO and KPCA-BO often show rapid initial progress in high dimensions because they simplify the search space early on. However, they frequently plateau as they get stuck in local optima on the reduced manifold.
  • BO Beats CMA-ES on Tight Budgets: A key takeaway for practitioners is that HDBO variants consistently outperform the state-of-the-art evolutionary strategy (CMA-ES) when the evaluation budget is very small, which is exactly the scenario where BO is intended to shine.

Key Results

  • Dimension 10: Vanilla BO remains highly competitive, but TuRBO and SAASBO begin to show advantages.
  • Dimension 40 & 60: The "curse" becomes evident; Vanilla BO and Random Search become non-competitive. TuRBO1 and TuRBOm (multi-trust region) become the only methods to consistently beat CMA-ES across the full budget.
  • Landscape Sensitivity: No single algorithm won every test. For example, RDUCB excelled on specific boundary problems (like function f5), while KPCA-BO was superior on functions with specific global structures (like f9 and f19).
  • Computational Efficiency: TuRBO1 was not only effective but also one of the fastest algorithms to run, making it highly practical for real-world engineering workflows.

Limitations and Future Work

The authors acknowledge that the poor performance of some algorithms on specific functions might be due to suboptimal default hyperparameters, suggesting that HDBO methods might be more sensitive to tuning than previously thought.

Looking forward, the authors propose hybridization as a promising path. For instance, combining the rapid dimensionality reduction of PCA-based embeddings with the robust local search of TuRBO's trust regions could create a "best of both worlds" optimizer for even higher-dimensional problems.

Summary updated

Abstract

Bayesian Optimization (BO) is a class of black-box, surrogate-based heuristics that can efficiently optimize problems that are expensive to evaluate, and hence admit only small evaluation budgets. BO is particularly popular for solving numerical optimization problems in industry, where the evaluation of objective functions often relies on time-consuming simulations or physical experiments. However, many industrial problems depend on a large number of parameters. This poses a challenge for BO algorithms, whose performance is often reported to suffer when the dimension grows beyond 15 variables. Although many new algorithms have been proposed to address this problem, it is not well understood which one is the best for which optimization scenario. In this work, we compare five state-of-the-art high-dimensional BO algorithms, with vanilla BO and CMA-ES on the 24 BBOB functions of the COCO environment at increasing dimensionality, ranging from 10 to 60 variables. Our results confirm the superiority of BO over CMA-ES for limited evaluation budgets and suggest that the most promising approach to improve BO is the use of trust regions. However, we also observe significant performance differences for different function landscapes and budget exploitation phases, indicating improvement potential, e.g., through hybridization of algorithmic components.
BibTeX
@misc{santoni2023comparison,
  author = {Maria Laura Santoni and Elena Raponi and Renato De Leone and Carola Doerr},
  title = {{Comparison of High-Dimensional Bayesian Optimization Algorithms on BBOB}},
  year = {2023},
  eprint = {2303.00890},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.00890},
}

Loading related content...

Figure