--- title: "Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection" authors: - "Chao Qian" - "Yang Yu" - "Ke Tang" doi: "10.24963/ijcai.2018/205" url: "https://ijcai.org/proceedings/2018/205" pdf: "https://ijcai.org/proceedings/2018/0205.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "1478-1484" track: "Main track" keywords: - "Heuristic Search and Game Playing: Combinatorial Search and Optimisation" - "Heuristic Search and Game Playing: Heuristic Search" - "Heuristic Search and Game Playing: Heuristic Search and Machine Learning" --- # Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection Chao Qian, Yang Yu, Ke Tang *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 1478-1484. DOI: [10.24963/ijcai.2018/205](https://doi.org/10.24963/ijcai.2018/205) ## Abstract Subset selection is a fundamental problem in many areas, which aims to select the best subset of size at most $k$ from a universe. Greedy algorithms are widely used for subset selection, and have shown good approximation performances in deterministic situations. However, their behaviors are stochastic in many realistic situations (e.g., large-scale and noisy). For general stochastic greedy algorithms, bounded approximation guarantees were obtained only for subset selection with monotone submodular objective functions, while real-world applications often involve non-monotone or non-submodular objective functions and can be subject to a more general constraint than a size constraint. This work proves their approximation guarantees in these cases, and thus largely extends the applicability of stochastic greedy algorithms. ## Full text ## 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). ## References 1. [Bian et al., 2017] A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In ICML, pages 498-507, 2017. 2. [Buchbinder et al., 2014] N. Buchbinder, M. Feldman, J. S. Naor, and R. Schwartz. Submodular maximization with cardinality constraints. In SODA, pages 1433-1452, 2014. 3. [Calinescu et al., 2011] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740-1766, 2011. 4. [Das and Kempe, 2011] A. Das and D. Kempe. Submodu- lar meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In ICML, pages 1057-1064, 2011. 5. [Elenberg et al., 2016] E. R. Elenberg, R. Khanna, A. G. Di- makis, and S. Negahban. Restricted strong convexity im- plies weak submodularity. arXiv:1612.00804, 2016. 6. [Fisher et al., 1978] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of approximations for maxi- mizing submodular set functions -II. Polyhedral Combi- natorics, pages 73-87, 1978. 7. [Hassidim and Singer, 2017] A. Hassidim and Y. Singer. Ro- bust guarantees of stochastic greedy algorithms. In ICML, pages 1424-1432, 2017. 8. [Jenkyns, 1976] T. A. Jenkyns. The efficacy of the 'greedy' algorithm. In Proceedings of the 7th Southeastern Con- ference on Combinatorics, Graph Theory and Computing, pages 341-350, 1976. 9. [Kempe et al., 2003] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social net- work. In KDD, pages 137-146, 2003. 10. [Khanna et al., 2017] R. Khanna, E. Elenberg, A. Dimakis, S. Negahban, and J. Ghosh. Scalable greedy feature se- lection via weak submodularity. In AISTATS, pages 1560- 1568, 2017. 11. [Korte and Hausmann, 1978] B. Korte and D. Hausmann. An analysis of the greedy heuristic for independence sys- tems. Annals of Discrete Mathematics, 2:65-74, 1978. 12. [Krause and Guestrin, 2005] A. Krause and C. Guestrin. Near-optimal nonmyopic value of information in graphi- cal models. In UAI, pages 324-331, 2005. 13. [Krause et al., 2008] A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Jour- nal of Machine Learning Research, 9:235-284, 2008. 14. [Kulesza and Taskar, 2012] A. Kulesza and B. Taskar. De- terminantal point processes for machine learning. Foun- dations and Trends in Machine Learning, 5(2-3):123-286, 2012. 15. [Lawrence et al., 2003] N. Lawrence, M. Seeger, and R. Her- brich. Fast sparse Gaussian process methods: The infor- mative vector machine. In NIPS, pages 625-632, 2003. 16. [Miller, 2002] A. Miller. Subset Selection in Regression. Chapman and Hall/CRC, 2nd edition, 2002. 17. [Mirzasoleiman et al., 2015] B. Mirzasoleiman, A. Badani- diyuru, A. Karbasi, J. Vondrák, and A. Krause. Lazier than lazy greedy. In AAAI, pages 1812-1818, 2015. 18. [Nemhauser and Wolsey, 1978] G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177-188, 1978. 19. [Nemhauser et al., 1978] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for max- imizing submodular set functions -I. Mathematical Pro- gramming, 14(1):265-294, 1978. 20. [Ohsaka and Yoshida, 2015] N. Ohsaka and Y. Yoshida. Monotone k-submodular function maximization with size constraints. In NIPS, pages 694-702, 2015. 21. [Qian et al., 2017a] C. Qian, J.-C. Shi, Y. Yu, and K. Tang. On subset selection with general cost constraints. In IJCAI, pages 2613-2619, 2017. 22. [Qian et al., 2017b] C. Qian, J.-C. Shi, Y. Yu, K. Tang, and Z.-H. Zhou. Subset selection under noise. In NIPS, pages 3562-3572, 2017. 23. [Singla et al., 2016] A. Singla, S. Tschiatschek, and A. Krause. Noisy submodular maximization via adap- tive sampling with applications to crowdsourced image collection summarization. In AAAI, pages 2037-2043, 2016. 24. [Strang, 2006] G. Strang. Linear Algebra and Its Applica- tions. Thomson Learning, 4th edition, 2006. 25. [Zhang and Vorobeychik, 2016] H. Zhang and Y. Vorobey- chik. Submodular optimization with routing constraints. In AAAI, pages 819-826, 2016. 26. [Zhou and Spanos, 2016] Y. Zhou and C. Spanos. Causal meets submodular: Subset selection with directed infor- mation. In NIPS, pages 2649-2657, 2016.