Fed-Cor: Federated Correlation Test with Secure Aggregation
Authors: Lun Wang
Qi Pang
Shuai Wang
Wenting Zheng
Dawn Song
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Analytics
Privacy and Security

Abstract: In this paper, we propose the first federated correlation test framework compatible with secure aggregation, namely Fed-Cor. In Fed-Cor, correlation tests are recast as frequency moment estimation problems. To estimate the frequency moments, the clients collaboratively generate a shared projection matrix and then use stable projection to encode the local information in a compact vector. As such encodings can be linearly aggregated, secure aggregation can be applied to conceal the individual updates. We formally establish the security guarantee of Fed-Cor by proving that only the minimum necessary information (i.e., the correlation statistics) is revealed to the server. The evaluation results show that Fed-Cor achieves good accuracy with small client-side computation overhead and performs comparably to the centralized correlation test in several real-world case studies.

In this paper, we propose the first federated correlation test framework compatible with secure aggregation, namely FED-COR. In FED-COR, correlation tests are recast as frequency moment estimation problems. To estimate the frequency moments, the clients collaboratively generate a shared projection matrix and then use stable projection to encode the local information in compact vector. As such encodings can be linearly aggregated, secure aggregation can be applied to conceal the individual updates. We formally establish the security guarantee of FED-COR by proving that only the minimum necessary information (i.e., the correlation statistics) revealed to the server. The evaluation results show that FED-COR Under review as a conference paper at ICLR 2023
FED-COR: FEDERATED CORRELATION TEST WITH SE- CURE AGGREGATION
Anonymous authors Paper under double-blind review
ABSTRACT
achieves good accuracy with small client-side computation overhead and performs comparably to the centralized correlation test in several real-world case studies.
INTRODUCTION
Correlation test, as the name implies, is the process of examining the correlation between two random variables using observational data. It is fundamental building block in wide variety of applications, including feature selection (Zheng et al., 2004), cryptanalysis (Nyberg, 2001), causal graph discovery (Spirtes et al., 2000), empirical finance (Ledoit & Wolf, 2008; Kim & Ji, 2015), medical studies (Kassirer, 1983) and genomics (Wilson et al., 1999; Dudoit et al., 2003). Because the observational data used in the correlation tests may contain sensitive information such as genomic information, and collecting participants' information to central repository poses a significant privacy risk. To address this problem, we utilize the federated setting, where each client maintains its own data and communicates with a central server to calculate function. The communication transcript should contain as little information as feasible to prevent the server from inferring sensitive information.
To motivate our work and ease the understanding of the problem setting, we consider a medical company that wants to study the correlation between genetic defects and races using the patients' private data from several hospitals. For a traditional method in the federated setting, the server, which is the medical company, will aggregate the hospitals' local private contingency tables' using secure aggregation (Bonawitz al., 2017: Bell et al., 2020). The company can conduct correlation tests with the aggregated global contingency table without directly accessing the individual hospitals' private data. Attentive readers might be aware that the method mentioned above leaks the joint distribution, which is the whole global contingency table, to the server. The joint distribution may contain sensitive information, and leaking it will probably violate privacy regulations. For instance, the medical company can observe the genetic distribution across races from the global table.
The secure aggregation primarily supports linear aggregation. However, in correlation tests, the computation involves computing a summed p-th moment over the aggregated data, where e (0, 1) U (1, 2]. Thus, the joint distribution will be leaked if we directly apply secure aggregation. To bridge the gap between secure aggregation and federated correlation tests, we take an important step towards designing non- non-linear secure aggregation protocols. Specifically, we design a federated protocol framework, namely FED-COR, optimized for class of correlation tests, such as x -test and G-test. FED-COR designed to have low computation and communication costs and only disclose information that is much less sensitive than the joint distribution. Our first insight is to recast correlation tests as frequency moment estimation problems. To approximate the frequency moments
Contingency table contains the frequency distribution of the variables; see (Wikipedia, 2021).

---

Under review as a conference paper at ICLR 2023
in federated manner, each client collaborates with the other clients to generate projection matrix and encodes its raw data into a low-dimensional vector via stable random projection (Indyk, 2006; Vempala, 2005; Li, 2008). Such encodings can be aggregated with only summation, allowing clients to leverage secure aggregation to aggregate the encodings. The server then decodes the aggregated encoding to approximate the frequency moments. As secure aggregation conceals each client's individual update within the aggregated global update, the server learns only necessary information for the correlation test.
To illustrate the power of FED-COR, we instantiate it with a representative correlation test, namely Pearson's 's -ttsttt (Pearson, 1900) and refer to the concrete protocol as FED-X2. We evaluate FED- x2 on 4 synthetic datasets and 16 real-world datasets. The results show that FED-X² can replace centralized correlation tests with good accuracy. Compared to the traditional method with secure aggregation mentioned above, FED-Xx saves factor of (m)) communication cost per client, where m is the size of the contingency tables. In FED-Xx. clients only need to upload a low-dimensional encoding with size É < while in the traditional method the clients will upload the complete contingency tables. Additionally, we analyze FED-X² two real-world use cases: feature selection and online false discovery rate control. The results show that FED-X² can achieve comparable performance with centralized correlation tests and can withstand up to 20% of clients dropping out with only minor influence the accuracy. Besides Pearson's s 2tett,, we also demonstrate how to accommodate other commonly used correlation tests such as G-test in FED-COR.
In summary, we make the following contributions:
We propose FED-COR, the first secure federated correlation test framework. FED-COR is computation- and communicationn-eficciett and leaks much less information than directly using secure aggregation to collect the contingency table, which completely leaks the joint distribution.
FED-COR decomposes correlation test into frequency moments estimation that can easily be encoded/decoded using stable projection and secure aggregation techniques. We provide formal security proof and utility analysis of the protocol.
We demonstrate how to accommodate -tetest and G-test in FED-CoR EOR, and empirically evaluate FED-X 2 in several real-world use cases. The findings suggest that FED- x² can substitute centralized x²-test with comparable accuracy. Besides, FED-Xx can tolerate up to 20% of clients dropout with minor accuracy drop. We provide the code in the supplementary material for results verification.
RELATED WORK
There have been line of works studying secure federated learning or statistics. Bonawitz et al. (2017) proposed the well-quoted secure aggregation protocol as a low-cost way to securely calculate linear functions in a federated setting. It has seen many variants and improvements since then. For instance, Truex et al. (2019) and Xu et al. (2019) employed advanced crypto tools for secure aggregation, such as threshold homomorphic encryption and functional encryption. So et al. (2021) proposed TURBOAGG, which combines secure sharing with erasure codes for better dropout tolerance. To improve communication efficiency, Bell et al. (2020) and Choi et al. (2020) replaced the complete graph in secure aggregation with either a sparse random graph or low-degree graph.
Secure aggregation is deployed in variety of applications. Agarwal al. (2018) added binomial noise to local gradients, resulting in both differential privacy and communication efficiency. Wang al. (2020) replaced the binomial noise with discrete Gaussian noise, which is shown to exhibit better composability. Kairouz et al. (2021) proved that the sum of discrete Gaussian is close to discrete Gaussian, thus discarding the common random seed assumption from Wang et (2020). The above three works all incorporate secure aggregation in their protocols to lower the noise scale required for differential privacy. Chen al. (2020) added an extra public parameter to each client 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 real-world scenarios, is not explored by existing research in this field.
3 METHODOLOGY
In this section, we elaborate on the design of FED-COR. Sec. 3.1 formalizes the problem, establishes the notation system, and introduces the threat model. In Sec. 3.2, we detail the design of FED-COR
2

---

Under review as a conference paper at ICLR 2023
by instantiating FED-COR with Pearson's -tst, namely FED-Xx In Sec. 3.3 and 3.4, present the security proof, utility analysis, communication and computation analysis of FED-X².
3.1 PROBLEM SETUP
We now formulate the problem of the federated correlation test and establish the notation system. We use [n] to denote (1,... n.). 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).
For the ease of representation, we use the example we mentioned in Sec. I to introduce all the notations. A medical company studying the correlation between genetic defects (denoted by variable X) and race (denoted by variable Y). The support domain of X (or Y) is denoted by X (or )). In the example, X {yes, no) representing whether the participant has the genetic defect, and ) is the set of all races. We denote the size of X' as myg the size of ) as My.
The company wants use the patient records from n hospitals conduct the research. Concretely, each hospital holds a 2-dimensional local contingency table D; = {* E X, ) vay E {O)U[M]}, where is the row label, y is the column label, and thy is the number of patients with the label (z.y). We use m = my?yy to denote the size of the contingency table.
(6)
The first step of the traditional method in federated setting is collect all the hospitals' contingency tables on a centralized server S of the company and sum them to obtain the global contingency table
D {2, Tay EiEnn] Day (3) The total number of samples with row label (or column label
y) is defined as Va ΣgEN Vzy (or By EvEx Uzy). The total number of samples observed is
V ExEx,vEy Uny-
The next step is to calculate test statistic, s(D), on the global table. For Pearson's =tttst,, the statistic is as below:
(Uay Bry]
(D) =
(1)
Ozy
where Bay XM is the expectation of Uay if X and Y uncorrelated. The statisties is then compared with a threshold to decide whether X and Y are correlated.
Attentive readers might be aware that the method described above incurs severe ethical issues that the patient records from different hospitals are collected on a centralized server of the company, which probably violates corresponding privacy regulations. In this work, our aim to design secure federated correlation test protocol only leaking non-sensitive information with low computa- tion/communication cost. Concretely, we trade off accuracy for security, as long as the estimation error is small with a high probability. Formally, if FED-COR outputs 8, whose corresponding standard centralized correlation test output is 8, the following accuracy requirement should be satisfied with small multiplicative error bound and small failure probability 8:
P[(1 c)s $ < (1 + t)s] 5
(2)
Threat Model. We assume that the centralized server S is honest but curious. It honestly follows the protocol due to regulatory or reputational pressure but is curious to 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.
On the other hand, we assume the clients (e.g. the hospitals) are honest and won't collude with the server. Specifically, we do not consider client-side adversarial attacks (e.g., data poisoning attacks (Bagdasaryan et al., 2020; Bhagoji al., 2019)). However, we allow a small portion of clients to drop out during the execution. We also provide further security analysis when collusion between the server and the client happens in Appendix G.
More importantly, assume that the marginal distributions of the variables are not sensitive while the joint distribution is. The above example is a natural case where such an assumption holds. The aggregated marginal distributions of the genetic defects and the races won't It' leak sensitive information. However, the correlation between a specific pair of race and genetic defect can be easily observed the joint distribution, which is the aggregated global contingency table, is obtained by the server.
3

---

Under review as a conference paper at ICLR 2023
3.2 FEDERATED CORRELATION TEST WITH SECURE AGGREGATION
In this section, we introduce the design of FED-COR in detail by instantiating FED-COR with Pearson's X -test. We also discuss how the design generalizes other statistical tests such as G-test (SOKAL et al., 1995) in Sec. 5.
From Federated Correlation Test Frequency Moments Estimation. The a-th frequency moment of key-value stream is formally defined as below:
Definition 1 (a-th frequency moment). Given a key-value stream {a, E A, E he the a-th frequency moment of S is defined as:
F (a
Σ Σ nEAA tE/T
b2)a
We observe that the test statistics of many correlation tests can be rewritten as frequency moments. For example, the statistic of X -test can be reformatted as a second frequency moment:
(uzy
Exy
Day
Dzy 2
(4)
Uzy
Uay
(88 xxx/n and the above
In the federated setting, the ith client calculates the vector u, (,, formula can be rewritten as a second frequency moment estimation problem:
Uay
Uay
Σ
v))
Uzy
J. 8E(M]
Federated Frequency Moments Estimation. Now that have reformatted the problem, the second step to design the messages transmitted in FED-COR for thth frequency moments estimation. We choose stable projection (Indyk, 2006; Vempala, 2005) encode the client-side information and geometric mean estimator (Li, 2008) to decode the aggregated message. Before we dive into the details, let's refresh some preliminaries. See Appendix A for more details stable distribution.
Definition (Symmetric a-stable distribution). A random variable X follows a symmetric a-stable distribution 2. if its characteristic function is as follows:
Φx (t) = exp( - -1-10// sggssgn(t) tan( T ))),
TO
(6)
where F is the scale, th E (0,2) the stability parameter, and is the skewness.
a-stable distribution is named due to its property called a-stability. Briefly, the sum of independent o-stable variables still follows an a-stable distribution with different differentscale. scale.
Definition (a-stability). random variables X 20,8,1 Y 2a, and X and Y are indepen- dent, then C + C.y ~ +
Inspired by the idea of Indyk's well-cited paper (Indyk, 2006), we encode the frequency moments in the scale parameter of stable distribution. To encode information contained in the local contingency table D:, the 5th client collaborates with other clients to generate a projection matrix P E / projection matrix, where is the encoding size. The components of P are drawn independently from an a-stable distribution 20,0,1- The client then calculates u, as defined in Eq. and applies the projection get e; = P u, the encoding (lines 1-2 in Alg. 1).
To decode, the server first sums the encodings from all the clients e = Eiejn e; According to the a-stability defined in Definition 3, every component in the encoding vector e, h E [é], follows this stable distribution 2.,0,,(D)- Thus, the statistic of the correlation test can be estimated with the scale of the distribution. We estimate the scale using an unbiased geometrie mean estimator (Li, 2008) (lines 3-4 in Alg. l).
A significant advantage of stable projection is that the encodings are linearly aggregatable and thus compatible with secure aggregation. Secure aggregation only reveals the aggregated encoding to the server and greatly reduces the privacy leakage. Furthermore, in Sec. 3.4, we show that small encoding size suffices to accurately approximate the frequency moments with high probability and potentially improve communication cost with certain setups.
4

---

Under review as a conference paper at ICLR 2023
Algorithm The encoding and decoding scheme (Indyk, 2006) 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 DECODE (e):
[ 15. 2/4
return ( ())
11 E iss the encoding size.
The complete FED-X² protocol. SECUREAGG is remote procedure that receives inputs from the clients and returns the summation to the server. INTISECUREAGG the corresponding setup protocol deciding the communication graph and other hyper-parameters.
Algorithm 2
Round I: Reveal the marginal statistics INITSECUREAGe (n)
11 clients number
for [m..] do U; SeCUREAGe (u,) kej))
for E [my] do Uy SECUREAGe (u ( )e(())
Server
Calculate En ta and Broadcast v. {Uz}, and {uy} } to all the clients
Round Approximate statisties
Client [n]
Calculate Uay
Prepare u, s.t. (a,
Randomly sample random seed and broadcast all the other clients
12
Collect the random seeds from other clients and obtain shared random seed
Σ
Sample the projection matrix P from x using the common random seed
14
Calculate e; ESCODE (P, 4;:)
15
e= SECURFAGE (QUAN==>S XE (e()))))
16
Server
17
DECODE (e)
FED-X² Protocol. We instantiate FED-COR with Pearson's x² -test, and the complete FED-X² protocol presented in Alg. Firstly, the marginal statistics Uz, Byy and are collected with secure aggregation and broadcasted to all the clients (lines 1-6 of Alg. 2). This step can be omitted if the marginal statistics are already known. The hth client calculates u, (lines 9-10 of Alg. 2), and samples random seed and broadcasts to other clients (line 11 of Alg. 2). Then, the clients receive the random seeds and sample the projection matrix from the o-stable distribution 2 using the common random seed (lines 12-13 of Alg. 2). The zth client projects u, obtain the encoding e; (line 14 of Alg. 2). Then, the encodings are quantized and aggregated with secure aggregation (line 15 of Alg. 2). As 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 as 64 bits, such that the precision of the quantized float numbers is comparable to even better than the IEEE floating numbers. We validate this conjecture with empirical evaluation and hence ignore the effect of quantization on accuracy the analysis. In the last step, the server gets the 2 statisties using the decoding algorithm described in Alg. 1 (line 17 of Alg. 2).
Remark: Client Dropout. Attentive readers might ask what some clients drop during the protocol execution? We argue that dropouts in the first round have no effect on the test's 's accuracy as long as the secure aggregation used is resilient dropout, such as (Bonawitz al., 2017: Bell et al., 2020). On the other hand, dropouts in the second round will affect the accuracy of the test. However, since the x2 value typically far from the decision threshold, FED-X2 2 is intrinsically robust to small portion of clients dropping out (see Section 4 for empirical assessment).
Remark: The Selection of Secure Aggregation. As introduced in Sec. 2, there are variety of secure aggregation protocols for different setups (Bonawitz et al., 2017: Truex et al., 2019; Xu et al., 2019; So et al., 2021; Bell et al., 2020; Choi et al., 2020). In the rest of the paper, we choose the state-of-the-an cross-device secure aggregation protocol by Bell al. (2020) due its simple trust assumption and low communication cost. We want to emphasize that FED-COR can incorporate any secure aggregation protocols needed.
5

---

Under review as a conference paper at ICLR 2023
3.3 SECURITY ANALYSIS
We now prove the security enforced by Alg. 2 via a standard simulation proof process (Lindell, 2017) on the basis of Theorem 1.
Theorem 1 (Security). Let II be instantiation of Alg. with the secure aggregation protocol in Alg. 4 of Appendix with cryprographic security parameter x. There exists a PPT simulator SIM such that for all clients C, the mumber of clients all the marginal distributions V and the aggregated encoding e, the oulput of SIM is indistinguishable from the view of the real server Tee in that execution, i.e., Tee R SIM(e, Va, Vy, n).
Intuitively, Theorem 1 illustrates that more information about the clients except the aggregated updates is revealed to the centralized server. Note that this is the minimal necessary information for the server to estimate the test statistic. The complete proof for Theorem I is deferred to Appendix D.
To further emphasize the privacy protection of our protocol, we also provide analysis on the leakage when the server colludes with a client in Appendix G. We show that even the collusion happens, our protocol can still successfully hide the information in a subspace with exponential possible distributions, which practically enforce privacy given the considerably large size of the solution space.
3.4 UTILITY, COMMUNICATION & COMPUTATION ANALYSIS
We first present the utility analysis of FED-X2 2 in Alg. 2. We show that the output of FED-X²: 8xa, is fairly accurate approximation (parameterized by e) to the correlation test output sya in the standard centralized setting with high probability parameterized by 8 when e is appropriately chosen. The proof deferred to Appendix E.
Theorem 2 (Utility). Let II be instantiation of Alg. with secure aggregation protocol in Alg. 4 of Appendix B. 11 is parameterized with { = & log((/8) for some constant c. After executing Ilc on all clients C, the server yields 8,2, whose distance to the accurate correlation test output xxa bounded with high probability as follows:
p|a (1 e)sya V (1 (1)))
Then present the communication and computation cost of Alg. 2.
Theorem 3 (Communication Cost). Let II be an instantiation of Alg. 2 with secure aggregation protocol Alg. 4 of Appendix B, then (1) the client-side communication cost Olog n + m my + E); (2) the server-side communication cost is O(n log + nm, nmy + nt).
Theorem 4 (Computation Cost). Let II be an instantiation of Alg. 2 with secure aggregation protocol in Alg. 4 of Appendix B, then )) the client-side computation cost is Ologg n + m + my) log n mé): (2) the server-side computation cost is O(n log' + n(( + my + my) log n + E).
Note that compared with the original computation cost presented in (Bell et al., 2020), the client-side overhead has extra (mm)) term. This term is incurred by the encoding overhead. We also give an empirical evaluation on the client-side computation overhead in Sec. 4.1. Please refer to Appendix for the detailed proof of Theorem 3 and Theorem 4.
EVALUATION
Experiment Setup. To assess FED-X2's accuracy, simulate it on four synthetic datasets and 12 real-world datasets. We compare the multiplicative error é := (2,)(D)= and power of FED-X2
(_2(D)
with that of the standard centralized -test The four synthetic datasets are independent, lincarly correlated, quadratically correlated, and logistically correlated. For the real-world datasets, we report the details in Appendix H.
We evaluate FED-X X utility in two real-world application scenarios: feature selection and online false discovery rate (FDR) control. For feature selection, we report the model accuracy trained on the selected features. For online FDR control, we report the average false discovery rate. We compare the performance of FED-X² 2 with that of the centralized x 2ttest in each of the three experiments.

---

Under review as a conference paper at ICLR 2023
Error no dropout
Error of 5% drepout
ACC no drapout
ACC of 5% dropout
Moliylicatie PPowe
Molplizatie Elee Nower
Molppicttee Ebmoe ef Dowee
Malggicatie Ease /Poaect
00:
20
000g
0.4-
041-
0.2-
60
.00
160
210
50
100
150
200
50
100
360
200
100
500
(a) Synthetic
(b) Symthttic
(c) Synthetic
Symthetic
Mallpheaiee Power
Mallplcahe Emme Honez
Nhilppechh Ef P Power
Mallglcaivenme if Poower
0-1-
0
0.4
0.2-
0.2
00
100
100
150
150
(g)
(h)
Maliciicaive / /Bwe
Maliplicas tmme Powee
Milhplictte Eimer of /f Fower
Maltsiiaive Eave in Powe
0.
0.4
0.
0.2
02
02
022
100
200
20
200
50
150
150
Data
( Data
Malipicanss fmmer (ower
Mrtipllatte t Power
Maltylicaine Eace Fawe Maliokiaaine E
D08-
0.6
0.6
Malisicatve
0.4
0.4
0.4
0.4
20
100
100
700
50
100
150
200
50
100
150
-30
50
(m) Data
(n) Data 10.
(0)
Data I...
(p)
Mulislcaire Eace //wd
Malrylicttee Exer lTowe
Minppliattee Extor t/ Fower Fower
0.8
06-
0.6
0.5-
0.6
100
Encoding size
Eacodine
(g) Data 13.
Data 14,
Data
Figure 1: Multiplicative error and power of FED-X2 w.r.t. encoding size l with and without dropout.
For secure aggregation, we discretize all the real numbers to 64-bit fix-point numbers. We provide further evaluation on the influence of finite field size in Appendix M, which shows that FED-X" is numerically stable under different finite field sizes.
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
Accuracy. We begin by evaluating the accuracy of FED-X2, as illustrated in Fig. 1. Each point represents the mean of 100 independent runs with 100 clients, while the error bars indicate the standard deviation. We choose m, = my = 20 in this experiment. Note that the accuracy drop of FED-X² is independent of the number of clients.
From Fig. 1, observe that the larger the encoding size f, the smaller the multiplicative error. When f f= 50, the multiplicative error ~ 0.2. This conforms with Theorem 2, in which the multiplicative emrrr c V (og(2/5) (2/)) decreases as increases.
We also evaluate the power (Cohen, 2013) of FED-X2. We set the p-value threshold as 0.05. From tell that the power of FED-X² is high. This conforms with
the dashed lines in Fig.
7

---

Under review as a conference paper at ICLR 2023
observation on the multiplicative errors. Specifically, since the x² values are typically far from the decision threshold, a multiplicative error of 0.2 rarely flips the final decision.
We also present the results when 5% of clients drop out in the second round of FED-X² in Fig, 1. The results show that FED-X² robust to a small portion of dropouts. In Appendix J, we present the results in terms of 10%, 15%, and 20% dropout rates. The results further show that FED-X² can tolerate a considerable portion of clients dropout in Round 2 of Alg. 2.
Client-side Computation Overhead. To assess extra computation overhead incurred by FED-x² on the client side, we measure the execution time of the encoding scheme device equipped with a Snapdragon865 CPU and 12GB RAM. We use PyDroid (Sandeep Nandal, 2020) run the client-side computation of FED-X² on the Android device.
Aog: Encading Time (ms)
Android 10 mobile
300
10-
As shown in Fig. 2, each point represents the average of 100 separate runs, with accompanying error bars. The overhead is generally neg- ligible. For example, for a 500 x 500 contingency table, the encoding takes less than 30ms. The overhead grows linearly in relation to mar (my) and consequently quadratically Fig. 2, where my = My.
100
2000
400
500
102
(my
Figure 2: Client-side encoding overhead.
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-k highest x²2 scores. We use Reuters-21.788 (Hayes & Weinstein, 1990), a 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,3 16 test documents. These documents are distributed randomly to 100 clients. each of whom receives the same number of training documents. After removing all numbers and stop-words, we obtain 167, 135 indexing terms.
The contingency table is of size 2020 where corresponds to whether term occurs in an article and 20 corresponds to the number of different article categories. After per- forming feature selection using FED-x we select the top 40,000 terms with the highest X2 scores. When compared with the centralized =tttest, 38,012 (5500%) of the lected terms are identical, indicating that FED-X² produces highly consistent results with the standard x 2ttest.
selection FED-x" no dropout
Model Accuracy
FED-x 10% dropout
FLD-x 206 dropout centralizd yaass
50
30
60
90
120
150
Epuch
We then train logistic regression models using the terms selected by FED-X² and the centralized x²ttest, respec- tively. All hyper-parameters are the same. The details of these models are reported in Appendix I. The training and testing splits are the same for FED-X2. centralized -tett, and model without feature selection (i.c. there are 17,262 training and 4.316 test documents). We 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.
Figure 3: Accuracy of models trained with features selected by FED-X² ² and centralized x" 22-test.
The results in Fig. 3 further demonstrate that FED-X² exhibits comparable performance with the centralized -tett. When 10% and 20% of clients dropout in the second round of FED-X2. the accuracy of the trained model using the features selected by FED-X2 does not drop much. We also examine performance without feature selection, and as expected, model accuracy 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. We also provide further evaluation the influence of encoding size & Appendix L, which shows that FED-X² can achieve comparable performance with the centralized x -test under different L.
Online False Discovery Rate Control. In the third case study, we explore federated online false discovery rate (FDR) control (Foster & Stine, 2008) with FED-X 2 In an online FDR control problem,
8

---

Under review as a conference paper at ICLR 2023
data analyst receives stream of hypotheses on the database, or equivalently, stream of p-values: P1, P2, ... At each time t, the data analyst should pick a threshold a to reject the hypothesis when Pt O4. The error metric is the false discovery rate, and the objective of online FDR control is to ensure that for any time I, the FDR up to time t. is smaller than a pre-deternined quantity. We use the SAFFRON procedure (Ramdas et al., 2018), the Mate-of-theeart online FDR control, for multiple hypothesis testing. The x² results and corresponding p-values are calculated by FED-X². We present the SAFFRON algorithm in Appendix C.
Each time, there are 100 independent hypotheses, with a probability of 0.5 that each hypothesis 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 is randomly sampled from a uniform distribution. For the independent data, the covariance matrix is diagonal, and its entries are randomly sampled from uniform distribution.
At time t, we use FED-X² to calculate the p-values Pt of all the hy- potheses, and then use the SAFFRON procedure to estimate the reject threshold a using Pt. The relationship between the average FDR and
100
FDR FDR/TDR /RR/TDRCO (%)
FFRR Fen-xx"
encoding size l is shown in Fig. 4. We observe that the variance of
601
.TIRR of Pinn-y"
independent runs is very small, so we omit the error bars. FED-X²
40
FDR of contralized t--test
TDR
x
achieves good performance (FDR lower than 10%) when the encoding size I is larger than 200. In Fig. 4, we also provide the FDR result of the centralized -tett well the true discovery rate (TDR, i.e., #correct reject/ #should reject). In addition, we provide statistics for each encoding size / that was evaluated in Appendix K. The results indicate that by increasing the encoding size É, FED-X² can achieve comparable performance to the centralized -tett. The results further demonstrate that FED-X² 2 can be employed in practice to facilitate online FDR control.
20
200
Encading Size
Figure 4: FDR & TDR w.r.t. 8 for SAFFRON.
5 DISCUSSION: CORRELATION TESTS BEYOND 2
Pearson's 's -tett is not the only correlation test compatible with FED-COR. To demonstrate the extensibility of FRD-COR, we show how to recast G-test (SOKAL. et al., 1995) to frequency moments estimation problem. The reduction is more involved as the statistics in G-test contains logarithmic term, and we rewrite sg as shown below:
sG (D) = Σ 2.
Day log Usy
= 3 Vay log May 2
> Bay log Tay 2.9
(8)
Dzy
2.8
Similar to 2ttttt Uzy = can be approximated using the following formula (Zhao al., 2007) with small A:
Xily, is the expectation of Dxy if X and Y are uncorrelated. The first term
Σ Uny y log Uay 21.0
1
Σ
(9)
24
2.3
In this way, we recast G-test to two frequency moments estimation of orders 1 + A and 1 - A. The rest of the protocol the same as FED-X² in Alg. 2 except that we estimate two frequency moments.
CONCLUSION & FUTURE WORKS
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 on an important application of the protocol: correlation test. We give formal security proof and utility analysis our proposed protocol and validate them with empirical evaluations and downstream use case studies.
We also discuss potential future direction. We deem it promising to provide stronger privacy guaran- tee for FED-COR by incorporating differential privacy techniques like differentially private frequency moments estimation (Wang et al., 2021) adding calibrated discrete Gaussian noise (Canonne et al., 2020) to the users' local updates.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. cpsgd: Communication-cficient and differentially-privart distributed sgd. Advances in Neural Information Processing Systems, 31, 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. In International Conference on Machine Learning, pp-
634 643. PMLR, 2019.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Maurizio Brunetti and Renato. Old and new proofs of cramer's rule. Applied Mathernatiaal Sciences, 8(133):68896667,, 2014.
Clément I. Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Advances Neural Information Processing Systems, 33:15666-15688, 2020.
Yu Chen, Fang Luo, Tong Li, Tao Xiang, Zheli Liu, and Li. A training-integrity privacy-preserving 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:2012.05433: 2020.
Jacob Cohen. Statistical power analysis for the behavioral sciences. Academic press, 2013.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL ics. uci..... frci.edu/mi edu/ml.
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 A Stine. a-investing: procedure for sequential control of expected false discoveries. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 70(2): 429-444, 2008.
Govindaraj, Praveen. Credit Risk Classification Dataset: Is Customer Risky or Not Risky ? https:
// //www. kaggle. com/ www.aveenoov//rrettteeeeee www.rreeeeiiiirrlreeeeeeeeeeeeee wtw.sccaaassiiaaaiiio..ooooo datiaet... Online; accessed 22 April 2021.
Philip J Hayes and Steven P Weinstein. Construe/tis: A system for content-based indexing of database of news stories. In !AAI, volume 90, pp. 49-64, 1990.
Sebastian Houben, Johannes Stallkamp, Jan Salmen, Mare Schlipsing, and Christian Igel. Detection of traffic signs in real-worte images: The German Traffic Sign Detection Benchmark. In International Joint Conference on Neural Networks, number 1288, 2013.
Piotr Indyk. Stable distributions, pscudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53(3):307-333, 2006.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning, pp. 5201-5212. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
Jerome P Kassirer. Teaching clinical medicine by iterative hypothesis testing: let's preach what 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: //archive.iicioo ics. uci edu ml/ /ataaatt//ad.lttttt Online: accessed 22 April 2021.
Kononenko, Igor and Cestnik, Bojan. UCI Machine Learning Repository: Lymphography Data Set. https: / arrcciiee. ics..icc... uci www.eeewueelleeeee http://.ww....aaaaataaaaa//paaaa Online; accessed 22 April 2021.
Oliver Ledoit and Michael Wolf. Robust performacee hypothesis testing with the sharpe ratio. Journal of Empirical Finance, 15(5):50-885, 2008.
Paul Lévy and Paul Lévy. Calcul des probabilités. Gauthier-Villars, 1925.
Ping Li. Estimators and tail bounds for dimension reduction in la (0 S 2) using stable random projections. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 10-19, 2008
Ychuda Lindell. How to Simulate 346. Springer International Publishing, Cham, 2017. ISBN 978-3-319-57048-88 doi: 10.1007/ 978-3-319-57048. -_60086666....0 URL https:://// org /tt.//11.1110///..1 /tt..////0..11000700---3111----0 0tt.0//099907-0-1--------0-
Tutorial on the Simulation Proof Technique, pp. 277-
__6.
Kaisa Nyberg. Correlation theorems in cryptanalysis. Discrete Applied Mathematics, 111(1-2): 177-188, 2001.
Karl Pearson. X. on the criterion that given system of deviations from the probable in the case of correlated system of variables such that it can be reasonably supposed to have arisen from random sampling. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 105302): 1900.
Aaditya Ramdas, Tijana Zmic, Martin Wainwright, and Michael Jordan. Saffron: an adaptive algorithm for online control of the false discovery rate. In International conference on machine learning, pp. 4296-4294. PMLR, 2018.
Sandeep Nandal. PyDroid. https: httpss//bopp..crrppppppses//pspp 2020. Online; ac- cessed 24 April 2021.
Schlimmer, Jeff. UCI Machine Learning Repository: Mushroom Data Set. https://archhi ics. uci..uci.ed http://dddaaattt///s///oooom
/Mush 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.
Robert SOKAL, James ROHLF, et al. Biometry: The principles and practis of statistic biological research. 1995.
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 preeeccpress federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, 1-11, 2019.
Santosh S Vempala. The random projection method, volume 65. American Mathematical Soc., 2005.

---

Under review as a conference paper at ICLR 2023
Lun Wang, Ruoxi Jia, and Dawn Song. D2p-fed: Differentially private federated learning with efficient communication. arxiv. wg/ppdf2006.13333 2020.
Lun Wang, Iosif Pinelis, and Dawn Song. Differentially private fractional frequency moments
estimation with polylogarithmic space. arXiv preprint arXiv:2105./2380 2021.
Wikipedia. Contingency table -
Wikipedia, the free encyclopedia, 2021. htttss://en. wiki pedia org/ index. petpptttiieeeeonninnnee..aaeaaa ingenccttneeeeeeee oldid=1055311221. [Online; accessed 27- 77-September-2022)
URL
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-16 1999.
Runhua Xu, Nathalie Baracaldo, Yi Zhou, Ali Anwar, and Heiko Ludwig. Hybridalpha: An efficient approach for privacy-presse preeacc-peseervnng 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 leml, volume 97, pp. 35. Nashville, TN, USA, 1997.
Jian Zhang and Yiming Yang. Robustness of regularized linear classification methods in text categorization. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pp. 190-197, 2003.
Haiquan Zhao, Ashwin Lall, Mitsunori Ogihara, Oliver Spatscheck, Jia Wang, and Jun Xu. A data streaming algorithm for estimating entropies of od flows. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pp. 279-290, 2007.
Zhaohui Zheng, Xiaoyun Wu, and Rohini Srihari. Feature selection for text categorization on imbalanced data. ACM Sigkdd Explorations Newsletter, 6 6(1):80-89,
89, 2004.
12

---

Under review as a conference paper at ICLR 2023
APPENDIX
A STABLE DISTRIBUTION REFRESHER
non-degenerate distribution is said to be stable if for and Y sampled from the distribution, ax + bY for some constants a, b > 0 has the same distribution up to location and scale parameters. Paul Léby first systematically study the stable distribution family in his master piece: Calcul des probabilités (Lévy & Lévy, 1925) so stable distribution is also referred to as Léby a-stable distribution. Stable distributions are parameterized by location μ., scale F, the stability parameter a and the skewness 3. When * 1, the characteristic function is as below:
xx = exp(itu (l - VIB stn(t) tan
Ta
)))
(10)
2
When a = 1, the characteristic function given by:
Øx (t) exp(itu - FIt 15 sgn(t) log [t))
(11)
In the main text, we only consider a subset of stable distributions where and a # 1.
Stable distribution family contains many familiar distributions. For example, 1-stable distribution is Cauchy distribution, 2-stable distribution is Gaussian distribution, and 1/2-stable distribution is known as Levy distribution.
Stable distributions also have discrete analogues defined by their probability generating function
G(I) = exp(-F1")
(12)
where F is the scale and is the stability parameter. However, for discrete stable distribution, the support domain of a is (0, 1] instead of (0,
B SECURE AGGREGATION REFRESHER
The secure aggregation protocol from Bell et al. (2020) is presented in Alg. 4. The first step of the protocol is generate a k-regular graph G, where the vertices are the clients participating in the protocol. The server runs a randomized graph generation algorithm INITSECUREAGE presented in Alg. 3 that takes the number of clients n and samples output (G, i, from distribution D. In Alg. 3, we uniformly rename the nodes of a graph known as a Harary graph defined in Definition with n 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 k = (log(n)), which is large enough to hide the updates inside the masks. is the threshold of the Shamir's Secret Sharing.
In the second step, the edges of the graph determine pairs of clients, each of which runs key agreement protocols to share random keys. The random keys will be used by each party derive a mask for her input and enable dropouts.
In the third step, each client e, i E A 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.
In the fifth step, each pair (i,j) of connected clients in G runs X-secure key agreement protocol 8t. K.A.Agreeess. (ski, ,k?), which uses the key exchange the previous step to derive a shared random key st.j. The pairwise masks m,, = F(ss,)) 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 c; is: y, e, +r EjeNe(nde m;j + N)NN(()))> m..i-
the pscudorandom
Steps 6-8 deal with the clients dropout by recovering the self masks r, of clients who are still active and pairwise masks m,j 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: Eie r,
EseNaron(4) Mij -EJENannuA m.j).
13

---

Under review as a conference paper at ICLR 2023
Definition 4 (HARARY(n, k) Graph). Let HARARY(n, k) denotes a graph with nodes and degree k. This graph has vertices = [n] and an edge between two distinct vertices and j if and only if j - (mod n) I (k 1)/2
(mod n) 2 k/2.
Algorithm 3 INITSECUREAGG: Generate Initial Graph for SECUREAGG.
Function INITSI SAITSECCUREASE
CUREAGG (n)
> n: Number of nodes.
> l: Threshold of Shamir's Secret Sharing.
k = (l))
Let H HARARY (n, k).
Sample random permutation x [n] 1 [n].
Let G be the set of edges {(T(1), (())) H}.
return (G, k))
C SAFFRON PROCEDURE REFRESHER
In Sec, 4.2, we adopt the SAFFRON procedure (Ramdas et al., 2018) to perform online FDR control. SAFFRON procedure currently the state of the arts for multiple hypothesis testing. In Alg. formally present the SAFFRON algorithm.
The initial error budget for SAFFRON (1 W)) < (1- (1-Ajja) >jaa), and this will be allocated to different tests over time. The sequence (N,} is defined by ge and X3 serves as a weak estimation of
az. 9t can be any coordinate wise non-decreasing function (line 8 in Alg. 5). R == [pp < aa) is the indicator for rejection, while C == [(p, < <\y) is the indicator for candidacy. Ty is the jth rejection time. For each pt. if Pt < A₁. SAFFRON adds to the candidate set C, and sets the candidates after the jth rejection (lines 9-10 in Alg. 5). Further, the is updated by several parameters like current wealth, current total rejection numbers, the current size of the candidate set, and so on (lines 11-14 in Alg. 5). Then, the decision R2 is made according to the updated a, (line 15 in Alg. 5).
The syper-parametert for the SAFFRON procedure online false discovery rate control of Sec. aligned with the setting in Ramdas et al. (2018). The target FDR level is 0.05, the initial wealth is Wo = 0.0125, and y is calculated in the following way: 7 = Σ 1/U+1)100
1/(j+1)200
10000
D PROOF FOR THEOREM 1
Proof for Theorem 1. To prove Theorem 1, we need the following lemma.
Lemma 1 (Security of secure aggregation protocol). Let SECUREAGG be the secure aggregation protocol in Alg. 4 of Appendix B instantiated with cryprographic security parameter X. There exists probabilistic polynomial-tmme (PPT) simulator SIMSA A such that for all clients C, the number of clients n, and the aggregated encoding e, the output of SIMSA is perfectly indistinguishable from the view of the real server, i.c. SECUREAGGe K) SIMSA(e,
Lemma is derived from the security analysis of our employed secure aggregation protocol (Theorem 3.6 in Bell al. (2020)), which establishes that the secure aggregation protocol securely conceals the individual information in the aggregated result. With this lemma, we are able to prove the theorem for federated correlation test by presenting 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 are indistinguishable according to transitivity.
HYB: This is the view of the server in the real protocol execution, REALC-
HYB2 In this hybrid, replace the view during the execution of each SECUREAGG( (vv. (ie in line of Alg. 2 with the output of SI,SA n) one by one correspondingly. According to Lemma 1, each replacement does not change the indistinguishability Hence, HYB2 is indistinguishable from HYB1-
14

---

Under review as a conference paper at ICLR 2023
HYB3 Similar to HYB2, we replace the view during the execution of each SECUREAGG hEEm! in line 4 of Alg. 2 with the output of SIMSA(V,, one by one. According to Lemma 1, HYB3 is indistinguishable from HYB2-
HYB4 In this hybrid, we replace the view during the execution of SECUREAGG((e) (E())) in line 15 of Alg. 2 with the SiMSA(e, n)) This hybrid is the output of SIM. According to Lemma 1, HYB, is indistinguishable from HYB3-
Algorithm 4 SECUREAGG: Secure Aggregation Protocol. (Algorithm from Bell al. (2020))
Function SECUREAGG ((e) ((e))
> Parties: Clients C1, Cns and Server.
> l: Vector length.
> x Input domain, e; x'.
b F: :0,, + X PRG.
b We denote by A1, A2, Ay the sets of clients that reach certain points without dropping out. Specifically Aı consists of the clients who finish step (3), A2 those who finish step (5), and A3 those who finish step (7). For each A;, A² is the set of clients for which the server sees they have completed that step on time.
(1) The server runs (G,t., k)
(n), where G is a regular degree-k undirected graph with n nodes. By (i) we denote the of ls nodes adjacent to c; (its neighbors).
(2) Client G, i E [n). generates key pairs (sk) pk?). ), (sk? pk?) and sends (ph: pki?) to the server who forwards the message (i).).
(3) for each Client c, E A do
Generates random PRG seed b;.
Computes two sets of shares:
H [h/,1 h/1b = Shamir k. b.)
H (1 ... ,,,) Shamir ki shi!)
Sends to the server a message m = (j. ci.). where Cijj = Eanth Baach,Enc((s. (1
kij = K.A.A.A.reeeeee pk.),, ) for each j No(1).
(4) The server aborts if |A1] < (1 8)n and otherwise forwards (J, c..) to client ej who deduces
A n NG))..
(5) for each Client c, E Ag do
Computes shared random PRG seed 8i.j as 81,j = Agr.eer
Computes masks m.j F(s.,) and r; F(b:).
Sends to the server their masked input
Σ jE(D]jKi
y: = =; +r
mi.i +
m
jE(n].jo
(6) The server collects masked inputs. It aborts if |A4]] (A's U No(i),, (Ai) U Nc(i)) ) to every client e, i E Alg.
(1 -1) and otherwise sends
(7) Client Cj,j As receives RR) from the server and sends {(i, ((ihi,)) Mi))ER (i,hhi obtained by decrypting the C.j received in Step (3). (8) The server aborts if |A4] (1 5)n and otherwise:
Collects, for each client c,, A/, the set B, of all shares in H. sent by clients in Ag. Then aborts if |B < / and otherwise recovers b, and r; using the / shares received which came from the lowest client IDs.
Collects, for each client ç, E (Ai (1))),, the set S, of all shares in HỘ sent by clients in Ag- Then aborts if |S and otherwise recovers sk! and m.jj.
return Σie (v. r; + + EsENG(nnA ma.j Esencrsna m..)).
15

---

Under review as a conference paper at ICLR 2023
E PROOF FOR UTILITY
Proof for Theorem 2. First, we introduce the following lemma from Li (2008).
Lemma 2 (Tail bounds of geometric mean estimator (Li, 2008)). The right tail bound of geometric mean estimator is:
p( 8x2 > e8x2) S exp(
(13)
GR where GR Ci log(1 + +) Cize - log( (a C1) sin =a(1)) )) a 2 in our
setting, C1 2 tan -1 log(1 1 and To is the Euler's 's constant.
(2+a")=/64
The left tail bound of the geometric mean estimator is:
P( 8x2 < <6822) sxp() GL
(14)
where
to. Gz CC2log(1 c) log( [[ T T
TT(-aCa)T(L C2) sin( mg(²))
2 $t
Co log(
1 sin( 2 1), and C2 = x² (2+a2)
12
With Lemma 2, Taking 2 max GL) and 8 2 exp(- we are able to prove P( <
-)ssx V 8 (1 + c)sya] S 8 with union bound, which is achieved when l - log(2/6). 0
F PROOF FOR COMMUNICATION & COMPUTATION CoST
In this section, we prove Theorem 3 and Theorem 4.
Theorem 3 (Communication Cost). Let II be an instantiation of Alg. 2 with secure aggregation protocol from Bell et al. (2020), then (1) the client-side communication cost is Ollog n m ty +(); (2) the server-side communication cost On log n + nm, + nmy + nl).
Proof sketch for Theorem 3. Each client performs key agreements (O(k) messages, line in Alg. 4) and sends 3 masked inputs (m(,, + my + f) complexity, lines 3, 4, 15 in Alg. 2 and line 10 in Alg. 4). Thus, the client communication cost is Ollog
m2 + my + E).
The server receives or sends Ologn n + my + my + E) messages to each client, so the server communication cost is Onglog + nm, nmy + nE).
Algorithm 5 SAFFRON Procedure.
Function PwE.PPRONNNPRCREEOR
(PP.P2..>. }. a, Wo. {7i) ( > {P1.P2. ... }: Stream of p-values computed by FED-X².
RC
> a: Target FDR level.
b Wo: Initial wealth.
> { Positive non-increasing sequence summing to one.
i -
// Set rejection number.
for each p-value Pa (pI.P2.... do
X 4 91
// Set the indicator for candidacy C.. Cj+ Σt Ci 11 set the candidates after the jth rejection.
C.+ [(p: < X1)
ift= then
01 (1 W
else
04 - (1 11-))(WWWrcc. +(a Wo) + Ejz -7-
R4 + [(p aa)
// Output R,
if RR then
1+i+1
// Update rejection number. // Set the 4th rejection time.
7 return
(Ro, R1....)
16

---

Under review as a conference paper at ICLR 2023
Theorem 4 (Computation Cost). Let II be an instantiation of Alg. 2 with secure aggregation protocol from Bell et al. (2020), then (1) the client-side computation cost is (m log n + my log n + flog n mē); (2) the server-side computation cost is (m, + my + E).
Proof sketch for Theorem 4. Each client computation can be broken up as k key agreements (O)
complexity, line 9 in Alg. 4), generating masks m.j for all neighbors çj (O(k(n, + My + ()) complexity, lines 3, 4, 15 in Alg. 2 and line 10 in Alg. 4), sampling encoding matrix P cost (mm)..
line 13 in Alg. 2, and encoding computation cost (mm) (line 14 in Alg. 2). Thus, the client computation cost is (m, log n. + my log + e log n + mf).
The server-side follows directly from the semi-honest computation analysis in Bell al. (2020). The extra (()) term is the complexity of the geometric mean estimator.
G FURTHER SECURITY ANALYSIS WHEN COLLUSION HAPPENS
We have shown that Alg. 2 provides strong security guarantee when there no collusion between the clients and the server. That is, the server only knows the non-private marginal distribution of the contingency table and the final aggregated results. In the following section, we will analyze the leakage of Alg. 2 when the collusion happens to demonstrate that FED-X² provides strong privacy guarantee and also help the readers better understand our protocol.
Remark: what does Alg. 2 leak when collusion between the server and the client happens? If the server colludes with one client, then knows the random seed r (line 12 Alg. 2) used to generate the projection matrix P. In the following, will analyze the leakage of client private data when the server knows
By Theorem 1, show that individual updates of clients are perfectly hidden in the aggregated results and FED-X2 leaks no more than a linear equation system if the server knows P:
{
Pxv
eT
JI JI. JI
V
(15)
where J1.m, and Ji,m, are my and my unit matrices, is an my x my matrix whose elements are {Vayh, and v is the flattened vector of V.
To understand (15), v (or V) sensitive and all the other matrices and vectors are already known to the server. Also note that due to the requirement of secure aggregation, all the values in (15) are discretized into finite field. Thus, the server can solve the system of equations (15) on finite field to get information about The following theorem establishes an important fact: the above equation system has a large solution space, which conceals the real joint distribution.
Proposition 1. Given a projection matrix P E Z Vz E Zn Yy E Z and e E Zy if m > E + m. my. there are at least qmh q my solutions to the system of equations (15).
Proof sketch for Proposition 1. The system of linear equations on Zy contains m. +y + equations and variables. Given m my + my + L, the rank of the coefficient matrix is no more than my + my + f. According to the Rouché-Capelli theorem (Brunctti & Renato, 2014) on finite fields, the solution forms least mm my E-dimensional traslation of subspace of Z As result, we know that the solution space contains at least yth m-(-m.-m, solution vectors.
Theorem I shows an important fact that the joint distribution is hidden in subspace with exponential possible distributions. Although the collusion between the client and the server not likely to happen in the cross-silo federated settings (consider our example in See. 3.1) and thus not considered in threat model, we still show that Alg. 2 practically enforce privacy given the considerably large size of the solution space.
17

---

Under review as a conference paper at ICLR 2023
H DETAILS OF DATASETS
The details for the real-world datasets used in Sec. 4.1 are provided in Table 1. The license of Credit Risk Classification (Govindaraj, Praveen) is CC BY-SA 4.0, the license of German Traffic Sign (Houben et al., 2013) is CCO: Public Domain. Other datasets without a license are from UCI Machine Learning Repository (Dua & Graff, 2017).
Table 1: Dataset details.
10
Data
Ailr #1
ART Cal
Allr #2
AR2 Cat
Aduli Income (Kohavi, 1996; Kobavi, Roany and Becker. Barry)
Occupation
14
Native Country
41
Credit Risk Classlisation (Govindrry) Pravoon)
Fealure
14
Pestune"
11
Credit Risk Classification (Govindara), Praveen)
Credit Product Type
28
Overdue Type
35
Crecht Risk Classiiiation (Giovindara,. Fraveen)
Type
Overdaa Type
Credit Risk Classifcation (Govindara), Pravecn)
Credit Product Type
28
Overdue Type III
36
German Traffic Sign (Houhen
3013)
Imagee Width
219
Traftic Sign
43
German Trafiic Sign (18ouben et al.,
2013)
Image Height
201
Traffic Sign
43
German Traliic Sign (Houben et 2013)
Upper J3lt X coordinate
21
Traliic Sign
43
German Tralfic Sign (Houlenn et al. 2013)
Upper Joli Y ovardinate
16
Tralfic Sign
10
German Traficc Sign (3ouben et al., 2013)
Lower right X coordinate
201
Tralicc Sign
Trallic Sign (Houlen al. 2013)
right coundinate
186
Trallic
Mushmoom (Schlimmer, Jeff)
Cap onlor
10
Oderr
Mushroom (Schlimmer, Jeff)
color
12
Stalk color above ring
Mushroom (Schlimmer. Jeff)
Stalk color below ring
Ring Type
Mushroom (Schlimmer, Jeff)
Spore print color
9
Habitat
Lymphography (Kosomenko, Igor und Bojan)
Siructure Clange
I DETAILS OF REGRESSION MODELS
The details of the regression models trained in feature selection in Sec. 4.2 is reported in Table 2. The training and testing splits are the same for FED-X2, centralized x²-test and model without feature selection (i.e. there 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.
J FURTHER RESULTS ON FED-X² WITH DROPOUTS
We present the results of 10%, 15%, and 20% clients dropout in Fig. 5. The results further show that FED-X² can tolerate a considerable portion of clients dropout in Round 2 of Alg. 2.
K FURTHER RESULTS FOR ONLINE FDR CONTROL
In this section, we provide further results for online FDR control. As we have shown in Fig. 4, FED-X² achieves good performance when the encoding size is larger than 200. In addition, we provide statistics for each encoding size | that was evaluated in Table 3. These results demonstrate that FED-X² performs well and comparable the centralized x² 2 when the encoding size I is increased.
L FURTHER RESULTS FOR FEATURE SELECTION
Our results in Sec. 4.2, paragraph Feature Selection, demonstrate that FED-X² performs well when encoding size 50. We conduct experiments with different encoding sizes further assess their effect on FED-X performance. In Fig. 6, we present the effect of encoding size on the ratio of the commonly-selected features between the original centralized x 2-test and FED-X2. larger ratio of caaumonly-selecte features means that FED-X² performs more closely to the original centralized x -testt And if the ratio is 1, these two algorithms select the identical features. The results in Fig. show that when the encoding size increases, the performance of FED-X approaches that of the original centralized -test.
Similar to Sec. 4.2, evaluate FED-X performance under different encoding sizes / by training the model with the features selected by FED-X2. Fig. 7 shows the results. When trained with FED- seseecce features, the model can achieve comparable accuracy the model trained with features
18

---

Under review as a conference paper at ICLR 2023
Table 2: Model details.
Task
Model Size
Learning Rate
Random Seed
F
10000 x 20
Centralized x test
40000 x 20
0.1
Without Feature Selection
167135 20
0.1
0
Error 10% dropout
Error 15% drupout
Ervor of 20% dropout
ACC 10% dropout
ACC 15% dropout
ACC of 20% dropout
Mukipiiattee Easer ADDC
Mobiplcctte Dant LADDC
Moliyficaties Easoe JACC
0.6
0/
Multylicatee
0.1-0
0:4
0.
20
100
150
200
50
100
150
200
50
100
150
700
100
150
100
(a) Synthetic Data
(b) Synthetic Data
(c) Synthetic Data 3.
(d) Synthetic Data 4.
Mullylictte AACC
Muligicatte Erner P AAC.
Menilicctte Bour 1
Meliylictnee Erst Ff
0.0
0.4
044
0.0
0.2
0.2
0.5
Data
Data
Data
(h) Data
Maltylicine Iime AXX
Milhpliatee timer ACC
Maltibbaske Eaoe ACC
0.5
0.8
0.8
0.6
0.c
0.6
06
D.G
Maliricaive
40
100
100
200
50
100
153
200
00
150
200
300
150
200
( Data
(i Data
(k) Data 7.
(1) Data 8.
Maltebhatie Ione AACE
Miltillativv time ADC
Maltblicatiee Enoe Enoe ACC
Miltribadvee
0.
06
0.6
0.4
0.4
0.4
0.8
20
100
150
300
50
100
150
2001
50
150
50
(m) Data
(n)
Data 10.
(0)
Data
(p)
Maliglaatie EroritAce
Maltehoatte 21 ACC
Mimplootee Enoor 2TAC
Maliphiazine Enour iTAC
0.5
0.5
0.4
0.4
0.2
20
15
15
Eacedinx duc
Encoddig size
Encoding size
Escedinx die
(g) Data 13.
( Data 14,
(3) Data 15.
(1 Data 16.
Figure 5: Multiplicative error and accuracy FED-X w.r.t. encoding size E w/ and w/o dropout.
selected by the original centralized =tesst Also, consistent with the results in Fig. 3 in Sec. 4.2, see that when the encoding size 2 25, models trained by FED-X" features achieve higher accuracy than that of the models without feature selection. These results further demonstrate the effectiveness of FED-X2.
M INFLUENCE OF FINITE FIELD SIZE
As shown in Fig. 8, we test the performance of FED-X2 under different finite field size We observe that when q E (216 232 261). there is almost difference in the performance. The result shows that FED-X2 is numerically stable.
19

---

Under review as a conference paper at ICLR 2023
Table 3: Detailed results for online FDR control.
#should reject
#should accept
#correct reject
#false reject
FED-X",1 10
5,900
4,100
5,144
1,392
FED-x".1=
5,900
4,100
5,328
1,356
TED-X".1== 50
5,900
4,100
5,325
1,143
FED-X , 100
5,900
4,100
5,398
943
FED-X2.1 150
5,900
4,100
5,393
765
FED-X".1 200
5,900
4.100
5,377
687
FED-X 250
5,900
4,100
5,328
615
FED-X BeD-x".1= -== 300
5,900
4,100
5,361
556
centralized -test
5,900
4,100
5,294
408
Common Feature Ratio (%))
100
80
feature selection
FED-X 1
Model Accuracy
FED-X 1 35
FED-X = 25
90-
FED-X 1-
65
centralized 2
50
50
40
10
25
35
30
60
90
120
150
Encoding
Epoch
Figure Ratio of commonly-selected features be- tween FED-X2 and original centralized x -eest.
Figure 7: Accuracy model trained w/ FED- 2
features under different encoding size
FED-X ACC FED-X
FED
of FED-x 2
Acc FED 32 bit
ACC of FED-X bit
Mulliplicativ Powwrr
0.8
0.4
0.2
50
100
150
200
Encoding size
Figure 8: Performance of FED-X² with different finite field size on synthetic data 3.
20


Reviews:
[{"review_id": "TNgv52zSwq", "reviewer": "Reviewer_Nyg7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "The paper proposed a federated framework for generating correlation tests for data distributed over multiple clients. The clients collaboratively generate a shared projection matrix, then do a projection and secure aggregation is applied to prevent data leakage from individual clients.", "summary_of_the_review": "Based on the work done in the paper, since there is missing math and explanation and the paper has weak experimentation and limited novelty its hard to accept. Additionally paper may be mis classified as a machine learning paper - I think it belongs in a stats journal.", "strength_and_weaknesses": "S1. Paper proposes a method for doing federated correlation in a distributed setting\n\nWeaknesses:\n1. The paper relies heavily on 2 separate works (one of which is quite recent). Work 1- is by Indyk et. al. for federated frequency moments estimation and Work 2 - is Bell et. al. Secure aggregation of frequency moments.  These two methods make the paper function as in paper can be summarized as composition of the two papers. Work 2 - can be replaced by any other scheme for secure aggregation. Both of these are left for readers to learn on their own! A novice reader could feel lost as math for simple stuff (like breaking of chi square into moments) is provided but the actual method (both federated computation of frequency moments) and secure aggregation are taken for granted. It would be greatly beneficial to community if authors could take the time (and pages left) to actually describe the methods in simple terms.\n2. Computations analysis seems to exclude the time required in actual secure aggregation. \n3. Paper lacks reproducibility statement \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "D5hUJ_Flp_6", "reviewer": "Reviewer_jFiZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "summary_of_the_paper": "This paper considers the problem of correlation testing in the federated framework compatible with secure aggregation. They motivate the problem of correlation testing with several applications and also give a relevant hospitals based example for the federated setting. They propose an algorithm with two simple observations - calculating correlations is equivalent to calculating moments, and one can use stable random projections to calculate moments. They provide formal security guarantees, utility guarantees and calculations of communication and computation costs. Lastly, they conduct extensive experiments on real world and simulated datasets to illustrate the efficacy of their algorithm.", "summary_of_the_review": "I think the weaknesses of the paper outweigh the strengths and the contribution is not novel enough to be published at ICLR.\n\nI really liked reading the paper since it taught me something and instructed me to add the idea of stable random projections to my toolbox. I think this paper should definitely be presented at workshops to spread the idea and submitting it to a short journal like Statistics and Probability Letters or some other empirical statistics journals which accepts short paper contributions.", "strength_and_weaknesses": "Strengths:\n1. The writing is very clear.\n2. The problem is well motivated and the explanation of the model using an example makes the paper easy to understand.\n3. The experiments seem thorough and the evaluation is done on both real world and synthetic datasets.\n\nWeaknesses:\n\nThe idea of correlation can be calculated using moments is quite obvious and if one knows the random projections literature, the idea of using stable projections to calculate $p^{th}$ moments for $p \\leq 2$ is also standard. The paper claims to make headway into non-linear secure aggregation, but using random (linear) projections in secure aggregations is not new and extending it to stable projections is great, but not enough of a contribution in and of itself, in my opinion. \n\nThe experiments are extensive and thorough, but besides the experiments studying the effects of clients dropping out, the experiments provide little additional info since the empirical results are expected from the theoretical results and they just illustrate the accuracy of stable random projections.\n\nThings that did not impact my score:\n\nThe formal security proof and utility proofs are just corollaries of the results from previous papers, and could be stated as such instead of \"theorems\". The communication and computation costs can just be remarks since they are simple calculations.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "2JVMHWsOSQ", "reviewer": "Reviewer_2ZL2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "This paper proposed a federated framework for correlation tests. And demonstrates an empirical evaluation of chi-square test and G-test under this framework.", "summary_of_the_review": "Overall I think it's a good paper, may need a better write-up.", "strength_and_weaknesses": "Strength:\n- The problem considered is important.\n- The proposed solution is intuitive and not too complex. It's also backed by theoretical analysis and security proof.\n- Numerical experiments are comprehensive and somewhat convincing.\n\nWeakness:\n- This write-up seems to be very tied to the chi-square test.\n- Is it the case that, in most cases, the weight updates already reveal a lot of information? Then lack of differential privacy could be very critical.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject