The Power of Second Chance: Personalized Submodular Maximization with Two Candidates
Jing Yuan Shaojie Tang




Personalized Submodular Maximization with Two Candidates






Department of Computer Science and Engineering, University of North Texas Department of Management Science and Systems, School of Management, University at Buffalo

The Power of Second Chance: Personalized Submodular Maximization with Two Candidates
    Jing Yuan1 Shaojie Tang2
    
====================================================================================



§ ABSTRACT 
Most of existing studies on submodular maximization focus on selecting a subset of items that maximizes a single submodular function. However, in many real-world scenarios, we might have multiple user-specific functions, each of which models the utility of a particular type of user. In these settings, our goal would be to choose a set of items that performs well across all the user-specific functions. One way to tackle this problem is to select a single subset that maximizes the sum of all of the user-specific functions. Although this aggregate approach is efficient in the sense that it avoids computation of sets for individual functions, it really misses the power of personalization - for it does not allow to choose different sets for different functions. In this paper, we introduce the problem of personalized submodular maximization with two candidate solutions. For any two candidate solutions, the utility of each user-specific function is defined as the better of these two candidates. Our objective is, therefore, to select the best set of two candidates that maximize the sum of utilities of all the user-specific functions. We have designed effective algorithms for this problem. We also discuss how our approach generalizes to multiple candidate solutions, increasing flexibility and personalization in our solution.






§ INTRODUCTION

A submodular function is defined by its intuitive diminishing returns property: adding an item to a smaller set will increase the return more in comparison with when this happens from a larger set. Such a function is extremely common in various combinatorial optimization problems naturally arising from machine learning, graph theory, economics, and game theory.  Most of the work in submodular optimization focuses on selecting a subset of items from a ground set  that maximizes a single submodular function. However, in many real-world scenarios, we are confronted with multiple user-specific functions denoted as f_1, ⋯, f_m : 2^Ω→ℝ_≥ 0. Each of these functions, such as f_i, captures the utility corresponding to some user type indexed by i. Our main goal will be to maximize the aggregate utility of all the m functions. One trivial way to achieve this would be to compute a solution individually for every single function f_i. Unfortunately, this would require to compute and store m solutions, which is infeasible or at least very inefficient if the number of user-specific functions is large.
Another way is to look for a single feasible solution, denoted as S⊆Ω, that maximizes the summation of these m functions, i.e., max_S⊆Ω∑_i∈[m] f_i(S). This problem, also known as the maximization of decomposable submodular functions <cit.>, has been well-studied in the literature and efficient algorithms have been designed for the same. Nevertheless, such an aggregate approach, despite being efficient, is unable to harness the power of personalization.  Specifically, it does not provide the flexibility in offering a personalized set for each function.

In our research, we introduce the innovative concept of personalized submodular maximization. Consider a pair of sets {S_1, S_2}, for each user-specific function f_i, we determine its utility based on the better-performing solution among these two candidates, represented as max{f_i(S_1), f_i(S_2)}. Mathematically, our problem can be expressed as follows:

    max_S_1, S_2 ⊆Ω∑_i∈[m]max{f_i(S_1), f_i(S_2)}
           |S_1|≤ k, |S_2|≤ k,

where k is the size constraint of a feasible solution.
In essence, our primary objective is to maximize the combined utility of user-specific functions while maintaining a personalized approach to item selection. An important and practical application of our study is in the context of two-stage optimization. Here, we consider that f_1, ⋯, f_m represent training examples of functions drawn from an unknown distribution, we aim to choose a pair of candidate solutions based on these m functions, ensuring that  one of the chosen candidates performs well when faced with a new function from the same distribution.


In this paper, we also discuss the possibility of expanding our approach  to accommodate multiple (more than two) candidate solutions. This potential extension would further enhance the flexibility and personalization options within our solution.



 §.§ Related Work
 The problem of submodular maximization has received considerable attention in the literature <cit.>. For example, one of the most well-established results is that a simple greedy algorithm achieves a tight approximation ratio of (1-1/e) for maximizing a single monotone submodular function subject to cardinality constraints <cit.>. Since most datasets are so big nowadays, several works were devoted to reducing the running time to maximize a submodular function. Examples include the development of accelerated greedy algorithms  <cit.> and streaming algorithms <cit.>. All of these works, however, focus on finding a single set that maximizes a submodular function. In contrast, our goal is to identify a pair of candidates that maximizes the sum of the better-performing solution between them. This presents a unique challenge, as the resulting objective function is no longer submodular. Consequently, existing results on submodular optimization cannot be directly applied to our study.

Our work is closely related to the field of two-stage submodular optimization <cit.>, in which the key objective is to find a smaller ground set from a large one. This reduction should be designed in such a way that choosing the items from the small set guarantees approximately the same performance as choosing items from the original large set for a variety of submodular functions. This aligns with our objective of seeking two initial solutions that cut down on computational effort in optimization with a new function. However, problem formulations between our studies are largely different despite sharing the same objective. Thereby, new methodologies should be developed to cope with the distinctive challenges presented in our research. Moreover, note that in the traditional framework of two-stage submodular optimization, once a reduced ground set is computed, further optimization based on this reduced set usually involves algorithms with possibly high time complexity, such as the greedy algorithm. In contrast, our personalized optimization model requires only a comparison between the performance of two candidate solutions, significantly reducing the computational burden in the second stage.


§ PROBLEM FORMULATION

Our problem involves an input set of n items denoted as Ω, and a collection of m submodular functions, namely, f_1, ⋯, f_m : 2^Ω→ℝ_≥ 0. To clarify, the notation Δ_i(x, A) denotes the marginal gain of adding item x to set A with respect to the function f_i. That is, Δ_i(x, A)=f_i({x}∪ A) - f_i(A). Specifically, a function f_i is considered submodular if and only if Δ_i(x, A) ≥Δ_i(x, A') holds for any two sets A and A' where A⊆ A'⊆Ω and for any item x∈Ω such that x∉ A'.


Our aim is to select a pair of candidate solutions, S_1 and S_2, and the utility of each user-specific function is determined by the superior solution among these two candidates.  These subsets should provide good performance across all m functions when we are limited to choosing solutions from either S_1 or S_2. Formally,

 

[0.7][c]
[t]0.7
P.0
max_S_1, S_2 ⊆Ω∑_i∈[m]max{f_i(S_1), f_i(S_2)}

|S_1|≤ k, |S_2|≤ k,






where k is the size constraint of a feasible solution.


A straightforward approach to solving P.0 is to transform it into a standard set selection problem. Specifically, we can introduce a ground set 𝒰 = {(i,j)| i∈Ω, j∈{1, 2}}. Here, selecting an element (i,j)∈𝒰 corresponds to placing item i in set S_j in our original problem. Let x_ij be a binary decision variable representing the selection of (i,j), such that x_ij=1 if and only if (i,j) is selected. Then P.0 is reduced to finding a set of elements from 𝒰 such that ∀ i∈Ω, x_i1+x_i2=1 and ∀ j∈{1, 2}, ∑_i∈Ωx_ij≤ k, which represents the intersection of two matroid constraints. Unfortunately, it is straightforward to verify that the utility function defined over 𝒰 is not necessarily submodular, even if each individual function f_i is submodular. Hence, existing solutions for submodular maximization subject to two matroid constraints are not directly applicable to our problem.






§ ALGORITHM DESIGN FOR CONSTANT M


We first study the case if the number of functions m is a constant. Before presenting our algorithm, we introduce a new optimization problem P.1. The objective of this problem is to partition the m functions  into two groups such that the sum of the optimal solutions for these two groups is maximized. Formally,

 

[0.7][c]
[t]0.7
P.1

    max_A, B⊆ [m]      (max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) + max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S))

subject to B = [m]∖ A.







We next show that the optimal solution of P.1 serves as an upper bound for our original problem.


Let OPT_1 (resp. OPT_0) denote the value of the optimal solution of P.1 (resp. our original problem P.0), we have

    OPT_1≥ OPT_0.


Proof: Assume S_1^* and S_2^* is the optimal solution of P.0, we can partition m functions to two groups A' and B' such that every function in A' favors S_1^* and  every function in B' favors S_2^*. That is,

    A'={i∈ [m]| f_i(S_1^*) ≥ f_i(S_2^*)}
 and 
    B'={i∈ [m]| f_i(S_1^*) < f_i(S_2^*)}.
 Hence,

    OPT_0= ∑_i∈[m]max{f_i(S_1^*), f_i(S_2^*)}
          = ∑_i∈ A'max{f_i(S_1^*), f_i(S_2^*)} + ∑_i∈ B'max{f_i(S_1^*), f_i(S_2^*)}
          = ∑_i∈ A'  f_i(S_1^*) + ∑_i∈ B'  f_i(S_2^*)

where the first inequality is by the definition of OPT_0, the second equality is by the observation that A' and B' is a partition of [m] and the third equality is by the definitions of A' and B'.

Moreover, it is easy to verify that

    max_S⊆Ω: |S|≤ k∑_i∈ A' f_i(S) + max_S⊆Ω: |S|≤ k∑_i∈ B' f_i(S) 
          ≥∑_i∈ A' f_i(S_1^*) + ∑_i∈ B' f_i(S_2^*).
 This is because |S_1^*|≤ k and |S_2^*|≤ k. It follows that

    OPT_0= ∑_i∈ A'  f_i(S_1^*) + ∑_i∈ B'  f_i(S_2^*) 
          ≤max_S⊆Ω: |S|≤ k∑_i∈ A' f_i(S) + max_S⊆Ω: |S|≤ k∑_i∈ B' f_i(S).


Therefore,

    OPT_1 = 
          max_A, B⊆ [m](max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) + max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S)) 
          ≥max_S⊆Ω: |S|≤ k∑_i∈ A' f_i(S) + max_S⊆Ω: |S|≤ k∑_i∈ B' f_i(S)
          ≥∑_i∈ A'  f_i(S_1^*) + ∑_i∈ B'  f_i(S_2^*) = OPT_0.
 This finishes the proof of this lemma. 

Now, we present our algorithm, called , which is listed in Algorithm <ref>. Our approach involves enumerating all possible partitions of [m]. For each partition, denoted as A and B, we utilize a state-of-the-art algorithm to solve two subproblems: 
    max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S)
 and 
    max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S).
 This results in obtaining two sets, C_1 and C_2, respectively. Finally, we return the best pair of sets as the solution for our original problem P.0.

Since the number of functions m is a constant, the maximum number of possible partitions we must enumerate is at most O(2^m), which is also a constant. As long as max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) and max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S) can be solved in polynomial time, the  is a polynomial time algorithm.  Next we provide an approximation ratio of  Algorithm <ref>.






Assuming the existence of α-approximation algorithms for 
    max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S)
 for any A ⊆ [m], our  (Algorithm <ref>) provides an α-approximation solution for P.0.

Proof: Assuming that A^* and B^* represent the optimal solution for P.1, let us consider the round of our algorithm where it enumerates the partition of A^* and B^*. In this round, we denote the solutions obtained as C_1 and C_2. Given that there exist α-approximation algorithms  for max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) for any A ⊆ [m], by adopting this algorithm as a subroutine, we have 
    ∑_i∈ A^* f_i(C_1) ≥αmax_S⊆Ω: |S|≤ k∑_i∈ A^* f_i(S)
 and 
    ∑_i∈ B^* f_i(C_2)≥αmax_S⊆Ω: |S|≤ k∑_i∈ B^* f_i(S).
 Hence,

    ∑_i∈[m]max{f_i(C_1), f_i(C_2)}≥∑_i∈ A^* f_i(C_1)  + ∑_i∈ B^* f_i(C_2)
          ≥α(max_S⊆Ω: |S|≤ k∑_i∈ A^* f_i(S) +  max_S⊆Ω: |S|≤ k∑_i∈ B^* f_i(S))
          =  α OPT_1

where the equality is by the assumption that A^* and B^* represent the optimal solution for P.1.

This, together with Lemma <ref>, implies that

    ∑_i∈[m]max{f_i(C_1), f_i(C_2)}≥α OPT_1≥α OPT_0.


This lemma is a consequence of the above inequality and the fact that the final solution obtained by our algorithm is at least as good as ∑_i∈[m]max{f_i(C_1), f_i(C_2)}. 

Observe that if all f_i are monotone and submodular functions, then there exists (1-1/e)-approximation algorithms for max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) for any A ⊆ [m]. Therefore, by substituting α=1-1/e into Lemma <ref>, we obtain the following theorem.


Assume all  f_i are monotone and submodular functions,  (Algorithm <ref>) provides an (1-1/e)-approximation solution for P.0.





§ ALGORITHM DESIGN FOR LARGE M


When dealing with a large value of m, relying on an enumeration-based approach can become impractical. In this section, we introduce a , outlined in Algorithm <ref>, that provides provable performance bounds. Instead of exhaustively enumerating all possible partitions of [m], we examine T random partitions. For each partition, we follow the same procedure as in Algorithm <ref> to compute two candidate solutions. Specifically, for each sampled partition, we employ a state-of-the-art α-approximation algorithm to solve two subproblems. Ultimately, we return the best pair of sets as the final solution.



In the following two lemmas, we provide two performance bounds for Algorithm <ref>. The first bound is independent of the number of samples T; thus, it holds even if T=1. The second bound depends on T, increasing as T increases.


Assuming the existence of α-approximation algorithms for 
    max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S)
 for any A ⊆ [m], our  (Algorithm <ref>) provides an α/2-approximation solution for P.0.

Proof: We first recall some notations form the proof of Lemma <ref>. Assume S_1^* and S_2^* is the optimal solution of P.0, we partition all m functions  to two groups A' and B' such that every function in A' favors S_1^* and  every function in B' favors S_2^*. That is, 
    A'={i∈ [m]| f_i(S_1^*) ≥ f_i(S_2^*)}
 and 
    B'={i∈ [m]| f_i(S_1^*) < f_i(S_2^*)}.
 Without loss of generality, we assume that ∑_i∈ A' f_i(S_1^*)≥∑_i∈ B' f_i(S_2^*), implying that ∑_i∈ A' f_i(S_1^*)≥ OPT_0/2. Now, let us consider any arbitrary partition sample denoted as A and B, generated by our algorithm, we have

    max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) +  max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S) 
          ≥∑_i∈ A f_i(S_1^*) + ∑_i∈ B f_i(S_1^*) ≥∑_i∈ A' f_i(S_1^*) ≥ OPT_0/2

where the first inequality is by the observation that |S_1^*|≤ k, the second inequality is by the observation that A' ⊆ A∪ B and the third inequality is by the observation that ∑_i∈ A' f_i(S_1^*)≥ OPT_0/2. Because there exist α-approximation algorithms  for max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) for any A ⊆ [m], by adopting this algorithm as a subroutine to compute C_1 and C_2, we have

    ∑_i∈ A f_i(C_1) ≥αmax_S⊆Ω: |S|≤ k∑_i∈ A f_i(S)
 and 
    ∑_i∈ B f_i(C_2)≥αmax_S⊆Ω: |S|≤ k∑_i∈ B f_i(S).
  Hence,

    ∑_i∈[m]max{f_i(C_1), f_i(C_2)}≥∑_i∈ A f_i(C_1)  + ∑_i∈ B f_i(C_2)
          ≥α(max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) +  max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S))≥  (α/2) OPT_0

where the third inequality is by inequality (<ref>). This finishes the proof of this lemma. 



Assuming the existence of α-approximation algorithms for 
    max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S)
 for any A ⊆ [m], our  (Algorithm <ref>), after T rounds, provides an αγ(T)  (1/2 + ϵ/√(m))-approximation solution for P.0 in expectation where γ(T)=1-(1/2+ϵe/π)^T.

Proof: Consider an arbitrary round of our algorithm, and let A and B denote the sampled partition, and let (C_1, C_2) denote the solution returned from this round. Observe that

    ∑_i∈[m]max{f_i(C_1), f_i(C_2)}≥∑_i∈ A f_i(C_1)  + ∑_i∈ B f_i(C_2).


Hence, the expected value of ∑_i∈[m]max{f_i(C_1), f_i(C_2)}, where the expectation is taken over A, B, is at least 𝔼_A, B[∑_i∈ A f_i(C_1) + ∑_i∈ B f_i(C_2)]. Recall that our algorithm runs T rounds and returns the best (C_1,C_2) as the final solution, to prove this lemma, it suffices to show that the expected value of ∑_i∈[m]max{f_i(C_1), f_i(C_2)} is at least αγ(T)  (1/2 + ϵ/√(m))OPT_0. To achieve this, we will focus on proving
𝔼_A, B[∑_i∈ A f_i(C_1) + ∑_i∈ B f_i(C_2)]≥αγ(T)  (1/2 + ϵ/√(m))OPT_0. The rest of the proof is devoted to proving this inequality.

First,

    𝔼_A, B[∑_i∈ A f_i(C_1) + ∑_i∈ B f_i(C_2)] 
          ≥𝔼_A, B[αmax_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) +  αmax_S⊆Ω: |S|≤ k∑_i∈ B f_i(S)] 
          = α𝔼_A, B[max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) +  max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S)] 
          =α𝔼_A[max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S)] + α𝔼_B[max_S⊆Ω: |S|≤ k∑_i∈ B f_i(S)] 
          ≥α𝔼_A[ ∑_i∈ A f_i(S_1^*)] + α𝔼_B[∑_i∈ B f_i(S_2^*)].


Next, we provide lower bounds for 𝔼_A[ ∑_i∈ A f_i(S_1^*)] and 𝔼_B[∑_i∈ B f_i(S_2^*)]. Recall that we defined A'={i∈ [m]| f_i(S_1^*) ≥ f_i(S_2^*)} and B'={i∈ [m]| f_i(S_1^*) < f_i(S_2^*)}. Now, for some β∈[0,1], let us denote the event as E, which occurs when the following condition holds for at least one partition (A, B) that is enumerated by our algorithm: |A∩ A'|/|A'|≥β. Because each item of A' is included in A independently with a probability of 1/2, for any β∈[0,1], we have the following:

    𝔼_A[ ∑_i∈ A f_i(S_1^*)] ≥[1_E=1]·β∑_i∈ A' f_i(S_1^*).







Consider a random sample A from [m] and observe that each item of A' is included in A independently with a probability of 1/2, by an “anti-concentration” result on binomial distributions (Lemma 22.2 in <cit.>), we have

    [|A∩ A'| ≥|A'|/2+ϵ√(|A'|)] ≥1/2 - ϵe/π.




This implies that

    [|A∩ A'|/|A'|≥1/2 + ϵ/√(|A'|)] ≥1/2 - ϵe/π.

Given that |A'| ≤ m, we further have

    [|A∩ A'|/|A'|≥1/2 + ϵ/√(m)] ≥1/2 - ϵe/π.


If we set β=1/2 + ϵ/√(m), then we can establish a lower bound on the probability of event E occurring after T rounds as follows:

    [1_E=1] ≥ 1-(1-[|A∩ A'|/|A'|≥1/2 + ϵ/√(m)])^T 
          ≥ 1-(1/2+ϵe/π)^T.





This, together with inequalities (<ref>), implies that

    𝔼_A[ ∑_i∈ A f_i(S_1^*)] ≥[1_E=1]·β∑_i∈ A' f_i(S_1^*)
    ≥ (1-(1/2+ϵe/π)^T) · (1/2 + ϵ/√(m))  ∑_i∈ A' f_i(S_1^*).


Following the same argument, we can prove that

    𝔼_B[ ∑_i∈ B f_i(S_2^*)]≥  (1-(1/2+ϵe/π)^T) · (1/2 + ϵ/√(m))  ∑_i∈ B' f_i(S_2^*).


Let γ(T)=1-(1/2+ϵe/π)^T. The above two inequalities, together with inequality (<ref>), imply that

    𝔼_A, B[∑_i∈ A f_i(C_1) + ∑_i∈ B f_i(C_2)]≥α𝔼_A[ ∑_i∈ A f_i(S_1^*)] + α𝔼_B[∑_i∈ B f_i(S_2^*)]
          ≥αγ(T) (1/2 + ϵ/√(m))  ∑_i∈ A' f_i(S_1^*) + αγ(T) (1/2 + ϵ/√(m))  ∑_i∈ B' f_i(S_2^*)
          = αγ(T)  (1/2 + ϵ/√(m))( ∑_i∈ A' f_i(S_1^*)+∑_i∈ B' f_i(S_2^*))
          =   αγ(T)  (1/2 + ϵ/√(m)) OPT_0.
 This finishes the proof of this lemma. 

By selecting a tighter bound derived from Lemma <ref> and Lemma <ref>, we can establish the following corollary.



Assuming the existence of α-approximation algorithms for 
    max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S)
 for any A ⊆ [m], our Sampling-based algorithm (Algorithm <ref>), after T rounds, provides an max{1/2,  γ(T)  (1/2 + ϵ/√(m))}·α-approximation solution for P.0 in expectation where γ(T)=1-(1/2+ϵe/π)^T.


Observe that if all f_i are monotone and submodular functions, then there exists (1-1/e)-approximation algorithms for max_S⊆Ω: |S|≤ k∑_i∈ A f_i(S) for any A ⊆ [m]. Therefore, substituting α=1-1/e into Corollary <ref>, we derive the following theorem.


Assume all  f_i are monotone and submodular functions, Sampling-based algorithm (Algorithm <ref>), after T rounds, provides an max{1/2,  γ(T)  (1/2 + ϵ/√(m))}·(1-1/e)-approximation solution for P.0 in expectation where γ(T)=1-(1/2+ϵe/π)^T.

































  
Discussion on Scenarios with More than Two Candidates
We next discuss the case if we allowed to keep  l≥ 2 candidate solutions. In this extension, our aim is to select l candidate solutions, S_1, ⋯, S_l, and the utility of each user-specific function is determined by the superior solution among these  candidates. Hence, our problem can be formulated as max_S_1, ⋯, S_l ⊆Ω∑_i∈[m]max{f_i(S_1), ⋯, f_i(S_l)} subject to  |S_1|≤ k, ⋯, |S_l|≤ k
where k is the size constraint of a feasible solution. To tackle this challenge, we can utilize our enumeration-based partition algorithm (Algorithm <ref>) to find an approximate solution. The procedure involves enumerating all possible ways to partition the set [m] into l groups. For each partition, we employ a state-of-the-art (1-1/e)-approximation algorithm to solve the maximization problem within each group. This process generates l sets, and we then choose the best l sets among all partitions as the final solution. By following the same argument used to prove Theorem <ref>, we can show that this approach guarantees an (1-1/e)-approximation solution.





splncs04



