Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors of this paper propose a linear-time algorithm for maximizing monotone and submodular functions under knapsack constraints. The proposed algorithm extends the threshold-greedy algorithm for cardinality constraints. Besides the theoretical results, the authors also provide experimental results to demonstrate the advantages of the proposed algorithm compared to SOTA algorithms.
strengths_and_weaknesses: 1. The proposed algorithm has linear time complexity and a strong approximation ratio.
2. The authors also provide strong information-theoretic lower bounds for the problem studied in this paper.
3. The authors conduct experiments on real-world datasets to show the practical advantages of the proposed algorithm to SOTA algorithms.
questions: Is the DENSITYGREEDY algorithm in experiments also accelerated by the Lazy Greedy idea?
limitations: 1. This paper discusses the situation of minimizing the number of queries to the objective function. In many important applications of submodular optimization, such as influence maximization, we may first generate a sketch data structure that can well approximate the objective function and evaluating the approximate function value is not that computational expensive. It would be better if the authors could discuss something about this in Conclusion.
2. One another interesting point is that the objective submodular function is often hard to compute exactly. What if we only have a noisy oracle of the function value? Is the proposed algorithm robust to a noisy oracle?
3. A minor issue. After Observation 3.3, the authors say "Let l be the value of k". I guess here "k" should be "h" since there is no parameter k in Algorithm 1.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies (mainly monotone) submodular maximization subject to various types of constraints. In particular, the authors focus is on deterministic algorithms that achieve constant factor approximation to the optimal solution while needing only linear time to terminate. 

The main contributions of the paper are: 
- a deterministic $(1-1/e-\varepsilon)$ approximation algorithm for monotone submodular maximization subject to cardinality constraint with $O(n/\varepsilon)$ running time
- a deterministic $(\frac 12 - \varepsilon)$ approximation algorithm for monotone submodular maximization subject to knapsack constraint with $O(n/\varepsilon \log(\frac{1}{\varepsilon}))$ running time

To complement these positive results, the authors construct information theoretical lower bounds that show how $\tilde\Omega(n)$ running time is needed to get constant factor approx for monotone submodular maximization with cardinality constraint and unconstrained non-monotone submodular maximization. For the former problem, it is also shown that when k is of the order of n, then no algorithm can do better than random sampling. 

Finally, the authors extend their techniques and design fast algorithms for monotone submodular maximization with a very general class of constraints, namely set system and multiple knapsack constraints. 

strengths_and_weaknesses: Achieving fast algorithms for submodular optimization is a rich and exciting line of research motivated by the applications and it is definitely within the scope of the conference.

As it is common in submodular maximization, many of the techniques used in this work are a careful combination of well known ideas and I do not think this is a limit of the paper. I particularly like Algorithm 4: although simple, it is crucial to argue that a constant number of thresholds is enough and I think it can be used in many other contexts. To the best of my knowledge it is original, but I might be mistaken. I also like the lower bounds: they are not surprising, but I am pretty sure they will be cited in future works. 

On the negative side, the actual contribution of the paper seems a bit marginal. Linear time algorithms (although randomized) already exists for cardinality constraints, while for knapsack it is easy to see that a straightforward algorithm like density greedy + lazy updates already yields a constant factor approximation in O(n log n) iterations, so the improvement consists in shaving the extra log factor.

Although I have not checked in detail all the proofs, the claims are well supported. The paper is fairly well written and clear.

The related work section is very rich. I would just mention that the authors might want to spend some words on the case of non monotone objectives, for cardinality constraint see e.g. Kuhnle AAAI21, while for knapsack see Amanatidis et al. NeurIPS 20.

questions: In the experiments with knapsack, is density greedy implemented with lazy updates? If not, why? Using lazy updates brings the computational complexity from $O(n^2)$ to $O(n \log n)$
limitations: Other comments to the authors: 
- please, state from the abstract that the positive results only apply to monotone objectives
- line 40 is submodular and not submodualr
- please mention in the preliminary that you are considering the value oracle model
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this submission, the problem of maximizing a submodular function subject to a knapsack constraint is considered, where the function is accessed by an oracle. There is a lot of literature on this problem and several approximation algorithms are known. In this paper, an approximation algorithm with a guarantee of 1/2-eps is developed whose running time is linear in n. This does not improve the best previously known approximation factor (which is 1-1/e) but it is the first algorithm with this approximation factor that runs in linear time. For the special case of a cardinality constraint the factor improves to 1-1/e-eps. 

The algorithmic result is complemented by information-theoretic lower bounds. It is shown that a linear number of function evaluations are needed to obtain a constant approximation guarantee even in the case of a cardinality constraint. This lower bound is true if the number k of allowed elements is constant. If it is a constant fraction of the size n of the ground set then Omega(n/log(n)) function evaluations are shown to be necessary to achieve a constant approximation.

The theoretical results are supported by experimental results showing that the designed approximation algorithm outperforms baseline algorithms from the literature.
strengths_and_weaknesses: The algorithm is very clean and natural and the proof of the approximation guarantee is easy to follow. I very much enjoyed reading this part of the submission. However, this part is also close to existing literature and many ideas in this part are taken from existing literature. A weakpoint is, of course, that the approximation ratio is only 1/2-eps and not 1-1/e-eps (which is known to be achievable in polynomial time). The lower bounds are rather involved but quite interesting. The experiments are clearly not the main focus of the submission and I would rather see them as a proof of concept that the algorithm works in practice but not as a thorough evaluation. For example, the two baselines are natural but it is never argued why exactly these algorithms are chosen as baselines and not other algorithms.
questions: l 40: "submodualr" -> "submodular"
l 50: "makes is impractical" -> "makes is impractical"
l 130: definition of f(T|S): I think f(T) should be f(S).
l 183: "where" -> "were"
page 15, last line: "forall e in ..." -> "forall u in"
limitations: n.a.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies the problem of submodular maximization under cardinality/knapsack constraints and provides fast $\mathit{deterministic}$ algorithm for the problem. The submodular maximization problem is a well-studied problem, where a set function $f$ defined over a ground set of n element, the set function is assumed to monotone and submodular (i.e., $f(A \cup \{u\} - f(A) \geq f(B \cup \{u\}) - f(B)$ for any set $A\subseteq B \subseteq [n]$ and element $\{u\}$). The goal is to maximize the function value, for cardinality constraints, the algorithm is allowed to select up to k elements, while for knapsack constraints, the algorithm is allowed to select ground set element with a knapsack constraints (each element is associated with some cost).

To summarize, the paper designs deterministic algorithm that achieves

(1) Under a knapsack constraint, it achieves $(1/2 -\epsilon)$ approximation in $O(n\epsilon^{-1}\log(1/\epsilon))$ times. The approximation ratio is not the state of art, as mentioned in the paper, as [Ene and Nguyen ICALP'19] proves a $(1-1/e -\epsilon)$  approximation algorithm, with linear time, but the dependency on $\epsilon$ is bad, i.e., $O((1/\epsilon)^{\epsilon})$.

(2) Under cardinality constraints, it achieves $(1-1/e-\epsilon)$-approximation using $O(n/\epsilon)$ oracles. The approximation ratio is optimal, but the stochastic greedy algorithm (a randomized algorithm) has better oracle complexity of $O(n\log(1/\epsilon))$. A nearly lower bound is also proved in the paper (but I am not sure whether these are folklores...)

(3) Constant approximation under multiple knapsack constraints.

(4) Extensive experiments showing the effectiveness of the algorithm

From a technical perspective, the algorithm is based on greedy algorithm with decreasing threshold. While for knapsack constraints, post processing is needed.



---------------------- Post rebuttal ------------------
After a few rounds of discussion with the author, I believe I convince the author that my main concern is (1) the significance of lower bound (I still believe it is more like a folklore result, but nice effort to write it down) and (2) the deterministic algorithm provides in the paper is not so exciting for an acceptance (I understand there are two or three paper in the area to develop deterministic algorithm).



strengths_and_weaknesses: Strength. The algorithm presents state of art $\mathit{deterministic}$ algorithm for the classic problem of submodular maximization with cardinality constraints and a knapsack constraint. The experiments show the algorithm is practical, which is very nice!


Weakness. There is no reason one restricts to deterministic instead of randomize algorithm, this decreases the value of the paper a lot.
questions: In line 365--366, it is claimed that the paper fully resolve the landscape of oracle complexity of submodular maximization, it seems too strong for me. After all, only deterministic algorithm is considered in this paper.
limitations: no
review_title: null

Meta-review: metareview: Overall, this paper achieves strong and interesting results regarding the query complexity of submodular maximization. One reviewer was concerned that the lower bound result was maybe a folklore result that is easy to prove. However, sufficient evidence to justify that claim was not provided and other reviewers did not share the same concern.
confidence: Less certain
Decision: Accept