Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper investigates how to federate the Expectation Maximization (EM) algorithm in the case of a curved exponential family.
The authors propose a novel algorithm, called FedEM, which translates the EM algorithm in the FL setting, which consists in iteratively sending local sufficient statistics to the server and updating the value of the model. This algorithm takes into account the distributed aspects, communication constraints (using an unbiased compressor with an error feedback mechanism for the local statistics to send), partial participation, and data heterogeneity of the FL setting.
The authors prove the convergence of FedEM (Corollary 2).
A variance-reduced version of FedEM is also proposed (VR-FedEM), also with convergence guarantees (Th. 4).
Experiments are performed on toy synthetic data, MNIST and real data (missing value imputation from a tabular dataset, bird).
main_review: ## Originality

To the best of my knowledge, this is the first work tackling the federation of the EM algorithm, which makes it novel.

## Clarity 

Overall, the paper is very well-written and easy to follow even for non-experts. However, in the experimental section (page 8), it is not stated what figure 2 refers to - I assume it is the MNIST experiments given the number of components estimated.

## Quality

Regarding the theoretical results, I did not check in detail the proofs, so I cannot judge their correctness.

If any, the experimental section could be further expanded.
- For instance, the author state that a naïve implementation of the EM algorithm in FL would not be resilient to heterogeneity, but there is no experimental demonstration of this assertion.
- Further, there is no study of the effect of compression
- Last, there is no comparison with the results obtained in a single node setting: does one retrieve results which are close to them? 

## Significance

The proposed algorithms and the convergence proofs are the main contributions of the paper. While the experimental section is a bit weak, I do think this is a minor problem given the other contributions.


========
Update following rebuttal
========

I thank the authors for clearly addressing all my criticisms in their answer, and for the time and precision they devoted to answer the other reviewers. I will raise my score to 8.
limitations_and_societal_impact: See above
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the problem of expectation-maximization in a federated setting. They propose two communication-efficient algorithms where the clients compress certain sufficient statistics to save communication. For each algorithm, convergence rates are presented that match their centralized counterparts in the absence of compression. 
main_review: Originality and Pros: Both the problem studied, and the algorithms presented, are novel to the best of my knowledge. The compression strategies used are somewhat unique to the problem being studied which makes them interesting. Concrete analytical results are presented to support the proposed algorithms. 

Clarity: The paper is mostly well-written, but certain parts could do with better explanations. In what follows, I explain these concerns in detail.

(1) In the standard FL setting, statistical heterogeneity causes the local loss functions of the clients to have potentially different minima. As a result, infrequent communication leads to "client-drift" which, in turn, can cause convergence to incorrect points. For the federated EM problem the authors' study, I found it hard to understand what heterogeneity means (despite the explanation in lines 58-59), and what the implications of heterogeneity are for convergence. A concrete mathematical description of heterogeneity would be very helpful in this context.

(2) One of the major concerns in FL is to reduce the number of communication rounds. To do so, almost all standard FL algorithms I am aware of (e.g., FedAvg, FedProx, SCAFFOLD, FedSplit, etc. ) involve periodic communication between the clients and the server. In between two communication rounds, clients perform multiple local computations on their private data. In contrast, if I understand correctly, both the algorithms proposed in the paper involve communication between the clients and the server *at every iteration*. This is quite undesirable since the number of communication rounds can be significantly higher relative to existing FL algorithms.

The authors need to discuss this potential limitation of their approach. How would periodic interactions impact the convergence guarantees of their proposed algorithms?

(3) Continuing with the above point, it is precisely due to infrequent communication that data heterogeneity creates a problem in standard FL settings. Indeed, even in the presence of heterogeneity, if the clients exchanged model updates with the server at every iteration, the iterates of all clients would evolve synchronously, i.e., this would essentially be equivalent to a centralized setting. Said differently, if the communication period is 1, then the "client-drift" phenomenon that arises due to data heterogeneity in common FL algorithms would cease to exist. 

Since the authors do not consider periodic communication, how (if at all) does heterogeneity create a challenge? To make my question clearer, suppose there is no compression/quantization. Moreover, suppose all clients participate in every round of communication. Even in these scenarios, data heterogeneity leads to challenges in the analysis of common FL algorithms such as FedAvg and FedProx, precisely due to infrequent, periodic communication. In contrast, I would imagine that if there is no compression, and full client participation at all times, Fed-EM would essentially behave as a standard centralized EM algorithm. Isn't this correct? 

The point I am trying to make here is that not considering infrequent communication takes away the typical challenges posed by data heterogeneity in standard FL settings. This point needs to be acknowledged and discussed.

(4) The authors do not cite or discuss any of the popular FL algorithms such as FedAvg, FedProx, or SCAFFOLD (to name a few). I would encourage the authors to compare their model of heterogeneity and the communication structure of their algorithm to the ones in the following references.

[R1] "Tighter theory for local SGD on identical and heterogeneous data", Khaled et al, AISTATS 20.

[R2] "On the convergence of fedavg on non-iid data", Li et al., arXiv 19.

[R3] "On the convergence of federated optimization in heterogeneous networks", Sahu et al., arXiv 18.

[R4] "Scaffold: Stochastic controlled averaging for federated learning", Karimireddy et al., ICML 20.

(5) Regarding Section 2, the authors list several assumptions without commenting on how strong these assumptions are. Are these assumptions standard in the analysis of EM algorithms? How do they compare to the typical assumptions of convexity and smoothness in standard FL optimization settings? (such as those in [R1]-[R4])

(6) A couple of questions regarding Algorithm 1: (i) Is the operator T known to all clients? (ii) Lines 6-8 appear to be inspired by the "error-feedback" mechanism employed when one considers compression/sparsification of gradients. If so, this should be stated clearly. (iii) In line 5, what does it mean to sample a sufficient statistic S_{k+1,i}? 

(7) (i) Although the variance reduction method in Algorithm 2 appears to be theoretically sound, it is not adequately motivated as I explain below. Typically in FL, variance reduction or gradient tracking is used to reduce the "client-drift" phenomenon that arises due to data heterogeneity and infrequent communication (see [R4] above and [R6] below). Since the authors do not clearly explain what challenge heterogeneity poses for their specific problem, I found it hard to appreciate the need for Algorithm 2.

(ii) Unlike Algorithm 1, Algo. 2 involves both outer and inner loops. However, no explanation is provided for the rationale behind this. 

(iii) How does variance reduction improve (if at all) the convergence guarantees relative to Algorithm 1? Does this come at the expense of more communication? It would be instructive if the authors clearly compared the complexity bounds of Theorem 4 with those of Theorem 1. 

(iv) The authors should also discuss how their variance reduction approach compares with those used in standard FL settings. In this context, the most relevant works are [R4] above and [R5], [R6] below.

[R5] "Federated Learning with Compression: Unified Analysis and Sharp Guarantees", Haddadpour et al., AISTATS 21.

[R6] "Achieving Linear Convergence in Federated Learning under Objective and Systems Heterogeneity", Mitra et al., arXiv 21.

Reference [R6] in particular employs both gradient tracking and error-feedback to tackle statistical heterogeneity and compression/sparsification, just as in VR-FedEM. Appropriate comparisons are thus warranted.

========================== REVIEW UPDATE =======================================

I have read the response of the authors and also the comments of the other Reviewers. The rebuttal by the authors has improved my understanding of the paper. So I am increasing my score to a 7. 




limitations_and_societal_impact: The authors briefly discuss some limitations and societal impacts of their work in Section 5.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: Authors propose and study a distributed variant of Expectation-Maximization for exponential families. Theoretical analysis is conducted to characterize the convergence of the proposed algorithms towards stationary points of the underlying objective function. The empirical performance of proposed algorithms is studied via numerical experiments on synthetic and open data. 

main_review: * It is unclear how data heterogeneity is modeled and handled by the proposed algorithms. As i understood, the main model underlying the proposed algorithms are homogeneous i.i.d. draws from a single exponential famliy Eq. (2). How would your FedEM algorithm cope with completely heterogeneous data which e.g. conforms with a networked exponential family as studied in 

A. Jung, "Networked Exponential Families for Big Data Over Networks," in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.

* It would help the reader to have a dedicated section or paragraph about existing work and how the proposed methods related to it. Also, Section 2 could be dedicated to the precise problem statement including the communication link constraints. 

* It would be good to have a dedidacted paragraph in Section 1 that summarizes the paper's contributions. This paragraph should also discuss the relation between FedEM and VR-FedEM. Is the latter a generalization of the former? Do both algorithms apply in different settings? 

* Pls add more discussion on how to choose the input parameters of Algorithm 1 and Algorithm 2 

* The numerical experiments need to be expanded and also compare with other methods, e.g., network Lasso methods such as studied in 

SarcheshmehPour, Y., Tian, Y., Zhang, L., and Jung, A., “Networked Federated Multi-Task Learning”, <i>arXiv e-prints</i>, 2021. https://arxiv.org/abs/2105.12769

* Pls discuss if the Assumptions 1 - 9 are satisfied for the datasets and models considered in the numerical experiments 

* There needs to be more discussion/analysis of the obtained numerical results from the perspective of the theoretical results. Do the plots in Figure 1 confirm the statements/insights provided by your Theorems ?  

* I did not find any discussion/reference to Figure 2 in the main text. 

* it is mentioned that "A major advantage of the EM algorithm stems from its invariance under homeomorphisms,..." However, it is not clear to me how this invariance is relevant for your methods?

* unclear what is meant by "..where heterogeneity is characterized by the non-cancellation of the local gradients at the optimum,.."

* unclear what is meant by "..conditions must therefore be derived to ensure convergence at the central server." which conditions are you referring to here?

* "...the complexity grows at the rate..."  which complexity do you mean? computational complexity or sample complexity?

* "...see [16] for an interesting discussion on the connection of EM and mirror descent." how is this connection relevant for the following developments?

* could you provide more motivation/intuition for introducing the concept of a mean-field in Eq. (6) ? does your convergence analysis make heavy use of this mean-field?

* "...that the conditional variance is (uniformly) bounded" the conditional variance of what quantity?

* "... of the new sufficient statistics." not clear what the "new sufficient statistic" is 

* "Crucially, a naive implementation of compressed distributed EM without assumptions on the heterogeneity would not converge." maybe add a reference to a proof for this statement 

* pls add more discussion on the consequences of Proposition 3. how strong does partial participation hurt the performance compared to having full participation?






limitations_and_societal_impact: this is theoretic work and therefore the societal impact can only be discussed on a rather high level.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes methods to implement Expectation-Maximization (EM) algorithm under Federated Learning (FL) setting. The methods proposed incorporate gradient compression and variance reduction techniques, and also allow for partial participation during training process. Moreover, the paper gives finite-time complexity analysis of proposed methods. Finally, paper demonstrates their methods by both simulated and real data experiments.
main_review: While the problem solved by the paper is important and interesting, the way it is solved in the paper seems straightforward. More specifically, the EM algorithm is well-studied, and both of the gradient compression and variance reduction techniques used to implement EM for FL setting are borrowed from previous literatures. The theoretical analysis, while it is appreciated, looks like adaptation from existing papers. All in all, I do not see much novelty in this paper.

The paper is technically correct. The paper gives finite-time complexity analysis of proposed methods. The paper demonstrates their methods by both simulated and real data experiments. The work is overall complete.

The submission is well-organized. The methods are clearly motivated and explained. The proof is clear and complete as well.

The problem studied by the paper will be interesting for many practitioners. However, the paper is more like a combination of existing works in to guide engineering, rather than a novel research. There is limited unique results in the work. Thus, overall, it is of limited significance. I think at least paper should make it more clear about what is new in this work.
limitations_and_societal_impact: The paper discussed about its potential negative societal impact. The paper could perhaps think more about whether EM under FL can protect privacy.
review_title: null

Meta-review: The reviewers appreciate the incorporation of EM algorithm into federated learning for dealing with data heterogeneity. The paper makes good theoretical contributions but also has weaknesses in experiments. Overall, I am in favor of acceptance. Please incorporate the new results in the final version. Please revise the paper based on the reviews and rebuttals.
Decision: Accept (Poster)