FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy
Authors: Yan Sun
Li Shen
Tiansheng Huang
Liang Ding
Dacheng Tao
Venue: ICLR 2023 poster (2023)
Keywords: federated learning

Abstract: Federated learning (FL) is an emerging distributed machine learning framework which jointly trains a global model via a large number of local devices with data privacy protections. Its performance suffers from the non-vanishing biases introduced by the local inconsistent optimal and the rugged client-drifts by the local over-fitting. In this paper, we propose a novel and practical method, FedSpeed, to alleviate the negative impacts posed by these problems.  Concretely, FedSpeed applies the prox-correction term on the current local updates to efficiently reduce the biases introduced by the prox-term, a necessary regularizer to maintain the strong local consistency. Furthermore, FedSpeed merges the vanilla stochastic gradient with a perturbation computed from an extra gradient ascent step in the neighborhood, thereby alleviating the issue of local over-fitting. Our theoretical analysis indicates that the convergence rate is related to both the communication rounds $T$ and local intervals $K$ with a tighter upper bound $\mathcal{O}(\frac{1}{T})$ if $K=\mathcal{O}(T)$.  Moreover, we conduct extensive experiments on the real-world dataset to demonstrate the efficiency of our proposed FedSpeed, which converges significantly faster and achieves the state-of-the-art (SOTA) performance on the general FL experimental settings than several baselines including FedAvg, FedProx, FedCM, FedAdam, SCAFFOLD, FedDyn, FedADMM, etc.

Published as a conference paper at ICLR 2023
FEDSPEED: LARGER LOCAL INTERVAL, LESS COM- MUNICATION ROUND, AND HIGHER GENERALIZATION ACCURACY
Yan Sun
Shen'
The University of Sydney ysun98996uni, sydney edu. au
JD Explore Academy
mat mathshenliee wea.mnii@mmmaaimmmmmmmmmmmmm com
Tiansheng Huang
Liang Ding
Georgia Institute of Technology clanshenghuangsscuee @etps/sccttttmmiil.. com
JD Explore Academy
1 riangding 1 iamm@gmaiiii.. com
Dacheng Tao
JD Explore Academy & The University of Sydney dacheng. tao @eaiimmmi.... com
ABSTRACT
Federated learning is emerging distributed machine learning framework which jointly trains a global model via a large number of local devices with data privacy protections. Its performance suffers from the non-vanishing biases introduced by the local inconsistent optimal and the rugged client-drifts by the local over-fitting, In this paper, we propose novel and practical method, FedSpeed, alleviate the negative impacts posed by these problems. Concretely, FedSpeed applies the prox-correction term on the current local updates to efficiently reduce the biases introduced by the prox-term, a necessary regularizer to maintain the strong local consistency. Furthermore, FedSpeed merges the vanilla stochastic gradient with perturbation computed from extra gradient ascent step in the neighborhood, thereby alleviating the issue of local over-fitting. Our theoretical analysis indicates that the convergence rate is related both the communication rounds T and local intervals K with a upper bound (1/TT) if setting a proper local interval. Moreover, conduct extensive experiments on the real-world dataset demonstrate the efficiency of our proposed FedSpeed, which performs significantly faster and achieves the state-of-the-art (SOTA) performance on the general FL experimental settings than several baselines including FedAvg, FedProx, FedCM, FedAdam, SCAFFOLD. FedDyn. FedADMM, etc.
INTRODUCTION
Since McMahan al. 2017 proposed federated learning (FL), it has gradually evolved into an efficient paradigm for acge-scall distributed training. Different from the traditional deep learning methods, FL allows multi local clients to jointly train single global model without data sharing. However, FL is far from its maturity, as it still suffers from the considerable performance degradation over the heterogeneously distributed data, very common setting in the practical application of FL.
We recognize the main culprit leading to the performance degradation of FL as local inconsistency and local heterogeneoux over-filting. Specifically, for canonical Saal-SGD-basedd FL method, e.g., FedAvg, the non-vanishing biases introduced by the local updates may eventually lead to inconsistent local solution. Then, the rugged client-drifts resulting from the local over-fitting into inconsistent local solutions may make the obtained global model degrading into the average of client's 's local parameters. The vanishing biases have been studied by several previous works Charles & Konečný (202T);
"Lii Shen the corresponding author.

---

Published as a conference paper at ICLR 2023
Malinovskiy et al. (2020) in different forms. The inconsistency due to the local heterogeneous data will compromise the global convergence during the training process. Eventually leads to serious client-drift which can be formulated x" * Lie(m] x /m. Larger data heterogeneity may enlarge the drifts, thereby degrading the practical training convergence rate and generalization performance.
In order to strengthen the local consistency during the local training process, and avoid the client-drifi resulting from the local over-fitting, we propose a novel and practical algorithm, dubbed as FedSpeed. Notably, FedSpeed incorporates two novel components to achieve SOTA performance. i) Firstly, FedSpeed inherits a penalized prox- -tem to force the local offset to be closer to the initial point at each communication round. However, recognized from Hanzely & Richtárik (2020); Khaled et al. (2019) that the prox-term between global and local solutions may introduce undesirable local training bias, we propose and utilize a prox-correction term to counteract the adverse impact. Indeed, in our theoretical analysis, the implication of the prox- mox-correction term could be considered as a momentum- based term of the weighted local gradients. Via utilizing the historical gradient information, the bias brought by the prox-term can be effectively corrected. ii) Secondly, to avoid the rugged local over-fitting, FedSpeed incorporates a local gradient perturbation via merging the vanilla stochastic gradient with an extra gradient, which can be viewed as taking an extra gradient ascent step for each local update. Based on the analysis in Zhao al. (022); van der Hoeven (2020), we demonstrate that the gradient perturbation term could be approximated as adding a penalized squared 1.2-norm of the stochastic gradients the original objective function, which efficiently search for the flatten local minima Andriushchenko & Flammarion 2022) to prevent the local over-fitting problems.
We also provide the theoretical analysis of our proposed FedSpeed and further demonstrate that its convergence rate could be accelerated by setting an appropriate large local interval K. Explicitly, under the non-convex and smooth cases, FedSpeed with an extra gradient perturbation could achieve the fast convergence rate of (1/TT) which indicates that FedSpeed achieves tighter upper bound with a proper local interval K to converge, without applying a specific global learning rate or assuming the precision for the local solutions (Durmus et al., 2021 Wang et al. 2022). Extensive experiments are tested on CIFAR- 10/100 and Tinylmagenet dataset with a standard BesNet-18-GN network under the different heterogeneous settings, which shows that our proposed FedSpeed is significantly better than several baselines, e.g. for FedAvg, FedProx, FedCM, FedPD, SCAFFOLD, FedDyn, on both the stability to enlarge the local interval K and the test generalization performance in the actual training.
To the end, we summarize the main contributions of this paper as follows:
We propose a novel and practical federated optimization algorithm, FedSpeed, which applies a prox-correction term to significantly reduce the bias due the local updates of the prox-term, and an extra gradient perturbation to efficiently avoid the local over-fitting, which achieves a fast convergence speed with large local steps and simultaneously maintains the high generalization.
We provide the convergence rate upper bound under the non-convex and smooth cases and prove that FedSpeed could achieve a fast convergence rate of O(1/T) via enlarging the local training interval K (TT without any other harsh assumptions the specific conditions required.
Extensive experiments are conducted on the CIFAR-10/100 and Tinylmagenet dataset to verify the performance of our proposed FedSpeed. To the best of our interests. both convergence speed and generalization performance could achieve the SOTA results under the general federated settings. FedSpeed could outperform other baselines and be more robust to enlarging the local interval.
RELATED WORK
McMahan et al. 2017) propose the federated framework with the properties of jointly training with several unbalance and non-iid local dataset via communicating with lower costs during the total training stage. The general FI. optimization involves local client training stage and global server update operation Asad et al. (2020) and it has been proved to achieve a linear speedup property in Yang et al. 2021 1). With the fast development of the FL, a series of efficient optimization method are applied in the federated framework. Li et al. (2020b) and Kairouz et al. (2021) introduce a detailed overview in this field. There are still many difficulties to be solved in the practical scenarios, while in this paper we focus to highlight the two main challenges of the local inconsistent solution and client-drifss due to heterogeneous over-fitting, which are acute limitations in the federated
2

---

Published as a conference paper at ICLR 2023
optimization Li al. (2020a): Yang et al. (2019); Konečný al. (2016); Liu et al. (2022) Shi et al. (2023):
Liu et al. (2023).
Local consistency. Sahu al. 2018 study the non-vanishing biases of the inconsistent solution in the experiments and apply prox-term regularization. FedProx utilizes the bounded local updates by penalizing parameters to provide good guarantee of consistency. In Liang et al. (2019) they introduce the local gradient tracking to reduce the local inconsistency in the local SGD method. Charles & Konečný (202T): Malinovskiy al. (2020) show that the local learning rate decay can balance the trade-off between the convergence rate and the local inconsistency with the rate of ( - 1)). Furthermore, Wang al. (2021 2020b) through simple counterexample to show that using adaptive optimizer or different hyper- parameters on local clients leads to an additional gaps. They propose a local correction technique to alleviate the biases. Wang et al. (2020a); y (Tan et al..
(2022) consider the different local settings and prove that in the case of asynchronous aggregation, the inconsistency bias will no longer be eliminated by local learning rate decay. [Haddadpour al. (202T) compress the local offset and adopt global correction to reduce the biases. Zhhng al. (202) apply
the primal dual method instead of the primal method to solve a series of sub-problems on the local clients and alternately updates the primal and dual variables which can achieve the fast convergence rate of ( with the local solution precision assumption. Based on FedPD, Durmus et al. (2021) propose FedDyn as a variants via averaging all the dual variables (the average quantity can then be viewed as the global gradient) under the partial participation settings, which can also achieve the same O ( under the assumption that exact local solution can be found by the local optimizer. Wang et al. (2022); Gong et al. (2022) propose two other variants to apply different dual variable aggregation strategies under partial participation settings. These methods benefit from applying the prox-term Li et al. (2019): Chen & Chao 2020) or higher efficient optimization methods Bischoff ct al. (2021) Yang et al. (2022) to control the local consistency.
Client-drifts. Karimireddy et al. (2020) firstly demonstrate the client-drifts for federated learning framework to indicate the negative impact on the global model when each local client over-fits to the local heterogeneous dataset. They propose SCAFFOLD via variance reduction technique to mitigate this drifts. Yu et al. (201 and Wang et al. (2019) introduce the momentum instead of the gradient to the local and global update respectively to improve the generalization performance. To maintain the property of consistency, Xu et al. 22221) propose a novel client-level momentum term to improve the local training process. (Ozatura et al. 2021) incorporate the client-level momentum with local momentum to further control the biases. In recent Gao et al. (2022): Kim et al.] (2022), they propose drift correction term as a penalized loss on the original local objective functions with global gradient estimation. CCen et al. (2020) and CCen et al. (202T 2022) focus on the adaptive method to alleviate the biases and improve the efficiency.
Our proposed FedSpeed inherits the prox-term at local update to guarantee the local consistency during local training. Different from the previous works, we adopt an extra prox-correction term to reduce the bias during the local training introduced by the update direction towards the last global model parameters. This ensures that the local update could be corrected towards the global minima. Furthermore, we incorporate a gradient perturbation update to enhance the generalization performance of the local model, which merges a gradient ascent step.
METHODOLOGY
In this part, we will introduce the preliminaries and our proposed method. We will explain the implicit meaning for each variables and demonstrate the FedSpeed algorithm inference details.
Notations and preliminary. Let m be the number of total clients. We denote St as the set of active clients at round f. K is the number of local updates and T is the communication rounds. (+){, denotes variable (.) at k-th iteration of (-th round the i-th client. x is the model parameters. g is the stochastic gradient computed by the sampled data. is the weighted quasi gradient computed as defined in Algorithm| g is the prox-correetee correctoo term. We denote (..-) as the inner product for two
vectors and || is the Fuclidean norm of vector. Other symbols are detailed at their references.
As the most FL frameworks, we consider to minimize the following finite-sum non-convex problem:
F (x)
F (x).
= m i=1
3

---

Published as a conference paper at ICLR 2023
Algorithm FedSpeed Algorithm Framework
Input: model parameters x", total communication rounds T, local gradient controller g," 0, penalized
weight X.
Output: model parameters x². I: for 0, 1, 1
round t 3: for client i E S parallel do
select active clients-set
4: communicate x" to local client i and set x1.0
5: for k 0, 0, 2... K do
sample minibatch e do compute unbiased stochastic gradient g(,x,1 V V. update the extra step: X x + Pg.
7:
8:
9:
compute unbiased stochastic gradient: gi,,22 = V V. (i(,,,i..).
10:
compute quasi- gradient: gi,a = (1 Bin, + agi
11:
update the gradient descent step: x,, x mi(i,x -i- {xx,, -x)) end for
12:
13: g = g
*xx1,x - x')
14:
communicate X =x(,x Agi to the global server
end for
16: x
3 Eies: X!
17:
end for
where F:
(x Ej) is objective function in the client i, and & represents for the random data samples obeying the distribution D., is the total number of clients. In FL, D, may differ across the local clients, which may introduce the client drifts by the heterogeneous data.
3.1 FEDSPEED ALGORITHM
In this part, we will introduce our proposed method to alleviate the negative impact of the heteroge- neous data and reduces the communication rounds. We are inspired by the dynamic regularization Durmus et al. (2021) for the local updates to eliminate the client drifts when T approaches infinite.
Our proposed FeedSpeed shown Algorithm At the beginning of each round f, subset of clients St are required to participate in the current training process. The global server will communicate the parameters x² the active clients for local training. Each active local client performs three stages: (I) computing the unbiased stochastic gradient g F if,,, with randomly sampled mini-batch data ef and executing gradient ascent step in the neighbourhood to approach X,; (2) computing the unbiased stochastic gradient gÂ,,,2 with the same sampled mini- batch data in (1) at the x and merging the gi,.1 with gi, to introduce a basic perturbation to the vanilla descent direction; (3) executing the gradient descent step with the merged quasi-gradien g the prox-term ||x|,x x" 1|2 and the local prox-correction term g!-! After K iterations local training, prox- prox-correction term f! will be updated as the weighted sum of the current local offset (xf,xx x(,o) and the historical offsets momentum. Then communicate the amended model parameters x x Age to the global server for aggregation. On the global server, a simple average aggregation is applied to generate the current global model parameters ++1 +1 at round t.
Prox-correction term. In the general optimization, the prox-term | 12 is penalized term for solving the non-smooth problems and it contributes to strengthen the local consistency in the FL framework by introducing a penalized direction the local updates as proposed in (Shu et al. (2018). However, as discussed in Hanzely & Richtárik (2020), it simply performs balance between the local and global solutions, and there still exists the non-vanishing vanishing inconsistent biases among the local solutions, i.e., the local solutions still largely deviated from each other, implying that local inconsistency is still not eliminated, which limits the efficiency of the federated learning framework.
To further strengthen the local consistency, utilize prox-correction term g which could be considered as a previous local offset momentum. According to the local update, we combine the <f term in the prox term and the local state, setting the weight (1 T multiplied to the basic
4

---

Published as a conference paper at ICLR 2023
local state. As shown in the local update in Algorithm
(Line. for x E R we have:
x x² -7
7h ? bi + 7
(2)
where =k= 7k -K-1 X x) )) |K-1- Proof details can be referred to the Appendix.
2 indicates that the local offset will be transferred to a exponential average of previous local gradients when applying the prox-term, and the updated formation of the local off'set is independent of the local learning rate This is different from the vamilla SGD-based methods, e.g. FedAvg, which treats all local updates fairly. 7% changes the importance of the historical gradients. As K increases, previous updates will be weakened by exponential decay significantly for T7 < A. Thus, we apply the prox correcorntt term balance the local offset. According to the iterative formula for g (Line. 13 in Algorithm and the equation (2) we can rewrite this update as:
Firstly let 8, O, Equation
g (1 7)
where y and "/k is defined the same in Equation Proof details can be referred to the Appendix.
Note that o performs as a momentum term of the historical local updates before round t, which be considered as estimation of the local offset round 1. At each local iteration & of round t, provides a correction for the local update to balance the impact of the prox-term to enhance the contribution of those descent steps executed firstly at each local stages, It should be noted that g different from the global momentum term mentioned in Wang al. (2019) which aggregates the average local updates to improve the generalization performance. Atter the local training, it updates the current information. Then we subtract the current g from the local models x counteract the influence in the local stages. Finally it sends the post-processed parameters x to the global server.
Gradient perturbation. Gradient perturbations (Foret et al. 2020a Mi et al. Zhao et al. 2022 Zhong et al. (022) significantly improves generalization for deep models. An extra gradient ascent the neighbourhood can effectively express the curvature near the current parameters. Referring to the analysis in Zhao et al. (2022). we show that the quasi-gradient g. which merges the extra ascent step gradient and the vanilla gradient, could be approximated as penalizing a square term of the L2-norm of the gradient on the original function. On each local client to solve the stationary point of (F,()) + B1| Fx) } can search for flat minima. Flatten loss landscapes will further mitigate the local inconsistency due to the averaging aggregation the global server heterogeneous dataset. Detailed discussions can be referred to the Appendix.
4 CONVERGENCE ANALYSIS
In this part we will demonstrate the theoretical analysis of our proposed FedSpeed and illustrate the convergence guarantees under the specific hyperparameters. Due the space limitations, more details could be referred to the Appendix. Some standard assumptions are stated as follows.
Assumption 4.1 (L-Smoothness)) For the non-convex function F; holds the property of smoothness for all [ml, i.e. [x) Fy(ly)l s L|[x brlx--y,,, for all x. E RRd.
Assumption 4.2 (Bounded Stochastic Gradient) The stochastic gradient gi, VFF e.,)) with the randomly sampled data Ei on the local client is an unbiased estimator of V with bounded variance, i.e., Elg; (.(()) and El]gg, VF((x( of, all x k. Rd.
Assumption 4.3 (Bounded Heterogeneity) The dissimilarity of the dataset among the local clients is bounded by the local and global gradients, i.e., ([ - Fx)))] < oz. for all x E Rd.
Assumption 4.1
guarantees Lipschitz continuity and Assumption 4.2 guarantees the stochastic
gradient is bounded by zero mean and constant variance. Assumption 4.3 is the heterogeneity bound for the non-iid dataset, which is widely used in many previous works (Reddi al. 2020 Yang et al.
5

---

Published as a conference paper at ICLR 2023
2021 Xu et al. 2021| Wang et al. 2021; Karimi al. 2021D. Our theoretical analysis depends on the above assumptions to explore the comprehensive properties in the local training process.
we introduce two m Σie(m) x,,K as the mean averaged parameters of the last iterations in the local training among the local clients. Based on {u'), we introduce the auxiliary sequences {z' =u= u² + 1-2 (u' u'=1)]=00- Combining the local update and the Equation 3
Proof sketch. To express the essential insights in the updates of the Algorithm D auxiliary sequences. Considering the u'
[+1
Σ
Σ
Yke (7gi,A + (1 - -)
(4)
m
kE[m]
A=
If we introduce K virtual states uf,,. it could be considered correction term g.- with the coefficient yy And the prox-correction term g: = - (uf, uf.)). which implies the global update direction in the local training process. And z' updates as:
momentum-basee update of the prox-
Σ
7kk
(5)
m
ic(m]
R=0
Detailed proofs can be referred in the Appendix. After mapping x' to u', the local update could be considered as a client momentum- like method with a normalized weight parameterized by yv- Further, after mapping u' to z', the entire update process will be simplified to SGD-type method with the quasi-gradients g. z' contains the penalized prox-term in the total local training stage. Though a prox-correction term is applied to eliminate the local biases, x' maintains to be beneficial from the update of penalizing the prox-term. The prox-correes prox-correction term plays the role as exponential average of the global offset. Then introduce our proof of the convergence rate for the FedSpeed algorithm:
Theorem 4.4 Under the Assumptions 4.1 4.3 when the perturbation learning rale satisfies p S VeaL' and the local learning rate satisfies m S min 32v3KL 2X}. and the local interval satisfies
K 2 X/m, let k. = 3a L2p2 1536n L K a positive constant with selecting the proper m and p. the auxiliary sequence z' in Equation (5) generated by executing the Algorithm satisfies:
T EI/FF()))1 ((F(z))-FT) F*) 64mL2K
32X²
Er
8 g + +
ART
KMiT
m
<E(m)
[E(m]
(6)
where F is a non-convex objective function F* is the optimal of F. The term t is:
T K
L2 + of) Xa L2 (303 + of))
(7)
where or is the perturbation weight. More proof details can be referred to the Appendix.
Corollary 4.5 Let p = O1/VT) 0(1//T) with the upper bound of p S 1/V/bal, and let mp = (1/K)
with the lower bound of m 2 X/K, when the local interval K is long enough with K = OT), the proposed FedSpeed achieves a fast convergence rate of (1/TT)
Remark 4.6 Compared with the other prox-baseds works, e.g. for Durmus et al. 2021 Wang et al. 2022: Gong et al. 2022), their proofs rely on the harsh assumption that local client must approach an exact stationary point or c-inexact stationary point in the local training per round. It cannot be strictly satisfied in the practical federated learning framework with the current theoretical analysis of the last iteration point on the non-convex case. We relax this assumption through enlarging the local interval and prove that federated prox-based methods can also achieve the convergence of (1/TT)
Remark 4.7 Compared with the other current methods, FedSpeed can improve the convergence rate by increasing the local interval K, which a good property for the practical federated learning framework. For the analysis of FedAvg (Yang el al. [202]). under the same assumplions, it achieves O(1/ AA/VSKT++ + K/T) which restricts the value of K to not exceed the order T. Karimireddy et al. (2020) contribute the convergence O(1/VSKT) under the constant local interval, and (Reddi let al. 2020) proves the same convergence under the strict coordinated bounded variance assumption for the global full gradient in the FedAdam. Our experiments also verify this characteristic in Section [.3 Most current algorithms are affected by increasing K in the training while FedSpeed shows the good stability under the enlarged local intervals and shrunk communication rounds.

---

Published as a conference paper at ICLR 2023
Feshro
fudlig
Fedhig
heack
1200
Feach
FudOyn
Tedpyn
Fed
1OLD
SCATFOLD
1M0 20n Rounds
Communication
10m 100
Communicatinn Rounds
Communicarion sin cide
(a) 10% participation of 100 clients CIFAR-10. (b) 2% participation of 500 clients CIFAR- 10.
Festhos
Fecheee
Feefree
ACC
TedCM
FreE
422 T00
FeeSbr
SCAP"OLD
Communication
Commuricatin
(c) 2% participation of 500 clients on CIFAR-
(d) 2% participation of 500 clients on Tinylmagenet.
Figure I: The top-1 accuracy in communication rounds of all compared methods CIFAR- and TinyImagenet Communication rounds are set as 1500 for CIFAR- 10/100, 3000 for Tinylnagenet. In each group, the left shows the performance on IID dataset while the right shows the performance on the non-IID dataset, which are split by setting heterogeneity weight of the Dirichlet as 0.6.
5 EXPERIMENTS
In this part, we firstly introduce our experimental setups. We present the convergence and generaliza- tion performance in Section 5.2 and study ablation experiments in Section 5.3
5.1 SETUP
Dataset and backbones. We test the experiments on CIFAR-10. 10, CIFAR- 100 Krizhevsky et al. (2009) and Tinylmagenet. Due to the space limitations we introduce these datasets the Appendix. We follow the Hsu et al. (2019) to introduce the heterogeneity via splitting the total dataset by sampling the label ratios from the Dirichlet distribution. We train and test the performance on the standard ResNet-18 18 He et al. (2016) backbone with the 7x7 filter size in the first convolution layer with
BN-layers replaced by GN GN/Wu & He (2018); Hsich et al. (2020) to avoid the invalid aggregation.
Implementation details. We select each hyper-parameters within the appropriate range and present the combinations under the best performance. To fairly compare these baseline methods, we fix the most ppper-parameters for all methods under the same setting. For the 10% participation of total 100 clients training, we set the local learning rate as 0.1 initially and set the global learning rate as 1.0 for all methods except for FedAdam which applies 0.1 on global server. The learning rate decay is set as multiplying 0.998 per communication round except for FedDyn, FedADMM and FedSpeed which apply 0.9995. Each active local client trains 5 epochs with batchsize 50. Weight decay is set le-3 for all methods. The weight for the prox-term in FedProx, FedDyn, FedADMM and FedSpeed is as 0.1. For the 2% participation, the learning rate decay is adjusted 0.9998 for FedDyn and FedSpeed. Each active client trains 2 epochs with batchsize 20. The weight for the prox-term is set as 0.001. The other
specific to each method will be introduced in the Appendix.
Baselines. We compare several classical and efficient methods with the proposed FedSpeed in our experiments, which focus on the local consistency and client-drifts, including FedAvg McMahan et al. 2017), FedAAam Reddi et al. (2020), SCAFFOLD Karimireddy et al. (220)). FedCM et al. (2021 1). FedProx Sahu et al. (2018), FedDyn Durmus et al. (2021) and FedADMM Wang et al. (2022). FedAdam applies adaptive optimizer to improve the performance on the global updates. SCAFFOLD and FedCM utilize the global gradient estimation to correct the local updates. FedProx introduces the prox-term to alleviate the local inconsistency. FedDyn and FedADMM both employ the different variants of the primal-dur method to reduce the local inconsistency. Due to the limited space, more detailed description and diseussions on these compared baselines are placed in the Appendix.
7

---

Published as a conference paper at ICLR 2023
Table I: Test accuracy (%) on the CIFAR-10/100 and Tinylmagenet under the 2% participation of 500 clients with IID and non-IlD dataset. The heterogeneity is applied as Dirichlet-0.6 (DIR.).
CIFAR-10
CIFAR-100 100
Tinylmagenet
Method
IID.
DIR.
IID.
DIR.
IID.
DIR.
FedAvg
77.01
75.21
40.68
39.33
33.58
32.71
FedProx
77.68
75.97
41.29
39.69
33.71
32.78
FedAdam
82.92
80.55
51.65
49.29
40.85
39.71
SCAFFOLD
80.11
77.71
47.38
46.33
38.03
37.54
FedCM
84.20
83.48
52.35
50.98
41.90
41.67
FedDyn
83.36
80.57
46.18
46.60
34.69
33.92
FedADMM
81.29
79.71
45.51
46.65
36.03
33.83
FedSpeed
85.80
84.79
53.93
52.88
43.38
42.75
5.2 EXPERIMENTS
CIFAR-I0. Our proposed FedSpeed is robust to different participation cases. Figure (a) shows the results of 10% participation of total 100 clients. For the IID splits, FedSpeed achieves 6.1 ahead of FedAvg as 88.5%. FedDyn suffers the instability when learning rate is small, which is the similar phenomenon as mentioned in Xu et al. (202I). When introducing the heterogeneity, FedAdam suffers from the increasing variance obviously with the accuracy dropping from 85.7% 83.2% Figure (b) shows the impact from reducing the participation. FedAdam is lightly affected by this change while the performance degradation of SCAFFOLD is significant which drops from 85.3% to 80.1%.
CIFAR-100 Finylmagenet. As shown in Figure (c) and (d), the performance of FedSpeed on the CIFAR- 100 and I'nylmagenet with low participating setting performs robustly and achieves approximately 1.6% and 1.8% improvement ahead of the FedCM respectively. As the participation is low, the impact from the heterogeneous data becomes weak gradually with a similar test accuracy. SCAFFOLD is still greatly affected by low participation ratio, which drops about 3.3% lower than FedAdam. FedCM converges fast the beginning of the training stage due the benefits from strong consistency limitations. FedSpeed adopts to update the prox-correction term and converges faster with its estimation within several rounds and then FedSpeed outperforms other methods.
Table 1 shows the accuracy under the low participation ratio equals to 2%. Our proposed FedSpeed outperforms on each dataset on both IID and non-Ill) settings. Table T shows the accuracy under the low participation ratio equals to 2%. Our proposed FedSpeed outperforms IID and non-IID settings. We observe the similar results as mentioned in Reddi et al. (2020 Xu et al. ()021). FedAdam and FedCM could maintain the low consistency in the local training stage with robust results to achieve better performance than others. While FedDyn is affected greatly by the number of training samples in the dataset, which is sensitive to the partial participation ratios.
each dataset on both
Large local interval for the prox-term. From the IID case to the non-IID case, the heterogencous dataset introduces the local inconsistency and leads the severe client-drifts problem. Almost all the baselines suffer from the performance degradation. High local consistency usually supports for a large interval for their bounded updates and limited offsets. Applying prox-term guarantees the local consistency, but it also has an negative impact on the local training towards the target of weighted local optimal and global server model. FedDyn and FedADMM succeed to apply the primal-dual method to alleviate this influence as they change the local objective function whose target is reformed by dual variable. These method can mitigate the local offsets caused by the prox-term -term and they improve about 3% ahead of the FedProx on CIFAR-10. However, the primal-dual method requires local e-close solution. In the non-convex optimization it is difficult to determine the selection of local training interval K under this requirement. Though Durmus al. (2021) claim that 5 local epochs are approximately enough for the e-close solution, there is still an unpredictable local biases.
FedSpeed directly applies prox-correction term to update K epochs and avoids the requirement for the precision of local solution. This ensures that the local optimization stage does not introduce the bias due to the eπrог of the inexact solution. Moreover, the extra ascent step can efficiently improve the performance of local model parameters. Thus, the proposed FedSpeed can improve 3% than FedDyy and FedADMM and achieve the comparable performance as training the IID dataset.
8

---

Published as a conference paper at ICLR 2023
100
Epochs
200
Epochs
1.0
200
204
200
200
(a) FedAdam.
(b) FedCM.
SCAFFOLD.
(d) FedSpeed.
Figure 2: Performance of FedAdam, FedCM, SCAFFOLD and FedSpeed with local epochs E 1, 2. 5, 10, 20 on the 10% participation case of total 100 clients on CIFAR-IO. We fix T x = 2500 as the equaled total training epochs to illustrate the performance of increasing E and decreasing T.
An interesting experimental phenomenon is that the performance of SCAFFOLD gradually degrades under the low participation ratio. It should be noticed that under the 10% participation case, SCAF- FOLD performs as well as the FedCM. It benefits from applying global gradient estimation to correct the local updates, which weaken the client-drifts by quasi gradient towards to the global optimal. Actually the estimation variance related to the participation ratio, which means that their efficiencies rely on the enough number of clients. When the participation ratio decreases be extremely low, their performance will also be greatly affected by the huge biases in the local training.
5.3 HYPERPARAMETER SENSITIVITY
Local interval K. To explore the acceleration on T by applying a large interval K, we fix the total training epochs E. It should be noted that K represents for the iteration and E represents for the epoch. A larger local interval can be applied to accelerate the convergence in many previous works theoretically, e.g. for SCAFFOLD and FedAdam, while empirical studies are usually unsatisfactory. As shown in Figure 2 in the FedAdam and FedCM, when K increases from 1 to 20, the accuracy drops about 13.7% and 10.6% respectively. SCAFFOLD is affected lightly while its performance is much lower. In Figure 2 (d), FedSpeed applies the larger E to accelerate the communication rounds T both theoretical proofs and empirical results, which stabilizes swing within 3.8% lightly.
Learning rate for gradient perturbation. In the simple analysis, p can be selected proper value which has no impact on the convergence complexity. By noticing that if / 0, p could be selected irrelevant to 1/. To achieve a better
Table 2: Performance of different Po with a
0
0.01
0.05
0.1
0.2
Acc.
83.97
84.6
85.38
85.72
84.35
performance, we apply the ascent learning rate p po/ V Fill in the experiments, where Pe is constant value selected from the Table 2 p is consistent with the sharpness aware minimization Foret jet al. (2020b) which can search for a local minimal. Table shows the performance of utilizing the different Po CIFAR-10 by 500 communication rounds under the 10% participation of total 100 clients setting. Due to the space limitations more details could be referred to the Appendix.
CONCLUSION
In this paper, we propose a novel and practical federated method FedSpeed which applies a prox- correction term to neutralize the bias due to prox-term in each local training stage and utilizes perturbation gradient weighted by an extra gradient ascent step to improve the local generalization performance. We provide the theoretical analysis to guarantee its convergence and prove that FedSpeed benefits from a larger local interval to achieve a fast convergence rate of (1/TT) without any other harsh assumptions. We also conduct extensive experiments to highlight the significant improvement and efficiency of our proposed FedSpeed, which is consistent with the properties of our analysis. This work inspires the FL framework design to focus on the local consistency and local higher generalization performance to implement the high-efficient method to federated learning.

---

Published as a conference paper at ICLR 2023
REFERENCES
Maksym Andriushchenko and Nicolas Flammarion. Towards understanding sharpness-aware mini- mization. In International Conference on Machine Learning, pp. 639-668. PMLR, 2022.
Muhammad Asad, Ahmed Moustafa, and Takayuki Ito. Fedopt: Towards communication efficiency and privacy preservation in federated learning. Applied Sciences, 10(8):2864, 2020.
Sebastian Bischoff, Stephan Günnemann, Martin Jaggi, and Sebastian U Stich. On second-order optimization methods for federated learning. arXiv preprint arXiv:2/09.023388 2021.
Debora Caldarola, Barbara Caputo, and Marco Ciccone. Improving generalization in federated learning by seeking flat minima. In Computer Vision-ECCH 2022: 17th European Conference, Tel Aviy, Israel October 23-27, 2022, Proceedings, Part XXIII, pp- 654-672. Springer, 2022.
Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs in federated learning and meta-lcarning. In International Conference on Artificial Intelligence and Statistics, pp. 2575-2583
PMLR, 2021.
Congliang Chen, Shen, Haozhi Huang, and Wei Liu. Quantized adam with error feedback. ACM Transactions Intelligent Systems and Technology (TIST), 12(5):1-26, 2021.
Congliang Chen, Li Shen, Wei Liu, and Zhi-Quan Luo. Efficient-adam: Communication-efficieee distributed adam with complexity analysis. arXiv preprint arXiv:2205. 14473, 2022.
Hong- You Chen and Wei-Lun Chao. Fedbe: Making bayesian model ensemble applicable federated learning, arXiv preprint wwXiv:2009.01974, 2020.
Hou
Xiangyi Chen, Xiaoyun Li, and Ping Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, pp. 119-128, 2020.
Alp Emre Durmus, Zhao Yue, Matas Ramon, Mattina Matthew, Whatmough Paul, and Saligrama Venkatesh. Federated learning based dynamic regularization. In International Conference on Learning Representations, 2021.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412 2020a.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020b.
Liang Gao, Huazhu Fu, Li Li, Yingwen Chen, Ming Xu, and Cheng-Zhong Xu. Fedde: Fed- erated learning with non-iid data via local drift decoupling and correction. arXiv preprint 11211:2203.11751, 2022.
Yonghai Gong, Yichuan Li, and Nikolaos M Freris. Fedadmm: robust federated deep learning framework with adaptivity to system heterogeneity. arXiv preprint arXiv:2204.005229 2022.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 2350-2358, PMLR. 2021.
Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. arXiv preprint arXiv:2002.05512 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and patlern recognition, pp. 770-778, 2016.
Kevin Hsich, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In International Conference on Machine Learning, pp. 4387-4398. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2023
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non- con-identical data distribution for federated visual classification. arXiv preprint FrXiv:1909.063320 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Belhal Karimi, Xiaoyun Li, and Ping Li. Fed-lamb: Layerwise and dimensionwise locally adaptive optimization algorithm. CoRR, abs/21 10.00532. 2021.
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. PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd heteroge- neous data. arXiv preprint arXiv:1909.0477 2019.
Geeho Kim, Jinkyu Kim, and Bohyung Han. Communication-effiienn federated learning with acceleration of global momentum. arXiv preprint arXiv:2201.03177 2022.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:/610.05499 2016.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Li Yuxi Fan, Mike Tse, and Kuo- Yi Lin. A review of applications in federated learning. Computers & Industrial Engineering, 149:106854 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy. Feddane: A federated newton-type method. 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pp. 1227-1231. IEEE, 2019.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 60, 2020b.
Xianfeng Liang. Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv: 1912. 12844, 2019.
Ji Liu, Jizhou Huang, Yang Zhou, Xuhong Li, Shilei Ji, Haoyi Xiong, and Dejing Dou. From distributed machine learning to federated learning: A survey, Knowledge and Information Systems, pp. 1-33, 2022.
Yixing Liu, Yan Sun, Zhengtao Ding, Li Shen, Bo Liu, and Dacheng Tao. Enhance local consistency in federated learning: A multi-step inertial momentum approach. arXiv preprint arXhv:2302.05726.
2023.
Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learning, pp. 6692-6701. PMLR, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Areas. Communication efficient learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282, PMLR, 2017.
Peng Mi, Li Shen, Tianhe Ren, Yiyi Zhou, Xiaoshuai Sun, Rongrong Ji, and Dacheng Tao. Make sharpness-award minimization stronger: A sparsified perturbation approach. In Advances in Neural Information Processing Systems.
Emre Ozfatura, Kerem Ozfatura, and Deniz Gündüz. Fedade: Accelerated federated learning with drift control. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 467-472. IEEE, 2021.
11

---

Published as a conference paper at ICLR 2023
Zhe Qu, Xingyu Li, Rui Duan, Yao Liu, Bo Tang, and Zhuo Lu. Generalized federated learning via sharpness aware minimization. In International Conference on Machine Learning, pp. 18250- 18280. PMLR, 2022.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint 2XXi:20033.00255 2020.
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogeneous networks. arXiv preprint arXiv:1812.06127, 3:3, 2018.
Yifan Shi, Li Shen, Kang Wei, Yan Sun, Bo Yuan, Xueqian Wang, and Dacheng Tao. Improving the model consistency of decentralized federated learning. arXiv preprint urXiv:2302.04083 2023.
Yue Tan, Guodong Long, Lu Liu, Tianyi Zhou, Qinghua Lu, Jing Jiang, and Chengqi Zhang. Fedproto: Federated prototype learning across heterogeneous clients. In AAAI Conference on Artificial Intelligence, volume 1, 2022.
Dirk van der Hoeven. Exploiting the surrogate gap online multiclass classification. Advances in Neural Information Processing Systems, 33:9562-9572. 2020.
Han Wang, Siddartha Marella, and James Anderson. Fedadmm: A federated primal-dual algorithm allowing partial participation. arXiv preprint arXiv:2203 2022.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving
communication-effiiee distributed sgd with slow momentum. arXiv preprint arXiv:1910.0060 2019.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:761 1-7623, 2020a.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 13:7611-7622 2020b.
Jiany Wang, Zheng Xu, Zachary Garrett, Zachary Charles, Luyang Liu, and Gauri Joshi. Local adaptivity in federated learning: Convergence and consistency. arXiv preprint arXiv:2106.02305. 2021.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pp. 3-19, 2018.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2106.1088 2021.
Haibo Yang. Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11200 2021.
Peng Yang. Yuning Jiang, Ting Wang, Yong Zhou, Yuanming Shi, and Colin N Jones. Over-the-air federated learning via second-order optimization. arXiv preprint arXiv:2203. 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-207, 2019.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pp. 7184-7193. PMLR, 2019.
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with adaptivity to non-iid data. IEEE Transactions on Signal Processing, 69:6055-6070)
2021.
12

---

Published as a conference paper at ICLR 2023
Yang Zhao, Hao Zhang, and Xiuyuan Hu. Penalizing gradient norm for efficiently improving generalization in deep learning. arXiv preprint arXiv:220..03599 2022.
Qihuang Zhong, Liang Ding, Li Shen, Peng Mi, Juhua Liu, Bo Du, and Dacheng Tao. Improving sharpness-aware minimization with fisher mask for better generalization on language models. arXiv preprint arXiv:2210.05497 2022.
13

---

Published as a conference paper at ICLR 2023
In this part, will introduce the gradient perturbation, the proofs of the major equations and the theorem, and some extra experiments. Section we provide a explanation for understanding the gradient perturbation step in proposed FedSpeed. In Section C we provide the full proofs of the major equation in the text, some main lemmas and the theorem. In Section B we provide the details of the implementation of the experiments including the setups, dataset, hyper-parameters and some extra experiments.
A
GRADIENT PERTURBATION
A.1 UNDERSTANDING OF GRADIENT PERTURBATION
We propose the gradient perturbation in the local training stage instead of the traditional stochastic gradient, which merges an extra gradient ascent step to the vanilla gradient by a hyper-parameter a. While its ascent step usually approximates the worst point in the neighbourhood. This has been studied in many previous works, e.g. for the form of extra gradient and the sharpness aware minimization. our studies, we perform the extra gradient ascent step instead of the descent step in extra gradient method. It also could be considered as a variant of the sharpness aware minimization method via weighted averaging the ascent step gradient and the vanilla gradient, instead of the normalized gradient. Here we illustrate the implicit of this quasi-gradient g in our proposed FedSpeed and explain the positive efficiency for the local training from the perspective of objective functions.
Firstly we consider to minimize the non-convex problem (x). To approach the stationary point of Cp. we can simply introduce a penalized gradient term as a extra loss in Ep. which is to solve the problem minx (x) å (x) + | (x) The final optimization target is consistent with the vanilla target, while penalizing gradient term can approach flatten minimal empirically, We compute the gradient form as follows:
VL(x) VCx)) 3 ( VZ, -V-40)) Vxp(x)).
(8)
The update in Equation (8) contains second-orde Hessian information, which involves a huge amount of parameters for calculation. To further simplify the updates, consider an approximation for the gradient form. We expand the function Lp via Taylor expansion as:
Cx A) Cx(x) (x)( 1 (x)A+,
where RA = ((1A113) is the infinitesimal to || which is directly omitted in our approximation.
Thus have the gradient form A as:
Vx & (x) (x)A
RA is relevant A. We set the = PVL, (x) and then we have:
V'L,(x)VL, (x) VV (VG, -Vc,xx))))))
(9)
Thus we connect Equation g and Equation we have:
VL(x)
VL, 3V L,) (x,(x)
(x) - VVL, (VC,(x)) vxx(x))
3
= (1 8 VC, 8 VC, +VVC,(x))
(L (x
Here we can see that the balance weight a our proposed method is actually the ratio of the gradient penalized weight 3 and the gradient ascent step size p. To fix the step size p. increasing
14

---

Published as a conference paper at ICLR 2023
means increasing the gradient penalized weight 8, which facilitates searching for flatten stationary point to improve the generalization performance. While the second term of V ((x) can not be directly computed for its nested form, upproximate the second term with the chain rule as follows:
VLp(x DVL
( (4
Finally we have:
vx(x)= = (1-a) - (V)
(10)
The Equation (TO) provides an understanding for the weighted quasi gradient g the local training
stage in our proposed FedSpeed. We select an appropriate 0 S 3 S to satisfy the update of perturbation gradient. It executes gradient ascent step firstly with the step size p X. Then generates the stochastic gradient by the same sampled mini-batch data as the ascent step at X. The quasi-gradient is merged as Equation (T)) to execute the gradient descent step.
This is just simple approximation for the gradient perturbation to help for understanding the implicit of the quasi-gradient and its performance in the training stage. Actually the error of the approximation depends lot on p. The smaller the higher the accuracy of this estimation, but the smaller the less efficient the optimizer performs. Similar understanding can be referred the (Qu et al. 2022 Caldarola et al. 2022, Andriushchenko & Flammarion 2022).
B EXPERIMENTS
B. SETUPS
Table 3: Dataset introductions.
Dataset
Training Data
Test Data
Class
Size
CIFAR-10
50,000
10,000
10
3x32x32
CIFAR-100
50,000
10,000
100
3x32x32
Tinylmagenet 100,000
10,000
200
3x64x64
Dataset and Backbones. Extensive experiments are tested CIFAR-110100 dataset. We test on the two different settings as 10% participation of total 100 clients and 2% participation of total 500 clients. CIFAR-10 dataset contains 50,000 training data and 10,000 test data in 10 classes. Each data sample is a 3x32x32 color image. CIFAR- Krizhevsky et al. (2099) includes 50,000 training data and 10,000 test data in 100 classes 500 training samples per class. TinyImagenet involves 100,000 training images and 10,000 test images in 200 classes for 3x 64 x64 color images, as shown in Table 3 To fairly compare with the other baselines, we train and test the performance on the standard ResNet-188 18 He et al. (2016) backbone with the x filter size in the first convolution layer as implemented in the previous works, e.g. for Karimireddy al. (2020); Durmus et al. (202T): Xu et al. (202T). We follow the Hsieh et al. (2020) to replace the batch normalization layer with group normalization Wu & (2018), which can be aggregated directly by averaging. These are all common setups in many previous works.
Dataset Partitions. To fairly compare with the other baselines, we follow the Hsu al. (2019) to introduce the heterogeneity via splitting the total dataset by sampling the label ratios from the Dirichlet distribution. An additional parameter used control the level of the heterogeneity of the entire data partition. In order to visualize the distribution of heterogeneous data, make the heat maps the label distribution different dataset, as shown Figure Since the heat map of 500 clients cannot be displayed normally, we show 100 clients case. It could be seen that for heterogeneity weight equals to 0.6, about 10% to 20% of the categories dominate on each client, which is white block in the Figure 3 The IID dataset is totally averaged in each client.
Data Argumentation. For CIFAR-10/100, we follow the implementation in the Karimireddy et al. (2020); Durmus et al. (2021) to normalize the pixel value within specific mean and std value in our code. which are (0.491, 0.482, 0.447] for mean, [0.247, 0.243, 0.262] for std and [0.5071. 0.4867, 0.4408] for mean, [0.2675, 0.2565, 0.2761] for std. We randomly flip the training samples and randomly crop the images enlarged with the padding equal to 4. For Tinylmagenet, the same argumentation is applied except for the padding equal to 8.
15

---

Published as a conference paper at ICLR 2023
Heterogeneity Distribution in CIFAR-10
Heterogeneity Distribution in CIFAR-100
0-
10
Classes
40
120
16
32
80
10
20
30
40
50
60
70
80
90
10
20
30
40
50
60
70
80
30
Clients
Clients
(a) CIFAR-10.
(b) CIFAR-100.
Figure 3: Heat maps for different dataset under heterogeneity weight equals to 0.6 for Dirichlet distribution.
Baselines. FedAvg McMahan al. (2077 is proposed the basic framework in the federated learning. And FedOpt improves it as a two-stage optimizer with a local and global optimizer update alternatively. Yang et (2021) proves specific 77 (not the average weight) can achieve faster convergence moon-dominant term). FedAdam Reddi et al. (2020) utilizes a adaptive optimizer on global server and SGD optimizer on the clients, which average the averaged local gradients as quasi-gradient for global server to implement the adaptive update. SCAFFOLD Karimireddy et al. (2020) applics the variance reduction technique i.c. SVRG, to approximate the global gradient as the averaged local gradients and transfer extra variable the client per round. This implementation can accelerate the convergence rate of the non-dominant term theoretically and achieve a high performance empirically. FedCM Xu et al., (2021) proposes client-level momentum to merge the global update as a momentum buffer to the local updates, which extremely reduces the local consistency. Though introduces unpredictable biases into the local updates, achieves the SOTA performance ahead of other methods. FedProx (ahu et al. (2018) implements the prox-point optimizer into the FL framework on local updates with regularization prox-term regularizer. It limits the local updates towards the initial point at the start of each local stage. Many previous works have analyzed its advantages and weaknesses. DDrmuu al. (202T): Wang al. (2022); Gong al.) (2022) use different variants of primal-dual method into FL. and achieve nice satisfactory in the FL framework. It does not need heterogeneity bounded assumption theoretically, which requires high local convergence guarantees. Our proposed FedSpeed achieve the same convergence rate without assuming the local exact solution and we provide the local interval bound to achieve this faster convergence. Both theoretical analysis and empirical results verifies the performance of our proposed FedSpeed.
B.2 EXPERIMENTS
B.3 AYER-PARAMETERS
Sapeee-prraeeers Selections. We fix the local learning rate as 0.1 and global learning rate as 1.0 for average, except for the FedAdam which is applied 0.1. The penalized weight of prox-term in FedProx, FedDyn, FedADMM and FedSpeed is selected from the [0.001, 0.01, 0.1, 0.5]. The learning rate decay is fixed as 0.998 expect for the FedDyn, FedADMM and FedSpeed is selected from [0.998, 0.999, 0.9995, 0.99995]. The perturbation weight is selected from [0, 0.5. 0.75, 0.875, 0.9375, 1]. The batchsize is selected from [20, 50]. The local interval is selected from [1, 2, 5, 10, 20]. For the specific parameters in FedAdam, the momentum weight is set 0.1 and the second order momentum weight set as 0.01. The minimal value is set as 0.001 to prevent the calculation of dividing by O. The levent-level momentum weight of FedCM set 0.1.
16

---

Published as a conference paper at ICLR 2023
Table 4: Communication rounds required achieve the target accuracy. On CIFAR-10/ 10/100 trains 1,500 rounds and on Tinylmagenet it trains 3,000 rounds. "_" means the test accuracy can not achieve the target accuracy within the fixed training rounds. DIR represents for the Dirichlet distribution with the heterogeneity weight equal to 0.6. Local interval K' is set as 5 on CIFAR-10 10 (100-10%) and on others. Other hyper-paraman paprr-parameters are introduced above.
Dataset
CIFAR-10 (100-10%)
CIFAR-10 (500-2%)
Heterogeneity
IID.
DIR.
IID.
DIR.
Target Acc. (%)
80.0
85.0
80.0
85.0
75.0
82.5
75.0
82.5
FedAvg
344
472
772
1357
FedProx
338
465
720
1151
FedAdam
324
1343
689
613
1476
878
SCAFFOLD
207
654
272
628
967
FedCM
109
620
192
1092
325
1160
449
1399
FedDyn
121
400
166
547
673
FedADMM
169
917
174
756
505
1440
687
FedSpeed
136
280
169
380
495
926
662
1148
Dataset
CIFAR- 100 (500-2%)
TinyImagenet (500-2%)
Heterogeneity
IID.
DIR.
IID.
DIR.
Target Acc.
40.0
50.0
40.0
50.0
33.0
40.0
33.0
40.0
FedAvg
1013
1615
FedProx
957
1588
FedAdam
614
1277
847
1151
2495
1584
SCAFFOLD 720
784
949
1187
FedCM
505
1150
526
1336
661
1360
817
1843
FedDyn
661
703
1419
2559
FedADMM
687
715
921
2711
FedSpeed
522
973
541
1038
684
1373
962
1885
Here briefly introduce the selection of the hyperparameters in FedSpeed.
(1) Vi is the learning rate which is a basic hyperparameters in the deep learning, and usually we do finetune this for the fair comparison in the experiments. We just select the same and common settings as the previous works mentioned.
(2) À the coefficient for the term, which is proposed in the FedProx and lot of prox-based federated methods adopt this hyperparameter widely both in personalized-Fi. and centralized-FI. The selection of this hyperparameter has been studied in many previous works which verify its efficiency. Usually the selection of À are in (10, 100} on the CIFAR-10/100 dataset, and we test it also works on the TinyImagenet.
(3) p is the ascent step learning rate. Like many extra gradient method, the selection of is usually related to the local learning rate 7) order not to unduly affect the performance the gradient descent, the learning rate for the extra gradient step p is usually not much larger than the learning rate for the gradient descent step 7, Obviously, if p is set very small, the updated state of the extra gradient steps will be very limited, which makes this operation have effect. Therefore, the selection
17

---

Published as a conference paper at ICLR 2023
of p usually matches that of 77- In our experiments, the 77 is set 0.1, which is common selection in the previous works. We test the selection of p in {0, 0.01, 0.05,0.1,0.... which represents for {"no extra gradient". "0.1m, "0.5%, "Im" "2n"" The best performing selection is p 1tp in CIFAR-10 (details in Section 5.3 paragraph "Learning rate for the gradient perturbation"), We also test this selection the CIFAR-100 and Tinylmagenet, and it also works well. We recommend that the selection of should be kept comparable to the learning rate
(4) or is the ratio for merging the gradient of the extra ascent step. In FedSpeed, the is in the range of [0, 1]. The same, if a is set very small, which means it does not merge the gradient of the ascent steps. In our experiments, we test the selection of in {0, 0.5, 0.75, 0.875, 0.9375, 1.0). The best performing selection is a 0.9375 in CIFAR-10 10. In fact a = 1 also works well (details in Section 5.3 paragraph "Perturbation weight a"). Thus, about a, we recommend that should be close to 1.0, e.g. for 0.9, 0.99, 1.0. This also verifies the improvements of the ascent steps.
B.3.1 BEST PERFORMING HYPER-PAR PARAMETERS.
For fair comparison, the learning rate is fixed for all the methods.
For CIFAR-10 dataset, select the batchsize as 50 for 100 clients and 20 for 500 clients. The total dataset 50,000 and there are 100 images under a single client it is set as 500 clients. Thus we decay it to 20 for 5 iterations per local epoch. The local epochs is Karimireddyy et al. 2020); Durmus et al. (202T); Xu et al. (202T) etc. and their performance is matching. We select the local interval K 5. The prox-term weight is selected as 0.1. The learning rate decay is selected as 0.9995 for prox-term based methods. We train the total dataset for 1,500 communication rounds.
5, the same the experiments
For CIFAR- 100 dataset, we select the 500 clients with 2% participation ratio in the experiments. we fine-tune little. The batchsize is selected as to avoid too little
Thus for each haper-paramesee iterations per local epoch. The local epochs is set as 2 for the final results comparison. The ablation study on local interval K indicates that our proposed FedSpeed outperforms significantly than other methods when K is large. Thus to compare the performance more clearly, we select the 2 as the local epochs. We decay the prox-term weight 0.01 for prox-term based methods. The learning rate decay selected as 0.99995 for prox-based methods. We train 1,500 rounds and then test the performance.
For TinyImagene dataset, the most selections are the same as for the CIFAR-100 dataset. The prox-term weight is selected as 0.1 and the learning rate decay is selected as 0.9995. Total 3,000 communication rounds are implemented in the training stage.
B.3.2 SPEED COMPARISON.
Table|[shows the communication rounds required achieve the target test accuracy. At the beginning of training, FedCM performs faster than others and usually achieve high accuracy finally. FedSpeed faster in the middle and late stages of training. We bold the data for the top-2 in each test and generally FedCM and FedSpeed significantly performs well on the training speed.
Figure shows the performance of different learning rate decay and prox-term weight for FedSpeed.
B.3.3
TIME COST
Table 5: Training wall-clock time comparison.
On
Times (s/Round)
Rounds
Total (s)
Cost Ratio
FedAvg
10.44
FedProx
11.33
FedAdam
14.74
1343
19795.8
4
SCAFFOLD
14.34
654
9378.3
2,03x
FedCM
13.22
622
8222.8
1.78x
FedDyn
14.11
400
5644.0
1.22x
FedSpeed
16.42
281
4614.0
18

---

Published as a conference paper at ICLR 2023
0.903
0.000
0,873
0.515
0.003
Test Top-1 Acc
0.023
0.802
Test
0.713
0.01
p= 0=001
p=0.05
0.1
p-0.1
0-
400
638
800
3000
2008
120:
3400
Communication Rounds
Communication Rounds
(a) Prox-term weight=0.5.
(b) Prox-term weight=0.1.
0.992
0.90
0.675
0.875
Acc
0.893
Test Top-1 Acc
0.850
0.023
0.025
0.803
0.775
0=01
0=0.11
0.753
0-0.0
0=
0.722
p=02
p=02
220
400
622
200
2000
1201
3400
200
402
500
802
2000
1250
:400
Communication Rounds
Communication Rounds
(c) Prox-term weight=0.01.
(d) Prox-term weight=0.001.
Figure 4: Performance of different ascent step size p under different prox-term weights of [0.001, 0.01, 0.5).
We test the time on the A100-SXMM440GB GPU and show the performance in the Table B.3.3 Experimental setups are the same the CIFAR-10 10% participation among total 100 clients on the DIR-0.6 dataset. The rounds in the table are the communication rounds required that the test accuracy achieves accuracy 85%. "h" means it can not achieve the target accuracy.
FedSpeed is slower due to the requirement of computing an extra gradient. So it gets slower in one single update, approximately 1.57 wall-clock time costs than FedAvg. But its convergence process is very fast. For the final convergence speed, FedSpeed still has a considerable advantage over other algorithms. The issue is possibly one of the improvements for FedSpeed in the future. For example, introduces single-cut call gradient method to save half the costs during backpropagation. We are also currently trying introduce new module save the cost.
B.3.4 DIFFERENT LETEROGENBITY.
Table 6: Comparison different heterogeneous dataset.
Or1
IID
Dir-0.6
Dir-0.3
Drops (i.i.d. Dir-0.6)
Drops (Dir-0.6 Dir-0.3)
FedAvg
77.01
75.21
71,96
1.80
3.25
FedAdam
82.92
80,55
76.87
2,37
3.68
SCAFFOLD
80.11
77.71
74.34
2,40
3.37
FedCM
84.20
83.48
81.02
0.72
2.46
FedDyn
83.36
80.57
77.33
2.79
3.24
FedSpeed 85.80
84.79
82.68
1.01
We test on the Dir-0.3 setups on CIFAR-10 10 and show the results as Table B.3.4 the other settings are the same the test in the text. The (i..d. Dir-0.6) is the difference between the IID dataset and the Dir-0.6 dataset and (Dir-0.6 > Dir-0.3) is the difference between the Dir-0.6 dataset and the DIR-0.3 dataset. FedSpeed outperform the others the Dir-0.3 setups whose heterogeneity is much
19

---

Published as a conference paper at ICLR 2023
Todlug
Fedidim
175
Fedtyy
SCAPFOLD
SD
K0
Commaniction
rounds
(a) CIFAR-10 LID.
(b) CIFAR- non-IID.
(c) FedCM.
(d) FedSpeed.
Figure 5: (a) and (b) show the loss curves on the CIFAR-IU IID/DIR-0. dataset. The FedSpeed achieves the best and stable performance in the training. (c) and (d) show the loss curve of FedCM
and FedSpeed on the CIFAR-10 DIR-0.6 dataset with increasing the local epochs from E 1 to 20.
stronger than Dir-0.6 6 setups. the heterogeneity becomes stronger, FedSpeed still maintain stable generalization performance. The correction term helps to correct the biases during the local training, while the gradient perturbation term helps resist the local over-fitting the heterogeneous dataset. FedSpeed can benefit from avoiding falling into the biased optima.
B.3.5
ABLATION STUDIES
Table 7: Ablation studies on different modules.
Prox-term Prox-correction term
Gradient perturbation
Accuracy (%)
81.92
82.24
83.94
83.88
85.70
From the practical training point of view, compared with the vanilla FedAvg, FedSpeed adds three main modules: (1) prox-term, (2) prox-coreection term, and (3) gradient perturbation. We test the performance of 500 communication rounds the different combination of the modules above on the CIFAR-10 10 with the settings of 10% participating ratio of total 100 clients. The Table shows their performance.
From the table above, proposed by the FedProx. But due to some issues we point out in our paper, this term has also negative impact the performance in FL.. When the prox-correction term is introduced in, it improves the performance from 82.24% to 83.94%. When the gradient perturbation is introduced in, improves the performance from 82.24% 83.88%. While FedSpeed applies them together and achieves a 3.46% improvement.
clearly see the performance of different modules. The prox-term is
Different performance of these modules:
As introduced in our paper, the prox-term simply performs as a balance between the local and global solutions, and there still exists the non-vanishing inconsistent biases among the local solutions, i.c.. the local solutions are still largely deviated from each other, implying that local inconsistency is still eliminated. Thus we utilize the prox-correction term to correct the inconsistent biases during the local training. About the function of gradient perturbation, we refer to theoretical explanation in the main text, and its proof is provided the supplementary material due to the space limitations. This perturbation is similar to utilize penalized gradient term to the objective function during local optimization process. The additional penalty will bring better properties to the local state, e.g. for flattened minimal and smoothness. For federated learning, the smoother the local minima is, the more flatness the model merged on the server will be. FedSpeed benefits from these two modules to improve the performance and achieves the SOTA results.
20

---

Published as a conference paper at ICLR 2023
B.3.6 LOss CURVE COMPARISON
According to the Figure 5 in (a) and (b) we can see the common FedAvg method fail to resist the local over-fitting and finally does not approach stable state in the training, while FedSpeed can converge stably and efficiently, which far faster than other baselines. (c) and (d) show the empirical studies of increasing the local interval. FedCM is the second SOTA-performing method in our baselines, while it still can not speed up by increasing local interval in the practical training. As shown in (c), increasing local interval almost does not have any benefits to FedCM, and the communication rounds can not be reduced. While in (d), FedSpeed succeed to apply larger local interval to reduce the communication rounds. When is increasing, to achieve the similar performance, the total communication rounds is nearly decreasing as K x, which is useful property that is very efficient in practical training.
In our paper, what we claim is that if a federated learning method could adopt large K, it is good property. Unfortunately, most SGD-type algorithms cannot increase the convergence rate by increasing K. Some useful techniques are adopt in the FL framework to improve the performance, e.g. variance reduction, gradient tracking and regularization term (mainly the prox-based methods). FedSpeed is prox-based method which incorporates the correction term and extra ascent gradient to improve the performance. In fact, it has been proven that apply the larger local interval in the local training under the requirement of local minimal solution per communication round. We theoretically prove that FedSpeed can achieve the fast rate without this harsh assumption and it apply the large K in the local client. Yang al. (202T) have proven that if FedAvg change the partial participation to the full participation (Local (Local-SGD-type) the dominant term of convergence rate will change from O
methods have the potential to
K to O ( ( which will be relaxed to K times faster. Full participation usually achieves higher theoretical rate than the partial participation. VRL-SGD Liang al. (2119) can theoretically improve the efficiency by adopting larger order of local interval K = OVTT) than FedAvg, while FedSpeed can adopt K = O(T).
VnT
B.3.7 ABLATION STUDY OF PERTURBATION WEIGHT a
Perturbation weight a. determines the degree of influence the perturba- tion gradient term to the vanilla stochas- tic gradient on the local training stage. It is trade-off to balance the ratio of the perturbation term. We select the a from O to and find FedSpeed can converge with any a E [o, 1]. Though the theoretical analysis demonstrates that by applying a > 0 in the term T will not increas- ing the extra orders. And the experimental results shown in Table indicates that the generalization performance improves by increasing a.
Table 8: Performance different a with Po = 0.1.
0
0.5
0.75
0.875
0.9375
1.0
Acc.
83.97
84.36
84.91
85.46
85.74
85.72
C PROOFS FOR ANALYSIS
In this part we will demonstrate the proofs of all formula mentioned in this paper. Each formula is presented in the form of a lemma.
C.1 PROOF OF EQUATION (2)
Equation (2) shows the update in the total local training stage.
Lemma C.1 For V xt_ E 2dd and i E St, we denote oi xx, - x(, - with setting 88,0 0, and
Ai,K = Ek 82 = xf,K x under the update rule in Algorithm Algorithm 1, we have:
D Xx
Σ
2k + +
(11)
Si,
K=U
where EK-1 7k -K-I 2
)
K K-1-b
=9=1 (1 2
21

---

Published as a conference paper at ICLR 2023
Proof] 1 According to the update rule of Li in Algorithm Algorithm 1, we have:
ōy: -i, - xi,k x1,k-1
- ( gl- + A (x x(,0) (nI -/- + A x
X
Then We can formulate the iterafive relationship of ii, as:
1 = -i, - -a--mmiie (g - 8. g!-1+ + A 1) = =11 x
111 | --1 m - -88
Taking the iteration on k and we have:
K-1
X - x = Di, =
(1
11
X
K
A 1.0
111 Σ
(1
-
m1 k
1 - -
km0
K
7
Σ
(1
111
1 (g 88 1
X
k=0
K-
T Ky (g., - gf
Ā (1
K
X
11 (1
"1
K-1-k : gi
+ (1 (1 2 K )
X
k=0
K-1
\y
Σ
Yk Bi,k >\gi-1
?
k=0
(a) applies Ai.0 = 6/,0- = =0.
C.2 PROOF OF EQUATION (3)
Equation (3) shows the update of the prox-correction term, which utilizes the weighted sum of the previous local offsets as a bias controller for eliminating the non-vanishing bias resulting from the prox-term.
Lemma C.2 Under the update rule in Algorithm Algorithm 1, we have:
K- 1
g = (1 - 7)8! +
(12)
Bi
k=0
where Σk=o Th = -K x (1- 4) K k- =7=1 (1 ))x
Proof According to the update rule of Line. 13 in Algorithm Algorithm 1, we have:
g s'=g.-1-
(xt
xx,0)
K-1
171
Σ
(1
171
K K-1-k
(gi,k
gi 11
0=
K-1
K-1
g
11
+
1
K-
1- gi,
K-1-R h
g
A
A=
k=0
K-1
11
1
(1
X
8i,
11
X
K-1
(1
K 1
m
A
Σ (1 - m
K- 1-
giA
0=
22

---

Published as a conference paper at ICLR 2023
K
= (1 - 7)
1
+
7k
Bi,
k=0
(a) applies the Lemma C.I
C.3 PROOF EQUATION (4) AND (5)
Lemma C.3 Considering the u ++ 1/ Eselm) xi,K is the mean averaged parameters among the + 1-7
last iteration of local clients at time t, the auxiliary sequence {z' ut satisfies the update rule as:
- (u'
u -' }eso
K
2 c+1
Bik
(13)
m 16[m]
km0
Proof Firstly, according the lemma C.1 and Line. 14 and Line. 16 in Algorithm
have:
x x,,x)
m
EE|m]
1
(xf K x1,0 - -18--1)
{E[m]
K-1
Tk _t Bi,k + An - -xg!-1)
m
?
{E[m]
k=
=
7k
(ngl + (1 - -1)!!!-!-)
ic(m]
k=0
This could be considered as momentum- term with the coefficient of Here define virtual observation sequence {u'} and its update rule is:
k+1 = u/ x 2k
(Tgi, + (1 - -7)8!-11
t+1 =
1+1 = Σ k
1,0
xE(m]
According the lemma C.2 and above update rule, get that:
K
(1- +
at
Bick
k=D
K-1
(uf
u4,0) - ?
Σ
2
2k 7
[ ul,a).
1
gi,k
γ
This function indicates that the virtual sequence ut could be considered commentum-basee update method with global correction term to guide the local update, and the correction term is calculated from the offset of the virtual observation sequence during the training process round t.
Then we expand the the auxiliary sequence z! as:
1 1-2
1 1-7 (u' -1)
++1 z¹ = =(u++1 - u²)
(u ++1 ut)
23

---

Published as a conference paper at ICLR 2023
1 -(uut1
-²)
1 7
7
(u' (u"-u" -u'-1)
?
K-1
Σ
gi,k)
=t
+
1 -
g!-
1 1-9
(u' - 1²
?
7
ic|m
0=
1
7h at
1 1-71 1
Σ
Ag
1-1
1 -
(u' - u2
Bi,k
m
7 m
iE|m
k=
im(m
Th at
1- 1
(u'
u + >g11--1
Bi,k
7
7 m
[m)
k=U
im(mi
Y
Bi,k
1-7 1
Σ
[
x
2 K
Agi
m
?
7 m
|E|m] k=
VE(m!
1 7 1
Si.k
[ -
x 000
Ag!-3) 3)
m
7
7 m
Em/
k=
kE(m!
Σ
7k Ki,k
m k=0
7
iE|m]
C.4 PROOF OF THEOREM 4.5
Firstly we state some important lemmas applied in the proof.
Lemma C.4 (Bounded global update) The global update
1 m Eie(m) &i holds the upper bound of:
K- 1
E.1 Σ g 12 E,
< 7
Σ g
1p
1 Σ E,
gil?
+ Eell
2k
g k
11?
vE(m)
(E[m)
*E [m)]
iE|m]
k=0
Proof 4 According to the lemma
C.2 we have:
K
1
=
Σ
7k gi
[m[m]
[E(m]
x
[m[m]
k=0
Take the L2-norm and we have:
K
=
Σ
Thk
11
ie [m] k= ?
3E[m)
K
I <11
Σ
1
12
vE[m]
:E|m]
k=0
Thus we have the following recursion,
K-1
E.ll 1
Eg
11
E- m
Ex
Σ
1
g
E. m
1
1
ΣEN
+EI
Σ Σ
The
m
?
iE ml
+E[m)
iE ml
.E(m] K=
24

---

Published as a conference paper at ICLR 2023
Lemma C,5 (Bounded local update) The local update g holds the upper bound of:
Ex
11
P 1
(E
12
24PL²
K-1
Tk
k.
|x1,
x11
m [m(m]
[m]
E [m]]
k=
+ 12PE.
(VF
P(120) + of))
where: 1. =11- 24
72
Proof' According to the lemmoC.2 we have:
K-1
g = (1
?)
1- +
Bi,k
?
k=0
Take the L2-norm and we have:
1 = 7g
1-1
+ 7
Σ
7k
Si,k
11?
?
k=0
(a)
S (1 (--))\ + 7/|
K-1
7kk
Bi, 1
?
k=0
(
K 1
1| 112 +
Tk
B 11
k=
(1
7)
11
Σ
7
|l 11
k=
(a) and (b) apply the Jensen inequality. Thus we have the following recursion:
K
1 Σ B.ll!--11
11
Σ
(E.ll!!-11)
1
7
E,
m (E[m]
Y m RE[m]
m sE[m]
Here provide a loose upper bound as a constant for the quasi- stonhssstc gradient:
K-1
78 E2
| 2
xE|m]
k=0
K- 1
Tik E, (1 - a)gin, + 2lg
m
VE [E(m]
0=0
K 1
1
Tik Er E + taliia -g,
7
VE ml
k=0
K- 1
<
2
Yik
(E,
+ oof
7
ml)
1m
<
2
K-1 1
.kk
+ VF +
7
k=0
4
Tk
V. + -
7
0=0
25

---

Published as a conference paper at ICLR 2023
1
K-
Fe || 2²12 + 12R, | VF + (120² + +of)
m
ie[m]
k=0
12L
K-1 1
7k
Er
||
x² +x - -u' + u² - -z'11
iE(m] k=
+ 122,,
[12 (120g +o²)
24L
7k
E, 112|, x-12 + 2-22 1xx - u² +u' 2112 + (120g of)
m
im(m)
k=
+ 12E, V Fz
24L
K-
2k E
-x11
27)² 241 -22)) 1
Belle:-11 $122
m
7² m
(E(m)
+ 12E (120g + +ff)
We applies the Jensen inequality, the basic inequality || - 2 n
1= >
a |all? and the upper is the constant, we
bound of p S atc. Combining the above inequalities, let 1o = 1 24 have:
2n
72
E.
P1 Y m
1Ecl@!!-11 12 24PL2
K-
7 E. |
x'11
m
m
?
1Emm]
[E(m)
ie(m] k=
+ 12PE. 12P P(120) of)
C.4.1
L-SMOOTHNESS OF THE FUNCTION F
For the general conve case, according to the Assumptions and the smoothness of F, we take the conditional expectation round + and expand the F(z(+1) as:
L.
[F(F(z(11) F(z') E (VF(z'), 211 z²)
Eg Ee|lz(+1 -
zz
2
L
F(x') (ZF(2') B, - 2²)
Re|lxtt1 - x2112
2
= EE,
Σ
K-1 1
7k
I. gi,k) + "Ellzztt [ - =z
m
2
{E[m]
0=0
K
= =F(2²) AE((V
Σ
VF(z)) + VF(z'))
ie m
k=0
-EB1l12t11 2²12
2
K
= =F(z') >||VF(z\))1 -E,
Σ
7k
gi - VF(2')
3E 8E|m]
km
R1
L
+ 2
Egllz" ++1 111
26

---

Published as a conference paper at ICLR 2023
C.4.2 BOUNDED R1
Note that R1 can be bounded as:
K-1
R1 = XE 1
2k
VF(2')
Bi,k
m
1E[m]
A=
K-1
K-1
@ XE,
Ik Bi.k
mhe
F; (2'))
m
m
EE
m
0=
VE [m]
h=0
K-
K K-1
|F(2')12
+
Eell
7
(ggi, - VFF((')) 12
Eell
Ne Egi
2
2
m
2m?
[m(m]
k=0
:E|m A==
() 2 VF(2'))
A +
K-1
1
IESi, VP((2')12
E&ll
|l
K-1
The Bgg & 11?
2
2m
mm(m)
K=U
iE iElm)
k=0
Rl.a
(a) applies the fact that 1 Eielm VF VF(z'). (b) applies yx,,y) - -11x|12== + 11y
m
||x + y)l²). (c) applies the Jensen's 's inequality and the fact that Σ 74 =
According to the update rule we have:
Eg (1 E [ + aE
[ = (1- a ( + +o (V
= a1 + -1 + +VVP( + pB),..).
Let p S V
thus we could bound the term R.I aa as follows:
The E Lggh V2((2))12
m
iE m/
k=0
K
Σ
2
E, [1 (1- -1 a)) +OVE + -VE()))
VFi(2')11
m
?
sEim]
k=0
K
7k
E, (F VE((2') + a (VEF((Z) + - 11?
m
sEim]
k=0
K
20²
K-
7k
E2 (x(,))) - VF(22))22+ +
7kk E2 ( - (F((2)
m
?
xE xc|m]
k=0
iE[m]
k=0
21
K-
Tkk R, |||, - 222 + 2a²12p²
K-
7k
E, lBf. ||
m
m
(E[m)
0=
AE xE(m) k=0
2L
K-1 1
Tkk E 1 1. x² + x² u² + uu
- z" 211
L2
K 7 Eg llg. 11?
(E(m)
K=0
1 [m]] k=0
4L2
Nk E, Ex x
4L2
K 1
7kk
Exl((x - u²) + (u' - x 22)
7
(E[m] k=
8E mm]
k=
2a L2 p
K
The Eell gil.....11 - (F )|
122
K-1
Fhe Eg (x
m
[E/m] k==0
1 mz] k==0
412
K-1
- 12 20
K 7h
7h
R., ||
E. V
2.22.220
7
m
EE kE(m
K=
V [E[m]
k=
27

---

Published as a conference paper at ICLR 2023
+ E,L' (x' - u') + (u' - -z')1²
4T2
K-1
7k 1 - xx112+
2022
K-1
[V 1202
m
7
m
iE[m] 0mm0
rE[m]
+ +4L
\g!-1
+ 7-1
(u' uu' !1
7
EE mm)
4L
K-1 1
Te Ee |Xx
x 11
20²LLpp p²
K
7 E,
m
rE(m] k= ?
[E[m]
k=0
--11)));;-) 1)P 11
1 ( )A8i-1)
+ Eee
(u'
+ Ag1-1)
(n'
u + Ag/-1) + (
m kE(m]
?
7
4L
K-1
Tee Eellx
x 12
2a²L2 p²
K-1
2 E. [V[(x))) +202
m
m
iE[m) K=
(E(m) k=0
22
27)²
Eell
Σ
Bi 11-211
72
m
ic(ml
4L
4X2 - 27)²
Eel ||
x
E,
-/- +222L'pp'
g:
m
7
72
iE[m)
k=0
mE/m]
20 1.2pp
K-1
T Eel ()(()(.))))))))))))))))))))))) VP((2') + VF((*) - VF(2')12
m
7
EE 0==
(0)
2L
K-
7k E, | - x1 422I2(1 - -27)2
1
Eell
Σ
o 1|2 + 202
m
?
72
m
[E[m]
km0
rE[m]
2L
K-1
7kk Be 1x
2/12 +
6a 1,2 oz + 6.221.2 12
m
?
ie[m]
k=0
8L2
K-1
Tke
- 12+
27)² 8A2L2(1 212))
ET
1 + 202
m
72
m
mm(m]
k=0
iE(m]
+ 6a 21 L2 p² o
+ 60 2.2 0² (V
(0) 8L
Σ
K
Lk
Ex - xx1 +
SA2IL(1 - -27)2
E1
Σ g
E,
Σ g
m
?
73
m
m
<E(m]
k=
4E(m)
dE(m)
8X2 L (1(
27)²
Bell m
Σ
K l
7h
g 2 + 202 + 60 22 + 66 602
/ 11
72
?
sE(m]
k=0
(a) applies the bound of p as p
ViaL. (b) applies the lemma C.4 These others use the fact B|rr- [[x]]] = E|a²] - [[x]]] and ||x y11 < (1 + x]||x||2 + (1 + I
-
We denote e¹ = Eiem Σk-1 (7h /r || - 12 term as the local offset after l iterations updates, we firstly consider the cj
1 Σrem E, | - x21 and it can be bounded as:
1
c/
Ex Ex k - x" x2112=
Ex 1x11 - x(,n-1 + x(x-1 - x
m
m
xE(me]
sE(m]
1
E. || - nr (g. B- - g! + (1
M1
N ) -x1,0)11
sE[m
28

---

Published as a conference paper at ICLR 2023
$ (1+a)(
3 Σ
Ee||x -x + (1 +
) Σ
1 of
Bellgi, - 8 1
A m
a m
:c(m]
RE [m
= =1+ a)(1
n / ccc_ 1 + (1+
Σ
E
(L -
- a) + tggi - 11- 11:12-1--11
a m
m
= =(1+ 1 MI
- Egl -
+ - -VE((()-)))
a' m ré(m]
+ (1 + in + (1 + a)(
M x P
1 3m
$ 51+
V + Ecll
- + +
a m /E/m
+ +(1 + un of + (1+ a1
1
T2 1dp
a
S
1 4m
E. [E -- (1+ 1 3nd
Σ
1
+ (1+
Mo!
1
a m
a m [E|m]
0
TE[m)
+ + (1
1 c
$1+ 1 4m
B2 [F VF(()) + VF(()) - + -
m
eE/m²
) 3n Σ
Eg 112 + (1 + 3 m 07 + (1+ m 7
1
+ +VF(z')11
+ +1+
sE(m]
s(1 + 1 161 L2
1
1
By B k- - x21 + (1 + 161) 1.2 x - 2 + (1 + - 1 (160 + +o7)
a
m
mm|m
1 अ
+ +(1+ - 16 (F || (1 +
E, 1| + +01+++++00 a) - ア c k-1
a
m
xE(m]
$ (1+ 33 + (1 +
- a
1
16n2 L2
c/ + (1 + - )) + +f)
+ +1+ 1
1166 | (F(
+ (1+
1
!n1 3+
1612I,21 - -27)2
1
E. 1ells/-'113
a
72
kE[m)
= (1 a)(1 -
m - + (1 (1+
1 | 167 1.2 1.2
c/ +11
)n? (160, + +f)
+ +1+ 1 |n (88P - 16) + (1+
2p - 1)
(120 + +f
3
+ (1+ -
-1167 E4 11 (1 +
nn (44P- - 8)
a
+ (1 1 2 1 Σ (B. 11
37
mE|m]
When P satisfies the condition of P S 2, which means & = 24x2 the constant of P(P
> 1 then we have
7²
3 2 < 1, let the last 120² y enlarged to 160z for convenience, we have:
of < (1 + a) - my -- + (1 + 1 _ 16 1.?
1 - (1603 + +of) + 160 + a 13
oi + 2(1 +
a
29

---

Published as a conference paper at ICLR 2023
96(1 + 1 [VF + 1 of 1
(Bellg:
1allg/-112 112
Eg E.
m =E(m]
Here we get the recursion formula between the of and - Actually we need to upper bound the c' ( (1./ thus let the weight satisfies that:
) (1+ )² + +1+ a
16m L² - YK 7K-3
11
-K-1
7K-2
70
X
let Yit < A and thus we have:
c²
7ke
ck
1
K-1
(1602 + of + 48E /FE + 80L'c'
2 +
km
E, B
112 1ella(11))
my
iE[m)
(0)
1
7
(160 of + (F(2))) 80T.c
2(1
M
?
1
Σ
EL
1 111 E.lla 1.
my
:E/m²
22(1 + )nik
1
160g oo + 48E 1V(2')1
(Eellgl-112 Exllg! (12)
a
my =E|m)
+ 160 + I.2''.
(a) enlarge the sum from K' to K where K' < K 1.
Let nn satisfies the upper bound of m S 320 for convenience, we can bound the cx as:
c' = 4(1 + 1 |n 160 + of 4SE (FF2')) my *E[m]
-
E.
Let the satisfies 1 for convenience, summarize the extra terms above and bound the term R.l.a as:
R..a=
7k E, E
(2))2))1
m iE[m]
k=0 7
22 - 27
< 8T.20' +
8 61-
Eell
Σ
gf12
+ 20221.220f
73
[m(m]
[m
82 -2
1
K-1
Eg
112
6a 6a2 202
72
m
ml
K=0
8A2 - 227)
Exl
Σ
11
Eg
E!'??
+ 2a 202 60 2
73
[E(m)
[m(m
30

---

Published as a conference paper at ICLR 2023
- (1
1
K-
64
Eel
(E 112
E, 11
7/
m
my
m
k=0
[m(m]
+ L2 /
VF
6a
( + +
thus bound the R.1 as follow:
K-1
X R1 S E, VF(2')]
7k
R1.a Bell
2
2m²
sE(ms]
( 2
A
22
+ 3Aa2 1536An
V )1
Eel
(Elle '12 -1
ym
sc(ml
413 - -27)3
1
1
Eel
g,
1--11
112
Eell
+ da L' 1222(330 + of)
73
m
SE
selm]
22 - 27)²
K-1
72
E1
m
2k at
Si,k γ
33 L3 (160, of)
vE[m]
We notice that R1 contains the same term with a negative weight, thus we can set another constrains for X to eliminate this term. We will prove it in the next part.
C.4.3 BOUNDED GLOBAL GRADIENT
As we have bounded the term R1 and R2, according to the smoothness inequality, we combine the inequalities above and get the inequality:
L R2
R. (F(2 S F(z')
+RI+ + 2
= F(Z')) - ( 32p² 1536Am L [VFF('))1 + >2 L3 of)
A
4 ( 2
L
K
+
E1ll
Σ
$f
72
2m
2m
7E|m)
k=0
32AmR 1.2K K
[E g 211 - Ell
+ 32 L22 K (160² + +ff)
mm
kE[m]
4X
2yy²
Bell m [E(m)
o 112 Eell Σ
Σ ?!'??
73
77 <E(m)
We follow as Yang et al. 2021) to set À that it satisfies 413 2
2m 2m S 0, which is
X X
easy to verified that A has upper bound for the quadratic inequality. Thus, the stochastic gradient
term is diminished by this X. We denote the constant λx = 3 2 - 1536An L K and k could be considered as constant. We can select two constants e₁ E (0. _ ) C2 (0, 1 and they C22 where
satisfy C1 + 02 E (0. 1), we let 1 -3p2 2 c1 and 1 1536n L
2
Vor < TaaL and m 1676KL 32/3KT Then we can bound the the P and tp satisfy P < 3aaL / 3 L2p² 1536n L2K > I constant upper bound.
0, and the term
N
<
22: -2g
2
which is a
We take the full expectation the bounded global gradient as:
A< < (BF(2') - EF(2(+1)) + 32 L
E EEl/!
12
m
[e(m
31

---

Published as a conference paper at ICLR 2023
4X 27)2
Erll - Σ g 11-
-Erll
Σ
73
m im(m]
m
cc(mm]
+ 32An L3 (160) + of) + Aa L2 p (30
+ of)
Take the full expectation and telescope sum on the inequality above and applying the fact that F S F(x) forx E Rd, we have:
1 E, VE S NOT (F(2)) E, ((("))) + 32t 1.3K K
[ (Elle?11 - l
kymi
sE(ml
4A2 - -27)²
Bell 1
+
8f1l2 - Eell Σ E
NY9T
ic(m)
<E(m)
1
+ R
(32 1.2 K(160²
9 + ot) + Xa 2 T.2 p² (300 + of))
(F(z") - F*)) + 32m 1.2K K
E
ArT
kymT
sc(m]
4X2 - 27)²
E1
||
g 12
RYST
m
xE(m)
1 (32Am (166, + of) + Xa2 + oi))
Here we summarize the conditions and some constrains in the above conclusion. Firstly we should
note that 7 = 11111-1 )) < when mnt S 2A. Thus we have 1/7 > 1. When K satisfies
that K 2 (1- -
(1= k < - and then 7 > 1 - - and 1/7 < - 2. To let
k= = 1/2
3a2 - 122 > hold, P and m satisfy that p < Veal and T 32/3KL
-
E (F((t))) 2(F(Zt)-F)) F²)
LAK
EIE + 32X²12
Σ
E2
Σ
g!
An.T
KT
m.
RT
m
kE(m)
EE (E|m)
(32Xn) + +o?) + Xo T?2 2= + +o?))
32


Reviews:
[{"review_id": "jugtMd7gbO", "reviewer": "Reviewer_P9p1", "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": "This paper proposed a new federated learning (FL) algorithm called FedSpeed to mitigate the negative impacts of data heterogeneity and client drift problems in FL. The proposed method uses a prox-correction term on current local updates to reduce the bias introduced by the prox-term while retaining the benefits of the prox-term to maintain local consistency. The authors showed that FedSpeed has an $O(1/T)$ convergence rate to a constant error neighborhood and allows $O(T)$ local steps per communication round. The authors conducted experiments to compare FedSpeed with several existing FL algorithms.", "summary_of_the_review": "This paper proposed a new algorithm called FedSpeed to mitigate the impact of data heterogeneity in FL and achieve a fast convergence rate under this setting. Although the problem is important and the proposed algorithm contains some interesting ideas, the algorithm has too many hyper-parameters to tune and could be hard to implement in practice. Perhaps also because of this reason, some of the convergence performance analysis seems questionable and may need more careful checking.", "strength_and_weaknesses": "Strengths:\n1. This paper considered how to mitigate data heterogeneity and the resultant client drift phenomenon, which is an important problem in FL.\n2. The authors conducted a detailed theoretical convergence rate analysis\n3. The authors conducted comprehensive experiments with existing FL algorithms.\n\nWeaknesses:\n1. Although the proposed FedSpeed algorithm contains some interesting ideas (momentum plus prox) and is shown to have a strong convergence rate performance, the FedSpeed algorithm has a large number of hyper-parameters: $\\rho$, $\\alpha$, $\\eta$, and $\\lambda$, which could be quite difficult to tune in practice. Also, in the experiments, although the authors mentioned to some degree how to choose these parameters, it's not entirely clear from the paper how these parameters are related to each other.\n\n2. The $O(1/T)$ convergence rate in Theorem 4.4 seems questionable. Specifically, there is a constant $\\kappa>0$, which necessitates a very small local learning rate $\\eta_l$ and parameter $\\rho$. Furthermore, $\\eta_l$ depends on local steps $K=O(T)$. So in the end, the denominators of the first 3 terms on the right-hand side of Eq. (6) all have nontrivial dependence on $T$. Thus, it seems to claim $O(1/T)$ convergence rate is questionable (at least not holding without a careful justification).\n\n3. Remark 4.7 also seems misleading. It is actually not safe to the performance will improve as $K$ increases. For the same reason as above, in Corollary 4.5 where the authors plugged in values to derive the dependence of $\\Phi$ w.r.t. $\\Phi$, the dependence of $\\kappa$ on $T$ seems neglected. I would suggest the authors double-check all the calculations to make sure there is no error.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "b0kvu8jY-NZ", "reviewer": "Reviewer_CRv7", "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": "This paper studies federated learning for nonconvex optimization. The paper proposes a novel algorithm called FedSpeed, which applies a prox-correction term to reduce the bias and leverages gradient perturbation to improve the local generalization performance. FedSpeed achieves a fast convergence rate of O(1/T) and outperforms other baselines empirically.", "summary_of_the_review": "Overall, I think this is an interesting paper with solid contributions to federated nonconvex optimization.", "strength_and_weaknesses": "The paper is well-written and easy to follow. The proposed algorithm achieves a convergence rate of O(1/T) by incorporating prox-correction terms and gradient perturbation techniques. I have not checked the proofs in the appendix, though major arguments seem to be correct. \n\nMy concern is that the experiments only compare the test accuracy. The paper may also present the training losses or gradient norms to verify the theoretical analysis.", "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": "QEJBzx21kq", "reviewer": "Reviewer_W3wF", "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 FedSpeed algorithm which has two components 1) prox-correction term and 2) extragradient perturbation where they relax a couple of assumptions made in prior work while achieving the same rate. \n\n", "summary_of_the_review": "Please see the comments above!\nI will update my score based on the authors feedback.\n\n", "strength_and_weaknesses": "Strength:\n\nThe experiment section is convincing to me. The way I see it, roughly speaking this paper uses both “gradient tracking” with additional “regularization” to deal with hetregenoty and improve generalization error which is interesting to me.\n\nComments:\n\nThere is no improvement in terms of achieved rates.\nAs mentioned on page 4, prox-term introduces an additional bias term. So, my question is do you show this extra gradient term can help to remove that bias?\nIn the title, it is mentioned “Higher Generalization error”, yet there is no theoretical proof for this claim (just verified through some experiments).\nAuthors keep mentioning that having larger local updates is a good property. However, there are a couple of papers such as [B] where it is suggested that there is no clear benefit to having a bigger local step size in FL, which contradicts the statement of this paper.\nMinor:\n\nThe following references [C] and [D] are using gradient tracking ideas (which show improvement over SCAFFOLD) so I would recommend authors compare their results with these references theoretically and empirically.  \n\n[B]: Woodworth, Blake E., Kumar Kshitij Patel, and Nati Srebro. \"Minibatch vs local sgd for heterogeneous distributed learning.\" Advances in Neural Information Processing Systems 33 (2020): 6281-6292.\n\n[C]: X. Liang, S. Shen, J. Liu, Z. Pan, E. Chen, and Y. Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv:1912.12844, 2019.\n\n[D]: Haddadpour, Farzin, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. \"Federated learning with compression: Unified analysis and sharp guarantees.\" In International Conference on Artificial Intelligence and Statistics, pp. 2350-2358. PMLR, 2021.\n", "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": "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": {}}]

Author rebuttal:

Decision: Accept: poster