Randomized Composable Core-sets for Distributed Submodular Maximization

Introduction

An effective way of processing massive data is to first extract a compact representation of the data and then perform further processing only on the representation itself. This approach significantly reduces the cost of processing, communicating and storing the data, as the representation size can be much smaller than the size of the original data set. Typically, the representation provides a smooth tradeoff between its size and the representation accuracy. Examples of this approach include techniques such as sampling, sketching, (composable) core-sets and mergeable summaries. Among these techniques, the concept of composable core-sets has been employed in several distributed optimization models such as nearest neighbor search , and the streaming and MapReduce models . Roughly speaking, the main idea behind this technique is as follows: First partition the data into smaller parts. Then compute a representative solution, referred to as a core-set, from each part. Finally, obtain a solution by solving the optimization problem over the union of core-sets for all parts. While this technique has been successfully applied to diversity maximization and clustering problems , for coverage and submodular maximization problems, impossibility bounds are known for this technique .

In this paper, we focus on efficient construction of a randomized variant of composable core-sets where the above idea is applied on a random clustering of the data. We employ this technique for the coverage, monotone and non-monotone submodular problems. Our results significantly improve upon the hardness results for non-randomized core-sets, and imply improved results for submodular maximization in a distributed and streaming settings. The effectiveness of this technique has been confirmed empirically for several machine learning applications , and our proof provides a theoretical foundation to this idea. Let us first define this concept, and then discuss its applications, and our results.

Here, we discuss the formal problem definition, and the distributed model motivating it.

Given an integer size constraint $k$, we let $f_{k}$ be

where the expectation is taken over the random choice of $\{T_{1},T_{2},\ldots,T_{m}\}$. For brevity, instead of saying that $\mathsf{ALG}$ implements a composable core-set, we say that $\mathsf{ALG}$ is an $\alpha$-approximate randomized composable core-set.

For ease of notation, when it is clear from the context, we may drop the term composable, and refer to composable core-sets as core-sets. Throughout this paper, we discuss randomized composable core-sets for the submodular maximization problem with a cardinality constraint $k$.

Distributed Approximation Algorithm. Note that we can use a randomized $\alpha$-approximate composable core-set algorithm $\mathsf{ALG}$ to design the following simple distributed $(1-{1\over e})\alpha$-approximation algorithm for monotone submodular maximization:

Each machine $i$ computes a randomized composable core-set $S_{i}\subseteq T_{i}$ of size $k^{\prime}$, i.e., $S_{i}=\mathsf{ALG}(T_{i})$ for each $1\leq i\leq m$.

In the second phase, first collect the union of all core-sets, $U=\cup_{1\leq i\leq m}S_{i}$, on one machine. Then apply a post-processing $(1-{1\over e})$-approximation algorithm (e.g., algorithm $\mathsf{Greedy}$) to compute a solution $S$ to the submodular maximization problem over the set $U$. Output $S$.

It follows from the definition of the $\alpha$-approximate randomized composable core-set that the above algorithm is a distributed $(1-{1\over e})\alpha$-approximation algorithm for submodular maximization problem. We refer to this two-phase algorithmic approach as the distributed algorithm, and the overall approximation factor of the distributed algorithm as the distributed approximation factor. For all our algorithms in this paper, in addition to presenting an algorithm that achieves an approximation factor $\alpha$ as a randomized composable core-set, we propose a post-processing algorithm for the second phase, and present an improved analysis that achieves much better than $(1-{1\over e})\alpha$-approximation as the distributed approximation factor.

Note that the above algorithm can be implemented in a distributed manner only if $k^{\prime}$ is small enough such that $mk^{\prime}$ items can be processed on one machine. In all our results the size of the composable core-set, $k^{\prime}$, is a function of the cardinality constraint, $k$: In particular, in Section 2, we apply a composable core-set of size $k^{\prime}=k$. In Section 4, we apply a composable core-set of size $k^{\prime}<4k$, and as a result, achieve a better approximation factor. We call a core-set, a small-size core-set, if its size $k^{\prime}$ is less than $k$ (See Section 5). As we will see, the hardness results for small-size core-sets are much stronger than that of core-sets of size $k$ or larger.

Non-randomized Composable Core-sets. The above definition for randomized composable core-sets is introduced in this paper. Prior work define a non-randomized variant of composable core-sets where the above property holds for any (arbitrary) partitioning $\{T_{1},T_{2},\ldots,T_{m}\}$ of data into $m$ parts It is not hard to see that for non-randomized composable core-set, the multiplicity parameter $C$ is not relevant., i.e., an algorithm $\mathsf{ALG}$ as described above is a $\alpha$-approximate (non-randomized) composable core-set of size $k^{\prime}$ for $f$, if for any cardinality constraint $k$, and any arbitrary partitioning $\{T_{1},T_{2},\ldots,T_{m}\}$ of the items into $m$ sets, we have $f_{k}(\mathsf{ALG}(T_{1})\cup\ldots\cup\mathsf{ALG}(T_{m}))\geq{\alpha}\cdot f_{k}(T_{1}\cup\ldots\cup T_{m})$.

2 Applications and Motivations

An $\alpha$-approximate randomized composable core-set of size $k^{\prime}=O(k)$ for a problem can be applied in three types of applications These results assume $k\leq n^{1-\epsilon}$ for a constant $\epsilon$.: (i) in distributed computation , where it implies an $\alpha$-approximation in one or two rounds of MapReduces using the total communication complexity of $O(n)$, (ii) in the random-order streaming model, where it implies an $\alpha$-approximation algorithm in one pass using sublinear memory, (iii) in a class of approximate nearest neighbor search problems, where it implies an $\alpha$-approximation algorithm based on the locally sensitive hashing (under an assumption). Here, we discuss the application for the MapReduce and Streaming framework, and for details of the approximate nearest neighbor application, we refer to .

