FED-$\chi^2$: Secure Federated Correlation Test
Authors: Lun Wang
Qi Pang
Shuai Wang
Dawn Song
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Analytics
Hypothesis Test

Abstract: In this paper, we propose the first secure federated $\chi^2$-test protocol, FED-$\chi^2$. We recast $\chi^2$-test as a problem of the second moment estimation and use stable projection to encode the local information in a short vector. Due to the fact that such encodings can be aggregated with summation, secure aggregation can smoothly be applied to conceal the individual updates. We formally establish the security guarantee of FED-$\chi^2$ by demonstrating that the joint distribution is hidden in a subspace containing exponentially possible distributions. Our evaluation results show that FED-$\chi^2$ achieves good accuracy with small client-side computation overhead. FED-$\chi^2$ performs comparably to the centralized $\chi^2$-test in several real-world case studies. The code for evaluation is in the supplementary material.

Under review as a conference paper at ICLR 2022
FED-X2: 2: SECURE FEDERATED CORRELATION TEST
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose the first secure federated xe-test protocol, FED-x We recast xe-test as a second frequency moment estimation problem and use stable projection to encode the local information in short vector. As such encodings can be aggregated with summation, secure aggregation can be applied to conceal the individual updates. We formally establish the security guarantee of FED-x* by demonstrating that the joint distribution is hidden in a subspace containing exponentially possible distributions. Our evaluation results show that FED-X achieves good accuracy with small client-side computation overhead. FED-X² performs comparably to the centralized x²-test in several real-world case studies. The code for evaluation is in the supplementary material.
INTRODUCTION
Correlation test, as the name implies, is the process of examining the correlation between two random variables using observational data. is a fundamental building block in a wide variety of real-world applications, including feature selection (Zheng al. 2004), cryptanalysis (Nyberg 200T), causal
graph discovery (Spirtes et al.] 22000), empirical finance (Ledoit & Wolf. [2008] Kim & Ji (203)).
medical studies (Kassirer, 1983) and genomies (Wilson et al. [1999] Dudoit et al. [2003). Because the observational data used in correlation tests may contain sensitive information such as genomic information, centralizing the data collection risky. To address, we resort to a federated setting in which each client maintains its own data and communicates with a centralized server to calculate a function. Note that the communication should contain as little information as feasible. Otherwise, the server may be able to infer sensitive information from the communication transcript.
In the present work, we study representative correlation test, namely x² -test, under the federated setting. There are two straightforward methods for conducting 2 in such context. First, clients can upload their raw data to the centralized server and delegate the test to it. While this method is effective in terms of communication, it entirely exposes the clients' private information. Second, clients may run secure multiparty computation (MPC) under the server's coordination. Thus, clients can jointly run x -test without disclosing their data to the server. However, general-purpose MPC imposes significant computation and communication overhead, which is typically intolerable in a federated setting with computationally limited clients, e.g., mobile devices.
To address the dilemma, we present a federated protocol optimized for x2-test that is computationally and communicationally efficient and discloses limited information to the server. We begin by recasting 2tttstt as a second frequency moment estimation problem. To approximate the second frequency moment in federated setting, each client encodes its raw data into a low-dimensional vector via stable random projection (Indyk] 2006 Vempala 2005 2008). Such encodings can be aggregated with only summation, allowing clients to leverage secure aggregation (Bonawitz et al. [017 Bell et al. 2020) to aggregate the encodings and the server to decode them to approximate the second frequency moment. Because secure aggregation conceals each client's individual update within the aggregated global update, the server learns only limited information about the clients' data.
Our evaluation on four synthetic datasets and 16 real-world datasets shows that FED-X² can replace centralized ""testt with good accuracy and low computation overhead. Additionally, analyze FED-X² in three real-world use cases: feature selection, cryptanalysis, and online false discovery rate control. The results show that FED-X² can achieve comparable performance with centralized -tst and can withstand up to 20% of clients dropping out with minor influence on the accuracy. In summary, we make the following contributions:

---

Under review as a conference paper at ICLR 2022
We propose FED-X2, the first secure federated -tttt protocol. FED-X² is computation- and communication-cffiiine and leaks much less information than trivially deploying secure aggregation.
FED-X2 decomposes ~tett into frequency moments estimation that can easily be encoded/decoded using stable projection and secure aggregation techniques. We give formal security proof and utility analysis of FED-X".
We evaluate FED-X² in real-world use cases, and the findings suggest that FED-X² 2 can substitute centralized -est with comparable accuracy, and FED-x² can tolerate up to 20% of clients dropout with minor accuracy drop.
RELATED WORK
Bonawitz al. (2017) proposed the well-celebrated secure aggregation protocol as low-cost way to calculate linear functions in a federated setting. It has seen many variants and improvements since then. For instance, [Trex al. (2019) and Xu al. (2019) employed advanced erypto tools for secure aggregation, such as threshold homomorphic encryption and functional encryption. [So et al.) (202I) proposed TURBOAGG, which combines secure sharing with erasure codes for better dropout folerance. To improve communication efficiency, [ell et al. (2020) and Choi et al. (2020) replaced the complete graph in secure aggregation with either sparse random graph or a low-degree graph.
Secure aggregation is deployed in variety of applications. Agarwal et al. (0118) added binomial noise local gradients, resulting in both differential privacy and communication efficiency. Waang al. (2000) replaced the binomial noise with discrete Gaussian noise, which is shown to exhibit better composability. Kairouzz al. (202T) proved that the sum of discrete Gaussian is close to discrete Gaussian, thus discarding the common random seed assumption from Wang et al. (2020). The above three works all incorporate secure ag aggregation in their protocols to lower the noise scale required for differential privacy. Chen al. (2020) added an extra public parameter to each client to force them to train in the same way, allowing for the detection of malicious clients during aggregation. Nevertheless, designing secure federated correlation tests, despite its importance in real-world scenarios, is not explored by existing research in this field.
On the other end of the spectrum, Wang et al. 2021) proved that stable projection is differentially private if the projection matrix is secret. In our protocol, the projection matrix is public information; hence FED-X2 does not consider the differential privacy guarantee.
3 FEDERATED CORRELATION TEST WITH MINIMAL LEAKAGE
In this section, we elaborate on the design of FED-X², secure federated protocol for 2tett Sec. 3.1 first formalizes the problem, establishes the notation system, and introduces the threat model. In Sec. 3.2 we recast x" -test as second frequency moment estimation problem in the federated setting, and consequently, we are able to leverage stable projection to encode each client's local information
(Sec. 3.3 and then aggregate them using secure aggregation (Sec. 3.4). Sec. 3.5 3.6 and 3.7 present security proof, utility analysis, communication analysis, and computation analysis of FED-XX
3.1 PROBLEM SETUP
We now formulate the problem of the federated correlation test and establish the notation system. [1....,).. We denote vectors with bold lower-case letters (e.g., a, b, c) and matrices with bold upper-case letters (e.g., A, B, C).
We use [n] to denote (1...., n..
We consider a population of n clients C = {ci]ie(M) Each client has one share of local data composed of the triplets D; {(x. y, (6) }. E X,y E V,
vay E (-M,.... M), where x and y are categories of the contingency table, day is the observed counting of the categories æ and in the local contingency table of the 5th client, |x| = my and | my are finite domains, and
(i)
(6) M is the maximum value [02g] can be. The global dataset is defined as = {(x, y, Uzy) : Vay =
Eieto (i) We focus federated xtetest and the data in contingency table is discrete. For the ease of presentation, we define the marginal statistics Us = Σy Uzy: By Exe[1>1) Days and P. Xe denoting the expectation of Uzy if a and Exe(tRe).eei Pay. Besides, define Tay
2

---

Under review as a conference paper at ICLR 2022
y are uncorrelated. We define my and use an indexing function I [m,]] x [my] + [m]] to obtain a uniform indexing given the indexing of each variable. centralized server S calculates the statisties for x >tttest (D= X' and y are correlated without collecting the raw data from clients.
[) (Mny=Bay] on the global dataset decide whether Vary
Overall, using MPC to conduct secure correlation tests in a federated scenario is highly expensive and impractical (Boyle et al. 2015, Damgård et al. 2012). Hence, in the present work, we trade off accuracy for efficrency, long the estimatin error small with high probability. Formally, if FED-X² outputs 8x2, whose corresponding standard centralized -tetest output is sx², the following accuracy requirement should be satisfied with small and ò.
P((1 e)sya S 8xa S c)s,a] 2 1
Threat Model. We assume that the centralized server S is honest but curious. It honestly follows the protocol due regulatory or reputational pressure but curious discover extra private information from clients' legitimate updates for profit or surveillance purposes. As result, client updates should contain as little sensitive information as feasible. We want emphasize that, while the server may explore the privacy of clients, the server will honestly follow the protocol due to regulation or reputational pressure. The server won't provide adversarial vectors to the clients.
On the other hand, we assume honest clients. Specifically, we do not consider client-side adversarial attacks (e.g., data poisoning attacks (Bagdasaryan et al. 2020. Bhagoji et al., 2019)). However, we allow small portion of clients drop out during the execution. Also, mentioned in Sec. 2
do not consider the differential privacy guarantee; see further clarification in Appendix
3.2 FROM CORRELATION TEST TO FREQUENCY MOMENTS ESTIMATION
We first recast correlation test to second frequency moments estimation problem as defined below. Given set of key-value pairs S {ks Us [e[j). we oe-onianize it into histogram 76 = {kt U/
Ex.= u. and estimate the th frequency moments as Fa E, u5. 2-testt can thus be
recast to 2nd frequency moments estimation problem as follows:
(U2y
Uxg))
Σ
Vay Uay )2
xxa
Try
Vuay
In federated setting, each client c, holds local dataset D. = {2x y. U2g } and computes a vector
(.()) - Bay/n and u, has m elements. Thus, the challenge in federated 2testt Bay
Uy where u, uı[[(z, y)] becomes calculating the following equation:
(D)
Usy
Üzy =1
EE(n]
3.3 ENCODING BY STABLE PROJECTION & DECODING BY GEOMETRIC MEAN ESTIMATOR
To address the aforemennioned challenges and to easily integrate the algorithm into secure aggregation protocols,
stable random projection (Indyk 2006; Vempala 2005) and geometric mean estimator LLi 2008) to approximate the data's second frequency moment efficiently. We begin by discussing stable distributions, followed by the encoding and decoding techniques.
Definition (a-stable distribution). A random variable follows an a-stable distribution Qa,3. if its characteristic funtitio is as follows.
tan where F is the scale the th power and 3 is the skewness.
(t( -
TT
2
o-stable distribution named due its property called a-stability. Briefly, the sum of independent a-stable variables still follows an o-stable distribution with a different scale.
Definition (a-stability). If random variables Qa,a,1 20.3.1 and X and Y are indepen- deni, then C C2Y Qa.8.Cy +C2-
We borrow the genius idea from Indyk's well-celebrated paper (Indyk 2006) to encode the frequency moments in the scale parameter of stable distribution defined Definition To encode the local
dataset D. = {xx y. (() }. each client c, i E [n), is given by the server an x m projection matrix whose values are drawn independently from a-stable distribution 20,8,1, where é is the encoding
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1:
The encoding and decoding scheme for federated frequency moments estimation.
Note that the encoding and decoding themselves do not provide any security guarantee.
Function ENCODE (P. u:):
return P x U;
Function GEOMETRR TRI CME AAMEANNESSTMTTN (e):
I1 1 1//
dm.).a f ( F) F))
// is the encoding size.
return d(2).am
Function DECODE (e):
return GEOMETRI CWW.MAERRCMEANEETT...
size and m = my my. The client re-organizes the data into a vector u, where u,(1(z, [[] = Ury Then, the client projects u, to e; = P x u, as the encoding (line 2 in Alg. D.
(i)
To decode, the server first sums the encodings up e Eiejnn e; and estimates the scale of the
variables in the aggregated encoding with an unbiased geometric mean estimator (Li 2008) in line of Alg. [ According to the a-stability defined in Definition 2 every element e₁ E [t]. follows this stable distribution: e ~ 22.0,11E " Thus, the le norm can be estimated by calculating
the scale of the distribution 2,,0.1 Mill3 with containing l elements.
During the above processes, u, and Eiemn) u, are not leaked and the aggregation among clients is calculated with only summation. Thus, secure aggregation protocols can be naturally applied with quantization, as will be discussed in Sec. 3.4 and 3.5 Furthermore, & = á log(1 (1))) suffices to guarantee that the second frequency moment can be approximated with a 1 c factor and a probability no less than 1 - 5. We will further analyze the utility of FED-X² x2 in Sec. 3.6
3.4 SECURE FEDERATED CORRELATION TEST
The complete protocol for FED-X² presented in Alg. 2 Firstly, the marginal statistics Ux By and v calculated with secure aggregation and broadcasted all clients (lines 1-6 in Alg. (2. This step can be omitted if the marginal statistics are already known. Then, on the server side, a projection matrix P is sampled from an a-stable distribution 22x. The projection matrix is broadcasted to all clients (lines 8-10 in Alg. 2 For each client c; the local data is re-organized into u, and projected to e, as encoding (lines 11-14 in Alg. 2). Then, the encoding results will be quantized and aggregated with secure aggregation (line 15 in Alg. 2 As we have already known the marginal statistics in the first round, the quantization bound can be set accordingly. Additionally, we can use high precision for quantization, such 64 bits, since the size of the contingency table is normally moderate rather than enormous. Thus, the precision of the quantized float number is comparable to or even better than that of float64, and hence we disregard the effect of quantization on accuracy. Finally, the server gets the x2 -tst result using the decoding algorithm described in Alg. 1 (line 17 in Alg. 2
Dropouts in the first round have no effect on the test's 's accuracy because they can be recovered inside secure aggregation (Bonawitz et al.] [017]] Bell et al. 22200). On the other hand, dropouts in the second round will affect the accuracy of the test. Still, because the x² value is typically far from the decision threshold, FED-X² is intrinsically robust to small portion of clients dropping out (see Section for empirical assessment).
3.5 SECURITY ANALYSIS
As discussed in Sec. the secure aggregation protocol is well studied, and many well-celebrated secure aggregation protocols have been proposed (Bonawitz al., 2017 Truex al. 2019 Xu et al.
2019]So So et al. 202 Bell et al. 2020 Choi et al. (020). In this paper, we choose the state-of-the-an secure aggregation protocol by Bell et al. (Bell et al. 2020), which replaces the complete graph with sparse random graph to enhance communication efficiency. We clarify that FED-x" can incorporate other popular secure aggregation protocols. We now prove the security enforced by Alg. via standard simulation proof process (Lindell 2017) the basis of Theorem I
Theorem (Security). Let II be instantiation of Alg. 2 with the secure aggregation protocol in Alg. of Appendix(HI with cryprographic security parameter There exists a PPT simulator SIM such that for all clients C, the number of clients n, all the marginal distributions (wz) ) (Vy), and all
4

---

Under review as a conference paper at ICLR 2022
the encodings {es}. the ouppu of SIM is indistingurishable from the view of the real server Ie in that execution, i.c. Iee R e.,
Intuitively, Theorem [ illustrates that more information about the clients except the averaged updates is revealed to the centralized server. Thus, each client's update is hidden by the rest clients in secure aggregation. We now present the formal proof for Theorem
Proof for Theorem !
To prove Theorem I we need the following lemma.
Lemma (Security of secure aggregation protocol). Let SECUREAGG be the secure aggregation protocol in Alg. of Appendix instantiated with cryprographic security parameter X. There exists probabilistic polynomial-time (PPT) simulator SIMSA A such that for all clients C, the number of clients n, and all inputs X' = heije the output of SIMSA A is perfectly indistinguishable from the view of the real server, ie.. SECUREAGGe = SIMSA (ee] ei, n.)
Lemma Tis derived from the security analysis of employed secure aggregation protocol (Theorem 3.6 in Bell et al. (2020)), which establishes that the secure aggregation protocol securely conceals the individual information in the aggregated result. With this lemma, we able to prove the theorem for federated -e-test by presenting a sequence of hybrids that begin with real protocol execution and end with simulated protocol execution. We demonstrate that every two consecutive hybrids are indistinguishable. illustrating that the hybrids indistinguishable according to transitivity.
HYB, This is the view of the server the real protocol execution, REALC.
HYB2 In this hybrid, replace the view during the execution of each SECUREAGG( (v)) in line 3 of Alg. 2 with the output of SIMS (MM, n) one by one. According to Lemma each replacement does not change the indistinguishability. Hence, HYB, indistinguish- able from HYB1.
helm))
HYB3 Similar to HYB2, we replace the view during the execution of each SECUREAGG( (fu (uy (2)
he((n) in line 4 of Alg. 2 with the output of SIMSA(U, n)
one by one. According to Lemma[] HYB3 is indistinguishable from HYB2-
HYB4 this hybrid, we replace the view during the exccution of SECUREAGG( ((ee) (ee))) in line of Alg. with the SIMSA e,,, n). This hybrid is the output of SIM. According to Lemma I H HBB. is indistinguishable from HYB3-
Remark: what does Alg. 2 leak? By Theorem I show that individual updates of clients
perfectly hidden in the aggregated results and FED-X leaks no more than a linear equation system:
e
JI JI.my x VT
Ji JI,m, x V
Algorithm 2: FED-X2: secure federated -testt SECUREAGG is remote procedure that re-
ceives inputs from the clients and returns the summation to the server. INITSECUREAG is the corresponding setup protocol deciding the communication graph and other htype-ppaameeter
Round 1: Reveal the marginal statistics INITSECUREAGG (n)
// is the client number.
for [mz] do Uz SECUREAGG ( ful )<e(s)
for E [my] do vy SECURBAGS (f }E())) Server
Calculate v Σn Vi and broadcast v, (uz) and [uy] to all the clients.
Round Approximate the statistics
Server
Sample the projection matrix P from @xxm
10
Broadcast the projection matrices to the clients
Client C,, [n]
12
Calculate Uxy
13
Prepare u: s.t. u. [I v)]
was Ray/n
Pay
14
Calculate e; EXCODE (P, 4:)
15
e= SECUREAGE (QUANTERE (fe))s(())
16
Server
17
5,a DECoDE (e)
5

---

Under review as a conference paper at ICLR 2022
where J1,m, and Ja,m, are 1 my and My unit matrices, V is an my x my matrix whose elements are { and v a vector flattened by V. To understand this, information leaked by FED- x" includes the estimation and marginal statistics Va and Vy- The following theorem establishes an important fact: the above equation system has exponentially large solution space, which effectively conceals the real joint distribution. We thus believe that Alg. 2 practically ensures privacy due to the solution space's vastness.
Theorem Given a projection matrix P E E Zfx'm {U2), {8y} and e, there are least q" f-m ma my feasible choices of {Vay}.
Proof sketch for Theorem 2 As demonstrated above, the given information forms linear equation with My + My + l equations. Given m > my + My + É, the rank of the coefficient matrix is no more than my + My + l. Solving the equations with Smith normal form, we know that the solution space is at least (m my my dimeennsio. With the following lemma, we manage to prove Theorem 2
Lemma 2. There are xe vectors in the subspace of Z
3.6 UTILITY ANALYSIS
In this section, we conduct the utility analysis in terms of multiplicative error. We show that the output of FED-X2, 8x2, is fairly accurate approximation (parameterized by e) to the correlation test output 8x2 in the standard centralized setting with high probability parameterized by 8.
Theorem (Utility). Ler II be an instantiation of Alg. 2 with secure aggregation protocol in Alg. 4 of Appendix [ 11 is parameterized with & = -t log(1, 1 for some constant c. After executing llc on all clients C. the server yields 822, whose distance to the accurate correlation test output 8x2 is bounded with high probability as follows:
P|.y2 < (1 c)8²² V > (1 c)
Proof sketch for Theorem 3
First, we introduce the following lemma from 2008
Lemma 3 (Tail bounds of geometric mean estimator mean estimator is:
Li 2008)). ) The right tail bound of geometric
P(š - 8 6s < exp(-e 2
GR
where Gn
Ci log + Cine(a
log lo - sin (Ta()))))) a = in our
setting, C1 2 tan
log(l-e) and 7e = 0.577215665... is the Euler's constant.
(1440")4/6)
The left tail bound of the geometric mean estimator is:
P(š 8,2 < -c8,a) S exp(
GL
where > to ( [(
C2 log(1 - t) log( 21 [ + C2) sin( =a(a))
Ty 1o sin ( and C2 1/ 32
C2 log( T
With Lemma Taking 2 max(Gn, Gz) and 5 exp( k2), we are able to prove Pp5y²
(1 - e)sx² V (1+ +)s s and the above bound holds when = & log(1/5).
3.7
COMMUNICATION & COMPUTATION ANALYSIS
In this section, we present the communication and computation cost of Alg.
Theorem 4 (Communication Cost). Let II be instantiation of Alg. with secure aggregation protocol in Alg.
Alg.Aor Af Appendix H then (I) the client-side communication cost is O n + m2
my + E); (2) the server-side communication cost is O(n log n + nm,, -my + nzE).
Theorem (Computation Cost). Let IT be an instantiation of Alg. with secure aggregation protocol in Alg. of Appendix then (1) the client-side computation cost Olog² n (e mm+ myy) log n-
mé); (2) the server-side computation cost is O(n log² + re(E + m2 + my) log + f).
Note that compared with the original computation cost presented in (Bell et al. 2020). the client-side overhead has extra O (ml)) term. This term is incurred by the encoding overhead. We also give empirical evaluation on the client-side computation overhead in Sec. 4.1 S.c. Please refer to Appendix for the detailed proof of Theorem 4 and Theorem

---

Under review as a conference paper at ICLR 2022
4 EVALUATION
Experiment Setup. To assess FED-X²'s accuracy, simulate it four synthetic datasets and 16 real-world datasets. We compare the multiplicative errors of FED-X² with that of the standard centralized -e-test. The four synthetic datasets are independent, linearly correlated, quadratically correlated, and logistically correlated. As the real-world datasets, we report the details in Appendix [
Additionally, evaluate FED-x22s utility in three real-world application scenarios: 1) feature selection, 2) cryptanalysis, and 3) online false discovery rate (FDR) control. For feature selection, we report the model accuracy trained on the selected features. For cryptanalysis, we report the success rate of cracking ciphertexts. For Online FDR control, we report the average false discovery rate. We compare the performance of FED-X² with that of the centralized x²-test in each of the three experiments. Unless otherwise specified, experiments are launched on an Ubuntu 18.04 LTS server equipped with 32 AMD Opteron(TM) Processor 6212 and 512GB RAM.
4.1 EVALUATION RESULTS
Erroc no dropouut
Error 5% drepout
ACC no dropout
ACC. of 5% dropout
Moliphizaive afC
Mukiplicztie Envor NCC
Muliphcztive Tiner XCC
XCC
0.8
0.6
Mokiphicatie Envor
0.3
0.0
0.6
0.1-
0.4-
0.4
100
150
750
50
100
1.50
1000
100
1.50
200
50
100
150
(a) Synthetic Data I.
(b) Synthetic Data
(c) Synthetic Data 3.
(d) Synthetic Data
Mulipiicaive Erver a
Muligiictire Enoor FCCC
Moliplicatne ACC
Malipiicatic ACC
0.8
0.5
0.
0.G
b.G
0.6
0.8
02
0.2
0.2
10
(e) Data
Data 2.
(e) Data
Data 4.
Maliyiicthe a
Sttt Exoox 1CCC
Valliiizanee Drve ADC
0.6
0.8
0.6
Mahijlicatre Earoe
0.5
0.5
0.4
0.4
0.4
0.4
02-
0.2
150
230
50
100
150
100
1.C
200
50
100
155
(i) Data
(j) Data
(k) Data
(1) Data
Multilicatve ACC
Mottpiicaive Exox c ARCC
Moltelicatte Cr ADC
Malliiizztive 1ACC
0.6
0.8
0..
0.6-
06:
0.6.
0.6
0.2
02-
0.2
0.2-
100
100
230
50
1001
150
200
300
150
210
20
40
50
(mx)
9.
(x)
(p) Data 12.
Muliplicaine Emro LACC
Mhttppoutte Enoor <ACC
Shilppicatee Liorr ACCC
Malippicatie Emoor AACC
DUB
0.6
0U6
0.4
0.4
0.4
0.2
0.2
0.2
0.
Encoding size
Encoding size
Ennoddng size
Escoding size
(q) Data 13. Figure I: Multiplicative error and accuracy FED-X w.r.l. encoding size f w/ and w/o dropout.
(c) Data 14.
(5) Data 15.
(1) Data 16.
Accuracy. We begin by evaluating the accuracy of FED-X2, as illustrated in Fig. I Each point represents the mean of 100 independent runs with 100 clients, while the error bars indicate the standard deviation. We choose m2 = my = 20 in this experiment. Note that the accuracy drop is independent of the number of clients.
7

---

Under review as a conference paper at ICLR 2022
From Fig. | we observe that the larger the encoding size e, the smaller the multiplicative error. When = 50, the multiplicative error e =e 0.2. This conforms with Theorem in which the multiplicative emoor c = v (1 decreases increases.
We also evaluate the power (Cohen 2013) of FED-X². We set the p-value threshold as 0.05, which determines whether or not to reject the null hypothesis. From The dashed lines in Fig. [ we can tell that the power of FED-X² is high. This conforms with our observation on the multiplicative errors. Specifically, since the x² values typically far from the decision threshold, multiplicative error of 0.2 rarely flips the final decision.
We also present the results when 5% of clients drop in the second round of FED-X y2 in Fig. The results show that FED-X² is robust to a small portion of dropouts. In Appendix results in terms of 10%, 15%, and 20% dropout rates.
we present the
Client-side Computation Overhead. To assess extra computa- tion overhead incurred by FED-X² on the client side, we measure the execution time of the encoding scheme on an Android 10 mobile de- vice equipped with a Snapdragon865 CPU and 12GB RAM. We use PyDroid (Sandeep Nandal (0200) to run the client-side computation of FED-X* on the Android device.
Avg. Encoding Time (ms)
40
20-
10-
The results are shown in Fig. 2 Each point represents the average of 100 separate runs, with accompanying error bars. The overhead is generally negligible. For example, for 500 x 500 contingency table, the encoding takes less than 30ms. The overhead grows línearly in relation to my (myy and consequently quadratically in Fig. 2 where m, equals my-
300
500
my (mly)
Figure 2: Client-side encoding overhead when my my-
4.2 DOWNSTREAM USE CASE STUDY
Feature Selection. Our first case study explores secure federated feature selection using FED-X?. The setting is that each client holds data with a large feature space and wants to collaborate with other clients to rule out unimportant features and retain features with top- highest x² scores. We use Reuters-21578 (Hayes & Weinstein 1990), standard text categorization dataset (Yang) 1999; Yang & Pedersen 1997 Zhang & Yang 2003), and pick the top-20 most frequent categories using 17,262 training and 4,316 test documents. These documents are distributed randomly to 100 clients, each whom receives the same number of training documents. After moving all numbers and stop-words, we obtain 167,135 indexing terms. After performing feature selection using FED-X2, select the top 40,000 terms with the highest x² scores. When compared with the centralized tettest, 38,012 (95.03%) of the selected terms are identical, indicating that FED-X² produces highly consistent results with the standard =testt
80
Model Accuracy (56
70-
60
feature selection
FED-x no drupout
HED-y 10% dropont
50
FED-y" 201 dropout
centralized x cess
40
30
60
90
120
150
Epoch
Figure 3: Accuracy of the model trained with features selected by FED-X² and centralized -test.
We then train logistic regression models using the terms selected by FED-X2 and the centralized -tttt respectively. All dlyper-paramee Appendix K The results in Fig. further demonstrate that FED-X² exhibits comparable performance with the centralized -test. When 10% and 20% of clients dropout in the second round of FED-X the accuracy of the trained model using the features selected by FED-X² does not drop much. We also examine performance without feature selection, and as expected, model accuracy is significantly greater after feature selection. Note that the model without feature selection has 2,542,700 more parameters than the model with feature selection. Hence, feature selection effectively improves model accuracy while reducing model size and computational cost.
are the same. The details of these models are reported in
Cryptanalysis. In the second case study, we explore federated cryptanalysis with FED-X2. 2 We break Caesar cipher (Luciano & Prichett 1987). classic substitution cipher, with FED-X In Caesar cipher, each letter in the plaintext is replaced by another letter with some fixed number of positions down the alphabet. For instance, each English letter be right-shifted by three, converting
8

---

Under review as a conference paper at ICLR 2022
the plaintext "good" to the ciphertext "jmn".. There are 26 possible shifts when given 26 English letters. The plaintext can be cracked in a shortcut by performing a correlation test on the ciphertext in relation to normal English text.
In our setting, each client is assumed to possess a segment of the Caesar ciphertext. To collaboratively crack the ciphertext, these clients run 26 x²-tests to determine the correlation level between each ciphertext letter and the letters in normal English text. The - yielding the highest correlation level elucidates how English letters are encrypted into Caesar ciphertexts.
Correct Rate (5)
95.
90
no dropout
10% drepout
20% dropout
We take Shakespeare's lines as the plaintext and encrypt it into a Caesar ciphertext with length of 1000 characters. We initiate the cracking process on ten non-overlapping ciphertexts to compute the average success rate (see Fig. 4. In general, the larger the encoding size, the more precise the x -statistiis is, and consequently the higher the success rate. Again, according to Theorem 3] the multiplicative error decreases as the encoding size increases. In Fig. rate when 10% and 20% clients dropout in Round two of FED-X" respectively. Even if 20% of clients dropout, the success rate can still be 100% long the encoding size E is larger than 20.
Encoding Size
Figure 4: The success of cracking Caesar ciphers.
we also report the success
Online False Discovery Rate Control. In the third case study, we explore federated online false discovery rate (FDR) control (Foster & Stine 2008) with FED-X2. In an online FDR control problem, a data analyst receives stream of hypotheses on the database, or equivalently, stream of p-values: P1, P2, data analyst should pick a threshold a to reject the hypothesis when Pe 04. The error metric is the false discovery rate, and the objective of online FDR control to ensure that for any time t, the FDR up time l is smaller than pre-determined quantity.
20
no dropout 10% dropout
15-
20%6 dropout
FDR (5)
10
At each time t, the
10
50
100
200
250
300
Encoding Size
We use the SAFFRON procedure (Ramdas et al. 2018), the state-of- the-art online FDR control, for multiple hypothesis testing. The x2 results and corresponding p-values are calculated by FED-X2. We present the detailed algorithm of SAFFRON and the hyper-parameters used in our evaluation in Appendix L The size of the randomly synthesized contingency table is 20 x 20. Each time, there are 100 independent hypotheses, with a probability of 0.5 that each hypothesis is either independent or correlated. The time sequence length is 100, and the number of clients is 10. The data are synthesized from a multivariate Gaussian distribution. For the correlated data, the covariance matrix randomly sampled from uniform distribution. For the independent data, the covariance matrix is diagonal, and its entries are randomly sampled from a uniform distribution.
Figure 5: Average FDR w.r.t.
for SAFTRON with FED-X?.
At time t, we FED-X² to calculate the p-values pr of all the hypotheses, and then use the SAFFRON procedure to estimate the reject threshold a using Pt. The relationship between the average FDR and encoding size f is shown in Fig. ( We observe that the variance of independent runs is very small, so we omit the error bars. The results indicate that by increasing the encoding size f, FED-X² can achieve low FDR of less than 5.0%. We also observe that dropouts improve the performance of FED-X² in this case study. The reason for this is because dropouts reduce the estimated x² value, which increases the probability of accepting the null hypothesis in FED-X2. As larger portion of queries follows the null hypothesis in online FDR control, the accuracy also increases. The results further demonstrate that FED-X² can be employed in practice facilitate online FDR control using a secure federated correlation test.
5 CONCLUSION
This paper takes an important step towards designing non-linear secure aggregation protocols in the federated setting. Specifically, we propose a universal secure protocol to evaluate frequency moments in the federated setting. We focus formal security proof and utility analysis on our proposed secure federated learning x 2test protocol FRD-X2 and validate them with empirical evaluations and case studies.
important application of the protocol: x" -test. We give

---

Under review as a conference paper at ICLR 2022
REFERENCES
Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and H Brendan Mcma- han. epsgd: Communication-efien effricient and differentially-priee priivat distributed sgd. arXiv preprint 1rXiv:/805.10555 2018.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2938-2948. PMLR, 2020.
James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1253-1269, 2020.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. International Conference on Machine Learning, pp- 634 643. PMLR, 2019.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175 1191, 2017.
Elette Boyle, Kai-Min Chung, and Rafael Pass. Large-scale secure computation: Multi-pan Multi-party computation for (parallel) ram programs. In Annual Cryptology Conference, pp. 742-762. Springer, 2015.
Yu Chen, Fang Luo, Tong Li, Tao Xiang, Zheli Liu, and Jin Li. A training-integrity privacy-preserinng federated learning scheme with trusted execution environment. Information Sciences, 522:69-79, 2020.
Beongjun Choi, Jy-yong Sohn, Dong-Jun Han, and Jackyun Moon. Communication-computttio efficient secure aggregation for federated learning, arXiv preprint arXiv:2011205433, 2020.
Jacob Cohen. Statistical power analysis for the behavioral sciences. Academic press, 2013.
Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Annual Cryptology Conference, pp. 643-662. Springer, 2012.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL BtLt:t//tachhii ics uci.uci... eddu/uu
Sandrine Dudoit, Juliet Popper Shaffer, Jennifer C Boldrick, et al. Multiple hypothesis testing in microarray experiments. Statistical Science, 18(1):71-103, 2003.
Dean P Foster and Robert Stine. a-investing: a procedure for sequential control of expected false discoveries. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(2):
2008
Govindaraj. Praveen. Credit Risk Classification Dataset: Is Customer Risky or Not Risky ? https
www..kagggla , http://wwwgggo//eerttttreeeeeeee www.-iilaassiiaatiiiaa...aaaaaae cetettiionnntttsste Online; accessed 22 April 2021.
Philip J Hayes and Steven Weinstein. Construe/tis: system for content-basee indexing of database of news stories. In IAAI, volume 90, pp. 49-64, 1990.
Sebastian Houben, Johannes Stallkamp, Jan Salmen, Mare Schlipsing, and Christian Igel. Detection of traffic signs in real-world images: The German Traffic Sign Detection Benchmark. In International Joint Conference on Neural Networks, number 1288, 2013.
Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53(3):307-323, 2006.
10

---

Under review as a conference paper at ICLR 2022
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. arXiv preprint arXiv:2102.06387, 2021.
Jerome Kassirer. Teaching clinical medicine by iterative hypothesis testing: let's preach what we practice, 1983.
Jae H Kim and Philip Inyeob Ji. Significance testing in empirical finance: A critical review and assessment. Journal of Empirical Finance, 34:1-14, 2015.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pp. 202-207, 1996.
Kohavi, Ronny and Becker, Barry. UCI Machine Learning Repository: Adult Data Set. https Online; accessed 22 April 2021.
//archive. http:///cccccccce///////////aa /dtataattttttttadltttt Ltt.
Kononenko, Igor and Cestnik, Bojan. UCI Machine Learning Repository: Lymphography Data Set.
httpss:/aarchii seseiiccs... uci wtt.://i....ccaaa/ataaaatttt//pr Online; accessed 22 April 2021.
Oliver Ledoit and Michael Wolf. Robust performance hypothesis testing with the sharpe ratio. Journal of Empirical Finance, 15(5):850-855 2008
Ping Li. Estimators and tail bounds for dimension reduction in (0 < S 2) using stable random projections. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 10-19, 2008.
Yehuda Lindell. How to Simulate - A Tutorial on the Simulation Proof Technique, pp. 277- 346. Springer International Publishing, Cham, 2017. ISBN 978-3-319-570MM doi: 1007/ 978-3-319-57048 8 6. URL https::s: /00 3-1-778----11------------------- 6.
1007
Dennis Luciano and Gordon Prichett. Cryptology: From caesar ciphers to public-key cryptosystems. The College Mathematies Journal, 18(1):2-17, 1987.
Kaisa Nyberg. Correlation theorems in cryptanalysis. Discrete Applied Mathematics, 111(1-2): 177-188, 2001.
Aaditya Ramdas, Tijana Zrnic, Martin Wainwright, and Michael Jordan. Saffron: an adaptive algorithm for online control of the false discovery rate. In International conference on machine learning, pp. 4286-4294. PMLR, 2018.
Sandeep Nandal. PyDroid. httpss//ppph..rr/ppppetttt/pp/pp cessed 24 April 2021.
2020. Online; ac-
Schlimmer, Jeff. UCI Machine Learning Repository: Mushroom Data Set. https://archive
ics. wci. htt.a/eee......aaattttee/ttaaaae
Online; accessed 22 April 2021.
Jinhyun So, Başak Güler, and A Salman Avestimehr. Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning. IEEE Journal on Selected Areas in Information Theory, 2021.
Pater Spirtes, Clark Glymour, Richard Scheines, Stuart Kauffman, Valerio Aimale, and Frank Wimberly. Constructing bayesian network models of gene expression networks from microarray data. 2000.
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach to privacy-pree prenecriprenningggg federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pp. 1-11, 2019.
Santosh S Vempala. The random projection method, volume 65. American Mathematical 2005.
Lun Wang, Ruoxi Jia, and Dawn Song. D2p-fed: Differentially private federated learning with efficient communication. arxiv. org/pd//2006./33 10006./3333 /3039, 2020.
Lun Wang, Iosif Pinelis, and Dawn Song. Differentially private fractional frequency moments estimation with polylogarithmic space. arXiv preprint arXiv:2 10..2105.22..... /2363, 2021.

---

Under review as a conference paper at ICLR 2022
R Bryce Wilson, Dana Davis, and Aaron P Mitchell. Rapid hypothesis testing with candida albicans through gene disruption with short homology regions. Journal of bacteriology, 181(6):1868 1874, 1999.
Runhua Xu, Nathalie Baracaldo, Yi Zhou, Ali Anwar, and Heiko Ludwig. Hybridalpha: An efficient approach for privacy-preserving federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pp. 13-23, 2019.
Yiming Yang. An evaluation of statistical approaches to text categorization, Information retrieval, 1 (1):69-90, 1999.
Yiming Yang and Jan Pedersen. A comparative study on feature selection text categorization. In Icml, volume 97, pp. 35. Nashville, TN, USA, 1997.
Jian Zhang and Yiming Yang. Robustness regularized linear classification methods in text categorization. In Proceedings of the 26th annual international ACM SIGIR conference Research and development in informaion retrieval, pp. 190-197, 2003.
Zhaohui Zheng, Xiaoyun Wu, and Rohini Srihari. Feature selection for text categorization imbalanced data. ACM Sigkdd Explorations Newsletter, 6(1):80-89, 2004.
APPENDIX
A CLARIFICATION ON PRIVACY
As indicated Sec. 2 the projection matrix is public information, and hence FED-X² does not take the differential privacy guarantee into account. We would want provide more information in order to eliminate any potential misunderstandings.
To begin, would want to emphasize that "privacy" in our paper refers MPC-style privacy, not DP-style privacy. In general, MPC-style privacy is orthogonal to DP-style privacy: in MPC, privacy obtained against semi-honest server in such way that the server cannot witness individual client's 's updates but only an aggregate of them, e.g. SecAgg (Bonawitz et al., 2017). In DP, privacy accomplished by including random noise in each client's update, such that the distribution of the output result does not reveal the clients' private information and the server cannot infer the clients' identification from the output result.
Second, we would like to emphasize that our work proposes a novel secure aggregation scheme particularly for the -test. Existing standard secure aggregation schemes are inapplicable to the -tett, which will reveal much more information than FED-X², as we have clarified in Sec. Again, this work requires guaranteeing MPC-style privacy, not DP.
Third, to quantify MPC-style privacy, we prove in Theorem hidden inside space with exponential size. This is weaker than hiding users' updates the whole space, but still gives meaningful privacy guarantees (consider attempting to guess the output of an exponential-sided dice, which is practically infeasible).
2 that the clients' updates in FED-X are
Finally, while DP is orthogonal to this research, we would want to emphasize that our protocol can achieve DP by introducing calibrated discrete Gaussian noise to the users' local updates.
B COMPARISON WITH POOLING 2
We also compare the performance of FED-X² with pooling x2 2-tsst. That is, the clients compute the x" 2-tesst with their local observations and then they aggregate their test results by pooling. The result of the pooling x² 2-test is determined by the majority of the clients' local results. Fig. shows the result of pooling x" -test on the real-world datasets. The details of the datasets are presented Appendix We observe that pooling x --tttt cannot give meaningful results and it tends give judgement that the data is independent since that the numbers the local observations are not sufficient to make correct judgement. The results further demonstrate the effectiveness and the necessity of FED-X?.
12

---

Under review as a conference paper at ICLR 2022
Error of FED-X²
ACC of FED-X
ACC of pooling -
Malipliatio Enver NCC.
Miltpllative Entor ACC
Maliplicato Eimer MCCCC
Maliplicatie NCC
0.4
63-
0.2
0.3-
20
101
100
10c
200
50
100
100
Data
(c) Data
4.
Mutiplictte Entor Enor FCC
Mokiphictte Enore NCC
Muliplizaiee Enor
0.8
0.8
Mukppiaate Timer
01.
0.5
0.6
0.-
066
0.6
0.4
0."
0.4
0.4
0.2
02
0.2
0.2
150
150
10
100
150
100
150
700
50
(c) Data
(f) Data 6.
(8)
Data
(h) Data 8.
Motipicattre Eborr ACCC
Mukipicattee Emmre AOC
0.8
Mobijlicaive Eime
0.0
Mulipiizaiee
0.4-
0.4
0.2
02
0.2
0.8
0
50
100
150
2.00
50
100
150
200
50
100
130
210
20
10
50
(i) Data
(j) Data 10.
(k) Data 11.
(1) Data 12.
Multpiicative Eavor NCC
0.5
0.8
Moltipicatte Dever
08.55
0.5
0.6-
04-
0.6
0.6-
Mulipiicatvee
0.4
0.4
0.4
02-
0.2
10
10
10
Encoding sine
Eacoding size 2
Unnedinng size
Emnoodnng sine
(m) Data 13.
(n) Data 14.
(0) Data 15.
(p) Data 16.
Figure 6: Comparison between FED-X2 and pooling x² -test
C PERFORMANCE OF FED-X2 2 WHEN ORIGINAL X2 -TEST ACHIEVES Low POWER
We have computed the multiplicative error and accuracy of FED-X² with the original centralized x² -t-test as the baseline. To further demonstrate the effectiveness of FED-X², we also set up the experiment to evaluate the performance of FED-X² on the synthesized dataset when the accuracy of the original centralized xtttest is lower. More specifically, we synthesize the random independent, linearly correlated, quadratically correlated, and logistically correlated datasets with the same hyper- parameters for 20 times. We then compute the accuracy of the original centralized x²-test over these 20 datasets. We report the results in Fig. 7 The results show that FED-X? can still achieve good performance the datasets when the original centralized x = 's accuracy is lower. Consistent with our results in Sec. 4.1 the multiplicative error becomes lower with the increase of the encoding size 1. Thus, conclude that FED-X 's performance is comparable that of the original centralized 2test with an appropriate encoding size I and this is not dependent on the datasets.
Ersor of FED-X²
ACC of FED-X2
ACC centralized x² -tstt
Multplicaive Emer ACC
Stutpllcattve Elvor ACC
Mitoplicttoo Emer ACC
0.5
08
0.8
Stutopiccatre Emerr
0.5
0.6
0.4
0.4
0.4
0.2
022
0.2
0.2
100
150
220
20
100
120
200
30
100
15c
21g)
50
100
120
350
Ensoding sinc
Enxxding siaze
Enceding size
Emssiing sinc
Synthetic Data
(b) Synthetic Data
Synthetic Data 3.
(4) Synthetic Data
Figure 7: Performance of FED-X 2 when original 2 achieves low accuracy.
13

---

Under review as a conference paper at ICLR 2022
D FURTHER RESULTS FOR ONLINE FDR CONTROL
In this section, we provide further results for online FDR control.
As we have shown in Fig. 5 FED-X² achieves good performance
FDR /TD (56)
80
(FDR lower than 5%) when the encoding size is larger than 200.
+HOR of HRD-y."
In Fig. we provide the FDR result of the original x²ttest as well as the true discovery rate (TDR, i... #correct reject/ #should reject).
TDR of PRB-X
10
FDR of centralized x--test
IDR of centralized --esst
In addition, we provide statistics for each encoding size that was evaluated in Table 1 These results demonstrate that FED-X² per- forms well and comparable to the centralized x²-test when the encoding size / is increased. More importantly, in Sec. 4.1 and Appendix C centralized -test and this is independent from the data.
20
10
50
100
150
200
200
300
have shown FED-X² gives results close to original
Encoding Size
Figure 8: Results of FDR & TDR.
#should reject
#should accept
#correct reject
#false reject
FED-X /
10
5,900
4,100
5,544
1,132
FED-X 25
5,900
4,100
5,871
1,022
FED-x 50
5,900
4,100
5,899
856
FED-X x1=x 100
5,900
4,100
5,900
606
FED-X 150
5,900
4,100
5,900
411
FED-X
1 200
5,900
4,100
5,900
335
FED-
= 250
5,900
4,100
5,900
270
FED-X 300
5,900
4.100
5,900
202
centralized x²-test
5,900
4,100
5,900
Table 1: Detailed results of online FDR control.
To further demonstrate that the close performance of FED-X2 and the original centralized 2 is independent of the data, we use a similar approach descrihed in Appendix Coo generate the data that
100
FDR TDR (56
the original centralized x -test struggles to distinguish its correlation (i.e., resulting higher FDR). To achieve this, we change the co-
-+
-+H of FED-x?
TDR of Pin-x"
40
FDR of centralized 2eesst
TDR of centralized Fesst
variance matrix of the Gaussian distribution when generating the independent and dependent data. The detailed results are shown 2 and in Fig. 9 The original centralized x² -tete achieves an FDR of 7.03% and TDR of 89.73%. The results indicate that when the encoding size 1 is increased, the performance of FED-Xx gets closer the original centralized x--test. When 300, FED-X2 performs similarly to the original centralized x² -test. The results in Fig. aadd Table consistent with those in Appendix[[] indicating that the performance of FED-X² is comparable to that of the original centralized -test when the encoding size is set appropriately, and that this is independent of the data.
50 10
100
150
200
200 300
Encoding Size
Figure 9: Results of FDR & TDR when the FDR of the original cen- tralized "test is higher.
#should reject
#should accept
#correct reject
#false reject
FED-X 7
10
5,900
4,100
5,144
1,392
FED-X /
5,900
4,100
5,328
1,356
FED-X 50
5,900
4,100
5,325
1,143
FED-X 1 100
5,900
4,100
5,398
943
FED-X 2 150
5,900
4,100
5,393
765
FED-X 200
5,900
4,100
5,377
687
FED-X 250
5,900
4,100
5,328
615
FED-X x 300
5,900
4,100
5,361
556
centralized -tes
5,900
4,100
5,294
408
Table 2: Detailed results of online FDR control when the FDR of the original centralized x² 2test higher.
E INCORPORATE GAUSSIAN MECHANISM IN FED-X2
As have mentioned in Appendix FED-X² can achieve differential privacy easily by incorporating stulist differentially private mechanisms. To further demonstrate this point, we utilize Gaussian Mechanism provide (c, 5)DP guarantee. We clipped the local clients' data such that the encoding
14

---

Under review as a conference paper at ICLR 2022
function's s sensitivity, which is the L2-norm of the clients' local data is bounded by Af- Before encoding their local data, each client add Gaussian noise (0, o²) to their local data vector A4s We can calculate o² 2lo (5/1.25/8)//1" After encoding and decoding with the computed vector, FED-X²
n(c/))
provides (c, 6) DP guarantee.
We evaluate the performance of differentially private FED-X² on the first four wolld datasets
adopted in this research as shown in Fig. [T] We choose encoding size | = 10 and = 0.01. The results show that the performance our algorithm becomes better with the increase of privacy budget e. However, when the privacy budget is small, the protocol tends to give the judgement that the data independent because that the independent noise too large and dominates the test. When the privacy budget is large enough (i.e., 100), our protocol can achieve 0.92, 0.68, 0.70, and 0.80 accuracy on these datasets accordingly, and its performance is comparable to the original FED-Xx.
Again, our work is orthogonal to differential privacy, thus we leave it as future work to further study saving privacy budget, and boosting the algorithm's 's performance on lower c.
20.
107
107
20F
.0F
Maltlliaate Envor
007
Maltppicatt Drver
107
104
208
Maltyticative
-07
207
102
.0F
166
10-1
10-1
10
10
201
13
107
107
10
Privscy
Privacy budgett
Privary budget
Data
Data 2
(c) Data
4.
Figure 10: Performance of FED-X when incorporating Gaussian Mechanism.
F FURTHER RESULTS FOR FEATURE SELECTION
Common Feature Ratio (%)
Our results in Sec. paragraph Feature Selection, demonstrate that FED-X² performs well when encoding size / 50. We conduct experiments with different encoding sizes / to further assess their effect FED-X FED-X2's performance. In Fig. 11 present the effect of encoding size on the ratio of the commonly-selected features between the original centralized x and FED-X?. A larger ratio of commonly--elected features means that FED-Xx performs more closely the original centralized -tste And if the ratio these two algorithms select the identical features. The results in Fig. TT show that when the encoding size increases, the performance FED-X² approaches that of the original centralized -test.
95
90
85
80
75 10
35
Encoding Size f
Figure 11: Ratio of commonly- selected fcatures between FED-X and original centralized X =tttst
Similar to Sec. 4.2 the model with the features selected by FED-X2. Fig. 12 shows the results. When trained with FFD-x--selected features, the model achieve comparable accuracy to the model trained with features selected by the original centralized x²-test. Also, consistent with
we evaluate FED-X2's performance by training
80
Model Accuracy
70
feature selection
60
FED ! 50
FED-X ! 35
FED-It.
the results in Fig- in Sec. 4.2 we see that when the encoding size I 2 25, models trained by FED-X2 2-selected features achieve higher accuracy than that of the models without feature selection. These results further demonstrate the effectiveness of FED-X2.
50-
PRiD-y.,1 10
centralizedd 2-tsst
40
150
Epoch
Figure 12: Accuracy of model
trained w/ FED-X" "reD-x--eeccct -elccct features under different encoding size
G FURTHER RESULTS ON FED-X2 WITH DROPOUTS
We present the results of 10%, 15%, and 20% clients dropout in Fig. 13 The results further show that FED-X2 2 can tolerate considerable portion of clients dropout in Round 2 of Alg.
15

---

Under review as a conference paper at ICLR 2022
Forur dmpoot
15% dropese
20% deppest
ATCC drepore
deepout
Maliglicaine LCCC
Malipiicate Erook ACC
Maliglicaine Drvee ACC
Maliglicatee ACCC
0.8
0.6-
016
0.0
0.4
0.4
0.4
0.4
0.2
150
(1) Synthetic Data I.
(b) Symthetic Data 2.
(c) Synthetic Data 3.
(d) Synthetic Data 4.
Maliyicatiee of ACC
ARCC
Malppiicane Cf ADC
Maliflictnee .AACC
0.6
0.8
0.6
0.0
06
0.4
0.4
0.4
0.3
0.9
0.8
0.3
100
100
220
20
61
50
50
100
100
1.00
210
00
100
100
230
(e)
(g)
4.
Malyltcustee Eiive of ACC
Maltpiicativ Cene ACC
Muliyliaiiee Eine
0.2
0.6-
0.60
Maliplicuskee
0.6
0.4
0.4
0.4
0.4
50
100
150
15C
(1) Data S.
(j) Data 6.
(k) Data 7.
(1) Data 8.
Mulipiiatie ACC
stutplicateee Eiver ACC
Mittyliatoo Limer of ACC
Muliiplictine Fareer ACC
0.6
08:8
0..
0.5
0.6-
0.4
0..5
0.4
0.6
0:2
0.2
00
100
100
250
20
1001
1:0
2000
500
100
100
210
20
10
50
(11) Data 9.
(n) Data 10.
(0) Data 11.
(p) Data 12.
Munipicatte Erace INCC
Munplicane I.CC
Moliglicatve NACC
0.8
0.6
0.5
0.6
0.6
Muliplicaive
0.2
0.2
0.2
0.2
Procdinn sine
Facoding dine 2
Fmocding sizn
Encoding sine
(q) Data 13.
(1) Data 14,
(5) Data 15.
(1) Data 16.
Figure 13: Multiplicative error and accuracy of FED-X x2 w.r.t. encoding size w/ and w/o dropout.
H SECURE AGGREGATION
The secure aggregation protocol from Bell et al. (2020) presented in Alg. The first step of the protocol is to generate a k-regular graph G, where the n vertices are the clients participating in the protocol. The server runs a randomized graph generation algorithm INITŠECUREAGG presented in Alg. 3 that takes the number of clients n and samples output (G, t, k) from distribution D. In Alg. we uniformly rename the nodes of a graph known as Harary graph defined in Definition 3 with yL nodes and & degrees. The graph G is constructed by sampling & neighbours uniformly and without replacement from the set of remaining n 1 clients. We choose = (log(n)). which is large enough to hide the updates inside the masks. t is the threshold of the Shamir's Secret Sharing.
In the second step, the edges of the graph determine pairs of clients, each which runs key agreement protocols to share random keys. The random keys will be used by each party derive mask for her input and enable dropouts.
In the third step, each client c; i Aj sends secret share its neighbors. In the fourth step, the server checks whether the clients dropout exceeds the threshold 5, and lets the clients know their neighbors who didn't dropout.
16

---

Under review as a conference paper at ICLR 2022
In the fifth step, each pair (i.j) of connected clients in G runs X-secure key agreement protocol Si = K.A.Agreeesk, .pk) which uses the key exchange in the previous step to derive a shared random key $i,j. The pairwise masks m = F(si.)) can be computed, where generator (PRG). If the semi-honest server announces dropouts and later some masked inputs of the claimed dropouts arrive, the server can recover the inputs. To prevent this happening, another level of masks, called self masks, r; is added the input. Thus, the input of client 6; is: y, e, + -EjeNo(0) Mij + [)ENo(())> Mi.j.
the pseudorandom
Steps 6-8 deal with the clients dropout by recovering the self masks of clients who are still
active and pairwise masks mij of the clients who have dropped out. Finally, the server can cancel out the pairwise masks and subtract the self masks in the final sum: EiEA, r;
EjENCOANA" Ai) Maj YIENCCOMAAAAAAIKIISII AL),isiin mi.)-
Definition (HARARY ke) Graph). Let HARARY(n, k) denotes a graph with n nodes and degree k. This gruph has vertices V = [n] and an edge between two distinct vertices and j if and only if j - (mod n) S (k: + 1 or (mod n) 2 n k/2.
Algorithm 3: INITSECUREAGG: Generate Initial Graph for SECUREAGG.
Function INItSICURIĀGG (n)
> n:: Number of nodes.
> f: Threshold of Shamir's Secret Sharing.
1: (log(n)).
Let !/ HARARY (n, k).
Sample a random permutation т [n] + [n].
Let G' be the set of edges ((=(i), x()))(()) H}.
return (G, k)
I PROOF FOR COMMUNICATION & COMPUTATION COST
We provide the proof for Theorem 4 and Theorem 5 in the following.
Theorem [Communication Cost). Let 11 be instantiation of Alg. 2 with secure aggregation protocol from Bell et al. (2020), then (1) the client-side communication cost is Olog n+ +y + (2) the server-side communication cost On log + nm, nmy + nE).
Proof sketch for Theorem 4 Each client performs key agreements (O(k) messages, line 9 in Alg. 4
and sends 3 masked inputs (O(m, + my + E) complexity, lines 3, 4, 15 Alg. 2 and line 10 in Alg. Thus, the client communication cost is Oloog n m2 + my + e).
The server receives or sends Olog + my + my + E) messages to each client, so the server communication cost is On log n + nm, nmy + nl).
Theorem (Computation Cost). Let IT an instantiation of Alg. 2 with secure aggregation protocol from Bell et al. 22220), then (1) the client-side computation cost is Om, log n + my log + +n flog n mé); (2) the server-side computation cost Omm + my + E).
Proof sketch for Theorem 5 Each client computation can be broken up as k key agreements (O(k)
complexity, line 9 in Alg. 4 generating masks m.j for all neighbors с (O(k(m, + my ())
complexity, lines 3, 4, 15 in Alg. 2 and line 10 in Alg. 4) and encoding computation cost ((m))
(line 14 in Alg. 2 Thus, the client computation cost is Om, log my log + llog + mé).
The server-side follows directly from the semi-honee computation analysis in Bell et al. (2020). The extra O(E) term is the complexity of the geometric mean estimator.
17

---

Under review as a conference paper at ICLR 2022
Algorithm 4: SECUREAGG: Secure Aggregation Protocol. (Algorithm 2 from Bell et al. (2020))
Function SECURRAGG ((ei)ee())
>> Parties: Clients " Cn. and Server.
> I: Vector length.
> X Input domain, e; EE EX
> F: [0,
X PRG.
> We denote by A1, A2, A3 the sets of clients that reach certain points without dropping out. Specifically A1 consists of the clients who finish step (3), A2 those who finish step (5), and Ag those who finish step (7). For each As, A is the set of clients for which the server sees they have completed that step time.
(1) The server runs (G, I, k) = INITSECURES
(n), where G' is a regular degree-k: undirected graph with n nodes. By Nc(i) we denote the of l nodes adjacent to oj (its neighbors).
(2) Client q; i E [n], generates key pairs (sk),pk)) (ski pk.) and sends ppk) to the server who forwards the message to (o()).
(3) for each Client q, i A do
Generates random PRG seed b;.
Computes two sets of shares:
H [ M.p) Shamir b.)
Hº = {h k = Shamir k; ski))
Sends to the server a message (j, 9.), where Ca2 = Eauth Enc(ksy (ilbb) ( (1hG,))) and kij = KKA.Agrreesss phit), for each Na(i).
(4) The server aborts if | < (1 6)n and otherwise forwards (j. ct.) ( to client oj who deduces A' n (J) (5) for each Client C, E A2 do
Computes shared random PRG seed st as 8t, K.A.Agree(sskt.
Computes masks m,j Fst.)) and r; = F(b.).
Sends to the server their masked input
Σ jEMMIjSi
Σ
y; +r
m +
ma.
jEinl.jzi
(6) The server collects masked inputs. It aborts if [Ab] < (1 6)n and otherwise sends
12
(As U Na(1), (Ai AAb) U No(i)) to every client G, E A/s-
13
(7) Client Cj.J E Ag receives (Ri, R2) from the server and sends
{li, h hen, U (i, h hee obtained by decrypting the ci, received in Step (3).
14
(8) The server aborts if [A4] < 6)n and otherwise:
Collects, for each client c, e A4, the set B; of all shares H& sent by clients in Ag. Then aborts if [B < t and otherwise recovers b, and r, using the t shares received which came from the lowest client IDs.
Collects, for each client c; E (Ai (A)) the set S, of all shares in Hy sent by clients in Ag- Then aborts if |S|| < t and otherwise recovers ske and m.jj.
return ΣiEas (y; r, + + EjeNaannA(1a)) m Esenaenaar4)iess m.,).
DETAILS OF DATASETS
The details for the real-world datasets used in Sec. 4.I are provided in Table 3 The license of Credit Risk Classification (Govindaraj, Praveen) is CC BY-SA 4.0, the license of German Traffic
18

---

Under review as a conference paper at ICLR 2022
Sign (Houben et al. 2013) is CCO: Public Domain. Other datasets without license are from UCI
Machine Learning Repository (Dua & Graff 2017).
Table 3: Dataset details.
Data
Aftr #1
AdI Cat
Attr #2
A#2 Cat
Aduli Income (Kahavii 1996 Kohavs, Ronny and Bocker, Harry"
Occupation
14
Country
Credit Kins Classiscation
Lioaadaara, Pravecn
Feature
14
Feature 7
11
Crodit Risk Classifcation
Govandarat Pravcon
Crodit Type
Overduc Type
35
Credit Kisk Classiscation
Liowndarr, Praveen
Credit Product Type
28
Overdae Type
35
Crvcit Risk Classiication
(ovandaras Fravocn
Ciedit Product
28
Overdue Type
36
German Trallsc Sign (Houben ot al 2015
Inagee Widki
219
Tialinc Sign
German Tratnic Sign
(Huithen of al
A015
Image Height
201
Traffic Sign
43
German Trallic Sigu
(Foollen
Upper Jefl X coordinate
Trallic
German Traffic Sign
(Pouiien et ml 2013
Upper left Y coordinate
16
Trafric Sign
43
German Traffic Sign
[Hiihhen
Lower right coondinate
204
Traffic Sign
43
German Trafiic Sign (1iouben et al
2013
Lower right coordinate
186
Traffic Sign
43
Mustroom (Shilimmer,
Cap Color
10
Odar
Mushroom Schlmmmet
color
12
color above ring
14
Mustaoom (Schlimmer Jel
Stalk color below ring
Ring Type
Mushroom (Scilmnnee,
Spore
Habital
16
Jymphhgriphy (Knnonenko, Igo ai Ceink, Bojon
Stricture Change
8
No. of modes
8
K DETAILS OF REGRESSION MODELS
The details of the regression models trained in feature selection in Sec. 4.2 is reported in Table The training and testing splits are the same for FED-X centralized x²-test and model without feature selection (i.e. there are 17,262 training and 4,316 test documents). We use the same learning rate; random seed and all other settings are also the same to make the comparison fair. We get the result of Fig. 3 and the models are all trained on NVIDIA GeForce RTX 3090.
Table 4: Model details.
Task
Model Size
Learning Rate
Random Seed
FED-X
10000 20
0.1
Centralized X test
40000 20
0.1
Without Feature Selection
167135 x 20
0.1
0
L SAFFRON PROCEDURE
In Sec. 4.2 adopt the SAFFRON procedure (Ramdas al. 2018) perform online FDR control. SAFFRON procedure is currently the state of the arts for multiple hypothesis testing. In Alg. 5 we formally present the SAFFRON algorithm.
The initial error budget for SAFFRON is (1 A W)) < (1 - Aιa), and this will be allocated to different tests over time. The sequence {},)ş= defined by gr and X; serves weak estimation of
az. 9t can be any coordinate wise non-decreasing function (line 8 in Alg. (5) R2 [pp < aay is the indicator for rejection, while C = (p, <x,) is the indicator for candidacy, Tj the jth rejection time. For each pt. if Pt < X₁ SAFFRON adds it to the candidate set C, and sets the candidates after the jthh rejection (lines 9-10 in Alg. 5). Further, the a₁ is updated by several parameters like current wealth, current total rejection numbers, the current size of the candidate set, and so on (lines 11 1--14 in Alg. 5). Then, the decision R2 is made according to the updated a, (line 15 in Alg 5)
The hyper-parameters we use for the SAFFRON procedure in online false discovery rate control of Sec. 4 are aligned with the setting Ramdas et al.] (2018). In particular, the target FDR level is 0.05, the initial wealth is Wo 0.0125, and 7, calculated in the following way: 7 1/(+1)11
100000 1/(/+1)1..
19

---

Under review as a conference paper at ICLR 2022
Algorithm 5: SAFFRON Procedure.
Function SAFFRONPROCEDURE (2,,,2,... ... J. a Wo, {7s )
{P1.P2, ...)))...)).............. }: Stream of p-values.
> a: Target FDR level.
> Wo: Initial wealth.
{?5),=o: Positive non-increasing sequence summing to one. // Set rejection number.
i i<0
for each p-value Pt. E (pI,P2,... " do
A + (1 C1a-1)
O. + [(p < )1)
// Set the indicator for candidacy Cr. // Set the candidates after the jth
Cj+ Ei Ci
rej rejection.
11
then an + -1- W
13
else
0₁ + (1 WoooWoc- + ( - W- + E)22
R& 1 [pr S ar)
// Output Rr.
16
R = then
i it 1
// Update refection number. Set the 7th rejection time.
7+t return
(Ro, Ri,
20


Reviews:
[{"review_id": "sREGrAMEZDs", "reviewer": "Reviewer_sPzq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The algorithm presented in the paper is pretty simple. First, it uses secure aggregation to compute marginal statistics. Each participant applies a stable random projection (with particular parameters) on their (normalized) frequency distribution. The results are then aggregated again using secure aggregation. Due to the nature of the stable distribution, the aggregated result follows a stable distribution as well, and its scale can be estimated. This scale ends up being equal to the squared sum in the correlation coefficient. \n\nOne concern I have is that the protocol actually reveals some significant amount of information to the server in addition to just the result. The authors explain in a remark that this is not a concern, because the leaked information constitutes a linear system (over a finite field) with a large solution space. However, I don't understand if all of these solutions are supposed to be equally realistic or equally likely. For example, realistic solutions may be particularly short vectors, or have some other properties that may make identifying them possible. Does this make it easier to find a solution to the system?", "summary_of_the_paper": "This paper introduces a federated analytics technique for computing the Pearson correlation for two random variables. The method is based on repeated uses of secure aggregation, as well as stable random projections. The protocol is argued to be secure in a semi-honest security model. ", "summary_of_the_review": "This paper presents a nice new federated analytics technique for computing correlations. I have some concerns about the security of the protocol, but it's possible I'm misunderstanding something.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "hBhQWivbknu", "reviewer": "Reviewer_DQ1G", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The algorithm is intuitive and easy to implement, and several possible applications are discussed. \n2. It provides the relationship of the reduced dimension with the test accuracy and the computation cost.\n\nWeaknesses:\n1. In evaluation section 4.1, what is the accuracy of the original chi-square test? If the original test has power 1 in the presented simulation, would we expect a similar comparison with the proposed test when the original test has lower power, such as 0.5?\n2. I don’t fully understand Figure 3. What is an epoch? When computing the accuracy, what is the ground truth?\n3. In the case study of online FDR, could you also show the power (#correctly rejected/ #hypotheses should be rejected)? Although unlikely, I would want to know whether lower FDR as $l$ increase is because the test is conservative and the power is also lower. Could you also include the original chi-square test in this case?\n4. Theoretically, do we know if the FED chi-square test statistics is an unbiased estimation given the original chi-square statistics, or systematically larger or smaller?\n5. As a reader not in the expertise of stable random projection and geometric mean estimator, I don't fully understand why the lower dimensional $e_k$ gets to the approximation.\n", "summary_of_the_paper": "This paper discusses the problem of conducting correlation tests with sensitive data separately collected from $n$ clients, where centralizing data collection is risky but the available secure multiparty computation is costly in computation. The proposed test adjusts the classical chi-square test by first rewriting it as a second frequency moments estimation using $n$ vectors, each from a client. The proposed test prevent data recovering when performing the test by letting each client project its vector to a lower dimension. The higher the dimension is, the more accurate the test is, yet the higher the computation costs.\n", "summary_of_the_review": "Overall I think the proposed test is intuitive, but I am a little confused about the experiments and theory as described above. I would feel more confident to judge the paper if my confusion is resolved.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2rodIyrtnyT", "reviewer": "Reviewer_UTuW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Paper proposes Fed-Chi square,a  secure chi-square test in the federated setting. The proposed method is practical in that it has many real-world applications as discussed by the authors. Overall, I like the paper, I have couple questions for the authors:\n\n1. For security, although the paper states that the method does not guarantee differential privacy, is it possible to show the gain in accuracy after not considering DP?\n\n2. Also, how does this compare to standard pooling of test statistics? i.e. everyone does the test on their own data and the final estimates are pooled. Similar to how one does for multiple imputation.", "summary_of_the_paper": "Paper proposes chi-square test in the federated setting where data sharing is not possible.", "summary_of_the_review": "It is a promising paper, I have couple minor questions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0ELRImWVJuT", "reviewer": "Reviewer_GEWR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n1) The problem is important and complex. \n\n2) The numeric experimental results are somewhat convincing.\n\nWeakness:\n\n1) I could not find any plausible proof or development of the theoretical claims. This may be a matter of presentation, but Sections~3.5-3.7 seem to be a bunch of statements without justification, explanation, mutual linkages or proofs. \n\n2) The paper is hard to follow and seems hastily written without proper development. For example, Section~3.2 seems to end abruptly. It describes a challenge, but not how the paper's proposal addresses the challenge. Such details may be elsewhere, but is unclear from the narrative. \n\n3) Not considering differential privacy seems a major deficiency. \n\n\n", "summary_of_the_paper": "The paper proposed a federated $\\chi^{2}$-test protocol. This is proposed as a technique that is computation- and communication-efficient and leaks much less information than other alternatives. The claim is that the proposed technique can tolerate up to 20\\% of clients dropout with minor accuracy drop. The proposed technique does not include differential privacy guarantee.\n", "summary_of_the_review": "The problem is important. However, technical concerns remain and the paper does not seem to be well-developed and is hard to read. \n\n\nRevised comments: Upon reading the authors' comments, I understand their perspective on proofs (not one that I completely agree with) and I thank them for pointing out the places where proofs may be found. However, I am still not convinced that the writing is transparent and clear, or that the issue of differential privacy may be entirely waved off. That being said, I will revise my rating and downgrade my confidence/expertise score, so if the paper is appealing to other reviewers, I will not stand in the way of its acceptance. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a federated version of the classical $\chi^2$ correlation test. The key new step is the use of stable projection to reduce computational overheads associated with the use of secure multi-party protocols. Overall while the contribution is of interest the novelty is rather limited. I also consider the work to be somewhat outside of scope for ICLR. It would be more suitable for a security or statistics focused venue. Therefore I do not recommend acceptance.
Decision: Reject