# optimization_of_chanceconstrained_submodular_functions__fd4f429a.pdf

The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-20)

Optimization of Chance-Constrained Submodular Functions

Benjamin Doerr,1 Carola Doerr,2 Aneta Neumann,3 Frank Neumann,3 Andrew M. Sutton4

1Laboratoire d Informatique (LIX), CNRS, Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France 2Sorbonne Universit e, CNRS, LIP6, Paris, France 3Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia 4Department of Computer Science, University of Minnesota Duluth, Duluth, MN, USA

Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a ﬁrst analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.

Introduction

Many real-world problems optimization problems involve uncertain components such as the execution length of a job, the fraction of ore in a cartload of rocks, the probability of earthquakes, etc. Safe critical systems or expensive productions must limit the potential violation of constraints imposed by such stochastic components. Constraints that explicitly address the probability of violation are known as chance constraints. Chance-constrained optimization deals with optimizing a given problem under the condition that the probability of a constraint violation does not exceed a given threshold probability α. In this work we study optimization under chance constraints for submodular functions. Submodular functions model problems where the beneﬁt of adding components diminishes with the addition of elements. They form an important class of optimization problems, and are extensively studied in the literature (Nemhauser and Wolsey 1978; Nemhauser, Wolsey, and Fisher 1978; Vondr ak 2010; Krause and Golovin 2014; Bian et al. 2017; Leskovec et al. 2007; Feldman, Harshaw, and Karbasi 2017; Harshaw et al. 2019). However, to our knowledge, submodular functions have not yet been studied in the chance-constrained setting.

Copyright c 2020, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Our Results Given a set V , we analyze the maximization of submodular functions f : 2V R subject to linear chance constraints Pr[W(S) > B] α where S V and W(S) is the sum of the random weights of the elements in S. Here, B is a deterministic constraint boundary and α is a tolerance level. The objective is thus to ﬁnd a set that maximizes f subject to the probability that its stochastic weights violate the boundary is at most α. Our focus is on monotone submodular functions, which are set functions characterized by the property that the function value cannot decrease by adding more elements. The optimization of the considered classes of submodular problems with deterministic constraints has already been investigated by (Nemhauser, Wolsey, and Fisher 1978; Leskovec et al. 2007). The theoretical contribution of this paper extends these results to the chance constrained setting. Since the computation of the chance constraint is usually not efﬁciently feasible, we assume it is evaluated by using a surrogate function that provides an upper bound on the constraint violation probability Pr[

s S W(s) > B]. This upper bound ensures that the chance constraint is met if the surrogate provides a value of at most α. As surrogates, we use popular deviation inequalities such as Chebyshev s inequality and Chernoff bounds. We show that using these surrogate functions, popular greedy algorithms are also applicable in the chanceconstrained setting. In particular, we analyze the case of uniformly distributed weights with identical dispersion and show that both inequalities only lead to a loss of a factor of 1 o(1) compared to the deterministic setting. We complement our theoretical work with an experimental investigation on the inﬂuence maximization problem in social networks. This investigation empirically analyzes the behavior of the greedy approaches for various stochastic settings. In particular, it shows the effectiveness of using Chernoff bounds for large inputs if only a small failure rate in terms of α can be tolerated.

Related work Submodular optimization has been studied for a wide range of different constraint types, see, for example, (Krause and

Golovin 2014) and references mentioned therein. Many of the results on monotone submodular functions are based on simple greedy selection strategies that are able to achieve provably the best possible approximation ratio in polynomial time, unless P=NP (Nemhauser, Wolsey, and Fisher 1978). Friedrich et al. (2019) recently showed that greedy approaches are also successful when dealing with nonmonotone submodular functions. Furthermore, Pareto optimization approaches can achieve the same worst-case performance guarantees while performing better than greedy approaches in practice if the user allows for a sufﬁciently large time budget (Qian et al. 2017b; Qian, Yu, and Zhou 2015; Qian et al. 2017a). Roostapour et al. (2019) showed that the adaptation of greedy approaches to monotone submodular problems with dynamic constraints might lead arbitrarily bad approximation behavior, whereas a Pareto optimization approach can effectively deal with dynamic changes. Evolutionary algorithms for the chanceconstrained knapsack problem, which constitutes a subclass of the chance-constrained submodular problems examined in this paper, have been experimentally investigated by Xie et al. (2019). The paper is structured as follows. Next, we introduce the class of submodular optimization problems and the algorithms that are subject to our investigations. Afterwards, we establish conditions to meet the chance constraints based on tail-bound inequalities. We present our theoretical results for chance-constrained submodular optimization for different classes of weights. Building on these foundations, we present empirical results that illustrate the effect of different settings of uncertainty on the considered greedy algorithms for the inﬂuence maximization problem in social networks. Finally, we ﬁnish with some concluding remarks.

Chance-Constrained Submodular Functions Given a set V = {v1, . . . , vn}, we consider the optimization of a monotone submodular function f : 2V R 0. A function is called monotone iff for every S, T V with S T, f(S) f(T) holds. A function f is called submodular iff for every S, T V with S T and x T we have f(S {x}) f(S) f(T {x}) f(T). We consider the optimization of such a monotone submodular function f subject to a chance constraint where each element s V takes on a random weight W(s). Precisely, we are considering constraints of the type Pr[W(S) > B] α. where W(S) =

s S W(s) is the sum of the random weights of the elements and B is the given constraint bound. The parameter α quantiﬁes the probability of exceeding the bound B that can be tolerated. It should be noted that for the uniform distribution, the exact joint distribution can, in principle, be computed as convolution if the random variables are independent. There is also an exact expression for the Irwin-Hall distribution (Johnson, Kotz, and Balakrishnan 1995) which assumes that all random variables are independent and uniformly distributed within [0, 1]. However, using these approaches may not be practical when the number of chosen items is large.

Greedy Algorithms We consider in this work the performance of greedy algorithms for the optimization of chance constrained submodular functions. Our ﬁrst greedy algorithm (GA, see Algorithm 1) starts with an empty set and subsequently adds in each iteration an element with the largest marginal gain that does not violate the chance constraint. It ends when no further element can be added. Algorithm 1 was already investigated by Nemhauser, Wolsey, and Fisher (1978) in the deterministic setting. Note that the computation of the probability Pr[W(S) > B] can usually not be computed exactly and we make use of a surrogate Pr[W(S) > B] α on this value (see line 5 of Algorithm 1). Since we use upper bounds for the constraint violation probability, we are guaranteed that the constraint is met whenever our surrogate Pr is at most α. Our second greedy algorithm is the generalized greedy algorithm (GGA), and is listed in Algorithm 2. The GGA extends the GA to the case in which the elements have different expected weights. It has previously been used in the deterministic setting (Khuller, Moss, and Naor 1999; Leskovec et al. 2007). The algorithm starts with the empty set. In each iteration, it adds an element whose ratio of the additional gain with respect to the submodular function f and the expected weight increase E[W(S {v}) W(S)] of the constraint is maximal while still satisfying the chance constraint. The algorithm terminates if no further element can be added. At this point, it compares this constructed greedy solution with each of the n solutions consisting of a single element, and returns the solution with the maximal f-value subject to the surrogate function is at most α. Note that we are using the exact calculation for Pr[W(v) > B] when considering a single element in line 9. Lines 9 and 10 of Algorithm 2 are needed in cases where large items of high proﬁt exist, see (Khuller, Moss, and Naor 1999; Leskovec et al. 2007) for more details.

Concentration Bounds We work with two different surrogates, which are concentration bounds of Chernoff and Chebyshev type. Such bounds are frequently used in the analysis of randomized algorithms (Motwani and Raghavan 1995). All bounds are wellknown and can be found, e.g., in (Doerr 2018). Theorem 1 (Multiplicative Chernoff bound). Let X1, . . . , Xn be independent random variables taking values in [0, 1]. Let X = n i=1 Xi. Let ϵ 0. Then

Pr[X (1 + ϵ)E[X]] eϵ

exp min{ϵ2, ϵ}E[X]

For ϵ 1, (2) simpliﬁes to

Pr[X (1 + ϵ)E[X]] exp ϵ2E[X]

For our experimental investigations, we work with equation (1), whereas equation (3) is used through our theoretical analysis. Note that equation (3) gives the weaker bound.

Algorithm 1: Greedy Algorithm (GA)

input: Set of elements V , budget constraint B, failure probability α.

4 v arg maxv V (f(S {v}) f(S));

5 if Pr[W(S {v }) > B] α then

6 S S {v };

7 V V \ {v };

8 until V ;

9 return S;

Algorithm 2: Generalized Greedy Algorithm (GGA)

input: Set of elements V , budget constraint B, failure probability α.

4 v arg maxv V f(S {v}) f(S) E[W (S {v}) W (S)];

5 if Pr[W(S {v }) > B] α then

6 S S {v };

7 V V \ {v };

8 until V ;

9 v arg max{v V ;Pr[W (v)>B] α} f(v);

10 return arg max Y {S,{v }} f(Y );

Therefore, our theoretical results showing approximation guarantees also hold when working with equation (1). Chernoff bounds are very useful when requiring very small values of α. For larger values of α, e.g. α = 0.1, we often get better estimates when working with a variant of Chebyshev s inequality. As we are only interested in the probability of exceeding a given constraint bound, we consider a one-sided Chebyshev inequality (also known as Cantelli s inequality), which estimates the probability of exceeding the expected value taking into account the variance of the considered random variable. Theorem 2 ((One-sided) Chebyshev s inequality). Let X be a random variable with expected value E[X] and variance Var[X] > 0. Then, for all λ > 0,

Pr[X E[X] + λ] Var[X] Var[X] + λ2 . (4)

Chance Constraint Conditions We now establish conditions to meet the chance constraint. We start by considering the Chernoff bound given in equation (3). Lemma 1. Let W(s) [a(s) δ, a(s)+δ] be independently chosen uniformly at random. If

(B E[W(X)])

3δk ln(1/α),

where k = |X|, then Pr[W(X) > B] α.

Proof. Every item has an uncertainty of δ. Instead of considering W(s) [a(s) δ, a(s) + δ] chosen uniformly at random, we can consider W (s) [0, 2δ] chosen uniformly at random and have W(s) = a(s) δ + W (s). For a selection X with |X| = k elements, we can therefore write W(X) = E[W(X)] δk +

x X W (X). We have E[W (X)] = δk. We consider the probability for exceeding this expected value by ϵδk. We set ϵ = (B E[W(X)])/(δk) which implies ϵδk + E[W(X)] = B. We investigate

Pr[W(X) > B] = Pr[W (X) > ϵδk + kδ].

Note that if ϵ = (B E[W(X)])/(δk) > 1 then Pr[W(X) > B] = 0 as all weights being maximal within their range would not exceed the bound B. For ϵ 1, we get

Pr[W(X) > B] = Pr[W (X) > ϵδk + kδ]

using equation (3). In order to meet the chance constraint, we require

ϵ2kδ 3 ln(1/α)

ϵ2 (3 ln(1/α))/(kδ).

This implies that ϵ

(3 ln(1/α))/(kδ) meets the chance constraint condition according to the considered Chernoff bound. Setting ϵ = (B E[W(X)])/(δk) leads to

(B E[W(X)])/(δk)

(3 ln(1/α))/(kδ)

(B E[W(X)])

3δk ln(1/α),

which completes the proof.

Based on Chebyshev s inequality, we can obtain the following condition for meeting the chance constraint. Lemma 2. Let X be a solution with expected weight E[W(X)] and variance Var[W(X)]. If

(1 α) Var[W(X)]

α then Pr[W(X) > B] α.

Proof. We have

Var[W(X)] Var[W(X)] + (B E[W(X)])2 α

Var[W(X)] α(Var[W(X)] + (B E[W(X)])2)

(1 α) Var[W(X)] α(B E[W(X)])2

(B E[W(X)])2 (1 α) Var[W(X)]

This together with Lemma 2 implies that the chance constraint is met if

(1 α) Var[W(X)]

Uniform IID Weights We ﬁrst study the case that all items have iid weights W(s) [a δ, a + δ] (δ a). For this case we prove that the greedy algorithm with the Chernoff bound surrogate achieves a (1 o(1))(1 1/e) approximation of the optimal solution for the deterministic setting when B = ω(1). This extends the same bound for the deterministic setting by (Nemhauser, Wolsey, and Fisher 1978) to the chanceconstrained case.

Theorem 3. Let a > 0 and 0 δ < a. Let W(s) [a δ, a + δ] be chosen uniformly at random for all s. Let

3δk ln(1/α)

a and k be the largest integer such that k + ϵ(k) kopt := B/a . Then the ﬁrst k items chosen by the greedy algorithm satisfy the chance constraint and are a 1 (1/e) exp( 1+ϵ(k) k +1+ϵ(k))-approximation. For B = ω(1), this is a (1 o(1))(1 1/e)-approximation.

Proof. Let kopt = B/a be the number of elements that are contained in an optimal solution OPT in the case that the weights are deterministic and attain the value a. Having produced a solution with k elements following the greedy procedure, we have obtained a solution X where

f(X) (1 (1 1/kopt)k) f(OPT)

due to an inductive argument given by (Nemhauser, Wolsey, and Fisher 1978). We now give a lower bound on k using Chernoff bound as a surrogate. Let X be a set of selected items containing k = |X| elements and E[X] =

x X a(x) be its expected weight, δ be the uncertainty common to all items. Since all items have the same expected weight a, we have E[W(X)] = ak. Using Lemma 1, the chance constraint is met if (B ak)

3δk ln(1/α). We have kopt = B/a for the number of elements that could be added if the weights

were deterministic. So any k with k +

3δk ln(1/α)

a kopt is feasible when using the Chernoff bound. Let

3δk ln(1/α)

kopt < (k + 1) +

3δ(k + 1) ln(1/α)

a =: β(k ).

Let X be a solution with k elements constructed by the greedy algorithm. Using the well-known estimate (1 + x) ex, we bound f(X ) from below by

(1 (1 1/kopt)k ) f(OPT)

1 1 1 β(k )

k + 1 + ϵ(k + 1)

e exp 1 + ϵ(k + 1) k + 1 + ϵ(k + 1)

When k = ω(1), the exp( ) expression is (1+o(1)), yielding the asymptotic part of the claim.

For comparison, we now determine what can be obtained from using a surrogate based on Chebyshev s inequality. This bound is weaker for small values of α, but can be better for larger values of α (depending on the other constants involved). We observe that Var[W(X)] = |X| δ2/3. Deﬁning

3αa and replacing equation (5) by

k = max {k | k + ϵ kopt}

our proof above yields the following theorem.

Theorem 4. Let a > 0 and 0 δ < a. Let W(s) [a δ, a+δ] be chosen uniformly at random for all s. Let ϵ(k) =

3αa and k be the largest integer such that k+ ϵ(k) kopt := B/a . Then the ﬁrst k items chosen by the greedy algorithm satisfy the chance constraint and are a 1 (1/e) exp( 1+ ϵ(k) k +1+ ϵ(k))-approximation. For B = ω(1), this is a (1 o(1))(1 1/e)-approximation.

Note that the main difference between the Chernoff bound and Chebyshev s inequality lies in the conﬁdence level of α that needs to be achieved as the equation using Chernoff only increases logarithmically with 1/α, whereas the one based on Chebyshev s inequality increases with the square root of 1/α. We note that, in principle, Chebyshev s inequality does not require that the items are chosen independently. We can use Chebyshev s inequality and the approach above whenever we can compute the variance.

Uniform Weights with the Same Dispersion We now consider the case that the items may have different random weights W(s) [a(s) δ, a(s) + δ]. However, we still assume the weights are chosen independently and uniformly at random. We also assume that the uncertainty δ is the same for all items. Let amax = maxs V a(s). We assume that amax+δ B

2δ α holds. This means that every single item fulﬁlls the chance constraint. Note that items that would not fulﬁll this condition could be ﬁltered out in a preprocessing step as they can

not be part of any feasible solution. Furthermore, we assume that B = ω(1) grows with the input size. The following theorem extends the results of Theorem 3 by (Leskovec et al. 2007) to the chance-constrained setting. Theorem 5. For all s V let W(s) [a(s) δ, a(s) + δ] with a(s) > 0 and 0 δ < min a(s). If amax+δ B

2δ α and B = ω(1), then the solution obtained by the Generalized Greedy algorithm GGA using Chernoff bound (3) as surrogate for the chance constraint is a (1/2 o(1))(1 1/e)- approximation.

Proof. Let S be the greedy solution constructed by the GGA (Algorithm 2) and let v be the element with the largest function value. Let T be the solution produced by the generalized greedy algorithm in the deterministic setting. We know that any solution X with E[W(X)] B

3δk ln(1/α) is feasible. Furthermore, every single item is feasible as amax+δ B

2δ α. Let ˆB = B

3δk ln(1/α). Let S = XL T be the subset of T consisting of the ﬁrst L elements exactly as chosen when working with the deterministic bound B. Note that we have f(S) f(S ) as f is monotone. If S = T, we know arg max Y {S,{v }} f(Y ) is a (1/2)(1 1/e)-approximation. Furthermore, let v V \ S be the the element with the largest function value. Note that v meets the constraint bound based on our assumptions. Let z = XL+1 \ XL T be the ﬁrst element of S not added when working with the chance constraint. If v = z, then we have E[W(S)] + a(v ) ˆB. As v is the single element with the largest function value, we have f(v ) f(z). Let x be the element added in iteration i to the partial solution Xi 1 in order to obtain Xi S . Furthermore, let OPT be an optimal solution for the deterministic setting. Then following (Leskovec et al. 2007) and using the expected cost value instead of the deterministic ones, we have

f(Xi) f(Xi 1) a(x) c(OPT) (f(OPT) f(Xi 1))

which by induction gives

Every element added to S would have also been chosen when working with the deterministic bound B. Furthermore, the single element v providing the largest possible proﬁt is also accepted due to our assumption on B and we have f(v ) f(z). We have

f(S ) + f(z) 1

where we take a(L + 1) to be a(z). Furthermore, we have

E[W(S )] + a(z) = a(z) +

s S a(s) ˆB

3δL ln(1/α)

as z is the ﬁrst element of S not added under the chance constraint. This implies

f(S) + f(v ) f(S ) + f(v ) f(S ) + f(z)

3δ(L + 1) ln(1/α)

1 1 L + 1 +

Again, we assume that α and δ are constants and B = ω(1) is growing with the input size. This implies f(S) + f(v ) (1 o(1))(1 1/e) and therefore max Y {S,{v }} f(Y ) (1/2 o(1))(1 1/e) f(OPT).

Using Chebyshev s inequality with Var[W(X)] = |X| δ2/3 and replacing

3δ(L + 1) ln(1/α) by

(1 α)(L+1)δ2

3α we obtain the following theorem.

Theorem 6. In the situation of Theorem 5, if amax+δ B

2δ α and B = ω(1), then the solution obtained by the Generalized Greedy algorithm using Chebyshev s inequality as surrogate for the chance constraint is a (1/2 o(1))(1 1/e)- approximation.

Experimental Investigations We examine our greedy algorithms on the submodular inﬂuence maximization problem (Zhang and Vorobeychik 2016; Qian et al. 2017b; Leskovec et al. 2007). We study the impact of Chebyshev s inequality and Chernoff bounds for the chance-constrained optimization problem in the context of various stochastic parameter settings.

The Inﬂuence Maximization Problem The inﬂuence maximization problem (IM) involves ﬁnding a set of most inﬂuential users in a social network. IM aims to maximize the spread of inﬂuence through a social network, which is the graph of interactions within a group of users (Kempe, Kleinberg, and Tardos 2003). A selection of users encounters a cost and the problem of inﬂuence maximization has been studied subject to a deterministic constraint that limits the cost of the user selection. Formally, the problem investigated in our experiments is deﬁned as follows. Given a directed graph G = (V, E) where each node represents a user, and each edge (u, v) E has assigned an edge probability pu,v that user u inﬂuences user v, the aim of the IM problem is to ﬁnd a subset X V such that the expected number of activated nodes E[I(X)] of X is maximized. Given a cost function c : V R+ and a budget B 0, the corresponding submodular optimization problem under chance constraints is given as

arg max X V E[I(X)] s.t. Pr[c(X) > B] α.

Budget = 20 Budget = 50 Budget = 100 Budget = 150

Chebyshev s inequality

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chernoff bounds

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

= 0.0001 = 0.001 = 0.01 = 0.1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Figure 1: Function value for budgets B = 20, 50, 100, 150 (from left to right) using Chebyshev s inequality (top) and Chernoff bound (bottom) for α = 0.1, 0.01, 0.001, 0.0001 with all the expected weights 1.

Chebyshev's inequality Budget = 20

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chernoff bound Budget = 20

Chebyshev's inequality Budget = 50

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0 5 10 15 20 25 30 35 40 45 50 55

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0 5 10 15 20 25 30 35 40 45 50 55

Chernoff bound Budget = 50

Chebyshev's inequality Budget = 100

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0 10 20 30 40 50 60 70 80 90 100

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0 10 20 30 40 50 60 70 80 90 100

Chernoff bound Budget = 100

Chebyshev's inequality Budget = 150

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chernoff bound Budget = 150

Figure 2: Maximal cost values for budgets B = 20, 50, 100, 150 (from left to right) using Chebyshev s inequality (top) and Chernoff bound (bottom) for α = 0.1, 0.01, 0.001, 0.0001 with uniform expected weights set to 1.

A more detailed description of the inﬂuence maximization problem on social networks is available at (Leskovec et al. 2007; Kempe, Kleinberg, and Tardos 2015; Zhang and Vorobeychik 2016; Qian et al. 2017b). Note though, that these works all study the case in which the cost of adding a user is deterministic.

We consider two types of cost constraints matching the settings investigated in the theoretical analysis. In the ﬁrst type, the expected weight of all nodes is 1, i.e. a(v) = 1, for all v V whereas in the second setting the expected cost of a node v is given by a(v) = deg(v) + 1. Here deg(v) denotes the degree of v in the given graph G. We examine GA for the ﬁrst type and GGA for the second type of instances. The chance constraint for both settings requires that the probability of exceeding the given bound B is at most α. We investigate different reliability thresholds given by α together with a range of δ values which determine the amount of uncertainty. To evaluate the inﬂuence maximization prob-

lem in the context of surrogate chance constraints, we employ a graph obtained from social news data, with simple settings collected from a real-world data set obtained from the social news aggregator Digg. The Digg dataset (Hogg and Lerman 2012) contains stories submitted to the platform over a period of a month, and identiﬁcation (IDs) of users who voted on the popular stories. The data consist of two tables that describe friendship links among users and the anonymized user votes on news stories (Hogg and Lerman 2012; Rossi and Ahmed 2015). We use the preprocessed data with 3523 nodes and 90244 edges, and estimated edge probabilities from the user votes based on the method in (Barbieri, Bonchi, and Manco 2012).

Uniform Chance Constraints

We consider the results for the greedy algorithm based on Chebyshev s inequality and the greedy algorithms based on Chernoff bounds subject to the uniform distribution with all

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chebyshev's inequality Budget = 100

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chernoff bound Budget = 100

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chebyshev's inequality Budget = 500

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chernoff bound Budget = 500

Figure 3: Function values for budgets B = 100 (left) and B = 500 (right) using Chebyshev s inequality and Chernoff bound for α = 0.1, 0.01, 0.001, 0.0001 with degree dependent random weights.

Chebyshev's inequality Budget = 100

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chernoff bound Budget = 100

Chebyshev's inequality Budget = 500

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Delta

Chernoff bound Budget = 500

Figure 4: Maximal cost values for budget B = 100 (left) and B = 500 using Chebyshev s inequality (top) and Chernoff bound (bottom) for α = 0.1, 0.01, 0.001, 0.0001 with degree dependent random weights.

the expected weights 1. Figure 1 shows the results of inﬂuence spread maximization for the GA based on Chebyshev s inequality (ﬁrst row) and the GA based on Chernoff bounds (second row) for budgets B = 20, 50, 100, 150. For the experimental investigations of our GA, we consider all combinations of α = 0.1, 0.01, 0.001, 0.0001, and δ = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0. We compare the results in terms of the ﬁtness achieved at each α and δ level for budgets B = 20, 50, 100, 150. For the deterministic setting, where B elements can be used, the obtained function values for B = 20, 50, 100, 150 are 161.42, 214.78, 287.56, and 345.84, respectively. For the chance-constrained problem, Figure 1 shows that the GA using Chernoff chance estimates has a better performance/higher ﬁtness values than the GA using Chebyshev s inequality among the considered δ values in most of the cases. It should be noted that higher budget values have a larger inﬂuence on the separation between the two surrogate constraints. In these cases, the Chernoff-based GA performs consistently better, and this is the result of the good asymptotic behavior of the Chernoff bound (Chernoff 1952; Mitzenmacher and Upfal 2005). We also compare the results in terms of the expected cost of the solution obtained by the GA based on Chebyshev s inequality and Chernoff bound for budgets B = 20, 50, 100, 150 as the tail inequalities limit the maximum cost. Note that cost in this case is the same as the number

of items picked by GA. The results are shown in Figure 2. The GA using the Chernoff bound is able to include more elements. The results show that the GA using the Chernoff bound allows for solutions with a larger number of elements if the budget B is high and α is small, for example B = 150, and for α = 0.001, 0.0001. The GA using Chebyshev s inequality has a better performance in the case of high α values, α = 0.1, 0.01 on the examined problem.

Non-Uniform Chance Constraints We now consider the GGA for the setting where the expected weights are not uniform but depend on the degree of the node of the graph. We consider budgets B = 100, 500 keeping the other parameters the same as in the uniform case. Figure 3 and 4 show the function and cost values obtained by the GGA based on Chernoff bounds for the combinations of α and δ. We do not observe a clear difference between using Chebyshev s inequality or Chernoff bound for the different combinations of δ and α which is due to a relatively small number of elements present in the solutions. The function values of the approaches are overall decreasing for each α with increasing value of δ. Due to the stochastic behavior of the evaluation, the obtained ﬁtness values show a jagged, irregular course with increasing value of δ.

Conclusion Chance constraints play a crucial role when dealing with stochastic components in constrained optimization. We presented a ﬁrst study on the optimization of submodular problems subject to a given chance constraint. We have shown that popular greedy algorithms making use of Chernoff bounds and Chebyshev s inequality provide provably good solutions for monotone submodular optimization problems with chance constraints. Our analysis reveals the impact of various stochastic settings on the quality of the solution obtained. Furthermore, we have provided experimental investigations that show the effectiveness of the considered greedy approaches for the submodular inﬂuence maximization problem under chance constraints.

Acknowledgements This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium Un-

locking Complex Resources through Lean Processing , by the Paris Ile-de-France region, and by a public grant as part of the Investissement d avenir project, reference ANR-11LABX-0056-LMH, Lab Ex LMH.

References Barbieri, N.; Bonchi, F.; and Manco, G. 2012. Topic-aware social inﬂuence propagation models. In IEEE Conference on Data Mining, 81 90. IEEE Computer Society. Bian, A. A.; Buhmann, J. M.; Krause, A.; and Tschiatschek, S. 2017. Guarantees for greedy maximization of nonsubmodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, 498 507. Chernoff, H. 1952. A measure of asymptotic efﬁciency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23(4):493 507. Doerr, B. 2018. Probabilistic tools for the analysis of randomized optimization heuristics. Co RR abs/1801.06733. Feldman, M.; Harshaw, C.; and Karbasi, A. 2017. Greed is good: Near-optimal submodular maximization via greedy optimization. In Proceedings of the 2017 Conference on Learning Theory, 758 784. Friedrich, T.; G obel, A.; Neumann, F.; Quinzan, F.; and Rothenberger, R. 2019. Greedy maximization of functions with bounded curvature under partition matroid constraints. In The 33rd AAAI Conference on Artiﬁcial Intelligence, AAAI 2019, 2272 2279. Harshaw, C.; Feldman, M.; Ward, J.; and Karbasi, A. 2019. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proceedings of the 36th International Conference on Machine Learning, 2634 2643. Hogg, T., and Lerman, K. 2012. Social dynamics of Digg. EPJ Data Science 1(1):5. Johnson, N. L.; Kotz, S.; and Balakrishnan, N. 1995. Continuous univariate distributions. Vol. 2. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons, Inc.

Kempe, D.; Kleinberg, J. M.; and Tardos, E. 2003. Maximizing the spread of inﬂuence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, 137 146. ACM. Kempe, D.; Kleinberg, J. M.; and Tardos, E. 2015. Maximizing the spread of inﬂuence through a social network. Theory of Computing 11:105 147. Khuller, S.; Moss, A.; and Naor, J. 1999. The budgeted maximum coverage problem. Information Processing Letters 70(1):39 45. Krause, A., and Golovin, D. 2014. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press. 71 104. Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; Van Briesen, J. M.; and Glance, N. S. 2007. Cost-effective

outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2007, 420 429. ACM. Mitzenmacher, M., and Upfal, E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. Motwani, R., and Raghavan, P. 1995. Randomized algorithms. Cambridge University Press. Nemhauser, G. L., and Wolsey, L. A. 1978. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research 3(3):177 188. Nemhauser, G. L.; Wolsey, L. A.; and Fisher, M. L. 1978. An analysis of approximations for maximizing submodular set functions - I. Math. Program. 14(1):265 294. Qian, C.; Shi, J.; Yu, Y.; Tang, K.; and Zhou, Z. 2017a. Subset selection under noise. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 3563 3573. Qian, C.; Shi, J.; Yu, Y.; and Tang, K. 2017b. On subset selection with general cost constraints. In International Joint Conference on Artiﬁcial Intelligence, IJCAI 2017, 2613 2619. Qian, C.; Yu, Y.; and Zhou, Z. 2015. Subset selection by Pareto optimization. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1, NIPS 2015, 1774 1782. Roostapour, V.; Neumann, A.; Neumann, F.; and Friedrich, T. 2019. Pareto optimization for subset selection with dynamic cost constraints. In The 33rd AAAI Conference on Artiﬁcial Intelligence, AAAI 2019, 2354 2361. AAAI Press. Rossi, R. A., and Ahmed, N. K. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artiﬁcial Intelligence, AAAI 2015, 4292 4293. AAAI Press. Vondr ak, J. 2010. Submodularity and curvature: The optimal algorithm. RIMS Kˆokyˆuroku Bessatsu B23:253 266. Xie, Y.; Harper, O.; Assimi, H.; Neumann, A.; and Neumann, F. 2019. Evolutionary algorithms for the chanceconstrained knapsack problem. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, 338 346. ACM. Zhang, H., and Vorobeychik, Y. 2016. Submodular optimization with routing constraints. In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence, AAAI 2016, 819 826. AAAI Press.