{"id":"127ba3e3-e1bd-4556-ae7b-1bc2f255ad09","arxiv_id":"1908.08686","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Fitness-proportionate selection needs a low mutation rate or exponential fitness scaling to optimize linear functions in polynomial time; with standard mutation it is exponentially slow.","lead":"An evolutionary algorithm that picks parents in proportion to their fitness is exponentially slow on every linear optimization problem when the mutation rate is the standard one, and this holds even for polynomial-sized populations. Lowering the mutation rate or exponentially scaling fitness makes the same algorithm provably efficient, and the proofs extend to Royal Road functions and may inform directed evolution models.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Positive results are proven only for integer weights; abstract overclaims 'polynomially bounded weights' for arbitrary real weights, leaving the polynomial-time claim unsupported for real-valued linear functions.","rationale":"The reader's weakest assumption correctly identifies that the positive results require integer weights while the abstract claims 'polynomially bounded weights'. This is the most load-bearing concern because the positive results are a central part of the paper's contribution: they purport to show polynomial expected runtime for all linear functions with moderate weights under low mutation or exponential scaling. If the weights may be arbitrary real numbers, the gap used in the (M3) verification can vanish, so the level-based argument does not go through; the polynomial bound is not established. The issue is not merely a missing reference or a cosmetic assumption; it changes the scope of the main positive theorem. The negative result (Theorem 4) is independent of integrality, and its proof using Lemma 1 and the negative drift theorem appears sound, apart from a minor mismatch in the probability exponent for part (i) when delta > 1 (the proof gives lambda e^{-Omega(n)} rather than lambda e^{-Omega(n^delta)}), which does not affect the qualitative conclusion of exponential runtime. The paper is otherwise rigorous, with parameter-free derivations and established proof techniques. A conditional acceptance with a required revision of the abstract and conclusions to state 'integer weights' (or an extension to real weights) would address the concern. This matches the reader's conditional verdict.","tokens_in":16121,"tokens_out":11245,"duration_ms":105439,"concrete_test":"Check the (M3) verification in the proof of Theorem 5 for the linear function f(x) = x_1 + (1 + 2^{-n}) x_2 + x_3 + ... + x_n. Construct a population in which the top ceil(gamma lambda) individuals have fitness f_gamma and all remaining individuals have fitness f_gamma - 2^{-n}. Compute the selection probability beta(gamma, P) and compare beta(gamma, P) * p_0 with gamma (1 + c/(4 n a_1)) using the parameters of Theorem 5. If the inequality fails for large n, the proof does not extend to arbitrary real weights, confirming the integer-weight restriction is load-bearing.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's positive upper bounds (Theorems 5, 6, 7, 8) are stated under the assumption, made at the start of Section 4, that all weights a_j are integer. The proofs of these theorems verify condition (M3) of the level-based theorem by bounding the selection probability using the fact that any fitness value strictly below a threshold f_gamma is at most f_gamma - 1. This integer gap is essential: it guarantees that the ratio beta(gamma, P) is strictly larger than gamma by a factor depending on f^*. For arbitrary real weights with polynomially bounded magnitude, the gap between distinct fitness values can be exponentially small (e.g., weights 1 and 1 + 2^{-n}), in which case the same argument only yields beta(gamma, P) >= gamma(1 + o(1)), and the required (1+delta) margin in (M3) with delta = c/(4 n a_1) can fail. Consequently, the polynomial expected runtime bounds do not follow for real-valued weights, and the abstract's phrase 'any linear function with polynomially bounded weights' overstates the proven result. The negative result (Theorem 4) and the lower-bound analysis do not depend on integrality and appear sound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the runtime of a non-elitist evolutionary algorithm with fitness-proportionate selection (Algorithm 1) on the class of linear pseudo-Boolean functions. Its main negative result (Theorem 4) states that for any linear function with positive weights, bitwise mutation rate χ/n for any constant χ > ln 2, and population size λ ≥ n^{2+δ} with λ polynomial, the probability of finding the optimum within e^{c n} generations is at most λ e^{-Ω(n^δ)}; a companion inapproximability bound (Corollary 1) is also derived. The positive results show that polynomial expected runtime can be recovered if the mutation rate is lowered to χ/n = (1-c)/(n^2 a_1) with sufficiently large λ (Theorems 5 and 6), or if the fitness is exponentially scaled, i.e., e^{(χ+ε)f(x)} or c·Linear(x) with c > e^χ (Theorem 7), and these bounds are extended to additively decomposed functions including Royal Road (Theorem 8). The proofs use the level-based analysis method (Theorems 1 and 2) and the negative drift theorem for populations (Theorem 3).","tokens_in":74,"tokens_out":22304,"duration_ms":300445,"significance":"If the results hold, they substantially extend the existing runtime theory of fitness-proportionate selection from the single benchmark function OneMax to the whole class of linear functions, a central class in evolutionary computation theory. The negative result is strong because it applies to all linear functions, covers the standard mutation regime χ = Θ(1), and is accompanied by an explicit inapproximability statement. The positive results identify two parameter regimes in which fitness-proportionate selection becomes efficient, and they are derived by verifying conditions of established theorems rather than introducing ad-hoc assumptions. The paper also makes a credible connection to biological applications such as SELEX and directed evolution. However, the positive results are proven only under an integer-weight assumption that is omitted from the abstract and from the theorem statements, and at least one proof of an improved runtime bound contains a concrete error; these issues need to be addressed before the claims as stated can be accepted.","major_comments":[{"comment":"The positive upper bounds are proven only under the blanket assumption stated at the start of Section 4 that all weights a_j are integer, but the abstract claims polynomial expected runtime for 'any linear function with polynomially bounded weights' without this restriction. In the proof of Theorem 5, the lower bound on β(γ,P) relies on the fact that any individual with fitness below the threshold f_γ has fitness at most f_γ − 1; for arbitrary real weights of polynomial magnitude, the gap can be exponentially small (e.g., weights 1 and 1 + 2^{-n}), so the required margin in condition (M3) with δ = c/(4 n a_1) does not follow. The same integrality assumption is used in the proof of Theorem 7 in the appendix, where it is stated that f(x) takes only integer values in case of integer weights a_j. The statements of Theorems 5–8 and the abstract should explicitly restrict to integer weights, or the proofs must be extended to real weights.","section":"Section 4 (Theorems 5–8) and Abstract"},{"comment":"The proof of Theorem 6 verifies condition (M4') but then concludes 'By Theorem 1', which requires (M4) rather than (M4'); the correct theorem is Theorem 2. Moreover, substituting δ = c/(4 n a_1), γ0 = c/4, and s_j = (1−c)/(e n^2 a_1) into Theorem 2's bound E[T] = O(m λ log(γ0 λ)/δ + (1/δ) Σ 1/(γ0 s_j)) yields a second term of order n^4 a_1^2/(c^2(1−c)), not the claimed n^3 a_1^2. The claimed bound O(n^2 a_1 λ log(na_1) + n^3 a_1^2) is therefore not justified by the given derivation; the proof must be corrected or the bound revised.","section":"Theorem 6 (proof and statement)"}],"minor_comments":[{"comment":"Part (i) is established only by saying 'analogously to Corollary 1 from [24]'; please provide a self-contained derivation or a precise statement of the corollary, since this is a central claim.","section":"Theorem 4, proof of part (i)"},{"comment":"The explicit runtime bound in the theorem statement and the proof's final expression are inconsistent: the proof writes E[T] ≤ 27 n^2 a_1^2/c^2 (n λ ln(3δλ/2) + 4e n^2 a_1/(c(1−c))) while the theorem states 27 n^3 a_1^2/c^2 (λ ln(3δλ/2) + 4e n^2 a_1/(c(1−c))). The constants also do not match the 128 that would follow from 8/δ^2. Please reconcile these expressions.","section":"Theorem 5, proof"},{"comment":"The symbol ψ is reused for an upper bound on ln(α)/χ, whereas in Theorem 3 it denotes ln(α)/χ + δ; please rename one of them to avoid confusion.","section":"Theorem 4, proof"},{"comment":"Reference [5] contains an empty author field ('Dang, D.C., , Jansen, T.'); please fix the citation.","section":"References"},{"comment":"The assumption λ = poly(n) from Theorem 3 is satisfied by the λ = n^k in the abstract, but this is not stated in the theorem; a short remark would improve readability.","section":"Theorem 4 and Corollary 1"}],"recommendation":"major_revision","confidential_remarks":"The integer-weight restriction on the positive results is, in my view, the most important issue: it materially narrows the abstract's claims and is easy for readers to miss because the blanket assumption is buried at the start of Section 4. The proof of Theorem 6 also appears to contain a concrete algebraic error in the runtime bound that should be fixed or corrected before publication. The negative result and the overall proof framework are solid and should be preserved. I recommend major revision rather than rejection because the core results are likely salvageable with the stated corrections."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Dang, Eremeev, and Lehre. The paper does something real: it shows that with standard mutation rates and polynomial population sizes, fitness-proportionate selection needs exponential time on every linear function (Theorem 4). That negative result is the main event, and it's clean. The positive results—polynomial time under mutation rate Θ(1/n²) and under exponential fitness scaling—are also genuinely new, and they extend to additively decomposed functions like Royal Road.\n\nThe proofs are built on the level-based method and the negative drift theorem for populations. I went through the main arguments and they're solid. Theorem 4's proof uses a concentration lemma to keep the average fitness above half the optimum, then bounds the reproductive rate and applies negative drift. The positive results verify conditions (M1)–(M4) carefully. Theorem 6's proof is only sketched, but it's the same machinery as Theorem 5, so that's not a real concern.\n\nThe soft spot is the integer-weights assumption. Section 4 starts with 'Throughout the section, we suppose that all weights a_j are integer.' The abstract and introduction, however, say the upper bounds hold for 'any linear function with polynomially bounded weights.' The proof of condition (M3) uses the fact that any fitness value strictly below f_γ is at most f_γ − 1. With real weights, that gap can be exponentially small, and the required (1+δ) margin can fail. So as written, the polynomial-time claims are established only for integer weights. This is a genuine mismatch between the statements and the proofs. It's not fatal—OneMax and all integer-weight linear functions are covered—but the advertised generality is wider than what is proven.\n\nThe negative result does not depend on integrality, and it alone is a good contribution. The citation pattern is appropriate; the authors build on their own earlier work (level-based analysis, negative drift) and on Doerr–Kötzing, and there's no circularity.\n\nMy recommendation: send it to peer review. The integer-weights issue should be fixed, either by restricting the abstract or by extending the proof (for rational weights, scaling to integers would likely work). A referee should check that. The paper deserves a serious referee.","headline":"A significant runtime analysis for fitness-proportionate selection on linear functions, with a clean negative result and useful positive results; the main caveat is that the positive results are proven only for integer weights, while the abstract claims more.","tokens_in":16870,"tokens_out":3314,"would_cite":true,"duration_ms":31749,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","68T20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Fitness-proportionate selection is exponentially slow on linear functions with standard mutation rates; lowering the mutation rate or exponentiating the fitness restores polynomial expected time.","keywords":["fitness-proportionate selection","roulette-wheel selection","evolutionary algorithm","runtime analysis","linear functions","negative drift theorem","level-based analysis","exponential fitness scaling"],"falsifier":"Run the algorithm with fitness-proportionate selection, mutation rate $(1-c)/(n a_1)$, and a linear function with non-integer polynomially bounded weights such as $a_j = 1 + 1/(2j)$; if the expected runtime stays polynomial, the integer-gap argument is not essential, and if it becomes exponential, the integer restriction is confirmed as load-bearing.","tokens_in":15904,"feed_emoji":"⏱️","tokens_out":4553,"duration_ms":42308,"temperature":0.7,"pith_summary":"This paper analyzes roulette-wheel (fitness-proportionate) selection, one of the oldest genetic-algorithm mechanisms, on the broad class of linear fitness functions over bit strings. It proves that with the standard per-bit mutation rate $\\Theta(1/n)$ and population size $n^k$ for any constant $k>2$, every linear function with positive weights requires exponential time to optimize, with overwhelmingly high probability. It then shows the mechanism can be rescued: lowering the mutation rate to $\\Theta(1/n^2)$ with a sufficiently large population gives polynomial expected runtime on linear functions with polynomially bounded integer weights, and exponentiating the fitness to $e^{(\\chi+\\varepsilon)f(x)}$ gives $O(n\\lambda\\ln\\lambda+n^2)$ expected time even at standard mutation rates. Together, these results draw a sharp boundary between efficient and inefficient settings for a selection rule that remains important in both evolutionary computation and models of directed evolution.","feed_headline":"Roulette-wheel selection is exponentially slow on linear functions","feed_subtitle":"Standard mutation forces e^{cn} generations; lowering the mutation rate or scaling fitness restores polynomial time.","key_machinery":"The argument runs on two complementary population-level drift tools. The lower bound uses the negative drift theorem for populations, which bounds the expected reproductive rate of individuals: at standard mutation rates, fitness-proportionate selection keeps the reproductive rate below $e^\\chi$, so the population cannot climb the fitness landscape toward the optimum. The upper bounds use the level-based analysis theorem applied to a partition of the search space into levels defined by prefix sums of the weights; the low mutation rate makes the probability of improving one level sufficiently large, and integrality of the weights gives a quantitative gap in selection probability for better individuals. Fitness scaling $e^{(\\chi+\\varepsilon)f(x)}$ amplifies the probability of selecting better individuals to a constant, which restores efficiency even at standard mutation rates.","core_discovery":"The central negative claim is Theorem 4: for any constant $\\chi>\\ln 2$, population size $\\lambda\\ge n^{2+\\delta}$, and any linear function with positive weights, the algorithm with fitness-proportionate selection and bitwise mutation rate $\\chi/n$ finds the optimum within $e^{c n}$ generations with probability at most $\\lambda e^{-\\Omega(n^\\delta)}$. That is, with standard mutation rates, optimizing any linear function requires exponential time with overwhelmingly high probability. The companion positive claims (Theorems 5-7) show that the same algorithm becomes efficient under two rescues: reducing the mutation rate to $\\chi/n=(1-c)/(n a_1)$ with population size polynomial in $n a_1$ yields polynomial expected runtime for integer weights, and applying the scaling $c^{f(x)}$ with $c>e^{\\chi}$ yields $O(n\\lambda\\ln\\lambda+n^2)$ expected runtime for any linear function and any $\\varepsilon>0$. These bounds extend to separable additively decomposed functions such as Royal Road functions.","pith_inferences":["Editorial inference: The integer-weights restriction on the positive theorems suggests the polynomial bounds may fail for real-valued weights; a testable hypothesis is that the true threshold for polynomial time depends on the minimum fitness gap between distinct levels, not just on the magnitude of the weights.","Editorial inference: The negative result at $\\chi>\\ln 2$ and the positive scaled-fitness result at any $\\chi>0$ with $c>e^\\chi$ imply a phase transition in selective pressure; one could search for the critical curve in the $(\\chi,c)$ parameter space where expected runtime jumps from polynomial to exponential.","Editorial inference: The connection to SELEX and directed evolution suggests that in vitro evolution with concentration-proportional amplification may operate in the exponential-scaling regime, so its efficiency may hinge on whether binding affinities effectively act as integer-valued weights."],"forward_implications":["Standard-mutation fitness-proportionate EAs are not merely slow on OneMax: they fail on every linear function, so the negative result is fully general for this class.","The inapproximability corollary shows that with weights differing by a factor of at most $r$, no solution within a concrete approximation factor is found within exponential time.","Reducing the mutation rate to $\\Theta(1/n^2)$ with a large population restores polynomial expected runtime for any linear function with polynomially bounded integer weights.","Exponential fitness scaling $e^{(\\chi+\\varepsilon)f(x)}$ with population size $\\lambda=\\Omega(\\ln n)$ gives $O(n\\lambda\\ln\\lambda+n^2)$ expected time for any linear function and any $\\varepsilon>0$.","The same positive results extend to separable additively decomposed fitness functions such as Royal Road functions with constant block length."],"supporting_citations":[{"why":"Supplies the negative drift theorem for populations used to prove the exponential lower bound.","marker":"[24]"},{"why":"Establishes the fitness-level analysis for non-elitist populations and the OneMax lower bound that this paper extends.","marker":"[25]"},{"why":"Provides the level-based theorem (Theorem 1) and the low-mutation OneMax result generalized here.","marker":"[6]"},{"why":"Provides the multiplicative up-drift theorem used as Theorem 2 for improved upper bounds.","marker":"[10]"},{"why":"Origin of the level-based analysis framework and the corollary that Theorem 1 tailors.","marker":"[3]"},{"why":"Earlier negative result on OneMax and the exponential-scaling idea that Theorem 7 generalizes.","marker":"[30]"},{"why":"Baseline $\\Theta(n\\log n)$ runtime for the (1+1) EA on linear functions, contrasted with population-based results.","marker":"[13]"},{"why":"Tight bounds for the (1+1) EA on linear functions, providing context for the population-based analysis.","marker":"[39]"}],"fun_headline_variants":["Fitness-proportionate selection on linear functions: exponential unless mutation rate low","Roulette-wheel selection: exponential time on linear functions","Low mutation rate makes fitness-proportionate selection fast on linear functions","Scaled fitness makes fitness-proportionate selection polynomial on linear functions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The polynomial upper bounds require all weights $a_j$ to be integers, because the proof needs a fitness gap of at least 1 between distinct levels; for arbitrary real weights that gap can vanish and the stated polynomial bounds are not proven.","fun_headline_variants_meta":{"raw":{"variants":["Fitness-proportionate selection on linear functions: exponential unless mutation rate low","Roulette-wheel selection: exponential time on linear functions","Low mutation rate makes fitness-proportionate selection fast on linear functions","Scaled fitness makes fitness-proportionate selection polynomial on linear functions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.003439,"raw_usage":{"total_tokens":12978,"prompt_tokens":1014,"completion_tokens":11964,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":11889}},"tokens_in":630,"tokens_out":11964,"duration_ms":85280,"temperature":1.0,"reasoning_tokens":11889,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:34:01.033381+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm with fitness-proportionate selection, mutation rate $(1-c)/(n a_1)$, and a linear function with non-integer polynomially bounded weights such as $a_j = 1 + 1/(2j)$; if the expected runtime stays polynomial, the integer-gap argument is not essential, and if it becomes exponential, the integer restriction is confirmed as load-bearing.","supporting_citations":[{"cited_title":"In: Proc","cited_arxiv_id":null,"evidence_quote":"Supplies the negative drift theorem for populations used to prove the exponential lower bound."},{"cited_title":"In: Proc","cited_arxiv_id":null,"evidence_quote":"Establishes the fitness-level analysis for non-elitist populations and the OneMax lower bound that this paper extends."},{"cited_title":"Algorithmica 75(3), 428–461 (2016)","cited_arxiv_id":null,"evidence_quote":"Provides the level-based theorem (Theorem 1) and the low-mutation OneMax result generalized here."},{"cited_title":"IEEE Trans","cited_arxiv_id":null,"evidence_quote":"Origin of the level-based analysis framework and the corollary that Theorem 1 tailors."},{"cited_title":"In: Proc","cited_arxiv_id":null,"evidence_quote":"Earlier negative result on OneMax and the exponential-scaling idea that Theorem 7 generalizes."},{"cited_title":"Theoretical Computer Science 276(1-2), 51–81 ( Apr 2002)","cited_arxiv_id":null,"evidence_quote":"Baseline $\\Theta(n\\log n)$ runtime for the (1+1) EA on linear functions, contrasted with population-based results."},{"cited_title":"Comb Probab Comput","cited_arxiv_id":null,"evidence_quote":"Tight bounds for the (1+1) EA on linear functions, providing context for the population-based analysis."}],"review_version":1}