A Simple Heuristic for Bayesian Optimization with A Low Budget

Masahiro Nomura, Kenshi AbearXiv 2019 · OpenReview

Abstract

The aim of black-box optimization is to optimize an objective function within the constraints of a given evaluation budget. In this problem, it is generally assumed that the computational cost for evaluating a point is large; thus, it is important to search efficiently with as low budget as possible. Bayesian optimization is an efficient method for black-box optimization and provides exploration-exploitation trade-off by constructing a surrogate model that considers uncertainty of the objective function. However, because Bayesian optimization should construct the surrogate model for the entire search space, it does not exhibit good performance when points are not sampled sufficiently. In this study, we develop a heuristic method refining the search space for Bayesian optimization when the available evaluation budget is low. The proposed method refines a promising region by dividing the original region so that Bayesian optimization can be executed with the promising region as the initial search space. We confirm that Bayesian optimization with the proposed method outperforms Bayesian optimization alone and shows equal or better performance to two search-space division algorithms through experiments on the benchmark functions and the hyperparameter optimization of machine learning algorithms.

Introduction

Bayesian Optimization (BO) is the standard approach for black-box optimization, particularly when evaluating parameters (e.g., hyperparameters for a deep neural network) is computationally expensive. However, BO faces a significant challenge in "low-budget" scenarios. To operate effectively, BO constructs a global surrogate model of the entire search space. When the evaluation budget is extremely limited—for instance, 20 evaluations for a 4-dimensional space—BO often spends too much of its budget exploring distant corners to reduce uncertainty. Consequently, it may fail to converge on high-performing local regions, often performing no better than a simple random search.

Methods: Refine, then Optimize

To address this, we propose a two-stage heuristic approach that aggressively prunes the search space before the standard BO process begins. The core motivation stems from theoretical results showing that "regret"—the gap between the found solution and the true optimum—is bounded by the volume of the search space. By shrinking this volume early, the difficulty of the remaining optimization task is significantly reduced.

1. Search-Space Refinement

Before the main BO loop, a small portion of the budget ($B_{ref}$) is used to zoom in on a promising region. The algorithm iteratively selects a dimension, divides it into $K$ equal intervals, and evaluates the center point of each. Only the interval containing the best result is retained. This process is repeated across all dimensions to carve out a smaller "promising" hypercube ($X_S$). Using an odd number for $K$ allows the center point of the original space to be reused, improving efficiency.

Visualization of the search-space refinement process.

2. Bayesian Optimization

Standard BO (e.g., GP-EI, TPE, or SMAC) is then executed, but its search is restricted entirely to the refined hypercube $X_S$. The budget allocation for refinement is determined by a derived heuristic: $\gamma = 0.59 \cdot \exp(-0.033B/d)$, where $B$ is the total budget and $d$ is the dimensionality. This formula ensures that as the budget increases, the reliance on refinement decreases.

Experimental Evaluation

The method was evaluated using two primary sets of experiments:

  • Synthetic Benchmarks: Six standard mathematical functions (Sphere, Rosenbrock, Branin, Hartmann, etc.) with varying dimensions (2 to 6).
  • Machine Learning HPO: Tuning hyperparameters for Multi-Layer Perceptrons (MLP), Convolutional Neural Networks (CNN) on MNIST, and LightGBM on the Breast Cancer Wisconsin dataset.

Results and Discussion

The proposed refinement step (Ref+) consistently improved baseline BO performance. In 5 out of 6 benchmark functions, Ref+GP-EI outperformed standard GP-EI, TPE, and SMAC. It also showed competitive or superior performance compared to specialized hierarchical division algorithms like SOO.

Behavioral plots demonstrate that the refined method focuses sampling in high-quality regions much earlier than standard BO, which continues to sample mediocre areas due to global uncertainty.

Comparison of sampling behavior without and with the proposed refinement.

In real-world applications like LightGBM tuning, the refinement method achieved a misclassification rate of 9.72%, a notable improvement over the 10.5% achieved by standard GP-EI. While effective, the heuristic assumes the center point of a region is representative of its quality. Future work will explore methods to address inter-variable correlations and evaluate performance in noisy environments.

Reference: Nomura, M., & Abe, K. (2019). A Simple Heuristic for Bayesian Optimization with A Low Budget. arXiv:1911.07790v3 [stat.ML].

Summary updated

Abstract

The aim of black-box optimization is to optimize an objective function within the constraints of a given evaluation budget. In this problem, it is generally assumed that the computational cost for evaluating a point is large; thus, it is important to search efficiently with as low budget as possible. Bayesian optimization is an efficient method for black-box optimization and provides exploration-exploitation trade-off by constructing a surrogate model that considers uncertainty of the objective function. However, because Bayesian optimization should construct the surrogate model for the entire search space, it does not exhibit good performance when points are not sampled sufficiently. In this study, we develop a heuristic method refining the search space for Bayesian optimization when the available evaluation budget is low. The proposed method refines a promising region by dividing the original region so that Bayesian optimization can be executed with the promising region as the initial search space. We confirm that Bayesian optimization with the proposed method outperforms Bayesian optimization alone and shows equal or better performance to two search-space division algorithms through experiments on the benchmark functions and the hyperparameter optimization of machine learning algorithms.
BibTeX
@misc{nomura2019simple,
  author = {Masahiro Nomura and Kenshi Abe},
  title = {{A Simple Heuristic for Bayesian Optimization with A Low Budget}},
  year = {2019},
  eprint = {1911.07790},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.07790},
}
Figure