Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters

Authors: david p woodruff
samson  zhou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:57:51

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.

Main paper: 
 introduction: 
 Adversarial robustness for big data models is increasingly important not only for ensuring the reliability and security of 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 is the streaming model of computation, which has emerged as a 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 a number of sequential updates that are 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 m of the data stream and the dimension n of the dataset.The streaming model of computation. In the classical oblivious streaming model, the stream S of updates u 1 , . . . , u m defines a dataset that is fixed in advance, though the ordering of the sequence of updates may be adversarial. In other words, the dataset is oblivious to any algorithmic design choices, such as 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 a random sign vector s and outputs |⟨s, f ⟩| as the estimate for the L 2 norm of the underlying frequency vector f defined by the stream. To show correctness of the sketch, we require s 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, GHS + 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, it 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 [BY20, HKM + 20, ABD + 21, BHM + 21, KMNS21, WZ21b, BKM + 22, BEO22, BJWY22, CGS22, ACGS23, ACSS23, DSWZ23, GLW + 24], a sequence of adaptively chosen updates u 1 , . . . , u m 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 to correctly approximate or compute a fixed function at all times in the stream. Formally, the black-box adversarial streaming model can be modeled as a two-player game between a streaming algorithm A and a source E that creates a 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) E computes an update u t for the stream, which possibly depends on all previous outputs from A.(2) A uses u t to update its data structures D t , acquires a fresh batch R t of random bits, and outputs a response Z t to the query Q.(3) E observes and records the response Z t .The goal of E is to induce from A an incorrect response Z t to the query Q at some time t ∈ [m] throughout the stream using its control over the sequence u 1 , . . . , u m . By the nature of the game, only a single pass over the stream is permitted. In the context of our paper, each update u t has the form (i t , ∆ t ), where i t ∈ [n] and ∆ t ∈ {±1}. The updates implicitly define a frequency vector f ∈ R n , so that u t changes the value of the (i t )-th coordinate of f by ∆ t .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-only streams, where updates are only allowed to 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 L p estimation have been achieved in polylogarithmic space for p ≤ 2 by [WZ21b] in the insertion-only model, it is a well-known open question whether there exists a constant C = Ω(1) such that the same problems require space Ω(n C ), where n is the dimension of the underlying frequency vector. Indeed, [HW13] showed that the existence of a constant C = Ω(1) such that no linear sketch with sketching dimension o(n C ) can approximate the L 2 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 + ε), the flip number λ is the number of times the target function Q changes by a factor of (1 + O (ε)). It is known that for polynomially-bounded monotone functions Q on insertion-only streams, we generally have λ = O 1 ε log 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 √ λ [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 √ λ times the space required by the oblivious algorithm, which may not be desirable in large setting of λ = Ω(m) for turnstile streams. By considering dense-sparse tradeoffs, [BEO22] gave a general framework that improved upon the Õ √ λ = Õ ( √ m) space bounds due to the flip number. In particular, their results show that Õ m p/(2p+1) space suffices for the goal of L p norm estimation, where the objective is to estimate (f p 1 + . . . + f p n ) 1/p for an input vector f ∈ R n , which is an important problem that has a number of applications, such as network traffic monitoring [FKSV02, KSZC03, TZ04], clustering and other high-dimensional geometry problems [BIRW16, CJLW22, CCJ + 23, CWZ23], low-rank approximation and linear regression [CW09, FMSW10, BDM + 20, VVWZ23, WY23], earth-mover estimation [Ind04, AIK08, ABIW09], cascaded norm estimation [JW09, MRWZ20], and entropy estimation [HNO08] . Unfortunately, there has been no progress for L p estimation on turnstile streams since the work of [BEO22] , either in terms of achievability or impossibility. Thus we ask: Is there a fundamental barrier for adversarially robust L p estimation on turnstile streams beyond the dense-sparse tradeoffs?In this paper, we answer the above question in the negative. We show that the techniques of [BEO22] do not realize a fundamental limit for adversarially robust L p estimation on turnstile streams. In particular, we give an algorithm that uses space Õ (m c ), for some constant c < p 2p+1 for p ∈ (1, 2). We first require an adversarially robust algorithm for heavy-hitters.Heavy hitters. Recall that the ε-L p -heavy hitter problem is defined as follows.Definition 1.1 (ε-L p -heavy hitters). Given a vector f ∈ R n and a threshold parameter ε ∈ (0, 1), output a list L that includes all i such that f i ≥ ε • ∥f ∥ p and includes no j such thatf j < ε 2 • ∥f ∥ p .Generally, heavy-hitter algorithms actually solve the harder problem of outputting a estimated frequencyf i such that | f i -f i | ≤ C • ε • ∥f ∥ p , for each i ∈ [n],where C is some constant such as 1 6 . Observe that such a guarantee solves the ε-L p -heavy hitters problem because each i such that f i ≥ ε • ∥f ∥ p must have f i > 3ε 4 • ∥f ∥ p and similarly each j such that f j ≥ 3ε 4 must havef j ≥ ε 2 • ∥f ∥ p .We give an adversarially robust streaming algorithm for the L p -heavy hitters problem on turnstile streams.Theorem 1.2. Let p ∈ [1, 2]. There exists an algorithm that uses Õ 1 ε 2.5 m (2p-2)/(4p-3) bits of space and solves the ε-L p -heavy hitters problem at all times in an adversarial stream of length m.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 α = p 2p+1 , while our result uses space Õ m β for β = 2p-2 4p-3 . It can be shown that α -β = 2-p (4p-3)(2p+1) , which is at positive for all p ∈ [1, 2). Thus our result is 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 Õ m 1/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 a frequency vector up to some tail error. More precisely, given a frequency vector f that is defined implicitly through a data stream and a parameter k > 0, let g be a tail vector of f , which omits the k entries of f largest in magnitude, breaking ties arbitrarily. Similarly, let h be a tail vector of f that omits the (1 -ε)k entries of f largest in magnitude, where ε ∈ (0, 1) serves as an error parameter. Then we give a one-pass streaming algorithm that outputs an estimate for ∥g∥ p p up to additive ε • ∥h∥ p p , using space poly 1 ε , log n . In particular, our space is independent of the tail parameter k. We defer the full guarantees of our algorithm as well as a more formal discussion to Section 3. We then give our main result:Theorem 1.3. Let p ∈ [1, 2] and c = 24p 2 -23p+4 (4p-3)(12p+3). There exists a streaming algorithm that uses O (m c ) • poly 1 ε , log(nm) bits of space and outputs a (1 + ε)-approximation to the L p norm of the underlying vector at all times of an adversarial stream of length m.It can again be shown that our result in Theorem 1.3 again improves on the dense-sparse framework of [BEO22] across all p ∈ (1, 2). For example, for p = 1.5, the previous result uses space Õ m 3/8 = Õ m 0.375 , while our algorithm uses space Õ m 47/126 ≈ Õ m 0.373 . 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.Recall that the flip number λ to be the number of times the F p moment changes by a factor of (1 + O (ε)), given a target accuracy (1 + ε). Given a stream with flip number λ, the standard sketch-switching technique [BJWY22] for adversarial robustness is to implement λ independent instances of an oblivious streaming algorithm for F p estimation, iteratively using the output of each algorithm only when it differs from the output of the previous algorithm by a (1 + ε)-multiplicative factor. Subsequently, [HKM + 20, ACSS23] showed that by using differential privacy, it suffices to use roughlyλ independent instances of an oblivious streaming algorithm for F p estimation to achieve correctness at all times for an adaptive input stream. Unfortunately, the flip number for a stream of length m can be as large as Ω(m), 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 p estimation, that once the frequency vector has at least m C nonzero entries for any fixed constant C ∈ (0, 1), then since all entries must be integral and all updates only change each entry by 1, at least Ω ε (m C/p ) updates are necessary before the p-th moment of the resulting frequency vector can differ by at least (1 + ε)-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 1-C/p , for ε = Ω(1). Thus it suffices to run Õ m 1/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 C -sparse, there are sparse recovery techniques that can exactly recover all the nonzero coordinates using Õ m C space, even if the input is adaptive. Hence by balancing Õ m C = Õ m (1/2-C/2p at C = 1 3 , [BEO22] achieves Õ m p/(2p+1) overall space for F p estimation for adaptive turnstile streams.Our key observation is that for p ∈ (1, 2), if the frequency vector has at least m C nonzero entries, a sequence of O ε (m C/p ) 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 O ε (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 a 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.Heavy-hitters. First, we need a streaming algorithm for accurately reporting the frequencies of the L p -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 L p norm might be necessary to identify the L p heavy-hitters. Moreover, algorithms for finding L p heavy-hitters are often used to estimate the L p norm of the underlying frequency, e.g., [IW05, WZ12, BBC + 17, LSW18, BWZ21, WZ21a, MWZ22, BMWZ23, JWZ24]. Instead, we use a turnstile streaming algorithm DETHH for L p heavyhitters [GM07] that uses sub-optimal space Õ 1 ε 2 • n 2-2/p bits of space for p ∈ (1, 2], rather than the optimal COUNTSKETCH, which uses O 1 ε 2 • log 2 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] . In 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 L p -heavy hitter algorithm in Section 2, ultimately achieving Theorem 1.2.Residual estimation. It remains to estimate the contribution of the elements that are not L p heavyhitters, i.e., the residual vector, toward the overall p-th moment. More generally, given a tail parameter k > 0 and an error parameter ε ∈ (0, 1), let g be a tail vector of f that omits the k entries of f largest in magnitude, breaking ties arbitrarily and let h be a tail vector of f that omits the (1 -ε)k entries of f largest in magnitude. We define the level sets of the p-th moment so that level set Λ ℓ roughly consists of the coordinates of g with magnitude [(1 + ε) ℓ , (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 [IW05] .Namely, we note that any "significant" level set has either a small number of items with large magnitude, or 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 a large number of items in the level set that remain. Moreover, these items will now be heavy with respect to the p-th moment of the resulting frequency vector after subsampling with high probability. Thus, these items can be identified by COUNTSKETCH 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 k such items. We provide the full details of the residual estimation algorithm in Section 3, culminating in Theorem 3.4. 
adversarially robust l p -heavy hitters: 
 In this section, we give an adversarially robust algorithm for L p -heavy hitters on turnstile streams. We first recall the following deterministic algorithm for L p -heavy hitters on turnstile streams. Theorem 2.1. [GM07] For p ∈ [1, 2), there exists a deterministic algorithm DETHH that solves the ε-L p heavy-hitters on a universe of size t and a stream of length m and uses 1 ε 2 t 2-2/p polylog tm ε bits of space.We also recall the following variant of COUNTSKETCH for answering a number of rounds of adaptive queries, as well as a more general framework for answering adaptive queries. Theorem 2.2. [CLN + 22] For p ∈ [1, 2), there exists a randomized algorithm ROBUSTCS that uses Õ √ λ ε 2 log n log nmλ δ bits of space, and for λ different times t on an adaptive stream of length m on a universe of size n, reports for all i ∈ [n] an estimate f(t) i such that | f (t) i -f (t) i | ≤ ε 100 • ∥f (t) ∥ 2, where f (t) is the induced frequency vector at time t. Theorem 2.3. [HKM + 20, BKM + 22, ACSS23, CSW + 23] Given a streaming algorithm A that uses S space and answers a query with constant failure probability δ 0 < 1 2 , there exists a data structure that answers Q adaptive queries, with probability 1 -δ using space O S √ Q log 2 Q δ .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 on deterministic algorithms. On the other hand, the space usage of DETHH 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 we shall use DETHH. On the other hand, if the universe size is large, then shall use the following robust version of COUNTSKETCH, requiring roughly √ λ 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 are in, i.e., the large universe case or the small universe case, by using the following L 0 estimation algorithm: Theorem 2.4. [KNW10] There exists an insertion-deletion streaming algorithm LZEROEST that uses O 1 ε 2 log n log 1 δ log 1 ε + log log m bits of space, and with probability at least 1 -δ, outputs a (1 + ε)-approximation to L 0 .Input: Turnstile stream of length m for a frequency vector of length n Output: Adversarially robust heavy-hitters 1: t ← O m p/(4p-3) , ℓ ← ε 100 • t 1/p , b ← m ℓ ,We give our algorithm in full in Algorithm 1. Because DETHH is 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 ℓ updates.Lemma 2.5. Suppose the number of distinct elements at the beginning of a block is at least 50t. Let S be the output of ROBUSTCS at the beginning of a block. Then conditioned on the correctness of ROBUSTCS, S solves the L p -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 Õ 1 ε 2.5 m (2p-2)/(4p-3) bits of space.Given our proof of correctness in Lemma 2.5 and Lemma 2.6, as well as the space analysis in Lemma 2.7, then we obtain Theorem 1.2. 
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 k > 0 and an error parameter ε ∈ (0, 1), let g be a tail vector of f that omits the k entries of f largest in magnitude, breaking ties arbitrarily and let h be a tail vector of f that omits the (1 -ε)k entries of f largest in magnitude. We give an algorithm that estimates ∥g∥ p p up to additive ε • ∥h∥ p p , using space poly 1 ε , log n , which is independent of the tail parameter k. It should be noted that our algorithm is imprecise on ∥g∥ p p 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 are independent of k are sufficiently useful for our subsequent application of L 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 η > 0 be a parameter and let m be the length of the stream. Let M be the power of two such that m p ≤ M < (1 + η)m p and let ζ ∈ [1, 2]. Then for each integer ℓ ≥ 1, we define the level setΓ ℓ := i ∈ [n] | f i ∈ ζM (1+η) ℓ-1 , ζM (1+η) ℓ . We also define the contribution C ℓ of level set Γ ℓ to be C ℓ := i∈Γ ℓ (f i ) p .For a residual vector g of f with the top k coordinates set to be zero, we similarly define the level sets Λ ℓ and D ℓ of g in the natural way, i.e., D ℓ :=i∈Λ ℓ (g i ) p for Λ ℓ := i ∈ [n] | g i ∈ ζM (1+η) ℓ-1 , ζM (1+η) ℓ . Algorithm 2 RESIDUALEST: residual F p approximation algorithm, p ∈ [1, 2] Input: Stream s 1 , . . . , s m of items from [n], accuracy parameter ε ∈ (0, 1), p ∈ [1, 2] Output: (1 + ε)-approximation to F p 1: η ← ε 100 , L ← Õ log(nm) η , P = Õ (log(nm)), R ← Õ log log n η , γ ← 2 20 2: for t = 1 to t = m do 3: for (i, r) ∈ [P ] × [R] do 4: Let U (r) i be a (nested) subset of [n] subsampled at rate p i := min(1, 2 1-i ) 5: if s t ∈ U (r) i then 6: Send s t to COUNTSKETCH (r) i with accuracy η 3 7: Let M = 2 i for some integer i ≥ 0, such that m p ≤ M < 2m p 8: c ← k 9: for ℓ = 1 to ℓ = L do 10: i ← max 1, log(1 + η) ℓ -log γ 2 log(nm) η 3 11: Let H (r) i be the outputs of COUNTSKETCH at level i 12: Let S (r) i be the set of ordered pairs (j, f j ) of H (r) i with f j p ∈ ζM (1+η) ℓ-1 , ζM (1+η) ℓ 13: |Γ ℓ | ← 1 pi median r∈[R] |S (r) i |, T ℓ ← max(0, Γ ℓ -c) 14: c ← max(c -Γ ℓ , 0) 15: |Λ ℓ | ← T ℓ • (1 + η) ℓ 16: Return F p,Res(k) = ℓ∈[L] |Λ ℓ |(1 + η) ℓ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 to a (1 + O (ε))-approximation. 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 a 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-hitters in the subsampled universe inversely by the sampling probability. We can thus carefully count the number of items in the contributing level sets and subtract off the largest k such items. Because we only have (1 + ε)-approximations to the number of such items, it may be possible that we subtract off too many, hence the bicriteria approximation.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 + ε)-factor. However, we note that the number of such items is only an ε 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 a small number of items with large mass will be estimated within a (1 + ε)-approximation.Lemma 3.2. Let r ∈ [R] be fixed. Then with probability at least 9 10 , we have that simultaneously for all j ∈ U (r) i for which(f j ) p ≥ η 3 •Fp(U (r) i ) 2 7 γ log 2 (nm) , H (r) ℓ outputs f j with 1 - η 8 log(nm) • (f j ) p ≤ ( f j ) p ≤ 1 + η 8 log(nm) • (f j ) p .We now show that the number of items in each "contributing" level set is estimated within a (1 + ε)approximation, including the level sets that contain a large number of small items. Lemma 3.3. Given a fixed ε ∈ (0, 1), let Λ ℓ be a fixed level set and let r ∈ [R] be fixed. Leti = max 1, log(1 + η) ℓ -log γ 2 log(nm) η 3. Define the events E 1 to be the event that|U (r) i | ≤ 32n 2 iand E 2 to be the event thatF p (U (r) i ) ≤ 32Fp 2 i . Then conditioned on E 1 and E 2 , for each j ∈ Λ ℓ ∩ U (r)i , there exists (j, f j ) in S (r) i such that with probability at least 9 10 , 1 -η 8 log(nm) • (f j ) p ≤ ( f j ) p ≤ 1 + η 8 log(nm) • (f j ) p .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 ≥ 0 (possibly upon post-processing the stream) and uses Õ 1 ε 6 • log 3 (nm) bits of space to output an estimateF p,Res(k) with Pr F p,Res(k) -F p,Res(k) ≤ ε • F p,Res((1-ε)k) ≥ 2 3 .4 Adversarially Robust L p EstimationIn this section, we give an adversarially robust algorithm for F p moment estimation on turnstile streams. Due to the relationship between the F p moment and the L p norm, our result similarly translates to a robust algorithm for L p norm estimation. We first require an algorithm to recover all the coordinates of the underlying frequency vector if it is sparse. Theorem 4.1.[GSTV07] There exists a deterministic algorithm SPARSERECOVER that recovers a k-sparse frequency vector defined by an insertion-deletion stream of length n. The algorithm uses k • polylog(n) bits of space.Algorithm 3 Adversarially robust L p -estimation Input: Turnstile stream of length m for a frequency vector of dimension n Output: Adversarially robust heavy-hitters 1: c ← 24p 2 -23p+4 (4p-3)(12p+3) , γ ← 2c 5 -(4p-4) (20p-15) , η ← ε 2 100m γ , k ← O 1 η p , ℓ ← O ε • m c/p k 1-1/p , STATE ←We remark that SPARSERECOVER is deterministic and guarantees correctness on a turnstile stream, even if the frequency vector is not sparse at 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 LZEROEST 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 is 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 a nuance for the analysis because our error guarantee can no longer be relative to the ∥f ∥ p p . Indeed, ε • ∥f ∥ p p additive error may induce (1 + ε)-multiplicative error at one point, but at some later point we could have ∥f ′ ∥ p p ≪ ∥f ∥ p p , 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 k coordinates of f largest in magnitude. Let v be any arbitrary vector such that ∥v∥ 1 ≤ ε 100 • ∥g∥ p • k 1-1/p and ∥v∥ 1 ≤ 1 2 ∥g∥ 1 . Let u be the residual vector omitting the k coordinates of f + v largest in magnitude. Then we have |∥g∥ p p -∥u∥ p p | ≤ ε 4 • ∥g∥ p p .We now show correctness and space complexity of Algorithm 3, after which Theorem 1.3 follows.Lemma 4.3. For log n = Θ(log m), Algorithm 3 uses Õ 1 ε 7.5 • m c 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 -ε)∥f ∥ p p ≤ F ≤ (1 + ε)∥f ∥ p p . 
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-nyc' data center's high-speed monitor. The dataset is commonly used for empirical evaluations on frequency moments and heavy-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 -5 }, values of the heavy-hitter threshold α ∈ {4 -1 , 4 -2 , . . . , 4 -10 }, and the frequency moment parameter p ∈ {1.1, 1.2, . . . , 1.9}.We describe the results in Figure 1 . Results and discussion. Our empirical evaluations serve as a simple proof-of-concept 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 1c , there is not a substantial increase, i.e., 1.24 to 1.31 from p = 1.1 to p = 1.9. On the other hand, as α decreases in Figure 1b , the ratio increases from 1.002 for α = 4 -1 to 1.6 for α = 4 -10 . Similarly, in Figure 1a , the ratio of these quantities begins at 1.17 for ε = 10 -1 and increases to as 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.For a positive integer n > 0, we use [n] to denote the set of integers {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 1 -1 poly(n) , 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 p > 0, the L p norm of a vector v ∈ R n is ∥v∥ p = (v p 1 + . . . + v p n ) 1/p . The p-th moment of v is defined as F p (v) = ∥v∥ p p . Note that for a constant p ≥ 1, a (1 + ε)-approximation to the F p (v) implies a (1 + ε)-approximation to ∥v∥ p . Similarly, for a sufficiently small constant ε ∈ (0, 1), a (1 + O (ε))-approximation to ∥v∥ p implies a (1 + O (ε)) p = (1 + ε)-approximation to F p (v). We thus use the problems of L p norm estimation and F p moment estimation interchangeably in discussion.We use F p,Res(k) (f ) to denote the p-th moment of a vector g obtained by setting to zero the k coordinates of f largest in magnitude, breaking ties arbitrarily. We also define ∥v∥ 0 to be the number of nonzero coordinates of v, so that∥v∥ 0 = |{i ∈ [n] | v i ̸ = 0}|.We recall the following notions regarding differential privacy.Given ε > 0 and δ ∈ (0, 1), a randomized algorithm A : D → R with domain D and range R is (ε, δ)-differentially private if, for every neighboring datasets S and S ′ and for all E ⊆ R,Pr [A(S) ∈ E] ≤ e ε • Pr [A(S ′ ) ∈ E] + δ.Theorem A.2 (Private median, e.g., [HKM + 20]). Given a database D ∈ X * , there exists an (ε, 0)differentially private algorithm PRIVMED that outputs an element x ∈ X such that with probability at least 1 -δ, there are at least |S| 2 -k elements in S that are at least x, and at least |S| 2 -k elements in S in S that are at most x,for k = O 1 ε log |X| δ .Theorem A.3 (Advanced composition, e.g., [DRV10] ). Let ε, δ ′ ∈ (0, 1] and let δ ∈ [0, 1]. Any mechanism that permits k adaptive interactions with mechanisms that preserve (ε, δ)-differential privacy guarantees (ε ′ , kδ + δ ′ )-differential privacy, where ε ′ = 2k ln 1 δ ′ • ε + 2kε 2 . Theorem A.4 (Generalization of DP, e.g., [DFH + 15, BNS + 21]). Let ε ∈ (0, 1/3), δ ∈ (0, ε/4), and n ≥ 1 ε 2 log 2ε δ . Suppose A : X n → 2 X is an (ε, δ)-differentially private algorithm that curates a database of size n and produces a function h : X → {0, 1}. Suppose D is a distribution over X and S is a set of n elements drawn independently and identically distributed from D. Then Pr S∼D,h←A(S)1 |S| x∈S h(x) -E x∼D [h(x)] ≥ 10ε < δ ε .Input: Oblivious algorithms A with failure probability δ 0 , number of queries Q, failure probability δ Output: Algorithm robust to Q queries, with failure probability at most δ1: r ← O √ Q log 2 Q δδ0 2: Implement k = O (r) independent instances A 1 , . . . , A k of A on the input 3: for each query q i , i ∈ [Q] do 4:Let Z i,j be the output of A j on q i 5:Let PRIVMED be 1 r , 0 -DP 6:Return PRIVMED({Z i,j } j∈[k] )We remark that Algorithm 4 is the algorithm corresponding to the statement of Theorem 2.3One reason that DETHH is not commonly utilized is that with the additional power of randomness, significantly better space bounds can be achieved, such as by the following guarantees:Theorem B.1. [CCF04] For p ∈ [1, 2), there exists a randomized algorithm COUNTSKETCH that solves the ε-L p heavy-hitters on a universe of size n and a stream of length m and uses O 1 ε 2 log n log nm δ bits of space.To achieve the guarantees of Theorem 2.2, a natural approach would be to apply Theorem 2.3 to the guarantees of COUNTSKETCH in Theorem B.1. However, this does not achieve the optimal bounds because each round of adaptive queries can require multiple answers, i.e., estimated frequencies for each of 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 S be the output of ROBUSTCS at the beginning of a block. Then conditioned on the correctness of ROBUSTCS, S solves the L p -heavy hitter problem on the entire block.Proof. Suppose the number of distinct elements at the beginning of a block is at least 50t. Let f be the frequency vector at the beginning of the block and let g be the frequency vector at any intermediate step in the block. Conditioned on the correctness of ROBUSTCS, we have that the estimated frequency f i of each item i satisfies| f i -f i | ≤ t 1/p 100 .Thus if f i is an ε 2 -L p heavy hitter, then i ∈ S and conversely if i ∈ S, then f i ≥ ε 4 ∥f ∥ p . Since each block has length ℓ = ε 100 t 1/p , then |g i -f i | ≤ ε 100 t 1/p . Moreover, because the number of distinct elements is at least 50t, then we have ∥f ∥ p ≥ 50t 1/p . Therefore if g i is an ε-L p heavy hitter, then f i is an ε 2 -L p heavy hitter, so that i ∈ S. Similarly ifg i < ε 2 ∥g∥ p , then f i < ε 4 ∥f ∥ p , so that i / ∈ S.Lemma 2.6. With high probability, ROBUSTCS is correct at the beginning of each block of length ℓ.Proof. We have ℓ = ε 100 • t 1/p . Note that there are b = m ℓ = 100m εt 1/p blocks of length ℓ. 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.Lemma 2.7. The total space by the algorithm is Õ 1 ε 2.5 m (2p-2)/(4p-3) bits of space.Proof. Since DETHH is called with threshold ε 16 for t = O m p/(4p-3) , then the total space by DETHH is Õ 1 ε 2 t 2-2/p = Õ 1 ε 2 m (2p-2)/(4p-3) bits. We require ROBUSTCS to be robust to b queries in the subroutine ADAPTIVEHH, thus using spaceÕ √ b ε 2 log n log nmλ δ for δ = 1 poly(n,m) and Õ √ b = Õ m εt 1/p = Õ ε -1/2 m (2p-2)/(4p-3) .Similarly, we use Õ √ b = Õ ε -1/2 m (2p-2)/(4p-3) instances of LZEROEST to guarantee robustness against b queries. Each instance of LZEROEST uses O 1 ε 2 log 2 (nm) bits of space. Hence, the overall space is Õ 1 ε 2.5 m (2p-2)/(4p-3) bits.We revisit the guarantee of COUNTSKETCH with a different parameterization in this section.Theorem C.1. [CCF04] Given p ∈ [1, 2], there exists a one-pass streaming algorithm COUNTSKETCH that with high probability, reports all j ∈ [n] for which (f j ) p ≥ ε p F p , along with estimations f j , such that(1 -ε)f p j ≤ ( f j ) p ≤ (1 + ε)f p j .Observe that to provide the guarantees of Theorem C.1, COUNTSKETCH would require space poly 1 ε , log n , rather than quadratic dependency 1 ε . Lemma 3.2. Let r ∈ [R] be fixed. Then with probability at least 9 10 , we have that simultaneously for all j ∈ U (r) i for which(f j ) p ≥ η 3 •Fp(U (r) i ) 2 7 γ log 2 (nm) , H (r) ℓ outputs f j with 1 - η 8 log(nm) • (f j ) p ≤ ( f j ) p ≤ 1 + η 8 log(nm) • (f j ) p .Proof. The proof follows from Theorem C.1 and the fact that COUNTSKETCH is only run on the substream induced byI (r) ℓ . Proof. Consider casework on log(1 + η) ℓ -log γ 2 log(nm) η 3 ≤ 1 or log(1 + η) ℓ -log γ 2 log(nm) η 3 > 1.Informally, the casework corresponds to whether the frequencies f j p in a significant level set are large or not large, i.e., whether they are above the 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 + η) ℓ -log γ 2 log(nm)η 3 ≤ 1, so that 1 (1+η) ℓ-1 ≥ η 3 γ log 2 (nm) . Note that j ∈ Λ ℓ implies (f j ) p ∈ ζM (1+η) ℓ-1 , ζM (1+η) ℓand thus (f j ) p ≥ η 3 ζM γ log 2 (nm) . Note that M ≥ F p and thus by Lemma 3.2, we have that with probability at least 9 10 , H (r) i outputs f j such that1 - η 8 log(nm) • (f j ) p ≤ ( f j ) p ≤ 1 + η 8 log(nm) • (f j ) p ,as desired.For the other case, suppose log(1 + η) ℓ -log γ 2 log(nm)η 3 > 1, so that i = log(1 + η) ℓ -log γ 2 log(nm) η 3. Since p i = 2 1-i , then we have thatEQUATION1+η) ℓ and therefore,(f j ) p ≥ F p 4 • (1 + η) ℓ ≥ η 3 4γ log 2 (nm) F p 2 i-1 .Conditioning on the event E 2 , we haveF p (U (r) i ) ≤ 32Fp 2 i and thus (f j ) p ≥ η 3 4γ log 2 (nm) 2F p 2 i ≥ η 3 128γ log 2 (nm) • F p (U (r) i ).Hence by Lemma 3.2, we have that with probability at least 9 10 , HEQUATION• (f j ) p , as desired.We now give the correctness guarantees of Algorithm 2.Lemma C.2. Pr F p,Res(k) -F p,Res(k) ≤ ε • F p,Res((1-ε)k) ≥ 2 3 .Proof. We would like to show that for each level set ℓ, we accurately estimate its residual contribution D ℓ . More specifically, we would like to show| D ℓ -D ℓ | ≤ η 8 log(nm) • F p for all ℓ ∈ [L].Let g be the residual vector of f with the largest k coordinates in magnitude set to zero. For a level set ℓ, we define the fractional contribution ϕ ℓ := C ℓ i∈[n] (fi) p . Given an accuracy parameter ε and a stream of length m, we define a level set Λ ℓ to be significant if ϕ ℓ ≥ ε 2 η 100p log(nm) . Furthermore, we define a level set Λ ℓ to be contributing if ϕ ℓ ≥ εη 100p log(nm) . Otherwise, the level set is defined to be ϕ ℓ < ε 2 η 100p log(nm) . . For a fixed ℓ, we have thatEQUATION1+η) ℓ . On the other hand, for each fixed r, we have that S (r) ℓ is determined using items j whose estimated frequency are in the rangeEQUATION1+η) ℓ , so it is possible that j could be classified into contributing to Λ ℓ even if j / ∈ Λ ℓ . Hence, we first analyze an "idealized" setting, where each index j is correctly classified across all level sets ℓ ∈ [L]. We that we achieve a (1 + Õ (ε))-approximation to F p 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 + ε)-approximation to F p , since only a small number of coordinates will be misclassified and so our approximation guarantee will only slightly degrade.Idealized setting. For a fixed r ∈ [R], let E 1 be the event that |U (r) i | ≤ 32n 2 ℓ and let E 2 be the event that F p (U (r) i ) ≤ 32Fp 2 ℓ . Note that M ≥ F p and thus conditioned on E 1 , E 2 , then by Lemma 3.2, we have that with probability at least 9 10 , HEQUATION• (f j ) p , as desired.We first show that when ( f j ) p is correctly classified for all j into level sets ℓ ∈ [L], then with probability 1 -1 poly(nm) , we have that simultaneously for each fixed level set ℓ,| D ℓ -D ℓ | ≤ η 8 log(nm) • F p .We defineD ℓ = T ℓ • (1 + η) ℓ, where T ℓ is the estimated size of Λ ℓ , formed by attempting to truncate the top k coordinates across the level sets Γ ℓ . In particular, we define|Γ ℓ | = 1 pi median r∈[R] |S (r) i | for i = max 1, log(1 + η) ℓ -log γ 2 log(nm) η 3 .We analyze the expectation and variance of |Γ ℓ |. Firstly, let r ∈ [R] be fixed and for each j ∈ Γ ℓ , let Y j be the indicator variable for whether Y j ∈ S (r) i . We haveE 1 p i • |Γ ℓ ∩ S (r) i | = 1 p i • j∈Γ ℓ E [Y j ] = 1 p i • (p i • |Γ ℓ |) = |Γ ℓ |.Similarly, we haveVar 1 p i • |Γ ℓ ∩ S (r) i | ≤ 1 p 2 i • j∈Γ ℓ E [Y j ] = 1 p 2 i • (p i • |Γ ℓ |) = |Γ ℓ | p i . Because p i ≥ min 1, γ 2 log 2 (nm) (1+η) ℓ η 3, then we have that by Chebyshev's inequality,Pr 1 p i • |Γ ℓ ∩ S (r) i | -|Γ ℓ | ≥ |Γ ℓ | • (1 + η) ℓ η 3 ≤ 1 10 ,conditioned on the events E 1 , E 2 , and E 3 .To analyze the probability of the events E 1 and E 2 , recall that in Ui , each item is sampled with probability 2 -i+1 . Hence,E |U (r) i | ≤ n 2 i-1 , E F p (U (r) i ) ≤ F p 2 i-1 .We define E 1 to be the event that|U (r) i | ≤ 32n 2 i . By Markov's inequality, we have Pr [E 1 ] ≥ 15 16. Similarly, we define E 2 to be the event thatF p (U (r) i ) ≤ 32Fp 2 i . By Markov's inequality, we also have Pr [E 2 ] ≥ 15 16 . We have that Pr E 3 | E 1 ∧ E 2 ≥ 9 10. Thus by a union bound,Pr 1 p i • |Γ ℓ ∩ S (r) i | -|Γ ℓ | ≥ |Γ ℓ | • (1 + η) ℓ η 3 ≤ 1 3 .By Chernoff bounds, we thus havePr |Γ ℓ | -|Γ ℓ | ≥ |Γ ℓ | • (1 + η) ℓ η 3 ≤ poly ε log(nm).Moreover, if level ℓ is significant, then eitherp i = 0 or |Γ ℓ | ≥ (1+η) ℓ 2η 3 . If p i = 0, then |Γ ℓ | = |Γ ℓ |. Otherwise if |Γ ℓ | ≥ (1+η) ℓ2η 3 , then with probability at least 1 -poly ε log(nm) , we have that simultaneously for all significant levels ℓ ∈[L], (1 -η)|Γ ℓ | ≤ |Γ ℓ | ≤ (1 + η)|Γ ℓ | or in other words, |Γ ℓ | -|Γ ℓ | ≤ η|Γ ℓ |.Since we subtract off the top k coordinates in Γ ℓ to form |Λ ℓ | then we also have|Λ ℓ | -Λ ℓ ≤ η|Γ ℓ |. It follows that since j ∈ Λ ℓ for (g j ) p ∈ ζM (1+η) ℓ-1 , ζM (1+η) ℓ , then for D ℓ = |Λ ℓ | • (1 + η) ℓ , we have that | D ℓ -D ℓ | ≤ η(1 + η)C ℓ .Taking the sum over all the significant levels, we see that the error is at most ℓ∈[L] 2ηC ℓ ≤ ε 2 2 • F p,Res((1-ε)k) .Note that the same guarantee holds if level ℓ is insignificant, provided that |Γ ℓ | < (1+η) ℓ 1000η 3 . On the other hand, if level ℓ is insignificant and |Γ ℓ | < (1+η) ℓ 1000η 3 . Thus with probability at least 1 -poly ε log(nm) , we have that simultaneously for all insignificant levels ℓ ∈ [L], [|Γ ℓ | ≤ 1 200η 3 . Then we set D ℓ = 0, so that | D ℓ -D ℓ | = D ℓ .In fact, we observe that the number of items in insignificant level sets can only be at most an η fraction of the items in the contributing level sets beneath them. Since the sum of the contributions of contributing level sets is at most F p,Res((1-ε)k) , then taking the sum over all the significant levels, we see that the error is at most the contribution of the tail of the insignificant levels, which by definition is at most ε2 • F p,Res((1-ε)k) .Randomized boundaries. By Lemma 3.2, we have that conditioned on E 3 ,1 - η 8 log(nm) • (f j ) p ≤ ( f j ) p ≤ 1 + η 8 log(nm) • (f j ) p , independently of the choice of ζ. Because we drawn ζ ∈ [1, 2] uniformly at random, then the probability that j ∈ [n] is misclassified is at most η 2 log(nm) . If j ∈ [n] is indeed misclassified, then it can only be classified into either level set Γ ℓ+1 or level set Γ ℓ-1 , since f j p is a 1 + η 8 log(nm) -approximation to (f j ) p .As a result, a misclassified index induces at most η(f j ) p additive error to the contribution of level set Γ ℓ and hence at most η(f j ) p additive error to the contribution of level set Λ ℓ in the residual vector. Therefore, the total additive error across all j ∈ [n] due to misclassification is at most η • F p in expectation. By Markov's inequality, the total additive error due to misclassification is at most ε 2 • F p,Res((1-ε)k) with probability at least 0.95. Theorem 3.4. There exists a one-pass streaming algorithm RESIDUALEST that takes an input parameter k ≥ 0 (possibly upon post-processing the stream) and uses Õ 1 ε 6 • log 3 (nm) bits of space to output an estimateF p,Res(k) with Pr F p,Res(k) -F p,Res(k) ≤ ε • F p,Res((1-ε)k) ≥ 2 3 .Proof. Consider Algorithm 1. By Lemma C.2, we have thatPr F p,Res(k) -F p,Res(k) ≤ ε • F p,Res((1-ε)k) ≥ 2 3 .It thus remains to analyze the space complexity.Note that Algorithm 1 implements P • R instances of COUNTSKETCH with accuracy η 3 , for P = Õ (log(nm)), R = Õ log log n η , and η = ε 100 . By Theorem C.1, each instance of COUNTSKETCH with threshold η 3 uses O 1 η 6 • log 2 (nm) bits of space. Therefore, the total space usage of Algorithm 1 is Õ 1 ε 6 • log 3 (nm) bits.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.and RESIDUALEST, we have G + H is a (1 + O (ε))-approximation to ∥f ∥ p p . For the purposes of notation, let h denote the residual vector of f at time t, omitting the k coordinates of f largest in magnitude. Now, consider some later time t ′ in the same block of ℓ updates and let v be the frequency vector induced by the updates in the block, i.e., the updates from t to t ′ . Let u be the residual vector omitting the k coordinates of f + v largest in magnitude. Since Finally, we analyze the space complexity of our algorithm. Lemma D.4. For log n = Θ(log m), Algorithm 3 uses Õ 1 ε 7.5 • m c bits of space in total.∥v∥ 1 ≤ ℓ for ℓ = O ε • m c/p k 1-1/p ,Proof. We observe that Algorithm 3 uses a few main subroutines. Firstly, it runs SPARSERECOVER with sparsity O (m c ), which requires m c • polylog(nm) bits of space, by Theorem 4.1. Next, it runs ROBUSTHH with threshold εη, for η = ε 2 100m γ . By Theorem 1.2, ROBUSTHH uses Õ 1 (εη) 2.5 m (2p-2)/(4p-3) bits of space. Note that for our choice of γ = 2c 5 -(4p-4) (20p-15) , we have Õ1 (εη) 2.5 m (2p-2)/(4p-3) = Õ 1 ε 7.5 • m c bits of space. Finally, it runs Õ √ m ℓcopies of LZEROEST and RESIDUALEST. By Theorem 3.4, each instance of RESIDUALEST uses Õ 1 ε 6 • log 3 (nm) bits of space. By Theorem 2.4, each instance of LZEROEST uses O log 2 (nm) log log m bits of space. Since ℓ = O ε • m c/p k 1-1/p , then we have Õ √ m ℓ = Õ (m c ) and thus the total space usage by these subroutines is Õ 1 ε 6 • m c bits The desired claim then follows by noting that across all procedures, the space usage is Õ 1 ε 7.5 • m c , due to our balancing choices of ℓ, γ, and c. Lemma 4.3. For log n = Θ(log m), Algorithm 3 uses Õ 1 ε 7.5 • m c 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 -ε)∥f∥ p p ≤ F ≤ (1 + ε)∥f ∥ p p .Proof. Note that Lemma 4.3 follows from Lemma D.3 and Lemma D.4.Putting things together, we get the full guarantees of our main result:Theorem 1.3. Let p ∈ [1, 2] and c = 24p 2 -23p+4 (4p-3)(12p+3). There exists a streaming algorithm that uses O (m c ) • poly 1 ε , log(nm) bits of space and outputs a (1 + ε)-approximation to the L p 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.As adversarial robustness can have applications to many applications in 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to 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 the paper. Guidelines:• The answer NA means that paper does not include experiments requiring code. 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).(11) SafeguardsQuestion: 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 no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.(12) Licenses for existing assets Question: 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?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.• If this information is not available online, the authors are encouraged to reach out to the asset'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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

 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.
Additionally, the paper focuses on the turnstile setting, i.e. the updates $\Delta_i$ to the vector can be both positive and negative.

The 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.

The 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$.

Up 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.

The 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$.

The work improves on the dense-sparse decomposition method of the previous work.
strength_weakness: strength_weakness: - 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}$.

- 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.
questions: 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.

Subsection 1.1. would be easier to read if the paper used \paragraph to separate the parts of the subsection that address different problems.
limitations: 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.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: Apart from the limitation described in the theorem statement, the authors could discuss limitations of this approach, and what the current barrier is.
paper_summary: paper_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.

The 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.

The achievement follows by leveraging known deterministic algorithms for heavy hitters and using them for tracking significant changes to the frequency vector.
strength_weakness: strength_weakness: 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$.
questions: 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? 

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?

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.
limitations: limitations: No direct negative social impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 

- 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.
questions: 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.
- 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: limitations: I think the authors have adequately addressed limitations and the assumptions made in their results.

Comments: comment: Thank you for the response.
Thank your for the response and reassuring me about the correctness of papers by Ganguly et al. I'm happy to improve my score to 7 (Accept). I still stand behind my conviction that the cases of $p = 0$ or $p =2$ would be more interesting.

As for the entropy application question, let me just warn you about a subtle point if you decide to mention it in your paper. For a fixed constant $p$, you usually do not care if there is a multiplicative factor that depends only on $p$ in the complexity of estimating $\ell_p$. In the entropy application, you are not considering, however, a fixed $p$, but you select $p = 1 + \delta$, where $\delta$ is some function of $\epsilon$ and perhaps parameters of the stream. Then the final complexity will have an additional multiplicative factor that depends on $\delta$ and you have to make sure it's not prohibitively large. This is usually not what people focus on for moment estimation, but for standard moment estimation algorithms, you get at a factor of at least $1/\delta$ I think. You would have to check the literature devoted to fractional moment estimation and see what impact (if any) this has on the complexity of deterministic heavy hitters you use.
Thanks for your response! I will tentatively raise my score to a 7: Accept.
Thank you for your response. Tentatively, I keep my rating at 6: Weak Accept