Smooth Flipping Probability for Differential Private Sign Random Projection Methods
Authors: Ping Li
Xiaoyun Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy
Random Projection

Abstract: We develop a series of differential privacy (DP) algorithms from a family of random projection (RP) and sign random projection (SignRP) methods. We first show how to improve the previous DP-RP approach using the ``optimal Gaussian mechanism''. Then, we propose a series of DP-SignRP algorithms that leverage the robustness of the ``sign flipping probability'' of random projections. That is, given $x = \sum_{i=1}^p u_i w_{i}$ where $u$ is a $p$-dimensional data vector and $w$ is a symmetric random vector,  $sign(x)$ only has a fairly small probability to be flipped if there is a small modification on data $u$, depending on the specific distribution of $w$. This robustness leads to our novel design of ``smooth flipping probability'' for SignRP-type algorithms with better utility than using the standard randomized response mechanism. Retrieval and classification experiments demonstrate that,  among the presented DP-RP  algorithms,  \textbf{DP-SignOPORP} (where OPORP  is an improvement over the celebrated  count-sketch algorithms), performs the best in general.

In the industrial practice, DP methods were not very popular for machine learning or search, largely because the performance typically would  drop substantially if DP is applied. Since our proposed new DP algorithms have significantly improved the  performance, it is anticipated that our work will motivate a wide adoption of DP in practice. Finally, we   stress that, since our  methods are applied to the original data (i.e., feature vectors), the privacy of  downstream tasks is naturally protected.

Smooth Flipping Probability for Differentially Private Sign Random Projection Methods
Ping Li, Xiaoyun Li
LinkedIn Ads
700 Bellevue Way NE, Bellevue, WA 98004, USA fpingli98, 1ixiaoyyn996y@@mall..cmm
Abstract
We develop series of differential privacy (DP) algorithms from family of random projection (RP) and sign random projection (SignRP) methods. We first show how to improve the previous DP-RP approach using the "optimal Gaussian mechanism". Then, we propose series of DP-SignRP algorithms that leverage the robustness of the "sign flipping probability" of random projections. That is, given x >i=1 uyY0; where w is p-dimensional data vector and w is symmetric random vector, sign(æ)) only has fairly small probability to be flipped if there is a small modification on data u, depending on the specific distribution of w. This robustness leads to our novel design of "smooth flipping probability" for SignRP- type algorithms with better utility than using the standard randomized response mechanism. Retrieval and classification experiments demonstrate that, among the presented DP-RP algorithms, OP-SignOPORP (where OPORP is an improvement over the celebrated count-sketch algorithms), performs the best in general.
In the industrial practice, DP methods were not very popular for machine learning or search, largely because the performance typically would drop substantially if DP is applied. Since our proposed new DP algorithms have significantly improved the performance, it is anticipated that our work will motivate a wide adoption DP in practice. Finally, we stress that, since methods applied to the original data (i.e., feature vectors), the privacy downstream tasks is naturally protected.
Introduction
Protecting data privacy has become urgent need and a trending research topic recently. Among many notions of privacy, the "differential privacy" (DP) [30] has gained tremendous attention both the research community and industrial applications, and has been widely applied numerous tasks such as frequency estimation [32, 26), clustering [36, 34], regression and classification [14, 85), DP- SGD [1, 35], principle component analysis [40], empirical risk minimization [15], graph analysis [33], matrix completion [8, 45], etc. In a machine learning model, there are several choices on when to deploy differential privacy (DP): (a) at the data collection/processing stage [84, 81, 19]: (b) during the model training stage [1, 78]; and (c) on the model output (or summary statistics) [29]. Among them, applying DP as early as the data collection stage provides strong protection in the sense that the subsequent operations or outputs will become private by the post-processing property of DP. Moreover, when the data holder needs to release the data to third third-parties, publishing mechanism (at an early stage) becomes necessary.
privacy-preserving data
In this paper, focus the differential privacy of the broad family of random projection (RP) methods, including RP, sign random projections (SignRP) and count-sketch-yye algorithm. Our algorithms can be applied data publishing and processing for downstream machine learning tasks.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Random Projections (RP) and Sign Random Projections (SignRP)
In practice, data compression and dimension reduction techniques can be crucial when dealing with massive hiigh-dimensiona) data. The random projection (RP) method is an important and fundamental dimensionality reduction algorithm. Denote u e R as the data vector with p features. With some & (and typically k < p), we define the random projection of u as
1 W u, W WER' E
X
The entries of the random matrix W typically follow the Gaussian distribution or Gaussian-lin -ike distribution such as the Rademacher (symmetric Bernoulli) distribution. It has been well-understood that, with a sufficient number of projections (k), the distance between two vectors (using the same projection W) is preserved within small multiplicative error with high probability. The dimension- ality reduction and geometry preserving properties make RP widely useful in numerous applications, such distance estimation, nearest neighbor search, clustering, classification, compressed sensing, permutation recovery, etc. [46, 44, 22, 6, 2, 37, 24, 76, 10, 28, 56, 38, 23, 21, 60, 68, 75, 82, 83).
While RP is able to reduce the dimensionality, storing and transmitting projected data might still be expensive for large datasets. One can further compress the RPs by quantiratio/ddiseeeiiziiinn, where only use a few bits to represent the projected values [41, 9, 27, 89, 54, 58, 50, 55, 61, 62]. In this paper, we will consider the differential privacy of the extreme case of sign (1-bit) random projection (SignRP), also known the "SimHash" [13, 24], where only the sign of the projected data is stored. The signs still preserve the angle/cosine information. SignRP has been widely used for approximate near neighbor (ANN) search [39] by building hash tables from the bits [44, 13, 71]. RP and SignRP can also be extended to non- non-linear random features [69, 63, 64].
1.2 Count-Sketch and OPORP: Efficient RP-type Alternatives
The celebrated sketch [12] can be viewed as a highly efficient RP-type algorithm, because, as an option, it only requires "one permutation + one random projection" (OPORP) [57], as opposed to projections in RP. Applications of count-sketch include graph embedding [80], word image embedding [16, 87, 3, 72, 86), model & communication compression [79, 17, 70, 42, 59], etc. The recent work by [57] improved the original count-sketch in two aspects: (i) using a fixed-length binning scheme makes the algorithms more convenient and also reduces the variance by factor of p-k. (ii) the projected data (i.e., vectors in k dimensions) should be normalized before they are used T-T
to estimate the original cosine which also substantially reduces the estimation variance, essentially from (1 + p²)/k (u-norrallzzd) to (1 - p²)² /k (normalized).
The main contributions of this work include the following:
In Section 3, for DP-RP, we first revisit the prior work [49] on the (e, 6)-D random projection based on Gaussian noise addition (called DP-RP-G). Then we incorporate the optimal Gaussian mechanism and propose an improved method DP-RP-G-OPT. We also develop DP-OPORP based on the optimal Gaussian mechanism.
In Section 4, we propose two algorithms for privatizing the (1-bit) Dignig.RP. The first method, DP- SignRP-RR, is based on the standard "randomized response" (RR). Then, we propose an improved method named DP-SignRP-RR-smoon 'smooth flpppig probability". thanks to the robustness brought by the "aggregate-and-sige operations of SignRP. Finally, we extend the idea of smooth flipping probability to OPORP and show that DP OP-SignOPORP is more advantageous in terms of privacy.
based on a proposed concept of
In Section 5, we conduct retrieval and classification experiments on benchmark datasets. For full-precision methods, the proposed OP-OPORP substantially improves prior method DP-RP-G. For the 1-bit RP variants, the suggested DP-SignOPORP can outperform DP-RP and DP-OPORP especially when is not large (e & S 5). Our results also verify the advantage of smooth flipping probability over the classic bit flipping strategy.

---

2 Background on Differential Privacy
Throughout the paper, || || and || |/2 are the 1 and norms, respectively, and || will denote the l2 norm if there risk of confusion. Let u E U be the data vector of a user where U denotes the data domain. In this paper, we consider real-valued data vectors with bounded range, i.e., 2, = [-1, convenience. We also assume ||u|| > O, i.e., there is no all-zero data sample. The formal definition of differential privacy (DP) is given as follows.
1, 1 for
Definition 2.1 (Differential Privacy [30]). For randomized algorithm M .U Range(M), for any two udjacent datasels and v', it holds that
Pr(M(u) Oj S e Pr(((u))) E
(2)
for 40 C. (Rnge(MM) and some e, 2 0, then algorithm M is called (e, d)dfferrnntt private. If 6 M is called e-differentially private.
In this work, we follow the standard setup in the literature of DP sketching/hashing (e.g., 17, 49, 73, 74, 88, 25, 65]) that neighhoring data vectors and w' only differ one dimension, which usually referred to as the "attribute-level DP"-an an adversary cannot detect small change in any attribute of u based on the output of the algorithm.
Definition 2.2 (3-adjaceney). Let E [-1, be a data vector. vector u' E [-1, 1]2 is said be B-adjacent to if ul and u differ in one dimension i, and |u, ui! S 3.
Data vectors u and u' satisfying Definition 2.2 are called B-adjacent or B 3-neighboring. the literature (e.g., [49]), = 1 is typically used. We allow general / to accommodate the practical needs. Moreover, the concept sensitivity important for the design of DP noise addition mechanisms.
Definition 2.3 (lz-sensitivity). Let Nb(u) denote the neighbor set u, and (()) = {(u, w/) : u' e Nb(u), u, u' U} be the collection of all possible neighboring data pairs. The l2 lz-sensitivity of function f u + IR* is defined as 222
(EN (l] - f(u')ll2
The following composition theorem of DP is also useful in our analysis. Theorem 2.1 (Composition Theorem [31]. Let Mj + IR be an (ej, D;D algorithm for j = -,,,,... 1,...,k. k. Then M(u)
is (E)=1 C. E,
3 Revisiting Differentially Private Random Projection Methods
We first revisit the DP noise addition mechanism for random projections and show how to apply the optimal Gaussian mechanism [4] to improve prior methods. We also propose a DP algorithm based on a variant of count-sketch which is computationally much more efficient than dense projections.
3.1 Gaussian Noise Mechanism for DP-RP
Let N {u, u' Eu E Nb(u)) be the collection of all possible B-neighboring data pairs, where Nb(u) is the neighbor set of u. For p-by-k projection matrix W, the lz-sensitivity of the RP (1), according to Definition 2.3, can precisely computed by
1
A
| u WT u' Vk (L,)))N
3 max
3 max [Wa.ll2. Vk s=.....
where WR.:) denotes the i-th of W. As such, the DP noise level depends on the choice of projection matrix W. A comparison Rademacher vs. Gaussian projection in DP-RP method can be found in Section I. With this calculation, the general Gaussian noise mechanism for DP-RP is summarized in Algorithm I. We present the algorithms for a single data point u, and the procedure applied to every data vector in the database (with same W but independent noise). After random projection, we simply add a random Gaussian noise vector following iid N(0 o²) to the projected data. The following "DP-RP-G" result is known in the literature.
Theorem 3.1 (DP-RP-G [49]). Let 2ig be defined in (3). For any 0 and 0 < < 1. DP-RP-G in
Algorithm 1 is (e, DP DP if > A v /2(0g(11/))tc)
3

---

Algorithm 1: DP-RP-G and DP-RP-G-OPT
Input: Data a E [-1, 1,1 privacy parameters 0, (0, 1), number of projections
2 Output: (e, 6) -differentiall private random projections ā E IR*
3 Apply RP æ = V W where W IP** has iid entries from (0, 1) or Rademacher
Compute the sensitivity 22 by (3)
Generate the random noise vector G R whose entries iid samples from NVO where is obtained by Theorem 3.1 (DP-RP-G) or Theorem 3.2 (DP-RP-G-OPT)
Return E x G
Remark 3.1. Note that in implementation, 22 computed by (3) using the realization of the projection matrix W. In Appendix A, we provide a high probability bound on La and more analysis and discussion on the Laplace mechanism for DP-RP.
In Theorem 3.1 (as well as the classical Gaussian mechanism, e.g.. [31]), the analysis the noise level based on upper bounding the tail Gaussian distribution. It can be improved by computing the exact tail probabilities. [4, Theorem 8] proposed optimal Gaussian mechanism based on this idea, which allows us to improve Theorem 3.1 and obtain the DP-RP-G-OPT method as follows.
Theorem 3.2 (DP-RP-G-OPT), Suppose D2 is defined as (3). For any > O and < < 1, DP-RP-G-OPT in Algorithm achieves (e, (e,D) if a² where o* is the solution the equation
( 20
60
e
D2
60
= 8,
4
20
42
where (b-) is the edf of the standard normal distribution.
Remark 3.2. For both Theorem 3.2 and Theorem 3.1, the Gaussian noise level is a = O when which is rate optimal [4]. Essentially, Theorem 3.2 reduces the noise variance of Theorem 3.1 by analyzing the tail probability exactly.
O, and O (2) when
3.2 DP-OPORP: A More Efficient Alternative
The standard random projections (1) require projections. We can reduce the cost from (kp) to (pp) by count-sketch: "binning + Rademacher RP". Basically, we split the data entries into bins, and apply RP each bin to generate i samples. [88] studied noise injection mechanism for count-sketch [12]. Recently, [57] proposed OPORP (One Permutation + One Random Projection), an improved variant of count-sketch using fixed- axed-length binning and the normalized estimator. The steps are summarized in Algorithm 2. Note that the output can be la normalized to reduce variance.
Algorithm 2: OPORP: count-sketch with fixed-length binning
Input: Data vector u E RR; Number of projected samples k
Output: OPORP samples
3 Apply a permutation II [p] + [p] to u to get UnT
Split the p permuted data columns into i consecutive length-p/K bins: un = [u
...., "1
(k)
$ Generate a vector to E IR following Rademacher distribution, denoted as w (L) .... w
Return & projected samples by 2; = w(+) "n for i 1,....
For OPORP, the sensitivity 22 = 3, due to the binning and Rademacher projection: changing one coordinate of by 3 leads change of B in term of distance between the projected vectors.
Theorem 3.3 (DP-OPORP). Adding noise from iid (O, a²) OPORP (the output of Algorithm 2) achieves (c, DDP, where a is the solution to (4) with 2 3.
The advantages of DP-RP and DP-OPORP over the approach of adding Gaussian noise to raw data for inner product estimation are theoretically justified in Appendix C.

---

DP-SignRP: Differentially Private Sign Random Projections
We now propose main algorithms that output SignRP with DP guarantees. Firstly, analyze the standard randomized response (RR) technique, DP-SignRP-RR, under Gaussian random projections. Next, we propose the concept of "smooth flipping probability" and develop Pe-SSinRP-RR-smooee as an improvement. Finally, we propose DP-SignOPORP that combines all the techniques.
4.1 DP-SignRP-RR by Randomized Response
Algorithm 3: DP-SignRP-RR
Input: Data u E 1]:; 0, d 1; Number projections k; norm lower bound m Output: Differentially private sign random projections
3 Apply RP by x = WTu, where W Pp is random (N, 1) matrix
Let N+ 6, p) be computed as in Proposition 4.3
sign(1z); with prob. e1 for j = L..,. with e' (/N Compute 5 sign((r)) with prob.
+1
Return 5 the DP-SignRP of
We develop DP-SignRP-RR based on the classic randomized response (RR) mechanism [77, 31]. As summarized in Algorithm 3, after we apply random projection x W'',, u, we take sign(x).
_ and flip the sign with probability -. Then, for each sj, we keep the sign with probability न
Here é' = / N where N+ (m, 6, k) p) is an upper bound the number of different signs (among k signs) of Proposition 4.3. Here, m is a lower bound on the l2 norm of the data, i.e., ||u]|| 2 m for all u U.
W u and x = W ul for any 3-adjacent (u, w'), which will be derived later in
The final output is after perturbing by the above procedure.
Theorem 4.1. Algorithm 3 (e, O)DP.
Proof. For any data point E U and its B-adjacent neighbor u', denote & = sign(WTW u) E {-1,+1} s' = sign sign u') E [-1,++1] +1] and let 3 and 5' be the corresponding randomized sign
vectors output by Algorithm 3. Denote S = {i 8, + s/} and S = k] S. For any vector y
{-1,+1}* define S. [j E S 8j y S₁ {j S s, + y, S {je S 8 Vj
and Sf = (j E 55: 5; # }. By Proposition 4.3, we know that the event {1S) S N (m,, 8, k)
happens with probability at least 5. In this event, we have
Pr(š y)
I ec IL a I o1 IL a'+1 Hiess ex +1 IsESs J4 Iises tt IlEs e't1
log Pr(5' = y)
log
H e' = | < N
< logg
T e'+1
Since this event occurs with probability at least 6, the overall procedure is (c, 5)DP)
4.1.1 The flipping probability and calculation of N+
In the proof of Theorem 4.1, N4 is upper bound on = {i: S3 + s/}} where sign(WTu) u) and wWnn u') for neighboring data (u, u'), which determines the flipping probability thus the utility. Next, we analyze N+. The following is useful lemma; all proofs are placed in Appendix E.
Lemma 4.2. Let XI...,,X, X, be iid NO., of) variables. Let N o be another Gaussian random variable with arbitrary dependence structure with X;'s. 's's Let =az/o, 1. Then
[X] > 5 J 2p/22(() ( (f))r)))(((ftdtt
P+(r.p) := Pr( max (=I....p
(5)
where d(x) and (xx) are the standard Gaussian pdf and cdf. respectively.
5

---

Equipped with Lemma 4.2, we can derive N+ in Algorithm 3, an upper bound on the number of projected signs that are possible change when is replaced by any neighboring data vector u'.
Proposition 4.3 (Bound N+). Suppose u E [-1, and 3 I |ull. Denote r = TTlll & and Fi =
P+ [ ( P) in (5). Denote s = sign(W" u) and s' = sign( W u') for B-neighboring (u, u'), and (i: 8j + 8.)) Then with probability 8, |S] S N ([| 6, K; p) (6; F willl.p k), where B (5; Full,pp k) represents the inverse edf of Binomial distribution with rate Fl and trials.
Since Fli (r, p) is increasing function in ///1ul|, N4 would be smaller if //1|u]] is smaller. Therefore, in JP--ignnP-RR the probability of flipping the true SignRP, c=78+ would be smaller when the data norm (or, its lower bound m) is large compared with B.
4.1.2 Utility in angle estimation by DP-SignRP-RR
Define the DP-SignRP-RR estimator of the angle between data points and
(e + 1)2 Σ 116; = 82g (e 1)2 [ec 1)2 3-1
2e
Inn T(1 - PnR), where PRR
(6)
Theorem 4.4. petp= cos(u, v) and = cos cos (p)- Run Algorithum 3 with N given in Proposi- tion 4.3 and define the DP-SignRP-RR angle estimator by (6). We have BlθRal 6. As k + oo,
ORR (0, Vaa ), with
2x2ee/N+ 4T2e2e/N+
+ VRR - 0) + (ce/N+ 1)2 (ee/N+ -
Theorem 4.4 says that R is an unbiased estimator and asymptotically normal. Compared with 0(m-8) the variance of the cosine estimator from nPn-DP SignRP [41, 13], we see that Onn incurs an k
2e//N+ [e"/$4-1) 1)
2620/N_ (6
This quantity increases gets smaller, illustrating the utility-privacy trade-off of DP-SignRP-RR.
extra variance (i.e., utility loss) of K
Optimal projection dimension k* Since by Proposition 4.3 we know that N x Fllillap roughly, the term
2/ 2020/0- (1) (e-/N-11j would increase with k. Therefore, there exists optimal k*
that minimizes the estimation variance. When k is sufficiently large, we have
VRR k
0 0) 2nd F
Tull.p
8 F Iull.p A-
4
using the approximation that ex - expression, we compute the derivative and set it as zero:
when is small. To find the optimal k minimizing this
(( π
0)
2x 2x F2
24T F4 wll.p
Fi 12
el( -
0
A22
FluilIP
This analysis suggests the optimal k of OP-SignRP-RR- is larger when: (1) is large; (2) Filad ip is small, which is typically true when the norm of the data is relatively large.
4.2 Smooth Flipping Probability: the Benefit of Robustness
Next, we improve OP-SignRP-RE based on a novel tool which we call "smooth flpping The idea is inspired by the "smooth sensitivity" for DP noise addition [66], which essentially says that, the farther u is from high "local sensitivity" region, the less noise needed for u to achieve DP. The local sensitivity at specific data point is defined as T.S(u) maxx'eNbr Il.(u) f(u')l which differs from Definition 2.3 in that local sensitivity only considers the local neighbors of u.
flippin probability".
What is the "local perturbation" for flipping the SignRP? Consider one projection x, W u and 8j sign(2z). For neighbor w' of u, denote x²; W[:ij] ut and s¹ sign(a)). By 8-adjacency,
of is possible to be different from sy only if |zz] max W.yl. This implics:

---

When |ayl < max;=1.....p Wayl the "local sign flipping" is required, since s/ may differ from 8j. We can apply the standard RR: keep 8j with prob, e5/h.I and flip otherwise.
<r/k
When |zy] 3 max. Way there does not exist u' (N(()) such that s o 8j- Thus, the "local sign flipping" is not needed. However, we do not perturb 8,, DP would be violated since si might need random flipping. Instead, probability" which applies less perturbation for points far away from the "high perturbation region", i.e., the regime where |z,| max,=1....pp [Weyl- Specifically,
use a "smooth flipping
define Lj
max: W., ]- The probability of keeping the sign sj is P) . where ej
|xyl
e
c.c. It be shown (e.g., in the proof of Theorem 4.5) that this flipping probability is x
"smooth": for Vu, u' that are neighbors, p(()) I e pf which justifies its name.
Algorithm 4: DD-SiinRR--R--smonee using smooth flipping probability
Input: Data u E [-1, 0; Number of projections
Output: Differentially private sign random projections
3 Apply RP by x = W u, where W E Bp*k is a random N matrix
Compute Lg maxp Wayl for 1,...h
lxd1
sign(x,); with prob. 5
Compute 8
o +1 for 1,,,.. k, with ej 4e
sign(zz), with prob.
Return the DP-SignRP of
The concrete steps of DP-SignRP-RR-smoon are summarized in Algorithm 4. Note that, the above </ two cases can be unified into one, since ot/441 is the smooth flipping probability with L;=11 1. In Figure I, we provide illustrative example of the smooth flipping probability (red) and the "local flipping prob- ability" (green) discussed above. The global upper bound (black dash) corresponds to the standard ran- domized response. The local flipping probability only non-zero at L = 1. The proposed smooth flip- ping probability is non-zero for all L > O, but keeps shrinking exponentially as L gets larger, i.e., as the projected value is farther from
0.3
Flipping Probability
smooth flip prob.
0.2
local flip prob.
-.oo global flip prob.
0.1
0
3
5
8
Figure 1: The smooth flipping prob., local flipping prob., and the global upper bound. = L is from Algorithm
Theorem 4.5. Algorithm 4 achieves e-DP.
Comparison with DP-SignRP-RR (Algorithm 3). In terms of algorithm design and privacy, P--SinnRP-RR-smovv (Algorithm 4) has two advantages over the standard DP-SignRP-RO method:
1. DP-SignRP-RR-smood does require (assume) lower bound on the data norms; -mmsoot 2. DP-SignRP-RO --- smooth achieves e-DP, while DP-SignRP-RR only guarantee (e, 0)-D.
Note that Algorithm can also achieve cDP if we set the flipping probability to be c</$41 (for all projected values). This corresponds the global upper bound (black dotted line) in Figure Thus, SSiignR--RR-smon requires much smaller flipping probability than DP-SignRP-RR.
DP-SignRP with Rademacher projection. Similar to DP-RP, the flipping probabilities also depend on the projection matrix W through N4 (for DP-SignRP-RR and L. (for -ignoo--R--moothh In Appendix B.2, we analytically show that Rademacher RP requires smaller flipping probability than that of Gaussian RP for both variants.
7

---

4.3 DP-SignOPORP with Smooth Flipping Probability
We incorporate the smooth flipping technique develop DP-SignOPORP, as given in Algorithm with two variants. DP- DpP-SigOOPOR--ER -RR is based on the standard randomized response (RR), while Dp--SinOOPOR--RR-mmonn an improved version with our proposed smooth flipping probability.
Algorithm 5: DP-SignOPORP-RR and DD-SignOPORP-RR--mmoon
Imput: Data u E [-1, 0; Number of projections A
2 Output: Differentially private sign OPORP
Apply Algorithm with a random Rademacher projection vector to get the OPORP x DP-SignOPORP-RK
sign(x;); with prob. sign(r,), with prob. for j = I,.... k
Compute 8j =
SignOPOORPRR-smooon
5 Compute L3- = |m for j k...,
sign(z)), with prob.
Compute 8j
e for l,..,, with ej Laee
sign(zz), with prob. For 8j 0, assign random coin in {-1,1} 8 Return 5 as the DP-SignRP of
e11
Benefit binning. In Algorithm 5, the key difference compared with DP-SignRP methods is that, the N_ (in Algorithm 3) or I (in Algorithm 4) is removed from the flipping probability formulas, which is significant advantage in privacy. This improvement is result of the binning step. By Definition 2.2, two neighboring data w' and u differ in one coordinate. For SignRP, since each projected data is an aggregation of the whole data vector, when we switch from w', (in principle) all k projections are possible to change. In contrast, in OPORP, since each data entry appears in only one bin, u' will only cause exactly one projected output to change, which enhances privacy.
Theorem 4.6. Both variants Algorithm 5 are c-D..
Proof. The proof follows the idea of the proofs of DP-Sign OP-SignRP methods, but we need to additionally consider the empty bins. Denote x and x' as the OPORP from Algorithm using a same random vector and let
sign(x)), s' sign(x'). Suppose u and u' differ in dimension i, and dimension i assigned to the jt bin with j = (f)//pp/))) where क : [p] + [y] is the permutation in OPORP. For any y E 1} it is easy to see that to compute log Pr(E=y)
pr(s'=y)> it suffices to look at the j th output sample because other probabilities cancel out. For the -* sample, when 8j* * 0 and s'y- * 0, by the same arguments as in the proof of Theorem 4.5, we know that e < Pr(s.))= (r(s(.)= < e
E 13, for both variants (DP-SignOPORP-RE RR and DP SignOPORP-RR--moon
When one
of sy- and s's- equals is also easy to see that (assume sj- and s/s_ a random coin)
Pr(83))= 15 Pr(s/.)
2et
Pr(8f)) - -1 2 Pr(
e +1 Se,
e
e +1 S1.
This holds for both variants. In particular, this case corresponds to Ly- 1 for the smooth flipping probability. This proves the theorem.
Multiple repetitions. In Algorithm 5 Line if OPORP generates an empty bin (i.e., x, 0), we must assign random sign to it in order to maintain DP. This tends to undermine the utility since random coin does not provide any useful information about the data. To avoid too many empty bins, one simple way is to repeat the DP-SignOPORP (with smaller k) for > 1 times, and concatenate the output vectors [12]. For example, the target & = 256, we may run Algorithm 5 for / times, each time with 256/4- /4- 64 projected values and privacy budget /4.. We still obtain a length-256 bit vector with cDP by the composition theorem. In the experiments, we will see that this strategy may improve the overall performance of DP-SignOPORP.

---

Experiments
We present experiments on retrieval and classification tasks demonstrate the effectiveness of our proposed methods. We compare the following algorithms:
Www-data-G-OPTI adding optimal Gaussian noise with sensitivity 3 to the original data, which is the most basic DP method for privatizing the original data.
DP-RP-G (Algorithm Theorem 3.1): Gaussian DP-RP with the Gaussian mechanism.
DP-RP-G-OPT (Algorithm Theorem 3.2): DP-RP with Gaussian random projection matrix and the optimal Gaussian noise.
DP-OPORP (Theorem 3.3): one permutation + one random projection with Rademacher projection vector and optimal Gaussian noise.
DP- OP-SignOPROP-RR and DP-SignOPORP-RR -mossoohh (Algorithm 5): signed OPORP with standard randomized response and with smooth flipping probability, respectively.
As noted Section 4.3, due binning, OP-SiinOPORP substantially better than Di-SignRP. Thus we present results for DP-SignOPORP in our experiments (and only B 1 for conciseness).
Similarity Search. We first the methods in similarity search problems, using two standard image retrieval datasets, MNIST [53] and CIFAR [51]. For both datasets, we treat the training set as the database, and use the samples from the test set as the queries. We set the ground truth neighbors for each query as the top-50) sample vectors with the highest cosine similarity to the query. To search with DP-RP (and DP-OPORP), we estimate the cosine between a query and a sample point by the cosine between their corresponding output noisy projected values. We report only the precisions (and please see Appendix for other metrics), averaged over 10 repetitions.
0.8
0.8
0.8
DP-OPORP
DP-OPORP
DP-OPORP
DP OPT DP-RP-G
BP-RP-G-OPT
DP-RP-G-OPT
0.6
0.6
0.6
DP.RP.G
precision@
data
precision
Raw-ddsa-G-OOF
precision
Raw-dala-G-OPT
0.4
0.4
0.4
0.2
0.2
0.2
MNIST: k
MNIST: = 128
MNIST: k 256
15
15
DP OPORP
DP-OPORP DP-RP-G-OPT
DP-OPORP DP-RP-G-OPT
0.4
DP-RP -P-OP---OPPT
precision@10
0.4
precision@10
0.4
precision@11
Raw data G OPT
Raw Raw-data-eee OPT
Raw data G GPPT
0.2
CIFAR:
0.2
CIFAR: k 128
0.2
CIFAR: k 256
15
10
20
Figure 2: Retrieval recall and precision on MNIST and CIFAR, 3 1, 10
Figure 2 shows that, result of the optimal Gaussian mechanism, DP-RP-G-OPT substantially outperforms the prior method in the literature, DP-RP-G, at all e. DP-OPORP achieve better performance than -P-RP-G-OPT and is recommended as the best (full-precision) DP-RP variant. These two methods provide much higher precision and recall than the optimal Gaussian mechanism applied to the original data (Raw-data-G-oe OPPP...
In Figure 3, we plot precision and recall of PP-SignOPORR-RR (with standard randomized response), and Op-SiinOPPORP-RR -R--s (with smooth flipping probability). We present the results with repetition 2, 4 which yield good overall performance. As we can see, (i) the proposed smooth flipping probability considerably improves the standard randomized response technique, and (ii)

---

0.8
0.8
OPORP
S00-000 bad
MNIST: k= 128
MNIST: 256
3P SPOORP a SPORPP
precision@11
0.6
precision@
0.6
precision@
0.6
#
0.4
0.4
0.4
oe-egynnneeeeee tup BInDPORPP
SIyOPORR
0.2
CRORP
DodApprP DINOPORP
MNIST: 512
0
0
Raw sua OPT
0
5
10
15
20
0
5
10
15
20
5
10
15
20
Figure 3: Retrieval on MNIST with DP-SignOPORP-RR and Dp-SinOOPORP-RRRsmoool For DP-OPORP, DP-SignOPORP-RA and R 10-6
100
90
WEBSPAM: k 1024
test accuracy (%)
90
test accuracy
80
WEBSPAM: k 256
test accuracy
80
WEBSPAM: k 512
80
70
OPOSR 1-1
70
DP-SSnOOORRPP RRI.1
DP OP-SigOPPRR.PR AR 1.1
0P-SgnOPORP RR-s t-1
DP.SignGPORP.RRR AR 1.1
JP.DPORP
DP-OPORP
DP-GPORP
Ram-dera---OP
Raw-dat OPT
Rae-data-G-OPT
60
60
60
5
10
15
20
10
15
20
0
5
10
15
20
Figure 4: SVM test accuracy WEBSPAM. For (c methods, 5 = 10 10-6.
DP- OP-SignOPORP1 in general provides better search accuracy than DP-OPORP when e << 10 15. This range of e is common in the use cases of DP for providing reasonable privacy protection. Also, we note that smaller (repetitions) typically performs better with smaller but worse when is large.
Classification. We evaluate the performance of DP-SignOPORP in classification problems trained by SVM [20]. on the WEBSPAM dataset [11]. We apply the "max normalization", i.e., divide each data column by its largest magnitude such that the data entries are bounded in [-1, 1]. The SVM results are presented in Figure For this task, we plot ui-SiinOPORP with
We again observe the advantage of OP-SignOPORP over DP-OPORP, and the advantage of the proposed smooth flipping probability over the standard randomized response. Specifically, when 5, the test accuracy of Raw-data-G-OPTT is around 60% (for WEBSPAM, this is almost the same random guessing), but DP-SignOPORP can achieve 95% classification accuracy with 1024.
Conclusion
For database U E _2*P consisting of n data points, our goal is to make its random projections (RP) and SignRP differentially private-the the DP guarantee we have derived holds independently and simultaneously for every data vector U. There are works randomized algorithms that assume the randomness the algorithm are "internal" and also kept private [7, 73, 25]. We assume the projection matrix W is known/public, which is stronger in privacy and enables broader applications of the released data. Also, a "known projection matrix" is typical in the local DP setting [47, 18), since the projection matrix is created and shared among the users by the data aggregator.
In our study, we first revisit the prior work [49] on the (e, 8) random projection based on Gaussian noise addition ("DP-RP-GT Then we incorporate the optimal Gaussian mechanism and propose an improved method DP-RP-G-OPT. We also develop DP-OPORP based on the optimal Gaussian mechanism. We then propose algorithms for privatizing the (1-bit) DP PP-SignRP: "DP- TDP-SignRP--R based on the standard "randomized response" (RR), and DoP-SignRP-RR RR-PRRothh based on a proposed concept of "smooth flipping probability" of SignRP. We extend the idea of smooth flipping probability to OPORP (a variant of count-sketch) and demonstrate the advantage of DP-SignOPORP.
Experiments on retrieval and classification tasks justify the effectiveness of our proposed methods. In particular, PP-SiinOPORR outperforms other methods especially when e is not large (e.g., S 5). These results also verify the advantage of using the smooth flipping probability.
10

---

Acknowledgement
The authors would like thank several researchers from Microsoft Research: Janardhan Kulkarni, Yin Tat Lee, Sergey Yekhanin, for the helpful discussions.
References
[1] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security (CCS), pages 308-318, Vienna, Austria, 2016.
[2] Dimitris Achlioptas. Database-friendly random projections: Johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci., 66(4):671-687 2003.
[3] Eman Abdullah AlOmar, Wajdi Aljedaani, Murtaza Tamjeed, Mohamed Wiem Mkaouer, and Yasmine N. El-Glaly. Finding the needle in haystack: On the automatic identification of accessibility user reviews. Proceedings of the Conference on Human Factors in Computing Systems (CHI), pages 387:1-387:15 Virtual Event / Yokohama, Japan, 2021.
[4] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Proceedings of the 35th International Confer- ence on Machine Learning (ICML). pages 403 412, Stockholmsmässan, Stockholm, Sweden, 2018.
[5] Arnaud Berlioz, Arik Friedman, Mohamed Ali Kåafar, Roksana Boreli, and Shlomo Berkovsky. Applying differential privacy to matrix factorization. In Proceedings of the 9th ACM Conference on Recommender Systems (RecSys), pages 107-114, Vienna, Austria, 2015.
[6] Ella Bingham and Heikki Mannila. Random projection in dimensionality reduction: Appli- cations to image and text data. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages -40, San Francisco, CA, 2001.
[7] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-lindensten trans- form itself preserves differential privacy. In Proceedings of the 53rd Anmual IEEE Symposium on Foundations of Computer Science (FOCS), pages 410-419, New Brunswick, NJ, 2012.
[8] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the SulQ framework. In Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGAN Symposium on Principles of Database Systems (PODS), pages 128-138, Baltimore, MD, 2005.
[9] Petros Boufounos and Richard G. Baraniuk. 1-bit compressive sensing, In Proceedings of the 42nd Annual Conference on Information Sciences and Systems (CISS), pages 16-21, Princeton, NJ, 2008
[10] Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory, 52(():489-5k) 009899955090000000 2006.
[11] Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM Transactions Intelligent Systems and Technology (TIST), 2(3):27, 2011.
[12] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items data streams.
Theor. Compur. Sci., 312(1)33-15, 2004.
[13] Moses Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the Foiry-Fourth Annual ACM Symposium on Theory of Computing (STOC), pages 380-388, Montreal, Canada, 2002.
[14] Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In Advances in Neural Information Processing Systems (NIPS), pages 289-296, Vancouver, Canada, 2008.
11

---

[15] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12:1069-1109, 2011.
[16] Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading wikipedia to answer open-domain questions. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1870-1879, Vancouver, Canada, 2017.
[17] Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing Neural Networks with the Hashing Trick. In Proceedings the 32nd International Conference on Machine Learning (ICML), pages 2285-2294 Lille, France, 2015.
[18) Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD), pages 1655-1658, Houston, TX, 2018.
[19] Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Marginal release under local differ- ential privacy. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD), pages 131-146, Houston, TX, 2018.
[20] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Mach. Learn., 20(3):273-297. 1995.
[21] George E. Dahl, Jack W. Stokes, Li Deng, and Dong Yu. Large-scale malware classification using random projections and neural networks. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3422-3426, Vancouver, Canada, 2013.
[22] Sanjoy Dasgupta. Experiments with random projection. In Proceedings of the 16th Conference in Uncertainty in Artificial Intelligence (UAI), pages 143-151, Stanford, CA, 2000.
[23] Sanjoy Dasgupta and Yoav Freund. Random projection trees and low dimensional manifolds. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 537-546, Victoria, Canada, 2008
[24] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG), pages 253-262, Brooklyn, NY, 2004.
[25] Charlie Dickens, Justin Thaler, and Daniel Ting. Order-invariant cardinality estimators are differentially private. In Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, 2022.
[26] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems (NIPS), pages 3571-3580 Long Beach, CA, 2017.
[27] Wei Dong, Moses Charikar, and Kai Li. Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pages 123-130. 2008
[28] David L. Donoho. Compressed sensing. IEEE Trans. Inf. Theory, 52(4):1289-1300 2006.
[29] Cynthia Dwork and Jing Lei. Differential privacy and robust statisties. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 371-380, Bethesda, MD, 2009.
[30] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Theory of Cryptography Conference (TCC), pages
New York, NY, 2006.
[31] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput, Sci., 9(34))211-400 2014.
12

---

[32] Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: randomized aggregatable privacy-press srraacy-reserrvng ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1054-1067, Scottsdale, A7., 2014.
[33] Chenglin Fan, Ping Li, and Xiaoyun Li. Private graph all pl--parrise-sshoottt-attt distance release with improved error rate. In Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, 2022.
[34] Chenglin Fan, Ping Li, and Xiaoyun Li. k-median clustering via metrie embedding: Towards better initialization with differential privacy. In Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, 2023.
[35] Huang Fang, Xiaoyun Li, Chenglin Fan, and Ping Li. Improved convergence of differential private sgd with gradient clipping. In Proceedings of the Eleventh International Conference on Learning Representations (ICLR), Kigali, Rwanda, 2023.
[36] Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proceedings of the s1 Annual ACM Symposium on Theory of Computing (STOC), pages 361-370, Bethesda, MD, 2009.
[37] Xiaoli Zhang Fern and Carla E. Brodley. Random projection for high dimensional data clustering: A cluster ensemble approach. In Proceedings of the Twentieth International Conference (ICML), pages 186-193, Washington, DC, 2003.
[38] Yoav Freund, Sanjoy Dasgupta, Mayank Kabra, and Nakul Verma. Learning the structure of manifolds using random projections. In Advances in Neural Information Processing Systems (NIPS), pages 473-480, Vancouver, Canada, 2007.
[39] Jerome H. Friedman, Forest Baskett, and Leonard J. Shustek. An algorithm for finding nearest neighbors. IEEE Trans. Computers, 24(10):
1975.
[40] Jason Ge, Zhaoran Wang, Mengdi Wang, and Han Liu. Minimax-optimal privacy-preserving sparse PCA in distributed systems. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1589-1598, Playa Blanca, Lanzarote, Canary Islands, Spain, 2018
[41] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maxi- mum cut and satisfiability problems using semidefinite programming. J. ACM, 4256):1 1995.
[42] Farzin Haddadpour, Belhal Karimi, Ping Li, and Xiaoyun Li. Fedsketch: Communication- efficient and private federated learning via sketching. arXiv preprint (txXix::000.049775, 2020.
[43] Justin Hsu Marco Gaboardi Andreas Haeberlen and Sanjeev Khanna, Differential privacy: An economic method for choosing epsilon. arXiv preprint arXiv:1402.3329, 2014.
[44] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pages 604 613, Dallas, TX, 1998.
[45] Prateek Jain, Om Dipakbhai Thakkar, and Abhradeep Thakurta. Differentially private matrix completion revisited. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 2220-2229, Stockholmsmässan, Stockholm, Sweden, 2018.
[46] William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mapping into Hilbert space. Contemporary Mathematics, 26: 189-206, 1984,
[47] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. In Advances Neural Information Processing Systems (NeurIPS), pages 2879-2887, Montreal, Canada, 2014.
[48] Christopher T Kenny, Shiro Kuriwaki, Cory McCartan, Evan TR Rosenman, Tyler Simko, and Kosuke Imai. The use differential privacy for census data and its impact on redistricting: The case of the 2020 us census. Science advances, 7(41)xeabk3283, 2021.
13

---

[49] Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra. Privacy via the Johnson-lindenstern transform. Priv. Confidentiality, 5(1), 2013.
[50] Karin Knudson, Rayan Saab, and Rachel Ward. One-bit compressive sensing with norm estimation. IEEE Trans. Inf. Theory, 62(5):2748- 2758, 2016.
[51] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report, University of Toronto, 2009.
[52] Béatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, pages 1302-1338, 2000.
[53] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEFE, 86(11):2278-2324, 1998.
[54] Cong Leng, Jian Cheng, and Hanqing Lu. Random subspace for binary codes learning in large scale image retrieval. In Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pages 1031-1034, Gold Coast, Australia, 2014.
[55] Ping Li. Sign-full random projections. In Proceedings of the Thirty-Thirl AAAI Conference on Artificial Intelligence (AAAT), pages 4205-4212, Honolulu, HI, 2019.
[56] Ping Li, Trevor Hastie, and Kenneth Ward Church. Very sparse random projections. In roceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 287-296, Philadelphia, PA, 2006.
[57] Ping Li and Xiaoyun Li. OPORP: one permutation + one random projection. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 1303- 1315, Long Beach, CA, 2023.
[58] Ping Li, Michael Mitzenmacher, and Anshumali Shrivastava. Coding for random projections. In Proceedings of the 31th International Conference on Machine Learning (ICML), pages 676-684, Beijing, China, 2014.
[59] Ping Li and Weijie Zhao Gewsnet: Generalized consistent weighted sampling for scalable and accurate training of neural networks. Proceedings of the 31 ACM International Conference on Information & Knowledge Management (CIKM), pages 1188-118 1198, Atlanta, GA, 2022.
[60] Xiaoyun Li and Ping Li. Generalization error analysis of quantized compressive learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 15124-15134, Vancouver, Canada, 2019.
[61] Xiaoyun Li and Ping Li. Random projections with asymmetric quantization. In Advances in Neural Information Processing Systems (NeurIPS), pages 10857-10866, Vancouver, Canada, 2019.
[62] Xiaoyun Li and Ping Li. One-sketch-for-all all: Non-linear random features from compressed linear measurements. In Proceedings of the 24th International Conference on Artificial Intelligence Virtual Event, 2021.
and Statistics (AISTATS), pages
[63] Xiaoyun Li and Ping Li. Quantization algorithms for random Fourier features. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 6369-6380, Virtual Event, 2021.
[64] Xiaoyun Li and Ping Li. Signrff: Sign random fourier features. In Advances in Neural Information Processing Systems (NeurlPS), pages 17802-178117 New Orleans, LA, 2022.
[65] Xiaoyun Li and Ping Li. Differentially private one permutation hashing and bin-wise consistent weighted sampling. arXiv preprint 0oXiv:3306006674. 2023.
[66] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 75 84, San Diego CA, 2007.
14

---

[67] Donald Bruce Owen. A table of normal integrals: A table. Communications in Statistics- Simulation and Computation, 9(4):389-419) 1980.
[68] Stephan Rabanser, Stephan Günnemann, and Zachary C. Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. In Advances in Neural Information Processing Systems (NeurIPS), pages 1394-1406, Vancouver, Canada, 2019.
[69] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NIPS), pages 1 1177-1184, 184, Vancouver, Canada, 2007.
[70] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, lon Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. FetchSGD: Communication--fficienn federated learning with sketching. Proceedings of the 37th International Conference on Machine Learning Virtual Event, 2020.
(ICML), pages 8253-8265.
[71] Anshumali Shrivastava and Ping Li. In defense of minhash over simhash. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS), pages 886-894, Reykjavik, Iceland, 2014.
[72] Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, John Rush, and Sushant Prakash. Federated reconstruction: Partially local federated learning. In Advances in Neural Information P Processing Systems (NeurIPS), virtual, 2021.
[73] Adam D. Smith, Shuang Song, and Abhradeep Thakurta. The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. In Advances in Neural Information Processing Systems, virtual, 2020.
[74] Nina Mesing Stausholm. Improved differentially private euclidean distance approximation. In Proceedings of the 40th ACM SIGMOD MMMOD-SIGAAT-SSGAAI Symposium Principles of Database Systems (PODS), pages 42-56, Virtual Event, China, 2021.
[75] Tyler M. Tomita, James Browne, Cencheng Shen, Jaewon Chung, Jesse Patsolic, Benjamin Falk, Carey E. Priebe, Jason Yim, Randal C. Burns, Mauro Maggioni, and Joshua T. Vogelstein. Sparse projection oblique randomer forests. J. Mach. Learn. Res., 21:104:11104:39, 2020.
[76] Santosh S Vempala. The random projection method, volume 65, American Mathematical Soc.. 2005.
[77] Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, 1965.
[78] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q. S. Quek, and H. Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Trans. Inf. Forensics Secur., 15:3454-3469, 2020.
[79] Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, and Josh Atten- berg. Feature hashing for large scale multitask learning. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML), pages 1113-1120, Montreal, Canada, 2009.
[80] Jun Wu, Jingrui He, and Jiejun Xu. DEMO-Net: Degree-specifee graph neural networks for node and graph classification. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 406-415 Anchorage, AK, 2019.
[81] Bin Yang, Issei Sato, and Hiroshi Nakagawa. Bayesian differential privacy correlated data. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 747-762, Melbourne, Australia, 2015.
[82] Hang Zhang and Ping Li. Optimal estimator for unlabeled linear regression. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 11153-11162, Virtual Event, 2020.
[83] Hang Zhang and Ping Li. One-step estimator for permuted sparse recovery. In Proceedings of the International Conference on Machine Learning (ICMI.), pages 41244 Honolulu, HI, 2023.
15

---

[84] Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. Privbayes: private data release via bayesian networks. International Conference on Manage- ment of Data (SIGMOD), pages 1434, Snowbird, UT, 2014.
[85] Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Mariannn Winslett. Functional mechanism: Regression analysis under differential privacy. Proc. VLDB Endow., 5(11):1364 1375, 2012.
[86] Shan Zhang, Lei Wang, Naila Murray, and Piotr Koniusz. Kernelized few-shot object detection with efficient integral aggregation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 19185-19194, New Orleans, LA, 2022.
[87] Zhaoqi Zhang, Panpan Qi, and Wei Wang. Dynamic malware analysis with feature engineering and feature learning. In Proceedings of the Thirty-Fourty AAAI Conference on Artificial Intelligence (AAAI), pages 1210-1217, New York, NY, 2020.
[88] Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[89] Argyrios Zymnis, Stephen P. Boyd, and Emmanuel J. Candès. Compressed sensing with quantized measurements. IEEE Signal Process. Lett., 17(2):149- 152, 2010.
16

---

Contents
Introduction
1.1
Random Projections (RP) and Sign Random Projections (SignRP)
1.2
Count-Sketch and OPORP: Efficient RP-type Alternatiees
2
Background on Differential Privacy
3
Revisiting Differentially Private Random Projection Methods
3.1 Gaussian Noise Mechanism for DP-RP
3.2
DP-OPORP: A More Efficient Alternative
4
DP-SignRP: Differentially Private Sign Random Projections
4.1
DP-SignRP-RR by Randomized Response
4.1.1
The flipping probability and calculation of N
4.1.2
Utility in angle estimation by DP-SignRP-RE
6
4.2
Smooth Flipping Probability: the Benefit of Robustness
4.3
DP-SignOPORP with Smooth Flipping Probability
5
Experiments
Conclusion
10
A Analytic DP-RP and the Laplace Mechanism
18
A.1 Analytic DP-RP-G Approach: Bounding the Sensitivity
18
A.2 The Laplace Noise Mechanism for DP-RP
18
Comparison Different Projection Matrices and the Benefits of Rademacher RP
20
B.1 Rademacher Projection DP-RP
20
B.2 Rademacher Projection for DP-SignRP.
21
Comparison DP-RP and DP-OPORP on Inner Product Estimation
22
D More Experiment Results
26
Deferred Proofs
28
E.1 Proof of Lemma 4.2
31
E.2 Proof of Proposition 4.3
31
E.3 Proof of Theorem 4.4
32
E,4 Proof of Theorem
32
17

---

A Analytic DP-RP and the Laplace Mechanism
A.1 Analytic DP-RP-G Approach: Bounding the Sensitivity
According to Theorem 3.1, one will choose based on the observed A2 which is calculated according (3) for given realization the projection matrix W. For the convenience of theoretical analysis, it is often helpful to derive the criterion for choosing directly in terms of the input parameters 5, P. and k, understand and better compare the noise level. We call the corresponding algorithm be "Analytic DP-RP-G", This is achieved by bounding A2 in high probability.
Lemma A.1 ([52)). Let Y,,.., Yn be iid standard Gaussian random variables, and denote Z, E == Y,P Then for any > 0,
Pr(Z + 2 + S exp(-I)-
Lemma A.2 (Bounding A2). Let W E Bpxk be a random matrix with iid NO0 1) entries, and A2 be defined in (3). Then for any 0 8 < 1,
Pr A2 Ar 8/
2 log(p//)//////// 2loolp//)// s 6.
Proof. Let be the unit base vector with the i-th dimension being and all other dimensions being zero. For each i = I,..PP W follows iid chi-square distribution with degree of freedom. Applying Lemma A. we have that for any 8' >>> 0,
Pr (IWTe a (k 2 1og(1/0)) + 2log(1/8)) 8 Vi = l.....
Applying union bound gives
Pr max T...
| 1 + 2 (1/8)/)))/ + 2l0g(1/8))/; po'.
Setting 8 = po' and taking the square root on both sides completes the proof.
With the high probability bound on the 1z-sensitivity Ag. we have the following result.
Theorem A.3 (Analytic DP-RP-G), For any 0 and < < 2. Algorithm I achieves (c, 8DDP
when o > (/L2///oodce///////22e////////// /2/00//000000///
Proof. By Lemma A.2, know that with probability 5/2, Ag is bounded by
3 21122ooo(2220 (og(2p/))/k + 2 (og(2//))/k. In this event, by Theorem 3.1, Algorithm is (c. 6/2)-DD when 2 A2 (20) Therefore, the approach is O)DP)
We remark that, since this analytic version is built upon a high probability bound on the sensitivity, in most cases, the noise variance in Theorem A.3 will be slightly larger than the one computed by the realized/exact sensitivity in Theorem 3.1.
A.2 The Laplace Noise Mechanism for DP-RP
We briefly discuss the Laplace mechanism for DP-RP (and why we did not use it).
Definition A.1 (1 ((y-sensitivity) Let Nb(u) denote the neighbor set of u, and N(4) {u, u') w' Nb(u), u, u' E U} be the collection of all possible neighboring data pairs. The ( Ii-sensitivity of function f ++ I2* defined as A max ll.((u) f(u')l1-
Theorem A.4 (Laplace mechanism [30]), Given any function f 11 + RR and e > 0, the randomized algorithm M(u) f(u) + (Zi,.., Z&) c-DP, where Zi..., Zv. follow iid Laplace (11/c) The centered Laplace distribution with scale X has density function g(z) 2x - -
18

---

Algorithm 6: DP-RP-L
Input: Data a E [-1, 1j" privacy parameters 0, number of projections &
2 Output: e-differentially private random projections IR*
3 Apply RP x = V W where W R a random N NO, 1) matrix
Compute sensitivity A by Definition A.1
Generate iid random noise vector IR* following Laplace( A!)
Return 0 2
By Theorem A.4, one may add Laplace(X) noise to the projected data with X = A1/e to achieve c-DP. For completeness, we detail the approach in Algorithm 6, which the same as Algorithm except for the noise added. A is the di-senittvvity for given W given in Definition A.I: A Vi mmaxx=1,...pp [Wi,1ll. Each term the maximum operator is a sum of k iid standard half- normal random variables (Y | where X is standard normal). The readers might be interested in a comparison between the noise level of the two noise addition mechanisms, i... DP-RP-G and DP-RP-L. To observe the dependence of the noise level À c, and p, derive tail bound on the l1-sensitivity. We first establish the following lemma.
Lemma A.5 (Half-normal tail bound), Let XI..., Xn be iid N(0, 1) random variables and let Y; = | Vi. Denote Z >i Y, Then for any t >> 0, it holds that
Pr(Z 2 2n2 log + 2mt) S exp(-t).
Proof. By the Markov inequality, we write (with some > 0)
E Yi exp(Ct)
Pr(Z 2 2) = Pr(exp(( Σ Yi) 2 exp(Ci)) S
By the independence Y, and the moment generating function of half-normal distribution, we have
E(exp(CY.)] = exp( ?
exp( n²²
E E(exp(S
Σ Yl
II
(24(())) exp(
2 + log (4)(
1=1
n6²
S exp(
+ n log 2).
2
Hence, we have
n6? 2
Pr(Z 2) exp(
tÇ n log
which is minimized at Ç f
n' leading to
12
Pr(Z expl
+ n log 2).
2n
Taking / 2nn log 2nt completes the proof.
Using Lemma A.5, we obtain a high probability bound on the d--seniitivity as follows. The proof is omitted since it is similar to the proof of Lemma A.2.
Lemma A.6 (Bounding A1). Let W E R be a random matrix with iid N(0, 1) entries, and A be defined in Definition A.I. Then for any
1,
Pr A 2 B 2k log 2 log(p/0) < 6.
It is important point out that, unlike in the Gaussian mechanism, simply inserting the upper bound in Lemma A.6 to replace the (exact) A the noise level of (aplace(A1/e) Algorithm does not provide pure e-DP. In other words, must compute the actual A₁ by Definition A. for realization
19

---

of the projection matrix W. This is because, using the high probability bound of A would introduce failure probability (i.c., when the actual A larger than the bound) which violates e-DP.
Comparison with DP-RP-G-OPT, Lemma A.6 provides an estimate of the noise level required by the Laplace mechanism. We can roughly compare DP-RP-L with DP-RP-OPT terms of the noise variances, which equal o² for Gaussian and 2X for Laplace, respectively. Lemma A.6 shows that in most cases, the Laplace noise requires À = O x Recall that in DP-RP-G and DP-RP-G-OPT, the Gaussian noise level σ = O when e - and Ø = O when + co. Thus, the Gaussian noise would be smaller with relatively small c, and the Laplace noise would be smaller only when 92(k), which is usually too large to useful since in practice & is usually hundreds to thousands. As result, would expect DP-RP-G methods to perform better than DP-RP-L in common scenarios. Therefore, in this work, we mainly focused on the Gaussian mechanism for DP-RP noise addition.
B Comparison of Different Projection Matrices and the Benefits of Rademacher RP
Besides Gaussian random projection, can also adopt other types of projection matrices which might even work better for DP. The following distributions of Way are popular:
The uniform distribution, v x [-,, The v3 factor is placed here to have E(wi,) by following the convention the practice of random projections.
The "very sparse" distribution, used in [56]:
-1 with prob. 1/(2s)
Wij = V8 x
with prob. 1 1-1/s,
+1 with prob.
1/(2s)
which generalizes [2] (for and 3). Note that when "symmetric Bernoulli" distribution or the "Rademacher" distribution.
is also called the
Next, we compare these various types of projection matrices and show that Rademacher (symmetric Bernoulli) random projection is superior to Gaussian random projection for both DP-RP and DP- SignRP that less perturbation is required to achieve the same privacy level.
B.1 Rademacher Projection for DP-RP
From Theorem 3.1 and Theorem 3.2, it is clear that the noise magnitude of Gaussian noise in DP-RP directly depends on the la-sensitivity A2, which, according to (3), equals the largest row norm the projection matrix W. Among the above mentioned distributions, the dense Rademacher projection (s = 1 in (7)) has A2 = vे x Vk B which is independent of p. This could be much smaller than the dense Gaussian projection (i.e., DP-RP-G-OPT)
1.3
Gaussian
Gaussian
uniform
uniforrm
S 1
1.2
S =
1.2
3
S = 10
S = 10
1.1
1.1
0
256
k
512
10
200
400
600
800
1000
10
200
400
600
800
1000
p
p
Figure 5: The l2-sensitivity 22 (3) for different types of random projection matrices against the data dimensionality p. at 256 and &o 512, respectively.
20

---

In Figure 5, we numerically simulate the 42 of different projection matrices, which shows that the Rademacher projection produces the smallest sensitivity. This, when plugged into the optimal Gaussian mechanism (Theorem 3.2), leads to smaller Gaussian noise variance needed.
B.2 Rademacher Projection for DP-SignRP
From our analysis, is clear that the flipping probability of DP-SignRP (both DP-SignRP-RR and DP-SignRP-RR (R-RP-t essentially depends on how concentrated the projected data is around zero. Particularly, N+ in Algorithm 3, as given in Proposition 4.3, high probability upper bound on Binomial random variable with success probability Pr(3 ma..= |ayl 2 w ul) with | al
(0, 1). In Algorithm 4, L 1,= max W,y 1. For both quantities, smaller value leads smaller sign flipping probability and thus better utility.
N_ in SignRRRR-- We first consider the N+ in Algorithm which determines the flipping probability c//++41 +1 Particularly, N+ in Algorithm 3, as given in Proposition 4.3, is a high probability upper bound on Binomial random variable with success probability
P+ Pr max i=I....
|ws|
2
|w unl (l)
(8)
where w is the p-dimensional projection vector. When is sampled from the Rademacher distribu- tion, i.e., wa E (1] with equal probabilities, the probability calculation can be simplified:
P., = Pr (8 max 1=
P
P
B |
w
= Pr 3
2Φ
1. (9)
Based on the central limit theorem, the normal approximation (9) is accurate unless p very small. Recall that, when wy 's are sampled from the Gaussian distribution, we can calculate an upper bound (20), which re-written as below:
Pt. Pr (B max 1_ 1e
{ 2p(20(1) (2 1)(())l
Σ waua|
S
(10)
Next, we provide a simulation study to justify the approximation and compare different distributions in terms of their impact the probability (8), for 8 simulate the data as a p-dimensional vector of uniform random numbers sampled from wnifl-1, We experiment with five different choices of w: the standard Gaussian, the uniform, the "very sparse" distribution (7) with
well as B 0.1. For simplicity,
1, 3, and s = 10. We vary from 10 to 1000. For each case, we repeat the simulations 10" times to ensure sufficient accuracy. Figure verifies that the two approximations (9) and (10) are accurate. In Figure 7, we provide the curves for more types of projection matrices. From both figures, we clearly see that using the Rademacher projection can considerably reduce (8) compared with Gaussian (and other) projections, leading to smaller N value. This typically implies better utility.
Lj in DP-SigHRP-RR-smoode Similarly, numerically evaluate the Lj in Algorithm 4. We run Algorithm 4 with & = 512, which gives 512 Ly values. In Figure 8, we plot the proportion (or the approximated distribution) of the values of L, among & projections. As see, Rademacher projection produces least number of small Lj values, and largest number of higher Lj values. As the exp( + larger L2 leads to smaller probability of sign flipping. Hence, Rademacher is again the best choice for the projection matrix.
smooth flipping probability equals
21

---

0.7
0.08
Gaussian
Gaussian Rademacher
0.6
8 0.1
Rademacher Approx
0.5
0.06
Approx
Prob
0.4
Prob
0.04
0.3
0.2
0.02
0.1
10
200
400
600
800
1000
10
200
400
600
800
1000
p
p
Figure 6: Simulations for evaluating (9) and (10), using two choices for w: the Gaussian distribution and the Rademacher distribution (i.e., (7) with 8 = 1). We plot the two upper bounds (9) and (10) as black dashed curves, which both overlap with their corresponding simulations.
0.7
0.08
Gaussian uniform
Gaussian
0.6
=
3 0.1
uniform
0.5
S
0.06
Prob
0.4
S = 3
Prob
=
S 10
0.04
10
0.3
0.2
0.02
0.1
0
10
200
400
600
800
1000
10
200
400
600
800
1000
p
Figure 7: Simulations (same in Figure 7) for evaluating (8), using five different choices for wt the Gaussian, the uniform, the "very sparse" distribution (7) with s 1,3 and 10. 8 = is the Rademacher distribution. The data vector is simulated by sampling each entry from
C Comparison of DP-RP and DP-OPORP on Inner Product Estimation
In this section, we thcoretically compare DP-RP and DP-OPORP. In Section B, we have shown that Rademacher projection requires lowest noise magnitude. Thus, we consider DP-RP with Rademacher projections here. For clarity, summarize the algorithm in Algorithm 7. We name it "DP-RP- G-OPT-B", where "G" stands for the Gaussian noise mechanism and "B" stands for "symmetric Bernoulli" projections.
Algorithm 7: DP-RP-G-OPT-B
Input: Data u E [|1, privacy parameters e 0, (0, 1), number of projections 2 Output: (c, -)iffffrretttllly private random projections à E &
Apply RP x 1 T u, where W IR is random Rademacher matrix
vI
Generate iid random noise vector G E IR following (0,, o²) where a is obtained by
Theorem 3.2 with 4g
$ Return v = x +
In our analysis, for simplicity we assume the data are normalized, i.e., the data vector has la norm equal to 1. In this case, the inner product is also the cosine. The baseline method is the most straightforward: we optimal Gaussian noise to each dimension of the original data (Raw-data- G-OPT). For this strategy. the sensitivity is also 22 3. This means, when we compare all three methods: Raw-data-G-OPT. DP-RP-G-OPT-B, and DP-OPORP, the noise level the same. This makes it convenience to conduct the comparisons, from which we can gain valuable insights.
22

---

0.5
0.15
Gaussian uniform
B
Gaussian
0.4
B
uniform
Proportion
S 1
Proportion
0.1
S 1
0.3
S = 10
S = 10
0.2
0.05
p 1000
p 100
0.1
0
8
10
10 L
15
20
L
Figure 8: Simulations for evaluating I.j in Algorithm 4, using different choices for w. 8 the Rademacher distribution. Left: = 100, right: 1000. The y-axis is the proportion (normalized histogram) the values of the L, =, 1.... computed using 512 projected samples.
Theorem C.1 RRaw-data-G-OPI, i.e., adding optimal Gaussian noise on raw data). Let a be the solution to (4) with A2 = 3. For any u, v E Lt let ü; u, + ag and i; is + by be the DP noisy vectors, with as, b, ~ N(0, o²) i.i.d. Then, denote gorg = Σi ūzū; we have
B Σ Uetis
Var (gorg) o² Σ (ut + ot) po"
(11)
Proof. To add Gaussian noise to the original data, it suffices to find the sensitivity, which, by Definition 2.2, is A2 Thus, the approach is (e, 8DP according the optimal Gaussian mechanism (Theorem 3.2). To compute the mean and variance, consider some E [p]. We have E [1, + a:) (w: + b;)] = E(u;; + 0,0% + b + a;b:] Ma4is.
Thus, taking the sum implies Elãorg! = Di u,yy For the variance,
E [(4 + a.) (v, + 6,)]² = Elu,o, + a, + br4 + a,b,j² = upuu + 0² (ut + 2,) + 04
which leads to
Var ((u: + (1; + b:)) = 0² 02² + + to¹
Therefore, by independence.
Var (Gorg) Var Σ (m az) (o +b;)
= Σ u + uz
pot,
which proves the claim.
For DP-RP-G-OPT-B and DP-OPORP, have the following results.
Theorem C.2 (DP-RP-G-OPT-B inner product estimation). Let be the solution to (4) with An = B.
In Algorithm 7, les W (-1,1)axk be Rademacher random matrix. Denote I _ W u.
Th
y WTe, v, and a, b are two random Gaussian noise vectors following NO, Let Drp
Vk Σ (a (2y a,) + bj). Then, Eigrpl
E/=1 U4U9s and
p
2
p
Var (0rp) d² Σ (u + v/) + kot
Σ
Σ
4
2
2
u
(12)
f=1
Proof. The conditional mean and variance can be computed as
E
(zy + az) (us + b,) 12 2o. j= 1,...
==1
23

---

# (oj
Var
(xg az) (vs by) Jz Un. l k
o²
vz + ko
where the variance calculation follows from Theorem C.I. Hence, we have
Σ
E
(xy + +g) (Us + bb²) = E
4
==1
2=1
Var (0rp)
=E
0²
j + v3)
ko*
+ Var
Σ
j=l
j=1
P +
ko
1
p
u
P
F
+
Σ
P
P
u
upu
(13)
h
i=1
In the above calculation, the formula of Var Rademacher distribution.
is from the result in [56] with s = 1 for
Algorithm 8: DP-OPORP
Input: Data u E 1JP, privacy parameters 0, (0, 1), number of projections Output:
Differentially private OPORP
3 Apply Algorithm with a random Rademacher projection vector to obtain the OPORP x
Set sensitivity A2 B
Generate iid random vector G E I following NN0, o?) where is computed by Theorem 3.2
6
Return 3 = x +
Theorem C.3 (DP-OPORP inner product estimation). Let a be the solution to (4) with D. = B. Let 1| be Rademacher random vector. In Algorithm 8, let x and y be the OPORP of u and v, and a, be two random Gaussian noise vectors following N (0,022). Denote Goporp () + a;) + by). Then, Elgoporpl
Ei=ı UyU', and
Var (Roporp) = o² Σ
(u? + 0,) + kot +
+
U44l's
W
p
p
1=1
1=1
1=1
1=1
(14)
Proof. The proof similar that of Theorem C.2, with the help of the result in [57].
The variance reduction factor p-k be quite beneficial when p is not very large. Also, see [57] p-1 for the normalized estimators for both OPORP and VSRP (very sparse random projections). The normalization steps can substantially reduce the estimation variance.
Comparison. For the convenience of comparison, let us assume that the data are row-normalized, ie., ||u||2 for all u U. Let p 2P 4,24, We have
Var (āorg) = 20 po
Var (ārp) = 20 + ko +
1 p² 3
h
1=1
Var (goporp) = 20 - kod +
1 1
2 2
p
h
k
1
1m1
24

---

For high- dith-niiensional data (large p), we see that Irp and Soporp has roughly the same variance, approximately 2o + kot 1 We would like to compare this with Var (Gorg) = 2o + po the variance for adding noise directly the original data.
E.
Let's define the ratio of the variances:
20² + po
pa
P (if p large or is high)
R 2x + ko +
(15)
kot
to illustrate the benefit RP-type algorithms (DP-RP and DP-OPORP) in protecting the privacy of the (high-dimensiona)) data. If \ 100, then it is possible that the ratio of the variances be roughly 100. This would be a huge advantage. Figure 9 plots the ratio R for p = 1000 and p = 10000 well series of k/p values, with respect to
102
102
kip = 0.01 k
k
10
0
kip 0.1
10
=.p 0.1
Ratio
100
kpp = 0.5
Ratio
100
kip=
10
10000
p = 1000
10
1
10.3
10
1
10-1
100
10
102
10
10
100
10
102
σ
Figure 9: We plot the ratio of variances in (15) for p = 1000 and p = 10000. We choose values with k/p {0.01, 0.050 0.5). Then for any value, able to compute the ratio R. For larger a, we have R as expected. See Figure 10 for the relationship among a, A, and (and ö).
10
10
8 1e-6
1e-6
10
A, 100
103
3
10
A,=
10
10
6=1
10
A₂
10
10
10
1
100
4,=0.1
10
10.2
10-1
10
10
1
10
10
10
102
A
Figure 10: Left panel: the optimal Gaussian noise versus for series of A2 values, by solving the nonlinear equation (4) in Theorem 3.2, for 8 = 10-6 Right panel: the optimal Gaussian noise versus Ag for series of values.
Figure 9 also illustrates when it might be good strategy directly add noise to the original data. For example, when 1000, the ratio can be below if a < 0.1. One can numerically verify that, (in we need > 100. In other words, adding noise the raw data might be plausible when > 100. In the literature, however, many DP applications typically require a much smaller e, such as e E [0.1, 20) (e.g.. [43, 48]). Therefore, DP-RP and DP-OPORP much better (i.e., has much smaller inner product estimation variance) than adding noise to the raw data in common privacy regimes.
Figure 10) order for 0.1 Ag = 3
25

---

D More Experiment Results
We provide the complete set of plots of our experimental results. Figure 11 and Figure 12, report the precision @ 10 and recall @ 100 curves of DP-RP variants and DP-OPORP on MNIST and CIFAR, respectively. In Figure 13, we report the test accuracy on the Webspam dataset of these methods. From all plots, we see that all tasks, significanly better than the strategy of adding Gaussian noise to the raw data.
and DP-OPORP perform equally the best on
In Figure 14, we report the recall@ @ 100 metric of DP-SignOPORP methods in addition to the precision @ 10 metric shown in the main paper. For completeness, we also include the SVM test accuracy in Figure 15, which is the same as Figure 4 in the main context.
0.8
0.8
0.8
OPORP
DP-OPORP
DD-OPPOR
DP-RP-G-OPP--
DP RP G OPT-B
DP RP OPT
precision@11g
0.6
DP-RP-G-OFT
DP.RP G
precision@16
-P-RP-G-OPP
DP-AP-3
precislon@11
DP-RP-
Raw data: OPT
Rew-deta-G-OPT
Row data G CPT
0.4
0.4
0.4
0.2
MNIST: k 64
MNIST: k 128
MNIST: k 256
0
5
10
15
20
0
10
15
20
5
10
15
20
0.8
0.8
DP-OPORP
DP-OPORP
DP.OPORP
DP RP OPT-
DP RP.. OPT-B
DP RP OPT
recal 100
0.6
DP-RP-G
recall@11 100
0.8
DP-RP-G
recall@ 100
0.6
DP-RP-G-OPT
DP GP.
Raw OPT
Raw-dals-G-OFT
data
0.4
0.4
0.4
0.2
MNIST: k 64
MNIST: k= 128
0
0
5
10
15
20
10
15
20
5
10
15
20
Figure 11: Retrieval recall and precision on MNIST, 3 = 1, 8 = 10
6
DP OPORP
OPOOPORP
DP-OPORP
0.4
DP RP GOPTT
0.4
DP OPT-B DP-RP-G-OPT
0.4
DP-RP-G-OPT-S
precision
DP-RP-G-OPT
DP-RP-G
precision@10
DP-RP-G
precislon@10
G.PPP DP.PP
Raw-dalt--GOOPT
daw-data-GOOPT
Raw-data-GOOPT
0.2
CIFAR: k 64
CIFAR: k 128
0.2
CIFAR: k 256
0
5
10
15
20
0
10
15
20
5
10
15
20
0.4
0.4
DP OPORP
--
DP OPORP
DP-OPORP
DP-RP-G-OFT-8
DP-RP-G-OPT-B
0.3
DPP.P.GG-OP
recall@1100 100
0.3
DP.AP.G.OR OPT
recall 100
0.3
DP.RP.G-OPT
DP RP-G
RP
DP.RP.G
recall@110
Raw Raw-data-G-Ome
Raw-data-G-OPT
Raw-dats-G-OPT
0.2
0.2
0.2
CIFAR: 256
CIFAR: k= 64
CIFAR: k 128
0
0
5
10
15
20
10
15
20
5
10
15
20
Figure 12: Retrieval recall and precision on CIFAR, 8 = 1,
10
26

---

WEBSPAM: k 256
WEBSPAM:
WEBSPAM: k 1024
test accuracy (%)
tast accuracy (%)
resouran Sourar (%)
80
80
80
DP-OPORP
DP-OPORP
DP-OPORP
DP-RP-G-OPT-B
70
DP-AP-G-OPT-B
70
DP-RP-C-OPT-B
DP.RP-G
DP-RP-G-OPT
DF-RP-G-OPT
DP-RPIG
16c
DP.RP
Raw data G
Raw data G OPT
Raw data G-OPT
60
60
10
15
20
5
10
15
0
10
15
20
Figure 13: SVM classification on WEBSPAM, 1, 10
0.8
0.8
DP SErORORR AR
MNIST: k= 128
MNIST:
precision@11
0.6
precision@1 10
0.6
precision@10
0.6
DP StrOPORP s-rd
0.4
0.4
0.4
UP SgrOPCN--- H-2
SyyOFORP bnd
nP SirrSooPP-PPPPP
Si-SSPPPPRP-PR bud
0.2
0.2
0.2
RP 3P-Ger0P
De-GPERP
MNIST:
0
Row dra e OPT
0
0
5
10
15
20
0
10
15
20
5
10
15
20
0.8
0.6
O SIrOPORR
OP OPORP AR
DP-DP SinOPPORP 1-2
recall@100 100
0.6
DP OPCPP
recall@100 100
0.6
-.- OPORP
recall 100
0.4
DP OPORP
-tae-dara----a
Haae 1---d
0.4
0.2
0.2
0.2
MNIST: = 128
MNIST: k 256
MNIST: k 512
0
20
15
Figure 14: Retrieval on MNIST with JUP-SignOPORP-RER and DP-SignOPORP-RR -R----ttR- (in the caption, "-s" stands for "-smooth". For DP-OPORP and Raw-data-G-OPT, we let 5 = 10
90
100
90
WEBSPAM:
test accuracy (%6)
lest accuracy (%6)
1 (%6
90
WEBSPAM: 256
80
WEBSPAM: k 512
test aoccuray
80
DP-SgnOPORP-6R 1-1
SknOPORP
- DP- Dww.-PP-OPPPP----- 1-1
70
DP SP-S@gOPORP-BBR P bet
DP-SinOPORP-PP -R--RRRR-------- DP-OFORP
SirOPOOP
DPORP
70
P-PP--GOPT-B
DP-RP G-OT
DP-RP-G-OPT-0
Raw-dess G-OPT
Rew-dats-G-OPT
Raw data G-OPT
60
10
15
20
5
10
15
10
15
Figure 15: SVM classification on Webspam with DP-SighOPORP-RR and DP- SR. For DP-OPORP and Raw-data-G-OPt we let ó 10-6
27

---

E Deferred Proofs
The following lemma on Gaussian random variables will be used in proof for Lemma 4.2, and may also be of independent interest.
X N
of po
po
Lemma E.1. Les
Denote ow/o Then we have:
y
oy
When r S 1, the maximum is ]
1. Pr([X] > [Y] = tan
r-p
+ tan -1
rtp
VI-
Vi-p²
achieved at p 0, i.e., max, Pr(IX
<
[Y])
2 tan
(r).
2. The conditional expectation:
r-p
r+p
11+r2-2pp
V14r2+2rp
B [[x]||x] > [V] 1x
tan
+ stan -1
rtp
V1-p2
VV-p2
3. The conditional tail probability: for any r > 0, PE (-), any 1 >> 0,
12
Pr([X] > +|| > YY) I exp
2n 2
Proof. The bivariate normal density function is
2pry 9
+ 33
f(x, y)
oxp
2To /1
p2
2(1 p²)
x22
122_ - p Po.1 2²
exp
exp
2TO / p²
2o
2(1 - p2)
Therefore, we have E
[
X > [8|]
=
A
ps
with
x
x²
(o, -p )2))
A
exp
dx
exp
dy:
00
V 2
/ 1 p-
20 u
-|x|
V
2(1 p2)
x
1
P
00 V2Ta 1-p2 exp
dx
exp
2(1 p²) dy.
20
||a]
V2Ta
y
Note that P Pr[[X] > (Y]) in the first statement of the theorem. Our calculation will use the following two identities involving the Gaussian functions [67]:
b )) [1
((xr) 2T|aa [al
+ tan
(16)
b
1+
(17)
2x2x
VI+
where ((x) and (x) are the pdf and edf of the standard Gaussian distribution. With a proper change of random variables, we can compute A as
A
exp
22
dx
V1
12
1
8²
ds
V 2TTO2
V
2
20
v
2T
|z|
|z|
x²
exp
dx
V VITTZ
2
x²
az exp
12)
2 |t|
pl.
+
Tv
+
dl
2
p
V
p3
A
A2.
28

---

For the first term we have
12
+ P
0
t2
+ +
A1 =
exp
dt +
exp
2m
2
1 p²
2m
2
p²
00
0g
exp
1²
Φ
2= P
By
di +
8
exp
s²
+
p
8
d8
2T
1 p²
V2T
p²
tp
1
V1
p²
1
1+
2v2T
G m)² 1-p²
2/2TT
CL +D)² 1-p²
+
1
T-P P
r r+ p
00x
/2T
VI 1 + r2 2rp
vI 1 r2 + 2rp
where we denote
and use (17). Similarly, we have that
By
12
+ p
t2
P
A2
0g
exp
dt
exp
$
dt
2T
p2
2m
P2
-00
12)
+ P
8²
r
p
0g
exp
$
di +
exp
$
ds
2m
V1 p²
JO
2
v 1
p²
1
P
r+ p
dx
2
2/2T
V1+12 1---111 2rp
v + 72 2rp
Therefore, we obtain
A(p,r) = A1 - A2 =
Ox
r-p p 11++2 -2rp
+
r r+ V1+ + r2 + 2rp
(18)
2
To compute P, by doing a similar change of variables, we have
100
1
t²
r|t| pt p2
r|t pt
P =
exp
②
dt
2T
2
v1 p2
P1
Pz-
Using (16), we obtain
1
t
P
0
1
t
+
P1
exp
dt +
exp
dt
2m
2
VI 2
2
v1 - 1
1
t2
V1 P
52
r p
exp
Φ
dt +
exp
ds
2T
2
2IT
2
VI z²
1
r
1
r P
+
tan
+ tan
2T
2
V1 1
2T
2
V1 - 122
1
tan 11
r-
+ tan 1
r + P
2
2T
V1 2
V1 - p²
1
1
r-
r P V1-P² p²
P2
tan
+ ttan
2
2T
/I - 2
which leads to
P(p.r) = P1 - P2
1
Lan 11
r- P /1 (1-p' p²
+ Itan" -1
r
(19)
V1-p²
π
29

---

Therefore, we know that
r-p
rtp
A(p,r) P(p.r)
V1+r2-2rp
V1+r
X
X
Y
=0=V3
tan
r-
tan -1
rtp
VI-p2
with = 0z/0y. We now investigate the derivative of P. By some algebra, we can show that
0P(p,r)
2rp(r² -
Op
(1 + 2rp)(1 + + + 2rp) V1 p2
When 0 < @P(pr) Up
0 when p 2 0 and DP(p.) dp
< when p > 0. Therefore, max, P(p. r)
P(O,r) = tan (r). ((r).
Tail bound. By our previous calculations, the conditional distribution X given [X] > |Y| is
(-
Φb rlur| px
p1 11pp2
exp
f(2||X| > [Y]) 22
V1-
IR
P
with P Pr( Yl) (19) the normalizing constant to make the integral equal to 1.
The conditional tail probability can be computed as follows. For some > 0, by symmetry.
Pr([
[Y])
x²
2
r|
-2
exp
$
de
2TT
20
V
p²
=2
exp
x²2
r|2
r
pr
dr
2T
2
p2
V1 /2
2
P2).
For Pl, using polar coordinates we have
v-n
VI-
P1
dr
2 dy
2T
tan
00
d8
rrr
2T
[o
tau
12
exp
20 cos
2 (8)
dA.
4
Similarly,
tan
1(-
V1-p"
rle
1
P3
2T
exp
20 cos? (8)
d0.
Therefore, we obtain
Pr([X]> [[[x|>,||X]]
(Y]
1
stan
V1-
exp
cos2(0) 20 cos (0)
t²
d8
π
tan
Vi-p²
tan
t2
V1-
exp
20 cos
co)2(()
do
V1-02
1
tan
2n7
d0,
30

---

tan
since (0) [0, 1]. Notice that P in (19) can be written as P
v1
d0. Hence, we
tan
know that the conditional tail probability is
Pr[XX 4IXI>
IYD)
Pr(|X > x|||> MT)
Pr( > (
S exp
(T20
Vr Vr>0,pE(11,1)
At the boundaries p p. - one can verity Pr([X] [Y] This concludes the proof.
E.1 Proof of Lemma 4.2
Proof. By Lemma E.1 and independence, we know that Pr(max,_1....p X > [Y]) reaches its
....... maximum when X; is independent of Y, i.c., when p(X,, Y) 0, vi = 1..... P. Since [X, follows
a half-normal distribution with edf being erf( x we have
V20a
p
Pr( max E.....
tt = erf
2Φ
20
0x
and probability density function g(x) = 2p _-1
1pp-1
20
When independent of
V2n0z
all X;'s (which gives the upper bound), we have
p-1
1
Pr( max E....
| (2
2p
20 Pr([Y]
2)dr
O
V2TO
p-1
2p
1
2a erf
dr
0z
V2TO
V20gg
2p (4D(t))
1}8- - l)
with proper change variables. This gives an upper bound as shown above.
F.2 Proof of Proposition 4.3
Proof. Consider a single Gaussian projection vector wo with iid N 1) entries. Since wTu
E 4j90; and each w; ~ N(0, 1), we know that Bws ~ N
82
P, where P:
p
||u|
Mi the correlation coefficient. Since |wo (u - v()l S 3 max;=1 luy by Definition 2.2 of
TTll
8-neighboring (and more generally, when ||u u''li (), we have
Pr( a Nb(()
|w (u u')l 2 m ul) (wTul) Pr(3 l......pp
|ws| 2 |wTTl)
Note that, 3 max |wy| 2 Tul is a necessary condition for the event that there exists neighbor such that sign(w" u) * sign(w"" w'). Denote
1 maxx;=1..... |wyl
Iw" |w"'ul} ul}.
Applying Lemma 4.2 with r = 3/llu|| S yields
E[1] Pr(B max
|w 2 |wTul)
i=I....p
S
Fl
2p(2 - 12--1(20(1)) - (t)(t)
(20)
as given by (5). Let I, be the corresponding indicator function w.r.t each column in the projection matrix W. Denote N+ Σ 4j. and by the above reasoning, we know that |S| < N+ where is defined in the theorem. Since the columns of W are independent, N₂ follows a Binomial (k; E E(T)
distribution with & trials and success probability E bounded as above. Therefore, with probability 1 6, we have N4 < B B-1 Fl k), where B-1 is the inverse edf of the Binomial distribution. O
This proves the claim as desired.
31

---

E.3 Proof of Theorem 4.4
Proof. Let = sign(WTTl u) E +-1,+1}* s' sign(WT ud)
E +-1,+11%
We denote the
collision probability of non- non-private SignRP as
PsRr Pr(s1s 822) 00s (p) =1
0
π Hence, the collision probability of DP-SignRP-RR can be computed as P == Pr(31 52j) = Pr(s15 82j, both change sign not change sign)
π
+ Pr(s11 # 82j; one sign changes)
e"
1
e²
PsRPl( èd +1 )2
)2
+ 2(1 PSRP) (ec 1)2
ec' +1
(e" 1)2
2
PSRP (e" + 1)2
+
(e" + 1)22
which increases linearly in PSRP. Thus, it holds that
(e' + +12
2e
PSRP 1 0 π
E[PRR] (er - 1)² (ec 112
P
which implies B[dRR] (1-(1 (1- 4) 0. To compute the variance, we first estimate 0 cos (p) by
0 -= t(1 - PPR)-
Then according to the Central Limit Theorem (CLT), for the sample mean of iid Bernouli'', as + 20, we have
1 k 1531 = 826} + N(P, k
P(1 P(1-P)) P)),
k j=1
As result, we have 1 + (0, VER), ). where
x2 2e + +1
(e' 1)2
2ee
2 +1
A (e' 1 1)2
VRR
(et 1)a (1
+
(1
π (ec' + 1)2
(ee' + 1)3
(er' + +1²
(ee' + 1)3
x² (e + +1)*
0 (e' - 1)2
2e
0 (c" -1)2
2
[11
+
+
(et 1)4
(er' + +1²
(ee' + 1)2
a (et' + +12
(ee + 11²
20
0 2e
0
2
4626'
(1
+ (1
+ (ee' 1111
π (et' - 1)
7t (e 1)2
π π
2 c
2 2c'
1( 0) +
Eee 1)2
(e' - -1)
We conclude the proof by replacing c' c/N..
E.4 Proof of Theorem 4.5
Proof. Let us consider a single projection vector w, = Wini) Denote x, = =wz u and 2'j = uz ul a neighboring data u' of u, and 8, = sign(x;); s/ sign(z;). Also, let I.j max..i..... W.
for
|z,1
|ag]
and L' I max.. |W,51 1- W.l.o.g., we can assume sj by the symmetry of random projection and the symmetry of DP. Consider two cases:
Case I: Lj > 2. In this case, we know that s/ = sj. i.c., the change from to u' will not change the sign of the projection. Thus, in Algorithm 4, we have
Pr(š, 1) Lj 41 c) Pr(3)= =1 expl
exp( c) +1 Ly expl x +1
32

---

By the definition of 3-adjaccecy,, [L, - -3] equals either 0 or 1. When L = D.j.
Pr(jz=1)
Pr(3-11)
1. When L, L33 = 1, we have
Pr(3, 1) exp( c) + exp(Ee)
Pr(3)= =1) exp( c)) +1
Hence, we have
Pr(3,=1) e by the numeric identity Pr(
b+c S for 26>
Pr(š,=1) I eñ. On the other hand, and c > 0. Thus, by symmetry, e - Pr(8/=1)
Pr(3, = -11 expl + +) +1
La Pr(3) = exp(
# E) +1
Similarly, when Inj T'j, the ratio equals 1. When T,j = I,j 1, we have Pr(,,=-1)
Pr(;,=-1) S
Pr(š,=-1) expl f Li et. By symmetry we obtain e S Pr(3 S et.
Case II: Lj 1. In this case, sj might be different from s/.. First, if Lj 2, then the above analysis also applies that Pr(s,=1) and Pr(š,=-1) are both lower and upper bounded by In this case,
Pr(
Pr(3)=-1)
e e and e², respectively. It suffices to examine the case when L' 5 = 8j 1 then the probability ratios simply equal If --1, we have
expí exp(
Pr(š, =1) 1) Pr(3 1)
et,
Pr(3j = -1) Pr(3f --1)
expl ) = =e
exp +
exp +)+I
exp )+I
Pr(3 =) S f. for = -1, 1, and for all j I,.., k. That is, each single perturbed sign achieves <DD. Since the k projections independent, by Theorem 2.1, we know that the output bit vector á = [$1,... 8u] is e-DP as claimed.
Combining two cases, we have that log Pr(s,=t)
33


Reviews:
[{"review_id": "Uz25dFanaJ", "reviewer": "Reviewer_ywEG", "summary": "This paper studies the problem of computing differentially private sketches of high dimensional vectors via random projections. The contributions are:\n1. Algorithm DP-RP-G-OPT: An algorithm that uses the Gaussian mechanism to privatize random projections using Gaussian and Rademacher matrices, but adds more carefully calibrated noise by using the CDF of the Gaussian distribution as opposed to the usual tail bounds. It outputs a k-dimensional DP sketch of a p dimensional input vector, it seems to be working in the local DP setting as it operates on a single data vector.\n2. Algorithm DP-OPORP: An algorithm that appends the OPORP mechanism of Li and Li ([53] in the paper) with the Gaussian mechanism to produce a DP variant of the former. It produces a k dimensional sketch of the p dimensional input vector but uses only $p$-many multiplication operations instead of $kp$-many.\n3. Algorithm DP-SignRP: An algorithm that produces a 1-bit sketch of the input vector in a differentially private way. The algorithm only accepts input vectors with some lower bound $m$ on the norm which must be passed as an argument. They also use this algorithm to produce a DP sign estimator.\n4. Algorithms DP-SignRP-RR and DP-SignRP-RR-Smooth: The authors aim to produce an improved version of DP-SignRP by leveraging the stability of the sign of the projected output under small changes in the input. They also use the binning of OPORP to reduce the sensitivity of the algorithm to the input so as to be able to add less privatizing noise.\n\nThe authors go on to test their methods empirically on similarity search and classification problems.", "questions": "1. Can you please elaborate on the model of differential privacy that you are operating in? What is the significance of this for the CountSketch application that you describe in the beginning?\n2. Why do we need to assume a lower bound on the norm of the input vector for DP-SignRP-RR? Does this impact its applicability/parameter regimes? How should we set the value of $m$? In particular it seems like $m<\\sqrt{p}$ is necessary to avoid the domain becoming empty.", "limitations": "This is a theoretical work and I do not feel that potential societal impact needs to be discussed here.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The authors want to leverage the stability of the sign operator under random projects to boost the privacy guarantee over what one might get naively, in some sense they want to appeal to the local sensitivity of the mapping when the input vector is far away from the decision boundary. This idea may be fruitful.\n2. The authors conduct some experiments to test their methods.", "weaknesses": "1. The privacy model here is not clear - the authors define and talk about differential privacy in the central model (where the stability guarantee holds over adjacent data sets) but their algorithms take as input only one data point. It seems that instead all the guarantees are meant to hold in the non-interactive local model of differential privacy.\n2. The methods DP-RP-G-OPT and DP-OPORP are not very novel - the first achieves no asymptotic improvements over prior work and seems to improve the performance by some unspecified constant. The second simply appends the OPORP algorithm from prior work by the Gaussian mechanism.\n3. The significance DP-SignRP-RR is not clear - there is a lower bound $m$ on the input vector.\n4. The quality of the writing needs to be improved. The most novel contribution seems to be DP-Sign-OPORP-smooth-RR which is relegated to the end.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer ywEG:\n\nThanks for your feedback on our submission.\n\nW1 and Q1.  As Reviewer mentioned, the proposed private sketching algorithms are designed to protect attribute-level privacy. That is, our method prevents the identification of a change in any element in the vector in the sense of DP. This is becauseRP is a \"sample-wise\" algorithm---RPs are concrete representations of the original data and are directly used for downstream tasks for search and learning. In fact, due to this nature of sketching methods, this attribute/item-level privacy setup is considered by many prior papers on DP sketching, for example,\n\nKenthapadi et al., Privacy via the johnson-lindenstrauss transform. J. Priv. Confidentiality 2013.\n\nNina Mesing Stausholm, Improved differentially private euclidean distance approximation. PODS 2021.\n\nZhao et al., Differentially private linear sketches: Efficient implementations and applications. NeurIPS 2022.\n\nSmith et al., The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. NeurIPS 2020.\n\nDickens et al., Order-invariant cardinality estimators are differentially private. NeurIPS 2022.\n\nIn a centralized setting with a database consisting of $n$ data points (vectors), we apply our algorithm to all $n$ data vectors. The privacy statement is: *\"an adversary cannot detect a small change in any user's data vector from the user's DP-RP or DP-SignRP samples.\"* On the other hand, as Reviewer kindly pointed out, our algorithm can also be applied to \"local\" DP settings where each local user owns one data vector. \n\nTo answer Q1 about the application scenarios, our algorithm and privacy protection (or, more generally, DP sketching methods) could be very useful when, for instance, an organization needs to share sensitive data like profiles or gene sequences data for machine learning tasks. Basically, the DP sketches can be used in all the applications where RP (or count sketch) are used. We have introduced and cited many of them in the paper.\n\nIf the reviewer hopes to see additional concrete applications, one example is that the bioinformatics community releases sets of 1000 sketches for all known genomes on a regular basis [1]. The sketches are used in various ML tasks like clustering and distance estimation, etc. In this application, our proposed algorithms based on DP-RP, DP-OPORP and their signed versions can all be applied, which protects the privacy of gene expressions of each patient.\n\n[1] Mash: fast genome and metagenome distance estimation using MinHash, Ondov et al., Genome Biology, 2016\n\nW2. DP-RP and DP-OPORP algorithms: In our paper, we hope to provide a complete picture of DP sketching using RP-based algorithms and a step-by-step derivation of the signed RP and OPORP sketches (i.e., DP-SignRP, DP-SignOPORP)\nfrom DP-RP. We include these algorithms in this submission since they are all highly related. We have tried our best to optimize the space and organization. \n\nThe focus (and the title) of our paper is \"Smooth Flipping Probability for Differential Private Sign Random Projection Methods\".  DP-RP and DP-OPORP are important baselines in our paper to compare with signed methods. This is why we spent about 1 page to review prior works on DP-RP, and proposed an improvement. Section 3 play two roles: (1) adopting the optimal Gaussian mechanism to RP and OPORP has not been proposed and evaluated in the literature before, so we hope this integration and the empirical evaluations could be useful to the community; (2) we aim to improve the baselines of (full-precision) DP-RP and DP-OPORP, to make a fair comparison with the proposed DP-SignRP and DP-SignOPORP methods.\n\nW3 and Q2. In DP-SignRP-RR, which is built upon the classic randomized response (RR) strategy, $\\|u\\| \\geq m$ is assumed for better utility. In fact, if we allow $m=0$, then DP-SignRP-RR reduces to the most naive RR approach with flipping probability $1/(e^{\\epsilon/k}+1)$, where $k$ is the number of projected samples. If we know that the data norm is lower bounded by $m>0$, then we can reduce the flipping probability, as in our analysis. In practice, this is quite common. One example is the Genome data (e.g., gene expression microarrays) for which sketching and hashing are widely used. The gene expression data are usually dense with large norms. In this case, we can have some large $m$ numbers.\n\n*\"How should we set the value of $m$?\"*\n\nAnswer: $m$ is not \"set\" but depends on the data (we assumed all the data points have norm $\\geq m$). In our experiments, we let $m$ be the smallest norm among all data points in the dataset. We can also determine it if we have some prior knowledge of the data.\n\n$m$ is just a lower bound on the data point's $l_2$ norm, so there is no constraint for it. It can range from 0 (for all empty vector) to $p$ (when all data entries equal to $\\pm 1$).\n\nFinally, we highlight that in our proposed DP-SignRP-RR-smooth with smooth flipping probability, the need of $m$ is waived.\n\nW4. Thanks for the suggestion. We organized Section 4 in this way to show the whole path towards our proposed algorithms, and why and how they improve the classic approach (DP-SignRP-RR). Particularly, the differential privacy of SignRP and SignOPORP has not been studied in the literature before, so we hope to conduct a thorough investigation. Thus, in Section 4.1, we start with the standard strategy to privatize SignRP using the classic randomized response (RR) technique, which requires some non-trivial probability calculations and privacy analysis for the algorithm design. Then in Section 4.2, we propose the novel idea of smooth flipping probability to improve the standard DP-SignRP-RR method, and further proposed DP-SignOPORP-smooth. While the smooth flipping probability is what we recommend eventually, both algorithms present novel analysis and ideas to the literature. \n\nThanks again for your review. We hope our response has well answered your questions."}, {"review_id": "na8MiHO4YT", "reviewer": "Reviewer_bvWd", "summary": "The paper introduces a series of differential privacy (DP) random projections (RP)  algorithms based on the robustness of the sign flipping probability in RP. This approach is promising as it seeks to enhance the existing methods in both theoretical guarantees and empirical performance.", "questions": "Could you provide more intuition on the scale of the smoothness in terms of sign flipping probability?", "limitations": "The authors adequately addressed the limitations", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The analysis of the probability of smooth sign flipping is a novel contribution, offering a fresh perspective for DP RP algorithms.\n\n2. The presentation of the paper is generally clear, providing a concise explanation of the methodology and algorithms developed. The authors effectively explain the motivation behind their research and the rationale for leveraging sign flipping probability.\n\n3. The experimental evaluation of the proposed algorithms is adequate, highlighting the improvements achieved by DP-SignOPORP and iDP-SignRP over existing algorithms in the standard differential privacy setting. The comparison with other methods in the literature provides valuable insights into the performance of the proposed algorithms. ", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer bvWd:\n\nThanks for your feedback on our paper.\n\nAs we mentioned at line 195, The concrete exponentially decaying form of the flipping probabilities in Algorithm 4 is leads to the \"smoothness\" of the flipping probability: for any neighboring $u$ and $u'$, $P^{(u)}\\leq e^{\\epsilon/k}P^{(u')}$. By re-arranging we see that $P^{(u)}/P^{(u')}\\leq e^{\\epsilon/k}$. In the proof, this bound the key to guarantee that each projected value takes $\\frac{\\epsilon}{k}$ privacy budget, leading to the $\\epsilon$-DP. Figure 4 plots the smooth flipping probability, the standard flipping probability (global upper bound), and the local flipping probability (which is non-DP). With the exponential decay, smooth flipping probability is much smaller than the worst-case analysis.\n\nWe are glad that you are interested in the smooth flipping probability, which is a novel idea for privatizing the SignRP and SignOPORP. We expect that this idea could be helpful for more DP algorithm designs. We hope now the intuition and design of the smooth flipping mechanism is more clear. Thanks again for your review. "}, {"review_id": "70K2qsivsa", "reviewer": "Reviewer_TuXU", "summary": "The authors study the important problem of preserving privacy in matrix data. They study a family of fundamental operations on data which is Random Projection. This is useful for dimensionality reduction, NN search etc. Based on RP one can also obtained signed RP (SRP) which are useful (as in  SimHash) to find near duplicates and estimate similarity of vectors, etc. The authors present DP algorithms for this family of applications (RP, SRP). Their algorithm improve over prior work ([47]) showing methods of reducing the amount of noise using a series of techniques including smooth sensitivity and better upper bounds on sensitivity. Their experiments show improved results.\nAll in all this is an interesting paper on improving the accuracy of an important building block in data analysis with privacy.", "questions": "1) Can you discuss more the comparison with methods like Blocki et al that keep W secrete (or even provide empirical results for comparing which such methods)? Is it possible to improve the results significantly?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ Important problem : computing with privacy random projection based sketches\n+ Improved empirical results for a practical algorithm \n+ theoretically sound and non-trivial results", "weaknesses": "- It would be interesting to know how much head room is there if the projection matrix itself is kept secrete. There is no comparison with methods that omit the matrix W.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer TuXU:\n\nWe appreciate your encouraging feedback on our theoretical and empirical results, and the significance of the DP sketching problem. We too believe that DP sketching methods (e.g., the RP-based algorithms in our paper) are interesting, important, and could have broad applications.\n\nThe DP-RP method under the setting where the projection matrix $W$ is also private/random was studied in [1]\n\n[1] Blocki et al., The johnson-lindenstrauss transform itself preserves differential privacy, FOCS 2012.\n\n[1] argued that when the singular values of the data matrix are all large enough, the randomness of RP itself provides DP. While the authors studied a slightly different problem of publishing covariance matrix through RPs, their analysis also implies that using the same Gaussian noise addition mechanism as in DP-RP, the Gaussian noise requires $\\sigma=O(\\sqrt{k}/\\epsilon)$ when $W$ is private. Asymptotically, this is the same as the noise level with known $W$ when $\\epsilon\\rightarrow 0$, and is smaller than $O(\\sqrt k/\\sqrt\\epsilon)$ with known $W$ when $\\epsilon\\rightarrow \\infty$ (see our Remark 3.1). Theoretically, we find that the analysis in [1] is quite tight, though no lower was proved.\n\nMoreover, for SignRP, we are not aware of any result/analysis under the private $W$ setting. The analysis seems challenging, but we believe this could be an interesting problem to explore.\n\nAgain, thanks for your review of our work. \n"}, {"review_id": "UF5r50qUO4", "reviewer": "Reviewer_hnU4", "summary": "This paper develops a series of differentially private (DP) Random Projection and Signed Random Projection algorithms. By using randomized responses and the idea of smooth sensitivity, the new proposed algorithms are shown to outperform previous results while still maintaining the same amount of privacy guarantee.", "questions": "- How does the author numerically evaluate $\\sigma$ in Theorem 3.2? Do we have a closed form solution for that?\n\n- I'm also curious how the author compute $N_{+}$ in practice since it looks like a pretty complicated bound?\n\n- Since Proposition 4.4 suggests that $N_{+}$ is smaller when the data norm is large compared to $\\beta$, can we just scale up the data in practice?\n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The idea of using the exact tail probabilities of Gaussian to compute the necessary noise level (Theorem 3.2) is pretty interesting. This might imply that we can improve the empirical performance of most Gaussian Mechanism-based algorithms by using this simple fix.\n\n- \"Local perturbation\" is also an interesting idea to investigate since a lot of the time, we only need to maintain the privacy for specific sets of datasets rather than for any datasets in the data universe.\n\n- The appendix has plenty of good and thorough discussions that improve the readability and completeness of the paper.\n\n- The proofs and analyses are fairly well-organized and well-written.", "weaknesses": "- Seems like we do not have a utility guarantee for the smooth flipping probability algorithms? Since this is the main focus of the paper, the result would be stronger if the author can show that the algorithm performs well both in practice and in theory.\n\n- It would be interesting to see if the new DP-random projection algorithms can perform well in deep learning tasks. For example, if we use the DP-random projection to quantize the gradient, how does that affect our results? I feel like this would better demonstrate the power of the projection algorithms.\n\n- The runtime should probably be reported in the experiments section since it's a fairly important aspect of these types of algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer hnU4:\n\nThanks for your feedback. We appreciate your interests in our work and the ideas behind the algorithms. We also hope that the theoretical and empirical results in our paper (the adoption of optimal Gaussian mechanism and the smooth flipping mechanism) could be helpful to the community.\n\nW1. Thanks for the question. In principle, we can derive some results for DP-SignRP-RR-smooth like the estimation variance in Theorem 4.5. However, this would be very complicated, since by using the smooth flipping probability, we need to compute the probability that the projected value falls in different \"regions\". We can use a similar calculation as in Lemma E.1, to express those probabilities as some tedious integrals. The final expression would be even more complicated when considering the interactions between the DP-SignRP-RR-smooth sketches of two data vectors. Therefore, in the submission, we mainly focused on elaborating the algorithm design and intuition, and the empirical evaluations. We are happy to add the analytical formula to the paper if suggested by the reviewer.\n\nW2. In this paper, we focus on the more fundamental aspects of the differential privacy of RP based algorithms, since many details and ideas (e.g., the smooth flipping probability) have not been addressed before. In future works, it would be interesting to apply these algorithms to more tasks/areas, such as deep learning as you kindly suggested. Thank you.\n\nW3. In general, since RP and OPORP only involves a matrix-matrix and vector-matrix multiplication which have very efficient implementations in the computing softwares, generating the sketches (or signed sketches) takes very little proportion of time compared with the time for search and model training. The flipping mechanisms can also be efficiently implemented by properly generating a binary mask matrix according to the flipping probabilities. The OPORP based algorithms are even faster since to generated $k$ projected values, we only need to touch each dimension of the data vector once. Thus, in the experiments we mainly focused on the performances of the proposed methods. If the reviewer is still interested in the overall running times, we are happy to share the more detailed running time evaluations.\n\n\nQ1. We numerically solved the (one-dimensional) nonlinear equation for $\\sigma$, for different $\\triangle_2, \\epsilon$, and $\\delta$ values. There is no closed-form solution for this problem. We have provided the detailed numerical values for $\\sigma$ as a plot, in a more detailed technical report. We are happy to include such a plot in the supplementary material if Reviewers feel it is necessary. Thank you. \n\nQ2. As stated in Theorem 4.4, we first compute $F_{\\|u\\|,p}=P_+(\\frac{\\beta}{\\|u\\|},p)$ as in Eq. (5), Lemma 4.2. Then we plug $F_{\\|u\\|,p}$ into Eq. (6). So basically we only need to do an Gaussian integration (5).\n\nQ3. Note that in our paper, we assumed that $u\\in [-1,1]^p$ and defined the distance between two neighbors to be $\\beta$. Alternatively, as the reviewer mentioned, we can scale the data domain to $[-C, C]$ with some $C>1$. However, in this case, to attain equal-strength privacy protection, the adjacency parameter should also be scaled to $C\\beta$. Thus, the ratio $\\beta/\\|u\\|$ would remain the same after scaling. Hence, simply scaling up the data would not help enhance privacy, unless we relax the privacy protection requirement (e.g., do not scale up $\\beta$ accordingly). We hope this answers the question. Thank you. \n\nThanks again for your feedback on our work. We hope our reply answers your questions adequately."}]

Author rebuttal:

Meta-review: Reviewers bvWd, TuXU, and hnU4 are all in favor of accepting the paper, arguing that the analysis is interesting and novel, some of the proposed methods have promising empirical results, and that the proofs are well organized and written. Reviewer ywEG raises two weaknesses: 1. the privacy model is not clear, and 2. the contributions of the paper are unclear. 

I agree that the privacy model was unclear in the original submission, but I feel that the authors adequately clarified during the discussion period. Section 2 should be updated to clarify that the paper studies **attribute-level** privacy, where adjacent datasets differ in the value of one attribute in one row. In particular, on line 83 the authors write "In this work, we follow the convention in the literature that neighboring databases $U$ and $U'$ only differ in one row." While this is technically true, this sentence is confusing because it sounds like neighboring datasets may differ on an entire row, which is not the case in the paper. I would suggest highlighting the fact that this is different from the majority of the DP literature, but common for papers on DP sketching.

The second concern of ywEG is that several of the mechanisms from Section 3 are not new, and it is unclear what the main contributions of the paper are. It may be worthwhile including a brief discussion in Section 3 to help readers identify the main contributions. During the reviewer discussion I asked the other reviewers if they had concerns about the clarity of the paper given reviewer ywEG's review, and reviewers bvWd and TxXU both said that they had no issues. 

Given the above minor additions, I believe that the paper is above the bar for NeurIPS.
Decision: Accept (poster)