acceptodds
Under review as a conference paper at ICLR 2027

Initializing Multi-Objective Evolutionary Algorithms with the Optima of Each Objective

Abstract

Multi-objective evolutionary algorithms (MOEAs) are among the most popular approaches to solve multi-objective optimization problems. In this work, we revisit a classic idea in multi-objective optimization, which is surprisingly little used in MOEAs, namely to start the optimization from the optima of the different objectives. The little theoretical previous work studying this idea in MOEAs has shown significant speed-ups for the theory-based GSEMO algorithm, but only together with a strong and non-standard diversity mechanism. In this work, we show that the GSEMO also profits from the initialization with the single-objective optima without additional non-standard mechanisms. We prove that this algorithm optimizes the OneMinMax and COCZ benchmarks in function evaluations, considerably faster than the classic runtime known from previous works. We extend this result to the NSGA-II, the most prominent MOEA in practice. Here this speed-up is obtained as soon as each single-objective optimum is contained once in the typically large initial population. These results constitute the first proof that initializing standard multi-objective evolutionary algorithms with the optima of the objectives can significantly improve their performance.

Primary area:
optimization
Keywords:
multi-objective optimization, NSGA-II, GSEMO, runtime analysis, seeding, speed-up

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_qKLYOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates an initialization strategy for multi-objective evolutionary algorithms (MOEAs) that incorporates the global optima of individual objectives into the initial population. The authors analyze SEMO/GSEMO with uniformly random parent selection, uniform crossover, and mutation, and extend their results to NSGA-II under the configuration specified in the paper. For the two bi-objective benchmark problems, OneMinMax and COCZ, the authors prove that SEMO/GSEMO can cover the entire Pareto front within O(n4/3log⁡4/3n)O(n^{4/3}\log^{4/3}n) function evaluations, both in expectation and with high probability. For NSGA-II satisfying the population-size conditions in Theorem 9, the corresponding bound is O(N4/3log⁡4/3n)O(N^{4/3}\log^{4/3}n).

The key mechanism underlying the proofs is to use mutation to expand existing solutions into contiguous covered segments and crossover to generate new solutions between these segments, progressively reducing the uncovered regions. The paper is primarily validated through mathematical runtime analysis, with its main contributions being new runtime guarantees under specific initialization conditions and insights into the underlying mechanisms.

Critical strengths
  1. Reduced reliance on specialized parent selection mechanisms in previous theoretical results. Prior studies employed both initialization with single-objective optima and strong diversity mechanisms, making it difficult to isolate the contribution of initialization. This paper establishes new runtime guarantees under uniformly random parent selection and demonstrates that the diversity mechanisms used in previous work can themselves substantially affect performance.

  2. An interpretable analytical framework and its extension to NSGA-II. The analysis based on segment growth and gap splitting connects the roles of local mutation, parent selection probabilities, and crossover in generating new solutions. Extending this analysis to NSGA-II, with its fixed population size and crowding-distance-based environmental selection, further strengthens the significance of the results.

Critical weaknesses
  1. The theoretical contributions have a limited scope, and their technical novelty and broader significance relative to existing work are not sufficiently established. The initialization strategy and related proof techniques have been studied in previous work, while the main new contributions of this paper are runtime bounds under specific algorithmic configurations. Moreover, OneMinMax and COCZ are mathematically simple benchmark problems in which the single-objective optima already lie on the Pareto front. More general settings, such as weakly Pareto-optimal solutions and problems with more objectives, are not considered. These two toy problems are insufficient to assess whether the proposed mechanism applies to different problem structures. The paper also does not clearly articulate what transferable theoretical insights it provides.

  2. The current theoretical results provide limited support for the effectiveness of the initialization strategy. First, the runtime analysis assumes that the global optima of individual objectives are already included in the initial population, without accounting for the computational cost of obtaining them in the overall complexity. Although these optima can be constructed directly for OneMinMax and COCZ, finding them may be computationally expensive in general multi-objective optimization problems. Second, the paper demonstrates the benefits of initialization by comparing its new runtime upper bounds with previously established upper bounds. Such a comparison does not rigorously establish that initialization with single-objective optima necessarily yields an asymptotic runtime advantage over random initialization.

  3. I believe this paper is more closely aligned with classical runtime analysis in evolutionary computation than with optimization theory of broad relevance to machine learning. Therefore, I am inclined to consider it a poor fit for ICLR.

Questions for authors

See weaknesses. Besides, the proof of Lemma 17 appears to rely on a condition regarding the distance between the parent solutions that is not explicitly stated, while the parent selection procedure in Lemma 18 may result in offsets exceeding the range permitted by Lemma 17.

5 comments

We thank the reviewer for carefully reading our paper and for their constructive feedback. We believe that we already addressed most of the weaknesses in the first submission, but the presentation can be deepened.

We uploaded a new version of our paper, with changes highlighted in orange.

  1. The theoretical contributions have a limited scope, and their technical novelty and broader significance relative to existing work are not sufficiently established. (1) Limited scope. We discuss in lines 497–500 that what the reviewer perceives as limited scope is a restriction common to essentially all state-of-the-art results in the field, many published at top AI venues. We discuss in lines 496–514 (almost unchanged from before) the general insights we obtain. We address below why this mechanism applies to different problem structures.

    (2) Technical novelty and broader significance relative to existing work. Section 3 addresses exactly this by addressing the limitations of the most relevant related work (Qian et al. (2013)) and explaining how our result is different. We do not think that analyzing established methods is a weakness but rather a strength, as it informs us about the potential of current methods.

  2. The current theoretical results provide limited support for the effectiveness of the initialization strategy. Our results alone are not supposed to show the effectiveness of the initialization strategy. Instead, they provide insights into why such a strategy can be useful. The effectiveness was shown by various empirical works, as we state in lines 57–59 (unchanged from before). Due to comments by other reviewers, we added further references (lines 53–56), which support that the computation of single-objective solutions is usually cheap and beneficial. All these works support the benefit of the proposed initialization strategy, which we believe makes a strong point for our contribution.

    Missing cost of computing the single-objective optima. Since this point was also mentioned by other reviewers, we state the same reply. We agree that finding these optima incurs some additional cost that, in practice, needs to be taken into account. However, this cost is often low, as we mention in lines 50–53. Unfortunately, we did not support this claim with references before, although such support exists, which we added (lines 53–55).

    In the case of the benchmarks that we study (OneMinMax and COCZ), the cost of computing the single-objective optima reduces to the well-known OneMax problem, which is solved by a plethora of evolutionary algorithms within Θ(nlog⁡n)\Theta(n\log n) function evaluations. Doing this twice incurs no asymptotic extra cost for our setting.

    In practice, one needs to stop the search for the single-objective optima after some time, and it remains unclear whether the obtained solutions are actually optimal. Hence, it is more realistic to start with any type of expected solution. Our analysis covers this already insofar as it shows how, given a specific interval, crossover adds new solutions from which the remaining gaps are filled via mutation.

    We highlight these points more clearly at the beginning of Section 4 in lines 328–336.

    Comparing only upper bounds. For NSGA-II, we mention in line 451 (unchanged from before) that the runtime with just random initialization is tight, up to constant factors. Hence, we actually obtain a true speed-up. We added this piece of information also to the introduction (lines 81–84).

    For GSEMO, we agree that no matching lower bound exists. In this case, we only obtain an improved upper bound. We made sure to revise any claims in the paper that are stricter than claiming an improved upper bound.

  3. Poor fit for ICLR. We argue that EAs are commonly used in machine learning pipelines, such as in neural architecture search, hyperparameter optimization, reinforcement learning, and prompt optimization. Thus, we believe EAs are relevant in the broader machine learning field and that our paper fits well into the optimization category given of ICLR 2027. We added such a brief connection to the introduction to more clearly communicated the relevance to the ICLR community (lines 38–41).

  4. Missing condition in Lemma 17 and exceeding the range in Lemma 18. We thank the reviewer for pointing these out. We fixed them, and all our results remain asymptotically as before. While this required mostly smaller changes in Lemmas 17 and 18 and their proofs, we streamlined the proofs to better work with the more specific assumptions. This entailed slight changes in the statements and proofs that made use of Lemmas 17 and 18. Hence, a fair amount of proofs changed but mostly little.

We hope that we could convince the reviewer that our paper makes a significant and relevant contribution to the broader machine learning field. If any doubts are left, we kindly ask the reviewer to state them so that we can address them. Thank you.

Thank you for the detailed response and revisions. I appreciate the improvements to the proofs and the clarification of initialization costs. However, my main concerns remain:

  • The cited tight runtime bound of Θ(Nnlog⁡n)\Theta(Nn\log n) applies to mutation-only NSGA-II, whereas the NSGA-II variant analyzed in this paper uses uniform crossover. Therefore, the comparison does not establish a strict asymptotic speed-up attributable specifically to initialization.

  • The theoretical results remain limited to two highly structured benchmarks with easily obtainable, Pareto-optimal single-objective optima. In more general multi-objective problems, however, single-objective optima may be only weakly Pareto-optimal. Therefore, the generalizability of the proposed mechanism remains unclear, and establishing its effectiveness beyond these favorable settings may require substantial additional theoretical work.

  • I remain concerned about the paper's relevance to ICLR. The newly added examples are rather broad and do not establish a substantive connection between the specific theoretical results and machine learning problems. While I acknowledge that ICLR welcomes optimization theory, this work appears more closely aligned with classical runtime analysis in evolutionary computation and may be a better fit for broader AI or optimization theory venues, such as AAAI or NeurIPS.

Therefore, despite the improvements, I do not find the current contributions sufficiently compelling to change my overall recommendation, and I maintain my rating.

We thank the reviewer for their thoughtful response. Briefly put, we agree with the speed-up discussion, but we do believe that the situation for the other two points is more positive than the current assessment of the reviewer.

  1. Current results do not allow attributing the speed-up specifically to initialization. We agree. In fact, since we discuss in the paper how the interplay of crossover and mutation is crucial, we never meant to give off the impression that this initialization by itself leads to the speed-up. The reply of the reviewer made us realize how our phrasing can be misleading. Hence, we will remove any claims of a speed-up and only speak of improved upper bounds.

  2. Limited theoretical results. Although our formal results only hold for two specific benchmarks (which is common for the state of the art), we would like to highlight our discussion in Section 4. It aims at providing a richer picture of our analysis, which is a consequence of the insights we obtained via our proof. In particular, we address settings, informally, that are more general than those for which we have rigorous guarantees. We believe that such insights are an important part of our contribution, which is why we highlight them here. For a similar reason, we repeat a briefer version of these insights in the conclusion.

    We agree that, generally, single-objective optima may only be weakly Pareto-optimal. However, for finite state spaces, for each objective i∈[1..m]i \in [1 .. m], there is a Pareto-optimal solution attaining the globally optimal value of objective ii. Hence, the situation can potentially be exploited similarly to the discussion we added to Section 4.

    We do not deny that further theoretical work can still provide richer insights, but given that this area has not received any theoretical consideration besides the few cases we discuss in the related work, we believe that our contribution is stronger than the reviewer makes it out to be.

  3. Unclear connection to ICLR. We appreciate this comment, as it was not clear to us before how tight of a fit the reviewer expected. We were under the impression that showcasing that evolutionary optimization is useful in a variety of machine learning contexts may be appealing. In any case, there is also relevant work that highlights a stronger connection between the nature of our results and ICLR. Elsken, Metzen, and Hutter [1] use a multi-objective evolutionary algorithm for neural architecture search. Zhao et al. [2] study efficient Pareto-front optimization, and Sukthanker et al. [3] explicitly identify the high evaluation cost of Pareto-front profiling as a central difficulty in multi-objective neural architecture search. Very recently, Abhyankar et al. [4] use multi-objective evolutionary search for materials discovery. We believe that these works demonstrate a strong connection between multi-objective search and current machine learning applications, oftentimes via evolutionary optimization. We will include these references in an updated version of the paper.

Overall, we hope that these additional points highlight more clearly the merit of our contribution, which we believe is stronger than the reviewer makes it out to be.

[1] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Efficient multi-objective neural architecture search via Lamarckian evolution. In International Conference on Learning Representations, ICLR 2019, 2019.

[2] Yiyang Zhao, Linnan Wang, Kevin Yang, Tianjun Zhang, Tian Guo, and Yuandong Tian. Multi-objective optimization by learning space partitions. In International Conference on Learning Representations, ICLR 2022, 2022.

[3] Rhea Sanjay Sukthanker, Arber Zela, Benedikt Staffler, Samuel Dooley, Josif Grabocka, and Frank Hutter. Multi-objective differentiable neural architecture search. In International Conference on Learning Representations, ICLR 2025, 2025.

[4] Nikhil Abhyankar, Sanchit Kabra, Saaketh Desai, and Chandan Reddy. LLEMA: Evolutionary search with LLMs for multi-objective materials discovery. In International Conference on Learning Representations, ICLR 2026, 2026.

Reviewer_zzhUOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

Runtime analysis of multi-objective evolutionary algorithms traditionally assume that the population is initialised uniformly at random. This paper asks whether it is beneficial to initialise the population at the optima of the individual objectives. Although finding these optima still requires computational effort, it is usually the interaction between objectives that dominate to the complexity of multi-objective optimisation.

The main contribution is to show that GSEMO finds the Pareto front of OneMinMax and CoCZ in expected time O(n^(4/3)log^(4/3) n), which is significantly lower than the best upper bound of O(n^2log n) with uniform intialisation. An analogous difference is found for the more practically employed NSGA-II algorithm. As far as I am aware, there are no lower bounds available for GSEMO on OneMinMax, hence the paper has not proved any speedup.

In overall, this is a significant contribution in theory of evolutionary multi-objective optimisation. I have not had the opportunity to check the proofs in details due to time limitations.

The novelty of the result has some limitations, as acknowedged by the authors. Previous research has already demonstrated that initialising the population at the optima can provably lead to speedup. The authors argue that the previous setting is more artificial than the one considered in this paper.

The results are only shown for two very simple toy problems. The paper would have been more complete if it had demonstrated empirically a clear speedup on a wide range of realistic/interesting multi-objective problems.

Critical strengths

The paper provides a mathematically rigorous and highly non-trivial analysis of the population dynamics in two multi-objective evolutionary algorithms.

Critical weaknesses

The improved runtime is only shown for two simple example functions. Empirical comparison on a broad range of interesting problems would have improved the paper.

Questions for authors

Can you demonstrate empirically a speedup on interesting problems?

3 comments

We thank the reviewer for reading our paper and for their positive assessment. We hope that this highest-confidence review can convince the less confident reviewers to reconsider their score.

In the following, we respond to the reviewer’s question and to the points that are highlighted as shortcomings and weaknesses. Briefly put, we believe that sufficient empirical related work exists so that it is justifiable for us not to include experiments.

We uploaded a new version of our paper, with changes highlighted in orange.

  1. Can you demonstrate empirically a speedup on interesting problems? In lines 57–59 (unchanged from before), we already refer to empirical works that showcase the benefit of this initialization strategy. Moreover, in our responses to other reviewers, we also highlighted other papers that we added to the revised version and that study more specifically the cost incurred by the single-objective optimization (lines 53–55). Many of these papers study established benchmark functions, but various papers also consider combinatorial problems, in particular references in Gong et al. (2025a). Overall, we believe this to be a broad range of sufficiently interesting problems. In the new version, we expanded the overview of previous empirical works in order to highlight this benefit more clearly (lines 53–55).

  2. No speed-up for GSEMO. We agree that currently no matching lower bound for GSEMO exists that would actually allow us to talk about a speed-up. However, for NSGA-II, such a lower bound exists, as we mention in line 451 (unchanged from before). Hence, in this case, we believe it is fair to talk of a speed-up. We mention this bound now also in the introduction (lines 82–84) and pay more attention to when we claim a speed-up and when we only prove an improved upper bound.

  3. No empirical results in the paper. We believe that the empirical papers that we cite and that we added to the revised version, as discussed in Point 1 above, show a general benefit of this initialization strategy. Thus, we believe that there is no need for us to add experiments. We prefer to use the space for the presentation and discussion of our theoretical insights.

We hope that the reviewer agrees that the existing empirical literature is rich enough that we do not have to conduct experiments ourselves. If this is the case, we believe that we cleared all weaknesses that the reviewer mentioned. In any case, we are happy to discuss further points if the reviewer wishes so.

Thank you for your response. I have maintained the scores from the original review.

We thank the reviewer for their reply and for their support.

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

This work starts the multi-objective optimization from the optimums of each objective rather than randomly initialized solutions. The paper is with theoretical analysis without experiments.

Critical strengths

The topic of this manuscript is in the scope. The paper is well written.

Critical weaknesses
  1. The motivation of this work is questionable, facing the "chicken first or egg first" issue, as the time complexity in obtaining the optimums of each objective is not counted. How can it be used in practice?

  2. Of course using the optimums of each objective as the initial solutions can be faster, it is obvious without the need for proofs.

  3. In practice, the suggested idea is inadvisable, as optimizing each objective then optimizing them together must be slower than optimizing the multi-objective optimization problem directly.

Questions for authors

N/A

1 comment

We thank the reviewer for reading our paper. In the following, we address the stated weaknesses, showing that there is substantial empirical evidence that proves some of their points wrong. We hope that this convinces the reviewer that our contribution is useful and strong.

We uploaded a new version of our paper, with changes highlighted in orange.

  • Missing overhead for computing the single-objective optima (Weakness 1.1). This point was also pointed out by Reviewer rrq9, which is why we provide the same reply. We agree that finding these optima incurs some additional cost that, in practice, needs to be taken into account. However, this cost is often low, as we mention in lines 50–53. Unfortunately, we did not support this claim with references before, although such support exists, which we added (lines 53–55).

    In the case of the benchmarks that we study (OneMinMax and COCZ), the cost of computing the single-objective optima reduces to the well-known OneMax problem, which is solved by a plethora of evolutionary algorithms within Θ(nlog⁡n)\Theta(n\log n) function evaluations. Doing this twice incurs no asymptotic extra cost for our setting.

    In practice, one needs to stop the search for the single-objective optima after some time, and it remains unclear whether the obtained solutions are actually optimal. Hence, it is more realistic to start with any type of expected solution. Our analysis covers this already insofar as it shows how, given a specific interval, crossover adds new solutions from which the remaining gaps are filled via mutation.

    We highlight these points more clearly at the beginning of Section 4 in lines 328–336.

  • How can this initialization strategy be used in practice? It is an inadvisible strategy (Weaknesses 1.2 and 3). In order to apply this strategy, one needs to run a single-objective solver for some time, stop it, and then switch to the multi-objective solver. Usually, this switch is done after a fixed budget, such as considered by Friedrich & Wagner (2015) and others (lines 46–50). However, adaptive methods, such as switching after a detected stagnation or too low degree of feasibility, also exist. All of these papers show that using some computation budget for the single-objective solver is usually a beneficial idea for the ultimate multi-objective optimization. Thus, we strongly disagree with the reviewer’s assessment that this strategy is inadvisible. We highlight this point more clearly now in the introduction in lines 46–50.

    In terms of the merit of our work, we clearly prove that the statement that first optimizing the single objective and then optimizing them together can be beneficial in certain scenarios, which directly disproves the reviewer’s claim. In addition, our work provides theoretical insights into why such an improved seeding can result in a far superior runtime. The interplay of crossover and mutation allows to cover regions of the objective space more efficiently than when solely relying on random initial solutions.

  • The message is obvious, so there is no need for proofs (Weakness 2). We hope that the reviewer agrees with us that knowing is better than believing. Moreover, we claim that our results are deeper than simply showing that seeding with single-objective optima is beneficial. First, we show a specific runtime improvement for the most commonly studied theory benchmark in the state of the art of multi-objective evolutionary optimization. We do not think that a runtime improvement by a factor of (Nlog⁡n)2/3(N \log n)^{2/3} is obvious. Second, we argue that our contribution lies not only in the runtime results but also in the insights on the behavior of the algorithms and operators that can be gained from our analysis. In particular, for the behavior of crossover, we show that it is useful without the need for strong diversity mechanisms or specifically-constructed fitness functions. We discuss this merit of the paper in lines 323–328 (unchanged from before) and in lines 506–514 (almost unchanged from before).

We hope that these points clarify the contribution and practical use of our results and that the reviewer will consider increasing their rating. We are happy to clarify any points if the reviewer wishes so.

Reviewer_rrq9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper revisits the idea of initializing MOEAs with the optima of the objectives. It derives improved runtime upper bounds for SEMO, GSEMO, and NSGA-II on OneMinMax and COCZ. The analysis is technical, but the study is limited to two simple benchmarks, and its implications for practical problems are not sufficiently discussed.

Critical strengths

The paper provides improved upper-bound runtime estimates for SEMO, GSEMO, and NSGA-II on OneMinMax and COCZ when initialized with single-objective optima, using uniform parent selection and uniform crossover.

Critical weaknesses
  1. Limited algorithmic novelty and unclear practical value. The initialization strategy and operators are established. Finding the exact optimum of each objective can be expensive in practice, but this cost is excluded from the analysis. Under a limited evaluation budget, obtaining these optima may leave insufficient resources for the subsequent multi-objective search.
  2. Simple benchmarks and unclear practical relevance. The connection between OneMinMax/COCZ and practical optimization problems is not sufficiently explained. The paper provides no analysis or experiments on real-world problems, leaving the broader relevance of the results unclear.
  3. Insufficient evidence for the claimed speed-up. The paper establishes improved upper bounds, but does not provide corresponding lower bounds for the same crossover-based algorithms under random initialization. These comparisons therefore do not directly establish a speed-up due to initialization alone.
  4. Large population requirements and untested smaller populations. The NSGA-II analysis requires preserving every discovered Pareto-front point, which may demand an unaffordable population size in practice. The paper provides no discussion or experiments on smaller populations. Does initialization with single-objective optima still improve performance with smaller populations, where some discovered points may be lost during selection?
Questions for authors

As noted in Weaknesses.

3 comments

We thank the reviewer for reading our paper and for their constructive feedback. We believe that our initial paper already addressed most of the points listed as weaknesses, but we agree that the discussion can be deepened.

We uploaded a new version of our paper, with changes highlighted in orange.

  1. Limited algorithmic novelty and unclear practical value. (1) Limited algorithmic novelty. We believe that understanding established operators more deeply, as we do, is not a weakness but a strong point, as it helps us assess the benefit of current methods.

    (2) Unclear practical value. We agree that finding these optima incurs some additional cost that, in practice, needs to be taken into account. However, this cost is often low, as we mention in lines 50–53. Unfortunately, we did not support this claim with references before, although such support exists, which we added (lines 53–55).

    In the case of the benchmarks that we study (OneMinMax and COCZ), the cost of computing the single-objective optima reduces to the well-known OneMax problem, which is solved by a plethora of evolutionary algorithms within Θ(nlog⁡n)\Theta(n\log n) function evaluations. Doing this twice incurs no asymptotic extra cost for our setting.

    In practice, one needs to stop the search for the single-objective optima after some time, and it remains unclear whether the obtained solutions are actually optimal. Hence, it is more realistic to start with any type of expected solution. Our analysis covers this already insofar as it shows how, given a specific interval, crossover adds new solutions from which the remaining gaps are filled via mutation.

    We highlight these points more clearly at the beginning of Section 4 in lines 328–336.

  2. Simple benchmarks and unclear practical relevance. (1) Simple benchmarks. As we mention in lines 497–498 (unchanged from before), this is a limitation of all state-of-the-art results in this field, many of which are published at top AI conferences.

    (2) Practical relevance. We discuss in lines 505–514 (mostly unchanged from before) the insights that we obtain that can carry over to other problems. In lines 57–58 (unchanged from before), we cite empirical works that show that this initialization strategy is beneficial. Thus, the practical relevance has already been established. Our work provides insights into why this is the case. We now provide more empirical support in lines 52–55.

  3. Insufficient evidence for the claimed speed-up. We mention in line 451 (unchanged from before) that there are asymptotically tight runtime bounds for NSGA-II, which prove that our upper bound is, indeed, a true speed-up. We added this information also when we discuss our contribution (lines 81–84).

    We agree that no such matching lower bound is known for GSEMO. Hence, we updated the paper in order not to give off a wrong impression that we obtain a certain speed-up in this case. However, given that NSGA-II is far more popular than GSEMO, we believe that our speed-up claim for NSGA-II remains relevant.

  4. Large population requirements and untested smaller populations. This is an interesting point that has not seen a lot of theoretical investigation. The main reason is that this entails that the Pareto front can no longer be witnessed at once. Instead, one needs to consider the approximation guarantees of the respective algorithm, which is a different mathematical question. As a consequence, the assumption of a sufficiently large population size for NSGA-II is standard in the theoretical analysis of this algorithm and present in almost all theory papers that consider it.

    One work that considered the approximation qualities of NSGA-II on OneMinMax shows that the gaps between the found Pareto optima on OneMinMax can differ by a constant factor. That is, the optima are not necessarily uniformly spread. In our setting, we expect something similar. The single-objective optima are maintained in NSGA-II, due to how the crowding distance tie-breaker works. For the other solutions, our insights into how crossover generates new, far-off individuals remain, with the only difference that the exact point from which we start may differ slightly. Since solutions that have a larger spread are generally preferred, such solutions are maintained, as long as the population does not contain too many.

    Since this point is a technical discussion, we now mention that our assumption is standard at the beginning of Section 5 (lines 441–443). We added a brief discussion about smaller population sizes to the discussion of the paper (lines 523–528).

We hope that these points clarify the strong contribution of our work and remove the doubts the reviewer may have. If any doubts remain, we kindly ask the reviewer to let us know so that we can provide more information. Thank you.

I appreciate the authors' detailed response. I remain concerned about the initialization cost and the effectiveness with smaller populations. As another reviewer also noted, the practical implications of these results warrant further investigation, especially for the broader ICLR community. I therefore maintain my rating.

We thank the reviewer for their reply. We note that their concerns regarding the initialization cost and the effectiveness for smaller populations remain, although we explicitly addressed both points in our response and incorporated corresponding clarifications into the revised paper. Since the reviewer does not specify which aspects of these concerns remain unresolved, we unfortunately cannot address them more specifically beyond the discussion already provided.

With respect to the practical implications, we would like to emphasize that the primary purpose of this work is not to establish empirically that this initialization strategy can be beneficial, as this has already been observed in a number of empirical works, but to provide theoretical insight into why such improvements can arise. Given the connections of (evolutionary) multi-objective optimization to problems studied in the broader ICLR community, we believe that these mechanistic insights are relevant.

Finally, we acknowledge that our rigorous results concern a limited number of benchmarks and parameter regimes. At the same time, such restrictions are typical of the current state of the art in theoretical analyses of multi-objective evolutionary algorithms. In this context, and given the very limited prior theoretical understanding of initialization in multi-objective evolutionary algorithms, we believe that our results provide a meaningful contribution to the ICLR community.

In any case, we thank the reviewer for taking the time to engage in this discussion with us.

Comments on the paper

2 comments

We thank the reviewers again for their thoughtful comments. However, given that the rebuttal period ends soon, and we have not received many responses, we are wondering if our replies and our updated PDF clarified all doubts that the reviewers may have. If not, we welcome any feedback, and we will try our best to clarify the situation. Thank you.

AuthorsOpenReview ↗

Summary of the Rebuttal

We thank all reviewers for their constructive and insightful feedback and for participating in the discussion with us. As a result of the initial reviews, we improved the paper substantially in order to clarify common concerns. In particular, we extended the discussion of the general merits and insights of our results.

From what we can tell, the reviewers generally acknowledge that the revisions addressed or clarified several of their original concerns. The main point of criticism remaining is that the insights are too limiting in scope and that the broader implications remain unclear. However, this is a point that we explicitly addressed in the new version. On the one hand, we detailed our discussion of the general lessons learned. On the other hand, we provide more references to the empirical literature showing that this strategy is overall beneficial and that multi-objective (evolutionary) optimization is of interest to the ICLR community. Hence, we believe that we already address these issues as far as possible within the scope of the current work. The limitations that remain are shared with much of the theoretical state of the art in this area. Consequently, we are of the impression that our work marks a strong contribution to this area, suitable for ICLR.

Reviewer k5sr was most critical of our work, but in our rebuttal, we pointed out factual inaccuracies in several of the concerns and provided clarifications for other apparent misunderstandings. Unfortunately, the reviewer did not reply during the discussion period, so we cannot judge whether some concerns remain after considering our response and the revised manuscript.

Reviewer zzhU gave the highest confidence and supports our contribution. We believe that this positive assessment is important context, in particular because it provides an independent view that the significance and scope of our results are in line with the standards of the current state of the art in this domain.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.