Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the personalized federated learning and makes a few contributions. First, it proves an information-theoretic lower bound on the sample complexity. Second, it proposes an all-for-one algorithm that matches the lower bound but needs a high communication cost for broadcasting stochastic gradients between agents. Third, it further proposes a communication-efficient all-for-all algorithm via the gradient-filtering method. 
strengths_and_weaknesses: originality: theoretical contributions to FL. It leverages the distribution-based distance to analyze the sample complexity.

quality: technical depth looks sufficient.  

clarity: good except that it is unclear how the analysis differs from existing works that is closest to this work.

significance: gradient filtering seems to be a good technique for both communication reduction and personalization promotion.


questions: In Line 179, how does the factor epsilon/4 come?

In Line 203, large epsilon?
limitations: see above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the sample complexity of personalized federated learning with a large number of users (each holding a few samples). The authors investigate the benefit of collaborative learning via stochastic gradient descent in terms of distribution biases, noise variance, and regularity of function classes (strongly convex and smooth optimization). Based on known distances between local distributions, the authors propose a lower bound on the sample complexity of all users in order to minimize the generalization error of one user. They also present the All-For-One algorithm, which achieves the linear speedup shown in the lower bound and propose a second modified algorithm to address the communication and computation costs associated with this method.
strengths_and_weaknesses: The mathematics in this paper appear to be correct, and the topic is interesting. The organization and writing of this paper are generally very good. Moreover, the authors have provided an experimental result to support their theoretical findings. A limitation of this study is that it does not compare with seminal work on personalized federated learning. A comparison of the two proposed algorithms (All-For-One and All-For-All) has not been conducted with other techniques for personalization.
questions: .
limitations: .
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 studies the issue of personalization in federated learning - a very timely topic. While several works have introduced a variety of techniques (e.g., clustering, representation learning, MAML, etc.,) to promote personalization in FL, this paper takes a different approach. It explores the idea of aggregating gradients by carefully adjusting the weights of such aggregation based on pairwise client similarities. An information-theoretic lower bound is established that reveals how much a client participating in the FL process can hope to benefit from collaboration. Furthermore, it is shown that the weighted aggregation scheme can achieve such a lower bound. 


strengths_and_weaknesses: Overall, I think this is a very well-written paper. I summarize my main comments below.

*Strengths* 
- The main contribution of the paper, in my opinion, is Theorem 1. It is very informative in that it reveals how much a client can reduce its local generalization error by using the data from other "similar" clients. In this context, the notions of similarity introduced in Assumption 3 are both novel and intuitive. 

-  The All-For-All algorithm achieves the lower bound in Theorem 1 by employing a filtering protocol - while updating its model via gradient aggregation, a client only uses the gradients of other clients that are close to it in a suitable sense. As a result, the weight matrix $W$ used in the aggregation rule is no longer a standard Markov matrix used for studying consensus/distributed optimization. This makes the analysis of the algorithm a bit different from the standard analyses. 

One key point to note here is that the algorithm assumes prior knowledge of the client similarity indices, which can be very prohibitive in practice. Fortunately, in Section 6, the authors show how one can use a small number of samples initially to figure out such similarity indices and accordingly cluster the agents. 

Coupled with the fundamental limit in Theorem 1, the All-For-All algorithm and the initial similarity-index estimation protocol in Section 6 lead to a strong theoretical contribution. I do have a few clarifying comments that are outlined below.

*Comments*

- Other than being a conceptual tool, is there any practical utility of the All-For-One Algorithm? In particular, in addition to the stringent communication overhead it imposes, it seems that at each round, every client needs to evaluate the gradient of its loss function at the models of *all* clients. This is in stark contrast to existing FL algorithms, where every client computes gradients at just its own model/iterate. As such, the All-For-One algorithm seems to require significantly more oracle calls than standard FL algorithms. Is this a fair assessment?

- The approach outlined in Section 6 seems to be valid for simple quadratic loss functions. This is fine for now as it lends some credibility to the overall approach proposed in this paper. But is there hope that the results in Section 6 can be generalized beyond quadratic losses? 

- At the end of the day, the overall technique boils down to clustering clients initially, and running a parallel gradient descent algorithm within each cluster; the benefits of collaboration are then limited to each cluster. In this sense, I am curious to know how this high-level idea compares with some other well-established clustering-based methods in FL. See, for instance, ref [R1] below.

[R0] *An Efficient Framework for Clustered Federated Learning*, Ghosh et al.., NeurIPS 20.

In [R0], the authors develop a strategy that involves alternatively refining the cluster identities and solving the supervised learning problem. That is, the clustering and learning processes are interleaved, as opposed to the hierarchical approach suggested in the current work. I would like the authors to comment on this further.

- The aspect of personalization stems from the fact that the data-generating distributions of the clients are non-identical in practice, leading to loss functions with different minima (indeed, if all clients saw data from identical distributions, the global model would also serve well as a personalized model). As such, a very rich body of work has explored the angle of objective/statistical heterogeneity, improving our understanding of this fundamental challenge in the context of FL. However, the authors in this paper completely ignore this line of work, which I find unsatisfactory. I would like to see a better representation (and discussion) of this literature in the authors' related work section. Some notable papers in this regard are mentioned below, but this is by no means an exhaustive list.

[R1] *Tighter Theory for Local SGD on Identical and Heterogeneous Data*, Mischenko et al., AISTATS 20.

[R2] *SCAFFOLD: Stochastic Controlled Averaging for Federated Learning*, Karimireddy et al., ICML 20.

[R3] *Minibatch vs local sgd for heterogeneous distributed learning*, Woodworth et al., NeurIPS 20.

[R4] *FedSplit: An algorithmic framework for fast federated optimization*, Pathak and Wainwright, NeurIPS 20.

[R5] *Convergence and accuracy trade-offs in federated learning and meta-learning*, Charles and Konecny, AISTATS 21.

[R6] *Federated Learning Based on Dynamic Regularization*, Acar et al., ICLR 21.

[R7] *Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients*, Mitra et al., NeurIPS 21.

[R8] *Local SGD: Unified Theory and New Efficient Methods*, Gorbunov et al., AISTATS 21.


questions: I don't have any questions beyond the clarifying comments I raised earlier.
limitations: I don't foresee any negative societal impacts of this work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper shows an information-theoretic lower bound on the number of oracle calls for collaborative training on clients. Two optimal collaborative training algorithms (gradient filtering algorithms) are proposed, and convergence rates are presented. 
strengths_and_weaknesses: Strengths. The paper develops a strong theory proving a lower bound on the sample complexity and proposing algorithms with matching upper bounds. 

Weaknesses. The limited experimental support of the theory.
questions: The paper in several sections is out of my area of expertise. My questions are as follows:

1. Theorem 2: given $\lambda_{ij} \geq 0$ and they sum up to 1, the 3rd term in the right-hand side of the inequality is lower bounded by $a_i := min_j \frac{b_{ij}^2}{\mu}$. The first two terms are at least zero. Does the theorem allow $\varepsilon$ to be less than $a_i$?

2. Why should the matrix $W$ in the equation between lines 53 and 54 be symmetric?
limitations: Limited experiments.
review_title: null

Meta-review: metareview: This paper addresses an important issue related to sample complexities for a personalized federated learning (PFL) problem. Its focus is on the case where a large number of agents collaborate to train the PFL problem, and each agent can have local data from a slightly different data distribution.
Author(s) provide both the lower and upper bound on the number of samples needed in order to achieve their goals. They also discuss techniques that allow for achieving an optimal bias-variance trade-off.

Note: please try to incorporate the suggestions and discussions into the camera-ready version.
confidence: Less certain
Decision: Accept