FedDUAP: Federated Learning with Dynamic Update and Adaptive Pruning Using Shared Data on the Server

1 Introduction

While a large amount of data are generally dispersed over numerous edge devices, some data may be available at the server side to facilitate more efficient processing [Zhao et al., 2018]. Due to the concerns of data privacy and security, multiple legal restrictions [Official Journal of the European Union, 2016; CCP, 2018] have been put into practice, which makes it complicated to aggregate the distributed sensitive data into a single server or data center. With the size of training data having a significant influence on the quality of machine learning models [Li et al., 2021], Federated Learning (FL) [McMahan et al., 2017; Liu et al., 2022] becomes a promising approach to collaboratively train a model without transferring raw data.

†H. Zhang and J. Liu contributed equally to the paper. This work was done when H. Zhang was an intern at Baidu Inc.

∗Corresponding authors (liuji04@baidu.com and jiajuncheng@suda.edu.cn).

Conventional FL was proposed to train a global model using non-Independent and Identically Distributed (non-IID) data on mobile devices [McMahan et al., 2017]. During the training process of FL, the raw training data is kept within each device while the gradients or the weights of a model are communicated. FL typically utilizes a parameter server architecture [Liu et al., 2022], where a parameter server (server) coordinates the distributed training process. The training process generally consists of multiple rounds, each of which is composed of three steps. First, the server randomly selects several devices and sends the global model to the selected devices. Second, each selected device updates the global model with local data and uploads the updated model to the server. Third, the server aggregates all uploaded local models to generate a new global model. These steps are repeated until the global model converges or predefined conditions are attained.

Although FL helps preserve the privacy and the security of distributed device data, two unsolved challenges limit the applicability of the FL paradigm in real-world scenarios. On the one hand, although a large amount of data are collected from numerous devices, the data over a single device may be limited, which results in low effectiveness of local training. On the other hand, local devices often have limited computing capacity and communication capacity [Li et al., 2018], which leads to low efficiency in the local training process.

While sensitive data are not allowed to be transferred among the devices and the server, some insensitive data may reside in the servers or the cloud [Yoshida et al., 2020] , e.g., Amazon Cloud [Amazon, 2021], which can be exploited to address the low-effectiveness challenges. Existing works that introduce the insensitive server data to improve the accuracy of the global model generally encounter high communication costs due to data transfer between the devices and the server [Zhao et al., 2018]. In addition, they may suffer from low efficiency due to simple processing of the server data as that in an ordinary device [Yoshida et al., 2020] or knowledge transfer for heterogeneous models [Lin et al., 2020b].

Pruning techniques are adopted within the training process of FL to reduce the communication costs between the devices and the server, as well as to accelerate the training process [Jiang et al., 2019]. However, most model pruning approaches in the FL context are lossy pruning methods with a single pruning strategy for all layers of neural networks, without considering their individual dimensions and importance [Lin et al., 2020a]. The aforementioned straightforward model pruning strategies may fail to generate a good approximation to prune appropriate parts and thus lead to non-trivial failure probability of FL training [Zhao et al., 2018].

In this paper, we propose FedDUAP, an efficient federated learning framework that collaboratively trains a global model using the device data and the server data. To address the two challenges in FL, we take advantage of the server data and the computing power of the server to improve the performance of the global model while considering the non-IID degrees of the server data and the device data. The non-IID degree represents the difference between the distribution of a dataset and that of all the devices.

Under this framework, we propose an FL algorithm, i.e., FedDU, to dynamically update the model using the device data and the server data. Within FedDU, we propose a method to dynamically adjust the centralized training within the server according to the accuracy of the global model and the non-IID degrees. Furthermore, we design an adaptive model pruning method, i.e., FedAP, to reduce the size of the global model, so as to further improve the efficiency and reduce the computational and communication costs of the training process while ensuring comparable accuracy. FedAP performs unique pruning operations for each layer of specific dimensions and importance to achieve a good balance between efficiency and effectiveness, based on the non-IID degrees and the server data. To the best of our knowledge, we are among the first to incorporate non-IID degrees in the dynamic server update and the adaptive pruning for FL. We summarize our contributions as follows:

