Tackling the Data Heterogeneity in Asynchronous Federated Learning with Cached Update Calibration
Authors: Yujia Wang
Yuanpu Cao
Jingcheng Wu
Ruoyu Chen
Jinghui Chen
Venue: ICLR 2024 poster (2024)
Keywords: Federated learning
Nonconvex optimization
Primary area: optimization

Abstract: Asynchronous federated learning, which enables local clients to send their model update asynchronously to the server without waiting for others, has recently emerged for its improved efficiency and scalability over traditional synchronized federated learning. In this paper, we study how the asynchronous delay affects the convergence of asynchronous federated learning under non-i.i.d. distributed data across clients. Through the theoretical convergence analysis of one representative asynchronous federated learning algorithm under standard nonconvex stochastic settings, we show that the asynchronous delay can largely slow down the convergence, especially with high data heterogeneity. To further improve the convergence of asynchronous federated learning under heterogeneous data distributions, we propose a novel asynchronous federated learning method with a cached update calibration. Specifically, we let the server cache the latest update for each client and reuse these variables for calibrating the global update at each round. We theoretically prove the convergence acceleration for our proposed method under nonconvex stochastic settings. Extensive experiments on several vision and language tasks demonstrate our superior performances compared to other asynchronous federated learning baselines.

Published as a conference paper at ICLR 2024
TACKLING THE DATA HETEROGENEITY IN ASYN- CHRONOUS FEDERATED LEARNING WITH CACHED UP- DATE CALIBRATION
Yujia Wang', Yuanpu Cao', Jingeheng Wu', Ruoyu Chen", Jinghui Chen 'The Pennsylvania State University *Carnegie Mellon University jyj4442, ymc5533) @psu. (jingchew, ruoyuche ) @andrew. cmu edu, jac5917epsu.edi
ABSTRACT
Asynchronous federated learning, which enables local clients to send their model update asynchronously to the server without waiting for others, has recently emerged for its improved efficiency and scalability over traditional synchronized federated learning. In this paper, we study how the asynchronous delay affects the convergence of asynchronous federated learning under non-i.idd. distributed data across clients. Through the theoretical convergence analysis of one representative asynchronous federated learning algorithm under standard nonconvex stochastic settings, show that the asynchronous delay can largely slow down the conver- gence, especially with high data heterogeneity. To further improve the convergence of asynchronous federated learning under heterogeneous data distributions, we propose a novel asynchronous federated learning method with cached update calibration. Specifically, let the server cache the latest update for each client and reuse these variables for calibrating the global update at each round. We theoreti- cally prove the convergence acceleration for our proposed method under nonconvex stochastic settings. Extensive experiments on several vision and language tasks demonstrate superior performances compared to other asynchronous federated learning baselines.
INTRODUCTION
Federated learning (FL) (Konečný et al. 2016) has become an increasingly popular large-scale machine learning paradigm where machine learning models are trained on multiple edge clients guided by central server. FedAvg (McMahan et al. (017) (McMahan et al. 2017). also known as Local SGD (Stich) (2018), is one of the most popular federated optimization methods, where each client locally performs multiple steps of SGD updates followed by the synchronous server aggregation of the local models. However, the traditional synchronous aggregation scheme may cause efficiency and scalability issues as the server need to wait for all participating clients to complete the task before conducting the global update step. This promotes the development of asynchronous federated learning methods such as FedAsyne (Xie al., 2019). FedBuff (Nguyen al., 2022), which adopt flexible aggregation schemes and allow clients to asynchronously send back their model update and thus improve the overall training efficiency and scalability.
Such an asynchronous aggregation scheme does not come with no costs: the asynchronous delay, which describes the fact that the delayed local model update could be computed based past global model rather than the current global model, slows down the convergence of asynchronous federated learning. Moreover, the negative impact of the asynchronous delay on the convergence gets even worse when the training data are non-i.i.d. distributed across clients. This is intuitive since empirical observation suggests that the global model changes more significantly in adjacent rounds when the data heterogeneity is high. Consequently, the asynchronous delay would cause the delayed local model update to more outdated and inconsistent with the current global model, hence worsening the overall model convergence. Furthermore, each global update in asynchronous federated learning

---

Published as a conference paper at ICLR 2024
is, by nature, contributed from only fraction of clients (similar to the partial participation scenarios in synchronous FL). This intensifies the global variance arising from data heterogeneity and leads to a further slowdown convergence. Therefore, it is crucial tackle the data heterogeneity issue to improve the overall convergence of asynchronous federated learning.
In this work, we rigorously study how the asynchronous delay affects the convergence of asynchronous federated learning under non-i..d. distributed data across clients. Through a theoretical convergence analysis of FedBuff (Nguyen al., 2022 one representative asynchronous federated learning algorithm, we show that the asynchronous delay can largely slow down the convergence, especially with high data heterogeneity. To further improve the convergence of asynchronous federated learning under heterogeneous data distributions, we propose a novel asynchronous federated learning method, Cache-Aide Asynchronous Federated Learning FC.2FL). CA allows the server cache the latest update from each client and reuses this cached update for calibrating the global update, which does not incur extra communication/commptaaai concerns (same as the traditional synchronous and asynchronous federated learning methods). We summarize contribution in this paper as follows:
overhead on clients, or raise any additional privacy
We present a convergence analysis of FedBuff (Nguyen et al. 2022), one representative asyn- chronous federated learning algorithm, under non-i.i.d. distributed data across clients (with fewer assumptions and slightly tighter bound on the asynchronous delay term). We demonstrate that the asynchronous delay can theoretically slow down the convergence and such an impact could be further amplified by the highly non-i.i.d. distributed data.
To tackle the convergence degradation in asynchronous federated learning caused by the joint effect of data heterogeneity and asynchronous delay, we propose novel asynchronous federated aggregation method with cached update calibrations (CA'FL) in which the server maintains cache updates for each client and reuse the cached update for global aggregation calibration. We theoretically show that with the help of cached updates, our proposed method can significantly improve the convergence rate under nonconvex stochastic settings.
Extensive experiments on several vision and language tasks demonstrate our superior perfor- mances compared to other asynchronous federated learning baselines and back up our theory.
2 RELATED WORK
Synchronous FL and Heterogeneity Issues. Federated learning (Konečný et al. 2016) plays
critical role in jointly training models at edge devices without sharing local data. Since FedAvg
(McMahan al. 2017). many federated learning variants are proposed (Li et al. 2019b: Stich 2018
Yang et al.) 2021 for various training scenarios. |Reddi al. (202T): Tong et al. (2020) Wang et al.
(2022) propose adaptive federated optimizers for dealing with heavy-tail stochastic gradient noise
distributions. Gu et al. [ Yan et al. (202)) focus on improving the overall FL performance by leveraging the latest historical gradients. Recently, many works also focused on addressing the data heterogeneity issue through several aspects. FedProx (Li ct al. 2020) adds proximate term to align the local model with the global one. FedDyn (Acar et al. 2021) ) involves a dynamic regularization term for local and global model consistency. FedNova (Wang et al. 2020b) proposes a normalized averaging mechanism that reduces objective inconsistency with heterogeneous data. Moreover, several works studied how to eliminate the client drift caused by data heterogeneity from the aspect of variance reduction including Karimireddy et al. 20200baa a); Khanduri et al. b; Cutkosky & Orabona 2 ; Jhunjhunwala al. (2022). They usually introduce additional control variables to track and correct the local model shift during local training, at the cost of extra communications for synchronizing these control variables. Besides, FedDC (Gao et al., 2022) involves both dynamic regularization terms and local drift variables for model correction.
Asynchronous SGD and Asynchronous FL. Asynchronous optimization methods such asyn- chronous SGD and its variants have been discussed for many years. Hogwild! SGD (Niu et al. 2011) studies a coordinate-we wise asynchronous method without any locking, and (Nguyen et al. 2018)
Herr we focus the FedBuff algorithm without differential privacy for the entire paper.
2

---

Published as a conference paper at ICLR 2024
provided tight convergence analysis for SGD and Hogwild! algorithm. Some other works focus the theoretical analysis for the asynchronous SGD such as (Mania et al. 2017 Stich et al. 2021
(Leblond et al., 2018) studies the asynchronous SAGA method and demonstrates its theoretical convergence. (Glasgow& & Wootters 2022) explored asynchronous SAGA methods for the distributed- data setting and provided a theoretical analysis. In the context of federated learning, FedAsyne (Xie)
iet al.
2019) is proposed for clients to update asynchronously to the server. FedBuff (Nguyen et al.
2022) proposed a buffered asynchronous aggregation strategy. Later Toghani & Uribe (2022) studies
the convergence analysis of FedBuff with fewer assumptions. Anarchic Federated Averaging YYnng
ct al. 2022) focuses on letting the clients decide when and whether to participate in global training. Stripelis et al. (2022) proposed a semi-synchronous federated learning method for energy-efficien training and accelerating convergence in cross-silo settings. SWIFT (Bornstein et al.] 2023) is an interesting wait-free decentralized FI. paradigm that shares similar idea to asynchronous Fl., and SWIFT also involves caching models by storing the neighboring local models. Moreover, there are several works studying the theoretical convergence analysis in asynchronous federated learning with arbitrary delay (Avdiukhin & Kasiviswanathan, [202] Mishchenko et al.] 2022) or the complete theoretical analysis under various assumptions (Koloskova et al. 2002)..
3 PRELIMINARIES FINDINGS ON ASYNCHRONOUS FEDERATED LEARNING
Federated Learning. In general federated learning framework, we aim to minimize the following objective through N local clients:
N Fl(z) = N Σ B (F(
N
1
min f(z) EERd
= N E1
(3.1)
where x represents the model parameters with dimensions, the local loss function corresponding to client and let 'D denotes the local data distribution on client i. FedAvg (McMahan et al., 2017) is a popular synchronous optimization algorithm to solve Eq. 3.1 where each participating client performs local SGD updates, and the server performs global averaging steps after receiving all the updates from assigned clients.
= = (F, (x),
E:)] represents
Asynchronous Federated Learning. Asynchronous federated learning has been introduced to facilitate efficiency and scalability for clients in solving Eq. 3.1 asynchronousll.. In asynchronous federated learning, clients are allowed train and synchronize local models on their own pace. For example, FedBuff [guuyen et al. 2022) studied asynchronous federated learning method with global update buffer and differential privacy mechanism. To give more concrete idea, we present a general asynchronous federated learning framework, which is essentially FedBuff without the differential privacy part, as shown in Algorithm I Specifically, the server initializes by randomly selecting active client set Mi with the size of the concurrency Mc. Then each assigned client will conduct K steps of local training asynchronously. This means the server does not need to wait until all assigned clients finish their local training to proceed, instead, the server just accumulates the model update in A, (Line 5 in Algorithm D and updates the global model every time it accumulates M updates" (Lines 9-11 1 in Algorithm I). Meanwhile, once the server receives client update, it will instantly re- se-sam another available client to continue the federated learning procedure. In this way, the server always maintains fixed number of active clients (i.c., the concurrency Mc).
Heterogeneity Across Clients. Several works (Karimireddy et al. 2020b Acar al., 202 Wang et al. 2020b) have shown that synchronized federated learning methods suffer from convergence and empirical degradation when data heterogeneously distributed across local clients. This issue of model inconsistency also occurs in asynchronous federated learning and may even become worse with the existing of gradient delay, since the model used for local gradient computation is usually different from the current global model, which makes local updates less representative of the global update direction. In order formally illustrate such relationship, we conduct the following convergence analysis on Algorithm | under standard stochastic nonconvex optimization settings. First, we introduce some necessary assumptions.
'The concurrency implies that the maximum size of the simultaneously active clients is M..
M denotes the buffer size in Fedbuff and M 2
3

---

Published as a conference paper at ICLR 2024
Algorithm FedBuff without DP
Input: local step size 1/t, global stepsize 77, server concurrency Mc. buffer size M;
1: Initialize A = 0, m = 0 and sample a set of Mc active clients to run local SGD updates.
2: repeat
3: if receive client update then
4: Server accumulates update from client i: A, + A. + A and set m +- m +
5: Samples another client j from available clients
6: Broadcast the current model æ; to client j, and local SGD updates on client j
7:
end if
8:
if m = .M then
9:
Update global model F₁-1 2t + +
10: Set O, A++1 f 0, - +++++1 ++1
11: end if
12:
until Convergence
Assumption 3.1 (Smoothness). Each loss function on the i-th worker F((x) is L-smooth, i.e., Vx, E R Fi(x)) - F.(y) (VF(()) w) S - --12
This also implies the L-gradient Lipschitz condition, i.e., [V+ VF(y)) S L| yll- Assumption 3.1 standard assumption in nonconvex optimization problems, which has been also adopted in (Kingma & Ba 2013 Reddi et al.) 2018 Li al. 2019a Yang et al. 202T).
Assumption 3.2 (Bounded Variance). Each stochastic gradient on the i-th worker has bounded local variance, i.e., for all æ, E [[V have B f[ fa fa , <) - (=]()) I o², and the loss function on each worker has global variance bound, 2 Σ VF(()) v f()))] ooz
Assumption 3.2 is widely used in federated optimization problems (Li et al. 2019a Reddi et al. 2021 Yang et al. and the bounded global variance represents data heterogeneity between clients. Note that og corresponds to the i.i.d setting, in which datasets from each client have the same distribution.
2021) The bounded local variance represents the randomness of stochastic gradients,
Assumption 3.3 (Bounded Gradient Delay). Let Tf represent the delay for global round and client i which is applied in Algorithm I and 2 Tę implies the difference hetween the current global round t and the global round which client started compute the gradient. We assume that the maximum gradient delay is bounded, i.e., Tmax [ {T() oc.
Assumption 3.3 is common assumption in convergence analysis for asynchronous federated learning method (Koloskova et al. 2022 Yang et al. 2020). Note that Assumption 3.3 naturally means that o0 is bounded.
the average delay Tavg NT
Ee 1-1
Di=1
Theorem 3.4. Under Assumptions 3.1 3.3 denote f. = arg min fax and fi f(x)), let T be the total global rounds and K be the number of local SGD training steps. If the local learning rate 1 ((v((vK)) KM) and 17 0 (1/VTK) then the global rounds of Algorithm satisfy
Σ B[]Vf(())) = -0( -ihh-AA +
+ 0
0² Ko²
VTKM
TK
+0
VK VTM o²)
+ +0 K (TmaxTTarge Tmaax
(3.2)
Remark 3.5. Theorem 3.4 presents the convergence analysis for Algorithm I w.r.t. global commu- nication round T. local steps K and the update accumulation amount M. From Eq. equation 3.2 it can be seen that the maximum delay Tmax and the average delay Tavg term indeed affects the overall convergence of the asynchronous federated learning algorithm. Particularly, the last term involves joint effect term 7maxxavxgo (TT) where the global variance où and the delay terms Tmax and Tang multiplied together. This implies that the convergence degradation brought by the
4

---

Published as a conference paper at ICLR 2024
asynchronous delay is amplified by the high data heterogeneity (large og). If data are i..d. distributed across clients, i.e., Og 0, then O K Tmax Tavg g term vanishes to O. On the other hand, if data are non-i.i.d. distributed, i.e., Jg * O, the term T max maxxTavg 2 will largely slow down the overall convergence (in fact, when T Σ KM, this term would become the dominant term in the convergence rate). This verifies our intuition that the data heterogeneity can worsen the impact of asynchronous delay and jointly deteriorate the convergence, which motivates to develop novel method for reducing such joint effects and improving the convergence for asynchronous federated learning. Compared to the original analysis in FedBuff, our analysis requires fewer assumptions and enjoys slightly tighter bound on the asynchronous delay term
PROPOSED METHOD: CACHE-AIDED ASYNCHRONOUS FL
To address the challenges of data heterogeneity and gradient delay across clients and achieve better convergence in asynchronous federated learning, we propose novel Cache-Aided Asynchronous FL FL) method. The proposed CA enables the server to maintain and reuse the cached updates for global update calibration. Algorithm summarizes Algorithmnuummarzzze our proposed CA In general, the CL largely follows the FedBuff framework in Algorithm [ while the main difference between our proposed CA3FL and Algorithm lies primarily in the global update steps. Specifically, we introduce a cached variable updating shown in Line and 13, and we incorporate a global calibration process in Line 4 and 11.
Algorithm 2 Cached-Aided Asynchronous FL
Input: local step size Tj, global stepsize 1), server concurrency Mc. buffer size M;
Initialize A 0, hi 0 for i [N], h1 0, m 0 and sample set of Mc active clients to run local SGD updates.
2: repeat
3: if' receive client update then
4: Server accumulates calibrated update from client 1: A, f A, (A) h/)
5: Server update clients' cached variables: h A
6: Set m 4- m + 1, S, + Sy U {i}
7: Samples another client j from available clients
8: Broadcast the current model æ to client j. and run local SGD updates on client j
9:
end if
10: if m = MM then
11:
e, h, + SS
A.
Update global model xT-1 = Zt + 170,
13:
Server maintains the cached variable h = h; for & S
14:
Server initialize h441= = Σn h
Set O, A + 0, S + 0. a
16:
end if
17:
until Convergence
Cached variable update. In CA the server maintains the latest cached update for each client, and reuses this cached update as an approximation each client's contribution the current round's update. Denote h; as the latest cached variable for client i and h; as the global cached variable which the average of h; among all clients, i.e., h N ΣN hi. Once the server received A from client i, then the server updates the cached variable for it, i.c., hit1 A (Line 6). For clients which don't contribute to round f, the server keeps the state variable unchanged as h = h (Line 14). This update rule for cached variable enforces the server maintains the latest model update difference for each client for global update calibration.
'Due to space limitations, we leave further discussions about Theorem 3.4 and the comparison with FedBuff' analysis in (Toghani & Uribe 2022) in Appendix B
5

---

