FedBIAD: Communication-Efficient and Accuracy-Guaranteed Federated Learning with Bayesian Inference-Based Adaptive Dropout

Deep Learning (DL) constructs an input-output mapping through a Deep Neural Network (DNN). Given a dataset $(X,Y)$, for any $(\bm{x},\,y)\in(X,\,Y)$, there is an input $\bm{x}$ and an unknown true function $f_{0}$ such that $y=f_{0}(\bm{x})$. The goal of DL is to learn a DNN model $f_{\theta}$ such that $f_{\theta}(\bm{x})\thickapprox f_{0}(\bm{x})$, where $\theta$ denotes the set of weights in the model.

We consider two types of commonly used DNNs: the non-recurrent neural network and the Recurrent Neural Network (RNN). Starting by a non-recurrent neural network with $L$ layers, $f_{\theta}:\mathbb{R}^{d}\to\mathbb{R}$ is written recursively as:

where $x_{0}=\bm{x}$, $\rho$ is an activation function, and $W_{l}$ is the weight matrix in the $l$-th layer of DNN such that $\theta=\{W_{1},\dots,W_{L}\}$. The input dimension is $d$. For ease of analysis, we use an equal-width DNN as [21] and [28], i,e., the number of units in each hidden layer is equal to $D$, where $d\leq D$.

For sequence learning tasks, such as time series forecasting and next-word prediction, the RNN with memory correlation ability is more effective. In this case, the input is a sequence of feature vectors $[x_{1},\ldots,x_{L}],x_{l}\in\mathbb{R}^{d}$, and $f_{\theta}$ can be expressed in a different form. The input sequence is mapped by

with $h_{0}=\overrightarrow{0}$. $W_{x}\in\mathbb{R}^{D\times d}$ is the input-hidden weight matrix, and $W_{h}\in\mathbb{R}^{D\times D}$ is the hidden-hidden weight matrix (denoted recurrent connections of RNN) such that $\theta=\{W_{x},W_{h}\}$. Besides, $\varrho$ and $\phi$ are activation functions.

We set $N$ as the total number of weights in $\theta$ and $\mathrm{J}$ as the number of rows in all weight matrices. The $\textbf{w}_{j}$ denotes the $j$-th row of weight matrices. The unsparse number $S$ is the number of nonzero weights in $\theta$. In this way, the model architecture is determined by $(S,L,D)$. $\Theta_{S,L,D}$ represents the solution space composed of all feasible weights.

From the Bayesian perspective, we consider $\theta$ as random variables following prior $\pi$. Given the dataset ($X,Y$), we aim to find out the posterior $\pi(\theta|X,Y)$, which is usually intractable because the posterior is high-dimensional and non-convex in DNN [29]. Variational Inference (VI) [30] is one of the most efficient solutions for the posterior studied in the last decade [31, 32, 33], which searches for a variational approximation to estimate $\pi(\theta|X,Y)$. Based on VI, [34] considers that the likelihood $p(y|\bm{x},\theta)$ could be replaced by $\big{[}p(y|\bm{x},\theta)\big{]}^{\alpha}$ for any $\alpha\in(0,1)$, leading to the tempered posterior

where $m$ is the number of samples. The proof of concentration of the tempered posterior $\pi_{m,\alpha}$ needs fewer assumptions than $\pi(\theta|X,Y)$ [34]. Following it, we pay attention to a variational approximation $\tilde{\pi}$ of the tempered posterior $\pi_{m,\alpha}$.

For any $(\bm{x}_{i},y_{i})\in(X,Y),\,i\in\{1,\ldots,m\}$, the $p(y_{i}|\bm{x}_{i},\theta)$ follows a Gaussian with a likelihood variance $\sigma^{2}$. Our objective is to explore a variational approximation $\tilde{\pi}$ to estimate the tempered posterior $\pi_{m,\alpha}$ for minimizing the loss function

The second item from the right in (2) has been proven to approximate L2 regularisation [16, 22]. Hence, variational Bayesian inference avoids overfitting and easily learns from small samples. Inspired by [21], Definition 1 gives an expression for the generalization error of variational approximation.

