{"id":"b1aaffe6-dcda-4c89-814f-36fca64c0af1","arxiv_id":"1908.06527","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The cGA optimizes jump functions with jump size up to (1/20)ln n in O(n log n) generations when the population parameter is chosen well, and needs exp(Ω(k)) generations for large jumps no matter the parameter.","lead":"This paper proves tight runtime bounds for the compact genetic algorithm (cGA) on jump functions, a standard multimodal test problem. For small jumps the cGA finds the optimum in O(n log n) time with the best population size, and for large jumps no parameter choice can beat exponential time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 26's Ω(n log n) lower bound is not self-contained: it depends on SW19's internal lemmas and a privately corrected boundary estimate (footnote 4), so the matching lower bound is conditional.","rationale":"I read the paper in good faith. The central positive result, Theorem 13, is proven through a careful three-phase argument (Lemmas 15–21) and I did not find a concrete error in the drift or boundary estimates that would invalidate it. The exponential lower bound Theorem 22 also appears internally consistent; the rescaling via Y_t and the case analysis are detailed. The reader's conditional verdict identifies exactly the same weak point I would flag: Theorem 26. The proof of this theorem does not reproduce the SW19 lower bound but transfers its internal lemmas, and the transfer contains a known numerical correction that is not proven in the paper. Because the paper explicitly concedes the omission and relies on a private communication, the Ω(n log n) part of Theorem 26 should be regarded as not fully established. I therefore agree with the reader's weakest_assumption and keep the conditional verdict; no change is needed. I would not escalate to rejection because the main upper bound and the exponential lower bound are independent and appear sound, and the disputed lower bound is a completeness result rather than the central contribution.","tokens_in":42487,"tokens_out":27468,"duration_ms":266287,"concrete_test":"Independently re-derive the relevant part of [SW19, Lemma 15] using the corrected estimate that a lower-boundary frequency leaves with probability O(1/n), and verify that the conclusion used by Theorem 26 still holds: after T = Θ(n log n) iterations, with probability 1 - poly(n)2^{-Ω(min{µ,n})}, at least √n frequencies remain at the lower boundary and Ω(n) frequencies stay in [1/6,5/6]. If the corrected constants force a smaller T or fewer remaining frequencies, the transfer fails and Theorem 26's Ω(n log n) term is unsupported; if the conclusion survives, the gap is a minor exposition issue. A published erratum or a self-contained appendix from the authors would also settle it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline upper bound (Theorem 13) and the uniform exponential lower bound (Theorem 22) are supported by detailed self-contained proofs; I found no flaw in those arguments that would threaten the main 'no extra cost' claim. The load-bearing weakness is the Ω(µ√n + n log n) lower bound in Theorem 26. Its proof is explicitly not self-contained: Section 6.2 states 'we cannot give a self-contained version of the proof' and instead argues that Lemmas 10–15 of [SW19] remain valid for jump functions with k ≤ κn. Footnote 4 then concedes that one estimate in that transfer, the probability O(n^{-3/2}) that a frequency at the lower boundary leaves it, is wrong and must be replaced by O(1/n), with the correction confirmed only privately by the authors of [SW19]. The rest of the transfer does not quantify how this change propagates through Lemma 15 of [SW19] or through the final paragraphs of the OneMax lower bound. Since Theorem 26 is the only support for the abstract's claim that Ω(µ√n + n log n) 'completes the picture', the matching lower bound is currently conditional on an unverifiable private communication. This does not affect Theorem 13 or Theorem 22, but it does affect the paper's completeness claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper analyzes the runtime of the compact genetic algorithm (cGA) on jump functions. It proves an O(µ√n) upper bound (Theorem 13) for subjump functions with jump size k ≤ (1/20)ln n - 1 and µ ≥ K√n ln n polynomially bounded in n, an exponential lower bound exp(Ω(k)) for all hypothetical population sizes µ (Theorem 22), and a lower bound Ω(µ√n + n log n) (Theorem 26) intended to match the upper bound for small k. The paper also contains ancillary results: a parallel-run scheme that converts high-probability runtime guarantees into expected-runtime guarantees (Theorem 2), and negative results showing that standard domination arguments cannot transfer OneMax lower bounds to arbitrary functions with unique optimum (Lemmas 24 and 25).","tokens_in":42686,"tokens_out":4401,"duration_ms":45556,"significance":"If the main results hold, this is a significant advance in the theory of estimation-of-distribution algorithms: it is the first analysis showing that the cGA can cross moderate fitness valleys at no extra cost compared with optimizing OneMax, and it provides the first exponential lower bound for an EDA that holds for arbitrary parameter settings. Theorems 13 and 22 are supported by detailed, self-contained proofs with explicit universal constants, and the paper correctly identifies and avoids a mean-field dependency issue in the earlier analysis of Hasenöhrl and Sutton. The parallel-run meta-algorithm of Theorem 2 is a useful side contribution. However, the lower bound in Theorem 26 is not self-contained and currently rests on a privately communicated correction, so the paper's 'complete the picture' claim is conditional.","major_comments":[{"comment":"The claimed Ω(µ√n + n log n) lower bound is not proven in the manuscript. The proof states that a self-contained version cannot be given and instead transfers Lemmas 10–15 of [SW19] to jump functions, including a boundary correction from O(n^{-3/2}) to O(1/n) that is said to have been confirmed privately by the authors of [SW19]. Because the corrected estimate is not proved and its propagation through Lemma 15 of [SW19] and the final paragraphs of that proof is not quantified, the theorem as stated is conditional. This is load-bearing for the abstract's claim that the picture is completed; either include the full transfer argument or state Theorem 26 as a conditional result and adjust the abstract and conclusion accordingly.","section":"Section 6.2, Theorem 26 and footnote 4"},{"comment":"The assertion that with the correct boundary estimate 'at least √n frequencies remain at the lower boundary at the end of the first T iterations' needs a supporting calculation. Lemma 15 of [SW19] has failure probability poly(n)2^{-Ω(min{µ,n})}, and it is not immediate that a per-iteration exit probability of O(1/n) preserves the conclusion under the constants needed in that proof. Without a self-contained analysis of this point, the Ω(n log n) part of Theorem 26 is unsupported.","section":"Section 6.2, footnote 4"}],"minor_comments":[{"comment":"The notation μ = Ω(√n log n) ∩ poly(n) is nonstandard as written; the theorem statements later give the intended meaning (μ ≥ c_μ√n ln n and μ ≤ n^{C_μ}), so the abstract formulation should be aligned with the precise statements.","section":"Abstract and Section 1.1"},{"comment":"There is a typo: 'mution' should be 'mutation' in the sentence beginning 'the number of bits that are flipped in a mution follows a binomial distribution'.","section":"Section 4.4"},{"comment":"In the proof of Lemma 12 the dimension parameter m is set, but the proof then uses n in expressions such as x1[ℓ+1..n]; this should be reconciled by consistently using m or by writing n for the dimension throughout the proof.","section":"Lemma 12"},{"comment":"The phrase 'with high probability needs at least Ω(µ√n + n log n) iterations' could be made more precise by noting that this is a lower bound on the optimization time, not on the first hitting time of a particular frequency state; the formal statements in Section 6 are clearer.","section":"Section 2.2"}],"recommendation":"major_revision","confidential_remarks":"The core contributions of the paper are strong: Theorems 13 and 22 have careful, mostly self-contained proofs, and the paper makes a genuine conceptual contribution about EDAs and fitness valleys. The main obstacle is Theorem 26, whose proof explicitly relies on a private communication and is not self-contained. Because this is localized and fixable — either by supplying the transfer proof or by marking the theorem conditional — major revision is more appropriate than rejection. The self-citations to [Doe19b] and [Doe19c] are reasonable given the paper's provenance as an extended version, though the novelty of Theorem 26 relative to those conference papers should be clarified in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the first rigorous runtime analysis of a univariate EDA on a multimodal function, and the main result is real. Theorem 13 proves that the cGA with μ = Θ(√n log n) optimizes jump functions with k ≤ (1/20) ln n in O(n log n), matching the OneMax lower bound. The proof is self-contained and explicitly fixes real errors in Hasenöhrl–Sutton and in Droste's drift argument. Theorem 22's uniform exp(Ω(k)) lower bound, valid for every μ, is also proven in full and is a genuinely new type of statement for EDAs. I checked the main lines of both proofs and found no flaw that threatens either result. The paper also earns credit for showing why domination arguments do not automatically extend OneMax lower bounds to other functions; that section is honest and useful.\n\nThe soft spot is Theorem 26, the Ω(μ√n + n log n) lower bound for jump functions. The proof is not self-contained: it transfers the internal lemmas of Sudholt–Witt's OneMax proof, and footnote 4 concedes that one estimate in that transfer is wrong, with the correction confirmed only privately. The stress-test note is right: as written, the matching lower bound is conditional on an unverifiable communication. This does not affect Theorem 13 or Theorem 22, but it does affect the paper's completeness claim. The fix is straightforward in spirit — reproduce the transfer, or publish a separate proof of the boundary estimate — but it needs to happen before the result can be taken as stated.\n\nThe paper is aimed at researchers in runtime analysis of EDAs and, more broadly, anyone interested in why EDAs cross fitness valleys cheaply. It deserves a serious referee: the two main theorems are important, the errors in prior work are real, and the proof techniques are reusable. My recommendation: accept after the Theorem 26 gap is addressed, either by a self-contained proof or by a clearly marked erratum with the corrected estimate. The paper is too strong to desk-reject, but too conditional in its final section to publish unchanged.","headline":"A genuine breakthrough for EDA runtime analysis, with a solid self-contained upper bound and exponential lower bound, but the matching Ω(n log n) lower bound is conditional on an unverified transfer from Sudholt–Witt.","tokens_in":43319,"tokens_out":1576,"would_cite":true,"duration_ms":19279,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"For jump widths up to (1/20) ln n, the compact genetic algorithm optimizes in O(n log n), matching OneMax; larger jumps cost exponential time for every population-size setting.","keywords":["compact genetic algorithm","estimation-of-distribution algorithms","jump functions","runtime analysis","drift analysis","multimodal optimization","population size","lower bounds"],"falsifier":"Evaluate exactly, for the cGA on a jump function with k ≤ κn, the one-step probability that a frequency at the lower boundary 1/n enters the interior. The proof of the Ω(n log n) lower bound requires this probability to be O(1/n) and requires at least √n frequencies to remain at the boundary; a numerical Markov-chain calculation that finds a larger exit probability, or fewer pinned frequencies, would invalidate Theorem 26.","tokens_in":42222,"feed_emoji":"🧬","tokens_out":13165,"duration_ms":119587,"temperature":0.7,"pith_summary":"This paper proves that the compact genetic algorithm (cGA) can cross moderate fitness valleys at no extra cost. On any $n$-dimensional jump function with gap width $k \\le \\frac{1}{20}\\ln n - 1$, the cGA with hypothetical population size $\\mu$ between $\\Omega(\\sqrt n \\log n)$ and $\\operatorname{poly}(n)$ finds the optimum with high probability in $O(\\mu\\sqrt n)$ iterations, which is $O(n\\log n)$ for the smallest admissible $\\mu$---the same order as its runtime on the unimodal OneMax function. For larger gaps, the paper shows an exponential lower bound $\\exp(\\Omega(k))$ that holds for every population size, so the earlier exponential guarantee of [HS18] cannot be improved by tuning $\\mu$. A matching lower bound $\\Omega(\\mu\\sqrt n + n\\log n)$ for all jump functions, plus a parallel-run method that converts high-probability guarantees into expected runtimes without prescribing $\\mu$, completes the picture.","feed_headline":"Small fitness valleys cost the compact GA nothing","feed_subtitle":"For jump sizes up to (1/20) log n, runtime is O(n log n); larger jumps take exponential time.","key_machinery":"The load-bearing object is the cGA's frequency vector $f_t$ and its aggregate distance from the all-ones optimum, $D_t = n - \\|f_t\\|_1$. While $D_t$ is large, gap samples are so rare that the run can be coupled to a OneMax run (Lemma 16); the proof then uses a drift estimate (Lemma 17) that corrects a mean-field mistake in [HS18], and a reduction of each component frequency to a fair random walk on a reflecting grid (Lemma 19) that keeps all frequencies above $1/3$ for long enough. In this regime the drift of $D_t$ is $\\Omega(1/\\mu)$, which by the additive drift theorem yields $D_t \\le O(k)$ within $O(\\mu\\sqrt n)$ iterations. From such small $D_t$, Lemma 11 shows the optimum is sampled with probability $1-n^{-\\omega(1)}$ in $O(\\mu \\log^{-2} n)$ more iterations. The exponential lower bound uses a different object: the rescaled process $Y_t = \\exp(c\\min\\{\\frac12 k - D_t, \\frac14 k\\})$, whose one-step drift is at most a constant; a Markov bound then forces $D_t$ to remain above $k/4$ for $\\exp(\\Omega(k))$ steps.","core_discovery":"The central discovery is that the cGA's runtime on jump functions is controlled by the frequency distance $D_t = n - \\|f_t\\|_1$: as long as no sampled search point lies in the gap, the process behaves exactly as on OneMax, and once a gap sample occurs, the drift of $D_t$ can still be bounded from below. The paper proves (Theorem 13) that for jump size $k \\le \\frac{1}{20}\\ln n - 1$, any hypothetical population size $\\mu$ between $\\Omega(\\sqrt n \\log n)$ and $\\operatorname{poly}(n)$ yields $O(\\mu\\sqrt n)$ iterations with probability $1-O(n^{-0.4})$; with $\\mu = \\Theta(\\sqrt n \\log n)$ this is $O(n\\log n)$. The proof is phase-based: first $D_t$ is driven to $O(\\log n)$ without ever sampling the gap, then to $O(k)$ using the drift estimate of Lemma 17, while Lemma 19, a pessimistic fair-random-walk replacement for each frequency, rules out frequencies dropping below $1/3$; from a state with $D_t$ of order $k$, Lemma 11 shows the optimum is sampled quickly with overwhelming probability. Theorem 22 gives the complementary lower bound: for every $\\mu$, an exponential rescaling $Y_t = \\exp(c\\min\\{\\frac12 k - D_t, \\frac14 k\\})$ has at most constant drift, so $D_t$ stays above $k/4$ for $\\exp(\\Omega(k))$ steps, and in each such step the optimum is sampled only with probability $\\exp(-\\Omega(k))$. Theorem 26 transfers the OneMax lower bound of [SW19] to jump functions, giving $\\Omega(\\mu\\sqrt n + n\\log n)$ and establishing that the upper bound is tight at the optimal $\\mu$.","pith_inferences":["The proof's diagnosis that the cGA samples candidates with high variance, hitting the optimum from distance $O(k)$ with probability $\\exp(-O(k))$ rather than $n^{-k}$, suggests that other EDAs with similar sampling variance, such as the UMDA, may also cross logarithmic jumps at no extra cost; the paper does not prove this.","Because the paper shows the natural domination arguments that make OneMax the easiest function for many evolutionary algorithms fail for the cGA, a general $\\Omega(n\\log n)$ lower bound for all functions with a unique optimum would need a proof genuinely about the cGA's stochastic process, not a black-box reduction.","The $\\Omega(n\\log n)$ lower bound is proved for jump functions, not for superjump functions; the failure of the OneMax lower bound to transfer to all unique-optimum functions leaves open the possibility that superjump functions are strictly harder for the cGA.","A direct test of the sampling-variance mechanism would be to run a cGA variant with artificially reduced sampling variance on small-$k$ jumps; the theory predicts its runtime should degrade toward the exponential regime at smaller $k$ than the standard cGA."],"forward_implications":["For $k \\le \\frac{1}{20}\\ln n - 1$, the cGA with $\\mu = \\Theta(\\sqrt n \\log n)$ solves every subjump function in $O(n\\log n)$ iterations with probability $1-O(n^{-0.4})$, the same asymptotic as its OneMax runtime.","The prior guarantee of $O(n^{5+\\varepsilon})$ for small $k$ is replaced by $O(n\\log n)$, and the usable population sizes are enlarged from $\\Omega(n^{3.5+\\varepsilon})$ down to $\\Omega(\\sqrt n \\log n)$.","For any hypothetical population size, jump size $k = \\omega(\\log n)$ forces runtime $\\exp(\\Omega(k))$ with high probability, so no parameter tuning can beat the exponential guarantee of [HS18].","The lower bound $\\Omega(\\mu\\sqrt n + n\\log n)$ for $\\mu = \\Omega(\\log n)$ on jump functions matches the upper bound, so the $O(n\\log n)$ result is tight at the optimal $\\mu$.","The parallel-run method converts an EDA with a high-probability runtime guarantee into a parameter-less version with expected runtime $O(T^*\\log T^*)$, where $T^*$ is the best restart-based bound with the optimal population size."],"supporting_citations":[{"why":"Gives the previous exponential-in-k upper bound for the cGA on jump functions, which this paper improves for small k and shows tight for large k.","marker":"[HS18]"},{"why":"Provides the OneMax runtime analysis and the Ω(µ√n + n log n) lower bound whose lemmas Theorem 26 transfers to jump functions.","marker":"[SW19]"},{"why":"Supplies the earlier OneMax runtime analysis and Lemma 14, the constant-probability progress estimate used in Theorem 13's upper bound.","marker":"[Dro06]"},{"why":"Defines the compact genetic algorithm, its frequency-vector update, and the hypothetical population size parameter µ.","marker":"[HLG99]"},{"why":"Supplies the additive drift theorem that converts the drift bounds into the hitting-time estimates used in the phase analysis.","marker":"[HY01]"},{"why":"Provides the Hoeffding/Chernoff tail bounds, including the partial-sum form used to control random-walk excursions of frequencies.","marker":"[Hoe63]"},{"why":"Establishes the Ω(n^k) lower bound for mutation-based EAs on jump functions, the contrast that motivates the 'no extra cost' claim.","marker":"[DJW02]"}],"fun_headline_variants":["cGA crosses fitness valleys at zero extra cost","Small jump sizes: cGA runs in O(n log n)","Tight runtime bounds for compact GA on jump functions","For k ≤ (ln n)/20, cGA matches OneMax speed","Exponential lower bound for any population size"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The matching Ω(n log n) lower bound assumes that [SW19]'s OneMax lemmas remain valid for jump functions; footnote 4 in the proof of Theorem 26 concedes that one boundary-exit probability is wrong and replaces it with a weaker estimate confirmed only privately, with no self-contained proof in this paper.","fun_headline_variants_meta":{"raw":{"variants":["cGA crosses fitness valleys at zero extra cost","Small jump sizes: cGA runs in O(n log n)","Tight runtime bounds for compact GA on jump functions","For k ≤ (ln n)/20, cGA matches OneMax speed","Exponential lower bound for any population size"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000799,"raw_usage":{"total_tokens":3689,"prompt_tokens":1295,"completion_tokens":2394,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":911,"completion_tokens_details":{"reasoning_tokens":2314}},"tokens_in":911,"tokens_out":2394,"duration_ms":18878,"temperature":1.0,"reasoning_tokens":2314,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:42:10.276006+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate exactly, for the cGA on a jump function with k ≤ κn, the one-step probability that a frequency at the lower boundary 1/n enters the interior. The proof of the Ω(n log n) lower bound requires this probability to be O(1/n) and requires at least √n frequencies to remain at the boundary; a numerical Markov-chain calculation that finds a larger exit probability, or fewer pinned frequencies, would invalidate Theorem 26.","supporting_citations":[],"review_version":1}