Trading Convergence Rate with Computational Budget in High Dimensional Bayesian Optimization

Hung Tran-The, Sunil Gupta, Santu Rana, Svetha Venkatesh

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 maximum 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 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, unlike many recent high-dimensional BO methods. Optimising the acquisition function in low-dimensional subspaces allows our method to obtain accurate solutions within a limited computational budget. We show that in spite of this convenience, our algorithm remains convergent. In particular, the cumulative regret of our algorithm only grows sub-linearly with the number of iterations. More importantly, as evident from our regret bounds, our algorithm provides a way to trade the convergence rate with the number of subspaces used in the optimisation. Finally, when the number of subspaces is "sufficiently large", our algorithm's cumulative regret is at most $\mathcal{O}^{*}(\sqrt{T\gamma_T})$ as opposed to $\mathcal{O}^{*}(\sqrt{DT\gamma_T})$ for the GP-UCB, reducing a crucial factor of $\sqrt{D}$ where $D$ is the dimensionality of the input space.

Introduction

Bayesian Optimization (BO) is a powerful framework for optimizing expensive black-box functions. However, its performance typically degrades significantly as the dimensionality of the search space increases, often hitting a practical limit around 15 dimensions. The primary bottleneck is the acquisition function: to suggest the next point to sample, one must find the global maximum of this function. In high-dimensional spaces, this becomes a "needle-in-a-haystack" problem, where limited computational budgets lead to poor optimization of the acquisition function itself, stalling the entire BO process.

The MS-UCB Algorithm

To address this, we introduce MS-UCB (Multiple Subspaces Upper Confidence Bound). Rather than attempting to optimize the acquisition function over the entire $D$-dimensional space $\mathcal{X}$, MS-UCB restricts the search to a collection of low-dimensional subspaces.

The algorithm works by splitting the $D$-dimensional space into a small $d$-dimensional component and a large $(D-d)$-dimensional component. At each iteration, we randomly sample a set of points in the large component, each defining a $d$-dimensional "slice" or subspace. By maximizing the acquisition function only within these specific low-dimensional slices (where $d$ is small, e.g., $d=5$), we can achieve fast and accurate optimization. This approach allows for a direct trade-off: by increasing the number of subspaces sampled ($N_t$), researchers can spend more computational budget to achieve faster convergence.

Theoretical Advantages

Unlike many existing high-dimensional BO methods, MS-UCB does not require the objective function to possess a hidden low-dimensional structure (like an effective subspace). However, if such a structure exists, the algorithm naturally exploits it. Theoretically, MS-UCB achieves a cumulative regret bound that improves upon the standard GP-UCB by a factor of $\sqrt{D}$. This implies that MS-UCB becomes increasingly efficient relative to standard methods as the dimensionality of the problem grows.

Experimental Evaluation

We evaluated MS-UCB against several state-of-the-art baselines, including REMBO, LineBO, and DropoutUCB, across a variety of tasks.

Synthetic Benchmarks

We tested the algorithm on standard functions such as Ackley, Levy, Hyper-Ellipsoid, and Camelback at dimensions $D=20, 50, \text{ and } 100$.

Performance on the Levy function at D=20, showing MS-UCB (blue) achieving lower regret faster than baselines.

As shown in the comprehensive results below, MS-UCB consistently outperforms baselines across different functions and dimensions. The performance gap often widens as the dimensionality increases, confirming the algorithm's scalability.

Comprehensive log regret results across multiple synthetic benchmarks for D=50 and D=100. MS-UCB (blue) consistently maintains the lowest regret.

Real-World Applications

The algorithm was also applied to high-dimensional machine learning tasks:

  • Neural Network Tuning: Optimizing weights for an MNIST classification network (up to 500 dimensions), where MS-UCB outperformed specialized methods like HeSBO.
  • Large-Scale Classification: Optimizing a ramp loss function on the Gisette dataset (5,000 dimensions). In this extreme high-dimensional setting, MS-UCB maintained superior performance while traditional methods struggled to converge.

Conclusion

MS-UCB provides a robust and scalable solution for high-dimensional Bayesian Optimization. By shifting the focus from exhaustive high-dimensional search to accurate optimization within multiple low-dimensional subspaces, it offers a principled way to trade computational budget for convergence speed. Its lack of restrictive structural assumptions makes it a versatile tool for a wide range of complex optimization problems.

Summary updated

Abstract

Scaling Bayesian optimisation (BO) to high-dimensional search spaces is a active and open research problems particularly when no assumptions are made on function structure. The main reason is that at each iteration, BO requires to find global maximisation of 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 solution of the maximisation. This inaccuracy adversely affects both the convergence and the efficiency of BO. We propose a novel approach 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 unlike many recent high-dimensional BO methods. Optimising acquisition function in low dimensional subspaces allows our method to obtain accurate solutions within limited computational budget. We show that in spite of this convenience, our algorithm remains convergent. In particular, cumulative regret of our algorithm only grows sub-linearly with the number of iterations. More importantly, as evident from our regret bounds, our algorithm provides a way to trade the convergence rate with the number of subspaces used in the optimisation. Finally, when the number of subspaces is "sufficiently large", our algorithm's cumulative regret is at most $\mathcal{O}^{*}(\sqrt{T\gamma_T})$ as opposed to $\mathcal{O}^{*}(\sqrt{DT\gamma_T})$ for the GP-UCB of Srinivas et al. (2012), reducing a crucial factor $\sqrt{D}$ where $D$ being the dimensional number of input space.
BibTeX
@inproceedings{tranthe2020trading,
  author = {Hung Tran-The and Sunil Gupta and Santu Rana and Svetha Venkatesh},
  title = {{Trading Convergence Rate with Computational Budget in High Dimensional Bayesian Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=PJleAmgDvbn},
}
Figure