FLuID: Mitigating Stragglers in Federated Learning using Invariant Dropout
Authors: Irene Wang
Prashant J. Nair
Divya Mahajan
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Learning
TL;DR: We develop a framework, called Federated Learning using Invariant Dropout (FluID), that at runtime determines the stragglers and tunes the training load by adapting the sub-model based both on the magnitude of neuron updates.

Abstract: Federated Learning (FL) allows machine learning models to train locally on individual mobile devices, synchronizing model updates via a shared server. This approach safeguards user privacy; however, it also generates a heterogeneous training environment due to the varying performance capabilities across devices. As a result, “straggler” devices with lower performance often dictate the overall
training time in FL. In this work, we aim to alleviate this performance bottleneck due to stragglers by dynamically balancing the training load across the system. We introduce Invariant Dropout, a method that extracts a sub-model based on the weight update threshold, thereby minimizing potential impacts on accuracy. Building on this dropout technique, we develop an adaptive training framework, Federated Learning using Invariant Dropout (FLuID). FLuID offers a lightweight sub-model extraction to regulate computational intensity, thereby reducing the load on straggler devices without affecting model quality. Our method leverages neuron updates from non-straggler devices to construct a tailored sub-model for each straggler based on client performance profiling. Furthermore, FLuID can dynamically adapt to changes in stragglers as runtime conditions shift. We evaluate FLuID using five real-world mobile clients. The evaluations show that Invariant Dropout maintains baseline model efficiency while alleviating the performance bottleneck of stragglers through a dynamic, runtime approach.

FLuID: Mitigating Stragglers in Federated Learning using Invariant Dropout
Irene Wang Prashant Nair Divya Mahajan
University of British Columbia', Microsoft", Georgia Institute of Technology
irene. wangogateggggccc....mmmm edu prashantnair@ece wtt.ce...bb.ee. ubc. edu waw.a.mmaaaaangaaaeea. edu
Abstract
Federated Learning (FL. allows machine learning models train locally on in- dividual mobile devices, synchronizing model updates via shared server. This approach safeguards user privacy; however, it generates a heterogeneous training environment due to the varying performance capabilities of devices. As result, "straggler" devices with lower performance often dictate the overall training time. In this work, we aim to alleviate this performance bottleneck due to stragglers by dynamically load balancing the training across the system. We introduce Invariant Dropout, method that extracts sub-model based the weight update thresh- old, thereby minimizing potential impacts on accuracy. Building on this dropout technique, develop adaptive training framework, Federated Learning using Invariant Dropout (FLulD). FLuID offers a lightweight framework for sub-model extraction regulate the computational intensity, thereby reducing the load on straggler devices without affecting model quality. Our method leverages neuron updates from non-straggler devices construct tailored sub-model for each straggler based on client performance profiling. Unlike prior work, FLuID can dynamically adapt to changes stragglers runtime conditions shift. We evaluate FLuID using five real-world mobile clients. The evaluations show that Invariant Dropout maintains baseline model efficiency while alleviating the performance bottleneck of stragglers through dynamic and lightweight runtime approach.
Introduction
Federated Learning (FL) enables machine learning models to train edge and mobile devices, synchronizing the model updates via a common server [SB09, SVHN10, LSTS20, ZBW+22]. This method ensures breaches, leaks, or unauthorized access to sensitive information the cloud [MMR+ 17]. However, FL introduces heterogeneity due varying performance capabilities of the participating devices. Consequently, straggler devices with lower computational and network performance often dictate the overall training latency and throughput, shown in Figure
privacy local data remains the device, minimizing the risk of data
Previous research mitigates the impact stragglers through asynchronous aggregation, where clients can communicate and update the server model independently and asynchronously (CCA+21. CNSR20, XKG19]. While this approach alleviates some of the detrimental effects of stragglers, introduce staleness into the global model. This occurs because the gradients used to update the server model may rely on outdated parameters, resulting in inaccuracies that have the potential to slow down convergence and reduce overall accuracy [BHS20, CCA+ +21, WUH HBGS19).
Other research proposes eliminating updates from slower devices entirely. [KMA+ + 19]. However, this approach can introduce training bias, as it effectively excludes certain clients and their respective data.
Source code available betpa://gitthn Lttt/
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Initial Model
Model Aggregation
Training
Traniny
Trining
Mlc:
Tritting
Idle
Traning
Toining
Idc
Figure I: Straggler's impact on FL performance. synchronous FL, clients, including stragglers, participate in global model aggregation.
To ensure the contribution of all devices, recent works in this area employ dropout technique where the stragglers only train a subset the global model [HLA 21, MGZP22). The overall accuracy of the model is determined by the subset of neurons that are dropped from the global model. Thus, previous work alleviates the training load on stragglers by either incurring training bias, creating sub-models, entirely reconstructing the sub-model.
performance-camee
Our paper proposes a novel dropout technique called Invariant Dropout, which identifies "invariant" neurons-thow that train quickly and show little variation during training. We observe that the training (computational load) and transfer (communication load) of these invariant neurons and from the straggler devices contribute minimally the efficiency of the global model. Thus, they can be dropped. We observe that after only 30% of the training iterations, 15%-30% of the neurons become invariant across CIFARIO 10 [Kri09], and LEAF datasets FEMNIST, and Shakespeare [CDW't 18]. Building on this insight, we develop a dynamic framework called Federated Learning using Invariant Dropout (FLulD), which adjusts the sub-model size based both the magnitude of neuron updates and the computational capabilities of the client devices. In addition to introducing a new dropout technique, FLuID, unlike prior work, periodically calibrates the sub-model size during runtime to account for changes in stragglers due to factors like low battery or network issues.
Overall, we face two challenges in building FLuiD) identifying invariant neurons and establishing dynamic lightweight method for straggler identification and sub-model size determination runtime. FLuID addresses the first challenge by leveraging the non-straggler clients, which typically outnumber stragglers and train on the entire model, to identify invariant neurons. The server is not used for this purpose it receives updates from stragglers running a sub-model. For the second challenge, FLuID uses drop-threshon threshold, below which neurons are dropped, allowing dynamic sub-model determination for each straggler. By profiling client training times and identifying stragglers during the initial epochs each calibration step, FLuID can incrementally adjust the drop- thre-shre until the number of selected neurons matches the target sub-model size for stragglers.
Our evaluation of FLulD on various models, datasets, and real-world mobile devices shows an up to 18% speedup in performance. Additionally, it improves training accuracy by maximum of 1.4 percentage points over the sate-of-the-an Ordered Dropout, all while mitigating the computational performance overheads caused by straggler devices.
Related Work
In the domain of heterogeneous client optimization, several prior work have tried to mitigate the effects of stragglers.
Dropout techniques. Federated Dropout [CKMTI8, RKPH22] randomly drops portions of the global model, sending a sub-model to the slower devices. However, this can potentially impact accuracy. Subsequent work, Ordered Dropout [HLA 1ILA+21, 21, DDT21], mitigates this accuracy loss by regulating which neurons are dropped, either from the left or right portions of the global model. Other methods, such as those outlined in [MGZP22], use a low-rank approximation to identify over-parameterized neurons and generate tailored sub-models. Despite these advancements, none of these works consider the individual contribution of each neuron while creating a sub-model. In contrast, our work not only introduces novel dropout technique that takes into account the contribution of cach neuron but also

---

provides a framework capable of dynamically identifying slower devices and adjusting the dropout
rate accordingly.
Server offloading strategies using split learning. The approach proposed by [WUH 21] employs split learning to offload part of the model to the server, while [HAA20] transfers their knowledge to a larger server-side CNN. [UWH+21] focuses on device mobility during Federated Learning, offloading training to edge servers. Finally, [WQR 22] introduces a compression method for split learning. However, unlike these methods, Invariant Dropout does not require data transfer out of the device and into the server, instead conducts all training on client devices. Nonetheless, if data movement was a possibility, Invariant Dropout can be stacked on top of these techniques to determine which part of the model needs to be offloaded to the server.
Communication Optimizations. To reduce learning time, [HWL200 proposes an online learning approach that reduces the communication overheads of Federated Learning by adaptively sparsifying gradients. [CSP+21] introduces Federated Learning framework utilizing a probabilistic device selection method to improve FL convergence time. (XFD*21 proposes a framework incorporating overhead reduction techniques for efficient training resource-limited edge devices, including pruning and quantization. Unlike these works, Invariant Dropout avoids both communication and computation overhead by dropping the least contributing "invariant" neurons, presenting new insight compared to these prior works.
Model Pruning. PruncFL [JWK+22 22] introduces an approach to dynamically select model sizes during FL and reduce communication and computation overhead, thereby minimizing training time. Work in [MSA 21] prunes the global model for slower clients by excluding neurons with no or small activations. These approaches either generate a single sub-model for all clients, including non-stragglers, to train on or generate a static sub-model for the entire training process which can result in the stragglers permanently losing the opportunity contribute certain parts of the model. In contrast, Invariant Dropout enables the generation of multiple sub-models with various resource budgets and dynamically chooses a sub-model for each round based on current neuron contribution.
Coded Federated Learning. CodedPaddedFL. and CodedSecAgg [SKRA21] utilize coding strategies to mitigate the impact of slower devices. By sharing an encoded version of their data with other clients, both schemes introduce redundancy in the client's local data. Therefore, during training, the computation of a subset of clients is sufficient to train the global model and the computations of straggling clients can be discarded without loss of information. While CodedPaddedFL. combines one-time padding with gradient codes, codedSecAge is based on Shamir's s secret sharing. Unlike these methods, Invariant Dropout allows each client to keep their data local.
Training Global Family of Models. SuperFed [KALT23] proposes co-training of multiple models to reduce training costs. It achieves this by sending subnetworks of different sizes to all clients. In contrast, FLuID focuses on optimizing the performance of stragglers by mostly training clients on the full global model and smaller percentage (stragglers) on sub-models tailored to their capabilities.
3 Background and Motivation
3.1 Challenges in Federated Learning
In Federated learning's synchronous aggregation protocols, the server hosts a global model and regularly aggregates updates from clients, which then redistributed to clients [CCA+21]. Thus, system heterogeneity remains a significant challenge in FL. (DTS+22, HLA+21, LSTS20]. As shown in Figure 2a, we observe significant differences in training times across five Android-based mobile phones, from 2018 to 2020, engaged in Federated Learning without any dropout mechanism in place. Depending on the dataset and machine learning model, training time can vary significantly, with differences of up to twofold across datasets such as CIFAR10, FEMNIST, and Shakespeare. The standard deviation between the training times of each client is 0.5, 22, and 21 seconds for FEMNIST, CIFAR10, and Shakespeare, respectively. This highlights the real-world challenge of system heterogeneity, where different devices, even if they are similar class (e.g., Android-based mobile phones) with just few years' difference, can offer dramatically different computational performance. Furthermore, we find the performance of mobile devices can fluctuate over time due to varying network bandwidth and resource availability, In response to these observations, develop
3

---

Nr Epodi To lng Thia Sicands
OHARED
TEHNOT
Tedtlgg Ordened
59.0
51.5
Orderol
107
45.0
38.5
(P4)
02.5
58.0
59.5
1101
57.5
41.
57.0
79.5
0.8
UG
Google
Samsunn
Samoung
Google
Galaxy
Galaxy
(a) The per-epoch training time client devices in log scale.
(b) Compared accuracy of Ordered Dropout with hase-
line implementation Federated Learning.
Figure 2: (a) Performance variation across mobile devices (in log scale), (b) accuracy implications of prior dropout (static) techniques.
FLuID, system designed to dynamically identify stragglers and adjust the training load to balance performance with non-straggler devices.
3.2 Dropout Techniques
Model dropout is a technique that involves sending a subset the global model, known as a sub- model, to stragglers for load balancing. There are two sate--of-the-ar proposals in this space: Federated Dropout [CKMT18] and Ordered Dropout from FjORD [HLA *21]. Federated Dropout randomly drops neurons, simplifying the selection of sub-models, but reducing the global model's accuracy. In contrast, Ordered Dropout systematically drops neurons by maintaining order within the sub-model. These works demonstrate that the sub-model's neuron selection is crucial for the global model's accuracy. In the context of this work, "neurons" refer to filters in convolutional (CONV) layers, activations in fully-connected (FC) layers, and hidden units in Long Short-Term Memory (LSTM) [HS97] layers.
Accuracy Implications with dropout: Figure 2b compares the testing accuracy of a non-dropout vanilla Federated Learning (FL) implementation with Ordered Dropout. This comparison per- formed using five mobile devices, one of which is a straggler, across three different datasets: CI- FARIO [Kri09], FEMNIST, and Shakespeare (CDW+18) As the sub-model size decreases, observe that across all three datasets and machine learning models, Ordered Dropout experiences up 2.5 percentage point drop in accuracy. We vary the sub-model size from 0.5 (representing 50% of the global model) to (the entire model). The results with 50-100 100 clients and 20% of them being stragglers are provided in Section 6.1.
Invariant Dropout
Invariant Dropout enables stragglers to only train on sub-model consisting of neurons that 'vary' over time and contribute to the global model. Invariant dropout achieves this by selecting a subset (i) of sub-models (s;) from total sub-model distribution (S), where each sub-model represents different number neurons and thus varies in compute and memory requirements. Appendix A.1 illustrates the temporal variation in the percentage of invariant neurons in the evaluated models. Note that all clients including the straggler still perform inference on the full model.
4.1 Proposed dropout mechanism
Invariant Dropout selects sub-model from a set of sub-models, S, composed of m total sub- models denoted as S' $1, $2, Sm- Each sub-model 8; contains neuron layers 01, a2 .... ag. The size of the sub-model corresponds to dropout rate that is based on the drop-threshold th for the dropout mechanism. Given a change in neuron value, g = Aa, we can select the sub-model 8; (01, a2,..., (4.) where the updates in neurons within the sub-model satisfy 2 th V aj E 8; and 1 < j S FLuID, which we describe below, selects 8; such that the compute utilization and memory footprint effectively mitigate the inefficiency of the straggler.

---

Next, we assuine that the system includes C' clients with T stragglers and N non-stragglers. T and N are exclusive and independent subsets of C. where T UUN and T n N Φ. Invariant Dropout maintains a dropout rate r E (0, 1] per layer across the T stragglers. However, the complexity of selecting az + 1) will vary with each sub-model 8;- To reduce the computational overhead of selecting the appropriate sub-model, ID leverages non-straggler clients to provide directions on the set of (t + 1). The server computes over a subset of potential sub-models s; to select the one with the maximum updates to the neurons.
4.2 Variance in Gradients with Invariant Dropout
Consider C' clients participating in Federated Learning. The training data is represented F. 1 where denotes client, and each client has corresponding loss function fo-=1 Learning minimizes the loss function using the following optimization: f(w) == E 1 fe(w). where Wt+1 Wt T) (g(x)))
Invariant Dropout can be viewed as sparse stochastic gradient vector, where each gradient has certain probability of being dropped. The gradient vector is denoted as G [91, 92: ..., 9k] where g R and each gradient has probability of being retained and transmitted across the network, represented as [PL,P2: .... Pk. The sparse vector for the stragglers is represented as G.. The variance of the ID-based gradient vector can be represented as E(G;) = E (i)Pt) [WWLZ18, XYXC21]. The variance of the dropout vector is small factor deviation from the non-dropout gradient vector represented as follows:
min
> (oPP.) = (1++)
(1)
Invariant Dropout drops weights based on the = Aa gradient across epochs. Thus, the probability of gradient not getting dropped (p;) is inversely proportional to the dropout rate r. This implies [g,] > 19,1 then p; Pj- Let's assume that the top-k magnitude of gradients are not dropped. Hence if G = [ 92, .... 9m is sorted, then G [g1 92, .... gh] has p = 1, whereas G [ Ik-2: ..., gal
has probability of 1g:l This modifies the optimization problem in Equation I to:
Σ oe
+
(1+ E)
Σ ge =0 9
1
(2)
T
k=+
Which implies that
Σ m.
ビ 1
(3)
(1 + c) Σ #= 0 -E g
As per the constraint [dc
1:
m2
m
19:1(
Σ 1=++1
(gil S (1+e)
(4)
Invariant Dropout retains the gradients with the greatest magnitude. As a result, the boundedness of the expected value from Equation can be represented as follows:
m
M
Σ
P:
=
Pt
Σ
P
(5)
im
Li=k+1 [gs|
k + |9:|
(6)
(1 (1+))
1=1 03
>/ =i 9
s=k+1
As such, the variance of the gradient in ID is bounded by Equation 7.
5

---

Cluball Modid
Ag
Global Model
Sin-Singgler
Climms
Global Model
Nen Stazzler Clierie
Stop
YIS
Start
ldmmnfy Singggkee
Deteminc (dep mar)
Iniiulizz (dogy ahresbold
Trannik done?
Aggezaate Updazes
Check dg from not- oragglens for inveram seunnns
Sob-Model
Streeler Cliait
Rafamuss
Stragoler
Eatrrsse anpa
Broedcast global muddel to stragalers
Broaccost sup uodel to Strgalen
Re Calibrate
marglors....l and sab anddaa
Sewrdy
Class Chaa
Figure 3: The workflow of FLuID. The non-stragglers used to determine the neurons that updated within a set threshold. Thereafter, sub-models are dynamically created by dropping invariant neurons. These sub-models are sent the straggler devices.
FLuID Framework
Figure shows the workflow of Federated Learning using Invariant Dropout (FLuID). In FLuID, each calibration step includes straggler determination (T), discovering invariant neurons(/ /N) and drop threshold (th), and sub-model extraction(s;). Currently, the calibration occurs per epoch, i.c. one training run over the complete client dataset. However, the frequency of calibration can be reduced if the invariant neurons and stragglers do not significantly change over steps.
Algorithm outlines the FLuID framework. At the onset of training, FLuID identifies the stragglers. To achieve this, FLuID runs the global model all clients, including stragglers, and measures the performance delay between the end-to-end training time of the slowest client (T (Tstraggter) and the target time (T (aaagger.EEd-ooooo
training includes upload/download latency and communication time.
Tearget is the desired training time FLuID aims to achieve for stragglers. FLuID assigns Tearget the next slowest client's 's training time. This choice optimizes non-straggler idle time reduction. Note, FLuID can support any Targeet value. Setting Tiorget lower than the next-slowest client's 's time offers no gain as non-stragglers cannot accelerate. Conversely, setting Tiarget above the next-slowest client's training time leads to longer idleness and suboptimal performance. The required speedup for stragglers is calculated as Speedup Terraggerr
Trorget The initial calibration is carried out in lines 6-9 and 18-22 of the algorithm. Note, it takes few epochs to calibrate the initial threshold, stragglers, and submodel. In subsequent calibration steps, the global server continues to measure the training time of clients and thereby identifies if there is any change in the straggler cohort.
Tuning the performance of stragglers. The sub-mode size determined by calculating the dropout rate r as detailed in lines 18-21 of Algorithm 1. The value of r is selected to ensure that the updated straggler training time, denoted as Tetragglernews is close to the target training time (Ttarget). Figure in Appendix A.3 demonstrates that across all evaluated datasets, the training time of all five mobile clients decreases linearly as the sub-model size decreases, and falls within 10% of the sub-model size. Using this insight, FLuID chooses an r that is closest to the inverse of the speedup.
Determining the drop threshold at runtime. Once FLuID has identified the stragglers and the dropout rate, it iteratively adjusts the threshold drop as many invariant neurons as possible. The design of FLuiD) is inspired by the preliminary results regarding the characteristics of invariant neurons and their impact on the model accuracy. Appendix A.2, we present results to quantify the impact of the threshold value on the number of invariant neurons during training. We observe that, in critical to select a threshold that yields a number of invariant
order to obtain the desired accuracy, neurons as close as possible to the number of neurons to be dropped for the sub-model.
Lets assume (t)e(t) represents the set of weights of the ith neuron in the jth layer for client e after the training epoch t. The percent difference g of the neuron, for each client is the minimum value of g as denoted by: g 2 (tse(t)-w,,(t--) those whose weight updates are within the threshold (th) compared to the previous calibration point. Unfortunately, determining the appropriate th poses a few challenges.
Neurons that potential candidates for dropping
(ty(t-1)

---

Algorithm FLuID executing on Centralized Server
1: Input: M(w)
# Model. M ( jismodelatstept
2: Output: S(w)
Sub models for stragglers
3: N + All Clients, + # stogglers, non-strugglers
IN +
Invariant newrons
5: while not done do
6: I' is 9 then {a Sinaggler and dropout threshold intialization }
7: Broadcast M (wo) to each C
8: Receive (ww) from every C
th min ("iget "1)(t"))(()))) #threshold for Invariant dropout
Wis(t-1)
10:
else {# Struggler and dropout threshold recalibration)
11:
S(ws) sub. model generation(IIV. M. (w:))
12:
Broadcast ((wes) all E T
13:
Broadcast (wr) all
T
14:
Receive ((w++1) from every
15:
M (w aggregate( (wy). ((w+1))
16:
IN = identify invariant neurons(hh,h)
17:
end if
18:
T. L determine_sttne (iremmnne_straggeess(()))
train latencles
19:
Tiarget identify_next powet_sloowss_cceent....
20:
Speedup, = Latrapglerg
Tearget
21:
ri S; = calculate =t=acuulat__uuummddL_e Jubmodel_size(Speecle 8 drspoia rate
22:
th = increment (tareenntt_rrshho(((r))
23:
done check_ httee_ttiiinnnoooneMiiiit
24:
end while
In order to identify neuron drop candidates, the global server cannot rely updates from all clients since stragglers only train on and update the sub-model. Instead, the server takes advantage of the fact that non-stragglers train the complete model and can identify neurons whose weight updates fall within the threshold (th) for each calibration step. FLuID prioritizes dropping neurons on stragglers whose weight updates fall within the threshold (th) for the majority of non-stragglers.
The initial threshold value (th) the FLuID framework is set as the average of the minimum percent update of all neurons in the initial few training epochs. The threshold is incrementally increased after each epoch until the number of neurons below the threshold greater than or equal the number of neurons to be left out of the sub-model. FLuID have different drop threshold for each layer. The algorithm targets neurons for dropping whose gradients consistently fall below the threshold over multiple epochs, prioritizing the elimination of non-critical neurons.
This entire process is repeated to recalibrate the stragglers, the drop rate (r), and the threshold (th).
6 Evaluation Setup
Models and datasets. We evaluate FLuID on three models and datasets as used by the prior works in the federated learning space [MGZP22, JWK* 22, HLA+ CKMT18).
The FEMNIST datasets consist of images of numbers and letters, partitioned based on the writer of the character in non-IlD setting. We train CNN with 5x5 CONV layers with 16 and 64 channels respectively, each of them followed with 2x2 max-pooling. The model also includes a fully connected dense layer with 120 units and a softmax output layer. The model is trained using a batch size of 10 and a learning rate of 0.004.
The Shakespeare dataset partitions data based on roles in Shakespeares' plays in non-lID setting. We train a two-layer LSTM classifier containing 128 hidden units. We train the model with a batch size of 128 and learning rate of 0.001.
The CIFARIO 10 dataset consists of images, partitioned using the same strategy as FjORD [HLA+2] 21] and the IID partition provided by the Flower [BTM+20], For the real-world mobile devices, we train on the VGG-9 model due to its ability to fit within the resource constraints of all the mobile phones tested. VGG-9 [SZ15] model architecture consists 6 3x3 CONV layers (the first 2 have 32 channels,
7

---

Table 1: Software-Hardweee specifications of clients
Device
Year
Android Version
CPU (Cores)
LG Velvet SG
2020
10
1x24 Gliz Kryo 475 Prime + 1x2.2 GHz Kryo 475 Gold + 1.8.8 GHzz Kryo 475 Silver Kryo
Google Pixel
2018
Kryo
Samsung Galaxy $9
2018
10
4x2.8 GHz Kryo 385 Gold + 4x 1.7 GHz Kryo 385 Silver
Samsung Galaxy $10
2019
II
2x22.73 GHz Mongoose M4 2x2.31 GHz Cortex-A75 4x 1.95 GHz Cortex-A55
Google
2019
1x Kryo
Kryo 1.78 Kryo
Table Accuracy comparison Random Dropout, Ordered Dropout, and Invariant Dropout. The text in bold indicates instances when Invariant Dropout showcases the highest accuracy. (u mean, a standard deviation, and r sub-model as fraction of global model).
Dataset
Dripout Method
7-
0.95
0.85
0.75
0.65
0.5
Accuracy (9)
o
Accuracy (0)
Accuracy (p)
Accuracy (e)
Accuracy (1))
Shakespeure
Random
43.3
0.1
42.5
0.1
42.4
0.1
41.8
0.2
41.3
0.1
Ordered
42,9
0.1
42.3
0.1
42.2
0.2
41.9
0.1
41.4
0.1
Invariant
43.6
42.5
0.1
42.6
42.2
0.2
41.7
0.1
CIFARIO
Random
57.5
0.1
56.8
0.2 57.0
0.2
57.2
0.2
51.2
0.3
(VGG-9)
Ordered
57.7
0.2 57.6
0.1
Invuriant
58.2
0.1
58.4
0.3 57.1
0.1 $7.5
0.2
$1.4
0.2
FEMNIST
Random
80.6
80.5
0.2 80.3
0.2
79.3
79.2
0.3
Ordered
80.6
80.5
0.2
80.4
0,2
80.3
0.1
79.7
0.3
Invariant
81.1
80.9
0.1 80.8
0.2 80.3
0.4
80.1
0.3
followed by two 64-channel layers, and lastly two 128-channel layers), two FC dense layers with 512 and 256 units and final softmax output layer. We train the model with a batch size of 20 and learning rate of 0.01. We conduct scalability experiments using the ResNet- 18 model, and the results presented in section 6.1. All the baseline dropout methods and Invariant Dropout evaluated using the same setup.
System Configuration. Table provides the details of the phones used for the experiments. We evaluate five clients and identify one straggler per training epoch. We connect all our client devices and our server over the same network. All the clients run on Android mobile phones from the years 2018 to 2020.
FLuID is implemented on top of the Flower (v0.18.0) [BTM+20) 20] framework and TensorFlow Lite [Goo] from TensorFlow v2.8.0 [ABC- 16]. Models are defined using TensorFlow's Sequential API, and then converted into tfliite formats.
Evaluation metrics and baselines. We compare the average training performance (wall-clock time) and accuracy for all workloads and experiments. In each evaluation round, clients receive the global model and report their evaluation accuracy and loss local data to the server. The server calculates the distributed accuracy and loss by performing weighted average based on the number of testing examples for each client. We compare FLuID with two established baselines: 1) Random Federated Dropout [CKMT18] and 2) Ordered Dropout from FjORD +11].
6.1 Results and Analysis
Accuracy Evaluation We compare accuracy of Invariant Dropout with two baselines, using different sub-model sizes. We trained the models for 100, 250, and 65 epochs for CIFARIO, FEMNIST, and Shakespeare datasets, respectively. Table 2 presents the average achieved accuracy (μ) along with the standard deviation (a)) for the three datasets. Specifically, Invariant Dropout outperforms Random Dropout across all three datasets. Compared to Random Dropout, our work achieves maximum accuracy gain of 1.6% points and on average 0.7% point higher accuracy for FEMNIST, 0.6% point higher accuracy for CIFAR10, 10, and 0.3% point higher accuracy for Shakespeare datasets.
Invariant Dropout also achieves higher accuracy against Ordered Dropout across all three datasets, with maximum increase in accuracy of 1.4% and average increase of 0.3% for FEMNIST, 0.4%

---

2500
Troining Time seconds
Original Roduced
120
Reduced
3.50
3.75
Origina Roduced
Traiinn Time seconds
Uaseline
Dyttamic
22020
Dynamic
Baselina
2000
Dynanic
Static
Baseline
20000
15000
130
3.25
1500
120
3.00
20000
10030
1000
2.75
5000
500
100
70
2.50
EHAKESPEARE
CIFAR10
FEMUUST
SMAKES SMAKESPPARRE
60
CIFAR0
2.25
53%
100%
50%
100%
4
Training Iterstion
(a) Training time for stragglers before and after FLuID.
(b) Training time reduction with varying stragglers.
Figure 4: Performance evaluation of FLulD
for CIFAR1O, and 0.4% for Shakespeare. The accuracy improvements of Invariant Dropout are statistically significant (a < 0.05). Moreover, Invariant Dropout shows less variation in accuracy between runs of the same sub-model size and across all sub-model sizes. This is because invariant Dropout eliminates only invariant neurons, which have little impact on the final model efficiency.
Computational Performance Evaluation Figure 4a shows FLuID's capability to effectively select the sub-model, resulting in a significant reduction in the straggler's training time that almost matches the next slowest client. In the absence of FLuID, the straggler's 's training time is typically 10% to 32% longer than the target time. However, after applying FLuID, the straggler's 's training time is within 10% of the target time. Furthermore, it is observed that the overall accuracy of the global model tends to be higher when stragglers train with larger sub-models Consequently, FLuID selects the largest possible sub-model size that minimizes training time variance across clients. Notably, the performance improvement, unlike accuracy, is influenced by the size of the sub-model and not the specific dropout technique employed. For a more detailed analysis of the impact of sub-model size on training time, please refer Appendix A.3.
Varying stragglers at runtime. FLuID recalibrate stragglers. During the experiments in Table 2, we observe that the performance of our mobile clients remained relatively stable, without significant changes in the straggler. However, to evaluate the impact of varying conditions at runtime, randomly executed certain clients at different points in the training process (25%, 50%, and 75% marks). This was achieved by enabling client run the training program background process between the specified periods. We observed that FLuID successfully adapted to the variation in stragglers during runtime. Figure 4b demonstrates the overall training time for this experiment. On average, the FLuID framework achieved 18% to 26% faster training time compared to the baseline, and 14% to 18% faster training time compared to selecting static straggler throughout the entire training process. All results include the overhead of FLuID, which, importantly, is not significant. We observe, FLulD calibration process takes significantly less time (less than 5%) compared to the actual training time. This is because the additional computations required for threshold and sub-model calibration are performed centrally on the server, rather than being distributed to edge devices.
Scalability study. To assess the scalability of FLuID, we conducted experiments using simulated clients ranging from 50 to 100. Each machine runs 10 to 20 clients in parallel. Among all clients, we identified the slowest 20% as stragglers. We further extend the experiment to run CIFAR10 with 18 as these are emulated clients on server and can support relatively larger models than mobile devices. Figure shows the accuracy performance across all three datasets. Overall, Invariant Dropout consistently outperforms Ordered and Random Dropout and maintains better accuracy profile similar to Table 2. In addition, our dropout technique performs significantly better than completely excluding stragglers from the training process.
We further extended the experiment to assess the scalability of FLuID by 1) clustering stragglers into multiple sub-model sizes (Appendix A.4), 2) Exploring the impact of varying ratios of stragglers in the system (Appendix A.5), and 3) scalability study with 1000 clients where client sampling employed as we cannot check for stragglers across 1000 devices individually (Appendix A.6). We demonstrate that FLuID can scale to scenarios involving multiple stragglers with varying computational capabilities by tailoring sub-model sizes for each client. Moreover, when compared to state-of-the-an dropout techniques, Invariant Dropout achieves high accuracies, even as the percentage of stragglers in the system scales up.

---

Foolug
Fodleg Tuddig [8D Clamta)
Tephug Clerta)
Irvaiom
Ineanintt
Ordened
Ortered
Bandom
Recuracy
RanSom
0.2
03
0.4
0.5
0.6
0.7
0.8
0.5
Sab-mode
Subemodel size
(a) Shakespeare LSTM (50 Clients, 10 stragglers)
(b) CIFARIO VGG9 (100 Clients, 20 stragglers)
FodAug
Teshkg 180 Cllents]
80.5
Invariant
78
$0.0
77
78
FodAeg
79.0
75
Tedfwg IuD Clants)
Invamann:
78.3
24-
Oedered
Random
18.0
0.2
0.3
0.4
0.5
0.6
0.7
0.8
09
877
0.8
09
Sub-modal
SUb model
(c) CIFARIO ResNet18 (100 Clients, 20 stragglers)
FEMNIST CNN (100 Clients, 20 stragglers)
Figure 5: The accuracy comparison Invariant Dropout with Ordered and Random Dropout as we scale to 50-100 clients with 20% of the slowest clients being stragglers.
7 Limitations and Future Work
Although FL.lD is able to mitigate some impact of the stragglers, it does incur minimal overhead to handle stragglers and maintain system performance. Our evaluation takes this into account but this overhead may increase if straggler performance constantly changes.
FLuID currently only uses pre-defined sub-model sizes mapped to straggler performance, which keeps the framework lightweight and avoids high overhead. However, for future works with varied edge devices, fine-gra ann-ggrined sub-model determination may further enhance the work.
8 Conclusions
Due to rapid technological advancements and device variability in handheld devices, system het- erogeneity is prevalent in federated learning. Straggler devices, which exhibit low computational performance, act as the bottleneck. In this paper, we address these issues by introducing novel dropout technique called Invariant Dropout. Invariant Dropout dynamically creates customized sub-models that include only the neurons exhibiting significant changes above a certain threshold. We build a framework, FLuID, which adapts to changes in stragglers as runtime conditions shift. FLuID effectively mitigates the performance overheads caused by stragglers while also achieving higher accuracy compared oatte-of-the-art techniques.
Acknowledgements
We thank the anonymous reviewers for their insightful comments. This research was supported in part through computational resources provided by Advanced Research Computing at the University of British Columbia (UBC) [soc]. This work was partially supported by Gift from Google and the Natural Sciences and Engineering Research Council of Canada (NSERC) [funding reference number CGPIN-2019-050591 The work, in part, was supported by Georgia Tech School of Electrical and Computer Engineering and School of Computer Science. The views and conclusions contained herein are those of the authors. They should not interpreted as necessarily representing the official policies endorsements, either expressed or implied, of Georgia Tech, Microsoft, and UBC.
10

---

References
[ABC*16] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving. Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large-scale machine learning. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI'16, page 265-283, USA, 2016. USENIX Association.
[BHS20] Saar Barkai, Ido Hakimi, and Assaf Schuster. Gap-aware mitigation of gradient staleness. In International Conference on Learning Representations, 2020.
[BTM+20] Daniel J. Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Javier Fernandez-Marquese Yan Gao, Lorenzo Sani, Kwing Hei Li, Titouan Parcollet, Pedro Porto Buarque de Gus- mão, and Nicholas D. Lane. Flower: A friendly federated learning research framework, 2020.
[CCA+21] Zheng Chai, Yujing Chen, Ali Anwar, Liang Zhao, Yue Cheng, and Huzefa Rangwala. Fedat: A high-performance and communication-effiieenn federated learning system with asynchronous tiers. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC '21, New York, NY, USA, 2021. Association for Computing Machinery.
18) Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečny, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: benchmark for federated settings, 2018.
[CKMT18] Sebastian Caldas, Jakub Konečny, H. Brendan McMahan, and Ameet Talwalkar. Ex- panding the reach of federated learning by reducing client resource requirements, 2018.
[CNSR20] 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), pages 15-24, 2020.
[CSP+21] Mingzhe Chen, Nir Shlezinger, H. Vincent Poor, Yonina C. Eldar, and Shuguang Cui. Communication--eficiien federated learning. Proceedings of the National Academy of Sciences, 118(17):e202448811 18, 2021.
[DDT21] Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. In 9th International Confer- ence on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[2TS+22] Jie Ding, Eric Tramel, Anit Kumar Sahu, Shuang Wu, Salman Avestimehr, and Tao Zhang. Federated learning challenges and opportunities: An outlook, 2022.
[Goo] Google. Tensorflow lite ml for mobile and edge devices. https://wwr tensorflow. org/lite. Accessed: 2022-08-14.
[НAA20] Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cnns at the edge. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4408--1400. Curran Associates, Inc., 2020.
[HBGS19] Ido Hakimi, Saar Barkai, Moshe Gabel, and Assaf Schuster. Taming momentum in distributed asynchronous environment, 2019.
[HLA+21] Samuel Horváth, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis, Stylianos Ve- nieris, and Nicholas Donald Lane. FjORD; Fair and accurate federated learning under heterogeneous targets with ordered dropout. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan, editors, Advances Neural Information Processing Systems, 2021.
11

---

[HS97] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computa- tion. 9(8):1735-1780 1997.
[HW220] Pengchao Han, Shiqiang Wang, and Kin Kwong Leung. Adaptive gradient sparsifi- cation for efficient federated learning: An online learning approach. 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), pages 300-310, 2020.
[2 Yuang Jiang, Shiqiang Wang, Bongjun Ko, Wei-Han Lee, and Leandros Tassiulas. Model pruning enables efficient federated learning on edge devices. IEEE transactions on neural networks and learning systems, PP. 2022.
[KALT23] Alind Khare, Animesh Agrawal, Myungjin Lee, and Alexey Tumanov. Superfed: Weight shared federated learning, 2023.
[KMA+19] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. CoRR, abs/1912.04977, 2019.
[Kri09] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[LSTS20] Tian Li, Anit Kumar Sahu, Ameet S. Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37:50- 60, 2020.
[MGZP22] Yiqun Mei, Pengfei Guo, Mo Zhou, and Vishal Patel. Resource-adaptive federated learn- ing with all-in-one neural composition. In Advances in Neural Information Processing Systems, 2022.
17] H. B. McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-effiienn learning of deep networks from decentralized data. In AISTATS, 2017
[MSA+21] Muhammad Tahir Munir, Muhammad Mustansar Saeed, Mahad Ali, Zafar Ayyub Qazi, and Ihsan Ayyub Qazi. Fedprune: Towards inclusive federated learning, 2021.
[RKPH22] Martin Rapp, Ramin Khalili, Kilian Pfeiffer. and Jörg Henkel. Distreal: Distributed resource-aware learning in heterogeneous systems. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 36, pages 8062-8071, 2022.
[SB09] Venkatesh Shankar and Sridhar Balasubramanian. Mobile marketing: A synthesis and prognosis. Journal of interactive marketing. 23(2):118-2))) 129, 2009.
[SKRA21] Reent Schlegel, Siddhartha Kumar, Eirik Rosnes, and Alexandre Graell i Amat. Cod- edpaddedfl and codedsecagg: Straggler mitigation and secure aggregation in federated learning, 2021.
[soc] UBC Advanced Research Computing, "UBC ARC Sockeye." UBC Advanced Research Computing, 2023, doi: 10.1KEES/OCCE
[SVHN10] Venkatesh Shankar, Alladi Venkatesh, Charles Hofacker, and Prasad Naik. Mobile marketing in the retailing environment: current insights and future research avenues. Journal of interactive marketing, 11- 2010.
12

---

[SZ15] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large- scale image recognition. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015.
[UWH+21] Rehmat Ullah, Di Wu, Paul Harvey, Peter Kilpatrick, Ivor Spence, and Blesson Varghese. Fedfly: Towards migration in edge-based distributed federated learning, 2021.
[WQR*22] Jianyu Wang, Hang Qi, Ankit Singh Rawat, Sashank Reddi, Sagar Waghmare, Felix X. Yu, and Gauri Joshi. Fedlite: A scalable approach for federated learning on resource- constrained clients, 2022.
[WUH+21] Di Wu, Rehmat Ullah, Paul Harvey, Peter Kilpatrick, Ivor Spence, and Blesson Varghese. Fedadapt: Adaptive offloading for iot devices in federated learning, 2021.
[WWL2188] Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication-fficient distributed optimization. In NeurlPS, 2018.
[XF Wenyuan Xu, Weiwei Fang, Yi Ding, Mcixia Zou, and Naixue N. Xiong. Accelerating federated learning for iot in big data analytics with pruning, quantization and selective updating. IEEE Access, 9:38457-38466, 2021.
[XKG19) Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization, 2019.
[XYXC21] Zirui Xu, Fuxun Yu, Jinjun Xiong, and Xiang Chen. Helios: Heterogeneity- aware federated learning with dynamically balanced collaboration. In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 997-1002, 2021.
[2BW+22] Zhengyi Zhong, Weidong Bao, Ji Wang, Xiaomin Zhu, and Xiongtao Zhang. Flee: A hierarchical federated learning framework for distributed deep neural network over cloud, edge and end device. ACM Trans. Intell. Syst. Technol., jan 2022, Just Accepted.
13

---

A Appendix
A.1 Evolution of Invariant Neurons
35%
30%
25%
20%
15%
10%
Shakespeaee
5%
CITARIO
0%
FEMNIST
0%
20%
40%
00%
80%
100%
Percent of Training Epochs
Figure 6: The percentage of 'invariant' neurons as the number training rounds vary
In this section, we provide an example that some neurons in the server are trained quickly and vary only below threshold in later iterations. Figure shows the percentages of invariant neurons as the number of training epochs increases. Even after only 30% of the training rounds are completed, 15%-30% of the neurons become invariant across CIFARIO, FEMNIST, and Shakespeare datasets For this example, we choose thresholds of 180%, 10%, and 500%, respectively, for these three datasets and compute their invariant neurons. Sending invariant neurons over straggler provides no utility; therefore, these neurons can be dropped. Our work FLull) builds upon this insight.
A.2 Choosing Suitable Threshold
Each model has different characteristics in terms of the magnitude of neuron updates. Therefore, choosing different threshold values results in a different number of neurons classified as invariant. We expanded on initial findings and studied the effect of threshold value on the number of invariant neurons during training. As expected, a higher threshold value leads to a higher percentage of invariant neurons. Table presents the percentage invariant neurons observed different threshold values, and the overall training accuracy of the FEMNIST model, using sub-model size of 0.75 for the stragglers.
Table 3:
Threshold vs accuracy results
Threshold value (%) Percentage of Invariant Neurons (%)
Accuracy (%)
80.1
6
80.3
13
80.5
18
80.7
22
80.7
80.5
We observe that obtain the desired accuracy and mitigate performance bottlenecks of stragglers, it critical to choose the threshold that has the closest number of invariant neurons as the number of neurons be dropped for the sub-model. The FLulD framework can automatically the threshold for the desired model based on the straggler performance, as described in Section 5.
A.3 Impact Sub-Model Size on Training Time
In this section, we present evidence that there is a linear relationship between client training time and sub-model size. We evaluated the training time of Android-based mobile phones from 2018 to 2020 outlined in Table 1. The training time is expressed in the percentage of the training time for the
14

---

Semourg
Sorsung Gallery 30
Training Time
Samoung Galeoy 333
Sarsung Galley 3XC
57%
17h
97%
Gongle
GoagleRou
73%
70%
Sar aurg Bakay 33
60%
Samsing falary
3076
SHAKESPEARE
CIFAR10
89%
FEMNIST
Goegie Reel
Reil
2.
08
10
05
07
09
05
34
07
06
09
3.0
Sub-model Size
Figure 7: Linear relationship between training time and model size across all three datasets
full model size (r = 1.O). Across CIFARIO, FEMNIST, and Shakespeare, the training time of all five mobile clients decreases linearly as the sub-model size decreases and falls within 10% of the sub-model size. Using this insight, FLuID selects a sub-model size as available sub-model, the size that's closest to the inverse of Speedup.
A.4 Additional Experiments with Scalability Studies.
In this section, we show that in the case that the network has multiple stragglers, FLulD does not assume that all stragglers have similar capabilities or select sub-model for all stragglers based on the slowest device. FLuID can select sub-model sizes for each straggler client based on each client's own capabilities. In this experiment, we cluster devices of similar capabilities into four groups of sub-model sizes. Table presents the accuracy when stragglers are assigned to equal-sized clusters (sub-model size 0.65, 0.75. 0.85, 0.95). The overall accuracy generally lies between assigning sub-model sizes of 0.75 and 0.85 for all stragglers. This way, FLuID can achieve higher training accuracy with shorter training time, even with stragglers that are initially more than 35% slower than non-straggler devices.
Table 4: Accuracy comparison of Random Dropout, Ordered Dropout, and Invariant Dropout as we cluster stragglers into different sub-model size groups.
Random
Ordered
Invariant
CIFARIO
71.7
72.3
72.7
FEMNIST
77.5
77.4
78.2
Shakespeare 53.8
53.9
54.1
A.5 Additional Experiments with Varying Straggler Percentages
In this section, we show that FLuID is capable of handling multiple ratios of stragglers. We have run additional experiments to explore the impact of different ratios stragglers, One common trend we observed across state-of-the -he techniques and FLuID is that accuracy decreases as the ratio of stragglers is increased as more of the devices are now being trained only on the sub-model. Nonetheless, in all the cases, Invariant Dropout offers the highest accuracy because it is aware of the neuron gradient changes and only drops the least changing neurons. The accuracy results of varying the straggler ratios while using 0.75-sized sub-models summarized in Figure 8.
Diver
72.
Inettet
Oraknd
750
110
11.0
22.5
773
515
655
753
Perrestag JEstorgee
Pei-stag Stoweer
(a) Shakespeare LSTM (50 Clients) (b) CIFARIO VGG9 (100 Clients) (c) FEMNIST CNN (100 Clients)
Figure& 8: Accuracy of varying the straggler ratios from 10% to 40% with 0.75 sub-model size
15

---

A.6 Scalability of FLuID with Client Sampling
As the federated learning system scales, FL servers sample subset clients participating in each training round. At any point in training, FLuID is capable of recalibrating stragglers and supports dynamic changes during runtime. The ability to adjust to a different set of clients and identify stragglers in every training round enables FLuID to easily incorporate client sampling into its process. We scaled FLulD to 1,000 clients with the FEMNIST dataset for 500 global training rounds. We run with client sampling ratio of 10%, as used by the prior works in federated learning spaces such as FjORD [HLA 221]. We present the accuracy results in Table against each sub-model size for Invariant Dropout and the baseline techniques. Invariant Dropout maintains better accuracy profile than the baselines even when scaled up to 1000 clients while incorporating client sampling.
Table 5: Accuracy comparison of Random Dropout, Ordered Dropout, and Invariant Dropout as for FEMNIST with 1000 clients and client sampling of 10%.
r=0.95
r=0.55
1=0.75
r=0.65
r=0.40
Random
87.9
87.5
87.5
86.9
85.7
Ordered
87.8
88.0
87.5
87.3
87.0
Invariant
88.1
88.2
88.0
87.7
87.2
16


Reviews:
[{"review_id": "vWxuKy0nrV", "reviewer": "Reviewer_sKfw", "summary": "The paper presents a framework, FLuID, for cross-device federated learning, where some of the clients are “stragglers”. The training time of these stragglers is significantly higher, hence they dictate the overall training time.\n\nFLuID uses Invariant Dropout to dynamically reduce the stragglers’ training time, hence alleviating their overall FL training time degradation.\n", "questions": "(1) Lines 196-198: “T_target is set equal to the training time of the ‘next slowest client’ … Thus speedup ensures optimal utilization of available clients”, can you explain this argument? How does such a setting of T_target ensure optimal utilization of the clients, regardless of the stragglers’ training time distribution?\n\n(2) Line 200: how does the server measure the training time of clients? The server is aware of the end-to-end latency of given clients that generally depends on the client’s (1) downlink bandwidth and latency, (2) training time, and (3) uplink bandwidth and latency. \n\n(3) Line 11 in Algorithm 1 is unclear: what’s “inv”?\n\n(4) The discussion about setting th in lines 209-219 is unclear, is it a heuristic? Does it have any theoretical properties/guarantees? \n", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The authors tackle a very important problem in cross-device federated learning. Clients are usually edge and mobile devices that are running several processes and applications at the same time. Therefore, the training time varies as compared to dedicated servers used in cross-silo FL setups.\n\nTherefore, proposing a dynamic approach to identify the stragglers and the appropriate dropout rate is of major importance in this domain.\n", "weaknesses": "While this paper targets a very important and relevant problem in the FL domain, I have concerns regarding the proposed framework, as detailed below:\n\n* How FLuID measures the training time of the stragglers, and how can it distinguish between stragglers due to high training time, and high upload/download latency? FLuID targets the former, while the latter requires a different solution than proposed in this paper.\n\n* Some of the design decisions/details lack further explanations. For instance, the setting of T_target and th (see more about it in the Questions section).\n\n* The number of invariants is bounded (at any given training round for any given model), while “Speedup” (as defined in the paper in line 197) is generally unbounded (depending on the stragglers’ training times). Therefore, FLuID might result in an aggressive dropout rate, and thus diminishing return.\n\n* The evaluation is insufficient: \n\n    (1) It includes small and relatively “easy” datasets to learn, as well as small ML models. \n\n    (2) The obtained accuracy improvement is quite negligible.\n\n    (3) Some of the evaluation setup information is missing. Mostly the distribution of the stragglers' training time, see also question (1) in the Questions section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We answer the questions in order.\n\n**Weakness 1: Training time of stragglers**\n\nFluID considers the end-to-end latency, upload/download latency, communication time, and training time of the device to determine if it is a straggler.\n\nHowever, similar to prior works in the area, such as Federated Dropout (Caldas et al., 2018) and FjORD(Horvath et al., 2021), the FLuID infrastructure is built to reduce the compute and communication load by only training on sub-models. FLuID focuses on identifying stragglers based on hardware processing capabilities. This approach effectively decreases the computation load on the device, focusing on training a sub-model and reducing the communication load by synchronizing fewer parameters.\n\nWe empirically observe that download/upload latencies are similar and **do not pose significant bottlenecks** for any device or dataset. For both CIFAR10 and Shakespeare datasets, the download/upload time accounts for less than 3% of the end-to-end training latency. Similarly, in the case of FEMNIST, even with relatively short actual model training times, the download/upload time remains within 15% of the end-to-end latency.\n\nFLuID assigns T_target as the \"next slowest client's training time.\" This choice optimizes non-straggler idle time reduction. FLuID is flexible to accommodate various t_target values. However, setting T_target lower than the \"next-slowest client's\" training time offers no gain as non-stragglers cannot accelerate. Conversely, setting t_target above training time leads to longer idleness and suboptimal performance.\n\n**Weakness 3: Unbounded Speedup**\n\nFLuID enforces a minimum model size to ensure accuracy is not significantly impacted. Consequently, in scenarios where the straggler's performance is exceptionally slow, FLuID might not **completely** eliminate the performance bottleneck caused by the straggler. Nevertheless, even in cases with high skewness in performance, FLuID will still alleviate some performance bottlenecks and reduce idle time for non-stragglers. Throughout our evaluations, we maintain a lower bound for the model size at 20%.\n\n**Weakness 4-(1) Evaluation datasets**\n\nWe evaluated FLuID on established models, datasets, and settings as used by the prior works in federated learning space such as  Federated Dropout (Caldas et al., 2018), FjORD(Horvath et al., 2021), Adaptive Gradient Sparsification for Efficient Federated Learning (Han et al., 2020), PruneFL (Jiang et al.,2022), and FLANC(Mei et al., 2022). \n\n**Weakness 4-(2) Impact of FLuID**\n\nThe primary goal of FLuID is to address the performance bottlenecks caused by stragglers in a federated learning scenario without compromising the model's accuracy. Compared to the state-of-the-art federated dropout techniques, FLuID offers up to 18% speedup in training time. FLuID introduces a novel dropout technique that considers neuron updates and performs dropout on invariant neurons to achieve this. This approach, moreover, results in accuracy improvements of up to 1.4%.\n\n**Weakness 4-(3) Distribution of the stragglers' training time**\n\nWe apologize for the confusion on the evaluation setup. Figure 2a shows the per epoch training time distribution across the mobile devices in the log scale. The standard deviation between the training times of each client is 0.5, 22, and 21 seconds for FEMNIST, CIFAR10, and Shakespeare, respectively.  We will add these details to the paper.\n\n**Question 1: Setting of T_target**\n\nWe will include the following explanation in the paper. \nFLuID aims to determine the optimal training time for straggler devices to mitigate non-straggler idle time in federated learning efficiently. To achieve this, we set a maximum training window while minimizing model dropout that effectively manages straggler impact without sacrificing accuracy. Notably, FLuID can enhance accuracy by up to 1.4% points compared to leading federated dropout techniques.\n\n**Question 2: Training time measurements**\n\nThe **reported training time** is each client's **actual wall clock training time**. The server's end-to-end training latency is also measured by taking the time difference between when it sends the global model and receiving training results from each client. Thus, this training time includes the upload/download latency, training time, and communication time. We will clarify these details in the paper. \n\n\n**Question 3: Line 11 in Algorithm 1 “inv”**\n\nThe inv is a typo. Inv instead is the variable IN in line 4 and line 16 of the algorithm. We will fix this in the final version of the paper. \n\n**Question 4:  Threshold selection**\n\nThe threshold selection is guided by a heuristic approach rooted in preliminary results and backed by evaluation data. We will clarify this in the paper. \n\nThe design of FLuID is inspired by the preliminary results regarding the characteristics of invariant neurons and their impact on the model accuracy. We have presented such preliminary results in Appendix A.1, Figure 6. These results show the number of invariant neurons across the training process. After only 30% of the training rounds are completed, 15%-30% of the neurons exhibit invariance across CIFAR10, FEMNIST, and Shakespeare datasets.\n\nA neuron is invariant if its update is below the threshold value. Different models exhibit distinct characteristics concerning the magnitude of neuron updates. Therefore, choosing different threshold values will lead to different numbers of neurons being categorized as invariant. In Appendix A.2, we showcase the threshold sweep and observe its impact on invariant neurons observed in the training process. Intuitively, the percentage of invariant neurons increases as the threshold value increases. Table 3 shows the percent of neurons observed with increasing threshold value as invariant and the overall training accuracy of the model trained for FEMNIST, with a sub-model size of 0.75 for the stragglers.\n"}, {"review_id": "mnh3AdWBOe", "reviewer": "Reviewer_yFRv", "summary": "FLuID authors tackle a straggler problem in Federated Learning, where a central model is trained across a set of heterogeneous devices.\nThis problem is particularly challenging when performance capabilities at training time are actually variable. This variable heterogeneity at training time requires a mechanism that can change the model sent to a client per round, in order to create a control mechanism that mitigates the clients’ straggler effect. FLuID achieves this with a proposed Invariant Dropout method. \nThe Invariant Dropout technique quite simply refers to identifying neurons the updates for which have become minimal (close to invariant) over some number of rounds. This observation is used to decide to exclude such neurons (or “drop” them) from training for a given client. Neurons can be ranked based on the extent to which they are “invariant”, and a line can be drawn as a function of computation budget to determine how many neurons to drop.\n\nFLuID builds on several technical challenges: \n1. identifying invariant neurons\n2. identifying stragglers\n3. determining a subset of the model weights to send to each client/straggler\n\nFLuID is able to match or exceed accuracy across several datasets. Performance includes real-world mobile client evaluation. Straggler effects are mitigated using Invariant Dropout. ", "questions": "Questions:\n* It would be interesting to get your perspective on comparison between FLuID and SuperFed [1]. SuperFed proposes sending clients subgraphs of the central model, which is isomorphic to structured dropout. SuperFed does NOT track neuron invariance, of course, but the idea of using structured dropout to send a smaller model to the client is there. In its conclusion, SuperFed mentions “adjusting .. for client resource constraints (e.g., compute, bandwidth, memory capacity)”. \n\n[1] SuperFed, https://arxiv.org/abs/2301.10879, 26 Jan 2023", "limitations": "yes, credit to authors for pointing out limitations: minimal overhead to handle stragglers and degradation of system perf in the worst case when the dynamics of client capacity variability causes instability.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ FLUid tackles a quintessential problem of stragglers in FL, which very practical and pervasive\n+ FLUid avoids using asynchronous aggregation techniques, which jeopardize model convergence. It sticks with synchronous aggregation\n+ the dropout technique is well known in DNN training and has been shown to improve performance, when random dropout is used\n+ The dynamic nature of invariant dropout is effective and can adapt to dynamically changing client compute (or communication) capacity. Support for this dynamic heterogeneity is rare in literature\n+ the paper is well written\n+ the experimental methodology is well executed", "weaknesses": "* the idea is very simple, some could consider the adaptation of dropout from previous literature to FL setting incremental? I’m certainly familiar with this idea and surprised this hasn’t been published yet.\n* this paper compares to different types of dropout as baselines, but doesn’t consider other published baselines, such as SuperFed [1]: \n    * https://arxiv.org/abs/2301.10879\n\n[1] SuperFed, https://arxiv.org/abs/2301.10879, 26 Jan 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We provide the comparison against SuperFed below:\n\nBoth SuperFed and FLUID propose sending a subset of a global model to edge clients, and both frameworks can send submodels of varying sizes to each client. However, these two frameworks differ significantly in two main aspects: their objectives and the approach used to form and distribute the subnets to clients.\n\nFirstly, the objective of SuperFed is to co-train a global \"family of models\" in a federated fashion, which ultimately reduces the cost of training multiple global models. On the other hand, FLuID aims to mitigate the performance bottleneck caused by stragglers in federated learning while training for a single global model. As a result, these differences in objectives lead to distinct design approaches. **In SuperFed, all clients receive subnetworks of different sizes, while in FLuID, most clients train on the full global network, and only a smaller percentage of clients (stragglers) train with sub-models.**\n\nSecondly, the formation and distribution of sub-models also exhibit significant differences between the two frameworks. SuperFed focuses on optimizing the spatial and temporal distribution of subnetworks, ensuring that each subnetwork receives equal exposure to all data partitions. Additionally, it keeps track of the number of times each client has been assigned to the smallest and largest subnetworks. During each round, SuperFed utilizes this information to assign the smallest, largest, and random subnetworks to the clients. **In contrast, Fluid takes a different approach, as pointed out by the reviewer, by tracking neuron invariance to generate submodels of sizes specifically optimized for the computational capabilities of the straggler device.**\n\nWe find SuperFed to be highly interesting, focusing on co-training model families in a cost-efficient federated fashion. The insights obtained from FLuID could prove valuable for the future advancement of SuperFed. By considering system heterogeneity and individual device capabilities in the load balancing and subnetwork distribution techniques, these frameworks can achieve improved performance and significant savings in training costs. \n"}, {"review_id": "Cj1FxgkzPU", "reviewer": "Reviewer_a2Bu", "summary": "The paper focuses on the issue of mitigating stragglers in a heterogenous FL environment through dynamic load balancing, introducing a technique called Invariant Dropout and an adaptive training framework called FLuID. Invariant Dropout dynamically creates customized sub models that include only the neurons exhibiting significant changes over a certain threshold. Through experimental evaluation, the papers shows that this approach mitigates performance overheads caused by stragglers while also achieving higher accuracy compared to the state-of-the-art technique - Ordered Dropout.", "questions": "N/A", "limitations": "In addition to the weaknesses mentioned above, the authors note two limitations\n- Overhead to handle stragglers and maintain system performance which may increase with changes in straggler performance\n- Currently the system only uses pre-defined sub model sizes mapped to straggler performance which keeps the framework lightweight, but for varied edge devices, fine grained sub model determination will be required.\n\nThe impact of this fine grained approach on the overhead needs to be measured to check for its suitability on different edge devices. If the overhead increases, the performance improvements noted here may diminish.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Up to 18% speedup in performance\n- Up to 1.4 pp improvement in accuracy over state-of-the-art Ordered Dropout\n- Evaluation is detailed - on 3 models and datasets and compared with two techniques: Random and Ordered\n- Improves on previous work which have drawback of incurring training bias, creating performance centric sub models, or entirely reconstructing the sub model\n", "weaknesses": "- Accuracy gains compared to Ordered and Random across datasets and models, while statistically significant may not justify the additional complexity of this system.\n- There is scope to improve the presentation\n   - In the lines 40-47 2 sentences are repeated\n   - Figure 2b has no label on the x axis\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We answer the most pressing questions first, followed by the remaining questions.\n\n**Weakness 1: Accuracy Gains of FLuID**\n\nWe have implemented FLuID as a lightweight system with minimal overheads. We empirically observe that the FLuID calibration process takes significantly less time (less than 5%) than the actual training time. Our evaluation takes these overheads into account while reporting the performance benefits. As we observe more heterogeneity in the system of devices, frameworks like FLuID will play a crucial role in mitigating performance bottlenecks.\n\n**Limitations**\n\nFLuID can scale to support more submodel sizes without significantly increasing overhead. As discussed in section 5, line 205, the sub-model size selection process is straightforward.  FLuID simply chooses a sub-model size closest to the inverse of the required speedup. Therefore, even with the addition of more sub-model sizes, the processing overhead complexity does not experience a significant increase. Notably, on real mobile phones, we have observed that the FLuID calibration process takes less than 5% of the training time.\n\n**Weakness 2: Improving the presentation**\n\nWe will clean the text to remove the repetition and ensure all figures have labels. "}, {"review_id": "aFHZqSIgdi", "reviewer": "Reviewer_DQm5", "summary": "The paper proposes (Federated Learning using Invariant Dropout) FLuiD to address the straggler problem in FL. Due to the presence of system heterogeneity, straggling nodes (nodes with resource constraints) become a bottleneck in the FL training process. In this paper, the authors propose a FLuID to address this problem. First, the identification of invariant neurons, neurons that quickly optimize and remain relatively stable for the remainder of the training. Second, the straggling devices participating in the training. This information will be used to “prune” the global model and send a subset model to the straggling devices in order to efficiently utilize the available computation and communication resources.\n\n", "questions": "- How the proposed approach is scalable with increasing the number of clients (clients can easily be scaled up to 1000 - 3000 clients in FEMNIST for instance.)?\n- Does the invariant dropout scheme will maintain its performance if client sampling is incorporated into the training? Clarification on this and further experiments would be helpful.\n- The authors should enhance the plot labels in Fig. 5", "limitations": "- Scalability is a major limitation that is not discussed and experimented well.\n- Sampling during the training process needs to be addressed clearly.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ The straggler experiments included setups conducted using mobile devices.\n+ The experiments show the proposed invariant dropout speeding up execution time relative to ordered dropout and random dropout.\n", "weaknesses": "- It appears most of the experiments involved only 5 devices. While it is commendable that the experiments involved hardware, it is not clear to claim that the accuracy margins would hold as the number of clients increases, as is expected in practical FL environments. The scaled up experiments involving 50 to 100 clients can easily be scaled up to 1000 - 3000 clients in FEMNIST for instance. This might require an FL simulation environment, but it would give a good sense of how the proposed scheme yields improved training time and accuracy.\n\n- FL usually requires client sampling in each round. This is necessary as the system scales, and not all clients can participate in each round. I didn’t see the client sample ratio discussed. Thus I assume, in your experiments, all clients are participating in each training round. If that’s the case, how will client sampling in each round affect the dropout scheme? It is not clear if the invariant dropout scheme will maintain its performance margin if client sampling is incorporated into the training process.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments, which have enabled us to add scalability analysis and sampling to the paper. \n\n**Question 1: Scalability**\n\nWe scale FLuID to **1000 clients** with the FEMNIST dataset for 500 global training rounds. We run with a **client sampling ratio of 10%**, as used by the prior works in federated learning space such as FjORD. We run these experiments on a private cloud cluster of Intel Xeon Silver CPUs and NVIDIA Tesla V100 GPUs. We emulate 20 clients on each machine using the Flower framework, as detailed in the scalability studies in Section 6.1. \nWe remain consistent with our other evaluations in Section 6.1, identifying the slowest 20% of clients as stragglers. At each global round, we randomly sample 10% of the available clients for the training round. FLuID maintains a record of the stragglers' cohort among all available clients. FLuID monitors the training times of the clients within the sampled group after every global training round. It updates the straggler record if any changes or new stragglers are identified.\n\nBelow, we present the accuracy results against each sub-model size for Invariant Dropout and the baseline techniques. Invariant dropout maintains a better accuracy profile than the baselines even when scaled up to 1000 clients while incorporating client sampling. We will add these experimental results in the final paper to showcase the efficacy of FLuID as it scales to a large number of devices for the evaluated datasets. \n\nDropout Method | r=0.95| r=0.85| r=0.75| r=0.65| r=0.40|\n---------------|-------|--------|-------|------|-------|\nRandom|87.9|87.5|87.5|86.9|85.7\nOrdered|87.8|88.0|87.5|87.3|87.0\nInvariant|88.1|88.2|88.0|87.7|87.2\n\n**Question 2: Client sampling**\n\nAt any point in training, FLuID is capable of recalibrating stragglers and supports dynamic changes during runtime. This allows FLuID to easily incorporate sampling in its process, as showcased by the new results presented here. If certain clients become unavailable or device properties change at any moment, FLuID can take that into account, as discussed in Section 6.1 and Figure 4b. \n\nHowever, all clients participated in each training round for the experiments included in the paper.\nWe scale FLuID to execute on 1000 clients in a system that emulates each client on the server described in Section 6 of the paper. We perform the experiments with the FEMNIST dataset with a client sampling ratio of 10%, as used by the prior works in federated learning space such as FjORD. We will add these experimental results **as presented above** in the final paper to showcase the efficacy of FLuID to incorporate client sampling as the number of devices grows. \n\n**Question 3: Enhancing Fig. 5**\n\nWe will enhance all the plot labels to ensure it is legible. \n"}]

Author rebuttal:

Meta-review: The reviewers generally agreed that the paper addresses an important problem and proposes a simple yet effective solution.
Decision: Accept (poster)