Unexpected Improvements to Expected Improvement for Bayesian Optimization

Summary

This paper addresses a major weakness of Bayesian expected improvement acquisition functions, which are ubiquitously used for black-box optimization tasks such as computational hyperparameter tuning, materials science, and biomedical research. It is very common to use gradient-based optimizers to find local maxima of the acquisition surface, however expected-improvement acquisition functions have the very unfortunate pathology of a completely flat acquisition surface (where both the acquisition value and acquisition gradient are 0) on large regions of input space, particularly as optimization progresses and the best known solution improves. This pathology makes Bayesian optimization extremely sensitive to implementation decisions, particularly the initialization scheme of the acquisition maximization subproblem, which hinders BayesOpt practitioners in academia and industry. This paper rightfully places numerical precision and stability as one of the primary considerations in acquisition function design, and proposes simple, intuitive modifications to expected improvement acquisition functions that significantly improve performance.

Strengths

I am strongly in favor of accepting this paper. The basic problem the authors are addressing is one I have often encountered myself, and I have even tried some similar ideas as those presented in this paper to try to address the problem, however I had to shelve the project due to competing demands for my time. I'm delighted to see the problem addressed so thoroughly here. The greatest strength of this paper is the emphasis placed on how acquisition function design interacts with the optimization algorithms used to find their maxima. Generally speaking I feel this aspect of acquisition function design is often neglected in many Bayesian optimization papers, to the great detriment of the field. Given the widespread use of BayesOpt across industries, and the use of EI-style acquisition functions in particular, I think this paper could have significant practical impact on multiple fields.

Weaknesses

This work is ready for publication without any significant revisions. I would encourage reviewers in general to think about the opportunity cost of burdening authors with minor or tangential concerns, slowing the development of follow-up work. It's worth noting that the weaknesses of EI-style acquisition functions are fairly well documented in latent-space BayesOpt papers, such as [1] and [2]. Both of those works employed a heuristic I didn't see mentioned in the paper, which is to scale the max_{x_i \in D} f(x_i) term in the acquisition function with some factor < 1 (e.g. 0.9). Some brief discussion in the related work on this point could help better communicate the potential impact of this paper. [1] Tripp, A., Daxberger, E., and Hernandez-Lobato, J. M. ´ Sample-efficient optimization in the latent space of deep generative models via weighted retraining. Advances in Neural Information Processing Systems, 33, 2020. [2] Stanton, S., Maddox, W., Gruver, N., Maffettone, P., Delaney, E., Greenside, P., & Wilson, A. G. (2022, June). Accelerating bayesian optimization for biological sequence design with denoising autoencoders. In International Conference on Machine Learning (pp. 20459-20478). PMLR.

Questions

Can you comment on whether you expect batch acquisition value optimization to outperform sequential greedy optimization when there are strong locality constraints placed on the inner loop problem (i.e. d(x_0, x_t) < \varepsilon for all x_t optimization iterates)? Intuitively it seems that the performance of batch acquisition optimization once again comes down to heuristics for choosing the right collection of points as the initial solution (e.g. [2]), since the iterates may not be able to move far enough from the initialization for the improved acquisition landscape to make much difference.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

I think the discussion section could be expanded a bit. In particular I think the following rather vague sentence could be made more specific: "While our contributions may not apply verbatim to other classes of acquisition functions, our key insights and strategies do translate and could help e.g. with improving information-based [20, 42], cost-aware [26, 36], and other types of acquisition functions that are prone to similar numerical challenges." I take this to mean that this paper has primarily focused on resolving numerical difficulties arising from the use of the max operator, and other acquisition functions may have numerical issues from operators that are not the max. If this is the case I think it could be stated more clearly, as it would give readers a clearer picture of avenues for future work.

Summary

The paper proposes LogEI, family of acquisition functions with improved numerical stability over EI that makes it more suitable for gradient-based acquisition function optimization, all while retaining similar optima as EI. Pathologies of EI are visualized and analyzed, and the approximation error between qEI and qLogEI is theoretically bounded. Empirically, LogEI clearly outperforms EI on most tasks, suggesting that it can act as a drop-in replacement for EI.

Strengths

__Good motivation__: Acquisition function optimization is an often-overlooked aspect of Bayesian optimization, and the paper does a good job of displaying the difficulties of acquisition function optimization (Fig. 1) and how the proposed approach remedies the issue. __Simple, effective and extensible solution:__ Simple solutions that work are great, and LogEI (and its extensions) is good example. __Very good empirical performance:__ The improvement over EI in the results is striking on most tasks, suggesting it is simply a superior acquisition function to the default.

Weaknesses

__Anecdotal evidence for similarity with EI:__ Intuitively, It is sensible that LogEI is similar to EI. However, there is little evidence (Fig. 1) and theory (Lemma 2) to support this. I would greatly appreciate a similar Lemma for the analytic variant, and examples of when the two may not be identical. The performance gain of LogEI compared to EI is rather substantial on Ackley (~4x on Ackley-16!) and Mich, which suggests that the two may in fact not be very similar (but that LogEI may in fact simply be superior). Specifically, I don't believe the statement in Row 9, "LogEI, whose members either have _identical or approximately equal optima_ as their canonical counterparts" is well supported. __Existing LogEI and Lacking references to Related work:__ The idea of a LogEI is not novel (LogEI was an acquisition function in SMAC at one point). Admittedly, that implementation regards log-transformations of the objective [1, 2] and would not help with numerical stability in the same manner. Nevertheless, I think these warrant citation and _comparison in the experiments_, given the similarities. Moreover, it limits the novelty of the approach. __Relevance in high dimensions:__ Currently, I am not convinced by the justification for LogEI in high dimensions. To me, LogEI aims to address the pathology where the acquisition function is zero, but I don't see that happening in high-dimensional problems due to the exuberance of high-uncertainty regions (which would make the acquisition function _non-zero, but constant?_). So, why is the proposed approach particularily important in high dimensions - i.e., why does LogEI help when the acquisition function is constant as opposed to (almost) zero? This would, in my opinion, require a separate motivation than Fig. 1, empirical results aside. Moreover, I think the _zero-value_ versus _constant-value_ distinction is very important, and should be emphasized more. With this in mind, I find Fig. 2 striking and odd. 60 data points (which is when almost all points have a zero-valued gradient) on an 8-dimensional problem is not a large amount of data (not even a 2x2x...x2 grid), yet the uncertainty is small to the point of "EI and its gradients become numerically zero across most of the domain"? With all due respect, are the authors sure that this is not _just_ the gradient (and not the function value), or that the model has oddly long lengthscales? __Minor:__ - __Noisy tasks:__ Adaptation of LogEI to noisy problem settings are missing - __Lack of conventional benchmarks__: As a potential drop-in replacement for EI, seeing its performance of the method on the most conventional low-dimensional tasks (Branin, Hartmanns) would be informative. Moreover, it would be helpful for future benchmarking. For all of these bullets, I believe that evidence to clarify (and not necessarily disprove) the remarks would substantially strengthen the paper. [1]. An experimental investigation of model-based parameter optimisation: SPO and beyond. F Hutter, HH Hoos, K Leyton-Brown, Kevin P. Murphy. _GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation_. 2009. [2] Sequential model-based optimization for general algorithm configuration. F Hutter, HH Hoos, K Leyton-Brown. _Learning and Intelligent Optimization: 5th International Conference_. 2011. LogEI in SMAC: https://github.com/automl/SMAC3/blob/29355618b35dcf4b3ce3e773d633109f036dba17/smac/optimizer/acquisition.py#L503

Questions

- Is there any setting where LogEI can _not_ act as a plug-in replacement for EI, or where performance would be expected to be worse? - Have the authors experimented with LogEI non-continous search spaces, and if so, what are the findings?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Some suggestions for addressing limitations have been stated in the Weaknesses section, but are otherwise adequately addressed.

Summary

This paper identifies a numerical pathology with the expected improvement (EI) family of acquisition functions: the vanishing gradients of the acquisition function leads to failure in acquisition function optimization. A set of modified EI acquisition functions that fix the numerical pathologies have been proposed. In experiments, the proposed EI acquisition functions are shown to outperform the canonical EI acquisition functions and to perform on par with other state-of-the-art acquisition functions on Bayesian optimization benchmarks.

Strengths

- This paper focuses on a previous neglected aspect of Bayesian optimization, acquisition function optimization, and identifies the numerical pathologies associated with EI acquisition functions. This paper provides a theoretical analysis of the vanishing gradient issue. - Improvements have been proposed to EI, Monto Carlo Parallel EI, Constrained EI and EHVI. - Experiments clearly show the numerical pathology of EI optimization and the superior performance of the improved EI version. - The proposed improved EI acquisition functions perform on par with state-of-the-art acquisition functions on high dimensional synthetic functions in both sequential and batch settings.

Weaknesses

- The proposed treatment only works for the acquisition functions with vanishing gradient issues.

Questions

- It is great to have an error bound of the qLogEI. However, for acquisition functions, preserving the relative order of values is more important than absolute difference. I wonder to what extent qLogEI preserves the relative order of values compared to qEI.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The limitation of the proposed method has been discussed in the last section.

Summary

In this paper, the authors identify both through examples and theoretical analysis several numerical pathologies inherent to the computation and optimization of the Expected Improvement (EI), a popular acquisition function at the heart of Bayesian Optimization (BO) algorithms. They subsequently propose a numerical reformulation, LogEI, which achieves substantially better performances on a quite extensive range of benchmarks. This reformulation applies to all the member of the EI family: constrained EI for constrained BO, parallel EI for batch BO, and expected hypervolume improvement for multi-objective BO.

Strengths

- The paper is well-written and well-organised. - The proposed numerical fix for EI is likely to have a great impact as it may benefit to all public implementations of EI. Furthermore, it does not incur excessively longer computation times except perhaps for multi-objective BO (roughly one order of magnitude larger). - LogEI seems to produce more consistent results with respect to the initial optimization starting point compared to its canonical counterpart EI, thus reducing the need for heuristics for that matter. - All claims are backed up by an impressive amount of numerical experiments and ablation studies in each setting (vanilla BO/ constrained BO/ batch BO/multi-objective BO).

Weaknesses

I did not spot any weakness.

Questions

I do not have any questions. Edit: I have read the rebuttal and the discussions between the authors and other reviewers, my score remains unchanged.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None.

Initial response

Thanks for the additional plots. These really strengthen the motivation for the paper, and (in my opinion) highlight the vanishing gradient even better. An aside: _I found myself checking the exact value at which torch.float64 (and torch.float32) rounds to zero, and thereafter, exactly how many standard deviations of tolerance EI supports. Such reference values (in both Rebutal Fig. 1 and Fig. 2) are, in my view, even more informative than the provided thresholds._ __Existing work__ I agree with the authors on this point. The existence of SMAC LogEI does not limit the novelty. Thanks for including it in the rebuttal plots. __Equivalence of optima of analytical LogEI and EI:__ The extraordinary difference between LogEI and EI is unsettling to me, especially given the Lemma for the CR. This, to me, should mean one or two (or both) things: 1. This method is very, _very_ necessary since EI truly is zero just about everywhere 2. Not enough budget is allocated towards optimizing EI While I am _decidedly not_ advocating for simply increasing the budget of EI, it seems like the gap is simply too large at the moment. Since the lemma suggests that an increased budget is guaranteed to solve the problem, are the authors able to provide an ablation as to when this happens (or at least, provide a sense of the rate)? For now, I have increased my score to a 6. To further increase it (which I am willing to do) I would appreciate the aforementioned ablation to assess the practical impact on the budget allocated to BO acquisition function maximization.

Acknowledgement

Thanks for your response, I remain strongly in favor of acceptance. I feel that it is relevant to mention that the problem the authors solve has been such a headache for me that I've already started using the code the authors included in the supplementary material for my own work. I can't think of better evidence for the potential impact of the paper. I completely agree with your comments on the incumbent scaling approach. I will have to think a bit more about how to make my question regarding constrained batch optimization more clear. Your clarification of the discussion section is great, I hope you include it in the camera-ready.