- Rating
- 2
- Confidence
- 2
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies monotone submodular maximization under a cardinality constraint, measuring surrogate error in marginal gains rather than function values. For an error parameter , it establishes an optimal approximation ratio of with unlimited queries and derives the exact approximation ratio of predictive greedy. It further proves that this ratio is tight among deterministic algorithms under a specified query budget.
Critical strengths
The paper provides detailed theoretical proofs for a well-established problem: submodular optimization using surrogate functions. Its rigorous characterization of how surrogate error affects approximation guarantees is a strength, particularly given the importance of such guarantees in this setting.
Critical weaknesses
-
The proofs are lengthy, but the key ideas and intuition are not sufficiently explained, making the arguments difficult to follow. A clearer proof roadmap would improve readability. Some proofs, such as that of Proposition 2, could also be shortened.
-
Marginal-gain approximation has been studied in prior work. The paper needs a more detailed comparison of its assumptions and guarantees with existing results, clearly identifying which results are new and how they improve upon previous bounds. The current presentation emphasizes formal derivations without sufficiently establishing the significance of the contributions.
-
The manuscript contains unresolved placeholders, such as “??”, and other formatting issues. It would benefit from careful proofreading.
Questions for authors
Could you clarify the definitions and interpretations of and in $ \eta^{\mathrm{sel}}\leq\eta^{\mathrm{tr}}\leq\eta? $ Their meanings are not sufficiently clear when this relationship is first introduced. Please also explain how these quantities differ and how they are measured in the experiments.
4 comments
Author response 2/2
W2: Comparison with prior work on marginal-gain approximation; what is new
Table 1. Closest prior analyses and this paper.
| Work | Objective known? | Error on | Guarantee | Upper bound for all algorithms |
|---|---|---|---|---|
| Goundan & Schulz (2007); adopted by Schwartzman (2024), Münch & Raach (2025) | Yes | The gain of the chosen element, at each step | for factor ; tight for | – |
| Wei et al. (2014) | Yes, expensive to evaluate | The gain of the chosen element, at each step | A bound in the step ratios and the curvature; attained | – |
| Gupta et al. (2018) | Yes | Every marginal gain | A constant factor, in the error and the curvature | – |
| Horel & Singer (2016) | No | Every value, within | Greedy: if ; no constant factor if | If : no constant factor with polynomially many queries |
| Hassidim & Singer (2017) | No | Every value (noise); Section 5.2: marginal gains | I.i.d. noise: close to , with a modified greedy. Section 5.2: a constant factor, stated as well known | Adversarial noise on values: no non-trivial guarantee. Additive noise on marginal gains: generally impossible |
| This paper | No | Every marginal gain of one surrogate | Exactly , strictly above the classical bound for and | with unlimited queries; with the queries of predictive greedy |
Summary. Our algorithm has no access to the objective, the error is on all marginal gains, and the paper gives the exact ratio and upper bounds for deterministic algorithms (conditions in Proposition 3 and Theorem 2). We will add any related work that Table 1 misses.
Revised text (Related work, second paragraph; four references added).
Prior analyses with error on marginal gains are of two kinds, by where the error lies. [...] Definition 1 is of the second kind, with the error carried by one surrogate. The second kind implies the first at every greedy step, so the known bound of Goundan & Schulz (2007) applies (Proposition 4). New are the exact ratio , above this bound for and , and upper bounds for all deterministic algorithms.
W3: Proofreading. We appreciate your careful reading. The question marks came from six cross-references that pointed to labels renamed when the sections were restructured.
Q1: the three errors
Definitions and how the errors differ.
- Global error : the largest factor by which a predicted gain is too low, times the largest factor by which a predicted gain is too high, over all sets.
- Trajectory error : the same quantity as the global error, computed only over the sets that one run visits.
- Selection error : the largest ratio, over the steps, of the true gain of the best element to the true gain of the picked element.
Each error looks at less: all sets, the visited sets, the picks. A wrong prediction costs greedy only when the prediction changes the pick. Example: A truly adds 10 and is predicted 5; B truly adds 8 and is predicted 12. Greedy picks B. The error of the surrogate at this set is (trajectory error), and the pick loses only (selection error). If one prediction at a set the run never visits is too low by a factor of 6, the global error is .
Measurement. After a run, the experiments compute the true gain of every candidate element at each of the visited sets. The true gains give ; the true gains and the predicted gains together give (Appendix H.1). The global error needs every set and cannot be read off a run.
Revision. The three errors now first appear in Section 3.4 with Definition 2, not in the technical contribution paragraph.
We hope that the responses above and the revision address every concern, and we would be grateful if the reviewer would reconsider the assessment of the paper.
References
The works compared in Table 1 of our response are linked here: Goundan & Schulz (2007); Schwartzman (2024); Münch & Raach (2025); Wei et al. (2014); Gupta et al. (2018); Horel & Singer (2016); Hassidim & Singer (2017).
Polite follow-up comment
Dear Reviewer 147C,
The revision has been uploaded. Our comment to all reviewers lists the changes by page, and the rows marked 147C answer this review.
We saw that the rating changed after our response. If a concern remains after the response and the revision, we would be grateful if the reviewer would state the concern here. We will answer promptly.
Thank you again for the time given to our paper!
Sincerely, The authors
Follow-up: a short summary of our response
Dear Reviewer,
We write to you once more before the discussion closes. Your review asked for changes that a reader can check in the revised PDF, and each one is there:
- Proof roadmap (W1). Figure 2 on page 4 shows the structure of the proofs. The opening of Section 3 states the two key ideas, and the long appendix proofs open with overviews, so a reader meets the roadmap and the key ideas before the proofs. The proof of Proposition 2 is shorter.
- Prior work (W2). Related work compares assumptions and guarantees with prior work on marginal-gain approximation, with four added references. The introduction states what is known and what is new.
- Proofreading (W3). All cross-references are fixed.
- The three errors (Q1). Section 3.4 now introduces the three errors together, with Definition 2.
Thank you for the suggestions, which made the paper easier to read.
Your review also asked for the significance of the contributions. We believe that the paper is useful to the community and that later work can build on the results, for three reasons:
- Prior theory for objectives that cannot be accessed is pessimistic. The paper shows that this pessimism comes from where the error is measured: on values, not on marginal gains.
- For an error on marginal gains, the paper gives the exact approximation ratio of greedy and shows that no deterministic algorithm with the same queries guarantees more, under the conditions of Theorem 2. These two results leave no room for a sharper analysis of greedy or a better deterministic algorithm within this budget.
- The paper names the error to control when a surrogate is learned for selection, and states four open questions, each with bounds, for later work.
The rating rose after our response and returned to weak rejection one day later. We do not know which concern remains. A single sentence that names the concern would help us, and we will answer at once. If the revision answers the review, we would be deeply grateful if you would reconsider the rating.
Best regards, The authors
Author response 1/2
Thank you for recognizing the characterization of how surrogate error affects approximation guarantees as a strength of the paper, and for noting the importance of such guarantees in this setting. We respond to each weakness and to the question below. Revised text of the paper is quoted, and the revision has been uploaded.
W1: A proof roadmap, the key ideas first, and shorter proofs
We appreciate these suggestions for guiding the reader and making the proofs easier to follow. The revision adopts each suggestion as follows.
A proof roadmap. A new figure, Figure 2, now opens Section 3 and shows which statements each result of the section rests on, in particular the lemmas behind Theorems 1 to 3. The appendix proofs of Theorems 1 and 2 each open with an overview (Appendices D.4 and E.2).
Key ideas and intuition. The opening paragraph of Section 3 now states the two key ideas of the proofs, a path-independence argument and a hiding argument, and Section 3.3 now explains the hiding argument in plain words. The revision also keeps the intuition of the submission. Section 3.2 states the idea behind Theorem 1 as a trade-off. One numerical example, K=3 and η=3/2, runs through Sections 3.1 to 3.3: the information price is 2/3 (Proposition 3), the exact ratio is 9/16 against the classical bound 0.53 (Theorem 1), and 9/16 is also the upper bound of Theorem 2.
Revised text (Section 3, opening paragraph).
Shorter proofs. The proof of Proposition 2 has 23 lines instead of 36. Passages that appeared twice now appear once.
W2: Comparison with prior work on marginal-gain approximation; what is new
Marginal-gain approximation has indeed been studied in prior work, and the submission builds on this work (Goundan & Schulz, 2007). We stated the comparison only briefly. The revision rewrites the comparison in Related work, with four added references. Table 1 in the next comment summarizes the comparison, and its last row lists what is new in this paper.
Assumptions. The closest analyses of marginal-gain approximation assume a known objective (Goundan & Schulz, 2007; Wei et al., 2014; Gupta et al., 2018). Three lines of prior work have no access to the objective and measure the error on values (samples, noisy oracles, values within 1±ϵ of f). Our paper studies marginal-gain approximation without access to the objective: the algorithm queries only a surrogate (Definition 1).
Known: with error η (Definition 1), every greedy step gains at least 1/η of the best element. This is the condition of Goundan & Schulz (2007), so the classical bound 1−(1−1/(ηK))K applies (Proposition 4). Wei et al. (2014) bound greedy through the step ratios of a run and show that their bound is attained.
What is new: three results for one surrogate that carries the marginal-gain error on all sets, not only along a run.
(1) Upper bound with unlimited queries. No deterministic algorithm guarantees more than 1/η, attained by exhaustive search (Proposition 3).
(2) Exact approximation ratio of predictive greedy. One surrogate cannot make every step a separate worst case, so predictive greedy guarantees strictly more than the classical bound for η>1 and K≥2. Theorem 1 gives the exact ratio.
(3) Optimality within the query budget. Any gap between the two comes from the query budget, not from greedy: no deterministic algorithm with the same queries guarantees more than predictive greedy, under the conditions of Theorem 2.
Together, results 2 and 3 leave no room for a sharper analysis of predictive greedy or a better deterministic algorithm within its query budget. The introduction now states this directly.
Revised text (Section 1, Technical contributions).