{"id":"d38b4fc0-b538-425c-a23b-607cbc879f9e","arxiv_id":"1908.06242","paper_version":6,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Stochastic Greedy with a rejection rule for non-positive marginal gains achieves an expected 1/4-approximation for non-monotone submodular maximization under a cardinality constraint in linear oracle queries.","lead":"A small modification of the popular Stochastic Greedy algorithm provably gives a constant-factor approximation in expectation for non-monotone submodular maximization with a cardinality constraint, using only O(n) value-oracle queries. This makes fast greedy selection reliable for large-scale tasks such as sensor placement, summarization, and feature selection where objective functions need not be monotone.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof is sound and the flagged non-negativity issue is covered by the standing assumption.","rationale":"The reader's weak-assumption analysis flags the omitted non-negativity condition in Lemma 2, and that is indeed a real statement-level error: Lemma 2 as printed is false for submodular functions that can take negative values, such as g(S)=−|S|. However, the paper's standing assumption is that f is non-negative, so the specific g used in Lemma 3, g(A)=f(A∪A*), is non-negative and Lemma 2 applies. Thus the flagged issue does not threaten the central claim. I also checked the other key steps: Lemma 1's non-monotone proof relies on clipping and the fact that Algorithm 1 only adds elements with positive marginal gain, which makes the per-iteration increment non-negative; the probability bound in the proof is standard and correct. Lemma 3's product bound on the probability that an element remains outside the current solution is valid even under dependence, and the subsequent application of Lemma 2 is legitimate. Lemma 4 is supported by Lemmas 5 and 6, both of which I verified. The modified SG algorithm is exactly equivalent to running original SG on the augmented ground set V, because the dummy elements have zero marginal gains and the hypergeometric sampling of real elements reproduces the distribution of real elements in the augmented uniform sample. The oracle-complexity bounds follow from the hypergeometric mean bound and the choice of N. The only other concern is a logical-presentation gap in Theorem 2: the statement says that setting ε=1/2+(k−1)/(N−k) yields 1/4(1−δ)^2, but that conclusion does not follow from the displayed general bound (ε−δ)(1−ε); it follows from the stronger pre-theorem bound (ε−2(k−1)/(N−k))(1−ε). Since the stronger bound is proven in the text, the actual result stands. These are minor issues that do not warrant changing the reader's ACCEPT verdict.","tokens_in":14125,"tokens_out":31760,"duration_ms":272424,"concrete_test":"Independently re-derive the 1/4(1−δ)^2 bound from (ε−2(k−1)/(N−k))(1−ε) with ε=1/2+(k−1)/(N−k) and N=max{n,k+ceil((2k−1)/δ)}, verifying it yields the claimed bound for all k≥2, δ∈(0,1), n≥k; this isolates the presentation gap in Theorem 2 without touching the algorithm's correctness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the main proof chain, I find no load-bearing flaw in the central claim that modified SG achieves E[f(A)] ≥ 1/4(1−δ)^2 f(A*) with O(n) expected oracle queries. Lemma 1's non-monotone version is valid: the algorithm rejects non-positive marginal gains, so increments remain non-negative, and the clipping argument in Appendix A correctly handles negative marginals. Lemma 3's probability bound is correct: the product lower bound on an element remaining outside uses only the worst-case remaining-set size, and the application of Lemma 2 is legitimate because f is non-negative, so g(·)=f(·∪A*) is non-negative as required. Lemma 4's inequalities (Lemmas 5 and 6) check out. The only real issues are presentation-level: Lemma 2 is stated without the non-negativity hypothesis, which is false as stated but harmless here; and Theorem 2's 'if we set ε' line derives from the stronger pre-theorem bound (ε−2(k−1)/(N−k))(1−ε), not from the displayed (ε−δ)(1−ε). Neither affects the correctness of the algorithm or its guarantee.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the stochastic greedy algorithm (SG) for maximizing a non-negative, not necessarily monotone submodular function under a cardinality constraint k. It proves that SG, with a slight modification that rejects non-positive marginal gains, yields a constant-factor approximation in expectation under n ≥ 3k: Theorem 1 gives E[f(A)] ≥ (ε − 2(k−1)/(n−k))(1−ε) f(A*), which becomes ≈ 1/4 when ε = 1/2 + (k−1)/(n−k). To remove the n ≥ 3k assumption, the author introduces modified SG (Algorithm 2), which simulates adding dummy elements through hypergeometric sampling, achieving E[f(A)] ≥ (ε−δ)(1−ε) f(A*) with O(n) expected oracle queries; with a suitable ε this is a 1/4(1−δ)^2 approximation. Experiments on synthetic cut functions and mutual information instances compare SG-type algorithms with existing methods.","tokens_in":14319,"tokens_out":8719,"duration_ms":71998,"significance":"If correct, this is a significant contribution: it extends the linear-time stochastic greedy algorithm to the non-monotone regime, providing the first constant-factor approximation with O(n) expected oracle queries for this problem, improving on the O(n/ε^2 log(1/ε)) random sampling algorithm of Buchbinder et al. and the O(n/ε log(n/ε)) deterministic algorithm of Kuhnle. The proof is self-contained, with detailed appendix justifications; Lemma 1's clipping argument for negative marginal gains is a neat and correct adaptation. The guarantee is in expectation, which the paper explicitly acknowledges, and the experiments support the practical efficiency claims. The central mathematical argument is sound.","major_comments":[],"minor_comments":[{"comment":"The statement of Lemma 2 omits the non-negativity hypothesis on g. As stated, the lemma is false (e.g., g(S) = −|S|). The application in Lemma 3 is safe because f is non-negative, so g(·) = f(· ∪ A*) is non-negative; nevertheless, please add the non-negativity condition to the lemma statement and note that the hypothesis is required for the proof.","section":"Section 3.1, Lemma 2"},{"comment":"The final sentence of Theorem 2 claims that setting ε = 1/2 + (k−1)/(N−k) yields E[f(A)] ≥ 1/4(1−δ)^2 f(A*). This conclusion does not follow from the displayed bound (ε−δ)(1−ε) f(A*); it follows from the stronger intermediate bound (ε−2(k−1)/(N−k))(1−ε) f(A*) derived in the dummy-element argument. Please clarify the derivation so that the reader does not attempt to substitute the displayed theorem inequality.","section":"Theorem 2"},{"comment":"The sentence 'We can also easily prove N≥3k by induction' is confusing; N ≥ 3k follows directly from N ≥ k + 2(k−1)/δ and δ ∈ (0,1), with no induction needed. Please rephrase or remove.","section":"Section 3.2"},{"comment":"The notation H(⌈s⌉, |V\\Ai−1|, |V\\Ai−1|) for the hypergeometric distribution is unclear because the second and third arguments appear identical. Please specify the population size and the number of target elements explicitly (e.g., population N−|Ai−1| and targets |V\\Ai−1|) so that the oracle-complexity calculation is easy to follow.","section":"Algorithm 2 and surrounding text"},{"comment":"There is a minor typo in 'over 10 trails'; it should read 'over 10 trials'.","section":"Section 4"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper gives the first constant-factor approximation guarantee for the stochastic greedy algorithm on non-monotone submodular functions with a cardinality constraint, and it does so with O(n) oracle queries. The central theorem is right, the proof is mostly clean, and the few presentation slips don't shake the main result.\n\nWhat's new: Mirzasoleiman et al. analyzed SG only for monotone objectives. Sakaue shows that if you let SG reject non-positive marginal gains and set the sampling parameter appropriately, you get expected 1/4(1−δ)^2 approximation in linear time. The constant is not the best known—Buchbinder et al. achieve 1/e−ε—but the oracle complexity is much lower, and the paper also gives a modified SG with random sample size that removes the need for n≫k. The proof idea is a nice extension of Buchbinder et al.'s random-greedy analysis: Lemma 1 is adapted by clipping negative marginals, and Lemma 2 controls the drift term. The induction in Theorem 1 checks out.\n\nSoft spots. Lemma 2 is stated without the non-negativity condition that its proof requires; as stated it's false (take g(S)=−|S|). The application is safe because f is non-negative, so g(A)=f(A∪A*) is non-negative. Worth a footnote in revision, not a flaw. In Theorem 2, the line \"if we set ϵ=...\" doesn't follow from the displayed bound (ε−δ)(1−ε) unless you read it as the earlier stronger bound; again cosmetic. The experiments are not the main point—they compare against an RS implementation with ε=0.3, which gives a weak guarantee, so the comparison is a little favorable to SG—but they do show large practical query savings. No code is released; that's minor for a theory paper.\n\nWho should read it: anyone working on fast submodular maximization, especially non-monotone objectives. It fills a clear gap in the literature and the main theorem is likely to be cited. The paper deserves a serious referee; I'd accept it with minor revisions.","headline":"Gives the first constant-factor guarantee for stochastic greedy on non-monotone submodular maximization, with O(n) queries; the proof is sound and the presentation slips are minor.","tokens_in":14862,"tokens_out":2133,"would_cite":true,"duration_ms":18145,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68W25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stochastic greedy achieves an almost 1/4-approximation in linear time even for non-monotone submodular objectives.","keywords":["stochastic greedy","submodular maximization","non-monotone submodular functions","cardinality constraint","approximation algorithm","oracle complexity","randomized algorithm","linear-time algorithm"],"falsifier":"Enumerate all subsets of a small non-negative submodular instance (say $n=6$, $k=2$, a cut function) to compute $f(A^*)$, then run Algorithm 2 with $\\epsilon=0.55$ and $\\delta=0.1$ many times; if the average output falls below $0.2025\\, f(A^*)$, the expected-approximation bound is false. Separately, on $g(S)=-|S|$ the random-subset inequality fails, showing that dropping non-negativity breaks the proof.","tokens_in":13904,"feed_emoji":"🎲","tokens_out":14106,"duration_ms":115921,"temperature":0.7,"pith_summary":"This paper asks whether stochastic greedy can keep its speed and its guarantee when the objective stops being monotone. It answers yes: after a small modification, the algorithm achieves an almost $1/4$-approximation in expectation with linear oracle complexity for non-negative submodular maximization under a cardinality constraint. This matters because non-monotone submodular objectives arise in sensor placement, document summarization, feature selection, and recommendation, while existing constant-factor algorithms for them need far more oracle queries. The proof balances two opposing inequalities, and experiments show the modified algorithm runs much faster than prior methods while matching their objective values.","feed_headline":"Stochastic greedy now has a linear-time 1/4 guarantee","feed_subtitle":"A tweaked sample size keeps oracle calls at O(n) while holding an almost 1/4-approximation for non-monotone objectives.","key_machinery":"The carrying object is the stochastic greedy rule with a randomized sample size: Algorithm 2 draws $r$ from the hypergeometric distribution $H(\\lceil s\\rceil, |V\\setminus A_{i-1}|, N-|A_{i-1}|)$ and picks the best of $r$ random remaining elements, mimicking stochastic greedy run on an augmented ground set of size $N = \\max\\{n, k+\\lceil(2k-1)/\\delta\\rceil\\}$ whose dummy elements have zero marginal gain. Two inequalities work against each other. Lemma 1, adapted from the original stochastic greedy paper, lower-bounds each round's expected gain by $(1-\\epsilon)/k$ times $E[f_{A_{i-1}}(A^*)]$ using the rejection of non-positive marginal gains, so smaller $\\epsilon$ is better. Lemma 3, via a random-subset lemma applied to $g(A)=f(A\\cup A^*)$, lower-bounds $E[f(A^*\\cup A_i)]$ by a product factor that shrinks as $\\epsilon$ decreases, so larger $\\epsilon$ is better. Balancing the two at $\\epsilon\\approx 1/2$ yields the $1/4$ constant, while the dummy ground set absorbs the $2(k-1)/(N-k)$ slack and removes the $n\\geq 3k$ condition.","core_discovery":"The paper establishes that stochastic greedy, originally proved only for monotone objectives, can be modified to give a constant-factor approximation for all non-negative submodular objectives under a cardinality constraint. The precise claim is Theorem 1: when $n\\geq 3k$ and $\\epsilon\\in[1/e,1)$, Algorithm 1 returns a set $A$ with $E[f(A)] \\geq (\\epsilon - 2(k-1)/(n-k))(1-\\epsilon) f(A^*)$, and setting $\\epsilon = 1/2+(k-1)/(n-k)$ gives $\\frac{1}{4}(1-2(k-1)/(n-k))^2 f(A^*)$. Theorem 2 removes the $n\\geq 3k$ condition by randomizing the per-round sample size: Algorithm 2 achieves $E[f(A)] \\geq (\\epsilon-\\delta)(1-\\epsilon)f(A^*)$, and at $\\epsilon=1/2+(k-1)/(N-k)$ this is $\\frac{1}{4}(1-\\delta)^2 f(A^*)$ with expected oracle complexity at most $n\\ln 2 + n\\delta k/(k-1)$ and worst-case at most $\\max\\{n, k+2k/\\delta\\}\\cdot\\ln 2 + k$. The ratio holds only in expectation, so a single run can be arbitrarily bad.","pith_inferences":["The hypergeometric sample-size trick is a generic device: any stochastic greedy variant whose analysis needs a larger effective ground set can simulate that ground set by drawing the sample count, without paying for dummy evaluations.","A high-probability analogue for non-monotone objectives is a plausible next step: concentration of the hypergeometric sample counts could turn the expectation bound into a $1-\\eta$ confidence bound, at the cost of a logarithmic factor in the query count.","The $\\epsilon\\approx 1/2$ balance between marginal-gain loss and union-coverage loss suggests that non-uniform sampling over the remaining elements could shift the trade-off and perhaps lift the constant above $1/4$; the paper does not explore that direction.","The rejection step for non-positive marginal gains is what makes the marginal-gain lemma survive without monotonicity, so for functions with bounded negative curvature a modified rejection threshold might preserve a constant factor, but that extension is not in the paper."],"forward_implications":["For every non-negative submodular objective, a near-$1/4$ approximation in expectation becomes available with $O(n)$ oracle queries, so large instances of sensor placement and summarization can use the same fast routine as in the monotone case.","The expected oracle complexity of modified stochastic greedy is at most $n\\ln 2 + n\\delta k/(k-1)$, and the worst case is at most $\\max\\{n, k+2k/\\delta\\}\\ln 2 + k$, which is $O(n/\\delta)$; the paper's comparison puts this below the query counts of prior constant-factor algorithms.","For monotone objectives the modified algorithm still inherits the classical $(1-1/e-\\epsilon)$-guarantee, so the modification does not sacrifice the known monotone regime.","Because the guarantee is in expectation, practitioners who need a high-probability output should average multiple runs or accept that some runs can be arbitrarily poor.","The randomized sample size implements the dummy-element construction without ever materializing dummy elements, which is why the worst-case oracle count stays linear in $n$ up to the $1/\\delta$ factor."],"supporting_citations":[{"why":"It defines stochastic greedy, supplies the monotone-case guarantee, and provides the marginal-gain lemma that the non-monotone proof extends.","marker":"Mirzasoleiman et al., 2015"},{"why":"It supplies the random-subset inequality used to control how much of the optimum remains covered after each round.","marker":"Buchbinder et al., 2014"},{"why":"It provides the random sampling algorithm whose oracle complexity is the baseline the paper must beat to claim the fewest queries.","marker":"Buchbinder et al., 2017"},{"why":"It provides the deterministic 1/4-epsilon algorithm with O(n/epsilon ln(n/epsilon)) queries, the closest constant-factor competitor used in the comparison and experiments.","marker":"Kuhnle, 2019"}],"fun_headline_variants":["Modified stochastic greedy achieves ~1/4 guarantee in linear time","Stochastic greedy now guarantees ~1/4 for non-monotone objectives in O(n)","Non-monotone submodular? Modified greedy gives near-1/4 in linear time","Fast constant-factor guarantee for non-monotone submodular maximization","Stochastic greedy meets non-monotone: near 1/4 approximation in O(n)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the objective $f$ is non-negative; if $f$ can take negative values, the random-subset inequality $E[g(A(p))] \\geq (1-p)g(\\emptyset)$ used to control $E[f(A^*\\cup A_i)]$ can fail, and the whole $1/4$ approximation chain collapses.","fun_headline_variants_meta":{"raw":{"variants":["Modified stochastic greedy achieves ~1/4 guarantee in linear time","Stochastic greedy now guarantees ~1/4 for non-monotone objectives in O(n)","Non-monotone submodular? Modified greedy gives near-1/4 in linear time","Fast constant-factor guarantee for non-monotone submodular maximization","Stochastic greedy meets non-monotone: near 1/4 approximation in O(n)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000821,"raw_usage":{"total_tokens":3624,"prompt_tokens":1010,"completion_tokens":2614,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":2507}},"tokens_in":626,"tokens_out":2614,"duration_ms":16620,"temperature":1.0,"reasoning_tokens":2507,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:54:08.097419+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all subsets of a small non-negative submodular instance (say $n=6$, $k=2$, a cut function) to compute $f(A^*)$, then run Algorithm 2 with $\\epsilon=0.55$ and $\\delta=0.1$ many times; if the average output falls below $0.2025\\, f(A^*)$, the expected-approximation bound is false. Separately, on $g(S)=-|S|$ the random-subset inequality fails, showing that dropping non-negativity breaks the proof.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines stochastic greedy, supplies the monotone-case guarantee, and provides the marginal-gain lemma that the non-monotone proof extends."},{"cited_title":"S., and Schwartz, R","cited_arxiv_id":null,"evidence_quote":"It supplies the random-subset inequality used to control how much of the optimum remains covered after each round."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the deterministic 1/4-epsilon algorithm with O(n/epsilon ln(n/epsilon)) queries, the closest constant-factor competitor used in the comparison and experiments."}],"review_version":1}