- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the estimation of constrained expected hypervolume improvement (qCEHVI) in batch multi-objective Bayesian optimisation. Existing implementations use a sigmoid relaxation to approximate feasibility indicators, which introduces bias and requires a temperature parameter. The authors show that directly replacing the sigmoid with the marginal probability of feasibility can also introduce bias when the batch size is greater than one. To address this issue, they propose a Rao-Blackwellized estimator based on conditional feasibility probabilities. The proposed estimator is shown to be unbiased, differentiable almost everywhere, and to have lower variance than the hard-indicator estimator. Experiments on synthetic and real-world constrained optimisation problems demonstrate its effectiveness and stability across different batch sizes.
Critical strengths
- The paper identifies a clear problem with using marginal PoF in batch constrained qEHVI. The authors explain why this can introduce bias and provide theoretical analysis to support their findings.
- The proposed method is simple and does not require tuning the sigmoid temperature parameter. The authors also prove that the estimator is unbiased, differentiable, and has lower variance than the hard-indicator estimator. The experiments show promising results across different batch sizes.
Critical weaknesses
- The experimental evaluation is limited to only five benchmark problems. It is unclear why these particular problems were selected. All of them have only two or three objectives, and the number of decision variables ranges from 2 to 10. The paper does not show whether the method works well on more challenging problems with higher dimensions and more objectives.
- The comparison with existing BO methods is limited. The paper does not include ParEGO or constrained ParEGO, which would be relevant baselines. Instead, it includes evolutionary algorithms such as NSGA-II and NSGA-III, which typically use relatively large populations and may not perform well under small evaluation budgets. Comparisons with more constrained BO methods would provide a better understanding of the proposed method's performance.
- The paper does not report the computational time of the proposed method. Although Section 3.4 states that RB and sigmoid have similar computational complexity, it would be useful to compare their actual running times, especially for larger batch sizes and more constraints.
Questions for authors
- Why were these five benchmark problems selected? Could the authors explain whether they cover the main challenges that the proposed method aims to address?
- How does the proposed method perform on problems with more decision variables and objectives? The current experiments only consider problems with 2 to 10 decision variables and 2 or 3 objectives.
- How does the proposed method compare with other constrained BO methods, such as constrained ParEGO? Would these methods provide more meaningful comparisons under small evaluation budgets?
- How does the actual running time of RB compare with the sigmoid approach? Does the difference become larger as the batch size or number of constraints increases?
- How does the proposed method perform when the constraints are correlated? The current experiments only consider independent GPs.
- How does the variance reduction in Theorem 2 affect the Monte Carlo estimation in practice? Could the authors compare the estimator variance and estimation error under different numbers of Monte Carlo samples?
- How does the marginal-PoF bias change with the distance or correlation between running points? Is this bias mainly a problem when running points are highly concentrated?
- Does the proposed method provide similar benefits when using joint batch optimisation instead of greedy batch selection?
3 comments
Thank you for the additional experiments and detailed clarifications, which have addressed most of my concerns. I will maintain my positive score.
Thank You for Your Response and Positive Assessment
Thank you for your response and for your positive assessment. We're glad the additional experiments and clarifications addressed most of your concerns.
Thank you for your detailed reviews. We summarize the updates to the manuscript:
Experiment Coverage
W2&Q3: BO Baselines
We added qParEGO and qHVKG [4] to Fig. 4.
Q6: Variance Reduction
Thm. 2 (iii) gives the per-sample variance gap E[HVI2p(1−p)] (p: conditional PoF). For iid draws, the gap is divided by S (Cor. 11), so the advantage persists for large S. In practice, RB benefits most when p is far from 0 and 1 (feasibility is uncertain). While our QMC makes the theory approximate, new Fig. 9 shows RB's standard deviation at S=32 is already below the hard indicator's at S=128 on most slices.
W3&Q4: Runtime Report
We added per-call AF runtime report (Fig. 13). The runtime difference between sigmoid and RB is indistinguishable, consistent with Sec. 3.4. Marginal PoF is slightly faster because it uses an unconditional rather than conditional GP. Pipeline runtime also depends on AF optimization iteration counts (Fig. 6).
W1&Q1/2: Problem Selection
We clarified our problem selection rationale in the manuscript. Handling low feasibility is crucial, so our setup pairs one relatively easy problem (Disc Brake) with several strict ones. Multi-product Batch Plant (0.6% feasibility), and Process Synthesis (<10−4%) represent strict real-world constraints. We made sure that mixed space and tri-objective problems are also covered. TNK highlights how marginal PoF bias degrades performance compared to RB. SRN is a strict synthetic function.
While high-dimensional and many-objective analyses are valuable, comprehensive studies fall outside our scope. Nevertheless, to address your concern, we added two high-dimensional problems. MW7 (d=15) is taken from the BoTorch test function suite where MW7 & C2DTLZ2 are the only high-dimensional CMO options and MW7 has far lower feasible ratio. DASCMOP2 (difficulty 2) is taken from pymoo where it was the highest-dimensional choice and difficulty 2 is controlled for low feasible ratio. RB is competitive with sigmoid (Fig. 10). However, we believe that a more detailed analysis is required to develop better designs for high-dimensional problems, which we leave for future work.
Regarding the number of objectives, evaluating M=2 or 3 is standard MOBO practice. Recent BoTorch literature [1-4] does not test constrained many-objective (M>3) problems (though [3] tested unconstrained M=4). Since our core focus is enhancing constraint handling, we believe the current scope of our evaluation is appropriate.
Q7: Marginal-PoF Bias
The bias -Cov[HVI, I] (Prop. 1) grows with the posterior correlation between the candidate's and running points' constraints. Prop. 14 shows bias vanishes without correlation. It is bounded by V[HVI]p(1−p) (marginal PoF: p), maximizing near the feasibility boundary (Rem. 15). Concentration isn't required, as one correlated running point suffices. This makes all cross-covariances nonnegative, turning the bias into a one-sided overestimate (Prop. 19) pulling the batch toward the cluster.
Q5/8: Joint Batch Optimization & Correlated Constraints
Thm. 2 (appendix Thms. 9, 10, 17) and Prop. 1 (Thm. 12) remain valid under joint optimization and correlated constraints. Thus, exactness, variance-reduction, differentiability, and marginal-PoF bias results carry over. Only the closed-form univariate expression (Cor. 21, Rem. 25) is lost. Table 1 summarizes this, and limitations note the joint-batch case lacks empirical evaluation.
For correlated constraints, we added an experiment (Fig. 11) using TNK and modified TNK with duplicated constraints. Results show negatively correlated constraints degrade RB's performance with multi-output GP (aligning with Zhang et al. [5]), but duplicating a constraint reversed this. We note the limited scope in the text, but hope this resolves your question.
References
[1] Ament et al. Unexpected Improvements to Expected Improvement for Bayesian Optimization. NeurIPS, 2023
[2] Daulton et al. Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization. NeurIPS, 2020
[3] Daulton et al. Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces. UAI, 2022
[4] Daulton et al. Hypervolume knowledge gradient: a lookahead approach for multi-objective Bayesian optimization with partial information. ICML, 2023
[5] Zhang et al. Dependence in constrained Bayesian optimization: When do we need it and how does it help? Optimization Letters, 2024.