{"id":"cb6d0412-071b-4e0d-b4a7-299cdf45a913","arxiv_id":"2509.01739","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The dynamic NSGA-II starts with four solutions and periodically doubles its population, provably optimizing OneMinMax in O(n log n) evaluations, a factor Theta(n) faster than static NSGA-II.","lead":"This paper proposes a version of the NSGA-II optimizer that starts with a tiny population and doubles it over time, proving it solves the OneMinMax benchmark in O(n log n) evaluations instead of the usual O(n^2 log n). If correct, this is a provable factor-n speed-up for one of the most studied multi-objective evolutionary algorithms, and a variant removes two user-chosen parameters.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central speedup rests on unproved extension of Lemma 7 to dNSGA-II; Theorem 2 depends on the empty-interval shrink step surviving population doubling.","rationale":"The reader's weakest assumption already identifies Lemma 7 as the unresolved load-bearing point. My stress-test agrees: the main OMM speedup is proven by reducing to a lemma whose dNSGA-II version is asserted rather than proved, with an explicit note that the lemma is a combination of prior results. This warrants a conditional rather than full acceptance, exactly as the reader concluded. The missing OneJumpZeroJump result in the abstract is a separate claims-integrity issue but does not affect the OMM theorem. Since the reader's verdict is already CONDITIONAL, I recommend no change.","tokens_in":16441,"tokens_out":13067,"duration_ms":152164,"concrete_test":"Independently re-derive Lemma 7's third bullet for the dNSGA-II, specifically for the phase-final operation P_{t+1} := P_t ∪ Q_t and for the first selection step after a doubling. Inspect the proofs of Lemmas 13/14 in Zheng and Doerr (2024a) and check each place the selection step uses the fixed population size μ; then verify whether the shrink probability 1/(2e) and the threshold 2n/(|P_t|-3) remain valid when N_t is a power of two and changes across phases. If the proof requires constant μ or a selection step at every iteration, Theorem 2 needs a separate lemma for doubling iterations.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2's phase analysis is built on Lemma 4, which is proved from Lemma 7. The appendix states that Lemma 7 itself 'does not show up exactly' in Zheng and Doerr (2024a) and is a combination of prior lemmas/proofs, then asserts without proof that the same properties hold for the dNSGA-II. This is the load-bearing step: the dNSGA-II's phase-final iteration is not a normal NSGA-II selection step — Algorithm 1 lines 10-12 set P_{t+1} := P_t ∪ Q_t — and the population size changes every phase, so the shrink-with-constant-probability bound and the floor 2n/(|P_t|-3) must be re-verified for variable N_t. If the third bullet of Lemma 7 fails at a doubling boundary, the claimed O(n log n) runtime for the (τ,μ)+-dNSGA-II is unsupported. I am not asserting the lemma is false; I am stating that the proof currently given does not cover the dynamic case. Separately, the metadata abstract claims a OneJumpZeroJump runtime absent from the body, but that is not needed for the OMM theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16715,"tokens_out":15314,"duration_ms":174451,"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":[{"comment":"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.","section":"Appendix, Lemma 7"},{"comment":"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.","section":"Preliminaries, Theorem 1"},{"comment":"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.","section":"Abstract / body discrepancy"},{"comment":"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.","section":"Proof of Theorem 2"}],"minor_comments":[{"comment":"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.","section":"Lemma 4"},{"comment":"The abstract renders 'τ ≥ 256/5 en' as 'τ ≥ 256 50 en'; the missing fraction is a typesetting error that should be corrected.","section":"Abstract"},{"comment":"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.","section":"Runtime Analysis"},{"comment":"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.","section":"Proof of Theorem 5"}],"recommendation":"major_revision","confidential_remarks":"The core OneMinMax result is plausible and the idea is valuable, but the unproved extension of Lemma 7 to the dNSGA-II is the main correctness risk. If the authors can provide a dedicated proof of Lemma 7 for the union/doubling steps, and remove or substantiate the OneJumpZeroJump abstract claim, the paper would likely be acceptable. The OJZJ discrepancy may indicate a leftover from an earlier version; the editor should ask for clarification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2509.01739. The core result is real: letting the NSGA-II grow its population over time on OneMinMax provably cuts the runtime from Theta(n^2 log n) to O(n log n), and the parameterless concurrent-run variant keeps most of the gain. That's a new idea in MOEA theory, and the phase-based proof is mostly careful and readable.\n\nWhat the paper does well: it identifies a genuine inefficiency in static-population MOEAs, proposes a simple mechanism with two variants, and gives a fairly complete runtime analysis for OneMinMax. The concurrent-run trick (Algorithm 2) is a nice touch—it removes the phase-length parameter at only an O(log n) cost, which makes the algorithm practical in a theoretical sense. The authors also correctly note that their proofs only need a constant per-iteration chance of producing a Hamming neighbor, so the results extend beyond standard bit mutation.\n\nThe soft spots are real but not disqualifying. First, Lemma 7—the empty-interval shrink property—is asserted for the dNSGA-II without a dedicated proof. The appendix admits it \"does not show up exactly\" in the prior paper and says it holds for the dynamic case, but the doubling step (lines 10-12 of Algorithm 1) is not a normal NSGA-II selection step, and the lemma's proof cannot simply be imported. This is load-bearing: Theorem 2 rests on it. I'm not saying the lemma is false; the union step probably satisfies the same shrink bound, but the paper needs to show that. Second, the metadata abstract promises a OneJumpZeroJump runtime that doesn't appear in the body; the conclusion lists OJZJ as future work. That should be fixed before publication.\n\nThe optimality bound O(n log n) is cited from single-objective lower bounds rather than derived, but that's standard practice and not a problem here.\n\nWho should read this: anyone working on runtime analysis of MOEAs. The dynamic-population idea will likely transfer to other benchmarks and other algorithms, and the paper gives a clean template. It deserves a serious referee. I'd accept it with a request for a self-contained proof of Lemma 7 for the dNSGA-II and a correction of the abstract.","headline":"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.","tokens_in":17205,"tokens_out":12005,"would_cite":true,"duration_ms":133327,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["dynamic population size","NSGA-II","multi-objective evolutionary algorithm","runtime analysis","OneMinMax","Pareto front","current crowding distance","parameterless algorithm"],"falsifier":"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.","tokens_in":16337,"feed_emoji":"🧬","tokens_out":10287,"duration_ms":108602,"temperature":0.7,"pith_summary":"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.","feed_headline":"Growing its population each phase makes NSGA-II n times faster on OneMinMax","feed_subtitle":"The full Pareto front appears in O(n log n) function evaluations, versus O(n² log n) for the classic algorithm.","key_machinery":"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","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the classic NSGA-II, its non-dominated sorting, and crowding distance selection that the dNSGA-II modifies.","marker":"Deb et al. 2002"},{"why":"Supplies the current crowding distance and the empty-interval lemmas showing that gaps never grow and shrink with constant probability; also provides the large-population O(n log n) bound used in Theorem 1.","marker":"Zheng and Doerr 2024a"},{"why":"Gives the matching Θ(n² log n) lower bound for the classic NSGA-II on OneMinMax, the baseline against which the speed-up is measured.","marker":"Doerr and Qu 2023"},{"why":"Introduces the OneMinMax benchmark, the problem on which all main runtime theorems are proved.","marker":"Giel and Lehre 2010"},{"why":"Provides the Ω(n log n) lower bound for finding the extreme point, used to argue that O(n log n) is optimal.","marker":"Droste, Jansen, and Wegener 2002"},{"why":"Supplies the concentration bound for sums of geometric random variables used in Lemma 3 and Lemma 7's probability estimates.","marker":"Doerr 2020"},{"why":"Contains the full proofs of the current-crowding-distance properties that Lemma 7 imports.","marker":"Zheng and Doerr 2022"}],"fun_headline_variants":["Dynamic population sizes make NSGA-II Θ(n) faster on OneMinMax","Start small, double later: NSGA-II achieves O(n log n) on OneMinMax","Growing population each phase speeds NSGA-II by factor n","Parameterless NSGA-II outruns classic by Θ(n) on OneMinMax","Doubling population size slashes NSGA-II runtime on OneMinMax"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic population sizes make NSGA-II Θ(n) faster on OneMinMax","Start small, double later: NSGA-II achieves O(n log n) on OneMinMax","Growing population each phase speeds NSGA-II by factor n","Parameterless NSGA-II outruns classic by Θ(n) on OneMinMax","Doubling population size slashes NSGA-II runtime on OneMinMax"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001411,"raw_usage":{"total_tokens":5584,"prompt_tokens":841,"completion_tokens":4743,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":4641}},"tokens_in":585,"tokens_out":4743,"duration_ms":40511,"temperature":1.0,"reasoning_tokens":4641,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:15:07.686140+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the classic NSGA-II, its non-dominated sorting, and crowding distance selection that the dNSGA-II modifies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the matching Θ(n² log n) lower bound for the classic NSGA-II on OneMinMax, the baseline against which the speed-up is measured."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the OneMinMax benchmark, the problem on which all main runtime theorems are proved."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Ω(n log n) lower bound for finding the extreme point, used to argue that O(n log n) is optimal."}],"review_version":1}