Summary and Contributions: Contribution: The paper gives a new deterministic algorithm for maximizing a non-monotone submodular function subject to a matroid constraint. The algorithm achieves a 1/4 approximation and it has a running time of O(n r), where n is the size of the ground set and r is the rank of the matroid. Using known techniques, one can speed up the algorithm to nearly-linear at a small loss in the approximation. Comparison to previous work: Previously, there were two main approaches for obtaining deterministic algorithms for the problem. The first approach, due to Lee et al., uses local search and it obtains a 1/4 - eps approximation but the running time is a much larger polynomial (at least n^4). Another approach, due to Gupta et al., uses achieves the same running time as the proposed algorithm but achieves a weaker approximation of 1/6. It is instructive to compare the algorithms of Gupta et al. and the proposed algorithm. The former algorithm first constructs a solution A by running the standard Greedy algorithm for monotone maximization on the entire ground set, then it constructs a second solution B by running the Greedy algorithm on the complement of A, and finally it constructs a third solution C by running an algorithm for unconstrained maximization on A, and returns the better of the three solutions A, B, C. In contrast, the proposed algorithm simultaneously constructs two disjoint solutions using the Greedy algorithm; if an element can be feasibly added to both solutions, it is added to the one with higher marginal gain. Using a very simple but careful analysis along the lines of the standard Greedy analysis, the paper shows that the algorithm achieves a 1/4 approximation. The work [11] gives a fast randomized algorithm RandomGreedy and show it achieves a 1/4 approximation, and the work [14] derandomizes the same algorithm. An approximation guarantee is not provided in [14] for non-monotone functions, it would be interesting to see whether such an analysis can be obtained. Compared to the derandomized RandomGreedy, the algorithm proposed in this work is faster by an r factor. Novelty: The algorithm is very simple and natural, but it is a novel contribution to the line of work devoted to obtaining fast deterministic algorithms for non-monotone functions. The analysis is very simple but insightful. === After the author feedback === I have read the author feedback. I agree with the authors that the randomized algorithms are not necessarily fast and there is a clear running time advantage for the proposed algorithm.
Strengths: The paper introduces a novel deterministic algorithm for submodular maximization with a matroid constraint. This is a topic of interest to the theory community and the result is nice and simple. The relevance to the ML community seems much more limited.
Weaknesses: The contribution is primarily of theoretical interest, since it focuses on deterministic algorithms and algorithms with matching or better approximations are known if randomization is allowed. There is a clear running time advantage for the proposed algorithm though.
Correctness: I checked the proofs in detail and I think they are correct.
Clarity: Yes.
Relation to Prior Work: Yes.
Reproducibility: Yes
Additional Feedback:
Summary and Contributions: The authors consider the problem of maximizing a (non-monotone, non-negative) submodular function subject to a matroid constraint. They develop a deterministic algorithm TwinGreedy that achieves a 1/4 approximation, which is the state-of-the-art for deterministic algorithms. They then modify their algorithm to achieve a 1/4 - epsilon approximation in time O(n log r / epsilon), where r is the rank of the matroid. Their analysis can be extended to p-systems as well. The authors then consider how their algorithm performs in practice.
Strengths: The algorithm proposed is practical to implement, deterministic, and efficient while achieving a provable approximation guarantee. In my experience, deterministic algorithms are preferred when possible as they lead to more stable solutions -- even if they do not improve the objective value much over randomized algorithms. The algorithmic framework is novel to the best of my knowledge and may be able to be applied to other problems. The authors achieve good practical performance with their algorithm. They achieve an objective value very close to the baseline considered with about two orders of magnitude fewer function evaluations.
Weaknesses: I don't have any major issues with the paper. For Fantom, there are randomized linear time algorithms that achieve a 1/2 approximation for unconstrained submodular maximization. How would performance change if this was used instead of the 1/3 approximation algorithm used in the paper?
Correctness: I skimmed through the proof of the main theorem and it seems correct. The experimental section also seems sound.
Clarity: The related work, description of the algorithm, and description of the experiments are clear and well written. The bar graphs in the experiments are poorly designed. At first I thought SampleGreedy was better than TwinGreedy. The bars in the key go in a different direction than the bars in the graph. At first I rotated the bars in the key to align with the bars in the graph but after reading the text I realized this was wrong. Please change how the algorithms are distinguished. The use of O1, ..., O8 in the proof is confusing. I would prefer more descriptive symbols based on the relationship between the symbols. For example, O_1 and O_2 differ only in using $\in$ or $\notin$, O_1 and O_3 differ only in swapping 1 and 2. Perhaps using superscripts + and - can distinguish between O_1, O_2 and O_3, O_4 and subscripts can distinguish between O_1, O_3 and O_2, O_4.
Relation to Prior Work: The authors do a detailed comparison of related algorithms and how they compare in runtime, approximation guarantees, and deterministic/random.
Reproducibility: Yes
Additional Feedback: How does the performance of the FastTwinGreedy algorithm change as epsilon changes? Is it possible to outperform Fantom with a different choice of epsilon? How about with TwinGreedy? What is the intuition for why the approximation holds for TwinGreedy but not regular greedy? What happens if rather than two sets you have three or more sets competing? In the experiment section, is there any reason to suspect that wall clock time would differ from number of queries?
Summary and Contributions: The paper gives two deterministic algorithms achieving roughly 1/4 approximations to submodular maximization under a matroid constraint, crucially without monotonicity. Crucially these algorithms are much more efficient than the state of the art. The algorithms also recover the known monotone 1/2 approximations (which is almost the state of the art approximation). The techniques used are a very clever idea of constructing two sets simultaneously which allows for comparison against the optimum.
Strengths: I enjoyed this paper a lot. I think the ideas are very clever and also very natural, and put together in an effective way. The proofs, while a bit tedious, are fairly straightforward and I think the ideas used to compare the two sets to the optimal are innovative and bring new directions to algorithm design in this area.
Weaknesses: I did feel that there could be more guiding text in general. It took several reads to understand what many of the lemmas are trying to do, even though the structure of the arguments themselves can be described in a few words. For instance, Lemma 1 is largely just an appeal to matroid basis exchange properties, and Lemma 2 is largely just using definitions and submodularity. The paper is understandably quite notation heavy, but I feel the names given to the sets can be a bit more descriptive than e.g. O_i for i = 1, 2, 3, 4, 5, 6, 7, 8. The proof of Lemma 1 is algorithmic and it might be helpful for the reader to actually see the algorithm. Finally, I had a (possibly somewhat mild) concern about the additional assumptions of non-negativity of the function f and that f(0) = 0. I saw that several of the prior works also make the assumption that f is non-negative -- is this necessary? As I am a bit unfamiliar with the literature, what algorithms / guarantees are known when this non-negativity assumption is lifted? I also couldn't see where the assumption f(0) = 0 was used, but it is possible I just missed something.
Correctness: I believe the claims are correct.
Clarity: The paper is fairly easy to follow, but as I stated above my main concern is that it is extremely notation heavy with a minimal amount of guiding text. That being said, I think a little bit of guiding text would significantly improve the readability (as the ideas and proof strategies themselves are very natural).
Relation to Prior Work: Yes.
Reproducibility: No
Additional Feedback:
Summary and Contributions: This paper proposes a deterministic 1/4-approximation algorithm for non-monotone submodular maximization with a matroid constraint that runs in O(nr) time. Also, the authors accelerate the algorithm and extend to p-set sytem constraints.
Strengths: This paper proposes TwinGreedy algorithm that returns a 1/4-approximate solution for non-monotone submodular maximization with a matroid constraint and runs in O(nr) time, where n is the size of the ground set and r is the matroid rank. This problem has been attracting a lot of attention as an important problem on subdmoular maximization and many kinds of approximation algorithms have been designed. TwinGreedy algorithm is basically a standard greedy algorithm but keeps two solutions. Its analysis is quite non-trivial and, to my knowledge, is not similar to any existing method. By utilizing the thresholding method proposed by Badanidiyuru and Vondrak (2014), the authors also propose TwinGreedyFast, which is an accelerated version of TwinGreedy algorithm. It is just a straightforward application of the existing idea, but it is practically absolutely efficient as illustrated in the experiment section. These results are extended to p-set system constraints (it is called p-system in most of the literature). The approximation ratio is 1/(2p+2). Compared to the existing (1/(p+2sqrt(p)+3)-eps)-approximation algorithm with O((nr+r/eps)sqrt(p)) time, the proposed one is always faster and achieves better approximation for small p. Since p-set systems include many important constraints, this algorithm would become a standard approach to non-monotone submodular maximization problems.
Weaknesses: The result (deterministic 1/4-approximation in O(nr) time) is the fastest among all deterministic 1/4-approximation algorithms, but it is hard to say this result is ground-breaking. There already exists a deterministic 1/4-eps approximation algorithm by Lee et al. and a randomized 1/4-approximation algorithm that runs in O(nr) time by Feldman et al.
Correctness: I briefly checked all the proofs. They seem to be correct.
Clarity: Overall, this paper is well written. The proofs are clearly presented.
Relation to Prior Work: There are several existing algorithms for non-monotone submodular maximization with a matroid constraint. In my opinion, this paper sufficiently sumamrizes these results. Since the result by Buchbinder and Feldman [10] is the best randomized approximation for this problem, it would be helpful if the authors add it to Table 1 though it is mentioned in related work section.
Reproducibility: Yes
Additional Feedback: # Update after the author feedback The authors clearly responded to the questions raised in my review. I agree with the acceptance of this paper.