- 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 and returns , where 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 , with probability at least , using scalar observations. It compares this with 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 . 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 , 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
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- 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, hidden items are each worth . Meeting the target requires finding at least of them, rather than all .
-
Algorithm and candidate size (pp. 3, 5–6). We now explain the algorithm and the choice of before the main theorems. Each uniform draw hits a top- label with probability . The prescribed , with of order , gives at least hits in each random-candidate round, except on an event of total probability at most .
In the proof, the first uniform draws from the top- true gains define a reference maximum, with auxiliary draws supplied if the pool has fewer than 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- mean minus this reference maximum. The algorithm does not identify the top- 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 after selections. Let be the largest singleton value. Conditional application of Lemma 3 bounds the weighted sum of these signed deficits by , with failure probability at most (Corollary 4). The remaining 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.
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 n items, we seek a set C of at most k items satisfying f(C)≥ρO−ε with probability at least 1−δ, where O=OPT and ρ=1−1/e. The challenge is to evaluate fewer marginals while retaining the strict approximation coefficient and the high-probability guarantee. When O is unknown and unbounded, even a small fixed coefficient loss ζ can introduce an objective loss ζO exceeding ε.
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) observations, without a supplied objective-value bound. This improves on the O(nk3/ε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/8, 0<ε≤1 and fixed 0<δ≤0.05.
Key idea. At each step, the mean of the k largest true marginal gains is at least the remaining gap to O divided by k. 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 ρ in the finite-k 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 ε. The method uses O(nlog(k/δ)) marginal estimates in total, compared with O(nk) for full scans at the same precision.