acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal Sample Complexity for PAC Submodular Maximization

Abstract

How many noisy observations are needed to select a high-quality set with high probability? We study monotone submodular maximization, where an item's benefit can decrease as other items are selected. Given items and a selection budget , we provide a polynomial-time algorithm that returns a set of value at least with probability , where is the optimal value. Under independent unit-variance Gaussian noise on marginal gains, the algorithm uses observations, without knowing or an upper bound on function values. A matching worst-case lower bound, up to logarithmic factors, holds even for additive functions, for fixed and . The algorithm begins by evaluating each item and then selects from random candidate subsets. An exponential-moment bound for sample maxima controls the total loss from these subsets; the initial gain and the slack in the greedy guarantee together offset that loss. With exact marginal queries, the same analysis gives the strict ratio with high probability using queries. We further show that, at comparable optimal values, submodular maximization can require polynomially more observations than maximizing an additive function.

Primary area:
learning theory
Keywords:
submodular maximization, sample complexity, PAC guarantees, stochastic greedy, minimax lower bounds, adaptive sampling

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_yzJgOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper considers maximizing a normalized monotone submodular function under a cardinality constraint. Each query has the form (S,i)(S,i) and returns Y=Δf(S,i)+ZY=\Delta_f(S,i)+Z, where ZZ is independent Gaussian noise with unit variance. The question is how many observations are needed to obtain a constant-factor approximation plus an additive error with high probability.

The paper claims a guarantee of (1−1/e)OPT−ε(1-1/e)\mathrm{OPT}-\varepsilon, with probability at least 1−δ1-\delta, using O~(nk2/ε2)\widetilde O(nk^2/\varepsilon^2) scalar observations. It compares this with O~(nk3/ε2)\widetilde O(nk^3/\varepsilon^2) sufficient budgets for earlier methods calibrated to the same guarantee. It also provides a lower bound matching the polynomial dependence, even for additive functions, up to a logarithmic factor. The guarantee does not require a supplied bound on function values.

Critical strengths

One of the strongest aspects of this work is the matching upper and lower bounds: identifying the optimal polynomial dependence n,k,ε−1n,k,\varepsilon^{-1}. Another important aspect of their work is that, their guarantee is with high probability not in expectation which makes their result strong.

Critical weaknesses

Unfortunately, I was unable to fully verify the proofs because I found the exposition difficult to follow. I therefore cannot confidently assess the technical contributions. The introduction and discussion of related work also need substantial improvement before I can assess the novelty and positioning.

The writing needs considerable improvement, and I do not consider the paper ready for publication in its current form. The introduction does not sufficiently motivate the problem. The sentence referring to Lv et al. (2026) and Poiani et al. (2026) seems disconnected from the surrounding discussion; please explain how these works motivate the present problem.

The paragraph “Near-optimal minimax observation cost” is difficult to digest. Please describe the procedure mentioned in lines 51–52 more concretely and explain what “partial recovery” means when it first appears. I could not follow the remainder of the introduction comfortably.

Section 2 presents the results before providing enough intuitive explanation of the algorithm. Although Algorithm 1 and equation (4) specify the procedure and parameters, their roles and choices, particularly the candidate sample size ss, need clearer motivation. Section 3 is short and could be incorporated before Theorems 1 and 2.

In Section 4, I had difficulty understanding how the initial singleton scan, Lemma 3, and the trajectory bound fit together to establish Theorem 1. The proof-mechanism box would benefit from a plain-language explanation of the quantities being balanced.

The explanation preceding Lemma 3 is also too compressed. In particular, please explain the role of the extreme-point reduction and why reducing to distributions supported on at most two points suffices.

I also found Corollary 4 difficult to follow. A brief explanation of the filtration and predictable weights, together with their interpretation in the algorithm, would make the statement more accessible.

I stopped reading at this point. I lean towards rejection in the current form because the exposition prevents me from reliably assessing the arguments and contributions. My confidence in this recommendation is limited. I believe the paper would benefit substantially from revision.

Questions for authors

Please see my comments in the weakness section.

5 comments
AuthorsOpenReview ↗

Response to Reviewer yzJg (Part 1/2)

Thank you for taking the time to review our paper. We have revised the presentation throughout the manuscript, including the motivation, the algorithm description, the transitions between proof steps, and the discussion of related work.

For your convenience, we summarize the main contribution and proof idea here before addressing your specific comments.

Problem and challenge. We study monotone submodular maximization with noisy marginal observations. In applications such as data summarization, reliably comparing items can require repeated observations. For a normalized objective on nn items, we seek a set CC of at most kk items satisfying f(C)≥ρO−εf(C)\ge\rho O-\varepsilon with probability at least 1−δ1-\delta, where O=OPTO=\mathrm{OPT} and ρ=1−1/e\rho=1-1/e. The challenge is to evaluate fewer marginals while retaining the strict approximation coefficient and the high-probability guarantee. When OO is unknown and unbounded, even a small fixed coefficient loss ζ\zeta can introduce an objective loss ζO\zeta O exceeding ε\varepsilon.

Main result. Our algorithm combines an initial singleton scan with random candidate pools. Under independent unit-Gaussian marginal noise, it achieves this guarantee using O~(nk2/ε2)\widetilde O(nk^2/\varepsilon^2) observations, without a supplied objective-value bound. This improves on the O~(nk3/ε2)\widetilde O(nk^3/\varepsilon^2) sufficient budget of full-scan greedy under the same guarantee. A lower bound on additive functions matches this polynomial dependence for 1≤k≤n/81\le k\le n/8, 0<ε≤10 < \varepsilon\le1 and fixed 0<δ≤0.050 < \delta\le0.05.

Key idea. At each step, the mean of the kk largest true marginal gains is at least the remaining gap to OO divided by kk. A pool can miss the best item and still contain a gain above this mean. We analyze these deviations over the whole selection process, allowing gains above this benchmark to compensate for shortfalls in other rounds. The upward bias of maxima of sampled true gains lets us bound the cumulative loss without a separate variance penalty in each round.

The initial singleton scan and the extra margin above ρ\rho in the finite-kk greedy guarantee together provide enough reserve to absorb this loss. Both the guaranteed reserve and the loss bound scale with the largest singleton value, so the unknown scale cancels. We set the estimation precision so that the remaining error is at most ε\varepsilon. The method uses O(nlog⁡(k/δ))O(n\log(k/\delta)) marginal estimates in total, compared with O(nk)O(nk) for full scans at the same precision.

AuthorsOpenReview ↗

Response to Reviewer yzJg (Part 2/2)

We address your specific comments below, with references to the corresponding changes in the revised manuscript.

  • Positioning relative to earlier analyses (Section 6, p. 8). Hassidim and Singer (2017a) concentrate local approximation ratios, whereas our exponential-moment bound controls signed deficits from the top-kk mean, allowing favorable rounds to offset unfavorable ones.

  • Connections to Lv and Poiani (Section 6, p. 8). These citations now appear in the related-work discussion. Lv et al. (2026) exploit a known function representation to accelerate optimization; we study observation cost under noisy marginal access. Poiani et al. (2026) study finite-confidence identification with several valid answers, a feature shared by our approximate selection target.

  • Partial recovery (p. 2). In the additive example, kk hidden items are each worth 4ε/k4\varepsilon/k. Meeting the target requires finding at least (ρ−1/4)k(\rho-1/4)k of them, rather than all kk.

  • Algorithm and candidate size (pp. 3, 5–6). We now explain the algorithm and the choice of ss before the main theorems. Each uniform draw hits a top-kk label with probability k/nk/n. The prescribed s=⌈nL/k⌉s=\lceil nL/k\rceil, with LL of order log⁡(k/δ)\log(k/\delta), gives at least r=⌈4elog⁡(3/δ)⌉r=\lceil4e\log(3/\delta)\rceil hits in each random-candidate round, except on an event of total probability at most δ/3\delta/3.

    In the proof, the first rr uniform draws from the top-kk true gains define a reference maximum, with auxiliary draws supplied if the pool has fewer than rr hits. Conditional on the past, these draws are independent; on the hit event, their maximum is at most the pool's best true gain. The signed deficit in Lemma 3 is the top-kk mean minus this reference maximum. The algorithm does not identify the top-kk labels.

  • Two-point reduction (p. 4). With fixed support and mean, the moment is convex in the probabilities, so a maximum occurs at an extreme point. Three positive masses admit opposite perturbations preserving total mass and mean; an extreme point therefore has at most two. Grid approximation covers general bounded distributions.

  • Filtration and predictable weights (pp. 5–6). The filtration records the growing history before each fresh pool. A predictable weight is known before the current draws; here it is wj=(1−1/k)k−1−j∈[0,1]w_j=(1-1/k)^{k-1-j}\in[0,1] after jj selections. Let aa be the largest singleton value. Conditional application of Lemma 3 bounds the weighted sum of these signed deficits by (2a/r)log⁡(3/δ)≤a/(2e)(2a/r)\log(3/\delta)\le a/(2e), with failure probability at most δ/3\delta/3 (Corollary 4). The remaining δ/3\delta/3 budget covers estimation errors.

We hope these explanations and revisions make the contribution and proof easier to follow.

Dear Reviewer yzJg,

As the discussion period draws to a close, we would appreciate hearing whether the revisions address your concerns about the presentation. Please let us know if you have any further questions or concerns. Thank you again for your time and consideration.

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

This paper studies PAC monotone submodular maximization with noisy marginal feedback. It establishes a near-optimal upper bound of O~(nk2/ε2)\widetilde{O}(nk^2/\varepsilon^2) and a matching lower bound of Ω(nk2/ε2)\Omega(nk^2/\varepsilon^2). The key technical contribution is a trajectory-level analysis using exponential-moment bounds and supermartingales, allowing favorable rounds to compensate for unfavorable ones. The paper also investigates amplitude-dependent complexity and validates the proposed approach through synthetic experiments.

Critical strengths
  1. Rather than requiring a separate high-probability guarantee for each round, the analysis controls cumulative signed deficits, allowing favorable rounds to compensate for unfavorable ones. By combining an exponential-moment bound for sample maxima, a supermartingale argument, and the surplus from the initial singleton scan, the paper obtains a high-probability guarantee for the full adaptive trajectory. I believe this is a substantial methodological contribution in trajectory-level analysis and may be of independent interest for other submodular bandit algorithms.

  2. The paper establishes an upper bound of O~(nk2/ε2)\widetilde O(nk^2/\varepsilon^2) and a matching Ω(nk2/ε2)\Omega(nk^2/\varepsilon^2) lower bound on modular instances, determining the joint polynomial dependence on n,k,ε−1n,k,\varepsilon^{-1} up to logarithmic factors. The result achieves the strict 1−1/e1-1/e PAC approximation guarantee and improves the sufficient sample complexity over fixed-batch threshold greedy by a factor of kk up to logarithmic factors.

Critical weaknesses

None.

Questions for authors
  1. The initial scan plays a key role in the analysis by providing a surplus that compensates for cumulative signed deficits in subsequent rounds. Is this step necessary to achieve the strict (1-1/e) PAC guarantee with (\widetilde O(nk^2/\varepsilon^2)) sample complexity, or is it primarily a feature of the current proof technique? In particular, could a similar guarantee be established using randomized candidate sampling in all rounds?

  2. Could the authors clarify how the proposed signed-deficit analysis differs from existing concentration techniques and trajectory-level analyses in stochastic submodular optimization?

  3. The experiments involve very large observation budgets (up to 10^13 samples). Could the authors discuss whether the theoretical improvements translate into practical gains under more moderate sampling budgets?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 3BBq

Thank you for your positive assessment of the paper. We respond to your questions below and include new results for the smaller-budget setting you asked about.

1. Role of the initial scan. The initial scan plays a key role in our current proof. Whether reduced candidate pools in every round can retain both the strict PAC guarantee and the observation rate remains open. The scan gives a first gain of at least a−2τa-2\tau, where aa is the largest singleton value and τ=ε/(2k)\tau=\varepsilon/(2k) is the estimation tolerance. Combined with the finite-kk greedy surplus, it covers up to a/(2e)a/(2e) of cumulative candidate loss. The lower bound concerns total observations and does not require them to be taken in the first round.

2. Relation to earlier trajectory analyses. The key step is a moment inequality specific to a sample maximum; a supermartingale argument then extends it along the adaptive trajectory. Hassidim and Singer (2017a, Theorem 2) concentrate local approximation factors measured relative to the largest available gain. Our benchmark is the mean of the top kk true gains, μj≥(OPT−f(Sj))/k\mu_j\ge(\mathrm{OPT}-f(S_j))/k.

For an auxiliary maximum WjW_j of r≥2r\ge2 independent draws from these gains, Lemma 3 gives

E[eh(μj−Wj)∣past]≤1,h=r2a.\mathbb{E}\left[e^{h(\mu_j-W_j)}\mid\text{past}\right]\le 1,\qquad h=\frac{r}{2a}.

The maximum's upward bias makes this possible: Wj>μjW_j>\mu_j contributes a negative deficit. Corollary 4 bounds their weighted sum by (2a/r)log⁡(3/δ)(2a/r)\log(3/\delta) with failure probability at most δ/3\delta/3, without accumulating a positive variance term each round. The choice r=⌈4elog⁡(3/δ)⌉r=\lceil4e\log(3/\delta)\rceil makes this bound at most a/(2e)a/(2e), which is covered by the surplus in Q1. Thus favorable rounds offset unfavorable ones in the same run, even as the gain distribution changes with the selected set. We have made this comparison explicit in Section 6 (p. 8).

3. Benefits below the certified budgets. To examine performance below the certified bounds, we added a fixed-budget comparison. It shows an improvement in solution quality at substantially smaller budgets. Candidate uniform and full uniform use the same total cap, initial scan, and uniform allocation rule; only the candidate pool differs. We test n=2048n=2048, k=128k=128, ε=δ=0.05\varepsilon=\delta=0.05, two families, two objective scales and six budgets per setting, with 24 trials per method and condition. A trial succeeds if f(C)≥(1−1/e)OPT−εf(C)\ge(1-1/e)\mathrm{OPT}-\varepsilon.

At OPT/ε=40\mathrm{OPT}/\varepsilon=40 and cap 1.30×1081.30\times10^8, normalized quality f(C)/OPTf(C)/\mathrm{OPT} is:

Instance familyMean: candidate / fullEmpirical 10th percentile: candidate / full
Hidden modular0.2230 / 0.17020.1820 / 0.1328
Layered coverage0.5205 / 0.49860.5039 / 0.4801

At this cap, candidate reduction improves both statistics; both methods remain below the quality target. Near the target, layered coverage at cap 2.08×1092.08\times10^9 gives 22/24 versus 6/24 successful trials. Hidden modular instances at OPT/ε=4\mathrm{OPT}/\varepsilon=4 and cap 5.20×10105.20\times10^{10} give 24/24 versus 8/24.

The comparisons reported above provide empirical evidence that candidate reduction can improve output quality and target attainment at budgets substantially below the certified bounds. Appendix F.5 (Figure 5 and Table 9, pp. 36–37) reports the allocation rule and complete results for all 24 conditions.

Thanks for the response. I will maintain my score.

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

In this paper, the authors study the sample complexity of submodular maximization under noisy bandit feedback in the PAC-learning setting. They propose a polynomial-time algorithm that achieves a (1−1/e)(1-1/e)-approximation up to additive error ϵ\epsilon, with probability at least 1−δ1-\delta, using O(nk2/ϵ2)O(nk^2/\epsilon^2) samples up to logarithmic factors, without knowing the optimal value or an upper bound on the function values. They also establish a matching lower bound up to logarithmic factors, and show that general submodular maximization can require polynomially more observations than additive maximization when the optimal value is restricted to a comparable range.

Critical strengths
  1. The authors study a classical and significant problem of submodular bandit under the pure exploration setting. This is a well-known problem with many applications and is definitely within the range of this conference.
  2. The paper provides both an efficient algorithm and a rigorous sample-complexity lower bound, establishing near-optimal dependence on (n), (k), and (\epsilon) up to logarithmic factors. The analysis also introduces an interesting exponential-moment argument to control cumulative losses from random candidate selection without requiring the algorithm to identify the top-(k) marginal elements.
Critical weaknesses

The authors discuss several related papers but do not provide a sufficiently thorough comparison with these works. One important point that requires clarification concerns the analysis in Appendix D.3, where the authors state that the threshold greedy algorithm requires (O(k/\log k)) passes to terminate. However, my understanding is that the standard algorithm introduced by Badanidiyuru and Vondrák in Fast Algorithms for Maximizing Submodular Functions (SODA 2014) achieves an (O(\log k)) number of passes. If the authors are referring to a different variant of the algorithm or using a different definition of a pass, please clarify this discrepancy in the rebuttal.

Questions for authors

Please reply to the point in the weakness section.

1 comment
AuthorsOpenReview ↗

Response to Reviewer bKYL

Thank you for the encouraging review. We explain the threshold schedule in more detail below, including why the comparison uses a smaller step and how this affects the pass count.

The bound for the fixed-batch threshold-greedy baseline in Appendix D.3 is O(klog⁡k)O(k\log k) passes for a parameter choice that retains the strict ρ=1−1/e\rho=1-1/e coefficient. With a fixed geometric step, the count is logarithmic. A pass means one scan of the remaining items at one threshold; the initial singleton scan is counted separately.

Badanidiyuru and Vondrák (SODA 2014, Algorithm 1) decrease the threshold from the largest singleton value dd to αd/n\alpha d/n, multiplying by 1−α1-\alpha at each step. Their approximation coefficient is ρ−α\rho-\alpha. Our comparison uses the cutoff αd0/k\alpha d_0/k of Chen, Xing and Crawford (UAI 2025), where d0d_0 is the largest singleton estimate. Unless the set fills earlier, this schedule takes

\le\left\lceil\alpha^{-1}\log(k/\alpha)\right\rceil$$ passes. Thus the same cutoff gives $O(\log k)$ passes for constant $\alpha$. The reason for the smaller step is our target, $f(C)\ge\rho O-\varepsilon$, where $O=\mathrm{OPT}$ has no supplied upper bound. For fixed $\alpha$, the $k$-step recurrence certifies a coefficient tending to $1-e^{-(1-\alpha)}<\rho$. This leaves a loss proportional to $O$, which cannot be bounded uniformly by $\varepsilon$. The choice $\alpha=1/(4k)$ suffices: the recurrence factor becomes $1-1/k+1/(4k^2)\le e^{-1/k}$, so after $k$ selections the coefficient is at least $\rho$. Estimation accuracy $\varepsilon/(2k)$ per marginal leaves at most $\varepsilon$ additive loss; the early-stop case also meets the target. Substituting this step into the pass bound gives $H_\alpha\le\lceil4k\log(4k^2)\rceil$. This explains the $O(k\log k)$ scan count behind Table 1's fixed-batch budget. The observation budget is sufficient for the specified fixed-batch implementation and parameter choice. We have made the schedules, pass definition and parameter choice explicit in Section 6 (p. 8) and Appendix D.3 (p. 26). We have also expanded the discussion of earlier trajectory analyses in Section 6. Hassidim and Singer (2017a) concentrate local approximation ratios, while our signed deficits from the top-$k$ mean allow favorable rounds to offset unfavorable ones.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.