{"id":"0068aee3-b7c5-41fa-98b7-f26a0cf5e202","arxiv_id":"2412.11684","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"SEMO and GSEMO cover a natural bi-objective integer benchmark in polynomial time, and power-law mutation is the most robust operator across parameters and starting points.","lead":"This paper proves the first runtime guarantees for multi-objective evolutionary algorithms on unbounded integer search spaces, testing three mutation strengths on a benchmark with a finite trade-off line. It finds that power-law mutation is the most robust choice across problem parameters and starting points, while tuned exponential-tail mutation can be faster only if the tuning is exactly right.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 16 appears sound, but the load-bearing gap is generalizing from the finite-line benchmark f to all unbounded integer problems: every proof uses the L1-dominance alignment and the 1/(2a+1) population bound that this specific benchmark provides.","rationale":"The stress-test pass found no internal inconsistency in the main proofs. I re-checked the two-phase drift arguments: Lemma 5's L1-dominance coupling is valid, Lemma 13's truncated geometric bounds check out, and the power-law variable drift calculations in Lemmas 18-19, including the interval-doubling phase, are sound up to constants. The slight non-monotonicity in the drift bound near the phase boundary can be repaired by taking h(X) = max(constant, X^{2-beta}/constant), so it does not invalidate Theorem 16. The load-bearing weakness is therefore not the theorem but the move from the single finite-line benchmark to a general recommendation. Every bound uses the special structure of f: finite Pareto front, uniqueness per first coordinate, and L1 as a monotone potential. The experiments, while reproducible and clearly reported, cover only this benchmark, a <= 200, n <= 10, 50 runs, and one starting-point family. Thus the practical conclusion 'prefer power-law mutation for unknown problems in integer spaces' is an extrapolation. The reader's weakest_assumption identifies exactly this generality gap, so I agree. The concrete test of a second benchmark with an unbounded (or truncated-unbounded) Pareto front would settle whether the recommendation is robust; until then, CONDITIONAL is the right verdict, and no change to the reader's verdict is needed.","tokens_in":25778,"tokens_out":27486,"duration_ms":274218,"concrete_test":"Run GSEMO with power-law mutation (beta = 1.5) and exponential-tail mutation (q tuned per case, e.g., q in {1/5, 1/10, ..., 1/M}) on a second benchmark with a genuinely unbounded Pareto front, such as f_M(x) = (|x1|, |x2|) on Z^2 with the goal of covering all Pareto-optimal objective values (0,k) and (k,0) for 0 <= k <= M, for M in {50, 100, 200} and x(0) = (0, 100M), 50 runs per cell. If power-law mutation does not dominate exponential-tail mutation across all M, the paper's general recommendation must be restricted to the finite-line benchmark class or supported by additional theory.","verdict_should_be":"UNCHANGED","load_bearing_attack":"All positive results are proven for the single benchmark f, whose Pareto front is the finite line {(k,0,...,0) | k in [-a,a]}. The proofs of Theorem 16, like the other runtime theorems, rely on benchmark-specific facts: Lemma 4 bounds the population by 2a+1, which follows from Lemmas 1-3 and the total comparability of solutions with equal first coordinate; Lemma 5 couples dominance to L1 order; and Lemma 6 makes the minimum L1 distance a non-increasing potential. These facts supply the 1/(2a+1) selection probability used in every drift bound, including Lemmas 18 and 19. For a problem with an unbounded Pareto front, or with two incomparable nondominated solutions sharing the same first coordinate, the population-size bound and the non-increasing L1 potential both fail, so none of the uniform runtime guarantees transfers. The experiments cover only this one benchmark, a up to 200, n up to 10, one starting-point family (0,100a), and 50 runs per cell (Tables 1 and 2). Consequently, the paper's final recommendation to prefer power-law mutation 'for unknown problems in integer spaces' extrapolates beyond the class for which any theorem or experiment is provided. This is a generality gap, not an internal inconsistency: Theorem 16 as stated appears correct.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper initiates the runtime analysis of multi-objective evolutionary algorithms on unbounded integer search spaces by analyzing SEMO and GSEMO (Algorithm 1) on the bi-objective benchmark f(x) = (|x1 - a| + sum_{i>=2}|xi|, |x1 + a| + sum_{i>=2}|xi|), whose Pareto front is the finite line {(k,0,...,0) : k in [-a,a]} of size 2a+1. Three mutation strengths are compared: unit-step (plus/minus 1), a bilateral geometric law with parameter q (exponential tails), and a symmetric power-law with exponent beta in (1,2). Each runtime is split into a first phase (hitting the all-zeros vector) and a second phase (covering the front). The main results are Theorem 9 (unit-step: O(n(2a+1)(||x(0)||1 + 2a))), Theorem 12 (exponential-tail: a bound dominated by an(n/q + ||x(0)||1 q + max{ln(a+1)/(aq), aq + ln(a+1)}) with an unspecified constant), and Theorem 16 (power-law: O(n(2a+1)||x(0)||1^(beta-1) + n(2a+1)^beta + n(2a+1)ln a), uniform over a and x(0)). Experiments for n in {2,4,10}, a up to 200, and 50 runs per setting indicate that power-law mutation is empirically fastest, including against a near-optimally tuned exponential-tail operator, and the authors recommend power-law mutation for unknown unbounded-integer problems.","tokens_in":26018,"tokens_out":37530,"duration_ms":315735,"significance":"If the theorems are correct, this is a genuine first step into a previously unstudied area: multi-objective runtime analysis in unbounded integer spaces. I spot-checked the drift arguments, case analyses, and constants in the appendix and found them consistent; for example, the constants in Theorem 16 majorize those derived in the proofs of Lemmas 18 and 19, and the integral estimates via Theorem 17 are valid. The most valuable result is Theorem 16, giving a parameter-free mutation operator with a polynomial bound uniform in a, n, and the starting point. The paper is also honest: it states that its bounds are not tight, that no lower bounds are proven, and that the experiments contradict the asymptotic ordering suggested by the upper bounds; the code is publicly available. The main shortcomings are the gap between the benchmark-specific structural lemmas and the general operator recommendation, and an internal inconsistency in the empirical section's theoretical comparison (see major comments). Once these are fixed, this will be a solid and useful contribution to the theory of evolutionary multi-objective optimization.","major_comments":[{"comment":"The headline recommendation - to favor power-law mutation 'for unknown problems in integer spaces' (Abstract, Conclusion) - extends beyond the class of problems for which any theorem or experiment is provided. Every positive result is proven for the single benchmark f, whose Pareto front is the finite line {(k,0,...,0) | k in [-a,a]}, and every drift argument in Lemmas 10, 14, 18, and 19 uses the population bound |P(t)| <= 2a+1 (Lemma 4) and the non-increasing minimum L1 distance (Lemma 6). These are benchmark-specific: Lemma 1 and Lemma 3 rely on total comparability of solutions with equal or out-of-range first coordinate, Lemma 5 couples dominance to L1 order, and Lemma 6 follows from Lemma 5; these facts supply the 1/(2a+1) selection probability used throughout. For a problem with an unbounded Pareto front, or with two incomparable nondominated solutions sharing a first coordinate, the population bound fails and the L1 potential can increase, so none of the uniform guarantees transfers. The experiments cover only this one benchmark, starting points with a single non-zero component equal to 100a, and a up to 200. This is a scoping gap rather than an error in Theorem 16 as stated, but it is load-bearing for the concluding recommendation. The authors should either scope the title, abstract, and conclusion to the benchmark class with an explicit limitation statement, or prove that a broader class of unbounded-integer objectives satisfies analogues of Lemmas 1-6.","section":"Abstract, Conclusion, Lemmas 1-6"},{"comment":"The comparison of the exponential-tail operator with the paper's own Theorem 12 is misstated. The paragraph claims the runtime 'is in the order of a^2 q + a max{ ln(a+1)/(aq), aq + ln(a+1)}' and that 'choosing q = 1/a minimizes the maximum expression ... resulting in a runtime bound in the order of a ln(a)'. This omits the first-phase term (2a+1)en/K * n*pi^2/(6q) from Lemma 14, which is the Theta(an^2/q) term in Theorem 12. At q = 1/a this term equals Theta(a^2 n^2), which dominates the claimed a ln(a) for every constant n >= 2; hence the asserted optimality of q = 1/a and the 'quasi-linear' comparison with power-law mutation do not follow from the bounds actually proven. Including the omitted term shifts the predicted optimal q and weakens the abstract's statement that exponential-tail 'yields the best runtime guarantees in our results'. Please reconcile the empirical theoretical comparison with Lemma 14 and Theorem 12, or state explicitly which regime of the bound is being ignored and why.","section":"Empirical Analysis, 'Theoretical considerations'"}],"minor_comments":[{"comment":"In the first sentence, 'letting S from Lemma 11 be T2' should read 'be T1'; as written, the definition of T2 is circular.","section":"Appendix, Proof of Theorem 9"},{"comment":"The first paragraph contains two issues: 'GESMO' should be 'GSEMO', and the claim that the GSEMO's runtime 'should be worse by a factor of at most e' is a statement about the proven upper bounds (factors 2n vs. 2en in Theorems 9, 12, and 16), not about the true runtimes; please rephrase accordingly.","section":"Empirical Analysis, first paragraph"},{"comment":"The bound is written as an equality, E[T | x(0)] = C(...), with C an unspecified 'sufficiently large' constant; since the proof supplies an upper bound, it would be clearer to write '<=' and to state that C depends on the constant c and on K from Lemma 13, as the current phrasing invites misreading as a two-sided estimate.","section":"Theorem 12"},{"comment":"The claim that each uncovered Pareto-optimal point 'has at least one neighbor in the population in distance 1' is not true for an arbitrary cover of half a path (e.g., a = 3 with covered set {0,1,-2,-3} leaves point 3 with only uncovered neighbors). The claim holds here only because the preceding doubling steps end with every interval of the fine partition (size between 1 and 2) hit; please insert that justification, since the sentence as written hides a use of that structure.","section":"Lemma 19, last stage"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The core theorems appear correct, and I regard the manuscript as a worthwhile contribution; my recommendation for major revision rests on (i) the gap between the benchmark-specific proofs and the general operator recommendation in the abstract and conclusion, and (ii) a concrete inconsistency between the empirical section's 'theoretical considerations' and Lemma 14/Theorem 12. Both are fixable in revision. The benchmark and the power-law operator come from works with substantial author overlap (Rudolph 2023; Doerr et al. 2017), which is normal in this community and properly cited; I see no circularity. I would be comfortable with this paper in a theory-of-evolutionary-computation venue once the scoping and the empirical-theoretical comparison are corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is the first runtime analysis that treats multi-objective EAs on unbounded integer spaces as genuinely multi-objective, and the main upper bounds look correct. Second, all of those bounds are for one particular benchmark, so the paper's broader advice—prefer power-law mutation for unknown integer problems—is an extrapolation, not a proven statement.\n\nWhat the paper does well: it takes Rudolph's bi-objective benchmark, works out the structural lemmas (population bound, L1-dominance coupling, monotone potential), and then gives clean drift proofs for unit, exponential-tail, and power-law mutations for both SEMO and GSEMO. Theorem 16 is the centerpiece: with power-law exponent beta in (1,2), the expected time to cover the front is polynomial in a and in the (beta-1)-th power of the initial L1 distance, uniform over parameters and starting point. That is a real result, and the appendix proofs are detailed enough that I found no internal contradiction. The experiments are honest—they show the bounds are not tight, and they report that power-law beats a tuned exponential-tail in their setup, which is a genuinely interesting empirical observation. Code is on Zenodo; minor deduction for no commit hash, but it is reproducible in principle.\n\nWhere it is soft. The main gap is exactly the one the stress-test note names: every drift bound uses that the Pareto front is the finite line (-a..a,0,...), that equal-first-coordinate solutions are comparable, and that the population is at most 2a+1. Those are benchmark-specific facts. For a problem with an unbounded Pareto front or two incomparable nondominated solutions sharing the first coordinate, the population bound and the L1 potential argument fail, and none of the uniform guarantees transfers. The authors do not hide that the theorems are for this benchmark, but the abstract and conclusion still recommend power-law mutation 'for unknown problems in integer spaces.' That recommendation should be softened or paired with additional benchmarks. Smaller points: the constants C and K are existential, so the bounds are not ready for quantitative prediction; there are no lower bounds; and the experiments cover only n up to 10, a up to 200, one starting-point family, 50 runs per cell.\n\nBottom line: the theorems look sound, the paper opens a genuinely new area, and the empirical finding is worth reporting. It deserves a serious referee. My recommendation: accept after the authors narrow the scope of the practical recommendation.","headline":"First sound runtime analysis of multi-objective EAs on unbounded integer spaces, with upper bounds proven for a finite-line benchmark; the broader practical recommendation to prefer power-law mutation goes beyond what the theorems or experiments support.","tokens_in":26576,"tokens_out":2410,"would_cite":true,"duration_ms":22649,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W50","90C29"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that power-law mutation gives polynomial, parameter-free runtime bounds for multi-objective evolutionary algorithms on unbounded integer spaces.","keywords":["runtime analysis","multi-objective evolutionary algorithms","unbounded integer search spaces","power-law mutation","SEMO","GSEMO","drift analysis","Pareto front"],"falsifier":"Pick beta=1.5, a large a, and a starting point with L1-norm comparable to a, run GSEMO with power-law mutation on f thousands of times, and check whether the mean runtime ever exceeds the right-hand side of Theorem 16 by a constant factor; a violation for a single parameter combination would refute the claimed uniform bound.","tokens_in":73,"feed_emoji":"🧬","tokens_out":4118,"duration_ms":129676,"temperature":0.7,"pith_summary":"The paper opens the runtime analysis of multi-objective evolutionary algorithms on unbounded integer search spaces, a setting where almost no theory existed. On a natural bi-objective benchmark whose Pareto front is a finite line of 2a+1 points, the authors prove expected-runtime bounds for SEMO and GSEMO under three mutation strengths. The central result is that power-law mutation with constant exponent beta in (1,2) covers the full Pareto front in time polynomial in the width a and in the initial L1-distance, uniformly over all starting points. Unit-step mutation can be slow from far away, and exponential-tail mutation is only good with a carefully tuned step-size parameter. The paper recommends power-law mutation for unknown integer-space problems, backed by experiments.","feed_headline":"Power-law mutation wins on unbounded integer spaces","feed_subtitle":"New runtime bounds show a parameter-free heavy-tailed operator beats unit-step and tuned exponential mutations.","key_machinery":"The analysis is driven by a potential function equal to the minimum L1-norm among all population members. Lemmas 1 through 6 show that this minimum never increases, that the population never exceeds 2a+1 individuals, and that all progress toward the zero vector is monotone in L1. The runtime proof splits into two phases: first hit the Pareto front by drifting the minimum L1-norm to zero, then cover the front by a doubling argument over intervals; drift theorems turn the per-step expected progress into hitting-time bounds, and the power-law's heavy tail supplies the uniform progress.","core_discovery":"The paper's central claim is Theorem 16: for both SEMO and GSEMO using power-law mutation with any constant exponent $\\beta$ in (1,2), the expected number of function evaluations to cover the entire Pareto front of the benchmark f is bounded by a product of (2a+1), n, and a polynomial whose leading terms are O(a^$\\beta$) from covering the front and O(||x(0)||$_1^{{beta-1}}$) from the initial approach, with constants depending only on $\\beta$. This holds uniformly for every initial search point x(0), with no tuning of the mutation operator.","pith_inferences":["The empirical observation of roughly linear runtime for power-law, far below the theorem's polynomial bound, suggests the true worst case is smaller and that the maximum-population assumption in the analysis is pessimistic.","If the uniform polynomial bound holds, it implies that the choice of mutation operator is more decisive than the choice between SEMO and GSEMO in unbounded integer spaces, since both receive essentially the same guarantee.","A natural extension would replace the finite line Pareto front by an infinite or higher-dimensional integer Pareto set; the present proof relies on |F*|=2a+1, so the recommendation to prefer power-law mutation should be re-examined there."],"forward_implications":["Unit-step mutation is at most linearly affected by initial distance but pays an extra linear factor per step, so from far starting points it is slowest.","Exponential-tail mutation can beat power-law in theory only when its scale q is chosen as a function of a and x(0); a wrong q can make the guarantee much worse.","Power-law mutation achieves a polynomial guarantee that does not depend on knowing a or x(0), making it the first parameter-free mutation operator with uniform worst-case bounds in this setting.","The two-phase drift framework applies to any finite-line Pareto front, so the same type of bound should transfer to problems whose Pareto set lies on a finite line of integer solutions."],"supporting_citations":[{"why":"Introduces the benchmark function f and establishes its Pareto set and front that this paper analyzes.","marker":"Rudolph 2023"},{"why":"Introduces the power-law mutation operator whose uniform bounds form the central result.","marker":"Doerr et al. 2017"},{"why":"Defines the SEMO algorithm used as one of the two analyzed variants.","marker":"Laumanns et al. 2002"},{"why":"Defines the GSEMO algorithm and its global mutation framework.","marker":"Giel 2003"},{"why":"Provides the discrete variable drift theorem used to convert per-step progress into expected hitting times.","marker":"Doerr et al. 2020"},{"why":"Provides the additive drift theorem used for the unit-step and second-phase arguments.","marker":"He and Yao 2004"}],"fun_headline_variants":["Parameter-free power-law mutation wins on unbounded integer spaces","Power-law mutation betters tuned exponential on unbounded integers","No tuning needed: power-law mutation wins on integer search spaces","Uniform runtime bounds favor power-law mutation in integer spaces"],"cache_read_input_tokens":28672,"weakest_assumption_plain":"The proofs assume the objective has a finite line Pareto front with exactly 2a+1 points, so the uniform power-law recommendation is only directly established for problems with that structure.","fun_headline_variants_meta":{"raw":{"variants":["Parameter-free power-law mutation wins on unbounded integer spaces","Power-law mutation betters tuned exponential on unbounded integers","No tuning needed: power-law mutation wins on integer search spaces","Uniform runtime bounds favor power-law mutation in integer spaces"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000649,"raw_usage":{"total_tokens":2982,"prompt_tokens":949,"completion_tokens":2033,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":565,"completion_tokens_details":{"reasoning_tokens":1966}},"tokens_in":565,"tokens_out":2033,"duration_ms":13009,"temperature":1.0,"reasoning_tokens":1966,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:42:56.794374+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Pick beta=1.5, a large a, and a starting point with L1-norm comparable to a, run GSEMO with power-law mutation on f thousands of times, and check whether the mean runtime ever exceeds the right-hand side of Theorem 16 by a constant factor; a violation for a single parameter combination would refute the claimed uniform bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the benchmark function f and establishes its Pareto set and front that this paper analyzes."},{"cited_title":"P.; Makhmara, R.; and Nguyen, T","cited_arxiv_id":null,"evidence_quote":"Introduces the power-law mutation operator whose uniform bounds form the central result."}],"review_version":1}