Pith. sign in

REVIEW 5 minor 34 references

Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint

T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read Stochastic greedy achieves an almost 1/4-approximation in linear time even for non-monotone submodular objectives.

desk verdict 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. read the letter →

arxiv 1908.06242 v6 pith:DMJEE26P submitted 2019-08-17 cs.DS

classification cs.DS MSC 68W2068W2590C27
keywords stochasticgreedysubmodularmaximizationnon-monotonefunctionscardinalityconstraintapproximationalgorithmoraclecomplexityrandomizedlinear-time
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

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.

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.

minor comments (5)
  1. [Section 3.1, Lemma 2] 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.
  2. [Theorem 2] 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.
  3. [Section 3.2] 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.
  4. [Algorithm 2 and surrounding text] 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.
  5. [Section 4] There is a minor typo in 'over 10 trails'; it should read 'over 10 trials'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the approximation guarantee is derived from external lemmas and the paper's own sampling analysis, with no fitted inputs or self-citations.

full rationale

The paper's central claim is a theorem proved from definitions and externally cited lemmas, not from a fitted parameter or a self-referential chain. Lemma 1 extends Mirzasoleiman et al.'s monotone analysis to non-monotone functions by clipping marginal gains, and its proof is self-contained in Appendix A. Lemma 3 applies Buchbinder et al. (2014, Lemma 2.2) as a black box to g(A)=f(A∪A*), with the probability bound derived directly from the random sampling process; the application is legitimate under the standing assumption that f is non-negative, so g is non-negative as required. Lemma 4 is an algebraic inequality proved in Appendix B. Theorem 1 combines these lemmas, and Section 3.2 obtains modified SG by a dummy-element argument with an explicit hypergeometric sampling procedure; epsilon and delta are user-chosen inputs, not fitted to data, and the oracle complexity bounds follow from the sampling distribution. The paper contains no self-citations that are load-bearing, and no prediction is equivalent by construction to an input. The one flagged presentation issue, that Lemma 2 is stated without its non-negativity hypothesis, does not create circularity because the paper explicitly assumes all set functions are non-negative throughout; it is a correctness-of-statement concern, not a circularity concern. The appended remark that eliminating delta is left as an open problem is an honest limitation, not a circular step. The derivation is therefore self-contained against external benchmarks and receives a score of 0.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim depends on f being non-negative and submodular, the value-oracle model, and the cited Lemma 2. Parameters epsilon and delta are user-specified algorithm inputs; no constants are fitted to data and no new entities are introduced.

free parameters (2)
  • epsilon (ϵ) = 1/2 + (k-1)/(N-k) for the 1/4 bound; 0.01 or 1/2 in experiments
    User-specified sampling-rate parameter for Algorithm 1 and 2. The theorem requires epsilon in [1/e, 1); the choice 1/2 balances Lemmas 1 and 3. It is an algorithm input, not fitted to data.
  • delta (δ) = any value in (0, epsilon); 0.1 in experiments
    User-specified parameter in modified SG controlling the trade-off between the approximation factor 1/4(1-delta)^2 and worst-case oracle complexity O(1/delta). It is chosen by hand, not fitted.
assumptions (5)
  • domain assumption f is non-negative and submodular
    Problem (1) and all theorems assume non-negative submodular f; Lemma 2's application requires non-negativity of g(A) = f(A union A*).
  • domain assumption Value oracle model: f(.) is a black-box that returns f(S) for any S
    Oracle complexity is measured in number of f evaluations; this is the standard model.
  • standard math Lemma 2 (Buchbinder et al. 2014, Lemma 2.2)
    Used to lower-bound E[f(A* union A_i)] from the per-element inclusion probability bound; stated without proof and without the non-negativity condition, though the application uses non-negative g.
  • domain assumption The algorithm may add dummy elements with identically zero marginal gain
    Used in Section 3.2 to remove the n >= 3k assumption; dummy elements do not affect f values and add no real selected elements.
  • domain assumption k >= 2
    Assumption 1; k = 1 is handled trivially in the text.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint." pith.science (2026). https://pith.science/paper/DMJEE26P

@misc{pith2026190806242,
  author       = {Pith},
  title        = {Pith review of: Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DMJEE26P}},
  note         = {Machine review of arXiv:1908.06242}
}
abstract

Submodular maximization with a cardinality constraint can model various problems, and those problems are often very large in practice. For the case where objective functions are monotone, many fast approximation algorithms have been developed. The stochastic greedy algorithm (SG) is one such algorithm, which is widely used thanks to its simplicity, efficiency, and high empirical performance. However, its approximation guarantee has been proved only for monotone objective functions. When it comes to non-monotone objective functions, existing approximation algorithms are inefficient relative to the fast algorithms developed for the case of monotone objectives. In this paper, we prove that SG (with slight modification) can achieve almost $1/4$-approximation guarantees in expectation in linear time even if objective functions are non-monotone. Our result provides a constant-factor approximation algorithm with the fewest oracle queries for non-monotone submodular maximization with a cardinality constraint. Experiments validate the performance of (modified) SG.

Figures

Figures reproduced from arXiv: 1908.06242 by the authors.

Figure 1
Figure 1. MSG Performance with Various δ Values. • Random sampling (RS) (Buchbinder et al., 2017): A randomized (1/e − )-approximation algorithm with O [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Comparison of Algorithms with Synthetic Cut-function Maximization Instances. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Comparison of Algorithms with Real-world Mutual Information Maximization Instances. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 33 canonical work pages

  1. [1]

    and Vondrák, J

    Badanidiyuru, A. and Vondrák, J. (2014). Fast algorithms for maximizing submodular functions. InProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1497–1514. SIAM

  2. [2]

    Balkanski, E., Breuer, A., and Singer, Y. (2018). Non-monotone submodular maximization in exponentially fewer iterations. In Advances in Neural Information Processing Systems 31, pages 2353–2364. Curran Associates, Inc

  3. [3]

    Bertsimas, D., King, A., and Mazumder, R. (2016). Best subset selection via a modern optimization lens.Ann. Statist., 44(2):813–852

  4. [4]

    and Feldman, M

    Buchbinder, N. and Feldman, M. (2018). Deterministic algorithms for submodular maximization problems.ACM Trans. Algorithms, 14(3):32:1–32:20

  5. [5]

    S., and Schwartz, R

    Buchbinder, N., Feldman, M., Naor, J. S., and Schwartz, R. (2014). Submodular maximization with cardinality constraints. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1433–1452. SIAM

  6. [6]

    Buchbinder, N., Feldman, M., and Schwartz, R. (2017). Comparing apples and oranges: Query trade-off in submodular maximization. Math. Oper. Res., 42(2):308–329. de Veciana, G., Hashemi, A., and Vikalo, H. (2019). Stochastic-greedy++: Closing the optimality gap in exact weak submodular maximization.arXiv preprint arXiv:1907.09064

  7. [7]

    Ene, A., Nguyen, H., and Vladu, A. (2019). Submodular maximization with matroid and packing constraints in parallel. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 90–101. ACM

  8. [8]

    Fahrbach, M., Mirrokni, V., and Zadimoghaddam, M. (2019). Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. InProceedings of the 36th International Conference on Machine Learning, volume 97, pages 1833–1842. PMLR

Show all 34 references
  1. [9]

    Feldman, M., Harshaw, C., and Karbasi, A. (2017). Greed is good: Near-optimal submodular maximization via greedy optimization. In Proceedings of the 2017 Conference on Learning Theory, volume 65, pages 758–784. PMLR. 10

  2. [10]

    Feldman, M., Naor, J., and Schwartz, R. (2011). A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 570–579

  3. [11]

    Gharan, S. O. and Vondrák, J. (2011). Submodular maximization by simulated annealing. InProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1098–1116. SIAM

  4. [12]

    Gupta, A., Roth, A., Schoenebeck, G., and Talwar, K. (2010). Constrained non-monotone submodular maximization: Offline and secretary algorithms. InProceedings of the 6th International Conference on Internet and Network Economics, pages 246–257. Springer-Verlag

  5. [13]

    Harshaw, C., Feldman, M., Ward, J., and Karbasi, A. (2019). Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. InProceedings of the 36th International Conference on Machine Learning, volume 97, pages 2634–2643. PMLR

  6. [14]

    Hashemi, A., Ghasemi, M., Vikalo, H., and Topcu, U. (2018). A randomized greedy algorithm for near-optimal sensor scheduling in large-scale sensor networks. In2018 Annual American Control Conference, pages 1027–1032

  7. [15]

    and Singer, Y

    Hassidim, A. and Singer, Y. (2017). Robust guarantees of stochastic greedy algorithms. InProceedings of the 34th International Conference on Machine Learning, volume 70, pages 1424–1432. PMLR

  8. [16]

    and Bilmes, J

    Iyer, R. and Bilmes, J. (2012). Algorithms for approximate minimization of the difference between submodular functions, with applications. InProceedings of the 28th Conference on Uncertainty in Artificial Intelligence, pages 407–417. AUAI Press

  9. [17]

    and Bilmes, J

    Iyer, R. and Bilmes, J. (2019). A memoization framework for scaling submodular optimization to large scale problems. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, volume 89, pages 2340–2349. PMLR

  10. [18]

    Ji, S., Xu, D., Li, M., Wang, Y., and Zhang, D. (2020). Stochastic greedy algorithm is still good: Maximizing submodular + supermodular functions. InOptimization of Complex Systems: Theory, Models, Algorithms and Applications, pages 488–497. Springer International Publishing

  11. [19]

    R., Dimakis, A

    Khanna, R., Elenberg, E. R., Dimakis, A. G., Ghosh, J., and Negahban, S. (2017). On approximation guarantees for greedy low rank optimization. InProceedings of the 34th International Conference on Machine Learning, volume 70, pages 1837–1846. PMLR

  12. [20]

    Krause, A., Singh, A., and Guestrin, C. (2008). Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies.J. Mach. Learn. Res., 9(Feb):235–284

  13. [21]

    Kuhnle, A. (2019). Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In Advances in Neural Information Processing Systems 32, pages 2371–2381. Curran Associates, Inc

  14. [22]

    Lee, J., Mirrokni, V., Nagarajan, V., and Sviridenko, M. (2010). Maximizing nonmonotone submodular functions under matroid or knapsack constraints.SIAM J. Discrete. Math., 23(4):2053–2078

  15. [23]

    Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., and Glance, N. (2007). Cost-effective outbreak detection in networks. InProceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 420–429. ACM

  16. [24]

    and Bilmes, J

    Lin, H. and Bilmes, J. (2010). Multi-document summarization via budgeted maximization of submodular functions. In Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 912–92...

  17. [25]

    Minoux, M. (1978). Accelerated greedy algorithms for maximizing submodular set functions. InProceedings of the 8th IFIP Conference on Optimization Techniques, pages 234–243. Springer

  18. [26]

    Mirzasoleiman, B., Badanidiyuru, A., and Karbasi, A. (2016). Fast constrained submodular maximization: Personal- ized data summarization. InProceedings of The 33rd International Conference on Machine Learning, volume 48, pages 1358–1367. PMLR

  19. [27]

    Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., and Krause, A. (2015). Lazier than lazy greedy. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 1812–1818. AAAI Press. 11

  20. [28]

    L., Wolsey, L

    Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions-I. Math. Program., 14(1):265–294

  21. [29]

    S., La Cava, W., Orzechowski, P., Urbanowicz, R

    Olson, R. S., La Cava, W., Orzechowski, P., Urbanowicz, R. J., and Moore, J. H. (2017). PMLB: A large benchmark suite for machine learning evaluation and comparison.BioData Min., 10(1):36

  22. [30]

    E., Bradley, J

    Pan, X., Jegelka, S., Gonzalez, J. E., Bradley, J. K., and Jordan, M. I. (2014). Parallel double greedy submodular maximization. In Advances in Neural Information Processing Systems 27, pages 118–126. Curran Associates, Inc

  23. [31]

    Qian, C., Yu, Y., and Tang, K. (2018). Approximation guarantees of stochastic greedy algorithms for subset selection. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 1478–1484. International Joint Conferences on Artificial Intelligence...

  24. [32]

    Sharma, D., Kapoor, A., and Deshpande, A. (2015). On greedy maximization of entropy. InProceedings of the 32nd International Conference on Machine Learning, pages 1330–1338. PMLR

  25. [33]

    O., Jegelka, S., Rathod, V., and Murphy, K

    Song, H. O., Jegelka, S., Rathod, V., and Murphy, K. (2017). Deep metric learning via facility location. In Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, pages 2206–2214. Vondrák, J. (2013). Symmetry and approximability of submodular maxim...

  26. [34]

    Wei, K., Iyer, R., and Bilmes, J. (2014). Fast multi-stage submodular maximization. InProceedings of the 31st International Conference on Machine Learning, volume 32, pages 1494–1502. PMLR. 12 Appendix A PROOF OF LEMMA 1 We here prove the following lemma: Lemma 1 (cf. (Mirzaso...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.