Decentralized Personalized Federated Learning based on a Conditional Sparse-to-Sparser Scheme
Qianyu Long Qiyuan Wang Christos Anagnostopoulos Daning Bi















Decentralized Personalized Federated Learning based on a Conditional ‘Sparse-to-Sparser’ Scheme
    
    Qianyu Long, Qiyuan Wang, Christos Anagnostopoulos,
    Daning Bi
    Qianyu Long, Qiyuan Wang, and Christos Anagnostopoulos are with the School of Computing Science, University of Glasgow, Glasgow G12 8QQ, United Kingdom (e-mail: christos.anagnostopoulos@glasgow.ac.uk & q.long.1@research.gla.ac.uk).
    Daning Bi is with the College of Finance and Statistics, Hunan University Finance Campus, Changsha City, China.
    


    
=================================================================================================================================================================================================================================================================================================================================================================================================================================================






Decentralized Federated Learning (DFL) has become popular due to its robustness and avoidance of centralized coordination. In this paradigm, clients actively engage in training by exchanging models with their networked neighbors. However, DFL introduces increased costs in terms of training and communication. Existing methods focus on minimizing communication often overlooking training efficiency and data heterogeneity. To address this gap, we propose a novel sparse-to-sparser training scheme: 
DA-DPFL. DA-DPFL initializes with a subset of model parameters, which progressively reduces during training via dynamic aggregation and leads to substantial energy savings while retaining adequate information during critical learning periods. 

Our experiments showcase that DA-DPFL substantially outperforms DFL baselines in test accuracy, while achieving up to 5 times reduction in energy costs. We provide a theoretical analysis of DA-DPFL's convergence by solidifying its applicability in decentralized and personalized learning. The code is available at:https://github.com/EricLoong/da-dpfl



Personalized Federated Learning, Model Pruning, Sparsification, Decentralized Federated Learning.




§ INTRODUCTION

Large-scale Deep Neural Networks (DNNs) have gained significant attention due to their high performance on complex tasks. 
The Vision Transformer, ViT-4 <cit.> by Google is a prime example of achieving a new state-of-the-art on ImageNet <cit.> with top-1 accuracy of 90.45%. 
The success of centralized training of DNNs motivated the counterpart decentralized training based on Federated Learning (FL) <cit.>. FL involves distributed clients' data in DNN training addressing challenges like privacy <cit.> by transmitting only model weights and/or gradients instead of raw data. However, FL faces two fundamental challenges <cit.>: expensive communication and statistical heterogeneity. Reducing the communication cost due to clients disseminating big-sized DNNs can be achieved by compressing information exchange while attaining model convergence. 
Gradient sparsification and quantization <cit.> significantly reduce communication cost. 
Model pruning <cit.> not only reduces communication cost but also accelerates local training. To alleviate statistical heterogeneity and cope with non-independent and identically distributed (non-i.i.d.) data, Personalized FL (PFL) emerges to allow a local (personalized) model per client rather than a global one shared among clients. Though PFL is still in its infancy, a plethora of works <cit.> shows its efficiency in data heterogeneity. 

FL is classified into Centralized FL (CFL) and Decentralized FL (DFL), differentiated by clients' communication methods during training. CFL, exemplified by FedAvg <cit.>, involves a central server coordinating client model aggregation, posing risks of server-targeted attacks and a single point of failure. In contrast, DFL <cit.> offers privacy enhancements and risk mitigation by enabling direct, dynamic, non-hierarchical client interactions within various network topologies such as line/bus, ring, star, or mesh.





To address communication cost, model/gradient compression-based DFL has been proposed <cit.>, where local models are pruned/quantized to achieve competitive performance similar to dense (non-pruned) models.









These approaches match communication costs for the busiest servers as CFL, having higher overall communication and training costs attributed to decentralized hybrid topology (each client can act as a server). 
Although DFL with pointing protocol, i.e., learning from previously trained models of clients in a sequential line one-peer-to-one-peer, can expedite convergence <cit.>, it struggles with data heterogeneity.





Overall, while FL frameworks target learning from decentralized data, they often overlook either statistical heterogeneity, as in DFL, or efficient training and communication, as in PFL. This highlights the need for an integrated approach that effectively balances communication, training efficiency, and data heterogeneity across different FL paradigms.

We contribute with a novel Dynamic Aggregation Decentralized PFL framework, coined as DA-DPFL, 
that (i) further reduces communication and training costs, (ii) expedites convergence, and (iii) overcomes data heterogeneity. 
DA-DPFL incorporates two main elements: a fair dynamic scheduling for aggregation of personalized models and a dynamic pruning policy. The innovative scheduling policy allows clients in DA-DPFL to reuse trained models within the same communication round, which significantly accelerates convergence. Moreover, DA-DPFL involves optimized pruning timing to conduct further pruning, i.e., sparse-to-sparser training, which does not violate clients' computing capacities while achieving communication, training, and inference efficiency. The trade-off is the controlled latency incurred as some clients await the completion of tasks by their neighbors. We comprehensively assess and compare DA-DPFL with baselines in CFL and DFL to showcase the advantage of dynamic pruning and aggregation in PFL. 

Our major technical contributions are:
(i) We innovatively align a dynamic aggregation framework to allow clients reuse previous 
models for local training within the same communication round. 
(ii) By measuring model compressibility, we propose a further pruning strategy, which effectively accommodates and extends existing sparse training techniques in DFL. 
(iii) Compared with both CFL and DFL baselines, 
our comprehensive experiments showcase that DA-DPFL achieves comparative or even superior model performance across various tasks and DNN architectures. 
(iv) The proposed learning method with dynamic aggregation achieves the highest energy and communication efficiency. 
(v) We provide a theoretical convergence analysis, which aligns with experimental observations.



§ RELATED WORK

Efficient FL: In distributed ML, communication and training costs are significant challenges. 
LAQ <cit.> and DGC <cit.> methods reduce communication costs through gradient quantization and deep gradient compression techniques, respectively. Model compression, notably pruning, plays a key role in alleviating device storage constraints, as demonstrated by PruneFL <cit.>, FedDST <cit.>, and FedDIP <cit.>, which achieve sparsity in model pruning. 
pFedGate <cit.> addresses the challenges by adaptively learning sparse local models with a trainable gating layer, enhancing model capacity and efficiency. FedPM <cit.> and FedMask <cit.> focus on efficient model communication using probability masks; with FedMask providing personalized, sparse DNNs for clients and FedPM employing Bayesian aggregation. However, while significant advancements have been made in reducing communication costs <cit.>, 
only a few methods <cit.> address reducing training costs through sparse mask learning.

Personalized FL: In FL, addressing data heterogeneity necessitates personalization of global model as achieved by e.g., FedMask <cit.>, FedSpa <cit.>, and DisPFL <cit.> using personalized masks. 
Ditto <cit.> offers a fair personalization framework through global-regularized multitask FL, 
while FOMO <cit.> focuses on first-order optimization for personalized learning. 
FedABC <cit.> employs a `one-vs-all' strategy and binary classification loss for class imbalance and unfair competition, 
while FedSLR <cit.> integrates low-rank global knowledge for efficient downloading during communication. 
However, such approaches increase training costs highlighting the need for more efficient training methods.

Decentralized FL: Since the work <cit.>, DFL emerged as a robust distributed learning paradigm, enabling clients to collaboratively train models with their neighbors, thereby enhancing privacy and reducing reliance on central servers. 
In DFL, increased client interaction leads to methods like DFedAvgM <cit.>, which extends FedAvg to decentralized context with momentum SGD, and BEER <cit.> for non-convex optimization that enhances convergence through communication compression and gradient tracking. GossipFL <cit.> uses bandwidth information to create a gossip matrix allowing communication with one peer using sparsified gradients, reducing communication. DFedSAM <cit.> considers utilizing Sharpness-Aware-Minimization (SAM) optimizer, while DisPFL <cit.> utilizes RigL-like pruning in decentralized sparse training to lower generalization error and communication costs. 







§ PROBLEM FUNDAMENTALS & PRELIMINARIES


Consider a distributed system with K clients indexed by 𝒦 = {1, 2, …, K}. The clients are 
networked given a topology represented by a graph 𝒢(𝒦, 𝐕), where the adjacency matrix 
𝐕=[v_i,j] ∈ℝ^K× K <cit.> 

defines the neighborhood 𝒢_k of client k ∈𝒦, i.e., subset of clients that directly communicate with  client k, 𝒢_k = {i ∈𝒦: v_i,k > 0}. 
An entry v_i,k = 0 indicates no communication from client i to client k, i.e., i ∉𝒩_k. 
Note that v_i,k=v_k,i may not always be valid for i≠ k.
The topology can be static or dynamic. 
In our case, we adopt dynamic communication among clients, i.e., entries in 𝐕^t depend on (discrete) time instance t ∈𝕋 = {1, 2, …}.
We define a time-varying and non-symmetric network topology via 𝐕^t=[v_i,j^t] ∈ℝ^K× K accommodating temporal neighborhood 𝒢_k^t for k-th client. 


We consider a scalable DFL setting with K clients (e.g., mobile devices, IoT devices)
with a time-varying topology. 
Each client k ∈𝒦 possesses local data 𝒟_k = {(𝐱,y)} of input-output pairs 𝐱∈𝒳 and y ∈𝒴, and communicates with neighbours 𝒢_k^t exchanging models. 
The problem formulation of PFL (adopting the formulation in <cit.>)

seeks to find the models ω_k, ∀ k ∈𝒦, that minimize:

    min_{ω_k}, k∈[1,K] f({ω_1}_k=1^K) = 1/K∑_k=1^K F_k(ω_k),

where F_k(ω_k) = 𝔼[ℒ(ω_k; (𝐱,y)) | (𝐱,y) ∈𝒟_k] with expected loss function ℒ(.;.) between actual and predicted output given local data 𝒟_k.
We depart from ((<ref>)) by adopting model pruning in DFL aiming at eliminating 
non-essential model weights. This is achieved by utilizing a binary mask 𝐦 over a model. 
Hence, the pruning-based (masked) PFL problem is succinctly formulated as finding the global model ω and individual masks 𝐦_k, ∀ k ∈𝒦:

    min_ω, {𝐦_k}, k∈[1,K] f({ω_k}_k=1^K) = 1/K∑_k=1^K F_k(ω⊙𝐦_k),

where F_k(ω⊙𝐦_k) = 𝔼[ℒ(ω⊙𝐦_k; (𝐱,y)) | (𝐱,y) ∈𝒟_k]; ⊙ represents the Hadamard product (element-wise product) of two matrices. 
The individual mask 𝐦_k denotes a pruning operator specific to client k. 
Given mask 𝐦_k, the sparsity s_k∈ [0,1] of 𝐦_k indicates the proportion of non-zero model weights among all weights. 

The goal of (<ref>) is to seek a global model ω and individual masks 𝐦_k such that the optimized personalized model for each client k ∈𝒦 is given by ω_k =ω⊙𝐦_k, while clients communicate at time t only with their neighbors 𝒢_k^t given  the time-varying 𝐕^t.



§ THE DA-DPFL FRAMEWORK



 §.§ Overview

We introduce the DA-DPFL framework to tackle the problem in Eq. (<ref>). 
DA-DPFL not only addresses data heterogeneity efficiently via masked-based PFL but also significantly improves convergence speed by incorporating a fair dynamic communication protocol. Sequential pointing line communication adopts an one-peer-to-neighbors mechanism striking the balance between computational parallelism and delay. As described in <cit.>, two sequential pointing DFL strategies, continual and aggregate, facilitate knowledge dissemination in distributed learning. 
However, certain challenges are evident as discussed in <cit.> such as data heterogeneity and non-scalability.





Furthermore, the decision on when to apply pruning during training is crucial <cit.>. While early pruning reduces computational cost, it may adversely affect performance. Choosing an optimal pruning time can enhance both training and communication efficiency, often with minimal performance degradation or even improvements. As elaborated in <cit.> and <cit.>, a sparser model tends to have a reduced generalization bound characterized by smaller discrepancy between training and test errors. Finding sparser models with lower generalization error, DA-DPFL introduces an innovative dynamic pruning strategy. 
DA-DPFL addresses data heterogeneity while decreasing the number of communication rounds needed for convergence and achieving high model performance. This comes at a small and controllable delay in 
learning from the trained models. The processes of DA-DPFL are depicted in Fig. <ref> and Algorithm <ref>. 


The relationship between model sparsity and performance links to the complexity of the task and model architecture. Pruning becomes a necessary solution when there is model redundancy for the given task, aligned with the findings in <cit.> and <cit.>. If the model is non-redundant, an increased sparsity invariably affects model performance. 






 §.§ Learning Scheduling Policy

In this section, we outline the scheduling policy adopted for client participation within our framework. This applies to any topological connection, such as a ring or fully-connected network, where neighborhood sets, denoted as 𝒢_k^t,k∈{1, 2, …, K}, are established. It is important to note that DA-DPFL is particularly suited for a time-varying connected topology while remains flexible to accommodate a static topology, represented as 𝒢_k. At the start of each communication round, denoted by t, reuse indexes for neighborhood sets, 𝒩_k^t, are randomly assigned to M clients, where |𝒢_k^t|=|𝒩_k^t| = M < K and 𝒢_k^tπ_k^t↔𝒩_k^t, where π_k^t is a random bijection mapping. Given 𝒢_k^t and 𝒩_k^t are both discrete sets,

    i = π_k^t(j),

with index i ∈𝒩_k^t and j ∈𝒢_k^t.

It is crucial to acknowledge that 𝒩_k^t may be equal with 𝒢_k^t if sets are randomly generated. For simplicity, we let 𝒩_k^t= 𝒢_k^t in Fig. <ref>, where client k is indexed with reuse index k. 
The introduction of 𝒩_k^t serves to emphasize the independence in the generation of reuse indexes, which are pivotal in guiding the dynamic aggregation process.
Note: the criteria for establishing 𝒢_k^t are influenced by factors e.g., network bandwidth, geographical location, link availability; however, 𝒩_k^t is independent of these factors. We reassign client indices for each training round.

 



Within DA-DPFL, a client k may defer the reception of models from some neighbors, contingent upon 𝒩_k^t. We denote 𝒩_k^t for each client k into two subsets based on the reuse indices of neighboring clients: 
(a) a prior client subset 𝒩_(a)k^t = {n_k^t≤ k : n_k^t∈𝒩_k^t}, and 
(b) a posterior client subset 𝒩_(b)k^t = {n_k^t > k : n_k^t∈𝒩_k^t} (refer to Fig. <ref> Top). Should 𝒩_(b)k^t = ∅, implying 𝒩_(a)k^t = 𝒩_k^t, client k awaits the slowest client within 𝒩_k^t before commencing model aggregation and local dataset training 𝒟_k. To enhance scalability, we introduce a threshold to allow waiting for, at most, N fastest clients in 𝒩_(a)k^t, where |𝒩_(a)k^(*)t| =N≤ M. Then, 𝒩_(a)k^(*)t∪𝒩_(b)k^(*)t=𝒩_k^t. Conversely, absence of a prior client set (𝒩_(a)k^(*)t = ∅) enables client k to incorporate models from 𝒩_(b)k^(*)t without delay, as illustrated by nodes 1, 2, and 4 in Fig. <ref>. Based on the bijection mapping between 𝒩_k^t and 𝒢_k^t, 𝒢_(a)k^(*)t is obtained. 
Therefore, DA-DPFL achieves a hybrid scheme between continual learning with delayed aggregation and immediate aggregation, i.e., dynamic aggregation. Continual learning is achieved by gradual learning of the models from clients in client k's prior set. The benefit obtained is the sequential knowledge transfer from clients in the prior set. 
This comes at the expense of a potential delay to client k for aggregating the models from 𝒢^(*)t_k(a). On the other hand, the models of the clients from the posterior set are independently sent to client k, without any delay achieving training parallelism.



    
    DA-DPFL learning schedule diverges from traditional FL paradigms.
    
    In our example, at time t, nodes {1,2,4} engage in simultaneous (parallel) training, while nodes {3,5,6} await model reuse from preceding clients. This methodology 
    
    allows subsequent nodes to train concurrently with preceding ones, as shown by nodes {5,6} training in tandem with node 3. 
    The introduction of a cutoff value N endows our waiting policy with controllability. 
    If N=0, DA-DPFL operates as a parallel FL system with sparse training; while N=M=K transits DA-DPFL to a sequential FL. 















 






















 §.§ Time-optimized Dynamic Pruning Policy

Alongside scheduling of local training and gradual model aggregation achieved by prior and posterior neighbors per client, we introduce a dynamic pruning policy. The initial mask 𝐦_k^0, ∀ k, is set up in accordance with the Erdos-Renyi Kernel (ERK) distribution <cit.>. Subsequently, masks are removed and re-grown based on the importance scores, which are computed from the magnitude of model weights and gradients. This strategy is an extension of the centralized RigL <cit.> to DA-DPFL as elaborated in Appendix <ref> (line:24) in Algorithm <ref>. We devise a method that is orthogonal to other fixed-sparsity training methods like 
RigL facilitating further pruning.
The Sparsity-informed Adaptive Pruning (SAP) in <cit.> introduces the PQ Index (PQI) to 
assess the potential `compressibility' of a DNN (line:19; Appendix <ref>). 
DA-DPFL leverages PQI by integrating within DFL, which addresses the heterogeneity of various local models by adaptively pruning different models. 


In centralized learning, EarlyCrop's analysis <cit.> on pruning scheduling relies on sufficient information during critical learning periods, while CriticalFL <cit.> advocates for an early doubling of information transmission. EarlyCrop leverages between gradient flow and neural tangent kernel to facilitate seamless transition into model pruning. We adjust the pruning time detection score as:

    |Δ_0^t-Δ_0^t-1|/|Δ_0^1|<δ_pr; Δ_0^t:=ω^t-ω^0^2,

where δ_pr is a predefined threshold. 
In DA-DPFL with K clients, we introduce a voting majority rule, where the client k's vote is defined as:

    v_t(k) = 
     
    1    if |Δ_0^t(k)-Δ_0^t-1(k)|/|Δ_0^1(k)|<δ_pr, 
    
    0    otherwise.

Hence, the first time to prune is determined by K clients as: 


    t^*=min{ t : 1/K∑_k=1^Kv_t(k) < δ_v}

where δ_v represents the ratio threshold for voting. Given the first pruning time t^*, DA-DPFL determines the frequency of pruning for rounds t>t^*. Based on the influence of early training phase, a.k.a. critical learning period <cit.> on the local curvature of the loss function in DNNs, our strategy permits a low pruning frequency during the initial stages which intensifies pruning as model approaches convergence. This balance between communication overhead and model performance yields an optimal pruning frequency that varies across tasks and model architectures. We define the pruning frequency, i.e., the gap between consecutive pruning events, and in turn the pruning times by non-evenly dividing the rest of the horizon T-t^*:

    I_τ:= ⌈t^*+b/c^τ-1⌉, τ∈{ℤ_≥1}.
 
Parameter b > 0 delays the optimal first pruning time, c>0 is a scaling factor to adjust pruning frequency. The p-th pruning time t_p with t_p > t^*, is t_p=∑_τ=1^pI_τ obtaining the pruning times set 𝒯 = {t_1, …, t_p: t^* < t_p < T}. 



 §.§ Masked-based Model Aggregation

For notation compatibility, following the model aggregation operator in DisPFL<cit.> and FedDST <cit.>, the client k's aggregated model ω_k^t derived from the models of client k's neighbors in 𝒢^t_k at round t based on masked local model is:

    ω_k^t=(∑_j∈𝒢_k+^tω_j^t/∑_j∈𝒢_k+^t𝐦_j^t)⊙𝐦_k^t,

where 𝒢_k+^t = 𝒢_k^t∪{k} is client k's neighborhood including client k. The local training rounds τ∈ E_l based on the obtained ω_k^t is:


ω_k,τ+1^t=ω_k,τ^t-η (𝐠_k,τ^t⊙𝐦_𝐤^𝐭),

where 𝐠_k,τ^t is the gradient of local loss function F_k(·) w.r.t. ω_k,τ^t.



§ THEORETICAL ANALYSIS






    μ-Lipschitz-continuity: ∀ω_1, ω_2∈ℝ^d, ∀ k ∈| K |, μ∈ℝ:
    
        ∇ f_k(ω_1) - ∇ f_k(ω_2)≤μω_1 - ω_2.
    





    

    



    Bounded variance for gradients: <cit.> ∀ k ∈| K | and  ω∈ℝ^d:
    
    𝔼[∇f̂_k(ω)-∇ f_k(ω)^2]≤σ^2_l,
    1/K∑_k=1^K∇ f_k(ω)-∇ f(ω)^2≤σ^2_g,
    1/K∑_k=1^K∇f̃_k(ω)-∇ f(ω)^2≤σ^2_p,

    f̂(·) is the estimated gradients from training data; f̃(·) is personalized global gradients. 


    
    The aggregated model ω_k^t for client k at iteration t is given by:
    
    ω_k^t   = (∑_j∈𝒢_k^tω_j^t/∑_j∈𝒢_k^t𝐦_j^t)⊙𝐦_k^t = (∑_j∈𝒢_k^tω_j^t/M)⊙𝐦_k^t

    where 𝒢_k^t is neighborhood of client k with size |𝒢_k^t| = M; all local models are sparse, i.e., ω_j^t = ω_j^t⊙𝐦_j^t. 




   Assume 𝒦 = {1, 2, …, K} clients,
   
   then, exactly m neighbors in 𝒩_k^t have reuse index less than k follows a hypergeometric distribution with 
    ℙ(m, k) = ℙ(|𝒩_(a)k| = m) = k-1mK - kM - m/K - 1M,
  
    where m<M and |𝒩_(a)k| is subset of 𝒩_k^t with index less than k.



    See Appendix <ref>

ω_k^t denotes the local personalized aggregated model for the k-th client at time t; The global aggregated model at time t, ω^t, is defined as the average of the local aggregated models, i.e., ω^t = 1/K∑_k=1^Kω_k^t, where K is the total number of clients. Let M represent the number of clients in the neighborhood. All models are under the setup of DA-DPFL, where (1) the models are sparse; and (2) a new scheduling strategy is adopted. Then, we obtain the following theorem.













Under Assumptions <ref> to <ref>, when T is sufficiently large and the stepsize η for SGD for training client models satisfies η≤√(1/12μ^2(M-1)(2M-1)) for M>1,

    min𝔼∇ f(ω^t)^2
       ≤2/T(η-6S_1(μ-η))( 𝔼[f(ω^0)] - minf) + S_3,

where S_1=2η^2M(M-1)( exp((3M+2)E_l/4(M^2-1)) - 1 ), S_2=1/2M-1σ^2_l + 3(σ^2_g+2σ^2_p)
, and S_3=2/η-6S_1(μ-η)·[ (μ-η) S_1S_2 +3μ^2η^3(3M+2)E_l/2(M+1)M(σ_l^2+σ_g^2)]. 
f(ω^0) represents initial global model loss, minf is minimum of loss, M is neighborhood size.



See Appendix <ref>


Theorem <ref> reveals that with sufficiently large T, the error due to initial model loss and bounded variance for gradients become negligible. Specifically, if one can choose η=𝒪(1/μ√(T)), the convergence boundary will be dominated by the rate of 𝒪(1/√(T)+σ^2_l+σ^2_g+σ^2_p/√(T)+σ^2_l+σ^2_g/T).



Theorem <ref> is consistent with two key empirical observations: (i) The number of communication rounds required to attain a specified error level ε is lower compared to the DisPFL model. Note: This efficiency gain is attributed to the term S_1>( e^E_l/(2M-2) - 1 ), i.e., no scheduling involved, which emerges from our scheduling strategy. The division of the left-hand side (first and third item) of the inequality by S_1 results in a reduced error boundary. (ii) Changed ratio is 3M+2/2M+2. When M=2, the ratio  simplifies to 4/3. As M increases, this ratio approaches 3/2. This indicates that while increasing M enhances the error-bound reduction, the improvement rate diminishes, suggesting a limit to the benefits offered DA-DPFL scheduling.





§ EXPERIMENTS



 §.§ Experimental Setup





  §.§.§ Datasets & Models
 Our experiments were conducted on three widely-used datasets: HAM10000 <cit.>, CIFAR10, and CIFAR100 <cit.>. We employed two distinct partition methods, Pathological and Dirichlet, to generate non-i.i.d. scenarios paralleling the approach in <cit.>. We use Dir for Dirichlet and Pat for Pathological in the following notations. The Dir. partition constructs non-i.i.d. data using a Dir(α) distribution, with α = 0.3 for CIFAR10 and CIFAR100, and α = 0.5 for HAM10000. For Pat. partitioning, several classes n_cls are assigned per client: 2 for CIFAR10 and HAM10000, and 10 for CIFAR100.
To validate the versatility of our pruning methods across various model architectures, we selected AlexNet <cit.> for HAM10000, ResNet18 <cit.> for CIFAR10, and VGG11 <cit.> for CIFAR100, ensuring a comprehensive evaluation across diverse model structures.



  §.§.§ Baselines
 We compare the proposed methods with baselines including CFL: FedAvg<cit.>, Ditto<cit.> and FedDST <cit.>, and DFL: GossipFL<cit.>, DFedAvgM<cit.>, DisPFL<cit.>, BEER<cit.> and DFedSAM<cit.>. 



  §.§.§ System Configuration
 We consider a network of K=100 clients and select M=N=10 clients (neighbors) per communication round. CFL focuses on the communication between central server and selected clients. DFL mirrors this communication allocating identical bandwidth to each of the busiest clients. This ensures that 10 clients are active per round matching server's connection load. 
All the baseline results are average values for three random seeds of best test model performance. In contrast to CFL, all DFL baselines except DFedSAM are configured with half the communication cost. Our method, FedDST, and DisPFL implement sparse model training for efficiency, which all start with initial sparsity s_k^0=0.5 with k∈ [K] for all clients. To ensure a balanced and fair comparison, all DFL benchmarks incorporate personalization by monitoring model performance following local training under randomly time-varying connection in <cit.>.



  §.§.§ Hyperparameters
 To ensure a fair comparison, we align our experimental hyperparameters with the setups described in <cit.> and <cit.>.  Unless otherwise specified, we fix the number of local epochs at 5 for all approaches and employ a Stochastic Gradient Descent (SGD) optimizer with a weight decay set to 5 × 10^-4. The learning rate is initialized at 0.1, undergoing an exponential decay with a factor of 0.998 after each global communication round. The batch size is consistently set to 128 across all experiments. The global communication rounds are conducted 500 times for the CIFAR10 and CIFAR100 datasets, and 300 times for the HAM10000 dataset. We let δ_v=0.5,b=0,c=1.3, {p,q,γ,η_c}={0.5,1,0.9,1} as suggested by <cit.>, and  δ_pr∈{0.01, 0.02,0.03} for all experiments. In the CFL baseline implementation, the local training for Ditto is bifurcated into two distinct phases: a global model training phase spanning 3 epochs and a personalized model training phase consisting of 2 epochs. Additionally, the update mask reconfiguration interval in FedDST is determined through a grid search within the set [1, 5, 10, 20]. In our DFL setup, when algorithms incorporate compression techniques, we manage to reduce half of the busiest communication load. In contrast, GossipFL utilizes a Random Match approach, which entails randomly clustering clients into specific groups. For the optimization algorithm, Momentum SGD is adopted in DFedAvgM and DFedSAM, with a momentum factor β = 0.9. Additionally, a ρ value for DFedSAM is decided by grid search from [0.01, 0.02, 0.05, 0.1, 0.2, 0.5], following the work for SAM optimizer.

















  §.§.§ Cost Simulation


For cost analysis, we utilized an NVIDIA 4090 GPU with 80 TFLOPS and 450 W TDP as a standard to assess clients' computational power and energy consumption. The architecture anticipates 1 Gbps bandwidth, with client network cards utilizing 1 W, cited from <cit.>. We derived C_time from Table <ref> and converted C_energy and C_time to monetary units using (1-θ)$/s and θ$/J, illustrated in Fig. <ref>. To address the gap between theoretical and actual GPU execution times, we performed real-world algorithm executions on the GPU. These revealed a fivefold increase over theoretical times, leading to a correction factor of 5 for computation time, calculated as T_comp = 5 ×D_FLOP/V_FLOPS, and energy, C_comp = T_comp× P_comp. Similarly, in estimating the communication time T_comm, we apply the formula T_comm = D_comm/B, where D_comm denotes the data volume to be transferred and B signifies the system's overall bandwidth. Accordingly, the communication energy cost C_comm is determined by C_comm = T_comm× P_comm, with P_comm indicating the transmission power of the wireless network card.



 §.§ Performance Analysis




  §.§.§ Test Accuracy Evaluation
 DA-DPFL outshines all baselines in top-1 accuracy across five out of six scenarios, maintaining robustness under extreme non-iid conditions (n_cls=2) (Fig. <ref>, Table <ref>). It exceeds the next best DFL baselines (DisPFL and GossipFL) by 2-3%, with a minor shortfall in HAM10000 (n_cls=2) by 0.5% against DFedAvgM. DA-DPFL consistently surpasses DisPFL in sparse model training and generalization, while maintaining efficient convergence. Conversely, CFL lags in convergence due to its limited client participation per round. Momentum-based methods like DFedAvgM show accelerated initial learning, while BEER, with gradient tracking, exhibits rapid convergence but does not necessarily reduce generalization error. DA-DPFL demonstrates a balanced trade-off between convergence rate and generalization performance, outperforming other baselines achieving target accuracy with reduced costs. 










  §.§.§ Efficiency
 We evaluate the efficiency of our algorithm by analyzing two key metrics: the Floating Point Operations (FLOP) required for inference, and communication overhead incurred during convergence rounds. To ensure a fair comparison, we employ the initialization protocol from DisPFL, thereby standardizing the initial communication costs and FLOP values in the initial pruning phase of training. 
Notably, the pruning stages integral to DA-DPFL lead to a significant reduction in these costs. This is evidenced by the final sparsity levels achieved: (0.61, 0.56) for HAM10000, (0.65, 0.73) for CIFAR10, and (0.70, 0.73) for CIFAR100 under Dir. and Pat. partitioning, respectively. These results are obtained within the constrained communication rounds. A critical observation is that both the busiest communication costs and training FLOPs for our approach are lower compared to the most efficient DFL baseline, DisPFL. These comparative insights are further elaborated in Table <ref>, with bold values underscoring the efficiency of DA-DPFL.
To quantify the impact of a potential delay in DA-DPFL, we adopt metrics to calculate the total cost C_total defined in <cit.> and  <cit.> as:

C_total = (1-θ)C_time + θ C_energy,

where θ∈ [0,1] is set to 0 for extreme time-sensitive applications and to 1 for extreme energy-sensitive tasks. This metric allows for a unified representation of time and energy costs in monetary units (USD $). 

To provide a realistic and practical insight into how the introduction of DA-DPFL would affect the total cost needed for the whole process of FL, we chose to combine the communication and the computation cost (FLOP) in the form of energy expenditure, i.e.,

C_energy = C_comm + C_comp,

where C_comm and C_comp is communication and computational cost, respectively. 
Figures <ref> and <ref> show the cost-effectiveness of DA-DPFL compared to other DFL baselines. Initially, when θ→ 0 
, DA-DPFL incurs a higher time cost. However, as θ increases beyond 0.2, DA-DPFL demonstrates remarkable advantages over the other DFL algorithms (represented by solid lines), with its lead expanding as θ further increases. Due to the system configuration, CFLs have significantly lower communication (1%) and computation (10%) costs compared to DFL, which (indicated by dotted lines) exhibits superior cost efficiency overall, but lower convergence speed. Overall, even when considering waiting time, DA-DPFL successfully achieves both cost and learning (convergence speed) efficiency.














































  §.§.§ Extended Topology

To demonstrate the adaptability of our DA-DPFL, we conducted further experiments utilizing both ring and fully-connected (FC) topologies. 
These experiments were carried out in comparison with the above baselines using a Dirichlet partition with α=0.3. The results, presented in Table <ref> show that DA-DPFL consistently surpasses other baselines, achieving higher performance with sparser models, within 500 communication rounds. 
DA-DPFL maintains a significant lead in performance.







 §.§ Analysis on neighborhood size M
 We train ResNet18 on CIFAR10 to examine the impacts of the hyper-parameters M. The neighborhood size parameter M markedly influences the scheduling efficiency in DA-DPFL. A higher M value accelerates the convergence of our approach, primarily by enhancing the reuse of the trained model throughout the training process, albeit at the risk of potential delay.
As illustrated in Fig.<ref> Bottom, while M=20 slightly outperforms M=10, it incurs approximately double the time delays. 



 §.§ Ablation Study



  §.§.§ Threshold δ_pr

Extending total communication rounds from 500 to 1000, we ascertain that a target sparsity of s=0.8 is attainable without compromising accuracy (DA-DPFL achieves 89% over DisPFL’s 83.27%). This finding challenges the generalization gap assumption in <cit.>, reducing the need for precise initial sparsity ratio selection in fixed sparsity pruning as DA-DPFL achieves equivalent or lower generalization error at higher sparsity levels through further pruning. Fig.<ref>(Top) shows the pruning decisions based on average detection scores across clients and their sparsity trajectories. The initial high detection score validates the substantial disparity between the random mask and the RigL algorithm-derived mask, differing from EarlyCrop’s centralized, densely initialized model approach. Post t^*, client models undergo incremental pruning in DA-DPFL, with the pruning scale diminishing due to reduced model compressibility, as evidenced by sparsity alterations at each pruning phase. To ascertain the effect of the early pruning threshold δ_pr, we conducted experiments with CIFAR10 and ResNet18. Fig.<ref> underscores pruning timing significance, indicating varying optimal thresholds for different data partitions and corresponding detection score divergences. Early pruning, though accelerating sparsity achievement, impedes critical learning phases, while excessively delayed pruning equates to post-training pruning, incurring higher costs. Consequently, our results advocate for early-stage further pruning, ideally between 30-40% of total communication rounds, aligning with a threshold range of 0.02-0.03, to balance model performance with energy efficiency.











  §.§.§ Waiting Threshold N

To ensure a fair comparison, we add N={0,2,5} with the same experiment setup as in <ref> for Dir partition.
The experimental results in Fig. <ref> demonstrate a clear trend: increasing the N consistently improves model accuracy across the CIFAR10 and CIFAR100 datasets, with CIFAR10 seeing up to a 1.87% increase and CIFAR100 a 1.41% increase in accuracy from N=0 to N=10. Interestingly, the HAM10000 dataset shows no  N=5 achieves the best performance, suggesting task-specific characteristics influence the optimal selection of N. Even the model performance for N=0 cases are higher than DisPFL, which illustrates the effectiveness of our further pruning strategy. Furthermore, it is possible to obtain redundancy in reusing models, especially when M is large. By selecting N, one can trade off between waiting and model performance. 







 §.§ Parallelism and Delay

We conducted 10,000 iterations to estimate the average impact on 
parallelism and latency attributed to waiting times. Here, we define parallelism as the proportion of clients that commence training concurrently. The result is depicted in Figures 
Figure <ref> illustrates a decline in parallelism as the number of clients in the neighborhood M increases (having K=100 clients). 
Figure <ref> shows delay against M. The black line, representing N=M, delineates the outcome of awaiting the most delayed clients, i.e., without any control. It is evidenced to scale almost linearly with the neighborhood size M. 
Moreover, in Figure <ref>, one can observe the efficacy of the constraint N ≤ M in mitigating delays while increasing M. 
The mean maximum waiting time is indicative of the multiplier effect on the time required for each communication round relative to traditional decentralized FL. The lines corresponding to N ∈{1,2,5,10,20} corroborate that the waiting period can be effectively regulated by N. 
In cases where M=N=100, DA-DPFL transits to sequential learning, while with M=100 and N=2, DA-DPFL sustains a comparatively high degree of parallelism with opportunities for model reuse. 
With N=0, DA-DPFL reduces to DisPFL with our pruning strategy.




























§ CONCLUSIONS

DA-DPFL is a fair learning scheduling framework that cost-effectively deals with data heterogeneity. 
DA-DPFL conserves computational & communication resources and accelerates the learning process by introducing a novel sparsity-driven pruning technique. 

We provide a theoretical analysis on DA-DPFL's convergence. Comprehensive experiments and comparisons with DFL and CFL baselines in PFL context showcase learning efficiency, enhanced model accuracy, and energy efficiency, which confirms the effectiveness of DA-DPFL in practical applications.
DA-DPFL sets the stage for future plans in adaptive algorithms handling time-series and graph data across diverse topologies expanding our models applicability to real-world scenarios.





§ ADDITIONAL ALGORITHMS



 §.§ SAP (PQI) Algorithm

In our approach, we adopt the SAP algorithm, as shown in Algorithm <ref>, to assess the compressibility of neural networks, characterized by four distinct features. Firstly, the initial model employed in our study is inherently sparse. Secondly, we implement PQI pruning as a further pruning technique within a Federated Learning (FL) framework, based on other fixed pruning methodologies. Thirdly, our method incorporates a meticulously designed pruning strategy that ensures proper pruning frequency and specifically avoids further pruning during the critical learning period. Lastly, unlike conventional practices, we integrate the SAP algorithm during the training phase, as opposed to applying it post-training.





 §.§ RigL Algorithm


We follow the RigL algorithm to generate the new mask each communication round, which is shown in Algorithm <ref>.



























































































§ CONVERGENCE ANALYSIS

In a time-varying connected topology, both 𝒢_k^t and 𝒩_k^t are randomly generated. We consider 𝒩_k^t=𝒢_k^t in theoretical analysis since our scheduling policy is regarded as one type of client selection policy.



 §.§ Client Selection Analysis


Given a system with K clients with indices sorted from 1 to K, and considering a particular client with index k then: 
(1) there are K-1 potential clients to select from; (2) among these K-1  clients, k-1 clients have an index less than k; (3) we wish to select M total clients in each sample as client's k neighbors. Hence, |𝒩_(a)k| is a hypergeometric random variable and the probability ℙ(m, k) = ℙ(|𝒩_(a)k| = m) that exactly m of the selected clients have an index less than k is

    ℙ(m, k) = k-1mK - kM - m/K-1M,

where ∑_0≤ m ≤min_(M,k-1)ℙ(m,k)=1, which essentially follows from Vandermonde's identity.


















































































 §.§ Auxiliary Lemmas and Proofs

DA-DPFL's local update follows:

    ω_k,τ+1^t = ω_k,τ^t - η𝐠_k,τ^t⊙𝐦_k^t,

where 𝐠_k,τ^t=∇ F_k(ω_k,τ^t). This implies that

    η∑_τ=0^E_l-1𝐠_k,τ^t⊙𝐦_k^t = (ω_k,0^t-ω_k,E_l^t)⊙𝐦_k^t.

Note that ω_k^t+1=ω^t_k,E_l and ω_k^t=ω_k,0^t. Considering traditional aggregation, like in FedAvg, without scheduling first, we then have Lemma <ref>.


     Under Assumptions <ref> to <ref>, for some M>1 and η such that η^2≤1/12Mμ^2(M-1)(2M-1),

    1/K∑_k=1^K𝔼ω_k^t+1 - ω_k^t^2≤( e^E_l/2M-2 - 1 ) (2M-2) 
         ×( 2M/2M-1η^2σ^2_l + 6Mη^2(σ^2_g+σ^2_p) . 
         . + 6Mη^2∑_k=1^K𝔼∇ f(ω_k^t)^2/K).


 

 Because the mask 𝐦_k^t is consistent during training, we omit the expression with the corresponding model for brevity.   
 We firstly consider the traditional weighted average aggregation where












    𝔼ω_k,τ+1^t - ω_k^t^2 
    = 𝔼ω̃_k,τ^t - ω_k^t 
    -η( g_k,τ^t⊙𝐦_k^t
          - ∇ f_k(ω̃_k,τ^t)+ ∇ f_k(ω̃_k,τ^t) - ∇ f(ω̃_k^t) 
    + ∇ f(ω̃_k^t) 
          - ∇ f_k(ω̃_k^t)+ ∇ f_k(ω̃_k^t)) ^2.


Write a:=𝔼ω̃_k,τ^t - η(g̃_k,τ^t⊙𝐦_k^t - ∇ f_k(ω̃_k,τ^t))- ω_k^t^2 and b= η^2𝔼∇ f_k(ω̃_k,τ^t) - ∇ f(ω̃_k^t)+ ∇ f(ω̃_k^t)- ∇ f_k(ω̃_k^t)+ ∇ f_k(ω̃_k^t) ^2, using the Cauchy’s inequality with a elastic variable 2M=2M>1, we have 

    𝔼ω_k^t+1 - ω_k^t^2≤ (1+1/2M-1)a+2Mb.

Then,  by Assumptions <ref> to <ref> and the triangle inequality, 

    a   ≤𝔼ω̃_k,τ^t-ω_k^t^2+η^2𝔼g̃_k,τ^t⊙𝐦_k^t - ∇ f_k(ω̃_k,τ^t)^2
       = 𝔼ω̃_k,τ^t-ω_k^t^2 + η^2σ^2_l,

and 

    b    ≤ 3η^2[𝔼∇ f_k(ω̃_k,τ^t) - ∇ f_k(ω̃_k^t)^2
          +𝔼∇ f(ω̃_k^t)^2 + 𝔼∇ f_k(ω̃_k^t) - ∇ f(ω̃_k^t)^2] 
       ≤ 3η^2[𝔼∇ f_k(ω̃_k,τ^t) - ∇ f_k(ω̃_k^t)^2
          +𝔼∇ f(ω̃_k^t)^2 + 𝔼∇ f_k(ω̃_k^t) - ∇ f(ω̃^t)^2
          +𝔼∇ f(ω̃_k^t) - ∇ f(ω̃^t)^2] 
       ≤ 3η^2[μ^2𝔼ω̃_k,τ^t-ω_k^t^2 + 𝔼∇ f(ω̃_k^t)^2
          +(σ^2_g+σ^2_p)].


Substitute Eq.(<ref>) & (<ref>) into Eq. (<ref>) with some η such that η^2≤1/12Mμ^2(M-1)(2M-1), we have

    𝔼ω_k,τ+1^t - ω_k^t^2≤ (1+1/2M-1 + 6Mη^2μ^2)𝔼ω̃_k,τ^t - ω_k^t^2
          + (1+1/2M-1)η^2σ^2_l + 6Mη^2(σ^2_g+σ^2_p+𝔼∇ f(ω̃_k^t)^2) 
       ≤ (1+1/2M-2)𝔼ω̃_k,τ^t - ω_k^t^2
          + (1+1/2M-1)η^2σ^2_l + 6Mη^2(σ^2_g+σ^2_p+𝔼∇ f(ω̃_k^t)^2)



Let A = 1 + 1/2(M-1), B = (1+1/2M-1)η^2σ^2_l + 6Mη^2(σ^2_g+σ^2_p), and C = 6Mη^2𝔼∇ f(ω̃_k^t)^2, then the recursive inequality Eq.(<ref>) becomes

    𝔼ω_k,τ+1^t - ω_k^t^2   ≤ A𝔼ω̃_k,τ^t - ω_k^t^2 + B + C.




When τ = 0, the initial condition is 𝔼ω̃_k,0^t - ω_k^t^2 = 0. For τ = 1 to E_l, we apply the inequality Eq.(<ref>) E_l times, summing up the constants multiplied by their respective powers of A gives

    𝔼ω_k,E_l^t - ω_k^t^2   ≤ A^E_l𝔼ω̃_k,0^t - ω_k^t^2 + B∑_j=0^E_l-1 A^j 
       + C∑_j=0^E_l-1 A^j.


The sums of the series can be simplified by the sum of a geometric series as follows

    ∑_j=0^E_l-1 A^j = 1 - A^E_l/1 - A.


Hence the inequality can be further simplified as 

    𝔼ω_k,E_l^t - ω_k^t^2   ≤ 0 + (B+C)A^E_l-1/A-1.

When M>1, A = 1 + 1/2M-2 < e^1/2M-2 hence A^E_l<e^E_l/2M-2, which gives the final bound for 𝔼ω_k^t+1 - ω_k^t^2 as in Eq.(<ref>). 


Consider the proposed scheduling strategy. Let ω_k^t(†) denote the local personalized aggregated model for the k-th client at time t. The global aggregated model at time t, ω^t(†), is defined as the average of the local models, i.e., ω^t(†) = 1/K∑_k=1^Kω_k^t(†), where K is the total number of clients. Let M represent the number of clients in the neighborhood. With the support of Lemma 1 in <cit.>, the expected value of the global model at time t+1, denoted as 𝔼(ω^t+1(†)), is given by


    𝔼(ω^t+1(†)) = 𝔼(ω^t(†)) - η𝔼( ∑_k=1^K∑_τ=0^E_l^*-1𝐠_τ,k(ω^t(†)) )/K,

where E_l^* = 3M+2/2(M+1)E_l, and E_l is the number of steps of local updates. Here, 𝐠_τ,k represents the gradient computation for the k-th client at local update step τ. 



Now we consider the effect of DA-DPFL's scheduling. Rewrite the mask element aggregation with the sequential appointment as 

    ω_k^t(†)   = ( ∑_j∈𝒩_(a)k^tω_j^t+∑_j∈𝒩_(b)k^tω_j^t+ω_k^t/∑_j∈𝒩_(a)k^t𝐦_j^t+∑_j∈𝒩_(b)k^t𝐦_j^t+𝐦_k^t)⊙𝐦_k^t
       = ( ∑_j∈𝒩_(a)k^tω_j^t+∑_j∈𝒩_(b)k+^tω_j^t/M+1)⊙𝐦_k^t,

where 𝒩_(b)k^t:=𝒩_k^t∖𝒩_(a)k^t, 𝒩_(b)k+^t𝒩_(b)k^t∪{k}, and 
the last equation holds under Assumption <ref>.

Similar to Eq.(<ref>), we omit 𝐦_k^t for convenience on notations since the mask is consistent during local training. Then for the j-th client at time t, the local personalized aggregated model is

    ω_j^t(†) = 
    ω_j^t-η∑_τ=0^E_l-1𝐠_j,τ^t⊙𝐦_j^t,    if  j ∈𝒩_(a)k^t;
    ω_j^t,    otherwise.

 When j ∈𝒩_(a)k^t, one can see that ω_j^t(†) is equivalent to ω_j^t+1, reflecting the scenario where, within a single communication round, all participating clients perform an equal number of local training iterations, analogous to traditional FL. The superscript (†) is introduced for an explicit differentiation, signifying that although the local gradients 𝐠_j,τ^t are computed under varying aggregation models, they are distinct from those in a synchronous FL framework.
Denoted by I_{j ∈𝒩^t_(a)k} an indicator function for the event that the j-th client is selected in the delayed neighborhoods of client k. 

































Using the results of Proposition <ref>, it can be shown that

    𝔼 ( ∑_j∈𝒩_(a)k^tω_j^t+1 )
           = 𝔼 ( 𝔼 ( ∑_j∈𝒩_(a)k^tω_j^t+1 | |𝒩^t_(a)k| ) )
       = 𝔼 ( 𝔼 ( ∑_j∈𝒩_k^tω_j^t+1 I_{j ∈𝒩^t_(a)k} | |𝒩^t_(a)k| ) )
       = 𝔼 ( 𝔼 ( ∑_j∈𝒩_k^tω_j^t+1 I_{j ∈𝒩^t_(a)k | |𝒩^t_(a)k|}  ) )
       = 𝔼 (   ∑_j∈𝒩_k^tω_j^t+1𝔼  (I_{j ∈𝒩^t_(a)k | |𝒩^t_(a)k|}  ) )
       = 𝔼 (   ∑_j∈𝒩_k^tω_j^t+1ℙ  (j ∈𝒩^t_(a)k | |𝒩^t_(a)k|  ) )
       = 𝔼 (   ∑_j∈𝒩_k^tω_j^t+1|𝒩^t_(a)k|/M  )
       = 𝔼 ( |𝒩^t_(a)k|  )  𝔼 (∑_j∈𝒩_k^tω_j^t+1)/M
       = (k-1)M/K-1𝔼 (ω^t+1),

where |𝒩^t_(a)k| follows hypergeometric distribution. Similarly,

    𝔼 ( ∑_j∈𝒩_(b)k+^tω_j^t )
           = 𝔼 ( 𝔼 ( ∑_j∈𝒩_(b)k+^tω_j^t | |𝒩^t_(b)k+| ) )
       = 𝔼 ( 𝔼 ( ∑_j∈𝒩_k+^tω_j^t I_{j ∈𝒩^t_(b)k+} | |𝒩^t_(b)k+| ) )
       = 𝔼 ( 𝔼 ( ∑_j∈𝒩_k+^tω_j^t I_{j ∈𝒩^t_(b)k+ | |𝒩^t_(b)k+|}  ) )
       = 𝔼 (   ∑_j∈𝒩_k+^tω_j^t𝔼  (I_{j ∈𝒩^t_(b)k+ | |𝒩^t_(b)k+|}  ) )
       = 𝔼 (   ∑_j∈𝒩_k+^tω_j^tℙ  (j ∈𝒩^t_(b)k+ | |𝒩^t_(b)k+|  ) )
       = 𝔼 (   ∑_j∈𝒩_k+^tω_j^t|𝒩^t_(b)k+|-1/M  )
       = 𝔼 ( (|𝒩^t_(b)k+|-1)  )  𝔼 (∑_j∈𝒩_k+^tω_j^t)/M
       = (K-k)(M+1)/(K-1)𝔼 (ω^t) .

Therefore, 𝔼(ω_k^t(†)) can be written as 


    [(k-1)M/(K-1)(M+1)𝔼(ω^t+1)   +  (K-k)/(K-1)𝔼(ω^t) ] ⊙𝐦_k^t
       = 𝔼(ω^t) ⊙𝐦_k^t  - [(k-1)M/(K-1)(M+1)× . 
         𝔼(η∑_j∈𝒩_k+^t∑_τ=0^E_l-1g_j,τ^t/M+1)] ⊙𝐦_k^t,



where one can verify that when k=1, 𝔼 ( ω_k^t(†) ) reduces to 𝔼 ( ω_k^t ). 
Recall that ω^t(†)=1/K∑_k=1^Kω_k^t(†), then

    𝔼(ω^t(†)) 
        = 1/K∑_k=1^K(𝔼(ω^t
          -(k-1)M/(K-1)(M+1)η∑_j∈𝒩_k+^t∑_τ=0^E_l-1g_j,τ^t(ω^t)) ⊙𝐦_k^t) 
       = 1/K∑_k=1^K(𝔼(ω^t)  -(k-1)M/(K-1)(M+1)η𝔼(g_k^t)⊙𝐦_k^t) 
       = 𝔼(ω^t) -1/K∑_k=1^K((k-1)M/(K-1)(M+1)η𝔼(g_k^t))⊙𝐦_k^t,



where g_k^t=∑_j∈𝒩_k+^t∑_τ=0^E_l-1g_j,τ^t/M+1 and the last equality holds according to the definition of ω^t. g_j,τ^t(ω) means the gradient at local epoch τ=0 is with respect to ω. 













 
Let g^t(†)=1/K∑_k=1^K[(k-1)M/(K-1)(M+1)g_k^t⊙𝐦_k^t], then
 
    𝔼(ω^t(†))    = 𝔼(ω^t)-η𝔼(g^t(†)).

 
 
 To find the boundary for the difference between the global model at time t and t+1 and according to Assumption <ref>, we have 

    𝔼[f(ω^t+1(†))] -𝔼[f(ω^t(†))] 
       ≤𝔼[<f(∇ω^t(†)), ω^t+1(†)-ω^t(†)>] 
          +μ/2ω^t+1(†)-ω^t(†)^2.


 
 



Lemma 1 in <cit.> ensures that ∀ k ∈| K |, 𝔼(∑_k=1^K∑_τ=0^E_l-1𝐠_τ,k(ω^t(†)) /K)=𝔼[𝐠_k^t] since 𝒩_k^t is selected randomly.
According to the definition and Eq. (<ref>),

    𝔼(ω^t+1(†)) 
           = 𝔼(ω^t+1) - η𝔼(g^t+1(†)) 
       = 𝔼(ω^t(†)) - η𝔼( ∑_k=1^K∑_τ=0^E_l-1𝐠_τ,k(ω^t(†)) )/K
          -η𝔼(g^t+1(†)) 
       = 𝔼(ω^t(†)) - η𝔼( ∑_k=1^K∑_τ=0^E_l^*-1𝐠_τ,k(ω^t(†)) )/K,


where E_l^*=E_l+M/2(M+1)E_l.
Actually, here the starting weights of g^t+1(†) is with respect to 𝔼 (ω^t+1)= 𝔼(ω^t(†)) -η∑_k=1^K𝔼∑_τ=0^E_l-1(𝐠_τ,k(ω^t(†)) )/K. One can think of just continuing M/2(M+1) more steps of local training, where 1/K∑_k=1^K[(k-1)M/(K-1)(M+1)]=M/2(M+1). E_l^* might not be an integer, we just use this to conclude the effect of sequential aligning for convergence analysis.





















Now, the target is to prove the boundary of 𝔼<f(∇ω^t(†)),ω^t+1(†)-ω^t(†)> and μ/2ω^t+1(†)-ω^t(†)^2.

     Under Assumptions <ref> to <ref> and Lemma <ref>, suppose ω^t+1(†) and ω^t(†) are global model learned by the proposed strategy, for some M>1 with η≤√(1/12Mμ^2(M-1)(2M-1)), 𝔼 [μ/2ω^t+1(†)-ω^t(†)^2] is upper bounded by







    𝔼 [μ/2ω^t+1(†)-ω^t(†)^2]
            ≤μ S_1( S_2+ 3𝔼∇ f(ω^t(†)^2),

where S_1=2η^2M(M-1)( exp((3M+2)E_l/4(M^2-1)) - 1 ) and S_2=1/2M-1σ^2_l + 3(σ^2_g+2σ^2_p).



Lemma <ref> states the boundary for the local updates. Eq. (<ref>) and Lemma <ref> states that the scheduling increases the local epochs E_l to E_l^* with the expectation for the (aggregated) global model. Hence,

    𝔼    [ω^t+1(†)-ω^t(†)^2] 
       =𝔼 [1/K∑_k=1^Kω_k^t+1(†) - 1/K∑_k=1^Kω_k^t(†)^2]
       ≤𝔼 [1/K∑_k=1^Kω_k^t+1(†) - ω_k^t(†)^2].

The last inequality holds since Jensen's Inequality where the defined function ϕ(.)=.^2 is convex.
Therefore, substituting the results of Lemma <ref> and changing E_l by E_l^*+1, we have a boundary with ∑_k=1^K𝔼∇ f(ω̃_k^t(†))^2/K. With the triangle inequality again and Assumption <ref>, 

    ∑_k=1^K𝔼∇ f(ω̃_k^t(†))^2/K
       =
        ∑_k=1^K𝔼∇ f(ω̃_k^t(†))-∇ f(ω^t(†))+∇ f(ω^t(†))^2/K
       ≤∑_k=1^K𝔼∇ f(ω̃_k^t(†))-∇ f(ω^t(†))^2+∇ f(ω^t(†))^2/K
       ≤𝔼∇ f(ω^t(†)^2+σ_p^2,

which finishes the proof.





Under Assumptions <ref> to <ref> and Lemma <ref>,
𝔼[<∇ f(ω^t(†)),ω^t+1(†)-ω^t(†)>] is upper bounded by

    -η/2∇ f(ω^t(†))^2-η/2𝔼𝐠̂^t(†)^2+3μ^2η^3E_l^*/M(σ_l^2+σ_g^2)

where E_l^*=3M+2/2(M+1)E_l





        According to Eq. (<ref>) and let 𝐠̂^t(†)= ∑_k=1^K∑_τ=0^E_l^*𝐠_τ,k(ω^t(†))/K,







𝔼[<∇ f(ω^t(†)),ω^t+1(†)-ω^t(†)>] 
    
= -η𝔼[<∇ f(ω^t(†)), 𝔼(𝐠̂^t(†))>].
Let's prove the boundary for -𝔼[<∇ f(ω^t(†)), 𝔼(𝐠̂^t(†))>].







    -𝔼[<∇ f(ω^t(†)), 𝔼(𝐠̂^t(†))>](a)= -1/2∇ f(ω^t(†))^2
         -1/2𝔼𝐠̂^t(†)^2 +1/2∇ f(ω^t(†))-𝔼[𝐠̂^t(†)]^2


, where (a) is due to <𝐚,𝐛>=𝐚^2+𝐛^2-(𝐚-𝐛)^2/2. Then only the third term in the right-hand-side is left, since the boundary for the first and second term can be found by Lemma <ref>. Based on Assumption <ref> and denote t_c as the start of the communication round of t, i.e before training,

    1/2∇ f(ω^t(†))-𝔼[𝐠̂^t(†)]^2≤μ^2/2K∑_k=1^K𝔼ω^t(†)-ω^t(†)_k^2
       = μ^2/2∑_k=1^K𝔼[1/Kω^t_c(†)- 1/K∑_j=1^K𝔼_𝒫_t,j[η/M∑_j∈𝒫_t,j∑_τ=t_c^t_c+E_l^*g_τ,j^t_c(†)]  
           -ω^t_c(†) + 𝔼_𝒫_t,k[η/M∑_k∈𝒫_t,k∑_τ=t_c^t_c+E_l^*g_τ,k^t_c(†)]^2] 
       = μ^2η^2/2∑_k=1^K𝔼[1/K𝔼_𝒫_t,k[1/M∑_k∈𝒫_t,k∑_τ=t_c^t_c+E_l^*g_τ,k^t_c(†)]  
           -1/K∑_j=1^K𝔼_𝒫_t,j[1/M∑_j∈𝒫_t,j∑_τ=t_c^t_c+E_l^*g_τ,j^t_c(†)]^2] 
       =μ^2η^2/2∑_k=1^K𝔼[1/K𝔼_𝒫_t,k[1/M∑_k∈𝒫_t,k∑_τ=t_c^t_c+E_l^*(g_τ,k^t_c(†)-∇ f_k(ω^t_c(†)_k,τ))]
          -1/K∑_j=1^K𝔼_𝒫_t,j[1/M∑_j∈𝒫_t,j∑_τ=t_c^t_c+E_l^*(g_τ,j^t_c(†)-∇ f_j(ω^t_c(†)_j,τ))]
          +𝔼_𝒫_t,k[1/M∑_k∈𝒫_t,k∑_τ=t_c^t_c+E_l^*∇ f_k(ω^t_c(†)_k,τ)]
          -1/K∑_j=1^K𝔼_𝒫_t,j[1/M∑_j∈𝒫_t,j∑_τ=t_c^t_c+E_l^*∇ f_j(ω^t_c(†)_j,τ)]^2].
       (b)≤3μ^2η^2/2K∑_k=1^K[ 𝔼_𝒫_t,j1/M∑_k∈𝒫_t,k∑_τ=t_c^t_c+E_l^* (g_τ,k^t_c(†)
             - ∇ f_k(ω^t_c(†)_k,τ) ) ^2
          + 1/K∑_j=1^K𝔼_𝒫_t,j[1/M∑_j∈𝒫_t,j∑_τ=t_c^t_c+E_l^*∇ f_j(ω^t_c(†)_j,τ)^2] 
          +.𝔼_𝒫_t,k[1/M∑_k∈𝒫_t,k∑_τ=t_c^t_c+E_l^*∇ f_k(ω^t_c(†)_k,τ)] 
            -1/K∑_j=1^K𝔼_𝒫_t,j[1/M∑_j∈𝒫_t,j∑_τ=t_c^t_c+E_l^*∇ f_j(ω^t_c(†)_j,τ)]^2] ]
       (c)≤3μ^2η^2/2K[E_l^*/Mσ_l^2+E_l^*Kσ^2_l/KM+E_l^*/Mσ_g^2+E_l^*Kσ^2_g/KM]
        =  3μ^2η^2E_l^*/M(σ_l^2+σ_g^2)

In the above formulation, the variable j serves to distinguish from k, ensuring clarity in the representation of individual client contributions. Here, 𝒫_t,k denotes the selection probability of client k at time t. The inequality marked as (b) derives from the application of the Cauchy-Schwarz inequality, exemplified by the relation a+b+c^2≤ 3(a^2+b^2+c^2). The step labeled as (c) leverages a similar analytical technique, focusing on the aggregation of global gradients, thereby facilitating the derivation of σ^2_g, which is in conjunction with Assumption <ref>.
Substitute the results from Lemma <ref> to Eq.(<ref>) with multiplying η to conclude the proof for Lemma <ref>.






 

 













 §.§ Proof for Theorem 1

Combining the bounds from Lemma <ref> and Lemma <ref>, we have:

    𝔼[f(ω^t+1(†))] -𝔼[f(ω^t(†))] ≤
         𝔼[μ/2ω^t+1(†)-ω^t(†)^2] 
       + 𝔼[⟨∇ f(ω^t(†)), ω^t+1(†)-ω^t(†)⟩] 
       = -η/2∇ f(ω^t(†))^2+μ-η/2𝔼𝐠̂^t(†)^2+3μ^2η^3E_l^*/M(σ_l^2+σ_g^2)
       ≤6S_1(μ-η)-η/2∇ f(ω^t(†))^2+(μ-η) S_1S_2 + 
         3μ^2η^3(3M+2/2(M+1)E_l-1)/M(σ_l^2+σ_g^2).


It is the fact that min∇ f(ω^t(†)^2≤∑_t=0^T-1∇ f(ω^t(†)^2/T. Summing up Eq. (<ref>) from t=0 to a large t=T concludes the proof. In detail, Given the inequality for each iteration t:

    𝔼[f(ω^t+1(†))] - 𝔼[f(ω^t(†))] ≤6S_1(μ-η)-η/2∇ f(ω^t(†))^2
       + (μ-η) S_1S_2 + 3μ^2η^3(3M+2/2(M+1)E_l-1)/M(σ_l^2+σ_g^2).


Summing this inequality from t=0 to t=T-1 yields:

    𝔼[f(ω^T(†))] - 𝔼[f(ω^0(†))] 
       ≤∑_t=0^T-1( 6S_1(μ-η)-η/2∇ f(ω^t(†))^2) + T ·[ (μ-η) S_1S_2. 
         . + 3μ^2η^3(3M+2/2(M+1)E_l-1)/M(σ_l^2+σ_g^2) ].


To isolate the cumulative gradient norm terms across T iterations, we divide the inequality by the coefficient of the gradient norm term:

    ∑_t=0^T-1∇ f(   ω^t(†))^2
       ≤2/η-6S_1(μ-η)( 𝔼[f(ω^0(†))] - 𝔼[f(ω^T(†))] ) 
          + S_3T



, where 
S_3=2/η-6S_1(μ-η)·[ (μ-η) S_1S_2 + 3μ^2η^3(3M+2)E_l/2(M+1)M(σ_l^2+σ_g^2) ]. When T is large, The denominator η-6S_1(μ-η) is nominated by η. Then when we choose η∝𝒪(1/√(T)μ) and as T is large enough, S_3 diminishes closely to 0.



























































































































IEEEtran









