{"id":"de236599-9860-4bf1-b068-9fca1f37d698","arxiv_id":"1908.01230","paper_version":5,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves a faster O(nP ln(1/epsilon)) analysis of Pareto optimization, but its new biased Pareto algorithm relies on an invalid Chernoff step and is not established.","lead":"This paper claims faster guarantees for evolutionary algorithms that choose a good representative subset from a large collection. It also introduces a biased variant that it says matches the fastest known subset-selection algorithm while keeping a population of solutions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Chernoff step in the proof of Theorem 2 has reversed containment for allowed parameters (e.g., P close to n, ξ=1/2), so the BPO query-complexity guarantee is not established.","rationale":"The paper's headline contribution is the BPO/κ-BPO query complexity matching stochastic greedy. That rests on Theorem 2. The proof of Theorem 2 has one place where a high-probability event must be shown: after T iterations the counter l_q has been incremented H_qκ times. Lemma 6 models these increments as Binomial(T,p/M), and the proof then uses a Chernoff lower-tail bound. The lower-tail bound is applied to the wrong threshold: the required number of successes can be much larger than Tp/(2M), so the event being bounded is not contained in the event the Chernoff bound controls. The explicit parameter example shows the claimed bound can fail by a large margin. Because Theorem 3's proof is explicitly 'left to the reader' and depends on the same style of argument, this defect undermines both BPO and κ-BPO claims. The reader's weakest_assumption identified exactly this reversed containment; my read agrees. I therefore see no basis to change the reader's REJECT verdict.","tokens_in":17770,"tokens_out":14177,"duration_ms":140098,"concrete_test":"Run the counterexample n=P=1000, κ=999, ξ=1/2, ε=0.01, p=1. Compute M=⌈log_2 1000⌉=10 and q=1 via Eq. (2); then H_1κ=2e ln(100)·999 and T=2e ln(100)·1000·10. Evaluate P(Bin(T,1/M) < H_1κ) exactly or by normal approximation. If, as anticipated, it is ≈0.43 rather than ≤0.01, the proof's Chernoff step is invalid. Analytically, verify H_1κ > Tp/(2M), so the appendix's inequality (a) has reversed containment and cannot be repaired by a different Chernoff constant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive defect is in the proof of Theorem 2. The proof sets M=⌈ln(P)/ln(1/ξ)⌉ and H_q=e ln(1/ε)/ξ^q, then reduces the desired event to S=ΣY_i ≥ H_qκ with S~Bin(T,p/M). It writes P(S < H_qκ) ≤ P(S < Tp/(2M)) and applies Chernoff. This containment requires H_qκ ≤ Tp/(2M). Substituting T ≥ 2en ln(1/ε)M/p gives the requirement κ/ξ^q ≤ n. But Equation (2) only gives κ/ξ^q ≤ P/ξ, so the requirement can fail exactly when ξ<1 and P is close to n. Example: n=P=1000, κ=999, ξ=1/2, ε=0.01, p=1. Then q=1, M=10, H_1κ≈25,011 and Tp/(2M)≈12,518, so {S<Tp/(2M)} is a strict subset of {S<H_1κ}; the displayed inequality has the wrong direction. The actual binomial tail is roughly 0.43, not ≤0.01. Thus the only high-probability argument for the event F breaks down in a parameter regime Theorem 2 explicitly covers. A related range failure is that for P=2,κ=1,ξ=1/2 no q∈{1,...,M} satisfies Eq. (2), so the proof's setup itself is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies monotone submodular maximization under a cardinality constraint. Its first contribution is a new analysis of the Pareto optimization algorithm PO, claimed to achieve a (1-epsilon)(1-1/e) approximation in expectation for every kappa < P in O(nP ln(1/epsilon)) queries, improving on the previous O(nP^2) analysis. The second contribution is a new algorithm BPO that uses a biased selection rule and is claimed to achieve a (1-epsilon)(1-1/e-epsilon) approximation in expectation for every kappa < P in O(n ln(P) ln(1/epsilon)) queries, matching the stochastic greedy algorithm's query complexity; a further specialization kappa-BPO is claimed to achieve the same ratio for a fixed kappa in O(n ln(1/epsilon)) queries. The paper also reports experiments on data summarization instances.","tokens_in":18083,"tokens_out":17879,"duration_ms":155690,"significance":"If the claims are correct, the paper would make a meaningful contribution: the PO analysis removes a factor P from the prior query complexity, and BPO would be, to my knowledge, the first evolutionary algorithm for monotone submodular maximization matching the stochastic greedy query complexity while maintaining a solution pool. The exposition is generally clear, the algorithms are given as pseudocode, and the empirical study supports the qualitative convergence behavior. However, the proof of the main BPO theorem contains a load-bearing error in the Chernoff application, and the proof of the kappa-BPO theorem is omitted; as a result the central claims for BPO and kappa-BPO are not established in the current manuscript.","major_comments":[{"comment":"The Chernoff step reverses the required containment. The proof writes P(sum_i Y_i < H q * kappa) <= P(sum_i Y_i < Tp/(2M)), but this is valid only when H_q * kappa <= Tp/(2M). Substituting H_q = e ln(1/epsilon)/xi^q and using Eq. (2) gives H_q * kappa <= e ln(1/epsilon) P / xi, while T >= alpha n M with alpha = 2e ln(1/epsilon)/p yields Tp/(2M) >= e n ln(1/epsilon). For P close to n and xi < 1, the first quantity can exceed the second. Example: n = P = 1000, kappa = 999, xi = 1/2, epsilon = 0.01, p = 1 gives q = 1, M = 10, H_1 kappa ~= 25,011, but Tp/(2M) ~= 12,518, so the event {sum < Tp/(2M)} is a strict subset of {sum < H_1 kappa} and the displayed inequality has the wrong direction. The Chernoff bound therefore does not control the probability of event F, and the O(n ln(P) ln(1/epsilon)) query-complexity claim for BPO is not proved.","section":"Section 2.2, End of Proof of Theorem 2 (Appendix 5.2)"},{"comment":"Even if the containment were repaired, the final probability bound is not epsilon. The chain concludes e^{-Tp/(8M)} <= epsilon with justification (c) that T >= 8 ln(n) M / p, but that only yields e^{-Tp/(8M)} <= 1/n. The theorem statement sets beta = 8/p, so the second term in T gives the 1/n bound, not an epsilon bound. The law-of-total-expectation step would then give a (1 - 1/n) factor instead of (1 - epsilon) unless one additionally assumes n >= 1/epsilon. This needs to be corrected either by changing the second term to 8 ln(1/epsilon) M / p or by modifying the theorem statement and proof accordingly.","section":"Section 2.2, End of Proof of Theorem 2 (Appendix 5.2)"},{"comment":"The existence of q in {1,...,ceil(ln(P)/ln(1/xi))} satisfying xi^q P < |A*| <= xi^{q-1} P is not guaranteed for all parameters covered by Theorem 2. For example, P = 2, kappa = 1, xi = 1/2 gives M = ceil(ln 2 / ln 2) = 1, and q = 1 fails because xi^1 P = 1 is not strictly less than kappa = 1. More generally, the condition can fail whenever P/kappa is exactly a power of 1/xi and M is too small. Since Theorem 2 quantifies over all kappa < P and all xi in (0,1), the proof does not cover its stated parameter range.","section":"Section 2.2, Eq. (2)"},{"comment":"The proof of Theorem 3 is not written out ('details are left to the reader'). This is one of the paper's headline results, and given that the analogous proof for Theorem 2 has the technical problems described above, the omission is not acceptable. A self-contained proof of Theorem 3, including the Chernoff step with explicit constants, is needed before the result can be verified.","section":"Section 2.3, Theorem 3"}],"minor_comments":[{"comment":"The statement of Lemma 4 in the appendix says P(sum_i Y_i < kappa) <= 1/n, while the main text states the same lemma with the bound epsilon and the proof concludes epsilon. This inconsistency should be fixed.","section":"Section 2.1, Lemma 4"},{"comment":"The proof of Lemma 6 says the success probability is p, but the lemma statement and the algorithm give p/ceil(ln(P)/ln(1/xi)). The proof should state that the index j must equal q as well.","section":"Appendix 5.2, Lemma 6 proof"},{"comment":"The text says the experiments evaluate PO and kappa-BPO, but the figure legends label a curve as 'BPO' rather than 'kappa-BPO'. This should be clarified.","section":"Section 3, Figure 1"},{"comment":"The abstract states the BPO guarantee as (1-epsilon)(1-1/e-epsilon) in one sentence and as (1-epsilon)(1-1/e) in another; the body consistently uses (1-epsilon)(1-1/e-epsilon). Please harmonize the wording.","section":"Abstract and Section 1.1"}],"recommendation":"major_revision","confidential_remarks":"The paper contains interesting algorithmic ideas and a plausible framework, but the current proof of Theorem 2 is not reliable: the Chernoff containment is reversed in a parameter regime the theorem explicitly covers, and the final tail bound is 1/n rather than epsilon. These are not minor typos but affect the central query-complexity claim. I would be willing to reconsider if the authors provide a corrected analysis with explicit constants, address the q-existence issue, and write out the proof of Theorem 3. The empirical section is supportive but cannot substitute for the missing theory."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about arXiv:1908.01230. First, Theorem 1 is a genuine improvement: the Pareto optimization algorithm gets a (1-ε)(1-1/e) guarantee in O(nP ln(1/ε)) queries, removing a factor P from the previous O(nP²) analysis, and the proof technique—tracking an idealized stochastic-greedy process inside PO—is a nice departure from greedy-emulation arguments. The induction is coherent and the Chernoff step for PO checks out. This part is publishable. Second, the headline BPO result, Theorem 2, is not established. In the appendix's final Chernoff step, the paper bounds P(ΣY_i < H_κ) by P(ΣY_i < Tp/(2M)) using T ≥ 2ne ln(1/ε)M/p. That containment requires H_κ ≤ Tp/(2M), i.e., κ/ξ^q ≤ n. But Equation (2) gives ξ^q P < κ, hence κ/ξ^q > P. For P close to n (or n+1), that exceeds n; the inequality is backwards. Concretely, P = n = 1000, κ = 999, ξ = 1/2, ε = 0.01 gives H_κ ≈ 25,011 and Tp/(2M) ≈ 12,518; the actual binomial tail is around 0.43, not ≤ ε. The theorem explicitly allows this regime. Theorem 3 is also not proven—the main proof is left to the reader—so its O(n ln(1/ε)) claim is unsupported as written. The empirical section has labeling inconsistencies (plots say BPO where the text says κ-BPO), but that is minor compared to the analytic gap.\n\nCredit where due: the paper is clearly written, the related work is fair, and the biased selection idea is worth further attention. But the load-bearing guarantee of the new algorithm is unproven. I'd send this to a serious referee, with the expectation of major revision: fix the Chernoff step (either restrict the theorem to a regime where the inequality holds, or find a different argument) and actually write out Theorem 3. If those repairs succeed, the paper becomes solid. As it stands, I would not rely on the BPO/κ-BPO claims.\n\nThis is a paper for researchers in evolutionary computation and submodular optimization. The PO result deserves citation; the BPO result needs a corrected analysis.","headline":"Theorem 1's O(nP) PO analysis is a real step forward, but the paper's BPO guarantee in Theorem 2 rests on a reversed Chernoff inequality and is not proven as stated.","tokens_in":18601,"tokens_out":5131,"would_cite":true,"duration_ms":47375,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A biased Pareto evolutionary algorithm matches stochastic greedy's O(n ln(1/ε)) query complexity for monotone submodular maximization while keeping a pool of solutions.","keywords":["monotone submodular maximization","Pareto optimization","evolutionary algorithm","cardinality constraint","query complexity","approximation ratio","stochastic greedy","Chernoff bound"],"falsifier":"Take ξ=1/2, κ=P−1, and large n; compute Tp/M with T as in Theorem 2 and compare it with H_qκ for the corresponding q. The claimed Chernoff step requires Tp/M ≥ 2H_qκ, but the asymptotic values are ≈2e ln(1/ε)n versus ≈2e ln(1/ε)P, which for P≈n makes the required number of successes equal to—not below half of—the mean. That calculation alone refutes the proof's concentration argument; an experiment counting actual iterations until κ-BPO reaches the promised ratio would show whether the theorem itself survives.","tokens_in":17566,"feed_emoji":"🧬","tokens_out":8528,"duration_ms":72464,"temperature":0.7,"pith_summary":"Monotone submodular maximization asks for a set of at most κ elements maximizing a monotone, submodular value oracle f. This paper proves that the Pareto optimization algorithm—an evolutionary method that keeps a pool of mutually non-dominating sets, trading off f-value against cardinality—reaches an expected (1−ε)(1−1/e) approximation for every cardinality constraint κ<P in O(nP ln(1/ε)) queries of f, removing a factor of P from the previous analysis. It then introduces a biased selection mechanism, BPO, and proves the same type of guarantee, (1−ε)(1−1/e−ε), for all κ<P in O(n ln(P) ln(1/ε)) queries, and a version specialized to a single κ in O(n ln(1/ε)) queries, matching the query complexity of stochastic greedy. The significance is that evolutionary Pareto search, previously thought to need cubic time in n, can be as fast in query count as the best randomized greedy methods while retaining a population of solutions. Experiments on data summarization with submodular and weakly submodular objectives support the predicted crossover points.","feed_headline":"Pareto search matches stochastic greedy's query speed","feed_subtitle":"New analysis cuts the query bound from cubic to near-linear; biased variant runs in O(n ln(1/ε)).","key_machinery":"The load-bearing device is a cardinality counter ω that tracks the largest f-value available among pool sets of size at most ω. Each time the pool's best set at that cardinality is selected and mutation flips exactly one element of the optimal set A*, ω increments; the proof lower-bounds the expected best f-value at the tracked cardinality by (1−(1−1/|A*|)^ω′)f(A*), which at ω=κ gives the (1−1/e) factor. For the biased algorithms, a family of counters β_j with geometrically spaced thresholds H_j=e ln(1/ε)/ξ^j approximately tracks ω without knowing κ, and each counter increment is an i.i.d. Bernoulli success with probability p/⌈ln(P)/ln(1/ξ)⌉ (or p for the single-κ version). Chernoff's bound converts the expected success count into a high-probability statement that the tracked cardinality reaches κ within T iterations, and the law of total expectation converts that into the approximation guarantee.","core_discovery":"The central discovery is that the slow part of earlier Pareto-optimization analyses was not the algorithm but the lens: waiting for the standard greedy algorithm to appear inside the random mutation process costs O($nP^{2}$) queries, whereas the same process probabilistically performs a random version of greedy—pick uniformly random elements of the optimal set, allowing repeats—which already has the (1−1/e) guarantee. Analyzing the expected time for this random-greedy process to reach κ cardinality inside PO yields O(nP ln(1/ε)) queries in expectation. Replacing uniform pool selection with a biased selector that concentrates mutations on the current best set at a tracked cardinality gives BPO and κ-BPO, whose successes are Bernoulli trials with probability p/M or p, respectively; Chernoff bounds then give the near-linear and linear query counts. The paper's claims include the explicit approximation ratios (1−ε)(1−1/e) for PO and (1−ε)(1−1/e−ε) for BPO and κ-BPO, for every κ<P (or a given κ), in expectation over the algorithm's randomness.","pith_inferences":["The random-greedy-within-mutation argument is structurally independent of the exact value of the cardinality constraint, which suggests the same O(nP ln(1/ε)) style bound could carry to other Pareto formulations, such as submodular cover or general cost constraints, whenever a suitable tracking variable exists.","The geometric threshold spacing in BPO effectively guesses κ up to a factor of ξ; one could test whether a different spacing, such as doubling instead of 1/ξ, yields the same query bound with fewer counters.","The proof's success-count condition implies a testable prediction: as κ approaches P, the constant in the O(n ln(1/ε)) bound for κ-BPO should degrade unless the threshold condition is repaired; running BPO with κ=P−1 and ξ=1/2 would reveal whether the observed query count stays linear or grows with P."],"forward_implications":["For any instance SM(f,κ) with κ<P, PO now comes with a deterministic-time query bound O(nP ln(1/ε)) for an expected (1−ε)(1−1/e) approximation, so the previous O(nP^2) wall is removed.","BPO provides the same style of guarantee for all cardinality constraints simultaneously in O(n ln(P) ln(1/ε)) queries, so one run yields usable solutions for every κ<P.","κ-BPO matches stochastic greedy's O(n ln(1/ε)) query complexity for a fixed cardinality κ, while keeping the evolutionary pool property that allows early termination and continued improvement.","The stated results transfer to monotone γ-weakly submodular objectives with the 1−1/e factor replaced by 1−1/e^γ, per the paper's extension.","If the guarantees hold, evolutionary Pareto methods are no longer dominated by greedy methods in query complexity for monotone submodular maximization."],"supporting_citations":[{"why":"Introduces the Pareto optimization algorithm for submodular maximization and the O(nP^2) analysis that this paper improves.","marker":"[Friedrich and Neumann, 2014]"},{"why":"Defines stochastic greedy, the O(n ln(1/ε))-query baseline that BPO and κ-BPO match, and whose solution values are used as empirical benchmarks.","marker":"[Mirzasoleiman et al., 2015]"},{"why":"Establishes the (1−1/e) approximation guarantee and the O(nκ)-query standard greedy baseline for monotone submodular maximization.","marker":"[Nemhauser and Wolsey, 1978]"},{"why":"Analyzes PO for subset selection with P=2κ and provides earlier PO query bounds for that special case.","marker":"[Qian et al., 2015b]"},{"why":"Defines γ-weak submodularity, the generalization to which the paper's theorems extend.","marker":"[Das and Kempe, 2011]"}],"fun_headline_variants":["Pareto search hits near-linear query time","Biased evolution reduces query count for submodular max","Faster guarantees from evolutionary algorithms","From cubic to near-linear: submodular gets faster","Evolutionary algorithm matches greedy with fewer queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise of the BPO and κ-BPO query bounds is that the biased counter increments form independent Bernoulli trials whose expected total is at least twice the number of increments needed to push the tracked cardinality to κ; if that mean-to-threshold condition fails, the Chernoff step that supplies the high-probability event does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Pareto search hits near-linear query time","Biased evolution reduces query count for submodular max","Faster guarantees from evolutionary algorithms","From cubic to near-linear: submodular gets faster","Evolutionary algorithm matches greedy with fewer queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000278,"raw_usage":{"total_tokens":1694,"prompt_tokens":1024,"completion_tokens":670,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":640,"completion_tokens_details":{"reasoning_tokens":599}},"tokens_in":640,"tokens_out":670,"duration_ms":7020,"temperature":1.0,"reasoning_tokens":599,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:21:53.019014+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take ξ=1/2, κ=P−1, and large n; compute Tp/M with T as in Theorem 2 and compare it with H_qκ for the corresponding q. The claimed Chernoff step requires Tp/M ≥ 2H_qκ, but the asymptotic values are ≈2e ln(1/ε)n versus ≈2e ln(1/ε)P, which for P≈n makes the required number of successes equal to—not below half of—the mean. That calculation alone refutes the proof's concentration argument; an experiment counting actual iterations until κ-BPO reaches the promised ratio would show whether the theorem itself survives.","supporting_citations":[{"cited_title":"Maximizing submodular functions under ma- troid constraints by evolutionary algorithms","cited_arxiv_id":null,"evidence_quote":"Introduces the Pareto optimization algorithm for submodular maximization and the O(nP^2) analysis that this paper improves."},{"cited_title":"Lazier Than Lazy Greedy","cited_arxiv_id":null,"evidence_quote":"Defines stochastic greedy, the O(n ln(1/ε))-query baseline that BPO and κ-BPO match, and whose solution values are used as empirical benchmarks."},{"cited_title":"Best Algorithms for Approximating the Maxi- mum of a Submodular Set Function","cited_arxiv_id":null,"evidence_quote":"Establishes the (1−1/e) approximation guarantee and the O(nκ)-query standard greedy baseline for monotone submodular maximization."},{"cited_title":"Submodular meets Spectral: Greedy Algorithms for Sub- set Selection, Sparse Approximation and Dictionary Se- lection","cited_arxiv_id":null,"evidence_quote":"Defines γ-weak submodularity, the generalization to which the paper's theorems extend."}],"review_version":1}