Kuiper: Moderated Asynchronous Federated Learning on Heterogeneous Mobile Devices with Non-IID Data
Authors: Dipesh Tamboli
Pranjal Jain
Atul Sharma
Biplab Banerjee
Saurabh Bagchi
Somali Chaterji
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Edge devices
Non-IID
Video action recognition

Abstract: Federated learning allows multiple clients to jointly learn an ML model while keeping their data private. While synchronous federated learning (Sync-FL) requires the devices to share local gradients synchronously to provide better guarantees, it suffers from the problem of stragglers. This is the scenario where the faster clients have to wait for the slower ones, slowing the entire training process. Conventional techniques completely drop the updates from the stragglers and lose the opportunity to learn from the data they hold, which is especially important in a non-iid setting. Asynchronous learning (Async-FL) provides a potential solution to allow the clients to function at their own pace, which typically achieves faster convergence. Since edge devices have a low compute, it is hard to train a video action recognition task on them. We present Kuiper, a variant of Async-FL, to help heterogeneous edge devices with limited resources learn a heavy model on video-action-recognition tasks with data distributed non-IID. Kuiper introduces a novel aggregation scheme, which solves the straggler problem while considering the different data distribution at different clients. Kuiper shows a 11% faster convergence compared to Oort15 [OSDI-21], up to 12% and 9% improvement in test accuracy compared to FedBuff16 [AISTAT-22] and Oort [OSDI-21] on HMDB51, and 10% and 9% on UCF101.

Under review as a conference paper at ICLR 2023
KUIPER: MODERATED ASYNCHRONOUS FEDERATED LEARNING ON HETEROGENEOUS MOBILE DEVICES WITH NON-IID DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning allows multiple clients to jointly learn an ML model while keep- ing their data private. While synchronous federated learning (Sync-FL) requires the devices to share local gradients synchronously, to provide better guarantees, it suffers from the problem of stragglers, slowing the entire training process. Con- ventional techniques completely drop the updates from the stragglers and lose the opportunity to learn from the data the stragglers hold, especially relevant in non-iid setting. Asynchronous learning (Async-FL) provides a potential solution allow the clients to function at their own pace, which typically achieves faster convergence. We target the video action recognition problem on edge devices as an exemplar heavyweight task to perform FL (Async-FL). Our FL system, KUIPER, leverages Async-FL FL to learn heavy model on aadeo-action-recogmiee non-lll) data. KUIPER introduces novel aggregation scheme, which solves the straggler problem, while taking into account the different client data in a non-iid setting. Although the proposed aggregation technique is catered majorly for video action recognition, it is task-independent and scalable, and we demonstrate it by showing experiments convergence compared to Oort [OSDI-21], up to 12% and 9% improvement in test accuracy compared to FedBuff [AISTAT-22] and Oort [OSDI-21] on HMDB51, and 10% and 9% on UCF101.
realistic edge setup using asynchronous-
tasks on heterogeneous edge testbed with
other vision and NLP tasks. KUIPER shows 1 11% faster
INTRODUCTION
Federated learning McMahan et al. (2017) has gained great popularity in recent times as it allows heterogeneous clients to collaborate and benefit from peer data while keeping their own data private. As a result, the clients learn a better model with collaboration than they would have, individually. The training process is orchestrated by central server that broadcasts the global model to the clients while the clients run local training on their own data and only share the gradient updates with the server. This has made it possible for clients with limited computational resources participate in the learning process. However, heterogencous clients with varying computational capabilities (we use the term "computational capabilities" as a shorthand to include heerogeneity in both computational capabilities on the node as well as the communication capabilities connecting the node to the federation server), if forced synchronize, direct the process to progress at the speed of the slowest client For example, in our experimental setup of embedded nodes with mobile GPUs, Jetson Nano is 5x slower than Jetson AGX Xavier; including variation in network speeds adds to this heterogeneity. becomes crucial to incorporate even slow clients when the data distribution among clients is noD-IID, as all clients then have distinctive elements to contribute to the learned model.
al. (2020a).
In this paper, we target heavyweight learning task, namely, video action recognition, that till date had been considered out of the reach of embedded devices, i.e., mobile GPUs. The straggler problem becomes particularly serious for heavyweight learning tasks on heterogeneous edge devices since the devices are resource constrained relative to the demands of the task and the variance in device capabilities (processing power, memory, storage) is large (5 x in our representative setup). Therefore, to deal with stragglers an obvious approach seems to be to synchronous learning. However, this prevents the global model from learning features specific to the local data of the stragglers, leading to model that underfits. This problem becomes more acute the degree of non- monels increases;

---

Under review as a conference paper at ICLR 2023
M
M
t-t,
Client
Client 2
n. acc,
t-t,
acc,
Client
t-T,
Client
Pg acc,
Client
5
t=t,
t=
Burst(K=3)
model update sendling client-1.3,4
(client-1.3.4 -1,344
Factor in staleness
Figure 1: Overview a working example of KUIPER in action for 5 heterogeneous clients with K (burst size) =3. The circle denotes that client is ready with its updates. The dashed vertical line denotes an aggregation step where we also update for the clients aggregated in the burst. The aggregator waits for clients to respond, comprising burst, denoted by identically colored circles. Within the burst, the individual client updates are weighed by a function of their local data
and training accuracy. The burst, as a whole, is then weighed again by the average staleness (1 - T.) of the clients comprising the burst, and the global model is updated. The updated model is sent back to all the clients in that same burst, and the process goes
again, for distributed edge device scenario, high degrees of non-llDness et al. (2018); Chen et al. (2020b). We empirically observe the severe negative consequence of discarding stragglers the learning accuracy (Figure 7(d)). This motivates the of asynchronous aggregation, which allows the central server to aggregate the clients' gradient updates as soon as they are made available without having to wait for all the clients to respond. However, has remained an open problem how to best aggregate the updates sent by all clients in order to maximize information learned while minimizing any adverse effect from slow updates'.
commonly seen Zhao
We propose KUIPER to solve the above problems of heteroge- neous clients with resource constraints and non- non-IID data, with the overview shown in Figure 1. We consider the typical case of FL with non-IID data where although the client might not have training data for the classes but wants to have global model which can work on all the classes (i.e., learning from peers). Our solution is based on the idea of scaling the stale updates before aggregation, depending on the staleness of the updates, and the current iteration's training error of the clients. Training error is measure of how much the local model has made progress learning from its own data. This ensures that the global model not starved of the information that could be learned from the stragglers' data. Our scaling policy is designed to ensure high model quality while balancing the need to incorporate relatively outdated updates if they improve the global model. Further, we find that pure asynchronous solution does not work well due to the wide diversity of rates of client updates. We then batch the updates from a group of clients, quantified by K, the batch size, before aggregation. This makes KUIPER a buffered asynchronous approach
Our proposed solution KUIPER:
Our contributions can be summarized as follows:
1. We propose a novel scheme to include heterogeneous clients in federated learning by balancing the utility of their data with their computational (and communication) efficiency.
2. We demonstrate our heterogeneous FL technique through video action recognition, which is a computationally heavy task and can be accomplished on resource-constrained edge devices only through the use of FL. In our setting, this task is particularly challenging due to device heterogeneity, network heterogeneity. and non- noD-IID data.
'There are two recent promising solutions to this problem in Oort Lai et al. (2021) and FedBuff Nguyen et al. (2022), and we discuss why they fall short and also compare them empirically to our solution.
"KIipEr is hand of small celestial hodies heyond the orbit of Neptune from which many short-period comets are believed to originate. Similarly, we make the small devices coalesce achieve big tasks. "Aspects of this design are shared with FedBuff Nguyen et al. (2022); explain the differences in Section 2 and empirically demonstrate superiority (Section 5).
2

---

Under review as a conference paper at ICLR 2023
3. We provide convergence analysis and show the effect of the number of clients in the federation and the non-IID parameter on the convergence.
4. With comprehensive evaluation of our proposed design on three Video Action Recognition datasets (Kinetics, HMDB51, and UCF101), we also show scalability of our algorithm on two other tasks (Image Recognition, and Next-Characte Prediction). We provide insights on the relationship between data staleness and non-IIDness and show how KUIPER achieves, for the HMDB51 dataset, up to 12% improvement in the action recognition task's test accuracy compared to FedBuff Nguyen et al. (2022), and 9% compared to Oort Lai et al. (2021), and an improvement of 10% and 9% respectively for the UCF101 dataset. Note that action recognition is a challenging task and even centralized training does not reach accuracy of 50% (47.8% to be exact) for a frame rate of 8, making the above (absolute) gains in accuracy significant.
RELATED WORK
FL McMahan et al. (2017) is used in multiple applications that require data privacy, for example, in healthcare Chen et al. (2020a); Li et al. (2019) and natural language processing on smartphones Llis- terri Giménez et al. (2022); Leroy et al. (2019). In synchronous FL, the server waits to receive updates from all the clients before aggregating the global model. FedAvg McMahan et al. (2017) is the baseline synchronous FI., where the global model is updated by the weighted sum of the gradients, weighted by the size of the local client data. FedProx Li et al. (2020b), FedAvgM Hsu et al. (2019), FedAdam Mills et al. (2020), are all modifications made to FedAvg to speed up convergence, albeit all of these are synchronous FL techniques.
Asynchronous optimization, solves the problem of straggler clients. Its innovation lies in rewarding and penalizing the clients in terms of the usefulness or staleness of the updates as in Smith et al. (2017); Xu et al. (2019). FedAsyne Xie et al. (2019) sets the local learning rate of clients to be inversely proportional to the frequency with which the client generates the model updates, in order to increase the contribution of slower clients. Oort Lai et al. (2021), on the other hand waits for fixed number of clients (K) to synchronize and runs FedAVG McMahan received updates. It prevents starvation of stragglers by maintaining a dynamic utility score for every participating client. This depends on the staleness and local training loss of the individual clients. FedBuff Nguyen et al. (2022) also waits for a fixed number of clients (K) to update its gradients but does not have client selection policy or a gradient weighing policy according to their performance. Thus, the model is biased towards the fast clients' data distribution (as it gives more weight to the fast clients because of their more frequent updates). When the non-IlI) bias is high, some slow clients will have exclusive data, which is important for the overall training and thus need to aggregate that client's 's model with high importance. Its focus is on guarding against an honest-but-curiou server (which it achieves by storing the buffer in a TEE) and in ensuring scalability to hundreds of clients (which is helped by the buffering).
al. (2017) the
Asynchronous FL, however has its own challenges. Previous literature in Asynchronous Learning Xie et al. (2019); Chen et al. (2020b) penalizes clients for their delayed updates and thus contribution of slow client to the global model is curtailed. In such scenarios, the problem arises when the data that clients have is distributed in a non-lll) manner, exacerbated for high non-IlI bias values. In such cases, a few clients may possess useful data while being stragglers. Previous literature does not consider this aspect and thus performs poorly when the non-IID bias is high (as we empirically show with FedBuff in Figures 3 and 6). We have evaluated Xie et al. (2019)'s method and it has comparable, albeit lower, accuracy relative to KUIPER for IID data. However, KUIPER'S 's performance higher than its counterparts for highly skewed data distributions, as would be the case in realistic mobile computing devices.
The fact that edge devices are often constrained in terms of local resources (compute, memory, and storage) as well as network resources (low bandwidth connections, intermittent connectivity) has given rise to fruitful areas of inquiry in communication-effiieen federated learning Reisizadeh et al. (2020); Sattler et al. (2019); Mills et al. (2019), asynchronous learning to deal with stragglers Smith et al. (2017); Xu et al. (2019), approximate models and computation Zhang et al. (2018); Wu et al. (2019); Han et al. (2020), and also knowledge distillation to create more succinct models Jang et al. (2020); Matsubara et al. (2020). Federated distillation Jeong et al. (2018) follows an online version of knowledge distillation, known co-distillation (CD) Anil et al. (2018). In CD, each device treats
3

---

Under review as a conference paper at ICLR 2023
itself as student, and sees the mean model output of all the other devices as its teacher's output. Furthermore, non-lID data of on-device ML can be corrected by obtaining the missing local data samples at each device from the other devices. This can induce significant overhead, so FAug Jeong et al. (2018) is proposed. FAug generates the missing data on each device. They empirically found that their approach yields lower overhead and better accuracy for image classification MNIST LeCun et al. (1998), Human action recognition approaches can be categorized into visual sensor-based based, non-visual sensor-based, and multi-modal categories Yurur et al. (2014); Ranasinghe et al. (2016). So far, federated learning for action recognition has only been incorporated into federated learning using wearable sensors Sozinov et al. (2018); Ek et al. (2020). That an easier task since the data streams from these sensors are much lighter compared to the targeted video data.
DESIGN AND ANALY OF KUIPER
KUIPER is a buffered asynchronous aggregation technique, which is designed considering the non-IlI) biases in the clients' datasets and heterogeneity clients' computational resources.
3.1 DESIGN DETAILS
The global server node and the client nodes conduct the training in buffered asynchronous manner. Each client independently trains the model obtained from the server on its local data and shares the gradient update with the server as soon it is ready. The server does not wait to hear from all the clients. Rather, the aggregation works in bursts where a burst consists of clients that have responded and are waiting for the server to send them back the aggregated global model. The server aggregates the received updates according to the client's ' local data size and training accuracy, and their staleness. It then updates the global model with these aggregated gradients and sends it to only those clients that contributed to the burst. Meanwhile, other clients might have responded to the server with their gradients and the server again waits until it has heard from K clients form a burst, and continue the above described process iteratively until convergence. We demonstrate a working example in Figure with heterogeneous clients and K-
Problem formulation. We consider a federated learning setup with M devices. We consider a supervised problem where the data is partitioned across M different clients with D1. Dz, ... Das data. Data samples are different for all the clients, i.e., D; n Dj = & for all the i, E [M] and U. Dr D. where D is the complete training data. Our aim is to find the parameters w that achieves min F(w), i.e.
M
W opt min F(w), whereF(w) = M Σ B[[(;; d:)
(I)
Here, d, is data sampled from local data D; on the i-th device, and I(-:-) is user-specified loss function. The 7t client performs training with a learning rate y/r using data d, which is randomly sampled from its local dataset D, We consider the typical case of FI. with non-III data where although the client might not have training data for all the classes but it wants to have a global model which can work on all the classes (i.c., learning from peers).
Knowledge distillation. To accommodate the limited resources on the embedded devices, we use knowledge distillation to train on the Kinetics dataset. We define the knowledge distillation loss LKD as the Mean Squared Error be- tween the logits from the teacher model z' and the student model z", i.e., LKD = ||2²(x) - z (x))] The overall loss function is combination of two loss functions, L aLds + (1 - LKD. Lat the conventional cross- cros--yytropy loss, computed for the predictions made by the student and the ground truth corresponding to the input x.
model ResNet-18, initialized from ResNet-34, trained
The teacher model cannot effectively transfer its knowledge to the student if the size gap between them is large Mirzadeh et al. (2020). To alleviate this, the knowledge distillation done through an intermediate Teaching Assistant (TA) model, which in our case is ResNet-26.
Fine tuning at the clients. In every epoch, the central server waits for K clients to report their updates, with these K clients forming burst. The individual gradients from each client within the burst are weighed according to three factors and shown in Equation 2: the amount of data at each client, the current training accuracy at the client, and the speed of the client. For larger non-IID bias, clients have data only from a subset of classes, and thus their reported gradients become relatively noisy. Weiggted-averaging those gradients first in burst and then aggregating the burst with the
4

---

Under review as a conference paper at ICLR 2023
global model helps to achieve better accuracy. Averaging also helps prevent inference attacks, as mentioned in Nguyen et al. (2022). Later, we experimentally see the importance this buffering over the vanilla asynchronous mode for video action recognition (Figure 9 (a)).
Now let us look at the various components Equation 2.
w When, [1(1 < To) x e(acetrain)) + 1(1 2 To)
Whe
nemott
The term n//N normalizes each client by the amount of data that it has. 1(-) is the identity function, which when the argument is True else O. This rewards clients which return results within latency threshold To. The function e e(acctrain)) = 1 acctrain,, considers this and thus give more importance the clients that have low training accuracy with the current state of the model. Intuitively, when client's s training accuracy is high, it means that the global model has already learned the features corresponding to that client's data and our global model can focus on other clients to learn their features.
Now let us consider how the aggregation handles stragglers and penalizes stale updates from clients. This is achieved in the second level of aggregation, where the weighting factor of the burst is determined (Equation 3).
a(t 70)
Here, Ct is the set of clients ((1, 2, i... K} }) we considering in the 8th update of the model. We calculate uy the global model at epoch t using Equation 4.
w + (1 8 J + 3 w Wnew,
To do this, we moderate the mixing byperparameter, 33 (0, 1). Here t - T captures how delayed the burst is and calculate staleness of the burst as s(t- sft- (1+t 11 - ) a where T mug(r', Vi E (1, 21. i, K)), which adaptively changes the mixing parameter 3 The general form of this function is that it monotonically and exponentially decreases with increase in staleness. The above is presented as a pseudo-code in Algorithm in Appendix B.
3.2 CONVERGENCE ANALYSIS
Here we prove the convergence guarantee of KUIPER. This analysis is influenced from FedBuff Nguyen al. (2022) and customized to our model. Specifically, we characterize the effect of non-IID bias on gradient variances and convergence guarantee.
Notation. M denotes total number of clients. g): (10; (i) denotes stochastic gradient on 7th client model with weights w and sampled batch Ç,. (w)) denotes the gradient with respect to the loss. of and og are local and global variances of the gradients. fww) is the objective function and f* is client received
the theoretical minima. is the current iteration and T, is the global iteration when 2th gradients from the server.
Assumption 1: (Unbiased client stochastic gradients) E[ga (w; G)] = VFi(w).
Assumption 2: (Bounded local and global variance) Vi E [M), E (xnklloo VR(w)) of
and M 1=1 [VV)(()) (w)) S 2
Assumption 3: (Gradients are bounded) IVFIIS
Assumption 4: (L-smoothnesss) Vi [M), the gradient is L-smooth, / [w) VF(W') <
Assumption 5: (Bounded Staleness) The staleness of stragglers t 7, where represents current global epoch and represents the global epoch when the client last synchronized with the server, is bounded { S Tmaz,1 which is the maximum across all the clients.
Choosing constant local learning rate vi and global learning rate fg such that n +. the global model iterates in KUIPER are bounded by
T-1 Σ
2F
L no + 3L2Q2 ing
BIllf(ww))
NT +
- man,K K + 1)
(5)
2
where F* == =²= of o² G². of and o' are the new bounds of local and global variance, and G' the updated norm of gradients when the gradient updates scaled by s(-) and e(-). Q is the number of local iterations for a client, and T the total number of global iterations. Further, choosing // (0/1//K/TT and f2 O(K), for all ng y satisfying fy n < I and sufficiently
9
5

---

Under review as a conference paper at ICLR 2023
large T, we have
F [Vf((m)) & 50 "TQQ"" + O(
of VTQ V 0
Qo TK + 0
Qo"2 maxx1
(6)
TK²
For sufficiently large T, the algorithm achieves the convergence rate shown in Eq. (10). We provide a detailed proof in the Appendix I. As we can see, the convergence guarantee increases with increasing K as tend go closer the synchronous aggregation. Also, non-IID bias increases, gradient variances increase, and weakens the convergence guarantee.
IMPLEMENTATION
The central server in the following experiments has an NVIDIA Tesla V100S 32GB GPU. We use four types of mobile GPU-equipped clients demonstrate that our asynchronous federated optimization is robust to heterogeneous edge devices: NVIDIA Jetson Nano, which has 4GB memory, and a 128-cor Maxwell GPU; NVIDIA Jetson 7X2, which has 8GB memory, and a 256-core Pascal GPU; NVIDIA Jetson Xavier NX, which has a 8GB memory, and a 384-core Volta GPU with 48 Tensor cores; and NVIDIA Jetson AGX Xavier, which has 32GB memory and 512-core Volta GPU.
We use two different setups where M (Number of clients) = 4 and K (Burst size)= = 2, and M=12 and K=4, For M=4, we use one device each from the above categories of devices, and for the M=12 setup,
three devices each from the above categories.
The Kinetics Kay et al. (2017) dataset, which we use for knowledge distillation, present at the central server. We conduct experiments on two datasets for finetuning: HMDB51 Kuehne et al. (2011) and UCF101 Soomro et al. (2012). This data distributed amongst the clients. The Kinetics dataset contains 400 human action classes, with at least 400 video clips for each action. Each clip lasts for around 10s and is taken from a different YouTube video. The dataset has 306,245 videos, and is divided into three splits: one for training, with 250-1000 videos per class; one for validation, with 50 videos per class; and one for testing, with 100 videos per class. The HMDB51 dataset contains 51 classes and a total of 3,312 videos. The UCF101 dataset consists of 101 classes and over 13K clips (27 hours of video data). We use the HMDB51 dataset for all experimental purposes unless otherwise stated. The model was trained using a learning rate of 0.001, staleness penalty a of 0.5, mixing parameter 3 of 0.7 (Appendix D), batch size of 8 video clips, for 200 global iterations with 3 local epochs per client. We show our algorithm's 's scalability recognition and next-word prediction tasks with other methods.
large number of clients for image
EXPERIMENTAL EVALUATION
In our evaluation, we ask, and answer, the following questions order: (1) Is FL feasible for the heavyweight task of video action recognition on embed- ded devices? Is Knowledge Distilla- tion useful for this? (2) How does KUIPER compare in terms of accuracy and time to train vis-à-vis the state- of-the-art in FL with heterogeneous clients, namely, FedAsync Xie et al. (2019), FedBuff Nguyen al. (2022), and Oort Lai et al. (2021). (3) What is the effect of the Burst Size (K) on ac- curacy and time to train KUIPER and the two baselines, FedBuff and Oort? (4) What is the effect of slow client, on KUIPER as well as the two base- lines, FedBuff and Oort? (5) Ablation study of KUIPER showing the effect
45
40
40
35.
30-
Acc 35
25.
20
20
15
sCc
I dlient scc
clicnt acc
Non-iid (4) device setup-
Nos-id blas
16: device setup HMODSS
Figure 2: Validation accuracy achieved by KUIPER as compared to individually trained clients across varying degrees of non-lII bias on HMDB51. Fig. (a) and (b) show the comparison on a 4-device and 12-device setup respectively, as deseribed in Section 4. We observe that the improvement in accuracy achieved with KUIPER increases with higher degree of non-I.Dness.
of each of its components and the hyperparameters a and B..
Is FL useful for action recognition, a computationally heavy task? this experiment, we motivate the use of Fl. in the action recognition scenario (the HMDB51 dataset). We first train each

---

Under review as a conference paper at ICLR 2023
50
50
30
Acc
Centralized training
Acc
Centra lize training
Centrelized training
20
FedAsync
20
RodAsync
20
FedAsync
FedBuff
FedBuff
FedBuff
10
Oort
10-
Oort
10
Dart
Kuiper
(US)
Kuiper (Us)
Kuiper (Us)
0.0
0.5
0.8
0.9
1.0
0.0
0.5
0.9
1.0
0.0
0.5
Non-lid bias
Non-lid bias
Non-iid bias
(a) device setup-HMDB51
(b) 12 device setup-HMMDB51
(c) device setup-UCF101
Figure 3: Comparison of KUIPER with the FedAsyne, FedBuff, and Oort baselines for varying non-IID bias. Figure shows the comparison when the training was done on a 4-device setup with HMDB51 dataset. Figure (b) on a 12-device setup HMDB51 dataset(sce Section 4), and Figure (c) on a 4-device setup with the UCF101 dataset. KUIPER achieves a higher validation accuracy across all non-IID bias values in all the setups. The change in relative accuracy for KUIPER compared to the baselines gets better with higher non-IID bias also carefully consider data quality. KUIPER outperforms Oort and FedBuff in absolute accuracy when non-III bias=1.0 by (a) 5% and 8% (b) 9% and 12% (c) 9% and
Sutup-1
Secup.2
25
action recognition
26
24
35
20-
FodAsync
FudAaynkc
Cart
Dort
Yulper
0053
Kuipor
(U3)
25
30
50
100
10U
Number clients 18) Nor-ID 0.0
Nur of clients (c) Compartson between setup-1 and setup-
Non-lD
Figure 4: Accuracy achieved with different number of clients on HMDB51 dataset. Here K 10 is fixed across KUIPER, FedBuff and Oort. (a) non-iid accuracy than other baselines. For a non-iid value of 0.5 and with an increasing number of devices, achieved accuracy approaches to a random guess accuracy which is number of classes" Accuracy achieved with different number of clients on HMDB51 dataset. Here K 10 is fixed across KUIPER, FedBuff and Oort. (c) Comparison between Setup-1 and Setup-2. In Setup-1, increasing client means fewer samples per client; thus, accuracy decreases with the increasing number of clients. In Setup-2, increasing client means increase in the training data, and thus accuracy increases with the increasing number of clients.
(b) non-iid 0.5. KUIPER achieves higher
client's model its data without collaboration for 50 epochs where the non-IIDness of the data distribution among the clients is varied. We report each client's 's validation accuracy Figure and compare it with that achieved with our aggregation technique in buffered asynchronous FL setting. Error bars correspond to minimum and maximum individual accuracy among the clients and the curve shows the mean accuracy across the clients. We observe clear improvement in accuracy when KUIPER is used, as compared to the accuracy of each client, motivating the use of FL. The improvement becomes more marked with higher non-lID bias. An improvement of up to 15% and 8% was observed for two setups involving and 12 clients, respectively.
Baseline comparison Previous asynchronous aggregation methods like FedAsync Xie et al. (2019). penalize all the lagging clients uniformly without considering the data quality a client holds. This usually leads to under-utilization of a client's 's updates and the system suffers an accuracy drop. FedBuff Nguyen et al. (2022) does not consider the quality the data that clients have. Oort Lai et al. (2021) considers both forms of utility of client how resource rich it is and how valuable is its data - to decide on client selection. However, once chosen, it gives the same weight to all clients' updates. With KUIPER, perform better than the three baselines for both HMDB51 and UCF101. Experiments are performed with and with 12 devices, following the setup described in 4. We vary the non-llI bias and observe that the improvement over all baselines increases with increasing non-IID bias as shown in Figure 3.
appropriately balance the delay penalty and data quality reward and thus

---

Under review as a conference paper at ICLR 2023
50
17.5
Shukespare: 1A
15.2
-41
$2.5
00
27.
30.0
4.2
Festhege
FosAsanIc Iediart
FosAsync
5.0
RedAaync
Fectfutt
Cort
Number of Clarbs
Kulper (115)
Ocit
Number of Clients
100
1000
30
Kulcer (1.4)
Octt
Redtlatt
Number of Cilents CIFARILO
150
1000
2.5
0.6
10
Kitoor 10:0
Quit
Number Cilenss
Shataspeare
100
1000
(D] FHISST
Figure 5: Scalability: Comparison of KUIPER with other methods on different tasks. Image recognition on a) MNIST b) FMNIST c) CIEAR10, and d) Next character prediction task on Shakespeare dataset.
Large number of clients In this section, to analyze the scalability of KUIPER, we propose two different setups: Setup-1: Data samples per client decreasing with increasing number of clients: Here, the total number of data samples is constant in every run, and with an increasing number of clients, we partition the dataset equally among the clients. For example, HMDB51 datasets have 8062 samples when we have eight frames per clip. When we consider four clients, each client gets 2013 data samples. For 100 clients, each client gets around 80 samples. With 80 data samples per client, we get around 1-2 samples per class when we have iid distribution. It gets challenging to train models on such small data samples, and we can see the achieved test accuracy decreasing with an increasing number of clients (Figure 4 setup-1), 1). Due to this reason, we limit our analysis to a maximum of 100 clients. Figure 4 (b) validates how even with 50 clients and 0.5 non-iid bias value, it is not possible to train the model as achieved accuracy is equivalent to random prediction accuracy.
Scalability:
Setup-2: Data samples per client increasing with increasing number of clients: In real- world scenario, more clients bring more data and thus help learn a model with good feature representation, which we have tried to mimic in this setup. In this section, unlike decreasing samples, 50 data slices from the total data. We assign one to every participating client. So, in this setup, if 20 clients participate, we have 40% of the total dataset in that training experiment. So, total training data increases with increasing clients as it should be in a real-world scenario. (Figure 4 Setup-2).
first create
Comparative performance other tasks In Figure 5, we show how KUIPER performs compared to other methods with up to 1,000 devices. Shakespeare dataset is used for the next-character prediction task. We have used perplexity loss (lower the better) for comparison (Figure 5 (d)). We used MNIST, FMNIST, and CIFAR 10 datasets (Figure 5 (a, b, c)) for the image recognition task. We use accuracy metric for the comparison here. We thus see that KUIPER is scalable solution and the advantage of KUIPER over the state-of-the-art baselines is maintained even at large scales.
Effeet of burst size (K) parameter We show the effect of varying Burst Size (K) on KUIPER as well as the two baselines, FedBuff and Oort (Figure 6) (this is a 12-device experiment HMDB51; UCF101 analyzed in the Supplement). As K becomes higher, the protocols become closer to synchronous aggregation. We see that KUIPER outperforms others for any given value of K. Another way of looking at this is that to reach the same accuracy as KUIPER, FedBuff and Oort will need higher values of K. Consequently in Figure 6(b), we see that the time taken to reach given accuracy is lowest in KUIPER. In Figure 6(c) we see that a synchronous approach like Oort takes much longer per aggregation round compared to FedBuff and KUIPER (KUIPER being slightly lower than FedBuff). This is due to Oort always waiting for the K chosen clients in each epoch.
Effect of stragglers A straggler is a slow client and we incorporate their inputs in our aggregation technique by weighing the updates in accordance with their staleness and quality as described in Section 3. Figure 12 (a, b) compares the two setups where all four devices are homogeneous (NX)) vs. three devices are the same (NX), and one slow device (Nano) is there. Updates of this device are delayed and thus stale. With a slow device, accuracy decreases (Figure 12 (a)), and the time taken to reach a specific accuracy increases. Here, note that Oort waits explicitly for the K clients depending on their utility scores, and waiting for the delayed client makes Oort slower than FedBuff even though it was faster in the homogeneous case (Appendix G).
Figure 7 (a, b) shows the analysis with 12 clients, with no delay, 4 with 3x delay, and 4 with 5x delay- - these delays are a multiple of the natural delay. The delay ratios have been chosen in order to mimic a realistic scenario. For example, the Jetson Nano device is ~ 5X slower, and the Jetson TX2 device is ~ 3X slower than Jetson AGX Xavier. For (a) the aggregation technique used is KUIPER in all the cases. Here, 8 with delay means, 8 devices are aggregated and 4 slowest are dropped. From
8

---

Under review as a conference paper at ICLR 2023
Time taken (mins) to reach 40% accuracy
FedBuff
FedBuff
Iime taken (mins) per aggregation
40
Cort
400
Oort
Kulpee (Us)
Kuiper (Us)
Accurecy (%)
30
300
4-
20
200
10-
100
(a) Accuracy comparison with different
K-2
Different values for nild-0.8
K=4
K=
Differant methods for n.id-0.8
FedBuff Kuiper
K-7 K-6 K-4
Different K values for nidd (c) Time taken per aggregation round
K-2
K=4
K-6
(b) Time-to-reach 40%
Figure Comparison of KUIPER with baselines Oort Lai al. (2021) and FedBuff Nguyen et al. (2022). (a) shows the effect of the parameter K on the accuracy. As we increase K, it gets more synchronous, and thus accuracy increases, but the time taken for each round increases. (b) shows time taken to reach 40 % accuracy. Here, Oort is using K=6 and FedBuff K=7 because they didn't achieve 40 % accuracy with K=4. KUIPER 11 % faster than Oort and 10% faster than FedBuff. (c) Time taken per aggregation round. As we increase K, time taken for each aggregation round increases. Oort waits for specific K clients but FedBuff and KUIPER aggregate the first K clients thus taking less time per aggregation.
this we conclude that dropping large numbers of stragglers hurts performance. The overall results from (a) and (b) show the robustness of KUIPER in the presence of stragglers across the entire range of non-IIDness in data, without any significant drop in the validation accuracy and is not much below the ideal accuracy case of "Sync 12 homogeneous devices". All the other baselines degrade much faster than KUIPER, with increasing non-lID bias.
TAKEAWAYS
Here we have solved heavyweight ML task, distributed action recognition, on edge devices with mobile GPUs using asynchronous FL as we have shown synchronous FL heavily suffers with the stragglers problem. We have considered a realistic scenario where all the clients might not have samples from each class (non-lII data distribution). Given the scarcity of the previous literature in asynchronous FL on heterogeneous and
40
30
20
12 delay
35.0
12 with dalay
10
with delay
delay
30.0
$13
FodBoftt devics
devices
no delay
25.
Euquer (Fi) diniiess
edge devices, we have proposed a new method called KUIPER, which is designed to handle both non-IID differences and heterogeneity in network speed and com- pute power of the clients. A unique design idea that we have developed in K KUIPER is to consider both the speed of clients as well as the intrinsic value of the data at each client, when perform- ing aggregation of gradient updates from each client. We have seen that a pure asynchronous approach does not work well and hence we have introduced a buffering strategy with a customizable "burst size" leading to a buffered asynchronous FL approach. We present a convergence proof of our approach, extending the analysis of FedBuff. Then, we empirically see that our KUIPER solution produces more accurate results on HMDB51 than the baselines (9% better than Oort, 12% than FedBuff, and 9% than FedAsync). For a comparable buffer size to reach the same accuracy, we are 11% and 10% faster than Oort and FedBuff respectively. Importantly, with hyperparameter tuning, we show that the per-elip accuracy achievable for buffered asynchronous federated learning (46.15%) is comparable to the case of central server (47.8%) with no clients. Thus, we for the first time empirically show that it is possible to achieve activity recognition edge devices that are already available for general release today. In future work, one may consider how to handle non-iid data in a personalized way to help cater to the specific needs of clients. One should also consider the effect of non-IlDness in feature space rather than just in classes.
Non
0.8
3U 1L.
Mar
(a) Dropping slow devices
Figure 7: Figures (a) and (b) show results on a 12 device setup: 4 devices with no delay, 4 with 3x delay, and 4 with 5x delay. Validation accuracy achieved when a straggler's updates are dropped as compared to (a) different delays (5x, 3x, no delay) and (b) weighing the stale updates in KUIPER. Highest validation accuracy is achieved by KUIPER because it considers updates from all clients. The improvement in accuracy increases with high non-IIDeess.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rohan Anil, Gabriel Pereyra, Alexandre Passos, Robert Ormandi, George Dahl, and Geoffrey Hinton. Large scale distributed neural network training through online distillation. arXiv preprint arXiv:1804.03255, 2018.
Yiqiang Chen, Xin Qin, Jindong Wang, Chaohui Yu, and Wen Gao. Fedhealth: A federated transfer learning framework for wearable healthcare. IEEE Intelligent Systems, 35(4):83-93, 2020a.
Yujing Chen, Yue Ning. Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In 2020 IEEE International Conference on Big Data (Big Data), pp. 15-24, IEEE, 2020b.
Sannara Ek, François Portet, Philippe Lalanda, and German Vega. Evaluation of federated learning aggregation algorithms: application to human activity recognition. In Adjunet Proceedings of the 2020 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2020 ACM International Symposium on Wearable Computers, pp. 638-643, 2020.
Kai Han, Yunhe Wang, Qi Tian, Jianyuan Guo, Chunjing Xu, and Chang Xu. Ghostnet: More features from cheap operations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1580-1589, 2020.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. NIPS 2014 Deep Learning Workshop, 2015.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.000 2019.
Ingook Jang, Hyunseok Kim, Donghun Lee, Young- Sung Son, and Sconghyun Kim. Knowledge transfer for on-device deep reinforcement learning in resource constrained edge computing systems. IEEE Access, 8:1 16588688-00 144486814659777 2020.
Eunjeong Jeong, Seungeun Oh, Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong-Lyu Kim. Conmuniiationn-effcccenn on-device machine learning: Federated distillation and augmentation under non-iid -id private data. arXiv preprint arXiv:1811.11429 2018.
Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al. The kinetics human action video dataset. arXiv preprint arXiv: 700. 079500 2017.
Hildegard Kuehne, Hueihan Jhuang, Estíbaliz Garrote, Tomaso Poggio, and Thomas Serre. Hmdb: a large video database for human motion recognition. In 2011 International conference on computer vision, pp. 3566.2563. IEEE, 2011.
Fan Lai, Xiangfeng Zhu, Harsha V. Madhyastha, and Mosharaf Chowdhury. Oort: Efficient fed- erated learning via guided participant selection. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2/), pp. 19-35. USENIX Association, July 2021. ISBN 978-1-9331133-2--9, URL https:/ /wwwwwww. usenix org/ confereence/osdi2211 presentation/1es /la..
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):2278-233) 22244, 1998.
David Leroy, Alice Coucke, Thibaut Lavril, Thibault Gisselbrecht, and Joseph Dureau. Federated learning for keyword spotting. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6341-6344 IEEE, 2019.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated Iearning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450 2020b.
10

---

Under review as a conference paper at ICLR 2023
Wenqi Li, Fausto Milletari, Daguang Xu. Nicola Ricke, Jonny Hancox, Wentao Zhu, Maximilian Baust, Yan Cheng, Sébastien Ourselin, M Jorge Cardoso, et al. Privacy-preservnnn federated brain tumour segmentation. In International workshop on machine learning in medical imaging, pp. 133-141. Springer, 2019.
Nil Llisterri Giménez, Mare Monfort Grau, Roger Pueyo Centelles, and Felix Freitag. On-device training of machine learning models on microcontrollerss with federated learning. Electronics, 11 (4):573, 2022.
Yoshitomo Matsubara, Davide Callegaro, Sabur Baidya, Marco Levorato, and Sameer Singh. Head network distillation: Splitting distilled deep neural networks for resource-constrained edge com- puting systems. IEEE Access, 8:212177-212195 2020.
Brendan McMMaan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efffcieett 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-effiienn federated learning for wireless edge intelligence in iot. IEEE Internet of Things Jourmal, 7(7):5986-577 5994, 2019.
Jed Mills, Jia Hu, and Geyong Min. User-oriented multi-task federated deep learning for mobile edge computing. 2020.
Seyed Iman Mirzadeh, Mehrdad Farajtabar, Ang Li, Nir Levine, Akihiro Matsukawa, and Hassan Ghasemzadeh. Improved knowledge distillation via teacher assistant. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5191-5198, 2020.
John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Michael Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In The 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Suneth Ranasinghe, Fadi Al Machot, and Heinrich C Mayr. A review applications of activity recognition systems with regard to performance and evaluation. International JoartinnnnnJJunnad of Distributed Sensor Networks, 1508)
2016.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-efficceen federated learning method with periodic averaging and quanti- zation. In International Conference Artificial Intelligence and Statistics, pp. 2021-2031. PMLR, 2020.
Felix Sattler, Simon Wiedemann, Klaus-Rober Müller, and Wojeiech Samek. Robust and communication-efiiieenn federated learning from non-iid data. IEEE transactions on neural networks and learning systems, 3109)3340-3443, 2019.
Virginia Smith, Chao-Kai Chiang. Maziar Sanjabi, and Ameet Talwalkar, Federated multi-task learning. Proceedings of the 31 International Conference on Neural Information Processing Systems (NeurIPS), pp. 4427 4437, 2017.
Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah. Ucf101: dataset 101 human actions 2012.
classes from videos in the wild. arXiv preprint
Konstantin Sozinov, Vladimir Vlassov, and Sarunas Girdzijauskas. Human activity recog- nition using federated learning. In 2018 IEEE Intl Conf on Parallel & Distributed Pro- cessing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking. Sustainable Computing & Communications CtW.CCCC//DDCouuuSSaaaaCCC/oaa..
pp. 1103-1111, IEEE, 2018.
Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. Patient knowledge distillation for bert model compression. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP. IJCNLP), pp. 4314-432 2019.
11

---

Under review as a conference paper at ICLR 2023
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 10734-10742, 2019.
Cong Xie. Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. 12th Annual Workshop Optimization for Machine Learning (OptML), pp. 1-11, 2019.
Zirui Xu, Zhao Yang. Jinjun Xiong, Jianlei Yang, and Xiang Chen. Elfish: Resource-aware federated learning heterogeneous edge devices. arXiv preprint arXiv:1912.01684, 2019.
Ozgur Yurur, Chi Harold Liu, and Wilfrido Moreno. A survey of context-aware middleware designs for human activity recognition. IEEE Communications Magazine, 52(6))24-31, 2014.
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 6848-6856 2018
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint //0iv:/806.000 0058, 2018.
APPENDIX
INTRODUCTION
In the supplementary material, show the following:
Link to our anonymized source code repository
Algorithm
Scalability of KUIPER: Performance with large number of devices (M=1000)
Experiments on the UCF101 dataset with the 12-device setup
Effect of number of clients and non-IID bias in final accuracy
Effect of number of frames per clip in final accuracy
Systematic delay experiment with the 4-device setup
Knowledge distillation and effect of TA
Convergence proof of KUIPER
A SOURCE CODE
We provide the source code of KUIPER at https://anonn/n sciencercieee//// vddact_ccde-75111 We have described in the README file how the edge devices can be prepared for running KUIPER.
12

---

Under review as a conference paper at ICLR 2023
B ALGORITHM
Algorithm 1 KUIPER
1: T: total iterations, [1, K]: counter for clients reported in burst, oy: set of clients in burst, ny: samples present on ith device.
17:
w new,
f- new.
N
18:
Tht
19t
K
19:
Be x- I (( .(-) is function
2: Server
of the staleness
3: Initialize WP from Knowledge Distillation model.
20:
wi + (1- 3 yu 1- + Pi w new
4: for t = 1 to to do
21:
send w client Vj E Ct
22: w + 0, h + 0. t 0,0, + f
5: if Receive (whew,ti r!) from any client
23: end if
then
24: end for
6:
if To then 7: Wnewnt <- nh w Wnen x se(acctrain) )
25: Client
26: for i E {l...., n in parallel do
8:
else
9:
nnew, f nhi w wnew. end if
Ct
27: receive global model and time stamp (wf,t)
11:
+ 4 UU {i} Tot t 7Ct +T
28: 2- L, w f- we
29: for local iteration h = 1: H do
30: Wh +- Wh-1 V ywn.
13:
k k + +1 N N N + Ybs
31: end for
14:
32: Send (WH; r) to the server
15:
end if
33: end for
16:
if = K then
C UCF101 EXPERIMENT FOR 12-DEVICE SETUP
Figure 8 shows the 12-device experiment on UCF101 dataset with K complementing the experiment (shown in Fig. 3(b) of the main paper with the HMDB51 dataset). This experiment compares KUIPER with the other three baselines FedAsync, FedBuff, and Oort. As KUIPER appropriately balances the delay penalty and data quality reward, it performs better than the other baselines. It is also interesting to observe that Oort takes more time than FedBuff when non-iid bias is zero. This is because it waits for specific clients according their statistical utility and all the clients have the same data distribution in an iid setting. However, when the non-iid bias is 0.8, Oort takes less time than FedBuff reach 25% accuracy selecting the specific clients with more useful data helps to aggregate better global model (Figure 8 (b)).
D KUIPER COMPONENTS AND HYPERPARAMETERS
Figure (a) shows how each component KUIPER affects the accuracy. When non-iid=O (iid case), the еттог reward term is not improving any accuracy as the data among all the clients is IID and the model can equally learn from any client. Figure 9b, c) shows the effect of staleness penalty a and mixing hyperparameter 3. For higher non-lII bias, increasing reduces accuracy drastically (4% for non-IID=0.5 and 8% for non-IID=O.80 0.)); when we change a from 0.7 to 1.0, slow clients have exclusive data, and global model can learn even from the stale gradients. & controls how much the global model should change with the new model updates. We find expectedly that too slow a change well too fast change hurts accuracy.
E EFFECT OF NON-IID BIAS AND NUMBER OF CLIENTS
Figure 10 shows how accuracy changes with different numbers of clients and non-lID bias. We have shown this analysis for three image recognition datasets (MNIST, FMNIST, and CIFAR10). For high number clients, increasing non-IID bias results in a drastic decrease in the accuracy compared to the case where the number of clients is low.
13

---

Under review as a conference paper at ICLR 2023
Time taken (mins) to reach accuri
40
500
400
30
Acc %
Centralized training
300
FedAsync
FedAsync
20
FedBuff
200
FedBuff
10
Oort
Oort
100
Kuiper (Us)
Kuiper (Us)
0
0.0
0.8
0.0
0.8
Non-iid bias
Non-iid bias (b) Time to accuracy
(a) Accuracy achieved
Figure 8: Comparison KUIPER with the FedAsyne, FedBuff, and Oort baselines for 12 device setup for UCF101 dataset (a) Accuracy achieved with different non-iid bias values and (b) Time taken to reach accuracy of 25 % when non-iid bias is 0 and 15% when non-iid bias is 0.8. KUIPER achieves higher accuracy and takes less time to reach the accuracy than the other baselines with low and high non-iid value.
10
40
30
Acc
20
36
34
Penalty
32
10
Stalaness penally
neward
1id = 0.5
nidd 0.5
Stalonedo Error Roward Burs:
0.0
0.5
0.8
0.9
1.0
0.0
0.2
0.6
1.0
0.2
0.G
1.0
Nonild blas
Alpha va lues
Beta values (c) Fffort of mixing hyperparameter
(3) Incremental changes (our nour_name] (Us
(b) Fffect of stal enneessss ponalty paramoter
Figure (a) Performance improvement due each of three design elements KUIPER, Effect a: non-IID factor increases (0.5 to 0.8), penalizing from a=0.7 o=1.0 shows significant drop accuracy, (c) Effect of 3 parameter with varying non-iid bias. When 9=0. the model is stuck with the initial weights and prediction is random. Too high 3 causes drop in accuracy.
F EFFECT OF NUMBER OF FRAMES PER CLIP IN FINAL ACCURACY
Figure 1l shows how accuracy changes with the number of frames. With more frames per video, is easier for the model to recognize the action, and thus accuracy increases as the number of frames per video increases. Due limited computational resources, we cannot increase the number of frames and thus fix it to 8 frames for the HMDB51 dataset and 32 for the UCF101.
G EFFECT OF STRAGGLERS: DELAY EXPERIMENT
Figure 12 shows how the inclusion of heterogeneous devices changes the training trajectory. Figure 12 (a, b) compares the two setups where all four devices are homogeneous (NX)) vs. three devices are the same (NX), and one slow device (Nano) is there. Updates of this device delayed and thus stale. With a slow device, accuracy decreases (Figure 12 (a)), and the time taken to reach a specific accuracy increases. Here, note that Oort waits explicitly for the K clients depending their utility
14

---

Under review as a conference paper at ICLR 2023
100
60
80
50
80
40
Acc %
Acc %
30
40
40
20
20
Non-iid bias:
20
Non-iid bias: 0.0
Non-iid bias: 0.0
Non-lid lid bias: 0.5
Non-lid blas:
10
Non-lid blas: 0.5
Non-lid bias: 0.8
Non-lid bias: 0.8
Non-lid bias: 0.8
10
100 1000
0
10
100
1000
0
10
100 1000
Number of clients
Number of clients (b) FMNIST
Number of clients (c) CIFAR10
(a) MNIST
Figure 10: Changing accuracy with changing number of clients and Non-IID bias for (a) MNIST (b)
FMNIST (c) CIFAR1O
60
50
50
40
40
Acc %
Acc %
30
30
20
20
10
10
Centralized training
Centralized training
0
0
4
16
24
32
4
8
16
32
48
Number of frames
Number of frames
(a) Accuracy vs #frames-HMDBB1
(b) Accuracy vs #frames-UCF101
Figure 11: Centralized training with different number of frames for (a) HMDB51 and (b) UCF101. Accuracy increases the number of frames per video increases.
scores, and waiting for the delayed client makes Oort slower than FedBuff though it was faster in the homogencous case
Figure 13 shows the effect of delay in 4-device setup, similar to Fig. d) in the main paper. In this experiment, 1x, 3x, 5x delays are a multiple of natural delay. The delay ratios have been chosen in order to mimic realistic scenario, described in "Effect of stragglers" in Experimental Evaluation section of the main paper. Here, the accuracy when the slowest device is dropped, is comparable to others for non-iid values of O and 0.5, but it gets drastically reduced for 0.8 non-iid value. Because
15

---

Under review as a conference paper at ICLR 2023
175
40
Time to reach 38% (mins)
150
125
30
Acc %
100
20
75
FedBuff
FedBuff
Oort
Oort
Kuiper (Us)
Kuiper (Us)
4 NX 3 NX+
NX 3 NX
1Nano
1Nano
(b) Time taken experiment w/ and w/o delayed device
(a) Accuracy experiment w/ and w/o delayed device
Figure 12: Comparison when all four devices homogeneous three devices homogeneous and one device slow, (a) Accuracy achieved with three different methods (b) Time taken reach 38% accuracy in two setups.
45
30
44
Acc %
Acc
43
20
devices
42
FedAsync: 4 devices
No Delay
FedBuff: 4 devices
10
Delay 3x
Oort: 4 devices
Delay 5x
*
Sync homogeneous devices
Dropped slowest
Kuiper (Us): devices
0
0.0
0.4
0.5
0.6
0.7
0.8
0.9 1.0
0.0
0.2
0.4
0.6
0.8
Non-iid bias
Non-iid bias
(a) Dropping devices
(b) Synthetic delay comparison
delay, one with 3x delay, one with 5x delay. Validation accuracy achieved when a straggler's updates are dropped as compared to (a) different delays (5x, 3x, Ix, no delay) and (b) weighing the stale updates in KUIPER. Highest validation accuracy is achieved by KUIPER because it considers updates from all clients. The improvement in accuracy increases with high non-tidness.
Figure 13: Four device sctup: one devices
delay, one
with high non-iid value, clients get more data some specific classes and losing that client means losing the training data for that class (Figure 13(b)).
H KNOWLEDGE DISTILLATION
In the first stage of our pipeline, perform knowledge distillation from larger model, trained on the Kinetics dataset. We compare three approaches in order to validate using knowledge distillation with an intermediate TA. For these experiments, an SGD optimizer with a weight decay 0.001 and momentum 0.9. In the first experiment, we train a ResNet- 18 model from scratch the Kinetics dataset and the per-clip top-1 accuracy achieved is
use batch size of 128, learning rate 7) 0.1, and
16

---

Under review as a conference paper at ICLR 2023
Table 1: ResNet-18 training time per epoch. For HMDB51 and UCFI01, each client has approximately 500MB and 1.73GB of video data respectively
Dataset
Device
Train Time (per local epoch)
HMDB51
NVIDIA Jetson Nano
391.1 1 seconds
HMDB51
NVIDIA Jetson TX2
293.1 seconds
HMDB51
NVIDIA Jetson Xavier NX
121.3 seconds
HMDB51
NVIDIA Jetson AGX Xavier
84.5 seconds
UCF101
NVIDIA Jetson Nano
2691.6 seconds
UCF101
NVIDIA Jetson TX2
2001.4 .4 seconds
UCF101
NVIDIA Jetson Xavier NX
821.9 seconds
UCF101
NVIDIA Jetson AGX Xavier
572.1 seconds
Table 2: ResNet-18 evaluated on the entire test dataset. The device heterogeneity is reflected in the inference times
Dataset
Device
Test Time
HMDB51
NVIDIA Jetson Nano
181.4 seconds
HMDB51
NVIDIA Jetson TX2
116.3 seconds
HMDB51
NVIDIA Jetson Xavier NX
89.4 seconds
HMDB51
NVIDIA Jetson AGX Xavier
68.3 seconds
UCF101
NVIDIA Jetson Nano
621.3 seconds
UCF101
NVIDIA Jetson TX2
381.2 seconds
UCF101
NVIDIA Jetson Xavier NX
322.5 seconds
UCFI01
NVIDIA Jetson AGX Xavier
217.7 seconds
50.2%. Using knowledge distillation, the accuracy improved to 53.8% when we distill directly from ResNet-34 to ResNet- 18, and 54.6% when we use ResNet-26 as the intermediate TA between the teacher and student. From Figure 14, it is evident that using distilled ResNet-18 better than using a ResNet-18 18 trained from scratch. There is counter pull from the training time - the KD approach (discounting the time to train the ResNet-34) takes 43% longer than training from scratch (ResNet-18)) This can be explained by the fact that "Train from scratch" includes only forward- -eraard-bacwarddd passes on ResNet- 8 with optimization using only cross-entropy loss. On the other hand, KD involves forward passes on the larger ResNet-34, forward-backwarr passes ResNet-18, 18, and optimization on ResNet-18 18 using a combination of both cross-entropp loss and the MSE on the logits (recall that we are fine-tuning only the last FC layer). This timing result is consistent with prior works that report on the timing performance of knowledge distillation Hinton et al. (2015); Sun et al. (2019).
We further investigate using multiple TAs. From Table 4, see that the introduction of one TA increases the train time from 44 hours 58 minutes to 55 hours 23 minutes and the corresponding increase in per-elip accuracy is 0.8%. Hence, there is trade-off between increased training time and increased accuracy. Furthermore, the introduction of TA almost always increases accuracy but the optimal number of TAs and size of each an open research question Mirzadeh et al. (2020). Additionally, TAs are used to bridge the gap between the student and teacher: by using ResNet-26 between ResNet-34 and ResNet-18 we already accomplish this. If the gap between the teacher and student were larger, using additional TAs would be of benefit at the expense of increased computation and train time required. In order to reduce the train times and achieve comparable accuracy to the baselines, we one TA.
From Figure 14, we conclude that using KD does give an improvement to all FL algorithms, with the improvement being most significant for FedAsyne (a 6% increase). KUIPER enjoys an improvement of 3%.
We further investigate the effects of using additional TAs in our pipeline.
In all these experiments, distillation is performed from teacher ResNet-34 to student ResNet- 18. In the first experiment, we do not any TAs. In the next experiment, we use ResNet-26 TA. The
17

---

Under review as a conference paper at ICLR 2023
Acc vs Epoch
40
Vanilla
Knowledge distillation
0.50
35
Knowledge distillation with TA
30
25
Acc
20
0.25
15
Async
10
FedBuff
5
Oort
Kuiper (Us)
0
without KD with KD
Offect KD
100
200
Epoch
Figure 14: (a) Accuracy the Kinetics validation dataset for 3 experiments: 1. Training ResNet-18 from scratch (Vanilla); Knowledge distillation from ResNet-34 to ResNet-18 (Knowledge Distillation with no TA); 3. Knowledge distillation with ResNet-34 Teacher, ResNet-26 TA, and ResNet-18 Student (Knowledge Distillation with TA) (b) Ablation study to show the importance of KD (Knowledge Distillation).
Table 3: Knowledge distillation performed by varying number of intermediate Teaching Assistants (TAs)
TAs
Epochs
Time (hrs, mins) (Inerease)
Per-Clip Accuracy
0
200
44 58 m (0%)
53.8%
200
55 h 23 m (23.2%)
54.6%
2
200
69 h 35 (54.7%)
54.8%
3
200
85 47 m (90.8%)
54.9%
18

---

Under review as a conference paper at ICLR 2023
conv 7x7x7, F 64
conv 7x7x7, F 64
conv 7x7x7, F
pool
pool
pool
Conv 3x3x3,
Resnet BasicBlock,
Resnet BasicBlock, F
Resnet BasicBlock, F
ReLLU
Resnet BasicBlock, F= 128
Resnet BasicBlock, F 128
x
Resnet BasicBlock, F 128
x2
Conv 3x3x3,
Resnet BasicBlock, F 256
x6
Resnet BasicBlock, F 256
x
Resnet BasicBlock, F 256
x2
BN
Resnet BasicBlock,
x Resnet BasicBlock, 512
x2
Resnet BasicBlock, F 512
x2
BlX
avg pool
avg pool
avg pool
B(X) +
Figure 15: (a) The central server first performs knowledge distillation using the Kinetics dataset: from teacher to teaching assistant (TA) and from TA to student. The students (compressed models) are then fine-tuned on the smaller dataset using an asynchronous federated optimization. (b) ResNet-34, ResNet-26, and ResNet-18 architectures derived from the basic building block.
Acc Epoch
ACC vs Epoch
maa
4
0.6
byoch
Figure 16: Central server: ResNet-18, distilled from ResNet-34, via ResNet-26 Teaching assistant, and fine-tuned on UCF101, performed at central server without any clients (b) ResNet-18 18, distilled from ResNet-34, via a ResNet-26 Teaching assistant, and fine-tuned on HMDB51. The fine-tuning is performed at the central server without any clients
third experiment is performed using two TAs: ResNet-28 and ResNet-24, and in the final experiment, we use three TAs: ResNet-30, ResNet-26. and ResNet-22. The architectures have been outlined in Figure 15. From Table 3, we that while the increase in per-clip top-1 accuracy is appreciable when one TA is introduced, using additional TAs does not produce any considerable improvement in accuracy. The training time increases sharply as more TAs are added. Hence, in the subsequent stages in our pipeline, we chose to use single TA.
For the rest of the experiments, we perform fine-tuning, by reinitializing the fully connected layer the last layer in the ResNet-18 model. The ResNet-18 18 being used is the model distilled from ResNet-34 (trained on the Kinetics dataset) via ResNet-26 TA.
The Kinetics-400 dataset requires approximate disk space of 400GB to store. Amongst the edge devices we are using in these experiments, the most well-endowed, NVIDIA Jetson AGX Xavier has only 32GB storage. Hence, edge devices can only accommodate smaller-sized datasets
Datasets
19

---

Under review as a conference paper at ICLR 2023
Table 4: The time required for various stages shown in Figure 15 (a) and the baseline experiments. KD refers Knowledge Distillation, synchronous refers fine-tuning using FedAvg, asynchronous refers to fine-tuning using asynchronous federated optimization. The fine-tuning is performed using ResNet-18, distilled from ResNett-4 via ResNet-26 Teaching assistant
Dataset
Task
Epochs
Time
Kinetics
Train from scratch
200
31 hrs 26 mins
Kinetics
KD (No ТA)
200
44 hrs 58 mins
Kinetics
KD (TA)
200
55 hrs 23 mins
HMDB51
Fine-tune no clients
80
3hrs 15mins
HMDB51
Synchronous
80
10 hrs 54 mins
HMDB51
Asynchronous
80
hrs 31 mins
UCF101
Fine-tune no clients
80
22 hrs mins
UCF101
Synchronous
80
74 hrs 27 mins
UCf101
Asynchronous
80
44 hrs mins
them'. In this section, we use the HMDB51 dataset and the UCF101 for evaluation. The HMDB51 which has a size of 2,062MB and is distributed amongst the clients in such way that requires approximately 500MB of storage space each client. The UCF101 is 6.9GB and each client has about 1.725GB of data. Once we have distilled knowledge from the larger ResNet-34, trained on the Kinetics dataset the ResNet-18 architecture via TA, the next step is to fine-tune the smaller dataset; i.e., HMDB51 or UCF101.
From Table refer to the HMDB51 experiments. We that the time required for synchronous optimization is 10 hours and 54 minutes. In contrast, the asynchronous federated algorithm takes only 6 hours and 31 minutes, 40% decrease. This can be attributed the clients having different computing resources, and hence requiring different amounts of time to complete the local epochs as given in Table 1. While the synchronous algorithm has wait for the slowest client send its update, the asynchronous algorithm continues its optimization. A similar effect is observed in the case of UCF101.
One may wonder that it is beneficial to use the approach of fine tuning at the server without any clients (for HMDB51 and UCF101) and thus not having to use our approach. This alternate method runs into the problem that it does not leverage federated learning, which has its traditional benefits of scaling to a large number clients (and thus not needing heavyweight server) and preserving privacy of client data. The same argument applies to why we would not want to train for the Kinetics data from scratch (this would obviously have to be done at the server).
I CONVERGENCE PROOF
Here we provide the complete convergence analysis of KUIPER. This analysis is influenced by model. Specifically, have characterized
FedBuff Nguyen al. (2022) and is customized the effect of non-iid bias on gradient variances and the convergence guarantee.
Notation. M denotes total number of clients. (:( (i) denotes stochastic gradient on tth client model with weights w and sampled batch Ç. F.,(w) denotes the gradient with respect to the loss. of and of are local and global variances of the gradients. f(w) is the objective function as described below, and f is its theoretical minima. t is the current iteration count and T; is the global iteration count when ith client received gradients from the server where every client runs Q local iterations before communicating with the server. The objective function is formally defined as
min f(w) W 2
_ Σ F.F)
'One may argue that adding cheap external storage such through Flash cards can alleviate this problem. However, reading from external storage is orders of magnitude slower than reading from internal storage and will thus increase the training time infeasible level.
20

---

Under review as a conference paper at ICLR 2023
where p; is the weight assigned to the updates coming from client i. We make the following assumptions for proving the convergence of KUIPER. Assumptions 1-4 are standard assumptions made for the convergence analysis of any synchronous FL system. Assumption 5 pertains to an asynchronous FL system.
Assumption 1: (Unbiased client stochastic gradients) [lg:(w; G)] = (F)(
Assumption 2: (Bounded local and global variance) Vi E [M], (eiellll: ()) VE(())]
and 37 == [[V ( 112 S og.
m
Assumption 3: (Gradients are bounded) ||VF G.
Assumption 4: (L-smoothnesss, Vi E [M], the gradient is L-smooth, [V] - VF((")) =
L|ww-'|13.
Assumption 5: (Bounded Staleness) The staleness of stragglers / - T, where I represents current global epoch and 7 represents the global epoch when the client last synchronized with the server, is bounded f - T S Tmaz,1 which is the maximum across all the clients.
Theorem 1- Let ( be the local learning rate of client SGD the q-th step, and define ai (Q) == s 1, for all local steps q = 0, ..., Q- 1,
Eq- o and cez(Q) := Eg= (n/ Choosing TiTh (
the global model iterates in Algorithm I achieves the following ergodic convergence rate
2 (f((w) f-)
L a
V (w')l
2 aq) of
(Q)T
+ +3I2Q0z(Q)) (12 maz, + 1) (a + o G)
(8)
Corollary 1- Choosing constant local learning rate nu and global learning rate ng such that Q S J. the global model iterates in KUIPER are bounded by
T-1 T Σ
L QT 2 nonoos + 13 man, + 1)o²2 +
2F
Fllls[(w))
G". In KUIPER, we rescale the client's 's gradients by e(.), which is bounded by 0 at the lower and at the higher end. Specifically, (w) = V (F((w) x e(error;), thus introducing o/, oyg. and G' as the new bounds of local variance, global variance, and norm of gradients when the gradient updates respectively. Q is the number of local iterations for a client, and the total number of global iterations. Further, choosing v = O(1/(K (TQ))) and Mlg = O(K), for all Mg. yn satisfying Q
where F* : ff
< T. and sufficiently large T, we have
Σ T 0=
1 T
F VTQ
) + ( Q0 TK + +0(
Q Tma
(IVS(w))) & O
+ +
(10)
VTQ
TK2
Reacall tha, in KUIPER, we rescale 72 with s(-) that is bounded by 0 at the lower and at the upper end. Specifically, 3 = 77 x s(t - T). The modified global rate 3 is therefore still bounded by O(K) and satisfies the above results. For sufficiently large T, the algorithm achieves the convergence rate as shown in Eq. (10). As we can see, convergence guarantee increases with increasing K as we tend to go closer to the synchronous aggregation. Also, non-iid bias increases, gradient variances increase, and weakens the convergence guarantee. Having described how the two modifications in KUIPER do not affect further analysis, we describe the rest of the formal proof without the two modifications for simplicity.
We now state a useful Lemma that will help us prove the above theorem. Lemma 1- E |?]
(oî + oo + G1), where the total expectation B[:] is evaluated over the randommess with respect to client participation and the stochastic gradient taken by a client.
Proof of Lemma 1- From the law of total expectation have E Ex-(m E C. (k- Hence,
E [1xx(w))
= Fm/ Folk [Iou(w)
FF (w) V (v) V(()]
< 3m [I. (rM.oo/-VVEEoo/----////ooo--/---
= = + +0²+G)
(11)
21

---

Under review as a conference paper at ICLR 2023
We now define Theorem which will use prove Theorem 1.
Theorem 2-
Let mi be the local learning rate of client SGD in the q-th step, and define a1(Q) = Igzo :i
1 Q (2l)) == = (m) )2 Choosing ng Q I for all local steps q = 0,-., Q 1, the global
model iterates in Algorithm achieves the following ergodic convergence rate
T-1
[+ v -((w))-((w)) + +3L2Qu2(Q)(i) Man, mar,K + 11)(o) + og + G) +
a2)
a (q o7.
T t=0
n2a1(Q)7
(12)
Proof Theorem 2- By L-smoothness assumption,
f(w S (w') V (w") A
+ L
fly A
2
T.ng
<s(w') - Th Σ
(VS (w')
4
TKTT))
|
(13)
K
2K
KES.
KES.
2
where -/- is the client delta which trained from using the global model after 7k updates as initialization. We will next derive the upper bounds on Ii and T2. To begin,
Ti
7g
(w
Σ 9=0
(4) m
The (yk.g" (-x))
KES.
M
(g)
V (w')
9b (yk.4 --x)
(14)
K
kES.
Using conditional expectation, the expectation operator can be written as
E[1 == [m (.. 1s.+l]
where Ex is the expectation over the history of the iterates, E.-[ar] is evaluated over the randomness over the distribution of clients i ~ [M] checking in at time-step f, and the inner expectation operates over the stochastic gradient of one step on a client. Hence, following unbiasedness,
1g K
Q-1
(g)
(w0) Il (uhtaa")) )
E T =
m
SE 9=0
m
Q-1
n
(9)
F [(m(m]]
VVf (wr*) It (vi
m
9=0
"a EE
(4)
(V (w").
VF (vi
mm
0=0
Vf (wt 1 Σ FFF (Vi }
Th En
m
V
(15)
From the identity,
(a, b)
(|all + ||b1|2 ||a - b11z)
22

---

Under review as a conference paper at ICLR 2023
have
Q-11
Q-1
(4)
E
[
7g
Σ
n(a))
||5 (1*)
(w'))
-Bx
1
Σ
V (uin
2
2
m
4=0
i=1
1 m
+ BE
Vi (10")
Σ
vb, (vi,4
(16)
m
Now for T3, from the definition of fww")
1 m
1
m
Ex [33]
Ex
V
(w²)
F (Van
m
m
1
Ex
VF; (w")
VE (ui
11 ||
(17)
i=1
Further, by telescoping, T3 can be decomposed as
E
[T3
1
EM
F. (w*) - VF, (w'- + VF; (w- - VF, (v ||
m
2
EH V (w") Pr (w
F&; (w'
vR. (26.g I1?)
(18)
1=1
staleness
Incal drift
2
1, 1.2 1/=
w0 Foll
+ 1.2 11-0- 1-7,
m
The upper bound on T3 can be understood as sums of bounds on the effect of staleness and local drift during client training, and local variance induced by client-side SGD. Further, we need produce an upper bound on the staleness of initial model from which the client models are trained.
|| - w T0
Σ
(wet1
wp)
Σ
m K
p P
=
TV
p
SpESp
v1² K2
Q
Σ
n gi (Vher))
11)
(19)
p=
SS 1=0
Taking the expectation terms of H.
1 QT
En I|w= w0 1|
11 2 1r,,D11''
K
E.E 1=0
mm") 2
3m
Q
max T ti
(of + 17 GG)
< QT K
n (1
(0î + +
(20)
where the last incquality follows from the assumption maximal delay and applying Lemma I (Eqn. 11). Similarly, the local drift term can be upper-bounded by
E |
Vigg
E
Vi To
)
(n)) )²
E
M
gi
Vi.1"
3g
Σ 1=0
(0) + 0g GG) (21)
23

---

Under review as a conference paper at ICLR 2023
Thus, the upper bound on T3 becomes:
p-1 Σ
(n (o) (0++0++)) + L2q
9-1
) (o) + G)
E [33 < 6
Q markk
Σ
(1
1=0
1
6
(1)
2
TTQxza +
< <6L2Q
(1)
Tgg
( maz,k + +1) (oî +o
(22)
Inserting the upper bound on T3 into Eqn.( 16), we have,
Q-1
Q-1
1
(9)
[[T]] S
72 2
Σ )
[1')
E
[7a]
n1 11
Ex
1
Σ
VF; (vhrT²) 11?
2
m
q=u
1=1
(23)
Let aQQ) = E9=0 Th!
and az(()= = (n= )2 Then
(m)
[Ti < - (1)
[(""))) )12 + 3ng 1,² 1.2Qan (Q)az (Q) (17 maax K + +1) (oî + oo + +G)
2
Q Q-1
1
(q)
Eh
(24)
2
0=0
T4
To derive the upperbound on the R.H.S. of Equ.( 13), we now need to upper bound [[T2]. We proceed by adding and subtracting the expected gradient within the norm,
27
E T2
=
E
L
g
2
M
(4)
(
2k
lEE. 9=0
Ln (2)
LQ
2 Q-1
Σ Σ
(n("))"E
[I (vi.g
(25)
2
2m
q iml
We now show that T4 + TB < 0
Q
LQ
Q-1
(T)+ =
Eμ
V F. F.
Σ
(T)
2
(0)
[[
(vi (12))
2
2m
0=
9=0
Q-1 m
ng (9)
T.Q 99)
Eh (F((,))))) Il
2m
2m
7=0
(26)
To ensure T3+T; < 0, it is sufficient to choose plugging (24), (25), and (26) into (13),
71 (4)
< + for all local steps = O,... Q - 1. Now,
Elf (wt+)) < E (w²)] - (Q) L
| (w') In, (1a T man, K + (of + +0 +G)
2
+ 2 2 0z (Q)
(27)
24

---

Under review as a conference paper at ICLR 2023
Summing up? from to T and rearrange, yields
T-1
0g (Q) V (1)
(E
[ (w')] E [ (wi
T-1
+3
Σ "1 1220 (Q) (1gTmax max + +) (oî + + G)
L
2
T-1
5 (f
- (ww")) +3 Σ
ng (g)2ar(Q)az2(4) (1g (ngTmar, + QQ) + oog + GG
t=
L,
(28)
2
Thus have
T-1
V (w')) < (1())) - 1 (w²))
T
(Q)T(Q))
L nz (Q) 2 an (Q) of
+3L2Qaz(2) (ng Tmaz, + 1) (o² + og + G)
(29)
For sufficiently large T, the algorithm achieves the convergence rate as shown in Equation 29. As we see, the convergence guarantee increases with increasing K as tend to go closer to the synchronous aggregation. Also, as non-IID bias increases, gradient variances increase, and weakens the convergence guarantee.
25


Reviews:
[{"review_id": "tJjswOdLmRI", "reviewer": "Reviewer_x4EL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "## The problem\nThe paper introduces an asynchronous  aggregation scheme to address the straggler problem and also taking in the effect of non-iid. The paper focuses on \"heavyweight\" learning task such as video action recognition that are out of reach for mobile devices processing power. Overall, the paper aims to address the problem of how to best aggregate the updates sent by all clients in order to maximize information\nlearned while minimizing any adverse effect from slow updates. \n## The solution\nScale client update based on its staleness and the client's local training loss. The aggregation scheme gives more importance to the clients with low training accuracy to push to global model to learn from clients with low accuracy. \n\n\n", "summary_of_the_review": "Overall, I believe this paper is a simple extension to FedBuff. However, I think the improvement is incremental and the problem of FL on heavyweight ML task seems like a niche problem space. \n\n## Post-rebuttal update\nThe authors answered my concerns about scalability and clarified the difference between KUIPER and FedBuff. However, I think the paper can benefit from throughout revision to make it clear what the contributions and focuses of the paper are. Secondly, the paper lacks details about the how the client execution time, staleness and how stragglers are simulated. I appreciate that the authors did clarify these point in their comments. \n\nI will stand by my initial rating of below the acceptance threshold. I think this is good contribution to the community once the weaknesses are addressed. \n\n", "strength_and_weaknesses": "## Strength\n1. The paper is easy to read and follow. The problem and motivation is clearly stated in the introduction. \n2. The aggregation scheme is simple and can be easily incorporated without making any new assumptions. \n3. The takeaways section helps capture the high level points of the paper. \n\n## Weakness\n1. Equation 2 is hard to follow. For example, what is $w_{new,t}^i$ ?\n2. The video action recognition experiments were done on a very small number of devices (less than 12). FedBuff is design for cross-device setting with very high concurrency and K to be a small fraction of concurrency. \n3. In large scale experiments (Figure 5), the difference between Kuiper vs Oort and FedBuff seems negligible. Did the author repeat the runs for multiple trials and report the average?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jOMFx6PCKG", "reviewer": "Reviewer_cvzu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "Kuiper is a federated learning system designed to produce accurate global models in the presence of non-IID client data.   In particular Kuiper addresses the straggling clients with an asynchronous, buffered aggregation technique.   Kuiper proceeds in rounds, starting a round when K client updates arrive.  It then adjusts the global model based on client data set size, update latency, and local training error.  The work provides a convergence analysis and experiments show that the system provides comparable or better prediction performance against recent work on different video action recognition benchmarks.    ", "summary_of_the_review": "Moderate contribution in asynchronous FL.   Strong evaluation / extensive results on a non-trivial problem across datasets, against competing algorithms, including exploring various tuning variables.   The writing and paper focus makes understanding details of the technical contribution difficult, as well as placing it in the context of the systems to which they compare.  \n\n[Post Author Response].  I'd like to thank the author's for explaining the questions my review raised.  The work unifyies techniques from other systems in a non-trivial manner, which is an important contribution for the community.   The authors address many of the presentation problems, and the system performance shows clear global model and training time improvements.    In view of this I'm adjusting the empirical significance and recommendation to a 6. ", "strength_and_weaknesses": "Positives\n+ Provides a delta on top of existing work in sync/async buffered approaches for dealing with stragglers. \n+ Extensive experiments on a challenging modeling task across multiple datasets against competing systems \n+ Experiments showed training/time benefits, and explored system design (scale, tuning variables)  \n\nNegatives\n- The description of the algorithm, particularly the use/measure of time, is not clear\n- While the system compares to Oort / FedBuff, the differences aren't clear and spread across the paper \n- The writing quality and organization makes understanding the contributions and system challenging. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PVJIlFWJPZ", "reviewer": "Reviewer_t9vz", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors tackle a practical problem of federated learning where asynchronous communication is frequent due to the computational heterogeneity. The authors propose a method considering taleness of local updates when performing model aggregation. They demonstrate the effectiveness of their method.\n", "summary_of_the_review": "I enjoyed reading the paper, but several improvements are required.\n", "strength_and_weaknesses": "**Strength**\n- They tackle the practical federated learning where asynchronous communication is frequent due to the computational heterogeneity.\n- The results are impressive.\n\n**Weaknesses**\n- The critical limitation of this work is the lack of significance. The proposed method for calculating staleness seems a rule-based algorithm which is hard to consider as significant. I think it could be a better way to devise a neural model learning the staleness and importance of asynchronously updated local models (neural aggregator, etc). \n- Error bars are missing and thus it is hard to discuss the marginal case i.e. Fig 4 (b) \n- Minor:\n    - Paper organization need to be polished (inbetween spaces are too tight)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject