Scheduling and Aggregation Design for Asynchronous Federated Learning over Wireless Networks

I Introduction

The training of machine learning (ML) models usually requires a massive amount of data. Nowadays, the ever-increasing number of connected user devices has benefited the development of ML algorithms by providing large sets of data that can be utilized for model training. As privacy concerns become vital in our society, using private data from user devices for training ML models becomes tricky. Therefore, federated learning (FL) with on-device information processing has been proposed for its advantages in preserving data privacy. FL is a collaborative ML framework where multiple devices participate in training a common global model based on locally available data . Unlike centralized ML architecture wherein the entire set of training data need to be centrally stored, in an FL system, only model parameters are shared between user devices and a parameter server. Due to the heterogeneity of participating devices, local training data might be unbalanced and not independent and identically distributed (i.i.d.), which deviates FL from conventional distributed optimization frameworks where homogeneous and evenly distributed data are assumed.

Federated Averaging (FedAvg) is one of the most representative and baseline FL algorithms , with an iterative process of model broadcasting, local training, and model aggregation. In every iteration, the model aggregation process can start only when all the devices have finished local training. Thus, the duration of one iteration is seriously limited by the slowest device . This phenomenon, commonly observed in synchronous FL methods, is known as the straggler issue. One approach to this issue is altering the synchronous procedure to an asynchronous one, i.e., the server does not need to wait for all the devices to finish local training before conducting updates aggregation. In the literature, such an asynchronous FL framework has been adopted in many deep-learning settings . However, fully asynchronous FL with sequential updating can lead to high communication costs due to frequent model exchanges. Hence, we propose an asynchronous FL framework with periodic aggregation, which eliminates the straggler effect without excessive model updating and information exchange between the server and participating devices. As compared to other existing works on FL with asynchronous updates , our proposed design is easy to implement and requires a small amount of side information.

Communication resource limitation is another critical issue in wireless FL systems. As model exchanges take place over wireless channels, the system performance (communication costs and latency) naturally suffers from the limitation of frequency/time resources, especially when the number of participating devices is large. One possible solution to reduce the communication load is to allow a fraction of participating devices to upload their local updates for model aggregation. Then, depending on the allocated communication resources and wireless link quality, each device compresses its model updates accordingly such that the compressed updates can be transmitted reliably given the allocated resources. Device scheduling and communication resource allocation are critical for achieving communication-efficient FL over wireless networks . Intuitively, devices with a higher impact on the learning performance should be prioritized in scheduling. This learning-oriented communication objective stands in contrast to the conventional rate-oriented design adopted in cellular networks, where the aim is to achieve higher spectral efficiency or network throughput. Several existing works consider different metrics to indicate the significance of local updates, such as norm of model updates and Age-of-Update (AoU) . Under the motivation of receiving model updates with less compression loss, some works consider wireless link quality in scheduling design . On the other hand, to take into account the non-i.i.d. data distribution, uncertainty of data distribution is considered in , and in the scheduling design follows the principle of giving higher priority to devices with larger diversity in their local data. Some works consider joint optimization of device scheduling and resource allocation towards minimal latency or empirical loss . Nevertheless, all of them consider synchronous FL systems. Few existing works have considered the design in an asynchronous setting. In , scheduling in asynchronous FL is considered based on maximizing the expected sum of training data subject to the uncertainty of channel conditions, data arrivals, and limited communication resources. However, the effect of non-i.i.d. data distribution is not considered in the scheduling design.

Compared to the synchronous setting, asynchronous FL needs to deal with the asynchrony of local model updates since different devices may perform local training based on different versions of the global model. Some heuristic aggregation designs are explored in the literature. In , devices with more frequent transmission failures from past iterations will transmit enlarged gradient updates. In , larger weights are given to slower tiers in the aggregation process because slower tiers contribute less frequently to the global model. Both approaches aim at equalizing the contributions from different devices, though with i.i.d. data, it might slow down the convergence since model updates obtained from older global models might contain little useful information to the current version.

