Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence performance of FedAvg for training (pyramidal topology) overparameterized deep networks. Specifically, under certain assumptions, the authors design a special initialization strategy for FedAvg and prove linear convergence rate of FedAvg on training such overparameterized models without making assumptions on data heterogeneity. The authors also provide experimental results on MNIST and CIFAR10 under different data heterogeneous settings to study the effect of model size in FedAvg training.
strength_and_weaknesses: Strength:

1. Given FedAvg is a widely used algorithm in FL and the interpolation regime is an interesting regime in FL. Built on the previous results on overparameterized models with pyramidal topology [NM2020], this paper makes important contributions to provide linear convergence rates of FedAvg in this setting.

2. The theoretical results are derived without assuming heterogeneity conditions.

Weaknesses:

1. The setup of experiments in Section 5 do not align with the theoretical results. I agree it is interesting to investigate the convergence performance of FedAvg under the settings in Sec 5. I would like to see the empirical performance of FedAvg with the specified initialization strategy for solving a problem where all the assumptions (network architecture and activation), which could better corroborate the theoretical results. Moreover, this could be helpful for examining the tightness of the convergence analysis (e.g., the theoretical linear convergence rate v.s. the actual linear convergence rate).

2. [minor] The non-iid setting considered in Sec 5 is not very challenging, it might be interesting to study the performance of FedAvg under more extreme data heterogeneity conditions, e.g., settings in Table III in [LDC+2021].

Questions:

1. The training loss is pretty large in Figure 2 and Figure 3, is the training loss in those plot the summed loss or averaged loss? Also, it might be helpful to visualize the training loss in log scale to study the linear convergence of FedAvg.


References

[NM2020] Global convergence of deep networks with one wide layer followed by pyramidal topology. Q. Nguyen and M. Mondelli. NeurIPS 2020.

[LDC+2021] Federated Learning on Non-IID Data Silos: An Experimental Study. Qinbin Li, Yiqun Diao, Quan Chen, Bingsheng He. https://arxiv.org/abs/2102.02079. 
clarity,_quality,_novelty_and_reproducibility: (Clarity) This work is well presented.

(Quality) High quality work, makes important contributions.

(Novelty) Novel.

(Reproducibility) Good.


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

Typo: In Remark 1, 'Assumption 2 is required to establish a PL like property' -> 'Assumption 3 is required to establish a PL like property'.
summary_of_the_review: This paper studies an important problem in FL optimization (convergence rate of FedAvg under overparameterized regime) and obtains interesting theoretical results, I would recommend acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of federated learning when optimizing with overparameterized multi-layer neural networks. More specifically, the author shows that with a specialized initialization, FedAvg has a linear convergence rate when solving the federated learning problem with overparameterized multi-layer neural networks.
strength_and_weaknesses: The strength of the paper:
1. It shows a linear convergence rate of FedAvg under certain conditions.
2. Experiments validate the effectiveness of theoretical guarantees.

The Weaknesses of the paper:
1. The presentation is not clear. There are lots of unclear definitions, which makes the paper hard to follow. (see detailed comments in next section)
2. Assumption 3 seems to be a strong assumption on the activation functions. What are specific examples of this kind of activation function?
3. It is unclear whether FedAvg is better than the naive mini-batch SGD baseline in this setting. For example, if we do not perform local updates and instead compute $r$ stochastic gradients at the same point and send the mini-batch gradients to the server and then update the model, whether FedAvg can outperform this mini-batch SGD baseline? According to Lemma 1, such a procedure can reduce $\rho$, and it will also avoid the error introduced by local updates as in Lemma 2.
4. The paper only shows the convergence guarantee of FedAvg. Therefore, it is unclear the generalization performance of FedAvg using overparameterized multi-layer neural networks. Note that most of the existing works consider a stochastic problem, and thus their convergence guarantees of FedAvg can serve as the generalization guarantees.
clarity,_quality,_novelty_and_reproducibility: The presentation of the current work needs to be improved:
1. In equations (2) and (3), what is the dimension of $W_l$ and $\theta$? In addition, what do you mean by $f_{L,k}(\theta)$? Do you mean is a function of just the output is dependent on $\theta$? Why do you have $F$ norm in equation (3)?
2. In definition 1, change $x$ to $\theta$.
3. Regarding Assumption 2, is the requirement for each client's model or the stacked model?
4. Why the condition in (7) depends on both $\theta_1$ and $\theta_2$ instead of just $\theta$?
5. There are lots of works that also make no assumptions on the data heterogeneity, e.g., Karimireddy 2020b, the authors should also discuss it.
summary_of_the_review: The problem, i.e., how the overparameterization will affect the performance of FedAvg, considered in this paper seems to be interesting. However, the results provided in the current paper are not strong enough. The main question I have is whether the FedAvg can outperform the naive mini-batch baseline in this setting. In addition, what is the generalization guarantee of the proposed method?
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proves under certain assumptions, FedAvg can converge linearly to the optimal solution even under heterogeneous clients. The convergence relies on specific network architectures and parameter initialization.
strength_and_weaknesses: Strength:
1. A global and linear convergence result for FedAvg. In this sense, the result is new and interesting.

Weakness:
1. Compared with the result for centralized training (Nguyen and Mondelli, 2020), the technical contribution of this paper is questionable. The network architecture, the initialization, as well as most of the proof, are from Nguyen and Mondelli (2020). While in Remark 5, the technical novelty compared with it is discussed, either extending to federated training or dealing with stochastic gradient is not significant or novel enough.

2. The analysis of federated training is likely to be superficial or unrealistic in that, the total update length within each communication round, decreases as the local training steps increases. In particular, the step size $\eta \asymp A^{-r}$ ($A > 1$) where $r$ is the number of local steps so in total, $\eta r$ decreases exponentially. For one thing, this is never the real world case. Usually, each local client will train for several steps with constant step size and then aggregate on the server side. More locally training steps makes the averaging step harder, while in this paper's configuration, more local steps mean the total change of the parameter becomes even smaller, thus averaging also become easier. This lead to the theoretical aspect: this kind of configuration makes the total local updates within $r$ steps so small, that the first-order approximation is precise enough. This makes the $r$-step update FedAvg no harder than the $1$-step update FedSGD. It is then trivial to show that FedSGD indeed can handle arbitrary heterogeneity in the clients.

3. The presentation needs further polishing. I found several typos and notation inconsistencies in the equations. 
clarity,_quality,_novelty_and_reproducibility: The paper should provide a more clear discussion on what is the technical contribution compared with previous works, Nguyen and Mondelli (2020). Currently, I have the impression that many contents in this paper highly overlap that of Nguyen and Mondelli (2020), including the network architecture, the initialization, and part of the proof. 

The key weakness of the FedAvg setting is that the learning rate is set so that more local steps make the first-order approximation easier rather than harder. Thus the key difficulty of analyzing FedAvg, namely the averaging part, is circumvented. I think to make the analysis meaningful or significant enough, at least the total update $\eta \cdot r$ should be of the order constant.

Along with Nguyen and Mondelli (2020), the significance or novelty of these results is questionable.

summary_of_the_review: Due to the lack of technical novelty, I recommend rejection.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes an interesting solution for overcoming the data heterogeneity of FedAvg algorithm. The theoretical result indicates that for a specific structure of neural network, FedAvg can achieve nearly zero loss at a linear convergence rate without making any additional assumptions on data distribution. The empirical result further validates this result. 
strength_and_weaknesses: ***Strength***
* It is the first convergence analysis of FedAvg over multi-layer neural network. And it is interesting to see it achieves linear convergence rate without additional requirements on data distribution.  

***Weaknesses***
* I feel that the linear convergence of overparameterized model in the federated learning scenario is trivial. See the following two references. The data heterogeneity is characterized by the gap between global minimum and average of client minimum [Li2019] or the gradient noise at the global minimizer [Khaled2019]. For overparameterized model, both of those value are zero. It generally says that for overparameterized model there is no "data heterogeneity". I would be expecting to hear how data heterogeneity is defined in this paper and how it is different from those existing definitions. 

*[Li2019] Li, X., Huang, K., Yang, W., Wang, S., & Zhang, Z. (2019, September). On the Convergence of FedAvg on Non-IID Data. In International Conference on Learning Representations.*

*[Khaled2019] Khaled, A., Mishchenko, K., & Richtárik, P. (2019). First analysis of local gd on heterogeneous data. arXiv preprint arXiv:1909.04715.*


* I agree that Theorem 1 indicates that FedAvg-SG attains a linear rate. But according to Remark 8 in the appendix, it appears that the choice of learning rate is very sensitive, it must be of the order $\Theta(\epsilon^2)$. If it is smaller, for example, $\eta =  \Theta(\epsilon^3)$, then the rate cannot be linear; and if $\eta =  \Theta(\epsilon)$, the convergence is not guaranteed. I don't think this result is satisfactory. For other research on overparameterized models, the following two references [Du2018] and [Ma2018] show the linear convergence rate can be achieved with a step size independent w.r.t. $\epsilon$. It is not clearly clarified in this paper why there is such uncommon constraints on the learning rate.

*[Du2018] Du, S. S., Zhai, X., Poczos, B., & Singh, A. (2018). Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054.*

*[Ma2018] Ma, S., Bassily, R., & Belkin, M. (2018, July). The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In International Conference on Machine Learning (pp. 3325-3334). PMLR.* 


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

Updates after Rebuttal:

I have read other reviews and the author's responses. I still tend to reject this paper. (1) As stated by the author in the rebuttal, this work uses a different definition of the data heterogeneity from [Li2019] and [Khaled2019]. So I don't think this result solves the standard heterogeneity issue in the federated learning. (2) Also, compared to prior over-parameterized model studies, this paper has non-standard constraints on the learning rate. I agree that multiple local updates will make -level learning rate invalid but it makes this paper meaningless: I can always run one-step local update at each edge device with a constant learning rate then applying [Du2018] and [Ma2018] to standard SGD with mini-batches; it also has a linear convergence rate. (3) Besides both above, I agree with Reviewer Er5f: there exists solid theoretical results showing that the minibatch SGD is always not worse than the federated averaging approach, so the motivation of sololy studying FedAvg is weak.
clarity,_quality,_novelty_and_reproducibility: This paper has high quality regarding its writing: it clearly defines every symbol, which is not easy especially when notations are very complicated; and there is an easy-to-understand proof sketch. But the contribution of this work might be limited as described in the weakness section. 
summary_of_the_review: This paper fills in the blank of applying overparameterized model to FedAvg algorithms and achieves the expected result: linear convergence rate. But I have two major concerns: (1) the unclear definition of data heterogeneity; this paper may fall into an existing scoop of federated learning research. (2) the uncommon constraint on the step size; the theoretical result doesn't match some existing overparameterized models research.  From these two reasons, I tend to reject.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: - Summary:

This paper studies the convergence performance of FedAvg for training (pyramidal topology) overparameterized deep networks. Specifically, under certain assumptions, the authors design a special initialization strategy for FedAvg and prove linear convergence rate of FedAvg on training such overparameterized models without making assumptions on data heterogeneity. The authors also provide experimental results on MNIST and CIFAR10 under different data heterogeneous settings to study the effect of model size in FedAvg training.

- Strengths
Findings of the paper include:
1. The paper makes contributions to provide linear convergence rates of FedAvg in the specific case considered in the paper (assuming heterogeneity assumptions).

- Weaknesses
1. Despite the response, Assumption 3 seems to be a strong assumption on the activation functions. The authors should consider dropping such an assumption to follow what the majority of literature assumes. 
2. Compared to previous results, extensions to stochastic cases vs full gradient steps might not be sufficient for acceptance, unless a new theoretical technique / proof difficulties emerge. E.g., it would be better if the authors were explaining better the difficulty of applying these changes and what new comes out of this proof technique. 
3. The use of heterogeneity in the paper is questioned how is different than existing works and how it adds to the difficulty of the task.

- What would be missing:
Overall, the authors could/should consider:
1. Dropping/"smoothing" proof-enabling assumptions
2. Make explicit statements + contributions how this theoretical extension is significantly different/more challenging than existing work.
3. This extends to the case of heterogeneity in the problem definition: reviewers still believe that clarification is needed whether this is significantly different case than existing works

justification_for_why_not_higher_score: For the weakness points mentioned above.
Decision: Reject