Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a method to improve the server optimization for non-iid settings in federated learning. The proposed method involves using the client gradients to adapt the server learning rate such that similar gradients should have a low learning rate, while dissimilar gradients will have a high server learning rate. The approach builds upon the intuition that similar gradients may correspond to a biased average gradient from similar client distributions, which may not correspond to the global average gradient if all the clients were used. The authors validate their proposal with several baselines on 4 datasets and demonstrate encouraging results.
strength_and_weaknesses: **Strengths**

**S1** The paper addresses a challenging and highly relevant problem in federated learning w/ non-iid client distributions.

**S2** The experiments in the non-iid setting are exhaustive with plenty of ablations. Moreover, the proposed FedGLAD outperforms commonly used baselines such as FedAvg, FedProx and FedAdam in the non-iid federated learning settings.

**S3** The paper is clear and easy to follow, (w/ some exceptions as discussed below).

**Weaknesses**

**W1** The theoretical motivation in section 3.2 and the corresponding claim that FedGLAD can mitigate the inconsistency b/w $g_t$ and $g_c$ doesn't seem solid. The technical motivation is inconsistent with the final method adopted (Please see the review justification).

**W2** I think the idea of using GSI to determine the learning rate is interesting and clever. But with increasing the learning rate for dissimilar client gradients, the method currently assumes that dissimilar gradients can "only" reflect useful global gradient. It seems only using non-iid partitions in the experiments may not reflect other weaknesses of this approach. For e.g. in the noisy federated learning setting [1] gradients will likely be dissimilar due to the noise, and increasing the server learning rate could lead to poor performance.   Another federated learning setting to consider could be the multi-modal non-iid setting in Federated Learning [2]. I think there should at least be a discussion on how FedGLAD would do in these settings. 

**References**

[1] Robust Federated Learning with Noisy Labels, Yang et al. (2020)

[2] Weight Anonymized Factorization for Federated Learning, Hao et al. (2020)
 
clarity,_quality,_novelty_and_reproducibility: **Clarity:** The paper was easy to follow and clear, with a few exceptions in the methods section 3.2 as discussed above.

**Novelty:** I find the idea of using gradient similarity to determine the learning rate to be particularly novel.

**Reproducibility:** The authors have made sufficient efforts to ensure reproducibility.
summary_of_the_review: My main concerns are listed below --

- In equation 8, since $||g_c||$ is considered a constant, the learning rate bound is not particularly unique for Equation 5. This bound will also hold for any constant vector in place of $g_c$, since it will be dropped later? The authors should clarify how the introduced scaling in $g$ can make it closer particularly to $g_c$ (As has been claimed in the third paragraph of section 3.2). 

- The paper also refers to Fig 1 and Fig 2 in section 3.2 to illustrate the motivation of Equation 5. But as discussed above, the GSI-based scaling is not particularly solving equation 5. Again, the claim of mitigating the inconsistency b/w $g_t$ and $g_c$ is not well-supported.

- While the authors motivate the non-iid setting from real-world data, other settings such as noisy labels [1] and client imbalance [2] are not considered. I feel the GSI-based scaling makes strong assumptions that the non-iid setting is the only challenge in the data distributions and the experiments are also designed in this isolated setting. Note that all the other baselines do not strictly make any such assumption. The paper should at least discuss the applicability of FedGLAD in other real-world federated learning settings.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The submission "When to Trust Aggregated Gradients: Addressing Negative Client Sampling in Federated Learning" describes a re-weighting strategy that can be applied during the optimization of ML models in federated learning. Given the full gradient norm over the entire dataset at some point in training, this strategy reweights the gradient norm of every mini-batch sample to be equal. This is combined with a moving average estimation of the full gradient norm, variants with separate rescaling for parameter-groups and dynamic bounds. This approach is evaluated on a range of datasets and models.
strength_and_weaknesses: Overall, I like the experimental evaluation done in Section 4, showing the effect of the proposed modification and the extensive commentary on the experimental evaluation in the appendices and submission of code and supplementary material.

My main point of contention though is with the motivation and derivations from the beginning all the way up to Section 3.2. Fundamentally, the phenomenon that the authors observe, that gradient norms computed over small sample sizes differ from the global gradient norm, is unrelated to federated learning. The same analysis and intuition also applies to normal training with stochastic gradient descent - no connection to FL is necessary. 

The submission then essentially derives and re-analyzes the conditions for the convergence of stochastic gradient descent, where indeed, a popular assumption is that the variance of the norm of sample gradients is bounded. SGD, as summarized for example in Bottou 2010 "Large-Scale Machine Learning with Stochastic Gradient Descent". SGD is generally thought to be close to an optimal algorithm, even when gradient norm variance is non-zero, but subsequent adaptations and variations do exist, for example in the extensive literature on variance-reduction methods for SGD. 

The submission derives the notion of a "gradient similarity-aware indicator" defined as $\mathbb{E}(||g||^2) / ||\mathbb{E}(g)||^2$, based on my re-annotation of Eq.(9) with the gradient $g$ a random variable. Updates are then reweighted based on dividing the current estimate of this quantity with a historical estimate. It is unclear whether this is an actual reduction in effective gradient norm variance, a part where I found have found a proof essential.

Ultimately, I don't believe this motivation makes sense, and it ignores a large body of work on the properties of stochastic gradient descent. The submission adds further wrinkles and complications with a parameter-wise variant and additional hyperparameters in the running average and the running bounds, all of which I'd like to see more carefully ablated, and the overall method potentially works. I can be convinced that the proposed method is empirically useful, based on the empirical evidence provided in Section 4, but I don't find the submitted evidence compelling that this method works for the reasons stated.

clarity,_quality,_novelty_and_reproducibility: I found the writing in this work easy to read and liked the style of presentation. Related work in topics of federated learning is well-described, but note my previous contention concerning related work concerning the analysis of stochastic gradient descent.

There is a minor typo in the abstract in "We find that the negative client sampling will cause the merged data distribution of currently sampled
clients heavily inconsistent" -> "We find that the negative client sampling will cause the merged data distribution of currently sampled
clients to be heavily inconsistent"
summary_of_the_review: This submission motivates a reweighting strategy for federated learning, but the analysis provided would have to equally apply to conventional stochastic gradient descent where I do not find it convincing. The submission adds further complications and produces evidence that the final algorithm is empirically useful, but I do not find the provided evidence compelling that this is for the reasons stated.

 If I fundamentally misunderstood the submission's intent, I would be interested in re-evaluating my score (and I welcome the authors' response in this regard), but otherwise I do not think this is a well-supported submission.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a technique to perform federated learning in the presence of non-IID data across clients. The main claim of the paper is to adjust the learning rate at the server side depending upon the similarity of the skewed gradients from non-iid data clients. The authors claim to achieve higher accuracy as compared to earlier techniques through empirical results. 
strength_and_weaknesses: The paper is well written and clearly motivates the problem and provides the related art. The paper also describes the experimental set-up quite clearly and the results obtained and the discussion on that.

The main drawback of the paper seems to be about its generality. The proposed approach seems to be mainly useful when most of the sampled clients for a given round will have very similar data distribution which is skewed!! I am not sure how probable this scenario is given  a purely random selection of clients in non-iid set-up. I would like to see at least a discussion on this and preferably some analysis on this aspect. The experiments are also done with only a fixed set of 10 clients in each round which is a comparably small number. It will be useful to see how the improvement scale as we increase the number of clients per round for different values of \alpha in Dirichlet distribution.

Other minor comments are below..

- results of FedAvg on CIFAR-10 seems to be lower than state-of-the-art, please check
- rather than reducing the learning rate and using all the gradients, a sampling/weighting of gradients can be done based on their directional heterogeneity.  Some experiments and discussion among these different approaches will be helpful. 
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and seems original. 
summary_of_the_review: see above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In federated learning, when clients have non-i.i.d. data, client sampling will introduce noises to the aggregated gradient. The authors propose a learning rate adaptation algorithm to adjust the server learning rate, which aims to prevent large parameter update to a bad direction. The algorithm is based on theoretical deduction, and is empirically evaluated on multiple tasks which universal accuracy improvement. 

strength_and_weaknesses: Strength: 

- The intuition is clear and the paper is easy to follow. 
- The paper has extensive empirical evaluation, which does show universal accuracy improvement. 

Weaknesses: 

- Inconsistency between intuitive claim and algorithm design. In the introduction, Figure 1, the authors claim that one should relatively decrease the server learning rate when the averaged gradient's **direction** deviates far away from the ideal gradient. However in the first inequality in Eq. (8), the authors replace the cosine similarity between $$g^t$$ and $$g_c^t$$ with 1, which totally ignores the direction information. 
- Unclear meaning of GSI. At the end of page 4, the authors claim that GSI measures the normalized similarity between local gradients. However, we can consider two extreme case. (1) When all local gradients are the same, all $$g_k^t = g^t$$, then GSI is 1. (2) When client gradients are diversed, e.g., half of then is $$(2, 2)$$ while half of them are $$(2, -2)$$, the GSI will be 1.414. So when local gradients are more noisy, the aggregated gradients will be enlarged rather than decreased, which contradicts with the authors' intuition. 
- The authors claim that unreliable gradients will be decreased while reliable gradients will be enlarged. There lacks verification of this important claim, e.g., a figure shows the correlation between GSI and gradient estimation error / distribution discrepancy between [merged dataset of selected clients] and [merged dataset of all clients]. 
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is well-written and easy to follow. 

Quality: The algorithm improves the accuracy of federated learning model. However, it is questionable why the algorithm works. 

Novelty: The proposed algorithm alters the server learning rate instead of gradient direction, which is orthogonal to previous works in federated learning. This direction has novelty in federated learning. 

Reproducibility: The authors give detailed explanation of their algorithm, and provide code implementation in the supplementary material. 

summary_of_the_review: It is a novel and effective algorithm, however the explanation is not convincing.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Paper studies Federated Learning and notes that the sampled average client pseudo-gradients $g^t$ may not align with global gradient $g^t_c$ if the sample of clients are biased. This motivates them to study an adaptive server learning rate mechanism which aims to make the gradient step $\eta_t g^t$ as close to ideal global server step $\eta_s g^t_c$ as possible. Paper provides some good results and ablation studies over many base FL algorithms and datasets. The parameter group-wise adaptation was also very interesting. Reviewers noted that the theoretical motivation for mechanism was not rigorous enough and may be making strong assumptions. Further no convergence rate guarantees are provided even for simple settings. Paper clarity would also improve if the authors can flesh out the connections to the vast literature on adaptive learning rates for centralized optimization. A good future experiment to solidify the theoretical motivation of the paper would be to verify that the performance increases when using the ideal learning rate $\eta_o^t$ claimed in equation (7), at least for smaller-scale problems (of course this needs computing. $g^t_c$). Authors can also do a correlation study between this ideal lr and the estimated lr in the algorithm. Finally, it might be better to term GSI as dissimilarity to avoid confusion since it at minimum when client pseudo gradients are the same.
justification_for_why_not_higher_score: Theoretical motivation is unclear and not rigorous enough. Further no convergence rate analysis is provided to show the adaptive mechanism improves the rate.
Decision: Reject