# Trading Convergence Rate with Computational Budget in High Dimensional Bayesian Optimization

arXiv: https://arxiv.org/abs/1911.11950 · HTML: https://mlsanity.com/paper/1911.11950/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2019.

## Built on by (most cited first, 7 of 7)

- [Computationally Efficient High-Dimensional Bayesian Optimization via Variable Selection](https://mlsanity.com/paper/2109.09264/) (2021)
- [Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2305.19838/) (2023)
- [Regional Expected Improvement for Efficient Trust Region Selection in High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2412.11456/) (2024)
- [High Dimensional Bayesian Optimization using Lasso Variable Selection](https://mlsanity.com/paper/2504.01743/) (2025)
- [Bayesian Optimistic Optimisation with Exponentially Decaying Regret](https://mlsanity.com/paper/2105.04332/) (2021)
- [High-Dimensional Bayesian Optimization via Random Projection of Manifold Subspaces](https://mlsanity.com/paper/2412.16554/) (2024)
- [High-dimensional Multi-objective Bayesian Optimization with Learned Variable Interactions](https://mlsanity.com/paper/2608.11713/) (2026)

## Abstract (arXiv)

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.