1. We propose a dynamic FL algorithm, i.e., FedDU, to take advantage of both server data and device data within FL. The algorithm dynamically adjusts the global model according to the accuracy of the global model and the non-IID degrees with normalized stochastic gradients.
2. We propose an adaptive pruning method, i.e., FedAP, which performs unique pruning operations adapted to the different dimensions and importance of layers based on the non-IID degrees, to further improve the efficiency with an accuracy comparable to the original model.
3. We carry out extensive experiments to show the advantages of our proposed approach. FedDUAP significantly outperforms state-of-the-art approaches on four typical models and two datasets in terms of accuracy, efficiency, and computational cost.

The rest of this paper is organized as follows. In Section 2, we present related work. In Section 3, we propose our framework, i.e., FedDUAP, including FedDU and FedAP. In Section 4, we show the experimental results using two typical models. Finally, Section 5 concludes.

2 RelatedWork

FL is first proposed to collaboratively train a global model with the non-IID data across mobile devices [McMahan et al., 2017]. Some works ([Kairouz et al., 2021; Zhou et al., 2021] and references therein) already exist to increase the performance of global models, while they only consider the device data. Because of incentive mechanisms [Yoshida et al., 2020] or the convenience of cloud services, some insensitive data may reside on the server and can be exploited for the training process. While the server data can be assumed to be IID by gathering the data from devices and can be treated as that in an ordinary device with a simple average method [Yoshida et al., 2020], the IID distribution of the server data is not realistic, and the upload of device data to the server may incur privacy or security concerns and excessive communication cost [Jeong et al., 2018]. In the existing literature, the server data is mainly exploited for some specific objectives, e.g., heterogeneous models [He et al., 2020], labelfree data [Lin et al., 2020b], and one-shot model training [Li et al., 2021], based on knowledge transfer methods, while these methods may suffer from low accuracy [He et al., 2020; Li et al., 2021], or long training time [Lin et al., 2020b]. The server data could also be transferred to the devices to further improve the model performance [Zhao et al., 2018], which incurs significant communication costs. Finally, the server data can be exploited to select relevant clients for the training [Nagalapatti and Narayanam, 2021], which is orthogonal to and can be combined with our approach.

Model pruning can help reduce the computation and communication cost in the training process of FL [Jiang et al., 2019], for which the server data is rarely considered. There are two major types of pruning, i.e., weight (unstructured) pruning and filter (structured) pruning. With unstructured pruning, some parameters are set to 0 without changing the model structure. While it can achieve accuracy comparable to the original model [Zhang et al., 2021] and helps reduce communication costs in FL [Jiang et al., 2019], unstructured pruning has limited advantages on general-purpose hardware in terms of computational cost [Lin et al., 2020a]. In contrast, structured pruning directly changes the structure of the model by removing some neurons (filters in the convolution layers). While it can significantly reduce both computational cost and communication cost [Lin et al., 2020a], it is complicated to determine the number of filters to preserve in the structured pruning method, and the existing methods are not well adapted to FL. Gradient compression or sparsification can be exploited in FL to reduce communication cost [Koneˇcn`y et al., 2016], which has been extensively researched in literature and won't be further explored in this paper.

3 Method

In this section, we first present the system model of our framework, i.e., FedDUAP. Then, we present our FL algorithm, i.e., FedDU, for the collaborative FL model update, and our adaptive model pruning method, i.e., FedAP, to reduce the computational and communication cost.

3.1 SystemModel

As shown in Figure 1, we consider an FL system composed of a server and N edge devices. We assume that the server is much more powerful than the devices. The server data resides in the server, and the device data is distributed in multiple devices, both of which can be locally exploited for the training process of FL without being transferred. We assume that Device k has a local dataset Dk = {xk,j, yk,j}nk j=1 , consisting of nk samples. D0 denotes the server data. xk,j is the j-th input data sample on Device k, and yk,j is the label of xk,j. We denote the input data sample set by X and the label set by Y. The objective of the FL training can be formulated as follows:

where w is the parameters of the global model, Fk(w) ≜ 1 nk ∑{xk,j,yk,j}∈Dk f(w, xk,j, yk,j) is the local loss function of Device k, and the loss function f(w, xk,j, yk,j) captures the error of the model on the data pair {xk,j , yk,j}.

While the data is generally non-IID in FL [Kairouz et al., 2021], we exploit the Jensen-Shannon (JS) divergence [Fuglede and Topsoe, 2004] to represent the non-IID degree of the data on a device and the server as shown in Formula 2:

where Pm = 1 2 (Pk +P ), P = ∑Nk=1 nkPk ∑Nk=1 nk , Pk = {Pk(y)|y ∈ Y} with Pk(y) representing the probability that a data sample corresponds to Label y in Device k or the server (k = 0), and DKL(·||·) is the Kullback-Leibler (KL) divergence [Kullback, 1997] defined in Formula 3:

A higher non-IID degree indicates that the data distribution of a specific device or the server differs from the global distribution more significantly. While the data cannot be transferred between the server and devices, we assume that the statistical meta information, i.e., Pk and nk, can be shared between the server and devices during the training process, which incurs much less privacy concern [Lai et al., 2021].

As shown in Figure 1, the training process of FedDUAP consists of multiple rounds, and each round is composed of

6 steps. In Step 1⃝, the server randomly selects a fraction (D t with t representing the round) of devices (D) to train a global model and distributes the global model to each device. Then, the model is updated using the local data of each device in Step 2⃝. The updated models are uploaded to the server in Step 3⃝, and aggregated using FedAvg [McMahan et al., 2017] in Step 4⃝. Afterward, the model is updated (server update) using the server data in Step 5⃝, which is detailed in Section 3.2. Finally, in a specific round, the model is pruned using the statistic information of both the server data and the device data, which is explained in Section 3.3. Steps 1⃝ - 4⃝ are similar to those of conventional FL steps, while we propose using the server data to dynamically update the global model (Step 5⃝) so as to improve the accuracy and an adaptive model pruning method based on both the server data and the device data (Step 6⃝) to accelerate the training of FL.

3.2 Server Update

In this section, we propose our FL algorithm, i.e., FedDU, which takes advantage of both server data and device data to update the global model. FedDU exploits the server data to dynamically determine the optimal steps of the server update while considering the non-IID degrees of the server data and the device data in order to improve the convergence and accuracy of the global model.

While the size of server data may be much bigger than that within a single device, the naive update of the aggregated model with the stochastic gradients generated from the server data may suffer from objective inconsistency [Wang et al., 2020]. In order to reduce the objective inconsistency, we normalize the stochastic gradients calculated based on the server data, inspired by [Wang et al., 2020]. Then, the model update in FedDU is defined in Formula 4.

where wt represents the weights of the global model at Round t, wt- 1 2 represents the weights of the global model after aggregating the models from devices as defined in Formula 5 [McMahan et al., 2017], τ t-1 eff is the effective step size for the server update defined in Formula 7, η is the learning rate, gt0 (·) is the normalized stochastic gradient on the server at Round t and defined in Formula 6.

where n′ = ∑k∈Dt nk is the total number of samples in the selected devices, gt-1 k (·) is the gradient calculated based on the local data in Device k.

where wt- 12 ,i is the parameters of the updated aggregated model, after i iterations within the batch of the server update at Round t, g(t-1) 0 (·) represents the corresponding stochastic gradients on the server, and τ = ⌈ |n0|E B ⌉ is the number of iterations performed within the server update, with E representing the number of local epochs and B representing the

Algorithm 1 Federated Dynamic Server Update (FedDU)

Input:

• D t : The set of selected devices at Round t
• Dk: The dataset on Device k with 0 representing that on the server
• wt-1 : The global model at Round t - 1
• E: The number of local epochs
• B: The local batch size

decay: The decay rate

• P : The set of data distribution {Pk|k ∈ {0} ∪ D t } with 0 representing the server
• η: The learning rate

Output:

• wt : The global model at Round t
• 1: for k in D t (in parallel) do
• 2: Calculate gt-1 k (wt-1 ) using wt-1 , Dk
• 3: end for
• 4: Calculate wt- 12 using wt-1 , η according to Formula 5
• 5: Calculate wt using wt- 1 2 , decay, E, B, P, η according to Formula 4

batch size. Within each round, the model is updated with multiple iterations by sampling a mini-batch of server data.

As τ t eff is critical to the training process, we propose to dynamically determine the effective step size based on the accuracy of the aggregated model, the non-IID degrees of the data, and the number of rounds, as defined in Formula 7.

where acct is the accuracy (evaluated using the insensitive server data) of the aggregated model at Round t, i.e., wt- 12 defined in Formula 5, n0 is the number of samples in the server data, D(·) is defined in Formula 2, P ′ t = ∑k∈Dt nkPk ∑k∈Dt nk denotes the distribution of all the data in the selected devices at Round t, P0 represents the distribution of the server data, decay ∈ (0, 1) is used to ensure that the final trained model converges to the solution of Formula 1, and C is a hyperparameter. f ′ (acc) is a function based on acc. At the beginning of the training, acc is relatively small, and the value corresponding to f ′ (acc) is prominent to exploit the server data and the high performance of the server to update the model. At the end of the training, in order to achieve the objective defined in Formula 1, f ′ (acc) becomes small to reduce the influence of the server data.

FedDU is shown in Algorithm 1. The local model update is performed in parallel in each selected device (Lines 1 - 3). Then, the aggregated model is calculated using Formula 5 (Line 4). Afterward, the new global model is updated based on the server data using Formula 4 (Line 5).

3.3 Adaptive Pruning

We propose a layer-adaptive pruning method, i.e., FedAP, to improve the efficiency of the FL training process. FedAP

Algorithm 2 Federated Adaptive Structured Pruning (FedAP)

Input:

• L: The list of convolutional layers to prune
• D: The set of all devices and the server
• w: The initial model
• w∗ : The current model at Round t

W = [v1, v2, · · · , vm]: The list of parameters in the model w∗ with m representing the number of parameters

Output:

w′ : The pruned model at Round t

• 1: w′ ←w∗
• 2: for k ∈ D (in parallel) do
• 3: Calculate the expected pruning rate p∗k
• 4: end for
• 5: Calculate p∗ according to Formula 8
• 6: W = [vo1 , vo2 , · · · , voR ] ← Sort W in ascending order of |v|
• 7: V = |vo⌊R∗p∗⌋ |
• 8: for l ∈ L do
• 9: Wl = [v1, v2, · · · , vql ] ←The parameters in Layer l
• 10: W ′ l ← [v1, v2, · · · , vq′ l ] with each |vq| < V
• 11: p∗l ← Cardinality(W ′ l ) ql
• 12: Calculate the ranks Rl of each filter in Layer l
• 13: Sort the filters according to Rl in an ascending order
• 14: w′ l ← Preserve the last dl - ⌊p∗l ∗ dl⌋ filters in Rl
• 15: w′ ←Replace the l-th layer of w′ with w′ l
• 16: end for

performs unique pruning operations on the server, which are adapted to the different dimensions and importance of multiple layers, based on the non-IID degrees of the server data and the device data. Please note that the pruning process is carried out at a specific round during the training process.

FedAP is shown in Algorithm 2. For each device and the server (Lines 2 - 4), we calculate the expected pruning rate using the server data and the device data (Line 3). In a device k or the server, given a neural network with initial parameters Wk, after T rounds of training, we denote the updated parameters by W ′k and the difference by ∆k = Wk -W ′k . Then, we calculate the Hessian matrix of the loss function, i.e., H(W ′k ), and sort its eigenvalues in ascending order, i.e., {λmk |m ∈ (1, dk)} with dk representing the rank of the Hessian matrix and m representing the index of an eigenvalue. We define a base function Bk(∆k) = H(W ′k ) - ▽L(∆k + W ′k ) with ▽L(·) representing the gradient of the loss function, and we denote its Lipschitz constant as Lk. Inspired by [Zhang et al., 2021], we find the first mk that satisfies λmk+1 -λmk > 4Lk to avoid accuracy reduction, and we calculate the expected pruning rate by p∗k = mk dk , i.e., the ratio between the number of pruned eigenvalues and that of all the eigenvalues. As the expected pruning rate in each device is of much difference because of the non-IID distribution of data, we use Formula 8 to calculate an aggregated expected pruning rate for the entire model on the server (Line 5).

where ϵ is a small value to avoid division by zero. We calculate a global threshold value (V ), which is used to calculate the pruning rate of each layer. The global threshold value equals the absolute value of the ⌊R ∗ p∗ ⌋-th parameter (Line 7) in all the parameters in ascending order (Line 6). Then, for each convolutional layer (Line 8), we calculate the pruning rate of the layer by dividing the number of parameters having inferior absolute values than the threshold value by the total number (Lines 9 - 11). Inspired by [Lin et al., 2020a], we prune the model based on the ranks of feature maps (the output of filters) (Lines 12 - 15). Let us denote the ranks of feature maps of Layer l by Rl = {rj l |j ∈ (1, dl)}, where dl represents the number of filters in the l-th layer. While feature maps are almost unchanged for a given model [Lin et al., 2020a], we assume that the ranks on the server are similar to those in each device. Thus, we prune the model with the feature maps on the server. We calculate (Line 12) and sort (Line 13) the ranks of the feature maps in Rl. We preserve the filters corresponding to the last dl -⌊p∗l ∗ dl⌋ ranks in the sorted Rl (in ascending order), in order to achieve the highest pruning rate pl ≤ p∗l (Line 14). Finally, we replace the layer of the original model with the preserved filters (Line 15). The process can be applied without the server data by carrying out the execution of Line 12 at a device and transferring the ranks Rl back to the server.

4 Experiments

In this section, we present the experimental results to show the advantages of FedDUAP by comparing it with state-ofthe-art baselines, i.e., FedAvg [McMahan et al., 2017], Datasharing [Zhao et al., 2018], Hybrid-FL [Yoshida et al., 2020], HRank [Lin et al., 2020a], IMC [Zhang et al., 2021], and PruneFL [Jiang et al., 2019].

4.1 Experimental Setup

We set up an FL system composed of a parameter server and 100 devices. In each round, we randomly select 10 devices to participate in the training. We consider the datasets of CIFAR-10 and CIFAR-100 [Krizhevsky et al., 2009] for comparison. We consider four models, i.e., a simple synthetic CNN network (CNN), ResNet18 (ResNet) [He et al., 2016], VGG11 (VGG) [Simonyan and Zisserman, 2015], and LeNet in our experimentation.

We report the results of CNN based on CIFAR10 and those of ResNet based on CIFAR100, while the other experimentation results reveal consistent findings. In Figure 3, we report the results of CNN and VGG based on CIFAR10 for the interest of training time. p represents the ratio between the size of data in the server and that in devices.

4.2 Evaluation with non-IIDData

In this section, we first compare FedDU with FedAvg, Datasharing, and Hybrid-FL in terms of model accuracy. Then, we compare the adaptive pruning method, i.e., FedAP, with FedAvg, IMC, HRank, and PruneFL, in terms of model efficiency. Finally, we compare FedDUAP, which contains both FedDU and FedAP, with the six state-of-the-art baselines.

Evaluation on FedDU

Data-sharing sends the server data to devices so that devices can mix the local data with the server data to form a dataset with a smaller non-IID degree to increase the accuracy of the global model. Hybrid-FL treats the server as an ordinary device using the FedAvg algorithm.

As shown in Figure 2, FedDU leads to a higher accuracy compared with FedAvg (up to 4.9%), Data-sharing (up to 4.1%), and Hybrid-FL (up to 19.5%) for both CNN and ResNet when p = 5% and 10%. Compared with FedDU, Data-sharing needs to transfer the server data to devices, which may incur a significant communication cost and privacy problems. In addition, Data-sharing needs a much longer training time to achieve the accuracy of 0.6 (up to 15.7 times slower) than FedDU on CNN.

We also evaluate the performance of FedDU with diverse settings of τeff and server data. The dynamic adjustment of τeff significantly outperforms a static value (up to 1.7%) in terms of accuracy. In addition, with various distributions of the server data, we find that when the non-IID degree of the server data is smaller, the global model can get faster performance improvement (up to 6.1 times faster) when comparing the non-IID degree of 0.31 with that of 9.0 ∗ 10-6 .

Evaluation on FedAP

In this section, we compare FedAP with two adapted methods, i.e., HRank [Lin et al., 2020a], and IMC [Zhang et al., 2021], and a state-of-the-art pruning method in FL, i.e., PruneFL [Jiang et al., 2019]. We exploit HRank with the server data during the training process of FL with diverse pruning rates, e.g., 0.2, 0.4, 0.6, and 0.8, of each layer. Similarly, we adapt the IMC method using the server data within the training process of FL. Among the three baseline approaches, HRank is structured, while IMC and PruneFL are unstructured.

As shown in Figure 3, FedAP can achieve an appropriate pruning rate (37.8% on average for CNN and 72.0% on average for VGG), which corresponds to a faster training speed (up to 1.8 times faster), while ensuring an excellent accuracy of the model (up to 0.1% accuracy reduction compared with that of unpruned FedAvg). The training time and the accuracy decrease simultaneously when the pruning rate increases with HRank. Our proposed method, i.e., FedAP, can generate adaptive pruning rates for each layer while achieving accuracy comparable with FedAvg. We then compare FedAP with FedAvg, IMC, and PruneFL. As shown in Figure 4, the training process of FedAP is significantly faster than baselines. And FedAP achieves the highest accuracy among the pruning methods while the training time is significantly shorter to achieve the accuracy of 0.55. As unstructured pruning methods cannot exploit general-purpose hardware to speed up the calculation, the computational cost remains unchanged. In contrast, FedAP leads to a much smaller computational cost (up to 55.7% reduction).

Evaluation on FedDUAP

We compare FedDUAP, consisting of both FedDU and FedAP, with the baseline approaches. As shown in Table 1, FedDUAP achieves higher accuracy compared with FedAvg (4.8%), Data-sharing (12.0%), Hybrid (18.4%), IMC (6.9%), and PruneFL (6.3%). In addition, FedDUAP corresponds to a shorter training time to achieve the target accuracy (up to 2.8 times faster than FedAvg, 15.0 times faster than Data-sharing, 8.8 times faster than Hybrid-FL, 3.7 times faster than IMC, and 4.5 times faster than PruneFL) and a much smaller computational cost (up to 61.9% compared with others).

5 Conclusion

In this work, we propose an efficient FL framework based on shared insensitive data on the server, i.e., FedDUAP. FedDUAP consists of a dynamic update FL algorithm, i.e., FedDU, and an adaptive pruning method, i.e., FedAP. We exploit both the server data and the device data to train the global model within FL while considering the non-IID degrees of the data. We carry out extensive experimentation with diverse models and real-life datasets. The experimental results demonstrate that FedDUAP significantly outperforms the state-of-the-art baseline approaches in terms of accuracy (up to 4.8% higher), efficiency (up to 2.8 times faster), and computational cost (up to 61.9% smaller).