Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ## Summary
In 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.

This 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.

## Pros
- The multi-server setting is interesting and practical. It hasn't been well-studied before. This paper makes the initial step along this direction.

## Cons
1. 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.
2. 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.
3. 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.
4. 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.

## Post-rebuttal comments
Thanks 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.

## References:
[1] Stich. Local SGD Converges Fast and Communicates Little. ICLR 2019
[2] Li et al. On the convergence of FedAvg on non-iid data. ICLR 2020
[3] Wang and Joshi. Cooperative SGD: a unified analysis for the design and analysis of communication-efficient SGD Algorithms. ICML 2019 workshop
[4] Khaled et al. Tighter Theory for Local SGD on Identical and Heterogeneous Data. AISTATS 2020
review_title: Review 1

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
This 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.

This 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. 

Pros:
+ The idea of leveraging overlapped ESs to decentralize FL is legitimate.
+ This paper shows promising experimental results compared with Hierarchical FL which requires more communication rounds.

Cons:
- 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.
- Performance gain over the prior art (*hierarchical* FL) is marginal when multiple clouds are adopted ($T_{cloud}=5$).
- Important baselines, such as cloud-based FL (FedAvg), and local training (without FL), are missing.
  - 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.
  - 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. 
- 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.
- 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.
- The weight design in Eq(9) is more like engineering efforts than theoretically motivated.
- 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.

Minor:
- The definition of  $t_c$(as the one-round delay) should be more clearly elaborated.
- 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.
- Eq(4): it would be better to use a different notation instead of $k$ for the second equation on the RHS to avoid confusion.
review_title: Interesting problem but lack of necessary motivation and novelty. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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).

Strong points:

1. How the broadcast wireless nature can be leveraged in federated learning is a practically motivated question, and the proposed algorithm is quite simple. 

2. The paper is well-written and easy to follow.

Major concerns:

1. 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. 

2. 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.

Specifically, (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.

Considering 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.

Other suggestions:

1. 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? 

2. 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? 

3. 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. 

4. 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?  

============= Post-Rebuttal Comments ===============
Thanks 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. 
review_title: Official Blind Review #4

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