FedCompass: Efficient Cross-Silo Federated Learning on Heterogeneous Client Devices Using a Computing Power-Aware Scheduler
Authors: Zilinghan Li
Pranshu Chaturvedi
Shilan He
Han Chen
Gagandeep Singh
Volodymyr Kindratenko
Eliu A Huerta
Kibaek Kim
Ravi Madduri
Venue: ICLR 2024 poster (2024)
Keywords: Federated Learning
Device Heterogeneity
Cross-silo Federated Learning
Primary area: general machine learning (i.e., none of the above)
TL;DR: We propose FedCompass, a semi-asynchronous federated learning algorithm for faster convergence on heterogeneous clients and data.

Abstract: Cross-silo federated learning offers a promising solution to collaboratively train robust and generalized AI models without compromising the privacy of local datasets, e.g., healthcare, financial, as well as scientific projects that lack a centralized data facility. Nonetheless, because of the disparity of computing resources among different clients (i.e., device heterogeneity), synchronous federated learning algorithms suffer from degraded efficiency when waiting for straggler clients. Similarly, asynchronous federated learning algorithms experience degradation in the convergence rate and final model accuracy on non-identically and independently distributed (non-IID) heterogeneous datasets due to stale local models and client drift. To address these limitations in cross-silo federated learning with heterogeneous clients and data, we propose FedCompass, an innovative semi-asynchronous federated learning algorithm with a computing power-aware scheduler on the server side, which adaptively assigns varying amounts of training tasks to different clients using the knowledge of the computing power of individual clients. FedCompass ensures that multiple locally trained models from clients are received almost simultaneously as a group for aggregation, effectively reducing the staleness of local models. At the same time, the overall training process remains asynchronous, eliminating prolonged waiting periods from straggler clients. Using diverse non-IID heterogeneous distributed datasets, we demonstrate that FedCompass achieves faster convergence and higher accuracy than other asynchronous algorithms while remaining more efficient than synchronous algorithms when performing federated learning on heterogeneous clients. The source code for FedCompass is available at https://github.com/APPFL/FedCompass.

Published as a conference paper at ICLR 2024
FEDCOMPASS: EFFICIENT CROSS-SILO FEDERATED LEARNING ON HETEROGENEOUS CLIENT DEVICES USING A COMPUTING
SCHEDULER
Zilinghan Li Pranshu Chaturvedi2.2.3. Shilan Hel.2.3 Han Chen', Gagandeep Singh Volodymyr Kindratenko E. A. Huerta Kiback Kim', Ravi Madduri-
Argonne National Laboratory, Univeersity of Illinois at Urbana- SabbanaChammaiin, National Center for Supercomputing Applications. *VMWare Research, 'The University Chicago
{2152, pranshu3, shilanh2, hanc7, ggnds, kindrtnk) ielliiiiiiiiiiieeeiieiiimiiiilll edu [elihu, kimk, (edduri]eani.goer
ABSTRACT
Cross-silo federated learning offers a promising solution to collaboratively train robust and generalized AI models without compromising the privacy of local datasets, e.g., healthcare, financial, as well as scientific projects that lack a central- ized data facility. Nonetheless, because of the disparity of computing resources among different clients (i.e., device heterogeneity), synchronous federated learn- ing algorithms suffer from degraded efficiency when waiting for straggler clients. Similarly, asynchronous federated learning algorithms experience degradation in the convergence rate and final model accuracy on non-identically and indepen- dently distributed (non-IID) heterogeneous datasets due to stale local models and client drift. To address these limitations cross-silo federated learning with innovative semi-
heterogeneous clients and data, we propose FedCompass, asynchronous federated learning algorithm with a computing power-aware sched- uler the server side, which adaptively assigns varying amounts of training tasks to different clients using the knowledge of the computing power of individual clients. FedCompass s ensures that multiple locally trained models from clients are received almost simultaneously as group for aggregation, effectively reduc- ing the staleness of local models. At the same time, the overall training pro- cess remains asynchronous, eliminating prolonged waiting periods from straggler clients. Using diverse non-lII heterogeneous distributed datasets, we demonstrate that FedCompass achieves faster convergence and higher accuracy than other asynchronous algorithms while remaining more efficient than synchronous algo- rithms when performing federated learning heterogeneous clients. The source code for FedCompass is available at https///giibbb.omm///PPP/LCCCCCp
INTRODUCTION
Federated learning (FL) is a model training approach where multiple clients train a global model under the orchestration of a central server (Konečný et al. 2016 McMahan et al. 2017 Yang al. 2019 Kairouz et al. 2021). In FL, there are m distributed clients solving the optimization problem: k== P. (w), where p; is the importance weight of client i's local data, and is usually defined as the relative data sample size, and F((w) is the loss on client i's local data. FL typ- ically runs two steps iteratively: (i) the server distributes the global model clients to train it using their local data, and (ii) the server collects the locally trained models and updates the global model by aggregating them. Federated Averaging (F (edAv)) (McMahan al. (017) is the most popular FL algorithm where each client trains a model using local data for C) local steps in each training round, after which the server aggregates all local models by performing a weighted averaging and sends the updated global model back to all clients for the next round of training. By leveraging the training data from multiple clients without explicitly sharing, FL empowers the training of more robust and generalized models while preserving the privacy of client data. The data in FL is generally hetero- geneous, which means that client data is non-identically and independently distributed (non-III) IID). FL is most commonly conducted in settings: cross-device FL and cross-silo FL (Kairouz al.) 202T). In cross-device FL, numerous mobile or loT devices participate, but not in every training round because of reliability issues (Mills al. 2019). In cross-silo FL., smaller number of reliable
min wi F(w)

---

Published as a conference paper at ICLR 2024
clients contribute to training in each round, and the clients are often represented by large institutions in domains such as healthcare or finance, where preserving data privacy is essential (Wang et al.
2019
Wang
2019: Kaissis et al., 2021 Pati et al. 2022 Hoang et al. 2023).
The performance of FL suffers from device heterogeneity, where the disparity of computing power among participating client devices leads to significant variations in local training times. Classical synchronous FL algorithms such as FedAvg, where the server waits for all client models before global aggregation, suffer from compute inefficiency as faster clients have to wait for slower clients (stragglers). Several asynchronous FL algorithms have been developed to immediately update the global model after receiving one client model to improve computing resource utilization. The prin- cipal shortcoming in asynchronous FL is that straggler clients may train on outdated global models and obtain stale local models, which can potentially undermine the performance of the global model. To deal with stale local models, various solutions have been proposed, including client selection, weighted aggregation, and tiered FL.. Client selection strategies such as FedAR (Imteaj & Amini, 2020) select a subset of clients according to their robustness computing power. However, these strategies may not be applicable for cross-silo FL settings, where all clients are expected to partic- ipate to maintain the robustness of the global model. Algorithms such FedAsync (Xie et al.) 2019] introduce a staleness factor to penalize the local models trained on outdated global models. While the staleness factor alleviates the negative impact of stale local models, it may cause the global model to drift away from the slower clients (client drift) even with minor disparities in client computing power, resulting in a further decrease in accuracy on non-IID heterogeneous distributed datasets. Tiered FL methods such as Fe FedAT (Chai et al. 2021] group clients into tiers based on their computing power, allowing each tier to update its own pace. Nonetheless, the waiting time inside each tier can be significant, and it is not resilient to sudden changes in computing power.
In this paper, we focus on improving the performance in cross-silo FL. settings. Particularly, we pro- pose a semi-asynchronous cross-silo FL. algorithm, FedCompass, which employs a COMputing Power-Aware Scheduler (Compass) to reduce client local model staleness and enhance FL effi- ciency in cross-silo settings. Compass assesses the computing power of individual clients based on their previous response times and dynamically assigns varying numbers of local training steps to ensure that a group of clients can complete local training almost simultaneously. Compass is also designed to be resilient to sudden client computing power changes. This enables the server to perform global aggregation using the local models from group of clients without prolonged wait- ing times, thus improving computing resource utilization. Group aggregation leads to less global update frequency and reduced local model staleness, thus mitigating client drift and improving the performance on non-IID heterogeneous data. In addition, the design of F FedCompass is orthog- onal to and compatible with several server-side optimization strategies for further enhancement of performance on non-IID IID data. In summary, the main contributions of this paper are as follows:
A novel semi-asyychronous cross-silo FL. algorithm, FedCompass, which employs a re- silient computing power-aware scheduler to make client updates arrive in groups almost simultaneously for aggregation, thus reducing client model staleness for enhanced perfor- mance on non-III heterogeneous distributed datasets while ensuring computing efficiency. A suite of convergence analyses which demonstrate that FedCompass s can converge to first-order critical point of the global loss function with heterogencous clients and data, and offer insights into how the number of local training steps impacts the convergence rate.
A suite of experiments with heterogeneous clients and datasets which demonstrate that FedCompase converges faster than synchronous and asynchronous FL algorithms, and achieves higher accuracy than other asynchronous algorithms by mitigating client drift.
2 RELATED WORK
Device Heterogeneity in Federated Learning. Device heterogeneity occurs when clients have varying computing power, leading to varied local training times (Li et al., 2020 Xu et al.) 2021). For synchronous FL. algorithms that wait for all local models before global aggregation, device het- erogeneity leads to degraded efficiency due to the waiting time for slower clients, often referred to as stragglers. Some methods address device heterogeneity by waiting only for some clients and ignoring the stragglers (Bonawitz et al. 2019). However, this approach disregards the contributions of straggler clients, resulting in wasted client computing resources and global model significantly biased towards faster clients. Other solutions explicitly select the clients that perform updates. [Chen et al. (2021) employs a greedy selection method with heuristic based client computing
2

---

Published as a conference paper at ICLR 2024
sources. Hao et al. (2020) defines priority function according to computing power and model accuracy to select participating clients. F FedAr (Imteaj & Amini 2020) assigns each client a trust score based previous activities. FLNAP (Reisizadeh et al. (022) starts from faster nodes and gradually involves slower ones. FedCs (Nishio & Yonetani 2019) queries client resource informa- tion for client selection. SAFA (Wu et 2022) chooses the clients with lower crash probabilities. However, these methods may not be suitable for cross-silo FL settings, where the participation of every client is crucial for maintaining the robustness of the global model and there are stronger assumptions with regard to the trustworthiness and reliability of clients.
Asynchronous Federated Learning. Asynchronous FL algorithms provide another avenue to mit- igate the impact of stragglers. In asynchronous FL, the server typically updates the global model once receiving one few client models (Xie et al. 2019 Chen al., 2020) stores the local mod- els in a size-K buffer (Nguyen et al. 2022] So et al. (2021). and then immediately sends the global model back for further local training. Asynchronous FL offers significant advantages in heteroge- neous client settings by reducing the idle time for each client. However, one of the key challenges in asynchronous FL is the staleness of local models. In asynchronous FL, global model updates can occur without waiting for all local models. This flexibility leads to stale local models trained on outdated global models, which may negatively impact the accuracy of the global model. Var- ious solutions aimed to mitigate these adverse effects have been proposed. One common strategy weighted aggregation, which is prevalent in numerous asynchronous FL. algorithms (Xie et al.) 2019 Chen et al. 2019 2020 Wann et al., 2021, Nguyen et al., 2022). This approach applies a staleness weight factor to penalize outdated local models during the aggregation. While effective in reducing the negative impact of stale models, this often causes the global model to drift away from the local data on slower clients, and the staleness factor could significantly degrade the final model performance in settings with minor computing disparities among clients. Tiered FL methods offer another option for improvement. FedAT (Chai et al.] 2021) clusters clients into several faster and slower tiers, allowing each tier to update the global model its own pace. However, the waiting time within tiers can be substantial, and it becomes less effective when the client pool is small and client heterogeneity large. The tiering may also not get updated timely to become resilient to speed changes. Similarly, CSAFL (Zhang et al. (02T) groups clients based on gradient direction and computation time. While this offers some benefits, the fixed grouping can become a liability if client computing speeds vary significantly over the course of training.
3 PROPOSED METHOD: FEDCOMPASS
The design choices of FedCompass are motivated by the shortcomings of other asynchronous FL algorithms caused by the potential staleness of client local models. In FedAsync, as the global model gets updated frequently, the client model is significantly penalized by a staleness weight factor, leading to theoretically and empirically sub-optimal convergence characteristics, especially when the disparity in computing power among clients is small. This can cause the global model non-lID
to gradually drift away from the data of slow clients and have decreased performance datasets. FedBuff f attempts to address this problem by introducing a size- K buffer for client up- dates to reduce the global update frequency. However, the optimal buffer size varies for different client numbers and heterogeneity settings and needs to be selected heuristically. It is also possible that one buffer contains several updates from the same client, or one client may train the same global model several times. Inspired by those shortcomings, we aim to group clients for global ag- gregation to reduce model staleness and avoid repeated aggregation or local training. As cross-silo FL involves a small number of reliable clients, this enables us to design a scheduler that can pro- file the computing power of each client. The scheduler then dynamically and automatically creates groups accordingly by assigning clients with different numbers of local training steps to allow clients with similar computing power to finish local training in close proximity each other. The scheduler tries to strike a balance between the time efficiency of asynchronous algorithms and the objective consistency of synchronous ones. Additionally, we keep the scheduler operations separated from the global aggregation, thus making it possible to combine the benefits of aggregation strategies in other FL algorithms, such as server-side optimizations for improving performance when training data are non-IID (Hsu et al. 2019 Reddi et al., 2020) and normalized averaging to eliminates objective in- consistency when clients perform various steps (Wang et al. 2020; Horváth et al. 2022). Further, from the drawbacks of tiered FL methods such FedAT, the scheduler is designed to cover mul- tiple corner cases to ensure its resilience to sudden speed changes, especially those occasional yet substantial changes that may arise in real-world cross-silo FL as a result of HPC/cloud auto-scaling.
3

---

Published as a conference paper at ICLR 2024
3.1 COMPASS: COMPUTING
SCHEDULER
To address the aforementioned desiderata, we introduce Compass, COMputing Power-Aware Scheduler that assesses the computing power of individual clients according to their previous re- sponse times. Compass then dynamically assigns varying numbers of local steps Q within pre- defined range [Qmin: muax] to different clients in each training round. This approach ensures that multiple client models are received nearly simultancously, allowing for a grouped server aggrega- tion. By incorporating several local models in a single global update and coordinating the timing of client responses, we effectively reduce the frequency of global model updates. This, in turn, reduces client model staleness while keeping the client idle time to minimum during the training process.
FedCompass Server
Artival Group
FedCaoppeo Server
Arrival Group 2 T. 22: 00
FucCCompss Server
Arrival Group 3 32:
Clant
Tu 12:00
Own
R Q Dae G Q Q Ir
Q Praz
Q
Orer 100
08:00
02:00
02: 00
12:00 D,
12:60
22:00 AL
22:00
Qen.
- 40
Q 50
2.Quex 50
00.00 08.00..m
04: 00
04:00 00
12:00 Aq
12:
22:00
22:00
3
Own 20
28
Q
2:0
00:
05:00 4y
05:00
12:00 bg
12:00
22:00 by
22:00
Qum 20
4
IIIT
10
Arrival Group 2
T, 22: 00
2 Q 25
02:00
08: 00 44
00::00 ar
22:00 d
22:00
3
Quis
CS
Q
1 & =0
00:
0 00 bg
10: D0
22:00 bg
22:00
AGGREGATE+ CREATEGROUP
Speed
AGOREGATE JonGROUP
Figure I: Overview of an example FL run using Compass scheduler on five clients with the mini- mum number of local steps Qmin = 20 and maximum number of local steps Qmax = 100.
Figure [ jillustrates an example run of federated learning using Compass on five clients with dif- ferent computing power. For the sake of brevity, this illustration focuses on a simple scenario, and more details are described in Section 3.2 All times in the figure are absolute wall-clock times from the start of FL. First, all clients are initialized with Qmin = 20 local steps. When client 1 finishes local training and sends the update A₁ to the server at time 02:00, Compass records its speed and creates the first arrival group with the expected arrival time T. = 12:00, which is computed based on the client speed and the assigned number of local steps Q = Q 100. We assume negli- gible communication and aggregation times in this example, so client receives an updated global model w immediately at 02:00 and begins the next round of training. Upon receiving the update from client 2, Compass slots it into the first arrival group with Q = 40 local steps, aiming for a completion time of Ta 12:00 as well. Client follows suit with 28 steps. When Compass computes local steps for client 4 in order to finish by To = 12:00. it finds that Q = 10 falls below Qmin 20. Therefore, Compass creates a new arrival group for client 4 with expected arrival time Ta = 22:00. Compass optimizes the value of Ta such that the clients in an existing arrival group may join this newly created group in the future for group merging. After client 5 finishes, it is assigned to the group created for client 4. When clients 1-3 finish their second round of local training at 12:00, Compass s assigns them to the arrival group of clients 4 and (i.c., arrival group 2) with the corresponding values of Q so that all the clients are in the same arrival group and expected to arrive nearly simultaneously for global aggregation in the future. The training then achieves equi- librium with fixed number of existing groups and group assignments, and future training rounds will proceed with certain values of Q for each client in the ideal case. The detailed implementation and explanation of Compass ss can be found in Appendix A We also provide analyses and empirical results for non-ideal scenarios with client computing powering changes in Appendix G.2 where we show how the design of Compass makes it resilient when clients experience speedup or slowdown during the course of training, and compare it with the tiered FL method FedAT (Chai et al. 2021)
3.2 FEDCOMPASS: FEDERATED LEARNING WITH COMPASS
FedCompass is semi-asynchronous FL algorithm that leverages the Compass scheduler to co- ordinate the training process. It is semi-asynchronous as the server may need to wait for a group of clients for global aggregation, but the Compass scheduler minimizes the waiting time by managing to have clients within the same group finish local training nearly simultancously, so the overall train- ing process still remains asynchronous without long client idle times. The function FEDCOMPASS-
4

---

Published as a conference paper at ICLR 2024
Algorithm 1: FedCompass Algorithm
Function CLNCCMPPSS-CCIENTY w, Q Te. B):
Input: Client id i, global model w, number of local steps Q. local learning rate rjr, batch size
for ....... Q] do
BiQq random training batch with batch size B;
W2.q = W1,4-1 n) (1 Br,q) We. client i's model after g steps, Wi.0 w;
Send A, == wi,0 Ws,Q to server;
Function WEDCOMMASSS-SERVERR
qe, B,
Input: Number comm. rounds local learning rate T7, hatch size B, initial model weight w FEDCOMPASS-COE CLIENT(Í, w, Qmin. Tjr, B) for all client i's; Initialize client info dictionary C, group info dictionary G, and global model timestamp Tg == 0: for ni [1,...,.] do
11
if receive update A, from client then
12
Record client speed into C [i] .S:
13
if client has an arrival group g then
9 [g] C.C.remevee (i), 9 [[g).AC (4) move client to arrived client list; if T 9 [g].Tmmme max then
A = A + st st - (() As; [i). Tgi & st(.) )) is staleness factor;
ASSIGNGROUP(d) > this computes C [4] QQ details in Alg. from Appendix; FEDCOMPASS-CLIENT (i, w. [[]..2,m B);
19
delete 9 [g] 1en (G ([g).CL) =
elsc
21
A = n st( (())r) * p. * A, b st(.) is staleness factor; if len (9 [g).CCC = 0) then GROUPAGGREGATE((S) >> details in Alg. 3 from Appendix; delete 9 [g];
else
: - C[ A;; To To 11; ASSIGNGROUP(1) this computes Clil.Q. details in Alg. from Appendix: FEDCOMPASS-CUAE CLIENT (i, Clú) (21i).Q.1 mr, B);
C(t) Tgi
26
27
CLIENT in Algorithm outlines the client-side algorithm for FedCompass. The client performs Q local steps using mini-batch stochastic gradient descent and sends the difference between the initial and final models A, as the client update to the server.
The function FEDCOMPASS-SERN SERVER in Algorithm presents the server algorithm for FedCompass. Initially, the absence prior knowledge of clients' computing speeds, the server assigns minimum of Qmin local steps to all clients for warm-up. Subsequently, client speed information is gathered and updated each time a client responds with the local update. For cach client's first response (lines 25 to 28), the server immediately updates the global model using the client update and assigns to an arrival group. All clients within the same arrival group are ex- pected to arrive almost simultaneously at specified time Ta for the next global group aggregation. This is achieved by assigning variable local steps based on individual computing speeds. The As- SIGNGROUP function first attempts assign the client
existing group with local steps within the range of [Qmin, maa)) If none of the existing groups have local step values that can accom- modate the client, a new group is created for the client with a local step value that facilitates future group merging opportunities. Further details for this function are elaborated in Appendix [A]
After the initial arrivals, each client is expected to adhere the group-specific arrival time T.. Nonetheless, to accommodate client speed fluctuations and potential estimation inaccuracies, a latest arrival time Tmax per group is designated. If a client arrives prior to Tmax (as per lines 20 to 24), the server stores the client update in a group-speeific buffer A and checks whether this client the last within its group to arrive. If so, the server invokes GROUPAGGREGATE to update the global model with contributions from all clients in the group and assign new training tasks to them with the latest global model. The details of GROUPAGGREGAN there remain pending clients within the group, the server will wait until the last client arrives or the latest arrival time Thax before the group aggregation. Client(s) that arrive after the latest time Tmax and miss the group aggregation (lines 15 to 19), due to an unforeseen delay or slowdown, have their updates stored in general buffer A, and the server assigns the client to arrival group
are shown in Algorithm 3 in the Appendix.
5

---

Published as a conference paper at ICLR 2024
immediately using the ASSIGNGROUP function for the next round of local training. The updates in the general buffer will be incorporated into the group aggregation of the following arrival group.
4 CONVERGENCE ANALYSIS
We provide the convergence analysis of FedCompass for smooth and non-convex loss functions (ww). We denote by V (w)) the gradient of global loss, (F.(w) the gradient of client i's local loss, and f, B.) the gradient of loss on batch B,. With that, we make the following assumptions.
Assumption 1. Lipschitz smoothness. The loss function of each client i is Lipschitz smooth. [VVF(w) - (F,(w')ll & L|[w - w'll
Assumption 2. Unbiased client stochastic gradient. Es, [i B.))] VF](.)
Assumption 3. Bounded gradient, and bounded local and global gradient variance. [[VF((W)) M, EB, VI [()) - V FF()))) S of, and [E[[[V
FF(w)]l?) S oz..
Assumption 4. Bounded client heterogeneity and staleness. Suppose that client is the fastest client, and client b is the slowest, Ta and To are the times per one local step of these two clients, respectively. We then assume that Taa"aa S pt. This assumption also implies that the staleness (Tg C [(].TT of each client model is also bounded by a number Tiax-
Assumptions 3 are common assumptions in the convergence analysis of federated distributed learning algorithms (Stch 2018: Li et al. 2019; Yu et al. 2019 Karimireddy et al.) [0200] Nguyen al. 2022). Assumption 4 indicates that the speed difference among clients is finite and is equiva- lent to the assumption that all clients are reliable, which is reasonable in cross-silo FL..
Theorem 1. Suppose that me S 21Quue. Q Quax// m and μl Qloong HJ, Then, after T
updates for global model w, FedCompass achieves the following convergence rate:
2 21ymemm of < Qmin
of max (T + 1);
(IVF(((()) T 1=0
21Q
71Qmin
(1)
where m is the number of clients, w(() is the global model after global updates, ?11 1+ a 7/2
1 + pd'mm - 1). F - F(w"), and 0² = =o + oi + M.
Corollary 1. When Qmin S Qmaxx/ and T/p = O(L(( VT) while satisfying Ve S 2T.Qmss'
then
min E VF 0 KETT]
mF VT
+ 0
moo om VT + O
( max max
2²2
T
The proof is provided in Appendix algorithmic characteristics.
C Based on Theorem [and Corollary
we remark the following
Worst-Case Convergence. Corollary [ provides an upper bound for the expected squared norm of the gradients of the global loss, which monotonically decreasing with respect to the total number of global updates T. This leads to the conclusion that FedCompas: converges to a first-order sta- tionary point in expectation, characterized by zero gradient, of the smooth and non-convex global loss function F(w) = >m Pt (w)) Specifically, the first term of equation 2 represents the influ- ence of model initialization, and the second term accounts for stochastic noise from local updates. The third term reflects the impact of device heterogeneity (f and data heterogeneity (a²) on the convergence process, which theoretically provides a convergence guarantee for FedCompass on nID heterogeneous distributed datasets and heterogeneous client devices.
Effect of Number of Local Steps. Theorem establishes the requirement ne S 21.Qmax signifying a trade-off between the maximum number of client local steps Quax and the client learning rate Me. A higher Quax necessitates smaller m) to ensure the convergence of FL training. The value of Qmin also presents a trade-off: a smaller Qmin leads to a reduced μ², causing an increase in 71 and a decrease in 72, which ultimately lowers the gradient bound. Appendix B shows that Qmin also influences the grouping of FedCompass. There are at most [logo μu] existing groups at the equilibrium state, so smaller Qmin results in fewer groups and smaller Tmax. However, since Qmin appears in the denominator in equation[]] [ a smaller Qmin could potentially increase the gra- dient bound. Corollary | represents extreme case where the value of Qmin makes p reach the

---

Published as a conference paper at ICLR 2024
minimum value of 1. We give empirical ablation study results the effect of the number of local steps in Section 5.2 and Appendix [.I] The ablation study results show that the performance of F FedCompass is not sensitive to the choice of the ratio Q = max Quii and wide range of Q still leads to better performance than other asynchronous Fl. algorithms such as FedBuff.
EXPERIMENTS
5.1 EXPERIMENT SETUP
Datasets. To account for the dataset inherent statistical heterogeneity, we use two types of datasets: (i) artificially partitioned MNIST (LeCun) 1998) and CIFAR- Krizhevsky et al. 2009 datasets, and (ii) two naturally split datasets from the cross-silo FL benchmark FLamby (Ogier du Terrail et al. 2022), Fed-IXI and Fed-ISIC2019. Artificially partitioned datasets are created by dividing classic datasets into client splits. We introduce class partition and dual Dirichlet partition strate- gies. The class partition makes each client hold data of only a few classes, and the dual Dirichlet parition employs Dirichlet distributions to model the class distribution within each client and the variation in sample sizes across clients. However, these methods might not accurately capture the intricate data heterogeneity in real federated datasets. Naturally split datasets, on the other hand, are composed of federated datasets obtained directly from multiple real-world clients, which retain the authentic characteristics and complexities of the underlying data distribution. The Fed-IXI dataset takes MRI images inputs to generate 3D brain masks, and the Fed-ISIC2019 dataset takes der- moscopy images as inputs and aims to predict the corresponding melanoma classes. The details of the partition strategies and the FLamby datasets are elaborated in Appendix [D]
Client Heterogeneity Simulation. To simulate client heterogeneity, let t. be the average time for client to finish one local step, and assume that & follows a random distribution. We use three different distributions in the experiments: normal distribution t; ~ (Vp,, with a = 0 (i.e., homogeneous clients), normal distribution 4 ~ (i,,, with a = 0.3y,, and exponential distri- bution 4; Exp(A). The client heterogeneity increases accordingly for these three heterogeneity settings. The mean values of the distributions (μ or 1/A) for different experiment datasets are given in Appendix E.I Additionally, to account for the variance in training time within each client across different training rounds, we apply another normal distribution ((a))) (L,,, (0.051.) )2) with smaller variance. This distribution simulates the local training time per step for client i in the training round k. considering the variability experienced by the client during different training rounds. The combi- nation of distributions adequately captures the client heterogeneity in terms of both average training time among clients and the variability in training time within each client across diffcrent rounds.
Training Settings. We employ convolutional neural network (CNN) for the partitioned MNIST dataset, and a R8 (He et al. 2016) for the partitioned CIFAR- dataset. For both datasets, conduct experiments with m= (5, 20) clients and the three client heterogeneity settings above, using the class partition and dual Dirichlet partition strategies. For datasets Fed-IXI and Fed- ISIC2019 from FLamby, detailed model architectures and experiment hyperparameters in Appendix E
the default experiment settings provided by FLamby. We list the
5.2 EXPERIMENT RESULTS
Performance Comparison. Table I shows the relative wall-clock time for various FL algorithms to first reach the target validation accuracy on the partitioned MNIST and CIFAR- datasets with different numbers of clients and client heterogeneity settings. Table 2 reports the relative wall- clock time to reach 0.98 DICE accuracy (Dice) 1945) on the Fed-IXI dataset and 50% balanced accuracy on the Fed-ISIC2019 dataset in three heterogeneity settings. The numbers are the aver- age results of ten runs with different random seeds, and the wall-clock time for FedCompass is used as a baseline. A dash 5_" signifies that a certain algorithm cannot reach the target accuracy in at least half of the experiment runs. The dataset target accuracy is carefully selected based on each algorithm's 's top achievable accuracy during training (given in Appendix D Among the beneh- marked algorithms, FedAvg (McMahan et al. 2017) is the most commonly used synchronous FL. algorithm, and FedAvgM (Hsu et al. (209)) is a variant of FedAvg using server-side momentum to address non-lID data. FedAsync (Xie et al. 2019) and FedBuff (Nguyen et al. 2022) are two popular asynchronous FL. algorithms, and F FedAT (Chai et al. 2021 is à tiered FL algorithm. Since the Compass scheduler is separated from global aggregation, making FedCompass com- patible with server-side optimization strategies, we also benchmark the performance of using server- side momentum and normalized averaging (Wang et al. 2020) in FecCoopass s (FedCompassi
7

---

Published as a conference paper at ICLR 2024
Table 1: Relative wall-clock time first reach the target validation accuracy different datasets for various FL algorithms with different numbers of clients and client heterogeneity settings.
Client number
10
20
Method
exp
homo
cap
eap
Fedivg FedAvgg
1.35%
2
4.32x
1.25%
2.10%
5.01x 6.01
1.4%%
4.20%
9.03x
1.27%
2.75x
4.23X
1.50%
2,51x
2.20%
5.36%
13.73x
FadAayna FocRutt
2.15%
2.34x
2.35%
2.17x
1.32%
4.44%
1.32X
MNIST Class
1,30%
1.57x
1.81x
1.58x
1.39
144%
1.37x
1.18%
1.39 x
Purtition (90%))
FedAT
1.36%
2.16X
3.07%
1.13x
1.77%
2.46%
0.97
1.58%
4.32
tediempass
1.0XX
1.00X
1,00X
1.0%
1,00x
1.00X
L00%
1.00
1.00X
F FedCempess
1.10%
1.19X
0,81%
1.88%
0.99
0.81
110%
1.09
1.08%
FedCempess
0.89
1.24x
0,94
1.44%
1,28
0.92
0.94%
1.01%
1.09
TedAvg TedAvgg
0.11x
1.85x
4.90x
1.18x
2.44
5,68
L14x
2.48x
5.94
0.91%
1.85x
4.89
1.22%
2.45
3.83X
121X
2.70x
6.12x
#edAsyne
1.76x
MNIST-DiricMef Partition (90%)
1.86X
181X
149%
2.77x
1.22%
1.29%
2.44X
L.2x
2.83
FndCompass
1.0XX
1.00x
1.00
1,00
1.00
1.00x
1,0x
1.00%
1.00X
TedCompasa IM
0.72%
0.92
0.95X
093x
0.91
0,88
0.87
1.31%
0.81
TedCompasa i
0.92X
x,55
1.26X
0.99
1.12X
0,95%
0.93
0,90%
1.08
FedAvg
x
x
1888
4.18
x
3.00
3.24
7.13x
FecRvgM
2.57x
2.88
9.04
6.9
FedAayne FedDuIE
3.18x
3.07X
5.18%
CIFARIO-Class
1.68%
2.18x
2.47%
1.62%
4.62
Partition (609%)
PeGAT
1.05%
1.42
2.33x
1.21x
1.83
3,21
1,20x
1,23
2.21
FedEempass
1.00X
1.00X
1.00X
1,00x
1.00x
1.00X
L,0x
1.00%
1.00X
TedCompasan
082X
0.82
0.95%
0,99 x
0.78%
0.96%
0.78%
0.81
0.83
red0cmpass+t
0.98
1.18X
0.99
1.22%
1,49X
1.32%
1.19X
1.16x
FadAvg
2.19%
2.81
10.86
4.55%
5.05
11.47%
5,88
5.83
9.05
TedAvgM
2.17x
2.97x
10.77
3.77
11.06x
5.19x
5,44x
8.63
Tedhaync TedBulf FedAl
3.18x
1.70x
5.35x
CIFAR1O-Dirickeer Partition (509)
1.62x
1.99
1.67
2.42%
1.04X
1.69
2.90X
1.36x
1.66X
2.30x
L.45x
1.58x
2.21
FedCompass
PedCompass
1.07%
0.86X
TedCompass
0.98
0.89
1.29
1
0.77
0.87x
1.23x
Table 2: Relative wall-clock time to first reach the target validation accuracy on the Fed-IXI and Fed-ISIC2019 datasets for various FL algorithms in different client heterogeneity settings.
Fed-IXI (0.98)
Fed-ISIC2019 (50%)
Method
homo
normal
exp
homo
normal
exp
FedAvg
TedAvgK
1.14x
2.20x
2.74x
FedAAyne
1.40x
1.31%
1.45%
1.50x
1.75X
1.69X
FeddBuff
1.20x
1.25X
1.38X
2.59%
3.76X
1.03%
PeGAT
1.07
1.30X
1,35x
1,08
1.65X
2.64X
FedCompasa
1.0x
1.00X
1.0xX
1.00X
1.00X
1.00x
TedCompasa IM
1.0x
0.98%
1.02X
2.22
2,02X
2.03x
reddlompas..t
0.98
0.97X
1.03x
1.04X
0.4X
0.97x
DI
PMMCTT Digenerril
2000
200
Saen CRPOREE Norral
DECORATC OWT Expennial
Figure 2: Change in validation accuracy and standard deviation for different FL algorithms on the dual Dirichlet partitioned MNIST dataset and the class partitioned CIFAR-10 dataset with five clients and three client heterogeneity settings. (Synchronous algorithms take the same amount of time, and asynchronous algorithms take the same amount time in the same experiment setting.)
8

---

Published as a conference paper at ICLR 2024
and FedCompass+N), From the table we obtain the following key observations: (i) The speedup provided by asynchronous FL algorithms increases as client heterogeneity increases. (ii) FedAT converges slower client heterogeneity increases due to non-negligible inner-tier waiting time, while FedCompass minimizes inner-group waiting time by dynamic local step assignment and the usage of the latest arrival time. (iii) Similar synchronous FL. where server-side optimizations can sometimes speed up the convergence, applying server momentum or normalized averaging to FedCompass in group aggregation can sometimes speed up the convergence as well. This indi- cates that the design of F FedCompass allows it to easily take advantage of other FL strategies. (iv) Because of client drift and model staleness, FedAsyne and FedBuff occasionally fail to achieve the target accuracy, particularly in settings with minimal client heterogeneity and unnecessary appli- cation of the staleness factor. On the other hand, FedCompass ss can quickly converge all cases, as Compass dynamically and automatically groups clients for global aggregation, reducing client model staleness and mitigating the client drift problem. This shows that FedCompass outper- forms other asynchronous algorithms on heterogeneous non-IID data without any prior knowledge of clients. Additionally, Figure Jillusrattes the change in validation accuracy during the training for different FL algorithms the dual Dirichlet partitioned MNIST dataset (subplots a to and the class partitioned CIFAR-I0 dataset (subplots d to f) with five clients and three client heterogene- ity settings. In the plots, synchronous algorithms take the same amount of time, and asynchronous algorithms take the same amount of time in the same experiment setting. These plots further illus- trate how FedCompass s converges faster than other algorithms and also achieves higher accuracy than other asynchronous algorithms. For example, subplots d and e explicitly demonstrate that FedAsync and FedBuff only converge to much lower accuracy in low-heterogeneity settings, mainly because of client drift from unnecessary staleness factors. More plots of the training process and the maximum achievable accuracy for each FL algorithm are given in Appendix F
/mmax Effeet of Number of Local Steps. We conduct ablation studies on the values of 1/Q Q minn/ max
to investigate its impact on FedCompasa's performance, with results listed in Table 3 From the table, observe that smaller 1/Q values (ranging from 0.05 to 0.2) usually lead to faster conver- gence speed. Additionally, a wide range of 1/Q (ranging from 0.05 to 0.8) can achieve a reasonable convergence rate compared with FedBuff or FedAT, which showcases that FedCompas ss is not sensitive to the value of Q. Therefore, users do not need to heuristically select Q for different client numbers and heterogeneity settings. In the extreme case that significant performance drop for F FedCompass, as Compass loses the flexibility to assign different local steps to different clients. Therefore, each client has its own arrival group, and F FedCompase becomes equivalent to FedAsync. More ablation study results are given in Appendix G.1
1, i.e. Qmin max- there is
Table 3: Relative wall-clock time for FedCompass to first reach the target validation accuracy on the dual Dirichlet partitioned MNIST/CIFAR10 datasets for various values of 1/Q Qmin/ / Qmax.
Client number
10
20
Dataset 1/2
homo
normal
exp
homo
normal
exp
homo
nonmal
exp
0.05 0.8 1.01/0977
0.85/0.76x
0.96/1.5xx
0.97/0.88
18x
1.001.055
I. L.02/0.97x x 0.96/0.00x
M / 0.10
0.91/1.15x 1.05/1.012
0.96/0.98 0.92m.73x
0.95/1.11x
0.85/1.27x
0.97/1.01
1,02/1.04X
0.96/1.01 X
CIFARI0
0.20 1.00/1
00x
1.001 00x
1.00/ x0x
1.00/1.00x 1.00/1000
1.001 x0x00xx
1.00/ 00x
1.00/1000x
1.00/1.00x
Dirichlet
0.40 1.02/1.28x
1.01 _6
1.70/1.36x
1.04/1.0xx
1,28/2.19x
L0000.96
1,25/1.08x
Partition
0.60
1.04/1.23x
1.01/0.99x
183/1 65x
1.000.97
1.01/1.61 x 1919/2552x
0.92/1.11x
1,11/106x
1,16/1,74x
(905/50%)
0.80
1.04/1.33x
1.13/1.242
1.58/1.66 64
0.91/1.32x
1,25/1.91 x 44x
0.86/L33X
1.22/2.95x
1,21/1.64X
1.00
1-78x//
1.68/3.18x
201/1170x
J
2-28x//-
1.29/5.35x
1.76x/-
#edaufs
1.23/162x
1.52/1.99x
1.86/1677
181x/
1.5LX/
1.49/2.42x
2.77xl-
1.22x/-
1.4xX/-
Fedar
1,29/1004 1.97/1.99x 2.08/2.90x
1,08/1.36x
1.70/1666x
2,44/2.30x
1.02/145xX
L83/1.58x
2
6 CONCLUSION
This paper introduces FedCompass, which employs novel computing power-aware scheduler to make several client models arrive almost simultancously for group aggregation to reduce global aggregation frequency and mitigate the stale local model issues in asynchronous FL., F FedCompa s thus enhances the FL training efficiency with heterogeneous client devices and improves the per- formance on non-IID heterogeneous distributed datasets. Through a comprehensive suite of experi- ments, we have demonstrated that FedCompass achieves faster convergence than other prevalent FL algorithms in various training tasks with heterogeneous training data and clients. This new ap- proach opens up new pathways for the development and use of robust AI models in settings that require privacy, with the additional advantage that it can readily leverage the existing disparate com- puting ecosystem.
9

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
The source code and instructions to reproduce all the experiment results can be found in the sup- plemental materials. The details of the classic dataset partition strategies are provided in Appendix DJ and the corresponding implementations are included in the source code. The setups and hyper- parameters used in the experiments are given in Appendix E Additionally, the proofs of Theorem and Corollary I
are provided in Appendix C
ACKNOWLEDGMENTS
This work was supported by Laboratory Directed Research and Development (LDRD) funding from Argonne National Laboratory, provided by the Director, Office of Science, of the U.S. Department of Energy under Contract No. RE-ACC2-06CHHI 1357. This research is also part of the Delta research computing project, which is supported by the National Science Foundation (award OCI 2005572), and the State of Illinois. Delta is joint effort of the University of Illinois at Urbana-Champaign and the National Center for Supercomputing Applications. E.A.H. was partially supported by National Science Foundation awards OAC-1931561 and OAC-2209892.
REFERENCES
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, et al. Towards federated learning at scale: System design. Proceedings of Machine Learning and Systems, I: 374-388, 2019.
Zheng Chai, Yujing Chen, Ali Anwar, Liang Zhao, Yue Cheng, and Huzefa Rangwala. FedAT: A per--performacc and communication-eeie effficcinn federated learning system with asynchronous tiers. In Proceedings of the International Conference for High Performance Computing, Network- ing, Storage and Analysis, pp. 1-16, 2021.
Yang Chen, Xiaoyan Sun, and Yaochu Jin. Communication-efiee
federated deep learning with layerwise asynchronous model update and temporally weighted aggregation. IEEE transactions neural networks and learning systems, 31(1))42229 4238, 2019.
Yujing Chen, Yue Ning, Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In 2020 JEEE International Conference on Big Data (Big Data), pp. 15 24. IEEE, 2020.
Zheyi Chen, Weixian Liao, Kun Hua, Chao Lu, and Wei Yu. Towards asynchronous federated learn- ing for heterogeneous edge-pout powered internet of things. Digital Communications and Networks, (3):317-326, 2021.
Özgün Çiçek, Ahmed Abdulkadir, Soeren Lienkamp. Thomas Brox, and Olaf Ronneberger. 3D U- Net: learning dense volumetric segmentation from sparse annotation. In Medical Image Comput- ing and Computer-Assisted Greece, October 17-21, 2016, Proceedings, Part 11 19, pp. 424 432. Springer, 2016.
Dntevention-MICCA. 2016: 19th International Conference, Athens,
Noel CF Codella, David Gutman, M Emre Celebi. Brian Helba, Michael A Marchetti, Stephen W Dusza, Aadi Kalloo, Konstantinos Liopyris, Nabin Mishra, Harald Kittler, et al. Skin lesion anal- ysis toward melanoma detection: A challenge at the 2017 international symposium on biomedical imaging (ISBI), hosted by the international skin imaging collaboration (isic). In 2018 IEEE 15th international symposium on biomedical imaging (ISBI 2018), pp. 168-172. IEBE, 2018
Mare Combalia, Noel CF Codella, Veronica Rotemberg, Brian Helba, Veronica Vilaplana, Ofer Reiter, Cristina Carrera, Alicia Barreiro, Allan C Halpern, Susana Puig, et al. Bcn20000: Dermo- scopic lesions in the wild. arXiv preprint arXiv: 02288, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE conference on Computer Vision and Pattern Recognition, pp. 248-255. Ieee, 2009.
10

---

Published as a conference paper at ICLR 2024
Lee R Dice. Measures of the amount of ecologic association between species. Ecology, 26(3): 297-302, 1945.
Jiangshan Hao, Yanchao Zhao, and Jiale Zhang. Time efficient federated learning with semi- asynchronous communication. 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS), pp. 136-163, JEEE, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on Computer Vision and Puttern Recognition, pp. 770-778, 2016.
Trung-Hise Hieu Hoang, Jordan Fuhrman, Ravi Madduri, Miao Li, Pranshu Chaturvedi, Zilinghan Li, Kibaek Kim, Minseok Ryu, Ryan Chard, EA Huerta, et al. Enabling end-to-end secure federated learning biomedical research on heterogeneous computing environments with appfix. arXiv preprint arXiv:2312.087000 2023.
Samuel Horváth, Maziar Sanjabi, Lin Xiao, Peter Richtárik, and Michael Rabbat. Fedshuffle: Recipes for better use of local work in federated learning, arXiv preprint arXiv:2204.131 2022.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint (rXiv:1909.06335 2019.
Ahmed Imteaj and M Hadi Amini. Fedar: Activity and resource-aware federated learning model for distributed mobile robots. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 1153-1160. IEEE, 2020.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Ad- vances and open problems in federated learning, Foundations and Trends@ in Machine Learning, 14(1-2):1-210 2021.
Georgios Kaissis, Alexander Ziller, Jonathan Passerat-Palmbadd Théo Ryffel, Dmitrii Usynin, An- drew Trask, Ionésio Lima Jr, Jason Mancuso, Friederike Jungmann, Marc-Matthias Steinborn, et al. End-to-end privacy preserving deep learning on multi-institutinall medical imaging. Nature Machine Intelligence, 3(6):473-488) 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMLR, 2020.
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:1610.05499 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
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 on non-iid data. arXiv preprint 1rXiv:1907.0221 2019.
Zilinghan Li, Shilan He, Pranshu Chaturvedi, Trung-Hieu Hoang, Minseok Ryu, EA Huerta, Volodymyr Kindratenko, Jordan Fuhrman, Maryellen Giger, Ryan Chard, et al. APPFLx: Providing privacy-pres preecc-preseriiggg cross-silo federated learning as a service. arXiv preprint arXiv:2308. 08786, 2023.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 1710 2017.
11

---

Published as a conference paper at ICLR 2024
Xiaodong Ma, Jia Zhu, Zhihao Lin, Shanxuan Chen, and Yangjie Qin. A state-of-the-an survey solving non-iid data in federated learning. Future Generation Computer Systems, 135:244-258, 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--fficeentt learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Jed Mills, Jia Hu, and Geyong Min. Communication--fficieee federated learning for wireless edge intelligence in loT. IEEE Internet of Things Journal, 7(7):5966-5994 2019.
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.
Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In 2C19-21-0119 IEEE international Conference on Communications (ICC), pp. 1-7. IEEE, 2019.
Jean Ogier du Terrail, Samy-Safwar Ayed, Edwige Cyffers, Felix Grimberg, Chaoyang He, Regis Loeb, Paul Mangold, Tanguy Marchand, Othmane Marfoq, Erum Mushtaq, et al. Flamby: Datasets and benchmarks for cross-silo federated learning in realistic healthcare settings. Ad- vances in Neural Information Processing Systems, 35:5315-5334, 2022.
Sarthak Pati, Uijwal Baid, Brandon Edwards, Micah Sheller, Shih-Han Wang, G Anthony Reina, Patrick Foley, Alexey Gruzdev, Deepthi Karkada, Christos Davatzikos, al. Federated learning enables big data for rare cancer boundary detection. Nature Communications, 13(1): 2022.
Fernando Pérez-García, Rachel Sparks, and Sébastien Ourselin. Torch1O:
Python library for effi- cient loading, preprocessing, augmentation and patch-based sampling of medical images in deep learning. Computer Methods and Programs in Biomedicine, 208:1062366 2021.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295. 2020.
Amirhossein Reisizadeh, Isidoros Tziotis, Hamed Hassani, Aryan Mokhtari, and Ramtin Pedarsani. Straggler-resilient federated learning: Leveraging the interplay between statistical accuracy and system heterogeneity. IEEE Journal on Selected Areas in Information Theory, 3(2):197-205, 2022.
Minseok Ryu, Youngdae Kim, Kibaek Kim, and Ravi K Madduri. APPFL: open-source software framework for privacy-preserving federated learning. In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 1074-1083. IEEE, 2022.
Jinhyun So, Ramy E Ali, Başak Güler, and A Salman Avestimehr. Secure aggregation for buffered asynchronous federated learning. arXiv preprint arXiv:2110.02177, 2021. 2021.
Sebastian U Stich. Local SGD converges fast and communicates little. arXiv preprint 1705007805.09767. 2018.
Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural net- works. In International conference on Machine Learning, pp. 6105-61 14. PMLR, 2019.
Philipp Tschandl, Cliff Rosendahl, and Harald Kittler. The HAM10000 dataset, large collection of multi-source dermatoscopic images of common pigmented skin lesions. Scientific data, 5(1): 1-9, 2018.
Guan Wang. Interpret federated learning with shapley values. arXiv preprint arXiv:1905.04539 2019.
Guan Wang, Charlie Xiaogian Dang, and Ziye Zhou. Measure contribution of participants in fed- crated learning. In 2019 IEEE international conference on Big Data (Big Data), pp. 2597-2604. IEFF, 2019.
12

---

Published as a conference paper at ICLR 2024
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 13:7611-7624 2020.
Qizhao Wang, Qing Li, Kai Wang, Hong Wang, and Peng Zeng. Efficient federated learning for fault diagnosis in industrial cloud-edge computing. Computing, 103(10):2319-333) 2021.
Wentai Wu, Ligang He, Weiwei Lin, Rui Mao, Carsten Maple, and Stephen Jarvis. SAFA: A semi- asynchronous protocol for fast federated learning with low overhead. IEEE Transactions on Com- puters, 70(5):655-668 2020.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint 1rXiv:1903.03394, 2019.
Chenhao Xu, Youyang Qu, Yong Xiang, and Longxiang Gao, Asynchronous federated learning on heterogeneous devices: survey, arXiv preprint urXiv:2109.04269 2021.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted with faster convergence and less com- munication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. Interna- tional conference on machine learning, pp. 7252-7200 PMLR, 2019.
Yu Zhang, Morning Duan, Duo Liu, Li Li, Ao Ren, Xianzhang Chen, Yujuan Tan, and Chengliang Wang. CSAFL: A clustered eemi-asyncronous federated learning framework. In 2021 Interna- tional Joint Conference Newral Networks (IJCNN), pp. 1-10. IEEE, 2021.
13

---

Published as a conference paper at ICLR 2024
A DETAILED IMPLEMENTATION OF FEDCOMPASS
Table lists all frequently used notations and their corresponding explanations in the algorithm description of FedCompass.
Table 4: Summary of notations used in algorithm description of FedCompass.
Notation
Explanation
client information dictionary arrival group information dictionary index of the arrival group for client number of local steps for client estimated computing speed for a client start time of current local training round for client list of non-arrived clients for an arrival group list of arrived clients for an arrival group expected arrival time for an arrival group latest arrival time for an arrival group current time
G
G
Q
Tann
CL
ACL
Ta
max
now
Quax
maximum number of local steps for clients minimum number of local steps for clients latest time factor client learning rate total number of communication rounds batch size for local training staleness function
Qmin
ME
N
B
s(()
timestamp of the global model that a client trained on timestamp of the global model
T
Pi
importance weight of client the difference between the original model and the trained model of client i client update buffer for group g general client update buffer
A
A
A
w
global model local model of client after local steps
Wi.g
Compass utilizes the concept of arrival group determine which clients are supposed arrive together. To manage the client arrival groups, Compass employs two dictionaries: C for client information and & for arrival group information. Specifically, for client Cúi (ttt).G,C(i [C[[(]Q. .Q, C [t].S, and C [i] .Taat represent the arrival group, number of local steps, estimated computing speed (time per step), and start time of current communication round of client C .T represents the timestamp of the global model upon which client trained (i.e., client local model timestamp). For arrival group g. 9 [g] .CL, 9 [g] AACL, [[g] .Ta and G [g] .Tmax represent the list of non-arrived and arrived clients, expected arrival time for clients in the group, and latest arrival time for clients in the group. According to the client speed estimation, all clients in group g are expected to finish local training and send the trained local updates back the server before G [g] ..,,, however, to account for potential errors in speed estimation and variations in computing speed, the group can wait until the latest arrival time G [[g] .Tmax for the clients to send their trained models back. The difference between g [g] .Taax and the group creation time is À times longer than the difference between g [g] .T and the group creation time.
Algorithm presents the process through which Compass assigns client to an arrival group. The dictionaries and G along with the constant parameters Qmax, Qmins and À are assumed to be available implicitly and are not explicitly passed as algorithm inputs. When Compass assigns client to group. it first checks whether can join an existing arrival group (function JOINGROUP, lines 5 to 16). For each group, Compass uses the current time, group expected arrival time, and estimated client speed to calculate tentative local step number (line 8). To avoid large disparity in the number of local steps, Compass uses two parameters Qmax and Quia specify valid range of local steps. If Compass can find the largest q within the range [Qmin Qmax]. it assigns the client to the corresponding group. Otherwise, Compass creates arrival group for the client. When
14

---

Published as a conference paper at ICLR 2024
Algorithm 2: ASSIGNGROUP
Function ASSIGNGROUP(): Input: Client id if JOINGROUP(i) False then
CREATEGROUP());
Function JOINGROUP()): Input: Client id
Initialization: Gassign: Qassign == -1,1-,1 -1;
for g E 9 do
q = (9 [g] Ta - Tow [cC
q Qiin and q 2 Qassign and 9 I max then
10 L Gassign; Qussign = 9, qi
Gassign # -1 then 11
12
[[i).(G, Q, Tsmn) = aassign Qassign Tno );
13
[Lg).CL.ador (i);
14
refurn True;
else
16
return False
17
Function CREATEGROUP()) Input: Client id
19 Initialization: Qussign == 11;
for g E 9 do
21
now < 9 [g].T, then speed of the fastest client in group gi Texp= = g [g] .Ta + S maxi
22
23
ussign == max (aasiQusignn [(Texp Toow (tow)/C(t].S))
24
25
Qaisign Z and Qassign Qmin then
26
Qassign = Q Qmii
27
else
28
if Qaesign < 0 or Qaisign Qiax then
L Qussign == Q maxi
29
30
Gnew := a unique id for the new group;
G [Gnew] 1. I.CCL, ACL) == ([i), (1);
12 [[Gnww To = Toom + Qussign * C[i].S:
[Gnew]] T.Tmaxx max == Tno
Qessign C(t) [ X;
34 C [[]--GG Q, T stam)) := (Gnew: Quesign: T Tnow):
Add timer event [Geww] .Tmax invoke GROUPAGGREGATTE Gnew);
Algorithm 3: GROUPAGGREGATE Algorithm
Function GROUPAGGREGATE(()
Input: group index g
g E g then
Ag Σ; A T=
sort G GAC] from fastest client to slowest client;
for i [g].ACL do
C(i).T:= Tgi ASSIGNGROUP)): CECCOMPASS-CLIENTTE C()) QQ, me. B);
creating this new group, Compass aims to ensure that specific existing arrival group join the newly created group for group merging once all its clients have arrived, as described function CREATEGROUP (lines 18 to 35). To achieve this, Compass first identifies the computing speed S of the fastest client in group g. It assumes that all clients the group will arrive at the expected time g [g] .T and the fastest client will perform Quax local steps in the round. Subsequently,
15

---

Published as a conference paper at ICLR 2024
Compass utilizes the expected arrival time in the next round (line 23) to determine the appropriate number local steps (line 24). It then selects the largest number of local steps while ensuring that it is within the range min: Qmxx] In cases where Compass is unable to set the number of local steps in a way that allows any existing group to be suitable for joining in the next round, it assigns Qmax to the client upon creating the group. Whenever a group is created, Compass sets up a timer event to invoke the GROUPAGGREGATE function (Algorithm 3 to aggregate the group of client updates after passing the group's 's latest arrival time 9 [[g] max. In GROUPAGGREGATE, the server updates the global model using the group-specifie buffer A containing updates from clients in arrival group 9, and the general buffer A, containing updates from clients arriving late in other groups. After the global update, the server updates the global model timestamp and assigns new training tasks to all arriving clients in group g.
B UPPER BOUND ON THE NUMBER OF GROUPS
If the client speeds do not have large variations for sufficient number of global updates, then FedCompass can reach an equilibrium state where the arrival group assignment for clients is fixed and the total number of existing groups (denoted by #g) is bounded by [logg /l), where Q maxx mmiin and j is the ratio of the time per local step between the slowest client and the fastest client.
Consider one execution of FedCompass with list of sorted client local computing times (Ti, T2. J. where T, represents the time for client i to complete one local step and T, S T {1.....0 ,91 be the first group of clients. Then all the clients E G1 will be assigned to the same arrival group at the equilibrium state with
< j. Let 91 = {i TI Quin
Qmax
Q: = 4. Qmax E 1Q 1mi max)] Similarly, if 9i < m, we can get the second group clients G2 {i Tos Qmax {9r + 1,.... 92 where the clients in G2 will be assigned another arrival group at the equilibrium state. Therefore, the maximum number of existing arrival groups at the equilibrium state is equal the smallest integer such that
Qmiu
Q max
#* =Q
T
# < [logg u1.
Q
Additionally, this implies that the maximum ratio of time for two different clients to finish one communication round at the equilibrium state is bounded by μ Uo08 #1 First, we can assume that the maximum ratio of time for two different clients to finish one communication round is the same as that for two different arrival groups to finish one communication round. In the extreme case that there are maximum [logo μu] arrival groups. Then the time ratio between the slowest group and fastest group is bounded by Q [log w1
Q Ulog a.
16

---

Published as a conference paper at ICLR 2024
C FEDCOMPASS CONVERGENCE ANALYSIS
C.I LIST NOTATIONS
Table
lists frequently used notations in the convergence analysis of FedCompass.
Table 5: Frequently used notations the convergence analysis of FedCompass.
Notation
Explanation
m
total number of clients
Te
client local learning rate
L
Lipschitz constant
j
ratio of the time per local step between the slowest client and the fastest client bound for local gradient variance
di
dg
bound for global gradient variance bound for gradient
min
minimum number of client local steps in each training round maximum number client local steps in each training round ratio between max and Qmin i.c., Qmax/ mmax//Qmin min number of local steps for client i in round
Q max
Q
Qie
to(()
global model after global updates local model of client i after q local steps, where the original model has timestam Ti.t
wag (l-Tu,))
Big
random training batch that client uses in the q-th local step global loss for model w client i's local loss for model w loss for model w evaluated gradient of global loss w.rt. w gradient of client i's local Ioss w.r.t.
F(w)
(.(w)
fi Bi)
batch B; from client
VF(W)
VF(w))
V fi(W, B.)
gradient of loss evaluated on batch B, w.r.t. w set of arriving clients at timestamp
S.
(c-T),))
update from client at timestamp trained on global model with staleness Tie aggregated local updates from clients for updating the global model at timestamp
A (1)
C.2 PROOF OF THEOREM M
Lemma 1. E [V B)) s 3(o + o +M) for any model w.
Proof of Lemmal
7
E [V,
= fi -
3E [ B,) VF [V((w v
<
300 + MM,
(4)
where step (a) utilizes Cauchy-Schwald inequality, and step (b) utilizes Assumption
Lemma 2. When a function F R + IR is Lipschitz smooth, then we have
L F(w') < F(w) (VF(w), w' w) + 2 11 w|l
(5)
Proof of Lemma
17

---

Published as a conference paper at ICLR 2024
Let we t(w' w) for t [0, 1]. Then according to the definition of gradient, we have
F(w') F(w) + / (VF(w:), wwdtt
F(w) + (VF(w), w/ - -w)+ ('" (VF(w)) VF((), w' w)dt
SF(w) + (VF(w), w/ - -w) + {-² [VF((;;) - VF(w)] ||w' - wildt
(6)
2 F(w) + (VF(w), w/ - w) + L {/¹ ||u, w|l 1111'0'- w llt
F(w) (VF(w), w/ w) Lll w 1 ( tdt
F(w)) + (VF(w), w' w) + 2 l/w w11
where step (a) utilizes Cauchy-Schwarz inequality (u, v) - 1u,, w8)l s ||u]
||u|], and step (b)
utilizes the definition of Lipschitz smoothness.
Proof of Theorem
According to Lemma
2
we have
F(w(t+1)) F(w(()) + (VF(w(()), w((+)) -w0())
L
F(wll)) - (VF(w)()) 1'0) 1 111
F(wl(t)
1 Σ (F( 1/ ((
+
L
k
(1-T
ct
2
2m
RES.
ke..
Pg
where S₁ represents the set of clients arrived at timestamp t, and A (t-Tw,) represents the update from client trained on the global model with staleness Te.t. Rearranging part Pt.
Q
P1 = E (VF(w())), (1-Ta A = 7e Σ (F KES.
Vill
(t-Ta)) ,Bku)).
RES.
Q=0
(8)
where Qk,i represents the number of local steps client ie has taken before sending the update the ((-Tx.+) represents the model of client k in local step g. and BR.g represents upper bound for the ex-
server timestamp Wk.9
random training batch that the client & uses in local step q. To compute
pectation part Pt, we utilize conditional expectation: E[P.] = En E [x) E ( (0~[m))H (P.). Specifically. Ex is the expectation the expectation over the random group of clients arriving at timestamp t, and EB, (1) (m] i8 the expectation over the mini-batch stochastic gradient client i.
the history 7. of iterates up to timestamp E [[]m[m]]
18

---

Published as a conference paper at ICLR 2024
Q
B
T
E
VF(W())
Vfn(wha
(t-Tm.)) Bu.a))
KES,
Qu.11
(
L E
VF(w(()) (F VF
KES.
Q
E
Σ
(IVF -
VF(w((1)) - Tm 113]
2m
KES:
Q
E
Σ
Σ
[V
( )1)
2m
kES,
172
Qaa-1
Σ
[17
1V VR(WW m2)) )1))
T
2m
Q
E
Σ
Σ
)
2m
keS;
9=0
DEP EEH
m
Q
VV
2m
q=0
neP
M
En
[VF(w())
V (w f0
2m
9=0
Qt,r- Σ
T)t E
Σ
/V kgg
112]
2m
kES,
m
Qaa-1
T]t E&
Σ
(1
T
2m
m
NE Ex
Σ n
(VF - V (w (1
2
Q
Ue
Σ KES.
Σ
( k.g [1
2m
where step (a) utilizes Assumption 2 step (b) utilizes the identity (u, e) $ ([|ua]² + |||||2 ||u 2)(2), and step (c) utilizes conditional expectation with the probability of client i to arrive at timestamp We let P
Σ ग. E m]] and T/ := T such that Σ =
To derive the upper and lower bounds of nτ, according to the conclusion get in Appendix B
have / S @ [1 lower bounds of T. as follows.
n¹, i.e. T'in 2 #² m Therefore, we can derive the upper and
1 / -
1
Σ
max + (m 1) 2 xmxx +
(10)
Tt' max
<
+ m-1
#
19

---

Published as a conference paper at ICLR 2024
1
3 min +mm
m)
Tiin p'mm 1)
i=
(11)
1
Tinn 2
1 1 p' 1))
Let 71 =1
and 7/2
+ p0 - 1). We have TT
[ 11 Then,
Qui
E[P]] S
Ti Qmin
E
|VF [V(
me
E
Σ
IV (u (w
272
2m
KES.
g=0
(12)
+
M18
En
Σ
[VF(w())
(u Te,) ||
2
2m
g
F
For part Ps. by utilizing Assumption
we can get
P3 BN
I (V((()) V (1- 113]
271
i=1
Q=0
Quaa
Me EM
Σ
(VF((w()) - VF: (2 + VV F (wi((-Tae)) V (w )
)
71
1m1
9=0
neLL
Qmax
(Iw(() - 10 + (t= - wig 71)0)))))))))
<
EH
(13)
For (l (o.t 1|2, we derive its upper bound in the following way, with step (a) utilizing Cauchy-Schware inequality and step (b) utilizing Lemmal) [
(l - w1 11
(wipt() - -woo)) (
A
(k.))
p t T2.t
KeSp
2
V (u (o Thind Blig)
m²
Te. KES,
q=0
(14)
Quw
1/ Tiaxx Q Quax
Vielwke Bra))l
m
p SES,
9=0
(b)
< 311 max Pena lof + 02 + M)
2-2
For (t-a))
((-Ta,e) 1|2, we derive its upper bound also using Lemma 1
wag
[ wig
(1-m.)) 1= n2 Σ Vill (t
Biell| < Qu (o + +0 + M)
(15)
Combining equation 14 and equation 15
we can obtain the upper bound of Ps:
3mL2mIQ2
Qi (T + +) + o M).
P3 <
(16)
71
20

---

Published as a conference paper at ICLR 2024
Putting the upper bound of Ps (equation 16 into equation 12
get:
Q
B|P S
[VF(W(())
The
Σ
||3
272
2m
RES,
q=0
(17)
3mL I
2
max
(F + 1)(o} + tog + M).
7/
To compute the upper bound for the expectation of part P2, similar Pl, we also apply conditional expectation: E[P2] = Ex (mm
B[P]]
2m1²" E
A (t Fand)
||
2
E
Q
(t (t-T
BBaill Buall
2m
S.
KES,
9=1
Qu
Qu.-1
E 2mn
ni L
V (i (1
(K-Tx.)) BBEA) VV (T
+ Σ
V (u ((-
SES,
RES.
Q
(8) n/2 L
Vi (t-T(,)) BBa) - V.F(
||
EH
m
L
( 12]
E
(w
m²
KES
T/ LP2
EH
Σ
Vi((W
(4-T4.) Beo)) - -FF((u
m
m L m2
(iicwul 122
E
Σ KES,
Σ
m Q
T2 EA
Vi (
(e-Ta.) Bia)) V (w (w(tt)))))
77
L
F (w (1T 2
m²
KES,
9=0
(b)
min LQ max
Vi (8-7),)) BBn)) V V. (1)())) 19
E
7,
Q
n L
E
Σ KES.
Σ
m²
9=0
( m Mi of LQ of 2
n2L L m
E
Σ
( (1((((
7
KES,
P3
(18)
where step (a) utilizes conditional expectation and Cauchy-Schwar inequality, step (b) utilizes Cauchy-Schwarz inequality, and step (c) utilizes Assumption
To find the upper bound of E[P, + Pa), we need to make sure that Pa + P3 < so that we can eliminate these two parts when evaluating the upper bound. The following step (a) employs Cauchy-
21

---

Published as a conference paper at ICLR 2024
Schwarz inequality.
P4+
P5
T]e
E
Qu.--1
( }13}
MZL m²
Qu
V (u
(c-
2m
KES,
kES, q=0 0
QU,11
Que
ne E
Σ KES:
VF (
ne IQuux max E
V (o 11
2m
m
Q=u
KEE. 9=0
1i
LQ
max
E
[VVE (1)
0o
m
2m
KES.
9=0
(19
Therefore, we need to have m) S 2LQmux we have
In such cases, combining equation 17 and equation
18
E| { Qmiu (VV((w()))))))
m² mz o7 LQO max
272
(20)
3mL 2 max
+
(F + 1)(o +0 MM).
71
Summing up & from 0 to T - 1, we can get
Qiiu
(w))((())) [P]
m2 m²n1207 LQ T
E
2/22
3mL m/ Qū Quaax T (T + +1) + oo M)
71
(21)
(F(w())) - -F(w")) + oz T.Q max T
7
3mL? 3mI?n1 Qinax (F + 1)(o} + oz + M).
Therefore, we obtain the conclusion in Theorem
1
[IV
272
(( F(wx))
2r of LQ Luax
T
ne Quin T 6)2mnn L2 Y1 Qumin
77Q min
(22)
max (T + +) + 0g + M)
Proof of Corollary y
When Qmiu I Qmax/ Hu, then μ S
= Q. Therefore, n' = Q llog M1 Ø" = 1.
(23)
Consequently, 71 = =1 m-1 and の² = of + 03 + M, equation 22 can be written as
N¹ 72 = 1 + μ (m
Letting F" = F(w(()) F(w")
2mF Qmini
2meo LQ maxx
om L2Q2 max
B 1=0
F (w) |13
(1 + 1). (24)
Qmin
Q miin
If choosing ne Q11/Q VT) and considering Qmax and Quin having the same order in the O-class estimation, we can derive the conclusion of Corollary D
T
=
moi
m miiax 222
min [
V
((
E IVF
<0
+ O
+
vT
vT
T
(25)
22

---

Published as a conference paper at ICLR 2024
D DETAILS OF THE EXPERIMENT DATASETS
D.1 CLASSIC DATASET PARTITION STRATEGY
To simulate data heterogeneity the classic datasets, we employ two partition strategies: (i) class purtition and (ii) dual Dirichlel partition, and apply them both MNIST (LeCun) 1998) and CIFAR-10 10 (Krizhevsky et al. 2009) datasets. These two datasets are the most commonly used datasets in evaluating FL algorithms (MNIST is used in 32% cases and CIFAR-10 is used in 28% cases) (Ma al. 2022). The details of these two partition strategies are elaborated in the following subsections.
D.1.1 CLASS PARTITION
Algorithm 4: CLASSPARTITION
Data:
Classic dataset D, sample indices for different classes class_indien -indices, number of clients m, total number of distinct classes minimum and maximum number of sample classes for each client split minn and Rmax. mean value of the normal distribution μa, standard deviation of the normal distribution a.
client datasets diientdosaseess = {i: [] for i E m|} Return value: local datasets for each client;
repeat
== 0 For a certain class, which client(s) have samples of that class in its client split:
for i [1, m do
n. := randint (Mmin Rmax)
classes; == raanppermutaaioe (n) [=n:];
for c E classes; do
class_partie citssspartition(e == [i] if e & class partststoiiionn else class carssssprttiinn [c] .add(i);
until Ien (class ) T
10
for e E class- parrtition do
n₂ normal (mean=ju, std=o, size=len (class catiusssprtttionttt [c] ));
12
nh == (n./sum (n.,) * len (class indices [c] > Number of samples with class e for
each assigned client;
for num,, i E zip (M,, class_pare class_perlition [c]) do
13
14
Add num samples of D with distinct indices from classes_indices [c] to client datasets [
15 return client_datseed
Algorithm 4 outlines the process of class partition, which partitions classic dataset into several client splits such that each client split has samples from only a few classes. Many previous re- search works partition the classical dataset in a similar way artificially create non-IlI federated datasets (McMahan et al.] 2017] Chen et af.] 2019). To partition a dataset D, we first obtain a dictionary class_ siassinndiees that contains the indices of samples belonging each class. Namely, Mass_indices [c] represents the indices of all samples in D with class c. Lines 2 to 9 of the algorithm assign each client with n; classes for its own client split, where n,; [Mmius R'max] Additionally, the algorithm ensures that each sample class is assigned to at least one client split. Subsequently, from lines 10 to 14, the algorithm determines the number of samples of class e that each assigned client split should have based on normal distribution, and then assigns the corre- sponding number of data samples to the respective clients. The class partition strategy results in imbalanced and non-IID FL datasets, with clients having varying sample classes within their local datasets.
In the experiments, the mean value of the normal distribution μ 10, and the standard deviation o = 3. Both the MNIST and the CIFAR-10 10 datasets have 10 distinct classes, namely, n = 10. When the number of clients and mm = Figure GJsoww a sample class distribution generated by the class partition strategy among 10 clients with Amnin 3, Amax 5, and 10.
5, 7minn
and 1mmax 6, when
10 20, nuin =
23

---

Published as a conference paper at ICLR 2024
Figure 3: Sample class distribution generated by the class partition strategy among ten clients.
D.1.2 DUAL DIRICHLET PARTITION
Algorithm 5: DUALDDRICHHEETPRRTTTII
Data: Classic dataset D, sample indices for different classes class indices, number of clients m. total number of distinct classes n,, two concentration parameters on and o2 for Dirichlet distributions.
client_dotasets == {i: [] for i [L. Return value: local datasets for each client;
P1 == [1/m for E m]] &o Prior distribution for the number of samples for each client;
P2 [len iidassiindies [c] for e Rlss_indiee
P2 [p/sum (P2) for E P2] > Prior distribution for the number of samples for each class;
01 = ai * *P1:
p2:
7 client_wts := dirichlet (01) > Normalized number of samples for each client, shape is
R" sum is 1;
class wts == ri sarrchhett (02, si ze=m) b Normalized number of samples for each class within each client, shape is Rmxx, row sum is 1;
for i E 11 ml do
for c E [1. do
10
l
num: dlient_wss[]] class_ sateswwsssss [c]c] * *len Add num samples of D with distinct indices from classes_indiee [c] to client datasets [
(client_/ (aussslss[;.).)
12
13 return client_datasee _datasess
Some prior works that model data heterogeneity also employ a Dirichlet distribution to model the class distribution within each local client dataset (Yurochkin al. 2019; (ssu et al., (019). We ex- tend the work others using two Dirichlet distributions, with details outlined in Algorithm 5 The first Dirichlet distribution uses concentration parameter on and prior distribution pı generate the normalized number of samples for each client, client_wts E Th The second Dirichlet distribution uses concentration parameter ag and prior distribution P2 generate the normalized number of samples for each class within each client, class_wts wts E Rmxxn, From lines 9 to 12, the algorithm combines client. wts, class class_wts, and the total number of samples for class calculate the num- ber of samples with class to be assigned for each client, and assigns the samples accordingly. In summary, the dual Dirichlet partition strategy employs two Dirichlet distributions to model two lev- els of data heterogeneity: the distribution across clients and the distribution across different classes within each client. Therefore, the generated client datasets are imbalanced and non-IID, which more accurately reflect world federated datasets.
In the experiments, we set a = m and ag = 0.5. The concentration parameter a governs the similarity among clients or classes. When - oo, the distribution becomes identical to the prior distribution. Conversely, when a - 0, only one item selected with a value of while the remain- ing items have value of O. Since concentration parameter 02 has very small value, each client has data samples from only few classes. Figure illustrates a sample class distribution generated by the dual Dirichlel partition strategy among m 10 clients, where 10, on 10, and 02 0.5.
D.2 NATURALLY SPLIT DATASETS: FLAMBY
FLamby is open-source suite that provides naturally split datasets specifically designed for benchmarking cross-silo federated learning algorithms (Ogier du Terrall et al., (2022). These datasets sourced directly from distributed real-world entities, ensuring that they preserve the
24

---

Published as a conference paper at ICLR 2024
Figure 4: Sample class distribution generated by the dual Dirichlet partition strategy among ten clients.
authentic characteristics and complexities of data distribution in FL. our study, we selected two medium-sized datasets from FLamby Fed-IXI, and Fed-ISIC2019 evaluate the performance of FedCompass and other Fl. algorithms the experiments. The two datasets offer valuable per- spectives into two healthcare domains, brain MRI interpretation (Fed-IXI), and skin cancer detection (Fed-ISIC2019), By leveraging these datasets, our goal is to showcase the robustness and versatility of F FedCompass across diverse machine learning tasks in real-world scenarios. Table 6 provides the overview of the two selected datasets in FLamby. Detailed descriptions of these datasets are provided in the following subsections.
Table 6: Overview of the two selected datasets in FLamby.
Dataset
Fed-IXT
Fed-ISIC2019
Inputs
Tl weighted image (TIWI)
Dermoscopy Classification Melanoma class
Task type
3D segmentation Brain mask
Prediction
Client number
Model
3D U-net U-net(Ciçek et al. DICE (Dice 1945
2016
EfficientNet( & Le 2019 Balanced accuracy 200 200 9GB
Metric
Input dimension
48 60 48
Dataset size
444MB
D.2.1 FED-IXI
The Fed-IXI dataset is sourced from the Information eXtraction from Images (IXI) database and in- cludes brain TI magnetic resonance images (MRIs) from three hospitals (Pérez-Garcia et al.) 2021) These MRIs have been repurposed for a brain segmentation task; the model performance evalu- ated with the DICE score (Dice 1945). To ensure consistency, the images undergo preprocessing voxels, and sample-wise intensity normalization. The 3D U-net (Çiçek et al. 2016) serves as the baseline model for this task.
steps, such as volume resizing to 48 60
D.2.2 FED-ISIC2019
The Fed-ISIC2019 dataset is sourced from the ISIC2019 dataset, which includes dermoscopy im- ages collected from four hospitals (Tschandl et al. 2018 Codella et al. 2018 Combalia et al. 2019). The images are restricted to a subset from the public train set and are split based on the imaging ac- quisition system, resulting in 6-client federated dataset. The task involves image classification among eight different melanoma classes, and the performance is measured through balanced accu- racy, Images are preprocessed by resizing and normalizing brightness and contrast. The baseline classification model is an EfficientNet (Tan & Le 2019) pretrained on ImageNet (Deng et al. 2009).
E EXPERIMENT SETUP DETAILS
All the experiments are implemented using the open-source software framework for privacy- preserving federated learning (Ryu et al. 2022 Li et al. 2023).
E. DETAILS OF CLIENT HETEROGENEITY SIMULATION
When simulating the client heterogeneity, we consider the average time t, required for client to complete local step. We assume that 4 follows a random distribution P. namely, 1, P(t). In
25

---

Published as a conference paper at ICLR 2024
experiments, employ three different distributions to simulate client heterogeneity: the normal distribution t; ~ _N,,, with o = 0 (i.e., homogencous clients), the normal distribution t, ~ (²) with = 0.3y, and the exponential distribution f; Exp(A). The exponential distribution models the amount of time until a certain event occurs (arrival time), specifically events that follow Poisson process. The mean values of the distribution (n1 1/A) adjusted for different datasets according to the size of the model and training data. Table 7 presents the mean values of the client training time distribution for different datasets used in the experiments. Furthermore, Figure illustrates the distribution of the training time to complete one local step among 50 clients under normal distribution with 0.3p and exponential distribution, both with a mean value of 0.15.
Table 7: Mean values of the training time distribution for different datasets.
Dataset Name
Batch Size
Mean (μ or 1/A)
MNIST
64
0.15s
CIFAR-10
128
0.5s
Fed-IXI
2
0.8s
Fed-ISIC2019
64
1.5s
12
Fuqqurcc 6-
Average Distribution Mcan-0.15
Average (b] Exponentisi Distribttion Mean=
update
Figure 5: Sample distribution of the training time to complete one local step among 50 clients under (a) normal distribution with a 0.3y, and (b) exponential distribution.
E.2 DETAILED SETUPS AND HYPERPARAMETERS FOR EXPERIMENTS ON THE MNIST DATASET
Table shows the detailed architecture of the convolutional neural network (CNN) used for the experiments on the MNIST dataset. Table g provides comprehensive list of the hyperparameter values used for training. Specifically, Q is the number of client local steps for each training round, Qmin and Q are the minimum and maximum numbers of client local steps in FedCompas He is the client local learning rate, ,3 is the server-side momentum, and is the batch size. For all asynchronous FL algorithms, we adopt the polynomial staleness function introduced in (Xie et al. 2019). denoted as st r) axt - - + 1) a The values of a and a are also listed in Table for all asynchronous algorithms. Additionally, K is the buffer size for the FedBuff algorithm, is the speed ratio factor for creating tiers for clients (clients with speed ratio within v are tiered together and its value is selected via grid search), and is the latest time factor for FedCompass, For hyperparameters given as length-three tuples, the tuple items correspond to the hyperparameter values when the number of clients is 10, and 20, respectively. For hyperparameters that are not applicable to certain algorithms, the corresponding value is marked as dash ".", To ensure a fair comparison, similar algorithms are assigned the same hyperparameter values, as depicted in the table. The number of global training rounds is chosen separately for different experiment settings and FL algorithms such that the corresponding FL algorithm converges, synchronous FL algorithms take the same amount of wall-clock time, and asynchronous algorithms take the same amount of wall-clock time the same setting. It is also worth mentioning that the buffer size K for the FedBuff algorithm (Nguyen et al. 2022 is selected from a search of multiple possible values. Though the original paper states that not require tuning, the value does not apply in the cross-silo cases where there less than equal
10 a good setting across all their benchmarks and does
26

---

Published as a conference paper at ICLR 2024
to ten clients in most experiment settings, while all the experiments in the original paper have more than thousands of clients.
Table 8: MNIST CNN model architecture.
Layer
Outsize
Setting
Parama #
Input
(8, 28)
0
Conv1
(32, 24, 24)
kernel=5, stride=1
832
ReLUI
(32, 24, 24)
0
MaxPooll
(32, 12, 12)
kernel=2, stride=2
0
Conv2
(64, 8, 8)
kernel=5, stride=1
51,264
ReLU2
(64, 8, 8)
0
MaxPool2
(64, 4,4,4,4) 4)
kemel=2, stride=2 0
Flatten
(1024.)
0
FC1
(512.)
524,800
ReLU2
(512.)
0
FC2
(10.)
5,130
Table 9: Hyperparameters for various FL. algorithms on the MNIST dataset.
FedAug
FodAwgM
FodAsyne
FedBuff
FedAT
FedCompass (+S)
FedCompass-tt
(200, 200, 100)
(200, 100)
200. 100)
(200, 200, 100)
(200, 200,
Q
Quio
(40, 40, 20) (200, 200, 100)
(40, 40, 20)
Quax Optim
(200, 200, 100)
Adam
Adam 0.003
Adam 0.003
Adam 0.003
Adam 0.003
Adam
Adam
ne
0.003
0.003
0.003
3
0.9
B
64
64
64
64
64
64
64
0.5
0.5
0.5
0.5
(3)
2.0
A
1.2
1.2
E.3 DETAILED SETUPS AND HYPERPARAMETERS FOR EXPERIMENTS ON THE CIFAR-10 DATASET
For experiments the CIFAR-10 dataset, randomly initialized ResNet-18 model (He al. 2016) used in training. Table 10 shows the detailed architecture of the ResNet-18 model, which con- tains eight residual blocks. Each residual block contains two convolutional batch normalization layers, as shown in Table | and the corresponding output is added by the input itself if the output channel is equal to the input channel, otherwise, the input goes through Ixl convolutional batch normalization layer before added to the output. An additional ReLU layer is appended at the end of the residual block. T2ble lists the hyperparameter values used in the training for various FL. algo- rithms. The number of global training rounds is chosen separately for different experiment settings and FL. algorithms such that the corresponding FL algorithm converges, synchronous FL. algorithms take the same amount of wall-clock time, and asynchronous algorithms take the same amount of wall-clock time the same setting.
E.4 DETAILED SETUPS AND HYPERPARAMETERR FOR EXPERIMENTS ON THE FLAMBY DATASETS
For the datasets from FLamby (Ogier du Terrail et al. 2022), we use the default experiments settings provided by FLamby. The details the experiment settings are shown in Table B3
27

---

Published as a conference paper at ICLR 2024
Table 10: CIFAR-10 ResNet18 model architecture.
Layer
Outsize
Setting
Param #
Input
(3, 32, 32)
0
Conv1
(64. 32, 32)
kemel=3, stride=1, stridee, padding=1, bias=False
1.728
BatchNorml
(64. 32, 32)
128
ReLUI
(64. 32, 32)
ResidualBlock1-1
(64, 32, 32)
stride=1
73,984
ResidualBlock1-2
(64, 32, 32)
stride=1
73,984
ResidualBBock2-1
(128, 16, 16)
stride=2
230, 144
ResidualBlock2-2
(128, 16, 16)
stride=1
295,424
ResidualBlock3-1
(256, 8, 8)
stride=2
919,040
ResidualBlock3-2
(256. 8,
stride=1
1,180,672
R
(512, 4,
stride=2
3,673,088
ResidualBlock4-2
(512, 4. 4)
stride=1
4,720,640
AvgPool
(512.)
kernel=4, stride=4
Linear
(10,)
5,130
Table 11: ResidualBlock ResNet18 architecture.
Layer
Outsize
Setting
Param
Input
(in_planes, H. W)
Conv1
(planes, H/stride, W/stride) (planes, H/stride, Wistride) (planes, I/stride, W/sidee
kernel=3, stride=stride, padding=1
in.planes "llanes 2'lanes
BatchNerm
ReLUU
0
Conv2
(planes, Histride, W/stride)
kemnll3,, stridem I, padding=l
planes planes 2'plancs
BatchNorm2
(planes. H/stride, W/stride)
"Identity"
(planes, Hisrrdde W/stride)
Ixl Conv RatchNorm if in.plane of plane
ReLU2
(planes, Isstridee Wistride) Apply after adding BatchNomm2 and "Identity" outputs
Table 12: Hyperparameters for various FL algorithms on the CIFAR-10 dataset.
Pedåvg
FedåvgM
FedAsyae
FedDuff
PedAT
FedCempas: (1))
FedCompass
(200, 200, 100)
(200, 100)
(200, 200, 100)
(200, 200, 100)
(200, 200, 100)
Q Quac Optim
(40, 40, 20)
(40, 40, 20)
(200, 200, 100)
(200, 200. 100)
SGD
SGD
SGD
SGD
SGD
SGD
SGD
0.1
0.1
0.1
0.1
0.1
0.1
B
73
128
128
128
128
128
128
128
a
0.9
0.9
0.5
0.5
0.5
0.5
(3)
A
1.2
1.2
Table 13: Detailed settings for experiments FLamby datasets.
Fed-IXI
Fed-ISIC2019
Model
3D U-net (Cçękk et al. 2016)
EfficientNet Tan & Le
2019
Metric
DICE
Balanced accuracy
(Client #)
3
50
Q min
20
20
Qmax
100
100
Optimizer
AdamW Loshchilov & Hutter 2017
Adam
0.001
0.0005
0.9
0.5
B
2
64
0.9
0,9
0.5
0.5
K
2
1.2
28

---

Published as a conference paper at ICLR 2024
F ADDITIONAL EXPERIMENT RESULTS
F.1 ADDITIONAL EXPERIMENT RESULTS ON THE MNIST DATASET
Table 14 shows the top validation accuracy and the corresponding standard deviation on the class partitioned MNIST dataset for various federated learning algorithms with different numbers of clients and client heterogeneity settings among ten independent experiment runs with different ran- dom seeds, and Table [1 shows that the dual Dirichlet partitioned MNIST dataset. As all asyn- chronous FL algorithms take the same amount of training time in the same experiment setting, the results indicate that FedCompass not only converges faster than other asynchronous FL al- gorithms but also can converge to higher accuracy. Notably, in the homogeneous client settings, F FedCompass does not behave exactly the same FedAvg the clients also have local speed variance in each local training round, and this prevents the Compa ss scheduler to assign Qmax to all clients and have exactly the same behavior FedAvg. The global model gets updated more frequently for FedCompass and leads to relatively faster convergence.
Figures I depict the change in validation accuracy during the training process for various FL algorithms in different experiment settings. Those figures illustrate how F FedCompass can achieve faster convergence in different data and device heterogeneity settings.
Table 14: Average top validation accuracy and standard deviation on the class partitioned MNIST dataset for various federated learning al algorithms with different numbers of clients and client hetero- geneity settings.
Method
exp
homo
normal
exp
homo
normal
exp
Fedkvg
92.42.13996
92.42.13.96
92.42.13.96
92.27
92.27 92.27.1..88
97.38 19.39 97.38 1.59 97. 17.38:11 1.59
Fedkvgh
96.224:2.45
96.22422.45
96.22++245
97.11=145 97.11 97.11 98.2740.18 98.27400188
98.27=0.18
FedAsynz
90.60:16696 92.53-55.57
92,44+33007
86.7346.22
92.27
96.25-2246
84.26+7996
90.98 48 98.01
FedRufe
9.97 94.69.13.52
95.68.11.78
91.93.14.50
94.83.13.36
1.9
93.04-1.61
98.12.10.54
98.56_10.22
FedNr
92,47:13.51
92,36:33.59
91.40:33.21
91.50
15
91.01
93.03:2.94
97.17
97.89:10.94
95.74=2.48
PedCompase
95.06++2.89
95.54=2.89
96.34+1.89
94.33=3.80
95.47=3305
97.51=1.66
98.49:00.55
23.66-+0.36
36 98.72=0.47
FedCompass* +M
95.58:122.87 95.98-12243
95.93+11.92
95.64422.72
96.61=:2.12
97.69:10.76
98. 98.58:1:023
97.05::0.91
98.51:0.477
TedCompase
94.03=:3.82 93.07=4.00 96.44 94.55=3.86 94.80=#3.65 1.52
98.52::::42 98.79+00.17 98.80-0.18
Table 15: Average top accuracy and standard deviation on the dual Dirichlet partitioned MNIST
dataset for various federated learning algorithms with different numbers of clients and client hetero- geneity settings.
5
10
20
Method
homo
nommll
exp
homo
normal
exp
homo
nermal
exp
FedRvg
93.081:.116 93.08 93.08+4.116 93.71=:4.52 93.71=:4.52
93.71+:4552
95.77++2.98 95.77+-2.98 98 95. 05.77=2..98
FedAugM
93.88:13.16
93.88:33.16 93.8813.116
94.00:33.49 94.00:13.49 94.00:33449
96.06:12.17 96.06-12.11
96.06:12.17
FedAsyno
92.11:12.99
93.96.13.70
93.29
86.11
90,72.14.30
9..99
78.49.16.28
85.82.1.5311
95.90
FedBufE
93.87-1:4330
94.11
94.94112.49
92.27
94.29.14.04
94.50.13.72
87.04-16.26
95.27-1 .84
96.90
FedAr
92.30:114.00 93.06:1:..74
92.8113.116
95.40:12.70
95.63-1.2.2
93.80:14.94
95.26:12.47
97.32-10.76
94.67-13011
FedCompaas
94.15:::426 94.36+44.28 95.4643..99
95.53=33.11
95.41:1:3522
96.341-2.64
96.41
97.62+1.57
97.86=0.71
TedCompase+M
94.74:33.42
33
96.15422.03
96.01
10:1992299
95.59422.1
1.50
93.25++.228
97.42-0.96
PedCompase NN
94.56:b4.25
92.56:24..6
94.57+13.69
95.45=3.41
95.13::3.02
95.01
26.28
97.61+0060
97.92=0.50
10000
(al Homogonoous
(2) Normal
[c]
Exporicddal
Figure 6: Change in validation accuracy during the training process for different FL algorithms on the class partitioned MNIST dataset with five clients and three client heterogeneity settings.
29

---

Published as a conference paper at ICLR 2024
300
3000
3059
Figure 7: Change validation accuracy during the training process for different FL algorithms on the class partitioned MNIST dataset with ten clients and three client heterogeneity settings.
1400000
recking Facduut
Tectog
Fedit
Compsse
fedcongurent
Tine bac)
Tyms 0:521
Tiree bext
(1) at
Figure 8: Change in validation accuracy during the training process for different FL algorithms the class partitioned MNIST dataset with twenty clients and three client heterogeneity settings.
125
155
155
280
480
400
1000
1200
1492
(3) Homegeencuu
(5) Normal
(c) Exporential
Figure 9: Change in validation accuracy during the training process for different FL algorithms on the dual Dirichlet partitioned MNIST dataset with five clients and three client heterogeneity settings.
100
fassongur
160
350
1200
3200
Homogercouss
(C)
Exponential
Figure 10: Change validation accuracy during the training process for different FL algorithms on the dual Dirichlet partitioned MNIST dataset with ten clients and three client heterogeneity settings.
M
Tealing Froit
Foodu.t
Fookl
Tims bac
Tims Seick
(1)
Figure 11: Change in validation accuracy during the training process for different FL algorithms on the dual Dirichlet partitioned MNIST dataset with twenty clients and three client heterogeneity settings.
30

---

Published as a conference paper at ICLR 2024
F.2 ADDITIONAL EXPERIMENT RESULTS ON THE CIFAR- 10 DATASET
Table shows the top validation accuracy and the corresponding standard deviation on the class partitioned CIFAR-10 10 dataset for various federated learning algorithms with different numbers of clients and client heterogeneity settings among ten independent experiment runs with different ran- dom sceds, and Table 77 shows that on the dual Dirichlet partitioned CIFAR-10 10 dataset. Figures 17 give the change in validation accuracy during the training process for various FL algorithms different experiment settings on the CIFAR-10 datasets.
Table 16: Average top accuracy and standard deviation on the class partitioned CIFAR- 10 dataset for various FL algorithms with different numbers of clients and client heterogeneity settings.
5
10
20
Method
homo
normal
homo
normal
homo
bormal
FedRvg
67.10:16.33 67. 30
67. 10.33333
66. 86.80
66
66.80:22.71
66,80:2..71
70.03:22.37
70.03+22.37 70.03=2.37
FodAvgg
63.44.13.26
63.44:1..26
63.44
63.50.12.56
2.656
23.50.1..56
64.47.11.88
64.47.1..88
64.47.1.88 1.88
Fedisyas
53.30:24.12 63.65228811
66,27-13391
37.0942.99
44.87+33.54
59.40:14.21
30.18:t2..84
36.73-4-.93
54.30=2.64
FedDufE
67.02=22.55 67.33-22,46
70,8++2.99
46.1424,14
14
50.86=+4.43
64,32+:3.78
43.83++.001
49.63=t4.00
60.90=3.37
FedsT
72.41+:3.11
72.92+2.552
71.15+3.18
65.25:4.21
65.70::4.34
66.57:14448
66.09:11.22
1.538
6..31=1.87
FedCcmpaas
72.66.1:244
7..64:11.80
73.9611183
66.27:12.11
67.07:12.40
68.73:11.95
66.83:11.29
67.14:1..32
6.54
FedCompaas
72.82:12.27
1.703:11.77
74.22::1.95
1.97
67.72.11.77
69. 1.77
1.18
1.348:11.38
1..91
FedUcmpass**
72.79:12.50 73.69:2.33 74.85::1911 65.53:12.52 66.78:12.31 68.0411.99
66.32::1.41 66.76:1:140 1.55
Table 17: Average top accuracy and standard deviation on the dual Dirichlet partitioned CIFAR-10 dataset for various FL algorithms with different numbers of clients and client heterogeneity settings.
10
20
Method
homo
normal
exp
homo
normal
homo
normal
FedRvg
48.88=8.003
88.88
48.8848.03
51.91=7.65
51.91 51.91 29.28-+2.22
49.2842.62
49.28=2262
FedAugM
49.89
49.8915..7 49.89115.27
51.7212.64
51.72.12.64
51.7212.64
49.94:14.15
49.9411..15 49.94
FedAsyno
44.38114.71 47.6711.29
51,21114.99
33.5213.22
38.1311.07
47.62
34.89:1..34
36.1211.69 .9 39.92:1.399
FedDufE
$1.85:+3.23
54.03+4.84
48.11+44.2
42.60=2447
45.24
$3.04
41.37+2.85
42.65+
46.30=2.90
FedAT
58.911:4.63
58.34:1..77
55.40114.05
$2.8216.77
53.5411.122
53.8315.366
48.63-13.02
50.56
50.37-2.38
FedCompaas
59.29.13.49
59.98.1..65
61.27
5..51
54.95
57.29
51.01:1..20
52.03.12.75
51.39.1.122
TedCompass+M
59.29-1:2.65
60:20:13001
59.73413997
54.2414.21
54.53433.16
14
56.30112.87
51
48:12:544
52.7342.61
51.70-2.06
#odCompaaco*
59.38.1..599 60.38.12.20
61.08.13.74
54.28
54.31.16.03
25.90.1..97
52.13:1211
52.44.1.91
$2.23.12.20
22-
2000
(3) eeneog
157 Narmal
(C) Exponcniaal
Figure 12: Change in validation accuracy during the training process for different FL algorithms on the class partitioned CIFAR-10 10 dataset with five clients and three client heterogeneity settings.
Froling
Comosee
restompus onpervt
M
Nacee
Hacht
(sac)
(c)
Figure 13: Change in validation accuracy during the training process for different FL algorithms on the class partitioned CIFAR-10 dataset with ten clients and three client heterogeneity settings.
31

---

Published as a conference paper at ICLR 2024
Poiit
Tere
Tireisest
Figure 14: Change in validation accuracy during the training process for different FL algorithms on the class partitioned CIFAR-10 dataset with twenty clients and three client heterogeneity settings.
Compase
Hed Compssee
01
300
1800
3006
2500
3000
380
2004
800
16500
Homagemeuus
Expereenti
Figure 15: Change in validation accuracy during the training process for different FL algorithms on the dual Dirichlet partitioned CIFAR-10 dataset with five clients and three client heterogeneity settings.
Commanto
1880
2000
18:00
19000
20100
Figure 16: Change in validation accuracy during the training process for different FL algorithms on the dual Dirichlet partitioned CIFAR-10 dataset with ten clients and three client heterogeneity settings.
2009
12:0
15000
Figure 17: Change validation accuracy during the training process for different FL algorithms on the dual Dirichlet partitioned CIFAR-10 dataset with twenty clients and three client heterogeneity settings.
32

---

Published as a conference paper at ICLR 2024
F.3 ADDITIONAL EXPERIMENT RESULTS ON THE FLAMBY DATASETS
Table 18 shows the top validation accuracy and the corresponding standard deviation on the Fed- IXI and Fed-ISIC2019 datasets from FLamby for various federated learning algorithms in different client heterogeneity settings among ten independent experiment runs with different random seeds. Figures T8 and 19 present the change in validation accuracy during the training process for various FL algorithms on the Fed-IXI and Fed-ISIC2019 datasets, respectively.
Table 18: Average top accuracy and standard deviation the FLamby datasets for various federated learning methods in different client heterogeneity settings.
Fed-IXI
Fed-IS1C2019
Mothod
homo
normal
exp
homo
normal
exp
FecAvg
08.39:00.02
98, 98.19:10.02
98 08.39:::0.02
59.12= 1,38
12.1221..38
59.12 1.38
TedAvgM
98.39=00.00
98.39=00.00
98.39:0.000
50.25=2.57
50.25:22.57
50.25::2.57
TecAayno
98.05:20.25
98.24::0.18
98. 98.32::0.20
19.43=1.18
59.66:1.04
56,34::.34
PedDuIE
98.36+0.03
98.35=0.03
98.35++0.06
57.65=2.07
57.46+22.60
55.13:4::74
FedAT
98.72:00.01
98.65-20.06
98.63-10.088
$8.31=2.35
18.55:11.76
61.93:14.56
TedCompasa
98.76=00000
98.61
98.59#0.004
68.46-0.38
66.35-33.66
65,46+5.33
VedCompass+*
98.76:10.00
98.61:10.06
98. 08.59:10.04
64.72-0.94
62.43:15.23
60.18:4.99
TedCompasa
98.7240.01
98.61
98.59:00.44
09.59-0.6
67.04433.56
66.4824884
10-
14.
82
Pee Compasi
FecDorgass fastompurees
Hot Compss0en
30
100
100
5/6
400
(3)
(c1 Exparential
Figure 18: Change in validation accuracy during the training process for different federated learning algorithms the FLamby Fed-IXI dataset with three different client heterogencity settings.
Fediig
33-
Fount
Nomogeneous
Ein Exponenetil
Figure 19: Change in validation accuracy during the training process for different federated learning algorithms on the FLamby Fed-ISIC2019 dataset with three different client heterogeneity settings.
G ABLATION STUDY
G.1 ABLATION STUDY ON fain//Qmax
In this section, we conduct ablation studies on the values of 1/Q Qmin/ /Quax investigate its impact on the performance of the FedCompass algorithm. Table [9 lists the relative wall-clock time for different values of I/Q = Quinn/ / reach 90% validation accuracy on the class partitioned and dual Dirichlet partitioned MNIST datasets, and 50% accuracy on the dual Dirichlet partitioned CIFARIO datasets different client heterogeneity settings, and Table 20 shows the corresponding the validation accuracy and standard deviations. The results are the average of ten different runs with random seeds. Table 19 also lists the results of FedBuff for reference. From Table 19 the following observations can be derived: (1) A smaller Qmia usually leads to faster convergence speed, which is consistent with the convergence analysis from Section where smaller I/Q results in fewer existing arrival groups equilibrium and may help reduce the impact of
33

---

Published as a conference paper at ICLR 2024
device heterogeneity. (2) Though FedCompass achieves faster convergence rate with smaller 1/Q (0.05-0.2) in general, it still can achieve reasonable convergence rate with large 1/Q values (0.2- 0.8) compared with FedBuff, which shows that FedCompass is not sensitive to the choice of the value Q. (3) In the extreme case that @ = 1, i.e. Qiin = Q max: there is significant performance drop for FedCompass, steps to different clients, so each client has its own group, and the FedCompass algorithm becomes equivalent the FedAsync algorithm.
the Compass ss scheduler is not able to assign different number of local
Table 19: Relative wall-clock time to first reach the target validation accuracy on the MNIST and CIFARIO datasets for various values of I/Q = Qiin/ hiinn/Qmas max with different number of clients and client heterogeneity settings.
173 5
m
771
Dataset
1/Q
homo
normal
exp
homo
normal
exp
homo
normal
cxp
0.05
1.04x
1.16x
0.92x
0.93x
0.90x
0.95
0.98 x
0.93
0.99
0.10
1.00x
1.38x
0.93x
1.03x
0.92
0,93x
1.01
1.03x
1.02
0.20
1.00x
1.00x
1.00x
1.00x
1.00
1.00x
1.00x
1.00x
1.00
MNIST-Class
0.40
0.99
1.67x
2.48x
0.98x
0.98x
1.41x
1.01
1.19x
1.10x
Partition (90%)
0.60
0.97x
1.23x
2.64x
0.98x
0.97
1.28x
1.02x
1.31x
1.11x
0.80
0.96x
1.33x
1.51
0.98x
1,21
1.23x
1.01x
1,61
1.28x
1.00
2.15x
2.34x
2.35x
2.17x
1.32x
4,44x
1.32x
FedBuff
1.30x
1.57x
1.81X
1.58x
1.39
1.43x
1.37x
1.18x
1.39
0.05
0.89x
1.1X
0.85x
0.96x
0.97
0.82
1.00
1.02x
0.96
0.10
0.91x
1.05x
0.92x
0.96x
0.95
0.85
0,97
1.02x
0.96x
0.20
1.00x
1.00X
1.00x
1.00X
1.00
1.00
1.00x
1.00x
1.00
MNIST-Dirichler
0.40
1.02x
1.03x
1.70x
1.04x
1.05
1.28x
1.00x
1.14x
1.25x
Partition (90%)
0.60
1.04x
1.01X
1.83x
1.00x
1.01
1.19x
0.92x
1.11X
1.16x
0.80
1.04x
1.13x
1.58X
0.91x
1.25
1.22x
0.86x
1,22x
1.21
1.00
1.78x
1.68X
2.01X
2.28x
1.29x
1.76x
FedBuff
1.23x
1.52X
1.86x
1811
1.51
1.49
2.77x
1.22x
1.40
0.05
1.27x
0.97x
0.76x
1.55x
0.98
1.19x
1.05x
0.97
0.90
0.10
1.15x
1.01
0.73x
0.98x
1.11x
1.27x
1.01x
1.04x
1.01x
0.20
1.00x
1.00x
1.00x
1.00x
1.00
1.00x
1.00x
1.00x
1.00
(IFAR1O-Dirichle
0.40
1.28x
1.06x
1.36x
1.02
1.06x
2.19x
0.96x
1.14x
1.08x
Partition (50%)
0.60
1.23x
0.99x
1.65x
0.97
1.61
2.52x
1.11X
1.06x
1.74x
0.80
1,23x
1,24x
1.64x
1.32x
1.91x
3.44x
1.33x
2.95x
1.64x
1.00
3.18x
1.70x
:
5.35x
Ff
1.62x
1.99X
1.67x
2.42x
G.2 CLIENT SPEED CHANGES IN FEDCOMPASS AND ABLATION STUDY ON À
In cross-silo federated learning scenarios, variations in computing power and speeds among clients are possible. For instance. client utilizing supercomputer might experience significant changes computing power due to the auto-scaling after the allocation deallocation of other tasks within the same cluster. Similarly, in cloud computing environments, a client might be subject to auto- scaling policies that dynamically adjust the number of virtual machines or container instances. In this section, we provide analyses and empirical results to study how FedCompass is resilient to client speed changes.
Figure 20 depicts an execution of FedCompass involving client speedup scenario. During the second round of local training, client 3 enhances its computing speed from step/min to 5 step/min. Consequently, client 3 transmits its local updates Ag 10:36, earlier than the expected group arrival time T, = 12:00. In this situation, FedCompass server first updates the speed record for client and then waits for the arrival of clients I and 2 in the same group. Upon the arrival of clients I and 2 at 12:00, FedCompass server assigns all three clients to arrival group 2 for the subsequent round of local training, and the number of local steps for client are assigned according its new speed.
Figures 21 and 22 illustrate two executions FedCompass with different levels of client slow- down. In Figure 21 the speed of client changes from 4 step/min 3.33 step/min during its second
34

---

Published as a conference paper at ICLR 2024
Table 20: Average top validation accuracy and standard deviation for various values of 1/Q Q mina/C / Qmax with different number of clients and client heterogeneity settings.
10
20
Dutaset
1/Q
homo
normal
homoo
normal
exp
homo
normal
eap
0.05
95.20=+22.53
95.21=22.00
97.22==1.67
94,29:33.80
94,88-33373
1,549=1155
98.56--0043
98.80=0.17
98.75=-0.20
0.10
95.03-+3.13
95.35 15 97.07+1.67
94.72223.56
94.655:3.74
1.27
98.57+0038
98.80=0.11
98.82+00.18
MNIST
95.06=+2.89
95 25.55
16834
94.33+3.80
95.47::3.05
1.651=1666
98.49:+0.45
9..6700.6
96.73=:0.47
Class
0.40
94.4443..26
35.34
92.73+3.09
94,42:4394
95.01=:3.52
9691
98.58:+0.36
98.74=0.26
98.75:-0.22
Partition
0.60
95.29.12.75
93.25
94.9011.997
94.17.1..88
95.38.12.55
97.73.10.86
98.48.00.66
98.80
98.80.10.19
(90%)
0.80
95.61::2.34
95.35.2..0
95.04
94.77:3.59
96.08:12.660
17.35:1:.49
98.60:1::55
98.72=0.25
98.74:10.25
1.00
90.60:16.96
92.53.1.557
92.441.3.07
6..73.16.62
92.27:13.82
96.25.1.2.46
84.26.17.96
90.98.12.48
98.01 0..01
0.05
94.10:-4.12
94.30=4.118
95.81
95,64+3.115
95.75+:2.98
96.1743.01
96.22:422255
97.40=1.82
97,04=11997
0.10
94, 14::088
94,1424,44
36.11
93.49
95.65::3.23
26778:22.66
96.39=
91.59 1.28
97.68 1.28
MNIST
94.15::4:26 94.36=44.28
95,46=3.59
95.53=3.211
95.41+3352
96.34:22.44
96.41+19%
9..62=1.57
97,86=00,71
Diricher
0.40
94.12:4:.11
94.2744.11
95.40-22.46
95,4643.47
95.67433.14
95.86:43335
96.07+22.55
98.03=0.93
97.85
Portition
0.60
94.09+4.11
94.65=4.111
94,29+3.43
95,43+3.36
95.89+33.26
95.27=4.711
96.37+2.35
98.04=0.68
97.66==1114
(90%)
0.80
94.23:4:.89
94.7143.55
95.09-42..2
95.3223.55
95.46:13.20
95.26:1-.366
96.72:42.20
0..51=0.84
97.66:10.62
1.00
92.11=22999
92.96=3.70
93.29::3.08
86,314451
90.72:+4.30
94.06++5.91
78,49::6.88
85.82=5.31
15.90=
0.05
59,40=:2.28
60.86=1994
61,79+3.27
54.0414.668
53.85-66.74
17.36:
50.58++2.26
50.62=2.58
11,40::1668
0.10
29.90:12..9
61.05:22.26
61.70112.92
53.91
55,13:15:42
26.36.1
51.15:12.4
50.81 2.339
$1.08.1..90
CIFARIO
39,29:33.99
59.98=3.65
61.23+22.77
$4.51
54.95+:3.68
1.929
5101+2200
52.03=2.75
51,39::2112
Dirichfer
0.40
59, 59.25:1:3.49
60.85:12.23
39,4413.222
53.29
$6.4771283
55.58:1:.004
50.90:1265
50.26:2..44
1..43::1.32
Portition
0.60
59,25+22.99
60.76:2222
59.01
$2.92+4.000
56.45-33005
24.76:22.11
50.67+2.20
50.33-2.04
11,44#1.79
(50%)
0.80
19.10:::3033
60.53:1.18
38.79
53.11
35.7841..00
53.23-42.03
49.8342004
29.61-2.10
51.01
1,00
44.38:t4.71 47.67=4.229
51.21
33.52=3.299
38.13:22.07
47.62:+2.59
34.89
36.12=1.69
39.92=3.399
FedCompass Server
Artival Group
FedCompass Server
Arrival Group 2
FedCompass Server
Antival Group
1
Y,
00
32: 00:0
Qum = 20
I S
Q Quaay 100
2 = 100
Oser 100
08:
12:00
12:00
22:00
22:00
2
Rui = 20
Sin
= 40
Q 50
Qrez
00:
00
12:00
22:00
3
Speedup
Qun 20
28
08:
00 4,
05:00
12:00 w
22:00 A,
22: or
9 10 Q Arrival Group
Gun - 20
mii
Ta = 22:00
Riser 25
00:
08:00
08::00
Speed Update
22:00
Ciant
Qnts 20
2-44
24
Qrazy
00:
20.00 J,
10: 00
22:00 J.
22: 00:000.0
ACCREGATE + CAEATEGROUP
Speed Clil.
AGGREGATE JOINGROUP
Figure 20: Overview of an execution of FedCompass on five clients with the minimum number of local steps Quin = 20, maximum number of local steps Qmax = 100, and client speedup.
round of training. Consequently, the client transmits its local update As back to the server at 13:24, surpassing the expected arrival time T₂ = 12:00. Nonetheless, it is important to recall that each arrival group has the latest arrival time Timax to accommodate potential client speed fluctuations. The time interval between Tmax and the group's 's creation time is À times longer than the difference between T. and the group's ' creation time. For this example, we select À 1.2, resulting in Tiax = 14:00 for arrival group 1. Since client arrives later than Tg but earlier than Tmax- the F FedCompass server waits until client arrives at 13:24. subsequently assigning clients 1 to to a new arrival group for the next training round. Figure 22 presents another case where the client has relatively larger slowdown. In this example, the speed of client 3 diminishes from 4 step/min to 2.5 step/min, causing it to transmit local update A₃ at 15:12 even exceeding Tiax = 14:00. When the F FedCompass server does not receive an update from client by the latest arrival time 14:00, it responds to clients and 2. The server assigns these clients to arrival group 2 with corresponding numbers of local steps. Upon client 3 arrives at 15:12, the server first attempts to assign it to group 2, but this is unsuccessful due to the corresponding number of steps (Q (22:00-15:12) the Qmin = 20. As a result, the server establishes a new group 3 for client 3. Subsequently, once all clients in group 2 arrive at 22 00, the server assigns all of them to group 3.
2.5 (step/min) = 17) falling below
35

---

Published as a conference paper at ICLR 2024
FedCompass
Artival Group 1
FedCampass Server
Arrival
FedCompass Server
Arrival Group
Clant
To = 12:00 Teur 14:00
T,
Gun 20
Q G.e.r 100
B6
Ouaz 100
08:
02: D0
12:00 A
13:24 1P"
22:00 A
NEw Q
2
Qunn 20
Nin
40
43
0 Puac
08:
00 bg
00
12:00 Ag Slowdown
13:24
22:00 dg
22: 00 oz
3
Owan
q - 28
Q
06: 00:00...
Cliant
0%:000 bg
05:
Rue
Arrival Group
2
8::44 by
13:24
22:00 bn
22:00
Qum = 20
0 Q=
T. 22:00
00 Paay
00:
U0: 00 w
Speed Update
22:00 A,
22: 00 o
5
Ants
Q
Rreez = 20
02:
10:00 00 b
10: 00
22:00 da
22: 00 a
AGGREGATE CREATEGROUP
Speed Record c(t).s
AGOREGATE JoHGRRUP
Figure 21: Overview of an execution of FedCompass on five clients with the minimum number of local steps Qwin 20 and maximum number of local steps Qmax 100 with client slowdown.
FedCompes Server
Arrival Group
FedCompass Server
Arrival Group
FadCCompass Server
Arrival Group 3
Arrival Group 42:00
12:00
22:00
32:00
4 Qeicr 100
4 100
100
02:00 A2
02:00
12:00 &
14: 00
22: OD
22:00
32:
32:00
04:00 Ag
04:00 or
12:00 & Sowdown
14:00
22: 00 Ag
22 00 ur
17: RD Ag
32,00
Artiaal Group
@
Q
2. 25
05:00 dy
05:00
15:12
JS:12
32:00
32:00
10
Group
ai 1 Q
m:15
25
1-0
0B:00 do 4
08:00
Speed Update
22: 00
22:00
521
32:00
Q-24
20
10:00 dg
10:00
22:00
22 60
32:00
321
Artial Group
AGGREGATE CRENTEGROUP
T, - 22:
Speed cnJ.
ASGREEaTE JOINGROUP
Figure 22: Overview of an execution of FedCompass on five clients with the minimum number of local steps Quin = 20 and maximum number of local steps Qmax 100 with client slowdown.
To empirically study how FedCompass is resilient to client speed changes compared to similar tiered FL methods such as FedAT (Chai et al.] (021) and how the value of may impact the resilience, we set up scenario such that each client has 10% probability to change its computing speed by re-sampling speed from the client speed distribution (normal or exponential distribution) in each local training round. This setup aims to mimic the occasional yet substantial changes in speed that may arise in real-world cross-silo federated learning environments as a result of auto- scaling. Table 21 shows the convergence speed for the FedCompass algorithm with different values of X and the FedAT algorithm, and Table (2 shows the corresponding average top accuracy and standard deviations. From Table 21] we can draw the following conclusions: (I) When À 1.00, the Compass scheduler is not resilient to even small client slowdown, so F FedCompass converges relatively slower compared with some À values slightly above 1.00 in general. (2) values slightly above 1.00 (e.g.. 1.20 - 1.50) result in faster convergence from the empirical results as the Compass scheduler accounts for minor client speed fluctuations without long waiting time. (3) Large À values sometimes slow down the convergence as the server needs to experience a long waiting time when there are significant client speed slowdowns. (4) FedCompass ss converges faster than FedAT regardless of the value of X, which further demonstrates its resilience to speed changes.
Finally, it is noteworthy that under extreme circumstances, where all client computing speeds are subject to dramatic and constant fluctuations, the scheduling mechanism of FedCompass may be unable to maintain the desired client synchronization. This is due to the reliance on prior speed data, which becomes obsolete in the face of such variability. In these scenarios, the training process would proceed in a completely asynchronous manner, effectively causing FedCompass to revert to similar behavior of the FedAsync (Xie et al. 2019) algorithm. However, different from cross-
36

---

Published as a conference paper at ICLR 2024
device FL where each client may experience frequent speed changes due power constraints, the operation of other concurrent applications, or network connectivity issues. practice, a cross-silo FL client usually has dedicated computing resources such HPC with job scheduler some cloud computing Seilittiss-whre significant changes in computing speed are less frequent, generally arising from events like auto-scaling.
Table 21: Relative wall-clock time to first reach the target validation accuracy on the MNIST datasets for various values of À with different numbers of clients and client heterogeneity settings, and each client has 10% probability to change its speed each local training round.
m 5
m 10
20 m
Dataset
A
normal
exp
normal
exp
normal
exp
1.00
1.00x
1,00
1.00x
1.00x
1,0x
1.00x
MNIST-Class
1.20
0.64x
0.83
0.84x
0.88x
0.86x
0.90x
Partition (90%)
1.50
0.67
1.00x
0.72
1.01
1.01
1.00x
2.00
0.68x
1.11x
0.80
1.11x
1,04x
1.37x
FedAT
3.13x
3.20x
4.04
5.92x
1.66x
3.33x
1.00
1.00x
1.00x
1.00x
1.00x
1.00x
1.00x
MNIST-Dirichlet
1.20
0.63x
1.05
0.75x
0.62x
0.79x
0.98x
Partition (90%)
1.50
0.55x
1,20x
0.75
0,62
0.85x
1.16x
2.00
0.55x
1.29
0.76x
0.83x
0.86x
1.28x
FedAT
1.03x
1,55x
1.41x
1.61x
1.71x
2.94x
Table 22: Average top validation accuracy and standard deviation on the MNIST datasets for various values of À with different numbers of clients and client heterogeneity settings, and each client has 10% probability to change its speed in each local training round.
5
10
20
Dataset
normal
exp
normal
exp
normal
exp
1.00
9..01
97.57-+1.01
96.55+1.007
97.45-42.11
98.78:10.03
98.76:10.15
MNIST-Class
1.20
96. 19:2246
9..54
96.78:2.94
97.03:2.771
98.86=t0.10
98.90:0.05
Partition (90%)
95.99+2.30
97.59:1.98
96.25:3.26
9..44
98.86:10.09
98.71::0.26
2.00
9..79:1.77
97.84:11.06
96.3743.17
97.37:2.229
98.86:10009
98.8311.113
FedAT
93.56+16.40
94.974.3.86
93.93+3.51
94.20
97.98++1.22
97.98++1.32
1.00
91.15::4.48
94.3412.84
94.8811.440
96.9011..33
98.0810.34
98.09:10.23
MNIST-Dirichlet
1.20
92.03:4.10
93.92:13.45
96.5912.10
9..1911.82
18.1013.11
98. 98.22:10.19
Partition (90%)
1.50
91.82+4.35
93.32+4..33
96.0443.36
97.47++1.22
98.28+00113
98.16+00.19
2.00
92.09-+4.11
93.08++3.61
95.77+3.29
97.36+
98. 08.16+00.0
98.26+40.07
FedAT
91.43++3.11
92.36++2.50
95.49+2.94
96.36+42.36
97.65++0.44
97.68++0.35
37


Reviews:
[{"review_id": "9ttqNAiggT", "reviewer": "Reviewer_UVPW", "summary": "The paper presents a way of tracking the computation speed of different clients in federated learning (FL), based on which a time threshold is determined to collect the clients' updates with possibly different numbers of local updates. Compared to fully asynchronous FL and some semi-asynchronous FL baselines, the experimental results show that the proposed FedCompass algorithm gives better performance.", "questions": "Basically all the things mentioned under weaknesses. Some specific questions include:\n- How does FedCompass compare with FedNova?\n- How is $K$ chosen for FedBuffer in the experiments? Was any hyper parameter optimization or grid search implemented?\n- Is it possible to theoretically show the robustness of the scheduler when the clients' computation speeds can vary arbitrarily?\n- What is the challenge and novelty in the convergence analysis?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This work tackles the important problem of system heterogeneity in FL, focusing on the cross-silo FL setup.", "weaknesses": "- The adaptation of the number of local updates based on clients' computation speed is not new. An important and well-known baseline is FedNova (Wang et al., 2020), which has been cited in the paper but not compared against. Compared with the proposed FedCompass method, FedNova is much easier to implement and supports both cross-silo FL and cross-device FL with partial client participation. The advantage of FedCompass over FedNova is not clear.  \n\n- The proposed FedCompass approach is heuristic and a lot of its description is based on simplified examples. The paper argues that FedBuffer includes the buffer size $K$ as a hyper parameter that needs to be tuned. However, FedCompass also includes hyper parameters $Q_\\mathrm{min}$, $Q_\\mathrm{max}$, and parameters in sub-procedures, such as $\\lambda$ in Algorithm 2, that need to be tuned heuristically. It is worth noting that the experiments in this paper use FedBuffer with small values of $K$ up to 5 (as listed in Appendix E) while the original FedBuffer paper (Nguyen et al., 2022) uses $K=10$ in the majority of experiments. It is not clear how the authors selected $K$ in the experiments presented in this paper, but I would expect that FedBuffer with a properly tuned $K$ would give a similar performance as FedCompass with properly tuned hyper parameters.\n\n    Side note: The algorithm is called FedBuff in the original paper (Nguyen et al., 2022), not sure why the authors call it FedBuffer in this paper.\n\n- In practice, the clients' computation speeds can vary over time due to the varying amount of concurrent tasks running in the system. The paper has a mentioning of this but only studies the behavior of the algorithm in some oversimplified cases of computation speed variation. It is unclear whether the scheduling procedure in Section 3.1 is robust to all types of speed variation, or does there exist a worst case scenario where the scheduler completely loses track in its estimation of clients' computation speeds. This needs a separate theoretical analysis IMHO, which is different from the convergence bound. \n\n- The convergence result appears fairly straightforward, since results with bounded staleness and different numbers of local updates both exist in the literature. It is not quite clear what is the challenge and novelty in the convergence analysis.", "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": "y37aJbvU5C", "reviewer": "Reviewer_7w8f", "summary": "This paper takes aim at tackling the combined problems of system and data heterogeneity in the context of cross-silo Federated Learning. The authors propose FedCompass a semi-asynchronous federated algorithm that assigns adaptively different amounts of training task to clients with different computational capabilities. Additionally, FedCompass ensures that received models are received in groups almost simultaneously reducing the staleness of local models while the overall process remains asynchronous eliminating long waiting periods for fast nodes. Theoretical results on the convergence of the proposed method are presented and experiments on both academic and real-world datasets support the theoretical findings.", "questions": "See the weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-The paper tackles an interesting problem in the literature of FL, namely the problem of system and data heterogeneity. Improving on prior works this paper attempts to circumvent the weaknesses observed in synchronous and asynchronous federated methods (which boil down to long delays due to stragglers and stale models respectively).\n\n-Theoretical results that prove the convergence of the proposed FedCompass are presented providing useful insights.\n\n-Substantial experimental evidence has been provided showcasing the superiority of the proposed method compared to established synchronous and asynchronous baselines.", "weaknesses": "-The description of the algorithm in section 3.2 is unclear and further discussion is required. Specifically, the assignment of groups and the group aggregation are major components of the proposed method and they are not presented or discussed sufficiently in the main body of the paper (I strongly believe that including these components or at least an extensive discussion about them in the main body of the paper would significantly improve the presentation of this work). It is unclear how the implementation of these components alleviate the bias introduced by faster nodes performing more updates than slower nodes (a common issue met in previously proposed asynchronous methods). It is also unclear how the overall method  reaches an equilibrium (as discussed in section 3.1) and what properties it has. I would appreciate it if the authors could elaborate on the above. \n\n-In the description in section 3.2 it seems that when a client arrives later than $G[g].T_{max}$ it is immediately assigned a new training task whereas the clients that arrive earlier than $G[g].T_{max}$ are assigned training tasks when the next aggregation takes place. What is the justification for this differentiation? \n\n-Some of the assumptions required for the theoretical results are very restrictive. Specifically, the bounded gradient assumption rules out simple function such as the quadratic. Further, the bounded heterogeneity  and staleness assumption is rather strong and the derived results in Theorem 1 and Corollary 1 have a heavy dependence on  quantity $\\mu$. As a result the impact of those results is diminished.\n\n-The related work section could be extended with works on device heterogeneity (Reisizadeh et al., 2022; Horvath et al., 2022) and on asynchronous FL (So et al., 2021)\n\nReisizadeh, A., Tziotis, I., Hassani, H., Mokhtari, A., and Pedarsani, R. (2022). Straggler-resilient federated\nlearning: Leveraging the interplay between statistical accuracy and system heterogeneity. \n\nHorváth, S., Sanjabi, M., Xiao, L., Richtárik, P., and Rabbat, M. (2022). Fedshuffle: Recipes for better use\nof local work in federated learning.\n\nSo, J., Ali, R. E., Güler, B., and Avestimehr, A. S. (2021). Secure aggregation for buffered asynchronous\nfederated learning.", "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": "SXOQvrowRD", "reviewer": "Reviewer_DhHF", "summary": "- This work proposes a new semi-asynchronous FL for cross-silo FL. Specifically, FedCompass is designed to track the computing time of each client and adaptively adjust the local epoch, which enables the server to simultaneously receive local models from clients. The proposed method not only mitigates the straggler issue but also provides a great platform for global aggregation. The authors established a theoretical convergence bound and experimentally confirmed that the proposed method converges faster and higher than other baselines.", "questions": "See Weaknesses and,\n\n- In Line 21-23 of Algorithm 1, it seems that each client’s update is accumulated one-by-one into group specific buffer. How can existing aggregation strategies (e.g., [ICLR’21]) be performed in the global aggregation step of the proposed algorithm?\n- Could the authors conduct ablation study on Q_min/Q_max using CIFAR-10 dataset and compare the results with other baselines?\n- There are some typos in Appendix that should be corrected (e.g., in equation (6) of the proof for Lemma 2, the gradient symbol is missing)\n\n[arXiv’22] Chao et al., Cross-silo federated learning: Challenges and opportunities \n\n[ICLR’21] Reddi et al., Adaptive Federated Optimization", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The approach of adjusting local updates differently for each client to reduce the staleness gap between models is interesting.\n- Compared to existing asynchronous methods, the proposed method enables global aggregation, which is an important advantage since various existing aggregation-based methods (e.g., robust aggregation methods in FL) can be combined.\n- The proposed method is well supported by theoretical analysis.", "weaknesses": "- The motivation is a bit unconvincing. The straggler issue is considered important primarily in cross-device FL since the organizations are expected to have sufficient computational/communication resources in cross-silo FL [arXiv’22].\n- Most experiments were conducted on datasets with a small number of classes. To confirm the scalability of the proposed method, could the authors conduct experiments on datasets with more classes like CIFAR-100?\n- The idea of adjusting local epochs for each client is straightforward and the technical novelty of the proposed method seems somewhat limited.", "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": "D7gbYHNwr9", "reviewer": "Reviewer_vABe", "summary": "This paper proposes a semi-asynchronous federated learning framework named FedCompass, which adjusts the local training steps of each client according to their computing power and groups clients with similar training times in asynchronous federated learning. The proposed framework effectively alleviates the staleness issue in asynchronous federated learning while avoiding prolonged waiting time in synchronous federated learning.", "questions": "See the weaknesses above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "FedCompass is a semi-asynchronous federated learning framework that benefits from both asynchronous and synchronous federated learning while avoiding the drawbacks of these two frameworks. More specifically,\n\n1.\tFedCompass effectively addresses the staleness issue in asynchronous federated learning by grouping clients and thereby reducing the frequency of model aggregation on the server. By adaptively setting numbers of local epochs for each client, FedCompass ensures that the clients in each group can complete the training in a similar time, which avoids prolonged waiting time in synchronous federated learning.\n\n2.\tA theoretical analysis of the convergence of FedCompass is provided to support the effectiveness of FedCompass.\n\n3.\tExperimental results on four datasets with different statistical and systematic heterogeneity are conducted, and the results show that FedCompass outperforms previous asynchronous and synchronous methods.", "weaknesses": "FedCompass seems to be an incremental improvement based on Tiered Federated Learning by complementing adaptive numbers of local epochs. The differences between FedCompass and Tired Federated Learning are not clear and not significant. Though the authors claim that Tired Federated Learning cannot deal with time-varying computing power, it is not a serious issue in cross-silo federated learning where the local devices usually have sufficient computing power for running multiple tasks at the same time. In addition, experiments do not provide any comparison between FedCompass and Tired Federated Learning. To highlight the contribution of this work, the authors need to give more elaborations and empirical evidence for the significance of FedCompass compared with Tired Federated Learning.\n\nIn addition, the explanation of Algorithm 1 in Section 3.2 is more difficult to follow than the explanation in Figure 1. The authors may need to improve the clarity of this part since it is the core of the proposed method.", "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)