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