High-Dimensional Bayesian Optimization

782 concepts592 papers6 proposals

Bayesian Optimization (BO) is a powerful framework for optimizing expensive, black-box functions. By maintaining a probabilistic surrogate model—typically a Gaussian Process (GP)—BO balances exploration and exploitation to find global optima with remarkably few function evaluations.

However, standard BO possesses a well-known Achilles' heel: it struggles to scale when the search space exceeds a few dozen variables. As Frank Hutter notes in Bayesian Optimization for More Automatic Machine Learning, navigating high-dimensional landscapes with hundreds of parameters remains a fundamental bottleneck for automated configuration systems. To understand why BO breaks down in high dimensions, and how modern techniques overcome it, we must look at how dimensionality distorts our models.

Why Standard Bayesian Optimization Fails

The core failure of BO in high dimensions stems from the geometry of high-dimensional spaces—often referred to as the curse of dimensionality.

When the number of input dimensions grows, the volume of the search space expands exponentially. Consequently, any available data points become incredibly sparse. For a standard Gaussian Process kernel (like the Matérn or RBF kernel), similarity is measured by Euclidean distance. In a massive, empty volume, almost every unobserved point is far away from the sampled data.

This sparsity has two catastrophic effects on the surrogate model and the acquisition function:

  1. The Flat Terrain Problem: Far away from data points, the GP surrogate model reverts entirely to its prior mean and maximum uncertainty. As a result, the acquisition function—the mathematical tool used to decide where to sample next—becomes completely flat across vast regions of the search space. Optimization algorithms trying to maximize this acquisition function get stuck in these flat zones, reducing the search to little more than random sampling.
  2. Inefficient Exploration: As highlighted by Xingchen Wan et al. in Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces, global surrogate models fail to accurately map high-dimensional landscapes. This inaccuracy causes the acquisition function to spend its limited evaluation budget over-exploring unpromising regions, destroying sample efficiency.

To make Bayesian Optimization viable in high dimensions, researchers have developed three primary intuition-driven strategies: projecting the space into low-dimensional subspaces, restricting the model to local trust regions, and exploiting structural sparsity.

Projecting into Low-Dimensional Subspaces

A common insight in high-dimensional optimization is that many real-world problems possess a low effective dimensionality. That is, while the parameter space may have hundreds of dimensions, the objective function varies significantly along only a small subset of directions.

Andreas Krause et al. formalized this in High-Dimensional Gaussian Process Bandits by introducing SI-BO. The algorithm uses low-rank matrix recovery to identify a low-dimensional subspace from initial data, and then restricts the subsequent Bayesian Optimization entirely to that compressed subspace. This prevents sample complexity from scaling exponentially with the ambient dimension.

High-Dimensional Space (D) --------[ Random / Linear Projection ]--------> Low-Dimensional Subspace (d)
       (Vast & Sparse)                                                           (Dense & Trackable)

Instead of explicitly learning the subspace, another approach uses random linear embeddings to project the high-dimensional space down to a manageable size. However, naive projections introduce subtle geometric distortions. Benjamin Letham et al. demonstrated in Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization that standard random embeddings suffer from hidden boundary distortions and poor kernel choices. To resolve this, the authors introduced ALEBO, which applies polytope constraints and a custom Mahalanobis kernel to ensure that distances in the low-dimensional embedding accurately reflect the geometry of the original space.

Similarly, David Ginsbourger et al. proposed a geometric warping technique in A Warped Kernel Improving Robustness in Bayesian Optimization Via Random Embeddings to make random embeddings more robust against the misspecification of the lower-dimensional space. Taking this reduction to its extreme, Huong Ha et al. developed BOIDS in BOIDS: High-Dimensional Bayesian Optimization via Incumbent-Guided Direction Lines and Subspace Embeddings, which restricts the optimization search to one-dimensional lines guided by the best solutions found so far (incumbents), preventing the acquisition function from wandering off into vast, unpromising regions.

Thinking Globally, Acting Locally

If mapping a massive high-dimensional space globally is impossible with a small budget, an alternative strategy is to abandon global modeling altogether and focus on local regions where the model can be highly accurate.

The CASMOPOLITAN framework, introduced by Xingchen Wan et al. in Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces, instantiates this by bounding the search within local "trust regions." By focusing the Gaussian Process on a confined volume around the current best solution, the model avoids being overwhelmed by the sparsity of the global space. If a trust region stops showing improvement, the algorithm executes a global restart to discover new promising areas.

This local perspective can be pushed even further by focusing on gradients rather than regions. In Local policy search with Bayesian optimization, Sarah Müller introduces GIBO (Gradient Information with Bayesian Optimization). Instead of attempting to find a global optimum in a high-dimensional space, GIBO uses BO locally to actively select samples that provide the most information about the local gradient. By using BO as a sample-efficient local gradient estimator, the algorithm bypasses the curse of dimensionality entirely, making it highly effective for complex reinforcement learning and policy search tasks.

Exploiting Sparsity and Structural Consistency

A third avenue for scaling BO involves exploiting the structural relationships between the input variables themselves, forcing the model to prioritize parameters that matter.

Bo Chen et al. pioneered this in Joint Optimization and Variable Selection of High-dimensional Gaussian Processes by performing simultaneous optimization and variable selection. By embedding a sparsity-inducing mechanism directly into the Gaussian Process, the model learns on-the-fly which variables are active contributors to the objective function and ignores the noisy, irrelevant dimensions that typically degrade standard BO.

[ Ambient Space ] ---> [ Structural Filter / Elastic Kernel ] ---> [ Active Dimensions ]
  Dim 1 (Active)                                                     Dim 1 (Active)
  Dim 2 (Noise)  ------------------ (Ignored) -------------------->
  Dim 3 (Active)                                                     Dim 3 (Active)

When variables cannot be entirely discarded, we can alter how the model perceives distance across flat landscapes. Santu Rana et al. addressed the flat acquisition function problem in High Dimensional Bayesian Optimization with Elastic Gaussian Process. Their Elastic Gaussian Process (EGP) dynamically stretches and shrinks the kernel length-scales. When the optimizer is stuck in a flat region far from data, the kernel length-scales are altered to create a non-zero gradient, allowing gradient-based acquisition optimizers to find peaks and escape the flat terrain.

Another structural trick is to alter the resolution of the search space hierarchically. In Bayesian Optimization with Clustering and Rollback for CNN Auto Pruning, Hanwei Fan et al. present BOCR. For deep neural networks with hundreds of layers, optimizing each layer independently is sample-prohibitive. BOCR clusters similar dimensions together to optimize in a temporary low-dimensional space, and then "rolls back" to the original high-dimensional space for fine-tuning.

Finally, Junyu Xuan et al. introduce HiBBO in HiBBO: HiPPO-based Space Consistency for High-dimensional Bayesian Optimisation, which borrows mathematical frameworks from long-term sequence modeling to maintain space consistency. This ensures that as the surrogate model scales up, the underlying mathematical mapping remains aligned with the true physical boundaries of the objective function.

Summary

High-dimensional Bayesian Optimization works by recognizing that the curse of dimensionality is primarily a modeling crisis: standard models get lost in empty space. By compressing the search space via subspace embeddings, restricting the focus to local trust regions, or dynamically adjusting kernels to handle structural sparsity, modern high-dimensional BO frameworks successfully restore sample efficiency to complex, black-box optimization problems.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_dimensionality_high_dimensional_341e4931,
  title = {curse of dimensionality (high-dimensional black-box optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-high-dimensional-black-box-optimization/rdr_341e4931508f4fa4b1cf71f799487fd9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_curse_of_dimensionality_high_dimensional_341e4931_v1,
  title = {curse of dimensionality (high-dimensional black-box optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-high-dimensional-black-box-optimization/rdr_341e4931508f4fa4b1cf71f799487fd9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake