⁠When Data Can't Meet: Estimating Correlation Across Privacy Barriers
Authors: Abhinav Chakraborty
Arnab Auddy
T. Tony Cai
Venue: NeurIPS 2025 spotlight ()
Keywords: differential privacy; distributed data; minimax optimality
Primary area: theory
TL;DR: We study estimation correlation from bivariate data separated vertically, i.e., component-wise into two servers with privacy constraints.

Abstract: We consider the problem of estimating the correlation of two random variables $X$ and $Y$, where the pairs $(X,Y)$ are not observed together, but are instead separated co-ordinate-wise at two servers: server 1 contains all the $X$ observations, and server 2 contains the corresponding $Y$ observations. In this vertically distributed setting, we assume that each server has its own privacy constraints, owing to which they can only share suitably privatized statistics of their own component observations. We consider differing privacy budgets $(\varepsilon_1,\delta_1)$ and $(\varepsilon_2,\delta_2)$ for the two servers and determine the minimax optimal rates for correlation estimation allowing for both non-interactive and interactive mechanisms. We also provide correlation estimators that achieve these rates and further develop inference procedures, namely, confidence intervals, for the estimated correlations. Our results are characterized by an interesting rate in terms of the sample size $n$, $\varepsilon_1$, $\varepsilon_2$, which is strictly slower than the usual central privacy estimation rates. More interestingly, we find that the interactive mechanism is always better than its non-interactive counterpart whenever the two privacy budgets are different. Results from extensive numerical experiments support our theoretical findings.

When Data Can't Meet: Estimating Correlation Across Privacy Barriers
Abhinav Chakraborty Columbia University New York, NY 10027
Arnab Auddy The Ohio State University Columbus, OH 43210 arnab. auddy@columbia edu
T. Tony Cai
The Wharton School University of Peunsylvania Philadelphia, PA 19104 tcai Trai@wharton.. upenn edu
ac46628coluumia.err
Abstract
We consider the problem of estimating the correlation of two random vari- ables and Y, where the pairs (X, Y) are not observed together, but are instead separated co-ordinate-wise at two servers: server 1 contains all the observations, and server 2 contains the corresponding Y observations. In this vertically distributed setting, we assume that each server has its own privacy constraints, owing to which they can only share suitably priva- tized statistics of their own component observations. We consider differing privacy budgets (1), and (22,6)) for the two servers and determine the minimax optimal rates for correlation estimation allowing for both interactive and interactive mechanisms. We also provide correlation esti- mators that achieve these rates and further develop inference procedures, namely, confidence intervals, for the estimated correlations. Our results are characterized by interesting rate in terms of the sample size n, E1, E2. which is strictly slower than the usual central privacy estimation rates. More interestingly, we find that the interactive mechanism is always better than its non-interactive counterpart whenever the two privacy budgets are differ- ent. Results from extensive numerical experiments support theoretical findings.
Introduction
Federated learning is a popular and extensively studied framework in modern machine learn- ing. In traditional federated learning, duc to privacy concerns, the servers are not allowed to pool raw data, but are restricted to sharing only sufficiently privatized statistics derived from the local observations. This method is particularly beneficial when training on scnsitive data, such healthcare finance. The federated scenario is very systematically studied when the separation occurs horizontally, i.e. observations of the same set of features are binned separately into different servers. See, for example, Kairouz et. al. [2021], Li et al. [2020a,b], Zhang et al. [2021] and the references therein.
To encourage collaboration on proprictary data across different organizations, however, it is often more reasonable to assume that the federation occurs "vertically", or across foatures. For example, in healthcare data, hospital and a pharmaceutical company might have different pieces of information on the same patient: the hospital does not share private clinical information such as patient demographics instead has its own private information on the same patient's 's response to certain drugs. This new framework called vertical federated learning has recently seen studied in Chen [2020], Liu et al. [2024], Wu et al. [2020], Wei et al. [2022]. Yang et al. [2019], but a theoretical understanding of estimation and inference has largely been missing. This motivates the current work. We study the correlation of bivariate data from pairs of samples (X,, Y,)
test results with the company, which
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

which are not observed together, but are instead separated into two servers as (X; n and {Y; :i:1st n).
To distinguish our results from the influence of estimating the marginal distributions of X and Y, we assume that E(X) = B(Y) = O and Var(X) Var(Y) = 1, and (X,Y) are sub-Gaussian. That is, we assume that our data are pre-normalized to have mean zero and variance one. We revisit the question of normalization in the supplementary material and show both theoretically and in numerical experiments that the rate of correlation estimation is not influenced by this step. In this situation, we consider estimating = B(XY) from the statistics shared by the two servers: viz., Server 1 releases (X X,). and Server releases Ty.Y...... Yn). ). To protect user privacy, we impose the differential privacy framework (sec, e.g., Abowd et al. [2020], Bassily et al. [2014], Dwork [2006], Karwa and Vadhan [2017]) on Ti and T2; both of which must satisfy (f1, 61) and (f2, 52)-DP constraints. For case of reference, we will somewhat looscly denote the above by a server-level (21,E2, E2, 51, 62) constraint and introduce specific definitions later. Such distributed privacy requirements are frequently used in federated learning. See, e.g., Auddy al. [2024], Cai et al. [2024a Shen et al. [2022], Wei et al. [2020, 2021] and references therein.
1.1 Main results
The key finding in this work is that the complexity of the correlation estimation in the above setup fundamentally depends on whether or not the statistics Ti and T2 are allowed to depend on one another. We now present our main results. Throughout this paper, we assume ε 82 < C for constant C >>0 0.
1.1.1 Non-interactive protocol
In our first set of results, we consider estimating p in the non-interactive (NI) framework of stricter privacy requirements, where Ti and T222 are constructed independently, i.e., with- out any interaction or information about one another. In this case, the diffcrential privacy requirements on Ti and T2 are follows. With X (XI...., Xn), Y (Yi...., Yn), and similarly X', Y' (with one data point replaced):
(X))(X) E A & PY) E A\Y) S exp(e))P(I5(Y") E A|Y") + 82.
E ) - 51
Let NI(=1,62, 01,82) to be the class of all correlation estimators constructed using Ti (X) and TY(Y) satisfying the above privacy requirement. The following theorem states the minimax rate for estimating P in this scenario.
Thcorem 1.1. The minimar rate for estimating correlation p via a non-interactive proce- dure satisfying server level (e1, 62, ò1, DDP constraints is given by
inf Pe Ni(es,22, 82) pE|-1,1]
sup
E (p - p)² x Lu
net
n
for factor Ln of order at most O(log(n)), whenever 81,52 = oln
Note that the rale does not depend on 0's. This implies that our rate matching correlation estimator achieves E2,, O, O)-DP, and is still rate optimal (up to logarithmic terms) even within NI(E1, E2, 51, 62), the class of all non-interactive estimators satisfying (E1, and (E2, 62) DP constraints for 8,, are small positive numbers. The rate optimal estimator in this case is given by the correlation of privatized batch means from both servers.
It is useful to compare the above rate with the ones existing in the literature. Firstly, when (X.Y) are jointly observed, and we impose (e, (e.8)-central DP constraints on (X,, Y2), the optimal correlation estimation rate is given by w-z.- See, e.g., Biswas et al. [2020). Cai et al. [2021]. As expected, when 61 = 82 E, this is betler than the rate we observe feature separated case, thus highlighting the cost of vertical federation. A second comparison can be made with component-wii
the current.
local privacy rates, studied in Amorino and Gloter [2023). The authors there show that in the vertically separated scenario, if we impose (E1,0) and (E2, 0) local DP constraints, the minimax estimation rate for correlation is given by लहदद which is again strictly worse than the rates we find under the server level DP constraints.
2

---

1.1.2 Interactive protocol
We next move to larger class of estimators in the interactive (INT) framework, where we still require server level privacy, but onc of the servers allowed access to the privatized statistic output from the other. In other words, allow the functions T₁ and T2 to have one way interaction with each other. This requires making exactly one out of two possible choices. The first possibility is that when constructing T2, Server 2 has access to Ti (X),, in addition to its own data Y. The second possibility arises by analogously interchanging the roles of servers 1 and 2. To fix ideas, if the transcript Ti, before computing T2, the privacy requirements become:
in the first case, i.e server 2 gets observe
(X))(X) E X I exp(e:) E AAX') 51
(YT2(Y,TIXX) E A) & (xp
E +
Replacing X with Y and the index with 2 allows one to write the analogous privacy constraint in the second case where Server has access to T2(Y). Let (NT 51 62) to be the class of all correlation estimators constructed using Ti (X) and T2(Y, Ti (X)) satisfying the above interactive privacy roquirement. The following theorem states the minimax rate for estimating p in this scenario.
Theorem 1.2. The minimax rule for eslimating correlation p via a non-inleraclive proce- dure salisfying server level (21, d1, 62) constraints is given by
( - p)² In ( 12 .2) pEl-1,11
inf
sup
((E) n² /
for factor Ln of order at most (log(n))), whenever 81, = o
Note that unlike NI, the INT ratc, the dominating term depends on E1 V E2, i.c. the less stringent privacy requirement. The stronger privacy requirement i.c., A E appears in the second term, but its effect is mitigated by the better sample size factor n This leads to INT being a strictly better estimator than NI whenever * E2. An interesting special case when X are public, meaning E1 is a constant, which case we find (e2, 52) rcentral DP rates for correlation estimation.
The rate optimal estimator in the interactive with a less stringent privacy budget should share their statistics with the other server. That is, if e > S2, we should allow T2 depend on Ti (X) and Y. The situation is reversed if 82 > E1
is borne out of a natural idea: the server
In addition to point estimates م. we also derive asymptotically valid confidence intervals in both the non-interactive (NT) and interactive (INT) scenarios. That is, we find (P(NT) (NN))
and (NNT) ((NT)) such that for fixed (0,1)
(k) (P Sp
(k) Pú,n) + +1--0 a as n + 00, for (NI,
We show that our estimation methods are minimax optimal by proving corresponding lower bounds, which to the best of our knowledge, has not been established previously under central differential privacy in vertically distributed setting. While we follow the classical Le Cam framework, our main tochnical contribution is direct control of KL divergence via Fisher information curvature bounds, yielding sharp lower bounds under both non- interactive and one-way interactive protocols. These bounds match our upper bounds up to constants in the Gaussian case and up to logarithmic factors in the sub- Gab--aassian case. Prior works, such as Hadar et al. [2019]. bound KL via mutual information in communication constraint settings;
take more direct route tailored to central DP. Unlike local DP lower bounds in Amorino and Gloter [2023], our approach handles the more delicate structure of central privacy with vertical data splitting.
The rest of the paper is organized as follows. In Sections 2 and 3 respectively, we describe non-interactive and interactive correlation estimators for bivariate Gaussian and bivariate sub-Gaussian distributions. Section provides minimax lower bounds showing that our estimation procedures are nearly optimal in all cases. Finally, Section 5 shows numerical experiments to corroborate our theoretical results. All proofs are in the supplementary material.
3

---

Non-interactive estimation methods
We first demonstrate an estimation procedure in the pon-interactive paradigm. Here Server 1 and Server 2 construct and share (X) and (x(X) without knowledge of one another. As mentioned in the introduction (X) must satisfy (E1, and (x) must satisfy (E2, 62)-DP constraints. Our estimator is based on sharing privatized batch means. Choosing
m 2 we separate the n observations in each server into batches size m as follows:
Bj = {m(j - 1) + ,....,mj].. for j= i=,,....k where = L
(1)
2.1 Non-interactive correlation estimation for Gaussian distribution
In this subsection, assuine that (X,Y) (o M())) with (E(p)) (2(p))22 = and (E(p)) = p. the bivariate Gaussian distribution with E(X) = (E()) - O, Var(X) = Var(Y) = and correlation B(XY)
Our estimation procedure for p is through the product of sample means across multiple batches. In order to bound the sensitivity directly, ie., without clipping, we will use the signs of X2 and Y place (X,, Vi) themselves, to compute our correlation estimator.
X
Σ m iEB
1
sign(X;), and y m VE
Σ sign
(2)
where B, are as definod in (1) for j I....,k. To ensure (EDP and (E2, D)- constraints each server adds Laplace noise to each batch mean and outputs the vectors (x),, E R with elements:
(T(())) vm(x)) )(n) and (T2(Y)) vm((b) 2 for 1 isisk k where z(1)
indep Laplace (o, mer) for 1 1= 1,2. We then compute
1 (T)))))
7XY h
(3)
Since (X, Y) are bivariate Gaussians, the covariance above satisfies
Eixxr 2P 0) 2 arccos(p)
(4)
which leads to the ffrhoddoffmomentt based private correlation estimator:
(P)
(G) == cos (1- = sin
TIIY
We would like to emphasize that (4) is preciscly where we use the assumption of Gaussianity on Y). Since the bivariate distribution is completely known once p specified, we can explicitly write P(XY > 0) as function of p, which in turn enables our sign-based estimation procedure. While this can be extended other bivariate families which are specified by single correlation parameter p, we do not discuss these details for brevity.
To create confidence intervals for P, let define S to be the sample variance of ((I)())))(22()); 1ijjs k... Then we can define the confidence interval:
(G) (C) (a) == PNI
xS,,
2Vb
G 21 21-0/2: PNI
(NT
(G) xS., 1-.VI-GAT 2Vb
21
21-a/2
(5)
where 21-a/2 is the (1 22 quantile of the standard Normal distribution.
2.2 Non-interactive correlation estimation for sub-Gaussian distributions
In general, we would deal with non- non-Gassiaa data, and thus the sign-based procedure of the previous section would not. be exact anymore. We will use clipping based estimator for this case. For clipping parameters X1, X2 > 0 to be chosen later we replace (2) by
g = 1 Σ sign(()) V A1) and 80- 1 Σ
(6)
B

---

where B, are as defined in (1) for j = 1....,k. As before, each server adds Laplace noise to each batch mean and shares:
=
= and (I2(Y)); - + + for 1 k,
where 2,0) indep Laplace (0,
2
for = 1,2. Then we will estimate by the quantity:
h (T(()))
(SG)
(7)
j=1
Once again defining Sg to be the sample variance of ((T(())) :1 s $ k), have the confidence interval:
(SC) (a) := PNI VI:
(SG)
Sp
(SG) Sp
2 PNI
21-0/2
(8)
vk
where 21-a/2 is the (1 (1-a/2)-th quantile of the standard Normal distribution. The following theorem states the results for correlation estimator under non-interactive protocol. Theorem 2.1. The sollowing resulls hold on the eslimation error of p using non- interactive componentuise privacy constrained estimator.
1. When (X,Y) NOO, E(p)) with (E(p)) (E(())22 and (E(p))12 p, the estimator (G) described in Section 2.1 satisfies PNi E E2, 8,, 52) and
B(PN 0)² x
1 82
is
8 V1.
7
E192
2. When Y) have mean zero, variance one, X is 111 Saub-Gasssia, Y is 72-8ub- Gaussian, and B[XY] = p, the estimator (SG) described Section 2.2 satisfies <(SG) NI((E,, 81, 62) and PNI
(SG) E(PNI pp) <
log(n)
1 S2
X A2
m
n
5152
A1 2m log(n) and X2 = 21p2 2 log(n).
3. For any flxed a E (0, 1), the confidence intervals defined in (5) and (8) satisfy
Ppp E (T( + - as + 0o, for k E (G)
Interactive estimation methods
We now show that the rates in the previous section be improved if we allow one-step interactive scheme between the two servers. To fix ideas, suppose E > E2, ie., the privacy requirement in the first server are less stringent than that in the second one. We will then share the private transcripts involving X to the second server containing the Y observations. This leads to estimation error rate that improves over the non-intcractive protocol.
3.1 Interactive correlation estimation for Gaussian distribution
In this case, our interactive estimator based on signs of (X, Y) is as follows. Server 1 first. communicates Server 2 the privatized sign vector Ti (X() with elements:
exp($1) +1 (2S, 1) (X,) for 1......,7 (Ti (X))))) = (exp(e1) - 1]
exp(e1) exp(r1)+1 are independent sign flips introduced by Server 1 to protect the privacy of X,. Given 7, the second server first computes the covariance
where S: did Bernoulli
a (T (X)); sYgn(Y.)
n
5

---

and then outputs the privatized version
2(exp(e1) +
T2 (2(Y, = ii + Z
where Z Laplace
(9)
n(exp((1)) 1)52
As before we then have the private correlation estimator
GG)
sin XY
PINT
Similar to the non-interactive case, defining o := confidence interval given by the following.
(xple))=1 exp(s1)+1
(P) (Txx allows the
1. If limn-too Vnone2 is finite, then the CI is
2
PINT
2vn
(PNT)
exp(e:)+1
exp(51)
Fr FT - aa/2)a2)))))
(10)
where for any a E R we define F.(x) = P(Zxx + + Map 2x) for To = 2/ n2) and Zapp Laplace(O,1).
diverges as + then the CI is 2. If vieg
VI (exple))+1 expler)-1) log(a)
PINT
(11)
3.2 Interactive correlation estimation for sub-Gaussing distributions
Following previous sections, Server will send to Server 2 the vector of privatized clipped observations Ti (XX) Rd with elements (Ti(X)); [X,]A, + Zii for clipping parameter
iid Laplace (2\1/E1) for i I,...,m.. Then Server 2 can construct A 0 and Z
"
(SG) PINT
(T)()) + 222.
In the above [z]; == sign(z)((z)AA for any E R and >> 0. Here Zn ~ Laplace (2A2/ns3) is Laplace noise added to ensure DP requirements. In addition to PINT Server also outputs a privatized sample variance 5 of [(T (X)), Yi)a, for 1,..., n. Then we have the confidence interval constructed as follows:
2h2 is finite, then the CI is 1. If lim Vnd,e2
(SG) Sp F. (1- (1-x/2), Pint
Sp F.- 1. - (a/2)) Vn
PiNT
(SG)
(12)
Vn
where for any I E R we define F.(x) = P(Zxy + C. ZLPp S x) for C, = 2)2/(V)S,e2), and Zaap Laplaco(O, 1).
2. If d diverges oc, then the CI is Vnez
(SG)
A log(a),, Pint
(SG) X2
log(a))
(13)
nE2
ne2
The following theorem states the results for correlation estimator under the interactive protocol.
Theorem 3.1. The following results hold on the estimation error of p using the above privacy constrained interactive estimator.
1. When (X,V) Y) ~ N(O, E(p)) with (E(p)) = (E(p)) = and (E(p))12 = the
AG) eslimalor PINT described in Seclion 3.1 salisfies PiNT E &2, and
-G))
1
1
B 2) n(si V
n²

---

2. When (X,Y) have mean zero, variance one, X is 7h "T----ub---an Gaussian, Y is 72-sub- Gaussion, and E|XY] = p, the estimator PINT described Section 3.2 satisfies ASG)
(SG)
PiNT' 01 82) and
B(PINT p)² 2
1 n(e V
n2
if \1 =2m1 llgi)) and X2 4(m v (loo((n)))/(E1 A1)
3. For any fixed a E (0, 1), under their respective assumptions, the confidence intervals defined in (10), (11), (12), and (13) satisfy P(p E C(NNT(a)) + as + 20, for l E (G,SG).
Minimax lower bounds
In this section, we show that the privale correlation estimators derived in the previous section are fact minimax optimal in many cases. Our proof stralegy is based on bounding Fisher information of the private transcripts and then using Van Trees inequality. We recall some standard results from parameter estimation theory in the next subsection.
4.1 Fisher information and Van Trees inequality
Let 0 be real-valued parameter taking unknown value in some interval [a, b]. We observe some random variable (or vector) X with distribution P(x(0) paramctorized by 8.
Assume that (()10) is absolutely continuous with respect to a reference mcasure μ, for each 0 E [a, and 4P((10) (x) is differentiable with respect to 0 E (a, 6) for p-almost all Then the Fisher information of w.r.t. X, denoted as IF(X; 0), is defined as
du
(x( (
00 In dPP(10)
2
(x) dP(x1().
(14)
du
The following inequality is well-known. See for example Gill and Levit [1995].
Lemma (Van Trees inequality). Let 0 be a real parameter with prior density ( supported
on Ja, b] C R, and let X ~ P(( 0) with conditional density p(z 0) dP(. (x). Under
some regularily condilions we have that for every eslimator ① = 0(X) with E[(O 0)3) < oo under the joint law of (X,0) ()0) salisfies
E O 0321 2 Es [x(T)( IF(())
[x:4)(X;0)] - 1r(X;0) do, (15)
where IF(() = S (c(00)) d0 is the prior Fisher information. (())
ensure that one can apply the dominated convergence theorem to exchange certain integrals and differentiations in the calculus. See for example Vaart [1998]. Additionally, assume that
The "regularity conditions" in Lemma
[x 0 + c) Ir(X;0) n())
(16)
where T7(e) C, for all |e| < co for some numerical constants co < 1 and C, >
4.2 Non interactive
For the non-interactive protocols the servers output transcripts Ti and Th which (#1, 61) and (E2, 8DP respectively. The transcripts are based on,y on the data from their own servers. An estimator is then calculated after combining Ti and T2.
Our lower bound shown by the difficulty of correlation estimation when p= Let us denote the transcripts by T (Ti, As first step, the next lemma shows that (T( 0) smaller than a quantity involving the sample size n and the privacy parameters E 82. Lemma 2. Assume that for k = 1,2 òg log(1/5k) O Let us denote the Fisher information for the transcripts T by (T); We have that
8 I (T: < (net A nE²).
π

---

The local regularity assumption in (16) at = 0 ensures that up to constant factor, the bound from the above lemma carries over to I (T: for løl I cp. For suitable choice of prior density Ç this in turn implies an upper bound on Eo [o 0)] and allows us to complete the proof by using Van-Trees inequality (Lemma 1). We then have the following lower bound on the minimax risk for estimating p in the non-interactive setting.
Theorem 4.1. Assume that o₂ = o(n oln) for k = 1,2 and n(e A + xc. Then for non interactive protocols the minimax rate is lower bounded by
1
1
inf PeN .2) pEl
sup 1 p
n
nei
ne
Remark 4.1. The assumption n( A E3) ) + do assumes that the minimar rate is going to zero ensuring consistent estimation of p in the first place.
4.3 Interactive
We next allow one way interaction among the servers where either the server can share its transcripts with the other server. Let us denote the set of protocols which allow allow interaction from server to 2 as 111-2, ie server gets to observe the transcript Ti, before computing T2. We first show the following upper bound
Iy (TI-+;;
Lemma 3. Assume that 61 log(1/6)) = olE)) and 82 log(1/02) = o(nefE)). Let us denote the Fisher information for the transcripts I_ by ( We have that
(F(11122;0) 0) nst A e7e3
If we denote the protocol which allow interaction from server 2 1 can show that (TT[-211;0) S nez A n22e Since we allow for either of the protocols IT = (T1--2, 22--1) have that
[II[::) < (II-2: (II2-11:0) S (nEî A n²=efE)) V (n= A n=eeE=))
(17)
Similar to the non-interactive case and a suitable prior density Ç with Van Trees inequality, leading to the following lower bound on the minimax risk in the interactive setting.
then use the local regularity assumption in (16)
Theorem 4.2. Assume that for k = 1,2 ōş = o(n o(n-1-w for w > O, n(E? V =²] + oo and n²=fez + co. Then for interactive protocols the minimaz rate is lower bounded by
1
inf pe Ag) pE(-
sup م pl n
n(E
n²=jE3
Remark 4.2. The assumption n(e? v +2) + ca and n²eeet
2 + assumes that the minimar rate going zero, ensuring consistent estimation of p the first place.
Numerical experiments
We evaluate our non-interen con-interactive sign-batch (NI) and interactive sign-flip (INT) estimators across different parameter settings. All our codes can be found at https: Sotted-correlaton
github. com/
5.1 Simulation experiments
In our experiments we write non-normalized mean that the mean and variances of the marginal distributions are known, and normalized to mean that they are unknown and estimated. We use two generative models.
Gaussian: (X,Y) ~ (N(,,, 2E())) with μ = 0.5), and Σ(p) given by Var(X) = Var(Y) and Corr (X, = p. We run each estimator with and without the private normalization step.
Bounded-factor (sub-Gaussian): = U y= U E2 with U Unif[-v3pp /3pl and E, Unif - / 3(1 p), / 3/11 - p)); so cach marginal is con- tred, variance-one, and bounded honce sub-Gaussian
For every design point we record mean-squared error (MSE), average iafidence-intervll (CT) length, empirical coverage (1 - a = 0.95) and the mean CI ofīset band E,C,, - p] E(Cb - p] where Cl, and Clu are the upper and lower confidence bars. In practice it is suf- ficient use the confidence intervals from (10) and (12) since (11) and (13) are respectively the limiting versions of the above two.
8

---

Parameter Grid. We vary our parameters as below, with 250 replications for each cell:
Sample size: E (1000, 1500, 2500, 4000, 6000, 9000).
Correlation: / {0, 0.15, 0.3, 0.4, 0.5, 0.66, 0.8,
Privacy budget: ($1, 62) E {00.5, 0.5), (1, (1.5, 0.5))
Mean CI offeet bands -n 1500, & 1.5, 6 =.5
Mean CI offeet bands -n 1500, = & 0.5
0.3
meanici)
0.0
-46
Figure 1: Gaussian, 1500, (2) = (1.5, 0.5). Mean CI-offset bands for NI (grey) and INT (blue). Left: without normalization. Right: with private normalization. Curves overlap.
Figure 1 compares the mean CI offset bands for n = 1500 and the budget (E1, = (1.5, 0.5). With and without normalization the ribbons coincide, indicating that private normalization is cost-free. Figure shows CT width and coverage versus n at 0.5; both variants adhere to the nominal 95% band. Figure confirms that INT is uniformly more efficient than NI, while normalization leaves MSE unchanged (largest relative difference <2%).
Average CI width vs (p 0.5))
Average CI width vs (050.5)
(e,
Average CI length
2.0
05.05
Average CI length
1.0
05.05
15.0.
1,1
1,1
0.5
Method
0.5
Method
1000
3000
20000
1000
3000
10000
(log-scale)
(log-scale)
Figure 2: Gaussian, p 0.5. Average CI length versus n. Left: no normalization; right: with normalization. Normalization has no discernible effect; INT yiclds shorter Cls. The coverage probabilitics are above 0.91 for all Cls.
MSE of 0 vs n (p = 0.5)
MSE of 6 vs n (p = 0.5)
0.000
1.00
(0)+g)
MSE (log-scale)
MSE (ogles
05..5
15,05
15.05
0.10
0.10
Method NI
Method
0.001
1000
3000
10000
5000 n (log-sclle)
10000
(log-scale)
Figure 3: Gaussian (left) and Bounded Factor (right) MSE, p 0.5. MSE versus n (log log). INT dominates NI
We repeat. the study with the bounded-factor DGP. The qualitative picture the same: INT enjoys narrower Cls and lower MSE, and both estimators achieve nominal coverage.

---

Non-interactive
Interac tive
mean(CI) for
mean(CI) for
0.0
0.0
-0.5
-0.5
0.5
1.0
1.5
2.0
2.5
0.5
1.5
2.0
Ecor
Ecom
Figure 4: Mean confidence interval bands for non-interactive (left) and interactive (right) methods for estimating the correlation between age and BMI in the Health and Retirement Study (HRS) data. The black dotted line indicates the non non-private estimator.
For the sake brevity we only show the MSE plots (Figure right). The CI bands, coverage and width plots are deferred to the supplementary material.
5.2 Real data experiments
We illustrate our methods using data from the Health and Relirement Study (HRS), a longi- tudinal survey of older adults in the United States. We focus two variables age and body mass index (BMI) from Wave (year 1993-94) corresponding to around 20k individuals. In this demographic, age and BMI are known to exhibit mild negative correlation.
We consider a distributed scenario which the two variables reside on separate servers, and the goal is to estimate their Pearson correlation cocfficient, p. Each server first applics Central differentially private (CDP) normalization so that the privatized fcatures have approximately zero mean and unit variance. Specifically, allocate & = 0.1 for each of the mean and standard deviation estimmates. The clipping bounds are chosen based on domain knowledge-Ho [45, 90] for age and [15, 35) for BMI demonstrating a setting where the privacy mechanism leverages prior information rather than data-dependent thresholds.
After normalization, we apply both the non-interactive (NI) and interactive (INT) protocols to obtain private confidence intervals for the estimated correlation p. We compare these to the non-private benchmark while varying the privacy budget Ccorr koeping it equal across the two servers. Results are given Figure As Ecorr increases, the private intervals contract and concentrate around the non-private Morcover, for fixed Ecorr, the INT intervals are consistently shorter than their NI counterparts. Notably, at Ecorr 1, the interactive CI excludes wero while the non-interactive CI includes it illustrating that privacy noise can increase uncertainty and, in some cases, prevent. rejection of the null hypothesis p = O.
Discussion
Across both distributions and all privacy budgets explored, INT consistently outperforms NI, while the required private normalization step incurs no measurable loss in bias, MSE or interval width. These findings support the theoretical claim that normalization's privacy cost is dominated by the subsequent correlation release.
We discuss two important directions of future work. First, allowing multiple features per server rather than single feature introduces new challenges, particularly in handling inter-feature correlations and maintaining privacy in higher dimensions. Second, extending our methods to heavy-tailed distributions would broaden applicability, as such data often arise in practice and require more robust estimation techniques.
A Acknowleegemmenss
The research was supported in part by NSF grant NSF DMS-2413106 and NIH grants R01- GM123050 and R01-GM129781.
10

---

References
John M Abowd, Tan M Rodriguez, William N Sexton, Phyllis E Singer, and Lars Vilhuber. The modernization statistical disclosure limitation at the us census bureau. US Census Bureau, 2020.
Chiara Amorino and Arnaud Gloter. Minimax rate for multivariate data under componen- twise local disferential privacy constraints. orXiv preprint arXiv:2305.1000 10416, 2023.
Arnab Auddy, T Tony Cai, and Abhinav Chakraborty. Minimax and adaptive transfer learning for nonparametric classification under distributed differential privacy constraints. arXiv preprint ar 20088, 2024.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464-473. IEEE, 2014.
Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Newral Information Processing Systems, 33:14473-14485, 2020.
T Tony Cai, Yichen Wang, and Linjun Zhang, The cost of privacy: Optimal rates of con- vergence for parameter estimation with differential privacy. The Annals of Statistics, 49 (5):2825 2850, 2021.
T Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. Federated nonparametrie hypoth- osis testing with differential privacy constraints: Optimal rates and adaptive tests. arXiv preprint orv:v22406. 06749, 2024a.
T Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. Optimal federated learning for nonparametric regression with heterogeneons distributed differential privacy constraints. arXiv preprint 066.0655,, 2024b.
Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. Optimal federated learning for functional mean estimation under heterogeneous privacy constraints. arXiv preprint arXiv:2412. 11.1899,,, 18992, 2024c.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. Vafl: a method of vertical asynchronous federated learning. arXiv preprint :xXt::2007.06081, 2020.
Cynthia Dwork. Differential privacy. In International colloquium on aulomala, languoges, and programming, pages 1-12. Springer, 2006.
Richard D Gill and Boris Y Levit. Applications of the van trees inequality: a bayesian cramér-rao bound. Bernoulli, pages 59 79, 1995.
Uri Hadar, Jingbo Liu, Yury Polyanskiy, and Ofer Shayevitz. Communiattion complexity of estimating correlations. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 192-803, 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachol Cum- mings, et al. Advances and open problems in federated lcarning. Foundations and trends@ in machine learning, 14(1-2):1-210, 2021.
Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint 1:1.::1111.00000 2017.
Li Li, Yuxi Fan, Mike Tse, and Kuo-Yi Lin. review of applications in federated learning. Computers & Industrial Engineering, 149:106854, 2020a.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEFE signal processing magazine, 37(3):50- 60, 2020b.
11

---

Yang Liu, Yan Kang, Tianyuan Zou, Yanhong Pu, Yuanqin He, Xiaozhou Ye, Ye Ouyang, Ya-Qu fa-Qin Zhang, and Qiang Yang. Vertical federated learning: Concepts, advances, and challenges. IEFE Transactions on Knowledge and Dala Engineering, 36(7):3615-36))) -634,, 2024.
Sheng Shen, Tianqing Zhu, Di Wu, Wei Wang, and Wanlei Zhou. From distributed machine learning to federated learning: In the view of data privacy and security. Concurrency and Computation: Practice and Experience, 34(16)xe5002, 2022.
Alexandre B. Tsybakov. Introduction to nonporametric estimation. Springer series in statis- lies. Springer, New York; London, 2009. ISBN 978-0-387-79051--0 978-0-387-79052-7.
OCLC: oen300399256.
A. W. van der Vaart. Asymptotic statistics. Cambridge scries in statistical and probabilistic mathematics. Cambridge University Press, Cambridge, UK ; New York, NY, USA, 1998. ISBN 978-0-521-49603-2
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensies and securily, 15:3454 3469, 2020.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Hang Su, Bo Zhang, and H Vincent Poor. User- level privacy-proserving federated learning: Analysis and performance optimization. IEEE Transactions on Mobile Compuling, 21(9):3388 3401, 2021.
Kang Wei, Jun Li, Chuan Ma, Ming Ding, Sha Wei, Fan Wu, Guihai Chen, and Thilina Ran- baduge. Vertical federated learning: Challenges, methodologies and experiments. arXiv preprint arxi:2200 04309, 2022.
Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen, and Beng Chin Ooi. Pri- vacy preserving vertical federated learning for tree-based models. arXin preprint arXio:2008. 061700, 2020.
Shengwen Yang, Bing Ren, Xuhui Zhou, and Liping Liu. Parallel distributed logistic gression for vertical federated learning without third-party coordinator. arXiv preprint arXiv:1911.005: 2019.
Chen Zhang, Yu Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. A survey on federated learning. Knowledge
-aaseedge-Bosed Based Systems, 216:106775, 2021.
12

---

NeurIPS Paper Checklist
The checklist designed to encourage best practices for responsible machine learning re- search, addressing issues of reproducibility, transparency, rescarch ethics, and societal im- pact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction clearly articulate the main contribu- tions of the paper, including the problem setup, the proposed methodology, and the theoretical guarantees. They accurately reflect the scope of the work and are consis- tent with the results presented in both the theoretical analysis and the simulation study, Any assumptions and limitations are also stated appropriately, ensuring that the claims are well-aligned with the actual contributions of the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, in- cluding the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it clear that these goals are not attained by the paper.
2. Limitations
Docs the paper discuss the limitations of the work performed by the authors?
Question:
Answer: [Yes]
Justification: Limitations and future directions are described in the Discussion sec- tion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noise- less settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on a fow datascts with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly
13

---

when image resolution is low or images are taken in low lighting, Or speech- to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algo- rithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The au- thors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Answer: [Yes]
The paper provides a complete and rigorous treatment of each the- oretical result, with all necessary assumptions clearly stated alongside the corre- sponding theorems. Full proofs are included in the supplemental material, and the main paper provides intuitive explanations aid understanding. All theorems and lemmas are properly numbered, referenced, and supported by either original argu- ments or citations well-cstablished results, ensuring the thcorctical contributions are transparent and verifiable.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-reeerenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be com- plemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided all experiment details in Section and codes in anonymized code repository.
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might, suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results way to reproduce the model (e-g., with an open-source dalaset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source modcls, it may be that access to the model is limited in some way (e.g,, to registered users), but it should be possible for other researchers to have some path reproducing or verifying the results.
5. Open access data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided all codes in an anonymized code repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https:/ //nips. for more details.
cc/publick Btapliic/guides//oodeeee guw.teee/Cddsuumsssssooooooo.eee
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submis- sion guidelines httt::////aa..cc//bbb//e///eeee httppp/ale//piieeee//eeeesaaasaa for more details.
15

---

The authors should provide instructions on data access and preparation, in- cluding how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and basclines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is per- mitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to un- derstand the results?
Question:
Answer: [Yes]
Justification:
All details are given in Section 5 and the anonymous code repository.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as sup- plemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We have reported 95% confidence intervals with all our estimates.
Guidelines:
The answer NA mcans that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The mothod for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the stan- dard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CT, if the hypothesis of Normality of errors is not verified.
16

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sulficient information on the computer resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Answer: [Yes]
Justification: All experiments were done on a desktop with 32 GB RAM, and were done over the course of hour.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more com- pute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Docs the rescarch conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics sttps://neurips.. http:///wwrpppp.cpppiiieee/e/ee/ https//ee/eeeetttieeeeeellllllll
Answer:
[Yes]
Justification:
There violations of the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws regulations in their jurisdiction.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and neg- ative societal impacts of the work performed?
Answer: [NA]
Justification:
There is societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has socictal impact or why the paper does not address socictal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness con- siderations (e.g., deployment of technologies that could make decisions that
17

---

unfairly impact specific groups), privacy considerations, and security consider- ations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement of generative models could be used to generate deepfakes for disinformation. On the other hand, it not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
the quality
The authors should consider possible harms that could arise when the technol- ogy being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in ad- dition attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe saleguards that have been put place for re- sponsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datascts that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective saleguards is challenging, and many pa- pers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
18

---

The name of the license (e.g. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
the package should be provided. For popular datasets, paperswithcode.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the doc- umentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Rescarchers should communicate the details of the datasot /code/modcl /oodel as part of their submissions via structured templates. This includes details about train- ing, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question:
For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshols, if applicable, well as details about compensation (if any)?
Answer: [NA]
The paper does not involve crowdsourcing nor research with human subjects.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (TRB) approvals (or an equivalent approval poprovalrreviewww /review based on the requirements of your country institution) were obtained?
19

---

Answer: [NA]
The paper does not involve crowdsourcing research with human subjects.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between insti- tutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, orig- inal, or non-standard component the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This research has not used LLM as an important, original, or non- standard component of the core methods.
Guidelines:
The answer NA means that the core method development this research does not involve LLMS any important, original, non-standard components.
Please refer our LLM policy (https: https///eerrss.ee/eeeeee scc/Conferennce/2225, LLM) for what should or should not be described.
20

---

A Implementation details
Since the mean and variance of each server can be computed under the central differential privacy (CDP) framework, we adopt estimators similar to those proposed in Karwa and Vadhan [2017] for our simulation study. After obtaining these estimators, we standardize the data and use the resulting values for downstream analysis.
Additionally, to improve the stability of our estimators, incorporate intermediate clipping steps in our simulation study. For example, in the Gaussian case, we clip the mean the signs to the interval [-1,1] before applying the sin transformation. In the sub-Gaussian case, we clip the final cstimator to [-1,1]-
A.1 Additional simulation study
Here we collect the additional plots and results pertaining to simulation study.
MSE of Qs n (p= = 0.5)
0.100
[6,55)
MSE (log-scale)
0.5.0.
155.0.
0.010
Method
INT
0.001
1000
3000
10000
(log -og-sc
Figure 5: Gaussian Normalized MSE, p = 0.5. MSE versus n (log-log).
Mean CI offset bands =6000, & 1.5, 0.5
0.5
meancii) -p
0.0
Estimator
INT
-05
0.5
Figure 6: Bactoe,,factor, n 6000, (21, (1.5, 0.5). Mean Cl offset bands for N1 and INT.
B Proofs
Proof of Theorem 1.1. The proof of this theorem follows from parts and of Theorem 2.1 and Theorem 4.1.
Proof of Theorem 1.2, The proof of this theorem follows from parts 1 and of Theorem 3.1 and Theorem 4.2.
21

---

Average CI width Vs (p = 0.5)
Coverage vs (p=0..) 0.5)
16,45]
(6)5))
Average C1 length
1.5
D.5.0.5
Empirical coverage
0.96
05.5
1,5,0.5
1.5.5
1.0
Method
Method
0.3
NI
0.92
N
3000
5000
10000
3000
5000
10000
(log-scale
(log-scalle
Figure 7: Bounded-factor, 0.5. Cl length (left) and coverage (right) versus
Coverage ip- 0.5)
Coverage 0.5)
(2.4)
Emparcal couraee
05.5
1.8.5
15535
0.39
Nothod
Method
0.32
608
1330
3233
10000
1000
10002
n.00g-scolel scole!
100 scalo)
Figure 8: Gaussian, م 0.5. Empirical coverage versus n. Left: normalisation; right: with normalisation. Normalisation has no discernible effect; INT yields shorter Cls. The coverage probabilitics are above 0.91 for all Cls.
B.1 Proofs of upper bound results
Proof of Theorem 2.1. We prove the two statements the theorem separately.
1. It is straightforward to check that
= m ( (F())) Elixx] mB] mlR[ (1)
Elsign (x)) sign
m
2PX 1 2 aarcoos 1=1 2 (acccos(p)
To bound the error in estimating by P)P) we therefore note that
(G) PNi
pl sin 2 sin
2
cos(E) π
E(ūxy]
< 11x
(P)
-E
(18)
where { = -ijjxy (1 [)x[áx]] for some E [0, 1].
Thus,
E EP
- -
El 1 1/2
Var - -[(xx]]
4
4
m2
((X(()) + +Z(2
y
B( + 225))111
4h
2 m
2
3
8
3
8
+
4k
m
m²
m
m²
3
9m
24
24
64
(19)
71
n
neT
m
n
24
24
80
10
4
nEt
ME1E2
E2
22

---

In the penultimate equality, we use the choice m 8 which minimizes the expression in the previous line. The privacy constraints are satisfied by the Laplace mechanism and checking the sensitivity of the batch mcans.
2. It is straightforward to check that
BIPNI = IXXX & λI Y S 22)
= p E (|X] A [Y] X2)]
We can thus bound the bias of the estimator ((SG) PNI as:
Eipht ol - [[[
> Aι
|Y| X2)]
s (E| (E
(P(X)) + A2))3
( )
1 3
2 cxp
(20)
where use the fact that X is 771 -usugauussian and Y is sp-suugaussian At the same time,
Var Var(PNI
PNI
(SG)
m
B(x(1
+
1/2
B(Y
) 1/2
m
1
X
A1 A2
2A
k
m
m²e?
m2=3
E2
where in the last step we use the choice of m = A1dæ which minimizes the expression
(P) Ei
in the previous step. Thus the MSE of PX in estimating is given by:
ElPNI p12 = (Blpki
2
+ Var(p
P)
2
x
A
A2 2
exp
3
m
m2
E1
E2
We now choose \ 2m/ (log(n) and bound from (20) then becomes:
X2
212 / log(n) for some K >>
The bias
E
PNI
(SG)
1
(21)
leading the MSE bound
E p/ S exp (-2gog()))) + log(n)
log(n) log(n)
m
72 2
+
S
n
nE?
of
Once again the privacy constraints satisfied by the Laplace mechanism and checking the sensitivity of the batch means.
3. We split the proofs for confidence interval coverage into the Gaussian and sub- Gaussian cases.
(a) (Gaussian case) Note that TXY in (3) is an average of k iid observations Т₃ defined as follows:
TXY
1
>
T3
where T₁ == m(x 2z(() + z
k
j=1
and
o = Var(T))
8 m=B{(((0))((P 2(0)))
Var(P +z(²)
(T (xxx)))
=m² (B m Var (2b11)
8
8
+
+
of
m
m288
(m 11-1 -mm--1
8
64
[1 +
R
1x
7
+
E
5
m²eqcz
23

---

where the last equality follows by expanding the squares of iid averages in the first term. Thus we have
Vk(ūxx - B(îxx)) 4 ((. as k + 00,
On
(P) and thus by delta method, (G) = Siin(iixy/2 (2) satisfies:
Vi(PNI - p) 4 N(0, 1) as k - oc. (T (T/2)on p²
Here we used the fact that sin (in(TE(fxx)/2) p. To estimate of we use the sample variance of Tj:
1 S : k
Σ j=1
(T) T)?
Note that S is constructed from ($1,62)-D) DDP statistics Tj, and thus S is also differentially private. By standard calculations,
B(S - o =
where we use our choice = 8/(5182) and & = n/m, and thus by Slutsky's theorem, we then have
Vi(Pi - p)
4 N(0 as k + co.
(T/2)S,, 1 (p
We thus have asymptotically a) coverage confidence intervals:
TS
(p(P))2
(G) TS 1I,vI= (p(P))2
PNi
2VK 21 2 PNI
2/k 21-0/2
(b) (sub-Gaussian case) Identical to what we observed for the case of Gaussian data, note that (SG) in (7) is average of k iid observations T, defined as follows:
PNI
SSG)
T /=1
where := m= + 2(2) 2
and
o² = Var(T;)
== 2 8
Var(Y-0) + +2,²))
(E
27
m²B((FU))(((0)))) (E ()) + m Var (ar(2
VVr((1)x)
8
m
m
1) (m-1) -(m-)) m 8 (Va((Y)xa) (ar((X]x1)
B(
[(X]) (Y15g)
(Var([X]A,) Var([Y]>,) (E
1)22) +
m
64
of
m
where the last equality follows by expanding the squares of iid averages in the first term of the previous line. Thus we have
V Vi(
9, N(O,1) as l: + co,
24

---

To estimate of we use the sample variance of Ty:
1 Sp = h: j=1
TT T)
Note that Sp is constructed from (51, DD statistics T3, and thus Sp is also differentially private. By standard calculations,
B(S -
-0))= =0
where we use our choice m mm (log(n)))(((1e)) and k = n/m, and thus by Slutsky's theorem, along with the asympiotically vanishing bias from (21) then have
vk(Phi p) 4 1(0, as k oc. Sp
We thus have an asymptotically (1 a) coverage confidence interval:
(SG)
Sp 21 a/2 (SG)
Sp 21-0/2) Vk
+
Vk:
Proof of Theorem 3.1. We separate the proofs of the two statements as follows.
1. To derive the MSE of the interactive correlation estimator for Gaussian data, first calculate from (9):
E iix + 2 - (2P(XX > 0) - 1)]
Var(fxx,,nt + Z) (E( (2T > 0) - 1))2
4e5x
4(cf1 + 1)2
n((ei - 1)2 n²(e=1 1) 0
4 n(E1 A 1)2
25
+
n² A 1)
Consequently,
E(PIN) - 2)²
T² 7²(1 (211-p² -p2)
(2P > 0) 1) int
(P)
12 π
+
E
(P)
7x (2P(XY > 0)
4
2
22 - -²)+1
+1
25 -1-p(1- +1
n(E1 A 1)2
4n²(E1
1)28
whenever ne(1 A 1) is sufficiently large.
2. To derive the MSE of the interactive correlation estimator for sub- Gabssias data, we take the following approach. It is straightforward to check that
E E ([[[X},, A >)))>a)
E (([X]A, + -2)) - B[[[X}, + Z))I((((}), + Z)Y| > A2)
=P- -[- > A1) -[([X), 2) + Z)Y| > 22)).
We next have P(((X)>, + 2)Y A2) S P(Y 2 Vlo(m))
P([[[]A, 2)1> X2/ /og(())
1
X
E1
exp
2
(log(n))
A
2\ (lo((n)
(22)
25

---

the fact that X is 1 subgauussin and Y is 7p-subgaussian. We can then bound the bias of the estimator ((SG)
BAANT P B[|XY| [( > + + (2()) + Z)Y1 > X2))]
(E) [ (EEXXY+ 2 (/log(m)) + + +2)1 > /2/ [ovlog(n)]
(23)
where we use (22) with
A1 21/1 v Ilg(n) and X2 = 4(72 V (l) A1)
and hence the variance becomes Var
v Var(([X]< 11))
413
n²
71
Var(XY)
4X
4r3
+
n
net
n²Ez
Var(XY)
16n
(log(n)) nej
64(73 1)(lg((n))
n²=3(E1 1)²
3. We split the proofs for confidence interval coverage into the Gaussian and sub- Gaussian cases.
(a) (Gaussian case) From (9) we write:
ixx + z exp(e1) +1
x Ti 12= exp(E1) +1 explsi) -1 (T' 22)
exp(e1) 1 1=1
where T; = -2
- 1) (X,, sign and Zo ~ Laplace (0, nea
2
Let us define:
(ex((E)) -1 exp((1)++ +1
o = Var(T:) =
(2P(XY > 0) - 1)
for which have the consistent estimator:
3 = 1 (ep((1) -11 2
exp((1) =1)
(πxx
We recall that [[ 2P(XX > 0) -1 and thus by the Berry Esseen limit theorem on T3
vn [ex(())) -1
On exp(e1) +1 7XV - P(XXY) > >0) ST
sup x
- PPxX + Zg 5x) 5
(24)
σ n
for a numerical constant C O. Here
Zxy N(0 and Zg Laplace (0, 0, V
2
and thus by the delta method,
P 2 2/n
exp((1) -1)
exp(E1) +1 (PINT - -p) (xx) -))$x)
(p(G)
sup
x n Poo
C
- P + +22 5x) $
(25)
26

---

To derive the confidence intervals we make two separate cases:
consider (vūsz)=- for finite constant c 2 0. In this case we have the confidence interval
Case 1: ((vnez)~1 e) In the first
PINT F To / (PINT)
exp(s1) +11 exp(e1) -1) (- - aa/2)/2
2/n2
where for any E R we define
F(x) = Pc I x)) where
lim n=000 Vnorn52
and Lap Laplace(0, 1).
The above is a valid confidence interval when lim vndges finite c, 2 0. This is no longer the case when vnE2 -> 0 as n - co.
2
for some
Case 2: (vnez + 0) In this case, (24) and (25) imply that we have the asymptolic convergence:
exp(s1) (PIN) -)) S Laplace(0. 1) # / pa exp(E1) +
ne2
leading to the asymptotically (1 a) coverage confidence interval
T / 1 (Pm))
(exp(E1) exp(e1) -1) log(a)
GCI PINT
nE2
where the width of the is determined by the a-th quantiles the Laplace(O, 1) distribution.
(b) (sub-Gaussian case) Note that
(9G)
n T: + 22
Σ
PINT
1=1
where [([x,] + Yi are iid random variables. Thus by the Berry Esseen theorem,
VniPPNTT
(SC)
(S0)
C(lg((n))75
sup
P sER
<x
PZxx + Zg S x) S
(26)
where Zxy ~ N(O, 1), 7/2 ~ Laplace (0,
2dz and
Tnapez
of = Var(([X}, ZI)Y).
As before, we now make two cases derive the confidence intervals.
Case 1: ((vnez/A2)) A2) + c) In the first case we consider (Viie/D2))> + c for finite constant 0. In this case (23) and (26) imply that have the confidence interval
PINT
σ F (1 n
a/2),
(80) PINT
T F- - a/2)
where
Σ (T: T)2
the sample variance of Tú, is an dD consistent estimator for o% Moreover, before for any & E R we define
F(x) = Ppxxx +c, Zapp S x) where e, lim 2A and ZLap Laplace 1).
n=000
Vno,EE2
27

---

The above is a valid confidence interval when lim,-xo /no,es for some
2Ag
finite Cx 2 0. This is no longer the case when vneg/>2 + 0 as n + 0c.
Case 2: (Vñes/\a 0) In this case, (23) and (26) imply that have the asymptotic convergence:
nE2
(SG)
-P) p) 4 Laplace(0,
PINT
2
leading to the asymptotically (1 a)) coverage confidence interval
(8G)
A2 log(a), PINT
(SG)
X log(a)
PINT
nE2
nE2
where the width of the CT determined by the a-th quantiles of the Laplace(O, 1) distribution.
B.2 Proofs of lower bound results
Proof of Theorem 4.1. Fix any non non-intoonn con-interactive (21, 61, DP protocol with transcript
T= (Ti, T2), and let P, denote the law of T when X22 iid. NN (t1)). We check an increasing function of whenever E (0, exp(-1)). Thus dc = --(n---w implies 6g log(1/6<) = o(n = o( The second inequality follows from the fact that net + oc. Invoking Lemma 2 gives, at O,
that f(x) = log log(1/z)
(T; <
nns A ne?).
(27)
Step 1. Prior supported in a small neighborhood of O. Let [-L/2, L/2) with L - 2co and center Po = O. Define the bosine-squanee prior on J:
2 do I (--77
2( (p00)p)) (2(0-~))
L m.))
cos cos2((Tx//) (Tx/2).
| 11
X(p)
0.
otherwise.
This prior satisfies the well known identity (see, e.g.; Tsybakov [2009])
X(p)2 A(p) 1
1m
2
IF(A)
dp
(28)
T
Step 2. Prior averaged information of the transcript. By (16) with po 0 and |pl S L/25 co.
IF(T:p) I (1+C))
Therefore
[.[Ie(T:P) = In(T: (P) & (1 (1+C))
(29)
Step 3. Van Trees inequality. Applying Lemma with parameter p, likelihood Pp, and
prior X, we obtain the Bayes risk lower bound
1 ((((T) p) 2 Ep[lx(Tip) + IF(A)
(29),(28)
(1+ Tp)(T) + (2m/T.)²
Using (27) and writing A = nEt A nEz,
1
Rayyes (A) inf E((p p) 2
(1 C.))
(30)
C1 A
(2m/T)²2 1.)2
28

---

Step 4. Choice of L and consequence. To minimize the denominator in (30) we take the largest admissible support, L 2cp, yielding
1
R Bayes (A) 2 ei + (m/CO)²
Since the minimax risk dominates the Bayes risk for any prior,
inf sup Ep [(p p)]] (A) 2 a + (T/c0)²
P pE1-1.11
In particular, whenever + de (our standing regime), the constant prior term is negligible and obtain
inf sup Ep[(p - [)]] nEt A
0 pE|-1.11
Step 5. Classical (1/n) term. Additionally the non privale parametric difficulty con- tributes an additional (11/n) term (e.g. by repeating the bound above without privacy constraints and with A x n near p = 0). Combining the terms yields
1
inf sup Ep (pp p) 2 PEN pEl 1111
n
nEi
n
Proof of Theorem 4.2. Let (i,j) be such that 2 Ej. Since 6, = o(n o(n-1-w), we have 5, (16;) = onn = o(E)), where the last equality follows from ne? + co. Simi- larly, 6, = o(n 11-) implies óz log' = o) = o(nefE)), using that n²=se3 + 2o. Hence, the conditions of Lemma 3 met, that Cn,,, in (17) indeed represents the Fisher-information bound for the (interactive, one-way) protocol.
Throughout, we abbreviate m eî e
Cn.. ne max A n²sje2. Let II { 22 be any fixed one-way interactive DP protocol, and denote by P, the law of the full transcript under correlation
=
Step Local regularity of information and the prior. By the standing regularity assumption (16), there are numerical constants co E (0,1) and C₁ > 0 such that
[IIII; p + +) = pI v(e)), |e| < <o.
sup |n((e] S Cn.
k|<ro
In particular, for |pl S co.
(FI:: S (1+C))
(31)
We place on p the aasine-squane prior supported on J = [- [-1,2, with I. S 20g and center 0 that the prior Fisher information is (see proof of Theorem 4.1 for details)
If(A) [ X((p)
2m
A(p) dp=
(32)
Step 2. Prior avorrgad information of the transcript. By (31) and Lemma 3 (or its analogue for Il2-1)),
([[])([) / (T]::)) Ap s (1+C,) < (1 + C,) Cn,
Step 3. Van Trees inequality.
Applying Lemma with parameter p. likelihood Ppr and
prior A, we obtain
1 Cn., (2T/L)²
Bayes (A) = inf E (p 2)
Ep((=([I:p)) + IF(A)
where = 1+ is an absolute constant. Choosing the largest admissible support L = 2co gives
1
Bayes (A) 2
(33)
C1 Cu + (T/cc)²² Since the minimax risk dominates the Bayes risk for every prior,
inf sup E, (p p) 2 RBayes (A). |E|-1,1]
29

---

Step 4. Extracting the two interactive terms.
By definition, Cı., = min(A, B} with
2 max!
= n
Hence 1/C1,, = max
(1/A + 1/B). Using (33) and the fact that the
additive constant (T/on)² 2 is negligible whenever AV B oc, we obtain the privacy-induced contribution
inf sup E l p)9]
2
Ne max
n n2
Step 5. Baseline parametric term and conclusion. Even without privacy constraints,
estimating a correlation from i.i.d. Gaussian samples incurs risk ((1/n); hence
1
inf 0 pE[-1.1]
Ep[ - p)3] 2 +
+
RE
n²=9=3"
max
which is the desired bound.
B.3 Proofs of Lemmas
In this section provide proofs of lemmas used to prove the lower bound theorems.
Proof of Lemma The main technical ingredient that goes into proving the minimax lower bound is obtaining a upper bound on the Fisher Information under the null i.c p = 0. Denote Z (X, Y) can be shown that the score function (2) for the parameter p under the null is given by
S₂(Z) = Σ X,Y
(34)
The fisher information under the null (T;;0)) is given by
1F [T; 0) = (EE(S,( TT)))
(35)
The fisher info under mull can be expressed as
Σ B(X,Y, 127) 27
(x(T;0) = EE
E
B(X, EY) Tz)
7 n
E
[X
Ty) T2)E(X, TT)B(Y, T2)]
==
where we have used the fact that X; Y, T, X, T/ Tj and Y, T Ti Th in the second line. We now have that
[TT:0)- = ΣΣ
E (E (OC
=1i=1
where in we use the fact that under the null Ti 1 T2. Define to matrices Mx and My such that
(Mx)1² E [E(X, TX) Ti)] and (My), E [E(Y, T2)E(Y, T2)
then we have that [F] tr(M)My). Using Lemmn we have that I=(T;0) 0)] < tr(Mx Mr(MM)]llMllb where 11-112 the spectral norm Next let us bound tr(Mx). Note that
can rewrite Mx as
Mx E (B(X TI)E(X [T))T)
(36)
30

---

where X is the data vector (x,) and [(X T) is the vector (B(X, T)) Hence
Ir(Mx] v Lr EE (E(x Ti) [Ti)))
[
X Ti) Ti)
B(E(X, Ti))?
Using Lemma 5 have that tr(Mx) I n e" (-1-e-1) (()===)) ) For bounding || ll2 can
either bound by tr(My) which implics by the previous argument that 1| lla ne3 or using contraction of the conditional expectation i.c.
Mx ( (X
= In
which implies || 11 S Putting everything together we have that
[F 0) & tr(MM) ) | [12 A tr
||Mx|2
2 e -1 2
e
e 51 2
S
π
π
Using the fact that ex 1 2x for < x <
we have that
8
1F (T;0)
< π
(Ee} A nE?)
Proof of Lemma Denote Z (X,, Y)) can be shown that the score function (Z) for the parameter under the null is given by
S,(Z) = Σ X,Y,
(37)
The fisher information under the null (T;;0) given by
Tr (T; 0) E(E(S,( Z)) (T)3)
(38)
The fisher info under null can be expressed as
B(XVV T)
(T;;0) = E
E(X, EYY T2.
27
B(E(X, TiYx, Tí, Tb)
(39)
where we have used the fact that X; 1 Y; T, X; 1 Ta Ti in the second line. Using the fact that ((B(A|B)²) EA² we have that.
2
2 EE Σ B(E(X, TD)D
(T;:0) = E B(E TDY Tr, Tb) )
1=1
31

---

Hence expanding the sum of squares we have that
Ir(T;0)
Σ E [
TT)YB(X,
[T))
[ YY?
Σ E [(X; Ti) In 6 E
2
where used the fact that Y; yj, Ti and 0, EY, 1 in the second and third line. The last inequality above follows from Lemma 5.
Following (39) can write
]
(T(
Σ E
R(X B(X
Σ B(E(X; TT) 7i, (1.75)
(40)
TiY;, T2)) and G E(X, Tr (Ee ii= B[E(X; TT)Y Ti, TT))))) Also nole that EGG, 0 since EY; 0 and Yx T T2, Tg. Now following a similar argument as in (46) we get that
Let call Gk E(X, Ti)Y (E=
6 (e9---
B.G. + 28 + / P([Ga| 2 t)dt + 1
EGR S
P(G 2 l)dt (41)
M
Note that
E
G
E
TXXx Ti
B(B(X, TiY Ti,
E
E (T)
E(E(X, TiY,, Tz)
27
E(E(X, Ti)3)
E
E(E(X, TiY,, Tı,TH)
c
1 (IE(T.O).
2
The last line follows since (Ti, d Tb) and the fact that E(E(Xx (T)²) < EX2 = Using the fact that (T(;;0) = Σx EG2 and putting everything together we have that
E e
2
- n1) VIr(T:O)
(T(T:0)
(42)
2
100
L P(IG)) t)dt
+ 2ndgM + +n
P(Gx 2 t)dt
(43)
Set
8
M 64
log
82.
in Lemma 4, to obtain
P(IGg|2)) di < 16 (8 + 4) (52/8)² s 62.
M
We similarly show that
P( 2 t)dt < 52.
M
32

---

Putting everything together we have that
c 52
----
e
[r(T:0) S n
VI=(T::)
(44)
π
log
8
+ 2nd264
+ 2nd2
(45)
82
VIr(T;0) & n/
pf1-e-91 2
11)
we are done else dividing both sides by
2
VIr(T:0) we have
2 VIr(T;0) Sn1
c
c2
e
11
π
2
2
8
2
-1/2
(E (E1)
-E
-1
e -
2nd264
log
2nd2
n1 -1
11
82
2
2
The second term can be dropped if dg loggog(())) (l/g(1 = o(n5782). The final form is achieved by using the fact that E1 S
B.4 Auxiliary Lemmas Lemma 4. Define G B(Xx Tijy EE B(E TJY T2, then we have that
P[[ 2 t) < 16(v 16(VMe-VVM/
M
Proof. Let us denote by Z; B(X; TiYY, We begin by bounding E By AM-GM and Cauchy-Schwarz inequality, we have that
S B23
Using the conditional Jensen's Inequality with the function I - ela? which is convex to obtain that
Re B(2 < ((E Ti, T2)) = ((e))2l))
Hence |/, I B(cllZi)). Bounding the RHS as follows
E(e = Be (X1100011)31
S (Y S tey? Be (TE),
where we used the AM-GM inequality in the second line and the independence of Y, and B(X; Ti) in the third line. Using conditional Jensen again, would have (EX,(EX < Ee which implics E(e s Ee Ee?.?? ?
Putting everything together we have that "G, < Eetex X,, Y; x This implics that
< for $ 1/2 (since
P(G.,| 2 1) < Pp G.1² 2 e//4 < 2e vi/4
The last. inequality follows from Markov. Hence we have that
P(G. 2 t) dt $2 Le c 16(vM MMe -M//4
33

---

Lemma 5. Assuming for h = 1,2, o% log(1/))) - o(E we have for any 1 i
iiin
2
B(R(X; TT))² S -a- 2
similarly we have R(E[V, (2))) - 2 6=2-0- 2
Proof of Lemma 5. Note that E(E(X, Ti)) (EX, Ti))] Denote A, = Xx(,(X, Ti)) we can write EA; = EAA" EA,,- Also let us define A; X,(B(X; T)) where T = (X'), where X' is the adjacent dataset with its ith data point replaced by X which is an independent copy.
We can write EA7- as
B(A)) = P(A 2 t)dt
M
PP(A 2jdt + S TP(AT 2 t)dt
cPI((())* 2 O)dL+ + ST IP(A 2 t)dt
-CAE(A)) En S P((AA) 2
[ TPAA 2 l)dl
S B(AD( + & + / P(AIZ t)dt
Similarly we have that
B(A7) P(AT 2 1)dt
IP(A, 2 t)dt + 1. IP(AT 2 t)dt
((()((())) 2 ()dt - + 1 TP(AT 2 t)dt.
P((A)) 2 t)dt 6, + / 10
e (IE(AA) 5
TP(A7 2 t)dt
M
2 E (EEEE / P((A 2 t)dt - M
Since EA, EA,- EAT we have that
/ 00 P(IAd Z t)dt
/ 1 P(IAT) Z t)dt
EA: S [(A)+
- B(A) + 25 +
R.A. + c
P(IAI 2 t)dt + S P(IA Z t)dt.
B|AT + 28, +
2
2
e E1
B|A71 + 28, M +
PP[A 2 t)dt +
IP([A]] 2 t)dt
(46)
2
MM
where we have used the fact that E.A- = 0. Observe that
E A1 = X TD < / 2
B(B(X, 22)) V /2 VEA.
Next we upper bound J PP(I. 2 l)dt in that direction we look at
Ee 144 E (x
< <
34

---

where we used the AM-GM inequality for the exponent. Next we can apply the Cauchy- Schwarz inequality obtain that
Re S V V ReCE(X.ITT))
the second term can further be bounded using the conditional Jensen's Inequality with the function x etx" which convex obtain that
Be EX TT)) E(E(e*X2 (i)) E(c(xi)
Putting everything together we have that EgdAA. & E(e(x:) S V2 for 1 1/4 (since X; Xf).This implics that
P(IA.) 2 1) < P(e 2 444 S /2e 1/4
The last inequality follows from Markov. Hence we have that JM P([A.) 2 t) 2v M/4
set M = 4log(1/61) to obtain JM P([A, 2 t) I 4y 201. we can similarly show that
J POA 2 t)dt S 48
Putting everything together we have that
c -
V² VEVA 861 log(1/6)) 88221
EA,
If EA < --1--- 2
done clse dividing both sides by VEA, have
VEA, S ( (
2 π (86, log(1/51) + 2v251)
2
1/2
6 c
51
π
2
The second term can be dropped if 61 log(1 (1))) = o(E?).
Lemma 6. For square matrices A and B, if B is symmetrie, we have
tr(AB) & ||A||2 tr(B)
Proof of Lemma 6. The proof follows from von Neumann's trace inequality:
tr(AB) & [tr(AB) s Σ agB, S max(as) Σ 8 = max(a;) x tr(B)
where 0g and 3, are the singular values of and B respectively. The proof follows by the definition of le operator norm used matrix A.
O
35


Reviews:
[{"review_id": "Ix66KLA8Ju", "reviewer": "Reviewer_dVhn", "summary": "This paper considers the problem of estimating the correlation between two random variables, $X$ and $Y$, which are obfuscated by approximate (i.e., $(\\epsilon,\\delta)$) differential privacy mechanisms. The paper considers two main scenarios:  \n\n- Non-interactive (NI) Protocol: In this setting, the statistics about $X$ and $Y$ are constructed and privatized independently. \n- Interactive (INT) Protocol: In this setting, the statistic about one variable (say, $X$) is constructed and sanitized independently from $Y$, whereas the statistic about the other variable $Y$ is constructed with the benefit of accessing the privatized version of the statistics of $X$, and then privatized. \n\nThe paper derives approximate formulas for the minimax optimal rate for correlation estimation in these two scenarios for Gaussian and sub-Gaussian distributions, in terms of MSE. One of the main results is that (perhaps unsurprisingly) the estimation under INT is strictly more precise than under NI. \n\nThe paper also proposes methods to estimate the correlations in both scenarios, which also provide confidence intervals. It also proves minimax lower bounds, confirming that the proposed estimation methods are nearly optimal. Another result (which, on the contrary, I found quite surprising) is that the formula for the NI case does not depend on $\\delta$.\n\nFinally, the paper presents experimental results that validate the theoretical findings.", "questions": "- Is $\\rho$ the Pearson correlation coefficient? \n\n- On what distribution on $\\rho$ is the expectation in the Theorems 1.1. and 1.2 taken?", "limitations": "- I would suggest the authors to provide some experiments on real data to explore the practical relevance of the results.\n\n-  I would recommend the authors to explain all the non-standard symbols and the key notions before using them.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths \n\n- The paper addresses an important problem and it justifies it well in terms of federated learning, specifically, for the vertically distributed setting. For instance, the case of healthcare data sharing between a hospital and a pharmaceutical company, where direct exchange of original data is not possible due to privacy constraints. \n\n- The paper provides a thorough theoretical analysis of the specific cases of Gaussian and sub-Gaussian, and seems rather solid technically.\n\n- I found it very surprising that the formula for the NI case does not depend on $\\delta$.\n\n- To the best of my knowledge, the paper addresses an original problem (although very natural), and the contribution is novel. \n\n## Weaknesses\n\n- I found the paper rather hard to read. First of all,  some notations are not explained. For instance, the symbol between the LHS and the RHS of the equations in Theorem 1.1 and 1.2 (I suppose it means \"approximately equal to\"), and the symbol \"V\" in the formula in Theorem 1.2 (I suppose it means \"the larger of the two\"). Furthermore, some key notions are not explained. For instance, the correlation measure $\\rho$ (I assume it is the Pearson correlation coefficient). These shortcomings, however, can be fixed by a brief preliminary section, which I invite the authors to provide. \n\n- The study is purely theoretical and on ideal distributions; it would have been good to provide at least one experiment on real data to explore the practical relevance of the results.", "was_revised": true, "final_justification": "The authors have replied to my questions in their rebuttal in a convincing way", "rebuttal": "Thank you for the positive review and the very relevant questions! Please find below our responses to the issues you have mentioned.\n\n### Response to Weakness 1  and Limitation 2\nThank you for bringing up the notational aspect. We agree that a concise preliminary section on our notation would greatly aid the reader. In the camera‑ready version, we will include such a section to ensure all symbols and conventions are clearly defined.\n\n### Response to Weakness 2  and Limitation 1\nWe appreciate your suggestion regarding empirical validation on heavy‑tailed data. For the camera‑ready version, we will incorporate additional experiments on real-world, heavy‑tailed datasets to demonstrate the robustness of our method. In addition, our preliminary findings suggest that heavy tailed data incur a stricter cost of privacy. We will investigate this in future work, and mention this direction in the future work section of this paper.\n\n### Response to Question 1  \nYes, $\\rho$ is indeed the Pearson correlation coefficient.\n\n### Response to Question 2  \nOur focus is on the minimax risk. Accordingly, we do not treat $\\rho$ as a random variable nor impose any prior distribution on it. Instead, we evaluate the mean squared error for each fixed $\\rho\\in[-1,1]$ and report the worst‑case (maximum) risk over that interval."}, {"review_id": "42Jq2v6jnb", "reviewer": "Reviewer_FZy2", "summary": "This work focuses on federated learning for correlation estimation of two random variables vertically partitioned on two servers. Due to privacy issues, servers share only privatized data with two sets of privacy budgets in terms of differential privacy. This work utilizes minimax optimal rates for correlation estimation for both non-interactive and interactive mechanisms, and also develops confidence intervals for the correlations. Additionally, it proves that interactive mechanism is better than the non-interactive one.", "questions": "1. Why does the delta on both servers does not affect the minimax rate?\n2. Why does the conditional probability in the right-hand side of the second inequality under Line 93 depend on X,Y’, not X’, Y’? In other word, why does the T2 construction not depend on X’?\n3. Line 99, I think you want to say interactive instead of non interactive.\n4. What datasets do you use in the experiments? Would be better to use some well-known benchmarks.\n5. What will be different if this work extends to several features instead of one feature? Can you talk more on this for the future work? It is ok to include this point in the appendix if space is limited.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This work provide both interactive and non-interactive framework for the correlation estimation with theorems, and verify that the interactive one outperforms the non-interactive one.\n2. This work considers the privacy budgets on both servers instead of a central privacy budget.\n3. Except theorems, this work provides experiments for both cases, and open-sourced the code.\n\nWeakness:\n\n1. The authors did not mention why they focus on correlation estimation, and why this problem is important in the VFL with DP.\n2. This work  hides all information of proofs in the appendixe. Would be better to mention clues to prove each theorem in the main text with one or two sentences.", "was_revised": true, "final_justification": "Authors have cleared all my questions, and since all reviewers tend to accept it, I will keep my score, too.", "rebuttal": "Thank you for the favorable review and the very relevant questions. Please find below our responses to the issues you have pointed out.\n\n### Response to Weakness 1\nThank you for this question on the motivation of the current work. We decided to explore and demonstrate the cost of privacy for correlation estimation because correlation is the most canonical example of interest from a _joint_ distribution. Just as the mean is arguably the most basic object to understand in the setting of central differential privacy, correlation becomes the essential quantity of interest in a joint distribution, even more so, when two sides of the data cannot meet. As our results show, this natural object already shows interesting departures from traditional rates on differential privacy. We believe exploring vertical federated learning through the lens of privacy cost would lead to even more exciting results--- our exploration into the correlation estimation is merely the tip of the iceberg. A number of interesting future directions have already appeared, from your and the other reviewers' suggestions (e.g., in your Question 4), which we will explore in subsequent work.\n\nWe appreciate your suggestion on including a short description of the proof. Space permitting, we will include steps for the upper bounds in the camera ready version. Note that the proof strategy for the lower bound is already given in Section 4.\n\n\n### Response to Question 1  \nFor the one-dimensional problem, both pure DP $(\\varepsilon,0)$ and approximate DP $(\\varepsilon,\\delta)$ achieve the same rate—provided $\\delta$ is sufficiently small. In other words, relaxing from pure to approximate DP does not improve the information‑theoretic rate.\n\n### Response to Question 2\nThanks for the great question; equation 9 is a key point in our privacy definition. To avoid confusion we will update the second line to:\n$$\n\\mathbb{P}(T_2(\\boldsymbol{Y},T_1)\\in A|T_1,\\boldsymbol{Y})\\le~ \\exp(\\varepsilon_2)\\mathbb{P}(T_2(\\boldsymbol{Y}',T_1)\\in A|T_1,\\boldsymbol{Y}')+\\delta_2\n$$\nwith the interpretation that in the interactive case, we are augmenting the non-interactive definition to allow $T_2$ to depend on $T_1$, which is seen as a fixed output from server 1. Since $T_1$ is already private, this inequality pertains to the privacy requirements on $\\boldsymbol{Y}$ for a fixed $T_1$. See also the first question by Reviewer TVPc.\n\n### Response to Question 3\n\nYes, that is correct; we shall correct this typo in the camera-ready version.\n\n### Response to Question 4\n\nOur numerical study sections are based on synthetic data (generated via simulations). We plan to add real data examples in the camera-ready version.\n\n### Response to Question 5\n\nIn the multidimensional setting one would have to estimate a correlation matrix, and we expect the rates to depend on 1) dimension $d$, and 2) the norm which we use to estimate the matrix. We plan to address this point in the future work section."}, {"review_id": "rZj8UfVLbe", "reviewer": "Reviewer_cn9Y", "summary": "This paper studies the fundamental problem of estimating the Pearson correlation coefficient between two variables that are vertically separated across two servers. The authors establish the minimax optimal estimation error rates under server-level differential privacy. The analysis covers two distinct communication protocols: a non-interactive setting where servers release privatized statistics independently, and an interactive setting where one server can access the privatized output of the other. The core theoretical contribution is the derivation of matching upper and lower bounds for the estimation error, which reveals that the interactive protocol is provably superior if and only if the servers have asymmetric privacy budgets. The authors propose estimators that achieve these optimal rates and provide numerical experiments to support their theory.", "questions": "- How would your estimators need to be adapted for heavy-tailed distributions? Would techniques based on median-of-means or other robust statistics fundamentally alter the minimax rates you have established?\n\n- Could you provide more insight into the non-asymptotic performance? A key concern with DP is that the hidden constants in the error bounds can render a method impractical. Can you characterize how the constants in your rates depend on the privacy parameters ($\\epsilon$, $\\delta$) and the sub-Gaussian parameters of the data? This is essential for understanding the true sample complexity of your method.", "limitations": "The authors have adequately addressed the limitations of their work", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths\n1. The paper's primary strength is its rigorous comparison of non-interactive and interactive protocols, yielding the new insight that interaction's benefit is tied directly to asymmetric privacy budgets.\n\n1. Within its assumed setting, the work is technically complete, providing matching upper and lower bounds on the minimax risk.\n\n---\n\n### Weaknesses\n1. The paper's most significant weakness is its focus on the bivariate case. By assuming each server holds only a single data column, it solves a \"toy problem\" that bears little resemblance to real-world Vertical Federated Learning, where entities hold datasets with hundreds or thousands of features. This makes it difficult to see the derived rates as a meaningful benchmark for any practical VFL application.\n\n1.  The analysis relies on the restrictive assumption of sub-Gaussian data, which excludes many important real-world datasets that exhibit heavy tails. This limits the applicability of the proposed estimators and the relevance of the optimality guarantees.\n\n1. The paper's asymptotic analysis of the error rates hides the constant factors, which can be substantial and dictate the practical sample complexity. There is a lack of discussion on the number of samples $n$ required to achieve reasonable error under strong privacy settings (e.g., small $\\epsilon$), which is a crucial question for any real-world deployment.", "was_revised": true, "final_justification": "The authors have clearly addressed all my concerns. I believe this is a good paper, and my former score already adequately reflects my assessment.", "rebuttal": "Thank you for the favorable review and the very pertinent questions. Please find below our responses to each of your comments.\n\n### Answer to Weakness 1\nA very valid concern indeed. In the multidimensional setting we are estimating a correlation matrix, and we expect the rates to depend on 1) dimension $d$, and 2) the norm which we use to estimate the matrix. We plan to address this point in the future work section.  \n### Answer to Weakness 2 and Question 1\nThe heavy-tailed case is fundamentally different from the sub-Gaussian case, even in the case of mean estimation and central DP. For example, KSU20 consider mean estimation under central DP through a median of means, and show a worse minimax rate due to the heavy tails. We expect this fundamental difference (in terms of rate) to also prevail in this vertical FL setup and consider it as an avenue for future work.\n\nKSU20: Kamath, G., Singhal, V., Ullman, J.. (2020). Private Mean Estimation of Heavy-Tailed Distributions. <i>Proceedings of Thirty Third Conference on Learning Theory</i>, in <i>Proceedings of Machine Learning Research</i> 125:2204-2235.\n\n\n\n### Answer to Weakness 3 and Question 2\nThe rates in the current version are written to explicitly show the dependence on the privacy parameters $\\varepsilon_1$ and $\\varepsilon_2$. Following your suggestion, in the revision, we will also make the dependence on the subgaussian parameters ($\\eta_1$ and $\\eta_2$) more explicit. Upto numerical constants, the sub-Gaussian error rates in the non-interactive case would be $\\frac{\\log(n)}{n}\n\t\t\\left(\n\t\t\\frac{\\eta_1^2}{\\varepsilon_1^2}\n\t\t+\\frac{\\eta_2^2}{\\varepsilon_2^2}\n\t\t\\right)$. For the interactive case, the sub-Gaussian error rates would be $\\frac{\\log(n)}{n(\\frac{\\varepsilon_1}{\\eta_1}\\vee \\frac{\\varepsilon_2}{\\eta_2})^2}\n\t+\\frac{\\eta_1^2\\vee\\eta_2^2(\\log(n))^4}{n^2\\varepsilon_1^2\\varepsilon_2^2}$.\nAll of this would be made more precise in the camera ready version."}, {"review_id": "sAtu3ycIT2", "reviewer": "Reviewer_TVPc", "summary": "This paper proposes a series of novel solutions for privately estimating the correlation (equiv. covariance) of two random variables X and Y vertically partitioned to two servers. Its non-interactive protocol for Gaussian (NI, G) takes the sign of each value and releases batch means of each server with Lapalce noise. The covariance is then estimated though a dot product between the noisy means. For subgaussians (NI, SG), truncation is applied to achieve a similar bound with O(log(n)) overhead. In its interactive protocol (INT, G), the server with less stringent privacy requirement applies random response to (the sign of) each value and sends it to the other server, who then computes a similar privatized dot product for estimating the covariance. The interactive protocol for subgaussian (INT, SG) also involves truncation. The paper provided confidence intervals for the above methods and proved matching lower bounds. It also conducted experiments on simulated data to justify the performance.", "questions": "In addition to the weaknesses above, I have the following questions:\n\nLine 93: In the second inequality, why is P(T2) conditioned on X? As T2 does not obvserve X directly, should the probability be conditioned on the same value of T1(X)?\n\nLine 106: If X is public, then why consider constant eps1 instead of eps=infty? In the latter case, your error bound for the interactive protocal becomes zero, which does not make sense since Y is still private. According to the proof, the dependency on eps1 should be min{eps1, 1}, I think it is better to clarify this.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "S1. This paper is technically dense. It achieves matching upper and lower bounds for the proposed problem, which is significant.\n\nS2. There are novel ideas in constructing the upper and lower bounds.\n\nS3. The paper is well-organized with precise statements and logical proofs.\n\nW1: For experiments, this paper provides simulation results where data are drawn from specific distributions. It will be interesting to perform experiments on real-world data which are not exactly Gaussian (or sub-Gaussian). In that case, the DP guarantee should still hold while the utility guarantee may not. But analyzing the estimation error still makes sense. Since the protocols require \\eta_l as inputs, it also helps to discuss about how they can be estimated for real data.\n\nW2: In Section 3 the authors provide an interactive protocol which achieves better rate than the non-interactive one. However, the main content of the paper do not discuss the reason behind this improvement. To be specific, the interactive protocol uses a different randomization method for T_1(X) compared to the non-interactive counterpart, it will be better to explain the intuition behind this design. Furthermore, the results in this paper holds for one-way interaction, it will be interesting to add a discussion on the two-way interaction results by properly dividing the privacy budget.\n\nW3: There are several typos in the paper, which should be corrected:\nLine 49: (eps1, delta) > (eps1, delta1)\nThe equation following line 64: T1(X)\\in A | Y > T1(X)\\in A | X\nTheorem 1.1: Please define \\asymp, which was used to denote big-Theta. Also define \\lesssim and \\gtrsim.\nLine 74: is this case > in this case\nTheorem 1.2: Please mention that \\wedge (and \\vee) was used for min (and max).\nLine 136: The current definition of Bj looks like a set of 2 elements, please use {m(j-1)+1,...,mj}\nLine 164: The noise should be 2*lambda_l / (m eps_l) here. This should be a typo, since the proof in line 760 looks fine.\nLine 753, Equation (16): The presence of constants here indicates the analysis is not asymptotic. Then the first equality (3rd line) is incorrect. By symmetry, you have E[(X+Z)^4]=E[X^4] + 6E[X^2Z^2] + E[Z^4] and the equality does not make sense. I believe this is asymptotically correct, but please be careful about the constants since it affects your choice of m.\nLine 757: The first equality needs to be corrected. You ommitted terms for X>lambda1 and Y>lambda2. Please include the condition for this and note that you should not write equal.\nLine 760: Missing end bracket.", "was_revised": true, "final_justification": "This paper proposes a series of novel solutions for privately estimating the correlation (equiv. covariance) of two random variables X and Y in the two server model. Although there are some limitations (e.g. supporting only two-servers, and only sub-gaussian distributions), the paper is in general technically dense, well-organized and clearly presented, provided that the typos are fixed as mentioned in the rebuttal. Therefore I would like to recommend accept.", "rebuttal": "First of all, thank you very much for the  for the favorable review  and the very careful reading. Your comments have helped us pinpoint a lot of oversights, which we have already corrected, and look forward to sharing in the camera ready version.\n\n### Answer to Weakness 1\n\nIn the revision we will add a real data experiment with the specific goal of explaining the use-case of our results. As you have pointed out, estimating the sub-Gaussianity parameter $\\eta$ is a valid concern in real data applications. We have not focused on this issue in the main results, but will make this explicit in the experiments section in our camera ready version. \n\nWhile working under the sub-Gaussianity assumption, to use our estimators and confidence intervals, we suggest obtaining an upper bound for $\\eta_1$ using the range of a subset of $X$, and part of the privacy budget $\\varepsilon_1$. This task would incur a cost according to central privacy rates, which would be asymptotically negligible in comparison to all the minimax rates we have found for vertical privacy.\n\n### Answer to Weakness 2\n\nThe basic intuition is from the standpoint of whether data on the two servers can meet. In the strictest notion where data cannot meet, we find the non-interactive rates. _Relaxing_ this to allow one server to look at certain private transcripts from the other server can thus be expected to improve the estimation rates. The exact nature of the transcripts was derived after experimenting with how the size of the transcripts to be shared affects the final rate. The specific version of randomization was chosen using existing local-DP techniques.\n\nOn two-way interactions, we conjecture that the rates cannot be improved beyond the currently derived ones. However our current framework does not cover two-way interactions, and so far such a general proof eludes us. We intend to pursue this in future research.\n\n### Answer to Weakness 3\n\nThank you for pointing out these typos! We will add a section explaining notations, as you and another reviewer have suggested. In addition, your comments on lines 753 and 757 would be answered as follows.\n\nLine 753: We will update equation 16 to $\\left(\n\t\t\t\\frac{9m}{n}\n\t\t\t+\n\t\t\t\\frac{24}{n\\varepsilon_1^2}\n\t\t\t+\n\t\t\t\\frac{24}{n\\varepsilon_1^2}\n\t\t\t+\n\t\t\t\\frac{64}{mn\\varepsilon_1^2\\varepsilon_2^2}\n\t\t\t\\right)\t$, and replace the equality in the previous line with inequality, as you have correctly pointed out. Without changing the choice of $m$, this leads to the final upper bound of $\\frac{10\\pi^2}{n}\\left(\\frac{1}{\\varepsilon_1}+\\frac{1}{\\varepsilon_2}\\right)^2$, validating the current statement of our theorem. The constants can be made tighter for a different choice of $m$, again, following your suggestion. We will implement this in the camera ready version.\n\nLine 757: Indeed, there would be additional terms for when $|X|$ or $|Y|$ are larger than $\\lambda_1$ or respectively $\\lambda_2$. To deal with this, we will write out the four terms of the expectation explicitly --- each term being contributed for the four cases depending on whether none, exactly one, or both, of $|X|$ is larger, or $|Y|$ is larger.\n\n### Answer to Question 1\n\nYes, we will update line 93 to allow conditioning on T1, and not on X. That is, the updated display would read\n$$\n\\mathbb{P}(T_2(\\boldsymbol{Y},T_1)\\in A|T_1,\\boldsymbol{Y})\\le~ \\exp(\\varepsilon_2)\\mathbb{P}(T_2(\\boldsymbol{Y}',T_1)\\in A|T_1,\\boldsymbol{Y}')+\\delta_2.\n$$\n\n### Answer to Question 2\n\nThank you for pointing this out. In the revision, we will add $\\varepsilon_1\\wedge 1$ in place of $\\varepsilon_1$ as you have suggested."}]

Author rebuttal:

Meta-review: The paper addresses the problem of estimating the correlation between two random variables whose values are stored on different servers and where differential privacy constraints are applied separately on each server. They derive the minimax optimal rates for both the interactive and non-interactive settings and algorithms that match these rates, showing that interactive estimators achieve strictly better rates. 

Reviewers unanimously found the paper to be rigorous and substantial, tackling a novel but simple and well motivated problem and providing complete and technically sophisticated results. Congratulations on a very well received paper. 

The weaknesses raised were minor in comparison, but included questions about application to real-world data and limitations to a relatively simple setting (bivariate, sub-Gaussian data), as well as some minor issues regarding notation and mathematical statements.

In the rebuttal, the authors responded to specific questions and promised to run experiments on one or more real-world data sets with heavy-tailed data for the final version of the paper. They highlighted that extensions to the multidimensional case and theoretical analysis for heavy-tailed distributions are interesting avenues for future work.
Decision: Accept (spotlight)