We summarize the main contributions of this work:

We propose an asynchronous FL framework with periodic aggregation that achieves fast convergence in the presence of stragglers, and avoids excessive model updating as in fully asynchronous FL settings.

We propose a scheduling policy that jointly considers the channel quality and the training data distribution, aiming at reducing the variance and bias of the aggregated model updates. The effectiveness of the proposed method is supported both by theoretical convergence analysis and simulation results.

We propose an age-aware weighting design for model aggregation to mitigate the effects of update asynchrony.

We highlight the impact of update compression, data heterogeneity, and intra-iteration asynchrony in the convergence analysis, which also provides a theoretical motivation for our scheduling design.

II System Model

where $l(\boldsymbol{\theta},x)$ is a sample-wise loss function computed based on the data sample $x$. Similarly, a local loss function of device $k$ is defined as

Then, we can rewrite $\eqref{eq:globalLoss}$ as

To characterize the heterogeneity of data distribution in $\mathcal{N}$, we define a metric

where $F^{*}=\underset{\boldsymbol{\theta}}{\mbox{min}}\,F(\boldsymbol{\theta})$ and $F_{k}^{*}=\underset{\boldsymbol{\theta}}{\mbox{min}}\,F_{k}(\boldsymbol{\theta})$ are the minimal global and local loss, respectively. With i.i.d. data distribution over devices, $\Gamma$ asymptotically approaches when $|\mathcal{S}|$ increases, while in non-i.i.d. scenario we expect $\Gamma\neq 0$, which reflects the data heterogeneity level among devices.

FedAvg is one representative FL algorithm with synchronous procedure of local training and global aggregation. The entire training process is divided into many global iterations (communication rounds), where during each iteration, the server aggregates the model updates from the participating devices computed over their locally available data. We consider a modified version of FedAvg, where an extra step of device scheduling is added after local training, as illustrated in Fig. 1. The main motivation behind this is to reduce the communication costs and delay, especially in a wireless network with limited communication resources. In the $t$-th global iteration, $t=1,2,\ldots$, the following steps are executed:

The server broadcasts the current global model $\boldsymbol{\theta}(t)$ to the device set $\mathcal{N}$.

Each device $k\in\mathcal{N}$ runs $E$ steps of stochastic gradient descent (SGD). The corresponding update rule follows

where $\tau=0,...,E-1$ indicates the local iteration index, $\boldsymbol{\theta}_{k}(t,0)=\boldsymbol{\theta}(t)$, $\alpha(t,\tau)$ represents the learning rate and $\nabla F_{k}(\boldsymbol{\theta}_{k}(t,\tau);\mathcal{B}_{k}(t,\tau))$ denotes the gradient computed based on a randomly selected mini-batch $\mathcal{B}_{k}(t,\tau)\subseteq\mathcal{S}_{k}$. After completing the local training, each device obtains the model update as the difference between the model parameter vector before and after training, i.e.,

After local training, a subset of devices $\Pi(t)\subseteq\mathcal{N}$ are scheduled for uploading their model updates to the server.This uplink scheduling step is particularly important for FL over wireless networks as communication resources need to be shared among devices.

After receiving the local updates from the scheduled devices, the server aggregates the received information and updates the global model according to

This iterative procedure continues until convergence.

II-B Asynchronous FL with Periodic Aggregation

To address the straggler issue in synchronous FL without generating excessive communication load, we propose an asynchronous FL framework with periodic aggregation. The general idea is to allow asynchronous training at different devices, with the server periodically collecting updates from those devices that have completed their computation, while the rest continue their local training without being interrupted or dropped. Fig. 2 shows an example of the training and updating timeline of the original synchronous FL, fully asynchronous FL , and our proposed scheme.

where $\lambda>0$ is the regularization coefficient. For any device $k\in\Pi(t)$, its local update is thus computed as

with $\tau=0,...,E-1$ and $\nabla H_{k}(t,\tau)$ evaluated on a randomly selected mini-batch $\mathcal{B}_{k}(t,\tau)\subseteq\mathcal{S}_{k}$. Due to the asynchronous setup, the initial model in the first local iteration is

indicates the latest global iteration in which device $k$ received an updated global model. After receiving the updates from all devices in $\Pi(t)$, the server conducts model aggregation as

where $\boldsymbol{u}_{k}(t)$ is defined in (4), and $w_{k}(t)$ denotes the weight coefficient, with $\sum_{k\in\Pi(t)}w_{k}(t)=1$. The updated model is then broadcast to all the devices in $\mathcal{K}(t)$ as the new global model to continue local training. Inspired by the concept of Age of Information (AoI) , we define the Age of Local Update (ALU) as

which represents the elapsed time since the last reception of an updated global model.Note that this age-based definition is different from the Age of Update (AoU) proposed in , which measures the elapsed time at each device since its last participation in model aggregation. The weight $w_{k}(t)$ can be related to the training data size $|\mathcal{S}_{k}|$, or the ALU $a_{k}(t)$, or combination of the both. Since the transmission of the model updates $\boldsymbol{u}_{k}(t),\forall k\in\Pi(t)$ is subject to communication resource constraints, a compressed version of $\boldsymbol{u}_{k}(t)$, denoted as $\hat{\boldsymbol{u}}_{k}(t)$, will be transmitted over the wireless channels. The compression scheme will be elaborated in the next sub-section.

II-C Physical Layer (PHY) Model

In an FL process, the communication part takes place in two phases, the server broadcasting global model to the devices (downlink transmission) and the devices reporting model updates to the server (uplink transmission). In general, the server has much higher transmit power than the devices, and the downlink transmission does not require dividing communication resources due to the broadcast channel. Therefore, we assume no compression errors in the downlink. However, uplink transmission suffers from the communication bottleneck, which makes the scheduling and resource allocation design particularly important.

We consider that at any global iteration $t$ the model updates from all devices are transmitted over a block fading channel with $n$-symbol coherence block. We assume orthogonal resource allocation among devices, i.e., $n_{k}(t)$ symbols are exclusively allocated to the device $k$ and $\sum_{k=1}^{|\Pi(t)|}n_{k}(t)=n$. Therefore, the transmissions from multiple devices are interference-free. Let $\beta_{k}$ and $h_{k}(t)$ denote the large-scale and small-scale fading of the channel from the $k$-th device to the server, respectively. Assuming that the $k$-th device has transmit power $P_{k}(t)\leq P_{k}^{\max}$ and the additive noise in the channel follows $CN(0,\sigma_{w}^{2})$, the channel capacity of the $k$-th link is

We consider that the devices apply appropriate data compression and channel coding scheme according to the channel capacity in (8) such that the transmissions of the model updates are error-free. Consequently, the server can reliably receive up to $n_{k}(t)C_{k}(t)$ bits from device $k$. The symbol allocation, $n_{k}(t),\forall k$, and data compression scheme are specified below.

To achieve the same level of compression loss in model updates from each device, we allocate the symbol resources in a way that

which implies that the devices with better channels are allocated with less symbols. Similar design is considered in .

II-C2 Sparsification and Quantization

Here, the first term $\log_{2}{d\choose r_{k}(t)}$ bits are used for sending the indexes $\mathcal{V}_{k}(t)$, the second term $32$ bits are for the vector norm value, and the third term means that $\left\lceil\log_{2}(\nu+1)\right\rceil+1$ bits are needed for transmitting each non-zero element of $\hat{\boldsymbol{u}}_{k}(t)$.

II-D Motivation of Scheduling and Aggregation Design

Under the proposed asynchronous FL setup, the key design questions are:

Given the communication resource constraints, how should we schedule a subset of $\mathcal{K}(t)$ for model aggregation under the scenario of heterogeneous training data distribution and wireless link quality?

Different devices might have different ALUs, either more recent or more outdated. How to design an appropriate weighting policy taking into account the freshness of model updates?

If all the devices have i.i.d. training data, we expect that $\Gamma\rightarrow 0$, as discussed in Sec. II. It directly follows that

II-D2 Data compression

As the model updates are transmitted through rate-limited wireless channels, the server only receives noisy information due to data compression. Larger compression loss will give a larger variance of the aggregated model.

II-D3 Asynchronous model updates

As shown in Sec. 2, the received updates $\boldsymbol{u}_{k}(t),\forall k$ might have different ALUs, which will be an extra source of variation in $||\boldsymbol{\theta}\left(t+1\right)-\boldsymbol{\theta}^{*}||_{2}^{2}$.

The scheduled devices should construct a homogeneous representation of the entire training data set $\mathcal{S}$.

Compression loss needs to be kept low, which motivates us to prioritize devices with better channel conditions.

From the perspective of model aggregation, we can alleviate the adverse impact of asynchronous updates by considering age-aware weighting design in the aggregation process.

III Scheduling and Aggregation Design for Asynchronous FL

We propose a scheduling policy that aims at achieving a smaller optimality gap, by considering the training data distribution and the channel conditions of ready-to-update devices.Our scheduling design is applicable to any distributed ML setting with heterogeneous and unbalanced data, not only in the considered asynchronous FL setting. Then, the aggregation weights are adjusted accordingly to alleviate the harmful impact from asynchronous training.

To illustrate the idea, we consider a classification problem with labeled data. The training data set is represented by $\mathcal{S}=\{(x,y)|y\in\mathcal{L}\}$, where $\mathcal{L}=\{y_{1},...,y_{\omega}\}$ is a finite set that contains all labels and $|\mathcal{L}|=\omega$. For any device $k$, $\boldsymbol{b}_{k}=[b_{k}^{1},...,b_{k}^{\omega}]$ is defined as the label distribution in $\mathcal{S}_{k}$, where $b_{k}^{j}$ is the number of $y_{j}$-labeled samples and $\sum_{j=1}^{\omega}b_{k}^{j}=|\mathcal{S}_{k}|$. To construct a homogeneous data distribution, we may select $\Pi(t)$ to achieve the minimal label variance

where $\bar{b}=\frac{1}{\omega}\sum_{j=1}^{\omega}\sum_{k\in\Pi(t)}b_{k}^{j}$. Additionally, scheduling devices with better channel quality leads to smaller compression loss per device. Combine these two selection criteria, we first pick a subset $\Pi^{\prime}(t)\subseteq\mathcal{K}(t)$ comprising of devices with $\mbox{min}(0.5N,|\mathcal{K}(t)|)$ highest channel capacity $C_{k}(t)$. Next, we find $\Pi(t)=\underset{\Pi\subseteq\Pi^{\prime}(t)}{\mbox{argmin}}\,\Omega\left(\Pi\right)$.

III-B Age-aware Model Aggregation

To tackle the asynchrony in model aggregation, we assign the weights not only based on the data proportion as in (5), but also on its ALU. The age-aware weighting design follows

Here, $\gamma$ is a real-valued constant, and the choice of its value can be divided into three cases:

$\gamma>1$, of which the system favors older local updates.

$\gamma<1$, of which the system favors fresher local updates.

$\gamma=1$, which is equivalent to the baseline design in (5).

Favoring older updates could potentially balance the participation frequency among the devices and reduce the risk of model training biased towards those with stronger computing capability. This design performs well when data distribution is highly non-i.i.d. and some devices with inferior computing capability possess unique training data. However, it also creates the problem of applying outdated updates on the already-evolved model. On the other hand, favoring fresher local updates would help the model to converge fast and smoothly with time, at the risk of converging to an imbalanced model biased towards devices with superior computing power. Since the proposed scheduling policy is conducted in a way that improves the homogeneity of data distribution, the advantage of “favoring fresher models” strategy becomes more convincing.

To summarize, the channel-aware data-importance-based scheduling design with favoring-fresh aggregation policy would lead to fast and smooth convergence performance. To verify the effectiveness of our design, we provide convergence analysis in Sec. IV and simulation results in V, respectively.

IV Convergence Analysis

We introduce some notations and definitions for the convergence analysis of the proposed system.

Let $M(t)$ be the number of different versions of receive global model in the $t$-th model aggregation, i.e., the number of unique elements in the set $\{a_{k}(t)|k\in\Pi(t)\}$.

Let $\mathcal{M}_{i}(t)\subseteq\Pi(t),i=1,...,M(t)$ be a device subset with the same ALU, i.e., $\forall k,j\in\mathcal{M}_{i}(t)$, $a_{k}(t)=a_{j}(t)$.

As in the proposed system, device scheduling is subject to the ready-to-update set $\mathcal{K}(t)$ instead of the full device set $\mathcal{N}$, we introduce the following metrics to quantify the data heterogeneity level for any device subset $\mathcal{M}$.

(Data heterogeneity level): For a device subset $\mathcal{M}\subseteq\mathcal{N}$ and $\sum_{k\in\mathcal{M}}w_{k}=1$Note that $\Gamma_{1}(\mathcal{N})=\Gamma$ if $w_{k}=\frac{|\mathcal{S}_{k}|}{|\mathcal{S}|},\forall k\in\mathcal{N}$. Besides, devices in any $\mathcal{M}_{i}(t)$ have the same ALU, so $w_{k}(t)$ are simplified to the case with $\gamma=1$., we define

To facilitate analysis, we make the following baseline assumptions.

followed by assumptions for stochastic gradient evaluation,

for some positive constant $C_{1}$ and $C_{2}$.

Let $\mathcal{M}$ be a subset of $\mathcal{N}$. Since $\mathcal{N}$ is a finite set, there exist non-negative $\zeta_{1}$ and $\zeta_{2}$ such that

i.e., the metrics of heterogeneity level are uniformly bounded.

Additionally, for the reserved number $r_{k}(t)$, we assume that there exists a minimum $r_{\min}>0$ such that

where the expectation is with respect to the randomness in wireless channels.

IV-B Convergence Study

In the following theorem, we provide the main convergence result of our system model in a special case with one local iteration per communication round, i.e., $E=1$.

Under Assumptions 1-3, equations (15)-(18), $E=1$, diminishing learning rate $\alpha(t,0)=\frac{\beta}{t+\kappa}$ with $\beta>\frac{d}{\mu r_{\min}}>0$ and $\kappa=\mbox{max}\{\frac{dL^{2}C_{2}C_{3}\beta^{2}}{\beta\mu r_{\min}-d},4L\beta-1,1\}>0$, and partial device participation such that $\Pi(\rho)=\cup_{j=1,...,M(\rho)}\mathcal{M}_{j}(\rho)\subseteq\mathcal{N},\rho=1,...,t$, the proposed scheme satisfies

where $A=2\left(\zeta_{1}+\zeta_{2}\right)$, $C_{3}=4(1+\frac{d}{4\nu^{2}})$, and

The expectation is taken over the randomness of stochastic gradient, channel gain and model compression, and device scheduling of all the past iterations.

The impact of multiple local iterations, i.e., $E>1$, on the convergence analysis has been already established and exploited in existing literature on FL (see, e.g., ,). The focus of our analysis is the impact of update compression, training data heterogeneity, and intra-iteration asynchrony on the system convergence. We believe that extending our results to the case with $E>1$ is possible by following approaches from, for example, , or ; this, however, would require, among other things, quantifying local model divergence.An extra term $||\boldsymbol{\theta}_{k}(t,\tau)-\boldsymbol{\theta}_{k}(t,0)||_{2}^{2}$ will be introduced and could be bounded by its gradient $||\nabla F_{k}(\boldsymbol{\theta}_{k}(t,\tau))||_{2}^{2}$ through (14). The learning rate would then have to be redesigned accordingly. For analytical clarity and simplicity, we consider the case with $E=1$.

Based on Theorem 1, the optimality gap asymptotically converges to a constant, i.e.,

when $t\rightarrow\infty$, where $M$, $A$, and $\beta$ are defined in (15) and in the theorem. This constant can be seen as an optimality gap, which increases with $A$, $M$ and $\beta$. In an i.i.d. data scenario where $\zeta_{1}=\zeta_{2}=0$ and thus $A=0$, the system converges to the optimum even with intra-iteration asynchrony, i.e., $M>1$, and update compression, i.e., $\beta>\frac{1}{\mu}$. However, in a non-i.i.d. scenario where $A>0$, a higher level of data heterogeneity leads to a larger optimality gap. The presence of $M$ implies that intra-iteration asynchrony makes the optimality gap larger. Moreover, the presence of $\beta$ reflects that scheduling devices with better channel quality improves the performance, since a larger $r_{\min}$ allows a lower $\beta$, given $\beta>\frac{d}{\mu r_{\min}}$ specified in the theorem and $r_{\min}$ defined in (18).

Apart from the asymptotic behavior, compression level of model updates also affects the per-iteration performance. With better link quality, the sparsification can be less aggressive, and/or with a higher quantization level $\nu$. As the result, the term $J(\beta,\kappa)$ can be smaller and thus the optimality gap in each iteration decreases. Moreover, as $J(\beta,\kappa)$ grows with $A$, lower data heterogeneity also improves the per-iteration performance.

These two remarks confirm the importance of considering both training data distribution and channel quality in our device scheduling design.

V Simulation Results

We perform simulations using the MNIST data set for solving the hand-written digit classification problem by adopting a convolutional neural network with model dimension $d=21840$. The block fading channel spans $n$ symbols for uplink transmissions. We consider Rayleigh fading $h_{k}(t)\sim\mathcal{CN}(0,1)$ and uplink power control such that the received signal-to-noise ratio is $13$dB. The system parameters are specified as follows.

(Training data distribution) $|\mathcal{S}|=60000$ samples are distributed evenly to all the devices. Both i.i.d. and non-i.i.d. data distribution scenarios are considered. For the i.i.d. case, $|\mathcal{S}|/N$ samples are randomly allocated to each device without replacement. For the non-i.i.d. case, the data allocation follows the setup in , where each device contains up to $\mbox{min}(\lfloor 200/N\rfloor,10)$ different digits.

(Heterogeneous computing capability) We use $T_{k}$ as the local training duration of device $k$, generated from uniform distribution $T_{k}\sim\mathcal{U}(T_{\min},T_{\max})$, where $T_{\min}$ is the least possible device training time.

(Compression) $4$-level random quantizer, $\mathcal{Q}_{4}$, is adopted.

(Diminishing learning rate) $\alpha(1,0)=0.01$ is initially adopted, together with regularization coefficient $\lambda=0.02$.

Since the communication resources are shared by maximally $R$ devices, more scheduled devices means less communication resources per device, leading to a higher compression loss. The test accuracy results with various choices of $R$ are shown in Fig. 3. As we can see, in the i.i.d. scenario, a smaller $R$ is preferable since it gives received model updates with better precision as the result of more allocated bits per user. On the other hand, in the non-i.i.d. scenario, there exists a trade-off between compression loss and model bias, which makes the choice of $R$ important. In this work, we focus on the impact of the scheduling design for a fixed $R$. The optimal value of $R$ depends on many system parameters; its optimization could be studied in future work.

The comparison between our proposed design, FedAvg, and FedAsyncAn $\alpha$-filtering mechanism is applied on device updates, specifically, $\boldsymbol{\theta}(t+1)=(1-\alpha)\boldsymbol{\theta}(t)+\alpha\boldsymbol{u}_{k}(t)$. (with $\alpha=0.4$ and $\alpha=0.8$) is shown in Fig. 5. We observe that although FedAsync can help reduce the straggler effect, the test accuracy result shows strong fluctuation, especially with non-i.i.d. training data. For both i.i.d. and non-i.i.d. scenarios, our proposed asynchronous FL design outperforms FedAsync and FedAvg, which shows its effectiveness in eliminating the straggler effect and achieving better convergence performance.

V-B Validation of convergence analysis

We provide training loss comparison in Figure 6 to validate the conclusions drawn in Remarks 4 and 5. We observe the following:

With the random and proposed scheduling methods, the training loss is lower in the i.i.d. scenario than in the non-i.i.d. scenario, which shows that a smaller $A$ leads to a lower training loss.

For both the i.i.d. and non-i.i.d. scenarios, our proposed scheduling design outperforms random scheduling, which validates the advantage of selecting devices with better link qualities and, collectively, a more homogeneous data representation.

To show the impact of intra-iteration asynchrony, we present the result for synchronous updates with random scheduling for i.i.d. data (the green curve). As compared to the asynchronous case (blue curve), the synchronous case has lower training loss, which shows that intra-iteration asynchrony is harmful for the convergence performance.

V-C Comparison of scheduling policies

First, the aggregation weights are set with $\gamma=1$ in (13). In Fig. 7, we show the test accuracy of the proposed scheduling design with some alternative reference methods.

rdm: we select up to $R$ devices uniformly at random.

BC : We select up to $R$ devices with highest $C_{k}(t)$.

BCBN2 For a fair comparison, symbol resource allocation follows (9), differing from the design in .: We first find a device subset $\mathcal{C}\subseteq\mathcal{K}(t)$ with $|\mathcal{C}|$ up to $0.5N$ that has highest $C_{k}(t)$. Then, among $\mathcal{C}$ we schedule devices with up to $R$ highest $||\boldsymbol{u}_{k}(t)||_{2}^{2}$.

Age-based This is a tweaked version of the method in , which likewise finds devices with better channel quality and minimizes the overall device staleness.: We first find $\mathcal{C}$ using the same way as in BCBN2, then among $\mathcal{C}$ we schedule up to $R$ devices with highest staleness metric

We see that the proposed scheduling policy outperforms the baseline random scheduling and the reference methods in both i.i.d. and non-i.i.d. scenarios. Besides, in non-i.i.d. scenario, we observe that the data-awareness in the proposed method further achieves a higher test accuracy than the pure channel-aware methods BC and BCBN2 .

V-D Comparison of aggregation policies

In Fig. 8, we show the performance of different aggregation policies under the proposed channel-aware data-importance-based scheduling and random scheduling methods. We see that the age-aware design outperforms the baseline with $\gamma=1$ in both i.i.d. and non-i.i.d. scenarios. For i.i.d. case, the favoring-fresh weighting strategy has an outstanding performance gain. For non-i.i.d. case, performance gain of the proposed aggregation design is more obvious when random scheduling is adopted.

VI Conclusions

In this work, we proposed an asynchronous FL framework with periodic aggregation that combines the advantages of asynchronous training and synchronous model aggregation. For the proposed design, we further developed a channel-aware data-importance-based scheduling policy and age-based aggregation design for FL under wireless resource constraints. Our proposed scheduling and aggregation design was shown to outperform existing methods, especially with heterogeneous training data among different devices. The main takeaway message is that the design principle of scheduling and resource allocation in wireless FL should be based on reducing the bias and variance of aggregated local updates. For asynchronous FL settings, balancing the freshness and usefulness of local model updates and adjusting their contributions in the new global model is also an important design aspect.

VII Acknowledgement

We thank Fredrik Jansson for his contribution to the idea of scheduling policy during his Master thesis project at the Division of Communication Systems, Linköping University.

VIII Appendix

We conduct the proof with a similar approach as in and except for some additional manipulations to handle the effect of asynchronous training. As briefly demonstrated in Section II-D, we begin the optimality gap analysis from (12). We define

as the weighting sum in $\mathcal{M}_{m}$ in $t$-th global iteration and

To facilitate analysis, we first evaluate $||\bar{\boldsymbol{\theta}}^{\left(m\right)}\left(t+1\right)-\boldsymbol{\theta}^{*}||_{2}^{2}$ for any ($m$,$t$) and simplify the notation of existing variables.

$\mathcal{M}_{m}(t)$, $\bar{\boldsymbol{\theta}}^{\left(m\right)}\left(t+1\right)$, $\bar{\boldsymbol{\theta}}^{\left(m\right)}\left(t\right)$, $w_{k}(t)$, $r_{k}(t)$, and $c_{m}(t)$ are simplified as $\mathcal{M}$, $\bar{\boldsymbol{\theta}}\left(t+1\right)$, $\bar{\boldsymbol{\theta}}\left(t\right)$, $w_{k}$, $r_{k}$, and $c$.

Since $E=1$, for $\alpha(t,0)$ and $\mathcal{B}_{k}(t,0)$ we omit index $\tau=0$ for simplicity and rewrite them as $\alpha(t)$ and $\mathcal{B}_{k}(t)$, respectively. Moreover, $H_{k}\left(t,0\right)=F_{k}\left(\boldsymbol{\theta}_{k}(t,0)\right)$ and

Resource allocation in (9) and transmission constraint in (10) lead to equivalent $r_{k},\forall k$. Hence, $r_{k}=r,\forall k$.

In addition, we introduce some variables and lemmas,

Let $\alpha(t)\leq\frac{1}{4L}$ and $A$ defined in Theorem 1, then

Let $C_{3}$ and $A$ defined in Theorem 1, then the variance of $\boldsymbol{g}\left(t\right)$ fulfills

Based on (20)-(21), $||\bar{\boldsymbol{\theta}}\left(t+1\right)-\boldsymbol{\theta}^{*}||_{2}^{2}$ can be rewritten as

where (22) is due to $\boldsymbol{\theta}_{k}\left(t,0\right)=\boldsymbol{\theta}\left(t\right),\forall k$. With Lemma 1 and (18), the total expectation of (23) fulfills

With diminishing learning rate $\alpha(t)=\frac{\beta}{t+\kappa}$, of which $\alpha(1)=\beta/(1+\kappa)\leq 1/(4L)$ satisfying the sufficient condition in Lemma 1, we claim that

where $v=\max\left[(\kappa+1)||\boldsymbol{\theta}\left(1\right)-\boldsymbol{\theta}^{*}||_{2}^{2},C_{4}\right]$ and

where $\bar{\boldsymbol{\theta}}\left(1\right)=\boldsymbol{\theta}\left(1\right)$ is the initial global model. We assume (25) holds and proceed with the case of $t+1$,

where (27) is due to the second term in (26) being negative. Hence, (25) holds for all $t$. Recovering the indices $m$ and $t$ and plugging the result into (19),

VIII-B Proof of Lemma 1

where (28) and (29) are due to the convexity of $||\cdot||_{2}^{2}$ and $\bar{\boldsymbol{\theta}}\left(t\right)=\boldsymbol{\theta}_{k}\left(t,0\right),\forall k$, respectively. The third term of (29) is constrained by the convexity of $F_{k}\left(\boldsymbol{\theta}\right)$,

By applying (30), and (38) in Section VIII-D, (29) is rearranged asSee Section VIII-D for details.

Based on the convexity of $||\cdot||_{2}^{2}$ and some manipulations,

Since $\alpha(t)\leq 1/(4L)$, we have $-\frac{2\alpha(t)r}{d}\left[1-\frac{Lr\alpha(t)}{d}\right]<0$. Then,

VIII-C Proof of Lemma 2

As the bound in (35) does not depend on current scheduling policy $\mathcal{M}$, the proof is completed.

Define the right-hand side of (36) as a new function

Since $g\left(\boldsymbol{\theta}_{1}\right)$ is a quadratic function with global minimum $g\left(\boldsymbol{\theta}^{*}\right)$ and $\nabla g\left(\boldsymbol{\theta}^{*}\right)=\boldsymbol{0}$, it follows that

References