Regional Expected Improvement for Efficient Trust Region Selection in High-Dimensional Bayesian Optimization

Nobuo Namura, Sho Takemori

Abstract

Real-world optimization problems often involve complex objective functions with costly evaluations. While Bayesian optimization (BO) with Gaussian processes is effective for these challenges, it suffers in high-dimensional spaces due to performance degradation from limited function evaluations. To overcome this, simplification techniques like dimensionality reduction have been employed, yet they often rely on assumptions about the problem characteristics, potentially underperforming when these assumptions do not hold. Trust-region-based methods, which avoid such assumptions, focus on local search but risk stagnation in local optima. In this study, we propose a novel acquisition function, regional expected improvement (REI), designed to enhance trust-region-based BO in medium to high-dimensional settings. REI identifies regions likely to contain the global optimum, improving performance without relying on specific problem characteristics. We provide a theoretical proof that REI effectively identifies optimal trust regions and empirically demonstrate that incorporating REI into trust-region-based BO outperforms conventional BO and other high-dimensional BO methods in medium to high-dimensional real-world problems.

Introduction

Standard Bayesian Optimization is the "gold standard" for optimizing expensive black-box functions, such as tuning machine learning models or designing complex engineering systems. However, its performance typically degrades significantly as the dimensionality of the search space increases beyond 10 dimensions. In these high-dimensional spaces, the Gaussian Process (GP) models used by BO become less accurate because the available data is too sparse to cover the volume of the search space effectively.

To address this, researchers often employ Trust Region methods, such as TuRBO, which focus the search on a small, local area where the GP model is more reliable. While effective locally, these methods face a critical challenge: when a local search converges or gets stuck, the algorithm typically restarts in a random location. In high-dimensional spaces, a random restart is highly unlikely to land near the global optimum. This research introduces Regional Expected Improvement (REI) to make these restarts "smarter" by using existing data to identify the most promising regions for the next search phase.

Methods: Regional Expected Improvement (REI)

The core innovation of this work is the REI acquisition function. While standard acquisition functions like Expected Improvement (EI) evaluate the potential of sampling a specific point, REI evaluates the average potential of an entire region (typically a hypercube).

Region-Averaging and qREI

REI calculates the mean value of the acquisition function over a potential trust region. This process effectively "smooths" the optimization landscape, allowing the algorithm to ignore fine-grained local noise and focus on broad valleys that are more likely to contain the global optimum. Because calculating the exact integral of EI over a region is mathematically complex, the authors developed qREI, a Monte Carlo variant that utilizes random sampling and Thompson Sampling to estimate a region's potential efficiently.

Comparison of standard Expected Improvement (EI) and Regional Expected Improvement (qREI) across iterations.

As shown in Figure 1, standard EI (green) can be highly peaky and localized. In contrast, qREI (orange) identifies broader areas of interest. When integrated into the TuRBO algorithm, REI replaces the random restart mechanism. When a trust region shrinks below a certain threshold, the algorithm maximizes qREI to select the next optimal starting region.

Theoretical and Key Insights

The paper provides theoretical grounding for REI, showing that the region-averaging operator reduces the complexity of the optimization problem. By focusing on "macro features"—the broad structural trends of the function—REI creates a surrogate objective function that is mathematically simpler to optimize than the original global GP model.

This approach naturally prioritizes "broad valleys" early in the search, ensuring the algorithm explores promising general areas. As the search progresses and more data is collected, the focus shifts toward "deep valleys" to refine the global optimum. This robustness is a key advantage over methods that rely on specific assumptions, such as parameter sparsity, which may not hold in real-world engineering problems.

Empirical Evaluation and Results

The authors evaluated the REI-enhanced TuRBO (TuRBO-1-LogEI-qREI) against several baselines, including standard TuRBO, CMA-ES, and specialized high-dimensional BO methods like SAASBO and DSP. The benchmarks included high-dimensional engineering problems such as Human-Powered Aircraft (HPA) design (17D to 108D), Rover Trajectory Planning (60D), and the MOPTA08 vehicle design problem (124D).

Performance benchmarks on HPA problems showing the superiority of the REI-enhanced TuRBO.

Key Findings

  • Superior Performance: The REI-enhanced version consistently outperformed baselines across almost all benchmarks. As illustrated in Figure 3, the method achieves lower minimum values faster than competing algorithms in the HPA suite.
  • Efficiency in Mid-to-High Dimensions: The improvements were most dramatic in the 17D to 32D range. In these settings, the algorithm has enough evaluations to trigger multiple restarts, allowing REI to repeatedly guide the search to superior regions.
  • Statistical Significance: Wilcoxon signed-rank tests confirmed that the improvements over standard TuRBO were statistically significant in several key benchmarks, including HPA101-0 and HPA102-1.

Conclusion and Future Work

Regional Expected Improvement provides a robust and theoretically sound method for navigating high-dimensional optimization landscapes. By identifying promising regions rather than just points, it significantly improves the efficiency of trust-region-based Bayesian Optimization.

While qREI introduces some additional computational overhead compared to random restarts, this cost is typically negligible compared to the expense of real-world function evaluations. Future research may explore "planned shrinkage"—limiting evaluations per trust region to force more frequent restarts—which could further leverage REI's guidance in extremely high-dimensional settings where trust regions might otherwise take too long to fail.

Summary updated

Abstract

Real-world optimization problems often involve complex objective functions with costly evaluations. While Bayesian optimization (BO) with Gaussian processes is effective for these challenges, it suffers in high-dimensional spaces due to performance degradation from limited function evaluations. To overcome this, simplification techniques like dimensionality reduction have been employed, yet they often rely on assumptions about the problem characteristics, potentially underperforming when these assumptions do not hold. Trust-region-based methods, which avoid such assumptions, focus on local search but risk stagnation in local optima. In this study, we propose a novel acquisition function, regional expected improvement (REI), designed to enhance trust-region-based BO in medium to high-dimensional settings. REI identifies regions likely to contain the global optimum, improving performance without relying on specific problem characteristics. We provide a theoretical proof that REI effectively identifies optimal trust regions and empirically demonstrate that incorporating REI into trust-region-based BO outperforms conventional BO and other high-dimensional BO methods in medium to high-dimensional real-world problems.
BibTeX
@inproceedings{namura2025regional,
  author = {Nobuo Namura and Sho Takemori},
  title = {{Regional Expected Improvement for Efficient Trust Region Selection in High-Dimensional Bayesian Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=dROxnvAUbe},
}
Figure