acceptodds
Under review as a conference paper at ICLR 2027

RaMMOBO: Random Max-Margin Multi-Objective Bayesian Optimization

Abstract

Multi-objective Bayesian optimization (MOBO) maximizes expensive black-box objectives with the goal of approximating the *Pareto set*, whose objective vectors cannot be improved in one component without sacrificing another. A common quality measure is *hypervolume*, the volume in objective space dominated by these vectors relative to a reference point. *Expected hypervolume improvement* (EHVI) directly targets this metric and is one-step Bayes-optimal, but its standard computation scales exponentially with , making it prohibitively expensive for many-objective problems. We introduce *random max-margin multi-objective Bayesian optimization* (RaMMOBO), whose acquisition function lower-bounds EHVI while requiring only linear cost in to evaluate. RaMMOBO measures the volume of a max-margin box contained in a candidate's hypervolume-improvement region and averages over random reweightings of the objective space, yielding a utility that is strictly Pareto-monotone on hypervolume-improving outcomes. It naturally handles noisy observations and different probabilistic surrogates and supports efficient gradient-based optimization. Across synthetic and real-world benchmarks, RaMMOBO matches or outperforms state-of-the-art methods, with largest gains at higher , with acquisition optimization up to two orders of magnitude faster than LogNEHVI. Our implementation is available at https://anonymous.4open.science/r/rammobo.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Multi-objective Bayesian Optimization, Acquisition Function, Expected hypervolume improvement, Gaussian Process

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_xXfFOpenReview ↗
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 O(NM)O(NM) operations for NN reference points and MM 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
  1. Computational Efficiency and Empirical Performance: The computational cost per weight sample is O(NM)O(NM). This linear scalability, particularly when the number of objectives (MM) is large, allows the method to achieve robust and stable Hypervolume improvement within a short computational time.

  2. 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
  1. 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.

  2. Motivation and Real-World Context: It is challenging to envision specific scenarios where the sheer number of objectives (MM) leads to a computational challenge. While the authors could provide a list of examples, given that high MM 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
  1. 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?

  2. 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?

  3. Objective Function Scaling: Doesn't the weight distribution depend on the scale of the objective functions? If so, what pre-normalization method is used?

  4. 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
AuthorsOpenReview ↗

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)O(NM) cost that lower-bounds HVI and recovers strict Pareto monotonicity through random weights.

Weaknesses

  1. 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.

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 MM (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≤4M \leq 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.

  1. Motivation and Real-World Context: It is challenging to envision specific scenarios where the sheer number of objectives (MM) 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.

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=14M = 14.

Regimes where M≥8M \geq 8 are exactly where existing acquisition functions break, and we measure this directly:

  • MESMO and JESMO exceed 110 GB of memory at M=14M = 14 (Appendix C.4)
  • qLogNEHVI relies on box decompositions of the dominated region. At large MM, it uses an approximate decomposition, which is empty in 13%, 46% and 58% of iterations at M=10,12,14M = 10, 12, 14, so qLogNEHVI falls back to a random candidate (Appendix C.4)
  • with exact box decompositions instead, the standard BoTorch implementation of qLogNEHVI requires at least 10 days for a single BO iteration at M=10M = 10. The revised version makes this explicit in Table 3, Appendix C.7.

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=5M = 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:

  • car-cab design, M=9M = 9 [4, 6] (our RE91);
  • general-aviation aircraft product-family design, M=10M = 10, severely constrained [7];
  • diesel-engine calibration, M=10M = 10 [8];
  • multi-reservoir operation with 10 stakeholder objectives [9];
  • radiotherapy (IMRT) planning, about 10 objectives, one per organ at risk [10];
  • calibration of a building-occupant simulation (about 30 min per run, M=9M = 9) and CNN hyperparameter tuning (M=8M = 8), both solved with Bayesian optimization [11].
AuthorsOpenReview ↗

Author Rebuttal: Questions

Questions

  1. 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 Δw\Delta_w. With noise, it is an approximation (Section 3.3).

  1. 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 Y(x)Y(x) and all reference outcomes Y(xi)i=1n\\{Y(x_i)\\}_{i=1}^n 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 p(Y(x),Y(x1),…,Y(xn) ∣ D)p(Y(x), Y(x_1), \dots, Y(x_n) \, | \, \mathcal{D}) 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.

  1. 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 zz is mapped into the same units (Appendix C.2).

  1. 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 Lˉ=EW[LW]\bar{L} = \mathbb E_W[L_W] (Eq. 16) with a Monte Carlo estimate L^S\hat{L}_S which uses SS i.i.d. draws of random weights w1,…,wSw_1, \dots, w_S. For y≻y′y \succ y', let pp be the probability of separating them, i.e., Lw(y)>Lw(y′)L_w(y) > L_w(y') for a single weight ww; Appendix A.2 shows p>0p > 0. Since every LwL_w is Pareto monotone, L^S(y)>L^S(y′)\hat{L}_S(y) > \hat{L}_S(y') holds exactly if Lwi(y)>Lwi(y′)L_{w_i}(y) > L_{w_i}(y') for at least one wiw_i. The estimate therefore ties on this pair only if no wiw_i separates them, which, since the weights are drawn independently, happens with probability (1−p)S(1-p)^S. The revised Appendix A.3 states this result and gives an explicit lower bound on pp. Empirically, along RaMMOBO runs on RE91 and DTLZ2 (M=10,14M = 10, 14), S=128S = 128 weights separated 99% of the tested pairs, whereas the single weight w=1w = \mathbf 1 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 MM.

AuthorsOpenReview ↗

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.

Reviewer_sDg9OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a multi-objective BO method for solving multi-objective, particuarly many-objective, optimization problems. It argues that the calculation of HV in the EHVI is too slow when dealing with problems with many objectives, and thus introducing a hypercube-based measure (i.e., calculating the volume based on the closest distance of the solution to the HV enclosed by the existing solutions) to accelerate the search, along with a random weighting technique.

Critical strengths
  1. Expensive problems are common in real-world application. This paper works on such problems by using BO which is a promising choice to deal with it. In addition, many-objective optimization is not uncommon and a method designed for dealing with such problems is of practice signficance.

  2. I like Figure 1 in the Introduction, which is intuitive and easy for the reader to understand the method proposed, without looking into the details in later sections.

Critical weaknesses
  1. A critical concern is the implementation of HV. It is known that the calculation of HV increases expoentionally with the number of objectives. However, its implementation can be signficantly faster than many people think. As far as I know, even for the implementation two decades ago (an improved dimension-sweep algorithm for the hypervolume indicator, CEC 2006), which is not the faster algorithm and with far from the least time complexity, calculating a set of 100 solutions with 10 objectives takes one or two seconds. This is well-known in the evolutioanry computation (EC) community, however, unfortunately less awared in the BO community. This is the gap between two communities, and the implementation of EHVI in open sources used widely in BO community is far from efficient. Moreover, for BO which usually has a few hundreds of solutions to be evaluated, I don't think the calculation of HV causes a big issue if it is implemented properly. Note that there are some theoretical work that can reduce the HV calculation complexity considerably.

  2. Again, for the calculation of HV, there are now alternatives, for example, using the decomposition (with a lot of well-distributed weights) to approximate the hypervolume, which can be rather reliable. There are some very recent works in the EC areas.

  3. The proposed method is to approximate the EHVI by a cube, which apparentaly may not be very accurate, but interestingly, why does its performance seem to be better than it in the experiment study.

  4. It is not clear to me why this method works well. There can be a situation that one solution is much better than another on all objectives but one, which is only slightly better. For such a situation, your metric will give a tiny value (as you consider the cube formed by the closest distance), however, the original HV will count in all objectives, hence a much better metric value.

  5. I like the illustration of Figure 1. However, it doesn't cover the random-weighting. Is it possible to provide an illustrative for it?

  6. Some settings in the experiment are not standard. For example, DTLZ7 with d=5, other DTLZ problems with d=m+1. DTLZ7 should have m+19 variables. In addition, why only a couple of DTLZ, how about other DTLZ problems like DTLZ5 and DTLZ6.

Questions for authors

I would like the authors to respond to the six weaknesses above, along with the following one question.

What is the reference point for the reference point in the HV calculation for both the proposed algorithm and comparative experiments?

8 comments
AuthorsOpenReview ↗

Author Rebuttal: Weaknesses (Part I)