The Bayesian inference with spike-and-slab distribution can act as a relevant proxy of the dropout [21]. As mentioned in [13], the dropout technique zeros out a fixed number of weights, while the idea of setting a subset of weights to zero can be realized by placing spike-and-slab distributions over weights [22]. Motivated by [16] and [22], we define the spike-and-slab distributions to factorize over the weight matrices, where each weight row $\textbf{w}_{j}$ follows

with dropout rate $p$ given in advance, the variational parameter (row vector) $\bm{\mu}_{j}$ learned in the local training, and posterior variance $\tilde{s}^{2}$. Here, $\delta(0)$ is an impulse function. We suppose that posterior variance $\tilde{s}^{2}$ is constant for any weight rows, which is common in Bayesian variational inference, as referred to [16, 21]. The precise setting of the posterior variance $\tilde{s}^{2}$ for FedBIAD will be detailed in Section IV-F. Based on the setting of constant posterior variance, we conduct extensive experiments, and the results are shown in Section V-B.

For better characterizing the spike-and-slab distributions of weight rows, we define a binary vector $\bm{\beta}=[\beta_{1},\ldots,\beta_{\mathrm{J}}]^{\top}\in\{0,1\}^{\mathrm{J}}$ as the dropping pattern to represent whether weight rows are dropped. If the dropping label $\beta_{j}$ of the $j$-th row is zero, then $\textbf{w}_{j}$ is dropped; otherwise, $\textbf{w}_{j}$ is held for training. Given dropout rate $p$, we compute the unsparse number $S=(1-p)\mathrm{J}\times D$ and determine the set of all possible dropping patterns $\mathcal{Z}^{S}_{N}$. Sampling $\bm{\beta}$ from $\mathcal{Z}^{S}_{N}$, the spike-and-slab distribution of $\textbf{w}_{j}$ is rewritten as

where $j\in\{1,\ldots,\mathrm{J}\}$. This work looks for high-quality dropping patterns based on importance indicators of weight rows to reduce uplink costs while achieving excellent performance.

Given $K$ devices formed a set $\mathcal{K}$, each device $k\in\mathcal{K}$ owns its data $\mathcal{D}^{k}$ and true function $f_{0}^{k}$ such that $y^{k}=f^{k}_{0}(\bm{x}^{k})$ for any $(\bm{x}^{k},y^{k})\in\mathcal{D}^{k}$. We aim to look for a global variational approximation $\tilde{\pi}^{g}=\mathcal{N}(U,\tilde{s}^{2}I)$ from a variational set [21] $\mathcal{F}_{S,L,D}\subseteq\Theta_{S,L,D}$ to minimize the average loss over all clients:

Here, $\mathcal{L}^{k}$ denotes the loss of the $k$-th client over $\mathcal{D}^{k}$ that can be calculated by (2), in which $m$ is replaced by $|\mathcal{D}^{k}|$.

Instead of using weights, we learn the variational approximation distribution in optimization problem (5) of average loss minimization. Each client $k$ owns its local variational approximation $\tilde{\pi}^{k}$, which is determined by the dropping pattern $\bm{\beta}^{k}$, local variational parameters $U^{k}=[\bm{\mu}^{k}_{1},\ldots,\bm{\mu}^{k}_{\mathrm{J}}]^{\top}$, and the posterior variance $\tilde{s}^{2}$. As stated above, we assume that $\tilde{s}^{2}$ is a constant, so client $k$ learns $U^{k}$ and explores $\bm{\beta}^{k}$ during local training. In this setting, client $k$ needs to transmit nonzero elements of $\bm{\beta}^{k}\circ U^{k}$ to the server, where we define

Concretely, for any $j\in\{1,\ldots,\mathrm{J}\}$, the variational parameter $\bm{\mu}^{k}_{j}$ will be transmitted only if $\beta^{k}_{j}\neq 0$.

As shown in Fig. 3, the procedure of FedBIAD in global round $r$ is as follows:

• $\bullet$

  Step 1: The server selects the client set $\mathcal{C}_{r}$ and sends global variational parameters $U_{r-1}$ to each client $k\in\mathcal{C}_{r}$.

• $\bullet$

  Step 2: For each client $k\in\mathcal{C}_{r}$, the local model is initialized by $\theta^{k,0}_{r}\sim\mathcal{N}(U_{r-1},\tilde{s}^{2}I)$. Then, fractional weight rows of the local model are dropped according to the dropping pattern $\bm{\beta}^{k}_{r}$, and the remaining sparse model is updated on local data. During local iterative training, the dropping pattern is adaptively adjusted based on changing trends of training loss. The experience of dropout is recorded in the weight score vector to characterize the importance of weight rows, which contributes to looking for a powerful dropping pattern for the client.

• $\bullet$

  Step 3: After $V$ training iterations, client $k\in\mathcal{C}_{r}$ uploads nonzero elements of variational parameters and binary dropping pattern (much less than variational parameters and can even be ignored in uplink costs) to the server.

• $\bullet$

  Step 4: The server reconstructs complete variational parameters based on the received binary dropping pattern for client $k\in\mathcal{C}_{r}$, and performs global aggregation to calculate new global variational parameters $U_{r}$ (§IV-E).

Specifically, FedBIAD is divided into two stages by a preset boundary $R_{b}$ of the global round. The difference between the two stages is the determination schemes of dropping patterns. In stage one (i.e., global round $r\leq R_{b}$), each client randomly samples the initial dropping pattern from $\mathcal{Z}^{S}_{N}$, and then adaptively adjusts the dropping pattern based on the trend of training loss (§IV-C) to find a better dropping pattern during training. If global round $r>R_{b}$, FedBIAD enters stage two, where the dropping pattern is determined by the experience-based importance indicator (§IV-D).

Our main idea is to explore the dropping pattern based on the trend of local training loss. As different weight rows have different effects on loss, we should drop the rows that cannot facilitate loss reduction. Firstly, we preset the dropout rate $p$, which determines the unsparse number $S=(1-p)\mathrm{J}\times D$. Given $S$, the set $\mathcal{Z}^{S}_{N}$ is specific. The $\bm{\beta}^{k,0}_{r}=[\beta^{k,0}_{r,1},\ldots,\beta^{k,0}_{r,\mathrm{J}}]^{\top}$ is defined as an initial dropping pattern of client $k$ in round $r$.

After receiving global variational parameters $U_{r-1}$, client $k$ initializes the local model $\theta^{k,0}_{r}\sim\mathcal{N}(U_{r-1},\tilde{s}^{2}I)$, randomly samples the dropping pattern $\bm{\beta}^{k,0}_{r}$ from $\mathcal{Z}^{S}_{N}$, and then zeros out each weight row $\textbf{w}_{j}$ whose dropping label $\beta^{k,0}_{r,j}=0$ in local model $\theta^{k,0}_{r}$. Subsequently, the remaining sparse model is trained locally. For the $v$-th iteration, the dropping pattern is denoted as $\bm{\beta}^{k,v}_{r}=[\beta^{k,v}_{r,1},\ldots,\beta^{k,v}_{r,\mathrm{J}}]^{\top},\,v\in\{1,\ldots,V\}$, and the variational parameters $U^{k,v}_{r}=[\bm{\mu}_{r,1}^{k,v},\ldots,\bm{\mu}_{r,\mathrm{J}}^{k,v}]^{\top}$ update by

where $\eta$ is the learning rate and $\tilde{\pi}^{k,v}_{r}=\bm{\beta}^{k,v}_{r}\circ\mathcal{N}(U^{k,v}_{r},\tilde{s}^{2}I)$.

During training, client $k$ calculates the loss gap between adjacent $\tau$ iterations, described as:

where $\bar{\mathcal{L}}^{k,v}_{r}=\sum_{i=v-\tau+1}^{v}{\mathcal{L}^{k}(\tilde{\pi}^{k,i}_{r})}$ is the average loss of the $(v-\tau+1)$-th iteration to the $v$-th iteration in the global round $r$. If $\Delta\mathcal{L}^{k,v}_{r}\leq 0$, the current dropping pattern $\bm{\beta}^{k,v}_{r}$ is favorable for loss decrease, which is used for the next $\tau$ iterations; otherwise, client $k$ resamples $\bm{\beta}^{k,v+1}_{r}=\ldots=\bm{\beta}^{k,v+\tau}_{r}$ from $\mathcal{Z}^{S}_{N}$ for training in the next $\tau$ iterations. After $V$ iterations, client $k$ drops zero row vectors, and transfers the variational parameters of the remaining weight rows to the server. Through dropout, clients can reduce transmitted parameter size so the uplink overhead can be alleviated. Note that, the amount of reduction in uplink costs is determined by the preset dropout rate $p$.

An intuitive dropout example for CNNs. In the above description, we elaborated on the dropout for fully connected neural networks and RNNs, where the weight matrix for each model layer is two-dimensional, and we can view weights by rows [16, 22]. Extending to Convolutional Neural Networks (CNNs), we view weights by filters and dropout is filter-wise, as referred to [12, 27]. Each client $k$ possesses a filter-wise dropping pattern $\bm{\beta}_{r}^{k,v}=[\beta^{k,v}_{r,1},\ldots,\beta^{k,v}_{r,J}]^{\top}$ for the local CNN in round $r$. For each convolutional layer in CNN, if the $j$-th filter has the dropping label $\beta^{k,v}_{r,j}=0$, all weights in this filter are zeroed out, meaning that the $j$-th filter is dropped. During local training, each client adaptively adjusts the filter-wise dropping pattern according to the loss gap calculated by (8), as mentioned above. After that, the dropped filters in the local CNN will not be transmitted to the server.

We design the weight score vector $E^{k}=[E_{1}^{k},\ldots,E_{\mathrm{J}}^{k}]$ for each client $k$, which is row-wise for fully connected neural networks or RNNs, but filter-wise for CNNs. In the training process described in Section IV-C, client $k$ records adaptive dropout times of each weight row for fully connected neural networks or RNNs in $E^{k}$. While for CNN, client $k$ reports the adaptive dropout times of each filter in $E^{k}$. Assuming that client $k$ holds the $j$-th weight row/filter $\textbf{w}_{j}$ in the $v$-th iteration, the score $E_{j}^{k}$ of $\textbf{w}_{j}$ is updated iteratively by

If the dropping label $\beta^{k,v+1}_{j}=1$ for the weight row $\textbf{w}_{j}$, then $e_{j}=1$; otherwise, $e_{j}=0$.

As FL progresses until global round $r>R_{b}$, FedBIAD enters stage two, where the accumulated dropout experiences are enough to be regarded as the importance indicator. This experience-based importance indicator can guide the client to select an effective dropping pattern, which is beneficial for loss reduction. Hence, in stage two, client $k$ can set the dropping pattern based on $E^{k}$ instead of random sampling, as shown in Fig. 4. The weight score vector determines the dropping pattern as follows. If global round $r>R_{b}$, client $k$ calculates the threshold $\lambda^{k}_{r}$ that is the $p$-quantile of $E^{k}$. If the score $E^{k}_{j}>\lambda^{k}_{r}$, then the dropping label $\beta^{k,0}_{r,j}=\ldots=\beta^{k,V}_{r,j}=1$ for the $j$-th weight row/filter; otherwise, $\beta^{k,0}_{r,j}=\ldots=\beta^{k,V}_{r,j}=0$.

After $V$ training iterations on local data, each client $k\in\mathcal{C}_{r}$ transmits nonzero elements of the latest variational parameters $\{\bm{\mu}_{r,j}^{k,V}|\bm{\mu}_{r,j}^{k,V}\in U_{r}^{k,V},\,\beta^{k,V}_{r,j}\neq 0,\;\text{for}\;j=1,\dots,\mathrm{J}\}$ and the dropping pattern $\bm{\beta}^{k,V}_{r}$ to the server. Subsequently, the server reconstructs complete variational parameters $\bm{\beta}^{k,V}_{r}\circ U_{r}^{k,V}$ based on the received $\bm{\beta}^{k,V}_{r}$, and performs global aggregation by averaging variational parameters [35]:

Essentially, the global variational approximation $\tilde{\pi}^{g}_{r}$ in round $r$ can be denoted as

where $\theta_{r}$ is the global weights in round $r$.

The entire process of FedBIAD is summarized in Algorithm 1, and Fig. 5 briefly depicts the iterative procedure. Moreover, inspired by [15], we can employ FedBIAD in combination with existing sketched compression methods to further lighten the communication burden. As shown in Fig. 5, variational parameters are compressed in steps (2) and (8).

Based on Section III-B, FedBIAD explores a global variational approximation $\tilde{\pi}^{g}$ to estimate the tempered posteriors of client-side data. Considering a global model $f_{\theta}$ with $L$ layers whose weights $\theta$ follow $\tilde{\pi}^{g}$, we define the unsparse number $S$ as the number of nonzero weights in $\theta$ and $D$ as the dimension of hidden layers in the global model. In this way, the global model is determined by $(S,L,D)$, and $\Theta_{S,L,D}$ represents the solution space composed of all feasible weights. The input dimension of the global model is $d$. As discussed in Section IV-A, each device $k\in\mathcal{K}$ owns its data $\mathcal{D}^{k}$ and unknown true function $f_{0}^{k}$ such that $y^{k}=f^{k}_{0}(\bm{x}^{k})$ for any $(\bm{x}^{k},y^{k})\in\mathcal{D}^{k}$.

We define $m$ as the client-side total input data, which is associated with the training round $r$. Considering that different clients have different amounts of local data, after $r$ rounds, the minimum amount of client-side total input data is denoted as $m_{r}=r\times V\times\min\{|\mathcal{D}^{1}|,\ldots,|\mathcal{D}^{K}|\}$, where $V$ is the number of training iterations in each round. To analyze the convergence of the average generalization error in FedBIAD, we start with some assumptions.

Assumption 1 and 2 are common in Bayesian convergence analysis works [21, 28], which are realistic. The activation functions (i.e., relu function $\rho$, tanh function $\varrho$, sigmoid function $\phi$) we used are actually 1-Lipschitz continuous. Besides, the optimal global model is denoted by $\theta^{\ast}=\mathrm{arg}\min_{\theta\in\Theta_{S,L,D}}\frac{1}{K}\sum_{k=1}^{K}\|f_{\theta}-f^{k}_{0}\|_{2}^{2}$, which is fixed. Hence, the absolute values of all weights in $\theta^{*}$ are fixed, and they must have an upper bound.

Based on [21, 28] and Definition 1, the average generalization error of global model learned by FedBIAD is the expected average of the squared L2-distance between the global model $f_{\theta}$ and local unknown true functions $\{f_{0}^{k}|k\in\mathcal{K}\}$, denoted by:

The constant posterior variance is set to

In FedBIAD, the posterior variances of local variational approximations on clients and the global variational approximation on the server are the same in each round. Hence, clients and the server do not exchange posterior variances $\tilde{s}^{2}$ and only compute $\tilde{s}^{2}$ via (13), which is beneficial for communication efficiency. Based on the setting of posterior variance in (13), we can derive the upper bound of the average generalization error expressed by (12) for FedBIAD in Theorem 1.

Through Theorem 1, we get the upper bound of the average generalization error of global model, which can ensure convergence of FedBIAD. Referring to [21], if local true functions $\{f^{k}_{0}|k\in\mathcal{K}\}$ are actually neural networks with structure $(S,L,D)$, the term $\xi^{k}$ denoted by (16) on the right-hand side of (1) vanishes. Then, we only need to analyze the first term on the right-hand side of (1), where $\varepsilon_{m_{r}}^{S,L,D}$ is calculated by (1). According to (1), $\varepsilon_{m_{r}}^{S,L,D}$ apparently declines with the increasing of client-side total input data $m_{r}$. While $m_{r}$ increases with the growth of training round $r$. Therefore, as the round grows, the upper bound of the generalization error of FedBIAD decreases, and FedBIAD gradually converges.

However, if local true functions $\{f^{k}_{0}|k\in\mathcal{K}\}$ are not neural networks with structure $(S,L,D)$ like the global model $f_{\theta}$, we have to consider the term $\xi^{k}$. Motivated by [28, 36], we assume that $\{f^{k}_{0}|k\in\mathcal{K}\}$ are $\gamma$-Hölder smooth functions with $0<\gamma<d$. According to Lemma 5.1 in [36] and Corollary 3 in [21], there exist constants $C,\,C^{\prime}$ such that $\xi^{k}\leq Cm^{\frac{-2\gamma}{2\gamma+d}}_{r}\cdot\log^{2}m_{r}$ and $\varepsilon_{m_{r}}^{S,L,D}\leq C^{\prime}m^{\frac{-2\gamma}{2\gamma+d}}_{r}\cdot\log^{2}m_{r}$. Then, we have

where $C_{1}>0$ is a constant. In addition, based on Theorem 8 in [37], there exists a constant $C_{2}>0$ such that

The (17) gives an upper bound of generalization error for FedBIAD with $\gamma$-Hölder smooth functions, while (18) provides the minimax lower bound [37, 28] of generalization error for FedBIAD. Both (17) and (18) have the same term of $m_{r}^{\frac{-2\gamma}{2\gamma+d}}$, through which we can derive the average generalization error of FedBIAD converges at the minimax rate $m_{r}^{\frac{-2\gamma}{2\gamma+d}}$ up to a squared logarithmic factor for the expected $L_{2}$-distance.

Note that, the setting of posterior variance can affect the generalization error bound. The optimal variance is derived in (13), which is used to derive the minimum generalization error bound in (1). Furthermore, FedBIAD only exchanges variational model parameters without sharing client-side data. Therefore, it does not introduce extra privacy concerns and existing FL privacy-preserving methods can be directly applied.

Datasets. We consider five datasets for the experiment evaluation: MNIST [38], Fashion-MNIST (FMNIST) [39], Penn TreeBank (PTB) [18], WikiText-2 [40], and Reddit [41].

MNIST and FMNIST are 10-class image datasets containing 60,000 training data and 10,000 test data. MNIST is for digital handwriting classification, while FMNIST consists of pictures of fashion clothes, and its task is more challenging than simple MNIST. For MNIST and FMNIST, the number of clients is 1000, and we utilize the non-IID partitioning strategy in [28].

PTB, WikiText-2, and Reddit are three English datasets widely used for next-word prediction [41, 42]. The PTB has a 5.1M training corpus, smaller than most modern datasets. The WikiText-2 is over 2 times larger than the PTB, featuring a vocabulary of more than 30,000 words. Both of them are IID. We randomly sample data without overlap and allocate them to 100 clients. For Reddit, the data are non-IID and the top 100 users with more data are chosen as clients, so that different clients have different sample sizes. The data in clients are split into the training set, validation set, and test set.

Dropout rate settings. Referring to [15], empirical dropout rates are between 0.1 to 0.5, which are associated with model scales. Different datasets require different-scale models [13]. For example, PTB is more challenging than simple MNIST, so the model for training PTB is bigger than MNIST. Large-scale models are often possible to use higher dropout rates [15]. For small-scale models (such as 531KB for MNIST), high rates make shrinking models unable to extract accurate features, degrading accuracy [13]. For MNIST, if dropout rate $p=0.5$, the accuracy results of FedDrop, AFD, FedMP, and FedBIAD are 94.45, 94.26, 94.45, and 94.69, lower than $p=0.2$ (see Table I). Thus, different dropout rates are necessary for different datasets requiring different model scales. Motivated by [13, 15], we set lower dropout rate $p=0.2$ for MNIST with small-scale model ($<1$M), while other four datasets requiring large-scale models ($\geq 1$M) use the same dropout rate $p=0.5$. This selection strategy for dropout rates is feasible in practice.

Performance Comparison. Table I shows the performance results of different methods on test data, where ‘Save Ratio’ is the saving multiples in upload parameter size per round compared to FedAvg, and the results are obtained in a NVIDIA Tesla V100 GPU with 32GB. Besides, ‘Upload Size’ in Table I has included the size of transmitted binary dropping pattern $\bm{\beta}$. Although each hidden layer has an independent row/filter size, the number of dropping labels for these rows/filters in all hidden layers is much less than the number of model weights. Besides, each dropping label is 1bit, while each weight is 32bit. Therefore, the size of $\bm{\beta}$ is much smaller than the model weights. For example, $\bm{\beta}$ in the Reddit dataset is 0.3KB, much smaller than the original model size of 29.8MB. Note that, for next-word prediction, we follow [2] to regard top-3 accuracy as the evaluation metric of model performance because mobile keyboards generally include three candidates, while the evaluation metric of the image classification is top-1 accuracy. As shown in Table I, FedBIAD achieves consistent state-of-the-art accuracy with minimal per-round upload parameters across all datasets. For image classification, FedBIAD reduces 2$\times$ uplink costs while improving accuracy by 2.41% on FMNIST compared to FedAvg. In terms of MNIST and FMNIST, the model architecture consists of several FC layers. Because both FedDrop and AFD can apply dropout to all FC layers, FedBIAD does not significantly outperform FedDrop and AFD in communication efficiency. However, for MNIST, FedBIAD increases accuracy by 0.17% and 0.71% compared to FedDrop and AFD. Similarly, FedBIAD shows 2.47% and 1.22% accuracy improvements on FMNIST.

We also observe from Table I that on next-word prediction, FedBIAD outperforms other baselines in both uplink communication efficiency and test accuracy, achieving a 2$\times$ reduction of uplink costs and up to 1.45% accuracy increase compared to FedAvg. Because FedDrop and AFD cannot be applied to recurrent connections of RNN models, both show smaller save ratios, meaning less reduction in uplink overhead. FedBIAD adaptively drops partial weight rows for recurrent connections, which provides more uplink savings with higher accuracy. Thus, FedBIAD has better communication efficiency than AFD and FedDrop when using LSTM (a typical RNN) layers on next-word prediction. Compared with FedDrop, FedBIAD provides a 1.6$\times$ reduction in uplink costs while increasing accuracy by 1.37% on Reddit. In comparison to AFD, FedBIAD compresses uplink costs by 1.5$\times$ with 0.97% accuracy improvement. Besides, FedBIAD reduces 1.4$\times$ uplink costs and is 2.17% more accurate than Fjord on Reddit.

Motivated by [15], we empirically combine FedBIAD with a sketched compression method, DGC [4], further alleviating communication overhead. We also compare FedBIAD with DGC against other sketched compression approaches, among which SignSGD [11] and FedPAQ [9] compress parameters via 1-bit and 8-bit quantizers, respectively. STC [5] integrates sparsification and quantization into a compression framework. Both STC and DGC require clients to upload the positions of compressed parameters. For fairness, we adopt the same position representation approach, where the position representation of each parameter occupies 64 bits [4]. The performance results are presented in Table II. We notice that FedBIAD with DGC consistently achieves the highest accuracy with the least uplink overhead than other methods. Compared to FedAvg, which does not involve any compression strategies, FedBIAD with DGC achieves up to 612$\times$ reduction in uplink overhead while improving accuracy by up to 2.43%. In addition, FedBIAD with DGC gives up to 3$\times$ better uplink compression than STC with up to 8.07% accuracy improvement. The uplink communication volume of FedBIAD with DGC is about 2$\times$ less than that of naive DGC, and FedBIAD with DGC is 2.26% more accurate than naive DGC. Furthermore, we combine AFD, Fjord with DGC, respectively. Both show lower model accuracy and more uplink costs than FedBIAD with DGC.

Convergence Comparison. To evaluate the convergence of FedBIAD, we report the average training loss and test accuracy of MNIST and WikiText-2 datasets varying with rounds in Fig. 6. Fig. 6a shows the convergence curves of MNIST. We observe that FedBIAD quickly converges to higher accuracy than other baselines. Additionally, FedBIAD nearly achieves the lowest training loss and the highest test accuracy in each round on MNIST. Fig. 6b presents the convergence curves of WikiText-2. For clarity, the curves are smoothed by the moving average, which will cause a few precision biases. As shown in Fig. 6b, although FedBIAD does not provide the lowest training loss, it converges to the best test accuracy, which indicates that FedBIAD avoids overfitting on training data and outperforms other baselines on test data.

The Local Training Time in a Round (LTTR) can be used to characterize the local computation costs. Fig. 7a and Fig. 7b show the LTTR of different datasets, in which time is gained from the end-user device of Macbook Pro 2019 with 32G RAM. We note that FedBIAD increases local computation costs, which is apparent on WikiText-2. Concretely, FedBIAD increases LTTR by 3.4 seconds (8.81%), 1.99 seconds (5.16%), and 6.1 seconds (15.81%) on WikiText-2 compared to FedDrop, AFD, and Fjord.

FedBIAD reduces uplink communication costs with accuracy improvement, so it can accelerate global models to achieve target accuracy. As shown in Fig. 6a and Fig. 6b, under the same number of rounds, FedBIAD can generally achieve higher accuracy, which means that FedBIAD consumes much fewer communication rounds to reach a pre-defined target accuracy. For example, FedBIAD can obtain an accuracy of 31% after 4 rounds on WikiText-2, while Fjord needs 7 rounds and AFD needs 13 rounds. Motivated by [46], we utilize Time-To-Accuracy (TTA) to measure the total training time required to achieve target accuracy, which comprises local running time, parameter transmission time, and parameter aggregation time.

To simulate parameter transmission time, we utilize the T-Mobile 5G network with a download speed of 110.6 Megabits per second (Mbps) and an upload speed of 14.0 Mbps [6]. The target accuracies are 90%, 80%, 31%, and 30% for MNIST, FMNIST, WikiText-2, and Reddit, respectively. Then, we calculate the TTA of different datasets, and the results are shown in Fig. 7c and Fig. 7d. We observe that on four datasets, FedBIAD consistently takes the shortest time to achieve the target accuracy compared with baselines. Although FedBIAD increases LTTR by 6.1 seconds on WikiText-2, it reduces uplink costs and the number of rounds, so the TTA of FedBIAD is 205.1 seconds shorter than Fjord. Specifically, FedBIAD reduces 66.67%, 72.00%, and 43.61% TTA on WikiText-2 compared to FedDrop, AFD, and Fjord, respectively. For FMNIST, the reductions are 29.64%, 23.91%, and 21.54%.

To investigate the effect of dropout rate $p$, we measure accuracy and TTA for different dropout rates on Reddit. As shown in Fig 8a, the results of FedAvg without dropout remain constant as it is not affected by dropout rates. We notice that compared with the other three baselines, FedBIAD provides the highest accuracy at different dropout rates. As shown in Fig. 8b, the TTA decreases as the dropout rate increases, and the TTA of FedBIAD is always shorter than other baselines. It indicates that FedBIAD achieves the goal of efficient communication and guaranteed performance in FL.

We want to analyze the upper bound on the generalization error of global variational approximation $\tilde{\pi}^{g}$ (see Definition 1 in the paper). Based on Theorem 2 in [21], we can obtain generalization properties of a fully connected DNN, where for any client $k$, the global model $f_{\theta}$ satisfies

with

In the proof process, A. Chérief [21] introduce the optimal posterior variance $\tilde{s}_{m}^{2}=\frac{S}{16m}\log(3D)^{-1}(2BD)^{-2L}\{(d+1+\frac{1}{BD-1})^{2}+\frac{1}{(2BD)^{2}-1}+\frac{2}{(2BD-1)^{2}}\}^{-1}$.

Then, we derive the upper bound on the global generalization error of a sparse single-layer RNN that is detailed in Section III-A. We start with the variant inequality of theorem 2.6 in [34]. Given the variational set $\mathcal{F}_{S,T,D}$ of tempered posterior, if there is $q^{\ast}\in\mathcal{F}_{S,T,D}$ and $\varepsilon_{m}>0$ such that

and

then for any $\alpha\in(0,1)$, we get the upper bound on the generalization error of Bayesian variational inference: