Pith. sign in

REVIEW 4 major objections 4 minor 28 references

Speeding Up the NSGA-II via Dynamic Population Sizes

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that a dynamic NSGA-II that starts with four solutions and doubles its population every τ evaluations computes the full OneMinMax Pareto front in O(n log n) function evaluations with optimal parameters, a factor Θ(n) faster

desk verdict A genuinely new dynamic-population result for NSGA-II with a plausible O(n log n) OneMinMax theorem, but the empty-interval lemma for the dynamic case is asserted rather than proven, and the metadata abstract overclaims a OneJumpZeroJump result that is absent from the body. read the letter →

arxiv 2509.01739 v3 pith:TS6BO3LZ submitted 2025-09-01 cs.NE

Benjamin Doerr , Martin S. Krejca , Simon Wietheger This is my paper · ORCID
classification cs.NE
keywords dynamicpopulationsizeNSGA-IImulti-objectiveevolutionaryalgorithmruntimeanalysisOneMinMaxParetofrontcurrentcrowdingdistanceparameterless
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Multi-objective optimizers must keep many candidate solutions to store the trade-offs between objectives, but a large static population means most evaluations are wasted. This paper introduces the dynamic NSGA-II (dNSGA-II), which starts with four solutions and doubles its population every τ evaluations up to a bound μ. The authors prove that on the OneMinMax benchmark of size n, an optimal choice of parameters finds the entire Pareto front in O(n log n) function evaluations, both in expectation and with high probability—a factor Θ(n) faster than the proven Θ(n² log n) time of the classic NSGA-II. A second variant with a longer first phase is slightly faster, and a concurrent-run scheme removes the need to choose τ at the cost of only a logarithmic slowdown. The abstract additionally claims an O(n^k log² n) bound on the OneJumpZeroJump benchmark, but the main text does not state or prove a corresponding theorem.

What carries the argument

The load-bearing object is the maximum empty interval (MEI): for a population containing 0ⁿ and 1ⁿ, the largest gap of Pareto-optimal objective values not yet present. The proof tracks MEI through the population-doubling phases. The crucial mechanism, imported from earlier work, states that under the current crowding distance tie-breaker, once the extremes are present each empty interval never grows, and shrinks by at least one with probability at least 1/(2e) per iteration. This lets the analysis show that each phase halves MEI, so after O(log n) phases the remaining gaps are small enough to be filled by direct sampling; the current crowding distance is what makes the small populations spre

What would settle it

Record the maximum empty interval (MEI) each iteration in a run of the (τ,μ)-dNSGA-II on OneMinMax after 0ⁿ and 1ⁿ have both appeared. If MEI ever increases, or if the average number of iterations per phase-shift does not keep MEI below the bound predicted by Lemma 4, then the imported shrinking property fails for dynamic populations and Theorem 2's proof collapses.

Watch

Extended reading notes

Core claim

Central claim (Theorem 2): with μ ≥ 4(n+1) and τ large enough, both dNSGA-II variants cover the OneMinMax Pareto front in O((τ+μ) log n) or O(log(μ)τ + μ log n) evaluations, in expectation and with high probability. Optimal choices give O(n log² n) and O(n log n); the latter is optimal, since even finding one extreme point takes Ω(n log n). This is Θ(n) faster than the classic NSGA-II's proven Θ(n² log n) runtime, with a Θ(n/log n) speed-up already for the fully parameterless version. The gain comes from letting a small population spread before doubling, so each larger phase fills gaps rather than wasting evaluations.

Load-bearing premise

The proof depends on a borrowed claim that once the two extreme solutions are found, a missing stretch of the Pareto front never widens and shrinks by one step with constant probability each iteration; the paper assumes this still holds while the population size is changing, without proving that extension.

Editorial extensions

If this is right

  • For optimal parameters on OneMinMax, dNSGA-II is asymptotically faster than the classic NSGA-II by a factor Θ(n), closing most of the gap to the Ω(n log n) lower bound inherited from single-objective OneMax optimization.
  • Because the high-probability runtime of the (τ,μ)-dNSGA-II is independent of μ once τ is large, users can set the maximum population size to infinity, leaving only the phase length as a parameter.
  • Running powers-of-two phase lengths concurrently removes the τ choice: the parameterless version is only O(log n) slower than the best fixed τ and still outperforms the classic NSGA-II by Θ(n/log n).
  • The proofs require only that each Hamming neighbor of any individual is created with constant probability per iteration, so the results extend to uniform parent selection, one-bit mutation, and crossover with rate bounded below 1, not just standard bit mutation.
  • Any phase length τ up to o(n²) still beats the classic NSGA-II's Θ(n² log n) runtime on OneMinMax, so the choice of τ is not delicate.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof template—small population, fast spread, then phase-wise gap filling—should transfer to any benchmark whose Pareto front is a one-dimensional path that the crowding distance spreads along, e.g., LOTZ; a runtime analysis there would test whether the Θ(n) speed-up is a general phenomenon or specific to OneMinMax.
  • The abstract's OneJumpZeroJump claim, O(n^k log² n) versus the known Θ(n^{k+1}), is not backed by a theorem in the body; if a complete proof appears it would show that dynamic population sizing also helps on multimodal fronts, but until then it should be read as an announcement, not a result.
  • One can also test whether the same phase-doubling schedule improves other MOEAs with static populations, such as SMS-EMOA or MOEA/D; the dNSGA-II's gain comes from population dynamics, not from the NSGA-II-specific non-dominated sorting, so at least part of the argument is portable.
  • Because the optimal O(n log n) is a lower bound for any algorithm using unbiased bit mutations, the only route to further speed-ups on OneMinMax is exploiting operators like crossover or an external archive, not further population-size tuning.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes a dynamic variant of the NSGA-II (dNSGA-II) in which the population starts at size 4 and doubles every τ function evaluations up to a maximum size μ. Two phase-length variants are analyzed, and a concurrent-run scheme is added to remove the τ parameter. The main contribution is a runtime analysis on the OneMinMax benchmark: the authors claim O(n log² n) and O(n log n) expected and high-probability runtimes for the two variants, versus Θ(n² log n) for the static NSGA-II, and a Θ(n) speed-up for an optimal parameter regime. The proof is built on a phase-based empty-interval analysis, using previous results by Zheng and Doerr on the current crowding distance.

Significance. If the main result is fully established, it would be a significant contribution to the theory of MOEAs: it would give the first provable speed-up of the NSGA-II via dynamic population sizes, show that the population-size choice can be partially decoupled from the problem size, and provide a parameterless variant with only an O(log n) overhead. The paper is generally careful with asymptotics, uses standard tail bounds, and is transparent about which statements are imported from prior work. However, the central proof hinges on an unproved extension of a prior lemma to the dynamic population update, and an advertised OneJumpZeroJump result is absent from the body. These issues currently prevent acceptance.

major comments (4)
  1. [Appendix, Lemma 7] Lemma 7 is the load-bearing device for the runtime proof: it supplies the 1/(2e) shrink probability and the floor 2n/(|P_t|-3) used in Lemma 4 and in the phase analysis of Theorem 2. The appendix explicitly says that the lemma 'does not show up exactly' in (Zheng and Doerr 2024a) and is a combination of prior lemmas/proofs, then asserts 'these properties also hold for the dNSGA-II' without proof. This is not obvious, because at phase-final iterations Algorithm 1 (lines 10-12) sets P_{t+1} := P_t ∪ Q_t and doubles N_t, so the update is not a current-crowding-distance selection. The three bullets, especially the shrink probability with the population-dependent floor, must be re-verified for this union step and for the changing N_t. Since Lemma 4 and Theorem 2 depend directly on Lemma 7, the claimed O(n log n)/O(n log² n) runtime is not yet supported.
  2. [Preliminaries, Theorem 1] Theorem 1 is imported from (Zheng and Doerr 2024a, Theorem 16) and asserted to extend to the dNSGA-II because it is 'evident from the proof.' This extension is used in the expectation part of Theorem 2 for the O(n log n) additional iterations after the high-probability event fails, and again in Theorem 5. No proof or precise reduction is given. If the intended scope includes expectation bounds, this is a load-bearing step. Please either provide the extension proof or restructure the expectation argument so that it does not rely on an unproved extension of a static-population theorem.
  3. [Abstract / body discrepancy] The submitted abstract claims: 'For the OneJumpZeroJump benchmark with gap size k, we show a runtime of O(n^k log^2 n), improving upon the known runtime of Θ(n^{k+1}).' The full text contains no theorem, proof, or even a statement of this result; the runtime analysis section is entirely about OneMinMax, and the conclusion lists OJZJ as future work. This claim must be either substantiated or removed from the abstract. It is not needed for the OneMinMax theorem, but as submitted it misrepresents the paper's contributions.
  4. [Proof of Theorem 2] In the proof of Theorem 2, the step bounding Pr[¬E_i ∩ ∩_{j<i} E_j] by the failure probability of a classic NSGA-II with initial population size eN_i is not formally justified. The argument needs the monotonicity fact that for any selected subset S ⊆ P_t ∪ Q_t, MEI(P_t ∪ Q_t) ≤ MEI(S), because adding individuals cannot create empty intervals. This is true, but it is not stated. In addition, Lemma 4's proof uses a fixed threshold based on |P_t|; the extension to populations whose size grows during the T iterations should be made explicit. These are local but necessary steps for the phase analysis to be complete.
