FjORD: Fair and Accurate Federated Learning under heterogeneous targets with Ordered Dropout
Authors: Samuel Horváth
Stefanos Laskaridis
Mario Almeida
Ilias Leontiadis
Stylianos Venieris
Nicholas Donald Lane
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Federated Learning
Heterogeneity
Efficient DNNs
Distributed Systems

Abstract: Federated Learning (FL) has been gaining significant traction across different ML tasks, ranging from vision to keyboard predictions. In large-scale deployments, client heterogeneity is a fact and constitutes a primary problem for fairness, training performance and accuracy. Although significant efforts have been made into tackling statistical data heterogeneity, the diversity in the processing capabilities and network bandwidth of clients, termed system heterogeneity, has remained largely unexplored. Current solutions either disregard a large portion of available devices or set a uniform limit on the model's capacity, restricted by the least capable participants.

In this work, we introduce Ordered Dropout, a mechanism that achieves an ordered, nested representation of knowledge in Neural Networks and enables the extraction of lower footprint submodels without the need for retraining. We further show that for linear maps our Ordered Dropout is equivalent to SVD.  We employ this technique, along with a self-distillation methodology, in the realm of FL in a framework called FjORD. FjORD alleviates the problem of client system heterogeneity by tailoring the model width to the client's capabilities. 
Extensive evaluation on both CNNs and RNNs across diverse modalities shows that FjORD consistently leads to significant performance gains over state-of-the-art baselines while maintaining its nested structure.

FjORD: Fair and Accurate Federated Learning under heterogeneous targets with Ordered Dropout
Samuel Horváth KAUST
Stefanos Laskaridis' Samsung Al Center Cambridge, UK mail@stefanos.co cc
Mario Almeida" Samsung AI Center Cambridge, UK mario. a.iamsunsnsnngg. com
Thuwal, KSA samuel www.hhhwkwass...ooooooooo edu.
Ilias Leontiadis
Stylianos Venieris Samsung AI Center Cambridge, UK
Nicholas D. Lane Samsung AI Center & University of Cambridge Cambridge, UK nic. www.eeeaammuug.... com
Samsung AI Center
Cambridge, UK
Leontiadis@sammung com
S. wwnierisssammunng com
Abstract
Federated Learning (FL) has been gaining significant traction across different ML tasks, ranging from vision to keyboard predictions. In large-scale deployments, client heterogeneity is a fact and constitutes a primary problem for fairness, training performance and accuracy. Although significant efforts have been made into tackling statistical data heterogeneity, the diversity in the processing capabilities and network bandwidth of clients, termed as system heterogeneity, has remained largely unexplored. Current solutions either disregard large portion of available devices or set uniform limit on the model's capacity, restricted by the least capable participants. In this work, we introduce Ordered Dropout, mechanism that achieves an ordered, nested representation of knowledge in deep neural networks (DNNs) and enables the extraction of lower footprint submodels without the need of retraining. We further show that for linear maps our Ordered Dropout is equivalent SVD. We employ this technique, along with a self-distillation methodology, the realm of FL in framework called FjORD. FjORD alleviates the problem of client system heterogeneity by tailoring the model width Extensive evaluation on both CNNs and RNNs across diverse modalities shows that FjORD consistently leads to significant performance gains over state-of-the-art baselines, while maintaining its nested structure.
client's capabilities.
Introduction
Over the past few years, advances in deep learning have revolutionised the way we interact with every- day devices. Much of this success relies on the availability large-scale training infrastructures and the collection of vast amounts of training data. However, users and providers are becoming increas- ingly aware the privacy implications of this ever-increasing data collection, leading the creation of various privacy-preservnn initiatives by service providers (3] and government regulators [0]]
Federated Learning (FL) [66] is relatively new subfield of machine learning (ML) that allows the training of models without the data leaving the users' devices; instead, FL allows users to collaboratively train a model by moving the computation
them. At each round, participating devices download the latest model and compute an updated model using their local data. These locally trained models are then sent from the participating devices back a central server where updates are
Indicates equal contribution. Work while intern at Samsung Al Center.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Master
p=02
p:0.6
Random Dropout (RD)
Ordered Dropout (OD)
Clients
p 0.2
0.2
0.5
- 0.75
Figure 2: Ordered vs. Random Dropout. In this example, the left-most features are used by more devices during training, creating a natural ordering to the importance of these features.
Figure 1:
FjORD employs OD tailor the amount of computation to the capa- bilities of each participating device.
aggregated for next round's global model. Until now, a lot of research effort has been invested with the sole goal of maximising the accuracy of the global model [46 mechanisms have been proposed to ensure privacy and robustness
42
39
31
63 while complementary
6
14
48
key challenge of deploying FL in the wild is the vast heterogeneity of devices [3]. ranging from low-end IoT to flagship mobile devices. Despite this fact, the widely accepted norm in FI. is that the local models have to share the same architecture as the global model. Under this assumption, developers typically opt to either drop low-tier devices from training, hence introducing training bias due to unseen data [30], or limit the global model's size to accommodate the slowest clients, leading to degraded accuracy due to the restricted model capacity S In addition to these limitations, variability in sample sizes, computation load and data transmission speeds further contribute to a very unbalanced training environment. Finally, the resulting model might not be as efficient as models specifically tailored to the capabilities of each device tier to meet the minimum processing- performance requirements [34].
In this work, we introduce FjORD (Fig. Db a novel adaptive training framework that enables hetero- geneous devices to participate in FL by dynamically adapting model size and thus computation, memory and data exchange sizes to the available client resources. To this end, we introduce Ordered Dropout (OD), mechanism for run-time ordered (importance-basely pruming, which enables us to extract and train submodels in a nested manner. As such, OD enables all devices to participate in the FL process independently of their capabilities by training a submodel of the original DNN, while still contributing knowledge to the global model. Alongside OD, we propose a self-distillation method from the maximal supported submodel on device to enhance the feature extraction of smaller submodels. Finally, our framework has the additional benefit of producing models that can be dynamically scaled during inference, based on the hardware and load constraints of the device.
Our evaluation shows that FjORD enables significant accuracy benefits over the baselines across diverse datasets and networks, while allowing for the extraction of submodels of varying FLOPs and sizes without the need for retraining.
2 Motivation
Despite the progress on the accuracy front, the unique deployment challenges of FL still set limit to the attainable performance. FL is typically deployed on either siloed setups, such as among hospitals, or on mobile devices in the wild 7 this work, we focus on the latter setting. Hence, while cloud-based distributed training uses powerful high-end clients [19] in FL these are commonly and heterogeneous embedded devices.
substituted by resource-constraing
In this respect, FL deployment is currently hindered by the vast heterogeneity of client hardware [66] 28 77. On the one hand, different mobile hardware leads significantly varying processing speed M. in turn leading to longer waits upon aggregation of updates (i.e. stragglers). At the same time, devices of mid and low tiers might not even be able to support larger models, e.g. the model does not fit in memory or processing is slow, and, thus, are either excluded or dropped upon timeouts from the training process, together with their unique data. More interestingly, the resource allocation to participating devices may also reflect on demographic and socio-economic information of owners, that makes the exclusion of such clients unfair 30) in terms of participation. Analogous to the device load and heterogeneity, similar trend can be traced in the downstream (model) and upstream

---

(updates) network communication in FL, which can be an additional substantial bottleneck for the training procedure (55).
3 Ordered Dropout
In this paper, we firstly introduce the tools that act as enablers for heterogeneous federated training.
Concretely, we have devised mechanism of importance-based pruning for the easy extraction of subnetworks from the original, specially trained model, each with a different computational and memory footprint. We name this technique Ordered Dropout (OD), as it orders knowledge representation in nested submodels of the original network.
More specifically, our technique starts by sampling a value (denoted by p) from a distribution of candidate values. Each of these values corresponds to a specific submodel, which in turn gets translated to specific computational and memory footprint (see Table lb). Such sampled values and associations are depicted in Fig. 2 Contrary conventional dropout (RD), our technique drops
adjacent components of the model instead of random neurons, which translates to computational benefits in today's 's linear algebra libraries and higher accuracy as shown later.
3.1 Ordered Dropout Mechanics
The proposed OD method is parametrised with respect to: i) the value of the dropout rate p é (0. 1] per layer, ii) the set of candidate values PP. such that E P and iii) the sampling method of over the set of candidate values, such that p Dp, where Dp the distribution over
primary hyperparameter of OD is the dropout rate p which defines how much of each layer is to be included, with the rest of the units dropped in structured and ordered manner. The value of is selected by sampling from the dropout distribution Dp which is represented by a set of discrete values P {si, $2,,... } such that 0<sı<... .. <spp S 1 and probabilities P(p s:) > O, Vi [P]]
1i=1 P(p- s;) = 1. For instance, a uniform distribution over P is denoted by p ~ Up (i.e. D = 20). In our experiments we use uniform distribution over the set P = {
such that >
which we refer to as 24 (or uniform-k). The discrete nature of the distribution stems from the innately discrete number of neurons or filters to be selected. The selection of set P is discussed in the next subsection.
The dropout rate p can be constant across all layers or configured individually per layer 1, leading to pt ~ D'p As such an approach opens the search space dramatically, we refer the reader to NAS techniques [69 and continue with the same p value across network layers for simplicity, without hurting the generality of our approach.
Given a p value, a pruned p-subnetwork can be directly obtained follows. For each layer I with widu Kr the submodel for a given p has all neurons/filters with index 1, P K2] 1} included and {[p- Ki] ..... Ki- 1} pruned. Moreover, the unnecessary connections between pruned neurons/filters are also removed
1o) We denote a pruned p-subnetwork F, with its weights wp. where F and w are the original network and weights, respectively. Importantly, contrary to existing pruning techniques [18 35 49, a p-subnetwork from OD can be directly obtained post-training without the need to fine-tune, thus eliminating the requirement to access any labelled data.
3.2 Training OD Formulation
We propose two ways to train an OD-enabled network: i) plain OD and ii) knowledge distillation OD training (OD w/ KD). In the first approach, in each step we first sample p ~ Dp; then we perform the forward and backward pass using the p-reduced network Fp; finally we update the submodel's weights using the selected optimiser. Since sampling a p-reduced network provides us significant computational savings on average, we can exploit this reduction further boost accuracy. Therefore, in the second approach we exploit the nested structure of OD, i.e. < P2 = allow for the bigger capacity supermodel to teach the sampled p-rduueed network at each iteration
Fp. C Fp and
$ 'OD through its nested pruning scheme that requires neither additional data structures for bookkeeping nor complex and costly data layout transformations, can capitalise directly over the existing and highly optimised dense matrix multiplication libraries.
*Note that p affects the number of output channels/neurons and thus the number of input channels/neurons of the next layer. Furthermore, OD is not applied on the input and last layer to maintain the same dimensionality. 'L.. neurons for fully connected layers (linear and recurrent) and filters for convolutional layers. RNN cells can seen as set of linear feedforward layers with activation and composition functions.
'For BatchNorm, we maintain a separate set of statistics for every dropout rate p. This has only marginal effect on the number of parameters and can be used in -erraccy-peeeeiigggg manner _
3

---

00 NY SM
Moystbs
Iucmmood (91
submrood (g)
suborooo
(a) ResNet18- CIFARIO
(b) CNN EMNIST
(c) RNN Shakespeare
Figure 3: Full non-federated datasets. OD-Ordered Dropout with Dp = Us SM-single independent
models, KD-knowledge distillation.
via knowledge distillation (teacher Pmax p. Pmax = max P). In particular, in each iteration, the loss function consists of two components as follows:
CS(SMp, SM panc? Vusel) (1 a ()CM((ax(SM,) Vrana) + a<L(SMMp. SMp T)
where SMp is the softmax output of the sampled p-submodel, 3/ahhl is the ground-truth label, CE is the cross-entropy function, KL is the KL. divergence, T is the distillation temperature [2] and is the relative weight of the two components. We observed in our experiments always backpropagating also the teacher network further boosts performance. Furthermore, the best performing values for distillation were a = 7 = I, thus smaller models exactly mimic the teacher output. This means that new knowledge propagates in submodels by proxy, i.e. by backpropagating on the teacher, leading to the following loss function:
(SM,, SMasa Iahel) = KI.(SMp. SMam T) + CFF(max(SM Pins Vlabel)
3.3 Ordered Dropout exactly recovers SVD
We further show that our new OD formulation can recover the Singular Value Decomposition (SVD) in the case where there exists linear mapping from features to responses. We formalise this claim in the following theorem.
Theorem 1. Let F R. R be a NN with two colle-commected linear layers with no activation or biases and K = min(m,n n hidden neurons. Moreover, let data X come from a uniform distribution on the n-dimensional unit ball and A be an m n. full rank matrix with K distinct singular values. If response is linked to data X via linear map: x. = Ax and distribution Dp is such that for every b E [K) there exists p E P for which b = [p- K7, then for the optimal solution of
min Ex~xXExDE F v
it holds F Fp(#)) = Asæ, where As is the best b-rank approximation of A and b [p. K].
Theorem shows that our OD formulation exhibits not only intuitively, but also theoretically ordered importance representation. Proof of this claim is deferred to the Appendix.
3.4 Model-Device Association
Computational and Memory Implications. The primary objective of OD is to alleviate the exces- sive computational and memory demands of the training and inference deployments. When layer is shrunk through OD, there is need to perform the forward and backward passes gradient updates on the pruned units. As a result, OD offers gains both in terms of FLOP count and model size. In particular, for every fully-connected and convolutional layer, the number of FLOPs and weight parameters is reduced by K2 Ky-K2/1 [/pppp 1 K,] ~ 1/p", where K₃ and K₂ correspond to the number of input and output neurons/channels, respectively. Accordingly, the bias terms reduced by factor of Ka/[n-Ka] ~ 1/p. The normalisation, activation and pooling layers are compressed in terms of FLOPSs and parameters similarly the biases in fully-connected and convolutional layers. This is also evident in Table [bb Finally, smaller model size also leads to reduced memory footprint for gradients and the optimiser's 's state vectors such as momentum. However, how are these submodels related to devices in the wild and how is this getting modelled?
Ordered Dropout Rates Space. Our primary objective with OD is tackle device heterogeneity. Inherently, each device has certain capabilities and can run a specific number of model operations within given time budget. Since each p value defines submodel of a given width, associate a pinxx value with the i-th device capabilities, such as memory, processing throughput or energy budget. As such, each participating client is given at most the Piax--ubmood it can handle.
indirectly
Devices in the wild, however, can have dramatically different capabilities; fact further exacerbated by the co-existence of previous-generatie devices. Modelling discretely each device becomes quickly

---

intractable at scale. Therefore, we cluster devices of similar capabilities together and subsequently associate a single Pinux value with each cluster. This clustering can be done heuristically (i.e. based on the specifications of the device) or via benchmarking of the model on the actual device and is considered system-design decision for our paper. As smartphones nowadays run multitude of simultaneous tasks 43). our framework can further support modelling of transient device load by reducing its associated Pimmx. which essentially brings the capabilities of the device to a lower tier at run time, thus bringing real-time adaptability to FjORD.
Concretely, the discrete candidate values of P depend on i) the number of clusters and corresponding device tiers, ii) the different load levels being modelled and iii the size of the network itself, as i.e. for each tier there exists Piuux beyond which the network cannot be resolved. In this paper, we treat the former two as invariants (assumed to be given by the service provider), but provide results across different number and distributions of clusters, models and datasets.
3.5 Preliminary Results
Here, we present some results to showcase the performance of OD in the centralised non-FL training setting (i.e. the server has access to all training data) across three tasks, explained in detail in $ $ Concretely, we run OD with distribution Dp = 14s (uniform distribution over the set (1/))--) and compare it with end-to-end trained submodels (SM) trained in isolation for the given width of the model. Fig. 3 shows that across the three datasets, the best attained performance of OD along every width p is very close to the performance of the bascline models. We extend this comparison against Random Dropout in the Appendix. We note at this point that the submodel baselines are trained from scratch, explicitly optimised to that given width with possibility to jump across them, while our OD model was trained using a single training loop and offers the ability to switch between accuracy-computatie points without the need to retrain.
4 FjORD
Building upon the shoulders of OD, we introduce FjORD, framework for federated training over heterogenous clients. We subsequently describe the FjORD'S workflow, further documented in Alg. [
As starting point, the global model architecture, F, is initialised with weights wo, either randomly or via a pretrained network. The dropout rates space P is selected along with distribution Dp with [P] discrete candidate values, with each p corresponding to a subnetwork of the global model with varying FLOPs and parameters. Next, the devices to participate are clustered into |Cierr| tiers and a Pmnxx value is associated with each cluster c. The resulting Prnxx represents the maximum capacity of the network that devices in this cluster can handle without violating a latency or memory constraint.
At the beginning of each communication round t, the set of participating devices S, is determined, which either consists of all available clients Ar or contains only random subset of A, based on the server's capacity. Next, the server broadcasts the current model to the set of clients S; and each client i receives un ppp.... On the client side, each client runs F. local iterations and at each local iteration k. the
device i samples (().)) from conditional distribution Dp S Pinax which accounts for its limited capability. Subsequently, each client updates the respective weights (w pr
) of the local submodel
using the FedAvg [46] update rule. In this step, other strategies [39] 63 31 can be interchangeably
employed. At the end of the local iterations, each device sends its update back to the server.
Finally, the server aggregates these communicated changes and updates the global model, to be distributed in the next global federated round to different subset of devices. Heterogeneity of devices leads to heterogeneity in the model updates and, hence, we need to account for that in the global aggregation step. To this end, we utilise the following aggregation rule
w 8g 5 WA (( (fw!
(6.1.)) ((...) \ (Waj-1 SiES;
(I)
1. w0+1 the global weights at commurication round f + 1, w u.t,t E) the weights on client at communication round after E local iterations, S = {i St Pinxx 2 } } a set of clients that have the capacity to update Wxy, and WA stands for weighted average, where weights are proportional to the amount of data on each client.
where W., \ W.y are the weights that belong to Fs, but not to F. F.,
Communication Savings. In addition to the computational savings ($3.4). OD provides additional communication savings. First, for the server-to-client transfer, every device with Piuxx < observes a reduction of approximately 1/Grim)) in the downstream transferred data due to the smaller model size (8 3.4p. Accordingly, the upstream client-to-server transfer is decreased by 3/(rin)) as only the gradient updates of the unpruned units are transmitted.
5

---

Algorithm 1: FjORD (Proposed Framework)
Input: F, w², Dp.T.
for I e to do I! Global rounds
Server selects clients a subset S, C Ar
Server broadcasts weights of -ubmoodl to each client i E St for k - to E 1 do I/ Local iterations
Vi E St: Device samples P(i.k) ~ Dr S Piax and updates the weights local model end
Vi E Sy: device i sends to the server the updated weights (t....))
Server updates w as in Eq. 1
end
Identifiability. A standard procedure in FL is to perform element wise averaging to aggregate model updates from clients. However, coordinate-
averaging of updates may have detrimental effects the accuracy of the global model, due to the permutation invariance of the hidden layers.
Recent techniques tackle this problem by matching clients' neurons before averaging [68] 57 62). Unfortunately, doing so is computationally expensive and hurts scalability. FjORD mitigates this issue since it exhibits the natural importance of neurons/channels within each hidden layer by design; essentially OD acts in licu of neuron matching algorithm without the computational overhead.
Subnetwork Knowledge Transfer. In $ 3.2 we introduced knowledge distillation for our OD formulation. We extend this approach to FjORD, where instead of the full network, we employ width max(p E P: p S Pmax } as teacher network in each local iteration on device i. We provide the alternative of FjORD with knowledge distillation mainly as a solution for cases where the client bottleneck is memory- or network-relate cases where client devices are computationally bound in terms of training latency, we propose FjORD without KD or decreasing Pinxx to account for the overhead of KD.
rather than computational nature (32]. However, in
5 Evaluation of FjORD
In this section, we provide a thorough evaluation of FjORD and its components across different tasks, datasets, models and device cluster distributions show its performance, elasticity and generality.
Datasets and Models. We evaluate FjORD on two vision and one text prediction task, shown in Table Ia] For CIFARIO (3), we use the "CIFAR" version of ResNet18 [20]. We federate the dataset specific client, and thus
by randomly dividing it into equally-sized partitions, each allocated remaining IID in nature. For FEMNIST, we use CNN with two convolutional layers followed by a softmax layer. For Shakespeare, we employ a RNN with an embedding layer (without dropout) followed by two LSTM [22] layers and a softmax layer. We report the model's performance of the last epoch on the test set which is constructed by combining the test data for each client. We report top-1 accuracy vision tasks and negative perplexity for text prediction. Further details, such as hyperparameters, description of datasets and models are available in the Appendix.
Table 1: Datasets and models
0.2
0.4
0.6
0.8
1.0
CIEARTO ResNNet8
203M
380M
Dataset
Model
A Clients A Sumples Task
Partat
456K
2M
4M
7M
11M
CIFARIO
RedNe118 Stakespeare
100 50, 000 Image classification
FEMNIST/CNE
FEMNIST CNN
3. 4040 671, 585 Image classification
MACS
47K
120K
218K
342K
491K
715 38, Next characte prediction
Pirsen
SK
15K
26K
Shikespeare
RNN
MACs
12K
40K
83K
143K
216K
(a) Datasets description
Parmms
12K
40K
82K
142K
214K
5.1 Experimental Setup
(b) MACs and parameters per p-reduced network
Infrastructure. FjORD was implemented on top of the Flower (v0. (40ev4 (5) framework and PyTorch (v1.4.0) (5T). We run all our experiments on a private cloud cluster, consisting of Nvidia V100 GPUs To scale to hundreds of clients on a single machine, we optimized Flower so that clients only allocate GPU resources when actively participating in a federated client round. We report average performance and the standard deviation across three runs for all experiments. To model client availability, we run up to 100 Flower clients in parallel and sample 10% at each global round, with the ability for clients to switch identity at the beginning of each round to overprovision for larger federated datasets. Furthermore, we model client heterogeneity by assigning each client to one of the device clusters. We provide the following setups:

---

50
80
.4.00
PJORD
FJOnD w/
-5.00
FJ3RD sFD
eFD
6FD
0.2
0.4
5.6
0.0
03
2.4
5.6
0.2
02
0.4
0.6
0.0
(a) 8 CIFARIO
(b) CNN- FEMNIST
(c) RNN Shakespeare
Figure 4: Ordered Dropout with KD vs eFD baselines. Performance vs dropout rate across different
networks and datasets, Dp 1ds
Uni This refers to the distribution Dp, i.e. ~ Ug. with k = or 10.
Drop Scale {0.5, 1.0}: This parameter affects possible skew in the number of devices per cluster. It refers to the drop in clients per cluster of devices, as we go to higher p's. Formally, for uniform-n and drop scale ds, the high-end cluster n contains 1 1- -E=0 da/n of the devices and the rest of the clusters contain dz/n each. Hence, for ds=1.0 1.0 of the uniform-5 case, all devices can the = 0.2 subnetwork, 80% can run the = 0.4 and so on, leading to a device distribution of (0.2, ...., 0.2). This percentage drop is half for the case of ds=0.5, resulting larger high-end cluster, e.g. (0.1, 0.1, ............0 0.6).
Baselines. To assess the performance against the state-of-the following baselines: i) Extended Federated Dropout (eFD), ii) FjORD with eFD (FjORD w/ eFD).
compare FjORD with the
eFD builds on top of the technique of Federated Dropout (FD) g which adopts Random Dropout (RD) at neuron/filter level for minimising the model's footprint. However, FD does not support adaptability to heterogeneous client capabilities out of the box, as it inherits a single dropout rate across devices. For this reason, we propose an extension to FD, allowing to adapt the dropout rate to the device capabilities, defined by the respective cluster membership. It is clear that eFD dominates FD in performance and provides a tougher baseline, as the latter needs to impose the same dropout rate to fit the model at hand on all devices, leading to larger dropout rates (i.e. uniform dropout of 80% for full model to support the low-end devices). We provide empirical evidence for this in the Appendix. For investigative purposes, also applied cFD on top of FjORD, as means to update larger part of the model from lower-tier devices, i.e. allow them to evaluate submodels beyond their P'mxx during training.
5.2 Performance Evaluation
In order to evaluate the performance of FjORD, we compare to the two baselines, eFD and OD+eFD. We consider the uniform-5 5 setup with drop scale of 1.0 (i.e. uniform clusters). For each baseline, we train one independent model Fp. end-to-end, for each p. For eFD, what this translates is that the clusters of devices that cannot run model p compensate by randomly dropping out neurons/filters. We point out that p = 0.2 omitted from the eFD) results as it essentially not employing any dropout whatsoever. For the case of FjORD + eFD, we control the RD by capping it to d = 0.25. This allows for larger submodels to be updated more often - as device belonging to cluster e can now have Pfnxx p during training where c+11 is the next more powerful cluster while at the same time it prevents the destructive effect of too high dropout values shown in the eFD baseline.
Fig. presents the achieved accuracy for varying values of p across the three target datasets. FjORD (denoted by FjORD w/ KD) outperforms eFD across all datasets with improvements between 1.53- 34.87 percentage points (pp) (19.22 pp avg. across p values) on CIFAR10. 1.57-6.27 pp (3.41 pp avg.) on FEMNIST and 0.01-0.82 points (p) (0.46 p avg.) on Shakespeare. Compared FjORD +eFD, FjORD achieves performance gains of 0.71-2.66 pp (1.79 avg.), up to 2.56 pp (1.35 pp avg.) on FEMNIST and 0.12-0.22 p (0.18 p avg.) on Shakespeare.
Across all tasks, we observe that FjORD is able to improve its performance with increasing p due to the nested structure of its OD method. We also conclude that eFD on top of FjORD does not seem to lead to better results. More importantly though, given the heterogeneous pool of devices, to obtain the highest performing model for eFD, multiple models have to be trained (i.e. one per device cluster). For instance, the highest performing models for eFD are F0.4. Fu.s and F0.4 for CIFARIO 10, FEMNIST and Shakespeare respectively, which can be obtained only a posteriori; after all model variants have been trained. Instead, despite the device heterogeneity, FjORD requires a single training process that leads to global model that significantly outperforms the best model of eFD (by 2.98 and 2.73 pp for CIFAR10 and FEMNIST, respectively, and 0.13 for Shakespeare), while allowing
7

