Bayesian Optimistic Optimisation with Exponentially Decaying Regret

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

Abstract

Bayesian optimisation (BO) is a well-known efficient algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from $\mathcal{O}(\frac{logN}{\sqrt{N}})$ to $\mathcal O(e^{-\sqrt{N}})$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation which are based on partitioning the search space. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $\mathcal O(N^{-\sqrt{N}})$ under the assumption that the objective function is sampled from a Gaussian process with a Mat'ern kernel with smoothness parameter $\nu > 4 +\frac{D}{2}$, where $D$ is the number of dimensions. We perform experiments on optimisation of various synthetic functions and machine learning hyperparameter tuning tasks and show that our algorithm outperforms baselines.

Introduction

Global optimization aims to find the maximum of an expensive, "black-box" function $f(x)$ with minimal evaluations. Traditionally, researchers have relied on two distinct paradigms: Bayesian Optimization (BO) and tree-based optimistic optimization (e.g., SOO, DIRECT). While BO is sample-efficient due to its Gaussian Process (GP) surrogate, it suffers from the computational difficulty of maximizing non-convex acquisition functions. Conversely, tree-based methods are computationally efficient but often model-free, leading to sample inefficiency.

A significant bottleneck in tree-based methods is the coupling of the branching factor ($m$) and the evaluation budget. Expanding a node into $m$ children typically requires $m$ function evaluations, forcing a trade-off between search resolution and budget consumption.

The BOO Algorithm

The proposed BOO (Bayesian Optimistic Optimisation) algorithm bridges these paradigms by decoupling the branching factor from the evaluation budget. It introduces three core innovations:

  1. Parent-Only Sampling: Unlike traditional methods, BOO evaluates the function only at the parent node. This allows for a high branching factor (e.g., $m=64$) without exhausting the evaluation budget, enabling rapid "zooming" into promising regions.
  2. Novel Partitioning ($P(m; a, b)$): BOO employs a scheme where $m = a^b$, dividing the $b$ longest dimensions into $a$ equal parts simultaneously to refine the search space faster across multiple dimensions.
  3. GP-UCB Selection: BOO uses a GP surrogate to calculate Upper Confidence Bounds (UCB) for leaf nodes, expanding only those with high potential for a global maximum. This discretizes the continuous acquisition function optimization into a search over finite leaf nodes.
The Parent-Only Sampling mechanism allows BOO to decouple branching from function evaluations.

Experimental Results

The authors evaluated BOO against state-of-the-art baselines, including GP-EI, GP-UCB, SOO, and BaMSOO, across synthetic benchmarks and machine learning hyperparameter tuning tasks.

Synthetic Benchmarks

On standard functions like Hartmann3 ($D=3$), Schwefel ($D=3$), and Shekel ($D=4$), BOO consistently achieved the global optimum faster than all baselines. Notably, BOO demonstrated significantly better computational efficiency. For the Shekel function, BOO achieved superior results in approximately 91 seconds, compared to 1640 seconds for standard GP-UCB.

BOO (red line) demonstrates superior convergence and lower regret across various synthetic benchmark functions.

Machine Learning Hyperparameter Tuning

BOO was applied to tuning ElasticNet (MNIST), Multilayer Perceptrons (MNIST), and XGBoost (Skin Segmentation). In the XGBoost task, which involved five hyperparameters, BOO outperformed all baselines by finding better configurations with fewer evaluations.

Conclusion

BOO represents a significant theoretical and practical advancement in Bayesian Optimization. By achieving an exponentially decaying regret bound of $O(N^{-\sqrt{N}})$, it sets a new state-of-the-art for noiseless global optimization. Future work will focus on extending this framework to noisy environments and addressing the curse of dimensionality in even higher-dimensional spaces.

Summary updated

Abstract

Bayesian optimisation (BO) is a well-known efficient algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from $\mathcal{O}(\frac{logN}{\sqrt{N}})$ to $\mathcal O(e^{-\sqrt{N}})$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation which are based on partitioning the search space. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $\mathcal O(N^{-\sqrt{N}})$ under the assumption that the objective function is sampled from a Gaussian process with a Mat\'ern kernel with smoothness parameter $\nu > 4 +\frac{D}{2}$, where $D$ is the number of dimensions. We perform experiments on optimisation of various synthetic functions and machine learning hyperparameter tuning tasks and show that our algorithm outperforms baselines.
BibTeX
@inproceedings{tranthe2021bayesian,
  author = {Hung Tran-The and Sunil Gupta and Santu Rana and Svetha Venkatesh},
  title = {{Bayesian Optimistic Optimisation with Exponentially Decaying Regret}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=8FZJCIjCa15},
}
Figure