Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary of the paper:
This paper brings into light a new perspective where the well known "FedAvg" algorithm can be modeled as expectation maximization. This reveals certain characteristics about federated averaging which can be useful in practice. Using these insights, "Fedsparse" algorithm is introduces that provides a trade-off between the sparsity (thus the model size) and accuracy of the models. Ample experiments are provided to validate theoretical claims.

Quality:
Presentation and the quality of writing is decent and the flow is understandable. But the major contributions are not clearly stated. I am wondering why the related work is at the end. I think it is better move the related work to an early section along with the emphasis on contributions.

Originality and significance:
I believe the connection between FedAvg and EM and the related understandings open up new avenues for designing better federated learning algorithms. FedSparse is clearly one of such methods that allows a trade-off between accuracy and memory consumption. Overall, believe this paper adds valuable contributions to the broader ICLR community.

Other comments:
When communicating the parameters from server to clients, I am wondering whether there are certain heuristics that can be used to prune $\theta$ values. Using an arbitrary threshold may not be the best given that the heterogeneous and non I.I.D. local datasets. Perhaps the authors can look into the effects of this as a future direction.

==============================================================================================================

Added after reading author response:

-----------------------------------------------------------------------

Authors have sufficiently addressed my concerns and I'm planning to maintain my generous score based on my initial understanding. However, other reviewers have raised many important concerns and I encourage authors to improve the paper based on those.
review_title: In overall, this paper adds valuable insights into designing fedearated optimization methods with help of EM analysis. I believe this paper adds decent contributions.

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Summary**

The paper proposes to re-interpret federated averaging (FedAvg) as a version of the expectation-maximization (EM) algorithm under a particular probabilistic model. Further, the authors propose to use spike-and-slab sparsity inducing priors over the local model parameters to sparsify the learned models (the corresponding method is called FedSparse), which naturally reduces the communication cost (only non-zero parameters need to be sent over the network). Improvement in communication efficiency is showcased on a few standard federated datasets.

**General comments and evaluation**

In my opinion, the paper has some interesting ideas; the effort to connect federated learning with techniques from probabilistic inference strongly resonates with me. However, the connection the authors make between federated averaging and EM is not as insightful as I anticipated. The fact that FedAvg can be seen as is a special case of EM with a particular choice of a prior distribution does not add much to our understanding of the behavior of the algorithm (e.g., convergence, issues related to different types of heterogeneity, etc.). While FedSparse is derived using Bayesian considerations, I would argue that the same algorithm can be derived using FedAvg + simple L1 regularization. Again, I do not see the benefit of the Bayesian formalism, especially given that it is essentially thrown away at the end by using the "hard" version of EM (where all the Gaussian distributions are collapsed). This unnecessarily complicates things without offering much insight.

Apart from the formalism, the authors should clarify the modeling assumptions of the FL setting they consider. Currently, there are two canonical FL settings, known as "cross-device" and "cross-silo" (https://arxiv.org/abs/1912.04977), which require FL methods to operate under drastically different assumptions -- the former assumes that the data is distributed among a very large number of devices (tens of millions) with limited memory and compute; the latter assumes a small number of clients with sufficient computational resources. It is unclear which of the settings the authors aim to address. For instance, $\arg\max_{w_{1:S}}$ in Eq. 13 seems meaningless in the cross-device setting since in practice S would be on the order of millions and only a subset of clients will participate in each round. I'm curious to hear which setting the authors had in mind.

All in all, I think the paper would significantly benefit from further clarification, a possibly theoretical analysis of the algorithm in heterogeneous settings (e.g., understand convergence rate and bounds on the tradeoffs between sparsity and performance) and/or a more careful and convincing empirical study.

**Detailed comments and questions**

- While reading the paper, a high-level question that wasn't clear to me: why use specifically "hard" EM for FedSparse instead of the standard EM?

- In the paragraph after Eq. 13, the authors propose a bunch of approximations, starting with collapsing Gaussian distributions, then removing the entropy term from the objective, setting hyperparameters, etc. This is a lot of approximations, I would like to know the purpose and the effect of each on the final result. Currently, many of these choices are obscure and unclear.

- The authors propose to use sampling of the binary variables z to compute gradients in Eqs. 18-19. The approach is indeed unbiased, but I'm worried that the increase in variance might be substantial in some practical cases. Can the authors somehow quantify this? (Ideally, provide a convergence rate for the algorithm that shows the effect of additional variance).

- What is the effect of structured pruning proposed to reduce server-to-client communication cost? It seems like a heuristic and it is unclear how it affects the algorithm.

**Experiments**

- Could the authors define local vs. global accuracy exactly?
- How many clients participated in each round in each benchmark? Was the server communicating with all clients or just a subset?
- The authors show some improvement of FedSparse over FedAvg and FedDrop in terms of the total amount of communication traffic in GB. Why does that metric matter? In which use-case? This goes back to my question about modeling assumptions.
- How many epochs per round did each client run? I would be curious to see how FedSparse compares to FedAvg if we double the amount of local computation (eg, make clients train for 2 epochs at each round instead of 1). I imagine that would improve convergence and reduce # of rounds, and as a result, reduce the total communication cost.
- I think that the benchmark datasets considered in the study may not be the best to showcase the benefit of sparsity. I would be curious to see how FedSparse compares to FedAvg on StackOverflow dataset introduced by Reddi et al. (2020), where the sparsity benefits can be much more visible. Eg, learning extremely sparse models could enable the use of much larger vocabularies, and as a result, produce more accurate models than what is achievable with FedAvg. That would be much more compelling evidence in favor of FedSparse than the results reported in the paper.
review_title: An interesting framework, but needs more clarifications and analysis, either theoretical or in the form of a careful ablation study

final_score: rating: 5: Marginally below acceptance threshold
review_content:   
The paper tries to use EM to explain the optimization procedure of the training method in a federated setting, and then treats the local model as a hidden variable of EM. Then, the authors propose a new FedSparse method to reduce communication efficiency by training a sparse model.

Pros:

It is a novel idea to treat local mode’s parameter \phi as a hidden variable in an EM framework. In particular, the following FedSparse algorithm is designed based on this setting. 

This proposed sparsity-based model compression method is linked to federated learning in a comprehensive way. 

As compared to FedAvg, the proposed method can reduce about 50% communication cost without scarifying accuracy. 

Cons:                                                     

The FedAvg is an SGD-based optimization, and treating the local model’s parameters as hidden variable phi_s is a little bit confusing. In particular, the FedAvg has no regularization term to prevent \phi moving too far from w, and the FedAvg’s variant version involves such a mode divergence-based regularization term – FedProx (Tian Li et. al. 2018).  Therefore, the definition of p(phi | w) in Equation 3 need more discussion.

The paper uses a classic sparsity method, spike, and slab (Mitchell & Beauchamp, 1988). The authors need to introduce a more model sparsity method for compression purposes and then justify choosing the spike and slab. 

In the experiment part, the proposed method and baseline methods have no significant difference in terms of accuracy. From a communication efficiency perspective, the proposed method should be also compared to FedDrop. Moreover, reduced communication cost in FedSparse is not very high.


	 
 
review_title: The paper has a novel idea but needs more clarification. 

final_score: rating: 5: Marginally below acceptance threshold
review_content: Federated learning has emerged as a promising approach to training models at the edge devices. This paper makes an observation that most algorithms used within federated learning, including the popular FedAvg, could be cast as instances of EM methods. The paper then continues to propose FedSparse, a federated learning framework imposing sparse priors (specifically Bernoulli-Gaussian priors), and concludes with some experimental results on FedSparse.

The paper revolves around two disjoint stories: *1) Federated learning can be cast in the EM framework*; and *2) FedSparse can solve federated learning with sparse priors*. Unfortunately, neither of these two stories are told in a convincing manner. My personal suggestion to the authors would have been to focus on one of these messages and do a thorough work around it. Here are my questions on the different parts of the story for the authors to strengthen their story and contributions.

**1-a)** The equivalences between coordinate descent and full EM, and many of the other observations made in this paper only hold when we are dealing with strongly concave convex problems. The paper lacks a rigorous statement on what conditions are needed for these methods to converge and what convergence rate guarantees could be derived. 

**1-b)** The observed equivalences in this paper are under the iid assumption. What happens in the presence of heterogeneous data?

**1-c)** Can you add a clear discussion on the connections between (Li et al. 2018), (Reddi et al. 2020), and the proposed EM framework in terms of the pros and cons and their suitability to different scenarios inspired by the observations in this paper? And can you then propose a set of experiments to verify such observations empirically?

**2-a)** How is FedSparse related to approximate message passing methods? AMP could also be cast as an instance of EM methods and is prevalent in solving sparse linear problems under the Bernoulli Gaussian prior assumption.

**2-b)** Can you please explain why the global accuracy of FedSparse is capped when compared to FedDrop? It is not clear to me why a sparse prior should be a good assumption in federated scenarios.

**2-c)** Can you please do a more in-depth study of the dependence of the performance of FedSparse in different scenarios? Can you also include (in the supplementary) a simulated scenario with truly sparse models and verify that FedSparse is well suited to such scenarios?

==== post rebuttal ====

It is an interesting observation that federated averaging and several other variants of it may be cast as instances of expectation maximization (EM). However, unfortunately, these connections have been made in a rather informal way, not resulting in much of new insights into convergence of such federated algorithms, or other practical tweaks to them. The paper then moves on to propose FedSparse, an abrupt shift from the original observation to federated learning with sparse priors. The study of FedSparse is thin, with unclear motivations, and with not so strong experimental results. Connections with the plethora of existing literature on sparse signal processing, specifically as it is cast in the EM framework, e.g., approximate message passing, is missing. In the end, the reader is left with two interesting ideas but it is not clear what the take-home message is.

My suggestion to the authors would be to "formalize" the connections between federated averaging and other instances of these algorithms (e.g., draw from EM literature to provide convergence guarantees, or maybe provide other variants of these algorithms with more favorable properties) and resubmit the paper with more formal connections to the EM framework. In my opinion, FedSparse is itself a separate paper that needs a separate motivation, set of hypotheses, and experiments.
review_title: two interesting observations; neither fully executed

Meta-review: The reviewers agree that the EM perspective of Federated Learning is novel and interesting. However, a common criticism is that the connection made is rather shallow and not sufficiently developed. There look to be quite interesting potentials of the proposed framework and the specific FedSparse method, but I agree with the reviewers that both aspects need further development before they are in publishable form.
Decision: Reject