FedGC: An Accurate and Efficient Federated Learning under Gradient Constraint for Heterogeneous Data
Authors: Peng Liu
Jie Du
Chi Man VONG
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Non-IID data

Abstract: Federated Learning (FL) is an important paradigm in large-scale distributed machine learning, which enables multiple clients to jointly learn a unified global model without transmitting their local data to a central server. FL has attracted growing attentions in many real-world applications, such as multi-center cardiovascular disease diagnosis and autonomous driving. Practically, the data across clients are always heterogeneous, i.e., not independently and identically distributed (Non-IID), making the local models suffer from catastrophic forgetting of the initial (or global) model. To mitigate this forgetting issue, existing FL methods may require additional regularization terms or generates pseudo data, resulting to 1) limited accuracy; 2) long training time and slow convergence rate for real-time applications; and 3) high communication cost. In this work, an accurate and efficient Federated Learning algorithm under Gradient Constraints (FedGC) is proposed, which provides three advantages: i) High accuracy is achieved by the proposed Client-Gradient-Constraint based projection method (CGC) to alleviate the forgetting issue occurred in clients, and the proposed Server-Gradient-Constraint based projection method (SGC) to effectively aggregate the gradients of clients; ii) Short training time and fast convergence rate are enabled by the proposed fast Pseudo-gradient-based mini-batch Gradient Descent (PGD) method and SGC; iii) Low communication cost is required due to the fast convergence rate and only gradients are necessary to be transmitted between server and clients. In the experiments, four real-world image datasets with three Non-IID types are evaluated, and five popular FL methods are used for comparison. The experimental results demonstrate that our FedGC not only significantly improves the accuracy and convergence rate on Non-IID data, but also drastically decreases the training time. Compared to the state-of-art FedReg, our FedGC improves the accuracy by up to 14.28% and speeds up the local training time by 15.5 times while decreasing 23% of the communication cost.

Under review as a conference paper at ICLR 2023
FEDGC: AN ACCURATE AND EFFICIENT FEDERATED LEARNING UNDER GRADIENT CONSTRAINT FOR HET- EROGENEOUS DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Federated Learning (FL) is an important paradigm in large-scale distributed ma- chine learning, which enables multiple clients to jointly learn unified global model without transmitting their local data to a central server. FL has attracted growing attentions in many real-world applications, such multi-center cardio- vascular disease diagnosis and autonomous driving. Practically, the data across clients are always heterogeneous, i.e., not independently and identically dis- tributed (Non-IID), making the local models suffer from catastrophic forgetting of the initial (or global) model. To mitigate this forgetting issue, existing FL methods may require additional regularization terms or generate pseudo data, re- sulting to 1) limited accuracy; long training time and slow convergence rate for real-time applications; and 3) high communication cost. In this work, an accurate and efficient Federated Learning algorithm under Gradient Constraints (FedGC) is proposed, which provides three advantages: i) High accuracy is achieved by the proposed Client- Granit--radint---ee Constraint based projection method (CGC) to alle- viate the forgetting issue occurred in clients, and the proposed Server- -ranien-- Constraint based projection method (SGC) to effectively aggregate the gradients of clients; ii) Short training time and fast convergence rate enabled by the pro- posed fast geeudo-gralient -based mini-batch Gradient Descent (PGD) method and SGC; iii) Low communication cost required due the fast convergence rate and only gradients are necessary to be transmitted between server and clients. In the experiments, four real-world image datasets with three Non-IID types are evaluated, and five popular FL methods are used for comparison. The experi- mental results demonstrate that our FedGC not only significantly improves the accuracy and convergence rate on Non-IID data, but also drastically decreases the training time. Compared to the state-of-art FedReg, our FedGC improves the ac- curacy by up to 14.28% and speeds up the local training time by 15.5 times while decreasing 23% of the communication cost.
INTRODUCTION
Federated Learning (FL) enables multiple participations / clients to collaboratively train global model while keeping the training data local due to various concerns such as data privacy and real-time processing. FL has attracted growing attention in many real-world applications, such as multi-center cardiovascular disease diagnosis Linardos et al. (2022). Homomorphic Encryption- based healthcare system Zhang al. (2022), FL-based real-time autonomous driving Zhang et al. (222a)); : et al. (2022), FL-based privacy-presee
vehicular navigation Kong et al. (2021), Fas-b automatic trajectory prediction Maacheerzyyk et al. (202T): Wang et al. (2022). However, in practice, the data across clients are always heterogeneous, i.e., not independently and identically distributed (Non-IID) (Sattler et al. 2020 Zhang et al. 2021b), which hinders the optimization con- vergence and generalization performance of FL in real-word applications. At each communication round, client firstly receives the aggregated knowledge of all clients from the server and then lo- cally trains its model using its own data. If the data Non-IID across clients, the local optimum of each client can be far from the others after local training and the initial model parameters received from server will be overridden. Hence, the clients will forget the initially received knowledge from

---

Under review as a conference paper at ICLR 2023
the server, i.e., the clients suffer from the catastrophic forgetting of the learned knowledge from other clients Shoham et al. ( Xu et al. (0022) In other words, there is a drastic performance drop (or loss increase) of model on global data after local training (as detailed in Appendix A.
Recently, several approaches have been proposed to mitigate the catastrophic forgetting in FL, c.g., Federated Curvature (FedCurv) (Shoham et al. 2019) and FedReg Xu al. (2022). FedCury uti- lizes the continual learning method Elastic Weight Consolidation (EWC) [Kirkpatrick et al.] 2017) to penalize the clients for changing the most informative parameters. The Fisher information matrix is used in EWC to determine which parameters are informative. However, EWC is not effective for mitigating the catastrophic forgetting Xu et al. (2022) in FL, and FedCurv needs to transmit the Fisher matrix between the server and clients besides model parameters. That significantly increases the communication cost (2.5 times than the baseline FedAvg Xu et al.. (2022). ). In addition, the cal- culation of Fisher matrix drastically increases the local training time. FedReg (Xu et al. 2022) is the most recently proposed FL. method inspired by the continual learning method Gradient Episodic Memory (GEM) Lopez-Paz & Ranzato (2017). GEM alleviates the catastrophic forgetting by avoid- ing the increase of loss at previous tasks. However, it requires an episodic memory to contain the representative samples from all previous tasks, which hinders it from being suitable for FL due to data privacy concerns Xu et al. (2022). To resolve this, each client in FedReg firstly generates pseudo data by encoding the knowledge of previous training data learned by the global model, and then regularizes its model parameters by avoiding the increase of loss on pseudo data after local training. Although it uses generated pseudo data to protect data privacy and alleviate the forgetting issue in FL, the data generation will increase a lot of computational and storage costs for clients, es- pecially when clients have large-scale data. In addition, the generation of pseudo data and parameter regularization also significantly increase the local training time. Therefore, these methods are not friendly enough to many real- time applications that concern communication & computational costs.
In this work, we propose an accurate and efficient Federated Learning algorithm under Gradient Constraints (FedGC) to improve the performance of FI. on Non-III data and reduce the local train- ing time. At client, fast Pseudo-ge Pseudo-gradient muddient-busel mini-batch Gradient Descent (PGD) algorithm is proposed to reduce the local training time while accelerating the convergence rates of FL. The pseudo gradient of a local model is obtained by calculating its gradients over few mini-batches data using gradient descent algorithm. In addition, to mitigate catastrophic forgetting, we propose an effective Grreiien-raditt---e Constraint based projection method (CGC). Different from GEM requir- ing memorized data from other clients and FedReg generating pseudo data at clients, our CGC only utilizes the server gradient (i.e., the aggregated gradient from all clients) to restrict the projected gradient to satisfy the constraint: the angle between these two gradients is less than 90', in order to enable the local model retains more knowledge received from server. Meanwhile, the projected gradient is also forced to be as close as possible to the pseudo gradient, that enables the local model to learn new knowledge from local data. At server, we propose a Server-Gradient Grastien--Constraintt based projection method (SGC) to achieve an optimal server gradient which involves the information of clients participated in aggregation while accelerating the convergence rate by restricting the angles between the server gradient and gradients of participating clients to be less than 90", Moreover. our FedGC only transmits the gradients between the server and clients. In other words, our FedGC greatly saves communication costs. The contributions are summarized as follows,
i) High accuracy of our FedGC on Non-IIID data achieved by the proposed CGC to mitigate the catastrophic forgetting occurred in clients and the proposed SGC to effectively aggregate the gradients of clients;
ii) Short training time and fast convergence rate in our FedGC are enabled by the proposed fast PGD method and SGC;
iii Low communication cost is required in our FedGC due to the fast convergence rate and only gradients be transmitted between server and clients;
iv) Extensive experimental results illustrate that our FedGC not only improves the performance of
FL on Non-IID data with a fast convergence rate but also significantly reduces local training time.
2

---

Under review as a conference paper at ICLR 2023
2
RELATED WORKS
Federated learning is an important paradigm in large-scale distributed machine learning. It enables multiple clients to jointly learn a unified global model without transmitting their local data to a central server (McMahan et al. 2017 Bhagoji et al. 2019 Yang al. 2019). FedAvg (McMahan jet al. (0177) is the most popular FL algorithm. In FedAvg, chients first locally train models on local data, and then their model updates (e.g., parameters) are transmitted over the network to a central server, where the updates are aggregated. However, data in many real-world applications are al- ways Non-IID, which degrades the performance of FedAvg and slows down the convergence rate Li et al. 2020; 2018); Xu et al. (2022). Many approaches have been proposed to improve the per- formance and accelerate the convergence rate of FedAvg. Except FedCurv and FedReg, two more popular FL methods resolving the Non-IID are introduced here, including FedProx (Li et al. 2018) and Stochastic Controlled Averaging algorithm (CCAFFOLD/Karrmireed
al. (2020). Similar to FedCurv, FedProx (Li et al.) 2018) tackles the heterogeneity in FL by adding a regularization term (i.e., the Proximal term) in local objective function. The proximal term represents the l2 distance between the local model parameters and the initial (global) model parameters. During local training, FedProx minimizes the local loss while restricting the local updates to be close to the initial (global) model. FedProx takes the same communication costs FedAvg because it does not transmit addi- tional information besides model parameters. However, compared to FedCurv, it lacks of flexibility of model parameters and its stiffness comes at the expense of accuracy. SCAFFOLD (Karimireddy eet al. 2020) introduces the control variates e and e; to correct the client-drift on Non-IID data in local training. The control variates and C; aim to guide the local model to update based on the average gradient of participating clients in the previous communication round. However, the variate c; has the same dimension with the gradient and transmitted between clients and server, which doubles the communication costs compared with FedAvg. Moreover, the average gradient in the pre- vious communication round may not satisfy its assumptions that Gj ~ 9j (36) and c N Σ, 95 ()()),
especially when deep learning models on image datasets perform at clients Li
2021
Notably, all the above FL methods rely on stochastic gradient descent (SGD) to train models at clients by performing multiple epochs on full local data. That significantly increases the local train- ing time of clients. In addition, the clients owning small training data need to wait a long time before the clients with large-scale data complete local training. That not computationally efficient in practice and increases the latency between clients. Minibatch SGD (Woodworth et al. (0220) is recently proposed to perform local training of clients on several mini-batch data at the same model, and then it calculates the mean gradient by averaging the gradients.
3 METHOD
Given K clients, each client k has a local dataset Dr. DD, = {xx, yk } C D3 represents a few mini- batches data including n& samples. Let T be the number of communication rounds, B be the number of mini-batches for local training. At each communication round, a subset of clients K. S [K] are sampled uniformly like FedAvg. In the f-th communication round, 0t represents the parameters of the global model at server and 0f is the parameters of the local model at client k. g represents the gradient of client i: on its local data after local training, g is the server gradient that is obtained by aggregating local gradients of clients. Notably, the gradient mentioned in this work is the negative gradient for the convenience of calculation.
3.1 LOCAL TRAINING WITH PGD AND CGC
At the t-th communication round, clients would firstly receive g' of the previous round, and then synchronize the parameters of local models with g' to ensure clients have the same initially parameters. For client & E K. with its mini-batches data DRx the objective function is given by,
0 4k)
ming; L(f (() yk)
s.t.
(I)
30
where (.) represents the inner product operation. f f(0) xx) represents the prediction of local model at client with parameters o and input Tg. L(f(O', 2x), yv)) is the loss function client on its local data D3 and
3

---

Under review as a conference paper at ICLR 2023
L(f (zze 0%): uk) = [D&l (3R,t.3R.
Σ
LKf( (.))),,;8)).. yk.)))
(2)
The constraint in problem indicates that the angle between the current gradient 8Lif(a (0) m.s))
00,
and the server gradient gf-Tis is less than 90" In this way, during local training, the update direction of local model will be not only learned from local data but also restricted by the server gradient. The server gradient obtained by our SGC involves the update direction of clients participated in aggregation detailed in Section 3.2. Hence, through solving problem the local model will convergence to the global optimum.
However, T is an optimization problem with inequality constraints, which cannot be directly solved by SGD. Hence, we divided the solution into two steps, as shown in Figure
Step 1: Pseudo-gradient-bie -basd mini-batch Gradient Descent (PGD)
At t-th communication round, for client & E K. with its local data D2, the loss function Eq. is first minimized,
0 H
ming, ((f ok,
(3)
0
d1 K(
36
o6
96 m. Ua.1"
6
where 0 is the model parameters after B mini-batches.
0
Clicat
Client
Mini-batch update: Instead of performing multiple epochs on full local data in each com- munication round like in FedAvg, we prefer to use few mini-batches to train local model to save local training time and avoid the latency between clients. Most importantly, when data Non-III, too many iterations in local train- ing may cause local models to be biased to- wards their local data and enlarge the differ- ence between the local model and the global the conver-
Local training with PGD and CGC per- formed at two clients of the f-th round. Clients receive the server gradient g (-1 before local training. At step 1, local models perform PGD compute the pseudo gradients (i.e., g and g by 4 At step 2. clients obtain the projected gradients by per- forming CGC on the pseudo gradients, Since the angle between of and gd is less than 90º, the projected gra- dient client is g itself through CGC. In contrast, the angle between 9 and g" is more than 90", the projected gradient gi is obtained by performing CGC (red arrow) on g satisfy constraints of (5. g and Ié (green arrows)
Figure 1:
three mini-batches, and
model. This is not conducive gence of global model. The experiments of Fe- dAvg using mini-batch update in Appendix A.7 can verify this statement.
the mean gradients used in Mini- batch SGD. The projected gradients usually have larger modulus than the mean gradients.
Pseudo-gradient: During this local training, gh.1 Tk.2. . I in Figure 1 (b) are obtained. Dif- ferent from the mean gradient g% (= hh Ii used in Minibatch SGD that averages multiple gradients for several mini-batches data at the same point (e.g., Oo.)), we prefer to calculate a pseudo gradient g to represent the final gradient after this local training, as shown below.
(0 0%.o
gl
(4)
!7 where og is the initialized model parameters and r) the learning rate.
Compared to the mean gradient g that has similar modulus with each gradient ge S 1 S B, the pseudo gradient O would have larger modulus than gh.- as shown in Figure 1b). In this way, g will promote large update for local model even with only few mini-batches in local training. This will accelerate the convergence rate of FL..
Step 2:
Client-Gradient-Comee
based projection method (CGC)
Since the data cross clients are Non-IID, the angle between the pscudo gradient ğ and server gra- dient gi may be more than 90", as shown in Figure [bb.. That means the update direction of local model deviates from the global optimum, i.e., the catastrophic forgetting occurs at clients. To Client-Gradient
mitigate this forgetting, the Client- Gradient Consttrait based projection method (CGC) is proposed in this subsection.
At t-th communication round, for client & E IC with its local data D&. the optimization problem of our CGC is given by ( In problem (5) the projected gradient 9 should be as close possible
4

---

Under review as a conference paper at ICLR 2023
to the pseudo gradient 9% (in squared L2 norm) while being at acute angle to the server gradient gf
ming 2 | r s.t. (ghe 9 C 2
(5)
where C 1e- -e-3inm is small positive constant to avoid g and g being orthogonal (i.e., to ensure (gkig (e..g"11)) > > 0) after projection.
Through solving problem (5), the projected gradient g will enable the model retain more knowledge received from server while learning new knowledge from local data, i.e., the model can balance preserving the knowledge received from the server and being adaptive local data.
By simplifying problem ( we obtain the primal of CGC Quadratic Program (QP) with inequality constraints:
1 u²u u h² u + 2 h min.. 2
s.t. C -z"u= S 0
(6)
where h h is constant term and can be discarded, u =gk E IR,, h O E RRP and = -g'-1 IR, and p indicates the number of parameters of local model.
Problem (6) QP on p variables and could be measured in millions. Hence, to solve problem (6)
efficiently, we convert the primal problem into dual problem, and obtain the dual the CGC QP:
min. 2² u²=²= z (h"z C)
s.t.
where v E R is a Lagrange multiplier, and problem 7 is a QP on 1 < p variable. To solve problem (7). the python library guadprog is used and then the optimum 2² is obtained. The details of calculating dual of CGC QP are provided in Appendix A.1
Finally, the optimal solution to problem (6) is calculated by u== h + v² i.c., gi 9 +0gg"1 after our CGC. In addition, since the whole concatenated gradient has very large dimension, we iteratively perform the gradient projection layer by layer (i.e., layer-wise manner) to reduce the memory overhead. Theoretical analysis gradient projection is detailed in Appendix A.3
3.2 SERVER AGGREGATION WITH SGC
At t-th communication round, the local gradients (i.e.. 9 of clients are then send to server for aggregation after local training. At server, the aggregated gradient g" (i.e., server gradient) is then send back clients and the parameters 6 of global model is calculated by 0 f- + ngg For aggregation, most FL methods simply use the weighted average of local gradients at server. When the data across clients are Non-IID, the weighted-average may be only effective for few clients. That is because the server gradient may point the opposite directions of some local gradients (i.e., the angle between them are more than 90%), that slow down the convergence rate of FL.
To effectively aggregate the local gradients at server and accelerate the convergence rate, we pro- Conssrrrinn based projection method (SGC). Through our SGC, the pro- jected gradient can point to the positive directions of most local gradients. The optimization problem of SGC is given by,
posed a
ming' 2 | - s.t. (o',git C20, V
(8)
where g' = EbEK "/ of is the weighted average of the local gradients, and N ExeK nik gk is the local gradient of client k. The constraint problem (8) is to restrict the angle between the projected gradient g" and local gradients at participating clients are less than 90"
Similarly, we obtain the primal of SGC QP with inequality constrains by simplifying Eq.
(8
min, 2
-" z g" 79"9
T g s.t. C- C-G= 5
where = g" E RD, R' E RD, and G = (.... .....gg.............. Ii....)T T ERRII h E K. 1 1 is constant term and can be ignored. Problem D is QP on p variables. To solve problem (8) efficiently, we also convert the primal problem ( into dual problem and obtain the dual of the SGC QP:
mInA
s.t. A 2
(10)
where À E R is the Lagrange multiplier, and problem (10) is a QP on ||C| < p variables. The solution A of problem (10) is also obtained by the quadprog library. The details of calculating dual of SGC QP are provided in Appendix A.2
5

---

Under review as a conference paper at ICLR 2023
Finally, the optimal solution to problem 9 is calculated by x" g =g+ G', g' g' GG after our SGC. When the problem (9) is unsolvable, we simply use g' to be g'.
ie..,
The pscudo codes of our method are provided in Algorithm | and the convergence analysis is detailed in Appendix A.4
4 EXPERIMENTS
We conduct extensive experiments to compare our FedGC with several popular approaches, in- cluding FedAvg, FedProx, FedCurv, SCAFFOLD and FedReg, real image datasets. The data preparation and experimental details are described below. The performances are evaluated in three aspects: 1) Overall test accuracy; 2) Convergence rate and training time; 3) Communication costs.
Algorithm 1: FedGC
4.1 DATASETS
Input: K, T, B, datasets D Ukelky 7
the parameters 6 of the global model. Initialize: server 0% clients 0% + 8 for
Output:
The experiments are conducted three real image datasets, including Handwritten-Digite CIFAR-10 (Krizhevsky) (209) and CIFAR-
&E {E(K]:
for = 1 to T do
100 Krizhevsky (2009). The data prepara- tion of each dataset is described below. More
for k [K] in parallel do
# #Synchroni ze parameters if > then
datasets details are provided in Appendix [A.6] 5 Siittrrritten-iiiitt It contains four common
g 9
handwritten- datasets, including MNIST
7
0 - 0 +
LeCun et al. (998), MNIST-M IZhao al. (2022). USPS Hull 1994) and SV SVHN Netzer al. (20TT). Each dataset contains 10 classes. 19
end
Randomly sample clients K. S [K]] for & E IC in parallel do
To input these images into deep models shar- ing the same network architecture, all images pre- pre-processed by re- shaping the size to (32, 32, 3), including the training sets and test sets. The training data are split into clients (named HWDigits-4) and 40 clients (named HWDigits 40) respectively. In HWDigits-4, each client owns one handwritten- digits dataset. In HW Digits-40, each client has 17 images belonging to only one class in a dataset under the one-class setting. HWDigits-4 suf- fers from the attribute skew of Non-IID issue, in which the attributes (i.e., data features) across 20 clients are different. In HWDigits-40, the data 21 across clients may have different labels and at- 22 end tributes, and hence it suffers from both attribute and label skew.
for 6 = 1 to B do
Randomly sample mini--btch data BR Dx; 0 - SGD (0) 7) on Bg.
in these four datasets
end
øi o - # Pseudo
7
gradient
gi - CGC (g). g g-1 in 6
0 + hipi
end
g'
Σ KEK N g/: G c- (... (....gh...... .".
k K:
SGC
(g' G) in
0F 0 n/
"I 1, 0 0 otherwise 0 0%
CIFAR-10 and CIFAR-100 Under the one-class setting, the training sets in CIFAR-10 and CIFAR- 100 are split into 10 (named CIFARIO-10) and 100 (named CIFAR100-100) clients, respectively, i.e, each client owns only samples of one class. All clients share the test sets in original CIFAR- 10 and CIFAR-100 respectively. CIFARI0-10 and CIFAR100-100 both suffer from the label skew under the one-class setting.
4.2 EXPERIMENTAL SETTING
We implement all methods in PyTorch- (Paszke et al. 2019) on a Ubuntu server with two Intel Xen CPUs and 8 NVIDIA RTX 3090 GPUs SGD with weight decay and momentum is used to train local models at clients. For HWDigits-4 and HWDigits-40, CNN similar to (McMahan al.) 2017) is adopted in experiments.
contains two 5x5 convolution layers followed by 2x2 Max- Pooling and two fully connected layers (the first layer with 512 units and the second layer with 100 units) with ReLU activation. The communication round T = 600 and the number of local epochs E in other compared methods is set to 1. The number of local iterations B (i.e., the number of mini-

---

Under review as a conference paper at ICLR 2023
batches for local training) in FedGC is 50. The client fraction is set to 1.0 and the batch size is 100. The learning rates 17 of all methods in experiments are tuned in the range of {0.01. 0.05, 0.1, 1.00, and the optimal 17 of our FedGC is 0.1 and the ones for all other compared methods are 0.01.
The learning rate 1 in FedGC is set to 0.1 and the learning rates other methods are 0.01. For CIFAR10-16 10 and CIFAR 1000000010000 ResNet-9 network with the Fixup initialization (Xu al.) 2022) is trained from scratch. The communication rounds T is set to 500 for CIFARIO- 10 and 1000 for CIFAR 100- E and B 1. The optimal 7) for our FedGC is 0.1 and the ones for all other compared methods are 0.05.
4.3 OVERALL TEST ACCURACY
Table I: Comparison results (%) on four datasets (f). 'wlo' and 'w' denote the server aggregation in FedGC without and with SGC, respectively.
Type of Non-III
Attribute skew
Label skew
Attribute&I Label skew
Method
HWDigits-4
CIFAR1O-10
CIFAR100-100
HWDigits-40
FodAvg
93.07
55,34
40.59
62.11
FedProx
93.69
55.13
32.74
62,01
FedCurv
91.78
55.61
9.48
62.55
SCAFFOLD
92.29
34.40
2.62'
45.32
FedReg
92.32
57.70
53.02
63.05
Our FedGC(w/o)
94.15
59.64
55.73
74.63
Our FedGC(w)
95.27
60.92
56,56
77.33
#samples per client
7,291~-73,257
5,000
500
542~~13.861
It represents model fails to convergence after 1000 communication rounds.
Table 1 shows the overall test accuracies of all compared methods on HWDigits-4, HWDigits-40, CIFAR1O-10 and CIFAR 100-100. In Table [ our FedGC (denotes FedGC(w) if not specified) achieves the highest test accuracies than all other compared methods. Specifically, for HWDigits- 40, our FedGC outperforms the SOTA FedReg by 14.28% (=77.33-63.0) of accuracy, which clearly shows the superiority of our FedGC in tackling the Non-III data. FedCurv is designed based on the assumption that the deep neural networks are over weer-paameterizee enough, so that it has a good probability of finding optimal solution task B in the neighborhood of previously learned task solution. However, for CIFAR I 1001000, there are 100 clients and each client contains only samples of one class. Hence. the assumption of ooeo-voerrttt pereraaaatttiizatioonn cannot be satisfied and it only gets 9.48% of accuracy. FedProx has strong constraints on model parameters, so that it lacks of flexibility, which hinders the learning of new knowledge from the local data. Hence, on CIFAR 100-0001100 100, it also gets worse performance than the baseline FedAvg. SCAFFOLD gets the worst performances on most of the compared datasets, because the average gradient in the previous communication round may not satisfy its assumptions, especially when deep learning models on image datasets perform at clients Li et al. 202T). FedReg is the most recently proposed method, which alleviates the catastrophic forgetting in FL by generating pseudo data. The pseudo data is generated to guarantce that the loss of local model on them is less than that of initial (global) model on them. In this way, the catastrophic forgetting issues can be alleviated. However, when the number of samples between clients varies significantly (e.g., HW HWDigits-4 and HWDigits-40), the FedReg will be biased to the majority clients (i.e., the clients with many samples). That is because the global model is obtained by weighted averaging the model parameters in FedReg and the global model will be biased to majority clients. In local training, the client with few samples (i.e., minority clients) will forget the learned knowledge from local data after regularizing the model parameters with pseudo data in FedReg. In other words, the FedReg has further magnified the bias of global model to majority clients.
Benefited from the proposed CGC, our FedGC mitigates the catastrophic forgetting of FL by con- straining the local gradient at an acute angle to the server gradient and simultaneously minimizing the loss of local model on its local data. Moreover, benefited from the proposed SGC, the projected server gradient in our FedGC can effectively aggregate the knowledge from clients. The gradient projected by both CGC and SGC can reduce the bias toward majority clients. As shown in Table I. FedGC(w) further improves the performances of FedGC(w/o). Particularly, the SGC can further accelerate the convergence rate of FL (as detailed in Section 4.4) Hence, FedGC(w) achieves the highest accuracy on all compared datasets, and the improvements are up to 14.28% (HWDigits-400) compared to the state-of-the-art (SOTA) FedReg. In addition, our FedGC neither transmits extra
7

---

Under review as a conference paper at ICLR 2023
data across the server and clients, needs extra storage costs to keep the generated data. The computational costs of CGC and SGC are also extremely small. Therefore, FedGC is very friendly for edge devices with limited computational resources.
Test accuracy vs. communication rounds four datascts. The black dotted line denotes the highest accuracy FedReg. The red and blue dotted lines represent the round numbers of FedGC and FedReg reaching this accuracy, respectively.
Figure 2:
HWDigits- 4
CIFAR10-10
0.6
0.9
Fechios
FeaCury
0.0
0.7
Test accuracy
0.5
Neefee
0.4
0.6
Test
0.5
0.4
0.3
0.2
0.2
493
0
100
200
300
400
500
600
100
200
400
500
Round communications
Round of communications
(a)
(b)
CIFAR100-100
HWDigits-40
Pishig
Pcolig
0.5
PeSCare
ReCCur
Test accuracy
0.4
Test accuracy
0.6
fectCloorr
0.5
0.3
0.2
0.3
0.1
0.2
0.0
0.1
365
1476
400
800
1000
100
300
400
600
Round of communications
Round of communications
(c)
(d)
4.4 CONVERGENCE RATE AND TRAINING TIME
Figure 2 illustrates that our FedGC can quickly achieve higher accuracies than other methods on all compared datasets until the end of communication. It indicates that our method can improve both the performance and the convergence rate of FL on Non-IID data. The high convergence rate is mainly benefited from our proposed PGD and SGC. FedReg is also proposed for accelerating the convergence rate of FL by alleviating the forgetting issue, but it is more biased to majority clients, that may slow down its convergence rate on HWDigits and HWDigits-40, For HWDigits- 40, FedReg achieves its highest accuracy (63.05%) at round 476 as shown in Figure d while FedGC reaches this accuracy round 365. Meanwhile,
FedGC improves the accuracy by of communication cos compared to FedReg. For CIFAR 100-100, our FedGC also quickly reaches 53.02% of accuracy (I.e., the accuracy of FedReg), which empirically verifies that the projected gradients in both server and clients helpful for FL.. Among compared methods, SCAFFOLD is very unstable during training (as shown in Figures (b) and (d)). In addition, Figure iilussraaes that our SGC can further improve the convergence rate of FL.
14.28% while decreasing 23% (Rs 1- 176x 0
x Ø
Training time another effective way to measure the practicality and efficiency of FL methods. The average training time of each client per communication round are summarized in Table 2 where FedAvg considered the baseline. Due the calculation of proximal term in objective function during local training, FedProx increases training time by about 13s F at each dataset per round. Similarly, SCAFFOL.D also requires more time to calculate and transmit the control variate between clients and server. FedCurv dramatically increases the training time due to the time consuming calculation of Fisher information matrix in every mini-batch. FedReg needs to generate pseudo data during local training, that it also significantly increases the training time. On the contrary, in our FedGC, the gradient projection methods in both clients and server are very efficient due to few
"The calculation is provided in Section 4.5 with FedReg as baseline. |0] denotes the amount of parameters. (67.99+63 65, 15+64.65--00 -2.82..4 (58 63+ 74478.93)
8

---

Under review as a conference paper at ICLR 2023
Figure 3: Test accuracy vs. communication rounds on HWDigits-4 and CIFARIO-10. The black dotted line denotes the highest accuracy of FedReg. The blue, green and red dotted lines represent the round numbers of FodReg, FodGC(w/o) and FodGC(w) reaching this accuracy, respectively.
HWDigits-4
CIFAR1O-10
0.6
0.9
0.7
Toxt accuracy
0.4
0.6
0.5
0.3
Eeding Fo00DAM
FedPag
0.2
138
280
0.1
400
444493
300
400
Round of communications
Round of communications
(a)
(b)
variables in the dual problems. Moreover, all compared methods train local model by performing multiple epochs on full local data, while our FedGC trains local model on few mini-batches in each
communication round. In this way, it will greatly decrease the training time per round, especially for the clients with many samples (e.g., HWDigits-4, HWDigits-40 and CIFAR 100-100), Particularly, our FedGC speeds up the training time by 15.5 (*< 274.72 times compared to SOTA FedReg on HWDigits-40.
17.77
Table 2: The training time per communication round and the communication costs (Comm. cost) (1).
Method
HWDigits
CIFAR10-10
CIFAR100- 100
HWDigits-00
Time(s)
Comm. cost
Time(s)
Comm. cost
Time(s)
Comm. cost
Time(s)
Comm. cost
FedAvg
58.63
557x 0
44,00
480x [0]
44.74
989x |0]
78,93
598x [
FedProx
67.99
439x (0)
65.15
N.A.
64.65
N.A.
82,41
N.A.
FedCurv
970.42
N.A.
1055.01
x90x 2.5
1061.29 2929
N.A.
933.11
578x 2.5
SCAFFOLD
81.21
N.A.
63.99
72.54
N.A.
115.84
FedReg
260.97
N.A.
257.69
431
(9)
260.72
S31 (@]
274.72
476x [
FedGC (our)
6.33
19x (
18.82
327x
39.71
287
(
17.77
387 0
N.A. represents the method has not achieved the target accuracy within maximum communication rounds.
4.5
COMMUNICATION COSTS
The comparison of communication costs is shown in Table 2 We calculate the communication cost by the number of communication round when the method achieves the target accuracy (e.g., the highest accuracy of baseline FedAvg) multiplied by the amount of transmitted data (e.g., the amount of parameters (0). 2.5 represents that FedCurv needs to transmit the Fisher matrix between the server and clients besides model parameters. In Table 2 our FedGC requires the lowest communi- cation costs on four datasets when achieving the target accuracy. Specifically, on HWDigits-4, our of the communication cost compared to FedAvg due to the fewest number of communication rounds. Compared SOTA FedReg, the communication cost can 287x|00
FedGC can decrease 96.6%(s11--) 19x(0]
557x|0
be decreased by 45%(==1- 531x 0
on CIFAR100-100.
CONCLUSIONS
This paper proposes accurate and efficient Federated Learning algorithm under Gradient Con- straints (FedGC) to address the challenging FL scenarios on Non-lID data: Low accuracy, and long local training time. Our FedGC includes several novel modules tackle the issues of Non-IID data: 1) CGC (alleviating the forgetting issue for higher accuracy) and PGD (for significantly shorter training time and fast convergence rate) at client; SGC (for effective aggregation of local gradi- ents) at server. Moreover, FedGC enables low communication cost due to fast convergence rate and only transmissions of gradients between server and clients. Extensive experiments are conducted on four datasets comparing several SOTA FL methods. The experimental results show that FedGC can significantly improve the performance and convergence rate of FL on Non-IID data with low communication and storage costs, The local training time can be drastically reduced. Our FedGC improves the accuracy by up to 14.28% and speeds up the local training time by 15.5 times com- pared to the SOTA FedReg, while decreasing 23% of the communication cost. In nutshell, FedGC has great potential for many real-world applications that concerns performance, real-time, commu- nication & computational costs, and privacy preservation.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference Machine Learning, pp. 634- 643. PMLR, 2019.
J.J. Hull. A database for handwritten text recognition research. JEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5):550-555) 1994. doi: 10.1109/3..211400
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMI.R, 2020.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska- Barsiiskka, al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13):35113522 2017.
Qinglei Kong, Feng Yin, Rongxing Lu, Beibei Li, Xiaohong Wang, Shuguang Cui, and Ping Zhang. crivacy-preserving aggregation for federated learning-basee based navigation in vehieular fog. IEEE Transactions on Industrial Informatics, ((12):8453-840) 2021.
A Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Tront, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. -radient-bbsed learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-22) 2324, 1998.
Qinbin Li, Bingsheng He, and Dawn Song. Model-contrasivee federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10713-10722, 2021.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks, arXiv preprint / 1etp////22..111 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, 2020.
Akis Linardos, Kaisar Kushibar, Sean Walsh, Polyxeni Gkontra, and Karim Lekadir. Federated learning for multi-center imaging diagnostics: a simulation study in cardiovascular disease. Sci- entific Reports, 12(1):1-12, 2022.
David Lopez-Paz and Mare' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017
Nathalic Majeherczyk, Nishan Srishankar, and Carlo Pinciroli. Flow-fl: Data-driven federated learn- ing for spatio-temporal predictions in multi-robot systems. In 2021 IEEE International Confer- ence on Robotics and Automation (ICRA), pp. 8836-8842, 2021. doi: 10. (0.1009/CR//4456622000
9560791.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficcine learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning, 2011.
Anh Nguyen, Tuong Do, Minh Tran, Binh X. Nguyen, Chien Duong, Tu Phan, Erman Tjiputra, and Quang D. Tran. Deep federated learning for autonomous driving. In 2022 IEEE Intelligent Vehicles Symposium (IV), pp. 1824-1830, 2022. doi: 10.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein. Luca Antiga, et al. Pytorch: an imperative style, high- performance deep learning library. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 8026-8037, 2019.
10

---

Under review as a conference paper at ICLR 2023
Felix Sattler, Simon Wiedemann, Klaus-Rober Müller, and Wojeiech Samek. Robust and communication-effiitnc federated learning from non-i... data. IEEE Transactions on Neural Nenworks and Learning Systems, 31(9):3400-3413, 2020.
Neta Shoham, Tomer Avidor, Aviv Keren, Nadav Israel, Daniel Benditkis, Liron Mor- Yos-Yo and Itai Zeitak. Overcoming forgetting in federated learning on non-iid data. arXiv preprint 1eXiv:9100.07796, 2019.
Chunnan Wang. Xiang Chen, Junzhe Wang, and Hongzhi Wang. Apff: Automatic trajectory pre- diction model design under federated learning framework. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Patlern Recognition, pp. 6563-6572, 2022.
Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogencous distributed learning. Advances in Neural Information Processing Systems, 33:6281 16292, 2020.
Chencheng Xu, Zhiwei Hong, Minlie Huang, and Tao Jiang. Acceleration of federated learning with alleviated forgetting in local training. In International Conference on Learning Representations, 2022.
Qiang Yang, Yang Liu, Yong Cheng, Yan Kang, Tianjian Chen, and Han Yu. Federated learning- Synthesis Lectures on Artificial Intelligence and Machine Learning, 13(3):1-007, 2019.
Hongyi Zhang, Jan Bosch, and Helena Holmström Olsson. Real-time end-to-end federated learning: An automotive case study. In 202/ IEEE 45th Annual Computers, Software, and Applications Conference (COMPSAC), pp. 459 468. IEEE, 2021a.
Li Zhang. Jianbo Xu, Pandi Vijayakumar, Pradip Kumar Sharma, and Uttam Ghosh. Homomorphic encryption- based Transactions on Network Science and Engineering, pp. 1-17, 2022. doi: 10.1109/TNSE.2222. 3185327.
federated learning in iot-enabled healthcare system. IEEE
Lin Zhang, Yong Luo, Yan Bai, Bo Du, and Ling- Yu Duan. Federated learning for non-iid data via unified feature learning and optimization objective alignment. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), pp. 4420-4428, October 2021b.
Sicheng Zhao, Xiangyu Yue. Shanghang Zhang, Bo Li, Han Zhao, Bichen Wu, Ravi Krishna, Joseph E. Gonzalez, Alberto I.. Sangiovaani-Viinentee Sanjit A. Seshia, and Kurt Keutzer. A review of single-source deep unsupervised visual domain adaptation. IEEE Transactions
Neural Networks and Learning Systems, 33(2):473-493, 2022.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
A APPENDIX
A. THE DUAL OF CGC QP
Here we provide the procedure of how to convert the primal of CGC QP into the dual problem. The primal problem is:
min, uT u h² hTh s.t. C TT 0
(11)
where R., R and R and indicates the number of parameters of local model. To obtain the dual of (II), we firstly conduct the Lagrange function L(u, v) with a Lagrange multi- plier v E IR as follow
11

---

Under review as a conference paper at ICLR 2023
L(,,0)
u
h² u + - hh v(C =z²u)
2 u u h² u + h + vC - =zzuu) u)
(12)
2
u u (h" + w2" )u + 2 h² h + vC
Because 12 is quadratic convex function, its minimal value be obtained by
VuL(u, u) = u (h+ 1 vz) 0
(13)
u ++
(14)
Hence, the minimal value of (12) is
1
1
L(h + v) = (h + uz) (h + uz)== h²-
hhthh (h + uz) + - h
vCC - -x
x² (h + uz))
2
2
1
(h" + uz 1zz)))) ) (h + uz) h" (h + uz) +
h + 2C uz 3x2Thh (h + uz) (15)
2
2
0²2 vh vC
The dual function G(v) is
G(v) inf L(u, v)
(16)
and the dual problem Therefore, the dual of CGC QP is
max. G(v)
(17)
s.t. 20
min, 20 202=T T +
v(h" C)
(18)
s.t. v 0
Problem (18) can be solved by quadprog library and the optimum v* is obtained. The standard form of QP problem in quadprog is
minx
x Tx axx
(19)
s.t. c
At last, the optimal solution of the primal CGC OP is calculated by u² h u²z.
A.2 THE DUAL OF SGC QP
Here we provide the procedure how to convert the primal of SGC QP into the dual problem. The primal problem is:
min, 2T 2 - g" 2 + g6g g
(20)
s.t. C Gz 5
where z E IR, g E RR, and G E x Problem 20 is QP on variables.
Its Lagrange function with Lagrange multiplier X R is
12

---

Under review as a conference paper at ICLR 2023
1 =²²x -9"= 2 g X Gz) [(z,A)
1 1
(21)
2²²= x (g" +XGG)= + 7 -
1
Since L(z, A) a quadratic convex function, its minimal value can obtained by
vzl(2, = (g" +x=G) =0 = + G
(22)
So
1
g'g G x) + I X
Lig G G
(g+
1 GG 1
2
1 X
= -Gg - G
(23)
Therefore, the dual of SGC QP
minx (Gg- "
x=GGG
(24)
s.t. 0
The optimum A can be calculated by library quadprog and the optimal solution of SGC QP z' + G X
A.3 THEORETICAL ANALYSTS OF GRADIENT PROJECTION
Assumption In each local update, small optimization steps happen and thus we can assume that the function F is locally linear (i.e., convex function..
To enable the local model retains more knowledge received from server after local update, the loss of local model on global data D should reduce after local update, i.e.,
F(O D) < F(0'-1.2) D)
(25)
where of is the model parameters at client k after local update and 0--1 is the initial model (i.e., the global model at previous round) parameters.
Since the global data D cannot be achieved in FL, we use gradient projection to achieve this objec-
tive. For simplifying, D is omitted in the following equations.
From convexity we know that VF VF (0'-1)² (0) 0'-1) 2 0 implies F(O 2 F(0'-1), so the search direction in local training must satisfy
VF (0'-1)" (0) 1
(26)
Thus, must make an acute angle with negative gradient, i.e.,
gg gl + (g"=
,g6)
(27)
where - FV (0C-1) and gf 0% -
13

---

Under review as a conference paper at ICLR 2023
A.4 CONVERGENCE ANALYSIS
Here we give a simple proof that our FedGC has a faster convergence rate than FedAvg. We analyze the convergence of our FedGC by finding an upper bound & of [F(0*)] F*, i.e., E [F(O") F Σ 5. where F F(eT) represents the final global model with parameter 0 in FL and F is the optimal model for all clients' data (i.e., the upper bound of global model in FL).
From A.3 our FedGC can guarantee that the loss of local model on global data reduces after local update (i.e., F(OE) < F(0'-1), while FedAvg cannot. In other words, our FedGC can guarantee that the loss of global model gradually reduces (i.e., F(O*) F(0'-1)), while FedAvg cannot. In detail,
K Σ
F(0') = F
PRO
(28)
where the aggregation is averaged for simplifying, and Σ Phe =1
Let Assumption holds, we can obtain
K L PkF =
F(0")= F
Σ P
Σ P&F F (0%)
(29)
Thus, after T communication rounds (i.e., one fixed T), the difference between E [F(0")] and F* of our FedGC should be smaller than that of FedAvg. Thus, we can conclude that ş cGC Agg
A.5 PRIVACY-PRESERVING ANALYSIS
Recently, Deep Leakage from Gradients (DLG) Zhu et al. (019)) attack has attracted growing atten- tions, which can completely steal real data from gradients. However, under our FedGC, the real data cannot be reversely obtained. The details are shown below.
In DLG, pair of "dummy" input and label are first randomly generated perform the usual forward and backward operations. In order to obtain the real data reversely, the dummy gradients from the dummy data are firstly derived, then DLG optimizes the dummy inputs and labels by minimizing the Euclidean distance between the dummy gradients and the real gradients. However, matching the gradients cannot make the dummy data close to the real data when our FedGC performs.
Figure 4: DLG in our FedGC.
Normal Participant
Diffcrentiable Model
F(x,,t, A
Predict
Loss: L
[0, 1, 0]
àL
Real label VL,k
Real imput Xe,le
SGC
a
Real gradient 8k
CGC
Global gradient y f-1
Try match
Malicious Attacker
aL,
Dummy gradient
Ø
Dammy input x
Differentiable Model F
Dummy label Vi,
Predict'
Loss': L
[0.3, 0.6, 0.1]
ai
Zy'x
i
||
lill
In Figure at t-th communication round, an honest client & samples a minibatch (ar, Vr,k) from its own data and an evil client randomly initializes dummy input are with dummy label vl The
14

---

Under review as a conference paper at ICLR 2023
objective of the evil client is
Fo Ue. arg min
| gill"
(30)
x' M'e. t.k
where
oL F 2 0% .B/
g
(31)
00
aL (Ri,ks 0%) Ve,k)
g CGC
(32)
00
From 32. we can observe that in our FedGC, gi is not only determined by but also depen-
aet dent on the global gradient g²11 by our CGC, and the CGC projection cannot be reversely derived. Thus, we can obtain
(c/, #(,x) + (are,es Vt.k)
(33)
Therefore, we can conclude that real data cannot be recovered with gradient inversion attacks (e.g., DLG) in our FedGC and our FedGC can ensure preserving of privacy.
In addition, we conduct the gradient inversion attacks experiment compare FedAvg and our FedGC with DLG on CIFAR 10-10 dataset. The backbone is ResNet-9. We set the number itera- tions in DLG to 300. As shown in Figure 5 the quality of the images recovered from our FedGC is significantly worse than those recovered from FedAvg, exhibiting a better privacy protection capa- bility of our FedGC.
Figure 5: Images recovered from updated gradients of FedAvg and FedGC on CIFAR10-10.
Iter
10
Ieer 550
Nee 100
Iter -200
lter. -300
Ier -10
lter 15
Iter-1000
Her 200
ler 300
25
25
20
25
FedAvg
FedGC(our)
A.6 MORE DATASETS DETAILS
Handwritten-Dighh MNIST has a training sets 60,000 examples and a test set of 10,000 exam- ples. The images in MNIST are grayscale with image size 28x28. MNIST-M contains 59,001 training and 90,001 test RGB images with size 28 28. USPS contains 9,298 grayscale images with image size 16x There 73,257 RGB images in training set of SVHN and 26,032 RGB images in test set with image size 32x32.
CIFAR-10 and 1000 CIFAR- contains 60,000 32x32 color images of 10 classes, including 5,000 images in training set and 1,000 images in test set per class. CIFAR-100 consists of 60,000
"http:/yyaroslav.gamm getin.net/
hhup://ufldl.. stanford http:://ffdd.sssafoodd..oo.
15

---

Under review as a conference paper at ICLR 2023
32x32 color images of 100 classes. In CIFAR-I00 there 500 images in training set and 100 images in test set per class.
A.7 EXPERIMENT OF FEDAVG ON HWDIGITS-4 UNDER MINI-BATCI UPDATE
In this experiment, the number of mini-batches B for local training in FedAvg is in the range of {1, 10, 30, 50 and the number of communication rounds is 600 for all experiments.
Table 3: Experiment of FedAvg HWDigits-4 under mini-batch update.
Setting
B
10
B 20
B 50
E 1 (i.c. 73 ~ 732)
FedAvg 85.22
92.75
93.43
93.59
93.07
In Table 3, we can observe that FedAvg can achieve better performance when B 50 while require- ing less iterations in local training stage compared E = The experimental results are consistent with the statement in Section 3.]
A.8 LEARNING CURVES
The learning curves are drawn in Figure where the x-axis is scaled by communication-budee (i.e., in multiples of [@)). The figures show that our FedGC can reach the target accuracy (i.c., the highest accuracy of baseline FedAvg) with the smallest communication budget.
Figure 6: Learning curves of compared methods terms of communication budget.
HWDigits-4 4
CIFAR10-10
0.6
0.8
0.5
Test accuracy
Test accuracy
0.6
0.3
1225
0.4
Fediig RecPnox
FedPeg
fecCurv
0.2
SCH+FLU
0.2
19
4395577
327
437438880 480
0
200
400
600
800
1000
1200
1400
0
200
400
600
800
1000
1200
Communication budget (x(8))
Communication budget (x101)
CIFAR100-100
HWDigits-40
0.8
0.7
Test accuracy
Pookng
Test accuracy
0.3
0.4
1445
0.2
FectCinert
0.3
PodRog
FedPoox
0.1
287531
989
0.2
SCAFFOLD
357476598
500
1000
1500
2000
2500
0
200
400
600
800
1000
1200
1400
Communication budget (x10))
Communication budget (x(61)
A.9 ABLATION EXPERIMENTS
We conduct the ablation experiment to disentangle CGC & SGC on all four compared datasets.
The results in Table illustrate that the performances of our FedGC will degrade without CGC, in particular for the label skew datasets. That is because the issue of catastrophic forgetting seriously
16

---

Under review as a conference paper at ICLR 2023
Table 4: Ablation experiments.
Method
HWDigits
CIFARIO-10
CIFARI00-10
HWDigits-40
FedAvg
93.07
55.34
40.59
62.11
FedReg
92.32
57.70
53.02
63.05
FodGC (w/o CGC)
93.38
54.09
41.64
74,51
FedGC (w/o SGC)
94.15
59.64
55.73
74.63
FedGC
95.37
60.92
56.56
77.33
influences the performance of FL, and CGC can mitigate this forgetting issue. Therefore, in FedGC, CGC is very important to improve the performance FL. on Non-IID data.
A. AVERAGE LOSSES OF EACH CLIENT ON GLOBAL DATA BEFORE AND AFTER LOCAL. TRAINING IN FEDAVG
Here we give an example to showcase that the forgetting issue is important. For FedAvg on CIFARIO-10, we calculate ī and r. to show the average losses of each client on global data before and after local training respectively.
1
Σ
L(
(34)
K
where K is the number of clients, 0% is the initial model before local training, D is the global data.
1
L(O Dx)
(35)
K
where of the local model after local training and Da is the local data.
Figure 7: Average losses of each client on global data before (L'-1) and after (LE) local training in FedAvg, and each point indicates one communication round.
CIFAR10-10
20
Loss 4
15
5
0
10
15 Loss 15-1
20
25
The Figure shows that in FedAvg, the average losses L global data for all communication rounds are significantly larger than f after local training. This because the clients forget the knowledge learned from global model after local training in FedAvg.
17


Reviews:
[{"review_id": "ofBb4b1YBl", "reviewer": "Reviewer_ESza", "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": "This paper studies the problem of alleviating convergence issues in FL in the face of non-iid data. In particular, the authors propose methods which align the gradient and the direction of update with the past update at the server, and align the server update with the aggregated client model update. The alignment is done through a projection operation. Finally, empirical results on public datasets illustrate the efficacy of the approach.", "summary_of_the_review": "The paper considers a relevant problem of interest in FL to tackle non-iidness and proposes to tackle it with gradient alignment via projections. There are a lot of questions concerning the algorithm both in terms of feasibility and convergence, which is not covered in the paper. Finally, experimental results are weak in terms of fairness of comparing with other baselines.", "strength_and_weaknesses": "Strengths:\n+ The paper is well written and easy to follow. The problem being considered is relevant and of sufficient interest to the FL community in general.\n+ The method proposed utilizes inequality constrained optimization to enforce alignment between local and global update directions. The alignment is done at both the level of the client and server which alleviates non-iidness to a certain extent. Technically speaking, the approach is quite general and original in its form.\n+ The experimental results show that the proposed algorithm outperforms other well known baselines.\n\nWeakenesses:\n- The alignment at the client level requires the server sending the aggregated model update from the past round to each client, which undermines the privacy-preserving aspect of FL quite a bit. Moreover, the optimization problem to be solved at hand is a constrained optimization with additional computational overhead on the clients, with no guarantees of existence of a feasible space.  It's also not clear how C is chosen and how it affects convergence.\n- The discussion in Step 1 in page 4 is erroneous. Unlike what the authors discuss, mini-batch SGD evaluates gradients at the same model iterate for multiple batches and then averages them. It doesn't take update steps after each gradient evaluation as suggested by the authors. Overall, step 1 of the algorithm is no different than standard local mini-batch SGD, where the client takes multiple local steps.\n- The question of feasibility of the constrained optimization becomes even more acute in case of the server, as it combines $k$ different constraints. It's not clear to me especially as to what is done, if the intersection of such constraints leads to an empty set, i.e., there's no feasible solution. In sufficiently non-iid data, how does one go about such scenarios.\n- The algorithm is devoid of any theoretical guarantees in terms of convergence. It's not clear if the aligned update directions thus obtained lead to a direction of sufficient descent.\n- Finally the experimental results leave a lot wanting. Number of local epochs is chosen to be $5$ for the proposed algorithm, while it is taken to be $1$ arbitrarily for all other baselines for the Handwritten digits dataset. Similarly, while learning rate tuning is done for the proposed algorithm, all other baselines are assigned a fixed learning rate without any tuning. Hence, the experimental comparisons are not fair and no claims regarding the superiority of the proposed approach can be made.\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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QwFOSfgG1uY", "reviewer": "Reviewer_NKr4", "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 authors propose modifications to the FedAvg algorithm: CGC & SGC. The CGC gradient projection empirically improves convergence by aligning each client's update with the server-side update. SGC attempts to improve upon the weighted clients' average by projecting it to the individual clients' updates. The paper has some open remaining questions in the empirical section and some corrections required for 'PDG' imo. \n", "summary_of_the_review": "Interesting algorithm with some weakness in the discussion (c.f. PDG), details (communication, subsampling) and the experimental evaluation. \nShould the authors improve their discussion around PDG, and provide the missing information about communication budget and client subsampling, I will raise my score. Should the authors also provide additional experiments, I will raise my score again. \n\n\n---- post-rebuttal ----\nI have read the rebuttal and other reviewer's comments and as a consequence have reduced my score to 3", "strength_and_weaknesses": "The paper's strength lies in the contribution through CGC and SGC. These modified update schemes are well motivated and show good empirical results. \nThe paper's weakness lies in some of the algorithmic details & discussion:\nThe discussion around 'Step 1 (PDG)' seems ad-hoc and not well-founded. Traditionally, FedAvg doesn't consider Mini-batch SGD since generally speaking FL tries to capitalize on the multiple local update steps in order to save on communication and decrease overall algorithm run-time. As such, this point doesn't seem worthwhile to explicitly make. The definition of $\\bar{g}_k^t$ for the 'mean gradient' of Mini-batch SGD seems to suggest an average of gradients, each of which is computed on a different models through intermediate application of the individual gradient steps. My understanding of Mini-batch SGD is that a client's gradient is computed on the same model and the final update corresponds to the gradient of a very large mini-batch. The update that the authors propose for $\\tilde{g}_k^t$ seems to be the standard (adaptive) FedAvg update that a client sends to the server (here scaled by $\\eta$). See e.g. Algorithm 1 in 'Reddi, Sashank, et al. \"Adaptive federated optimization.\" arXiv preprint arXiv:2003.00295 (2020).'\n\nI would need some clarification on the details in Algorithm 2 `ClientLocalUpdate`:\nThe server-side code suggests that you explicitly consider client sub-sampling (which is great!). As a consequence, you need to explicitly send the previous server-side model $\\theta_k^{t-1}$ along with the gradient $g^{t-1}$ to reconstruct the current server-side model $\\theta_{k,0}^t=\\theta_{k}^t$. In principle, this prevents you from using server-side adaptive optimizers that rely on momenta (such as FedAdam in above Reddi et al. paper). Ideally, you communicate $\\theta_{k}^t$ directly to the client. Your algorithm explicitly states that you are communicating both, $g^{t-1}$ and  $\\theta_k^{t-1}$  to the client, however you mention \"Moreover, our FedGC only transmits the gradients between the server and clients.\" (also in the discussion: \" Moreover, FedGC enables low communication cost due to fast convergence rate and only transmissions of gradients between server and clients\"). Furthermore, you critique SCAFFOLD for doubling communication cost from server to client). In Section 4.4 you deduce that \"the average gradient in the previous communication round is less useful in current round\". This is curious to me, since your method also communicates the previous (projected) gradient - and uses it in a different way than Scaffold. Can you make a more precise statement here on why you believe your method is less susceptible to the use of previous-round gradient? \nFurther in section 4.4 you are critiquing \"SCAFFOLD also requires more time to calculate and transmit the control variate between clients and server.\" Again, your method requires computing and sending the projected gradient to clients, in addition to model parameters. \nBased on your somewhat contradicting discussion and lack of explicit statement about the communication-costs of FedGC, I have low confidence in your experimental evaluation as regards the communication costs (Table 2 & Section 4.5). I believe your method communicates $2.0 |\\theta\\$ from server to client (same as scaffold). Can you confirm that? And did you account for that in Table 2 correctly? I would like to see a learning curve similar to Figure 3, where the x-axis is scaled by communication-budget (i.e in multiples of $|\\theta\\$) instead of communication rounds to substantiate your claims. \n\nWhy did you choose to apply gradient projection layer-wise and not align the whole concatenated gradient? I am not sure I understand the argument that different layers have different dimension? How would that influence the flatten, then concatenate alternative?\n\nExperiments:\nrelated to above discussion: Are you using client-subsampling? How many clients are selected per-round? \nWhy are you using $E=50$ for FedGC and not the base-line? Please show an ablation study for these different settings. If using $E=50$ is required for FedGC, the computational cost is increased many times and claiming FedGC is well-suited because of low computation costs (as in the discussion) is misleading. \n\nAnother ablation I think would be very insightful to disentangle CGC & SGC further is to run without CGC and only have server-side projection. Such a method would come 'for free' in the sense that there is no communication overhead server->client. \n\n\nNit-picking: \nYour last sentence in the main-body states \"In a nutshell, FedGC has great potential for many real-world applications that concerns performance, real-time, communication & computational costs, and privacy preservation.\" I would like to see claims about 'real-time' made more concrete and substantiated, as well as how FedGC is privacy-preserving, since e.g. is it amenable to classical Differential privacy techniques (I believe it should be) and arguably reveals to clients the average update of previous-round clients, which is more privacy-revealing than standard FedAvg. ", "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": "8aFnTTbSq9w", "reviewer": "Reviewer_yV7y", "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": " This paper proposes a set of new methods to deal with the \"catastrophic forgetting\" issue for federated learning over heterogeneous data.  The main idea of this method is to project the newly sampled gradients into the set with acute angle with previous gradients which is kind of like efficient regularization that has an efficient QP solution. The boost in performance is significant in that both the reported test accuracy and communication cost required to reach certain accuracy demonstrate superiority in contrast to existing methods. ", "summary_of_the_review": "This paper crafts a set of methods that demonstrates great improvement in experiments to deal with the \"catastrophic forgetting\" issue in federated learning over heterogeneous datasets. Given that other methods are also well tuned, the test accuracy of the proposed methods have some edges towards existing methods and the reported communication cost and training time savings are significant. ", "strength_and_weaknesses": "Strength: \n1. The proposed methods are intuitive, easy to understand and implement with the aid of QP solver. \n2. The proposed methods are very effective in experiments. \n\nWeakness: \n1. There are no explanations on the development of these methods, maybe some examples in image classification tasks can be given, or give some explanations to persuade people that these methods may also work in NLP tasks that are not experimented in this paper. \n2. There is no theoretical support for the proposed methods. \n3. The QP constrained optimization orientated gradient projection idea is not new in the literature (such as https://arxiv.org/pdf/2101.11296.pdf), some more comparisons may be needed in terms of novelty of the proposed methods.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": {}}]

Author rebuttal:

Decision: Reject