Non-monotone Submodular Optimization: $p$-Matchoid Constraints and Fully Dynamic Setting
Authors: Kiarash Banihashem
Samira Goudarzi
MohammadTaghi Hajiaghayi
Peyman Jabbarzade
Morteza Monemizadeh
Venue: NeurIPS 2025 poster ()
Keywords: optimization
submodular
p-matchoid
non-monotone
dynamic
Primary area: theory

Abstract: Submodular maximization subject to a $p$-matchoid constraint has various applications in machine learning, particularly in tasks such as feature selection, video and text summarization, movie recommendation, graph-based learning, and constraint-based optimization. We study this problem in the dynamic setting, where a sequence of insertions and deletions of elements to a $p$-matchoid $\mathcal{M}(\mathcal{V},\mathcal{I})$ occurs over time and the goal is to efficiently maintain an approximate solution.
We propose a dynamic algorithm for non-monotone submodular maximization under a $p$-matchoid constraint. For a $p$-matchoid $\mathcal{M}(\mathcal{V},\mathcal{I})$ of rank $k$, defined by a collection of $m$ matroids, our algorithm guarantees a $(2p + 2\sqrt{p(p+1)} + 1 + \epsilon)$-approximate solution at any time $t$ in the update sequence, with an expected amortized query complexity of $O(\epsilon^{-3} pk^4 \log^2(k))$ per update.

Non-monotone Submodular Optimization: p-Matchoid Constraints and Fully Dynamic Setting
Kiarash Banihashem" University of Maryland College Park, MD, USA kiarash@umd. edu
Samira Goudarzi' University of Maryland College Park, MD, USA samirag@umd.cm edu
MohammadTaghhi Hajiaghayi" University of Maryland College Park, MD, USA hajiagha@umd. edu
Peyman Jabbarzade' University of Maryland College Park, MD, USA peyman @umd. @umm edu
Morteza Monemizadeh"
TU Eindhoven
Eindhoven, The Netherlands M. Monemi zadeh@tur uee .nl
Abstract
Submodular maximization subject to a p-matchoid constraint has various applica- tions in machine learning, particularly in tasks such feature selection, video and text summarization, movie recommendation, graph-based learning, and constraint- based optimization. We study this problem in the dynamic setting, where sequence of insertions and deletions of elements to a p-matchoid M(V,I) occurs over time and the goal is to efficiently maintain approximate solution. We propose dy- namic algorithm for non-monotone submodular maximization under p-matchoid constraint. For p-matchoid M(V, of rank defined by collection of ma- troids, our algorithm guarantees (2p 2 v + 1) + -approxxiaate solution at any time in the update sequence, with an expected amortized query complexity of -3 pk* (k)) per update.
1 Introduction
p-matchoid M(V. II) consists of matroids Mi(Vi, M2 ....) M,., In). where each element in the ground set V appears in the ground sets of at most of these matroids. Addition- ally, every subset X C V is independent set in I if X n Vi for any matroid I,,. In the context of submodular maximization subject to a p-matchoid constraint M(V, I). the objective is find an independent I that maximizes f(("), where submodular function defined over subsets of the ground set V.
2 R200 is (non-monotone)
The p-matchoid constraint has various applications in machine learning, particularly in tasks involving optimization and constraint satisfaction including the followings:
Feature selection: In feature selection, where the goal to pick subset of features that works well while keeping things simple, p-matchoids can be used to model constraints on the relationships between features. For example, if certain features
highly correlated redundant, p-matchoid constraint can ensure that only limited number of such features are chosen together Das and Kempe
20088 Khanna al. [2017). Elenberg al. (2016) Qian and Singer
[2019] Quinzan et [2023]
Video summarization and movie recommendation tasks: Submodular maximization under p- matchoid constraints is crucial for video summarization Feldman et al. [2018). Mirzasoeiman et al.
2018 Gu et al. 20233 and movie recommendation Harshaw (2022 Badanidiyuru et al. [2020).
'Equal Contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Liu et al. [2022] Tschiatschek et al. [0018] tasks. It helps select representative content and generate personalized and diverse recommendations, leading to improved user experience and engagement.
Text summarization: In text summarization Lin and Bilmes 2011] Bairi et al. 2015 Lin and Bilmes (2010), [Liu et al. (2013), summarizing multiple documents together (e.g.. news articles on the same topic or survey paper) is often necessary. In such scenarios, p-matchoids help ensure that the resulting summary represents a balanced combination of information from each document.
Viral marketing campaigns: Viral marketing promotes products services through social sharing and mfrd-of-mouth for rapid, exponential message spread. p- p-matchoids can model relationships and interactions, capturing constraints on information dissemination and influence propagation Zhang
et al. 2023] Jin et al. 2021]. Cui et al. [2021] Kempe et al. [2003)
In general, p-matchoids provide flexible way add complex rules to optimization problems in machine learning. By setting p-matchoid constraints, practitioners can adjust optimization algorithms to meet specific requirements and constraints, resulting in more robust models Quinzan al. [2021] Friedrich et al. [019 Wei et al. 20155.
In this paper, we study the non-monotone submodular maximization problem under p-matchoid constraint in fully dynamic setting. This model considers a sequence of updates, each of which is either an insertion or deletion. Using the notation V, V represent the set of elements present at any given time r, this model assumes that V, is derived from V after the insertion or deletion of an element e at time 1.
The ultimate objective of this problem is to maintain an independent set I' E I at each time such that f()) OPT, where OPT, = maxjer,ıvv, f(/) the optimal submodular value among any independent set in I present at time f. However, finding an exact solution for this problem, even in an offline setting where the elements are fixed and provided at once, is NP-hard as it generalizes problems such as unconstrained non-monotone submodular maximization and monotone submodular maximization under a cardinality constraint, both of which are known to be NP-hard Feige et al.) 2011], Nemhauser et al. (1978]. Therefore, we focus on developing approximate dynamic algorithms and use their approximation ratios to evaluate their quality. Also, following prior work, we assume having an oracle access to the submodular function f. and measure the performance of our algorithms based on their query complexities.
To underscore some specific aspects of this problem that make it more challenging than some other similar problems in the literature, we highlight the following:
The nature of the p-matchoid constraint, which is extremely versatile and generalizes even complex combinatorial structures such as the intersection of p matroids, p-uniform hypergraph matching, and by extension, matroid, and cardinality constraints, making it significantly more complex to handle.
Function ff not being monotone, as non-monon monoooet submodular maximization inherently more difficult than its monotone counterpart, evidenced by the weaker approximation guar- antees and increased complexity it typically yields across different settings and constraints, adding to the challenge.
The dynamic setting of the problem, where elements get inserted or deleted adversarially, and it requires algorithms to adapt to real-time changes.
To date, the most significant advancement in non-monotone submodular maximization in the dynamic setting is result presented at NeurlPS'23 23. In their pioneering study, Banihashem, Biabani, Goudarzi. Hajiaghayi, Jabbarzade, and Monemizadeh [Banihashem et al.) [2033] proposed a dynamic algorithm for non-monotone submodular maximization under cardinality constraint k. Their algorithm achieves (8 + approxxiimtioo while requiring an expected amortized Ok= log'(k)) oracle queries per update.
Despite this progress, the development of dynamic algorithms for non-monotone submodular maxi- mization under a matroid constraint, or more generally a p-matchoid constraint, remains an open and unexplored challenge, one that address in this study.

---

1.1 Our contribution and techniques
We present the main result of this paper the following theorem.
Theorem 1.1 (Main Theorem). Let 0 E be a parameter. Let M(V.I) I) be a p-matchoid consisting of m matroids Mi(V,, largest independent set I. Let f 2 + R (not necessarily monotone) submodular function defined over subsets of the ground set V. Then, there exists a dynamic algorithm for maximizing the function I subject to the p-matchoid constraint M(V. I), which maintains (2p+2 pp(p 1)+ ++)-- approximate solution at any time during the sequence of updates, while performing an expected amortized OlE pkc plo k) oracle queries per update.
and let k denote the size of the
As byproduct, obtain another result for the special case of cardinality k, stated below.
Corollary 1.2. There exists a dynamic algorithm for non-monotone submodular maximization subject to a matroid constraint of rank k (including the cardinality constraint k), which achieves (5.82 e)-aprooximate solution using OlE*k log k) oracle queries per update.
Our algorithm for the cardinality case is an improvement upon the approximation of the dynamic algorithm presented by Banihashem et Banihashem et al. [2023], which maintains (8 + E)-
approximate solution with an expected amortized O( 0(="k'' log' (k)) oracle queries per update.
Under the assumption that the submodular function I is monotone, the approximation guarantee of Theorem I.1 can be strengthened. An adaptation of our algorithm then yields the following side result:
Proposition 1.3. There exists a dynamic algorithm for monotone submodular maximization subject to p-matchoid constraint of rank k with (4p + e) approximation guarantee and O pk* log"(k) (k)) update time.
1.1.1 Overview of our algorithm
We present dynamic algorithm for non-monotone submodular maximization under p-matchoid constraints, where the ground set evolves through a sequence of insertions and deletions. Our approach builds combining two core ideas: filtering and selective sampling. The offline algorithm processes elements in multiple levels, iteratively refining the solution by selecting elements with high marginal gain relative to the structural cost imposed by the p-matchoid constraints. This recursive mechanism forms the backbone of our dynamic algorithm.
offline recursive framework that incrementally constructs feasible solution by
At each level, the algorithm maintains a candidate set and a partial solution. An element promoted to the next level only if its marginal contribution outweighs the cost of maintaining feasibility across the constituent matroids. Within each level, one element is sampled from the surviving candidates and added to the solution, while conflicting elements are removed. This yields layered recursive structure culminating in the final solution.
Our dynamic algorithm is inspired by the streaming algorithm Feldman, Karbasi, and Kazemi Feld required support efficient updates in fully
man al. [2018). but technical modifications dynamic setting. Our key idea is to simulate the behavior of the offline algorithm on an evolving ground set, while ensuring that the amortized update cost remains low.
Our algorithm incorporates randomized procedures. The first is initial sampling phase that reduces the input size and transforms a non-monotone problem into a more tractable monotone-like instance. The second is used during updates to guard against adversarially ordered insertions and deletions. When an element is inserted, it is retained with some probability. If retained, it is evaluated for inclusion in the current solution, and affected levels may be reconstructed. Similarly, deletions are handled by checking whether the element contributed to the current solution and selectively rebuilding the necessary components.
This design ensures that each update has low expected cost while maintaining near-optimal perfor- mance guarantees. A complete description of the algorithm appears in Section 4
3

---

1.1.2 Comparison with prior dynamic and streaming algorithms
Several dynamic and streaming algorithms exist for submodular maximization under various con- straints such as cardinality, matroid, and p-matchoid constraints. However, our algorithm differs in several key aspects that we summarize below:
Streaming vs. dynamic models. The algorithm by Feldman et al. Feldman et al. (0118) is specifically designed for the insertion-only streaming setting, and it cannot naturally handle deletions. In the streaming model, once an element is deleted, we must reassess all previously seen elements to find replacement-
typically requires (2()) oracle queries. In contrast, the dynamic model demands efficient handling of both insertions and delctions. Applying the streaming algorithm in dynamic setting would require reconstructing the solution from scratch after every deletion, resulting in linear query complexity per update, which is computationally prohibitive.
Matroid vs. p-matchoid constraints. p-matchoid constraints are a generalization of matroid constraints, which makes adapting existing algorithms more challenging. For example, the algorithm of Banihashem et al. [Banihashem et al. (2024) depends on a monotonicity property essential for performing binary search over levels. This property holds in matroids but not in general p-matchoids. Hence, their approach cannot be extended to p-matchoids.
To illustrate the failure of monotonicity in p-matchoids, consider the following counterexample.
Let V = [1. 2, 3) and define a 2-matchoid composed of two matroids. The first has ground set (1, and allows only one element, i.e., I (0. (1), (2)). The second has ground set (1,3) with I2 = (9. (1), (3)). Thus, the independent sets of the matchoid are I = (0. (1), (3..
Now consider an additive submodular function with f((3)) < f(1)) < f((2))100. Suppose A = (1) is selected at level 1. At level 2, adding element requires removing 1 (due to matroid 1), giving A = (2). Since 1 is now absent, we can include element 3 at level 3, resulting in A3 = (2.3). Thus, element can be added at level but not at level I due to conflict with 1, violating monotonicity assumptions. This shows the binary search technique used for matroids fails for p-matchoids.
Monotone vs. non-monotone functions. Our algorithm also handles non non-monotone submodular functions, unlike the method of Monemizadeh Monemizadeh [2020). which designed for monotone functions under cardinality constraints. Monemizadeh's 's algorithm samples O(E log n) elements to ensure a sufficiently good one is selected, whereas we require only a single sample due to our algorithmic structure and more refined analysis.
Cardinality vs. p-matchoid constraints. The algorithm by Banihashem et al. Banihashem et al. [2023 is specific to cardinality constraints and achieves an (8 approxxiimttoonnn for non-monotone submodular functions. Since cardinality is a special case of p-matchoid constraints, our algorithm generalizes their result while improving the approximation factor to (5.82 + +)..
2 Related work
Submodular maximization under cardinality constraint k in the dynamic model was first studied at NeurIPS'200 20 by Lattanzi, Mitrovic, Norouzi-Fart Tarnawski, and Zadimoghaddam Lattanzi LLatanzz et al.
[2020]. and independently by Monemizadeh Monemizadeh (2020]. Both papers demonstrated how to maintain a (2 + e)-approximate solution for this problem while having fast query time.
The amortized query complexity of the dynamic algorithm presented in Lattanzi et al. [2020] is O log'(k) (n)) in expectation. And the algorithm presented in Monemizadehi 2020 has an expected amortized 0k2 log'(n)) (n)) query complexity. Later, Chen and Peng Chen and Peng 2022 showed that developing a c-approximation dynamic algorithm for any c < requires an amortized query complexity polynomial in the size of the ground set V.
Recently, at ICML 2023, Duetting, Fusco, Lattanzi, Norouzi-Fard, and Zadimoghaddam Duetting et al. 2023] studied monotone submodular maximization under matroid constraint in the dynamic model and proposed a dynamic (4 + e) e)aaprooximation algorithm with an amortized expected query complexity of E log(k) log2(n) log'(5) ())). Simultaneously, Banihashem, Biabani, Goudarzi, Haji- aghayi, Jabbarzade, and Monemizadeh [annhaahem et al. [2024) tackled the same problem with the same approximation guarantee but with improved query complexity. Specifically, their algorithm achieves a worst-case expected query complexity of O(k log(k) log'( Additionally, the authors in Banihashem al. [024] improved the query complexity of the dynamic algorithm proposed in Monemizadeh 2020 for the cardinality constraint to expected O(ke- log)(K)).

---

All these results are for monotone submodular maximization problems. The only result for non- monotone submodular maximization within the dynamic setting recent result presented at NeurlPS'2. 23 by Banihashem, Biabani, Goudarzi, Hajiaghayi, Jabbarzad, and Monemizadeh [Bani- hashem et al. [2023] who presented a dynamic algorithm for non-monotone submodular maximization under the cardinality constraint k. This dynamic algorithm maintains a (8 + -)approoxm solution for cardinality constraint while having an expected amortized O(E22k² log' (k)) oracle queries per update.
Submodular maximization problems have also been studied in the streaming model. Badanidiyura, Mirzasoleiman, Karbasi, and Krause (Badanidiyuru et al. [014]] investigated monotone submodular maximization under cardinality constraint & and proposed an insertion-only streaming algorithm with a (2 + elaaproximation guarantee. Chekuri, Gupta, and Quanrud[Chekuri
Chekuri et al. (2015) presented O(p)-approximation single-pass streaming algorithm for maximizing non-monotone submodu- lar functions subject to p-matchoid constraints using O(k log k) space, Feldman, Karbasi, and Kazemi Feldman al. [2018) and Mirzasoleiman, Jegelka, and Krause Mirzasoleiman et al.) [2018) subsequently developed streaming algorithms with improved approximation guarantees for maxi- mizing non- monotone functions under p p-matchoid constraints. Specifically, the streaming algorithm in Feldman et al. [2018), which was an inspiration for our dynamic algorithm has the same approxi- mation guarantee of 4p + 2 ((1) as algorithm, and uses O(k) space and O(km/ p) query calls per element.
3 Models and definitions
Let V denote a ground set. A function f 2 R=00 termed submodular if it satisfies the inequality f(A U (ef) 105-flu f(A) 2 (e) for all A C ç V and e & B. For a subset A S V and an element marginal gain of adding e to A. If f satisfies (e) 2 f(A) for all choices of A and e, meaning that all marginal gains are non-negative, we refer to f as monotone. Conversely, we refer to f as non-monotone if the marginal gain of adding an element to a subset is not necessarily non-negative; that is, there could be a subset A and an element e & A such that f'A e) < S(A).
V. the difference A(e(A) ee)+e) f(A commonly referred to as the
Matroids and p-matchoids. A matroid M(V, I) is defined by ground set V and a nonempty downward-close set system I S 2", where I consists of independent sets. It satisfies the exchange axiom: for any pair of independent sets A, B with |A| < [B], there exists an element x e A such that U (x) I. Any subset of the ground set ' that is not independent is labeled as dependent. A maximal independent set, which becomes dependent upon the addition of any other element, is known as basis for the matroid M(V.I). Conversely, circuit in matroid M(V.I) is minimal dependent subset of V, meaning dependent set whose proper subsets are all independent. Given subset A of V, the rank of A, denoted as rank(A), represents the maximum cardinality of an independent subset within A.
An p-matchoid M(V. D) consists of m matroids that each element in the ground set V appears in the ground sets of at most p of these matroids. The set I of independent sets is defined the collection of all subsets of VV whose projection onto any
Man
m: Im) such
ground set V, is an independent set in I, In other words, I {s c 2" y nV, E II].
classic example the 2-matchoid representing the classical matching problem. In this case, given an unweighted graph G(V, E), set M C E is matching of G if and only if every vertex E V is incident to at most one edge of M. We can define a 2-matchoid M(V.I) for with ground set V= = E as the edge set of G and independent set I representing all valid matchings in G. Specifically, for each vertex v. a matroid M,, is defined, where V, represents the edges in V incident to An edge set X C V is independent in M, if nV, 1. Thus, any edge set X C V is an independent set in the 2-matchoid M(V, (i.e,, X e I) if and only X is valid matching in G.
Definition 3.1 (p-matchoid submodular maximization), Consider a submodular function f:2VV R²0 (not necessarily monotone). The goal in p-matchoid submodular maximization or submodular maximization subject to the p-matchoid constraint M(V, I) is to find an independent set I' e I that maximizes f())). In other words, if we denote the maximum submodular value of an independent
For a set A and an element we may represent the union of sets A and (c) as A + or A Ue for convenience. Similarly, when considering set with element e A, we may denote A (el as A or A le.
5

---

set in I as OPT = max f(),, then I' E I is an independent set that achieves the optimal value f(r) = OPT.
Oracle queries. We assume that the access matchoid M(V,I) is through an oracle that answers the following types of queries.
Submodular value oracle:
The oracle provides access submodular function f: = R allowing retrieval of the value f(A) for any subset A c V. In this query access model, computing the marginal gain f(A U (e]) f(A) is achieved through two queries: f(A U (e))
and f(A), where A C V and e EV..
Matroid independence oracle: The oracle allows access matroid II) of a p-matchoid I). For any subset 5 S V, the oracle answers whether S is an independent in matroid M(VV,, if it dependent. In other words, it determines if 5 E I,
We assess the time complexity of an algorithm that (approximately) solves p-matchoid submodular maximization in terms of its query complexity, defined the number of queries made to either the submodular value oracle for f or the matroid independence oracle for I.
Dynamic Model. Consider a sequence S comprising insertions and deletions of elements from an underlying ground set V. Let S, denote the sequence of the first updates (insertions deletions) from S. The term time refers to the moment after the first updates of the sequence S have been executed. We define V, the set of elements that have been inserted until time but have not been deleted since their latest insertion.
In dynamic p-matchoid submodular maxinization, our goal is to have approximate solution of OPT, maxi,gV:ter f(1,) at any time t. We use the term dynamic a-approximate algorithm to refer such an algorithm whose output solution every timestep guaranteed have function value that is at least a=1 OPT,
The performance of dynamic algorithms is evaluated based their update time, which measures the computational effort required to maintain a feasible solution between two consecutive updates. Accordingly, the query complexity of dynamic a-approximate algorithm for p-matchoid submodular maximization denotes the number of oracle queries (value or independence) required to compute an independent set whose submodular value is an a-approximation of OPT,, given all computations performed up to time / 1. 1.
Our dynamic algorithm operates within the oblivious udversarial model Carter and Wegman 1977 In this model, the adversary determines the elements in the set V and their arrival order. However, the adversary remains unaware of the random bits used in the algorithm and, therefore, cannot adaptively choose updates in response to the algorithm's 's randomly guided choices. It is assumed that the adversary prepares the complete input sequence (of insertions and deletions) before the algorithm starts running.
4 Offline and Dynamic algorithms for p-matchoid
First, we explain offline method provided in Algorithm [ [hat given a ground set V. computes approximate solution for submodular maximization subject to p-matchoid constraints. This algorithm fully executed by invoking the INI((V) procedure, which solves the problem in the offline scenario or acts as pre-processing step in the dynamic scenario, in which case V may be either empty or not. Then, show how handle the insertion and deletion of elements in Algorithm 2 Note that throughout the paper, we assume access to a parameter MAX that approximates the maximum submodular value up factor of 2: formally, max,e f(v) s MAX < 2 max f(v). This is standard assumption, which we show how to lift by maintaining parallel runs in Appendix B
4.1 Offline algorithm
In the beginning, our offline algorithm employs random sampling procedure named RATESAMPLING that intuitively transforms a non-monotone submodular maximization instance into monotone one. Once the initial sampling is complete, the algorithm uses a recursive procedure to refine solution from the remaining elements different levels. At any level i, we maintain two sets A, and B, The set B, is the set of every element E B whose marginal gain in case of addition to Ai-1 is large enough

---

Algorithm MATCHONDCONSTRUCCION
Procedure INIT(V):
Procedure EXTENSION(A-I,e))
Ao 0, and Bo RATESAMPLING(V)
1: Set weight w(e)) t A(eiAAi11)
2: Return RECURSION(Ao. Bo)
2: A, - Ai-1- -,,()) +
Procedure AAPENNAMLLIG
3: Return A;
1: Sample each element
i.id with proba-
Procedure I)
bility q = (p+ vp² + p 1)-1
1: U,(e) + DDEENENCIDEIITIINAA...
2: Return sampled set By in Step
c V1+1
Procedure RECURSION(A;-1, B:-1):
3: max (11 + c) w(U((e)), sMAN 2
1: B; FULTERINGAA-1.. B(-1)
4: if A(elAi-1) 2 then
2: if [B:] > then
5: Return Ui(e)
3: Sample element e, E B, uniformly
6: else
random
7: Return FAIL
4: A; EXTENSION(AA ei)
5: Return RECURSION(A, B,)
Procedure DPEENENCYDETEECIONALL..
6: Let -i-1
7: Return Ar
1: U((e) + 0
Procedure FILTERING(A,-I B,-1)
2: for j= do
3:
if (A,1 + ne)n NV, & EI, then
1: B;
4:
X, (c' A x arg min,ex, w(e')
2: for every element E Bj-1 do
5:
3: U,(e) FINDSWAPS(A--I,e))
6:
Uí(e) U.(e) +
4: store U,(e) for element as may be used
7:
Return U:(e)
later in Procedure EXTENSION
5: if (e) # FAIL then
6: B, B; Ue
7:
Return B;
to offset the loss of the elements we would need to delete from A;-1 to preserve its independence, and the set A, is the solution computed at the first i levels. In the end, we denote the number last constructed level by i", and A, would be our final solution. This recursive procedure relies filtering process and a second sampling process designed to outmaneuver the adversary.
Initial sampling The first sampling process samples elements of V with probability 4 (p + 1)-1 E O(p=!) and discards elements that are not sampled. This simple sampling process is well-established Fahrbacc Fahrbach et al. [2019) Mirzasoleiman et al. [2018] Feldman et al. (2018) as technique to transform an instance non-monotone submodular maximization into monotone one. It even speeds up the algorithm as it reduces the number of elements process.
Algorithm 2 UPDATEOPERATIONS
Procedure INSERT(C):
Procedure DELETE(e):
1: With probability 1 1- a Ignore and return
1: for i <- to do if & B, then
2: Bo <- Bn +
2:
3: for i - to 1" do
3:
Return
4: U,(e) - FINDSWAPS(AA-1.)))
4:
B, < B,+B--e
5: if U,(e) FAIL then
5:
if = then
6: Return
6:
if [B,] > then
7: B; < Be
7:
Sample an element uniformly at random
8: With probability r; = IBI
C: +
8:
A; EXIENSION(A
A, EXTENSION(AL1.ee)
9:
Return RECURSION(A, B,)
3 Return RECURSION(A,, B,)
10:
Let i-i
11: Return AP

---

Filtering, The imputs to the filtering procedure at an arbitrary level are the sets A;-1 and B In this procedure. for each e E B we decide whether keep or filter this element this level based on its suitability for addition to A--1- Note that if is later selected for addition to A;-1, we fix its weight as w(e) = A(e Ai-1), where A(e A) == (e)) - f(A) denotes the marginal gain of with respect to A.
Adding e to Aμ-1 may violate its independency. To address this, we compute a set U/ of elements that would need to be removed to make it independent again. Formally, we start with empty set U, then for each matroid M,(V,, J) of p-matchoid M(V,I) for which (A₂11 + +e) nV $ J. we identify the element e' E A4-1 with minimum weight that (A,1 + e -e) V, E I and add e' to U,ee).
Once U,(e) is computed, we consider two cases: If the marginal gain of adding to A;11 is significant
enough to offset deleting Uz(e), specifically if A(e)A,-)) (1 V 1)) Eeet,e) w(e'), then will be added to a survivor set B,, which was initialized as an empty set at the beginning of this level. If this condition is not met, e gets filtered out.
Sampling and EXTENSION. At the end of the filtering step in level i, set B, is the set of survivors. We sample one of the survivors, say e; E B,, and obtain the new solution set A, = A;-1 + U,(e:). In addition, we set the weight of sampled element e, to w(e,) A(ej/A,-)).
Our sampling strategy is similar to that of Monemizadeh Monemizadeh 2020) who used a similar method for dynamic (monotone) submodular maximization under a cardinality constraint. However, in that work, he samples OEE log(n)) elements to guarantee that one of the sampled elements has marginal gain above a predetermined threshold. contrast, our sampling strategy requires sampling just one element, and our filtering guarantees that the marginal gain of this element is sufficiently large.
4.2 Insertion and deletion algorithms
Upon the insertion of an element e, we ignore e with probability 1 - and terminate the insertion algorithm. Otherwise (i.e., with probability q), we iterate through levels (I.....P") and check if we can add e to the survivor set B,. If this is the case, we then reconstruct levels i...., 1' with probability Bi
For deleting an element e, we iterate through levels (I,....;"). At each level we check e the element that has been sampled at level i. If this is the case, similar to the insertion algorithm, we reconstruct levels i". a recursive manner.
5 Analysis
In this section, provide a sketch of our analysis including some notations and definitions. The detailed proof's are provided in Appendix [
Survivors elements of set B; that are included in set B,. Formally, we define them as follows:
Definition 5.1 (Survivor). Let 1 s i 1" be level. We call an element e, survivor for level i if A(clA-1)) 2 (1+ VI+ f)) EeeUae) w(e').
In this definition, U,(e) denotes the set of dependent elements that must get removed from the independent set A;-1 that can be added to it. More precisely, for every matroid M,,VV,DD) in the matchoid M(V.T), if (A,1 + e) ny, & J, we define X, = (e' A, ((A,)) -é' e' + + +V) E I the set of elements whose removal would restore independence in matroid M,(') J,I,) after the addition of e. We then select the element xj = arg min w(e') with the smallest weight among those in X, and add it to Uf(e).
In the amalysis of our randomized algorithm, we denote the random variable itself as x for any variable x, and x represents its value during execution. The key random variables used in our analysis are as follows:
We denote e; as the random variable corresponding to the sampled element e; at level i.
B, represents the random variable corresponding the set B,.
8

---

The random variable i' corresponds to r", the index of the last non-empty level created.
We define C; (Cl...., 1,11 Bo.... Bo..... B₂) the random variable corresponding configura- tion C; = (e1.-.., e--,, Bo..... B2) up to level i.
When observing update at time r, it is crucial to differentiate between random variables e,, B,, I", and C and their respective values before and after the update. To this end, we employ the notations Y and Y to represent random variable and its value before time We continue denote them at the current time after the execution the update.
Y and Y to
We divide the analysis of the dynamic algorithm algorithm into several steps. We first define set of invariants and we show that we can maintain them in the course the dynamic algorithm. Having these invariants in hand, prove the approximation guarantee and the query complexity of the algorithm.
Step 1: Invariants. Initially, we introduce the following set of invariants.
1. Survivor: B; = (e E B A(dAA-1 (1+ /1 f) Everres w(e'll for all isisi +1.
2. Starter: B, RATESAMPLING(V) and Ao 0
3. Weight: For - iis,i,,, E B, and w(e,) = A(ejAA,-1)
4. Independent: For 1 s i A, A,1 + - U,(e)
5. Terminator: Br+1
6. Uniform invariant: P [ee = eli" 2 and C, = C,I 1 B,].
Step 2: Maintenance of invariants. Next, demonstrate the validity of the invariants at the end
of the execution of AuccHOnCCNSTRUUTTONN We also show that these invariants remain preserved following each insertion and deletion operation. Specifically, we establish the following lemmas.
Lemma 5.2. At the end of Algorithm MArcHondCONSTRUCTTON all invariants hold.
Lemma 5.3. If before the insertion or deletion of an element e, the invariants hold, then they also hold after the execution of INSERT(E) and DELETE(e), respectively.
Step 3: Query complexity, Subsequently, we establish bounds on the expected worst-case query complexity of both insertion and deletion operations. Formally, prove the following result.
Theorem 5.4. The expected query complexity of each insert/delete for all runs is 0 pk* (k)).
Step 4: Approximation guarantee. Finally, we demonstrate that, assuming the invariants hold, an independent set Ap of the matchoid M(Y, can be reported, with a submodular value approximating the optimal solution by (2p + /
(p( ( + +++)++)
Theorem 5.5. Suppose that the invariants hold in every run of UPDATEOPERATIONS. Let Ap be the independent set that Algorithm UPDAIEOPERATIONS returns. Then, the set Ar satisfies (2p + 2 Vplp 1)+1+8) f(A,) 2 OPT, where OPT maxrer f((").
Acknowledgements
The work is partially supported by DARPA QuICC, ONR MURI 2024 award Algorithms, Learning, and Game Theory, Army-Research Laboratory (ARL) grant 1911N2241002,, NSF AF:Small grants 2218678, 2114269, 2347322, and Royal Society grant 12/22212
References
A. Badanidiyura, B. Mirzasoleiman, A. Karbasi, and A. Krause. Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 67 1-60, 2014.
A. Badanidiyuru, A. Karbasi, E. Kazemi, and J. Vondrák, Submodular maximization through barrier functions. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in

---

Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 12, 2020. virtual. 2020. http:: h/tttced///proceeiings neurips. cc
Aabtsseeebbbbe--traatttttc...... Abstract html
R. Bairi, R. K. Iyer. G. Ramakrishnan, and J. A. Bilmes. Summarization of multi-document topic hierarchies using submodular mixtures. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference Natural Language Processing of the Asian Federation of Natural Language Processing, ACI. 2015, July 26-31, 2015, Beijing, China, Volume I: Long Papers, pages 553 533-563. The Association for Computer Linguisties, 2015. doi: 10.31 10.3115/V1/PPI 15/11//11555005 1054. URL httpht:/p//oo.ooo 011.11.1100111111115//// 1/pp15-1054
K. Banihashem, I.. Biabani, Goudarzi, M. Hajiaghayi, Jabbarzade, and M. Monemizadeh. Dy- namic non-monotone submodular maximization. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL http::/pppper..nnppss..t.p cc/pppp httpsssssaaaapee..l//aaaaaaa files/paper/ 2023/hash/
html
K. Banihashem, L. Biabani, S. Goudarzi, M. Hajiaghayi, P. Jabbarzade, and M. Monemizadeh. Dynamic algorithms for matroid submodular maximization. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pages 3485-3533, SIAM, 2024.
N. Buchbinder, M. Feldman, Naor, and R. Schwartz. Submodular maximization with cardinality constraints. In C. Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, Jamuary 5-7, 2014, pages 1433- 1452. SIAM, 2014. ISBN https://doi. org/10. 10. 01117/11.97861199774499999 106
197-338-. doi: 10.11377).988861119340....
URL
L. Carter and M. N. Wegman. Universal classes of hash functions (extended abstract). In Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 106-112, 1977. doi: 10.1 10/1/4/000005. 1804400000 URL https://doi. org/ 1145/
800 105. 803400
C. Chekuri, S. Gupta, and K. Quanrud. Streaming algorithms for submodular function maxi- mization. In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Au- tomata, Languages, and Programming 42nd International Colloquium, ICALP 2015, Ky- oto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Com- puter Science, pages 318-330. Springer. 2015. doi: https://doi.org 10. 1007 3-66--77777--226
URL
X. Chen and B. Peng. On the complexity of dynamic submodular maximization. In Proceedings of the Fifty-Fourth Annual ACM on Symposium on Theory of Computing, STOC 2022, to appear, 2022.
/tttts:://rxxx http://axxvvvvvo orgg abs/2111. 63198
S. Cui, K. Han, T. Zhu, J. Tang, B. Wu, and H. Huang. Randomized algorithms for submodular function maximization with a k-system constraint. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2222-2232. PMLR, 2021. URL http://proceeddngg mlr.
wtw.roeeeinnssm....rresss/////// ppress/v19//ci22
html
A. Das and D. Kempe. Algorithms for subset selection in linear regression. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 45-54. ACM, 2008. doi: N0.1145/1374376.1374888 URL https //doi.org// /10.01.11111111.
Duetting, F. Fusco, Lattanzi, A. Norouzi-Fard, and M. Zadimoghaddam. Fully dynamic submodular maximization over matroids. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 8821-8835. PMIRR 2023. http: http:tppps/pprcceeingg.... mlr. press//22/// duetting23a, html
10

---

E. R. Elenberg. R. Khanna, A. G. Dimakis, and S. N. Negahban. Restricted strong convexity implies weak submodularity. CoRR, abs/1612.000004, 2016. URL htttp://axii..rr/ /bs/ 1612.00804 00804
M. Fahrbach, V. S. Mirrokni, and M. Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In 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 1883-1844 PMLR, 2019. URL
http://proceedings itrpiig..mm............ /eves//v97// heap.prress////faaaaaclalla wawhbacchh9..htma
U. Feige, V. S. Mirrokni, and J. Vondrák. Maximizing non-monotone submodular functions. SIAM J. Comput., 40(():1133-11) 2011. doi: 10.1137/090779346. URL httptt:///o.i.ooo http:///oooor//////// 1137/ 090779346
M. Feldman, A. Karbasi, and F. Kazemi. Do less, get more: Streaming submodular maximization with subsampling. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 740, 2018. URL http:///rroeednnn...ii...pp 2018
wat.aa/asesseeeeaaaaaaaatt...... www.tbasstt...... html
T. Friedrich, A. Göbel, F. Neumann, F. Quinzan, and R. Rothenberger. Greedy maximization of functions with bounded curvature under partition matroid constraints. In The Thirty- AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February URL
1, 2019, pages 2272-2279, AAAI Press, 2019. doi: 10. 1609/AAALVV31101300002222 https://doi orgooogg///1 10. 1609/ aaai. www.01.33.1333. 33012277
Y. Gu, C. Bian, and C. Qian. Submodular maximization under the intersection of matroid and knapsack constraints. In B. Williams, Y. Chen, and Neville, editors, Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 3959-3967. AAAI Press, 2023. doi: 2.1609/AAAA.33314.2555
URL BtRLshtts:://ott //ooi. org/ 16. 1609/aaai. v...3..1....... http://aaa..331..5555555.3 25510
C. Harshaw, E. Kazemi, M. Feldman, and A. Karbasi. The power of subsampling in submodular maximization. Math. Oper. Res., (7(2))3365 1393, 2022. doi: 10. 10.1287/M00R.2021.177 URL
https://doi.ogg/// 10. 1287 /moorm 2021 1172
T. Jin, Y. Yang, R. Yang, J. Shi, K. Huang, and X. Xiao. Unconstrained submodular maximization with modular costs: Tight approximation and application to profit maximization. Proc. VLDB Endow., 14610)) 2021. doi: 10. 10.14778/3467861 34667666..6 http://:://war vldb org orggpp/lch/vo114//1755 jin.pdf
E. Kazemi, M. Mitrovic, M. Zadimoghaddam, S. Lattanzi, and A. Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3311-3320. PMLR, 2019. URL URL. mlr. wwwpprssvvvii /tt///azeemiiaaa 19a. html
D. Kempe, J. M. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. L. Getoor, T. E. Senator, M. Domingos, and C. Faloutsos, editors, Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24- 27, 2003, pages 137-146. ACM, 2003. doi: 10.1145/956750. 956769. URL https:///oi. org/ 10. 11451145//00 956750. 956769
R. Khanna, E. R. Elenberg, A. G. Dimakis, S. N. Negahban, and J. Ghosh. Scalable greedy feature selection via weak submodularity. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine I Learning Research, pages 1560-1568. PMLR, 2017. URL http:/ http://proceedings. mlr. www...press.S.... wwtp//////aaaaaaaaaaaaaa. html
11

---

S. Lattanzi, S. Mitrovic, A. Norouzi-Fard J. Tarnawski, and M. Zadimoghaddam. Fully dynamic algorithm for constrained submodular optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https: pettp::/proceedinss.eeeee www.iig.nneiiii..com wwtpeeps....pappee/////eppccc wwtpcc/pppppe/////// 2aap//a222/h/hhha
11116044332966fff33///eeeee3333 oasp://ccccccceeeeeeaaaaaaaareta Abstract.html
H. Lin and J. A. Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, June 2-4, 2010, Los Angeles, Califormia. USA, pages 912-920. The Association for Computational Linguistics, 2010. URL https:// aclanthology org N010-1101111 1
H. Lin and J. A. Bilmes. class of submodular functions for document summarization. In D. Lin, Y. Matsumoto, and R. Mihalcea, editors. The 49th Annual Meeting of the Association for Compula- tional Linguistics: Human Language Technologies, Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon, USA. pages 510-520. The Association for Computer Linguisties, 2011. URL httph:ttp////t. aclweb. org/ htt////oooooogo111//2/22
S. Liu, Lu, C. Chen, and K. Tang. Efficient combinatorial optimization for word-level adversarial textual attack. IEEE ACM Trans. Audio Speech Lang. Process., 30:98- 111, 2022. doi: 10.1109/ MASL...021.3110092
https:/s:://do org/10g..100 0tgg100.109/TTA.. 1109/TASLP 2021 3130970
Y. Liu, K. Wei, K. Kirchhoff, Y. Song, and J. A. Bilmes. Submodular feature selection for high- dimensional acoustic score spaces. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2013, Vancouver, BC, Canada, May 26-31, 2013, pages 7184-7188. IEEE, 2013, doi: 10. (0.1109//CASSP2211336663 2013. 6639057
URL https:/::/// org/ 10. 1169/ICASSI
B. Mirzasoleiman, S. Jegelka, and A. Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In S. A. Mellraith and K. Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018 pages 1379-1386. AAAI Press, 2018. URL wttphhtpp:///// aaai. org/ocs/ index
17014
M. Monemizadeh. Dynamic submodular maximization. In H. Larochelle, M. Ranzato, R. Had- sell, M. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, Decem- ber 6-12, 2020, virtual, 2020. URL 12eeeff22lhbbbh Abstract httml
httpooceednng...urrisssp/pppappp /
45bd8-1e224bb23331144440000 2eb
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I. Math. Program. 14(1):265-294, 1978. doi: 10.1007/BF01158891. URL ht org/10 1007/BF01588971
S. Qian and Y. Singer. Fast parallel algorithms for statistical subset selection problems. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
F. Quinzan, V. Doskoc, A. Göbel, and T. Friedrich. Adaptive sampling for fast constrained maximiza- tion of submodular functions. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 964-972. PMLR, 2021. URL http://proceeddngg/ mlr press/ pipess/v1300 1110/ http///1////q/aiuaee qttp/uuiiinnnin 1a. html
Quinzan, R. Khanna, M. Hershcovitch, S. Cohen, D. G. Waddington, T. Friedrich, and M. W. Mahoney. Fast feature selection with faimess constraints. In F. J. R. Ruiz, J. G. Dy, and J. van de Meent, editors, International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain, volume 206 of Proceedings of Machine Learning Research, pages 7800-7823, PMLR, 2023. URI.httss http:/ttt///proceinngss... mlr. mls.seessss...266 quinzan2 2a..2aa.. html
12

---

S. Tschiatschek, A. Sahin, and A. Krause, Differentiable submodular maximization. In J. Lang. editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 2731 -7338. ijcai. 2018. doi:
101249971 URL h0tppp///oooloorg10002/6//66///6 /
K. Wei, R. K. Iyer, and J. A. Bilmes. Submodularity in data subset selection and active learning. In F. R. Bach and D. M. Blei, editors, Proceedings of the 32nd International Conference Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 JMLR Workshop and Conference Proceedings, pages 1954-1963. JMLR.org, 2015. URL httpht//p//oceeeiigg... mmr
press/v3 wwwlw.wi11....... html
G. Zhang, N. Tatti, and A. Gionis. Ranking with submodular functions on the fly. S. Shekhar, Z. Zhou, Y. Chiang, and G. Stiglic, editors, Proceedings the 2023 SIAM International Conference on Data Mining, SDM 2023, Minneapolis-Sr Paul Twin Cities, MN, USA, April 27-29, 2023, pages 604 612. SIAM, 2023, doi: 10111377.97311111766666666 URL https://doi. org 10
1133/L.9731611177633.ccb
13

---

A Omitted proofs
We begin proving the main theorem of our paper by first introducing basic probabilistic terminology.
Conditional expectation. For a function x and set A, we denote x[A] as the function x restricted to the domain A. For an event E, we define [E] the indicator function of E, i.e., 1 [E] is set to one if E holds and zero otherwise. When dealing with random variables and their values, we use bold and non-bold letters, respectively. For instance, random variable is denoted X. and its value is represented by X. We use the notations P [X] and E [X] for the probability and expectation of a random variable X. For events and B. the notation [A|B] denotes "the conditional probability of A given B" or "the probability of A under the condition B". For an event A with nonzero probability and a discrete random variable X. we denote by E [X]A] the conditional expectation of X given A. i.c., E [X[A] = ,x x P [X- x|A]. Similarly, for discrete random variables X and Y, the conditional expectation of X given Y is denoted by E [X y]
A.1 Maintenance of survivor invariant
We first prove that the survivor invariant holds at the end of the algorithm MArcHoinCoNSTRUCTINN Later, we show that it holds after the execution of INSERT(e) and DELETE(E) provided it was upheld before the insertion or deletion of an element e. We employ a similar methodology to demonstrate the preservation of the remaining invariants. In particular, we first prove them for the algorithm MATCHOnCCNNSTRICCINNNnd then for INSERT(e) and DELETF(E).
Survivor invariant for MarchonnCoSSTRUCOOXXCC holds for any element e and any level i < i". For the base case i = O, if any arbitrary element e E V is sampled with probability q. element will be in Bo. Otherwise, it will not be added to B
We inductively prove that survivor invariant
Now, let consider arbitrary element that is in survivor set B of a level i i- 1 where 1 & i < r'. Recall that U,(e) is the set of dependent elements that needs to be deleted from independent set A,-1 so that can be added to it. In the algorithm FUTERING, we check if A(elA,1))
(1+ / 1)- Ereu.ite w(e'). If that is the case, is added to B,, otherwise, is not added to B,. Thus, the survivor invariant holds.
Survivor invariant for INSERT(e): We first give a few useful facts and for that, define variables and as follows.
* Let s be the largest i E [0, + 1] such that e is added to B7.
* If there is a level i e [i"]] in which We consider two cases.
then we let r be i. Otherwise, we let r be i"- + 1.
Case happens if r S T" Then, we know that Subroutines EXTENSION and RECURSION have been invoked. In addition, we have e, e and x
Case 2 occurs r j"- I which means Subroutines EXTENSION and RECURSION have never been invoked for INSERT(e). Thus, the last level i" after inserting e is the same last level /" before inserting That is, 1" 1"- Note that, must have since otherwise, we have [B - = 0 and [Br+1l = 1. Therefore, we have invoked Subroutines EXTENSION and RECURSION for this level what means i' > i"- which is not the case. Thus, 8 <===== 2" + 1.
i"- 1,
We handle INSERT(V). Therefore, for any i < r. we have not made any change in variables e7, w(e)), or A because we have not invoked Subroutines EXTENSION and REcURSION for those levels upon insertion of e. Hence, the following facts are correct.
Fact A.I. For any E [1,r) we have: e, = e, A = A,
w(e,) w (e;) 3 A = A, For i 0, we have
By the definition of s, we add e to the set B, for each i [0, s] and we have S r. In addition, by invoking Subroutines EXTENSION and REcURSION for level r + 1, nothing happens to the variables in levels that are less than + 1. Thus, we obtain the following fact.
Fact A.2. For any i E [1, s], we have B; = B + e. Fact A.3. For any i E [s + 1,7], we have B, = B
14

---

A7 = A
A A
A =
Ar + Ar
oo m0
6 02
4 = =t-1
9,
6: =
B B
+
B2= Bj t
B, B7 1
Levels
2
r
Case inserting an element
A7
A7 = Ag
45 Ar-
-1 61
6 02
6
= B7 +
Bi m Bj 4
Th
D3
R, m B, 4
B2 Rg
Levels
0
1
2
Case of inserting an element e
Figure 1: Visualisation of two cases upon INSERT(e).
Next, show that the survivor invariant holds, i..,, B, le B MelA--) (1 vI+ + Eeevie) w(e')) for i E [1,2].
First, let us consider i E [1, s]. By the assumption, the survivor invariant holds before the the insertion of element at time t. That is, B, le B A(elAT,) 2 (1 + V ()) Ee'ettee wTee)) for
i E []. Using Fact A.2 B = B, v holds for all s]. Thus,
| ).
B; = +v= (eE M (1+ v
w (e()) +v
P deUiie)
le UM) MdA (1
|
w w((e)) Σ
p
e'eUiee)
According to Fact A.I for any e [1, s] C (1,r) we have: Therefore, obtain The following:
el e
w(e)) = w (e))
0 A7
I |+ -+
Σ w(e')) e'eU.te
B; = B. vv= (e B 2le +1+
Recall that if Case occurs, r == Since in this case, Subroutines EXTENSION and RECURSION have been invoked, we know that the survivor invariant will be held for all level [s + 1, However, if Case happens, we need to prove that the survivor invariant is held for all levels [s + 1,2"].
Thus, we are in Case 2 and we need prove the survivor invariant for all levels [s 1,7"]. We have =1= + 1. According to Fact A.3 for any i E [s + 1, 1], we have B, B7.
1 -)
Σ w w"(e)) e'EU,()
B, = B, = (e B A(eAA 2 +1+ 1
P
15

---

Once again, using Fact A.1 for any i e [1, we have: what means
ei
w(e)) w (e,))
A A,
B, lee B A(elA-1) +1+ V -
Σ w(e'))
p ctEUxte
This essentially means that the survivor invariant holds after INSERT(e).
Survivor invariant for DElETR(e): Similar INSERT(e), We first define variables and s follows.
* Let s be the largest i E [0,7"* + 1] from which is deleted from By.
& If there is level [1,7" in which e; e, then let be Otherwise, let be i"- 1.
We consider two cases.
Case happens if /" Then, we know that Subroutines EXTENSION and RECURSION have been invoked. addition, we have e, e and s
Case 2 occurs if 1"~ which means Subroutines EXTENSION and REcURSION have never been invoked for INSERT(E). Thus, the last level i" after deleting is the same last level 1*' before deleting That is, r" Note that, must have < 1"- 1, since otherwise, we have |8, +11 = which cannot be the case.
Our update is DELETE(P). Thus, in any level i [1, we do not make any change in in these levels other than removing the element e from By if S s. Fact A.4. For any E [1, have: e; = e, w(e;) w (e:) 3 A; = A7- For i we have
A, = A7. Fact A.S. For any ie [0, s]. it holds that B, (vv) and for any e 1, we have B By the assumption, the survivor invariant holds before the the deletion of element at time r. That is,
B, = le E 1 A(eAA 2 (1 + Erethe w (e')) for E [1, Thus, using Fact A.5 for
ie [1,s]
B B le Met : +1+ V
|+-).
Σ w (e')) e'Et((e)
and for i E [,r1,r]
1 J Σ
B B fe = B ((M 21 +1+
w((e))
P c'E((ee)
Since by Fact A.4 for any i (1,r) we have e =
w(e)) w (e))
A, = A7, we conclude
that
B; = B.Me = le B ACeA +1+ / ; Σ w(e') d'EUite)
what proves that the survivor invariant holds for i () after the deletion of element Recall that r I 7", Subroutines ExtensioN and RECURSION have been invoked, therefore, we know that the survivor invariant will be held for all levels [r, (r.
A.2 Maintenance starter invariant
Starter invariant for INsERr(e): Recall that in Subroutine RATESAMPLING(1V, we sample each element e E V i.id with probability = (p + vp² + + 1)- and let Bo be the set of elements that are sampled. By our assumption, we have By RATESAMPLING(( and Aj = 0.
Upon insertion of an element e, we add it to Bj with probability q. Observe that we always add to the ground set. Thus, V - +e Condition of this event which happens with probability we have Bg B5 + e. Thus, Bo RATESAMPLING(( + = RATESAMII AMPPLNA))))())) addition, using we have Ag Aj 0.
Fact A.I
16

---

Starter invariant for DELETE(E): By our assumption, we have B = - and A = 0. Moreover, V, = V. Me). If E B (what happens with probability q), we then remove from B That is, BD = B Me) RATESAMPING(V
= MATESAMPLING((11 Using Fact A; A = 0.
This proves that the starter invariant holds after insertion or deletion of an arbitrary element e.
A.3 Maintenance of independent invariant
We assume that the independent invariant holds until time r. That is, for any level 1 s i S i", A, = A e ). Upon the insertion or deletion of an arbitrary element at time we show that A, A,1 + Ú,())) for any level S iiso 1".
Remarkably, we can establish this invariant for both insertions and delctions simultancously, without the need for separate consideration of each operation. Indeed, according to Facts A.1 and A.4 upon the insertion or deletion of an arbitrary element e at time 1, for any E [1, r) we have =
w(e,) = w (e:) A = A, and for O, we have A; = A7- Thus, A; = A A + U,ee))
Now, observe that for any j i- 1< <r we have ej = w(e (e) @ イ A and for j = O, we have A -- This essentially means that A; = A + + U,(e,) for any level i s is i'. Also, recall that if r I i"= Subroutines EXTENSION and RECURSION have been invoked, therefore, we know that the independent invariant will be held for all levels [r,
A.4 Maintenance of weight invariant
Next, we show that the weight invariant holds. That is, assuming that for 1 isiii" E B and w (e,)) Me, 1)) We show that upon the insertion or deletion of an arbitrary element e at time t, e, E B, and w(e;) = A(e:A;-1) for ii
Weight invariant for (e): According to Fact A.2 for any i e [1, s]. we have B; = B, + e and for any i E [s + r, we have B; = Bī using Fact A.3 Thus, Bj S B,.
Using Fact A.1 for any i r) we have have A;
A; A,. For i 0, we Therefore, = e, Bj S B; for any iE [1, This essentially means that E B,
e; e
@ w(e,) = w (e,)
Next we need show w(e;)= --)(A;11)
[(A11 + e;) f(A,-). For any i (1,r), have w (e,) = n (e7). Moreover, the assumption of this lemma implies that w (e, = Ale, (N = f(A=, +
w(e,) = w (e,) and e; - Then, w
- Since e; = e, we obtain f(A + + f(A
f(A + e2) f(A.-)). Putting everything together, for any iE [1, r) we have
m(e)) = w (e)) = w (e,e ((,1 + s(A))) = [(A + ei) M(elA)))))MelAAA))))
Weight invariant for DELETE(E): We next prove that the weight invariant holds upon deletion of an element at time f. According to Fact A.4 for any ie [l. we have O =e; @ w(e,) w (ei) @ A, A,. In addition, for i O, we have A, = A, From the definition of r we know that e, E R, We).
Using Fact A.5 for any E [0, s]. it holds that B, B, (v) and for any i [s I, we have B, B
Therefore, B B, Mul which means that e; e E B, Mell = B,.
By the assumption, we have w (eT Ale Aee -= we have w(e,) = w (e,) w (e7) = f(A + -
f
((A)) Thus, for any ie (1, ʃ(A + +e) f(A,1) = A()
which completes the proof that the weight invariant holds upon deletion of an element at time
A.5 Maintemance of terminator invariant
Next, we prove that the terminator invariant holds. That is, upon the insertion or deletion of an arbitrary element e at time f, we have Br+1 0 assuming that B 0 holds.
By the definition of r, if r r i"- we know that is the level where e, upon insertion or deletion of an element at time 1, we know that Subroutines EXTENSION and RECURSION have been invoked. In addition, we have = If this happens, RecuRsioNsubrouttne terminates when [B] > O. As the result, we have = which means that B = 0.
However, if r p- + 1, we know that Subroutines EXTENSION and RECURSION have never been invoked for (NSERT(e) and DELETE(e). Thus, the last level i' after inserting is the same last level i" before inserting That is, i"- Note that, we must have # i"- + 1, since otherwise, we have |B= - = 0 and |1 Therefore, we have invoked Subroutines ExtensioN and RECURSION for this level what means i' f"- which is not the case. Thus, < i"- + 1 which means Br+1 B 0.
17

---

A.6 Maintenance of uniform invariant
We now prove that the uniform invariant holds. That is, for any i 2 1" we have P(e, = eji' 2 and C Cj] = | 1 B.]. Consider the time when the element e, is sampled. At this time, all of the random values in C, are realized. By construction, e; is sampled uniformly at random from Bj. Therefore, at this time the claim holds. Additionally, none of the values in C are changed afterwards the execution. Therefore, the claim holds the end of the execution well.
In this section, we prove the uniform invariant, i.e. we show that for any i I i' we have P(e, = eji" 2 and C C.1 Bi [e E B,]. We first that the invariant holds after calling INIT because we sample e; be uniformly random from B, and none of the value of C are changed after this sampling. The main thing to prove is that the invariant holds after each insertion and deletion operation.
Assume that the invariant holds before some update which is either the insertion or deletion of an element v. we will prove that it holds after the update as well. We use the superscript denote values before the update, e.g.: ej denotes the value of e; before the update. When no superscript is used, we are referring to values after the update. By assumption, the invariant holds before the update,
ie., for any and e, and any C; such that P i 2 i, C = C. > 0 we have we have
P Ple
dir 2 C, = c BT11 B,
(1)
We need to show that after the update, for any arbitrary i and e, and any C; such that P[i 2 C, C,] > 0 we have
Ple. eli 2 i
1 BJ
Note that P(e, = efi 2 i, C, C.I. is only defined when P[i 2 C, = CJ O, which means that given the input and considering the behavior of our algorithm including its random choices, it is possible to reach a state where i' i and C, = C,.
A.6.1 Insertions
If v & Bo, then it means that the data structure has ignored which in turn implies that C, = C, and e, = c and = -- which means the claim follows from the induction assumption. Formally, the following claim holds.
Claim A.6. If & Bo, then events (i* 2 i,C, C₁) and (r- 2 CT C.-1. Bo] equivalent. Furthermore, the event implies that e; = e
Proof. The first direction of equivalency clear; we have (i' 2 i, = C2) then the algorithm has ignored because otherwise would have E BB By. Therefore, have i* i and C, C, For the other direction, since v g B, we know that the algorithm has ignored y which means that i* i' and C C, as before.
Since the event implies that the algorithm has ignored v, we have e, = e; for all i.
Given the above claim, for all C such that $ Bo.
P f = i 2 -, = Cj]
= e 1" 2 i, = = C-
= P e = = 2 C, C--l
[e B.).
B
Here, for the second equality we have used the fact that the realization of e, is independent of whether Bn. This is because the algorithm decides whether or not v E Bg by flipping a coin with probability q afte e, is realized.
We therefore focus on C, for which E By.
18

---

For any i, let P, denote the random variable that is 1 if we invoke RECURSION(A,, Bj) for some j j i, and equals 0 otherwise. We first show that
P(e 1 2 L. Pi, = 1]
1 B:]
[
This is because e, obtained by sampling uniformly at random from B; and at the time of the sampling, the values in C, are realized and they do not change afterwards.
We now consider the case where P, O. We claim that
1 P(e = i 2 i, C P-i = = [8]]
[e B,]
(3)
V & B,, then we have B, = B and e; Define 7 as C (Bo) .v)..... BA el...., eI,...,
Define the event
o= -= - B P, =0]
Claim A.7. For any C, such that P[r 2 C, C, P-1 0] > 0, the event or is equivalent to (i" 2 C, C, 0)
Proof. Assume that the said event holds. We first note that F 2 i; if this is not the case then P. = implies that 1*
well which not possible. Additionally, Pi-1 0 ensures that e, = for all j s and the only difference between B, and B is that the former may possibly contain v. Finally, we have E By given the assumption on C, made in the beginning of the proof. We note that since we assumed that [[" 2 C, P- 0] > this further means that P [o, C C, O.
must have C, C, because
For the converse, assume that holds. Since P:-1 0, have i' i We therefore need to show that C, = C, The values in eI...., C,1 are not changed so e; e, ej by definition of C₁- Additionally, the values of Bu.... B, are now deterministic because we have fixed the realization of the coin flips occurring with probability [ by assuming P,1 0, and have assumed
Bg. Therefore, there is only one possible value for C,. Therefore, either P PCC, C, o 0 or P[C: = C; or] = 1. We have already proved that [C, C, O, which means we must have P(C, = C; o]] finishing the proof.
Claim A.8. P [P. 0 o]
[[c
BB.1
which means that P, 0 if and only if the algorithm flips the coin in Line 2 invoke recursion. v & B,, then this cannot happen because Line 2 would never be executed. If v B,, then we note that this happens with probability [87 because of Line 2 Note that the time this line is executed, the values ff C.,, C..
Proof. If a holds then P-1
Combining the above claims we obtain
P(e = el 2 i, C, = C, P 0]
= PPee [r]
(Claim A.9
1 Bil
(1- 1 [ Bi]
Ple ( = 1]+ =1]+
Ple =el,=e
(Claim A.9imAA9)
|B|
BB
1 [ Bi]
B:]
1le v
Ple: = el =l
B/
where for the final equality have used the fact that if RECURSION(A, B,) is invoked (i.e., if 1), then we must have e; v. We next calculate P [e: = o, = 0J. We begin by observing that if P. 0, then must have e; e which means
P o. 0] P[e = e. 0].
(5)
Define the event o' o' = 1 CT. Bo), i.c., o' satisfies lo', PP O).
19

---

Clain A.9. Conditioned on the event (i- 2 i, C, c7 the events (v Bu. P, 0] and e, = e are independent.
Proof. In order have Bu and P, O, the insertion algorithm should not ignore and for all j such that we reach line 2 we need to flip the coin such that RECURSION is not invoked. The realization of e has no effect this. For Bu, the coint is always flipped with the same probability and for P. 0, if the coins are flipped, they are always flipped with the same probability [ or not the coin is flipped (i.e., Line executed) depends only the value of B, and A j-1, neither of which are affected by the realization of e,.
and whether
Given the above claim,
P j P. 0]
= P(c e /- 2 i, C, - P, 0
(Definition of o))
=Ple = = 7- 2
(Claim A.9
[ee B;
(Induction assumption T
|8
[e E [MHl
(Definition of B,)
|A [v}]
Combined with Equation and Equation (5) this gives
P Plc = el 2,, C.
[iv B,
1 e (A 1 [vve B,]
B,1
B;
|BA [v]
We therefore need to show that the above expression is the same as HeeBRl however using a case by case analysis. If v & B, then the first term vanishes and the second term becomes [[c8]] as required. If v E B, then the expression can be rewritten as [
This easy to check
TB
1 [e = vl
B 11 E BA (v]l
fl==ef22i0 X, 0] =
B
|B
|B|1-1
1 1ee v]
1 E BA]r]]
B
|Bil
Depending on whether # v or e = v, either the first term (respectively) the second term disappears
and the other term equals [&] This proves Equation (5) which combined with Equation 4 the proof.
finishes
A.6.2 Deletion
For any i, let P, denote the random variable that is 1 if we invoke RECURSION(A,, B)) for some j s i, and equals 0 otherwise. We first claim that
P = i 2 C, - 1]=
-le B,]
(6)
[B]]
As in the case of insertion, this is because is obtained by sampling uniformly at random from B and at the time of the sampling, the values in C, are realized and they do change afterwards.
We next show that
Ple: = C, 0]=
[B] l B,]
We start by evaluating the left hand side. We first claim that the event (i' i, C, P; 0) implies the event 1 í. This is because if i < i, then P, O means that RECURSION is not invoked by deletion, which in turn means that i' i- contradicting the assumption 2 Since i-- 2 the value of C, is defined. We condition on the value of C,. Formally.
Fle = l 2 i, C, P. = 0] Bc, [P
2, C, 0, 0.C; = C,
(8)
20

---

where in the above expectation, the value of C is sampled from the distribution of C, condi- tioned on li' 2 i. C, = C. P: = 0). We note that all the values considered in the expectation satisfy p| 2 i, = C, P, = 0. C, = -7 >0. O.
=
Consider some C such that P. [ 2 = C 0. C; = c We claim that rewrite the event (rr 2 i, = C, P; = 0, C = C7) is equivalent 11- 2 i, C, Cj P. 0/. It is clear that the first event implies the second event. As for the other direction, we note that the realization of C, fully determitte the realization of C₁; specifically, since P. = 0 we have B, = BB (v) for all j S and
e, =ej for all i. Therefore, Pli 2 i, C, C, P, 0 i' 2 i, C, Ci is either 0 or 1. We know that it cannot be O however because by assumption, P i' 2 i, C, = C, = 0. C7 c7] O. Therefore, it must be which means C, G. Finally, since P. 0 we have i" = 1- We note that P, = 0 itself implies that e; q, Therefore, we can rewrite the probability inside the expectation in Equation (8) as
P F = i' 2 C = P. = c7
= P =e -e 10 2,C = P. C.
P = 00 0 =,, -. c. = = 2 ci
(Bayes' Rule)
P 01 p- C, =
We first claim that v # ej for all j < i. This is because v = ej for some j < i, then because the deletion of v (which is e would invoke RECURSION.
P By assumption however, we only considered values of C, for which P C C,, P, = 0 > in the expectation in Equation
P - i 0 = 77
Given this, we have P, = 0 if and only if v # eT. It follows that
1 1/ve e B,
P = 0 10000-22..0 2.C = C, = Ple # # 2
B7
and
P [ = 0 -,,-- 2 i, C, = P * vvle = =,, 2 =
1 le # vl.
By induction hypothesis (Equation
1 | Ple = 2 i, C. c]
B
Putting all together we obtain
1 Ilee
E B.
1l le + v]
=e==llae
1 [EE
B
B.
If v E B,. then we have B, = B, and the above expression turns into
1l le E B, le # v]
1 [e e B:]
|B
|B,
where for the equality we have used the fact that if B, must have # v since & B, If v B, then the above expression becomes
1 [e U # v]
1 1 B.]
(I (IB|+1)((1 18/11]
[B,
where for the equality we have used the fact that e (v] and e is equivalent to E B, rewrite the numerator and simplified (1 B; + 1) [8|11 to
B B,
(I 1)
[B + [
to rewrite the denominator. We have therefore proved Equation 7 which finishes the proof together with Equation (
21

---

A.7 Query complexity
To analyze the query complexity of this algorithm, we first prove that checking if an element can be added to level requires O(p- log(k)) oracle queries due to Lemma A.I0 Consequently, the FILTERING algorithm requires O( p log(k)) queries to operate on level
Therefore, running RECURSION on level requires O(i" |B:1- p log(k)) oracle calls construct levels i,i+ I.....''. Given the uniform invariant, in each update, we reconstruct at level i with probability 1/B, Thus, the expected number of oracle calls for reconstructing at level i is O(i p plog(k))
Summing this up for all levels, the expected number of oracle calls is O((i')² log(k)), which can be written as 0(=-ppk pk* log(k)) because Lemma A.11
Finally, as mentioned Section B.2 each element is applied in (llo(( parallel runs, resulting in total query complexity of O( pk (k)).
Lemma A.10 (Lemma 3.2 in (Banihashem al. 2024)). Let I I be independent set of matroid M, and be an element such that TO (e) & J. Define Xj := =e' é' + E i) Let w: 1 - R be an arbitrary weight function and define xj == arg minzex, w(e'). ). The element xj can be found using at most Ollo(()) oracle queries.
Lemma A.11. The number of levels i' is most O
Proof. For each element e E V. we have f(e) z MAX. Therefore, because of submodularity, we have w(e) = f(elA,) f(e) z MAX. Thus, we can conclude that w(A,) = Ered, w(e) S k MAX.
Moreover, at level i, we add element e,, we have two cases:
If e; does not replace any other elements, given the survivor invariant, w(e)) 2 &MAX which means w(A,) - w(A,11) 2
sMAX
If the element removes set of elements Ufle;), its weight should be larger than (1+ times the total weight of the removed elements in Uz(e;). This means removing elements of
Uz(e;) and adding e, adds at least / w(U'le))) 2
MMA
MAX
Since after each level, the value of w(A,) increases by at least mMXX and it cannot exceed k. MAX, number of levels at most
k MAX 12
MAX
8
Next, we analyze the query complexity of calling RECURSION on level Lemma A.12. The total cost of calling RECURSION(i) is most Ole pk? [B]| log(k)).
Proof. Based on Lemma A.10 inside the for loop of DEPENDENcY calls find replacing element. Since each element is inside most p matroids, we need to run inside that for loop times, which makes the query complexity of DepenDencyDETeeTTIO
requires Ollg(()) query
(oolk))))).
Since FINDSWAPS calls DEPENDENCY DEFECTION, and FILTERING calls FINDSWAPS on every element of [B:], one step of RECURSION needs O(B:) log(k)) oracle calls.
As proved in Lemma A.11 the depth of recursion in RECURSION is most O (E). Therefore, the query complexity of RECURSION()) is O (0 k2 [B]] p log(k)).
Lemma A.13. For a specified value of MAX, each update operation in Algorithm UPDATeOPERATIONS has query complexity at most 2 2pk² log(k)).
Proof. Based on the uniform invariant, when we insert or delete an element, for each level i it, we call REcuRSION()) with probability
1. [e B,), which is at most
Using Lemma A.12 the
[B]
[B]
22

---

query complexity for calling RecURSION()) is O pk2. [B: (Bggkk)(()) Therefore, the expected number of queries caused by level is bounded by
00'5(''ppp pk² |B|] -BB1I-og(kk)) 0 (0= "6-ppp" pk² log(k)). [
As Lemma A.11 bounds the number of levels by 1" = 0 (o:) we calculate the expected number of query calls for each update by summing the expected number of query calls at each level:
Σ 0 pk2 log(k)) s0
pk (kkkk))
To create an algorithm that operates independently of the value of MAX, we employ a strategy of guessing MAX up factor of 2 using parallel runs. Each element is inserted into only log(k/e) instances of the algorithm. Consequently, we achieve the total query complexity as claimed in Theorem 5.4
A.8 Approximation guarantee
In this section, we aim to establish the approximation guarantee of our algorithm. For this purpose, we make the assumption that elements are randomly discarded the beginning. Instead, discard them with probability - when attempting to add them to our solution. While this adjustment does affect the solution itself, it simplifies the proof of the approximation factor. We denote the set of elements discarded in this approach as R. and we use M to represent the set of elements filtered in FINDSWAPS because their marginal gain was less than sMAX
Before starting the proofs, we introduce some useful variables and notations. First, we define A' = 0 A; the union of solutions at all levels. Additionally, introduce crucial notation for our proofs:
Definition A.14. Let V be element and S V be of elements. Let be the largest number such that e E B,. We define f(e S) == A(esS \ B,), which calculates the marginal gain of adding
subset of S containing only elements that have been selected or filtered in levels preceding the level of selecting or filtering e. Note that w(e) = A(e(A;-)) ) = A(eAA \,) fle: Ai-1), where is the weight function defined Algorithm Eeer f(e: : S).
For sets T.S C V. we define f(T S)
Additionally, for every element e V. we define d(e) the first level such that e A B..
Now we represent several lemmas from Feldman et al, [018] and utilize them in our proofs. In the following, we use the constant c, defined as c =
+ p'
Lemma A.15 (Lemma in Feldman al. (2018) ). f(A' \Ap Ar) f(A,)
2018). f(A) c+1
Lemma A.16 (Corollary 8 in Feldman et al.
-((A))
Lemma A.17 (Proposition 10 in Feldman et al. (2018)) For every independent set S S (V(MUR) there exists a mapping øs from elements of S to multi-subsets of A' such that:
Each element e E Ay appears at most p times in the multi-sets of (é) (eE(s))EES),
Each element A' Ar appears at most p times in the multi-sets of (és(ee) ee
Each element e S A' satisfies w(e) S (1 + c) Eeesgte) f(e': Adee)-))
Each element E S n A' satisfies w(e) S f(e' 1 for every e' E ds(e), and the multi-set dos (e) contains exactly p elements (including repetitions).
Theorem A.18. [[f(A' U & (I+0'L. [[ +f(OPT)
23

---

Proof. First, we break A' U OPT into union of four sets:
f(A' O & f(A)+
Σ
A(elA')
+
Σ +
Σ A(elA')
(submodularity)
UAUUM)
OPTIR
OPT
S(A) +
Σ
w(e)
Σ w(e)+
w(e)
(w(e) A(eAA)) A(elA))
(UUMM)
OPTOR
OPTПM
1
f(A))+
Σ
w(e)
w(e) +
w(e).
(Lemma A.16
c
OPTNA'ORI (RUM)
OPTOR
OPTOM
If we Set = OPT (RU M), we can use Lemma
A.17 to bound the second term of the last expression:
Σ
w(e)
(1)
Σ
f(d' :
URUM))
CEOPT ('GOOPMANMN!())
Moreover,
Σ
f(e' ae
E w(e)
GEOPTMA CRUM)) e' ('
ecOPTNA'
Σ
fid :S (
(Lemma A.17
CCOPTIA'
Edderrmmantel
$ p
Σ
fle: Ap) ) + 1p-
Σ
fle: Sdie--))
(Lemma A.17
tEAr
$ p f(Ar)+ + p-1 -((A)
(Lemma A.15
C
(1+c)p- -(Ac).
Combining all together, get:
U l+c [(A))+(1++
(1 .-1c)pp111 -(A-)-p
Σ
m(e)
cEOPTeW
Σ w(e)+ + Σ w(e)
OPTOR
OPTПM
(1 + (1
-(A))-(1+))
Σ
w(e)+
Σ w(e) + Σ w(e).
eCOPTTWW
CEOPICR
OPTOM
We can bound the last term given that for each element e M, we have w(e) & sMAX = sf(OPT (OPT] S k, we can conclude that
and
Σ w(e) sf((OPT)
Now, we want to show that the expectations of the second term and the third term are equal. Consider an arbitrary clement OPT. Based about discarding elements randomly, if they were going to be added to the solution instead of being discarded at the beginning, each time element is considered for addition to the solution, with probability it will be added to A' and with probability q it will be discarded, which means will be added to R. Therefore, we have
assumption discussed at the beginning of this section
B[1 le A'] w(e)] B[1 [e R] w(e)]
q
1-4 q
where 1 [X] set to one if holds and is set to zero otherwise. Rearranging the above equality, we have
B
w(e)
1 1-q
Σ
w(e)
+ (1p E
Σ
w(e)
LOCOPTOR
9
24

---

where the last equality comes from the fact that the equality
! q
(1 + c)p holds for q
(p + vp² p+ 1 and c= v
By combining the above, get
(NUOPT) & (1 P =f(PP))(
Lemma A.19 (Lemma 2.2 Buchbinder et al. 2014)). Let ge 2 R² be a submodular function. Let S be random subset of such that each element appears in S with probability at most q, not necessarily independently. We have Blg(S) ) 2 (1 - g)g(0).
Let's define g(S)= f(S u OPT). Since g is non-negative submodular function, and each element will be discarded with probability - 4, meaning it can appear in A with probability most g. we can use Lemma A.19 to conclude that
Proof of Theorem 5.5
BIf(A' UOPT)] = E[g(A') ) 2 (1 g)((0) = (1 - 4)T(PPP) = f(OPT).
where the last equality holds because the equation Combining this with Theorem A.18 we get
q 1 for q (p+ + vp- + p 1)-1 and
(1 + ctpp BIS(A;)] + +(((PT) - ((PP),
or rearranging as
B[f(Ar) (1+ + c f(0PT) 1p + vplp 1)+11
E f(PPT).
The proof of this result is analogous to the proof of the main result I.1 with the key difference that its approximation guarantee follows directly from Theorem AA. which relies solely on the equation - (1 + c)p, unlike the proof of Theorem 5.5 which also uses the equation q = This flexibility allows the approximation ratio to be optimized by adjusting the parameters and setting c and q = (2p + 1)-!
Proof of Proposition 1.3
B Removing known MAX assumption
In this section, we show how to remove the assumption that we know a parameter MAX satisfying max,ev f(v) MAX < max f(v). While the techniques here are standard in the literature for both dynamic and streaming Kazemi et al. (201)) Lattanzi et al. [2020). [Banhashem et al. 20244] submodular optimization, we here provide the approach and the proof for completeness.
B.1 Overview of the reduction
Let A denote a dynamic algorithm that operates without this knowledge, i.c., the algorithm presented in the paper. We will maintain parallel runs of the algorithm A memory which try to guess the value MAX. Formally, for any integer i, possibly negative, let A, denote of the algorithm A with the parameter MAX set to 2'. Note that we will not actually initialize these runs for all i and will only do for some values based the inserted elements.
When an element is inserted, define I, as
2' f(v) s 22)
E2 K
For each i E l,, if the instance A, is not initialized, then we initialize it. Next, for all i E I,, we insert v in A.
When an element is deleted, we delete it from all A, for i I,. We always output the maximum answer among all parallel runs that are initialized. We note that this does not require any queries.
25

---

B.2 Analysis of query complexity
Since 1,| z log(k/s), and initializing A, with an empty ground set does not require any queries, the expected query complexity of the algorithm is O(log(k/E) times the expected query complexity of A
B.3 Analysis of approximation guarantee
We first consider an alternative version of the algorithm in which we set I, to be
4 = -;= f(v) 21
We claim that the output of this version is the same the version described in Section B. Note that this new algorithm used for the purpose of analysis only and is not actually used for implementation.
This is because if f(v) {2', then the algorithm simply discards it given the check in FINDSWAPS. For the new version of the algorithm, set i' such that 2"-1 f(v) s 2'. Given the analysis in Section A the output of Ay provides the desired approximation guarantee. Since we are always taking the output of the A, with the best output, output provides the desired approximation guarantee well.
26

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly and accurately state the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The assumptions made in the paper as well as the results are clearly stated and therefore the limitations are clear.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
27

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: complete proof of theoretical results is provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper makes significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
28

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper makes a significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr Sowiiddess/odeeuuumisiiioooooo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
haapss/ccc/obll/gggggii///ooaaao wwimiissiinns ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: The paper makes significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
29

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper makes significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror hars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper makes significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
30

---

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httptt/eseeeers...ooooooooicccia
Answer: [Yes]
Justification:
Conforms to the guidelines
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical in nature and does not have societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
31

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssw thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
32

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not use crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: No LLMs were used in conducting the research or generating the results.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non stanstdddard components.
Please refer LLM policy hatto:///narrrssccc///oorrrrrere for what should or should not be described.
33


Reviews:
[{"review_id": "LKcpRohrqr", "reviewer": "Reviewer_uQeU", "summary": "The paper studies dynamic maximization of submodular objective over a matchoid where single elements are inserted or removed dynamically. A 2-part algorithm is given; it builds an initial solution, and updates it as the ground set is modified. The paper includes its theoretical analysis, with findings pertaining to the query complexity and online approximation guarantees.", "questions": "Since $f$ can be non-monotone, the assertion that $\\min_{X\\in\\mathcal{I}}f(X)=0$ would preserve the generality of the problem, while $f(\\emptyset)=0$ would not. Do the results in this work require that the latter hold, or would a more careful application of notations suffice?\n\nAlgorithm 1: is $A_0$ assigned 0 or $\\emptyset$?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is written clearly. The concepts and settings are explained in a way that accommodates unfamiliar readers. The method is explained well, and adequately contextualized by existing work.\n\nThe contribution is significant due to the breadth of the considered setting. General submodular functions are relevant to machine learning, and matchoids capture a wide range of independence systems. The proposed method also improves over an existing method under a simpler setting in approximation guarantees, at the cost of increased query complexity.\n\nDue to the generality of the setting, sharpened results in popular special cases would be appreciated. Only one case is listed. There is a large body of work on monotone objectives. I believe the approximation bound in this work can be strengthened under monotonicity of $f$.\n\nThe algorithm contains some stochastic components, the most impactful of which is the RateSampling subroutine. It'd make the paper more self-contained to have its relevant probabilistic properties stated in Section 4.1.\n\nThe study lacks empirical investigation. It'd be nice to see the online approximation quality of the algorithm under various insertion/deletion patterns, or at least a direct comparison to the performances given by Banihashem et. al, 2023.", "was_revised": true, "final_justification": "The authors adequately addressed my concerns, which are minor. Given that the additional experimental results are unavailable at this time, I will keep my score.", "rebuttal": "Thank you so much for your positive feedback. We are glad you were satisfied with the clarity, significance, and quality of our paper. We address specific questions and comments below:\n\n> Since $f$ can be non-monotone, the assertion ... . Do the results in this work require that the latter hold, or would a more careful application of notations suffice?\n\n\nThank you for the question. The stronger assumption is not required, and non-negativity of the function $f$ is sufficient for the analysis to hold, which, as you noted, preserves the generality of the problem. We have made proper adjustments to the notations accordingly.\n\n> Algorithm 1: is $A_0$ assigned 0 or $\\emptyset$?\n\nThe variable $A_0$ is initialized to $\\emptyset$. Thanks for catching this. \n\n> It'd be nice to see the online approximation quality of the algorithm under various insertion/deletion patterns, or at least a direct comparison to the performances given by Banihashem et. al, 2023.\n\nWe acknowledge that empirical results would provide further valuable insight. We have conducted experiments evaluating the performance of\nour algorithm for video summarization using datasets obtained from YouTube and the Open Video Project. \nFor the special case of cardinality constraint, we benchmarked the total number of query calls and the submodular value of our solution, demonstrating competitive performance compared to [Banihashem et al., 2023]. \nAs per the guidelines, we are unable to provide these during the rebuttal period; however, we will incorporate them in the final version of the paper."}, {"review_id": "YzBYqay5s4", "reviewer": "Reviewer_Tfaj", "summary": "This paper studies non-monotone submodular maximization with p-matchoid constraint, in the fully dynamic setting. In such setting, elements are inserted and deleted by an adversary, and the goal is to maintain an high-quality solution using few queries. Typically, the amortized number of queries should not depend polynomially in $n$, the length of the stream. \n\nThe authors propose an $\\approx 4p$ approximation for $p$-matchoids, building on the fully-dynamic framework of Banihashem et al.", "questions": "None", "limitations": "nothing to add here", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "- Submodular maximization is an important optimization task that has been studied intensively by the NeurIPS and ICML communities\n- The fully dynamic setting is well motivated in practice\n- Non-monotone submodular maximization naturally arises in applications\n- p-matchoids are arguably the most general constraints in the submodular maximization literature\n- the paper is fairly well written\n- the authors improve on the state of the art for cardinality constraints (from 8 to 5.82, but at the cost of worse running time)\n- The technical contribution is non-trivial, but not totally unexpected and original. The author's construction is heavily inspired by the versatile framework of Banihashem et al. and adapted to $p$-matchoids.", "was_revised": true, "final_justification": "I confirm my score", "rebuttal": "We thank the reviewer for recognizing the importance of our problem and contributions. We are pleased that you found the paper well-written and of high quality, and we greatly appreciate the positive and affirming review."}, {"review_id": "f36EpnROjO", "reviewer": "Reviewer_fHaN", "summary": "This paper investigates non-monotone submodular maximization in a fully dynamic setting with $p$-matchoid constraints. The main contributions are:\n- A $(2p+2\\sqrt{p(p+1)}+1+\\epsilon)$-approximation algorithm with an expected amortized query complexity of $O(\\epsilon^{-3}pk^4\\log^2(k))$. This is the first theoretical advancement for this problem under $p$-matchoid constraints.\n- As a byproduct, a $(5.82+\\epsilon)$-approximation algorithm is proposed under size constraints with $O(\\epsilon^{-3}k^4\\log^2(k))$ oracle queries per update. This algorithm improves the best-known $(8+\\epsilon)$ approximation ratio for this problem.", "questions": "- Empirical validation would significantly strengthen the paper's contributions. Especially the comparison of the $(5.82+\\epsilon)$-approximation algorithm with the existing $(8+\\epsilon)$-approximation algorithm under size constraints. Experiments under $p$-matchoid can also serve as reference points for future works.\n- It might to better to shorten the first three sections and move some of the analysis into the analysis section.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The study addresses an important and practically relevant problem in submodular optimization, with clearly motivated applications discussed such as feature selection.\n- The paper provides the first approximation algorithm for non-monotone submodular maximization under $p$-matchoid constraints in dynamic settings. As a by-product, it also improves the approximation ratio for the special case of cardinality constraints, advancing the state of the art. \n- The paper is clearly written and logically structured, making the technical contributions accessible to readers.\n\nWeaknesses\n\nGiven the practical nature of dynamic settings, experimental validation on real-world or synthetic datasets would strengthen the paper’s impact.", "was_revised": true, "final_justification": "I have read the rebuttal and other reviews. I will keep my score.", "rebuttal": "We thank the reviewer for the positive evaluation and for highlighting the importance and quality of our contributions. \nWe are very pleased that you found our paper well-written and technically solid.\n\nWe appreciate your helpful feedback and will incorporate your suggestions into our paper.\n\nSpecifically, regarding empirical evaluations, while the primary focus of this work has been on the theoretical development, we fully agree that empirical evaluations would further enhance the impact of our work. \nFor the special case of cardinality constraints, we have conducted experiments on real-world datasets (videos from YouTube and Open Video Project for the task of video summarization). \nWe compared our algorithm’s query complexity and submodular value against the state-of-the-art $(8+\\epsilon)$-approximation algorithm, and the results showcased the competitive performance of our algorithm. We will include these in the revised version of our paper."}, {"review_id": "qU3DSZdnVr", "reviewer": "Reviewer_wQek", "summary": "This paper presents the first dynamic algorithm for non-monotone submodular maximization under general p-matchoid constraints. The authors develop a recursive filtering and sampling framework that maintains an approximate solution as elements are inserted or deleted. Their algorithm achieves a provable approximation guarantee and low amortized query complexity, improving prior results for special cases like cardinality constraints.", "questions": "1. The algorithm relies on random sampling to simulate monotone behavior, how sensitive is the performance to the sampling probability q? \n2. Would a different choice affect approximation or update cost significantly?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.The paper introduces the first dynamic algorithm for non-monotone submodular maximization under general p-matchoid constraints, achieving strong theoretical guarantees and improving upon prior results.\n\n2.The recursive filtering and sampling framework is elegant and efficiently handles both insertions and deletions with provable amortized query complexity.\n\nWeaknesses:\n\n1.The theoretical query complexity includes high-degree polynomial terms, which may limit scalability in real-world applications.\n\n2.The dynamic model is based on the oblivious adversarial assumption, and its robustness against adaptive attack scenarios has not been fully discussed.", "was_revised": true, "final_justification": "My concerns have been fully addressed via author rebuttal.", "rebuttal": "Thank you for the constructive and encouraging review. We greatly appreciate your positive assessment of the strength and elegance of our algorithm. Below, we address questions and concerns you raised.\n\n> The theoretical query complexity includes high-degree polynomial terms ...\n\nWe note that the query complexity, although polynomial in $k$, is independent of $n$, the size of the ground set. This makes it practical in many real-world scenarios. \n\n> The dynamic model is based on the oblivious adversarial assumption, and its robustness against adaptive attack scenarios has not been fully discussed. \n\nThe approximation guarantee of the algorithm does not rely on the oblivious adversarial assumption. However, our current analysis of the query complexity bounds is tailored to the oblivious setting\nand may not directly extend to scenarios against an adversary with full knowledge of the random bits used in the algorithm. \nHowever, we should note that this is a valid assumption in many real-world scenarios, and it is also consistent with prior work in fully dynamic submodular optimization, where, to the best of our knowledge, all existing results assume the same kind of adversarial setting. \nNonetheless, robustness against adaptive adversaries is an interesting and important direction for future research in the field. \n\n> The algorithm relies on random sampling to simulate monotone behavior. How sensitive is the performance to the sampling probability q?\n\nThe analysis of the algorithm is based on a fixed value for the parameter  $q = (p+\\sqrt{p^2+p}+1)^{-1}$. \nWe use equalities $\\frac{1}{q} - 1 = (1 + c)p$ and $1 - q = \\frac{1}{c}$ to get an approximation gurantee of $\\frac{c}{(1+c)^2p}\\left(\\frac{1}{c} - \\epsilon \\right)$. These equalities hold for the said choice of $q$ and $c=\\sqrt{1+\\frac{1}{p}}$. \n\nWe will clarify this earlier in the paper to avoid ambiguity.\n\nIf you feel that our response has adequately addressed your concerns, we would appreciate it if you would possibly raise your score accordingly."}]

Author rebuttal:

Meta-review: This paper studies submodular maximization in the dynamic setting. The main result is an algorithm that maintains an approximate solution with a fast update time for non-monotone submodular maximization over a p-matchoid constraint. Previous dynamic algorithms were either for non-monotone functions under a cardinality constraint or for monotone functions under a matroid constraint. p-matchoid constraints are a general family of constraints that generalize matroids.
This paper achieves a strong result for a very general setting. The algorithm is technically involved and interesting (but does mostly build on ideas from previous work).
Decision: Accept (poster)