We thank the reviewer for the insightful comments and are glad that our work is perceived as sound, important, and clearly communicated.

Weaknesses

  1. A critical concern is the implementation of HV. [...] for BO which usually has a few hundreds of solutions to be evaluated, I don't think the calculation of HV causes a big issue if it is implemented properly. Note that there are some theoretical work that can reduce the HV calculation complexity considerably.

We thank the reviewer for pointing us to this line of work, which we had been less aware of. We benchmarked against BoTorch, the de-facto standard in BO, and now include dedicated HV algorithms in the related work (Section 4) and as an additional baseline: Monte Carlo EHVI in which every HVI is computed exactly by WFG [3]. Table 3 (Appendix C.7) reports its wall-clock time.

We agree that a single HV computation for about 100 points at M=10M=10 is fast with these algorithms. However, the BO workload is different: one acquisition step evaluates HVI for S=128S = 128 posterior samples at thousands of candidate inputs, i.e., about 5⋅1055 \cdot 10^5 HVI computations per selected point. Noisy EHVI further requires a separate front per posterior sample, and a batch of qq points requires qq such steps.

Empirically, exact EHVI with WFG can indeed be fast for small NN and qq on our benchmark fronts. However, its worst-case runtime remains exponential in MM [4, 5], and some fronts in our benchmarks are already expensive at small NN: on the disconnected front of DTLZ7 (M=14M = 14), a single step takes up to 2 hours. As NN and qq grow, WFG becomes prohibitively expensive also on the more benign DTLZ2 front: a single BO iteration with N=800N = 800 and q=4q = 4 takes 3–7 days at M=14M = 14 (Table 3 (c)), whereas RaMMOBO selects a point within minutes on the same fronts.

  1. Again, for the calculation of HV, there are now alternatives, for example, using the decomposition (with a lot of well-distributed weights) to approximate the hypervolume, which can be rather reliable. There are some very recent works in the EC areas.

We would appreciate pointers to the specific works the reviewer has in mind, so that we can discuss them in the revised related work section. We already compare against the closest such approximation in BO, a Monte Carlo estimate of the hypervolume-as-expectation identity of Zhang & Golovin (2020): it underperforms RaMMOBO considerably on almost all tasks (Figure 15, Appendix D.2), and its concentration guarantee depends exponentially on MM.

  1. The proposed method is to approximate the EHVI by a cube, which apparentaly may not be very accurate, but interestingly, why does its performance seem to be better than it in the experiment study.

For small MM, where qLogNEHVI can be computed exactly (i.e., α=0\alpha = 0), RaMMOBO performs on par with qLogNEHVI in terms of hypervolume. For large MM, the main improvement over qLogNEHVI comes from the fact that the latter has to use approximate box decompositions (α>0\alpha > 0) to stay computationally feasible. In this setting, qLogNEHVI's approximate decomposition may be empty, in which case a random candidate is proposed (Appendix C.4). For M=14M=14 (DTLZ2), this happened in 5858\\% of all iterations. In contrast, RaMMOBO requires no box decomposition and therefore never falls back to random proposals.

AuthorsOpenReview ↗

Author Rebuttal: Weaknesses (Part II), Questions

  1. It is not clear to me why this method works well. There can be a situation that one solution is much better than another on all objectives but one, which is only slightly better. For such a situation, your metric will give a tiny value (as you consider the cube formed by the closest distance), however, the original HV will count in all objectives, hence a much better metric value.

We believe this is a misunderstanding of the margin Δ(y;R)=min⁡imax⁡m(ym−ri,m)+\Delta(y; R) = \min_i \max_m (y_m - r_{i,m})_+ (Eq. 10): for each incumbent, it takes the largest improvement over the objectives, not the smallest. Consider exactly the reviewer's example with one incumbent r=(0,0,0)r = (0, 0, 0), z=(−1,−1,−1)z = (-1, -1, -1), and y=(10,10,0.1)y = (10, 10, 0.1), which is much better in two objectives and only slightly better in the third. The margin is Δ=10\Delta = 10, not 0.10.1, and the box has sides (10,10,1.1)(10, 10, 1.1) and volume 110110, against HVI=132.1\mathrm{HVI} = 132.1, i.e., the bound captures 8383\\%.

