# FedDIP: Federated Learning with Extreme
Dynamic Pruning and Incremental Regularization

Qianyu Long1, Christos Anagnostopoulos1, Shameem Puthiya Parambath1, and
Daning Bi2  1 School of Computing Science, University of Glasgow, UK
<EMAIL_ADDRESS>{christos.anagnostopoulos,
<EMAIL_ADDRESS>2 College of Finance and Statistics, Hunan
University, China
<EMAIL_ADDRESS>
###### Abstract

Federated Learning (FL) has been successfully adopted for distributed training
and inference of large-scale Deep Neural Networks (DNNs). However, DNNs are
characterized by an extremely large number of parameters, thus, yielding
significant challenges in exchanging these parameters among distributed nodes
and managing the memory. Although recent DNN compression methods (e.g.,
sparsification, pruning) tackle such challenges, they do not holistically
consider an adaptively controlled reduction of parameter exchange while
maintaining high accuracy levels. We, therefore, contribute with a novel FL
framework (coined FedDIP), which combines (i) dynamic model pruning with error
feedback to eliminate redundant information exchange, which contributes to
significant performance improvement, with (ii) incremental regularization that
can achieve extreme sparsity of models. We provide convergence analysis of
FedDIP and report on a comprehensive performance and comparative assessment
against state-of-the-art methods using benchmark data sets and DNN models. Our
results showcase that FedDIP not only controls the model sparsity but
efficiently achieves similar or better performance compared to other model
pruning methods adopting incremental regularization during distributed model
training. The code is available at : https://github.com/EricLoong/feddip.

###### Index Terms:

Federated Learning, dynamic pruning, extreme sparsification, incremental
regularization.

##  I Introduction

Federated Learning (FL) [1] is a prevalent distributed learning paradigm due
to its ability to tackle learning at scale. FL plays a significant role in
large-scale predictive analytics by enabling the decentralization of knowledge
discovery. FL contributes towards privacy preservation, which overcomes
fundamental issues of data governance and ownership [2]. Distributed training
and deploying large-scale Machine Learning (ML) models, i.e., Deep Neural
Networks (DNNs), impose significant challenges due to the huge volumes of
training data, large models, and diversity in data distributions.

Distributed computing nodes, mainly located at the network edge being as close
to data sources as possible, collaboratively engineer ML models rather than
depending on collecting all the data to a centralized location (data center or
Cloud) for training [3]. This computing paradigm coined Edge Computing, has
been successfully applied to various predictive modeling, mining, and
analytics applications, e.g., in finance [4], healthcare [5] and wireless
sensor networks [6].

DNNs are characterized by an extremely large number of parameters. For
instance, the Convolutional Neural Networks (CNN) ResNet50 [7] and VGG16 [8]
consist of 27 and 140 million parameters, respectively, while generative AI
models, like GPT-2 have more than 1.5 billion parameters [9]. Evidently, this
places a great burden on distributed computing nodes when exchanging model
parameters during training, tuning, and inference.

Model size reduction (pruning) methods, e.g., [10], [11], [12] aim to retain
the prediction accuracy while reducing the communication overhead by
decreasing the number of model parameters exchanged among nodes. However, most
pruning methods focus on the compression of model gradients. Even though they
yield high compression rates, they do not achieve significantly compact models
for exchange. But in general, methods that can produce compact models along
with significant redundancy in the number of DNN weights by sophisticatedly
pruning the weights are deemed appropriate [13]. In contrast to model gradient
compression, model weight compression significantly shrinks the model size by
setting most of the weights to zero. This is desirable for eliminating
redundancy in model exchange during distributed knowledge extraction. But
often such models result in performance degradation. Therefore, the question
we are addressing is: How to effectively introduce model pruning mechanisms in
a decentralized learning setting that is capable of achieving extremely high
compression rates while preserving optimal predictive performance? We
contribute with an efficient method based on dynamic pruning with error
feedback and incremental regularization, coined FedDIP. FedDIP’s novelty lies
in the principle of adapting dynamic pruning in a decentralized way by pushing
unimportant weights to zeros (extreme pruning) whilst maintaining high
accuracy through incremental regularization. To the best of our knowledge,
FedDIP is the first approach that combines incremental regularization and
extreme dynamic pruning in FL.

The paper is organized as follows: Section II reports on related work and our
contribution. Section III provides preliminaries in FL and model pruning
methods. Section IV elaborates on the FedDIP framework, while Section V
reports on the theoretical properties of FedDIP and convergence analysis. Our
experimental results in Section VI showcase the efficiency of FedDIP in
distributed learning. Section VII concludes the paper with future research
directions.

##  II Related Work & Contribution

###  II-A Model Gradient & Model Weight Sparsification

Expensive and redundant sharing of model weights is a significant obstacle in
distributed learning [14]. The size of the exchanged models among nodes can be
reduced by compression and sparsification. The work in [11] adopts magnitude
selection on model gradients to yield sparsification when using Stochastic
Gradient Descent (SGD). Instead of dense updates of weights, [10] proposed a
distributed SGD that keeps 1% of the gradients by comparing their magnitude
values. The method in [15] scales up SGD training of DNN via controlling the
rate of weight update per individual weight. [16] develops encoding SGD-based
vectors achieving reduced communication overhead. [17] proposed the periodic
quantized averaging SGD strategy that attains similar model predictive
performance while the size of shared model gradients is reduced $95\%$. In
[18], the authors argued that 99% of gradients are redundant and introduced a
deep gradient compression method, which achieves compression rates in the
range 270-600 with sacrificing accuracy. The gTop-k gradient sparsification
method in [19] reduces communication cost based on the Top-k method in [18].
[20] develops a method based on [21] that adaptively compresses the size of
exchanged model gradients via quantization.

In contrast to gradient sparsification, the shrinkage of the entire model size
is of paramount importance in distributed learning. It not only eliminates
communication redundancy during training but also enables less storage and
inference time, which makes FL welcome in distributed knowledge systems.
However, so far, only centralized learning adopts model compression via, e.g.,
weight pruning, quantization, low-rank factorization, transferred
convolutional filters, and knowledge distillation [22], with pruning being our
focus in this work. SNIP [23] introduces a method that prunes a DNN model once
(i.e., prior to training) based on the identification of important connections
in the model. [24] proposes a centralized two-step method that prunes each
layer of a DNN via regression-based channel selection and least squares
reconstruction. The method in [25] prunes CNNs centrally using the Alternating
Direction Method of Multipliers (ADMM). Following [25], the PruneTrain method
[26] uses structured group-LASSO regularization to accelerate CNN training in
a centralized location only. The DPF [27] method allows dynamic management of
the model sparsity with a feedback mechanism that re-activates pruned weights.

###  II-B Contribution

Most of the approaches in FL take into account only the communication overhead
and thus adopt gradient sparsification. Nonetheless, weight sparsification is
also equally important and can lead to accurate distributed sparse models.
Such sparse models are lightweight and, thus, suitable for storage, transfer,
training, and fast inference. As shown in [28], model weights and gradients
averaging policies are equivalent only when the local number of model training
epochs equals one. FedDIP tries to bridge the gap of weights average pruning
in FL by obtaining highly accurate sparse models through incremental
regularization and reducing communication during training through dynamic
pruning.

To the best of our knowledge in distributed learning, PruneFL [12] FedDST [29]
and LotteryFL [30] methods attempt model pruning. However, LotteryFL focuses
on a completely different problem from ours. LotteryFL tries to discover
sparse local sub-networks (a.k.a. Lottery Ticket Networks) of a base DNN
model. In contrast, FedDIP searches for a sparse global DNN model with mask
readjustments on a central server, as we will elaborate on later. PruneFL
starts with a pre-selected node to train a global shared mask function, while
FedDIP generates the mask function with weights following the Erdős-Renéyi-
Kernel (ERK) distribution [31], as we will discuss in the later sections.
FedDST, as proposed by Bibikar et al., initially derives a pruning mask based
on the ERK distribution. Subsequent stages involve layerwise pruning on the
global model. The method ensures efficient training through a prune-regrow
procedure, which maintains a local sparse mask, particularly under non-iid
data distributions. Our technical contributions are:

  * •

An innovative federated learning paradigm, coined FedDIP, combines extreme
sparsity-driven model pruning with incremental regularization.

  * •

FedDIP achieves negligible overhead keeping accuracy at the same or even
higher levels over extremely pruned models.

  * •

Theoretical convergence and analysis of FedDIP.

  * •

A comprehensive performance evaluation and comparative assessment of FedDIP
with benchmark i.i.d. and non-i.i.d. datasets and various DNN models. Our
experimental results reveal that FedDIP, in the context of high model
compression rates, delivers superior prediction performance compared to the
baseline methods and other approaches found in the literature, specifically,
FedAvg [1], PruneFL [12], PruneTrain [26], FedDST [29], DPF [27], and SNIP
[23].

Notations | Definition
---|---
$N,K$ |  $N$: total number of nodes, where $K<N$ nodes
| participated in each training round
$n$ indexes a node; $z$ indexes a DNN layer; $n\in[N],z\in[Z]$
$[N]$ abbreviates the integer sequence $1,2,\ldots,N$
$\mathcal{D}_{n},D_{n}$ | Dataset and its size on node $n$.
$(\mathbf{x},y)\in\mathcal{D}_{n}$ |  $\mathbf{x},y$ are features and labels in node $n$’s dataset
$f(\cdot),\nabla f(\cdot)$ | Loss function and its derivative
$\rho_{n},\eta$ | Weight percentage and learning rate
$\boldsymbol{\omega}_{G}$, $\boldsymbol{\omega}_{n}$, $\boldsymbol{\omega}_{n}^{\prime}$ | Global, local and pruned local model parameters
$T,E_{l},\tau,\ell$ | Global and local rounds, global and local epochs
$\lambda$ | Regularization hyperparameter
$\odot$ | Element-wise (Hadamard) product
$s_{0}$, $s_{t}$, $s_{p}$ | initial sparsity, sparsity at round $t$, final sparsity
Table I: Table of Notations Figure 1:  Illustration of the FedDIP framework:
(1) During the downlink phase, the pruned global model
$\mathcal{\omega}^{\prime}_{G}$ is broadcasted to participating clients.
(2) In the uplink phase, each selected client communicates its local dense
model $\mathcal{\omega}_{n}$ back to the server for aggregation.
(3) The global mask $\mathbf{m}_{G}$ is derived from the global model,
directing the sparse training (DPF) across clients.

##  III Preliminaries

###  III-A Federated Learning

For the general notations and definitions, please refer to Table I. Consider a
distributed learning system involving a set of $N$ nodes (clients)
$\mathcal{N}=\\{1,2,\ldots,N\\}$. Let $\mathcal{D}_{n}=\\{(\mathbf{x},y)\\}$
be the local dataset associated with a node $n\in\mathcal{N}$ such that
$\mathbf{x}\in\mathcal{X}\subset\mathbb{R}^{d}$,
$y\in\mathcal{Y}\subset\mathbb{R}$, and $D_{n}=|\mathcal{D}_{n}|$. In the
standard FL setting, given a subset of $K<N$ nodes
$\mathcal{N}_{c}\subset\mathcal{N}$, the local loss is given by:

$f_{n}(\boldsymbol{\omega})=\frac{1}{D_{n}}\sum_{(\mathbf{x},y)\in\mathcal{D}_{n}}\mathcal{L}(\mathcal{G}(\boldsymbol{\omega},\mathbf{x}),y)$
(1)

where $\boldsymbol{\omega}$ is the model parameter, $\mathcal{G}$ is the
discriminant function that maps the input space to output space and
$\mathcal{L}$ is a loss function that measures the quality of the prediction,
e.g., mean-squared-error, maximum likelihood, cross-entropy loss. The global
loss function for all the selected nodes $n\in\mathcal{N}_{c}$ is:

$f(\boldsymbol{\omega})=\sum_{n\in\mathcal{N}_{c}}\rho_{n}f_{n}(\boldsymbol{\omega}),\text{
where }\rho_{n}=\frac{D_{n}}{\sum_{j\in\mathcal{N}_{c}}D_{j}}.$ (2)

The model training process spans periodically over $T$ global rounds with $L$
local rounds. Let $t\in=\\{0,1,\ldots,T-1\\}$ be a discrete-time instance
during the training process. Then, $\tau=\lfloor\frac{t}{L}\rfloor L$ is the
start time of the current global epoch. At $\tau$, the nodes (clients) receive
updated aggregated weights $\bar{\boldsymbol{\omega}}^{\tau}$ from the node
responsible for aggregating the nodes’ model parameters, a.k.a. the server
node. The local training at client $n$ at local epoch $l=1,\ldots,L$ proceeds
as:

$\boldsymbol{\omega}^{(\tau+l)+1}_{n}=\boldsymbol{\omega}^{\tau+l}_{n}-\eta_{\tau+l}\nabla
f_{n}(\boldsymbol{\omega}^{\tau+l}_{n}),$ (3)

where $\eta\in(0,1)$ is the learning rate. The weight averaging policy on the
server node can be written as:

$\displaystyle\bar{\boldsymbol{\omega}}^{\tau}$ $\displaystyle=$
$\displaystyle\sum_{n\in\mathcal{N}}\rho_{n}\boldsymbol{\omega}_{n}^{\tau}.$
(4)

###  III-B Model Pruning

In centralized learning systems (e.g., in Cloud), where all data are centrally
stored and available, the model pruning [32] aims to sparsify various
connection matrices that represent the weights of the DNN models. Notably,
sparsity, hereinafter noted by $s\in[0,1]$, indicates the proportion of non-
zero weights among overall weights. A 100% sparse ($s=1$) model indicates that
all the weights are negligible (their values are close to $0$), while a 0%
sparse ($s=0$) model stands for the full model with original weight values.
Typically, the reduction of the number of nonzero weights (pruning) of a DNN
model is achieved using mask functions. A mask function $\mathbf{m}$ acts like
an indicator function that decides whether the parameter/weight at a certain
position in a layer of a DNN model is zero or not. The model pruning based on
mask functions requires a criterion to select the parameters to prune. The
most common pruning criterion considers the absolute value of the weights of
each parameter in a layer. Generally, a parameter is removed from the training
process if its absolute value of the weight is less than a predefined
threshold.

On the other hand, model pruning in FL is vital in light of reducing
communication cost in each training round. Moreover, the global number of
rounds should be reduced as this significantly contributes to the overall
communication overhead. Hence, in FL, pruning aims at extreme model
compression rates, i.e., $s\geq 0.8$ with a relatively small compromise in
prediction accuracy. It is then deemed appropriate to introduce a distributed
and adaptive pruning method with relatively high and controlled DNN model
sparsity, which reduces communication costs per round along with ensuring
convergence under high sparsity with only a marginal decrease in prediction
accuracy.

The pruning techniques are typically categorized into three: pruning before
training (e.g., SNIP [23]), pruning during training (e.g., PruneTrain [26],
FedDST [29], DPF [27] and PruneFL [12]), and pruning after training. In this
work, we concentrate on the two former techniques, which deal with efficient
model training. The pruning after training approach offers limited utility in
the context of distributed learning. The two commonly employed techniques for
pruning are: (i) Regularization-based Pruning (RP) and (ii) Importance-based
Pruning (IP) [33]. The interested reader may refer to [24, 25, 33] and the
references therein for a comprehensive survey of RP and IP techniques. RP uses
intrinsic sparsity-inducing properties of $L_{1}$ (Manhattan distance) and
$L_{2}$ (Euclidean distance) norms to limit the importance of different model
parameters. The sparsity-inducing norms constrain the weights of the
unimportant parameters to small absolute values during training. Moreover, RP
can effectively constrain the weights into a sparse model space via tuning the
regularization hyperparameter $\lambda$. Whereas in IP, parameters are pruned
purely based on predefined formulae that are defined in terms of the weights
of the parameters or the sum of the weights. IP techniques were originally
proposed in the unstructured pruning settings that can result in sparse models
not capable of speeding up the computation. Even though RP techniques are
considered superior to IP techniques, they struggle with two fundamental
challenges: (C1) The first challenge pertains to controlling the sparsity
value $s$ during pruning. For example, in PruneTrain [26], employing a pruning
threshold value of $10^{-4}$ to eliminate model parameters does not guarantee
the delivery of a sparse model. (C2) The second challenge is dynamically
tuning a regularization parameter $\lambda$. A large $\lambda$ leads to model
divergence during training, as the model may excessively lean towards penalty
patterns. By adding regularization terms in DNN training traditionally aims
for overfitting issues. However, additional regularization for prunable layers
is required for RP, which is the core difference between traditional training
and RP-based training.

##  IV The FedDIP Framework

The proposed FedDIP framework integrates extreme dynamic pruning with error
feedback and incremental regularization in distributed learning environments.
Figure 1 illustrates a schematic representation of the FedDIP, which will be
elaborated on in this section. FedDIP attempts to effectively train pruned DNN
models across collaborative clients ensuring convergence by addressing the two
challenges C1 and C2 prevalent in RP-based methods discussed in Section III-B.

The dynamic pruning method (DPF) in [27] demonstrates improved performance in
comparison with other baselines under high sparsity. Given the SGD update
scheme, the model gradient in DPF is computed on the pruned model as:

$\boldsymbol{\omega}_{t+1}=\boldsymbol{\omega}_{t}-\eta_{t}\nabla
f(\boldsymbol{\omega}_{t}^{\prime})=\boldsymbol{\omega}_{t}-\eta_{t}\nabla
f(\boldsymbol{\omega}_{t}\odot\mathbf{m}_{t}),$ (5)

taking into account the error feedback (analytically):

$\boldsymbol{\omega}_{t+1}=\boldsymbol{\omega}_{t}-\eta_{t}\nabla
f(\boldsymbol{\omega}_{t}+\mathbf{e}_{t}),$ (6)

where
$\mathbf{e}_{t}=\boldsymbol{\omega}_{t}^{\prime}-\boldsymbol{\omega}_{t}$. In
(5), $\odot$ represents the Hadamard (element-wise) product between the two
model weights, $\boldsymbol{\omega}_{t}$ represents the entire model
parameters, $\boldsymbol{\omega}_{t}^{\prime}$ represents the pruned model
parameters, and $\mathbf{m}$ is the adopted mask function used for pruning as
in, e.g., in [12], [26], and [27]. The mask is applied on the model parameters
$\boldsymbol{\omega}_{t}$ to eliminate weights according to the magnitude of
each weight, thus, producing the pruned $\boldsymbol{\omega}_{t}^{\prime}$.
Applying the gradient, in this case, allows recovering from errors due to
premature masking out of important weights, i.e., the rule in (5) takes a step
that best suits the pruned model (our target). In contrast, all the pruning
methods adopted in FL, e.g., [12], led to sub-optimal decisions by adopting
the rule:

$\boldsymbol{\omega}_{t+1}=\boldsymbol{\omega}_{t}^{\prime}-\eta_{t}\nabla
f(\boldsymbol{\omega}_{t}^{\prime}).$ (7)

One can observe that the update rule in (5) retains more information, as it
only computes gradients of the pruned model, compared to the update rule in
(7). This is expected to yield superior performance under high sparsity.

Moreover, it is known that the multi-collinearity111In multi-collinearity, two
or more independent variables are highly correlated in a regression model,
which violates the independence assumption. challenge is alleviated by the
Least Absolute Shrinkage and Selection Operator (LASSO). LASSO performs
simultaneous variable selection and regularisation [34]. LASSO adds the
$L_{1}$ regularization term to the regression loss function, providing a
solution to cases where the number of model parameters is significantly larger
than the available observations. Apparently, this is the case in DNNs, which
typically involve millions of parameters with only tens of thousands of
observations. The two challenges reported in Section III-B deal with selecting
appropriate dynamic policies for sparsity control and regularization
hyperparameter $\lambda$. To address the challenge C1, we dynamically drop the
least $s\cdot 100\%$ percentile according to weights magnitude. The challenge
C2 is addressed by incrementally increasing the regularization parameter
departing from the principles of LASSO regression. It is also evidenced in
[33] that growing regularization benefits pruning. Based on these
observations, we establish the FedDIP algorithm to maintain the predictive
model performance under extreme sparsity with incremental regularization and
dynamic pruning. To clarify terminology, we refer to our algorithm that
directly applies dynamic pruning as ‘FedDP’ (addressing challenge C1), while
‘FedDIP’ represents the variant that also adds incremental regularization
(addressing both challenges C1 and C2). Collectively, we refer to these
variants as ‘FedD(I)P’. Each node $n\in\mathcal{N}$ first trains a local
sparse DNN model, which contains weights with relatively small magnitudes (see
also Fig. 1). Then, the node $n$ optimizes the proposed local incrementally
regularized loss function at round $t$ as:

$f_{n}(\boldsymbol{\omega}_{t})=\frac{1}{D_{n}}\sum_{(\mathbf{x},y)\in\mathcal{D}}\mathcal{L}(G(\boldsymbol{\omega}_{t},\mathbf{x}),y)+\lambda_{t}\sum_{z=1}^{Z}\|\boldsymbol{\omega}_{t}^{(z)}\|_{2},$
(8)

where the step $t$ dependent regularization parameter $\lambda_{t}$ controls
the degree of model shrinkage, i.e., the sparsity, and $Z$ is the number of
the DNN layers (this, of course, depends on the DNN architecture; in our
experiments, it is the sum of convolutional and fully connected layers). The
norm
$\|\boldsymbol{\omega}^{(z)}\|_{2}=(\sum_{k}\lvert\omega^{(z)}_{k}\rvert^{2})^{1/2}$
is the $L_{2}$ norm of the pruned $z^{th}$ layer of model weights
$\boldsymbol{\omega}^{(z)}$. We then introduce the incremental regularization
over $\lambda_{t}$ based on the schedule:

$\lambda_{t}=\begin{cases}0&\text{if }0\leq t<\frac{T}{Q}\\\ \vdots&\vdots\\\
\frac{\lambda_{\text{max}}\cdot(i-1)}{Q}&\text{if }\frac{(i-1)T}{Q}\leq
t<\frac{iT}{Q}\\\ \vdots&\vdots\\\
\frac{\lambda_{\text{max}}(Q-1)}{Q}&\text{if }\frac{(Q-1)T}{Q}\leq t\leq T\\\
\end{cases}$ (9)

with quantization step size $Q>0$. The influence of $Q$ on regularization is
controlled by adapting $\lambda_{max}$. Such step size divides the
regularization parameter space from $\frac{\lambda_{\max}}{Q}$ to
$\lambda_{\max}$ to achieve a gradual increase of regularization at every
$\frac{T}{Q}$ rounds. In addition, each node $n$ adopts dynamic pruning to
progressively update its local model weights
$\boldsymbol{\omega}_{n}^{\tau+L}$ to optimize (8) as:

$\boldsymbol{\omega}^{\tau,l+1}_{n}=\boldsymbol{\omega}^{\tau,l}_{n}-\eta_{\tau}\nabla
f_{n}(\boldsymbol{\omega}^{\prime(\tau,l)}_{n}),$ (10)

where $\boldsymbol{\omega}^{\prime(\tau+l)}_{n}$ is obtained through pruning
based on a global mask function $\mathbf{m}_{\tau}$ generated by the server
node. Moreover, our gradual pruning policy modifies the sparsity update policy
per round from [35] by incrementally updating the sparsity as:

$s_{t}=s_{p}+(s_{0}-s_{p})\Big{(}1-\frac{t}{T}\Big{)}^{3},$ (11)

where $s_{t}$ represents the sparsity applied to the model pruning at round
$t$, $s_{0}$ is the initial sparsity, and $s_{p}$ is the desired/target
sparsity. Notably, in our approach $s_{0}$ is strictly non-zero; this can be a
moderate sparsity of $s_{0}=0.5$. Such adaptation differentiates our method
from [35], where $s_{0}=0$. In essence, we permit the sparsity to increment
from moderate to extreme levels throughout the process. If considering
$s_{0}>0$, the layer-wise sparsity of the initial mask follows the ERK
distribution introduced in [31]. At the end of a local epoch $l$, the server
node collects $K<N$ model weights $\boldsymbol{\omega}_{n}^{\tau+l}$ from the
selected nodes $n\in\mathcal{N}_{c}$, and calculates the global weights
average as:

$\bar{\boldsymbol{\omega}}^{\tau+l}_{G}=\sum_{n\in\mathcal{N}}\rho_{n}\boldsymbol{\omega}_{n}^{\tau+l}.$
(12)

In addition, the $\mathbf{m}_{\tau}$ mask function is generated based on
pruning on $\bar{\boldsymbol{\omega}}^{\tau+l}_{G}$ with current sparsity
$s_{\tau}$. The FedDIP process is summarized in Algorithm 1, where only pruned
models are exchanged from server to nodes, while pruning is locally achieved
in the clients. Note: FedDIP achieves data-free initialization and generalizes
the DPF [27] in dynamic pruning process. When we set initial $s_{0}=0$ and no
incremental regularization, i.e., $\lambda_{t}=0$, $\forall t$, then FedDIP
reduces to DPF. Moreover, we obtain our variant FedDP if we set
$\lambda_{t}=0$, $\forall t$ with $s_{0}>0$ w.r.t. ERK distribution.

######  Remark 1.

Trade-off between Pruning and Fine-tuning: The FedDIP approach introduces a
reconfiguration horizon, denoted as $R$, during the model training phase to
periodically update the mask function. Specifically, the mask function
$\mathbf{m}_{\tau}$ is updated at every $R$ global round, i.e., when $\tau\mod
R=0$, to ensure a consistent and smooth accuracy learning curve. The value of
this horizon is determined empirically. Potential Outcomes of Insufficient
Pruning: If the mask function remains unchanged throughout the horizon $T$,
there’s a risk that the model could converge to a local optimum. Consequences
of Insufficient Fine-tuning: Conversely, if the mask function undergoes
frequent updates, the changes in the model might not align with the
alterations in the sparse model structure.

######  Remark 2.

Integration of Incremental Regularization and DPF: Differing from the approach
in [33], which centralizes increasing penalty factors on pre-trained models,
FedDIP initiates this from the outset within a distributed learning context.
The integration of incremental regularization with DPF offers advantages,
primarily because DPF obviates the need for post-pruning fine-tuning, making
it preferable to one-shot pruning methods like SNIP.

Algorithm 1 The FedDIP Algorithm

1:$N$ nodes; $T$ global rounds; $E_{l}$ local rounds; initial and target
sparsity $s_{0}$ and $s_{p}$; maximum regularization $\lambda_{\max}$;
quantization step $Q$; reconfiguration horizon $R$

2:Global pruned DNN model weights $\boldsymbol{\omega}_{G}^{\prime}$

3://Server initiliazation

4:if $s_{0}>0$ then

5: Server initializes global mask $\mathbf{m}_{0}$ (ERK distribution)

6:end if

7://Node update & pruning

8:for global round $\tau=1,\ldots,T$ do

9: Server randomly selects $K$ nodes $\mathcal{N}_{c}\subset\mathcal{N}$

10: for selected node $n\in\mathcal{N}_{c}$ in parallel do

11: Receive pruned weights $\boldsymbol{\omega}_{G}^{\prime(\tau-1)}$ from
server node

12: Obtain mask $\mathbf{m}_{\tau-1}$ from
$\boldsymbol{\omega}_{G}^{\prime(\tau-1)}$

13: Train $\boldsymbol{\omega}_{n}^{\tau}$ over $E_{l}$ rounds on data
$\mathcal{D}_{n}$ using (10)

14: if incremental regularization is chosen then

15: Optimize (8) with incremental $\lambda_{\tau}$ in (9)

16: else

17: Optimize (1)

18: end if

19: end for

20: //Server update, aggregation & reconfiguration

21: Server receives models and aggregates $\boldsymbol{\omega}_{G}^{\tau}$ in
(12)

22: if $\tau\mod R==0$ then

23: Reconfigure global mask $\mathbf{m}_{\tau}$ based on pruning
$\boldsymbol{\omega}_{G}^{\tau}$

24: end if

25: Server prunes global model with $\mathbf{m}_{\tau}$ and obtains
$\boldsymbol{\omega}_{G}^{\prime(\tau)}$

26: Server node returns $\boldsymbol{\omega}_{G}^{\prime(\tau)}$ to all nodes.

27:end for

##  V Theoretical & Convergence Analysis

In this section, we provide a theoretical analysis of FedDIP including the
convergence Theorem 1 ensuring stability in training models w.r.t. incremental
regularization and dynamic extreme pruning. Note for Proofs: The proofs of our
Theorem 1 and lemmas are in the Appendix A

At each global round $t\in\\{1,\ldots,T\\}$, $K$ out of $N$ nodes participate,
each one selected with probability $\rho_{n}$ aligned with [36], [37] and
$\sum_{n=1}^{N}\rho_{n}=1$. Let $\boldsymbol{\omega}_{n}^{t}$ and
$\boldsymbol{\omega}_{n}^{\prime(t)}$ be the weights and pruned ones at round
$t$ on node $n$, respectively, with

$\boldsymbol{\omega}_{n}^{\prime(t)}=\boldsymbol{\omega}_{n}^{t}\odot\mbox{m}^{t}.$
(13)

Let also $\mathbf{v}_{n}^{t}$ and $\tilde{\mathbf{v}}_{n}^{t}$ be the expected
and estimated gradients at $t$, respectively, on node $n$. Based on
$\boldsymbol{\omega}_{n}^{\prime(t)}$, we obtain:
$\mathbf{v}_{n}^{\prime(t)}=\nabla f(\boldsymbol{\omega}_{n}^{\prime(t)})$
while $\tilde{\mathbf{v}}_{n}^{\prime(t)}$ is the estimated one. The global
aggregated model for FedAvg is:

$\displaystyle\bar{\boldsymbol{\omega}}^{t}$
$\displaystyle=\frac{1}{K}\sum_{n\in\mathcal{N}_{c}}\boldsymbol{\omega}^{t}_{n},$
(14)

while before the server sends the model, it is pruned as

$\bar{\boldsymbol{\omega}}^{\prime(t)}=\frac{1}{K}\sum_{n\in\mathcal{N}_{c}}\boldsymbol{\omega}^{t}_{n}\odot\mbox{m}^{t}.$
(15)

The global estimated aggregated gradient and expected global gradient,
respectively, are:

$\mathbf{\tilde{{v}}}^{t}=\frac{1}{K}\sum_{n\in\mathcal{N}_{c}}\tilde{\mathbf{v}}_{n}^{t}\mbox{
and
}\mathbf{\bar{v}}^{t}=\frac{1}{K}\sum_{n\in\mathcal{N}_{c}}\mathbf{v}_{n}^{t}.$
(16)

Similarly, for DPF, we have that:

$\mathbf{\tilde{{v}}}^{\prime(t)}=\frac{1}{K}\sum_{n\in\mathcal{N}_{c}}\tilde{\mathbf{v}}_{n}^{\prime(t)}\text{
and
}\mathbf{\bar{v}}^{\prime(t)}=\frac{1}{K}\sum_{n\in\mathcal{N}_{c}}\mathbf{v}_{n}^{\prime(t)}.$
(17)

In FedAvg, $\bar{\boldsymbol{\omega}}^{t}$ is updated as:
$\bar{\boldsymbol{\omega}}^{t+1}=\bar{\boldsymbol{\omega}}^{t}-\eta_{t}\tilde{\mathbf{v}}^{t}$,
while the update rule based on DPF at node $n$ is:

$\boldsymbol{\omega}^{t+1}_{n}=\boldsymbol{\omega}^{t}_{n}-\eta_{t}\tilde{\mathbf{v}}_{n}^{\prime(t)},$
(18)

where $\boldsymbol{\omega}^{t}_{n}=\boldsymbol{\bar{\omega}}^{\prime(t)}$.
Similarly, $\bar{\boldsymbol{\omega}}^{t+1}$ is updated as:

$\bar{\boldsymbol{\omega}}^{t+1}=\bar{\boldsymbol{\omega}}^{\prime(t)}-\eta_{t}\tilde{\mathbf{v}}^{\prime(t)}.$
(19)

###### Definition 1.

According to [27], the quality of pruning is defined by the parameter
$\delta_{t}\in[0,1]$ as:

$\delta_{t}:=\frac{\|\boldsymbol{\omega}^{t}-\boldsymbol{\omega}^{\prime(t)}\|^{2}_{F}}{\|\boldsymbol{\omega}^{t}\|^{2}_{F}}$
(20)

where $\|.\|^{2}_{F}$ is the square of Frobenius matrix norm. $\delta_{t}$
indicates the degree of information loss by pruning in terms of magnitude. A
smaller $\delta_{t}$ stands for less information loss.

###### Definition 2.

Following the Definition $1$ in [38], a measurement $\gamma$ of non-i.i.d.
(non-independent and identically distributed) data is defined as follows:

$\gamma=\frac{\sum_{n=1}^{N}p_{n}\|\nabla
f_{n}(\boldsymbol{\omega})\|^{2}}{\|\sum_{n=1}^{N}p_{n}\nabla
f_{n}(\boldsymbol{\omega})\|^{2}},$ (21)

with $\gamma\geq 1$; $\gamma=1$ holds in i.i.d case.

We list our assumptions for proving the convergence of FedDIP in the learning
phase.

###### Assumption 1.

$L-$Smoothness.
$,\forall\boldsymbol{\omega}^{t_{1}},\boldsymbol{\omega}^{t_{2}}\in\mathbb{R}^{d}$,
$L\in\mathbb{R}$

$\displaystyle f(\boldsymbol{\omega}^{t_{1}})\leq
f(\boldsymbol{\omega}^{t_{2}})+(\boldsymbol{\omega}^{t_{1}}-\boldsymbol{\omega}^{t_{2}})^{\top}\nabla
f(\boldsymbol{\omega}^{t_{2}})+\frac{L}{2}\|\boldsymbol{\omega}^{t_{1}}-\boldsymbol{\omega}^{t_{2}}\|^{2}$

###### Assumption 2.

$\mu-$Lipschitzness.
$\forall\boldsymbol{\omega}^{t_{1}},\boldsymbol{\omega}^{t_{2}}\in\mathbb{R}^{d}$
and $\mu\in\mathbb{R}$

$\|f(\boldsymbol{\omega}^{t_{1}})-f(\boldsymbol{\omega}^{t_{2}})\|\leq\mu\|\boldsymbol{\omega}^{t_{1}}-\boldsymbol{\omega}^{t_{2}}\|$
(22)

###### Assumption 3.

Bounded variance for gradients. Following Assumption 3 in [37], the local
model gradients on each node $n$ are self-bounded in variance:

$\mathbb{E}[\|\tilde{\mathbf{v}}_{n}^{t}-\mathbf{v}_{n}^{t}\|^{2}]\leq\sigma^{2}_{n}.$
(23)

###### Assumption 4.

Bounded weighted aggregation of gradients. Following Assumption 4 in [38], the
aggregation of local gradients at time $t$ are bounded as:

$\|\sum_{n=1}^{N}\rho_{n}\mathbf{v}_{n}^{t}\|^{2}\leq G^{2},$ (24)

where $\sum_{n=1}^{N}\rho_{n}=1$ and
$\sum_{n=1}^{N}\rho_{n}\mathbf{v}_{n}^{t}$ stands for the weighted aggregation
of local gradients; $G\in\mathbb{R}$.

######  Theorem 1 (FidDIP Convergence).

Consider the Assumptions 1, 2 and 3, Lemmas 1, 2, 3, and let
$\eta_{t}=\frac{1}{tL}$, $L>0$. Then, the convergence rate of the FedDIP
process is bounded by:

$\frac{1}{T}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}\leq
2L\mathbb{E}(f(\boldsymbol{\omega}_{1})-f^{*})+\\\
2L\sum_{t=1}^{T}[\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|]+\frac{\pi^{2}}{3L^{2}}\chi,$
(25)

where $f(\boldsymbol{\omega}_{1})$ and $f^{*}$ stand for the initial loss and
the final convergent stable loss, with
$\chi=\frac{(\gamma-1)L^{2}+L}{2K}\sum_{n=1}^{N}\rho_{n}\sigma^{2}_{n}+\frac{(\gamma-1)\gamma
E_{l}^{2}L^{2}G^{2}}{2}$, and $\gamma$ defined in Definition 2.

###### Proof.

Refer to ‘Note for Proofs’ at the beginning of this section. ∎

In Theorem 1, the first term of the right-hand side of the inequality (25)
denotes the gap between the initial and final loss, while $\chi$ goes to zero
as $K\gg 1$ and the i.i.d. case assumption holds. This also suggests that
non-i.i.d. case results in large boundaries. The quantity
$\frac{1}{T}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}$ is bounded by the loss
produced by pruning. Overall, the convergence result shows that the $L_{2}$
norms of the pruned gradients parameters vanish over time, which indicates
that a stable model is obtained at the end (recall, a stable gradient vector
enables a small change on the model under SGD).

##  VI Experimental Evaluation

###  VI-A Experimental Setup

Datasets and Models: We experiment with the datasets Fashion-MNIST [39],
CIFAR10, and CIFAR100 [40]. Fashion-MNIST consists of $60,000$ training and
$10,000$ test 28x28 grayscale images labeled from 10 classes. Both of CIFAR
datasets consist of $50,000$ training and $10,000$ test 32x32 color images; in
CIFAR10 and CIFAR100 there are 10 classes (6000 images per class) and 100
classes (600 images per class), respectively. We consider the i.i.d.
(independent and identically distributed) case to compare all the algorithms
and extend FedDIP to be applied for non-i.i.d. cases. To test and compare the
efficiency of FedDIP, we use different well-known CNN architectures:
LeNet-5[41], AlexNet [42] and Resnet-18 [7] as backbone (dense or unpruned)
models, with the baseline FedAvg [1] and the pruning baselines PruneFL [12],
PruneTrain [26], FedDST [29], DPF [27] (equivalent to FedDP as discussed
above), and SNIP [23]. For the non-i.i.d. case, we adopt the pathological data
partition method in [1], which assigns only two classes for each node. We
merge FedDIP with FedProx [43], a generalization and re-parametrization of
FedAvg to address the heterogeneity of data (coined FedDIP+Prox), and compare
with baseline FedAvg and FedProx. Our target is to evaluate FedDIP’s accuracy,
storage, and communication efficiency in FL environments under extreme
sparsity.

Configurations: Table II details our configurations. For PruneFL, FedDST, and
PruneTrain, we experimentally determined the optimal reconfiguration intervals
$R$ to be $20$, $20$, and $1$, respectively, to ensure the best possible model
performance; the same for step size $Q$ for all models. Especially, the
annealing factor for FedDST is set as $0.5$. As SNIP prunes the model before
training, the global mask is pruned via one-shot achieving the target sparsity
$s_{p}$. We used grid-search to fix the penalty factor for PruneTrain ranging
from $10^{-1}$ to $10^{-5}$ for different experiments. When necessary, other
hyperparameters were set to match ours. In non-i.i.d. case, the penalty for
the proximal term in FedProx is determined via grid-search ranging from
$10^{-1}$ to $10^{-5}$. FedDIP+Prox adopts the optimal combination of penalty
values for FedDIP and FedProx.

Datasets | Fashion-MNIST | CIFAR10 | CIFAR100
---|---|---|---
DNN/CNN Model | LeNet-5 | AlexNet | ResNet-18
Number of pruning layers ($Z$) | 5 | 8 | 18
Initial learning rate ($\eta_{0}$) | $0.01$ | $0.1$ | $0.1$
Number of clients per round ($K$) |  $5$ (out of $50$) |  $5$ (out of $50$) |  $5$ (out of $50$)
Batchsize in SGD | $64$ | $128$ | $128$
Initial sparsity ($s_{0}$) | $0.5$ | $0.5$ | $0.05$
Global rounds ($T$) | $1,000$ | $1,000$ | $1,000$
Reconfiguration interval ($R$) | $5$ | $5$ | $5$
Regularization step size ($Q$) | $10$ | $10$ | $10$
Local round ($E_{l}$) | $5$ | $5$ | $5$
Maximum penalty ($\lambda_{\max}$) | $10^{-3}$ | $10^{-3}$ | $5\cdot 10^{-3}$
Table II: Configuration Table

Hardware: Our FedDIP framework and experiments are implemented and conducted
on GeForce RTX 3090s GPUs in the institution’s HPC environment.

###  VI-B Performance Under Extreme Sparsity

To demonstrate the performance of FedDIP and other baseline methods under
extreme sparsity, we set target $s_{p}=0.9$ for both Fashion-MNIST and CIFAR10
tasks and $s_{p}=0.8$ for the CIFAR100 task. Notably, as $s_{p}=0.9$ causes
divergence during the training of AlexNet with SNIP, we adjust $s_{p}$ to
$0.8$ for SNIP in this particular case.

####  VI-B1 Accuracy

Figures 2(a), 3(a), and 4(a) demonstrate that FedDIP surpasses other baselines
in achieving the highest top-1 accuracy (ratio of the correctly classified
images) while maintaining the same extreme target sparsity. As indicated in
Table III, to attain target sparsity of $s_{p}=0.9$ and $s_{p}=0.8$
respectively, FedDIP only compromises LeNet-5 and ResNet-18 model accuracy by
$1.24\%$ and $1.25\%$, respectively. For AlexNet, FedDIP can even improve
model performance $0.7\%$, compared with FedAvg with $s_{p}=0.9$.

####  VI-B2 Cumulative Communication & Training Cost

To make a fair comparison of cumulative communication cost during training
(amount of information exchanged in MB) w.r.t. a fixed budget, we showcase the
relationship between communication cost and accuracy. Figures 2(b), 3(b),
4(b), and specifically Table IV present a comprehensive overview, emphasizing
that FedDIP, when provided with adequate communication cost (budget),
effectively prunes the model across all experiments outperforming the other
models. This indicates the trade-off between model performance and
communication/training cost. FedDIP demonstrates comparable communication
efficiency to other baselines, principally due to the minimal decrement in
model performance. Through our experiments, it is evidenced that FedDIP
achieves optimally pruned models under conditions of extreme sparsity, while
incurring less or equivalent communication costs compared to FedAvg. Even in
the early stages (i.e., in restricted budget cases), FedDIP manages to match
the communication efficiency of other pruning methods in the CIFAR
experiments. This underscores the capacity of our approach to effectively
balance model performance and communication expenditure. All in all, FedDIP
introduces only minor computational overhead due to the incremental
regularization, while achieving high accuracy compared to baselines. This
computational requirement is on par with that of PruneTrain, PruneFL, and
SNIP, given the same sparsity at each epoch. A slight increase in
computational cost can be justified by the improvements achieved in the final
model performance considering extremely high sparsity. The size of the pruned
CNN models (Table III) has been significantly reduced ($\sim$ 1 order of
magnitude) from the un-pruned models in FedAvg.

(a) Test accuracy.

(b) Test accuracy vs. communication budget.

Figure 2: Fashion-MNIST experiment with LeNet-5.

(a) Test accuracy.

(b) Test accuracy vs. communication budget.

Figure 3: CIFAR10 experiment with AlexNet.

(a) Test accuracy.

(b) Test accuracy vs. communication budget.

Figure 4: CIFAR100 experiment with ResNet18.

####  VI-B3 Experiments with non-i.i.d. data

As shown in Table V, our methodology exhibits strong adaptability to FedProx
(non-pruning), yielding commendable results on non-i.i.d. data. When
juxtaposed with FedAvg, our approach manages to maintain comparable results
even after pruning $90\%$ of model parameters, albeit at a slight trade-off of
1-2% in model accuracy in the experiments with LeNet-5 and AlexNet. Across a
span of $T=1000$ rounds, FedDIP emerges as the superior performer in terms of
top-1 accuracy, particularly at sparsity $s_{p}=0.8$ in ResNet-18. This
comprehensive suite of results underscores the adaptability of FedDIP in
effectively managing non-i.i.d. cases, even in extreme sparsity.

Table III: Test Accuracy (top-1) | Model Performance ($\%$)1 with target sparsity $s_{p}$
---|---
Model |  LeNet;$s_{p}=.9$ |  AlexNet;$s_{p}=.9$ |  ResNet;$s_{p}=.8$
FedAvg | 89.50 (.09) | 85.07 (.13) | 70.92 (.10)
FedDP | 88.06 (.08) | 84.81 (.18) | 69.23 (.14)
FedDIP |  88.26 (0.09) |  85.14 (.22) |  69.67 (.10)
PruneFL | 86.00 (.10) | 81.64 (.17) | 68.17 (.20)
SNIP | 86.08 (.15) | 80.10 (.15) | 51.46 (.11)
PruneTrain | 84.36 (.10) | 79.73 (.10) | 69.39 (.08)
FedDST | 80.37 (.20) | – | 68.06 (.20)
# param.(FedAvg) | 62K | 23.3M | 11.2M
# param.(pruned) | 6.1K | 2.3M | 2.2M
1 Mean accuracy; standard deviation in ‘()’.
Table IV: Communication Efficiency | Model Performance ($\%$) with communication budget
---|---
Case | LeNet-5(1) | AlexNet(2) | ResNet-18(3)
FedAvg | 86.76 | 78.98 | 70.06
FedDP | 86.54 | 82.29 | 69.10
FedDIP | 86.62 | 82.58 | 69.57
PruneFL | 85.57 | 81.73 | 68.4
SNIP | 86.32 | 80.11 | 51.63
PruneTrain | 82.68 | 78.16 | 69.42
FedDST | 80.37 | – | 68.06
Communication budget (1)$4\cdot 10^{3}$MB, (2)$1.8\cdot 10^{6}$MB, (3)$2\cdot
10^{6}$MB
Table V: Extension to non-i.i.d. data | Model Performance1 ($\%$) (non-i.i.d. case)
---|---
Case | LeNet-5 | AlexNet | ResNet-18
FedAvg | 76.42(0.28) | 61.59 (0.73) | 16.44 (0.49)
FedProx |  76.63(0.34) |  65.74 (0.26) | 18.48 (0.91)
FedDIP+Prox | 74.49 (0.09) | 60.47 (0.52) |  19.22 (0.8)
1 Mean of the highest five top-1 test accuracy during $T$ rounds.

###  VI-C FedDIP Sparsity Analysis

####  VI-C1 Layerwise sparsity

Figure 5 shows the sparsity per layer of ResNet-18 ($s_{p}=0.8$), LeNet-5
($s_{p}=0.9$), and AlexNet ($s_{p}=0.9$). Notably, the first layers of all
models are the least pruned ($0.3\leq s\leq 0.4$), which is attributed to
their significant role in general feature extraction. Furthermore, there is a
correlation between the number of weights per layer and the corresponding
sparsity level. This stems from the initial ERK distribution, which allocates
a higher degree of sparsity to layers containing more weights, although we
adopt global magnitude pruning in a later process. Such correlation is
remarkable in both convolutional and fully-connected layers of the models. In
convolutional layers, the correlations are found to be perfectly linear for
LeNet-5 with a correlation coefficient $\varrho\simeq 1$, for AlexNet we
obtain $\varrho=0.86$, while for ResNet-18 $\varrho=0.8$. For fully-connected
layers, since only one exists in ResNet-18, we obtain $\varrho=(0.91,0.82)$
for LeNet-5, AlexNet, respectively. These findings highlight the dependency of
layerwise sparsity and the number of weights per layer, reflecting the
influence of the ERK distribution in FedDIP’s initialization.

(a) Distribution of layer sparsity; ResNet-18.

(b) Distribution of layer sparsity; AlexNet.

(c) Distribution of layer sparsiy; LeNet-5.

Figure 5: Layerwise pruning sparsity; f0w stands for (f)eatures layer, layer
index (e.g, 0), and (w)eights, respectively. c stands for the fully-connected
classifier layer (the same notation is used for other layers). ResNet-18
consists of 18 pruning layers.

####  VI-C2 FedDIP in extreme sparsity

We examine the efficiency of FedDIP under varying conditions of extreme
sparsity. For Fashion-MNIST and CIFAR10 experiments, we investigate two
additional extreme sparsity levels $s_{p}=0.95$ and $s_{p}=0.99$, and for
CIFAR100 experiments, we investigate $s_{p}=0.9$ and $s_{p}=0.95$. These
conditions provide a robust assessment of FedDIP’s performance across a range
of extreme sparsity. As shown in Figure 6, under extreme sparsity like $0.95$
and $0.99$, the largest drops $\Delta$ in classification accuracy are only
$\Delta=6.97\%$, $\Delta=5.03\%$, and $\Delta=8.08\%$, respectively. This also
comes with further 90%, 89%, and 74% reduction on LeNet-5, Alex-Net, and
ResNet-18 model sizes, respectively. This indicates (i) FedDIP’s efficiency in
storing and managing trained and pruned models as well as (ii) efficiency in
inference tasks (after training) due to relatively small models. All in all,
the pruned DNN models’ performance is relatively high with small accuracy
drops and high model compression (92%) across different tasks.

Figure 6: FedDIP performance on extreme sparsity values.

##  VII Conclusions

We propose FedDIP, a novel FL framework with dynamic pruning and incremental
regularization achieving highly accurate and extremely sparse DNN models.
FedDIP gradually regularizes sparse DNN models obtaining extremely compressed
models that maintain baseline accuracy and ensure controllable communication
overhead. FedDIP is a data-free initialization method based on ERK
distribution. We provide a theoretical convergence analysis of FedDIP and
evaluate it across different DNN structures. FedDIP achieves comparable and
higher accuracy against FL baselines and state-of-the-art FL-based model
pruning approaches, respectively, over extreme sparsity using benchmark data
sets (i.i.d. & non-i.i.d. cases). Our agenda includes addressing heterogeneity
in personalized FL environments.

## Acknowledgement

The authors would like to express their sincere gratitude to Dr. Fani
Deligianni for her invaluable insights and discussions during peer
communications.

This work is partially funded by the EU Horizon Grant ‘Integration and
Harmonization of Logistics Operations’ TRACE (#101104278) and ’National
Natural Science Foundation of China’ (NSFC) under Grant #72201093.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [2] G. A. Kaissis, M. R. Makowski, D. Rückert, and R. F. Braren, “Secure, privacy-preserving and federated machine learning in medical imaging,” _Nature Machine Intelligence_ , vol. 2, no. 6, pp. 305–311, 2020.
  * [3] Q. Yang, Y. Liu, Y. Cheng, Y. Kang, T. Chen, and H. Yu, “Federated learning,” _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , vol. 13, no. 3, pp. 1–207, 2019.
  * [4] G. Long, Y. Tan, J. Jiang, and C. Zhang, “Federated learning for open banking,” in _Federated learning_. Springer, 2020, pp. 240–254.
  * [5] J. Xu, B. S. Glicksberg, C. Su, P. Walker, J. Bian, and F. Wang, “Federated learning for healthcare informatics,” _Journal of Healthcare Informatics Research_ , vol. 5, no. 1, pp. 1–19, 2021.
  * [6] S. Niknam, H. S. Dhillon, and J. H. Reed, “Federated learning for wireless communications: Motivation, opportunities, and challenges,” _IEEE Comm. Magazine_ , vol. 58, no. 6, pp. 46–51, 2020.
  * [7] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _IEEE CVPR_ , 2016, pp. 770–778.
  * [8] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _arXiv preprint arXiv:1409.1556_ , 2014.
  * [9] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language models are unsupervised multitask learners,” 2019.
  * [10] A. F. Aji and K. Heafield, “Sparse communication for distributed gradient descent,” in _EMNLP’17_ , 2017, pp. 440–445.
  * [11] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” _NeurIPS’18_ , vol. 31, 2018.
  * [12] Y. Jiang, S. Wang, V. Valls, B. J. Ko, W.-H. Lee, K. K. Leung, and L. Tassiulas, “Model pruning enables efficient federated learning on edge devices,” _IEEE TNNLS_ , 2022.
  * [13] Z. Zhou, X. Chen, E. Li, L. Zeng, K. Luo, and J. Zhang, “Edge intelligence: Paving the last mile of artificial intelligence with edge computing,” _Proc. of IEEE_ , vol. 107, no. 8, pp. 1738–1762, 2019.
  * [14] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Proc. Magazine_ , vol. 37, no. 3, pp. 50–60, 2020.
  * [15] N. Strom, “Scalable distributed dnn training using commodity gpu cloud computing,” in _16th Intl Conf Speech Comm. Assoc._ , 2015.
  * [16] J. Konečnỳ and P. Richtárik, “Randomized distributed mean estimation: Accuracy vs. communication,” _Frontiers in Applied Mathematics and Statistics_ , vol. 4, p. 62, 2018.
  * [17] P. Jiang and G. Agrawal, “A linear speedup analysis of distributed deep learning with sparse and quantized communication,” _NeurIPS’18_ , vol. 31, 2018.
  * [18] Y. Lin, S. Han, H. Mao, Y. Wang, and W. J. Dally, “Deep Gradient Compression: Reducing the communication bandwidth for distributed training,” in _ICLR_ , 2018.
  * [19] S. Shi, K. Zhao, Q. Wang, Z. Tang, and X. Chu, “A convergence analysis of distributed sgd with communication-efficient gradient sparsification.” in _IJCAI_ , 2019, pp. 3411–3417.
  * [20] J. Sun, T. Chen, G. Giannakis, and Z. Yang, “Communication-efficient distributed learning via lazily aggregated quantized gradients,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [21] T. Chen, G. Giannakis, T. Sun, and W. Yin, “Lag: Lazily aggregated gradient for communication-efficient distributed learning,” _NeurIPS’18_ , vol. 31, 2018.
  * [22] Y. Cheng, D. Wang, P. Zhou, and T. Zhang, “A survey of model compression and acceleration for deep neural networks,” _arXiv preprint arXiv:1710.09282_ , 2017.
  * [23] N. Lee, T. Ajanthan, and P. H. Torr, “Snip: Single-shot network pruning based on connection sensitivity,” _ICLR 2019 arXiv preprint arXiv:1810.02340_ , 2018.
  * [24] Y. He, X. Zhang, and J. Sun, “Channel pruning for accelerating very deep neural networks,” in _IEEE ICCV_ , 2017, pp. 1389–1397.
  * [25] T. Zhang, S. Ye, K. Zhang, J. Tang, W. Wen, M. Fardad, and Y. Wang, “A systematic dnn weight pruning framework using alternating direction method of multipliers,” in _ECCV_ , 2018, pp. 184–199.
  * [26] S. Lym, E. Choukse, S. Zangeneh, W. Wen, S. Sanghavi, and M. Erez, “Prunetrain: fast neural network training by dynamic sparse model reconfiguration,” in _SC’19_ , 2019, pp. 1–13.
  * [27] T. Lin, S. U. Stich, L. F. Barba Flores, D. Dmitriev, and M. Jaggi, “Dynamic model pruning with feedback,” in _ICLR_ , no. CONF, 2020.
  * [28] X. Yao, T. Huang, R.-X. Zhang, R. Li, and L. Sun, “Federated learning with unbiased gradient aggregation and controllable meta updating,” _arXiv preprint arXiv:1910.08234_ , 2019.
  * [29] S. Bibikar, H. Vikalo, Z. Wang, and X. Chen, “Federated dynamic sparse training: Computing less, communicating less, yet learning better,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 36, no. 6, 2022, pp. 6080–6088.
  * [30] A. Li, J. Sun, B. Wang, L. Duan, S. Li, Y. Chen, and H. Li, “Lotteryfl: empower edge intelligence with personalized and communication-efficient federated learning,” in _IEEE/ACM SEC_. IEEE, 2021, pp. 68–79.
  * [31] U. Evci, T. Gale, J. Menick, P. S. Castro, and E. Elsen, “Rigging the lottery: Making all tickets winners,” in _ICML_. PMLR, 2020, pp. 2943–2952.
  * [32] M. Zhu and S. Gupta, “To prune, or not to prune: exploring the efficacy of pruning for model compression,” _arXiv preprint arXiv:1710.01878_ , 2017.
  * [33] H. Wang, C. Qin, Y. Zhang, and Y. Fu, “Neural pruning via growing regularization,” in _ICLR_ , 2021.
  * [34] W. Fu and K. Knight, “Asymptotics for lasso-type estimators,” _The Annals of Statistics_ , vol. 28, no. 5, pp. 1356–1378, 2000.
  * [35] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” _PMLR_ , vol. 2, pp. 429–450, 2020.
  * [36] F. Haddadpour and M. Mahdavi, “On the convergence of local descent methods in federated learning,” _CoRR_ , vol. abs/1910.14425, 2019. [Online]. Available: http://arxiv.org/abs/1910.14425
  * [37] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” in _ICLR_ , 2019.
  * [38] S. Wan, J. Lu, P. Fan, Y. Shao, C. Peng, and K. B. Letaief, “Convergence analysis and system design for federated learning over wireless networks,” _IEEE JSAC_ , vol. 39, no. 12, pp. 3622–3639, 2021.
  * [39] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” _arXiv preprint arXiv:1708.07747_ , 2017.
  * [40] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * [41] Y. LeCun _et al._ , “Lenet-5, convolutional neural networks,” _URL: http://yann. lecun. com/exdb/lenet_ , vol. 20, no. 5, p. 14, 2015.
  * [42] A. Krizhevsky, “One weird trick for parallelizing convolutional neural networks,” _CoRR_ , vol. abs/1404.5997, 2014. [Online]. Available: http://arxiv.org/abs/1404.5997
  * [43] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” in _PMLS_ , vol. 2, 2020, pp. 429–450.

##  Appendix A Proof for FedDIP

Before the proof of convergence Theorem 1, we stress that:

$\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t+1)})-f(\boldsymbol{\bar{\omega}}^{\prime(t)})]=\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t+1)})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{(t+1)})]\\\
+\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{(t+1)})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t)})],$
(26)

where mask update only happens at server and
$\boldsymbol{\bar{\omega}}^{\prime(t)}$ is the global model received by nodes
at time $t$, as the start of the local model training phase.

######  Lemma 1.

Given any mask function $\mathbf{m}:=\\{0,1\\}^{n\times p}$ for pruning, the
Frobenius norm of model weight/gradients matrix $\boldsymbol{\omega}$ is
greater than or equal to the pruned one $\mathbf{m}\odot\boldsymbol{\omega}$,
i.e.,

$\|\boldsymbol{\omega}\|\geq\|\mathbf{m}\odot\boldsymbol{\omega}\|.$ (27)

###### Proof.

According to the definition of Frobenius norm, we have

$\|\mathbf{m}\odot\boldsymbol{\omega}\|^{2}=Tr([\mathbf{m}\odot\boldsymbol{\omega}]^{T}\cdot[\mathbf{m}\odot\boldsymbol{\omega}])\\\
=\sum_{i=1}^{n}\sum_{j=1}^{p}\lvert
m_{ij}\boldsymbol{\omega}_{ij}\rvert^{2}\leq\sum_{i=1}^{n}\sum_{j=1}^{p}\lvert\boldsymbol{\omega}_{ij}\rvert^{2}=\|\boldsymbol{\omega}\|^{2}.$

∎

Lemma 1 provides the foundation that the quality of pruning $\delta_{t}$,
respectively, are in the range $[0,1]$.

######  Lemma 2.

Given the Definition 1 and Assumption 2, the effect of pruning on pruned model
weights at server ($\delta_{t+1}$) is bounded as:

$\displaystyle\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t+1)})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{t+1})]\leq\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|]$
(28)

###### Proof.

$\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t+1)})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{t+1})]\leq\mu\mathbb{E}[\|\boldsymbol{\bar{\omega}}^{\prime(t+1)}-\boldsymbol{\bar{\omega}}^{t+1}\|]\\\
=\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|].$ (29)

∎

######  Lemma 3.

Under the definitions provided in Section V and Assumptions $1$ & $4$,
$\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{t+1})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t)})]$
is bounded by:

$\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{t+1})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t)})]\leq\frac{(\gamma-1)L^{2}\eta_{t}^{2}+\eta_{t}^{2}L}{2K}\sum_{n=1}^{N}\rho_{n}\sigma^{2}_{n}+\\\
\frac{(\gamma-1)\gamma
E_{l}\eta_{t}^{2}L^{2}}{2}\sum_{k=t_{c}+1}^{t_{c}+E_{l}}\|\sum_{n=1}^{N}\rho_{n}\mathbf{v}_{n}^{\prime(k)}\|^{2}-\frac{\eta_{t}}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}+\\\
\frac{\gamma\eta_{t}^{2}L-\eta_{t}}{2}\|\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}\|^{2}.$
(30)

###### Proof.

Firstly, according to the Assumption 1, we have

$\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{t+1})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t)})]\\\
\leq\mathbb{E}[<\boldsymbol{\bar{\omega}}^{t+1}-\boldsymbol{\bar{\omega}}^{\prime(t)},\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})>]+\frac{L}{2}\mathbb{E}\|\boldsymbol{\bar{\omega}}^{t+1}-\boldsymbol{\bar{\omega}}^{\prime(t)}\|^{2}\\\
\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny{\small\smalla⃝}}}}{=}}{\frac{\eta_{t}^{2}L}{2}\mathbb{E}\|\tilde{\mathbf{v}}^{\prime(t)}\|^{2}}-\mathbb{E}[<\eta_{t}\tilde{\mathbf{v}}^{\prime(t)},\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})>],$ (31)

where $\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny{\small\smalla⃝}}}}{=}}{}$
holds because of (19). Following the proof structure in [38], we give the
boundary for $-\mathbb{E}[<\eta_{t}\tilde{\mathbf{v}}^{\prime(t)},\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})>]$ and
$\mathbb{E}\|\tilde{\mathbf{v}}^{\prime(t)}\|^{2}$, respectively.

According to the variance formula and the definition of
$\bar{\mathbf{v}}^{\prime(t)}$, we can expand
$\mathbb{E}\|\tilde{\mathbf{v}}^{\prime(t)}\|^{2}$ as follows:

$\mathbb{E}\|\tilde{\mathbf{v}}^{\prime(t)}\|^{2}=\mathbb{E}\|\tilde{\mathbf{v}}^{\prime(t)}-\mathbb{E}(\tilde{\mathbf{v}}^{\prime(t)})\|^{2}+[\mathbb{E}(\tilde{\mathbf{v}}^{\prime(t)})]^{2}\\\
=\mathbb{E}\|\tilde{\mathbf{v}}^{\prime(t)}-\bar{\mathbf{v}}^{\prime(t)}\|^{2}+\|\bar{\mathbf{v}}^{\prime(t)}\|^{2}.$
(32)

Recall that $P_{t}$ is the selection probability of clients, thus, one can
obtain:

$\|\bar{\mathbf{v}}^{\prime(t)}\|^{2}=\left\|\frac{1}{K}\mathbb{E}_{P_{t}}[\sum_{n\in
P_{t}}\mathbf{v}_{n}^{\prime(t)}]\right\|^{2}\leq\frac{1}{K}\mathbb{E}_{P_{t}}\left[\sum_{n\in
P_{t}}\|\mathbf{v}_{n}^{\prime(t)}\|^{2}\right]$ (33)

The last inequality holds due to Jenson’s Inequality. Similarly, based on the
definitions in (17), we have:

$\mathbb{E}[\|\tilde{\mathbf{v}}^{\prime(t)}-\bar{\mathbf{v}}^{\prime(t)}\|^{2}]=\mathbb{E}[\|\mathbb{E}_{P_{t}}[\frac{1}{K}\sum_{n\in
P_{t}}\tilde{\mathbf{v}}_{n}^{\prime(t)}-\frac{1}{K}\sum_{n\in
P_{t}}\mathbf{v}_{n}^{\prime(t)}]\|^{2}]\\\
=\frac{1}{K^{2}}\\{\mathbb{E}[\mathbb{E}_{P_{t}}[\sum_{n\in
P_{t}}\|\tilde{\mathbf{v}}_{n}^{\prime(t)}-\mathbf{v}_{n}^{\prime(t)}\|^{2}]]\\\
+\sum_{i\not=j}<\tilde{\mathbf{v}}_{i}^{\prime(t)}-\mathbf{v}_{i}^{\prime(t)},\tilde{\mathbf{v}}_{j}^{\prime(t)}-\mathbf{v}_{j}^{\prime(t)}>\\}\\\
=\frac{1}{K}\mathbb{E}[\sum_{n=1}^{N}\rho_{n}\|\tilde{\mathbf{v}}_{n}^{\prime(t)}-\mathbf{v}_{n}^{\prime(t)}\|^{2}].$
(34)

Substituting (33) and (34) into (32), and according to the Lemma $1$,
Definition 2 and Assumption $4$, we obtain that:

$\mathbb{E}\|\tilde{\mathbf{v}}^{\prime(t)}\|^{2}\leq\frac{1}{K}\mathbb{E}[\sum_{n\in
P_{t}}\|\mathbf{v}_{n}^{\prime(t)}\|^{2}]+\frac{1}{K^{2}}\mathbb{E}[\sum_{n\in
P_{t}}\|\tilde{\mathbf{v}}_{n}^{\prime(t)}-\mathbf{v}_{n}^{\prime(t)}\|^{2}]\\\
\leq\sum_{n=1}^{N}\rho_{n}\|\mathbf{v}_{n}^{\prime(t)}\|^{2}+\frac{1}{K}\mathbb{E}[\sum_{n=1}^{N}\|\tilde{\mathbf{v}}_{n}^{\prime(t)}-\mathbf{v}_{n}^{\prime(t)}\|^{2}]\\\
\leq\sum_{n=1}^{N}\rho_{n}\|\mathbf{v}_{n}^{\prime(t)}\|^{2}+\frac{1}{K}\sum_{n=1}^{N}\rho_{n}\sigma_{n}^{2}\\\
\leq\gamma\sum_{n=1}^{N}\|\rho_{n}\mathbf{v}_{n}^{\prime(t)}\|^{2}+\frac{1}{K}\sum_{n=1}^{N}\rho_{n}\sigma_{n}^{2}.$
(35)

Next, we provide the boundary for
$-\mathbb{E}[<\eta_{t}\tilde{\mathbf{v}}^{\prime(t)},\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})>]$ .

$-\mathbb{E}[\langle\tilde{\mathbf{v}}^{\prime(t)},\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\rangle]=-\langle\mathbb{E}[\frac{1}{K}\sum_{n\in
P_{t}}\tilde{\mathbf{v}}_{n}^{\prime(t)}],\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\rangle\\\
=-\langle\mathbb{E}[\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}],\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\rangle\\\
\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny{\small\smalla⃝}}}}{=}}-\frac{1}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}-\frac{1}{2}\|\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}\|^{2}+\frac{1}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})-\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}\|^{2}\\\
=-\frac{1}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}-\frac{1}{2}\|\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}\|^{2}+\\\
\frac{1}{2}\|\sum_{n=1}^{N}\rho_{n}(\nabla
f_{n}(\boldsymbol{\bar{\omega}}^{\prime(t)})-\nabla
f_{n}(\boldsymbol{\omega}_{n}^{\prime(t)}))\|^{2}\\\
\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny{\small\smallb⃝}}}}{\leq}}-\frac{1}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}-\frac{1}{2}\|\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}\|^{2}+\\\
\frac{L^{2}}{2}\sum_{n=1}^{N}\rho_{n}\|(\boldsymbol{\bar{\omega}}^{\prime(t)}-\boldsymbol{\omega}_{n}^{\prime(t)})\|^{2},$
(36)

where the condition ⓐ is satisfied due to the relation
$ab=\frac{a^{2}+b^{2}-(a-b)^{2}}{2}$, while condition ⓑ is satisfied by virtue
of Assumption 1. Our approach to the proof utilizes a similar structure to the
one found in the reference [38], owing to the fact that the global mask
$\mbox{m}_{t}$ remains consistent throughout the local training process. The
specifics of this proof methodology are explicated as follows. Let
$t_{c}=[\frac{t}{E_{l}}]E_{l}$ be the start time of local training. Then
$\boldsymbol{\bar{\omega}}^{\prime(t)}$ and
$\boldsymbol{\omega}_{n}^{\prime(t)}$ can be written as

$\boldsymbol{\bar{\omega}}^{\prime(t)}=(\boldsymbol{\bar{\omega}}^{\prime(t_{c})}-\frac{1}{K}\sum_{n\in
P_{t}}\sum_{k=t_{c}+1}^{t-1}\eta_{k}\tilde{\mathbf{v}}_{n}^{\prime(k)})\odot\mbox{m}_{t},$
(37)
$\boldsymbol{\omega}^{\prime(t)}_{n}=(\boldsymbol{\bar{\omega}}^{\prime(t_{c})}-\sum_{k=t_{c}+1}^{t-1}\eta_{k}\tilde{\mathbf{v}}_{n}^{\prime(k)})\odot\mbox{m}_{t}.$
(38)

According to Lemma 1, Assumption 3, Definition 2 and Eq. $(50)-(54)$ in [38],
while taking expectation of $P_{t}$, we can obtain

$\sum_{n=1}^{N}\rho_{n}\|(\boldsymbol{\bar{\omega}}^{\prime(t)}-\boldsymbol{\omega}_{n}^{\prime(t)})\|^{2}\\\
\leq(\gamma-1)[\frac{1}{K}\sum_{n=1}^{N}\sum_{k=t_{c}+1}^{t-1}\eta_{k}^{2}\rho_{n}\sigma^{2}_{n}+\gamma
E_{l}\sum_{k=t_{c}+1}^{t-1}\eta_{k}^{2}\|\sum_{n=1}^{N}\rho_{n}\mathbf{v}_{n}^{\prime(k)}\|^{2}].$
(39)

Consider decreasing learning rate $\eta_{k}^{2}\leq\eta_{t}$ with
$t_{c}+1<k<t$ and substitute Eq. (39) into (36), we have

$-\mathbb{E}[\langle\tilde{\mathbf{v}}^{\prime(t)},\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\rangle]\leq\frac{(\gamma-1)L^{2}\eta_{t}}{2K}\sum_{n=1}^{N}\rho_{n}\sigma^{2}_{n}+\\\
\frac{(\gamma-1)\gamma
E_{l}\eta_{t}L^{2}}{2}\sum_{k=t_{c}+1}^{t_{c}+E_{l}}\|\sum_{n=1}^{N}\rho_{n}\mathbf{v}_{n}^{\prime(k)}\|^{2}-\frac{1}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}\\\
-\frac{1}{2}\|\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}\|^{2}.$
(40)

Substituting (35) and (40) into (31) finishes the proof. ∎

Proof of Theorem $1$:

###### Proof.

Recall (26), we sum up the theoretical results of Lemma 2 and 3.

$\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t+1)})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t)})]\leq\frac{(\gamma-1)L^{2}\eta_{t}^{2}+\eta_{t}^{2}L}{2K}\sum_{n=1}^{N}\rho_{n}\sigma^{2}_{n}+\\\
\frac{(\gamma-1)\gamma
E_{l}\eta_{t}^{2}L^{2}}{2}\sum_{k=t_{c}+1}^{t_{c}+E_{l}}\|\sum_{n=1}^{N}\rho_{n}\mathbf{v}_{n}^{\prime(k)}\|^{2}-\frac{\eta_{t}}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}+\\\
\frac{\gamma\eta_{t}^{2}L-\eta_{t}}{2}\|\sum_{n=1}^{N}\rho_{n}\tilde{\mathbf{v}}_{n}^{\prime(t)}\|^{2}+\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|].$
(41)

While $\eta_{t}\leq\frac{1}{tL}$ and Assumption 4, Equation (41) can be
expressed as:

$\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t+1)})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t)})]\leq\frac{(\gamma-1)L^{2}\eta_{t}^{2}+\eta_{t}^{2}L}{2K}\sum_{n=1}^{N}\rho_{n}\sigma^{2}_{n}+\\\
\frac{(\gamma-1)\gamma
E_{l}^{2}\eta_{t}^{2}L^{2}G^{2}}{2}+\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|.$
(42)

Denote
$\chi=\frac{(\gamma-1)L^{2}+L}{2K}\sum_{n=1}^{N}\rho_{n}\sigma^{2}_{n}+\frac{(\gamma-1)\gamma
E_{l}^{2}L^{2}G^{2}}{2}$, (42) is written as

$\frac{\eta_{t}}{2}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}\leq\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t)})]-\mathbb{E}[f(\boldsymbol{\bar{\omega}}^{\prime(t+1)})]\\\
+\chi\eta_{t}^{2}+\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|.$
(43)

After taking the average of (43) over time $T$, we have the results as follows
after rearranging. Note that we assume that the model will converge to a
stable point regarded as the optimum $f^{*}$.

$\frac{1}{T}\sum_{t=1}^{T}\frac{1}{tL}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}\leq\frac{1}{T}\mathbb{E}(f(\boldsymbol{\omega}_{1})-f^{*})+\\\
\frac{2}{T}\sum_{t=1}^{T}[\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|+\chi\eta_{t}^{2}].$
(44)

Since $\frac{1}{T}\sum_{t=1}^{T}\frac{1}{T}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}\leq\frac{1}{T}\sum_{t=1}^{T}\frac{1}{t}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}$, (44) can be expressed as

$\frac{1}{T}\sum_{t=1}^{T}\|\nabla
f(\boldsymbol{\bar{\omega}}^{\prime(t)})\|^{2}\leq
2L\mathbb{E}(f(\boldsymbol{\omega}_{1})-f^{*})+\\\
2L\sum_{t=1}^{T}[\mu\mathbb{E}[\sqrt{\delta_{t+1}}\|\boldsymbol{\bar{\omega}}^{t+1}\|]+\frac{\pi^{2}}{3L^{2}}\chi,$
(45)

where it is known that $\sum_{t=1}^{T}\frac{1}{t^{2}}=\frac{\pi^{2}}{6}$. ∎