- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes a computationally efficient acquisition function based on a randomized geometric lower bound on hypervolume improvement (HVI) for MOBO. The key idea is in constructing an axis-aligned box guaranteed to lie within the improvement region, where its side lengths are determined by a weighted max-min margin relative to the reference set. Each utility evaluation requires only operations for reference points and objectives. Although individual weighted utilities are only weakly Pareto-monotone, it is shown that averaging over a full-support distribution of positive weights restores strict Pareto-monotonicity whenever HVI is positive. Taking the posterior expectation of this randomized utility yields a lower bound on EHVI and naturally extends to noisy observations through a probabilistic reference set. For practical optimization, reference-set pruning, smooth approximations, and numerically stable Monte Carlo estimation are used. Experiments on synthetic benchmarks and real-world problems demonstrate competitive and stable hypervolume improvement, particularly in many-objective settings, while maintaining substantially lower computational costs than several existing MOBO methods.
Critical strengths
-
Computational Efficiency and Empirical Performance: The computational cost per weight sample is . This linear scalability, particularly when the number of objectives () is large, allows the method to achieve robust and stable Hypervolume improvement within a short computational time.
-
Theoretically Sound Acquisition Function: The Weighted Box Utility serves as a lower bound on HVI. By averaging over random weights, the proposed method successfully recovers strict Pareto-monotonicity. Furthermore, it allows for natural extension to Noisy Expected Hypervolume Improvement (NEHVI).
Critical weaknesses
-
Uncertainty in NEHVI Approximation Quality: Because the lower bound can be arbitrarily conservative, even if strict Pareto-monotonicity is established, we cannot guarantee that the selected candidates will lie near the true optimum of NEHVI.
-
Motivation and Real-World Context: It is challenging to envision specific scenarios where the sheer number of objectives () leads to a computational challenge. While the authors could provide a list of examples, given that high is a core motivation of this research, it would greatly enhance the paper if they presented multiple examples of real-world MOBO problems characterized by a large number of objectives.
Minor typo: The last index of r in the set R should be "M" instead of "N".
Questions for authors
-
Reference Set Construction: When keeping only the non-dominated points from the posterior mean, how is the reduction criterion and the baseline update frequency determined? What is the impact of this setting on performance?
-
Independent Sampling Meaning: Does this ignore the posterior correlation between candidates and baselines, or the correlation between the objectives themselves? Which assumption was used in the experiments?
-
Objective Function Scaling: Doesn't the weight distribution depend on the scale of the objective functions? If so, what pre-normalization method is used?
-
Implementation of Averaging: How effective is the theoretical strictness in finite samples? What tangible benefit does this strict Pareto-monotonicity provide in practical scenarios, and how does it perform in finite sample settings?
6 comments
Author Rebuttal: Questions
Questions
-
Reference Set Construction: When keeping only the non-dominated points from the posterior mean, how is the reduction criterion and the baseline update frequency determined? What is the impact of this setting on performance?
We understand the question as asking how the reference set is selected and how often it is updated, analogous to the baseline pruning of qLogNEHVI in BoTorch (prune_baseline). In RaMMOBO, both are fixed and have no tuning parameters. The reference set consists of the evaluated inputs whose posterior means are nondominated (Algorithm 1, line 1; Appendix C.3), and it is recomputed in every BO iteration after the GP is refit. Without noise, restricting the reference set to the nondominated points does not change the acquisition function: a reference dominated by another reference is always farther from the candidate, so it never determines the margin . With noise, it is an approximation (Section 3.3).
-
Independent Sampling Meaning: Does this ignore the posterior correlation between candidates and baselines, or the correlation between the objectives themselves? Which assumption was used in the experiments?
Independent sampling ignores the posterior correlation across inputs, i.e., treats the candidate outcome and all reference outcomes as independent. There is no cross-objective correlation to ignore, since all methods use an independent GP per objective (Appendix C.2). All experiments use this independent version, which is a common choice in the literature.
To quantify the effect, the revision compares this with exact joint sampling from in Table 4 (Appendix D.3). The final hypervolume of the two versions differs by less than the variation across seeds, while the joint version is about 20–40% slower per iteration.
-
Objective Function Scaling: Doesn't the weight distribution depend on the scale of the objective functions? If so, what pre-normalization method is used?
Yes. This is why outcomes are standardized in every iteration and the reference point is mapped into the same units (Appendix C.2).
-
Implementation of Averaging: How effective is the theoretical strictness in finite samples? What tangible benefit does this strict Pareto-monotonicity provide in practical scenarios, and how does it perform in finite sample settings?
We particularly thank the reviewer for this interesting question. The implementation estimates (Eq. 16) with a Monte Carlo estimate which uses i.i.d. draws of random weights . For , let be the probability of separating them, i.e., for a single weight ; Appendix A.2 shows . Since every is Pareto monotone, holds exactly if for at least one . The estimate therefore ties on this pair only if no separates them, which, since the weights are drawn independently, happens with probability . The revised Appendix A.3 states this result and gives an explicit lower bound on . Empirically, along RaMMOBO runs on RE91 and DTLZ2 (), weights separated 99% of the tested pairs, whereas the single weight separated only 9–13% (Table 1, Appendix A.3).
The practical benefit is shown in the ablation of Figure 2: "Clipped EMmI, no weights" differs from RaMMOBO only by the random weights, and adding them improves the hypervolume increasingly with .
Author Rebuttal: References
[1] Fleming, P. J., Purshouse, R. C., & Lygoe, R. J. (2005). Many-objective optimization: An engineering design perspective. In Evolutionary Multi-Criterion Optimization (EMO 2005), Lecture Notes in Computer Science, Vol. 3410 (pp. 14–32). Springer.
[2] Li, B., Li, J., Tang, K., & Yao, X. (2015). Many-objective evolutionary algorithms: A survey. ACM Computing Surveys, 48(1), 13:1–13:35.
[3] Fromer, J. C., & Coley, C. W. (2023). Computer-aided multi-objective optimization in small molecule discovery. Patterns, 4(2), 100678.
[4] Tanabe, R., & Ishibuchi, H. (2020). An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 89, 106078.
[5] Jiang, C., Huang, J., & Li, M. (2026). Do we really need to approach the entire Pareto front in many-objective Bayesian optimisation? arXiv:2604.09417.
[6] Deb, K., & Jain, H. (2014). An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4), 577–601.
[7] Hadka, D., Reed, P. M., & Simpson, T. W. (2012). Diagnostic assessment of the Borg MOEA for many-objective product family design problems. In IEEE Congress on Evolutionary Computation (CEC 2012) (pp. 1–10).
[8] Lygoe, R. J., Cary, M., & Fleming, P. J. (2013). A real-world application of a many-objective optimisation complexity reduction process. In Evolutionary Multi-Criterion Optimization (EMO 2013), Lecture Notes in Computer Science, Vol. 7811. Springer.
[9] Hurford, A. P., Huskova, I., & Harou, J. J. (2014). Using many-objective trade-off analysis to help dams promote economic development, protect the poor and enhance ecological health. Environmental Science & Policy, 38, 72–86.
[10] Craft, D., & Bortfeld, T. (2008). How many plans are needed in an IMRT multi-objective plan database? Physics in Medicine and Biology, 53(11), 2785–2796.
[11] Binois, M., Picheny, V., Taillandier, P., & Habbal, A. (2020). The Kalai–Smorodinsky solution for many-objective Bayesian optimization. Journal of Machine Learning Research, 21(150), 1–42.
Author Rebuttal: Weaknesses
We thank the reviewer for the careful reading. We are glad that the reviewer appreciates what we consider the key contributions of our work: an acquisition function with O(NM) cost that lower-bounds HVI and recovers strict Pareto monotonicity through random weights.
Weaknesses
We agree that optimizing a lower bound does not guarantee proximity to the exact NEHVI maximizer. However, our bound has the advantage to be strictly positive whenever the exact HVI is positive, whereas approximate decompositions used by qLogNEHVI assign zero improvement to all candidates in 13–58% of iterations at high M (Appendix C.4).
Empricially, our strong BO results empirically demonstrate that the bound guides optimization effectively. Moreover, our rank agreement analysis shows consistent candidate rankings between RaMMOBO and qLogNEHVI for M≤4 (Figure 10, Appendix C.9). Agreement weakens primarily on RE91, where qLogNEHVI itself relies on approximation, making it difficult to attribute the discrepancy to either method alone.
Thus, while we do not claim proximity to the exact NEHVI maximizer, our approach provides a principled acquisition function with structural guarantees and demonstrated empirical effectiveness.
In the submission we provide several examples and motivations for high-dimensional MOBO, which we briefly summarize here. First, the introduction cites multiobjective applications [1–4]. Second, the experiments include a real-world 9-objective problem, RE91 (car-cab design). There, RaMMOBO outperforms all competing methods (Figure 3), and its acquisition optimization is about two orders of magnitude faster than qLogNEHVI's (Figure 5). Third, Figure 4 scales DTLZ2 to M=14.
Regimes where M≥8 are exactly where existing acquisition functions break, and we measure this directly:
The bottleneck is therefore not a single hypervolume computation but the many differentiable HVI evaluations that acquisition optimization requires. An independent study reaches the same conclusion: Jiang et al. [5] evaluate EHVI/NEHVI only up to M=5 because "the acquisition optimisation wall time becomes prohibitively high when the number of objectives increases to 10".
Documented real-world problems with many objectives include: