Dynamic Non-monotone Submodular Maximization
Authors: Kiarash Banihashem
Leyla Biabani
Samira Goudarzi
MohammadTaghi Hajiaghayi
Peyman Jabbarzade
Morteza Monemizadeh
Venue: NeurIPS 2023 poster (2023)
Keywords: Non-monotone submodular maximization
dynamic algorithm
oracle query
video summarization

Abstract: Maximizing submodular functions has been increasingly used in many applications of machine learning, such as data summarization, recommendation systems, and feature selection. Moreover, there has been a growing interest in both submodular maximization and dynamic algorithms. 
In 2020, Monemizadeh and 
Lattanzi, Mitrovic, Norouzi-Fard, Tarnawski, and Zadimoghaddam initiated developing dynamic algorithms for the monotone submodular maximization problem under the cardinality constraint $k$. 
In 2022, Chen and Peng studied the complexity of this problem and raised an important open question: "\emph{Can we extend [fully dynamic] results (algorithm or hardness) to non-monotone submodular maximization?}". 
We affirmatively answer their question by demonstrating a reduction from maximizing a non-monotone submodular function under the cardinality constraint $k$ to maximizing a monotone submodular function under the same constraint. 
Through this reduction, we obtain the first dynamic algorithms to solve the non-monotone submodular maximization problem under the cardinality constraint $k$. Our algorithms maintain an $(8+\epsilon)$-approximate of the solution and use expected amortized $O(\epsilon^{-3}k^3\log^3(n)\log(k))$ or $O(\epsilon^{-1}k^2\log^3(k))$ oracle queries per update, respectively. 
Furthermore, we showcase the benefits of our dynamic algorithm for video summarization and max-cut problems on several real-world data sets.

Dynamic Non-monotone Submodular Maximization
Kiarash Banihashem" kiarash@umd. edu University of Maryland
Leyla Biabani" bi bbiabani@tun Seaai@tue... TU Eindhoven
Samira Goudarzi" samiragSumd edu University of Maryland
Mohammad Hajiaghayi" hajiagha@cs umd. edu University of Maryland
Peyman Jabbarzade" peymanj @umdd. edu University of Maryland
Morteza Monemizadeh" m. mww.mmiiadeee@uuee...... nl TU Eindhoven
Abstract
Maximizing submodular functions has been increasingly used in many applications machine learning, such as data summarization, recommendation systems, and feature selection. Morcover, there has been growing interest in both submodular maximization and dynamic algorithms. In 2020, Monemizadeh [46] and Lattanzi, Mitrovic, Norouzi-Fard, Tamaaski,, and Zadimoghaddam [40] initiated developing dynamic algorithms for the monotone submodular maximization problem under the cardinality constraint k. In 2022, Chen and Peng [15] studied the complexity of this problem and raised an important open question: "Can we extend [fully dynamic| results (algorithm or hardness) non-montoone submodular maximization ?". We affirmatively answer their question by demonstrating reduction from maximizing non-monotone submodular function under the cardinality constraint maxi- mizing monotone submodular function under the same constraint. Through this reduction, we obtain the first dynamic algorithms solving the non-monotone sub- modular maximization problem under the cardinality constraint k. We've derived two algorithms, both maintaining
(8 + <)-approximate of the solution. The first algorithm requires ( 333 log" (n) log(k)) oracle queries per update, while the second one requires Occ-1 (k:).. Furthermore, we showease the benefits of our dynamic algorithm for video summarization and max-cut problems several real-world data sets.
Introduction
Submodular functions are powerful tools for solving real-world problems as they provide a theoretical framework for modeling the famous "diminishing returns" [30] phenomenon arising in variety of practical settings. Many theoretical problems such as those involving graph cuts, entropy-based clustering, coverage functions, and mutual information can be cast in the submodular maximization framework. As result, submodular functions have been increasingly used in many applications of machine learning such data summarization [52 50), feature selection
[7 19
38] and
recommendation systems [24]. These applications include both the monotone and non-monotone versions of the maximization of submodular functions.
Applications of non-monotone submodular maximization. The general problem of non- This
monotone submodular maximization has been studied extensively 27 2
equul contribution
Department of Computer Science, University of Maryland, College Park, MD, USA.
DDpaartment of Mathematics and Computer Science, Eindhoven University of Technology, the Netherlands.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

problem has numerous applications in video summarization, movie recommendation [43, and rev- enue maximization in viral marketing B3 An important upplication of this problem appears in maximizing the difference between monotone submodular function and a linear function that penalizes the addition of more elements to the set (e.g., the coverage and diversity trade-off). An illustrative example of this application is the maximum facility location in which we want to open a subset of facilities and maximize the total profit from served clients plus the cost of facilities we did not open (21). Another important application occurs when expressing learning problems such as feature selection using weakly submodular functions 17
Our contribution. In this paper, we consider the non monooootone submodular maximization problem under cardinality constraint & in the fully dynamic setting. In this model, we have universal ground ser V. At any time f. ground set V2 S V is the set of elements that are inserted but not deleted after their last insertion till time t. More formally, we assume that there a sequence of "updates" such that each update either inserts an element to Vi-1 or deletes an element from V to form Vi-
We assume that there is (non- mon-monntone) submodular function f that is defined over the universal ground set V. Our goal is to maintain, at each point in time, a set of size at most & whose submodular value is maximum among any subset of V, of size most k.
Since calculating such a set is known to be NP-hard [27 even in the offline setting (where you get all the items at the same time), we focus providing algorithms with provable approximation guarantees, while maintaining fast update time. This is challenging as clements may be inserted or deleted, possibly in an adversarial order. While several dynamic algorithms exist for monotone submodular maximization, non-monotone submodular maximization is a considerably more challenging problem as adding elements to set may decrease its value.
In STOC 2022, Chen and Peng [55 raised the following open question:
Open problem: "Can we extend [fully dynamic] results (algorithm or hardness) to non-monotone submodular maximization?"
In this paper, we answer their question affirmatively by providing the first dynamic algorithms for non-monotone submodular maximization.
To emphasize the significance of our result, should be considered that although monotone submod- ular maximization under cardinality constraint has tight e-1 approximation algorithm in the offline mode and nearly tight (2 + e) approximation algorithms for both streaming and dynamic settings, there is hardness result for the non-monotone version stating that impossible obtaín a 2.04 (i.e., 0.491) approximation algorithm for this problem even in the offline setting[31], and to the best of our knowledge, the current state of the art algorithms for this problem have 2.6 and 3.6 (i.e., 0.385 and 0.2779) approximation guarantees for offline 10 and streaming settings (2). respectively.
We obtain our result, by proposing general reduction from the problem of dynamically maintaining a non-monotone submodular function under cardinality constraint k to developing a dynamic thresh- olding algorithm for maximizing monotone submodular functions under the same constraint. We first define 7-thresholding dynamic algorithms that we use in our reduction.
Definition 1.1 (r-Thresholding Dynamic Algorithm). Let 7 > 0 be a parameter. We say dynamic algorithm is r-thresholding if at any time of sequence E, it reports a set St S V of size at most such that
Property 1: either a) St has k elements and f(S.) 2 KT, or b) S, has less than l elements and for any e E V4 \ Se, the marginal gain ((v)S:) <
Property 2: The number of elements changed in any update, i.e |S.41 \SS] + [S, (S4r1. is not more than the number of queries made by the algorithm during the update.
In the above definition, the first property reflects the main intuition of threshold-based algorithms, while the last property is a technical condition required in our analysis. It's worth noting that the thresholding technique has been used widely for optimizing submodular functions [46] 41 26 40 16) We next state our main result, which is a general reduction.
"The problem of selecting subset of people in social network to maximize their influence in a viral marketing campaign can be modeled as a constrained submodular maximization problem. When we introduce cost, then the influence minus the cost is modeled monotone submodular maximization problems 9 g 34

---

Theorem 1.2 (Reduction Metatheorem). Suppose that f - R2u is (possibly non-monotone) submodular function defined on subsets of a ground set V and let ls E N be a parameter.
Assume that for any given value of т, there exists a T-thresholding dynamic algorithm with an expected (amortized) O(g(n,)) oracle queries per update. Then, there exist the following dynamic algorithms:
A dynamic algorithm with approximation guarantee of (8 + E) using an expected (amor- tized) O + min(k: g(n, k)) g(n, k)- (og(k))) oracle queries per update.
A dynamic algorithm maintaining a (10 + -a-ppoxxmmmaee solution of the optimal value of f using an expected (amortized) O (k, g(n, k)) g(n, k) log(k)) oracle calls per update.
In [46. Monemizadeh developed a dynamic algorithm for monotone submodular maximization under cardinality constraint k; which requires an amortized (5=222 (n)) number of oracle queries per update. Interestingly, in the appendix, we show that this algorithm is indeed r-thresholding (for any given r). Now, if we use this r-thresholding dynamic algorithm inside our reduction Metatheorem 1.2 obtain dynamic algorithm that maintains a (8 + 5) appproximate solution using an expected amortized ( 5 log"(r) log(A:)) oracle queries per update.
The recent paper 66 of Banihashem, Biabani, Goudarzi, Hajiaghayi. Jabbarzade, and Monemizadeh develops new dynamic algorithm for monotone submodular maximization under cardinality con- straint k, which uses an expected O(=-1k k log (k)) number of oracle queries per update. A similar proof shows that this new algorithm is 7-thresholding as well. We have provided its pseudocode and a detailed explanation on why this algorithm is indeed 7-thresholding in the appendix. By exploiting this algorithm in our Reduction Metatheorem mentioned to an expected number of (( 22² log (k)) per update.
1.2 we can reduce the number of oracle queries (l)()())))))
The second result in Theorem i.2 is also of interest as it can be used to devise a dynamic algorithm for non-monotone submodular maximization with polylogarithmic query complexity if one can provide a r-thresholding dynamic algorithm for maximizing monotone submodular functions (under the cardinality constraint k) with polylogarithmic query complexity.
1.1 Preliminaries
Submodular maximization. Let V be ground set of elements. We say function f 2 + Rzo is a submodular function if for any A, B C V. f(A) + f(B) 2 f(AUB) + f(An B). Equivalently. is a submodular function if for any subsets A A C B C V and for any element e E V V\B, B, holds that ( {e}) - f(A) 2 ((B -
f(B) We define A(e[A) : f(A
f(A) A) the marginal
gain of adding the element e to set A. Similarly, we define A(B(A) == B) f(A) for any sets A, B C V. Function f is monotone if f(A) < f(B) holds for any A S B S V. and it is non- monotone if it is not necessarily the case. In the submodular maximization problem under cardinality constraint k, we seek to compute set S such that |S < k and f(S*) max si J(S), where a submodular function and E a given parameter.
we assume the access to submodular function f is given by an oracle. The oracle allows set queries such that for every subset A C V, one can query the value f(A). In this query access model, the marginal gain A ( A) = fAA (e]) - (A) for every subset C V and an element e E V,,A, can be computed using two set queries. To do so, we first query f(A U {e}) and then f(A).
Query access model. Similar to recent dynamic works 40 15],
Dynamic model. Let E be a sequence of inserts and deletes of underlying universe V. We assume that f 2V - R2za is a (possibly non-monotone) submodular function defined on subsets of the universe V. We define time f to be the th update (i.e., insertion or deletion) of sequence E. We let E, be the sub-sequence of updates from the beginning of sequence E till time and denote by V. S V the set elements that are inserted but not deleted from the beginning of the sequence E till any time That is, V, is the current ground set of elements. We let OPT, max J(S).
Query complexity. The query complexity of a dynamic a-approximate algorithm the number of oracle queries that the algorithm must make compute solution S; with respect to ground set V.
3

---

whose submodular value is an a-approximation of OPT, That is, |St] S k and f(S) 2 a OPT. Observe that the dynamic algorithm remembers every query has made so far. Thus results of queries made in previous times may help find St in current time l.
Oblivious adversarial model. The dynamic algorithms that we develop in this paper are in the oblivious adversarial model as common for analysis of randomized data structures such as universal hashing [13]. The model allows the adversary, who is aware of the submodular function f and the algorithm that is going to be used, to determine all the arrivals and departures of the elements in the ground set V. However, the adversary is unaware of the random bits used in the algorithm and so cannot choose updates adaptively in response to the randomly guided choices of the algorithm. Equivalently, we can suppose that the adversary prepares the full input (insertions and deletions) before the algorithm runs.
1.2 Related Work
Offline algorithms. The offline version of non-monotone submodular maximization was first studied by Feige, Mirrokni, and Vondrák in [27]. They studied unconstrained non-monotone sub- modular maximization and developed constant-factor approximation algorithms for this problem. In the offline query access model, they showed that a subset S chosen uniformly at random has submodular value which a 4-approximation of the optimal value for this problem. In addition, they also described two local search algorithms. The first uses I as the objective function, and provides 3- 3-approximation and the second uses a noisy version of f as the objective function and achieves an improved approximation guarantee 2.5 for maximizing unconstrained non- oonmonotone non-negative submodular functions. Interestingly, they showed (2 - E) apprrooximtoo for symmetric submodular functions would require exponential number of queries for any fixed
0.
Oveis Gharan and Vondrák [32] showed that an extension of the ap-approximation algorithm can be seen as simulated annealing method which provides an improved approximation of roughly 2.4. Later, Buchbinder, Feldman, Naor, and Schwartz [1] at FOCS' 12, presented a randomized linear time algorithm achieving tight approximation guarantee of 2 that matches the known hardness result of [27]. Bateni, Hajiaghayi, and Zadimoghaddam p| S and Gupta, Roth, Schoeneheck, and Talwar [34] independently studied non-monotone submodular maximization subject to cardinality constraint & in the offline and secretary settings. In particular, Gupta et al. (34] obtained an offline 6.5-approximation for this problem.
All of the aforementioned approximation algorithms are offline, where the whole input is given in the beginning, whereas the need for real-time analysis of rapidly changing data streams motivates the study of this problem in settings such as the dynamic model that we study this paper.
Streaming algorithms. The dynamic model that we study in this paper is closely related to the streaming model 36). However, the difference between these two models is that in the streaming model, we maintain data structure using which we compute solution at the end of the stream and so, the time to extract the solution is not important as we do it once. However, in the dynamic model, we need maintain a solution after every update, thus, the update time of dynamic algorithm should be as fast as possible.
The known streaming algorithms do not support deletions as well as insertions. Indeed, there are streaming algorithms [37 455 for the monotone submodular maximization problem that support deletions, but the space and the update time of these algorithms depend on the number of deletions which could be 2(n)) where n = [V] is the size of ground set V.
44
28
29
work in the insertion-only streaming model and they
For monotone submodular maximization, Badanidiyuru, Mirzasoleimaan Karbasi, and Krause [4] proposed an insertion-onle streaming algorithm with a (2 + ( apprrxximationnn guarantec under a cardi-
nality constraint k. Chekuri, Gupta, and Quanrud [1] presented (insertion-only) streaming algorithms for maximizing monotone and non-monotone submodular functions subject p-matchoid constrainf
Later, Mirzasoleiman, Jegelka, and Krause 44 and Feldman, Karbasi, and Kazemi 28 devel-
For non-monotome monotone submodular maximization subject to cardinality constraint kt Chekuri, Gupta, and Quanrud [14] claimed that they obtained 4. appproxximttion algorithm. However, Alaluf, Ene, Feldman, Nguyen, and Suh M found error in the proof of this approximation guarantee.

---

oped streaming algorithms with better approximation guarantees for maximizing a monoonot function under p-matchoid constraint. Currently, the best streaming algorithm for maximizing a non-monotone submodular function subject to cardinality constraint is due to Alaluf, Ene, Feldman, Nguyen, and Suh [ whose approximation guarantee is 3.6 + e, improving the 5.8-approximation guarantee that was proposed by Feldman et al. [28].
Dynamic algorithms. At NeurIPS 2020, Lattanzi, Mitrovic. Norouzi-Fard Tarnawski, and Zadi- moghaddam [40] and Monemizadeh [46] initiated the study of submodular maximization in the dynamic model. They presented dynamic algorithms that maintain (2 + a)-aproxima solutions for maximizing a monotone submodular function subject to cardinality constraint k. Later, at STOC 2022, Chen and Peng [5] studied the complexity of this problem and they proved that developing c-approximation dynamic algorithm for < 2 is not possible unless we use number of oracle queries polynomial in the size of ground set V. In 2023, Banihashem, Biabani, Goudarzi, Hajiaghayi, Jabbarzade, and Monemizadeh 7 developed problem under cardinality constraint using a polylogarithmic amortized update time. Concurrent works of Banihashem, Biabani, Goudarzi, Hajiaghayi, Jabbarzade, and Monemizadeh and Duet- ting, Fusco, Lattanzi, Norouzi-Fard and Zadimoghaddam [22] developed the first dynamic algorithms for monotone submodular maximization under matroid constraint. Authors of [6] also improve the algorithm of [46] for monotone submodular maximization subject to cardinality constraint k. There also studies the dynamic model of influence maximization, which shares similarities with submodular maximization 48
algorithm for monotone submodular maximization
In this paper, for the first time, we study the generalized version of their problem by presenting an algorithm for maximizing the non-monotone submodular functions in the dynamic setting.
2 Dynamic algorithm
In this section, explain the algorithm that we use in the reduction that we stated in Metatheorm
1.2
The pseudocode of our algorithm is given in Algorithm I Algorithm 2 and Algorithm 3
Such reductions were previously proposed in the offline model by [34, and later works extended this idea to the streaming model [4 We develop reduction in the dynamic model inspired by these works, though in our proof, we require tighter analysis to obtain the approximation guarantee in our setting.
We consider an arbitrary time t of sequence E where V2 is the set of elements inserted before time t, but not deleted after their last insertion. Let OPT; maxscv.:1s gu f(S). For simplicity, we drop t from V2 and OPT;, when it is clear from the context.
In the following, assume that the value of OPT is known. Although the exact value of OPT* is unknown, we can maintain parallel runs of our dynamic algorithm for different guesses of the optimal value. By using (1 + E')², where i Z as our guesses for the optimal value, one of our guesses (1+ ='==''-appooximaat the value of OPT We show that the output of our algorithm satisfies the approximation guarantee in the run whose OPT (1 E') aapproxiimatss the value of OPT Later, in the appendix, we show that is enough to consider each element e only in runs for which we have 5'2 (1 + e')² < f(e) S (1 + e')². This method increases the query complexity of our dynamic algorithm by only a factor of Os--1 log k).
Our approach for solving the non-monotone submodular maximization is to first run the thresholding algorithm with input set V to find a set Sj of at most k elements. Since ff is non non-monotone, subsets of S might have higher submodular value than fSi). Then, we use an a-approximation algorithm (for 0- < a < 1) to choose a set S C S1 with guarantee (S]( 2 a maxcgs, fC). Next, we run the thresholding algorithm with the input set V\S1 and compute a set Sy. At the end, we return set S = arg maxçe (S,.), (.5)) f(C). Intuitively, for an optimal solution S if f(S1 n S*) is good approximation of OPT. then f(S)) is good approximation of OPT. On the other hand, if both (Si) and f (S; n S are small with respect to OPT, then we can ignore the elements of S and show that we can find set S, C V S1 of size at most k whose submodular value is good approximation of OPT. The following lemma proves that the submodular value of S is a reliable approximation of the optimal solution. The formal proof of this lemma can be found in Section
5

---

Lemma 2.1 (Approximation Guarantee). Assuming that OPT* submodular value of set is E[f(S)) 2 (1 O(e)) OPT
14ee OPT), the expected
OPT
6+
Next, we explain the steps of our reduction in detail. Let us first fix the threshold
k(3+1/(2a)) Then, we fix a r-thresholding dynamic algorithm (for example, [46 or (6) and suppose we denote it by DYN.MICTHRESOOLLING Before sequence = of updates starts, we create two independent instances 7 and Zz of DYMMMICTTRESHOLNNGG The first instance will maintain set S1 and the second instance will maintain set S2. For instance I₃ where i E {1,2}, we consider the following subroutines:
OPT
INSERTy, (v): This subroutine inserts an element v to instance I,
DELETEZ, (v): Invoking this subroutine will delete the element v from instance I,,
EXTRACTZ, This subroutine returns the maintained set (of size at most k) of I,
Extracting St. After the update at time t, first, we would like to set Z = oru Si (u). if the update is the insertion of an element ST is the set Si that instance In maintains just before this update. To find set ST we just need to invoke subroutine EXTRACTZ, If the update is insertion, we insert it into instance Iι using INSERTZ, (v, r), and if the update is a deletion, we delete o from both Iς and Iz using DELETEZ, (v) and DELETEI, (v). We then invoke EXTRACTI, once again return set Sj.
Z the deletion of element v, respectively, where
Extracting Sy. Buchbinder et al. developed a method to extract a subset Si C S1 whose submodular value is good approximation of maxcçs, f(C). In this algorithm, we start with two solutions 0 and Si. The algorithm considers the elements (in arbitrary order) one at a time. For each element, determines whether should be added to the first solution or removed from the second solution. Thus, after a single pass over set Sj, both solutions completely coincide, which is the solution that the algorithm outputs. They show that a (deterministic) greedy choice in each step obtains 3-approximation of the best solution in Sj. However, if we combine this greedy choice with randomization, we can obtain a-approximate solution. Since we do a single pass over set S1, the number of oracle queries is ({S)
The second algorithm that we can
extract Sy is random sampling algorithm proposed by Feige et al. (27), which choose every element in S₁ with probability 1/2. They show that this random sampling returns set Si whose approximation factor is 1 1/4 of maxcgs, f(C), and its number of oracle calls is O(1). We denote either of these two methods by SUBSETSELECTION
Extracting S2. Next, would like to update the set S2 that is maintained by instance Iz. To do this, for every element u E Z 11, we add it to Ig using INSERTZ, (u, T). and for every element S1 ZZ, delete it from Ig using DELETEZ, (u, r). Finally, when In exactly includes all the current elements other than the ones in S,, we call subroutine EXTRACTZ, to return set S2.
Corollary 2.2.
We obtain the (8 + E) approximation guaranty stated in the Metatheorem
1.2 by
using the local search method for our FUBSET and we get the (10 + 8) approximation guaranty by utilizing the random sampling method for our SUBSETSELECTION subroutine.
Proof. These immediate results of Lemma 2.1 and being 2/2 and in the local search method and random sampling method, respectively.
Algorithm Initialization(k: OPT)
1:
OPT (23+) where or based on the selection of algorithm for SUBSETSELECTION.
2: Instantiate two independent instances I, and Iz DYNAMICTHRESHOL.DIN for monotone submodular maximization under cardinality constraint l using 7

---

Algorithm 2 UPDATB(U)
Z <- EXTRACTZ,
2:
if UPDATE({) is an insertion then
3: Invoke INSERTT, (v), Z + {v}
4: else
5:
Invoke DELETEZ, (v), DELETEI, (v), + (0)
6: S + EXTRACTZ,
7: Si < SUBSETSELECTIONSS)
8: for S1 1Z do
9: DELETET, (u)
10: for E S) do INSERTZ, (u)
12: S2 + EXTRACTI,
13: Return arg (8..5) f(C)
Algorithm 3 SUBSETSELECTION(S)
1:
function UNIFORMSUUBSET(S)
2:
T 7+0 0
3: for E S do
4: if (oin( then T T
With probability 2
5:
6: return
7: function L.CAL.SEACCHSUUSETUSS
8: Xu + 0. Yo + S.
9:
for i = 1 to |S| do
10:
0; + s(X;-1 U (
b, t ((Y=-1 - s(Y.1)
af -- max (a;, 0), 61 max(bi;0))
12:
if 0 = 11 = 0 then d// + ()) =0
13:
with probability da/(a, + b)) do:
14:
X; + X (s.) Y, + Y;-1 else do: X, + X,-1, Y, Y,11 {s.)
15:
16:
return Xisı (or equivalently Y(s
Analysis. In this section, prove the correctness of algorithms and analyze the number of oracle queries of our algorithms, which finishes the proof of Theorems 1.2
Consider arbitrary time t. Let S, be the reported set of DYNAMICTHRESHOLDIS at time t. Recall that V. is the ground set at time t, and we drop the for simplicity, so we use V and $ to denote Vn and S,. We first present Lemmal 2.3 whose proof is given in the appendix. Then we proceed
to prove Lemma 2.1 and Theorem 1.2
Lemma 2.3. Suppose that set S satisfies Property 1.b of Definition I.I It means that S has less than k elements and for any V \ S, the marginal gain A(v)S) < Then, for any arbitrary subset
C' V, we have J'(S) 2 -
Assume that at fixed time t, OPT* and S are the optimal value and an optimal solution for the submodular maximization function f under cardinality constraint k. This means that | < k and f(S*) OPT*. Recall that - OPT where OPT is our 3.3+25
Proof of Lemma 2.1:
guess for the optimal value. Also, by assumption have OPT* E OPT OPT), or equivalently OPT [OPT*, + e')OPT").
To prove the lemma, claim that max (l)
G+ Suppose this claim is true. Using Jensen's inequality 233 we have -1-0()))) OPT (ax(E] (S))),), ([)()))) which yields ({)(S) 2 (1 O(e') OPT
(41)))
6417a.
7

---

To prove the claim, we consider two cases. The first case is when f(S1 ( > zk and the second r case is if f(S (SS*) 2n
Suppose the first case is true. Then, the subset selection algorithm (either random sampling method or local search) returns Sj for which E[f())) 2 maxscs, S(S). Since Si n S Si, we have
For the latter case, we show that [[](S + E[ > (1 O(s)) orr" 3+1/2a inferring or | 6+1/a Indeed, since S1 and S2 are reported by an k. then max max Eff is at least -PPT by the first property of r-thresholding algorithms.
max (B[](S))), ([((S2))) 2 (1 (s'))
OPT
r-thresholding algorithm, if [S]]
7k 3+1/2a
Now suppose that | |S2l < k; which means that Property 1.b of Definition 1.1 holds for S and S2. Therefore, we have ((Si) 2 S(S U.S) - and f(S2 2 [(S (S* (i) - -| Si]
by Lemma 2.3 Besides, we have ((S
rk < 0. Therefore,
S(Si) + f(52) 2 Since |S* (1 - |S S k we have
- -|S- + 1(22 (()) - -11S" \ J(S 2a
f(Si) + ((s)
US)) f(2 (8)) + (( (2 1/(a)))
Since S S2 0 and submodular, we have [(S U S*) A(, (S* \ (1) > S(S]
S2 U
+ + f(S S1). Additionally, by the submodularity and non-negativity of f. we have f(S 2 f(S)) - \ Si). because f(S (SS**SS \S1 + f(; ns*) )( f0)). By adding the last two inequalities and using the non-negativity of f once again, we get f(S US*)+ f(S, U
(S* Si)) + [(S n*)*) 2 f(1 USSSS*) + f(5) 2 f(S") = OPT*. By putting everything together we have,
S(S)) + ((S2) 2 OPT (2+ 1200))2k===0PPP 4a + (
OPT(2a)
2a
6a +
By using the assumption that OPT - (1 +')PPP we have,
[(S))+((S)) OPT" (PP (4a 1) OPT 2a c(4a +
OPT (1-00(')) - ; 1/(x))
6a +
6a
+
Proof of Theorem 1.2
As previously discussed, we' ve established in Lemma 2.1 and Corollary 2.2 that utilizing the local search method for the SUBSETSELECTION subroutine results an approximation ratio of (8 + e). whereas the random sampling method achieves an approximation ratio of (10 + +)). Thus, the only remaining aspect to address in proving this theorem is proving the query complexity of our proposed algorithm. In Lemma 2.4, we bound the number of queries made in each run of our algorithm per
update, proving the bounds given in Theorem 1.2 by considering the extra O -1 llog ff)-fcctor caused by our parallel runs.
D
Lemma 2.4. Let the random variable Qt denote the number of oracle calls that our algorithu in Theorem T.2 makes time in each of the parallel runs. Depending on whether the expected or ex- pected amortized number of oracle calls made by the thresholding algorithm DYNAMICTHRESHOOD per each update is (gg(n, ((,1))) k)), if we choose the local search method our SUBSETSELECTIIN subroutine, we have
E[Qr] O(min(k: g(n, k), g(,,))),
or
E
Qd O(T min(k g(n, k), g(, k))) 0(k)
and if we choose the random sampling method as our SUBSETSELECTION subroutine, we have
E[Q:] E Ommin(k g(n, k), g(n, g(, k))))
8

---

or
T
E Qil O(T min(k s(n, (n,, k)))
t=1
Proof. Consider the case where the expected number of oracle calls made by the thresholding algorithm DYNAMICTHRESHOLD per each update is O(g(n, k)). Per each update, our algorithm makes an update in instance I causing (g(n, k)) oracle queries. Next, we make either O(k) or oracle queries for the SUBSET SELECTION subroutine, depending on the used method. We also make series of updates in instance Zz, each causing ( k)) oracle queries. The number of such updates is bounded by number of changes k and (g,(n, k)) (according to the second property of Definition 1.1 These comprise all the oracle queries made by our algorithm at time t. Therefore, the given bounds for this case hold. A detailed proof for the remaining bounds is provided in the appendix.
output instance Ii, which is bounded by both
Empirical results
this section, we empirically study our -aprro-apioximmatio dynamic algorithm. We implement our codes in C++ and run them MacBook laptop with 8 GB RAM and M1 processor. We empirically study the performance our algorithm for video summarization and the Max-Cut problem.
Video summarization. Here, we use the Determinantal Point Process (DPP) which is introduced by [42], and combine it with our algorithm to capture video summarization. We experiments on YouTube and Open Video Project (OVP) datasets from 220].
For each video, we use the linear method of 33 to extract subset of frames and find positive semi-definite kernel with size n n where is the number of extracted frames. Then, we try find
a subset S of frames such that it maximizes det(Ly) where Ls is the sub-matrix of L restricted to
Ze([++]
indices corresponding frames S. Since I. is positive semi-definite matrix, have det(Ls)) 0. Interestingly, (39 showed that log(det( Ls)) a non-monotone function. We use these properties and set (S) log(det(Ls)) 1) to make f non-monotone non-negative submodular function. Then we run our (8 + e)aaproxximate dynamic algorithm to find the best to maximize f(S) such
that |S| & for ls [10].
Figure 1: Video summarization of Susan Boyle's performance on Britain's Got Talent show (video 106) from YouTube.
Figure 2: Video summarization for "Senses And Sensitivity, Introduct, to Lecture 1 presenter" (video 36) from OVP.
First, we insert all frames observe the quality of our algorithm. Figure and are the selected frames by our algorithm for Video 106 from YouTube and Video 36 from OVP, respectively, when we limit the number of selected frames to 4. Then, we create a sequence
updates frames each
video. Similar to 40 we define the sequence
sliding window model. That is, given window of size W for parameter W N, a frame inserted time L. and will be alive for window of size W and then delete that frame.

---

To evaluate the performance of our algorithm, we benchmark (See Figure } the total number of query calls and the submodular value of set S of our algorithm and the streaming algorithm proposed for non-monotone submodular maximization so-called SAMPLEE-TRRAMII algorithm works as follows: Upon arrival of an element u, with probability (1 2). for a parameter
proposed in 28). This
O < 9 < 1, we ignore u, otherwise (i.e., with probability Q) we do the following. If the size of set S that we maintain is less than h; ie. [S] < & and A(usS) > O, we add u to S. However, if [S] = k. we select an element E S for which ( : S) is minimum possible, where A(u 5) equals to A() where S,, are elements that arrived before u in sequence E. If (uu]S) 2 (1 + c) : S) for constant c, we replace by u, otherwise, we do nothing. Now convert this streaming algorithm into a dynamic algorithm. To accomplish this, we restart SAMPLE-STREAMIN STREAMING after every deletion that deletes an element of solution set S that is reported by SAMPLE-STREAMIN STREAMING'S outputs. That is, a deletion does not touch any element in set S, we do nothing; otherwise we restart the streaming algorithm.
10
1,000
ornele calls
calls
1,000
500
500
0
0
2
10
2
10
2
4
6
8
k
k (c)
k (d)
(a)
(b)
Figure 3: We plot the total number of query calls and the average output of our dynamic algorithm and SAMPLE-STRER STREAIINTA on video 106 from YouTuube and video 36 from OVP, In this figure, from left to right, figuris (a) and (b) are the total oracle calls for video 106 and 36, respectively. Similarly, Sub-figures (c) and (d) are average submodular value for video 106 and 36, respectively.
We run our algorithm for e = k/2 and compare the total oracle calls and average output of our algorithm and SAMPLE-STREAMIN in Figure 3 To prove the approximation guarantee of our dynamic algorithm, we assumed e < 1. However, in practice, it is possible to increase E up to a certain level without affecting the output of the algorithm significantly. On the other hand, increasing e reduces the total oracle calls and makes the algorithm faster. As you can see in Figure plots (b) algorithm
and (d), the submodular value of our algorithm is not worse than the SAMPLE-STREANE whose approximation factor is 3 + 2v2 5.828 which is better than our approximation factor. Thus, our algorithm has an outcome better than our expectation, while its total oracle calls are better than SAMPLE-S CAMPLE-STREAMPII STreAMING algorithm (look at Figure 3 plots (a) and (c)).
We also empirically study the celebrated Max-Cu problem which is a non-monotone submodular maximization function (See (27). These experiments are given in the appendix.
4 Conclusion
In this paper, we studied non-monotone submodular maximization subject to cardinality constraint & in the dynamic setting by providing reduction from this problem to maximizing monotone submodular algo-
functions under the cardinality constraint A with certain kind of (ooriihm((-threshoddie rithms). Moreover, we used our reduction to develop the first dynamic algorithms for this problem. In particular, both our algorithms maintain solution set whose submodular value is a (8 + e)- approximation of the optimal value and require O(= (ng log(k)) and O( -(=-1A? log log²(k) (k)) oracle queries per update, respectively.
5 Acknowledgements
This work partially supported by DARPA QuICC NSF AF:lmall #2218678, and NSF AF:lmall #21 14269.
10

---

References
[1] Naor Alaluf, Alina Enc, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal streaming algorithms for submodular maximization with cardinality constraints. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming. ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 6: 6:1-6:19. Schloss Dagstuhl Leibniz-Zennrum Zentrum für Informatik, 2020.
[2] Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh, An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 47(4):2667-200 2022.
[3] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999.
[4] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: massive data summarization on the fly. Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, 2014.
[5] Eric Balkanski, Adam Breuer, and Yaron Singer. Non-monotone submodular maximization in exponentially fewer iterations. Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 1359-2377 Red Hook, NY, USA, 2018. Curran Associates Inc.
[6] Kiarash Banihashem, Leyla Biabani, Samira Goudarzi. MohammadTaghh Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic algorithms for matroid submodular maxi- mization. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, arXiv:2306.0099 00959..
[7] Kiarash Banihashem, Leyla Biabani, Samira Goudarzi. Mohammadtaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic constrained submodular optimization with polylogarithmic update time. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages (660-1691. PMLR, 23-29 Jul 2023.
[8] MosammadHossein Bateni, Mohammad Taghi Hajiaghayi, and Morteza Zadimoghaddam. Submodular secretary problem and extensions. ACM Trans. Algorithms, ((4):32:1332:2)) 2013.
[9] MohammadHoseein Bateni, MohammadTaghh Hajiaghayi, and Morteza Zadimoghaddam. Sub- modular secretary problem and extensions. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Al- gorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 39-52. Springer, 2010.
[10] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via nonsymmet- ric technique. Math. Oper. Res., 44(3):988-1003 2019.
[11] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization. SIAM J. Comput., 44(5):1384 1402, 2015.
[12] Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz. Submodular maxi- mization with cardinality constraints. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, page 1433-1452, USA, 2014. Society for Industrial and Applied Mathematics.
[13] Larry Carter and Mark N. Wegman. Universal classes of hash functions (extended abstract). In Proceedings of the 9th Annual ACM Symposiun on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA. pages 106-112, 1977.

---

[14] Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In Magnús M. Halldórsson, Kazuo Iwana, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming, pages 318-330, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
[15] Xi Chen and Binghui Peng. On the complexity of dynamic submodular maximization. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1685-1698. ACM, 2022.
[16] Yixin Chen and Alan Kuhnle. Practical and parallelizable algorithms for non-monotone submodular maximization with size constraint, 2022.
[17] Abhimanyu Das and David Kempe. Algorithms for subset selection in linear regression. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 45-54, ACM, 2008.
[18] Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28- July 2, 2011, pages 1057-1064, Omnipress, 2011.
[19] Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. J. Mach. Learn. Res., 19:3:1-3:34, 2018.
[20] Sandra Eliza Fontes de Avila, Ana Paula Brandão Lopes, Antonio da Luz Jr., and Arnaldo de Albuquerque Araújo. VSUMM: A mechanism designed to produce static video summaries and novel evaluation method. Pattern Recognit. Lett., 32(1):56-68, 2011.
[21] Delbert Dueck and Brendan J. Frey. Non-metric affinity propagation for unsupervised image categorization. In JEEE / Ith International Conference on Computer Vision, ICCV 2007, Rio de Janeiro, Brazil, October 14-20, 2007, pages 1-8. IEEE Computer Society, 2007.
[22] Paul Duetting, Federico Fusco, Silvio Lattanzi. Ashkan Norouzi-Fard and Morteza Zadi- moghaddam. Fully dynamic submodular maximization over matroids. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages
PMLR, 23-29 Jul 2023.
[23] Rick Durrett. Probability: Theory and Examples, 4th Edition. Cambridge University Press, 2010.
[24] Khalid El-Arini and Carlos Guestrin. Beyond keyword search: discovering relevant scientific literature. In Chid Apté, Joydeep Ghosh, and Padhraic Smyth, editors, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011, pages 439 447. ACM, 2011.
[25] Ethan R. Elenberg. Rajiv Khanna, Alexandros G. Dimakis, and Sahand N. Negahban. Restricted strong convexity implies weak submodularity. CoRR, abs/1612.00804, 2016.
[26] Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Non-monotone sub- modular maximization with nearly optimal adaptivity and query complexity. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pages 1833-1842. PMLR, 2019.
[27] Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM J. Comput., 40(4):1 133--153, 2011.
[28] Moran Feldman, Amin Karbasi, and Ehsan Kazemi. Do less, get more: Streaming submodular maximization with subsampling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Resa-Bianchh, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018,
NewrlPS 2018, December 3-8, 2018, Montréal, Canada, pages 730-740, 2018.
12

---

[29] Moran Feldman, Joseph Naor, and Roy Schwartz. Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract). Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, Automata, Languages and Programming 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, volume 6755 of Lecture Notes in Computer Science, pages 442-353. Springer, 2011.
[30] Satoru Fujishige. Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions. Math. Program., 29(2):142-155, 1984.
[31] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing.
In Proceedings of the Twenty-Secone Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 11, page 1098-1118 USA, 2011, Society for Industrial and Applied Mathematics.
[32] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithus, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1098-1116. SIAM, 2011.
[33] Boqing Gong, Wei-Lun Chao, Kristen Grauman, and Fei Sha. Diverse sequential subset selection for supervised video summarization. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 1-13 2014, Montreal, Quebec, Canada, pages 2069-20777 2014.
[34] Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non- non-monotone submodular maximization: Offline and secretary algorithms. In Amin Saberi, editor, Internet and Network Economics 6th International Workshop, WINE 2010, Stanford, CA, USA, December 13-17, 2010. Proceedings, volume 6484 of Lecture Notes in Computer Science pages 246-256 257. Springer, 2010.
[35] Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. Optimal marketing strategies over social networks. In Proceedings of the 17th international conference on World Wide Web, pages 189-198, 2008
[36] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 53(3):307-323, 2006.
[37] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submod- ular maximization: Data summarization with privacy and fairness constraints. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässann Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Muchine Learning Reseurch, pages 2549-2558. PMLR, 2018
[38] Rajiv Khanna, Ethan R. Elenberg, Alexandros G. Dimakis, Sahand N. Negahban, and Joy- deep Ghosh. Scalable greedy feature selection via weak submodularity. In Aarti Singh and Xiaojin (Jerry) Zhu, editors, Proceedings of the 20th International Conference on Artificial Intel- ligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pages 1560-1568 1568. PMLR, 2017.
[39] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. Found. Trends Mach. Learn., 5(2-3): 123-286, 2012.
[40] Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Morteza Zadimoghaddam. Fully dynamic algorithm for constrained submodular optimization. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florin, Balean, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[41] Paul Liu and Jan Vondrák. Submodular optimization the mapreduce model. In Jeremy Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA @ SODA 2019, January 8-9, 2019 San Diego CA, USA, volume 69 of OASICS, pages 18:1-18:10 10. Schloss Dagstuhl- Leibniz-Zentrun für Informatik, 2019.
13

---

[42] Odile Macchi. The coincidence approach to stochastic point processes. Advances in Applied Probability, 7(1):83-122, 1975.
[43] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In Maria Florina Balcan and Kilian Q. Weinberger, editors. Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1358-1367, New York, New York, USA, 20-22 Jun 2016. PMLR.
[44] Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors, Proceedings of the Thirly-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovalive Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-I8), New Orleans, Louisiana, USA, February 2-7, 2018, pages 1379-1386. AAAI Press. 2018.
[45] Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Deletion-robust submodular maximization: Data summarization with "the right to be forgotten". In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages -458.2458. PMLR, 2017.
[46] Morteza Monemizadeh. Dynamic submodular maximization. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
[47] Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovic, Amir Zandich, Aidasadat Mousav- ifar, and Ola Svensson. Beyond 1/2-approximation for submodular maximization on massive data streams. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th Interna- tional Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3826-3835. PMLR, 2018
[48] Binghui Peng. Dynamic influence maximization. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 10718- 10731,, 2021.
[49] Sharon Qian and Yaron Singer. Fast Parallel Algorithms for Statistical Subset Selection Problems. Curran Associates Inc., Red Hook, NY, USA, 2019.
[50] Ian Simon, Noah Snavely, and Steven M. Seitz. Scene summarization for online image collections. In IEEE 11th International Conference on Computer Vision, ICCV 2007, Rio de Janeiro, Brazil, October 14-20, 2007, pages 1-8. IEEE Computer Society, 2007.
[51] Ruben Sipos, Adith Swaminathan, Pannaga Shivaswamy, and Thorsten Joachims. Temporal cor- pus summarization using submodular word coverage. Xue-wen Chen, Guy Lebanon, Haixun Wang, and Mohammed J. Zaki, editors, 21st ACM International Conference Information and Knowledge Management, CIKM 12, Maui, HI. USA, October 29 November 02, 2012, pages 754-763. ACM, 2012.
[52] Sebastian Tschiatschek, Rishabh K Tyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Pro- cessing Systems, volume 27, Curran Associates, Inc., 2014.
14


Reviews:
[{"review_id": "pr5KyXsIA6", "reviewer": "Reviewer_Ma6Y", "summary": "The authors consider an submodular non-monotone optimization problem in fully dynamic setting. The authors propose a 8+epsilon approximation algorithm by combining several existing methods.", "questions": "The authors should improve the presentation of the paper\n\n- The abstract is probably better without references to Neurips or STOC\n- Line 20-22. Provide citations.\n- Page 2: remove grey outline boxes.\n- Line 51, remove bolding\n- Property 2. queries is not defined.\n- Reword/remove metatheorem.\n- Line 98: . That is -> , that is,\n- Line 178: algorithms -> algorithm\n- Named paragraphs starting on Page 5 need connecting text.\n- There is a follow-up paper of [7] that derandomizes the algorithm of [7] (and keeping 2-approximation). Can this algorithm used?", "limitations": "Probably the biggest limitation of the method is a rather weak approximation guarantee. It is not clear whether a stronger approximation is possible. This is not discussed by the authors.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The technique behind the proposed algorithm is interesting.\n- Proven approximation guarantee.\n- A nice continuation of the existing literature in submodular optimization.", "weaknesses": "- 8 + epsilon is a rather weak approximation guarantee.\n- The other algorithm with 10 + epsilon approximation uses a weak algorithm, so the algorithm is largely pedagogical.\n- Presentation needs improvement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Please see below for our answers to your comments: \n\n> 8 + epsilon is a rather weak approximation guarantee.\n\nOur primary goal in this paper was to obtain the first dynamic constant-factor approximation algorithm for non-monotone submodular maximization. This answers affirmatively an open question posed by Chen and Peng in [11]. Indeed, developing a dynamic algorithm for this problem with a better approximation factor than $(8 +\\epsilon)$ is an interesting future direction in this area. \nYet, it is worth mentioning that non-monotone submodular maximization is far more difficult than monotone submodular maximization. Monotone submodular maximization under cardinality constraint has a tight $\\frac{e}{e -1}$ approximation algorithm in the offline mode and nearly tight $2 + \\epsilon$ approximation algorithms for both streaming and dynamic settings. However, for the non-monotone version, there is a hardness result that says it is impossible to obtain a $2.04$ (i.e., $0.491$) approximation algorithm for this problem even in the offline setting, and to the best of our knowledge, the current state of the art algorithms for this problem have $2.6$ and $3.6$ (i.e., $0.385$ and $0.2779$) approximation guarantee for offline and streaming settings respectively. Hence, we believe our algorithm with $(8+\\epsilon)$ approximation guarantee as the first non-monotone algorithm in the dynamic setting is valuable.\n\n> Probably the biggest limitation of the method is a rather weak approximation guarantee. It is not clear whether a stronger approximation is possible. This is not discussed by the authors.\n\nThe reduction resulting in the $(10 + \\epsilon)$-approximation algorithm is interesting because of its potential to develop a dynamic algorithm with polylog(n) oracle queries for non-monotone submodular maximization. In particular, if one can show that a dynamic algorithm for monotone submodular maximization with polylog(n) oracle queries is a $\\tau$-thresholding dynamic algorithm, our reduction immediately provides a counterpart dynamic algorithm for non-monotone submodular maximization with polylog(n) oracle queries. \n\n> The abstract is probably better without ...\n\nThank you for your comments on the presentation. We will incorporate them in the revised version of the paper.\n\n> There is a follow-up paper of [7] that derandomizes the algorithm of [7] (and keeping 2-approximation). Can this algorithm be used?\n\nThe dynamic algorithm from [38] that we use as our $\\tau$-thresholding algorithm is a randomized algorithm. Therefore, even if we use the derandomized version of the algorithm of [7], our dynamic algorithm would remain randomized. \n\n> Probably the biggest limitation of the method is a rather weak approximation guarantee. It is not clear whether a stronger approximation is possible. This is not discussed by the authors.\n\nPlease see our response to the first comment.\n\n"}, {"review_id": "8Rt60PQwuw", "reviewer": "Reviewer_4fuM", "summary": "The paper studies the dynamic submodular maximization problem and gives the first efficient dynamic algorithm that maintains a constant approximation solution.\n\nIn the problem of dynamic submodular maximization, there is a sequence of updates (insertions/deletions) of ground set element, and one wants to maintain a subset (of size at most $k$) that obtains the maximum possible function value. Previous work provide tight approximation guarantee when the function is monotone, while this paper extends to non-monotone submodular function (albeit with worse approximation guarantee).\n\nThe main result of this paper is an $(8+\\epsilon)$ approximation algorithm with $\\mathsf{poly}(k, \\log n, \\epsilon^{-1})$ amortized update time per update. The algorithm is obtained through a clever reduction from dynamic algorithms for monotone function (and satisfies certain threshold property). The overall idea is to simulate the monotone threshold algorithm twice and combines double greedy or random sampling. The first run guarantees the marginal is small for the second algorithm, if it works bad.\n\nBesides theoretical results, the author also conduct empirical study and verify its practicality.\n\n\n--------------\nI have read the author's response and I keep my positive evaluation of the paper.\n\n", "questions": ".", "limitations": ".", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper provides the first sublinear dynamic algorithm for non-montonne submodular maximization. The theoretical contribution is novel and interesting from my perspective. The experiment result is also promising.", "weaknesses": "There is no major weakness. Some minor issues are listed below.\n\n\n(1) Line 201, it seems one can directly use the double greedy algorithm to extract $S_1'$, I don't see why you mention the 3-approximation deterministic algorithm.\n\n(2) Line 242, delete \"what\"\n\n(3) The related work is quite extensive, there are a few missing reference that are relevant to the paper. The first two reference below seems appear on Arxiv later than NeurIPS submission, but I encourage the author to add the reference in the later version. The third reference gives lower bound for white box dynamic submodular maximization.\n\n[1] Dynamic Algorithms for Matroid Submodular Maximization. Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh\n\n[2] Fully Dynamic Submodular Maximization over Matroids. ICML 2023\nPaul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam\n\n[3] Dynamic influence maximization. NeurIPS 2021\nBinghui Peng\n\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for pointing out the issues and listing the extra references. We will make sure to incorporate them in the revised version of the paper."}, {"review_id": "cGPXtcaxKQ", "reviewer": "Reviewer_PoYA", "summary": "In this paper, the authors consider the non-monotone submodular maximization problem under the cardinality constraint and dynamic model. Here, the dynamic model means that the ground set of the submodular function changes every time step where one element is inserted into or deleted from the ground set, and the update is controlled by an oblivious adversarial. They show a reduction from non-monotone case to monotone case, and then obtain a dynamic algorithm with (8+eps)-approximation ratio. They further test their algorithm on some real-world data sets.", "questions": "See weakness 1", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. In the dynamic setting, they provide a constant approximation algorithm for non-monotone submodular maximization problem under cardinality constraint. \n2. The reduction between non-monotone dynamic algorithm and monotone dynamic algorithm shows some connection between these two cases.", "weaknesses": "1. I’m confused with the relation between parameter $\\tau$ and the results in theorem 1.2. The current description looks like there is no relationship between these two. But, if $\\tau$ is large enough, it seems we can satisfy definition 1.1 by keeping $S_t$ an empty set. For example, we can assume without loss of generality $f(u)\\leq 1$ for any u and set $\\tau =1$. In this case, we have a trivial $\\tau$-thresholding dynamic algorithm. Then, what does theorem 1.2 look like?\n2. Although the paper tries to show the connection between monotone case and non-monotone case by the reduction theorem, it seems that this connection is weak. Firstly, to show a monotone dynamic algorithm is \\tau-thresholding algorithm is not an easy task, so that it is not easy to use this reduction. More importantly, the reduction does not mean that a better monotone dynamic algorithm can imply a better non-monotone dynamic algorithm (comparing to the reduction result in [35]). The better approximation ratio of the monotone dynamic algorithm does not help. It is also not clear whether the lower amortized update time can help or not.\n\nThe author's response has clarified my main concern here, so I would like to raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Please see below for our answers to your comments: \n\n>I’m confused with the relation between parameter $\\tau$ and the results in theorem ...\n\nThank you for pointing out this issue. It appears that the writing here has been confusing, and you may have misunderstood the theorem statement.\nThe assumption of the theorem is that there exists a $\\tau$-thresholding for **any** given value of $\\tau$. In other words, $\\tau$ is an input parameter. Therefore, one cannot simply set $\\tau=1$ and obtain an algorithm for this value; the algorithm should work for *any* value of tau.\nSpecifically, our reduction sets $\\tau = \\frac{OPT}{k(3+1/(2\\alpha))}$, where OPT denotes our guess for the optimal value.\n\nPlease let us know if you have any additional questions regarding the theorem.\n\n>Although the paper tries to show the connection between monotone case and non-monotone case by ...\n\nWe answer different parts of your comment separately to cover all the points you made, with the hope of resolving all of your concerns.\n\nFirstly, regarding your concern about the difficulty of showing that an algorithm is $\\tau$-thresholding:\nWe agree that for any monotone algorithm, the $\\tau$-thresholding property would need to be formally verified (e.g., we do this in our paper in Appendix D).\nHowever, all dynamic algorithms known for monotone submodular maximization under cardinality constraint $k$ have been based on the thresholding algorithm proposed in [1], and it is not unreasonable to expect current and even future dynamic algorithms to be $\\tau$-thresholding. \n\nSecondly, regarding your concern about improvements in monotone dynamic algorithms:\nChen and Peng in [2] show that $\\frac{1}{2}$ is a tight approximation guarantee for the dynamic submodular maximization problem. Therefore, we do not expect any improvement in the approximation guarantee of monotone dynamic algorithms. However, the query complexity of dynamic algorithms for the problem of monotone submodular maximization under cardinality constraint can be improved. As we observe in Theorem 1.2, if such improvements are obtained using a $\\tau$-thresholding algorithm, this will improve the update time (measured by query complexity) of our dynamic algorithm for the non-monotone version as well. \n\nIt is worth mentioning that a new dynamic algorithm for monotone submodular maximization has been proposed in [3] (also mentioned by another reviewer). We believe it can be shown that this new and improved algorithm is also a $\\tau$-thresholding algorithm, which works fine in our reduction, and our reduction has already resulted in a better dynamic algorithm for non-monotone submodular maximization under cardinality constraint $k$. \n\nLastly, regarding the reduction in [35] ([4] below), we should mention that their reduction does not seem to be general as well. In their paper, they claim that the solution obtained by approximation algorithms for monotone submodular functions often satisfies $f(S) \\geq \\alpha f(S \\cup C^∗)$, where $1 \\geq \\alpha > 0$, and $C^∗$ is the optimal solution. (See Section Streaming Local Search for a collection of independence systems on page 3.) They use this as an assumption in their proof for their Theorem 1. (See equation (2) in proof of theorem 1 in supplementary materials). Hence, we believe their reduction also only works for monotone algorithms with that particular property and not any general algorithm. \n\n\n[1] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, Andreas Krause:\nStreaming submodular maximization: massive data summarization on the fly. KDD 2014: 671-680\n\n[2] Xi Chen, Binghui Peng: On the complexity of dynamic submodular maximization. STOC 2022: 1685-1698\n\n[3] Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh: Dynamic Algorithms for Matroid Submodular Maximization. CoRR abs/2306.00959 (2023)\n\n[4] Baharan Mirzasoleiman, Stefanie Jegelka, Andreas Krause:\nStreaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly. http://arxiv.org/abs/1706.03583\n"}, {"review_id": "4BMseEtp0n", "reviewer": "Reviewer_dvm4", "summary": "This work studies non-monotone submodular maximization subject to a cardinality\nconstraint in a fully dynamic setting, i.e., maintaining a good solution as\nelements are inserted and deleted from the \"current\" ground set. Studying\nnon-monotone submodular maximization in this model is the natural follow-up to\nthe works of:\n- Monemizadeh (NeurIPS 2020): $(0.5 - \\varepsilon)$-approximation for *monotone* dynamic submodular maximization with amortized update time $O(k^2 \\varepsilon^{-3} \\log^{5} n)$.\n- Lattanzi et al. (NeurIPS 2020): $(0.5 - \\varepsilon)$-approximation for *monotone* dynamic submodular maximization with amortized update time $O(\\log^4(k) \\log^2 (n) / \\varepsilon^{7})$.\n- Chen and Peng (STOC 2020): proves query complexity lower bounds for approximation ratios strictly greater than $0.5$ for monotone dynamic submodular maximization. Gives $(1-1/e-\\varepsilon)$-approximation for \"insertion-only\" streams for matroid constraints.\n\nThis work gives a $(1/8-\\varepsilon)$-approximation for the *non-monotone*\nfully dynamic cardinality-constrained problem with amortized query complexity\n$O(\\varepsilon^{-3} k^3 \\log^3 n \\log k)$ queries per update. The proposed\nalgorithm builds on connections to thresholding algorithms for *monotone*\nsubmodular maximization and then altering these solutions to get guarantees for\nnon-monotone functions. The authors include experiments and compare their\nalgorithm to the Simple-Streaming in Feldman-Karbasi-Kazemi (NeurIPS 2018).", "questions": "**Questions**\n- [line  74] This is less of a question and more of a comment:\n  The authors are correct in questioning whether thresholding works in a\n  non-monotone setting when a randomly sampled set is added to the current\n  solution, i.e., $f(S_t) \\ge k \\tau$. See Chen-Kuhnle (2022) for an example\n  where this property does not hold. However, also see Chen-Kuhnle (2022) and\n  Fahrbach-Mirrokni-Zadimoghaddam (ICML 2019, arXiv:1808.06932v3) for a method\n  to circumvent this problem.\n\n**Typos and suggestions**\n- [line 27] Two relevant missing works for non-monotone submodular maximization:\n  1. \"Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity\" (Fahrbach-Mirrokni-Zadimoghaddam, ICML 2019)\n  2. \"Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint\" (Chen-Kuhnle, arXiv:2009.01947, 2022)\n- [line  38] suggestion: The description of the dynamic setting \"... set of\n  elements that are inserted but not deleted after their last insertion time\n  till time $t$\" is not clear and should be improved. The description in Section\n  1.1 is better, but could still be improved (i.e., saying that $V_t$ is the set\n  of ``active'' elements at time $t$).\n- [line  71] typo: \"The only such a result\" --> \"The only such result\"\n- [line 184] suggestion: Consider using $\\text{Insert}_{i}(v, \\tau)$ to avoid\n  a double subscript.\n- [line 313] typo in Figure 3 description: \"submdoular\"\n", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- Gives $(1/8 - \\varepsilon)$-approximation for fully-dynamic non-monotone\n  submodular maximization subject to a cardinality constraint, answering an\n  open question in Chen-Peng (STOC 2020).\n- Builds on thresholding techniques commonly used for monotone submodular\n  maximization. This helps connect the toolkits for each problem type. Some\n  missing references on line 54 when discussing thresholding:\n  1. \"Submodular Optimization in the MapReduce Model\" (Liu-Vondrak, SOSA 2019)\n  2. \"Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity\" (Fahrbach-Mirrokni-Zadimoghaddam, SODA 2019)\n  3. \"Fully Dynamic Algorithm for Constrained Submodular Optimization\" (Lattanzi et al., NeurIPS 2020)\n  4. \"Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint\" (Chen-Kuhnle, arXiv:2009.01947, 2022)\n", "weaknesses": "- The biggest weakness of this paper are the experiments. They almost check all\n  of the boxes, but they aren't very motivating. This paper investigates:\n  1. video frame summary on the entire set, which doesn't use any aspect of\n     streaming but is a reasonable starting place to show what the algorithms\n     output.\n  2. sliding window model of length $W$, which is fully dynamic but not in the\n     most interesting way (though possibly the most practical way).\n  3. only compares against the Sample-Streaming algorithm of\n     Feldman-Karbasi-Kazemi (NeurIPS 2018). It would be nice to include\n     comparisons to the three papers discussed in the abstract, too, even though\n     they are for monotone submodular functions.\n- Given that there is randomness in this paper's Update algorithm (line 4 of\n  SubsetSelection), it is important for these experiments to be averaged over\n  several trials with standard deviation error bars. Both the oracle calls and\n  objective value plots appear somewhat noisy and non-monotone.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. We will make sure to fix the issues you pointed out and incorporate your suggestions in the revised version of the paper. "}]

Author rebuttal:

Meta-review: This paper gives the first constant factor approximation algorithm for non-monotone submodular maximization under a cardinality constraint in the fully dynamic setting with sublinear update time. Dynamic submodular maximization is a recent and active area of research in submodular optimization and this paper makes substantial progress in this area with the first algorithm for non-monotone functions. The techniques are also interesting and novel. I recommend acceptance.
Decision: Accept (poster)