On Computing Pairwise Statistics with Local Differential Privacy
Authors: Badih Ghazi
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Adam Sealfon
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
local differential privacy
pairwise statistics
TL;DR: We give algorithms and lower bounds for computing pairwise statistics and quadratic forms under local differential privacy.

Abstract: We study the problem of computing pairwise statistics, i.e., ones of the form $\binom{n}{2}^{-1} \sum_{i \ne j} f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $\tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries.

On Computing Pairwise Statistics with Local Differential Privacy
Badih Ghazi Google Research Mountain View, CA, US badihghazi Sanggaazi@mmaill... com
Pritish Kamath Google Research Mountain View, CA, US pritish@alum.mit. mit. .du
Ravi Kumar
Google Research
Mountain View, CA, US
ravi kw3kkk33mmmmlmm com
Pasin Manurangsi Google Research Bangkok, Thailand pasinégoogle. com
Adam Sealfon Google Research
New York, NY, US
adamseelfoo@@gogge..com com
Abstract
We study the problem of computing pairwise statistics, i.e., ones of the form ( Eisy (a sty); where x; denotes the input to the ith user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's r coefficient, Area Under Curve, Gini's mean difference, Gini's en- tropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries.
1 Introduction
Differential privacy (DP) [DMNS06] is widely studied and used notion for quantifying the privacy protections of algorithms in data analytics and machine learning. It has witnessed many practical deployments [EPK14, Shal4, Gre 16, App17, DKY17, Abo18, RE19, TM20, KT18, RSP*21]. On a high level, DP dictates that the output of a (randomized) algorithm remains statistically indistin- guishable if the input of any single user is modified; the degree of statistical indistinguishability is quantified by the privacy parameter > 0.
An important setting of DP is the local model [EGS03, KLN 11], where each of n users holds an input that they wish to keep private. An analyst wishes to compute some known function of the users inputs. The analyst and the users engage in interactive protocol at the end of which the analyst is supposed to compute an estimate to the value of the function on the user inputs. When aforementioned statistical indistinguishabiliy property is enforced on the algorithm'' 's transcript, the algorithm is said to be e-local DP (see Section 2 for a formal definition). Non-interactive algorithms refer the setting where each user sends single (DP) message to the analyst, who is then supposed to output an estimate of the desired value without any further interaction with the users. As usual assume broadcast model where every communication is
in the interactive local DP setting, visible to all users and to the analyst (and subject to the DP constraint). The number of rounds of an interactive protocol refers the number of back-and-forthss between the of users and the analyst.
While the local DP setting offers compelling trust model compared to the central DP model (where an analyst is assumed to have access to the raw user data and the privacy guarantee is only enforced at its output), the local setting is often limited by lower bounds on the error incurred by private protocols (c.g., [BNO08, CSSI In this work, we study some basic tasks in analytics and learning, and give local DP protocols with significantly smaller error than what was previously known.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Quadratic Form Computation. Throughout the paper, we consider the following task:
Definition 1 (Quadratic Form Computation). Given matrix W E RRR Each user i receives I; E [R.. The goal is to compute the quadratic form lig hix where lx E 72/0 denotes the normalized b]/-
histogram of the input, i.e., (bx)) := Mi E [n] x
An algorithm computing quadratic forms immediately implies an algorithm for computing pairwise statisties (also known as U-sttaisticcs of degree 2) defined as F(X) = (?) Eigkzgnn ff (zz, 2.y)
where f= X²2 + R is a symmetric function (called kernel), and I; is the input to the ith user. The family of pairwise statistics is notable in that it contains several statistical quantities that are widely used in different areas, including the Area Under the Curve (AUC), Kendall's T coefficient, the Gini's mean difference, and the Gini's diversity index (aka Gini- Simpson index or Gini's impurity), Computing quadratic forms has been studied in the context of local DP by Bell et al. [BBGK20] who gave algorithms for functions that are Lipschitz and for estimating the AUC of classifier; the latter was improved recently [CM23]. While these problems are simple in central DP (as we can directly add noise to the function value), we note that clear challenge for computing pairwise statistics (and hence quadratic forms) in local DP is that each summand depends on data points held by two different users.
Linear Queries.
Computation of quadratic forms is a natural "degree-2" variant of the so-called linear queries (defined below), well-studied problem in the DP literature.
Definition 2 (Linear Queries). Given a workload matrix W * the goal is to compute Whx where lix _ denotes the normalized histogram of the input.
There is a long line of work on privately answering linear queries. In both the central and local models, the optimal errors achievable by DP algorithms are (mostly) well-understood for various types of errors, such as the Ezerror or the - [HT10, BDKT12, LMH 15, NTZ16, BUV18, BBNS19, ENU20, Nik23]. Recall that the MSE of an estimate of a real value is defined as MSE(2, 2) == [g - 2) For our purpose, we consider the following natural measure of accuracy: Definition (mMSE). Given a mechanism M that answers linear queries for a workload ma- trx W E b its maximum mean square error (mMSE) defined as mMSF(M: W) max max MSE(M(x)), (Whx)j).
In a recent seminal work, Edmonds et al. [ENU20] provide a nearly optimal characterization of the error achievable by non-interactive s-local DP algorithms. To describe their result, we need some additional definitions of norms on matrices and related quantities:
> 1 + 2 norm: For any matrix A, ||A|]]-2 is the maximum (f2-)norm of its columns. foo-norm For any matrix A, || is the maximum absolute value among its entries.
Factorization norm: For W E R kek let r2WW) == minnTr--e [| [|]
ApproximateeFFcctrriatioo norm': For W E R and a z O, let 72 aW: =
minlwwwa 5a 7/ (W))
Finally, we define <(W, n) == mina> (72 a) + aEVT). (Note that nW, S (W) as we can pick a = 0.) The result of Edmonds et al. [ENU20] states that this quantity, up to polylogarithmic factors, governs the best eтror achievable for linear queries in the non interactive local DP model?:
Theorem 4 ([ENU20)). For any workload matrix W, there is a non-interactiive e-local DP mechanism for linear queries with mMSE at most O
Furthermore, any non interactive e-local DP An
mechanism must incur mMSE at least á
<(W,)) ein
Given such tight and generic characterization for linear queries, it is natural to ask:
Can we characterize the error of computing the quadratic form for any matrix W with local DP?
'Note that, unlike the three quantities above, this is not actually norm. "We remark that [ENU20] did not state their bounds in the form we present in Theorem (or even for mMSE); we provide more detail on how to interpret their lower bound in this form in Appendix B. The upper bound is via the matrix mechanism, introduced in central DP earlier in [LMH*1 15, NTZ16].

---

1.1 Our Contributions
In this work, we answer this question by establishing connections between the problems of computing quadratic forms and linear queries. Leveraging the wealth of knowledge the latter, obtain several new (and general) upper and lower bounds for the former.
Non-Interactive Local DP. First, in the non non-interactive setting, we give the following upper and lower bounds. Together, they show that the error one can expect for computing quadratic forms is essentially the same as that for computing linear queries (as provided in Theorem 4).
Theorem (Non-interacee Algorithm). For any W B there is non non-interacttiv E-local DP mechanism for estimating quadratic forms W with MSE most O ((W.n)
gAn
Theorem 6 (Non-interactive Lower Bound). For any symmetric W E Bkak any non-interactive
e-local DP mechanism for estimating quadratic forms on W must incur MSE at least (((W.))
22
Our results above are generic and can be applied to any pairwise statistics. To demonstrate the power of the algorithm, now state implications for several classes of statisties that have been studied in the privacy literature. Due to space constraints, we defer their definitions to Section 5.
Corollary 7. There is a non-interactive e-local DP mechanism for computing pairwise statistics for:
Any Liiipsschttzfuncttinn f [0, R. with MSE O Kendall's coefficient, with MSE O
G log EA
(log ky (logg)
c'n
(log k.) c+n
AUC under the balancedness assumption', with MSE O
Gini's diversity index, with MSE
log 22m
For (11)-Lipschitz functions, which includes several well-known metrics such as Gini mean dif- ference, we improve upon the algorithm of Bell al. [BBGK20] whose MSE is O EVT We not aware of any previous bounds on Kendall's coefficient before; the metric was mentioned in [BBGK20] without any error guarantee given. For AUC, our bound is the same as in [BBGK20] but worse than follow-up work [CM23] by a log & factor; nonetheless, derived as a corollary of a generic algorithm without relying too deeply on AUC (except for the 72-norm of its matrix). For Gini's diversity index, bound is again worse than that from Bravo et al. [BHBFG+2] 22] by log k factor, but their algorithm requires the use of public randomness; we do not any public randomness. (Throughout this work, when refer to the local model without further specification, we assume no public randomness, aka private-coin model.)
stress that our result
Remark. Since our non-interactive algorithm only requires a vector-summation primitive, we can also apply protocols for vector summation in the shuffle model (e.g., [CSU+ 19, BBGN20, GMPV20J) to obtain an (s, 6)-DP protocol in the shuffle model, reducing the MSE by a factor of n for each setting in Theorem and Corollary 7.
Interactive Local DP. Finally, also provide an interactive algorithm whose MSE does not depend on 72 (W), as long as n sufficiently large:
Theorem 8 (Interactive Algorithm). For any W kxk there a three-round s-DP algorithm for estimating quadratic forms on W such that, for n 2 (22(W) 00(1,
)0(1), the MSE is O EAn
[
We note that the dependence O the problem is as hard as binary summation, which known to require MSE at least Ω (+²²) even for arbitrary number of rounds of interactions [CSS12), and rescale this hard instance to get any desired loo -nor.
W
is the best possible: even when the k 2 and W is binary.
'The balancedness assumption for AUC states that there are 2(n) examples with each label 0, This is a required assumption to achieve an error in the form presented, as otherwise when e.g., there is a single O-lalled example, is impossible to achieve any non-trivial guarantee.
3

---

Combining the non -on-interactive lower bound in Theorem 6 and the interactive upper bound in The- orem 8, our results imply that there exists matrix W E R kxk , O, E N such that interactive algorithms are provably more accurate than non-interactive ones for privately computing the quadratic form on W. This places computing pairwise statistics as one of the few problems (and perhaps the most natural) that are known to separate interactive and non-interactive local DP. Due to space constraints, we defer further discussion of this to the Appendix.
1.2 Technical Overview
We now give a brief technical overview of our proofs.
Black-Box Reduction from Linear Queries (Lower Bound). As mentioned earlier, our results are shown through connections between computing quadratic forms and linear queries. We will start with black-box reductions between the two. Suppose that we have a non-interactive e-local DP algorithm A for computing the quadratic form on W. We will construct a non-interactive s-local DP algorithm A' for computing linear queries of W. This will allow to establish our lower bound (Theorem 6) as a consequence of the lower bound for linear queries (Theorem 4).
For simplicity of this overview, instead of considering the full quadratic form, suppose that A works on 2n users with inputs 21..... .y. yi...... ........ In and computes an estimate of hy Why. On input T1 ..... Zn. algorithm A works as follows:
Each user i runs the randomizer of A on I; get a response o; and sends it to the analyst.
For each j E [k:], the analyst simulates running the randomizer of A. on y1 = ... yn = j to get responses 01, 01.-..,0, on. Then, the analyst lets ēy be the estimator of A. based on the responses 01...., On 01 o'....,o,, on.
The analyst then outputs ($1...., ,2) as its estimate.
In other words, the randomized responses from & are used as an "oracle" for A' to compute the different linear queries. The key observation here is that, when we set y1
Yn = j. A produces an estimate for by Wh> = 13 Wh> = (Whx); as desired. Note that this reduction only works in the non-interaen inniinteractiv setting: if we were in the interactive setting, the responses on 21.-... Fy (of protocol A) would have been dependent on those of y,...., Therefore, the first step of the reduction would have been impossible.
While this encapsulates the high-level ideas of our proof, there are some details that needs to be handled. E.g.. if A outputs the quadratic form h Whxuy, there are "cross terms" of the form 1ig W h that need to be removed. We formally describe and analyze the full reduction in Section 4.
Black-Box Reduction to Linear Queries (Algorithm). We can also give a reduction in the reverse direction, although this results in an additional round of communication. Specifically, let A' be a non-interactive e-local DP algorithm for computing linear queries of W. We can construct a two-round (2s)-local DP algorithm A for computing the quadratic form on W as follows.
First Round: Run A' on all users to compute an estimate ($ 2x) for Whx-
Second Round: Each user E [n]], sends 0j = Łσ, + Ki to the analyst where Ky is (appropriately calibrated) Laplace noise. The analyst then outputs (0) +... o,).
Again, we omit some details for simplicity, such as the fact that each â may not be bounded priori, which may make the second step violate DP. However, these are relatively straightforward to handle.
If there were no noise, we would have oj 17 Whx and thus n (01 +...+ o,) h Why as desired. Furthermore, it not hard see that the error from Ni...., Kn dominated by the error from A' in the first step. In other words, we get an error similar to the one in Theorem 5 here, but the protocol is interactive (two-round). Making the protocol non-interactive requires us to step away from the black-box approach and open up the linear query algorithm (Theorem 4).
White-Box Algorithms. For simplicity, in this section we describe protocols with accuracy that depends on P22WW, ). which can be larger than C(W, n). The desired error dependence on <(W, n) can be obtained from this bound via a reduction, shown in Lemma 10.
To understand our algorithm, we first describe the matrix mechanism for linear queries (cf. [ENU20]. That algorithm works as follows: factorize W = = R. Then, user i sends of R1, :; + 2

---

where 2," is appropriately selected random noise. In other words, each user privatizes W1,, and sends it to the analyst. Finally, the analyst outputs L (o .... + ). This is exactly equal to Whx + L R where Z (=f +... + =. It is possible to select the noise in such a way that Z is (( (atei)uuuu--u-ssse Gaussian. This leads to mMSE of O (22)
This suggests a natural approach for quadratic forms: in addition to sending (a privatized version of) RI.,, the user sends privatized version of L1z,, i.e. of L1,; + at where 2t is a random
noise, to the analyst. The analyst then outputs ( (o +.... oh): 1 (of +.... -...)),,) Letting
z : + +2++) +2)). the output can be written as h W (L/xx Zh) ) (Rlxx -4) 24)+(24, =²)
There are three error terms: (Thx; ZR), ) (Rix; ) and (Z4, ZR). Similar to linear queries 22
analysis, it not hard to see that the first two terms contribute O
the MSE. Unfortunately,
6
the last term is problematic for us: a simple calculation shows that it contributes O ( ) to the MSE, where & denotes the number of rows of L, R. A priori, this term be quite large there is no obvious bound on f. In fact, if W is full rank (which the case for most popular pairwise statistics), then we know that must be at least k. This leads to an undesired error term O (FfE). which dominates the first term for small-to-moderade values of n, i.c., when S "
To overcome this, we observe that, if we only look for approximate factorization (in the same sense 72 aW; defined above), then it is always possible to reduce É via dimensionality reduction techniques (c.g.. [DG03J, Namely, we may pick a (e.g.. random Gaussian) matrix A and replace L, R with AL, AR respectively. Selecting the number of rows of A appropriately then yields Theorem 5.
Additional Interactive Algorithms. To describe our algorithm, let us start by instantiating the above black-box two-round reduction using the matrix mechanism. In this context, the reduction yields the following algorithm:
First Round: Each user i sends of = L1r; + 2 to the analyst, where 2f is appropriately selected random noise. The analyst then broadcasts O (of +.... +o,) to each user.
Second Round: Each user j E [m] sends 0j = (0r, Rl,,) + K2 to the analyst, where Ky is appropriately calibrated Laplace noise. The analyst then outputs _ + +... O.))
It is not hard to see that the Ky noise terms together contribute at most ((1/sn)) to the MSE. Therefore, the main noise comes from the first step. Similar to the previous discussion, this noise can be written + =/.). The contribution of this noise to the MSE is then
as Rhxx 2 where ZL
(af
O
22(W)) 2x The (W) term shows up in the error because || ll2 can be as large as ||]|| 1-2-
The idea motivating our improvement is simple: Can we replace the Rhx term with a term that is much smaller?
This brings us to the following strategy. We will use an additional round at the beginning to compute a rough estimate μ of Rlxx Using the so-called projection mechanism [BBNS19]*, it is possible
to compute μ such that || μlll < (rz(W)-(log o)) The subspace orthogonal to μ can be nda())
processed in a similar manner as before, but now the error term will just be (Rhx - p, z²) Since |[h /4|| is now much smaller (approaches 0 as n oo), this gives us the improved error bound. We note that the direction of can be handled by having each user directly send (of 1) plus an appropriately calibrated noise. This summarizes the high-level idea of our approach.
Due to space constraints, we focus on the non- -ntiretracttie algorithms in the main body and defer the proof of the interactive algorithm to the Appendix.
Preliminaries
Differential Privacy. For 8 2 0, an algorithm A eD for every pair X, X' of inputs that differ on one user's input and for every possible output o, Pr[M(X)= = of < E Pr(M((X) = o).
'See also [NTZ16] for the original projection mechanism that was proposed for the central model.
5

---

An algorithm A in the local DP model consists of a randomizer R and an analyst, computed as A said be (non-interactive)
A(X) (n( (.....,................ R(xx)) for imput X , Fn
8-local DP if R. is c-DP.
A real-valued random variable Z is o-sub-Gaussian iff E[exp (roppZ?//2\1 S 2. A & valued random variable Z is sub-Gaussian iff (0. Z)
Gaussinn for all unit vectors 0 R
Theorem 9 ([BBNS19]). For any C,E O, there is a (non-interactive) E-local DP algorithm VRand,,C C that takes in z E R" such that ||=||| I C and outputs Y E IR" such that E{Y] x and Y I is o--uu----aaae Gaussian for = O(C/e).
caaexiimtat--Pctoiiiaatii We show that it suffices to give errors in terms of (W) instead of <(W; n);; this will be convenient for our subsequent proofs. Due to space constraints, the proof of the following statement is deferred to Appendix A.
Error: Factorization vs
Lemma 10. Suppose that, for all W E TRk there is non-interactive e-local DP protocol A for ra(W)) quadratic form on W with MSE O (c(n,e,k) 6
wherec(n,, ((,,,,)) 2 2(1). Then there is also a non-interactive e-local DP protocol A' with MSE O (c(n,,,) k) 2'
((W:))
3 Non-Interactive Algorithm
In this section, we prove Theorem 5. To do so, let us start by defining (approximate) rank-restricted factorization norms², which are the same as 72(W), (W;; except we now restrict the number of rows of L, R to be at most f:
For W Rxk
L let
(ct (g(W) =
|||||=2|||||||1
For W E kxk le N and a 2 0, let (WW == min - W| ~ (W))
We can now use the approximate rank-restricted factorization to perform the algorithm as outlined in Section 1.2 with an error term that depends E (and oi):
Lemma 11. For any W IRkx kxk L N, and 2 0, there is non-interactive E-local DP algorithm
that estimates the quadratic form on W to within an MSE of O (a² + r2(WWa))
=
Proof. By definition of 75( (:: a), there exists W E kxk I., R E R txk such that | - Wl S
and W L where, w.l.o.g.. by rescaling, || - ||]|| Vz5(W)= C.
Algorithm Description. Let E = e/2. The algorithm works as follows:
> Each user E [n] sends y + VRandg (where VRand. (-) from Theorem 9).
and yu" + (Randg.c(R1, to the analyst
> The analyst outputs (1 Eielmi E wf²)
As each user runs an (E/2)-DP randomizer twice, the algorithm is s-DP.
Utility Analysis. Let 2 y. - L1,, and z = y R1 From Theorem 9, 2 2 are zero-mean RR and Sauu-aaas for a = OC Let 2 = 1/ Eie(m) of Z == 1/2 Σie(n) 2, we then have that these zero-mean and a¹
for o' o/ Vn. The MSE of the protocol is given by
27
E
Σ R
h h/x hix
11
1E(m)
xE(m)
[1 w)ix + +ZZ RR) + (Lh,
+ ) ( ) 2
E
< B(b w) 2 (2 Rh)² +E (Lh, 2 + + + ,2R?
$ - - + (o') RA + (o')
+ + (o')*
'heee actually norms, but use the term for consistency with other similar quantities.

---

I <a Sa (o) (d' Sa Ca + enn²"
+e- (d')²
C.
2nn
Rank-Restricted Approximate Factorization via JL. We next show that w.l.o.g. we can take to be quite small in Lemma 11 above.
Lemma 12. Ler W E I kok and a (2W),, there is E "2(W) with 72(W; S r2(W).
a²
As mentioned earlier, this lemma is proved by applying Johnson-Lindenstraus (JL) dimensionality reduction to each column of L, R. We summarize a simplified version of the JL lemma below.
Lemma 13 (Johnson-Lindenstrnnn Lindenstrauss Lemma (e.g., (DG03J)) Let (0, 1) and U {ui,... um S Rd For some < O 22 log m) there exists a matrix A E Rxdd such that for all u, v E U, we have (1 - 2) v11 < Au A (1 B) 2112.
We are now ready to prove Lemma 12.
Proof of Lemma 12. By definition of 72 (W), there exists L, R Ba for some d E such that W = I R where] T-|l--2 = || = (2) C.
Let LI...., La (resp. RI...., R&)) be the columns of L (resp- R). Consider U
{0, Li.... Ln, Rl..... Rk. -i....., - LLk -R,.... R& and 3 = 0.5a//²; let l
O 13 log 0 (>2(W)2 logk and A IR exd be guaranteed by Lemma 13. a²
Let L AL, R AR, and W = R. For all E [A]]. we have || 1 (1 + 3 and || < +1+ R, Moreover, for each i.j [k], we have
R. Therefore, || | R||1-2 & OCC), i... 7S(W) - (W))
Wis Wis = Li, R2) (Li, RA)
1
(IIZ, + +R,113 ||4 + R2112 + |
R II,, Ra188
$ 4
8
$ (114, +R,113 11 12,13)
$ 2 a.
Thus, || W| 1 S and therefore 75( - (W)))W) as claimed.
We end this section by proving Theorem 5, which simple combination of Lemma 11 and Lemma 12.
Proof of Theorem 5. Pick a = (W) and apply Lemma 12: There exists f = O (2((W) log Ev"
O ((log k))²n) such that 75 (W; < ((T)(W)). Plugging this back into Lemma 11 then gives us a non con-interactive e-local DP protocol with MSE
(
1 22n
log k E2n
?2(W)² (o
a + (WW
S22)2 s-n E
S
22
Applying Lemma 10 then concludes the proof.
Lower Bounds for Non-Interactive Algorithms
In this section formalize the reduction from linear queries computing quadratic forms, as outlined in Section 1.2. The properties of the reduction are stated in the theorem below.
'We may assume w.l.o.g. that I >x(W); otherwise, the guarantee in Theorem 5 is trivial, i.e., always outputting 0 satisfies the bound.
7

---

Theorem 14. Let W E Ri* be symmetric. Suppose that there is a con-interactive E-local DP mechanism for computing the quadratic form on W with MSE at most a(e, n). Then there is non- interactive e-local DP protocol for computing the linear queries of W with mMSF. ( ale/2,2n))
Theorem 14 and the lower bound in Theorem 4 immediately imply Theorem 6. In the proof below, we use subscripts E, n to denote the privacy loss parameter and the number of users in the protocol.
Proof of Theorem 14. Let Ae,n be the e-local DP protocol for computing the quadratic form on W, and let Re, denote its randomizer. We construct an algorithm A',, for linear queries with workload matrix W. On input ,.,...,, Fn proceed as follows:
Run the protocol of Az/2,n on #1, Tn to compute an estimate for hig Alix
In the same round as above, run the randomizer Re/2.2n of 22/2,2n on , In to get the responses R (e)2n)..))
For each [k], do the following:
b Run the randomizer R of A on 1/1 ..... Yn = j to get the responses Re/2.2n (B1).
Re/2,2n
b Compute the estimator z'J of A on the 2n responses (e/2,2n(21), Re Re/2.22 (Nn),
Re/2,2n ...)..... Re/2.2n (yx).
Set 23 22/ 2 11,W1
Output (21,.... 2,) as the estimates for the linear queries.
Since (e/2)-local DP randomizers run on each input x;, twice, the basic composition theorem implies that this is e-local DP algorithm as desired.
For each j E [k], we now compute the MSE of 2j. First, observe that
(Whx), - 1 = (h Wh Whxuy)
1 h
1 Wh
-,,,, w1,
2
2
where y denotes the dataset with copies of j. Therefore, bound the MSE of ēg follows:
2 (Whx);) E (ē) (W
1 +2 (2-NTwwkl) 27
2 (2/) b W Whx,))
E
(2/ h W Wixxu)) )
E [8- bZ
ass/2, 2n) + a(E/2, n),
where the last inequality follows from the guarantees of A. Thus, the mMSE of A' is at most ((a(=/2,2n) + a(s/2,n)) n)). as desired.
Upper Bounds for Specific Metrics
In this section, we obtain concrete upper bounds for many well-known U-statistics of degree 2. For kernel X R. let W IR xxX' denote the matrix defined by w W...r f(x x'). Our proof of Corollary 7 proceeds by providing an upper bound on (2 for each U-statistic with kernel f: the bounds immediately follow from Theorem 5. Similar to before, let A denote |x]
The following (non-trivial) facts about the factorization norm are useful to keep in mind:
Fact 15. The factorization norm "/2 satisfies the following properties:
1. [TJ89] For any A, B, we have 72((A A + B) < 72 + (B). 2. [LSS08] For any A, B. Te( A & B) = (A) (B).
8

---

Gini's diversity index. For X' _ R. the kernel f(z,x') = 1[x * x'] captures Gini's diversity index. From Fact 15(1), we have 7/2 (W") - 72 <x(1*xk) + 722 kx*)) I 1 + where the inequality (1xx)) & 1 is from the factorization
R 1s and (Ixx)) S 1 is from L R Laxk-
Kendall's т coefficient and AUC. For X = A B C R with 2; = (vi. 2.), the kernel f((u,,2) 24), (gg:2)) = (gg - 2 2y) yields Kendall's T coefficient. Let Um E [-1,1)" 1 denote the matrix that has +1 all entries above the main diagonal (inclusive) and - elsewhere. It is known that (2(Um) = (log m). We can bound 722 ) for Kendall's t coefficient by observing that W = U @ Up- From Fact 15(2), 72 (2 S (UA)) (2(UB) & (log [A]) (log BI) I (log k)².
AUC for binary classification is defined in a similar manner as Kendall's ' tau coefficient, except that (i) B = {0,1] and (ii) the normalization constant being n n. instead if - where n* (resp., n
(2)
denotes the number of 1-labeled (resp.. 0-labeled) examples. The AUC result follows from the above since [B] = 2 in this case. We remark that, for the AUC case, we also have to split the privacy budget and use half of to estimate n+ so that we can renormalize correctly. is not hard to see that this renormalization procedure results in at most an additive factor of O 2 in the MSE, under the
balancedness assumption that .=+ S2()).
Lipschitz Losses. Let X = [0, 1] and let f X R be any function such that (f()) f(d') S G-Iz- 1-|x--0 z/|; we call f G-Lipschitz. This class includes U-statistics such as the Gini's mean difference, which is given by the kernel fzx,,
I. zyI. which is 1-Lipschitz.
Similar to [BBGK20], we use a discrete case where X = [k] as a subroutine. Our algorithm for this is stated below. Note that Corollary 16 immediately implies the bound for the continuous case: given any function f [0. 1] - TR, we may select k to be sufficiently large, e.g., k = O(en²). ). and discretize
the function over the points 1/k; 2/k, ..... k/ k. Defining g [R:] TR. by g(i) -((kk) allows to
use Corollary 16 with Lipschitz constant G/k. This leads to a MSE of O G2 (oggennn?
The MSE
22n
resulting from the discretization error is then at most G²p² E² <
G² 2"
Corollary 16 (Discrete Lipschitz). Assuming X' = [kc] and that I is G-Lipschitz. There a non- GG& (log k) c
interactive e-local DP algorithm for computing pairwise statistics for with MSE O
Again, the above corollary follows from Theorem 5 and the following factorization.
Lemma 17. Assuming that f [k]] - R is G-Lipschitz, then (2 < O(Gk).
Proof. We assume w.l.o.g. that l: = 29 1 for some q E N and ||W S Lk; otherwise, we may shift W (and the answer) without incurring any additional error. We arrange [k] into a balanced binary search tree T of depth q y-1 naturally (where the root is 2 and the leaves are ........ .,, k). Let P(j) denote the path from node j to the root (inclusive) in T, and let {(j) denote the depth of (where the root has depth 0). Furthermore, let parent(j) denote the parent of j in T. For notational convenience, let parent (29-1)- =1 and let (ú, 1) = for all E [k].
We construct T., R E & as follows.
For all i,j E [k]. let Rt,j = (2) {(1) 1l1 E P()]-
For all i E [k]. Ljs = (0) 80) (f(i.) f(i, parent(j))).
For i,j E [k]], we have (L R) = ElEP()) (f(i,)) - f(i, (aren(((()))) = f(,,)). Thus, L = W.
Furthermore, || 1 1+ (3)² + (3) 2(00-)) z 1. Meanwhile, we can bound ||]| by
6 80) (((i.)) S(i, parent())))
6
Gk
max xE
5
2d
5
2d
$
G
JE[M]
d=0
where the first inequality follows since f is G-Lipschitz. Thus (2(W!) < O(Gk).

---

Conclusion and Open Questions
In this work, we systematically study the problem privately computing pairwise statisties. We give non-interactive local DP algorithm and a marly-natching lower bound for the problem. Furthermore, we show that, for some metrics, improvements can be made if interaction allowed.
There are several immediate questions from our work. For example, log A multiplicative factor in our non-interactive algorithm (Theorem 5)? Similarly, can the second additive term in our interactive algorithm be removed? As also suggested by [BBGK20), an intriguing research direction is study involving triplets instead of pairs). It would be interesting to see if techniques from linear queries and from our work can be applied these problems.
possible to remove the
complicated statistics such the "higher-degree" ones (e.g., those
10

---

References
[Abo18] John Abowd. The US Census Bureau adopts differential privacy. In KDD, pages 2867-2867, 2018.
[ACG+16 16] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In SIGSAC, pages 308-318, 2016.
[App17] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017.
[BBGK20] James Bell, Aurélien Bellet, Adrià Gascón, and Tejas Kulkarni. Private protocols for U-statistics in the local model and beyond. In AISTATS, volume 108, pages 1573-1583, 2020.
[BBGN20] Borja Balle, James Bell. Adrià Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. In CCS, pages 657-676, 2020.
[BBNS19] Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. Towards instance-optimal private query release. In SODA, pages 2480-2497, 2019.
[BDKT12] Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar. Unconditional differentially private mechanisms for linear queries. In STOC, pages 1269-1284, 2012.
[BHBFG+22] Gecia Munoz Medina, and Umar Syed. Private and communication-effiien algorithms for entropy estimation. NeurlPS, 35:15382-15395 2022.
Róbert Busa-Fekete, Mohammad Ghavamzadeh, Andres
[BNO08] Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simultancously solving how and what. In CRYPTO, pages 451-468. Springer, 2008.
[Bub15] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4)2231-35) 2015.
[BUV18] Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM J. Comput., 17(5):1888-199 -938,, 2018.
[CM23] Graham Cormode and Igor Markov. Federated calibration and evaluation of binary classifiers. Proc. VLDB Endow, 16(11): 1):3233-3266. 2023.
[CSS12] TH Hubert Chan, Elaine Shi, and Dawn Song. Optimal lower bound for differentially private multi-pane multi-party aggregation. ESA, pages 277-288, 2012.
[CSU+ 19] Albert Cheu, Adam D. Smith, Jonathan R. Ullman. David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In EUROCRYPT, pages 375-403, 2019.
[DG03] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Struct. Algorithms, 22(1 ):60655, 2003.
[DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In NeurlPS, pages 3571-3580, 2017.
[DMNS06] Cynthia Dwork, Frank McSherry. Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
[EGS03] Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In PODS, pages 211-222, 2003.
[ENU20] Alexander Edmonds, Alcksandar Nikolov, and Jonathan R. Ullman. The power of factorization mechanisms in local and central differential privacy. In STOC, pages 425-438, 2020.
[EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In CCS, pages 1054-1067, 2014,
11

---

[GMPV20] Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggre- gation from fewer anonymous messages. In EUROCRYPT, pages 798-827, 2020.
[Gre16] Andy Greenberg, Apple's "differential privacy" is about collecting your data but not your data. Wired, June, 13, 2016.
[HT10] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705-714, 2010.
11] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? SIAM J. Comput., 40(3):793-826, 2011.
[KT18] Krishnaram Kenthapadi and Thanh T. L. Tran. Pripearl: A framework for privacy- preserving analytics and reporting at linkedin. In CIKM, pages 2183-2191, 2018.
[LMH+ 15] Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. VLDB J., 246))77777811, 2015.
[LMSS07] Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. Complexity measures of sign matrices. Comb., 27(4):439-463, 2007.
[LSS08] Troy Lee, Adi Shraibman, and Robert Spalek. A direct product theorem for discrep- ancy. In CCC, pages 71-80, 2008.
[Nik23] Aleksandar Nikolov. Private query release via the johnson-lindeensrrass transform. Nikhil Bansal and Viswanath Nagarajan, editors, SODA, pages 4982-5002, 2023.
[NTZ16] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry differential privacy: The small database and approximate cases. SIAM J. Comput., 45(2):575-611 2016.
[RE19] Carey Radebaugh and Ulfar Erlingsson. Introducing TensorFlow Privacy: Learning with Differential Privacy for Training Data, March 2019. blog. tensorflow. org.
[RSP*21] Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. Linkedin 's audience engagements API: privacy preserving data analytics system at scale. J. Priv. Confiden., 11(3), 2021.
[Sha14] Stephen Shankland. How Google tricks itself to protect Chrome user privacy, CNET, October, 2014.
[TJ89] Nicole Comezak-Jacgermenn Banach-Mazz distances and finiteddimensional opera- tor ideals. Pure and Applied Mathematics, 38:395, 1989.
[TM20] Davide Testuggine and Tlya Mironov. PyTorch Differential Privacy Series Part 1: DP-SGD Algorithm Explained, August 2020. medium com.
12

---

A Additional Preliminaries
We use dev, dKL to denote the total variation (TV) distance and the Kullback-Leibler (KL) divergence between two distributions. Pinsker's inequality states that
(P,
V2 dkL(Pl (),
(I)
for all distributions P.Q.
Interactive Local DP
For interactive local DP, we consider protocols that proceed in rounds. each round, the analyst may send a message (which may depend on what the analyst has received in the previous rounds) to each user, who then replies back with (randomized) response. The DP guarantee is then enforced on the view of the analyst.
Clipping and Resulting Error
Clipping is standard technique in DP achieve bounded sensitivity (ef. [ACG+16)). In interactive algorithm, we will use clipping on real values to bound their sensitivity, More specifically, for 2 0, let clip, R R denote the function:
T
if T if 2 x -T,
cip,((x)
=
- > x.
There could be additional errors resulting from clipping. For the purpose of bounding such terms, will use the following simple lemma:
Lemma 18. Let X denote any random variable over T. and any 2 0. Then, we have
E clip, / [ Pr| T].
Proof. We can bound the LHS term by
E[(X- cx))
s E[X² | T]]
I /E[X*| | -|2]
= EE[X*] Pr > T]
where in the second step used the
inequality.
Factorization vs Approximate-Facttriizze
Proof of Lemma 10
Proof of Lemma 10. Let W be any matrix. By definition of Ç, there exists W such that ((W;n) (2W) + !| - W (Evn). The new protocol A' simply runs A but on W. Let & denote the output of A'. Its MSE can be bounded by
E
2 wxx)
E
((
1 W/xx
[ Wh - 1 W/xz)))
S E
( 1 w/x
+E ( WiWWix 11x - 1 W1xx)
22(22
c(n,e,k):
||W - 1
82n
s(W;n)²
<(W;m)²
< (n,,,
E2n
EPn
n(W;n)²
S Scn,E,K)
g2n
13

---

Projection Mechanism
As outlined in Section 1.2, we will use the projection mechanism as subroutine for our algorithm.
For W R we define WA to denote the set {Wax x x R² ||æ||| S 1]. The guarantees of the algorithm are summarized below.
Theorem 19 ([BBNS19]). For any workload W E R there is non-interactive e-local DP mechanism M such that
W WW 2og
E Bu=M(o) Whx 11
EVN
Moreover, the output M(W) always belongs to W
We provide the proof below for completeness.
Proof of Theorem 19. Let C = ||ill-22 The algorithm works as follows:
Each user E [r]] sends == "Randd,c(W1,, to the analyst (where VRand. (-) is from Theorem 9).
The analyzer computes Y == 1 (i)))) Yr and then outputs == argmin ||u Yl12-
The privacy guarantee of the algorithm follows from Theorem
W1 W1,. From Theorem 9, 2; is zero-mean and c-sub-Gaussian for o O(C/e). Let Z := Lig in] 25 we then have that is zero-mean and o'-sub-Gaussian for o' o/ /n. By the definition of Sub-Gaussian random variable and a union bound, for every 0, with probability 1 - 3 the following holds:
Let 2,
C
(W 2115
eVv Vlog(k/B)
bj E kk]
where Wj denote the jth column of W.
is well known? that if define μ as we did (i.e., projection of Y on WA), then we have (p w. Y) 0,
for all w WA
Plugging in w = W hxx we have
|| Whx
12 = (n Whxx 11 Y) + (u - Whxx Z)
I (1 W Whxx² 2)
S max
(w', Z)
w'
max
(W, Z
kk(k]
where the equality follows from the fact W is the convex hull of Wi...., We. - -W,.... We-.
Putting together (2) and the above then yields
C² Vogk
Blll Wh
Evn
B On the Lower Bound for Linear Queries from [ENU20]
In this section, we provide details on how we can interpret the bounds of [ENU20] stated in the form of Theorem 4. The lower bound in [ENU20] is originally for the loe -error; we make the observation below that a simple modification of their proof can be made so that it applies mMSE. Note that, in addition to getting stronger result in terms of error metric (because lower bound on
See e.g.. [Bub15, Lemma 3.1].
14

---

mMSE implies the same lower bound on eer-rr,,,, we also get quantitatively stronger bound that does not depend & because we avoid having to take union bound over lt queries (which was required for the proof for -errrro in [ENU20]).
In [ENU20, Section 3.4], it was shown that w.l.o.g. it suffices to consider "symmetric" workload matrix W (i.c., ones that can be written as - for some W'), We will thus do so throughout the rest of this section. Following their notation, we also assume that W E R x i..., A' is the imput space and there are & linear queries. We also recall the following two lemmas from their paper.
Lemma 20 ([ENU20, Lemma 11]). Let (0, 1]. For any distribution X1,..., Ams Mi..... ......... Pm X. distribution π over [m] and E-local DP randomizer R, we have"
E Evn (dxz (R(),)) R((x)) )²)] nE? -12(m))
where M R.xX a matrix such that M (x( (x()).
We note that in [ENU20, Lemma 11], the LHS is not exactly the same as in our version above. However, inspecting the very first inequality from their proof shows that their bound goes through the quantity the LHS of Lemma 20.
The next lemma, which describes the properties of the hard distributions, is arguably the main technical contribution of the lower bound in [ENU20].
Lemma 21 ([ENU20, Lemma 21]). Let W E R*x* be any symmetric workload matrix and a > There exist & 2 O, and distributions . Ak. Pl..... . Pi on X' and ßं over [k]] such that
(i) (WX.); = for all i, E [k].
(ii) for all supp(f), (Wiz) Z log( /a)
t+
(iii) Let M be defined similarly as in Lemma 20. Then [M & (W.aa)
will in fact be easier to work with the following version of the lemma, which is implicit in the proof of [ENU20, Theorem 22]:
Lemma 22. Les W I xxX be any symmetric workload matrix and 0. There exist distributions
....... Ai...., dR, P1, ..... fuk X' and से over [k] such that
(i) (WX.); for all i, [K]]
(ii) for all supp(ā). (W Wo) Z log( /a)
(iii) Let M be defined similarly as in Lemma 20. Then || (la E (WW,a)
Proof Sketch. This is constructed by taking Ay...., Ar..,.... P....., Px and from Lemma 21. Then, replace each jo, by the mixture (1 - (3 A + B Aü where B = m a/E), for all e E [k). Both the lower bound for W.)) and the upper bound for || ( scale linearly with B, yielding the desired bounds.
We can now prove the following, which is more qualitative version of the lower bound Theorem 4. Theorem 23. Let W E IR kxX be any symmetric workload matrix. Any non-interactive e-local DP
S(W.)) 8
mechanism must incur an mMSE at least Q
lox
'Here || Lz)(x> max]]=]]=== ||M2]lza(m) where ||a|| [a]l = Eve(() T(V)a Note that we will dealing with this quantity further than here.
"In [ENU20], & is related to the dual solution as { = W e where U is the dual witness of the approximate factorization norm, i.c., one with (W) = WOU (See [ENU20, Section 2.3) for more details.) However, these specifies are not used the remainder the proof.
Note that the [[W] olo term does not show up in [ENU20] since they assume that ||| 1.
15

---

Proof. For notational convenience, we write Ç as shorthand for ((W,n) n).. Let = Gc where C1 E (0, 0.1) sufficiently small constant. Suppose for the sake of contradiction that there exists non ioon-interactive e-local DP protocol (whose randomizer is R) with mMSE at most (a')² for a'
sve
C.o where C2 E (0, 0.1) is sufficiently small constant.
log( [=
Recall the definition of Ç; we must have Ç S 72 (W, 22 2- This gives
5 2
W. 22
Since 72(,,,) is increasing function, thus have
aE n (2(W, S C1.
Let Ai...., de, u1,..... .... To and न be as in Lemma 22. By Lemma 20 and Lemma 22(iii), we have
aE aEVT (W, a.)
Evw del, (R(,.)) R(u,)")
(4)
On the other hand, since the protocol has mMSE at most (a')?, we may use the following algorithm to distinguish R(x,,)" from R(,,))" let the analyst computes an estimate for Whx (using the samples from RR(-) provided). If the estimate has absolute value less than 10a', then output Xp: otherwise, output Ma From Lemma 22()) it is not hard to see that, for C2 that is sufficiently small, this algorithm is correct with probability at least 2/3. This means that (R(A,)) R(u,)") 2 1/3. Pinsker's inequality (i.e., eq. (I)) then yields dkL (R(A.)" R(p,)") Z 1. Comparing this with the asv'n 2 1, which contradicts eq. (3) when Cj is sufficiently small.
above eq. (4), we get (W,a)
C Three-Round Algorithm
In this section, we describe and analyze our interactive algorithm. The error guarantees of the algorithm are stated below. (Note that Theorem 24 is more precise version of Theorem 8.)
Theorem 24. For any W E kxk and > á (2>(WM) (Wyy" log
(
there a three-round E-DP algorithm
for estimating quadratic forms on W such that the MSE is O [III.
Proof. Throughout the proof, assume that Q
22 log log (U)2(W)lae log where Q is W
[W
sufficiently large constant. Recall from the definition of (W) that there must exist T., R such that W = L' R and [|]11-2 ||]]
(W) C.
Algorithm Description. Let E e/4 and T llee The algorithm works as follows:
b First Round: Run the 8-local DP protocol from Theorem 19 to get an estimate f of Rlxe
D Second Round:
The analyzer forwards _ to all users. Each user i [n]] sends the following to the analyst:
v - VRandy,c (L1,,) (where VRand. (-) is from Theorem 9).
> a, + (L1,,, (R) + K; where K; ~ Lap(2] lle//) back to the analyst.
Third Round:
The analyst then computes yb n
Σ Dieln v and forwards it the users.
Each user E [m] sends v; t clip,((Y', Rlz, - -RR) + 2, where 2, ~ Lap(2r/E).
Finally, the analyst outputs 1 4 (Eve(n) a:) + ( w.).
16

---

Privacy Analysis. Each user i's imput is used four times:
To produce f. This step is E-DP by Theorem 19.
produce y!- This step is 6DD by Theorem 9.
To produce 0ç- From the guarantee of Theorem 19, Pa belong to R As result, (Lig,, S ||W] In other words, the sensitivity of (Lig, Pa) (as a function of x;) is at most 2 [ Since K; is sampled from (ap(2[[W]oo//E this step is also E-DP.
To produce Ug Due to clipping, the sensitivity of clip, ( is at most 2r. Thus, since we are adding a noise 2, drawn from Lap(2r/2 (ē), this step is also E-DP. Hence, by the basic composition theorem, the entire algorithm is E-local DP as desired.
=R) (as a function of x;)
Utility Analysis. First, notice that, for fixed un RA,, have
hig Whx (blix; Rlxx = (Llix; + (Lixx, Rhx (RR))
(L PR) +
(Lhx, Rlx, - PR).
11 VE
KE(M
Let 2 y Il1, From Theorem 9, 2. is zero-mean and o-sub-Gaussiag for OC//E) Let
z-_ " LiEnj #;: we then have that z is zero-mean and that 8-
for o' = 0/ /T. Note = Ihx + Z Furthermore, let us write 0 as a shorthand for cli,,((Y,, 11,,, pn) (Y (Y',RI,, pR)-
The MSE can be bounded by
E
Vi
1 whx
m
iE(m)
iE|m]
E
Σ
+
Σ
+
Zz
Rhx MR) + Σ 0:
VE(m)
=E[m]
27
27
|
$ EE
Σ Ki
+
1 Σ
+ E (z R/xx (R)) +B
0:
VEIN)
sEin]
iE|n]
[ 1
+ E (z", Rhx - PR)
+
Σ
E [?
(5)
E2n
sEin]
where the last step is by applying the
inequality to the last term.
To handle the middle term in eq. (5), note that 2L is independent of μr and, as stated earlier, is a "-suu-Gaussian Thus, have
E (Z Rhx uR) = EugLEzz (Zt, J02,,hx (R))
5 Epp(( (o (0')2 12 mall2
C² Vook
(From Theorem 19) S (o')2
e/n
C* VoVlog k
33n
(6)
8?n
where the last inequality is due to our assumption on n. As for the last term in eq. (5), notice that
(Y R1.; UR) , pR) + (Lhx, RIs; (R))
17

---

Since PR belongs to R we have (R1,, pR) R which implies that (Lhx, Rls, -MA)
2|[W|] oz and |R1, Mall2 S 2C. As such, we have
E(Y Rln. pR)
S B (z
R1z, (R)
+ |W
2 (d')* C+ + 1
C
stm? + ||
|| 1l:
where the last inequality is due to our assumption on n and from 72(W) 2 | Meanwhile, since = 4||W]| we have
Pr[ (Y Rl.;
(R)
Rl.; UR) > T/2
exp (006T/(''22)))
= exp (-0(e]/W]l
g'n2
where the last inequality is again due to our assumption on n and from (2(W) 2 || Thus, we may apply Lemma 18 to conclude that
W
&
Enn2
e2n
[W]
Combining eqs. (5) (7), the MSE of the estimate is at most O
desired.
C.1 On Separating Non-Interactive and Interactive Local DP
We end by observing that our interactive local DP algorithm (Theorem 24) together with the non- interactive lower bound (Theorem 6 and particularly, the more quantitative version, Theorem 23) gives an asymptotic separation on the MSF achievable by e-local DP interactive algorithms and those that are non-interactive, as long
pick W together with N such that the following holds:
n
>w(W) iog log
(00x((W) log [[
and
C(W W 2 wlog
where the first condition is from Theorem 24 (and letting 1) and the second condition ensures that the error from Theorem 24 asymptotically larger than the lower bound from Theorem 23.
is simple to verify that it suffices to pick W such that |[W]] = 1, 72 (W, 021),72(W)) = O(k*) for and pick to precisely satisfy the bound in the first condition. Again, is not hard to construct such a matrix e.g., by taking W to be random (k x k) matrix where each entry is an i..dd Rademacher random variable, which yields (W, 0.1), (WV) θ(Vk) w.h.p. (LMSS07).
any constant
18


Reviews:
[{"review_id": "fihaKRdcKY", "reviewer": "Reviewer_q1oD", "summary": "The paper considers the computation of quadratic forms of histograms under local differential privacy (LDP). Previously, special cases of this problem have been studied, but this paper presents a general theory analogous to the existing theory for linear queries. The problem is studied both in the standard LDP setting and using \"interactive\", multi-round protocols where each user outputs an LDP value in every round. The 9-page submission focuses on the standard, non-interactive setting. Lower and upper bounds are presented that are tight up to polylogarithmic factors. A sketch of interactive protocols (with better utility) is presented, with details in supplementary material.", "questions": "- Can you comment on potential practical use of your results? Are there large factors hidden in big-O notation, and in particular what kind of data size is needed to get good utility for the examples in Corollary 7?\n- The shuffle model is sometimes used to amplify privacy of LDP protocols. What results in the this model are implied by your results?\n- In line 36, I suppose $\\mathcal{X}$ should be $\\mathcal{X}^2$?", "limitations": "Since there are no experiments, I would have like at least some discussion of the extent to which the protocols proposed might be practical, or whether the contribution is considered purely theoretical.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Identifies a natural problem for which special cases have been studied before and presents a general theory\n- The results are tight (up to polylogarithmic factors) for *every* quadratic form\n- The techniques for multi-round LDP protocols are particularly interesting, and separate single- and multi-round LDP for a natural problem\n- The mechanisms are simple to describe\n- The paper is very well-written", "weaknesses": "- Though LDP has been deployed in practice, its general usefulness has sometimes been questioned, since it tends to require very large data sizes to get good utility", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review & questions. Please find the answers to your questions below.\n\n- While we omitted the constants (following the precedence of not reporting exact constants in most previous work), it is not hard to compute them in Corollary 7.  We will consider adding them in the revision. In terms of practicality, our algorithms subsume those in previous work such as [BBGK20, BHBFG+22]. Therefore, the practicality is similar, e.g., our protocol for Gini’s diversity index has less than 0.01 error for $\\epsilon=3, k \\leq 1000$ and $n \\geq 100,000$.\n\n- This is a great question. Our non-interactive algorithm only requires a vector-summation primitive (where each vector has norm at most $C$). Since known protocols for vector summation in the Shuffle model achieve an RMSE of $O\\\\left(C\\\\cdot\\\\sqrt{\\\\log(1/\\\\delta)}/\\\\epsilon\\\\right)$ [Balle et al., CCS 2020], we can simply replace Theorem 9 in our paper by this protocol and reduce MSE by a factor of $n$ in Theorem 5 and Corollary 7. Thank you for suggesting this; we will add this to the revision.\n\n- Re line 36: Yes, $\\mathcal{X}$ should be replaced by $\\mathcal{X}^2$. Thank you for pointing this out; we will fix this in the revision.\n"}, {"review_id": "q9fYBIwY2N", "reviewer": "Reviewer_6AxR", "summary": "This paper studies the problem of computing Quadratic Forms $h_x^TWh_x$ under Local Differential Privacy, where $h_x$ is the normalized histogram representation of a vector $x\\in [k]^n$. In particular, reductions to and from the problem of computing linear queries are established, through which algorithms and tight bound results (in mean squared error) consequently follow from those in linear queries. The reduction from linear queries is built on the observation that the $j$th entry $(Wh_x)_j$ of the linear query can be obtained from three quadratic forms:\n\n($h_{x\\cup 1_j}^TWh_{x\\cup 1_j}$), ($h_{x}^TWh_{x}$) and ($h_{1_j}^TWh_{1_j}$). \n\nThe reduction to linear queries is built on two observations: 1) $h_x^T W h_x^T$ is a linear query on $h_x$ with weights $Wh_x$ (also a linear query); 2) $h_x^T W h_x^T$ is an inner product of $Lh_x$ and $Rh_x$, where $W=L^T R$. The second approach can be further refined, where using a JL projection on $L$ and $R$ allows the magnitudes of the noise terms associated with privatizing $Lh_x$ and $Rh_x$ to be reduced to $O(\\log n)$ from $O(k)$.", "questions": "- In the proof of Theorem 14, line 286 requires $W$ to be symmetric? ", "limitations": "N/A.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper presents a generic framework for estimating pairwise statistics that can be expressed as quadratic forms (although utility in some statistics can be improved by exploiting their specific properties).\n- The ideas used are interesting and natural, the presented analysis is solid.\n- They discuss both interactive and non-interactive settings, and show that computing pairwise statistics separate interactive and non-interactive local DP.", "weaknesses": "- In the proof of Theorem 5, the condition on $\\alpha$ requires $\\varepsilon \\ge 1/\\sqrt{n}$, but $l=O(\\log(k) \\varepsilon^2 n)$ requires $\\varepsilon < 1$ for $l< n$? These place $\\varepsilon$ in a restrictive range.\n- Although the main paper focuses on presenting reductions in the non-interactive setting, there are places where the discussions of interactive and non-interactive appear together, which caused some distraction for me. I think all of the discussion on the interactive setting can be moved to its own section toward the end.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review & questions. Please find the answers to your questions below.\n\n## $\\\\epsilon$ value in  Theorem 5:\nWe remark that the lower bound requirement $\\\\epsilon \\\\geq 1/\\\\sqrt{n}$ for non-trivial utility is present in essentially _all known_ local DP results and is supported by Theorem 6 (which implies that non-trivial utility is impossible when $\\\\epsilon \\ll \\\\tilde{O}(1/\\sqrt{n})$). In fact, to the best of our knowledge, this is required to get sub-constant error even for the very simple problem of averaging binary values.\n\nOn the other hand, there is no upper bound required on $\\\\epsilon$. Note that our proof of Theorem 5 works for arbitrarily large $\\\\epsilon$ and the condition $\\\\ell \\\\leq O(\\\\log(k)\\\\epsilon^2 n)$ does *not* enforce any upper bound on $\\\\epsilon$.\n\n## Writing (Interactive vs Non-Interactive):\nThanks for your suggestion and apologies for causing the distraction.  In the revision, we will consider separating the discussions on the interactive vs non-interactive in a more streamlined way.\n\n\n## Theorem 14: \nWe implicitly assume that $W$ is symmetric, which is the case when we construct $W$ from a kernel $f$ as specified on line 293. Indeed, line 286 uses symmetry of $W$ as you said. We will make sure to clarify this in the revision. (Note that our algorithms work even for asymmetric $W$. However, the lower bound is harder to handle due to the cross terms.)\n\n\n"}, {"review_id": "Hbr37CWNpf", "reviewer": "Reviewer_xtaj", "summary": "This paper studies the computing of pairwise statistics with local differential privacy by considering the quadratic form computation.  In order to obtain the lower boudn and uppoer bounds, it proposes the inter-reductions between quadratic forms and linear queries.", "questions": "Q1:  Could you pls explain the logic behind the sentence in Line 150?\n\nQ2: Could you explain more the matrix mechanism especially the factorization? (Line 159)\n\nQ3:  I don't see the reasoning in Line 288 especially the second line there about \"cross terms\".", "limitations": "This paper highly depends on the results in ENU20. I don't see any significant technical contribution in this paper ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Studying pair statistics with local differential privacy is intersting. ", "weaknesses": "(1)  The presentation needs some improvement.   There are many grammmatical mistakes in many  places.  The preliminary part is quite messy: a formal definition of central differetial privacy is given but the definition of local DP is informal.   Randomized response mechanisms are not defined in the paper.\n(2)  I don't see the significance of the two reductions in Section 1.2.    Either the reductions are trivial or the subtlety has not been made explicit yet. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## High-level Response:\n\nWe completely agree with the reviewer that the reductions in Section 1.2 are simple, _but only in hindsight!_ On the other hand, we think of this as a significant contribution of our work for the following reason.  While previous works [BBGK20 (AISTATS’20), CM22 (VLDB’23), BHBFG+22 (NeurIPS’22)] had elaborate and specific algorithms for _each_ specific kernel $f$, our reduction gives algorithms for *all* kernels that essentially match (and sometimes even improve upon) the guarantees in previous works. Similarly, none of the previous work showed any lower bounds for their problem, meanwhile our reduction gives nearly tight lower bounds for all possible kernels in the non-interactive setting (Theorem 6). In summary, our reductions give simple, tight, and extremely general results for the problem of computing pairwise statistics.\n\n\nRegarding the comparison to [ENU20], we wish to point out that we study a *completely different problem* (computing pairwise statistics) compared to that paper (computing linear queries). Indeed, one of our main (and arguably surprising) contributions is to show that these two ostensibly unrelated problems are intimately related.\n\n\nWe hope the reviewer will consider these points in their (re)evaluation of the paper.\n\n\n## Q1:\n\n\nFirst, we apologize for the typos: on line 145 (and 131) $( \\\\hat{z}_1, \\\\dots, \\\\hat{z}_j )$ should be changed to $( \\\\hat{z}_1, \\\\dots, \\\\hat{z}_k )$.\n\n\nNow, on to line 150: If we do not add noise at all, then we would set $\\\\kappa\\_j = 0$ and the $( {\\\\hat{z}}\\_1, {\\\\dots}, {\\\\hat{z}}\\_k )$ on line 145 are exactly equal to the answer of the linear queries. \nThis means that $o_j = \\\\hat{z}\\_{x\\_j} = {{(W h\\_x)}\\_{x\\_j}} + 0 = {{1_{x_j}}^T} W h_x$. \nAveraging this over $j = 1, …, n$, we get $\\\\frac{1}{n}(o_1 + \\\\dots o_n) = \\\\frac{1}{n}\\\\left(1_{x_1}^T + \\\\cdots + 1_{x_n}^T\\\\right) W h_x = h_x^T W h_x$, whereas the last inequality simply follows from the definition of normalized histogram $h_x$ (line 33).\n\n\n## Q2:\n\n\nMatrix mechanism is a standard tool in DP that dates back to (at least) the paper “Optimizing linear counting queries under differential privacy” from Li et al. in PODS'10. Given the long history of the topic, it is impossible to cover it thoroughly below; [ENU20] and references therein contains a more detailed picture.\n\n\nNevertheless, we will try to explain it here. The matrix mechanism is based on the following idea.  If the linear queries in $W$ are similar (or correlated in certain ways), it is not optimal to add independent noise to them. For example, let’s say that all linear queries in $W$ are identical. Namely, all the rows of $W$ are the same. The “trivial” algorithm here is to add independent noise to each answer. Due to (the advanced) composition of DP, this will mean that we will have to scale the noise by a factor of roughly $\\\\sqrt{k}$. Meanwhile, a much better algorithm is to compute the answer of just a single query, add noise to it, and then use this noisy value as the answer to all queries. This has the same noise as if we were to answer a single query, so we get a lot of savings by doing so! Here we can think of it as factoring $W = L \\\\cdot R$ where $L$ is the $(k \\\\times 1)$ all-one matrix and $R$ as the $(1 \\\\times k)$ matrix containing a single row of $W$. The aforementioned algorithm is thus to compute $y = R h_x + z$ where $z$ is the noise and answer $L y$. The matrix mechanism is the generalization of this, which allows arbitrary factorizations $L, R$. It turns out that $\\\\gamma_2(W)$ is exactly the error of the matrix mechanism (after some scaling) and that the optimal factorization can be done efficiently.\n\n\n## Q3:\n\n\nWe are simply using the identity $(a + b)^2 \\\\leq 2a^2 + 2b^2$ here, so there is no cross term to be taken care of.\n"}, {"review_id": "65p5QA4o5s", "reviewer": "Reviewer_YTda", "summary": "In this paper, the authors analyzed the problem of privately computing the quadratic form in the model of differential privacy, and provide non-interactive local DP algorithm with MSE upper/lower bounds with gap log(k). The paper further develops results for an interactive algorithm for the same problem and proves analogous bounds.", "questions": "1. In addition to the discussions in the paper, can the author provide some intuitions on if the upper bound of the non-interactive local DP mechanism for estimating quadratic forms should depend on k?\n\n2. Can the author provide some intuition on why the definition of $\\gamma_2(W,\\alpha)$ uses infinity norm instead of other norms? Is there any complexity results on other norms?", "limitations": "Compared to the similar sample complexity results for computing the statistical queries in the models of differential privacy, the sample complexity results for computing the pairwise statistics in local DP reveals a gap that depends on the dimension of the matrix $W$. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The bound results for both non-interactive and interactive local DP algorithms are generic. The authors provided a complete analysis on the non-interactive algorithm along with its bound results.", "weaknesses": "Compared to the linear queries result, the MSE bounds of the non-interactive local DP mechanism for estimating quadratic forms reveal a noticeable gap depending on $k$, the dimension of matrix W. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review & questions. Please find the answers to your questions below.\n\n1. This is indeed a great question and is why we also pose it as an open question in our paper (lines 344-345). We conjecture this might be necessary since even the seemingly simpler heavy-hitter problem also requires a dependency on $k$ (e.g,. [Bun et al., PODS’10]).  However, this is just an intuition since we are not aware of a formal reduction between computing heavy-hitters and computing pairwise statistics.\n\n    Furthermore, note that the original work of [ENU20] on linear queries *also contained a $\\\\log k$ gap*. (In particular, $\\\\gamma_2(W, \\\\alpha)$ is required to be at least $\\\\log k$ for the result to hold; see Theorem 22 in their arxiv version.) It is only in our paper that this gap is closed, due to a simple tweak of the proof; see Appendix B for more details. We will make sure to emphasize this point more clearly in the revision.\n\n\n2. Roughly speaking, the infinity norm is used due to the fact that we often want a worst case guarantee across all linear queries (i.e., $mMSE$ error). Recall that in the matrix mechanism we output $L(R h_x + z)$ where $z$ is the noise term. Even if the noise term $z$ is zero, our output is still $L R h_x$. Now, it turns out that we can find $h_x$ and $j$ such that the difference between $(LR h\\_x)\\_j$ (our answer for the $j$-th query) and $(W h\\_x)\\_j$ (the correct answer for the $j$-th query) is proportional to $\\\\|LR - W\\\\|\\_{\\\\infty}$. (Namely, if $(LR - W)\\_{ij}$ is the largest entry in absolute value, then we just let $x\\_1 = \\dots = x\\_n = i$.) Since our reduction uses the $mMSE$ error measure, we consider the definition of $\\\\gamma_2(W, \\\\alpha)$ as stated in the paper.\n\n    If we want some average guarantee, then it seems plausible to change the infinity norm to, e.g., the Frobenius norm. However, we are not aware of previous results on this.\n"}]

Author rebuttal:

Meta-review: This paper investigates the private computation of pairwise statistics on discrete data (a.k.a., quadratic forms). Relying on connections to linear queries, they provide lower bounds as well as general algorithms with guaranteed error bounds. Most reviewers support acceptance, praising the nice theory, the improvements compared to prior work, and the interesting connections with other private estimation problems. One reviewer voted for rejection mostly based on presentation issues, which in my opinion are rather minor and were clarified well by the authors in their response (note that the reviewer did not acknowledge the response). For these reasons, I recommend acceptance.
Decision: Accept (poster)