Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers the problem of maximizing a monotone submodular function under matroid constraints when the value queries have independent random noise drawn from generalized exponential tail distributions. The first result is for uniform matroid constraints (aka cardinality constraints). Here, the new result improves on existing work in that the cardinality range over which it applies is larger than that of previous work while preserving polynomial dependence of query complexity on the approximation parameter $\epsilon$. Prior work either applied only to larger cardinality values $\Omega(\log \log n/\epsilon^2)$ against $\Omega(1/\epsilon)$ or required exponential dependence of query complexity on $\epsilon$. The second result is for general matroid constraints and obtains a constant approximation. Prior work had not considered general matroid constraints in maximizing submodular functions in the noisy setting.

The main technique is to use local search where each step swaps a single element. Prior work for noisy submodular maximization mostly used variants of the greedy algorithm. The local search algorithm is an adaptation of prior work by Filmus and Ward for exact queries, and the optimization function used for local search is also a robust version of the function used by FW.
strengths_and_weaknesses: Strengths:

1. Submodular function maximization is an important classical problem with applications spanning many areas.

2. The paper gives the first results for submodular maximization under general matroid constraints in the noisy setting. Without noise, this is a standard setting in which submodular maximization is studied, so this is a good research direction in general. The approximation constant doesn't appear very impressive, but as the first paper considering this problem, it provides a good start.

3. The adaptation of the local search technique to the noisy setting might be useful in general. Local search is used in many contexts and constructing a robust version in the presence of noise might have value beyond the results in this paper.

Weaknesses:

1. The techniques employed in this paper are not very novel. The adaptation of the FW algorithm is fairly straightforward, and as such, the paper does not contribute much in terms of new techniques.

2. The noise model comes across as quite limited, and the paper does not include a discussion on it. It is true that a couple of previous papers also considered the same noise model, but I feel it would be useful to discuss the contexts in which this type of noise distribution is relevant.
questions: I do not have specific questions.
limitations: The paper includes a discussion of limitations at the end, but it seems largely perfunctory. As I mentioned above, it would be interesting to have a longer discussion about the noise model with its application scenarios and limitations, for instance. Also, are the cardinality bounds in this paper tight? If not, what are the challenges in removing this constraint altogether? Discussions of this sort would help make the paper a more engaging read.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of maximizing a submodular set function when function values are given by a noisy oracle. The authors propose 2 novel auxiliary functions which can be queried efficiently in order to improve the algorithms' candidate solutions via local search. The approach for cardinality constraints is then extended to work with matroid constraints.
strengths_and_weaknesses: ## Originality/ Significance
- Interesting theoretical contributions which lead to more practical ways to handle noisy function evaluation
- Cites previous related work where appropriate

## Quality
- Smoothing surrogate auxiliary functions appear to be a novel, elegant approach that leads to exponential improvement in query complexity compared to previous work

## Clarity
- This paper is generally well organized. However I have 2 small suggestions:
    - State the note after Theorem 3.3 as a separate corollary, showing intermediate steps in the Appendix. this is important because subsequent theorems appear to include an extra $\log r$ term 
    - The second paragraph of related work on noise-free optimization with more complex constraints is not relevant to the paper. This could be moved to the Appendix or removed altogether
- "approximate ratio" is used throughout the paper where "approximation ratio" is more standard

questions: - Can the surrogates be used in the noise-free setting to improve the query complexity of local search? Does this improve on the guarantees in reference [5] or simply generalize them when the oracle has noise?
- Is there a clear mapping from noise parameters $c_i$, $\gamma_i$ to auxiliary function constants $\alpha$, $\delta$?

[5] Yuval Filmus and Justin Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM Journal on Computing, 43(2):514–542, 2014.
limitations: This paper describes limitations as opportunities for future work, but does not address any potential negative social impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper focuses on the problem of monotone submodular maximization subject to matroid constraints, when the function is only accessible through a noisy oracle. In particular, they provide an algorithm that with high probability outputs a solution with near-optimal (1 - 1/e - O(\epsilon)-approximation guarantee. Notably, they deliver this result with a polynomial computational complexity in 1/\epsilon, while the current works in the literature have an exponential complexity. 
strengths_and_weaknesses: Strengths:
(a) The paper studies an interesting generic problem with broad applications in the data mining and machine learning areas. 
(b) The paper is very well-written and easy to follow. In particular, the authors make the transition into their main results smooth by providing sufficient intuitive explanations and motivations. Moreover, they justly credit the related the works and clearly distinguish their contributions from the existing methods or definitions. 
(c) They provide strong results and considerable improvements over the state-of-the-art. 

Weaknesses:
Overall I find the results quite strong. I just have few minor comments on the presentation of the results, which I state under the Questions. 
 
questions: The claims that presented earlier in the paper in a less formal manner can be a bit misleading and undermine the main results of the paper. For example:
(a) In the abstract, it is stated that the algorithm provides a 1 - 1/e - O(\epsilon) guarantee without introducing \epsilon. It is my understanding that this \epsilon is an arbitrary value (given Theorems 5.1 and 5.2). If so, could the authors please clear this up in the abstract? As otherwise the provided bound can be quite far from the optimal. 

(b) In Theorem 1.1, the success probability of the algorithm is stated to be 1 - O(1). However, given Theorems 5.1 and 5.2, it seems that this is not correct as the probability either depends on n or \epsilon and is not a constant. 
limitations: Yes.
review_title: null

Meta-review: metareview: Overall, this paper studies an important problem and obtains strong results. There were some concerns raised by one reviewer regarding the novelty of the techniques and the lack of discussion regarding the noise model. Please make sure to add the discussion about the noise model from the rebuttal in the camera ready version of the paper.
confidence: Certain
Decision: Accept