Communication-Efficient Federated Learning with Accelerated Client Gradient
Authors: Geeho Kim
Jinkyu Kim
Bohyung Han
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated learning
Data heterogeneity
Deep Neural Networks
Distributed Optimization

Abstract: Federated learning often suffers from slow and unstable convergence due to heterogeneous characteristics of participating client datasets.
Such a tendency is aggravated when the client participation ratio is low since the information collected from the clients is prone to have large variations.
To tackle this challenge, we propose a novel federated learning framework, which improves the consistency across clients and facilitates the convergence of the server model.
This is achieved by making the server broadcast a global model with a gradient acceleration.
By adopting the strategy, the proposed algorithm conveys the projective global update information to participants effectively with no extra communication cost and relieves the clients from storing the previous models.
We also regularize local updates by aligning each of the clients with the overshot global model to reduce bias and improve the stability of our algorithm.
We perform comprehensive empirical studies on real data under various settings and demonstrate remarkable performance gains of the proposed method in terms of accuracy and communication efficiency compared to the state-of-the-art methods, especially with low client participation rates.
We will release our code to facilitate and disseminate our work.

Under review as a conference paper at ICLR 2023
COMMUNICATION-EFFRIINNNN FEDERATED D LEARNING WITH ACCELERATED CLIENT GRADIENT
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning often suffers from slow and unstable convergence due het- erogeneous characteristics of participating client datasets, Such tendency is ag- gravated when the client participation ratio is low since the information collected from the clients is prone to have large variations. To tackle this challenge, we propose a novel federated learning framework, which improves the consistency across clients and facilitates the convergence of the server model. This is achieved by making the server broadcast global model with a gradient acceleration. By adopting the strategy, the proposed algorithm conveys the projective global up- date information to participants effectively with no extra communication cost, and relieves the clients from storing the previous models. We also regularize local updates by aligning each of the client with the overshot global model to reduce bias and improve the stability of our algorithm. We perform comprehensive pirical studies on real data under various settings and demonstrate remarkable performance gains of the proposed method in terms of accuracy and communi- cation efficiency compared to the state-of-the-art methods, especially with low client participation rates. We will release our code facilitate and disseminate our work.
INTRODUCTION
Federated learning (McMahan al., 2017) is large-scale machine learning framework that learns shared model in a central server through collaboration with large number of remote clients with separate datasets. This decentralized learning concept allows federated learning to achieve the basic level of data privacy since the server does not observe training data directly. On the other hand, remote clients such as mobile or IoT devices have limited communication bandwidths, and federated learning algorithms particularly sensitive to communication costs.
baseline algorithm of federated learning, FedAvg (McMahan et al. 2017) updates a subset of its client models based gradient descent method using their local data and then uploads the resulting models to the server for computing the global model parameters via model averaging. As discussed extensively the convergence of FedAvg (Stich) 2019; Yu al.) 2019 Wang & Joshi, 2021 Stich & Karimireddy [2019] Basu et al. 22020), multiple local updates conducted before server- side aggregation provide theoretical support and practical benefit of federated learning by reducing communication cost greatly.
Despite the initial success, federated learning faces two key challenges: high heterogeneity in train- ing data distributed over clients and limited participation rates of clients. Several studies (Zhao al. 2018: Karimireddy et al.) 2020) have shown that multiple local updates in the clients with non-i.i.d (independent and identically distributed) data lead to client model drift, in other words, diverging updates the individual clients. Such a phenomenon introduces the high variance issue in the FedAvg step for global model updates, which hampers the convergence to the optimal average loss over all clients (Li et al. 2020; Wang et al., [201b]] Khaled et al., 2019 Li et al. 2019b Hsich et al. 2020 Wang et al.) 2020). The challenge related to client model drift exacerbated when the client participation rate per communication round is low, due to unstable client device operations and limited communication channels.
To properly address the client heterogeneity issue, we propose a novel optimization algorithm for federated learning Federated averaging with Accelerated Client Gradient (FedACG), which conveys

---

Under review as a conference paper at ICLR 2023
the momentum of the global gradient to clients and enables the momentum to be incorporated into the local updates in the individual clients. Specifically, we introduce an extra-gradien step on the global model via the global momentum, which allows each client performs its local gradient step along the future gradient. This approach turns out to be effective for reducing the gap between global and local losses. Contrary the existing methods that require to send additional bits to communicate the momentum, FedACG transmits the global model integrated with the momentum in the form of a single message and saves the cost for communication. In addition, FedACG adds a regularization term in the objective function of clients to make the local gradients more consistent across clients.
Although there have been a growing number of works that handle the client heterogeneity in fed- erated learning, FedACG has the following major advantages. Unlike existing approaches focusing on server-level optimization (Reddi et al. 2021 Wang et at. 2019a HHsu et al. (0119] or client-level
optimization (Xu et al., | Acar et al. 2021; Karimireddy et al. 22200] Li et al. 2021 2020 Zhang et al.) 2020] Karimireddy et al. 2021 Li et al. [2019a] Liang et al. 2019), FedACG incorpo- rates the momentum based the global gradient information for client-side updates. This strategy allows the proposed algorithm to achieve the same level of task-specific performance with fewer communication rounds. Moreover, while most of existing methods have additional requirements compared to FedAvg including full participation (Liang et al. [019 Zhang et al.] 2020 Khanduri
al.
202T), additional communication bandwidth (Xu et al., 2021
Karimireddy et al.
2020 Zhu
et al. 2021 Karimireddy et al. [202T] Li et al.) 2019a|[aas et al. 2020
Gao et al. [2022) and mem-
ory budgets in clients store local states or variables (Acar et al. 2021 Karimireddy et al.. 2020 Li
ict al. 2021; Gao et al. 2022), FedACG is completely free from any additional communication and
memory overhead, which ensures the compatibility with large-scale and oowpaaticcipation federated
learning problems. The main contributions of this paper are summarized as follows.
We propose a communication-efficiee federated optimization algorithm that deals with client heterogeneity effectively. The proposed approach employs the global momentum for the acceleration of client gradients to facilitate the optimization of local models.
We also revise the objective function of clients, which augments a regularization term to the local gradient direction, which further aligns the gradients of server and individual clients.
We show that the proposed approach does not require any additional communication cost and memory overhead, which is desirable for the real-world settings of federated learning.
We demonstrate outstanding performance of our optimization technique in terms of com- munication efficiency and robustness to client heterogeneity, especially when the participa- tion ratio is low.
RELATED WORK
Federated learning was first introduced in McMahan et al. (2017), which formulates the problem and provides the FedAvg algorithm as solution for its key challenges such non-iid client data, massively distributed clients, and partial participation of clients. Many works explore the negative influence of heterogeneity in federated learning empirically (Zhao et al., 2018) and derive conver- gence rates depending on the level of heterogeneity (Li et 2020 Wang et al., 2019h) Khaled
al. 2019 Li al. 2019b Hsich et al., 2020 Wang al. (220)).
There exists a long line of research for client-side optimization to prevent the divergence of clients
from the global model. FedProx (Li al. (020)) penalizes the difference between the server and client parameters, while FedDyn (Acar et al., (02T) and FedPD (Zhang et al.) 2020) use cumu- lative gradients of each client to dynamically regularize local update. FedDC (Gao al. 2022) introduces the auxiliary drift variables for each client to reduce the impact of the local drift on the global objective. There is another line of works which adopt variance reduction techniques in client update to eliminate inconsistent update across clients. SCAFFOLD (Karimireddy et al., 2020) and Mime (Karimireddy et al. 2021 employ control variates for local updates while FedDANE (Li et al. 2019a) and FedCM (Xu et al. (021) add gradient correction term based on the server gra- dient. FedPA (Al-Shedivat et al., (022)) de-bias client updates by estimating the global posterior on the client side. On the other hand, some approaches adopt a contrastive loss (Li et al. 2021), knowledge distillation (Kim et al., 2022), or a generative model (Zhu et al.] (021) to ensure the similarity of the representations between the global model and local networks. FedSAM (Qu al.)
2

---

Under review as a conference paper at ICLR 2023
Algorithm FedACG
Input: 3. X, initial server model 80, number clients N, number of communication rounds T,
local learning rate 7)
Initialize the global momentum, m = O. for each round 1 ......., do
Sample subset of clients St S ( (1,...,,N;
Server sends gt Am'-1 to initialize local models for all clients E St.
for each client E S,, in parallel do
Set f = argmin (0) + 211 (0'-1 + 211=
" Client sends of back to the server.
end In server:
0' = Lies, wi0!
m' = 0¹ 8i-1
end
Return 0
and ASAM Caldarola et al. 2022) apply SAM (Foret et al. 2021) as a client-side optimizer for reducing the gap between global and local losses. However, most of these methods require full
2022
participation (Zhang et al.
2020:
Khanduri et al. 2021 additional communication cost (Xu et al.,
2021
Karimireddy
al. 2020 Zhu et al. 202 Karimireddy al. 202T; Li al. 2019a Das
et al.
2020
Gao et al. 2022), or extra client storage (Acar et al., [202] Karimireddy et 2020
al.
2021
Gao al.
2022). which can be problematic in realistic federated learning tasks.
Server-side optimization techniques also have been explored for the stability and speedup of conver- gence. These approaches adopt momentum SGD (Hsu al. 2019), or an adaptive gradient-deseee descent method (Reddi et al. [2021] Caldarola et al. (2022). while FedDF (Lin et al. (2020) utilizes the aver-
aged representations of local models on proxy data for aggregation. STEM (Khanduri et al. 2021)
and FedGLOMO (Das et al. 2020) apply STORM algorithm (Cutkosky & Orabona 2019) both
server-level and client-level SGD procedures for reducing high variance in server model update.
Meanwhile, another set of works aims to decrease the communication cost per round by compress- ing the model transmitted. FedPAQ (Reisizadeh et al. 2020). FedCAMS (Wang et al. 2022) and FedCOMGATE (Haddadpour et al. (021) quantize the communicated message by using low bit precision, while FedPara (Nam et al. 20022) use low-rank Hadamard product to reparameterize the model's 's weights. These works are orthogonal to approach, they can be readily combined with our proposed method.
METHOD
In the federated learning setting, there N clients that optimize their local models based the corresponding private datasets as well as a central server that broadcasts the global model and then aggregates messages from the clients. Let (0) () [fr( 0)] be the loss function of the ,th (1...., N) client with local dataset denoted by D.. Then, our goal to train model that minimizes the average loss of all clients as follows:
N
min ((0) = 2ir w.C
1=1
where the parameter of the global model and Wi is the normalized weight of the 7th client proportional to the size of the local dataset. We focus the non-i.i.d data setting, where local datasets have heterogeneous distributions. Note that the communication of training data between clients and the central server is strictly prohibited in principle due to privacy.
3.1 FEDACG
To reduce the inconsistency between the local models and the consequent divergence of the global one, incorporate the global momentum into local models for guiding local updates.
3

---

Under review as a conference paper at ICLR 2023
0'
Am t-1
Accelerated point at
Global momentum
H
Averaged local updates
Server update
Figure I:
An illustration of the proposed accelerated client gradient method. We first partially update the global model in the direction of the global momentum (orange) and then aggregate local updates (gray), resulting in the server model in the next round (bluc). Through this anticipatory update, we make the individual local updates aligned with the global gradient and achieve speed-up of convergence.
Overall framework Each round of FedAGC starts from the server. In the (th communication round, the server computes its momentum m := g'-1 fr-2, and broadcasts the accelerated global model gt + Am' single message to the active client set S, S {1...., .N. where (0, 1] controls the importance of the global momentum. Each participating client optimizes its local model from the noomentum-ineerratee the sum of its empirical loss on the local data and penalty from the difference between the local online model and the accelerated global model, which is given by
initialization. The objective of each client is minimize
{ ==(0))===,1
8 2100 (0--1 Am \m3
min 8
where 3 controls the balance between the two terms. Each client uploads their trained model 0f to the server, and then the server constructs the next server model He via simple aggregation, i.e., g Lies, W Algorithm I presents the procedure of FedACG.
Accelerated client gradient The main idea of this work, accelerated client gradient, to lever- age the global momentum and allow clients to look ahead the landscape of the global loss. The momentum m' serves as an approximate gradient of the global loss since it maintains past global updates even in partial participating setting. Let the local update of each participating client be A 0g (0t-1 Am Am(-1), 11). Then, m' is defined recursively with an exponential decay factor as
m² = 0² g = [A' + (0'-1 + Am'- - g² = A + Am
where A = = Eies, W denotes the expected local updates of all participating clients in the current round
As illustrated in Figure 1 FedACG makes an anticipatory update by integrating Amt to the pre- vious global model - This strategy allows the updates of each client be aligned with the trajectory of the global gradients, which improves consistency of local updates in FedACG. Our approach has a similar motivation with meta-learning (Finn et al. 2017). where meta-learner iden- tifies the optimal point facilitate the optimization of all target tasks.
Regularization with momentum-integratee model In addition to the initial acceleration for local training, the second term of our local objective function in Eq. (2) takes the advantage of the global gradient information to reduce the variations of client-specific gradients, A, This regularization term enforces the local model not to deviate from the accelerated point, preventing each client from falling into biased local minima.
3.2 DISCUSSION
While our formulation has something in common with the existing works that also address client het- erogeneity by employing global gradient information for the local update, FedACG has the following major advantages. First, contrary to Karimireddy et al. (2020); Xu et al. (202T): Gao et al. (2022). the server and clients only communicate model parameters without imposing additional network
4

---

Under review as a conference paper at ICLR 2023
overhead for transmitting gradients and other information; the server broadcasts (6 + Am as a single message and each client sends 8 to the server. This is a critical benefit because the increase in communication cost challenges many realistic federated learning applications involving clients with limited network bandwidths. Second, FedACG is robust to the low participation rate of clients and allows new-arriving clients to join the training process immediately without warmup phase because, unlike Karimireddy et al. (2020), |Acar et al. (2021). Li et al. (2021), and |ao et al. (2022) the clients are supposed neither store their local states nor use them for model updates.
3.3 CONVERGENCE ANALYSIS OF FEDACG
We present the theoretical convergence rate of FedACG. We first state two assumptions for the local loss functions (0), which are commonly used in several previous works on federated optimization KKariirredy et 2020, Reddi al. 2021 Xu al. 2021 Acar al. 2021). First, the local function (2))) is assumed to be L-smooth for all 2 E (1,...,, L.i.
(z) v4(1il s -||-- yll Vz, Second, we additionally assume the convexity of the functions {4(-))= we have
(4)
VE,
V(((2) ve(xx)) < ((z) f(x.) and
(5)
2LN
Vx, 2, (VL()), v) -2(=) + (v) + 2 || - x 111??
(6)
where ((x) = N Σ (xx) and Vi(x.) = Based on the above assumptions, we derive the
following asymptotic convergence bound of FedACG. Note that make no further assumptions such as a form of bounded variance and gradients used in Karimireddy et al. (202)) Reddi et al. (202I. and Xu et al. (202I).
Theorem 1. Assuming the convexity and L-smoothness of (4(0))) < X < 1, Algorithm satisfies
E
l T
Σ
001) (0.))
(1.110-- 0a112 -0-10-00111
1
N
V4, (0.) 11
T
LN
where 0, = argmin E(0) and 0º 130
EiEs, of.
Theorem implies that, for convex and smooth local functions, the global objective function is expected to converge at rate of O VA(L-A] This rate is the empirical loss averaged over all devices. It further implies a higher value À improves the convergence rate under the convex setting, which will be empirically verified in our experiments. Please, refer to the supplementary document for the full proof.
4 EXPERIMENTS
This section presents empirical evaluations of FedACG and competing federated learning methods, to highlight the robustness data heterogeneity of the proposed method in terms of performance and communication-eliiiinnng.
4.1 EXPERIMENTAL SETUP
Datasets and baselines We conduct a set experiments on CIFAR-10 Krizhevsky et al. 2009). CIFAR-10W (Krizhevsky et al., 2009), and Imag- Le & Yang 2015) with various data heterogeneity levels and participation rates. Note that Tiny- ImageNet (200 classes with 10, 000 samples) is more natural and realistic compared to the simple datasets, such as MNIST and CIFAR.
https: www. wwwpwwwwwwwwwww...p..pp.pwpwwwww
kaggle. e. com/ htt/://iiin// http:///iiingggeettttttetee imagenet
5

---

Under review as a conference paper at ICLR 2023
Table I: Comparisons of FedACG with baselines on CIFAR-IO, CIFAR-100 and Tiny-ImageNet for two different federated learning settings. For moderate-scale experiment (a), the number of clients and participation rate, are set 100, and 5%, respectively, while large-scale experiment (b) has 500 clients with 2% participation rate. The Dirichlet parameter is commonly set to 0.3. Accuracy at target round and the communication round to reach target test accuracy based on running exponential moving average with parameter 0.9. The arrows indicate whether higher (1) or lower (L) is better. The best performance in each column is denoted in bold. FedCM and FedDC require 1.5x and 2 communication cost for each communication round, respectively.
Moderate-scale: 5% participation, 100 clients
CIFAR-10
CIFAR- R-10
Tiny- -mageNet
Method
Acc. (%,, f) Rounds (1) Acc. (%. 1) Rounds (U) Acc.
(%. f)
Rounds (U)
500R
1000R 81% 85% 500R 1000R 47% 55% 500R
1000R 35%
38%
FedAvg (McMahan al.
2017
74.36 82.53 840 1000+ 41.88 47.83
924 1000+ 33.94
35.37
1000+
FedProx el al. 22020
2020
73.70
82.68
826
1000+ 42.43
48.32
1000+
34.14
35.53
1000+
FedAvgM Hssu ci al. 2019
80.56
85.48
519
828
46.98
53.29
515
1000+
36.32
38.51
416
829
FedADAM [Reddi 2022
72.33
81.73
908
1000+
44.80
52.48
691
1000+
33.22
38,91
658
945
FedDyn (Acar et al. 2021
84.82
88.10
392
646
48.38
55.79
424
37.35
41.18
MOON (Li al. 202T
83.32
86.30
686
53.15
58.37
284
640
36.62
40.33
627
FedCMt (Xu et al. 2021
78.92
83.71
624
1000+
52.44
58.06
293
747
31.61
37.87
694
1000+
FedDC! Gao et al. 2022
86.52
87.47
323
519
54.25
59.01
333
553
40.32
45.51
340
403
FedACG (ours)
85.13
89.10
319
450
55.79
62.51
260
409
42.26
46.31
226
331
(b) Large-scale: 2% participation, 500 clients
CIFAR-10
CIFAR-100
Tiny-ImageNo
Method
Acc. (%. f) Rounds (1) Acc. (%. [)
Rounds (L)
Acc. (%. f) Rounds (L)
500R 1000R
73%
77%
500R
1000R
36%
40%
500R 1000R
24% 30%
FedAvg
McMahan et al.
2017
58.74 71.45
1000+
1000+
30.16
38.11
842
1000+
23.63
29.48
523
1000+
FedProx [J eJ al. 2020
57.88 70.75
1000+
1000+
29.28
36.16
966
1000+
25.45
31.71
445
799
FedAvgM HHsu et al. 2019
65.85
77.49
753
959
31.80
40.54
724
955
26.75
33.26
386
687
FedADAM
[Redd al 2021
61.53
69.94
1000+
1000+
24.40
30.83
1000+
1000+
21.88
28.08
648
1000+
FedDyn
(Aarr et al. 202
65.49
77.92
732
936
31.58
41.01
691
927
24.35
29.54
483
1000+
MOON
[ at.
69.15
78.06
617
872
33.51
42.41
601
828
26.69
31.81
382
741
FedCM
Xu al.
2012
69.27
76.57
742
1000+
27.23
38.79
872
1000+
19.41
24.09
975
1000+
FedDCF
Gao et al.
2022
71.86
83.49
518
686
34.64
45.93
569
741
25.72
28.92
420
1000+
FedACG (nurs)
73.61
82.80
484
605
35.68
48.40
505
616
31.47
38.48
246
447
used for evaluation of many previous methods (McMahan et al. 2017 Karimireddy al. 2020). We
generate IID data split by randomly assigning training data to individual clients without replacement. For the non-Ill) data, we simulate the data heterogeneity by sampling the label ratios from Dirichlet distribution with.a symmetric parameter (0.3, J.6], following Hsu et al. 2019). We keep the training data balanced, so each client holds the same amount of data.
We compare our method, FedACG, with several state-of-the-art federated learning techniques, which include FedAvg (McMahan et 2017), FedProx (Li et al. 2020), FedAvgM (Hsu et al. 2019), FedADAM (Reddi et al. (021). FedDyn (Acar et al.) 2021). FedCM (Xu et al. 2021] MOON (Li et al. 2021). FedDC (Gao et al. (022). We adopt a standard ResNet-18 (He et al., 2016) as backbone network for all benchmarks, but we replace batch normalization by group nor- malization as suggested in Hsieh al. (2020).
Evaluation metries To evaluate the generalization performance of the methods on the global dis- tribution, we use the entire test set in the CIFAR-10, CIFAR-100, and Tmay-ImageNet. Since both the speed of learning as well as the final performance are important quantities for federated learning, we measure: (i) the performance attained at a specified number of rounds, and (ii) the number of rounds needed for an algorithm to attain the desired level of target accuracy, following Al-Shedivat et al. (02T). For the selection of target accuracies, we first choose the median of all methods at round 1000 and another representative value lower than the median. For methods that could not achieve aimed accuracy within the maximum communication round, we append the communication round with a + sign.

---

Under review as a conference paper at ICLR 2023
Table 2: Effect of low participation rate, 1% over 500 clients with Dirichlet (0.3) split, for FedACG and the baselines on CIFAR-10 and CIFAR-100. Accuracy at the target round and the communi- cation round to reach target test accuracy are based on running exponential moving average with parameter 0.9. The arrows indicate whether higher (f) or lower (J) is better. FedCM and FedDC! require 1.5x and 2x communication cost for each communication round, respectively.
CIFAR-10
CIFAR- 100
Method
accuracy (1c, T
rounds (ff, U)
accuracy (%,, 1)
rounds (H, U)
500R
1000R
64%
68%
500R
1000R
30%
35%
FedAvg [McMahan et al. 2017
54.71
68.96
792
949
26.94
35.69
636
950
FedProx (T 2020
55.18
69.80
773
919
26.92
35.41
648
963
FedAvgM
FFsu et al. 2019
57.82
71.12
669
812
29.29
39.36
530
755
FedADAM (RedA
2021
47.97
55.11
1000+
1000+
17.72
23.92
1000+
1000+
FedDyn (Acar et al. 2021
54.86
70.78
713
858
27.86
36.31
595
896
MOON [Li
2021
64.55
73.89
491
645
28.29
36.37
567
886
FedCM (Xu et al.
2021
49.21
60.38
1000+
1000+
16.32
22,59
1000+
1000+
FedDC! (Gao al.
2022
60.56
75.06
610
681
29.14
38.84
519
789
FedACG (ours)
63.70
76.45
497
618
31.74
45.18
458
581
Implementation details We use PyTorch Paszke et al. 2019) to implement FedACG and the other baselines. We follow Acar al. (2021); Xu et al. (2021) for evaluation protocol. For local update, we use the SGD optimizer with a learning rate 0.1 for all approaches on the three bench- marks. We apply exponential decay the local learning rate, and the decay parameter is selected from {1.0, 0.998, 0.995). We apply no momentum for local SGD, but apply weight decay of 0.001 prevent overfitting. We also use gradient clipping to increase the stability of the algorithms. The number of local training epochs over each client update is set to 5, and the batch size is set so that the total iteration for local updates is set to 50 for all experiments. We set the global learning rate for all methods except for FedADAM which is set to 0.01. We list the details of the hyperparameters specific to FedACG and the compared algorithms in Appendix
4.2 MAIN RESULTS
Evaluation with standard federated learning scenarios We first present the performance of the proposed approach, FedACG, on CIFAR-10, CIFAR-I00, and Tiny-Ima in the scenarios by varying the number of clients, data heterogeneity, and participation rate. Our experiment has been performed on two different settings; one is with moderate-scaa scale, which involves 100 devices with 5% participation rate per round, and the other is with a large number of clients, 500 with 2% participation rate. Note that the number of clients the large-scale setting 5 times more than the moderate-scale experiment, which reduces the number of examples per client by 80%.
Table Ta demonstrates that FedACG improves accuracy and convergence speed significantly and consistently compared with other federated learning methods in most cases. This is partly because FedACG enables each client to look ahead the global update and aligns the local model updates with the global gradient trajectory. Note that FedCM and FedDC require 1.5x and 2x communication costs for each communication round respectively since they communicate the current model and the associated gradient information per round, while others only require model parameters.
For the large-scale setting, Table illustrates the outstanding performance of FedACG on CIFAR- 10, CIFAR-100, and Tiny-ImageNet, except for the accuracy 1K rounds CIFAR-10. One noticeable thing is that the overall performance is lower than the case with a moderate number of clients. This is because the number of training data for each client decreases and each client suffers more from the heterogeneous data distribution. Nevertheless, we observe that FedACG outperforms other methods consistently in most cases; the accuracy gap between FedACG and its strongest com- petitor becomes larger in these more challenging scenarios. The results from the large-scale exper- iments informs the robustness FedACG to the heterogeneity and limited participation of clients. We present more comprehensive results for the convergence of FedACG in Appendix D.I
Effect of low participation rate Partial participation is critical challenge to slow down the vergence of the global model in federated learning. To verify the robustness to the low participation rate of clients, perform experiments when the total number of clients is 500 and the participation
7

---

Under review as a conference paper at ICLR 2023
Table Results on CIFAR-100 when client set changes dynamically: we sample 250 clients out of 500 clients as candidate clients set at every 100 rounds over 10 stages on Dirichlet (0.3) split. 10 clients out of the sampled client set participate for the local training for each communication round. FedDCT requires 2x communication cost for each communication round.
CIFAR- 100
Method
Acc.
(%, f)
Rounds (T)
500R
1000R
30%
38%
FedAvg
McMahan et al. 2017
28.61
35.87
577
1000+
FedDyn
Acar et al. 2021
29.45
38.47
517
941
MOON
Li 202T
30.88
39.57
430
852
FedDC Gao
2022
31.35
36.82
469
1000+
FedACG (ours)
32.70
41.51
376
769
Table 4: Contribution of individual components in FedACG 1000 rounds CIFAR-10 and
CIFAR-100 with 2% participation and 500 clients.
Accelerated gradient (X) Regularization term (9)
CIFAR-10
CIFAR-I00
71.45
38.11
70.75
36.16
82.20
46.80
82.80
48.40
rate is as low as 1%. The numbers of local epochs and iterations are set to 5 and 50, respectively. This setting makes each client have very few training examples and increases client heterogeneity significantly. Table 2 again shows that FedACG has the best performance for most cases. Note that the performance gap between FedACG and the recond-best method, FedDC, becomes larger than when the participation rate is 2%: from -0.69%p to 1.39%p on CIFAR-10 and from 2.47%p to 6. on CIFAR- 100 at round 1000. This is partly because the local states managed by FedDC susceptible to get stale quickly in this scenario, making its convergence require extra iterations. In contrast, our method does not rely on the past information stored in local devices and is not affected by this issue.
Evaluation on dynamic client set Since FedACG free from the requirements of storing local model history for local updates, it is conceptually better-suited for the scenarios in the presence of newly participating clients. In order to validate the property, we conduct an experiment on CIFAR- 100 with 500 clients for Dirichlet(0.33) splits. We sample 250 clients at every 100 rounds as candi- date client set, and then 10 randomly sampled clients (4% of clients) participate in the local training for each communication round. Table P shows that FedACG outperforms FedAvg and FedDyn. Note that FedDyn is worse than FedAvg since the client model has trouble with its heterogeneity and divergence because new clients have or non-informative local states.
4.3 ABLATION STUDY
Contribution of individual components Table 4 presents the contribution of individual compo- nents in the experiment on CIFAR-IO for the large-scale federated learning setting. We observe that the accelerated client gradient for local training has more critical impact on accuracy with 1000 rounds. Note that the proposed regularization term in local loss function shows larger performance gain when used with the accelerated client gradient. while employing the regularization term only do necessarily achieve performance gains in CIFAR- 10 and CIFAR-100.
Ablation study for hyperparameters Table 5 presents the accuracy of FedACG for Dirichlet(O.3) and IID splits by varying the value of and B. which control the momentum integration of the server model and the weight of the proximal term, respectively. As shown in the table[5a| the low values of do not work well, supporting the benefit of the proposed accelerated client gradient strategy, while Table 5b shows that the accuracy is stable with respect B.
8

---

Under review as a conference paper at ICLR 2023
Table Ablation study of FedACG the weights of the two hyperparameters, (a) and (b), with respect to the accuracy at 1000 rounds on CIFAR-10 in 2% participation and 500 clients.
(a) Sensitivity of FedACG to À
(b) Sensitivity FedACG to /
A
0.25
0.5
0.75
0.85
0.95
0.001
0.01
0.1
DIr0.3)
70.75
73.93
79.14
81.32
82.80
78.25
Dir(O.3)
82.10
82,80
82.32
82.44
IID
72.20
74.29
80.52
85.52
86.83
84.37
IID
86.54
86.83
86.72
85.92
Table Results the realistic federated learning datasets which contain feature skewness and data imbalance between the clients. FedCM and FedDC* require 1.5x and 2x communication cost for each communication round, respectively.
FEMNIST
CelebA
Method
Acc. (%. 1)
Rounds (J)
Acc. (%. t)
Rounds ())
500R
78%
500R
88%
FedAvg (McMahan ct al.
2017
78.38
328
89.92
134
FedProx [L1
20200
78.34
328
89.90
132
FedAvgM (Hsu et al. 2019
78.37
256
89.85
113
FedADAM (Redd (Redi ct
2012
75.96
500+
87.00
500+
FedDyn (Acar ct |022
79.80
227
89.74
126
MOON
LL al. 2021
78.33
336
87.95
500+
FedCM Xu ct al.
2021
72.79
500+
88.89
222
FedDC Gao al.
2022
80.11
149
88.97
126
FedACG (ours)
80.61
169
90.09
108
4.4 EXPERIMENTS ON REALISTIC DATASETS
We conducted experiments additional realistic datasets, FEMNIST and CelebA in LEAF (Caldas al.
2019), which includes other non-iid scenarios such as feature skewness and data imbalance be- tween clients. For the experiment, the number of clients is set to 2000 with data split following Cal- das et al. (2019), and 10 randomly sampled clients participate the training for each communication round. We use simple CNN with group normalization with the number of layers two for FEMNIST and four for CelebA, respectively. Table presents presentss that FedACG also outperforms other baselines on both datasets for most cases, which supports our claim about the strength of FedACG on dataset heterogeneity. Table presents that FedACG also outperforms other baselines on both datasets for most cases, which supports our claim about the strength of FedACG on dataset heterogeneity. Note that, while FedACG requires 20 more communication rounds than FedDC to reach target accuracy on FEMNIST, sends 1.76x less parameters than FedDC.
CONCLUSION
This paper tackles realistic federated learning scenario, where large number clients with het- erogencous data and limited participation constraints hurt the convergence and performance of the model. To address this problem, we proposed novel federated learning framework, which nat- urally aggregates previous global gradient information and incorporates it to guide client updates. The proposed algorithm transmits the global gradient information to clients without additional com- munication cost by simply adding the global information the current model when broadcasting it to clients. We showed that the proposed method is desirable with the realistic federated learning scenarios since does not require any constraints such as communication or memory overhead. We demonstrate the effectiveness of the proposed method in terms of robustness and communication- efficiency in the presence of client heterogeneity through extensive evaluation on multiple bench- marks.
Ethics statement We propose a coamuunication-ffffieee federated learning framework which handles non-i.id data distribution over remote clients. Without access to the raw data stored in mote devices, the proposed method gets the basic level privacy. Also, unlike centralized training which suffers from dataset bias and unfairness problems since collected data reflects the perspec-

---

Under review as a conference paper at ICLR 2023
tive of the person who collects the data, it opens the way to learn real data distribution instead of collected data distribution.
Reproducibility statement We present the procedure of our proposed method in Algorithm I and the implementation details in Section 4.1 We also present algorithm-depender hyperparameters in Appendix B We have submitted the code and will make it publicly available.
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In ICLR, 2021.
Maruan Al-Shedivat, Jennifer Gillenwater, Eric Xing, and Afshin Rostamizadeh, Federated learning via posterior averaging: A new perspective and practical algorithms. In ICLR, 2021.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas N Diggavi. Qsparse-local-sgd. Distributed sgd with quantization, sparsification, and local computations. IEFE Journal on Selected Areas in Information Theory, 1(1):217-226, 2020.
Debora Caldarola. Barbara Caputo, and Marco Ciccone. Improving generalization in federated learning by seeking flat minima. In ECCV, 2022.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. In NeurIPSW, 2019.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. In NeurlPS, 2019.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topeu. Faster non-convex federated learning via global and local momentum. arXiv preprint arXiv:2012.040661 2020.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adaptation of deep networks. In ICML, 2017.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimiza- tion for efficiently improving generalization. In ICLR, 2021.
Liang Gao, Huazhu Fu, Li Li, Yingwen Chen, Ming Xu, and Cheng-Zhong Xu. Fedde: Federated learning with non-iid data via local drift decoupling and correction. In CVPR, 2022.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Feder- ated learning with compression: Unified analysis and sharp guarantees. In AISTATS, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, 2016.
Kevin Hsich, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In ICMI., 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.063:0 2019.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Federated visual classification with real-world data distribution. In ECCV, 2020.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for on-device federated learn- ing. In ICML, 2020.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri. Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Breaking the centralized barrier for cross-device federated learning. In NewrlPS, 2021.
10

---

Under review as a conference paper at ICLR 2023
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd hetero- geneous data. arXiv preprint arXiv:1009.0475, 2019.
Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong. Jia Liu, Ketan Rajawar, and Pramod K Varshney. Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning. In NeurIPS, 2021.
Jinkyu Kim, Geeho Kim, and Bohyung Han. learning. In ICML, 2022.
Multi-level branched regularization for federated
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Qinbin Li, Bingsheng He, and Dawn Song. Model-contrastive federated learning, In CVPR, 2021.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy, Feddane: A federated newton-type method. In ACSCC, 2019a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks, In MLSys, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv: /90.022/99 2019b.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv: /9/2. 12844, 2019.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. NeurIPS, 2020.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--ffiiinn learning deep networks from decentralized data. In AISTATS, 2017.
Hyeon-Woo Nam, Moon Ye-Bin, and Tae-Hyun Oh. Fedpara: Low-rank hadamard product for communication-effcceent federated learning. ICT.R, 2022.
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 NeurIPS, 2019.
Zhe Qu, Xingyu Li, Rui Duan, Yao Liu, Bo Tang, and Zhuo Lu. Generalized federated learning via sharpness aware minimization. In ICML, 2022.
Sashank J Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In ICLR, 2021.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. FedPAQ: A communication- tization. AISTATS, 2020.
federated learning method with periodic averaging and quan-
Sebastian U Stich. Local sgd converges fast and communicates little. In ICLR, 2019.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv: 1900:05350, 2019.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. Journal Machine Learning Research, 2202 2021.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication-effcieenn distributed sgd with slow momentum. In ICLR, 2019a.

---

Under review as a conference paper at ICLR 2023
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective in- consistency problem in heterogeneous federated optimization. arXiv preprint arXiv:2007.07881, 2020.
Shigiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. JEEE Journal on Selected Areas in Communications, 37(6):1205-122) 2019b.
Yujia Wang, Lu Lin, and Jinghui Chen. Communication--fficiinn adaptive federated learning. In ICML, 2022.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedom: Federated learning with client-level momentum. arXiv preprint 21th:22106.18774,, 2021.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. AAAI, 2019.
Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu, Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. In arXiv preprint arXiv:2005. 1418, 2020.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv: 180.0008,, 2018
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for heterogeneous federated learning. In ICML, 2021.
A CONVERGENCE OF FEDACG
We now present the theoretical convergence rate of FedACG. We first state few assumptions for the local loss functions (0), which are commonly used in several previous works federated optimization (Karimireddy et al., 2020 Reddi et al. 2021: et al. 202I). First, the local function (-(.) is assumed to be I- for all E (I,..., Le.,
(v) V.)( S L|[x - yll Vn,y- y-
local functions
{ are convex, we additionally have
VE,
2LN Σ [VL,(=) vx,(x))1 < L(x) - -(xx) and
(8)
V,, (VL, 2- - -c,(2) + L.(v) + L 2 -1===11
(9)
(z) and VL(x.) (,(x)) have bounded variance, i.e., Ep, [[) vz,())) < o², and bounded gradients i.e., [|Cr(z)]l2 < G. for all x. Based on the above assumptions, we derive the following asymptotic convergence bound of FedACG.
where C(x) 1/2 EN
Second, we assume the local loss functions
A.1 NON-CONVEX ANALYSIS
Theorem 1. (Convergence of FedACG) Suppose that local functions {ft) are non-convex and L-smooth. Let z' 8t Am for any 0 X 1. Then, by setting 7 min FedACG satisfies,
1->
C
2LK
VFFT
f
min E + Am 5 2(F(zz) F.) (1- max k
2LK
Vi V
B"
++1
1-
C
Vt+1
(10)
where D" = [ー>}] ((1 + L*K4 ((1 - A) +
XLLK²
+ (1 +
AN
(1
1S ()K2
+
3
21-
|
Ix*K2 )) 2
LK²
(2+ 1a1 )
12

---

Under review as a conference paper at ICLR 2023
Proof. We start the proof from the result in Lemma
E[F(2(+1) - F(2 -
VF + + B¹:
where B nk 1 - !LK
1-x and B'
2(1 2(1-X) x)2 (11 L'K* )1 (1 +
x/2
x'LK²
(1+
[s.((N (1
4N
1-1
2(1-
(LK2
LX*K² x1-x}=)) マ
LK* 2
(1 x 0²2
x²
respectively.
By summing the above incqualities for ...... t and by noting that
1-d
ZK
B
E VF( + >m'))l F(=(+1) + (t (t+ 1I
k=
s <BF((=))
Then
f (2o) - f.
B'
min
E V (0' + =mm²)
+
(11)
(t 1)B
B
Assume 1) S
1-A 2LK
then B
R 2(
Then
min E VF (0' + Amm))1 (FF F1)
2(1 - X) 1₁K
B'.
(12)
n)((1 +1)
Noting that 17 = min
1-1 C
VIFT j. we can have
21.
min B BI/ (0' + Am') < (2)) F.)
2LK
vt+1
C
B"
k=......
1+1
max
1-X C
VI +
(13)
where B" (1~)) ((1 L²K1 (1 X) +
ALL 2(1-
+ (1
[ (1
N
(LLK2
+
LA*K2 G² LK² (2+ ( ) 0² We then complete the proof by noting that 1 = +mm
0
Lemma 1. For proving Theorem 1 first prove the key Lemma below. Let z' 0¹ + *
A 8: (01-1 + Xm--1) Σk- f (.))). 8 = N ExEIN) K- F and
e' A
8*. FedACG satisfies for any t 2 and 0 S A 1
El (2K+1) - [zx)] < BE | (xs))l² +B',
where B nK| (1 pLk 1-x 1-X and B' x²
-1- ((1
[1 - X)
LLLK2
+ (1+
4N
3
2Q1
[.
1841 x1) - G2
12*K²
+ LK²
2 + パ- 02)
1
13

---

Under review as a conference paper at ICLR 2023
Proof.
L
=((ltt)(((())) (VF()) -2) 2 -11=4t1-= - =912
I
=F((') 1 (FF(2) A+ 2(1 2)2
A 1
= =F(²') +
+ 1 1- r (VF(2") +1 1 + VKF + Am') - nk + Amm)))
+ 2(1 2)2 ||el+1 + 11
1
=F(x²)+ 1- (VF(z'),
1 A (VF(2'), (8*h) +nK + Amm))))
n X (VF(='), VF(O0 am
L
+ 2(1 ))2 |le 1+ + 1011
1
= =F(²)) (VF(='),
1 (VF(z'), 8r +nkVF(O' + Amm'))
n
nk
1 (VF(2')) VF((0' + Am'). VF((0 + Amm))) 1- VF(00* + +1m))
L
2(1 x)a Iollet11 + 1
First inequality comes from the L-smoothness of the loss function F. By taking expectation on both sides, get following equation.
B(F(s+t)) F(z)) B((VF(=') 8' +nKKF(( Am'))]
nk BKVF((=') VF(OO + Am'), VF(0' Am'))]]
L
BIIIVF(0' Am + 2(1 - 2)2 Fllle 8
1 X
([I + EIIl L (5' + FKF + 11
<
2(1 A)
nr-
L
B(IV VF(O0 Am Am
E [1[1e(11191 + B[||o++112
4L.
2(1 A)2
( Kn )²
Kn 1-x JEIIF + +
First line holds because E[c++1== = 0. Second inequality comes from the Lemma 5 find the upper bound of five terms depicted in the last inequality. I''s upper bound is,
Now we have to
I = =1=1"EI1
= G2
NE[M]
The upper bound of II", III", and IV* are handled Lemma '* upper bound is,
Lemma and Lemma respectively.
K-1
K-1
V Ell N
Σ
Σ
E
B[IVF MP s
K2²
N
iE[N]
k=
SE[N]
0=0
Substituting upper bound for five items yields the desired result.
Lemma 2. (6 + *VKF(( >mm)) in the proof of Lemma has following bound.
Bll (8t + nKVF + >m L²²
3
14

---

Under review as a conference paper at ICLR 2023
Proof.
1 Elll (6' + nKVF(0' + +)m/))113) Ell| (8t + nKVFF(' + +Xm²))112
1
1)
K-1
Elll 1
Σ
Σ
(-VF(())))))))) + V. + +
N
N 0=0
K-1
K
Σ
BII(- + VF.(0' + {11
ME[M] K=0
K
K-1
El - -0,001
N
[E[N]
K=
L
K-1
EII
(0F
N
NEIN
K=0
PTPK
K-1
Σ
E
(
N
ME[N]
R=O
LL'K
K-1 Σ
Σ
K
N
NE[N]
K=0
PIPK-G2
3
Inequality in the third and sixth line comes from Jensen's inequality. Inequality in the fourth line is derived by the smoothness of the objective function. Inequality in the seventh line use bounded gradient assumption.
Lemma 3. () VFF(O' + >22 in the proof of Lemma 6 has the following bound for any 0 S <
72 1+
AN
(1 (8 N
+
22
[[F((>> - V.F(0' + +1 s
Se
SN 1)
(1 A)1
Proof.
X²
2²
E [[(((()))- - VFF(O + +mm'))l S T.
m 12
R Rl|m'
1
X
(1
X)2
E
(1 Xj²
k==
where the first inequality comes from the L-smoothness of the global loss function F. while the last equation comes from the unrolling the recursion of the momentum m², i.e., m² = Ei A AA
Let r
Σ Ei X
-- For 0 < A 1,
< Then
X+ 1+2
112
(1 - xy² EI|
x (1 X)2
r x
0=
112
X11,2
<
(1 1|² I'
(1 - xy2 1IE
x2
4N
+ 1222222202 11- 1 |
S 11
(1 - A)
15

---

Under review as a conference paper at ICLR 2023
Lemma 4. E|jel? in the proof of Lemma has the following bound,
Nx22 |5t||
11 W x²² + (N - 1)|s N
(1
)G2
Proof.
We have El|e²112
1E| A 8'11. Note that:
K-
K-1
K
BIJA' - 8912==11
(F((K)))))
V. +
Σ
Σ
(0
S
S
N
iES:
K=U
iES: A=
EE[N]
R=U
K Vii(Ot VF.CO + E
K-
=
E
VF.(0% - 8'12
SES, k=U
iES, R=0
1
(F((0)))) 1
S
SES: k=
VES: R=0
K-1
17 K2² + EI|
-F((0()) 1
St
iES,
(A)
In (A), we take expectation with respect to S& and total clients N. For that, we Lemma 4 of Reisizadeh et al. 2020). Specifically, using Eq. (59) in Reisizadeh et al. 2020), we get:
(A)
S
11
S
[ N(N - -
Σ N
EI
K
VF
8t -11
S
N
2
S
[. -
2
Σ
EJ
2
Σ KE[N]
K B
Σ
V (1WW)))
[S,12
N
N(N - 1)
N
YE[M]
k=
k=
4n²
SS
[s.1([s.) 1 Σ
K-1
E
18
N
N(N - 1)
KE[N]
K=
4n2
SS
(s.(((s))))
N(N 1) NK
S
This gives us the desired result.
Lemma 5. (Relaxed triangle inequality). For any a > 0. 1l v2ll s (1 + a) |ll 2 +
(1+ d) ||
Proof. This lemma holds because when we organize the formulas on the right, we get 0 <
|av] 22
A.2 CONVEX ANALYSIS
Theorem 2. Suppose that local functions N are convex and T-smooth. Then, for 1/2 < A <1
[
and L 1-x
S B, FedACG satisfies,
T
B(1 - A) 100 - 0.12 + X N gt-1 - E {(o))
1
Ve, (09) 113)
E
S T
T
B N
1=1
0
where 0, = -argmin (()), 0¹
[..] Eies,
ies, 0f.
16

---

Under review as a conference paper at ICLR 2023
3 1 L. I-A we get the statement Theorem in the main paper. We utilize similar approaches in SCAFFOLD (Karimireddy et al. the proof. We define momentum m
2020 and FedDyn (Acar et al. 202T) analysis throughout
0' ge-1, and a set of variables for the analysis. Following
analysis in FedDyn (Acar et al. 2021). J. we first define virtual variable {0{ as,
: argmin (0) + 2 | (0' Am Am1=
(14)
0e consists of the locally trained models from participating devices. We express the server model as active device average and its relation with accelerated model as,
1
0
0% 0' -" Am'.
(15)
S
iES.
We also define & which calculate difference between local models and the average of device models from previous round as,
61 Σ
Ellē; -
(16)
(E......
If models converge to 0.. G, will be O. consequence of the following Lemma, Lemma 6. For convex and L-smooth {f)) functions, 1/2 < X < and L T-X S B, FedACG satisfies
After these definitions, Theorem can be seen direct
E110 - 0.1l + ket S E 1 0-112 + KEE- - KoB (1(00-1) E(0-))
where 0, arggin ((0), (3" 41
4,92 (A)
43 48- Kig -
41 9- A-)
33- -3-"2
Lemma 6 can be telescoped in the following way, Kg [(((0-1) - E(B.)] [E| 6 11 + riC;_1) (Bl10² -0.112 2 -B110--0.11- keE)
T
E [e(0--1)- - -((0.]] - (0 0.11 + kEO) - (B|10" - -0.11 + KET)
60
If < < and
I S 8, ko and x become positive. Eliminating negative terms on RHS gives, I-x
E [((0)-2) E(O=)] s E| 6a1 KED
Kg
Applying Jensen's inequality on LHS gives,
1 T
1 S (110) 0-11 ( O
1 T
E
-E(0,)
E(O.)
T KO
which proves the statement in Theorem 2 Similar to convergence analysis of gradient descent,
|10 0. is expressed as |00 00 0-1 0. and expanded in the proof of Lemma 6 To tackle the extra terms, we state the following Lemmas and corresponding proofs. We first bound
||0- 112 with the following,
Lemma 7. Suppose that local functions { are convex and L-smooth. Then we can bound the global model update,
El - -0--000-11 00-1112 S
(17)
Proof. Note that
E 8
8--
8
81-1)
E
10
8
11
S
S
iES,
LiES,
S
2
IE
6r
E
0
S.S
5.1
N
LieS.
17

---

Under review as a conference paper at ICLR 2023
where first equality comes from Eq. (5) The following inequality applies Jensen. Remaining relations are due to Of 0 if St, taking expectation by conditioning randomness before time t and definition of 6z-
We introduce additional Lemma to further bound term in Lemma introduce triangular inequality here.
Before the proof, first Lemma 8. Hu R triangular inequality satisfies
n S 72
8
|1
122
j=1
Proof. With Jensen's inequality, gives the inequality.
|
0//
1|
S # |/ Multiplying both sides with n?
Lemma 9. For convex and L-smooth { functions, then the updates of FedACG have bounded drift,
(1
4L2
8L
4 S
4x2
4-1
+
R [((0--1) - e(0.))
(18)
B²
B
Proof.
N
0
0² 112
N
1=1
N
1
1
ve((0)) + >m-=11
E
N
3
i=1
N
1
Ve,(0.) + ve((.)) ve,(0-11) 1 ve((0-
E
3
(O, + Xm--1
32 -
4
N Σ
4 1
E (0,))
N
Σ
((,(0)) - ve((0-1))12 + 41
32 N
1=1
4L2
8L
g2 Et
+
4X2
E [((00- - -((0.)
B
where first and second equations come from Eq. (15) and first order condition of Eq. 14 inequalities come from Lemma g and convexity.
Following
18

---

Under review as a conference paper at ICLR 2023
Now, let's express ||0| - 8x1l term as,
EllØ' 0.11² 2 El|0-=1 0. 0³ - 112
E1100=1 1 0.112 21 (
00, 10-00-0-11 -0--1) =B100-00* 0--112
N
E110011 0.112 + (1 N
2
(0-- 02, - -V(((0)
+ 1B10 - 0² 112
S BB100-1 1.1
+ E 112
N
2
E (j().) 11(0-=1) + 1.
2 1100 0r 0--1112
(1- 11
i=1
El10'-1 11,1
E [e(ot-1) 1 - E(0.)]
(1 2)B
L
(1 X)B² <e + Eel0
11- 112
(19)
where approximately have E/m''] (1-A)aN Σ E (0)) since global gradient infor- mation is an exponentially updated with coefficient Following inequality is due the quadratic bound by convexity and T-smmothhnsss of local functions.
Let's scale Eq. (19) with (1-A)(3=411²=4"33 Note that the coefficient is positive due the condi- DLL-333X
tion on ,3 and A. Summing scaled version Eq. 19 and Lemma 9 gives the statement in Lemma
B HYPERPARAMETER SETTING
For the hyperparameter selection, we assume the scenario that the server can compute the validation accuracy through communication with clients the early stages, which is common to all algorithms.
For the experiments on CIFAR- 10 and CIFAR-100 we choose as the number of local training epochs (50 iterations) and 0.1 as the local learning rate. We set the batch size of the local update to 50 and 10 for the 100 and 500 client participation, respectively. The learning rate decay parameter of each algorithm selected from (0.995, 0.998, 1} achieve the best performance. The global learning rate is set to 1, except for FedAdam, which is tested with 0.01.
For the experiments Tiny- we match the total local iterations of local updates with other benchmarks by setting the batch size of local updates as 100 and 20 for the 100 and 500 client participation, respectively.
As for algorithm-dependen hyperparameters, in FedCM is selected from 10.1. 0.3, 0.5), a in FedDyn is selected from (0.001, 0.01, 0, and a in FedDC set to 0.01. r in FedAdam set to 0,001 while in MOON is set to 1. 8 in FedAvgM is selected from f0.4, 0.6, 0.8), B in FedProx and FedACG is selected from 10.1, 0.01, 0.001}, and À FedACG is selected from {0.8, 0.85, 0.9).
We submitted and will release the source code to facilitate the reproduction of our results.
C EVALUATION ON VARIOUS DATA HETEROGENEITY
Tables 7 and [ show that FedACG matches or outperforms the performance of competitive methods when data heterogeneity not severe (Dirichlet 0.6) or absent (IID) on CIFAR-10 in most cases. Note that, while the compared methods show performance degradation as the participation rate de- creases, FedACG shows little degradation as the participation rate decreases for both data splits. This implies that FedACG is more robust for low participation rates than other baselines. This is partly because low client heterogeneity reduces noise the momentum of global gradient, which attributes to the smooth trajectory of global update. Since FedACG effectively incorporates the mo- mentum for local updates, FedACG is relatively unaffected by the partial participation of federated learning.
19

---

Under review as a conference paper at ICLR 2023
Table 7: Results with Dirichlet (0.6) data split on CIFAR-I0 and CIFAR-I00 for different federated learning settings. Accuracy at the target round and the communication round to reach target test accuracy are based on running exponential moving average with parameter 0.9. The arrow indicate whether higher (f) or lower (1) is better. FedCM and FedDC! require 1.5x and 2x communication cost for each communication round, respectively.
(a) Dirichlet (0.6), 100 clients, 5% participation
CIFAR-10
CIFAR-100
Method
(%, T)
rounds (U)
acc.
(%.
rounds (J)
500R
1000R
81%
87%
500R
1000R
50%
56%
FedAvg [McMahan al.
2017
80.56
85.97
520
1000+
43.91
49.18
1000+
1000+
FedProx (Li |
2020
80.39
85.53
524
1000+
43.15
48.45
1000+
1000+
[Hsu FedAvgM
2019
84.65
87.96
355
811
46.66
52.49
735
1000+
FedADAM
2021
80.25
83.52
526
1000+
45.95
51.63
778
1000+
FedDyn (Acar at. 2021
87.23
89.49
310
487
50.51
56.78
488
886
MOON
Li Li al.. 2021
84,95
87.99
272
728
55.76
61.42
338
527
FedCM
Xu al.
2021
82.84
86.64
1000+
53.75
60.48
331
FedDC
Gao et ul.
2022
88.05
89.58
270
437
56.00
60.58
347
491
FedACG (ours)
87.57
90.56
218
453
58.82
63.88
243
396
(b) Dirichlet (0.6), 500 clients, 2% participation
CIFAR-10
CIFAR-100
Method
acc.
(%. T)
rounds (J)
acc.
(%.
rounds (L)
500R
1000R
69%
80%
500R
1000R
32%
41%
FedAvg
McMahan et al.
2017
62.79
75.17
671
1000+
29.41
36.62
648
1000++
FedProx
ef a 2020
62.48
75.10
688
1000+
29.62
36.70
647
1000+
FedAvg
Hsu et al 2019
69.10
80.26
498
981
32.78
41.93
468
942
FedADAM (Reddi ef
2021
68.48
78.92
535
1000+
37.57
48.29
341
624
FedDyn
Acar ct al. 202
68.53
80.33
513
983
32.06
43.28
498
917
MOON
Tr al. 2021
74.29
80.66
368
921
31.64
41.61
515
931
FedCM
Xu al.
2021
71.42
78.94
429
1000+
26.82
39.78
714
1000+
FedDCt
Gao
2022
77.74
86.32
596
34.24
44.69
444
FedACG (ours)
78.49
85.28
565
39.61
49.70
304
540
D CONVERGENCE PLOT
D.1 EVALUATION ON VARIOUS FEDERATED LEARNING SCENARIOS
Figure 2 to Figure show the convergence of FedACG and the compared algorithms CIFAR- 10, CIFAR-100 100, and ImageemeeNet for various federated learning settings: varying the number of total clients, participation rates, data heterogeneity. FedACG continuously matches exceeds the performance of the most powerful our competitors in most learning sections.
Figure shows the convergence plots under massive clients, 1% participation rate setting. The result shows that FedACG takes the lead in most learning sections, which also demonstrates the effectiveness of FedACG.
D.2 EVALUATION DYNAMIC CLIENT SET
Figure 6) shows convergence plot when the entire client's pool changes during training. The result shows that FedACG outperforms the baselines in most learning sections. Note that FedDyn shows worse performance than FedAvg in the overall section of learning, and only achieves FedAvg's 's performance at the end. This partly because needs to store local states for local training each client, which requires kind of warm-up period for newly participating clients contain useful information. In contrast, FedACG, which is free from these restrictions, shows strength in a realistic federated learning scenario where the pool of the entire clients changes during training.
20

---

Under review as a conference paper at ICLR 2023
Table 8: Results with IID data split on CIFAR-10 10 and CIFAR-100 for two different federated learn- ing settings. Accuracy at the target round and the communication round to reach target test accuracy based on running exponential moving average with parameter 0.9. The arrows indicate whether higher (1) or lower (f) is better. FedCM and FedDCt require 1.5x and 2x communication cost for each communication round, respectively.
(a) IDD, 100 clients, 5% participation
CIFAR-10
CIFAR-100
Method
acc.
(%, 7)
rounds (.)
acc.
(%, 1)
rounds (L)
500R
1000R
82%
89%
500R
1000R
52%
58%
FedAvg (McMahan et al.
2017
85,28
88,69
372
1000+
43.96
48.20
1000+
1000+
FedProx Li Cl al 2020
2022
84.79
87.99
384
1000+
43.57
47.75
1000+
1000+
FedAvgM (Hsu el al. 2019
87.67
89.96
258
375
47.43
52.83
880
1000+
FedADAM (Redc al. 2021
85.29
87.97
286
1000+
52.23
57.73
496
1000+
FedDyn Acar et al. 2021
89.19
90.70
269
492
50.37
56.88
592
898
MOON
Li
al. 2021
88,24
89.96
207
628
58.50
64.73
311
484
FedCM Xu al. 2021
87.38
89,65
182
782
57.10
62.48
266
466
FedDC Gao al.
2022
90.07
90.80
55.17
61.00
400
FedACG (ours)
90.57
92.29
354
59.82
64.08
244
(b) IID, 500 clients, participation
CIFAR-10
CIFAR-100
Method
acc.
(%. T)
rounds (J)
acc.
(%, f)
rounds (T)
500R
1000R
83%
500R
1000R
33%
42%
FedAvg
McMahan al.
2017
68.70
78.21
10004
30.71
37.85
664
1000+
FedProx
ef al. 20/20 20020
68.74
77.96
1000+
30.11
37.13
685
1000+
FedAvg
HHs cf al. 2019
74.34
83.64
943
33.54
42.55
479
971
FedADAM (Reddi
2021
75.32
84.01
491
915
38.74
48.94
328
FedDyn
Acar et al, 2021
74.81
84.71
398
823
33.20
42.91
492
936
MOON
al.
202D
69.86
81.89
586
1000+
28.82
41.26
649
1000+
FedCM
Xu ct al.
2021
77.84
83.26
491
959
29.59
42.04
653
991
FedDC!
Gao al.
2022
80.87
87,53
358
574
33.93
45.80
476
817
FedACG (ours)
80.15
87.47
316
578
41.16
49.10
299
525
21

---

Under review as a conference paper at ICLR 2023
87
80
64
56
FedáCo FedCM FedDyn
Feddug
FedACG FeeCM FedDyn
FedAug
FedProx
FedProx
FedDC
FedDC
FedADDM
24
FouNDAM
Rounds
Rounds
(a) Dirichlet (0.3), 100 clients, 5% participation
(b) Dirichlet (0.3), 500 clients, 2% participation
90.0
07.5
85.0
75
8 80.0
86
77.5
FedACG FedCM FedtDmm FacACIAM
Fedivag
FedACG FedCM
Fedlug
FeeSrrx
56
PedProx
72.5
RedDCC
FedAngg RedADAM
MOON
70.0
200
400
600
1000
Rounds
Rounds
(c) Dirichlet (0.6), 100 clients, 5% participation
(d) Dirichlet (0.6), 500 clients, 2% participation
90.0
88.5
70
8 85.5
84.0
80
82.5
FedACG PoOGM
Fedivg
FedACG FedhigM FedADAM
FedAug MOON
FeeProx MOON
79.5
FatAroM FedADAM
50
200
400
600
800
1000
200
400
600
800
1000
Rounds
Rounds
(e) IID, clients, 5% participation
(f) IID, 500 clients, 2% participation
Figure 2: The convergence plots of FedACG and the baselines CIFAR-10 with different federated learning scenarios.
22

---

Under review as a conference paper at ICLR 2023
50-
56
8
FedáCo TedCM
Feddvg
FedACG FedCM
FedAug FedProk
TedPrix
FeaDyn
FedDyn
32
FodADAM
FsGADAM
MOON
Rounds
Rounds
(a) Dirichlet (0.3), 100 clients, 5% participation
(b) Dirichlet (0.3), 500 clients, 2% participation
2
32
FedACC FedDyn FedAiggM FedADAM
Feddug
24
FodAco FedAvgV FocADAM
FodAug
FedProx
32
FeaDC
MOON
MOON
28
430
1000
400
600
1000
Rounds
Rounds
(c) Dirichlet (0.6), 100 clients, 5% participation
(d) Dirichlet (0.6), 500 clients, 2% participation
8
28
Fadkug
FedACG FadDye
FedAug
FedEM
FedDyn
FedDDC
FedDC:
FedAuggM
MOON
20
FadAugM FedADAM
MOON
FidACAAM
200
400
630
800
1000
200
400
600
800
1000
Rounds
Rounds
(e) IID, clients, 5% participation
(f) IID, 500 clients, 2% participation
Figure 3: The convergence plots of FedACG and the baselines CIFAR-100 with different feder- ated learning scenarios.
45
32
26
2
33
FedACG FedDyn PedhiggM FedACAM
Fedlug
16
FedACG FedMigM FecADAM
FedAvg FedProx MOON
FedDC
MOON
200
400
830
1000
400
600
1000
Rounds
Rounds
(a) Dirichlet (0.3), 100 clients, 5% participation
(b) Dirichlet (0.3), 500 clients, 2% participation
Figure 4: The convergence plots of FedACG and the baselines I'an--Im with different federated learning scenarios.
23

---

Under review as a conference paper at ICLR 2023
8
25
FedACG
Fed/ug FedPrix
15
FeuNCG
Fed/vg RedProx
FedCM
FedCM
FedDyn
FedDC
FeiDyn
FedDC
Feeligg
FedADDM
Rounds
Rounds
(a) 10
(b) CIFAR-I0K 100
Figure 5: The convergence plots of FedACG and the baselines when participation rate is low (1%) for 500 clients CIFAR-I0 and CIFAR-100. The Dirichlet parameter is 0.3 for the experi-
ments.
39
33
27
FadACO
FodDC MOON
FadDyn FadAug
18
200
400
800
800
1000
Rounds
Figure 6: The convergence plots of FedACG, FedAvg, FedDyn, FedDC, and MOON on CIFAR- 100 when the client changes over dynamically: we sample 250 clients out 500 clients candidate clients set at every 100 rounds over 10 stages on Dirichlet (0.3) split. 10 clients out of the sampled client set participate for the local training for each communication round. Dirichlet parameter is set to 0.3.
24

---

Under review as a conference paper at ICLR 2023
E DISCUSSION ABOUT THE DIFFERENCE BETWEEN FEDACG AND THE OTHER METHODS
FedAvgM The unique characteristic of FedACG lies client accelerated gradient. Although FedACG and FedAvgM global momentum in common, FedACG broadcasts the accelerated global model by adding global momentum to the current global model (8'-1 + Am" while Fe- dAvgM (Hsu et al. 2020) broadcasts the current global model(0(-1) each client as the initial point of the local model. To clarify the novelty of FedACG, we provide two pseudo-codes FedACG and FedAvgM with local regularization term in Algorithm and Algorithm respectively. Figure 7 and Figure also illustrates the server broadcasting and aggregation process of FedACG and FedAvgM, respectively.
FedProx FedACG is totally different method from FedProx for three reasons. First, FedACG utilizes the global momentum for server update as in Algorithm 2 Second, since FedACG uses client accelerated gradient, the local model's initial point is different from FedProx. From this, third, objective function FedACG regularize the distance not between the local model and the previous global model (FedProx), but between the local model and the accelerated point.
F EFFECT OF LOCAL REGULARIZATION TERM
Table 9 shows the effect of local regularization term in FedAvg, FedAvgM, and FedACG. Note the role of the local regularization term is different in FedACG due to the acceleration term (+Am²-1) included in the message from the global model. We first observe that employing accelerated client gradient by adding global momentum the current model plays critical role for the performance gain. We also observe the effectiveness of the local regularization term in FedACG; Adding the local regularization term the other baselines do not necessarily achieve performance gains in CIFAR-10 and CIFAR-100.
Algorithm 2 FedACG
Input: 3, X, initial server model 0", number clients N, number of communication rounds T, number of local iterations K, local learning rate n
Initialize global momentum m7
for each round / 1,2.....
do Sample subset of clients S. C (1,...,NN) N} Server sends f--1 Am=-1 for all clients E St for each client E S,, in parallel do Initialize local model 0 0t-1 Am
for each local iteration A = 1, K do
Compute mini-batch loss fa x = (0) + -10 1, -80-1 (m' >m'- |11
0i 0º k- f.
end
A = 0. (QC-1 Xm--11
Client sends A back to the server end
In server:
A = Eies, !
m' Am3 + A
0r = 0--1 m
end
Return 0º
25

---

Under review as a conference paper at ICLR 2023
Algorithm 3 FedAvgM with local regularization
Input: 3. X, initial server model 80_ number of clients N, number of communication rounds T, number of local iterations K, local learning rate !
Initialize global momentum m for each round & 1.2..... do
Sample subset of clients S. C [I,...,,N) Server sends g for all clients i St
for each client E S,, in parallel do
Initialize local model 0 = g
for each local iteration
2,...... K do
Compute mini-hatch loss [0 = (0 + 20 - 11-112
f
H k-
VVV f
end
A = 0f 0C-1
Client sends Af back to the server
end
In server:
A' = Lies, Wi4i
m' Am + A
0r 0'-1 + m
end
Return 6¹
gt-
Xmn 2- 1-2
4
Accelerated point 2
Xm
A
A 1-1
f 2
Accelerated point at ]
gt
3
t
2
Global momentum
Averaged local updates
Server update
Figure 7: An illustration the FedACG during two communication rounds
Table Effect of local regularization term on different federtaed learning algorithms on CIFAR-10 and 110 with 2% participation and 500 clients.
Server update
Method
Accelerated client gradient Local regularization
CIFAR-10
CIFAR- 100
w momentum
FedAvg
71.45
38.11
FedProx
70.75
36.16
FedAvgM
77.49
40.54
FedAvgM w local reg FedACG w/o local reg FedACG
76.16
41.64
82,20
46.80
82.80
48.40
26

---

Under review as a conference paper at ICLR 2023
1-1
0t
2
Xmn 1
A
0
Am 1-1
A
1-1
A
1-1
A
t
2
Global momentum
Averaged local updates
Server update
Figure 8: An illustration of the FedAvgM during two communication rounds
27


Reviews:
[{"review_id": "yYBzpGo3kd", "reviewer": "Reviewer_bEuE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a communication-efficient federated optimization algorithm that deals with client heterogeneity under large-scale and low-participation FL settings. The proposed algorithm, FedACG, leverages global momentum and local regularization. This paper demonstrates outstanding performance in terms of communication efficiency and robustness to client heterogeneity.", "summary_of_the_review": "The paper proposed an interesting method for FL. But I am afraid that it has several major weaknesses to be addressed.", "strength_and_weaknesses": "Strength:\n1. Propose practical algorithm that considers more realistic and strict FL settings\n2. Outstanding performance in terms of communication efficiency and model performance over many baselines\n3. The paper is well-written and easy to understand.\n\nWeakness\n1. The proposed algorithm FedACG is very similar to FedProx (Li et al., 2020) in the sense that FedACG has the additional hyperparameter \\lambda. For example, when \\lambda = 1, FedACG becomes FedProx. It would be great if this paper could elaborate on the relationship between FedACG and FedProx, and why introducing this additional hyperparameter \\lambda is beneficial. \n2.  Following on from the first point, introducing this additional hyperparameter \\lambda results in better performance but it’s not without any cost. Typically, we want to keep the number of hyperparameters as minimal as possible, because hyperparameter tuning is very costly. Actually, according to Table 6(a), the performance of FedACG varies a lot depending on the value of \\lambda. \n3. For the convergence analysis (i.e., Theorem 1), I am not sure why we need to assume 0.5 < \\lambda < 1, which seems to be a very strict assumption for \\lambda because it’s practically possible for 0 < \\lambda <= 1 (or even \\lambda > 1 if we want more emphasis on the momentum m). Is it possible to derive a similar convergence rate when 0< \\lambda < 0.5? In addition, when \\lambda = 1,  FedACG becomes FedProx. It would be great if the convergence analysis can recover the analysis of FedProx when  \\lambda = 1.\n4. Lastly, [1] (see reference list below) has also considered using momentum for FL, and may need to be discussed in this paper.\n\nReference.   \n[1] Das, Rudrajit, et al. \"Faster non-convex federated learning via global and local momentum.\" Uncertainty in Artificial Intelligence. PMLR, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kZOn8tQw_r", "reviewer": "Reviewer_Ym7U", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper (FedACG) proposes the following additive regularization term to the learning objective function for federated learning clients:\n\n$$\n\\quad\\quad \\frac{\\beta}{2}||\\theta - (\\theta^{t-1} + \\lambda m^{t-1}) ||^2 \n$$\n\nwhere $\\beta$ and $\\lambda$ are tuning parameters. $\\theta$ is the model parameters. The $m$ momentum term is calculated at the server, which is the difference between the sum of weighted parameter values received  from clients at round $t$ and round $t{-}1$. This is similar to $\\ell_2$-regularization, but with a gradient acceleration (or momentum term).\n\nThe paper uses ResNet-18 and evaluates on datasets: CIFAR-10, CIFAR-100, Tiny-ImageNet, FEMNIST, and CelebA. IID data is generated via random sampling without replacement. Non-IID data is generated via sampling label ratios from a Dirichlet distribution. All clients hold the same number of training data.\n\nCommunication efficiency is captured by (reduced) number of communication rounds to achieve a particular level of test accuracy.\n", "summary_of_the_review": "The proposed technique is simple and appears effective given the empirical results. However, the empirical evaluation can be improved.\n\nUpdate: I thank the authors for answering my questions. I will maintain my review. However, having read through the other reviews (and replies) I think that the comparison with (at least) FedAvgM needs to be further clarified and highlighted.\n", "strength_and_weaknesses": "The proposed technique is simple and the idea is intuitive. However, my main concern is with some of the empirical evaluation. Specifically:\n\n1. How many trials were used in running the experiments?\n2. Are the results in Table 1 (a) and (b) under the non-IID setting since the description in the table says \"The Dirichlet parameter is commonly set to 0.3\"? \n3. The way the Dirichlet distribution sampling is used in the paper seems different from [Hsu et al. 2019], where the data is drawn from Dirchlet($\\alpha,\\boldsymbol{p}$), where $\\boldsymbol{p}$ characterizes a prior class distribution over $N$ classes, and $\\alpha{>}0$ is a concentration parameter controlling the identicalness among classes.\n4. Do all the accuracy numbers use the exponential moving average with 0.9 coefficient (meaning older observations are discounted faster)?\n5. In Table 1 (a): for MOON (CIFAR-100), 500R shows Acc. of 83.32%, but 81% is achieved at 543 rounds? In Table 2: for FedDC (CIFAR-10), 500R shows Acc. of 60.56%, but 64% is achieved at 509 rounds. This means over 3% was gained in 9 rounds?\n6. Table 6 shows that accuracy is sensitive to the shown different settings to $\\lambda$, but stable to the show different settings to $\\beta$. This is surprising, and somewhat counter intuitive from the perspective of $\\ell_2$-regularization.\n7. Table 6 shows the more realistic FL setting with feature skew and data imbalance. The results for FedACG compared to FedDC, FedAvg, FedAvgM are close enough such that it is not clear on the statistical significance of the result. I would be curious to see incorporating data imbalance in the main experimental results.\n8. The empirical evaluations are limited to image datasets and one neural network model.\n\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": "K5Yhdp-XrQ", "reviewer": "Reviewer_fVhK", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposed a communication-efficient federated learning algorithm, FedACG to accelerate the convergence of training. Specifically, by adding a momentum to the aggregated weight and using this term as a regularizer, the authors show that the model can converge faster with higher accuracy theoretically and empirically.", "summary_of_the_review": "Overall, the paper presented FedACG, a communication-efficient federated learning algorithm and demonstrated its advantages through extensive experiments. However, it was similar to a previous paper FedAvgM and no discussion about difference between two methods. Thus, it was marginally below the acceptance threshold.", "strength_and_weaknesses": "Strengths:\n- The proposed method is simple yet effective. Figure 1 gives a clear picture of the idea and makes the paper easy to follow.\n- The experimental part is comprehensive. In detail, evaluation was conducted on three representative datasets under different data distribution. And it can be observed that FedACG performed consistently better among these settings. Ablation study to investigate individual components of the method is sufficient.\n- A convergence analysis was provided to show that FedACG can guarantee the convergence of the model.\n\nWeaknesses:\n\n- The biggest concern of this paper is the difference between FedACG and FedAvgM [1]. It seems that FedACG merely adds a regularization term to reduce variance in local clients on top of FedAvgM, in which momentum was also leveraged to update the model in the server side. Then it is surprising to see that a regularizer can contribute to the performance gain significantly. More analysis and discussion of FedAvgM is necessary.\n- To show FedACG achieves a better convergence rate theoretically, there should be a comparison among all other methods, i.e., the asymptotic convergence rate of methods such as FedAvg.\n- \n- It lacks a discussion about differential privacy of FedACG. It is important to a FL algorithm whether it can preserve differential privacy.\n\n[1] Hsu, Tzu-Ming Harry, Hang Qi, and Matthew Brown. \"Measuring the effects of non-identical data distribution for federated visual classification.\" arXiv preprint arXiv:1909.06335 (2019).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9N_8Zd6BXof", "reviewer": "Reviewer_KHhq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper solves the bottleneck of slow and unstable convergence issues in heterogeneous federated learning especially when the client participation ratio is low. The paper proposes a novel framework that can improve consistency to alleviate the heterogeneous issue and then accelerate the convergence of federated learning.", "summary_of_the_review": "1 . The theoretical result seems a bit weak. It only contains a convex convergence result in the full batch setting which is not practical.  Also it is not clear whether the obtained convergence rate is better than other methods.\n2. While the main story is about improving FL when the participation ratio is low, in the theoretical result, I didn’t find the term corresponding to the ratio. Did the author only consider the full participation setting in the theorem?  \n3. Why do we have the constraint that $0.5 < \\lambda < 1$? Any intuitions?\n \nThis paper provides novel methods for improving slow and unstable convergence in federated learning, and solid experimental results back up the method. The convergence analysis can be further improved with detailed discussions.\n \n", "strength_and_weaknesses": "Strengths:\n1. The proposed method seems effective. The introduced momentum term of the global client makes the local model close to the global one. This method does not involve additional communication costs thus it is communication efficient.\n2. The paper shows a complete experimental setup covering several cases that effectively supports the proposed FedACG.\n \nWeaknesses:\n1. From the Algorithm and Theorem 1, it seems the client computes full gradients. Hence the convergence analysis lacks consideration under stochastic gradient variance.\n2. There lacks of nonconvex convergence analysis which is more practical in the real world. \n \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject