acceptodds
Under review as a conference paper at ICLR 2027

Submodular Maximization with Predictions: The Exact Price of Error

Abstract

Maximizing a monotone submodular function under a cardinality constraint has a classical approximation guarantee, but in many subset-selection tasks the objective cannot be evaluated while the set is chosen, and an algorithm maximizes a learned model of the objective, a surrogate. Prior work bounds the surrogate's error on function values and is pessimistic: no algorithm with polynomially many queries retains a constant fraction of the optimum. The classical greedy guarantee rests on marginal gains, and we measure the error there: the surrogate may distort any marginal gain by at most a factor . We consider deterministic algorithms that query only the surrogate and determine three prices. The information price is : with unlimited queries, no deterministic algorithm guarantees more, and exhaustive search on the surrogate attains it. Predictive greedy, the greedy algorithm applied to the surrogate, pays exactly , an explicit function of and that tends to ; the classical approximate-greedy bound is not tight for a surrogate. The price of the budget accounts for the rest: within greedy's query budget, no deterministic algorithm guarantees more than , so predictive greedy is optimal there. The error along the greedy path gives a per-instance guarantee and, on learned surrogates for feature selection, influence maximization, and summarization, ranks surrogates by their true performance.

Primary area:
optimization
Keywords:
Learning-augmented algorithms, submodular functions, optimization, predictions

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_147COpenReview ↗
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 η\eta, it establishes an optimal approximation ratio of 1/η1/\eta with unlimited queries and derives the exact approximation ratio ρK(η)\rho_K(\eta) 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
  1. 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.

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

  3. 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 ηsel\eta^{\mathrm{sel}} and ηtr\eta^{\mathrm{tr}} 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
AuthorsOpenReview ↗

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=3K=3 and η=3/2\eta=3/2, runs through Sections 3.1 to 3.3: the information price is 2/32/3 (Proposition 3), the exact ratio is 9/169/16 against the classical bound 0.530.53 (Theorem 1), and 9/169/16 is also the upper bound of Theorem 2.

Revised text (Section 3, opening paragraph).

This section proves the three prices; Figure 2 shows the proof structure. Two ideas recur. First, one surrogate answers every step: adding two elements in either order reaches the same predicted value, giving an inequality the classical analysis lacks. Second, the optimal set is placed after the queries: against an uninformative surrogate, a deterministic algorithm fixes its queries and output before the objective is chosen. [...]

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±ϵ1\pm\epsilon of ff). Our paper studies marginal-gain approximation without access to the objective: the algorithm queries only a surrogate (Definition 1).

Known: with error η\eta (Definition 1), every greedy step gains at least 1/η1/\eta of the best element. This is the condition of Goundan & Schulz (2007), so the classical bound 1−(1−1/(ηK))K1-(1-1/(\eta 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/η1/\eta, 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\eta > 1 and K≥2K\ge2. 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).

For greedy, the classical bound of Goundan & Schulz (2007) is the known guarantee (Proposition 4). We show that no surrogate with error η>1\eta > 1 attains it for K≥2K\ge2: the price greedy pays is ρK(η)\rho_K(\eta), a closed form that tends to 1−e−1/η1-e^{-1/\eta} as KK grows (Theorem 1); to our knowledge, the first exact ratio of greedy under a marginal-gain error on all sets. [...] Theorems 1 and 2 leave no room for a sharper analysis of greedy or a better deterministic algorithm within this budget; the gap between ρK(η)\rho_K(\eta) and 1/η1/\eta is the price of the budget, not of greedy.

AuthorsOpenReview ↗

Author response 2/2

W2: Comparison with prior work on marginal-gain approximation; what is new

Table 1. Closest prior analyses and this paper.

WorkObjective known?Error onGuaranteeUpper bound for all algorithms
Goundan & Schulz (2007); adopted by Schwartzman (2024), Münch & Raach (2025)YesThe gain of the chosen element, at each step1−(1−1αk)k1-(1-\frac{1}{\alpha k})^{k} for factor α\alpha; tight for α=1\alpha=1–
Wei et al. (2014)Yes, expensive to evaluateThe gain of the chosen element, at each stepA bound in the step ratios and the curvature; attained–
Gupta et al. (2018)YesEvery marginal gainA constant factor, in the error and the curvature–
Horel & Singer (2016)NoEvery value, within 1±ϵ1\pm\epsilonGreedy: 1−1/e−O(δ)1-1/e-O(\delta) if ϵ=δ/k\epsilon=\delta/k; no constant factor if ϵ=1/k1−β\epsilon=1/k^{1-\beta}If ϵ≥1/n1/2−β\epsilon\ge1/n^{1/2-\beta}: no constant factor with polynomially many queries
Hassidim & Singer (2017)NoEvery value (noise); Section 5.2: marginal gainsI.i.d. noise: close to 1−1/e1-1/e, with a modified greedy. Section 5.2: a constant factor, stated as well knownAdversarial noise on values: no non-trivial guarantee. Additive noise on marginal gains: generally impossible
This paperNoEvery marginal gain of one surrogateExactly ρK(η)\rho_K(\eta), strictly above the classical bound for η>1\eta > 1 and K≥2K\ge21/η1/\eta with unlimited queries; ρK(η)\rho_K(\eta) 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 ρK(η)\rho_K(\eta), above this bound for η>1\eta > 1 and K≥2K\ge2, 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 ηsel≤ηtr≤η\eta_{\mathrm{sel}}\le\eta_{\mathrm{tr}}\le\eta

Definitions and how the errors differ.

  • Global error η\eta: 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 ηtr\eta_{\mathrm{tr}}: the same quantity as the global error, computed only over the KK sets that one run visits.
  • Selection error ηsel\eta_{\mathrm{sel}}: the largest ratio, over the KK 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 2×1.5=32\times1.5=3 (trajectory error), and the pick loses only 10/8=1.2510/8=1.25 (selection error). If one prediction at a set the run never visits is too low by a factor of 6, the global error is 6×1.5=96\times1.5=9.

Measurement. After a run, the experiments compute the true gain of every candidate element at each of the KK visited sets. The true gains give ηsel\eta_{\mathrm{sel}}; the true gains and the predicted gains together give ηtr\eta_{\mathrm{tr}} (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).

AuthorsOpenReview ↗

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

AuthorsOpenReview ↗

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

Reviewer_NkbqOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies monotone submodular maximization when the true objective is unavailable and only a surrogate can be queried. The authors derive an exact approximation ratio for predictive greedy under bounded multiplicative marginal-gain error and establish its optimality within a restricted query budget.

Critical strengths
  • The problem formulation is clear, and the exact approximation analysis is theoretically interesting.

  • The paper provides tight worst-case constructions and query-complexity lower bounds.

Critical weaknesses
  1. The experimental evidence does not convincingly support the practical relevance of the theoretical guarantees. In the influence maximization experiments, the global marginal-gain error is infinite for all 160 email-network runs, preventing direct application of the finite-error exact guarantee. The per-run certificates are also highly conservative: at K=30K=30 and p=0.5p=0.5, the reported certificate is only 0.125 for the email network and 0 for the government network, whereas the observed ratios against true-objective greedy are 0.963 and 0.940, respectively. Furthermore, the objectives used in feature selection and summarization violate the monotonicity or submodularity assumptions. As a result, the real-world experiments provide limited evidence that the proposed exact guarantees are informative for practical learned surrogates.

  2. The practical significance of the theoretical improvement remains unclear. The exact bound improves upon the classical approximate-greedy guarantee by only (O(1/K)), making the improvement increasingly small for larger budgets. Moreover, the tight constructions rely on non-submodular surrogates in an important parameter regime, whereas several practical surrogates considered in the paper are submodular. This raises questions about how representative the exact worst-case characterization is of practical applications.

  3. The optimality result is established under restrictive conditions, requiring (n =< K^4) and considering only deterministic algorithms with constrained queries. Furthermore, the empirical certificates are often extremely loose despite strong observed performance and require post-hoc access to true marginal gains. These limitations weaken the practical implications of the theoretical results.

Questions for authors

See the weaknesses above.

5 comments
AuthorsOpenReview ↗

Author response 1/3

Thank you for the careful reading of both the theory and the experiments, and for recognizing the clear formulation, the exact analysis, the tight constructions and the query lower bounds. Revised text of the paper is quoted, and the revision has been uploaded.

W1: Practical relevance of the guarantees in the experiments

Thank you for this observation. We are sorry that the submission did not state the role of the experiments directly, so the experiments could be read as a test of the guarantees. The role is stated below and in the revised opening of Section 4.

Role of the experiments.

  • The main contribution is the theory of Section 3, whose guarantees are worst-case: a guarantee is the lowest ratio over all surrogates with error η\eta, and a real surrogate can do better.
  • The experiments are an addition to the theory and do not test the guarantees. For real surrogates, Section 4 reports the ratio that predictive greedy reaches and the certificate that the theory gives for each run.

The global error is infinite on real surrogates. What can we use instead? The error measured on the run itself (Section 3.4).

  • Why infinite. A run on the email network considers about 30,000 candidates, and a single candidate with true gain zero and positive predicted gain, or the reverse, makes the global error infinite. Such candidates occur on every network run. The value is a measurement, reported as observed.
  • Consequence. As you note, Theorem 1 gives no guarantee on these runs. The cause lies in the problem, not in the assumption: without a bound on the error, no deterministic algorithm has a constant-factor guarantee (Proposition 1).
  • What the paper does. Section 3.4 measures the error on the run itself and certifies the run afterwards. The submission listed these errors side by side with little explanation; Table 1 states where each error is measured, when each is available and what each gives.

Table 1. Errors and guarantees. Certificate values are medians at p=0.5p=0.5 and K=30K=30.

ErrorMeasured onAvailableGivesValue
Global error η\eta (Definition 1)all setsbefore the run, if knownguarantee of Theorem 1infinite on every network run: no guarantee
Selection error (Definition 2)the worst step of a runafter the runcertificate in the submission0.125 (email), 0 (government)
Step ratios (Definition 2)every step of a runafter the runper-step certificate in the revision0.495 (email), 0.533 (government)

The step ratios follow prior work: the individual greedy ratios of Wei et al. (2014). The per-step certificate uses each step as measured (Appendix H.9 of the submission; now Table 1 of the revision).

The ratio and the certificate in the submission's Table 1 were far apart for two reasons.

  • The two columns answer different questions. The ratio divides the value of the set chosen on the surrogate by the value of the set that greedy chooses on the true objective. The certificate is a guarantee against the best possible set, which cannot be computed on these networks. Greedy on the true objective itself has ratio 1 and certificate 0.638 at K=30K=30, the classical bound, so no certificate can be near 0.96.
  • The certificate in the submission's Table 1 lets one step decide the whole run. Within a run, this certificate treats all 30 steps as the worst one. On government, half of the runs have one step that adds nothing, which gives 0. This is too conservative, and we thank you for pointing to these two numbers.

We now report the per-step certificate, in which one poor step costs one step. Email and government reach 78% and 83% of the greedy's certificate on the true objective. For comparison, ranking by observed degree keeps 66% to 89% of the value of greedy on the true objective, and random nodes keep 6% to 54%, against 94% to 99% for predictive greedy.

A new control experiment applies Theorem 1 directly. The experiment builds surrogates of known error η\eta from 1.25 to 5 (weighted coverage, node weights in [1/η,η][1/\sqrt{\eta},\sqrt{\eta}]). Every run of this experiment is above the guarantee:

  • Random instances, n=12n=12, K=3K=3, 500 runs: lowest ratio 0.800, against guarantees from 0.200 to 0.626 (ratio to the exact optimum).
  • Real networks, weights set against greedy, 80 runs: lowest ratio 0.697, against guarantees from 0.186 to 0.595 (ratio to greedy on ff).
  • Real networks, random weights, 400 runs: lowest ratio 0.988, against the same guarantees (ratio to greedy on ff).

The 60 constructed instances of Section 4 attain the guarantee exactly.

Revised text (Section 4, opening).

Section 3 gives the worst-case guarantee over all surrogates with error η\eta; a single surrogate can do better. The experiments therefore do not test the bounds, and measure how far above the bounds real surrogates lie. [...]

AuthorsOpenReview ↗

Author response 2/3

W1 (continued): feature selection and summarization

Held-out accuracy and ROUGE-1 F are submodular-like objectives, and greedy is the standard method for such objectives. Many objectives in applications are close to submodular without being exactly submodular, and the literature runs and analyzes greedy on such objectives. Prior work:

The paper follows this practice and runs predictive greedy on these two objectives.

What the submission claims. As you note, neither objective is exactly monotone submodular. The reason is known: an added feature can lower held-out accuracy, and ROUGE-1 F penalizes length. Both objectives show diminishing returns. The paper marks the bounds of these two applications as reference values, not certificates (the parentheses in the submission's Table 1). Certificates are claimed only where the objective is monotone submodular: the four networks, the constructed instances and the new control experiment.

Revised text (Section 4, paragraph on these two applications, now titled "Submodular-like objectives").

Held-out accuracy and ROUGE-1 F are submodular-like: not exactly monotone submodular, and maximized by greedy in practice as submodular objectives are (Das & Kempe, 2011; Lin & Bilmes, 2011; Bian et al., 2017; Elenberg et al., 2018). [...]

W2: Significance of the exact bound, and submodular surrogates

The O(1/K)O(1/K) term is the whole distance between the classical bound and the exact bound. As you note, the difference is of order 1/K1/K (Corollary 1). This small difference is the exact answer, not a limit of the analysis.

  • No larger improvement exists. The guarantee of Theorem 1 is tight: predictive greedy keeps at least ρK(η)\rho_K(\eta) on every instance and exactly ρK(η)\rho_K(\eta) on some instance. No analysis can prove a guarantee above ρK(η)\rho_K(\eta).
  • What Theorem 1 settles. The classical bound is attained when the error is measured along the run (Wei et al., 2014; Proposition 5). Whether one surrogate with error η\eta on all sets attains the classical bound was, to our knowledge, not determined. Theorem 1 answers: no such surrogate does for η>1\eta>1 and K≥2K\ge2.
  • Large budgets. The difference shrinks because the classical bound approaches the exact bound: both tend to 1−e−1/η1-e^{-1/\eta}. A small difference at large KK therefore means that the classical bound is nearly exact there, and Theorem 1 is the result that proves this.
  • Small budgets. The difference is larger: at K=3K=3 the exact bound is 3% to 12% above the classical bound for η\eta from 1.25 to 5, for example 0.467 against 0.421 at η=2\eta=2. Small budgets are common in applications: Das & Kempe (2011) select at most 8 features, the extractive summarizer of Liu (2019) selects three sentences, and our paper uses K=5K=5 for summarization and K=7K=7 for feature selection.
  • The exact bound brings optimality, not a margin. With the classical bound alone, the lower bound and the upper bound do not meet.

The guarantee of Theorem 1 holds for every surrogate with error η\eta, submodular or not. As you note, the tight constructions of Theorem 1 rely on non-submodular surrogates, and we thank you for raising this point. The remaining question is how much higher the guarantee is for submodular surrogates alone.

  • Upper bound. Lemma 12 gives a closed-form upper bound on this guarantee: the ratio of predictive greedy on explicit instances with a submodular objective and a submodular surrogate.
  • Size of the gap. The upper bound equals ρK(η)\rho_K(\eta) for η≥K\eta\ge K and is less than 0.04 above ρK(η)\rho_K(\eta) at every pair computed, with KK up to 2000. The largest gap found is 0.0397, at K=2000K=2000 and η=1.86\eta=1.86 (0.4557 against 0.4160); at K=3K=3 and η=1.5\eta=1.5 the gap is 0.0133 (0.5758 against 0.5625).
  • Open. The exact value is an open question, already listed in the conclusion.

Revised text (Section 3.2, after Corollary 1).

This term is the whole distance between the classical bound and the exact ratio: instances attain ρK(η)\rho_K(\eta) for every K≥2K\ge2, so no analysis can prove a guarantee above ρK(η)\rho_K(\eta). [...] Requiring a submodular surrogate defines a different ratio, equal to ρK(η)\rho_K(\eta) for η≥K\eta\ge K and, for 1<η<K1<\eta<K, between ρK(η)\rho_K(\eta) and the value min⁡mWm(K,η)\min_m W_m(K,\eta) of an explicit family with submodular surrogates (Lemma 12). The two values differ by less than 0.04 at every pair computed (Appendix D.7).

AuthorsOpenReview ↗

Author response 3/3

W3: Conditions of the optimality result, and the certificates

The three conditions (ground-set size, deterministic algorithms, query budget) belong to Theorem 2, which compares predictive greedy with other algorithms. The guarantee of predictive greedy needs none of the three: Theorem 1 holds for every n≥2Kn\ge2K.

Prior results of this kind also need a large ground set; Theorem 2 states how large.

  • Prior results. For a known objective and fixed KK, greedy has the best guarantee among algorithms with O(n)O(n) computations (Nemhauser & Wolsey, 1978). Horel & Singer (2016), Hassidim & Singer (2017) and Balkanski et al. (2017) are asymptotic in nn and state no threshold.
  • Why a threshold is needed. For n≤K+2n\le K+2, exhaustive search fits within the budget of Theorem 2 and guarantees more than predictive greedy for 1<η<K1<\eta<K (Remark 1).
  • What is open. The threshold n≥K4n\ge K^4 is sufficient, not the least possible. The least threshold is an open question, listed in the conclusion.

Deterministic algorithms are also the setting of the classical optimality result. The proof of Nemhauser & Wolsey (1978) covers deterministic algorithms only; Sviridenko et al. (2017) point this out and give an extension to randomized algorithms. For a surrogate, Proposition 6 bounds randomized algorithms with unlimited queries, and the best randomized guarantee is an open question as well.

A query budget is needed: with unlimited queries, exhaustive search guarantees more. Exhaustive search over the surrogate guarantees 1/η1/\eta, more than ρK(η)\rho_K(\eta) for 1<η<K1<\eta<K (Proposition 3). Theorem 2 therefore takes the budget of predictive greedy itself; the classical result likewise has a budget of O(n)O(n) computations.

The revision states the open question behind each condition.

Revised text (conclusion; see also the revised Section 3.5).

Questions remain open, each with bounds proved in this paper: the least ground-set size from which predictive greedy is optimal within its budget; the best guarantee of randomized algorithms; the best guarantee of deterministic algorithms with queries on sets of any size; and, for 1<η<K1<\eta<K, the exact approximation ratio of predictive greedy over submodular surrogates alone, which is at least ρK(η)\rho_K(\eta).

You are right that the certificate reported in the submission was too conservative; the revision reports the per-step certificate. The per-step certificate reaches 78% to 93% of the 0.638 that greedy on the true objective itself receives on the four networks (see W1).

True gains are used only after the run, to evaluate the run. We understand your concern about practical use when the certificate needs true gains. The paper uses different information before, during and after the run:

  • Before the run. Three results apply and need no true gain. With a bound on the error, Theorem 1 gives the guarantee, as in the control experiment of W1. Theorem 2 addresses the choice of algorithm within the budget of predictive greedy. Proposition 2 names the error to control in a surrogate: the error on marginal gains, not on values.
  • During the run. The premise of the paper is that the objective cannot be evaluated while the set is chosen, and predictive greedy queries the surrogate only.
  • After the run. As you note, the certificate is computed after the run from true gains: the true gain of every candidate at each of the KK steps, at most nKnK values. The observed ratio needs the same information, because greedy on the true objective, the denominator of the ratio, also reads the true gain of every candidate at each of its KK steps.

Section 3.4 of the submission states this role of the certificate: "an audit after the run", not a fallback during the run. Section 4 of the revision states for each reported quantity whether true gains are needed, as in Table 1 of our first comment.

Thank you for your time and comments. We hope that the response and the revision address your concerns, and we would be grateful if you would reconsider the rating. We are glad to answer any further questions to fully address your concerns.

References (works not in the bibliography of the submission)

Reviewer_Hpe9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers maximizing a normalized monotone submodular function ff under a cardinality constraint when only query access to a surrogate function f~\tilde f is available. Although related problems have been studied before, this paper focuses on a two-sided multiplicative bound on marginal-gain errors. The surrogate is not assumed to be submodular, although the error condition implies monotonicity. Under this assumption, the authors establish hardness results and approximation guarantees for predictive greedy, which grows the selected set by adding elements with the largest surrogate marginal gains.

Critical strengths

I enjoyed reading the paper and found the writing very good. Propositions 1 and 2 clearly position the results and motivate the marginal-error assumption. From a theoretical standpoint, the paper provides several strong results. Proposition 3 characterizes the best achievable approximation for deterministic algorithms even with unrestricted query access. On the positive side, the authors establish a tight approximation guarantee for predictive greedy. They also show that, for n≥K4n\ge K^4, predictive greedy is optimal among deterministic algorithms making at most nKnK surrogate queries, each on a set of size at most KK. These constitute a solid and comprehensive set of theoretical guarantees within the stated model.

Critical weaknesses

I did not identify a specific critical weakness.

Questions for authors

none.

3 comments
AuthorsOpenReview ↗

Author response

Thank you very much for the time and care given to our paper. A great deal of work went into this paper, and the review reflects a close reading of the theory: the role of Propositions 1 and 2, the best guarantee in Proposition 3, the tight guarantee of predictive greedy, and the exact conditions of the optimality result. We are deeply grateful that the reviewer enjoyed reading the paper, found the writing very good, and regards the results as "a solid and comprehensive set of theoretical guarantees" with no critical weakness. This recognition means a great deal to us.

The revision keeps the results and the style of the submission, and is clearer. The theorems and the contributions are unchanged. We revised the presentation carefully, following the comments of the other reviewers:

  • The introduction states, in the paragraph on technical contributions, what is known and what is new.
  • Related work compares the assumptions and guarantees with prior work on marginal-gain error in more detail.
  • Section 3 opens with a figure that shows the structure of the proofs.
  • Section 3.4 explains the certificate in plainer terms, and Section 3.5 states the setting of Theorem 2 and the open questions in one place.
  • Section 4 states the role of the experiments, adds a control experiment with surrogates of known error, and reports a stronger certificate, the per-step certificate, in Table 1.

The revision has been uploaded already, and we would appreciate the reviewer's reading of the revised sections.

We believe that the paper is useful to the community and that later work can build on the results. Prior work on approximate objectives is pessimistic. With the error measured on marginal gains, the paper gives exact answers for deterministic algorithms, and the conclusion lists four open questions, each with bounds proved in the paper.

If the revision reads well to the reviewer, we would be grateful if the reviewer would consider raising the rating to acceptance and supporting the paper in the discussion. We are glad to answer any further question.

Thank you for the rebuttal. I maintain my positive score.

Dear Reviewer,

Thank you very much for reading our response and for keeping the positive assessment! The support of a reviewer who read the theory this closely means a great deal to us.

Our responses to the other two reviews cover the role of the experiments, the comparison with prior work, and the significance of the exact ratio. These responses and our summary comment may be useful for the discussion among the reviewers and the Area Chair.

We have one more request. If a reservation keeps the rating at weak acceptance, we would be grateful if the reviewer would name the reservation, and we will answer before the discussion closes. If no reservation remains, we would be deeply grateful if the reviewer would consider raising the rating to acceptance and supporting the paper in that discussion.

Thank you again for your time and kind words.

Best regards, The authors

Comments on the paper

2 comments
AuthorsOpenReview ↗

Revision uploaded

Dear Reviewers,

Thank you for your reviews. Your valuable comments made the revision more complete and easier to follow, and tied the experiments more closely to the theory. The revision is uploaded. This comment summarizes the changes, so that each reviewer can go directly to the passages that answer the review. Page numbers refer to the revised PDF.

The technical contributions are unchanged. Theorems 1 to 3, Propositions 1 to 4, Corollary 1 and Remark 1 are word for word as in the submission and keep the same numbers.

PagePlaceChangeReviewer
1AbstractStates the setting of Theorem 2 (nKnK queries on sets of at most KK elements, n≥K4n \ge K^4) and that the certificate is measured after a runNkbq W3
2Introduction, "Technical contributions"What is known (the classical bound of Goundan & Schulz, 2007) and what is new147C W2
3, 4Related workAssumptions and guarantees compared with prior work on marginal-gain error; four references added147C W2
4Figure 2; opening of Section 3The structure of the proofs; the two key ideas147C W1
5, 6Sections 3.1 and 3.2Fuller proof sketches, with the instance that attains the exact ratio. After Corollary 1: the term of order 1/K1/K, and submodular surrogates147C W1, Nkbq W2
6, 7Section 3.3The hiding argument in plain words; proof sketches of Theorems 2 and 3; larger budgets, queries of any size, randomized algorithms147C W1, Nkbq W3
8Section 3.4The three errors first appear here, with Definition 2. Proposition 5 (ii) is the per-step certificate147C Q1, Nkbq W1
8Section 3.5The setting of Theorem 2, and the open questionsNkbq W3
9Section 4; Figures 3 and 4The role of the experiments; which quantities need true gains; the control experiment with surrogates of known errorNkbq W1, W3
10Table 1; "Real surrogates"; "Submodular-like objectives"The per-step certificate; the infinite global error; the baselines; feature selection and summarizationNkbq W1
10ConclusionLimitations; four open questions, each with bounds proved in the paperNkbq W2, W3

We thank all three reviewers, and the Area Chair, very much for the time and care given to this paper. Reviewer 147C's request for a roadmap led to Figure 2 and to the overviews that open the long proofs. Reviewer Nkbq's reading of the experiments led to the control experiment and to the per-step certificate, and the questions on Theorem 2 led to Section 3.5. Reviewer Hpe9's close reading of the theory, and the kind words in that review, encouraged us throughout the revision. A great deal of work went into this paper and into the revision. We would be deeply grateful if every reviewer would read the revised passages; the last column shows which rows answer which review. We are glad to answer any further question before the discussion closes.

AuthorsOpenReview ↗

General response to reviewers and AC

Dear Area Chair and Reviewers,

Thank you for the time given to this paper. This comment summarizes, in plain words, the contributions of the paper, the discussion and the revision.

1. Contributions

In many subset-selection tasks, such as data selection, summarization and influence maximization, the objective cannot be evaluated while the set is chosen, and the algorithm maximizes a learned model of the objective, a surrogate. Prior theory without access to the objective measures the error of the surrogate on function values and is pessimistic: in general, no algorithm with polynomially many queries keeps a constant fraction of the optimum. The closest analyses of marginal-gain approximation assume a known objective. The paper studies marginal-gain error without access to the objective, and gives exact answers for deterministic algorithms that query only the surrogate.

  • Unlimited queries. The paper determines the best guarantee of any deterministic algorithm, reached by exhaustive search.
  • Greedy on the surrogate. No single surrogate achieve the classical approximate-greedy bound when the error factor and the cardinality constraint both exceed one. The paper gives the exact approximation ratio in closed form: to our knowledge, the first exact ratio of greedy under a marginal-gain error on all sets.
  • Optimality. For a large enough ground set, no deterministic algorithm with the query budget of greedy guarantees more than greedy.
  • One run. When the error on all sets is unknown, quantities measured after a run certify that run.

2. Relevance to machine learning

  • The paper names the error to control when a surrogate is learned for selection: the error on marginal gains, not on values. Accurate values are neither necessary nor sufficient for greedy on a surrogate.
  • The pessimism of prior theory comes from where the error was measured, not from surrogates. A bound on marginal gains leaves greedy a constant fraction of the optimum, and the distance to the best possible guarantee is the price of the query budget, not of greedy.
  • Four open questions, each with bounds proved in the paper, are stated for later work.

3. Points clarified in the discussion

  • Role of the experiments. The guarantees are worst-case over all surrogates with a given error, and a real surrogate can do better. The experiments are an addition to the theory and do not test the guarantees. Certificates are claimed only where the objective is monotone submodular; for feature selection and summarization, the bounds are reference values.
  • Infinite error on real surrogates. Without a bound on the error, no deterministic algorithm has a constant-factor guarantee, so the paper certifies such runs afterwards. The realized ratio compares with greedy on the true objective; the certificate compares with the unknown optimum.
  • Prior work. The classical bound is known and credited. The exact ratio and the upper bounds for all deterministic algorithms are new.
  • Size of the improvement. The difference from the classical bound is small because no larger difference is possible. The exact ratio brings optimality: the lower bound and the upper bound meet.
  • Submodular surrogates. The guarantee holds for every surrogate, submodular or not. For submodular surrogates alone, the exact value is open and lies less than 0.04 above the general guarantee on every case computed.
  • Conditions of the optimality result. The conditions belong to the comparison with other algorithms, not to the guarantee of greedy. A threshold on the ground-set size and a query budget are both needed, and the classical optimality result is also for deterministic algorithms.

4. Changes in the revision, highlighted in newly updated manuscript

  • Following Reviewer 147C. A figure of the proof structure opens the theory section, the long appendix proofs open with overviews, and proofs are shortened after careful revision. The introduction states what is known and what is new, Related work compares assumptions and guarantees with prior work on marginal-gain error, with four added references, and all cross-references are fixed.
  • Following Reviewer Nkbq. The experiments section states the role of the experiments and adds a control experiment with surrogates of known error, in which every run lies above the guarantee. The results table reports the stronger per-step certificate, which reaches 78% to 93% of the certificate of greedy on the true objective on the four networks. One subsection states the setting of the optimality result and the open questions.

The theorems and the contributions are unchanged, and the main text stays within the 10 pages allowed during the discussion. Our earlier comment lists the changes by page.

We would be grateful if the Area Chair and the reviewers would consider the responses and the revision in the final assessment.

Best regards, The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.