Improved Utility Analysis of Private CountSketch
Authors: Rasmus Pagh
Mikkel Thorup
Venue: NeurIPS 2022 Accept (2022)
Keywords: sketching
dimension reduction
sparsity
differential privacy
countsketch

Abstract: Sketching is an important tool for dealing with high-dimensional vectors that are sparse (or well-approximated by a sparse vector), especially useful in distributed, parallel, and streaming settings.
It is known that sketches can be made differentially private by adding noise according to the sensitivity of the sketch, and this has been used in private analytics and federated learning settings.
The post-processing property of differential privacy implies that \emph{all} estimates computed from the sketch can be released within the given privacy budget.

In this paper we consider the classical CountSketch, made differentially private with the Gaussian mechanism, and give an improved analysis of its estimation error.
Perhaps surprisingly, the privacy-utility trade-off is essentially the best one could hope for, independent of the number of repetitions in CountSketch:
The error is almost identical to the error from non-private CountSketch plus the noise needed to make the vector private in the original, high-dimensional domain.


Improved Utility Analysis of Private CountSketch
Rasmus Pagh
Mikkel Thorup
Basic Algorithms Research Copenhagen University of Copenhagen pagh@di. ku.dk
Basic Algorithms Research Copenhagen University of Copenhagen
mikkell2horuppggaii.. com
Abstract
Sketching is an important tool for dealing with high-dimensional vectors that are sparse (or well-approxi by sparse vector), especially useful in distributed, parallel, and streaming settings. It is known that sketches can be made differen- tially private by adding noise according to the sensitivity of the sketch, and this has been used in private analytics and federated learning settings. The post-processing property of differential privacy implies that all estimates computed from the sketch can be released within the given privacy budget.
In this paper consider the classical CountSketch, made differentially private with the Gaussian mechanism, and give an improved analysis of its estimation eπror. Perhaps surprisingly, the privacy-utility trade-off is essentially the best could hope for, independent of the number of repetitions in CountSketch: The error is almost identical to the error from non-private CountSketch plus the noise needed to make the vector private in the original, high-dimensional domain.
Introduction
CountSketch was introduced by Chariaa, Chen, and Parach-Colton (2004) as method for finding heavy hitters in data streams. In machine learning the same sketch was studied by Weinberger, Das gupta, Langford, Smola, and Attenberg (2009) under the name feature hashing, or less formally the "hashing trick". The idea is to map high-dimensional vector x E Rd to a lower-dimensional repre- sentation Ax R using a certain random linear mapping A. From Ar it is possible estimate entries Zi, with error that depends on D and the norm of x; and more generally to estimate inner products. It was shown in (Weinberger ale 2009) that for Rd. (Az, Ayy is well-concentrated around (I. y). Recent interest in sketching techniques is motivated by distributed applications such as federated learning (Kairouz all M02I), where many users contribute creating model on their combined data, without transferring data itself. In this context, sketching can be used to iden- tify the large-magnitude entries in the of many high-dimensional vectors (one held by each user), using communication proportional to the number of such entries.
Perhaps the most basic property of Coumtketechffeature hashing is the error of estimators for single coordinate x;. The sketch directly provides independent, noisy estimators XI...., Xg. each symmetric with mean I;- Two main ways of combining these into more reliable estimator for x; have been studied: Taking the median estimator (Charikar et all 2004), or taking the average of estimators (implicit in Weinberger all (2(09)). Minton and Price (20) showed that using the median estimator with k (log d) is not only is more robust, but alse decreases the variance of the estimator by factor of 2(log d). Later Larsen, Pagh, and Tētek (202I showed that using the median estimator with & = 3 makes the error decrease quadratically with the sketch size D.
In this paper consider CountSketches that have been made differentially private using the Gaus- sian mechanism, which is perhaps the most widely used mechanism for making high-dimensional vectors differentially private. This sketch, which we will refer to as Private CountSketch, works by
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

adding i...d. Gaussian noise to each coordinate of the CountSketch, with variance scaled according to the (squared L2) sensitivity & of the sketch.
We give additional evidence that the median estimator is preferable to the mean by showing that its estimation noise is independent of the number & of estimators. Previous applications of sketching techniques to differential privacy have had noise that grew (polynomially) with k. The failure prob- ability of CountSketch decreases exponentially in k so preferable to have relatively large, and thus these methods faced a trade-off between the noise from the Gaussian mechanism and the error probability of the underlying CountSketch. We show that this trade-off is not needed: It is possible to both get highly reliable CountSketch (by choosing &s large enough) and achieve noise that depends only on the privacy parameters (independent of k))
Related work
The analysis of the Gaussian mechanism is attributed in Dwork and Roth (201) Appendix A) to the the authors of the seminal paper differential privacy (Dwork, McSherry, Nissi.. and Smith, 2006). It has since been shown to have desirable properties related to keeping track of privacy loss under composition, see e.g. Bun & Steinke (2016); Mironovi (2017).
Local differential privacy. A variant of CountSketch, the Count Mean Sketch has been used by Apple to privately collect information on heavy hitters, e-g. popular emoji in different countries (Ap- ple Differential Privacy Team, 2)17). This can be phrased in terms of summing n user vectors, each one 1-hot vector with single 1, and identifying the large entries. Their protocol works in the local model of differential privacy, which means that each report is differentially private. Lower bounds on local differential privacy (Chan, Shi, and Song, 2012) imply that the noise on estimates in this setting grow with 2 (v)n,, where n is the number of users.
Independently, Bassily, Nissi,, Stemmer, and Thakurta (2020) improved theoretical results of Bassa ily and Smuth (2015) on heavy hitter estimation in the local model, providing practical methods for matching the lower bound of (Chan all 2012). They also base their method CountSketch, though it is made private using a sampling technique combined with randomized response, not by adding noise to each coordinate. The noise from this step, rather than from CountSketch itself, dom- inates the error. Acharya, Sun, and Zhang (2012) showed that similar error can be achieved without any agreed-upon public randomness (with no need for common, random sketch matrix).
Huang, Qiu, Yi, and Cormode (2022) used CountSketch, made private with the geometric (aka. dis- crete Laplace) mechanism, to design protocols for frequency estimation under local differential privacy and multiparty differential privacy. They observe that the estimator in each repetition of CountSketch is symmetric (assuming fully random hashing). but unlike the present paper they do not demonstrate that the median estimator has noise that is smaller than the noise added to each estimator. Thus their estimation error bound grows with the number of repetitions of CountSketch.
Zhou, Wang, Chan, Fanti, and Shi (2022) recently used CountSketch as the basis for a mechanism that releases (-sparse vectors with differential privacy. We relate our result to theirs in Section [44]
Independent of our work, Zhao, Qiao, Redberg, Agrawal, Abbadi, and Wang (1222) recently pre- sented a comprehensive study of differentially private linear sketches, including Private CountSketch. They focus on bounding the maximum error, but also have theoretical results for point estimates that are weaker than ours. Their experiments confirm the performance of Private CountSketch in practice. In addition they show how CountSketch can be used build sketch for quantile approximation. and our results imply tighter analysis for that application.
Protocols based on cryptography. Motivated by srivacy-preeevvigg aggregation of distributed statistics, [Meis. Danezis, and Cristofard (20TT) considered CountSketch (and the related Count- Min sketch) made e-differentially private using the Laplace mechanism (Dwork et all 2016). They empirically showed that the set of heavy hitters, i.e., large entries in the vector, could be identified with very little error on skewed distributions, but did not provide general bounds on estimation error. Their protocol can be implemented in a distributed setting in which each user has 1-hot vector, and we want to sketch the sum of these vectors, using cryptographic protocols for secure aggregation. This bypasses lower bounds on local differential privacy, and yields much better privacy-utility trade-

---

off's (but now assuming security of the aggregation protocols, so guarantees rely on cryptographic assumptions and are coarmatiion-thooettte
Another model of differential privacy, built on the cryptographic primitive of an anonymous channel (e-g. implemented
mixner), is the shuffle model (Cheu, Smith, Ullman, Zeber, and Zhilyaev, 2019: Erlingsso,, Feldman, Mıronov, Raghunathan, Talwar, and Thakurta, 2019). Ghazı, Golowich, Kumar, Pagh, and Velingkei (202T) used Count-Min sketches in a protocol for frequency estimation and heavy hitters in this context. Our work suggests that better accuracy can be obtained by using CountSketch instead of Count-Ming especially for tigh-probability bounds.
Related results in the central model. Mir, Muthukrishnan, Nikolov, and Wiight (201)) studied general mechanisms for making sketching algorithms differentially private, and in particular stud- ied using the Count-Min sketch to identify heavy hitters. They observed that any mechanism that makes linear sketch private by adding (oblivious) noise to the sketch vector implies pan-private sketch that can be updated dynamically. Our work implies an improved pan-private sketch based on CountSketch.
Aumuller, Lebeda, and Pagh (20211) studied differentially private representations sparse vectors, showing that it is possible to achieve space close the number of non-zero entries while keeping noise comparable to a naïve application of the Laplace mechanism to the raw vectors. Our work implies that, up logarithmic factor in space, such result is possible with a linear sketch, which enjoys many desirable properties.
Analysis of CountSketch. Several authors have worked on improved analysis of the error of CountSketch in the non-private setting, including Minton and Price (201)) and Larsen, Pagh, and Teck (2021). It seems possible to analyze Private CountSketch using the framework of (Minton &
Prace 20,,), but we will pursue an elementary, direct analysis that does not depend on the Fourier transform of random variables.
3
Private CountSketch
In this section we provide the necessary background information on CountSketch, and present our improved analysis of Private CountSketch.
3.1 Notation and background
We use [k: to denote the set (1,...,k)
k). Vectors indexed by more integers, each from designated ranges. For example, a vector of dimension D = kbb may be indexed by (i.j) where i [k] and j E [b]. The ordering of vector entries is not important. For integer k. let tail, (2)) denote the vector that is identical to x except that the k coordinates of largest magnitude are replaced with zeros. For a predicate P. we let [P] denote the indicator that is if P true and otherwise.
The
CountSketch is random linear mapping of vector x E Rd to Ax E R.D. For suitable parameters b such that D = kb, the sketch CS((r) is defined in terms of two sequences of random, independent hash functions:
hy..... h4 [d] + [b]. and
S....... Sk [d] + (-1.+11 +1}.
CountSketch was originally presented with hash functions from a 2-wise independent fami- lies (Chankar 2004), but in this paper assume that all hash functions used are fully random. (Full randomness is used in our analysis of error, but the privacy of our method does not depend on this assumption.) To simplify our exposition we will further assume that & is odd and that b is even.
we index CS(x) E R by (i.j) E [k] x [6], then CS()),
Σ (,())x)(h,(1) ME
That is, each vector entry x4 added, with sign sz()), to entries indexed by (1, (O), for [k]. We can the sketch as sequence of à hash tables, each of size b; thus refer to & as the number
3

---

of repetitions and to b as the table size. It is easy to see that
x; - =(())S()))
is an unbiased estimator for zạ for each i E [k]. Furthermore, since is fully random the distribution
of X; conditioned on st( -1 is identical to the distribution of X, conditioned on si({)
which means that X, is symmetric around Iz. We can combine these estimators into more robust estimator:
t median ((s:())CS())))a)))
[K]))
(1)
Minton Price (2014) bounded the error of äg with failure probability that exponentially decreasing with k:
Theorem 3.1 (Munion & Price (MI)))) For every a E [0, 1] and every & E [d], the estimation error of CountSketch with & repetitions and table size satisfies
Pr Pr zel > A] 2exp (-S2 (a²k))
where A = [
Note that ||tail, (2) S ||||||, but can be much smaller for skewed distributions and even zero for sparse vectors. Choosing suitable a²k: = O(log d) we get that all coordinates are estimated within this error bound with high probability.
3.2 Private CountSketch
Several approaches for releasing a CountSketch with differential privacy have been studied. These all require that the sketches of neighboring vectors x, x', denoted x ~ x'. have similar distributions. The neighboring relation that we consider is that x ~ x' if and only if these vectors differ in at most one entry, by most 1, or equivalently that z- x' has single nonzero entry with value in [-1,+1]. Since CountSketch is linear, CS(x) CS(x') = CS(x - x'). From this it is easy to see that for ~ x', ||CS((x) CS(x')ll s Vk. In differential privacy terminology, the sensitivity of the sketch is Vk.
There are many ways to compute a differentially private version of a CountSketch CS(x)) (or any other function of x),, but it is most common to consider oblivious methods that work by sampling a symmetric noise vector v E RD that is independent (2( and releasing the private Count- Sketch:
PCS(x) = CS(x)+ +v. +v.
Since the noise is symmetric around zero, have (similar to before) that X; s)))) an unbiased estimator for øe, and therefore it makes sense to use the median estimator (II) also for Private CountSketch:
f = median ((s(a)(((((())SS)))))))))) l i [b])
Note that except for the addition v, which can be considered an alternative initialization step, Private CountSketch works in exactly the same way CountSketch: Updates are done in the same way, and estimators Ze are computed in the same way.
Properties of Private CountSketch. Since PCS(x) is affine transformation, it can be main- tained under updates to æ. Also, it is possible to add and subtract Private CountSketches (based on the same hash functions), e.g.: PCS(z) +CS()) = CS(( + 3) + 22.
where 2/2 and My are sampled according to the noise distribution.
The noise distribution we will consider in this paper is the standard D D-dimensional Gaussian distri- bution (0, with mean zero and variance o², and in the rest of this paper we refer to PSC(a) with noise [1 P. Differential privacy properties of PCS(x) follows from general results on the Gaussian mechanism, see e.g. Dwork Roth (2014, Apendix A) and Bun & Steinke (2016). We state some of them for convenience here:

---

Lemma 3.2. (CS(x) is (e, (...))-dffeeentiill private for satisfying o² 2k I/ and & and it is (k/2o' oo²) ) -ezro-concentratee differentially private.
This tells that get good privacy parameters, need to Gaussian noise with variance (2(k), Le., standard deviation least DD /R). The median estimator (2)) returns, for some i,
81 ()) (e( (CS(T).A..) (.)..())
i.e., value that could be returned by CountSketch plus noise term with standard deviation 22 ((k)). Thus, we might expect magnitude of the noise to scale proportionally to vk. Our main result that this does not happen, and in fact the magnitude of the noise can be bounded independently of k.
Theorem 3.3. For every E [0, 1] and every [d] the estimation error of Private CountSketch with k repetitions, table size and noise from N 2 satisfies
Pr[léz xel > max A, o)) < 2exp (a2k))))))
where A =
Discussion. Theorem generalizes the known tail bound on CountSketch, since we let a 1 and = 0 recover Theorem [.].
For < if we choose suitable o O / h (o) the Private CountSketch satisfies (e, 6)-
differential privacy. For noise level / 2 A and deviation y < a we then get:
Pr[lă: Iz > > < 2 exp (-2 (>2s² (m(=/))((1)0)))
Up to the hidden constant in the order-notation this is identical to the tail bound for the noise of the Gaussian distribution applied directly to in order ensure (e, diffferential privacy.
3.3 Analysis of Private CountSketch
The message of our paper is that Gaussian noise composes very nicely with the CountSketches as analysed by (Minton Price, 2) All we use is that the CountSketch estimator the median of symmetric variables.
For the median trick indendent symmetric random variables Cı,..., Ck. Minton & Price (2014) Lemma 3.3) show that for > O where Pr|[C] S 7] 2 it holds that
Pr Fr]]mmdian C.|
7 s 2 2exp(_p2kk)
In our case, for i I,...,,, k we have a symmetric random variable A, (representing a simple estimator error before noise) to which we add Gaussian noise B; N(O, The estimator C, = A; + B; is clearly also symmetric. Basic properties of the Gaussian distribution implies that
(a) y S a and |A| I a then Pr[|C,| s 7 2(7/o).
(b) if 2 σ and | E then Pr[ C. S 7] (1)).
In our concrete (details below) we will have furher property of A,, namely
(c) There exists A > 0 such that for every E Pr(]A4 s aAl = -(a).
Lemma 3.4. Assuming (a), (b), and (c) then for every a' E [0,
Pr[[Cd a' max(A, l(aa).
Proof. If a' 2 then using (b) and (c),
Pr[[Ca] $ a' max/A, o
Pr[|C,| a'A] Pr[[C,| < a'A ||A a'A] PPIIA S d'A]
((1) 22a') 2(aa))
5

---

If a' I and A 2 0, we set a1 = 0/4 and 02 = a' a/o such that 0102 = a'. Using (a) and
(c) we get
Pr[[C S a' m o = Pr|CC]] a
Pr[[C]] < a'A |A:| < Pr|]AA S
Pr[[ S ago
| S Pr[|A & aT
((02)) (((1)) = Q(a')
Finally, if a' and A o, use (a) and (c) get
Pr||Ci| S a' max .)] Pr[[C]| a'o]
z Pr[[C]| S a'o |A/ 5 PrIJA| S
-(aa)) 2(1) 22aa
We now return to the details of Private CountSketch. For given E [d]. Private CountSketch finds simple estimates
X, = =(((( (CS( + (.,..0))
of zς and returns the median, where (f) ~ o²) is Gaussian noise. Since the noise is symmetric, we get exactly the same distribution of X; if we compute it as
X; = se( (C,) + B,
where B, ~ N(O, o2). The point is that we can fix the variables in (f( (CS(z)ana1) first, and with the sign (i) fixed, (())L,,)))) ~ NN,
In the above s; (O(CS()))) is the ith simple estimator of xy in the CountSketch. has error
A = (0())))))))))
so the error of Private CountSketch is distributed as C; A; + B,. For the error A; from Count- Sketch Minton Price (2014) (proof of Theorem 4.1, using Corollary 3.2) proved that (c) is satisfied with = ||tail 22 (x) (22)ll//// 2 /Vb. Hence, by Lemma B.4 Pr[[C.| s maxx(A,o)) o)] 2(aa) for every
[0, 1]. Now, by (E) for every a [0, 1].
Pr|Imedian,e;g/ Ci| >> max(A, s 2exp(-Q(a²kk))
If m is the index of the median C, then Xm D2 + Cm is the Private Countsketch estimator of we. so this completes the proof of Theorem 3.3.
We note that Theorem KK could also be proved using the framework of (Minton & Price, 2014), exploiting that Gaussian variables have non-negative Fourier transform. However, this requires that the noise free error A, also has non-negative Fourier transform. Indeed this is the case for CountSketch as proved in (M & Price, 201 b > 1. However, our proof does not require A; to have negative Fourier transform, and this could prove useful in other contexts where Gaussian noise is added.
Limitations. Our error analysis relies on the assumption that the sign hash functions used are fully random. This assumption may be expensive to realize in practice, though it is always possible by storing an explicit, random list
hash values (as done in our experiments). Alternatively, as observed in (Minton & Price, 2012) we could use the pseudorandom generator of Nisan (199() to implement our hash functions, which requires space that exceeds the space for the sketch by logarithmic factor. Furthermore, these hash functions be shared among several CountSketches, reducing the space overhead.
Another issue to be aware of is that though CountSketch will be able to significantly compress sufficiently skewed or sparse input vectors, size of a CountSketch with good accuracy can in general be larger than the size of the original vector.

---

3.4 Comparison to Other Private Sketches
is instructive to compare Private CountSketch to other private sketches that have been studied in the literature, in particular Private Count-Min Sketch eMll 20166 and Count Mean Sketch (Apple Differential Privacy Team, 20T7).
Private Count-Min Sketch. The Count-Min Sketch (Cormode & Muthukrishnan, 2003) is a well- known sketch that corresponds to CountSketch without the sign functions (or alternatively with constant (e) 1). Its estimator is similar to that of CountSketch except that it works by taking the minimum of the i independent estimates obtained from the sketch. The minimum estimator has a one-sided eπror guarantee (never underestimates zz) in terms of 2 l[2 for vectors z that have only nonnegative entries. Similar to CountSketch failure probability decreases exponentially with the number & of repetitions.
A private version of Count-Min Sketch, studied by Melis et all (2016), works by adding independent (Laplace) noise to each entry of the sketch. This of course breaks the one-sided eπror guarantee. Another variant, with a non-negative binomial noise distribution (for integer valued vectors), was studied by Ghazi et all (202T)). In both cases the minimum estimator is biased and its variance grows with k. A third possibility would be Gaussian noise, but again the variance of the minimum estimator can be large (at least Okk log k) for the minimum of & Gaussians with variance k)).
Private Count-Mean Sketch. We use Count-Mean Sketch to refer to CountSketch, where the estimator is the mean rather than the median. This sketch was studied by Apple Differential Privacy Teaml (2017) in the local model, where it was only used on 1-hot vectors with single 1. One can ask if the mean estimator is useful in other models of differential privacy, but unfortunately it lacks the robustness properties of CountSketch. In particular, it gives error bounds in terms of the norm ||ا||| rather than ||tail//2 (z)]l2 which means that it is not robust against outliers or adversarial data.
Local differential privacy Zhou (20222 consider differentially private encodings of t-sparse vectors with nonzero values in [-1, They use CountSketch with single repetition to encode t-sparse vector, optionally apply a clipping step, and then add Laplace noise to ensure privacy. The main use case is the local differential privacy (LDP) model, where each noisy CountSketch is sent it to an aggrator that sums the estimates of n users.
Kane & Nelson (2014) have shown that the norm of a CountSketch, ||Aæ||2. with A: = O (log(11/))
repetitions is within a factor 1 + from VE||z||2 with probability at least 1 - 5. In particular, the CountSketch of a t-sparse vector with nonzero values in [-1, has norm ||Ax||2 < 22/l|/2222 < 2/kt with probability sian noise by 2vkt our results imply an alternative LDP encoding of t-sparse vectors in [-1, 1]d that differs from the protocol of Zhou et all (2022) by offering smaller error (in fact matching their lower bound) the expense of larger communication complexity.
5. Applying clipping to ensure norm at most 2/kt and scaling the Gaus-
4 Experiments
We have conducted experiments to empirically investigate the properties of private CountSketch. Our main result ignores constant factors in the exponent of the bound on failure probability, but we see in experiments that these constants are very reasonable. All experiments can be recreated by running Python script available on GitHub 0 (runs in ~13 minutes on an MI MacBook Pro). Density plots are smoothed using the Seaborn library's 's kdeplot function with default parameters.
4.1 Median of normals
As warm-up up we consider the setting in which a function f(x) is released k times independently. Th,..., Tk (([(x), for some integer k. The magnitude of the noise is chosen such that the privacy is bounded independently of k, e.g., if f(x) has sensitivity then (ri....,,r) satisfies 1 1/2-rero-concentrateed differentially privacy (different parameters can be achieved by scaling the
magnitude of the noise). Each release has noise of expected magnitude O ((Kk), but the median

---

Median of Cruusians with mean zero and vartenoe
Add emor over Countskeich in zero vanance eetting
k-15
kmb3
Proortonn
0.4
02
Figure well-known that the median of l Gaussians with variance k is itself subgaussian, with variance independent of k. This illustrates a "best case" for Private CountSketch, in which estimators X3 (w/o noise) provide the exact an-
Figure 2:
Distribution of noise magnitude for Private CountSketch the setting where Count- Sketch estimators have zero variance. The magni- tude is only slightly higher than a standard Gaus- sian, achieving the same level of privacy.
Cumulativn sparse
10)
1.0
3
0.6
Stl. Goussian
0.4
Figure 3: Error distribution for Private Count- Sketch on sparse vectors for various number of repetitions, compared making the output dif- ferentially private using a standard Gaussian, giving the same privacy guarantee.
0.0
-15
-10 -5
10 16
has noise that be bounded independently of k illustrated in Figure II. This gives form of differentially private secret sharing, where of k releases can be combined to yield an estimator with noise of magnitude @ /k/i). Taking the mean value also gives a low-variance estimator, but mean values are sensitive outliers and are not robust to adversarially corrupted data.
4.2
The zero-variance CountSketch setting
Next, consider the idealized setting in which CountSketch itself does not have any error. This corresponds to letting the table size go to infinity, so we would hope to come close to the noise achieved by applying the Gaussian mechanism directly indicative the situation which the noise added to achieve differential privacy dominates the noise coming from randomness in CountSketch. Figure E shows the cumulative distribution function for the absolute value of the error obtained by Private CountSketch, for different values k. (Of course, in this setting choosing & 1 suffices to achieve low failure probability, but large value of & is needed in general to ensure few estimation failures.) As can be seen, the noise distributions quite close that the standard Gaussian mechanism operating directly desired level of privacy, the noise in both cases has to be scaled appropriately, e.g., to achieve (e, d)- differential privacy for E < 1 it suffices to multiply the noise by factor 121////))
the vector x. More generally, this is
To achieve
4.3 Sparse vectors
Next we investigate the error distribution on I-sparse vectors, where most entries are non-zero.
is well-known that a CountSketch with & = O(log d) repetitions each using space b O(t) is able

---

1e-WWorid ciiea skeuth orrer with DP nais magnibude 1e104
Jo-Poorld citse skutch arror with DP neise of megnitude 1a
14
K:1. b-10000
X:1, b-1000
1-3. b- 1-10000
1e3, b-1000
1.2
1e5, 10930
ln5, b-1030
b-10000
b-1000
1.0
0.8
Danatyy
0.5
0.4
0.2
0.0
-100000
166
Figure Distribution of noise for Private CountSketch on the world cities dataset with table size b = 10, 000 (left) and b = 1000 (right) for various number of repetitions k. The scale of the noise added for differential privacy a = 10, 000 (left) and a 100, 000 (right) so the sketch achieves strong group privacy. The Gaussian with standard deviation is included for comparison.
to reconstruct t-sparse vectors without any error, with high probability. Thus we expect the error from Private CountSketch, with a sufficiently large number of repetitions, to be similar to the error obtained by applying the Gaussian mechanism the raw vectors. Figure shows the cumulative error distribution for a Private CountSketch (event-level privacy) representing a t-sparse vector in which every nonzero entry has a value of 10, using repetitions with table size t. As can be seen, once the number of repetitions goes to 15 or more, the error distribution becomes comparable to that of the Gaussian mechanism applied directly to the sparse representation.
4.4 Real-world examples
Population data with group privacy. To illustrate how Private CountSketch may be used on real- world data, we first consider the noise of a sketch of population counts in about 40,000 cities". We can consider this as a very sparse, high-dimensional data set indexed by the names of cities (among the set of all possible strings). In this way, the sketch does not need to contain any direct information on the set of cities whose population counts are stored, though we will be able to infer such membership from auxiliary information on population (if this number is sufficiently high).
We aim for group privacy for large sets of people (see (Dwork & Rothi 201 for formal definition) by setting the target noise magnitude on estimates high, from 10a 10sh Intuitively, this hides the contribution to the sketch from any not too large group of people. The table size b of the sketches is chosen roughly balance the noise from the CountSketch itself and the Gaussian mechanism.
Figure El shows the figure with noise at scale 10a (left) and at scale 10a (right). As can be seen, the tails of the noise become noticably thinner as k increased (of course at the cost of factor & in sketch size). Some of the sketches have size kb larger than the original data set (the sparsity of the vector indexed by city names) so the point of sketching is not compression per se, though one would expect to see compression for larger and more skewed data sets.
Market basket data. Finally, we consider representing two sparse histograms based on market basket data sets obtained from the FIMI data collection, http: uantwerpen. beatwerpen.be//dtte//
The kosarak dataset (collected by Ferenc Bodon) contains click-stream data of Hun- garian on-line news portal, a set of click IDs per user session. We limit the size of each set to 100 clicks, resulting in 40148 distinct click IDs and 7264322 clicks in total. The high-dimensional vector considered represents the number of occurrences of each click ID.
The retail dataset (collected by Tom Brijs) contains the shopping basket data from a Belgian retail store, set of item IDs per customer. We limit the size of each set to 30 items, resulting in 16243 distinct item IDs and 888317 items in total. The high-dimensional vector considered represents the number of purchases of each item.
Retriieedd 2022-01-27 from https: http:::/ssmmmmmaapppa http:/pppp..poocmttt/aloldddd-da

---

Estimation enor CDF koserox jrax baoket size 100%, k-S, b-1000
Eviinaion ener CDF retal Irax basket srze 30), k-5, b-500
1.0
prtvate s-1, o 1x-88
pmavr CS2 a-1, Te-66
0.
Figure Cumulative distribution of noise for Private CountSketch on two market basket datasets, kosarak (left) and retail (right). Privacy is with respect to adding removing single basket, where baskets are truncated to maximum size of 100 and 30, respectively.
For both datasets constructed CountSketches of size considerably smaller than the number of dis- tinct IDs: kb = 5000 sketch entries for kosarak and kb = 2500 entries for retail. Figure & shows the empirical cumulative distribution functions of the error of CountSketch and Private CountSketch for the two datasets. For privacy parameters = 1 and å = 10-6 (with respect to a single market basket) see that the error of Private CountSketch is nearly well concentrated as the error of CountSketch.
Conclusion
We have seen that CountSketch can be made differentially private at essentially the smallest conceiv- able cost: Coordinates of the sketched vector estimated with error that is close to the maximum of the error from non-private CountSketch and error necessary for differential privacy without sketching. A problem we leave is to obtain the same error bound with explicit, space-efficient classes of hash functions.
Since CountSketch can represent t-sparse vectors without error, for k = Ollog d). this implies new differentially private representation of such vectors that uses space O log d), is dynamic in the sense that the set of nonzero entries can be updated, and which keeps the level of noise close the best possible in the non-sparse setting. This also implies that we can get good estimates of dot products between standard sparse vectors and vectors represented using Private CountSketch. Less clear is how to best estimate dot product between two vectors given as Private CountSketches. This is related to work of Stausholm (202T) differentially private Euclidean distance estimation, though one could hope for error guarantees in terms the norm of tails of the two vectors.
Finally, we note that Cohen al (2022) recently used differential privacy techniques in connection with CountSketch in order achieve robustness against adaptive adversaries that attempt to find elements that appear to be heavy hitters but are in fact not. It is worth investigating whether Private Countsketch has similar robustness properties.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their help with improving the exposition, and in particular with clarifying the relationship between our work and Minton & Price (2012). The authors affiliated with Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. Rasmus Pagh supported by a Providentia, a Data Science Distinguished Investigator grant from Novo Nordisk Fonden.
10

---

References
Acharya, J., Sun, Z., and Zhang, H. Hadamard response: Estimating distributions privately, effi- ciently, and with little communication. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1120-1122 129, PMLR, 2019.
Apple Differential Privacy Team. Learning with privacy at scale. Apple Mach. Learn. J, 1(8):1-25, 2017.
Aumüller, M.. Lebeda, C. J., and Pagh, R. Differentially private sparse vectors with low enror, optimal space, and fast access. Proceedings of Conference on Computer and Communications Security (CCS), pp. 1223-1236. ACM, 2021.
Bassily, R. and Smith, A. Local, private, efficient protocols for succinct histograms. In Proceedings of ACM Symposium Theory of Computing (STOC), pp. 127-135, 2015.
Bassily, R., Nissim, K., Stemmer, U., and Thakurta, A. Practical locally private heavy hitters. Jour- nal of Machine Learning Research, 21(16): 2020.
Bun, M. and Steinke, Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference (TCC), pp. 635-658. Springer, 2016.
Chan, T. H., Shi, E., and Song, D. Optimal lower bound for differentially private multi-party ag- gregation. In Proceedings of European Symposium Algorithms (ESA), pp. 277-288. Springer, 2012.
Charikar, M., Chen, K., and Farach-Coltor M. Finding frequent items data streams. Theoretical Computer Science, 312(1):3-15) 2004.
Cheu, A., Smith, A., Ullman, J., Zeber, D., and Zhilyaev, M. Distributed differential privacy via shuffling. In Proceedings of International Conference the Theory and Applications of Crypto- graphic Techniques (Eurocrypt), pp. 375 7733403.45 Springer, 2019.
Cohen, E., Lyu, X., Nelson, J., Sarlós, T., Shechner, M., and Stemmer, U. On the robustness of countsketch to adaptive inputs. In International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pp. 4112-4140, PMLR, 2022.
Cormode, G. and Muthukrishnan, S. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005.
Dwork, C. and Roth, The algorithmic foundations of differential privacy. Foundations and Trendsö in Theoretical Computer Science, 9(34)221-400 2014. ISSN 1551-305X. doi: 10.1561/ 0400000042.
Dwork, C., McSherry, F., Nissim, K., and Smith, Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference (TCC), pp. 265-284. Springer, 2006.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentiality, 733:17-51,, 2016.
Erlingsson, Ú. Feldman, V., Mironov, Raghunathan, A., Talwar, K., and Thakurta, Amplifi- cation by shuffling: From local to central differential privacy via anonymity. In Proceedings of Symposium on Discrete Algorithms (SODA), pp. 2468 2479. SIAM, 2019.
Ghazi, B., Golowich, N., Kumar, R., Pagh, R., and Velingker, A. On the power of multiple anony- mous messages: Frequency estimation and selection in the shuffle model differential privacy. In Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), pp. 463-488. Springer, 2021.
Huang, 7., Qiu, Y., Yi, K., and Cormode, Frequency estimation under multiparty differential privacy: One-shot and streaming. Proc. VLDB Endow. 15(10):2058-200 2022.
11

---

Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M.. Bhagoji. A. N., Bonawitz, K. A.,
Charles, Z., Cormode, G., Cummings, R., D'Oliveira, R. G. L., Eichner, H., Rouayheb, S. E.. Evans, D., Gardner, J., Garrett, Z.,, Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He, L.,, Huo, Z.,, Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konečný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T.,, Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh. R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song, W. Stich, S. U., Sun, Z., Suresh, A. T., Tramèr, F., Vepakomma. P., Wang. J., Xiong, L., Xu, Z., Yang. Q. Yu, F. X., Yu, H., and Zhao, S. Advances and open problems in federated learning. Found. Trends Mach. Learn., 14(1-2)11-110 2021.
Kane, D. M. and Nelson, J. Sparser Johnson-LLindenstrau transforms. Journal of the ACM, 61(1), January 2014. ISSN 0004-5411.
Larsen, K. G., Pagh, R., and Tětek, J. Countsketches, feature hashing and the median of three. In Proceedings of International Conference on Machine Learning (ICML), volume 139 of Proceed- ings of Machine Learning Research, pp. 601 1-6020. PMLR, 2021.
Melis, L.,, Danezis, G., and Cristofaro, E. D. Efficient private statistics with succinet sketches. In Annual Network and Distributed System Security Symposium (NDSS). The Internet Society, 2016.
Minton, G. T. and Price. E. Improved concentration bounds for count-sketch. Proceedings of Symposium Discrete Algorithms (SODA), pp. 669-686, 2014.
Mir, D., Muthukrishnan, S., Nikolov, A., and Wright, R. N. Pan-private algorithms via statistics sketches In Proceedings of Symposium on Principles of database systems (PODS), pp. 37-48, 2011.
Mironov, I. Rényi differential privacy. In Proceedings of Computer Security Foundations Symposium (CSF), pp.
IEEE, 2017.
Nisan, N. Pseudorandom generators for space-bounded computations. Symposium on Theory of Computing (STOC), pp. 204-212, 1990.
In Proceedings of ACM
Stausholm, N. M. Improved differentially private euclidean distance approximation. In Proceedings of Symposium on Principles of Database Systems (PODS), pp. 42-56, 2021.
Weinberger, K., Dasgupta, A., Langford, J., Smola, A., and Attenberg, Feature hashing for large scale multitask learning. In Proceedings of International Conference on Machine Learning (ICML), pp. 1113-1120, 2009.
Zhao, F., Qiao, D., Redberg, R., Agrawal, D., Abbadi, E., and Wang. Y. Differentially private linear sketches: Efficient implementations and applications. In Proceedings of conference on Neural Information Processing Systems (NeurIPS), 2022.
Zhou, M., Wang. T., Chan, H., Fanti, G., and Shi, E. Locally differentially private sparse vector aggregation. In Symposium on Security and Privacy (SP), IEEE, 2022.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "gCfvyXMJcPv", "reviewer": "Reviewer_o9ww", "summary": "The paper considers CountSketch that is made private using Gaussian mechanism. They show that the privacy-utility trade-off is essentially tight.  ", "questions": "No questions", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper gives a new analysis of private count sketch, where privacy is achieved using Gaussian mechanism. They show that median estimator has better bounds than mean estimator. \n\nThe proof is correct and the paper does improves the general understanding of the area. I recommend accepting the paper.\n\nepsilon should be less than one in Lemma 3.2 .\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WpDNV29ceS0", "reviewer": "Reviewer_x5cX", "summary": "The paper present a novel analysis of CountSketch made differentially private using the Gaussian mechanism.  The analysis makes use of some novel/recent median-of-symmetric variables concentration analysis in a fruitful way.  The end result is that the performance (in terms of the noise added) matches what would occur with directly adding Guassian noise to the original vector to achieve differential privacy.  Experiments results are presented.", "questions": "\nGiven my comments on the experiments above,  I am hoping you can provide some motivation/explanation of the experiments, and I would encourage you to more clearly motivate/explain them in the final version.  ", "limitations": "Not applicable", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe median analysis is very nice.  \nSeems like a worthwhile issue in differential privacy.\n\nWeaknesses:\n\nI didn't find the experiments and their explanations very clear.  For example, I couldn't understand what the high-variance CountSketch setting was supposed to demonstrate, or where this situation arises, or how these experimental results related to the theorems.  It's a setting that wasn't explained prior to the experimental section, does not seem to be standard (at least you don't reference other papers that have considered this setting), and it's not clear what the point is.  (A seemingly artificial setting where the private CountSketch can give better estimate than the standard CountSketch is not especially compelling.)  It could be my fault as the reader but I did not understand the purpose of that experiment.  \n\nSimilarly I'm not clear on the importance/relevance of the sparse vector case -- it seems like you're just using it as a test, but it doesn't seem to be practically motivated, and is loosely related to the theoretical claims.\n\nMore compelling real-world datasets would also be useful.  In particular, you are using high noise for group privacy;  it feels like the setting with lower noise would still be worth examining and it would be useful to see it here as well.  \n[Overall, it felt like you could have added an appendix with more details/clarity on your experiments, and present more experiments.]\n\nNeutral:  \n\nThe authors note that their results require \"full randomness\" and that more limited randomness (e.g, k-wise independence) would not suffice.  They are up front about this assumption and the assumption itself is quite natural.  \n\nOriginality:  Nice theoretical result.\nQuality:  Same above.\nClarity:  Well written, except for the experimental section.\nSignificance:  Hard to say; if you believe people will actually use differential privacy, this seems a significant advance for applications using CountSketch, which I believe do exist.  ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1HsSJpPlsV", "reviewer": "Reviewer_CnGL", "summary": "CountSketch [Charikar-Chen-Farach-Colton 2004] is a popular data structure for maintaining a high-dimension vector $x\\in \\{0,1\\}^d$ using a lower-dimensional representation $Ax\\in \\mathbb{R}^D$(think of $D\\gg d$), while supporting single-entry estimations (i.e., given $i\\in [d]$, return an additive estimation of $x_i$) and heavy-hitter queries (i.e., return a small list $L\\subseteq [n]$ of indices, which includes all those $i$'s such that $|x_i|$ is large).\n\nThe standard CountSketch is parametrized by $(d,k,b)$. Intuitively, $b$ is the \"table size\" of CountSketch and $k$ is the number of \"repetitions\". It stores a representation of $x\\in \\mathbb{R}^d$ by a vector $Ax\\in \\mathbb{R}^{kb}$. Given a point query $i\\in [d]$, it can return an estimation of $x_i$ (using the so-called median estimator) such that\n\n$\n\\Pr\\left[|x_i - \\tilde{x}_i| > \\frac{1}{\\sqrt{b}} \\| tail(x,b) \\|_2 \\right]\\le e^{-\\Omega(k)}.\n$\n\nThe CountSketch can be made $(\\varepsilon,\\delta)$-differentially private by adding a Gaussian noise to the sketch vector: release $Ax+\\nu$ where $\\nu \\sim N(0,\\sigma^2)^{kb}$  and $\\sigma^2 \\approx \\frac{2k}{\\varepsilon^2} \\ln(1.25/\\delta)$. Intuitively, this distorts each entry of $Ax$ by a noise with variance $\\sqrt{k}$. Therefore, one might expect the Private CountSketch can only support  point query with additive error $\\Omega(\\sqrt{k})$. \n\nThe authors argued that this is not the case by showing that, using the median estimator on top the Private CountSketch, one has\n\n$\n\\Pr\\left[ |x_i - \\tilde{x}_i| > \\frac{1}{\\sqrt{b}} \\| tail(x,b) \\|_2 + \\gamma \\right] \\le e^{-\\Omega(\\gamma^2\\varepsilon^2/\\ln(1/\\delta))}.\n$\n\nRemarkably, this is independent of $k$ (the number of \"repetitions\" in the count sketch). (However, in order to recover the $e^{-\\Omega(k)}$ upper bound on the failure probability, one must take $\\gamma$ as $\\Omega(\\sqrt{k})$.)\n\nThe authors show extensive simulations to support their theoretical claims. In particular, note that there might be two sources of errors in the private CountSketch: (1) from the the inaccuracy of CountSketch itself (the $\\frac{1}{\\sqrt{b}}\\|x_{tail(b)}\\|$ term). (2) from the introduction of Gaussian noise. The authors consider different scenarios regarding which term of the errors is dominant and conduct experiments to see how the error scales with k. Overall, the finding is that as the number of repetitions $k$ increases, the error from the Gaussian noise dominates, and the PDF of the error \"converges\" to that of a Gaussian distribution.\n", "questions": "1. You mentioned that applying the Minton-Price technique in your setting directly yields weaker results. But it seems to me you can use the Minton-Price technique (https://arxiv.org/pdf/1207.5200.pdf) in a nearly black-box way to reproduce your main theorem. Let $X$ be an estimation of $x_\\ell$ given by the (non-private) CountSketch. Let $\\Delta = 1/\\sqrt{b} ||x_{tail(b)} ||$. Let $g\\sim N(0,\\sigma^2)$. Essentially, your proof wants to lower bound $\\Pr[X + g \\in [x_{\\ell} - \\Delta - \\gamma, x_{\\ell} + \\Delta + \\gamma]]$ by $\\Omega(\\gamma/\\sigma)$. You achieve this by showing that $\\Pr[X \\in [x_{\\ell} - \\Delta, x_{\\ell} + \\Delta]] \\ge \\Omega(1)$ and $\\Pr[|g|\\le \\gamma] \\ge \\Omega(\\gamma/\\sigma)$. However, if we consider $Y := X + g - x_{\\ell}$, it is easy to see that $Y$ (1) has varaince $\\le \\sigma^2 + \\Delta^2$, (2) is symmetric around zero, and (3) has non-negative Fourier transform. Using Lemma 3.1 in [ https://arxiv.org/pdf/1207.5200.pdf ] should allow you to recover (and slightly improve if $\\Delta \\ll \\sigma$) your result. (Please correct me if I make a mistake at some step.)\n2. In your discussion at Line 171: it should be $|x_{tail(b)}|/\\sqrt{b} < \\gamma < \\sigma$ (the submission stated $\\gamma > \\max(\\sigma, |x_{tail(b)}|/\\sqrt{b})$?\n2. Minor typo: the equation below Line 206: $x_i + \\Delta$ ==> $x_\\ell + \\Delta$.", "limitations": "See the \"weakness\" and \"questions\" sections.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The observation that the median estimator is \"compatible\" with Gaussian noise is nice and elegant. Although this seems not completely novel (see the \"weakness\" and my question below), this paper manages to apply this observation in the context of sketching + privacy, which allows privatizing CountSketch in a simple and standard way, while still achieving a good utility guarantee.\n- The experiments are thorough and illustrative, which I appreciate. Although I did not try to reproduce the simulations myself, the presentation looks sound and clear.\n- Discussions about related work and comparisons with other private sketches are well-written and informative.\n\nWeakness:\n\n- The main technical message of this work is that \"taking the median of several i.i.d. random variables, you can expect the result deviation (aka. error) to be much smaller than the standard deviation of the individual random variables\". This appears not to be a completely novel observation. In particular, it appears in a previous work [Minton and Price, SODA 2014. see also https://arxiv.org/abs/1207.5200 ]. The current paper did mention the Minton-Price result, but the discussion and comparison seem not quite fair (see my question below).\n- The theoretical analysis needs to assume that the hash functions for CountSketch are truly random. Storing a truly-random hash function would require a space as large as the dimension of the input vector. To compare, the standard analysis for CountSketch (as in [Charikar-Chen-Farach-Colton 2004]) only needs pairwise-independent hash functions, which can be stored using a space that is logarithmic in the dimension of x.\n\nMy overall opinion is that (1) the technical result in this paper is not completely novel, given the previous Minton-Price result. But the current paper does find a new application of the Minton-Price idea to an important question (i.e., privatizing CountSketch). (2) The presentation is good, the experiments are thorough, and the discussions about related works are informative. \n\nIn summary, I would recommend a weak accept.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept