Skirting Additive Error Barriers for Private Turnstile Streams
Authors: Anders Aamand
Justin Y. Chen
Sandeep Silwal
Venue: ICLR 2026 Poster (2026)
Keywords: Differential privacy
streaming
distinctelements
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We circumvent polynomial lower bounds for differentially private distinct element and F2 moment estimation by allowing some multiplicative error of our estimators.

Abstract: We study differentially private continual release of the number of distinct items in a turnstile stream, where items may be both inserted and deleted. A recent work of Jain, Kalemaj, Raskhodnikova, Sivakumar, and Smith (NeurIPS '23) shows that for streams of length $T$, polynomial additive error of $\Omega(T^{1/4})$ is necessary, even without any space restrictions. We show that this additive error lower bound can be circumvented if the algorithm is allowed to output estimates with both additive \emph{and multiplicative} error. We give an algorithm for the continual release of the number of distinct elements with $\text{polylog} (T)$ multiplicative and  $\text{polylog}(T)$ additive error. We also show a qualitatively similar phenomenon for estimating the $F_2$ moment of a turnstile stream, where we can obtain $1+o(1)$ multiplicative and $\text{polylog} (T)$ additive error. Both results can be achieved using polylogarithmic space whereas prior approaches use polynomial space. In the sublinear space regime, some multiplicative error is necessary even if privacy is not a consideration. We raise several open questions aimed at better understanding trade-offs between multiplicative and additive error in private continual release.

Published as a conference paper at ICLR 2026
SKIRTING ADDITIVE ERROR BARRIERS FOR PRIVATE TURNSTILE STREAMS
Anders Aamand BARC
Justin Y. Chen CSAIL, EECS Massachusetts Institute of Technology Cambridge, MA, USA justcémit. edu
University of Copenhagen
Copenhagen, Denmark
aa@di. ku. dk
Sandeep Silwal
Department of Computer Sciences
UW Madison
Madison, WI, USA
silwal@cs wisc. edu
ABSTRACT
We study differentially private continual release the number of distinct items in turnstile stream, where items may he both inserted and deleted. A recent work of Jain, Kalemaj. Raskhodnikova, Sivakumar, and Smith (NeurIPS '23) shows that for streams of length T, polynomial additive error of (((T1/4) is necessary, even without any space restrictions. We show that this additive error lower bound be circumvented if the algorithm is allowed to output estimates with both addi- tive and multiplicative error. We give algorithm for the continual release of the number of distinct elements with polylog(7)) multiplicative and polylog(T) additive error. We also show a qualitatively similar phenomenon for estimating the F/2 moment of turnstile stream, where we can obtain 1 + o(1) multiplicative and polylog(T) (T) additive error. Both results can be achieved using polylogarith- mic space whereas prior approaches use polynomial space. In the sublinear space regime, some multiplicative error is necessary even privacy is not a consider- ation. We raise several open questions aimed at better understanding trade-offs between multiplicative and additive error in private continual release.
INTRODUCTION
Differential privacy (DP) under continual release captures the setting where private data is updated over time. The data arrives one at a time in a stream, and an algorithm must privately release an underlying statistic of interest as the data changes. The continual release model goes back to the early days of DP and has been extensively studied for counting the number of events in a binary stream, also called continual counting Dwork et al. (2010); Chan al. (201 1); Honaker (2015); Andersson & Pagh (2023); Fichtenberger et al. (2023); Henzinger et al. (2023); Andersson et al. (2024); Henzinger al. (2024b); Dvijotham al. (2024); Henzinger & Upadhyay (2025), private machine learning applications (via DP-SGD and DP-FTRL) Kairouz et al. (2021); Denissov et al. (2022); McMahan & Thakurta (2022); Choquette- Choo et al. (2023a;b; 2024) (also see the survey of Pillutla et al. (2025)), and tracking graph statistics Song et al. (2018) 8); Fichtenberger et al. (2021); I); (2026). In our setting, the stream is modeled items from known universe [ni] o updates. We consider the turnstile model where items may be both inserted and deleted.
Jain al. (2024); Raskhodnikova & Steiner (2024); Aryanfard et al. (2025); Andersson
Continual release is algorithmically interesting since it combines challenges of both differential pri- vacy and streaming algorithms, and there is a recent line of work aiming to nail down the optimal davacy-utilityy trade-offs for continual release of some of the most basic and well-studied statis- tics in a stream, including estimating the number of distinct elements and the F, moments of the stream Epasto al. (2023); Jain et al. (2023b;a); Henzinger al. (2024a); Cummings et al. (2025);

---

Published as a conference paper at ICLR 2026
Aryanfard et al. (2025); Andersson et al. (2026); Epasto et al. (2026). We focus on the distinct elements and Fg moment estimation problems in this paper, two of the foundational problems in streaming algorithms.
However, there remain substantial gaps in our understanding of these fundamental streaming prob- lems when privacy is a concern. Even ignoring space considerations, which make the aforemen- tioned problems trivial in the standard streaming setting without privacy, there exist polynomial gaps (in the stream length 7) between known upper and lower bounds in turnstile streams. For example, for estimating the number of distinct elements' in the stream, the best known algorithms achieve a (TT/3332 additive error bound Jain et al. (2023a); Cummings et al. (2025). On the flip side, is known that any private algorithm must incur 12(72/4) additive error Jain et al. (2023a), and closing this gap a challenging open problem. Furthermore, just from sensitivity considerations, is easy to see that any algorithm for private F2 estimation must incur (TT) additive error.
We are motivated by the fact that (low-space) streaming algorithms for both distinct elements and F2 estimation must incur multiplicatiie eπror Jayram & Woodruff (2013), and thus it is natural to ask if one can go beyond the existing additive error lower bounds for continual release in turnstile streams if the algorithm is allowed to output estimates with both multiplicatiie and additive error. Indeed, some evidence of why this is possible is already present in the prior work of Epasto et al. (2023) which obtains polylogarithmic additive error along with small multiplicative error for Fp moment estimation, including distinct elements, albeit in the significantly easier setting of insertion- only streams where items are never deleted. Furthermore, it can be checked that the lower bound instances for ((T1/1) additive error for distinct elements Jain et al. (2023a) and (2(7)) additive error for F2 estimation both occur when the true underlying value is itself much larger than the additive error, meaning they do not imply any hardness for obtaining constant multiplicative error. Beyond the continual release setting, overcoming purely additive error lower bounds by introducing multiplicative error has been feature of several recent works in DP Aamand et al. (2025); Ghazi et al. (2025); Aryanfard et al. (2025).
The main conceptual message of our paper is that polynomial additive errors for fundamental stream- ing problems can be replaced with polylogarithmic additive errors, at the cost of some multi- plicative error. Furthermore this can often be achieved while simultaneously using small space.
1.1 OUR RESULTS
We are focused on computation over data streams of length T from a universe of size n. We use (aj, $1). ... (aT, ST) to denote general turnstile data stream where a, E [n] is an element iden- tifier and s; E (, }} is the increment amount. We call an update an insertion if s; deletion if 8; = 1. In insertion-only streams, 8; = 1 and in strict turnstile streams, at any point in time, the number of deletions to any given element can never exceed the insertions to that element (the element's s frequency cannot be negative). We are concerned with the following notion of mixed multiplicative and additive error for continual estimation of stream statistics.
and a
Definition 1.1 (Multiplicative and Additive Error for Continual Estimation). Let Y, E RR be a func- tion of the prefix of a stream $1),....... (ae, 8t). A streaming algorithm for the continual esti- mation problem outputs an estimate Y, after receiving the ith stream update for all t E [T]. For parameters a: 2 1,3 2 O, we say the algorithm solves the problem with (a,, 3) error if there exist parameters p. q 2 with pq = a and r, 8 2 0 with r + s =B such that, for all E [T].
Y1/p- r S Y, S +
For a randomized algorithm, we say the algorithm has error (a. with probability -y if the error bounds hold across all timesteps with probability at least 1 - 7 over the randomness of the algorithm.
If an algorithm satisfies (1,9) error, say it has purely additive error. If an algorithm satisfies (a, 0) error, we say it has purely multiplicative error.
'The number of elements with non-zero frequency. A We use Ō(f) to denote O(f polylog(f)). 'hhe F2 value of stream, also known as the second frequency moment, is defined as the sum of squares of frequencies of items in the stream.
2

---

Published as a conference paper at ICLR 2026
Remark 1.1 (Interpretation of (),3) error). One interpretation of (a, 3) ervor is that get close to an a multiplicatiive approximation to the statistic Y, as long as it is above the noise floor Y₁ >> B.
Our results in this paper operate in the event-level notion of privacy for continual release. In this setting, two datasets are neighboring if they differ only in a single update (a,, 8,). This contrasts with the more stringent notion of privacy called item-level which two datasets differ in all updates which touch a certain domain element a E [rz]. The formal definition of privacy can be found in Section 2.
Distinct Elements When the statistic of interest is the number of distinct (non-zero frequency) elements, we show that we can skirt the lower bound of /2(T1/44) from Jain et al. (2023a) if we also allow multiplicative error in our estimates. Our main result is an algorithm that solves the distinct elements problem with only polylogarithmic additive and multiplicative error.
Theorem 1.1 (Informal version of Theorems 3.1 and 4.1). Let E, < L. There exists an (c, D-DP algorithm for the continual distinct elements problem that with probability 1 1/ppol(TT), for all points in time i [T' oulputs an estimate D2 of the number of distinct elements D2 with error (a, B) The space usage of the algorithm is polylog(n. T).
where a; B O (ol)loo(T.1//6) (1
Recall that the best bound from prior work incurs error (1, (TT ignoring dependencies on and 5. Our bound improves upon this as long the true number of distinct elements is upper bounded by Ö(T1/3). As n is trivial upper bound for the additive error of any algorithm (the number of distinct elements is between O and n),, the prior work gives non-trivial estimates when the stream length is upper bounded T < na. By comparison, for 7 which grows superpolynomially in n. In settings where our bound and the prior bound alternate in quality over the course of the stream, the best of the two bounds (up constant factors) can be achieved by simply running both in parallel each with half of the privacy budget and outputting the estimate from prior work when it exceeds twice its additive error.
bounds give non-trivial estimates
Our results are achieved by two different algorithms for continual distinct elements estimation. As core primitive, both rely on differentially private continual counting. Our contribution using tools from the streaming literature to carefully transform distinct elements estimation into certain counting problems which are amenable to the additive error guarantees of private continual counting.
The first algorithm (which leads to Theorem 3.1) is inspired by the classic idea of using the minimum hash value of keys constraints, we cannot compute the minimum hash value exactly. Instead, we create buckets based on the least significant non-zero bit of hashes of keys such that the expected number of keys hashing to the buckets increase geometrically. We can then use private continual counting in each bucket to approximately determine the min hash.
set to estimate the size of A and appears in Section 3. Under privacy
The second algorithm (which yields Theorem 4.1) is based on performing domain reduction, also via a hash function, to a domain sufficiently small such that many elements collide. These collisions can be detected by private continual counting algorithm. We can then use the size of the reduced domain as an estimate for the number of distinct elements. This algorithm is presented Section 4.
The minimum hash algorithm is limited to strict tursstile streams but achieves better error and less space usage than the domain reduction algorithm which applies to general turnstile streams. In Sec- tion we also show potential path towards achieving arbitrarily good multiplicative error. Using the same tools as the domain reduction algorithm, we show the following reduction: a (hypothetical) algorithm achieving purely additive error sublinear in the domain size n implies the existence of an algorithm achieving (1 + 77, polylog(T") error. See Theorem 4.2 for details.
Frequency Moments In addition the distinct elements problem, we also consider the F2 esti- mation problem, where we are interested in approximating the second moment of the frequencies of elements the stream at any point of time. Specifically, if each update (ar, 5t) satisfies a, E [n] and s E (-1,0, 1}. we may define xt] Exstor=s 8j. and we are interested in approximating F2 Ejema [2] for any t. It is easy to see that any algorithm with only purely additive error (a, 3) = 3), must have 3 = ((()), simply because the sensitivity of the second moment is A(T). Surprisingly, we show that allowing small constant multiplicative error, the additive error
3

---

Published as a conference paper at ICLR 2026
Source
Error
Space
Privacy
Notes
Jain et al. (2023b)
(1, (1,((1)))))
O(T)
Item-level
Cummings et al. (2025)
(1 + 11, O(T(/3))
O,(TV/3
Event-level
Jain al. (2023a)
(1,9((1)/))
Event-level
Lower bound
Epasto et al. (2023)
(1+ 17. (log (T)))
polylog(T)
Event-level
Insertion-only
Theorem 3.1
(O(log((T)) O(log
O (T))
Event-lovel
Strict turnstile
Theorem 4.1
(O(log O(log" (T)))
poly(T)
Event-level
Table Multiplicative and additive error bounds for (e, -D algorithms for the Continual Distinct Elements Problem. We ignore dependencies on the privacy parameters. Unless otherwise stated, upper bounds hold for general turnstile streams and lower bounds hold for strict turnstile streams. We present results which hold for worst-case streams of length T. See Appendix A for numerous prior works which give instance-specific bounds depending on stream statistics.
Source
Error
Space
Privacy
Notes
Epasto et al. (2023)
(1 + 1), (log' (T))) (n(log((T))
Event-level
Insertion-only
Lemma 5.1
(1,S)(T)
Event-level
Lower bound
Theorem 5.1
(1 + 1). O,, (log" (log"(T)) (T))) On(log((T)
Event-level
Table 2: Multiplicative and additive error bounds for (c, 6DDP algorithms for the Continual F2 Problem. We ignore dependencies the privacy parameters. Unless otherwise stated, upper bounds hold for general turnstile streams and lower bounds hold for strict turnstile streams.
can be made polylogarithmic. Furthermore, algorithm quantitatively improves upon the prior work of Epasto et al. (2023) which only applies in the insertion-only model.
Theorem 1.2 (Informal version of Theorem 5.1). Let E, 5, < 1. There exists an (c, 5)-DP al- gorithm for the F2 estimation problem that with probability 1 - 1/poly(T), for all points in time I E [T] outputs an estimate of F2 of F2 with error (1 + 3) where 3 = polylog T, 1)8))) The space usage of the algorithm is polylog(T)/r)
Again, this result relies on continual counting. We use the Johnson-Lindenstrnn Lindenstrauss reduction to map the n--dimensional frequency vector to a small domain, and use continual counting to estimate the coordinates in the reduced domain.
1.2 PRIOR WORK AND OPEN PROBLEMS
We include detailed discussion of prior and concurrent works in Appendix A and several interesting open questions in Appendix B.
PRELIMINARIES AND NOTATION 2
Throughout the paper, pTly(T) refers to a polynomial of arbitrarily large constant degree. We con- sider the base logarithm by default: log(.) log2(-).
2.1 DATA STREAMS
Let (1),88),... ..., (aT, 8T) denote the data stream where E [n] is an element identifier and (-1, 0, 1} is the increment amount. Let x, IR" denote the frequency vector at time step For i E [m]] [i] is the sum of increments to item across all timesteps up to t. In the strict turnstile model. we have zz > 0 for all i E [n], E
[T], and the number of distinct elements at time t is defined D. e [n] 2 > 0j. In the general turnstile model, the true frequency vector D, is allowed to have negative entries and the number of distinct elements is simply the number of non-zero coordinates. We interchangeably denote the number of distinct elements as ||0:||o-
4

---

Published as a conference paper at ICLR 2026
In this work, assume that the universe size and stream length T are known up to constant factors to the streaming algorithm a priori for simplicity. Without loss of generality, we will consider poly(T) by standard hashing tricks.
A streaming algorithm processes each update one at time while maintaining only a bounded mem- ory. In this work, measure space in terms of words of size at least Si(log T) bits. This is standard measurement, assuming that the length of the stream and the universe size can be stored in constant number of words. We also assume access
oracle which can produce sample of one-dimensional Gaussian noise . (O, o²) which can be stored in constant words. See Canonne al. (2022) for background on sampling Gaussian noise for differential privacy.
We consider randomized streaming algorithms with non-adaptive adversaries. The stream is chosen independent of the randomness of the algorithm. While some private algorithms can succeed against adaptive adversaries Jain et al. (2023b), the best (even non-private) streaming algorithms for many fundamental problems including distinct elements require space polynomial in the stream length Attias et al. (2024).
2.2 DIFFERENTIAL PRIVACY
Definition 2.1 (Event-Level Neighboring Datasets). Let X = (a1, (1),s).,.,,a...... ST) and X' (a), s1),... (3)).,,.(77) S'r) be two strict turnstile data streams. These streams are neighboring if there exists an index E [T] such that (a,, + &)), and for all j + (a), = (d 83))
A different notion of level privacy is also studied where all updates which touch a given ele- ment E [n] may change between neighboring dataset. In this work, focus the event-level definition.
Definition 2.2 (Differential Privacy Dwork et al. (2006)), Let A : X + y be a randomized algorithm. For parameters E, 2 0, A satisfies (E for any two neighboring datasets X'X' X and measurable subset of outputs O y
Pr[A(X) E &
<PP(((() E 0
We will also make use of similar form of differential privacy called zero-concentrated differential privacy, p-zCDP, introduced by Bun & Steinke (2016), p-zCDP implies (s, DDD and benefits from tighter and simpler composition of multiple private mechanisms.
Definition 2.3 (Rényi Divergence Rényi (1961)). Given distributions P,Q over y and pa- rameter ( E (1, oo), we define the Rényi Divergence as
P(x) ((()) Q(zz)
5-1
Qc(P))Q) C-1 log Eg-P
Definition 2.4 Conce-Coneett Differential Privacy (zCDP) Bun & Steinke (2016)), Let A X be a randomized algorithm. For parameter p 2 0, A satisfies p-zCDP for any two neighboring datasets X, E X and < oc),
(,(A(X))A((X'))> SS.
Lemma 2.1 (zCDP Composition Bun & Steinke (2016)). Let A: X + x be algorithms satisfying Pı-zCDP and p2-2CDP, respectively. Then, the algorithm which, given input X E X, outputs ((X B(X,,(X))) satisfies (pı + P2)-2CDP
and X y Z
Lemma 2.2 (zCDP Translation Bun & Steinke (2016)). Any algorithm satisfying p-2CDP also sat- isfies (p 2 p (1/5) DP for any 8 > 0.
Therefore, an algorithm satisfying p-zCDP also satisfies Df 0 (lg))))
The simpler problem of DP Continual Counting was introduced in Dwork et al. (2010); Chan et al. (2011). In this setting, the stream is comprised of a sequence of updates in (,1,0,1) to an un- derlying count and the goal is maintain rumning approximation to the prefix sum of updates every timestep with small additive error. The problem is normally defined over a stream of bits with b, E (0. 1). Allowing decrements as well can be achieved with the same asymptotic additive emror
5

---

Published as a conference paper at ICLR 2026
by using two counters to separately count increments and decrements. We present the following result based on Jain et al. (2023b) which uses the binary tree mechanism of Dwork et al. (2010); Chan et al. (2011) while leveraging Gaussian noise and zCDP. The result presented here is a special case of Theorem 5.4 of their work with 1.
Theorem 2.1 (Gaussian Binary Tree Mechanism). Let p > be the privacy parameter. Con- sider stream of updates b1....,b by where b, {-1,0, 1}. There exists randomized algorithm A(b bT) which outputs estimates ......, .7 with the following guarantees:
Let two inputs b...... by and b4,,. by....,bby b4g be neighboring if and only if there exists j [2' such that by * b/ and be = for all + j. Under this neighboring definition, A preserves p-zCDP.
For E [T,, let y/: Ei- b. Then, with probability 1 11ppoly([
max vv EE
del 5 (ll)
A can be implemented streaming algorithm using (log(TT) words of space.
2.3 OTHER PRELIMINARIES
We use version of the Johnson-Lindenstere lemma with Rademacher random variables.
Lemma 2.3 (Rademacher Johnson-Lindensee Lindenstrauss Achlioptas (2003)). Let x E R" and let A be an m matrix with i.i.d. random entries ats with Pr(as.j = mm/mm Pr(a.. 1/ /m] 1/2. Assume that Clog(1/5)/a² for sufficiently large constant C. Then Pr ==13= <
||Ar| S (1 [=) -
Throughout the paper, we instantiate various hash functions. In Section 3, only pairwise indepen- dence is needed. In Sections and 5, we not optimize for randomness and note that Olog T)- wise independence suffices.
3 CONTINUAL DISTINCT ELEMENTS VIA MINHASH
Without loss of generality, assume that n is power of two with n = 2 for K E N (we can always artificially increase the universe size to achieve this). Consider a hash function h : [n] + [n]. Given an integer E [n], we define (sb(a) E {0. ....... [log n|} to be the (zero-indexed) index of the least significant non-zero bit of a in standard binary representation. For example, 1sb(4) = 2. Consider the (K 1) dimmennsional. O-indexed vector fi where, for any ie E (o....,K"
filk] Σ [[Isb(h(a:)) k]] s;.
This quantity [k] is the sum of frequencies of distinct elements time in the stream with A: trailing zeros. For each we will maintain an estimate [k] over all times e [T] via (K + 1) DP Continual Counters C(O), .. C (Theorem 2.1).
classic estimator for distinct elements is to consider the index of the largest non-zero bit. The non- private template is to identify the largest e {0, ..., K) such that [r[ > 0 and report ò 2 The probability that a given element has sb(aa) le is equal to 2 (k+1), so among 1 elements, we roughly expect to see at least one element with 1sb so (og()) and no elements with 1sb > log(D).
The challenge with implementing this estimator with differential privacy is that a single change to the stream can possibly change the identity of the largest non-empty entry in fa for many timesteps I. By
"While this is common technique for distinct element estimation, perhaps the most natural is to hash stream elements uniformly at random into [0.1] and use 1/(miniumm hashed value) as an estimator distinct elements. is not clear if this technique is amenable to privatization. A naive calculation would upper bound the sensitivity of the minimum hashed value by O(1) (since the value is always in the interval [0, IJ). but this is not strong enough to he useful in the continual setting as the minimum hashed value could change often over the course of the stream the result of single event-level change.

---

Published as a conference paper at ICLR 2026
using continual counters, can only guarantee that fi(k] is approximated up to polylog(T) additive error. So, instead of identifying the largest non-empty entry of ft. we try to identify the largest entry of fz which exceeds this noise threshold If stream elements were bounded to have most constant frequency, this would immediately yield an algorithm with error (O(1), r). However, stream elements could have frequencies larger than т. Therefore, find has count fi[e] > because (a) (o/T) and approximately т elements of constant frequency have 1sb 1sb L. This is the source of the (r) multiplicatiie enror.
do not know if the bucket
(b) log(D) and single element of frequency more than T has
Algorithm 1: MinHash Subroutine
Input: Privacy parameter p. stream length T, domain size 2 poly(T).
1. Initialize p" = p/22.
2. Initialize a pairwise independent hash function h [n] + [n]].
3. For E (0....,K], initialize a DP Continual Counter (Theorem 2.1) C(A] with
privacy parameter p". Let T = Olog 1.5 (T)/VP) an upper bound on the (1
1 1/poly(T) quantile of the maximum additive error of counter all timesteps
E [7).
4. When stream update (ae; 82) arrives,
(a) + 1sb(h(a:)).
(b) Update C(A]] with update 8t. Update all other counters C(k' for k + k with update 0.
(c) Let fe(k'] be the current estimate of C[k'] for all k E (O...., K}. Let e be the largest index such that [(((] > If no such index exists, let l <- 0.
(d) Output: D, + 2
Algorithm 2: MinHash Estimator
Input: Privacy parameter stream length T, domain size n = 2 poly(T).
1. Let m = Ologg T)
2. Initialize = p/m.
3. Run m copies of Algorithm in parallel with privacy parameter p'.
4. For each timestep [T],
(a) For E [m], let D be the estimate of the jth subroutine at time
(b) Report estimate median (D!.....ip? Dr.).
Theorem 3.1. Algorithm 2 is p-cCDP and space Ollog (T)). On strict turn- stile streams, if p Olog T), Algorithum solves continual distinct elements estimation with (O(log2(T) vp), O (log" (T)) error with probability 1/poly(TT).
Note that the condition on p not being too large relative to T is mild the privacy parameter is often chosen to be a small constant. The proof of this theorem is given in Appendix C.
4 CONTINUAL. DISTINCT ELEMENTS VIA DOMAIN REDUCTION
We present another algorithmic technique which guarantees polylog(T)) multiplicative ap- proximation to the number of distinct elements in a private turnstile stream (see Section 2). The main theorem of this section is Theorem 4.1. While the bounds of Theorem 4.1 are quantitatively
Under this promise, the algorithm would also succeed with high probability via a Chernoff bound without the need for independent repetitions.

---

Published as a conference paper at ICLR 2026
worse than of our main theorem, Theorem 3.1, this section serves demonstrate new ideas for the private continual estimation setting, which may be of independent interest. Additionally, they apply to the general turnstile model while Theorem 3.1 applies only to the strict turnstile model where frequencies are non-negative at all times.
Algorithm 3: Domain Reduction Estimator
Input: Privacy parameter p. stream length T'
1. Let C² 2 1 be sufficiently large constants.
2. Set p' p/(CCloo' T).
3. For 1 S i S log 7 and S S C'log construct independent functions, fg
[n] + {2-] as in Lemma D.I.
4. For all i,j and all time steps & [7'. compute coordinate-wise frequency estimate Ig (ax) hy (Ir)) in the streaming continual release model, each which is p p'-zCDP. This guarantees Ilf kk (2+) - ( S for all i,j,t with 1.5 (T) vf) via Theorem 2.1. failure probability B where O(lgg
5. For all and all time steps E [T], let ('()) E R22 denote the (coordinate-wise) median of fj hy (2t)..... g1o0 T 1000 (Tt). & Note i is fixed.
6. For every time step & [2'. let 8" (t) be the largest value such that all | (t)llx N C'T.
7. Return: 2²"(1) as an estimate of || at time [T].
Theorem 4.1. Algorithm 3 satisfies p-zCDP. It solves the continual distinct elements estimation with
(O(log (T)lo)((())/p)))))))) ((log"")))))
error with probability 1/poly(TT. The algorithm uses polynomial in T space and works in the general turnstile model.
The same techniques allow to show reduction from multiplicative error to additive error (in the domain size), showing that an existence of an algorithm (for our distinct elements problem) with sublinear additive еттor in the domain size implies an algorithm which guarantees multiplicative approximations arbitrarily close to 1. In the theorem below, recall that n is the size of the universe. We also restrict polylog( 2 2 in the theorem statement below, since we will use the algorithm of Theorem 3.1.
Theorem 4.2. Suppose there exists a constant > c1 2 such that there is a p-cCDP algorithu A for the continual distinct elements problem which has additive error n /poly(p) and is correct with probability 1 /oly((T) for all time steps. Then for any n E (0, 1), there exists another P-zCDP algorithm A' (for the continual distinct elements problem) which achieves a multiplicative error - 1), additive error poly(log(T),, 1/1,, 1/pp and is also correct with probability - 1/poly(TT).
At a high-level, Algorithm giving a dimensionality reduction map which preserves the number of distinct elements up to poly- logarithie multiplicative error. Unlike traditional dimensionality reduction however, we are
necessarily interested in reducing the dimension of the frequency vector (which is the size of the universe). Rather, we exploit different property of dimensionality reduction which that increases the value of coordinates the reduced dimension. This useful from DP perspective, as large coordinates can be detected via continual counting.
The proofs of these theorems are given Appendix D.
CONTINUAL F2 ESTIMATION
We next consider the problem of F2 estimation. To recap, the stream consists of I" stream elements S (at, St)EE(T] where at E [m] and s, {-1,0, 0, For t [T] and j E [n]. we define sa Exsta,es 8i. We assume the striet turnstile model where 24 [j] 2 0 always. Define (t
8

---

Published as a conference paper at ICLR 2026
to be the n--dimensional vector (xn())))e(n) In this section our interest is to estimate the second moment (S) [x ||x(*) [] at any point of time t.
We first prove a simple lower bound using standard techniques based on the sensitivity of the second moment when single stream element is changed. Note, that the lower bound works even against non-streaming algorithms that see the entire stream up-front.
Lemma 5.1. Let S be the set of all streams S (as, St)ke(T). Let M 8 R be an 6D protocol. Then there exists some So E S such that
Pr Pr[MM(s)) - F2 (S.)
1-6 6 +1
Thus, the additive enror incurred by any DP F2 estimation algorithm is (((T).
Proof of Lemma 5.1. Let S be the stream where all stream elements are (a.. = (1, 1) and
then 5 be the neighboring stream which is identical to S except that (ar, 8T) (2, 1). Then,
F(T) (S) = T and F = (T - 1)² + 12 so that, (S) (S) = 2T - 2. Define
= (S) FT) and = e"+1" If Pr(M(S)) I ^] 2 p. the result follows with So = S, so assume that PS( S A] < p. Then, by differential privacy,
1-6
Pr(M(S) > 2 Pr(M(S) > Al - 1 5
P.
e
6
so the result follows with So S'
Notice that the lower bound instance used to prove the above lemma has single element E [n] with frequency (T)) However, for such an input S, the value (2 is of the order (2(72) which much larger than the additive error. Motivated by this observation, we ask if it is possible to obtain better additive error of our estimates if we allow a small multiplicative error of (1 + a). In this section, show that for any small constant it is possible to obtain additive error polylog(T"). Note that Epasto et al. (2023) obtain qualitatively similar bound, but in the restricted setting of insertion-only streams.
At a high-level, our algorithm is inspired by the classic AMS sketch for F2 estimation in standard streaming Alon et al. (1996), and uses the classic Johnson--indenstrauss (JI.) lemma Lemma 2.3 to reduce the domain size from [n]] to polylog(T). By using a JL construction which utilizes Rademacher random variables, we able approximately (and privately) track the frequencies of the domain elements after applying the JL lemma via continual counting (see Theorem 2.1). Com- position (Lemma 2.1) allows us to simultaneously release the frequencies in the reduced domain with a low-additive eгror overhead since the size of the domain has reduced significantly. Alto- gether, we show that the frequencies in the reduced domain can all be simultaneously estimated up to polylog(7) additive error, which implies our desired error bound. The 1 + multiplicative error incurred by the JI. step itself.

---

Published as a conference paper at ICLR 2026
Algorithm 4: F2 Estimator
Input: Privacy parameter P. stream length T, domain size n, approximation parameter a
0.
1. Let ag = a/5.
2. Let m = C1 (log 2 with C1 sufficiently large according to Lemma 2.3.
3. Initialize random m x n matrix A where the Aij are i.i.d with Pr(A:; = 1/ /
Pr[Ai = - /m 1/2.
4. For E {...... m), initialize DP Continual Counter (Theorem 2.1) C[i] with privacy parameter p' p/m.
5. When stream element (t) arrives,
(a) Let E [n].
(b) For each i [m]. update C(i) with VmAr183 E (-1,0,1).
6. For each timestep [T].
(a) Report estimate 1 E C
Theorem 5.1. Let 0 < < 1 and privacy purameter >> O. There exists p-zCDP algorithm which for all E [T]] provides an estimate Fl of [|x0())11 such that with high probability in T,
(log T)
T
LE - (1> S aall +
 a²p
Moreover, the algorithm can be implemented in the streaming model where it uses O /a²) words of memory.
Note again that to obtain an algorithm which satisfies 6)-D,, it suffices to pick p O(E²/ log(1/5)). The algorithm behind this result is Algorithm 4, and the proof given in Ap- pendix E.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
The authors thank anonymous ICLR 2026 reviewers for helpful feedback. The authors thank Xin Lyu and A. R. Sricharan for discussions on their concurrent works.
Anders Aamand was supported by the VILLUM Foundation grant 54451. Justin Y. Chen was sup- ported by the NSF TRIPODS program (award DMS-2022448) and NSF Graduate Research Fellow- ship under Grant No. 1745302.
REFERENCES
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Breaking the n 1-5 additive error barrier for private and efficient graph sparsification via private expander decomposition. In Proceedings the 42nd International Conference on Machine Learning, 2025. 12
Dimitris Achlioptas. patabase-friendle random projections: Jahnson-lindenstraus. with binary coins. Journal of computer and System Sciences, 66(4):671-68) 2003. 16
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments, In Proceedings of the twent--iigtth annual ACM symposium on Theory of computing. pp. 20-29, 1996. 19
Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private con- tinual observation. In Proceedings the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023, Curran Associates Inc. 1
Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, and Jalaj Upadhyay. Continual counting with gradual privacy expiration. In The ehirty- Annual Conference Neural Information Processing Systems, 2024. URL https: http///eeeeeeeeeeeeeeeee net/ forum?
id=V6gdb12gsM. 11
Joel Daniel Andersson, Palak Jain, and Satchit Sivakumar. Improved Accuracy for Private Continual Cardinality Estimation Fully Dynamic Streams via Matrix Factorization, 2026. https://
arxiv. org/ abs//bb// 02257. 11, 12, 116
Bardiya Aryanfard, Monika Henzinger, David Saulpic, and A. R. Sricharan. Improved lower bounds for privacy under continual release, 2025. URL https: /tt//aixvvvv///////////////aaala wwwpwwwwoo////////////1 1,, 12, 116, 117
Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. framework for adversarial stream- ing via differential privacy and difference estimators. Algorithmica, 86(11):3339-334, August 2024. ISSN 0178-4617. doi: 10.10077/000533-244-03333 15
URL https: /tttt::://doi.ooo http://oooooogg////////
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds In Proceedings. Part I, of the 14th International Conference on The- ory of Cryptography Volume 9985, pp. 635-658, Berlin, Heidelberg, 2016. ppringer-Verlag. ISBN 9783662536407. doi: 10. 11100//97-3-662-56666 1007/978 1111:/988---80 3-
URL https: //ooi. org/10.
24. 15
Clement Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Journal of Privacy and Confidentiality, 12(1). Jul. 2022. 15
J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-15) 1979. 199
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur, 14(3), November 2011. ISSN 1094-9224. 11, 15, 16
Christopher A. Choquette-Chie Choo, Arun Ganesh, Ryan McKenna, Hugh Brendan McMahan. Keith Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: A uni- fied approach to private training. In Thirty-seventh Conference on Neural Information Processing Systems, 2023a. URL https: httt:///ppp//viieeee www.:nee/eeee fort/formmm 2 11

---

Published as a conference paper at ICLR 2026
Christopher A. Choquette-Chane H. Brendan McMahan, Keith Rush, and Abhradeep Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023b. 1
Christopher A. Choquette- Choo, Krishnamurthy Dj Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Correlated noise provably beats independent noise for differentially private learning. In The Twelfth International Conference on Learning Representations, 2024. URL https: http//pppeeeeeeeeeeeeee forum? weerrummiixxccmooeee (e-cHcCCcAAASSSSS 11
Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 205-214, 2009. 124
Rachel Cummings, Alessandro Epasto, Jieming Mao, Tamalika Mukherjee, Tingting Ou, and Peilin Zhong. Differentially private space-efficient algorithms for counting distinct elements in the turnstile model. In Forty-second International Conference on Machine Learning, 2025. URL https:
/icts::/eppereeeee http://pppeeeeeeeeeeeeeee net. forum? ditmmmddd--000mmmmmmmmmm 11, 12, 14, 115, 166
Serguei Denissov, Hugh Brendan McMahan, J Keith Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad- vances in Neural Information Processing Systems, 2022. URLhttps: http///ppneeeeeeeeeeeeeeeee forum? id=i 9XTHJoyLqJ. 11
Krishnamurthy Dj Dvijotham, H Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential pri- vacy, In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. IEEE, 2024. 11
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006. 15
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under con- tinual observation. In Proceedings of the forty-second ACM symposium Theory of computing, pp. 715-724, 2010. 11, 15, 16
Alessandro Epasto. Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially Private Continual Releases of Streaming Frequency Moment Estima- tions. In Yael Tauman Kalai (ed.), 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (IJPPcss), pp. 48:1- 48:24, Dagstuhl, Germany, 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. ISBN 978-3-95977-263-1. URL https: / /drops.....///////////////////// dagst 4230/LIPIcS ITCS 2023. 48. 11, 12, 14, 19, 115
Alessandro Epasto, Xin Lyu, and Pasin Manurangsi. Keeping Secret Requires a Good Mem- ory: Space Lower-Bounde for Private Algorithms, 2026. https: /tttp:://arii.....//// arxiv. org abb//602. 12209. 12,116 166
P. Erdós. On a lemma of littlewood and offord. Bulletin of the American Mathematical Society, 51(12):898 902, December 1945. doi: 10.1090/50002-99000 990-- 1945-08454-7 URL https:// doi.org/1e 1tt.://00.100/00000--200 990--9994--00 000-000-9994-945----80 1944-08454---- 120
Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. Differentially Private Algorithms for Graphs Under Continual Observation.
Petra Mutzel, Rasmus Pagh, and Grzegorz Her- man (eds.), 29th Annual European Symposium Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPles), pp. 42:1-42:16, Dagstuhl, Ger- many, 2021. Schloss Dagstuhl Zebbiiz-Zentrum für Informatik. ISBN 978-3-959777204-4 URL https:/ /rrops. dagstuhl de de/entities//////eeeeeeei
doi: 0042300LIPIcs..AAA.2221 document/10 4230 2IP/ Ics ESA. 202.2002122 2021.42. 42.
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: fin-grained error bound on differentially private continual observation. In Proceedings of the 40th International Conference Machine Learning, ICML'23, JMLR.org, 2023. 1
12

---

Published as a conference paper at ICLR 2026
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop. Ravi Kumar, Pasin Manurangsi, and Sushant Sachdeva. Prem: Privately answering statistical queries with relative error. In Pro- ceedings of Thirty Eighth Conference Learning Theory, 2025. 12
Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithuss (SODA), pp. 2951-2970, 2025. doi: 10.1137/1 19759//9.78811111888222 URL https: /ppubs. 01778661198322..0 95. 11
s siam. ww.. /ooi hatpia/bbs////a/ 11370/11331111
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differ- entially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 5003-5039, 2023. doi: 10. 111177/19788111197744.hhh URL https: ptttps://epbbe http//ppbbss.// siam owt//oi///aaoooooooooooo... http////aaab//// 11 1137 (1t.:/.7711119991 chw.73
11, 116
Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. Private Counting of Distinct Elements in the Turnstile Model and Extensions. In Amit Kumar and Noga Ron-Zewi (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques (APPROX/RANDOM 2024), volume 317 of Leibniz International Proceedings in formaticy (LIPlcs). pp. 40:1-40: 1-4021, Dagstuhl, Germany, 2024a. Schloss Dagstuhl Leibniz- Zentrum für Informatik. ISBN 978-3-95977-348-5.
doi: D04230LPP/G.AAPPRXXAAADDDOO 2024.40. URL https:/ /trpp//rrpppp//oo//o// dagstuhi.ccoom www.ahh..eeeeeeeeeeee LIPICS APPROX SAA.K/RAADOOM.M. 2024.400000 11,,
10. 4230/
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. A unifying framework for dif- ferentially private sums under continual observation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 995-1018, 2024b. doi: 10. 1137/1 113771.97816111779112888 URL https: s sim.. wtt.aaag/oo///o///eeeeeeeeeeee/e 10 1137/1. 9781611977912. 11
James Honaker. Efficient use of differentially private binary trees. In Theory and Practice of Differ- ential Privacy (TPDP 2015), London, UK, 2015. 1
Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. Ad- vances in Neural Information Processing Systems, 36:4610-4623, 2023a. 11, 12, 13, 14, 115, 16
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. In Proceedings of the 40th International Conference on Machine Learning. 2023b. 11, 14, 15, 16, 115
Palak Jain, Adam Smith, and Connor Wagaman. Time-Awar Projections: Truly Node-Private Graph Statistics under Continual Observation In 2024 IEEE Symposium on Security and Pri- vacy (SP), pp. 127-145, Los Alamitos, CA, USA, May 2024. IEEE Computer Society. doi: URL https://dol jeeecooputerrsccitty orgg/00.
10.1109/SP54263 2024.000022220 1109/SP5422 63. 2024 ..2224440000 00196. 11
Christian Janos Lebeda and Jakub Tetek. Better differentially private approximate histograms and heavy hitters using the misra-gries sketch. In PODS, 2024. 15
Thathachar Jayram and David Woodruff. Optimal bounds for johnson-lindenstraus transforms and streaming problems with subconstant error. ACM Transactions on Algorithms (TALG), 9(3): 1-17, 2013. 12
Peter Kairouz, Brendan Memahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling shuffling. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5213-5225. PMLR, 18 24 Jul 2021. URL https: / www.nngsmm.lr................m.. www....rrss//...m.....o...e wwa.lr.pres//v1/////0e http://vv//aaaaaa koo./// html. 11
Brendan McMahan and Abhradeep Thakurta. Federated learning with formal differential privacy
guarantees. In Google Research Blog, 2022. 11
13

---

Published as a conference paper at ICLR 2026
Rasmus Pagh and Mikkel Thorup. Improved utility analysis of private countsketch. In Proceedings of the 36th International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 978171387108 1088. 11
Krishna Pillutaa, Jalaj Upadhyay, Christopher A Choquette-Choo, Krishnamurthy Dvijotham, Arun Ganesh, Monika Henzinger, Jonathan Katz, Ryan McKenna, H Brendan McMahan, Keith Rush, al. Correlated noise mechanisms for differentially private learning. arXiv preprint arXiv:2506.08201, 082001 2025. 11
Yuan Qiu and Ke Yi. Differential privacy fully dynamic streams. In The Thirty- Annual Conference on Neural Information Processing Systems, 2025. URL https: opwnreview.eeeeeeee net/ Fow.mmmdd-ppieee....... wwt.mndddpppppippyee
115
Sofya Raskhodnikova and Teresa Anna Steiner. Fully dynamic graph algorithms with edge differ- ential privacy. arXiv preprint arXiv:2409. 17623, 2024. 117
Alfréd Rényi. On measures of entropy and information. In Fourth Berkeley Symposium on Mathe- matical Statisties and Probability, Volume 1: Contributions to the Theory of Statistics, 1961. URL https: /app: semant iestttcccchhcsce wwtg/orrpsss..ooo 123056571. 15
Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. The flajolet-martin sketch it- self preserves differential privacy: Private counting with minimal space. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.). Advances in Neural In- formation Processing Systems, volume 33, pp. 19561-19572. Curran Associates, Inc., 2020. URL https: https:://ptoeeeeeeee http:///ooooeeee...e.ee. wtw.:eeddddnnn...enieeeeeeeeeeee neurips. cc http/ppper_fffeeee /tlle//ppper/////// fi12-6800FT111333888883338282283
115
Shuang Song, Susan Little, Sanjay Mehta, Staal Amund Vinterbo, and Kamalika Chaudhuri. Dif- ferentially private continual release of graph statistics. ArXiv, 0e0/1809.02577 2018. URL httpps:/aage semant iew.anttccchllar org/CCrppsII 52155555555 75677. 11
Mark N Wegman and Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265-277 1981. 124
Fuheng Zhao, Dan Qiao, Rachel Emily Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu- Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: h/tp::////ppeevveeww net forum? 2d=6NTFiim iNpQJ.. 115
14

---

Published as a conference paper at ICLR 2026
A PRIOR WORK
In this section, we describe existing results on (e, 6)-DP continual distinct elements and F2 estima- tion. Beyond directly related prior work, there are several works which investigate other streaming problems (not necessarily with continual release) achieving small space along with privacy guaran- tees Smith et al. (2020); Zhao et al. (2022); Pagh & Thorup (2022); Janos Lebeda & Tetek (2024); Qiu & Yi (2025). For simplicity, we ignore dependencies on the privacy parameters in the error bounds in following presentation.
Item-Level Privacy The recomputation technique of Jain et al. (2023b) can be used to get an algorithm for turnstile streams which achieves error (1, (TT(33) by recomputing private estimate of the number of distinct elements every T1/3 timesteps and outputting the most recent estimate every & E [T]. This algorithm uses space which linear in either T or n as the exact distinct element count must be maintained throughout the stream."
Jain et al. (2023a) initiated the specific study of the turnstile continual distinct elements problem. This and several follow-up works do not generally improve upon T additive error but introduce error bounds parameterized by statistics of the stream instance. Therefore, for certain instances, these bounds may improve upon the worst-case. This work gives an algorithm achieving additive er- ror (V)w) where w is the flippancy of the stream: the maximum number times any one element switches between zero frequency and positive frequency. This algorithm requires Q(T) space in order estimate the flippancy. The authors show that (mmax (Vn, T1/33)) purely additive error is required. Henzinger et al. (2024a) consider a quantity K which is the total flippancy: the total num- ber of times any element switches between zero and positive frequency. They show that ((K1/3) purely additive error is achievable and required.
Event-Level Privacy Event-level privacy is strictly weaker than item-level privacy. Therefore, algorithms for item-level privacy also apply to event-level privacy, while lower bounds for event- level privacy imply lower bounds for item-level privacy.
Jain et al. (2023a) show that for event-level privacy, weaker lower bound {(max (1/T1141 T1/4)
purely additive error is required. This leaves open an interesting gap between the upper bound of T (which achievable with item-level privacy) and lower bound of 71/4, Henzinger et al. (2024a) show that even for event-level privacy, Ô (K1/3) the best possible dependence on the total flippancy for purely additive error.
Cummings et al. (2025) give an algorithm achieving (1+ 7, error where v is the occur- rency: the maximum number of times any given element is updated in the stream. While w, their algorithm has the benefit of using space (TT4/3)). While this work allows for multiplicative error, their goal was simply to achieve the existing bound T with low space (which necessitates some multiplicative error). In this work, we show that allowing (more) multiplicative error allows for significantly better additive error, and we achieve polylogarithmic as opposed to polynomial space.
To our knowledge, there has been no prior work specifically studying continual estimation of other frequency moments such as F& in turnstile streams.
Insertion-Only Streams and the "Likes" Model When deletions are not allowed (or limited), the problem of continual distinct elements becomes significantly easier.
Epasto et al. (2023) study the problem of continual release of frequency moments (including the number of distinct elements, which is equivalent the zeroth frequency moment) in the insertion- only model where stream updates must be increments with 8 1. They give an (e.0), O)-DP algorithm
achieving ((1 + n. Os m (log² (T"))) error algorithm using space poly ploy I", 1/n, 1/E). The authors
'It tempting to make a sublinear space version of Jain et al. (2023b) by applying the recomputation technique to multiplicative approximation to the number of distinct elements at any time using a standard streaming algorithm. However, this idea does not straightforwardly work as such approximation algorithms blow up the sensitivity.
15

---

Published as a conference paper at ICLR 2026
also study F2 estimation in insertion-only streams. They achieve (1 [1+ 17, (log' error using space (logg(T))m3)
Henzinger et al. (2024a) consider the "likes" model in which elements may only switch from having frequency zero or one. This is an intermediate model between insertion-only and strict turnstile streams. In this setting, (T)ylog(T) additive error is necessary and achievable.
Concurrent Works of Aryanfard et al. (2025); Andersson et al. (2026); Epasto et al. (2026) Three concurrent works study various related aspects private continual estimation. There is no direct overlap with results, though combined, their and results significantly expand the land- scape of private turnstile estimation.
The work of Aryanfard et al. (2025) studies mixed multiplicative and additive error in continual settings with focus on graph problems. They show that hardness for purely additive error for sev- eral fundamental graph problems in the continual setting hold for insertion-only well turnstile streams. On the other hand, they show improved bounds for several insertion-only problems with mixed multiplicative and additive error including graph problems and simultaneous norm estima- tion. They do not provide any new upper bounds for turnstile streams, which is the focus of our work. Finally, they show that for continual estimation of some graph statistics in the item-level pri- vacy setting, the product of multiplicative and additive errors must be large. Their lower bounds (either via a reduction from distinet elements to EdgeCount problem or by their lower bound on 1- -Way-Marginals combined with the reduction of Jain et al. (2023a)) extend to distinct elements: the product of multiplicative and additive errors o,3 must be essentially T1/37 This means that an analogue of our upper bounds, which hold for event-level DP, cannot hold for item-level DP.
The work of Andersson et al. (2026) improves constant factors in the additive eтrоr for continual release of distinct elements, degree counts, and triangle counts. Their main contribution is to adapt matrix factorization techniques which improve constant factors for continual counting (e.g., Hen- zinger et al. (2023)) to replace the binary tree mechanism existing approaches such as in Jain et al. (2023a). In comparison, some multiplicative error.
results give asymptotically better additive error at the price of
The work of Epasto et al. (2026) proves space lower bounds against algorithms achieving results similar to those of Jain et al. (2023a); Cummings et al. (2025) in the item-level setting. In particular, they show that any algorithm achieving error (1.1, oTT1/))) (where the improvement over 1//3 error may be due to instance-specin close to 1/3 We show that it is possible in different setting to simultaneously achieve small space and small additive error, specifically, in the event-level privacy setting when the multiplicative error is significantly more than 1.1.5
occurrency statistics in Cummings al. (2025)) must space
WWe thank the authors of Aryanfard al. (2025) for pointing out that their lower bounds can be extended the distinct elements problem. From discussions with the authors of Epasto et al. (2026), it seems likely that their lower bound can be extended to large multiplicative error.
16

---

Published as a conference paper at ICLR 2026
B OPEN PROBLEMS
We discuss several open problems exploring the trade-off's between multiplicative and additive errors in private continual estimation settings.
Better dependence on n and T for counting distinct elements. Perhaps the main open question of our paper is whether one can obtain better bounds for counting distinct elements under differ- ential privacy with purely additive error. Without any assumptions on the input stream, there is polynomial gap between the upper bound of Ö(T4/$) and the lower bound of Q(TT/4). Moreover, the lower bound holds only with some restrictions on the values of and T. namely under the as- sumption that T S n For general values of n and T. the lower bound is Q(min .,'' n²/3)) which never stronger than a lower bound of 1/2, Note that when counting distinct elements over domain of size it is trivial to obtain error n. An interesting question towards resolving the optimal dependence on the parameters in the additive error whether there exists an algorithm with error o(n) when 7 is large polynomial in This is especially interesting in light of our following result.
Theorem B.1 (Informal version of Theorem 4.2). Any (E. - algorithm for the number of distinct elements in the continual release setting with purely additive error n 0.99 can be converted to another differentially private algorithm with (1 + 1)) mullipiiiieat and poly(log T, 1/n, 1/e, log(1 (1)) ad- ditive error for any constant 0.
A Alternatively, this reduction could be used as a path towards proving lower bounds against o(n) purely additive error.
Constant multiplicative approximation to distinct elements with small additive error. Our results show that we can avoid the large additive error of the lower bounds, if we allow for a multi- plicative error of polylog(7)) for counting distinct. It is an interesting question whether there exists an algorithm with constant multiplicative error and small (e.g., polylogarithmic) additive error. Our techniques based on continual counting seems to reach natural barrier here, which arises from the fact that the counters cannot distinguish between whether the count of a bucket comes from a single highly frequent element, or from many infrequent elements, each having frequency say.
Tradeoff' between multiplicative and additive error. Taking step further, what is the correct tradcoff between multiplicative and additive error for counting distinct elements? If distinct ele- ments algorithm with (1 + 17) multiplicative approximation and small additive error exists, what is the dependence on r) in the additive error? similar question can be asked for F2 estimation, where our current algorithm has (1 17) multiplicative approximation and ((1/7²)) additive error. More broadly, it is interesting to explore tradeoffss between multiplicative and additive error in other set- tings for private continual estimation. potential direction adapt the lower bound techniques in the concurrent work of Aryanfard et al. (2025).
Triangle Counting. Recently, Raskhodnikova & Steiner (2024) considered differentially private triangle counting in dynamic graphs. Their paper contains several results, but most relevant to our setting is an algorithm for counting triangles in a graph with bounded additive error depending on T and the number of vertices of the graph. The algorithm and analysis of this problem mirror continual distinct elements estimation, and it is interesting to see whether we can obtain better additive error guarantees if we are allowed a small multiplicative error.
17

---

Published as a conference paper at ICLR 2026
C PROOFS FOR SECTION 3
We first prove intermediate lemmas about the error and privacy of Algorithm 1. Lemma C.I. Given privacy parameter p input, Algorithm 1 preserves p-zCDP.
Proof. Consider the algorithm A which, at every timestep t, reports the K + dimensional vector ft. Note that Algorithm 1 is simply a post-processing of this hypothetical algorithm. So, it suffices to consider the privacy of A. Consider two neighboring data streams and X' = (a ............. (a', 57) which are the same for all timesteps except for some i E [7] where (as, s;) + (d/, s().
(a1, $1),... (aT, sT)
...,,...
Note that the randomness of h is independent of the randomness used for privacy of all coun- ters CāK). Fix and let k = 1sb(h(a;)) and l = 1sb(h(a))). The distribution over (TC))))),T,EE.....)N)))))
is the same for A run on X and X'. We will proceed by cases
Consider the case where k * li2, and consider the counters C(ka] and C[k2]. The updates are the same these counters under X and X' all timesteps other than time At time i, under X, C[ki] receives update and C'K2]] receives update O while under X', C'ky]] receives update O and C[k2] receives update s/. This exactly corresponds the neighboring datasets relation for DP Continual Counting in Theorem 2.1. As C[ky] and C(ks2] are p" -CDP with p" p/2, by composition (Lemma 2.1), A is p-zCDP.
Consider the case where k = k = k2. The updates to C[k] are the same for all timesteps except at the ith timestep where the update is 8; under X and sy under X'. By the privacy of Ckk) given in Theorem 2. A satisfies (p/ (0/2)-ZCDP.
Lemma C.2. Consider any fixed timestep E [T]. pf O(log T) and the stream in the strict turnstile model, then the output of Algorithm satisfies
Dz/67 s D. S 4D, +1
with probability 2/3.
Proof. By the definition of r, with probability 1/ 1/poly(T),
[a(A]] [(]]]]
EE (E......
For the rest of the analysis, assume that this upper bound holds.
Consider any E {O..... KJ. For given element a [n]. Pra[1sb(a) = 2--(++) and (ræ[1sb(a) 2 2-
We will first show that the estimate Dr cannot be too small. It is always the case that f 0, so D, 2 1. Note that if D, S 67, then D, > Dz/6r by default.
Consider the case that D. > 67, and let i = (D))))] Let Z: a random variable for the number of elements in S₁ with least significant bit equal to i. Under full randomness, Z; would be distributed as Bin( D. 2 2-++))) Then, & E| E [3T, 67] and Var [2]] S By Chebyshev's inequality,
Var Z.] 6 2r
Pro < 2T|
Pri - 11 S 2r <
This quantity is upper bounded by 1/100 long is sufficiently large constant which is implied by p ((lgg((T))
With probability at least 99/100, there exists an index i > [log D. such that Z, > 2r. As all elements in S, have frequency at least (this is where we use the strict turnstile model) and by the additive error given by Theorem 2.1, fa[(] > т. As this is valid choice for f, e 2 [log( (2 ]. so
Dj 2
18

---

Published as a conference paper at ICLR 2026
Next will show that & cannot be too large. Any empty bucket with Z, 0 will have folil T. Consider the case where Di > and let j =
Then,
K Σ i=j
]
2, = = - 2-) D. 21-2-
Pr
2 3/4.
Under this event, l j. so D. S 4D,. Note that if D. then Σ Z: 0 and D,
Union bounding over all events, with probability 1- 1elpllpplyy)))) 1/000 1/100 1/4 2 2/3, the following holds:
Di/6r S D. - 4D, +1
Proof of Theorem 3.1. We will separately prove that the subroutine is private, accurate, and has bounded space.
Privacy Algorithm is a post-processing of the m copies of the subroutine Algorithm 1. By the privacy of the subroutine (Lemma C.I) and composition (Lemma 2.1), Algorithm 2 satisfies mp' = p-zCDP.
Error
Lemma C.2 bounds the error, for each timestep t, of each estimator D by
Dz/67 S D2 S 4D,+1 +1
where - = (log'
= (T)) This error bound holds with probability 2/3 under the condition that p' = O(lgg which is equivalent to p Ollog (T)).
(l)))
By standard argument, the median estimator will violate this error bound with probability exp(-S((m)) = 1/ppol(TT) via Hoeffding bound. The result follows by union bounding over all timesteps."
Space Each subroutine Algorithm maintains K + 1- O(log n) DP Continual Counters which each require O(log 7') space due to Theorem 2.1. In the error analysis of Lemma C.2, we require that the hash function à in] [m] satisfies certain pseudorandomness conditions. Specifically, we use the first and second moments of the random variables Z; under full randomness, which is guaranteed by a pairwise independent hash family. Such hash function can be stored in (11) words of space Carter & Wegman (1979). So, a single subroutine uses O n log 2') words of space. The overall algorithm with m copies of the subroutine uses space Oloog n log (T)).
'Technically, we prove the stronger result that the algorithm satisfics (OI) 1) error. We choose present the result as (O (T)) O (log (P)) as we only get non-trivial multiplicative approxi- mation of the number of distinct elements when it exceeds Olog' (T)/ Vp).
19

