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

We thank the reviewer for the positive evaluation of our work. We have thoroughly addressed each of the reviewer’s raised concerns and are eager to engage in further discussion to ensure all remaining issues are resolved.

1. 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.

The runtime is a problematic measure as it highly depends on implementation details and the level of optimization employed, often making comparisons based on this method non-robust. Thus, it is customary in the literature about submodular maximization to use the number of queries to the objective function as a more reliable proxy for the real-world performance of an algorithm. Accordingly, we include in the PDF of the general rebuttal a plot comparing the number of queries used by our algorithm and central algorithms from the literature. Interestingly, the number of queries used by our algorithm is empirically dominated by the queries used for the initialization of the Fast Local search procedure (Line 1 of Algorithm 1). Implementing this initialization in the way described in the submitted paper leads to a query complexity that is somewhat worse than that of other algorithms. However, an alternative implementation of this initialization is implied by a very recent paper [1] that describes a fast ¼-approximation algorithm for maximizing non-monotone submodular functions under matroid constraints (of which cardinality constraints are a special case). When initialized this way, our algorithm becomes much faster (in terms of the empirical number of query calls), while the quality of the solution produced in terms of the objective value remains almost unchanged. We stress that the change in the initialization method only affects the implementation of Line 1 of Algorithm 1 in our paper.

[1] Balkanski, Eric, Steven DiSilvio, and Alan Kuhnle. "Submodular Maximization in Exactly n Queries" arXiv preprint arXiv:2406.00148 (2024).

2. Typos/Writing suggestions/comments

We thank the reviewer for their keen observations. We have addressed your comments and revised the manuscript accordingly.

We would like to thank the reviewer for the detailed review. We hope that our response below addresses all their concerns about the paper. If further clarification is needed, we will be happy to provide it.

1. 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.

As mentioned by the reviewer, our algorithm is based on ideas from [2], and its main novelty is in finding a way to implement these ideas efficiently and practically. As explained in Section 1.1, the work of [10] is an independent parallel work that is also based on [2]. Both works come up with a very similar basic algorithm having a query complexity of O(nk). However, the two works diverge beyond this point. The objective of [10] was to derandomize this basic algorithm and extend it to other constraints. In contrast, our objective was to further speed up the algorithm beyond the above-mentioned query complexity. This additional speed-up is an important technical contribution of our work. For example, getting the local search part of the algorithm of [2] to run fast (as implemented in Algorithm 1) required us to relax the notion of local optimum used and introduce a sophisticated probabilistic analysis deviating from the well-threaded path of analysis of local search algorithms in submodular optimization.

2. 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.

As mentioned by the reviewer, the query complexity of our algorithm is O(n + k^2), which is linear for k = O(n^{½}). For applications that require larger values of k, our algorithm indeed runs in super-linear time, which is unfortunate. Still, one should note two things:

• The PDF of the general rebuttal includes a plot comparing the empirical query complexity of our algorithm with various existing algorithms, including linear query complexity algorithms like the one of [5]. This plot demonstrates that our algorithm compares very well with these algorithms in terms of the empirical query complexity (while outcompeting them in terms of the value of the solution produced).

• The only other algorithm in the literature that guarantees an approximation ratio better than 1/e and has a possibly practical query complexity is the algorithm due to the recent independent work of [10]. This algorithm has a query complexity of $O(nk)$, which is worse than the query complexity of our algorithm except in the regime of k = $\Omega(n)$ (and in this regime the query complexities of both algorithms become identical).

Thank you for your response. I decide to increase my score.

We are grateful for the reviewer’s positive evaluation of our work. In what follows, we address the concerns raised by the reviewer in detail. We will be happy to engage to address any lingering concerns.

1. 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. | Do you have any practical comparisons of the number of query calls used in your experiments?

We thank the reviewer for the insightful suggestion. We have generated graphs depicting the number of query calls, comparing the efficiency of our method with that of our competitors. These graphs can be found in the PDF file of the general rebuttal. Interestingly, the number of queries used by our algorithm is empirically dominated by the queries used for the initialization of the Fast Local search procedure (Line 1 of Algorithm 1). Implementing this initialization in the way described in the submitted paper leads to a query complexity that is somewhat worse than that of other algorithms. However, an alternative implementation of this initialization is implied by a very recent paper [1] that describes a fast ¼-approximation algorithm for maximizing non-monotone submodular functions under matroid constraints (of which cardinality constraints are a special case). When initialized this way, our algorithm becomes much faster (in terms of the empirical number of query calls), while the quality of the solution produced in terms of the objective value remains almost unchanged. We stress that the change in the initialization method only affects the implementation of Line 1 of Algorithm 1 in our paper.

[1] Balkanski, Eric, Steven DiSilvio, and Alan Kuhnle. "Submodular Maximization in Exactly n Queries" arXiv preprint arXiv:2406.00148 (2024).

2. What is the query complexity of your algorithm in terms of epsilon?

The query complexity of our algorithm is $O\left(n * \epsilon^{-2} \log\left(\frac{1}{\varepsilon}\right) + k^2 * \varepsilon^{-1} \log\frac{1}{\varepsilon}\right)$, excluding the query complexity required for obtaining the initial solution $S_0$ for the Fast Local search procedure. The query complexity required for getting this initial solution is independent of epsilon when the algorithm of [1] is used for that purpose, as described in the response to the previous question.

3. 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

Intuitively, Algorithms 1 and 2 balance each other. In a sense, Algorithm 2 uses the output of Algorithm 1 as a “set to avoid”, and its analysis shows that when the output of Algorithm 1 has a poor value, then by avoiding it Algorithm 2 is guaranteed to output a set of good value. Thus, it is guaranteed that the better of the outputs of the two algorithms is always a good solution.

4. Typos/writing suggestions/comments

We have addressed all of the raised comments and suggestions concerning the writing. We are thankful for the keen observation of the reviewer and the fruitful suggestions.

We deeply appreciate the reviewer's meticulous evaluation of our paper. Thank you for your invaluable feedback. In what follows, we address the reviewer’s questions/comments. We will be happy to engage with you to address any lingering concerns

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.

We have addressed the typos raised in the Questions section and will thoroughly pass over the paper to fix any additional types. We thank you for your keen observation.

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 $\frac{1}{e}$ ratio. In doing so, the paper might be more readable to those who haven’t read [2] before.

We thank the reviewer for the fruitful suggestion. We will be more than happy to add such a paragraph to the paper.

3. 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.

Making the recent 0.401-approximation of [3] practical is an interesting question that we have also considered. Unfortunately, this goal seems to be very challenging and requires significant new ideas because the algorithm of [3] has a query complexity that is exponential in 1/epsilon. Notice that this complexity remains exponential even if we assume access to the multilinear extension of the objective function rather than requiring the algorithm to use samples to estimate it. Making the algorithm combinatorial, as we have done in the current paper, can make this assumption justified, but it does not help to alleviate the inherent exponentiality of the query complexity of the other parts of the algorithm.