Published as a conference paper at ICLR 2024
Global calibration. Once client finish the local training and send A; to the server, the server accumulates A; h; to A Let St represent set of clients in which the server received their update round I. After the server receives M updates, we calculate the server updates e, the summation of the global cached variable h2 with the average global update [s]] (Line 11). The global model
4++1 is then updated by this calibrated variable v,. Note that v, is actually a linear combination in terms of the latest received model update difference Aj and cached variable h i.e.,
h:
+
(A: h.).
(4.1)
Discussion. The design (Eq, 4.1) for the calibration and cached variables felt somewhat similar to SAGA (Defazio et al., 2014), a well-recognized stochastic variance-reduction method that stores previously computed gradients and leverages them for reducing the gradient variance. Eq. 4.1 looks like a special form of SAGA by treating model update difference A as gradients and applied globally over different clients. However, it is important to note that our method does not adhere the properties of unbiased incremental gradients that SAGA mainly relies for its variance reduction purposes, which makes our theoretical analysis non-trie von-trial and different from that of SAGA. Therefore, CA should not be considered as a direct application of SAGA to asynchronous federated learning. Note that FL. does require extra communication and computation overhead clients, and it is compatible with privacy persevering approaches such as differential privacy and secure aggregation.
5 CONVERGENCE ANALYSIS
We first introduce the additional assumption needed for the convergence analysis of our proposed CA FL algorithm.
Assumption 5.1 (Bounded State Delay), Let Ç/ represent the delay of the state variable for global round and client j & St in Algorithm 2 çf is state in the context of client j which does not update the model difference in round and then maintains the state variable hj as the last step. C/ implies the difference between the current global round and the global round at which this client j started to compute the last gradient. We assume that the maximum gradient delay is also bounded, i.e., Smax = max (c/) < co.
Assumption 5. is also commonly used in convergence analysis for memory-aided federated learning method (Gu et al. 2021 Yang et al.] 2022). In nutshell, the state delay describes how many global rounds has it been since the last local training for a client. In the following, will show the convergence results for our proposed CA2FI.
Theorem 5.2. Under Assumptions 3.1 3.3 and Assumption 5.1 if the local learning rate n @(VKM) and m ((L/VTK) then the global rounds of Algorithm satisfy
Σ [[ = 0 f1 f-
+ +0
VTKM +
o²
0
Ko²
+ 0
(Fiax + Smax) )²²
VTKM
TK
T
(5.1)
where f. = arg min x (ax).
Remark 5.3. Theorem 5. suggests that with a sufficient amount of global rounds T, i.e., T > KM, our proposed CA. method achieves a desired convergence rate of O ((TTRM w.r.t. global round T. local steps K and the update accumulation amount M, which matches the convergence rate in traditional synchronous federated learning baselines (Yang et al. 2021 Reddi et al. 2021 Jhunjhunwala et al. 2022).
Remark 5.4. Compared with Eq. 3.2 the joint effect term O(K Tiax o (T) no longer exists, while in Eq. 5.1 the asynchronous delay Tmax only relates to the stochastic noise a. This suggests that our proposed C can benefit from the design of reusing the cached update for global update calibration, which tackles the data heterogeneity issue across clients and reduces the joint impact caused by the asynchronous delay and data heterogeneity. Note that our design also contributes the general data hetcrogeneity issuc in that the O O those two improvements finally lead to better convergence rate for our proposed CA algorithm.
"MMM a term in Eq. 3.2 also gets smaller. Together,

---

Published as a conference paper at ICLR 2024
6 EXPERIMENTAL RESULTS
Datasets, models, and methods. We present the experimental results on both vision and language tasks to verify the effectiveness of the proposed method. For the vision tasks, we train the CIFAR-10 dataset with CNN (Wang & Ji. 2022) and ResNet-18 (He et al. 2016) models, and we also train CIFAR-I00 (Krizhevsky al. 2009) datasets with ResNet- 18 model, and we provide various data sampling levels and client concurrency settings. For the language tasks, we conduct experiments on fine-tuning a pretrained Bert-base model (Devlin et al. 2018) on several datasets in GLUE benchmark (Wang et 2018). We evaluate experiments on non-i.i.d. data distributions by a Dirichlet distribution partitioned strategy similar to (Wang et al., 2020a b) with several parameters for both vision and language tasks. We adopt the same CNN network in and ResNet-18 network (He et al. 2016). We compare our proposed CA with the asynchronous FL baseline, FedBuff (without differential privacy) (Nguyen et al. 2022) and FedAsync Xie et al. (2019) (constant), and with the synchronized FL. method, FedAvg McMahan et al. (017). Due the space limit, we leave additional experiments on more datasets and models together with the experiment details in Appendix A
Implementation overview of vision tasks, For experiments on CIFAR-10 10 and CIFAR-100 the number of local training iterations K on each client is set two local epochs (the amount of iteration depends on the amount of data for each client, and the batch size is set to 50 for all experiments by default). For local update, we use the SGD optimizer with a learning rate gridding from (0.001, 0.01, 0.1, 1) with momentum 0.9 and weight decay of 1e-4, and the global learning rate is gridding from f0.1, 1.0, 2.0} for all methods. We set total of 100 clients in the network and the concurrency Mr = 20 if there is no further instructions, and we set the update accumulation amount M = 10 by default.
Implementation overview of language tasks. For experiments on fine-tuning Bert-base model on the MRPC, SST-2, RTE and CoLA datasets from the GLUE benchmark, the number of local iterations K on each client is one local epoch (the amount of iteration depends on the amount of data for each client, and the batch size is set to for all experiments by default). We employ Dir (0.6) for non-i.i.d. data partitioned among clients. We adopt the low-rank adaptation (LoRA) (Hu et al.) fine-tuning method. Specifically, for a pre-trained weight matrix
2021) as the parameter-effice Wo E R LoRA freezes Wo but tuned the ÁW by representing with a low-rank decomposition with rank r < min(d, k)). Wo + AW = Wo + BA, where B Øaxr and A grxk are two trainable parameters. For all experiments, we choose r = 1 and 0r 1. For local update, we use the widely-used Adam W optimizer with a learning rate gridding from i 55--5, 1e-4, 5e-4, 1e-3 3) with weight decay of 1e-4, and the global learning rate gridding from (0.1, 1) for all methods. We set total of 10 clients in the network and the concurrency M, = if there further instructions, and we set the update accumulation amount M 3 by default.
6.1
MAIN RESULTS
Table T shows the overall performance of training CIFAR-10 with CNN model and the ResNet-18 model. We observe that the proposed CA shows improvement upon the FedBuff and FedAsync. Particularly, when training with the lightweight CNN model (with about 2.2M trainable parameters), the training loss of FedAsyne is severely fluctuating and cannot converge when a 0.1, while our proposed CF are more robust to the highly heterogeneous settings and achieve better result than FedBuff.
Table Prelseetsststsss the overall test accuracy of experiments CIFAR-100 with two data heterogeneity levels. For = 0.1, our proposed FL achieves higher test accuracy compared to FedBuff but has lower accuracy than FedAsyne. Specifically, when the data is highly heterogeneously distributed, e.g. a 0.01, our CA method significantly outperforms than FedBuff and FedAsyne.
For fine-tuning the Bert-base model on the GLUE benchmark, Table presents the evaluation results for four datasets with several tasks. Note that the MRPC, SST-2, and RTE datasets are evaluated
'e also provide experimental results on fine-tuning TinylmageNet with two ResNet models, and parameter- efficient fine-tuning GPT-2 small model on E2F. NL. Challenge.
7

---

Published as a conference paper at ICLR 2024
Table I: The test accuracy of different models on the CIFAR-10 dataset with different models and data heterogeneity degrees. We report the mean accuracy and the standard derivation for the last 5 rounds.
Din(O.3)
Dir(O.1)
Method
CNN
Re Acc. & std
CNN
ResNet-18 Acc. & std
Acc. & std
Acc. & std
FedAsyne
62.29 + 0.16
79.8 + 2.28
40.58 + 2.92
FedBuff
60.74 + 1.18
78.53 + 3.31
53.96 + 0.10
63.03 + 3.17
CA
64.40 + 0.32
83.79 + 0.34
57.62 + 0.42
68.37 + 1.97
by the validation accuracy, while the CoLA dataset is evaluated by Matthew's 's correlation. We observe that FedAsync achieves higher validation accuracy in MRPC, for other tasks and datasets, our proposed CA2FL obtains better evaluation results. Moreover, we plot the training loss w.r.t. the global rounds in Figure | and it verifies the theoretical convergence improvements of our proposed CA?FL..
CAR
Tratring Loss
12
Talning
(a) CIFAR-10 Dir(O.1)
(b) CIFAR-10 Dir(O.3)
(c) MRPC
(d) SST-2
Figure 1: Training/fine-tunnn loss several models and datasets.
Table 3: The result of Bert-base model on several language datasets with data heterogeneity degrees Dir(0.6). We report the mean evaluation metrics and the standard derivation for the last 5 rounds.
MRPC
SST-2
RTE
CoLA
Method
Acc. & std.
Acc. & std.
Acc. & std.
Acc. & std.
FedAsyne
82.86 + 0.42
87.32 + 3.76
62.09 + 0.76
54.53 1.52
FedBuff
78.68 = 0.41
86.06 = 3.86
60.07 = 1.09
55.57 + 0.94
CA
79.26 + 0.12
90.76 + 1.02
65.63 = 0.35
56.10 + 0.25
We also conduct detailed comparison for studying the overall training/fine-tunn speedup for our proposed method to investi- gate the efficiency of our proposed method in Table 4 We simulate the wall-clock delay by assuming 80% of clients have normal local training processes, 10% have mild delays, and the last 10% have severe delays. Specifically, we observe that for each task, client would finish the local training in train seconds, then the simulated local training time for the normal clients would be t X kuann where I; ~Uniform(0.5 1) x berann for the mild delay clients, there is &; X brain where I, ~ Uniform(1, 2) x Ximin for severe delay clients, there is 4, ~ UUniform(2, 3). We've provided an ablation study about different simulation settings in the Appendix. From Table 4 we observe
Table 2: The test accuracy of different models on the CIFAR-100 dataset with different data heterogeneity degrees. We report the mean accuracy and the standard derivation for the last 5 rounds.
Dir(O.1) Acc. & std
Dir(0.01) Acc. & std
Method
FedAsync FedBuff CA
62.91 1.67
57.12 0.60
32.49 1.31
59.50 + 0.24
37.30 + 0.26
8

---

Published as a conference paper at ICLR 2024
that proposed CA FL maintains better training/fine-tuin efficiency among all asynchronous methods. CA also shows the advantage of asynchronous learning in image classification tasks. However, the efficiency of CI is still challenged compared to synchronized FL. in the case of fine-tuning pre-trane pre-trained models. We would like to take this phenomenon conclusion of future work for further research.
Table 4: Training/fin--tningg time simulation (in units of 10 seconds) to reach target validation accuracy (Matthew's correlation for CoLA). For each dataset, the concurrency is fixed for fair comparison. Bold represents the best evaluation results and the underline represents the best results for asynchronous FL.
Acc.
FedAsyne
FedBuff
CA
FedAvg
CIFAR-10 10
80%
268.80
291.53
214.16
388.64
CIFAR-100 100
55%
333.47
295.49
233.49
476.78
MRPC
80%
2549.54
403.95
87.39
97.71
SST-2
90%
2853.5
2079.35
648.71
572.01
RTE
63%
815.94
420.83
79.61
95.17
CoLA
55%
217.23
144.64
34.75
0.79
Tee Accumty
Teust Accurcyy
2 E
Test
(a) Non-i.id. for FedBuff (b) Non-i.i. for CA
(c) M, for CA3FL
(d) Buffer M for CA
Figure 2: Test accuracy of ablation studies for FedBuff and CA2 in training CIFAR-10 on ResNet- 18 model.
We conduct ablation studies to investigate the effect of the effect of data heterogeneity, the delay simulation strategies, and the relationship between the concurrency and the buffer size M. Due to constraints space, leave detailed ablation results and discussions in Appendix From Figure 3 plots (a) and (b), we can observe the impact of data heterogeneity for FedBuff and CA They show that the CA is overall less sensitive to data heterogeneity than FedBuff with less fluctuation. Plot (c) shows the the ablation study for the concurrency M. for fixed buffer M 10, it shows that the accuracy decreases the coneurrency increases, with the same buffer M 10. Plot (d) shows the impact of the buffer M with fixed concurrency Mc 20. We observe that as the increase of buffer size M, the overall performance increases w.r.t. the global round T'.
CONCLUSIONS
In this paper, we first investigate the convergence of FedBuff under non-convex heterogeneous data distribution settings and we show that the data heterogeneity amplifies the negative impact of asynchronous delay which slows down the convergence of asynchronous federated learning. To address this convergence degradation issue, we propose novel asynchronous federated learning method, CA which involves caching and reusing previous updates for global calibration. We provide theoretical analysis under non-convex stochastic settings that demonstrate the significant convergence improvement of our proposed CA Empirical results demonstrate the superior performance of the proposed CA"FL compared to general asynchronous federated learning, and it also shows that the proposed 2F could largely save the memory overhead while maintaining the superior performance benefits from the cached update.

---

Published as a conference paper at ICLR 2024
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. International Conference on Learning Representations, 2021. htthtts:: BRLLbttts///ppeeerriiie /opp//eeep///eeeeeeeeeeeeeeeeeee neteeewwweeeeeeeeeeeee..ee net/ wwwpiiermmee//oomm
(d=B/v4QMR629)
Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communication patterns, In Proceedings of the 38th International Conference on Machine Learning, pp. 425-435, 2021.
Marco Bornstein, Tahseen Rabbani, Evan Z Wang, Amrit Bedi, and Furong Huang. SWIFT: Rapid
decentralized federated learning via wait-free model communication. The Eleventh International Conference Learning Representations, 2023. URL
id- [d-jhhnCir1RRd
Ashok Cutkosky and Francesco Orabona. Momentum based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
Jacob Devlin, Ming- Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint trXiv:1810.04800 2018.
Liang Gao, Huazhu Fu, Li Li, Yingwen Chen, Ming Xu, and Cheng-Zhong Xu. Fedde: Federated learning with non-iid data via local drift decoupling and correction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 101 10112-10, 2022.
Margalit R Glasgow and Mary Wootters. Asynchronous distributed optimization with stochastic delays, In International Conference on Artificial Intelligence and Statistics, pp. 9247-9279. PMLR, 2022.
Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of arbitrary device unavailability. Advances in Neural Information Processing Systems, 34:12052-12064 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685 2021.
Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi. Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence, pp. 906 916. PMLR, 2022.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mchryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008. 200,00008.03066, 2020a.
Sai Pranceth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143. PMLR, 2020b.
Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshney. Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning. Advances in Neural Information Processing Systems, 34:6050-6061 2021.
10

---

Published as a conference paper at ICLR 2024
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. net
URL
forum id-4 nwt.:orunee//trteeeeeee 4
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:/610.05492. 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009,
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Remi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. Improved asynchronous parallel optimization analysis for stochastic incremental methods. Journal of Machine Learning Research, 19(81):1-68, 2018.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint 197.02190, 2019a.
Xiang Li, Wenhao Yang. Shusen Wang, and Zhihua Zhang. Communication--fficicen local decentral- ized sgd methods. arXiv preprint arXiv: 2019b.
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal on Optimization, ((44):2022-222)) 2017.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efiee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282 PMLR, 2017.
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous sgd beats minibatch sgd under arbitrary delays. Advances in Neural Information Processing Systems, 35:420-433, 2022.
John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statistics, pp. 3581-3607 PMLR, 2022.
Lam Nguyen, PHUONG HA NGUYEN, Marten van Dijk, Peter Richtarik, Katya Scheinberg, and Martin Takac. SGD and hogwild! Convergence without the bounded gradients assumption. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3750-3758 URL https: https://procedding mlr. www.ppprssssseeeeee htt.://eeeiia.......eeeeee////en presss/v00/nguyenleee
PMLR, 10-15 Jul 2018.
html
Feng Niu, Benjamin Recht, Christopher Re, and Stephen J. Wright. Hogwild! lock-free approach to parallelizing stochastic gradient descent. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS' 11, pp. 693-701, Red Hook, NY, USA, 2011. Curran Associates Inc. ISBN 9781618395993.
Jekaterina Novikova, Ondřej Dušek, and Verena Rieser. The e2e dataset: New challenges for end-to-end generation. arXiv preprint arXiv: /ttp//766...2... 2017.

---

Published as a conference paper at ICLR 2024
Kunjal Panchal, Sunav Choudhary, Subrata Mitra, Koyel Mukherjee, Somdeb Sarkhel, Saayan Mitra, and Hui Guan. Flash: Concept drift adaptation in federated learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardd, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 26931-26962. PMLR, 23-29 Jul 2023.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
Sebastian Stich, Amirkeivan Mohtashami, and Martin Jaggi. Critical parameters for scalable dis- tributed learning with large batches and asynchronous updates. In International Conference on Artificial Intelligence and Statistics, pp. 4042-4050. PMLR, 2021.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.0976; 2018.
Dimitris Stripelis, Paul M Thompson, and José Luis Ambite. Semi-synchronous federated learning for energy-efficient training and accelerated convergence in cross-silo settings. ACM Transactions on Intelligent Systems and Technology (TIST), 13(5):1-29, 2022.
Mohammad Taha Toghani and César A Uribe. Unbounded gradients in federated learning with buffered asynchronous aggregation. In 2022 58th Annual Allerton Conference Communication, Control, and Computing (Allerton), pp. 1-8. IEEE, 2022.
Qianqian Tong, Guannan Liang, and Jinbo Bi. Effective federated adaptive gradient methods with non-iid decentralized data. arXiv preprint arXiv:2009.06557 2020.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint 1rXiv:/804.072 2018.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Fed- erated learning with matched averaging. In International Conference on Learning Representations, 2020a. URL httphtttt////peeeeeeeeee
net. fort//oru??
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. arXiv preprint arXiv:2007 074481, 2020b.
Shiqiang Wang and Mingyue A unified analysis of federated learning with arbitrary client participation. In Advances in Neural Information Processing Systems, volume 35, pp. 19124- 19137, 2022.
Yujia Wang, Lu Lin, and Jinghui Chen. Communication-effiee adaptive federated learning. In Proceedings of the 39th International Conference Machine Learning, pp. 22802-2288 22838. PMLR, 2022.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint N5ti::1903.0399 2019.
Yikai Yan, Chaoyue Niu, Yucheng Ding, Zhenzhe Zheng, Fan Wu, Guihai Chen, Shaojie Tang, and Zhihua Wu. Distributed non-convex optimization with sublinear speedup under intermittent client availability. arXiv preprint arXiv:2002.07399) 2020.
12

---

Published as a conference paper at ICLR 2024
Haibo Yang. Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-lID federated learning. In International Conference on Learning Representations, 2021.
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International Conference on Machine Learning, pp. 25331-25322 PMLR, 2022.
Zhaohui Yang. Mingzhe Chen, Walid Saad, Choong Seon Hong, and Mohammad Baake-Bahaei.... Energy efficient federated learning over wireless communication networks. IEEE Transactions on Wireless Communications, 20(3):995-11499 2020.
13

---

Published as a conference paper at ICLR 2024
A ADDITIONAL EXPERIMENTS
In this section, we present additional empirical results for our proposed methods in training CNN network as Wang & Ji (2022) on CIFAR-10, and ResNet- network He et al. (2016) on CIFAR- 10/100 Krizhevsky al. (2009) datasets, and fine-tuning Bert-base Devlin et al. (2018) model on
GLUE datase Wang et al. (2018). Ablations and discussions about our proposed methods are also provided. All experiments in this paper are conducted on 4 NVIDIA RTX A6000 GPUs.
A.1 MEMORY FRIENDLY CACHED-AIDEE ASYNCHRONOUS FI.
While CA successfully tackles the data heterogeneity issue in Asynchronous FI., it involves extra memory costs for maintaining the cached variable for each client the server. However, this memory overhead can pose challenges when applying CA FL in practice, especially for large models with massive trainable parameters. To overcome this memory overhead, we extend the proposed CA to a memory-friendly adaption method (MF-CA2FL) The main difference between C and MF-CA'FL lies in whether the server maintains full-size quantized latest update. Specifically, in MF- after the client i obtains the model differences A and sends it to the server, the server quantizes A : to Q(4 (-rr) via unbiased quantization approaches such as 8-bit or 4-bit quantization and keeps 2(4 (--r)) memory. The server updates the global calibration variable en same as FL. Note that for each global round the server updates the quantized ((4) (-rr as the cached update, i.c., h1+1 ((4; Vi S₁, that being said, the cached variable h1+1 for each client represents the latest quantized model update difference. Therefore, compared to CA FL, this friendly adaption effectively reduces the memory overhead.
A.2 ADDITIONAL EXPERIMENTAL RESULTS
Results on CIFAR-10. Table 5) shows the overall test accuracy of experiments on CIFAR- 10 on training different models with two data heterogeneity levels. demonstrates that our proposed CA achieve better test accuracy than asynchronous federated learning baselines. Particularly, when the data is highly heterogeneously distributed across clients, indicated by smaller a values in Dirichlet sampling strategies, our CA method significantly outperforms the other asynchronous baseline. Particularly, when 0.1, CA can significantly outperform FedBuff with more than 5% increase on training ResNet-18. Moreover, in the memory-friendly version MF-CA3FL, which reduces the memory overhead by keeping the quantized cached update, the superior performance of the cached variable is still observed and leading better test accuracy than asynchronous baseline. Furthermore, Figure 3 provides the test accuracy curves of training CNN and ResNet- 18 networks on CIFAR-10 with a 0.3, offering a visual illustration of the effectiveness of our proposed method.
Table 5: The test accuracy of different models on the CIFAR- 10 dataset with different models and data heterogeneity degrees. We report the mean accuracy and the standard derivationfor the last rounds.
Dir(O.3)
Dir(0.1)
Method
CNN
ResNet-18 Acc. & std
CNN
ResNet-18 Acc. & std
Acc. & std
Acc. & std
FedAsyne
62.29 0.16
79.8 = 2.28
40.58 + 2.92
FedBuff
60.74 1.18
78.53 = 3.31
53.96 + 0.10
63.03 + 3.17
CL
64.40 0.32
83.79 = 0.34
57.62 = 0.42
68.37 + 1.97
MF-CA (8 bits)
62.43 + 0.04
83.07 = 0.43
57.00 + 0.40
71.85 + 1.57
MF-CA2FL (4 bits)
62.41 + 0.19
82.72 - 0.39
56.20 + 0.54
70.98 +\t 1.82
Results on CIFAR-100. Table presents the overall test accuracy of experiments on CIFAR-100
with two data heterogeneity levels. It demonstrates that our proposed CA achieve higher test accuracy compared to the asynchronous federated learning baselines. Specifically, when the data is
14

---

Published as a conference paper at ICLR 2024
Frdhegne Pedbut
0.0
Test Accuracy
MI-CAPL 26 brso
NT-CATPL: 24
0.4
0.3
HP CATL 05-445)
6.
100
200
2003
4:0
500
100
200
2017
400
500
(a) Dir (0.1)
(b) Dir (0.3)
Figure 3: The test accuracy for our proposed CA and MF-CA'FL (4 bits) with asynchronous federated learning baselines training CIFARIO data on ResNet- 18 model.
highly heterogeneously distributed, e.g., 0.01, CA method significantly outperforms asynchronous baselines with more than 4.5% improvement compared to Asynchronous FL. The memory-friendly version MF-CA also shows its advantage over asynchronous federated learning baselines when severely data heterogeneity settings.
Table The test accuracy different models on the CIFAR-100 110 dataset with different data hetero- geneity degrees. We report the mean accuracy and the standard derivation for the last rounds.
Dir(O.1) Acc. std
Dir(0.01)
Method
Acc. & std
FedAsync
62.91 + 1.67
FedBuff
57.12 + 0.60
32.49 + 1.31
CA
59.50 + 0.24
37.30 + 0.26
MF-CA (8 bits)
59.12 + 0.21
37.34 + 0.43
MF-CA2FL (4 bits)
59.50 + 0.35
37.29 = 0.36
Results on Tiny Imagenet. Table 7 shows the overall test accuracy of experiments on Tiny Imagenet- 200 (Le & Yang. 2013) Krizhevsky et al. (0012) on fine-tuning a pre-trained ResNet-18 (He et al.] 2016) and ResNet-34 (He et al. (0066) models under non-i.i.d. data distribution settings. Similar to previous image classificattin tasks, there are 100 clients in total, and we set the concurrency M, 20 and update buffer M = 10, and we set highly heterogeneous data distribution with Dir (0.01). Table 7 demonstrates that our proposed CA 2L achieves better test accuracy than asynchronous federated learning baselines.
Table 7: The test accuracy of two models the Tiny Imagenet dataset. We report the mean accuracy and the standard derivation for the last rounds.
ResNet-18 Acc. & std
ResNet-34 Acc. & std
Method
FedAsync
50.74 + 1.08
54.13 + 1.12
FedBuff
55.55 + 0.37
61.85 + 0.38
CA
56.17 + 0.23
62.51 + 0.20
Results on E2E NLG Challenge. Table shows the validation loss of experiments on E2E NLG Challenge (Novikova et al.) 2017) on parameter--efficient fine-tuning pre-trained GPT-2 small (Radford et al. 2019) model under non-i.i.d. data distribution settings. We set 10 clients in total, with concurrency M. = 5 and update buffer M 2. Since there are no labels for the generation tasks, naturally sample heterogeneous data distribution among clients. Similar the previous
15

---

Published as a conference paper at ICLR 2024
18
5eting
2
0.0
Training LDSS
1.2
Setting
Sc00ing 2
0.5
6.3
Setting
320
200
420
550
250
203
52o
#foundds
Figure 4: Ablation for several settings for wall-clock delay simulation.
language classification tasks, we adopt LoRA fine-tuning with OLARA = 1 and = 1. Table g demonstrates that our proposed CA2FL. achieves lower validation loss than asynchronous federated learning baselines. This further shows the effectiveness of our proposed method on various tasks.
Table 8: The validation loss of fine-tuning GPT-2 small model on E2E NLG Challenge. We report the mean loss value and the standard derivation for the last 5 rounds.
Method
Loss & std.
FedAsyne
0.1533 + 0.0438
FedBuff
0.1241 + 0.0110
CA'FL
0.1025 = 0.0004
A.2.1 ADDITIONI RESULTS
Table 9: Several settings for wall-clock delay simulation.
Setting
80% from (0.5,, 1). 10% from U (11, 2). 10% from (2,
Setting 2
80% from (0.5,, 1), 10% from (11,3). 10% from ((3, 5)
Setting
80% from (0.,5, 1). 10% from (11, 5). 10% from (5,,, 10)
Setting 4
80% from (0.5,, 1), 20% from U(5, 10)
Setting 5
60% from (0.5, 1), 40% from U5, 10)
Simulated delay distributions. We simulate the delay distributions on various settings summarized in Table 9 From Figure 4 it shows that changing the setting of delay sampling would not make significant effect on both convergence and generalization.
Performance under concept shift. In real-world applications, the non-stationary data sources (model drift) can result in some long-term challenges. Although this not the main focus of this paper, we conduct an experiment examine whether our proposed method maintains its advantage under time-varying distribution shifts. We utilize similar setting of sudden drift as in Flash (Panchal et al.) 2023): all the clients suffer from the distribution change abruptly at the same round (the concept drift occurs at the 200th and 400th rounds). The concept shift is conducted as follows: for task with n labels, we swap the i-th label with + 1-th label, i [0, 1, .... 1]. and we swap the n-th label with label O. The following results, demonstrate that our proposed CA FF still achieves better performance compared to other asynchronous FL baselines when there exist distribution shifts. Since this is not our main focus in this paper, we did not have any specific design for the model drift issues but it is interesting direction and will leave it our future work.
16

---

Published as a conference paper at ICLR 2024
Table 10: The test accuracy training ResNet-18 model CIFAR-10 dataset. We report the mean accuracy and the standard derivation for the last 5 rounds.
Method
Acc. std.
FedAsync
78.49 + 3.24
FedBuff
74.17 4.61
CA
79.91 + 1.00
A.3 SYPER-PARAMETER DETAILS
Image classifications. We conduct detailed prper--arammter searches to find the best hyper-papaeee parameter for each baseline. We grid over the local learning rater n E {0.001, 0.01, 0.1, 1.0), and the global learning rate 7) E {0.1, 1.0, 2.0} for each methods. Table I] summarizes the hyper-parameter details in our experiments. Experiments are set up with 100 total clients, the concurrency is M. 20 by default, and we let the server update the global model once receives M = 10 updates from clients. For each method, we conduct 2 local epochs (the explicit local iterations K may differ from clients) of local training with batch size of 50 by default. We set the weight decay 10-1 for the local SGD optimizer. For FedAsync Xie et al. (2019), we additionally grid over the weight of the regularization term p E {0.01, 0.1, 1.0), the momentum factor a2 E (.31, 0.5, 0.9}.
Languages tasks. We conduct detailed hyper- parameter searches to find the best Mayper-paameeet for each baseline. We grid over the local learning rater Nn {5 10 10 10--0,,, 10 10 100--, and the global learning rate 7) E {0.1, 1.0, 2.0} for each methods. Table I1 summarizes the hyper-parameter details in our experiments. Experiments are set up with total clients, concurrency is M, = by default, and let the server update the global model once it receives M 3 updates from clients. For each method, we conduct 1 local epochs (the explicit local iterations K may differ from clients) of local training with batch size of 32 by default. We set 31 = 0.9, Bg = 0.999. c 10-6 and weight decay as 10-4 for the local AdamW optimizer. For FedAsyne Xie al. (019)) additionally grid over the weight of the regularization term p E {0.01, 0.1, 1.0]. the momentum factor a E (0.1, 0.3, 0.9)..9).
Table 11: Hyper- sapee-pprameterss details.
CIFAR-10
FedAsyne
FedBuff
CA
MF-CAAFL (8 bits)
MF-CA FL (4 bits)
Models & Dir(o)
"
CNN & Dir(O.3)
0.001
1.0
0.01
1.0
0.01
1.0
0.01
1.0
0.01
1.0
ResNet-18 & Dir(0.3)
0.01
1.0
0.01
1.0
0.01
1.0
0.01
1.0
0.01
1.0
CNN & Dir(O.1)
0.01
1.0
0.01
1.0
0.01
1.0
0.01
1.0
ResNet-18 18 & Dir(O.1)
0.001
1.0
0.01
1.0
0.01
1.0
0.01
1.0
0.01
1.0
CIFAR-100
FedAsyne
FedBuff
CA²FL
MF-CA T (8 bits)
MF-CA F (4 bits)
Models & Dir(a))
7
1p:
?]
7/
17
ResNet-18 & Dir(0.1)
0.001
1.0
0.01
1.0
0.01
1.0
0.01
1.0
0.01
1.0
ResNet-18 & Dir(0.01)
0.01
1.0
0.01
1.0
0.01
1.0
0.01
1.0
B FURTHER DISCUSSION ABOUT THEOREM 3.4
Discussions. Compare to the original proof in FedBuff (gguyen et al. 2022). our analysis for Theorem eliminans the unrealistic bounded gradient assumption of | AT- < G. Furthermore, obtains a tighter dependency of gradient delay TÝ. While FedBuff's original analysis has - dependency, and obtain Tmax Tang dependency. Compared to FedAsyne (ie et al. 2019).
17

---

Published as a conference paper at ICLR 2024
Table 12: Hyper-parameters details.
GLUE
FedAsyne
FedBuff
CA2FL
Models & Dir(a)
7
?
MRPC
5 10
1.0
5 x 10-4
1.0
x 10
1.0
SST-2
x 10 4
1.0
5 10
1.0
10
RTE
x 10
1.0
5 10
1.0
6 10
1.0
CoLA
x 10
1.0
5 10
1.0
5 10
Theorem 3.4 eliminates the assumption for weak convexity, providing a more common nonconvex analysis for the asynchronous FL method.
It's worth noting that (Koloskova et al. 2022) relaxes the delay dependency in the convergence rate for distributed asynchronous SGD to /Timx In our study, we focus on the FL scenario where each client performs multiple local update steps prior global aggregation. Particularly, by setting VM
we can achieve the same delay dependency in convergence rate of /TmaxTavg in (Koloskova et al. 2022). Additionally, while (Mishchenko et al., 2022) explores the arbitrary delay in asynchronous SGD, our approach yields an improved convergence rate heterogeneous scenarios compared to their results under similar assumptions.
K = and selecting a delay- dependde learning rate of O
Comparisons with Toghani & Uribe (2022).
Our original FedBuff analysis in Theorem 3.4 obtains
a convergence rate (flf-fsl+o") VTKM
o²*Ko²
<Ro²
Kima Tago o +
+
+ O
TK
VTM
If we only consider the T and t related terms, we obtain a similar convergence rate of
+ O Timax Tax compared O ((+)) + 00 Tmax
Toghani & Uribe (2022).
If we consider the convergence rate w.r.t. T, K, M and related terms, when M > K,
obtain similar convergence of O /7 0 Krmaxfar
compared O
/T
Kr2
in Toghani & Uribe 2022).
Moreover, the convergence rate highly related the learning rate choosing. For example, when adopting different learning rate as in Theorem 3.4, our convergence rate can match the result in [1] w.r.t T, K, .M and without any further constraints: following Equation (C.15) in Appendix, choosing 77 = O(1) and Tn of
((TRR) then we get DT f(IlVf(z
O (fo (fo-f=))
O ( VTKM + +0
+0
Timaxe Tang
+ O T
O +KKo If we look at the T and delay TK
VTM
Ths
related terms, our rate would be O +
Traae Toug
and this is slighlty better on the non-dominant
TM
O
Tiaax Tazy TM
term than the rate in Toghani & Uribe
2022
C CONVERGENCE ANALYSIS FOR ASYNCHRONOUS FL
Proof of Theorem 3.4 Since f is L-smooth, taking conditional expectation at time t, we have
E [[f( f(xr))
[B([[(()) m.t1 + L EEl Fl 2cel
2 Elll A 1.1
EVV{(x))) ma)l +
(C.1)
18

---

Published as a conference paper at ICLR 2024
Bounding I
[ 77 nA
E
Vf(z)))
E
A Aim
= M
iEML
K-1
177 B "M
E
iEM: h=0
K-1
VF (F(aaLrtN)) }
E
((xx)) Σ
M
ieMM, K=
= (T/(O)))
N K-1
VF((o)_-)))) ))
VF
(C.2)
N
where the second and third equation holds by the update rule. The fifth one holds by the unbiasedness of stochastic gradient. By the fact of (a. b) = ||lall + ||b11 - l|a b|| we have
Fi )
B (Zxx),
K=
k
K
MIl E
N
12
E
V
V (a)
2K
N
K
1
+
E
VVV((a)
2
NVK
1=1
k=
N
E [((
Wi
E
2
2K
N
1 N
+
m
(a:)))
(
(C.3)
2
K=
for the last term, we have
K-1
N
7
1 Σ
V
- N
2
k=0
K-
N
T/
B[IVF.((
2
N
N
7
N
K-1
N
m
Σ
- x,,r;1111 L L'EE||I,-r =2/
(C.4)
N
For the second term, we have
1 <
E -
xx Fe-ry
1
Σ
m1 7f.m
m=0
O0² 2 + 6Koy) + 30K 2 V Vf (ax
(C.5)
19

---

Published as a conference paper at ICLR 2024
For the first term, we have
(0++1 - xz) 27
E| x
x -1 12]
E
K-1
E
ng -5.
M
JeM, 0=
(F 8-12 ) + Voy( [اااا|
E
nlg -
s= =
JEM, 0=
- 1
VF (3 2 1 + + "
Σ
ΣΣ
K-1
M
n nl 1
M
m
V
(a)
JEM, k=0
-
JEM, k=0
ATmaaKi nz
0²
+
mT m
Σ E
k
VF (a= 1
(C.6)
M
M
JEM, k=0
For simplicity, we assume that the clients' participation distributions are simulated as independently uniform distribution, then for the last term, we have
K- 1
( 11
Σ
JEM, k=
M(N - M)
N
K-1
17
M(M -1) 1)BB
N K-1
vF (a = 1/1
Σ E
VF
N(N - 1) B
N(N - 1)
/=1
j=1
M(N - MM
N
15NK3 11 (0² + 6Kog) + 10 +3K2)
Σ [
[[T )19 +3NK 03
N(N - 1)
M(M- -
N K
N K-1
N(N - 1) E
Pa
+
VF (2c (+t)
K=0
K=
M(N - MM)
15N (02 + (Koz) + (90K 1,2 n +3K2)
Σ
RE / 5 (xc )11 3N
N(N - 1)
1=1
2M(M 1)
N(N 1) E.
V -
ΣΣ
N K-1
17
2M - 1)K? N
Σ
E|ll V | (a,_,,)))
N
M(N - M)
N Σ
15NK + 6Koz) + (90K
1p + +3K2)
| (1 + 3N
N(N - 1)
2M (M - 1)KL2
N K-
2M (M
1)K2 N
B B1ll -- - - - 12
Σ
E B|| ( (0,_,))
N-1
N
k=0
j=1
3N - MM) +
M 1
3K3L L2 (02
(02 + +300 + xK2
1
Bl| V f( (z (<=,,,,)) )13)
N= 1
N 1
N
3M - M)
K222
(C.7)
N 1
20

---

Published as a conference paper at ICLR 2024
where the first inequality is inspire from Lemma E.1 Then
Bl| Tz-77 12] x
max Kn
ni
0² +
2 max n'
m
Σ
3M - M
2NM(M
M
M
-
N
e=
3M - M)
5K3T + [KKo)) + (30K +
K202
N- 1
(C.8)
Thus we have
M 2
Σ
(..)
Σ
V
Fi 1
N
1-
K=
1=1
mmk? (0² + +(Koz)
+ +3KR21² "
B (20 + =)191] + 2nm KT²
Tmax Kipni 0²
M
+ 2 2 Tmaxiipn? N
1-1
3M M) + 2NM(M 1)
Σ
M
N
-
s
3M(N M)
5K3 + 6Koz) + (30K* 4 LiT + V Ball
N - K202
+ 2177 K L Timaxe Krj np
< <mKL? (02 + +KKog) + 30K22 mp
EI (xe M|P]
M
2mmKL2 Tm
N
3M(N M) 2NM
M
N N
N
s=t-
((00))6K3))) + +3 + +
(f (< )1A1 }
+ 6nl 12 L
M(N - 1) N Σ T/00 g"
N - M
Timax
(C.9)
Thus for 7, we have
mnK
m
K-1
V Fi(a wnd 11']
15 2
E
2K
Tmaax KTppuR o²
+ mm L??
3Kni(0² + [KKog) + +3KK2 2/ N
Σ
E||l V / x -;) =1/1
+ 21 Ki L2
M
==1
+ 22ypKK KI2
? op
Σ
1-1
3M(N - M) 2N
+
(M 11]
2
N
N-1
N-
N- - M 1
5K + 6Koz) + (30K
+ +
6612" K Tiaxx
M(N 1) N Σ T.0
(C.
21

---

Published as a conference paper at ICLR 2024
Bounding II
L 2
L20L E
11
M E
iEMi
K
-M)
$ 17 L
0² +
(N 1) 15NK L2 (0² + 6Ko + 190NK*L2'' + +3K2)
M
N
N K-1
B f(z f(E +
+ NM - 1] E
Σ
VF
k=
(C.11)
where the inequality holds by Lemma E.1 For simplicity, in the following, we define V E V
Merging pieces. Therefore, by merging pieces together, we have
[[f(z++1]] - f(zz) = II
N
K
K
E [
mi 2K
E
F
2
N
Tmax Fmax-Kr2 Kr²'n 0²
+ tm
5K (0² + +6Kog) + +00K2 m
Bill V f [
+ 21p K L
N
M
Tmaxo??
up
N
3M M)
2NM (M - 1)
+ 22mKLL'
M N
N-1
N
N M 1 N
T + +KKo)) (30K + +
+ 61j" K 2 max
Σ T/0O
M(N 1) N
i=1
vi M) NM 11)
N
+ 1 TT
0²
(ONK) + (90NKK* +3K3)
B|| [
M
+3 +3NK?0?
TM - 1) NM(N -1) E
N K-1
V ( 17}
K=0
k K
E
+ mI.
5km (0²
+ +Koo)) + +30X2
n
2 1
Σ B[[l f ( [219
2
N
+ +2np KT2 Tmax K Kopni 0² + 2mp KI, mf P
N 1-1
3M M) 2NM(M 1) N
Σ
M
M
N-
N
N M
LK +6Ko + +30 + K2 EE V
f(x ب- |18]
+ 6nj 'n' L3L T
M(N 1) N T 1=1
Kni
0² + (N M)
+ L L
15K (02 +6Ko))
M
M(N 11)
1 N
7 - 1) NM 11)
+ (90K<L331 + 333)
N Σ
B[IIf + +
THR
E [[[V1.
2KN2
(C.
22

---

Published as a conference paper at ICLR 2024
By organizing and merging similar terms, we have
B[[(Z++)) - f(z))
miK
2 1
2 B1| [[[[[[(=))]]]] + mm (o + +KKo)) + +30K211
1/1
BII S (2 -
N
27 m K2 1?
maax 0² + +21 m L 2
N
3(N M) N -
2N 1)
Tmax
+
M
MN
N 1
N T-M 1 N
LK + +6Kog) + (30K
+
( f(==-=))11 )1|
+ +67" K Lx
M(N 1) N T/00
Knj
0² + ni (N- M)
+ n7²1 L
L3 + +6Kog)
M
M(N 1)
+ +900 L3np + 3K²)
1 N
Σ
3K }+
n/ - 1)
7717
E B[[[V.1
NM - 1)
2K N
(C.13)
Summing over t to T, we have
1]](2T+1]] - f(11)
T
N
S 2
ki
K
Elll [(: + KTK
5k T(o2 + +6Ko3)
+ +3K22
o
2
1
E BlIl ff (3x -111
N
217² mi K2 1.2 Tmax T 0² + 217² nr KT.
T N
3(N M)
2N - 1)
M
MN
N N-1 1
N N-1 1
(0 +6Kog) + +30K 1 + K2
f ب- )
N 1 T
N
KTT 0²
iN - M)
+ +67 3
2 1
+ 2
1 + +KKo))
max
M(N 1) N
M
M(N 1)
1=1
+ +90K + +3K2
[[IV((>))11 [BI +311)+13+3KK03 3K }
1 L(M -1
VI
E [1]]
NM (N
2KN
K T
- KTK +6Ko7)+ + +0K22 of Tmax Σ ([IV)(
< 2
2n7 21/211 K2 L2
Tiaxx T 0² + 2n nH KL 2
3(N - MM)
2N - 1)
max
M
M
N
N
N - M
5K 13 (0² + +6Kog) + (30K L + K2 max 1E [[(=))1]]
+
T TanaxxTvvg Taug" T
M(N 1) og
KTm 2 0² + Ii(N - M)
+1221 L
15K 15K T (02 + +6Ko²)
M
M(N 1)
L 11) NM -1)
+ +90K + +3K2) Σ B[|VS[() + 32 +
THR 2KN2
E v.
(C.14)
23

---

Published as a conference paper at ICLR 2024
thus by specific constraint the learning rate 7/t and 17, i.e., m S k and mm <
we have
4Tmax
T
1777 KT [f(2)) - [[]( + I25Kin + +KKo))
T
2Krîn L 0²+ 2 L Tmax
3(N - M)
N + 2N 1)
M
M
N
- M
5K 3 L2 (o² + +6Ko + 37 T/ K L2 TaaxFave
M(N - 1)
nL m
0² + m(N M)
M(N - 115K2 -6Kg)) + +3Ko]]
M
(C.15)
By choosing 1 ((VKK) and m 011/v/TTT have
|||V/(()]] o -1160 (o] - 0F
02 + Ko²
+ +0
VTKM
TK
VK
KTTax Tavg g
+ T=ax
+ +0 o
(C.16)
VTM
T
where ʃa = arr min (1x).
24

---

Published as a conference paper at ICLR 2024
D CONVERGENCE ANALYSIS FOR CA
Proof of Theorem 5.2
By the update scheme of Algorithm 2
we have
t h4 +
( 1-
h1-1)
7
h
+ 1
Σ
A 1- - -h-1)).
M
M
iESt
Σ
h
1-11
+ N
Σ
h
Σ r-
h h
N
M
iKS,
iES.
iES,
Σ
h
Σ
N
M
1
h +
M
1
レー!
(D.1)
S
VES.
Since we & represents the state update for client i, and h keeps unchanged if i S.. We also have the following
h, h h1-1+ Σ b-
h;
1
Σ A
+
Σ
A
(D.2)
N iES,
iES.
igS.
Since f is L-smooth, taking conditional expectation at time t, have
[[ - ((ar))
L E 2 mcel?
< <B(VS(()) [041
mg91 + + 1 L 2
(V)((x)))
Ell v 191
(D.3)
25

---

Published as a conference paper at ICLR 2024
Bounding I
1= ((V) moc))
=B( V (ar))
?
ΣΣ
7
Σ
h
+
1
Σ
hi-1)
M
N
M
N
iESt
SES,
= =m (f(()) M
K-1
9 -i-Tikk
+
N
1
M
1
K
N
Σ
Σ
K-1
g
ct.kk
}
iES,
k=0
iES,
k=0
tES, k=0
K-1
K-1
= -
(((a.)
VFL
+
M
N
M
EES. K=0
SES,
k=0
K-
N I
k=
K-1 VF +
K-1
=-MMKB
(f((a)
) MK
1
Σ
NK
MK
iES, k=0
iES, k=0
K-1 Vil
NK
KES, k=0
miK
Blll V f (xx1)1
2
W 2K
E
K-1
F. 5
+
N M
1
1/ ) ) + N
Σ PES. h=
K-1
v
F (at (
M
IES. k=0
mp K
E
K
1
Σ
M
V
+
N
1
M
1
ieS. k=n
K-1
V.. (0)
(D.4)
N
iES, k=0
where the second and third equation holds by the update rule. The forth one holds by the unbiasedness
of stochastic gradient, and the last one holds by the fact of (a, b) ||laa| 12 + [|b|22 - ||a b||3].
For the last item, we have
mp K
E
(xx)
Σ
(o
+
1 1 ) N M
2
K
M
S.
k=
F.
K K
E
(..) K
Σ
K-1 1
VR
(
w) + (+
1
V V
2
NK
M
M
i=1 0=
SES. k=0
|1 = (+)),
Σ
(
(D.5)
N
55 k=
26

---

Published as a conference paper at ICLR 2024
then
17
K
E
1
K-1
( +
(N
1
1
1 K-1
VF - VFF((=-
2
MK
N
M
K
iES; kmm
iES,
k= 0
K 1 Σ
+ NK
(P((
VV + M
Σ
[Pi(2,)) - V FZ 71
SRS. K=
iES.
+
1 M
Σ
VF( +
[Fi(x;)) - Fi a c3
N
N
iES.
VES.
K-1
SmIKE
MK Σ
- VPi(at [P(((0)-)))
+
VP. - VEi(x
N
M
SES, 0=0
iES, k=
K-1
(F)(a,-;)) - VB( /1] + MIKEE
+ NK
1
Σ
[V -
M
i K=
iES.
1
Σ [F((a,))) - (F
+ N Σ -VF((z))-V(((z) -
+ N
M
iES.
IES.
(D.6)
where we have
K- (P. - ( +
K-1
mi KE
V
(1 - VF
MK
N
M
EE k=0
iES, k=0
K-1 (P((a=-)) -
1
+
NK
Sg..s h=0
3mm E
(R(( - VF, mال00|1
M
K
iES,
31m K(N - M)
K-1
+
E
V
(2 ( ct
N
K
YES,
k=0
3 M)
K-1
127
+
[F((x,-)) - VF -3,
N2
YES
k=0
37m1 K
+ 6Koz) + 30K L2 E1 -1
M
SES.
31 M)²
+
[5KI 1/ + +0X
N2M
i.S.
3mm K(N M)
[5KL' 2 (0² +6Ko7) + 2 1 1131
N2
90mm31*L' L2
33mmK [5KL2 (0² + 6Ko +
EI|l [=);))))
M
iES.
61pK((N- - -
90mm K3 222²
1 (0² + +KKo +
E V Vf(+
N2
N
90mm K2 M)
(D.7)
22 igS,
27

---

Published as a conference paper at ICLR 2024
We also have
mE
1
[F((z)))
VE( +
Σ
[(A(())) - [=(x
M EE
N M
SE
(x,) VF (F 10100=>>11
N
igS.
37m K
3rp K(N - -)
E
[VF((a))) - F. (-2
E
[V.((x)) - (F
M
N
VES.
iES.
3mp K KIN
M)
N2
vgS.
31m KL2
E
Σ
Σ
(xo+1 a.)
3rm K(N M)
E
Σ
a0+t1 2c,)
M
N
EES
sm
ieS.
4
SypiK(N M)L²
E
Σ
(05+1 - 22a)
(D.8)
N2
Then we have
3mmKL' KL2
2
E
Σ
(x.+1 nzy)
37m K (N - 2)
E
Σ
Σ
(0 x.,)
M
N
iES.
==t-
SES;
3 M)L²
(Is+1 2z7)
E
N2
ig..
==1-6 cf
3mm K L
N Σ
21
31m K (N M)2
2
E
(0++1
xx5)
+
Σ
(xs+1 - x..)
N3
7f
S 4
3mm K(N 22
N
(xo+1 xx) 17
E
Σ
N3
3mm
KT2
17
6rm K K(N
2
E
Σ
(xs+1
E
(as+1 x2)
N
N3
(D.9)
Similar to the proof in the previous section, we have
Σ (xx+1
x:s))
of
E[[ xz op 1121
mmmax K <n²2ni 0² +
21 m
Σ E
K-1
Σ
1
VF
+
Mr
1
v
M
M
M
s
jeS,
A=D
Σ K-1
2000 17
+ N
Σ
VF (2f
(D.10)
U&S, 0=
28

---

Published as a conference paper at ICLR 2024
and
Σ (ms+1 - mim) 29
= B|| Iz 21-1;1171
26max K Knžnit
26 2mmax121i
Σ
1 M
((N
1
0² +
VF((2'
N
V
M
M
M
s
JES, k=0
K
V
(or
(D.11)
JdS, k=0
Bounding II
L II
E uz [9]
L
E
1 Σ
+
(N
(N-
N
111
Σ
h
+
1
Σ
hi
2
2
M
M
N
iES.
iES.
IgS.
K-
(+)
S
s LE
g
(=((at(=(,,)) +
Igi-
VF
M
N
M
VES, k=0
K-1 N Σ
|
Σ K-1
+
VF (p=t=i-
+ LE
M
14S,
k=0
IES. k=0
K-1
- 1
1
+ N
+
V (a((ot-(..)))
M
N
iES. K=0
K-1
1
2
K-1
S I M
+
E Bllgg- - (.F((r
N
M
iES, k=
iES, K=0
K-1
K-1 1
+ N2
Billgt +=(===
Σ
VF
M
S
k=0
iES, k=
+ 1 1
VF. (F((aL
+ N
V (P
N M
igS, K==
3K
K
(2o (1) + -
) (
1
< 17 n/
0²
+
2
LE
M
M
M
YES. k=0
Σ K
V
(D.12)
1g5, k=
Merging pieces.
For simplicity, we define V = Eies. Σk-1 (1 VF (1 ) + (2)
1 (V + N Eigs, ΣK- VF ( Therefore, by merging pieces together, we
29

---

Published as a conference paper at ICLR 2024
have
Bif( ((22) II 1I
mil
1Mt Bill V + 3 + 6umK(1 ((N-MM² 2K
E B1IVf(2;)1111
5KL2 T1i + +KKo
2
N²
3
90mM K3 -M)²
+
30K 1,2
30K
Σ
E [
M
N
iESt
iES.
90mm
L M)
6Tmax Kn²n) 2 L2
0²
N2
M
S
+
Σ E
K
1 (N=
VFi(
1
V
VF
M
M
M
JES.
k==
K-
19
126max K xn L
12 126max L2²
V (c0--s
F. (x)
o²
E
M
M
545,
s=t- ci
K-1
(a - + (N
11
1
VR 8 8 c2.kk
M
M
JES, k=
JES,
h=0
3K rp
+ L
vp BII d1f!
M
[ + 3
6(N
M)²
5xp 5mm K2
12 + +6Ko)) + +1221.
3k o²
2
N2
M
mamax K12nn
6 maxx 12 n2n22 L2
Elll V + 126max Knp L2
126 126max 17 PRRL L2
o² +
Elll V |
M
M
M
M
20mm 12
90mm 2 K 3 L - M2
f )1p
Σ
Ell V (
M
N
iES
iESt
K3 M)
r) n22n8 L
BV 1/
(D.13)
N
2K
Summing over t = to T. we have
(if( - -f((1)
miK
6(N .))
3KT o²
[(x))(+ 3
2TL2 6Ko + +
2
N2
M
6rmax 2 T.?KT
0² 126 p T.2
T.2 KT
+
0²
M
M
90mm L2
T
90mm K L -M) T
+
EI V f(x x )11
B V f (x, (x,-
M
N
t=1 iES.
1=1 ieS.
90mm K3 M)
+
N2
S
2 2 22
12c2 122 22 M
m
22 T
E B|I1,
(D.14)
2K
M
30

---

Published as a conference paper at ICLR 2024
with some conditions the learning rate yi and n), i.e., m S 1 mor
K 36 1
S
S 72
R <
36, Fmmaa. and K I 36v/maxl Therefore,
E -
mi
T
3 G(N M)
T o²
S
B(IVS(E))11)
K (o² 6Ko + +n²
4
N2
M
6T m) L KT 0² +
125max L 0².
(D.15)
M
M
Therefore,
mp K T
V s f(x1) [[ 3 6(N 6(N-6((6)))) -M)2
5mmK TLL + +Koo))
N²
+ 11²1 35T o² + 6Tmax 21, L2
125maxt 1 L2
0²
0²,
M
M
M
6(N - -M²
+ Σ B
K7 [f(x) B[f(x++1]]] 3
5KL (o + 6KKg))
N2
+ 3mm o² (Tmax + 26max)
6
(D.16)
M
Hence by choosing Yit
VTK and 1) = KM, then the convergence rate satisfies
T
E [1; o fo f fx
10(0²
(02 (o2+ Ko
VTKMM
+ +0
+ +0
VTKM
TK
(Tmax + Smax) )o²
+ O
(D.17)
T
where f- = aar ming (x)
E SUPPORTING LEMMAS
Lemma E.I. The model difference A, = - Eiem, Ai= + Eiem, Σk- gi with Mel = M
satisfies
2km M
2N M)
A 12 S
of
(f + +
NM 1)
21f( 1)
N K-1
2 -
+ 32 20 +
Σ (F((2(
NM -
0=
31

---

Published as a conference paper at ICLR 2024
Proof. We have
[
E
A
11
Σ
M
M:M:
1 E
lie Mi)ai
M
2nd
K-1
1
K-1
B
Σ li E Mi)
Σ
(=((2,,,))
+
Σ
liie Md
Σ
(F((
M
2nf
K-1
1
K
EiE E M.
Σ
+
Hi E MM
M
k=
1=1
k=0
2nf
K-1
11
2d2
K-1
E
Σ
Σ
19
EE
E Ci Σ
VF
NM
M
k=0
k=0
2km of
2n EE
N
K-1
17
Σ
T(EEM,)
Σ
(E.1)
n
M
k=
where the fifth equation holds due to E M.)
M
N. Note that we have
||
2
Σ
Σ
Σ
(
+
N
K-
K-1
1
Σ N
V
(
V FJ
2
t.kk
k=
k=0
k=
(E.2)
where the second equation holds due to
|| Σ
2z 22 =
-i=1
N
||
1|
E Eij
|0, 22,11 By the
sampling strategy (without replacement), we have Pii M.) #/4 and thus we have
M,]
M(M-1)
N(N
N
K
)
||
E M.)
K-1 Σ Pli e Mi}
N
12 11
K-1
K-1
EPli
Σ
+ EPRij S Mi
Σ
(F((E)))
Σ VF, (x
k=O
143
M
M(M 1)
K-1
K-1
+
(F
Σ
V
VE (a
N
N(N 1) (
k=
M N
M(M 1)
K
Σ
VR(CEN)))
Σ
(
V (
N
2N(N - 1) (f)
k==
M(N M)
N
K-1
2
M(M -1) 1)
N
Σ
Σ
Σ
Σ
(a((
N(N 1)
N(N - 1)
:=1 k=0
(E.3)
where the third equation holds due to (a, y) |||ج|| + || 1|
|| 2| and the last equation
holds due to Eitj Iz 2, Σ N|
1|2
Σ Di x; Therefore, for the last term in
equation E. we have
E|| A 19|
<
2K t
M o NM 11)
2 - M)
Σ
E
V FF(2
17
2n (M - 1) E NM 1)
V V
1=1
A= 0
i=1 k= 0 (E.4)
32

---

Published as a conference paper at ICLR 2024
The second term in equation
E.4
is bounded partially following Reddi et al. (2021).
Σ
Σ
R
VF (f:))))) Vf(ax) V
N
K-
1
$ 3
[F(((
VA( -
+3NK 2NN
K-1
<3Kt²
Bllo
+NNK2
+ (3x
k=0 < 15NK"L3 6Koz)
(9ONK +3 3N
(E.5)
where the last inequality holds by applying Lemma E.2 (also follows from Reddi al. (222
Substituting equation E.5 into equation E.4 this concludes the proof.
Lemma E.2. (This lemma directly follows from Lemma 3 in FedAdam Reddi et al. (2021) l). For local learning rate which satisfying vp I 8KE the local model difference after (vk E {0, ..., K 1)) steps local updates satisfies
Ell - xr|1?] s (o + 6Ko?) + 30 [[]
(E.6)
Proof. The proof of Lemma
E.2 exactly same as the proof of Lemma 3 in Reddi al. (202I).
33


Reviews:
[{"review_id": "474A7Qi1ix", "reviewer": "Reviewer_3At2", "summary": "The manuscript tackles the problem of data heterogeneity in asynchronous federated learning. The authors show that the asynchronous delay can negatively affect the convergence of the learning process, especially when the data across clients are highly non-i.i.d. To address this issue, they propose a novel method called  Cached-Aided Asynchronous FL, which uses cached updates from each client to calibrate the global update at the server. They prove that the proposed method can improve the convergence rate under nonconvex stochastic settings and demonstrate its performance on several vision and language tasks. Moreover, the authors present a convergence analysis of FedBuff algorithm, a prior asynchronous FL algorithm, under non-i.i.d. distributed data across clients.", "questions": "The paper “Unbounded Gradients in Federated Learning with Buffered Asynchronous Aggregation” also improves the analysis of FedBuff. I recommend comparing your FedBuff analysis with this work as well.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has several strengths that make it an incremental contribution to the field of asynchronous FL. First, the paper presents a novel and unified convergence analysis of FedBuff algorithm. The paper also makes fewer assumptions (similar to Koloskova et al.) and provides slightly tighter bounds on the asynchronous delay term than previous works. Second, the paper proposes a novel method that improves the convergence rate under nonconvex settings. Third, the paper demonstrates the superior performance on both vision and language tasks.", "weaknesses": "The paper has some limitations that could be further addressed. First, the paper only evaluates its method on relatively simple vision and language tasks, such as CIFAR. It would be interesting to see how the method performs on more challenging data sets, such as ImageNet. Second, the paper only considers classification tasks for language, which may not fully capture the complexity and diversity of natural language processing. It would be worthwhile to explore how the method works on other language tasks, such as generation, translation, summarization, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BYBmTNBduJ", "reviewer": "Reviewer_yUBQ", "summary": "Paper introduces the Cache-Aided Asynchronous Federated Learning (CA$^2$FL) algorithm which allows a central server to cache each received update from a device and use it to correct the global update. Standard convergence rate guarantees are provided, and nice empirical results showcase the improved performance of CA$^2$FL. CA$^2$FL is closely tied to FedBuff, with a small tweak to allow models to be cached and reused during training.", "questions": "1. Remark 3.5 and the overall convergence analysis of FedBuff is not very novel. Equation (4) in FedBuff also details the $\\tau_{max}$ and $\\sigma^2$ issues. What is novel by reproducing it?\n2. The state delay seems closely tied to the gradient delay. Why can't the state delay take the form of the gradient delay? The inclusion seems to muddle the convergence result in Equation (5.1).\n3. Do the convergence rates align with FedBuff and FedAsync? Are they better or worse? A table would be nice to detail this comparison.\n4. How much memory is added to the training process when models are cached? I could see that this would be problematic in real-world implementations with thousands or hundreds of thousands of devices participating in training.\n5. The idea of caching seems quite similar to the recent ICLR work [R2], except in the decentralized setting. [R2] seems to also utilize some sense of caching and it might be a closer comparison in the asynchronous FL domain.\n\nI am interested to see how to authors respond to my questions and concerns. I feel that this paper is very strong empirically, which is important. At the same time, the novelty of the proposed method does not seem to clear the bar of an accepted paper.\n\n[R2] Bornstein, Marco and Rabbani, Tahseen and Wang, Evan and Bedi, Amrit Singh and Huang, Furong. \"SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication.\" International Conference on Learning Representations. 2023.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Paper is well-written, concise, and straightforward.\n2. Very strong empirical results! The section is nicely done, and the algorithm is compared to relevant baselines (one other algorithm which may be quite related could also be compared against and I've mentioned it in the Questions section).", "weaknesses": "1. Reproducing the empirical results of FedBuff is important to motivate the Cache-Aided algorithm, but should not take up much space and shouldn't be considered a contribution.\n2. The cache idea seems to stem from SAGA, and while its inclusion is non-trivial, this is the only new piece to the FedBuff algorithm and thus the contribution seems to be marginal.\n3. Maximum gradient delay bound is used, however newer works no longer require this assumption [R1]. I ask below in the questions, but slight confusion with state delay and why gradient delay can't be used for it as well.\n\n[R1] Koloskova, Anastasiia, Sebastian U. Stich, and Martin Jaggi. \"Sharper convergence guarantees for asynchronous sgd for distributed and federated learning.\" Advances in Neural Information Processing Systems 35 (2022): 17202-17215.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3cbdrONM8i", "reviewer": "Reviewer_xHG4", "summary": "This paper presents a significant advancement in the field of federated learning by introducing the Caching and Asynchronous Aggregation Federated Learning (CA2FL) method, a novel approach designed to optimize the learning process in non-convex stochastic settings. Recognizing the challenges posed by asynchronous updates and non-IID data in decentralized learning systems, the authors propose an innovative technique that caches and reuses previous updates for global calibration, aiming to enhance convergence and overall efficiency.\n\nThe core contribution of the research lies in its robust theoretical analysis, which underscores the method's substantial improvements in convergence. In addition to the theory, the paper provides empirical results that demonstrate CA2FL's superior performance compared to traditional asynchronous federated learning approaches. These results are particularly good, indicating that the method not only addresses key challenges in the field but also outperforms existing solutions.\n\nFurthermore, the research introduces an iteration of the method, MF-CA2FL, designed to significantly reduce memory overhead, a critical consideration in practical applications. This variant maintains the performance benefits of the original method, indicating the approach's flexibility and adaptability.", "questions": "1.  The CA2FL method introduces a unique approach to handling asynchronous updates in federated learning, but how does it adapt to various neural network architectures and models? Given the diverse range of models used in different sectors, can the authors elaborate on the method's compatibility and performance enhancements across these varied architectures?\n2.  Federated learning often operates under constraints like limited bandwidth, varied data quality, or privacy regulations. How does the CA2FL method, with its caching and asynchronous aggregation, perform under such practical constraints? \n3. The paper highlights the immediate improvements in convergence and efficiency, but federated learning models often operate over extended periods, during which they may encounter non-stationary data sources (model drift). How does the CA2FL approach anticipate and handle such long-term challenges? Are there mechanisms within the method to adapt to evolving data characteristics while maintaining its efficiency and accuracy over time?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. By implementing a caching mechanism that reuses previous updates, the CA2FL  method optimizes the learning process, particularly in environments with non-IID data and asynchronous updates. \n2. The authors don’t just stop at theoretical claims; they substantiate their findings with empirical data, demonstrating the method's superior performance in real-world scenarios, including several vision and language tasks.\n3. By addressing the critical issue of memory overhead in federated learning systems, MF-CA2FL maintains the advantages of the CA2FL method while significantly reducing resource consumption, making it highly beneficial for practical deployments, especially in resource-constrained environments.", "weaknesses": "1.  It's unclear if the proposed CA2FL method was tested across a diverse range of scenarios, network architectures, or data distributions. This limited scope might raise questions about the method's generalizability and effectiveness in various real-world applications outside the tested environments.\n2. The paper might not fully address how this complexity impacts the scalability of the method, especially in larger, more diverse decentralized systems. If the method imposes significant computational or communicational overhead, it could limit its scalability and practical adoption. For example, it is only tested on CIFAR-10/100 dataset with ResNet-18 which is a shallow small NN architecture.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)