When to Trust Aggregated Gradients: Addressing Negative Client Sampling in Federated Learning
Authors: Wenkai Yang
Yankai Lin
Guangxiang Zhao
Peng Li
Jie Zhou
Xu Sun
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated learning
client sampling

Abstract: Federated Learning has become a widely-used framework which allows learning a global model on decentralized local datasets under the condition of protecting local data privacy. However, federated learning faces severe optimization difficulty when training samples are not independently and identically distributed (non-i.i.d.). In this paper, we point out that the client sampling practice plays a decisive role in the aforementioned optimization difficulty. We find that the negative client sampling will cause the merged data distribution of currently sampled clients heavily inconsistent with that of all available clients, and further make the aggregated gradient unreliable. To address this issue, we propose a novel learning rate adaptation mechanism to adaptively adjust the server learning rate for the aggregated gradient in each round, according to the consistency between the merged data distribution of currently sampled clients and that of all available clients. Specifically, we make theoretical deductions to find a meaningful and robust indicator that is positively related to the optimal server learning rate and can effectively reflect the merged data distribution of sampled clients, and we utilize it for the server learning rate adaptation. Extensive experiments on multiple image and text classification tasks validate the great effectiveness of our method.

Under review as a conference paper at ICLR 2023
WHEN TO TRUST AGGREGATED GRADIENTS: AD- DRESSING NEGATIVE CLIENT SAMPLING IN FEDER- ATED LEARNING
Anonymous authors Paper under double-bling brindd review
ABSTRACT
Federated Learning has become a widely-used framework which allows learning a global model on decentralized local datasets under the condition of protecting local data privacy. However, federated learning faces severe optimization dif- ficulty when training samples not independently and identically distributed (non-iidd.). In this paper, we point out that the client sampling practice plays a decisive role in the aforementioned optimization difficulty. We find that the neg- ative client sampling will cause the merged data distribution currently sampled clients heavily inconsistent with that of all available clients, and further make the aggregated gradient unreliable. To address this issue, we propose a novel learning rate adaptation mechanism to adaptively adjust the server learning rate for the aggregated gradient in each round, according to the consistency between the merged data distribution of currently sampled clients and that of all available clients. Specifically, we make theoretical deductions to find meaningful and ro- bust indicator that is positively related the optimal server learning rate and can effectively reflect the merged data distribution of sampled clients, and utilize it for the server learning rate adaptation. Extensive experiments on multiple image and text classification tasks validate the great effectiveness of our method.
INTRODUCTION
As tremendous data is produced various edge devices (e.g., mobile phones) every day, becomes important to study how to effectively utilize the data without revealing personal information and privacy. Federated Learning (Konečný et al. 2016 McMahan al., 2017) is then proposed to allow many clients to jointly train a well-behaved global model without exposing their private data. In each communication round, clients get the global model from a server and train the model locally on their own data for multiple steps. Then they upload the accumulated gradients only to the server, which is responsible to aggregate (average) the collected gradients and update the global model. By doing so, the training data never leaves the local devices.
has been shown that the federated learning algorithms perform poorly when training samples are independently and identically distributed (non-i.idd)) across clients (McMahan et al., 20117 Li ctt al. 2021), which is the common case in reality. Previous studies (Zhao et al. [0018] Karimireddy al. 2020) mainly attribute this problem the fact that the non-i.i.d. data distribution leads the divergence of the directions of the local gradients. Thus, they aim to solve this issue by making the local gradients have more consistent directions (Li et al., 2018 (Sattle et al., 202T Acar al.) 2020). However, we point out that the above studies overlook the negative impact brought by the client sampling procedure (McMahan et al.) 2017 Fraboni et al. (021b), whose existence we think should be the main cause of the optimization difficulty of the federated learning non-i.idd data.
Client sampling is widely applied in the server to solve the communication difficulty between the great number of total clients and the server with limited communication capability, by only sampling a small part of clients to participate in each round. We find that the client sampling induces the neg- federated learning. For example, assume each client
ative effect of the non-i.i.d. data distribution performs one full-batch gradient descent and uploads the local full- ball- gradient immediately (i.c., FedSGD in McMahan et al. (2017), (1) if all clients participate in the current round, it is equívalent

---

Under review as a conference paper at ICLR 2023
to performing global full- gradient descent on all training samples, and the aggregated server gradient is accurate regardless of whether the data is i..d. or not; (2) if only a part of clients is sam- pled for participation, the aggregated server gradient will deviate from the above global full-batch gradient and its direction depends on the merged data distribution of the currently sampled clients (i.e., the label distribution of the dataset constructed by data points from all sampled clients). The analysis is similar in the scenario where clients perform multiple local updates before uploading the gradients, and we have detailed discussion in Appendix B
The above analysis indicates that the reliabil- ity of the averaged gradients depends on the consistency between the merged data distri- bution of currently sampled clients and that of all available clients. Specifically, take the image classification task as an example (re- fer to Figure []: (1) if local samples from all selected clients are almost all cat images, the averaged gradient's 's direction deviates far away from the ideal server gradient averaged by all clients' local gradients. In this case, we may not trust the aggregated gradient, and decrease the server learning rate. (2) How- ever, if the merged data distribution of se- lected clients matches well with the merged data distribution of all clients, the averaged gradient's direction is more reliable. Thus, we should relatively enlarge the server learn- ing rate. This example motivates us to set dy- namic server learning rates across rounds in- stead of a fixed one as previous methods do.
Clent
Clice
splisdedd gradiont
averaged server gradiont
gradieur
Figure 1: An illustration of the impact of client sam- pling through a binary (cats v.s. dogs) image classi- fication task. (Right Top): If Client and Client are selected, their merged local samples are almost all cat images. Then the averaged gradient deviates far away from the ideal gradient that would be aver- aged by all clients' local gradients. (Right Bottom): If Client 1 and Client N are selected, their merged data distribution matches well with the global data distribution merged by all clients' data, and the av- eraged gradient has more reliable direction.
In this paper, we first analyze the impact of client sampling and are motivated to mitigate its negative impact by dynamically adjusting the server learning rates based on the relia- bility of the aggregated server gradients. We theoretically show that the optimal server learning rate in each round is positively related to an in- dicator called the Gradient Similarity-aware Indicator (GSI), which can reflect the merged data distribution of sampled clients by measuring the dissimilarity between uploaded gradients. Based on this indicator, we propose a gradient similarity- aware learning rate adaptation mechanism to adaptively adjust the server learning rates. Furthermore, our method will adjust the learning rate for each parameter group (i.e., weight matrix) individually based on its own GSI, in order to solve the issue of the inconsistent fluctuation patterns of GSI across parameter groups and achieve more pre- cise adjustments. Extensive experiments on multiple benchmarks show that our method consistently brings improvement to various state-of-the-arr federated optimization methods in various settings.
RELATED WORK
Federated Averaging (FedAvg) is first proposed by McMahan al. (2017) for the federated learning, and its convergence property is then widely studied (Li et al. 2019 Karimireddy et al. (202)). While FedAvg behaves well on the i.i.d. data with client sampling, further studies (Karimireddy al. (020)
reveal that its performance on the non-i.i.d. data degrades greatly. Therefore, existing studies focus on improving the model's performance when the training samples are non-i.i.d. under the partial client participation setting. They can be divided into the following categories:
Ad Advancing the optimizer used in the server's updating: Compared with FedAvg that is equiva- lent to applying SGD during the server's updating, other studies take steps further to use advanced server optimizers, such as using SGDM (Hsu et al. 2019 Wang et al. 2019b) and adaptive opti-
'Though in our example in Figure for simplicity, assume the merged data distribution of all available clients is balanced, we do not have this assumption in our later analysis.
2

---

Under review as a conference paper at ICLR 2023
However, their improvement comes from the effects of using advanced server optimizers, and they do not truly target on addressing the problems of the non-i.i.d data distribution and the client sampling. We show that our method can be effectively applied with these federated optimizers.
mizers (Reddi et al. 2020) like Adam (Kingma & Ba 2014).
Improving the directions of the averaged server gradients: (1) Some studies (Wang al. 2020
Yeganeh et al.] 2020 Wu & Wang 2021) manage to introduce better gradients' re-weighting proce- dures during server's S aggregation than the naive averaging (MeMahan et al. 2017). However, they either require an extra global dataset for validation or fail to tackle the situation where most of the sampled clients have similar but skewed data distributions.
(2) Instead of focusing on the server side, other studies choose to improve the local training on the client side. For example, FedProx (Li jet al. 2018) and FedDyn (Acar et al.) 2020) choose to add the regularization terms to make local gradients' directions more consistent; SCAFFOLD (Karimireddy et al. 2020) and VRLSGD (Liang) al.) 2019) send the historical aggregated gradients to each client for helping correct its local gra- dient's 's direction. In this paper, we consider from an orthogonal angle that aims to find an optimal server learning rate after the averaged gradient is determined. Thus, our method can be naturally combined with them.
Introducing new client sampling strategies: Being aware of the important role the client sampling
plays in federated learning, some studies (Ribero & Vikalo 2020 Chen al. 2020 Cho et al. 2020 Fraboni et al. 2021a) try to propose better client sampling schemes than the default uniform sampling without replacement strategy (McMahan et al.] (017). They attempt to select the most important clients based on some statistics of their local gradients, such as the gradient's 's norm. Our work is also orthogonal to them and can bring additional improvement when applied with them.
METHODOL.OGY
3.1
PROBLEM DEFINITION
The optimization target of the federated learning (McMahan et al. 2017) can be formalized as
NV 7 min L(0) min Σ k=1 n
(+),),
0
where N is the total number of clients, Tip is the number of local training samples client k. Σmm ng the total number of training samples, and (0) the local training objective for client k.
1 Σ 4 (0: x (k). y (8)) is
mg
The most popular federated learning framework is the FedAvg MMMMahan et al. 2017). which broad- casts the current global model 0 the available clients when the (++1)-th round begins and allows each client to perform the multi-step centralized training on its own data. Then each client only sends the accumulated local gradient 9 (k- 1,... N) to the server, and the server will aggregate (average) the local gradients and update the global model the following:
Ø++1 1 = 0² Σ
n&k gk
(2)
where 7/ is the server learning rate. The server will send the 0 to clients again for the next round's training.
In most real cases, due to the great number of clients and the server's limited communication capa- bility, the server will perform a client sampling strategy sample small portion of clients only in each round. Also, since we assume the number of local updates performed during each client's local training is the same in each training round following previous studies (McMahan et al. 2017 Reddi et al. 2020 then all ng are assumed to be the same. Therefore, Eq. can be re-written as
0 = 0¹ T/s Σ E E gk.
(3)
where r the number of sampled clients, S(N, r)t) represents a sampling procedure of sampling clients from N clients in the (t + 1)-th round, and we abbreviate it to St in the following paper.
?Our later proposed method in Section 3.3 can also he applied in the setting where the number of local updates varies across clients, combining with specific optimization methods like FodNova (Wang al. 2020
3

---

Under review as a conference paper at ICLR 2023
3.2 ANALYSIS OF THE IMPACT OF CLIENT SAMPLING
As we can except, in a given round, the averaged gradient under partial client participation will deviate from the ideal gradient under full client participation, which we think has reliable direction since it contains the data information of all clients. Thus, the motivation of most current studies can be summarized into optimizing the following problem:
maxx(CosSimg'.. ,
(4)
g'
k= g They achieve this goal indirectly from the per- spective of improving the local gradients, either by adjusting the direction of gl. (Li et al. 2018 Karimireddy et al. 2020: Acar et al. 2020), or by sampling better groups of clients (Chen et al.
where g' = 2 ge and g = x Σ
motivated to mitigate the inconsistent between g" and g from a different perspective, that is scaling g to achieve the nearest distance between and g:. (refer Figure 2). By doing so, a great advantage is to avoid updating the model towards a skewed direction overly when the uploaded gradients are similar but skewed (refer to the right top of Figure l). Then our optimization target can be written F
However, based on the analysis in Figure I
Ni = arg min I! g' n=gg.
(5)
ny
where 17, is the optimal global learning rate used under the full client participation setting.
Moreover, we point out that since our method is orthogonal to previous studies, we can get a more comprchensive optimization target by combining Eq. (5) with Eq. 44 as:
min Iln'g n=96"1. s.t. g = arg max (icosSii(ggg)))
(6)
However, in the scope of this paper, we only focus on the first part of Eq. (6) that is overlooked by previous studies, while assuming g' is already obtained or optimized by existing methods. Then, by solving Eq. (5) we can get
r = 1)s ((g) /l)g/"l''l))
where <. >> is an element-wise dot product operation.
In the (t + 1)-th round given 0', o is the determined but unknown parameters, which means it is impossible calculate < g" 9 precisely. However, we can still find the factors that will affect T by analyzing its upper bound:
Ekes, 1 ||g
g gg'l
ns 1
1/
7)
EkES, lo
In the first equality of Eq. we make the further derivation to separate the scale component V Ebes, l| that decided by the scales of the local gradients, and the direction component |gg / Ekes, | that depends on the similarity between the directions of local gradicnts, from |/g Now in the first term of the final equation of Eq. (8) ||gE|| can be considered as an un- known constant in this round given 0¹; the scale component y Exes, || can also be regarded constant which is barely affected by the sampling results in current round, since assume each client performs the same number of local updates, so the difference between the norms of all local gradients be negligible (especially when the local optimizer is Adam) compared with the dif- ference of local gradients' directions. However, the second term (v Exes, (3)//lg)lll indeed depends on the merged data distribution of currently sampled clients, as the directions of the local gradients depends on the sampled clients' local data distributions. Since it measures the normalized similarity between local gradients, we name it the Gradient Similarity-aware Indicator (GSI):
GST = V 1 KES.
(9)
II the following paper, || || represents the Frobenius norm. We make the detailed discussion and provide the empirical evidence in Appendix
4

---

Under review as a conference paper at ICLR 2023
sirer gradient
with Bood learning rule
Algorithm
Gradient Similarit--Aware Learning
avecaged sever gradiees
Rate Adaptation for Federated Learning
with optinall koarnngg rals
Sleal server learning role
Server Input: 0", no. 8 = 0.9, 0.02
for each round / = 0 to T do
sample client S C {1.-.. .N3
Figure 2: Illustration of our motivation.
for l E S in parallel do
g f- LocalTraining(k: k. 0', D&)
Gralien Similato www.eooooaaaa worrendece
end for
g' + E g for each param. group 0% 's gradient 9j do
GST; V(KES, | (1))lll)))/((ll)))))))))))
ciii levert thi Corigh
Bd. + GSIP
dard unt la costiiitiin noight
Glrd suttriinn
ipp t- max (GSTp/Bp, 1- 1-),, 1,
71,,
7t)
Commuication Round
66
Te
190
Bp + 3Bp + + (1- 3)GSI
gp + rlppr
Figure 3: Fluctuation patterns of GSIs in different parameter groups when federated training on 20NewsGroups (Lang 1995) with DistilBERT (Sanh al. 2019
end for g + 7g
end for
The reason why we do not choose 1/llg'|l as the indicator and make the further derivation in Eq. (8) is, the scales of the gradients will naturally decreases when training goes on, and 1/|lg'|| || will be in an increasing trend. This leads to the consistently increasing server learning rates, which makes SGD based optimization (which happens in the server aggregation phase) fail at the end of training. However, GSI is normalized indicator whose scale is stable across rounds.
We surprisingly find that the GSI happens to have the similar form the gradient diversity concept proposed in the distributed learning field (Yin et al. 2018),, however, they have different functions: the gradient diversity concept originally used to illustrate that allocating heterogeneous data to different nodes helps distributed learning; while in federated learning, the local data distributions and the sampling results in each round have been decided, but GSI can reflect the reliability of the sampling results and be further used to mitigate the negative impacts of bad sampling results. Specifically, if the training data is non-i.i.d., and the sampled clients have more similar local data distributions, which will be reflected in more similar local gradients and smaller GST, the merged data distribution of sampled clients is more likely to be skewed from the global data distribution. Then the aggregated server gradient may not be fully trusted, and the server learning rate should be relatively smaller. Otherwise, the GSI is larger, and the server learning rate should be larger.
3.3 GRADIENT SIMILARITY- AWARE LEARNING RATE ADAPTATION FOR FEDERATED LEARNING
Though we can not calculate the exact nh from Eq. (8) the above analysis motivates to use GSI as an indicator to relatively adjust the current round's server learning rate. Specifically, we can relatively adjust the learning rate by comparing the current round's GST with baseline B which we choose it as the exponential average of historical GSTs:
B = ='= 1 + (1 - B)GSI'-1 t= 1,2,
B = GSI..
(10)
Then the adjusted learning rate ń is calculated by multiplying the initial global learning rate Tj with the ratio of G and Bc:
n' = (GSI\BB)))
(11)
Parameter group-wise adaptation Based the above analysis, a direct solution is to regard all parameters as a whole and universally adjust the global learning rate based on Eq. However,
'no is a haper-parameter that can he tuned in the same way previous methods did to get their optimal server learning rate 7s- Thus, this is not extra harereper introduced for our work.
5

---

Under review as a conference paper at ICLR 2023
in our preliminary explorations, visualize the fluctuation patterns of GSI in different param- eter groups (i.e., weight matrices) when using FedAvg to train on 20NewsGroups (Lang 1995 f
in Figure and find that the GSIs have very different fluctuation degrees in different parameter groups whether from the same layer or not. Thus, to achieve more precise adaptations, we give each parameter group Pp independent adaptive learning rate based on its own GST in each round:
f/ no (GSI)//B)).
= 0, 0, ..
(12)
where GSIP and B are calculated based on the averaged gradient of the 0% only from Eq. (9).
Adaptation with dynamic bounds Moreover, as we can see from Figure the GSI varies much more greatly at the beginning than it does when the training becomes stable. The reason is that, when the global model is newly initialized, the local gradients are not stable, leading to the great variability of GSTs. In addition, there are not enough historical GSIs for estimating B% at the beginning, which will further cause the GST//B5 Bi, and tifr to vary greatly. Therefore, to avoid doing harm to the initial training caused by the great variations of the learning rates, set dynamic bounds which will restrict the parameter group-wise adaptive learning rates at the initial stage but gradually relax restrictions as the training becomes stable. The finally used learning rate for 0% is:
T/p- To min { (fixx/i//ooo.. --),,,, 1 + tt,, t 0,
(13)
where y is the bounding factor that controls the steepness of dynamic bounds. We name our method the Gradient Similarity-Aware Learning RAle ADaptation for Federated learning (FedGLAD). The
simplified illustration is in Algorithm 1, and the detailed version is in Appendix
Though the previous analysis based on the FedAvg framework, our proposed algorithm can also be applied with other federated optimization methods (e.g.. FedProx (Li et al.) 2018)) FedAvgM (Hsu al. 2019). FedAdam (Reddi et al.) 2020)). We make a detailed discussion about these variations, and illustrate how to effectively combine FedGLAD with them in Appendix [F] Also, we have a discussion about our method's limitations in the Limitations Section Appendix A
EXPERIMENTS AND ANALYSIS
4.1 DATASETS, MODELS, DATA PARTITIONING AND CLIENT SAMPLING
We perform experiments on two image classification tasks: CIFAR-10 10 (riizhessyy et al.
2009
and MNIST (LeCun et al. 1998), and two text classification tasks: 20NewsGroups (Lang 1995)
and AGNews (Zhang et al. 2015). The statistics of all datasets can be found in Appendix G We
use the ResNet-56 (He et al.) 2016 as the global model for CIFAR-10 and the same convolutional
neural network (CNN) as that used in Reddi et al. (2020) for MNIST. We use DistiBERT (Sanh
al.
2019 as the backbone for two text classification datasets following recent studies (Hilmkil
et al.
2021 Lin et al. 2021). We also explore the performance of using BiLSTM (Hochreiter &
Schmidhuber 1997) as the backbone in Appendix O
To simulate realistic non-i.i.d data partitions, we follow previous studies (Wang et al. 2019a Lin et al. (022)) by taking the advantage of the Dirichlet distribution Dir(a). In our main experiments, we choose the non-i.i.d. degree hyper-parameter a as 0. We also conduct extra experiments on a 1.0. The results are in Appendix L and the conclusions remain the same.
The total number of clients for each dataset is all 100, and the number of clients sampled in each round is 10. We adopt the widely-used uniform sampling without replacement strategy for client sampling (McMahan et al., 2017]] Fraboni et al. 2021b). We further explore the impacts of using different sampling ratios and sampling strategies in Section 5.2 and Section 5.3 respectively.
4.2 BASELINE METHODS AND TRAINING DETAILS
We choose 4 popular federated optimization methods as baselines Using SGD as the server optimizer: FedAvg (McMahan et al. 2017) and FedProx L et al.)
which can be divided as: (1)
We also visualize the results on CIFAR-10 (Krizhevsky et al. (009) and put the results in Appendix [D] while the conclusions are the same.
'hhe experimental settings are the same as that introduced Section 4.1
We also perform experiments with SCAFFOLDD (Karimireddy et al. 2020), but we find it can not work
well in our main experiments' settings. The detailed discussions be found in Appendix N

---

Under review as a conference paper at ICLR 2023
Table 1: The main results of all baselines with (+FedGLAAD) without our method.
Method
CIFAR-10
MNIST
20NewsGroups
AGNews
SGD Server Optimizer
FedAvg
35.30 (#: 1.62)
78.17 (1L 0.35)
72.84 (1 0.12)
79.48 (1 0.46)
FedGLAD
38.44 0.91)
79.71 (# 0.49)
73.14 (# 0.08)
80.74 (# 0.79)
FedProx
43.48
0.79)
82.72 72 (1 0.25)
72.78 (1 0.20)
82.61 (1 0.56)
+ FedGLAD
44,52 (1: 0.72)
83.54 (d: 0.34)
73.19 (#: 0.08)
83.44 (1: 0.44)
Advanced Server Optimizer
FedAvgM
48.79
1.35)
81.71 (# 0.99)
75.44 (# 0.10)
80.28 (# 1.75) 83.68 (+: 0.87)
FedGLAD 50.91 (= 1.33)
82.11 (#: 0.64)
75.91 (= 0.29)
FedAdam
56.82 (= 1.12)
96.94 (1 0.14)
76.76 (# 1.17)
86.72 (#: 1.02) 88.47 (+ 0.51)
FedGLAD
57.69 1.23)
97.11 (#: 0.11)
76.59 (# 0.81)
2018: (2) Using advanced server optimizers: FedAvgM (Hsu et al. 2019, Wang et al. and FedAdam (Reddi et al.) (020). The detailed descriptions of them are in the Appendix !! We show that our method can be applied to any of them to further improve the performance.
2019b)
As for the local training, we choose the client optimizers for image and text tasks as SGDM and Adam respectively. For each dataset, we adopt the optimal local learning rate ? and batch size B which are optimal in the centralized training the local training syper-parametert for all federated baselines. Then we allow each baseline method to tune its own best server learning rate 77 on each dataset. The number of local epochs is for two image classification datasets, and 1 for two text classification datasets. We also conduct the experiments to explore the impact of the number of local epochs E. the results and analysis are in Appendix PP The optimal training hyper-parameters (e.g.. server learning rates) will be tuned based on the training loss of the previous 20% rounds (Reddi al. 2020 Details of all the training hyper-parameters (including the total number of communi- cation rounds for each dataset) and further explanations are in Appendix
When applying our method with each baseline method in each setting, we use the original train- ing dyper-parameters tuned before in that experiment directly without extra tuning. In Ap- pendix M we explore the sensitivity to the bounding factor 7 of our method, and find 7 = 0.02 can be generally good choice in all cases. Thus, in our main experiments, we fix 7 as 0.02. The exponential decay factor / fixed as 0.9. We run each experiment on 3 different seeds, and on each seed we save the average test accuracy (%) over the last 10 rounds (Reddi et al.) 2020). Finally, we report the mean and the standard deviation of the average accuracy over the last 10 rounds on all seeds. Our code is mainly based FedNLP (Lin et al. 2021) and FedML (He et al. 2020).
4.3 MAIN RESULTS
The results of our main experiments are displayed in Table We also display the results of the cen- tralized training on each dataset in Appendix K The main conclusion is, our method can consis- tently bring improvement to all baselines on both image and text classification tasks in almost all settings. Note that though the standard deviation in each experiment in Table may seems bit large compared with the improvement gap, we point out that actually on almost each seed of one specific experiment, applying our method can gain the improvement over the corresponding baseline. We put the result on each seed in Appendix Q for comparison.
(1) First of all, our method effectively improves the performance of FedAvg in all settings, which directly validates our analysis in Section that it is better to set adaptive server learning rates based on the client sampling results. FedProx also uses SGD as the server optimizer but tries to improve the local gradients by making them have more consistent directions. However, FedProx requires the carefully tuning of its syper-parameter j to achieve better performance than FedAvg (refer to Appendix D.4) and there is guarantee that FedProx can outperform FedAvg in any setting (same conclusion for SCAFFOLD). This means that empirically adjusting the directions of local gradients may bring negative effects. Additionally, we find that FedAvg applied with FedGLAD can achieve
7

---

Under review as a conference paper at ICLR 2023
comparable performance with FedProx in some cases. This result indicates that optimizing the scales of the averaged gradients by adjusting the server learning rates is equally as important as optimizing the directions of local gradients before aggregation, while the former is overlooked by previous studies. Also, our method can further help FedProx to gain more improvement, since they are two complementary aspects for optimizing the full target in Eq. (6).
(2) FedAvgM and FedAdam belong to another type of baselines, which uses advanced server opti- mizers. For these two methods, the averaged server gradient in the current round will continuously affect the training in the future rounds since there is a momentum term to store it. Our method aims enlarge the scales of the relatively reliable averaged gradients, while down-scaling the aver- aged gradients that deviate greatly from the global optimization direction in specific rounds. Thus, our method can improve the learning when server optimizers include momentum term to stabilize training.
(3) When comparing the results in Table [ with the results on a = 1.0 in Table in Appendix L we can get that each dataset, the trend is the improvement brought by our method is greater the non-i..d. degree larger (i.c., smaller a). Our explanation is when the label distribution is more skewed, the impact of client sampling becomes larger. More analysis is in Appendix L
4.4 THE EFFECT OF FEDGLAD UNDER EXTREMELY BAD CLIENT SAMPLING SCENARIOS
In Figure we draw an example under the extremely bad client sampling scenario to illustrate the neces- sity of adapting server learning rates according to the client sampling results. Here, we validate this moti- vation by conducting a special experiment on MNIST with FedAvg. Specifically, while keeping other set- tings unchanged, we make sure that clients sampled in the 40-th round only have almost one same cat- egory of samples. Figure 4 displays the curves of the evaluation accuracy and the GS/ calculated by regarding all parameters as whole after each round.
90
Evaluation Accurccy (%)
80
70
16
16
5 5 2 GS)
Scampling Blagpens
TesAvg
B
Felling 651
25 Communicction Round
Figure 4:
The good effect of FedGLAD stabilizing training when extremely bad client sampling scenarios happen.
We notice that in the 40-th round, the accuracy of Fe- dAvg drops greatly due to the bad client sampling re- sults, and the corresponding GSST is also the smallest (i.e., close to 1) during the training. After applying FedGLAD, the accuracy degradation problem is effectively mitigated, and the accuracy curve is much more stable. The indicates that, our method can help to stabilize the training when extremely bad client sampling scenarios happen.
DEEP EXPLORATIONS
In this section, we take steps further to make more explorations of our method. We choose FedAvg and FedAvgM as baseline methods, and perform experiments on CIFAR-10 10 and 20NewsGroups (with the backbone DistilBERT) datasets with the non-i.i.d. degree a 0.1. The bounding factor ? of our method is fixed as 0.02. All experiments are run on 3 random seeds.
5.1 THE EFFECT OF ADJUSTING LEARNING RATES INDIVIDUALLY FOR DIFFERENT PARAMETER GROUPS
Here, we explore the benefits of using parameter group-wise adaptation compared with the direct solution that considers all parameters as whole and adjusts the server learning rate universally (universal adaptation, mentioned at the beginning of Section 3.3). The results are in Figure
Firstly, the universal adaptation strategy can already bring improvement to the baselines without adaptation. This indicates that dynamically adjusting the server learning rates based on the dissimi- larity between local gradients can indeed help federated learning. Moreover, the performance of pa- rameter group-wis adaptation strategy is consistently better than the universal adaptation strategy, which validates our motivation based on the findings in Figure 3 that the non-i.id. data distribution has different impacts the different parameter groups, should deal with them individually.
8

---

Under review as a conference paper at ICLR 2023
50
uniresal adapiution
wilhuut aleptaiiun
50,40
Test Accuracy (%)
76
universal ddpitation
willaut saleptation
75.44
75.42
75.91
Teat Accurazy
parzrn group-wiia adaptation
plezmn grop-sibe adeptasion
45
75
40
35,30
$7.05
73
72.95
73.14
35
FedAvg
PodAvgM
72
FedAvg
FedAvgM
(a) Results on CIFAR-10.
(b) Results on 20NewsCrrous.
Figure 5: Comparisons between two learning rate adaptation strategies of FedGLAD.
Table 2: Results under different sampling ratios.
Table 3: Results of different sampling strategies.
Sampling Ratio
Sampling Strategy
Datasct
Method
Dataset
Method
5%
10%
20%
MD
AdaFL
FedAvg
29.91
35.30
52.05
FedAvg
41.44
39.85
FedGLAD
33.35
38.44
53.40
FedGLAD
42,20
41.39
CIFAR-10
CIFAR-I0
FedAvgM
34.72
48.79
63.56
FedAvgM
51.77
52.76
FedGLAD
36.48
50,91
63.84
+ FedGGAA
53.85
53.68
FedAvg
63.09
72.84
76.31
FedAvg
73.36
72.14
FedGLAD
63.49
73.14
76.35
+ FedGLAD
74.04
72.92
20NewsGroups
20NewsGroups
FedAvgM
61.51
75.44
80.08
FedAvgM
75.22
76.18
FedGLAD
62.48
75.91
79.98
FedGLAD
75.60
76.40
5.2 THE IMPACT OF USING DIFFERENT SAMPLING RATIOS
In the main experiments, we fix the sampling ratio as 0.1. Here, we explore our method's perfor- mance in the settings where 5, 10, 20 out of 100 clients are sampled in each round. The optimal server learning rates for baselines are re-tuned here. The results are in Table 2 The overall trend the improvement brought by our method more significant when the sampling ratio is smaller. That is because when the number of sampled clients increases, the merged data distribu- tion of sampled clients is more likely be consistent with the merged data distribution of all clients, thus the impact of client sampling decreases.
5.3 COMBINING WITH VARIOUS CLIENT SAMPLING STRATEGIES
In this subsection, we want to show that our method can also be combined with other sampling mechanisms besides the normal one used in our main experiments. We conduct experiments with two additional sampling strategies: (1) Multinomial Distribation-based Sampling (MD) (Fraboni 2021b): considering sampled clients as r i.i.d. samples from Multinomial Distribution; Sampling (AdaFL) (Chen et al. 2021): dynamically adjusting the sampling weights of clients during the training. The sampling ratio is O.I. The results in Table show that our method can also work well with these sampling strategies, since they aim to sample better groups of clients in each round while our method improves the learning after the sampling results are determined.
(2) Dynamic Attention-base
6 CONCLUSION
In this paper, we study and mitigate the difficulty of federated learning non-i.i.d. data caused by the client sampling practice. We point out that the negative client sampling will make the aggregated gradients unreliable, thus the server learning rates should be dynamically adjusted according to the situations the local data distributions of sampled clients. We then theoretically find that the optimal server learning rate in each round is positively related to an indicator, which reflect the merged data distribution of sampled clients in that round. Based on this indicator, we design a novel learning rate adaptation mechanism mitigate the negative impact of client sampling. Extensive experiments validate the effectiveness of our method.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
Though the purpose of our work is positive as we aim to improve the performance of improve feder- ated learning on non-i.id. data, we admit that some adversarial clients may utilize the characteristics of our method to enforce the server to focus on their outlier local gradients, since our method tends give larger server learning rates when local gradients have more divergent directions. However, safety problems are not in the scope of this paper and belong to another field. One possible solution applying existing detecting techniques (Blanchard et al. 2017 to filter extremely abnormal gradients first before aggregation.
REPRODUCIBILITY STATEMENT
We have made great efforts to ensure the reproducibility of our work. First, we provide the neces- sary descriptions about the experimental settings Section 4.1 and Section (422) such as describing the datasets, backbone models and baseline methods we and the sufficient information of the training details. Also, as we mentioned and referred above sections, we put the complete ex- perimental details about the datasets and models in Appendix G the data partitioning procedure in Appendix H the descriptions of the baseline methods in Appendix [[ and the detailed training pro- cedure and hyper-parameters in Appendix J Most importantly, we have attached the anonymized code the supplementary materials.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Durmus Alp Emre Acar, Yue Zhao. Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Con- ference on Learning Representations, 2020.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning. arXiv preprint arXiv:2010. 13723, 2020.
Zihan Chen, Kai Fong Ernest Chong, and Tony QS Quek. Dynamic attention-based communication- efficient federated learning. arXiv preprint arXiv:2108.0570 2021.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint arXiv:2010.01243 2020.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171-4186. Minneapolis, Minnesota, 2019. Association for Computational Linguistics. doi: 10.188533v1/N19-11 1423. [tthstts::/
aclweb. org/ logg N1 1423
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Yann Fraboni, Richard Vidal, Lactitia Kameni, and Marco Lorenzi. Clustered sampling: Low-
variance and improved representativity for clients selection in federated learning. arXiv preprint arXiv:2/05.05883, 2021a.
Yann Fraboni, Richard Vidal, Lactitia Kameni, and Marco Lorenzi. On the impact of client sampling on federated learning convergence. arXiv preprint arXiv:2107.12211, 2021b.
Chaoyang He, Songze Li, Jinhyun So, Xiao Zeng, Mi Zhang, Hongyi Wang, Xiaoyang Wang, Pra- neeth Vepakomma, Abhishek Singh, Hang Qiu, et al. Fedml: A research library and benchmark for federated machine learning. arXiv preprint arXiv:2007. 13518, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Agrin Hilmkil, Sebastian Callh, Matteo Barbieri, Leon René Sütfeld, Edvin Listo Zec, and Olof Mogren. Scaling federated learning for fine-tuning of large language models. In International Conference on Applications of Natural Language to Information Systems, pp. 15-23. Springer, 2021.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.0m6 2019.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 1132-5143. PMLR, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6980, 2014.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint 16Xiv:/610.02555 2016.
11

---

Under review as a conference paper at ICLR 2023
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Ken Lang. Newsweeder: learning to filter netnews. In Proceedings of the Twelfth International Conference on International Conference on Machine Learning, pp. 331-339, 1995.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-22324 1998.
Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. Federated learning non-iid data silos: An experimental study. arXiv preprint arXiv:2102.02077 2021.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint arXiv: 1812:0181.. 2018.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2019.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv:1912.12844 2019.
Bill Yuchen Lin, Chaoyang He, Zihang Zeng. Hulin Wang, Yufen Huang, Mahdi Soltanolkotabi, Xiang Ren, and Salman Avestimehr. Fednlp: A research platform for federated learning in natural language processing. arXiv preprint
2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- learning deep networks from decentralized data. In Artificial intelli gence and statistics, pp. 1273-1282. PMLR, 2017.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings the 2014 conference empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Sashank J Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2020.
Monica Ribero and Haris Vikalo. Communication-efiie federated learning via optimal client sampling. arXiv preprint 10Xi::2007.11997,
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, distilled version of bert: smaller, faster. cheaper and lighter. arXiv preprint arXiv:1910.01100 2019.
Felix Sattler, Tim Korjakow, Roman Rischke, and Wojeiech Samek. Fedaux: Leveraging unlabeled auxiliary data in federated learning. arXiv preprint arXiv:2102.02514, 2021.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference on Learning Represen- tations. 2019a.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication--eficieett distributed sgd with slow momentum. In International Conference on Learning Representations, 2019b.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33, 2020.
Hongda Wu and Ping Wang- Fast-convergent federated learning with adaptive weighting. IEEE Transactions on Cognitive Communications and Networking, 2021.
Yousef Yeganeh, Azade Farshad, Nassir Navab, and Shadi Albargouni. Inverse distance aggregation for federated learning with non-iid data. In Domain Adaptation and Representation Transfer, and Distributed and Collaborative Learning, pp. 150-159. Springer, 2020.
12

---

Under review as a conference paper at ICLR 2023
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ranchandran, and Peter Bartlett. Gradient diversity: a key ingredient for scalable distributed learning. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2018.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. Advances in neural information processing systems, 28:649-657, 2015.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, XrXiv preprint 1806 2018.
13

---

Under review as a conference paper at ICLR 2023
A LIMITATIONS
There are also some limitations of our method: (1) First, we do not provide the convergence anal- ysis of our algorithm. However, algorithm's convergence can be guaranteed by the conver- gence results of existing federated learning algorithms (Li et al., 2019; Karimireddy et al.) 2020), since our approach is directly plugged into these methods without changing their main frameworks and our adaptive learning rate is well-bounded by the common assumption that the heterogene- ity of local gradients is bounded. (2) Second, in Eq. (8) we make the assumption that the term
V /KEEs, |[ 2 is barely affected by client sampling, while this assumption only strictly holds when the local optimizer is Adam. However, we provide the empirical evidence in the following Appendix to show that this assumption may still roughly holds even when the local optimizer SGD(M), as long as the number of local epochs is generally small.
B THE IMPACT OF CLIENT SAMPLING WHEN CLIENTS PERFORM MULTIPLE LOCAL UPDATES
In our main paper, we take the example of FedSGD (cMMhan et al. 2017) to illustrate our claim that, client sampling is the main root cause of the performance degradation of federated learning on non-i..d. data. In real cases, clients usually perform multiple local updates before uploading the accumulated gradients (McMahan et al. 2017). in order to accelerate the convergence. In this case, previous studies (Karimireddy setting, there still exists the optimization difficulty of FedAvg. The reason is, when the number of local steps increases, the local gradients are accumulated have more divergent directions, which leads to the unstable aggregation of local gradients in the server. However, this is not contradictory to our claim that, in this scenario, the directions of the averaged server gradients should still be more reliable and accurate under the full client participation setting than that under the partial participation setting.
al.] 2020) point that even under the full client participation
C DISCUSSION ABOUT THE IMPACT OF CLIENT SAMPLING ON THE SCALE COMPONENT
In Eq. 8 we made the further derivation by claiming that compared with the GST, the scale com- ponent ERES, || is barely affected by the client sampling results. We admit that this claim can hold under some certain assumptions. (1) First, if the local optimizer is chosen Adam, the norm of each local gradient is almost the same. That is because the update scale by using Adam is independent of the scales of gradients, but only depends on the learning rate and the number of up- dates, which are assumed to be the same across clients. (2) Second, if SGD(M) is the local optimizer, it is true that the scales of local gradients are different across clients, especially under the non-i.i.d. data scenario. However, if the number of local epochs is small, the difference between the norms of local gradients can be negligible compared with the divergence between their directions. This assumption can hold in ours setting since previous studies (Li et al.) 2018) suggest to use relatively small number of local epochs under the non-i.i.d. data situation with large number of clients and the small sampling ratio. The reason is, in this case, large local epochs may cause the local model to overfit the local data severely and make the aggregation difficult.
In order to explore the impact of client sampling the scale component, conduct the following experiments: we calculate the mean and the standard deviation of the squared norms of the uploaded local gradients in each round and then calculate the ratio between the standard deviation and the mean value. We report the averaged value of the ratios in each run. If the ratio is small during the training, we can have that the scale component indeed barely affected by the client sampling.
The results are in Table 7 As we can see, (1) when the local optimizer is Adam (i.e., experiments on 20NewsGroups). the ratios are all less than 0.2 in all settings, and the ratios smaller when is smaller or the number of epochs decreases. This indicates that when Adam is the local optimizer, our assumption that the squared norms of local gradients are almost the same across clients can hold
The optimization method is FedAvg and the settings are kept as the same as that in the main experiments.
14

---

Under review as a conference paper at ICLR 2023
Gradient Similarity-aann wwaiaaritt--zzzee Indistar
Figure 7: The averaged ratio values be-
2.3
tween the mean and standard deviation of
uploaded local gradients in different set-
tings.
Local Epochs
Ryyrr weight
Dataset
Byuer Necit connt wingh
5
byyer Nicci connt weigs
10
26
50
70
90
330
0.24
0.29
0.33
Communicaioon Round
CIFAR-10
1.0
0.23
0.19
0.15
Figure 8: Fluctuation patterns of GSTss in differ- ent parameter groups when federated training on CIFAR-I0 (Krizhevsky et al. 2009) with ResNet-
0.1
0.12
0.15
0.16
20NewsGroups
1.0
0.08
0.15
0.15
56 (He al. 20166).
well. (2) When the local optimizer SGDM (i.e., experiments on CIFAR-10), the ratios become larger as expected. However, even when the number of local epochs is 5 and a 0.1, the ratio smaller than 1/3, so our assumption that the scale component is barely affected by the client sampling compared with the direction component still roughly holds, and the experimental results also validate the effectiveness An interesting phenomenon in CIFAR-101 -- is, when 1.0, the ratio becomes smaller the number of local epochs increases, but is still smaller than that when a = 0.1. Our explanation is, when the number of local epochs is small, the randomness (e.g., data random shuffle, dropout) during the local training plays great role; and when the number of local epochs is large enough, the scale of each local gradient is stable and only depends on the local training objective.
our method even when we choose SGDM as the local optimizer.
D VISUALIZATIONS OF FLUCTUATION PATTERNS OF GSI ON CIFAR-10
In this section, we display the visualizations of fluctuation patterns of GSI in different parameter groups (i.e., weight matrices) during federated training on CIFAR-10 (Krizhevsky al. 2009) with ResNet-56 (He et al. 2016). Results are in Figure The conclusion is the same as that in 20News- Groups (refer to Figure groups.
GSIs have different fluctuation degrees in different kinds of parameter
E WHY CHOOSE PARAMETER GROUP- WISE ADAPTATION
In Section 3.3 we point out that giving different adaptive learning rates different parameter groups (i.e., weight matrices) can achieve more precise adjustments compared with the universal adaptation strategy, which considers all parameters as whole group. We verify the benefit of using the param- eter group-wise adaptation strategy in Section 5.1 Researchers can also choose other adaptation strategies, such as adjusting the learning rates layer-wisely that consider all parameters in the same layer as group. However, we find the layer-wise adaptation performs worse than the parameter group-wise adaptation. The reason is, even the same layer, GSI has different fluctuation pat- terns in different kinds of weight matrices (refer to Figure and Figure 8). Thus, the parameter group-wise adaptation strategy should better. On the other hand, we point out that an individual group to be adjusted should contain certain number of parameters, in order make the GSI more reliable due to the fact that the neurons in the same global model that are dropped out during dif- ferent clients' local training are different. This indicates that the element-wise adaptation (i.e., each element in weight matrix is re-scaled independently based on its own GSS)) may not work well.
F COMBINING FEDGLAD WITH VARIOUS FEDERATED OPTIMIZATION METHODS
In our main paper, we put simplified version of our method when combining it with FedAvg in Al Algorithm 1. Here, will give the detailed versions of our method when combined with various
15

---

Under review as a conference paper at ICLR 2023
optimization frameworks. In the following, we will first illustrate how to apply method in different kinds of methods.
If the optimization method aims to improve the local training while following the same aggregation mechanism as that of FedAvg, such as FedProx (Li et al. 2013), SCAFFOLD (Karimireddy et al, 2020) or FedDyn (Acar et al. 2020), can adapt the server learning rates following the same way as that in Algorithm 1.
There some other methods (Wang et al. 2019b; Hsu al. 2019) which try to utilize momentum term of the server gradient to help aggregating. In this case, we reformulate the original optimization target in Eq. (5) as:
No arg min ((n'gg + =m (g. Bm Bm. = arg min In'' -gtl??
5¹
7
(14)
g¹
Σ
m = = g--1 + m gh.
RES
Thus, the solution can be written as
g g
(15)
which is the same as that in Eq. with 7/+- = 1.0. Therefore, in this case, we can first adjust the current aggregated gradient's scale following the same mechanism discussed through Section [33 Then we use the adjusted server gradient to update the momentum, and update the global model with the global learning rate.
If the federated optimization framework (Reddi et al. 2020) utilizes an adaptive optimizer such as Adam (Kingma & Bal 2014) or AdaGrad (Duchi et al.J (01I) to update the global model in the server, our solution is only adjust the scale of the server gradient used in the numerator while keeping the squared gradient in the denominator unchanged. There are two reasons: (1) The scale of the server gradient will not only affect the first moment estimate m in the numerator, but also the second moment estimate o² in the denominator. For example, if we decrease the scale of f is also correspondingly down-scaled, the second moment estimate of in the denominator will also decrease, which may lead to larger adaptive learning rate, and this is not we expect happen. (2) The second reason is, the purpose of using the second moment estimate in Adam is to estimate and adjust the scale of current gradient based on the previous steps' gradients as the training goes on, while the purpose of our method is to optimize the scale of current gradient to mitigate the negative effect brought by the randomness of client sampling at a given round. Thus, we choose to keep the scale of the squared gradient unchanged.
current server gradient, then if the squared gradient g @gg
We summarize all above variations in detail in Algorithm 1
G DATASETS AND MODELS
Here we provide the detailed descriptions of the datasets and models we used in our experiments in Table 4 We get data from their public releases. Since these datasets are widely used, they do not contain any personally private information. Some of them do not have the public licenses, so we give all the public links to the datasets we use in the following. Following previous studies (Reddi et al. 2020). we use all original training samples for federated training and use test examples for final evaluation. We tune the 20% communication rounds (Reddi et al. 2020).
based on the averaged training loss of the previous
We use the ResNet-56 (He et al. 2) as the global model for CIFAR-IO Krizhevsky et al. 2009), and the same CNN used in Reddi et al. (2020) for MNIST 10 (LeCun et al. 1998). For 20News- Groups
Lang 1995) and AGNews (Zhang et al. 2015 we choose the DistilBERT (Sanh et al,, 2019 the global model, since previous work (Hilmkil et al. 202T) validates the great effec-
tiveness of utilizing pre-trained language models for federated fine-tuning, and DistilBERT is a
"MNIST can be obtained from http://yann..ecu.commeeee ktiz///fai//z////l/
"CIFAR-1O can be obtained from
11 "2oNessGroups can be obtained from http::///wo/ccccccccccc com/ Jasom/20Newsgrreee
The source page of AGNews corpus http:://roup..dd.unigi di gulli/AG corpus of news httml
16

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Variations of Gradient Similarity-Aware Learning Rate Adaptation for Federated Learning
1: Server Input: initial global model 0", global learning rate vJo, hyper-parameters 0.9.
7 0.02 and 31, 92
2: for each round 0 to T do
3: Sample clients from N clients: S C (1,-.- ,N
4: for E S" in parallel do
5: Broadcast current global model O' to client k D2)
6: 9 < L-oaaTTraiiiig(
7:
end for
8:
g¹ + g
9:
wit1 < -320' + (1-
(1-32)g 32)g" @ g' (FedAdam)
10:
for each parameter group 0% gradient g do
GST + V /EEES, 12
12:
13:
B¹, + GST
end if
15:
T/p f
701,-1),,10 + +t)
16:
Bp BBB + (1 - B)SSI
gp. s Tpgpp
18:
end for
Gc+1 f- 0' "og (FedAvg, FedProx, SCAFFOLD)
20:
m't1 + 8im (1- 31)g'
21:
0 SGDM m . 70) (FedAvgM)
22:
g++1 Adam 0 m=+1 _ 7o) (FedAdam)
23: end for
24:
25: Client k's Input: current global model 0', local dataset Da. local training hyper-parameters
26: LocalTraining(k, 0' Dx):
27: Client k performs centralized training to 0f on local data Da with tuned training hyper- parameters. get final model 0*+1
28: Return g 0" 0++1
Table 4: The statistics of the datasets we used in our experiments.
Dataset
# Training Samples
# Testing Samples
# Lahels
Model
of Rounds
CIFAR-10
50,000
10,000
10
ResNet-56
500
MNIST
60,000
10,000
10
CNN
50
20NewsGroups
11,314
7,532
20
DistilBERT
100
AGNews
120,000
7,600
4
DistilBERT
100
powerful lite version of BERT (Devlin et al., 2019) which makes it more suitable to local devices. The max_seq_ lew.sll..eehhhhhheeeeee length set as 128. We also conduct experiments on BiLSTM (Hochreiter & Schmidhuber 1997). and display the results in Appendix O
H DATA PARTITIONING STRATEGY
To simulate the non-i.i.d. data partitions, we follow FedNLP (Lin et al. 2021 by taking the advan- tage of the Dirichlet distribution. Specifically, assume there totally C' classes in the dataset, the vector 9k (gk,s 2 0, E [1, || ll = 1) represents the label distribution in client kt then we draw qk from Dirichlet distribution qk Dir(ap) where p represents the label distribution in the whole dataset and a controls the degree skewness of label distribution: when a becomes smaller, the label distribution becomes more skewed; when a oc, it becomes the i.i.d. setting. We assume
17

---

Under review as a conference paper at ICLR 2023
each client has the same number of local training samples so we can allocate samples to client A once qk is determined. order to solve the problem that some clients may not have enough exam- ples to sample from specific classes the sampling procedure goes, FedNLP provides dynamic reassigning strategy that can use samples from other classes which still have remainings to fill the vacancy of the chosen class whose samples are all used out. More details can be found in Lin et al. 2021
I BASELINE METHODS
We choose 4 widely- used federated optimization methods as baselines in our main experiments, and they are: (1) FedAvg (McMahan et al. (017): the most popular baseline in federated learning; (2) FedProx (Li et al. 2018): the widely-adopted baseline which aims to optimize the directions of local gradients, while keeping as the same aggregation mechanism
that of FedAvg in the server; (3) FedAvgM (Hsu et al., 2019; Wang et al. 2019b): the method that adds the momentum term during the server's updates; (4) FedAdam (Reddi et al.) 2020): the method that utilizes the adaptive optimizer Adam (Kingma & Ba 2014) to update the global model with the averaged server gradient. We also conduct experiments
another baseline SCAFFOLD (Karimireddy al. 2020), while during experiments we find SCAFFOLD itself can not converge well in our main experiments' settings. Thus, we make a separate discussion about this part in Appendix N
TRAINING DETAILS
J.1 LOCAL TRAINING
Firstly, we find SGDM is more suitable to train CNNs and Adam is more suitable to train Transformer- based models. Thus we choose the client optimizer as SGDM when training on two image classification datasets, and choose the client optimizer Adam for two text classification datasets. Then we perform centralized training on each dataset in order to find the optimal client learning rate oi and batch size B, and use that learning rate and batch size the local training hyper-parin pareepparameter for all federated optimization baselines in the federated training setting. The opti- mal local training hyper-parameters for each dataset are listed in Table [3] To decide the number of local training epoches for each dataset, we tune it from {1, 3, 5, 10} by using FedAvg, and use the tuned one for other optimization baselines.
J.2 SERVER AGGREGATING
We allow each baseline to tune its own optimal server learning rate in each data partition setting. The server learning rate search grids for all baseline methods are displayed in Table [4 We also display the server learning rates we have tuned and used in our main experiments in Table [5] The server learning rates used for the baseline methods in Section 5.2 and Section 5.3 are re-tuned, since we find the optimal server learning rates under different sampling ratios or different sampling strategies different.
There are several reasons to use the above local data, the optimal hyper-parameter in the centralized training setting should also work well for clients' local training in the federated training. (2) Using the same local training for each baseline method allows us make fair and clear comparison between them.
tuning strategy: (1) Since clients have
J.3 INFRASTRUCTURE AND TRAINING COSTS
All experiments are conducted on T+TIAN RTX. The running time of each method on CIFAR-1O, MNIST, 20Nessrrups and AGNews is about 12h, 0.5h, 6h and 6h respectively.
In this paper, we mainly focus on the label distribution shift problem, rather than the quantity shift problem. Also, since we assume each client performs the same number of local updates following previous studies, this practice is reasonable.
18

---

Under review as a conference paper at ICLR 2023
Table 5: The value and the standard deviation of the test accuracy for each dataset in the traditional centralized training setting.
CIFAR-10
MNIST
20NewsGroupss
AGNews
91.86 (# 0.49 99.26 0.04)
84.12 0.05)
93.43 0.07)
J.4 HYPER- PARAMEER TUNING OF FEDPROX
For FedProx, we allow it to tune its own hyper- parameter μe from (1.0, 0.1, 0.01, 0.001] in each data partition setting, and we display the best j in each setting in Table [2] As we can see, there is no general j for all settings, and researchers may carefully this hyper-parameter in each setting,
J.5 HYPER-PARAMETER TUNING OF FEDGLAD
As for our method, the key hyper-parameter is the bounding factor 7, Though the best y in each setting depends on its dataset, the label skewness degree and the backbone model, in our main experiments we show that there exists a general value (i.e., y = 0.02) which works well in most settings. researchers want to tune the optimal y each setting to achieve better performance, the recommended grid is (0.01, 0.02, 0.05).
Since our method aims to adjust the server learning rate relatively, it is also important to choose proper global learning rate `/ (refer to Algorithm method, we directly use the server learning rate used in the original baseline without extra tuning, since assume the optimal learning rate for the original baseline is the right choice for the global learning rate after applying our method, and we want to show our method is easy to apply. However, it is expectable that re-tuning the global learning rate for our method may bring more improvement.
During our experiments, when applying our
K RESULTS OF CENTRALIZED TRAINING
For comparison with the results in the federated training setting, we display the results on all datasets the traditional centralized training setting in T The training settings and on each dataset are kept the same as that in the local training of the federated learning.
L EXPERIMENTS ON 1.0
Besides the non-i.idd degrees we set in our main paper to conduct the main experiments, we also explore the performance of our method when a 1.0. The baselines and the settings are the same as that in the main experiments, and the results are in Table
As we can see, FedGLAD can also consistently bring improvement in this setting, which validates the effectiveness of our method. However, compared with the results in Table the main paper, we find that on each dataset, the overall trend is the improvement brought by our method are greater if the non-i.idd degree is larger (i.c., smaller a).. Our explanation is when the label distribution is more skewed, the impact of client sampling becomes larger. For example, when data is more non- i..d. and the sampled clients have the similar but skewed local data distributions, the averaged server gradient's s direction will deviate far more away from the ideal direction that we assume is averaged by all clients' local gradients. Thus, it becomes more important to adjust the server learning rates in these scenarios.
M THE SENSITIVITY TO THE BOUNDING FACTOR 7
Here, we want to explore our method's ss sensitivity to the bounding factor 7. The results are displayed Generally speaking, the best 7 in each setting depends on many factors, such as the
in Figure g
This can be important hyper-parameter if the optimization method follows the same aggregation strategy that of FedAvg. However, if using FedAvgM FedAdam, T 1.0.
19

---

Under review as a conference paper at ICLR 2023
Table 6: The results of all baselines with (+FedGLAAD without our method on 1.0.
Method
CIFAR-10
MNIST
20NewsGroups
AGNews
SGD Server Optimizer
FedAvg
72.09 (t: 1.27)
91.42 (1L 0.11)
76.66 (1 0.36)
91.27 (1 0.04)
FedGLAD 72.79 1.13)
91.63 (# 0.08)
77.21 (# 0.42)
91.38 (# 0.04)
FedProx
71.22
0.83)
91.68 (1 0.05)
76.51 (1 0.47)
91.24 (1 0.09)
+ FedGLAD
71.52 (:: 0.61)
91.86 (1. 0.06)
77.13 (# 0.17)
91.35 (1: 0.09)
Advanced Server Optimizer
FedAvgM
72.63
0.56)
93.37
0.29)
79.51 (# 0.31)
90.07 (# 0.27) 90.45 (# 0.42)
FedGLAD 73.07 (= 0.33)
93.97
(#: 0.26)
79.77 (= 0.08)
FedAdam
79.97 (= 1.30)
98.42 ( 0.08)
79.96 (# 0.12)
91.72 (#: 0.12) 91.81 (+: 0.10)
FedGLAD 80.75
1.35)
98.53 (d: 0.04)
80.13 (#: 0.20)
Test Accuney (%)
50
45.02
40.00
46.67
48:36
Tes Accurscy (%)
7544
75,50
75591
75,22
75.54
45
Fedtyg
FedSigM
75
FolAng
00
35.03
18:44
38
FodAngM
35
50
7251
73/14
7331
73.13
7306
35
71
0.00
6.01
6.02
0.04
0.05
0.0
0.01
0.02
Bounding Factor
Bounding Factor
(a) Results on CIFAR-10.
(b) Results on 20NewsCroups.
Figure& 8: The results of using different for FedGLAD. y= represents the original baseline and = do represents removing the bounds from the beginning. 0.02 can be a generally good choice.
dataset and the non-i.i.d. degree of data distribution across clients, from figures, we can see that there exists general value (i.e., 7 0.02) which works well in most cases. Therefore, choose 0.02 as the default value in the experiments in the main paper. Moreover, (1) though the performance of removing the bounds is better than the original baseline in some cases, it is consistently worse than that of setting the bounds. (2) The standard deviation in each experiment of using larger y increases. This validates motivation that without the restrictions, the learning rates the beginning will vary greatly, which will cause harm to the training.
N EXPERIMENTS ON SCAFFOLD
Besides the baselines we choose in the main experiments, we also conduct experiments with another baseline SCAFFOLD (Karimireddy al. 2020). SCAFFOLD aims optimize the directions of the averaged server gradients by improving the local training with the help of local control variates. The original version of SCAFFOLD assumes the client optimizer SGD, while we make some adaptations to make it applicable when the client optimizer is SGDM or Adam. However, we find the SCAFFOLD can not converge well on two image classification tasks if we follow the same training settings in our main experiments. We find the key factor which will affect the performance of SCAFFOLD is the sampling ratio and the number local training epochs E. That is, the sampling ratio is very small and when E is very large, SCAFFOLD may not converge well. We guess the reason may be that, when the sampling ratio is small, the number between two consecutive rounds of participation of client & is large. Thus, the local control variate of client k in the latter round may no longer be reliable, and using this control variate to adjust the directions local gradients for many local update steps will cause harm the local training. While for two text
20

---

Under review as a conference paper at ICLR 2023
Table 7: The results of SCAFFOLD with (+FedGLAD) without our method in different non-i.i.d. degree settings.
20NuwsGroups
AGNews
MNIST
Method
0.1
1.0
0.1
1.0
0.1
1.0
SCAFFOLD
76.22 (# 0.63)
77.14 (:: 0.39)
77.43 (#: 0,99)
91.08 (= 0.15)
86.02 (:: 0.64)
87.93 (:: 0.30)
FedGLAD
76.88 (# 0.48)
78.46 0.30)
81.42 (t 1.48)
91.17 (= 0.16)
86.06 (:: 0.88)
87.91 (#: 0.29)
Table 8: The results of BiLSTM.
Method a
20NewsGroups
AGNews
Centralized
XC
78.28 (# 0.94)
91.47 (# 0.16)
FedAvg
0.1
36.25 (# 0.46)
69.84 (= 0.29)
FedGLAD
0.1
37.37 (1: 0.40)
70.64 (#: 0:24)
FedAvgM
0.1
35.54 (#: 0.64)
71.36 (= 1.29)
FedGLAD
0.1
35.91 (t 0.67)
73.50 (= 1.40)
classification tasks, we choose F as 1 and also use pre-trained backhone that already mitigates the problem caused by the non-i.i.d. data distribution and the client sampling at certain degree, so the SCAFFOLD can work well on these two text classification datasets.
We keep the training hyper-parameters the same as that in our main experiments for two text classi- fication tasks. After re-tuning, we choose E for two image classification tasks. Other settings are the same as that in our main experiments. We find SCAFFOLD itself can still not converge well on CIFAR-10. 10, so we only report the results on the other three datasets in Table 7 The conclusions are the same as those in the main experiments: FedGLAD is also applicable with SCAFFOLD and tends to bring more improvement when non-i.i.d. degree is larger.
O EXPERIMENTS ON BILSTM
In our main experiments, we use pre-trained backbone DistilBERT for two text classification tasks. In this section, we conduct extra experiments with not pre-trained backbone BiLSTM (Hochreiter) & Schmidhuber] 1997) on 20NewsGroups and AGNews. The model is I-layer BiL.TMM with the hidden size of 300. We use the pre-trained word embeddings glove. 6b 300d (Pennington et al., 2014) for the embedding layer. The max seq length is 128. The dropout ratio for the LSTM layer is 0.2.
We use FedAvg and FedAvgM baselines, and the non-i.i.d. degree be found in Table [6] The results are in Table g As we can see, since BiLSTM not pre-trained, the performance gap between the federated training and the centralized training larger than that of using DistilBERT as the backbone under the same number of communication rounds. Secondly, after applying our learning rate adaptation mechanism, the performance consistently becomes better. The experimental results validate the effectiveness of our method on the BiLSTM.
0.1. Other details can
P EXPERIMENTS WITH DIFFERENT NUMBERS OF LOCAL EPOCHS
In our main experiments, we set local epochs E 5 for image classification tasks. As we dis- cussed in Section 3.2 in the main paper and Appendix C when the local optimizer is SGD(M) and when the number of epochs increases, our assumption about the scale component and the direction component may not generally holds. However, also we explained, increasing local epochs will easily make the local model overfit to the local dataset severely, and the choices of local epochs in
Downloaded from http://mh..saafoollddooooooooooo
21

---

Under review as a conference paper at ICLR 2023
Table 9: The results of different numbers of local epochs.
CIFAR-10
MNIST
Method
FedAvg
52.23 (# 1.78)
58.31 (# 1.59)
82.71 (# 0.68)
86. 13 (#: 0.40)
+ FedGLAD
53.81 0.56)
59.02 (# 1.13)
84.25
(# 0.33)
87.47 (1: 0.35)
FedAvgM
53.28 (# 1.86)
56.59 (# 1.50)
83.15 (# 2.63)
86.20 2.55) (1: 2.64) 86.68 (1 2.68)
+ FedGLAD 55.55 (1 0.24) 58.35 (1. 1.04)
82.71 1
Table 10: Results on each seed under 0.1.
Table 11: Results each seed under 1.0.
Random Seed
Random Seed
Dataset
Method
Dataset
Method
Sced1
Seed2
Scod3
Sced
Sced2
Sced3
FodAvg
37.08
33,90
34.91
FodAvg
73.20
70.70
72.36
FedGLAD
39.49
38.02
37.82
FedGLAD
74.07
71.91
72.39
CIFAR-10
CIFAR-I0
FedAvgM
47.24
49.38
49.76
FedAvgM
72.18
FadGLAD
49.40
51.91
51.42
FedGLAD
72.70
73.18
73.32
FedAvg
78.29
77.77
78.44
FedAvg
91.48
91.30
91.49
+edGLAD
79.20
79.75
80.19
+ FedGLAD
91.70
91.55
91.65
MNIST
MNIST
FedAvgM
80.68
82.65
81.79
FodAvgM
93.55
93.52
93.04
FedGLAD
81.68
82.84
81.81
FedGLAD
94.06
94.17
93.67
FedAvg
72.72
72.96
72.84
FedAvg
76.57
FedGLAD
73.13
73.22
73.06
FedGLAD
77.53
76.74
77.37
20NewsGroups
20NewsGroups
FedAvgM
75.39
75.38
75.56
FodAvgM
79.51
79.20
79.82
+edGLAD
76.02
76.12
75.58
+ FedGLAD
79.80
79.68
79.83
FedAvg
78.95
79.78
79.72
FedAvg
91.26
91.31
91.23
FedGLAD
79.83
81.29
81.11
FedGLAD
91.38
91.41
91.34
AGNews
AGNews
FedAvgM
82.25
79.67
78.91
FodAvgM
89.77
90.17
FedGLAD
84,22
84.14
82.67
FedGLAD
90.82
89.99
90.53
our experiments are also widely-adopted choices in previous studies (Reddi et al. 2020 Lin et al. 2021
Here, we conduct further experiments to explore the impact of the large number of local epochs on FedGLAD, We perform experiments on CIFAR-10 and MNIST with 0.1 and the local epochs E' = 10 and E = 20. As we can see from the Table 9 FedGLAD can also bring improvement in almost all settings. Our explanation is, in this case, the negative effect of bad sampling results will be further amplified, and GSI can detect this anomaly and decrease the learning rate in time. Also, during training we find that the accuracy curves (also the loss curves) vary greatly when E 10 or E = 20, indicates that they may not be proper choices in ours settings, and E can guarantee the stable training.
Q RESULTS ON EACH SEED OF EACH EXPERIMENT
As we mentioned in our paper in the experiment analysis section (Section 4.3 the standard devia- tion in each experiment in Table[aand may seems bit large compared with the improvement gap. However, we display the result on each seed of our method and baselines (take FedAvg and FedAvgM as examples) in the Table T0 and Table TT point out that actually almost each seed of one specific experiment, applying our method can gain the improvement over the cor- responding baseline. The large standard deviation of the baseline results are mainly caused by the fact that the large non-i.i.d. degree makes the baseline training sensitive to the random seeds.
22

---

Under review as a conference paper at ICLR 2023
Pearson Corr. 0.4753
GST w.r.t All Parameters
4.0
3.5
3.0
2.5
2.0
0,60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
Merged Data Distribution Similarity b/w Selected and All Clients
Figure 9: GSI is positively related to the the merged data distribution similarity between the sampled clients and all clients.
R CORRELATION BETWEEN GST AND THE MERGED DATA DISTRIBUTION SIMILARITY BETWEEN THE SAMPLED CLIENTS AND ALL CLIENTS
Here, we make deep analysis about the correlation between our proposed GST and the merged data distribution similarity between the sampled clients and all clients. First, we calculate the GSI in each round considering all parameters as group. At the same time, we calculate the similarity score between the merged data distribution of currently sampled clients and that of all clients. The simi- larity score is based on the cosine similarity between two distributions: denote L the total number
(4) of classes, ni as the number of samples belonging to label in client k's local data, Tip
Σ m
Σ
(2)
then the merged data distribution of sampled clients is d'
kest
).
Similarly,
kest
kEst
(2)
the merged data distribution of all clients is written de similarity score can be calculated as
Then, the
sim score'
= CosSo dd).
Then we visualize the seatter plot of the corresponding GSI and sim score" in Figure g red line corresponds to the linear regression result. The Pearson correlation coefficient between two variables is 0.4753, revealing that GSI is positively related to the the merged data distribution similarity between the sampled clients and all clients. This indicates that the GSI can effectively reflect the sampling results, and then be used to optimize the server learning rates, which helps to verify our original motivation.
The
23

---

Under review as a conference paper at ICLR 2023
Table 12: The best j for FedProx we tuned in each data partition setting.
CIFAR-10
MNIST
20NewsGroups
AGNews
Method
0.1
1.0
0.1
1.0
0.1
1.0
0.1
1.0
FedProx
0.1
0.1
1.0
0.1
0.001
0.001
1.0
0.001
Table 13: Local training hyper-paramenn for each dataset.
Dataset
Learning Rate
Batch Size
Client Optimizer
Local Epochs
CIFAR-10
0.1
64
SGDM
MNIST
0.01
64
SGDM
20NewsGroups
5e-5
32
Adam
AGNews
2e-5
32
Adam
Table 14: The server learning rate search grids for each baseline method.
Methods
Datasets
Search Grids
(CIFAR-10, MNIST)
[0.5, 2.0, 10.0)
(FedAvg, FedProx, SCAFFOLD) (20NewsGroups, AGNews)
{0.5, 2.0, 10.0}
[CIFAR-IO, MNIST)
(0.05,0.1,00 0.2, 0.5, 2.0. 5.0)
FedAvgM
(20NewsGroups, AGNews)
{0.05, 00.05,.1,0.2,--1 0.0, 2.0, 5503
(CIFAR-IO, MNIST)
(le3,203, So.31le Sc-2]
FedAdam
(20NowsGroups, AGNews]
50-53
Table 15: The optimal server learning rates for each baseline method in our experiments.
CIFAR-10
MNIST
20NewsGroups
AGNews
Method
α 0.1
a
1.0
0.1
a
1.0
0.1
a
1.0
a 0.1
a
1.0
FedAvg
0.5
1.0
6.0
1.0
FedProx
0.5
0.5
1.0
1.0
7.0
6.0
1.0
1.0
SCAFFOLD
0.5
0.5
1.0
1.0
7.0
6.0
1.0
1.0
FedAvgM
0.2
0.1
0.5
0.5
2.0
2.0
0.5
0.5
FedAdam
5c-3
5e-3
le-2
1c-2
3c-4
3c-4
2c-4
1e-4
Table 16: Training details of experiments on BiLSTM.
Local Training
Server Aggregating
Dataset
Optimizer
L.R
Batch Size
Local Epochs
Method
Server LR
Total Rounds
FedAvg
20NewsGiroups
Adam
0.001
32
FedAvgM
0.1
200
0.01
FedAvg
0.5
100
0.02
AGNews
Adam
0.001
32
FedAvgM
0.05
100
0.02
24


Reviews:
[{"review_id": "kvEPym1qals", "reviewer": "Reviewer_VDBr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "summary_of_the_review": "It is a novel and effective algorithm, however the explanation is not convincing. ", "strength_and_weaknesses": "Strength: \n\n- The intuition is clear and the paper is easy to follow. \n- The paper has extensive empirical evaluation, which does show universal accuracy improvement. \n\nWeaknesses: \n\n- 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. \n- 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. \n- 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]. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "i2Me7QTMHTc", "reviewer": "Reviewer_4pTV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.\n\n 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.", "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.\n\nMy 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. \n\nThe 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. \n\nThe 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.\n\nUltimately, 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Xr_4-fXM2g", "reviewer": "Reviewer_9Lj6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "My main concerns are listed below --\n\n- 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). \n\n- 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.\n\n- 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.", "strength_and_weaknesses": "**Strengths**\n\n**S1** The paper addresses a challenging and highly relevant problem in federated learning w/ non-iid client distributions.\n\n**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.\n\n**S3** The paper is clear and easy to follow, (w/ some exceptions as discussed below).\n\n**Weaknesses**\n\n**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).\n\n**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. \n\n**References**\n\n[1] Robust Federated Learning with Noisy Labels, Yang et al. (2020)\n\n[2] Weight Anonymized Factorization for Federated Learning, Hao et al. (2020)\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RGcjgRXX_iX", "reviewer": "Reviewer_s9jn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "summary_of_the_review": "see above. ", "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.\n\nThe 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.\n\nOther minor comments are below..\n\n- results of FedAvg on CIFAR-10 seems to be lower than state-of-the-art, please check\n- 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject