Abstract
We present GLASSES: Global optimisation with Look-Ahead through Stochastic Simulation and Expected-loss Search. The majority of global optimisation approaches in use are myopic, in only considering the impact of the next function value; the non-myopic approaches that do exist are able to consider only a handful of future evaluations. Our novel algorithm, GLASSES, permits the consideration of dozens of evaluations into the future. This is done by approximating the ideal look-ahead loss function, which is expensive to evaluate, by a cheaper alternative in which the future steps of the algorithm are simulated beforehand. An Expectation Propagation algorithm is used to compute the expected value of the loss. We show that the far-horizon planning thus enabled leads to substantive performance gains in empirical tests.
Introduction
Bayesian Optimization (BO) is a powerful framework for optimizing expensive black-box functions, such as hyperparameter tuning in machine learning or experimental design. However, standard BO methods are typically "myopic," meaning they only consider the immediate impact of the next evaluation. This short-sightedness can lead to suboptimal exploration, especially when a fixed budget of evaluations is available. GLASSES (Global optimisation with Look-Ahead through Stochastic Simulation and Expected-loss Search) addresses this by enabling long-horizon planning, allowing the algorithm to look dozens of steps into the future.
Methodology
The core challenge in non-myopic BO is the computational complexity of evaluating the expected loss over multiple future steps. GLASSES overcomes this through two primary innovations:
Future Step Simulation
Instead of exploring all possible future trajectories, GLASSES simulates a set of "putative" future evaluation locations. This is achieved using a local penalization strategy, which identifies likely future points by iteratively selecting locations that minimize current loss and then penalizing those regions to ensure diversity in the simulated set.
Expectation Propagation (EP)
Calculating the expected minimum value over these putative points requires solving a high-dimensional integral. GLASSES employs Expectation Propagation to approximate this integral efficiently. This technical choice allows the algorithm to scale to horizons of dozens of steps, far exceeding the 2-6 step limit of previous non-myopic methods.
Key Insights: The Flattening Effect
A significant conceptual contribution of this work is the visualization of how the expected loss surface changes with the look-ahead horizon. As the horizon increases, the loss function "flattens." This occurs because the algorithm accounts for the fact that it has multiple future opportunities to refine its search, reducing the pressure to immediately exploit a local optimum.
As the budget is exhausted, the loss surface becomes more peaked, naturally transitioning the algorithm from broad exploration to focused exploitation.
Empirical Evaluation
The researchers tested GLASSES against standard myopic BO on a variety of synthetic benchmarks, ranging from 1D to 10D. These functions represent various challenges, such as multiple local optima and high-frequency oscillations.
- Performance: GLASSES outperformed standard myopic Expected Loss in a majority of test cases (6 out of 11).
- Horizon Impact: For complex functions like McCormick and Powers, increasing the look-ahead horizon consistently improved the ability to find the global minimum.
- Robustness: Even in cases where it was not the top performer, GLASSES remained competitive, suggesting it is a robust default for expensive optimization tasks where the computational cost of look-ahead is small compared to function evaluation.
Conclusion
GLASSES provides a computationally tractable way to incorporate long-term planning into Bayesian Optimization. By bridging the gap between batch BO and non-myopic planning, and utilizing EP for efficient integration, it offers a significant step forward in global optimization for expensive black-box functions.
Summary updated