Technical Summary: Scalable Batch Bayesian Optimization Via Subspace Acquisition Functions

Problem Statement

Bayesian Optimization (BO) is a powerful framework for solving expensive, black-box optimization problems. While standard BO operates sequentially, selecting one sample point at a time, this approach is inefficient when parallel computing resources are available. To leverage parallelism, Batch Bayesian Optimization algorithms are required to evaluate multiple samples simultaneously.

However, existing batch approaches face significant scalability issues as the batch size ($q$) increases:

• Multi-point Expected Improvement (qEI): While theoretically sound, optimizing qEI involves a search space of dimension $d \times q$ (where $d$ is the problem dimension). As $q$ grows, the computational cost of evaluating the multivariate cumulative distribution function and the difficulty of optimizing the acquisition function increase exponentially, rendering qEI and its variants (e.g., FqEI, qLogEI) impractical for large batch sizes (typically $q > 10$).
• Heuristic Approaches (e.g., Kriging Believer, Constant Liar, Local Penalization): These methods often rely on "fake" points or artificial penalty functions to simulate batch effects. As the batch size increases, the accumulation of these artificial points degrades the accuracy of the Gaussian Process (GP) model, potentially misleading the search direction and reducing optimization efficiency.
• Multi-objective and Multi-model Approaches: Methods that train multiple surrogate models or solve multi-objective optimization problems often incur high computational costs that do not scale well with large batch sizes.

The core challenge addressed in this work is designing a batch acquisition strategy that remains computationally tractable and effective for large-scale batch evaluations without suffering from the curse of dimensionality or model degradation.

Methodology

The authors propose a novel approach called Subspace Acquisition Functions, which extends existing acquisition functions (specifically Expected Improvement, but also adaptable to PI and UCB) to operate within randomly selected, axis-aligned subspaces.

Core Concept: Subspace Expected Improvement (SSEI)

Instead of searching for $q$ points in the full $d$-dimensional design space simultaneously, the method:

1. Selects Subspaces: Randomly selects a set of axis-aligned subspaces. A $k$-dimensional axis-aligned subspace is defined by choosing $k$ coordinates from the original $d$ dimensions while fixing the remaining $d-k$ coordinates to the values of the current best solution ($x_{min}$).
2. Optimizes Locally: For each selected subspace, the standard acquisition function (e.g., EI) is optimized only over the $k$ active variables. The unselected variables remain fixed at $x_{min}$.
3. Generates Batch: One query point is selected from each unique subspace. If the required batch size $q$ exceeds the number of available subspaces ($N = 2^d - 1$), the method employs Subspace Multi-Point Expected Improvement (SSqEI), which optimizes multiple points within a single subspace.

Computational Framework

The proposed algorithm (Algorithm 1) operates as follows:

• Initialization: Generate initial samples and train a GP model.
• Subspace Selection: Randomly draw an integer $k \in [1, d]$ and then a random combination of $k$ coordinates to form a subspace. This avoids the computational expense of enumerating all possible subspaces.
• Acquisition Optimization:
  • If $q \le N$: Select $q$ distinct subspaces and optimize the standard SSEI in each to find one point per subspace.
  • If $q > N$: Distribute the $q$ points across the available $N$ subspaces (optimizing multiple points per subspace using SSqEI).
• Evaluation: Evaluate the resulting batch of $q$ points in parallel.
• Update: Update the GP model with the new observations and repeat.

The dimensionality of the optimization problem for the acquisition function is reduced from $d \times q$ to approximately $k \times 1$ (or $k \times q_i$ for SSqEI), where the expected dimension $E[k] \approx d/2$. This significantly reduces the complexity of the acquisition optimization.

Key Contributions

1. Scalable Batch Strategy: The paper introduces a method to extend Bayesian optimization to large batch sizes by decoupling the batch selection into independent or low-dimensional subspace optimizations, avoiding the exponential complexity of qEI.
2. Simplicity and Generality: The approach requires no additional hyperparameters and is applicable to a wide range of acquisition functions (demonstrated on EI, PI, and UCB). It is conceptually simple: "draw subspaces, optimize locally, aggregate."
3. Robustness to Dimensionality: By restricting the search to axis-aligned subspaces anchored at the current best solution, the method naturally balances exploration (via random subspace selection) and exploitation (via local search around $x_{min}$), making it particularly effective in high-dimensional spaces.

Experimental Results

The authors evaluated the proposed method (SSEI) against ten state-of-the-art batch algorithms (including qEI, qLogEI, FqEI, TuRBO, MSMR, MACE, PEI, EIMI, KB, and Random Search) on 60 synthetic benchmark problems (GPMean, SumSquares, Rosenbrock, etc.) across dimensions $d \in \{2, 4, 8, 10, 20, 30\}$ and batch sizes $q \in \{1, 2, 4, 8, 16, 32, 64, 128\}$.

• Performance vs. Sequential BO: When $q=1$, SSEI performs similarly to standard EI on low-dimensional problems but significantly outperforms it on high-dimensional problems ($d \ge 8$). The authors attribute this to the fact that sequential EI struggles to optimize the acquisition function in high dimensions, whereas SSEI's local subspace search finds better local optima for the acquisition function.
• Scalability with Batch Size:
  • Small to Medium Batches ($q \le 32$): SSEI achieves nearly linear speedup in terms of wall-clock time (iterations) while maintaining performance comparable to or better than other batch methods when measured by function evaluations.
  • Large Batches ($q = 128$): SSEI significantly outperforms all compared batch algorithms, including qEI variants which fail or degrade significantly at this scale. The proposed method converges faster and finds better final solutions.
• Comparison with Specific Algorithms:
  • vs. qEI/qLogEI/FqEI: SSEI is superior, especially as $d$ and $q$ increase, because it avoids the $d \times q$ dimensionality curse.
  • vs. TuRBO: SSEI performs competitively, often outperforming TuRBO on low-to-mid dimensions and matching it on high dimensions.
  • vs. Penalty-based methods (PEI, EIMI, KB): SSEI consistently outperforms these methods, which suffer from model degradation as the batch size grows.
• Generalizability: The subspace approach was successfully applied to Probability of Improvement (SSPI) and Upper Confidence Bound (SSUCB), showing similar performance gains over their multi-point counterparts (qPI, qUCB).

Significance and Claims

The paper claims that the proposed Subspace Acquisition Functions provide a simple, efficient, and scalable solution for batch Bayesian optimization. The primary significance lies in enabling the use of large-scale parallel computing resources (large $q$) without the computational bottlenecks or accuracy degradation associated with existing methods.

The authors emphasize that:

• The method effectively mitigates the curse of dimensionality in acquisition function optimization.
• It offers a practical trade-off between global exploration (via random subspace selection) and local exploitation (via fixing non-selected variables).
• It is a "plug-and-play" extension that can be applied to various acquisition functions and is particularly valuable for expensive optimization problems where parallel evaluation is feasible.

The work concludes that selecting query points from multiple different subspaces is a promising strategy for large-scale batch Bayesian optimization, offering significant improvements in convergence speed and solution quality compared to current state-of-the-art approaches.