Abstract
Scaling Bayesian optimisation (BO) to high-dimensional search spaces is an active and open research problem, particularly when no assumptions are made on function structure. The main reason is that at each iteration, BO requires finding the global maximisation of an acquisition function, which itself is a non-convex optimization problem in the original search space. With growing dimensions, the computational budget for this maximisation gets increasingly short, leading to inaccurate solutions. This inaccuracy adversely affects both the convergence and the efficiency of BO. We propose a novel approach, MS-UCB, where the acquisition function only requires maximisation on a discrete set of low-dimensional subspaces embedded in the original high-dimensional search space. Our method is free of any low-dimensional structure assumption on the function. Optimising the acquisition function in low-dimensional subspaces allows our method to obtain accurate solutions within a limited computational budget. We show that our algorithm remains convergent with sub-linear cumulative regret. More importantly, our algorithm provides a way to trade the convergence rate with the number of subspaces used in the optimisation. When the number of subspaces is "sufficiently large", our algorithm's cumulative regret reduces a crucial factor of $\sqrt{D}$ compared to standard GP-UCB. Empirical experiments show that its sample efficiency is better than existing methods for many optimisation problems involving dimensions up to 5000.
The Challenge of High-Dimensional BO
Bayesian Optimization (BO) is the gold standard for optimizing expensive black-box functions, such as hyperparameter tuning for deep neural networks or chemical design. However, as the dimensionality ($D$) of the search space increases, BO encounters the "curse of dimensionality." The primary bottleneck is not necessarily the Gaussian Process (GP) surrogate model itself, but the acquisition function.
To select the next point to sample, BO must find the global maximum of the acquisition function. In high dimensions, this becomes a needle-in-a-haystack problem. Most existing high-dimensional BO methods attempt to solve this by assuming the function resides in a low-dimensional effective subspace (e.g., only a few dimensions are "active"). If this structural assumption is violated, these methods fail to converge.
MS-UCB: Multiple Subspace Upper Confidence Bound
The proposed MS-UCB algorithm bypasses the need for structural assumptions by transforming the high-dimensional optimization of the acquisition function into a series of low-dimensional tasks.
- Subspace Decomposition: The algorithm splits the $D$-dimensional space into a small "active" subspace of dimension $d$ and a "latent" space of dimension $D-d$.
- Random Sampling: At each iteration, the algorithm samples a set of points in the latent space. Each point defines a $d$-dimensional "slice" or subspace of the original space.
- Efficient Maximization: The acquisition function is maximized only over this discrete set of low-dimensional subspaces. Because $d$ is small (e.g., $d=5$), finding the local maximum within each slice is computationally cheap and highly accurate, even with a limited budget.
Theoretical and Computational Trade-offs
A key contribution of this work is the explicit trade-off between computational budget and convergence rate. By increasing the number of sampled subspaces ($N_t$), the algorithm achieves better coverage of the search space, leading to faster convergence.
Theoretically, the authors prove that MS-UCB achieves a cumulative regret of $O^*(\sqrt{T}\gamma_T)$, effectively removing the $\sqrt{D}$ factor present in standard GP-UCB bounds. This suggests that MS-UCB is not just a heuristic for high dimensions, but a theoretically superior approach when the acquisition function cannot be perfectly optimized in the full space.
Empirical Results
The researchers evaluated MS-UCB against state-of-the-art baselines, including REMBO, HeSBO, and LineBO, across various synthetic and real-world benchmarks.
- Synthetic Benchmarks: On functions like Ackley, Levy, and Camelback (up to $D=100$), MS-UCB consistently achieved lower regret than competitors.
- High-Dimensional Scaling: In a ramp loss linear classification task using the Gisette dataset ($D=5000$), MS-UCB outperformed methods specifically designed for low-rank embeddings, demonstrating its robustness when structural assumptions are absent.
Conclusion
MS-UCB provides a scalable framework for Bayesian Optimization that addresses the computational reality of high-dimensional search. By focusing optimization efforts on low-dimensional subspaces, it ensures that the acquisition function is maximized accurately, leading to superior sample efficiency and theoretical regret bounds without relying on restrictive assumptions about the underlying function's structure.
Summary updated