Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space
Authors: Lun Wang
Iosif Pinelis
Dawn Song
Venue: ICLR 2022 Poster (2022)
Keywords: Differential Privacy
Fractional Frequency Moments

Abstract: We prove that $\mathbb{F}_p$ sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when $p\in(0, 1]$. $\mathbb{F}_p$ sketch uses only polylogarithmic space, exponentially better than existing DP baselines and only worse than the optimal non-private baseline by a logarithmic factor. The evaluation shows that $\mathbb{F}_p$ sketch can achieve reasonable accuracy with strong privacy guarantees. The code for evaluation is included in the supplementary material.

Published as a conference paper at ICLR 2022
DIFFERENTIALLY PRIVATE FRACTIONAL FREQUENCY MOMENTS ESTIMATION WITH POLYLOGARITHMIC SPACE
Lun Wang UC Berkeley
losif Pinelis Michigan Tech i ipinel
Dawn Song
UC Berkeley
wanglunnberrkeley. edu
dawnsongêcs wwwpenn@@ss...eeeeeeeeee edu
ABSTRACT
We prove that F, sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when p (0, 1). F,, sketch uses only polylogarithnic space, exponentially better than existing DP baselines and only worse than the optimal non-private baseline by logarithmic factor. The evaluation shows that F, sketch can achieve reasonable accuracy with differential privacy guarantee. The evaluation code is included in the supplementary material.
INTRODUCTION
Counting is one of the most fundamental operations in almost every area of computer science. typically refers to estimating the cardinality (the 0th frequency moment) of a given set. However, counting can actually refer the process of estimating a broader class of statisties, namely p" frequency moment, denoted Fp. Frequency moments estimation is at the core of various important statistical problems. Fj is used for data mining (Cormode et al. 2005) and hypothesis tests (Indyk & McCrregor 2008). F2 has applications in calculating Gini index (oorenz 1905 Gini 1912)
and surprise index (Good. 1989), training random forests (Breiman (201)) numerical linear alge-
bra (Clarkson & Woodruff 2009 Sarlos 2006) and network anomaly detection (Krishnamurthy
et al. 20033 Thorup & Zhang 2004). Fractional frequency moments are used in Shannon entropy
estimation Harvey et al.
2008 Zhao al. 2007) and image decomposition (Geiger et al. 1999).
Non-private frequency moments estimation is systematically studied in the data streaming
model (Alon al.) [1999] Charikar et al., 2002 Thorup & Zhang, 2004 Feigenbaum et al. 2002
Indyk 2006; Li| 2008) Kane et al. 2010: Nelson & Woodruff, 2009 2010; Kane et al. 2011 1).
This model assumes extremely limited storage such as network routers. The optimal non-prin non-private
algorithm (Kane et al., I) uses only polylogarithmic space to maintain frequency moments. In the present work, we inherit the low space complexity requirement for the versatility of the algorithm.
The data being counted sometimes contains sensitive information. For example, to calculate Gini index, the data should contain pairs of ID and income. Frequency moments of such data, if published. might leak sensitive information. To mitigate, the gold standard of differential privacy (DP) should be applied. Special cases of DP frequency moments estimation such as p 0, 1, are well-studied in wide spectrum of works (Choi et al.] 2020 Smith et al., 20200 Blocki et al.) 2012 Sheffer 2017 Upadhyay 2014, Choi et al. 2020 Bu et al. 2021 Mir et al. (011)).
In the present work, we make the first customized effort towards DP estimation of fractional frequency moments, i.e, p E (0, with low space complexity. We show that a well-known streaming algorithm, namely F, sketch (Indyk 2006), preserves differential privacy is. With its small space complexity, F, sketch elegantly solves the trilemma between efficiency, accuracy, and privacy.
Problem Formulation. We use bold lowercase letters to denote vectors (e.g. a, b, e) and bold uppercase letters to denote matrices (e.g. A, B, C). (1,...,7 .n) denoted by [n].
Let S ((ki, -. (kn, vn)) } (n > 1) be stream of key-value pairs where h; E [m]] (m > 2). 0 E [M] (M 2 1
We would like to design a randomized mechanism M that estimates the pt
"In main text. we consider the cash register model where each update vs 2 0. The result can be extended to the striet turnstile model as shown in Appendix A

---

Published as a conference paper at ICLR 2022
frequency moment:
Pa(S) =
likk = k)
k=
1=1
for p E (0, 1] where is an indicator function returning 1 if k = kÚ and O otherwise.
To provide rigorous privacy guarantee, M should preserve differential privacy as defined below. In our setting, neighboring data streams differ in one key-value pair.
Definition ((c, 6) Differreet Privacy). A randomized algorithm M is said to preserve (e. for two neighboring datasets S,S' and any measurable subset of the output space
P[M(S) E 8) & ePP(M(S') E 8) +
When 8 = 0, we omit it and denote the privacy guarantee as e-DP.
Oftentimes, n. is large (e.g. IP streams routers) so M should take polylogarithmic space in terms of n, m.
Proof Intuition. We summarize the intuition behind the proof that IF sketch is differentially private when p E (0, 1]. Recall that when proving DP for traditional mechanisms such as the Gaussian
mechanism, the core is to upper-bound the ratio
Q(z) where P(z) and Q(x) are the probability
P(z)
density functions of outputs when the inputs are neighboring datasets. In the proof of Gaussian
mechanism, P(x) and (x) can be viewed as a horizontal translation of each other and the distance between their mean values the sensitivity of the output.
For Fp. however, neighboring inputs do not translate the output distribution but instead change its scale. For example, when p 2, P(r) and (xx) are Gaussian distributions with the same mean and different variance. Inspired by the analogy to Gaussian mechanism, we need to address the below two questions to prove differential privacy for F, sketches
QI. How to bound the difference between the scales of P(z)) and Q(z)?
Q2. How to bound the ratio between the density functions of P(x)) and Q(z)?
To answer QI, we propose a new sensitivity definition called pure multiplicative sensitivity. Pure multiplicative sensitivity depicts the maximal multiplicative change in the output when the inputs neighboring datasets. We analyze frequency moments estimation and find that its pure multiplicative sensitivity approximately max{22 2 2p) when p E (0, 1] and > M.
To answer Q2, we first analyze the special case of p 1. When p = 1, P(r)
Q()) is rigorously upper-
bounded and thus F, sketch preserves e-DP. By analogy. we conjecture that Ep.P E (0. 1] also satisfies similar properties, which doubly confirmed by the numerically simulated plots Figure The conjecture is formally proved in Theorem 3
RELATED WORK
Frequency moments estimation is thoroughly studied the data streaming model. Alon et al. (1999) proposed the first space-efficient algorithm for estimating nd frequency moments when p is integer. Indyk 2006) extended the use case from integer moments to fractional moments using stable distributions. line of following works improve Indyk's algorithm in various aspects such as space
complexity (Kane et al. 2010 Nelson & Woodruff 2009). time complexity (Nelson & Woodruff
2010
Kane al. 2011) or accuracy [Li 2008 2009).
Several special cases in private frequency moments estimation such as 0, 1,2 were also well studied, Choi et al. (2020) and [Smith et al. (2020) studied differentially private Fo estimation. They separately proved that the Plajolet-Martin sketch is differentially private as is. Several independent works (Blocki et al. 2012 Sheffet (2077] [Upadhyay] 22144] Choi et al. 2020 Bu et al. 202T) studied the differential privacy guarantee in the special case p 2 under the name of Johnson-Lindenstran projection.
On the other hand, there is harely any prior work focusing on differentially private fractional frequency moments estimation. Differentially private distribution estimation algorithms (Acs et al. 2012 Xu

---

Published as a conference paper at ICLR 2022
al. 2013; Bassily Smith 2015; Suresh 2019; Wang et al., 2019) can used provide
differentially private estimation of fractional frequency moments. However, they are overkill as their outputs contain much more information than the queried fractional frequency moment. They only provide sub-optimal privacy-utility trade-off and are exponentially worse in terms of space complexity.
Datar al. (2004) considered similar (but not the same) mathematical problem to the present work when designing a locality-sensitiee hashing scheme. However, their analysis focuses on the simple cases when p and 2 and totally depends numerical analysis for p (0, 1).
DIFFERENTIALLY PRIVATE FREQUENCY MOMENTS ESTIMATION
In this section, we first revisit Fp sketch and then prove the differential privacy guarantee for F, sketch step by step. Different from most differential privacy analyses based on additive sensitivity, proof depends on a variant of the multiplicative sensitivity (Dwork et al. 2015) called pure multiplicative sensitivity. We give the first analysis of pure multiplicative sensitivity for p-th frequency moments. Then we motivate the differential privacy proof using a special case when the general proof that F, sketch preserves differential privacy. The main challenge stems from the fact that the density functions of p-stable distributions have no close-form expressions when p E (0, 1).
1. Finally we proceed
3.1 REVISITING P SKETCH
For completeness, we revisit the well-celebrated F, sketch by Indyk (206)) (also known as stable projection or compressed counting). We first introduce p-stable distribution, the basic building block in F, sketch. Then we review how to construct and query F, sketch using stable distributions.
Definition (p-stable distribution). random variable X follows 8-skewed p-stable distribution if its characteristic function is
(x cxp((c((pPP - 111Bsgg[[ tan TP ) 2
where -1 -1 8 is the skewness parameter, < > the scale parameter to the pt power.
In this paper, we focus on stable distributions with B 0, namely symmetric stable distributions. We denote symmetric p-stable distribution by 'Dp.c= and slightly abuse the notation to denote the density function as (x)) Note that the density function is the inverse Fourier transform of the characteristic function.
(p.(
2T cos (at)
2T
two independent random variables X,, X2 Dp.1, then C,X, + C2X2 ~ D Dp.oT +cp. We refer to this property as p-stability. Fp sketch leverages the p-stability of these distributions keep track of the frequency moments.
The pseudo-code for vanilla F, sketch is presented in Algorithm I
To construct, sketch of size initialized to all zeros and projection matrix P sampled from rxx (line 2). For each incoming p.1 key- value pair (k; 1;), we multiply the one-hot encoding k; scaled by v; with the projection matrix P and add it to the sketch (line 4).
a
x U.Ck.
=
Σ k=
P
Uy De)ek ~ DT.,
k =

---

Published as a conference paper at ICLR 2022
To query the sketch, we estimate Ç from using various estimators such as median, inter-quantile, geometric mean or harmonic mean suggested by Indyk 2006), L. (2008) and Li (2009).
Algorithm 1: F sketch.
Input :ata stream: S = {(Kk) (1),, (kis vn))
Construct:
Initialize [0]", DrX
Update:
for i E [x)] do Let eke be the one-hot encoder of k; P 0.e::
Query:
return scale_ caale_ssimattr(a))
3.2 PURE MULTIPLICATIVE SENSITIVITY OF FREQUENCY MOMENTS ESTIMATION
As we will see in the following two subsections, the differential privacy proof for FP sketch depends on the pure multiplicative sensitivity of p-th frequency moments. As the first step, give the definition pure multiplicative differential privacy. "Pure" is to distinguish from multiplicative sensitivity defined in Dwork al. (2015).
Definition (Pure multiplicatiie sensitivity). The multiplicative sensitivity of a function M is defined as the maximum ratio between outputs on neighboring inputs S and S'.
M(S)
Pp(n)
sup [S|=n.] (S,)))
M(S')
We might omit the subscript and argument when they are clear from the context.
The pure multiplicative sensitivity of F, is as below.
Theorem (Multiplicative sensitivity of F2). mechanism M which calculates Fp.P (0, 1] has pure multiplicative sensitivity upper bounded by
1 M
Pp 2
2p
+ (m 1)
Proof for Theorem] 7 Theorem giies an upper bound the multiplicative change when two input datasets with the same size m differ in one entry. To prove, we first consider a slightly different setting when the second dataset is generated by adding an entry to the first dataset. Then the neighboring datasets in the original setting can be generated by adding different entries to the same dataset. Thus, taking the division of the upper and lower bound of the sensitivity in the incremental setting will give an upper bound for sensitivity in the original setting.
Concretely, let u {ur,... Um)) where nn > O, E d; = 8, 2 We would like find both upper and lower bounds for the below expression.
Σ
m 2
u
+
(u
(u
+
Vp (0,
(1)
To bound expression T we first observe the following two inequalities 2 and 3
2,.bc.dd0.a32 b. d, a a+c <
b+c
(2)
a d b b d
m
Vp (0, 1),
P
w
(3)
Inequality can be proved with simple algebra. The left-hand-side of inequality
follows
because Σ uf is concave in (u,,..., Un) in the simplex defined by the conditions u,
0 for all
4

---

Published as a conference paper at ICLR 2022
i, and Σn Wy 8 and hence the minimum of th u on the simplex is attained a vertex of the simplex. The night-handdside of inequality (3) is an instance of the well-known generalized mean inequality (Sýkora 2009) or Hölder inequality (Hölder 1889).
First, let's upper bound expression IT. According to inequality (2) and (3)
Ee up + (u1 + A)P (2)+(3) E uh. + up
EE u4)p + (#1 + A)P
(8-11) + (u1 + A)
(3) S 2 21- A
S
L= u P + up
(s u1 ) uh
Similarly, to lower bound expression
Σ uh (u1 + A) (2)+(3) (m 1) 1 EE Uz) + (u1 A)
Di=2 ut + up
(m - 1)1 1 U. 8 + up
(s u2) + ((m 1) (nj + +)))
(s -1) + ((m - 1) x U1)
(3)
2 20-1 (mm- 1) " 1)u + s + (m 1) " A A
((m 1) == x 1)u1 +
2 2 2-21-pp (1+ (m 1)
5
Taking the division between the supremum and the infimum, we get
M (m
n1 + M
Pp S 20
22-20
n 1-1+ (m - 1) p-1
s
In typical streaming model where m is large and >> M, Pp ~ 22-2p < 4. To get better sense of how changes with p. we plot several curves with different hyper-parameter in Figure | Note that the pure multiplicative sensitivity only depends n, m, M and p which public information.
0.1
0.2
te me2 M-1
U.S 0.4
Muitplicative Senstiveyy
m-203,
me22 M-20
0.S--..p
0.G
m=320 M
5-240
m=240 M
5
10
10
20
0.2
0.4
0.6
0.8
(p) with different values of p E (0, 1] on Rt. The negative half is symmetric.
Figure/ 2: The curves of De.(())
Figure 1: Pure multiplicative sensitivity.
3.3 DIFFERENTIALLY PRIVATE Fj SKETCH
Instead of directly diving into the complete analysis, we first motivate the analysis with the special case p 1. In this case, the symmetric 1 "t-stable distribution is the well-known Cauchy distribution: (1.(()) = マ.... and thus the analyses are significantly simplified. The main purpose of this section is to pave the way for the proof of general F, sketch.
Theorem (e-DP for FF sketch). Let #I represent the multiplicative sensitivity of the first frequency moments. When the size of the sketch r = 1, IF is In p1-differentially private.
Proof for Theorem 2
Di. (w)
p1(Ff+22) is decreasing function of x when x E (0, 00)
F+
Di F. (x)
because its derivative
2(p (F +22]2
21
possiiieeeve Thus,
1 D1.F((20))
5 (T) <
DI.F, (0)
P1 D Di
Pi DimpF(()) D FL (0)

---

Published as a conference paper at ICLR 2022
Then, for any data stream S and arbitrary measurable subset 8,
/ (z)) ./=- D ()))(()(()) (s (x) (1)))
P[F((S) E s)
DEE
| (D)) = en P P (S") E s]
$
3.4 DIFFERENTALLY PRIVATE F SKETCHI (0,
The example of F, being e-DP indicates the possibility that Fp might have similar property when p E (0, 1J. To validate, plot the curves for different values of ps as shown in Figure 2 From the figure we can tell that when p E (0, 1]. the ratio 2p.((x) seems to he well-bounded and preserve c-DP.
2p)((z)
We now prove the conjecture as formalized in Theorem 3
Theorem 3 (e-DP for Algorithm[] D. Let Pp represent the multiplicatiie sensitivity the p-th frequecy moments, When and E (0, 1), Fp sketch (Algorithm 1 is 1 In Pp-differentially private.
Proof for Theorem 3
To prove Theorem
we prove the following inequality.
(x.
Pp < Pp S Dp.pp.p,.))
S pp
We first prove the right-hand-side of the inequality. Observe that 2x) = ?
c +xt) 2x
= 2n Ja cos(xt) exp(- -Dpc where * substitutes
with using integration by substitution. Thus,
DM.F( Pp. (2) P
DF. S Pb Dy.pFF F, (0) Pb Dp. (z)
Dr.F, (0)
as Pp,1 is increasing on (-00,0) 0] and decreasing on [0, oo), and Pp 2 1. To prove the left-hand-side of the inequality, we reorganize it into the format of Fourier transform.
Lx (pp exp((=FFFtt - ssp(-ppF,tt)) cos(tt)) dt 2 0
It suffices to show that
h(p) exp(- exp(-pPft)) cos(tx)dt
P
is decreasing. Taking the first derivative of h, we have
Ōh 1 / g(t) dts where g(t) = exp(-pF,,) (pF + +1) p² Jo
0p
According to Pólya criterion (Gneiting] 2001), it suffices to show that is positive definite. We first observe that the function 0 S + (1 + ee wt// is the Laplace transform Schiffi 1999) e- 11((t)
of the positive function 0 / 4/a 15/2 (the proof is deferred to the end) and hence mixture
of exponential functions 0 < ト ccu with > 0. Thus with variable substitution, the function + (1 + es|P)e-|+l -1s1" a mixture of functions s + -ds1a with e 0, which are positive definite for any p E (0, 1] as they are characteristic functions of stable distributions.
The last step is to prove the function F(u) (1 u w-/2)e--" w//2 - 2 0 is the Laplace trans- 1l(At)
form of ft) 15/2 > F(u) 10 f(t)e- "ddt dt, 2 0. Let R(u) F(u) and
L(u) = S0 f(t)e ut dt. We observe that lim L(x) = lim R(x) = limg-+x L'(x) =

---

Published as a conference paper at ICLR 2022
oo (x) so enough to show that [²(u)= R² Ru) enough to show
After a simple rescaling, is
J(a) /- exp
{ -
dt
Vi Vv Va
al
2vt
where a > as both sides do not contain linear terms. Using substitutions t u² and then L/(ava), we get
í(a) /
exp {
1 u2 au au²) du du [==KK(a/aaa
where (aa) = So exp ax²
11 de x..
Note that K'(a) Ja(a) and K(a) J(a)aā. So.
we get the differential equation J'(a) - 21) J(a), whose general solution is given by (a)= fo e -2 for a constant c. To determine c, note that K K(a) = J(a) = So exp -
an? du vā = J0 exp ( y² x²) dy and c K(0+) = Jo -xp dy = v= 2
3.5 PRIVACY AMPLIFICATION BY SUB-LAMPLING
30
The last step of Algorithm estimates given samples from the stable distributions. There are many candidate es- timators such as the geometric estimator and the harmonic estimator LLi 2008 2009). These estimators typically, suggested in (2008). require at least r 2 50 samples to give accurate estimation of Ç. However, the privacy parameter e grows linearly with r with trivial composi- tion (Dwork et al. 2006), which might result in weak privacy protection.
20
0.2
0.4
To address, follow the standard approach, amplifying privacy using sub-sampling. Different from Algorithm each input has probability q to be inserted into each di- mension of
Figure 3: Privacy budget E vs. p. n
2 220 M 2
presented in Algorithm 2 If we take
q = e then the privacy parameters Theorem hold as is. The proof a simple application of the composition theorems (Dwork et al. (006) and privacy amplification (Balle et al. 2018).
Theorem 4 (c-DP for Algorithm D.. Lel represent the multiplicative sensitivity of the p-th frequency moments, When p (0, 1). F. sketch with sub- samplinm rate q qr In Pp differenntill private.
Algorithm 2: Fp sketch with sub-sampling. The only change appears in line 3-4 and 7, corre- sponding to line 3 and 5 in Algorithm Bernoulligg) refers to Bernoulli distribution with success probability q.
Input :Data stream: S ((ki,v)) Un)) Construction
Initialize a = { ~~ Drxm; for i E [n] do
p.1
b Bernoulli(q):
Let ex, be the one-hot encoder of k; a = -a x buiek
Query
return scale_estimator(a)/r
3.6 UTILITY ALGORITHME 2
We depict the accuracy of a F, estimator with a pair of parameters (7, 17). Definition ((75 randomized algorithm M is said to be (7, -cccuurte if
(1 - (),()) & M(S) S (1+ w.p. 1-n
7

---

Published as a conference paper at ICLR 2022
Algorithm 2 satisfies the following utility guarantee. The space complexity only worse than the optimal non-private algorithm (Kane et al., (011)) by logarithmic factor. The accuracy bound is also a worst-case bound and the performance practice typically much better (Section
Theorem 5 (Utilitty of Algorithm 2). Vp E (0, 1] and E (0, 1), Algorithm is (++
92 1P-9ap -1-
A)-accurate if ( -2 log( ;,) In this case, Algorithm 2 uses ( log (mM (rT)) log( log( H,
bits.
Proof. Let SAg represent the sub-sampling process and F represent a Fp sketch with length r. Then Algorithm can be represented F7 SA, where represents composition of mechanisms.
First, we need the accuracy of Fp sketch. According to Theorem 4 of Indyk (2006), we fix the sub-sampled items,
PIIEE 1 (1 2 (n)(
F S 7F% (A)( 2 11-1 1
Second, we need the accuracy of the sub-sampling process. The expectation and variance of the sub-sampling process is as follow.
E SA(S)) (FF((())
(4)
VIE, o SA(S)] E[F, SA((S)) - - (
(5)
S F)() x F (S((S)) - (2PF9( = =(p -p))
According to Chebyshev's inequality,
q" q2P 2 1-
P[[Fp SA((S) - -"
Combining
( and 66) get Theorem 5
4 EVALUATION
4.1
EVALUATION SETUP
Multiplicative Ervor ?
0.23
0.5 1.0
045
0.5
0-25---
Multiplicative Error
075
1.0
0.6
0.3
0.4
0.2
0.2
0.1
0
104
10a
106
107
104
10a
10
107
Stream Size
Stream Size n
Uniformly Distributed Stream.
Binomially Distributed Stream.
Figure 4: Results on Synthetic Data.
As would like empirically understand F, sketch's 's trade-off between space, error and privacy, evaluate FP with E (0.25, 0.5, 0.75, 1} using synthetic streams of different sizes and distributions. We also evaluate F, with p E {0.05, 0.1, o. 0.95, 1} on real-world data. All the experiments were run on a Ubuntu 8.04 LTS server with 32 AMD Opteron(TM) Processor 6212 with 512GB RAM.
Synthetic Data. We first evaluate F, sketches using synthetic data. We synthesize two kinds of data: the key domain is either uniformly or binomially distributed. The value domain is (1) by default. The size of the key domain is 1000.

---

Published as a conference paper at ICLR 2022
Real-world Data. We also evaluate Fp sketches using real- wol-w application usage data (Ye et al. 2019) collected by TalkingData SDK. There are more than 30 million events in this dataset, each representing one access to the Tat SDK. We view the event type as the key and the value set to I by default.
4.2 EVALUATION RESULTS
In this section, we present the evaluation results. To avoid the inffuence of outliers, we report the median and interquartile of 100 runs for each data point except for the real-data evaluation. For all the evaluation, the sketch size is 50 as suggested in Li (2088) The sub-sampling rate in all the experiments is 0.02.
Synthetic Data. The evaluation results synthetic data are presented in Figure For uniformly distributed data, we observe that as the stream size increases, the multiplicative error decreases. We conjecture the reason to be the effect of sub-sampling. Concretely, each bin in the value domain has to get enough samples to approximate the behavior of the true distribution. On the other hand, when the data is binomially distributed, the multiplicative error is relatively stable with small fluctuation. We conjecture the reason is that as binomial distribution is more concentrated, the sample complexity is smaller than uniform distribution. Besides, for uniformly distributed data, ps close to have relatively large errors while the errors when is close to 1 are small. The reason is that the further is from 1, the larger the influence of sub-sampling.
= 1.1
p p= 1.9
p= 1.95
p= 1.99
Multppicative Error y
0.8
0.6
0.4
0.5
0.2
10a
10
10a
10a
0-
P
0.4
0.6
0.8
(2)2(()) with different values of E (1, on Rt The negative half is symmetric. The x-axis is log-scale to highlight the complex monotone trends.
Figure 6: The curves of (w)
Figure 5: Results on Real-world Data.
Real-world Data. The evaluation results for real-world data are presented in Figure We sampled 100,0000 data points from the dataset and the key has a domain of size 1488095. Each data point is the median of runs. We observe that the further p from 1, the higher the multiplicative error. This conforms with our observation in the evaluation synthetic data.
5 CONCLUSION & FUTURE WORK
This paper takes an important step towards narrowing the gap of space complexity between private and non-private frequency moments estimation algorithms. We prove that F, differentially private as is when (0, 1] and thus give the first differentially private frequency estimation protocol with polylogarithmic space complexity.
At the same time, we observe several open challenges. First, the proof does not easily extend to p 2). Figure 6 exhibits the complexity of monocity of Py.i(a)
(a) when p (1, The most complex curve when p = 1.99 composed of three monotonic parts in the figure. Hence, an interesting next step is fully understand the monotonicity pattern of the ratio curve when p (1,2) and get corresponding privacy parameters. Second, the space complexity of Algorithm /iss still worse than the optimal non-private algorithm by factor of log(m). It interesting check whether the optimal algorithm (Kane et al. 2011) also preserves differential privacy.

---

Published as a conference paper at ICLR 2022
Ethics Statement. Our work study the intrinsic differential privacy of Fp sketches. Pp sketches should be used with careful calibration to make sure the output is accurate and provides reasonable privacy guarantee. All the datasets and packages used are open-sourced.
REFERENCES
Gergely Acs, Claude Castelluccia, and Rui Chen. Differentially private histogram publishing through lossy compression. In 2012 IEEE 12th International Conference on Data Mining, pp- 1-10. IEEE, 2012.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. arXiv preprint arXiv: / 2018.
Raef Bassily and Adam Smith. Local, private, efficient protocols for succinet histograms. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 127-135, 2015.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The johnson-lindenstraus transform itself preserves differential privacy. In 2012 IEEE 53rd Anmual Symposium on Foundations of Computer Science, pp. 410-419. IEFE, 2012.
Leo Breiman. Random forests. Machine learning, 45(1):5-33 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. arXiv preprint ar arXiv:2102.000 03013, 2021.
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding fireuuett items in data streams. In International Colloquium on Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Seung Geol Choi, Dana Baachman-Solede Mukul Kulkarni, and Arkady Yerukhimovich. Diffcrentially- private multi-party sketching for large-scale statistics. Proceedings Privacy Enhancing Tech- nologies, 2020(3):153-)
2020.
Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 205-214, 2009.
Graham Cormode, Muthukrishnan, and Irina Rozenbaum. Summarizing and mining inverse distributions on data streams via dynamic inverse sampling. In VLDB, volume 5, pp. 25-36, 2005.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality- hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pp. 253-262, 2004.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory cryptography conference, pp. 265-2666220 284. Springer, 2006.
Cynthia Dwork, Weijie Su, and Li Zhang. Private false discovery rate control. arXiv preprint arXiv:1511.03803 2015.
Joan Feigenbaum. Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. An approximate I I-difference algorithm for massive data streams. SIAM Journal on Computing, 3111)113 2002.
Davi Geiger, Tyng-Luh Liu, and Michael Donahue. Sparse representations for image decompositions. International Journal of Computer Vision, 3392)1139-156, 1999.
Corrado Gini. Variabilità mutabilità. Reprinted in Memorie di metodologica statistica (Ed. Pizetti E, 1912.
10

---

Published as a conference paper at ICLR 2022
Tilmann Gneiting. Criteria of päglya type for radial positive definite functions. Proceedings of the American Mathematical Sociery, (29(8)23309-233 2318, 2001.
IJ Good. C332. surprise indexes and p-values. 1989.
Nicholas JA Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 489-498. IEEE, 2008.
Otto Hölder. Ueber einen mittelwerthabsatz. Nachrichten von der Königl. Gesellschaft der Wis- senschaften und der Aecorg-Arguuuss-Uniivrrrrttt zu Göttingen, 1889:38-47, 1889.
Piotr Indyk. Stable distributions, pseudorandom generators, emheddings, and data stream computation. Journal of the ACM (JACM), 53(3):307-323, 2006.
Piotr Indyk and Andrew McGregor. Declaring independence via the sketching of sketches. In SODA, volume 8, pp. 737-745, 2008.
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 Discrete Algorithms, pp. 1161-1178. SIAM, 2010.
Daniel M Kane, Jelani Nelson, Ely Porat, and David P Woodruff. Fast moment estimation in data streams optimal space. In Proceedings of the forty-third annual ACM symposium Theory of computing, pp. 745-754 2011.
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.
Ping Li. Estimators and tail bounds for dimension reduction in &a (0 < 2) using stable random projections. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 10-19, 2008
Ping Li. Compressed counting. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithmss, pp. 412-42 22142. SIAM, 2009.
Max O Lorenz. Methods of measuring the concentration of wealth. Publications of the American statistical association, 9770)209-219, 1905.
Darakhshan Mir, Shan Muthukrishnan, Aleksandar Nikolov, and Rebecca N Wright. Pan-private algorithms via statistics on sketches. In Proceedings of the thirtieth ACM SIGMOD-SIGACT. SIGART symposium on Principles of database systems, pp. 37-48, 2011.
Jelani Nelson and David P Woodruff. A near-optimal algorithm for I1-difference. arXiv preprint arXiv:0904.2027. 2009.
Jelani Nelson and David P Woodruff. Fast manhattan sketches data streams. In Proceedings of the /wenty-ninth ACM SIGMOD-SIGACT-SIGART symposs Principles of database systems, pp. 99-110, 2010.
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 06)), pp. (43-152. IEEE, 2006.
Joel L Schiff. The Laplace transform: theory and applications. Springer Science & Business Media, 1999.
Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pp. 3105-3114, PMLR, 2017.
Adam Smith, Shuang Song, and Abhradeep Thakurta. The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. Advances in Neural Information Processing Systems, 33, 2020.
11

---

Published as a conference paper at ICLR 2022
Ananda Theertha Suresh. arXiv:/910.03553, 2019.
Differentially private anonymized histograms.
arXiv preprint
Stanislav Sykora. Mathematical Means and Averages: Basic Properties. PhD thesis, Ed. S. Sykora, 2009.
Mikkel Thorup and Yin Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. In SODA, volume 4, pp. 615-624, 2004.
Jalaj Upadhyay. Differentially private linear algebra in the streaming model. arXiv preprint arXiv: 1409. 5444, 2014.
Tianhao Wang, Milan Zwakknber Zitao Li, Boris Skoric, and Ninghui Li. Locally differentially private frequency estimation with consistency. arXiv preprint arXiv:I90S. 0900000320, 2019.
Jia Xu, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, Ge Yu, and Marianne Winslett. Differentially private histogram publication. The VLDB Journal, 22(6))797-822, 2013.
Qingqing Ye, Haibo Hu, Xiaofeng Meng, and Huadi Zheng, Privkv: Key-value data collection with local differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 317-331. IEEE, 2019.
Haiquan Zhao, Ashwin Lall, Mitsunori Ogihara, Oliver Spatscheck, Jia Wang, and Jun Xu. A data streaming algorithm for estimating entropies of od flows. In Proceedings of the 7th ACM SIGCOMM conference Internet measurement, pp. 209-299, 2007.
12

---

Published as a conference paper at ICLR 2022
A PURE MULTIPLICATIVE SENSITIVITY IN STRICT TURNSTILE MODEL
In this section, derive the pure multiplicative sensitivity of Fp in the strict turnstile model. In the strict tumstile model, for a key-value stream S = {(k 01). ... (ka 2,) (n 2 1) where & E [m]] (m 2 2), f-M,.-. M) (M 1), the sum of of the same key should always be non-negative:
Σ I(k: k)u; 20
Besides, for the utility of the result, we need to assume that M <n-l,
Theorem (Multiplicative sensitivity of Fp in strict turnstile model). A mechanism M < nt - 1 which calculates Fp.P (0, 1] in the strict turnstile model when has pure multiplicative sensitivity upper bounded by
2M
0% s 2 2p (1+
2-2222
P
M
Proof for Theorem 0 derived by taking the division of the upper and lower bound in the incremental setting following the same logic as the proof for Theorem [ The upper bound is the same as in the proof of Theorem 6 so we only need calculate the lower bound of the following expression.
An upper bound for the sensitivity of Fp in the strict turnstile model can be
First, we observe the following two inequalities.
atc btc
b+ d'
Σ i= up + (m1 A)P (8)+(7)
( Li=z uz) (ni A)
E uf +ep
EI u + up
u ) (ul A)P
(s U1 12 + up
2 (1
Taking the division between the supremum and the infimum, we get
2A
2M
PSt S 22- 21
22 2p-2p(1
n n M
As shown in Figure 7 when m is the same, the sensitivity is very close to the sensitivity in the cash register model if M
Pure Multiplicative Sensitivity
n=2 m= M=1
4
15 m=
M=2
n=215 m= M=210
3
2
0.2
0.4
0.6
0.8
p
Figure 7: Pure multiplicative sensitivity in the Striet Turnstile Model.
13


Reviews:
[{"review_id": "zgzPvZk7DB1", "reviewer": "Reviewer_PGRe", "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": "The following are the strengths of the paper:\n\n(+) The paper presents a solid theoretical result for a very (at least mathematically) natural problem.\n\n(+) The paper shows that an existing algorithm for the frequency moment problem in the data stream literature is also \\eps-DP. This is really nice since it shows that an existing algorithm is more powerful than what was already known.\n\n(+) It seems like the notion of pure multiplicative sensitivity is new or perhaps more accurately not that well explored in the DP literature.\n\nThe main weakness of the paper are mostly from motivational/presentation for me:\n\n(-) The paper starts off with some applications of p'th moment for p=1 and p=2 but from what I can tell there are no applications given for p\\in (0,1), which is the range where the results in the paper are new. While it is mathematically natural to study the DP of this problem, one thing missing is to show (if possible) what _potential_ practical applications exists from having an \\eps-DP algo for computing the p-th frequency moments for p\\in (0,1).\n\n(-) It would be useful to have a sense for why proving the results in the paper are hard? Or put another way what are the new technical ideas that are unique to this paper that was not present before that prevented previous works to solve the current problem? The paper states that the notion of pure multiplicative sensitivity is new but it also seems like the definition was already used for p=1 in Mir et al. (2011).\n\n(-) From a theoretical point of view one potential drawback is that the result only holds for the turnstile model: i.e. where each update is positive. It seems like this is needed in proof of Thm 3 in the paper but it's not clear to me if this assumption is reasonable for potential applications of the results in the paper.\n\n(-) The presentation of the paper is not ideal, though the issues I found (see details below) should be easily fixable.\n\n(*) This is not really a concern but the paper did not have an ethics statement. While I can understand that the authors think that since the results in this paper are theoretical there are not ethical issues. While it is correct that there are no direct ethical issues, I would encourage the authors to think about potential mis-uses of the the algorithm by someone who potentially uses the results in this paper. Listing those in an ethical statement could be of use to others.\n\nBelow are some comments for the authors to improve on the presentation:\n\n[Pg. 3, Def 2] \\alpha (in the last line of def) is not defined.\n\n[Algo 1] Is \\delta needed? Also at this point \"accuracy constraint\" is not defined.\n\n[Thm 1] When you say \\M calculates F_p \"accurately\" what does it mean? Do you mean exactly? Another Q: is the \\rho_M the same as \\rho_p that is used in Thm 3? Finally the bound on \\rho_M should have \\le instead of =.\n\n[Proof of Thm 1, para 1] The setting seems different from that on Def 3: why does this not affect the final bounds/results? Please justify.\n\n[Pg. 6, line below first display eq] The claim after \"Observe that\" is not clear: the p-stability does not mention the constant of proportionality while the claimed equality uses the the fact that the constant of proportionality is \\zeta^{-1/p}. Some justification of this would be nice.\n\n[Pg. 6, proof of Thm 3] If there is space it would be nice to define the Laplace transform as well.\n\n[Algo 2] \\delta not required?\n\n[Comparison with Kane et al. above Thm 5] When claiming that the space requirement of Algo 2 is close to Kane et al. is it for the same accuracy requirement on Kane et al.?\n", "summary_of_the_paper": "This paper considers the problem of computing the p'th frequency moment for p\\in (0,1] with \\eps-Differential Privacy (or \\eps-DP). I.e. it presents a randomized algorithm that given a stream of key-values pairs estimates the p-th frequency moment (of a vector indexed by the key and whose entry is the sums of values for the given key) that satisfies the property that given two key-value pair streams \\S and \\S' of the same size such that they differ in exactly on key-value pair, the probability that the output of the mechanism on \\S and S' fall in the same measurable subset of the output space differ by a multiplicative e^{\\eps} factor.\n\nIn fact the paper shows that an existing data stream algorithm due to Indyk based on p-stable distributions gives \\eps-DP guarantees. Using standard techniques from DP literature, the paper shows how to amplify the privacy guarantee by subsampling. The space complexity of the algorithm in the paper is only a log factor away from the optimal space complexity of non-private frequency moment estimation.\n\nThe main technical ingredient is the use of what the paper calls _pure multiplicative sensitivity_ of the p'th frequency moment function (this notion was used for p=1 in Mir et al. (2011)). The bound on the pure multiplicative sensitivity follows from (fairly) simple algebra. Converting the sensitivity bound into \\eps-DP guarantee reduces to showing a certain exponential depending on the p-th frequency moment is positive definite (which is done using the Laplace transform of the exponential).\n\nThe paper also presents some experimental results on the accuracy bounds for the algorithm on real and synthetic data.", "summary_of_the_review": "Theoretically, the paper seems nice but it could be made stronger by providing motivations for the specific problem being studied in the paper, giving better intuition for what technically is new in this paper and by possibility solving the problem for the case when the updates can be negative. These reason being the paper a bit below a clear accept for me.\n\nPost rebuttal comments\n----------------------------\n\nThe authors have addressed most of my concerns about the paper. I'm still not super-convinced about the usefulness of the result for the entire range $p\\in (0,1]$ since the entropy applications seems only to need values $p=1-\\Delta$ for $\\Delta\\to 0$. However, _theoretically_ studying the whole range still makes sense. After the rebuttal the paper is more of a 7 for me.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "v6-eUqcUoo8", "reviewer": "Reviewer_P1Tg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "There has been a growing literature showing that different sketching techniques from the streaming literature preserve differential privacy. By now this is known for the Johnson-Lindenstrauss sketch of the $\\ell_2$ norm, and the Flajolet-Martin distinct counts sketch. This paper adds to this line of work by showing that Indyk’s p-stable distribution sketches, which can be seen as an extension of the Johnson-Lindenstrauss sketch to $\\ell_p$ norms for $p \\in (0,2]$, also preserve differential privacy. The main idea is to first bound the *multiplicative* sensitivity of the $\\ell_p$ norm, and then bound the ratio of the pdfs of the sketch for two neighboring streams in terms of this sensitivity. \n\nThe result is technically interesting, and provides further evidence that techniques from sketching are inherently privacy preserving. For this reason, I think the paper makes a nice conceptual contribution. Unfortunately, the authors don’t really give applications of their result. I would’ve liked to see an example scenario when would one want to publish a p-stable sketch of a stream? Since the randomness of the sketch itself must be kept hidden in order to protect privacy, this result is not applicable in a distributed setting, or in the pan-privacy setting, and I would like to see an example in which it is applicable. \n\nFurther detailed comments:\n\n* Often these sketches are applied to the difference of two streams, in order to estimate the $\\ell_p$ distance between them. In such cases the $v_i$ values might be negative. Can the analysis techniques here be extended to handle this situation?\n\n* What is $\\alpha$ in Definition 2?\n\n* In Definition 3 and Theorem 1 you could just talk about functions rather than deterministic mechanisms.\n\n* The RHS of (3) is also a direct application of Holder’s inequality.\n\n* The authors claim that Theorem 2 was previously proven by Mir et al's PODS 2011 paper, but I cannot find any such result there. What theorem in that paper gives this result?\n\n* In the proof of Theorem 2, please specify that the ratio of pdfs is a decreasing function *of $x$*.\n\n* I can’t fully follow the proof of Theorem 3. Some comments:\n- give a reference or prove that $\\mathcal{D}_{p,1}(x)$ is increasing for $x \\le 0$ and increasing for $x \\ge 0$; also, I don’t understand how the upper bound on the ratio of pdfs follows from this fact;\n- why is it sufficient to show (4), and how does this follow from the second derivative of $(1+u^{1/2})e^{-u^{1/2}}$?\n\n* Instead of subsampling, can’t you improve the privacy loss parameter by padding the stream in order to increase $n$?", "summary_of_the_paper": "The main result of the paper is that Indyk’s p-stable distribution sketch of the $\\ell_p$ norm of a stream itself preserves differential privacy, without any additional randomization. The privacy loss parameter is a function of the length of the stream, the maximum value of any update, and the universe size. The privacy loss improves when the length of the stream goes to infinity with respect to the other parameters. ", "summary_of_the_review": "This paper makes an interesting technical contribution, giving further evidence that sketching techniques from the streaming literature preserve differential privacy without further randomization. The paper can be accepted, although it would be stronger if the authors gave applications of their results. ", "strength_and_weaknesses": "", "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": "4P4js9uYAsy", "reviewer": "Reviewer_49oY", "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": "The result is interesting and satisfying. The problem is important and it's good to have DP algorithms for it. The technical contribution is strong.\n\nThe main weakness is that the result only works for p in (0,1) and therefore feels incomplete. ", "summary_of_the_paper": "This paper proves that Indyk's classical Fp streaming algorithm for frequency moments satisfies the differential privacy (DP) requirements whenever p is in (0,1).\n\nThis leads to the first DP streaming algorithm for this problem with polylog space.\n\nThe new proof is based on a novel analysis of the sensitivity of this algorithm: how much does the output change when the input changes by a bit.\n\n", "summary_of_the_review": "Strong and interesting results. Slightly incomplete, but still a good contribution.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1Fo1HOJl94K", "reviewer": "Reviewer_Pbv7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "**Updated my review to be more positive**\n\nStrengths: They provide reasonable bounds to show that the $\\mathbb{F}_p$ sketch of (Indyk, 2006) is\n$(1/p\\cdot \\ln\\rho_p)$-DP.  I like the flow of the exposition. This is a valuable contribution to the DP literature.\n\nWeaknesses: The privacy parameter is not a constant but the DP guarantee should be a constant.\ne.g., $\\epsilon \\in(0, 1])$. But this is not the case with this paper, rendering the paper\na little bit dangerous for the DP research community. There are other (perhaps minor) details about\nproofs I'd like the authors to clarify. Also, the \"real-world\" dataset is not specified well (where is it from?). The description of the experiments on Page 9 should be a lot more detailed!\n\nTheir algorithm\nprovides, sometimes, vacuous privacy guarantees and inadequate accuracy.\nWe ideally want privacy of $\\epsilon \\leq 1$ but this seems to\nonly happen when $p$ is very close to 1.\nIf $\\rho_p$ is the **multiplicative sensitivity** of the $p$-th frequency moment, then the\nalgorithm (the $\\mathbb{F}_p$ sketch of Indyk) is $1/p\\cdot \\ln\\rho_p$-DP, which is not a constant.\n\nAs described in several DP surveys, $\\epsilon$ should be\na constant (ideally between 0 and 1).  But it appears this is not the case for the $\\mathbb{F}_p$ sketch of\nIndyk. I still think that certain improvements could help make this $\\epsilon$ a constant.\nAs a baseline, the algorithm that uses sampling, to amplify privacy, can maintain polylogarithmic space complexity.\nA $\\epsilon$-DP algorithm (for $\\epsilon\\leq 1$)\nthat chooses, uniformly and at random, $\\gamma n$ entries out of $n$ becomes $2\\gamma\\epsilon$-DP. Clearly,\nif the algorithm uses polylog space for storing the samples, then this could serve as a baseline for\ncomparison for the $F_p$ sketch. (I recognize the authors also use privacy amplification by sampling but on top of the $F_p$ sketch.)\n\nAlso, the authors claim to give the first DP frequency estimation protocol with polylog space complexity\nbut this is clearly not the case. It is known, in the streaming literature, that for $p  > 2$,  the\nspace for $F_p$ estimation must be polynomial whereas polylogarithmic factors are achievable for\n$p\\leq 2$. And since there are DP algorithms for $p=0, 1, 2$, polylog space complexity has already\nbeen achieved previously.\n\n\nOther technical comments:\n\n- In proof for Theorem 1 (page 4): in the first line after \"to lower bound expression (1)\", the\n$(m-1)^{1-p}$ changes to $(m-1)^{p-1}$ in the next line. Is this a typo?\n\n- The proof of Theorem 3 assumes that $\\rho_p\\geq 1$. Is this always the case?\n\n- Proof of Theorem 5: How did you derive the variance of the sub-sampling process? Doesn't seem quite right to me.\n\n## Post-Rebuttal Comments\nThe authors have addressed all my concerns.", "summary_of_the_paper": "The authors show that the $\\mathbb{F}_p$ sketch for frequency moments estimation is differentially private, as is,\nfor $p\\in (0, 1]$. Other special cases for frequency moments estimation have been studied previously in the\nliterature (e.g., Choi et al., 2020, Smith et al., 2020, who study cases for $p = 0, 1, 2$).\n\nFor $p\\in (0, 1]$, the authors build upon the $\\mathbb{F}_p$ sketch of (Indyk, 2006) and show DP properties.\nSpecifically, they show, in Theorem 3,\nthat the $\\mathbb{F}_p$ sketch of Indyk is $1/p\\cdot \\ln\\rho_p$ where\n$\\rho_p$ is the **multiplicative sensitivity** of the $p$-th frequency moment.\n\nThe authors also present basic experimental evaluation of their algorithm (see Figure 3).\nThey also claim (wrongly, in my opinion) that their algorithm is the first with polylog space complexity\nfor $F_p$ estimation.", "summary_of_the_review": "1) They provide reasonable bounds to show that the $\\mathbb{F}_p$ sketch of (Indyk, 2006) is $(1/p\\cdot \\ln\\rho_p)$-DP.  I like the flow of the exposition. This is a valuable contribution to the DP literature.\n\n2) Inadequate privacy guarantee: In the literature, it is recommended that the privacy parameter be a constant. But instead it is $(1/p\\cdot \\ln\\rho_p)$ which might provide no privacy at all for small $p$. [mostly addressed]\n\n3) Experimental Evaluation: the experiments are rather sparse; also the \"real-world\" dataset is not specified. Where is it from? [addressed]\n\n4) There might be some typos in the proofs. Also one calculation (Theorem 5) isn't fully specified. [now addressed]", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agreed that this is a technically novel and interesting paper with results for a very natural problem and all voted for acceptance. The paper gives more evidence for the wide-ranging compatibility between the goals of sketching and of privacy.
Decision: Accept (Poster)