Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint

Summary

The paper studies the problem of approximately maximizing a submodular function under a constraint that the sets can be of size at most $k$. By carefully combining algorithms from previous work and developing them further, the authors obtain an algorithm that guarantees a $0.385$-approximation with $O_\epsilon(n + k^2)$ queries to the function and a user-defined probability of failure. The good performance of the proposed algorithm is demostrated with several experiments.

Strengths

Even though the work relies heavily on previous work as described in the beginning of Sec. 3, their combination appears highly nontrivial to me, and the techniques have been developed further from the previous work. The empirical results demonstrate clear improvements over previous state of the art and appear to have significantly less variance in the output.

Weaknesses

Because of my limited expertise on the topic, my largest complaint is on the presentation of the results: Although the authors do a good job in explaining the ideas behind the math, the formulas are occasionally relatively cumbersome to read, e.g., Line 14 of Algorithm 1. On the other hand, I must admit that I do not have an immediate solution on how to improve them.

Questions

In terms of the running time, i.e., not the number of queries, how does the proposed algorithm compare against the state of the art? Because the running time depends on, for example, $epsilon$, it is not immediately clear to me how large the constant factors of the algorithms would be. Other: - Abstract: Without previous background on the topic, it was unclear to what $k$ and $n$ referred to in the abstract. - Lines 29–32: first, $B$ is a subset of $A$, but then $A$ is a subset of $B$. This can be confusing to the reader. - Line 66: If I understood the paper correctly, I think it would be more precise to use $O_\epsilon$ instead of the $O$-notation here (although a constant $\epsilon$ is used in the experiments) - Caption of Alg. 3: maximiziation -> maximization - Line 172: OPT is not written with \mathbb

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Since the paper focuses on a optimizing a method that is used in ML applications and does not study application directly, I think the limited discussion of limitations is sufficient here.

Summary

The paper introduces a new algorithm, FAST-LOCAL-SEARCH, for maximizing non-monotone submodular functions, achieving a 0.385-approximation with low query complexity. It combines initial solution search, accelerated local search, and stochastic greedy improvement steps to outperform existing algorithms in machine-learning applications like movie recommendation, image summarization, and revenue maximization. The algorithm guarantees a constant approximation to the optimal set and is supported by theoretical proofs and empirical evaluations.

Strengths

The paper introduces an algorithm, FAST-LOCAL-SEARCH, for maximizing non-monotone submodular functions under a cardinality constraint. This algorithm combines initial solution search, accelerated local search, and stochastic greedy improvement steps to achieve a 0.385-approximation with query complexity of O(n + k^2). The practical performance of the algorithm has been validated in real-world applications.

Weaknesses

The novelty of the paper is limited. The idea of this paper is derived from existing work [2], and more significantly, the "guided algorithm" proposed in this paper is very similar to [10] in both algorithm design and theoretical analysis. The authors claim that the algorithm proposed in this paper has a practical query complexity of O(n+k^2); however, in practical applications, the value of k is often very large, making an O(k^2) query complexity potentially impractical.

Questions

Please refer to weaknesses.

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

N.A.

Summary

This work addresses the problem of maximizing a non-monotone submodular function subject to a cardinality constraint. In submodular maximization, we have a set of elements (ground set) and a function that assigns a value to any subset of elements. A function is submodular if adding an element to a smaller set contributes more value than adding it to a larger set. Formally, for sets A and B where A is a subset of B, adding an element x to A increases the function value more than adding x to B. A function is monotone if its value always increases with set size. Non-monotone functions don't necessarily have this property. The goal here is to find a subset of size at most k from the ground set that maximizes the value of the non-monotone submodular function. While they developed a 0.385-approximate solution for this problem, there is an algorithm with a better approximation factor of 0.401. Another work also achieves a 0.385-approximate solution, but both are impractical due to the high number of query calls required. In contrast, this work uses only O(n+k^2) query calls. Additionally, there are two works with a 0.367-approximation, one requiring O(nk) query calls and the other O(n) query calls. In the experiment section, the authors compared the output value of their algorithm with those of the two latter algorithms. The core idea of the proposed algorithm involves: - Running the sample greedy algorithm by Buchbinder et al. [5]. - Applying a local search technique to improve the initial solution. - Employing a Stochastic greedy method and returning the solution with the highest value between the local search and Stochastic greedy outputs. This approach leverages existing techniques while incorporating additional steps to enhance the solution within a reasonable computational cost.

Strengths

For non-monotone submodular maximization under a cardinality constraint, their work achieves the best query complexity for algorithms that attain at least a 0.385-approximate solution. In other words, among practical algorithms—those that can be implemented and executed in a reasonable time—they offer the highest approximation factor.

Weaknesses

Since their algorithm does not have the best approximation factor, it is less interesting for theoretical work and more important for practical applications. Therefore, a comprehensive experiment supporting their claims is crucial. While they did a great job by running experiments on different problems and demonstrating the advantage of their output value compared to two other algorithms with worse approximation guarantees, it is also necessary to plot the number of query calls for these algorithms. Comparing the number of query calls in addition to the output value is essential, as they claimed to have the best approximation algorithm with "a low and practical" query complexity. ### Comments for the authors: - Line 43: Remove “over” - Line 50: I think [14] present a ½-approximation algorithm for symmetric submodular functions and for non-symmetric, they only achieve a ⅖-approximation algorithm. - Line 68: Do you mean “3 applications”? - Line 149: Remove “)” after “pn” - Line 208: Replace “she is” with “they are” - Line 548: Replace “lemmata” with “lemmas” The revenue maximization experiment is mostly known as the max-cut problem. I think it is good to at least mention that. - In Algorithm 3, the term “AIDED-MEASURED DISCRETE STOCHASTIC GREEDY” has been used to refer to Algorithm 2. However, the name of Algorithm 2 is different. - From lines 95 and 96, I assumed that Algorithm 2 improves the output of Algorithm 1. However, after reading the algorithms, it seems that Algorithm 2 finds a different

Questions

- What is the query complexity of your algorithm in terms of epsilon? - Do you have any practical comparisons of the number of query calls used in your experiments?

Rating

6

Confidence

4

Soundness

2

Presentation

4

Contribution

2

Limitations

N/A

Summary

The paper presents a practical $0.385$-approximation algorithm using $O(n+k^2)$ queries for non-monotone submodular maximization under a cardinality (size) constraint, where $n$ is the number of elements in the ground set and $k$ is the maximum size of a feasible solution. As a comparison, the state-of-the-art algorithms attain a $0.401$ approximation ratio with a high number of queries, or $1/e-\epsilon$ approximation ratio using $O_{\epsilon}(n)$ queries. The paper also evaluates its method experimentally on several applications.

Strengths

1. The paper makes a substantial progress for the studied problem by presenting a new algorithm with low query complexity and improved approximation ratio. The algorithm is obtained by carefully combining several well-known techniques and methods in the field. Such a result already contains enough originality as a NeurIPS submission. 2. The paper is complete, in the sense that it contains both a correct theoretical analysis and detailed experimental evaluations of its algorithm. 3. The paper is organized well. It splits the algorithm into several ingredients and then explains each part in detail and how to combine them to get the final result. In such a way, it’s easy for readers to follow the basic ideas and check the correctness of the algorithm. 4. The paper, as suggested by the experiments, provides a better solution for several important applications. On the other hand, it further exploits several mature techniques in the field, which may inspire more results in the area.

Weaknesses

1. There are many typos in the proofs (see Questions for some examples), which affects the clarity. The authors are suggested to proofread their paper in a later version. 2. The main algorithmic framework is borrowed from [2]. So, if the space is enough, I suggest the authors to add a paragraph discussing why the framework can beat the $1/e$ ratio. In doing so, the paper might be more readable to those who haven’t read [2] before.

Questions

1. I’m curious about if it’s possible to discretize the algorithm in [3] to get a practical $0.401$ algorithm, just like this paper. 2. Following are some typos: 1) I suggest using “at most” to replace “at max” in the paper. 2) Page 13. “Let S be a subset in N of size at (missing most) k”. 3) Page 16, Lemma A.3, $x_{\in}$ --> $x\in$. 4) Page 16, in the last inequality, \beta^{i} should be \beta_{i}. 5) Page 17, in the first formula, A\cup B_{\lambda}\cap Z should be A\cup B_{\lambda} ‘\cup’ Z. 6) Page 18, Lemma B.1, “that starts returns a set…” doesn’t read smoothly. 7) Page 18, in the first sentence of the proof of Lemma B.1, S_{i,j} should be S_i^j. 8) Page 20, in inequality (6), the subscript L should be i.

Rating

7

Confidence

5

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes

Thank you!

We sincerely thank the reviewers for their careful reading, insightful comments, and active engagement during the authors-reviewers rebuttal period. Your feedback has been invaluable in enhancing our paper, and we greatly appreciate your input. Best regards, The Authors.