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 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.

  1. 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$.
  2. 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.
  3. 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.
Impact of subspace count on convergence. Increasing the number of subspaces (higher alpha) leads to lower log regret.

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.
MS-UCB performance vs. baselines on the Ackley function (D=50). MS-UCB (blue) shows significantly faster and deeper convergence.

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

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 O*(√TγT) as opposed to O*(√DTγT) for the GP-UCB of Srinivas et al. (2012), reducing a crucial factor √D where D being the dimensional number of input space. We perform empirical experiments to evaluate our method extensively, showing that its sample efficiency is better than the existing methods for many optimisation problems involving dimensions up to 5000.
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