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: Motivated by the empirical success of Federated Averaging to generalize to new tasks (after fine-tuning), this paper seeks to connect this empirical success with a theoretical argument for how well FedAvg is capable of learning good representations, which is not an explicit objective of the optimization. Theoretical guarantees are presented for a multi-task linear regression setting and further empirical results demonstrate the effectiveness of learning representations with image classification tasks.
strengths_and_weaknesses: ### Strengths
- The paper is extremely well written and well organized. The mathematical notation is clearly described and easy to follow. 
- The theoretical results are well presented, with clear assumptions and, at each steps, the assumptions and statements are described in an intuitive way.
- While the result under study (effectiveness of FedAvg for Representation Learning) has been shown (empirically) before, the formalization is an original contribution
- The experiments are well described and effective at supporting the main theoretical claims

### Weaknesses
- The paper ends abruptly. It would be nice to have a conclusion section to tie up the paper. Perhaps some of the problem setting and notation could be abbreviated or moved to the appendix.
- The main result is proved in simplified setting (linear regression tasks), which is far from the usual application of FedAvg for deep learning
questions: While much of the empirical success of FedAvg was discussed in the paper, I would appreciate a discussion of related work that specifically addresses the representation learning aspect [1,2] or extensions that aim to improve the personalization aspect [3] and how they fit with the assumptions and insights provided by this paper's theoretical analysis.

[1]: Zhuang, W., Gan, X., Wen, Y., Zhang, S., & Yi, S. (2021). Collaborative unsupervised visual representation learning from decentralized data. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 4912-4921).

[2]: Li, Q., He, B., & Song, D. (2021). Model-contrastive federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 10713-10722).

[3]: Hahn, S. J., Jeong, M., & Lee, J. (2021). Connecting Low-Loss Subspace for Personalized Federated Learning. arXiv preprint arXiv:2109.07628.
limitations: The paper adequately addresses its 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 work shows that FedAvg learns better representations than Distributed SGD; with a largely theoretical contribution, and some well executed small-scale empirical results. This paper:
* considers multi-task linear regression in a non-convex setting (i.e., prediction is the composition of a learnable subspace matrix, and a linear head), where the shared component across tasks lives in a low-dimensional subspace. The works shows that FedAvg can regress to the correct concept (given a good initialization), because local client-updates in FedAvg encourage diverse high-rank representations, whereas Distributed SGD finds low-rank representations.
* provide empirical experiments (both linear regression and CNN-based image classification), showing that FedAvg discovers better representations, that generalize better than Distributed SGD.

strengths_and_weaknesses: Originality: Despite the growing literature of work on the role of federated learning in representation learning, this work is very interesting and quite timely. Rather than proposing a new method, the authors provide an analysis explaining why FedAvg can produce more generalizable representations than Distributed SGD.

Quality: Despite minor errors (probably typos in the math), this work is sound.

Clarity: The exposition is clear, although the proof sketches are a little obscure; and cannot be as readily comprehended without going through the proofs themselves.

I am happy to recommend this work for acceptance.
questions: * In related work, please discuss the relation to work in the gossip literature. In general, gossip-algorithm can be seen as a a generalization of Local-GD; e.g., with diminishing step-sizes, Local-SGD with an arbitrary number of local steps converges to a stationary point of the global objective [1,2]. If clients perform a different, and potentially time-varying, number of local-steps, then from [3] we can also see that they will minimize a weighted average of the global objective, and that this can be corrected with knowledge of agents’ local update rates. Moreover, gradient tracking was actually first proposed in the gossip literature (e.g., see [4])

* Error in line 177; wbar_{*,i) with a summation over i^\prime... I believe here you should just have wbar_* without a summation

* On lines 205: if you analyze the sequence produced immediately after each synchronization step, and consider a diminishing step-size, this will converge (e.g., this is can be seen as a special case of Subgradient-Push, with a particular mixing matrix over a \tau-strongly connected graph). The intuition is that the mixing converges at an R-linear rate (much faster than the sublinear rate of optimization with a diminishing step-size).

* It is not clear to me how the method can discover the correct subspace, but not converge to a stationary point of the loss… e.g., after finding the correct subspace, fix B and optimize for w… this is a convex problem. I believe figure 3 supports this intuition, (i.e., the evolution of the loss with and without fine-tuning the head); please clarify this in the exposition.

* From the analysis, one implicit requirement for the diversity of the discovered representation in the proof is that the clients do not overfit to their local objectives, as this would remove energy from other elements in the column-space, not aligned with the local objective, what is the role of \tau in this case? is there an optimal range for the number of local steps?

[1] Nedic and Olshevsky, Distributed optimization over time-varying directed graphs, IEEE TAC 2014.
[2] Assran et al., Stochastic Gradient Push for Distributed Deep Learning, ICML 2019.
[3] Assran and Rabbat, Asynchronous Gradient Push, IEEE TAC 2021.
[4] Xi and Khan, DEXTRA: A fast algorithm for optimization over directed graphs, IEEE TAC 2017.
limitations: Some minor limitations on the analysis should be stated; e.g.,
* The second term in the min condition in theorem 1 can easily be vacuous for any reasonable number of iterations, and thus the theorem requires all clients to participate in each round… this should be made clear in a remark following the theorem. Numerical results in section 5.1 also have all clients participate in each round.
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 provides theoretical analysis of FedAvg with Fine Tuning. When the local model weights for clients lie on a linear subspace, theorem 1 suggests FedAvg gets linear convergence, while proposition 1 suggests Distributed GD may diverge for representation learning. Some empirical results on a toy problem are used to verify the theorem, and results on CIFAR-10 and CIFAR-100 shows FedAvg+FineTune outperforms D-SGD+FineTune.
strengths_and_weaknesses: Strengths
+ FedAvg is one of the most popular algorithms in FL. Though the connection between FedAvg and MAML/Reptile is known, the theoretical justification of the advantage of FedAvg for representation is (to my knowledge) novel. 

Weakness
- The paper can probably improve on clarity. I find it difficult to connect Theorem 1 to the FedAvg algorithm described in Section 2 and the objective eq. (5). 
- As the authors acknowledged, previous work has drawn connections between FedAvg and MAML, and empirically shown FedAvg+FineTune is better than SGD+FineTune. The main contribution of this paper is theoretical, while the assumptions are very strong. 

questions: Like I mentioned,  I find it difficult to connect Theorem 1 to the FedAvg algorithm described in Section 2 and the objective eq. (5).  Specifically, what is the connection between (5) and (7), why do we care about  \|Bw − B∗w∗\|^2 in (7)? 

Could the authors clarify what assumptions of FedAvg, and what assumptions of representation learning are made? 

Related to previous questions, it is not quite clear to me what is the difference between a FL setting and a multi-task/transfer learning setting.  

Could the authors discuss and compare to Adaptive Gradient-Based Meta-Learning Methods https://arxiv.org/pdf/1906.02717.pdf ? I am not an expert on meta-learning/representation learning theory, and this is only one of the papers that also discuss FedAvg. 

limitations: NA
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 analyzes both theoretically and empirically the performances of FedAvg with local fine-tuning as a post-processing step. More precisely, they consider the scenario where the model parameters are split into two distinct parts: a shared backbone model and a personalized head model. This scenario encompasses for instance convolutional neural networks where the backbone model extract high-level features and the head performs prediction. In order to derive theoretical results, the authors restrict their analysis to the linear case where the backbone parameter is a matrix $B \in \mathbb{R}^{d \times k}$ with $k < d$ and $\omega$ is the head.
Their main result is a Theorem showing the generalization power of FedAvg with at least 2 local updates via convergence towards the ground-truth backbone parameter $B_\star$. They validate their theory with experiments.
strengths_and_weaknesses: Overall, the paper is well-written and clear. The related work section acknowledging previous works is sufficient.

My main concerns / remarks are:

* The work by Collins et al. (ICML 2021) on shared representations should be compared more deeply with the proposed analysis since the two setting bear some similarity. Some comparison has been done in the supplement but should appear in the main paper in my opinion.
* How difficult the analysis beyond the linear case is?
questions: See the previous remarks and concerns.
limitations: N/A
review_title: null

Meta-review: metareview: This work provides an analysis explaining why FedAvg can produce more generalizable representations than distributed SGD. Theoretical guarantees are presented for a multi-task linear regression setting and further empirical results demonstrate the effectiveness of learning representations with image classification tasks. The theoretical analysis presented can be an important building block for the study of more complex settings in federated optimization. All reviewers recommend acceptance.

Please take the (few) suggestions by the reviewer into account, and also incorporate the explanations and clarifications provided during the rebuttal in the camera ready version.

confidence: Certain
Decision: Accept