We first show how to use a randomized composable core-set of size $O(k)$ to design a distributed algorithm in one or two rounds of MapReduces The straightforward way of applying the ideas will result in two rounds of MapReduce. However, if we assume that the data is originally sharded randomly and each part is in a single shard, and the memory for each machine is more than the size of each shard, then it can be implemented via one round of MapReduce computation. using linear total communication complexity: Let $m=\sqrt{n/k}$, and let $(T_{1},\ldots,T_{m})$ be a random partitioning where $T_{i}$ has $\sqrt{kn}$ items. In the distributed algorithm, we assume that the random partitioning is produced in one round of MapReduce where each of $m$ reducers receives $T_{i}$ as input, and produces a core-set $S_{i}$ for the next round. Alternatively, we may assume that the data (or the items) are distributed uniformly at random among machines, or similarity each of $m$ mappers receives $T_{i}$ as input, and produces a core-set $S_{i}$ for the reducer. In either case, the produced core-sets are passed to a single reducer in the first or the second round. The total input to the reducer, i.e., the union of the core-sets, is of size at most $mk^{\prime}=O(k)\sqrt{n/k}=O(\sqrt{kn})$. The solution computed by the reducer for the union of the core-sets is, by definition, a good approximation to the original problem. It is easy to see that the total communication complexity of this algorithm is $O(n)$, and this computation can be performed in one or two rounds as formally defined in the MapReduce computation model .

Next, we elaborate on the application for a streaming computation model: In the random-order data stream model, a random sequence of $n$ data points needs to be processed “on-the-fly” while using only limited storage. An algorithm for a randomized composable core-set can be easily used to obtain an algorithm for this setting The paper introduced this approach for the special case of $k$-median clustering. More general formulation of this method with other applications appeared in .. In particular, if a randomized composable core-set for a given problem has size $k$, we start by dividing the random stream of data into $\sqrt{n/k}$ blocks of size $s=\sqrt{nk}$. This way, each block will be a random subset of items. The algorithm then proceeds block by block. Each block is read and stored in the main memory, its core-set is computed and stored, and the block is deleted. At the end, the algorithm solves the problem for the union of the core-sets. The whole algorithm takes only $O(\sqrt{kn})$ space. The storage can be reduced further by utilizing more than one level of compression, at the cost of increasing the approximation factor.

Variants of the composable core-set technique have been applied for optimization under MapReduce framework . However, none of these previous results formally study the difference between randomized and non-randomized variants and in most cases, they employ non-randomized composable core-sets. Indyk et al. observed that the idea of non-randomized composable core-sets cannot be applied to the coverage maximization (or more generally submodular maximization) problems. In fact, all our hardness results also apply to a class of submodular maximization problems known as the maximum $k$-coverage problems, i.e., given a number $k$, and a family of subsets ${\cal A}\subset 2^{X}$, find a subfamily of $k$ subsets $A_{1},\ldots,A_{k}$ whose union $\cup_{j=1}^{k}A_{j}$ is maximized. Solving max $k$-coverage and submodular maximization in a distributed manner have attracted a significant amount of research over the last few years . Other than the importance of these problems, one reason for the popularity of this problem in this context is the fact that its approximation algorithm is algorithm $\mathsf{Greedy}$ which is naturally sequential and it is hard to parallelize or implement in a distributed manner.

3 Our Contributions

Our results are summarized in Table 1. As our first result, we prove that a family of efficient algorithms including a variant of algorithm $\mathsf{Greedy}$ with a consistent tie-breaking rule leads to an almost $1/3$-approximate randomized composable core-set of size $k$ for any monotone submodular function and cardinality constraint $k$ with multiplicity of $1$ (see Section 2). This is in contrast to a known $O({\log k\over\sqrt{k}})$ hardness result for any (non-randomized) composable core-set , and shows the advantage of using the randomization here. Furthermore, by constructing this randomized core-set and applying algorithm $\mathsf{Greedy}$ afterwards, we show a $0.27$ distributed approximation factor for the monotone submodular maximization problem in one or two rounds of MapReduces with a linear communication complexity. Previous results lead to algorithms with either much larger number of rounds of MapReduce , and/or larger communication complexity . This improvement is important, since the number of rounds of MapReduce computation and communication complexity are the most important factors in determining the performance of a MapReduced-based algorithm . The effectiveness of using this technique has been confirmed empirically by Mirzasoleiman et al who studied a similar algorithm on a subclass of submodular maximization problems. However, they only provide provable guarantees for a subclass of submodular functions satisfying a certain Lipchitz condition . Our result not only works for monotone submodular functions, but also extends to non-monotone (non-negative) submodular functions, and leads to the first constant-round MapReduce-based constant-factor approximation algorithm for non-monotone submodular maximization (with $O(n)$ total communication complexity and approximation factor of $0.18$). It also leads to the first constant-factor approximation algorithm for non-monotone submodular maximization in a random-order streaming model in one pass with sublinear memory.

Our next goal is to improve the approximation factor of the above algorithm for monotone submodular functions. To this end, we first observe that one cannot achieve a better than the $1/2$ factor via core-sets of size $k$ using algorithm $\mathsf{Greedy}$ or any algorithm in a family of local search algorithms. In Section 4, we show how to go beyond the $1/2$-approximation by applying core-sets of size higher than $k$ but still of size $O(k)$, and prove that algorithm $\mathsf{Greedy}$ with a consistent tie-breaking rule provides a $0.585$-approximate randomized composable core-set of size $k^{\prime}<4k$ for our problem. We then present algorithm $\mathsf{PseudoGreedy}$ that can be applied as a post-processing step to design a distributed $0.545$-approximation algorithm in one or two rounds of MapReduces, and with linear total communication complexity. For monotone submodular maximization, this result implies the first distributed approximation algorithm with approximation factor better than $1/2$ that runs in a constant number of rounds. We achieve this approximation factor using one or two rounds of MapReduces and with the total communication complexity of $O(n)$. In addition, this result implies the first approximation algorithm beating the $1/2$ factor for the random-order streaming model with constant number of passes on the data and sublinear memory. To complement this result, we first show that our analysis for algorithm $\mathsf{Greedy}$ is tight. Moreover, we show that it is information theoretically impossible to achieve an approximation factor better than $1-{1/e}$ using a core-set with size polynomial in $k$.

Finally, we consider the construction of small-size core-sets, i.e., a core-set of size $k^{\prime}<k$. Studying such core-sets is important particularly for cases with large parameter $k$, e.g., $k=\Omega(n)$ or $k={n\over\log n}$ For such large $k$, a core-set of size $k$ may not be as useful since outputting the whole core-set may be impossible. For example, in the formal MapReduce model , outputting a core-set of size $k$ for $k=\Omega(n)$ is not feasible.. For our problem, we first observe a hardness bound of $O({k^{\prime}\over k})$ for non-randomized core-sets. On the other hand, in Subsection 5.2, we show an $\Omega(\sqrt{k^{\prime}\over k})$-approximate randomized composable core-set for this problem, and accompany this result by a matching hardness bound of $O(\sqrt{k^{\prime}\over k})$ for randomized composable core-set. The hardness result is presented in Subsection 5.1.

4 Other Related Work.

Submodular Maximization in Streaming and MapReduce: Solving max $k$-coverage and submodular maximization in a distributed manner have attracted a significant amount of research over the last few years . From theoretical point of view, for the coverage maximization problem, Chierchetti et al. present a $(1-1/e)$-approximation algorithm in polylogarithmic number of MapReduce rounds, and Belloch et al improved this result and achieved $\log^{2}n$ number of rounds. Recently, Kumar et al. present a $(1-1/e)$-approximation algorithm using a logarithmic number of rounds of MapReduces. They also derive $(1/2-{\epsilon})$-approximation algorithm that runs in $O({1\over\delta})$ number of rounds of MapReduce (for a constant $\delta$), but this algorithm needs a $\log n$ blowup in the communication complexity. As observed in various empirical studies , the communication complexity and the number of MapReduce rounds are important factors in determining the performance of a MapReduce-based algorithm and a $\log n$ blowup in the communication complexity can play a crucial role in applicability of the algorithm in practice. Our algorithm on the other hand runs only in (one or) two rounds, and can run on any number of machines as long as they can store the data, i.e, it needs $m$ machines each with memory proportional to ${1\over m}$ of the size of the input. One previous attempt to apply the idea of core-sets for submodular maximization is by Indyk et al. who rule out the applicability of non-randomized core-sets by showing a hardness bound of $O({\log k\over\sqrt{k}})$ for non-randomized core-sets. The most relevant previous attempt in applying randomized core-sets to submodular maximization is by Mirzasoleiman et al , where the authors study a class of algorithms similar to the ones discussed here, and show the effectiveness of applying algorithm $\mathsf{Greedy}$ over a random partitioning empirically for several machine learning applications. The authors also prove theoretical guarantees for algorithm $\mathsf{Greedy}$ for special classes of submodular functions satisfying a certain Lipschitz condition . Here, on the other hand, we present guaranteed approximation results for all monotone and non-monotone submodular functions. In fact, Ashwinkumar and Karbasi observed that if one applies the greedy algorithm without a consistent tie-breaking rule, the approximation factor of the algorithm is not bounded for coverage functions. In this paper, we prove that a class of algorithms including greedy with a consistent tie-breaking rule provide a guaranteed $0.27$-approximation algorithm for all monotone submodular functions. We also show how to achieve an improved $0.54$-approximation using slightly larger core-sets of size $O(k)$. Finally, there is a recent paper in the streaming model in which the authors present a streaming $1/2$-approximation algorithm with one pass and linear memory. Our results lead to improved results for random-order streaming model for monotone and non-monotone submodular maximization.

Core-sets: The notion of core-sets has been introduced in . In this paper, we use the term core-sets to refer to “composable core-sets” which was formally defined in a recent paper . This notion has been also implicitly used in Section 5 of Agarwal et al. where the authors specify composability properties of $\epsilon$-kernels (a variant of core-sets). The notion of (composable) core-sets are also related to the concept of mergeable summaries that have been studied in the literature . As discussed before, the idea of using core-sets has been applied either explicitly or implicitly in the streaming model and in the MapReduce framework . Moreover, notions similar to randomized core-sets have been studied for random-order streaming models . Finally, the idea of random projection in performing algebraic projections can be viewed as a related topic but it does not discuss the concept of composability over a random partitioning.

5 More Notation

Consider a submodular set function $f$. Let $\mathsf{ALG}$ be an algorithm that given any subset $T$ returns subset ${\mathsf{ALG}}(T)\subseteq T$ with size at most $k^{\prime}$. We say that this Algorithm $\mathsf{ALG}$ is a $\beta$-nice algorithm for function $f$ and some parameter $\beta$ iff for any set $T$ and any item $x\in T\setminus{\mathsf{ALG}}(T)$ (item $x$ is in set $T$ but is not selected in the output of algorithm $\mathsf{ALG}$), then the following two properties hold:

Set ${\mathsf{ALG}}(T\setminus\{x\})$ is equal to ${\mathsf{ALG}}(T)$, i.e., intuitively the output of the algorithm should not depend on the items it does not select, and

$\Delta(x,{\mathsf{ALG}}(T))$ is at most $\beta\frac{f({\mathsf{ALG}}(T))}{k^{\prime}}$. In other words, the marginal $f$ value of any not-selected item cannot be more than $\beta$ times the average contribution of selected items.

Randomized Core-sets for Submodular Maximization

In this section, we show that a family of $\beta$-nice algorithms, introduced in Section 1.5, leads to a constant-factor approximate randomized composable core-set, and a constant-factor distributed approximation algorithm for monotone and non-monotone submodular maximization problems with cardinality constraints. Later, in Subsection 2.2, we show that several efficient algorithms in the literature of submodular maximization are $\beta$-nice for some $\beta\in[1,1+\epsilon]$ (for $\epsilon=o(1)$) including some variant of algorithm $\mathsf{Greedy}$ with a consistent tie-breaking rule, and also an almost linear-time algorithm in . Before stating the theorem, we emphasize that in this section, we apply a composable core-set of multiplicity 1 which corresponds to a random partitioning of items into $m$ disjoint pieces.

For any $\beta>0$, any $\beta$-nice algorithm $\mathsf{ALG}$ is a $\frac{1}{2+\beta}$-approximate randomized composable core-set of multiplicity 1 and size $k$ for the monotone, and $\frac{1-\frac{1}{m}}{2+\beta}$-approximate for non-monotone submodular maximization problems with cardinality constraint $k$.

