Technical Summary: BAXUS – Adaptive Bayesian Optimization in Nested Subspaces

Problem Statement

High-dimensional Bayesian optimization (HDBO) aims to optimize expensive-to-evaluate black-box functions with dozens to hundreds of input dimensions. While recent advances have extended the scope of Bayesian optimization (BO) to fields like life sciences, neural architecture search, and robotics, state-of-the-art methods face significant limitations as dimensionality increases.

Existing approaches generally fall into two categories, both with critical drawbacks:

1. Trust Region Methods (e.g., TURBO): These optimize over local bounded regions (trust regions) within the full input space. While effective for moderate dimensions, their performance degrades in very high dimensions because the trust regions retain the full dimensionality of the problem, suffering from the curse of dimensionality.
2. Linear Embedding Methods (e.g., REMBO, HESBO, ALEBO): These assume the existence of a low-dimensional "active subspace" and project the high-dimensional input space into a lower-dimensional target space. However, these methods require the user to "guess" the effective dimensionality ($d_e$) of the active subspace. If the chosen target dimensionality ($d$) is too small, the subspace cannot represent the global optimum; if $d$ is too large, optimization slows due to the curse of dimensionality. Furthermore, methods like HESBO rely on random hashing that offers lower worst-case guarantees for containing an optimum compared to other embeddings.

The core challenge is to develop an HDBO method that reliably finds global optima without requiring prior knowledge of the active subspace's dimensionality, while avoiding the performance degradation associated with high-dimensional search spaces.

Methodology: BAXUS

The authors propose BAXUS (Bayesian optimization with adaptively expanding subspaces), a theoretically grounded approach that dynamically adjusts the dimensionality of the optimization space.

1. Adaptive Nested Subspaces

Instead of fixing the target dimensionality, BAXUS operates on a family of nested random subspaces. The algorithm begins with a low-dimensional target space ($d_{init}$) and progressively increases the dimensionality as it collects more data.

• Initialization: BAXUS starts with a small target dimension $d_0$.
• Expansion: As the optimization proceeds, the target dimensionality is increased by "splitting" existing target dimensions. This process continues until the target dimensionality roughly reaches the input dimensionality $D$ or the evaluation budget is exhausted.
• Observation Retention: A critical feature of BAXUS is its ability to retain observations from lower-dimensional spaces when expanding to higher dimensions. When a target dimension is split, the contributing input dimensions are re-assigned to the original dimension and new bins. The function values (observations) are copied to the new dimensions, ensuring that data collected in the low-dimensional phase remains valid in the higher-dimensional phase.

2. The Sparse BAXUS Embedding

BAXUS utilizes a novel sparse linear embedding to map the target space $Y \in \mathbb{R}^d$ to the input space $X \in \mathbb{R}^D$.

• Structure: The embedding matrix $S^\top \in \{0, \pm 1\}^{d \times D}$ is sparse, meaning each column (input dimension) has exactly one non-zero entry.
• Bin Balancing: Unlike HESBO, which assigns input dimensions to target dimensions uniformly at random (leading to variable bin sizes), BAXUS enforces that the number of contributing input dimensions per target dimension (bin size) differs by at most one. This "balanced" assignment is achieved by permuting input dimensions and splitting them into $d$ bins.
• Theoretical Advantage: The authors prove that this balanced sparse embedding provides a strictly higher worst-case success probability (the probability that the target space contains a global optimum) than the HESBO embedding for finite input dimensions. As $D \to \infty$, the success probability of BAXUS converges to that of HESBO.

3. Trust Region and Splitting Strategy

BAXUS integrates the embedding expansion with a Trust Region (TR) approach similar to TURBO:

• Trust Regions: Optimization occurs within hyper-rectangular trust regions in the target space, scaled by GP length scales.
• Expansion Trigger: The target dimensionality is increased when the trust region base side length falls below a minimum threshold (indicating the current region is too small or the algorithm is stuck).
• Failure Control: The number of allowed "failures" (consecutive iterations without improvement) before a split occurs is scaled down based on the current target dimensionality. This ensures the algorithm can reach high dimensionalities within a fixed evaluation budget.
• Convergence: The algorithm is proven to achieve global convergence. Once the target dimensionality reaches the input dimensionality $D$, BAXUS behaves like TURBO, which is known to converge globally.

Key Contributions

1. Algorithm Development: The authors introduce BAXUS, which reliably achieves excellent solutions on a broad set of high-dimensional tasks, outperforming current state-of-the-art methods.
2. Novel Embedding Theory: They present a new family of nested random embeddings with three key properties:
   • It provides a larger worst-case guarantee for containing a global optimum compared to the HESBO embedding.
   • It is an optimal sparse embedding, meaning no other sparse embedding has a higher worst-case success probability for the same input, target, and effective dimensionalities.
   • Its probability of containing an optimum converges to the HESBO probability as input dimensionality $D \to \infty$.
3. Comprehensive Evaluation: The paper provides extensive empirical evidence demonstrating BAXUS's superiority over TURBO, SAASBO, ALEBO, HESBO, CMA-ES, and random search across diverse benchmarks.

Experimental Results

The authors evaluated BAXUS on a collection of 388-dimensional hyperparameter optimization tasks, 124-dimensional design problems, and benchmarks with known active subspaces (LASSO, MOPTA08, BRANIN, HARTMANN).

• Performance: BAXUS consistently outperformed state-of-the-art methods. On the 388D SVM benchmark, BAXUS adapted to the appropriate target dimensionality and found better solutions faster than TURBO and CMA-ES. On the 1000D LASSO-HARD benchmark, BAXUS achieved considerably better solutions than all competitors, including methods that rely on active subspace assumptions (SAASBO, ALEBO, HESBO), which failed to benefit from the active subspace structure.
• Robustness: BAXUS demonstrated robustness to observational noise, maintaining strong performance on noisy variants of benchmarks where competitors like SAASBO and CMA-ES degraded significantly.
• Ablation Studies: Replacing the BAXUS embedding with a nested HESBO embedding resulted in significantly worse performance, confirming that the balanced binning strategy is a key driver of success.
• Comparison to Fixed Embeddings: BAXUS outperformed running TURBO with a fixed target dimensionality, showing that the adaptive expansion strategy is superior to static choices of $d$.

Significance and Claims

The paper claims that BAXUS addresses the critical limitations of current HDBO methods by removing the need for practitioners to "guess" the effective dimensionality of the problem. By adaptively expanding the search space, BAXUS leverages the efficiency of low-dimensional optimization while guaranteeing that the search space eventually covers the full input space, thus ensuring the global optimum is reachable.

The authors assert that BAXUS is a "ready-to-use" (out-of-the-box) optimizer that achieves robust performance across a wide variety of high-dimensional tasks without requiring specific assumptions about the problem structure (such as axis-aligned active subspaces). The work aims to make high-dimensional Bayesian optimization more accessible and reliable for applications in science and industry where the number of tunable parameters is large and their effective dimensionality is unknown.