minor comments (4)
  1. [Lemma 4] In Lemma 4, the statement writes 'MEI(PT)' where it should presumably be 'MEI(P_t)' based on the surrounding notation; this makes the statement confusing.
  2. [Abstract] The abstract renders 'τ ≥ 256/5 en' as 'τ ≥ 256 50 en'; the missing fraction is a typesetting error that should be corrected.
  3. [Runtime Analysis] The paper states that O(n log n) is optimal because finding 0^n or 1^n requires Ω(n log n) evaluations, citing single-objective lower bounds. A short derivation for the four-individual dNSGA-II would make this claim self-contained.
  4. [Proof of Theorem 5] The expectation argument in Theorem 5 uses a product-form sum Pr[(4/n)^i] for the probability that the first i instances fail. This assumes independence across instances; since the instances are initialized independently, this is likely fixable, but the independence or a union-bound alternative should be stated.

Circularity Check

1 steps flagged · score 2.0 of 10

No circular derivation by construction; the dNSGA-II runtime proof imports prior NSGA-II lemmas and tersely asserts their extension to the dynamic population case, which is an omitted-proof gap rather than an equivalence-to-input.

  1. other [Appendix, Lemma 7 (footnote 2); used in Lemma 4 and Theorem 2]
    "We note that the result itself does not show up exactly in (Zheng and Doerr 2024a) but is a combination of statements from some of the lemmas therein as well as their proofs, noting that these properties also hold for the dNSGA-II."

    This is not a circular reduction: the cited lemmas are independently proven for the classic NSGA-II with current crowding distance. However, the exact Lemma 7 is assembled from those prior lemmas and the extension to the dNSGA-II—where Algorithm 1 lines 10-12 set Pt+1 := Pt ∪ Qt and the population size doubles—is asserted rather than proved. Lemma 4 and the phase argument of Theorem 2 rely on Lemma 7's shrink-with-probability-1/(2e) bound at every iteration, including the doubling final iteration of each phase. The central O(n log n) claim therefore rests on an unproved transfer of a self-cited result. This is a load-bearing self-citation with an omitted proof, not an equivalence by construction.

full rationale

The derivation chain is not circular in the sense of equations reducing to their inputs. Theorem 2 is a new runtime bound proved from Lemmas 3 and 4, which use standard concentration inequalities (Doerr 2020) and the empty-interval shrink property for current-crowding-distance NSGA-II (Zheng and Doerr 2024a). The cited prior work is a published, parameter-free theorem whose assumptions (classic NSGA-II with current crowding distance) do not include the dNSGA-II result, so it is genuine independent evidence for the non-doubling iterations. The main issue is that the appendix assembles Lemma 7 and asserts, without a dedicated proof, that the same properties 'also hold for the dNSGA-II', including the doubling iteration in which Algorithm 1 replaces selection by Pt+1 := Pt ∪ Qt. The phase analysis and Lemma 4 depend on this transfer; that is an omitted-proof / self-citation load-bearing gap, but not a reduction of the theorem to its own assumptions. No parameter is fitted to the target runtime, no quantity is defined in terms of the claimed result, and no known result is merely renamed. The abstract's OneJumpZeroJump O(n^k log^2 n) claim does not appear in the body; this is a missing-support discrepancy, not circularity. Overall, the central O(n log n) speedup has independent algorithmic content, so the circularity score is low; the score of 2 reflects the unproved self-cited extension rather than a constructed equivalence.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central runtime claims depend on two explicit user parameters (mu and tau), on prior current-crowding-distance lemmas from the authors' own group, and on standard concentration inequalities. No hidden fitted parameters or invented entities are introduced. The main risk is the asserted extension of Lemma 7 to the dNSGA-II, which is load-bearing for the OMM proof.

free parameters (2)
  • maximum population size mu = mu >= 4(n+1); can be set to infinity for the (tau,mu)-dNSGA-II
    User-defined cap on population; required to be at least 4(n+1) to represent the full Pareto front. Not fitted to data; the concurrent-run variant removes the need to choose it.
  • phase length tau = Theta(n) for (tau,mu)+, Theta(n log n) for (tau,mu)- in optimal asymptotic choices
    User-defined number of function evaluations between doublings; runtime bounds require tau >= 8 e n ln n, or 520e(n+1) ln n for mu-free bounds. Explicit design parameter, not fitted to data; removed by Algorithm 2.
assumptions (3)
  • domain assumption The empty-interval contraction property (Lemma 7) holds for the dNSGA-II exactly as for the classic NSGA-II with current crowding distance on OneMinMax.
    Stated as extending Zheng and Doerr (2024a, Lemmas 13 and 14) to the dNSGA-II without a proof of the extension; Lemma 4 and Theorem 2 depend on it.
  • standard math Tail bounds for sums of independent geometric and Bernoulli random variables (Doerr 2020, Theorems 8 and 9) apply.
    Used in Lemmas 3, 4, and Theorem 5; standard concentration inequalities.
  • domain assumption The lower bound Omega(n log n) for finding 0^n or 1^n with standard bit mutation and four individuals transfers from single-objective EAs to the dNSGA-II.
    Cited to Droste et al. (2002) and used to declare O(n log n) optimal for OneMinMax; no transfer argument is derived in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Speeding Up the NSGA-II via Dynamic Population Sizes." pith.science (2026). https://pith.science/paper/TS6BO3LZ

@misc{pith2026250901739,
  author       = {Pith},
  title        = {Pith review of: Speeding Up the NSGA-II via Dynamic Population Sizes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TS6BO3LZ}},
  note         = {Machine review of arXiv:2509.01739}
}
abstract

Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) simultaneously, MOEAs are typically run with a large population of solution candidates. This slows down the algorithm and renders the choice of the population size a crucial design decision. In this work, we aim to overcome these difficulties by proposing the dynamic NSGA-II, a variant of the well-known NSGA-II that starts with a small initial population and doubles it after a user-specified number $\tau$ of function evaluations, up to a maximum size of $N_{max}$. We prove that the dynamic NSGA-II with optimal parameters computes the Pareto front of the OneMinMax benchmark of size $n$ with high probability in $O(n \log^2 n)$ function evaluations, which is considerably faster than the $\Theta(n^2 \log n)$ runtime of the static NSGA-II with optimal parameters. For the OneJumpZeroJump benchmark with gap size $k$, we show a runtime of $O(n^k \log^2 n)$, improving upon the known runtime of $\Theta(n^{k+1})$. We also propose a variant that uses the initial population size for a longer period and achieves slightly better performance. Finally, we show that a simple concurrent-run strategy turns our dynamic NSGA-II variants into parameter-less algorithms that exceed the above runtimes only by a logarithmic factor and hence still outperform the static NSGA-II by a factor of $\tilde\Omega(n)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [1]

    Beume, N.; Naujoks, B.; and Emmerich, M. 2007. SMS-EMOA : Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181: 1653--1669

    work page 2007

  2. [2]

    Bian, C.; Ren, S.; Li, M.; and Qian, C. 2024. An archive can bring provable speed-ups in multi-objective evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2024 , 6905--6913. ijcai.org

    work page 2024

  3. [3]

    Bian, C.; Zhou, Y.; Li, M.; and Qian, C. 2023. Stochastic population update can provably be helpful in multi-objective evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2023, 5513--5521. ijcai.org

    work page 2023

  4. [4]

    Coello, C. A. C.; Lamont, G. B.; and van Veldhuizen, D. A. 2007. Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, 2nd edition

    work page 2007

  5. [5]

    Deb, K.; and Jain, H. 2014. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18: 577--601

    work page 2014

  6. [6]

    Deb, K.; Pratap, A.; Agarwal, S.; and Meyarivan, T. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II . IEEE Transactions on Evolutionary Computation, 6: 182--197

    work page 2002

  7. [7]

    Doerr, B. 2020. Probabilistic tools for the analysis of randomized optimization heuristics. In Doerr, B.; and Neumann, F., eds., Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, 1--87. Springer. Also available at https://arxiv.org/abs/1801.06733

    arXiv 2020

  8. [8]

    Doerr, B.; and Doerr, C. 2018. Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm. Algorithmica, 80: 1658--1709

    work page 2018

