Bayesian Optimistic Optimisation with Exponentially Decaying Regret

1. Problem Statement

The paper addresses the problem of global optimization for expensive, noise-free, black-box functions $f(x)$, where $x \in \mathcal{X} \subset \mathbb{R}^D$. The goal is to find the global maximum $x^*$ with a limited budget of function evaluations $N$.

Performance is measured by simple regret:
$$r_N = \sup_{x \in \mathcal{X}} f(x) - \max_{1 \le i \le N} f(x_i)$$

Existing Limitations:

• Bayesian Optimization (BO): Standard BO algorithms (e.g., GP-UCB, GP-EI) typically achieve sublinear regret bounds (e.g., $O(\sqrt{\frac{\log N}{N}})$ or $O(1/\sqrt{N})$). A major bottleneck is that BO must solve an auxiliary optimization problem (non-convex) at every iteration (maximizing the acquisition function), which is computationally intensive and difficult in high dimensions.
• Optimistic Optimization (Tree-based): Algorithms like SOO and BaMSOO partition the search space hierarchically. Although they avoid auxiliary optimization, they suffer from a strict negative correlation between the branching factor $m$ (granularity of partitioning) and the number of tree expansions. To achieve fine partitions (large $m$), many child nodes must be evaluated, which quickly exhausts the evaluation budget $N$. Consequently, their worst-case regret bounds are often limited to $O(e^{-\sqrt{N}})$ or sublinear rates.

The authors ask: Can we design a practical algorithm that combines the model efficiency of BO with the structural advantages of tree-based optimistic optimization to achieve a tighter regret bound (specifically $O(N^{-\sqrt{N}})$) without the computational cost of auxiliary optimization?

2. Methodology: The BOO Algorithm

The authors propose Bayesian Optimistic Optimisation (BOO), a novel algorithm that integrates Gaussian Processes (GP) with a modified hierarchical tree search.

Key Innovations

1. Decoupling the Branching Factor from Evaluations:

   • Traditional Approach: In SOO/BaMSOO, expanding a node requires evaluating $m$ children. Thus, the number of expansions is limited to $N/m$.
   • BOO Approach: The algorithm selects a node for expansion based on the GP Upper Confidence Bound (GP-UCB). Crucially, it evaluates only the objective function at the selected parent node, not at its $m$ children. The children are structurally added to the tree but remain unevaluated until they are selected later.
   • Result: This "decouples" the branching factor $m$ from the evaluation budget. The algorithm can use a very large $m$ to create extremely fine partitions without incurring the cost of $m$ evaluations per step.

2. Novel Partitioning Procedure $P(m; a, b)$:

   • Instead of splitting only the longest side of a cell (standard in SOO), BOO decomposes the branching factor into $m = a^b$.
   • It splits the cell along its $b$ longest dimensions, each into $a$ equal parts.
   • By setting $b = D$ (the dimensionality), the algorithm partitions all dimensions simultaneously. This enables much faster refinement of the search space in all directions compared to sequential dimension splitting.

3. Sampling Strategy:

   • The algorithm maintains a GP model.
   • In each step, it selects the leaf node with the highest GP-UCB value.
   • It evaluates $f$ only at the center of this selected node.
   • It updates the GP and the tree structure by adding $m$ children to the selected node.

Algorithm Flow (Simplified)

1. Initialize a tree with a root node.
2. Select the leaf node $(h, i)$ with the maximum GP-UCB value $U_p(c_{h,i})$.
3. If $U_p(c_{h,i}) \ge v_{max}$ (current best observed value):
   • Evaluate $f$ at the center of the node.
   • Update the dataset and refit the GP.
   • Expand the node by adding $m$ children using the partitioning rule $P(m; a, b)$.
4. Repeat until the budget $N$ is exhausted.

3. Theoretical Contributions & Regret Analysis

The paper provides a rigorous theoretical analysis assuming that $f$ is drawn from a Gaussian Process with a Matérn kernel with smoothness parameter $\nu > 4 + \frac{D}{2}$.

• Regret Bound: The authors prove that BOO achieves a simple regret bound of:
  $$r_N = O(N^{-\sqrt{N}})$$
  This is an exponentially decaying regret, which is strictly tighter than the $O(e^{-\sqrt{N}})$ bound of previous state-of-the-art optimistic algorithms (such as IMGPO) and significantly better than standard BO bounds.

• Key Mechanism of the Theory:

  • The proof relies on bounding the size of the "expansion set" (nodes that could potentially contain the optimum).
  • By using the novel partitioning ($b=D$) and a large branching factor $m$, it is shown that the "near-optimality dimension" is effectively 0.
  • The decoupling of $m$ from evaluations allows the algorithm to explore the space with high granularity (large $m$) while maintaining low evaluation costs, leading to an improved convergence rate.

4. Experimental Results

The authors validated BOO on synthetic benchmarks and real-world machine learning hyperparameter tuning tasks.

• Baselines: Comparison with GP-EI, GP-UCB, SOO, BaMSOO, and IMGPO.
• Synthetic Functions: Tested on Hartmann3, Schwefel, and Shekel functions.
  • Result: BOO consistently outperformed all baselines in terms of convergence speed (logarithmic distance to the optimum). It achieved the best performance on Hartmann and Schwefel, and competitive performance on Shekel.
• Hyperparameter Tuning:
  • Tasks: Tuning ElasticNet, MLP, and XGBoost on the MNIST and Skin Segmentation datasets.
  • Result: BOO achieved lower prediction errors compared to all baselines. For XGBoost, it outperformed the others by a large margin.
• Computational Performance:
  • BOO is significantly faster than GP-EI and GP-UCB because it avoids the expensive maximization of acquisition functions over continuous spaces.
  • It is somewhat slower than IMGPO due to the overhead of managing a larger tree (large $m$), but the trade-off leads to superior optimization performance.

5. Significance and Conclusion

• Breaking the Regret Barrier: This is the first practical algorithm to achieve a regret bound of $O(N^{-\sqrt{N}})$ for Bayesian optimization, surpassing the theoretical limits of previous optimistic and Bayesian methods.
• Practicality: Unlike previous theoretical approaches that required impractical sampling (such as $\delta$-cover sampling), BOO is implementable and efficient.
• Synergy: The work successfully bridges the gap between model-based optimization (BO) and model-free optimistic optimization, demonstrating that integrating a GP model into a tree-based structure with a specific sampling strategy can yield exponential improvements in convergence.
• Future Work: The authors plan to extend the method to noisy settings and higher-dimensional spaces.

In summary, the paper represents a significant advancement in the theory and practice of global optimization by introducing a mechanism to decouple search granularity from evaluation costs, resulting in a state-of-the-art regret bound and superior empirical performance.