FedGSNR: Accelerating Federated Learning on Non-IID Data via Maximum Gradient Signal to Noise Ratio
Authors: Qi Tan
Yi Zhao
Ke Xu
Qi Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated learning
Gradient Signal to Noise Ratio
Optimal Local Updates
Non-IID Data

Abstract: Federated learning (FL) allows participants jointly training a model without direct data sharing. In such a process, participants rather than the central server perform local updates of stochastic gradient descent (SGD) and the central server aggregates the gradients from the participants to update the global model. However, the non-iid training data in participants significantly impact global model convergence.Most of existing studies addressed this issue by utilizing variance reduction or regularization. However, these studies focusing on specific datasets lack theoretical guarantee for efficient model training. In this paper, we provide a novel perspective on the non-iid issue by optimizing Gradient Signal to Noise Ratio (GSNR) during model training. In each participant, we decompose local gradients calculated on the non-iid training data into the signal and noise components and then speed up the model convergence by maximizing GSNR. We prove that GSNR can be maximized by using the optimal number of local updates. Subsequently, we develop FedGSNR to compute the optimal number of local updates for each participant, which can be applied to existing gradient calculation algorithms to accelerate the global model convergence. Moreover, according to the positive correlation between GSNR and the quality of shared information, FedGSNR allows the server to accurately evaluate contributions of different participants (i.e., the quality of local datasets) by utilizing GSNR. Extensive experimental evaluations demonstrate that FedGSNR achieves on average a 1.69× speedup with comparable accuracy.

Under review as a conference paper at ICLR 2023
FEDGSNR: ACCELERATING FEDERATED LEARNING ON NON-IID DATA VIA MAXIMUM GRADIENT SIGNAL TO NOISE RATIO
Anonymous authors Paper under double-blee blind review
ABSTRACT
Federated learning (FL) allows participants jointly training a model without direct data sharing. In such process, participants rather than the central server perform local updates of stochastic gradient descent (SGD) and the central server aggregates the gradients from the participants to update the global model. However, the non- iid training data in participants significantly impact global model convergence. Most of existing studies addressed this issue by utilizing variance reduction or regularization. However, these studies focusing on specific datasets lack theoretical guarantee for efficient model training. In this paper, we provide a novel perspective the non-iid issue by optimizing Gradient Signal to Noise Ratio (GSNR) during model training. In each participant, we decompose local gradients calculated on the non-iid training data into the signal and noise components and then speed up the model convergence by maximizing GSNR. We prove that GSNR can be maximized by using the optimal number of local updates. Subsequently, we develop FedGSNR to compute the optimal number of local updates for each participant, which can be applied existing gradient calculation algorithms to accelerate the global model convergence. Moreover, according to the positive correlation between GSNR and the quality of shared information, FedGSNR allows the server to accurately evaluate contributions of different participants (i.c., the quality of local datasets) by utilizing GSNR. Extensive experimental evaluations demonstrate that FedGSNR achieves average 1.69x speedup with comparable accuracy.
INTRODUCTION
Federated learning (FL) McMahan et al. (2017) focuses on practical scenario with multiple partici- pants to collaboratively train a model without direct data sharing. Different from the typical central- ized optimization problem, FL decomposes the optimization problem into several sub-optimizationn problems, and distributes them to different participants to be solved separately with the corresponding local datasets. Moreover, these local datasets often follow non-iid distributions in reality. During the training phase, each participant solves the sub-problem via stochastic gradient decent (SGD), and sends back the corresponding results for aggregation. One of the most popular FL algorithms FedAvg McMahan et al. (2017). and it typically accelerates global model convergence through multi- ple local updates. Although it has shown great performance many practical applications, there's 're still mysteries in this area, especially in non-iid -id cases, and many previous literatures Haddadpour & Mahdavi (2019): Khaled al. (200 Li al. (2020b) make efforts to analyze the convergency or even to accelerate it.
One of the key challenges in FL how a model can be well trained on non-iid data in different participants. On the one hand, such imbalance breaks the unbiased optimization procedure when we utilize multiple local updates. While on the other hand, due to the differences between different local datasets, non-iid information distribution makes it difficult to evaluate the contribution of different participants. The former slows down the FL-based model convergence, i.c., a key factor of the efficiency. The latter is associated with contribution evaluation involving malicious data tampering detection, contribution- based profit distribution, incentive mechanism design, etc. Especially in the current data-driven age Sim et al. (2020), contribution evaluation is particularly important. In addition

---

Under review as a conference paper at ICLR 2023
to separately pursuing the two goals of accelerating model convergence and improving contribution evaluation accuracy, these two goals even conflict with each other.
To solve above challenges. propose novel approach that speedups model training by maximizing Gradient Signal to Noise Ratio (GSNR). The intuitions behind the design are two-fold. First, there is always global optimal solution no matter how the data is distributed. For each local dataset, can obtain an optimal optimization direction, i.e., the global gradient. Second, based on the information theory, GSNR determines the channel capacity, i.e., Shannon' 's formula: C W log(( SNR), and larger GSNR means we can get more information with identical communication rounds, which can accelerate the model convergence. Thus, we can decompose the local optimization direction (i.e.. the local gradient) into mutually orthogonal signal vector and noise vector. We find that if we can obtain the global gradient, the signal vector is parallel the global gradient, while the noise vector orthogonal to it. Fig. shows a typical example of orthogonal decomposition of two participants.
We prove that the number of local updates can control the GSNR value and we can maximize GSNR by computing the optimal number of local updates. To maximize GSNR, we uti- lize the gradients uploaded by the participants to estimate the global gradient, and propose FedGSNR algorithm to compute the optimal number of local updates according to the esti- mated global gradient. Moreover, based on the GSNR perspective, we also develop specific method to compute the GSNR for each dataset, which allow the server to evaluate each partici- pant's contribution.
Staxal
Fl
ErG IC))
W2
Figure An example of Gradient Signal to Noise Ratio (GSNR). A local step can be de- composed into two components: signal and noise, the former parallels to the update with global data, and the latter orthogonal to it.
In addition to personalizing the number of lo- cal updates to optimize model convergence ef- ficiency, the newly proposed GSNR strategy FedGSNR is orthogonal to existing methods, which mostly depends on modifying gradients calculating. Hence, FedGSNR can be combined with these methods so to further improve them.
In summary, our contributions in this paper are as follows:
We prove that the optimal local updates decides the maximal GSNR, which leads to faster and more stable convergence.
We analyze existing FL algorithms with the perspective of GSNR. Moreover, based on the viewpoint of GSNR maximization, we propose an algorithm FedGSNR, which can be combined with most of current FL algorithms to calculate its optimal local updates.
We derive a function r(w) to calculate GSNR, which can be utilized to evaluate the local contributions of different participants.
We confirm our theoretical results on CIFAR-IO and CIFAR-100 datasets, and experiments indicate that FedGSNR can achieve on average a 1.69 speedup over its original when the information unevenly distributed among all participants, and r(w) is a reasonable metric for local contributions.
Related Work. There has been lot of literatures devoted improving FL, including convergence
Karimireddy et al. (2020); Li et al. (2020b); Wang et al. (2020a); Reddi et al. (2021) robustness
Mohri al. (2019): y: Fang et al. (2020): Li al. (2021). ),, and data privacy Melis al. (2019; Zhu et al. (2019); Bagdasaryan et al. (2018). Regarding GSNR, Rainforth et al. (2018) 18) Liu et al. (2020)
try to analyze the generalization and variational bounds with such concept. In this work, we focus on the relationship between GSNR and the optimal local updates in FL scenarios. To control the
noise component (client drift), Karimireddy et al. (2020) proposes a specific gradient calculating method based on variance reduction. Li et al. (2020a) indicates that under non-iid FL conditions, large number of local updates lead to divergence or instability. While Wang et al.) (2020b) tries to stabilize the training procedure with a new average strategy. On the other hand, Wang et al. (2019) proposes practical optimization problem with resources constraints, and it determines the number of local updates for each participant according to the corresponding constraints.
2

---

Under review as a conference paper at ICLR 2023
A similar work Khaled al. (2020) derives upper bound of local updates by total iterations T and the number of participants M, which proposes a theoretical analysis local updates. But, they treat each participant equally, and fail to propose method to calculate the optimal number of local updates directly from the heterogeneous data. More discussion of related work can be found in Appendix A
PRELIMINARY
2.1 FEDERATED AVERAGING (FEDAVG) In this work, consider the following federated optimization problem:
min (w)= = (u, 5) = EF(Be[F(ur, 1 -1=EPPn P(C= P(C=CP
B E(Ck),, (1)
k=1
where F(w, is a specified loss function with model w, K is the number of participants, and P(C)
discrete probability distribution correlated to the importance of different datasets. Usually, P(C)
is a uniform distribution or proportional to the local data quantity, and c|Ca random sample drawn from the dataset of k-th participant, i.e., c|Ck p(æ(Cx))
Regarding traditional machine learning, the global dataset is gathered from all participants, and the goal is to minimize
F(w) = [f E)],
(2)
where & a random sample global dataset, i.e., the gathered data. However, in most cases, due to the privacy requests, we cannot gather data from different participants. Thus, we separate the target function as Eq. [T. and send the initial model w to each participant, then they do the optimization locally, and send back the corresponding results. We finally obtain the results by Eq. (T).
each participant does only one step optimization, according to the property of conditional expecta- tion, minimizing Eq. (1) is equivalent to minimizing Eq. (2) But this procedure puts lot of pressure on communication, so researchers propose to do more local updates for efficiency. Hence, for the k-th participant, the optimization procedure of typical round can be formalized
w + 1 EEEEC, F(w E|Cx)l, = 1,....
Then the central server aggregates local models wh+1
w to update the global model by
K
Pk n+1
where we denote pa for P(C = Cx) for convenience.
2.2 WASSERSTEIN DISTANCE
Wasserstein distance Villani (2009) is metric in probabilistic space inspired by the problem of optimal transport. It is distance between probability distributions that takes geometric information into account. The general wasserstein distance is defined as
Wp v)
inf y)F(ue))
B(mx))>>ll - -
which difficult find closed form solution. However, if chose 2-norm the geometric measure and simplify the problem to Gaussian distribution, the distance has an analytic solution
& = || - where we define d = W2(N(H1 E Ex).
3 MAXIMIZE GSNR WITH OPTIMAL LOCAL UPDATES
In this section, we investigate the relationship between GSNR and the local updates, then we propose method to caleulate the optimal number of local updates. As Section will introduce, GSNR can be

---

Under review as a conference paper at ICLR 2023
calculated by the ratio between the norm of global gradient, which is a constant for all participants, and the distance between global and local gradients. Therefore, to maximize GSNR is equivalent to minimize the distance between the distributions of global and local gradients. Furthermore, the minimal distance, i.e., the maximum GSNR, is decided by the optimal local updates.
On the other hand, mentioned in Section 2.1 our target is to gather data as optimize Eq. centralizedly. But in practice, due to some real restrictions, we can just optimize Eq. (1) distributedly. Thus, we treat the former procedure as an ideal optimization process. Based upon this idea, for accelerating convergence, our practical optimization problem also requires to minimize the distance between practical and ideal optimization path. which is determined by the corresponding gradients.
The distance between practical and ideal optimization path, which are denoted by the distributions of Pw (w) and pw, (w) respectively can be formalized as
(5) According to Eq. due to the conditional independence of the data from different participants, the random vector w convex combination of a set of independent random vectors, hence Pw(w) is identified by the convolution of corresponding local distribution functions, and such a distribution contains all details of each participant. Intuitively, if specific participant attempts to minimize Eq. (5). it has to gather all information from others, which violates the privacy requests. Then we
D W2 (Pw(w), Pw, (w)),
need to derive an upper bound Eq. (5)
D W2(Pw
Pw, (w)) (w) + (ET(Pp))
inf
Ph
inf
(( |||e y112).
(6)
7h (P :Pwg)
1=1
where we split ||æ: T(P P.,.). Then the inequality depends on triangle inequality and the fact that wh++ is mutual independent. The upper bound is obvious, since by optimal transport, comprehensively considering all mounds is better than the sum of separate consideration.
yll E (e( y)ll, and each pair (ætx y) is supported on
By upper bound (6). the distance between practical and ideal optimization path is upper bounded. In other words, while minimizing upper bound (6). the target distance (5) is approximately minimized. Specifically, the target gap vanishes as the upper bound approaches to O. Regarding Eq. (6). it the sum of the distance between each independent local distribution pwtt, and the global distribution
Pw,, then due to the rotating symmetry, we can minimize upper bound (6) separately for each participant. Hence, without loss of generality, we just consider specific participant in federated learning in the rest of this paper.
Based on former analysis, for maximizing GSNR, each participant needs to greedily optimize its local
gradient distribution to minimize the distance W2(Pw; (w), Pw, (w)).. ). As the initial parameters,
i.e., wf for all participants are identical, the main target to estimate the gradient distribution of different participants. Then we have the following assumption.
Assumption 3.1. (Bounded variance) The variance of stochastic gradients are uniformly bounded, i.c., Eejc, V F (C) - pill < o², Vi, w, where μ4: := Eqc, ( F(w, E|C.)]
Under such an assumption, the mini-batch stochastic gradient descent converges to joint normal distribution. The detailed proofs can be found in Appendix B
3.1 let (EuD 1 < SS s B) be set of iid sam- (9), ... ,9n) be a finite dimensional gradient vector, where 9: t EB=, VwF(W, E,,D), i (1,.... "L.....,t .n...., then vB(g - E(g]) converges to multivariate normal distribution.
Lemma 3.2. With Assumption ples of a specific dataset,
Remark 3.3. Let S = vBlg B(g)) and Z ~ N(0. Σ), where Σ is the covariance matrix of S, then based on Berry-Esseen theorem, for all convex sets U C Rdd, we have [Pr(S E U) Pr(Z
- C (rank(S) where C is a constant, which provides an upper bound of estimation error for /2
Lemma 3.2
" is the ideal optimization path based the global data distribution, i.e., the ideal distribution of data gathered from all participants, while the corresponding practical path defined by Eq.
4

---

where m is a constant, the and the minimal distance is Under review as a conference paper at ICLR 2023
implies that, with mini-batch stochastic gradient descent, the sum of local updates converges to Gaussian distribution, i.e. g = Wn+11 - w = Di= 9: = 1" g, where g is linear transformation of a joint Gaussian vector. Thus, with finite batch size B, it can be approximated by Gaussian distribution. Then we need to calculate the mean vector and the covariance matrix. For such a purpose, we have another assumption of smoothness.
Lemma 3.2
Assumption 3.4. (Smoothness) The target function F(w, :):R" R + the expected matrix norm of hessian matrix H HFF(w, )) is bounded, i.e., lEg (H(FFFF E))(1 s 1.?, where & is randomly sampled from a specific dataset.
is twice differentiable, and
Note that Assumption 3.4 is weaker than L-sooohh Assumption, since if a function F(w,, is L-smooth, conforms to Assumption 3.4. but not vice versa.
Assumption 3.4alway always holds for typical machine learning tasks, c.g., logistic regression, soft-max classification and so on. With these assumptions, we have the following lemma.
Lemma 3.5. If Assumption 3.1 and 3.4 hold, let { be sequence of real number such that lim 7r = O, and { be sequence of random vectors, where E, = 9 and
9 ET=1 FwF(( E:). 9 V F..w, E:) with w; w;-1 7.9 (2. .
respectively, then we have e, 4 O, which implies 9 -.g. 9.
Remark 3.6. Based on the proof of Lemma 3.5 in appendix, the estimation error is Elg gll s
n(n LG, which implies that if we consider learning rate decay then
Ve, lim Pr(lg ا1l > <) =.
+
In typical communication round r. the optimization process implies that w wi 7/.9. While based on Eq. (7). we can use 7/ = Σx= V F(w, E.) to estimate 1/.9. Moreover, we multiply Eq. by Tr the estimation error becomes LG))
Specifically, since wT is constant vector and & is iid sampled from the dataset in different local steps, (V.F E [I.....n] are also iid random vectors. Therefore, based on the sum of independent random variables, have μ = E[ng mf, E)], and E = Cov(n,g n) = E1
Additionally, Σ a second order term. To simplify the analysis, we need convert coefficient n to n As mentioned before, ΣS is the covariance matrix of mean vector distribution, hence it depends on the batch size B. Let B = B /n, then we obtain Σ n
For convenience, in the rest our work, we use μ., and Σ, to denote the corresponding mean vector and covariance matrix of gradients estimated by specific dataset. Similarly, as we can change the local batch size for simplifying computation, we ignore the differrnnces between B and B.
According to Lemma 3.2 and 3.5 we can estimate the parameter distributions of one global step and n local steps by N (m th and and ((nn,, n² n² E. respectively. Then the optimal number of local updates maximize GSNR is implied by following theorem.
Theorem 3.7. The minimal Wasserstein distance between two multivariate Gaussian distribution En denoted by N (nrig 1i B) and N (mm-uu n² Σn with variable is achieved when
11 14 (r((E,,,))
opt n1
=max(0,
B
|| + (2))
B
and the minimum distance is (Appt 2 = =1,12
MT Mg + (EE
A = || 2 tr(2n)
B
B
11:11221 + (r(E))
Corollary 3.8. For (mmm-pg mr Eg)) and N N MMi Mu, Es). opt
optimal minimize the Wasserstein distance is nopt ni (A = p22
FFor example, Nr noa" refers a widely used learning rate decay method with decay rate
5

---

Under review as a conference paper at ICLR 2023
Algorithm Example of FedGSNR in conjunction with FedAvg
Input: initial model w1, learning rate yo. sample size and chosen global steps M
for : 1 to R do
Sample clients S _ fl....... K
Server: send Wi and dr to each client i
On each active client in parallel: initialize local model w² <- Wi, compute 9; and
diag(22 _;), and send them to the server
opt with Theorem 3.7 for each client i, and send it to each client Server: compute 71,
On each active client in parallel: for k = to M opt do 11,
w' w 7.9i
end for
Server: + E p, where $ = {ili E S.n > 0}, and p; is the corre- sponding probability ratio, i.e., p./ E
end for
Based on Corollary 3.8 if is a constant, the minimum Wasserstein distance achieved when m np which the optimal number of local updates for maximizing GSNR, leading maximal channel capacity for information communication.
To estimate the optimal local updates, we need to compute the mean vectors and covariance matrix for both local distribution and global distribution by the samples from each participant. In practice, we use sample mean vector and sample covariance matrix to estimate the parameters of local distribution, i.e., for participant with model w1, the corresponding statistics are gl: = B Σ Ik.b and Σx B 2 (g (gk,b )" where gb.A F(w1 Ck). While for the server, based on the theorem of conditional random variables, the corresponding global statistics are
g Eclg
Σ
pkgk
(8)
K
K
Σ =
Ec C) Cove (ī|C)
Ph: [ () - -1
In practice, the covariance matrix increases the communication traffic and the calculation of matrix introduces lots computation, we need to simplify the procedure. Specifically, Theorem [37] we mainly need the trace of covariance matrix. Meanwhile, according to Balluzzzi al. (2017). we know that the covariance matrix of gradients a sparse matrix and the estimate error can be scaled by the batch size B. Therefore, we can instead utilize the principal diagonal element of Σ, for efficiency. Based on former analysis, propose an algorithm FedGSNR calculate the optimal number of local updates, and Algorithm is typical example of FedGSNR in conjunction with FedAvg
Partial participation. In federated scenarios, the active participants are usually 100%, cannot obtain perfect information of global gradient. However, we claim that FedGSNR can also adapt this situation, because such imperfect information encourages us transform Eq. (5) with triangle inequality to
We (P(P((w), Pw, (w)) (2 (P(((s)) (w), Pa (w)) + W2(Pw(w) Pw,, (w))))
where is the average parameters active clients (i.e., a subset of total clients). With a specific client set S, 5 = (2(Pw (w)) Pw, (w)) is constant, and W2 (w), Par Pa-(ww (w)) can be bounded by inequality (6). Thus, with some tolerance ó, we can similarly minimize Eq. (5) with the new upper bound, but the performance decreases as the ratio of active clients declines.
Note that proposed FedGSNR is compatible method, and the referred FedAvg can also be replaced by other methods (c.g., FedProx).

---

Under review as a conference paper at ICLR 2023
Convergence analysis. FedGSNR is convergent algorithm, since just change the number of local updates. Moreover, we can transform the convergence analysis of FedGSNR to its original version by the inequality < Emin Eir maa. We provide example of convergence analysis for FedGSNR with FedAvg in Appendix
4 CALCULATE GSNR BY LOCAL GRADIENTS
In this section, we first analyze the optimal local updates as well as the optimal distance between the local gradient distribution and the global gradient distribution, and then derive method to caleulate GSNR by the optimal distance. However, due to the limited space, the detailed analysis between GSNR and the optimization procedure can be found Appendix C
Regarding the optimal number of local updates p and the corresponding optimal distance (A)² let
Global Step
L || 1| tr(Ea) M pu My (r((EEE,) and N = 1112 + tr(Zi) m0 N and (A)² L M N
tr
we can rewrite ni
B
||ll
17²
Then define matrix follows:
Local Steps
R.
Figure 2:
An overview for GSNR: the GSNR can be calculated by the statistics of global gradient distribution and local gradient distribution.
u
1 Σ.)²
where fć, is the component of (1) ,().
On the one hand, participants On the other hand, N |R l depends on local distribution, thus it is normalization coefficient. Hence, the two variables n and (2)² mainly depend on the value of M, the inner product of two matrixes, i.e., < R, Rg >.. r. which represents the similarity of them.
R f is correlated the global distribution, which is constant for all
Based on former analysis, we derive method to calculate GSNR as Definition 4.1
Definition 4.1. Gradient Signal to Noise Ratio (GSNR). For local dataset Dj and global dataset Dg, with a loss function F(w, the GSNR is a function of w defined as
R
Rg
>F
r(w) ma
R 2
R
R R >
In Fig. we imagine a similar case in Euclid space. In this case, angle 9 can be viewed as the similarity between global and local gradient vectors. In Euclid space, the minimum distance from a point to line is the segment vertical to the line, csc
Specifically, Fig. 2 illlstrrates an example for Definition
thus the black dash line orthogonal to local gradient vector. Hence, As for GSNR, defined as the magnitude ratio between the parallel component and the orthogonal component, it be viewed the cot 8. Then according trigonometric transformation, i.e., cot? esc? 1, we can obtain Definition 4.1
A
EXPERIMENT
We run our experiments on the well known real world datasets CIFAR-10 and CIFAR-100 mentioned in Krizhevsky al. (2009) to validate our design.
Setup. For non-iid settings, we utilize methods for data partition. First, we follow the settings in Hsu et al. (2019) to generate non-iid data across different participants by Dirichlet distribution, where
I1 || and .,* PF Frobenius inner product and Frobenius respectively.

---

Under review as a conference paper at ICLR 2023
is parameter represents the level of non-iid. Second, propose NonBalance and Pareto for imbalanced partition, which simulates the imbalanced distributed information in practical scenario. Due to the limited space, the details of different methods can be found in Appendix D For all experiments, we use LeNet for CIFAR-10 and VGG-16 for CIFAR-100.
Table I: Communication rounds to reach 0.5 accuracy and corresponding speedup" of FedGSNR on CIFAR1O. We distributed the data among 30 clients, utilize batch size of 64, and set Econst 20.
Algorithms
a 0.5
a 0.1
Label
NonBalance
Pareto
FedAvg
(1.00)
355 (1.0x)
470 (1.0x)
210
550 (1.0x)
FedGSNR with FedAvg
115 (1.5x)
285 (1.3%)
340 (1.4x)
155 (1.4x)
170 (3.2x)
FedProx
185 (1.0x)
(3.00)))
(1.0x)
220
385 (1.0x)
FedGSNR with FedProx
140 (1.3x)
300 (1.4x)
405 (1.2x)
180 (1.2x)
210 (1.8x)
Scaffold
385 (1.0x)
(1000)
81.0 x) 390 (1.0 x)
>KK
FedGSNR with Scaffold
140 (2.7x)
425 (1.8x)
770
170 (2.3
>KK
To ensure all methods are comparable, we need to set the total computation, i.e., local updates, to be equal. So in FedGSNR, we set the local updates for different participants to be E
ond
N Econst E "1.: where N and Econst represent the active participants and the local updates of baseline algorithms respectively. Note that Eg is redistribution local steps.
Pik
The necessity of optimal local updates. To understand the necessity of optimal local updates, calculate the entropy of the local steps, ie., H
Ek= p(Ck) log ((C)), opt
0.2
where p(Cx) ΣK EK,n mppp, and the re-
sults are illustrated in Fig. 3 Specifi- cally, the dashed blue line on the top is the uniform distribution of local updates, which is the maximum entropy distribu- tion of discrete variables, and it repre- sents the equal local updates among all participants. Moreover, when the degree of non-iid increases, the computation is allocated more concentrated, i.e., a smaller entropy. On the contrary, the entropy converges its maximum when the distributed data is closer to iid. Additionally, the corresponding convergence rate is illustrated in Table which indicates that the re-allocation of local updates based on FedGSNR accelerates the model convergence.
04
Fersaree reator mas (25
Rachimur coue
Nenbolace
205
500
200
433
#50
2000
Figure 3: The entropy of lo- cal steps for different parti- tion methods.
Figure 4: Test accuracy of different algorithms with dif- ferent local steps.
The impatet on test accuracy. Versus its original, FedGSNR achieves comparable test accuracy and even outperform its original when the non-iid degree increases. For example, in Pareto scenario, the accuracy of FedGSNR with FedProx achieves an increase of 6.43%. More detailed results can be found in Appendix D.2
(a) Test accuracy
(b) GSNR
(a) IID
(b) NonBalance
Figure 5: An imbalanced scenario with Pareto partition on CIFAR-100 dataset.
Figure 6: The variation of GSNR when we change the labels of a specific participant.
Model convergence of FedGSNR. During experiments, set μ 0.01 for FedProx, and compare the performance different algorithms to its combination with FedGSNR. Then according to Table
SSpeedup Karimireddy et al. 2020 i.c.,
measures the relative performance of two methods. Tnew
Tatd.
8

---

Under review as a conference paper at ICLR 2023
Table 2: Communication rounds to reach 0.5 test accuracy for classification on NonBalance CIFAR-10 of 100 participants as we vary the number of active clients.
10%
20%
100%
FedAvg
210 (1.0%)
140
(1.0%)
FedNova
235 (0.9x)
(1.0x
(1.2x)
Scaffold
230 (0.9x)
FedGSNR with FedAvg
150 150 (1.4x)
80 (1.7x)
55 (1.8%)
FedGSNR with different algorithms achieve faster convergence versus its original, and it reaches 1.69 speedup on average with comparable accuracy. The corresponding accuracy can be found in Appendix D.2 Besides, Fig. 4 iillustrates the accuracy when we set different number of Econst- and FedGSNR with FedAvg converges faster and achieves better accuracy with different local steps (Scaffold fails to work when we set Bconst 25). Moreover, in practice, Pareto's 's Law is common principle, which means a small number of participants possess large number information. Fig. 5()) indicates that FedGSNR with different algorithms converge faster and reaches comparable accuracy. Meanwhile, the GSNR of different participants are resemble to their label distribution (the histogram on the bottom of Fig. 5(b)), which demonstrates GSNR can distinguish the information quality between different local datasets. Furthermore, Table @ indicates that the growth of active clients speeds up the convergence of different algorithms. Particularly, FedGSNR gains more benefit from global information as its speedup increases from 1.4x to 1.8x when active clients grows.
(a) IID
(b) Dirichlet(1.0)
(c) Dirichlet(O.5)
(d) Label 2
Figure 7: The GSNR of different clients. We observe that GSNR larger and almost the same among all participants when data is iid distributed, then it gets smaller and heterogeneous as the non-iid level grows. Finally, when data partition method is Label 2, GSNR is small but similar to each other again, which probably indicates that data is distributed with some symmetries in regard to the information.
Evaluate local contributions with GSNR. Fig. 7 displays the variation of GSNR when we utilize Dirichlet method with different a. And the results demonstrate that when the level of non-iid grows, GSNR of different clients vary dramatically, which represents the contributions of different clients different. Moreover, combined GSNR with the results in Table the model convergence is faster than its opponents when considerate such differences. Further more, to investigate the performance of data evaluation, we change the labels 1 of client O to be (1 + k) mod 10. So that the client provides a label flipping attack (Hitaj et al. (2017). Fig. 6 illustrates the changes of GSNR when change the labels, and the red dashed line box represents the original GSNR when the labels are unchanged. Specifically, we observe that the GSNR dramatically decreases when we make malicious change to the labels. Additionally, we instead change the data points to be sampled from a uniform distribution, and observe similar phenomenon. For both of malicious changes, we observe FedGSNR is more robust. Due to the limited space, we send these experiments to Appendix D
6 CONCLUSION
In this paper, we have investigated the FL problem via new perspective, i.c., GSNR. Our theoretical analysis indicates that under non-iid scenarios, the local updates can be decomposed into signal and noise components, and we can maximize GSNR with the optimal local updates. Based on theoretical analysis, we further propose an algorithm FedGSNR to calculate the optimal local updates for different FL algorithms, which achieves faster global model convergence. Additionally, we derive a method to calculate GSNR directly from the local datasets, which can be utilized to evaluate the local contributions of different participants. Finally, extensive experimental results demonstrate the beneficial effect of optimizing FL from the new perspective of GSNR, and also open up a promising new direction for follow-up research.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N. Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In Proceedings of ICLR. OpenReview.net, 2021.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How To Backdoor Federated Learning. In Proceedings of AISTATS, pp. 2938-2948, 2018.
David Balduzzi, Marcus Frean, Lennox Leary, J. P. Lewis, Kurt Wan-Duc Ma, and Brian McWilliams. The shattered gradients problem: resnets are the answer, then what the question? In Proceedings of ICMI., 2017.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Local Model Poisoning Attacks to Byzantine-Robut Federated Learning. In Proceedings of USENIX Security, pp. 1605-1622, 2020.
Farzin Haddadpour and Mehrdad Mahdavi. the Convergence Local Descent Methods in Federated Learning. CoRR, abs/1910. 14425, 2019.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck R. Cadambe. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization. In Proceedings of ICML, volume 97, pp. 2545-2554. PMLR, 2019.
Briland Hitaj, Giuseppe Ateniese, and Fernando Pérez-Cruz. Deep Models Under the GAN: Infor- mation Leakage from Collaborative Deep Learning. In Proceedings of CCS, pp. 603-618. ACM, 2017.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. CoRR, ftbs//999.06335, 2019.
Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. CoRR, abs/1909. 12488, 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In Proceedings of ICML, pp. 5132-5101 5143, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter Theory for Local SGD on Identical and Heterogeneous Data. In Proceedings of AISTATS, pp. 4519 4529, 2020.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Viraj Kulkarni, Milind Kulkarni, and Aniruddha Pant. Survey of personalization techniques for federated learning. CoRR, abs/2003.08673. 2020.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated Optimization in Heterogeneous Networks. In Proceedings of MLSys, 2020a.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and Robust Federated Learning Through Personalization. In Proceedings of ICML, pp. 6357-63666 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the Convergence of FedAvg on Non-IID Data. In Proceedings of ICLR, 2020b.
Jinlong Liu, Yunzhi Bai, Guoqing Jiang, Ting Chen, and Huayan Wang. Understanding Why Neural Networks Generalize Well Through GSNR of Parameters. In Proceedings of ICLR, 2020.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. CoRR, abs/2002. 10ti19002.1019,, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication Effiicieeffiitttttt Learning of Deep Networks from Decentralized Data. In Proceedings of AISTATS, pp. 1273-1282, 2017.
10

---

Under review as a conference paper at ICLR 2023
Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting Unintended Feature Leakage in Collaborative Learning. Proceedings of IEEE SP (Oakland), pp. 691-706, 2019.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic Federated Learning. In Proceedings of ICML, pp. 4615-4625, 2019.
Yurii Nesterov. Introductory lectures convex programming volume i: Basic course. Lecture notes, 3(4):5, 1998.
Tom Rainforth, Adam R. Kosiorek, Tuan Anh Le, Chris Maddison, Maximilian Igl, Frank Wood, and Yee Whye Teh. Tighter Variational Bounds are Not Necessarily Better. In Proceedings of ICML, pp. 4274 4282, 2018.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný. Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive Federated Optimization. Proceedings of ICLR, 2021.
Khe Chai Sim, Petr Zadrazil, and Françoise Beaufays. An investigation into on-device personalization of end-to-end automatic speech recognition models. In Interspeech 2019, 20th Annual Conference of the International Speech Communication Association, Graz, Austria, 15-19 September 2019, pp. 774-778. ISCA, 2019.
Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collabora- tive machine learning with incentive-aware model rewards. In Proceedings of ICMI., volume 119 of Proceedings of Machine Learning Research, pp. 8927-8936. PMLR, 2020.
Cédric Villani. Optimal transport: old and new, volume 338. 2009.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris S. Papailiopoulos. and Yasaman Khazaeni. Federated Learning with Matched Averaging. In Proceedings of ICLR, 2020a.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization. In Proceedings of NeurIPS, 2020b.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting Hc, and Kevin Chan. Adaptive Federated Learning in Resource Constrained Edge Computing Systems. IEEE Journal on Selected Areas in Communications, (((6):200-122)) 2019.
Dong Yin, Ashwin Pananjady, Maximilian Lam, Dimitris S. Papailiopoulos, Kannan Ramchandran, and Peter L. Bartlett. Gradient diversity: a key ingredient for scalable distributed learning. In Proceedings of AISTATS, volume 84, pp. 1998-2000 PMLR, 2018.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD) with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of AAAL pp. 5693-5700. AAAI Press, 2019.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep Leakage from Gradients. In Proceedings of NeurIPS, pp. 14747-14756, 2019.

---

Under review as a conference paper at ICLR 2023
A
RELATED WORK
Gradient Diversity. Gradient diversity is key ingredient of federated learning, which captures the differences between the datasets possessed by different participants. Yin et al. (2018) employs gradient diversity to investigate the relationship between batch size and the convergence rate in parallel SGD. Yu et al. (2019) analyzes why periodical model averaging is suitable for deep learning, and provides a deep understanding of model averaging. Haddadpour et al. (2019) tries mitigate gradient diversity through sharing small batch of data among all participants, but also introduces a higher privacy risk. Accrr et al. (202I) introduces a dynamic regularization term to resolve the problem of gradient divergence. However, most of previous literatures try to solve gradient diversity through gradient calculating, such as gradient prediction, regularization, personalized target function and However, the influence of local updates gains less attention. In this paper, we propose new perspective to analyze the optimization procedure by Gradient Signal to Noise Ratio, it reduces the required communication rounds via elaborate configuration of local updates and propose method to evaluate the contributions different participants.
Personalization in federated learning. Another important problem in federated learning is personal- ization. Formally, personalization transform the optimization problem from global distribution p(E) specific local distribution p(E C₂) on client it scarifies the global performance in order to gain more benefit in local scenario. Kulkarni et al. (020)) reviews the investigations of personalization, and the situations are divided into three categories: device heterogeneity. data heterogeneity and model heterogeneity, while the last one is the motivation of personalization, Mansour et al. (2020) proposes three methods to achieve personalization, these methods try to balance the model performance on global data distribution as well as local data distribution. [Sim et al.] (2019) proposes method to optimize global model and local model separately in order to make local model more personalized. Jiang et al. (2019) proposes three objectives to make personalization easily. However, personalization is an important topic in federated learning since different participants confront different problems, but if we greedily utilize global information for personalization, there is likely to appear Prisoner's Dilemma, the collective benefit for all participants is not optimal and therefore, the profit for each participant can probably be futher improved. Hence, cooperation is also important problem, and a better goal of personalization is to search optimum on conditional data distribution p(E C2) combined with cooperation.
B PROOFS OF LEMMA AND THEOREM
B. PROOF OF LEMMA 3.2
Proof. For any constant gradient vector g can be rewritten as
B
V w Flo1, (w01) E1o)), -r. V FwFF(w En,
B
let 9. = E1,b),, ..., F {n,b))), we further have
1
gb.
B
then with Assumption 3.1 and n a constant, 9b is subject to some complex distribution with bounded covariance matrix. As E,, is iid sampled from a specific dataset, g is the mean vector of
gl. ... GB. which are iid random vectors.
Therefore, based on the classical Central Limit Theory, with B growing large, vB(g EEg) converges (0, Σ) in distribution, where Σ is the covariance matrix of g.
B.2 PROOF OF LEMMA 3.5
Proof. First, we prove lim ||||,,|| 0.
000
12

---

Under review as a conference paper at ICLR 2023
Regarding the gradient 9t, i {1,... nn. due to the smoothness of W F E), we expand 9: based on Lagrange's s mean value theorem as
w Fww; {,) Vu F F.... ())+ & (w, ww) 91.++ & (ww w1).
(10)
where vi == Aw + (1 A)w, À [0, 1}, and I1.: represents the gradient at w, with sample &,. which is an unbiased estimator of g1- Note that when * j. 91, is independent of gıj- Then
(a) - E B g. 91.1l - (F (w) wi)ll
E (F & MIll(w, w1)l
(11)
(((ú, & &)) w1 1 (c)
i-1
L.
EE 11
Σ 9;
j=1
L2 Tr
(i- 1) _
E |
12
(i LG,,GG 2
where (a) follows from sub- sub-multiplicative property of matrix norm, (b) is based on Cauchy-Schine Seehwr inequality, (c) an immediate consequence of Assumption 3.4aand and the local optimization process,
t (d) comes from the fact > a;1l² S 1= ||a;11", and (e) is based on Assumption 3.1
where
G = ṭ² + 2² μ = max { |4: llke (1,...)) Hence,
E E||,|||
Elgg
9ll E|| Σ g: 91.))ll Σ
Elig: g1
LG n(n - 1) LG
where the first inequality follows from the triangle inequality, and the second inequality is based on Eq. (1).
As n represents the number local steps, which is constant, E er is upper bounded by yr- M, where M is a bounded value. Therefore,
0 s lim B||e,11 & lim Br M 0. ++00
(12)
Formula implies e, converge to 0 in mean, i.e., er 4 O, which immediately completes the proof.
B.3 PROOF OF THEOREM 3.7
Proof. According Eq.
minimize the distance between N( o Eg B ), we can build an optimization problem as
and
NTTT, n² Eg
min d² = || -nn- -m11111 + tr(M2)
(13)
1/
2 E
s.t. M
B
B
2 0.
Note that Eq. L3 quadratic function of n, which immediately completes the proof.
13

---

Under review as a conference paper at ICLR 2023
B.4 PROOF OF COROLLARY 3.8
Proof. In this case, we change the distribution N Mg. 1hr B) to (mmn mxj 2e). B
and refor-
mulate problem 13) as
min d² = m² (1
-1, -..ppp [
1|2 (r((M)))
m
Eg
1
Zi
M = s.t.
B
B
n 2 0,
let d = d and ñ immediately.
m then the new problem reduces to problem
13
which concludes the proof
C DETAIL ANALYSIS OF GSNR
F'(w )
F"(, C2)
Steps
("(w,
Optimal & Steps
W2
Optimal disttance
W
Steps
W1
Figure 8: A similar case in Euclid space: ideal optimization path discrete, there optimal distance between global updates and multiple local updates. Further more, when global updates converge to the optimum, the local updates converge to the nearest point the optimum.
Figure 9: A representative scenario of GSNR: r(w) a random variable with re- gard to w. If get closer to the optimum of C2. GSNR of C1 will increase and the GSNR of C2 will decrease. While if we get closer to the optimum C1, the situation changes in the opposite way.
According to Fig. 8 the stochastic gradient descent algorithm converges to the e-neighborhood of optimum after constant steps (usually more than O ) Nesterov (998)). For convenience, we refer such a constant as the optimal Mopt- In practice, as Fig. - indicates, with determined differences between global distribution and local distribution, i.c., maximal GSNR is constant during specific round, set the target global steps as Mopt is an optimal choice. However, a large number of m leads to a large error of gradient estimation, which is determined by Onn?n? Hence, in practice, in order to decide m, we need trade off between the estimation error and the corresponding convergence rate.
Then we focus on Definition 4.1 the function to calculate GSNR. Specifically, Cauchy-Schward inequality implies that 2 > 0, and the equality holds when local distribution is the same as the global distribution, i.c., the data is iid distributed among all participants. With A decreases, which implies local data distribution approaches the global data distribution, opt gradually increases. Moreover, when A reaches its minimum 0, n2 attains its maximum value 1. Based on the analysis, we can conclude that the more similarity between local dataset and the global dataset, i.e., the larger GSNR the local dataset achieves, the more local updates we need for optimization procedure, which is heuristically experimented in Li al. 2020b).
To calculate GSNR, we derive r(w) as Definition 4.1 and r(w) is positive related to n On the one hand, when n 0. from its definition, we know that < R₁, R,, > p= 0, hence optimal distance A achieves its maximum ||y. and r(w) attains its minimum 0. On the other hand, when local distribution is the same the global distribution, i.e., A 0, r(w) 400, we treat this
14

---

Under review as a conference paper at ICLR 2023
scenario as a noiseless optimization procedure, and the data is iid distributed among each participant. Therefore, r(w) ) (0, +-0)..
With former analysis, we know r(w) E (0, +oo). On the one hand, as the data is iid distributed among all participants, ie., GSNR goes to +oo, the distributed optimization is a noiscless procedure, which means the local updates is unbiased. On the other hand, when GSNR is O, which means < Ry Rg >p 0, the angle between local gradient and the global gradient is greater than 90' In other words, for current optimization, local data distribution independent of global data distribution, thus for global optimization, it is no better than a random guess, then its signal component will be set to 0, which leads GSNR to be O.
As for the relationship between GSNR and the parameters w, Fig. 9 displays a representative scenario. Due to the randomness of SGD, the new parameters after w with another aggregation can be either wy or w22 On the one hand, if the parameters w2, which means we get closer to the optimum of client C2, there are different changes of the GSNR for different clients: for C₁, the GSNR increases, while for C2, the vector is almost orthogonal to global optimization vector, which implies GSNR closer to O. On the other hand, if the parameters is Wzy which is closer to optimum of C₁, the phenomenon is slightly different: the GSNR of C₁ decreases and the GSNR of C2 increases. Hence, during the training process, r( r(w) is a random variable correlated to the random process w, and tend to use GSNR to evaluate the contribution of different participants, we need to observe its statistics, i.e., mean or median.
D DETAILS OF EXPERIMENTS
D.1 DIFFERENT METHODS OF DATA PARTITION
Dirichlet partition. we follow the settings in Hsu et al. 2019) to generate non-iid data across different participants by Dirichlet distribution. Specifically, the prior distribution is set to be Uniform, and then the parameter represents the level of concentration. With + +oo, the data distributions of all participants tend to be identical, hence the data is iid distributed among all clients. While each participant only possesses data chosen from just class, i.e., label for each participant. As for Label 2., it is a specific partition method in Hsu et al. (2019). and each client owns the data sampled from 2 classes.
Non NanBalence partition. For NonBalance partition, we tend to simulate the practical scenario of imbalanced information distribution. Specifically, We divide all participants into three categories: abundant information, medium information and less information, which represent the clients possess data chosen from different number of labels. First, for clients with abundant information, we random chose data from all labels, and the number of them is 10% of total clients. Second, for the clients with medium information, we random chose 50% classes for each client, then distribute data randomly according to their chosen labels, and the ratio of them is 40%. Finally, for the clients with less information, the number of labels reduces to 20%, and the ratio of them raises to 50%.
Pareto partition. In practice, Pareto distribution is common scenario. It represents the long tailed distribution of practical scenario such as the degree of nodes in complex network, the distribution of social wealth, the distribution of followers in social network, etc. Hence, design Pareto partition to simulate the so called Two-Eight distribution in practice. First, we sample N points from Pareto distribution,
Roand g
if x 2 Xmán otherwise.
p(x)=
0.
Where N represents the number of clients. Denote the corresponding samples as X ( and we normalize x; with ã; xz/ max (X) to guarantee all data distributed in [0, 1]. Finally, we use E as the ratio of classes possessed by different clients for random sampling, and set the minimum number of labels among all clients to be 1.
D.2 ADDITIONAL EXPERIMENTS
Fig. I0 displays the change of GSNR and corresponding test accuracy when we apply different malicious change to client. Interestingly, compare Fig. [0(a) and 10(b) with Fig. [O(c) and
15

---

Under review as a conference paper at ICLR 2023
(a) GSNR on IID CIFAR- (b) GSNR on NonBal- (c) GSNR on IID CIFAR- (d) GSNR on NonBalance
10 with Label change.
ance CIFAR-10 with Label 10 with Random imput. change.
CIFAR- 10 with Random in- put.
1e00 ad Halhy Ude Crapoteooss
Load
SM
200 20
(e) Test accuracy on IID (f) Test accuracy on Non- (g) Test accuracy on IID (h) Test accuracy on Non- CIFAR-10 with Label Balance CIFAR-I0 with CIFAR-10 with Random in- Balance CIFAR-10 with change.
Label change.
put.
Random input.
Figure 10: We make different malicious changes to client 0 in different partition methods. In (a) and (b), we change the labels of client to / - 3. While in (c) and (d), the labels remain unchanged, and we change the input data to be a uniform distribution (--1, 1). (e)-(h) are the corresponding test accuracy of different scenarios.
[0(d) we can discover that the decrease of GSNR for random input is larger than label changing. Specifically, it is consistent with our intuition, since malicious attack of label changing contains more information than random input. Simply put, after label changing, the model still gets the information that such data belong to a same class. For example, if we change all labels of 'cat' to 'dog", we still know the data of "cat' belongs to a same class, though we call them 'dog'. On the contrary, the change of random input cannot provide this information.
Table 3: Best test accuracy on CIFAR-I0. We distributed the data among 30 clients, utilize batch size of 64, and set local steps Econst = for different algorithms.
Algorithms
a = 0.5
a = 0.1
Label
NonBalance
Pareto
FedAvg
67.06 %
57.44%
58.25 %
65.48%
57.23% 63.38 %
FedGSNR with FedAvg
66.23%
61.41 %
57.69%
66.42% %
FedProx
63. 14% 63.5%
57.80%
58.84%
63.87%
56.96%
FedGSNR with FedProx
59.39%
58.39%
68.17% %
63.39 %
Scaffold
62.05%
53.98%
50.38%
62.79%
40.73 %
FedGSNR with Scaffold
63.53%
58.95%
55.48%
64.96% %
39.83%
Table 3 displays the corresponding test accuracy of different algorithms aforementioned in Table I and indicates that FedGSNR not only converges faster, but also achieves a comparable accuracy than its opponents. As for the accuracy drop in Table it's possibly because FedGSNR is gradient-based algorithm, if the basic method introduces gradient estimation (i.e., Scaffold), the performance of FedGSNR will be correlated to the precision of such an estimation, and a relatively low precision leads to the corresponding accuracy drop. Meanwhile, as we have illustrated in Fig. 7 the method of Label distributes the data with some symmetries in regard to the information, i.c., the GSNR of each participant are similar to each other, then it's naturally compatible to identical local updates, hence the test accuracy between FedGSNR and its opponents are close each other.
16

---

Under review as a conference paper at ICLR 2023
E
AN EXAMPLE OF CONVERGENCE ANALYSIS
As defined in Sec.
we have
U,
R. =
u
where μl and E, are the corresponding mean vector and covariance matrix calculated by the samples
sampled from D. respectively, and μe, is the component of μ., (H., " p.). Then we have following lemmas. Lemma E.1.
| [elll..ll where B 2
Proof.
First, we have
1e k. = Rglga] " = (r(eeee [e.g)
Note that 2 1, hence
tr Σn,
1.. p.. + (tr(..)
tr(EEg 9-, F5g [g....1 + Σ.)
R. 12 2 = nº u. +
B
B
B
Eg (
Ee Belllg.1111
B
which concludes the proof.
Lemma E.2. If Assumpption 3.1 holds, then |R S G2,, where G2 is the upper bound of EEgllg.!|
Proof. Similarly,
RR. 2| 4. tr(D.)
B S 4. p. +tr(E.) tr(Belo.|Eggg.1 + E.)
= =eeltr(g.g = Relllg. | G
which concludes the proof.
Then analyze the convergence of FedGSNR with FedAvg based on the proofs of Li al. (022b).
For the analysis, we make additional assumptions.
Assumption E.3, The functions F₁ are all L-smooth: for all w and v, Fa( S (x + (v
VF.(w) w)'VFi
+ |
l| - w1l..
Assumption E.4. The functions Fg are all u-strongly convex: for all us and v, Fa(v) 2 Fa(w)
(u-w)"'Al ()) + $ || wl
Assumption E.5. Vk. (1,.... KJ. (())
Where (w) short for F(w: (CC)
The Lemma 1 and 2 in Li et al. (2020b) implies the bound for one step SGD and the bound for the variance of gradients, as they are independent of the number of local steps, we can use them directly.
Lemma E.6. (Results of one step SGD). Assume Assumption E.3 and E. hold. If +. we have
K
E U1+1 w=|l < (1 -1, w.ll + + Elg. gell + 6L 2r + 2E
pk w will.
K where T = _=_ >K Pk Fx
17

---

Under review as a conference paper at ICLR 2023
Lemma E.7. (Bounding the variance). Assume Assumption 3.1
holds, then we have
K Po oo.
9: Dell -
k=1
We focus on Lemma 3 in et al. (2020b), which is related the number of local steps, and we prove that when apply method to decide the number of local steps, the lemma still holds.
Lemma E.8. (Bounding the divergence of w when we use FedGSNR to decide the number of local updates). Assume the assumptions hold, then we have
K
4n/ L2 const BG
E
w S
where w. = P
Since based on our strategy, the local steps is individually decided by Ex.r n Econstt where Eoonst constant. Hence we define the local optimization process as
Proof.
V W Fm.(), 0 < ln Ek,r wi Ek,r St to < Emarx
wo
w +++
(14)
where w = Wto represents the aggregation step, and without loss of generality, to is the initial time of communication round r, Emaz max ( [x S k S 1 1rlsrs R). Then the situation becomes an identical number of local steps, and we prove that the upper bound is independent of Emaz. We use the fact to Emaz, where to represents the last aggregation step before t, 7) is non-in non-increasing and nto < 2m for all to I Emans we have
K
K
E
wi
w
wlll
= E
p 1 - wio) - (w; wio )|a1
k
E
Pkll( (ull(
)13
min Ea. 11)
Ph
B[1
Σ
V w P (1w
smto
K
lo+ Er,
B
E V (1
8=ta
K
Eo
|R
Pk B
Evonst
V V VwF((1113
|
==to
1ot Eo
VBG
Pk Froost
Vie F(w
E F(
A
where inequality (1) depends w; p. and the fact ||a + b1I2 < 2(1aa|1 2b]2) based on the local optimization process Eq. (14). Inequality (3) a consequence of Σ a
Inequality (2)
Ei= ||a. 2 Incquality (4) depends on the Cauchy- inequality, i.c., nppt
R
R and inequality (5) is an immediate consequence of Lemma E.1 and E.2
Then based on the
| L-Smoothness, we have
F(wE)l < 2L(F(wE) F(w")),
similarly, according to the p-strong convexity, we have
V F(w 24((P F(wx)))
18

---

Under review as a conference paper at ICLR 2023
Hence, we can further bound A1
to+ Ek
VBG
A1 S
Pio Fxconst
Σ
(2I(((uug)) F(w"") )))
2p 2p(( (F(w(( F(w*))
1ot Ekr
VBG
Pho Piconst
(2I((F(u)2)) - F(w*)))
V 22((F(uf)) F(w=))
s=to
BG
Σ
pio Eeonet 2p(F(urk)) - F(w*))
(2L(F(w))) F(w")))
4nh E contt L
where the second inequality depends on F(w") = min F(w), and the fact that F(w ( < F(w()) Vt {to..... to + Ek, - 1} (i.c., the process is non-increasing sequence). The third inequality depends on the upper bound of Ek.r, and the last inequality is consequence of 1tto I 21/-
Hence, we have
K
An/ 2 BG L
E
Pk W
w
<
which is related to constant Econst-
Li et al. (020b) by the substitution the upper bound of Then we can prove the Thm.
E Ph wr - -w,
Theorem E.9. Let the assumptions hold, and L, μ. G, defined therein, if we choose 4,2
7 2 max(8k 1, Emar] and the learning rate 1he p(++t)
2 Then FedGSNR with FedAvg satisfies
2k M
[[F(WT)]
1- S
+ 2L||w0 w" w'll),
(15)
7
where
8 romst
BG
M = 0² + 177
4
19


Reviews:
[{"review_id": "vrLxqxGWUm", "reviewer": "Reviewer_kU4r", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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 this paper, the authors investigate the possibility of optimizing a number of local steps in the FedAvg algorithm by minimizing the Wasserstein Distance between global and local gradient distributions.", "summary_of_the_review": "While the idea of the paper is nice, the theory seems to be weak (see Strength And Weaknesses).", "strength_and_weaknesses": "The paper provides a nice and (as far as I know) novel idea of how to use the statistical properties of local datasets in order to optimize the optimization procedure of the distribution problem.\nHowever, I believe that the paper is too empirical and contains the following problems:\n\nMajor:\n1. The paper does not provide convergence rate comparisons of the new method and FedAvg (see https://arxiv.org/pdf/1910.06378.pdf). It is not enough to say \"The convergence of FedGSNR is obvious, as we just change the number of local updates.\" I believe that it is not a trivial task to obtain precise convergence rates for the new method.\n2. Lemma 3.4 and the discussion implies that we can estimate $\\eta_r \\widehat{g}$ with $\\eta_r \\bar{g}$ if $\\eta_r \\approx 0.$ I think that it is not a strong result and probably misleading. This result virtually holds for any two random vectors, not only for gradients. In practice, we want to take $\\eta_r$ as big as possible. Moreover, the smaller $\\eta_r$, the worse we get the convergence rate.\n3. In the proof of Theorem 3.5, the authors say: \"the global gradient distribution can be approximately interpreted as normal distribution.\" It is a very weak argument for the main theorem of the paper. I would like to see more rigorous mathematical calculations.\n4. Theoretically, it is not clear how the maximization GSNR is connected to faster convergence. For instance, is it possible to show that we can guarantee the convergence rate faster than the vanilla FedAvg if we maximize GSNR?\n\nMinor:\n1. In order to calculate $n^{opt},$ the method required the global $\\mu_g$ and $\\Sigma_g$ and local $\\mu_l$ and $\\Sigma_l.$ The authors propose to estimate them using sampling. It would be nice to have an alternative to Theorem 3.5.\n2. How does the formula in (7) depends on $r$?\n3. In order to estimate $\\Sigma_g$ or $\\Sigma_l$, would the method require a large batch size?\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "vp8akIfLJT3", "reviewer": "Reviewer_Dx1S", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 Strength And Weaknesses", "summary_of_the_review": "In Strength And Weaknesses", "strength_and_weaknesses": "This paper speedups model training by maximizing GSNR in FL and provides the optimal local updates from a theoretical viewpoint. However, I'm not an expert in FL and have a heavy review load. Due to my limited time, I can't be more positive at the current stage. I encourage the authors pay more attention on other reviewers' responses as I will make my confidence the lowest.\n\nThough I'm not an expert in FL but I find the theoretical results in Sec 3 are interesting. Thus, I will only give some comments and ask some questions about this part. My questions may be highly biased due to I didn't go through all details in the paper. I would be glad if the authors could point out my misunderstandings.\n\n1. About the upper bound Eqn (6). Why is the target distance (5) approximately minimized when the upper bound is minimized? There might be a gap. It would be better if the authors provide a simple example to verify its possibility in the current setting.\n2. I'm confused by Lemma 3.2 and Lemma 3.4. It seems Lemma 3.4 is to calculate the asymptotic mean and variance by initial weight $w_1$. And the step size goes infinity. But Lemma 3.2 let the minibatch $B$ goes infinity. Could the author tell me more about how to connect Lemma 3.2 and Lemma 3.4 with different asymptotic parameters ($B$ and $r$)?\n\n", "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": {}}, {"review_id": "qbW4s_PMRX7", "reviewer": "Reviewer_zXke", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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 proposes a framework for federated learning with non-iid data. The authors tackle this problem by optimizing Gradient Signal to Noise Ratio (GSNR). They decompose local gradients calculated on the non-iid training data into the signal and noise components and then speed up the model convergence by maximizing GSNR. Based on this, they develop the FedGSNR method, which can be applied to existing gradient calculation algorithms. \n", "summary_of_the_review": "The paper is well-written, although I could not evaluate it with confidence. However, there are several parts where theoretical explanation is insufficient. For example, the authors define the expected value in Section 2, but because the data is non-iid, we can consider samples that do not have the expectation. The authors more carefully discuss them because this paper discusses non-iid data. Furthermore, I could not understand why Lemma 3.2 holds. I would like the authors to clarify it. ", "strength_and_weaknesses": "The proposed framework is general and seems to be applied to various existing methods. The non-iid data issue is important in this fields, and the authors address the problem well. Unfortunately, I am not familiar to this topic. Therefore, I cannot assess the exact strength and weakness of the proposed framework. I read the paper and could not find significant faults. ", "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": "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": "qQBju05QM3h", "reviewer": "Reviewer_8mk1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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 with heterogeneous data, the gradient of each client is pointing in a different direction when running a local algorithm s.t. local SGD. Since each client performs several local steps, the algorithm deviates from the theoretically better algorithm that would follow the averaged direction of the gradients. \n\nThis paper proposes a technique to reduce this deviation effect and speedup the training algorithm. Based on the Gradient Signal to Noise Ratio, they compute the \"optimal\" number of local steps to reduce the deviation effect. In particular, the number of local steps is not the same for every client.\n\nThe approach relies on making some gaussian approximation for the local training and the global training, computing the Wasserstein distance for the deviation between both and computing the number of local steps to minimize the deviation.", "summary_of_the_review": "The idea is original but not well executed.", "strength_and_weaknesses": "Strength\n\n- The approach to compute the optimal number of local updates is original and flexible, can be applied to virtually any local optimization algorithm\n\n-The method allows for a different number of local updates for each client, and allows for measuring the contribution of each client\n\nWeaknesses\n\n-GSNR is computed on the basis of several approximations. We don't know how far is the estimated optimal number of local updates from the true optimal number of local updates. In general, the fact that the approach is based on several approximations is really not discussed\n\n-The goal of the GSNR approach is to accelerate the training. Acceleration is only shown experimentally", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject