Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a framework for federated learning with non-iid data. The authors tackle this problem by optimizing Gradient Signal to Noise Ratio (GSNR). They decompose local gradients calculated on the non-iid training data into the signal and noise components and then speed up the model convergence by maximizing GSNR. Based on this, they develop the FedGSNR method, which can be applied to existing gradient calculation algorithms. 

strength_and_weaknesses: The proposed framework is general and seems to be applied to various existing methods. The non-iid data issue is important in this fields, and the authors address the problem well. Unfortunately, I am not familiar to this topic. Therefore, I cannot assess the exact strength and weakness of the proposed framework. I read the paper and could not find significant faults. 
clarity,_quality,_novelty_and_reproducibility: In Lemma 3.2: When the samples are significantly non-iid, we cannot apply the CLT in general. However, the authors apply the CLT to show Lemma 3.2. Could you explain why it is possible? In addition, I think that the statement should be "$\sqrt{B}(g - \mathbb{E}[g])$ converges to a multivariate normal distribution as $B\to \infty$,"  and the authors should clarify that what CLT theorem they used in the proof.
summary_of_the_review: The paper is well-written, although I could not evaluate it with confidence. However, there are several parts where theoretical explanation is insufficient. For example, the authors define the expected value in Section 2, but because the data is non-iid, we can consider samples that do not have the expectation. The authors more carefully discuss them because this paper discusses non-iid data. Furthermore, I could not understand why Lemma 3.2 holds. I would like the authors to clarify it.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors investigate the possibility of optimizing a number of local steps in the FedAvg algorithm by minimizing the Wasserstein Distance between global and local gradient distributions.
strength_and_weaknesses: The paper provides a nice and (as far as I know) novel idea of how to use the statistical properties of local datasets in order to optimize the optimization procedure of the distribution problem.
However, I believe that the paper is too empirical and contains the following problems:

Major:
1. The paper does not provide convergence rate comparisons of the new method and FedAvg (see https://arxiv.org/pdf/1910.06378.pdf). It is not enough to say "The convergence of FedGSNR is obvious, as we just change the number of local updates." I believe that it is not a trivial task to obtain precise convergence rates for the new method.
2. Lemma 3.4 and the discussion implies that we can estimate $\eta_r \widehat{g}$ with $\eta_r \bar{g}$ if $\eta_r \approx 0.$ I think that it is not a strong result and probably misleading. This result virtually holds for any two random vectors, not only for gradients. In practice, we want to take $\eta_r$ as big as possible. Moreover, the smaller $\eta_r$, the worse we get the convergence rate.
3. In the proof of Theorem 3.5, the authors say: "the global gradient distribution can be approximately interpreted as normal distribution." It is a very weak argument for the main theorem of the paper. I would like to see more rigorous mathematical calculations.
4. Theoretically, it is not clear how the maximization GSNR is connected to faster convergence. For instance, is it possible to show that we can guarantee the convergence rate faster than the vanilla FedAvg if we maximize GSNR?

Minor:
1. In order to calculate $n^{opt},$ the method required the global $\mu_g$ and $\Sigma_g$ and local $\mu_l$ and $\Sigma_l.$ The authors propose to estimate them using sampling. It would be nice to have an alternative to Theorem 3.5.
2. How does the formula in (7) depends on $r$?
3. In order to estimate $\Sigma_g$ or $\Sigma_l$, would the method require a large batch size?


clarity,_quality,_novelty_and_reproducibility: -
summary_of_the_review: While the idea of the paper is nice, the theory seems to be weak (see Strength And Weaknesses).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In Federated Learning with heterogeneous data, the gradient of each client is pointing in a different direction when running a local algorithm s.t. local SGD. Since each client performs several local steps, the algorithm deviates from the theoretically better algorithm that would follow the averaged direction of the gradients. 

This paper proposes a technique to reduce this deviation effect and speedup the training algorithm. Based on the Gradient Signal to Noise Ratio, they compute the "optimal" number of local steps to reduce the deviation effect. In particular, the number of local steps is not the same for every client.

The approach relies on making some gaussian approximation for the local training and the global training, computing the Wasserstein distance for the deviation between both and computing the number of local steps to minimize the deviation.
strength_and_weaknesses: Strength

- The approach to compute the optimal number of local updates is original and flexible, can be applied to virtually any local optimization algorithm

-The method allows for a different number of local updates for each client, and allows for measuring the contribution of each client

Weaknesses

-GSNR is computed on the basis of several approximations. We don't know how far is the estimated optimal number of local updates from the true optimal number of local updates. In general, the fact that the approach is based on several approximations is really not discussed

-The goal of the GSNR approach is to accelerate the training. Acceleration is only shown experimentally
clarity,_quality,_novelty_and_reproducibility: Clarity and quality:

I enjoyed the overall story of the paper, but when I tried to check the details I was bothered by some clarity issues.

Is Lemma 3.4 saying that running gradient descent is equivalent to running gradient descent without updating the gradient? This approximation seems too crude to give a good approximation of the optimal number of local steps. Besides, I would have expected the optimal number of local steps to be just one (since the communication constraint is not encoded in the GSNR)? 

In Eq 5, p_w are not defined. It is not clear what this equation means.

Th 3.5. is the main theorem, but its statement is really confusing. The optimal number of local updates is not mathematically defined. What is the criterion to be optimized (I needed to check the proof to understand)? Are there constraints? Same for the optimal distance (here it is also not clear what "distance" refers to). I suggest putting the proof of Th 3.5 in the main text. 

Finally, these optimal numbers are obtained after making several approximations: CLT, Lemma 3.4. This is not recalled, nor discussed. 

The GSNR appears only in page 7, after it is used to compute the optimal number of local steps. Wy this choice? This is confusing. Moreover, in the current form, Section 2.2 seems useless because it is not related to the rest of the paper (only implicitly for the proof of Th 3.5), am I correct?


Experiments show the flexibility of the approach to evaluate local contribution, this is an interesting feature of the approach. They also check the test accuracy, justify the necessity of optimal local steps and obtain a convergence speedup. There are some experiments for justification of local steps, but I am not sure to understand what the outcome of this experiment is. However, they do show model convergence speedup.  

Novelty:

The idea of monitoring the deviation between local and global training is original. I believe that it could give good results in practice.

summary_of_the_review: The idea is original but not well executed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In Strength And Weaknesses
strength_and_weaknesses: This paper speedups model training by maximizing GSNR in FL and provides the optimal local updates from a theoretical viewpoint. However, I'm not an expert in FL and have a heavy review load. Due to my limited time, I can't be more positive at the current stage. I encourage the authors pay more attention on other reviewers' responses as I will make my confidence the lowest.

Though I'm not an expert in FL but I find the theoretical results in Sec 3 are interesting. Thus, I will only give some comments and ask some questions about this part. My questions may be highly biased due to I didn't go through all details in the paper. I would be glad if the authors could point out my misunderstandings.

1. About the upper bound Eqn (6). Why is the target distance (5) approximately minimized when the upper bound is minimized? There might be a gap. It would be better if the authors provide a simple example to verify its possibility in the current setting.
2. I'm confused by Lemma 3.2 and Lemma 3.4. It seems Lemma 3.4 is to calculate the asymptotic mean and variance by initial weight $w_1$. And the step size goes infinity. But Lemma 3.2 let the minibatch $B$ goes infinity. Could the author tell me more about how to connect Lemma 3.2 and Lemma 3.4 with different asymptotic parameters ($B$ and $r$)?


clarity,_quality,_novelty_and_reproducibility: In Strength And Weaknesses
summary_of_the_review: In Strength And Weaknesses
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors investigate the possibility of optimizing the # of local steps in FedAvg by minimizing the Wasserstein Distance between the global and local gradient distributions. The main idea of the work seems to be novel.

The work strings together a number of heuristic arguments presented as rigorous mathematical results. Some reviewers criticized the insufficient rigor, and I agree with this criticism. This alone is highly problematic, and is a reason for rejection. If the paper is of an empirical nature, it should be written as such, and the heuristic thinking that lead to the development of the method should have been clearly presented as such.

There are prior works that optimize  # of local steps in a mathematical rigorous manner (e.g., the ProxSkip method of Mishchenko et al, ICML 2022) which have not been discussed.

Some reviewers suggested borderline acceptance. However, both of these reviewers were not confident in his/her evaluation (confidence 1 and 2). I have read these reviews; and do not see sufficient reasoning/evidence to warrant acceptance.



justification_for_why_not_higher_score: Wrong and misleading mathematical statements
Decision: Reject