Distributed Pareto Optimization for Subset Selection

1 Introduction

The subset selection problem, which aims to select a subset of size at most k from a ground set of n items for maximizing some given objective function f, captures a wide variety of real-world applications, such as maximum coverage [Feige, 1998], influence maximization [Kempe et al., 2003], sparse regression [Miller, 2002], active set selection [Rasmussen, 2004] and exemplar-based clustering [Dueck and Frey, 2007], to name a few. It is generally NP-hard, but the simple greedy algorithm, which iteratively selects one item with the largest marginal gain, was shown to be a good approximation solver. For examples, for a monotone submodular function f, the greedy algorithm achieves the optimal approximation guarantee of (1 - 1/e) [Nemhauser et al., 1978; Nemhauser and Wolsey, 1978]; for sparse regression where f can be non-submodular, it obtains the best-so-far approximation guarantee of (1-e-γ ) [Das and Kempe, 2011], where γ is the submodularity ratio.

Recently, a new approach Pareto Optimization for Subset Selection (POSS) has been shown superior to the greedy algorithm [Qian et al., 2015; 2017b]. The idea of POSS is to reformulate the original subset selection problem as a bi-objective optimization problem that requires maximizing the given objective f and minimizing the subset size simultaneously. To solve this bi-objective problem, a randomized iterative procedure is employed, which randomly generates a new solution (i.e., subset) in each iteration. POSS was proved to achieve the same general approximation guarantee as the greedy algorithm, and was shown better on some subclasses [Das and Kempe, 2008]. Furthermore, it has achieved significantly better empirical performance on the applications of influence maximization and sparse regression.

To achieve a good performance, POSS requires running 2ek2n (e ≈ 2.71828 is Euler's number) iterations, which could be unsatisfactory for large k and n. Qian et al. [2016] thus further proposed a parallel version of POSS (called PPOSS), which generates multiple new solutions in parallel in each iteration instead of generating only one new solution. PPOSS can achieve linear speedup in the number of iterations while preserving the solution quality.

Note that the subset selection applications often come with massive data sets, e.g., the number of social network users in influence maximization and the number of variables in sparse regression can be millions. However, both POSS and PPOSS require centralized access to the full data set, which makes them impractical for large-scale real-world applications. The large-scale data set cannot be stored on one single machine, and must be distributed among a set of machines.

In this paper, we propose a distributed version of POSS (called DPOSS), which has a bounded approximation guarantee for subset selection with monotone objective functions. DPOSS uses a two-round divide and conquer strategy and can be easily implemented in the MapReduce framework. We conducted experiments using Spark on maximum coverage and sparse regression, two typical applications with the objective function being submodular and non-submodular, respectively. The results on real-world data sets with size ranging from thousands to millions show that DPOSS achieves performance close to the centralized POSS (the average approximation ratios on the two applications are at least 99.6% and

98.6%, respectively), and clearly outperforms the state-ofthe-art distributed greedy algorithm RANDGREEDI [Mirzasoleiman et al., 2013; Barbosa et al., 2015].

We start the rest of the paper by introducing the subset selection problem and the POSS algorithm, respectively. In Section 4, we propose the DPOSS algorithm and give the theoretical analysis. Section 5 presents the empirical studies. The final section concludes this paper.

2 Subset Selection

Given a ground set V = {v1, v2, . . . , vn}, we study the functions f : 2V → R over subsets of V . A set function f is monotone if for any S ⊆ T, f(S) ≤ f(T). Without loss of generality, we assume that monotone functions are normalized, i.e., f(∅) = 0. A set function f : 2V →R is submodular [Nemhauser et al., 1978] if for any S ⊆ T ⊆ V ,

or equivalently, for any S ⊆ T ⊆ V and v /∈ T ,

Note that we represent a singleton set {v} by v for simplicity.

We then give two notions of "approximate submodularity", which measure to what extent a general set function f has the submodular property. The γ- and α-submodularity ratios are defined based on Eqs. (1) and (2), respectively. For a monotone set function f, it is easy to see that 0 ≤ γS,l(f) ≤ 1, 0 ≤ αf ≤ 1, and f is submodular iff γS,l(f) = αf = 1. For some concrete monotone non-submodular functions, lower bounds on γ and α were derived [Das and Kempe, 2011; Elenberg et al., 2016; Bian et al., 2017; Qian et al., 2018]. When f is clear, we will use γS,l and α for short.

Definition 1 (γ-Submodularity Ratio [Das and Kempe, 2011]). The submodularity ratio of a set function f : 2V → R with respect to a set S ⊆ V and a parameter l ≥ 1 is

Definition 2 (α-Submodularity Ratio [Zhang and Vorobeychik, 2016; Qian et al., 2017a]). The submodularity ratio of a set function f : 2V →R is

The subset selection problem as presented in Definition 3 is to select a subset S of V such that a given objective f is maximized with the size constraint |S| ≤ k, where | · | denotes the size of a set. For a monotone objective function f, the greedy algorithm, which iteratively adds one item with the largest marginal gain until k items are selected, can achieve an approximation guarantee of (1-e-γS,k ) [Das and Kempe, 2011], where S is the subset output by the greedy algorithm. Particularly, when f is submodular (i.e., γS,k = 1), the approximation guarantee becomes 1 - e-1 , which is optimal in general [Nemhauser andWolsey, 1978].

Definition 3 (Subset Selection). Given all items V = {v1, v2, . . . , vn}, an objective function f and a budget k, it is to find a subset of at most k items maximizing f, i.e.,

Here are two applications of subset selection, that will be investigated in this paper. Given a family of sets that cover a universe of elements, maximum coverage [Feige, 1998] as presented in Definition 4 is to select at most k sets whose union is maximal. It is easy to verify that f is monotone and submodular. Sparse regression [Miller, 2002] as presented in Definition 5 is to find a sparse approximation solution to the linear regression problem. Note that we do not distinguish S and its index set {i | vi ∈ S} for notational convenience, and we assume without loss of generality that all variables are normalized to have expectation 0 and variance 1. The objective function R2 z,S is monotone, but not necessarily submodular [Das and Kempe, 2011].

Definition 4 (Maximum Coverage). Given a set U of elements, a collection V = {v1, v2, . . . , vn} of subsets of U, and a budget k, it is to find at most k sets from V maximizing the number of covered elements, i.e.,

Definition 5 (Sparse Regression). Given all observation variables V = {v1, v2, . . . , vn}, a predictor variable z and a budget k, it is to find at most k variables from V maximizing the squared multiple correlation [Diekhoff, 1992; Johnson and Wichern, 2007], i.e.,

where MSEz,S denotes the mean squared error, i.e.,

3 The POSS Algorithm

Qian et al. [2015] proposed a new subset selection method by Pareto optimization, briefly called POSS. Let a binary vector s ∈ {0, 1}n represent a subset S of V , where si = 1 if S contains the item vi and si = 0 otherwise. We will not distinguish s ∈ {0, 1}n and its corresponding subset for notational convenience. The POSS algorithm reformulates the original problem Eq. (3) as a bi-objective minimization problem

where

That is, POSS maximizes the original objective function f and minimizes the subset size |s| simultaneously. Note that setting f1 to +∞ is to exclude overly infeasible solutions (i.e., subsets), the size of which is at least 2k.

To compare two solutions in the bi-objective setting, both the two objective values have to be considered. For two solutions s and s′ , s weakly dominates s′ (i.e., s is better than s′ , denoted as s ⪯ s′ ) if f1(s) ≤ f1(s′ ) ∧ f2(s) ≤ f2(s′ ); s dominates s′ (i.e., s is strictly better, denoted as s ≺ s′ ) if

Algorithm 1 POSS Algorithm

Input: all items V = {v1, v2, . . . , vn}, an objective function f : 2V →R and a budget k

Parameter: the number T of iterations

Output: a subset of V with at most k items

Process:

• 1: Let s = {0}n and P = {s}.
• 2: Let t = 0.
• 3: while t < T do
• 4: Select s from P uniformly at random.
• 5: Generate s′ by flipping each bit of s with prob. 1/n.
• 6: if ∄z ∈ P such that z ≺ s′ then
• 7: P = (P \ {z ∈ P | s′ ⪯ z}) ∪ {s′ }.
• 8: end if
• 9: t = t + 1.
• 10: end while
• 11: return argmaxs∈P,|s|≤k f(s)

s ⪯ s′ and either f1(s) < f1(s′ ) or f2(s) < f2(s′ ). But if neither s ⪯ s′ nor s′ ⪯ s, they are incomparable.

As described in Algorithm 1, POSS uses a randomized iterative procedure to solve the bi-objective problem. It starts from the solution {0}n representing an empty set (line 1) and then iteratively tries to improve the solutions in the archive P (lines 3-10). In each iteration, a new solution s′ is generated by randomly flipping bits of an archived solution s (line 5), which is uniformly randomly selected from the current P (line 4); if s′ is not dominated by any archived solution in P (line 6), it will be added into P, and meanwhile those archived solutions weakly dominated by s′ will be removed from P (line 7). After running T iterations, the best solution w.r.t. the original problemEq. (3) is selected fromP, i.e., the solution with the largest f value among those satisfying the size constraint in P is selected (line 11).

For subset selection with monotone objective functions, POSS using E[T] ≤ 2ek2n was proved to achieve the same general approximation guarantee as the greedy algorithm [Qian et al., 2015; 2017b]. Note that we use E[·] to denote the expectation of a random variable. On some examples of maximum coverage and sparse regression, it was shown that POSS using polynomial iterations can find an optimal solution while the greedy algorithm cannot. Since the required number 2ek2n of iterations is impractical for large k and n, Qian et al. [2016] further proposed the PPOSS algorithm by generating multiple solutions in parallel in each iteration instead of generating only one solution. They proved that PPOSS can achieve linear speedup in the number of iterations without sacrificing the solution quality. However, both POSS and PPOSS require centralized access to the ground set V , since randomly generated subsets of V have to be evaluated on one single machine. Thus, they are not readily applicable to large-scale subset selection applications, where the ground set V is too large to be stored on one single machine.

4 The DPOSS Algorithm

In this section, we propose a distributed version of POSS, called DPOSS. As shown in Algorithm 2, DPOSS is a sim-

Algorithm 2 DPOSS Algorithm

Input: all items V = {v1, v2, . . . , vn}, an objective function f : 2V → R, a budget k and the number m of machines

Parameter: T1, T2, . . . , Tm, Tm+1

Output: a subset of V with at most k items

Process:

• 1: Partition V into m sets V1, V2, . . . , Vm arbitrarily so that each Vi can fit on one machine.
• 2: Run POSS with T = Ti on each Vi to find a subset si.
• 3: Merge the m resulting subsets into a set U = ∪mi=1si.
• 4: Run POSS with T = Tm+1 on U to find a subset sm+1.
• 5: return argmaxs∈{s1,s2,...,sm+1} f(s)

ple two-round algorithm. In the first round, it arbitrarily distributes the ground set V over m machines, and then each machine runs POSS to find a subset si (1 ≤ i ≤ m) in parallel. In the second round, the m resulting subsets are merged on one machine, and then POSS is run on ∪mi=1si to find another subset sm+1. The final returned subset is the best one among these m+1 subsets. The number of iterations in each run of POSS is a parameter, which could affect the quality of the final output subset. Their relation will be analyzed later.

Note that when the size of the union ∪mi=1si exceeds the capacity of one machine in the second round of DPOSS, the algorithm will break down. But DPOSS can be easily extended to multi-round to address this issue. The idea is to continue to distribute the union of the partial subsets over several machines after each round, until the union can fit on one single machine. Note that if we have extra machines, we can also run PPOSS instead of POSS for further acceleration.

Then, we theoretically analyze the approximation performance of DPOSS for subset selection with monotone objective functions. Let OPT denote the optimal function value of Eq. (3). For an arbitrary partition {V1, V2, . . . , Vm} of the ground set V , let ni = |Vi| and nmax = max{ni | 1 ≤ i ≤ m}. Theorem 1 gives the approximation guarantee of DPOSS. The proof is inspired from that of Theorem 1 in [Qian et al., 2015], and it relies on the following two lemmas. For 1 ≤ i ≤ m, let oi ∈ argmaxs⊆Vi:|s|≤k f(s) denote an optimal subset of Vi. Lemma 1 gives a lower bound on the f value of the best oi. Its proof is inspired from that of Theorem 3 in [Mirzasoleiman et al., 2016]. Lemma 2 shows that for any subset s ⊆ Vi, there exists another item, the inclusion of which can improve f by at least a quantity proportional to the current distance to the optimum.

Lemma 1. For any partition of V , it holds that

Proof. We first prove that max{f(oi)|1≤i≤m}≥ αm OPT. Let o denote an optimal subset of V , i.e., f(o) = OPT . For 1 ≤ i ≤ m, let Ai = o ∩ Vi. Thus, ∪mi=1Ai = o and for any i ̸= j, Ai ∩ Aj = ∅. Then, we have

1 ≤ i ≤ m, it holds that

where the inequality is by the definition of α-submodularity ratio (i.e., Definition 2) since {vi1 , . . . , vi l-1 } ⊆ ∪i-1 j=1Aj ∪ {vi1 , . . . , vi l-1 }. Note that for any 1 ≤ i ≤ m, f(oi) ≥ f(Ai), since Ai ⊆ Vi and |Ai| ≤ |o| ≤ k. Thus, we get

which leads to max{f(oi) | 1 ≤ i ≤ m} ≥ αm · OPT .

We then prove that max{f(oi)|1 ≤ i ≤m} ≥ γ∅,k k OPT. By the definition of γ-submodularity ratio (i.e., Definition 1), f(o) ≤ ∑v∈o f(v)/γ∅,k. Let v∗ ∈ argmaxv∈o f(v). Then f(v∗ ) ≥ γ∅,kf(o) |o| ≥ γ∅,k k · OPT. Since {V1, V2, . . . , Vm} is a partition of V , v∗ must belong to one of these m sets. Thus, max{f(oi) | 1 ≤ i ≤ m} ≥ f(v∗ ) ≥ γ∅,k k · OPT.

Lemma 2. [Qian et al., 2016] For any s ⊆ Vi (1 ≤ i ≤m), there exists one item v ∈ Vi \ s such that

Theorem 1. For subset selection with a monotone objective function f, DPOSS using E[max{Ti | 1 ≤ i ≤ m}] = O(k2nmax(1 + logm)) finds a subset s with |s| ≤ k and

Proof. In the first round of DPOSS, we analyze themaximum number of iterations (i.e., max{Ti | 1 ≤ i ≤ m}) on each machine until f(si) ≥ (1 - e-γmin ) · f(oi) for each 1 ≤ i ≤ m. For the machine running POSS on Vi (1 ≤ i ≤ m), let J imax denote the maximum value of j ∈ {0, 1, . . . , k} such that in the archive P, there exists a solution s with |s| ≤ j and f (s) ≥ (1 - (1 - γmin k )j ) · f(oi). That is,

We then only need to analyze max{Ti | 1 ≤ i ≤ m} until min{J imax | 1 ≤ i ≤ m} = k, since J imax = k implies that for POSS running on Vi, there exists one solution s in P satisfying that |s| ≤ k and f(s) ≥ (1-(1- γmin k )k )·f(oi) ≥ (1 - e-γmin ) · f(oi), thus f(si) ≥ (1 - e-γmin ) · f(oi).

The initial value of min{J imax | 1≤i≤m} is 0, since for any 1 ≤ i ≤m, POSS running on Vi starts from {0}n , and then J imax = 0. Assume that currently min{J imax | 1 ≤ i ≤ m}=j <k and the number of J imax = j is l (1 ≤ l ≤ m), i.e., |{J imax =j | 1≤i≤m}| = l. For POSS running on Vi, let zi be a corresponding solution with the value J imax , i.e., |zi| ≤ J imax and

It is easy to see that J imax cannot decrease because cleaning zi from P (line 7 of Algorithm 1) implies that zi is weakly dominated by the newly generated solution, which must have a smaller size and a larger f value. Thus, we can conclude that j never decreases and the corresponding l never increases.

By Lemma 2, we know that for any 1 ≤ i ≤ m, flipping one specific 0 bit of zi (i.e., adding a specific item) can generate a new solution s′ , which satisfies that f(s′ ) - f(zi) ≥

where the last inequality is by Eq. (4) and γzi,k ≥ γmin, which can be easily derived from |zi| ≤ J imax < k and γs,k decreasing with s. Since |s′ | = |zi| + 1 ≤ J imax + 1, s′ will be included into P; otherwise, s′ must be dominated by one solution in P (line 6 of Algorithm 1), which makes a contradiction with the definition of J imax . After including s′ , J imax increases by at least 1. Let Pmax denote the largest size of P during the run of POSS. Thus, J imax can increase by at least 1 in one iteration with probability at least 1 Pmax · 1 ni (1 - 1 ni )ni-1 ≥ 1 eniPmax , where 1 Pmax is a lower bound on the probability of selecting zi in line 4 of Algorithm1 and 1 ni (1- 1 ni )ni-1 is the probability of flipping only a specific bit of zi in line 5. By the procedure of POSS, we know that the solutions maintained in P must be incomparable. Thus, each value of one objective can correspond to at most one solution in P. Because the solutions with |s| ≥ 2k have +∞ value on the first objective, they must be excluded from P. Thus, Pmax ≤ 2k, which implies that J imax can increase by at least 1 in one iteration with probability at least 1 2ekni . We then get that after one iteration in the first round of DPOSS, l can decrease by at least 1 with probability at least

since it is sufficient that at least one of those J imax = j increases. Thus, the expected number of iterations until j increases (i.e., l decreases to 0) is at most

where the inequality is by 1 (1- 1 2eknmax )l =(1+ 1 2eknmax 1- 1 2eknmax )l ≥

1+ l 2eknmax 1- 1 2eknmax = 1+ l 2eknmax-1 , and Hm is the m-th harmonic number. Then, the expected number of iterations until min{J imax | 1≤i≤m}=k (i.e., j increases to k) is at most (m + (2eknmax - 1)Hm)k = O(k2nmax(1 + log m)), i.e.,

Since min{J imax | 1 ≤ i ≤ m} = k implies that f(si) ≥ (1-e-γmin )·f(oi) for any 1 ≤ i ≤ m, the f value of the final output subset satisfies that max{f(si) | 1 ≤ i ≤ m+ 1} ≥ (1 - e-γmin ) · max{f(oi) | 1 ≤ i ≤ m}. By Lemma 1, the theorem holds.

5 Experiments

In this section, we empirically evaluate the effectiveness of DPOSS on maximum coverage and sparse regression, two applications of subset selection with submodular and nonsubmodular objective functions, respectively. All of the experiments are coded in Python 2.7.14 and run on an identical configuration: a cluster of 10 quad-core machines running Spark 2.0.2. We compare DPOSS with the state-ofthe-art distributed greedy algorithm RANDGREEDI [Mirzasoleiman et al., 2013; Barbosa et al., 2015; Mirrokni and Zadimoghaddam, 2015; Lucic et al., 2016; Khanna et al., 2017] on regular-scale as well as large-scale data sets. By regular-scale data sets, we can examine how well DPOSS performs compared with the centralized POSS. To implement DPOSS, each machine runs POSS for 2ek2N iterations, where N is the number of items allocated to that machine, as suggested in [Qian et al., 2015; 2017b].

Maximum Coverage. We use 8 regular-scale and 2 largescale data sets 1 . Note that some data sets are given by graphs, and we create a set for each node which contains the node itself and its adjacent nodes. The budget k is set to 8. For regular-scale data sets, we set the number m of reducers to {1, 2, . . . , 10}. For each data set and each m > 1, we perform the partition by assigning items uniformly randomly to the reducers. We run DPOSS and RANDGREEDI on the same 10 partitions generated independently and report the average results. When m = 1, we also repeat the run of the centralized POSS 10 times independently, since it is a randomized algorithm. Note that DPOSS with m = 1 is just the centralized POSS. The results are plotted in Figure 1. We can observe that DPOSS is almost always better than RANDGREEDI, and the only loss is for m = 1 on the frb59-26-mis data set. Note that on the retail data set, the standard deviation of the f value by DPOSS is 0, which is because DPOSS always finds the same good solution in 10 runs for each m. For large-scale data sets, m is set to 300, and each machine carries out a set of reduce tasks in sequence. The results are shown in Table 1. We can observe that DPOSS performs the same as RANDGREEDI on the kosarak data set and is better on the other data set accident. The same performance on kosarak may be because RANDGREEDI has already been nearly optimal on this data set, as observed in [Barbosa et al., 2015].

1 The data sets are downloaded from http://fimi.ua. ac.be/data/, https://snap.stanford.edu/data/, https://turing.cs.hbg.psu.edu/txn131/vertex_ cover.html and http://sites.nlsde.buaa.edu.cn/ ˜kexu/benchmarks/graph-benchmarks.htm.

For regular-scale data sets, we also compute the approximation ratio of DPOSS compared to the centralized POSS. For each m = i ∈ {2, . . . , 10}, the approximation ratio is calculated through dividing the f value for m = i by that for m = 1. Figure 2(a) plots the average approximation ratios over all data sets, which are at least 99.6%, implying that DPOSS can achieve performance very close to the centralized POSS. From Figure 1, we can also observe that in some cases (e.g., m = 3 on the hamming data set), DPOSS can even be better than the centralized POSS, which may be because the partition of the full data set luckily avoids the local optimum.

Figure 3 shows the runtime speedup of DPOSS compared to the centralized POSS on two data sets hamming and frb100-40-mis. For each m=i∈{2, . . . , 10}, the speedup is calculated as the ratio of the runtime for m=1 and m=i. For m= 1, the centralized POSS runs for 2ek2n iterations. For m> 1, the number of iterations of DPOSS consists of two parts: nearly 2ek2n/m on each machine in the first round due to uniform random partition, and 2ek2 · (mk) in the second round. Thus, when m is much smaller than √n/k, the runtime of the second round can be neglected and DPOSS can achieve nearly linear speedup; when m continues to increase, the runtime of the second round will gradually dominate the whole runtime and the speedup will be far away from linear speedup. The results in Figure 3 are consistent with the analysis. For hamming, √n/k = 11.3 and thus we cannot observe linear speedup as m approaches to 10; while for frb100-40mis, √n/k = 22.4 is much larger than the maximum m = 10 and thus DPOSS always achieves nearly linear speedup.

Sparse Regression. We use 8 regular-scale and 3 largescale data sets 2 . Note that some classification data sets are used for regression, and all variables are normalized to have mean 0 and variance 1. We use the same setting as that for maximum coverage. The results on regular-scale and largescale data sets are shown in Figure 4 and Table 2, respectively. We can see that DPOSS is always better than RANDGREEDI. Figure 2(b) plots the average approximation ratios of DPOSS compared to the centralized POSS over all regularscale data sets, which are at least 98.6%. We also plot the runtime speedup of DPOSS on two data sets MicroMass and leukemia in Figure 5, which is similar to that we have observed for maximum coverage.

2 The data sets are downloaded from https://archive. ics.uci.edu/ml/datasets.html and https://www. csie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/.

6 Conclusion

Subset selection is a fundamental problem in many areas, and the POSS algorithm has been shown to be a powerful approximation solver. However, POSS requires centralized access to the full data set, restricting its large-scale applications. In this paper, we propose a distributed version of POSS (DPOSS) with a bounded approximation guarantee. Extensive experiments using Spark on the applications of maximum coverage and sparse regression show that DPOSS can achieve competitive performance to the centralized POSS; can scale well to very large data sets; and can clearly outperform the state-ofthe-art distributed greedy algorithm RANDGREEDI.

Acknowledgments

This work was supported in part by the National Key Research and Development Program of China (2017YFB1003102), the NSFC (61603367, 61672478), the Science and Technology Innovation Committee Foundation of Shenzhen (ZDSYS201703031748284), and the Royal Society Newton Advanced Fellowship (NA150123).