Differential Privacy on Fully Dynamic Streams
Authors: Yuan Qiu
Ke Yi
Venue: NeurIPS 2025 spotlight ()
Keywords: Differential Privacy
Linear Queries
Fully Dynamic Streams
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: A fundamental problem in differential privacy is to release privatized answers to a class of linear queries with small error. This problem has been well studied in the static case. In this paper, we consider the fully dynamic setting where items may be inserted into or deleted from the dataset over time, and we need to continually release query answers at every time instance. We present efficient black-box constructions of such dynamic differentially private mechanisms from static ones with only a polylogarithmic degradation in the utility.

Differential Privacy on Fully Dynamic Streams
Yuan Qiu
Ke Yi
School of Cyber Science and Engineering Southeast University Nanjing, China 211189 yuangiu@seu. edu.
Department of Computer Science and Engineering Hong Kong University of Science and Technology Hong Kong SAR, China 999077 yike@cse ust .k
Abstract
A fundamental problem in differential privacy is to release privatized answers to a class linear queries with small error. This problem has been well studied in the static case. In this paper, consider the fully dynamic setting where items may inserted into or deleted from the dataset over time, and we need continually release query answers at every time instance. We present efficient black-box constructions such dynamic differentially private mechanisms from static ones with only a polylogarithmic degradation in the utility.
Introduction
In the data streaming model, a stream consists of a pair of possibly infinitely long vectors (5, Ø). It defines a dynamically changing dataset Dr, which is multiset of elements from a universe X. Initially, Do 0. At time E N+, (1) arrives, where s; E {+--, indicates the operation and E X' is the relevant element. Then D, is defined inductively as follows:
If 8, = +, then D. == Di-1 { i.e., one copy of z; is inserted into the dataset.
If
then D; Di-1 (#+) ), i.e., copy of is deleted from the dataset (it is required that at least one copy of Ia exists in D.-1).
If s, = L. then D. = D,-1.
Two variants of the streaming model have been considered in the literature 25 5
The model above referred to as the fully dynamic setting (a.k.a. a. the turnstile model), while the case where 8, can only be + 1 is called the insertion-only setting (a.k.a. the cash register model).
fundamental problem in differential privacy (DP) how answer class of linear queries on given dataset D privately and accurately. In particular, the private multiplicative weights mechanism (PMW) [5, can answer a set of arbitrary linear queries with maximum erro ((V)D)). Better error bounds can achieved the class queries exhibit good structures. For instance, d- d-dimensional half-space queries can be answered with error Ó(D da [26]: please see Appendix A for a review of results on various query classes. Note that, since there can be many queries in the class, these algorithms do not return the query answers explicitly; instead, privatized data structure (e-g., a histogram the case of PMW) is often returned, and data analyst. can subsequently extract the answer of any query from the data structure.
Combining the query-answering problem and the data streaming model naturally gives rise the problem of differential privacy under continual observation, first studied in the foundational work of Dwork et [9. Here, the goal is to continually release privatized query answers under the following requirements:
'The Ô notation suppresses dependencies the privacy parameter and polylogarithmic terms.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Online: For any t, we must release a data structure (D;) before (st-1, 2(+1) arrives.
Private: All released data structures (D)) (D2). jointly satisfy DP.
Accurate: For every I, all queries D, be answered from M() (D,)) with small error, ideally matching the error in the static case, i.c., as if all queries were answered D, one-shot.
Efficient: The mechanism should run efficiently.
The pioneer work has only studied the basic counting problem, i.e., the query just asks for [Dll under the insertion-only streaming model. However, we observe that their algorithms are actually Macc-boxed and can be instantiated with any static mechanism for some other query class, as long the queries are union-preserving. with polylogarithmic-fccto increase in the error bound. Formally, a query f is called union-preee peiie-pres if f(D(I) w D(2) = f(D(1) + f(D(2)) for any datasets D D where wi denotes the multiset union. For example, by plugging in PMW, any class of linear queries on D, can be answered with error ((V)D+ for every t. Perhaps not realizing this, [6] presented a white-bos box version of PMW for the insertion-only streaming model, but the error ((D,, [3/4). They also showed black-box solution, but the error D((D,15/)) when instantiated with PMW.
standard approach dealing with the fully-dynamic case is to divide the stream into insertion- only steams: one only containing insertions and one only containing deletions but treating these deletions as insertions. Let D == Wigt..,++ {æ;} be all items inserted up to time t, and D, := -igtts.-- {aa} } all items deleted up to time I, then D. = D - DJ_ For any union-preserving query f. we have f(D,) = f(D+t) f(D,), ), so we can run two separate instances of the insertion-only mechanism, and use their difference answer f Dr. However, the worst-case error of this solution is very bad. Suppose we instantiate the insertion-only algorithm of [9 with PMW. Then f(Dt)
respectively, which means and f(DT) can be answered with error Ô (VIDt) and Ô (VID.T
that the error for f(D.) is Ô (VID! + I This can be arbitrarily worse than the optimal error of Ō (DT.) in the static case: D and D; may both be very large but D. - 0.
Our Contributions. In this paper, we present a black-box algorithm for dully-dynamic streams that can answer any class of umion siiio-preservvng queries with error matching that in the static case, up to polylogarithmic factors. For instance, when instantiated with PMW, our algorithm achieves an error of Ó( D(VlD,)) for every Furthermore, its total running time up to time t is also just polylogarithmic factor higher than that of the static mechanism run on all the stream elements up to time I.
2 Preliminaries
2.1 Differential Privacy
Let X' be the universe of items. A static dataset is multiset of items D N Two static datasets D. D' E N are neighbors, denoted D ~ D', ,, if there exists an item x E X' such that D = D' u {x} or vise versa. Differential privacy (DP)
defined as follows.
Definition 1 (Differential Privacy 8 ). A randomized mechanism M: N y satisfies OD
for any neighboring datasets ~ D' and any subset of outputs Y C y,
Pr[M(D) E < ef Pr(M(D') EY)
In the streaming setting. two streams neighbors if one has one more update, which can be either an insertion or a deletion, than the other [9] Formally, two streams (3, क) and (8", x") neighbors, if 3i E N+ such that (5).z)) (5 z() for any * i, and either s; s is L. Plugging this neighboring relationship into Definition yields the DP definition for the streaming model. More precisely, M(D) and M(D') in [ are replaced by (M), (D2), and (D'),, (D))...) respectively, where D, and D' are the datasets induced by any two neighboring streams at i.

---

An important property used in designing DP mechanisms is composition, which comes in two settings:
Theorem 2 (Sequential Composition B)). Let M; N + Yr each be an (Es, 6;) mechanism.
Then the composed mechanism DD) (Mi(D)....... Mc())) is EE Ei, Ex= 6t)-
Note that there are many "advanced" versions of sequential composition Io 21 2 with better
dependencies on k. Nevertheless, as & is logarithmic in all of our algorithms, those advanced versions do not offer better bounds for the problem studied in this paper.
Theorem 3 (Parallel Composition (24)). Let = U1 U... UU, be purtitioning of the universe U. and M₁ : No.. + Yi, each be an (E4, 6,) mechanism. Then the composed mechanism M(D) = (M1 (L)). MM (U))) is (max² C2 max; (
U...UUk
2.2 Linear Queries
A linear query is specified by a function f: X - [0. 1]. The result of evaluating f on D is defined as f(D) =
EreD fx). A fundamental problem in differential privacy is the following: Given set of linear queries F = {fi.... .f....... firi), design DP mechanism M that, on any given D, outputs data structure M(D), from which an approximate (D) can be extracted for any f E F. We say that M has error with probability 1 - B, if
Pr
max feF
[M(D)- (((D)--(D)) S(D) > S
for any D, where the probability taken over the internal randomness of M. Clearly, a is function of the privacy parameters (s, 5) and the failure probability B. For most mechanisms, it also depends on the data size [D) number of queries [Fl, and domain size | To simplify notation, we often omit some of these parameters from the full list a 6, 3, D [FF,, (2')) if they are clear from the context. Similarly, we denote the running time of the mechanism by time([D).>) which depends on the data size [D] and possibly other parameters.
There is extensive work (30 15 17 29
the best achievable for various families of linear queries. This paper takes a black- box approach, i.e., we present dynamic algorithms that can work with any M that has been designed for queries JF on a static dataset D. The error for the dynamic algorithm will be stated in terms of the a function of the mechanism M that is plugged into the black box. Nevertheless, we often derive the explicit bounds for the following two most interesting and extreme cases:
14
22
23 26
Basic counting. If F consists of a single query f(-) = 1, which simply returns f(D) |D], then the "data structure" " MMD) consists of just one number, which is a mosse-masked S(D). The most popular choice of the noise is a random variable drawn from the Laplace distribution )ap())) Its
error function a is given by LLap(e, B) O ( log 1). Alternatively, one can add Gaussian
noise, which is (e, 8)-DP for 8 > 0 and yields OrGanss (c, 5) = O (Lvlog log _/ log 3) The two error bounds are generally incomparable, but the former is usually better since 8 < 8 in common parameter regimes. Both the Laplace and the Gaussian mechanism have Lime([D)) = O(DD).
Arbitrary queries. If F is set of arbitrary linear queries, then the private multiplicative weights (PMW) [1 17 mechanism achieves aPMW ((((D)) for 8 > 0 and ((ID)2/3) for 8 0. These
error bounds are optimal for [F] sufficiently large. The running time of PMW is Ō(ID) + [FI [D|2/a²).
There are many possibilities between the two extreme cases, and the achievable error bound intricately depends on the discrepancy of the query set F [16, 26). We include a brief review in Appendix A which is not necessary for the understanding of this paper. We make reasonable assumption that a does not depend on any of its parameters exponentially, which allows us to ignore the constant coefficients in the parameters, e.g., (<)())) is asymptotically the same a(e). This assumption holds for most existing mechanisms for linear queries.
NNote that the "universe" 24 above is not necessarily the same as the universe X' of stream items. In fact, in our algorithms, we often take 24 as the time domain, and parallel composition then implies that running an (e, 5)-DP mechanism in each disjoint time interval satisfies (e, 6DDP over the entire stream.
3

---

2.3 Differential Privacy for Insertion-only Streams
The insertion-only algorithms. as well as our fully dynamic algorithm, work by decomposing D D(2) H ..... D(R) for some k; so I(D) = ((D() +
[(D(k) by the union-preserving property. Thus, if the error of each (D(() is a(-, B), the error of f f(D is at most k a by union bound. Further, if the estimates of ((D()) are unbiased with good concentration properties, this bound can be tightened. For example, for the basic counting query I(D) = ID], if we use the
Laplace mechanism to estimate each f (D()). then the error for fDD is O (t ( A } + log
which is better than k- k-apap(- (. 3/kk) - O ( log + We derive this result, as well as the error bounds of some other mechanisms under such a disjoint union, Appendix B the main text, for generality we will use (k) denote this error bound. Note that (A) is also a function of [D],e, e, 6, 8, [F1, |X) but we may omit these parameters when the context is clear. Using this notation, the result of existing insertion-only algorithms can be restated as follows.
Lemma 4 4.. For a set of union- preserving queries F, let M: N + be (E,5)-DP static mechanism whose error is a(E, 5, 33, ID), [ on any D, with running time time( Then there is an (e, 5-D mechanism My, ine for insertion-only streams, so that at any time it answers
queries F on Dr with error
Ale 6, 1T. = (logg)
(1e
log 1.' log 1." 8. 8.1.1..111111.
E
5
The total running time of My,ins up to time t is Olog t) time( Drl).
Our algorithm will also use special case of Lemma 4 when F is the basic counting query. Plugging
in our bound on Lap better than that in [].
(R) in Appendix B leads to the following explicit error bound, which is slightly
Corollary 1. There is an E-DP mechanism inst,ins that at any time t, answers the counting query f(D,) = |Dil on an insertion-only stream with error
(log t)
(8o (000'o111
log'
1.5
log t 1 3 log 3
I log
Tonn
Gi.ap
Tog
3 Differential Privacy on Fully Dynamic Streams
In this section, we describe our algorithm for answering a set of union-preserving queries on a possibly infinite fully dynamic stream under differential privacy. We use n, == |D, to denote the size of the dataset at time f, and N, to denote the total number of updates up to time f. Note that for an insertion-only stream we have ni Nr, but fully dynamic stream ne may be much smaller than N,. Our goal to achieve an error bound that depends on 7i,
We will treat fully dynamic stream as a set of labeled time intervals. An interval [i..] labeled with item z e X represents that a copy of x is inserted at time i and deleted at time j. It is possible that j = oc, if the item is never deleted. Note that this interval representation of a stream is not unique, e.g., when many copies of the same item are inserted and then deleted. Any representation can be used; in fact, our algorithm does not use this interval representation, only the analysis does.
Using the interval representation, D. consists of all items whose intervals are stabbed by i.e., all intervals (i,.)) э t. We will make use of the interval tree 77 to organize all the intervals. In an interval tree, each D, is decomposed into a logarithmic number of subsets, each of which consists of one-sided intervals, which will allow us to use the insertion-only mechanism. However, there two technical difficulties in implementing such plan. First, the intervals fashion, i.c., at time t, we only see the endpoints of the intervals prior to t. When we see the left endpoint of an interval, we do not know where in the interval tree to put this interval, yet, we need to immediately release privatized information about this interval. Second, the interval tree on an infinite stream is also infinitely large, so we have to build it incrementally, while allocating the privacy budget appropriately.
given in an online
For running time, is often assumed that no-ops in the stream be skipped cost.

---

We describe how to overcome the difficulties above in Section 3.1 In Section 3.2 we introduce DP mechanism running at each node of the new tree structure support querying at any time with respect to intervals stored in the tree. The output of the whole mechanism is obtained by combining the individual mechanisms at the tree nodes, which is summarized in Section 3.3
3.1 Online Interval Tree
We first build a binary tree T over the timestamps, where each timestamp corresponds to a tree node. Figure I shows an (offline) interval tree built on the first timestamps. It is clear that the tree on timestamps (1,...,4} 44 has L nodes and O(log 1) height. In the online setting, T will grow from left to right. We order the nodes using in-order traversal of T: 0 U2....; and will release the information about e2 right after time i.
Ignoring differential privacy for now, let us first focus on how to answer stabbing query using an interval tree, i.c., report all items (intervals) in the dataset Dg at query time q. In a standard interval tree, an interval is stored the highest node U/ such that its timestamp t stabs the interval. Denote by D(v) the set of labeled intervals stored at U. For example. ((v)) = fa, b, c} in Figure Given a query at time q. follow the noot-to-node path 2gg in T. For each left node vy on the path where I q. we find all intervals [i ) in D(er) such that j > q; for each right node er on the path where
r 4, we find all intervals (i in (v,,) such that S q. Standard analysis on the interval tree shows that these subsets form a disjoint union of all intervals stabbed by q-
Example (Interval Tree Query). Given the interval free in Figure [ assume a query is issued at time 6. We follow the path (v6, U1, Us....). Along the path, U2 is on the left, where a, E D(v,) are deleted after q = 6; ug on the right, where d E D(us) begins at (or before) q 6. Thus we report Ds = {a, d], which are exactly the elements present in the dataset at the query time.
(d}
{a, c.
fa ba,b.c}
{a b}
{d]
(1}
3
6
2
6
7
Figure 1: standard interval tree.
Figure An online interval tree.
In an online setting, however, we do not know which node is the highest to put an interval in, since we do not know the deletion time when an item is inserted. Consider timestamp 3 in Figure[] where item is inserted into D2 = (a, b). If were to be deleted at timestamp then 2y becomes the highest node that stabs it, which by definition should store c. However, if is deleted at some timestamp among {5, 6, 7). then 24 the highest node. Other possible candidates are Ug V16. One idea is to put a copy of the interval into every node where the interval might be placed into. But there are infinitely many such nodes, therefore we do so lazily. More formally, we design a novel online interval tree that is capable of handling an infinite stream.
Definition 5 (Online Interval Tree). In an online interval tree T, a tree node Vt stores an interval (i,j) if and only if both A) < f < j; and B) 0; is in the subtree rooted at Vr.
Compared with the standard offline interval tree, an online interval tree may store an interval (i, at multiple nodes. Nevertheless, condition B) implies that all these nodes lie on the root-to-node path to V; so each level, there at most one node that stores [). which is the key property we will need. We use Figure to illustrate. Interval a is stored at U1, U2, U4. which are ancestors of U1. It is not stored vg since condition A) is violated: intuitively, by timestamp 8, is already deleted, so there is no need to store a at Ug. On the other hand, needs to be stored in all U1, U2, (in the standard interval tree, only stored at v4), because by timestamp or 2, we still do not know the deletion time of a. Similarly, interval d is stored in both Ug and ug.
5

---

3.1.1 Building the Online Interval Tree
This online interval tree can be incrementally constructed easily. After observing the update at timestamp t, we first compute the dataset D, at time These are exactly the elements that satisfy condition A). Then we construct the dataset (vx)) for the node v, out of elements in Dr, keeping only those that also satisfy condition B). These will be the intervals whose insertion-time node 0; or or lies in the left-subtree of et- For any node on the left-most path of T (where i is a power of 2), D(w)) Dj simply contains elements in the current dataset. Otherwise, ((,)) C Dr will only contain items inserted after its closest left- ancesor......
Example 2 (Online Interval Tree Construction). In Figure we construct D(vs) = D2 (a, b. c} at
construct ((vg), we first compute DG {a. c, d}. But we only consider items whose insertion-ting time is in the left-subtree (namely (V5, V.., therefore (vv)) = {d} will only include d from Dg. The intuition that and have already been covered by 14-
Note that when ((v)) is first constructed, we do not have the deletion times of the items in D(v)). which will be added when these items are actually deleted later. For example, in Figure 2 ( = {a, b} is constructed at timestamp 2 but neither item is associated with a deletion time. After timestamp 5, we add the deletion time of b, augmenting D(v2) to {a, (b, 5)}; after timestamp 8, becomes {(a, 8), (b, 5) Note that there is need to associate the left endpoints (i.e., insertion times) to the items as in the standard interval tree, and we will see why below.
3.1.2 Querying the Online Interval Tree
Now we show how answer a stabbing query using the online interval tree. Since the online interval tree includes multiple copies of an item, the standard interval tree query algorithm will not work, as it may report duplicates. For the stabbing problem itself, duplicates not an issue they can be casily removed they have been reported already. However, for answering linear queries, we actually need to cover all stabbed intervals by disjoint union of subsets. To achieve it, modify the stabbing query process as follows. Given query at time q. We follow the root-to-node path to di in T, and only consider left nodes t on the path where S q. For each ut, report all intervals (i,5) in D(v)) where j > q.
Example 3 (Online Interval Tree Query). Again consider a query at q= Figure 2 on the root-to-node path, nodes 14 and 0g satisfy S We visit them and report {a, c} and {d} respectively, which jointly form the dataset DG-
Unlike in the standard interval tree, we do not query those right ancestors (e.g. v3). It turns out that the items stored in the right ancestors are exactly compensated by the extra copies items stored in the left ancestors of lq.. The following lemma formalizes this guarantee.
Lemma 6. The query procedure described above reports each stabbed interval exactly once.
11
Nodes of storing (i.j)
Ug
Nodes v/ queried timestamp ?
Figure 3: Querying a stabbed interval.
Proof. Given a query at time y, consider any item inserted at time i and deleted time j. represented by interval j). We first prove that this item will not be reported if it is not in the dataset D,, i.e. interval (i,]) ) not stabbed by q. This happens when: (1) the item has been deleted at query time (j I q). As only report item whose deletion time j > q. the interval is filtered out; (2) the item

---

has not arrived by query time (i > q). As we only visit left nodes i where S q, it follows that I 1 q By definition, 2/ can store an item only if ( 2 i, so this item is not stored by v)-
The final case is when i S q < j. and the interval is supposed to be reported by exactly one node. This is shown in Figure 3] For the trivial case that q = i, the newly constructed node e is the only node reporting this interval. Otherwise, consider the minimum subtree containing both D, and Ug. and assume rooted at vt. We must have i; in its left subtree and by in its right subtree by the minimum property, with the only exception that one of them can be ey itself, i.c. i S. 1 S g. We can argue that iy the only node that reports the interval: any node of & in that stores [i,5) is either in the left subtree of i/ or an ancestor of ey that is on the right side of iy any node ey # queried at q is either in the right subtree of v, or an ancestor of on that is on the left side of vt. Thus the only node that can possibly report this interval is Ur. Since by is queried and j >> q, this stabbing interval is reported exactly once by vi.
3.2 Deletion-only Mechanism at Each Node
We have shown that the online interval tree can be incrementally constructed, such that at any time t, we can obtain the current dataset D, by a disjoint union of Ollog t) subsets, each from vt or left ancestor of 2 in the interval tree. Consider each queried node U, (i I t) where (e,);) denotes the set of items that node U; stores at time t. This implies that a linear query fDi) can be answered by computing the sum E; (()(())) over queried nodes U, as specified in Section 3.1.2 Answering queries F on items stored by 02 at time I. is a deletion-only problem: when D(v;) is first constructed timestamp it has size n(())) S n, and no element is associated with deletion time. Then, items in D(r)) get deleted as time goes by.
Now we focus the deletion-only problem at node u; To distinguish, we use D(es) to denote the initial state of node v when it first gets constructed at timestamp i, and use De(us) to denote the remaining items in node i, at time I. Conceptually, we also consider a dynamic dataset Dj (v:), which consists of all the deleied elements from node v,. Their sizes will be denoted as n((v)), me(()) and n, (v.) respectively. For example,
D(02) = {a, when constructed at time 2, whereas D5(12) = {a} and D5 (12) [b]. Clearly at any time i, Dr(vs) w D (v:) = D(vs) and therefore mx(1;) - n (v:) n(m)). We then have nz (1:) S and ne(1s) S (((x)) S n4. but there is no relationship between n, and nı.
A simple solution for this deletion-only problem is to first release a privatized f(D(e:) when initialized, and then run an insertion-only mechanism over the conceptual dataset DJ (c:) so that ((DT(u:) can be obtained at any time. Using their difference, f(D,(u:) can be answered. The problem here that given static mechanism M with error function a( (),),,, the initial (vv))) is answered with error a<n(v))),)) -). Although n((;) is bounded by n,, it has no relationship with the current data size ne at query time, In particular, the initial data size ruv;;) can be arbitrarily larger than its current size nee (R:), which fails to achieve our target error bound -n).
To fix the problem, ensure that more than n(e:)/2 2 items should be deleted that at any time we can guarantee n²(;)) = (nz)). When half the items have been deleted from D(v;), we restart the process on new D (1:) that consists of the remaining items with fresh privacy budgets.
There are still few privacy-related issues with the above idea. First, we cannot restart when exactly half the items have been deleted, which would violate DP. Instead, run a basic counting mechanism Mont,ins over the conceptual dataset for deletions to approximately keep track of the number of deletions; we show that such an approximation will only contribute an additive polylogarithmic error. Second, since we restart the process above multiple times, we need to allocate the privacy budget carefully using sequential composition. But the privacy degradation is only polylogarithmic since we have only O(log n (v;)) = (logt) t) restarts with high probability. Finally, as the decision of restarting the process depends on random noises, the total number of restarts can not be fixed in advance. Since we must guarantee differential privacy for any possible instantiation, we need to allocate the privacy budget through convergent sequence. Similar to (4, we allocate the privacy budgets proportional to r (1++)) in round for small constant 7) 0. The total privacy is then
bounded regardless of the number of actual rounds, as r (1++) < ! + 1. This incurs another
logarithmic-factt degradation. Algorithm [ details the steps we run at each node v in the online
7

---

interval tree. We present in Lemma 7 its accuracy guarantee, assuming each node is allocated with (E.
Algorithm 1: (e, 6) Algorithm at node v =
Input: Fully-dynamic stream (..., (8,, 2.)....). constant 77, privacy budget (e, 6), probability B,
static (Mx) and insertion-only (Mr,ins) mechanisms for queries F, continual counting mechanism Ment,ins
Output: F(D)(w)) at any time t 2
// Initialize 2 D(w)) <- items in D. inserted after the closest left-ancestor of o in online interval tree;
0 1+1" 1, (51, 61) + e/=, (6) + :
D < D(vi):
<- D + +app(1//e):
5 Release MM(DD) under (51,61)-3 )-DP to answer (vD)(v:)):
Initiate M under (E1, d1 and Mentiina under DD:
7 foreach t + + 1, 2.... do
update (st, v4) (-, where x E D(v;) then Augment the deletion time of a to (x, t); Feed an update (+, x) to Misins and Ment,insi
10
else
12
Feed an update (T, x) to MF,ins and Ment,insi
13
Approximate number of deletions from Ment, < Error bound (e; Er; 8,) in Corollary
14
i h/2 2n then
// Restart
r 1, (Er, 5,) +- (arito 2x 2) ,r Grito D < (u:);
18
+ [D] + Lap(1/EE);
19
á < 2% then Halt by answering O to all future F(Di(e:));
// Terminate
21
Release new My(D) under (Er, 8,) -DP answer F(D((n)) Restart MF,ins under (E,, DDP and Ment,ins under e,-
22
else
24
F(D) + Query the current MD(D);
25
F(D) )+ + Query the current Mysinsi
26
Answer ( F(D,)
For each node Vi. Algorithm 7 is (e, 8D- Suppose there is a static mechanism Mj for answering query class is equipped with error function a (E, 5, |), (x),)2)). Then at any time t, Algorithm answwrss FVD:( with error a (lggt)
Lemma 7.
5 3, n (F1,11))))))
o o())
Proof. We some extra notation in the proof for simplicity. As focus the deletion-only problem at node v, we denote = Dr (wx). D D (v.) = n,, (v.) and n n 7 n-R (v:). where is the query time and to is the beginning time of the current round. the public error bound of basic counting on infinite streams given in Corollary I which only depends on parameters the round and the time t.
Privacy, Algorithm I Juses four black-box mechanisms. In each round, ń released using the Laplace mechanism and F(D) is released using static mechanism My. In addition, two insertion-only mechanisms My, and Ment,ins are used to track J and the basie counting query over deletions D any round r, the composition of these four mechanisms is (4E,, 26,) = (مبي o) DP. As restart these mechanisms, they sequentially composed, which guarantees the whole mechanism node is (s, DDD,, since D アー I+ guarantee holds regardless of the number of restarts.
2 + 1. Note that the privacy

---

Accuracy. Let random variable R denote the number of restarts before the mechanism terminates, we first bound R as follows. When a restart happens, we have á > f + 27, where ( With probability
23,, both á and n have eπror at most n. Conditioned on this happening, we get n > 2: at least half of the remaining items have been deleted from D. As U; was initialized with n(.)) S n, S N; S N₁ items, with high probability this can happen at most Ollog N₂) times before there are only (e;) S items left. Still conditioned on the noise being small, line 19 becomes true and the algorithm halts by answering O, which has error at most 0(7) for any linear query. To conclude, conditioned on the events that in each round, the noises in counting are smaller than the bound 7, which happens with probability - -x= 28, > 1 /3/3, there can only be Ollg N,) rounds at time L, where N, is the number of updates up till time I.
We next bound the error of (v)) in any round S R, as a function of r and with probability 1 1- 23/3. If the algorithm decides to restart at time f, an up-to-date dataset (e(,,) is computed and a fresh ((D) is obtained from the static mechanism My with privacy budget (Er, 6,), whose
error is [cr, 5r, 3: (mt)).)) a(er, 6r, 3, :) with probability 1 - 2/3/3. Otherwise (line 23
20
with probability 1 1,, we have the actual number of deletions n I 47/2+47. Namely the current data size is at least ne ne((x)) = n n 2 n/2 - 47. Conditioned on this, we calculate ((Dr(v))
from the difference of F(D) and F(D ). Note that with probability 3/6, the error for F(D)
from My is a (Er:Er, 9 n. by definition; also with probability 1 3/6, the error for F(D")
from MI,ins is (l0gg) log log 6 :.::))) :.)
6.
by Lemma 4 But now both terms can be bounded by
(log.) r) logt log
& 3, ne + 7. with high probability, as n S n S (1: + 8-y = O(n + 7).
This means their difference, (v)) has error a (logr) at least 1 2,,, 23/6 2 1
Ex & log7 log
3, ne + 7;-) with probability
Finally we condition on the event that there are only r = Olog N₂) rounds to get rid of the dependency on r, which happens with all but B/3 probability. By Corollary [ the counting error
in round at time t is 7tt Br) O Therefore the error for (())( is (with probability - B3
logt.. 2 log J. + logt log サ.) O (oggh.e t
llog 3.
Er
Er
a (logt) (
E
8
B, + (log l- N,) log 1.5 t log
log Ne 3
.1.1, 12)1
(log 11 logt' (log 14 II N,) logt"
3.3 Full Algorithm
Lemma 7 Jassumes each node is under (c, 5)DD, which we cannot afford since we have an online interval tree of depth logt. Since the tree size grows with t and can be infinite, allocate (E(o), )())) proportional to 1/C +1 to a node v at level l in the online interval tree, so that the composition of
mechanisms at all the nodes still satisfies (e, 8)-DP any time t. Since each item will only affect one single node in each level, nodes at the same level enjoy parallel composition. The error of the final sum is then decomposed into log t online interval tree nodes, where the error of each node is given by Lemma but under (e(v),((v))-n DDD)
To provide an error guarantee to the final results, note that it is the disjoint union of (log² 1) static mechanisms. This is because each of the (log t) queried online interval tree nodes runs an insertion- only mechanism to support querying the deleted elements, the error of each one is from the error of (log t) static mechanisms. We are left with analyzing the error of each building block: the static mechanisms. Their error depends on the privacy budgets (s', 8') allocated to it. In our construction, it has a polylogarithmic degradation compared to the (e. 8) for the whole mechanism. In particular, there are 3 factors that accounts for the allocation of privacy budgets.
1. We have an online interval tree of height (log (). While nodes on the same level enjoy parallel composition, it is possible that the change of one timestamp affects multiple tree nodes on the root-to-node path corresponding to this timestamp. Therefore, we must allocate privacy budget with sequential composition. Moreover, the tree can grow infinitely. So

---

instead of an even allocation, we apply convergent sequence to divide the budgets, which causes a log*+" overhead to the worst building block at time t.
2. At each online interval tree node, we restart the mechanisms several times. Since this may repeatedly reveal information of the same entry, also need to divide the privacy budget accordingly. Again, we allocate the budgets in each round using a convergent sequence again to make the DP guarantee independent of the number of restarts. With high probability, no queried node will restart more than log N, times, so the minimum privacy budget in any round a 1/og
1+7 N₂) fraction the budget allocated to the node.
3. Finally, in each round of each node, the insertion- only mechanisms Mont,ins and MM are built from static mechanisms, each receiving 1/(log () fraction of the budget.
Putting things together, we arrive at the main result this paper. For the running time, observe that the mechanism at each node of T is dominated by the insertion-only mechanism from Lemma that tracks the deletions. Since there can be Oloog t) restarts, and the total running time over all nodes in the same level is Ollog t) time(N, (N.. Summing over all (log t) levels, obtain the running time stated.
Theorem 8. If there is static DP mechanism with error function a (,,1,,,, X1) for set of streams, so that at any time answers queries F on D2 with error
queries F, then there is an (c, 8)-PPP mechanism Mdyn for fullyddnammc
C(t;e, 8, [1) a (log2
20g 3, n
log
3.
log
logt
|F 1x11
log
3+
2n
3
for any constant v) > The running time of Mayn up to time Ologg t) timo(N.).
Plugging in PMW as the static DP mechanism, we obtain fully dynamic algorithm for answering set of arbitrary linear queries with the following error bounds:
Corollary 2. Given a set of linear queries F, there an (e, 0)-DP mechanism MF,dyy that at any time t, answers any query E F on
stream with error
(,1,,,,,,,m.. [1) =
(Ó(1) 0PPM
O(1) 0(1) B, n + 0(1),
(((VT)):
6> 0, 8 8= 0.
Our mechanism only has a polynomial dependency on the data size n, at time t, matching results in the static setting, whereas straightforward extension of insertion-only mechanisms [9] 4 will have a polynomial dependency on the number of updates N, > nt.
4 Limitations
While polylogarithmic factors are often neglected in theoretical studies, they still present significant overhead practice, which limits the practicality the algorithms proposed in this paper. How to reduce this overhead remains an interesting problem for further investigation. A possible future direction is to consider white-box mechanisms that improve the accuracy (though they can only reduce the polylogarithmic factors) while being practical. It is also interesting study how answer non-union- non-union-preservinng queries (e.g. distinct count) accurately under the streaming DP setting.
Acknowledgments and Disclosure of Funding
This work is supported by HKRGC under grants 16205422, 16204223, and 16203924; and by the Start-up Research Fund of Southeast University under grant RF RF10286251500 We would also like to thank the anonymous reviewers who have made valuable suggestions improving the presentation of the paper.
10

---

References
[1] A. Blum, K. Ligett, and A. Roth. A learning theory approach to noninteractive database privacy. 2013.
J. ACM, 60(2):
[2] M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proc. Theory of Cryptography, TCC, volume 9985, pages 635-656 2016.
[3] A. R. Cardoso and R. Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. In AISTATS, volume 1 of Proceedings of Machine Learning Research, pages 2397-2419. PMLR, 2022.
[4] T. H. Chan, E. Shi, and D. Song. Private and continual release of statistics. In Proc. Automata, Languages and Programming, ICALP, volume 6199, pages 405-417. Springer, 2010.
[5] G. Cormode and K. Yi. Small summaries for big data. Cambridge University Press, 2020.
[6] R. Cummings, S. Krehbiel, K. A. Lai, and U. T. TTattipongpipat. Differential privacy for growing databases. In Proc. Advances in Neural Information Processing Systems, NeurIPS, pages 8878-8887, 2018.
[7] M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. ISBN 9783540779735.
[8] C. Dwork and Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211 1-10, 2014.
[9] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. In Proc. ACM Symposium Theory of Computing, STOC, pages 715-724. ACM, 2010.
[10] C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In IEEE Symposium on Foundations of Computer Science, FOCS, pages 51-60. IEEE Computer Society, 2010.
[11] C. Dwork, Naor, O. Reingold, and N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Proc. Advances in Cryptology, ASIACRYPT, volume 9453, pages 735-751. Springer, 2015.
[12] H. Fichtenberger, M. Henzinger, and Ost, Differentially private algorithms for graphs under continual observation. In ESA, volume 204 of L/PIcs, pages 42:1 Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
[13] H. Fichtenberger, M. Henzinger, and J. Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation using completely bounded norms. In Proc. International Conference Machine Learning. ICML, 2023.
[14] A. Ganesh and J. Zhao. Privately answering counting queries with generalized gaussian mechanisms. Symposium on Foundations of Responsible Computing, FORC, volume 192 of LIPIcs, pages 1:1-1:18, 2021.
[15] M. Hardt and G. N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In JEEE Symposium Foundations of Computer Science, FOCS, pages 61-70. IEEE Computer Society, 2010.
[16] M. Hardt and K. Talwar, On the geometry of differential privacy. In Proc. ACM Symposium on Theory of Computing, STOC, pages 105-714. ACM, 2010.
[17] M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. Proc. Advances Neural Information Processing Systems, NeurIPS, pages 2012.
[18] M. Henzinger, J. Upadhyay, and S. Upadhyay. Almost tight error bounds on differentially private continual counting. In Proc. ACM-SIAM Symposium on Discrete Algorithms, SODA. pages 5003-5039, SIAM, 2023.
[19] Jain, I. Kalemaj, S. Ruskhodnikova, S. Sivakumar, and A. D. Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. In NeurlPS, 2023.
[20] Jain, D. Smith, and C. Wagaman. Time-aware projections: Truly node-private graph statistics under continual observation. In SP, pages 127-145, IEEE, 2024.

---

[21] P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. IEEE Trans. Inf. Theory, 63(6):4037-4449, 2017.
[22] C. Li, M. Hay, V. Rastogi, G. Miklau, and A. McGregor. Optimizing linear counting queries under differential privacy. In Proc. ACM SIGMOD-SIGACTSSIGARRT Symposium on Principles of Database Systems, PODS, pages 123-134. ACM, 2010.
[23] C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. VLDB J., 24(6):557-781, 2015.
[24] McSherry. Privacy integrated queries: an extensible platform for analysis. In Proc. ACM SIGMOD International Conference on Management of Data, SIGMOD, pages 19-30. ACM, 2009.
data
[25] S. Muthukrishnan. Data streams: Algorithms and applications. Found. Trends Theor. Comput. Sci., 1(2), 2005.
[26] S. Muthukrishhan and A. Nikolov. Optimal private halfspace counting via discrepancy. In Proc. Symposium Theory of Computing Conference, STOC, pages 1285-1292. ACM, 2012.
[27] S. Raskhodnikova and T. A. Steiner. Fully dynamic algorithms for graph databases with edge differential privacy. Proc. ACM Manag. Data, (122):99:1-99222 2025.
[28] S. Song, S. Little, S. Mehta, A. Vinterbo, and K. Chaudhuri. Differentially private continual release of graph statistics. CoRR, htss/880..25555 2018.
[29] T. Steinke and J. R. Ullman. Between pure and approximate differential privacy. J. Priv. Confidentiality, 7(2), 2016.
[30] S. P. Vadhan. The complexity of differential privacy. In Tutorials the Foundations of Cryptography, pages 347-450. Springer International Publishing, 2017.
[31] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes]. [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificctin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: both the abstract and the introduction, we stated that this paper presents black-box algorithms for DP queries on fully-dynamic streams with polylogarithmic degradation in the utility compared to static ones.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should elearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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]
13

---

Justification:
We have discussed the limitations in Section 4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section 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 approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 be used by reviewers as grounds for rejection, a 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 an 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 proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We stated the assumptions in Section 2 and presented our results with proof's in Section
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is theoretical paper that does not include experiments.
Guidelines:
14

---

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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If 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 be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This is theoretical paper that does not include experiments.
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, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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 //iips.cc/pulli///uus
CodeeSumiiiie issiissiino ssionoolicy 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 are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

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
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?
Question:
Answer: [NA]
Justification:
This is theoretical paper that does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: [NA]
Justification: This is theoretical paper that does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, 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.
OK to report 1-sigma error bars, but one should state 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 out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is theoretical paper that does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as 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
Answer: [Yes]
Justification:
This paper confirms with the NeurIPS 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: [NA]
Justification: This paper studies DP query answering from theoretical perspective, which should have a societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has socictal 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 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 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 a 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: This paper poses such risks since it does not involve specific data model. Guidelines:
17

---

The answer NA means that the paper poses 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 usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but 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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does 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 URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
18

---

Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved 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 equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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 the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
The core method development in the research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM for what should or should not be described.
19

---

A DP Mechanisms for Linear Queries: A Review
In this section, we present some important DP mechanisms for linear queries and their enror bounds. The analysis is similar to that in in [30,, but we clarify the dependency on 3, which will be needed for analyzing the simultaneous error in the streaming setting. Note that linear query has sensitivity 1 by definition.
Laplace Mechanism. When F {f} is single query, the Laplace mechanism that outputs Mtap (D) - I(D) + Lap(;) has error (e, B) - In When contains multiple queries,
we may add Lap( ( noise to each query result and apply basic composition to guarantee E-DP of the whole mechanism. To translate it into error bound, we bound the failure probability of each noise by 8 [ that union bound will bring the total failure probability B. A similar argument can be made using advanced composition. To conclude, answering set of queries using Laplace mechanism achieves error (for 8 2 0)
F
F
o
log
8 S &<--((
LLap (F,
F log
FF B
log
2 e -(1=))
Gaussian Mechanism. Similar to the Laplace mechanism, the Gaussian mechanism protects (c, 6)- DP of query í by outputting MGauss ()) = S(D) + (0, In 1. Its error is O'Gauss 5, = In 1.25 In 2
When composing multiple Gaussian mechanisms that each answers query from
B.
F, ZCDP composition 2 can be applied, which shows adding N (o. F log noise each query suffices to protect (s, -DP of the whole mechanism. Therefore answering set of queries F using Gaussian mechanism achieves error (for > 0)
F log
F
O.Gauss (e, (,1, = O
log
Private Multiplicative Weights. When there are many queries |F| = D() composing individual mechanisms has error polynomial in [FF, thus also in DI. The Private Multiplicative Weights mechanism [15
17 performs better in this case. The following error bound is presented in [7
D log | log([ $
6= 0;
@PMW
=
[ / log X log (100) log F F1/B)
88>0 0.
E
Apart from mechanisms mentioned above, there are other private mechanisms for linear queries. For example, the optimal composition (21] can be used in place of basic or advanced composition to provide better allocation of privacy budget, yet computing it is costly. The log | factor is removable for Laplace mechanism (29] and almost removable for Gaussian mechanism [14. Under pure-DP, SmalIDB [ has asymptotically the same error PMW. but its running time prohibitive. The Matrix mechanism [22 23 exploits structural properties within the query set F and works well practice. But does not have a closed-form error bound for general queries, and finding an optimal querying strategy is time-consuming.
In general, the best mechanism is related to the hereditary discrepancy 16 26 of the set of queries. For example, for d-dimensional halfspace counting queries, (26] has error Ō(D z In this paper we use as function of E, 8, 3, and possibly [D], [F1, | to denote the error of any mechanism answering linear queries on static datasets, without detailing the best mechanism under a specific setting and choice of the parameters. Since our paper takes a black-box approach, all these algorithms can be plugged into our framework so as to support dynamic data, while incurring a polylogarithmic- factor degradation.
20

---

B Error Bounds under Disjoint Union
Note that (k) denotes the enror of the sum of k mechanisms, each of which having enror under the same parameter settings. It always holds that (*) (.,8) k a(., () by union bound. In this section, we show cases where (&) can be tightened for specific mechanisms. As our running example, consider (e, B) In 3- The union bound reduction above gives
h: In 0 Lapp (c, 3) I E 3
(K)
k
bound the error of summing Laplace noises Lap(?). (). Next we show how this can be tightened.
B.1 Unbiasedness
a mechanism M unbiased with error a, naturally the error only scales with vh. To see why this true, we can argue that with all but & probability, individual mechanisms have their errors bounded by al', #t) simultaneously. Conditioned on this happening, apply Hoeffding's inequality with the remaining probability, we get
O Unbiased (:,B)
V
4 B 2k a
(:
(:22
This can be applied to the Laplace mechanism to get
VT
k log
(k) Lap (c, =
log
3
B.2 Concentration Bounds
For specific distributions like Laplace (sub-exponential) and Gaussian (sub-gaussian), the concentra- tion bounds are usually tighter than using unbiasedness only. It helps save the log factor from union bound. Consider the Laplace mechanism, note that the Lap(²) random variable is sub-exponential
with norm |[ap(( llv, 2. We can then apply Bernstein's inequality (3I).
Lemma 9 (Bernstein's 's inequality). Let XI,..., XR be i.i.d. zero-mean sub-exponential random variables with norm 11 There is an absolute constant e so that for any O,
k
1 Av?
-cmin
Pr
X
>
2exp
We therefore conclude the Laplace mechanism has error function
(k) ( LLap (e. B) =) (2)
k ( log !) log
As another example, for the Gaussian mechanism, the sum of & Gaussian noises is still a Gaussian noise with its variance scaled up by k; thus the disjoint union of Gaussian mechanisms has error
(k) Gause (5, = 0 { k log 3 log 1 3
21

---

For the PMW mechanism, the union bound remains the best we know, that is
[ log X log (og(()))//)) $
0 k.
== 0:
(6) dPMW
[| log X log(1 (1/) logg))og((( log (K(3)) $
0 k.
0 0.
① k |D|$] 0;
① k: D
8 0.
C Related Work for DP under Continual Observation
In the Binary Tree mechanism [2], each timestamp is treated as a leaf node in the binary tree, and the mechanism privately releases the count of each tree node. the stream has bounded length T, then each node receives a TngT fraction of the privacy budget, and the final count consists of (lug 4) :
counts from O(log tree nodes. Using our notation, the mechanism has error OLap basic counting. Chan et al. 4 first showed that allocating the privacy budget through convergent sequence will allow the Binary Tree mechanism to also work for infinite streams, where the error
3) for
worse by logarithmic factor LLap log To7: 3) for constant 0. They further proposed
(log 4)
hybrid mechanism to show that Lapp (Top7: (3) can be achieved by separately releasing the counts for [1, 2), [2, 4), [4, ..... Using the Laap function in Equation 2 above, we obtain the error
(logt)
(k)
Lap
(logt)
E logt'
=
=0
log 1.5
log
1 logt 1
log 3)
8
for continual counting, which was presented Corollary as our building block. Note that this is per-query bound: with constant probability, query any time can be answered with error O(3 log 1.5 t).
Altemattvely, if we replace 3 with B/T where an upper bound on we obtain a bound that holds simultaneously for all queries < T: with constant probability, any query can be answered with error ( log" 7'). The simultaneons bound given in 9 was O log 2.5 using unbiasedness but not concentration, which corrected in In (k) Lap (c, (3 0 /E log 1t). and thus
4 Chan al. presented the (*) function as
(logr) Lap
log ( ))
1 3
loog -0
log
While the per-query bound is the same, for the simultaneous bound, this only gives O log 2.5 T). whereas our tighter bound gives O(2 log² T). The same simultaneous bound was presented [3 [8] with improved constants using the Matrix Mechanism [22 23 as building block. For sparse finite streams, achieves ( log!.3 N, log + log + per-query error for basic counting, which has an asymptotic improvement when N, (1))
We briefly mention some other work under similar settings but are less related. 3 studies the DP histogram problem in the streaming setting, which is a special case of linear queries. Their main contribution when the universe X' or the sensitivity of the queries are unbounded. Otherwise, the algorithm is equivalent to Corollary I [19 studies the DP distinct counting problem under the turnstile (fully-dynamic) model. Distinct counting queries are known to be non-linear and not union-prees preserving, which is separate from the interest of this paper. There are also existing work that study graph queries under the continual observation model of differential privacy, e.g. 28
20 27
22


Reviews:
[{"review_id": "WQWGblknfq", "reviewer": "Reviewer_Px2a", "summary": "This paper introduces a new black-box mechanism that integrates any given algorithm for the private linear query problem with the binary tree mechanism to construct an algorithm for private query release under continual observation. This method achieves lower additive error for the streaming turnstile model than that indicated by prior work. For context, the private linear query problem simply asks the data curator to return the result of an arbitrary set of linear (counting) queries under the constraints of $\\varepsilon$-differential privacy - prior work shows that this is possible with additive error $\\sqrt{n}/\\varepsilon$, where $n$ is the size of the private data set. The continual observation setting requires the data curator to accept modifications to the data set (insertions, deletions, or no change) in a stream, and respond to the set of queries after every update. A general-purpose technique in the privacy literature to deal with queries with an additive structure (union-preserving, as mentioned by the authors) is to use the binary mechanism of Chan et. al., that essentially allows one to use batch algorithms for the query release problem and suffer additive error that is inflated by a factor that is only polylogarithmic in the length of the stream, despite making a release after each new stream element (naive privacy accounting would lead to a $\\sqrt{T}$ additive error when the stream is of length $T$ instead which is much worse).\n\nIt is observed by the authors that for the turnstile setting, this general purpose method suffers the drawback that the net error is not $\\sqrt{n}\\log^c T$ for some $c$ but instead on the order of $(\\sqrt{n_+} + \\sqrt{n_{-}}) \\log^c T$, where $n_+$ s the number of insertions and $n_-$ is the number of deletions. For long streams, clearly this is much (potentially arbitrarily) worse than the former. The main contribution of this paper is a new algorithm that achieves additive error with only a $\\sqrt{n}$ term.\n\nMethods: The algorithm suggested is essentially a modification of the binary tree mechanism (maintaining a copy of the batch algorithm at each internal node of a binary tree over the stream), where one backtracks to tag nodes with 'liveness' interval endpoints when deletions are made. Just as in the binary tree mechanism, multiple copies of an element are maintained at each level, so are they here, but instead of each element only being added to the nodes corresponding to the dyadic intervals in which it lies, it is added to all nodes whose interval happens to lie within the liveness interval of that element. This leads to the possibility of double counting when a query is made, to deal with this one considers only the responses from the batch algorithm at `left' nodes.\n\nTo achieve the main improvement, the algorithm refreshes the privacy budget of each internal node when half the elements it carried previously are deleted, which ensures that the additive error remains on the order of $\\sqrt{n}$. The restart points themselves can be privatized with the Sparse Vector Technique (SVT). Refreshing the budget in this manner is not too wasteful because this can happen only logarithmically many times for any node over the course of the stream.", "questions": "1. What happens if an element is deleted more often than it is inserted? It looks like it doesn't make much of a difference since the algorithm would just check the internal nodes and find nothing to add a deletion tag to, but this might be good to discuss explicitly.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The problem is very general, of interest to the privacy community and impactful.\n2. The algorithm is simple and straightforward to understand, intuition is given well.\n\nWeaknesses:\n1. I think the proofs need to be written more rigorously, possibly in the appendix - at a high-level this approach makes sense, but for instance not having a formal definition of a left node and a right node made the reading a bit harder.\n2. Although intuition is given well, the writing could be polished a lot more - this is a very minor and subjective issue but subheadings like 'Putting it Together' are maybe a bit informal and not very helpful to a reader trying to find the right subsection quickly, for instance.", "was_revised": true, "final_justification": "I didn't have any major concerns for this paper, and there were no significant weaknesses to address, so I keep my score as is (a 5).", "rebuttal": "> W1. I think the proofs need to be written more rigorously, possibly in the appendix - at a high-level this approach makes sense, but for instance not having a formal definition of a left node and a right node made the reading a bit harder.\n\nWe will include formal definitions for these terms and revise the proofs.\n\n> W2. Although intuition is given well, the writing could be polished a lot more - this is a very minor and subjective issue but subheadings like 'Putting it Together' are maybe a bit informal and not very helpful to a reader trying to find the right subsection quickly, for instance.\n\n We will change the subheading to 'Full Algorithm' and polish the writing.\n\n> Q1. What happens if an element is deleted more often than it is inserted? It looks like it doesn't make much of a difference since the algorithm would just check the internal nodes and find nothing to add a deletion tag to, but this might be good to discuss explicitly.\n\nSimilar to our definition in line 14, all existing work on the turnstile model under DP (e.g. [18]) has also adopted the **strict** trunstile model. Under this model, an item to be deleted must exist in the dataset. A more relaxed model, which allows negative counts, has been studied in the non-private setting, but it has not been studied under DP yet."}, {"review_id": "dhtCRWbsFC", "reviewer": "Reviewer_QjJv", "summary": "While differential privacy (DP) oftentimes imposes a challenging trade-off between utility and privacy in the static setting, dynamic algorithms add another factor tearing this trade off apart, which is time (or number of updates). The authors of the submission present a construction for a dynamic, $(\\epsilon, \\delta)$-DP algorithm for any union-preserving query (e.g., linear queries), given a static, $(\\epsilon', \\delta')$-DP algorithm. A query $f$ is union preserving on multisets $D_1, D_2$ if $f(D_1 \\cup D_2) = f(D_1) + f(D_2)$. For linear queries, using the DP multiplicative weights mechanism, their fully dynamic algorithm achieves an error of $\\tilde{O}(n_t^{2/3})$ for pure DP ($\\delta=0$), and $\\tilde{O}(\\sqrt{n_t})$ for approximate DP with a multiplicative $O(\\log^2 t)$ blow-up in time, where $n_t$ is the size of the dynamic dataset at time $t$. This improves over existing constructions with similar error bounds but which are only partially dynamic (insertions or deletions), and fully dynamic constructions with error bounds that that are linear in $t$. For union-preserving queries, the bound is a bit more complex: Given a static DP mechanism with an of error $\\alpha^{(k)}$ when transformed into an insert-only mechanism via appropriate standard techniques, roughly speaking, the resulting dynamic error bound is $\\alpha^{(\\log^2 t)}$, and dependencies on $\\epsilon, \\delta$, size of the dataset are substituted by themselves multiplied by a $O(\\log^3 t)$ or $O(1/\\log^3 t)$ factor. The running time is claimed as the running time of the static black-box algorithm on $n_t$ times $O(\\log^2 t)$.", "questions": "The running time as stated is a bit confusing to me. It seems to me that it should be the time to run the static mechanism for every time step, plus the time for running the incremental mechanisms for the respective restart intervals. However, $time(|D_t|)$ is the time complexity to process $|D_t|$ incremental updates to me. Would'n you need to sum up the time complexities for each restart interval / lifetime of an incremental mechanism separately instead of bounding them by $|D_t|$, which may be even 0?\n\nThe notation $\\\\alpha^{(k)}$, in particular the definition of $(k)$, is a bit informal. The extensive list of arguments is very helpful, but the meaning of the stream-related exponent $k$ for a static algorithm is a bit ambiguous or vague.\n\nThe definition of union-preserving might deserve to be more prominent than a footnote.", "limitations": "Yes, all limitations addressed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The algorithm is based on the established, high-level concept of maintaining the dynamic updates and privacy budget of a DP datastructure in a tree of logarithmic depth, but generalizes it by keeping track of insertion/deletion pairs represented as intervals. The authors propose an online version of an interval tree, where the index of a node in an in-order traversal is $t$. An insertion at time $t$ is tracked on the path from the root to the node $v_t$, and it is removed from it at the time of deletion. At each node, the algorithm uses three black-box mechanisms: a static DP mechanism for $f$ to provide an answer for the dataset at time $t' \\\\leq t$, an insertion-only DP mechanism to track deletions since $t'$, and a insertion-only DP mechanism to count deletions. The latter mechanism is required because when a node's privacy budget is exceeded, it needs to restart its mechanism (and sets $t' = t$).\n\nThe main technical contribution and novelty of this paper is a black-box construction for dynamic data streams and union-preserving queries. Except for a few special cases like counting (where $f \\\\equiv 1$), it reduces the best known multiplicative error bound for linear queries in the number of updates $t$ from linear to $log^2$. Arguably, counting is an important special case, and the improvement for this case is $\\\\log^2.5$ to $\\\\log^2$. The paper is well written except for a few minor improvements to notations that could be made, and appears to be sound on the level of arguments (without checking numbers).", "was_revised": true, "final_justification": "The authors provided answers to all my (minor) questions. I still recommend acceptance.", "rebuttal": "> Q1. The running time as stated is a bit confusing to me...\n\nThank you for pointing this out. This is a typo: We meant to write $O(\\log^2 t) \\cdot time(N_t)$ for the running time, where $N_t=|D_t^+|+|D_t^-|$ is the number of updates (rather than the data size). The two $\\log$ factors account for the fact that each node can be restarted $(\\log t)$ times, and the tree has height $(\\log t)$. Within each round, the number of items is bounded by the number of updates.\n\n> Q2. The notation $\\alpha^{(k)}$, in particular the definition of $(k)$, is a bit informal. The extensive list of arguments is very helpful, but the meaning of the stream-related exponent $k$ for a static algorithm is a bit ambiguous or vague.\n\nWe would like to clarify that $\\alpha^{(k)}$ is not necessarily defined with respect to a stream. It just refers to the total error when summing up $k$ DP estimators.  For example, when answering a range query consisting of $k$ counts from a standard Laplace histogram, the error will also be $\\alpha_{\\mathrm{Lap}}^{(k)}=\\tilde{O}(\\sqrt{k})$. We just use this notation (instead of $k\\cdot \\alpha$, which is not tight) to express our error in the streaming setting.\n\n> Q3. The definition of union-preserving might deserve to be more prominent than a footnote.\n\nWe will move it to the main text."}, {"review_id": "PXFf6ukdql", "reviewer": "Reviewer_KNz3", "summary": "The paper tackles continual release of differentially-private answers for fully dynamic (turnstile) data streams, where elements may be both inserted and deleted. While previous work handled insertion-only streams or the static setting, the authors design a black-box transformation that turns any static DP mechanism for a union-preserving family of queries (e.g. linear queries) into a mechanism that operates on fully dynamic streams with only a polylogarithmic loss in accuracy and running-time.\n\nThe core technical contribution is an online interval tree that stores each item in at most one node per tree level, permitting a decomposition of the data set at time $t$ into $O(\\log t)$ disjoint parts that can each be handled by an insertion-only sub-mechanism . \n\nA careful choice of parameters bounds the cumulative privacy loss while keeping the error blow-up within polylogarithmic factors.\nIn particular, plugging private multiplicative weights as the static algorithm, they achieve $\\tilde O(\\sqrt{|D_t|})$ error for approximate DP and $\\tilde O(|D_t|^{3/4})$ for pure-DP. Here $|D_t|$ is the size of the current dataset $D_t$. Notably, there is no dependence on the number of queries for linear queries, whereas straightforward extensions of prior insertion-only works would result in polynomial dependence on the number of queries.", "questions": "1. Are there any interesting classes of union-preserving query families beyond linear queries?\n\n---\n\n### Suggestions\n1. I would suggest (informally) stating the main results within the introduction of the paper and quantifying the improvements from prior works.\n2. There are some references for continual release which may be relevant.\n\n---\n\n- Song, Little, Mehta, Vinterbo, Chaudhuri. \"Differentially private continual release of graph statistics.\" arXiv 2018.\n- Fichtenberger, Henzinger, Ost. \"Differentially Private Algorithms for Graphs Under Continual Observation.\" ESA 2021.\n- Epasto, Liu, Mukherjee, Zhou. \"Sublinear Space Graph Algorithms in the Continual Release Model.\" arXiv 2024.\n- Jain, Smith, Wagaman. \"Time-aware projections: Truly node-private graph statistics under continual observation.\" SP 2024.\n- Raskhodnikova, Steiner. \"Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy.\" PACMMoD 2025", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. To the best of my knowledge, this is the first black-box method that matches static-query accuracy up to polylog factors for fully dynamic streams, closing the gap with insertion-only results.\n1. The online interval tree data structure seems to be novel and may be of independent interest even beyond privacy.\n\n---\n\n### Weaknesses\n1. The results only hold for union-preserving query families. While this includes the class of linear queries, it limits applicability.", "was_revised": true, "final_justification": "The rebuttal clarified the scope of the contribution, specifically about union-preserving families. I think this will be a good contribution to NeurIPS.", "rebuttal": "> W1. The results only hold for union-preserving query families. While this includes the class of linear queries, it limits applicability.\n\nThe class of linear queries is extensively studied under differential privacy (e.g. references in line 97). This is a large family and serves as building block for many problems:\n- histograms, range counting, k-marginals and data cubes are well-known linear queries;\n- the sum/mean-estimation query $\\sum_i x_i$ can be rewritten as $B\\cdot \\sum_i (x_i/B)$ where the weight for a value $v$ is $v/B$, assuming each item is bounded by $[0,B]$;\n- the sum-of-square query $\\sum_i x_i^2$ for computing variance can be rewritten similarly;\n- the median query itself is non-linear (and not union-preserving), but it is known that any quantile query can be reduced to $(\\log B)$ linear queries under DP.\n\n> Q1. Are there any interesting classes of union-preserving query families beyond linear queries?\n\nIn fact, the definition for union-preserving queries (footnote 2 on page 2) can be generalized to any $+$ operator that is associative. For example, consider the truncated-linear query $g(D)=\\min(f(D),\\tau)$ where $f$ is a linear query and $\\tau$ is a constant.  This non-linear query is also union-preserving by defining $a+b := \\min(a+b,\\tau)$.  Note that our error bound then also becomes the \"sum\" of the errors from a polylogarithmic number of the black-box static estimators, where the overloaded $+$ is used to compute the sum.\n\n> S1. I would suggest (informally) stating the main results within the introduction of the paper and quantifying the improvements from prior works.\n\nWe have stated the main result near the end of introduction (line 57). We will emphasize it by adding a paragraph header in bold.\n\n> S2. There are some references for continual release which may be relevant.\n\nThanks for the pointers.  We will include these references."}, {"review_id": "FSRLGsGSMM", "reviewer": "Reviewer_yUVf", "summary": "This paper studies privately answering linear queries that are union-preserving (i.e., $f(D_1\\cup D_2)=f(D_1)+f(D_2)$) in the turnstile streaming model. Prior works mainly focus on insertion-only streams, as most of the DP tools can be naturally attuned in this model. Note that simply treats a turnstile stream as two insertion-only streams is not enough, as popular private mechanisms have square root dependencies on the size of the set, doing so would lead to undesirable bound on the error. Thus, to obtain reasonable error bound on turnstile streams, the authors use a novel online interval tree to keep track of the lifespan of elements. This is significantly different from classical interval trees, where all intervals are known in advance. Authors show that it is possible to maintain the intervals in an online fashion while not blowing up the complexity of the data structure significantly. Using this data structure, authors show that the problem is then reduced to a deletion-only problem, but running an insertion-only algorithm is not enough, so the proposed algorithm restarts the data structure when half of the elements are deleted. With some extra caveats being taken care of, the authors arrive at a private algorithm for linear queries over turnstile streams.", "questions": "1. What do you think are some other applications of the online interval tree when used for turnstile streams?\n\n2. For non-union-preserving linear queries, is it possible to extend the developed techniques to handle them? If not, what are the major barriers?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The result obtained in this paper is strong, it achieves nearly-optimal dependence (up to polylog factors) on the size of the stream, which is nontrivial. Although the core mechanism (private multiplicative weights and insertion-only algorithm) has been developed, designing the correct data structure to utilize these tools is an important contribution.\n\n2. The online interval tree is a novel contribution that might find applications other than DP in the turnstile streaming setting. In fact, adapting the online interval tree for turnstile streams could be abstracted as a framework for tasks that have good insertion-only and static algorithms that depend on the size of the stream.\n\n3. The paper overall is well-written, the algorithm is explained clearly and the online interval tree data structure, facilitated with several figures, is easy to understand. \n\nWeaknesses:\n\n1. The mechanism is developed for the general setting, it would be interesting to see more white-box application of the proposed algorithm for particular problems, such as half-space queries, with even more improved error bounds.\n\n2. The paper is technically dense, thus the discussions on future directions are limited.", "was_revised": true, "final_justification": "The paper is very solid, I only have minor suggestions and authors have addressed them well.", "rebuttal": "> W1. The mechanism is developed for the general setting, it would be interesting to see more white-box application of the proposed algorithm for particular problems, such as half-space queries, with even more improved error bounds.\n\n> W2. The paper is technically dense, thus the discussions on future directions are limited.\n\nOur paper takes a black-box approach. We believe designing white-box mechanisms to improve the bounds is an interesting future direction.\n\n> Q1. What do you think are some other applications of the online interval tree when used for turnstile streams?\n\nWe think the data structure will be useful for answering interval-stabbing queries and range queries in the online setting.\n\n> Q2. For non-union-preserving linear queries, is it possible to extend the developed techniques to handle them? If not, what are the major barriers?\n\nThe problem for non-union-preserving queries is challenging since the tree-decomposition does not work. For example, if the dataset is divided into two subsets, each containing 40 and 50 distinct elements respectively, then the distinct count of the original dataset can be any value between 50 and 90."}, {"review_id": "FZXEo5P23r", "reviewer": "Reviewer_kHdG", "summary": "This paper is about answering linear queries on a fully dynamic stream while preserving differential privacy. Previous work has only worked on insertion only streams where an element is never deleted. Moreover, the insertion only algorithms can be extended to fully dynamic but with a rather high error: their error is a function of $|D_t|$, the size of the dataset at time t. In a fully dynamic stream, if the number of elements ever inserted until time t is $N_t$, naively using insertion only algorithms gives an error that is a function of $N_t$ and not $|D_t|$, while $|D_t|$ can be much smaller than $N_t$.\n\nThis work shows how to use an insertion only algorithm in a blackbox way and get same errors in terms of the size of the dataset at time t. Their approach consists of many interesting components. First they introduce a dynamic interval tree that can cope with deletions and any query can be answered by only inspecting log t nodes. If $D^+_t$ is the set of nodes ever inserted up to time t and $D^-_t$ is the set of nodes deleted on or before t, they compute a linear query by computing it on $D^+_t$ minus its value on $D^-_t$. Their second component is \"restarts\", where they compute a query from scratch on $D_t$ using a static algorithm instead of computing it on  $D^+_t$ and  $D^-_t$. They do these restarts when almost half of the elements in a tree node are deleted, and this way they can control the error to be in a function of $|D_t|$. Their third component is a clever distribution of privacy budget which is not novel on its own but is nicely used.", "questions": "On line 341 you allocate privacy budget of $1/\\ell^{1+\\eta}$ to nodes at level $\\ell$. However as time goes on the level of nodes can increase. Could you explain why this is fine?", "limitations": "I can't think of any limitations other than the ones stated.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is very well written. They provide really good examples to explain their ideas, and as explained above I like the components of their algorithm. their contribution is strong.\n\nWeaknesses: \n- minor: the proof of Lemma 7 refers to Algorithm 1 which is stated after this lemma in the appendix. It would have be good to provide a summary of this algorithm or explain the parameters before referring to them.", "was_revised": true, "final_justification": "This paper is strong and original enough for acceptance.", "rebuttal": "> W1. The proof of Lemma 7 refers to Algorithm 1 which is stated after this lemma in the appendix. It would have be good to provide a summary of this algorithm or explain the parameters before referring to them.\n\nWe will add some description to Algorithm 1 in the main text.\n\n> Q1. On line 341 you allocate privacy budget of $1/\\ell^{1+\\eta}$ to nodes at level $\\ell$. However as time goes on the level of nodes can increase. Could you explain why this is fine?\n\nThe height of the tree is $\\ell=O(\\log t)$, so this only causes a polylogrithmic factor increase to the error, which is often neglected in theoretical studies."}]

Author rebuttal:

Meta-review: This paper gives a black-box method that can be used to go from a private linear query algorithm to a private query release algorithm that works in dynamic streams where elements may be inserted or deleted. The construction presented improves better parameters than existing algorithms and works on fully dynamic streams in contrast with insertion-only streams. The paper achieves nearly optimal dependence on the length of the stream (up to polylog factors).
The reviews do not identify any significant weakness except recognizing that these techniques are unlikely to work beyond linear (or more specifically, a union-preserving family) or queries.
I think this paper is quite impressive because of the generality and (near) optimality of the result, resolving questions that several papers had looked at. In addition, some reviewers thought that the paper was well written. Because of these reasons, I would like to recommend this paper for a spotlight.
The discussion was collegial. The issues identified by the reviewers were very minor, and addressed well by the authors.
Decision: Accept (spotlight)