Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection

1 Introduction

The subset selection problem is to select a subset of size at most k from a ground set of n items for maximizing some given objective function f. It arises in many applications, such as sparse regression [Miller, 2002], influence maximization [Kempe et al., 2003], and sensor placement [Krause et al., 2008], to name a few. For this general NP-hard problem, greedy algorithms were shown to be powerful. For example, when the objective function f satisfies the monotone and submodular property, the standard greedy algorithm, which iteratively adds one item with the largest marginal gain on f, achieves the optimal approximation guarantee of (1 - 1/e) [Nemhauser et al., 1978; Nemhauser and Wolsey, 1978].

However, greedy algorithms can only be performed stochastically in many realistic situations. For example, when the ground set is very large or the objective function evaluation is noisy, the standard greedy algorithm can only select an item whose marginal gain is approximately optimal in expectation at each greedy step. For large-scale applications, the random sampling technique is often employed to improve the scalability [Mirzasoleiman et al., 2015; Ohsaka and Yoshida, 2015], which makes that the best item from a random subset (instead of the whole set) of remaining items is selected in each iteration. For noisy applications, the noise in the objective function evaluation makes that the item with the largest noisy marginal gain (instead of the largest true marginal gain) is selected in each iteration [Singla et al., 2016; Qian et al., 2017b].

To the best of our knowledge, general stochastic greedy algorithms for subset selection were not studied until recently. Hassidim and Singer [2017] considered a general framework for stochastic variants of the standard greedy algorithm, called STOCHASTIC-STANDARD-GREEDY. In each iteration, a value ξ is randomly sampled from a distribution D, and then the algorithm selects one item whose marginal gain is a ξ-approximation of the largest marginal gain (i.e., at least the largest marginal gain times a factor of ξ). They proved that when f is monotone submodular, STOCHASTICSTANDARD-GREEDY achieves a (1 - e-µ )-approximation guarantee, where µ is the expectation of ξ ∼ D.

Note that real-world applications of subset selection often involve non-submodular or non-monotone objective functions, and can be subject to a more general constraint than a size constraint. In this paper, we thus theoretically study the approximation performance of the stochastic version of the corresponding greedy algorithms in these cases. Our analysis uses some quantities γ, λ and α, which characterize how close an arbitrary function f is to submodularity from different aspects [Das and Kempe, 2011; Zhou and Spanos, 2016; Zhang and Vorobeychik, 2016]. The main contributions are:

• For subset selection with a monotone (not necessarily submodular) objective function and a size constraint, the STOCHASTIC-STANDARD-GREEDY algorithm obtains an approximation guarantee of (1 - e-µγ ) (Theorem 1).
• For subset selection with a non-monotone (not necessarily submodular) objective function and a size constraint, the STOCHASTIC-RANDOM-GREEDY algorithm obtains an approximation guarantee of µe plus a term depending on λ (Theorem 2).

• For subset selection with a monotone (not necessarily submodular) objective function and a p-system constraint, the STOCHASTIC-GENERAL-GREEDY algorithm obtains an approximation guarantee of α2 µ p+α2 µ (Theorem 3).

We also show how to bound the quantities γ, λ and α in several real-world applications, implying the practical applicability of our derived approximation guarantees.

2 Preliminaries

Let R and R+ denote the set of reals and non-negative reals, respectively. 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. Let fS(T) denote the marginal value f(S∪T)-f(S). 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 three notions of "approximate submodularity", which measure to what extent a general set function f has the submodular property. The γ-submodularity ratio and the λsubmodularity index are defined based on Eq. (1), while the α-submodularity ratio is defined based on Eq. (2). It is easy to verify that γS,k(f) ≤ 1, λS,k(f) ≤ 0 and αf ≤ 1. When f is clear, we will use γS,k, λS,k 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 and a parameter k ≥ 1 is

Definition 2 (λ-Submodularity Index [Zhou and Spanos, 2016]). The submodularity index of a set function f : 2V → R with respect to a set S and a parameter k ≥ 1 is

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

Remark 1. For a general set function f, f is submodular iff λS,k(f)=0 for any S and k. For a monotone set function f, it holds: (1) f is submodular iff γS,k(f)=1 for any S and k; (2) f is submodular iff αf = 1; (3) αf ≤ γS,k(f) for any S and k, since fL(T ) in Definition 1 can be upper bounded by

where the items in T are denoted as {v∗ 1 , . . . , v∗ |T| } and | · | denotes the size of a set.

Algorithm 1 STOCHASTIC-STANDARD-GREEDY Algorithm

Input: a budget k and a distribution D

Output: a subset of V with k items

Process:

• 1: Let S = ∅.
• 2: repeat
• 3: ξ ← randomly sampled fromD.
• 4: v∗ ←an arbitrary item from V \ S s.t.

fS(v∗ ) ≥ ξ · maxv∈V \S fS(v).

• 5: S ←S ∪ v∗ .
• 6: until |S| = k
• 7: return S

An independence system is a pair (V, I), where V is a ground set and I ⊆ 2V , satisfying that ∅ ∈ I and ∀S ⊆ T ∈ I : S ∈ I. Any set S ∈ I is called an independent set. For any S ⊆ V , a maximal independent subset of S is called a basis of S. The general subset selection problem is presented in Definition 4, which is to find an independent subset of V maximizing a given objective function f. Without loss of generality, we assume that f is non-negative.

Definition 4 (Subset Selection). Given all items V = {v1, v2, . . . , vn}, an objective function f : 2V → R+ and an independence system (V, I), the goal is to find a subset S ⊆ V maximizing f(S) such that S ∈ I, i.e.,

In this paper, we will study the subset selection problem with two specific independence systems, a uniform matroid and a p-system. An independence system (V, I) is a matroid if it satisfies the additional property: ∀S, T ∈ I, |S| > |T| : ∃v ∈ S \T, T ∪v ∈ I. A uniform matroid is (V, I) with I = {S ⊆ V | |S| ≤ k}, which is actually a size constraint |S| ≤ k. An independence system (V, I) is a p-system [Jenkyns, 1976; Korte and Hausmann, 1978], if for any S ⊆ V ,

Note that a p-system is much more general than a uniform matroid, and even covers the intersection of p matroids (i.e., (V, ∩pi=1Ii), where each (V, Ii) is a matroid) [Calinescu et al., 2011].

3 Non-submodular Functions

For the subset selection problem with a monotone submodular objective function f and a size constraint |S| ≤ k, it was proved that STOCHASTIC-STANDARD-GREEDY finds a subset S of V with E[f(S)] ≥ (1 - e-µ ) · OPT [Hassidim and Singer, 2017]. Note that E[·] denotes the expectation of a random variable, and OPT denotes the optimal function value. As presented in Algorithm 1, instead of selecting one item with the largest marginal gain, the stochastic algorithm selects one item whose marginal gain is at least a factor of ξ from the largest marginal gain in each iteration, where ξ ∈ (0, 1] is drawn i.i.d. from some distribution D. Let µ denote the expectation of ξ ∼ D.

In this section, we consider a more general situation, where f is not necessarily submodular. The approximation guarantee is shown in Theorem 1. The proof relies on Lemma 1, which gives the expected improvement on f in one iteration.

Lemma 1. Let Si denote the subset S after i iterations of STOCHASTIC-STANDARD-GREEDY. Then, we have

Proof. Let S∗ be an optimal subset, i.e., f(S∗ ) = OPT, and let ξi denote the value of ξ in the i-th iteration of Algorithm 1. Then, for any given Si, we have

where the first inequality is by lines 3-5 of Algorithm 1, the second is by |S∗ \Si| ≤ k, the third is by Definition 1 and the monotonicity of f, and the last is by f(S∗ ∪ Si) ≥ f(S∗ ) = OPT. Taking the expectation over both sides, the lemma holds, since E[ξi+1 | ξi+1 ∼ D] = µ.

Theorem 1. For subset selection with a monotone objective function and a size constraint, STOCHASTIC-STANDARDGREEDY finds a subset S ⊆ V with |S| = k and

where γmin = minS:|S|=k-1 γS,k.

Proof. Taking the expectation over Si, we know from Lemma 1 that for 0 ≤ i ≤ k - 1,

Note that γSi,k ≥ γmin since |Si| ≤ k-1 and γS,k decreases with S. By a simple transformation, we can equivalently get

Based on this inequality, an inductive proof can show that, for 0 ≤ i ≤ k,

Thus, for the returned subset Sk, we get

Note that our derived approximation guarantee in Theorem 1 is consistent with known results in specific cases.

Remark 2. When f is submodular (where γmin = 1), it recovers the approximation ratio 1-e-µ [Hassidim and Singer, 2017]; when the stochastic behavior is due to random sampling (where µ ≥ 1 - δ), it recovers the approximation ratio 1 - e-(1-δ)γmin [Khanna et al., 2017]; when the algorithm performs exactly (where µ = 1), it recovers the approximation ratio 1 - e-γS,k [Das and Kempe, 2011], where S is the returned subset.

Algorithm 2 STOCHASTIC-RANDOM-GREEDY Algorithm

Input: a budget k and a distribution D

Output: a subset of V with k items

Process:

• 1: Let S = ∅.
• 2: repeat
• 3: ξ ← randomly sampled fromD.
• 4: U ∗ ←an arbitrary subset of V \ S with size k s.t. ∑v∈U ∗ fS(v) ≥ ξ · maxU⊆V \S,|U|=k ∑v∈U fS(v).
• 5: v ←uniformly chosen fromU ∗ at random.
• 6: S ←S ∪ v.
• 7: until |S| = k
• 8: return S

4 Non-monotone Functions

In this section, we consider the subset selection problem with a non-monotone (not necessarily submodular) objective function f and a size constraint. It was known that when f is submodular, the standard greedy algorithm fails to provide any constant guarantee, while the random greedy algorithm can achieve a (1/e)-approximation guarantee [Buchbinder et al., 2014]. Instead of selecting the best item in each iteration, the random greedy algorithm selects one from the best k items uniformly at random. We thus analyze the stochastic version of the random greedy algorithm, called STOCHASTIC-RANDOM-GREEDY as presented in Algorithm 2. As in [Buchbinder et al., 2014], we also assume that there are 2k "dummy" items in V whose marginal gain to any set is 0. We prove the approximation guarantee in Theorem 2 by utilizing the recursive inequality shown in Lemma 3. Note that the submodularity index λ is used here instead of the submodularity ratio γ, since γ can be negative for a nonmonotone function f.

Lemma 2. [Zhou and Spanos, 2016] Given a set function f : 2V → R+, let S(p) be a random subset of S ⊆ V , where each item of S appears in S(p) with probability at most p. Then, we have

Lemma 3. Let Si denote the subset S after i iterations of STOCHASTIC-RANDOM-GREEDY, and let S∗ denote an optimal subset. Then, we have

Proof. According to lines 3-6 of Algorithm 2 and E[ξ | ξ ∼ D] = µ, we have

where the second inequality is by |S∗ \ Si| ≤ k and the existence of "dummy" items, and the last is by Definition 2.

Theorem 2. For subset selection with a non-monotone objective function and a size constraint, STOCHASTIC-RANDOMGREEDY finds a subset S ⊆ V with |S| = k and

where λmin = minS:|S|=k-1 λS,k.

Proof. Taking the expectation over Si, we know from Lemma 3 that for 0 ≤ i ≤ k - 1,

Note that λSi,k ≥ λmin since |Si| ≤ k-1 and λS,k decreases with S. We define a function g : 2V \S∗ → R+ as for any S ⊆ V \ S∗ , g(S) = f(S ∪ S∗ ). Then,

It is easy to see that any item is selected with probability at most 1/k in each iteration of Algorithm 2. Thus, any item of V \ S∗ appears in Si \ S∗ with probability at most 1 - (1 - 1/k)i . Note that Si \ S∗ is a random subset of V \ S∗ . By applying Lemma 2 to the function g, we get

where the last inequality is by g(∅) = f(S∗ ) = OPT, |V \ S∗ | ≤ n and λV \S∗ ,2(g) ≤ 0. Based on Definition 2, we get

Thus, we get

Based on this recursive inequality, an inductive proof can show that for 0 ≤ i ≤ k, if µ < 1,

Thus, for the returned subset Sk, we get, if µ < 1,

where the last inequality is derived by (1 + 1-µ k-1 )k ≥ 1 + (1-µ)k k-1 , (1- 1k )k-1 ≥ 1e , (1- µk )k ≥ 1-µ and λS,k ≤ 0 for any S ⊆ V and k ≥ 1. If µ = 1, we have

Thus, we can get a unified lower bound on E[f(Sk)] for any µ ∈ (0, 1], i.e.,

Note that this derived approximation guarantee is consistent with known results for the random greedy algorithm.

Remark 3. When the algorithm performs exactly (where µ = 1), it recovers the approximation bound 1e · OPT + n(n-1) 2 λV,2 + λmin [Zhou and Spanos, 2016], which further recovers the approximation ratio 1e for submodular f (where λS,k=0 for any S⊆V and k≥1) [Buchbinder et al., 2014].

5 General Constraints

In this section, we consider a more general constraint, i.e., a subset S belongs to a p-system. Note that a p-system covers an intersection of p matroids, and of course covers a uniform matroid (i.e., a size constraint |S| ≤ k). That is, we study the subset selection problem with a monotone (not necessarily submodular) objective function f and a psystem constraint. It was known that when f is submodular, the general greedy algorithm, which iteratively adds one

Algorithm 3 STOCHASTIC-GENERAL-GREEDY Algorithm

Input: an independence system (V, I) and a distribution D Output: a basis of V

Process:

1: Let S = ∅ and U = V .

• 2: repeat

3: U ← {v ∈ U | S ∪ v ∈ I}

4:

if U ̸= ∅ then

5:

ξ ← randomly sampled from D.

6:

7:

v∗ ← an arbitrary item from U s.t.

fS(v∗ ) ≥ ξ · maxv∈U fS(v).

S ← S ∪ v∗ and U ← U \ v∗ .

8: end if

• 9: until U = ∅
• 10: return S

item with the largest marginal gain among those items that keep the set independent, can achieve a tight approximation guarantee of 1/(p + 1) [Calinescu et al., 2011]. We thus analyze the stochastic version of the general greedy algorithm, called STOCHASTIC-GENERAL-GREEDY as presented in Algorithm 3. We prove the approximation guarantee in Theorem 3. Note that the submodularity ratio α is used here, since we need a weak version of the diminishing return property (i.e., Eq. (2)) in the proof.

Lemma 4. [Fisher et al., 1978] For δi, ρi ≥ 0 with 0 ≤ i ≤ k - 1, if it satisfies that ∑t-1 i=0 δi ≤ t for 1 ≤ t ≤ k and ρi-1 ≥ ρi for 1 ≤ i ≤ k - 1, then ∑k-1 i=0 δiρi ≤ ∑k-1 i=0 ρi.

Theorem 3. For subset selection with a monotone objective function and a p-system constraint, STOCHASTICGENERAL-GREEDY finds a basis S of V with

Proof. Let S∗ denote an optimal subset, i.e., f(S∗ ) = OPT. Assume that the returned basis by STOCHASTIC-GENERALGREEDY (i.e., Algorithm 3) contains k items. Let Si (0 ≤ i ≤ k) denote the subset S after i iterations of Algorithm 3, where S0 = ∅ and Sk is the returned basis. By Definition 1 and the monotonicity of f , we have

For 0 ≤ i ≤ k, let Xi = Si ∪ {v ∈ V | Si ∪ v /∈ I}. Then, in the (i + 1)-th iteration of Algorithm 3, the set U in line 3 is actually V \ Xi, which is the set of items whose inclusion into Si keep the set independent. It is easy to verify that Xi ⊆ Xi+1 and Xk = V since Sk is a basis (i.e., a maximal independent subset of V ). By the definition of a p-system (i.e., Eq. (3)), we get, for 0 ≤ i ≤ k,

since Si is a basis of Xi and Xi ∩S∗ is an independent subset of Xi. For 0 ≤ i ≤ k - 1, let S∗ i = (Xi+1 \Xi) ∩S∗ . Since Xi ⊆ Xi+1 and Xk = V , we have S∗ i ∩S∗ j = ∅ for any i ̸= j and ∪k-1 i=0 S∗ i = (Xk \X0)∩S∗ = (V \X0)∩S∗ = S∗ . Note that X0 ∩ S∗ = ∅. That is, {S∗ 0 , S∗ 1 , . . . , S ∗ k-1 } is a partition of S∗ . Then, we have

Let u∗i ∈ argmaxv∈V \Xi fSk (v). Since S∗ i ⊆ V \ Xi, we have, for any v ∈ S∗ i , fSk (v) ≤ fSk (u∗i ). Thus, we get

Since Xi ⊆ Xi+1, we have fSk (u∗i ) ≥ fSk (u∗i+1 ). For any 1 ≤ t ≤ k, it holds that

where the inequality is by Eq. (5). Thus, by Lemma 4, we get

Since Si ⊆ Sk for any i < k, by Definition 3 and the monotonicity of f , we can get

Let v∗ i ∈ argmaxv∈V \Xi fSi (v). Since u∗i ∈ V \Xi, it holds

By applying Eqs. (7), (8) and (9) to Eq. (6), we get

By the procedure of Algorithm 3, we have

Note that V \Xi is the set of items whose inclusion into Si can keep the set independent, and v∗ i is the item with the largest marginal gain among V \Xi. Taking the expectation over Si,

Then, we have

By combining Eqs. (4) and (10), taking the expectation over both sides, and using γSk,|S∗ \Sk| ≥ α (see Remark 1), we get

where the last inequality is by Eq. (11). Thus, for the returned subset Sk, we have

Note that our derived approximation guarantee in Theorem 3 is consistent with known results for the problem with submodular f and matroid constraints.

Remark 4. When f is submodular (where α = 1) and a p-system is specialized as an intersection of p-matroids, it recovers the approximation ratio µ p+µ [Hassidim and Singer, 2017], which further recovers the approximation ratio 1 p+1 of the exact algorithm (where µ = 1) [Fisher et al., 1978].

6 Applications of Approximation Guarantees

To understand the derived approximation guarantees of stochastic greedy algorithms in real-world applications, we need to provide lower bounds on γ, λ or α for the corresponding objective functions. Note that, lower bounds on γ were derived for some monotone non-submodular applications [Das and Kempe, 2011; Elenberg et al., 2016; Bian et al., 2017], and that on λ were also derived for the nonmonotone non-submodular application of causal covariate selection [Zhou and Spanos, 2016]. In this paper, we thus only analyze the submodularity ratio α, which was never touched before. We give lower bounds on α in Lemmas 5 and 6 for the monotone non-submodular objective functions in the applications of Bayesian experimental design and non-parametric learning. The proofs are inspired from that of Propositions 1 and 2 in [Bian et al., 2017], which prove lower bounds on γ.

In Bayesian experimental design, the goal is to select observations to maximize the quality of parameter estimation. Krause et al. [2008] considered the Bayesian A-optimality objective function, which is to maximally reduce the variance of the posterior distribution over parameters in linear models. Let X = [x1, x2, . . . , xn] ∈ Rd×n denote the observation matrix, where xi ∈ Rd . Assume that each xi is normalized, i.e., ‖xi‖ = 1. Let XS ∈ Rd×|S| denote the submatrix of X with its columns indexed by S ⊆ {1, 2, . . . , n}. Let tr(·) denote the trace of a matrix and let σi(·) denote the i-th largest singular value of a matrix. The linear model is described as yS = XT S θ + w, where θ ∼ N(0,Λ-1 ), Λ = β2 Id, w ∼ N(0, δ2 I|S|), and Ij denotes the identity matrix of size j. Then, the A-optimality objective function is defined as

which is monotone non-submodular [Krause et al., 2008].

Lemma 5. For the A-optimality objective function (i.e., Eq. (12)) in Bayesian experimental design, the submodularity ratio α can be lower bounded as

Proof. For any column index set S ⊆ {1, . . . , n} and v /∈ S,

where the third and the fifth equalities are by the definition of the trace of a matrix, the inequality is by Cauchy interlacing inequality of singular values [Strang, 2006], the sixth equality is by the linearity of the trace and the last is by tr(XvXT v ) = ‖Xv‖2 = 1. We can similarly derive that

According to Definition 3, the lemma thus holds.

In non-parametric learning (e.g., sparse Gaussian processes), the goal is to select a set of representative data points. Let C ∈ Rn×n be the covariance matrix parameterized by a positive definite kernel. Let CS ∈ R|S|×|S| denote the submatrix of C with its rows and columns indexed by S ⊆ {1, 2, . . . , n}. The determinantal function

is often involved in the objective functions of non-parametric learning, e.g., [Lawrence et al., 2003; Kulesza and Taskar, 2012]. Although the logarithm of f is monotone submodular [Krause and Guestrin, 2005], the determinantal function f itself is not submodular in general. Let λi(·) denote the ith largest eigenvalue value of a squire matrix. For notational convenience, we will use A and AS to denote In + δ-2C and I|S| + δ-2CS, respectively.

Lemma 6. For the determinantal function (i.e., Eq. (13)) in non-parametric learning, the submodularity ratio α can be lower bounded as

Proof. For any index set S ⊆ {1, . . . , n} and v /∈ S, we have fS(v) = det(AS∪v) - det(AS)

where the inequality is derived by Cauchy interlacing inequality. We can similarly derive that

fS(v) ≤ (λ1(AS∪v) - 1) · ∏|S| i=1 λi(AS). Thus, for any S ⊆ T and v /∈ T , we have fS (v) fT (v) ≥ (λ|S∪v|(AS∪v) - 1) · ∏|S| i=1 λi(AS) (λ1(AT∪v) - 1) · ∏|T | i=1 λi(AT ) ≥ λ|S∪v|(AS∪v ) - 1 (λ1(AT∪v) - 1) · ∏|T |-|S| i=1 λi(AT ) ≥ λn(A) - 1 (λ1(A) - 1) ∏n-1 i=1 λi(A) ,

where the last two inequalities are derived by Cauchy interlacing inequality. Thus, the lemma holds.

7 Conclusion

In this paper, we prove the approximation guarantees of general stochastic greedy algorithms for subset selection with non-monotone or non-submodular objective functions and also with a general constraint. This largely extends previous studies, which mainly focused on subset selection with monotone submodular objective functions and a size constraint. Moreover, we show that the derived approximation guarantees are applicable to real-world subset selection tasks.

Acknowledgments

This work was supported by the NSFC (61603367, 61672478), the Jiangsu NSF (BK20160066), the Science and Technology Innovation Committee Foundation of Shenzhen (ZDSYS201703031748284), and the Royal Society Newton Advanced Fellowship (NA150123).