Show all 28 references
  1. [9]

    Doerr, B.; Ivan, T.; and Krejca, M. S. 2025. Speeding up the NSGA-II with a simple tie-breaking rule. In Conference on Artificial Intelligence, AAAI 2025 , 26964--26972. AAAI Press

    2025

  2. [10]

    S.; and Weeks, N

    Doerr, B.; Krejca, M. S.; and Weeks, N. 2024. Proven runtime guarantees for how the MOEA/D computes the P areto front from the subproblem solutions. In Parallel Problem Solving from Nature, PPSN 2024, Part III , 197--212. Springer

    2024

  3. [11]

    Doerr, B.; and Qu, Z. 2023. From understanding the population dynamics of the NSGA-II to the first proven lower bounds. In Conference on Artificial Intelligence, AAAI 2023 , 12408--12416. AAAI Press

    2023

  4. [12]

    Doerr, B.; and Zheng, W. 2021. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In Conference on Artificial Intelligence, AAAI 2021 , 12293--12301. AAAI Press

    2021

  5. [13]

    Droste, S.; Jansen, T.; and Wegener, I. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276: 51--81

    2002

  6. [14]

    Giel, O.; and Lehre, P. K. 2010. On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation, 18: 335--356

    2010

  7. [15]

    Laumanns, M.; Thiele, L.; and Zitzler, E. 2004. Running time analysis of multiobjective evolutionary algorithms on pseudo- B oolean functions. IEEE Transactions on Evolutionary Computation, 8: 170--182

    2004

  8. [16]

    K.; and Witt, C

    Lehre, P. K.; and Witt, C. 2012. Black-box search by unbiased variation. Algorithmica, 64: 623--642

    2012

  9. [17]

    Li, M.; L \' o pez - Ib \' a \ n ez, M.; and Yao, X. 2024. Multi-Objective Archiving. IEEE Transactions on Evolutionary Computation, 28(3): 696--717

    2024

  10. [18]

    Li, Y.-L.; Zhou, Y.-R.; Zhan, Z.-H.; and Zhang, J. 2016. A primary theoretical study on decomposition-based multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 20: 563--576

    2016

  11. [19]

    Ren, S.; Bian, C.; Li, M.; and Qian, C. 2024. A first running time analysis of the S trength P areto E volutionary A lgorithm 2 (SPEA2) . In Parallel Problem Solving from Nature, PPSN 2024, Part III , 295--312. Springer

    2024

  12. [20]

    Wietheger, S.; and Doerr, B. 2023. A mathematical runtime analysis of the non-dominated sorting genetic algorithm III ( NSGA-III ). In International Joint Conference on Artificial Intelligence, IJCAI 2023 , 5657--5665. ijcai.org

    2023

  13. [21]

    Wietheger, S.; and Doerr, B. 2024. Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms. CoRR, abs/2404.12746

    2024 arXiv

  14. [22]

    Zhang, Q.; and Li, H. 2007. MOEA/D : A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11: 712--731

    2007

  15. [23]

    Zheng, W.; and Doerr, B. 2022. Better Approximation Guarantees for the NSGA-II by Using the Current Crowding Distance. CoRR, abs/2203.02693. Was: ZhengD22arxiv

    2022

  16. [24]

    Zheng, W.; and Doerr, B. 2024 a . Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II). IEEE Transactions on Evolutionary Computation, 1--15. Early access

    2024

  17. [25]

    Zheng, W.; and Doerr, B. 2024 b . Runtime analysis of the SMS-EMOA for many-objective optimization. In Conference on Artificial Intelligence, AAAI 2024 , 20874--20882. AAAI Press

    2024

  18. [26]

    Zheng, W.; Liu, Y.; and Doerr, B. 2022. A first mathematical runtime analysis of the non-dominated sorting genetic algorithm II ( NSGA-II ). In Conference on Artificial Intelligence, AAAI 2022 , 10408--10416. AAAI Press

    2022

  19. [27]

    N.; and Zhang, Q

    Zhou, A.; Qu, B.-Y.; Li, H.; Zhao, S.-Z.; Suganthan, P. N.; and Zhang, Q. 2011. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation, 1: 32--49

    2011

  20. [28]

    Zitzler, E.; Laumanns, M.; and Thiele, L. 2001. SPEA2 : Improving the strength P areto evolutionary algorithm. TIK report, 103

    2001

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.