Learning-Augmented Dynamic Submodular Maximization
Authors: Arpit Agarwal
Eric Balkanski
Venue: NeurIPS 2024 poster (2024)
Keywords: Submodular maximization
algorithms with predictions
dynamic algorithms
Primary area: optimization
TL;DR: We study dynamic submodular maximization in the algorithms with predictions framework.

Abstract: In dynamic submodular maximization, the goal is to maintain a high-value solution over a sequence of element insertions and deletions with a fast update time. Motivated by large-scale applications and the fact that dynamic data often exhibits patterns, we ask the following question: can predictions be used to accelerate the update time of dynamic submodular maximization algorithms? 

We consider the model for dynamic algorithms with predictions where predictions regarding the insertion and deletion times of elements can be used for preprocessing. Our main result is an algorithm with an $O(\text{poly}(\log \eta, \log w, \log k))$ amortized update time over the sequence of updates that achieves a $1/2 - \epsilon$ approximation for dynamic monotone submodular maximization under a cardinality constraint $k$, where the prediction error $\eta$ is the number of elements that are not inserted and deleted within $w$ time steps of their predicted insertion and deletion times. This amortized update time is independent of the length of the stream and instead depends on the prediction error.

Learning-Augmented Dynamic Submodular Maximization
Arpit Agarwal Indian Institute of Technology Bombay aarpit@iitb.ac ac.aittb.c..i..
Eric Balkanski Columbia University eb32249columiia edu
Abstract
In dynamic submodular maximization, the goal is to maintain high-value solu- tion over sequence of element insertions and deletions with a fast update time. Motivated by large-scale applications and the fact that dynamic data often exhibits patterns, we ask the following question: can predictions be used to accelerate the update time of dynamic submodular maximization algorithms?
We consider the model for dynamic algorithms with predictions where predictions regarding the insertion and deletion times of elements can be used for preprocessing. Our main result is an algorithm with an (ppoly (poly((og) 7), log w, log k)) amortized update time over the sequence of updates that achieves a 1/2 approximation for dynamic monotone submodular maximization under cardinality constraint k, where the prediction eтror is the number of elements that are not inserted and deleted within w time steps of their predicted insertion and deletion times. This amortized update time is independent of the length of the stream and instead depends on the prediction error.
Introduction
Submodular functions are well-studied family of functions that satisfy a natural diminishing returns property. Since many fundamental objectives are submodular, including coverage, diversity, and entropy, submodular optimization algorithms play an important role in machine learning [88 8) network analysis [17), and mechanism design
[3I]. For the canonical problem of maximizing monotone submodular function under cardinality constraint, the celebrated greedy algorithm achieves 1-e approximation guarantee (27). which is the best approximation guarantee achievable by any polynomial time algorithm (26). Motivated by the highly dynamic nature of applications such as influence maximization social networks and recommender systems on streaming platforms, recent line of work has studied the problem of dynamic submodular maximization 20 25 28 [0 [1
7. the dynamic setting, the input consists of a stream of elements that are inserted or deleted from the set of active elements, and the goal is to maintain, throughout the stream, subset of the active elements that maximizes a submodular function.
The standard worst-case approach to analyzing the update time of a dynamic algorithm is to measure its update time over the worst sequence of updates possible. However, in many application domains, dynamic data is not arbitrary and often exhibits patterns that can be learned from historical data, Very recent work has studied dynamic problems settings where the algorithm is given as input This recent work is part of a broader research surming--ugmented
predictions regarding the stream of updates [14 22 9.
area called learning augmented algorithms (or algorithms with predictions). seamiin--augmented algorithms, the goal is to design algorithms that achieve improved performance guarantee when the error of the prediction small and bounded guarantee even when the prediction error is arbitrarily large. A lot of the effort in this area has been focused on using predictions to improve the competitive 15 and more generally to
ratio of online algorithms (see, e.g., 23 30 improve the solution quality of algorithms.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

For dynamic submodular maximization with predictions, Liu and Srinivas [22] considered a predicted-deletione model and achieved, under some mild assumption, a 0.3178 approximation and an (pooly(k: (k; log n) I updatte time for dynamic monotone submodular maximization under a matroid constraint of rank k and over stream of length n. This approximation is an improvement over the best-known 1 1/4 approximation for dynamic monotone submodular maximization (without predictions) under matroid constraint with an update time that is sublinear in n ααI. Since the update time of dynamic algorithms is often the main bottleneck in large-scale problems, another promising direction is to leverage predictions to improve the update time of dynamic algorithms.
Can predictions help to accelerate the update time of dynamic submodular maximization algorithms?
We note that the three very recent papers on dynamic algorithms with predictions have achieved improved update times for several dynamic graph problems [14] [2 However, to the best of our knowledge, there is no previous result that achieves an improved update time for dynamic submodular maximization by using predictions.
Our contributions. In dynamic submodular maximization, the input is a submodular function f 2 + R20 and a sequence of n element insertions and deletions. The active elements V2 S V at time are the elements that have been inserted and have not yet been deleted during the first updates. The goal is to maintain, at every time step i, a solution S, C V2 that is approximately optimal with respect to V. while minimizing the number of queries I each time step, which referred as we consider a prediction model where, at time = 0, the algorithm is
the update time. As in 14] 9. given a prediction regarding the sequence of updates, which can be used for preprocessing. More precisely, at time t O, the algorithh is given predictions (f. (2) about the insertion and deletion time of each element a. A dynamic algorithm with predictions consists of two phases. During the precomputation phase f 0, the algorithm uses the predictions to perform queries before the start of the stream. During the streaming phase at time steps & > O, the algorithm performs queries, and uses the precomputations, to maintain a good solution with respect the true stream.
In this model, there a trivial algorithm that achieves a constant update time when the predictions exactly correct and an (u)) update time when the predictions are arbitrarily wrong. Here, is the update time of an arbitrary algorithm A for the problem without predictions. This algorithm precomputes, for each future time step f, a solution for the elements that predicted to be active at time and then, during the streaming phase, returns the precomputed solutions while the prediction is correct and switches to running algorithm A at the first error in the prediction. Thus, the interesting question is whether it is possible to obtain an improved update time not only when the predictions are exactly correct, but more generally when the error in the predictions is small. An important component of our model is the measure for the prediction error. Given time window tolerance w, an element a is considered be correctly predicted if the predicted insertion and deletion times of are both within w times steps of its true insertion and deletion times. The prediction error 7j is then the number of elements that are not correctly predicted. Thus. 17 if the predictions are exactly correct and (nn) if the predictions are completely wrong.
For dynamic monotone submodular maximization (without predictions) under cardinality con- straint k, Lattanzi et al. (20] and Monemizadeh (2 concurrently obtained dynamic algorithms with Oppoly(log n, log k)) and (polylog(n)) A?)) amortized update time, respectively, that achieve 1/2 approximation. More recently. Banihashem et al. [7] achieved a 1/2 approximation with O(k- polylog(k)) amortized update time. Our main result is the following.
Theorem. For monotone submodular maximization under cardinality constraint k, there is dynamic algorithm with predictions that, for any tolerance w and constant e 0, achieves an amortized expected query complexity per update of (pply 17, log w, logk)), an approximation 1/2 in expectation, and a query complexity of Ö(n) during the precomputation phase.
We note that, when the prediction error 7) is arbitrarily large, our algorithm matches the O(poly(log n. log k)) amortized expected query complexity per update in (20). It also achieves an approximation that matches the optimal approximation for dynamic algorithms (without predic- tions) with update time that is sublinear in n. An intriguing open question is whether an improvement in update time can be obtained in the predicted-deletion model of (22 with no preprocessing and instead a predicted deletion time for each element is given at the time when a is inserted.
In this paper, we the notation (n)( as shorthand for O(g(n) log g())).

---

Related work. For monotone submodular maximization under a cardinality constraint, dynamic algorithms with O(poly n, log k)) and O(polylog(n) x²)) amortized update time that achieve a
1/2 approximation were concurrently obtained in [20 25 Recently, Banihashem et al. 7 gave
1/2 approximation algorithm with a O(k pololoolllo))))) k)) amortized update time. Chen and Peng [TQ] showed that any dynamic algorithm with an approximation better than 1 1/2 must have poly(n) amortized query complexity per update. For matroid constraints, Chen and Peng [00] obtained an insertion-only algorithm. As mentioned in [29]. the streaming algorithm in [13] can be adapted to also give an insertion-only algorithm. Two 1 1/4-approximation dynamic algorithms with (kk) and (polylog(n)) A²) amortized update time were concurrently obtained in 7 and M.Л.
Algorithms with predictions have been studied in a wide range of areas, including online algorithms 23 [3], mechanism design [3], and differential privacy [2] Improved update times for several dynamic graph problems were very recently obtained by leveraging predictions [4] 22 9. In particular, Liu and Srinivas [22] obtained, under some mild assumption on the prediction error, a 0.3178 approximation and (poly(kk: log n)) update time for dynamic monotone submodular maximization under matroid constraint of rank i in the more challenging predicted-deletion model. Thus, by using predictions, this result improves the 1/4 approximation achieved, without predictions, in 7 and [I] (but does not improve the 1/2 approximation for cardinality constraints). The results in 22 use framework that takes as input an insertion-only dynamic algorithm. In contrast, we develop a framework that uses a fully dynamic algorithm and a deletion-robust algorithm.
2 Preliminaries
A function f 2 - IR defined over a ground set V is submodular if for all S S T'S S V and the marginal
V.T, T,, we have that fs(()= 2 (a))), where fa( = S(S U (a)) S(S) contribution of a to S. It is monotone if f(S) S f(T) for all S C We consider the canonical problem of maximizing monotone submodular function f under a cardinality constraint k.
In dynamic submodular maximization, there is a stream {(a,, )r) of n element insertions and deletions where o E (insert, deletion) and a is element in V. The active elements V, are the elements that have been inserted and have not been deleted by time t. We assume that (a,, insertion) and (a:; deletion) can occur in the stream only if a, & V, and a E V,, respectively, and that each element is inserted at most once The goal is to maintain solution S; C V that approximates the optimal solution over V,, which we denote by O,. Since our algorithmic framework takes as input a dynamic algorithm, we formally define dynamic algorithms in terms of black-box subroutines that are used in our algorithms.
Definition 1. A dynamic algorithm DYNAMIC(J, ke) consists of the following four subroutines to process stream {(a,,
DYNAMICINIT (f,k) initializes data structure A at t 0. If or = insertion or O2 = deletion, DYNAMICINSÍ (ACIINS((,,n,, oz) or DYNAMICDEL az) insert in A or delete from A element a time At time i, DYNAMICSOL(A) returns S. S (A) s.t. |S| < k. where V(A)= = Vz is the set of elements that have been inserted in and not been deleted from A.
A dynamic algorithm achieves an a-approximation in expectation if, for all time steps t, [S)) > max ss (S) and has a u(n, k) amortized expected query complexity per update if its expected total number of queries n u(n,k)) k).
In dynamic submodular maximization with predictions, the algorithm is given at time t = 0 predictions {(5t f=)) about the insertion and deletion time of elements a. The prediction error v) is the number of elements that are incorrectly predicted, where an element a is correctly predicted if it is inserted and deleted within a time window, of size parameterized by a time window tolerance w, that is centered at the time at which is predicted to be inserted and deleted.
Definition 2. Given a tolerance w E Z+, predictions (( ( Jaev, and true insertion and deletions times {(t tz Jaev. v. the prediction error is r)- = Ia E V : [ - + > w or 1f, - t > w]|.
We note that 17 = w = 0 corresponds to the predictions being exactly correct and 77 0(n) and = (nn) corresponds to thems being arbitrarily wrong. We also emphasize that our model does not require knowing the entire ground set V at f = O. Elements that are not known at t = 0 are assumed to have predicted arrival and departure times equal infinity, and contribute to the prediction error n).
If an element is re-inserted, copy a' of a can be created.
3

---

Deletion-robust submodular maximization. Our framework also takes as input a deletion-robust algorithm. which we formally define in terms of black-box subroutines. A deletion- algorithm finds solution S S V that is robust to the deletion of at most d elements.
Definition 3. Given function f 2V - R, cardinality constraint k; and a maximum number of deletions parameter d, a deletion- algorithm ROBUST(J. V,k,d) consists of a first subroutine ROBUSTI (f, V, k, d) that returns robust set R _ V and a second subroutine ROBUST2(J, R, D, that returns a set S - RRRD such that ||| S
deletion-robust algorithm achieves an approximation if, for any f. V, k. and d, the subroutine ROBUSTI (f, V, k, d) returns It such that, for any D S V such that DD I d, ROBUST2(F, R, D, k) returns 8 such that E[[(S)] Z maxxgy D f()). Kazemi al. [6] show that there is deletion-robut algorithm for monotone submodular maximization under a cardinality constraint such that ROBUSTI returns set R of size |R| = O(e dloo + k). It achieves 1/2
approximation in expectation, ROBUST has O([V)-(k+e log k)) query complexity, and ROBUST2 has O ddgg k + k) e log k) query complexity.
The algorithmic framework. We present algorithmic framework that decomposes dynamic algorithms with predictions into two subroutines, PRECOMPUTATIONS and UPDATESOL. The remainder of the paper then consists of designing and analyzing these subroutines. We first introduce some terminology. An element a is said to be correctly predicted if 1 - 1 I and 1 la S w.
The predicted elements V2 consist of all elements that could potentially be active at time t if correctly predicted, i.e., the elements such that it < L + and 1, 2 phase, the first subroutine, PRECOMPUTATIONS takes as input the predicted elements Vi and outputs, for each time step f, a data structure P. that will then be used at time of the streaming phase to compute solution efficiently. During the streaming phase, the active elements Vú partitioned into the predicted active elements V22 V; V, and the umpredicted active elements V,2 V2 V. The second subroutine, UPDATESOL, is given V,² and V?2 as input and computes a solution C V, V each time step. UPDATESOL also given input precomputations Pt and the current prediction error Th. It also stores useful information for future time steps in data structure A.
During the precomputation
Algorithm 1 The Algorithmic Framework
Input: function : + I, constraint k. predictions )eev, tolerance
1: V/2 {a EVEV it < t and i 2 1 -w for E [m]
2: (Pr) f- PRECOMPUTATIONSS {V.)=..)))
3: Vo,++0
4: for = to do
5:
Update active elements Vú according to operation at time
6:
V. V2 n V. V V2 Vz
7:
Ve < current prediction emror
8:
A,5 < UPDATESOL k, A, P., V1 V2, m)
9: return
3 The warm-up algorithm
In this section, we present subroutines that achieve an Ö(q + w + k) amortized update time and a 1/4- approximation in expectation. These warm-up subroutines assume that the error 17 known. They take as input dynamic algorithm (without predictions) DYNAMIC and deletion-robust algorithm ROBUST algorithm. The proofs are all deferred the appendix.
The precomputations subroutine A main observation is that the problem of finding solution S" S V. among the predicted active elements corresponds to a deletion-robuss problem over V. where the deleted elements D are the predicted elements V. \ V that are not active at time t. WARMUJ--PEECOMPUTTTOON thus calls, for each time t, the first stage ROBUSTl of ROBUST,
WARMUP- PRRMUU-PRRCCOMUUTTTIONS/ (V.)2 k) [RoBUSTI(F, V,, 2w) )-1-

---

The algorithm sets the maximum number of deletions parameter d for ROBUSTI to 2w because the number of predicted elements Vi \ Vi that are not active at time i is at most + 2w (Lemma
The updatesol subroutine WARMUP-UPDATESST
finds a solution S' V by calling ROBUST2 over the precomputed Pt and deleted elements D = V; V, To find solution S S V2² among the unpredicted active elements, we use DYNAMIC over the stream of element insertions and deletions that result in unpredicted active elements V/² ..... V which is the stream that inserts elements V?2 V22 and deletes elements V2-, \ V22 at time t. The solution S is then the solution produced by DYNAMICSOL, over this stream. The solution S returned by UPDATESOL is the best solution between S' and S
Algorithm 2 WARMUP- SARMÜPP-PPATESOLL
Input: function f, constraint k; data structure A, time precomputations Pt, predicted active elements V/ unpredicted active elements V2², predicted elements Vi
1: S < ROBUST2(f, Pt, V V2 k)
2: i = then A + DYNAMICINIT(f 1:)
3: for a E V/2 ((A) do DYNAMICINS a)
4: for ((A) V do DYNAMICDEL
5: S + DYNAMICSOL(A)
6: return A, (f ((
The analysis of the warm-up algorithm We first analyze the approximation. We on and 02 denote the approximations achieved by ROBUST and DYNAMIC. The first lemma shows that solution St is an di approximation to the optimal solution over the predicted active elements V/2 and that solution S is an a2 approximation to the optimal solution over the unpredicted active elements V/2.
Lemma 1. At every time step t. E[f(s") 2 OPT(V;)) and E[f( 2 0: OPT(V?)-
The main lemma for the amortized query complexity bounds the number of calls to DYNAMICINS.
Lemma 2. WARMUP-UPDATESON makes at most 2n calls to DYNAMICINS on A over the stream.
The main result for the warm-up algorithm is the following.
Theorem 1. For monotone submodular maximization under cardinality constraint k, Algorithm 7 with the CREMUP-PRECOMPUTAAE
and WARMUP- SLARMUP-UPDATESOO subroutines achieves, for any tolerance and constant >> O, amortized expected query complexity per update during the streaming phase of Ö(1 + w + k). approximation of 1/4 in expectation, and query complexity of O(n k) during the precomputation phase.
In the next sections, we improve the dependencies on 7), and k for the query complexity per update from linear logarithmic, the approximation from 1/4 to 1/2, and the precomputations query complexity from (nn²k) (n)). We also remove the assumption that the prediction error is known.
The UpdateSol subroutine
In this section, we improve the dependencies in 7) w, and for the amortized query complexity from linear to logarithmic, which is the main technical challenge. For finding solution over the predicted active elements V.!, the main idea is to not only use precomputations Pt, but also to exploit computations from previous time steps E' < t over the previous predicted active elements Vit. As in the warm-up subroutine, the new UPDATESOLMAIN subroutine also uses a precomputed deletion-robust solution Pr. but it requires P. to satisfy a property termed the strongly robust property (Definition
4 below), which is stronger than the deletion-robust property Definition 3 A strongly robust solution comprises two components Q and R, where R is a small set of elements that have high marginal contribution to Q. The set Q is such that, for any deleted set D, f(Q) D) is guaranteed to, in expectation over the randomization of Q, retain large amount of f()).
Definition& 4. A pair of sets (Q, R) is (d, e, -.))))stogllyyy robust, where d, k, y 0 and E [0,
5

---

Size. |Q1 S l and |R| 2 (d k) log k) with probability 1,
Value. f(Q) S SVV \ R we have (S) < (2k) + 67--
(2k) with probability 1. In addition, if [Q] k, then for any
Robustness. For any D V s.t. [D] d. Eolf(Q DJJ (1-))(()))
The set P returned by the first stage ROBUSTI (f, k. d) of the deletion-robus algorithm of Kazemi et al. [16 can be decomposed into two sets Q and R that are, for any d, >> and with 7 = OPT(V (V). maxscv:1s SA fSS,, (d, 7t-stroggly robust Thus, with the ROBUST algorithm of [16], the set Pe returned by
where (V)
can be decomposed into P. and Q that are, for any e > 0. (2(n++2w) OPT ( robust. We omit the proof of the (d, -ttronnly robust property of ROBUSTI from [66 and, in the next section, we instead prove strong-robustness for our PRECOMPUTATIONSMANT subroutine which has better overall query complexity than [16].
The UPDATESOLMAIN subroutine proceeds in phases. During each phase. UPDATESOLMAI maintains a data structure (B, A, 7ola). The set B Qr is a fixed base set chosen during the first time step t' of the current phase. A is dynamic data structure used by dynamic submodular maximization algorithm DYNAMIC that initializes A over function fB. cardinality constraint & [B], and a parameter to be later discussed. If a new phase starts time note that if (Qt, R₂) are strongly robust, then the only predicted active elements V, that are needed to find a good solution at time are, in addition to B 22, the small set of elements R, that also in V,"_ Thus to find a good solution for the function Sn. (Re n V2²) U V22 are inserted into A. The solution that OPDATESOLMAINN outputs at time step are the active elements B n V. that in the base for the current phase, together with the solution DYNAMICSOL maintained by A.
Algorithm 3 MADATESOLMAIN
Input: function f. data structure (B, A, nota). constraint k precomputations P. = (Qt, Re), t, upper bound 1/d on prediction error, V.!. V22, Vi-1, parameter "
1: ift = 1 or Ops (A) Tuu + then
Start new phase
2:
B g+ Q
3: A + D
4:
for E (V)) VV, do DYNAMICINS(A,a))
5:
nold + Th
6: else
Continue the current phase
7:
for E V, Vi-1 do DYNAMICINS(A.a)
8: for a E (BLEM(An V--1) V/ do DYNAMICDEI(A,a)
9: S (B (BU (YNDDMMICSOO)()))
10: return (B, A, S
During the next time steps of the current phase, if an element a is inserted into the stream then is inserted in A (independently of the predictions). If an element is deleted from the stream, then if was in A, it is deleted from A. We define Ops" (AA) to be the collection of all insertion and deletion operations to A. excluding the insertions of elements in (Re n V. V/2 at the time t where was initialized. The current phase ends when Ops" (A) exceeds Mata/2 + w. Since the update time of the dynamic algorithm in (20) depends on length of the stream, we upper bound the length of the stream handled by A during phase.
The parameter "/ corresponds guess for OPT, == OPT(V)). Section 6 we present the UPDATESOLFULE subroutine which calls UPDATESOLMAI with different guesses Tt. This parameter "t. is needed when initializing DYNAMIC because our analysis requires that DYNAMIC satisfies property that we call threshold-based. which we formally define next.
The approximation
Definition S. A dynamic algorithm DYNAMIC is threshold-baser d if, when initialized with threshold parameter " such that 7 S OPT, < (1 + e) a cardinality constraint k, and e > 0, it maintains data structure A₁ and solution SOL, DYNAMICSOL(A)) that satisfy, for all 1, f(SOL. Z I SOL,
and, if SOL. < (1 e) then for any set S C (At), we have fenr, (S)
1817
2k
eTy.
The size of R in 16 is Od k/c) which is better than what is required be strongly robust.

---

Lemma 3. The DYNAMIC algorithum of Lattanzi et al. 120 is threshold- based.
The main lemma for the approximation guarantee is the following.
Lemma 4. Consider the data structure (B, Moid) returned by UPDATESOLM at time t. Let E be the time at which A was initialized, (Qv, Re.) and " be the precomputations and guess for OPTy inputs UPDATESOLMAIN at time t'. If (Qe, Re) are (d = 2(Joid + 2w), T, - robust, The is such that T I OPT, I (1+ +++e)re and DYNAMIC is threshold-based dynamic algorithm, then the set S returned by UPDATESOLMAIN such that E[f(S) Z 1-ae yv-
2
The update time We next analyze the query complexity of UPDATESOLMAIN, Recall that unn, k) denotes the amortized query complexity per update of DYNAMIC.
Lemma 5. Consider the data structure (B, A, Mola) returned by UPDATESOL.MAT at time t. Let be the time which A was initialized and (Qu, Re:) be the precomputations input UPDATESOL MAIN MAIN at time t'. If precomputations (Qr, Re) are (d 2(Toid + 2w). 7) strongly-robust then the total number of queries performed by UPDATESOL during the t- t' time steps between time and time is (uu(TTat + w + k) log k. k) (Mald + w + k) log k). Additionally, the number of queries between time and is upper bounded by (u((, k) t).
The Precomputations subroutine
In this section, we provide a PRECOMPUTTTIIOS subroutine that has an improved query complexity compared to the warm-up precomputations subroutine. Recall that the warm-up subroutine computes robust solution over predicted elements V,, independently for all times t. The improved PRECOM- PUTATIONS does not do this independently for each time step. Instead, it relies on the following lemma that shows that the data structure maintained by the dynamic algorithm of (20 can be used to find a strongly robust solution without any additional query.
Lemma 6. Let DYNAMIC(T,,c) be the dynamic submodular maximization algorithm of 120) and A be the data structure it maintains. There a ROBUST FROMDYNAMIC algorithm such that, given as input a deletion size parameter d, and the data structure at time with 7 OPT, < (1+e)n outputs sets (Q, R) that are (d, e, -sstrongly robust with respect to the ground set Vz. Moreover, this algorithm does not perform any oracle queries.
The improved PRECOMPUTATIONSMAN subroutine runs the dynamic algorithm of 20 and then, using the ROBUST FROMDYNAMIC algorithm of Lemma 6 computes a strongly-robust set from the data structure maintained by the dynamic algorithm.
Algorithm 4 PRECOMPUTATIONSMANN
Input: function 2V + R. constraint k; predicted elements Vi,..., V, S V, time error tolerance W, parameter 7, parameter h
1: < (yNAMICINIT(,KK1))
2: for = 1 to n do
3: for E V. \ Vi_1 do DYNAMICINS(A.
4: for E ((A) \ V. do DYNAMICDEL(A,
5: if [V(A) > 0 then Qt, R₁ +- ROBUST1 A, h,,2(h + 2w))
6: return ((Q,,R))P)
The parameters y and h correspond to guesses for OPT and respectively.
Lemma 7. The total query complexity of the PRECOMPUTATIONSSANN algorithm is n u(n, k), where u(n, k) is the amortized query complexity of calls to DYNAMIC.
'Not that the initially published algorithm in 20 had an issue with correctness, refer to the revised version.
7

---

6 The full algorithm
The UPDATESOLMMAT and PRECOMPUTATIONSIN optimal value OPT, at time and the total prediction error In Appendix D we describe the full UPDATESOLFULL and PRECOMPUTATIONSFULE subroutines that call the previously defined subroutines over different guesses and h. The parameters of these calls must be carefully designed bound the streaming amortized query complexity per update and precomputations query complexity. By combining the algorithmic framework (Algorithm I together with subroutines UPDATESOLFULD and EEECOMPPTTTTIONSUUL. we obtain our main result.
subroutines guesses y and h for the
Theorem 2. Algorithmm 7 with subroutines UPDATESOLFULL and PRECCOMUUAATIONSUULL is dy- namic algorithm that, for any tolerance and constant > O, achieves an amortized expected query complexity per update during the streaming phase of ((poly(log 17, log w, log k)), an approximation 1/2 in expectation, and query complexity 5 of (n) during the precomputation phase.
Note that the query complexity per update during the streaming phase and the query complexity during the precomputation phase both have a polynomial dependence on e. Additionally, note that our update bound is not constant even when the prediction error is O. However, with the following simple change, our algorithm achieves a constant update time when the predictions are exactly correct, while also maintaining its current guarantees: (1) as additional precomputations, also compute a predicted solution St for each time t assuming the predictions are exactly correct, (2) during the streaming phase, as long as the predictions are exactly correct, return the precomputed predicted solution S.. At the first time step where the predictions are no longer exactly correct, switch to our main algorithm in the paper.
7 Experiments
7.1 Experimental Setup
Benchmarks. We compare our DYNAMICWPRES algorithm two benchmarks. The first is the DYNAMIC submodular maximization algorithm of [20], which does not use predictions. The second is the OFFLINEGREEDY algorithm that computes an offline greedy solution $, at each time step & based on the set V, of available items in the predicted stream. In the streaming phase, it outputs the solution S, n V/ at time / based on the available items V,. Note that this algorithm does not make any queries other than the queries used for rreeoopputttion. These benchmarks are at two extremes in terms of their reliance the predictions. DYNAMICW uses the DYNAMIC algorithm of (20) and the ROBUST algorithm of [16] as subroutines. We implemented our algorithm and OnfeeN in C++, and used the C++ implementation of DYNAMIC that is provided by 20
We set c = 0.2 for all algorithms.
Metrics. We report the total number of oracle calls made by each algorithm when processing the actual stream (a, o). This does not include any oracle calls during the pre-computation phase. We also report the average function value 1 Erets) (S,) of the output sets over time steps t [n]] Each experiment is repeated 5 times and the average values are reported.
Datasets and submodular function. We perform experiments on a subset of the Enron dataset from the SNAP Large Networks Data Collection (21]. We select a set V of 200 nodes from the graph, and consider the subgraph induced by V U N(V) where N(V) is the set of neighboring nodes of V. This resulted in subgraph with 7845 vertices and 20033 edges. The submodular function is the dominating set objective function over the ground set V with [V| = 200. Specifically, for subset of nodes S C V. we define f(S) (S) U S), where N(S) is the set of neighboring nodes of S. This function monotone and submodular.
'We note that, despite the amortized query complexity of Lattanzi et al. 20 being in expectation, the asymptotic bound on the precomputation query complexity can hold deterministically. instead of in expectation, terminate if it has performed number of queries that is larger than
by forcing PRECOMPUTATIONSSUL times its expected number of queries (note that the precomputation query complexity only depends on known parameters, n and k). By Markov's 's inequality, such an early termination happens with probability at most e. Thus, even with no guarantees on the approximation achieved in these early termination cases, the loss in the expected approximation caused by this forced termination is at most 1
8

---

Enron: effect of prodiction error
Enroo: offect of cardinality
Earon: effect of window
number of quesies
number of queriis
namber querriis
10%
1041
DysamieWFred
Dynamic Offinnnrredy
10r
101
10
0.6
prediction error: 4
cardinality:
Window size:
Enrou: effeect of predietion errorr
Enrva: effect of cardinality
Earon: edffect of window sise
function value
2000
function value
2400-
2550
B 2000
1200
2003
61 2200
2310
1800
2100
1000
1600
2000
10005
1900
1800
0.0
0.2
E.4
0.6
0.8
1.0
10
15
20
20
30
10
20
25
30
prediction
cardinality:
window size:
Figure 1: The number of queries and function value of our algorithm, DYNAMICWPRED and the two benchmarks for the Enron data and sliding window stream with == 50 function of the prediction error 7) with 10 and (column 2), and as a function of the window size parameter w with 20 and n = 0.125 (column 3).
(column 1), as a function of the cardinality parameter with v = 0.25 and =
Generation of true stream. We consider the sliding window protocol from 20 in order to generate the dynamic stream of insertions and deletions. Specifically, we process the nodes V in an arbitrary order and consider a sliding window of size I. When the window reaches a node a, we add the operation (a, insert) to the dynamic stream. Similarly, after steps when the node a leaves the window, we add the operation (a, delete) to the dynamic stream. Since, |V] 200, we have 400 for all experiments. We report results with 50 (observations were similar for other values of l).
Generation of predicted stream. Given target prediction error 1) and window size w, we generate the predicted stream for our experiments by adding perturbations to the actual stream such that Definition 2 is satisfied. Note that we add these perturbations while maintaining the consistency of the stream, i.c. the insertion of an element always happens before its deletion. In particular, we first select a E of n/2 elements uniformly random and let T denote the set of all insertion and deletion times of these elements in the actual stream. For each e E E, we assign new insertion and deletion times in the predicted stream by randomly drawing from T. We make sure that these new insertion and deletion times are consistent and are at least a distance of w from the corresponding old times. The insertion and deletion times for of E remain the same so far. Now, for each & E, we randomly swap an their operations (e, o) and (e', o') that are within distance of w while maintaining consistency.
7.2 Experiment Results
Experiment Set 1. We first consider the effect of the prediction error 1) on the function value. For ease of exposition, we overload the notation and report the fractional prediction error, i.e. prediction error divided by the length of the stream From the first column of Figure we observe that our algorithm outperforms OFFLINERREEDY in terms of function value when the prediction error reasonably large, and always achieves a similar function value DYNAMIC. Since DYNAMIC does not use the predictions, its performance remains constant as a function of the prediction errors. The performance of OFFLINEGREEDY deteriorates quickly the predictions. Note that the function value achieved by OFFLINEGREEDY is not zero even in the case of large prediction error. This is because the error is not adversarial and some elements from its offline solution remain active during the streaming phase.
function of 17 as it completely relies on
We also consider the effect of on the number of oracle calls. Figure I shows that the number of oracle calls our algorithm much better than DYNAMIC the case of low prediction error, and is also not much worse in the case of large prediction error. This shows that our algorithm has consistency in the case of low 7) but also robustness in the case of large 7). The number of oracle calls of OFFLINEGREEDY is very small as it completely relies on the prediction.

---

Experiment Set 2. We also consider the effect of cardinality parameter &o on the function value and number of oracle calls. It can be observed from the second column of Figure the function value increases for all algorithms as function of k. Moreover, the rate of increase for the number of oracle calls made by our algorithm is similar to the rate of increase of DYNAMIC. Experiment Set 3. We consider the effect of the window size parameter on the function value and number of oracle calls. Figure [ shows that the window size has almost no impact on the function value of our algorithm. The number of oracle calls for our algorithm grows a function of the window size but this growth very small.
8 Limitations
To obtain an asymptotic improvement over the best-known amortized query complexity per update, the prediction error y) needs to be subpolynomial in the length of the stream n, which is relatively small. However, our experimental results show that in practice the number of queries performed by our algorithm outperforms the number queries of existing algorithm without predictions even when the prediction error is relatively large. Another limitation is the assumption that the algorithm is given all predictions at time f 0. An intriguing open question whether an improvement in update time can also be obtained in the preiicedddeeettonn model where there is no preprocessing and instead a predicted deletion time for each element given the time when it is inserted.
References
[1] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: Leveraging predictions for facility location. EC, 2022.
[2] Kareem Amin, Travis Dick, Mikhail Khodak, and Sergei Vassilvitskii. Private algorithms with private predictions. arXiv preprint arXiv:2210.11222: 2022.
[3] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online matching problems with machine learned advice. NeurIPS, 2020.
[4] Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[5] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms,, SODA 2022. SIAM, 2022.
[6] Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, Mohammad Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic constrained submodular optimization with polylogarithmic update time. ICML., 2023.
[7] Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic algorithms for matroid submodular maxi- mization. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3485-3533, SIAM, 2024.
[8] Jeff Bilmes. Submodularity in machine learning and artificial intelligence. arXiv preprint 2rXiv:220..00132, 2022.
[9] Jan van den Brand, Sebastian Forster, Yasamin Nazari, and Adam Polak. On dynamic graph algorithms with predictions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 3534-3557. STAM, 2024.
[10] Xi Chen and Binghui Peng. On the complexity of dynamic submodular maximization. In Proceedings of the 54th Annual ACM SIGACT' Symposium on Theory of Computing, pages 1685-1698, 2022.
10

---

[11] Paul Duetting, Federico Fusco, Silvio Lattanzi. Ashkan Norouzi-Fard, and Morteza Zadi- moghaddam. Fully dynamic submodular maximization over matroids. In Proceedings of the 40th International Conference on Machine Learning, pages 8821-8835, 2023.
[12] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Compulation, pages 409 429, 2021.
[13] Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Streaming submodular maximization under matroid constraints. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl-Lecinniz-Zennte für Informatik, 2022.
[14] Monika Henzinger, Barna Saha, Martin P Seybold, and Christopher Ye. On the complexity of algorithms with predictions for dynamic graph problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss- Schloss-Dagstuhl 2024.
Zentrum für Informatik,
[15] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. Advances in Neural Information Processing Systems, 34, 2021.
[16] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submod- ular maximization: Data summarization with privacy and fairness constraints. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockhollssmsssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages
PMLR, 2018.
[17] David Kempe, Jon Kleinberg, and Êva Tardos. Maximizing the spread of influence through social network. KDD, 2003.
[18] Andreas Krause and Daniel Golovin. Submodular function maximization. Traclubility, 3:71- 104, 2014.
[19] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 1859-1877.S$ SIAM, 2020.
[20] Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub Tarnawski, and Morteza 7adimoghaddam. Fully dynamic algorithm for constrained submodular optimization. Advances in Neural Information Processing Systems, 13:12923-12933 2020.
[21] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap... stanf ord. /ata, June 2014.
[22] Quanquan C Liu and Vaidehi Srinivas. The predicted-deletion dynamic model: Taking advantage of ml predictions, for free. arXiv preprint wxXiv:230700880, 2023.
[23]
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 18:4):2:: 2021.
[24] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In 11th Innovations Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl- Leibniz-Zentrum für Informatik. 2020.
[25] Morteza Monemizadeh. Dynamic submodular maximization. In Advances in Neural Information Processing Systems, 2020.
[26] George Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of submodular set function. Mathematics of operations research. 377) 1978.
[27] George I. Nemhauser, Laurence A Wolsey, and Marshall Fisher. An analysis of approximations for maximizing submodular set functions i. Mathematical programming, 14(1):265-294 1978.

---

[28] Binghui Peng. Dynamic influence maximization. Advances in Neural Information Processing Systems, 34:10718-10753 2021.
[29] Binghui Peng and Aviad Rubinstein. Fully-dynamii-t--nereeesss reductions with known deletion order (eg sliding window). In Symposium on Simplicity in Algorithms (SOSA), pages 261-271. SIAM, 2023.
[30] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predic- tions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018.
[31] Yaron Singer. Budget feasible mechanisms. In 2010 IEEE 51st Annual Symposium on founda- tions of computer science, pages 765-774, IEEE, 2010.
[32] Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. Advances in Neural Information Processing Systems, 33, 2020.
[33] Chenyang and Pinyan Lu. Mechanism design with predictions. In Lud De Raedt, editor, Proceedings of the Thirty-Firss International Joint Conference Artificial Intelligence, IJCAI- 22, pages 571-577. International Joint Conferences on Artificial Intelligence Organization,
2022.
12

---

A Missing proofs from Section
3
Lemma 8. Assume that the predicted stream has, with a time error tolerance w, prediction error at most 1,. Then, at any time step I, IV, \ Vil S 1) 2w.
Proof. Let E = fa E V 1t - t/ > w or F tal w). Hence, for all a & E. we have F tol S w and It- ta I w. By Definition
2 we have that [E] = We first note that any E V \ E such that l S - and - > + also belongs to V,. This is because & E implies that 1ot S f and lg
Hence, the only elements that present in V; E. but are absent from V/2 are such that t > -- w or f S + w. Since, the only elements in V, are such that & S t + w and f 2 w, this implies that there can be at most 2w such elements. Combining with the fact that | = 7,, we get [V. \ Vil S E + 1(V. \ E) \ Vi S + 2w.
Lemma 1. At every time step B[f(8*) (PT and E[f(S²)) 2 02 OPT(V?).
Proof. We first show that at every time step f(S)) 2 OPT(V)). Fix some time step t. First, note that
P. PA (Z - (Pr U = P.n
where the second equality is since P. C Vg. In addition, we have that [ V/"1 = |VAVI S f7-2 = d, where the inequality is by Lemma &
With D VAV. such that [D] < d, R = Pt. and N Vv, we thus have by Definition 3 that the output S of ROBUST2 Ps V. V7, k) ROBUSTS (ʃ, R, k) is such that Sa
C P. n and
E E[f(s') ( a1
max
f(S)
01 max f(S) a1 DPT(V.)) sgv'
SCRAD: Sk
18|
Next, we show that every time step I, (S²) > 02 (V?( Observe that the algorithm
runs the dynamic streaming algorithm DYNAMIC over the sequence of ground sets Vi?.... V/2 . By Definition the solutions returned by DYNAMIC each time step achieve an a2 approximation. Since these solutions are .,...., S. we get that for every time step t, f(?) 2 a2 maxsgv?:1sIsk f(S).
Lemma 9. For any monotone submodular function f NNNN + R. if S and S2 are such that f(S:) on maxxsnNilsis J(S) and ((22 2 02
max J(S), then
max(f(S)), 2 1 min(a1, a2] maxsgN,UNsISISN f(S).
Proof. Let = tor..... ArgDRRKSCMMUMM/SSSE ((S) be an arbitrary ordering of the optimal
elements. We have that
max S(S) f(0)
SCN(UNG
$ lf,, E
(o:) + Σ los E Walf INNs (o:)
S(OON)) +
< max [(S) +
max
S(S)
sENt|Sisk
SCNs:|Sisk
< f(S))/1 + +f(S2//a
(S:)) mminfan, o2)
where the first inequality is by submodularity.
13

---

By combining Lemma] ! Land Lemma we obtain the main lemma for the approximation guarantee.
Lemma 10. At every time step t, max(f( f(()) 2 Y/2 min(a2, OPT(V))
Lemma 2. WARMUP-UPDATESSOI makes at most 21 calls to DYNAMICINS on A over the stream.
Proof. The number of calls to DYNAMICINS is {a s.t. a V? 12 Since V2? V2 = (Vi \ Vi (V-11 V2-1),
: att AV : a (V Vi-1) \ Vil
+|fa st (V-1 [
Next, we have
Ha st. aE (V, \ (--1) MH = :fa:: a Vig
Ma: it > t + or t < m]
Ha t t <t> -w
s Ha 1 - + or to wH
Similarly,
: a E (V-1 nK] = =aaa: E +w
Ifaa t Eo + w/
S Ma [ te w or 1 - - w)
Combining the above incqualities, we get that the number of calls to DYNAMICINS ([a 38 s.t. a E 12,H1
VV\V2, 2n.
Theorem 1. For monotone submodular maximization under cardinality constraint k, Algorithml 7 with the MARMUP-PRECOMPTTAN
and WARMUP-UPDATESOO subroutines achieves, for any tolerance w and constant e >> O, an amorlized expected query complexity per update during the streaming phase of Ö(n + w + k), an approximation of 1 /4 - e in expectation, and a query complexity of (()kk) during the precompulation phase.
Proof. We choose DYNAMIC to be the algorithm from 200 and ROBUST to be the algorithm from
[16] By Lemma 10 and since we have a₁ = a2 = 1/2-c, the approximation is 2 min(as, a1} =
miiff -
For the query complexity during the streaming phase, by Lemma the total number of calls to DYNAMICINS on A is (()). The total number of calls to DYNAMIC DEL on A is also ( since an element can only be deleted if it has been inserted. Thus, the total number of insertions and deletions handled by the dynamic streaming algorithm DYNAMIC is (n)). Since the amortized expected query complexity per update of DYNAMIC Oppoly(log n. log k)), we get that the amortized expected number of queries performed when calling DYNAMICINS, DYNAMICDEL, and DYNAMICSOL on A Onn- poly(log 7,, log k)/n) For the number of queries due ROBUST2, at every time step t, the algorithm calls ROBUST2(f. Pt. (V/) V)). k) with maximum number of deletions = 7 2w, which causes at most Ô (n + w + k) queries at each time step since the query complexity of ROBUST2 is Ô (d + k). The total amortized expected query complexity per update during the streaming phase is thus Ö + w + k). For the query complexity during the precomputation phase, the query complexity of ROBUSTI is (((V(k) and there are n calls to ROBUSTI, 1, so the query complexity of that phase is Ōn)²)).
14

---

B Missing proof from Section
Lemma 3. The DYNAMIC algorithm of Lattanzi et al. 120 threshold-basee
Proof. The first condition that (SOL,) 2 |SOLe] follows directly from the fact that each element e that is added to SOL, has marginal contribution of at least 7/2k to the partial solution. Some elements could have been deleted from the partial solution since the time e was added, but this can only increase the contribution of e due to submodularity.
We will now show that if [SOL.] < (1 - -))k then for any S S ((A,) we have fsaI, (S) 1sh + ETy. We will use the set X defined in the proof of Theorem 5.1 in (0) The proof of Theorem 5.1 in
2x
20 shows that [SOL,] 2 (1 x) Using this, the condition that [SOL;] < (1 c)k implies that
X < k. Hence, we fall the case 2 of the proof of Theorem 5.1 which shows that f(e S 7/2k
for all e Ve \ SOL, We then have that
fsoL, (S) f(S U SOL,) - ( - f(SOL,)
f(SUU) - ((x)
- f(x - -(())+((X (1x))(1-)f(())
- Σ fx(e) +f((x)
<ES
7
1+E
< |S|
+
1-6 7
2k
where the inequality f(X) S He follows because f(x)= S F(SOL)) - e) S I 7.
Lemma 4. Consider the data structure (B, A, Moia) returned by UPDATESOLMAIN at time t. Let t' be the time at which A was initialized, (Qu, Re)) and " be the precomputations and guess for OPT. inputs UPDATESOLMAIN at time t'. If (Qu, Re) are (d 2(Toid + 2w), " --trrongly robust, "y is such that Tt' & OPT, < (1 + eyTu, and DYNAMIC is threshold based dynamic algorithm, then the set S returned by UPDATESOLMAIN is such that E[f(S)] 1-5e
2 yv.
To prove Lemma we first bound the value of Qr O Ve.
Lemma 11. Consider the data structure (B, A, Mola) returned by UPDATESOLMAIN at time Let t' be the time which A was initialized, (Qu,, Re) and "/e be the precomputations and guess for OPT,, imputs to UPDATESOLMM AIN at time V., If precomputations (Qr, (Rr) are (d = 2( + 2w), e, Th) strongly robust, then have
Bif(Qe O V.) 2 (1-c)((O)) 2 (1 1cll (2k).
Proof. We first show that (Qr \ V1l S d. We know that Qu S Vr. Firstly, we have Vy Ve. S Ni + 2w Nol + 2w due to the Lemma Next, note that the number of insertions and deletions Ops" (A) to A between time and / is at most 2 +w, otherwise A would have been reinitialized due to the condition of UPDATESOLMANN Hence, we have that
Tige
start new phase. This implies that Vv. \ Vil 'ooaa + 2w.
Qu \ Vll & ViVe \ Vi $ IiVe \ Av/++ VV \ Vl < 2(7 + -w) =
We conclude that (e n Vi) 2 (1 - (Q+) 2 (1 1) /i where the first inequality is by the robustness property of strongly-robust precomputations and the second by their value property.
Proof of Lemma There are three cases.
Qel 2 k. We have that E[f(S) 2 E (v) (1- 1r- Te' 2 (1 (1-c) Tr' where the first inequality is by monotonicity and since $ 2 BUV - = Qr n V. the second by Lemma II and the last by the condition for this first case.
'Not that the initially published algorithm in 20 had an issue with correctness, we refer to the revised version.
15

---

2. (YNAMICSOL(A)I 2 (1 - c) - Qe1). Let SOL, DYNAMICSOL(A) and recall that
A was initializee with DYNAMICINIT over function fer, with cardinality constraint | and threshold parameter "/ (k: [B1)/k. We get [[((S]]
e n V4) + Jawnv (SOL:)
definition of S
2 E Vi)
fa. (SOL:)]
submodularity
2 (1 1Qpr
'V'
El (SOLz)
Lemma 11
2k
W (k BB)/ SOLe
2 (1 e)
Definition
2k
2(k
[B])
2 (1 1Q
W (1 <) - 1Q=1))
case assumption
2k
2k
(1 e)T
3. QQe k and |SOLe] < (1 e) 1Qel): Recall that Re S Ve. Also, let Rs
U \ Ve). In this case, we have that
f(O,) S(a) E[f(O; SOL, Q+)]
ElJ(SOL, U Qr)) + ElJsoL, (O, \ RR)] + UQ (b) E|S(SOL, U Qr)) + ElSØ, (O, R.)] + EsaL, (O, n R.))
R.)
S(o) E[S(SOL, U 2r)] + |0, Ral
'r'
+ EYe + ElJsoL. (O, n R.))
2k
(a) (SJ U 0r)) + |0, Rd
Yt'
+ 6Yv + +1O0n n Rel "
+ 67y
2k
2k
Yv'
S(e) (SLL, [2 + (1 + 4e)
2
where (a) is by monotonicity, (b) is by submodularity, (c) since (Qr,, Re) are (d 2Tood + 2w) e, Te-) )-strongly robust (value property) and since we have that O R O₂ ((V. ) (V, Vy)) C Ve Rg and Q₂ < k. (d) is since DYNAMIC is threshold- based, |SOL,] < (1 (k [Qrl) D) and Rg S (A), and (e) is since |Ool S k. The above
series of inequalities implies that
E[f(sOL, U UQr1 f(O,) (1 + 4ch
(1 - --4c)
2
2
We conclude that
Ef{(S)] E[f((Qu ( VI)
definition of S
E[f((Qe 0 V1) U SOL,)]
SOL, C V/
2 E[f(Qr ( + [(fQ,
submodularity Lemma 11
2 (1 -c)s(Q)) + (SLL,
> (1 - e) E[/(SOL, U Qr.)
(1 5e 5e
IV
2
Lemma 5. Consider the data structure (B, A, Mold) returned by UPDATESOLMAIN at time t. Let be the time which A was initialized and (Qu, R,,) be the precomputations input UPDATESOLMAIN at time 1'_ If precomputations (Qr,, Re) are (d 2(1jou 2w), e, 7) strongly-robust, then the total number of queries performed by UPDATESOL during the L- (L time steps between time and time I. is (uu(Toota + w + k) log ki k) (Nold + w + k)) log k).. Additionally, the number of queries between time and is upper bounded by O(u(t, k) -t).
Proof. The only queries made by UPDATESOL are due to calls to DYNAMIC. Hence, we calculate the total number of operations Ops(A) between time l' and (. The number of insertions time l' is
Ry V/ + |
(1) O((rsus + k) log k) + |
S(2) O + k) log k) + Vold
= O((7oia + w + k) log k)).
16

---

where (1) is by the size property of the (d = 2(Todd + 2w), c, strongly-robust precomputations and
(2) is since 1V, S ?ie S Ti. Nold-
Moreover, the total number of operations Ops"(A) ((4) between time 1' + 1 and / is at most Motaa 2 + w d/4, otherwise would have been reinitialized due the condition of UPDATESOL.MAIN new phase. Hence, the total query complexity between time t' and time is at most u(O(a + w k) log k) (u + + k) log k, k) (Nold + w + k) log k).
start
k) log k), k 1 1Q=1)) ((Told
In the case 1' = 1, the number of operations at time t' since [Vr 1, and the number of operations from time 2 to is at most t 1. This gives the bound of (utt,, A) when t' 1. 0
C Missing proofs from Section 5
Lemma 6. Let DYNAMIC(Y, <) be the dynamic submodular maximization algorithm of f20) and A be the data structure it maintains. There a ROBUST FROMIDNNAO algorithm such that, given as imput a deletion size parameter d, and the data structure A at time with y S OPT, S (1 e)n, it outputs sets (Q; R) that are (d, 6, (d,,,7)-shn -ttrrnngy robust with respect to the ground set Vz. Moreover, this algorithm does not perform any oracle queries.
Proof. We will first set up some notation. The algorithm of 20 creates several buckets (ALe) [E(T] where R Olog k/e) is the number of thresholds and O(log n) is the number of levels. A solution is constructed using these buckets by iteratively selecting S from Art starting from the smallest (i, E) (0, 0) to the largest (i, E) = T). The buffer level is denoted by Be. Each set S is constructed by iteratively selecting elements uniformly ran- dom (without replacement) from the corresponding bucket. More precisely, given indices i, the algorithm adds elements to the solution S.ee one by one in line 7 of Algorithm 6 in 20 only if (el()) 2 T, 2 7/2k.
We will now show how to construct (Q, R) from the DYNAMIC data structure A. Note that we will extract (Q, R) by observing the evolution of the data-structure Hence, we do not need to make any additional oracle queries in order to extract (Q, R).
The following algorithm gives procedure for extracting (Q, R) by observing the actions of the peeling algorithm (Algorithm 6) in (20).
Algorithm 5 ROBBUSS FRRMUSTFRR
Input: function f 2V + I, dynamic data-structure A, constraint k, deletion parameter
parameter
1: Q + Ø
2: R +++0 0
3: for E [T] do
4:
for E [R] do
5:
if n/2
d
+ k then
6:
Q U..
7: else
8:
R RU A
9:
return R,
We will now show that the conditions required in Definition bby the above algorithm.
Size. The fact that |Q| < follows using the Q S Uce.Sa.E S where S is the solution output by DYNAMIC with |S| < k.
We will now show that the size of R = 0 ( + k)). Let e E [T] be the largest value such that the corresponding bucket size n/22 is at least d/c + k. Recall that
R= Ue (ULEIR) An.)
17

---

We first have that
Wee8 Bil $ Σ
n/22 S 1 +)) -h).
Secondly,
ΣΣ tcl RE(R)
n/2" S 2n/2 0 log ( +k))
log k
UUEEE UsEm
Combining the above inequalities gives us the desired bound on the size of R.
Value. The fact that f(Q) 2 1Qh//kk follows directly using the property of the dynamic algorithm of [20] element is added to Sie during call to Bucket- Bookke-Consttuct(i,, E) only if (c) 2 T2 where т, 2 7/ 7/2k and is the partial solution. is possible that some the elements of the partial solution have been deleted since the last time Bucket-Construn was called on index E), but the marginal contribution of can only increase with deletions due to submodularity.
We now show that, if [Q] < k, then for any for any set S V \ R we have (S) < (2k) + ey. Let Q' denote the set of elements in Q at the time when Level-Construct(() was called last, We have
fQ(S)
S =()) f(Q)
())))
< +e(())
eES
1+6
< |S| 2h
+ 1-6 7
and the inequality (e) S 2/2 follows by considering two cases: (1) was inserted before the latest time const-Construct(() was called in which case cannot have high marginal contribution to Q' as otherwise would have been inserted in Q', (2) e was inserted after the latest time Level-Construct({) was called in which case either has low marginal contribution to Q' or would included in the set R.
where the inequality f(Q") S Itc follows because f(Q') S f(Q)/(1-c)
T-c
Robustness. For any set D V such that |D| s d. Eolf(Q) \D) (1 c)f((Q. We have that
S(Q) =1)==Σ< Σ
Sppartia (eg,a))
E2i jE((S,e)
where c,,, is the j-th element that was added to Siee and Spartial is the partial solution before the j-th element was added. We have that
ΣΣ PZE
Skel 2 f(Q) & (1+6)
ΣΣ
E21 1E|M
18

---

Since, each element in St, is selected from set of size at least d/c, it can only be deleted with probability most We have that
E \ D -
Σ
[el & D) Aagartil (er,ia)
2 je([S,,d)
Σ
E
Σ
Efile $ D) fsparsal (cE,,))
ielm Jells
Σ Σ
Σ
Pr(ecss DD D). T
f2 iE R jE([S,,e]
Σ
Σ
1+ f()) 2 1 1-
Lemma 7. The total query complexity of the PRECOMPUTATIONSMM algorithm is n u(n, k). where u(n, k) is the amortized query complexity of calls to DYNAMIC.
Proof. It is easy to observe that the algorithm makes at most n calls to DYNAMICINS or DYNAMICDEL since E. Vi-1l= \V-1 V/l S n. Hence, the total query complexity due to calls DYNAMIC
u), Moreover. the calls FoBust/FRoMDDNam cur any additional queries due to Lemma 6. Hence, the total number of queries performed in the precomputation phase given by u(n,k).
do not in-
D Missing proofs from Section 6
The UPDATESOLMAIN and PRECOMPUTATIONSAIN subroutines use guesses 7 and h for the optimal value OPT, time / and the total prediction error y). In this section, we describe the full UPDATESOL and PRECOMPUTATIINNSFUI
subroutines that call the previously defined subroutines over different guesses 7/ and h. The parameters these calls must be carefully designed to bound the streaming amortized query complexity per update and precomputations query complexity.
D.1 The full PRECOMPUTATIONS subroutine
We define H (n/2 E (loga(max( (--2w : 1)), (og)(n) 1, loga } be of guesses for the prediction error 77. Since PRECOMPUTATIONSMAN requires guess h for n, PRECOMPUTATIONSSUU.. calls PRECOMPUTATIONSMA. that the minimum guess h is such that h + 2w is least kt The challenge with the guess y of OPT needed for PRECOMPUTATIONSMATT two time steps. Thus, with Vi,..., Vn C V, we define the collection of guesses for OPT to be == ((1 + +) min.ey f(a), (1 + e) min f(a). ...)....... f(V)). which can be an arbitrarily large set.
over all guesses h E H. We ensure
is that OPT can have arbitrarily large changes between
Instead of having bounded number of guesses elements at time for each guess y E T such that for each element is, there is a bounded number of guesses 7 E I such that a E V.(7). More precisely, for any set T, we define T(>) == (a E T ET S f(a) < 2 and r(a) (7 E r (a) 7 S < The PRECOMPUTATIONSFULL subroutine outputs, for every time step 6, strongly-robust sets (Q) h),"), for all guesses 7 E l and h H. If Vi(7)) 0, assume that ?? 0 and R. 0.
consider subset Vi(r) S V2 of the predicted
19

---

Algorithm 6 PRECOMPUTAATONNFULLL
Input: function f. constraint k, predicted active elements Vi...., Vn S V, time error tolerance
w
1: for Y ' such that [V(())] > 0 for some E [n] do
2:
for E H do
{(Q7th R2 ) return {[(Q7. "MET,eeH PRECOMPUTTATIOOSMAAN(1..M (,
4:
Lemma 12. The total query complexity of PRECOMPUTATIONSFULLL is
O(n log(n) log(k) u(n, A:).
Proof. For any E I,, let nt be the length of the stream corresponding to predicted active elements Vi(n),..... V. (7). By Lemma 7 the total query complexity is
Σ ner
H n u(n"nn k) S Σ log(n) 2)((()) (nn
yer
2(log n (n, k) Σ [r(a)
eEV
(log(() u(n, k) n log k).
D.2 The full UPDATESOL subroutine
UPDATESOLFULL takes as input the strongly robust sets (Q h R.?.h)) ). for all guesses H. It maintains a data structure {(B", A", 17 he where (B", A", '7²)) ) the data structure maintained by UPDATESOLMAR
and
over guess for OPT. MADA is called over all guesses y E T such that there least one active element a E Vi(7). The precomputations given input to where T// H is the closest guess in H to
UPDATESOLMAAN with guess y E T are (Q7,% RR,* the current prediction error 77 that has value at least Yęt- Note that 17, is such that v/! + 2w 2 k due to the definition of H. The solution returned time by UPDATESOLFULLA is the best solution found by UPDATESOLMAIN over all guesses 7 E r.
Algorithm 7 UPDATESOL.FULL
Input: function 2V -> R, data structure A, constraint k; precomputations P. {(Q2") R2 ")ee,,e time current prediction error The Vt,, V?2 V,
1: [AT)en & A
2: m/ + mingh E h ne
3: for such that [V((>) > 0 do
A7, UPOATESOLMAINJ,, (Q7 R, (-
4:
5: A 4- {AT}er
6: S erg f(S))
7:
return S
Lemma 13. The UPDATESOLFULD algorithm has, over the time-steps of the streaming phase, an amortized query complexity per update of O (log²()) u(n +.k,, k,)
Proof. For every E I' consider the following stream associated to y: {aa/ ) where (o,, of) = (a, o,) y E T(a:) and (a/, of) = (mull, null) otherwise. null is a dummy symbol denoting absence of insertion deletion. Let n be the number of insertion/dellttinns in this new stream, i.e., n = Σn [[a, * mull].
Using Lemma 5 the total query complexity due to single phase corresponding to a (7, pair is O(u((17 + w k) log k) (17" + + k) log k). Next, note that there a one-to-one mapping between insertions/dellttinn to A at line line 11 of UPDATESOL and elements of the stream
20

---

{(a;, i-) Thus, since phase ends when (Ops" > 122/2 + w. all phases except the last phase process at least 7/¹ / + non-null elements from the stream {(aj, d) Thus, there are at least two phases corresponding to n² then the total query complexity over these v/7 /2 + w non-null > k we have that the amortized query complexity over n² non-null elements is O(u(n) + w + k. k) log k).. We also have that (u((7" + w + k, k) log k) = (uu(n + + k, k) log k) because either 1) + 2w > k which implies that rj" + w = (n + w) or 1j + 2w < k in which case rj² w + k (k)).
elements is (u((17 + w + A.) (177 + w + k) log k
=² ///2+") Since, 17 /2/22/222222
If there is only one phase, i.e. when n² S 1 / w, then the amortized query complexity for the first phase is upper bounded by u(n", k) (uu(n" /2 w. k)). Thus, the amortized query complexity due to y is (u((n + w + k. k) log k), for any E We get that the total query complexity is
Σ I(((n+ w 7ET
+ w n² log k) = -
Σ
O + w + k. k)) log k)
7ET (ET(
Σ
Σ
Ou((+++++ log k))
aEV (ET(a)
Onn k) u(n + w+
D.3
The main result
By combining the algorithmic framework (Algorithm 1 together with subroutines FUDA and PRECOMPUTATIONSFULL. we obtain our main result.
Theorem Algorithm D with subroutines UPDATESOLFULA and PRECOMPUTATIONSFULI is dy- namic algorithm that, for any tolerance w and constant >> O, achieves an amortized expected query complexity per update during the streaming phase of O(poly 17, log w, log k)), an approximation 1/2 in expectation, and a query complexity of (n) during the precomputation phase.
Proof. The dynamic algorithm DYNAMIC used by the PRECOMPUTATIONS and UPDATESOL sub- routines is the algorithm of Lattanzi et al. (00 with amortized expected update time u(n, k) Oppoly(logm, n, log k)). By Lemma 13 the amortized expected query complexity is
O (log2(k) u(n + 2w + k. k)) = O (poly(log(1 + w + log k)).
For the approximation, consider some arbitrary time t. Let y* = max(7 E eT:; S -1- c)OPT)
Let OPT == maxsgw(rrHssss f(8). We have that
OPT 2 f(0,n Zay f(O.)
f(o) 2(2) f(O,) - k 6x oEO:nVa(T")
Σ
2 (1 e)TP,
k
where (1) is by submodularity, (2) is by definition of V1(>*), ) and (3) by definition of n* Consider the calls to UPDATESOL by UPDATESOLFULL with = --,, Let l' be the time at which A," was initialized by UPDATESOL with precomputations (Qr,, Re)) (0) me R² me), where this equality is by definition of UPDATESOLFULL.
Next, we show that the conditions to apply Lemma 4 are satisfied. By definition of PRECOMPUTATIONSFLL and and Lemma 6 RQ) are (d = 2(mk +(w),, e, ( " robust with
respect to V((>*) with y* = wv Since Th 2 ne, we have that (Qu, Ryy) are (d = 2(Too r*). We also have that
T'e (1 - e)PT, OPT, < OPT, < (1+ + (1+))ww(11-
We note that, despite the amortized query complexity of Lattanzi et al. 200 being in expectation, the asymptotic bound on the precomputation query complexity can hold deterministically. instead of in expectation, by forcing PRECOMPUTATIIONSUUL. times its expected number of queries (note that the precomputation query complexity only depends on known parameters, n and k). By Markov's 's inequality, such an early termination happens with probability at most e. Thus, even with no guarantees on the approximation achieved in these early termination cases, the loss in the expected approximation caused by this forced termination is at most 1
terminate if it has performed number of queries that is larger than
21

---

Thus, with c' > 0 such that (1+ (1+e)/(1 e), we get " I OPT S (1 + c' Ye. By Lemma DYNAMIC is threshold-based algorithm. Thus, all the conditions of Lemma are satisfied and we get that the solution S7 returned by the call to UPDATESOL with y = y at time
where A7" was initialized by UPDATESOL at time t' with 7 y², is such that E[f(s? ]] > 1-5c' Y* (1 - c) 1- OPT,, Finally, since UPDATESOLFULL returns, among all the solutions
2
returned by UPDATESOL. the one with highest value, it returns a set St such that E[f 2
([f(s?") }] 2 (1 أطا OPT, Finally, the precomputation query complexity by Lemma 12 with u(n, k) = Oppoyy(log n, k)).
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical contributions mentioned in the abstract and introduction are formalized theorems with complete proof's and perform experiments validating the theory.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: discuss the limitations separate section. The computational efficiency of the proposed algorithms is clearly stated in the main theorems.
Guidelines:
The answer NA means that the paper has 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 "I "Limitations" section in 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 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 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 to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
23

---

Answer: [Yes]
Justification: We provide a comprehensive proof for all the theoretical results and state all the assumptions.
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 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 encouraged provide short proof sketch to 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 properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results 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 not)?
Question:
Answer: [Yes]
Justification: all the information needed for reproducibility of the experimental results is included.
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 to either make it possible for others to 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 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, other means that appropriate to the research performed.
also be provided via detailed
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 it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(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 reprodueibility may be tricky in some cases, in which authors are welcome to describe 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 or verifying the results.
5. Open access to data and code
24

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We are not submitting the code because one of the libraries we extensively use/modify requires several conditions for distributing derivatives of their library. We did not have time to satisfy all these conditions before the deadline. However, we have carefully read these conditions and will definitely be able to meet these conditions before the potential camera-ready deadline, at which point we would release our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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
/nips..cc/ublic/guiddes howpeeee/oooeeeueeeiiiiioeneeee
for more details.
The authors should provide instructions on 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 new proposed method and baselines. If only subset of experiments 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 as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies all the information about the dataset and hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: we only conduct small scale experiments to validate our theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
25

---

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, or 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).
It 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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог 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 or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: we only compute small scale experiments which can be run within a few minutes on CPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 well 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
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httups:/neurips.c cctpiiiss.ccpppppcpccc http://wwwpppp..ppp../.chcccccaa
Answer: [Yes]
Justification:
We follow the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 a special consid- eration due to laws 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: [No]
Justification: the main contribution of this work is theoretical and we do not anticipate any negative societal impact of our model.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
26

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 as 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 or 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:
Our experiments pose no such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
we cite the code due to 20 used in our work and we respect the license of use.
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 dataset.
The authors should state which version of the asset used and, possible, include URI.
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.
27

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information 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 are released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
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 details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing involved.
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information 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 to 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No crowdsoureing involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
28

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "XjkME2zOU3", "reviewer": "Reviewer_L8zN", "summary": "This paper studied the dynamic submodular maximization problem with predictions. The goal of the problem is to maintain a high-quality solution in the presence of insertions and deletions. The main contribution is leveraging predictions, in the form of the pattern of insertions and deletions, to accelerate the update time of dynamic submodular maximization algorithms.", "questions": "Please refer to the weakness section.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to read. The proposed solution and analysis, especially the connection to the robust submodular maximization problem, are technically sound.\n2. The results improve upon existing ones when the prediction is accurate.", "weaknesses": "1. The paper does not provide enough details on how predictions are obtained in real life. For example, it lacks specific information about machine learning algorithms that could potentially be used to make the predictions. This is concerning because the current notation of prediction error is defined in a worst-case manner. If there exists one prediction with poor accuracy, it might dramatically hurt the results. To fully benefit from their results, a very robust and stable prediction algorithm is required.\n2. The tightness of their results is unclear. As mentioned in the introduction, if the prediction is 100% accurate, there exists a trivial algorithm that requires constant update time. However, even with zero prediction error, their bound does not reduce to a constant.\n3. A more natural benefit of predictions is achieving an enhanced approximation ratio. While the authors mention existing studies along this direction, it is worth exploring whether predictions can improve the approximation ratio, using the same update time as algorithms without predictions.\n4. Generally, incorporating predictions often sacrifices worst-case performance, which is especially true if the prediction is inaccurate. It would be beneficial for the authors to comment on this, specifically addressing to what extent bad predictions might hurt the update time of their algorithms.\n5. The last comment is more of a clarification question instead of a comment. In the dynamic setting, why not simply use the state-of-the-art offline algorithm, such as the classic greedy algorithm, to solve the maximization problem in each round? I understand that this might incur higher update time, but if we consider a special case of the dynamic setting where there is only one round, it seems that the update time cannot be lower than the state-of-the-art offline algorithm. Is there any assumption regarding the length of the time horizon, for example, the number of rounds must be at least O(n)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments! \n\n- *“If there exists one prediction with poor accuracy, it might dramatically hurt the results.”*\n\nWe believe that there might have been a misunderstanding about the prediction error. The prediction error is the number of elements whose predicted inserted and deletion times were not sufficiently accurate. In particular, if the predicted inserted and deletion times of one element are completely wrong, then this only increases the prediction error eta by one. Thus, it is not the case that “if there exists one prediction with poor accuracy, it might dramatically hurt the results.\"\n\n\n- *“The paper does not provide enough details on how predictions are obtained in real life.”*\n\nRegarding how predictions could be obtained, consider the product recommendation application where a platform only wants to display items that are in stock. Platforms often have accurate predictions about when an item will go from in-stock to out-of-stock (due to current inventory and rate of purchase) or from out-of-stock to in-stock (due to inventory information provided by seller).\n\n\n- *\"The tightness of their results is unclear. As mentioned in the introduction, if the prediction is 100% accurate, there exists a trivial algorithm that requires constant update time. However, even with zero prediction error, their bound does not reduce to a constant.\"*\n\nThe reviewer is correct that our update bound is not constant even when the prediction error is zero. With the following simple change, our algorithm achieves a constant update time when the predictions are exactly correct, while also maintaining its current guarantees: (1) as additional precomputations, also compute a predicted solution S_t for each time t assuming the predictions are exactly correct, (2) during the streaming phase, as long as the predictions are exactly correct, return the precomputed predicted solution S_t. At the first time step where the predictions are no longer exactly correct, switch to our main algorithm in the paper.\n\n\n- *\"A more natural benefit of predictions is achieving an enhanced approximation ratio. While the authors mention existing studies along this direction, it is worth exploring whether predictions can improve the approximation ratio, using the same update time as algorithms without predictions.\"*\n\nWe agree that using predictions to improve the approximation is also an interesting direction. We note that the best potential improvement we can hope to achieve with a polynomial-time algorithm is to go from 1/2 to 1-1/e, which is the best approximation achievable in the offline setting.\n\n\n- *\"Generally, incorporating predictions often sacrifices worst-case performance, which is especially true if the prediction is inaccurate. It would be beneficial for the authors to comment on this, specifically addressing to what extent bad predictions might hurt the update time of their algorithms.\"*\n\nAs mentioned in lines 86-87, even when the prediction error is arbitrarily large, the update time of our algorithm asymptotically matches the O(poly(log n, log k)) amortized expected query complexity from Lattanzi et al.. Thus, asymptotically, incorporating predictions does not cause our algorithm to sacrifice worst-case performance in comparison to this previous work.\n\n\n- *\"The last comment is more of a clarification question instead of a comment. In the dynamic setting, why not simply use the state-of-the-art offline algorithm, such as the classic greedy algorithm, to solve the maximization problem in each round? I understand that this might incur higher update time, but if we consider a special case of the dynamic setting where there is only one round, it seems that the update time cannot be lower than the state-of-the-art offline algorithm. Is there any assumption regarding the length of the time horizon, for example, the number of rounds must be at least O(n)?\"*\n\nThere is no assumption regarding the length of the time horizon. As mentioned by the reviewer, simply using offline greedy in each round would lead to slower update time. We note that the notation n in dynamic submodular maximization refers to the length of the stream (and not the size of the ground set). We also note that, since it is assumed that at time t=0 there are no active elements, the total number of elements that can be active at any time t is at most t. If there is only one time step (which is what we believe the reviewer means by “only one round”), then there is at most one element that was inserted and the maximizing problem over one element is trivial.\n\n\nWe believe that we have addressed all the reviewer’s concerns. If there remains any concern, we would be happy to answer those during the reviewers-authors discussion phase.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ViNOzjdwno", "reviewer": "Reviewer_A7Fx", "summary": "The paper studies the monotone dynamic submodular maximization problem under a cardinality constraint $k$ in the framework of algorithms with predictions. The authors consider a prediction model where the insert and delete times of the elements are predicted at time 0, and for any window size $w$, the prediction error $\\eta$ is defined to be the number of elements whose actual insertion or deletion times differ from the predicted insertion or deletion times by more than $w$. Their main result is an algorithm that produces a $(1/2-\\epsilon)$-approximate solution at each time step with expected amortized update time $O(\\text{poly}(\\log \\eta, \\log w, \\log k))$ and preprocessing time $\\tilde{O}(n)$.", "questions": "* Why is not the algorithm with update time $O(k \\cdot \\text{polylog}(k))$ presented in [7] compared to your learning-augmented algorithm theoretically or empirically?", "limitations": "The authors state their theoretical results formally, describing all assumptions.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The problem studied is important and interesting to the NeurIPS community\n* The result is strong, and the prediction model and the notion of error are natural. The algorithm is robust in the sense that it can handle an arbitrary number of elements with low prediction error (that fall within the $w$ window of their actual insertion/deletion time) and a reasonable number of elements with high error (whose predictions are off by more than $w$, counted by $\\eta$). Moreover, their algorithm can handle elements that are not predicted to arrive but actually show up in the input sequence (these elements contribute to $\\eta$). The performance of the algorithm also degrades gracefully as the prediction error increases.\n* While the subject is inherently complicated as there are lots of parameters involved, the authors did a good job keeping everything clear and precise so that it is relatively easy to follow. The notation is also good. Moreover, the warm-up algorithm helps the reader understand some of the main ideas of the final algorithm.", "weaknesses": "* In the case where $k = o(\\log n)$ and the prediction error $\\eta = \\Omega(n)$, the update time of the algorithm is worse than the update time $O(k \\cdot \\text{polylog}(k))$ achieved in reference [7]. Thus, in some cases, the algorithm performs worse than a worst-case algorithm without predictions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments! \n\n- *“In the case where k=o(log⁡n) and the prediction error η=Ω(n), the update time of the algorithm is worse than the update time O(k⋅polylog(k)) achieved in reference [7]. Thus, in some cases, the algorithm performs worse than a worst-case algorithm without predictions.” and “Why is not the algorithm with update time O(k⋅polylog(k)) presented in [7] compared to your learning-augmented algorithm theoretically or empirically?”*\n\nThe reviewer is correct that there are cases where our update time is worse than the update time O(k⋅polylog(k)). Our main goal was to achieve a worst-case update time that is at most the O(poly(log n, log k)) update time achieved by Lattanzi et al.. We believe that achieving a worst-case update time that is at most the O(k⋅polylog(k)) update time achieved by Banihashem et al., while also achieving an improved update time when the predictions are accurate, is an interesting open question. At the time when we performed the experiments, the paper by Banihashem et al. was not online yet. We plan on adding their algorithm as a benchmark for our experiments in the next version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8xEMHkDJUo", "reviewer": "Reviewer_T4wq", "summary": "The authors studied monotone submodular maximization under a cardinality constraint in a dynamic model where predictions of insertions and deletions are given. In submodular maximization, a ground set of elements and a function assign a value to any subset of these elements. A function is submodular if adding an element to a smaller set contributes more value than adding it to a larger set. A function is monotone if its value always increases with the set size. In the dynamic model, elements are inserted and removed, and only elements that are inserted but not deleted can be selected. The error $\\eta$ is defined as the number of elements whose actual insertion or deletion time differs from the prediction by at least ww. The goal is to find, after each update, a subset of size at most k from the current elements that maximizes the value of the monotone submodular function while minimizing the number of query calls.\n\nPrevious works on dynamic monotone submodular maximization under cardinality constraints (without predictions) achieve a 1/2 approximation factor using O(polylog(n)) or O(k⋅polylog(k)) query calls. There are also works on dynamic monotone submodular maximization with predictions under matroid constraints, which is a generalization of cardinality constraints, achieving a ∼0.32 approximation factor. In this paper, the authors design an algorithm for dynamic monotone submodular maximization under cardinality constraints using predictions that achieve a 1/2 approximation factor with only $O(poly(log(\\eta),log(w),log(k)))$. When the predictions are poor, the algorithm’s complexity is as bad as the algorithm without predictions, having O(polylog(n)) query complexity since $\\eta$ would become $\\theta(n)$. \n\nThey use precomputation to compute a solution based on predictions for each time and leverage previous works on the dynamic model and delete-robustness model to update their solution according to real insertions and deletions. They also run experiments, comparing their query complexity with the dynamic algorithm. The results show that when prediction errors are small, their algorithm requires significantly fewer query calls. However, when the predictions are poor, the query complexity is comparable to that of the dynamic algorithm.", "questions": "I see that you mentioned Chen and Peng [10] proved that a dynamic algorithm for this problem needs poly(n)poly(n) query complexity, but does their approach apply when we have good predictions? I understand this question may be difficult and don’t expect the authors to answer it, but if they can answer affirmatively, it makes their result much stronger.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Recently, many learning-augmented algorithms have been developed for dynamic and online models. They are interesting because, in real applications, we sometimes have an idea of how elements will change, raising the question of how we can improve our algorithms by leveraging these predictions. In this work, the authors improved the query complexity, eliminating the dependency on n and reducing the dependency on k to only logarithmically. It is interesting how query complexity can be improved using predictions, and it would be even more interesting if the approximation factor could also be improved.", "weaknesses": "There were different algorithms for this problem without using predictions: one using O(polylog(n)) (first algorithm) and the other using O(k⋅polylog(k)) (second algorithm) query calls. Since the authors' algorithm has polylog(k) in its query complexity, if k is as large as $\\theta(n^\\epsilon)$ where $\\epsilon$ is a constant, their algorithm is not better than the first algorithm. If k is small, the second algorithm is not that bad. Still, in the second case, the authors' algorithm is slightly better, but we should note that they also have O(n⋅polylog(n)) for precomputation.\n\n## Comments for the authors:\n- Line 37: cited [30] twice\n- Some sentences are too long and make it hard to read. For example, look at the sentences from lines 60 to 63, and the next sentence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments!\n\n- *\"Line 37: cited [30] twice\"*\n- *\"Some sentences are too long and make it hard to read. For example, look at the sentences from lines 60 to 63, and the next sentence.\"*\n\nThank you, we have fixed the double citation and shortened these sentences to “A dynamic algorithm with predictions consists of two phases. During the precomputation\nphase at t = 0, the algorithm uses the predictions to perform queries before the start of the\nStream. During the streaming phase at time steps t > 0, the algorithm performs queries, and uses the precomputations, to maintain a good solution with respect to the true stream. In this model, there is a trivial algorithm that achieves a constant update time when the predictions\nare exactly correct and an O(u) update time when the predictions are arbitrarily wrong. Here, u\nis the update time of an arbitrary algorithm A for the problem without predictions.“\n\n\n- *\"I see that you mentioned Chen and Peng [10] proved that a dynamic algorithm for this problem needs poly(n) query complexity, but does their approach apply when we have good predictions? I understand this question may be difficult and don’t expect the authors to answer it, but if they can answer affirmatively, it makes their result much stronger.\"*\n\nThe result from Chen and Peng that shows that poly(n) query complexity per update is necessary to achieve an approximation better than 1/2 does NOT hold when we have perfect predictions. In particular, it is possible to precompute solutions S_t that achieve a 1-1/e approximation for each time step during the precomputation phase and then use these solutions during the streaming phase while having 0 queries per update when the predictions are exactly correct. It is an interesting question for future work whether a 1-1/e approximation with an update time faster than poly(n) can be achieved not only when the predictions are exactly correct but also when the prediction error is small.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JqNJYUjW5S", "reviewer": "Reviewer_a2JE", "summary": "Authors consider submodular maximization with cardinality constraint\nin dynamic setting: Algorithm sees a series of $n$ insertions and deletions\nof elements and has to maintain a subset of active elements\nmaximizing given submodular function.\nBest known algorithms for this problem by Lattanzi et al., Monemizadeh,\nand Banihashem et al., achieve approximation ratio 0.5-eps\nwith amortized update time polylogarithmic in $n$ and $k$, where\n$n$ is the length of the input stream and $k$ denotes the cardinality\nconstraint.\n\nIn this paper, authors propose an algorithm which receives predictions\nabout insertion and deletion time of each element beforehand.\nThis allows the algorithm to precompute an update strategy assuming that the\npredictions are correct.\nGiven a parameter $w$, authors define the prediction error $\\eta$ as the number\nof elements whose predicted insertion or deletion time is not within\n$w$ time steps from the real one.\nTheir main result is an algorithm with approximation ratio 0.5-eps\nwhose amortized update time is polylogarithmic in $\\eta$, $w$, and $k$.\nWith $\\eta = o(n)$, their algorithm achieves an assymptotic improvement\nover the existing algorithms which do not use predictions.", "questions": "* where does dependence on epsilon appear in your bounds in Theorem?\n* is the algorithm of Lattanzi the only existing algorithm which is\nthreshold-based, or is this property more common among existing techniques?", "limitations": "Clearly explained.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* result seems strong and requires introduction of new ideas as well\nas proving new properties about existing algorithms", "weaknesses": "* the predictions used are quite verbose:\nhaving all predictions ahead of time is quite a restrictive requirement.\nAuthors pose utilization of predictions which come one by one as an open\nproblem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments!\n\n- *\"where does dependence on epsilon appear in your bounds in Theorem?*\"\n\nOur approximation is 1/2 - epsilon. In addition, the query complexity per update during the streaming phase and the query complexity during the precomputation phase both have a polynomial dependence on epsilon.\n\n- *\"is the algorithm of Lattanzi the only existing algorithm which is threshold-based, or is this property more common among existing techniques?*\"\n\nAlgorithms that used threshold-based ideas are very common in submodular maximization. One of the first such algorithms is by Badanidiyuru-Vondrák in their 2013 paper on “Fast Algorithms for Maximizing Submodular Functions:.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Most of the reviewers agreed that the paper makes a strong theoretical contribution to learning-augmented algorithms for submodular maximization. The problem studied is well motivated and the contribution is relevant to the community. The reviewers also noted several weaknesses of this work, notably that there are relevant parameter regimes where the algorithm performs worse than worst case algorithms without predictions. Additionally, although the prediction model is natural, one of the reviewers noted that the paper does not address how to obtain predictions in practice. Overall, the strengths of this paper outweigh its weaknesses.
Decision: Accept (poster)