Bayesian Optimization (BO) is the standard tool for optimizing expensive black-box functions, such as tuning hyperparameters for a deep neural network or designing a new chemical compound. However, BO traditionally suffers from the curse of dimensionality. As the number of input variables increases, the volume of the search space grows exponentially. In a 100-dimensional space, the "middle" of the space is vast, and points become increasingly isolated, making it nearly impossible for a standard Gaussian Process (GP) to build an accurate global map.
To break this wall, researchers have shifted away from trying to model the entire high-dimensional landscape. Instead, they use structural priors—assumptions about how the function behaves—to make the search tractable.
Localizing the Search Space
The most direct way to handle a massive search space is to stop trying to model all of it at once. If we assume the global optimum is likely near a region we’ve already explored, we can focus our computational budget on "trust regions."
David Eriksson and colleagues introduced TuRBO (Scalable Global Optimization via Local Bayesian Optimization), which replaces a single global surrogate model with a collection of local models. By maintaining these local trust regions and managing them with a multi-armed bandit strategy, TuRBO avoids the trap of over-exploring unpromising, high-uncertainty areas in the corners of the high-dimensional cube.
Building on this local philosophy, Lam Ngo and Vu Nguyen proposed using Covariance Matrix Adaptation (CMA) (High-dimensional Bayesian Optimization via Covariance Matrix Adaptation Strategy) to dynamically "zoom in" on promising regions. Rather than fixed boxes, this approach adapts the search shape to the local geometry of the function, allowing BO to scale to hundreds of dimensions.
Exploiting Additive Decompositions
Another powerful structural prior is the assumption that the high-dimensional function is additive. In many real-world problems, variables don't all interact with each other simultaneously; instead, the function might be a sum of several lower-dimensional functions.
Eric Han and Jonathan Scarlett developed a method using tree-structured additive models (High-Dimensional Bayesian Optimization via Tree-Structured Additive Models). By organizing variables into a tree, they can model complex interactions while keeping the underlying GP kernels low-dimensional and computationally efficient.
Interestingly, Juliusz Ziomek and Haitham Bou-Ammar found that we don't even necessarily need to learn the "perfect" decomposition. Their algorithm, RDUCB (Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?), suggests that simply picking random tree-structured decompositions at each step is often superior to data-driven methods that might get stuck on misleading local features.
Identifying Active Subspaces
Not all dimensions are created equal. In many high-dimensional problems, only a small subset of variables—or a linear combination of them—actually drives the function's value.
One way to find these "important" variables is through Group Testing. Carl Hvarfner and Luigi Nardi introduced GTBO (High-dimensional Bayesian Optimization with Group Testing), which uses information theory to quickly identify active dimensions before focusing the optimization budget on them.
Alternatively, we can look for "active subspaces" using gradients. Cyril Picard and Faez Ahmed proposed GIT-BO (GIT-BO: High-Dimensional Bayesian Optimization with Tabular Foundation Models), which leverages a pre-trained transformer (TabPFN) to extract gradient information. This allows the optimizer to project the 500-dimensional problem into a much smaller, more manageable subspace where traditional BO can thrive.
Searching Along Lines and Embeddings
When the space is too large to sample effectively, some researchers suggest restricting the search to one-dimensional paths. Huong Ha and Jeffrey Chan developed BOIDS (BOIDS: High-Dimensional Bayesian Optimization via Incumbent-Guided Direction Lines and Subspace Embeddings), which searches along lines connecting the best-found points (incumbents). By combining this with subspace embeddings, they reduce the complex high-dimensional search into a series of efficient 1D optimizations.
Even in discrete or combinatorial spaces, structural priors help. Jungtaek Kim and Seungjin Choi showed that mapping massive discrete spaces into a continuous convex polytope (Combinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytope) allows standard BO tools to work in spaces that would otherwise be computationally explosive.
Summary
The evolution of high-dimensional Bayesian Optimization is a move from global uncertainty reduction to structured local search. Whether by decomposing the function into additive parts, focusing on trust regions, or projecting the problem into active subspaces, these methods all work by imposing a specific "shape" on the problem, allowing the optimizer to ignore the vast, empty volume of high-dimensional space.