- 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 function evaluations, both in expectation and with high probability. For NSGA-II satisfying the population-size conditions in Theorem 9, the corresponding bound is .
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
-
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.
-
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
-
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.
-
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.
-
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
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 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.
-
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.
-
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 , there is a Pareto-optimal solution attaining the globally optimal value of objective . 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.
-
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.
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.
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.
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 Θ(nlogn) 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.
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).
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.