---

06
FDRDD wt XD RORD
FORE W/ ID FORRO
-37
RDRD AORD
85
75
-39
hogutte per
82
01
0.2
0.2
submoddel
submodaliyg
sabmooal
(a) ResNet18- CIFAR10
(b) CNN - FEMNIST
(c) RNN Shakespeare
Figure 5: Ablation analysis of FjORD with Knowledge Distillation. Ordered Dropout with Dp Us KD Knowledge distillation.
the direct, seamless extraction of submodels due the nested structure of OD. Empirical evidence of the convergence of FjORD and the corresponding baselines is provided in the Appendix.
5.3 Ablation Study of KD in FjORD
To evaluate the contribution of our knowledge distillation method to the attainable performance of FjORD, we conduct an ablative analysis on all three datasets. We adopt the same setup of uniform-5 and drop scale 1.0 as in the previous section and compare FjORD with and without KD.
Fig. shows the efficacy of FjORD's s KD in FL settings. FjORD'S KD consistently improves the performance across all three datasets when > 0.4, with average gains of 0.18, 0.68 and 0.87 pp for submodels of size 0.6, 0.8 and 1 on CIFAR-10. 1.96, 2.39 and 2.65 pp for FEMNIST and 0.10 p for Shakespeare. For the cases of S 0.4, the impact of KD is fading. We believe this to be sidc-effect of optimising for the average accuracy across submodels, which also yielded the T We leave the exploration of alternative weighted KD strategies as future work. Overall, the use of KD significantly improves the performance of the global model, yielding gains of 0.71 and 2.63 pp for CIFAR10 and FEMNIST and 0.10 for Shakespeare.
1 strategy.
5.4
FjORD's Deployment Flexibility
5.4.1 Device Clusters Scalability
An important characteristic of FjORD is its ability scale to a larger number of device clusters or, equivalently, perform well with higher granularity of values. To illustrate this, we test the performance of OD across setups, uniform-5 and -10 (defined in $5.1)
As shown in Fig. 6 FjORD sustains its performance even under the higher granularity of p values. This means that for applications where the modelling of clients needs to be more fine-gra mne-grained, FjORD can still be of great value, without any significant degradation achieved accuracy per submodel. This further supports the use-case where device-load needs to be modelled explicitly in device clusters (e.g. modelling device capabilities and load with deciles).
5.4.2 Adaptability to Device Distributions
In this section, we make similar case about FjORD's elasticity with respect to the allocation of available devices to each cluster. We adopt the setup of uniform-5 once again, but compare across drop scales 0.5 and 1.0 (defined in $5.1). In both cases, clients that support models of Pinxx E (O. 0.88) are equisized, but the former halves the percentage of devices and allocates it to the last (high-end) cluster, now accounting for 60% of the devices. The rationale behind this is that the majority of participating devices are able to run the whole original model.
The results depicted in Fig. show that the larger submodels are expectedly more accurate, being updated more often. However, the same graphs also indicate that FjORD does not significantly degrade the accuracy of the smaller submodels in the presence of more high-tier devices (i.e. ds 0.5). This a direct consequence of sampling p values during local rounds, instead of tying each tier with only the maximal submodel it can handle. We should also note that we did not alter the uniform sampling in this case on the premise that high-end devices are seen more often, precisely to illustrate FjORD's adaptability to latent user device distribution changes of which the server may not be aware.
6 Related Work
Dropout Techniques. Contrary to conventional Random Dropout [59]. which stochastically drops different, random set of a layer's units in every batch and is typically applied for regularisation purposes, OD employs a structured ordered dropping scheme that aims primarily at tunably reducing the computational and memory cost of training and inference. However, OD can still have an implicit regularisation effect since we encourage learning towards the tap-ranked units (e.g. the left-most units in the example of Fig. 2) these units will be dropped less often during training. Respectively,
8

---

00
75
78-
70-
24
TJRRD uy drop scate FORRD wi KD drop scale
Uniforn SORRD
0.2
0.4
0.6 zubmoda (p)
0.3
0.2
0.8
2.8
(a) CNN FEMNIST
(a) CNN- FEMNIST
-36
-4.00
Nangeton pleplendty
-30
-4.25
-4.50
-60
-4.55
-42
-64
FJORI RD -dop ScalN RIORD drop
-525
Unform 10 FJORD wi KD
Unform - PJORD or KG
-66
02
0.4
0,5
0.8
1.0
submodee
submcodt (9)
(b) RNN Shakespeare
(b) RNN- Shakespeare
Figure 7: Demonstration of the adaptability of FjORD across different device distributions.
Figure 6: Demonstration of FjORD's scalability with respect to the number of device clusters. at inference time, the load of client can be dynamically adjusted by dropping the least important units, i.e. adjusting the width of the network.
To the best of our knowledge, the only similar technique to OD is Nested Dropout, where the authors proposed a similar construction, which is applied to the representation layer in autoencoders (54) in
order to enforce identifiability of the learned representation or the last layer of the feature extractor 22 to learn an ordered set of features for transfer learning. our case, we apply OD to every layer to clastically adapt the computation and memory requirements during training and inference.
Traditional Pruning. Conventional non-FL compression techniques can be applicable the network size and computation needs. The majority of pruning methods [18] [6] 337 335 49]
reduce
aim to generate a single pruned model and require access to labelled data in order to perform costly fine-tunin/ccalibraii for each pruned variant. Instead, FjORD's Ordered Dropout enables the deterministic extraction of multiple pruned models with varying resource budgets directly after training. In this manner, we remove both the excessive overhead of fine-tuning and the need for
labelled data availability, which is crucial for real-world, privacy-aware applications [60 [56. Finally,
other model compression methods 13 64 9
remain orthogonal to FjORD.
System Heterogeneity. So far, although substantial effort has been devoted to alleviating the
statistical heterogeneity [88) among clients [58] 36
26 12 40). the system heterogeneity has largely remained unaddressed. Considering the diversity of client devices, techniques on client selection [50]
and control of the per-round number of participating clients and local iterations [55] 65 have been developed. Nevertheless, as these schemes are restricted to allocate a uniform amount of work to each selected client, they either limit the model complexity to fit the lowest-end devices or exclude slow clients altogether. From an aggregation viewpoint, (39 allows for partial results to integrated to the global model, thus enabling the allocation of different amounts of work across heterogeneous clients. Despite the fact that each client is allowed to perform a different number of local iterations based on its resources, large models still cannot be accommodated on the more constrained devices.
Communication Optimisation. The majority of existing work has focused on tackling the communi- cation overhead in FL. 32 proposed using structured and sketched updates to reduce the transmitted data. ATOMO [1 introduced a generalised gradient decomposition and sparsification technique, aiming to reduce the gradient sizes communicated upstream. [17] adaptively select the gradients' sparsification degree based on the available handwidth and computational power. Building upon gradient quantisation methods 44 23 53 25). (2) proposed using quantisation in the model sharing and aggregation steps. However, their scheme requires the same clients to participate across all rounds, and is, thus, unsuitable for realistic settings where clients' availability cannot be guaranteed. Despite the bandwidth savings, these caamunicaaiionopiimisinn approaches do not offer computational gains nor do they address device heterogeneity. Nonetheless, they remain orthogonal to our work and can be complementarily combined to further alleviate the communication cost.

---

Computaton-Coomunicaali Communication Co-optimisation. A few works aim to co-optimise both the compu- tational and bandwidth costs. PruneFL (29 proposes an unstructured pruning method. Despite the similarity to our work in terms of pruning, this method assumes a common pruned model across all clients at a given round, thus not allowing more powerful devices to update more weights. Hence, the pruned model needs to meet the constraints of the least capable devices, which severely limits the model capacity. Moreover, the adopted unstructured sparsity is difficult to translate to processing speed gains [67]. Federated Dropout [8] randomly sparsifies the global model, before sharing it to the clients. Similarly to PruneFL, Federated Dropout does not consider the system diversity and distributes the same model size to all clients. Thus, it is restricted by the low-end devices or excludes them altogether from the FL process. Additionally, Federated Dropout does not translate to computational benefits at inference time, since the whole model is deployed after federated training.
Computation-
Contrary to the presented works, our framework embraces the client heterogeneity, instead of treating it as limitation, and thus pushes the boundaries of FL deployment in terms of fairness, scalability and performance by tailoring the model size to the device at hand, both at training and inference time, in wewpoooeeeeelleeeeeeeeeeeeeeeeee
manner.
7 Conclusions & Future Work
In this work, we have introduced FjORD, federated learning method for heterogeneous device training. To this direction, FjORD builds on top of our Ordered Dropout technique as a means to extract submodels of smaller footprints from main model in a way where training the part also participates in training the whole. We show that our Ordered Dropout is equivalent to SVD for linear mappings and demonstrate that FjORD's performance in the local and federated setting exceeds that of competing techniques, while maintaining flexibility across different environment setups.
In the future, we plan to investigate how FjORD can be deployed and extended to future-gen devices and models in a life-long manner, the interplay between system and data heterogeneity for OD-based personalisation well as alternative dynamic inference techniques for tackling system heterogeneity.
Broader Impact
Our work has a dual broader societal impact: i) on privacy and fairness in participation and ii) on the environment. On the one hand, centralised DNN training [19] has been the norm for a long time, mainly facilitated by the advances in server-grade grade accelerator design and cheap storage. However, this paradigm comes with a set of disadvantages, both in terms of data privacy and energy consumption. With mobile and embedded devices becoming more capable and FL. becoming a viable alternative 77 one can leverage the free compute cycles of client devices to train models on-device, without data ever leaving the device premises. These devices, being typically battery-powered, operate under a more constrained power envelope compared to data-center accelerators (0. Moreover, these devices are already deployed in the wild, but typically not used for training purposes. What FjORD contributes is the ability for even less capable devices to participate in the training process, thus increasing the representation of low-tier devices (and by extension the correlated demographic groups). well adding to the overall compute capabilities of the distributed system whole, potentially offsetting part of the carbon footprint of centralised training data centers [52]
However, moving the computation cost from the service provider to the user of the device is nonnnegligible step and the user should be made aware what their device is used for, especially they are contributing to the knowledge of model they do not own. Moreover, while many large data centers [11 15 are increasingly dependent on renewable resources for meeting their power demands, this might not be the case for household electricity, which may impede the sustainability of training on device, at least the short run.
Funding Disclosure
This work was entirely performed at and funded by Samsung AI.
References
[1] Mario Almeida, Stefanos Laskaridis, Iliss Leontiadis, Stylianos I. Venieris, and Nicholas D. Lane. EmBench: Quantifying Performance Variations of Deep Neural Networks Across Modern Commodity Devices. In The 3rd International Workshop on Deep Learning for Mobile Systems and Applications (EMDL), 2019.
10

---

[2] Mohammad Mohammadi Amiri, Deniz Gunduz, Sanjeev R Kulkamni, and H Vincent Poor. Federated Learning with Quantized Global Model Updates. arXiv preprint arXiv:2006.1067 2020.
[3] Apple. Learning with Privacy at Scale. In Differential Privacy Team Technical Report, 2017.
[4] Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How To Backdoor Federated Learning. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2938-2948, 2020.
[5] Daniel J Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, and Nicholas D Lane. Flower: A Friendly Federated Learning Research Framework. arXiv preprint arXiv:2007.14390 2020.
[6] Keith Bonawitz et al. Practical Secure Aggregation for Privacy-Preserving Machine Learning. In Proceedings of the 2017 ACM SIGSAC Conference Computer and Communications Security (CCS), 2017.
[7] Keith Bonawitz et al. Towards Federated Learning at Scale: System Design. In Proceedings of Machine Learning and Systems (MI.Sys), 2019.
[8] Sebastian Caldas, Jakub Konečný, Brendan McMahan, and Ameet Talwalkar. Expanding the Reach of Federated Learning by Reducing Client Resource Requirements. In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentiality, 2018.
[9] Eukasz Dudziak, Mohamed S Abdelfattah, Ravichander Vipperla, Stefanos Laskaridis, and Nicholas D Lane. ShrinkML: End-to-End ASR Model Compression Using Reinforcement Learning. INTERSPEECH, pages 2235-2239, 2019.
[10] European Commission. GDPR: 2018 Reform of EU Data Protection Rules.
[11] Facebook. Software, servers, systems, sensors, and science: Facebook's recipe for hyperefficient data centers. https://tech. fb. http://wwh....coooooooe.eetttttt January 10, 2022.
2021. Accessed:
[12] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized Federated Learning with Theoretical Guarantees: Model-Agnostic Meta-Learning Approach. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[13] Biyi Fang, Xiao Zeng, and Mi Zhang. NestDNN: Resource-Aware Multi-Tenant On-Device Deep Learning for Continuous Mobile Vision. In Proceedings of the 24th Annual International Conference Mobile Computing and Networking (MobiCom), pages 115-127, 2018
[14] Robin C. Geyer, Tassilo J. Klein, and Moin Nabi. Differentially Private Federated Learning A Client Level Perspective. In NewrIPS Workshop on Machine Learning on the Phone and other Consumer Devices (MLPCD), 2017.
[15] Google. Google datacenters efficiency.
https: www.w...oll....m... co. wuwukk/aaa about/ 2021. Accessed: January 10, 2022.
datacenters/effiie
[16] Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic Network Surgery for Efficient DNNs. In Advances Neural Information Processing Systems (NeuriPS), pages 1387-1395, 2016.
[17] Pengchao Han, Shiqiang Wang, and Kin K Leung. Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approach. In IEEE International Conference Distributed Computing Systems (ICDCS), 2020.
[18] Song Han, Jeff Pool, John Tran, and William Dally. Learning both Weights and Connections for Efficient Neural Network. Advances in Neural Information Processing Systems (NeurIPS). pages 1135-1143, 2015.
[19] K. Hazelwood et al. Applied Machine Learning at Facebook: A Datacenter Infrastructure Perspective. IEEE International Symposium on High Performance Computer Architecture (HPCA), 2018.
11

---

[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[21] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge in a Neural Network. In NeurlPS Deep Learning Workshop, 2014.
[22] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation. 1(5):1735-1780, 1997.
[23] Samuel Horváth, Chen-Yo Yu Ho, L'udovít Horväth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural Compression for Distributed Deep Learning. arXiv preprini arXiv: 10988, 2019.
[24] Samuel Horváth, Aaron Klein, Peter Richtárik, and Cédric Archambeau. Hyperparameter transfer learning with adaptive complexity. In International Conference Artificial Intelligence and Statistics, pages 1378-1386. PMLR, 2021.
[25] Samuel Horváth and Peter Richtárik. A Better Alternative to Error Feedback for Communication- Efficient Distributed Learning. In International Conference on Learning Representations, 2021.
[26] Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The Non-IID Data Quagmire of Decentralized Machine Learning. In International Conference on Machine Learning (ICML), 2020.
[27] R. Hu, Y. Guo, H. Li, Q. Pei, and Y. Gong. Personalized Federated Learning With Differential Privacy. IEEE Internet of Things Journal (JIOT), 7(10):530--5539 2020.
[28] Andrey Ignatov, Radu Timofte, Andrei Kulik, Seungsoo Yang, Ke Wang. Felix Baum, Max Wu, Lirong Xu, and Luc Van Gool. AI Benchmark: All About Deep Learning on Smartphones in 2019. In International Conference on Computer Vision Workshops (ICCVW), 2019.
[29] Yuang Jiang. Shiqiang Wang, Bong Jun Ko, Wei-Han Lee, and Leandros Tassiulas. Model Pruning Enables Efficient Federated Learning on Edge Devices. In Workshop on Scalability, Privacy, and Security in Federated Learning (SpicyFL), NeurlPS, 2020.
[30] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. arXiv preprint 192.04791. 2019.
[31] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In International Conference on Machine Learning (ICML), 2020.
[32] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated Learning: Strategies for Improving Communication Efficiency. In NeurlPS Workshop on Private Multi-Party Machine Learning, 2016.
[33] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[34] Stefanos Laskaridis, Stylianos I. Venieris, Hyeji Kim, and Nicholas D. Lane. HAPI: Hardware- Aware Progressive Inference. In International Conference on Computer-Aided Design (ICCAD), 2020.
[35] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: Single-Shot Network Pruning based on Connection Sensitivity. In International Conference on Learning Representations (ICLR), 2019.
[36] Daliang Li and Junpu Wang. FedMD: Heterogenous Federated Learning via Model Distillation. In NeurIPS 2019 Workshop on Federated Learning for Data Privacy and Confidentiality, 2019.
[37] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning Filters for Efficient ConvNets. In International Conference on Learning Representations (ICLR), 2016.
12

---

[38] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated Learning: Chal- lenges, Methods, and Future Directions. IEEE Signal Processing Magazine, 2020.
[39] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated Optimization in Heterogeneous Networks. In Proceedings of Machine Learning and Systems (MLSys), 2020.
[40] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair Resource Allocation in Federated Learning. In International Conference on Learning Representations (ICLR), 2020.
[41] Xiaoxiao Li, Meirui JANG, Xiaofei Zhang, Michael Kamp, and Qi Dou. (ed) Federated Learning Non- (IID) Features via Local Batch Normalization. In International Conference on Learning Representations (ICLR), 2021.
[42] Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas B Allen, Randy P Auerbach, David Brent, Ruslan Salakhutdinov, and Loouis-Philipe Morency. Think Locally, Act Globally: Federated Learning with Local and Global Representations. In NeurIPS 2019 Workshop Federated Learning, 2019.
[43] Robert LiKam Wa and Lin Zhong. Starfish: Efficient Concurrency Support for Computer Vision Applications. In Proceedings of the 13th Annual International Conference on Mobile Systems, Applications, and Services (MobiSys), pages 213-226, 2015.
[44] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training. In International Conference on Learning Representations (ICLR), 2018.
[45] Bing Luo, Xiang Li, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Cost-Effective Federated Learning Design. In INFOCOM, 2021.
[46] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication Efficient Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
[47] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning Differentially Private Recurrent Language Models. In International Conference on Learning Representations (ICLR), 2018.
[48] Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting Unintended Feature Leakage in Collaborative Learning. In IEEE Symposium Security and Privacy (SP), pages 691-706, 2019.
[49] Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance Estimation for Neural Network Pruning. In Proceedings the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1224-11272, 2019.
[50] Takayuki Nishio and Ryo Yonetani. Client Selection for Federated Learning with Heterogencous Resources in Mobile Edge. In IEEE International Conference on Communications (ICC), 2019.
[51] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, Righ-Peerfrrancc Deep Learning Library. In Advances in Neural Information Processing Systems (NeurIPS), pages 8026-8037 2019.
[52] Xinchi Qiu, Titouan Parcollet, Daniel J. Beutel, Taner Topal, Akhil Mathur, and Nicholas D. Lane. A first look into the carbon footprint of federated learning. CORR, abs/2010.06537. 2020.
[53] Aditya Rajagopal, Diederik Vink, Stylianos Venieris, and Abristos-Savvar Bouganis. Multi- Precision Policy Enforced Training (MuPPET) A PrecisionSSwitchig Strategy for Quantised Fixed-Point Training of CNNs. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 7943-7952, 2020.
13

---

[54] Oren Rippel, Michael Gelbart, and Ryan Adams. Learning Ordered Representations with Nested Dropout. In International Conference on Machine Learning (ICML), pages 1746-1754, 2014.
[55] F. Sattler, S. Wiedemann, K. R. Müller, and W. Samek. Robust and Communication--ffiicce Federated Learning From Non-ii.d. Data. IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 31(9)3440-33411 2020.
[56] Reza Shokri and Vitaly Shmatikov. Privacy-Preserving Deep Learning In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1310-1321, 2015.
[57] Sidak Pal Singh and Martin Jaggi. Model Fusion via Optimal Transport. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
(58) Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated Multi- Task Learning. In Advances Neural Information Processing Systems (NeurIPS), 2017.
[59] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learning Research (JMLR), 15(56):1929-1955 2014.
[60] Martin J Wainwright, Michael Jordan, and John C Duchi. Privacy Aware Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2012.
[61] Hongyi Wang. Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. ATOMO: Communication Effiicien Learning via Atomic Sparsification. Advances Neural Information Processing Systems (NeurlPS), 2018.
[62] Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khaza- eni. Federated Learning with Matched Averaging. In International Conference on Learning Representations (ICLR), 2020.
[63] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the Ob- jective Inconsistency Problem in Heterogeneous Federated Optimization. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[64] Kuan Wang, Zhijian Liu, Yujun Lin, Ji Lin, and Song Han. HAQ: Hardware-Aware Automated Quantization with Mixed Precision. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR), pages 8612-8620, 2019.
[65] Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive Federated Learning in Resource Constrained Edge Computing Systems. IEEE Journal on Selected Areas in Communications (JSAC), 37(6), 2019.
[66] C. Wu et al. Machine Learning at Facebook: Understanding Inference at the Edge. In IEEE International Symposium on High Performance Computer Architecture (HPCA), 2019.
[67] Zhuliang Yao, Shijie Cao, Wencong Xiao, Chen Zhang, and Lanshun Nie. Balanced Sparsity for Efficient DNN Inference on GPU. In AAAI Conference on Artificial Intelligence (AAAI), volume 33, pages 5676-5683, 2019.
[68] Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian Nonparametrie Federated Learning of Neural Networks. In International Conference on Machine Learning (ICML), pages 7252-7261. PMLR, 2019.
[69] Barret Zoph and Quoe Le. Neural Architecture Search with Reinforcement Learning. In International Conference on Learning Representations (ICLR), 2017.
14


Reviews:
[{"review_id": "vT5W_gEJGxz", "reviewer": "Reviewer_Pjs4", "summary": "The paper considers system heterogeneity in federated learning where different devices may have distinct processing capabilities or network bandwidth. Prior work addressed this scenario by not considering lower-end devices or scaling down models to fit all participants. In contrast, this paper proposes a novel (ordered) dropout technique to dynamically prune a shared model without sacrificing accuracy. Unlike random dropout, ordered dropout induces hierarchical pruning, allowing for efficient training via knowledge distillation. The paper empirically validates the proposed method on various federated learning benchmarks, demonstrating superior performance over the state-of-the-art.", "questions": "", "limitations": "", "rating": 7, "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": "**Originality:** The paper proposes the first method addressing system heterogeneity in federated learning. To that end, the paper develops a novel form of dropout, which leverages a hierarchical structure to ensure good performance across a wide range of device capabilities. Related work is adequately cited.\n\n**Quality:** The submission is technically sound, and the method is empirically validated on various federated learning benchmarks. However, the code was not submitted.\n\n**Clarity:** The paper is clearly written and well organized. However, the section heading margins have been substantially decreased. I am not sure whether this is grounds for rejection (according to the [NeurIPS 2021 Style Files](https://media.neurips.cc/Conferences/NeurIPS2021/Styles/neurips_2021.pdf)), but it significantly reduces readability and should be changed.\n\n**Significance:** Unlike prior work, which does not consider system heterogeneity or resorts to suboptimal approaches such as dropping lower-end devices or downscaling the shared model, the proposed method embraces heterogeneity. Consequently, the proposed technique is simple yet elegant and provides a practical solution to a relevant problem in federated learning.\n\n**Questions**\n\n- How do ordered dropout and knowledge distillation ordered dropout compare in terms of running time? Knowledge distillation might be significantly more expensive since it always evaluates the largest possible model.\n- How do you achieve good accuracy with $\\alpha = 1$ where the loss consists entirely of the KL divergence term?\n- What do $U$ and $V$ correspond to in Theorem 1? After reading the proof, I assume that they denote the network layers, but the reader should not have to guess.\n- How do you evaluate federated dropout or extended federated dropout on devices with low capabilities? While random dropout prunes neurons during training, these neurons are all present at inference time.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper fails to discuss potential negative societal impacts within the page limit (as required by the [NeurIPS blog](https://neuripsconf.medium.com/introducing-the-neurips-2021-paper-checklist-3220d6df500b)).", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "cK7umYvwCR", "reviewer": "Reviewer_7FTD", "summary": "The paper proposed a scheme for training deep models in the setup of federated learning, where updates to different nested submodels can be trained at different clients with different hardware capabilities.\n\n(+) I appreciate solid grounding in practical motivation with potential significant practical value, and I would love to see further works in this direction.\n\n(-) I feel execution on these ideas is not good enough, especially in terms of matching empirical baselines. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "### Presentation\n\nOverall, the paper reads well, clearly describes relation to prior work, and its contributions. I only have minor comments and suggestions for improvement.\n\nOne detail in presentation I found confusing is in Sec 1-3 is whether the target impact of this work is on training or deployment for inference. In some way both, but I think these two points are somewhat confusingly entangled and may be worth explicitly separating as two distinct values delivered.\n\nIn Fig 2, I find the visualization misleading. The two diagrams for p=0.2 are networks functionally equivalent with respect to permutation of activations. I believe the crucial feature of proposed approach is the relation in line 113, and should be promoted in the narrative. I see it as the main originality / novelty, and while the idea may seem simple, I think it is very important.\n\nLines 81-83 I don't get the comment about computational benefits. No matter how random neurons are sampled, in the setup you have, you can still represent the model forwards / backward pass using dense matrix multiplies of smaller size. \n\nSec 3.1, the focus on layers when explaining the idea seems confusing to me, as it primarily impacts how adjacent layers interact. Moreover, the presentation seems to apply only to something that would fit into tf.keras.Sequential, but really is more general. \n\nSec 3.3 feels quite disruptive in the overall flow. I would either move it completely to appendix, leaving just a brief shoutout, or include more details about what this actually means. U, V are for instance not even defined, and I can't really understand what you try to say without looking at the appendix.\n\nIn Alg 1, server already makes a decision about what submodel to send to a client ( p_{max}^i ). If that is already the case, why not also include the sampling in the server's decision and save some communication? [I now see this would not quite work for KD variant]. Perhaps look up how could the story be improve with PIR here [your 31, Sec 4.2.1].\n\nEq (2) - I think this is a problem only if you are aggregating the updated models. If you instead aggregate the model updates (difference between initial and updated model), this would not be a problem (?) Similarly, paragraph in line 201+ seems not relevant afterwards (?)\n\n\n\nFig 4/5 have overlap in the same data (FjORD w/ KD) but different color. That is confusing.\n\n### Experimental evaluation\n\nMajor problem I see is lack of focus on recovering solid baseline model quality.\n\nIn Fig 3. I would like to see additional baseline, which should make a strong case for the OD idea and highlight why line 113 is important. That is, take the SM p=1.0 model, and create random submodels from it for smaller p values. I would expect the model quality to be below the OD line. **Could you please include this in response?**\n\nFor CIFAR 10 dataset partitioning, I would like to see something else than uniform split. See perhaps \"Reddi et al, Adaptive Federated Optimization\" for ideas. But even then, I would be looking more at the other two datasets.\n\nSomewhere, I would in more detail explain how to apply the idea to RNNs, I think that is not at all intuitive.\n\nThe major problem I see is in Fig 4/5. The accuracies are significantly below baselines (omitted from these figures). Baselines presented in Fig 2 in this paper (!) and also other works, for instance in mentioned \"Reddi et al., Adaptive Federated Optimization\". I see this as a significant problem for this work which is focused primarily on the practical side of things. \n\nIf you are able to almost match the baselines for p=1.0, and have this additional message that submodels are readily available, that would be a very strong message to me. As is, it appears as collection of regimes that do not quite work, yet.\n\n### Ideas for improvement\n\nI would mainly focus on narrowing the gap from existing baselines.\n\nI like the messaging around device heterogeneity. What is completely missing, is that the device hardware is likely going to correlate with the data available to it. I think if you took a richer dataset, maybe stackoverflow which contains lot more information based on which to partition the data, you could create a setup when comparing full model trained on a single cluster, and FjORD trained model on two (or all) clusters. There is a chance that creating really strong contribution would be easier with such larger / richer dataset, than it is with the simple datasets used in the current submission.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "5m7jVmR04wL", "reviewer": "Reviewer_WKyC", "summary": "This paper offers a dropout approach to account for different client resources. The idea is simply through pruning the network where clients fit smaller networks. The papers also offers an approach called ordered dropout where end layers are dropped rather than random neurons. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "The paper idea is interesting. Below are my main concerns: \n\n1) Starting from the title the paper claims this approach induces fairness. How and why ? Having clients with less computational power train smaller models does not guarantee any fairness. Perhaps it might even hurt it. The authors needs to clearly define a measure of fairness and if not prove at least test how this measure is improved. Ex: is the distribution of accuracy across clients narrowed ? \n\n2) The authors are encouraged to check convergence. This idea of ordered pruning can induce bias in gradients, especially if clusters are imbalanced ! Will the method still recover a meaningful solution ?\n\n3) The idea of clustering is strange. One would expect clusters to be done based on P_{y|x} at each client or perhaps P_{y,x}. The authors instead cluster and aggregate within clients of similar capabilities. What about heterogeneity is the data distribution ? what if clients is same clients (computation wise) are very different in data distribution\n\n4) The authors need to benchmark with more models and personalization approaches.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper develops new techniques for tackling system heterogeneity (i.e., diversity in the processing capabilities and network bandwidth of clients) in federated learning. The paper highlights the practical issue of system heterogeneity in federated learning that is often ignored in many papers. All the reviewers agree that the paper has interesting ideas and solves an important problem, and are in favor of accepting the paper. Along with data heterogeneity, systematic study of system heterogeneity can potentially have significant practical value and can be of interest to a wider audience. I recommend acceptance of the paper. I suggest the authors address the concerns of the reviewers in the final revision.
Decision: Accept (Spotlight)