Batched Energy-Entropy acquisition for Bayesian Optimization

Thank you for your comments and questions. We respond to them individually below, and are looking forward to further discussion.

1. The idea is straightforward [..] We are convinced that BEEBO is a novel acquisition function. In section B.2, we extensively compare BEEBO to the, to our knowledge, most similar existing work, GIBBON. We show how BEEBO’s entropy term can have advantages over GIBBON’s, and empirically show that the closed-form summarization term works better for large batches than GIBBON’s lower bound approximation.

Moreover, BEEBO’s closed-form softmax-weighted sum expectation is novel. It is of course not our intent to claim that we have discovered entropy reduction. However, we are not aware of any existing work that proposed an acquisition function of this form for batch BO.

2 . [...] other surrogate models.

Indeed, BEEBO was designed to work primarily with GPs, as closed-form expressions and multivariate normal posteriors enable efficient computation. We have edited the abstract to already mention the GP focus there. In the outlook section, we now provide a discussion of how BEEBO could be generalized:

Beyond GPs, BEEBO could be generalized to work with any probabilistic model. However, GPs are unique in that $H_{\textup{aug}}$ is available in closed form and can be used to compute $I(\mathbf{x})$ analytically, without solving the integral over $\mathbf{y}$ in Eq. 4. Other models may require approximations and sampling-based approaches for computing the information gain. 3. In control problems [...] the performances [...] are not outstanding [...]

We agree - on these problems, KB turns out to be very strong, not just in comparison to BEEBO, but all baselines including TuRBO, which was originally found to be state of the art for these problems. We think that this is a consequence of using LogEI. Hence, we also mentioned in the results section of the main text that KB using LogEI performs very competitively for large batches. We have now updated this statement to explicitly point to the control problems also.

4 . Although BEEBO performs well on many synthetic test problems [..] more experimental validation in specific applications.

We are happy to include additional experiments. Are there any specific ones that we should consider? Overall, we are convinced that our empirical section is comprehensive and well aligned with common practices in BO research, such as e.g. Wilson et al, NeurIPS 2017 [24], Ament et al, NeurIPS 2023 [57], Gonzalez et al. AISTATS 2016 [37].

5. [...] comparisons with other batched baselines [...] Thank you for the recommendation. We had tested multiple layouts for the results and ultimately decided that given the number of experiments and methods, including the baselines in the main text tables makes them too hard to read and interpret. We have thus maintained the focus on q-UCB, and discuss additional baselines in the text, ensuring the supplement is referred to at numerous places.

We believe that both Figure 1, as well as the 33 batch regret experiments in Table 3, fully demonstrate the controllability of the trade-off in BEEBO and highlight the key problem with q-UCB not having tight control with large batch sizes.

6. The theoretical analysis is not deep. No regret bound is analyzed.

We provide an extended analysis of the BEEBO algorithm in the supplementary section B, tying BEEBO to the rich theoretical framework of existing methodology, such as UCB, DPP and local penalization.
A theoretical analysis focusing on regret bounds, along the approach outlined for B-UCB’s bounds in [34] would indeed be very interesting, and we believe this deserves its own paper. Given the provided theoretical linkage to existing methodology, we consider the manuscript to be quite comprehensive, focusing on empirical demonstration of BEEBO's efficiency. With 33 experiments conducted, three different batch sizes (q=5,10,100), eight different acquisition strategies, several of them operated at different scales (GIBBON default & scaled, q-UCB & BEEBO at different T), and 10 replicates each (corresponding to more than 12,800 recorded BO trajectories total), we consider our benchmarking approach thorough. We believe that including an analysis of regret bounds in the manuscript as well will only challenge the focus of our paper for a reader even more, as already indicated by reviewer mXVT.

How to set the parameter T properly

This is indeed very important - we do not want the controllability (which we consider an advantageous feature in general) to become a nuisance. As outlined in our main response, we now feature the relation of T to UCB more prominently.

In line 158, why does I(x) also scale linearly with batch size?

The linear scaling of $I(x)$ is a consequence of I being a log determinant (or more precisely, the difference of two log determinants). Considering the log determinant as the sum of log eigenvalues, we see that the scaling is in fact linear, as we add an eigenvalue for each increase in Q.

The Equation A5 is not shown.

We removed this trailing newline.

What are the advantages of multiplying batch size Q in E(X)?

To maintain a Q-independent T parameter, we wish for both $I(x)$ and $E(x)$ to scale equally. As we define $E(x)$ to be the mean or the softmax-weighted sum, this expression does not scale with Q itself, and we therefore multiply it.

How does the behavior of BEBBO change with batch size?

As just outlined, the explore-exploit parametrization of BEEBO is invariant. That being said, it is correct that there will always be an effect from Q. Specifically, at large Q compared to the search domain, one might expect to see the exploration (=repulsion) term grow larger, as points will compete to occupy the same regions of the domain. We believe that our additional low-Q experiments in the updated manuscript support this, showing that at low Q higher explore rates are beneficial for BEEBO as well as for q-UCB.

We thank the reviewer for their detailed comments. We have answered them individually below, and are happy to discuss further.

Lack of Unique Selling Point

We would like to point out that as mentioned in line 275, supplementary section D.1 provides a comprehensive benchmark beyond q-UCB, including GIBBON, TS, KB, q-EI and now, as suggested by reviewer x4GE, also TurBO.

Moreover, we provide an extensive theoretical analysis of how BEEBO compares to other strategies in supplementary section B, highlighting how BEEBO can be understood in light of existing works and improve upon them, tying our method to theory such as DPPs.

BEEBO does in fact address issues that other methods face: q-UCB lacks the controllability of acquisition behavior in practice, as quantified in Table 3, and GIBBON is known to scale poorly to larger batch sizes, whereas BEEBO does so.

Not Based on MC Integration

We believe that Figure 1 and Table 3 highlight a serious practical problem with large batch q-UCB in BoTorch. Moreover, the MC q-EI also failed to outperform BEEBO in our extended benchmark.

As BEEBO is an analytical expression without sampling, we are unsure what kind of convergence guarantees are meant by the comment. We optimize BEEBO using gradient descent, and while it is, as most acquisition functions, multimodal, it can be optimized efficiently using multiple restarts, as is common in BO practice (and done in BoTorch).

Tight Control of Trade-off

Thank you for the reference. BALLET uses local regions to shrink high-dimensional search spaces, similar to TuRBO. However, unlike TuRBO, the paper is exclusively about single-point BO. It is not directly obvious to us how batched acquisition is meant to be done using their acquisition function (Eq. 7) without further generalizing BALLET. The sampling-based acquisitions (Eq. 8,9) may permit batch mode, but no mention of this is made in the paper.

We would like to note that the primary focus of our work is batch BO, rather than high-dimensional BO. We now include TuRBO as an exemplary method for trust region approaches.

We think it would be inadequate to benchmark single-point works that make no mention of batched BO in their own experiments. It is beyond the scope of our paper to generalize existing single-point works to batch mode. If there is a batched BALLET that we are not aware of, we would be happy to add it to our benchmark.
We have modified our claims to explicitly state “Tight Control of the explore-exploit trade-off in batch mode”.

Heteroskedastic BO

We fully agree that existing (single-point) methods also address heteroskedasticity. Hence we compare to Makarova et al.’s RAHBO [11] in supplement section B. We are happy to include any other relevant UCB variants that handle batch BO. A key limitation of existing work is that to our knowledge, e.g. RAHBO has not been generalized to batches. The core focus of our work is batch, with heteroskedasticity as a secondary consideration.

As you mention, UCB does not differentiate between epistemic and aleatoric uncertainty. Thus we are unfamiliar with the concept that we can get risk-averse BO from a heteroskedastic GP without modifying UCB as done in e.g. Makarova et al. Could you provide a reference?

Setting k

It is true that setting parameters in BO can be challenging. However, in our work, we considered UCB-like controllability a desirable feature. In supplementary section B.1, we show how BEEBO’s $T$ and UCB’s $\beta$ (or $\kappa$, as used this work to avoid confusion with the softmax $\beta$) are related. We always use $T’$, a parameter scaled for UCB equivalence, to allow users to follow existing guidance and allow fair experimental comparison.
As outlined in the main response, we have edited section 3.1 to feature this more prominently.

Constrained Uncertainty Sampling

[3] indeed also discusses the information gain. However, we understand that it does not use it for batch BO.
We are unsure how the “variance-only approach” comment is meant to be understood in light of our work. We would also expect only using the variance of a point to be a poor strategy for BO - however, we do no such thing.

Could you provide a reference regarding misspecification, and why batch BO in general causes more misspecification vs. single-point? We understand that [49] considers misspecification of GPs irrespective of the BO strategy, with no causal relation to batch BO.
Note that BEEBO does not use iterative fantasization - we immediately discard fantasized GPs after computing H_aug. The model itself remains unchanged for further gradient descent iterations, and no hallucinated observations are used.

We attempted including SOBER [49]. Following the quickstart guide in the official repository, and plugging that into the experimental loop that we used for all other experiments, we encountered problems such as linalg errors, invalid gaussians, and OOM errors on some test problems. We have thus decided to exclude SOBER, rather than reporting results that may not be valid due to technical limitations in the available code. We are open to add a statement on the exclusion due to these problems in the manuscript.

Data Augmentation Procedure

The terms in BEEBO and [3] do not differ - they both refer to the information gain of a GP (and call it so). We avoided using the term fantasization, as it is often understood as fantasizing (and using) $y$ values at $x$, as done in e.g. the KB baseline. As also pointed out in [3], when using the entropy (and not the posterior mean), $y$ is not used, so no hallucinated $y$ values affect the result.

As we introduce the concept already in Eq. 4, the generic form that marginalizes over $y$, we use the term augmentation, as in the that case it would not be called fantasization.
We have edited Alg. 1 to use the term “fantasize” instead of "augment" to make clear that we use fantasization to compute $C_{aug}$ on the implementation level.

We thank the reviewer for their encouraging comments! Having a compelling experimental evaluation is of key importance to us, and we have performed the requested experiments to further demonstrate BEEBO's performance.

Issue 1: Evaluation limited to large-batch setting

Thank you for the helpful suggestions! We have now ensured that

• TurBO is also discussed in the related works section.
• TurBO is included in the experiments.
• Experiments on batch sizes 5 and 10 were added.

Please see the PDF of the global response for the results of the additional experiments.
Indeed, it was our focus to improve performance in the “large-batch” setting, as this is where we found $q$-UCB to underperform, and GIBBON to not be applicable. We have now clarified this in multiple places in the paper to be more precise.

Issue 2: Lack of statistical significance

We appreciate that we need to be more rigorous with our reporting of results. We have now doubled the number of replicates and performed statistical testing on the differences in means. We can confirm that on aggregate over all experiments, BEEBO’s performance gain over the baselines is statistically significant. We have updated all results tables accordingly, and include the results of the statistical testing in the appendix. Please see the global response for combined p-values.

(For the time being, performance of GIBBON will still be based on nine replicates on five Ackley test problems, as one replicate can take multiple days. This should not affect the findings, as we already achieved statistical significance, but we will update the manuscript once the last runs finish for consistency.)

We agree that the best way to present results would be in principle to include the confidence intervals in Tables 2 and 3. However, we found that this makes the tables very dense and extremely hard to read.. As a compromise, we added the confidence intervals to the extended tables in the supplementary material (and the rebuttal PDF), and mention this in the captions of Tables 2 and 3.

The issues raised above can be addressed by running more experiments [..] Do we expect the method to work well for Q=5 and Q=10?

We really appreciate that the reviewer is mindful of computational requirements - thankfully, we managed to run all critical experiments in the rebuttal period, as outlined above. We find that also at Q=5 and Q=10, BEEBO is competitive with TuRBO and GIBBON. Especially at Q=10, q-UCB shows strong performance. Overall, both BEEBO and q-UCB benefit from higher exploration rates at low Q.

Thank you for your comments! We have incorporated the feedback in the updated manuscript, and look forward to further discussion.

The introduced parameter controlling the trade-off lacks interpretation as in previous methods.

We fully agree that an entropy quantity is in principle harder to intuitively interpret than a univariate variance, as used in (single-point) UCB. However, we note that when working in batch mode, the $q$-UCB parameter also becomes harder to interpret, as illustrated in Figure 1. In supplementary section B.1, we provide a derivation showing how BEEBO’s $T$ parameter can be set to match the interpretation of the (single-point) UCB parameter. In the experiments as well as in our available implementation, we always make use of this derivation, operating with the UCB-matched $T’$, rather than a raw $T$.

We have reworked main text section 3.1 to more prominently explain the relation of $T$ to UCB.

The completeness of the related work discussion is concerning. This is potential because the summarization lacks high-level extraction of the design of the algorithm, and the focus of the paper is, to some extent, scattered。

Thank you for pointing out the recent Yi et al. paper on MCMC for BO, which we have now included in the related works section. Could you provide further guidance as to what you would find missing from the related works section?

Given the space constraints and the focus of our paper, our intent was to offer a concise summary of batch BO methodology, rather than delving further into MC methods. As suggested by another reviewer, we have now also added TurBO to the related works section as well as the experiments.

The related works section now ends in

Eriksson et al. demonstrate that overexploration also can be problematic in higher dimensions, and alleviate this using local trust regions in TuRBO. Maintaining such regions with high precision discretization can be memory-expensive, as indicated by Yi et al., who suggest using MCMC-BO with adaptive local optimization to address this by transitioning a set of candidate points towards more promising positions.