Non-monotone Submodular Maximization in Exponentially Fewer Iterations
In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily close to 1/2e in O(log 2 n) adaptive rounds, where n is the size of the ground set. This is an exponential speedup in parallel running time over any previously studied algorithm for constrained non-monotone submodular maximization. Beyond its provable guarantees, the algorithm performs well in practice. Specifically, experiments on traffic monitoring and personalized data summarization applications show that the algorithm finds solutions whose values are competitive with state-of-the-art algorithms while running in exponentially fewer parallel iterations.
The authors consider the parallel complexity of non-monotone submodular maximization subject to a cardinality constraint. They develop an algorithm for this problem and they are able to show it has a (1 / 2e)-factor optimization for this problem in polylog(n) parallel rounds. They experimentally observe that their algorithm is able to achieve a good approximation in far fewer rounds.  The theoretical results of this paper are very strong. It is typically difficult to obtain good approximation guarantees for non-monotone functions.  The paper is well written.  The author's algorithm is a tweak of the algorithmic framework proposed in [BS18a, BS18b, BRS18]. Some of the proof ideas are similar to BRS18. The authors should better differentiate the proof for this problem by discussing the difficulties unique to this problem.  One important experiment missing is running a real parallel or distributed implementation of the algorithm and observing how well the algorithm parallelizes in practice. How does the performance improve with the number of processors and how does this compare to parallel implementations of other algorithms such as the greedy algorithm?  The guess-and-check idea for the algorithm is related to the algorithm in the following work: Badanidiyuru, Ashwinkumar, et al. "Streaming submodular maximization: Massive data summarization on the fly." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014. The authors should cite this work.  One improvement to the psedocode:  if E_{R ~ U(X)}[...] <= ..., then sample R ~ U(X) and return R \cap X^+  As written, it was somewhat confusing at first with R as both the variable under the expectation and the random sample.  The authors should clearly write the value of k used in the experiments, as this defines the number of iterations for the competing algorithms.  *** Post-Rebuttal ***  Thank you for your response. While I agree that the experiments provided bring insights that a real parallel implementation would not, I still think a real parallel implementation would be useful. I think simply seeing how the running time decreases as the number of CPUs increases would be insightful. Also it seems to me that the RandomGreedy algorithm has a natural Map/Reduce style parallel algorithm that could be used for comparison.