Year: 2021

Abstract:
Federated Learning (FL) has shown great potential as a privacy-preserving solution to learning from decentralized data that are only accessible to end devices (i.e., clients). In many scenarios however, a large proportion of the clients are probably in possession of low-quality data that are biased, noisy or even irrelevant. As a result, they could significantly slow down the convergence of the global model we aim to build and also compromise its quality. In light of this, we propose FEDPROF, a novel algorithm for optimizing FL under such circumstances without breaching data privacy. The key of our approach is a data representation profiling and matching scheme that uses the global model to dynamically profile data representations and allows for low-cost, lightweight representation matching. Based on the scheme we adaptively score each client and adjust its participation probability so as to mitigate the impact of low-value clients on the training process. We have conducted extensive experiments on public datasets using various FL settings. The results show that FEDPROF effectively reduces the number of communication rounds and overall time (up to 4.5x speedup) for the global model to converge and provides accuracy gain.

heading: 1 INTRODUCTION
text: With the advances in Artificial Intelligence (AI), we are seeing a rapid growth in the number of AI-driven applications as well as the volume of data required to train them. However, a large proportion of data used for machine learning are often generated outside the data centers by distributed resources such as mobile phones and IoT (Internet of Things) devices. It is predicted that the data generated by IoT devices will account for 75% of the total in 2025 (Meulen, 2018). Under this circumstance, it will be very costly to gather all the data for centralized training. More importantly, moving the data out of their local devices (e.g., mobile phones) is now restricted by law in many countries, such as the General Data Protection Regulation (GDPR)1 enforced in EU.
We face three main difficulties to learn from decentralized data: i) massive scale of end devices; ii) limited communication bandwidth at the network edge; and iii) uncertain data distribution and data quality. As an promising solution, Federated Learning (FL) (McMahan et al., 2017) is a framework for efficient distributed machine learning with privacy protection (i.e., no data exchange). A typical process of FL is organized in rounds where the devices (clients) download the global model from the server, perform local training on their data and then upload their updated local models to the server for aggregation. Compared to traditional distributed learning methods, FL is naturally more communication-efficient at scale (Konečnỳ et al., 2016; Wang et al., 2019). Nonetheless, several issues stand out.

heading: 1.1 MOTIVATION
text: 1) FL is susceptible to biased and low-quality local data. Only a fraction of clients are selected for a round of FL (involving too many clients leads to diminishing gains (Li et al., 2019)). The standard FL algorithm (McMahan et al., 2017) selects clients randomly, which implies that every client (and its local data) is considered equally important. This makes the training process susceptible to local data with strong heterogeneity and of low quality (e.g., user-generated texts (Hard et al.,
1https://gdpr.eu/what-is-gdpr/
2018) and noisy photos). In some scenarios, local data may contain irrelevant or even adversarial samples (Bhagoji et al., 2019; Bagdasaryan et al., 2020) from malicious clients (Fang et al., 2020; Bagdasaryan et al., 2020; Tolpegin et al., 2020). Traditional solutions such as data augmentation (Yoo et al., 2020) and re-sampling (Lin et al., 2017) prove useful for centralised training but applying them to local datasets may introduce extra noise (Cui et al., 2019) and increase the risk of information leakage (Yu et al., 2021). Another naive solution is to directly exclude those low-value clients with low-quality data, which, however, is often impractical because i) the quality of the data depends on the learning task and is difficult to gauge; ii) some noisy or biased data could be useful to the training at early stages (Feelders, 1996); and iii) sometimes low-quality data are very common across the clients.
In Fig. 1 we demonstrate the impact of involving ”low-value” clients by running FL over 100 clients to learn a CNN model on MNIST using the standard FEDAVG algorithm. From the traces we can see that training over clients with problematic or strongly biased data can compromise the efficiency and efficacy of FL, resulting in an inferior global model that takes more rounds to converge.
2) Learned representations can reflect data distribution and quality. Representation learning is vital to the performance of deep models because learned representations can capture the intrinsic structure of data and provide useful information for the downstream machine learning tasks (Bengio et al., 2013). In ML research, The value of representations lies in the fact that they characterize the domain and learning task and provide task-specific knowledge (Morcos et al., 2018; Kornblith et al., 2019). In the context of FL, the similarity of representations are used for refining the model update rules (Li et al., 2021; Feng & Yu, 2020), but the distributional difference between representations of heterogeneous data is not yet explored.
Our study is also motivated by a key observation that representations from neural networks tend to have Gaussian patterns. As a demonstration we trained two different models (LeNet-5 and ResNet18) on two different datasets (MNIST and CIFAR-100) separately. Fig. 2a shows the neuron-wise distribution of representations extracted from the first dense layer (FC-1) of LeNet-5. Fig. 2b shows the distribution of fused representations (in a channel-wise manner) extracted from a plain convolution layer and a residual block of ResNet-18.
These observations motivate us to study the distributional property of data representations and use it as a means to differentiate clients’ value.

heading: 1.2 CONTRIBUTIONS
text: Our contributions are summarized as the following:
• We first provide theoretical proof for the observation that data representations from neural networks tend to follow Gaussian distribution, based on which we propose a representation profiling and matching scheme for fast, low-cost comparison between different representation profiles.
• We present a novel FL algorithm FEDPROF that adaptively adjusts clients’ participation probability based on representation profile dissimilarity.
• Results of extensive experiments show that FEDPROF reduces the number of communication rounds by up to 77%, shortens the overall training time (up to 4.5x speedup) while increasing the accuracy of the global model by up to 2.5%.

heading: 2 RELATED WORK
text: Different from traditional distributed training methods (e.g., Alistarh et al. (2017); Wu et al. (2018); Zheng et al. (2017)), Federated Learning assumes strict constraints of data locality and limited communication capacity (Konečnỳ et al., 2016). Much effort has been made in optimizing FL and covers a variety of perspectives including communication (Konečnỳ et al., 2016; Niknam et al., 2020; Cui et al., 2021), update rules (Li et al., 2020; Wu et al., 2021a; Leroy et al., 2019; Luping et al., 2019), flexible aggregation (Wang et al., 2019; Wu et al., 2021b) and personalization (Fallah et al., 2020; Tan et al., 2021; Deng et al., 2020).
The control of device participation is imperative in cross-device FL scenarios (Kairouz et al., 2019; Yang et al., 2020) where the quality of local data is uncontrollable and the clients show varied value for the training task (Tuor et al., 2020). To this end, the selection of clients is pivotal to the convergence of FL over heterogeneous data and devices (Nishio & Yonetani, 2019; Wang et al., 2020b; Chai et al., 2019; Acar et al., 2020). Non-uniform client selection is widely adopted in existing studies (Li et al., 2020; Goetz et al., 2019; Cho et al., 2020; Li et al., 2019; Chen et al., 2020b; Wang et al., 2020a) and has been theoretically proven with convergence guarantees (Chen et al., 2020b; Li et al., 2019). Many approaches sample clients based on their performance (Nishio & Yonetani, 2019; Chai et al., 2020) or aim to jointly optimize the model accuracy and training time (Shi et al., 2020; Chen et al., 2020a; 2021). A popular strategy is to use loss as the information to guide client selection (Goetz et al., 2019; Lai et al., 2021; Sarkar et al., 2020). For example, AFL (Goetz et al., 2019) prioritizes the clients with high loss feedback on local data, but it is potentially susceptible to noisy and unexpected data that yield illusive loss values. Data representations are
useful in the context of FL for information exchange (Feng & Yu, 2020) or objective adaptation. For example, Li et al. (2021) introduces representation similarities into local objectives. This contrastive learning approach guides local training to avoid model divergence. Nonetheless, the study on the distribution of data representations is still lacking whilst its connection to clients’ training value is hardly explored either.

heading: 3 DATA REPRESENTATION PROFILING AND MATCHING
text: In this paper, we consider a typical cross-device FL setting (Kairouz et al., 2019), in which multiple end devices collaboratively perform local training on their own datasets Di, i = 1, 2, ..., n. The server owns a validation dataset D∗ for model evaluation. Every dataset is only accessible to its owner.
Considering the distributional pattern of data representations (Fig. 2) and the role of the global model in FL, we propose to profile the representations of local data using the global model. In this section, we first provide theoretical proof to support our observation that representations from neural network models tend to follow Gaussian distribution. Then we present a novel scheme to profile data representations and define profile dissimilarity for fast and secure representation comparison.

heading: 3.1 GAUSSIAN DISTRIBUTION OF REPRESENTATIONS
text: We first make the following definition to facilitate our analysis. Definition 1 (The Lyapunov’s condition). A set of random variables {Z1, Z2, . . . , Zv} satisfy the Lyapunov’s condition if there exists a δ such that
lim v→∞
1
s2+δ v∑ k=1 E [ |Zk − µk|2+δ ] = 0, (1)
where µk = E[Zk], σ2k = E[(Zk − µk)2] and s = √∑v k=1 σ 2 k.
The Lyapunov’s condition can be intuitively explained as a limit on the overall variation (with |Zk− µk|2+δ being the (2 + δ)-th moment of Zk) of a set of random variables. Now we present Proposition 1 and Proposition 2. The Propositions provide theoretical support for our representation profiling and matching method to be introduced in Section 3.2. Proposition 1. The representations from linear operators (e.g., a pre-activation dense layer or a plain convolutional layer) in a neural network tend to follow the Gaussian distribution if the layer’s weighted inputs satisfy the Lyapunov’s condition. Proposition 2. The fused representations2 from non-linear operators (e.g., a hidden layer of LSTM or a residual block of ResNet) in a neural network tend to follow the Gaussian distribution if the layer’s output elements satisfy the Lyapunov’s condition.
The proofs of Propositions 1 and 2 are provided in Appendices A.1 and A.2, respectively.
We base our proof on the Lyapunov’s CLT which assumes independence between the variables. The assumption theoretically holds by using the Bayesian network concepts: let X denote the layer’s input and Hk denote the k-th component in its output. The inference through the layer produces dependencies X → Hk for all k. According to Local Markov Property, we have Hi independent of any Hj (j ̸= i) given X . Also, the Lyapunov’s condition is typically met when the model is properly initialized and batch normalization is applied. Next, we discuss the proposed representation profiling and matching scheme.

heading: 3.2 DISTRIBUTIONAL PROFILING AND MATCHING
text: Based on the Gaussian pattern of representations, we compress the data representations statistically into a compact form called representation profiles. The profile produced by the global model w on
2Fused representations refer to the sum of elements in the original representations produced by a single layer (channel-wise for a residual block).
a dataset D, denoted by RP (w,D), has the following format:
RP (w,D) = {N (µi, σ2i )} q i=1, (2)
where q is the profile length determined by the dimensionality of the representations. For example, q is equal to the number of kernels for channel-wise fused representations from a convolutional layer. The tuple (µi, σ2i ) contains the mean and the variance of the i-th representation element.
Local representation profiles are generated by clients and sent to the server for comparison (the cost of transmission is negligible considering each profile is only q × 8 bytes). Let RPk denote the local profile from client k, and RP ∗ denote the baseline profile (generated in model evaluation) on the server. The dissimilarity between RPk and RP ∗, denoted by div(RPk, RP ∗), is defined as:
div(RPk, RP ∗) =
1
q q∑ i=1 KL(N (k)i ||N ∗ i ), (3)
where KL(·) denotes the Kullback–Leibler (KL) divergence. An advantage of our profiling scheme is that a much simplified KL divergence formula can be adopted because of the Gaussian distribution property (see Roberts & Penny (2002, Appendix B) for details), which yields:
KL(N (k)i ||N ∗ i ) = log
σ∗i
σ (k) i
+ (σ
(k) i ) 2 + (µ (k) i − µ∗i )2
2(σ∗i ) 2
, (4)
Eq. (4) computes the KL divergence without calculating any integral, which is computationally cost-efficient. Besides, the computation of profile dissimilarity can be performed under the Homomorphic Encryption for minimum knowledge disclosure (see Appendix D for details).

heading: 4 THE TRAINING ALGORITHM FEDPROF
text: Our research aims to optimize the global model over a large group of clients (datasets) of disparate training value. Given the client set U(|U | = N), let Dk denote the local dataset on client k and D∗ the validation set on the server, We formulate the optimization problem in (5) where the coefficient ρk differentiates the importance of the local objective functions Fk(w) and depends on the data in Dk. Our global objective is in a sense similar to the agnostic learning scenario (Mohri et al., 2019) where a non-uniform mixture of local data distributions is implied.
argmin w F (w) = N∑ k=1 ρkFk(w), (5)
where w is the parameter set of the global model. The coefficients {ρk}Nk=1 add up to 1. Fk(w) is client k’s local objective function of training based on the loss function ℓ(·):
Fk(w) = 1 |Dk| ∑
(xi,yi)∈Dk
ℓ(xi, yi;w), (6)
Involving the ”right” clients facilitates the convergence. With this motivation we score each client with λk each round based on the representation profile dissimilarity:
λk = exp ( − α · div(RPk(vk), RP ∗(vk) ) , (7)
where vk is the version of RPk (i.e., the version of the global model that client k receives) and α is a preference factor deciding how biased the selection strategy needs to be towards the clients with small profile dissimilarity (i.e., higher training value). With α = 0, our strategy is equivalent to random selection. The scores connect the representation profiling and matching scheme to the design of the selective client participation strategy adopted in our FL training algorithm FEDPROF, which is outlined in Algorithm 1 (see Appendix B for a detailed version with both client and server processes). The key steps of our algorithm are local representation profiling (line 5), baseline representation profiling (line 9) and client scoring (line 3). Fig. 3 illustrates the workflow of the proposed algorithm from representation profiling, matching to scheduling.
Algorithm 1: the FEDPROF algorithm Input: maximum number of rounds Tmax, iterations per round E, fraction C
1 Initialize global model w and generate baseline profile RP ∗ 2 Collect initial representation profiles {RPk}k∈U from all clients
for round T ← 1 to Tmax do 3 Update client scores {λk}k∈U and compute Λ = ∑ k∈U λk 4 S ← Choose K = N · C clients by probability distribution {λkΛ }k∈U for client k in S in parallel do 5 RPk ← updateProfile(k,w, T − 1) 6 wk ← localTraining(k,w,E) end 7 Collect local profiles from the clients in S 8 Update w via model aggregation 9 Evaluate w and update RP ∗
end 10 return w
The convergence rate of FL algorithms with opportunistic client selection (sampling) has been extensively studied in the literature (Li et al., 2019; Chen et al., 2020b; Wang et al., 2019). Inspired by these studies, we present Theorem 1 to guarantee the global model’s convergence for our algorithm. Similar to Stich et al. (2018); Zhang et al. (2013); Li et al. (2019), we assume that {Fk}Nk=1 are L-smooth and µ-strongly convex and that in expectation, the variance of local stochastic gradients are bounded by ϵ2 and their squared norms are bounded by G2. For each local update step t we define S(t) as the set of selected clients in the associated round. Theorem 1. Using partial aggregation and a strategy π that selects clients by the probability distribution {qk}Nk=1, the global model w(t) converges in expectation by having qk = ρk, an aggregation interval E ≥ 1 and a decreasing step size (learning rate) ηt = 2µ(t+γ) .
E [ F (w(t)) ] − F ∗ ≤ L
(γ + t) (2(B + C) µ2 + γ + 1 2 ∆1 ) , (8)
where t ∈ TA = {nE|n = 1, 2, . . .}, γ = max{ 8Lµ , E}−1, B = ∑N k=1 ρ 2 kϵ 2 k+6LΓ+8(E−1)2G2, C = 4KE 2G2, Γ = F ∗ − ∑N k=1 ρkF ∗ k , ∆1 = E∥w̄(1)− w∗∥2, K = |S(t)| = N · C.
The proof of Theorem 1 is provided in Appendix C.

heading: 5 EXPERIMENTS
text: We conducted extensive experiments to evaluate FEDPROF under various FL settings. Apart from FEDAVG (McMahan et al., 2017), we also reproduced several state-of-the-art FL algorithms for comparison. For fair comparison, the algorithms are grouped by the aggregation method (i.e., full aggregation and partial aggregation) and configured following the hyper-parameter settings in their papers (if any). Table 1 summarizes these FL algorithms. Note that our algorithm can adapt to both aggregation methods.

heading: 5.1 EXPERIMENT SETUP
text: We built our simulated FL system and implemented the algorithms based on the Pytorch framework (Build 1.7.0). We first set up a Small-scale Task (S-Task) to learn a multi-layer feed-forward network model from decentralized sensor data for predicting carbon monoxide (CO) and nitrogen oxides (NOx) emissions using the GasTurbine3 dataset. Next, we set up a Large-scale Task (L-Task) to train a CNN over a large population of user devices for image classification (EMNIST4). In both tasks, data sharing is not allowed between any parties. The data are non-IID across the end devices.5 We introduce a diversity of noise into the local datasets on end devices to simulate the discrepancy in data quality. The S-Task is performed over 50 sensor clients and 50% of them produce noisy data (including 10% invalid). The population for L-Task contains 1000 end devices across which the data spread with strong class imbalance – roughly 60% of the samples on each device fall into the same class. 15% of the local datasets in the L-Task are irrelevant images whereas another 45% of them are low-quality images (blurred or affected by salt-and-pepper noise). Considering the population of the clients, the setting of the selection fraction C is based on the scale of the training participants suggested by Kairouz et al. (2019). For both tasks, the clients are heterogeneous in terms of both performance and communication bandwidth. More experimental settings are listed in Table 4 in Appendix E where the environment setup is also given in details.

heading: 5.2 EVALUATION RESULTS
text: We evaluate the performance of our FEDPROF algorithm in terms of the efficacy (best accuracy achieved) and efficiency (costs for convergence) in establishing a global model for the two tasks. Tables 2 and 3 report the average results of multiple runs with standard deviations for our algorithm. Figs. 4 and 5 plot the accuracy traces from the round-wise evaluations of the global model.
1) Convergence in different aggregation modes: Our results show a great difference in convergence rate under different aggregation modes. From Figs. 4 and 5, we observe that partial aggregation facilitates faster convergence of the global model than full aggregation, which is consistent with the observations made by Li et al. (2019). The advantage is especially obvious in the L-Task where partial aggregation requires much fewer communication rounds to reach the 90% accuracy. Our FEDPROF algorithm yields the fastest convergence in both groups of comparison for both tasks because selective participation benefits both aggregation methods.
3https://archive.ics.uci.edu/ml/datasets/Gas+Turbine+CO+and+NOx+Emission+Data+Set 4https://www.nist.gov/itl/products-and-services/emnist-dataset. We use the digits subset of EMNIST. 5In the S-Task, local datasets are of different sizes that follow a Gaussian distribution. In the L-Task, local
data are largely imbalanced where around 60% of the samples on each client have the same class label.
2) Best accuracy of the global model: Through the training process of FL, the global model is evaluated each round on the server. The best global model obtained thus far is stored on the server. As shown in the 2nd column of Tables 2 and 3, our FEDPROF algorithm improves the accuracy achieved by 2.5% when compared against the baselines (FEDAVG and FEDAVG-RP). The AFL algorithm uses a loss-oriented client selection strategy, which shows the closest performance to our algorithm in the L-Task but the worst accuracy in the S-Task.
3) Total communication rounds for convergence: The number of communication rounds required for reaching convergence is a key indicator to the efficiency of FL. In the S-Task, our algorithm takes less than half the communication rounds required by other algorithms in most cases. In the L-Task with C=0.05, our algorithm reaches 90% accuracy within 100 rounds whilst FEDAVG and CFCFM need more than 200. In this case, FEDPROF also achieves approximately 7% higher accuracy in 50 rounds. Partial aggregation turns out to be much more communication-efficient: FEDAVG-RP
needs 8 rounds to reach the accuracy target for the S-Task and 12 rounds for the L-Task, whilst our algorithm reduces the numbers to 5 and 8, respectively.
4) Total time needed for convergence: The overall time consumption is closely related to total communication rounds needed for convergence and the time cost for each round. Algorithms requiring more rounds to converge typically take longer to reach the accuracy target except the case of CFCFM, which priorities the clients that work faster. Using FEDAVG as the baseline, CFCFM accelerates the training process by 2.1x whilst our algorithm provides a 4.5x speedup for achieving the same target accuracy (S-Task, C=0.3). FEDPROF also has a clear advantage over FEDAVGRP, FEDPROX and FEDADAM in the partial aggregation group where it shows a 2.6x speedup over FEDAVG-RP in the S-Task with C=0.2.
5) Energy consumption of end devices: A main concern for the end devices, as the participants of FL, is their power usage (Watt hours). Full aggregation methods experience slower convergence and thus endure higher energy cost on the devices. For example, with a small selection fraction C=0.05 in the L-Task, FEDAVG and CFCFM consume over 60Wh to reach the target accuracy. In this case, our algorithm reduces the cost by more than a half (28.22Wh). With the partial aggregation mode, the reduction by our algorithm is up to 62% (S-Task, C = 0.2). Considering all the cases, FEDPROF achieves the target accuracy with the least energy cost, providing an reduction of 29% ∼ 53%. 6) Differentiated participation with FEDPROF: Fig. 6 reflects the preference of our selection strategy. In the S-Task we can observe that the clients with useless samples or noisy data get significantly less involved (<10 on average) in training. In the L-Task our algorithm also effectively limits (basically excludes) the clients who owns the image data of poor quality (i.e., irrelevant or severely blurred), whereas the clients with moderately noisy images are selected with reduced frequency as compared to those with normal data. A potential issue of having the preference towards some of the devices is about fairness. Nonetheless, one can apply our algorithm together with an incentive mechanism (e.g., Yu et al. (2020)) to address it.

heading: 6 CONCLUSION
text: Federated learning provides a privacy-preserving approach to decentralized training but is vulnerable to the heterogeneity and uncertain quality of on-device data. In this paper, we use a novel approach to address the issue without violating the data locality restriction. We first provide key insights for the distribution of data representations and then develop a dynamic data representation profiling and matching scheme. Based on the scheme we propose a selective FL training algorithm FEDPROF that adaptively adjusts clients’ participation chance based on their profile dissimilarity. We have conducted extensive experiments on public datasets under various environment settings. Evaluation results show that our algorithm significantly improves the efficiency of FL and reduces the time and energy costs for the global model to converge.

heading: A PROOF OF PROPOSITIONS

heading: A.1 PROOF OF PROPOSITION 1
text: Without loss of generality, we provide the proof of Proposition 1 for the pre-activation representations from dense (fully-connected) layers and standard convolutional layers, respectively. The results can be easily extended to other linear neural operators.

heading: Dense layers
text: Proof. Let Ω = {neu1, neu2, ..., neuq} denote a dense layer (with q neurons) of any neural network model and Hk denote the pre-activation output of neuk in Ω. We first provide the theoretical proof to support the observation that Hk tends to follow the Gaussian distribution.
Let χ = Rv denote the input feature space (with v features) and assume the feature Xi (which is a random variable) follows a certain distribution ζi(µi, σ2i ) (not necessarily Gaussian) with finite mean µi = E[Xi] and variance σ2i = E[Xi − µi]. For each neuron neuk, let wk = [wk,1 wk,2 . . . wk,v] denote the neuron’s weight vector, bk denote the bias, and Zk,i = Xiwk,i denote the i-th weighted input. Let Hk denote the output of neuk. During the forward propagation, we have:
Hk = Xw T k + bk
= v∑ i=1 Xiwk,i + bk
= v∑ i=1 Zk,i + bk. (9)
Apparently Zk,i is a random variable because Zk,i = Xiwk,i (where the weights wk,i are constants during a forward pass), thus Hk is also a random variable according to Eq. (9).
In an ideal situation, the inputs variables X1, X2, . . . , Xv may follow a multivariate Gaussian distribution, in which case Proposition 1 automatically holds due to the property of multivariate normal distribution that every linear combination of the components of the random vector (X1, X2, . . . , Xv)
T follows a Gaussian distribution (Lemons, 2003). In other words, Hk = X1wk,1 + X2wk,2 + . . . + Xvwk,v + bk is a normally distributed variable since wk,i and bk (k = 1, 2, . . . , v) are constants in the forward propagation. A special case for this condition is that X1, X2, . . . , Xv are independent on each other and Xi follows a Gaussian distribution N (µi, σ2i ) for all i = 1, 2, . . . , v. In this case, by the definition of Zk,i, we have:
Zk,i = Xiwk,i ∼ N ( wk,iµi, (wk,iσi) 2 ) , (10)
where Z1, Z2, . . . , Zv are independent on each other. Combining Eqs. (9) and (10), we have:
Hk ∼ N ( v∑ i=1 wk,iµi + bk, v∑ i=1 (wk,iσi) 2 ) , (11)
For more general cases where X1, X2, . . . , Xv are not necessarily normally distributed, we assume the weighted inputs Zk,i of the dense layer satisfy the Lyapunov’s condition (see definition 1). As a result, we have the following according to the Central Limit Theorem (CLT) (Billingsley, 2008) considering that Xi follows ζi(µi, σ2i ):
1
sk v∑ i=1 ( Zk,i − wk,iµi ) d−→ N (0, 1) (12) where sk = √∑v i=1 ( wk,iσi )2 andN (0, 1) denotes the standard normal distribution. Equivalently, for every neuk we have:
v∑ i=1 Zk,i d−→ N ( v∑ i=1 wk,iµi, s 2 k) (13)
Combining Eqs. (9) and (13) we can derive that:
Hk d−→ N ( v∑ i=1 wk,iµi + bk, s 2 k), (14)
which means that Hk(k = 1, 2, . . . , v) tend to follow Gaussian distribution and proves our Proposition 1 for fully-connected layers.

heading: Convolutional layers
text: Proof. Standard convolution in CNNs is also a linear transformation of the input feature space and its main difference from dense layers rests on the restricted size of receptive field. Without loss of generality, we analyze the representation (output) of a single kernel. To facilitate our analysis for convolutional layers, let C denote the number of input channels and K denote the kernel size. For ease of presentation, we define a receptive field mapping function Θ(k, i, j) that maps the positions (k for channel index, i and j for indices on the same channel) of elements in the feature map (i.e., the representations) to the input features. For the k-th kernel, let Wk denote its weight tensor (with Wk,c being the weight matrix for channel c) and bk its bias.
Given the corresponding input patch XΘ(k,i,j), The element Hk,i,j of the representations from a convolutional layer can be formulated as:
Hk,i,j = C∑ c=1 K∑ i′=1 K∑ j′=1 ( XΘ(k,i,j) ◦Wk,c ) i′,j′ + bk, (15)
where ◦ denotes Hadamard product. The three summations reduce the results of element-wise product between the input patch and the k-th kernel to the correspond representation element Hk,i,j in the feature map. For ease of presentation, here we use the notation Z
(k) c,i′,j′ to replace( XΘ(k,i,j) ◦Wk,c ) i′,j′ and let ζ(µc,i′,j′ , σ2c,i′,j′) be the distribution that Z (k) c,i′,j′ follows. Note that ζ can be any distribution since we do not make any distributional assumption on Z(k)c,i′,j′ .
With the notations, Eq. (15) can be rewritten in a similar form to Eq. (9):
Hk,i,j = C∑ c=1 K∑ i′=1 K∑ j′=1 Z (k) c,i′,j′ + bk. (16)
We use the condition that the random variables Z(k)c,i′,j′ satisfy the Lyapunov’s condition, i.e., there exists a δ such that
lim C×K2→∞
1
s2+δ C∑ c=1 K∑ i′=1 K∑ j′=1 E [ |Z(k)c,i′,j′ − µc,i′,j′ | 2+δ ] = 0, (17)
where s = √∑C
c=1 ∑K i′=1 ∑K j′=1 σ 2 c,i′,j′ .
Then according to the Lyapunov CLT, the following holds:
Hk,i,j d−→ N ( ∑ c,i′,j′∈Θ(k,i,j) µc,i′,j′ + bk, ∑ c,i′,j′∈Θ(k,i,j) σ2c,i′,j′), (18)
which proves our Proposition 1 for standard convolution layers.

heading: A.2 PROOF OF PROPOSITION 2
text: Without loss of generality, we prove Proposition 2 for the fused representations from the LSTM layer and the residual block of ResNet models, respectively. The results can be easily extended to other non-linear neural operators.
LSTM
Proof. Long Short-Term Memory (LSTM) models are popular for extracting useful representations from sequence data for tasks such as speech recognition and language modeling. Each LSTM layer contains multiple neural units. For the k-th unit, it takes as input the current input feature vector Xt = (Xt,1, Xt,2, . . .), hidden state vector Ht−1 and its cell state ct−1,k. The outputs of the unit are its new hidden state ht,k and cell state ct,k. In this paper, we study the distribution of ht,k. Multiple gates are adopted in an LSTM unit: by it,k, ft,k, gt,k and ot,k we denote the input gate, forget gate, cell gate and output gate of the LSTM unit k at time step t. The update rules of these gates and the cell state are:
it,k = sigmoid(W(i)k[Ht−1, Xt] + b(i)k),
ft,k = sigmoid(W(f)k[Ht−1, Xt] + b(f)k),
gt,k = tanh(W(g)k[Ht−1, Xt] + b(g)k),
ot,k = sigmoid(W(o)k[Ht−1, Xt] + b(o)k),
ct,k = ft,k · ct−1,k + it,k · gt,k, (19)
where the W(i)k, W(f)k, W(g)k and W(o)k are the weight parameters and b(i)k, b(f)k, b(g)k and b(o)k are the bias parameters for the gates.
The output of the LSTM unit ht,k is calculated as the following:
ht,k = ot,k · tanh(ct,k). (20)
Using the final hidden states hT,k (with T being the length of the sequence) as the elements of the layer-wise representation, we apply the following layer-wise fusion to further produce H over all the hT,k in a single LSTM layer:
H = d∑ k=1 hT,k, (21)
where d is the dimension of the LSTM layer. Again, by ζ(µk, σ2k) we denote the distribution of hT,k (where the notation T is dropped here since it is typically a fixed parameter). With {hT,k|k = 1, 2, . . . , d} satisfying the Lyapunov’s condition and by Central Limit Theorem H , tends to follow the Gaussian distribution:
H d−→ N ( d∑ i=1 µk, d∑ i=1 σ2k), (22)
which proves the Proposition 2 for layer-wise fused representations from LSTM.

heading: Residual blocks
text: Proof. Residual blocks are the basic units in the Residual neural network (ResNet) architecture (He et al., 2016). A typical residual block contains two convolutional layers with batch normalization (BN) and uses the ReLU activation function. The input of the whole block is added to the output of the second convolution (after BN) through a skip connection before the final activation. Since the convolution operators are the same as we formulate in the second part of Section A.1, here we use the notation Ψ(X) to denote the sequential operations of convolution on X followed by BN, i.e., Ψ(X) ≜ BN(Conv(X)). Again, we reuse the receptive field mapping Θ(k, i, j) as defined in Section A.1 to position the inputs of the residual block corresponding to the element Zk,i,j in the output representation of the whole residual block.
Let X denote the input of the residual block and Zk,i,j denote an element in the output tensor of the whole residual block. Then we have:
Zk,i,j = f ( Xk,i,j +BN ( Conv ( f ( BN(Conv(XΘ(k,i,j))) )))) = f ( Xk,i,j +Ψ ( f(Ψ(XΘ(k,i,j))) )) , (23)
where f is the activation function (ReLU).
We perform channel-wise fusion on the representation from the residual block to produce Hk for the k-th channel:
Hk = dH∑ i=1 dW∑ j=1 Zk,i,j , (24)
where dH and dW are the dimensions of the feature map and k is the channel index.
Let ζ(µk,i,j , σ2k,i,j) denote the distribution that Zk,i,j follows. Then we apply the Lyapunov’s condition to the representation elements layer-wise, i.e.,
lim dW×dH→∞
1
s2+δk dH∑ i=1 dW∑ j=1 E [ |Zk,i,j − µk,i,j |2+δ ] = 0, (25)
where sk = √∑dH
i=1 ∑dW j=1 σ 2 k,i,j .
With the above condition satisfied, by CLT Hk (the fused representation on channel k) tends to follow the Gaussian distribution:
Hk d−→ N ( dH∑ i=1 dW∑ j=1 µk,i,j , dH∑ i=1 dW∑ j=1 σ2k,i,j), (26)
which proves the Proposition 2 for channel-wise fused representations from any residual block.

heading: B PSEUDO-CODE OF FEDPROF (DETAILED VERSION)
text: See Algorithm 2 for a complete version of the proposed training algorithm.

heading: C CONVERGENCE ANALYSIS
text: In this section we provide the proof of the proposed Theorem 1. The analysis is mainly based on the results provided by Li et al. (2019). We first introduce several notations to facilitate the analysis.

heading: C.1 NOTATIONS
text: Let U (|U | = N ) denote the full set of clients and S(t) (|S(t)| = K) denote the set of clients selected for participating. By wk(t) we denote the local model on client k at time step t. We define an auxiliary sequence vk(t) for each client to represent the immediate local model after a local SGD update. Note that vk(t) is updated from vk(t− 1) with learning rate ηt−1:
vk(t) = wk(t− 1)− ηt−1∇Fk(wk(t− 1), ξk,t−1), (27) where∇Fk(wk(t−1), ξk,t−1) is the stochastic gradient computed over a batch of data ξk,t−1 drawn from Dk with regard to wk(t− 1).
We also define two virtual sequences v̄(t) = ∑N
k=1 ρkvk(t) and w̄(t) = Aggregate({vk(t)}k∈S(t)) for every time step t (Note that the actual global model w(t) is only updated at the aggregation steps TA = {E, 2E, 3E, . . .}). Given an aggregation interval E ≥ 1, we provide the analysis for the partial aggregation rule that yields w̄(t) as:
w̄(t) = 1
K ∑ k∈S(t) vk(t), (28)
where S(t) (|S(t)| = K) is the selected set of clients for the round ⌈ tE ⌉ that contains step t. At the aggregation steps TA, w(t) is equal to w̄(t), i.e., w(t) = w̄(t) if t ∈ TA. To facilitate the analysis, we assume each client always performs model update (and synchronization) to produce vk(t) and v̄(t) (but obviously it does not affect the resulting w̄ and w for k /∈ S(t)).
wk(t) = { vk(t), if t /∈ TA w̄(t), if t ∈ TA
(29)
Algorithm 2: the FEDPROF protocol (detailed version) Input : maximum number of rounds Tmax, local iterations per round E, client set U , client fraction C, validation set D∗; Output: the global model w // Server process: running on the server
1 Initialize global model w using a seed 2 v ← 0 // version of the latest global model 3 Broadcast the seed to all clients for identical model initialization 4 Collect initial profiles {RPk}k∈U from all the clients 5 vk ← 0, ∀k ∈ U 6 Generate initial baseline profile RP ∗(0) on D∗ 7 K ← |U | · C
for round T ← 1 to Tmax do 8 Calculate div(RPk(vk), RP ∗(vk)) for each client k 9 Update client scores {λk}k∈U and compute Λ = ∑ k∈U λk
10 S ← Choose K clients by probability distribution {λkΛ }k∈U 11 Distribute w to the clients in S for client k in S in parallel do 12 vk ← v, ∀k ∈ S 13 RPk(vk)← updateProfile(k,w, v) 14 wk ← localTraining(k,w,E) end 15 Collect local profiles from the clients in S 16 Update w via model aggregation 17 v ← T 18 Evaluate w and generate RP ∗(v)
end 19 return w
// Client process: running on client k updateProfile(k,w, v):
20 Generate RPk on Dk with the global w received 21 Label profile RPk with version number v 22 Return RPk
return localTraining(k,w,E):
23 wk ← w for step e← 1 to E do 24 Update wk using gradient-based method end 25 Return wk return
For ease of presentation, we also define two virtual gradient sequences: ḡ(t) =∑N k=1 ρk∇Fk(wk(t)) and g(t) = ∑N k=1 ρk∇Fk(wk(t), ξk,t). Thus we have E[g(t)] = ḡ(t) and v̄(t) = w̄(t− 1)− ηt−1g(t− 1).

heading: C.2 ASSUMPTIONS
text: We formally make four assumptions to support our analysis of convergence. Assumptions 1 and 2 are standard in the literature (Li et al., 2019; Wang et al., 2019; Cho et al., 2020) defining the convexity and smoothness properties of the objective functions. Assumptions 3 and 4 bound the variance of the local stochastic gradients and their squared norms in expectation, respectively. These two assumptions are also made in by Li et al. (2019). Assumption 1. F1, F2, . . . , FN are L-smooth, i.e., for any k ∈ U , x and y: Fk(y) ≤ Fk(x)+ (y− x)T∇Fk(x) + L2 ∥y − x∥ 2 2
It is obvious that the global objective F is also L-smooth as a linear combination of F1, F2, . . . , FN with ρ1, ρ2, . . . , ρN being the weights.
Assumption 2. F1, F2, . . . , FN are µ-strongly convex, i.e., for all k ∈ U and any x, y: Fk(y) ≥ Fk(x) + (y − x)T∇Fk(x) + µ2 ∥y − x∥ 2 2
Assumption 3. The variance of local stochastic gradients on each device is bounded: For all k ∈ U , E∥∇Fk(wk(t), ξt,k)− Fk(wk(t))∥2 ≤ ϵ2
Assumption 4. The squared norm of local stochastic gradients on each device is bounded: For all k ∈ U , E∥∇Fk(wk(t), ξt,k)∥2 ≤ G2

heading: C.3 KEY LEMMAS
text: To facilitate the proof of our main theorem, we first present several key lemmas.
Lemma 1 (Result of one SGD step). Under Assumptions 1 and 2 and with ηt < 14L , for any t it holds true that E∥v̄(t+1)−w∗∥2 ≤ (1−ηtµ)E∥w̄(t)−w∗∥2+η2tE∥gt−ḡt∥2+6Lη2tΓ+2E [ N∑ k=1 ρk∥wk(t)−w̄(t)∥2 ] , (30) where Γ = F ∗ − ∑N k=1 ρkF ∗ k .
Lemma 2 (Gradient variance bound). Under Assumption 3, one can derive that
E∥gt − ḡt∥2 ≤ N∑
k=1
ρ2kϵ 2 k. (31)
Lemma 3 (Bounded divergence of wk(t)). Assume Assumption 4 holds and a non-increasing step size ηt s.t. ηt ≤ 2ηt+E for all t = 1, 2, . . ., it follows that
E [ N∑ k=1 ρk∥wk(t)− w̄(t)∥2 ] ≤ 4η2t (E − 1)2G2. (32)
Lemmas 1, 2 and 3 hold for both full and partial participation and are independent of the client selection strategy. We refer the readers to Li et al. (2019) for their proofs and focus our analysis on opportunistic selection.
The next two lemmas give important properties of the aggregated model w̄ as a result of partial participation and non-uniform client selection/sampling.
Lemma 4 (Unbiased aggregation). For any aggregation step t ∈ TA and with qk = ρk in the selection of S(t), it follows that
ES(t)[w̄(t)] = v̄(t). (33)
Proof. First, we present a key observation given by Li et al. (2019) as an important trick to handle the randomness caused by client selection with probability distribution {qk}Nk=1. By taking the expectation over S(t), it follows that
ES(t) ∑
k∈S(t)
Xk = KES(t)[Xk] = K N∑ k=1 qkXk. (34)
Let qk = ρk, take the expectation of w̄(t) over S(t) and notice that v̄(t) = ∑ k∈U ρkvk(t):
ES(t)[w̄(t)] = ES(t) [ 1 K ∑ k∈S(t) vk(t) ]
= 1
K ES(t) [ ∑ k∈S(t) [vk(t) ]
= 1
K KES(t)[vk(t)] = ∑ k∈U qkvk(t)
= v̄(t).
Lemma 5 (Bounded variance of w̄(t)). For any aggregation step t ∈ TA and with a non-increasing step size ηt s.t. ηt ≤ 2ηt+E−1, it follows that
ES(t)∥w̄(t)− v̄(t)∥2 ≤ 4
K η2t−1E 2G2. (35)
Proof. First, one can prove that vk(t) is an unbiased estimate of v̄(t) for any k: ES(t)[vk(t)] = ∑ k∈U qkvk(t) = v̄(t). (36)
Then by the aggregation rule w̄(t) = 1K ∑ k∈S(t) vk(t), we have:
ES(t)∥w̄(t)− v̄(t)∥2 = 1
K2 ES(t)∥Kw̄(t)−Kv̄(t)∥2
= 1
K2 ES(t)∥ ∑ k∈S(t) vk(t)− K∑ k=1 v̄(t)∥2
= 1
K2 ES(t)∥ ∑ k∈S(t) ( vk(t)− v̄(t) ) ∥2
= 1
K2
( ES(t) ∑ k∈S(t) ∥vk(t)− v̄(t)∥2
+ ES(t) ∑
i,j∈S(t),i̸=j ⟨vi(t)− v̄(t), vj(t)− v̄(t)⟩︸ ︷︷ ︸ =0
) , (37)
where the second term on the RHS of (37) equals zero because {vk(t)}k∈U are independent and unbiased (see Eq. 36). Further, by noticing t − E ∈ TA (because t ∈ TA) which implies that wk(t− E) = w̄(t− E) since the last communication, we have:
ES(t)∥w̄(t)− v̄(t)∥2 = 1
K2 ES(t) ∑ k∈S(t) ∥vk(t)− v̄(t)∥2
= 1
K2 KES(t)∥vk(t)− v̄(t)∥2
= 1
K ES(t)∥
( vk(t)− w̄(t− E) ) − ( v̄(t)− w̄(t− E) ) ∥2
≤ 1 K ES(t)∥vk(t)− w̄(t− E)∥2, (38)
where the last inequality results from E[vk(t)−w̄(t−E)] = v̄(t)−w̄(t−E) and that E∥X−EX∥2 ≤ E∥X∥2. Further, we have:
ES(t)∥w̄(t)− v̄(t)∥2 ≤ 1
K ES(t)∥vk(t)− w̄(t− E)∥2
= 1
K N∑ k=1 qkES(t)∥vk(t)− w̄(t− E)∥2
= 1
K N∑ k=1 qk ES(t)∥ t−1∑
i=t−E ηi∇Fk(wk(i), ξk,i)∥2︸ ︷︷ ︸
Z1
. (39)
Let im = argmaxi ∥∇Fk ( wk(i), ξk,i ) ∥, i ∈ [t−E, t−1]. By using the Cauchy-Schwarz inequality, Assumption 4 and choosing a non-increasing ηt s.t. ηt ≤ 2ηt+E−1, we have:
Z1 = ES(t)∥ t−1∑
i=t−E ηi∇Fk(wk(i), ξk,i)∥2
= t−1∑ i=t−E t−1∑ j=t−E ES(t)⟨ηi∇Fk ( wk(i), ξk,i ) , ηj∇Fk ( wk(j), ξk,j ) ⟩ ≤ t−1∑
i=t−E t−1∑ j=t−E ES(t) [ ∥ηi∇Fk ( wk(i), ξk,i ) ∥ · ∥ηj∇Fk ( wk(j), ξk,j ) ∥ ]
≤ t−1∑
i=t−E t−1∑ j=t−E ηiηj · ES(t)∥∇Fk ( wk(im), ξk,im ) ∥2
≤ t−1∑
i=t−E t−1∑ j=t−E η2t−E · ES(t)∥∇Fk ( wk(im), ξk,im ) ∥2
≤ 4η2t−1E2G2. (40)
Plug Z1 back into (39) and notice that ∑N k=1 qk = 1, we have:
ES(t)∥w̄(t)− v̄(t)∥2 ≤ 1
K N∑ k=1 qk4η 2 tE 2G2
= 4
K η2t−1E 2G2.

heading: C.4 PROOF OF THEOREM 1
text: Proof. Taking expectation of ∥w̄(t)− w∗∥2, we have:
E∥w̄(t)− w∗∥2 = ES(t)∥w̄(t)− v̄(t) + v̄(t)− w∗∥2
= E∥w̄(t)− v̄(t)∥2︸ ︷︷ ︸ A1 +E∥v̄(t)− w∗∥2︸ ︷︷ ︸ A2 +E⟨w̄(t)− v̄(t), v̄(t)− w∗⟩︸ ︷︷ ︸ A3
(41)
where A3 vanishes because w̄(t) is an unbiased estimate of v̄(t) by first taking expectation over S(t) (Lemma 4).
To bound A2 for t ∈ TA, we apply Lemma 1:
A2 = E∥v̄(t)− w∗∥2 ≤ (1− ηt−1µ)E∥w̄(t− 1)− w∗∥2 + η2t−1E∥gt−1 − ḡt−1∥2︸ ︷︷ ︸ B1
+ 6Lη2t−1Γ + E [ N∑ k=1 ρk∥wk(t− 1)− w̄(t− 1)∥2 ]
︸ ︷︷ ︸ B2
. (42)
Then we use Lemmas 2 and 3 to bound B1 and B2 respectively, which yields:
A2 = E∥v̄(t)− w∗∥2 ≤ (1− ηt−1µ)E∥w̄(t− 1)− w∗∥2 + η2t−1B, (43)
where B = ∑N
k=1 ρ 2 kϵ 2 k + 6LΓ + 8(E − 1)2G2.
To bound A1, one can first take expectation over S(t) and apply Lemma 5 where the upper bound actually eliminates both sources of randomness. Thus, it follows that
A1 = E∥w̄(t)− v̄(t)∥2 ≤ 4
K η2t−1E 2G2 (44)
Let C = 4KE 2G2 and plug A1 and A2 back into (41):
E∥w̄(t)− w∗∥2 ≤ (1− ηt−1µ)E∥w̄(t− 1)− w∗∥2 + η2t−1(B + C). (45)
Equivalently, let ∆t = E∥w̄(t) − w∗∥2, then we have the following recurrence relation for any t ≥ 1:
∆t ≤ (1− ηt−1µ)∆t−1 + η2t−1(B + C). (46)
Next we prove by induction that ∆t ≤ νγ+t where ν = max { β2(B+C) βµ−1 , (γ + 1)∆1 } using an aggregation interval E ≥ 1 and a diminishing step size ηt = βt+γ for some β > 1 µ and γ > 0 such that η1 ≤ min{ 1µ , 1 4L} and ηt ≤ 2ηt+E .
First, for t = 1 the conclusion holds that ∆1 ≤ νγ+1 given the conditions. Then by assuming it holds for some t, one can derive from (46) that
∆t+1 ≤ (1− ηtµ)∆t + η2t (B + C) ≤ ( 1− βµ
t+ γ ) ν γ + t + ( β t+ γ )2 (B + C)
= t+ γ − 1 (t+ γ)2
ν + [β2(B + C)
(t+ γ)2 − βµ− 1 (t+ γ)2 ν ]
︸ ︷︷ ︸ ≥0
≤ t+ γ − 1 (t+ γ)2 ν
≤ t+ γ − 1 (t+ γ)2 − 1 ν
= ν
t+ γ + 1 , (47)
which proves the conclusion ∆t ≤ νγ+t for any t ≥ 1.
Then by the smoothness of the objective function F , it follows that
E[F (w̄(t))]− F ∗ ≤ L 2 E∥w̄(t)− w∗∥2
= L
2 ∆t ≤
L
2
ν
γ + t . (48)
Specifically, by choosing β = 2µ (i.e., ηt = 2 µ(γ+t) ), γ = max{ 8L µ , E} − 1 , we have
ν = max {β2(B + C)
βµ− 1 , (γ + 1)∆1 } ≤ β
2(B + C) βµ− 1 + (γ + 1)∆1
= 4(B + C)
µ2 + (γ + 1)∆1. (49)
By definition, we have w(t) = w̄(t) at the aggregation steps. Therefore, for t ∈ TA:
E[F (w(t))]− F ∗ ≤ L 2 ν γ + t
= L
(γ + t) (2(B + C) µ2 + γ + 1 2 ∆1 ) .

heading: D PROFILE DISSIMILARITY UNDER HOMOMORPHIC ENCRYPTION
text: The proposed representation profiling scheme encodes the representations of data into a list of distribution parameters, namely RP (w, D) = {(µi, σ2i )|i = 1, 2, . . . , q} where q is the length of the profile. Theoretically, the information leakage (in terms of the data in D) by exposing RP (w, D) is very limited and it is basically impossible to reconstruct the samples in D given RP (w, D). Nonetheless, Homomorphic Encryption (HE) can be applied to the profiles (both locally and on the server) so as to guarantee zero knowledge disclosure while still allowing profile matching under the encryption. In the following we give details on how to encrypt a representation profile and compute profile dissimilarity under Homomorphic Encryption (HE).
To calculate (3) and (4) under encryption, a client needs to encrypt (denoted as [[·]]) every single µi and σ2i in its profile RP (w, D) locally before upload whereas the server does the same for its RP ∗(w, D∗). Therefore, according to Eq. (4) we have:
[[KL(N (k)i ||N ∗ i )]] =
1 2 log[[(σ∗i ) 2]]− 1 2 log[[(σ (k) i ) 2]]− [[ 1 2 ]]
+ ([[(σ
(k) i ) 2]] + ([[µ (k) i ]]− [[µ∗i ]])2
2[[(σ∗i ) 2]]
, (50)
where the first two terms on the right-hand side require logarithm operation on the ciphertext. However, this may not be very practical because most HE schemes are designed for basic arithmetic operations on the ciphertext. Thus we also consider the situation where HE scheme at hand only provides additive and multiplicative homomorphisms (Gentry, 2009). In this case, to avoid the logarithm operation, the client needs to keep every σ2i in RP
∗(w, Di) as plaintext and only encrypts µi, likewise for the server. As a result, the KL divergence can be computed under encryption as:
[[KL(N (k)i ||N ∗ i )]] = [[1 2 log( σ∗i
σ (k) i
)2 + 1 2 ( σ (k) i σ∗i )2 − 1 2 ]] + 1
2(σ∗i ) 2 ([[µ
(k) i ]]− [[µ ∗ i ]]) 2 (51)
where the first term on the right-hand side is encrypted after calculation with plaintext values (σki ) 2 and (σ∗)2 whereas the second term requires multiple operations on the ciphertext values [[µki ]] and [[µ∗]].
Now, in either case, we can compute profile dissimilarity under encryption by summing up all the KL divergence values in ciphertext:
[[div(RPk, RP ∗)]] =
1
q q∑ i=1 [[KL(N (k)i ||N ∗ i )]]
(52)

heading: E DETAILS OF EXPERIMENTAL SETUP

heading: E.1 ENVIRONMENT SETUP
text: Detailed experimental settings are listed in Table 4. In the S-Task, the total population is 50 and the data collected by a proportion of the sensors (i.e., end devices of this task) are of low-quality: 10% of the sensors have no valid data and 40% of them produce noisy data. In the L-Task, we set up a relatively large population (1000 end devices) and spread the data (from EMNIST digits) across the devices with strong class imbalance – roughly 60% of the samples on each device fall into the same class. Besides, many local datasets are of low-quality: the images on 15% of the clients are irrelevant (valueless for the training of this task), 20% are (Gaussian) blurred, and 25% are affected by the salt-and-pepper noise (random black and white dots on the image, density=0.3). For the STask, the maximum number of rounds tmax is set to 100 for both aggregation modes, whilst it is set to 300 and 50 for the full aggregation and partial aggregation, respectively, for the L-Task. The preference factor α for our protocol is set to 10. Considering the population of the clients, the setting of the selection fraction C is based on the scale of the training participants suggested by Kairouz et al. (2019).
To simulate a realistic FL system that consists of disparate end devices, the clients are heterogeneous in terms of both performance and communication bandwidth (see Table 4). A validation set is kept by the server (as the benchmark data) and used for model evaluation.

heading: E.2 DETAILS OF COST FORMULATION
text: In each FL round, the server selects a fraction (i.e., C) of clients, distributes the global model to these clients and waits for them to finish the local training and upload the models. Given a selected set of clients S, the time cost and energy cost of a communication round can be formulated as:
Tround = max k∈S {T commk + T traink + TRPk }, (53)
Ek = E comm k + E train k + E RP k . (54)
where T commk and T train k are the communication time and local training time, respectively. The device-side energy consumption Ek mainly comes from model transmission (through wireless channels) and local processing (training), corresponding to Ecommk and E train k , respectively. T RP k and ERPk estimate the time and energy costs for generating and uploading local profiles and only apply to FEDPROF.
Eq. (53) formulates the length of one communication round of FL, where T commk can be modeled by Eq. (55) according to Tran et al. (2019), where bwk is the downlink bandwidth of device k (in MHz); SNR is the Signal-to-Noise Ratio of the communication channel, which is set to be constant as in general the end devices are coordinated by the base stations for balanced SNR with the fairnessbased policies; msize is the size of the model; the model upload time is twice as much as that for model download since the uplink bandwidth is set as 50% of the downlink bandwidth.
T commk = T upload k + T download k
= 2× T downloadk + T downloadk
= 3× msize bwk · log(1 + SNR) , (55)
T traink in Eq. (53) can be modeled by Eq. (56), where sk is the device performance (in GHz) and the numerator computes the total number of processor cycles required for processing M epochs of local training on Dk.
T traink = M · |Dk| ·BPS · CPB
sk , (56)
TRPk consists of two parts: T RPgen k for local model evaluation (to generate the profiles of Dk) and TRPupk for uploading the profile. T RP k can be modeled as:
TRPk = T RPgen k + T RPup k
= 1
M T traink + RPsize 1 2bwk · log(1 + SNR) , (57)
where TRPgenk is estimated as the time cost of one epoch of local training; T RPup k is computed in a similar way to the calculation of T commk in Eq. (55) (where the uplink bandwidth is set as one half of the total bwk); RPsize is the size of a profile, which is equal to 4× 2× q = 8× q (four bytes for each floating point number) according to our definition of profile in (2).
Using Eq. (54) we model the energy cost of each end device by mainly considering the energy consumption of the transmitters for communication (Eq. 58) and on-device computation for local training (Eq. 59). For FEDPROF, there is an extra energy cost for generating and uploading profiles (Eq. 60).
Ecommk = Ptrans · T commk (58)
Etraink = Pfs 3 k · T traink (59)
ERPk = Ptrans · T RPup k + Pfs 3 k · T RPgen k , (60)
where Pfs3k is a simplified computation power consumption model (Song et al., 2013) and Pf is the power of a baseline processor. Ptrans is the transmitter’s power. We set Ptrans and Pf to 0.5 and 0.7 Watts respectively based on the benchmarking data provided by Carroll et al. (2010).

Review summaries:
In this paper, the authors propose a user selection algorithm for federated learning (FL). The key motivation is to select high quality clients for update and thus to reduce the impact of low quality data on FL training. A hidden hypothesis is that high quality data has similar representations while noisy and low-quality data has different distributions of representations. Based on this hypothesis, the key idea is to select users based on their representation layer distribution difference from the global model, the higher the difference, the lower the chance of the client being selected.  Furthermore, the authors observed and proved that representation layers follow a Gaussian distribution, which makes the representation difference learning more efficient. The authors evaluated the proposed algorithm in comparison to existing algorithms using a small-scale sensor dataset and a large-scale EMNIST dataset. The proposed algorithm performs well in the evaluation.