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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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.
- [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.
- [Section 4] There is a minor typo in 'over 10 trails'; it should read 'over 10 trials'.
Circularity Check
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
free parameters (2)
- epsilon (ϵ) =
1/2 + (k-1)/(N-k) for the 1/4 bound; 0.01 or 1/2 in experiments
- delta (δ) =
any value in (0, epsilon); 0.1 in experiments
assumptions (5)
- domain assumption f is non-negative and submodular
- domain assumption Value oracle model: f(.) is a black-box that returns f(S) for any S
- standard math Lemma 2 (Buchbinder et al. 2014, Lemma 2.2)
- domain assumption The algorithm may add dummy elements with identically zero marginal gain
- domain assumption k >= 2
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
Reference graph
Works this paper leans on
-
[1]
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
work page 2014
-
[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
work page 2018
-
[3]
Bertsimas, D., King, A., and Mazumder, R. (2016). Best subset selection via a modern optimization lens.Ann. Statist., 44(2):813–852
work page 2016
-
[4]
Buchbinder, N. and Feldman, M. (2018). Deterministic algorithms for submodular maximization problems.ACM Trans. Algorithms, 14(3):32:1–32:20
work page 2018
-
[5]
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
work page 2014
-
[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
arXiv 2017
-
[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
work page 2019
-
[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
work page 2019
Show all 34 references
-
[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
2017
-
[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
2011
-
[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
2011
-
[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
2010
-
[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
2019
-
[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
2018
-
[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
2017
-
[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
2012
-
[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
2019
-
[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
2020
-
[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
2017
-
[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
2008
-
[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
2019
-
[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
2010
-
[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
2007
-
[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...
2010
-
[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
1978
-
[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
2016
-
[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
2015
-
[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
1978
-
[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
2017
-
[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
2014
-
[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...
2018
-
[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
2015
-
[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...
2017
-
[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...
2014
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.