Distributed Submodular Maximization: Identifying Representative Elements in Massive Data
Many large-scale machine learning problems (such as clustering, non-parametric learning, kernel machines, etc.) require selecting, out of a massive data set, a manageable yet representative subset. Such problems can often be reduced to maximizing a submodular set function subject to cardinality constraints. Classical approaches require centralized access to the full data set; but for truly large-scale problems, rendering the data centrally is often impractical. In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol GREEDI, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show, that under certain natural conditions, performance close to the (impractical) centralized approach can be achieved. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar-based clustering, on tens of millions of data points using Hadoop.
This paper provides a novel algorithm for large scale 
      submodular function maximization. The main contribution is a distributed 
      algorithm, using MapReduce, where the ground set is partitioned and each 
      machine operates on a subsets of the ground set. These solutions are 
      merged, to find an approximate subset. They provide approximation 
      guarantees for their approach and also show that it is tight. They also 
      investigate the performance of their algorithm under specific assumptions 
      on the datasets or the function. I think overall the authors try 
      to solve a very challenging problem, which could have a lot of utility in 
      large scale real world applications. I also feel that the experimental 
      validation is thorough and extensive. I also appreciate that this problem 
      is very challenging and it would really hard to obtain satisfactory 
      performance guarantees without additional assumptions. I was 
      somewhat disappointed with the theoretical analysis. It seems that the 
      guarantees are pretty weak; I acknowledge that the worst case analysis 
      shows that the algorithm is tight. However, this is expected particularly 
      for a very bad choice of partitions V1, V2, ... I was expecting some kind 
      of dependence on the choice of the the distributions, or even a heuristic 
      of what choices of distributions might work. The main guarantee (Theorem 
      5.1) seems almost a linear factor in m and k, which is somewhat 
      discouraging. As the proof technique reveals, and even otherwise, it is 
      easy to see that a simple modular upper bound based approximation gives a 
      factor k approximation. Given this, it is not immediately clear how GREEDI 
      performs theoretically w.r.t a simple modular upper bound particularly for 
      large m (which is of practical relevance), though I am sure the modular 
      upper bound based algorithm will perform very badly in practice. 
      There is one extremely important aspect, however, which is very 
      loosely described in the paper. I think this should be clarified much 
      better. A number of practical submodular functions are graph based 
      submodular functions (this includes, for example, the graph cut like 
      function and the exemplar based clustering objective from 3.1 -- A small 
      clarification here is this objective is essentially a form of 
      facility-location objective with a similarity instead of a distance 
      function) In these cases, evaluating the function requires a sum over all 
      the elements in V, even though the set under which the function needs to 
      be evaluated is considerably smaller. In these cases, it is not clear how 
      to evaluate the function. More specifically, a main motivation of this 
      approach (lines 122-127) is that the datasets are extremely large and 
      would possibly not fit within any single machine. However each of the 
      individual machines would still need to compute the outer sum over V in a 
      graph based objective (say the facility location objective). Under these 
      circumstances, it is not clear how to run the algorithm. Possibly, there 
      could be a time reduction due to the distribution, but it is not clear how 
      this will help in terms of memory. One solution could be to evaluate the 
      function just on the subsets Vi (i.e the outer sum may only be over the 
      Vi's), but this would then change the submodular function and the 
      guarantees would no longer hold. Overall, I think this is a major issue 
      which should be clarified in the rebuttal. Some minor suggestions 
      are that the proof of theorem 4.1 (specifically the tight instance) is 
      very hard to grasp. Maybe that can be better explained? Also, I think over 
      smaller datasets the actual greedy algorithm should be compared to GREEDI 
      (just to see how the performance is with respect to the best serial 
      algorithm). I would also love to see a timing analysis of the algorithms 
      and memory requirements etc. in the experimental results.