While this does not mean that the bound is tight in general, it need not be to be useful: an acquisition function is used only through its maximizer. Empirically, RaMMOBO and qLogNEHVI rank candidates consistently for M≤4M \le 4, with agreement weakening only on RE91, where qLogNEHVI itself is approximate (Figure 10, Appendix C.9).

  1. I like the illustration of Figure 1. However, it doesn't cover the random-weighting. Is it possible to provide an illustrative for it?

We are happy that Figure 1 improved clarity. The revised version of the paper will include an illustration of the random weighting.

  1. Some settings in the experiment are not standard. For example, DTLZ7 with d=5, other DTLZ problems with d=m+1. DTLZ7 should have m+19 variables. In addition, why only a couple of DTLZ, how about other DTLZ problems like DTLZ5 and DTLZ6.

Our experimental settings are standard in the MOBO literature against which we benchmark. Specifically, DTLZ3 and DTLZ7 with d=10d=10 and d=5d=5, respectively, follow exactly the setup in qPOTS [1], while DTLZ2 with d=M+1d=M+1 follows BOtied [2]. Our choices are consistent with the relevant MOBO literature and ensure comparability with prior work.

Moreover, we have included experiments on DTLZ4, DTLZ5, and DTLZ7 (M∈{10,14}M \in \{10, 14\}) in the revised Appendix (Figure 7), where RaMMOBO is best or tied-best at M=14M = 14 across these front geometries.

Questions

  1. [...] What is the reference point for the reference point in the HV calculation for both the proposed algorithm and comparative experiments?

All experimental settings, including reference points, are listed in Table 2 (Appendix).


[1] Renganathan, A., & Carlson, K. (2025). qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson sampling. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 258, pp. 4051–4059.

[2] Park, J. W., Tagasovska, N., Maser, M., Ra, S., & Cho, K. (2024). BOtied: Multi-objective Bayesian optimization with tied multivariate ranks. In Proceedings of the 41st International Conference on Machine Learning (ICML), PMLR 235, pp. 39813–39833.

[3] While, L., Bradstreet, L., & Barone, L. (2012). A fast way of calculating exact hypervolumes. IEEE Transactions on Evolutionary Computation, 16(1), 86–95.

[4] Bringmann, K., & Friedrich, T. (2010). Approximating the volume of unions and intersections of high-dimensional geometric objects. Computational Geometry, 43(6–7), 601–610.

[5] Chan, T. M. (2013). Klee's measure problem made easy. In IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 410–419.

Dear Reviewer sDg9,

Thank you very much for your help with reviewing for ICLR'27!

The authors have now responded to your reviews. As the discussion period is approaching the end, I'm wondering if you could have a look at the authors' responses and see whether they have addressed your concerns. And could you also leave a comment to let the authors know your thoughts? If any concerns remain, please explain which ones have not been addressed and why.

Warm regards, Your AC

Reviewer_JASXOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes RaMMOBO -- which claims to offer a faster acquisition function, that ends up as a lowerbound to EHVI, to improve scalability of MOBO with the number of objectives. The do this with the volume of a geometrically constructed box that is guaranteed to lie within the hypervolume improvement region

The proposed method builds upon expected maximin improvement (EMmI) and introduces two modifications. First, the maximin margin is converted into a reference-point-aware hyper rectangle whose volume provides a lower bound on hypervolume improvement. Second, random objective weights, drawn from a Dirichlet distribution, are used to vary the box geometry. Averaging these over these weights yields a utility that is strictly Pareto-monotone for hypervolume improving outcomes.

The authors show the complexity scales linarly with number of objectives MM; and empirical results show M=2−14M=2-14, with evidence of better performance at M≥10M\geq 10.

Critical strengths
  • strict Pareto monotonicity
  • linear scaling of complexity
  • and a lower bound connection to EHVI
Critical weaknesses
  • Typically, multiobjective optimization involve atmost a dozen or so objectives. So, it makes me wonder, why improving the scale-up with MM is a compelling problem to solve. What do we gain by saving a few seconds/minutes of wallclock time in the MOBO method, when each objective itself can be quite expensive (taking hours/days) to evaluate?
  • The method does not show how to handle constraints; rarely in practice do multiobjective problems feature without constraints.
Questions for authors
  • The strongest results for M≥10M \geq 10 are obtained exclusively on DTLZ2. Is there additional evidence from structurally different many-objective problems demonstrating that the improvement is not specific to this benchmark's geometry?
  • While the reasons for speed-up from RaMMBO is clear, can you explain why it is more accurate than competitors?
  • Some of the baselines, e.g. qPOTS (Renganathan and Carlson (2025)) have been shown in their paper to outperform qNEHVI, JESMO, PESMO, MESMO, and even Sobol -- on experiments such as DTLZ2, Vehicle Safety, and Car side-impact. Can the authors provide details of the other baseline implementations for transparency?
  • Why were variants of DTLZ2 alone tested instead of other synthetic functions.
4 comments
AuthorsOpenReview ↗

Author Rebuttal: Weaknesses

We thank the reviewer for the constructive comments and are glad that many key elements of our contributions---like strict Pareto monotonicity, O(NM)O(NM) scaling, and showing a global lower bound to NEHVI---are considered as critical strengths.

Weaknesses

  1. Typically, multiobjective optimization involve atmost a dozen or so objectives. So, it makes me wonder, why improving the scale-up with is a compelling problem to solve. What do we gain by saving a few seconds/minutes of wallclock time in the MOBO method, when each objective itself can be quite expensive (taking hours/days) to evaluate?

This characterization severely understates the computational challenges addressed in the paper. Even for M=10M=10, the standard BoTorch implementation of qLogNEHVI (using exact box decompositions, i.e. α=0\alpha = 0) requires at least 10 days for a single BO iteration, making it impractical for most applications. For large MM, Figure 5 measures wall-clock for approximate qLogNEHVI (α>0\alpha > 0): The revised Appendix includes Table 3 (a), showing wall-clock time for exact qLogNEHVI.

  1. The method does not show how to handle constraints; rarely in practice do multiobjective problems feature without constraints.

While there are many unconstrained multiobjective problems [1-6], we thank the reviewer for suggesting this extension: While we originally considered constraints to be out of scope, we extended RaMMOBO to incorporate constraints, which still preserves the lower bound to constrained NEHVI. In our revision, Section 3.4 details our extended method, and Figure 6 empirically shows competitive performance on all but one benchmark, where we achieve state-of-the-art results. Due to time constraints, we conducted this experiment with a reduced set of comparison methods, and the final revision will include all methods.


[1] 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.

[2] Lu, Z., Cheng, R., Jin, Y., Tan, K. C., & Deb, K. (2024). Neural architecture search as multiobjective optimization benchmarks: Problem formulation and performance assessment. IEEE Transactions on Evolutionary Computation, 28(2), 323–337.

[3] Hughes, E. J. (2007). Radar waveform optimisation as a many-objective application benchmark. In Evolutionary Multi-Criterion Optimization (EMO 2007), Lecture Notes in Computer Science, Vol. 4403 (pp. 700–714). Springer.

[4] Sener, O., & Koltun, V. (2018). Multi-task learning as multi-objective optimization. In Advances in Neural Information Processing Systems 31 (NeurIPS 2018).

[5] Liao, X., Li, Q., Yang, X., Zhang, W., & Li, W. (2008). Multiobjective optimization for crash safety design of vehicles using stepwise regression model. Structural and Multidisciplinary Optimization, 35(6), 561–569.

[6] Deb, K., Thiele, L., Laumanns, M., & Zitzler, E. (2005). Scalable test problems for evolutionary multiobjective optimization. In A. Abraham, L. Jain, & R. Goldberg (Eds.), Evolutionary Multiobjective Optimization: Theoretical Advances and Applications (pp. 105–145). Springer.

AuthorsOpenReview ↗

Author Rebuttal: Questions

Questions

  1. The strongest results for are obtained exclusively on DTLZ2. Is there additional evidence from structurally different many-objective problems demonstrating that the improvement is not specific to this benchmark's geometry?

We respectfully disagree: As shown in Figure 3, our method also achieves state-of-the-art results on RE91, a real-world benchmark. Moreover, Figure 8 (Appendix) reports additional state-of-the-art IGD+ results on DTLZ7 (synthetic) and Vehicle Design (real-world), which we acknowledge may not have been apparent from the main paper alone.

However, since we agree that more large-MM experiments on different Pareto front geometries strengthen our paper, we have included experiments on DTLZ4, DTLZ5, and DTLZ7 (M∈{10,14}M \in \{10, 14\}) in the revised Appendix (Figure 7): Across front geometries that differ from DTLZ2 (biased solution density in DTLZ4, a degenerate one-dimensional front in DTLZ5, 2M−12^{M-1} disconnected regions in DTLZ7), RaMMOBO is best or tied-best at M=14M = 14. At M=10M = 10, only qLogNEHVI on DTLZ7 beats it, at roughly 200×200\times the acquisition cost.

  1. While the reasons for speed-up from RaMMBO is clear, can you explain why it is more accurate than competitors?

For small MM, where qLogNEHVI can be computed exactly (i.e., α=0\alpha = 0), RaMMOBO performs on par with qLogNEHVI in terms of hypervolume. For large MM, the main improvement over qLogNEHVI comes from the fact that the latter has to use approximate box decompositions (α>0\alpha > 0) to stay computationally feasible. In this setting, qLogNEHVI's approximate decomposition may be empty, in which case a random candidate is proposed (Appendix C.4). For M=14M=14 (DTLZ2), this happened in 58%58\% of all iterations. In contrast, RaMMOBO requires no box decomposition and therefore never falls back to random proposals.

  1. Some of the baselines, e.g. qPOTS (Renganathan and Carlson (2025)) have been shown in their paper to outperform qNEHVI, JESMO, PESMO, MESMO, and even Sobol -- on experiments such as DTLZ2, Vehicle Safety, and Car side-impact. Can the authors provide details of the other baseline implementations for transparency?

We use the qPOTS authors own code [7] and find that their shipped qNEHVI baseline outperforms qPOTS on Branin-Currin (+49.8 vs. +32.8). This contradicts their reported results, where qNEHVI does not improve at all on many objectives [7]. We report this in Section 5, but the revision makes this more explicit. We have no insights how these highly implausible results were reported in the qPOTS paper in the first place.

Moreover, qPOTS [7] does not publish the number of NSGA-II generations. We reproduce the paper's reported results only with 200 NSGA-II generations, while the released default of 10 does not. Hence, we use the former as the comparison method. We have revised Appendix C.4 to make this more explicit.

Furthermore, as noted in Section 5, the published code of BOtied [8] implements a faulty version of the qNEHVI baseline, which uses standardized outputs, but mistakenly uses an unstandardized reference point.

Finally, experimental details of our baselines can be found in Appendix C and in the supplied code.

  1. Why were variants of DTLZ2 alone tested instead of other synthetic functions.

Figure 3 validates our method on multiple additional synthetic functions (Branin-Currin, DTLZ3, DTLZ7). Moreover, as detailed above, we have added additional synthetic experiments with varying MM in the revised Appendix (Figure 7).


[7] Renganathan, A., & Carlson, K. (2025). qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson sampling. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 258, pp. 4051–4059.

[8] Park, J. W., Tagasovska, N., Maser, M., Ra, S., & Cho, K. (2024). BOtied: Multi-objective Bayesian optimization with tied multivariate ranks. In Proceedings of the 41st International Conference on Machine Learning (ICML), PMLR 235, pp. 39813–39833.

Dear Reviewer JASX,

Thank you very much for your help with reviewing for ICLR'27!

The authors have now responded to your reviews. As the discussion period is approaching the end, I'm wondering if you could have a look at the authors' responses and see whether they have addressed your concerns. And could you also leave a comment to let the authors know your thoughts? If any concerns remain, please explain which ones have not been addressed and why.

Warm regards, Your AC

AuthorsOpenReview ↗

Follow-up on Rebuttal and Remaining Concerns

Dear Reviewer JASX,

As the discussion period is coming to a close in approximately 24 hours, we would greatly appreciate your feedback on our rebuttal and the revised manuscript.

We have invested considerable effort in addressing your concerns, including extending our method to constrained optimization, conducting additional experiments on diverse benchmark geometries, and providing further runtime analyses and implementation details.

We believe these additions substantially address the concerns raised in your review. Could you kindly let us know whether you find our responses satisfactory, or whether there are any remaining concerns we could clarify before the discussion period ends?

Thank you for your time and consideration.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.