Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The following points summarize the paper:

1. The authors propose a two-phase federated learning algorithm to learn cluster label and mixed regression parameter vectors. 
2. In Phase 1, few anchor clients (with $\tilde{\Omega(k)}$ data) obtain a course model estimate.
3. In Phase 2, each client alternately estimates its cluster label and refines the model estimates based on FedAvg or FedProx.
4. Their method works with unbalanced data across clients.
5. They also provide global convergence of their algorithm with any initialization.  

strengths_and_weaknesses: Strengths:
Authors have done a commendable job of providing theoretical gurantees for their claims. The paper is theoretical in nature and like any theoretical paper, seems a bit tedious to parse at times. However, on a high level all the proofs seem to follow naturally and support the claim. Overall, it is a well written paper with strong theoretical claims.

Weaknesses:
- The assumptions such $\| \theta_j^* \|  \leq R$ seem quite strong as they essentially remove $O(\sqrt{d})$ dependency (assuming $R$ is treated as constant) from the problem. This combined with conditions like $\frac{R}{\Delta} = \mathcal{O}(1)$ seem like quite stringent conditions on the entries of $\theta_j^*$. 
- Although, it is a theoretical paper, it would have been nice to add some experiments (on synthetic or real data) to validate the theorems.     
questions: - Is $R$ (and $\Delta, \sigma$) treated as a constant in the proofs? If not, does it change the theoretical results (concentration rate etc)?  
limitations: The limitations are adequately addressed by the authors.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper generally studies the problem of clustered federated learning. Specifically, the paper proposes a method for clustered federated learning under a mixed regression setting. At its core, the paper explains the method (dividing it into an initial estimation phase and a fine-tuning phase) and gives convergence guarantees about the statistical error of incurred by the method. The theoretical proofs are the bulk of the paper's contribution, and involve eigengap-free bounds on subspace estimation and VC dimension analyses of certain classes of polynomials.
strengths_and_weaknesses: ## Core Strengths

The core contribution of the paper (as it is claimed in the paper) is novel and exciting: Rigorous guarantees on clustered federated learning are few and far between, and I believe that trying to attain this is a significant strength of the paper. Moreover, I think the authors do a good job of motivating this type of approach and giving a rigorous taxonomy of the related literature.

At a high level, I believe that the paper's theoretical results are significant and enough to warrant acceptance. It is clear that there is a lot of interesting facets to the analysis, and the authors mainly do a good job of blending together a variety of disparate analytical viewpoints. In particular, the strategy outlined to prove Theorems 1 & 2 seems promising and mainly correct. I have not verified every detail though, but the portions I have looked at all seem correct. In particular, I especially appreciated the application of the Milnor-Thom theorem (though there is a slight, fixable issue with that, see the suggestions below).

## Weaknesses

The biggest weakness of the paper (and the method proposed by the authors more generally) is its questionable pertinence to federated learning. In particular, as the authors state in their "Broad Impact" section, one of the primary tenets of federated learning is the ability to perform machine learning without compromising data privacy. In the original FedAvg paper, for example, the models trained by clients are never shared directly with one another or the server, but are instead all averaged together (which paves the way for things like differential privacy and secure aggregation, which have formal privacy guarantees).

However, Algorithm 1 repeatedly sends models that are held by a client (specifically an anchor client) to many other clients. While this is not the same as broadcasting data directly, it seems questionable as to whether this method is preserving data privacy. This is particularly concerning due to the linear structure of the problem, where clients could conceivably use an anchor client's model to learn about the client's data. Note that I do not believe that all FL algorithms need to incorporate privacy from the start. However, I think that a lack of any reasonable pathway to privacy integration is a drawback to a method that should be discussed and considered. As a naive reference point, an algorithm that had clients send all their data directly to one another would be effectively useless as an FL method.

This is all to say that I believe that the paper should 1) be up front about what kind of privacy model it is actually envisioning and 2) discuss possible pathways to improving the privacy of the algorithm (if there are any). If the authors believe that broadcasting cluster model estimates (as in Algorithm 1, Line 9) directly to other clients is acceptable, then I believe that this warrants discussion.

A more minor weakness of the work is that some of the notation becomes cumbersome, and relies on quantities/assumptions that could use extra explanation. For example, Theorem 2 makes an assumption on the "clustering error" term $\nu$ (namely, k$\nu\log(e/\nu) \leq \rho/\kappa$). It is not immediately clear how strong or weak this assumption is. If I understand correctly, then this actually imposes a restriction on the dimension $d$, which seems like an important thing to note.

## Summary

I think this is a theoretically strong paper that studies an important topic in federated learning. However, I would prefer that the authors are more up front about the actual privacy model underlying their method, and whether or not that has a pathway to integration with privacy mechanisms like differential privacy or secure aggregation.

### Review Score

I have opted to only give the work a weak accept (6) at the time of writing this review. While I believe the theory is strong, this score is tied to the privacy concerns above. I would be happy to revisit this score, contingent upon the work including a useful, grounded discussion of the privacy risks of the method and potential pathways forward.


# Concerning the Author Feedback and Discussion

This section has been added after reading the other reviews and author feedback. The authors have addressed my feedback well, and have even gone so far as to add entirely new experiments (as per the request of another reviewer). I do not believe that these were necessary for the purposes of acceptance, but cement my belief that this paper should be accepted. I have increased my score from a 6 to a 7 correspondingly.
questions: 1. The application of the Milnor-Thom theorem in the proof of Lemma 10 is not quite correct. The bound quoted on the number of sign patterns in L684 of the appendix is only valid if $m(k-1) \geq dk$. However, if this does not hold then the resulting bound on $m$ follows anyways, so the lemma is still true. However, this is worth cleaning up.

2. The assumption that $\phi(x_{ij})$ is sub-Gaussian means that the assumption that $\phi(\cdot)$ can be a non-linear mapping is not particularly useful, and simply adds unnecessary notation. I think the paper would be clearer if $\phi$ was omitted altogether, and the authors assume a mixed linear regression setting with sub-Gaussian data.

3. Intuitively, what does the bound on $\nu$ in the assumptions of Theorem 1 impose?
limitations: There are no negative societal impacts of the work. My only concern is whether or not the method proposed can be made private (in some formal notion) and this is discussed above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the mixture linear regression problem under the federated learning setting. One major contribution is that the paper studies the situation where when clients’ local data volume is highly unbalanced. The authors introduce a two-phase estimation procedure. The Phase 1 aims to estimate the parameters of anchor clients (clients with large data volume), and the Phase 2 then gets the estimations of all clients by using the anchor clients’ estimation results obtained from the Phase 1. Theoretical guarantees are developed to support their methodologies.
strengths_and_weaknesses: Originality: The method and theory are both novel to me. Typically, in Phase 1, the author utilizes clients with low data volume to help reduce the sample complexity of estimating the parameters of anchor clients, which is clever. Besides, the theoretical results are highly nontrivial.

Quality: The mythology and theoretical analysis are in good quality. Especially, the development of the theoretical results is highly nontrivial. However, I am not familiar with relevant literature on mixture linear regression, thus I cannot judge the significance of the contribution made by the paper on theoretical perspectives. 

One major concern, however, is that there is no experiment in the paper. Given that the paper is proposing new algorithms, it is not ideal to miss the empirical evidence. I understand that the main contribution of the paper is on theory; but I personally think that empirical evidence is still necessary.

Clarity: The paper is in general clear. I can follow the main ideas of the paper. However, I think there should be more discussion on the motivation of the design of Federated Moment Descent (FedMD) algorithm. The current description is not clear enough for me to follow easily.

Significance: Both methodologies and theories are significant. However, the lack of experiments hurts the significance of the paper in all.
questions: May the authors propose some experimental design to justify their algorithms?
limitations: The authors have adequately addressed the limitation concerns.
review_title: null

Meta-review: metareview: This is mainly a theoretical piece of work studying the problem of clustered federated learning under a mixed regression setting. The authors establish convergence guarantees related to the statistical error incurred by the method; the results include eigengap-free bounds on subspace estimation and VC dimension analyses of certain classes of polynomials.

The reviewers highlighted many positive attributes of the work, including:

- The core contribution of the paper (as it is claimed in the paper) is novel and exciting: Rigorous guarantees on clustered federated learning are few and far between, and I believe that trying to attain this is a significant strength of the paper. 
- I think the authors do a good job of motivating this type of approach and giving a rigorous taxonomy of the related literature.
- At a high level, I believe that the paper's theoretical results are significant and enough to warrant acceptance. It is clear that there is a lot of interesting facets to the analysis, and the authors mainly do a good job of blending together a variety of disparate analytical viewpoints. In particular, the strategy outlined to prove Theorems 1 & 2 seems promising and mainly correct. I have not verified every detail though, but the portions I have looked at all seem correct. In particular, I especially appreciated the application of the Milnor-Thom theorem (though there is a slight, fixable issue with that, see the suggestions below).
- I think this is a theoretically strong paper that studies an important topic in federated learning.
- The method and theory are both novel to me. Typically, in Phase 1, the authors utilize clients with low data volume to help reduce the sample complexity of estimating the parameters of anchor clients, which is clever. Besides, the theoretical results are highly nontrivial.
- The methodology and theoretical analysis are of good quality. Especially, the development of the theoretical results is highly nontrivial. 
- The paper is in general clear. I can follow the main ideas of the paper. 
- Both methodologies and theories are significant. 

Besides these words of praise, some criticism was mentioned. The remaining criticism (after rebuttal and discussion) was not very major, however. **I therefore, and with pleasure, propose to accept this paper.** I would wish to stress that it is important to properly address all issues in the camera-ready version of the paper.

Best regards,

AC
confidence: Certain
Decision: Accept