FedorAS: Federated Architecture Search under system heterogeneity
Authors: Łukasz Dudziak
Stefanos Laskaridis
Javier Fernandez-Marques
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Neural Architecture Search
Deep Learning
Efficient DNN Training

Abstract: Federated learning (FL) has recently gained considerable attention due to its ability to learn on decentralised data while preserving client privacy. However, it also poses additional challenges related to the heterogeneity of the participating devices, both in terms of their computational capabilities and contributed data. Meanwhile, Neural Architecture Search (NAS) has been successfully used with centralised datasets, producing state-of-the-art results in constrained or unconstrained settings. However, such centralised datasets may not be always available for training. Most recent work at the intersection of NAS and FL attempts to alleviate this issue in a cross-silo federated setting, which assumes homogeneous compute environments with datacenter-grade hardware. 
In this paper we explore the question of whether we can design architectures of different footprints in a cross-device federated setting, where the device landscape, availability and scale are very different. To this end, we design our system, FedorAS, to discover and train promising architectures in a resource-aware manner when dealing with devices of varying capabilities holding non-IID distributed data. We present empirical evidence of its effectiveness across different settings, spanning across three different modalities (vision, speech, text), and showcase its better performance compared to state-of-the-art federated solutions, while maintaining resource efficiency.

Under review as a conference paper at ICLR 2023
FEDORAS: FEDERATED ARCHITECTURE SEARCH UNDER SYSTEM HETEROGENEITY
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) has recently gained considerable attention due to its ability to learn on decentralised data while preserving client privacy. However, it also poses additional challenges related to the heterogeneity of the participating devices, both in terms of their computational capabilities and contributed data. Mcanwhile, Neural Architecture Search (NAS) has been successfully used with centralised datasets, producing ttateooftthe-ae results in constrained or unconstrained settings. However, such centralised datasets may not be always available for training. Most recent work at the intersection of NAS and FL attempts to alleviate this issue in a cross-silo federated setting, which assumes homogeneous compute environments with datacenter we can design architectures of different footprints in a cross-device federated setting, where the device landscape, availability and scale are very different. To this end, we design our system, FedorAs, to discover and train promising architectures in resource-aware manner when dealing with devices of varying capabilities holding non-lID distributed data. We present empirical evidence of its effectiveness across different settings, spanning across three different modalities (vision, speech, text), and showcase its better performance compared to state state-of-the the--rrtt federated solutions, while maintaining resource efficiency.
hardware. In this paper we explore the question of whether
INTRODUCTION
As smart devices become omnipresent where we live, work and socialise, the MI.-powered services that these provide grow in sophistication. This ambient intelligence has undoubtedly been sustained by recent advances Deep Learning (DL) across a multitude of tasks and modalities. Parallel to this race for state-of-the-art performance in various in DL benchmarks, mobile and embedded devices also became more capable to accommodate new Deep Neural Network (DNN) designs [37], some even integrating specialised accelerators their System- On-Chips (SoC) (e.g. NPUs) to efficiently run DL workloads (3]. These often come in various sonfigurations in terms of their compute/memory capabilities and power envelopes 4 and co-exist in the wild rich multi-generational ecosystem (system heterogeneity) [79]. These devices bring intelligence through users' interactions, also innately heterogeneous amongst them, leading non-independent or identically distributed (non-IID) data in the wild (data heterogeneity).
Powered by the recent advances in SoCs' capabilities and motivated by privacy concerns custody of data, Federated Learning (FL) (58) has emerged as a way of training on-device on user data without it ever directly leaving the device premises. However, FL training has largely been focused on the weights of static global model architecture, assumed to be runnable by every participating client [40]. Not only may this not be the case, but it can also lead to subpar performance of the overall training process in the presence of stragglers or biases in the case of consistently dropping certain low-powered devices. On the opposite end, more capable devices might not fully take advantage of their data if the deployed model is of reduced capacity ensure all devices can participate [52].
1 over the
Parallel to these trends, Neural Architecture Search (NAS) has become the de facto mechanism to automate the design of DNNs that meet the requirements (e.g. latency, model size) for these to run on resource-comee comturce-c devices. The success of NAS can be partly attributed to the fact that these frameworks are commonly in datacenters, where high-performing hardware and/or large curated

---

Under review as a conference paper at ICLR 2023
62 62 are available. However, this also imposes two major limitations current NAS approaches: i) privacy, i.. these methods were often not designed to work in situations when user's s data must remain on-device; and, consequently, ii) tail data non-discoverabiliny i.. they might never be exposed to infrequent or time/user-specifee data that exist in the wild but not necessarily in centralized datasets. On top of these, the whole cost is born by the provider and separate on-device mooellligg/poffiiin needs to be done in the case of hardware-aware NAS [26 73 45)
datasets + 23 20
39
which has mainly focused on inference performance hitherto.
Motivated by the aforementioned phenomena and limitations of the existing NAS methods, we propose FedorAS, a system that performs NAS over heterogeneous devices holding heterogeneous data in a resource-aware and federated manner. To this direction, we cluster clients into tiers based on their capabiliities and design supernet comprising operations covering the whole spectrum of compute complexities. This supernet acts both as search space and a weight-sharing backbone. Upon federation, is only partially and stochastically shared to clients, respecting their computational and bandwidth capabilities. In turn, we leverage resource-aware one-shot path sampling (28) and adapt it to facilitate lightweight on-device NAS. In this way, networks in a given search space are not only deployed in aeseurce-aware manner, but also trained as such, by tuning the downstream communication (i.e. the subspace explored by each client) and computation (i.e. FLOPs of sampled paths) to meet the device's 's training budget. Once federated training of the supernetwork has completed, usable pretrained networks can be extracted even before performing fine-tuning or personalising per device, thus minimising the number of extra on-device training rounds to achieve competitive performance.
In summary, in this work we make the following contributions:
We propose a system for resource efficient federated NAS that can be applied in cross-device set- tings. where partial device participation, device and data heterogeneity are innate characteristics. We implement a system called F FedorAS (Federated nAS) that leverages a server-resident supernet enabling weight sharing for efficient knowledge exchange between clients, without directly sharing common model architectures with one another.
We propose a novel aggregation method named OPA (OPerator Aggregation) for weighing updates from multiple ssingle-path one-shot" client updates in frequency-
manner. We empirically evaluate the performance and convergence of our system under IID and non- settings across different datasets, tasks and modalities, spanning different device distributions and compare our system's 's behaviour against state-of of-thc-art FL techniques.
BACKGROUND & MOTIVATION
Federated Learning. A typical FL pipeline is comprised of three distinct stages: given global
model initialised on a central server, wa (t=0) i) the server randomly samples & clients out of the available K (k < K for cross-device; [10] k = K for cross-silo setting) and sends them the current state of the global model; ii) those clients perform training on-device using their own data partition,
D,, for a number of epochs and send the updated models, wi back to the server after local training is
completed; finally, iii) the server aggregates these models and a new global model, wi (l+1) is obtained.
This aggregation can be implemented in different ways [58 70 [3]. For example, in FedAvg (58)
each update is weighted by the relative amount of data on each client: wg ((+1) = > Σ -i- [D,
Stages ii) and iii) repeat until convergence. The quality of the global model Wg can be assessed: on the globul test set; by evaluating the fit of the w/ each participating client's 's data (D,) and derive fairness metrics [54]; or, by evaluating the adaptability of the Wg to each client's 's data or new data these might generate over time, this is commonly referred to as personalised FL. (27 51].
Contrary to traditional distributed learning, cross-device FL performs the bulk of the compute on a highly heterogeneous [40] set of devices in terms of their compute capabilities, availability and data distribution. In such scenarios, a trade-off between model capacity and client participation arises: larger architectures might result in more accurate models which may only be trained fraction of the available devices; on the other hand, deploying smaller footprint networks could target more devices and thus more data for training, but these might be of inferior quality (gap in Fig. D
Neural Architecture Search. NAS is usually defined as a bi-level optimisation problem:
a" arg min (W,, Do), where w (Dz) = arg min L(was D:) W,
(1)
aEA
2

---

Under review as a conference paper at ICLR 2023
CIFARID HID (LDA a=1000)
CIFARIO non-lID (LDA e-1.0)
90
Tler
Ter
88
Ferr
Mer
Tiend
86-
86-
Test acquraty
84
Tier unaware
84-
Client partiopetion gap
82-
Client
participation gap
(naivel Tier aware (FedorAS)
82
80-
80
78
78-
100
400 FLOPS (M)
700
100
700
FLOPS (M)
Figure 1: For three I.DA settings, 160 architectures randomly sampled from ResNet-like search space and trained CIFAR-10 10 FL. setup with 100 clients, with 10 clients participating on each round for total of 500 rounds. Clients are uniformly assigned a tier, resulting in 25 clients per tier. Given sufficient data and ignoring tier limits, model performance tends to improve as its footprint (FLOPS) increases (black crosses). However, when models are restricted to only train on clients that support them (tier-aware), the lack of data severely restricts the performance of more capable models (red dots). FedorAS successfully overcomes the challenges of tier-aware and outperforms existing system heterogeneous basclines, as shown later in Fig.
where A is a finite (discrete) set of architectures to search from (a search space), C is a loss function, wa are weights of model with architecture o, and D(v,)) are validation and training datasets, respectively. The main challenge of NAS comes directly from the fact that in order to assess quality of different architectures (outer optimisation), we have to obtain their optimal weights which entitles conducting full training (inner optimisation).
There exist multiple approaches speed up NAS 65 56
More relevant to our work are those utilising the concept of supernet [5 7 where single model that encapsulates all possible architectures from the search space is created and trained. Specifically, supernet is constructed by defining an operator that incorporates all candidate operations (the set of which we denote by Ct) for each searchable layer common choice is to define it as a weighted
sum of candidates' individual outputs yι = Eoeo, aj (o) * o(y:-1), where factors {ai layer/ can be defined differently for different methods (e.g, continuous parameters [56] 16 25 or
) JoED, of each
random one-hot vectors (28)). Importantly for us, methods that use sparse weighting factors can avoid executing operations associated with zero weights, saving both memory and compute [16 28
After a supernet has been constructed and trained, searching for at is usually performed by either investigating architectural parameters [36] 25 [6], or using zero-th order optimisation methods to directly solve the outer loop of Eq. [ while approximating w with weights taken from the supernet (thus avoiding the costly inner optimisation) 48 28). The final model can then be retrained in isolation using either random initialisation or weights from the supernet as a starting point.
Challenges of Federated NAS. As highlighted before, devices in the wild exhibit different compute capabilities and can hold non-IID distributed data, resulting in system and data heterogeneity. In the context of NAS, system heterogeneity has particularly significant effects, we might no longer be able to guarantee that any model from our search space can be efficiently trained on all devices. This inability can be attributed to insufficient compute power, limited network bandwidth unavailability of the client at hand. Consequently, some of the models might be deemed worse than others not because of their worse ability to generalise, but because they might not be exposed to the same subsets of data as others as shown in Fig. []] where we show models of different footprint trained across client of varying capabilities under constrained (tier-aware) and full (tier (ier-unaware) participation.
3 THE FEDORAS FRAMEWORK
FedorAS is resource-aware Federated NAS framework that combines: learning from clients across all tiers and yielding models tailored to each tier that benefit from this collective knowledge.
Workflow. FedorAs' workflow consists of three stages (Fig, 2): i) supernet training, ii) model search and validation and iii) model fine-tuning. First, we train the supernet in a resource-aware and federated manner (Stage 1, Sec. 3.I. We then search for models from the supernet with the goal of finding the best architecture per tier (Stage 2. Sec. Sec.B.2). Models are effectively sampled, validated on global validation set and ranked per tier. These architectures and their associated weights act as initialisation to the next phase, where each model is fine-tuned in a per-tier manner (Stage 3. Sec. 3.3). The end goal of our system is to have the best possible model per each cluster of devices.
3

---

Under review as a conference paper at ICLR 2023
pet of scnoecs Par
becha
bith
B4 Seperi
For with slant, pomple aucepees excceding badgel Be
Stege Fwe Supprrett Trerrnng
Ohrdisica haiiing with bucgelanan samping
Superna
Por- Search
agpiaption
Fix of tuid
Per-Tier Firdtumig
I-N RO00
Figure 2: Training process workflow with FedorAS.
Design rationale. We build our system around the concept of a supernet to facilitate weight-sharing between architectures of various footprints. Operations in the supernet are samplable from paths (i.e. models) of different footprint. As such, while normally large models would not be directly trained on data of low-tier clients, our design allows for indirectly sharing this knowledge through the association of the same operation to different paths. To ensure efficient training of supernet, we chose to base our approach on SPOS (28) and adapt (see Eq. 4 since its training procedure is lightweight, introducing very little overhead in terms of memory consumption and/or required floating point operations, especially compared to [56]] Last, we opted for clustering devices into "tiers" based on their computational capabilities and search for architecture for each tier balance between having one model to fit all needs (30 and a different architecture per client (60)
3.1 SUPERNET TRAINING
Search space & models. First, we define the search space in terms of range of operators options per layer in the network that are valid choices to form a network. This search space resides as a whole on the server and only partially communicated participating clients of training round to keep communication overheads minimal. Specific models (i.e. paths) consist of selections of one operator manner on-device per local iteration.
option per layer, sampled in a singlc-path-
Subspace sampling. It is obvious that communicating the whole space of operators along with the associated weights to each device becomes quickly intractable, especially bearing in mind that communication is usually a primary bottleneck in Federated Learning [40] [52] To this direction. FedorAS adopts a uniform parameter size budget, Bo and samples the search space for operators until this limit is hit (Fq. (2). Setting the limit to half the size of typical network deployed for task worked sufficiently well in experiments and in fact accelerated convergence (Sec. 4.4)
Lo, (0) < BiD Ōi C O2
1=0 DEO,
where L is the number of layer in the supernet, O, the candidate and On the selected operations in layer 1 a unit vector of valid operations and ccmmm a measure of DNN size (e.g. #parameters).
In terms of sampling strategies, experimented with uniform operator sampling, which we found to work sufficiently well and provide uniform coverage over the search space. is also worth noting that different subspace (not necessarily mutex) could be selected for each participating client in round.
Client-side sampling & local training. Participating clients receive the subspace sampled the server, {O:)/ from which they sample a single operator on every layer. This constitutes a path along the supernet (PL) representing a single model. For every batch, clients sample paths that do not surpass the assigned training budget Bieer Throughout this work, we consider T (rriin()) (t) to be a cost function that counts the FLOPs of given operator. This FLOPs limit is defined per tier so that a network does not exceed the capabilities of the target device. Our goal is to sample valid paths uniformly, to ensure systematic coverage of the entire (sub) search space during training:
I. Pr-
Ü or u(Oi) s.t. 1=0
Σ (o)) < B Tier I=0
parameriii operations are always sent downstream layers without options are prioritised guarantee valid network.
4

---

Under review as a conference paper at ICLR 2023
However, realising Eq. Befficiently is not trivial task. Originally [28], the authors considered naive approach of repeatedly sampling a path until it fits the given budget, which results in non non-negligibbe overhead if the probability of finding model under the threshold is low. Were we to employ such method, the most restricted devices, for which the set of eligible models is the smallest, would be the ones burdened with the largest overhead. Therefore, we propose a greedy approximation in which operations are selected sequentially. Specifically, in order to obtain a path pL = {o:) we sample operations layer-by-layer, according to a random permutation o, in such a way that the i-th operation is chosen from the candidates for layer (i) whose total overhead would not violate the constraint:
02 ~ ~ufo: 6o()) A
Σ P (rran((;) + P (0) < B j=0
Tier Orain
(4)
We can ensure that Eq. 4 can always obtain a valid architecture without resampling if layers have Identity among their candidate operations and prioritising the selection of those which do not.
After having sampled the path, model is instantiated and single optimization step using single batch of data is performed. The number of samples passing through each operator are kept and communicated back to the server, along with the updates, for properly weighting updated parameters upon aggregation, as we will see next.
A ggregationn with OPA. An operator gets stochastically exposed to clients data. This stems from subspace sampling and client-side path sampling. As such, naively aggregating updates in an equi- weighed manner (Plain-Ave Avg) or total samples residing on a client (FedAvg (58)) would not reflect the training experience during a round. For this reason, we propose OPA, OPerator Aggregation, an aggregation method that weights updates based on the relative experience of an operator across all clients that have updated that operator. Concretely, our method generalisation of FedAvg where normalisation is performed independently for each layer, rather than collectively for full models. In order to enable that, we keep track of how many examples were used to update each searchable operation on, independently on each client, and later use this information to weight updates. Formally:
Di=
(4)
(or)
if C
>1
w (o))
1 2.0
(5)
Wg (ot)
otherwise
where w/ (-) are global weights, w (-) are local weights of client at global step t, (D) is the number of samples having backpropagated through an operator o for client in round t. and clff) is the set of clients s.t. [D! 0. Updates to wg" happen only if c(f) > 1 in order to protect the privacy of single clients. Finally, if an operation is always selected, then Eq. recovers FedAvg. which means we can effectively use OPA throughout the model and not only for searchable layers.
3.2 MODEL SEARCH & VALIDATION
After training the supernet, search phase is implemented discover the best trained architecture per device tier. Models are sampled with NSGA-II [22) and evaluated on global validation set. The rationale behind selecting the NSGA-II algorithm for our search is the fact that it is multi-objecctive and allows us for efficient space exploration with the goal of optimising for model size in a specific tier and accuracy. Other search algorithms can be used in place of NSGA-II, based on the objective at hand. Search can stop after a specified number of steps when an accuracy threshold is met. At the end of this stage, we have a model architecture per tier, already encompassing knowledge across devices of different tiers, which serves as initialisation for further training.
3.3 FINE-TUNING PHASE
Subsequently, we move to train each of the previously produced models in a federated manner across all eligible clients. This means that architectures falling in specific tier, in terms of footprint, can be trained across clients belonging to that tier and above. Our hypothesis here is that compared to regular FL where one needs to trade off capacity of participation, FedorAS allows for better generalisation due to knowledge sharing through its supernet structure. Here we use conventional FedAvg and partial client participation per round, again with the goal of training a single network per tier.
5

---

Under review as a conference paper at ICLR 2023
Table 1: Datasets for evaluating HedorAS. We par- tition CIFAR- 100/00 following the Latent Dirichlet
Tier
Tier
87.5
Allocation (LDA) partitioning [36]. with each client
80.0
80.5
receiving approximately equisized training sets. For
80.0
CIFAR-10, we consider a E (1000, 1.0 0.1] configu-
77.5
rations, while for 1IAAR-10, we adopt = 0.1 (70)
FjORD-LDA
nieewwaae (haies)
FedorAs:
The remaining datasets come naturally partitioned.
72.5
FIORD
Search Number
Number
70.0
0
200
200
300
400
500
600
760
Datuset
Space Clients Examples Target Task
TLPPS 1MI
Figure 3: FedorAS outperforms other approaches (de-
CIFARIO
CNN-L 100
50K Image classification
tails in Appendix D.7]. CIFAR-I0 10 (non-IID, a=1.0). FjORD represented a line can switch between operating points on-the-fly via Ordered Dropout.
CIFARI00
CNN-L
500
50K Image classification
Speech Commands
CNN.S
2,112
105.8 Keyword Spotting
Shakespeare
RNN
715
38K Next char, prediction
EVALUATION
This section provides a thorough evaluation of Fedort rAS across different tasks to show its perfor- mance and generality. First, we compare FedorAS to existing approaches in the context of federated NAS in the cross-device and cross silo setting. Next, we we draw from the broader FL literature and showcase our technique's 's performance gains compared to homogeneous and heterogeneous federated solutions (Sec. (.2). This can be traced back to the benefits of supernet weight sharing; as such we, subsequently, quantify its contribution by comparing it to FedorAS with randomly initialised networks trained on eligible clients in a federated way (Sec. 4.3) without weight sharing. Last, we showcase the contribution of specific components of our system through an ablation study (Sec. and also the performance and behaviour of alternative search methods (Sec. 4.5
4.1 EXPERIMENTAL SETUP
Datasets & Baselines. Datasets summarised in Tab. I More information in Appendix D
Search space. The adopted search spaces are specific to the dataset and task at hand, both in terms of size and type of operators. In general, we assume highest tier of model sizes to coincide with a typical network footprint used for that task in the FL. literature (e.g. ResNet-18 for CIFAR-10). Nevertheless, there may be operators in the space that cannot be sampled in some tiers due their footprint. FedorAS sets the communication budget Br to be half the size of the supernet. The full set of available operators per task provided in the Appendix D.3
Clusters definition. In our experiments, we cluster clients based on the amount of operations they can sustain per round of training (#FLOPs), for simplicity. Other resources (e.g. #parameters, energy consumption) can be used in place or in conjunction with FLOPs. More details in Appendix
D.4 D.4
4.2 PERFORMANCE EVALUATION
Federated NAS. We start the evaluation by comparing our system with existing works in the federated NAS domain. Specifically, we find two systems that perform federated NAS, namely FedNAS [30 and SPIDER 60) and compare in the cross-device and cross-silo settings. In the former setting, we adapt FedNAS to support partial participation and compare their technique to FedorAS under the same cross-device settings in CIFAR- 10. Results shown in Tab, 2 showing FedorAS performing 1.04% better than FedNAS on CIFAR-1O, and 48.7% on CIFAR-10,=0.. for the same training memory footprint. Further details can be found in Appendix D.6 At the same time, while running in cross-silo setting is not the main focus of 7 FedorAS, we have adapted our experimental setting to match that of FedNAS and SPIDER. Results shown in Tab. with F FedorAS performing +1 1.6% and -1.3% than the baselines, respectively, on the test set of their selected settings.
Table 2: Cross-device federated NAS on CIFAR-10.
Table 3: Cross-silo federated NAS CIFAR- 10.
Dutaset
Method
Mem, Peak (MB)
Perf. (%)
Dataset
Method
Validation ace.
Test ace.
Adlients
FedNAS
2837
90.02
FedNAS persortiod
90.4
20
CIRARI0-11
FedNAS (4i back
1919
85.4
CIFAR
FaINAS glowl
81.2
16
PedorrAS
1996
86-4610
AedorASuwwe
97.2
98.6:a2
20
CIFARIOL
FedNAS (4))
FedNAS
2837
54.86
65.28
CIFARIQ...7
SPIDER
92,00:20
90.82
FedozAS
FRINAS reports validation for this setting.
Comparison with Random Search. We further compare our search with a random search baseline which is naive way of running FL. NAS in experimental setting (the same search space, etc.)

---

Under review as a conference paper at ICLR 2023
Table 4: Comparison with heterogeneous federated baselines. FedorAS performs better across datasets.
Dataset
Method
MFLOPs
Params
Performannc
Zerofl..oom
65
557- [35.
11.17 [0.76, 6.08, 11,16] [2,96, 2,93, 3.38, 4.32)
CIFAR 10.. 1000
FjORDunx
313,556] [111. 140, 256, 329)
[78. 78 78 25 77 19
Fedozis
6x
189,40 89 29.60 89.64:022 a9.24
Zero
66
557?
11.17 [0.70, 2.79, 6.28, 11,16]
$1,04aazs
CIPAR1O
FjORDups
19
[35, 139, 513, 556]
[78. 54 1., 79.25.a st. 78, 78.66 77 27
Fedozhi5pe
[116, 183, 262, 330)
[2.59, 2,90, 3.55, 4,31]
[85. 185,99 96.30 86,34 86.46:a.1]
C1PAR10
FjORDuy
(35, 139, 313, 516]
[0,70, 2,79, 6.28. 11.16]
(61,450034, (081 st- 59, 39,725516, 57 (455)
FedorASye
[117. 159, 238, 345)
(2.17, 2,49, 2,61]
[81,01 $1.53 80,64: 80.85:a24)
Shakespeare
FJURD 14
11,3, 11, 17, 12, 15, 21,
0J04, 0,08, 0.14, 0.21)
[4.46 3.91.8 a.87, 3.87ami, 3.87.0
(Popiccty La bomz))
Pedozhāpe dur
[0.09, 0.15, 0.18, 0.26, 0.30]
13,43 3.39 a84,
com,, a.42
SpeechCoomaads
Oar
2382
21.29
(3 daadd
PynanidFL
2382
21.29
63.84
FedortSsup
10
0,63
70.10
CR perform dient selection beaed on systzm beserngrnrity and are prosided for conteat. FL.0% compural aoaring the common [i 40x S1 MFCC franez inpor
K6 specdsup tranning w/ highty-sgarse convs, ottainable only with specialised Itw.. result obtained from the best model of setup in Appendix
and find that FedorAS performs significantly better an average of +5. +3.24pp, +12.84pp, +9.27pp. +0.25p across tiers for 1TFAR-10==(100.111 Only in the case of SpeechCommands did our search result in -0.87pp of aceuracy on average. We suspect this is an artifact of insufficiently-lnn fine-tuning which means models might not have converged (suggested by a high variance). Detailed results are provided in Appendix E.T
CIFAR-100 and Shakespeare, respectively.
Federated Learning baselines. Next, we compare the performance of FedorAS with different
federated baselines, including homogeneous [70] and system heterogeneous frameworks 34 44 66
In the former setting, we compare with results from [70] on CIFAR -00 FedorAS performs 1 PF better than the FedAvg baseline, at 45.84% but at a fraction of the cost] Simultaneously, retraining the discovered model from scratch using random initialisation under the same training setting as the baseline results in 11.43 pp higher accuracy than the best FedAdam (63. 63%944% vs 52.50%), showcasing the quality of FedorAS- -esooudedddd bespoke architectures.
With respect to heterogeneous baselines (ZeroFL [66], FjORD 34)) )) we see that FedorAS consis- tently leads to models with higher accuracy across tiers that are in the respective clients' computational budget (Tab. 4 At the same time, we depict how FedorAS performs compared to FjORD and randomly selected architectures trained naively in resource-aware manner in Fig. 3 One can clearly see that the degrees of architectural freedom that our solution offers leads to significantly better accuracy per resource tier. Notably, we perform 15.20% and 12.58% better on average than FjORD on CIFAR-10 and Shakespeare, respectively, while still respecting client eligibility.
While model accuracy may not seem to scale proportionally their size, we attribute this to the limited participation eligibility of clients, an innate trait of system heterogeneous landscape. Normally, this can cause performance gaps due to limited exposure to federated data (Fig. [T. We argue that FedorAS is able to bridge this gap (+0.03 points (p) avg). by means of weight sharing and OPA, +1 +1.72 p more effectively than FjORD (avg Tier vs Tier gap across datasets).
Additional results. Additional results on the convergence and fairness of FedorAs as well as alternative client allocation 44 to clusters are provided in Appendix G.2 and H.3 respectively.
G.2
4.3 SUPERNET SHARING WITH FEDORAS
Here, we evaluate the impact of weight sharing through FedorAS' supernet. We compare the performance of FedorAS' models to the same architectures models, but trained end-to-end in a federated manner, across all four datasets. With this comparison, we aim to showcase that F FedorAs not only comes up with better architectures, but it also effectively transfers knowledge between tiers through its supernet structure and OPA aggregation scheme. In order to accomplish that, we first train with PedorAS across the three stages described in Sec. 33 (supernet-init) Subsequently, we take the output architectures from our system, randomly initialise them and train end-to-end in federated manner, where each model trains across all eligible clients grand-init.. Results are presented in Tab. 5
Indeed, models benefit from being initialised from supernet across cases; this means that weight- sharing mitigates both the limited model capacity of the lower-tier and the limited data exposure of large models. The accuracy improvement is further magnified as non-IIID-ness increases, leading up to +15 pp over rand-init. Results on different tasks of the same dataset presented in Appendix
We smmotate ahsvlate performance differenne as (pereetagge points (plp and relarive difference %
16 GRLOPS, 11.4M 62M paramoters, 4000 va 850 global rounds (750 rouncs supernet training and 100 rounds model finetuning)
7

---

Under review as a conference paper at ICLR 2023
Table 5: Models discovered by FedorAS benefit from weight sharing across tiers. Models resulted from the search stage in FedorAS and subsequently FL- finetuedd are compared to models using the same architecture but trained end-to-end in an FL. manner (i.e. randomly initialised, rond-init) on eligible clients.
Doisert
Clients
Setting
Partitioning
Inirialisation
Classes
Tier 1
Tier
Tier 3
Tier
1000
Supernet rand-Juur
10
89.05.017
89.60):.15
87,84,031
89.64.mm
86.181008
81.27
Supernet rund--intr
25.99
86, 16..1
86.46
CIFAR-10
100
Stundard
nop- nee
87.12
86.29
83. 10
80. 80.10
non- IID 1iDaa
Supernet rand Juur
10
81.01 ooss
70.61
81,53
70.30
80.64.004
68. 29.4
80.85 ma:s
64.87
(ucc (R) Istae)
CIFAR-100
500
Standard
non- pon-IIDa-u.
Supernet rand
36.30
39.26::::1
39 39.06:132
45.42...3
36.77
45.07
Speech C Commands
(Auc botec
2112
Standard
given
Supernet rund--inn
81.92a1.2
=9.75
79.9/1294
80.47:114
78.5 78.57
81.0:1.5
80.56:
79.36
Dutaset
Client
Setting
Partitioning
Initialisation
Classes
Tier 1
Tier
Tier
Tier 4
Tier 5
(Poplaayy 1 Hilerr
Shokesppare
215
Standard
given
Supernet rund-init
3.43:100
3.44.o0
3.39
3.50g0m
3.70
3.47.006
3.40.:.01
3.52ga00
3.42a401
3.60.00
4.4 ABLATION STUDY
Next, we measure the contribution of specific components of FedorAS to the quality and per- formance of these models. To this direction, we firstly compare the performance of our system's 's aggregation compared to naive averaging. Subsequently, we measure the impact of sending smaller subspaces to clients for supernet training. We provide indicative results on CIFAR-10a=ah
OPA vs. naive averaging. OPA compared FedAvg leads to increased accuracy by +1.2, +0.9, +1.01 and +1.78 pp for tiers 1-4, respectively. More details in Appendix G.2
Subspace sampling size. FedorAS samples the supernet before communicating it client. For CIFAR-10 (a = 1.0) and when Bz... is set to 22.3M parameters (i.e. allowing sending whole supernet), FedorAs yields 85.48% 86.7 86.73% 86.50% average accuracies across tiers for full, 1/2 and 1/4 of the size of the search space, respectively. Thus, not only is the overhead of communication reduced with FedorAs, but convergence to the same level of accuracy is faster. We hypothesise that this is due a better balance in the exploration vs. exploitation trade-off. Details in Appendix G.2
4.5 EVALUATION OF THE SEARCH PIASE
In order to assess the quality of models during search (Stage 2), so far we have needed a proxy dataset to evaluate different paths and rank them. We consider this as a set of examples that each application provider has centrally measure the quality of their deployed models in production settings.
Validation set size. The size and representativeness of the centralised dataset might affect the quality of the search. To gauge the sensitivity of the end models to the underlying distribution of the validation set, we sample down the validation set, as a held-out portion of the clients datasets, to 20% and 50% of the original size. We find noticeable impact on final model quality. More in App. J.I
Federated search. There may be also cases where no such dataset can be centralised. To this direction, we test whether our search can operate under a federated setting with partial participation in order to faithfully rank the quality of models stemming from the supernet. In this setting, we have implemented a federated version of NSGA-II. Instead of candidate models being evaluated on the same validation set, they are stochastically evaluated on sampled federated client datasets [64]. We hypothesise is possible to maintain faithful ranking of models compared to centralised evaluation if enough clients are leveraged to evaluate models, at the cost of increased communication cost. Furthermore, we expect the overall cost of achieving robust evaluation to increase as non-IIID-nes and #clients increase, and the instantaneous cost of sending models to decrease over time, as NSGA-II converges to well-performing models (i.e. decreased diversity of models). Fig. 4 shows results for CIFARI0.=0.1 with extra results and details presented in Appendix J.2 Our experiments support the aforementioned conjectures. Noticeably, even under highly non- settings, we can attain faithful FE at reasonable cost (4 rounds to Kendall-7>0.8 for the results presented in Fig. 4
Correlation with final accuracy. We observe that the best models after Stage 2 are rather unlikely to be the best ones after Stage 3 (Kendall-7 0.2-0.3). However, they tend to achieve decent results, suggesting they are a safe choice we want to keep fine-tuning to the minimum. See App. [.3
RELATED WORK Data and system heterogeneity. Traditionally, works have focused on tackling the statistical data heterogeneity 72
50
35
27 54 or minimising the upstream communication cost (46 42 76 29
8

---

Under review as a conference paper at ICLR 2023
Aug tota comm.. COS (GB
0.3
1.0
0.7
60
0.8
Forr Terk
0.5
20
10
15 23
rounds
of rounds per
Figure 4: Ranking quality & cost of federated evaluation (FE) of models for CIFAR-10s=0.. during federated search. Each time a new population of models is evaluated, a minimal supernet encompassing selected models is sent to sample of clients: left) ranking correlation between scores produced by FE & centralised evaluation (CF), as a function FE, rounds (f rounds = clients); middle) total communication cost of sending all necessary supernets to all clients, to run a full search; right) changes in the supernet size as NSGA-II progresses.
the primary bottleneck in the federated training process. However, it has become apparent that computational disparity becomes an equally important barrier for contributing knowledge in FL. As such, lately, there has been line of work focusing on this very problem which affects the convergence rate or fairness of the deployed system. Specifically, such solutions draw from efficient ML and attempt dynamically alter the footprint of local models my means of structured (PruneFL [38]
HeteroFL (24). ). unstructured (Adaptive Federated Dropout [12]. LotteryFL [47] ) or importance-base
pruning (FjORD (34) ) quantisation (AQFL. 2), low-rank factorisation (FedHM (80). sparsity-
inducing training (ZeroFl. (67]) or distillation (GKT (1)) However, each approach has limitations,
either because they involve extra training overhead [31 and residence of multiple DNN copies in
memory (2), or because they require specialised hardware for performance gains (167 (2)). Last, some of the architectural changes proposed may not offer the degrees of freedom that NAS exposes
80 47 and perform uni- uni-dimensional search over the control variable across layers
may
have a different optimisation objective altogether 47
Federated NAS. The concept of performing NAS in federated setting has been considered be- However, current solutions vary greatly in their approaches and goals, with most of them being applied and applicable to the cross-silo setting, where full participation and small number of participants are expected. Specifically, one of the first works in the area was FedNAS (30) which adopts DARTS-based approach and aims to find globally good model for all clients, to be personalised at later stage. This approach requires the whole supernet to be transmitted and kept in memory for architectural updates, which leads to excessive requirements (Fig. 2 that make it largely inapplicable for cross-device setups with clients of limited capabilities. To mitigate this requirement, [8] proposes an RL-based approach for cross-silo Fl.-based NAS. Despite the intention, it still incurs significant overheads due to RL-based model sampling convergence and single model training per client. A somewhat different approach is adopted by HAFL (55), which leverages means to generate outputs of model. While interesting, performance and scalability are not on par with current state-of-the-an On the front of personalisation, FedP- NAS (32] searches for architectures with shared based component across clients and a personalised component. However, this work is only aimed at IID vision tasks and involves a meta-step for personalisation, which increases training overheads significantly. At the other extreme for cross-silo personalised FL,, SPIDER [60] aims at finding personalised architectures per client. It requires the whole space on-device and federation is accomplished through second static on-device network. These non-negligible overheads make porting this approach to the cross-device setting non-trivial.
fore (30 60 81
84 555
graph hypernetworks
In contrast, F FedorAS brings Federated NAS the cross-device setting and is designed with resource efficiency and system heterogeneity in mind. This way, communication and computation cost is kept within the defined limits, respecting the runtime on constrained devices. Crucially, our system does not assume full participation of clients and is able to efficiently exchange knowledge through the supernet weight sharing and generalise across different modalities and granularity of tasks.
6 CONCLUSION
In this work, we have presented FedorAS, a system that performs resource-efficien federated NAS in the cross-device setting. Our method offers significantly lower overhead compared to existing federated NAS techniques, while achieving state-of-the -het---r performance compared to heterogeneous FL solutions, by means of effective weight sharing and flexible resource-awer aware training.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohamed S Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Donald Lane. Zero-cost proxies for lightweight NAS. In International Conference on Learning Representations (ICLR), 2021.
[2] Ahmed M Abdelmoniem and Marco Canini. Towards mitigating device heterogeneity in federated learning via adaptive model quantization. In Proceedings of the 1st Workshop on Machine Learning and Systems, FuroMLSSs '21, pages 96-103, New York, NY, USA, April 2021. Association for Computing Machinery.
[3] Mario Almeida, Stefanos Laskaridis, Ilias Leontiadis. Stylianos Venieris, and Nicholas D Lane. EmBench: Quantifying Performance Variations of Deep Neural Networks across Modem Commodity Devices. In The 3rd International Workshop on Deep Learning for Mobile Systems and Applications (EMDL). pages 1-6, 2019.
[4] Mario Almeida, Stefanos Laskaridis, Abhinav Mehrotra, Lukasz Dudziak, Ilias Leontiadis, and Nicholas Lane. Smart at what cost? characterising mobile deep neural networks in the wild. In Proceedings of the 21st ACM Internet Measurement Conference, IMC '21, page 658 672, New York, NY, USA, 2021. Association for Computing Machinery.
[5] Mohammad Mohammadi Amiri, Deniz Gunduz, Sanjeev R Kulkarni, and H Vincent Poor. Federated Learning with Quantized Global Model Updates. arXiv preprint arXiv:2006. 10672, 2020.
[6] James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure Single-Server aggregation with Logarttoiii overhead. In Proceedings of the 2020 ACM SIGSAC Conference Computer and Communicutions Security, pages 1253-1269. Association for Computing Machinery, New York, NY, USA, October 2020.
(7) Gabriel Bender, Picter-Jan Kindermans, Barret Zoph, Vijay Vasudovan, and Quoc V. Le. Understanding and simplifying one-shot architecture search. In International Conference on Machine Learning (ICML.), 2018.
[8] Axel Berg, Mark O'Connor, and Miguel Tairum Cruz. Keyword Transformer: A Self-Attention Model for Keyword Spotting. In Proc. Interspeech 2021, pages 4249 4253, 2021.
[9] Daniel J. Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, and Nicholas D. Lane. Flower: A friendly federated learning research framework, 2020.
[10] Keith Bonawitz et al. Towards Federated Learning at Scale: System Design. In Proceedings of Machine Learning and Systems (MLSys), 2019.
[11] Keith Bonawitz. Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for Privacy-Preserving Preserving machine learning. In Proceedings of the 2017ACM ACM SIGSAC Conference on Computer and Communications Security, CCS 17, pages 1175-1191, 191, New York, NY, USA, October 2017. Association for Computing Machinery.
[12] Nader Bouacida, Jiahui Hou, Hui Zang, and Xin Liu. Adaptive federated dropout: Improving communica- tion efficiency and generalization for federated learning. In IEEE INFOCOM 2021 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 66, 2021.
[13] James Bradbury, Stephen Merity, Caiming Xiong, and Richard Socher, Quasi-recurrent neural networks. In International Conference Learning Representations (ICLR), 2017.
[14] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. CoRR, October 2017.
[15] Andrew Brock, Theo Lim, James Ritchie, and Nick Weston. SMASH: One-shot model architecture search through hypernetworks. In International Conference on Learning Representations (ICLR). 2018.
[16] Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search target task and hardware. International Conference on Learning Repressntaatins (ICLR), 2019.
[17] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 2018
[18] Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches, 2014.
[19] D. Coimbra de Andrade, S. Leo, M. Loesener Da Silva Viana, and C. Bernkopf. A neural attention model for speech command recognition. ArXiv e-prints, August 2018
10

---

Under review as a conference paper at ICLR 2023
[20] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Scharwächter, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bert Schiele. The cityscapes dataset. In CVPR Workshop on The Future of Datasets in Vision, 2015.
[21] S. Davis and P. Mermelstein. Comparison parametric representations for monosyllabic word recognition in continuously spoken sentences. IEFE Transactions on Acoustics, Speech, and Signal Processing, 28(4):357-366, 1980.
[22] K. Deb, A. Pratap, S. Agarwal, and Meyarivan. fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6(2):182-197, 2002.
[23] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: A large-scale hicrarchical image database. In 2009 IEEE Conference on Computer Vision and Puttern Recognition, pages 248-255, 2009.
[24] Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. In International Conference on Learning Reprexentutions, 2020.
[25] Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition (CVPR), pages 1761-1770, 2019.
[26] Lukasz Dudziak, Thomas Chau, Mohamed Abdelfattah, Royson Lee, Hyeji Kim, and Nicholas Lane, Brp-nas: Prediction-based nas using geas. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages Curran Associates, Inc., 2020.
[27] Alireza Fallah, Aryan Mokhtari. and Asuman Ozdaglar. Personalized Federated Learning with Theoretical Guarantees: A Model-Agnoste -ageo--gnotiicc Meta-Lcarming Approach. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[28] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu. Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. European Conference on Computer Vision, pages 544-560. Springer, 2020.
[29] Pengehao Han, Shiqiang Wang, and Kin K Leung. Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approach. In IEEE International Conference on Distributed Computing Systems (ICDCS), 2020.
[30] C He, M Annavaram, and S Avestimehr. Fednas: Federated deep learning via neural architecture search. arXiv e-prints. 2020.
[31] Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cnns at the edge. Advances in Neural Information Processing Systems, 33:14068 14080, 2020.
[32] Minh Hoang and Carl Kingsford. Personalized neural architecture search for federated learning, 2022.
[33] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 173-17335)
nov 1997.
[34] Samuel Horvath, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis, Stylianos Venieris, and Nicholas Lane. Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout. arXiv preprint 10Xi 13451, 2021.
[35] Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The Non-lID Data Quagmire of Decentralized Machine Learning. In International Conference Machine Learning (ICML). 2020.
[36] Tzu-Ming Harry Hsu, Hang Qi. and Matthew Brown. Measuring the effects of non-identical data distribu- tion for federated visual classification. arXiv preprint urXiv:1909.06333 2019.
[37] Andrey Ignatov, Radu Timofte, Andrei Kulik, Scungsoo 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 (ICCV) Workshops, 2019.
[38] Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Loe, Kin K. Leung, and Leandros Tassiulas. Model pruning enables efficient federated learning edge devices. IEEE Transactions on Neural Networks and Learning Systems, pages 1-13, 2022.
[39] William M. Fisher John S. Garofolo, Lori F. Lamel et al. Timit acoustic-phonetic continuous speech corpus.
In Linguistic Data Consortium, Philadelphia, 1983.
11

---

Under review as a conference paper at ICLR 2023
[40] Peter Kairouz, I Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji. Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019.
[41] Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang. Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory. IEEE Internet Things Journal, (16::10000-07144 2019.
[42] 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- Parrty Machine Learning, 2016.
[43] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
[44] Fan Lai, Xiangfeng Zhu, Harsha V. Madhyastha, and Mosharaf Chowdhury. Oort: Efficient federated learning via guided participant selection. In 15th USENIX Symposium Operating Systems Design and Implementation (OSDI 21). pages 19-35. USENIX Association, July 2021.
[45] Hayeon Lee, Sewoong Lee, Song Chong, and Sung Ju Hwang. Help: Hardware- Hardware-adaptive efficient latency prediction for nas via meta-learning In Advances in Neural Information Processing Systems (NeurlPS), 2021.
[46] Ang Li, Jingwei Sun, Pengeheng Li, Yu Pu, Hai Li, and Yiran Chen. Hermes: an efficient federated learning framework for heterogeneous mobile clients. In Proceedings of the 27th Annual International Conference on Mobile Computing and Networking, MobiCom '21, pages 420-437 437, New York, NY. USA. October 2021. Association for Computing Machinery.
[47] Ang Li, Jingwei Sun, Binghui Wang. Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. Lotteryfl: Empower edge intelligence with personalized and communication-cffe efficcient federated learning. In 2021 IEEE/ACM Symposium on Edge Computing (SEC), pages 68-79, 2021.
[48] Changlin Li. Jiefeng Peng, Liuchun Yuan, Guangrun Wang. Xiaodan Liang. Liang Lin, and Xiaojun Chang. Blockwisely supervised neural architecture search with knowledge distillation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), 2020.
[49] Chenning Li, Xiao Zeng. Mi Zhang, and Zhichao Cao. Pyramidfl: A fine-grained client selection framework for efficient federated learning. In Proceedings of the 28th Annual International Conference on Mobile Computing and Networking, MobiCom '22. Association for Computing Machinery, 2022.
[50] Daliang Li and Junpu Wang. FedMD: Heterogenous Federated Learning via Model Distillation. In NeurlPS 2019 Workshop on Federated Learning for Data Privacy and Confidentiality, 2019.
[51] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6357-6368. PMLR, 2021.
[52] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated Learning: Challenges, Methods, and Future Directions. IEEE Signal Processing Magazine, 2020.
[53] Tian Li. Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint 1011v:1812.06127. 2018
[54] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2020.
[55] Or Litany, Haggai Maron, David Acuna. Jan Kautz, Gal Chechik, and Sanja Fidler. Federated learning with heterogeneous architectures using graph hypernetworks, 2022.
[56] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019.
[57] Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie-Yan Yan Liu. Neural architecture optimization. In Proceedings of the 32nd International Conference on Neural Information Prucessing Systems, NIPS' 18, page 7827-7838, Red Hook, NY, USA, 2018. Curran Associates Inc.
[58] Brendan McMahan, Eider Moore. Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-<ffcices learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
12

---

Under review as a conference paper at ICLR 2023
[59] Bert Moons, Parham Noorzad, Andrii Skliar, Giovanni Mariani, Dushyant Mehta, Chris Lott, and Tijmen Blankevoort. Distilling optimal neural networks: Rapid search in diverse spaces. arXiv:20/2.08859, 2020.
[60] Erum Mushtaq, Chaoyang He, Jie Ding, and Salman Avestimehr. SPIDER: Searching personalized neural architecture for federated learning. CoRR, December 2021.
[61] Xuefei Ning, Changcheng Tang, Wenshuo Li, Zixuan Zhou, Shuang Liang, Huazhong Yang, and Yu Wang. Evaluating efficient performance estimators of neural architectures. In Advances Neural Information Processing Systems (NeurlPS), 2021.
[62] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an asr corpus based on public domain audio books. In Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on, pages 5206-5210. IEEE, 2015.
[63] 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 Veto Martin Raison. Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Performance Deep I Learning Library. In Advances in Neural Information Processing Systems (NeurlPS), pages 8026-8037, 2019.
[64] Matthias Paulik, Matt Seigel, Henry Mason, Dominic Telaar, Joris Kluivers, Rogier van Dalen, Chi Wai Lau, Luke Carlson, Filip Granqvist, Chris Vandevelde, et al. Federated evaluation and tuning for on-device personalization: System design & applications. arXiv preprint
2021.
[65] Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning (ICML). pages 4095 4104, 2018.
[66] Xinchi Qiu, Javier Brrmandez-Marqueer Pedro PB Gusmao, Yan Gao, Titouan Parcollet, and Nicholas Don- ald Lane. ZeroFL: Efficient on on-device training for federated learning with local sparsity. In International Conference on Learning Representations, 2022.
[67] Xinchi Qiu, Titouan Parcollet, Javier Fernandez- Fernandez-Marques, Pedro Porto Buarque Gusmao, Daniel J Beutel, Taner Topal, Akhil Mathur, and Nicholas D Lane. A first look into the carbon footprint of federated learning. arXiv preprint vrxiv:2102.0763: 2021.
[68] Mirco Ravanelli, Philemon Brakel, Maurizio Omologo, and Yoshua Bengio. Light gated recurrent units for speech recognition. IEFE Transactions on Emerging Topics Computational Intelligence, 2(2):22-102,
apr 2018.
[69] Mirco Ravanelli, Titouan Parcollet, Peter Plantinga, Aku Rouhe, Samuele Cornell, Loren Lugosch, Cem Subakan, Nauman Dawalatabad, Abdelwahab Heba, Jianyuan Zhong, Ju-Chieh Chou, Sung-Lin Yeh, Szu-Wei Fu, Chien-Feng Liao, Elena Rastorgueva, François Grondin, William Aris, Hwidong Na, Yan Gao, Renato De Mori, and Yoshua Bengio. SpeechBrain: A arXiv:2106.04624
speech toolkit, 2021.
[70] Sashank J. Reddi. Zachary Charles, Manzil Zaheer. Zachary Garrett, Keith Rush, Jakub Konečný. Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
[71] Han Shi, Renjic Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sample-based and one-shot neural architecture search with bonas. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1808-1819. Curran Associates, Inc., 2020.
[72] Virginia Smith, Cha Chiang. Maziar Sanjabi, and Ameet Talwalkar. Federated Multi-Tat Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[73] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe V. Lc. MnasNet: matform-awar neural architecture search for mobile. In The IEEE Conference on Computer Vision and Pottern Recognition (CVPR), 2019.
[74] Nguyen Truong, Kai Sun, Siyao Wang, Florian Guitton, and YiKe Guo. Privacy preservation in federated learning: An insightful survey from the gdpr perspective. Computers & Security, page 102402, 2021.
[75] Roman Vygon and Nikolay Mikhaylovskiy. Learning efficient representations for keyword spotting with triplet loss. In Speech and Computer, pages 773-785. Sprinne International Publishing, 2021.
13

---

Under review as a conference paper at ICLR 2023
[76] Hongyi Wang. Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. ATOMO: Communication-EEfiicee Learning via Atomic Sparsification. Advances in Neural Information Processing Systems (NewrPPS), 2018.
[77] Pete Warden. Speech commands: A dataset arXiv:1844.0000 1804.0:209 2018.
speech recognition. arXiv preprint
[78] Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[79] C. Wu, D. Brooks, K. Chen, D. Chen, S. Choudhury, M. Dukhan, K. Hazelwood. E. Isaac, Jia, Jia, T. Leyvand, H. Lu, Y. Lu, L. Qiao, B. Reagen, J. Spisak, F. Sun, A. Tulloch, P. Vajda, X. Wang, Wang. B. Wasti, Y. Wu, R. Xian, S. Yoo, and P. Zhang. Machine Learning at Facebook: Understanding Inference at the Edge. In 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 331-344, 2019.
[80] Dezhong Yao, Wanning Pan, Yao Wan, Hai Jin, and Lichao Sun. Fedhm: Efficient federated learning for heterogeneous models via low-rank factorization. arXiv preprint arXiv:2111. 2021.
[81] Dixi Yao, Lingdong Wang. Jiayu Xu, Liyao Xiang, Shuo Shao, Yingqi Chen, and Yanjun Tong. Federated model search via reinforcement learning. In 202/ IEEE 41st International Conference Distributed Computing Systems (ICDCS), pages 830-840, July 2021.
[82] Kaicheng Yu, Christian Sciuto, Martin Jaggi, and Mathieu Salzmann Claudiu Musat. Evaluating the search phase of neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
[83] Arher Zela, Julien Siems, and Frank Hutter. N Benchmarking and dissecting one-shot neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
[84] Chunhui Zhang. Xiaoming Yuan, Qianyun Zhang, Guangxu Zhu, Lei Cheng, and Ning Zhang. Towards tailored models on private AloT devices: Federated direct neural architecture search. Corr, February 2022.
[85] Yuge Zhang, Zejun Lin, Junyang Jiang, Quanlu Zhang, Yujing Wang, Hui Xuc, Chen Zhang, and Yaming Yang. Deeper insights into weight sharing in neural architecture search, 2020.
[86] Yundong Zhang, Navren Suda, Liangzhen Lai, and Vikas Chandra. Hello edge: Keyword spotting on microcomtrollers, 2018.
[87] Dongzhan Zhou, Xinchi Zhou, Wenwei Zhang, Chen Change Loy, Shuai Yi, Xuesen Zhang, and Wanli Ouyang. Econas: Finding proxies for economical neural architecture search. In Proceedings of the IEÉE/CVF Conference Computer Vision and Puttern Recognition (CVPR), 2020.
14

---

Under review as a conference paper at ICLR 2023
Table of Contents
Introduction
15
B Broader Impact
16
Limitations & Future Work
16
D Detailed Experimental Setup
16
D.1 Implementation
16
D.2 Datasets
16
Search Spaces
Tiers: definition client assignment
Hyperparameters)
20
Cross-device Federated NAS evaluation
21
Baselines]
21
E
Comparison with alternative NAS algorithms
23
E.1
Comparison against random search
................................
23
Comparison against centralised NAS
................................
24
Impact of weight-sharing on different task training F
24
G
Convergence and FedorAS per-stage analysis
25
G.1 Impact of Stage III: Federated finetuning
25
2
Convergence and Impact of Supernet Sampling
25
H
Behaviour under alternative tier clustering
26
H.1
Supernet with wider FLOPs range
................................
26
H.2
Scalability more clusters
28
H3
Different allocation of clients to tiers
28
Pairness
28
Evaluation of the Search Phase
29
J.1
Sensitivity to size of validation set
29
J
Federated Search
29
J.3
Correlation with post fine tuning accuracy
31
A
INTRODUCTION
This Appendix extends the content of the main paper by providing support material to the study presented in Sec. 3 and, additional insights about FedorAs. Concretely, the Appendix is divided into three main blocks of extra content:
Impact and Limitations. We concisely present the broad impact and limitations of our work well future research directions in Sec. B C
Experimental Setup. Sec. provides details the libraries used to build FedorAs, the datasets considered for experiments as well as the hyperparameters used to obtain the results presented in Section 4 Crucially, we provide detailed description of the search spaces utilised for each dataset domain, how tiers are defined and, a concise description each baseline method included in this work.
15

---

Under review as a conference paper at ICLR 2023
Additional Experiments. Sec. E.1 through study different aspects of FedorAS such as: i) learning multiple tasks using the supernet in Sec. or ii) the convergence behaviour in Sec. G.2 iit) the fairness aspect of FedorAS; under scenarios altogether, such as: iv) an alternative procedure to assign clients to tiers in Section H.3 or iv) alternative search methods for Stage 2 in Sec.
Overall, the following content substantially extends what is already presented in the main text.
B BROADER IMPACT
Our system, FedorAS, performs federated and resource-aware NAS in the cross-device setting. Despite the benefits illustrated compared centralised NAS and cross-silo FL solutions, running Neural Architecture Search is still resource resource-demandiigg demanding process, in terms of compute, memory and network bandwidth. While FedorAS's target devices can be of significantly lower TDP (i.e. smartphones and IoT devices vs. server-grade GPUs) with consequences on the overall energy consumption of training (67] - they are resources not directly owned by the operator. As such, special care needs to be taken with respect to how many device resources leveraged any point in, as not hinder the usability of the device or invoke monetary costs to the user [41].
C LIMITATIONS & FUTURE WORK
Despite the challenges addressed by FedorAS, our prototype has certain limitations. First and foremost, we have opted to cluster devices (i.e. in tiers) based their FLOPS. While it is perfectly normal divide clusters based on other criteria (e-g. memory, latency, energy) or in multi-objectivve manner, we have kept it simple. Moreover, one opt for biased sampling of i) clients participating round, ii) the subspace they get communicated and iii) the paths sampled from that subspace, we opted for uniform sampling for all of the above for simplicity, uniform coverage of the search space and fairness in participation. We leave the exploration such strategies as future work. Last but not least, we have considered privacy- sewaacy-nhancingg techniques, such Differential Privacy [14] Secure Aggregation 11 6, as orthogonal to our scheme. Combining Federated NAS with such strategies can expose interesting trade-off's of exploration-erpllittaooo--iiiiii budgets that could be explored in the future.
D DETAILED EXPERIMENTAL SETUP
D.I IMPLEMENTATION
FedorAS implemented top of the Flower (v0.18) 99] framework and PyTorch (v1.11.0) 63
We run all our experiments on private cloud cluster simulated manner, across four iterations each and report averages and standard deviations.
D.2 DATASETS
We partition 1IFAR-10/100 following the Latent Dirichlet Allocation (LDA) partitioning [36], with each client receiving approximately equisized training sets. For CIFAR- 10, we consider
E {1000, 1.0, 0.1} configurations, while for CIFAR-100, we adopt 0.1 as in [70]. The remaining datasets come naturally partitioned.
CIFAR-10/100. The CIFAR-10 datasets contains 10k and 50k 32x32 RGB images in its test and training sets respectively comprising ten classes. The goal to classify these images correctly. Similarly, CIFAR-100 follows identical partitioning but, this time, across 100 classes (fine lebels) or 20 superclasses (coarse labels). Both CIFAR datasets have a uniform coverage across their classes.
Commands The Speech Commands datasets 777 is comprised of 105,829, 16KHz 1-second long audio clips spoken word (e.g. "yes", "up". "stop") and the task is to classify these in 12 or 35 classes setting. The datasets comes pre-partiiinned into 35 classes and in order to obtain the 12-classes version, the standard approach [8] [9) [75 is to keep 10 classes of interest (i.e. "yes", "no", "up". "down". "left", "right", "on". "off". "stop", "go"), place the remaining 25 under the "unknown"
16

---

Under review as a conference paper at ICLR 2023
class and, introduce class "silence" where spoken word appear is the audio clip. In this work we consider SpeechCommandsV2 the most recent version of this dataset. The dataset spans three disjoint set of speakers: 2112 form the training set. 256 for validation and, 250 for testing. In F Fedo the supernet training phase makes uses of the 2112 clients in the training partition only. The results are obtained by measuring the performance of the discovered models the data of the 250 clients comprising the test set. Data is not uniformly distributed and some clients have more data than others. This dataset is processed by first extracting MFCC [2T] features from each audio clip 86 8) Across our experiments we extract 40 MFCC features from a MelSpectrogram where each audio signal is first sub-sampled down 8KHz and then sampled using 40ms wide time windows strided 20ms appart. This results in I-second audio clip being transformed into x10051 input that can be passed to a CNN.
58 from The Complete Works of William Shakespeare and partitioned in such a way data that from each role in the play is assigned to a client. This results in a total of 1,129 partitions where the average number of samples per device is 3.7K and the standard deviation 6.2K samples. This makes Shakespeare a relatively imbalanced dataset. The task is to correctly predict the next character in dialog given the previously seen characters in the sentence. The vocabulary considered has 86 English characters as well as four special tokens: start and end of sentence, padding and out-of-vocabulat tokens.
Shakespeare. This dataset is built 17
D.3 SEARCH SPACES
We assume that the largest model in the search space is the maximal size that any of the clients can handle. The minimum cost is set to the fixed cost of the network (i.e. cost of non-searchable components). Given this range, and number of clusters C, we define the first and last clusters at prctt, prct, percentiles of a randomly sampled set of models from the search space and linearly scale the C 2 clusters in- bebeeeeenn All supernet search spaces are depicted in Fig. 5 and described below.
d-128
2=2
c-damme
c-15
0spravr1.5
2=2
esprov"1.6
a=2
podtee
Openkm
Coneti
inpeadedd Timiia
repeatedd Smaes
repeated 2 Sraw
Figure 5: Summary of models used in our experiments: left) CIFAR-10 10 and CIFAR- 100, middle) Speech Commands, right) Shakespeare. Blocks highlighted in blue are fixed, orange blocks represent searchable layers. e- output channels, stride, d output feature dimension, DSConv depthwise separable convolution. Whenever layer has more than one input they are added, All convolutions are followed by BN and ReLU. For convolution and pooling operations, numbers in parentheses represent window sizes.
CIFAR-10 and CTFAR-100. We use ResNet-like search space similar to the one used in, for example, Cai et al. (16.. Specifically, our model is a feedforward model with fixed (i.e. non- searchable) stem layer followed by a sequence of 3 searchable blocks, each followed by a fixed reduction block. A standard block consists of 4 searchable layers organized again in simple feedforward manner. Operations within a standard block preserve shape of their inputs, but are allowed to change dimensions of intermediate results. On the other hand, the goal of reduction blocks is to reduce spatial resolution (2x in each dimension) and increase number of channels (1.5x). Reduction blocks
fixed throughout and consists of depthwise separable convolution 3 3, with the first part performing spatial reduction and the second increasing the number of channels, and standard 2 2 convolution applied a residual link. The sequence of blocks finished with a global average pooling per-channel and classification layer outputting either 10 or 20/100 logits, which the only difference between the two models. Each convolution operation followed by a batch normalization (BN) and ReLU.
In our experiments we considered the following candidate operations:
standard convolution x with BN and ReLUU
17

---

Under review as a conference paper at ICLR 2023
depthwise separable convolution 3 x 3 with expansion ratio (controlling the number of intermediate channels) set to 10),, with each expansion ratio being an independent choice in our search space
MobileNet-like block consisting of a convolution with kernel size k and expansion ratio e, followed by a Squeeze-ane and-Excitation layer, followed by a 1 x convolution reverting the channels expansion, considered {(k L, = 2), (Is 3, 0.5), (A 3, e 1), (k: = 3, e = 2
identity operation
The stem layer was set 3 3 convolution outputting 64 channels.
Speech Commands. The model follows the one used for the CIFAR datasets but is made more lightweight to roughly match what can be found in the literature by reducing stem channels to 16 and including only 1 (resp. 2) searchable operations in the first (resp. last) two blocks. Additionally, reduction block only includes a single
convolution, that changes the number of channels, followed by a 3 x 3 average pooling that reduces spatial dimensions. We also include additional candidate operations:
standard convolution
depthwise separable convolution with kernel size 1 and expansion ratio 2
All other operations from the CIFAR model are also included.
Specifically, the model recurrent network that begins with fixed embedding layer outputting 8-dimensional feature vector per each input character. This is then followed by a searchable operation #1 that increases dimensionality from 8 to 128; in parallel, we have searchable skip connection #1 operation whose output added to the output of the operation #1. Later there another searchable operation #2 with its own skip connection #2, both keeping the hidden dimension at 128. Again, their outputs are added and passed to the final classification layer.
Shakespeare. We base our design on the model used by FjORD.
Candidate operations for each of the four searchable layers mainly the same, with minor adjust- ments made to make sure valid model is always constructed. These include:
an LSTM layer 33
GRU layer 18]
LiGRU layer with tanh activation 668]
QuasiRNN layer B
simple Linear layer (no recurrent connection) followed by ssigmoid activation,
1D convolution with kernel 5 spanning time dimension (looking at the current character and 4 previous ones), followed by a s sigmoid activation (no normalisation).
identity operation (only included in later operation, after feature dimension has been in- creased to 128),
zero operation, outputting zeros of the correct shape (only included in skip connection layers).
For LiGRU and QuasiRNN used implementations provided by the Speechbrain project (69, after minor modifications. For others, we used standard operations from Py Torch. All operations were used unidirectional. We did not any normalisation throughout the model.
D.4
TIERS: DEFINITION AND CLIENT ASSIGNMENT
With FedorAS the discovery and training of architectures happens in tier-aware fashion federated process. In this work we considered splitting each search space along the FLOPs dimensions (but other splits possible, e.g. energy, meak-memory usage, illustrates the span terms of model parameters and FLOPs of each search space presented D.3 and the split along the FLOPss dimensions for each of them. These search spaces vary considerably in
combination of these). Fig. 6
18

---

Under review as a conference paper at ICLR 2023
Table 6: This table summarises how each search space is split into tiers. Parameters pr. and ps used to conveniently split the FLOPs axis for each dataset and present challenging scenarios for FedorAs. The last column refers to the percentage of the total clients that are assigned to each tier.
Dataset
1pt. pM)
Tier
FLOPS range
Models
Portion( (%)
Clients (%)
T1
10, 120.9]]
2
12.92%
25%
T2
(120,9M. 223.2M]
1089.4-10
58,80%
25%
CIFAR-IO
[0.0, 0.95]
T3
(223,2M. 325.4M]
477.2-10'2
25.75%
25%
T4
(325,4M. 716.0M)
46.9-10²2
2.53%
25%
TI
[0. 111.5M]
168.4-10'2
9.09%
25%
CIFAR-100
[0.0, 0.9]
T2
(111.5M. 204.3M]
975,4-10'2
52.64%
25%
T3
(204.3M, 297.
609,5-10'2
32.89%
25%
T4
(297.1M, 716.0M]
99.7-10"2
5.38%
25%
[0. 111.5M]
168.4-10
9,09%
CIFAR-100 task setting
[0.0.
(111.5M, 204.3M]
975.4-10'2
$2.64%
(204.3M. 297.IM]
609.5-10'2
32.89%
12.5%
Appendis
T4
(297.1M, 716.0M]
99.7-10'2
5.38%
12.5%
T1
[0. 5.0M]
827.5-10
46.71%
80%
10.3, 0.925]
T2
(5.0M. 7.5M]
617.4-10*
34.85%
1.25%
(7.5M, 10.1M]
260.2-10*
14.69%
1.25%
(10.IM, 20.0M]
66.4-10
3.75%
17.5%
T1
[0. 7.8M]
316
13.48%
20%
(7.8M, 12.8M]
577
24.54%
20%
Shakespeare
[0.1. 0.77]
T3
(12.8M. 17.8M]
787
33,48%
20%
T4
(17.8M. 22.8M]
473
20.14%
20%
(22.8M, 33.8M]
196
8.37%
2013
terms of size and span, which motivated us to use different number of tiers client-to to-tier assignment strategies. 6 shows the the FLOPs ranges considered for each tier, the number models in those sub-spaces exposed to FedorAS as well as the ratio of models in the entire search space that fall onto each tier.
Identifying FLOPs ranges for each tier. Regardless of the dataset, follow common approach to divide the FLOPs dimension that each dataset spans. The main aim is to finely control how many models fall onto the smallest/largest tier, given that these are considerably sparse regions of the entire search space. If we were to evenly split the FLOPs dimension, almost no architecture would fall onto the largest tier. To simplify the process of defining where each tier's boundaries lie, we follow these steps which require two byperparameters: (1) we construct long array of FLOPs from models sampled from the search space and this array is then sorted from lowest to highest; then, (2) we normalise this array of FLOPs and compute the cumulative sum of such normalised array; finally, (3) we identify the lower limit of the highest tier as maximum FLOPs value found in the first pN, p E [0, 1J. elements of the array where N is the number of samples taken (we found 100K to work well). Essentially, we find the FLOPs for which the approximated PDF over the FLOPS of a given search space doesn't 't surpass p. Once that FLOPs value is identified, the FLOPs range is evenly split for the tiers below and the higher limit for the largest tier becomes the maximum FLOPs a model in the search space (a) and (b). For SpeechCommands and Shakespeare we introduce a similar approach to give a wider range to the smallest tier. We refer to pr. and ри the PDF ratios identify the boundaries splitting Tierl &2 and Tier3&4 respectively. The concrete values for each dataset as well as the FLOPs values for each tier boundary are shown in Tab 6
have. This is the approach for CIFAR-10 and CIFAR-100
illustrated in
Clients to tiers assignment. For CIFAR-10/100 clients are uniformly assigned to a cluster of devices or tier. For these datasets we consider four tiers. so each ends up containing 25% the clients resulting in 25 clients for CIFAR-10 and 125 clients for CIFAR- 100. Similarly, for Shakespeare clients are also uniformly assigned tier, resulting 143 clients per tier. For SpeechCommands, we designed more challenging setup and divide the clients into tiers as follows: 80% of clients are assigned to be tier-l devices, 17.5% are Tier-4 devices and the rest evenly split into Tier-2 and Tier-3. This distribution better represents the the types of systems in the wild that perform keyword-spottie where the majority of the commercially deployed systems run these applications on low end CPUs or microcontrollers due their always-on nature. Across datasets, the client-to dlient-to-tier assignments was done irrespective of the amount of data these contained or distribution over the labels. An alternative client tier allocation is provided in Sec. H.3
(86),
19

---

Under review as a conference paper at ICLR 2023
Peramo (M)
Tier
Tier
Tiar
Tier 3
Ter 2
Tier
1
Tier
Twr
100
200
300
400
500
6:00
700
100
200
300
400
5.00
600
700
FLOPs
FLOPs
(a) CIFAR-10
(b) CIFAR-100
1.0
0.35
0.30
Param: 04
Panams (N)
0.25
0.20
0.4
0.15
0.10
0.05
Tier
0.00
5.0
10.0
20
FLOPs (M)
(c) SpeechCommands
(d) Shakespeare
Figure 6: For each search space, we randomly sample 500 architectures and color code them based the they belong to. Vertical dashed lines represent the boundaries between device tiers. For Shakespeare, majority of the candidate operators in the searchspace include just linear layers or no-op layers, as a results the number of FLOPs grows almost linearly with the model of parameters.
D.5 HYPERPARAMETERS
Here present the hyperparameters used across all datasets and tasks to generate the results presented Sec. In Tab. 7 we show the hyperparamters utilised for the first stage in the FedorAS framework: federated training of the supernet. Noticeably
require more local epochs in this stage as training each client effectively ppre-)trains multiple models and we need sufficiently many forward passes order sample large enough number of paths on each client. In the context of FedorAS, the combination of batch size and number of local epochs define the exploration vs. exploitation trade-off the communicated subspace. It is natural that if enough paths are explored or if paths overfit the local data, the overall NAS results and thus model ranking would be severely affected. As such, we increase the number of local epochs together with batch size, ensure that the total number of forward passes remains constant for the same number of training examples After this stage, the best model for each tier is extracted from the supernet and then, they get finetuned in per- tier aware manner (i.c. clients in tier T and above finetune model that belong to tier T)). The hyperparameters of these two consecutive stages are shown Tab,
client.
Regarding the rand-init results (i.e. models discovered by FedorAs but trained from scratch discarding the weights given by the supernet) we present the hyperparameters in Tab. 9 These hyperparameters the ones used to generate the results in Tab. 5 and [ as well Fig. In Sec. 4.2 we present CIFAR- 100 result that largely outperforms existing federated baseline of 770
This achieved by model discovered FedorAs but trained in the rand-init setting following
20

---

Under review as a conference paper at ICLR 2023
Table 7: Hyperparameters used for the federated supernet training stage in FedorAS, described in Sec. 3.1
The learning rate is kept fixed during this stage. all datasets, the aggregation strategy followed the proposed -ongramm-infomed methodology OPA, first presented Sec.
# Federated Rounds
# Clients
Local Epochs
Local Optimizer
Batch Size
Gradient Clipping
Datasct
Momentum
per round
CIFAR-10
500
10
50
SGD
128
0.1
0.9
N
CIFAR-100
500/750
10
SGD
0.9
SpeechCommands
750
21
SGD
64
0.9
N
Shakespeare
500
16
SGD
1.0
0.0
Y
Table 8: Hyperparameters used by FedorAS to scarch for the best model in the supernet and finetune them in a tier-a aware fashion as described Sec. S.c.33.2aaa an2 and Sec. respecctcy. Scarching iterations shown are allocated per-tier (i.c. CIFAR-10 has 4 tiers so a total of 4K valid models would be considered during the search). Cosine LR scheduling gradually reduces the initial LR (shown in the table) by order of magnitude over the span of the the finetuning process. For Shakespeare, step LR decay worked best. This is applied at rounds 50 and 75, each decreasing
LR by a factor of 10x. SpeechCommands assigns different search iterations based on ratio of clients assigned to each tier. FedorAS scales the amount of search for valid models within the tier accordingly. For Shakespeare, the sub-searchspaces that yield Tier-1 and Tier-5 models are smaller than for the other tiers, therefore consider fewer search iterations.
Tiers
Search Iterations
Finetune Rounds
# Clients ronnd
Local Epochs
Batch Size
LR Scheduling
Other
Dataset
Hyperparams
CIFAR-10
4
1000
100
32
0.01
cosine
momentum=0.9
CIFAR-100
4
1000
100
1
0.01
cosine
momentum=0099
SpeechCommands
500/2000
100
I
0.01
cosine
momentum=009
Shakespeare
5 100/150
100
16
1
4
1.0
step
g g.lippiig=55
the setup in 770: 10 clients per round for 4k rounds using batch 20, starting learning rate of 0.1 decaying to 0.01 following a cosine scheduling.
D.6 CROSS-DEVICE FEDERATED NAS EVALUATION
In Tab. of Sec. 4.2 compared FedorAS against FedNAS in the cross-sile setting with 100 clients and 10 clients randomly sampled on each round. Both methods follow substantially different approach far as NAS concern and, result, FedNAS has significantly higher memory peak than FedorAS for the same batch size. For example. for batch size of 64 images. FedorAS sees memory peak of 998MB whereas FedNAS requires 7674MB. Similarly, both methods translate in different compute footprints for each client. For example, FedNAS requires on average 716 GFLOPs per client (assuming each client), while clients in FedorAS need 280 GFLOPs for the same amount of local epochs and data in the client. Due to these differences, we aimed at normalising these aspects to make the comparison fair. These results are shown Tab. 10 which extends the content of Tab. 2
D.7 BASELINES
In this section faithfully describe what each baseline represents in the experiments of the main paper and the appendix to clarify with what we are comparing in each section.
Tier-unaware (Fig 3):
This baseline represents model architectures that have been trained end-to- end a federated manner without any awareness of client eligibility. We are using FedAvg with hyperparameters similar to those presented in Tab.
Tier-aware (Fig 3):
This baseline adds client eligibility awareness to the previous baseline. This means that models of certain footprint can be trained only clients of the eligible cluster and above.
FJORD 34 (Fig Tab. 4b: FjORD is a baseline that is tackling system heterogeneity by means of Ordered Dropout. It assumes uniform dropout rate across layers, essentially keeping the control variable dimenniinii and thus offering fewer degrees architectural freedom. Nevertheless, it enables the dynamic extraction of candidate submodels without the need to retrain finetune.
21

---

Under review as a conference paper at ICLR 2023
Table 9: The architectures discovered by FedozAS also be trained from scratch. This table contains the hyperparameters utilised to generate the rand-inil results shown in Tab, and 13 Training of these baselines also performed in a tier-aware fashion. Cosine LR scheduling gradually reduces the initial LR (shown in the table) by an order of magnitude over the span of the the finetuning process. For Shakespeare, step LR decay worked best. This is applied rounds 250 and 375, each decreasing the LR by a factor of 10x.
# Federated Rounds
Clients per round
Local Epochs
Batch Size
LR Scheduling
Other Hyperparams
Dataset
LR
CIFAR-10
500
10
0.1
cosine
momentum=0.99
CIFAR-100
500
10
32
0.1
cosine
momentum=0.9
SpeechCommands
500
21
32
0.1
cosine
momentum=0.9
Shakespeare
500
16
1.0
step
g g.clipping=5
Table 10: Cross-device federated NAS on CIFAR-I0. We compare FedorAS and FedNAS while normalising
aspects that are critical to on-device training: namely the number of FLOPs clients do in a given round and the memory peak seen over the course such training. The later directly impacts model could trained on. normalise memory peak by lowering the batch size that FedNAS uses (from 32 to 16) and reduce the number of local epochs in FedorAS down to 20 to match the FLOPs of typical FedNAS client. For further context, we maintain the results of FedorAS with 50 local epochs the setting used throughout the majority of the experiments in this paper.
which devices particular
Dataset
Method FedNAS
Local Epochs
Batch
Mem. Peak (GB)
GFLOPs/client
Perf. (%)
32
3837
1431
90.02
CIFARIO
FedNAS
16
1919
1431
85.45
FedorAS
128
1996
1402
87.21
FedorAS
50
128
1996
3504
86.4620.32
FedNAS
3837
1431
65.28
FedNAS
16
1919
1431
$4.84
CIFARIO.=0..
FedorAS
128
1996
1402
79.41
FedorAS
50
128
1996
3504
81.53=0.22
This particular variant is assuming the experimental setup of the original paper which shards the CIFAR-10 dataset per client without LDA. The Shakespeare setup remains the same as ours.
FjORD-LDA 34
the same For this baseline, we implemented FjORD and number of clusters as FedorAs, with LDA for CIFAR-10.
(Fig 3 Tab. 4h:
of the first papers attempting perform NAS in federated setting. Its search is DARTS-basee and it was primarily aimed for the cross-silo setting, Cross-device FL NAS of limited scale (20 total clients with 4 clients sample per round) was also showcased in the original paper. We adjusted the code of FedNAS to perform cross-silo and cross- device FL NAS with setups of varying training footprints by adjusting the amount of local epochs and batch size. We have kept the original search space.
FedNAS 30 (Tab. 2 :) FedNAS
SPIDER [60] (Tab. 3): SPIDER another paper performing personalised Federated NAS in the cross-silo setting. As there is no publicly available codebasse, we assume their setting with FedorAs and compare on CIFAR-10.
ZeroFL 66 (Tab. For this baseline, we borrow the results of respective paper for
CIFAR-10,=411 (1.10000 which assumes same setup as ours. We present the results for sparsity level of 90% and annotate its footprint the original model FLOPS and the number of non-zero parameters.
Oort [44] (Tab, The Oort framework proposes participation sampling criterion by which clients are sampled based on their utility (i.c. how much their data can contribute to the global model) while also taking the device capabilities into consideration. Over the course of FL training, the sampling of clients with high data and system utility is prioritised to reduce the time needed to convergence. For SpeechCommands (see Tab. 4 Oort made use of ResNet-34 model.
Fy (Tb. D. At a high-level, PyramidFL proposes a framework similar to that in Oort. The core difference between these two methods is that PyramidFI. leverages more fine-grained
22

---

Under review as a conference paper at ICLR 2023
AIIO a=1000]
CIFARIO (LDA
CIFAR1O
(LDA
Tee
08-
88-
06
86
Tesk Sccurocy (%)
84
AM
65
60
Test
78
78
55
75
76
100
200
330
400
300
000
700
100
230
300
400
500
800
700
100
200
300
400
500
600
700
PLCKS (M)
FLOPS (M)
FLOPS (M)
CIFAR 100
non-ilD (LDA 2-0.11
Shakespeare
SperchCammands (12 closses)
Twr2 Berr) Fard
Tert
Tea
Fer Ser
TerA
65
12
Test accuracy (B6
T10 peeppeenn pepittsiiy
80
75
12
20
18
330 FLOPS
FLOPS
Figure 7: For each dataset, we randomly sample their search space and train these models end-to-end. We repeat this process (with new samples) three times, and overlap the scatter plots of different runs (i.c. red, green, blue). Then, for each tier we average the best performing models across each of three runs and plot the result as a dashed horizontal line with grey area reprosenting standard deviation. The compute budget allocated to generate the data for each plot is equivalent to the cost of running F FedorAS, which also yields one model per tier.
statistics when assessing the contribution potential (i.e. utility) of the selected clients. It also uses ResNet-34 for SpeachCommands.
rand-init (Tab. 13 17): This baseline refers to the concept of rumning the search, coming up with an architecture and subsequently re-initialising the weights and running a conventional federated training setup. It shows vanilla scaling that would be obtained if simply trained identified models in a standard way, using random initialization and full FI. training using standard practices. Model architectures are kept the same between FedorAS and "rand-init" experiments. Models belonging to higher tiers, as a whole, are never trained on data belonging to devices from lower tiers.
E COMPARISON WITH ALTERNATIVE NAS ALGORTHTS
Note: this section considers replacing FedorAS as a whole with a different approach to searching for the best performing model in the same search space etc. On the other hand, for additional details about the searching stage of FedorAs (Stage 2) please see Section
E COMPARISON AGAINST RANDOM SEARCH
In the main paper we compare our FedorAS to the state-of-the- methods from the literature (Sec. 4.2 and also investigate the impact of initializing models with weights from a supernet (Sec. Here present one more important baseline for any NAS algorithm comparison to random search. Specifically, while we have already shown that models found by FedorAS in most cases benefit from supernet training. this does constitute a conclusive argument justifying the necessity of the entire process in broader context. Perhaps there exist models that do not need to be initialized from a supernet but, since the focus of our work is on supernet training, we missed them due to biased conditioning?
In order to check this hypothesis we run a simple random search algorithm, to get an estimate the expected best case performance of models from search spaces when trained following standard FL procedure. This simple baseline was allowed to train random models until the total training cost exceeded the cost of rumning FedorAS this turned out to be equivalent to roughly 40 fully- trained models. After we run out of the training budget, we simply get the best model for each tier as our solution NAS. We repeated the entire process times for each search space and report average and
23

---

Under review as a conference paper at ICLR 2023
Table 11: Comparison of performance of models found with FedorAS and with simple random search.
Dataset
FedorAS
Random search
T1
T2
T1
T4
75
T4
CIFAR-10 1000
19.40)
89.60.14115
89.64.
89.24_.030
86.03..0 11
19.99 m
85.18
70:841077
CIFAR-10 = 1.00
85.99
1813
86.30
86.34 8.19
85.58
83.68.1031
84 14.501.mm
84.30.1034
79:65.14 IS
CIFAR- 10 0.3
81.01:144
$1.53:0229
80.64:
80.85 10.38
66.75
70.85:1:5
69.00:111
66.88:222
CIFAR 100
45.25:0113
45.84:918
45,42:4:3
45,07:0331
34.41:990
37.642044
36.98
35.4540000
SpeechConmands
60.19=175
80.17=1.0
61.00=1.38
80.56:0.40
82.84:1146
81.17=9266
50.61=941
Shikesspaar
3,4
3,3
3.38
3.40
3.4
3.86
3.54
3.45
3,801030
3.60
Table 12: Comparison of FedorA8 centralised NAS setting.
Method
Dataset
Tier
Tier
Tier 3
Tier 4
Centralised NAS
CIFAR-
CIFAR-IQqmaaiad
93,77aa00
94.14
94,04
94.33
FedorAS
CIFAR- CIFAR-100-1100
89.40gar9 (-4,77) 89.602011 (-4.54) 89 89.6440m (4.40) 89: 29.24 (-5.09)
Table 13: Models discovered by FedorAS benefit from weight sharing across tiers compared to models using the same architecture but trained an-to--end on clients that support them. Models derived from a F FedorAS supemeet outperform their baselines by large margins in most cases. First part: accuracy, second part: perplexity.
Dataset
Setting
Partitioning
Mode
Classes
Tier
Tier
CIFAR-100
500
Multi-task
non-IIDa-o.1
FedorAS
nand-inir
[20,20, 100, 100]
57,93+931
41 64.444 26
42.45.05
57,86+a7
27. 11
38.63:2744
37.68
21,28
26
Commands
Speech
2112
Transfer
given
FedorAs rand inir
35
64.99
67.0612122
65.03
67.65
66.55
66.84.uar
68.49.1.47
1 Trained only on clients belonging to Tier 3 and
standard deviation compared to the average performance of models found by FedorAs in Tab. Additionally, we also plot detailed performance of each model trained during this process in Fig. for the sake of completeness. Noticeably, FedorAS achieves significantly better results almost all cases, with SpeechCommands being the only exception. We suspect this is due to problem with fine-tuning rather than architectures themselves specifically, we witness accuracy of the discovered models can vary significantly we repeat the fine-tuning process (this is also visible in the case of full training, although the extend is smaller). Consequently, although on average FedorAS performs slightly worse, in many cases the best results surpass that of random search because of that suspect that fine-tuning for longer would improve FedorAs's performance. We leave this for future work, considering that single shortcoming like that does not seem significant in the light of the rest of our results.
E.2 COMPARISON AGAINST CENTRALISED NAS
To study the impact that FL. has in supernet-based NAS, we train the CIFAR-10 supernet in a similar centralised setting to FedorAS's. Similarly to Stage I in FedorAS, we do 500 training epochs following the SPOS paradigm but, because it is centralised, we do not impose any FLOPs budgets when sampling paths along the supernet. After training, we use NSGA-II to search for the best performing architecture/path and select the best among 1000 valid models for each tier. Finally, these models are trained from scratch for 200 epochs (again in centralised setting, i.e., having access to all training data). The resulting test accuracies per tier are shown in the Tab. [2 and compared against the federated IID setting of CIFAR-10 (the simplest FL setup).
F IMPACT OF WEIGHT-SHARING ON DIFFERENT TASK TRAINING
In this section, we expand on the analysis of Sec. 4.3 Specifically for CIFAR- 100 and SpeechCom- mands, we also create a second scenario, where not all clients train in the same domain of labels. For CIFAR- 100, there are 20 superclasses that are coarse -griinedr categories of the 100 standard labels. In contrast, for SpeechCommands. there are 12 and 35-class label sets, with the latter annotating the "other" class more specifically. In both cases, we assume a non-uniform distribution of clients to clusters, assuming that most data (75-80%) reside on lower-tier devices, whereas the two higher
24

---

Under review as a conference paper at ICLR 2023
Table 14: The effect of Stage-Ill III of FedorAS: tier-aware federated finetuning of models extracted from the supernt.. This table reports the increase validation accuracy (measured in percentage points) for classification tasks of the model after finetuning and the decrease in perplexity for next word prediction (i.e. Shakespeare).
Datasct
Tier 1
Tier 2
Tier 3
Tier 4
Tier 5
CIFAR-10.
1.23
0.80
1.18:0002
1.11
N/A
CIFAR-10.=Lo
3.99+0.22 22
1.86
3.55+0.68
2.63+00.4
N/A
CIFAR-10a=0.1
8.27+1.34
7.44
1.78+1.39
7.76+2.57
N/A
CIFAR-100a
8.56:0.00 04
8.69:0.33
7.20+0.34
7.74
N/A
Speech Commands
4.66 06
5,68.10.55
7.98:1111
6.71
N/A
Shakespeare
0.273:0.025
0.220:0.025
0.227 046
0.210=0.020
0. 0.19020.00
tier-devices (holding 20-25% of data) can train on the fine fine-grained label set. Our aim is to test whether few data allocation on the high tier devices can benefit from the knowledge and feature extraction learned from the paase-grained label set. We adopt two different setups. For CIFAR-I00, we train both tasks simultaneously, having essentially two distinct linear layers across tiers (1,2) and (3,4). We call this setup multi-task. On the other hand, for SpeechCommands, we train all clients on the same coarse domain and subsequently transfer learn fine-grained 35 classes linear layer for the client of tiers (3,4). We fine-tune the linear layer keeping the rest of the network frozen for 25 epochs and then allow for finetuning of the whole network for another 100. We present the results in Tab. 13
In both cases FedorAS learns better models and transfer knowledge from the low-tiers to high-tiers and vereaversa through weight sharing of the supernet. Indicatively, for CIFAR-100 we are able to achieve +14.91 pp (percentage points) of accuracy compared to training the same architectures end-to-end eligible devices. Similarly, achieve +1.6 pp higher accuracy for SpeechCommands.
G CONVERGENCE AND FedorAS PER-STAGE ANALYSIS
G.1 IMPACT OF STAGE III: FEDERATED FINETUNING
After Stage I FedorAS, models extracted from the supernet can directly be used for the target task (e.g. image classification). However, performance this target task can be improved further by finetuning these models. This is the purpose of Stage III. In Table 14 we show the increase in model quality (measured on the global validation set) before and after Stage III.
G.2 CONVERGENCE AND IMPACT OF SUPERNET SAMPLING
The proposed OPA aggregation scheme converges faster than alternative aggregation method that does FedAvg of the updated supernets. We show this in Fig. g When supernets from each client participating in the round get aggregated with OPA, the resulting supernet is consistently better in terms of validation accuracy than when aggregation is done with FedAvg. This difference becomes more evident as B is reduced, i.c., as smaller portions of the supernet are sent the clients. In Fig. [ (d) we asses the feasibility of reducing the number of rounds and end the federated supernet training stage when validation accuracy reaches approximately 70%. Those points correspond to 250 rounds and 150 rounds for the setting when 50% and 25% of the supernet is sent to the clients, respectively. The results that these settings yield show a significant loss (compared to their respective settings but over 500 rounds) and we therefore also run the same settings but when allowing for 50 additional runs. We observe a significant jump in per-tier model performance. We leave as future work investigating altermative metrics to more accurately (but without incurring into heavy computational costs) measure the quality of the supernet at any given training iteration and leverage this to better inform early stopping mechanism further reduce communication costs.
25

---

Under review as a conference paper at ICLR 2023
Volldation Accrasy (S))
100
Supa net Bain
Par-err bearch
(96
Supenee frais
Porder Search
Pathog
validatiinn Accuratty
(S0
Test Accuracy
80
47
40
40
85
20
86
84
T2
T4
T2 Device Tier
Step (thousandds)
Diviice Tier
Step [thousandss)
(a) Sending whole of the supemet (B sonm
22.3M (b) Sending 50% of the supernet (B aBaa
11.15M)
100
Supal and Battt
Pan-bar Swarchh
100
Volication Accarocc 185)
0%
valicatiio Accuracy (16)
80
OM 125% g133
Accurscy
DRA (25% g202/221
07
100
Train
Partar Search
86
80
60
20
40
84
Step (thousends)
(thousands)
(c) Sending 25% of the supernet (Beccm
5.58M)
(d) Impact of fewer rounds
Figure 8: Results using OPA compared to FedAvg in FedorAS for CIFAR-IO non-IID (a = 1.0) with fixed hyperparameters. Each sub-plot contains two plots: first a scatter plot that visualises the federated supernet training (Sec. [3.]] in the first 5k steps and the per-tier search stage (Sec. B.2 the remaining steps; and. bar plot that shows the average test accuracies of each tier after federated finetuning (Sec. (S.c.3.3). For (a)-(c), the training setups are identical with the exception of using either OPA or FedAvg. Both settings perform 500 rounds of federated supernet training using 10 clients per round (i.c. 5k steps). Every 10 rounds, the supernet is evaluated on the global validation set by randomly sampling paths and dot is added to the plot. In the context of reduced communication budget, OPA largely outperforms FedAvg, requiring fewer federated rounds to reach the same validation accuracy. This difference is more noticeable when sending 50% of the supernet (roughly corresponding to the size of ResNet18 8 model). In (d) we measure the quality of the models found when the supernet training phase ends once 70% validation accuracy is reached the highest reached by FedAvg in (a)-(c) and show competitive performance of models derived from OPA aPg-ggggeet supernets. By extending the training phase by 50 rounds, we observe large improvements in the quality of the final models.
In Figure we show the behaviour of FedorAS across all stages for the datasets considered in this work. These analysis uses the intermediate results generated for one of the seeds in Table 5 using the default hyperparameters as per Tables [ and with all datasets using as communication budget, Bra. ,half of their respective supernet sizes.
H BEHAVIOUR UNDER ALTERNATIVE TIER CLUSTERING H.1 SUPERNET WITH WIDER FLOPS RANGE
We design a larger supernet for CIFAR-10 by stacking more blocks (4 blocks with 4 searchable layers followed by two blocks of 8 searchable layers) in the supernet while not requiring the reduction block between supernet blocks to always downsample the input (see D.3. This is done to prevent the width and height of activations to decrease too rapidly (i.e. after each block). The MFLOPs limits for each tier are: [101.00 101.06,77 714.01, 1326.95, 4450.72), with the smallest model in Tier 1 (i.e. 53.77 MFLOPs) representing the fixed costs of the supernet (FLOPs involving -ea-chacch layers). With this setup, Tier 4 models can have a 82x larger compute footprint than Tier 1 models. Results are depicted in Table 15 These were obtained using the exact same hyperparemeter configuration (see Table 7 and Table 8 for hyperparameters of FedorAS Stage I and Stage- & III respectively) as the CIFAR-10 10 experiments shown in Table with the exception of now having a larger supernet. Still, the candidate operators in the supernet remain the same and so is the proportion of clients assigned to each tier. For these experiments we followed the same procedure when establishing the communication budget and therefore we set it to be half of the supernet size. We report the results of the finetuning stage of FedorAS and show improvement over those obtained with the smaller (original) supernet. We also report the resulting performance when networks are randomly initialised (i.e. rand-init setup).
26

---

Under review as a conference paper at ICLR 2023
Gleb. Vel. Accuracy (%)
Supemet
88
Tor
Ther Teer
0
40
00
80
100
(thousands)
Finetuning Stop
Glob. Vol. Accuracy (%)
Supernet Train
Pentier Search
Glob. Val. Accuracy (96) Glab. Val. Accurccy
22
-8
Step [thossands]
Finetuning Step
Glob. val. Accuracy (%)
Supernet Train
Pertier Search
82
40
10
15
20
25
20
40
60
80
1.00
(thousands)
Finetuning
Glbb. Val. Perplextty
8
Supernet Train
Per-tier Search
Clob. Perplexity
9.7
8
Step (thousands)
finetuning Step
Figure 9: Convergence analysis for each of the datasets considered in this work (from top top bottom: CIFAR-IP 10, CIFAR-100. Speech Commands and, Shakespear). For each dataset, the three stages in FedorAS shown in the first subplot the row (Stages I&II) and the subplot on the right shows the final per-tier fientuning (Stage III), Per-tier search and finetuning colour-coded.
27

---

Under review as a conference paper at ICLR 2023
Table 15: Performance of FedorAS when increasing the FLOPs range of models in the supernet. Models in Tier are up to 82x larger than dose in Tier
Dataset
Tier
Tier 2
Tier 3
Tier
CIFAR-10a-1.0
89.5410.12
p3.55pp)
89.89 (+3.59pp)
89.99 (3365pp) 84.11 (+3.47pp)
89.3440.41 (+2.88pp) 83.63+1113 (+2.78pp)
CIFAR-10,z0.1
84,42+0.41 (43.41pp)
84,94 (+3,41pp)
Table 16: Performance FedorAS when scaled 8 tiers.
Tier
Tier
Tier
Tier 5
Tier
Tier
Tier 8
CIFAR-10, 10,=1.0
87.53
87.81
87.59
87.84
87.65
87.76+0.40
87.21
87.11
CIFAR-10a=0.1 80.34+1.70
81.5640.46
81.50=111
81.5420.0
81.12=0:11
81.14
81,28
79.92+1.04
The results in Table 13 tstllll us that even in the scenario where the span of model footprints is larger (82x this experiment): small models (Tier 1 - up to 101 MFLOPs) trained with FedorAS can very well take advantage of larger models trained other more capable clients (Tier 2 and above); and, better models are obtained across Tiers showing large gains compared to the original supernet (considering models up 700MFLOPs approximately).
H.2 SCALABILITY MORE CLUSTERS
So far, we have shown results on a set number of clusters. In this section, we scale up the number of clusters from 4 to 8 and show the behaviour of our system in the case of CIFAR- CIFAR-100==1..0.3) Results are depicted Tab. 16
H.3 DIFFERENT ALLOCATION OF CLIENTS TO TIERS
In this experiment, contrary what described in Appendix D.4 trace from Oort [44] for our device to cluster allocation and performed training on CIFAR- and CIFAR- 100. Results are depicted Tab. [7 It can be witnessed that FedorAS is able to operate even under harsher heterogeneity conditions and still output competitive models in the federated setting.
adopt the device capabilities
I FAIRNESS
Up this point, we have reported on the global accuracy, which is union over the test of the clients for all datasets but SpeechCommands, which defines a separate set of clients mutually exclusive to the ones participating in federated training. In this section we want to measure how the ability of our system to aggregate knowledge across tiers during supernet training affects the fairness in participation. We quantifyy this through variance and worst-case statistical measures of client performance their respective test set. These test sets are considered to be following the same distribution (L.AA or pre-split) of their train and validation sets.
Results are shown on Tab. 18 for the different datasets offering per-client test data splits for all clients. can be seen that Fedo ASS leads consistently to better performance compared to end-to-end FL trained networks of the same architectures, where only eligible clients can train models. With respect to the standard deviation of per client performance, we witness FedorAS offering lower variance, except for the case of CIFAR- 100. We consider this to be a consequence of our significantly higher
Table 17:
FedorAS performance under 44 device clustering. We see that performance still scales well, albeit taking an impact due to more extreme system heterogeneity compared results from Tab. [ This hints that weight-sharing through our supernet works well under varying device allocation settings.
Dataset
Aclients
Method
Perf.
CIFARI0,.1
100(10)
FedoråS
[87_77 87.43 87.15 87.01
(10)
rond
15.83 83.912a08, 83,2140.0 10
C1
(10)
FedozåSprra
[44,33:nsL, 43.83 43.72:aa2, 43.22:140
500 (10)
rond inis
33.76 32.72 30.77
28

---

Under review as a conference paper at ICLR 2023
Table 18: Quantification of fairness with per client accuracy statistics, comparing end-to-end with FedorAS's performance. We report on the mean, standard deviation per tier and across tiers and minimum performance (min accuracy or max perplexity) across datasets with per-tier client test sets. Lower standard deviation is better.
Mode
Total Clients
Perf.
Perf. (per
Wonst Perf
Dataset
(across tiers)
CIFAR-10
Fedoras
81_36:8.58
182.43:787, =9.4, 81,78:3.49, 79.80:84:]
47.00)
(Acc. 09 betir)
rand-init
65.70 13.111
167,4311222% 66. 10.1455 66. 14113.02, 13.12.11276
11.00
CIFAR-100 100
Fedoras
15.61=13115
[44.46211881, 11.51 15.19 13.29=13155
5,00
500
(9) betie)
rand-inir
31,08..12.0
[30.7211314,
30.65111.27, 30.43L111.25 12.52..12.59
0.00
Shakessparee
Fedoras
1.93
12.93#897,
2.94 1.83 2,98=1.04, 1.91
8.43
(Perpionty y hetterr
rand inis
3.07
[3.07=1055 3.08 3.02=1.11,, 3.11, 3.07
8,36
rand-init FederAS
80
Cient
Figure 10: Accuracy per client of FedorAS vs. end-to-end (rand-init) Fl.-trained models (same architecture) on CIFAR-10. 10. Accuracy is quantified on each client's dataset from the model associated with that device's 's tier and error bars represent the standard deviation of accuracy between different runs. Across runs, the allocation of data to clients does not change. Ordered by ascending end-to-end accuracy.
accuracy. Similar behaviour, also witnessed when we measure variance per tier of devices. Last, we also showcase the worst-case result of clients performance in the last column of the table.
in-depth view of how each client behaves is depicted in Fig. TO for CIFAR-10 10, where we show performance of Fedoras vs. end-to-end FL-trained models per client.
J EVALUATION OF THE SEARCH PHASE
J.1 SENSITIVITY TO SIZE OF VALIDATION SET
In order to more meaningfully examine the impact of the validation set size, we run experiments on all datasets with 20% and 50% of the size of the initial global validation set. This means that during Stage-Il of FedorAs, architectures sampled from the supernet are scored using fraction of the global validation set. These validation subsets are extracted uniformly. After obtaining the best performing models for each tier, these are fine-tuned in a federated fashion (Stage-III in F FedorAS) for 100 rounds just like it was done for Tab. [ We maintain the same hyperparameters those used to generate Tab. [5] Results are depicted in Tab 19 for all datasets.
J.2 FEDERATED SEARCH
In this Section, we provide additional details and results concerning our federated variant of NSGA-II, discussed in Sec. 4..] of the main paper. Below, provide some context about how the algo- rithm works, how we setup the federated experiments and commentary of the results on CIFAR- 10 10000,1.0.13 and CIFAR-100.
29

---

Under review as a conference paper at ICLR 2023
Table 19:
Test accuracy for different sample size of validation set. Results shown relative change in final test accuracy for each tier compared to the scenario where the whole validation set used. Results each dataset are averaged over three runs.
Dataset
Clients
Partitionnng
Val set pret.
Classes
Tier
Tier 2
3
Tier
1.0
10
89. 19.401: 19
89 602001
89.642973
89 29
IDD 1000
0.5
-0.31
-0,10
-0.14
+0.03
-0.17
-0.19
-0.02
CIFAR-10
100
non -1.0
0.5
1.0
10
85 990
+0.06
86. 302041
-0.18
+0.19
85. 55.58:4455
-0.19
+0.02
-0.28
-0.29
1.0
81.01 L:46
81,53,u2
80.64,a0e
80.85 6.26
10
non-I1.2-o.1
0.5
+0.633
-1.5
-0.29
-0.14
+0.13
-1.55
-0.09
1.0
100
45.25 1..11
8..84nn
45.42,001
45.07 .671
CIFAR-100
500
non-I
0.5
-0.30
+0.01
-0:27
-0.38
+0.07
+0.11
40.32
-0.60
Speech Commands
2112
grven
0.5
1.0
12
80. 10.19 75
+0.40
80.47.1
+0.64
81.0 s
+0..2
80. 10.56_44m
+1.76
-0.98
-0.40
-1.49
+1.08
Dalaset
Clients
Partitioning
Val sel pret.
Classes
Tier
Tier 2
Tier 3
Tier 4
Tier
1.0
3.4
3.39
3.38 am
3.40
3:42.am
Shakesspaaee
715
given
0.5
90
-0.004
40,000
-0014
.0.05
-0.004
0.2
-0.002
-0.07
-0003
40.003
-0.008
Algorithm details. Federation is achieved by delegating evaluation of models to individual clients. This means that evaluation done stochastically on clients' local datasets. This setting is similar to Federated Evaluation in [64] In order to avoid sending large number of models to clients, thus saving communication cost, we leverage the fact that NSGA-II operates in "batches" of models in each iteration, a number of models (i.e. sample size) from the population is selected to produce new models that replace the ones not selected. Since models from a single "batch" are all selected at the same time, we do not need to evaluate them sequentially. Instead, considering that weights between architectures are shared, we can construct a minimal supernet that encapsulates all selected models and send it to relevant clients. This way, we can achieve parallel evaluation of all selected models and optima communication cost for a given "batch"".
Experimental setting. The experimental setting is following exactly what was used in other ex- periments. Specifically, population and sample sizes were the same as the ones used in centralised NSGA-II (128 and 64, respectively), and federated evaluation (FE) rounds were analogous rounds during federated training of the supernet from which models to evaluate were extracted. Concretely, number of clients, allocation of clients to tiers, allocation of data to clients, number of available clients per round, and client selection mechanism were all exactly the same for FE as the ones used during the relevant Stage of FedorAs.
However, to present more meaningful results, we assumed that as we fluctuate the number of clients used to evaluate models (number of evaluation rounds) additional clients are always unique. In other words, reshuffling and "forgetting" of clients is happening only between federated NSGA-II iterations. Consequently, it is possible that: i) if all clients are used to evaluate a model (e.g. 10 evaluation rounds for CIFAR- 10). FE is equivalent to centralised evaluation; ii) with relatively small number of FE rounds, it is possible that one set of models produced by NSGA-II is evaluated on a completely disjoint set of data to another "batch"; lii) similarly, we do not enforee in any way that all clients have to be used (unless we use all clients in a single iteration of NSGA-II). Finally, keeping consistent performed evaluation in tier-aware manner, meaning that models
with the rest of the paper, belonging to higher tiers could only access subset of all validation data based on client eligibility. This is the reason why relevant curves finish a different maximum number of FE rounds, that is a smaller number of FE rounds (i.e. Federated NSGA-II iterations) is needed to exhaust the set of eligible clients.
Results. Fig. II complements Fig. 4 and presents results across three different experimental settings, with varying level of non-IID-ness (a E (1, 0.1)) and numher of clients ((100, 500)). ). As conjectured in the main paper, we can observe that the cost of achieving the same fidelity of FE increases with both the level of non-IID-ness and the number of clients. Specifically, Kendall-7 of 0.8 is achieved
Opeimal sense of comminicatng paths once and not accounting for orthogonal techniques such compression, etc.
30

---

Under review as a conference paper at ICLR 2023
CIFAR1 Ozan
CIFARL 0LOA-1
1.00
Avg. total comm. CONT (GB)
Arerage Gubemet size (MB)
Average Kandalis
0.65
Tar
100
0.85
0.40
80
60
0.80
0.75
0.70
20
0.65
Tix
10
4
10
11 15 29 2729
No. FE rounds per NSGA iter
No. FE rounds per NSGA Iter.
NSGA-1 Reration
CIFAR10LDA--E C.1
CIFARIO
CIFAR10
1.0
120
Thr
Average supemet stza (NB)
80
Average Kendall
0.0
200
The
0.8
20
60
0.7
0.6
20
0.5
Thr Thr
Aeg.
10
11 13 15 23
No. FE rounds per NSGA-II Iter.
No. FE rounds per NSGAVI Iter.
NSGA-11 II Reration
CIFAR100
CIFAR100
CIFARIOB 63
300
Thr
Average supamet stza (MB)
Average Kondallis
250
The
0.8
200
62
150
0.6
Aeg.
10r 4
5
11
17
11 15 17 19
13 15 2729
No. FF rounds per NSGA-11 iter.
No. of rounds per NSGAHI iter.
N3GA-1I Reration
Figure 11: Ranking quality & cost of federated evaluation (FE) of models during federated search. Each time new population of models is evaluated, minimal supernet encompassing selected models is clients; left) ranking correlation between scores produced by FE & centralised evaluation (CE), as function of FE rounds (f rounds = 1 clients); middle) total communication cost of sending all necessary supernets to all clients, to run full search; right) changes in the supernet size as NSGA-II progresses.
sample of
approximately three FE rounds for (a 1, clients 100), and increases to four and six for {a 0.1, clients 100) and fa 0.1, clients 500}, respectively. At the same time, we can see that regardless the setting NSGA-II tends to produce smaller supernets as the search progresses, suggesting that searching for longer does not have to incur proportional increase in the communication cost.
J.3 CORRELATION WITH POST-FINE TUNING ACCURACY
The main objective of the NSGA-II search in Stage is find the most accurate models, where accuracy is understood as validation accuracy immediately after extracting a relevant subnet from pretrained supernet. The assumption that the better model performs
case like that, the better it will be after the following fine tuning performed in Stage 3. However, weight-sharing NAS is well-known fail meet this assumption many cases 82
Therefore, we additionally quantify the fidelity of out searching objective by measuring ranking correlation between validation accuracy of 160 random models from a search space, when taken directly from supernet after Stage 2, to their final test accuracy after fine tuning in Stage 3. Results are presneted in Figure T2
We can see that in general ranking models based on their accuracy when directly using weights from a supernet is not very faithful to how good model can be with extra fine-tuning, which is aligned with the aforementioned observations made in the centralised setting, While this shows that further improvements could be achieved with more work on the searching algorithm, we would argue that to would need to perform additional training, which
obtain more indicative performance of models, in our settings involves following the entire FL procedure, making the cost doing so even more con-negligible On the other hand, while the best models identified after Stage 2 are unlikely to be
31

---

Under review as a conference paper at ICLR 2023
Kendalkt: 0.255
Kendall-m: 0.237
Kendall-T: 0.327
Firal best eccurntyy ofter Stage
Findl test accurscy ahter Stzee
46
88
44
70
60 Stage ascuracy
40
50
70
80
90
30
70
10
20
30
Stagl accuracy
Stago 2 accuracy
Correlation between validation accuracy measured during Stage 2 and the final test accuracy of model after fine-tuning Stage 3, 160 models randomly selected from relevant search space. Left) CUFAR-10,=1.0 middle) CIFAR-10az0.1 right) CIFAR-100g=0.11 Note: unlike the rest of paper, CTFAR- 10 supernets were trained for 750 epochs here, not 500.
Figure 12:
the best after fine-tuning, they tend lean towards better performing ones. Therefore, based our strong empirical results and observed rankings in Figure 12. we would conclude that they constitute safe choice which, at the same time, involves minimal searching cost. Due those reasons, we leave the challenge of improving the fidelity of validation scores for future work.
32


Reviews:
[{"review_id": "g5tbzgNl9X-", "reviewer": "Reviewer_Zb8v", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method for federated neural architecture search, namely FedorAS, which leverages supernet for sharing knowledge across clients with device and data heterogeneity. They also introduce OPA (operation aggregation) that weighs the client updates in a frequency-aware manner. They demonstrate the effectiveness of their method against multiple existing methods.", "summary_of_the_review": "I enjoyed reading the paper, but several improvement seems to be required, as mentioned above.\n", "strength_and_weaknesses": "**Strength**\n- The paper is well-organized and easy to read.\n- They tackle the practical problem of federated learning where participants have device heterogeneity, i.e. computation and memory budgets.\n- They demonstrate the effectiveness of the proposed method in various modalities, i.e. vision, speech, text.\n- The results are impressive.\n\n**Weaknesses**\n- It seems better to discuss the overall costs (i.e. supernet train and model search time (ms) or # rounds, etc) and compare them to the baseline models. Since the proposed framework has three steps; (1) supernet training, (2) model search, and (3) local fine-tuning, each step may take the individual computation and communication costs. In the paper, however, I can only find the analysis for the searched models obtained from the step 3 only. More detailed discussion for overall costs is required, for example:\n    - How many rounds do the stage (1) and stage (3) need? \n    - How long does the (2) model search process take? \n    - How much overall computation and memory costs are required to get the final results for your model and baseline models?\n- Is the number of “tiers” the hyper-parameters? Can we have more tiers? Does varying the number of tiers affect the performance? or the overall costs for each step? \n- HeteroFL [Diao et al 21], one of the essential works tackling the same problem, is missing. The method also leverages the supernet for sampling local models considering the complexity levels, which is also similar to your tier clustering. It would be very helpful for you to discuss pros and cons and compare it with the proposed model.\n\nDiao et al, HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clients, ICLR 2021\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8g0hbcpufc", "reviewer": "Reviewer_C28f", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents FedorAS to discover and train architectures which are suitable for devices of various scales. FedorAS leverages a server-resident supernet enabling weight sharing for knowledge exchange between clients, without sharing common model architectures. This work also provides a new aggregation method called OPA for weighing updates from multiple “single-path one-shot” client updates in a frequency-aware manner. The method is demonstrated on different settings and shows a good performance while maintaining resource efficiency.", "summary_of_the_review": "The paper is overall well-written, providing a novel approach FedorAS to leverage a supernet for knowledge exchange between clients. The method shows better results by demonstrating on different datasets compared with multiple baselines. However, there are still some fundamental issues that need to be fixed.", "strength_and_weaknesses": "The paper is well written, and the method is well demonstrated on various datasets compared with different baselines. But there are still some issues, which are discussed in the next part. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8T5D44Ikbny", "reviewer": "Reviewer_7XQj", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The manuscript proposed a neural architecture search (NAS) algorithm, FedorAS, under cross-device federated learning setting. The proposed algorithm follows settings of one-shot NAS utilizing a super-net search space with weight sharing. It enables knowledge exchange between server and clients via sub-networks. And a new model weight aggregation methods is introduced to compensate sampling frequencies of sub-networks at clients. Moreover, the experimental results validate the proposed algorithm with datasets in computer vision, audio data processing, and natural language processing. The comprehensive experiments cover various FL setting including IID/non-IID data distribution, cross-device FL/cross-silo FL.", "summary_of_the_review": "The manuscript presented an interesting study of the proposed federated NAS algorithm. Its experiments are comprehensive. But its novelties could be limited as it is a straightforward combination of federated learning and single-path one-shot NAS.", "strength_and_weaknesses": "<Strength>\n\n•\tThe paper is well-organized and well-written.\n\n•\tThe experimental results supports the claims made in the manuscripts.\n\n•\tThe experiments and ablation studies are comprehensive.\n\n•\tThe submitted content is related to the application of neural architecture search in federated learning, which is highly relevant to the ICLR audience.\n\n<Weakness>\n\n•\tThe novelties of the proposed algorithm are limited. The idea of FedorAS is a direct combination of federated learning and single-path one-shot NAS.\n\n•\tDiscussion or ablation studies are not sufficient (see below).\n\n<Comments>\n\n1.\tWhat is training and searching efficiency of the proposed algorithm?\n\n2.\tHow to determine that when to stop the searching process?\n\n3.\tDoes the training recipe (e.g., batch size) matter for the NAS outcome? Do different training recipes or different random seeds result in different Kendall rank correlation coefficients?\n\n4.\tIt is the necessary to show the gap between federated NAS (FedorAS) and the centralized NAS?\n\n5.\tIs it possible to search for different architectures with FedorAS when clients have different computing devices or budgets?\n\n6.\tHow does the number of tiers affect the performance of the proposed algorithm?\n\n7.\tThe necessary ablation study would be evaluating ranking correlations using the proposed super-net based NAS algorithm.\n\n8.\tTypo: Page 6, Section 4, “… we we draw …” => “… we draw …”.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8JqbeCu6qC", "reviewer": "Reviewer_djQ3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a method called \"FedorAS\" which incorporates ideas from Neural Architecture Search into the domain of Federated Learning. In the scenario where the devices participating in a Federated Learning session has varying capabilities, and heterogeneous data distribution across devices, the goal of FedorAS is to provide each device with an efficiency-tailored architecture and parameters.  \n\nIn FedorAS, the participating devices are clustered into several tiers, according to their hardware capability. Using a supernet architecture, from which a subspace is sampled for each device. The client, after receiving the subspace, trains the models within the subspace by randomly sampling the subpaths. The server then aggregates the updated client weights using a weighted averaging technique which normalizes for the number of examples passed through each subpath. After training, the server performs the NSGA-II algorithm to find the best architecture for each device tier. After that, the obtained models are fine-tuned with FedAvg among devices with the same tier or above.\n\nThe authors report that FedorAS achieves better performance than other cross-device baselines, on multiple domains such as speech, vision, and text.", "summary_of_the_review": "FedorAS is a novel method for performing NAS in a federated learning setting, which outperforms similar existing methods. It is well-written and easy to understand, but some of the experiments are considered somewhat unrealistic, and analyses are lacking. The authors do not provide any code for reproducibility.", "strength_and_weaknesses": "**Strengths:**\n* FedorAS achieves superior performance over other baselines in cross-silo settings.\n\n**Weaknesses:**\n* An ablation study on the effect of the fine-tuning process is lacking. How much does the fine-tuning process affect the final performance?\n\n* Experiments on a more extreme division of the device tiers are lacking. For example, in the CIFAR-10 experiments, it is assumed that the lowest tier devices are capable of 120.9MFLOPs, whereas the highest tier devices are assumed to be capable of 716.0MFLOPs. That is only about 6x difference. However, the FLOPs difference between real embedded devices and high-performance devices is more extreme, for example, the FLOPs difference between the M1 chip and the Raspberry Pi Zero is about 500x, given the average power for each device. [1]\n\n[1] https://web.eece.maine.edu/~vweaver/group/green_machines.html", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject