cs.LGJun 28, 2024
SaveCost-aware Bayesian Optimization via the Pandora's Box Gittins Index
Organizations: Cornell University · Caltech
Abstract
Bayesian optimization is a technique for efficiently optimizing unknown functions in a black-box manner. To handle practical settings where gathering data requires use of finite resources, it is desirable to explicitly incorporate function evaluation costs into Bayesian optimization policies. To understand how to do so, we develop a previously-unexplored connection between cost-aware Bayesian optimization and the Pandora's Box problem, a decision problem from economics. The Pandora's Box problem admits a Bayesian-optimal solution based on an expression called the Gittins index, which can be reinterpreted as an acquisition function. We study the use of this acquisition function for cost-aware Bayesian optimization, and demonstrate empirically that it performs well, particularly in medium-high dimensions. We further show that this performance carries over to classical Bayesian optimization without explicit evaluation costs. Our work constitutes a first step towards integrating techniques from Gittins index theory into Bayesian optimization.
Figures & tables
Figure 1: An illustration of this work’s key idea. We view cost-aware Bayesian optimization as an extension of the Pandora’s Box problem, and derive the cost-aware acquisition function by incorporating the posterior into the Bayesian-optimal Pandora’s Box acquisition function .
Figure 2: A Bayesian optimization problem with varying costs on which LogEIPC—a numerically stable implementation of EIPC, see Sections 4 and D.1 —has poor performance, inspired by [ 4 , Section A] . The domain is , which we visualize on the subinterval . Left: illustration of the non-uniform prior variance, which is given by a Matérn-5/2 kernel scaled by a narrow bump function. Center: the cost function, which is a narrow bump-shaped function. Right: median regret curves and quartiles for LogEIPC and PBGI. Legend refers only to regret curves.
Figure 3: Left: contour plots showing how EI (left) and PBGI (center-left, center-right) depend on the posterior mean and standard deviation at a given point (lighter colors indicate higher values). We see that PBGI values high standard deviation more than EI. Right: PBGI performance across values of , under the setup of the Bayesian regret experiment of Section 4 with . We plot the median of a set of samples using random seeds, along with quartiles to show variability. We see that large -values decrease regret sooner, but eventually lose out to smaller -values.
Figure 4: Regret curves for objective functions sampled from the prior, shown using medians, as well as quartiles to indicate experiment variability. We see in the cost-aware setting that both PBGI variants usually exhibit comparable performance to LogEIPC and LogEICC, with PBGI-D decisively outperforming other baselines. In the uniform-cost setting, the story is similar for and : PBGI and PBGI-D perform comparably to the best baselines, which are LogEI and UCB, as well as MSEI for . However, for , all methods perform comparably to random search, with PBGI, PBGI-D, LogEI, and UCB having near-identical median performance. See Figure 14 for an alternative visualization using mean and standard error.
Figure 5: Synthetic benchmark regret curves, shown using medians, as well as quartiles to assess variability. All objective functions are defined with dimension . We see in the cost-aware setting that PBGI, PBGI-D, LogEIPC, and LogEICC all perform similarly on the heavily-multimodal Ackley function, matching or outperforming the non-myopic BMSEI baseline. On the Levy and Rosenbrock functions, PBGI-D matches—and for some cost budgets outperforms—all baselines, including the non-myopic BMSEI. Under uniform costs, PBGI performs well on Ackley and Levy, but is outperformed by PBGI-D and most baselines on Rosenbrock. See Figure 14 for an alternative visualization using mean and standard error.
Figure 6: Empirical benchmark regret curves, shown using medians, as well as quartiles to show variability. We see in both the varying-cost and uniform-cost settings that PBGI exhibits strong performance on the Pest Control and Lunar Lander problems. On the Robot Pushing problem, LogEI variants perform strongest, with PBGI-D performing second-strongest and matching or outperforming all other baselines. See Figure 14 for an alternative visualization using mean and standard error.
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: An illustration of the two-dimensional Ackley, Levy, and Rosenbrock functions. 1 1 1 This visual originally appeared in [ 41 ] , and is reproduced here with permission. From the visual, one can see that these functions differ in terms of multimodality and ridge-regions within the optimization landscape.
Figure 8: Comparison between three acquisition functions, namely Expected Improvement (EI), Pandora’s Box Gittins Index (PBGI) with a large -value of , and Pandora’s Box Gittins Index with a small -value of . All three are computed using the same posterior distribution with four data points. The maximum is shown as a large dot.
Figure 9: A Bayesian optimization problem with varying costs on which LogEI, a numerically stable implementation of EI—which by construction ignores costs—has poor performance. See Sections 4 and D.1 for additional details. Like Figure 2 , this construction also mirrors [ 4 , Section A] . The domain is , which we visualize on the subinterval . Left: illustration of the non-uniform prior variance, which is given by a Matérn-5/2 kernel scaled by a narrow bump function, plus a constant. Center: the cost function, which is a narrow bump-shaped function. Right: regret curves, shown as medians and quartiles.
Figure 10: Experimental results comparing the impact of log-scaling and numerical stability on the performance of EI and PBGI, tested on Bayesian regret with and shown using quartiles. We see that Exp(LogEI) is close to Unst. EI, and similarly for S-PBGI vs PBGI. However, Log(Unst. EI) improves significantly over EI, and LogEI improves even more.
Figure 11: Runtime comparison of PBGI against baselines for computing the acquisition function on the Ackley benchmark across different dimensions ( ). We see that runtime of PBGI is slower than LogEI and TS, but faster than KG and MSEI.
Figure 12: Behavior of PBGI-D under different choices of the initial value , and the coefficient of decay , on the Bayesian regret experiment with and other parameters set the same way as in Section 4 . We show medians under samples, along with quartiles to assess variability. We see that smaller -values act similarly to the behavior seen in Figure 3 for PBGI, trading off risk-seeking vs. risk-averse behavior, but with a substantially smaller gap between the two variants. Larger -values lead to more-abrupt decay curves for , with an effect qualitatively similar to . In both cases, though our relatively-large sample size allows us to see small differences between methods, their overall impact on performance is close-to-nonexistent on the scale of variability.
Figure 13: Experimental results for the Robot Pushing empirical benchmark, with the known-cost variant (left) and unknown-cost variant (right). We see that LogEIPC, LogEICC, and PBGI-D perform best in both cases.
Figure 14: Regret curves for the Bayesian regret and synthetic benchmark experiments, as well as best observed values for the empirical experiments, shown using means (solid lines) and two times standard errors (shaded regions). See Figures 4 , 5 and 6 for details.
Figure 15: Comparison of Bayesian regret across Gaussian process priors with different kernels over different dimensions, in the uniform-cost setting. All length scales are . We see that overall behavior is similar, but the precise thresholds at which each example switches between the easy, medium-hard, and very hard regimes differ.
Figure 16: Comparison of Bayesian regret across Gaussian process priors with different kernels over different dimensions, in the cost-aware setting. All length scales are . We see that overall behavior is similar, but the precise thresholds at which each example switches between the easy, medium-hard, and very hard regimes differ.
Figure 17: Comparison of Bayesian regret across different length scales and dimensions, with a Matérn-5/2 kernel, in the uniform-cost setting. We see similar overall behavior, but each example switches between the easy, medium-hard, and very hard regimes at different precise thresholds.
Figure 18: Comparison of Bayesian regret across different length scales and dimensions, with a Matérn-5/2 kernel, in the cost-aware setting. We see similar overall behavior, but each example switches between the easy, medium-hard, and very hard regimes at different precise thresholds.
Figure 19: Comparison of regret for synthetic benchmark functions under different dimensions, in the uniform-cost setting. We see that most methods perform similarly for , with differences between the most-competitive methods emerging as dimension increases to and .
Figure 20: Comparison of regret for synthetic benchmark functions under different dimensions, in the cost-aware setting. We see that most methods perform similarly for , with differences between the most-competitive methods emerging as dimension increases to and .
More in this topic
Bayesian Optimization
Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.
See all 253 papers