We want to show that there exists a subset of $\cup_{i=1}^{m}S_{i}$ with size at most $k$, and at least an expected $f$ value of $\frac{f(\textsc{OPT}{})}{2+\beta}$ for monotone $f$, and $\frac{(1-1/m)f(\textsc{OPT}{})}{2+\beta}$ for non-monotone $f$. Toward this goal, we take the maximum of $\max_{1\leq i\leq m}f(S_{i})$ and $f(\textsc{OPT}{}^{S})$ as a candidate solution. We define some notation to simplify the rest of the proof. Consider an arbitrary permutation $\pi$ on items of OPT, and for each item $x\in\textsc{OPT}{}$ let $\textsc{OPT}{}^{x}$ be the set of items in $\pi$ that appear before $x$. We will first lower bound $f(\textsc{OPT}{}^{S})$ using the submodularity property in Lemma 2.2.

For any set of selected items, $f(\textsc{OPT}{}^{S})\geq f(\textsc{OPT}{})-\sum_{x\in\textsc{OPT}{}\setminus(\cup_{i=1}^{m}S_{i})}\Delta(x,\textsc{OPT}{}^{x})$ for a monotone or non-monotone submodular function $f$.

First we note that $f(\textsc{OPT}{})-f(\textsc{OPT}{}^{S})=\sum_{x\in\textsc{OPT}{}\setminus\textsc{OPT}{}^{S}}\Delta(x,\textsc{OPT}{}^{x}\cup\textsc{OPT}{}^{S})$. Using submodularity property, we know that $\Delta(x,\textsc{OPT}{}^{x}\cup\textsc{OPT}{}^{S})$ is at most $\Delta(x,\textsc{OPT}{}^{x})$ because $\textsc{OPT}{}^{x}$ is a subset of $\textsc{OPT}{}^{x}\cup\textsc{OPT}{}^{S}$. Therefore $f(\textsc{OPT}{})-f(\textsc{OPT}{}\cap A)\leq\sum_{x\in\textsc{OPT}{}\setminus\textsc{OPT}{}^{S}}\Delta(x,\textsc{OPT}{}^{x})$ which is equal to $\sum_{x\in\textsc{OPT}{}\setminus(\cup_{i=1}^{m}S_{i})}\Delta(x,\textsc{OPT}{}^{x})$ by definition of $\textsc{OPT}{}^{S}$. This concludes the proof. ∎

Lemma 2.2 suggests that we should upper bound $\sum_{x\in\textsc{OPT}{}\setminus(\cup_{i=1}^{m}S_{i})}\Delta(x,\textsc{OPT}{}^{x})$ which is done in the next lemma.

The sum $\sum_{i=1}^{m}\sum_{x\in\textsc{OPT}{}\cap T_{i}\setminus S_{i}}\Delta(x,\textsc{OPT}{}^{x})$ is at most $\beta\left(\max_{1\leq i\leq m}f(S_{i})\right)+$ $\sum_{i=1}^{m}\sum_{x\in\textsc{OPT}{}\cap T_{i}\setminus S_{i}}$ $\left(\Delta(x,\textsc{OPT}{}^{x})-\Delta(x,\textsc{OPT}{}^{x}\cup S_{i})\right)$ for a monotone or non-monotone submodular function $f$.

The sum $\sum_{i=1}^{m}\sum_{x\in\textsc{OPT}{}\cap T_{i}\setminus S_{i}}\Delta(x,\textsc{OPT}{}^{x})$ can be written as:

The first term in the sum is upper bounded by $\beta\frac{f(S_{i})}{k}$ using the second property of $\beta$-nice algorithms. To conclude the proof, we apply inequality $f(S_{i})\leq\max_{1\leq i^{\prime}\leq m}f(S_{i^{\prime}})$, and use the fact that there are at most $k$ items in $\textsc{OPT}{}\setminus\textsc{OPT}{}^{S}=\cup_{i=1}^{m}(\textsc{OPT}{}\cap T_{i}\setminus S_{i})$. ∎

At this stage of the analysis, we use randomness of partition $\{T_{i}\}_{i=1}^{m}$ to upper bound the expected value of these differences in $\Delta$ values with the expected value of average of $f(S_{i})$. This is stated in the following lemma:

Before proving the lemmas, we observe that putting these three lemmas together, we can finish the proof of the theorem. In particular, for a monotone or non-monotone submodular function $f$, we have that:

Proof of Lemma 2.4. The main part of the proof is to show that the sum of the $\Delta$ differences in the statement of the lemma is in expectation at most $\frac{1}{m}$ fraction of sum of $\Delta$ differences for a larger set of pairs $(i,x)$. In particular, we show that

In Theorem 2.1, we prove that if on each part (set $T_{i}$) of the partitioning, we run a $\beta$-nice algorithm $\mathsf{ALG}$, the union of output sets of $\mathsf{ALG}$ will contain a set of size at most $k$ that preserves at least $\frac{1}{2+\beta}$ fraction of value of optimum set. If we run algorithm $\mathsf{Greedy}$ on the union of output sets $\cup_{i=1}^{m}S_{i}$, using the classic analysis of algorithm $\mathsf{Greedy}$, we can easily claim that the overall value of the output set at the end is at least $\frac{1-1/e}{2+\beta}$ fraction of $f(\textsc{OPT}{})$. In Theorem 2.5, we show an improved distributed approximation factor.

Let $S$ be the output of algorithm $\mathsf{Greedy}$ over $\cup_{i=1}^{m}S_{i}$, i.e. $S=\mathsf{Greedy}(\cup_{i=1}^{m}S_{i})$ for a monotone submodular function $f$. Also let $S$ be the output of non-monotone submodular maximization algorithm of Buchbinder et al. on $\cup_{i=1}^{m}S_{i}$ when $f$ is a non-monotone submodular function. The expected value of $\max\{f(S),\max_{i=1}^{m}\{f(S_{i})\}\}$ is at least $\frac{(1-1/e)f(\textsc{OPT}{})}{1+(1-1/e)(1+\beta)}$ for monotone and $\frac{(1-\frac{1}{m})f(\textsc{OPT}{})/e}{1+(1+\beta)/e}$ for non-monotone submodular $f$. In particular, for $\beta=1$, the distributed approximation factors are $\geq 0.27$, and $\geq 0.21-\frac{1}{4m}$ for monotone and non-monotone $f$ respectively.

By applying lemmas 2.2, 2.3, and 2.4, we have that: $f(\textsc{OPT}{}^{S})\geq f(\textsc{OPT}{})-\beta\max_{i=1}^{m}f(S_{i})-\frac{\sum_{i=1}^{m}f(S_{i})}{m}\geq f(\textsc{OPT}{})-(1+\beta)\max_{i=1}^{m}f(S_{i})$ for a monotone submodular function $f$. Using the classic analysis of $\mathsf{Greedy}$ on submodular maximization in , one can prove that $f(S)\geq(1-1/e)f(\textsc{OPT}{}^{S})$ when $f$ is monotone. By taking the expectation of the two sides of this inequality, and using Lemma 2.4, we have that:

If $f$ is non-monotone, we get a weaker inequality $f(S)\geq\frac{f(\textsc{OPT}{}^{S})}{e}$ by applying the algorithm of Buchbinder et al. . Using lemmas 2.2, 2.3, and 2.4, we have that: $f(\textsc{OPT}{}^{S})\geq f(\textsc{OPT}{})-\beta\max_{i=1}^{m}f(S_{i})-\frac{\sum_{i=1}^{m}f(S_{i})}{m}-\frac{f(\textsc{OPT}{})}{m}\geq(1-\frac{1}{m})f(\textsc{OPT}{})-(1+\beta)\max_{i=1}^{m}f(S_{i})$. Similarly, we can claim that $\rho\geq\frac{(1-\frac{1}{m})/e}{1+(1+\beta)/e}$. This implies the desired lower bound of $\frac{(1-\frac{1}{m})/e}{1+(1+\beta)/e}$ on $\rho$. ∎

2 Examples of β𝛽\beta-Nice Algorithms

In this section, we show that several existing algorithms for submodular maximization in the literature belong to the family of $\beta$-nice algorithms.

Algorithm $\mathsf{Greedy}$ with Consistent Tie-breaking: First, we observe that algorithm $\mathsf{Greedy}$ is $1$-nice if it has a consistent tie breaking rule: while selecting among the items with the same marginal value, $\mathsf{Greedy}$ can have a fixed strict total ordering ($\Pi$) of the items, and among the set of items with the maximum marginal value chooses the one highest rank in $\Pi$. The consistency of the tie breaking rule implies the first property of nice algorithms. To see the second property, first observe that (i) $\mathsf{Greedy}$ always adds an item with the maximum marginal $f$ value, and (ii) using submodularity of $f$, the marginal $f$ values are decreasing as more items are added to the selected items. Therefore, after $k$ iterations, the marginal value of adding any other item, is less than each of the $k$ marginal $f$ values we achieved while adding the first $k$ items. This implies the 2nd property, and concludes that $\mathsf{Greedy}$ with a consistent tie-breaking rule is a $1$-nice algorithm.

An almost linear-time $(1+\epsilon)$-nice Algorithm: Badanidiyuru and Vondrak present an almost linear-time $(1-\frac{1}{e}-\epsilon)$-approximation algorithm for monotone submodular maximization with a cardinality constraint. We observe that this algorithm is $(1+2\epsilon)$-nice. The algorithm is a relaxed version of $\mathsf{Greedy}$ where in each iteration, it adds an item with almost maximum marginal value (with at least $1-\epsilon$ fraction of the maximum marginal). As a result, similar to the proof for $\mathsf{Greedy}$, one can show that this linear-time algorithm $\frac{1}{1-\epsilon}$-nice and consequently $(1+2\epsilon)$-nice for $\epsilon\leq 0.5$.

Hardness Results for Randomized Core-sets

In Section 2, we showed that a family of $\beta$-nice algorithms are $\frac{1}{2+\beta}$-approximate randomized core sets (e.g., $\frac{1}{3}$-approximate for algorithm $\mathsf{Greedy}$). Here we show what kinds of randomized core-sets are not achievable. In particular, we prove, in Theorem 3.1 that if we restrict our attention to core-sets of size $k$, algorithm $\mathsf{Greedy}$ or any local search algorithm does not achieve an approximation factor better than $\frac{1}{2}$ even if each item is sent to multiple machines (up to multiplicity $C=o(\sqrt{m})$). This leads to the following question: does increasing the output size of core-sets, $k^{\prime}$, help with the approximation factor? In other words, can we get a better than $1/2$ approximation factor if we allow the algorithm to select more than $k$ items on each machine? To answer this question, we first prove, in Theorem 3.3 that it is not possible to achieve a randomized composable core-set of size $k^{\prime}=o(\frac{n}{Cm})$ with approximation better than $1-\frac{1}{e}$ even when we allow for multiplicity $C=o(\sqrt{\frac{m}{k}})$. We then show in Section 4 that although it is not possible to beat the $1-\frac{1}{e}$ barrier, we can slightly increase the output sizes, apply algorithm $\mathsf{Greedy}$ to achieve an approximation factor $\approx 2-\sqrt{2}>\frac{1}{2}$ with a constant multiplicity.

Following we show a limitation on core-sets of size $k$. In particular, we introduce a family of instances for which algorithm $\mathsf{Greedy}$ and any algorithm that returns a locally optimum solution of size at most $k$ do not achieve a better than $\frac{1}{2}+\epsilon$-approximate core-set for any $\epsilon>0$. This lower-bound result applies to a coverage valuation (and therefore submodular) function $f$ and it holds even if we send each item to multiple machines.

For any $\epsilon>0$, assuming each item is sent to at least one random machine (to set $T_{i}$ for a random $1\leq i\leq n$), and at most $C\leq\sqrt{\frac{\epsilon m}{2}}$ random machines, and the number of items an algorithm is allowed to return is at most $k$, there exists a family of instances for which algorithm $\mathsf{Greedy}$ and any other local search algorithm returns an at most $(\frac{1}{2}+\frac{1}{k}+\epsilon)$-approximate composable core-set.

