Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
Authors: David Woodruff
Samson Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: streaming algorithms
adversarial robustness
heavy-hitters
norm estimation
differential privacy
Primary area: optimization

Abstract: In the adversarial streaming model, the input is a sequence of adaptive updates that defines an underlying dataset and the goal is to approximate, collect, or compute some statistic while using space sublinear in the size of the dataset. In 2022, Ben-Eliezer, Eden, and Onak showed a dense-sparse trade-off technique that elegantly combined sparse recovery with known techniques using differential privacy and sketch switching to achieve adversarially robust algorithms for $L_p$ estimation and other algorithms on turnstile streams. However, there has been no progress since, either in terms of achievability or impossibility. In this work, we first give improved algorithms for adversarially robust $L_p$-heavy hitters, utilizing deterministic turnstile heavy-hitter algorithms with better tradeoffs. We then utilize our heavy-hitter algorithm to reduce the problem to estimating the frequency moment of the tail vector. We give a new algorithm for this problem in the classical streaming setting, which achieves additive error and uses space independent in the size of the tail. We then leverage these ingredients to give an improved algorithm for adversarially robust $L_p$ estimation on turnstile streams. We believe that our results serve as an important conceptual message, demonstrating that there is no inherent barrier at the previous state-of-the-art.

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
David Woodruff
Samson Zhou Department of Computer Science
Department of Computer Science Camegie Mellon University dwoodruf Candrew cmu. edu
Texas A&M University
samsonzhou@gmail com
Abstract
In the adversarial streaming model, the input is sequence of adaptive updates that defines underlying dataset and the goal is to approximate, collect, compute some statistic while using space sublinear the size of the dataset. 2022, Ben-Eliezer, Eden, and Onak showed dense-sparse trade-off technique that elegantly combined sparse recovery with known techniques using differential privacy and sketch switching to achieve adversarially robust algorithms for Lp estimation and other algorithms on turnstile streams. However, there has been no progress since, either in terms of achievability impossibility. In this work, we first give improved algorithms for adversarially robust Ly he-ay hitters, utilizing deterministic turnstile heavy-hitter algorithms with better tradeoffs. We then utilize our heavy-hitter algorithm to reduce the problem to estimating the frequency moment of the tail vector. We give a new algorithm for this problem the classical streaming setting, which achieves additive error and uses space independent in the size of the tail. We then leverage these ingredients to give an improved algorithm for adversarially robust Lp estimation turnstile streams. We believe that our results serve as an important conceptual message, demonstrating that there no inherent barrier at the previous stateoof-theaars
Introduction
Adversarial robustness for big data models is increasingly important not only for ensuring the reliability and security algorithmic design against malicious inputs and manipulations, but also to retain guarantees for honest inputs that are nonetheless co-dependent with previous outputs of the algorithm. One such big data model the streaming model computation, which has emerged as central paradigm for studying statistics of datasets that are too large to store. Common examples of datasets that are well-represented by data streams include database logs generated from e-commerce transactions, Internet of Things sensors, scientific observations, social network traffic, or stock markets. To capture these applications, the one-pass streaming model defines an underlying dataset that evolves over time through number of sequential updates that discarded irrevocably after processing, and the goal is to compute or approximate some fixed function of the dataset while using space sublinear in both the length of the data stream and the dimension of the dataset.
The streaming model of computation. updates .i...., Um defines a dataset that is fixed in advance, though the ordering of the sequence of updates may be adversarial. other words, the dataset oblivious to any algorithmic design choices, such instantiations of internal random variables. This is vital for many streaming algorithms, which crucially leverage randomness to achieve meaningful guarantees in sublinear space. For example, the celebrated AMS sketch [AMS99] initializes random sign vector and outputs (ss, f) as the estimate for the Le norm of the underlying frequency vector f defined by the stream. To show
the classical oblivious streaming model, the stream S of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

correctness of the sketch, we require to be chosen uniformly at random, independent of the value of f. Similar assumptions are standard across many fundamental sublinear algorithms for machine learning, such as linear regression, low-rank approximation, or column subset selection.
Unfortunately, such an assumption is unreasonable [MNS11, 12, BMSC17, NY19, CN20), as an honest user may need to repeatedly interact with an algorithm, choosing their future actions based on responses to previous questions. For example, in recommendation systems, is advisable to produce suggestions so that when a user later decides to dismiss some of the items previously recommended by the algorithm, a new high-quality list of suggestions can be quickly computed without solving the entire problem from scratch [KMGG07, MBN 17, KZK18, OSU18, AMYZ19]. Another example is in stochastic gradient descent or linear programming, where each time step can update the eventual output by an amount based on a previous query. For tasks such as linear regression, actions as simple as sorting a dataset have been shown to cause popular machine learning libraries to fail [BHM+21].
Adversarially robust streaming model. In the adversarial streaming model [BY HKM 20, ABD*21, BH,+ KMNS21, WZ21b, BKM 22, BEO22, BJWY22, CGS22, ACGS23, ACSS23, DSWZ23, GLW+24], a sequence of adaptively chosen updates ....... Um is given as an input data stream to an algorithm. The adversary may choose to generate future updates based on previous outputs of the algorithm, while the goal of the algorithm is correctly approximate or compute a fixed function at all times in the stream. Formally, the black-box adversarial streaming model can be modeled as two-player game between a streaming algorithm A and a source C that creates stream of adaptive and possibly adversarial inputs to A. Prior to the game, a fixed statistic Q is determined, so that the goal of the algorithm is to approximate Q on the sequence of inputs seen at each time. The game then proceeds across m rounds. In the t-th round:
(1) C computes an update for the stream, which possibly depends on all previous outputs from A.
(2) A uses u, to update its data structures Dr, acquires a fresh batch Rg of random bits, and outputs a response Ze to the query Q
(3) E observes and records the response Z,-
The goal of E is to induce from A an incorrect response Z₁ to the query Q at some time t E [m]] throughout the stream using its control over the sequence ........ um- By the nature of the game, only a single pass over the stream is permitted. In the context of our paper, each update ue has the form (ix, A.), where it E [ni] and A, E {+1). The updates implicitly define a frequency vector I E RR," so that u, changes the value of the (it)-th coordinate of ʃ by A..
Turnstile streams and flip number. In the turnstile model of streaming, updates are allowed to either increase or decrease the weight of elements in the underlying dataset, as compared to insertion-onl streams. where updates are only allowed increase the weight. Whereas various techniques are known for the adversarial robustness on insertion-only streams, significantly less is known for turnstile streams. While near-optimal adversarially robust streaming algorithms for fundamental problem such as Lp estimation have been achieved in polylogarithmic space for p S 2 by [WZ21b] in the insertion-only model, it is a well-known open question whether there exists a constant C = 2(1) such that the same problems require space Q(nC), where n is the dimension of the underlying frequency vector. Indeed, [HW13] showed that the existence of a constant C C== 2211) such that no linear sketch with sketching dimension o(n can approximate the Le norm of an underlying frequency vector within even a polynomial multiplicative factor, when the adversarial input stream is turnstile and real-valued.
Given an accuracy parameter (1 + e). the flip number À is the number of times the target function Q changes by a factor of (1 +1+00 O (E)). It is known that for sylymomiallybbounde monotone functions Q on insertion-only streams, we generally have X = O ( m)) but for turnstile streams that toggle the underlying frequency vector between the all-zeros vector and a nonzero vector with each update, we may have À= = (m)). There are various techniques that then implement À [BJWY22] or even roughly VÁ [HKM+20 ACSS23] independent instances of an oblivious algorithm, processing all stream updates to all instances. Therefore, the space complexity of these approaches are at least roughly v X times the space required by the oblivious algorithm, which may not be desirable in large setting of x= = 2(m) for turnstile streams. By considering dense- sparse tradeoffs, [BEO22] gave general

---

framework that improved upon the Ô ticular, their results show that Ô (mz/ (2pp)))))) space suffices for the goal of Lp norm estimation, where the objective is to estimate (f +... f2) 1/P for an input vector f E I2", which is an important prob- lem that has a number of applications, such network traffic monitoring [FKSV02, KSZC03, TZ04], clustering and other nigh-dimensional geometry problems 181RW16, CJLW22, CCJ+23, CWZ23], low-rank approximation and linear regression [CW09, 10SW10, BDM+20, VVWZ23, WY23], earth-mover estimation [Ind04, AIK08, ABIW09], cascaded norm estimation [JW09, MRWZ20J, and entropy estimation [HNO08]. Unfortunately, there has been no progress for Lp estimation on turnstile streams since the work of [BEO22], either in terms of achievability or impossibility. Thus ask:
(V Ô (vm) space bounds due the flip number. In par-
Is there fundamental barrier for adversarially robust Ly estimation on turnstile streams beyond the dense-sparse tradeoffs?
1.1 Our Contributions
In this paper, answer the above question in the negative. We show that the techniques of [BEO22] do not realize a fundamental limit for adversarially robust L, estimation on turnstile streams. In particular, we give an algorithm that uses space Ô (m²), for some constant < 2p+1 We first require an adversarially robust algorithm for heavy-hitters.
P for E (1,2).
Heavy hitters. Recall that the e-Tay-hevvy hitter problem is defined follows.
Definition 1.1 (e-Ly-heavy hitters). Given a vector f E R" and a threshold parameter 5 E (0. 1), output list C that includes all i such that f. E [|p and includes such that f, < 2 [[
Generally, heavy-hitter algorithms actually solve the harder problem of outputting estimated frequency fr such that If. fil S C E Ip.f for each E [n]. where C' some constant such as G. Observe that such guarantee solves the -heavy hitters problem because each i such that fi 2 e || must have Zi - [Il and similarly each j such that f; > 36 must have fa 2 5 |p We give an adversarially robust streaming algorithm for the Lp-heavy hitters problem on turnstile streams.
Theorem 1.2. Let p E (1, There exists an algorithm that uses Ô ( ( space and solves the h-Tvy hitters problem at all times in an adversarial stream of length m.
bits of
Though not necessarily obvious, our result in Theorem 1.2 improves on the dense-sparse framework of [BEO22] across all p [1. 2). Specifically, the result of [BEO22] uses space Ô (m²) for 2p+1'
while our result uses space Ô (me) for 3 2p-2 It can be shown that a - B 31--312p+1}
--p
1p-3
which is at positive for all p E [1, 2). Thus our result an important conceptual contribution showing that the true nature of the heavy-hitter problem lies beyond the techniques of [BEO22].
A particular regime of interest is p 1, where the previous dense- sparse framework of [BEO22] achieves Ô (m2/3) bits of space, but our result in Theorem 1.2 only requires polylogarithmic space.
Moment estimation. Along the way to our main result, we also give a new algorithm for estimating the residual of frequency vector up to some tail error. More precisely, given frequency vector that is defined implicitly through a data stream and a parameter & > O, let g be a tail vector of f. which omits the A entries of f largest in magnitude, breaking ties arbitrarily. Similarly, let h be tail vector of f that omits the (1 - e)k entries of ff largest in magnitude, where E E (0, 1) serves as an error parameter. Then give one- streaming algorithm that outputs estimate for l|9 l/ up to additive e [|l] using space poly (L. log logn). In particular, our space is independent of the tail parameter k. We defer the full guarantees of our algorithm as well as more formal discussion to Section 3. We then give our main result:
Theorem 1.3. Let E [1,2] and c [4p 23 There exists streaming algorithu that uses O (m)) poly (L, log(nm)) bits of spuce and outputs a (1 + E) apprroxiimtiio to the Top norm of the underlying vector at all times of an adversarial stream of length m.
3

---

It can again be shown that our result in Theorem 1.3 again improves on the dense-sparss framework of [BEO22] across all E (1. For example, for p = 1.5, the previous result uses space Ô (m2/6) Ô (m (m0)) while our algorithm uses space Ô (m
Ô (m))).) Although our quantitative improvement is mild, we believe it nevertheless illustrates an important message which shows that the dense-sparse technique does not serve as an impossibility barrier.
1.2 Technical Overview
Recall that the flip number to be the number of times the Fe moment changes by a factor of (1 + O (E)), given target accuracy (1 + E). Given stream with flip number X, the standard shetch-switching technique [BJWY22] for adversarial robustness is to implement À independent instances of an oblivious streaming algorithm for F, estimation, iteratively using the output of each algorithm only when it differs from the output of the previous algorithm by a (1 + e) --multiplicative factor. Subsequently, [HKM+20 20, ACSS23] showed that by using differential privacy, it suffices to use roughly VÀ independent instances of an oblivious streaming algorithm for F' estimation to achieve correctness at all times for an adaptive input stream. Unfortunately, the flip number for stream of length m can be large as (mm), such as in the case where the underlying frequency vector alternates between the all zeros vector and a nonzero vector.
The dense-sparse framework of [BEO22] observes that the only case where the flip number can be large is when there are a large number of times in the stream where the corresponding frequency vector is somewhat sparse. For example, in the above scenario where the underlying frequency vector alternates between the all zeros vector and a nonzero vector, all input vectors are 1-sparse. In fact, they notice that for F, estimation, that once the frequency vector has at least m. nonzero entries for any fixed constant C E (0, 1), then since all entries must be integral and all updates only change each entry by 1, at least S2g (m (/P) updates are necessary before the p-th moment of the resulting frequency vector can differ by least (1 + e)-multiplicative factor. Hence in the stream updates where the frequency vector has at least m C nonzero entries, the flip number can be at most O (m-- for e = (1).. Thus it suffices to run Ô (m1/2-C/2p) independent instances of the oblivious algorithm, using the differential privacy technique of [HKM+20, ACSS23). Moreover, in the case where the vector is m mnC-sprree there are sparse recovery techniques that can exactly recover all the nonzero coordinates using Ô (m- space, even if the input is adaptive. Hence by balancing Ô (m²) = ó (m/2/2-0/22) at C' = 3. [BEO22] achieves Ö (mp/(2p+1) overall space for Fp estimation for adaptive turnstile streams.
Our key observation is that for E (1,2), if the frequency vector has at least m nonzero entries, a sequence of O.(mm//) updates may not always change the p-th moment of the underlying vector. For example, if the updates are all to separate coordinates, then the p-th moment may actually change very little. In fact, a sequence of Og (m C/P) updates may only change the p-th moment of the underlying vector by (1 [++) =) if most of the updates are to a small number of coordinates. As a result, most of the updates are to some coordinate that was either initially a heavy-hitter or subsequently heavy-hitter. Then by tracking the heavy-hitters of the underlying frequency vector, we can handle the hard input for [BEO22], thus demanding a larger number of stream updates before the p-th moment of the vector can change by (1 +)). Consequently, the number of independent instances decreases, which facilitates a better balancing and allows us to achieve better space bounds. Unfortunately, there are multiple challenges to realizing this intuition.
First, we need a streaming algorithm for accurately reporting the frequencies of the Lp-heavy hitters at all times in the adaptive stream. However, such a subroutine is not known and naïvely, one might expect an estimate of the Lp norm might be necessary to identify the Lp heavy-hitters. Moreover, algorithms for finding Lp heavy-hitters are often used to estimate the Lp norm of the underlying frequency, e.g., [IWO5, WZ12, BBC LSW18, BWZ21, WZ21a, MWZ22, BMWZ23, JWZ24]. Instead, we use a turnstile streaming algorithm DETHH for Lp heavy- hitters [GM07] that uses sub-optimal space Ô ( 2222 bits of space for P E (1, 2). rather than the optimal COUNTSKETCH, which uses O logg
Heavy-hitters.
2og?nn n) bits of space. However, the advantage of DETHH is that the algorithm is deterministic, so we can utilize the previous intuition from the dense-sparse framework of [BEO22]. particular, if the universe size is small, then we can run DETHH, and if the universe size is large, then we collectively handle these cases using an ensemble

---

of COUNTSKETCH algorithms via differential privacy. We provide the full details of the robust Lp he-ay hitter algorithm in Section ultimately achieving Theorem 1.2.
Residual estimation. It remains to estimate the contribution of the elements that are not Tp heavy- hitters, i.e., the residual vector, toward the overall p-th moment. More generally, given tail parameter k > 0 and an eπror parameter & E (0, 1), let be a tail vector of f that omits the k entries of f largest in magnitude, breaking ties arbitrarily and let be a tail vector of f that omits the (1 =) entries of f largest in magnitude. We define the level sets of the p-th moment so that level set A roughly consists of the coordinates of g with magnitude [[1 + =)
% (1 + =) We then estimate
the contribution of each level set to the p-th moment of the residual vector using the subsampling framework introduced by [IWO5].
Namely, we note that any "significant" level set has either a small number of items with large magnitude, a large number of items that collectively have significant contribution to the p-th moment. In the former case, we can use COUNTSKETCH to identify the items with large magnitude, while in the latter case, it can be shown that after subsampling the universe, there will be large number of items in the level set that remain. Moreover, these items will now be heavy with respect the p-th moment of the resulting frequency vector after subsampling with high probability. Thus, these items can be identified by COUNTSKETCII on the subsampled universe. Furthermore, after rescaling inversely by the sampling probability, the total number of such items in the level set can be estimated accurately by rescaling the number of the heavy-hitters in the subsampled universe. Hence in both cases, we can estimate the number of items in the significant level sets and subtract off the largest & such items. We provide the full details of the residual estimation algorithm in Section 3, culminating in Theorem 3.4.
Adversarially Robust Lp-Heavy Hitters
In this section, give an adversarially robust algorithm for Lp-heavy hitters on turnstile streams. We first recall the following deterministic algorithm for Lp-heavy hitters on turnstile streams.
Theorem 2.1. [GM07] For p E [1, 2), there exists a deterministic algorithm DETHH that solves the e Ly heavy-hitters on a universe of size and a stream of length m and uses 12 22-2/p polylog tm =
bits of space.
We also recall the following variant of COUNTSKETCH for answering a number of rounds of adaptive queries, well more general framework for answering adaptive queries.
Theorem 2.2. /CLN+22) 22) For p (1,2), there exists randomized algorithm ROBUSTCS that uses
δ A log n log mmn bits of space, and for X different times t on an adaptive stream of length m
on a universe of size n, reports for all E [n] an estimate f( such that If! f((') S where f()) is the induced frequency vector at time t. Theorem 2.3. 20, BKM+ ACSS23, CSW+ 23] Given a streaming algorithm A that uses S space and answers query with constant failure probability da < 1. there exists a data structure that answers Q adaptive queries, with probability 1 using space (sVQlog²) 9).
5 -1
100
While ROBUSTCS has better space guarantees than DETHH, determinism nevertheless serves an important purpose for us. Namely, adversarial input can induce failures on randomized algorithms but cannot induce failures grows with the size of the universe. Thus, we now use insight from the dense-sparse framework of [BEO22]. If the universe size is small, then shall use DETHH. On the other hand, if the universe size large, then shall use the following robust version of COUNTŠKETCH, requiring roughly vÀ number of independent instances, where À is the flip number. The key observation is that because the universe size is large. then the flip number will be much smaller than in the worst possible case. Moreover, we can determine which case we in, i.e., the large universe case or the small universe case, by using the following Lo estimation algorithm:
deterministic algorithms. On the other hand, the space usage of DETHH
Theorem 2.4. [KNWI0] There exists an dasertion-deletioe streaming algorithm LZEROËST that uses O ( log log 3 (Iog? + log log m)) bits of space, and with probability at least 1 - 6, outputs (1 + E) aapppoxxmmation to Lo-
5

---

Algorithm 1 ROBUSTHH: Adversarially robust Lp-heavy hitters
Input: Turnstile stream of length m for frequency vector of length
Output: Adversarially robust heavy-hitters
t (mp/(lp-3)), e < 100 ///p, b .TSTTTE <- SPARSE
2: Initialize DETHH with threshold =
16
3: Initialize ROBUSTCS robust to queries, with threshold i for O /x rounds
4: Initialize Ô (vb) copies LZEROEST with accuracy robust b queries
5: for each block of l updates do
6: Update DETHH, ROBUSTCS, and all copies of L.ZEROEST
7:
if STATE- SPARSE at the beginning of the block then
8:
Return the output of DETHH
9:
else
10:
Return the output of ROBUSTCS at the beginning of the block
TTheorem 2.2 >Theorem 2.3 and Theorem 2.4
11:
Let Z be the output of robust LZEROEST
if Z >> 100t then
13:
STATE + DENSE
else
15:
STATE <- SPARSE
We give our algorithm in full in Algorithm 1. Because DETHH a deterministic algorithm, it will always be correct in the case where the universe size is small. Thus, we first prove that in the case where the universe size is large, then ROBUSTCS ensures correctness within each sequence of e updates.
Lemma 2.5. Suppose the number of distinct elements the beginning of a block is at leust 50L. Let S be the output of ROBUSTCS at the beginning of a block. Then conditioned on the correctness of ROBUSTCS, S solves the heavy hitter problem on the entire block.
Next, we show that ROBUSTCS ensures correctness in between blocks as well. We also analyze the space complexity of our algorithm.
Lemma 2.6. With high probability, ROBUSTCS is correct at the beginning of each block of length é.
Lemma 2.7. The total space by the algorithm is Ô m 22/-2)/44-)3))) bits of space.
Given our proof of correctness in Lemma 2.5 and Lemma 2.6, well as the space analysis in Lemma 2.7, then we obtain Theorem 1.2.
3 Oblivious Residual Estimation Algorithm
In this section, we consider norm and moment estimation of a residual vector, permitting bicriteria error by allowing some slack in the size of the tail. Specifically, suppose the input vector f arrives
in the streaming model. Given a tail parameter A: >> 0 and an error parameter E (0. 1), let be tail vector of f that omits the & entries of ʃ largest in magnitude, breaking ties arbitrarily and let be a tail vector of f that omits the (1 - k entries of f largest in magnitude. We give an algorithm that estimates ||//| || up to additive e ||/l|p using space poly (). log n). which is independent the tail parameter k. It should be noted that our algorithm is imprecise on l[gl]g I in two ways. Firstly, it incurs additive error proportional to Secondly, the additive error has error with respect to h, which is missing the top (1 - k) entries of f in magnitude, rather than the top k. Nevertheless, the space bounds that independent of l: are sufficiently useful for subsequent application of T.p estimation. We first define the level sets of the p-th moment and the contribution of each level set.
Definition 3.1 (Level sets and contribution). Let n > 0 be parameter and let m be the length of the stream. Let M be the power of two such that m2 < M < (1 nimp and let Ç [1,2]. Then
for each integer E 2 define the level set T2 i [m] ft
- (1+1) } We also
CM CM
define the contribution Ce of level set I' be Ct Eier, (f.P.

---

For residual vector 9 of f with the top k coordinates set to be zero, we similarly de- fine the level sets Dg and D₃ of g in the natural way, i.e, Dj = Eier, for M.
{i [n] gi E (1tT) (1+1)²
CM CM
Algorithm RESIDUALEST: residual F3 approximation algorithm, p E [1,2]
Input: Stream $1..... 8m of items from [nx] accuracy parameter E (0, p E [1.2]
Output: (1 + a)aaproxximaooon F,
1: 1) -- 100
_ L Ô log(nm)
P= Ô (log(nm)),
Ô (log Ing . 22
2: for (= = 1 to m do
3:
for (i,r) E [P] x [R] do
Let (!!)) be a (nested) subset of [n]] subsampled at rate min (1, (1,2
4:
5:
if st E U then
Send 8, COUNTSKETCH"" (t) with accuracy 17² 7: Let M = 2' for some integer 2 0, such that m² & M < 2m
6:
8: c c k
9: for l == to l = I do
10:
+ max (1.
log(1 + n) log 12 log(nm)
Let H7!1)) the outputs of COUNTSKETCH at level
11:
12:
Let s(r)) be the set of ordered pairs (..fa) of H with (f))E
(I+n)<-) (1+7)
CM
Tel + 1 median,e(aa | Te + max F c)
13:
14:
t max(c- - 0),
15:
Ae Te (1 n))
16:
Return F (..Res(k) Exe(y [M + t)
Our algorithm attempts to estimate the contribution of each level set. Some of these level sets contribute a "significant" amount to the p-th moment of f, whereas other level sets do not. It can be seen that the number of items in each level set that is contributing can be estimated up (1+ O (E)) approxxiiatnn In particular, either a contributing level set has a small number of items with large mass, or a large number of items that collectively have significant mass. We use the heavy-hitter algorithm COUNTSKETCH to detect the level sets with small number of items with large mass, and count the number of items in these level sets. For the large number of items that collectively have significant mass, it can be shown that after subsampling the universe, there will be a large number of these items remaining, and those items will be identified by COUNTSKETCH on the subsampled universe. Moreover, the total number of such items in the level set can be estimated accurately by rescaling the number of the heavy-hitter sampling probability. We can thus carefully count the number of items in the contributing level sets and subtract off the largest such items. Because we only have (1 + e) approxximatio to the number of such items, it may be possible that we subtract off too many, hence the bicriteria approximation.
the subsampled universe inversely by the
Finally, we note that for the insignificant level sets, we can no longer estimate the number of items in these level set up to (1 + e)-factor. However, we note that the number of such items is only an 8 fraction of the number of items in the lower level sets that are contributing. Therefore, we can show that it suffices to set the contribution of these level sets to zero. Our algorithm appears in full in Algorithm 2.
We now show that the number of items (as well as their contribution) in each "contributing" level set with small number of items with large mass will be estimated within (1 + approxxiaitt
Lemma 3.2. Let E [R] be fixed. Then with probability at least 9 we have that simultaneously "²,F,(!!") 27 log (nm))
for all j U for which (1z)² 2
H:(") outputs J, with (1 sog(mm)) (Jz)
(J,)² < (1+ 8 (og(mm)) (.z)..
7

---

We now show that the number of items in each "contributing" level set is estimated within a (1 + E)- approximation, including the level sets that contain large number small items.
Lemma 3.3. Given a fixed E (0,1), let Ae be fixed level set and ler r [R] be fixed. Let
i max (I.[oo((1 and &g to be the event that FT( I 32F2, Then conditioned on &1 and &2, for each j E A
log(1 + +n) - loog" 12 (llg(nmm) 1). Define the events &1 be the event that | S 32n
"
there exists (5) in S such that with probability at least 9
Blog(am)) (f)) S (f))
(I (lo((mm)) (f,)².
Putting things together, we have the following full guarantees for our algorithm. Theorem 3.4. There exists a one-pass streaming algorithm RESIDUALEST that takes an input
parameter k 2 (possibly upon post-processing the stream) and uses O ( llogo (nm)) bits of
space to output estimate Fe.Res(k) with Pr p.Rs((()) Fp,Res(k) E E. Fp,Res((--eA))
2
Adversarially Robust Lp Estimation
In this section, we give an adversarially robust algorithm for Fp moment estimation on turnstile streams. Due to the relationship between the Fp moment and the L, norm, our result similarly translates to robust algorithm for Lp norm estimation. We first require an algorithm recover all the coordinates of the underlying frequency vector if it is sparse.
Theorem 4.1. [GSTV07] There exists deterministic algorithum SPARSERECOVER that recovers k-sparse frequency vector defined by an ixsertionddeletion stream of length n. The algorithm uses k- polylog(n) n) bits of space.
Algorithm 3 Adversarially robust L, esttmmttti
Input: Turnstile stream of length m for frequency vector of dimension n
Output: Adversarially robust heavy-hitters
1: c + 24p" -2p++4
(42p3))12p+3) Y < 2c (4p-4)
(20p-15)> 17 f 100m 1 + O et O
STATE + SPARSE
2: Initialize SPARSERECOVER with sparsity O (m²)
3: Initialize ROBUSTHH with threshold En)
4: Initialize LZEROEST with accuracy 2 robust to b: queries
5: Initialize RESIDUALEST with parameter &o and accuracy (E) robust to b queries
6: for each block of & updates do
7: Update ROBUSTHH, I.ZEROEST, and RESIDUAL EST
8: STATE- = SPARSE at the beginning of the block then
9:
Let g be the vector output by SPARSERECOVER
G G+11g 1g
10:
Return G
12: else
Let g be the vector output by ROBUSTHH at the beginning of the block Let H be the output of RESIDUALEST
14:
15:
1
Return G
Let Z be the output of robust LZEROËST
18:
if Z > 100l then
19:
STATE DENSE
20:
else
STATE <- SPARSE
We remark that SPARSERECOVER is deterministic and guarantees correctness on turnstile stream, even if the frequency vector is not sparse some intermediate step of the stream. On the other hand,

---

if the frequency vector is not sparse, then a query to SPARSERECOVER could be erroneous. Hence, our algorithm thus utilizes robust EST to detect whether the underlying frequency vector is dense or sparse. Similar to [BEO22]. the intuition is that due to the sparse case always succeeding, the adversary can only induce failure if the vector dense, which in turn decreases the flip number. However, because we also accurately track the heavy-hitters, then the adversary must spread the updates across a multiple number of coordinates, resulting in a larger number of updates necessary to double the residual vector. Since the number of updates is larger, then the flip number is smaller, and so our algorithm can use less space. Unfortunately, even though the residual vector may not double in its p-th moment, the p-th moment of entire frequency vector f may change drastically. This is nuance for the analysis because our error guarantee can no longer be relative to the ll Indeed, e lll additive error may induce (1 - - error at one point, but at some later point we could have || < Il so that the same additive error could even be polynomial multiplicative error. Hence, we require the RESIDUALEST subroutine from Section 3, whose guarantees are in terms of the residual vector. We give our algorithm in full in Algorithm 3.
We upper bound the amount that the p-th moment of the residual vector can change, given a bounded number of updates.
Lemma 4.2. Let f be a frequency vector and g be the residual vector omitting the ls coordinates of f largest in magnitude. Let v be any arbitrary vector such that ||e]]] S 10O -lllll> k'-1/p and I|l|| S 1[l]|1 Let u be the residual vector omitting the k coordinates of f + + largest in magnitude. |l
Then we have ||91| - [|u|pp]
We now show correctness and space complexity of Algorithm 3. after which Theorem 1.3 follows.
Lemma 4.3. For log = @(log Algorithm uses Ô (sts m(² bits of space in total. Moreover, for any fixed time during a stream, let f be the induced frequeccy vector and let F be the output of Algorithm 3. Then we have that with high probability, (1 f) & F S +1+ f)lffI
Empirical Evaluations
In this section, we describe our empirical evaluations for comparing the flip number of the entire vector and the flip number of the residual vector on real-world datasets. Note that these quantities parameterize the space used by the algorithm of [BEO22] and by our algorithm, respectively.
CAIDA traffic monitoring dataset. We used the CAIDA dataset [CAI16] of anonymized passive traffic traces from the "equinix-ny -ncc' data center's high-speed monitor. The dataset is commonly used for empirical evaluations on frequency moments and heive-hitters. We extracted the sender IP addresses from 12 minutes of the internet flow data, which contained 2.9922,873 total events.
Experimental setup. Our empirical evaluations were performed Python 3.10 on a 64-bit operating system on an AMD Ryzen 7 5700U CPU, with 8GB RAM and 8 cores with base clock 1.80 GHz. We compare the flip number of the entire data stream versus the flip number of the residual vector across various values of the algorithm error {10-1, 10-2 ..... 10-$3, values of the heavy-hitter threshold a E {4-1, 4-2 ,..., 4-10), J, and the frequency moment parameter E {1.1, 1.2,..., 1.9). We describe the results in Figure
1100
22
(a) Flip number across login 8
(b) Flip number across - log, C
(c) Flip number across p
Fig. 1: Empirical evaluations on the CAIDA dataset, comparing flip number of the p-th frequency moment and the residual, for & = a 0.001 and p = 1.5 when not variable. Smaller flip numbers indicate less space needed by the algorithm.

---

Results and discussion. Our empirical evaluations serve simple proof-of-conee demonstrating that adversarially robust algorithm can use significantly less space than existing algorithms. In particular, existing algorithms use space that is an increasing function of the flip number of the p-th frequency moment, while our algorithms use space that is an increasing function of the flip number of the residual, which is significantly less across all settings in Figure 1. While the ratio does increase as the exponent p increases in Figure Ic, there is not a substantial increase, i.c., 1.24 to 1.31 from p 1.1 to p- 1.9. On the other hand, for a = 4 to 1.6 for a = 4-10, Similarly, in Figure la, the ratio of these quantities begins at 1.17 for 10 and increases to large as 1.75 for 10 5 Therefore, even in the case where the input is not adaptive, our empirical evaluations demonstrate that these flip number quantities can be quite different, and consequently, our algorithm can use significantly less space than previous existing algorithms.
decreases in Figure 1b, the ratio increases from 1.002
Acknowledgements
David P. Woodruff was supported in part by a Simons Investigator Award and NSF CCF-2335412. Samson Zhou is supported in part by NSF CCF-2335411. The work was conducted in part while David P. Woodruff and Samson Zhou were visiting the Simons Institute for the Theory of Computing as part of the Sublinear Algorithms program.
References
[ABD+21) Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. In STOC; 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 447-455, 2021.
[ABIW09] Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. Efficient sketches for earth-mover distance, with applications. In 50th Annual IEEE Symposium Foundations of Computer Science, FOCS, pages 324-330, 2009.
[ACGS23] Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Coloring in graph streams via deterministic and adversarially robust algorithms. In Proceedings of the 42nd ACM SIGMOD SIGMOD-SIGACTE -SIAAI-GAAIGGGIA Symposium on Principles of Database Systems, PODS, pages 141-153, 2023.
[ACSS23] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adver- sarial streaming via differential privacy and difference estimators. 14th Innovations in Theoretical Computer Science Conference, ITCS, pages 8:1:8:19, 2023.
[AIK08] Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high- dimensional spaces. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 343-352, 2008
[AMS99] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999.
[AMYZ19] Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou. Adver- sarially robust submodular maximization under knapsack constraints. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 148-156 2019.
[7] Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang. Streaming symmetric norms via measure concentration. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, STOC, pages 716 026,729,270 2017.
[BDM+20] Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upad- hyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 6/ IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 517-528, 2020.
10

---

[BEO22] Omri Ben- Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. 5th Symposium on Simplicity in Algorithms. SOSA, 2022. (to
appear).
[BHM*21] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Advances in Newral Information Processing Systems 34: Anmual Conference Neural Information Processing, NeurIPS, pages 3544-3551 -357,, 2021.
[BIRW16] Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, and David P. Woodruff. Nearly- optimal bounds for sparse recovery in generic norms, with applications to k-median sketching. Proceedings of the Eventy-Seventh Annual ACM-SIAN Symposium on Discrete Algorithms, SODA, pages 31 318-337, 2016.
[BJWY22] Omri Ben-Eliezer Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. J. ACM, 69(2):1::1117333 2022.
[BKM 22] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic con- structions and lower bounds. In STOC '2: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1671-1684, 2022.
[BMSC17] Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. Robust submodular maximization: non-uniform partitioning approach. In Proceedings of the 34th International Conference Machine Learning, ICML, pages 508-516, 2017.
[BMWZ23] Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, and Samson Zhou. Private data stream analysis for universal symmetric norm estimation. In Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 14:24,, 2023.
[BNS+21] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput., 50(3), 2021.
[BWZ21] Vladimir Braverman, Viska Wei, and Samson Zhou. Symmetric norm estimation and regression on sliding windows. In Computing and Combinatorics- 27th International Conference, COCOON, Proceedings, pages 528-539, 2021.
[BY20] Omri Ben-Eliezer and Eylon Yogev. The adversarial robustness of sampling. In Proceedings of the 39th ACM Database Systems, PODS, pages 49- 62, 2020.
Symposium on Principles of
[CA116] CAIDA. The caida uesd anonymized internet traces. https://www.cadda org/ catalog/ http:/daaattt/sssseeeee pass/vessseeeeee _ataaee___teeeeeaaaaaaaeeaeeeeee 2016.
[CCF04] Moses Charikar, Kevin C. Chen, and Martin Parach-Colton. Finding frequent items in data streams. Theor Comput. Sci., 312(1):3-15, 2004.
[CCJ+23] Xi Chen, Vincent Cohen- Rajesh Jayaram, Amit Levi, and Erik Waingarten. Streaming euclidean MST to constant factor. In Proceedings of the 55th Annual ACM Symposiun on Theory of Computing. STOC, pages 156-169, 2023.
[CGS22] Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. In 13th Innovations in Theoretical Computer Science Conference, ITCS, pages 37:1-37:23, 2022.
(CJLW22) Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional EMD and MST. STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 222-233, 2022.
11

---

[CLN' 22] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In International Conference on Machine Learning, ICMI., pages 41 4112-4140, 2022.
[CN20] Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS, 2020.
[CSW+23] Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou. Robust algorithms on adaptive inputs from bounded adver- saries. In The Eleventh International Conference on Learning Representations, ICLR, 2023.
[CW09] Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41 Annual ACM Symposium on Theory of Computing, STOC, pages 205-214, 2009.
[CWZ23] Vincent Cohen-Addad, David Woodruff, and Samson Zhou. Streaming euclidean k-median and k-means with o(log n) space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 883-908 2023.
[DF+ 15] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 117-126. ACM, 2015.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC, Proceedings, pages 265-284, 2006.
[DRV10] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 51-60, 2010.
[DSWZ23] Itai Dinur, Uri Stemmer, David P. Woodruff, and Samson Zhou. On differential privacy and adaptive data analysis with bounded space. In Advances in Cryptology EURO- CRYPT 2023 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part III, pages 35-65, 2023.
[FKSV02] Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. An ap- proximate 11 -ifffeeree algorithm for massive data streams. SIAM J. Comput., 32(1):131- 151, 2002.
[FMWW10] Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. Core- sets and sketches for high dimensional subspace approximation problems. In Proceed- ings of the Twenty-Fii Firntt-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 630-649, 2010.
[GHS+ + 12] Anna C. Gilbert, Brett Hemenway, Martin Strauss, David P. Woodruff, and Mary Wootters. Reusable low-error compressive sampling schemes through privacy. In IEEE Statistical Signal Processing Workshop, SSP, pages 536-539, 2012.
[G]W+24] Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. A strong separation for adversarially robust 4 estimation for linear sketches. CoRR, abs/2409.16153, 2024.
[GM07) Sumit Ganguly and Anirban Majumder. Cr-precis: A deterministic summary structure for update data streams. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, First International Symposium, ESCAPE, pages 48-59,
[GSTV07] Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, and Roman Vershynin. One sketch for all: fast algorithms for compressed sensing. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 237-246, 2007.
12

---

[HKM* 20] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NewrIPS, 2020.
[HNO08] Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 489-498, 2008
[HW13] Moritz Hardt and David Woodruff. How robust are linear sketches to adaptive inputs? In Symposium on Theory of Computing Conference, STOC, pages 121-130, 2013.
[Ind04] Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing. pages 373-380, 2004.
[IWOS] Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 202-208, 2005.
[JW09] T. S. Jayram and David P. Woodruff. The data stream space complexity of cascaded norms. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 765-774, 2009.
[JW7244] Rajesh Jayaram, David Woodruff, and Samson Zhou. Streaming algorithms with few state changes. In Proceedings of the 43rd ACM SIGMOD--SGGACT-SIGA Symposium on Principles of Database Systems, PODS, 2024.
[KMGG07) Andreas Krause, H. Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Select- ing observations against adversarial objectives. In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, pages 777-784, 2007.
[KMNS21] Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Advances in Cryptology- CRYPTO 41 Annual International Cryptology Conference, CRYPTO Proceedings, Part III, pages 94-121, 2021.
[KNW10] Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings of the Twenty-Ninth ACM SIGMOD- SIGACT-SIGART Symposium Principles of Database Systems, PODS, pages 41-52, 2010.
[KSZC03]
Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen. Sketch-based change detection: methods, evaluation, and applications. In Proceedings of the 3rd ACM SIGCOMM Internet Measurement Conference, IMC, pages 234 1442247,444 2003.
[KZK88] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable debbuitn-robust robust submodular maximization! Data summarization with privacy and faimess constraints, In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018.
[LSW18] Roie Levin, Anish Prasad Sevekari, and David P. Woodruff. Robust subspace approxi- mation in a stream. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, 2018
[MBN+17 17] Slobodan Mitrovic, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevher. Streaming robust submodular maximization: A partitioned threshold- ing approach. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pages 4557-4566, 2017.
[MNS1]] Ilya Mironov, Moni Naor, and Gil Segev. Sketching in adversarial environments. SIAM J. Comput., 1846)1184 2011.
13

---

[MRWZ20] Sepideh Mahabadi, Ilya P. Razenshteyn. David P. Woodruff, and Samson Zhou. Non- adaptive adaptive sampling on turnstile streams. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1251-1264, 2020.
[MWZ22] Sepideh Mahabadi, David P. Woodruff, and Samson Zhou. Adaptive sketches for robust regression with importance sampling. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM) pages 31:1-31:21, 2022.
[NY19] Moni Naor and Eylon Yogev. Bloom filters in adversarial environments. ACM Trans. Algorithms, 15(3)355:1-35:300 2019.
[OSU18] James B. Orlin, Andreas S. Schulz, and Rajan Udwani. Robust monotone submodular function maximization. Math. Program., 172(1-2):505-533 537,00555577755 2018.
[TZ04] Mikkel Thorup and Yin Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 615-624, 2004.
[VVWZ23] Ameya Velingker, Maximilian Vötsch, David P. Woodruff, and Samson Zhou. Fast (I+c)- approximation algorithms for binary matrix factorization. In International Conference on Machine Learning ICML, pages 34952-34977 2023.
[WY23] David P. Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 4622-4666, 2023.
[WZ12] David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 941-960, 2012.
[WZ21a] David P. Woodruff and Samson Zhou. Separations for estimating large frequency moments data streams. In 48th International Colloquiun Automata, Languages, and Programming, ICALP, pages 1 11:11-112:21, 2021.
[W721b] David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1183-1196, 2021.
A Preliminaries
For positive integer O, we use [n]] denote the set of integers {1, (1...., n). We use poly(n) to denote a fixed polynomial in n whose degree can be set by adjust constants in the algorithm based on various desiderata, e-g., in the failure probability. We use polylog(n) to denote poly(log) n). When there exist constants to facilitate an event to occur with probability
poly(z)' we say that the event occurs with high probability. For a random variable X, we use E X to denote its expectation and Var(X) to denote its variance.
Recall that for > O, the L, norm of a vector E Rd is ||I|| = (vf + +... +g. The p-th moment of is defined as (v) = ||u.p. Note that for a constant p 2 1, a (1 + appproxxmmtio to the F2 (v) implies a (1 + ---aappoxxiiiioonnn to ||e||p- Similarly, for a sufficiently small constant & E (0, 1), (1 + O (app-approxiaaaio to || implies a (1 + (s))² = (1 + apaapproxinatoon to (.) We thus use the problems of I.p norm estimation and F, moment estimation interchangeably in discussion.
We use Fp. (p) (f) to denote the p-th moment of vector g obtained by setting to zero the coordinates of f largest in magnitude, breaking ties arbitrarily. We also define |le||o to be the number of nonzero coordinates of v, so that ||o||o = Hi E [m]] wa # O)|-
We recall the following notions regarding differential privacy.
14

---

Definition A.1 (Differential privacy). [DMNS06] Given E > 0 and E (0, 1). a randomized algorithm A D - R with domain and range R is (eiff-ififrrentialll private if. for every neighboring datasets S and S' and for all & _ R
[r(A(S) E 8) & e Pr[A(S)) E +
Theorem A.2 (Private median, e-g., [HKM*20]). Given a database DD X*, there exists an (e, 0)- differentially private algorithm PRIV MED that outputs an element x E X such that with probability at least 1 - 5, there at least |S k elements in S that are at least 2, and at least [s k elements in S in S that at most x, for k = O ( log IX
Theorem A.3 (Advanced composition, e-g., [DRV1O]) Let E, 8 E (0,1) and let 8 [0. Any mechanism that permits & adaptive interactions with mechanisms that preserve (s, (e.d)-differential
privacy guarantees (E', + d'iddffferlttia privacy, where e' = =22k In
1 8 -E 2ke
Theorem A.4 (Generalization of DP, e.g. [DFH 15, BNS+2IJ. Let 1/31, 8 E (0,e/4), and n log 25. Suppose A X 2 is an (e. 8) -i-iifferentiall private algorithm that curates
database of size and produces a function h X + {0, 1}. Suppose D is distribution over X and a set of n elements drawn independently and identically distributed from D. Then
Pr S~D.htA(S)
Σ
h(x)
E IND
[bxx)]
2 10e
S
Algorithm 4 Adversarially Robust Framework
Input: Oblivious algorithms A with failure probability do, number of queries Q, failure probability 8
Output: Algorithm robust to Q queries, with failure probability at most 5
1: + O (VQ log
Q
68g
2: Implement
O (r) independent instances , As of A the input
3: for each query q:s [Q] do
4: Let Zi.j be the output of A, on q
5: Let PRIVMED be (
6: Return PRIVMED [Z..j bE(4))
We remark that Algorithm 4 is the algorithm corresponding to the statement of Theorem 2.3
B
Missing Proofs from Section 2
One reason that DETHH is not commonly utilized that with the additional power of randomness, significantly better space bounds be achieved, such by the following guarantees:
Theorem B.1. [CCF04] For E [1. there exists a randomized algorithm COUNTSKETCII that solves the E-Lo heavy-hilters on universe of size n and a stream of length m and uses O ( log n log nm bits of space.
To achieve the guarantees of Theorem 2.2, natural approach would be to apply Theorem 2.3 the guarantees of COUNTSKETCH in Theorem B.I. However, this does not achieve the optimal bounds because each round of adaptive queries can require multiple answers, i.c., estimated frequencies for each the heavy-hitters at that time. Thus, [CLN+22] proposed a slight variation of the algorithm along with intricate analysis to achieve the guarantees of Theorem 2.2.
Lemma 2.5. Suppose the number of distinct elements at the beginning of a block is at least 50t. Let be the output of ROBUSTCS at the beginning of a block. Then conditioned on the correctness of ROBUSTCS, S solves the he,-h hitter problem on the entire block.
Proof. Suppose the number of distinct elements at the beginning of a block least 50l. Let be the frequency vector at the beginning of the block and let g be the frequency vector at any
15

---

intermediate step in the block. Conditioned on the correctness of ROBUSTCS, we have that the estimated frequency f. of each item i satisfies
1/P
-
100
Thus if fi is an Lpp heavy hitter, then i and conversely if E S, then fi 2 fllfflp-
Since each block has length = 100 f1/2, then |g; - - S c /1/ Moreover, because the number
100
of distinct elements is at least 506, then we have || 2 50 Therefore if ga is an s-Lp heavy
hitter, then Js is 5-Lpp heavy hitter, so that E S. Similarly if gi 51lgllp- then < fll/lpp so that & S.
Lemma 2.6. With high probability, ROBUSTCS is correct at the beginning of each block of length É.
t// Note that there are b f 100m blocks of length l. Thus it suffices to require ROBUSTCS to be robust to b queries in the subroutine ADAPTIVEHH to achieve correctness at the beginning of each block, with high probability.
Proof. We have =
Lemma 2.7. The total space by the algorithm is Ô 2.0 m (0n(2222//0 2)((4-3))) bits of space.
Proof. Since DETHH is called with threshold & for / = O (mP/((p-3)), then the total space by 16 DETHH is Ō (1. (22/)) O (202)22)((4 bits.
We require ROBUSTCS to be robust to b queries in the subroutine ADAPTIVEHH, thus using space Ô Vb log log
amd) 7 for 5 poly(n.m) and
m Vb = δ (V
ctl/D = =0 (2002)/(10-3)
Similarly, we use δ (vb) = Ô (E (E-1/2m m/2m 23/ (4p-3)) instances of LZEROEST to guarantee ro-
bustness against queries. Each instance of LZEERËSST uses O (1 log"(mm)) bits of space. Hence, the overall space is Ô (52o (2 (mm2222)///)) 2)/((p-3))) bits.
C Missing Proofs from Section
We revisit the guarantee of COUNTSKETCH with a different parameterization in this section. Theorem C.I. [CCF04] Given
[1,2]. there exists one-pass streaming algorithmm COUNTSKETCH that with high probability, reports all j [n] for which (f,) 2 Ep, along with estimations Ty. such that (1 - 5) s (f)) S (1 6)+5)
Observe that to provide the guarantees of Theorem C.I, COUNTSKETCH would require space poly (L. n), rather than quadratic dependency -.
10 we have that simultaneously Lemma 3.2. Let E [R] be fixed. Then with probability at least 9
)² for all j ((T)) for which (fz) 2 2 log (nm) H!! outputs F3 with (1- Zogg(nm)
(fi) S
(J)) < (1 1 (mm))))) ) (fz)².
Proof. The proof follows from Theorem C.I and the fact that COUNTSKETCH is only run on the substream induced by (!
Proof. Consider
casework
[og(( 11) f -log 72 log(nm)
1
1
log(1 + +1)) log 3 log((m))
Informally, the casework corresponds to whether the frequencies (f)) in a significant level set are large or not large, i.e., whether they are above
1
16

---

heavy-hitter threshold before subsampling the universe. Thus if the frequencies are large, then the heavy-hitter algorithm will estimate their frequencies, but if the frequencies are not large, then we must perform subsampling before the items surpass the heavy-hitter threshold.
Suppose
log(1 + 1)) - log llg((m))
S 1, so that (1- 2
7 "lom) Note that j Ag
implies (f₂)² E ((+T)<- (I+m) and thus (fi) 2
CM
17 CMCM 7 7lg'((mm
Note that M 2 Po and thus by
Lemma 3.2, we have that with probability at least I0. H!! outputs Fy such that
(1 log(mm)) ) (f,) & (f)) $ (+
8 $log(nm)) (fz),
as desired.
suppose Log( 1 + 11) -log 22 log(nm)
For the other case,
1. so that =
log(1 + n) - log 2 (mm)
Since pt = =2 =2 then we have that
Pi 27 log (nm)
(1 + 7)
Since j E A,, we have again (f,)² E [
(147)--1 (1+1)e)
CM CM
and therefore,
Fp
178
Fp
(1))² 2 4 (1 + 11)e
47 log (nm)
2
Conditioning on the event Eg, we have F
S
32f 2
and thus
f 4y log (nm)
2Fp
n
E2(U,"))
2
1287 log" (nm)
Hence by Lemma 3.2, we have that with probability at least 9 !1 outputs fq such that
(1 sog(mm))
(ft) s (F)) (1+
11+
8 8log(rm)) )
7
(f)),
as desired.
We now give the correctness guarantees of Algorithm 2. Lemma C.2. Pr (2) - Fp. S e Fp.
2 3/
Proof. We would like to show that for each level set f, accurately estimate its residual contribution
De. More specifically, we would like to show |D: Del S 8 Blog(nm) Fp for all & E [Z]. Let g be the residual vector of f with the largest coordinates in magnitude set to zero. For a level set f, we define the fractional contribution de == Eiem (f.) (F)) Given an accuracy parameter & and a stream of length
sin m, we define a level set At to be significant if Φe 2 100p Jogtty) Furthermore, we define a level set Ag to be contributing if di 2
5n 100plog(nm]]
Otherwise, the level set is defined to be di 1ogp [mm]
s²n
For fixed E, we have that De = ExEA, where j E A if (g)) E
CM [(++))
CM On (I+1)²
the other hand, for each fixed r, we have that S(()) is determined using items whose estimated CM (M frequency in the range (G))² E (147)--1 (1+v)e)) so it is possible that j could be classified into contributing to A, even if j & Ay. Hence, we first analyze an "idealized" setting, where each index is correctly classified across all level sets E E [L]. We that we achieve (1 + Ô (E) )approximmation to F, in the idealized setting and then argue that because we choose Ç uniformly at random, then only approximation guarantee will worsen only slightly but still remain a (1 + -pappproxinntoonn to Fp. since only a small number of coordinates will be misclassified and so our approximation guarantee will only slightly degrade.
17

---

Idealized setting. For fixed r [R]. let & be the event that |0,-7 S
32n and let &g be the event
2
that ( v 32F Note that M 2 Fp and thus conditioned on &1, &2, then by Lemma 3.2, we have that with probability at least
a Iū
H
((()) outputs I2 such that
(f)) (F)) [1 8 llg(rm))
(fz)², (mm)
log(nm)
as desired.
We first show that when (fz) is correctly classified for all j into level sets & [T]. then with probability poly(am}) we have that simultaneously for each fixed level set E, Dr DDl s [mm] Fp-
We define De Te (1 + n)) where Tp is the estimated size of Ac, formed by attempting to truncate the top k coordinates across the level sets Пg. In particular, we define [Te] modian,e(R) |
for max (1, log(1 r1) log 22 log(am)
7¹
We analyze the expectation and variance of [Tel. Firstly, let r E [R] be fixed and for each E Te, let
Y, be the indicator variable for whether Y, S We have
E
1 pi
1 Pi
Σ jer,
1
(p:
-re) = [Tel.
Similarly, we have
1
Var
Ie
Σ
B|y]]
p
p
jET,
[dl
(p.
Tel)
p
Because p: 2 min (1,
7 log (mm)
(mm))
then we have that by Chebyshev's 's inequality,
(1+m)in
1 s
|Tal 2 [Tdl v m) <
1
Pr
10'
conditioned on the events E,, Eg, and Es.
To analyze the probability of the events El and &s, recall that in 0 each item is sampled with probability 2-++1 Hence,
| S 2i-1'
E [[ <
F, 2
We define & to be the event that (1
32n <
By Markov's inequality, we have Pr [E]] 2 15
2n
Te
Similarly, we define Eg to be the event that F2 (r I 2 By Markov's inequality, we also have
Pr E21 Z 16"
We have that Pr Eg ε A 2 10.
9
Thus by union bound,
Pr
L pj
- rel
Fdl V(L n) S
1
By Chernoff bounds, we thus have
Pr Te [rel 2 [el. v ()+m)
m) s poly log(nm)
Moreover, if level é is significant, then either p; or |r/l >
(1+r)* 27
If 0, then ['']]
[Te]. Otherwise if [[e]= 2 (1+n)* then with probability at least poly
Tog((um) we have that
simultaneously for all significant levels & [7.), (1 - T2) s [2 S (1 + Tel in other words,
[ [Te| S T/l
18

---

Since subtract off the top l coordinates in De to form Ael then we also have [Ad] Ae S n/Tel- then for Dj | (1 + v1) we have
It follows that since E Ag for (gz)² E [I+n)/=T,
CM
CM (I+n]²
that DDe Dil S 7 + Cr. Taking the sum over all the significant levels, we see that the error is at most EeE(L] 2n V 2 Fp. "p.Ree((1-<)k))
Note that the same guarantee holds if level is insignificant, provided that [Tyl
(1-1)' 1000y
On the other
hand, if level is insignificant and [T'el T000
[I+n)
Thus with probability at least 1 poly log((mm
we have that simultaneously for all insignificant levels & E [Z],
Tel S 2007
Then we set Dj - O, so that [D; insignificant level sets can only be at most an vj fraction of the items in the contributing level sets beneath them. Since the sum of the contributions of contributing level sets is at most Fp Res((1-c) then taking the sum over all the sigmificant levels, we see that the error most the contribution of the tail of the insignificant levels, which by definition is at most 5 F [e.ee((1-eMM))
DDl D,. In fact, we observe that the number of items in
Randomized boundaries.
By Lemma 3.2, we have that conditioned on Eg,
(1- 7 ) (f))
GB (1 (1+ 8 llg((mm) ) (f))
log(nm)
independently of the choice of Ç. Because we drawn Ç E [1,2] uniformly at random, then the probability that j [n] is misclassified is most Hlo[[mm]
If j [n] is indeed misclassified, then it can only be classified into either level set Te+1 or level set Tz-1, since (f," p) is (1+ slog(ams) -approximation to (fz)². As result, misclassified index induces at most n(f))" additive error to the contribution of level set H3 and hence at most mff))² additive error to the contribution of level set A₃ the residual vector. Therefore, the total additive error across all E [r] due to misclassification is at most 17 Fp in expectation. By Markov's s inequality, the total additive error due to miselassification is at most 5 ((p,)e(((-=)))) with probability at least 0.95.
Theorem 3.4. There exists a one-pass streaming algorithm RESIDUAL.EST that takes input parameter k 2 (possibly upon post- post-processing the stream) and uses Ô (d. llog (og)) bits of space to output an estimate (epRes(k)) with Pr (Fp.Reeck)) (pp. S (1__))((1-=)kk) 2
Proof. Consider Algorithm 1. By Lemma C.2, have that
2
Pr F (e.Re)()) F Fo.kos(k) S Fp.Rea((1-e)))
thus remains to analyze the space complexity.
Note that Algorithm implements P - R instances of COUNTSKETCH with accuracy 17², for P = Ô (log(nm)), R = δ [lgg logn) and n = 1 By Theorem C.I, each instance of
COUNTSKETCH with threshold x7 uses O (+ log (mm)) bits of space. Therefore, the total space usage of Algorithm 1 is Ô (db log"(nm)) bits.
D Missing Proofs from Section
We first show that the p-th moment of f can be essentially split by looking at the p-th moment of the vector consisting of the largest k coordinates and the remaining tail vector.
19

---

Lemma D.1. Let E (0. 1) be a fixed accuracy parameter and let > 0 be fixed. Let f E R² be any fixed vector and let any fixed parameter. Let g be the vector consisting of the l coordinates of f largest in magnitude and let h be the residual vector, so that f = g + Suppose G and H satisfy
E |
7 || < < 11 + 1 1
||
- 11 < f < || + |1
Then
11=
(1+ ; 1s
Proof. The claim follows immediately from the fact that |l = |l + |1ll since f f= +-+ but g and h have disjoint support.
In fact, we show the estimation is relatively accurate even if the tail vector does not quite truncate the entries largest in magnitude.
Lemma D.2. Let f be a frequency vector, g be the residual vector omitting the coordinates of largest in magnitude, and h be the residual vector omitting the ((1 - (4) l coordinates of f largest in magnitude. Then we have ||ll| || S -l
Proof. Note that the smallest coordinates of the top & coordinates is only nonzero when Thus they can only contribute I fraction to the entire moment. It follows that II991 - -1 < f as desired.
Lemma 4.2. Let f be a frequency vector and be the residual vector omitting the k coordinates of f largest in magnitude. Let be any arbitvary vector such that ||0|]| ||ul|a S 1lll]] Let u be the residual vector omitting the coordinates of f + largest in magnitude. Then we have || - ||ul|p| < lllll..
100 ||lll,> k'-1/p and
Proof. Let |gl = M. Since ||ll S اIlاl1, then by an averaging argument |ny| can be at most (M)3//
(SM) 1/P before: is in the top k coordinates of f + u. Similarly, if E [n]] is in the top k coordinates of f for |us] less than ( (*M) 1/p ) and is no longer in the top k coordinates of f + v, then we must have |u,1 < (16.) 1/p Otherwise by averaging argument, |u,] would be too large and would be in the top le coordinates of f + v.
Thus the contribution to ||||| 1- - ||u||/] is at most the contribution in the case where the number of coordinates with |o:| 8M 1/p is maximized. Because ||0||/ S TÕo . A1-1/p, then there can k
1/p By the above argument, for each i, be most 108 coordinates E [n] such that |cy| 2 [
we have ||9,| u, P1 < 16M Since there can be at most s k such coordinates, then the total
k
100
change in the p-th moment of residual is at most 16. 100 I á ... The desired result then follows from the recollection that [|g|]]] M.
We now show the correctness of Algorithm 3.
Lemma D.3. For any fixed time during stream, let J be the induced frequency vector and let F. be the output of Algorithm Then we have that with high probability,
(1 (1-5)1513 < s (1++)1111
Proof. Consider the first time t in block of l updates and let of be the frequency vector induced by the stream up to that point. We first observe that ROBUSTHH with threshold ev will return any coordinates i E [n] such that fi 2 sPnj² [| up to (1 + s)-aprroximation For the remaining coordinates in the k-sparse vector returned by ROBUSTHH, any of them can contribute at most e" II Therefore, we have by Lemma D. that conditioned the correctness of ROBUSTHH
20

---

and RESIDUALEST, we have G H is a (1 + O ( (aproxxpxonnnnooonn to Il For the purposes of notation, let h denote the residual vector of f time t. omitting the l coordinates of largest in magnitude.
Now, consider some later time E' in the same block of & updates and let be the frequency vector induced by the updates in the block, i... the updates from to t'. Let be the residual vector omitting the & coordinates of f + v largest in magnitude. Since ||ulla S for = (e m m²/pk" 1///:///11/ 1/). then by Lemma 4.2, have that || ||u]]] I 5 ||Allp-- Thus provided that H is (1 O (e))- approximation to || IEg, then remains (1 + -ppproxxmmaao to ||ulI Hence conditioned on the correctness again of ROBUSTHH time L', we have that A M remains (1 + apprroxxiitaio to [ at time L.
As correctness of ROBUSTHH follows from Theorem 1.2, it remains to show correctness of RESIDUALEST on an adaptive stream. Because each block has size L, then the stream has at most 7 such blocks. Hence by the adversarial robustness of differential privacy, i... Theorem 2.3, it suffices run O all times.
copies of RESIDUALEST to guarantee correctness with high probability
Finally, we analyze the space complexity of our algorithm. Lemma D.4. For log n (logmm,, Algorithm 3 uses Ô (2to m²) bits of space in total.
Proof. We observe that Algorithm 3 uses a few main subroutines. Firstly, rums SPARSERECOVER with sparsity O (m²), which requires m polylog(nm) bits of space, by Theorem 4.1. Next,
runs ROBUSTHH with threshold ey,, for r = 100m5 By Theorem 1.2, ROBUSTHH uses
g2
δ 1 m( 2))pp))))))))) bits of space. Note that for our choice of = 2c (4p-4)
[em)a.s
3 (20p-15)
we have Ô (emjatm (2p (1-2))
( mm) bits of space. Finally, it runs m
copies of LZEROEST and RESIDUALEST. By Theorem 3.4, each instance of RESIDUALEST uses ( log (nm)) bits of space. By Theorem 2.4, each instance of LZZEROEST uses O (log" (nm) log logm) m) bits of space. Since & = O (s m=/pg1-1/p) then we have Ô
Ô (m²) and thus the total space usage by these subroutines is Ô ( [ m²) bits The desired claim then follows by noting that across all procedures, the space usage O (-t m²), due our balaneing choices of f, 7, and c.
Lemma 4.3. For log O(log m), Algorithm 3 uses Ô (gtss m²) bits of space in total. Moreover, for any fixed time during a stream, let f be the induced frequency vector and let F be the output of Algorithm 3. Then we have that with high probability, (1 fill < F < (1 + f)lfflp.
Proof. Note that Lemma 4.3 follows from Lemma D.3 and Lemma D.4.
Putting things together, we get the full guarantees our main result:
Theorem 1.3. Let E [1,2] and c (12p3)()))+3) There exists streaming algorithm that uses O (m²) poly (:. log(m))) bits of space and outputs a (1 + apprrxximaaii to the Lp norm of the underlying vector at all times of an adversarial stream of length m.
Proof. Observe that the correctness stems from Lemma D.3, while the space complexity follows form Lemma D.4.
Broader Impact Statement
As adversarial robustness can have applications to many applications machine learning, a potential broader impact of our work is the advancement of the theoretical foundations of trustworthy machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
21

---

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

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, open access to the data and code are provided in the full version of paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / httppsscccppbccccccceecce geides/ Codeeubbm ssi aasonnooicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
(6) Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, all the testing parameters are described in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
(7) Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, the paper provides the significant statistics of our experiments, which are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
(8) Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, the computing resources are described in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: / /neuris...p..// oc cc/public/ hwtpubic/Ethhcioo wtwiiiihieeeeiimmmccc
didn't 't make it into the paper).
(9) Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: Yes, the paper conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
(10) Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, we address the potential broader impacts in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
(11) Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our dataset was acquired from a publicly available repository and we do not introduce new datasets in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
(12) Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All original assets used in this paper have been referenced appropriately.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
(13) New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Yes, the provided code is well-documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
(14) Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
(15) Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "1HlXoD5TTE", "reviewer": "Reviewer_KENe", "summary": "The work develops new algorithms in the adversarially robust streaming model. In this model, the algorithm observes updates to some vector arrive in the form of a data stream and maintain estimates to some property of the vector as it changes. At each time-step i, the algorithm receives the update of the vector at this time-step. Specifically, it receives an update of the form $(i, \\Delta_i)$ that means that the $i$-th coordinate of the vector changes by $\\Delta_i$. Also, at every time-step i the algorithm outputs an estimate of some property of this vector.\n\n The work focuses on the adversarially robust setting, where the updates in subsequent time-steps can potentially depend on the estimates that the algorithm gave in previous time-steps. This is an important property of the streaming algorithm, because when decisions are made based on the estimates given by a streaming algorithm this will likely influence the data received by this algorithm in the future. At the same time, notably, many previously studied streaming algorithms are not adversarially robust.\nAdditionally, the paper focuses on the turnstile setting, i.e. the updates $\\Delta_i$ to the vector can be both positive and negative.\n\nThe length of the data stream is denoted by $m$, and in the adversarially robust streaming setting the paper mainly studies the problems of $L_p$-heavy hitter estimation and the problem of estimating the $L_p$ norm of the vector.\n\nThe problem of adversarially robust  $L_p$-heavy-hitter estimation requires the streaming algorithm maintain a list of elements that contribute a lot to the $L_p$ norm of the vector. Formally, it requires the list to contain all elements $i$ for which $|x_i| \\geq \\epsilon ||x||_p$ and all elements $j$ in the list should satisfy $|x_j| \\geq \\epsilon/2 ||x||_p$.\n\nUp to constantants and logarithmic factors in m and $\\epsilon$, the $L_p$-heavy-hitter estimation algorithm requires $1/\\epsilon^2.5 * m^\\alpha$, where $\\alpha=(2p-2)/(4p-3)$. This improves on the previous algorithm from the literature that achieves $\\alpha=p/(2p+1)$. This constitutes an improvement for all $p$ in $[1,2)$, with the most pronounced improvement at $p=1$ where the space usage is improved from polynomial in $m$ to polylogarithmic.\n\nThe work also presents new algorithms for estimating the $L_p$-norm of the underlying vector (up to a multiplicative factor of $1+\\epsilon$). Up to polylogarithmic factors and constants, the amount of space used by the algorithm is of the form $m^c poly(1/\\epsilon)$. The exact dependence of $c$ on the value of $p$ is $c=(24p^2-23p+4)/((4p-3)(12p+3))$. As the paper notes, for $p=1.5$ we have $c=0.373$ whereas the best previous algorithm has $c=0.375$.\n\nThe work improves on the dense-sparse decomposition method of the previous work.", "questions": "In subsection 1.1 what is the relationship between vectors $f$ and $x$? In the rest of the paper $f$ is used to denote the frequency vector of the stream, whereas the vector $x$ does not appear to be invoked anywhere again. In any case, it would be helpful if the vectors $x$ and $f$ are clearly defined in the beginning of subsection 1.1.\n\nSubsection 1.1. would be easier to read if the paper used \\paragraph to separate the parts of the subsection that address different problems.", "limitations": "It would be helpful if the authors added a dedicated paragraph in the paper that indicated what are the main limitations of the work according to the authors.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The adversarially robust streaming framework is natural and well-motivated.\n\n- For the L_1-heavy-hitter problem the work gives qualitative improvement on the previous algorithms by improving the space use from polynomial in the stream length to polylogarithmic.", "weaknesses": "- Other than the $L_1$-heavy hitter estimation, many of the improvements are extremely incremental, for instance the aforementioned improvement of the dependence on the length $m$ of the stream for $L_{1.5}$-norm estimation to $m^{0.373}$ from $m^{0.375}$.\n\n- Other than the results for L_1-heavy-hitter estimation, my understanding is that there is no evidence of optimality for the results given in this work. For example, to the best of my understanding, it can conceivably be the case that the above-mentioned dependence of  $m^{0.373}$  could in the future be improved to polylog$(m)$. If this happens, the impact of this work could potentially be small.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Other than the $L_1$-heavy hitter estimation, many of the improvements are extremely incremental, for instance the aforementioned improvement of the dependence on the length $m$ of the stream for $L_{1.5}$-norm estimation to $m^{0.373}$ from $m^{0.375}$.\n\n> Other than the results for L_1-heavy-hitter estimation, my understanding is that there is no evidence of optimality for the results given in this work. For example, to the best of my understanding, it can conceivably be the case that the above-mentioned dependence of $m^{0.373}$ could in the future be improved to polylog$(m)$. If this happens, the impact of this work could potentially be small.\n\nWe do agree that in some settings, the quantitative improvement is not large. However, we emphasize that optimal bounds for adversarial insertion-deletion streams is a major open question and therefore, the main strength of our work is the conceptual message that the despite the lack of recent progress, previous results are not optimal. Thus we hope our work will inspire future research in this direction.  \n\n> In subsection 1.1 what is the relationship between vectors $f$ and $x$? In the rest of the paper $f$ is used to denote the frequency vector of the stream, whereas the vector $x$ does not appear to be invoked anywhere again. In any case, it would be helpful if the vectors $x$ and $f$ are clearly defined in the beginning of subsection 1.1.\n\nDue to the problems of heavy-hitters and moment estimation, we use both $f$ and $x$ to denote the same underlying vector. We will unify this notation with the same symbol in the updated version. \n\n> Subsection 1.1. would be easier to read if the paper used \\paragraph to separate the parts of the subsection that address different problems.\n\nThanks for the suggestion, we will add paragraph notation to demarcate the discussion on heavy-hitters and norm estimation in the updated version.", "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": "04wrT2mVPs", "reviewer": "Reviewer_pbML", "summary": "This paper focuses on the L_p estimation (of the frequencies of items in a stream) in the adversarially robust streaming setting. The previous work by Ben-Eliezer, Eden and Onak achieved an $\\tilde{O}(m^{p/2p+1})$ space, which is slightly better than the $P(\\sqrt{m})$ space bound due to the flip number technique by considering a sparse-dense tradeoff. The authors of this work question whether the above bound is tight or if it can be improved.\n\nThe authors present an algorithm that beats the bound of $\\tilde{O}(m^{p/2p+1})$. This is obtained by first building an adversarially robust streaming algorithm for L_p heavy hitters, utilizing deterministic turnstile heavy-hitter algorithms with better tradeoffs. This is then combined with another algorithm that estimates the frequency of the tail-vector, and has additive error and space independent of the size of the tail.", "questions": "Do you see any potential barriers to this approach? A discussion on what the limits are (is the bottleneck the heavy hitters algorithm or the tail-estimation algorithm?) would be greatly appreciated. This will also give the reader the assurance that this minor improvement is still significant as it pushes a new idea to a reasonable extent.", "limitations": "Apart from the limitation described in the theorem statement, the authors could discuss limitations of this approach, and what the current barrier is.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As the paper mentions, this is a conceptual breakthrough, showing that the previous bound of $\\tilde{O}(m^{p/2p+1})$ is not tight. The paper explains all the ideas pretty well, and it was easy to read. \n\nThe novel insight here is that in the dense-sparse tradeoff of [BEO22], in order to change the p-th moment by at least a $1+\\epsilon$ factor, most of the updates are to a small number of coordinates, which then naturally must have either already been heavy-hitters, or became so after the update. The authors are able to effectively handle the had case of [BEO22], resulting in a better improvement.", "weaknesses": "The only obvious weakness is that the result is a very slight improvement, sometimes in the third decimal place. While the insight is nice, the techniques are a linear combination of different algorithms for different cases.  While I did not find the techniques very exciting, I think this passes the bar for NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The only obvious weakness is that the result is a very slight improvement, sometimes in the third decimal place. While the insight is nice, the techniques are a linear combination of different algorithms for different cases. While I did not find the techniques very exciting, I think this passes the bar for NeurIPS.\n\nWe do agree that in some settings, the quantitative improvement is not large. However, we emphasize that optimal bounds for adversarial insertion-deletion streams is a major open question and therefore, the main strength of our work is the conceptual message that the despite the lack of recent progress, previous results are not optimal. Thus we hope our work will inspire future research in this direction.  \n\n> Do you see any potential barriers to this approach? A discussion on what the limits are (is the bottleneck the heavy hitters algorithm or the tail-estimation algorithm?) would be greatly appreciated. This will also give the reader the assurance that this minor improvement is still significant as it pushes a new idea to a reasonable extent.\n\nThe relatively larger space used by the deterministic heavy-hitter algorithm compared to the space-optimal randomized heavy-hitter algorithms is a major bottleneck on further improving the bounds for this approach. One hope would be to improve the space usage of the deterministic heavy-hitter algorithm. However, it is known that the existing bounds are optimal, i.e., there are no deterministic heavy-hitter algorithms that use less space. Thus, the current analysis we use is tight for this approach and any further improvements likely require significantly new or different algorithmic designs.", "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": "Q1XitLfzXr", "reviewer": "Reviewer_VAPi", "summary": "In adversarially robust streaming, one wants to design streaming algorithms that work well even in the interactive setting, in which the stream is not fully fixed in advance, but is constructed element by element by an adversary who can see the current solution provided by the streaming algorithm. If the algorithm is randomized, each intermediate solution may reveal some information about the internal randomness of the car, which could allow the adversary make updates that break the estimates of the algorithm.\n\nThe paper concerns two fundamental problems in this setting: heavy hitters and moment estimation. In particular, the paper improves on the best known algorithm for moment estimation that considers two regimes, sparse and dense vectors. The paper shows that estimating $L_p$ moments for $p \\in [1,2)$ can be done in smaller space than previously known.\n\nThe achievement follows by leveraging known deterministic algorithms for heavy hitters and using them for tracking significant changes to the frequency vector.", "questions": "\"Unusual\" values of moments can be used for computing entropy (see Harvey, Nelson, Onak 2008). Do you think this could be used here to provide further motivation for your results? \n\nYour result heavily relies on Ganguly's heavy hitters result. I tried looking at this and related papers but I didn't have enough time to read them. Those are not the most frequently cited papers. Did you maybe verify their correctness?\n\nAre your results in the general turnstile model (where frequencies can get negative) or the strict turnstile modeli (where deletions are allowed, but all frequencies are always non-negative)? In particular, this goes back to the results of Ganguly. Which of the models are they for? Because if they are only for strict turnstile, then the case of $p=1$ is trivial.", "limitations": "No direct negative social impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* Insightful contribution to a very active research area.\n\n* Non-trivial improvement for some of the most popular streaming problems: heavy hitters and moments. The combination of different ideas to make this work is not easy.", "weaknesses": "The moments/norms for which the paper improves the space requirements are not the most important ones, which are I think are $p=0$ and $p=2$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The moments/norms for which the paper improves the space requirements are not the most important ones, which are I think are $p=0$ and $p=2$.\n\nIn general, a common goal is to find the heavy-hitters above a desired threshold that may be arbitrary. In this case, we want $|x_i|>\\tau$ for some threshold $\\tau$. We can then choose the values of $\\varepsilon$ and $p$ accordingly, so that $\\tau=\\varepsilon\\cdot\\|x\\|_p$ so that the $L_p$-heavy hitters correspond to the items whose frequency are above the threshold. \n\n> \"Unusual\" values of moments can be used for computing entropy (see Harvey, Nelson, Onak 2008). Do you think this could be used here to provide further motivation for your results?\n\nYes, entropy estimation is certainly an additional application for our results, particularly since the previous streaming algorithm utilizes $F_p$ moment estimation for $p\\in(1,2)$. Thanks for the pointer!\n\n> Your result heavily relies on Ganguly's heavy hitters result. I tried looking at this and related papers but I didn't have enough time to read them. Those are not the most frequently cited papers. Did you maybe verify their correctness?\n\n> Are your results in the general turnstile model (where frequencies can get negative) or the strict turnstile modeli (where deletions are allowed, but all frequencies are always non-negative)? In particular, this goes back to the results of Ganguly. Which of the models are they for? Because if they are only for strict turnstile, then the case of $p=1$ is trivial.\n\nGanguly and Majumder's heavy-hitters algorithm uses Chinese remainder codes in their Lemma 9 statement and can be stated for the general turnstile model. Importantly, their Lemma 11 does not give an $\\Omega(n)$ lower bound for the general turnstile model for the heavy-hitter problem because it only applies for heavy-hitters problem \"with parameter $s$\" with $s=\\Omega(n)$, where the additive error for each estimate is $\\frac{||x||_1}{s}$ and the universe has size $n$. \n\nFurthermore, their work is subsequently extended to general error correcting codes in [NNW12], which actually achieves a slightly better space bound in logarithmic dependencies. Specifically, [NNW12] constructs a deterministic matrix $A$ with Johnson-Lindenstrauss properties, so that maintaining $Ax$ for the underlying frequency vector $x$ is amenable even in the general turnstile model. \n\n[NNW12] Jelani Nelson, Huy L. Nguyên, David P. Woodruff: On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. APPROX-RANDOM 2012: 627-638", "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": "G0oqm333zr", "reviewer": "Reviewer_B1cC", "summary": "The authors present an algorithm for adversarially robust $L_p$-estimation estimation in the turnstile streaming model, which improves on the space-complexity of existing algorithms in the regime $p \\in (1, 2)$. They achieve this improvement via an alteration of the dense-sparse tradeoff technique of the existing state-of-the-art algorithm where they show it is sufficient to track the heavy-hitters while keeping track of an estimated residual. In addition to the improved Lp-estimation algorithm, the results include an adversarially-robust streaming algorithm for  the heavy-hitters problem along with an adversarially robust algorithm for estimating the residual of the frequency vector. The authors also include experiments providing support for their theoretical improvement guarantees.", "questions": "- What is the variable b that is referred to in Algorithm 3 (in the parameters for LZeroEst and ResidualEst)? Perhaps I am missing something but I don't see where it is defined.\n- I was a bit confused on the purpose of the empirical evaluations. It seems that you demonstrate that empirically in one real-world instance, the flip number of the residual vector can be significanly smaller than the flip number of the entire datastream. However, if I am understanding correctly, your algorithmic guarantees depend on the worst-case flip-number of the residual vector, and are not adaptive to the actual flip number. How should I interpret these empirical results with respect to the performance of your proposed algorithm?", "limitations": "I think the authors have adequately addressed limitations and the assumptions made in their results.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors do a great job of situating themselves in prior work, and explaining exactly how their results differ and improve. \n- While I am not well-versed in this area, the results seem correct and were clearly explained and decomposed.", "weaknesses": "- The actual improvement over the previous work seems very minimal, i.e. a tiny reduction in the space complexity on a very small portion of possible choices of p. However, the relation to heavy-hitters seems like an interesting and non-trivial insight used to achieve this improvement, and the algorithms for heavy hitters and residual estimation seem to me to be of independent interest. \n\n- The authors do a great job at explaining the intuition behind their techniques and how they fit with existing works. However, I found the actual preliminaries to be extremely confusing. The paper would greatly benefit from a clearer introduction on the exact setting and definitions of the various variables. I found the introduction of  https://arxiv.org/pdf/2003.14265 to be very helpful in clarifying my confusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The actual improvement over the previous work seems very minimal, i.e. a tiny reduction in the space complexity on a very small portion of possible choices of p. However, the relation to heavy-hitters seems like an interesting and non-trivial insight used to achieve this improvement, and the algorithms for heavy hitters and residual estimation seem to me to be of independent interest.\n\nIndeed, we do agree that in some settings, the quantitative improvement is not large. However, we emphasize that optimal bounds for adversarial insertion-deletion streams is a major open question and therefore, the main strength of our work is the conceptual message that the despite the lack of recent progress, previous results are not optimal. Thus we hope our work will inspire future research in this direction. \n\n> The authors do a great job at explaining the intuition behind their techniques and how they fit with existing works. However, I found the actual preliminaries to be extremely confusing. The paper would greatly benefit from a clearer introduction on the exact setting and definitions of the various variables. I found the introduction of https://arxiv.org/pdf/2003.14265 to be very helpful in clarifying my confusion.\n\nThanks for the suggestion. We will expand the preliminaries to reiterate the model described in Section 1 (lines 50-67) with the discussion specifically centered around the $L_p$ heavy-hitter problem and/or the $L_p$ norm estimation problem. \n\n> What is the variable b that is referred to in Algorithm 3 (in the parameters for LZeroEst and ResidualEst)? Perhaps I am missing something but I don't see where it is defined.\n\nSimilar to Algorithm 1, $b$ is the number of queries made to the oblivious algorithms. Since the stream has length $m$ and the stream is split into blocks of length $\\ell$, then there are at most $\\frac{m}{\\ell}$ queries made to each of the algorithms, as in Algorithm 1. We will explicitly clarify the setting of $b=\\frac{m}{\\ell}$ in Algorithm 3. \n\n> I was a bit confused on the purpose of the empirical evaluations. It seems that you demonstrate that empirically in one real-world instance, the flip number of the residual vector can be significanly smaller than the flip number of the entire datastream. However, if I am understanding correctly, your algorithmic guarantees depend on the worst-case flip-number of the residual vector, and are not adaptive to the actual flip number. How should I interpret these empirical results with respect to the performance of your proposed algorithm?\n\nYes, that's a fair point. However, we remark that the algorithmic guarantees of the previous results also depend on the worst-case flip-number of the entire vector, so in some sense we are still comparing apples to apples by comparing the empirical flip-number of the residual vector to the empirical flip-number of the entire vector. In particular, the algorithm must still commit to some budget for the flip-number before the algorithm is initialized and our empirical results show that the same budget can handle significantly more updates for our algorithm.", "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:
We thank the reviewers for their thoughtful comments and valuable insight. We also appreciate the positive feedback, such as:
- The adversarially robust streaming framework is natural and well-motivated. (Reviewer KENe)
- For the L_1-heavy-hitter problem the work gives qualitative improvement on the previous algorithms by improving the space use from polynomial in the stream length to polylogarithmic. (Reviewer KENe)
- As the paper mentions, this is a conceptual breakthrough, showing that the previous bound of $\tilde{O}(m^{p/2p+1})$ is not tight. (Reviewer pbML)
- The paper explains all the ideas pretty well, and it was easy to read. (Reviewer pbML)
- The authors are able to effectively handle the had case of [BEO22], resulting in a better improvement. (Reviewer pbML)
- Insightful contribution to a very active research area. (Reviewer VAPi)
- Non-trivial improvement for some of the most popular streaming problems: heavy hitters and moments. The combination of different ideas to make this work is not easy. (Reviewer VAPi)
- The authors do a great job of situating themselves in prior work, and explaining exactly how their results differ and improve. (Reviewer B1cC)
- The results seem correct and were clearly explained and decomposed. (Reviewer B1cC)

We provide specific responses to the initial comments of each reviewer below. We hope our answers addresses all points raised by the reviewers and we will be most happy to answer any remaining or additional questions during the discussion phase!

Meta-review: This paper studies the problem of $L_p$ heavy-hitters estimation in the robust streaming model. The results of the paper improve polynomially the memory requirements for this task, and the gains are more pronounced for $p=1$, where the memory bound becomes poly-logarithmic, as opposed to previous works where the corresponding bound is $O(m^{1/3})$. These results are based on novel innovations on previous works which introduced a dense-sparse tradeoff technique and techniques from differential-privacy. Reviewers were consistently positive about the merits of the work, while there were some concerns about the broader implications (or lack thereof) of these results, as well as the lack of matching lower bounds.
Decision: Accept (poster)