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

Nobuo Namura, Sho Takemori

Abstract

Bayesian Optimization (BO) is a powerful tool for black-box optimization but struggles in high-dimensional spaces due to the curse of dimensionality. Trust-region methods like TuRBO address this by focusing on local searches but often rely on inefficient random restarts for global exploration. We present Regional Expected Improvement (REI), a novel acquisition function that evaluates the potential of entire regions rather than individual points. By averaging Expected Improvement (EI) over a volume, REI identifies promising areas for new trust regions, effectively smoothing the search landscape. Empirical results on high-dimensional benchmarks (up to $D=124$) demonstrate that REI-enhanced TuRBO consistently outperforms state-of-the-art baselines in both efficiency and stability.

Introduction

Bayesian Optimization (BO) is the gold standard for optimizing expensive "black-box" functions, such as hyperparameter tuning for large-scale machine learning models or complex engineering designs. However, standard BO methods typically fail as dimensionality increases beyond 10-20 dimensions. In these high-dimensional spaces, a global Gaussian Process (GP) model cannot accurately map the entire landscape with a feasible number of samples.

To mitigate this, researchers often employ Trust Region methods, such as TuRBO, which perform intensive local searches within restricted areas. While effective at finding local optima, these methods struggle with global exploration. When a local search converges, the algorithm typically "restarts" at a random location. In high-dimensional spaces, random restarts are highly inefficient, often missing the global optimum entirely.

Methods: Regional Expected Improvement (REI)

The authors introduce Regional Expected Improvement (REI), a novel acquisition function designed to strategically select the next trust-region location rather than relying on random restarts.

The Core Idea

Instead of identifying a single point with the highest Expected Improvement (EI), REI calculates the average EI over a specific volume (the candidate trust region). This approach prioritizes regions with broad potential over narrow, sharp peaks that might be artifacts of model uncertainty.

Implementation via qREI

Calculating the exact integral of improvement over a high-dimensional volume is computationally prohibitive. To address this, the authors utilize a Monte Carlo variant, qREI, which samples points within a candidate region to estimate its aggregate potential. This allows for efficient integration into the TuRBO framework: when a restart is triggered, the global GP model uses qREI to find the region where the "average" potential for improvement is maximized.

Comparison of qREI and EI acquisition functions across iterations. qREI identifies broader regions of potential, facilitating better global exploration compared to the point-wise EI.

Landscape Smoothing

By averaging the acquisition function over a volume, REI effectively "smooths" the search landscape. This makes the global optimization problem more tractable for the GP model, as it is less likely to be trapped by sharp, narrow local optima that do not represent significant regions of improvement.

Experimental Evaluation

The proposed method was evaluated on several challenging, high-dimensional benchmarks, including Human-Powered Aircraft (HPA) design, Rover Trajectory Planning ($D=60$), and the MOPTA08 automotive benchmark ($D=124$). These problems represent real-world scenarios where the internal structure of the function is unknown and sparsity cannot be assumed.

Key Results

The empirical results demonstrate that REI-enhanced TuRBO consistently outperforms standard TuRBO and other state-of-the-art baselines like CMA-ES and SAASBO.

Performance comparison on high-dimensional benchmarks. TuRBO-1-LogEI-qREI consistently achieves lower objective values and demonstrates higher stability across random seeds compared to standard TuRBO and other baselines.

As shown in the performance curves and violin plots, the REI variants achieved the best results after 1,000–2,000 evaluations. Notably, REI leads to more consistent results across different random seeds, significantly reducing the variance often associated with random restarts in high dimensions. This stability is a critical advantage for practical applications where only a few optimization runs may be feasible.

Conclusion

Regional Expected Improvement provides a principled way to navigate high-dimensional landscapes by evaluating the potential of entire search regions. By integrating REI into trust-region frameworks, researchers can overcome the limitations of random restarts, leading to more efficient and stable global optimization. Future work may explore more frequent regional selection or the application of REI to discrete and categorical variable spaces.

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