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