acceptodds
Under review as a conference paper at ICLR 2027

To Reevaluate or Not: A Theoretical Study of NSGA-II Under Noise

Abstract

Multi-objective evolutionary algorithms (MOEAs) are widely used to optimize problems with multiple objectives. In real-world applications, however, solution evaluations may be corrupted by noise, for example, when using a simulator. A straightforward response is to reevaluate solutions. This raises a key question: is it more beneficial to reevaluate solutions in every generation, or retain their initial noisy fitness values throughout the search? We investigate this question theoretically for NSGA-II, one of the most widely used MOEAs. On the common benchmark LOTZ under one-bit prior noise, we show that under noise levels of and , retaining initial fitness values yields polynomial expected runtime, whereas reevaluation requires superpolynomial expected runtime, with all other algorithm settings unchanged. The proven detrimental effect of reevaluation echoes known results for simple MOEAs. Further, we construct a new benchmark PairedCOCZ and prove that for noise levels below but sufficiently close to one, reevaluation is helpful: it leads to polynomial expected runtime, compared with at least exponential expected runtime without reevaluation. These results not only provide theoretical comparison of evaluation strategies for practical MOEAs under noise for the first time, but also challenge the prevailing belief that reevaluation is always detrimental. We complement the theory with empirical studies.

Primary area:
optimization
Keywords:
NSGA-II, Re-evaluation, Evaluation Strategy

Reviews

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

This paper studies a specific design choice in noisy multi-objective evolutionary optimization: whether NSGA-II should retain individuals’ initial fitness evaluations or reevaluate them in every generation. On LOTZ, reevaluation can increase the expected runtime from polynomial to superpolynomial. On the newly constructed PairedCOCZ benchmark, reevaluation instead provides a substantial advantage when the noise probability equals or is sufficiently close to one. Experiments further illustrate the mechanisms underlying these contrasting results.

Critical strengths

The problem is clearly formulated, and the theoretical results support the main conclusions under explicitly stated assumptions.

The paper demonstrates that a small change in the fitness evaluation policy can substantially improve noise robustness, producing large runtime advantages while leaving other algorithmic components unchanged.

Critical weaknesses

This is a typical theoretical paper that analyzes a specific mechanism on constructed, abstract problems and provides experimental support for its conclusions. If I were to identify areas for improvement, I would highlight the following three points:

  1. I would appreciate more discussion of the motivation behind PairedCOCZ, particularly whether its construction captures features of real-world optimization problems.
  2. The theoretical bounds are relatively loose, leaving a substantial gap between the proven guarantees and the experimental settings. However, this is not unusual in theoretical runtime analysis, and I do not consider it a major concern.
  3. I would like to see experiments on more realistic problems beyond toy benchmarks such as LOTZ, LeadingOnes, and OneMax (in single objective optimisation), or at least on classical optimization problems with practical relevance. Such experiments would help establish whether the mechanisms identified in the theoretical analysis translate into practical benefits.
Questions for authors

This is a question for discussion rather than a weakness of the paper. Could the authors discuss the connection between reevaluation and non-elitist population replacement? Although NSGA-II remains structurally elitist, reevaluation prevents a previously favorable noisy evaluation from conferring a permanent survival advantage. Fully replacing parents with freshly evaluated offspring could potentially break the same mechanism of persistent overestimation. Existing single-objective analyses show that non-elitist EAs can handle noise efficiently with appropriately chosen mutation rates and population parameters, and that parameter control mechanisms can further improve noise tolerance in certain settings. These results motivate asking whether non-elitist replacement could provide a complementary approach to noisy multi-objective optimization. A key challenge would be maintaining representatives of the entire Pareto front. Could suitable mutation-rate control, together with appropriate population sizing and diversity preservation, address this challenge while preventing incorrect fitness evaluations from persisting indefinitely?

4 comments

Response to Reviewer Gy8x (1/3)

We sincerely thank you for your time, insightful comments and helpful suggestions, as well as the recognition of our work. Your encouraging remarks are much appreciated. Please find below our detailed responses to your comments and the revision made accordingly. All changes are marked in blue in the uploaded PDF.

Motivation of PairedCOCZ. Thank you for this question. Following it, we revised the paper to make the motivation stronger. We added a sentence in Section 4 and a new Appendix A.2, and we added a classical combinatorial problem that has the same property as PairedCOCZ, together with a new experiment. We explain both points here.

PairedCOCZ is not a model of one application. It focuses on one property that practical problems can have: optima that are sensitive to small changes. Every one-bit neighbour of an optimum is worse than every optimum in both objectives. Under prior noise, an optimum is therefore never evaluated better than it is, and it is evaluated worse whenever the evaluation is corrupted. Such optima are the non-robust optima of robust optimization (Jin and Branke 2005). They occur, for example, when the best designs lie at the boundary of the feasible region and violations are penalized, so that a slightly changed copy of the design pays the penalty; in PairedCOCZ the penalty r+1r+1 per defect has this role. In addition, a changed copy of a slightly worse solution can be optimal, so a non-optimal solution can receive a value that is too good, and without reevaluation it keeps this value.

The example that we added is the bi-objective minimum spanning tree problem in the penalized formulation of Neumann (2007), in which edge sets that are not spanning trees are penalized. This problem has the property that motivated PairedCOCZ. A spanning tree has a fixed number of edges, so flipping any single bit of a spanning tree gives an edge set that is not a spanning tree and is penalized. A corrupted evaluation therefore always makes an optimal spanning tree look worse, as it does for the optima of PairedCOCZ. Our new experiments on this problem, which we describe in the answer to your third point below, show the same behaviour as on PairedCOCZ.

In addition, following a comment of Reviewer eZxp, we added a new result on the noise levels of Theorem 4 (Lemma 54 in Appendix H.3). Theorem 4 is stated only for the maximal noise level p=1p=1 and for noise levels that are exponentially close to it, 0<1−p≤2−2n0 < 1-p\le 2^{-2n}. The new lemma shows that, for constant rr and every p<1p < 1, the expected runtime without reevaluation on PairedCOCZ is polynomial in nn, μ\mu and 1/(1−p)1/(1-p). So reevaluation can be faster by more than a polynomial factor only if pp is extremely close to 1. A restriction of Theorem 4 to such noise levels is therefore necessary, and it is not a weakness of our proof.

Loose bounds. Thank you for pointing this out; we agree. The constants are larger than needed because they come from union bounds over long runs. Closing the gaps between the proved noise ranges on LOTZ is listed as future work.

Response to Reviewer Gy8x (2/3)

Experiments on more realistic problems. Thank you for this suggestion. We agree, and following it we added such an experiment to the revision (last paragraph of Section 5, Figure 1(d) and Appendix I.6). We ran NSGA-II with both strategies, under the same noise model, on the bi-objective minimum spanning tree problem described above. The setting is as follows. The main experiment uses 1000 random instances on the complete graph with 8 vertices (28 edges) and the population size μ=100\mu=100; the appendix also reports 6 and 7 vertices. For every noise level and each strategy, NSGA-II is run once on each instance, which gives 1000 runs. Both strategies get the same number of fitness evaluations: every run has a budget of 2,000,100 evaluations, which are 20,000 generations without reevaluation and 10,000 generations with reevaluation, because reevaluation uses twice as many evaluations per generation. We count the runs whose population covers the Pareto front within this budget, that is, contains, for every vector of the Pareto front, a spanning tree with this weight vector.

The results are consistent with our theoretical findings and with the experiments on PairedCOCZ: when the noise is not too high, no reevaluation is better, and when the noise is very high, reevaluation is better.

  • Moderate noise. At p=0.5p=0.5, all 1000 runs without reevaluation cover the Pareto front, but only 27.6% of the runs with reevaluation. Reevaluation is harmful here, as we proved on LOTZ.
  • High noise. The order changes between p=0.9p=0.9 and p=0.99p=0.99, as on PairedCOCZ. Without reevaluation, 96.0% of the runs cover the front at p=0.9p=0.9, 4.9% at p=0.99p=0.99 and none at p=1p=1; with reevaluation, these are 16.9%, 16.8% and 16.8%. At p=1p=1, every run without reevaluation ends in a population that stores only values of spanning trees and contains no spanning tree. Such a population never accepts a spanning tree, which is the situation of Theorem 4(b). Reevaluation is helpful here, as we proved on PairedCOCZ.

Response to Reviewer Gy8x (3/3)

Reevaluation and non-elitist replacement. Thank you for this insightful comment. We added Appendix A.3 for discussion. Our view is as follows.

  • Both mechanisms limit the time during which one lucky noisy evaluation helps an individual. With reevaluation, the individual may stay, but its value is replaced in the next generation. With non-elitist replacement, the value stays with the individual, but the individual is removed.
  • However, non-elitist replacement may not have the same effect as reevaluation. On PairedCOCZ at p=1p=1, replacing all parents by the offspring would remove the absorbing populations of Theorem 4(b), because their members would not survive. This alone does not give a runtime bound. With reevaluation, an optimum can stay in the population and only its value is renewed. With full replacement, no optimum survives as an individual, so the classes of the front must be created again in every generation. Our lower bound for reevaluation on LOTZ shows where noise adds a difficulty. Its key lemma uses only that many Pareto-optimal solutions have at most two copies and that all copies of a solution can receive dominated values in the same generation. Neither fact depends on elitism. A non-elitist NSGA-II would therefore need more copies of every Pareto-optimal solution, for example through a larger population.
  • For single-objective optimization, non-elitist evolutionary algorithms with a suitable mutation rate and selective pressure are efficient under noise (Dang and Lehre 2015; Lehre and Qin 2024), and self-adaptation of the mutation rate can increase the noise level that the algorithm can handle (Lehre and Qin 2023). In the multi-objective case the algorithm must also keep representatives of the whole front, as you point out. On LOTZ, each Pareto-optimal solution is the only solution with its fitness vector and would have to be created again in every generation. Whether mutation-rate control, together with a suitable population size and a mechanism that keeps the population diverse, can achieve this under noise is, in our view, an interesting open question.

Thanks to your suggestions, we have revised the paper to add non-elitist survival selection as a direction for future work (Section 6).

Thank you again for your encouraging and helpful review. We would be glad to answer any further questions.

References

  • Duc-Cuong Dang and Per Kristian Lehre. Efficient Optimisation of Noisy Fitness Functions with Population-based Evolutionary Algorithms. In Proceedings of the 13th Workshop on Foundations of Genetic Algorithms (FOGA'15), pp. 62–68, Aberystwyth, UK, 2015.
  • Yaochu Jin and Jürgen Branke. Evolutionary Optimization in Uncertain Environments—A Survey. IEEE Transactions on Evolutionary Computation, 9(3):303–317, 2005.
  • Per Kristian Lehre and Xiaoyu Qin. Self-Adaptation Can Improve the Noise-Tolerance of Evolutionary Algorithms. In Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA'23), pp. 105–116, Potsdam, Germany, 2023.
  • Per Kristian Lehre and Xiaoyu Qin. More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments. Algorithmica, 86(2):396–441, 2024.
  • Frank Neumann. Expected Runtimes of a Simple Evolutionary Algorithm for the Multi-Objective Minimum Spanning Tree Problem. European Journal of Operational Research, 181(3):1620–1629, 2007.

Dear Reviewer Gy8x,

Thank you again for your helpful suggestions. Following them, we have carefully revised the paper point by point, and your suggestions have helped us a lot to improve our work.

Finally, we would like to thank you sincerely for your encouraging review. It means a lot to us.

Best regards,

The Authors

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

This paper presents a rigorous theoretical runtime analysis of NSGA-II under one-bit prior noise, comparing two different evaluation strategies when dealing with noise: reevaluating individuals at every generation, and retaining their creation-time fitness values when the offspring is created. By investigating the NSGA-II on the classic LOTZ benchmark and a newly introduced PairedCOCZ benchmark, the authors demonstrate that NSGA-II is able to optimize this benchmark when using both noise models. Specifically, reevaluation can cause useful solutions to be lost (leading to superpolynomial runtimes), whereas retaining incorrect fitness values can trap the population in apparent optimal Pareto-optimal points and hence, excludes true optima on PairedCOCZ. The reason is, that the Pareto optima of PairedCOCZ are never evaluated correctly. Note that reevaluation can restore Pareto optimal search points in polynomial runtime. The theoretical claims are well-supported by both mathematical proofs and empirical experiments.

Critical strengths

The message of the paper is very clear, and the research question is of high interest, especially given the rising number of similar papers emerging in recent years. The topic is motivated appropriately, and the contributions are clearly stated. Furthermore, the benchmarks are formally introduced in a correct way, and the description of the underlying algorithm is solid. I also appreciate the overall structure of the paper, which places the full theorems and proofs in the appendix while providing helpful proof sketches in the main text. I commend the authors for the depth and effort put into this work, and I believe all the stated results are more or less correct.

Critical weaknesses

Recommendation: "Weak reject"

While the manuscript has significant potential and tackles a compelling research question in noisy multi-objective optimization, it currently requires a comprehensive revision before it is ready for publication. In particular, the motivation, positioning against related work, algorithmic setup, and proof intuitions need substantial clarification to ensure accessibility to a broad ICLR audience. I have outlined the seven most critical areas of concern below, along with detailed questions to help the authors strengthen the manuscript. Note that there are many many more!

-> Introduction and Background: The introduction currently lacks sufficient background information. The authors should better articulate why this paper is specifically suitable for ICLR, clearly explain the underlying noise model, and provide an intuitive overview of how reevaluation operates alongside the role of the noise parameter pp. Please clarify the key differences between this work and the study by Antipov and Doerr (2025)—beyond the obvious shift to the multi-objective LOTZ problem. Also provide a more intuitive description of the newly introduced PairedCOCZ problem. Additionally, the introduction mentions a bound on pp, whereas subsequent statements refer specifically to p=1p=1. Please clarify what happens when p=1p=1 and define precisely what is meant by an "infinite expected runtime" in this context.

-> Preliminaries: It is recommended to explicitly state the core objective of multi-objective optimization early on—specifically, whether the goal is to find a Pareto-optimal set or to cover the entire Pareto front. Also, please anchor the noise model more firmly in existing literature and justify why a more realistic model was not chosen. Furthermore, the mathematical formulation of the noise model lacks precision: Is a subset I⊆{1,…,n}I \subseteq \{1, \ldots, n\} drawn uniformly, or a single element? Further, the text discusses "reevaluation on 2μ2\mu individuals" before NSGA-II has even been formally defined. Please reorder or cross-reference these definitions appropriately.

-> NSGA-II Algorithm: Why is the population size lower bound of μ=2n+2\mu = 2n+2 sufficient? Is it strictly because the analysis works out, and what happens if μ\mu is smaller? The algorithm description requires more formal rigor. Please formally introduce standard bit mutation, explain the choice of one-point crossover, formally define the crowding distance, and clarify what is meant by the phrasing "parents come before offspring." Finally, what are the theoretical bounds on the runtime of such an algorithm?

-> Can the authors parameterize μ\mu and state the valid range of μ\mu for which Theorem 1 holds, especially given that we are operating in a black-box scenario? Please distinguish between the time required to reach the Pareto front versus the time needed to cover it. Where does the factor 2n2n originate? Furthermore, the potential loss of front points requires much clearer explanation. For instance, an individual like 1110111000000000 could be evaluated incorrectly, potentially causing a true Pareto point like 1111111000000000 to be lost from the front due to having a crowding distance of zero. Please clarify how this is mitigated In total, make the proof accessible to a broader readership by splitting it in small sublemmas. (Note: Intuition suggests that neither crossover nor strict conditions on the noise probability are strictly necessary, as incorrectly evaluated individuals can typically be repaired).

-> Theorem 2: The noise probability constraint appears overly restrictive, raising questions regarding the novelty of the result. The underlying arguments mirror classical runtime analyses: in O(n2)O(n^2) evaluations, the Pareto front is covered under noise-free conditions, after which the process is simply repeated. What parent selection mechanism is deployed here? For standard binary tournament selection, the expected bound is typically O(n3)O(n^3). Is this stochastic tournament selection or a power-law ranking scheme? Please clarify.

-> The proof structure for Theorem 3 (and subsequent theorems) would benefit greatly from a more systematic breakdown—particularly since it establishes a negative result, which requires rigorous substeps. Currently, multiple assertions appear consecutively without sufficient justification. Please structure the proofs step-by-step using intermediate sub-lemmas that clearly state why each claim holds.

-> There appears to be a precision issue in the formal definition: it reads as though the values c11(x)c_{11}(x) and c00(x)c_{00}(x) are defined solely with respect to the first bit string of length rr. Please clarify and correct this formulation.

-> Theorem 4: Why is Θ(log⁡n)\Theta(\log n) a sufficient population size here? This scaling appears inconsistent when considering large values where r=ω(log⁡n)r = \omega(\log n). Where does the noise probability explicitly manifest in the theorem? Moreover, it remains unclear how the preservation of Pareto-optimal solutions within the population is mathematically guaranteed—please provide a more explicit argument.

Questions for authors

There are plenty of points which require classification. I stated many of them already above!

10 comments

Response to Reviewer McGp (1/8)

We sincerely thank you for the time you spent on our paper and for the detailed and constructive report. Your comments showed us many places where the submission was unclear or incomplete, and we have revised the paper on every point. All changes are marked in blue in the uploaded PDF. The main text is now ten pages long, and longer explanations are collected in a new Appendix A. Below we answer your comments in the order of the review.

1. Introduction and background

Thank you for these comments on the introduction. We agree that the submitted introduction assumed too much background, and we have rewritten the parts listed below.

Suitability for ICLR. MOEAs such as NSGA-II are used for multi-objective problems in machine learning. One example is neural architecture search (Lu et al., GECCO 2019; Elsken et al., ICLR 2019), where a candidate is assessed by a noisy training run. Every such method has to decide whether a candidate that is kept also keeps its first noisy value or is evaluated again. Our paper gives the first proven comparison of the two options for NSGA-II. The introduction now mentions this use.

Noise model, reevaluation and the role of pp. We are sorry that the submission used these terms before explaining them. The introduction now defines the model first. Each evaluation returns, independently with probability pp, the fitness of the solution with one uniformly random bit flipped; the solution itself is not changed. So p=0p=0 means no noise, and at p=1p=1 every evaluation is corrupted. With reevaluation, a wrong value affects only one selection step, but every surviving solution meets new noise in each generation. Without reevaluation, a solution meets noise once, but a wrong value stays with it as long as it survives.

Difference from Antipov and Doerr (2025). This is a very interesting paper, and we are glad to compare our work with it more carefully. We first describe what they do, since the submission mentioned it only briefly. Antipov and Doerr studied single-objective optimization. Their algorithm is the (1+1) EA, which keeps a single solution, and their benchmark is LeadingOnes. The noise is prior noise, as in our paper: one-bit noise with rate qq, where one uniformly random bit is flipped before the evaluation with probability qq, or bit-wise noise, where every bit is flipped independently with probability q/nq/n. Without reevaluation, the algorithm stores the noisy fitness of its current solution, evaluates each offspring once, and accepts the offspring if its noisy fitness is at least the stored one. They proved that this algorithm finds the optimum in O(n2)O(n^2) expected iterations at constant noise rates, for example for every constant q<1q < 1 under one-bit noise with one-bit mutation. They compared this with the same algorithm with reevaluation, which was known to have polynomial expected runtime on LeadingOnes only for noise rates up to order log⁡n/n2\log n/n^2. In their setting, no reevaluation is therefore much better.

Our work differs from theirs in the problem, in the conclusion and in the proofs.

Differences in the problem and conclusion.

  • They look for one optimum with one solution. We study a multi-objective problem, where NSGA-II must hold all the Pareto-optimal solutions in its population at the same time.
  • Their comparison has one direction: no reevaluation is better. We show both directions for NSGA-II. No reevaluation is better on LOTZ (Theorems 1 and 3), and reevaluation is better on PairedCOCZ at and near the maximal noise level (Theorem 4).
  • Their bound without reevaluation covers constant noise rates. Ours only covers p=O(1/log⁡n)p=O(1/\log n). Whether NSGA-II can handle constant noise levels, as the (1+1) EA can, is open.

Response to Reviewer McGp (2/8)

1. Introduction and background (continued)

Differences in the proofs.

  • Their proof follows one stored value. This value can be correct, too low or too high, and for one-bit noise they showed with a Markov chain on these three states that the algorithm quickly returns to a correct stored value. In NSGA-II each of the 2n+22n+2 individuals has its own stored value, and a wrong stored value causes a problem that does not exist for a single solution. Consider a non-optimal individual whose stored value lies on the Pareto front. In the survival selection it competes with the true Pareto-optimal solution that has the same value, and it can take the place of this solution. The front value is then still stored in the population, but the Pareto-optimal solution itself is lost. The main part of the proof of Theorem 1 controls this for all n+1n+1 front values at the same time. This is where the crowding distance, the order of equal-valued individuals and crossover enter the proof.
  • For the (1+1) EA with reevaluation, they could use the known bound of Sudholt (2021). For NSGA-II no such bound was known. The population holds several copies of a solution, so it is not clear in advance that new noise still removes Pareto-optimal solutions. Theorem 3 proves that it does: near coverage, many solutions have at most two copies, and all copies of such a solution receive dominated values in the same generation often enough.
  • In their setting, a stored value that is too high is repaired quickly. On PairedCOCZ at p=1p=1 this is not possible. The stored front values of non-optimal individuals dominate every value that an optimum can receive, so no optimum survives (Theorem 4(b)). The proof that reevaluation is efficient there (Theorem 4(a)) is new as well.

Intuitive description of PairedCOCZ. Following your comment, we added an intuitive description to the second contribution, and the new Appendix A.2 explains the idea behind the function. We describe both here.

The first 2r2r bits form rr pairs, where rr is a constant. The first objective counts the pairs 1111, and the second objective counts the pairs 0000. A pair 0101 or 1010 and a zero among the other n−2rn-2r bits are called defects, and both objectives are reduced by r+1r+1 for every defect. The function has the following features.

  • The objectives conflict only in the pairs: changing a pair from 0000 to 1111 improves the first objective and makes the second worse. On the other bits the objectives agree. This follows the benchmark COCZ (Laumanns et al. 2004), in which the objectives agree on one half of the bits and conflict on the other half.
  • The Pareto-optimal solutions are the solutions without defects. There are 2r2^r of them, and the Pareto front has r+1r+1 vectors.
  • Every one-bit neighbour of an optimum has one defect and is worse than every optimum in both objectives. Under one-bit noise an optimum is therefore never evaluated better than it is, and every corrupted evaluation makes it look worse.
  • In the other direction, a solution with one defect is one bit away from an optimum, so a corrupted evaluation can give it the fitness of an optimum. Without reevaluation it keeps this value, which is too good.

PairedCOCZ is a constructed function and not a model of one application, like LOTZ, OneMinMax and COCZ. The property it focuses on does occur in practice: optima that lose their quality under a small change of the solution. In robust optimization these are called non-robust optima (Jin and Branke 2005). A typical case is a problem whose constraints are handled by penalties and whose best solutions lie at the boundary of the feasible region, so that a slightly changed copy of such a solution is infeasible and pays the penalty. A classical example is the bi-objective minimum spanning tree problem in the penalized formulation of Neumann (2007), where no one-bit neighbour of a spanning tree is a spanning tree. In our new experiments on this problem (last paragraph of Section 5, Figure 1(d) and Appendix I.6), the two strategies behave at high noise as on PairedCOCZ: for p≥0.99p\ge 0.99, more runs cover the Pareto front with reevaluation than without it when both strategies get the same number of fitness evaluations, and at p=1p=1 every run without reevaluation ends in a population that stores only values of spanning trees and contains no spanning tree. Appendix G.1 contains worked examples of PairedCOCZ.

Response to Reviewer McGp (3/8)

1. Introduction and background (continued)

Bound on pp versus p=1p=1; infinite expected runtime. Thank you for pointing out this being confusing. The two results are about different noise ranges, and the introduction now says so. The LOTZ comparison holds for pp up to order 1/log⁡n1/\log n. The PairedCOCZ comparison holds at the maximal noise level p=1p=1 and at noise levels that are exponentially close to it, that is, for p=1−qp=1-q with 0<q≤2−2n0 < q\le 2^{-2n}. At p=1p=1, every evaluation returns the fitness of a uniformly random Hamming neighbour of the solution. The runtime TT is the first generation in which the population covers the front, and T=∞T=\infty if this never happens (Section 2.3). At p=1p=1 without reevaluation, the population reaches, with positive probability, a state in which all individuals are non-optimal and store front values. These stored values strictly dominate every value that an optimum can receive, so no optimum survives from then on. Hence P[T=∞]>0P[T=\infty] > 0 and E[T]=∞E[T]=\infty (Theorem 4(b)).

2. Preliminaries

Thank you for the careful reading of this section. Your comments helped us to make the definitions precise.

Goal. Section 2.1 now states the goal at the start. The goal is to cover the Pareto front: for every vector of the front, the population must contain a solution with this true fitness. The whole Pareto set is not required. On LOTZ the two are the same; on PairedCOCZ there are 2r2^r optima and r+1r+1 front vectors.

Noise model. Thank you for this question, which we are happy to discuss. One-bit prior noise was first studied by Droste (2004) and is a standard model in runtime analyses under noise (Gießen and Kötzing 2016; Sudholt 2021). We chose it because it is the model of the SEMO analysis of Dinot et al. (2023), which our LOTZ result extends, so that the bounds can be compared directly. We agree with you that a more realistic model is desirable. The natural next step is bit-wise noise, in which every bit is flipped independently, and we plan to study NSGA-II under this model in future work; the conclusion now states it. We would like to explain why this extension is not straightforward. Our proofs use the one-bit structure: an individual that stores a front value differs from the matching optimum in at most one bit (Lemma 5). Under bit-wise noise several bits can be flipped in one evaluation, so this no longer holds, and the proofs do not apply directly. Section 2.2 now gives the references, and Appendix A.1 discusses the choice of the model.

Precision. Thank you for noticing this. II is a single index drawn uniformly at random from the nn bit positions, not a subset. The text now says so.

Order of the definitions. We agree that the order was confusing. Section 2.2 now contains only the noise model. The two evaluation strategies are defined in Section 2.3, after the algorithm, with a reference to line 13 of Algorithm 1.

Reviewer_eZxpOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper theoretically studies whether NSGA-II under one-bit prior noise benefits from reevaluating individuals each generation or retaining their creation-time fitness values. On LOTZ, it establishes a noise regime in which retaining fitness yields polynomial expected runtime, whereas reevaluation requires superpolynomial expected runtime. Conversely, on the newly constructed PairedCOCZ benchmark, reevaluation achieves polynomial expected runtime at or sufficiently near maximal noise, while retaining fitness leads to infinite or at least exponential expected runtime. Within each comparison, the other algorithm settings remain unchanged. The paper provides detailed proofs and complementary experiments with 1,000 runs per setting and strategy, including comparisons under equal fitness-evaluation budgets.

Critical strengths

The contrasting runtime separations provide a substantive theoretical contribution. The paper establishes that either evaluation policy can be substantially worse, depending on the problem structure. Extending this comparison to NSGA-II requires accounting for population multiplicities, crowding distance, tournament selection, and crossover. The resulting separations clarify why conclusions drawn from simpler evolutionary algorithms do not settle the choice of evaluation policy for NSGA-II.

Critical weaknesses

1.The separation favoring reevaluation is established under highly restrictive conditions. PairedCOCZ is specifically constructed to create persistent fitness overestimates, has a constant-size Pareto front, and yields the exponential-versus-polynomial comparison only for some condition, alongside the infinite-runtime result at another case. Moreover, the exponential lower bound can follow from a rare trapping event and does not establish exponential runtime for typical runs. Although this is a valid counterexample to universally preferring retained fitness, it provides limited guidance about when reevaluation helps under less extreme noise. 2.The robustness of the conclusions to algorithmic choices remains insufficiently established. The analysis specifies stable objective sorting with parents before offspring, and the LOTZ separation uses exactly. The experiments do not test alternative ordering rules or larger LOTZ populations, and none of the PairedCOCZ settings satisfies the explicit proof’s population conditions. Consequently, the empirical results illustrate the proposed mechanisms but leave unresolved how strongly the conclusions depend on these implementation and parameter choices.

Questions for authors

The details are shown in the critical weaknesses.

8 comments

Response to Reviewer eZxp (1/5)

We sincerely thank you for reviewing our paper. We are grateful for your assessment that the two separations are a meaningful contribution, and we take both weaknesses seriously. Both are about the scope of the results. Thanks to your comments, the revision (changes in blue) now states the scope more precisely. Below please find our responses.

W1. The separation in favor of reevaluation holds under restrictive conditions.

Thank you for this point. We agree with you that PairedCOCZ is an artificial function, which we constructed as a counterexample, and the paper says so clearly. We would like to explain why we think it is a meaningful result, how it is related to practical problems, and what we have added for less extreme noise.

Why the counterexample matters. For noisy multi-objective evolutionary algorithms, theoretical work on this question is still rare. To our knowledge, the choice between the two strategies has been analysed only once before, by Dinot et al. (IJCAI 2023) for SEMO on OneMinMax. That work and our own LOTZ result for NSGA-II (Theorems 1 to 3) both show that reevaluation does not help and can be harmful. The single-objective analysis of Antipov and Doerr (IJCAI 2025) reaches the same conclusion. From these results alone, one could conclude that reevaluation should be avoided in general. Theorem 4 is, as far as we know, the first proof that this conclusion is not correct: there are problems on which reevaluation is needed. In runtime analysis, a constructed function is the usual tool for a statement of this kind.

Relation to practical problems. PairedCOCZ is built around one property that practical problems can have. Its optima are sensitive to small changes: flipping any single bit of an optimum gives a solution that is worse than every optimum in both objectives. In the other direction, a solution that is one bit away from an optimum is evaluated as this optimum when the noise flips the right bit. So noise can only make an optimum look worse, but it can make a slightly worse solution look optimal, and without reevaluation this solution keeps its wrong value. In robust optimization, optima of this kind are called non-robust optima (Jin and Branke 2005). They are typical for problems whose constraints are handled by penalties and whose best solutions lie at the boundary of the feasible region: a slightly changed copy of such a solution is infeasible and pays the penalty. A classical example is the bi-objective minimum spanning tree problem in the penalized formulation of Neumann (2007). A spanning tree has a fixed number of edges, so no one-bit neighbour of a spanning tree is a spanning tree, and every such neighbour is penalized. To show that PairedCOCZ reflects this feature of real problems, the revision now includes this problem and a new experiment on it (last paragraph of Section 5, Figure 1(d) and Appendix I.6). In this experiment the two strategies behave as on PairedCOCZ; the last item of the list below gives the setting and the numbers. The new Appendix A.2 explains this motivation.

Response to Reviewer eZxp (2/5)

W1 (continued)

Less extreme noise. Following your comment, we extended the analysis to all noise levels below one (new Lemma 54 in Appendix H.3). Without reevaluation, at noise level p=1−qp=1-q with 0<q≤10 < q\le 1, the expected runtime on PairedCOCZ is at most 4μ4n3/q+μ4⌈M/2⌉(4n2r+1/q)M4\mu^4n^3/q+\mu^{4\lceil M/2\rceil}(4n^{2r+1}/q)^M. For constant rr this is polynomial in nn, μ\mu and 1/q1/q. So for less extreme noise, for example for every constant p<1p < 1 and also for p=1−n−cp=1-n^{-c} with a constant c>0c > 0, no reevaluation is efficient on PairedCOCZ as well, and reevaluation can be faster by at most a polynomial factor. The proof is short. The smallest number of defects among the stored values never increases and decreases with probability at least q/(4μ4n2)q/(4\mu^4n^2) per generation. Once an individual with a stored front value exists, one generation creates correctly evaluated optima of all classes as its last offspring with probability polynomial in 1/n1/n and qq, and these offspring survive.

What this means for the noise condition of Theorem 4. The new lemma and Theorem 4 fit together as follows.

  • If 1−p1-p is not extremely small, say 1−p≥n−c1-p\ge n^{-c} for a constant c>0c > 0, then no reevaluation has polynomial expected runtime by Lemma 54. For such noise levels, reevaluation can be faster by at most a polynomial factor.
  • Reevaluation can therefore be faster by more than a polynomial factor only if 1−p1-p is smaller than every inverse polynomial (i.e., pp is extremely close to 1).
  • Theorem 4 shows that for such noise levels this large advantage really exists. It covers two cases. In the first case, the noise level is maximal, p=1p=1: the expected runtime is polynomial with reevaluation and infinite without it. In the second case, the noise level is exponentially close to one, 0<1−p≤2−2n0 < 1-p\le 2^{-2n}: the expected runtime is polynomial with reevaluation and at least 2n−o(n)2^{n-o(n)} without it.

So the extreme noise level in Theorem 4 is not a weakness of our proof. On PairedCOCZ, reevaluation can have a superpolynomial advantage only when pp is extremely close to 1, and Theorem 4 proves this advantage there. For less extreme noise our results point in one direction: no reevaluation is the better choice, as the experiments below show.

Response to Reviewer eZxp (3/5)

W1 (continued)

Three further facts may be useful for your assessment.

  • The upper bound for reevaluation is not restricted to exponentially small 1−p1-p. With q=1−pq=1-p, the polynomial bound holds for all 0≤q≤c/(n2μ4M−6)0\le q\le c/(n^2\mu^{4M-6}) with a small constant c>0c > 0, that is, also for inverse-polynomial qq when μ=Θ(log⁡n)\mu=\Theta(\log n) (Theorem 12 and the last paragraph of Section 4). Only the exponential lower bound for no reevaluation needs 0<q≤2−2n0 < q\le 2^{-2n}.
  • The experiments on PairedCOCZ agree with the theory. For every setting and each strategy we made 1000 independent runs, and we count the runs that cover the Pareto front within the budget, that is, whose population contains a true optimum for every front value. At p=1p=1 (with n=128n=128 and n=256n=256, μ=18\mu=18 and a budget of 10n210n^2 generations), all 1000 runs with reevaluation covered the front, as Theorem 4(a) predicts, and none of the 1000 runs without reevaluation did. Theorem 4(b) rests on the following event: the population reaches a state in which every individual is non-optimal but stores a front value. From then on no true optimum can enter the population, so the front is never covered. Our proof gives only a small lower bound on the probability of this event, but in the experiments it happened in every run without reevaluation (Figure 1(c)). For noise levels below one, we use n=40n=40 and μ=32\mu=32 and give both strategies the same budget of 32,032 fitness evaluations per run, which are 1000 generations without reevaluation and 500 generations with reevaluation. At p=0.5p=0.5, 94.3% of the runs without reevaluation and 53.8% of the runs with reevaluation covered the front within this budget; at p=0.9p=0.9, these are 75.8% and 48.8%. For higher noise the order changes: at p=0.99p=0.99, 5.8% of the runs without reevaluation and 45.8% of the runs with reevaluation covered the front; at p=0.999p=0.999, 5.8% and 47.4% (Figure 1(b) and Table 12). By Lemma 54, the advantage of reevaluation at p=0.99p=0.99 and p=0.999p=0.999 is at most a polynomial factor in the expected runtime.
  • The same change of order appears on a combinatorial problem. The revision adds experiments on the bi-objective minimum spanning tree problem in the penalized formulation of Neumann (2007) (last paragraph of Section 5, Figure 1(d) and Appendix I.6). As explained above, no one-bit neighbour of a spanning tree is a spanning tree, which is the property that PairedCOCZ focuses on. The setting is as follows. We use 1000 random instances on the complete graph with 8 vertices (28 edges) and the population size μ=100\mu=100. For every noise level and each strategy, NSGA-II is run once on each instance, which gives 1000 runs. Every run has a budget of 2,000,100 fitness evaluations; these are 20,000 generations without reevaluation and 10,000 generations with reevaluation. A run is successful if its population covers the Pareto front within this budget, that is, if it contains, for every vector of the Pareto front, a spanning tree with this weight vector. We record the number of successful runs. At p=0.5p=0.5, all runs without reevaluation and 27.6% of the runs with reevaluation are successful; at p=0.9p=0.9, these are 96.0% and 16.9%. For higher noise the order changes: at p=0.99p=0.99, 4.9% of the runs without reevaluation and 16.8% of the runs with reevaluation are successful, and at p=1p=1, none of the runs without reevaluation and 16.8% of the runs with reevaluation. At p=1p=1, every run without reevaluation ends in a population that stores only values of spanning trees and contains no spanning tree, which is the situation of Theorem 4(b). These results suggest that the effect is not limited to the constructed function.

We also agree with you that the exponential lower bound for p<1p < 1 comes from a rare event and does not show that typical runs are slow. Section 4 says this explicitly: the bound "does not imply that most runs take exponential time". Thank you for pointing this out.

Comments on the paper

1 comment

Dear Area Chairs and Reviewers,

We sincerely thank you all for the time you spent on reviewing our paper and for the many constructive comments. We have revised the paper point by point according to them, and the comments have helped us a lot to improve the paper. For your convenience, we summarize the main changes here. All changes are marked in blue in the uploaded PDF.

Theoretical analysis

  • Following the comment of Reviewer eZxp, we added a runtime analysis of NSGA-II without reevaluation on PairedCOCZ under less extreme noise and derived an upper bound on the expected runtime (Lemma 54 in Appendix H.3, and the last paragraph of Section 4).
  • Following the comments of Reviewers McGp and eZxp, we added a remark on the role of the population size in the proof of Theorem 1 (Remark 1 in Appendix D).

Experiments

  • Following the comments of Reviewers Gy8x and eZxp, we added experiments on a classical combinatorial problem, the bi-objective minimum spanning tree problem (last paragraph of Section 5, Figure 1(d) and Appendix I.6).
  • Following the suggestions of Reviewer eZxp, we added experiments with other orders of equal-valued individuals and with larger population sizes (Appendix I.5).

Discussion

  • Following the comments of Reviewers McGp, eZxp and Gy8x, we added a discussion of the motivation of PairedCOCZ and of its relation to practical problems (Sections 1 and 4, and Appendix A.2).
  • Following the question of Reviewer Gy8x, we added a discussion of the relation between reevaluation and non-elitist survival selection (Appendix A.3), and we added non-elitist survival selection to the directions for future work (Section 6).
  • Following the comments of Reviewer McGp, we added a discussion of the noise model, of the components of the algorithm and of the conditions of the theorems (Appendix A.1). We also extended the comparison with the work of Antipov and Doerr (Section 1), and we added bit-wise noise to the directions for future work (Section 6).

Clarifications

  • Following the comments of Reviewer McGp, we revised the introduction to explain the relevance to machine learning, the noise model, the two evaluation strategies and the noise ranges of our two results (Section 1).
  • Following the comments of Reviewer McGp, we revised the preliminaries: we added the goal of the optimization, references for the noise model, formal definitions of all components of NSGA-II, the reason for the population size μ=2n+2\mu=2n+2, and the known runtime bounds (Section 2).
  • Following the comments of Reviewer McGp, we divided the proof sketches of Theorems 1 to 4 into steps that name the lemmas of the appendix (Sections 3 and 4), and we revised the definition of PairedCOCZ and the statement of Theorem 4 (Section 4).

For the details, please see our replies to each reviewer.

Thank you again for your time and effort.

Sincerely,

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.