FedMes: Speeding Up Federated Learning with Multiple Edge Servers
Authors: Dong-Jun Han
Minseok Choi
Jungwuk Park
Jaekyun Moon
Venue:  (2021)
Keywords: Federated Learning
Edge Servers
Wireless Edge Networks

Abstract: We consider federated learning with multiple wireless edge servers having their own local coverages. We focus on speeding up training in this increasingly practical setup. Our key idea is to utilize the devices located in the overlapping areas between the coverage of edge servers; in the model-downloading stage, the devices in the overlapping areas receive multiple models from different edge servers, take the average of the received models, and then update the model with their local data. These devices send their updated model to multiple edge servers by broadcasting, which acts as bridges for sharing the trained models between servers. Even when some edge servers are given biased datasets within their coverages, their training processes can be assisted by coverages of adjacent servers, through the devices in the overlapping regions. As a result, the proposed scheme does not require costly communications with the central cloud server (located at the higher tier of edge servers) for model synchronization, significantly reducing the overall training time compared to the conventional cloud-based federated learning systems. Extensive experimental results show remarkable performance gains of our scheme compared to existing methods.

Under review as a conference paper at ICLR 2021
FEDMES: SPEEDING UP FEDERATED LEARNING WITH MULTIPLE EDGE SERVERS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider federated learning with multiple wireless edge servers having their own local coverages. We focus on speeding up training in this increasingly practical setup. Our key idea is to utilize the devices located in the overlapping areas between the coverage of edge servers; in the nodel-downloading stage, the devices in the overlapping areas receive multiple models from different edge servers, take the average of the received models, and then update the model with their local data. These devices send their updated model to multiple edge servers by broadcasting, which acts as bridges for sharing the trained models between servers. Even when some edge servers are given biased datasets within their coverages, their training processes can be assisted by coverages of adjacent servers, through the devices the overlapping regions. As result, the proposed scheme does not require costly communications with the central cloud server (located at the higher tier edge servers) for model synchronization, significantly reducing the overall training time compared to the conventional cloud- federated learning systems. Extensive experimental results show remarkable performance gains of our scheme compared to existing methods.
INTRODUCTION
With the explosive growth in the numbers of smart phones, wearable devices and Internet of Things (IoT) sensors, large portion of data generated nowadays is collected outside the cloud. especially at the distributed end-devices at the edge. Federated learning (McMahan et al. [201]] Koneeny et al. 2016b [onawwtz et al. 2019; Li et al., 2019a) is recent paradigm for this setup, which enables training of machine learning model in distributed network while significantly resolving privacy concerns of the individual devices. However, training requires repeated downloading and uploading of the models between the parameter server (PS) and devices, presenting significant challenges in terms of 1) the communication bottleneck at the PS and 2) the nonlID (independent, identically distributed) data characteristic across devices ZZhao al., 2018 Sattler al., 2019 Li et al. 2019b
Reisizadeh et al., 2019; Jeong et al. (0188).
In federated learning, the PS can be located at the cloud at the edge (e.g., small base stations). Most current studies on federated learning consider the former, with the assumption that millions of devices within the coverage of the PS at the cloud; every global round, the devices in the system should communicate with the PS (located at the cloud) for downloading and uploading the models. However, an inherent limitation of this cloud-based system is the long distance between the device and the cloud server, which causes significant propagation delay during model downloading/uploodii stages in federated learning (Mao et al. 2017) Nguyen al., 2019). Specifically, it is reported in (Mao) et al. 2017) that the supportable latency (for inference) of cloud based systems is larger than 100 milliseconds, while the edge-based systems have supportable latency of less than tens of milliseconds.
This large delay between the cloud and the devices directly affects the training time of cloud- based federated learning systems. In order to support latency-sensitive applications (e.g., smart cars) or emergency events (e.g., disaster response by drones) by federated learning, utilization of edge-based system is absolutely necessary.
An issue, however, is that although the edge-based federated learning system can considerably reduce the latency between the PS and the devices, the coverage of an edge server is generally limited in practical systems (c.g., wireless cellular networks); there are insufficient number devices within the coverage of an edge server for training global model with enough accuracy. Accordingly, the

---

Under review as a conference paper at ICLR 2021
Model
(a) Model download
(b) Model average at the overlapped regions
0
Local update
(c) Model update with local data
(d) Model upload and aggregation
Figure 1: FedMes: the proposed federated learning algorithm leveraging multiple edge servers (ESs). The devices in the overlapping areas can as bridges for sharing the trained models between ESs. When specific ES given biased dataset within its coverage, giving more weights to the devices located in the overlapping regions (in each aggregation step at the ESs) can further speed up training. Our design targets latency-sensitee applications where edge-based federated learning is essential, e.g., when number of cars/drones should quickly adapt the current situation by cooperation (federated Icarning) and make the right decision.
limited coverage of single edge server could include biased datasets and thus could lead to a biased model after training. Thus in practice, performing federated learning with the devices in single edge server would result in significant performance degradation.
Main contributions. To overcome the above practical challenges, we propose FedMes, novel federated learning algorithm highly tailored the environment with multiple edge servers (ESs). Our idea here is to utilize the devices located in the overlapping areas between the coverage of ESs, which are typical 5G and beyond systems with dense deployment of ESs. In the nodel-dowwlloddig stage, each ES sends the current model to the devices in its coverage area; in this process the devices the overlapped region receive multiple models from different ESs. These devices in the overlapping area take the average of the received models, and then update the model based on their local data. Then each device sends its updated model to the corresponding ES or ESs, which is aggregated at each ES. A high-level description of FedMes is given in Fig. T
For example, suppose that device k is located in the non-overlapped region of ES i while device I is
in the overlapped region between ES and ES j. In conventional federated learning systems, device I
participates in the training process of only of ES i ES j; the other hand, in FedMes, device I can act as a bridge for sharing the trained models between both ESs. To be specific, the updated model of device A averaged only at its associated ES i. In the next step, this averaged model sent the
devices in its covered area, including device I. After the local model updates at the devices, device / sends its updated model to both ES and ES j. From this point of view, even when some training samples are only in the coverage of specific ES, these data can still assist the training process of other servers. Hence, the proposed scheme does not require costly communications with the central cloud server (located at the higher tier of ESs) for model synchronization, significantly reducing the overall training time compared cloud-based federated learning systems. Comparing with the scheme which does not consider the overlapping areas, FedMes provide significant performance gain, especially when the data distributions across coverages of different servers are nonlID, e.g., when a specific server has biased dataset within its covered area. Especially in this nonlID setup, giving more weights to the devices located the overlapping areas (in each aggregation step at the ESs) can further speed up training.
From the service provider point of view, FedMes does not require any backhaul traffic between the ES$ and the cloud server, significantly reducing the communication resources required for federated
2

---

Under review as a conference paper at ICLR 2021
learning. Moreover, since the devices in the overlapping areas send their results to multiples ESs, our scheme can reduce the number of devices participating at each global round while achieving the desired performance.
Extensive experimental results on various datasets show that FedMes provides remarkable perfor- mance gain compared to 1) the scheme that requires communications with the central cloud server for model synchronization (i.e., cloud-based federated learning) and 2) the scheme that does not take the overlapping areas between servers into account.
Related works. Thanks the recent advent of edge computing, there has been an increased interest
in edge-facilitated federated learning systems (Tran et al. 2019 Wang et al. 2019 Lim et al. 2020
Abad et al. 2020; Liu al., 2019). The authors of (Wang al. (219)
10019focomm focused on optimizing federated
learning framework with given resource budget in wireless edge networks. The authors of (Tran
et al. 2019) considered resource allocation to minimize energy consumption at the devices in wireless networks. However, single-server setup is considered in (Tran et al.) 2019) and (Wang et al. 2019)) which is totally different from our work leveraging multiple edge servers. Only a few prior works on federated learning (Abad et al.] 2020 Liu et al., 2019) considered setup with multiple edge servers. However, the schemes of (Abad et al. 2020 Liu et al. 2019) still require costly communication with the central cloud server for model synchronization, which could significantly slow down the overall training process. If the communication period with the cloud is small, frequent model synchronization between edge servers is possible but incurs large communication time delay, Infrequent model synchronization can lead to a bad performance especially with nonIID data across the servers. FedMes overcomes these challenges by enabling fast federated learning without any help with the cloud server, i.c., only using the edge servers. It is shown later in Section 4 that our scheme can outperform the hierarchical scheme of (Liu et al. 2019) which requires costly communications with the central cloud server.
2 PROBLEM SETUP
Federated learning. Let K be the number of devices in the system. Let n& be the number of data samples in device k. with Σk n& being the total number of training samples. We also denote the i-th sample in device k as Zk,5, for E 21,2,..., n4 Our goal is to solve the following optimization problem
min F(w) min Σ The Fx(w), n
where (w( is the local loss function of data samples in device k, written as Fe(w) ny D (( w). Now we briefly describe the conventional cloud-based federated averaging (FedAvg) algorithm in (McMahan al. (017). typical way solve this problem. At step each device downloads the current model w(t) from the PS, which is generally located at the cloud covering all the devices in the system. Then each device (say device k) sets (&()) w(t) and performs E local updates according to
(t i i 1) wx +) Th+ VF
(t. i i 0, -
(2)
where 7) is the learning rate at step t and (t) is set of randomly selected data samples from device at step Now each device sends the updated model to the PS, and the PS aggregates the model as w(t + E)= = Ek= li (t + E). However, full device participation at each aggregation step is impossible in practice and the PS often selects set S4+ C {1, .... K), containing the devices that transmit the results to the PS. Then, we have
n
w(1 E)
Σ KES
Th wx + E).
n
This overall process is repeated until the model achieves the desired accuracy or some stopping condition is met. According to the algorithm, the model of the k-th device at step ++ is written
(x(() (t) T) (F.
if E +
wa(t +
ng (1) ( (0. otherwise.
(4)
n
g
Problem formulation. In contrast with the conventional cloud-based federated learning systems having central cloud server covering the whole devices, in this paper we consider T. ESs each
3

---

Under review as a conference paper at ICLR 2021
covering its own local area. We call this local coverage of each edge server cell. Especially with dense deployment of ESs in 5G and beyond networks, there generally exist more than one ES within the range of specific user that can be reliably communicate with. We call this region in which the device can reliably communicate with multiple ESs overlapping cell area. Let C₁ be the set of indices for users located in cell E 21, ...; I.). Now define U, the set of user indices for the non-overlapped region of cell i, which is the subset of C. We also define Vi,5 as the set of user indices for the overlapping area between cell and cell j (i メ j and Vi,; v,), which is also the subset of C. Here, the devices in Vi, can communicate with both ES and ES j during model download or upload. While we can similarly define overlapped regions with more than two ESs, we consider the case in which the coverage of at most two ESs overlapped for clarity of presentation. Then the coverage of cell i, i.e., C2 can be written as
U VaJ) SELDMMO
(5)
for all i E (1.2, L). The overall coverage of the system can be written as C = 21, K]= = - U; U ( - V.,g). Note that each ES can communicate with the devices in its covered area only. Our goal is to solve the problem in (1) in this setup, without sharing the learning models at the higher tier of ESs (i.e., the cloud server) during training.
3 PROPOSED FEDMES ALGORITHM
Now we describe FedMes, the proposed algorithm tailored to the above setup with multiple edge servers. At the beginning of step i, each device in cell i downloads the current model (() from ES and lets (t) = ((() (t) if located in the non-overlapped region, i.e., k E U,. Device & E Va, additionally downloads w w(x) (t) from ES j and combines the two received models according to
W (t) Ekes!O nh + ERESCO) T&R
ΣΣ
N&W (t) +
Σ n& (t))((t) RES
KES
where 5(9) and s(d) are the sets of devices that sent their results to ES i and ES j. respectively, at
the previous aggregation step. Here, larger weight is given to the aggregated model of the ES that utilized more training samples in the previous aggregation step. If the number of training samples utilized at both ES and ES j are the same, i.e., Σkesfo n Ekespo ng, then we can rewrite (6)
as
(t( = 2 (w( (() + w (t).
(7)
We take this assumption for the rest of the paper for ease of presentation. Now every device (say device k) updates the model with its own local data according to equation 2 for E steps to obtain W1 + E). Then, device l sends its updated model w + E) to the corresponding ES((). In particular, the devices in the overlapped region Vi, send their results to both ES i and ES j by broadcasting. Here, note that this does not require additional communication time since only one round of communication is required at each device by the broadcast nature of wireless networks.
Now every ES i collects the locally updated models from the devices in its covered area C₁ obtain the aggregated result. In this aggregation process, each ES takes the weighted average of the received models, where the weight depends on the location of device & (i.e., whether device i located in the
s(8) overlapped region or not). To be specific, let 5 be the set of indices for devices that transmit the results to ES i. Then, ES obtains the aggregated result w (*)) (t + E) by taking the weighted average of the received models as
( (1+ = Σ W + E),
kE
where Y is the normalized parameter that gives weight depending on device k's location and the number of data samples in it:
k E U;
7
E Vi5 for all j
and
Σ 7ks =
(9)
kES
Here, a, and a, are constant values and we generally consider the case with a, I a,, to give larger weights to the devices in the overlapped regions that act as bridges for sharing the trained models
4

---

Under review as a conference paper at ICLR 2021
Algorithm Federated Learning with Multiple Edge Servers (FedMes)
Input: Initialized model w(0), Output: Final global model w Set wx (0) w(0) for all devices
1,2,... ... K
1: for each step & = 0, 11,,..... ..., T do
2: if' 1 1 t + then
3:
for each device k = 1.2, ..... K in parallel do
4: (x 1) (t) 7) (F..(((((tt...(() // Local update
5: end for
6:
else
Each edge server randomly selects 5(0) to receive the updated models from the devices for each device k 1,2, ..., K in parallel do
7:
8:
9:
if k E U, for some i {1,2, ..., L} then
w I)) - Σ EkEStY 7k (t<(t) my (FF
// Edge aggregation
11:
end if
12:
if E Vas for j.j E {1, 2, ..., L) and i # then wx(( + - E ExestY) Th (t) n (F))(((((())&(())
13:
|| Average of
+ + CNEs(i 7hk (l) (FA((w
two edge aggregations
14:
end if
end for
16: end if
end for
18:
w + Exess (T) // Averaged model of L edge servers
between ESs. Note that by setting a., Oe,, the above aggregation rule in (8) at each ES reduces to the conventional FedAvg in (McMahan et al., (017). This overall process at the edge servers and the devices is repeated until some stopping condition is met, say step T. When the overall training is finished, the models are averaged over all ESs to obtain the final global model w as follows:
w
(T))
(10)
The details of FedMes are summarized in Algorithm I Compared to the conventional cloud-based federated learning systems which require communication with the cloud server (located at the higher tier of ESs) for model synchronization, in FedMes, only the communications between the devices and ESs are required. Fig. 1 shows an example with L 3. [U,] [U2] = UU 2 and V3,1 1. As can be seen from Figs. ((b) and [(c) the unique characteristic FedMes that the starting points of models could be different even for the devices the same cell, due to model average in the overlapped regions. This is totally different from typical federated learning algorithms in which the devices have the same starting points at the beginning of each global round. From the overall process, it can be also seen that the non-overlapped region of cell i, i.e., Ug these data can still assist the training process of other cells. We show later in Section 4 that
[Vi.2| = 1/2
when some training samples only in
scheme with multiple starting points performs well by sufficiently reflecting the data samples that are not in the coverage of a specific ES. By utilizing the weight parameters 7k in (2). the model of device k C2 at step + be written follows:
W (t)
T/e V.. (t), (t), Σ 7h (t) (V, if 6+ and E U,
if if E +
wx(++1) +1) =
Σ (w(wx(() (w.
(11)
kEs
Σ
78 (R(w<(t)
(0) if E | tt+1 and & Vi,
RESU)
for E (1,2, I.) and (1,2, 1.) (i).
5

---

Under review as a conference paper at ICLR 2021
100
80
70
85-
Test accur eccurecy
83
Tost sccuraay
60
Test S00u
80-
Fastlee ted pwc3
FFoliles 2-20
86
-Fachles: un20 v-11
600
FFohhea: 1150
85
Aign In noweag (1n30 (wl)
Herarchal FL "1
-Ago.1 no overipg (aod
Mesrachccll FL "oou"")
40
seedap Jaallood)
Heranricl (T
Merarovical "awe
30
Hasssciaal (T
80
82
20
10
40
50
150
30
90
150
180
Running time
Runnnnng time
Running time
(a) MNIST, to = 5
(b) FMNIST, fo = 5
(c) CIFAR1O, to =
90
70
Test accurecy
Test acouracy
80
accuracy
60
150
80
Heaad FLLT dove"" 1)
Algn ip ovedan (MwM)ow))
Fostile u.
Hora chioal FL IT
Fosties undiwed
85
84
Foohllss u-20
Agge mo zwarag lox00t wol)
Fwiklle: cad awd3
Verescnical
40
30-
20
Fedbliee tull 10
Aigo.1 overlap (1-90x-0)
Hierorchccl (f
[Heearthical FI (T
80
10
10
40
90
120
150
30
90
120
150
100
Running time
Running time
Running time
(d) MNIST, t. 10
(c) FMNIST, te 10
(f) CIFARIO, t. 10
Figure Test accuracy versus training time a (device IID, cell IT) setup.
Remark 1.
Note that our FedMes can be easily generalized to cell topologies with multiple overlap-
ping ESs (more than two), by simply adding equations in (17) for the regions with 3, 4 overlapping ESs more. We also note that (I7) holds regardless of the device's 's location, which means that (17) is still valid even with moving devices (i.e., mobiles).
4 EXPERIMENTS
In this section, provide experimental results for algorithm using the MNIST (LeCun et al. 1998). FMNIST (Xiao et al., 2017) and CIFAR10 10 (Krizhevsky et al. 2009) datasets. We split the MNIST and FMNIST datasets into 60,000 training samples and 10,000 test samples, and split the CIFAR1O dataset into 50,000 training samples and 10,000 test samples. For MNIST and FMNIST, we utilized the convolutional neural network (CNN) with 2 convolutional layers and fully connected layers, and 2 convolutional layers and fully connected layer. respectively. For CIFARIO, we utilized
VGG-11 for training.
Comparison schemes. We compare our FedMes with the following schemes. First, we consider the hierarchical FL scheme (Liu et al. (019),, which utilizes L edge servers (with no overlapping regions) and a single cloud server. After F. local updates at each device, each edge server aggregates the models from the devices in its own covered area and then distributes across the corresponding devices. After Teloud aggregations at each edge server, the cloud server aggregates the models from the edge servers and distributes across the devices. Here, the case with Toloud = I can be viewed as the cloud-based systems since communication with the cloud occurs with every E local updates at the devices. Secondly, consider Algoritlum | with no overlap, where the proposed Algorithm is applied in setup with no overlapping cell regions. Each edge server independently performs training without any communication with the cloud, i.e., Teloud = cc. When training is finished, the model parameters of different cells are averaged to obtain the final global model.
Experimental setup. We consider a setup with L, = 3 edge servers and K = 90 devices. We also consider a symmetric cell geometry with |U1| = 1U/| = U3 u and Vi.2l |V2,al = |V/.1 = u. where u + K/3 /3- = 30 holds. In the aggregation step at the edge servers, we let each edge server to collect the results of randomly selected m = 20 devices in its covered area. Considering - edge servers, total of 60 devices participate in each aggregation step when there are no overlapping regions (v = 0). With v > O, each edge server has access to u + 2r devices. For a fair comparison, we let each edge server to collect the results of m 20 devices, where a+20
um of them are taken from the um of non-overlapped region U, and 2um of them are selected from the two overlapping areas, u+2e u+2e
each. Assuming that the adjacent edge servers select the same a=2o
um devices from the overlapping area
by cooperation, a total of 3(u-e)m 60(a+e) devices participates in each aggregation step. Hence, u+2F x+22
the number of devices participating each global round is reduced compared the scheme with no
6

---

Under review as a conference paper at ICLR 2021
100
70
85
95-
60
Test S02 apy
Test aocur aocureey
80
Tost accuracy
60
20
-3
Fediieer tadl vedn
Feahhess +-0
40
86
Aggal overlap (0-00x00))
FecMess u-20
-Tarsenncal Touu"!)
300
Alyo roinweden vwo2
Fechlea: 200
80-
Mararcheca FL -1
20
Hisrarshical PL
75
60
10
100 Running time
60
120
400
800
1000
Running time
Running time
(a) MNIST, to =5
(b) FMNIST, fo = 5
(c) CI
96
Test accuresy
Test acqurecy
Tost accuracy
550
60-
40
88--
80
RudMes---
Agp coetep 21
Holarhiial FL (T (!
Tecileer sed mw30
65
FTachlee ox20t
-Mgo1 no ovol (0+500
Heerandccaa ITL
Harardiiza
-30
20
Factins ued Fastdes und
Algo no overla (1-30
(Tamu
Herondiical 1n IT (l
Elberardeca FL
75
10
50
100
150
60
120
150
200
4:00
600
800
1000
Running time
Running time
Running time
(d) MNIST, t. 10
(c) FMNIST, to 10
(f) CIFARIO, t. 10
Figure Test accuracy versus training time a (device nonlID, cell IT) sctup.
overlap. We let fe be the one-round delay between the device and the cloud, where the one-round delay between the device and the edge server is normalized to 1. This one-round delay include both the communication time for one-round trip between the server and the device, and the computation time at each device. Mini-batch stochastic gradient descent with an initial learning rate of 0.01 is utilized. For all experiments, we set the number of local epochs each device to 5, and the local mini-batch size to 10.
We consider three data allocation scenarios test nonllD situations: The first is the (device IID, cell IID) case, where the datasets across K devices and across L cells are IID. Secondly, we consider (device nonlID, cell IID) case where each device randomly selects two classes for data assignment. Hence, the datasets across devices are nonllD but across cells are IID. The last is the (device nonlID, cell nonlID) where the devices in each cell are given with two fixed classes. Hence, the datasets across devices and cells are both nonlII. For the first two scenarios, we only consider the case with Qg = O₂ since our scheme with a, = a₂ already shows the optimal performance in these scenarios. For the last nonlll) scenario, we consider both cases with a, a and a, < 0gg- In addition, we ignored the batch normalization layers of the VGG model during training and testing for the last two nonlID scenarios.
Experiments in a (device IID, cell IID) setup. In Fig. 2 we plot the test accuracy versus running time in a (device IID. cell IID) setup. We let au a for FedMes. We have the following important observations in this setup. First, the proposed schemes with v >> have very similar performances. It can be seen that FedMes with 20, with all devices in the overlapping areas (u = 0, v = 30). Comparing FedMes with Algorithm 7 with no overlap (u 30, v 0), we have the following results. For the MNIST dataset, Algorithm [ with no overlap performs almost the same with the proposed schemes, since the dataset is simple enough to achieve the ideal performance by only utilizing the data covered by specific cell. With the FMNIST dataset, a slight gap between FedMes and Algorithm I with no overlap is observed. For more complicated dataset CIFAR1O, we have a larger gap between them, around test accuracy of 8%. Since the proposed FedMes and Algorithm with no overlap do not require any communication with the central cloud server during training, the performances are not affected by the parameter l..
10 has almost the same performance the scheme
Now we observe the hierarchical FL (Liu et al. 2019) with Taloud = 1, where the edge servers communicate with the cloud for model synchronization in every aggregation step at the edges. For all three datasets, our observation is that FedMes can eventually achieve the best-test accuracy of the cloud-based scheme, which is the ideal performance. However, the proposed schemes do not require costly communication with the central cloud server, significantly reducing the running time to achieve the ideal test accuracy compared to the cloud-based based systems. The hierarchical FL with Tetoud > can reduce the period of communication with the cloud, while achieving the ideal performance. Hence,
7

---

Under review as a conference paper at ICLR 2021
100
80
70
80
Test SOOU aay
80
70-
80
rectles uudt w-l1
Tectlee uudoado
Fectiaau u 10
Agga (oo0)
Hesaroodd FL
Test accur Bby
Polhlle u cn, 10--, 1.2r
Fedkles uudd 1o
-deerstiinn Fl
Test accurase
00
40
20
-00
Pactaee
Aigon www.eooog
50
40
40
60
120
1000
1500
Running time
Running time
Running time
(a) MNIST, to =5
(b) FMNIST, fo = 5
(c) CIFARIO, to =
60
Test ascures)
80
Factdle und
Test accurery
codd polllnge
Test accuracy
40
60
70
Foothins snddisat (0
60
Abpcl ro sartee 10-00
Factllc u 10
Herrodical
30
20
Feetfee Lwd3 wil
Pestffa 22
the seriicaa (T (
10
Hieoorthics FL. (T
Prevanticc PL
40
100
150
500
1000
Running time
Running time
Running time
(d) MNIST, t. 10
(c) FMNIST, te 10
(f) CIFARIO, t. 10
Figure 4: Test accuracy versus training time in a (device nonlID, cell nonlID) setup.
with a properly chosen Telond, it can be seen that hierarchical FL with T Telond performs better than the based scheme with T Toloud = However, the hierarchical FL. scheme still suffers from communication delay with the cloud, especially when te is large. Here, note that very large Telond can reduce the communication time with the cloud in the hierarchical scheme, but as Toloud grows, it gets closer to the comparison scheme Algorithm I with overlap. Therefore, significant degradation of the accuracy with complicated datasets is expected when a large Teloud is chosen to reduce the communication time with the cloud. The overall results show remarkable performance gains of FedMes compared to others, especially with on CIFAR1O.
Experiments in a (device nonIID, cell ITD) setup. Fig. 3 the result in a (device nonIID, cell IID) setup. We set a2 = a2 for our schemes. Since the datasets across the devices are nonIID, the performance of each scheme is degraded compared to the case in Fig. [2] We also observe a larger gap between the proposed schemes and Algorithm [[] with no overlap. The trend is consistent with the (device IID, cell IID) case, confirming the advantage of FedMes utilizing the devices in the overlapping cell areas.
Experiments in a (device nonlII, cell nonlII) setup. Finally, the case with nonIID datasets across both devices and cells is illustrated in Fig. 4 In this nonlID setup, we consider both cases with Og = (b and On < a, for FedMes. An interesting observation here is that the test accuracy of hierarchical FL with Trioud 5 decreases before each aggregation step at the cloud. This is because each edge server is given a biased dataset within its coverage due to the cell nonlIDness, which can degrade the performance before model synchronization the central cloud. Since Algorithm / with no overlap does not allow any synchronization at the cloud during training, it has significantly low test accuracy. In FedMes, the devices in the overlapping cell areas enable share the trained models between edge servers. Therefore, even when some edge servers have biased datasets within their coverage, the model of each edge server can be assisted by various classes that are not within its coverage. Especially in this scenario with nonlID data across cells, it is observed that giving more weights to the devices in the overlapping cell areas (i.e., ag < a.y) can further speed up training than the scheme that gives the same weights to all devices (o.,. = o.,). The overall results show that FedMes is still powerful even in this nonilI setup, compared to the schemes that require costly communication with the central cloud server for model synchronization and the scheme that does not take the overlapping areas between edge servers into account.
Comparison with varying f.. We note that whatever computation/commuiicaaii delay model we use, one can define the ratio of (one-round delay between the devices and the cloud) to (one-round delay between the device and the edge) as fc. based their system parameters. Now the question is, given a t. value of the current system, which scheme performs the best and how much performance gain do we have? Fig. 5 provides the result on test accuracy at specific time function of le-
8

---

Under review as a conference paper at ICLR 2021
98
90
80
80.5
Test Scurrsy
accuracy
Tost accuracy
70
96
95
94
Agys costap 20020
nowter (1472
Hosarniica FL
Hanurchia FL (L.T...
Heraissaa FL. FL( 11
87
40
15
6
10
14
6
10
12
16
20
(a) MNIST, IID
(b) FMNIST, IID
(c) CIFARIO, III
Teat accuracy
Tost accuraay
Test accuracy
60
150
80
80
Fedlles, U-0
Fechies: 20
FecMes:
Tethiiet tnd0 2wild
78
Fachles: ux20 eo
70
Agos1 no overop (+-80aad))
Tharrchiaa IL "1
75
|eenssscanl TL
30
Alp.1 no oversp (an00ood)
Hera:caca PL (a
Hartrchiccl FL
Berorosca
50
74
20
(d) MNIST, device nonlID, IID (c) FMNIST, device nonlID, cell CIFARIO, device nonlID, cell IID
90
60
Test socursoy
80
Test aocuaacy
05s aocurapy
130
60
70-
Footicc 10
Fastlae uelowd
Mouuchhaa FL.T.m.e1 11
Ages no moedap (b300w))
65
Algo: (o overtap xv10
Fodiitee: (w20
Festieen:
Sodd IT "1
40
-00
scMMe:: 200
50
Horandhioal FL (T -8)
50
Hinureh koolockkoaaaoooo R.
Herrosica
TL
40
10
14
18
20
12
14
16
18
20
6
10
12
20
(g) MNIST, device/cell nonlID
(h) FMNIST, device/cell nonlID
(i) CIFARIO, device/cell nonlID
Figure 5: Test accuracy versus fc. The test accuracies computed specific time slot. 1) IID: time 30, 80, 80 for MNIST, FMNIST, CIFAR10. 2) (device nonlID, cell IID): time 40, 80, 400 for MNIST, FMNIST, CIFAR1O. 3) device/cell nonIID: time 60, 80, 1000 for MNIST, FMNIST, CIFAR10.
can be seen that FedMes performs the best even with small te value. Especially in practical regimes where the supportable latency of cloud-based systems are much larger than that of edge-based systems, FedMes can provide significant advantage compared to other baselines.
Comparison with varying The portion of devices in the overlapping area is another key metric that determines the performance of FedMes. In Supplementary Materials, we compare the performance of FedMes with different u values. A quick conclusion is that although there are some slight performance degradation, FedMes performs well even with a small portion of devices in the overlapping regions (i.e., small v). Especially in 5G and beyond systems where a large number of devices are in the overlapping regions, FedMes can provide significant advantage compared to other schemes.
5 CONCLUSION
In this paper, we proposed FedMes, federated learning algorithm leveraging multiple edge servers, to speed up training without sharing the models at the higher tier of edge servers. Our key idea was to utilize the devices in the overlapping cell areas, which act as bridges for sharing the models between servers. Extensive experiments verified the advantage of FedMes compared to existing methods on various datasets with different data distribution setups. Our solution enables to support real-time applications by speeding up federated learning in real-world wireless networks 1) having large communication time delay between the devices and the cloud server and 2) having biased datasets within the coverage of each edge server.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Mehdi Salehi Heydar Abad, Emre Ozfatura, Deniz Gunduz, and Ozgur Ercetin. Hierarchical federated learning across heterogeneous cellular networks. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 8866-8870. IEEE, 2020.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint arXiv:1902.01046, 2019.
Eunjeong Jeong, Seungeun Oh, Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong- Kim. Conmunication-efficceenn on-device machine learning: Federated distillation and augmentation under non-iid private data. arXiv preprint arXiv: arXiv:1811.10 11/..11114777 2018.
Jakub Konecny, H. Brendan McMahan, and Daniel Ramage. Federated optimization: distributed machine learning for on-device intelligence. arXiv:1610.02527, 2016a.
Jakub Konecny, H. Brendan McMahan, Felix X. Yu, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Workshop on Private Multi-Party Machine Learning, 2016b.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2) 2222222444 1998.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. arXiv preprint arXiv: trrXiv:990..00 1908.07875. 2019a.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprini arXiv: 007.02289, 2019b.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Bing-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communications Surveys Tutorials, 2020.
Lumin Liu, Jun Zhang, SH Song, and Khaled B Letaief. Client-edge-cloud hierarchical federated learning. arXiv preprint arXiv: /905.0665566 2019.
Yuyi Mao, Changsheng You,Jun Zhang, Kaibin Huang, and Khaled B Letaief. A survey on mobile edge computing: The communication perspective. IEEE Communications Surveys & Tutorials, 19 (4):2322-233) 2358, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication--fffcieee learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, 2017.
Ti Ti Nguyen, Vu Nguyen Ha, Long Bao Le, and Robert Schober. Joint data compression and computa- tion offloading in hierarchical fog-cloud systems. IEEE Transactions on Wireless Communications, 2019.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-effiee federated learning method with periodic averaging and quanti- zation. arXiv preprint arXiv: 1909, 13014, 2019.
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and communication-eeiiccent federated learning from non-iid data. IEEE transactions on neural networks and learning systems, 2019.
Nguyen H Tran, Wei Bao, Albert Zomaya. Nguyen Minh NH, and Choong Seon Hong. Federated learning over wireless networks: Optimization model design and analysis. In IEEÉ INFOCOM 2019-IEEE Conference on Computer Communications, pp. 1387-1395. IEFF, 2019.
10

---

Under review as a conference paper at ICLR 2021
Shiqiang Wang. Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 37(6):1205-13)) 1220,,1211,2111 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprini arXiv:1708.07747, 2017.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, arXiv preprint 17Xiv:180600055 2018.

---

Under review as a conference paper at ICLR 2021
A TEST ACCURACY VERSUS GLOBAL ROUND
Fig. A.1 shows the accuracy-versus-oumm plots for each dataset and data distribution setup. can be seen that FedMes with both (u 0, 30) and (u 20, t 10) achieve the same final accuracy with the cloud-based system (purple line), except for the case with Fig. A.I For CIFARIO in a (device nonlID, cell nonlID) setup, FedMes with (u = 0, v 30) achieves the same final accuracy with the purple line but the case with (u 20, v = 10) does not. This indicates that a larger number of devices should be in the overlapping areas across the cells are nonllD and the dataset is relatively complex.
bridges, especially when the data distributions
80
95
Test aoouracy
100
Test accuracy
Tast accurary
600
86
Fistlee uwd80ow 10
FostAca Un-00-3
85
Foohllss u-20
Farhlle: cad awd0
und v0000
Aggn cowtap (1-30 awd)
Agge mo zuarag Inx00 mal)
40
80
Herarcheca 11
84
ercrchicll T1
(u-Sta--0)
75
Herarchoo FL (T
Terreciccal (
20
eraerciical cou
|Terschical ('ous!))
70
10
20
30
40
0
30
60
90
120
130
180
80
120
160
Globral round
Globral round
Global round
(a) MNIST. IID
(b) FMNIST, IID
(c) CIFARIO. IID
1.00
70
60
Test socuraay
Tost accuracy
80
Test accuracy
60
25
85
FooMass u-dt ex10
His areiia FL +1)
Agoo (1-30w0))
Teccden uofowe0
20
Fustles u-20
-ovrarhooal FL
40
30
Algo: no pvertap (u-30xx0)
FadiMne: 1w
Feathaen und 2wi30
80
.orardica ge
20
(T
Harrrchica Fi.
75
60
10
400
Global round
Global round
Global round
(d) MNIST, device nonlID, cell IID (c) PMNIST, device nonlID, cell ITD (f) CIFAR1O, device nonllI, cell
90
60
Test accurac)
80
70
Myo.1 ovollap (--50)m-0)
Techlee: owd0 to
Herracoccal TL
Test eccuracy
80
Agait ro eeerlap (0-50.--0)
Fediiee: tud0 sw10
Leeortiical 17 (T
Fediitsst und
Test accurasy
80
40
-00
teerrchcal
Fediles; 0-00
50
Alpo: Deariap (1-
40
10
Heeorchiccl FI,
20
40
60
80
100
120
50
100
150
500
1000
Global
Global round
Global round
(g) MNIST, device/cell nonlID
(h) FMNIST, device/cell nonlID
(i) CIFARIO, device/cell nonlID
Figure A.I: Test accuracy versus glohal round.
B COMPARISON WITH VARYING V
In Fig. B.I we compare the performance of FedMes with the following cases: (u = 0, v = 30), (u 20, 10), (u = 25, u = 5), (u 30, 0). Although there are some slight performance degradation, FedMes performs well even with a small portion of devices in the overlapping regions.
C EFFECT OF VARYING Ouu Oie
In the main manuscript, we showed that giving more weights to the devices in the overlapping regions (during aggregation step at the edge servers) can further speed up FedMes, especially in (device nonlID, cell nonlID) setup. In this section, we provide additional experiments to gain insights on the effect of varying On and ag- Consider L edge servers (ESs) and let be the number of devices in the non-ow -verlaale region each cell and v be the number of devices in the overlapped region between any two cells.
12

---

Under review as a conference paper at ICLR 2021
100
80
70
85
Tost 3ccuracy
Test acuur00
60
Test Socu
80
85
100
und pv30
40
-5
30
80
82
20
10
50
150
30
90
150
Running time
Running time
Running time
(a) MNIST, IID
(b) FMNIST, IID
(c) CIFARIO, III
Test accurecy
Test acqurecy
80
Tost accuracy
50
00
40
885
-00000
70
Unl 2-200--10 10
100
80
.-00...0
65
U 50
50.a00
75
10
50
100
60
120
200
4:00
800
Running time
Running time
Running time
(d) MNIST, device nonlID, cell IID (c) FMNIST, device nonlID, cell (f) CIFARIO, device nonlID, cell IID
Figure B.I: Performance of FedMes with varying v.
Fig. C.1 shows the performance of FedMes with 20, 10 in (device nonllI), cell nonlID) setup. The overall settings are exactly the same as in the main manuscript. We have the following interesting observations from Fig. C.I First, if o, is too small, i.e., if we give too small weights to the devices in the overlapped regions, the effect of devices in the overlapping areas are neglected; the aggregated models of the ESs cannot be shared through the devices in the overlapping areas, degrading the performance of learning. If a₂ is too large, i.c., if we give large enough weights to the devices in the overlapped regions, the effect of devices in the non-overlapped regions neglected which also significantly degrades the performance of the trained model. With an appropriate choice of an and ag, we can speed up training compared the simple approach that gives the same weights to all devices in the system (a,, = a.). In particular, for MNIST, a, 1.3a,, gives the best performance, while ag 1.5a, does for FMNIST and CIFARIO.
|.1ssows
100
80
80
30
Teat aecuracy
20
socuracy
50
FosMessin
30
60
FesMest 11..5
Text
FedMess a, -80,
Feetheer o. 100
30
100
50
FacMMas
20
Fedkits:
-0.1m
Teedllet
20
40
6D
80
100
120
60
100
150
600
1000
1000
Punning time
Running time
Running Time
(a) MNIST
(b) FMNIST
(c) CIFARIO
Figure C.I: Effect of varying Ou,, Or a (device nonlID, cell nonlID) setup.
Fig. C.2 shows the result of FedMes with u = 20, = 10 in a (device IID, cell IID) setup. For MNIST, the test accuracy is not affected by aus a;; even though some devices may be neglected due to large/small ac,, we can achieve ideal performance since the dataset is simple enough and data distributions across the devices are IID. For FMNIST, we see slight gaps among the schemes with different au, a values. On CIFAR10, accuracies jump quite bit as aa and ag differ significantly. Compared to the result in a nonlID setup in Fig. C.I giving more weights to the devices in the overlapped region does not provide additional performance gain in this IID setup.
13

---

Under review as a conference paper at ICLR 2021
100
Teot accurany
-88
Fodides
Fachless oyen
Fedlless uy
Fechless o -1.50
Test
Fodides -00
-110
FedMeess
Fodilcs a, -0
84
Fochlesi 0,0
FedMes: o,eai
FediMees: ooa
10
20
30
40
50
50
103
150
00
100
160
Funniig time
Punnning time
Punning time
(a) MNIST
(b) FMNIST
(c) CIFARIO
Figure C.2: Effect of varying cuu. dv a (device IID,, cell IID) setup.
D EXPERIMENTS WITH MULTIPLE OVERLAPPING ESS
In the experiment section the main manuscript, we considered setup where each device located in the overlapping region of more than two ESs. Here, assume that the devices can be in regions with more than two overlapping ESs.
Again, we focus on L, = 3 ESs and define in the overlapped region among all L cells (see Fig. D.I). The number of devices in the system can be written K = 3(u v) + w. Fig. D.2 shows the performance of FedMes depending and we in a (device nonlID, cell nonlID) setup. Here, we let each ES to give the same weights to all devices regardless of the location. The overall results show that having more devices in the overlapped regions can speed up training. On CIFARIO, when u >> 0, the case with w >> 0 can achieve target accuracy much faster.
above. We also introduce we, the number of devices
u
V
u
U
Figure D.1: Number of devices located in each region with L cells.
100
30
70
30
Test sccureyy
60
70
Faciides: und vud0, WeB Faciides:
80
FodMlles
40
30
Fuiliees: und, vi20,
30
FactAne: Hell wu20 mill
v-10, wi30
50
FedMlcx
wx50
Fastdeo: ni20, vo wuo Festdsa: will wi20, mis0
30
20
Focthee: 10, su10, w-20
40
150
600
1200
Punning
Running
Running
(a) MNIST
(b) FMNIST
(c) CIFARIO
Figure D.2: Experiments with multiple overlapping ESs in a (device nonlID, cell nonlID) setup.
14

---

Under review as a conference paper at ICLR 2021
E EXPERIMENTS IN AN ASYMMETRIC CELL TOPOLOGY
In Fig. we provide additional experimental results in an asymmetric cell topology. The number of edge servers are L 3, and we set the number of devices in each region as in Fig. E.2 The results are consistent with the plots in the main manuscript, confirming the advantage of FedMes in practical asymmetric cell topology.
90
Test aocuracy
Tost accuracy
Tost socurasy
80
05
Symmeat: UnG
Symmemic aad telll Anyrsaatr
Spmmeticc: Symmeree: Asyrenetic
Symmeric: 10220000
Symmerik: u-30Am0
84
10
20
50
40
50
30
80
1.0
1.50
180
30
90
120
150
180
Running
Running
Running
MNIST, ITD
(b) FMNIST, IID
CTFARIO, IID
1.00
70
85
96
60
Test accurasy
Test accuracy
80
Test accuracy
150
90
25
40
Symmerte: und 30
Symmerec: 10-20-110
70
Symmemic un2
-30
Symmetiic u-200--11 Symmertic tndlooe Asymenetre
Symmeetic und
Symmeree und)
Asymmoali
Adyramemt:
20
75
60
10
50
100
150
30
60
120
200
4:00
600
000
1000
Running time
Running time
Running time
(d) MNIST, device nonlID, cell IID (c) FMNIST, device nonlID, cell IID (f) CIFARIO, device nonlID, cell IID
Figure E.I: Performance of FedMes in an asymmetric cell topology.
10
10
30
20
20
0
Figure E.2: Asymmetric topology with L = 3 cells.
F COOPERATION BETWEEN EDGE SERVERS
In the experiment section of the main manuscript, it is assumed that adjacent edge servers select the same set of devices from the overlapping area by cooperating with each other. In practical scenarios. we can imagine two different situations where this cooperative federated learning is available. First, if user mobility is not very high, the system proactively determines the candidate of devices available to participate in the current federated learning process. Then, we can design protocol that provides rule selecting devices in overlapping areas, For example, devices whose uplink SNRs with adjacent edge servers are larger than given threshold value consist of the candidates set first. The candidate devices can be arranged in order of high average of uplink SNRs with adjacent edge servers, denoted by d1, di.....de dg where d, is the device whose average uplink SNR is the i-th highest, when K devices are in the candidate set. Then, we can use the protocol that lets di..... dy participate in the first round of federated learning process. For the second round, d dx+1 1 ... daN participate. I Likewise,
15

---

Under review as a conference paper at ICLR 2021
variety of protocols can be designed to determine which devices will participate in each round of federated learning process. all edge servers agree to use certain protocol for selecting devices in the overlapping areas before the federated learning process begins, then we don't 't have to consider cooperation among adjacent edge servers in every round of learning process.
Second, even though most studies federated learning (including this manuscript) assume that edge servers select devices unilaterally, participating for federated learning definitely sacrifices the devices' resources and battery. Therefore, in practice, edge servers have request each device participate first, and the devices will respond to it. In this process, we can find some devices that are willing help cooperation among adjacent edge servers. This request-response process is required for our method as well as the conventional federated learning; therefore, it does not generate the additional latency for selecting the devices in overlapping areas. Thus, we can conclude that we don't have to consider the additional latency for selecting the same set of devices in the overlapping areas by cooperation among adjacent edge servers.
16


Reviews:
[{"review_id": "zEOEGS8HVpW", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposed to decentralize FL by using multiple edge servers (ES), each only covering a subset of user devices, and utilize devices in the overlapped region of ESs to assist model aggregation, which saves the need to communicate with higher tier ESs. This decentralized architecture for FL hopefully can be more communication-efficient than a cloud-based or a hierarchical FL framework, with comparable model performance.\n\nThis paper has its merits in leveraging devices in overlapped ES cells to assist model aggregation, which could be a practical FL setting in the near future given the advance of 5G techniques. Experimental results on several benchmarks revealed the efficacy of this approach compared with a hierarchical FL baseline. However, the nonnegligible pitfalls of this paper are 1) the novelty is limited, 2) the challenge that they aim to address is unclear, and 3) their algorithm objective is not well formulated. Moreover, as a purely empirical study, its experiment designs are quite simple, missing comparisons with more state-of-the-art baselines, which further weakens their contribution. \n\nPros:\n+ The idea of leveraging overlapped ESs to decentralize FL is legitimate.\n+ This paper shows promising experimental results compared with Hierarchical FL which requires more communication rounds.\n\nCons:\n- Although following an interesting direction, the novelty of their proposed algorithm is limited, and the challenge of this setting is not clearly described. I feel it is a straightforward extension of FedAvg and Hierarchical FL to a decentralized scenario.\n- Performance gain over the prior art (*hierarchical* FL) is marginal when multiple clouds are adopted ($T_{cloud}=5$).\n- Important baselines, such as cloud-based FL (FedAvg), and local training (without FL), are missing.\n  - 1) The main focus of this paper is to decentralize FL to improve communication efficiency, but the tradeoff between performance and communication efficiency is not shown in the paper.\n  - 2) Since the task of binary classification is quite simple, it is likely that each local device can perform well without using information from other devices, so I consider it necessary to comparing with local training. \n- The argument that FedMes is more communication-efficient than cloud-based FL is doubtful. FedMes actually requires more communication rounds, since critical users in the overlapped region need to communicate with multiple servers. Another argument in the paper that the communication can be done by broadcasting applies to cloud-based FL as well. A theoretical or empirical analysis of communication efficiency is needed.\n- Unclear objective: the proposed algorithm is designed to optimize Eq(1). However, since there is no higher-tier central server to aggregate the models from ESs, it is doubtful whether Algorithm 1 truly aligns with the optimization of Eq(1). A different objective, such as those adopted by personalized FL, where multiple sets of weights are learned rather than a single set, seems to fit this scenario more than the canonical FL objective.\n- The weight design in Eq(9) is more like engineering efforts than theoretically motivated.\n- Robustness of the proposed algorithm: Although I agree with the argument that \"even users in the non-overlapped region can help training in other ESs\". However, their contributions heavily depend on the participants of users in overlapped regions, and their hyper-parameter choice in Eq(9). An unresolved question is, when the number of users in overlapped regions is quite small, does their effects on other ESs reduce greatly as well? As shown in Figure 4, when there is no overlap, the performance is worse than all other baselines. The current experiment setting of using ratio 1:2 for overlapped versus non-overlapped users can be too enthusiastic. What if only 10% of users are in the overlapped regions? A sensitivity analysis of this ratio would be very interesting to see.\n\nMinor:\n- The definition of  $t_c$(as the one-round delay) should be more clearly elaborated.\n- Eq(6) - Eq(7): weighted average requires each user in the overlapped region knows the total number of training samples for its corresponding ESs, is this assumption practical? In cloud-based FL, only the central cloud knows the number of training samples for each device.\n- Eq(4): it would be better to use a different notation instead of $k$ for the second equation on the RHS to avoid confusion.", "extra_scores": {}, "extra_text": {}}, {"review_id": "yV000WDjpeJ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nIn previous federated learning literature, people usually assume there is only one cloud server communicating with all edge nodes/clients. However, since each server has its own coverage in practice, the latency between the server and clients out of the coverage can be pretty long. This paper focuses on reducing the communication cost in this practical setting. The authors propose to use multiple edge servers, which have overlapped coverages. The clients in the overlapping areas will receive model parameters from multiple server and return the average model back. This can help to mix the information between different edge servers. Experiments on MNIST, EMNIST, and CIFAR10 datasets validate the effectiveness of the proposed algorithm: FedMes.\n\nThis paper provides novel insights into a practical setting of FL. But its experimental setting is too simple and there's no theoretical guarantees. These make the evaluations to be less convincing.\n\n## Pros\n- The multi-server setting is interesting and practical. It hasn't been well-studied before. This paper makes the initial step along this direction.\n\n## Cons\n1. The simulation plots only show accuracy-versus-time. It would be great to show accuracy-versus-round as well. In figure (3), the purple line doesn't converge yet due to its high running time per round. It is unclear whether the purple line can achieve a higher final accuracy than other methods. Intuitively, there should be a trade-off: although communicating with a single cloud server costs a lot, it can ensure all local models to be the same and may have better final accuracy. This trade-off isn't clearly discussed in the paper.\n2. In practice, whether to use the proposed algorithm should depend on the latency per round as well as the topology of the overall network. For example, in the cases where the latency $t_c$ is very small or the number of overlapping clients $v$ is very few, then the performance of FedMes may not beat Hierarichical FL (T_cloud=1). In the paper, it's unclear how the performance of FedMes changes along with $t_c$ and the topology of the network, as the authors only consider 2 values for $t_c$ and 3 values for $v$. It would be better to have some plots showing how the accuracy changes with these parameters. It would help people to have a better idea on when to use this algorithm.\n3. This paper doesn't provide any theoretical guarantee for the proposed algorithm. It would be nice to see how the error bound scales with $t_c, u, v$. The analysis techniques for FedAvg and decentralized averaging is very mature. The authors can take a look at [1-4] to see whether FedMes can be easily analyzed by these frameworks.\n4. In the experiments, the authors only consider a symmetric topology among clients with only 3 edge servers. One can also generate some random topologies with arbitrary overlapping clients to test the performance of the algorithm. This kind of evaluation would be more convincing. Since there is no theoretical guarantees, only empirical results on a simple symmetric topology is not enough. It's possible that the proposed algorithm only works for this special case.\n\n## Post-rebuttal comments\nThanks the authors for the clarifications! Most of my concerns are addressed. But the newly added asymmetric topology is still very benign and there is only 3 cells. I agree with other reviewers that this paper can be further improved.\n\n## References:\n[1] Stich. Local SGD Converges Fast and Communicates Little. ICLR 2019\n[2] Li et al. On the convergence of FedAvg on non-iid data. ICLR 2020\n[3] Wang and Joshi. Cooperative SGD: a unified analysis for the design and analysis of communication-efficient SGD Algorithms. ICML 2019 workshop\n[4] Khaled et al. Tighter Theory for Local SGD on Identical and Heterogeneous Data. AISTATS 2020", "extra_scores": {}, "extra_text": {}}, {"review_id": "8G_c9zooDa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers federated learning for edge devices with multiple wireless edge servers. The paper proposes FedMes to leverage devices in overlapping areas covered by multiple edge servers. In particular, in FedMes, if a device is in the coverage area of multiple edge servers, the device receives current models from all the edge servers covering it. Each device uses a (weighted) average of the models it receives as a starting point, and performs local updates (using SGD). A device broadcasts the updated model to multiple edge servers that cover the device. The key idea is that these devices in the overlapping coverage area act as ‘bridges’, and communication between edge servers is not required (until the final averaging step). The authors carry out experiments to evaluate FedMes, and compare against hierarchical federated learning of (Liu et al., 2019).\n\nStrong points:\n\n1. How the broadcast wireless nature can be leveraged in federated learning is a practically motivated question, and the proposed algorithm is quite simple. \n\n2. The paper is well-written and easy to follow.\n\nMajor concerns:\n\n1. The main premise of the paper is that communication with the central cloud server located at the higher tier of edge servers is costly and incurs significant delay. (One of the selling points of FedMes is that it does not require any backhaul traffic.) However, the authors do not provide much evidence for this premise. In fact, the bottleneck in wireless networks is typically the communication between edge devices and edge servers, and the backhaul communication is usually cheap and fast. It is not even clear why a central cloud server is required since edge servers can talk with each other periodically, and simply average the models. It will be important to give an evidence that communicating with a cloud server or between edge servers incurs large delay. \n\n2. The paper only presents experimental evaluation, and the experiments make several simplifying assumptions. For instance, the latency with the cloud is modeled with simple one-round delay parameter t_c, and the one-round delay between a device and edge server is assumed to be 1. Further, the devices in overlapping coverage areas are assumed to be very symmetric. These assumptions do not seem to be practical, and it is difficult to assess the usefulness of FedMes over hierarchical FL. FedMes may perform better in these somewhat ideal conditions, but it would be important to consider practical aspects.\n\nSpecifically, (Liu et al., 2019) compute latency using a wireless model. Also, they consider various values of E and T_cloud. It will be useful to consider various values in the experiments for the fairness of comparisons. (Abad et al., 2020) also analyze end-to-end latency by considering the properties of the wireless nature. Overall, it will be important to consider similar models for latency other than taking a simplistic approach of one-round delay t_c.\n\nConsidering the above points, the contribution and novelty seem to be fairly limited. It will be helpful if authors can consider a more practical latency model, and/or provide more evidence for the values and assumptions used in experimental evaluations.\n\nOther suggestions:\n\n1. The authors cite latency sensitive applications, e.g., smart cars, to motivate faster training time. It will be helpful to clearly distinguish between training time and inference time. For instance, the 100 milliseconds latency considered in (Mao et al., 2017) is for training or inference? \n\n2. In Fig. 2 and 3, what are the units of $t_c$ and the running time? When $t_c$ (delay between cloud and device) is increased, clearly FL and hierarchical FL will be slower. It will be important to give evidence for how these values are chosen. Also, what about the case when ES can talk with each other over backhaul; does it incur similar delay as talking to a cloud server? \n\n3. In experiments, it is assumed that adjacent edge servers select the same set of devices from the overlapping area by cooperating with each other. It will be helpful to comment on the impact of this cooperation on latency as compared to sharing the (possibly compressed) models between edge servers. \n\n4. Considering the same devices in the coverage area of an edge server throughout the training process does not seem to be practical. Would it be possible to extend the experiments to consider the case when the devices in the coverage area of an edge server follow some practically motivated distribution?  \n\n============= Post-Rebuttal Comments ===============\nThanks to authors for their response and efforts in updating the manuscript. Some of my concerns were addressed. However, I still think that the novelty is fairly limited. For example, additional experiments in Fig. 5 produce quite intuitive results in the sense that any scheme that yields smaller t_c will have higher accuracy at a specific time slot. FedMes reduces t_c with the assumption that it is faster to communicate between edge servers. Systems-level experiments to thoroughly study the effect on t_c will greatly improve the contributions. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the benefit of having multiple servers (with partial coverage) in increase the training speed and latency in Federated Learning.  Of course optimization/learning in the multi-server setting comes with a number of challenges which the authors seek to address via novel algorithmic procedures (e.g. FedMes).  I believe the paper is suggesting an important, and potentially impactful, methodology to improve the training speedup/latency of FL. I also acknowledge the additional experiments provided by the reviewers which were quite helpful in addressing some of the concerns. However, as the paper mainly relies on experimental studies to evaluate the performance of the proposed methods, the reviewers (and myself) believe that the paper needs some more investigation in which (i) some of the assumptions (e.g. faster communication between the servers) are either removed or validated; and (ii) more complicated  topologies are considered. 
Decision: Reject