Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initialization
Authors: Yan Sun
Li Shen
Dacheng Tao
Venue: NeurIPS 2023 poster (2023)
Keywords: federated learning
local consistency
personalized initialization
excess risk
TL;DR: We propose a novel FL method and analyze the excess risk theoretically to understand the essential impact of the local consistency.

Abstract: Federated learning (FL) is a distributed paradigm that coordinates massive local clients to collaboratively train a global model via stage-wise local training processes on the heterogeneous dataset.
  Previous works have implicitly studied that FL suffers from the "client-drift" problem, which is caused by the inconsistent optimum across local clients. However, till now it still lacks solid theoretical analysis to explain the impact of this local inconsistency. 
  To alleviate the negative impact of the "client drift" and explore its substance in FL, in this paper, we first design an efficient FL algorithm FedInit, which allows employing the personalized relaxed initialization state at the beginning of each local training stage. Specifically, FedInit initializes the local state by moving away from the current global state towards the reverse direction of the latest local state. This relaxed initialization helps to revise the local divergence and enhance the local consistency level.
  Moreover, to further understand how inconsistency disrupts performance in FL, we introduce the excess risk analysis and study the divergence term to investigate the test error of the proposed FedInit method. Our studies show that on the non-convex objectives, optimization error is not sensitive to this local inconsistency, while it mainly affects the generalization error bound in FedInit. 
  Extensive experiments are conducted to validate this conclusion. Our proposed FedInit could achieve state-of-the-art (SOTA) results compared to several advanced benchmarks without any additional costs. Meanwhile, stage-wise relaxed initialization could also be incorporated into the current advanced algorithms to achieve higher performance in the FL paradigm.

Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initialization
Yan Sun The University of Sydney ysun98990umi. sydney. syyd:geeemnnynnnnoeoooeoeaama
Li Shen' JD Explore Academy mathshenl 10gmail. com
Dacheng Tao The University of Sydney dacheng tao@gmail com
edu. au
Abstract
Federated learning (FL) is a distributed paradigm that coordinates massive local clients to collaboratively train global model via wise local training processes the heterogeneous dataset. Previous works have implicitly studied that FL suffers from the "client-drift" problem, which is caused by the inconsistent optimum across local clients. However, till now it still lacks solid theoretical analysis to explain the impact of this local inconsistency. To alleviate the negative impact of the "client drift" and explore its substance in FL, in this paper. first design efficient FL algorithm FedInit, which allows employing the personalized relaxed initialization state at the beginning of each local training stage. Specifically, FedInit initializes the local state by moving away from the current global state towards the reverse direction of the latest local state. This relaxed initialization helps revise the local divergence and enhance the local consistency level. Moreover, to further understand how inconsistency disrupts performance FL. we introduce the excess risk analysis and study the divergence term to investigate the test error of the proposed Fedlnit method. Our studies show that optimization error is not sensitive to this local inconsistency, while it mainly affects the generalization error bound in FedInit. Extensive experiments are conducted to validate this conclusion. Our proposed FedInit could achieve state-of-the-ar (SOTA) results compared to several advanced benchmarks without any additional costs. Mcanwhile, stage-wist wise relaxed initialization could also be incorporated into the current advanced algorithms achieve higher performance in the FL paradigm.
1 Introduction
Since McMahan et al. [26] developed federated learning, it becomes a promising paradigm to effectively make full use of the computational ability of massive edge devices. Kairouz et al. [17] further classify the modes based on the specific tasks and different environmental setups. Different from centralized training, FL. utilizes central server to coordinate the clients to perform several local training stages and aggregate local models as one global model. However, due to the heterogeneous dataset, it still suffers from significant performance degradation in practical scenarios.
Several previous studies explore the essence of performance limitations in FL and summarize as the "client-drift" problem [1, 19, 22, 38, 44, 46, 48]. From the perspective of the global target, Karimireddy al. [19] claim that the aggregated local optimum is far away from the global optimum due to the heterogeneity of the local dataset, which introduces the "client- drint" in FL. However, under limited local training steps, local clients can not genuinely approach the local optimum. To describe this negative impact more accurately, Acar et al. [1] and Wang et al. [44] point out that each locally optimized objective should be regularized to be aligned with the global objective. Moreover, beyond the guarantees of local consistent objective, Xu et al. [46] indicate that the performance "Li Shen the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

degradation could be further eliminated in FL if it guarantees the local consistent updates at each communication round, which is more similar to the centralized scenarios. These arguments intuitively provide forward-looking guidance for improving the performance in FI.. However, in the existing analysis, there is still no solid theoretical support to understand the impact of the consistency term, which also severely hinders the further development of the FL paradigm.
To alleviate the negative impact of the "client-drift" problem and strengthen consistency in the FL paradigm, in this paper, we take into account adopting the personalized relaxed initialization at the beginning of each communication round, dubbed Fedlnit method. Specifically, Fedlnir initializes the selected local state by moving away from the current global state towards the reverse direction of the current latest local state. Personalized relaxed initialization helps each local model to revise its divergence and gather together with each other during the local training process. This flexible approach is surprisingly effective in FL. and only adopts a constant coefficient to control the divergence level of the initialization. It could also be easily incorporated as plug-in into other advanced benchmarks to further improve their performance.
Moreover, to explicitly understand how local inconsistency disrupts performance, we introduce the excess risk analysis to investigate the test error of FedInit under the smooth non-convex objective, which includes an optimization error bound and a generalization error bound. Our theoretical studies indicate that the optimization error is insensitive to local inconsistency, while it mainly affects the generalization performance. Under PE-condition, consistency performs as the dominant term in the excess risk. Extensive empirical studies are conducted to validate the efficiency of the FedInit method. On the CIFAR-10 10/ 100 dataset, it could achieve SOTA results compared to several advanced benchmarks without additional costs. also helps to enhance the consistency level in FI..
In summary, the main contributions of this work are stated as follows:
We propose an efficient and novel FL. method, dubbed Fedinit, which adopts the personalized relaxed initialization state on the selected local clients at each communication round. Relaxed initialization is dedicated to enhancing local consistency during training, and it is also a practical plug-in that could easily to incorporated into other methods.
One important contribution is that we introduce the excess risk analysis in the proposed FedInit method to understand the intrinsic impact of local consistency. Our theoretical studies prove that the optimization error is insensitive to consistency, while it mainly affects the test error and generalization error bound.
Extensive numerical studies are conducted on the real-world dataset to validate the efficiency of the FedInit method, which outperforms several SOTA benchmarks without additional training costs. Meanwhile, as an efficient plug-in, relaxed initialization (FedInit) could also help the other benchmarks in our paper to achieve higher performance with effortlessness.
2 Related Work
Consistency in FL. FL employs an enormous number of edge devices to jointly train single model among the isolated heterogeneous dataset [17, 26). As a standard benchmark, FedAvg [2, 26, 48] allows the local stochastic gradient descent (local SGD) [10, 23, 45] based updates and uniformly selected partial clients' participation to alleviate the communication bottleneck. The stage-wise local training processes lead to significant divergence for each client [5, 25, 43, 44). To improve the efficiency of the FL paradigm, a series of methods are proposed. Karimireddy et al. [19] indicate that inconsistent local optimums cause the severe "client drift" problem and propose the SCAFFOLD method which adopts the variance reduction [6, 16) technique to mitigate it. Li et al. [22] penalize the prox-term on the local objective to force the local update towards both the local optimum and the last global state. Zhang et al. [49] utilize the primal-dual method to improve consistency via solving local objectives under the equality constraint. Specifically, series of works further adopt the alternating direction method of multipliers (ADMM) to optimize the global objective [1, 9, 41, 52], which could also enhance the consistency term. Beyond these, series of momentum- based methods are proposed to strengthen local consistency. Wang et al. [42] study a global momentum update method to stabilize the global model. Further, Gao et al. [8] use a local drift correction via momentum-bant
term to revise the local gradient, efficiently reducing inconsistency. Ozfatura et al. [28), Xu et al. [46], Sun et al. [39] propose similar client-level momentum to force the local update towards the last global direction. A variant of client-level momentum that adopts the incrtial momentum to further improve

---

the local consistency level [24, 40]. At present, improving the consisteney in FL remains a very important and promising research direction. Though these studies involve the heuristic discussion on consistency, in this paper we focus on the personalized relaxed initialization.
Generalization in FI. A lot of works have studied the properties of generalization in FL.. Based on the margin loss [3, 7, 27]. Reisizadeh et al. [31] develop a robust FL paradigm to alleviate the distribution shifts across the heterogeneous clients. Shi et al. [32] study the efficient and stable model technique of model ensembling. Yagli et al. [47] prove the information-theores
bounds on the
generalization error and privacy leakage in the general FL paradigm. Qu et [29] propose to adopt the sharpness aware minimization (SAM) optimizer on the local client to improve the flatness of the
loss landscape. Caldarola et al. [4], Sun et al. [37, 38), Shi al. [33, 34] propose several variants based on SAM that could achieve higher performance. However, these works only focus on the generalization efficiency in FI., while in this paper we prove that its generalization error bound dominated by consistency.
3 Methodology
3.1
Preliminaries
Under the cross-device FL setups, there are a very large number of local clients to collaboratively train a global model. Due to privacy protection and unreliable network bandwidth, only fraction of devices are open-accessed at any one time [17, 29]. Therefore, we define each client stores a private dataset S, = { where 2j is drawn from an unknown unique distribution D;- The whole local clients constitute set C = [i] where i is the index of each local client and |C| = C. Actually, in the training process, we expect to approach the optimum of the population risk F:
w E arg min
F(w)= A C
Σ (() LEC
(1)
where Fi(w)= E,,,D, FD
Fu zy) is the local population risk. While practice, we usually consider the empirical risk minimization of the non-convex finite-sum problem in FL as:
{ [(w) & E(ww)
w* E aig
(2)
where + fiww; 2z) is the local empirical risk. In Section 4.1, we will analyze the difference between these two results. Furthermore, we introduce the excess risk analysis to upper bound the test error and further understand how consistency works in the FL paradigm.
3.2 Personalized Relaxed Initialization
In this part, we introduce the relaxed initialization in Fedmnit method. FedAvg proposes the local- SGD-based implementation in the FI. paradigm with a partial participation selection. It allows uniformly selecting a subset of clients / to par- ticipate in the current training. In each round, it initializes the local model as the last global model. Therefore, after each round, the local models are always far away from each other. The local offset wi,k w' is the main culprit leading to incon- sistency. Moreover, for different clients, their im- pacts vary with local heterogeneity. To alleviate this divergence, we propose the Fedinit method which adopts the personalized relaxed initializa- tion at the beginning of each round. Concretely, on the selected active clients, it begins the local train- ing from new personalized state, which moves away from the last global model towards the re- 14 end verse direction from the latest local state (Line.6 in
Algorithm 1: FedInit Algorithm
Input: model w, local model wx. T, K. Output: model w².
Initialize states: initialize w wT, _ w.. for t T do
3
randomly seleet active clients set N from for i E N in parallel do send the w" to the active clients set the w" + 3(w( - w as wio for == 0, 1,..,
4
1-1
6
7
do compute gradient ,', at wi, wi,0+1 = wi, - ngin
end
send the w/ = wi,x to the server end w(t1 N EiEN of
3

---

Algorithm 1). A coefficient 3 is adopted to control the level of personality. This offset B(w" - w k in the relaxed initialization (RI) provides correction that could help local models gather together after the local training process. Furthermore, this relaxed initialization irrelevant the local optimizer, which means, it could be easily incorporated into other methods. Additionally, Fedlnit does not require extra auxiliary information to communicate. It practical technique in FL.
4 Theoretical Analysis
In this section, we first introduce the excess risk in FL which could provide a comprehensive analysis on the joint performance of both optimization and generalization. In the second part, we introduce the main assumptions adopted in our proofs and discuss them in different situations. Then we state the main theorems on the analysis the excess risk our proposed FedInit method.
4.1 Excess Risk Error in FL
Since Karimireddy et al. [19] pointed out that client-drift problem may seriously damage the per- formance the FL paradigm, many previous works [15, 18, 19, 30, 36, 44, 46, 48] have learned its inefficiency in the FL paradigm. However, most of the analyses focus on the studies from the onefold perspective of optimization convergence but ignore investigating its impact on generality. To further provide comprehensive understanding of how client-drift affects the performance in FL, we adopt well-known excess risk the analysis of our proposed FedInit method.
We denote =n as the model generated by FedInit method after T communication rounds. Compared with f(w"). we mainly focus on the efficiency of F(w") which corresponds its generalization performance. Therefore, we analyze the E[F(w")] from the excess risk &g as:
E = EFF("") [[/ = B[F((([[) - f("))
BB f(w"))
(3)
Eo: generulization envor
Eg: optimization eiror
Generally, the [[f(=*)) is expected be very small and even to zero if the model could well-fit the dataset. Thus Eg could be considered as the joint efficiency of the generated model w" Thereinto, Eg means the different performance of w" between the training dataset and the test dataset, and Eo means the similarity between w" and optimization optimum w* on the training dataset.
Assumptions
In this part, we introduce some assumptions adopted in our analysis. We will discuss their properties and distinguish the proofs they are used in.
Assumption For Vw1, W2 E Rd, the non-convex local function Js satisfies L-smooth if:
[Vfi(w)) V/((wa)]l S Ll[ws wall
(4)
Assumption For Ve E Rd, the stochastic gradient is bounded by its expectation and variance as:
E [oiil] f((...), Bllg',- f((wix))l < of
(5)
Assumption For Ve Rd, the heterogeneous similarity is bounded on the gradient norm as: B[ s B"+BV
(6)
Assumption For Ywi, w2 E Rd, the global function satisfies La Lipschitt if:
[]](w)) - f(wa)]l S La | - w2ll-
(7)
Assumption For Vi E Rdd let w* E arg min [ww), the function I satisfies Pl-condition if: 24 (f(w) - f(w")) s [V())]
Discussions. Assumptions 1~33 are three general assumptions to analyze the non-conver objective in FL. which is widely used in the previous works [15, 18, 19, 30, 36, 44, 46, 48). Assumption 4 is used to bound the uniform stability for the non-convex objective, which is used in [11, 51]. Different from the analysis in the margin-base based generalization bound [27, 29, 31, 38] that focus on understanding how the designed objective affects the final generalization performance, work focuses understanding

---

how the generalization performance changes in the training process. We consider the entire training process and adopt uniform stability to measure the global generality in FL. For the general non-convex objective, one often uses the gradient norm E|j V (w))) l| instead of bounding the loss difference E [f f["")] to measure the optimization convergence. To construct and analyze the excess risk, and further understand how the consistency affects the FL paradigm, we follow [51] to use Assumption 5 to bound the loss distance. Through this, we can establish a theoretical framework to
jointly analyze the trade-off on the optimization and generalization the FL paradigm.
4.3
Main Theorems
4.3.1
Optimization Error &
Theorem Under Assumptions 1~3, let participation ratio is N/C where 1 < N < C, let the learning rate satisfy 1 min { (2CKL: NKL) where K 2 2, let the relaxation coefficient B I v2 12'
and after training T rounds, the global model w² generated by Fedlnit satisfies:
T-1
( AnKT
RanL 2 AN oi
3RyMKL L
C².
(9)
T ==
AN
where E (0,1), K1
1300,8 I- 7292
17, and K2
1020,82 I- 7232
+ 13 are three constants, Further, by
selecting the proper learning rate 17 O(V KT and let D f(w0) f(w") the initialization bias, the global model w' satisfies:
D [of + KG
Σ EES(WNIS t=0
(10)
VNKT
Theorem 1 provides the convergence rate of the FedInit method without the PL-condition, which could achieve the ((1/VNKT) with the linear speedup N x. The dominant term of the training convergence rate is the heterogeneous bias G, which is K x larger than the initialization bias D and stochastic bias σr According to the formulation (10), by ignoring the initialization bias, the best local interval K Ooo G This selection also implies that when G increases, which means the local heterogeneity increases, the local interval is required to decrease appropriately to maintain the same efficiency. More importantly, though FedInit adopts weighted bias the initialization state at the beginning of each communication round, the divergence term IE] Bllu ' w'Il does not affect the convergence bound whether 3 is 0 not. This indicates that the FL paradigm allows a di- vergence of local clients from the optimization perspective. Proof details are stated Appendix A.2.3.
f-1
Theorem Under Assumptions 1~3 and 5, let participation ratio is N/C where < N < C, let the learning rate satisfy vi S min 2CKT. NKL Tuk
I where K 2 2, let the relaxation coefficient
122 s
12 and after training T rounds, the global model wt generated by FedInit satisfies:
Blf(w") - f(w'((()))) Se AWnKT [(w")]++++ 3R1 G2
K22T.. of 2N
(11)
2N
where X, AKK1K2 R2 is defined in Theorem I. Further, by selecting the proper learning rate 1j
O log (onN ANNKT) and let D f(w") - -f(=*) as the initialization bias, the global model w" satisfies:
ARKT
Blf(w") - f(ww(()))))))))))) 3 (" D+ L(oî + KOO)) NKT
(12)
To bound the Eo term, we adopt Assumption 5 and prove that Fedinit method could achieve the O(INKTT) rate where we omit the (log(N KT)) term, maintains the properties stated in the Theorem 1. Detailed proofs of the convergence bound are stated in Appendix A.2.4.
4.3.2 Generalization Error &g
Uniform Stability. One powerful analysis of the generalization error is the uniform stability [11, 21, 50]. It says, for general proposed method, its generalization error is always lower than the bound
5

---

of uniform stability. We assume that there is new set Č where C and C differ in at most one data sample on the i* client. Then we denote the w" and w" as the generated model after training T rounds on these two sets, respectively. Thus, we have the following lemma:
Lemma (Uniform Stability. [11)) For the two models w" and w" generated as introduced above, general method satisfies e-uniformly stability if:
sup [ 22) f(w" : 22 sy-(PD)
(13)
Moreover, if general method satisfies c-uniformly stability, then its generalization ervor satisfies Eg S (D,,)>(D.)>>)))) [[f(="; :2)) ff ;2)] S [50].
Theorem Under Assumptions 1, 2, 4, and 5, let all conditions above be satisfied, let learning rate O KT = & where c c= Lo is a constant, and let [S]] = S as the number of the data samples, by randomly selecting the sample 2, we can bound the uniform stability of our proposed FedInit as:
K
Ellf(w" f ;2)]
f(w0"++
1 22 + SLGa))
I40L
ULTK
ol
A T
(14)
$
+ (1 BOE FOE
5-1
L
2
SLGa)
where U is a constant and A = - Eiec B|| Bl w²1l is the divergence term at round t.
For the generalization error, Theorem 3 indicates that &g term contains two main parts. The first part comes from the stochastic gradients as the vanilla centralized training process [11], which is of the order (((TK) 14 /S). The constant is of the order (L/KK)
R. thus we have 1HoL K+poL. If we assume the po is generally small, we always expect to adopt a larger K in the FL paradigm to reduce generalization error. For instance, if we select K + oo, then (((KK) ( /S) + O /S) which is very strong upper bound of the generalization error. However, the selection of local interval K must be restricted from the optimization conditions and we will discuss the details in Section 4.3.4. In addition, the second part in Theorem 3 comes from the divergence term, which is unique factor in the FL. paradigm. As we mentioned above, the divergence term measures the authentic client-drift in the training process. The divergence term is not affected by the number of samples S and it is only related to the proposed method and the local heterogeneity of the dataset. Proof details are stated in Appendix A.3.
f.
4.3.3 Divergence Term
In the former two parts, we provide the complete theorem to measure optimization error & and generalization error Eg. And we notice that, in the FL paradigm, the divergence term mainly affects the generalization ability of the model instead of the optimization convergence. focus on the analysis of the divergence term of proposed FedInit method. Due to the relaxed initialization at the beginning of each communication round, according to the Algorithm I, we have w
this part, we
w|,x K = w + f(w
1-1
gh.k- Thus, we have the following recursive relationship:
K
2+1
w
(w) w" (w
ng
(15)
kumnt)
local divergence at
local divergence
global updote
local updates
According to the formulation (15). we can bound the divergence A via the following two theorems.
Theorem Under Assumptions 1~3,, we can bound the divergence term as follows. Let the learning
rate satisfy 1) S min+ ZZCKL' NKI VOKL where 2 2, and after training T rounds, let 0 < B < Ja 24 the divergence term (A') generated by Fedlnit satisfies:
JN
- Σ
Nioi + KG -0= A'
VNKB* D L(of + KG9]]
(16)
T
T
t=0
Theorem 4 points out the convergence order the divergence A generated by Fedlnit during the training process. This bound matches the conclusion in Theorem with the same learning rate. The

---

dominant term achieves the O(NK/T) rate on the heterogeneity bias G. It could be seen that the number of selected clients N will inhibit its convergence and the local consistency linearly increases with N. Different from the selection in Theorem local interval K is expected as small enough to maintain the high consistency. Also, the initialization bias no longer dominant in consistency. We omit the constant weight 1-9637 in this upper bound. Proof details are stated in Appendix A.2.5.
Theorem Under Assumptions 1-3 and 5, we can bound the divergence term as follows. Let the learning rate satisfy ') S min 2CKL NKL. xpk where K 2 2, and after training T rounds, let
0 < B <
Ae the divergence term A generated by FedInit satisfies:
21'
D + G² T
Noi KG² NKT
A =
(17)
NKT
Theorem 5 indicates the convergence of the divergence A under the PL-condition which matches the conclusion in Theorem with the same learning rate selection. Assumption 5 establishes a relationship between the gradient norm and the loss difference on the non-convex function f. Different from the Theorem 4, the initialization bias D and the heterogeneous bias G are the dominant terms. Under Assumption 5, the FedInit supports a larger local interval K in the training process. This conclusion also matches the selection of in Theorem 2. When the model converges, FedInit guarantees the local models towards the global optimum under at least (1/T22 rate. Similarly, we omit the constant and we will discuss the 3 in Section 4.3.4. Proof details are stated in Appendix A.2.6.
weight T 96,37
4.3.4 Excess Risk
In this part, we analyze the excess risk & of FedInit method. According to the theorems above,
Theorem Under Assumption 1~5, let the participation ratio is N/C where < N < C, let N the learning rate satisfies S min 2CKL" 1 NKL' >ak:) where K 2 2, let the relaxed coefficient
Ve and let [S,] = S. By selecting the learning rate = O (olg(AuNKTT) 21'
0 S 3 <
I i. after
AuKT
training T communication rounds, the excess risk of the FedInit method achieves:
DD+ (P+ Llot + KGA) +o t [T(TK)
VD GK rtct
EE S 5
+
(18)
NKT
TTIE
optimization bins
stability
divergence biax
According to the Theorems 3, and 5, combine their dominant terms upper bound the excess risk of Fedinit method. The first term comes from the optimization error, the second term comes from the stability bias, and the third term comes from the divergence bias. From the perspective of excess risk, the main restriction in the FL paradigm is the divergence term with the bound of Ö T -- ).
The second term of excess risk matches the conclusion in SGD [11, 51] which relies on the number S. Our analysis of the excess risk reveals two important corollaries in FL:
From the perspective of optimization, the FL paradigm is insensitive to local consistency in the training process (Theorems 1&2).
From the perspective of generalization, the local consistency level significantly affects the performance in the FL paradigm (Theorem 6).
Then we discuss the best selection of the local interval K and relaxed coefficient B.
Selection of K. In the first term, to minimize the optimization error, the local interval K is required to ef. < 1, the upper bound expects small local interval
be large enough. In the second term, since ItcL
K. In the third term, since T K+pol 1, it expects large K guarantee the order of T to approach (1/T), where the divergence bias could maintain a high-level consistency. Therefore, there is specific optimal constant selection for K to minimize the excess risk.
Selection of As the dominant term, the coefficient of the divergence bias also plays a key role in the error bound. In Theorem 5, the constant weight we omit for the divergence term A is 1-90,2-
Thus the coefficient of / T is
Combined with Theorem 3, we have the coefficient for the
/I V/-9662" 96
7

---

Table 1: Test accuracy (%) the CIFAR-10/II 100 dataset. We test two participation ratios on each Under each setup, we test two Dirichlet splittings, and each result test for times. This table reports results on 18-Ge (upper part) and VGG-11 (lower part) respectively.
dataset.
CIFAR-10
CIFAR-100
Method
10%-100 clients
5%-200 clients
10%-100 clients
5%6-20 clients
Dir-0.6
Dir-0.1
Dir-0.6
Dir-0.1
Dir-0.6
Dir-0.1
Dir-0.6
Dir-0.1
FedAvg
78.77..11
72.532.17
14
20.
46.35
42.624.22
44.70+.2 22
40.41
FedAdam
76.522.14
70.44
73.28
68.87
48.35
40.77
44.33
38.04..25
FedSAM
79.23
72.89
75.45..19
71.231.26
47.51
43.431.12
15.98
40. 40.222.27
SCAFFOLD
81.37+.177
75.06+.16
78.17
71.244..2
51.98
44.41
41.83 20.70+.29
FedDyn
82.43+.16
75.08
79.96
74.154.34
50.82
42.50
47.32+.21
41.74=.21
FedCM
81.67+.17
73.93
79.49
73.124.18
51.564.20
43.03
50.93+.19
42.33=.19 .9
FedInit
83.11
75.95
80.58
74.92
52.211.09
4..221.21
51.161.18
43.77
FedAvg
85.284.12
78.02
81.23
4.
53.464.25
4..53
47.554.13
45.05
FedAdam
86.44+.13
77.55+.28
81.05
74.044.17
55.564.29
53.41+.18
51.33+.25
47.264.21
FedSAM
86.37
79.10
81.764.26
75.221.13
54.85
51.88+.27
48.65
46,58
SCAFFOLD
81.98 87.73+.17
1.
84.81
19.04
59.45
56.67
53.73
50.08
FedDyn
87.35
82.70
84.84
80.01-.22
56.
53.97 18.18
51.744.11
48. 48.16
FedCM
86.80..33
79.85
83.23
76.421.36
53 03.88..22 22
50.732.35
47.8 47
46.33
FedInit
88.47
83.51
85.36..19
58.84 79.73+.14
27.22
54.122.08
50.27 1.29
divergence term in formulation (18) is (1+-))8%
Therefore, to minimize this term, there is specific
V1-9634
optimal constant selection for 0 < 3
/6
We validate their selections in Section 5.2.
24
Experiments
In this part, we introduce our empirical studies. Due to the page limitations, the details of the dataset, hyperparameters selection, implementation, and some extra ablation studies are stated in Appendix B.
Benchmarks. Our selected benchmarks in this paper are stated as follows. FedAvg [26] proposes the general FL paradigm. FedAdam [30] studies the efficiency of adaptive optimizer in FL. SCAF- FOLD [19], FedDyn [1]. and FedCM [46] learn the "client-drift" problem and adopt the variance reduction technique, ADMM, and client-level momentum respectively FL to alleviate its negative impact. FedSAM [29] uses the local SAM objective instead of the vanilla empirical risk objective to search for a smooth loss landscape, which focuses on the generalization performance.
Setups. Here we briefly introduce the setups in our experiments. We test our proposed FedInit on the CIFAR-10 /100 dataset [20]. To generate local heterogeneity, we follow Hsu al. [14] to split the local clients through the Dirichlet sampling via coefficient D, to control the heterogeneous level and follow Sun et al. [38] to adopt the sampling with replacement to enhance the heterogeneity level. We test on the ResNet- 18-GN [12, 13] and VGG-11 [35] to validate its efficiency. Actually, when the heterogeneity is strong, the performance of personalized initialization will be better. To better demonstrate the performance of our proposed method, we add additional noises to the dataset. Specifically, we first introduce the client-based biases. Among clients, we assume that the data samples are obtained differently. Because the local dataset is private and its construction is unknown, i.e., they are collected from different machines or cameras. Therefore, we change the strength of the RGB channels with random Gaussian noise for different clients. The second noise is the category-base basery--baeddde biases. We assume that samples for each category also contain heterogeneity. In our experiments, we add different brightness perturbations to the samples in each category by a random Gaussian noise. Based on these two noises, the heterogeneity of the local dataset is significantly enlarged. In this more realistic dataset, we can clearly observe the performance of each algorithm.
For each benchmark in our experiments, we adopt two coefficients D, 0.1 and 0.6 for each dataset to generate different heterogeneity. We generally select the local learning rate 0.1 and global learning rate ' = on all setups except for FedAdam we use 0.1. The learning rate decay is set as multiplying 0.998 per round except for FedDyn we use 0.999. We train 500 rounds on CIFAR-10 and 800 rounds on CIFAR- 100 to achieve stable test accuracy. The participation ratios are selected as 10% and 5% respectively of total 100 and 200 clients. More details are stated in Appendix B.
8

---

5.1 Experiment results
In this part, we mainly introduce the experiment results compared with the other benchmarks.
In Table 1, our proposed Fedinit method performs well than the other benchmarks with good stability across different experimental setups. On the results of ResNet- 100--888-88 18-GN on CIFAR- 10, it achieves about 3.42% improve- ment than the vanilla FedAvg on the high heterogeneous splitting with
Table 2: We incorporate the relaxed initialization (RI) into the
benchmarks to test improvements on BesNet-18-GN on CIFAR-10 with the same hyperparameters and specific relaxed coefficient B.
10%-100 elients
5%-200 clients
Method
Dir-0.6
Dir-0.1
Dir-0.6
Dir-0.1
+RI
+R1
+RI
+RI
FodAvg
78.77
83.11
72.53
75.95
74.81
80.58
70.65
74.92
D, 0.1. When the participation ratio decreases to 5%, the accuracy drops only about 0.1% 1% while FedArg drops almost 1.88%. Similar results on CIFAR-100, when the ratio de-
FedAdam
76.52
78.33
70.44
72.55
73.28
78.33
68.87
71.34
FedSAM
79.23
83.36
72.89
76.34
75.45
80.66
71.23
75.08
SCAFFOLD
81.37
83.27
75.06
77.30
78.17
81.02
74.24
76.22
FedDyn
82,43
81.91
75.08
75.11
79.96
79.88
74.15
74.34
FedCM
81.67
81.77
73.93
73.71
79.49
79.72
73.12
72.98
creases, FedInit still achieves 43%77% while the second best method SCAFFOLD drops about 3.21%.
This indicates the proposed FedInit holds good stability on the varies of the participation. In addition, in Table 2, we incorporate the relaxed initialization (RI) into the other benchmarks to test its benefit. "_" means the vanilla benchmarks, and "+RI" means adopting the relaxed initialization. It shows that the relaxed initialization holds the promising potential to further enhance the performance. Actually, FedInit could be considered as (RI FedAvg). whose improvement achieves about over 3% on each setup. Table 1 shows the poor performance of the vanilla FedAvg. Nevertheless, when adopting the RI, Fedlnit remains above most benchmarks several setups. When the RI is incorporated into other benchmarks, it helps them to achieve higher performance without additional communication costs.
5.2 Ablation
In this part, we mainly introduce the ablation results of different hyperparameters.
Hyperparameters Sensitivity. The excess risk and test error of FedInit indicate there exists best selections for local interval K and relaxed co-
Performance of diffeentt
Porformance of dfferent 5
efficient 3, respectively. In this part, test series of selections to validate our conclusions. To be aligned with previous studies, we denote K as training epochs. In Figure I (a), we can see that the selection range of the beta very small while it has great potential to improve per- formance. When it is larger than the threshold, the training process will diverge quickly. As lo- cal interval K increases, test accuracy rises first and then decreases. Our analysis provides a clear explanation of the phenomenon. The optimization error decreases as K increases when it is small. When K exceeds the threshold, the divergence term in generalization cannot be ignored. Therefore, the test accuracy will be significantly affected.
200
+ Dromss-2
Iocalintarvar
relaxed coofTicent F
(a) Different K.
(b) Different 3.
Figure 1: THyperparameters sensitivity studies of lo- cal intervals K and relaxed coefficient & of Fedlnit method on CIFAR-10. 10. To fairly compare their efficiency, we fix the total communication rounds T = 500.
Consistency. In this part, we test the relationship between the test accuracy and divergence term A under differ- ent 33 selections. As introduced in Al- gorithm 1 Line.6, negative means to adopt the relaxed initialization which close the latest local model. Fe- dinit degrades to FedAvg when 3 0. Table 3 validates that RI required to be far away from the local model (a positive 3). When 9 is small, the correction is limited. The local divergence term difficult to be diminished efficiently. While it becomes too large, the local training begins from bad initialization, which can not receive enough guidance of global information from the global models. Furthermore, as shown in Table 3, if the initialization is too far from the local model, the quality of the initialization state will not be effectively guaranteed.
Table 3:
We test different selections of the relaxed coefficient 8 of the FedInit method CIFAR-10 10%- 100 Dir-0.1 splitting to validate the relationship between test error and consistency after 500 rounds. We fix other hyperparameters as the same selection above for a fair comparison.
3 -0.2
-0.1
0
0.01
0.02
0.05
0.1
0.15
Accuracy (%)
64.70
67.47
72.53
72.82
73.45
74.65
75.95
44.47
A" 0.873
0.815
0.855
0.875
0.850
0.823
0.760
9

---

5.3 Discussions of Relaxed Initialization
In this part, we mainly discuss the improvements of the proposed relaxed initialization.
In vanilla classical FedAvg and the most advanced methods, at the beginning of each communication round, are always caught in misunderstanding of the high consistency. Because the target of FL a globally consistent solution, it is always an involuntary aggregation in the algorithm to ensure consistency. We prove that this does contribute the efficiency of the optimization process, but it is not the best selection for generalization. To better improve the generalization, we prove that a relaxed initialization state will contribute more. We compare their difference in Figure 5.3.
global model w(t)
global model w(t+1)
* local optimum 1
* local optimum 2
global optimum
local relaxed Init. 1
local relaxed Init. 2
FedAvg
Fedinit
Figure 2: Schematics of the classical FedAvg and our proposed FedInit.
As shown in the above figure, we can clearly see why FedInil contributes more to the consistency. When we move little in the opposite direction of the last local optimization state, will move further away from local optimal solutions in the current communication round. The working mode of RI similar the idea of "lookahead". Differently, (1) "lookahead" only works the end of each stage: (2) "lookahead" only works for the global models on the global server. However, RI helps each local client to backtrack small distance at the beginning of each stage. Therefore, after the local training in the next stage, the trained local models will get closer to each other than before.
6 Conclusion
In this work, we propose an efficient and novel FL method, dubbed FedInit, which adopts the stage- wise personalized relaxed initialization enhance the local consistency level. Furthermore, to clearly understand the essential impact of consistency in FL, we introduce the excess risk analysis FL and study the divergence term. Our proofs indicate that consistency dominates the test error and generalization error bound while optimization error is insensitive to it. Extensive experiments are conducted validate the efficiency of relaxed initialization. As practical and light plug in, it could also be easily incorporated into other FL. paradigms to improve their performance.
Limitations & Broader Impact. In this work, we analyze the excess risk for the Fedinit method to understand how consistency works FL. Actually, the relaxed initialization may also work for the personalized FL (pFL) paradigm. It is future study to explore its properties in the pFL and decentralized FL, which may inspire us to design novel efficient algorithms the FL community.
Acknowledgements
Prof. Dacheng Tao is partially supported by Australian Research Council Project FL-170100117.
10

---

References
[1] Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough. and Venkatesh Saligrama. Federated learning based on dynamic regularization. arXiv preprint urXiv:2111.04233,, 2021.
[2] Muhammad Asad, Ahmed Moustafa, and Takayuki Ito, Fedopt: Towards communication efficiency and privacy preservation in federated learning. Applied Sciences, 10(8):2864, 2020.
[3] Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalln margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[4] Debora Caldarola, Barbara Caputo, and Marco Ciccone. Improving generalization in federated leamning by seeking flat minima. In Computer Vision-ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXIII, pages 654-672. Springer, 2022.
[5] Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs federated learning and meta-learning, In International Conference on Artificial Intelligence and Statistics, pages 2575-2583. PMLR, 2021.
[6] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
[7] Farzan Famna, Jesse Zhang, and David Tsc. Generalizable adversarial training via spectral normalization. arXiv preprint arXiv: / 1.07457, 2018.
[8] Liang Gao, Huazhu Fu, Li Li, Yingwen Chen, Ming Xu, and Cheng-Zhong Zhong Xu, Fedde: Federated learning with non-iid data via local drift decoupling and correction. arXiv preprint arXiv:2203. 1751, 2022.
[9] Yonghai Gong, Yichuan Li, and Nikolaos M Freris. Fedadmm: A robust fedcrated deep lcarning framework with adaptivity system heterogeneity, In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2575-2587 IEEE, 2022.
[10] Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 3556-3564. PMIR, 2021.
[11] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[12] 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 pattern recognition, pages 770-778, 2016.
[13] Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In International Conference Machine Learning, pages 4387-4398. PMLR, 2020.
[14] Tzu- Tzu-Ming Harry Hsu, Hang Qi. and Matthew Brown. Measuring the effects of -on-identiaal data distribu- 2019.
tian for federated visual classification, arXiv preprint
[15] Tiansheng Huang, Li Shen, Yan Sun, Weiwei Lin, and Dacheng Tao. Fusion of global and local knowledge for personalized federated lcarning. arXiv preprint arXiv:2302. /055, 2023.
[16] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
[17] 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. Advances and open problems federated learning. Foundations and TrendsS in Machine Learning, 14(1-2):1-210, 2021.
[18] Belhal Karimi, Ping Li, and Xiaoyun Li. wise and dimension- wise locally adaptive federated learning. arXiv preprint arXiv:2110.0052: 2021.
[19] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national Conference Machine Learning, pages 5132-510 5143. PMLR, 2020.
[20] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
11

---

[21] Iiaa Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2815-2824. PMLR, 2018
[22] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429-450, 2020.
[23] Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini- batche, use local sgd. arXiv preprint arXiv: 1808, 17, 2018.
[24] Yixing Liu, Sun, Zhengtao Ding. Li Shen, Bo Liu, and Dacheng Tao. Enhance local consistency in federated learning: A multi-step incrtial momentum approach. arXiv preprint arXiv:2302.05722 2023,
[25] 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, pages 6692-6701. PMLR, 2020.
[26] Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--fficiii learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1282. PMLR, 2017.
[27] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-hayesian approach spectrally- normalized margin bounds for neural networks. arXiv preprint arXiv: (000::777.0000 0.564,944 2017.
[28] Emre Ozfatura, Kerem Ozfatura, and Deniz Gündüz. Fedade: Accelerated federated learning with drift control. 2021 IEEE International Symposium on Information Theory (ISIT), pages 467 667-472. IEEE, 2021.
[29] Zhe Qu, Xingyu Li. Rui Duan, Yao Liu, Bo Tang, and Zhuo Lu. Generalized federated learning via sharpness aware minimization. International Conference on Machine Learning, pages 18280. PMLR, 2022.
[30] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
[31] Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaic. Robust federated learning: The case affine distribution shifts. Advances in Neural Information Processing Systems, 33:21554-2111 -25655, 2020.
[32] Naichen Shi, Fan Lai, Raed Al Kontar, and Mosharaf Chowdhury. Fed-ensemble: Improving generalization through model ensembling in federated learning. arXiv preprint 100.:2000..1666. 2021.
[33] Yifan Shi, Yingqi Liu, Kang Wei, Li Shen, Xueqian Wang, and Dacheng Tao. Make landscape flatter in differentially private federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 24552-24562 2023.
[34] Yifan Shi, Li Shen, Kang Wei, Yan Sun, Bo Yuan, Xueqian Wang, and Dacheng Tao. Improving the model consistency of dccentralized federated lcarning. arXiv preprint arXiv:2302.04000 2023.
[35] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni- tion. arXiv preprint arXiv: (ttl::1409.15050 2014.
[36] Hao Sun, Li Shen, Qihuang Zhong, Liang Ding, Shixiang Chen, Jingwei Sun, Jing Li, Guangzhong Sun, and Dacheng Tao. Adasam: Boosting sharpness-aware minimization with adaptive learning rate and momentum for training deep neural networks. arXiv preprint arXiv:2303.0055: 2023.
[37] Yan Sun, Li Shen, Shixiang Chen, Liang Ding, and Dacheng Tao. Dynamic regularized sharpness aware minimization in federated learning: Approaching global consistency and smooth landscape. arXiv preprint arXiv:2305.1 1184, 2023.
[38] Yan Sun, Li Shen, Tiansheng Huang, Liang Ding, and Dacheng Tao. Fedspeed: Larger local interval, less communication round, and higher generalization accuracy. arXiv preprint arXiv:2.02. 2023.
[39] Yan Sun, Li Shen, Hao Sun, Liang Ding, and Dacheng Tao. Efficient federated learning via local adaptive amended optimizer with linear speedup. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
[40] 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.
12

---

[41] Han Wang, Siddartha Marella, and James Anderson. Fedadmm: A federated primal-dual algorithm allowing partial participation. In 2022 IEEE 61st Conference Decision and Control (CDC), pages 287-294, IEEE, 2022.
[42] Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication- efficient distributed sgd with slow momentum. arXiv preprint arXiv:1910.00443, 2019.
[43] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. sistency problem in heterogeneous federated optimization. Advances neural information processing systems, 33:7611 --223,, 2020.
Tackling the objective incon-
[44] Jianyu Wang. Zheng Xu, Zachary Garrett, Zachary Charles, Luyang Liu, Gauri Joshi. Local adaptivity in federated learning: Convergence and consistency. arXiv preprint arXiv:2106.02500 2021.
[45] Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281 6222, 2020.
[46] Jing Xu, Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2 10874, 2021.
[47] Semih Yagli, Alex Dytso, and Vincent Poor. Information-theoree bounds on the generalization error and privacy leakage in federated learning. In 2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pages 1-5, IEEE, 2020.
[48] Haibo Yang. Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11203 2021.
[49] 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-60700 6070, 2021.
[50] Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability of sgd: Tightness analysis and improved bounds. In Uncertainty in Artificial Intelligence, pages 2364-2377 (373. PMLR, 2022.
[51] Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan. Towards understanding why lookahead generalizes better than sgd and beyond. Advances in Neural Information Processing Systems, 34:27290 27304, 2021.
[52] Shenglong Zhou and Geoffrey Ye Li. Federated learning via inexact admm. IEEE Transactions Puttern Analysis and Machine Intelligence, 2023.
13

---

A Proofs
In this section, introduce proofs of the main theorems in the main context, In the first part, we introduce assumptions used in proofs and point out their functions used for which part. In the second part, prove convergence rate and optimization error under the general assumptions. the third part, we prove uniform stability to measure the generalization error and analyze how each term affects the accuracy.
We suppose there are C' clients participating the training process and cach has a local heterogencous dataset. In cach round t, we randomly select N clients to send the global model and they will train K iterations to get N local models. The local models will be aggregated on the global server the next global model. After T rounds, method generates global model the final state. We denote the total client set and the selected client set as N.
A.1 Assumptions
this part, we state assumptions our proofs and discuss them. We will introduce each assumption and develop their corollaries.
Assumption 6 For Vun, W2 Rdd, the non-convex local function satisfies L-smooth if:
Li[w w2ll,
(19)
where L is a universal constant.
Assumption For Vi IR,, the stochastic gradient is bounded by its expectation and variance as:
E. [oi.]] (f(((()))
(20)
El V((w(,)) so.
where di 0 universal constant.
Assumption 8 For Vo W., the heterogeneous similarity is bounded the gradient as:
[VS[W)) +² BB
(21)
where G 2 0 and B 2 1 are two universal constants.
Assumption 9 For Van, we RR,, the global function I satisfies Le LipLisschitz if:
[l f(w22)l S Ta [pm w2ll:
(22)
where La is a universal constant.
Assumption For Vu E R². let w² E arg min... (w,, the global fanction satisfies PL-condition if:
2p (p( f(w")) [[
(23)
where p a universal positive constant.
Discussion. Assumption are three general assumptions to analyze non-convex objective in FL, which widely used the previous works [15, 18, 19, 30, 36, 44, 46, 48). Assumption is used bound the uniform stability for the non-convex objective, which is used in [11, 51]. Different from the analysis in the margin- based generalization bound [27, 29, 31, 38] that focus understanding how the designed objective affects the final generalization performance, training process.
work focuses understanding how the generalization performance changes consider the entire training process and adopt uniform stability to measure global generality in FL and theoretically study the importance of consistency to FL.. For the general non-convex objective, one often uses the gradient norm E fw)) 1 instead of the loss difference I [f(ww)) - f(:) to measure the training error. To construct and analyze the excess risk to further understand how the consistency affects FL paradigm, we follow [51] to use Assumption 10 to bound loss distance. Through this, we can establish a theoretical framework to jointly analyze the trade-off on the optimization and generalization in the FL. paradigm.
A.2 Proofs for the Optimization Error
In this part, we prove the training error for our proposed method. We assume the objective function f(w) è Exec f((w) is L-smooth w.r. w. Then we could upper bound the training error in the FL. Some useful notations in the proof are introduced in the Table 4.
Then introduce some important lemmas used the proof.
14

---

Table 4: Some abbreviations of the used terms in the proof of bounded training error.
Notation
Formulation
Description
w/ w! V V
parameters at k-th iteration in round & on client i
global parameters in round / averaged norm of the local updates in round norm of the global updates in round t inconsistency/divrreeee term in round f bias between the initialization state and optimal
Eiec Li
El Bllw
w'1l 11
w²| 1.k
Ellut+1
A
δ Eiec [B| Blll,,,K 1-1 w011
D
f(w f(w))
A.2.1
Important Lemmas
Lemma 2 (Bounded local updates) We first bound the local training updates in the local training. Under the Assumptions stated, the averaged norm of the local updates of total C clients could be bounded as:
V S. AK A' + 3K2 (oî +4KG*) + 12 of V f(w" (11
(24)
Proof measures norm of the local offset during the local training stage. could be bounded by two major steps. Firstly, we bound the separated term on the single client i at iteration as:
Eg| w² wi, 11?
Vf(wwl, V(((w') Vf((w)) ll By Iw' wi,k-- + (gi -
1 + 2K -
1
Bellww wiA--1 + +1 (0i V
+ 2K') (
V.i(w') V.fi(''\\'
Eellw² w/. + 1 E+lloia [/((w()-1))1'
2K -
V - Vf((w")) "11a 4K [V
+ 2K -
1
+ 4nj KL² Bellu wii || + no + 4
1+ K
Eellw' wi + 1o 4K Vi
where the learning rate is required 1y I T(K for K 2 2.
Computing the overage of the separated term on client i, have:
1 Σ
E, Blllw'
wl
C
IEC
< 1 K
Br I1o0
wi16-112 +1 + +4K
C Vi(("')]
iEc
Σ
B. Billw' wi,e-11 1r + AK + 4K B"I
K
C
iec
2 (1+ x-1)² s
Unrolling the aggregated term on iteration & < K.
When local interval
(1+ x K
< Then we have:
1
Σ
Ballz0
3
k-1
Σ
1
(1i0) +
K K-1
==0
|+
K 111
1
k
1
Σ
| wi,l
C
TEc
< 3(K -1) 1) (4) of G2 BaK'"
+ 4.8
Σ
Eallo0 - w
C
15

---

I <fK (oi +4KG²) 12K (V7 43
Summing the iteration k = 0,1,
K-1
B. -w:ll' 4K 3K +1 B² BV
C
LEC h-u
This completes the proof.
Lemma (Bounded global updates) The norm of the global update could be bounded by uniformly sampling. Under assumptions stated above, let rj S RT. the norn of the global update of selected clients could be bounded as:
15.9 N
10n² K
3
V/2 -
A
of
G
N
N
(25)
39n/
K2 B
o
EE iEC
N
CN
Proof V2 measures the variance of the global offset after each communication round. We define indicator function levent if the event happens. Then, to bound it, we firstly split the expectation term:
El c+1 - 10
= Fl Σ
1
wii 10'1
EW
E
(wi.x- w))1?
N
B
(wixx - w )EEN!
N
K-1
B
Σ
LiEN
Σ
ngi, B(w'' wiikk) 11
N
SEC
K
Elight
vi(WW())1
Σ
TEN
B(w' wiit) 11?
NC
No
scd
17² Kot
No
Σ
LEN
K-1 (VS((tt)))))
Σ
3(w=
wiix)) 1??
N
iec
kk-
To bound the second term, we can adopt the following equation. For the vector as E Rd we have:
B
1eNx,,12 =B(
-B> LEAN
Σ 1GENZ,)
Σ
E(L B(LENE, LeNz,) +
Σ
BiliaN,, (ENZY,)
(KS))EC
(i=jjeC
Σ
E(LEEN LENa,) +
Σ Sallew;,,Jeeea
(KAS)EC
(s-S)EC
N(N 1)
Σ
E(s, C
Σ E(s,,
C(C
(EAS)EC
(imj)EC
N(N 1)
N(C -N)
Σ B(
Σ B(x,,
C(C 1)
C(C-1)
WEE
((=J)EC
N(N - 1)
N(C - N)
E
Σ
Ella;|13.
C(C - 1)
C(C -
We firstly bound the first term in the above equation. Taking x, = ΣK- n/ f. + 3(w0 w(iT)) into
E|| Eieo sx./?, ? we have:
K-1
K-
E
Σ
(((((())) B(w' wi7²)
112 n E Σ
VEC
SEC
k=0
16

---

Then we bound the second term in above equation. Taking Ek=o vV(((()))) + 3(w' -wix) into we have:
Eiec E
K
E
V.((())))))) + +B(w0' -wixk)'
SEC
E
(V + K (w' wx,kk' 1?
K-1
S KK)
(l + K
(w0 -w,x))l
iEC
[l +
+ 3
p (w' 2(w'-wi -w''-w;, ww,
K
K
S 3n 333KK' KL
Bllui,
K²
Σ B|V)(("") 338² IEC
Ell(w' - )1?
REC k=0
SEC
CV:
KL'V, + 3C 3Cn K2 3Cr B² E(V'(("))1
We bound all the components in V/ term. Ler <. N < C, to generate the final bound, sunmarizing the inequalities all above and adopting the bounded VI in Lemma 2, then have:
7
Koł
K--
V S
E
TEEN
Vi(wi)) + B(w' w(ixk) 11?
N
N2
1EC
n Kof
3(C N)
2 KLV + B K² 122 ="
N(C 1)
(N - 1)
1/ 2
CN(C 1)
iec
n
Koo
3/4
3
(B
+ + o (
El
K-1 v(((w()))
N
N
CN
sEC
k=0
3
(4r2
+3K (ot " (1)
N
333
A 12K (1+9K9
3n²
(1+1n
o2
(1 12n 1 121 a²
N
K2B
K
(1 12n K B[VS(W))
E
Σ iEC
Σ
N
CN
k=0
To minimize the coefficients of each term, we can select a constant order for the term 1/² K2 For convenience, we directly select the r²² K3 L < 1 which requires the learning rate S 1
KL. This completes the proof.
Lemma 4 (Bounded divergenec term) The divergence term A' could be upper bounded by the local update rules. According to the relaxed initialization
method, under assumptions stated above, let the learning rate satisfy 1) KL and the relaxed cuefficient satisfy B /2 the divergence term A could be bounded as the recursion of:
A A' A'
1-1
5172K
195n K2 22
195n2K2B
72332
+
oi 7232
-2,32
G²
7232
3n²
K-1
(26)
Σ SEC K=0
CN(1 72,32)
Proof The divergence term measures the inconsistency level the FL framework. According to the local updates, we have the following recursive formula::
K-1
10
[+1
wiik =
(w w +(u w²)
Σ
noine
kma
local bisss be round
local bias round
17

---

By laking the squared norm and expectation on both sides, we have:
K-1
El = w²) + w t1 w² Σ
nglull 11
k=0
S 333 3 1
w0
+-37|]
The second term in the above inequality is V/2 we have bounded in lemma 3. Then we bound the stochastic gradients term. We have:
K-
K-1
EI
Σ
= B]
Σ s
U
- Σ (ol, - (V
V f (((
5T + , K-1
Fl V)((w) + ffiw"')
K-1
1o² + +212K K
ElIVS((w),)) VS(w"))] + 2n
E [(
k=
S Kot + K kT.
Bllwi, - u w0113 112 (
Taking the average client we have:
KT? C
K-1
Ellwi,x - w + 2n
nol.N S Koo
Σ
C
IEC
S Kot 2n 2 + 2,222²2 k² + 21 K2 B² ((
Recalling the condition of n S Rे. and combining this and the squared norm inequality, we have:
1
A
EE 100
+1
xl
C
IEC
K-1 1
S 3,9
A' + +3V +
ngl.ull
iEC
k=
S 3300 (1+
15
+
8n x2 1.2
+ 67/ R22
1+
39
+ 12,22k21
El 2(
N
2N
3n²K' K
+
10
61 r²1
oî + 67 6 k²
1 2N
39
+ 12n
+10p2 R212) 02
N
3n² E
K
f (((
CN
ICC
kmD
7288" A + 5ln
Kop "
1957 K2 + 195 "²² 2= B
3n²
CN
iEC
/22 Let 728 < where 3 thus we add (1 7282) A' on both sides and get the recursive formulation:
(1-7288) s (A' 1t1 + 517 Kof + 1957' x²G² 1957² K² (
3
K-1
E
ΣΣ REC k-d
CN
Then multiply the 1-7232 both sides, which completes the proof.
18

---

A.2.2 Expanding the Smoothness Inequality for the Non-convex Objective
For the non-conve, and L-smooth function f. we firsdy expand the smoothness inequality at round as:
B Bl f(("")
L
<E(SS(w"), w²)
11
2
V2
1 = =E(V)(w")
Σ wf,x w²' + LV1
N
EEN
[wvi - who) + -,(00' - -w(,k) LV
iEC
1
LV2
Σ
V(((w') + (V](w")) +
C
2
IEC k=0
iEC k=0
-->KB]
11
R-1 -V((m') 2
LV2
iEC k=0
S
2
20
IEC K=
71
El
K-1
((( +
LVV
2C'K
2
85C k=0
<
nK B[s(w")1 + nL?
Σ Σ
K-1
Bllw²
wi.al?
El
V f((w(()) + LV3
2
2
2C²
iEC k=0
V
< - n Bls(w")| + LL
7
(((W())) +
LV2 2
2
20KK
According Lemma and lemma 3 to bound the V and V2, can get the following recursive formula:
B[f(w(+t)) =[ww))]
Bl]
11
7
E
(
2
2CN
20*K
IEC
A
nL
[1K32''
A +3K2, 1 (of + +AKG2) + 12K 1/ B B
2
L.
2n² A 1L (1+ oi
3r K2L
(1+
(1 + K2 0²
2N
2N
2N
3n²
K2
B2BBL
11
1²) [VV)(''))
2N
v²LL
3
4N
n + (1 (1+ (1+1)²²²13) A:
2CN
202K
2N
KL
3r2² K
[3NKKL + (1 + 2 12T
[ANnKL + (1
2N
2N
n
3nKLB²
(1 12n2 K² K²L²) 12n 2² Bl
2
N
Here we make a comprchensive discussion on the selection of n to simplify the above formula. In fact, in lemma 2, there is a constraint on the learning rate as 77 S I지ū for K 2 2. lemma and lemma 4, there is a constraint on the learning rate as & RZ- To further minimize the coefficient, we select the Nr LL to be constant order. For convenience, we directly select the 7, S NKT. Thus, we have:
Blf(w - f(w')) L
2N (4N)KL+5) A:
12KL 2N
(3N 10)
3r K (AN + 13) C²
2N
19

---

39
-12n 12 BlIf(w")Il
2
N
LL
K-1
E
Σ
Σ
v(((w(a)1
2CN 2C
REC R=O
106² L(A' - A 1
3r² K
1300/²2
K2KLL
1020,32
(1 - 72
2N
- 72,32
+ 17
G²
+
2N
1-7223
+ 13
oî
n22 L
"1
E
CN 7282)
2CN
2C
SEC
k=
nK 2
39
89008"
728")N 12m 212nmK" K Bd
fllf(w"))l
N
Firstly, to remove the gradient term, we follow the [19, 48] and
300
a अ S
(N-(1-7287)
2CN
then learning rate 1 S 2CKL"
N Then, according to the [48], there is positive constant À E (0, () to satisfy
1 39cKLB" 390005 "LL (2-7252)
2 >> We denote Ka
13005
+17 and K2 1-72 +1
10205
1-725a
constants the formula. Therefore, have:
Knk
2 B1
3 K2L C² S [if(w') - fw (1-7232)N (A' -1+1)
10
22n2 KL
2N oi.
A.2.3 Proof of Theorem
Theorem 7 Under Assumption 6--8, let participation ratio is N/C where 1 < N < C. let the learning rate
satisfy S min { N ZCKI WKL } where K. 2 2, let the relaxation coefficient S 12
J3 and after training T
rounds, the global model w² generated by Fedlnit satisfies:
2 (f((w") ) f(ww))
R2nL of + AN
361KKL G².
Σ
(27)
T
Ank
AN
where X (0, K1 1300s
17, and K2
1020,²
72p2
13 three constants.
Further, by selecting the proper learning rate 1j = O(v KT
and let f(w) - f(== as the initialization
bias, the global model wi satisfies:
T-1 Σ
D D (oF +op +3KG9)
(28)
VNKT
1=0
Proof According to the expansion of the smoothness inequality, we have:
Ank
2 Elf(w"))1
10
38 KLL
K2ni KL
< ff(((') - f(w )}] + [1 72,3)
(A' )++1+
G² +
2N oi.
2N
Taking the accumulation from 0 to T 1, we have:
(llf(w")) (1
2E[ - f(wF)]
20 L
(A -A7)+
KanL
of +
3RnnKL 62
AnKT
(1 D27
AN
AN
(f((w)) - f(w*))
NanT. of 3RITKL G².
AnKT
AN
XN
We select the learning rate 1j = O(v
and let D = f(w") ) - (ww") ) as the initialization bias, then we have:
KT
B] ( D [ +o2++KK3) +3KG
T 1-0
VNKT
This completes the proof.
20

---

A.2.4 Proof of Theorem 2
Theorem 8 Under Assumption 6--8 and 10, let participation ratio is N/C where 1 < N < C. let the learning
rate satisfy y S min { N
ZCKL: NKL. xpk where K 2 2, let the relaxation coefficient 3 S 12'
1/2
and after
training rounds, the global model w² generated by FedInit satisfies:
Blf(w") f(w")((w))))))")) S -
AunkT [BI(w") - f((w"(())) []=""]+
3L
G² 2N
Kan1. oi. 2N
(29)
Further, by selecting the proper learning rate n = initialization biax, the global model w' satisfies:
loK(uNKT) AUKT
and let D f(w0) - f(w)) as the
D ( Lio KG
Blf(w") - [w=)][
(30)
NKT
Proof According to the expansion of the smoothness inequality, we have:
An B1
2
S [Bf((w) - f(w [(w + (1 (1-723 (A A 3 G²
10
N2n
2N oi.
According to Assumption 10, we have 2u([(w) f(w")) - [Vʃ(w) 12 we have:
XunKB[/(w") f(w")] Ank [ (u')l
2
S <Ef((w') - ((w++1) + 10,5L
7232)N (A' A 3k21 K22 C² +
K2n KL
2N oi.
Combining the terms aligned with w' and +1 we have:
Elf +1 f(ww))
1053L L
3x, K2
N2T KL
< (1 AunK) f(w"),
(1 72-3) (A'- A
G²
2N
2N
Taking the recursion from t
0 T - and let learning rate S
Auk we have:
Elf(w²) -(w"))
T-1
10
$ (1 \unk)" (((](((w)())) +]+
Σ
(A -1t11
(1-7233)
1=0
3k19 K 1
K2n
+
02+ +
of
(1 A1mNK)-11 T-1-t
2N
2N
103
(1 \unK)²
E[f(w") A
[(w"]]+
(A A7)
(1 7232)N
381 L G²
K2n KL
1 - (1 (NTRK)
of
2N
ApnK
< (mfK)"E([(w)) f(w"))
3RgnKL
C²
R2nL o
2N
2N
Se Air "lf(w") s(w")] + 3L G²
o.
2N
2.N AN
We select the learning rate O (og(ANNATT AUKT
and let D f(wo² f(w²) as the initialization bias, then
we have:
-((w")-((e)) =0 (D+ L -0 KG
NKT
This completes the proof.
A.2.5 Proof of Theorem 4
Theorem 9 Under Assumption 6r~8, we can bound the divergence term as follows. Let the learning rate satisfy S min
N
JN where K 2 2, and after training T rounds, let 0 < 8 < 28 the divergence
2CKL
NKL: VCKL
21'
21

---

lerm A' generated by Fedlnit sutisfies:
N(o7 KKG T -
T-1
VNKB DD+ Lio7 + KG
(31)
T
1
t=0
Proof According to Lemma 4, we have:
A 1+1
72,8 A + 511/ K + k2 + 195n K² B
3m
CN
Here we further bound the gradient term, we have:
E
Σ
(VS((())) -Vli('))) + +Vi(w")) |?
REC
=B
(VA(wL))- VV(("')))((((())) ||
SEC k=D
$ CKK Σ
BIV V/((''++++
R-1
2CK
FEC k=n
$ 2C KL + 2C K =|
Combining this into the recursive formulation, and let the learning rate satisfy 11
VN VOKL'
we have:
1" A 1+1 I gd 72 2
195 + 720 =20TT"2=1" 1"
A'
d'+
B Bl
N
N
+ 1 K K +1+ 18C12 K2
195 + T2Cn2K3LL'
of + 1/ k2
N
< 969 A' 267n)* B"B" E (w III + 69rj Koū + 267n G²
JB Let 96,8 < the decayed coefficient where 3 similar Lemma 4, we have:
2677' K2 B²
69n² K 96932
267m² k²
of
G².
9633
1 9632
96.3
by taking the accumulation from 0 1,
T
A
A
69722K K
26772K² K2
G 267 K2 B²
T-1
A
+
96,32 of
Σ
[V
T 1=0
96,
1- 96,22
1 96,92 T
26717 K2
2 (f(wn) - -f(w"))
KanL +
of + 3RnnLL O² AN
1 96,3
MMKT
AN
69m K
26 K2 G²
96,92 di + 1- 9632
534 B (f(w²) - f(w') ))
267n 3 K2 B²B² w2 B²Bawah 2 + 96.3
801n k3 B² 22²nn
0²
(1 9632 )XI
(1 96,32
6972 K
267m K22
of
G2.
96.32
I 96.3
N The same, the learning rate is selected as Olv and let 96,3 1, thus we have:
and let D = f(w0)) - (w=" as the initialization bias
KT)
-'
T-1
NiO7 KKG
2
D L(o? + KGJ]
T
T
T
t=0
This completes this proof.
22

---

A.2.6 Proof of Theorem 5
Theorem 10 Under Assumption 6--8 and 10, we can bound the divergence term as follows. Let the learning
rate satisfy 1) S min
2CKL' NKL' AnR J where K 2 2, and after training T rounds, let 0 < B < y the
N
21
divergence term AT generated by FedInit satisfies:
AJ ===
D
T + No¹ + KG
+0 NKT
(32)
NKT
Proof According to the Theorem 8, we have:
A ++1 S 96 A' 267T) 2 K2 B'B V f(w" )12 69n Koj 267n/ K2C²
Taking recurxive formulation from = t 1, we have:
T S (96,3)TA2)
+
(96 (2671)² K² B² V ( 69n Kot 267n K² G²
69m"
267n/ G
+ 2671) 2 k² B²
96,32
96
69n/ Ko?
267n/ G²G
267x/² K2 B²
Kann 2
3xnKL G²
0i
+ AN
96,34
96,32
1 96,82
AN
534mBB²
T-1 Σ
10
+
(96
(6-0")-11110
[f(((()) - f(ww
(A A²)
(1 - -2,33)) )
1-0
Ko
267m/
K2G
267
(22 k2
3x1m² K3
- 1 96,92
+
of
+
G2
9683
-1- (
N
N
534nKB*
T-1
(9633)T-1---)
[[((w') f(w")]
According to the Theorem 11, we have:
Elf(w") - f(w")(w)))))))))n Apn " B(f(w")) -(w'))
3
G² K2TL of. 2N
2N
Let 968 <
AAnn thus we have:
534nKB5 1
T-1
(96,32) - B (F((ww) -((("))((ww"
A
26
R22n2 K of N
3min2 K2 )+)
534nK B²
T-1 A E(s(w") [(w")
Σ
(96 (008))-1--- 1-1----
(1
1963))X2
N
1=0
2 (1
K2nl"K of
K² 02
96.3))2P
N
N
534nKB²
(ls(w") f(w' aee -
A
Σ
2Ap
Thus selecting the same learning rate 17 O bias, we have:
(IUB(ANN and let D f(w") f((") the initialization
D+ T
No² KG
T =0=
NKT
NKT
This completes the proof.
23

---

A.3 Proofs for the Generalization Error
In this part, we prove the generalization enror for our proposed method. We assume the objective function is L-smooth and Le-Lipschitz defined in [11, 51]. We follow the uniform stability to upper bound the generalization error in the FL.
We suppose there are C clients participating in the training process a set C (i) Each client has local dataset S, { with total S data sampled from specific unknown distribution D, Now we define re-sampled dataset S, which only differs from the dataset S, the j""th data. We replace the S,, with S,+ and keep other C 1 local dataset, which composes a new set C. From the perspective of total data, C' only differs from the C at -"tth data on the i"-th client. Then, based on these two sets, our method could generate two output models, w' and wt respectively, after t training rounds. We first introduce some notations used in the proof of the generalization error.
Table 5: Some abbreviations of the used terms in the proof of bounded training error.
Notation
Formulation
Description
W
parameters trained with set C parameters trained with set e inconsistenoyyddirreeee term in round t
A'
C Eiec El wl wi
Then we introduce some important lemmas our proofs.
A.3.1 Important Lemmas
Lemma (Lemma 3.11 in [1T]) We follow the definition [11, 51] to upper bound the uniform stability term after each communication round in FL paradigm. Different from their vanilla calculations, FL considers the fimite-sum function on heterogeneous clients. Let non-negative objective is L-smooth and Lipsschhii, After training? II' rounds on C and C. our method generates two models w T+1 and TT+1 respectively. For each data z and every to E 21,2,3,- ... S). we have:
Bil T+ +2)) 1( 12)1 S Uto +
LG
>E [l - T 11
(33)
C iec
Proof Let { denote the event ||w - woo
0 and U sup fww; 2). have:
El[[("++'; - [(=T++;;)))
= P((E)) R [l.fww f( f : + P((E'))
[1((w0+);22 ( - - 15
<R
[11f(wo -f( [(=T++:))1 |c] P((E') sup f(w;
wiz
< LoB
[|I0" T+1 - "h 15 + +UP((5
= LoB
11
Σ
( -fxxill 1 +UP((E)))
6Ee
$ C
Lo
- wTxlll UP((E))
Σ
1
IEC
Before the j -th data i' -th client is sampled, the iterative states identical both C and Č. Let is the index of the first different sampling, if > to, then E = hold for to- Therefore, we have:
P((E)) P((E 03) PG to) to) 5
where j is uniformly selected. This completes the proof.
Lemma (Lemmaa 1.1 in [51]) Different from their calculations, we prove the similar inequalities on f in the stochastic optimization. Let non-negative objective is L-smooth
The local updates satisfy wi,t+ = w n on C and wi,+1 = Wix -mrLx on Č. If at k-th iteration on each round, we sample the same data in C and C, then we have:
B B Wia+ill $ (1 nLlBBllu xl 21Jo.
(34)
24

---

Proof In each round by the triangle inequality and omiiting the same data we have:
E|| wi,,+1l
BlJuii n9:, Wi. -775,
< BlJee,, - wil.ull 1l +nElloi, - Fixll
Bl|we,, wi.ull + r (si. V.fi(w(,))) - (H.. V.i(((),)) + (VS((in)) v((T(N))
< Bl|udi, willl + n - ((((w)x)) nE V (ElVV (
$ (1 nL), Wh,1 || 2n0
V((((N)) & VBllst. Vii(wt)))1 & or. This The final inequality adopts assumptions Ell completes the proof.
Lemma (Lemma 1.2 in [51]) Different from their calculations, we prove the similar inequalities on f in the stochastic optimization. Let non-negative objective f L-smooth and Le- Lipschitt w.rl w. The local updates
satisfy w , wh 199', C and W 1,, W 19 k C. If at k-th teration each round, sample the different data C and Č, then have:
Elluei, - Wheti 11 S B - Wf,all + 2n(or + LG). Proof In each round let by the triangle inequality and denoting the different data as and ž, we have:
(35)
Bl Wi,++1ll
Eljwi, ngsi. wix v
- E| wi,x |l 1BBllss a gi
E| wi,xll ll + =Bllgg. (.(((w),))) Fi. V)(((( +AA V((())
El[w[R wf,, ll 2no + -EEVV fE - ff 2|
El[wi, I 2n( + LG).
final inequality adopts the Lipscccci This completes the proof.
A.3.2 Bounded Uniform Stability
According to Lemma we firstly bound recursive stability on in one round. the sampled data is same, we can adopt Lemma 6. Otherwise, we adopt Lemma 7. Thus we can bound the second term in Lemma 5
as:
B |1li Whr+ []]
P(=) E. |||mi,,+1 wi Il 5. + P(z) E [[ -1, [.
(1 + mL)B [|lwi, - Wi,ell [ 2no + 3/ [1lwi
whAll 11
21La
5
+ (1
5 5/5 nT.
R. [|lwot, - - 1 [|] + 21La
+ 2
s
< (1 - +) ) I||
x |4]
2gLa 21jo1.
At the beginning each round f, FL paradigm will aggregate the last state cach client w according to our method, wi,0 = w² + B(wr"
w. x2)x thus the relationship between them is:
Σ AEC
EllwiO - म6 || (1 31)
Σ Ellw" - w (1
Ellw - w
Σ /
$1+ 01 8)
It could be seen that if we consider the wf. - w as general update step. it is independent to the dataset. Hence, we assume a virtual update between w and wip which could be bounded by the divergence term A' Then we bound the recursive term on t.
We know that before t" + k* = la. no different data is sampled, which is, wf = Wh for V tK + < t" K k" After they become different. Thus, when t" K k" > let learning rate })s be constant
25

---

within each round and 7. then we have:
Σ
|
2L w. 5) <
+ 201
TK Σ tme
np exp
(113))
L
E +
KK
C
5
Iec
K+*
+ (1 + (1+ ScL
Σ exp
>> VA.
We adopt the same learning rate ry { where
R is positive constant, then
1
Σ
R
|
- x111
0
IE0
S 2c
LG
+ t
Σ
TK
{ exp
(11
TK cL
5
1=
K+
(1-3)
1
+ (1 (1+3)) scL
3
exp
cl
Σ
V
1m1*+1
s 2c
LG 8
σi
Σ
TK
exp
((1-
1
cl log
TK
t
[=
K+
+(1+ sct
Σ exp
((1-3)
cL log
TK
VA
5
t
1=1+41
20
Lo to:
(TK)(I-))at
TK Σ
1+(1-
}cL
+ (1 +1+ 3)
Σ
TK
(1-
A
t= Br*K+*
1=
2 (Le +So)
TK KK +
cb
TK ot t
+11+ DeL
VAC
1)
(=(++1
+1
A.3.3 Proof of Theorem 3
Theorem 11 Under the Assumptions 6, 7, 9, and 10, let all conditions above satisfied, we can bound the uniform stability of our proposed Fedhntt as:
[ T+, 2) - f(w -(WT+1: :1]l
U 1422
2( 2 + ST Kob rTez
(1+ (3 sèz
ULTK 22L3 SLGoI)
Itel T
VA.
(36)
S-1
L
Proof According to Lemma 5, we have:
=lIf(w++;;)) :2)
12)1l S Uto
+
Le
>
B
[| [Iwxxx xh
C
Iee
The second term is bounded by uniform stability term as:
1
Σ 15 W
W. [
2 + Soi)
TK
ot.
+ +11 3) Der
Σ
T
(TK)
et.
A
C
(S 11-
tK t** K²
KEC
1=
2 (Lo + Soi)
TK
al
TK
+(1+ 3) FEL
VA.
(S 1IL
[2 +LLGo) (TK))L) UL
riद then t" >
[((8+ UL
riel
Traer ct
Let the tu = K + K*
we have:
1-
El] T+1 +1,2)= f( z)1l
U T
2 + SLoo))
ct (TK)
S-1
UL 2(12 + SLGo)
T
VAa
+ (1 + (8) pez
(TK)
1
T
t=1
26

---

Uf44L S
22 + (Tao))
ULTK 2(L3 SLaoi)
rtot
T
v A
8) गल.
--1
T
This completes this proof.
B
Experiments
In this section, we mainly provide the detailed experimental sctups in paper, including the introduction of the benchmarks, datasct, hyperparameters selections, and adding some more experiments.
B.1 Setups
Dataset. We follow the previous works and select the CIFAR-I0 /100 [20] dataset in our experiments. In the CIFAR-10 dataset, there is total of 50,000 training images and 10,000 test images which contain 10 categories. Each data sample is a color image with a size of 32x In the CIFAR-100 100 datasct, there is also total of 50,000 training images and 10,000 test images. It contains 100 categories of the same size as CIFAR-10. For their limited resolutions, we only use general data augmentations. On each local heterogeneous dataset, we use general normalization on the images with specific mean and variance. For the training process, we randomly crop 32x 32 patch from the vanilla images with a zero padding of 4. For the test process, we use the raw images.
Heterogeneity. We follow Hsu al. [14] to introduce the label imbalance the heterogeneous dataset. According to the Dirichlet distribution, we first generate a specific vector with respect to constant D, to control its variance level. Usually, heterogeneity becomes stronger when D, decreases. Then according to the vector, we sample the images from the training dataset. Here we enable the sampling with replacement to generate the local dataset, which means the local clients may have the same data sample if they are assigned to the same category. This is more related the real scenario. At the same time, it also will lose assume this case is due to the offline devices. This is a common case hecause the FI. has an unreliable network connection across the devices.
data samples, we
Benchmarks. In this paper, we use FedAvg [26], FedAdam [30]. FedSAM [29]. SCAFFOLD [19], FedDyn [1]. and FedCM [46] as the benchmarks. FedAvg propose the general FL paradigm hased on the local SGD method. It allows partial participation training via uniformly selecting subset of local clients. A series of developments followed to improve its performance. FedAdam studies the efficient adaptive optimizer on the global server update, which extends scope the FL paradigm. SCAFFOLD indicates that FL suffers from the client-drift problem which is due to the inconsistency of local optimum. Beyond this, it uses the variance reduction technique to further reduce the divergence across the local clients. To further alleviate, FedDyn studies the primal-dua method via adopting the ADMM solve the problem. The consistency condition works constraint during the optimization. It proves that when the global model converges, the local objectives will be aligned with the global one. FedCM proposes an efficient momentum based method, dubbed client-level momentum. communicates the glohal update as a correction to correct each local update to force the local client updates in a similar direction. It maintains very high consistency via biased correction. Therefore, it relies on accurate global direction estimation. FedSAM considers the generalization performance. Generally, we adopt empirical risk minimization (ERM) to perform the optimization process. While the sharpness- wwwpeess-wwar---miieee minmization (SAM) studies that it could search for a flat loss landscape. Flatness guarantees a higher generalization performance. Though our focus is not the generalization, we theoretically prove that even in the FedAvg method divergence term affects the generalization error bound more than the optimization error bound. From this perspective, inperalizatioo-fffcienee methods may also be connected with consistency guarantees. These are all the SOTA benchmarks in the FL community that concern more on enhancing consistency.
Hyperparameters selection. Here we detail our hyperparameter selection in our experiments. For each splitting, we fix the total communication rounds T, local interval K, and hati-bbtchhsie for all the benchmarks and our proposed FedInit. The other selections are stated as follows.
mcans different selections according to the specific setups.
We fix the most hyperparameters of testing the whole benchmarks for a fair comparison. The other algorithm- specific hyperparameters are subjected to specific cireumstances. The ResNet-18-CG and VGG-11 adopt the same set of selections. Then we show algorithm-speeffic hyperparameters:
Special hyperparameter selections. In the FedAdam method, we test that it is very sensitive the global learning rate, Though we report best selection 0.1, still requires some finetuning based on the dataset and experimental setups. In the FedSAM method, we test is very sensitive to the perturbation learning rate. Usually, it should be selected as 0.1 in most cases. However, in some poor pamplag cases, i.c. low participation ratio, it should be selected as 0.01. In the FedDyn, we test is very sensitive the regularization coefficient.
27

---

Table 6: General hyperparameters introductions.
Dataset
CIFAR-10
best selection
communication round
500
local interval K minibatch
5
50
weight decay
1e-3
local learning
[0.01, 0.1,0.5, 0.5, 1]
0.1
global learning rate lcarning rate decay
[0.01, 0.1, 1.0
1.0/0.1
[0.995, 0.998, 0.9995
0.998
relaxed coefficient &
[0.01, 0.02, 0.05, 0.15
0.1/0.01
Dataset
CIFAR-100
best selection
communication round local interval K
5
minibatch
50
weight decay
le-3 3
local learning rate
[0.01, 0.1, 0.5, 1]
global learning rate
[0.01, 0.1, 1.0
1.0/0.1
lcarning rate decay
[0.998, 0.9995, 0.9998
0.998 0.998/0.9990 90.9999
relaxed coefficient
0.011, 0.02, 0.05, 0.1, 0.15)
Table 7: Algorithm-specifie hyperparameter introductions.
Method
specific hyperparameter
introduction
selection
best selection
FedAdam
glohal learning rate perturbation learning rate regularization coefficient client-level coefficient
adaptive learning rate
[0.01, 0.05, 0.1, 1]
FedSAM
ascent step update
[0.01, 0.1,
0.1
FedDyn
coefficient of prox- prox-term 00.001, 1.01,..01.0.1.1
FedCM
ratios in local updates
[0.05, 0.5, 0.9
Generally, it adopts the regularization coefficient to be 0.1 on CIFAR-I0 and 0,01/0.001 on CIFAR-I00. In FedCM, we select the client-level coefficient as 0.1 which followed by Xu et al. [46] in most cases. However, on the VGG-11 -1 model, it fails to converge with small client-level coefficient.
28

---

B.2 Experiments
B.2.1 Curves
In this section, we show the curves of our results.
1005
communccation Rounds
commun catiuaaaaaiionn Rounds
cammun Rounds
20
communication Rounda
(a) Dir-0.6 10%--00.
(b) Dir-0.1 10%--00.
(c) Dir-0.6 5%-200.
(d)
Dir-0.1 5%--000
Figure 3: Loss on the CIFAR-10 10 dataset.
1050
(a) Dir-0.6 10%-100.
(b) Dir-0.1 10%--00.
(c) Dir-0.6 5%-200.
(d) Dir-O.1 5%-200.
Figure 4: Loss the CIFAR-100 dataset.
105 Scor/cy
105 SCOUTD
Leet
500
20
(a) Dir-0.6 10%-100.
(b) Dir-0.1 10%-100.
(c) Dir-0.6 5%-200.
(d) Dir-0.1 5%-200.
Figure 5: Test accuracy on the CIFAR-10 10 dataset.
100 D1cur10
200
0
100 20
Houndss
20 100
callon Rounds
cammun
communication Rounds
(a) Dir-0.6 10%-100.
(b) Oir-0.1 10%-100.
(c) Dir-0.6 5%-200.
(d) Dir-0.1 5%-200.
Figure 6: Test accuracy on the CIFAR-100 dataset.
To show the stable accuracy curves, the third-party tamoothie.cmm smoother smootherrrre smooth the via the function ConvolutionSann iow.oouttnSSmmoteer @rindo__lenn100 window_type= haaeeiannnnn )) On most setups, our proposed Fedinit achieves the SOTA results. effectively avoids negative impacts from local overfitting.
29

---

B.2.2 Consistency of Different Initialization
In this part, we mainly test the consistency level of different B. The coefficient controls the divergence level of the local initialization states. We select the FedArg and SCAFFOLDD to show the efficiency of the proposed relaxed initialization.
bela-122
tethed
Iethan 235
be
Commanication Rounds
Cammunication Rounds
Communicatin Rounds
Communication Rounds
(a) 0.6 0.6 10%--100 Accuracy and Consistency.
(b) Dir 0.1 5%-200 Accuracy and Consistency.
Figure Experiments of FedAvg on the CIFAR-10 dataset.
Iela-12
tetaedd 62
telbed3
letbon 23s
Ieibo
beth-
Iodame
b
bola-03
bele00.5
Communication Rounds
Communiattio Rounds
Communicatio Rounds
Communication Rounde
(a) Dir 0.6 10%--100 Accuracy and Consistency.
(b) Dir 0.1 5%-200 Accuracy and Consistency.
Figure Experiments of SCAFFOLD on the CIFAR-10 dataset.
These experiments show that the relaxed initialization (RI) effectively reduces the consistency and improves the test accuracy. In all tests, when 3 (green curve), represents the vanilla method without RI. After incorporating the RI, the accuracy achieves at least 2% improvement on each setup.
30

---

B.2.3
Communication, Calculation and Storage Costs
this part, we mainly compare the communication, calculation, and storage costs theoretically and experimen-
tally. By assuming the total model maintain d dimensions, we summarize the costs of benchmarks and our proposed FedIntt as follows:
Table 8: Communication, calculation, and storage costs per communication round.
Method
communication
ratio
gradient calculation
ratio
total storage
ratio
FedAvg
Nd
1x
NKd
1x
Cd
1x
FedAdam
Nd
1x
NKd
1x
Cd
1x
FedSAM
Nd
1x
2NKd
2x
2Cd
2x
SCAFFOLD
2Nd
2x
NKd
1x
3Cd
3x
FedDyn
Nd
1x
NKd
1x
3Cd
3x
FedCM
2Nd
NKd
2Cd
3x
FedInit
Nd
1x
NKd
1x
Cd
1x
where N is the number of participating clients, C is the total number of clients, and K is the local training interval.
Limitations of the benchmarks. From this table, we can see that SCAFFOLD and FedCM both require double communication costs than the vanilla FedAvg. They adopt the correction term (variance reduction and client- level momentum) revise each local iteration. Though this achieves good performance, millions of edge devices the FL paradigm, this may introduce very heavy communication bottleneck. In addition, the FedSAM method considers adopting the local SAM optimizer instead of ERM to approach the flat minimal. However, it requires double gradient calculations per iteration. For the very large model, it brings large calculation cost that not be neglected. SCAFFOLD and FedDyn required store 3x vectors each local devices. This is also limitation the light device, iee. mobiles.
indicate that under
We also test the practical wall-clock on devices. Our experiment environments are stated as follows:
Table 9: Experiment environments.
GPU
CUDA
Driver Version
CUDA Version
Platform
Tesla-V (16GB)
NVIDIA-SMI 470.57.02
470.57.02
11.4
Pytorch-1.12.I
In the following table, we test the wall-clock time cost of each method:
Table 10: Wall-clock time cost (s/round).
FedAvg
FedAdam
FedSAM
SCAFFOLD
FedDyn
FedCM
FedInit
10%-100
19.38 x
23.22
30.23
28.61
23.84
22.63
20.41
ratio
1.19x
1.56x
1.47x
1.23x
1.17
1.05
5%-200
17.50
22.18
24.49
20.61
18.19
16.14
ratio 1x
1.10x
1.40x
1.54x
1.30x
1.15x
1.02x
From this table, due to the different communication costs and calculation costs, the practical wall-clock time different for each method. Generally, FedAvg adopts the local-SGD updates without any additional calculations. FedAdam adopts similar local-SGD updates and adaptive optimizer the global server. FedSAM calculation double gradients, which the main reason being slowest among the benchmarks. SCAFFOLD. FedDyn, and FedCM are required to calculate some additional vectors to correct the local updates. Therefore they need some additional time costs. Our proposed FedInit only adopts an additional initialization calculation, which requires the same costs as FedAvg.
31

---

B.2.4 Training Efficiency: Communication Rounds and Time Costs
In this part, we mainly show the results of the training efficiency. We set the target accuracy and compare their required communication rounds and training time respectively. We test on the ResNet-18 18-GN model with the 10%-100 Dir-0.1 splitting.
Table 11: We train 500 rounds on CIFAR-10 10 and 800 rounds CIFAR-100. "-" means the corresponding method can achieve the target accuracy during the training processes.
CIFAR-10 20%%
CIFAR-I00 (230%)
Method
Round
Time (s)
Round
Time (s)
Speed Ratio
Speed Ratio
Speed Ratio
Speed Ratio
FedAvg
371
1x
7189
1x
191
1x
3701
1x
FedAdam
489
0.76x
11354
0.63x
256
0.74x
5944
0.62x
FedSAM
377
0.98x
11396
0.63x
204
0.93x
6166
0.60x
SCAFFOLD
248
1.50x
7095
1.01
211
0.90
6036
0.61 x
FedDyn
192
1.93x
4577
1.57
122
1.56x
2908
1.27x
FedCM
183
2.02x
4141
1.73x
95
2.01
2149
1.72x
FedInit
172
2.15x
3510
2.04x
132
1.44x
2694
1.37x
The setups test environment are stated Table 9, According to this table, we clearly see that some advanced methods, i.. SCAFFOLD and FedDyn, are efficient on the communication round T. However, due to the additional costs of each training iteration, they must spend more time on the total training. FedIut is a very light and practical method, which only adopts relaxed initialization on the FedAvg method, which makes it be better and even achieves SOTA results.
32


Reviews:
[{"review_id": "lrR1mQyJGK", "reviewer": "Reviewer_qyTU", "summary": "This paper proposes an efficient stage-wise initialization for the federated learning paradigm, named FedInit, which could be extended as a plug-in to several existing methods. It provides the theoretical analysis on both the convergence and generalization to illustrate how consistency term affects the FL. Experiments also show its efficiency in practical scenarios.", "questions": "Please see the weaknesses.", "limitations": "Please see the weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. FedInit is a light and nimble technique that does not introduce extra communication costs in the FL framework. Compared with other algorithms, FedInit can almost achieve the same performance as SOTA algorithms while maintaining the same communication cost as the vanilla FedAvg. And, Relaxed initialization (RI) could be easily extended into other advanced algorithms as a plug-in and efficiently improve their performance.\n\n2. This paper explores the impacts of global consistency constraints in FL, which is an essential and interesting problem in federated learning. It also indicates the relationships between generalization and optimization.\n\n3. This paper provides a theoretical analysis of the excess risk to comprehensively explain how the dominant factors affect the final performance (test accuracy) throughout the training process. Ablation studies are conducted to validate the conclusion of the theoretical analysis on the hyperparameters, i.e. local interval $K$, coefficient of RI $\\beta$.\n", "weaknesses": "1. The relaxed initialization (RI) looks like an extrapolation algorithm between the global model and the local models as $w+\\beta(w-w_i)$. Several methods including the benchmarks of this paper, i.e. FedProx, and FedCM, are accustomed to applying interpolation methods to adjust local training to make the entire heterogeneous training smoother. So what is their essential difference? I think the author should add a paragraph to discuss it.\n\n2. This paper involves a lot of analytical proofs, so I suggest that the author write a simple proof sketch for each sub-sections to facilitate reading.\n\n3. In Table.2, RI helps to largely improve the performance of FedSAM and SCAFFOLD but shows limited help for FedCM and FedDyn. What is the main reason for this phenomenon? Does it imply that RI is subject to some existing algorithms? I think the author should add a paragraph to discuss it.\n\n4. Some typos (for example):\n(1) Line.150 \"... ... its generality\"\n\n(2) Line.79 \"client drift\" and Line.151 \"client-drift\"\n\n(3) Line.192 the sentence is difficult to read\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and affirmation of our work. We'll answer your questions one by one in the following, including some misunderstandings and some essential academic questions worth exploring. We are also very honored to share some of our understandings with you.\n\n## About the question \"What is the essential difference between the extrapolation and interpolation in relaxed initialization (RI)?\":\n\nAlthough they look alike, they have completely opposite effects in relaxed initialization. Here we can express these two formations in a unified form as $w_{init}=w+\\beta(w-w_i)$, where $\\beta\\geq 0$ means extrapolation and $\\beta < 0$ means interpolation. When we review the inconsistency due to local updates on the heterogeneous dataset, it means each local client is always optimized to achieve its local optimum. From this perspective, each optimized $w_{i}$ is always close to the local optimum.\n\nTherefore, if we select the interpolation method ($\\beta < 0$), from the above formulation, the local initialization state will get close to the local optimum than the vanilla global state, which means each local state overfits more on the local dataset than before. It will introduce a larger inconsistency. However, if we use the extrapolation, it means the local initial state will get far away from the local optimum than the vanilla global state. Since this initialization is used as compensation, the local state obtained after the next stage of training will also get close to each other. We also theoretically prove that using a small positive $\\beta$ could reduce the constant part of the generalization error bound. That's why we use extrapolation as our proposed RI calculation.\n\nWe also test these experiments in the paper. In Table.3 (Line.348) in our paper,\n|  $\\beta$   | -0.2  |  -0.1  |  0 (FedAvg)  |  0.01  |  0.02  |  0.05  |  0.1  |  0.15  |\n|  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |\n|  Accuracy   |  64.70   |  67.47  |  72.53   |  72.82  |  73.45   |  74.65  |  **75.95**   |  44.47  |\n\nUsing a positive $\\beta$ is better.\n\n\n## About the question \"I suggest that the author write a simple proof sketch for each sub-sections to facilitate reading.\":\n\nThank you for pointing out this. Due to space limitations, we delete the original proof sketch in the submission version. We will add some proof sketches in the next version to further clarify our proof process.\n\n\n## About the question \"What is the main reason that RI shows different performance on different methods?\"\n\nThe proxy-based methods may not be improved by RI. Because they utilize a proxy term $\\Vert w - w_{Init}\\Vert^2$ in the local objectives at each communication round, which are sensitive to the initialization state. For instance, FedDyn [1] uses a dynamic regularization term to correct the local objective constantly, which could achieve the same objective for different clients. It is a variant of ADMM which controls the dual variables. Due to the impact of the dual variable, if we directly use the relaxed initial state, the vanilla dual variable will not match the proxy term. In other words, it requires a more specific study on this ADMM-type method in FL. FedCM [2] uses the global update as a biased correction to update the local training, which has achieved a very high consistency. That is why the performance of the (RI + FedCM) is weak. The promotion for enhancing the consistency of FedCM from RI is limited by the correction term.   \n\n[1] Federated Learning Based on Dynamic Regularization\n\n[2] FedCM: Federated Learning with Client-level Momentum\n\n\n\n## About the question of \"Some typos\":\n\nLine.150, we will fix it as \"its generalization performance\".\n\nLine.151, we will fix it as \"client drift\".\n\nLine.192, this sentence says that $G$ controls the heterogeneity level, and the local interval $K$ is limited by the $G$.\n\n\n\n### It is a pleasure to discuss this with you, which will help us to improve this work further. We explain and prove the concerns mentioned in the reviews. If there are any questions, we are happy to continue the discussion with you. Thank you again for reading this rebuttal."}, {"review_id": "ndFQ5VqKd3", "reviewer": "Reviewer_9rh8", "summary": "This paper aims to solve the “client-drift” problem in Federated Learning, which is caused by the NonIID data. Specifically, this paper proposes initializing the local model of each client with its personalized model to alleviate the problem. Further, the paper theoretically analyzes the impact of inconsistency on the convergence of FL. Besides, extensive experiments also demonstrate the effectiveness of the proposed method.", "questions": "See above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe idea of initializing the local model for solving the NonIID problem is interesting.\n2.\tThe theoretical analysis for the proposed method is solid. \n3.\tThe experimental results demonstrate the effectiveness of the proposed method.\n", "weaknesses": "1.\tAlthough the theoretical results are sufficient to verify the convergence of the proposed method, they cannot present the effectiveness of the initialization strategy in principle. More specifically, how does the proposed method reduce the divergence term compared to the vanilla FedAvg?\n\n2.\tThe workflow of the proposed method seems not correct. Are the locations of line 10 and line 12 placed correctly?\n\n3.\tHow to obtain the value of $w_{i,k}^{t-1}$ is not clear. The client may not participate in the previous round $t-1$ under the setting of random client selection. If the local model $w_{i,k}^{t’-1}$ is obtained in many previous rounds, the motivation of bias correction using $ w_{i,k}^{t’-1} - w^{t-1}$ is not reasonable due to the significant gap between $t’$ and $t$.\n\n4.\tThe key hyperparameter K is set inappropriately. In typical FL literature, the number of local epochs is usually set to range from $5$, $10$, and up to $20$, which may contain many local iterations (mini-batches). However, the experiment of this paper only adopts a small number of local iterations instead of local epochs, e.g., 5 local iterations in Table 1, which seems manually adjusted.\n\n5.\tIt would be better if there is a figure to illustrate the principles of the proposed method.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and affirmation of our work. We'll answer your questions one by one in the following, including some misunderstandings and some essential academic questions worth exploring. We are also very honored to share some of our understandings with you.\n\n\n## About the question of \"theoretical results cannot present the effectiveness of the initialization strategy in principle\":\n\nThank you for pointing out this. We discuss our theoretical analysis in each subsection of Section 4 and our theoretical analysis comprehensively explains why FedInit works better than vanilla FedAvg. \n\nOur paper mainly explores the performance of the consistency term in FL to understand how it affects each term. The proposed FedInit method could be considered as a method that adopts a local relaxed initialization on the FedAvg. From the perspective of optimization, under this perturbation, we prove that the order of the convergence rate will not be affected by this perturbation (Thm 1 & 2).\n\nIn section 4.3.4, thm.6 indicates that the consistency term mainly affects the generalization rather than optimization in the excess risk. When we consider the PL-condition, the optimization error achieves $\\mathcal{O}(1/T)$ and the generalization error achieves $\\mathcal{O}(1/T^{\\frac{1}{1+cL}})$. The dominant term comes from the consistency term. Therefore, our proof reveals that the consistency term affects the generalization more than the optimization in the vanilla FedAvg method. In Thm.6, we discuss the minimization in the paragraph \"Selection of $\\beta$\". The constant part of the dominant term (related to $\\beta$) is $\\frac{(1+\\beta)^{\\frac{1}{\\beta cL}}}{\\sqrt{1-96\\beta^2}}$ (Line.287) where $0<\\beta<\\frac{\\sqrt{6}}{24}$. It can be easily verified that when $\\beta$ is selected as a specific positive number the constant term achieves the minimal. This value is less than the limit value of the constant term when $\\beta$ approaches 0.\n\nIn summary, our proofs mainly indicate:\n\n(1) (**Consistency term mainly affects generalization in FL.**) From the perspective of excess risk (sometimes it could be considered as the test error), the consistency term mainly affects the generalization and dominates the excess risk.\n\n(2) (**Relaxed initialization works better.**) From the excess risk perspective, Selecting a small positive $\\beta$ works better than vanilla FedAvg theoretically, which could minimize the constant part in the dominant term. Both experiments and theoretical analysis could validate the efficiency of relaxed initialization.\n\n\n## About the question \"The workflow of the proposed method seems not correct.\":\n\nThank you very much and we are sorry for this mistake. Line.10 should be moved outside the inner loop. After local training, it sends the optimized local state to the global server. And, Line.12 should be moved outside the middle loop. It aggregates the global model after the selected local clients send their local models to the global server. We will fix it.\n\n\n## About the question of \"How to obtain the value of $w_{i,K}^{t-1}$ is not clear.\":\n\nThank you very much for pointing out this. Actually at each communication round $t$, if client $i$ is selected to be active, $w_{i,K}^t$ is trained by $K$ steps. If the client $i$ is not selected, $w_{i,K}^t=w_{i,K}^{t-1}$. The same operation could be found in FedDyn [1], it inherits the states of the local clients who do not participate in the training at the current stage.\n\nWhy does it work?\n\nA client may not be selected after many communication rounds, but its last optimized local state still maintains the information of the local minimal. Local training makes each local model close to the local optimum (in most cases, local training could make the local training loss very low). Compared with adopting the current global model as initialization, the effort of the RI is to make the local initialization far away from the local optimum. Therefore, using the historical state is still useful. Though it may not be very accurate, it still works as a correction away from the local optimal solution.\n\nActually, we submit our code in the Supplementary Material. In the experiments, we just use the above policy to train the FedInit and achieve comparable results as many advanced methods. RI also helps many methods achieve higher test accuracy, i.e. SCAFFOLD and FedSAM. It could work as a light plug-in to further improve their performance as shown in Table.2.\n\n[1] Federated Learning Based on Dynamic Regularization (ICLR 2021)\n\n\n## About the question of \"The key hyperparameter K is set inappropriately.\":\n\nWe are sorry for this misunderstanding. **The $K$ in the theoretical analysis means the iteration. But we do 5 local epochs in the training. We will correct it in the next version**. We submit the code in the Supplementary Material and it can be checked there we use 5 local epochs for training.\n\nWe referred to the experimental setups from the baselines in our paper and chose an intermediate value of 5 to fairly compare their performance. We are sorry for this misunderstanding and we will correct the number of $K$ in our paper. We can use $E = 5$ to represent the local epochs in the hyperparameters introduction.\n\n\n## About the question of \"It would be better if there is a figure to illustrate the principles of the proposed method.\":\n\nThank you very much for pointing out this. Since we took up a lot of space in the introduction of theoretical analysis, we did not provide the schematic diagram in the submitted version. We provide a figure in the one-page .pdf file to illustrate the principles.\n\n\n### It is a pleasure to discuss this with you, which will help us to improve this work further. We explain and prove the concerns mentioned in the reviews. If there are any questions, we are happy to continue the discussion with you. Thank you again for reading this rebuttal.\n"}, {"review_id": "LxaHZZg2SJ", "reviewer": "Reviewer_sALG", "summary": "This paper proposes to initialize the local state by moving away from the current global state toward the reverse direction of the latest local state. They demonstrate theoretically and empirically that this revision can help consistency for better performance. The method is also a practical plug-in that could easily to incorporated into other methods.", "questions": "- Does the method also work well for a large number of clients, e.g., 1000?\n- How does participation rate influence performance?", "limitations": "The authors have stated the limitation and future work as pFL.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper goes deeper into how consistency work in FL systems, and provides a simple and effective initialization-based solution.\n- This paper gives a comprehensive theoretical analysis of the problem, which I think is a good contribution.\n- The paper is well-written and easy to follow.\n- Experiment shows good performance.", "weaknesses": "- I understand there might not be enough space for experiments and the focus looks to be theoretical analysis, but it would be better if the authors can give more experimental results for different FL settings, e.g., more clients/datasets, which may help evaluate the method better. For example,  100 clients/10% participation rate and 200 clients/ 5% participation rate can be relatively limited. Maybe can we have a curve for participation rate with the same amount of clients and perhaps a curve for number of clients to see how these FL settings influence the performance?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and affirmation of our work. We'll answer your questions one by one in the following, including some misunderstandings and some essential academic questions worth exploring. We are also very honored to share some of our understandings with you.\n\n\n## About the question \"Does the method also work well for a large number of clients, e.g., 1000?\"\n\nThank you very much for this question. Large-scale training is one of the goals pursued by federated learning. We finish the experiments on a total of 1000 clients and summarize their results in the following table.\n\n#### Total clients=1000, CIFAR-10, Partial-participation=0.01 (10 active clients/round), Communication round=500, Dirichlet-0.1 split\n\nDue to the very large number of clients, each client is provided with 50 training samples only. In order to avoid serious overfitting, we reduce the batchsize from 50 to 25. The other hyperparameters are the same as we mentioned in our paper.\n\n|  Method   | Dirichlet-0.6  |  Dirichlet-0.1  |\n|  :----:   |  :----:   |  :----:   |\n|  FedAvg   |  63.56%   |  58.61%  |\n|  SCAFFOLD |  65.11%   |  60.94%  |\n|  FedInit  |  65.08%   |  60.71%  |\n\nThough we do not adjust the coefficient of the relaxed initialization and just use 0.1, the proposed FedInit could still achieve the comparable test accuracy of the SCAFFOLD method. Due to the time limitations of this rebuttal stage, we will fine-tune this parameter in the final version to find the optimal value. However, the improvements of the relaxed initialization are still strong even on the setup of 1000 clients.\n\n|  Method   | Vanilla  |  + relaxed initialization  |  improvement (value) |\n|  :----:   |  :----:   |  :----:   |  :----:   |\n|  FedAvg   |  58.61%   |  60.71% (FedInit)     |  +2.1%  |\n|  SCAFFOLD |  60.94%   |  61.47%   |  +0.53%   |\n\nThe vanilla FedAvg could be improved by 2% and the vanilla SCAFFOLD could be improved by 0.53% (Dirichlet-0.1). Likewise, we do not finetune $\\beta$ and only select it as 0.1. We believe this improvement will increase further after a simple search. Due to the time limitation, we will complete the entire experiment in the next version.\n\n## About the question of \"How does participation rate influence performance?\":\n\nTo explore the performance of the different participation rates, we do the following experiments. Due to the time limitation, we test the proposed FedInit on two setups.\n\n#### Total clients=100, CIFAR-10, Dirichlet-0.1, Communication round=500\n|            | 5%  |  10%  |  20%  |  30%  |  50%  |\n|  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |\n| Top-1 Accuracy  |  73.16%  |  75.89%  |  76.04%  |  76.33%  |  76.52%  |\n|  Loss (min)  |  0.5832  |  0.4799  |  0.4040  |  0.3854  |  0.3706  |\n\n#### Total clients=1000, CIFAR-10, Dirichlet-0.1, Communication round=500\n|            | 1%  |  2%  |  5%  |  10%  |  \n|  :----:   |  :----:   |  :----:   |  :----:   |  :----:   |\n| Top-1 Accuracy  |  60.61%  |  61.83%  |  62.30%  |  62.12%  |\n|  Loss (min)  |  1.1381  |  1.0839  |  1.0462  |  1.0374  |\n\nThe same as above, to avoid overfitting, we adjust the batchsize to 25 on the setup of 1000 clients. The other hyperparameters are fixed the same as we adopted in our paper. Both experiments validate the influence of changing the participation ratios. When the number of active clients are increasing, the performance achieves better. This also matches the theoretical analysis. One key problem is that we should make sure that the training process does not overfit when adopting larger scale of clients. We show the loss curve in the one-page .pdf file to validate their trends.\n\n### It is a pleasure to discuss this with you, which will help us to improve this work further. We explain and prove the concerns mentioned in the reviews. If there are any questions, we are happy to continue the discussion with you. Thank you again for reading this rebuttal."}, {"review_id": "KCiWPefhGG", "reviewer": "Reviewer_g4w5", "summary": "The manuscript proposes a novel federated learning method to alleviate the negative impact of the \"client drift\" problem and enhance consistency in the FL paradigm. The manuscript also analyzes the intrinsic impact of local consistency on optimization error, test error, and generalization error. Several experiments are conducted to validate the efficiency of the proposed method.", "questions": "1. The manuscript thinks that inconsistent local optima cause \"client drift,\" which results in the inferiority of federated learning (FL) algorithms. The proposed method aims to alleviate this divergence by employing personalized relaxed initialization at the beginning of each round. I have a question: based on my understanding, personalized initialization in each round would lead to greater differences across different clients. So, how does this strategy help alleviate the divergence?\n2. After a brief review of the theoretical analysis, I am uncertain if I correctly understood the proof. In formulas (9) and (14), the upper bounds achieve their minimum when beta=0. If that's the case, why does the personalized relaxation contribute to improving the performance of FL algorithms?", "limitations": "The experiments in the manuscript are not rigorous enough as the hyperparameters for different methods were not tuned. This could potentially lead to an overestimation of the performance of the proposed method.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed method outperforms baseline methods without increasing communication costs and can be easily incorporated into other methods.\n2. The manuscript provides ample theoretical analysis to demonstrate the theoretical bounds of the proposed method.", "weaknesses": "1. The hyperparameters were not tuned for different methods. Since the experiments are highly sensitive to hyperparameter settings, the superiority of the proposed method is likely due to the selection of hyperparameters. Given that the personalized process proposed in the manuscript bears resemblance to the momentum of parameter updates, I suspect that when tuning the learning rate for the baseline method, the baseline method may outperform the proposed method.\n2.  The results shown in Figure 1 suggest that the proposed method is highly sensitive to the choice of beta.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and comments on our work. We'll answer your questions one by one, including some misunderstandings and some essential academic questions. We are also very honored to share some of our understandings with you.\n\n\n## About the question of \"The hyperparameters were not tuned for different methods.\":\n\n**We have finetuned the hyperparameters and all baselines are carefully tuned and compared fairly.** Due to the page limitation, the details are stated on **Line.738 (Table.6)** and **Line.742 (Table.7)** in the **Appendix** and we also submit the code in the Supplementary Material.\n\nWe test all algorithms and select parameters that most algorithms can be trained well to report as the best selection in Table.6, which is also widely used in many previous works. For instance, in [1], they provide the hyperparameters on the page.15 (Appendix) which are similar to ours. In [2], they provide the hyperparameters in Section E.2, which adopt the same learning rate as ours. In [3], they provide the hyperparameters selection in section C.2 and most parameters are the same as ours. Additionally, we also finetuned personalized hyperparameters in Table.7. Moreover, we use the same set of hyperparameters to test the experiments of adding the relaxed initialization as a plug-in to the current methods, i.e. SCAFFOLD and FedSAM, and they also could be improved by the RI, as shown in Table.2. Our proposed RI is not a trick based on the specific hyperparameters selection. It works both theoretically and experimentally. Additional experiments of re-tuning lr are still running and we will reply soon when it is finished.\n\n**We also use the sampling with replacement in the dataset split**. Compared to **sampling without replacement**, our split is more difficult and the performance will drop a lot on all methods. It means one data sample may exist in more local clients. This situation is more realistic because, on large-scale federated clients, the probability of data duplication is very high.\n\n[1] Federated Learning Based on Dynamic Regularization (ICLR 2021)\n\n[2] Generalized Federated Learning via Sharpness Aware Minimization (ICML 2022)\n\n[3] FedCM: Federated Learning with Client-level Momentum\n\n\n## About the question \"The results shown in Figure 1 suggest that the proposed method is highly sensitive to the choice of beta.\":\n\nWe have proven that the coefficient $\\beta$ has a maximum value (see $\\beta$ selection range in Theorem 6). If it exceeds this maximum value, the method may not converge. Figure.1 demonstrates that our proof matches the experiments. In the experiments, we suggest selecting this coefficient as a small positive value, i.e. 0.05, 0.1. It could be seen in Figure.1, it is very stable in its valid range.\n\n\n## About the question \"I have a question: based on my understanding, personalized initialization would lead to greater differences across different clients. So, how does this strategy help alleviate the divergence?\":\n\nOur motivation is that if the current initialization is farther away from the local optimal solution than the global server model, then after the local training is finished it will also be farther away from the local optimal solution than before. To implement this, we propose relaxed initialization (RI). The working mode of RI is similar to the idea of \"​​lookahead\". Differently, (1) \"​​lookahead\" only works at the end of each stage; (2) \"​​lookahead\" only works for the global models on the global server. However, RI helps each local client to backtrack a small distance at the beginning of each stage. Therefore, after the local training in the next stage, the trained local model will get close to each other than before. We provide a figure to illustrate the principles of the relaxed initialization in the one-page .pdf file.\n\n\n## About the question of \"In formulas (9) and (14), the upper bounds achieve their minimum when beta=0.\":\nFormulas (9) and (14) are not the final conclusion. We aim to find the best selection for the excess risk instead of the optimization only. Here we briefly introduce the final conclusion in section 4.3.4 (formula (18)).\n\nWe combine the Theorem.2, 3, 5 and bound the excess risk as:\n$$\n\\mathcal{E}_E\\leq \\widetilde{\\mathcal{O}}\\left(\\frac{D+L(\\sigma_l^2 + KG^2)}{NKT}\\right) + \\mathcal{O}\\left(\\frac{1}{S}\\left[\\sigma_l(TK)^{cL}\\right]^\\frac{1}{1+cL}\\right) + \\widetilde{\\mathcal{O}}\\left(\\frac{\\sqrt{D+G^2}K^\\frac{cL}{1+cL}}{T^\\frac{1}{1+cL}}\\right).\n$$\n\nFormula (9) only indicates the optimization bias term. Formula (14) indicates the latter two terms as the generalization bias. Because the constant part in the convergence term $\\Delta^t$ also contains $\\beta$, formula (14) is not the final version. In above upper bound, it contains three main parts. The first part is the optimization error, the second part is the stability bias which is related to the total number of samples, and the dominant part is the divergence bias which comes from the consistency term. Here we omit the constant part on the above formula. **In the paragraph \"Selection of $\\beta$\" (Line.284)**, we discuss it in detail. The constant part of the dominant term (related to $\\beta$) is $\\frac{(1+\\beta)^{\\frac{1}{\\beta cL}}}{\\sqrt{1-96\\beta^2}}$ (Line.287) where $0<\\beta<\\frac{\\sqrt{6}}{24}$. It can be easily verified that when $\\beta$ is selected as a specific positive number the constant term achieves the minimal.\n\nWe summarize them as follows:\n\n(1) $\\beta=0$ only helps to minimize the optimization error.\n\n(2) It is a trade-off between optimization and excess risk.\n\n(3) To minimize the dominant term of the excess risk, $\\beta$ should be selected as a small positive number instead of 0.\n\n### It is a pleasure to discuss this with you, which will help us to improve this work further. We explain and prove the concerns mentioned in the reviews. If there are any questions, we are happy to continue the discussion with you. Thank you again for reading this rebuttal."}]

Author rebuttal:
**We are very grateful to all the reviewers for their valuable comments.**

We make individual responses to each reviewer to address the concerns they raised. Here we submit the one-page .pdf file which contains some experiment curves mentioned by review sALG and a figure to illustrate the principle of the proposed relaxed initialization technique which is mentioned by review 9rh8 and g4w5. Thanks again for the valuable comments of the reviewers.

Meta-review: The authors have developed a stage-wise relaxed initialization-based federated learning algorithm. In this approach, the local model at the start of each local training stage is initialized by moving away from the current global model in the opposite direction. This algorithm aims to address the challenge of client drift. When the initialization parameter $\beta$ is sufficiently small, the authors show that the proposed algorithm can discover stationary points or global optimal solutions for federated learning problems when the loss function is nonconvex or satisfies the PL condition, respectively. They have also conducted an analysis of the uniform stability and excess risk of this algorithm.

The theoretical analysis is straightforward, albeit with strong assumptions about the Lipschitz continuity of the loss function. Also,  it is worth noting that the paper does not mention communication efficiency.

All reviewers have provided positive feedback on the quality of this work, and most of them acknowledged authors' responses. Additionally, there were no responses to my initiated discussions during the AC-reviewer discussion phase. Based on my evaluation, it appears to be a borderline work.
Decision: Accept (poster)