---

Published as a conference paper at ICLR 2026
D PROOFS FOR SECTION 4
The proofs Theorems 4.1 and 4.2 are based on a series of domain reduction lemmas, which allow us to reduce the size of the universe, while approximately preserving the number of distinct elements of the stream. The first lemma, Lemma D.I, gives anti-concentration bounds for the frequency of items when main size is smaller than the number of non-zero entries of the frequency vector by polylogarithmic factors, then all the non-zero frequencies in the reduced domain are "sufficiently large." Conversely, Lemma D.2 shows that if the reduced domain is sufficiently larger than the number of non-zero entries, then any single coordinate in the reduced domain is likely to be zero.
randomly hash the domain
smaller universe. It shows that if the reduced do-
These two lemmas form the foundation of the proof of Theorem 4.1, At a high level, we can reduce estimating the number of distinet elements to frequency estimation, which can be tracked up to polylogarithmic error via Theorem 2.1. To summarize, this is because if we reduce the domain to the "right size" (comparable to ||æz up to polylogarithmic factors), all domain elements will have large frequencies, and hence can be detected via Theorem 2.
Finally, the third domain reduction lemma, Lemma D.3, shows that the &g norm of a vector is preserved very precisely, if we again map the domain to suitably larger domain. This is the main technical tool in Theorem 4.2.
Lemma D.1 (Domain Reduction Lemma 1). Suppose n. is sufficiently large. Let h [m] [m]] and
g: [n] + {+1} be random functions. For a vector x E Z", define the mapping fg E 2n as
E [m],
fg,(();; =
Σ
g(i) -gj
with an empty sum denoting O. 1f S m S Iarllo for some N 100 log(n), then for every fixed i [m]), have
Vt
Pra. Sana
> 0.97.
1000
Proof. Fix an [m]. Let S; = = [n] 1 supp(æ), the support of æ that hash to the ith coordinate. Note that |S ~ Bin [| 4.). Noting that E, [|S.]] 2 2 100 log(n, we have that |S|] 2 f/2 with probability at least 0.999.
i} denote the elements in
Now conditioned on |S.| 2/2, know that
Σ 2( Kj
jES,
sum of weighted Rademacher random variables, where each |ay| 2 1. Since is a random function, assume without loss of generality that x, 1. Thus, the bound Erdōs (1945), again conditioned on [S|] 2 L/2, implies that
sup Pr
Σ 9
Ty E
<
50 Vt
g
JES;
for any interval I of length at most 1. By union bound over intervals,
Pr,
Σ g(
x
ve
Vi
|S 2
4/2
50
<
1000
1000
2000
Vi
40"
JES:
Therefore, we have
Pro.g [an(o))
Vt
2 Pr
Σ (()))xz3 &
Vi
Vt
|S|| Z 8/2
Pra[[Sa| 2 1/2)
1000
1000
1000
JES,
0.999(0.975) > 0.97,
desired.
20

---

Published as a conference paper at ICLR 2026
Lemma D.2 (Domain Reduction Lemma 2). Consider the same setting as Lemma D.1 but suppose m 2 E| Then for every fixed E [mm) we have
Prialfad(E) + 0] S 0.01.
Proof. We know |Si] ~ Bin([] ), so E, [|::]] - 7.-
7. Thus, the probability that |S,| * is at
most 1/L & 0.01 by Markov's inequality. In the case that S = 0, it is clear that (g,n(z); = 0, as
desired.
Lemma D.3 (Domain Reduction Lemma 3). Suppose sufficiently large and let h [n] [m]] be a random function as in Lemma D.1. For vector æ E R", define the mapping fa(x) E I as
Vi [m]. fn(x); = E
JE())A()=
with an empty sum denoting If 2 || e- ll for some l, 2 then
|=l|o [1)( 2 (1 (1- ||=
1 F
Pra
Proof. is clear that ||0||o II (x) lo holds deterministically, as fa may have collisions. For the other direction, for j E supp(r), let Xj denote the indicator variable that no other j' E supp(x) satisfies h(j') h(j). We have
I vello-1
1
1
Pra(X, =]
2
1
m
8.
Thus,
1
E
Σ
X,
2
1
||=||0-
e.
J (Euup((r)
so by Markov's inequality, have
10110
Prk
Σ
X,
2
S 8r
l
jEsupp(ar)
as desired.
We now ready to prove Theorem 4.1.
Proof of Theorem 4.1. First we prove privacy. Consider just one fixed function Sayn, for fixed i and j in Algorithm 3. For simplicity, just denote this f. Let (a), ..... (ar, ST) and 81)
(a', s be two neighboring streams for either event level privacy. Then ((ia), ..., (f((r) 8T) and (J(a)), i1),.. ... (J(a))), are also neighboring streams (for the same privacy model). This is because if a single event changes in the stream from say (a,, s;) to (a', s(), then this also induces at most single event change in the stream after mapping under (note it could also induce no change if the domain elements a; and of already collide under f and 8; s().
Thus, Algorithm keeps track of O(log T) different frequency estimations, each of which are p'- zCDP where / is an appropriate scaling of Then by composition via Lemma 2.1, outputting all the frequency estimates f under all functions f that we considered is p-zCDP, as desired. Note the rest of the algorithm proceeds by post-processing which also private.
Now we argue for the approximation factor. Fix timestep L. Assume for now that | > ((log" (T) The other case will be handled shortly. Now also consider one of our mappings < ||æ for 2 100 Iog( then for any fixed coordinate
to [2*]. Lemma D.I tells us that of the mapping f. that coordinate is larger than ((VE) in absolute value with probability at least 97%. In particular, if we pick the largest i such that 2 < O(I log(T)), then the coordinate
21

---

Published as a conference paper at ICLR 2026
wise median of .h (ze). ................................ Jaone my ho r) (zt) satisfies that all of its coordinates are larger than R(v in absolute value with probability 1/poly(T). This is still true if we consider the coordinates of Fr and set l (logg (T)og"(T)/p))) since we have additive error T O ((logl//(T)//V/ (T))/V) on every coordinate of mn, (z+).
Conversely, now consider the case where 2' 2 E||xz for the same choice of é as above. Then the coordinate wise median of f hy (zz)..... S Soque myoonn vy (Ia) satisfies that all of its coordinates are 0 with probability 1 - 1/poly(T) (T), and so || [) < C'r by picking C' sufficiently large.
To summarize, plugging in our value of p' and union bound, we have that any where 2 < Coaeelloo/oo/TTTT
O(I log" (T)) satisfies || (t)lls 2 C'r. Conversely, any where 2 2 22 ([)log(T)[l (T) (ll satisfies [F((t)) < C'T. Thus, our choice of i" (t) is a multiplicative O (T)) approxi- 1/poly(T).
mation |azello with probability
Now handle the case where | - (T))))T))p) Here, the above paragraph implies that won't It return anything larger than 2' where 2 2 f||zzllo which is O(log" 10 (T) which can be subsumed into our additive error. This completes the proof.
The proof of Theorem 4.2 uses similar ideas that of Theorem 4.1.
Proof of Theorem 4.2. For each m; = 24, consider Oloog T) maps h hi,..., h Votlor T) mapping
[n] + [m:]] as Lemma D.3. Each such map defines a new stream in the reduced domain [m,]. Now for each map, we would like to run algorithm A. First, we need to check that our definition of neighboring streams is still valid under a mapping. The proof of this is the same as in Theorem 4. 1. To summarize, the mapping will never add any new differences between neighboring streams (but it may actually reduce the number of differences if collision occurs).
Thus, we run (log" (T)) many copies of across all functions htj. Naturally we must scale p down by Q(log2(TT) so that our output remain private via composition of Lemma 1. In parallel, we also run another private algorithm B with Ologg (log)(TT)/ algorithm from Theorem 3.1). Note that this also further requires scaling down by constant factors. We also assume B3 is correct throughout all steps T,, which happens with probability 1 1/polyy
multiplicative and 1 additive error (e.g. our
Now the purported algorithm A' operates by post-proceet post-prrcessing the outputs of the two algorithms A and B (and thus satisfies the desired privacy guarantees). A'' does the following: every time step it first uses B to compute the smallest power of 2, denoted as m, which satisfies ((Ixrello) 2 m, 2 @[I vpl log" (T)). Then it outputs the median of the answers released by A, but only on the maps corresponding to the next power of 2, denoted as m/. which is larger than O m. ((g (so that m. satisfies the hypothesis of Lemma D.3 as we shall see shortly).
VPM
For conrectness, fix a time step t. Lemma D.3 implies that long as my > 2([1=allo// mn),
which is true by our choice, then the number of distinct elements under a map h [x]] + [m]] as in Lemma D.3 satisfies that (=))l is a 1 + b) approximation ity 99%. In which case, the median answer across (log independent copies of h is thus a n approximation with probability 1 1/poly(T'). However, each of our calls of A gives additive error | ei poly(log(T)). 1/p). our median output is 1 + 7 multiplicative and
|| llo with probabil-
[ poly (log (T') 1/p) additive error estimate. Since c < 1, ||xee160 can be absorbed into the multiplicative error, if ||=/|lo sufficiently larger than poly(log(T), 1/n, 1/p). This completes the proof.
22

---

Published as a conference paper at ICLR 2026
E PROOFS FOR SECTION 5
Proof of Theorem 5.1. The algorithm appears as Algorithm 4. Let og > 0 to be fixed later and let be the random matrix of the Johnson-Lindenstruus Lemma 2.3 with m z C1 /)/ag with C1 sufficiently large such that with high probability in T. it holds for all t E [T] simultaneously that if y( Ax then || [ ||x I ox vo]|az(011) I13 Our algorithm uses DP-algorithm for
continual counting estimate each entry of ( To see why this is possible, fix and denote by A; the ith row of A. Then
(Ax(*); = A,x
Σ Agpall)
Since the entries of A are 1 Vm. it follows that changing a single æs by E1l will change the count (Ax("); by at most (11/ Vm). To be precise, define bi....,by by by
b. Σ AGgalal
Σ j=1
Σ Acy(0s15 - x1-1l) E (-1/Vm,0.1///) 1=1
so that vi = : b- - A1j Then, if an adjacent dataset is obtained by replacing single input Sto) with (olg: s1,), then defining the b/ analogously for the neighboring dataset, is easy to check that b, 11 for * to- For some choice of privacy parameter Po. we may thus apply Theorem 2.1 (appropriately rescaled by 1/vm), obtain estimates it of v such that max lu| - = O (log 12 with high probability in I and such that outputting these estimates Po-ZCDP.
We not quite done as we want to release estimates of b. A.goo] for cach fixed i E [m]] For this, use the analysis above with the privacy parameter Po chosen such that when employing advanced composition over all m releases, the final algorithm is p-zCDP. By Lemma 2. 1, follows that we can put Po = p/m to achieve that over the m releases, the final algorithm is p-zCDP. The maximum final error of single estimate is thus O (log T) Denote by À this upper bound on the maximum error.
vP
Now since the above algorithm for releasing all estimates 0f is DDDP, by post-processing, we may release any function of these estimates without violating privacy. Our final estimate of 111 is simply Em ( Below, we analyze the accuracy of this estimator.
Accuracy Using that (0))² (ut)² 2 (0t that
vot + vt), and our bound 10! v S A, we have
Σ (1t)2
(vi)2
A
list + vi
[m[m]
(e(m]
iE|ml
Let S = {i E [m]] |vd < a/ao} and S2 = [m]] \
St.
Note that luil S A/ao implies that
lvd + 0i S X(1 + 1/ao) < 2\/an. Thus,
S|A
Σ VE
10t +
vil
ox
Moreover, lořl > A/ag implies that
00 vil
2| x 2 (vt)² + X, and so,
Σ
10
+ vil
1 112 + X|S2/. 200
SES
Combining these bounds, we get that
2
Σ
(0))
Σ
(2/)²
< 200l 1
ao
#E m2)
E [mmm
23

---

Published as a conference paper at ICLR 2026
It thus follows from the high probability guarantee of the JL map and the triangle inequality that,
2 + +oo 2 11 - (2ao(1 + oo) + ao) ||
2m
Σ (0 - 1 - 20ollval12 kE[m)
ag
ag
Picking ao = a/5, the above bound is at most al| gives the desired result.
10 Plugging in the values of m and 13 +
Space Usage It well known that the dimensionality reduction matrix A satisfies the guarantee of Lemma 2.3 even if the entries are only Ollog 7) independent Clarkson & Woodruff (2009). To
populate the entries of A, we can for example use k-independent hashing Wegman & Carter (1981) which when implemented as polynomials of degree k (loo T',, requires (log words of memory. We additionally, need store the counters for continual counting. By Theorem 2.1, this can be achieved with (m log 7) = O(log />?/a²) words of memory.
24


Reviews:
[{"review_id": "vjjweCmrVZ", "reviewer": "Reviewer_3SKD", "summary": "The paper provides new algorithms for differentially-private, low-space estimators of statistics on a **turnstile** data stream, where elements may be added and removed in the stream. The paper gives algorithms with a mixed multiplicative $polylog(T)$ and additive $poly(log(T)/\\epsilon)$ guarantee for counting distinct elements and $F_2$ estimation. These algorithm build on a pair of recent results, one that uses linear space to get an additive-only guarantee, and another that uses sublinear but still polynomial in T (about $T^{1/3}$) space. \n\nOn a technical level, the paper modifies existing sketching algorithms. They obtain significantly stronger results in the `strict turnstile' setting (where deletion requests only occur for items that actually exist in the current logical dataset) than in the general setting.", "questions": "* What is possible with item-level guarantees? (These are natural for cardinality, which is 1-sensitive to item-level changes at every time step.)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper provides a nice contribution to the literature on space-bounded private computations, addressing basic problems ($F_0$ and $F_2$ estimation). \n\n* The paper an open question explicitly asked by previous work of JKRSS (Jain et al, ICML 2023); it improves on [CEMMOZ] (Cummings et al., ICML 25), which explicitly addressed the same question.\n\n* The paper appears to be technically sound, with clear high-level overviews of the algorithms and proof ideas.", "weaknesses": "* The polylog multiplicative guarantee is quite weak. The previous work of CEMMOZ (as well as a combination of JKRSS and KNW'10) achieves a $(1+\\eta)$-multiplicative guarantee, and already demonstrates that sublinear additive error and space guarantees are possible. Is there any evidence that one cannot get a constant-factor multiplicative approximation along with a polylogarithmic additive error guarantee?\n\n\nSignificant, but not major, drawbacks: \n\n* The techniques in the paper are standard—they mostly consist of combining known tools in the right way. (There's nothing wrong with that, but it means that new technical tools are not a big contribution here.)\n\n* The fit for ICLR is a bit weird. Although cardinality estimation is a basic algorithmic and statistical topic, it's unclear how relevant it is to most of the ICLR audience. Of course, ICLR is quite broad at this point.\n\n* The comparison to previous work in Table 1 is missing a discussion of the work of [CEMMOZ]. That work provides the first sublinear-space algorithm for the problem (with a much tighter multiplicative guarantee and a much looser additive error and space guarantee than the ones in this paper). If I understood correctly, this submission points out that one could achieve a better result (that is, $(1+\\eta, \\tilde O(\\sqrt[3]{T}))$ multiplicative/additive error in polylog space) by directly combining the JKRSS approach with an algorithm due to Kane et al. It's good to point that out, but I would still keep CEMMOZ in the discussion. (Also, it would be good to spell out the combination of JKRSS with Kane et al in a bit more detail—perhaps in the appendix—and clarify the attribution in Table 1, since the result does not appear in JKRSS.)\n\n\nMinor comments: \n\n* The exact (event-level) privacy definition is unclear until page 3 of the paper. Claiming \"differential privacy\" doesn't make sense without an adjacency notion. Given that several have been studied for this problem, it makes sense to clarify the point early. \n\n* The theorem statements claim 1/polylog(T) probability of error. Presumably one could amplify this by running several parallel copies of the algorithm (and increasing epsilon). Why the weaker statement?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mmRzqz2oFP", "reviewer": "Reviewer_NCxW", "summary": "The paper studies the problem of estimating statistics on a data stream under a general turnstile model. In this model, there is a strong lower bound that essentially rules out any algorithm with additive error that is logarithmic in the stream length. The problem is also studied in other models of streams, specifically insertion-only models, where one can achieve a polylog additive error with a small multiplicative approximation. \n\nThe paper gives algorithms for distinct element counting and F_2 moment estimation with additive error that scales with poly-log(T) at a cost of a large multiplicative error.", "questions": "Please look at my weakness point above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's strength lies in being the first private algorithm for distinct counting and F_2 moment estimation under the general turnstile update model. Their result also raises a general question as to what the tradeoff is between multiplicative and additive error. I also like the fact that the authors mention some open problems with proper discussion. \n\nIn terms of idea, I do not see something new that comes up and that is alright. I do not consider it a weakness and actually consider a strength with a small bias (so mentioning it in the strengths section).", "weaknesses": "My biggest worry is that the multiplicative error and the additive error have the same scale. In particular, what the authors end up showing in the upper bound side is that they can approximate distinct elements with polylog(T) multiplicative approximation (the additive term can get subsumed if we consider that there are at least $O(1)$ distinct elements). The same goes for $F_2$ estimation. This makes me a little worried about the strength of the result, especially because in both problems, one can achieve a significantly smaller multiplicative approximation (without privacy constraints). Since the extra $\\log^2(T)$ factor in space comes mainly because of continual release, we can take $\\rho = O(\\log^4(T))$ and get a constant approximation, but larger space than non-private variants. Ideally, one sanity check I like to make is to let the privacy parameter go to $\\infty$, and we should recover the result in a non-private setting. That does not seem to happen here. Can the authors shed some light here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QbEL96k9qW", "reviewer": "Reviewer_Azzh", "summary": "This paper considers the differentially private estimation of the fundamental stream quantity of distinct elements (and F2 norm). The privacy (and utility) guarantee is with respect to all intermediate updates of the number of distinct elements. This is kknown as the continual release model of differential privacy. \n\nPrior work shows an $T^{1/3}$-additive error algorithm, where $T$ is the stream length, for continually counting the number of disinct elements in turnstile streams, where stream updates consist of elements insertions and removals. They also show a lower bound of $T^{1/4}$ on the additive error. (The problem is much simpler for insertion-only streams, where polylog T error is achievable). The authors of this paper show that by allowing mulitplicative  error, we can bypass the polynomial lower bound on the additive error. They show an algorithm with polylogT additive and mulitplicative error that also has polylogT space (the prior work used polynomial in T space). \n\nAn open question on the optimality of the multiplicative error remains, in particular can there be algorithms with constant multiplicative error for this private estimation problem?", "questions": "The algorithm in Section 4 was hard to grasp without much explanation in words. Could you please provide an overview of the technical novelty for Algorithm 4 compared to existing work in the non-private literature?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper opens an interesting research direction of considering multiplicative error algorithms in the space of continual release algorithms, where strong additive error lower bounds are known. \n\n- Allowing for multiplicative error gives rise to algorithms with polylog space, which has been a relevant question of prior works (Jain et al 2023, Cummings et al 25).", "weaknesses": "- The algorithmic techniques are not very novel, the main results are achieved through a combination of common streaming algorithms and the differentially private technique of continual counting. \n\n- Without lower bounds, it is hard to say how close/far from optimal the approximation bound is. It is very open whether an algorithm with constant multiplicative error exists.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KFh98oh1XW", "reviewer": "Reviewer_RNQM", "summary": "The paper studies (approximately) differentially private (DP) release of the number of distinct items in a turnstile stream, where at each step an item can be either added or removed from the active set. The stream has length $T$, the universe of items is of size $n$, and the notion of neighboring is *event-level*, meaning that the input at a single step can change. Past work showed a lower bound of $\\Omega(T^{1/4})$ (Jain et al., 2023a) (event-level) and gave an algorithm running in $\\tilde{O}(T^{1/3})$ (Jain et al., 2023b) (item-level), both on the additive error achieved by the algorithm. This paper circumvents the lower bound by considering mixed error guarantees which are also *multiplicative*, showing that $\\mathrm{polylog}(T)$ additive error is possible if $\\mathrm{polylog}(T)$ multiplicative error is tolerated. This can be contrasted with other lines of work (Jain et al., 2023a; Henzinger et al., 2024a; Cummings et al., 2025) that instead pursue guarantees parameterized in the input.\n\nThe paper also investigates the $F_2$ moment on turnstile streams, showing that any purely additive error guarantee necessarily is $\\Omega(T)$, but that if constant multiplicative error is allowed then $\\mathrm{polylog}(T)$ additive error is possible.\n\nThe techniques in the paper are based on sketching, where the counting problem on the turnstile stream is reduced to running many parallel instances of differentially private continual counting. Algorithm 2 builds on MinHash, Algorithm 3 (conceptually in my view, see later question) on CountSketch and Algorithm 4 on the AMS sketch for $F_2$ estimation.", "questions": "Overall, I find the paper well-written and interesting with a meaningful contribution. I also think it invites clear follow-up work. I recommend it for acceptance, but I have some concerns regarding the novelty of the techniques used (hence my confidence score). I think the paper would benefit from, at least a brief, discussion of how the techniques employed compare to past work.\n\n1. How novel are your techniques over past work for counting distinct elements on turnstile streams specifically? How do your techniques differ?\n2. Can Algorithm 3 be viewed as continual release of CountSketch, in a “high-collision regime”? If so, how does it compare to the continual release of CountSketch employed in Epasto et al. (2023)?\n3. Do you believe your techniques could be extended to work for item-level DP?\n4. Not a severe issue, but I think the inequality you state on line 856 in the proof of Lemma C.1 is wrong. My understanding of the argument is that you enlarge the unit-sized interval to have size $\\sqrt{l}/500$, and then union bound over ~this number of unit-sized intervals, but then the first factor on the right-hand-side should be divided by 500 rather than 50000, right? If this is an error, I think it should only impact constants in Lemma C.1, nothing in the main paper.\n\n*Typos/comments:*\n- General comment: The exact assumption on the hash/random functions involved are not stated clearly. E.g., in Algorithm 1, Step 2 it is a “random hash function” from $[n]$ to $[n]$, Lemma C.1 only specifies that $f$ and $g$ are “random functions”. From the proof of the space usage in Theorem 3.1, you state that pairwise independent hash functions are enough for the analysis in that case, and necessary for the claimed space usage, but it is not stated in the main theorem. It would benefit the clarity of the paper if the requirement on the hash functions was more explicit. Perhaps it could be stated once that e.g., \"all hash functions are assumed pairwise independent and can be stored in space...\", if the requirement is consistent throughout the paper.\n- Line 043-044: References appear twice?\n- Line 150-151: remove “to”\n- Line 318-319: The interpretation of $f_t[k]$ seems wrong to me, that it is the number of elements at time $t$ whose value hash into $[2^k, 2^{k+1})$. I think this would only be true if it tracked the *most* significant bit.\n- Line 393:  Step 3 of Algorithm 3 missing a “for”\n- Line 444: If it *is* possible\n- Line 485: Remove “for” in “algorithm for behind”. Stylistic preference “that it satisfies” -> “it satisfying”.\n- Line 820: *form* the foundation..\n- Line 843: [k]now\n- Line 851 and 855: I think it would not hurt to add a bit of motivation for why these inequalities hold. The first seems like a loose invocation of a bound by Erdos and the second a union bound.\n- Line 847: Again, it is not just any random function.\n- Line 872: Large[r]", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem of (DP) counting distinct elements on a turnstile stream is easy to motivate, and a fundamental problem in DP. Given the existence of a polynomial lower bound on the additive error, studying the problem under a multiplicative guarantee is natural and well-motivated.\n2. The paper is overall well-written, with the main part of the paper giving enough intuition for the results while still giving broader context.\n3. The techniques/ideas used are natural, and the proofs in the appendix that I checked seemed correct (up to constants, see questions).\n4. The message that polynomial additive errors can be replaced by polylogarithmic additive errors at the expense of (potentially non-trivial) multiplicative error, and sometimes in low space, is relatively clean and nice. I think this message, in combination with the Open Problems section, will lead to additional future work in this direction.\n5. The subject fits the scope of ICLR.", "weaknesses": "1. A $\\mathrm{polylog}(T)$ multiplicative guarantee will not always be competitive with the pure additive error guarantees parametrized in e.g., flippancy (Jain et al. (2023a)) or total flippancy (Henzinger et al. (2024a)). Many natural streams are prone to exhibit low flippancy (e.g., tracking occupancy in a store). The multiplicative guarantee can potentially offer an improvement in pathological cases where the flippancy is very high, e.g., when updates are concentrated in a few items, but it is not clear to me how realistic/interesting a setting this is.\n2. The paper only considers event-level DP, rather than item-level DP. It is not clear how (or if) the techniques could be extended to work for item-level DP.\n3. The techniques used in the paper, and how they compare to techniques used in past work on DP counting distinct elements on turnstile streams, are insufficiently discussed. This paper is not the first to use sketching in the context of DP more broadly, see e.g., [1,2,3,4]. [1] for example appears to solve the same problem in the setting where only the final number of distinct elements has to be released (i.e., not under continual release), and does so with a multiplicative/additive guarantee. More related still, the key building block in Epasto et al. (2023) is an implementation of CountSketch under continual release. It would strengthen the paper to discuss the extent to which its techniques differ from past work. This could mostly still be done in the appendix by extending Section A.\n\nReferences:\n- [1] The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space, Smith et al., NeurIPS‘20.\n- [2] Differentially Private Linear Sketches: Efficient Implementations and Applications, Zhao et al., NeurIPS’22.\n- [3] Improved Utility Analysis of Private CountSketch, Pagh & Thorup, NeurIPS’22.\n- [4] Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch, Lebeda & Tetek, ACM Trans. Datab. Syst.’25.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)