Bayesian Optimistic Optimisation with Exponentially Decaying Regret

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

In the world of global optimization, we often face a "black box" problem: we want to find the maximum of a function that is incredibly expensive to evaluate, such as a complex climate model or a deep neural network's hyperparameters. Bayesian Optimization (BO) has long been the gold standard for these tasks, but it faces significant theoretical and practical bottlenecks.

A new paper from researchers at Deakin University, titled "Bayesian Optimistic Optimisation with Exponentially Decaying Regret," introduces an algorithm called BOO that promises to break through these limitations with a significantly tighter regret bound.

TL;DR

The authors propose BOO (Bayesian Optimistic Optimisation), a hybrid algorithm that combines Gaussian Process models with tree-based search. By decoupling the branching factor of the search tree from the number of function evaluations, BOO achieves a state-of-the-art exponential regret bound of $O(N^{-\sqrt{N}})$ in noiseless settings, outperforming existing practical Bayesian Optimization methods.

What Problem Does This Paper Address?

When optimizing an expensive black-box function $f(x)$, we measure success using simple regret: the difference between the true maximum and the best value we’ve found after $N$ evaluations.

Current approaches generally fall into two camps:

  1. Standard BO: Uses a surrogate model (like a Gaussian Process) and an "acquisition function" to pick the next point. While sample-efficient, optimizing the acquisition function itself is often a difficult, non-convex problem.
  2. Tree-based Optimistic Optimization (e.g., SOO): Partitions the search space into a hierarchical tree. These are "model-free" and computationally cheap but often inefficient because they don't use previous observations to guide the search effectively.

The core challenge is the strict negative correlation in tree-based methods: if you want a high branching factor (to search more finely), you end up spending your entire evaluation budget just looking at the "children" of a single node, leaving no budget to go deeper into the tree.

Methods

BOO bridges these two worlds using three key innovations:

  • GP-UCB Tree Expansion: Instead of a model-free search, BOO uses a Gaussian Process (GP) to model the function. It selects which node to "expand" (split into smaller regions) based on the Upper Confidence Bound (UCB) of the node's center.
  • Novel Partitioning ($P(m; a, b)$): Unlike standard methods that split only the longest dimension, BOO's partitioning scheme allows splitting multiple dimensions simultaneously. This is crucial for the theoretical convergence proof.
Comparison of single-dimension vs. multi-dimension partitioning schemes.
  • The "Evaluate Parent Only" Strategy: This is the "aha!" moment. Traditional tree-based methods evaluate every child node when a parent is split. BOO evaluates only the parent node. Because it has a GP model, it can "trust" the information at the parent's center to represent the region, effectively "untieing" the branching factor from the evaluation cost. This allows the algorithm to use a large branching factor without exhausting the budget.

Key Insights and Ideas

  • Breaking the Correlation: By only evaluating the parent node, BOO can afford a much higher branching factor ($m$). This leads to a much finer partitioning of the search space much earlier in the process.
  • Tighter Regret Bounds: Most BO algorithms have sub-linear regret. BOO achieves an exponential decay $O(N^{-\sqrt{N}})$. Under the assumption of a smooth Matérn kernel ($\nu > 4 + D/2$), this is the tightest known bound for a practical BO algorithm.
  • Computational Efficiency: Standard BO requires solving a continuous optimization problem to find the next point (maximizing the acquisition function). BOO only needs to compare UCB values across a finite set of leaf nodes in a tree, making it significantly faster in terms of overhead.

Datasets and Key Results

The authors evaluated BOO on both synthetic benchmarks (Hartmann3, Schwefel, Shekel) and real-world machine learning tasks (Elastic Net, MLP, and XGBoost hyperparameter tuning).

  • Superior Regret: In synthetic tests, BOO reached lower regret levels faster than established baselines like GP-UCB, GP-EI, and IMGPO. Adjusting the partitioning dimensions (e.g., $b=D$) further accelerates convergence.
Log distance to optima over iterations for the Hartmann6 dataset, showing BOO's rapid convergence.
  • ML Performance: On the XGBoost tuning task, BOO outperformed all baselines by a wide margin. For the MLP task, it achieved a prediction error of 1.8%, slightly better than the best-performing baselines.
  • Speed: While slightly slower than the model-free SOO (which does almost no computation), BOO was orders of magnitude faster than standard GP-EI and GP-UCB, which struggle with the overhead of optimizing acquisition functions in continuous space.

Limitations and Future Work

The authors acknowledge a few constraints:

  • Noiseless Assumption: The current theoretical proof and algorithm are optimized for the noiseless setting (where evaluating $f(x)$ gives the exact value). Real-world experiments often have noise, but the theory doesn't fully cover it yet.
  • Kernel Smoothness: The regret bound relies on the Matérn kernel being sufficiently smooth ($\nu > 4 + D/2$). If the function is very "jagged," the guarantees may weaken.
  • High Dimensions: While BOO performs well, tree-based partitioning naturally struggles as the number of dimensions ($D$) grows very large (the "curse of dimensionality"). Extending the work to high-dimensional and noisy settings is the next logical step.

Reference: Tran-The, H., Gupta, S., Rana, S., & Venkatesh, S. (2021). Bayesian Optimistic Optimisation with Exponentially Decaying Regret. Proceedings of the 38th International Conference on Machine Learning (ICML).

Summary updated

Abstract

Bayesian optimisation (BO) is a well known algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from $\mathcal{...
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