Distributed Submodular Cover: Succinctly Summarizing Massive Data
How can one find a subset, ideally as small as possible, that well represents a massive dataset? I.e., its corresponding utility, measured according to a suitable utility function, should be comparable to that of the whole dataset. In this paper, we formalize this challenge as a submodular cover problem. Here, the utility is assumed to exhibit submodularity, a natural diminishing returns condition prevalent in many data summarization applications. The classical greedy algorithm is known to provide solutions with logarithmic approximation guarantees compared to the optimum solution. However, this sequential, centralized approach is impractical for truly large-scale problems. In this work, we develop the first distributed algorithm -DISCOVER -for submodular set cover that is easily implementable using MapReduce-style computations. We theoretically analyze our approach, and present approximation guarantees for the solutions returned by DISCOVER. We also study a natural trade-off between the communication cost and the number of rounds required to obtain such a solution. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including active set selection, exemplar based clustering, and vertex cover on tens of millions of data points using Spark.
This paper proposes a distributed algorithm DISCOVER for solving submodular set cover problem. The idea of DISCOVER is to iteratively run the GreeDI as an oracle to incrementally obtain a solution until its valuation is greater than the solution quality requirement. The algorithm can tradeoff between the number of iterations and the communication cost needed for each iteration. This method is also validated on large-scale data applications. I think this paper studies an important problem and the proposed algorithm -- DISCOVER is novel under the distributed setting. The paper is well presented. The algorithm is complemented with theoretical justification and the empirical validation is also extensive. But still, I hope the authors could address the some of my questions below.  Some questions and comments:(1) The section about the tradeoff between communication cost and number of rounds is a bit confusing to me. It seems to me that by choosing smaller \alpha, it requires more rounds, but each round needs smaller amount of communication. I think the goal should be to find an \alpha such that the overall communication cost is minimized, instead of only looking at the cost per round. I think it would be interesting to have more discussion on how to choose \alpha in practice. (2) Instead of setting \alpha as a constant between 0 and 1, it may be more efficient to set alpha adaptively as the algorithm proceeds. One possibility could be to set \alpha close to 1 at the first few rounds, and then gradually decreases \alpha to 0 towards the end. (3) In Alg. 3, suppose we set \alpha = 1. I think the tradeoff between the communication cost and the number of rounds may also be achieved by replacing the doubling strategy (Line 8 of Alg. 3) with \ell = \ell * \beta, where \beta > 1 is a hyperparameter that controls the tradeoff. When \beta is only slightly larger than 1, the algorithm takes more rounds with the communication cost of each round being small. (4) In the experiment section, what \lambda is used for each experiment?Minor comment:The bound in Theorem 4.3 may be further improved: the following paper shows a guarantee of(1-1/e)/ (2\sqrt{k}) with k being the cardinality constraint for GreeDI and also shows that GreeDI is tight at 1/\sqrt(k).The Power of Randomization Distributed Submodular Maximization on Massive Datasets http://arxiv.org/pdf/1502.02606v2.pdf