Private Data Stream Analysis for Universal Symmetric Norm Estimation
Authors: Vladimir Braverman
Joel Manning
Steven Wu
Samson Zhou
Venue: Submitted to ICLR 2023 (2023)
Keywords: differential privacy
norm estimation

Abstract: We study how to release summary statistics on a data stream subject to the constraint of differential privacy. In particular, we focus on releasing the family of \emph{symmetric norms}, which are invariant under sign-flips and coordinate-wise permutations on an input data stream and include $L_p$ norms, $k$-support norms, top-$k$ norms, and the box norm as special cases. Although it may be possible to design and analyze a separate mechanism for each symmetric norm, we propose a general parametrizable framework that differentially privately releases a number of sufficient statistics from which the approximation of all symmetric norms can be simultaneously computed. Our framework partitions the coordinates of the underlying frequency vector into different levels based on their magnitude and releases approximate frequencies for the ``heavy'' coordinates in important levels and releases approximate level sizes for the ``light'' coordinates in important levels.  Surprisingly, our mechanism allows for the release of an \emph{arbitrary} number of symmetric norm approximations without any overhead or additional loss in privacy. Moreover, our mechanism permits $(1+\alpha)$-approximation to each of the symmetric norms and can be implemented using sublinear space in the streaming model for many regimes of the accuracy and privacy parameters.

PRIVATE DATA STREAM ANALYSIS FOR UNIVERSAL SYMMETRIC NORM ESTIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
We study how to release summary statistics on a data stream subject to the con- straint of differential privacy. In particular, we focus releasing the family of symmetric norms, which are invariant under sign-flips and coordinate-wise per- mutations
input data stream and include Lp norms, k-support norms, top-k norms, and the box norm as special cases. Although may be possible to de- sign and analyze separate mechanism for each symmetric norm, we propose a general parametrizable framework that differentially privately releases a number of sufficient statisties from which the approximation of all symmetric norms can be simultaneously computed. Our framework partitions the coordinates of the underlying frequency vector into different levels based on their magnitude and releases approximate frequencies for the "heavy" coordinates in important levels and releases approximate level sizes for the "light" coordinates in important lev- els. Surprisingly, our mechanism allows for the release of an arbitrary number of symmetric norm approximations without any overhead or additional loss in pri- vacy. Moreover, our mechanism permits (1 + a >appproximation to each of the symmetric norms and can be implemented using sublinear space in the streaming model for many regimes of the accuracy and privacy parameters.
INTRODUCTION
underlying dataset, where the Lp norm of an n--dimensional vector freqeuncy x is defined as the number of nonzero coordinates x for
The family of Lp norms represent important statisties
p 0 and [x, (xf ... + x//)1/ 1/P for p > O. Thus, Lg norm counts the number of distinet elements in the dataset and, e.g., is used to detect denial of service or port sean attacks in network monitoring (Akella et al., 2003; Estan al., 2003), to understand the magnitude of quantities such as search engine queries or internet graph connectivity in data mining (Palmer et al., 2001), to manage workload in database design (Finkelstein al., 1988), and to select a minimum-cost query plan in query optimization (Selinger et al., 1979). The L1 norm computes the total number of elements in the dataset and, e.g., is used for data mining (Cormode al., 2005) and hypothesis testing (Indyk & McGregor, 2008), while the T.2 norm, e.g., is used for training random forests in machine learn- ing (Breiman, 2001), computing the Gini index in statistics (Lorenz, 1905; Gini, 1912), and network anomaly detection in traffic monitoring (Krishnamurthy et al., 2003; Thorup & Zhang, 2004). Con- sequently, Lp estimation has been extensively studied the data stream model (Alon et al., 1999; Indyk & Woodruff, 2005; Indyk, 2006; Li, 2008; Kane al., 201 Andoni, 2017; Braverman al., 20188: 8b;; Ganguly & Woodruff, 2018; Woodruff & Zhou, 2020; 2021). The simplest streaming model perhaps the insertion-only model, in which sequence of m updates increments coordinates of an nndimmnniioal frequency vector x and the goal is to compute or approximate some statistic of x in space that is sublinear in both m and n.
In many cases, the underlying dataset contains sensitive information that should not be leaked. Hence, an active line of work has focused on estimating Lp norms for various values of p, while preserving differential privacy (Mir et al., 2011; Blocki et al., 2012; Smith et al., 2020; Bu et al., 2021: Wang et al., 2021).
Definition 1.1 (Differential privacy). (Dwork et al., 2006) Given > 0 and E (0, 1). a randomized algorithm A II y is (e, -ddifferrenl private if. for every neighboring streams & and &

---

and for all E y
Pr Pr(A E E Prr(A(r) E E]+
where streams G and G' are neighboring if there exists a single update E [m]] such that us + ula where "1,..., Um are the updates of G and ui,,..,,u wmm are the updates of G'.
For example, (Blocki et al., 2012) showed that the Johnson--Lindenstraus transformation preserves differential privacy (DP), thereby showing one of the main techniques in the streaming model for L2 estimation already guarantees DP. Similarly, (Smith et al., 2020) showed that the Flajolet-Mann Martin sketch, which is one of the main approaches for Lo estimation in the streaming model, also preserves DP. Notably, algorithmic designs for Tpp estimation in the streaming model differ greatly and require individual analysis to ensure DP, which can be quite difficult due to the complexity of the various techniques. This is especially pronounced in the work of (Wang et al., 2021), who studied the p-stable sketch that estimates the Lp norm for p E (0, 2] (Indyk, 2006)'. (Wang et al., 2021) showed that for p E (0, 1], the p-stable sketch preserves DP, but was unable to show DP for p E (1, 2). even though the general algorithmic approach remains the same. Thus the natural question is whether differential privacy can be guaranteed for approach that simultaneously estimates the Lp norm in the streaming model, for all p. More generally, the family of Lp norms are all symmetric norms, which are invariant under sign-flips and coordinate- wise permutations on input data stream. Symmetric norms thus also include other important families of norms such as the k- support norms and the top-k norms.
In this paper, we show that not only does there exist a differentially private algorithm for the es- timation of symmetric norms in the streaming model, but also that there exists an algorithm that privately releases set of statistics, from which estimates of all (properly parametrized) symmetric norms can be simultaneously computed. To illustrate the difference, suppose we wanted to release approximations of the Lp norm of the stream for & different values of p. To guarantee (e, 6)-DP for the set of k statistics, we would need, by advanced composition, to demand (o (0
VK ; .0 -DP
from instances of a single differentially private Lpp-stimation algorithm, corresponding to the different values of p. Due to accuracy-privee privacy tradeoffs, the quality of the estimation will degrade severely as & increases. By comparison, our algorithm releases a single set C' of private statistics. By post-processing, we can then estimate the Tnp norms for k different values of while only requiring (s, 8)-DP from C. Hence, our algorithm can simultaneously handle any large number of estimations of symmetric norms without compromising the quality of approximation.
Theorem 1.2. There exists a (e, 8) -iiiffeerntiaaly private algorithm that outputs a C. from which the (1 + a) approximation to any norm with maximum modulus of concentration at most M can be computed, with probability at least 1 - 5. The algorithm uses M poly (a. 1 x: log n, log 1) bits of
space.
The maximum modulus of concentration of norm measures the worst-case ratio of the maximum value to the median value norm on the Lz-unit sphere for any restriction of the coordinates and can intuitively quantify the complexity of computing norm. For example, the I, norm is generally "easy" to compute and has maximum modulus of concentration O (logn) n))
We emphasize that prior to work, there is algorithm that can handle private symmetric norm estimation, much less simultaneously for all parametrized symmetric norms. Although there is specific analysis for various norm estimation algorithms, e.g., see the discussion on related work in the supplementary material, these algorithms require a specific predetermined norm for their input. Thus a separate private algorithm must be run for each estimation, which increases the overall space. Moreover, for a large number of queries, the privacy parameter will need to be much smaller due to the composition of privacy, and thus to ensure privacy, the utility of each algorithm is provably poor. Our algorithm sidesteps both the space and accuracy problems and is the first and only work to do so.
Applications. We briefly describe number of specific symmetric norms that are handled by The- orem 1.2 and commonly used across various applications machine learning. We first note the following parameterization of the previously discussed Lp norms.
'Tp for (0,1) does not satisfy the triangle inequality and therefore is not a norm, but is still well- defined/welllmattiall and can he computed
2

---

Lemma 1.3. (Milman & Schechtman, 2009; Klartag & Vershynin, 2007) For Lp norms, have for p [1,2] and mmc((T) [.) O (n//2-1/o) for p > 2.
that mmc(T. (.) O (log for
Thus our algorithm immediately introduces a differentially private mechanism for the approximation of 1.p norms that unlike previous work, e.g., (Blocki et al., 2012; Sheffet, 2019; Choi et al., 2020; Smith et al., 2020; Bu ct al., 2021; Wang ct al., 2021), does not need to provide separate analysis for specific values of p. Moreover for constant-factor approximation, the space complexity is tight with the optimal appapooxiimtoo algorithms that do not consider privacy, up to polylogarithmic factors (Kane et al., 2010; Li & Woodruff, 2013; Ganguly, 2015; Woodruff & Zhou, 2021).
Definition 1.4 (Q (Q-norm and Q' Qonnor). We call a norm L a Q-norm if there exists a symmetric norm L' such that L(x)) = 122 for all x E IR". Here, use x² to denote the coordinate square power of z. We also call a norm L' a Q' Q'-orm if its dual norm is a Q-norm.
The family of Q'-norms includes the T.p norms for 1 S p S 2, the k-support norm, and the box norm (Bhatia, 2013) and thus Q'-norms have been proposed to regularize sparse recovery problems in machine learning. For instance, (Argyriou et al., 2012) showed that Q' norms have tighter relax- ations than elastic nets and can thus be more effective for sparse prediction. Similarly, (McDonald et al., 2014) used Q' norms to optimize sparse prediction algorithms for multitask clustering. Lemma 1.5. (Blasiok et al., 2017) mmc [.) = O (logn) n) every Q' -'-ormm L..
Theorem 1.2 and Lemma 1.5 thus present a differentially private algorithm for Q' Qnnorm approxima- tion that uses polylogarithmic space.
Definition 1.6 (Top-k norm). The top-k norm for a vector x E R is the sum of the largest coordinates of (zr.. where we use |z]| to denote the coordinate absolute value of x.
The top-k norm frequently used to understand the more general Ky Fan k-norm (Wu al., 2014) 4), which is used to regularize optimization problems in numerical linear algebra. Whereas the Ky Fan k norm is defined as the sum of the k largest singular values of a matrix, the top-k norm is equivalent to the Ky Fan k norm when the input vector z represents the vector of the singular values of the matrix.
Lemma 1.7. (Blasiok et al., 2017) mL) Ô (V+) for the top-k norm L.
In particular, the top-k norm for vector of singular values when k n is equivalent to the Schatten- 1 norm of a matrix, which is a common metric for matrix fitting problems such as low-rank approx- imation (Li & Woodruff, 2020).
2 PRELIMINARIES
In this section, we introduce definitions and simple or well-known results from differential privacy, sketching algorithms, and symmetric norms. For notation, we use [n] for an integer n > 0 to denote the set (1, rt.. We also use the notation poly(n) to represent constant degree polynomial in n and we say an event occurs with high probubility if the event holds with probability poly(n)* Similarly, we use polylog(n) to denote poly(logn).
Sketching algorithms. Given a frequency vector z F on a data stream, the AMS algorithm for T-zestimattion first generates a sign vector E [11,+1}² and sets S = ((),,)))² The AMS algorithm then repeats this process h = d independent times to obtain dot products Si,... S,, sets z² to be the arithmetic mean of ,,,..., S,, and reports Z.
We define the La norm of a vector I E R" by L2(x)= = V
Lz-heavy hitters). Given an accuracy parameter E (0.1). threshold parameter y, and a frequency vector z E R", compute a set H and set of approximations Ty for all lo E H such that:
Definition 2.1 (v-approximate
(1) If nL2(x) for any k [n), then k E H, so that H contains all 1) Lz-heavy hitters of T.
(2) There exists a universal constant C > 0 so that if I < Cu L2(x) for any k E [n], then 2
k & H, so that H does not contain any index that is not an
On L Lz-heavy hitter of x.
3

---

(3) Ifk H. for any ls [n], then compute (1 v)) approximaatin the frequency 2h, i.e., value Fy such that (1 - v) I F I (1 (1+1)2g
We introduce and use a private variant PRIV PRIVCOUNTSKETCH of the well-known COUNTSKETCH algorithm (Charikar et al., 2004) by adding noise to each coordinate and then using standard private threshold routine to ensure differential privacy. Specifically, PRIVCOUNTSKETCH first uses the COUNTSKETCH data structure to obtain estimated frequency for each coordinate. It then adds
to each estimated frequency and then acquires a threshold 7 from the L2 norm estimation algorithm AMS and releases all coordinates (and estimated frequencies) whose estimated frequencies are at least scale parameter
Laplacian noise with scale parameter O 1--
Pyf 2 X, where is Laplacian noise with
Then PRIVCOUNTSKETCH gives the following guarantees:
Lemma 2.2. There exists a one-pass streaming algorithm PRIvCOUNTSKETCH that takes an ac- curacy parameter E (0, and a threshold parameter 1j² and outputs list H that contains all indices E [n] of an underlying frequency vector x with 2k 2 L2(x) and no index E [n]] with I& S (11 - L2(r). For each k E Н. PRIVCOUNTSKETCH
also reports estimated fre-
quency Ikk such that (1 v) O
log mi
S IK S (1 + D) + +0 log m
The algorithm uses
Tj
uroz log" n) bits of space and succeeds with probability 1 - poly(m)
Symmetric norms. We now introduce preliminaries for symmetric norms.
Definition 2.3 (Symmetric norm). A function L RR" E is a symmetric norm if is a norm and for all x E IR" and any vector E IR. that is a permutation of the coordinates of x. we have L(x) L(y). Moreover, we have L(x) I((x)), where (ar] is the coordinate- absolute value of x.
Definition 2.4 (Modulus of concentration). Let I E IR be a random variable drawn from the uniform distribution on the Lz-unit sphere Sm-1 and let by denote the maximum value of L(x) over ST-1 The median of a symmetric norm L is the unique value ML such that Pr Pr[((z) 2 M2] 2 1
and Pr (Txx) Mr) 2 2- Then the ratio mc(L)) norm L.
by is the modulus of concentration of the ML
Although the modulus of concentration quantifies the "average" behavior of the norm L on IR", norms with challenging behavior can still be embedded in diver-dimeniional subspaces. For stance. the L1 norm satisfies mc(L) = O (1), but when x E R" has fewer than vn nonzero coordinates, the norm max(Loo (z), L, (x)/vn) on the unit ball becomes identically L (Bla- siok et al., 2017), which requires ((vn)) space (Alon et al., 1999) to estimate. Hence, we further quantify the behavior of a norm T. by examining its behavior on all lower dimensions.
Definition 2.5 (Maximum modulus of concentration). For norm L. R. R and every k n. define the norm (k) g + R by ( ((x1,...... II)] = L((21..... Ik. .,......)). Then the b,,00
maximum modulus of concentration of the norm L is mmnoL) = max mo (m(()())) max kSn M MLON"
kSn
Definition 2.6 (Important Levels). For R and & >> 1, we define the level i as the set B {k E [n] : gi- & |æa| < E.}. We define b, = B. as the size of level i. For 8 E (0, (0,1], we say level i is 8-important if by B Ejziby and 21 2 Ejss by.21.
Informally, level 8-important if (1) its size is at least 3-fraction of the total sizes of the higher levels and (2) its contribution is roughly f-fraction of the total contribution of all the lower levels. We would like to show that to approximate symmetric norm L(x), it suffices to identify the 3- important levels and their sizes for fixed base E 1.
Lemma 2.7. (Blasiok et al., 2017) Let s = O (logn). If level is 8-important, then
either 2i 2
Tog" F2(x) or there exists j [s] such that b, 2
a²
2 log" m
and g
0² Ps(x) log
a² F((x)
log*
Lemma 2.7 implies that if level is ß-important, then either (1) will be identified by using PRIVCOUNTSKETCH with threshold log m
a²
the stream or (2) its contribution be well-
4

---

approximated by using PRIVCOUNTSKETCH with threshold a² log" m on substream formed by sam-
pling coordinates of the universe with probability 27 We thus split our algorithm and analysis to handle these cases. In particular, we call a frequency level "high" if t²i z
log (2(2). We call
a²B=²
frequency level "medium" if ç a²g'e" F2(x)) > and b, 2 O a²B'="
2 log" m for certain B
and a threshold T. We call a frequency level i "low" if g²i 2 2
F2(2) and b, 2 O (
2 log" m a²e²
but T 2 2 (2(x).
B'=
ALGORITHMIC INTUITION AND OVERVIEW
In this section, we give brief technical overview both our algorithmic intuition and how our ap- proaches differ from previous (non-private) work. We defer the full proofs and additional discussion of related work to the supplementary material.
Our starting point is the Lp estimation algorithm of (Indyk & Woodruff, 2005), which was parametrized by (Blasiok et al., 2017) to handle symmetric norms. For a (1 + a)aaproxximttoon the algorithm partitions the coordinates of the frequency vector into powers of {-based on their magnitudes, where ξ > is a fixed function of a. Each partition forms a level set, but (Indyk & Woodruff, 2005; Blasiok et al., 2017) showed that it suffices to accurately count the size of each important level set and zero out to the other level sets, where a level set is considered important its size is large enough to contribute an Tog
a² fraction of the symmetric norm.
Private symmetric norm estimation in the centralized setting. To preserve (s, ddiiferrrnt privacy, one initial approach would be to treat the statistics as a histogram and add Laplacian noise with scale O (c) to the frequency of each element. However, the level sets consisting of elements with frequencies between c(+1) for small i, say = O, could be largely perturbed by such Laplacian noise. Fortunately, if is small, the corresponding level set must contain large number of elements if is important, so it seems possible to privately release the size L3 of the level set. Indeed, we can show that the L1 sensitivity of the vector corresponding to level set sizes is small
and so we can add Laplacian noise with scale O (2) to each level set size. Hence the level set has size r. roughly Ω (d)). then the Laplacian noise will affect r, by (1 + a-)-fcttor.
Unfortunately, there can be level sets that are both important and small in size. For example, if there is a single element with frequency m, then the size of the corresponding level set is just one. Then adding Laplacian noise with scale O (?) will severely affect the size of the level set and thus the estimation of the symmetric norm. On the other hand, for m > I. the frequency of the coordinate is quite large so again it seems like we can just add Laplacian noise with scale O (2) and output the noisy frequency of the coordinate.
az
classifying and separately handling high, medium, and low frequency levels. The main takeaway from these challenges is that we should handle different level sets separately. We partition the levels into three groups after defining thresholds Ti and T2. with Ti > T.. We define the "high frequency levels" as the levels whose coordinates exceed Ti in frequency. The intuition is that because the high frequency levels have such large magnitude, their frequencies can be well-approximmted by running an Le-heavy hitters algorithm on the stream S.
New approach:
We define the "medium frequency levels" as the levels whose coordinates are between Ti and Tr in frequency. These coordinates are not large enough to be detected by running an L2-heavy hitters algorithm on the stream S. However, the sizes of these level sets must be large if the level set is important. Thus there exists substream Sy for which a large number of these coordinates are sub- sampled and their frequencies can be well-approximated by rumning Le Le-vy hitters algorithm on the substream Sz. Finally, we define the "low frequency levels" as the levels whose coordinates are less than T2 in fre- quency. These coordinates are small enough that we cannot add Laplacian noise to their frequencies without affecting the level sets they mapped to. Instead, we show that L1 sensitivity for the level set estimations is particularly small for the low frequency levels. Thus, for these frequency levels, report the size of the frequency levels rather than the identities of the heavy-hitters. We remark
5

---

that if our goal to just approximate the symmetric norms without preserving differential privacy, then it would suffice to just consider the high and medium frequency levels, since the low frequency levels are particularly problematic when Laplacian noise is added to the frequency vector. We also remark that we only use the thresholds Ti and 72 for the purposes of describing our algorithm in the actual implementation of the algorithm, the thresholds 7i and 72 will be implicitly defined by each of the substreams, We summarize our new approach in Figure 1.
High Level Sets
PRIVCOUNTSKETCH
Private coordinate magnitudes
Medium Level Sets
Subsampling
PRIVCOUNTSKETCH
Private level set sizes
Low Level Sets
Subsampling
Noisy level set sizes
Private level set sizes
Fig. Illustration of separate handling of the high, medium, and low level sets.
Private symmetric norm estimation in the streaming model. Although the previously discussed intuition builds towards a working algorithm, the main caveat is that far, we have mainly discussed the centralized model, where space is not restricted and so each coordinate and thus each level set size can be counted exactly. In the streaming model, we cannot explicitly track the frequency vector, or even the frequencies of a constant fraction of coordinates. Instead, to estimate the sizes of each level set, (Indyk & Woodruff, 2005; Blasiok et al., 2017) take the stream S and form s = O (log n) substreams S1, ......; S., where the j-th substream is created by sampling the universe of size n a rate of 2--1- Then Sj will only consist of the stream updates to the particular coordinates of x that are sampled. Thus in expectation, the frequency vector induced by S, will have sparsity 2/-1. Similarly, if a level set has size I;, then I of its members will be sampled in S, in expectation. It then be shown through variance argument that if level set is important, then there exists an explicit substream j from which Т; can be well-approximated using the Ly-heavy hitter algorithm COUNTSKETCH and result, the symmetric norm of can be well-approximated. The main point of the subsampling approach is that if there exists a level set with large size consisting of small coordinates, then the coordinates will not be detected by the COUNTŠKETCHI on S, but because Sj has significantly smaller L2 norm, then the coordinates will be detected by COUNTSKETCH on Sj.
However, adapting the subsampling and heave-hitter approach introduces additional challenges for privacy. For instance, we can analyze the Ly-heavy hitter algorithm COUNTSKETCH and show that although the In sensitivity of the estimated frequency for a single coordinate is small, the L sensitivity of the estimated frequency for all the coordinates is large. Instead, we use the view that COUNTSKETCH poly (1, L, log and then outputs only those estimates that are above a certain threshold. Sim- ilarly, the Laplacian noise added to privately use COUNTSKETCH can alter the sizes of significant number of level sets for small coordinates. Thus for the small coordinates (corresponding to the substreams Sy with large j), we invoke COUNTSKETCH with much higher accuracy, so that with high probability, it will return exactly the frequencies for the small coordinates. For example, note that if the frequency fi of a coordinate E [n] is at most z0 then any (1 + aappoopppooinnnoo to fu can be rounded to exactly recover fx. This decreases the L, sensitivity of the vector of estimated level set sizes, therefore allowing us to add Laplacian noise without greatly affecting the quality of approximation.
a composition function that first only estimates frequencies for the top
PRIVATE SYMMETRIC NORM ESTIMATION ALGORITHM
In this section, we give our algorithm that releases set of private statistics from which an arbi- trary number of symmetric norms be well-approximated. In particular, recall that it suffices to approximate the sizes of the important levels and identity the non-important levels, so that their contributions can be set to zero.

---

4.1 RECOVERY OF HIGH FREQUENCY LEVELS
As a warm-up, we describe our algorithm for recovering the high frequency levels, whose coor- dinates have sufficiently large magnitude and thus their frequencies can be well-approximated by running an Tz2- hitters algorithm on the stream S. Moreover, with high probability, adding Laplacian noise will not affect the level sets because the frequencies are so large. Thus it simply suffices to return the noisy estimated frequencies of each of the elements in the high frequency levels. This algorithm is the simplest of our cases and we give the algorithm in full in Algorithm
Algorithm Algorithm to privately estimate the high levels
Input: Privacy parameter >> O, accuracy parameter a E (0, 1)
Output: Private estimation of the frequencies of the coordinates of the high frequency levels 1: B + O mmme())" log" m) 3' + O
a
8=
log YI
2: Run PRIVCOUNTSKETCH on the stream with threshold a² and failure probability poly(m)
3: for each heavy-hitter E [n] reported by PRIVCOUNTSKETCH do
4: Let fi be the frequency estimated by PRIVCOUNTSKETCH
5: TK + Ik Lap B'e
6: return FR
We first show that coordinates in high frequency levels are identified and their frequencies are accu- rately estimated and similarly that if coordinate does not have high frequency, it will not be output by Algorithm 1.
Lemma 4.1. Suppose of 2
F2(z) and m aa 35532 Then with high probability, Algo- a=²
22llog m)
log m
rithm I outpuas Iy such that (1 (1-ol 11-o2pm yox S 3h S Tg. On the other hand if < 22log" F2(x)), then
a²
with high probability, Algorithm outputs Fy such that Fh <
3e² "llog m
F2(1)).
We now justify the privacy and space complexity of Algorithm 1.
Lemma 4.2. Algorithm is (q. 4) -differrret private for 8 poly(m) and uses space mmo 2
poly ( 2 1.logm) m).
4.2 RECOVERY OF MEDIUM FREQUENCY LEVELS
In this section, we describe our algorithm for recovering the medium frequency levels, whose co- ordinates do not have sufficiently large magnitude to be detected by rumning an Ly-heavy hitters algorithm on the stream S, but have sufficiently large size, so that there exists some j E [s] across the s subsampling levels such that the coordinates can be detected by running an Lz-heavy hitters algorithm on the stream Sj. On the other hand, their magnitudes are sufficiently large so that with high probability, adding Laplacian noise will not affect the level sets. We give the algorithm in full in Algorithm 2.
We first upper bound the second frequency moment (and hence the L2 norm) of each substream. This is necessary because want to detect the coordinates of the medium frequency levels as Le-heavy hitters for each substream, but if the substream has overwhelmingly large Le norm, then will not be able find coordinates of the medium frequency levels. However, it may not be true that F2())) is significantly smaller than F2(S) with high probability. For example, if there were a single large element, then the probability it is sampled at level s is 1. which is roughly 2
1 (m] Instead, we note that PRIVCOUNTSKETCH benefits from the stronger tail guarantee, which states that not only does PRIVCOUNTSKETCH with threshold 1/ 1 detect the elements k such that (fx)) 2 (S)) but it also detects the elements such that (fx)² 2 1/ (S where Stan(1/g) is the frequency vector f induced by S, with the largest " entries instead set to zero (Braverman et al., 2017: 2018a).
Lemma 4.3. With high probability, F(((E))1 < 200 log F2(x) for all [s].
7

---

Algorithm 2 Algorithm to privately estimate the medium levels
Input: Privacy parameter O, aceuracy parameter E (0,
Output: Private estimations of the sizes of the medium frequency levels
B O (mmo(() (mmo(L)" log m/ ).3²' +- O a²
log m E + (1 O (E))
2: 7 < (1/2,1) 1) uniformly at random, L < [loge (2m) 8 + (log
3: for E [s] with 2
log do
ffree
4: Form stream Sj by sampling elements of [r]] with probability 1
23
5: Run PRIVCOUNTSKETCUL, on stream Sj with threshold B' and failure probability
(mly
6:
for each heavy-hitter & [ni] reported by PRIVCOUNTSKETCH, do
Let F&k be the frequency estimated by PRIVCOUNTSKETCH 7:
8:
if T5k
log then Pon
9:
Tk LK Lap
3
10:
for [6] with
m 20
7
28 2
2
do
11:
Let by be the number of indices [n] such that 7621 S Fk g
12:
6. + [1) b
13:
return 6;
We now show that conditioned on the event that the Le norm of the subsampled streams not too large, then we can -pproxiate the frequency of any coordinate of the medium frequency levels, provided that they sampled in the substream.
Lemma 4.4. Suppose is a ß-important level and k E [n] is in level i, so that Ik E (5',5t+1 If F2((S))1/(a2 < 200 logm F2(x) for all j E [s], then ls is sampled in stream Sj with 2 > log n then with high probability, Algorithm 2 outputs Ty such that (1 a²) Jank S 36 S Kk-
D'ae'
Unfortunately, Lemma 4.4 only provides guarantees for the coordinates of the medium frequency levels that are sampled. Thus, we still need to use Lemma 4.4 to show that a good estimator to the sizes of the medium frequency levels can be obtained from the estimates of the coordinates of the medium frequency levels that are sampled. In particular, we show that rescaling the empirical sizes of the medium frequency levels forms good estimator to the actual sizes of the medium frequency levels.
Lemma 4.5. Consider 8-important level i with ş E integer j > and E > log
Fa(x)
log 2 for some
20222 Fa(a))
log
F'o5" If Fa((S))))(
200 1oo 2
F2(x) for all j [s), then
sampled in stream Sy with 2 >, then with high probability, Algorithu outputs by such that (1 (a)):: < 62 S bi. where by is the size of level i.
We now analyze the priavcy and the space complexity of Algorithm 2
Lemma 4.6. Algorithm is (5 4) -ddifffernttially private for 8 poly(m] and uses space mmc(L)
poly L E l)..
4.3 RECOVERY OF LOW FREQUENCY LEVELS
In this section, we describe our algorithm for recovering the low frequency levels, whose coordi- nates have magnitude small enough that we cannot add Laplacian noise to their frequencies without affecting the corresponding level set sizes. We instead report the sizes of the level sets for the low frequency levels rather than the identities and approximate frequencies of the heavy-hitters. Thus we must add Laplacian noise to the sizes of the level sets; we show that L1 sensitivity for the level set estimations is particularly small for the low frequency levels and thus the Laplacian noise does not greatly affect the estimates of the level set sizes. We note that this approach does not work for the high frequency levels because the high frequency levels may have small level set sizes, that
8

---

adding Laplacian noise to the sizes can significantly affect the resulting estimates of the level set sizes. Similarly, it is more challenging to argue the low L1 sensitivity for the level set estimations for the medium frequency levels. Hence, both the algorithm and analysis are especially well-catered to the low frequency levels. We give the algorithm in full in Algorithm
Algorithm Algorithm to privately estimate the low levels
Input: Privacy parameter O, accuracy parameter E (0, 1) Output: Private estimations of the sizes of the low frequency levels
B O mmmm 7.22
+0
O
E (1+ (s))
(.)ool))Flog"aa log"
log nt
2: 7 < (1/2, 1) uniformly at random, l < logg (2m) : t O (logn)
3: for E [s] with 2
I log do
B'ae
4:
Form stream Sj by sampling elements of [r] with probability 1/2
5: Run PRIVCOUNTSKETCH on stream Sj with threshold (8" ==
log
6: for each heavy-hitter
[n] reported by PRIVCOUNTSKETCHH,
7: Let 26 be the frequency estimated by PRIVCOUNTSKETCH
8:
for i E [C] with O
logn ('at
2 2/+1 > 7522 2 2 do
9:
Let 6g be the number indices E [n] such that 762h th S 3k < <
b. (+
(be + Lap Lap (9)
11: return 6;
We first show that the estimates of the level set sizes for the low frequency levels are accurate.
Lemma 4.7. Consider a 8-important level i with e²i E
=a²=²
Fa(x)
Sa²=² Fa(a))
21-1 for some
log"
2 log"
integer j > 0 and Ç < logn
If (a(((5))/((2)2)))
200 log m F2(x) for all E [s). then k 2
D'ae'
is sampled in stream Sy with 2 >, then with high probability, Algorithm 3 outputs b, such that O (a))b, b, S b,, where b; the size of level set i.
We then argue the privacy and space complexity of Algorithm 3. Lemma 4.8. Algorithm 3 is (5: 2) -differrentially private for poly(m] and uses space mmc( L)
poly + Eo log m).
4.4 PUTTING THINGS TOGETHER
We would like to combine the subroutines from the previous sections to output private dataset for symmetric norm estimation. Thus it remains to describe how to privately partition the co- ordinates into the high, medium, and low frequency levels. To that end, we remark that al- though PRIVCOUNTSKETen actually provides an estimated frequency for each coordinate, for our purposes, we only need estimated frequencies for the Le-heavy hitters and there are at most K = O possible Ly-heavy hitters with whichever threshold that choose, e.g., 1) 23 in Algorithm 1. Thus suffices to observe that we can privately partition the coordinates into the high, medium, and low frequency levels by first privately outputting the top K estimated frequencies and then partitioning the coordinates according to their noisy estimated frequencies, which can be viewed as proteeroc.s.ing. In particular, (Qiao et al., 2021) observes that it suffices add Laplacian noise with scale & to each of the frequencies and then outputting the top K noisy estimated fre- quencies to achieve -diifferential privacy. We now finally put together the results from the previous sections to show the following result. In particular, correctness follows from applying Lemma 2.7 to Lemma 4.1, Lemma 4.5, and Lemma 4.7, while privacy and the space complexity follow from Lemma 4.2, Lemma 4.6, and Lemma 4.8.
ns
Theorem 4.9. There exists a (c, -diffferreell private algorithm that outputs a set C, for 5 poly(m)) From C, the (1 + a)) appprxximmtiio any norm with maximum modulus of concentration at most M can be computed, with probability at least The algorithm uses M poly ( E loo m) bits of space.

---

REFERENCES
Aditya Akella, Ashwin Bharambe, Mike Reiter, and Srinivasan Seshan. Detecting ddos attacks on isp networks. In Proceedings of the Eventy-Second ACM SIGMOD/PODS Workshop on Manage- ment and Processing of Data Streams, pp. 1-3, 2003.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments, Comput. Syst. Sci., 58(1):137-147, 1999. 1,
Alexandr Andoni. High frequency moments via max-stability In 2017 IEEE International Confer- ence on Acoustics, Speech and Signal Processing, ICASSP, pp. 6364 6364-6368, 6368, 2017. 1
Andreas Argyriou, Rina Foygel, and Nathan Srebro. Sparse prediction with the k-support norm. In Advances in Neural Information Processing Systems 25: Annual Conference on Neural Informa- tion Processing Systems, pp. 1466-1474, 2012.
Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgammrr and Lin F. Yang. Streaming symmetric norms via measure concentration. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theeor of Computing, STOC, pp. 716-729, 2017. 3, 5,
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The johnson-lindenstraus transform itself preserves differential privacy. 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 410-419, 2012. 2,
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P. Woodruff. Bptree: An l2 heavy hitters algorithm using constant memory. In Proceedings of the Symposium on Principles of Database Systems, PODS, pp.
36th ACM SIGMOD-SIGACT-OO 361-376, 2017."
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters sliding windows. In Approximation, Random- ization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp- 7:1-7:22, 2018a.
Vladimir Braverman, Emanuele Viola, David Woodruff, and Lin F. Yang. Revisiting frequency moment estimation in random order streams. In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 25:1-25:14, 2018b.
Leo Breiman. Random forests. Machine learning, 45(1):5-32 32, 2001.
Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Judy Hanwen Shen, and Uthaipon Tantipongpipat. Fast and memory efficient differentially private-sgd via JL projections. CoRR, abs/2102.03013, 2021. 1,3
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theor Comput. Sci., 312(1):3 15, 2004.
Seung Geol Choi, Dana Dachman-Soue Soled, Mukul Kulkarni, and Arkady Yerukhimovich. Diffcreentially multi-party sketching for large-scale statistics. Proc. Priv. Enhancing Tech- nol., 2020(3):153 2020.
Graham Cormode, S. Muthukrishnan, and Irina Rozenbaum. Summarizing and mining inverse dis- tributions on data streams via dynamic inverse sampling. In Proceedings of the 31st International Conference on Very Large Data Bases, pp. 25-36, 2005. 1
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitiv- ity in private data analysis. Theory of Cryptography, Third Theory of Cryptography Conference, TCC, Proceedings, pp. 265-284, 2006.
Cristian Estan, George Varghese, and Mike Fisk. Bitmap algorithms for counting active flows high speed links. In Proceedings of the ACM SIGCOMM conference on Internet measurement, pp. 153-166, 2003.
10

---

Sheldon J. Finkelstein, Mario Schkolnick, and Paolo Tiberio. Physical database design for relational databases. ACM Trans. Database Syst., 13(1)911-128, 1988.
Sumit Ganguly, Taylor polynomial estimator for estimating frequency moments. Automata, Languages, and Programming 42nd International Colloquium, ICALP Proceedings, Part pp. 542-553, 2015.
Sumit Ganguly and David Woodruff. High probability frequency moment sketches. In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 58:1-58:15. 2018.
Corado Gini. Variabilità mutabilità. Reprinted in Memorie di metodologica statistica, 1912.
Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computa- tion. J. ACM, 53(3):307-323, 2006. 1,2
Piotr Indyk and Andrew McGregor. Declaring independence via the sketching of sketches. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 737-745. SIAM, 2008.
Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium Theory of Compuling, pp. 202- 208, 2005. 1,5,6 6
Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1161-1178, 2010. 3
Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff. Fast moment estimation in data streams in optimal space. In Proceedings of the 43rd ACM Symposium Theory of Computing, STOC, pp. 745-754, 2011.
Bo' az Klartag and Roman Vershynin. Small ball probability and dvoretzky's theorem. Israel Journal of Mathematics, 157(1):193-20) 2007.
Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen. Sketch-based change detection: Methods, evaluation, and applications. In Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, pp. 234-247, 2003. 1
Ping Li. Estimators and tail bounds for dimension reduction in la (0 < a S 2) using stable ran- dom projections. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 10-19, 2008 1
Yi Li and David P. Woodruff. A tight lower bound for high frequency moment estimation with small error. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 16th International Workshop, APPROX 2013, and 17th International Workshop. RANDOM. Proceedings, pp. 623-638, 2013. 3
Yi Li and David P. Woodruff. Input-sparsity low rank approximation in schatten norm. In Proceed- ings of the 37th International Conference on Machine Learning, ICMI., pp. 6001-6009, 2020.
Max Lorenz. Methods of measuring the concentration of wealth. Publications of the American statistical association, 9(70):209-21, 1905.
Andrew M. McDonald, Massimiliano Pontil, and Dimitris Stamos. Spectral k-support norm reg- ularization. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems, pp. 3644-3652, 2014.
Vitali D Milman and Gideon Schechtman. Asymptotic theory of finite dimensional normed spaces: Isoperimetric inequalities in riemannian manifolds, volume 1200. Springer, 2009.
Darakhshan J. Mir, S. Muthukrishnan. Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches. In Proceedings of the 30th ACM SIGMOD SIGMOD-SIGACTI SIGACT-SiGART Symposium Principles of Database Systems, PODS, pp. 37-48, 2011.
11

---

Christopher R Palmer, Georgos Siganos, Michalis Faloutsos, Christos Faloutsos, and Phillip B Gib- bons. The connectivity and fault-tolerance the internet topology, 2001.
Gang Qiao, Weijie J. Su, and Li Zhang. Oneshot differentially private top-k selection. In Proceed- ings of the 38th International Conference on Machine Learning, ICML, pp. 8672-8681, 2021.
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. Access path selection a relational database management system. Proceed- ings of the 1979 ACM SIGMOD International Conference Management of Dala, pp. 23-34, 1979.
Or Sheffet. Differentially private ordinary least squares. J. Priv. Confidentialiiyy 9(1), 2019.
Adam D. Smith, Shuang Song, and Abhradeep Thakurta. The flajolet-marti sketch itself preserves differential privacy: Private counting with minimal space. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurlPS, 2020. 2, 3
Mikkel Thorup and Yin Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. In Proceedings the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 615-624, 2004.
Lun Wang, losif Pinelis, and Dawn Song. Differentially private fractional frequency moments esti- mation with polylogarithmic space. arXiv preprint arXiv:2105. /2363, 2021. 2,
David Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. CoRR, abs/201 1.07471, 2020.
David P. Woodruff and Samson Zhou. Separations for estimating large frequency moments data streams. In 48th International Colloquium on Automata, Languages, and Programming, ICALP, volume 198, pp. 12:1-112:21, 2021. 1,3
Bin Wu, Chao Ding, Defeng Sun, and Kim-Chuan Toh. On the moreau-yosida regularization of the vector k-norm related functions. SIAM J. Optim., 24(2):766-794, 2014. 3
12


Reviews:
[{"review_id": "xTknPs8pBq", "reviewer": "Reviewer_a8eC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a general algorithmic framework for differentially privately releasing a number of sufficient statistics on a data stream. With the released statistics, all symmetric norms can be approximated simultaneously, which makes the algorithm especially suitable for a large number of queries.", "summary_of_the_review": " \nI found the idea of classifying and separately handling high, medium and low frequency levels novel and interesting. It makes sense to release approximate frequencies for the high frequency levels while release approximate level sizes for the light frequency levels for better utility. The theoretical analysis for the accuracy and privacy guarantee looks sound to me.", "strength_and_weaknesses": "I found the idea of classifying and separately handling high, medium and low frequency levels novel and interesting. It makes sense to release approximate frequencies for the high frequency levels while release approximate level sizes for the light frequency levels for better utility. The theoretical analysis for the accuracy and privacy guarantee looks sound to me.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ip8nXv5pq4A", "reviewer": "Reviewer_9ZLt", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a framework to release the family of symmetric norms with differential privacy. The mechanism permits (1+\\alpha)-approximation to each norm.", "summary_of_the_review": "This paper proposed a framework to release the family of symmetric norms with differential privacy.  However, some important details are missing or unclear.  I may have missed some crucial details.", "strength_and_weaknesses": "Strength: \nThe targeted problem is interesting. This paper provides many theoretical results.\n\nWeakness:\n1. In general, the manuscript is not very well written. I noticed a lot of typographical and grammatical errors that made reading and understanding the manuscript a bit difficult. This paper is not easy to follow. There are many technical phrases that lack sufficient explanations.\n2. No exact definition of (1+\\alpha)-approximation in the main manuscript.\n3. It would be better to provide PRICOUNTSKETCH instead of the sketching algorithms in Section 3.\n4. The level thresholds T_1 and T_2 to separate the data is important. Algorithm 1 gives some theoretical order of the thresholds. However, how to choose them numerically?\n5. There is no experimental evaluation of the proposed algorithms in this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dpccwgqE96F", "reviewer": "Reviewer_1krD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies preserving differential privacy in when releasing information of streaming models. The authors propose a new DP mechanism that can release a set of sufficient statistics which can be used to estimate any symmetric norm of the data. ", "summary_of_the_review": "I think this paper is novel and the results are significant. But the writing can be improved. ", "strength_and_weaknesses": "This paper studies a very important problem, i.e., releasing the norms of data while protecting the differential privacy in streaming cases. Previous work many focus on limited settings (i.e., p<1), while this paper proposes a universal mechanism which works for any symmetric norms with low space complexity. This idea for coordinate parathion to my knowledge is novel and very interesting. \n\nI have a hard time reading this paper. I think the following advices may be helpful:\n\n1.\tA more clear and detailed definition of the streaming model. Currently, it is not very clear to the readers what the exact streaming model is. The authors only mentioned the model with one sentence (“The simplest streaming model is perhaps the insertion-only model,…”). Is this the only model the authors study, or the model can be more general? \n\n2.\tThe preliminary should be put before Section 2, since many definitions of Section 3 are used in Section 2. \n\n3.\tIt would be great if the authors can add a related work section to compare with other work (especially smith et al., 2020, wang et al., 2021, blocki et al., 2012) and illustrate the differences. \n\n4.\t“We emphasize that prior to our work, there is no algorithm that can handle private symmetric norm estimation”I am not sure if it is an overclaim, since previous can handle the cases when p<1.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BNH1NBR5cKI", "reviewer": "Reviewer_DEcx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper claims that sufficient statistics can be generated from which a wide range f norm estimations can be differentially privately computed.", "summary_of_the_review": "The paper suggests a nice idea for which probably a proof exists, but the elaboration is insufficiently rigorous.", "strength_and_weaknesses": "Intuitively, the idea sounds very plausible to me, but the text is insufficiently rigorous for me to be able to follow the proof.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject