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:
- Variable Selection (SAASBO): Uses a sparsity-inducing prior to identify and focus on the most relevant dimensions.
- Additive Models (RDUCB): Assumes the objective function can be decomposed into a sum of lower-dimensional components.
- Linear Embeddings (PCA-BO): Projects the high-dimensional search space onto a linear, lower-dimensional manifold using Principal Component Analysis.
- Nonlinear Embeddings (KPCA-BO): Similar to PCA-BO, but uses kernel methods to find nonlinear manifolds.
- 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.
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