We say a machine is a good machine if for each $1\leq i\leq k$, it receives at least a set $B_{i,j}$ for some $1\leq j\leq L$, and we call it is a bad machine otherwise. At first, we show that the output of algorithm $\mathsf{Greedy}$ or any local search algorithm on a good machine that has not received set $A_{1}$ is exactly one set $B_{i,j}$ for each $1\leq i\leq k$, and nothing else. In other words, these algorithms do not return any of the sets $A_{2},A_{3},\cdots,A_{k}$ unless they have a set $A_{1}$ as part of their input, or they are running on a bad machine. It is not hard to see that if $A_{1}$ is not part of the input each set $B_{i,j}$ has marginal value $k$ if no other set $B_{i,j^{\prime}}$ for $j^{\prime}\neq j$ has been selected before. On the other hand, the marginal value of each of the sets $\{A_{i}\}_{i=2}^{k}$ is $k-1$. So $\mathsf{Greedy}$ or any local search algorithm does not select any of the sets $\{A_{i}\}_{i=2}^{k}$ unless some set $B_{i,j}$ has been selected for each $1\leq i\leq k$. The fact that the output sizes are limited to $k$ implies that sets $\{A_{i}\}_{i=2}^{k}$ are not selected.

Now it suffices to prove that most machines are good, and most sets in $\{A_{i}\}_{i=2}^{k}$ are not sent to a machine that has set $A_{1}$ as well. To prove this, we show that each machine is good with probability at least $1-\frac{\epsilon}{2C}$. To see this, note that for each $i$, there are $L$ identical sets $B_{i,j}$, and the probability that a machine does not receive any of these $L$ copies is at most $(1-\frac{1}{m})^{L}\leq e^{-L/m}\leq\frac{\epsilon}{2Ck}$. So the probability that a machine is good is at least $(1-\frac{\epsilon}{2Ck})^{k}\geq 1-\frac{\epsilon}{2C}$. Since each set is sent to at most $C$ machines, for each $1\leq i\leq k$, we know that set $A_{i}$ is sent to only good machines with probability at least $(1-\frac{\epsilon}{2C})^{C}\geq 1-\frac{\epsilon}{2}$. We also know that the probability that for each $2\leq i\leq k$, the probability of set $A_{i}$ sharing a machine with set $A_{1}$ is at most $\frac{C^{2}}{m}\leq\frac{\epsilon}{2}$ since each set is sent to at most $C$ random machines. As a result, at most $\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon$ fraction of sets $\{A_{i}\}_{i=2}^{k}$ are selected by at least one machine in expectation, and therefore in expectation the size of the union of all selected sets (not only the best $k$ of them) is at most $k^{2}+\epsilon(k-1)^{2}$ which is less than $\frac{1}{2}+\frac{1}{k}+\epsilon$ fraction of the value of the optimum $k$ sets ($\{A_{i}\}_{i=1}^{k}$). ∎

Following, we prove that it is not possible to achieve a better than $1-\frac{1}{e}+\epsilon$ approximation factor for submodular maximization subject to a cardinality constraint even if each item is sent to at most $C$ machines where $C\leq\sqrt{\epsilon m}$, and each machine is allowed to return $k^{\prime}=\frac{\epsilon(1-\epsilon)n}{8Cm}$ items. We note that in this hardness result, the size of the output sets can be arbitrarily large in terms of $k$, i.e. for instance $k^{\prime}$ could be $\Omega(2^{k})$ for some values of $n,m,C$, and $k$. This is an information theoretic hardness result that does not use any complexity theoretic assumption. In fact, the instance itself can be optimally solved on a single machine, but distributing the items among several machines makes it hard to preserve the optimum solution. Before presenting the hardness result, we state the following version of Chernoff bound (which we use in the proof) as given on page 267, Corollary $A.1.10$ and Theorem $A.1.13$ in :

Suppose $X_{1},X_{2},\cdots,X_{n}$ are $0-1$ random variables such that $Pr[X_{i}=1]=p_{i}$, and let $\mu=\sum_{i=1}^{n}p_{i}$, and $X=\sum_{i=1}^{n}X_{i}$. Then for any $a>0$

For any $\epsilon>0$, $k\geq\frac{8}{\epsilon}$ and $C\leq\sqrt{\frac{\epsilon m}{4k}}$, assuming each item is sent to at most $C$ machines randomly, and each machine can output at most $k^{\prime}=\frac{\epsilon(1-\epsilon)}{8C}\times\frac{n}{m}$ items, there exists a family of instances for which no algorithm can guarantee a core-set of expected value more than $(1-\frac{1}{e}+\epsilon)$ fraction of the optimum solution.

So among the optimum solution items that are alone in their machines, at most $\frac{\epsilon}{4C}$ fraction of them will be selected. We note that each item is sent to at most $C$ machines, therefore in total $\frac{\epsilon k}{4}$ optimum items will be selected in this category in expectation.

On the other hand, the total number of optimum items that share a machine with some other optimum item is at most $\frac{(Ck)^{2}}{m}\leq\frac{\epsilon k}{4}$ (an upper bound on the expected number of collisions). We conclude that in total at most $\frac{\epsilon k}{2}$ optimum items will be selected in expectation. Therefore the total value of the selected optimum items does not exceed $\frac{\epsilon}{2}$ fraction of the optimum solution.

Better Randomized Core-sets for Monotone Submodular Maximization

In this section, we prove that although it is not possible to beat the $1-\frac{1}{e}$ barrier, we can slightly increase the output sizes (to $k^{\prime}=(\sqrt{2}+1)k$), and apply algorithm $\mathsf{Greedy}$ to achieve an approximation factor $\approx 2-\sqrt{2}>\frac{1}{2}$ with a constant multiplicity. Furthermore, we show in Theorem 4.8 that our analysis is tight for algorithm $\mathsf{Greedy}$ even if we increase the core-set sizes significantly. Finally, we present in Subsection 4.1 a post-processing algorithm $\mathsf{PseudoGreedy}$ that achieves an overall distributed approximation factor better than $1/2$. In particular, after the first phase, we show how to find a size $k$ subset of the union of selected items with expected value at least $(0.545-o(1))f(\textsc{OPT}{})$. Since in this section, we are dealing with a monotone submodular function $f$, we can assume WLOG that $f(\emptyset)=0$.

For any integer $C\geq 1$, any cardinality constraint $k=o(m)$, algorithm $\mathsf{Greedy}$ is a $\left(2-\sqrt{2}-O\left(\frac{1}{k}+\frac{\ln(C)}{C}\right)\right)$-approximate randomized composable core-set of multiplicity $C$ and size $k^{\prime}=(2\sqrt{2}+1)k$ for any monotone submodular function $f$. By letting $C={1\over\epsilon}$, this leads to a randomized composable core-set of approximation factor $0.5857$.

Let $D\stackrel{{\scriptstyle\text{def}}}{{=}}2\sqrt{2}+1$, and $k^{\prime}=Dk$. Following our notation from Section 1.5, let $S_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathsf{Greedy}(T_{i})$ for $1\leq i\leq m$, where $T_{i}$ is the set of items sent to the machine $i$. Note that we can let $|S_{i}|=Dk$, since if there are less than $Dk$ items in $T_{i}$, WLOG we can assume the algorithm returns some extra dummy items just for the sake of analysis.

Consider an item $x\in\textsc{OPT}{}$. We say that $x$ survives from machine $i$, if, when we send $x$ to machine $i$ in addition to items of $T_{i}$, algorithm $\mathsf{Greedy}$ would choose this item $x$ in its output of size $k^{\prime}$, i.e., if $x\in\mathsf{Greedy}(T_{i}\cup\{x\})\}$. For the sake of analysis, we partition the optimum solution into two sets as follows: let $\textsc{OPT}{}_{1}$ be the set of items in the optimum solution that would survive the first machine, i.e., $\textsc{OPT}{}_{1}\stackrel{{\scriptstyle\text{def}}}{{=}}\{x|x\in\textsc{OPT}{}\cap\mathsf{Greedy}(T_{1}\cup\{x\})\}$. Let $\textsc{OPT}{}_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}\textsc{OPT}{}\setminus\textsc{OPT}{}_{1}$, and $k_{1}\stackrel{{\scriptstyle\text{def}}}{{=}}|\textsc{OPT}{}_{1}|$, and $k_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}|\textsc{OPT}{}_{2}|$ (note that $k_{1}+k_{2}=k$). We also define $\textsc{OPT}{}_{1}^{\prime}\stackrel{{\scriptstyle\text{def}}}{{=}}\textsc{OPT}{}_{1}\cap\textsc{OPT}{}^{S}$, and $\textsc{OPT}{}^{\prime}\stackrel{{\scriptstyle\text{def}}}{{=}}\textsc{OPT}{}_{1}^{\prime}\cup\textsc{OPT}{}_{2}$ where $\textsc{OPT}{}^{S}$ is defined in Subsection 1.5.

The optimum value $f(\textsc{OPT}{})$ is equal to $\sum_{x\in\textsc{OPT}{}}\Delta(x,\pi^{x})$, and the term $f(\textsc{OPT}{})-f(\textsc{OPT}{}^{\prime})$ is at most $\sum_{x\in\textsc{OPT}{}_{1}\setminus\textsc{OPT}{}^{S}}\Delta(x,\pi^{x})$.

By definition of $\Delta$ values, we have that: $\sum_{x\in\textsc{OPT}{}}\Delta(x,\pi^{x})=f(\textsc{OPT}{})-f(\emptyset)=f(\textsc{OPT}{})$. Similarly, we have that $f(\textsc{OPT}{}^{\prime})$ is equal to $\sum_{x\in\textsc{OPT}{}^{\prime}}\Delta(x,\pi^{x}\cap\textsc{OPT}{}^{\prime})$. By submodularity, we know that $\Delta(x,\pi^{x}\cap\textsc{OPT}{}^{\prime})$ is at least $\Delta(x,\pi^{x})$ because $\pi^{x}\cap\textsc{OPT}{}^{\prime}$ is a subset of $\pi^{x}$. Therefore, we have:

where the last equality holds by definition of $\textsc{OPT}{}^{\prime}$. ∎

We note that $\Delta(x,\pi^{x})$ is a fixed (non-random) term and therefore we can take it out of the expectation. Since $f(\textsc{OPT}{})$ is equal to $\sum_{x\in\textsc{OPT}{}}\Delta(x,\pi^{x})$, we just need to prove that $Pr[x\in\textsc{OPT}{}_{1}\setminus\textsc{OPT}{}^{S}]$ is at most $O\left(\frac{\ln(C)}{C}\right)$ for any item $x\in\textsc{OPT}{}$.

We note that the first machine is just a random machine, and the distribution of set of items sent to it, $T_{1}$, is the same as any other set $T_{i}$ for any $2\leq i\leq m$. We consider two cases for an item $x\in\textsc{OPT}{}$:

The probability of $x$ being chosen when added to a random machine is at most $\frac{\ln(C)}{C}$, i.e. $Pr[x\in\mathsf{Greedy}(T_{1}\cup\{x\})]=\frac{\ln(C)}{C}$.

The probability $Pr[x\in\mathsf{Greedy}(T_{1}\cup\{x\})]$ is at least $\frac{\ln(C)}{C}$.

In the first case, we know that $Pr[x\in\textsc{OPT}{}_{1}]\leq\frac{\ln(C)}{C}$, and therefore $Pr[x\in\textsc{OPT}{}_{1}\setminus\textsc{OPT}{}^{S}]\leq\frac{\ln(C)}{C}$ which concludes the proof.

Using Lemma 4.2, it is sufficient prove that ratio $\frac{f_{k}(S_{1}\cup\textsc{OPT}{}_{1}^{\prime})}{f(\textsc{OPT}{}^{\prime})}$ is at least $2-\sqrt{2}-O\left(\frac{1}{k}\right)$. In order to lower bound the ratio $\frac{f_{k}(S_{1}\cup\textsc{OPT}{}_{1}^{\prime})}{f(\textsc{OPT}{}^{\prime})}$, we write the following factor-revealing linear program $LP^{k,k_{2}}$, and prove in Lemma 4.4 that the solution to this LP is a lower bound on the aforementioned ratio.

For any integer $k>0$, the ratio $\frac{f_{k}(S_{1}\cup\textsc{OPT}{}_{1}^{\prime})}{f(\textsc{OPT}{}^{\prime})}$ is lower bounded by the optimum solution of linear program $LP^{k,k_{2}}$ for some integer $1\leq k_{2}\leq k$.

We want to prove that ratio $\frac{f_{k}(S_{1}\cup\textsc{OPT}{}_{1}^{\prime})}{f(\textsc{OPT}{}^{\prime})}$ is lower bounded by the solution of minimization linear program $LP^{k,k_{2}}$. It suffices to construct one feasible solution with objective value $\beta$ equal to $\frac{f_{k}(S_{1}\cup\textsc{OPT}{}_{1}^{\prime})}{f(\textsc{OPT}{}^{\prime})}$. At first, we construct this solution for every instance of the problem, and then prove its feasibility in Claim 4.5.

We remind that $\textsc{OPT}{}^{\prime}$ is the union of two disjoint sets $\textsc{OPT}{}_{1}^{\prime}$, and $\textsc{OPT}{}_{2}$. Fix a permutation $\pi$ on the items of $\textsc{OPT}{}^{\prime}$ such that every item of $\textsc{OPT}{}_{1}^{\prime}$ appears before every item of $\textsc{OPT}{}_{2}$ in $\pi$. In other words, $\pi$ is an arbitrary permutation on items of $\textsc{OPT}{}_{1}^{\prime}$ followed by an arbitrary permutation on items of $\textsc{OPT}{}_{2}$. For any item $x$ in $\textsc{OPT}{}^{\prime}$, define $\pi^{x}$ to be the set of items in $\textsc{OPT}{}^{\prime}$ that appear prior to $x$ in permutation $\pi$. For any $1\leq j\leq Dk$, we define set $S^{j}$ to be the first $j$ items of $S_{1}$. We set the linear program variables as follows:

The above assignment forms a feasible solution of $LP^{k,k_{2}}$, and its solution is equal to $\frac{f_{k}(S_{1}\cup\textsc{OPT}{}_{1}^{\prime})}{f(\textsc{OPT}{}^{\prime})}$.

The claim on the objective value of the solution is evident by definition of $\beta$. To prove that the constraints hold, we show some simple and useful facts about the marginal values of items in OPT. We note that $\sum_{x\in\textsc{OPT}{}^{\prime}}\Delta(x,\pi^{x})=f(\textsc{OPT}{}^{\prime})$ by definition of $\Delta$ values and the fact that $f(\emptyset)=0$. Similarly for any $1\leq j\leq Dk$, we have that:

We are ready to prove that all constraints $(1),(2),\cdots,(5)$ one by one. We start with constraint $(1)$. For any set $J\subset[DK]$ with size $|J|=k_{2}$, we define $S(J)$ to be $\{y_{j}|j\in J\}$ where $y_{j}$ is the $j$th item selected by algorithm $\mathsf{Greedy}$ in $S_{1}$. We also define $S^{\prime}(J)$ to be $\textsc{OPT}{}_{1}^{\prime}\cup S(J)$. Set $S^{\prime}(J)$ is a subset of $\textsc{OPT}{}_{1}^{\prime}\cup S_{1}$ with size at most $k_{2}+k_{1}=k$. Therefore $f(S^{\prime}(J))$ is a lower bound on $f_{k}(\textsc{OPT}{}_{1}^{\prime}\cup S_{1})$. We can also lower bound $f(S^{\prime}(J))$ as follows:

The first equality holds by definition of $\Delta$. The first inequality holds by submodularity of $f$, and knowing that $S^{j-1}\cap S(J)\subseteq S^{j-1}$. The second equality holds by definition of $\alpha$, and the last equality holds by definition of $c_{j}$. We claim that \Big{(}f(\textsc{OPT}{}_{1}^{\prime}\cup S^{j})-f(S^{j})\Big{)}-\Big{(}f(\textsc{OPT}{}_{1}^{\prime}\cup S^{j-1})-f(S^{j-1})\Big{)} (which is part of the right hand side of the last equality) is equal to $-b_{j}f(\textsc{OPT}{}^{\prime})$. We note that \Big{(}f(\textsc{OPT}{}_{1}^{\prime}\cup S^{j})-f(S^{j})\Big{)} is equal to $\sum_{x\in\textsc{OPT}{}_{1}^{\prime}}\Delta(x,\pi^{x}\cup S^{j})$, and similarly \Big{(}f(\textsc{OPT}{}_{1}^{\prime}\cup S^{j-1})-f(S^{j-1})\Big{)} is equal to $\sum_{x\in\textsc{OPT}{}_{1}^{\prime}}\Delta(x,\pi^{x}\cup S^{j-1})$. By taking the difference of them, we have:

which is (by definition of $b_{j}$) equal to $-b_{j}f(\textsc{OPT}{}^{\prime})$. We conclude that $f(S^{\prime})$, and consequently $f_{k}(S_{1}\cup\textsc{OPT}{}_{1}^{\prime})$ are both at least $(1-\alpha+\sum_{j\in J}a_{j}+c_{j})f(\textsc{OPT}{}^{\prime})$ which concludes the proof of constraint $(1)$.

We prove constraint $(2)$ using the fact that algorithm $\mathsf{Greedy}$ selects the item with maximum marginal value in each step. We note that the right hand side of constraint $(2)$ is $a_{j}+b_{j}+c_{j}$ which is by definition the marginal gain of item $y_{j}$ divided by $f(\textsc{OPT}{}^{\prime})$, i.e. $\frac{\Delta(y_{j},S^{j-1})}{f(\textsc{OPT}{}^{\prime})}$. We know that any item $x\in\textsc{OPT}{}_{2}$ will not be selected by algorithm $\mathsf{Greedy}$ if it is part of the input set which means that the marginal gain $(a_{j}+b_{j}+c_{j})f(\textsc{OPT}{}^{\prime})=\Delta(y_{j},S^{j-1})$ is at least the marginal gain $\Delta(x,S^{j-1})$ for any $x\in\textsc{OPT}{}_{2}$, and it is also greater than the average of these marginal gains. In other words, we have:

To finish the proof of constraint $(2)$, it suffices to prove the following inequality:

By definition of $\alpha$, and $a$ values, we have that:

which completes the proof of Equation 2, and consequently constraint $(2)$.

Now, we prove that constraint $(3)$ holds. By definition of $\alpha$, and the fact that $f(\textsc{OPT}{}^{\prime})=$ $\sum_{x\in\textsc{OPT}{}^{\prime}}$ $\Delta(x,\pi^{x})$, we know that $1-\alpha$ is equal to $\frac{\sum_{x\in\textsc{OPT}{}_{1}^{\prime}}\Delta(x,\pi^{x})}{f(\textsc{OPT}{}^{\prime})}$. We also know that: