Submodular Maximization with Cardinality Constraints in Optimization

Submodular Maximization with Cardinality Constraints Moran Feldman Based On Submodular Maximization with Cardinality Constraints. Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz, SODA 2014 (to appear).

Set Functions Definition Given a ground set N, a set function f : 2N R assigns a number to every subset of the ground set. Intuition Consider a player participating in an auction on a set N of elements. The utility of the player from buying a subset N N of elements is given by a set function f. Basic Properties of Set Functions Non negativity the utility from every subset of elements is non- negative. N A : 0 f(A) Monotonicity - More elements cannot give less utility. A : B N f(A) f(B) 2

Submodularity - Definition Intuition Captures scenarios where elements can replace each other, but never complement each other. The marginal contribution of an element to a set decreases as more elements are added to the set. Notation Given a set A, and an elements u, fu(A) is the marginal contribution of u to A: ( ) ( A f A fu = u ) ( ) A f Formal Definition For sets A B N, and u B: fu(A) fu(B) For sets A, B N: f(A) + f(B) f(A B) + f(A B) 3

Submodular Function - Example 7 Too heavy 11 0 6 8 0 5 10 5 4 -8 Non-negative Nonmonotone Submodular 4

Where can One Find Submodular Set Functions? In Combinatorial Settings Ground Set Submodular Function Nodes of a graph The number of edges leaving a set of nodes. Collection of sets The number of elements in the union of a sub-collection. In Applicative Settings Utility/cost functions in economics (economy of scale). Influence of a set of users in a social network. 5

12 Maximization Subject to a Cardinality Constraint Instance A non-negative submodular function f : 2N R+ and an integer k. Objective Find a subset S N of size at most k maximizing f(S). Accessing the Function A representation of f can be exponential in the size of the ground set. The algorithm has access to f via an oracle. Value Oracle given a set S returns f(S). Algorithmic Evaluation Criteria Approximation ratio. Oracle queries. Time complexity - ignored in this talk. 6

The (Classical) Greedy Algorithm The Algorithm Do k iterations. In each iteration pick the element with the maximum marginal contribution. More Formally 1. Let S0 . 2. For i = 1 to k do: 3. Let ui be the element maximizing: fui(Si-1). 4. Let Si Si-1 {ui}. 5. Return Sk. 7

12 Results for Monotone Functions Greedy Achieves 1-1/e approximation [Nemhauser et al. 78]. Match a hardness of [Nemhauser et al. 78] O(nk) oracle queries. For other constraints: -approximation for a general matroid constraint. [Nemhauser et al. 78] (k+1)-1-approximation for k-set systems. [Nemhauser et al. 78] (presented formally by [Calinescu et al. 11]). Reducing the Number of Oracle Calls O(nk) oracle queries is very good compared to tight algorithms for more involved constraints. A new result gives 1 1/e approximation using O(n -1log (n / )) oracle queries. [Ashwinkumar and Vondrak 14] The number of oracle queries can be further reduced to O(n log( -1)). 8

12 What About Non-monotone Functions? Approximation Ratio 0.325 approximation via simulated annealing [Oveis Gharan and Vondrak 11] 1/e o(1) approximation (measured continuous greedy) [Feldman et al. 11] 0.491 hardness [Oveis Gharan and Vondrak 11] Oracle Queries Both algorithms require many oracle queries. The greedy algorithm requires few oracle queries, but guarantees no constant approximation ratio. Example: = , , , , 2 1 u u u v N n S v S ( ) S v = = and 2 f S 0 otherwise The greedy algorithm will select v in the first iteration. 9

The Random Greedy Algorithm The Algorithm Do k iterations. In each iteration pick at random one element out of the k with the largest marginal contributions. More Formally 1. Let S0 . 2. For i = 1 to k do: 3. Let Mi be set of k the elements maximizing: fu(Si-1). 4. Let ui be a uniformly random element from Mi. 5. Let Si Si-1 {ui}. 6. Return Sk. 10

Warm Up: Analysis for Monotone Functions In iteration i Fix everything that happened before iteration i. All the expectations will be conditioned on the history. By submodularity and monotonicity: ( ) ( ) 1 1 OPT u ( ) ( ) ( ) E f S E f OPT S E f S f OPT E f S 1 1 u i i i i The elememt ui is picked at random from Mi, and OPT is a potential candidate to be Mi. ( ) k 1 1 = ( ) S ( ) ( ) ( ) E f E f S = E f S E f S E f S 1 i i 1 1 1 u i u i u i k i OPT u M u i ( ) ( ) f OPT E f S = 1 i k Unfix history - if it holds for every given history, it holds in general too. 11

Warm Up: Analysis for Monotone Functions (cont.) Adding up all iterations Rearranging: ( OPT f 1 k ) ( ) S ( ) ( ) 1 E f f OPT E f S 1 i i Combining: f k k 1 1 1 1 ( ) ( ) S ( ) ( ) S ( ) OPT f f OPT f f OPT 0 k k k Rearranging again: k 1 1 1 1 ( ) S ( ) ( ) 1 f f OPT f OPT k k e We get a set with a value of (1 1/e) f(OPT) in expectation (unlike in the classical greedy). 12

Reduction for Non-monotone Functions We add k dummy elements of value 0. The dummy elements are removed at the end. Allows us to assume OPT is of size exactly k. Analysis for Non-monotone Functions Helper Lemma For a submodular function g : 2N R+ and a random set R containing every element with probability at most p: E[g(R)] (1 p) g( ). Similar to a Lemma from [Feige et al. 2007]. Will be proved later. Current Objective Lower bound E[f(OPT Si)]. Method - show that no element belongs to Si with a large probability, and then apply the above lemma. 13

Analysis for Non-monotone Functions (cont.) Observation In every iteration i, every element outside of Si-1 has a probability of at most 1/k to get into Si. Corollary An element belongs to Si with probability at most 1 (1-1/k)i. Applying the Helper Lemma Let g(S) = f(OPT S). Observe that g(S) is non-negative and submodular. E[f(OPT Si)] = E[g(Si)] (1-1/k)i g( ) = (1-1/k)i f(OPT). Next Step Repeat the analysis of the classical greedy algorithm, and use the above bound instead of monotonicity. 14

Analysis for Non-monotone Functions (cont.) In iteration i Fix everything that happened before iteration i. All the expectations will be conditioned on the history. By submodularity: u ( ) ( ) ( ) E f S E f OPT S E f S 1 1 1 u i i i OPT The elememt ui is picked at random from Mi, and OPT is a potential candidate to be Mi. k 1 1 = ( ) S ( ) ( ) ( ) ( ) = E f E f S E f S E f S E f S 1 i i 1 1 1 u i u i u i k i OPT u M u i ( ) ( ) E f OPT S E f S = 1 1 i i k 15

Analysis for Non-monotone Functions (cont.) Unfixing history, and using previous observations, we get: ( ) ( ) i / 1 1 ( ) k f OPT E f S ( ) S ( ) 1 i E f E f S 1 i i k Adding up all iterations We got a lower bound on the (expected) improvement in each iteration. Using induction it is possible to prove that: ( ) ( ) OPT f k k 1 1 k i 1 1 1 k 1 i ( ) S ( ) ( ) 1 E f f OPT e f OPT E f S k i k k Remarks This algorithm both uses less oracle calls than the previous ones, and gets ride of the o(1) in the approximation ratio. Now it all boils down to proving the helper lemma. 16

F1 Proof of the Helper Lemma Helper Lemma - Reminder Given a submodular function g : 2N R+ and a random set R containing every element with probability at most p. Then, E[g(R)] (1 p) g( ). Intuition Adding all the elements can reduce the value of g( ) by at most g( ) to 0. Adding at most a p fraction of every element, should reduce g ( ) by no more than p g( ). Notation Order the elements of N in an order u1, u2, , unof non-increasing probability to belong to R. Let Ni be the set of the first i elements in the above order. Let pi = Pr[ui R]. Let Xi be an indicator for the event ui R. Notice that E[Xi] = pi. 17

F1 Proof of the Helper Lemma (cont.) The value of the set R can be represented using the following telescopic sum: ( ) ( ) = i 1 k ( ) ( ) = + 1 g R g g N R g N R i i Taking an expectation over both sides, we get: ( ) ( ) ( ) + = = N g X E g i 1 k ( ) i E g R g E g N R g N R 1 i i 1 k ( ) ( ) ( ) = + R g N R 1 i i i = k k ( ) ( ) ( ) ( ) ( ) ( ) i i + = + g E X g N g N g p g N g N 1 1 i i i i i i = = 1 1 1 k ) ( ) ( ) ( ( ) ( N ) ( ) i = + + 1 1 p g g N p p p g p g + 1 1 1 i i i n = 1 18

Playing with the Size of Mi Question The size of Mi determines the guarantee we have on E[f(Si OPT)]. The larger Mi - the better the guarantee. Why not increase |Mi| to be larger than k? Answer We know there are k good elements (in average) the elements of OPT. Increasing Mi might introduce into it useless elements. The gain in every single iteration might decrease. 19

And yet The Bad Case Let Mik be the set of the k elements with best marginal values at iteration i. There are no useful elements outside of Mik. Most of OPT s value is contributed by OPT Mik. The best subset of Mik is: Feasible. Has a lot of value. Can be (approximately) found using an algorithm for unconstrained submodular maximization. Taking Advantage Apply the fast algorithm with Mi larger than k. At every iteration, find the best subset of Mik. Output the best set seen. 20

And yet (cont.) By making the size of Mi a function of i, one can get e-1 + for some small constant > 0. Using a few more tricks, one can improve to 0.004. Implications Very small improvement in approximation ratio at the cost of many more oracle queries. The ratio e-1 is not the right ratio for a cardinality constraint. No candidate for the right ratio. e-1 is the state of the art for a general matroid constraint. Is it right for that case? 21

12 Equality Cardinality Constraint New Objective Find a subset S N of size exactly k maximizing f(S). Monotone Functions Not interesting. We can always add arbitrary elements to the output. Non-monotone Functions Best previous approximation: - o(1). Modifications to our algorithm: Apply a reduction that let us assume k n/2. Avoid the reduction described previously. Select only elements of N \ Si-1 into Mi. Achieves: Approximation of: Uses O(nk) oracle queries. The term ok(1) can be replaced with at the cost of a multiplicative constant increase in the number of oracle queries. ( / 1 2 v ) v/2 erfi / 1 1 e 2 v ( ) 1 where v = n/k 1. o ( ) k + 22

Understanding the Approximation Ratio The interesting range is: 1 v (k n/2). erfi is the imaginary error function: ( ) erfi 2 z 2 = ydy z e 0 The approximation ratio as a function of v: 23

Reduction Aim We want to assume k n/2. Observations Equivalent problem - find a subset of size exactly n-k maximizing h(S) = f(N \ S). h(S) is non-negative and submodular if and only if f has these properties. ( ) ( ) ( ) ( A f = ( ) A ( ) ( ) ) + = + + h A h B f f B f A B f A B ) ( ( ) ( ) + = + B f A B h A B h A B Corollary If k > n/2, we can switch to the above equivalent problem. 24

Analysis Intuition A possible candidate for Mi is OPT \ Si padded with random elements of N \ (OPT Si). The padding elements can reduce the value of the solution. However: The expected number of padding elements in iteration i is only: k(1 (1 1/k)i) (and k is small compared to n because of the reduction). Adding all the elements of N \ (OPT Si) reduces the value to 0 (at the worst case). Thus, an average element of N \ (OPT Si) reduces the value by a factor of at most 1 / |N \ (OPT Si)|. OPT \ Si Padding k 25

Other Results Cardinality Constraint For both problems we consider, an approximation ratio of: + 1 n 1 ( ) 2 n k k For k = n/2, both problems have an approximation ratio of . For an equality constraint: 0.356-approximation by balancing this ratio with the one presented before. Fast Algorithms for General Matroid Constraint Approximation Ratio Oracle Queries Time Complexity 1/4 O(nk) O(nk) (1-e2) / 2 > 0.283 O(nk + k3) O(nk + k +1) State of the art approximation ratio for a general matroid constraint: e-1 o(1). 26

Open Problems Cardinality Constraint The approximability depends on k/n. For k/n = 0.5, we have 0.5 approximation. For small k s, one cannot beat 0.491 [Oveis Gharan and Vondrak 11] What is the correct approximation ratio for a given k/n? Fast Algorithms Finding fast algorithms for more involved constraints. Such as a general matroid constraint. Beating e-1 using a fast algorithm: Even for large k/n values. Further reducing the number of oracle quires necessary to get 1-1/e- approximation. No lower bounds on the number of necessary oracle queries. 27

28