Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization

Both the results and techniques in this paper are somewhat similar to those in the recent paper (https://arxiv.org/abs/2405.13994). It might be beneficial to explain the relationship between your paper and theirs, especially the difference in the techinique ideas.

Thank you for bringing this paper to our attention; we note that it was released on arXiv after the submission deadline for NeurIPS 2024. Also, we would like to respectfully point out the policy of NeurIPS concerning contemporaneous work.

Indeed, the authors of arXiv:2405.13994 had a similar goal to our work, namely to produce practical algorithms with guarantee larger than $1/e$. It appears to be a case of independent, parallel work. Broadly speaking, the main idea of the two works is similar -- to develop methods to guide the random greedy algorithm with a fast algorithm to find a local optimum. Our local search procedure is deterministic, while theirs is randomized and uses different ideas. Their local search is faster for small $k$ values. They also guide a faster variant of RandomGreedy to achieve their overall time complexity of $O(n + k^2)$.

On the other hand, in our work, we 1) develop a guided algorithm for matroid constraints; 2) for size constraint, we have an asymptotically faster algorithm that uses a novel way of guiding with partial solutions from random greedy itself, which are not local optima, thereby achieving ratio $0.377$ in $O_{\epsilon}(n \log k)$; and 3) we derandomize. For 1) and 2), we had to develop novel recurrences to analyze random greedy, which depart further from the original guiding and analysis of the continuous measured greedy algorithm to achieve ratio $0.385$. Random greedy for matroids is much more like a local search algorithm than a greedy algorithm, as the best swap is made at each iteration. In particular, the guided recurrences stated in Lemmas C.5 and C.6 for the matroid constraint, and their closed form solution in Lemma C.7, as illustrated in Fig. 4. Further, derandomization for the matroid constraint required development of Algorithm 8 and its analysis in Lemma D.1. For 2), we think the use of random greedy to guide itself is interesting, and we believe the resulting analysis (depicted in Fig. 2) aids in the understanding of the random greedy algorithm, perhaps opening up further uses such as bicriteria algorithms, etc. Although the deterministic version has poor dependence on $\epsilon$, this idea might be used to produce a faster randomized version of this algorithm in subsequent work.

In future versions of our paper, we will add a citation to this independent, parallel work and a discussion of the technical relationship.

We thank the reviewer for the thoughtful feedback. We respond to each point below.

Paper Clarity: For the most part, the paper is not well organized and can be challenging to read. With the exception of Section 2.2, the writing is a bit rushed and lacking focus. Many times I had to go back and forth in the paper just to read it. Perhaps the reason for this is that several algorithms are being presented with various guarantees and settings. While the results are great, the paper requires some serious efforts in improving the readability.

We apologize for the difficulty. Due to space constraints, it was difficult to decide what should be presented in the main text vs. the appendices. We decided 1) to limit the main text to the size constraint, as it is more accessible than the matroid constraint, and 2) to try to explain the most important ideas in the main text at a high level, and leave the formal analysis to the appendix. However, this means we sometimes refer to lemmas, etc., in the appendix, which decreases readability. In the next revision, we will make a further refinement in the hope of increasing readibility further and to minimize the necessity of consulting back and forth between the appendices and main text.

The objective functions are not presented and the movie summarization dataset is not discussed.

Due to space constraints, the objective functions for each application, and the movie summarization dataset details are discussed in Appendix F. We will make this more clear in the next version.

It is claimed that max-cut is run on 3 different random graph models -- but then how does only one line appear in the Figure 3c?

In the main text, we only present the results on ER graphs. The results on the other two models are provided in Fig. 6 in Appendix F. We will add references in the experiment section to clarify.

If FastLS + GuidedRG is random, then why does it not also have some uncertainty quantification (i.e. standard error bars) on its objective value and run time?

Thank you for asking this. Interestingly, it turns out that the objective value of our algorithm is usually dominated by the local search subroutine, which is deterministic. Thus, there is little variance in the objective value, which is why the error bars are not visible (they are there). For the runtime, the number of queries of GuidedRG is deterministic. Thus, the number of queries of our main algorithm is deterministic.

The simulations are weak because in all of these instances, the more sophisticated algorithms provide very little improvement over the greedy algorithm. I'm sympathetic to this phenomenon, I know it can happen. But then I think that the experiments should focus on practical instances where the sophisticated algorithms do actually improve over the greedy algorithm.

In our results, we observe an improvement over Greedy of up to 2%, which in our opinion is significant. However, we agree that we could have chosen applications, perhaps weakly submodular ones, in which further improvement on Greedy is possible. Analyzing our algorithms in the weakly submodular case both theoretically and empirically is an interesting avenue for future work.

In addition, Greedy does not guarantee a constant approximation ratio for non-monotone submodular maximization problems. Compared to those algorithms which do provide constant approximation ratio, our algorithm outperforms RandomGreedy with respect to the objective value, and outperforms Lee et al.'s LocalSearch with respect to the query complexity.

We thank the reviewer for the constructive comments.

On lines 73-75, you mention "Unfortunately, there is no known method to derandomize continuous algorithms, as the only known way to approximate the multilinear extension relies on random sampling methods." You may want to revise this sentence because as far as I know, there is a work that proposes estimating the multilinear relaxation of coverage-like functions with Taylor series expansions instead of sampling. Citation: Özcan, Gözde, Armin Moharrer, and Stratis Ioannidis. "Submodular maximization via Taylor series approximation." Proceedings of the 2021 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 2021.

We thank the reviewer for pointing us to this work, which provides an interesting way to approximate the multilinear extension in the case of coverage functions. We will add it to the discussion, and modify the claim as the reviewer suggests.

On line 283, you mention an InterlaceGreedy algorithm for the first time as far as I can tell. Is this a typo or a different algorithm? If it is a different algorithm, where it is described?

We apologize for the confusion. InterlaceGreedy is a subroutine of the InterpolatedGreedy of [11] (number 11 of the bibliography in the manuscript). We develop guided versions of it in Alg. 8 and 9 of the appendix.

On lines 114-115, you mention using an LP method for derandomizing the RandomGreedy algorithm and how this method did not work in this case. Could you please elaborate more on why this was the case? Was the problem asymptotic query complexity or something else?

The LP method relies on a standard lemma for non-monotone submodular functions, which needs a bound on the probability that any element is chosen into the solution. Specifically, Lemma 2.2 of [A] and its generalization in [B]. When the algorithm switches back from the guided behavior to unguided, we were only able to provide a loose upper bound on this probability that wasn't good enough for the analysis. In particular, we had difficulty ordering the the probabilities of the elements in a way that would allow us to apply the lemma. It is possible that a generalization of Lemma 2.2, or a clever way of considering the probabilities is possible and that the LP method could be used.

[A]: Feige et al. Maximizing Non-monotone Submodular Functions. SIAM Journal on Computing 40 (4).

[B]: Buchbinder et al. Submodular Maximization with Cardinality Constraints. SODA 2014.

Why are the dummy elements needed?

We introduce dummy elements to simplify both the pseudocodes and the analysis. The simplification comes from the fact that we may assume that an optimal solution is of size $k$, or a base of the matroid, by adding dummy elements. Moreover, our set $M_i$ in RandomGreedy of the top $k$ marginal gains has $k$ non-negative gains. Otherwise, we would have to allow $M_i$ to potentially be smaller and adjust the probabilities of elements, for example: choose no element with some probability, and one of the remainder uniformly randomly. This would create more cases in the analysis and complicate the picture unnecessarily.