Conceptio › Archive › arXiv CS

arXiv CSopen access

Rethinking the Personalized Relaxed Initialization in the Federated Learning: Consistency and Generalization

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Rethinking the Personalized Relaxed Initialization

Rethinking the Personalized Relaxed Initialization in the Federated Learning: Consistency and Generalization Li Shen

[email protected]

School of Cyber Science and Technology Shenzhen Campus of Sun Yat-sen University

arXiv:2604.12768v1 [cs.LG] 14 Apr 2026

Yan Sun

[email protected]

School of Computer Science Faculty of Engineering The University of Sydney

Dacheng Tao

[email protected]

Generative AI Lab College of Computing and Data Science Nanyang Technological University

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 “client drift” and explore its substance in FL, in this paper, we first propose 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. 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 in FL. Our studies show that optimization error is not sensitive to this local inconsistency, while it mainly affects the generalization error bound. Extensive experiments are conducted to validate its efficiency. The proposed FedInit method could achieve comparable results compared to several advanced benchmarks without any additional training or communication costs. Meanwhile, the stage-wise personalized relaxed initialization could also be incorporated into several current advanced algorithms to achieve higher generalization performance in the FL paradigm. Keywords: Federated learning, personalized relaxed initialization, excess risk.

1 Introduction Since McMahan et al. (2017) developed federated learning (FL), it has become a promising paradigm to effectively make full use of edged computational powers of local devices. Kairouz et al. (2021) further classify the different modes in FL based on the specific tasks and unique environmental setups. Different from centralized training, FL utilizes a central server to coordinate the clients to perform several local training stages and aggregate local models as one global model regularly. This creative training framework greatly improves the effective use of edged devices. However, it also has unavoidable disadvantages. Due to the 1

Rethinking the Personalized Relaxed Initialization

local heterogeneous dataset, it usually suffers from the significant performance degradation. Several previous studies explore the essence of performance limitations and inherent biases in FL, and summarize them as the “client-drift” problems (Acar et al., 2021; Karimireddy et al., 2020; Li et al., 2020; Sun et al., 2023c; Wang et al., 2021; Xu et al., 2021; Yang et al., 2021). From the global objective perspective, Karimireddy et al. (2020) claim that the aggregated local optimum is always far away from Pthe global optimum due to the local heterogeneity, which introduces the issue of w⋆ ̸= C1 i wi⋆ in FL. However, when the local training iterations are limited, local clients could not exactly achieve their local optimum. To describe this negative impact more accurately, Acar et al. (2021) and Wang et al. (2021) point out that each locally optimized objective should be regularized to be aligned with the global objective. Moreover, beyond the requirement of the local consistent objectives, Xu et al. (2021) also indicates that the performance degradation could be mitigated when each local updates maintain high consistency at each communication round, which is more similar to the centralized scenarios. These explorations intuitively provide the forward-looking insights of improving the performance in FL. Although this analysis explains the inherent biases across local heterogeneous datasets, there is still no solid theoretical support to further understand the incomprehensible impact of the consistency, which also greatly hinders its developments. Therefore, our work tries to provide a new perspective on consistency. Motivation. From the training strategies, the largest difference between FL and general centralized training is to adopt local training processes, which results in local clients tilt towards the local optimum. We spontaneously and naturally expect to add an inverse effect in the local training process to correct the deviation. Several previous studies have introduced more variables, which has caused great pressure on communication bottlenecks. To further alleviate the negative impact of the “client-drift” problem and strengthen consistency in the FL paradigm without any additional communication burdens, in this paper, we take into account adopting the personalized relaxed initialization at the beginning of each communication round, dubbed FedInit method. Specifically, FedInit initializes each local models of active clients by moving away from the current global state towards the reverse direction of the current latest local state, which is named relaxed initialization (RI). Personalized RI helps each local model to revise its divergence and gather together with each other during the local training process. Because each initialization of the local model is more distant from the local optimum than the global model, locally trained solutions naturally maintain higher consistency under the same local training interval. This flexible approach is surprisingly effective in FL and only adopts one additional coefficient to control the divergence level of the initialization. It could also be easily incorporated as a plug-in into other advanced benchmarks to further improve their efficiency. We also provide a schematic illustration of the effects of this initialization. Moreover, to explicitly understand how and why RI could help to improve the performance in FL, we introduce the excess risk analysis to investigate the test error of FedInit under the smooth non-convex objectives, including the joint analysis on both the optimization error and the generalization error. Our theoretical analysis indicates that both optimization 2

Rethinking the Personalized Relaxed Initialization

error and generalization error could be greatly improved by the RI technique. Furthermore, under PL-condition, RI could efficiently reduce the excess risk and the test error. Extensive empirical studies are conducted to validate the efficiency of the proposed FedInit method on different classical federated experimental setups. On the CIFAR-10/100 dataset, it could achieve SOTA results compared to several advanced benchmarks without additional costs. It also helps to enhance the consistency level in FL. Main contributions of our work are summarized as follows: • We propose an efficient and novel FL method, dubbed FedInit, which adopts the personalized relaxed initialization (RI) state on the selected local clients at each communication round. RI 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 RI could help to improve both the optimization error and generalization error on the smooth and non-convex objectives. • Extensive numerical studies are conducted on the real-world dataset to validate the efficiency of the FedInit method, which could achieve the comparable results of several SOTA benchmarks, without any additional communication costs during the training.

2 Related Work Improving Consistency in FL. FL employs an enormous number of edge devices to jointly train a single model among the isolated heterogeneous dataset (Kairouz et al., 2021; McMahan et al., 2017). As a standard benchmark, FedAvg (Asad et al., 2020; McMahan et al., 2017; Yang et al., 2021) allows the local stochastic gradient descent (local SGD) (Gorbunov et al., 2021; Lin et al., 2018; Woodworth et al., 2020) based updates and uniformly selected partial clients’ participation to alleviate the communication bottleneck. The stagewise local training processes lead to significant divergence for each client (Charles and Konečnỳ, 2021; Malinovskiy et al., 2020; Wang et al., 2020, 2021). To improve the efficiency of the FL paradigm, a series of methods are proposed. Karimireddy et al. (2020) indicate that inconsistent local optimums cause the severe “client drift” problem and propose the SCAFFOLD method which adopts the variance reduction (Defazio et al., 2014; Johnson and Zhang, 2013) technique to mitigate it. Li et al. (2020) penalize the prox-term on the local objectives to force each local update towards both the local optimum and the last global state. Zhang et al. (2021) utilize the primal-dual method to improve consistency via solving local objectives under the equality constraint. Specifically, a series of works further explore and extend the alternating direction method of multipliers (ADMM) to optimize the global objective (Acar et al., 2021; Gong et al., 2022; Wang et al., 2022a; Zhou and Li, 2023; Sun et al., 2024), which could also enhance the consistency term. Beyond these, a series of momentum-based methods are proposed to strengthen local consistency. Wang et al. (2019) study a global momentum update method to stabilize the global model. Further, Gao et al. (2022) adopt the local drift correction via a momentum-based variable 3

Rethinking the Personalized Relaxed Initialization

Table 1: Notation tables. Symbol

Definition

N,N C, C K, k T, t w, w⋆ S, S ∆t O(·) e O(·)

set / number of active clients set / number of total clients number / index of local interval number / index of communication rounds model parameters / optimum parameters local dataset / size of local dataset consistency / divergence term at t-round the order of approximation the order of approximation without Logarithmic term

to revise the local gradients, efficiently reducing inconsistency. Ozfatura et al. (2021); Xu et al. (2021); Sun et al. (2023d) propose a similar client-level momentum to force the local update towards the last global direction. Several variants of client-level momentum methods adopt the inertial momentum to further improve the local consistency level (Liu et al., 2023; Tan et al., 2022). Improving the consistency in FL remains a very important and promising research direction. Though these studies involve a lot of heuristic discussions, exploring and improving local consistency is always one of the essential studies in FL. Generalization Efficiency in FL. Several works have studied the properties of the generalization errors in FL. Based on the margin loss (Bartlett et al., 2017; Farnia et al., 2018; Neyshabur et al., 2017), Reisizadeh et al. (2020) develop a robust FL paradigm to alleviate the distribution shifts across the heterogeneous clients. Shi et al. (2021) study the efficient and stable model technique of model ensembling. Yagli et al. (2020) prove the information-theoretic bounds on the generalization error and privacy leakage in the general FL paradigm. Qu et al. (2022) propose to adopt the sharpness aware minimization (SAM) optimizer on the local client to enhance the flatnesses of the loss landscape. Caldarola et al. (2022); Sun et al. (2023b,c); Shi et al. (2023a,b) propose several variants based on SAM that could achieve higher performance. Beyond the optimizer, Caldarola et al. (2023) further propose a window-based averaging to improve the generalization efficiency in FL. Different from these works, this paper focuses both on the optimization and generalization performance and explores the impact of consistency items in FL.

3 Methodology 3.1 Preliminaries We first introduce the notations in our paper. We use italics for scalars and [·] denotes the integer list within [1, ·]. Unless otherwise specified, all four arithmetic operators conform to element-wise operations. Table 1 shows some special notations. Other symbols are defined when they are first introduced.

Rethinking the Personalized Relaxed Initialization

Following the previous study (Sun et al., 2023e), there are a very large number of local clients to collaboratively train a global model. Due to privacy protection and unreliable network bandwidth, only a fraction of devices are open-accessed at any one time (Kairouz et al., 2021; Qu et al., 2022). Therefore, we define each client stores a private dataset Si = {zj } where zj is drawn from an unknown unique distribution Di . The whole local clients constitute a 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: ( ) X 1 ⋆ wD ∈ arg min F (w) ≜ Fi (w) , (1) w C i∈C

where Fi (w) = Ezj ∼Di Fi (w, zj ) is the local population risk. While in practice, we usually consider the empirical risk minimization of the non-convex finite-sum problem in FL as: ) ( 1 X ⋆ fi (w) , (2) w ∈ arg min f (w) ≜ w C i∈C

1 P

where fi (w) = Si zj ∈Si fi (w; zj ) 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 to improve the efficiency in FL. 3.2 Personalized Relaxed Initialization In this part, we introduce the relaxed initialization in FedInit method. FedAvg proposes the local-SGD-based implementation in the FL paradigm with a partial participation selection. It allows uniformly selecting a subset of clients N to participate in the current training. In each round, it initializes the local model as the last global model. Therefore, after each t−1 − wt is round, the local models are always far away from each other. The local offset wi,K the main culprit leading to inconsistency. Moreover, for different clients, their impacts vary with local heterogeneity. To alleviate this divergence, we propose the FedInit method which adopts the personalized relaxed initialization at the beginning of each round. Concretely, on the selected active clients, it begins the local training from a new personalized state, which moves away from the last global model towards the reverse direction from the latest local state (Line.6 in Algorithm 1). A coefficient β is adopted to control the level of personality. t−1 This offset β(wt − wi,K ) in the relaxed initialization (RI) provides a correction that could help local models gather together after the local training process. Furthermore, this relaxed initialization is irrelevant to the local optimizer, which means, it could be easily incorporated into other methods. Additionally, FedInit does not require extra auxiliary information to communicate between the server and local clients, which indicates it a practical technique.

4 Theoretical Analysis In this section, we first introduce the theoretical analysis which could provide a comprehensive analysis of the joint performance of both optimization and generalization. In the second part, we introduce the main assumptions adopted in our proofs and discuss them 5

Rethinking the Personalized Relaxed Initialization

Algorithm 1 FedInit Method Input: model w, local model wi , T , K, β Output: global parameters wT −1 1: Initialize w −1 = wi,0 = w 0 . 2: for t = 0, 1, 2, · · · , T − 1 do 3: randomly select active clients set N from C 4: for client i ∈ N in parallel do 5: send the wt to the active clients t = w t + β(w t − w t−1 ) 6: set the wi,0 i,K 7: for k = 0, 1, 2, · · · , K − 1 do t 8: compute unbiased stochastic gradient gi,k t t − ηg t 9: wi,k+1 = wi,k i,k 10: end for t 11: communicate wit = wi,K to the server 12: end for 13: for client i ∈ / N in parallel do t−1 t 14: wi,K = wi,K 15: end for P 16: wt+1 = N1 i∈N wit 17: end for in different situations. Then we demonstrate the main theorems in our analysis, including both the optimization and generalization respectively. 4.1 Excess Risk Error Since Karimireddy et al. (2020) indicated that the “client-drift” problem seriously damages the performance in the FL paradigm, many previous works (Huang et al., 2023; Karimi et al., 2021; Karimireddy et al., 2020; Reddi et al., 2020; Sun et al., 2023a; Wang et al., 2021; Xu et al., 2021; Yang et al., 2021) have widely investigated the inefficiency of consistency in the FL paradigm. However, the most of analyses focus on the studies from the onefold perspective of convergence but ignore learning its impact on generality. To further provide a comprehensive studies of the joint performance of both the optimization and generalization in FL, we introduce the well-known excess risk in the analysis. We denote wT as the final model generated by FedInit method after T communication rounds. Compared with f (wT ), we mainly focus on the efficiency of F (wT ) which corresponds to its generalization performance and test accuracy. Thus, we analyze the E[F (wT )] from the excess risk EE as: EE = E[F (wT )] − E[f (w∗ )] = E[F (wT ) − f (wT )] + E[f (wT ) − f (w∗ )] . | {z } | {z } EG : generalization error

EO : optimization error

Generally, the E[f (w∗ )] is expected to be very small and even to zero if the model could fit the dataset. Thus EE could be considered as the joint efficiency of the generated model wT . 6

Rethinking the Personalized Relaxed Initialization

Thereinto, EG means the different performance of wT between the training dataset and the test dataset, and EO means the similarity between wT and optimization optimum w⋆ . From the perspective of the excess risk, εE approximates our focus E[F (wT )]. We investigate the optimization and generalization performance respectively in the following part. At last, we also provide a simple analysis of the divergence term. 4.2 Assumptions In this part, we mainly introduce the assumptions adopted in our analysis. Then We discuss their properties and distinguish which proofs they are adopted in. Assumption 1 (L-smooth) Local function fi satisfies the L-smoothness, i.e., for ∀w1 , w2 ∈ Rd , ∥∇fi (w1 ) − ∇fi (w2 )∥ ≤ L∥w1 − w2 ∥ for any data sample. Assumption 2 (PL-condition) Global function f satisfies PL-condition, i.e., for ∀w ∈ Rd , µ (f (w) − f (w⋆ )) ≤ ∥∇f (w)∥2 , where w⋆ ∈ arg minw f (w) is one optimum state. Assumption 1 is widely adopted to analyze FL methods (Karimireddy et al., 2020; Yang et al., 2021; Sun et al., 2023b; Qu et al., 2022; Sun et al., 2023c). Assumption 2 is merely adopted in joint analysis ofP excess risk. Most analysis of general smooth non-convex 1 t 2 objectives in FL only indicates t E∥∇f T (w )∥ is necessarily bounded. To approximate T ⋆ the optimization error E f (w ) − f (w ) in excess risk, we follow Zhou et al. (2021) to adopt the PL-condition. We also provide results without PL-condition. Assumption 3 (Stochastic) The unbiased stochastic gradients gi = ∇fi (w, z) of any data sample z satisfies the bounded variance, i.e., for ∀w ∈ Rd , E∥gi − ∇fi (w)∥2 ≤ σl2 . Assumption 4 (Local Interpolation) The unbiased stochastic gradients gi = ∇fi (w, z) of any data sample z satisfies the interpolations, i.e., for ∀w ∈ Rd , ∥gi ∥2 ≤ a2 ∥∇fi (w)∥2 . Assumption 3 is widely adopted to analyze the stochastic optimization. Assumption 4 is recently adopted to describe the property of over-parameterized models in deep learning (Vaswani et al., 2019; Karzand and Nowak, 2019; Wang et al., 2022b). Large models always show the potential strong ability to flawlessly handle each single data sample, which implies the separated gradient ∇fi (w⋆ , z) → 0 if ∇fi (w⋆ ) → 0. Assumption 5 (Heterogeneity) We consider the dissimilarity among different local clients to be bounded, i.e., for ∀w ∈ Rd , E∥∇fi (w) − ∇f (w)∥2 ≤ σg2 . Assumption 6 (Global Interpolation) Similarly, we take into account local gradients ∇fi (w) maintain interpolations, i.e., for ∀w ∈ Rd , ∥∇fi (w)∥2 ≤ b2 ∥∇f (w)∥2 . Assumption 5 is widely adopted to measure the dissimilarity of the private local dataset. Assumption 6 is an extension of interpolations to the global model, which maintains a similar property as Assumption 4 on the over-parameterized models. Assumption 4 and 6 do not have to be established at the same time. For instance, even if local interpolations hold for the local dataset, global interpolations still could not be necessarily supported under large heterogeneity. 7

Rethinking the Personalized Relaxed Initialization

Table 2: Summary of the convergence bound of our proposed FedInit method. Assumption

Convergence bound

1, 3, 5

13β κβ L 1 PT −1 D κLσ t 2 T t=0 E∥∇f (w )∥ ≤ ληKT + η λN − ληN KT ∆ T

1, 2, 3, 5

κLσ E f (wT ) − f (w⋆ ) ≤ e−λµηKT D + η λµN + O Tη + η 2 2γβ β 2 L T 1 PT −1 D t 2 t=0 E∥∇f (w )∥ ≤ ζηKT − ζηKT ∆ T E f (wT ) − f (w⋆ ) ≤ e−ζµηKT D + Rβ η 2 K 2 LD

1, 4, 6 1, 2, 4, 6

Convergence rate O √N1KT 1 O N KT 1 O N KT O T12

Assumption 7 (Lipschitz Continuity) The global function f satisfies the LG -Lipschitz property, i.e., for ∀w1 , w2 ∈ Rd , ∥f (w1 ) − f (w2 )∥ ≤ LG ∥w1 − w2 ∥. Assumption 7 is a generally strong assumption which indicates the bounded gradient ∥∇f (w)∥ ≤ LG . Recent studies learn it may not always hold for the deep models (Kim et al., 2021; Mai and Johansson, 2021; Patel and Berahas, 2022; Das et al., 2023). The previous stability analysis always adopts it in the iterative formulation. However, we propose to remove this assumption in the iterative proofs. We only adopt it at the last state, which implies ∥∇f (wT )∥ ≤ LG when T is sufficiently large. 4.3 Optimization Analysis In this part, we predominantly demonstrate the optimization error and the convergence rate of our FedInit method under two gradient properties (bounded variance and interpolation) and two function properties (smoothness and PL-condition), respectively. We also discuss the impact of the consistency. All detailed proofs could be referred to the Appendix A. Theorem 1 Under Assumption 1, 3, and 5, let participation ratio be N/C where 1 < N < C, let the learning rate satisfies η ≤ 1/N KL where K > 1, and let the RI coefficient be a small positive constant, after total T communication rounds, the global model wT generated by the FedInit satisfies: T −1

1 X D κLσ 13β 2 κβ L2 T E∥∇f (wt )∥2 ≤ +η − ∆ , T ληKT λN ληN KT

(3)

t=0

where D = f (w0 ) − f (w⋆ ) is the initialized bias, σ = σl2 + 6Kσg2 is the combination of biases of stochastic gradients and heterogeneity, κβ = 1/(1 − 141β 2 ) is a constant related to β, κ = 8 + 78β 2 κ2β is a constant related to β and κβ , λ is a constant within (0, 12 ), P T −1 ∆T = C1 i∈C E∥wi,K − wT ∥2 is the consistency term at round T . Remark 2 Theorem 1 shows the general convergence bound of the FedInit method. When β = 0, it degrades to the vanilla FedAvg method. The same as FedAvg, it is subject to the initialization bias D and the inherent variance σ. Differently, due to adopting RI, the consistency item could help to reduce the upper bound of the convergence rate. This effect from ∆T term remains the same magnitude as the effect of D. 8

Rethinking the Personalized Relaxed Initialization

1 Remark 3 Let the learning rate η be properly selected as η = O (N/KT ) 2 , we can bound − 12 the convergence rate as O (N KT ) ) , which has been proven as the optimal rate in the stochastic methods in FL under the general assumptions. The improvement of consistency term becomes weaker than the convergence rate by O(N −1 ). Although it could not further improve the rate, it is still catalytic to reduce the theoretical upper bound to some extend. Theorem 4 Under Assumption 1, 2, 3, and 5, let participation ratio be N/C where 1 < N < C, let the learning rate satisfies η ≤ 1/N KL where K > 1, and let the RI coefficient be a small positive constant, after total T communication rounds, the global model wT generated by the FedInit satisfies: η κLσ E f (wT ) − f (w⋆ ) ≤ e−λµηKT D + η +O + η2 , λµN T

(4)

where the coefficients are defined in Theorem 1. Remark 5 Theorem 4 shows the general convergence bound of FedInit method under the PL-condition. The impact of the consistency is much weaker than the dominant term of σ, which can be considered that the primary consistency term does not burden the convergence bound. If we properly selected the learning rate as η = O (log(N KT )/λµKT ), the e (N KT )−1 , which still maintains the linear speedup convergence rate achieves at most O property with N and K. Theorem 6 Under Assumption 1, 4, and 6, let participation ratio be N/C where 1 < N < C, let the learning rate satisfies η ≤ 1/aKL where K > 1, and let the RI coefficient be a small positive constant, after total T communication rounds, the global model wT generated by the FedInit satisfies: T −1

2γβ β 2 L T 1 X D E∥∇f (wt )∥2 ≤ − ∆ , T ζηKT ζηKT

(5)

t=0

where γβ = 1/(1 − 39β 2 ) is a constant related to β, ζ is a constant within (0, 21 ), and other coefficients are defined in Theorem 1. Remark 7 Theorem 6 shows the general convergence bound of FedInit method under the interpolation conditions. The deep models are considered to maintain the high ability to handle each single data sample. Under this assumption, the negative impact of the variance will be diminished to very small when the optimization process converges. Its dominant term mainly comes from the initialization bias D. The same, RI still contributes a positive effort to reduce the convergence bound with the consistency term on the non-convex objective. Remark 8 Let the learning rate η be properly selected as η = O N −1 , we can still bound the convergence rate as O (N KT )−1 . The improvement of consistency term maintains the same order with the initialization bias D. Improved optimization errors with RI can be felt more intuitively here, which benefits from a positive β. 9

Rethinking the Personalized Relaxed Initialization

Theorem 9 Under Assumption 1, 2, 4, and 6, let participation ratio be N/C where 1 < N < C, let the learning rate satisfies η ≤ 1/aKL where K > 1, and let the RI coefficient be a small positive constant, after total T communication rounds, the global model wT generated by the FedInit satisfies: E f (wT ) − f (w⋆ ) ≤ e−ζµηKT D + Rβ η 2 K 2 LD,

(6)

where Rβ = 228µγβ β 2 a2 b2 is a constant related to β, and other coefficients are defined in Theorem 1 and 6. Remark 10 Theorem 9 shows the general convergence bound of the FedInit method under both PL-condition and interpolation conditions. Let learning rate η be properly selected as e T −2 , which is domiη = O (2 log(KT )/ζµKT ), the convergence rate achieves at most O nated by the initialization bias D. It is consistent with the upper bound in Theorem 4 when stochastic variances are ignored under interpolations. We summarize the main conclusions of optimization in Table 2. 4.4 Generalization Analysis In this part, we mainly illustrate the generalization analysis of our FedInit method under two gradients properties (bounded variance and interpolation). We adopt the uniform stability analysis which is widely adopted in previous literatures. We first introduce the definition of our analysis as follows, and then introduce the theoretical analysis and demonstrate the improvements of the RI technique in FL. All detailed proofs could be referred to the Appendix B. In the FL framework, we suppose there are C clients participating in the training process S as a set C = {i}C i=1 . Each client has a local dataset Si = {zj }j=1 with total S data sampled from a specific unknown distribution Di . Now we define a re-sampled dataset Sei which only differs from the dataset Si on the j ⋆ -th data. We replace the Si⋆ with Sei⋆ and keep e From the perspective of total other C − 1 local dataset, which composes a new set C. ⋆ ⋆ e data, C only differs from the C at j -th data on the i -th client. Then, based on these two sets, our method could generate two output models, wT and w eT respectively, after T communication rounds. By bounding the difference according to these two models, we can learn the stability and generalization efficiency. Our analysis mainly focuses comparisons of vanilla SGD, FedAvg, and our proposed FedInit method. Definition 11 (Uniform Stability (Hardt et al., 2016)) For these two models wT and w eT generated as introduced above, a general method satisfies ϵ-uniformly stability if: sup E[f (wT ; zj ) − f (w eT ; zj )] ≤ ϵ.

(7)

zj ∼{Di }

Moreover, if a general method satisfies ϵ-uniformly stability, then its generalization error could also be bounded as EG ≤ supzj ∼{Di } E[f (wT ; zj ) − f (w eT ; zj )] ≤ ϵ (Hardt et al., 2016; Zhang et al., 2022). 10

Rethinking the Personalized Relaxed Initialization

Theorem 12 Under Assumption 1, 3, and 7, let all conditions in the optimization process be satisfied, let the learning rate be selected as η = O (1/t) = c/t where c is a constant, let t0 be a specific round to firstly select the different data sample, and let U = sup f (w, z) be the upper bound, for arbitrary data sample z followed the joint distribution {Di }, we have: εG ≤ E∥f (wT +1 ; z) − f (w eT +1 ; z)∥ ≤

N U Kt0 2σl LG + CS (1 + 2β)CSL

T t0

cKL .

Furthermore, to minimize the stability errors, we can select the proper observation point h i 1 cKL 1+cKL 2σl LG T 1+cKL and then we have: t0 = (1+2β)N U KL 1 1+cKL cKL 2 2σl LG εG ≤ (N U KT ) 1+cKL . CS (1 + 2β)L

(8)

Remark 13 Theorem 12 demonstrates the general generalization error bound of the proposed FedInit method. When β = 0, it degrades to the vanilla FedAvg method. From the generalization bound, we mainly focuses on the terms of total number of data samples and the training length T and K. If we adopt the vanilla SGD to train a single model with total CS data samples after T iterations, Hardt et al. (2016) have provided the general stability cL 1+cL

on the smooth and non-convex objectives as O T CS . In FL, our analysis indicates that cKL ) 1+cKL it achieves O (N KTCS . We first summarize the comparison between vanilla SGD and FedAvg (β = 0) in Table 3. Table 3: Comparison between vanilla SGD and FedAvg. SGD number of samples number of iterations

1 O CS cL O T 1+cL

FedAvg cKL 1+cKL

O N CS cKL O (T K) 1+cKL

From above table, we clearly see the damage to the stability due to the local training process on local private dataset. When K = 1 and N = 1, FedAvg degrades to the vanilla SGD method. When K = 1 and N > 1, FedAvg degrades to the mini-batch SGD with the batchsize of N . Therefore, we know that to achieve the same stability error, FL always requires more data samples. This is the inherent bias in FL. The worst case in FL is to let N = C as cKL 1 1+cKL 1 the full participation and it achieves the O C S . A large number of local clients will seriously hinder the stability of the global model. Similarly, for the high stability, the number of participating clients per round also needs to be limited. Remark 14 Obviously, when we select a small positive β, it reduces the generalization error 1 1+cKL 1 by 1+2β , which illustrates the advantages of RI. It effectively improves the stability 11

Rethinking the Personalized Relaxed Initialization

of the global model and has enormous utility in practice. As K increases, the performance improvement brought by β will gradually become smaller. This conclusion is also intuitive. RI moves away from the last local state as a new initialization, but when K is large enough, the advantages of this compensation will be greatly reduced. The local training will make the 1 1+cKL 1 → 1. local model overfit to the local dataset. When K → ∞, the impact of 1+2β Theorem 15 Under Assumption 1, 4, and 7, let all conditions in the optimization process be satisfied, let the learning rate be selected as η = O (1/t) = c/t where c is a constant, let t0 be a specific round to firstly select the different data sample, and let U = sup f (w, z) be the upper bound, for arbitrary data sample z followed the joint distribution {Di }, furthermore, let β be a decayed sequence {β t }Tt=0 by the round t, we have: εG ≤ E∥f (wT +1 ; z) − f (w eT +1 ; z)∥ ≤ e2

t=1 β

abcL2G K . 2β 0 CS

(9)

Remark 16 Theorem 15 demonstrates the general generalization error bound of the proK rate under posed FedInit method under the interpolation condition. It achieves the O CS P the proper selection of β. Here the β must be decayed by the round t and let Tt=1 β t be at least a constant bound. Actually, the coefficient β includes the decayed rate of the learning rate which could be considered as a quasi-learning rate term. Increasing the local interval K still damages the stability and draws a negative impact on the final convergence. This error asymptotically approximates the error of the vanilla SGD (Hardt et al., 2016). 4.5 Divergence Term ∆t In the former two parts, we provide the complete theorem to understand the optimization error EO and generalization error EG . In this part, we focus on the analysis of the divergence term of our proposed FedInit method. Due to the RI at the beginning of each Pcommunication t−1 t t )−η K−1 round, according to the Algorithm 1, we have wi,K = wt +β(wt −wi,K k=0 gi,k . Thus, we have the following recursive relationship: w |

t+1

t − wi,K

}

local divergence at t + 1

=β

t−1 (wi,K − wt )

}

local divergence at t

+ (w |

t+1

− w )+ {z }

global update

K−1 X

t . ηgi,k

(10)

k=0

}

local updates

According to the recursive formulation (10), we can bound the divergence ∆t . Detailed proofs are stated in Appendix A. Theorem 17 Under Assumption 1, 3, and 5, let all conditions in Theorem 1 and 4 hold, we can bound the divergence term: T −1

η 804Cβ K 1 X t ∆ ≤η D + η 2 Jβ Kσ = O + η2 , T λT T

(11)

t=0

where Cβ = κβ /(1−48β 2 κβ ) is a constant related to κβ and β, and Jβ = Cβ (132+804κ/λN ) is a constant related to Cβ . Other constant coefficients are defined in Theorem 1. 12

Rethinking the Personalized Relaxed Initialization

Remark 18 Theorem 17 corresponds to the general analysis of Theorem 1 and 4. When 1 the learning rate is selected as O (N/KT ) 2 (Theorem 1), the dominant term comes from the stochastic variance and heterogeneity and achieves the O T −1 rate. When the learning rate is selected as O (log(N KT )/λµKT) (Theorem 4), the dominant term comes from the e T −2 rate. It also indicates that if the learning rate is initial bias D and achieves the O selected as a constant, the consistency will always maintain a constant upper bound which is dominated by the stochastic variance. Theorem 19 Under Assumption 1, 4, and 6, let all conditions in Theorem 6 and 9 hold, we can bound the divergence term: T −1

η Rβ K 1 X t ∆ ≤η D = O , T 2µβ 2 ζT T

(12)

t=0

where all coefficients are defined in Theorem 9. Remark 20 Theorem 19 demonstrates the divergence term will always diminish by at least O(T −1 ) rate under interpolation condition. The conclusion under the strong assumption reveals the potential prospects of FL on large models. When the model could handle each separate data sample, the consensus of the local clients during the training process can always be effectively guaranteed. Meanwhile, it also illustrates that improving the capabilities of the model can greatly compensate for the inherent bias in the training model in FL, which can reduce the negative impact of “client drift”. Discussion. We provide a comprehensive analysis on both optimization and generalization of our proposed FedInit method to further understand how and why it can improve efficiency in FL. From the Theorem 1 and 6, we can know that under the general assumptions, compared with the FedAvg, RI contributes to reducing the convergence bound by an additional negative term of divergence. This negative term is independent of the methods adopted, which only comes from personalized relaxed initialization. In other words, if we incorporate RI into advanced benchmarks, e.g. for SCAFFOLD, it also could be proven that there is a similar term to reduce its convergence bound. Furthermore, we provide how it helps to reduce the generalization error bound in Theorem 12 under the general assumptions. By 1 1+cKL 1 adopting RI, the stability is enhanced with a 1+2β rate. When the local interval K increases, appropriately increasing β can also maintain high efficiency and model stability.

5 Experiments In this section, we mainly introduce our experimental studies. We first introduce the experimental setups, including the benchmarks, general settings, and hyperparameter selections. Then we show our experiments and provide the corresponding understanding according to the theoretical analysis, specifically for the efficiency of relaxed initialization. 5.1 Experimental Setups Benchmarks. Benchmarks selected in our paper: FedAvg (McMahan et al., 2017) proposes a general FL paradigm; FedAdam (Reddi et al., 2020) studies the efficiency of the 13

Rethinking the Personalized Relaxed Initialization

adaptive optimizer in FL; SCAFFOLD (Karimireddy et al., 2020), FedDyn (Acar et al., 2021), and FedCM (Xu et al., 2021) learn the “client-drift” problem and adopt the variance reduction technique, ADMM, and the client-level momentum respectively in FL to alleviate its negative impact; FedSAM (Qu et al., 2022) uses the local SAM objective instead of the vanilla empirical risk objective to search for a smooth loss landscape. Models and Dataset. Here we briefly introduce the setups in our experiments. We validate the proposed FedInit method on the classical CIFAR-10/100 dataset (Krizhevsky et al., 2009). To generate local heterogeneity, we follow Hsu et al. (2019) to split the local clients through the Dirichlet sampling via the coefficient Dr to control the heterogeneous level and follow Sun et al. (2023c) to adopt the sampling with replacement to enhance the heterogeneity level. We test on the ResNet-18-GN (He et al., 2016; Hsieh et al., 2020) and VGG-11 (Simonyan and Zisserman, 2014) 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 a random Gaussian noise for different clients. The second noise is the category-based 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, local heterogeneity is significantly enlarged. Hyperparameters. For each benchmark in our experiments, we adopt two coefficients Dr = 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 η = 1 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.9995. We train 500 rounds on CIFAR-10 and 800 rounds on CIFAR100 to achieve the stable test accuracy. The participation ratios are selected as 10% and 5% respectively of total 100 and 200 clients. To eliminate large variances due to training instability, all results are first smoothed by the convolution filter and then we select the maximization value in the last 50 communication rounds. 5.2 Main Results In Table 4 and 5, our FedInit method performs better than the other benchmarks with good stability across different experimental setups. On the test of ResNet-18-GN model on CIFAR-10, it achieves about 3.42% improvement than the vanilla FedAvg on the high heterogeneous splitting with Dr = 0.1. When the participation ratio decreases to 5%, the accuracy drops only about 0.1% while FedAvg drops almost 1.88%. Similar results on CIFAR-100, when the participation ratio decreases, FedInit can still achieve the test accuracy of 43.77%, while the second best method SCAFFOLD drops 3.21% from the former. This clearly demonstrates the good generalization of the proposed FedInit on 14

Rethinking the Personalized Relaxed Initialization

Table 4: Test accuracy on the CIFAR-10 dataset. We test two active ratios on each dataset. On each setup, we test two Dirichlet splittings, and each result tests 3 times. The table reports results on ResNet-18-GN (upper) and VGG-11 (lower). CIFAR-10 Method

10%-100 clients

5%-200 clients

Dir-0.6

Dir-0.1

Dir-0.6

Dir-0.1

FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM FedInit

78.77±.11 76.52±.14 79.23±.22 81.37±.17 82.43±.16 81.67±.17 83.11±.29

72.53±.17 70.44±.22 72.89±.23 75.06±.16 75.08±.19 73.93±.26 75.95±.19

74.81±.18 73.28±.18 75.45±.19 78.17±.28 79.96±.13 79.49±.17 80.58±.20

70.65±.21 68.87±.26 71.23±.26 74.24±.22 74.15±.34 73.12±.18 74.92±.17

FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM FedInit

85.28±.12 86.44±.13 86.37±.22 87.73±.17 87.35±.19 86.80±.33 88.47±.22

78.02±.22 77.55±.28 79.10±.07 81.98±.19 82.70±.24 79.85±.29 83.51±.13

81.23±.14 81.05±.23 81.76±.26 84.81±.15 84.84±.19 83.23±.31 85.36±.19

74.89±.25 74.04±.17 75.22±.13 79.04±.16 80.01±.22 76.42±.36 79.73±.14

different participation ratios. Judging from the overall results, the improvement of adopting RI is significantly considerable. In addition, in Table 6, we incorporate the relaxed initialization (RI) into the other benchmarks to further validate 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 4 and 5 shows the poor performance of the vanilla FedAvg. Nevertheless, when adopting the RI, FedInit remains above most benchmarks on several setups. When the RI is incorporated into other benchmarks, it helps them to achieve higher performance without additional communication costs. RI does not hinder other algorithms and significantly improves their performance. For instance, it helps the classical SCAFFOLD method to improve about 2% ∼ 3%, which makes the SCAFFOLD method easily achieve the SOTA results. This is consistent with the theoretical analysis we mentioned above. The improvement in RI is due to the training mode of FL and is independent of the method adopted for local training. As a very lightweight computing plug-in, it can help many advanced algorithms further improve their performance, which has high compatibility and scalability. 15

Rethinking the Personalized Relaxed Initialization

Table 5: Test accuracy on the CIFAR-10/100 dataset. We test two active ratios on each dataset. On each setup, we test two Dirichlet splittings, and each result tests 3 times. The table reports results on ResNet-18-GN (upper) and VGG-11 (lower). CIFAR-100 10%-100 clients

Method

Dir-0.6

Dir-0.1

Dir-0.6

Dir-0.1

FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM FedInit

46.35±.15 48.35±.17 47.51±.26 51.98±.23 50.82±.19 51.56±.20 52.21±.09

42.62±.22 40.77±.31 43.43±.12 44.41±.15 42.50±.28 43.03±.26 44.22±.21

44.70±.22 44.33±.26 45.98±.27 50.70±.29 47.32±.21 50.93±.19 51.16±.18

40.41±.33 38.04±.25 40.22±.27 41.83±.29 41.74±.21 42.33±.19 43.77±.36

FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM FedInit

53.46±.25 55.56±.29 54.85±.31 59.45±.17 56.13±.18 53.88±.22 58.84±.11

50.53±.20 53.41±.18 51.88±.27 56.67±.24 53.97±.11 50.73±.35 57.22±.21

47.55±.13 51.33±.25 48.65±.21 53.73±.32 51.74±.18 47.83±.19 54.12±.08

45.05±.33 47.26±.21 46.58±.28 50.08±.19 48.16±.17 46.33±.25 50.27±.29

Performance of different K

test accuracy

Performance of different

82 80 78 76

Dirichlet-0.1 Dirichlet-0.6

74 72

5%-200 clients

local interval K

75 70 65 60 55

Dirichlet-0.1 Dirichlet-0.6

50 45

-0.2

(a) Different K.

-0.1

0.01

0.02

0.05

relaxed coefficient

0.1

0.15

(b) Different β.

Figure 1: Sensitivity studies of local intervals K and relaxed coefficient β of the FedInit method on CIFAR-10. To fairly compare their efficiency.

5.3 Sensitivity on K and β The excess risk and test error of FedInit indicates there exist best selections for local interval K and relaxed coefficient β, respectively. In this part, we test a series of selections to validate 16

Rethinking the Personalized Relaxed Initialization

beta=-0.2 beta=-0.1 beta=0 beta=0.1

0.4 0.3

100

200

300

400

Communication Rounds

1.8 1.6

500

100

200

300

400

Communication Rounds

0.6

beta=-0.2 beta=-0.1 beta=0 beta=0.1

0.5 0.4 0.3

100

200

300

400

Communication Rounds

500

beta=-0.2 beta=-0.1 beta=0 beta=0.1

2.4 2.2 2.0 1.8

100

200

300

400

Communication Rounds

200

300

400

1.0 0.9 0.8

500

100

200

300

400

500

Communication Rounds

0.6 0.5

500

beta=-0.2 beta=-0.1 beta=0 beta=0.025 beta=0.05

0.4 0.3 0.2 0.1

beta=-0.2 beta=-0.1 beta=0 beta=0.025 beta=0.05

1.5

0.7

1.6 0

100

Communication Rounds

beta=-0.2 beta=-0.1 beta=0 beta=0.025 beta=0.05

1.1

(b) Dir-0.1 5%-200 with FedAvg + RI (FedInit).

Test Top-1 Acc.

2.6

Divergence term

Test Top-1 Acc.

2.8

0.3

500

(a) Dir-0.6 10%-100, FedAvg + RI (FedInit).

0.7

beta=-0.2 beta=-0.1 beta=0 beta=0.025 beta=0.05

0.4

0.2

1.4

0.8

0.5

Divergence term

beta=-0.2 beta=-0.1 beta=0 beta=0.1

0.5

0.6

100

200

300

400

Communication Rounds

500

Divergence term

0.6

2.0

1.2

0.7

Test Top-1 Acc.

2.2

0.7

Divergence term

Test Top-1 Acc.

0.8

1.4 1.3 1.2 1.1 1.0 0.9 0

100

200

300

400

Communication Rounds

500

(d) Dir-0.1 5%-200 with SCAFFOLD + RI.

Figure 2: The accuracy and divergence of different β. (a) and (b) are tested with FedAvg + RI (FedInit), while (c) and (d) for SCAFFOLD + RI. (a) and (c) are tested on the Dir-0.6 10%-100 setups, while (b) and (d) for Dir-0.1 5%-200 setups.

our conclusions. To be aligned with previous studies, we denote K as training epochs in the experiments instead of the iterations in the theoretical analysis. Their relationship is: 1 epoch = (S/batchsize) iterations. In Fig. 1 (a), we clearly see that there is the best selection on the local interval K. As local interval K increases, test accuracy rises first and then decreases. Our analysis provides a comprehensive explanation of this 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. In Fig. 1 (b), we can see that the selection of the β is stable within its valid range, which has great potential to improve performance. When it is larger than the threshold, the training process will diverge quickly. This phenomenon is highly consistent with our analysis. To simplify the analysis, we omit the full terms of the upper bound of β and select a constant bound in our theorems. In fact, the complete upper bound of β is related to the learning rate η and the local interval K. However, in the experiments, we find that a simple constant selection can offer high improvements. 5.4 Divergence Term ∆t In this part, we mainly test the consistency level of different β. The coefficient β controls the divergence level of the local initialization states. We select the FedAvg and SCAFFOLD to show the efficiency of the proposed relaxed initialization. Fig. 2 demonstrates that the relaxed initialization (RI) effectively reduces the divergence term and improves the test accuracy. In all tests, when β = 0 (green curve), it represents the vanilla method without RI. After incorporating the RI, the test accuracy achieves at least 2% improvement on each setup. As introduced in Algorithm 1 Line.6, a negative β 17

Rethinking the Personalized Relaxed Initialization

Table 6: We incorporate the relaxed initialization (RI) into the different benchmarks to test their improvements on the ResNet-18-GN model on the CIFAR-10 dataset under the same settings and hyperparameters selections. 10%-100 clients Dir-0.6

Method FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM

5%-200 clients

Dir-0.1

Dir-0.6

Dir-0.1

+RI

78.77 76.52 79.23 81.37 82.43 81.67

83.11 78.33 83.36 83.27 81.91 81.77

72.53 70.44 72.89 75.06 75.08 73.93

75.95 72.55 76.34 77.30 75.11 73.71

74.81 73.28 75.45 78.17 79.96 79.49

80.58 78.33 80.66 81.02 79.88 79.72

70.65 68.87 71.23 74.24 74.15 73.12

74.92 71.34 75.08 76.22 74.34 72.98

Table 7: Averaged wall-clock time cost (s/round) of the ResNet-18-GN model in the training process on CIFAR-10 dataset. FedAvg

FedAdam

FedSAM

SCAFFOLD

FedDyn

FedCM

FedInit

10%-100 ratio

19.38 1×

23.22 1.19×

30.23 1.56×

28.61 1.47×

23.84 1.23×

22.63 1.17×

20.41 1.05×

5%-200 ratio

15.87 1×

17.50 1.10×

22.18 1.40×

24.49 1.54×

20.61 1.30×

18.19 1.15×

16.14 1.02×

means to adopt the relaxed initialization which is close to the latest local model. This is not our expectation. When β = 0, FedInit degrades to vanilla FedAvg. The positive β is the truly effective selection of RI. When we select the negative β, in most cases it will result in greater divergence and worse test accuracy (orange and blue curves in Fig. 2). It validates that RI is required to be far away from the local model (a positive β). When β is small, the correction is limited. The local divergence term is difficult to be diminished efficiently. While it becomes too large, the local training begins from a bad initialization, which can not receive enough guidance of global information from the global models. Furthermore, if the initialization is too far from the local model, the quality of the initialization state will not be effectively guaranteed. Another interesting phenomenon is that RI will cause a large fluctuation of divergence in the early stage of training, but the test accuracy will be improved stably. We speculate that the main reason for this phenomenon is the imprecise selection of β. One potential research direction is to find more adaptive β in the training process. For most existing tasks, constant β is already an excellent solution in practice. Furthermore, due to the limited range of β, it is really easy to search for a optimal value. 18

Rethinking the Personalized Relaxed Initialization

Table 8: Acceleration ratio of the communication rounds and wall-clock time of the ResNet18-GN model on CIFAR-10 dataset. Round

Time (s)

Speed Ratio

FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM FedInit

371 489 377 248 192 183 172

1× 0.76× 0.98× 1.50× 1.93× 2.02× 2.15×

7189 11354 11396 7095 4577 4141 3510

1× 0.63× 0.63× 1.01× 1.57× 1.73× 2.04×

FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM FedInit

191 256 204 211 122 95 132

1× 0.74× 0.93× 0.90× 1.56× 2.01× 1.44×

3701 5944 6166 6036 2908 2149 2694

1× 0.62× 0.60× 0.61× 1.27× 1.72× 1.37×

5.5 Communication Rounds and Wall-clock Time Costs In this part, we mainly demonstrate the test on time costs, including both the communication rounds and the wall-clock time required. As the major consideration to validate whether an algorithm is practical, the time consumption is one of the very important studies. We verify that although some previous advanced algorithms appear to be efficient, they introduce a large amount of extra calculations and the final running time does not be effectively accelerated as they proposed. As shown in Table 7, due to the additional calculation costs, the practical wall-clock time is different for each method. Generally, FedAvg adopts the local-SGD updates without any additional calculations. FedAdam adopts similar local-SGD updates and an adaptive optimizer on the global server. FedSAM calculation double gradients, which is the main reason for 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 about the same costs as the vanilla FedAvg. Table 8 shows the communication rounds and wall-clock time required to achieve the target accuracy. In this part, we set the target accuracy and compare their required communication rounds and training time respectively. We test on the ResNet-18-GN model with the setup of 10%-100 Dir-0.1 splitting. We clearly see that some advanced methods, i.e. SCAFFOLD 19

Rethinking the Personalized Relaxed Initialization

Table 9: Communication and storage costs. Method

Communication

ratio

Storage

ratio

FedAvg FedAdam FedSAM SCAFFOLD FedDyn FedCM FedInit

Nd Nd Nd 2N d Nd 2N d Nd

1× 1× 1× 2× 1× 2× 1×

Cd 2Cd 2Cd 2Cd 2Cd 2Cd Cd

1× 2× 2× 2× 2× 2× 1×

N : number of participating clients; C: number of total clients. 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. FedInit is a very light and practical method, which only adopts a relaxed initialization on the FedAvg method, which makes it to be better and even achieves SOTA results. 5.6 Communication Bottleneck and Storage Costs In this part, we mainly compare the communication, calculation, and storage costs theoretically and experimentally. By assuming the total model maintains d dimensions, we summarize the costs of benchmarks and our proposed FedInit in Table 9. 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) to revise each local iteration. Though this achieves good performance, we must indicate that under the millions of edge devices in the FL paradigm, this may introduce a 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 a large calculation cost that can not be neglected. SCAFFOLD and FedDyn are required to store 2× vectors on each local devices. This is also a limitation for light devices, i.e. mobiles.

6 Conclusion In this work, we propose an efficient and novel FL method, dubbed FedInit, which adopts the stage-wise personalized relaxed initialization (RI) to improve the generalization efficiency in FL. Furthermore, to clearly understand the essential impact of consistency in FL, we explore the joint analysis of optimization and generalization in FL. Our proofs indicate that consistency dominates RI could help to reduce both the optimization errors and generalization errors. Extensive experiments are conducted to validate the efficiency of relaxed initialization. As a practical and light plug-in, it could also be easily incorporated into other FL paradigms to further improve their performance.

Rethinking the Personalized Relaxed Initialization

Appendix A. Proof of Optimization A.1 Some Notations We assume the objective function is L-smooth and non-convex w.r.t w. We could upper bound the training error in the FL. Some useful notations in the proof are introduced in Table 10. And, some important lemmas are stated as follows. Table 10: Some abbreviations of the used terms in the proof of the optimization process. Notation

Formulation

Description

t wi,k wt

V1t V2t ∆t D

PK−1 1 P t t 2 k=0 E∥wi,k − w ∥ i∈C C t+1 t 2 E∥w −w ∥

parameters at k-th iteration in round t on client i global parameters in round t averaged norm of the local updates in round t norm of the global updates in round t inconsistency/divergence term in round t bias between the initialization state and optimal

t−1 1 P t 2 i∈C E∥wi,K − w ∥ C 0 ⋆ f (w ) − f (w )

A.2 Proofs with Assumption 3 A.2.1 Some Important Lemmas Lemma 21 (Bounded local updates) Under Assumption 1, 3 and 5, the averaged norm of the local updates of total C clients could be bounded as: (13) V1t ≤ 4Kβ 2 ∆t + 3K 2 η 2 σl2 + 6Kσg2 + 18K 3 η 2 E∥∇f (wt )∥2 . Proof V1 measures the norm of the local offset during the local training stage. It could be bounded by two major steps. Firstly, we bound the separated term on the single client i at iteration k as: t ∥2 Et ∥wt − wi,k+1 t t t t = Et ∥wt − wi,k + η(gi,k − ∇fi (wi,k ) + ∇fi (wi,k ) − ∇fi (wt ) + ∇fi (wt ) − ∇f (wt ) + ∇f (wt ))∥2 1 2 t t 2 t t ≤ η Et ∥gi,k − ∇fi (wi,k )∥ + 1 + ∥2 + 6Kη 2 Et ∥∇fi (wi,k ) − ∇fi (wt )∥2 Et ∥wt − wi,k 2K − 1

+ 6Kη 2 Et ∥∇fi (wt ) − ∇f (wt )∥2 + 6Kη 2 ∥∇f (wt )∥2 1 2 2 t ≤ 1+ + 6η KL Et ∥wt − wi,k ∥2 + η 2 σl2 + 6Kη 2 σg2 + 6Kη 2 ∥∇f (wt )∥2 2K − 1 1 t Et ∥wt − wi,k−1 ∥2 + η 2 σl2 + 6Kη 2 σg2 + 6Kη 2 ∥∇f (wt )∥2 , ≤ 1+ K −1 where the learning rate is required η ≤ √

1 for K ≥ 2. 6(K−1)(2K−1)L

Therefore, by computing the average of the separated term on client i: X 1 X 1 1 t t 2 t Et ∥w − wi,k+1 ∥ ≤ 1 + Et ∥wt − wi,k ∥2 + η 2 σl2 + 6Kη 2 σg2 + 6Kη 2 ∥∇f (wt )∥2 . C K −1 C i∈C

i∈C

Rethinking the Personalized Relaxed Initialization

k 1 ≤ Unrolling the aggregated term on iteration k ≤ K. When local interval K ≥ 2, 1 + K−1 K 1 ≤ 4. Then we have: 1 + K−1 1 X t Et ∥wt − wi,k+1 ∥2 C i∈C τ k X k X 1 1 1 2 2 2 2 2 t 2 t η σl + 6Kη σg + 6Kη ∥∇f (w )∥ + 1 + ≤ 1+ ∥wt − wi,0 ∥2 K −1 K −1 C τ =0 i∈C X 1 t−1 2 Et ∥wt − wi,K ∥ ≤ 3(K − 1) η 2 σl2 + 6Kη 2 σg2 + 6Kη 2 ∥∇f (wt )∥2 + 4β 2 C i∈C < 4β 2 ∆t + 3Kη 2 σl2 + 6Kσg2 + 18K 2 η 2 ∥∇f (wt )∥2 . Summing the iteration on k = 0, 1, · · · , K − 1, K−1

V1t =

1 XX t ∥2 ≤ 4Kβ 2 ∆t + 3K 2 η 2 σl2 + 6Kσg2 + 18K 3 η 2 ∥∇f (wt )∥2 . Et ∥wt − wi,k C i∈C k=0

This completes the proof.

1 , the Lemma 22 (Bounded global updates) Under Assumption 1, 3 and 5, let η ≤ KL norm of the global update of selected N clients could be bounded as: K−1

13η 2 K 2 76η 2 K 2 2 76η 2 K 2 2η 2 X X t )∥2 . ∆ + σl + σg + E∥∇f (wt )∥2 + 2 E∥ ∇fi (wi,k N N N N C

22β V2t ≤

i∈C k=0

(14) Proof V2 measures the variance of the global offset after each communication round. We define an indicator function Ievent = 1 if the event happens. Then, to upper bound it, we first split the expectation term as: 1 X t wi,K − wt ∥2 N i∈N X X 1 1 t t = 2 E∥ (wi,K − wt )∥2 = 2 E∥ (wi,K − wt )Ii∈N ∥2 N N i∈N i∈C "K−1 # X X 1 t−1 t Ii∈N ηgi,k + β(wt − wi,K ) ∥2 = 2 E∥ N i∈C k=0 "K−1 # K−1 X X η2 X X 1 t−1 t t t E∥gi,k Ii∈N η∇fi (wi,k ) + β(wt − wi,K ) ∥2 = − ∇fi (wi,k )∥2 + 2 E∥ NC N E∥wt+1 − wt ∥2 = E∥

i∈C k=0

i∈C

k=0

Rethinking the Personalized Relaxed Initialization

X η 2 Kσl2 1 ≤ + 2 E∥ Ii∈N N N

"K−1 X

i∈C

# t−1 t η∇fi (wi,k ) + β(wt − wi,K )

∥2 .

k=0

For the second term, we can adopt the following equation. For the arbitrary vector xi ∈ Rd , X X X E∥ Ii∈N xi ∥2 = E⟨ Ii∈N xi , Ij∈N xj ⟩ i∈C

i∈C

j∈C

E⟨Ii∈N xi , Ij∈N xj ⟩ +

N (N − 1) X N E⟨xi , xj ⟩ + C(C − 1) C (i̸=j)∈C

E⟨Ii∈N xi , Ij∈N xj ⟩

(i=j)∈C

(i̸=j)∈C

E⟨Ii∈N xi , Ij∈N xj ⟩

(i=j)∈C

(i̸=j)∈C

E⟨Ii∈N xi , Ij∈N xj ⟩ +

N (N − 1) X N (C − N ) X E⟨xi , xj ⟩ + E⟨xi , xj ⟩ C(C − 1) C(C − 1) i,j∈C

E⟨xi , xj ⟩

(i=j)∈C

N (N − 1) E∥ C(C − 1)

(i=j)∈C

xi ∥2 +

i∈C

N (C − N ) X C(C − 1)

E∥xi ∥2 .

i∈C

PK−1

t ) + β(w t − w t−1 ) into We first upper bound the first term. By taking xi = k=0 η∇fi (wi,k i,K P E∥ i∈C xi ∥2 , we have: # " X K−1 X X K−1 X t−1 2 2 t t t ∇fi (wi,k )∥2 + 2β 2 C 2 ∆t . E∥ η∇fi (wi,k ) + β(w − wi,K ) ∥ ≤ 2η E∥ i∈C

i∈C k=0

k=0

Then we upper bound the second term. By taking xi = P into i∈C E∥xi ∥2 , we have: X

E∥

K−1 X k=0

K−1 X

i∈C

≤K

β t−1 t ) + (wt − wi,K η∇fi (wi,k ) K

k=0

X K−1 X

t E∥η∇fi (wi,k )+

i∈C k=0

X K−1 X

t−1 t t k=0 η∇fi (wi,k ) + β(w − wi,K )

t−1 2 t )∥ η∇fi (wi,k ) + β(wt − wi,K

i∈C

E∥

PK−1

∥2

β t t−1 2 (w − wi,K )∥ K

t E∥η∇fi (wi,k ) − η∇fi (wt ) + η∇fi (wt ) − η∇f (wt ) + η∇f (wt ) +

i∈C k=0 2 2

≤ 4Cη KL V1t + 4Cβ 2 ∆t + 4Cη 2 K 2 σg2 + 4Cη 2 K 2 E∥∇f (wt )∥2 . Let 1 ≤ N < C, we have: X η 2 Kσl2 1 + 2 E∥ Ii∈N V2t ≤ N N i∈C

"K−1 X

# t−1 t η∇fi (wi,k ) + β(wt − wi,K ) ∥2

k=0

β t t−1 2 (w − wi,K )∥ K

Rethinking the Personalized Relaxed Initialization

≤

η 2 Kσl2 4(C − N ) 2 + (η KL2 V1t + β 2 ∆t + η 2 K 2 σg2 + η 2 K 2 E∥∇f (wt )∥2 ) N N (C − 1) K−1

2(N − 1) 2 X X 2β 2 (N − 1) t t η E∥ ∆ ∇fi (wi,k )∥2 + CN (C − 1) N (C − 1) i∈C k=0

K−1

2η 2 X X η 2 Kσl2 4 t β 2 ∆t + η 2 K 2 σg2 + η 2 K 2 E∥∇f (wt )∥2 + 2 E∥ + ∇fi (wi,k )∥2 ≤ N N C i∈C k=0

2β 2 t 4β 2 ∆t + 3Kη 2 σl2 + 6Kσg + 18η 2 K 2 ∥∇f (wt )∥2 + ∆ N N 2β 2 η2K 4η 2 K 2 = 3 + 8η 2 K 2 L2 ∆t + 1 + 12η 2 K 2 L2 σl2 + 1 + 18η 2 K 2 L2 σg2 N N N K−1 2η 2 X X 4η 2 K 2 t 1 + 18η 2 K 2 L2 E∥∇f (wt )∥2 + 2 E∥ ∇fi (wi,k )∥2 . + N C +

4η 2 K 2 L2

i∈C k=0

Generally, we can simplify the coefficient by selecting some special term η 2 K 2 L2 . For con1 venience, we directly select the η ≤ KL . This completes the proof.

Lemma 23 (Bounded divergence term) Under Assumption 1, 3 and 5, let the learning rate 1 1 t satisfy η ≤ KL and let κβ = 1−141β 2 be a constant, the divergence term ∆ could be bounded as the recursion of: K−1 6κβ η 2 X X t )∥2 . ∆t ≤ κβ ∆t − ∆t+1 + 96η 2 κβ K σl2 + 6Kσg2 + 576κβ η 2 K 2 E∥∇f (wt )∥2 + E∥ ∇fi (wi,k C2 i∈C k=0

(15) Proof According to the local updates, we have the following recursive formula: t wt+1 − wi,K | {z }

=β

local bias in round t + 1

t−1 − wt ) (wi,K | {z }

+(wt+1 − wt ) +

K−1 X

t ηgi,k .

k=0

local bias in round t

By taking the squared norm and expectation on both sides, we have: t−1 t E∥wt+1 − wi,K ∥2 = E∥β(wi,K − wt ) + wt+1 − wt +

K−1 X

t ηgi,k ∥2

k=0 t−1 ≤ 3β 2 E∥wi,K − wt ∥2 + 3 E∥wt+1 − wt ∥2 +3E∥ | {z } V2t

K−1 X

t ηgi,k ∥2 .

k=0

The second term in the above inequality is V2 we have bounded in lemma 22. Then we bound the stochastic gradients term. We have: E∥

K−1 X k=0

t ηgi,k ∥2 ≤ 2η 2 E∥

K−1 X

K−1 X t t t ∇fi (wi,k )∥2 gi,k − ∇fi (wi,k ) ∥2 + 2η 2 E∥

k=0

Rethinking the Personalized Relaxed Initialization

≤ 2η 2 Kσl2 + 2η 2 K

K−1 X

t E∥∇fi (wi,k ) − ∇fi (wt ) + ∇fi (wt ) − ∇f (wt ) + ∇f (wt )∥2

k=0 K−1 X 2

≤ 2η 2 Kσl2 + 6η 2 KL

t E∥wi,k − wt ∥2 + 6η 2 K 2 σg2 + 6η 2 K 2 E∥∇f (wt )∥2 .

k=0

Taking the average on client i, we have: K−1

X 1 X t E∥ ηgi,k ∥2 ≤ 2η 2 Kσl2 + 6η 2 KL2 V1t + 6η 2 K 2 σg2 + 6η 2 K 2 E∥∇f (wt )∥2 . C i∈C

k=0

1 and combining this and the squared norm inequality, we have: With η ≤ KL

∆

t+1

K−1 X 3 X 1 X t+1 t 2 2 t t t ∥2 E∥w − wi,K ∥ ≤ 3β ∆ + 3V2 + E∥ ηgi,k = C C i∈C i∈C k=0 22 13 2 2 2 2 t 2 2 2 2 ≤ 3β 1 + + 24η K L ∆ + 3η K 1 + + 18η K L σl2 N N 39 39 2 2 2 2 2 2 2 2 2 2 2 + 6η K 3 + + 54η K L σg + 6η K 3 + + 54η K L E∥∇f (wt )∥2 N N K−1

6η 2 X X t )∥2 . E∥ ∇fi (wi,k C2 i∈C k=0

Similarly, we can simplify the constant as: K−1 6η 2 X X t ∆t+1 ≤ 141β 2 ∆t + 96η 2 K σl2 + 6Kσg2 + 576η 2 K 2 E∥∇f (wt )∥2 + 2 E∥ ∇fi (wi,k )∥2 . C i∈C k=0

Let 141β 2 < 1, thus we add (1 − 141β 2 )∆t on both sides and get the recursive formulation: K−1

(1 − 141β )∆ ≤ (∆ − ∆

t+1

) + 96η K

σl2 + 6Kσg2

6η 2 X X t + 576η K E∥∇f (w )∥ + 2 E∥ )∥2 . ∇fi (wi,k C 2

i∈C k=0

1 Then we multiply the 1−141β 2 on both sides, which completes the proof.

A.2.2 Expanding the Smoothness Iteration For the non-convex and L-smooth function, we firstly expand the smoothness inequality at round t as: E[f (wt+1 ) − f (wt )] ≤ E⟨∇f (wt ), wt+1 − wt ⟩ +

L E∥wt+1 − wt ∥2 {z } 2| V2t

Rethinking the Personalized Relaxed Initialization

1 X t LV2t wi,K − wt ⟩ + N 2 i∈N i 1 Xh t LV2t t−1 t = E⟨∇f (wt ), (wi,K − wi,0 ) + β(wt − wi,K ) ⟩+ C 2 = E⟨∇f (wt ),

i∈C

K−1

1 XX 1 XX LV2t t = −ηE⟨∇f (w ), ∇fi (wi,k )− ∇fi (wt ) + K∇f (wt )⟩ + C C 2 i∈C k=0 i∈C k=0 r K−1 p η 1 XX LV2t t t t 2 ∇fi (wt ) − ∇fi (wi,k ) ⟩+ = −ηKE∥f (w )∥ + E⟨ ηK∇f (w ), KC 2 t

i∈C k=0 K−1

≤ −ηKE∥f (wt )∥2 +

ηK η XX t E∥f (wt )∥2 + E∥∇fi (wt ) − ∇fi (wi,k )∥2 2 2C i∈C k=0

η E∥ 2C 2 K

−

X K−1 X

t )∥2 + ∇fi (wi,k

i∈C k=0

LV2t 2

K−1 X K−1 X LV2t ηL2 1 X X η ηK 2 t 2 t t t )∥2 + E∥f (w )∥ + E∥w − wi,k ∥ − 2 E∥ ∇fi (wi,k ≤− 2 2 C 2C K 2 i∈C k=0 i∈C k=0 | {z } V1t

K−1

≤−

XX ηK ηL2 V1t η LV2t t E∥f (wt )∥2 + − E∥ ∇fi (wi,k )∥2 + . 2 2 2 2C K 2 i∈C k=0

According to Lemma 21 and lemma 22 to bound the V1t and V2t , we can get the following recursive formula: E[f (wt+1 ) − f (wt )] K−1

≤−

XX ηK LV2t ηL2 V1t η 2 t )∥ + E∥f (wt )∥2 + − E∥ ∇f (w i i,k 2 2 2C 2 K 2 i∈C k=0

ηL2

ηK E∥f (wt )∥2 + 4Kβ 2 ∆t + 3K 2 η 2 σl2 + 6Kσg2 + 18K 3 η 2 E∥∇f (wt )∥2 2 2 L 22β 2 t 13η 2 K 2 76η 2 K 2 2 76η 2 K 2 t 2 + ∆ + σl + σg + E∥∇f (w )∥ 2 N N N N

≤−

K−1 X K−1 X η2L X X η t 2 t E∥ ∇f (w )∥ − E∥ ∇fi (wi,k )∥2 i i,k C2 2C 2 K i∈C k=0 i∈C k=0 K−1 2 XX η η L 1 38ηKL t 2 2 2 2 ≤− − 2 E∥ ∇fi (wi,k )∥ − ηK − − 9η K L E∥∇f (wt )∥2 2C 2 K C 2 N

i∈C k=0

β2L η 2 KL (13 + 3ηN KL) σl2 + 6Kσg2 + (11 + 2ηN KL) ∆t . + 2N N We can also select some special cases on learning rate to simplify the above formula. In fact, 1 in lemma 21, there is a constraint on the learning rate as η ≤ √ for K ≥ 2. 6(K−1)(2K−1)L

Rethinking the Personalized Relaxed Initialization

1 In lemma 22 and lemma 23, there is a constraint on the learning rate as η ≤ KL . To further 1 simplify the coefficients, we select η ≤ N KL to remove the constant parts. Therefore,

E[f (wt+1 ) − f (wt )] X K−1 X 78β 2 κβ ηK 2 L η 1 η 2 κKL 2 t ≤− 2 E∥ − ηL − ∇fi (wi,k )∥2 + σl + 6Kσg2 C 2K N N i∈C k=0 13β 2 κβ L 1 38ηKL 728β 2 κβ ηKL − − − 9η 2 K 2 L2 E∥∇f (wt )∥2 + ∆t − ∆t+1 , − ηK 2 N N N where κ = 8 + 78β 2 κ2β is the constant coefficient. 78β 2 κ ηK 2 L

β 1 We follow Karimireddy et al. (2020); Yang et al. (2021) and let 2K − ηL − ≥0 N 1 1 which indicates the learning rate η ≤ ≤ . Then, according to the study 2 2 78β κ K 2KL β 2KL(1+ ) N 2 728β κβ ηKL 38ηKL 1 − 9η 2 K 2 L2 term could be bounded as a of Yang et al. (2021), the 2 − N − N constant λ ∈ (0, 21 ). Therefore, we have:

13β 2 κβ L η 2 κKL 2 (σl + 6Kσg2 ) + ∆t − ∆t+1 . N N Taking the accumulation from 0 to T − 1 and let D = E f (w0 ) − f (w⋆ ) be the initial bias, we have: T −1 E f (w0 ) − f (wT ) 13β 2 κβ L 1 X κL 2 t 2 E∥f (w )∥ ≤ +η (σl + 6Kσg2 ) + ∆0 − ∆ T T ληKT λN λN ηKT ληKE∥f (wt )∥2 ≤ E[f (wt ) − f (wt+1 )] +

t=0

≤

13β 2 κβ L T 1 ηκL 2 D+ (σl + 6Kσg2 ) − ∆ . ληKT λN λN ηKT

The general analysis of the convergence only includes the impacts of the stochastic variance σl2 , and heterogeneity variance σg2 . However, F edInit could benefit from the relaxed initial by the ∆T term after T communication rounds.

A.2.3 Expanding the Smoothness Iteration under PL-condition Assumption 2 indicates the PL-condition to measure the true loss difference instead of the gradient norm. Similarly, according to the expansion of the smoothness inequality above and Assumption 2, we have µ(f (w) − f (w⋆ )) ≤ ∥∇f (w)∥2 , then: λµηKE[f (wt ) − f (w⋆ )] ≤ ληKE∥f (wt )∥2 ≤ E[f (wt ) − f (wt+1 )] +

13β 2 κβ L η 2 κKL 2 (σl + 6Kσg2 ) + ∆t − ∆t+1 . N N

Combining the terms aligned with wt and wt+1 , we have: E[f (wt+1 ) − f (w⋆ )] ≤ (1 − λµηK)E[f (wt ) − f (w⋆ )] + 27

13β 2 κβ L η 2 κKL 2 (σl + 6Kσg2 ) + ∆t − ∆t+1 . N N

Rethinking the Personalized Relaxed Initialization

1 Taking the recursion from t = 0 to T − 1 and let learning rate η ≤ λµK , we have:

E[f (wT ) − f (w⋆ )] T −1

13β 2 κβ L X ≤ (1 − λµηK) E[f (w ) − f (w )] + (1 − λµηK)T −1−t (∆t − ∆t+1 ) N T

⋆

t=0

η 2 κKL N

(σl2 + 6Kσg2 )

T −1 X

(1 − λµηK)T −1−t

t=0

= e−λµηKT E[f (w0 ) − f (w⋆ )] + 13β 2 κβ L + N

T −1 X

η 2 κKL 2 1 − (1 − λµηK)T (σl + 6Kσg2 ) N λµηK !

(1 − λµηK)T −1−t − (1 − λµηK)T −t ∆t + (1 − λµηK)T −1 ∆0 − ∆T

t=1 T −1

< e−λµηKT D +

13β 2 κβ L X ηκL 2 λµηK(1 − λµηK)T −1−t ∆t (σl + 6Kσg2 ) + λµN N t=0

T −1

≤ e−λµηKT D +

13β 2 κβ λµηKT L 1 X t ηκL 2 (σl + 6Kσg2 ) + ∆. λµN N T t=1

According to Lemma 23, we have: K−1 6κβ η 2 X X t ∆t ≤ κβ ∆t − ∆t+1 + 96η 2 κβ K σl2 + 6Kσg2 + 576κβ η 2 K 2 E∥∇f (wt )∥2 + E∥ ∇fi (wi,k )∥2 . C2 i∈C k=0

Here we first bound the gradient term as: E∥

X K−1 X

t )∥2 ≤ E∥ ∇fi (wi,k

i∈C k=0

X K−1 X

t ) − ∇fi (wt ) + ∇f (wt ) ∥2 ∇fi (wi,k

i∈C k=0 2 ≤ 2C KL2 V1t + 2C 2 K 2 E∥∇f (wt )∥2 . κ

Combining this into the recursive formulation and let Cβ = 1−48ββ 2 κβ and ηKL ≤ 1, ∆t ≤ Cβ ∆t − ∆t+1 + 132Cβ η 2 K σl2 + 6Kσg2 + 804Cβ η 2 K 2 E∥∇f (wt )∥2 . By taking the accumulation from t = 0 to T − 1 and according to the bound of gradients, T −1 T −1 X 1 X t Cβ 0 T 2 2 2 2 21 ∆ ≤ ∆ − ∆ + 132Cβ η K σl + 6Kσg + 804Cβ η K E∥∇f (wt )∥2 T T T t=0 t=0 η 804Cβ K 804κ ≤η D + Cβ η 2 K 132 + σl2 + 6Kσg2 = O + η2 . λT λN T

Therefore, by combining the : E[f (wT ) − f (w⋆ )] ≤ e−λµηKT D + η

η κL (σl2 + 6Kσg2 ) + O + η2 . λµN T

Rethinking the Personalized Relaxed Initialization

A.3 Proofs under Interpolation Conditions A.3.1 Some Important Lemmas Lemma 24 (Bounded local updates) Under Assumption 1, 4, and 6, the averaged norm of the local updates of total C clients could be bounded as: V1t ≤ 4Kβ 2 ∆t + 12a2 b2 η 2 K 3 E∥∇f (wt )∥2 .

(16)

Proof According to Lemma 21, we adopt the interpolation and have: t t t Et ∥wt − wi,k ∥2 = Et ∥wt − wi,k−1 + ηgi,k−1 ∥2 1 t t ≤ 1+ Et ∥wt − wi,k−1 ∥2 + 2η 2 KEt ∥gi,k−1 ∥2 2K − 1 1 t t ≤ 1+ ∥2 + 2η 2 Ka2 ∥∇fi (wi,k−1 ) − fi (wt ) + fi (wt )∥2 Et ∥wt − wi,k−1 2K − 1 1 2 2 2 t ∥2 + 4η 2 Ka2 b2 ∥∇f (w)∥2 + 4a η KL Et ∥wt − wi,k−1 ≤ 1+ 2K − 1 1 t ≤ 1+ ∥2 + 4a2 b2 η 2 K∥∇f (w)∥2 , Et ∥wt − wi,k−1 K −1

where the learning rate is required as η ≤

√

1 for K ≥ 2. (2K−1)(K−1)L

Similarly, we have: 1 X t ∥2 ≤ Et ∥wt − wi,k+1 C

i∈C

1 K −1

1 X t ∥2 + 4a2 b2 η 2 K∥∇f (w)∥2 . Et ∥wt − wi,k C i∈C

Unrolling the index k, we have: 1 X t ∥2 ≤ 12a2 b2 η 2 K 2 ∥∇f (w)∥2 + 4β 2 ∆t . Et ∥wt − wi,k+1 C i∈C

Summing the iteration from k = 0 to K − 1 completes the proofs.

Lemma 25 (Bounded global updates) Under Assumption 1, 4, and 6, the norm of the global update of selected N clients could be bounded as: V2t ≤ 4β 2 ∆t + 12a2 b2 η 2 K 2 ∥∇f (w)∥2 .

(17)

Proof According to Lemma 22, we modify the local iterations as: E∥wt+1 − wt ∥2 = E∥

1 X t 1 X t wi,K − wt ∥2 ≤ E ∥(wi,K − wt )∥2 ≤ 12a2 b2 η 2 K 2 ∥∇f (w)∥2 + 4β 2 ∆t . N N i∈N

i∈N

This completes the proofs.

Rethinking the Personalized Relaxed Initialization

Lemma 26 (Bounded divergence term) Under Assumption 1, 4, and 6, let the learning 1 1 rate η ≤ aKL and γβ = 1−39β 2 , the divergence term satisfies: ∆t ≤ γβ ∆t − ∆t+1 + 114γβ a2 b2 η 2 K 2 E∥∇f (wt )∥2 .

(18)

Proof Similarly, we adopt the recursive formula and upper bound the gradient term as:

E∥

K−1 X

t ηgi,k ∥2 = η 2 E∥

k=0

K−1 X

t gi,k ∥2 ≤ η 2 K

k=0

t E∥gi,k ∥2 ≤ a2 η 2 K

k=0

≤ 2a2 η 2 KL2

K−1 X

t E∥∇fi (wi,k )∥2

k=0

t E∥wi,k − wt ∥2 + 2a2 b2 η 2 K 2 E∥∇f (wt )∥2 .

k=0 1 , we have: Therefore, the same let η ≤ aKL K−1

X 1 X t ∥2 ≤ 2a2 η 2 KL2 V1t + 2a2 b2 η 2 K 2 E∥∇f (wt )∥2 ≤ 8β 2 ∆t + 26a2 b2 η 2 K 2 E∥∇f (wt )∥2 . E∥ ηgi,k C i∈C

k=0

According to the recursive formula of the divergence term in Lemma 23, K−1

∆t+1 =

X 1 X 3 X t t ∥2 ηgi,k E∥wt+1 − wi,K ∥2 ≤ 3β 2 ∆t + 3V22 + E∥ C C i∈C 2 t

i∈C

2 2 2

k=0 t

≤ 3β ∆ + 3(4β ∆ + 12a b η K ∥∇f (w)∥ ) + 3(8β ∆ + 26a2 b2 η 2 K 2 E∥∇f (wt )∥2 ) ≤ 39β 2 ∆t + 114a2 b2 η 2 K 2 E∥∇f (wt )∥2 . 1 Let 39β 2 ≤ 1 and γβ = 1−39β 2 , we can bounded the recursive formulation as:

∆t ≤ γβ ∆t − ∆t+1 + 114γβ a2 b2 η 2 K 2 E∥∇f (wt )∥2 . This completes the proofs.

A.3.2 Expanding the Smoothness Iteration Similarly, we first expand the smoothness as: K−1

E[f (wt+1 ) − f (wt )] ≤ −

XX ηK ηL2 V1t η LV2t t 2 E∥f (wt )∥2 + − E∥ ∇f (w )∥ + . i i,k 2 2 2C 2 K 2 i∈C k=0

Combining the Lemma 24, 25, and 26, we have: E[f (wt+1 ) − f (wt )] ≤ − ≤−

ηL2 V1t LV2t ηK E∥f (wt )∥2 + + 2 2 2

ηK ηL2 L E∥f (wt )∥2 + (4Kβ 2 ∆t + 12a2 b2 η 2 K 3 E∥∇f (wt )∥2 ) + (4β 2 ∆t + 12a2 b2 η 2 K 2 ∥∇f (w)∥2 ) 2 2 2 30

Rethinking the Personalized Relaxed Initialization

1 2 2 2 2 2 2 2 ≤ −ηK − 6a b ηKL − 6a b η K L E∥∇f (wt )∥2 2 + 2β 2 L γβ ∆t − ∆t+1 + 114γβ a2 b2 η 2 K 2 E∥∇f (wt )∥2 1 2 t t+1 2 2 2 2 2 2 2 2 2 = 2γβ β L ∆ − ∆ − ηK − 6a b ηKL − 114γβ a b ηK − 6a b η K L E∥∇f (wt )∥2 . 2 1 Let η ≤ KL and ζ = 12 − 6a2 b2 ηKL − 114γβ a2 b2 ηK − 6a2 b2 η 2 K 2 L2 is a constant within 1 (0, 2 ), we have:

E[f (wt ) − f (wt+1 )] 2γβ β 2 L + ∆t − ∆t+1 . ζηK ζηK Taking the accumulation from 0 to T − 1 and let D = E f (w0 ) − f (w⋆ ) be the initial bias, we have: T −1 E f (w0 ) − f (wT ) 2γβ β 2 L 2γβ β 2 L T 1 X D t 2 E∥∇f (w )∥ ≤ + ∆0 − ∆ T ≤ − ∆ . T ζηKT ζηKT ζηKT ζηKT E∥∇f (wt )∥2 ≤

t=0

A.3.3 Expanding the Smoothness Iteration under PL-condition Similarly, we adopt the Assumption 2 in the smoothness property as: ζµηKE[f (wt ) − f (w⋆ )] ≤ ζηKE∥∇f (wt )∥2 ≤ E[f (wt ) − f (wt+1 )] + 2γβ β 2 L ∆t − ∆t+1 . We have: E[f (wt + 1) − f (w⋆ )] ≤ (1 − ζµηK)E[f (wt ) − f (w⋆ )] + 2γβ β 2 L ∆t − ∆t+1 . Taking the recursion from t = 0 to T − 1, we have: T

⋆

E[f (w ) − f (w )] ≤ (1 − ζµηK) + 2γβ β L

T −1 X

(1 − ζµηK)T −1−t ∆t − ∆t+1

t=0 T −1

≤ e−ζµηKT D + 2γβ β 2 ζµηKT L

1 X t ∆ T

! .

t=0

According to Lemma 26, we have: ∆t ≤ γβ ∆t − ∆t+1 + 114γβ a2 b2 η 2 K 2 E∥∇f (wt )∥2 . By taking the accumulation from t = 0 to T − 1, T −1

1 X t γβ ∆ ≤ ∆0 − ∆T + 114γβ a2 b2 η 2 K 2 T T t=0

T −1

1 X E∥∇f (wt )∥2 T t=0

! ≤

114γβ a2 b2 ηK D. ζT

Therefore, by combining the above two inequalities we have: E[f (wT ) − f (w⋆ )] ≤ e−ζµηKT D + 228µγβ2 β 2 a2 b2 η 2 K 2 LD. 31

Rethinking the Personalized Relaxed Initialization

Appendix B. Proof of Generalization B.1 Some Notations We still let the objective be a smooth and non-convex finite-sum function. We could upper bound the stability bias in the FL. We first introduce the proof background. According to the stability analysis, we suppose there are C clients participating in the training process S as a set C = {i}C i=1 . Each client has a local dataset Si = {zj }j=1 with total S data sampled from a specific unknown distribution Di . Now we define a re-sampled dataset Sei which only differs from the dataset Si on the j ⋆ -th data. We replace the Si⋆ with Sei⋆ and keep other e From the perspective of total data, C C − 1 local dataset, which composes a new set C. ⋆ ⋆ only differs from the Ce at j -th data on the i -th client. Then, based on these two sets, our method could generate two output models, wt and w et respectively, after t training rounds. We first introduce some notations used in the proof of the generalization error. Table 11: Some abbreviations of the used terms in the proof of bounded stability error. Notation

Formulation

Description

w w e ∆t δkt

t−1 1 P t 2 C P i∈C E∥wi,K − w ∥ 1 t t ei,k ∥2 i∈C E∥wi,k − w C

parameters trained with set C parameters trained with set Ce inconsistency/divergence term in round t stability difference at k-iteration on t-round

B.2 Proofs with Assumption 3 B.2.1 Some Important Lemmas Lemma 27 (Lemma 3.11 of Hardt et al. (2016)) We follow the definition of Hardt et al. (2016); Zhou et al. (2021) to upper bound the uniform stability term after each communication round in FL paradigm. Different from their vanilla calculations, FL considers the finite-sum function on heterogeneous clients. Let non-negative objective f is L-smooth and e our method generates two models wT +1 LG -Lipschitz. After training T rounds on C and C, T +1 and w e respectively. For each data z and every t0 ∈ {1, 2, 3, · · · , S}, we have: E∥f (wT +1 ; z) − f (w eT +1 ; z)∥ ≤

N U Kt0 T + L G δK . CS

(19)

Proof Let ξ = 1 denote the event ∥wt0 − w et0 ∥ = 0 and U = supw,z f (w; z), we have: E∥f (wT +1 ; z) − f (w eT +1 ; z)∥ = P ({ξ}) E ∥f (wT +1 ; z) − f (w eT +1 ; z)∥ | ξ + P ({ξ c }) E ∥f (wT +1 ; z) − f (w eT +1 ; z)∥ | ξ c ≤ E ∥f (wT +1 ; z) − f (w eT +1 ; z)∥ | ξ + P ({ξ c }) sup f (w; z) w,z

≤ LG E ∥wT +1 − w eT +1 ∥ | ξ + U P ({ξ c }) " # 1 X T T = LG E ∥ (wi,K − w ei,K )∥ | ξ + U P ({ξ c }) C i∈C

Rethinking the Personalized Relaxed Initialization

≤

LG X T T E ∥wi,K − w ei,K ∥ | ξ + U P ({ξ c }). C i∈C

Before the j ⋆ -th data on i⋆ -th client is sampled, the iterative states are identical on both C e Let I be the index of the first different sampling, if I > t0 , then ξ = 1 holds for t0 . and C. Let χ be the event of selecting Si⋆ dataset and τ0 = t0 K + k0 be the observation moment (t0 , k0 ). Therefore, we have: P (I ≤ t0 K + k0 ) ≤

tX 0 −1 K−1 X

P (I = tK + k; χ) +

t=0 k=0

N = C

P (I = t0 K + k; χ)

k=0

tX 0 −1 K−1 XX t=0 k=0

k0 X

P (I = tK + k|χ)P (χ) +

tX 0 −1 K−1 X

k0 X X

P (I = t0 K + k|χ)P (χ)

k=0 χ

P (I = tK + k) +

t=0 k=0

k0 X

! P (I = t0 K + k)

k=0

N Kt0 . CS

This completes the proof.

Lemma 28 (Lemma 1.1 of Zhou et al. (2021)) Different from their calculations, we prove similar inequalities on f in the stochastic optimization. Under Assumption 1 and 3, the t on C. t − ηe t t − ηg t on C and w t e If at k-th gi,k =w ei,k ei,k+1 = wi,k local updates satisfy wi,k+1 i,k e then we have: iteration on each round, we sample the same data in C and C, t t t t ∥. E∥wi,k+1 −w ei,k+1 ∥ ≤ (1 + ηL)E∥wi,k −w ei,k

(20)

Proof In each round t, by the triangle inequality and omitting the same data z, we have: t t t t t t E∥wi,k+1 −w ei,k+1 ∥ = E∥wi,k − ηgi,k −w ei,k − ηe gi,k ∥ t t t t t t ∥. −w ei,k , z)∥ ≤ (1 + ηL)E∥wi,k , z) − ∇fi (w ei,k ∥ + ηE∥∇fi (wi,k −w ei,k ≤ E∥wi,k

This completes the proof.

Lemma 29 (Lemma 1.2 of Zhou et al. (2021)) Different from their calculations, we prove similar inequalities on f in the stochastic optimization. Under Assumption 1 and 3, the t t − ηg t on C and w t t − ηe t on C. e If at k-th local updates satisfy wi,k+1 = wi,k ei,k+1 =w ei,k gi,k i,k e then we have: iteration on each round, we sample the different data in C and C, t t t t E∥wi,k+1 −w ei,k+1 ∥ ≤ (1 + ηL)E∥wi,k −w ei,k ∥ + 2ησl .

(21)

Proof In each round t, let by the triangle inequality and denoting the different data as z and ze, we have: t t E∥wi,k+1 −w ei,k+1 ∥

Rethinking the Personalized Relaxed Initialization

t t t t = E∥wi,k − ηgi,k −w ei,k − ηe gi,k ∥ t t t t ≤ E∥wi,k −w ei,k ∥ + ηE∥gi,k − gei,k ∥ t t t t t t t t = E∥wi,k −w ei,k ∥ + ηE∥gi,k − ∇fi (wi,k ) − gei,k − ∇fi (w ei,k ) + ∇fi (wi,k ) − ∇fi (w ei,k )∥ t t t t ≤ E∥wi,k −w ei,k ∥ + 2ησl + ηE∥∇fi (wi,k ) − ∇fi (w ei,k )∥ t t ≤ (1 + ηL)E∥wi,k −w ei,k ∥ + 2ησl .

This completes the proof.

B.2.2 Bounded Uniform Stability According to Lemma 27, we firstly bound the recursive stability on k in one round. If the sampled data is the same, we can adopt Lemma 28. Otherwise, we adopt Lemma 29. Thus we can bound the second term in Lemma 27 as: 1 X t t ∥|ξ ei,k+1 E ∥wi,k+1 − w C i∈C 1 X t 1 X t t t = P (z) ∥ | ξ, z + P (e z) ∥ | ξ, ze ei,k+1 ei,k+1 E ∥wi,k+1 − w E ∥wi,k+1 − w C C i∈C i∈C X 1 1 t t ≤ ∥|ξ + (1 + ηL)E ∥wi,k −w ei,k (1 + ηL)E ∥wit⋆ ,k − w eit⋆ ,k ∥ | ξ + 2ησl C CS

t = δk+1

i∈C

≤ (1 + ηL) δkt +

2ησl . CS

Balancing the LHS and RHS, we have the following recursive formulation: 2σl 2σl t t ≤ (1 + ηL) δk+1 + . δk+1 + CSL CSL Therefore, in one single communication round, by generally defining learning rate η = ηkt , 2σl t δK + ≤ CSL

K−1 Y

(1 + ηkt L)

δ0t +

k=0

2σl CSL

t−1 The next important relationship is to measure the δK and δ0t . According to the update t−1 t = w t + β(w t − w rule wi,0 i,K ), we have the difference follows: t−1 t−1 t t wi,0 −w ei,0 = wt − w et + β(wt − wi,K ) − β(w et − w ei,K ) t−1 t−1 = (1 + β)(wt − w et ) − β(wi,K −w ei,K )

By taking the expectation on the l2 norm, we have: δ0t =

1 X 1+β X β X t−1 t−1 t−1 t t E∥wi,0 −w ei,0 ∥≤ E∥wt − w et ∥ + E∥wi,K −w ei,K ∥ ≤ (1 + 2β)δK . C C C i∈C

i∈C

Rethinking the Personalized Relaxed Initialization

Q t t By denoting ϕ(t) = K−1 k=0 (1 + ηk L) be the combination of learning rate ηk , we can provide an upper bound of the recursive formulation as: ! K−1 Y 2σl 2σl 2σl t−1 t t ≤ ϕ(t) (1 + 2β) δK . δK + ≤ + (1 + ηk L) δ0t + CSL CSL CSL k=0

To balance the constant part, assuming the learning rate is decayed by communication round t which indicates ϕ(t) ≤ ϕ(t − 1) and let 2β ≤ ϕ(t−1) ϕ(t) − 1 be the upper bound, then we have the following recursive formulation: ϕ(t) − 1 2σl ϕ(t − 1) − 1 2σl t−1 t δK + ≤ ϕ(t − 1) δK + . (1 + 2β)ϕ(t) − 1 CSL (1 + 2β)ϕ(t − 1) − 1 CSL Unrolling from t0 − 1 to T , we have: ! T Y 2σl ϕ(T + 1) − 1 2σl ϕ(t0 − 1) − 1 t0 −1 T +1 δK ≤ − ϕ(τ ) δK + (1 + 2β)ϕ(t0 − 1) − 1 CSL (1 + 2β)ϕ(T + 1) − 1 CSL τ =t0 −1 ! ! T T K−1 Y Y Y 2σl ϕ(t0 − 1) − 1 2σl ϕ(τ ) (1 + ηkτ L) ≤ ≤ (1 + 2β)ϕ(t0 − 1) − 1 CSL (1 + 2β)CSL τ =t0 −1 τ =t0 −1 k=0 ! T K−1 X X 2σl ηkτ L ≤ exp . (1 + 2β)CSL τ =t0 −1 k=0

Let the learning rate be the same selection as it in the optimization of O( 1t ) = ct , we have: ! ! T −1 K−1 T −1 X X X 2σ cKL 2σl l T δK ≤ exp ηkτ L ≤ exp (1 + 2β)CSL τ (1 + 2β)CSL τ =t0 −1 k=0 τ =t0 −1 Z T cKL 2σl cKL 2σl T ≤ exp dτ = . (1 + 2β)CSL τ (1 + 2β)CSL t 0 τ =t0 To summarize the above inequalities and the Lemma 27, we have: E∥f (w

T +1

; z) − f (w e

T +1

N U Kt0 2σl LG N U Kt0 T + LG δK ≤ + ; z)∥ ≤ CS CS (1 + 2β)CSL

T t0

cKL .

Furthermore, to minimize the stability errors, we can select the proper observation point i 1 h cKL 1+cKL 2σl LG T 1+cKL and then we have: t0 = (1+2β)N U KL E∥f (w

T +1

; z) − f (w e

T +1

1 1+cKL cKL 2 2σl LG ; z)∥ ≤ (N U KT ) 1+cKL . CS (1 + 2β)L

B.3 Proofs with Interpolation Conditions B.3.1 Some Important Lemmas t t −ηg t Lemma 30 Under Assumption 1 and 4, and 7, the local updates satisfy wi,k+1 = wi,k i,k e If at k-th iteration on each round, we sample the on C and w et = w et − ηe g t on C. i,k+1

i,k

e then we have: different data in C and C, t t t t E∥wi,k+1 −w ei,k+1 ∥ ≤ E∥wi,k −w ei,k ∥ + 2abηLG .

(22)

Rethinking the Personalized Relaxed Initialization

Proof Similar to Lemma 28, we directly upper bound the recursive formulation as: t t t t t t t t t t E∥wi,k+1 −w ei,k+1 ∥ = E∥wi,k − ηgi,k −w ei,k − ηe gi,k ∥ ≤ E∥wi,k −w ei,k ∥ + ηE∥∇fi (wi,k , z) − ∇fi (w ei,k , ze)∥ t t ≤ E∥wi,k −w ei,k ∥ + 2abηLG .

This completes the proofs.

B.3.2 Bounded Uniform Stability T term. We first Similar to the last section, we need to provide the upper bound of the δK rebuild the recursive formulation according to Lemma 30 and above conclusion, t δk+1 ≤ δkt +

abηLG . CS

Taking the accumulation from k = 0 to K − 1 in a single round and let φ(t) = we have:

PK−1

t k=0 ηk ,

K−1

t δK ≤ δ0t +

abLG X t abLG t−1 + ηk ≤ (1 + 2β)δK φ(t). CS CS k=0

Similarly, according to the factor of φ(t) ≤ φ(t − 1), let β t be related to t and be decayed φ(t−1) by the round t, further we assume the β satisfies φt β t ≤ β t−1 , we have: t δK +

abLG abLG abLG t−1 t−1 t t + + φ(t) ≤ (1 + 2β ) δ φ(t) ≤ (1 + 2β ) δ φ(t − 1) . K K 2β t CS 2β t CS 2β t−1 CS

Taking the accumulation from t = 1 to T − 1 and adopting the factor of φ(0) = cK, we have: ! T P Y abLG t abcLG K T 2 T t=1 β δK ≤ (1 + 2β t ) φ(0) ≤ e . 0 2β CS 2β 0 CS t=1

Lemma 30 does not identify the data sample, therefore we can revise Lemma 27 as: T E∥f (wT +1 ; z) − f (w eT +1 ; z)∥ ≤ LG δK ≤ e2

t=1 β

abcL2G K . 2β 0 CS

References D. A. E. Acar, Y. Zhao, R. M. Navarro, M. Mattina, P. N. Whatmough, and V. Saligrama. Federated learning based on dynamic regularization. arXiv preprint arXiv:2111.04263, 2021. M. Asad, A. Moustafa, and T. Ito. Fedopt: Towards communication efficiency and privacy preservation in federated learning. Applied Sciences, 10(8):2864, 2020. 36

Rethinking the Personalized Relaxed Initialization

P. L. Bartlett, D. J. Foster, and M. J. Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017. D. Caldarola, B. Caputo, and M. Ciccone. Improving generalization in federated learning 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. D. Caldarola, B. Caputo, and M. Ciccone. Window-based model averaging improves generalization in heterogeneous federated learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2263–2271, 2023. Z. Charles and J. Konečnỳ. Convergence and accuracy trade-offs in federated learning and meta-learning. In International Conference on Artificial Intelligence and Statistics, pages 2575–2583. PMLR, 2021. R. Das, S. Kale, Z. Xu, T. Zhang, and S. Sanghavi. Beyond uniform lipschitz condition in differentially private optimization. In International Conference on Machine Learning, pages 7066–7101. PMLR, 2023. A. Defazio, F. Bach, and S. Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014. F. Farnia, J. M. Zhang, and D. Tse. Generalizable adversarial training via spectral normalization. arXiv preprint arXiv:1811.07457, 2018. L. Gao, H. Fu, L. Li, Y. Chen, M. Xu, and C.-Z. Xu. Feddc: Federated learning with non-iid data via local drift decoupling and correction. arXiv preprint arXiv:2203.11751, 2022. Y. Gong, Y. Li, and N. M. Freris. Fedadmm: A robust federated deep learning framework with adaptivity to system heterogeneity. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2575–2587. IEEE, 2022. E. Gorbunov, F. Hanzely, and P. Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 3556– 3564. PMLR, 2021. M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225–1234. PMLR, 2016. K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016. K. Hsieh, A. Phanishayee, O. Mutlu, and P. Gibbons. The non-iid data quagmire of decentralized machine learning. In International Conference on Machine Learning, pages 4387–4398. PMLR, 2020. 37

Rethinking the Personalized Relaxed Initialization

T.-M. H. Hsu, H. Qi, and M. Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06335, 2019. T. Huang, L. Shen, Y. Sun, W. Lin, and D. Tao. Fusion of global and local knowledge for personalized federated learning. arXiv preprint arXiv:2302.11051, 2023. R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013. P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 14(1–2):1–210, 2021. B. Karimi, P. Li, and X. Li. Layer-wise and dimension-wise locally adaptive federated learning. arXiv preprint arXiv:2110.00532, 2021. S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132–5143. PMLR, 2020. M. Karzand and R. D. Nowak. Maximin active learning with data-dependent norms. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 871–878. IEEE, 2019. H. Kim, G. Papamakarios, and A. Mnih. The lipschitz constant of self-attention. In International Conference on Machine Learning, pages 5562–5571. PMLR, 2021. A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009. T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429–450, 2020. T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi. Don’t use large mini-batches, use local sgd. arXiv preprint arXiv:1808.07217, 2018. Y. Liu, Y. Sun, Z. Ding, L. Shen, B. Liu, and D. Tao. Enhance local consistency in federated learning: A multi-step inertial momentum approach. arXiv preprint arXiv:2302.05726, 2023. V. V. Mai and M. Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pages 7325–7335. PMLR, 2021. G. Malinovskiy, D. Kovalev, E. Gasanov, L. Condat, and P. Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learning, pages 6692–6701. PMLR, 2020. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communicationefficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017. 38

Rethinking the Personalized Relaxed Initialization

B. Neyshabur, S. Bhojanapalli, and N. Srebro. A pac-bayesian approach to spectrallynormalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564, 2017. E. Ozfatura, K. Ozfatura, and D. Gündüz. Fedadc: Accelerated federated learning with drift control. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 467–472. IEEE, 2021. V. Patel and A. S. Berahas. Gradient descent in the absence of global lipschitz continuity of the gradients: Convergence, divergence and limitations of its continuous approximation. arXiv preprint arXiv:2210.02418, 2022. Z. Qu, X. Li, R. Duan, Y. Liu, B. Tang, and Z. Lu. Generalized federated learning via sharpness aware minimization. In International Conference on Machine Learning, pages 18250–18280. PMLR, 2022. S. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečnỳ, S. Kumar, and H. B. McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020. A. Reisizadeh, F. Farnia, R. Pedarsani, and A. Jadbabaie. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Systems, 33: 21554–21565, 2020. N. Shi, F. Lai, R. A. Kontar, and M. Chowdhury. Fed-ensemble: Improving generalization through model ensembling in federated learning. arXiv preprint arXiv:2107.10663, 2021. Y. Shi, Y. Liu, K. Wei, L. Shen, X. Wang, and D. 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, 2023a. Y. Shi, L. Shen, K. Wei, Y. Sun, B. Yuan, X. Wang, and D. Tao. Improving the model consistency of decentralized federated learning. arXiv preprint arXiv:2302.04083, 2023b. K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014. H. Sun, L. Shen, Q. Zhong, L. Ding, S. Chen, J. Sun, J. Li, G. Sun, and D. Tao. Adasam: Boosting sharpness-aware minimization with adaptive learning rate and momentum for training deep neural networks. arXiv preprint arXiv:2303.00565, 2023a. Y. Sun, L. Shen, S. Chen, L. Ding, and D. Tao. Dynamic regularized sharpness aware minimization in federated learning: Approaching global consistency and smooth landscape. In International conference on machine learning, pages 32991–33013. PMLR, 2023b. Y. Sun, L. Shen, T. Huang, L. Ding, and D. Tao. Fedspeed: Larger local interval, less communication round, and higher generalization accuracy. arXiv preprint arXiv:2302.10429, 2023c. Y. Sun, L. Shen, H. Sun, L. Ding, and D. Tao. Efficient federated learning via local adaptive amended optimizer with linear speedup. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(12):14453–14464, 2023d. 39

Rethinking the Personalized Relaxed Initialization

Y. Sun, L. Shen, and D. Tao. Understanding how consistency works in federated learning via stage-wise relaxed initialization. Advances in Neural Information Processing Systems, 36:80543–80574, 2023e. Y. Sun, L. Shen, and D. Tao. A-fedpd: aligning dual-drift is all federated primal-dual learning needs. Advances in Neural Information Processing Systems, 37:85742–85777, 2024. Y. Tan, G. Long, L. Liu, T. Zhou, Q. Lu, J. Jiang, and C. Zhang. Fedproto: Federated prototype learning across heterogeneous clients. In AAAI Conference on Artificial Intelligence, volume 1, 2022. S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence of sgd for overparameterized models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pages 1195–1204. PMLR, 2019. H. Wang, S. Marella, and J. Anderson. Fedadmm: A federated primal-dual algorithm allowing partial participation. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 287–294. IEEE, 2022a. J. Wang, V. Tantia, N. Ballas, and M. Rabbat. Slowmo: Improving communication-efficient distributed sgd with slow momentum. arXiv preprint arXiv:1910.00643, 2019. J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:7611–7623, 2020. J. Wang, Z. Xu, Z. Garrett, Z. Charles, L. Liu, and G. Joshi. Local adaptivity in federated learning: Convergence and consistency. arXiv preprint arXiv:2106.02305, 2021. Y. Wang, W. Liu, B. Wang, et al. On the convergence of sgd under the over-parameter setting. 2022b. B. E. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281–6292, 2020. J. Xu, S. Wang, L. Wang, and A. C.-C. Yao. Fedcm: Federated learning with client-level momentum. arXiv preprint arXiv:2106.10874, 2021. S. Yagli, A. Dytso, and H. V. Poor. Information-theoretic 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. H. Yang, M. Fang, and J. Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11203, 2021. X. Zhang, M. Hong, S. Dhople, W. Yin, and Y. Liu. Fedpd: A federated learning framework with adaptivity to non-iid data. IEEE Transactions on Signal Processing, 69:6055–6070, 2021. 40

Rethinking the Personalized Relaxed Initialization

Y. Zhang, W. Zhang, S. Bald, V. Pingali, C. Chen, and M. Goswami. Stability of sgd: Tightness analysis and improved bounds. In Uncertainty in Artificial Intelligence, pages 2364–2373. PMLR, 2022. P. Zhou, H. Yan, X. Yuan, J. Feng, and S. Yan. Towards understanding why lookahead generalizes better than sgd and beyond. Advances in Neural Information Processing Systems, 34:27290–27304, 2021. S. Zhou and G. Y. Li. Federated learning via inexact admm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.

Record · ID 13096 · SHA-256 65681c5f06ca5997
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.