# FedP3: Federated Personalized and Privacy-friendly Network Pruning under
Model Heterogeneity

Kai Yi1 , Nidham Gazagnadou2, Peter Richtárik1, Lingjuan Lyu2
1KAUST, 2Sony AI
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Work done during an
internship at Sony AI.

###### Abstract

The interest in federated learning has surged in recent research due to its
unique ability to train a global model using privacy-secured information held
locally on each client. This paper pays particular attention to the issue of
client-side model heterogeneity, a pervasive challenge in the practical
implementation of FL that escalates its complexity. Assuming a scenario where
each client possesses varied memory storage, processing capabilities and
network bandwidth - a phenomenon referred to as system heterogeneity - there
is a pressing need to customize a unique model for each client. In response to
this, we present an effective and adaptable federated framework FedP3,
representing Federated Personalized and Privacy-friendly network Pruning,
tailored for model heterogeneity scenarios. Our proposed methodology can
incorporate and adapt well-established techniques to its specific instances.
We offer a theoretical interpretation of FedP3 and its locally differential-
private variant, DP-FedP3, and theoretically validate their efficiencies.

##  1 Introduction

Federated learning (FL) (McMahan et al., 2017; Konečnỳ et al., 2016) has
emerged as a significant machine learning paradigm wherein multiple clients
perform computations on their private data locally and subsequently
communicate their findings to a remote server. Standard FL can be articulated
as an optimization problem, specifically the Empirical Risk Minimization (ERM)
given by

$\min_{W\in\mathbb{R}^{d}}f(W)\coloneqq\frac{1}{n}\sum_{i=1}^{n}f_{i}(W)\enspace,$
(1)

where $W$ represents the shared global network parameters, $f_{i}$ denotes the
local objective for client $i$, and $n$ is the total number of clients.

Distinguishing it from conventional distributed learning, FL predominantly
addresses heterogeneity stemming from both data and model aspects. Data
heterogeneity characterizes the fact that the local data distribution across
clients can vary widely. Such variation is rooted in real-world scenarios
where clients or users exhibit marked differences in their data, reflective of
the variety of sensors or software Jiang et al. (2020), of users’ unique
preferences, etc. Li et al. (2020a). Recent works Zhao et al. (2018) showed
how detrimental the non-iidness of the local data could be on the training of
a FL model. This phenomenon known as client-drift, is intensively studied to
develop methods limiting its impact on the performance (Karimireddy et al.,
2020; Gao et al., 2022b; Mendieta et al., 2022).

Furthermore, given disparities among clients in device resources, e.g., energy
consumption, computational capacities, memory storage or network bandwidths,
model heterogeneity becomes a pivotal consideration. To avoid restricting the
global model’s architecture to the largest that is compatible with all
clients, recent methods aim at reducing its size differently for each client
to extract the utmost of their capacities. This can be referred to as
constraint-based local model personalization (Gao et al., 2022a). In such a
context, clients often train a pruned version of the global model (Jiang et
al., 2022b; Diao et al., 2021) before transmitting it to the server for
aggregation (Li et al., 2021). A contemporary and influential offshoot of this
is Independent Subnetwork Training (IST) (Yuan et al., 2022). It hinges on the
concept that each client trains a subset of the main server-side model,
subsequently forwarding the pruned model to the server. Such an approach
significantly trims local computational burdens in FL (Dun et al., 2023).

Our research, while aligning with the IST premise, brings to light some key
distinctions. A significant observation from our study is the potential
privacy implications of continuously sending the complete model back to the
server. Presently, even pruned networks tend to preserve the overarching
structure of the global model. In this paper, we present an innovative
approach to privacy-friendly pruning. Our method involves transmitting only
select segments of the global model back to the server. This technique
effectively conceals the true structure of the global model, thus achieving a
delicate balance between utility and confidentiality. As highlighted in Zeiler
& Fergus (2014), different layers within networks demonstrate varied
capacities for representation and semantic interpretation. The challenge of
securely transferring knowledge from client to server, particularly amidst
notable model heterogeneity, is an area that has not been thoroughly explored.
It’s pertinent to acknowledge that the concept of gradient pruning as a means
of preserving privacy was initially popularized by the foundational work of
Zhu et al. (2019). Following this, studies such as Huang et al. (2020) have
further investigated the efficacy of DNN pruning in maintaining privacy.

Besides, large language models (LLMs) have garnered significant attention and
have been applied to a plethora of real-world scenarios (Brown et al., 2020;
Chowdhery et al., 2022; Touvron et al., 2023) recently. However, the parameter
count of modern LLMs often reaches the billion scale, making it challenging to
utilize user or client information and communicate within a FL framework. We
aim to explore the feasibility of training a more compact local model and
transmitting only a subset of the global network parameters to the server,
while still achieving commendable performance.

From a formulation standpoint, our goal is to optimize the following
objective, thereby crafting a global model under conditions of model
heterogeneity:

$\min_{W_{1},\dotsc,W_{n}\in\mathbb{R}^{d}}f(W)\coloneqq
h\left(f_{1}(W_{1}),f_{2}(W_{2}),\dotsc,f_{n}(W_{n})\right)\enspace,$ (2)

where $W_{i}$ denotes the model downloaded from client $i$ to the server,
which can differ as we allow global pruning or other sparsification
strategies. The global model $W$ is a function of
$\\{W_{1},W_{2},\dotsc,W_{n}\\}$, $f_{i}$ the local objective for client $i$
and $n$ the total number of clients. Function $h$ is the aggregation mapping
from the clients to the server. In conventional FL, it’s assumed that function
$h$ is the average and all $W_{1}=\dotsc W_{n}=W$, which means the full global
model is downloaded from the server to every client. When maintaining a global
model $W$, this gives us $f(x)\coloneqq\frac{1}{n}\sum_{i=1}^{n}f_{i}(W)$,
which aligns with the standard empirical risk minimization (ERM).

In this paper, we introduce an efficient and adaptable federated network
pruning framework tailored to address model heterogeneity. The main
contributions of our framework, denoted as FedP3 (Federated Personalized and
Privacy-friendly network Pruning) algorithm, are:

  * •

Versatile Framework: Our framework allows personalization based on each
client’s unique constraints (computational, memory, and communication).

  * •

Dual-Pruning Method: Incorporates both global (server to client) and local
(client-specific) pruning strategies for enhanced efficiency.

  * •

Privacy-Friendly Approach: Ensures privacy-friendly to each client by limiting
the data shared with the server to only select layers post-local training.

  * •

Managing Heterogeneity: Effectively tackles data and model diversity,
supporting non-iid data distributions and various client-model architectures.

  * •

Theoretical Interpretation: Provides a comprehensive analysis of global
pruning and personalized model aggregation. Discusses convergence theories,
communication costs, and the advantages over existing methodologies.

  * •

Local Differential-Privacy Algorithm: Introduces LDP-FedP3, a novel local
differential privacy algorithm. Outlines privacy guarantees, utility, and
communication efficiency.

##  2 Approach

We focus on the training of neural networks within the FL paradigm. Consider a
global model

$W\coloneqq\\{W^{0},W^{1},\dots,W^{L},W^{\mathrm{out}}\\}\enspace,$

where $W^{0}$ represents the weights of the input layer, $W^{\mathrm{out}}$
the weights of the final output layer, and $L$ the number of hidden layers.
Each $W^{l}$, for all $l\in\mathcal{L}\coloneqq\\{0,1,\dots,L\\}$, denotes the
model parameters for layer $l$. We distribute the complete dataset $X$ across
$n$ clients following a specific distribution, which can be non-iid. Each
client then conducts local training on its local data denoted by $X_{i}$.

##### Algorithmic overview.

In Algorithm 1, we introduce the details of our proposed general framework
called Federated Personalized and Privacy-friendly network Pruning (FedP3).
For every client $i\in[n]$, we assign predefined pruning mechanisms $P_{i}$
and $Q_{i}$, determined by the client’s computational capacity and network
bandwidth (see Line 2). Here, $P_{i}$ denotes the maximum capacity of a pruned
global model $W$ sent to client $i$, signifying server-client global pruning.
On the other hand, $Q_{i}$ stands for the local pruning mechanism, enhancing
both the speed of local computation and the robustness (allowing more
dynamics) of local network training.

Algorithm 1 FedP3

1: Input: Client $i$ has data $X_{i}$ for $i\in[n]$, the number of local
updates $K$, the number of communication rounds $T$, initial model weights
$W_{t}=\\{W_{t}^{0},W_{t}^{1},\ldots,W_{t}^{L}\\}$ on the server for $t=0$

2: Server specifies the server pruning mechanism $P_{i}$, the client pruning
mechanism $Q_{i}$, and the set of layers to train $L_{i}\subseteq[L]$ for each
client $i\in[n]$

3: for $t=0,1,\dotsc,T-1$ do

4: Server samples a subset of participating clients $\mathcal{C}_{t}\
\subset[n]$

5: Server sends the layer weights $W_{t}^{l}$ for $l\in L_{i}$ to client
$i\in\mathcal{C}_{t}$ for training

6: Server sends the pruned weights $P_{i}\odot W_{t}^{l}$ for $l\notin L_{i}$
to client $i\in\mathcal{C}_{t}$

7: for each client $i\in\mathcal{C}_{t}$ in parallel do

8: Initialize $W_{t,0}^{l}=W_{t}^{l}$ for all $l\in[L_{i}]$ and
$W_{t,0}^{l}=P_{i}\odot W_{t}^{l}$ for all $l\notin[L_{i}]$

9: for $k=0,1,\dotsc,K-1$ do

10: Compute
$W_{t,k+1}\leftarrow\texttt{LocalUpdate}(W_{t,k},X_{i},L_{i},Q_{i},k)$, where
$W_{t,k}\coloneqq\\{W_{t,k}^{0},W_{t,k}^{1},\ldots,W_{t,k}^{L}\\}$

11: end for

12: Send $\cup_{l\in L_{i}}W_{t,K}^{l}$ to the server

13: end for

14: Server aggregates $W_{t+1}=\texttt{Aggregation}(\cup_{i\in[n]}\cup_{l\in
L_{i}}W_{t,K}^{l})$

15: end for

16: Output: $W_{T}$

In Line 4, we opt for partial client participation by selecting a subset of
clients $\mathcal{C}_{t}$ from the total pool $[n]$. Unlike the independent
subnetwork training approach, Lines 5–6 employ a personalized server-client
pruning strategy. This aligns with the concept of collaborative training.
Under this approach, we envision each client learning a subset of layers,
sticking to smaller neural network architectures of the global model. Due to
the efficient and privacy-friendly communication, such a method is not only
practical but also paves a promising path for future research in FL-type
training and large language models.

The server chooses a layer subset $L_{i}$ for client $i$ and dispatches the
pruned weights, conditioned by $P_{i}$, for the remaining layers. Local
training spans $K$ steps (Lines 8–12), detailed in Algorithm 2. To uphold a
privacy-friendly framework, only weights $\cup_{l\in L_{i}}W^{l}_{t,K}$
necessary for training of each client $i$ are transmitted to the server (Line
12). The server concludes by aggregating the weights received from every
client to forge the updated model $W_{t+1}$, as described in Algorithm 3. We
also provide an intuitive pipeline in Figure 1.

Figure 1: Pipeline illustration of our proposed framework FedP3.

##### Local update.

Our proposed framework, FedP3, incorporates dynamic network pruning. In
addition to personalized task assignments for each client $i$, our local
update mechanism supports diverse pruning strategies. Although efficient
pruning strategies in FL remain an active research area (Horváth et al., 2021;
Alam et al., 2022; Liao et al., 2023), we aim to determine if our framework
can accommodate various strategies and yield significant insights. In this
context, we examine different local update rules as described in Algorithm 2.
We evaluate three distinct strategies: fixed without pruning, uniform pruning,
and uniform ordered dropout.

Assuming our current focus is on $W^{l}_{t,k}$, where $l\notin L_{i}$, after
procuring the pruned model conditioned on $P_{i}$ from the server, we denote
the sparse model we obtain by $P_{i}\odot W^{l}_{t,0}$. Here:

  * •

Fixed without pruning implies that we conduct multiple steps of the local
update without additional local pruning, resulting in $P_{i}\odot
W^{l}_{t,K}$.

  * •

Uniform pruning dictates that for every local iteration $k$, we randomly
generate the probability $q_{i,k}$ and train the model $q_{i,k}\odot
P_{i}\odot W^{l}_{t,K}$.

  * •

Uniform ordered dropout is inspired by Horváth et al. (2021). In essence, if
$P_{i}\odot W^{l}_{t,0}\in\mathbb{R}^{d_{1}\times d_{2}}$ (extendable to 4D
convolutional weights; however, we reference 2D fully connected layer weights
here), we retain only the subset $P_{i}\odot
W^{l}_{t,0}[:q_{i,k}d_{1},:q_{i,k}d_{2}]$ for training purposes.
$[:q_{i,k}d_{1}]$ represents we select the first $q_{i,k}\times d_{1}$
elements from the total $d_{1}$ elements.

Regardless of the chosen method, the locally deployed model is given by
$\left(\cup_{l\in L_{i}}W_{t,k}^{l}\right)\cup\left(\cup_{l\not\in
L_{i}}q_{i,k}\odot P_{i}\odot W_{t,k}^{l}\right)$, as highlighted in Algorithm
2 Line 3.

Algorithm 2 LocalUpdate

1: Input: $W_{t,k},X_{i},L_{i},Q_{i},k$

2: Generate the step-wise local pruning ratio $q_{i,k}$ conditioned on $P_{i}$
and $Q_{i}$

3: Local training $\left(\cup_{l\in
L_{i}}W_{t,k}^{l}\right)\cup\left(\cup_{l\not\in L_{i}}q_{i,k}\odot P_{i}\odot
W_{t}^{l}\right)$ using local data $X_{i}$

4: Output: $W_{t,k+1}$

##### Layer-wise aggregation.

Our Algorithm 1 distinctively deviates from existing methods in Line 12 as
each client forwards only a portion of information to the server, thus
prompting an investigation into optimal aggregation techniques. In Algorithm 3
we evaluate three aggregation methodologies:

  * •

Simple averaging computes the mean of all client contributions that include a
specific layer $l$. This option is presented in Line 3.

  * •

Weighted averaging adopts a weighting scheme based on the number of layers
client $i$ is designated to train. Specifically, the weight for aggregating
$W_{t,K,i}^{l}$ from client $i$ is given by $|L_{i}|/\sum_{j=1}^{n}|L_{j}|$,
analogous to importance sampling. This option is presented in Line 5

  * •

Attention-based averaging introduces an adaptive mechanism where an attention
layer is learned specifically for layer-wise aggregation. This option is
presented in Line 9.

Algorithm 3 Aggregation

1: Input: $\cup_{i\in[n]}\cup_{l\in L_{i}}W_{t,K}^{l}$

2: Simple Averaging:

3: $W_{t+1}^{l}\leftarrow\texttt{Avg}\left(W_{t,K,i}^{l}\right)$ for all nodes
with $l\in L_{i}$

4: Weighted Averaging:

5: Construct the aggregation weighting $\alpha_{i}$ for each client $i$

6: $W_{t+1}^{l}\leftarrow\texttt{Avg}\left(\alpha_{i}W_{t,K,i}^{l}\right)$ for
all nodes with $l\in L_{i}$

7: Attention Averaging:

8: Construct an attention mapping layer annoted by function $h$

9: $W_{t+1}^{l}\leftarrow h\left(W_{t,K,i}^{l}\right)$ for all nodes with
$l\in L_{i}$

10: Output: $W_{t+1}$

##  3 Theoretical Analysis

Our work refines independent subnetwork training (IST) by adding
personalization and layer-level sampling, areas yet to be fully explored (see
Appendix A.2 for related work). Drawing on the sketch-based analysis from
Shulgin & Richtárik (2023), we aim to thoroughly analyze FedP3, enhancing the
sketch-type design concept in both scope and depth.

Consider a global model denoted as $w\in\mathbb{R}^{d}$. In Shulgin &
Richtárik (2023), a sketch $\mathcal{C}_{i}^{k}\in\mathbb{R}^{d\times d}$
represents submodel computations by weights permutations. We extend this idea
to a more general case encompassing both global pruning, denoted as
$\mathbf{P}\in\mathbb{R}^{d\times d}$, and personalized model aggregations,
denoted as $\mathbf{S}\in\mathbb{R}^{d\times d}$. Now we first present the
formal definitions.

######  Definition 1 (Global Pruning Sketch $\mathbf{P}$).

Let a random subset $\mathcal{S}$ of $[d]$ is a proper sampling such that the
probability $c_{j}\coloneqq\mathrm{Prob}(j\in S)>0$ for all $j\in[d]$. Then
the biased diagonal sketch with $\mathcal{S}$ is
$\mathbf{P}\coloneqq\mathrm{Diag}(p^{1}_{s},p^{2}_{s},\cdots,p^{d}_{s})$,
where $p^{j}_{s}=1$ if $j\in S$ otherwise $0$.

Unlike Shulgin & Richtárik (2023), we assume client-specific sampling with
potential weight overlap. For simplicity, we consider all layers pruned from
the server to the client, a more challenging case than the partial pruning in
FedP3 (Algorithm 1). The convergence analysis of this global pruning sketch is
in Appendix C.4.

######  Definition 2 (Personalized Model Aggregation Sketch $\mathbf{S}$).

Assume $d\geq n$, $d=sn$, where $s\geq 1$ is an integer. Let
$\pi=(\pi_{1},\cdots,\pi_{d})$ be a random permutation of the set $[d]$. The
number of parameters per layer $n_{l}$, assume $s$ can be divided by $n_{l}$.
Then, for all $x\in\mathbb{R}^{d}$ and each $i\in[n]$, we define $\mathbf{S}$
as $\mathbf{S}\coloneqq n\sum^{si}_{j=s(i-1)+1}e_{\pi_{j}}e^{\top}_{\pi_{j}}$.

Sketch $\mathbf{S}$ is based on the permutation compressor technique from
Szlendak et al. (2021). Extending this idea to scenarios where $d$ is not
divisible by $n$ follows a similar approach as outlined in Szlendak et al.
(2021). To facilitate analysis, we apply a uniform parameter count $n_{l}$
across layers, preserving layer heterogeneity. For layers with fewer
parameters than $d_{L}$, zero-padding ensures operational consistency. This
uniform distribution assumption maintains our findings’ generality and
simplifies the discussion. Our method assumes $s$ divides $d_{l}$,
streamlining layer selection over individual elements. The variable $v$
denotes the number of layers chosen per client, shaping a more analytically
conducive framework for FedP3, detailed in Algorithm 4 in the Appendix.

######  Theorem 1 (Personalized Model Aggregation).

Let Assumption 1 holds. Iterations $K$, choose stepsize
$\gamma\leq\left\\{\nicefrac{{1}}{{L_{\max}}},\nicefrac{{1}}{{\sqrt{\hat{L}L_{\max}K}}}\right\\}$.
Denote $\Delta_{0}\coloneqq f(w^{0})-f^{\inf}$. Then for any $K\geq 1$, the
iterates ${w^{k}}$ of FedP3 in Algorithm 4 satisfy

$\displaystyle\min_{0\leq k\leq K-1}\mathbb{E}\\!\left[\left\|\nabla
f(w^{k})\right\|^{2}\right]\leq\frac{2(1+\bar{L}L_{\max}\gamma^{2})^{K}}{\gamma
K}\Delta_{0}.$ (3)

We have achieved a total communication cost of
$\mathcal{O}\left(\nicefrac{{d}}{{\epsilon^{2}}}\right)$, marking a
significant improvement over unpruned methods. This enhancement is
particularly crucial in FL for scalable deployments, especially with a large
number of clients. Our approach demonstrates a reduction in communication
costs by a factor of $\mathcal{O}\left(\nicefrac{{n}}{{\epsilon}}\right)$. In
the deterministic setting of unpruned methods, we compute the exact gradient,
in contrast to bounding the gradient as in Lemma 1. Remarkably, by applying
the smoothness-based bound condition (Lemma 1) to both FedP3 and the unpruned
method, we achieve a communication cost reduction by a factor of
$\mathcal{O}(\nicefrac{{d}}{{n}})$ for free. This indicates that identifying a
tighter upper gradient bound could potentially lead to even more substantial
theoretical improvements in communication efficiency. A detailed analysis is
available in Appendix C.2. We have also presented an analysis of the locally
differential-private variant of FedP3, termed LDP-FedP3, in Theorem 2.

######  Theorem 2 (LDP-FedP3).

Under Assumptions 1 and 2, with the use of Algorithm 5, consider the number of
samples per client to be $m$ and the number of steps to be $K$. Let the local
sampling probability be $q\equiv b/m$. For constants $c^{\prime}$ and $c$, and
for any $\epsilon<c^{\prime}q^{2}K$ and $\delta\in(0,1)$, LDP-FedP3 achieves
$(\epsilon,\delta)$-LDP with
$\sigma^{2}=\frac{cKC^{2}\log(1/\epsilon)}{m^{2}\epsilon^{2}}$.

Set
$K=\max\Big{\\{}\frac{m\epsilon\sqrt{L\Delta_{0}}}{C\sqrt{cd\log(1/\delta)}},\frac{m^{2}\epsilon^{2}}{cd\log(1/\delta)}\Big{\\}}$
and
$\gamma=\min\Big{\\{}\frac{1}{L},\frac{\sqrt{\Delta_{0}cd\log(1/\delta)}}{Cm\epsilon\sqrt{L}}\Big{\\}}$,
we have:

$\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\\!\left[{\left\lVert\nabla
f(w^{t})\right\rVert}^{2}\right]\leq\frac{2C\sqrt{Lcd\log(1/\sigma)}}{m\epsilon}=\mathcal{O}\left(\frac{C\sqrt{Ld\log(1/\delta)}}{m\epsilon}\right).$

Consequently, the total communication cost is:

$C_{\mathrm{LDP-
FedP3}}=\mathcal{O}\left(\frac{m\epsilon\sqrt{dL\Delta_{0}}}{C\sqrt{\log(1/\delta)}}+\frac{m^{2}\epsilon^{2}}{\log(1/\delta)}\right).$

We establish the privacy guarantee and communication cost of LDP-FedP3. Our
analysis aligns with the communication complexity in Li et al. (2022) while
providing a more precise convergence bound. Further details and comparisons
with existing work are discussed in Appendix C.3.

##  4 Experiments

###  4.1 Datasets and Splitting Techniques

We utilize benchmark datasets CIFAR10/100 Krizhevsky et al. (2009), a subset
of EMNIST labeled EMNIST-L Cohen et al. (2017), and FashionMNIST Xiao et al.
(2017), maintaining standard train/test splits as in McMahan et al. (2017) and
Li et al. (2020b). While CIFAR100 has 100 labels, the others have 10, with a
consistent data split of 70% for training and 30% for testing. Details on
these splits are in Table 3 in the Appendix. For non-iid splits in these
datasets, we employ class-wise and Dirichlet non-iid strategies, detailed in
Appendix B.2.

###  4.2 Optimal Layer Overlapping Among Clients

##### Datasets and Models Specifications.

In this section, our objective is to develop a communication-efficient
architecture that also preserves accuracy. We conducted extensive experiments
on recognized datasets like CIFAR10/100 and FashionMNIST, using a neural
network with two convolutional layers (denoted as Conv) and four fully-
connected layers (FC). For EMNIST-L, our model includes four FC layers
including the output layer. This approach simplifies the identification of
optimal layer overlaps among clients. We provide the details of network
architectures in Appendix B.3.

##### Layer Overlapping Analysis.

Figure 2 presents a comparison of different layer overlapping strategies. For
Optional Pruning Uniformly with selection of 2 layers (OPU2) represents the
selection of two uniformly chosen layers from the entire network for training,
while OPU3 involves 3 such layers. LowerB denotes the scenario where only one
layer’s parameters are trained per client, serving as a potential lower bound
benchmark. All clients participate in training the final FC layer (denoted as
FFC). “S1” and “S2” signify class-wise and Dirichlet data distributions,
respectively. For example, FedAvg-S1 shows the performance of FedAvg under a
class-wise non-iid setting. Given that a few layers are randomly assigned for
each client to train, we assess the communication cost on average. In
CIFAR10/100 and FashionMNIST training, by design, we obtain a 20%
communication reduction for OPU3, 40% for OPU2, and 60% for LowerB.
Remarkably, OPU3 shows comparable performance to FedAvg, with only 80% of the
parameters communicated. Computational results in the Appendix B.5 (Figure 6)
elucidate the outcomes of randomly sampling a single layer (LowerB).
Particularly in CIFAR10, clients training on FC2+FFC layers face communication
costs more than 10,815 times higher than those training on Conv1+FFC layers,
indicating significant model heterogeneity.

Figure 2:  Comparative Analysis of Layer Overlap Strategies: The left figure
presents a comparative study of different overlapping layer configurations
across four major datasets. On the right, we extend this comparison to include
the state-of-the-art personalized FL method, FedCR. In this context, S1 refers
to a class-wise non-iid distribution, while S2 indicates a Dirichlet non-iid
distribution.

Beyond validating FedAvg, we compare with the state-of-the-art personalized FL
method FedCR Zhang et al. (2023) (details in Appendix B.4), as shown on the
right of Figure 2. Our method (FedCR-OPU3), despite 20% lower communication
costs, achieves promising performance with only a 2.56% drop on S1 and a 3.20%
drop on S2 across four datasets. Additionally, Figure 2 highlights the
performance differences between the two non-iid data distribution strategies,
S1 and S2. The average performance gap across LowerB, OPU2, and OPU3 is 3.55%.
This minimal reduction in performance across all datasets underscores the
robustness and stability of our FedP3 pruning strategy in diverse data
distributions within FL.

##### Larger Network Verifications.

Our assessment extends beyond shallow networks to the more complex ResNet18
model He et al. (2016), tested with CIFAR10 and CIFAR100 datasets. Figure 3
illustrates the ResNet18 architecture, composed of four blocks, each
containing four layers with skip connections, plus an input and an output
layer, totaling 18 layers. A key focus of our study is to evaluate the
efficiency of training this heterogeneous model using only a partial set of
its layers. We performed layer ablations in blocks 2 and 3 (B2 and B3), as
shown in Figure 1. The notation -B2-B3(full) indicates complete random pruning
of B2 or B3, with the remaining structure sent to the server. -B2(part) refers
to pruning the first or last two layers in B2. We default the global pruning
ratio from server to client at 0.9, implying that the locally deployed model
is approximately 10% smaller than the global model. Results in Figure 1
demonstrate that dropping random layers from ResNet18 does not significantly
impact performance, sometimes even enhancing it. Compared with Full, -B2(part)
and -B3(part) achieved a 6.25% reduction in communication costs with only a
1.03% average decrease in performance. Compared to the standard FedAvg without
pruning, this is a 16.63% reduction, showcasing the efficiency of our FedP3
method. Remarkably, -B3(part) even surpassed the Full model in performance.
Additionally, -B2-B3(full) resulted in a 12.5% average reduction in
communication costs (21.25% less compared to unpruned FedAvg), with just a
6.32% performance drop on CIFAR10 and CIFAR100. These results demonstrate the
potential of FedP3 for effective learning in LLMs.

Figure 3: ResNet18 architecture.

Method | CIFAR10 | CIFAR100
---|---|---
Full | 73.25 | 63.33
-B2-B3 (full) | 65.68 | 58.26
-B2 (part) | 72.09 | 61.11
-B3 (part) | 73.47 | 62.39

Table 1: Performance of ResNet18 under class-wise non-iid conditions. The
global pruning ratio from server to client is maintained at 0.9 for all
baseline comparisons by default.

Figure 4:  Comparative Analysis of Server to Client Global Pruning Strategies:
The left portion displays Top-1 accuracy across four major datasets and two
distinct non-IID distributions, varying with different global pruning rates.
On the right, we quantitatively assess the trade-off between model size and
accuracy.

###  4.3 Key Ablation Studies

Our framework, detailed in Algorithm 1, critically depends on the choice of
pruning strategies. The FedP3 algorithm integrates both server-to-client
global pruning and client-specific local pruning. Global pruning aims to
minimize the size of the model deployed locally, while local pruning focuses
on efficient training and enhanced robustness.

####  4.3.1 Exploring Server to Client Global Pruning Strategies

We investigate various global pruning ratios and their impacts, as shown in
the left part of Figure 4. A global pruning rate of 0.9 implies the local
model has 10% fewer parameters than the global model. When comparing unpruned
(rate 1.0) scenarios, we note an average performance drop of 5.32% when
reducing the rate to 0.9, 12.86% to 0.7, and a significant 27.76% to 0.5
across four major datasets and two data distributions. The performance decline
is more pronounced at a 0.5 pruning ratio, indicating substantial compromises
in performance for halving the model parameters.

In the right part of Figure 4, we evaluate the trade-off between model size
and accuracy. Assuming the total global model parameters as $N$ and accuracy
as Acc, the global pruning ratio as $r$, we weigh the local model parameters
against accuracy using a factor $\alpha\coloneqq N/\text{Acc}>0$, where the
x-axis represents $\text{Acc}+\alpha/r$. A higher $\alpha$ indicates a focus
on reducing parameter numbers for large global models, accepting some
performance loss. This becomes increasingly advantageous with higher $\alpha$
values, suggesting a promising area for future exploration, especially with
larger-scale models.

####  4.3.2 Exploring Client-Wise Local Pruning Strategies

Next, we are interested in exploring the influence of different local pruning
strategies. Building upon our initial analysis, we investigate scenarios where
our framework permits varying levels of local network pruning ratios.
Noteworthy implementations in this domain resemble FjORD (Horváth et al.,
2021), FedRolex (Alam et al., 2022), and Flado (Liao et al., 2023). Given that
the only partially open-source code available is from FjORD, we employ their
layer-wise approach to network sparsity. The subsequent comparisons and their
outcomes are presented in Table2. The details of different pruning strategies,
including Fixed, Uniform and Ordered Dropout are presented in the above
Approach section. ”Fixed”, ”Uniform”, ”Ordered Dropout” represents Fixed
without pruning, Uniform pruning, and Uniform order dropout in the Approach
section, respectively. From the results in Table. 2, we can see the difference
between Uniform and Ordered Dropout strategies will be smaller with small
global pruning ratio $p$ from 0.9 to 0.7. Besides, in our experiments, Ordered
Dropout is no better than the simple Uniform strategy for local pruning.

Table 2: Comparison of different network local pruning strategies. Global
pruning ratio $p$ is 0.9.

Strategies | CIFAR10 | CIFAR100 | EMNIST-L | FashionMNIST
---|---|---|---|---
Fixed | 67.65 / 61.17 | 65.41 / 57.38 | 88.75 / 86.33 | 81.75 / 84.27
Uniform ($p=0.9$) | 65.51 / 60.10 | 64.33 / 58.20 | 85.14 / 84.29 | 78.81 / 77.24
Ordered Dropout ($p=0.9$) | 61.73 / 58.82 | 61.11 / 53.28 | 82.54 / 80.18 | 75.45 / 73.27
Uniform ($p=0.7$) | 60.78 / 56.41 | 60.35 / 54.88 | 77.39 / 75.82 | 72.66 / 70.37
Ordered Dropout ($p=0.7$) | 58.90 / 53.38 | 59.72 / 50.03 | 72.19 / 70.30 | 70.21 / 67.58

####  4.3.3 Exploring Adaptive Model Aggregation Strategies

In this section, we explore a range of weighting strategies, including both
simple and advanced averaging methods, primarily focusing on the CIFAR10/100
datasets. We assign clients with $1-3$ layers (OPU1-2-3) or $2-3$ layers
(OPU2-3) randomly. In Algorithm 3, we implement two aggregation approaches:
simple and weighted aggregation.

Let $L^{l}$ denote the set of clients involved in training the $l$-th layer,
where $l\in\mathcal{L}$. The server’s received weights for layer $l$ from
client $i$ are represented as $W_{t,K,i}^{l}$. The general form of model
aggregation is thus defined as:

$W_{t+1}^{l}=\sum_{j=1}^{L^{l}}\alpha_{i}W_{t,K,i}^{l}.$

If $\alpha_{i}$ is initialized as $\nicefrac{{1}}{{|L^{l}|}}$, this
constitutes simple mean averaging. Considering $N_{i}$ as the total number of
layers for client $i$ and $n$ as the total number of clients, if
$\alpha_{i}=\nicefrac{{N_{i}}}{{\sum_{j=1}^{n}N_{j}}}$, this method is termed
weighted averaging. The underlying idea is that clients with more
comprehensive network information should have greater weight in parameter
contribution. A more flexible approach is attention averaging, where
$\alpha_{i}$ is learnable, encompassing simple and weighted averaging as
specific cases.

Figure 5:  Comparison of various model aggregation strategies. $p=0.9$.

Future research may delve into a broader range of aggregation strategies. Our
findings, shown in Figure 5, include S123-S1 for the OPU1-2-3 method with
simple aggregation in class-wise non-iid distributions, and W23-S2 for OPU2-3
with weighted aggregation in Dirichlet non-iid. The data illustrates that
weighted averaging relatively improves over simple averaging by 1.01% on
CIFAR10 and 1.05% on CIFAR100. Furthermore, OPU-2-3 consistently surpasses
OPU1-2-3 by 1.89%, empirically validating our hypotheses.

##  5 Conclusion

In this paper, we introduce FedP3, a nuanced solution designed to tackle both
data and model heterogeneities while prioritizing privacy. We have precisely
defined the concepts of personalization, privacy, and pruning as central to
our analysis. The efficacy of each component is rigorously validated through
comprehensive proofs and extensive experimental evaluations.

## References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pp. 308–318, 2016.
  * Alam et al. (2022) Samiul Alam, Luyang Liu, Ming Yan, and Mi Zhang.  Fedrolex: Model-heterogeneous federated learning with rolling sub-model extraction.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Andrés et al. (2013) Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi.  Geo-indistinguishability: Differential privacy for location-based systems.  In _Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security_, pp. 901–914, 2013.
  * Arjevani et al. (2020) Yossi Arjevani, Ohad Shamir, and Nathan Srebro.  A tight convergence analysis for stochastic gradient descent with delayed updates.  In _Algorithmic Learning Theory_ , pp. 111–132. PMLR, 2020.
  * Bassily et al. (2014) Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _2014 IEEE 55th annual symposium on foundations of computer science_ , pp. 464–473. IEEE, 2014.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chatzikokolakis et al. (2013) Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi.  Broadening the scope of differential privacy using metrics.  In _Privacy Enhancing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings 13_ , pp. 82–102. Springer, 2013.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.
  * Cohen et al. (2017) Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik.  Emnist: Extending mnist to handwritten letters.  In _2017 international joint conference on neural networks (IJCNN)_ , pp. 2921–2926. IEEE, 2017.
  * Cunha et al. (2022) Leonardo Cunha, Gauthier Gidel, Fabian Pedregosa, Damien Scieur, and Courtney Paquette.  Only tails matter: Average-case universality and robustness in the convex regime.  In _International Conference on Machine Learning_ , pp. 4474–4491. PMLR, 2022.
  * Diao et al. (2021) Enmao Diao, Jie Ding, and Vahid Tarokh.  Heterofl: Computation and communication efficient federated learning for heterogeneous clients.  In _International Conference on Learning Representations_ , 2021.
  * Ding et al. (2021) Jiahao Ding, Guannan Liang, Jinbo Bi, and Miao Pan.  Differentially private and communication efficient collaborative learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 7219–7227, 2021.
  * Dun et al. (2022) Chen Dun, Cameron R Wolfe, Christopher M Jermaine, and Anastasios Kyrillidis.  Resist: Layer-wise decomposition of resnets for distributed training.  In _Uncertainty in Artificial Intelligence_ , pp. 610–620. PMLR, 2022.
  * Dun et al. (2023) Chen Dun, Mirian Hipolito, Chris Jermaine, Dimitrios Dimitriadis, and Anastasios Kyrillidis.  Efficient and light-weight federated learning via asynchronous distributed dropout.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 6630–6660. PMLR, 2023.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3_ , pp. 265–284. Springer, 2006.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Feldman et al. (2020) Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: optimal rates in linear time.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , pp. 439–449, 2020.
  * Gao et al. (2022a) Dashan Gao, Xin Yao, and Qiang Yang.  A survey on heterogeneous federated learning.  _arXiv preprint arXiv:2210.04505_ , 2022a.
  * Gao et al. (2022b) Liang Gao, Huazhu Fu, Li Li, Yingwen Chen, Ming Xu, and Cheng-Zhong Xu.  Feddc: Federated learning with non-iid data via local drift decoupling and correction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 10112–10121, June 2022b.
  * Ghadimi & Lan (2013) Saeed Ghadimi and Guanghui Lan.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  _SIAM Journal on Optimization_ , 23(4):2341–2368, 2013.
  * Goujaud et al. (2022) Baptiste Goujaud, Damien Scieur, Aymeric Dieuleveut, Adrien B Taylor, and Fabian Pedregosa.  Super-acceleration with cyclical step-sizes.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 3028–3065. PMLR, 2022.
  * He et al. (2021) Chaoyang He, Erum Mushtaq, Jie Ding, and Salman Avestimehr.  Fednas: Federated deep learning via neural architecture search.  2021\.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Horváth et al. (2021) Samuel Horváth, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis, Stylianos Venieris, and Nicholas Lane.  Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout.  _Advances in Neural Information Processing Systems_ , 34:12876–12889, 2021.
  * Huang et al. (2022) Hong Huang, Lan Zhang, Chaoyue Sun, Ruogu Fang, Xiaoyong Yuan, and Dapeng Wu.  Fedtiny: Pruned federated learning towards specialized tiny models.  _arXiv preprint arXiv:2212.01977_ , 2022.
  * Huang et al. (2020) Yangsibo Huang, Yushan Su, Sachin Ravi, Zhao Song, Sanjeev Arora, and Kai Li.  Privacy-preserving learning via deep net pruning.  _arXiv preprint arXiv:2003.01876_ , 2020.
  * Iyengar et al. (2019) Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang.  Towards practical differentially private convex optimization.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , pp. 299–316. IEEE, 2019.
  * Jaggi et al. (2014) Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael I Jordan.  Communication-efficient distributed dual coordinate ascent.  _Advances in neural information processing systems_ , 27, 2014.
  * Jiang et al. (2020) Ji Chu Jiang, Burak Kantarci, Sema Oktug, and Tolga Soyata.  Federated learning in smart city sensing: Challenges and opportunities.  _Sensors_ , 20(21):6230, 2020.
  * Jiang et al. (2022a) Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K Leung, and Leandros Tassiulas.  Model pruning enables efficient federated learning on edge devices.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2022a.
  * Jiang et al. (2022b) Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K Leung, and Leandros Tassiulas.  Model pruning enables efficient federated learning on edge devices.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2022b.
  * Kairouz et al. (2021) Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Karimireddy et al. (2020) Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.  Scaffold: Stochastic controlled averaging for federated learning.  In _International conference on machine learning_ , pp. 5132–5143. PMLR, 2020.
  * Khaled & Richtárik (2020) Ahmed Khaled and Peter Richtárik.  Better theory for sgd in the nonconvex world.  _arXiv preprint arXiv:2002.03329_ , 2020.
  * Konečnỳ et al. (2016) Jakub Konečnỳ, H Brendan McMahan, Daniel Ramage, and Peter Richtárik.  Federated optimization: Distributed machine learning for on-device intelligence.  _arXiv preprint arXiv:1610.02527_ , 2016.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Li & Wang (2019) Daliang Li and Junpu Wang.  Fedmd: Heterogenous federated learning via model distillation.  _arXiv preprint arXiv:1910.03581_ , 2019.
  * Li et al. (2021) Qinbin Li, Bingsheng He, and Dawn Song.  Model-contrastive federated learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 10713–10722, 2021.
  * Li et al. (2020a) Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE signal processing magazine_ , 37(3):50–60, 2020a.
  * Li et al. (2020b) Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.  Federated optimization in heterogeneous networks.  _Proceedings of Machine learning and systems_ , 2:429–450, 2020b.
  * Li & Li (2022) Zhize Li and Jian Li.  Simple and optimal stochastic gradient methods for nonsmooth nonconvex optimization.  _The Journal of Machine Learning Research_ , 23(1):10891–10951, 2022.
  * Li et al. (2022) Zhize Li, Haoyu Zhao, Boyue Li, and Yuejie Chi.  Soteriafl: A unified framework for private federated learning with communication compression.  _Advances in Neural Information Processing Systems_ , 35:4285–4300, 2022.
  * Liao et al. (2023) Dongping Liao, Xitong Gao, Yiren Zhao, and Cheng-Zhong Xu.  Adaptive channel sparsity for federated learning under system heterogeneity.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 20432–20441, 2023.
  * Liao & Kyrillidis (2022) Fangshuo Liao and Anastasios Kyrillidis.  On the convergence of shallow neural network training with randomly masked neurons.  _Transactions on Machine Learning Research_ , 2022.
  * Lin et al. (2020) Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi.  Ensemble distillation for robust model fusion in federated learning.  _Advances in Neural Information Processing Systems_ , 33:2351–2363, 2020.
  * Lowy et al. (2023) Andrew Lowy, Ali Ghafelebashi, and Meisam Razaviyayn.  Private non-convex federated learning without a trusted server.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 5749–5786. PMLR, 2023.
  * Ma et al. (2015) Chenxin Ma, Virginia Smith, Martin Jaggi, Michael Jordan, Peter Richtárik, and Martin Takác.  Adding vs. averaging in distributed primal-dual optimization.  In _International Conference on Machine Learning_ , pp. 1973–1982. PMLR, 2015.
  * Malinovsky et al. (2022) Grigory Malinovsky, Kai Yi, and Peter Richtárik.  Variance reduced Proxskip: Algorithm, theory and application to federated learning.  _NeurIPS_ , 2022.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pp. 1273–1282. PMLR, 2017.
  * Mendieta et al. (2022) Matias Mendieta, Taojiannan Yang, Pu Wang, Minwoo Lee, Zhengming Ding, and Chen Chen.  Local learning matters: Rethinking data heterogeneity in federated learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 8397–8406, June 2022.
  * Mishchenko et al. (2022) Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik.  ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally!  In _39th International Conference on Machine Learning (ICML 2022)_ , 2022.
  * Nesterov (2003) Yurii Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer Science & Business Media, 2003.
  * Safaryan et al. (2021) Mher Safaryan, Filip Hanzely, and Peter Richtárik.  Smoothness matrices beat smoothness constants: Better communication compression techniques for distributed optimization.  _Advances in Neural Information Processing Systems_ , 34:25688–25702, 2021.
  * Shulgin & Richtárik (2023) Egor Shulgin and Peter Richtárik.  Towards a better theoretical understanding of independent subnetwork training.  _arXiv preprint arXiv:2306.16484_ , 2023.
  * Smith et al. (2017) Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar.  Federated multi-task learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Szlendak et al. (2021) Rafał Szlendak, Alexander Tyurin, and Peter Richtárik.  Permutation compressors for provably faster distributed nonconvex optimization.  _arXiv preprint arXiv:2110.03300_ , 2021.
  * Tan et al. (2022) Yue Tan, Guodong Long, Lu Liu, Tianyi Zhou, Qinghua Lu, Jing Jiang, and Chengqi Zhang.  Fedproto: Federated prototype learning across heterogeneous clients.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 8432–8440, 2022.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Wang et al. (2022) Bokun Wang, Mher Safaryan, and Peter Richtárik.  Theoretically better and numerically faster distributed optimization with smoothness-aware quantization techniques.  _Advances in Neural Information Processing Systems_ , 35:9841–9852, 2022.
  * Wang et al. (2017) Di Wang, Minwei Ye, and Jinhui Xu.  Differentially private empirical risk minimization revisited: Faster and more general.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Wolfe et al. (2023) Cameron R Wolfe, Jingkang Yang, Fangshuo Liao, Arindam Chowdhury, Chen Dun, Artun Bayer, Santiago Segarra, and Anastasios Kyrillidis.  Gist: Distributed training for large-scale graph convolutional networks.  _Journal of Applied and Computational Topology_ , pp. 1–53, 2023\.
  * Xiao et al. (2017) Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ , 2017.
  * Ye et al. (2023) Mang Ye, Xiuwen Fang, Bo Du, Pong C Yuen, and Dacheng Tao.  Heterogeneous federated learning: State-of-the-art and research challenges.  _ACM Computing Surveys_ , 56(3):1–44, 2023.
  * Yi et al. (2023) Kai Yi, Laurent Condat, and Peter Richtárik.  Explicit personalization and local training: Double communication acceleration in federated learning.  _arXiv preprint arXiv:2305.13170_ , 2023.
  * Yuan et al. (2022) Binhang Yuan, Cameron R Wolfe, Chen Dun, Yuxin Tang, Anastasios Kyrillidis, and Chris Jermaine.  Distributed learning of fully connected neural networks using independent subnet training.  _Proceedings of the VLDB Endowment_ , 15(8):1581–1590, 2022.
  * Zeiler & Fergus (2014) Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part I 13_ , pp. 818–833. Springer, 2014.
  * Zhang et al. (2019) Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George Dahl, Chris Shallue, and Roger B Grosse.  Which algorithmic choices matter at which batch sizes? insights from a noisy quadratic model.  _Advances in neural information processing systems_ , 32, 2019.
  * Zhang et al. (2023) Hao Zhang, Chenglin Li, Wenrui Dai, Junni Zou, and Hongkai Xiong.  Fedcr: Personalized federated learning based on across-client common representation with conditional mutual information regularization.  2023\.
  * Zhang et al. (2020) Xin Zhang, Minghong Fang, Jia Liu, and Zhengyuan Zhu.  Private and communication-efficient edge learning: a sparse differential gaussian-masking distributed sgd approach.  In _Proceedings of the Twenty-First International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ , pp. 261–270, 2020.
  * Zhao et al. (2020) Yang Zhao, Jun Zhao, Mengmeng Yang, Teng Wang, Ning Wang, Lingjuan Lyu, Dusit Niyato, and Kwok-Yan Lam.  Local differential privacy-based federated learning for internet of things.  _IEEE Internet of Things Journal_ , 8(11):8836–8853, 2020.
  * Zhao et al. (2018) Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra.  Federated learning with non-iid data.  _arXiv preprint arXiv:1806.00582_ , 2018.
  * Zhu et al. (2022) Libin Zhu, Chaoyue Liu, Adityanarayanan Radhakrishnan, and Mikhail Belkin.  Quadratic models for understanding neural network dynamics.  _arXiv preprint arXiv:2205.11787_ , 2022.
  * Zhu et al. (2019) Ligeng Zhu, Zhijian Liu, and Song Han.  Deep leakage from gradients.  _Advances in neural information processing systems_ , 32, 2019.

###### Contents

  1. 1 Introduction
  2. 2 Approach
  3. 3 Theoretical Analysis
  4. 4 Experiments
    1. 4.1 Datasets and Splitting Techniques
    2. 4.2 Optimal Layer Overlapping Among Clients
    3. 4.3 Key Ablation Studies
      1. 4.3.1 Exploring Server to Client Global Pruning Strategies
      2. 4.3.2 Exploring Client-Wise Local Pruning Strategies
      3. 4.3.3 Exploring Adaptive Model Aggregation Strategies
  5. 5 Conclusion
  6. A Extended Related Work
    1. A.1 Federated Network Pruning
    2. A.2 Subnetwork Training
    3. A.3 Model Heterogeneity
  7. B Experimental Details
    1. B.1 Statistics of Datasets
    2. B.2 Data Distributions
    3. B.3 Network Architectures
    4. B.4 Training Details
    5. B.5 Quantitative Analysis of Reduced Parameters
  8. C Extended Theoretical Analysis
    1. C.1 Analysis of the General FedP3 Theoretical Framework
    2. C.2 Model Aggregation Analysis
    3. C.3 Differential-Private FedP3 Analysis
    4. C.4 Global Pruning Analysis
  9. D Missing Proofs
    1. D.1 Proof of Theorem 1
    2. D.2 Proof of Theorem 2
    3. D.3 Proof of Theorem 3

##  Appendix A Extended Related Work

###  A.1 Federated Network Pruning

We introduce two distinct types of network pruning within our study: 1) global
pruning, which extends from server to client, and 2) local pruning, where each
client’s network is pruned based on its own specific data. In our setting, we
assume federated pruning is the scenario with both possible global and local
pruning. Federated network pruning, a closely related field, pursues the
objective of identifying the optimal or near-optimal pruned neural network at
each communication from the server to the clients, as documented in works of
Jiang et al. (2022a) and Huang et al. (2022), for example.

During the initial phase of global pruning, (Jiang et al., 2022a) isolates a
single potent and reliable client to initiate model pruning. The subsequent
stage of local pruning incorporates all clients, advancing the adaptive
pruning process. This process involves not only parameter removal but also the
reintroduction of parameters, complemented by the standard FedAvg (McMahan et
al., 2017). However, the need for substantial local memory to record the
updated relevance measures of all parameters in the full-scale model poses a
challenge. As a solution to this problem, Huang et al. (2022) proposes an
adaptive batch normalization and progressive pruning modules that utilize
sparse local computation. Yet, these methods overlook explicit considerations
for constraints related to client-side computational resources and
communication bandwidth.

Our primary attention gravitates towards designing distinct local pruning
methods, such as (Horváth et al., 2021), (Alam et al., 2022), and (Liao et
al., 2023). Instead of learning the optimal or suboptimal pruned local
network, each client attempts to identify the optimal adaptive sparsity
method. The work of Horváth et al. (2021) has been groundbreaking, as they
introduced Ordered Dropout to navigate this issue, achieving commendable
results. It’s noteworthy that our overarching framework is compatible with
these methods, facilitating straightforward integration of diverse local
pruning methods. There are other noticeable methods, such as (Diao et al.,
2021), which focuses on reducing the size of each layer in neural networks. In
contrast, our approach contemplates a more comprehensive layer-wise selection
and emphasizes neuron-oriented sparsity.

As of our current knowledge, no existing literature directly aligns with our
approach, despite its practicality and generality. Even the standard
literature regarding federated network pruning appears to be rather
constrained.

###  A.2 Subnetwork Training

Our research aligns with the rising interest in Independent Subnetwork
Training (IST), a technique that partitions a neural network into smaller
components. Each component is trained in a distributed parallel manner, and
the results are subsequently aggregated to update the weights of the entire
model. The decoupling in IST enables each subnetwork to operate autonomously,
using fewer parameters than the complete model. This not only diminishes the
computational cost on individual nodes but also expedites synchronization.

This approach was introduced by Yuan et al. (2022) for networks with fully
connected layers and was later extended to ResNets Dun et al. (2022) and Graph
architectures Wolfe et al. (2023). Empirical evaluations have consistently
posited IST as an attractive strategy, proficiently melding data and model
parallelism to train expansive models even with restricted computational
resources.

Further theoretical insights into IST for overparameterized single hidden
layer neural networks with ReLU activations were presented by Liao &
Kyrillidis (2022). Concurrently, Shulgin & Richtárik (2023) revisited IST,
exploring it through the lens of sketch-type compression.

While acknowledging the adaptation of IST to FL using asynchronous distributed
dropout techniques Dun et al. (2023), our approach diverges significantly from
prior works. We advocate that clients should not relay the entirety of their
subnetworks to the central server—both to curb excessive networking costs and
to safeguard privacy. Moreover, our model envisions each client akin to an
assembly line component: each specializes in a fraction of the complete neural
network, guided by its intrinsic resources and computational prowess.

In Section A.1 and A.2, we compared our study with pivotal existing research,
focusing on federated network pruning and subnetwork training. Responding to
reviewer feedback, we have broadened the scope of our related work section to
include a more extensive comparison with other significant studies.

###  A.3 Model Heterogeneity

Model heterogeneity denotes the variation in local models trained across
diverse clients, as highlighted in previous research (Kairouz et al., 2021; Ye
et al., 2023). A seminal work by Smith et al. (2017) extended the well-known
COCOA method (Jaggi et al., 2014; Ma et al., 2015), incorporating system
heterogeneity by randomly selecting the number of local iterations or mini-
batch sizes. However, this approach did not account for variations in client-
specific model architectures or sizes. Knowledge distillation has emerged as a
prominent strategy for addressing model heterogeneity in Federated Learning
(FL). Li & Wang (2019) demonstrated training local models with distinct
architectures through knowledge distillation, but their method assumes access
to a large public dataset for each client, a premise not typically found in
current FL scenarios. Additionally, their approach, which shares model
outputs, contrasts with our method of sharing pruned local models. Building on
this concept, Lin et al. (2020) proposed local parameter fusion based on model
prototypes, fusing outputs of clients with similar architectures and employing
ensemble training on additional unlabeled datasets. Tan et al. (2022)
introduced an approach where clients transmit the mean values of embedding
vectors for specific classes, enabling the server to aggregate and
redistribute global prototypes to minimize the local-global prototype
distance. He et al. (2021) developed FedNAS, where clients collaboratively
train a global model by searching for optimal architectures, but this requires
transmitting both full network weights and additional architecture parameters.
Our method diverges from these approaches by transmitting only weights from a
subset of neural network layers from client to server.

##  Appendix B Experimental Details

###  B.1 Statistics of Datasets

We provide the statistics of our adopted datasets in Table. 3.

Dataset | # data | # train per client | # test per client
---|---|---|---
EMNIST-L (Cohen et al., 2017) | 48K+8K | 392 | 168
FashionMNIST (Xiao et al., 2017) | 60K+10K | 490 | 210
CIFAR10 (Krizhevsky et al., 2009) | 50K+10K | 420 | 180
CIFAR100 (Krizhevsky et al., 2009) | 50K+10K | 420 | 180
Table 3: Dataset statistics, with data uniformly divided among 100 clients by
default.

###  B.2 Data Distributions

We emulated non-iid data distribution among clients using both class-wise and
Dirichlet non-iid scenarios.

  * •

Class-wise: we designate fixed classes directly to every client, ensuring
uniform data volume per class. As specifics, EMNIST-L, FashionMNIST, and
CIFAR10 assign 5 classes per client, while CIFAR100 allocates 15 classes for
each client.

  * •

Dirichlet: following an approach similar to FedCR (Zhang et al., 2023), we use
a Dirichlet distribution over dataset labels to create a heterogeneous
dataset. Each client is assigned a vector (based on the Dirichlet
distribution) that corresponds to class preferences, dictating how labels–and
consequently images–are selected without repetition. This method continues
until every data point is allocated to a client. The Dirichlet factor
indicates the level of data non-iidness. With a Dirichlet parameter of 0.5,
about 80% of the samples for each client on EMNIST-L, FashionMNIST, and
CIFAR10 are concentrated in four classes. For CIFAR100, the parameter is set
to 0.3.

###  B.3 Network Architectures

Our primary experiments utilize four widely recognized datasets, with detailed
descriptions provided in the Experiments section. For the CIFAR10/100 and
FashionMNIST experiments, we opt for CNNs comprising two convolutional layers
and four fully-connected layers as our standard network architecture. In
contrast, for the EMNIST-L experiments, we employ a four-layer MLP
architecture. The specifics of these architectures are outlined in Table 4.
Additionally, the default ResNet18 network architecture is selected for our
layer-overlapping experiments.

Layer Type | Size | # of Params.
---|---|---
Conv + ReLu | $5\times 5\times 64$ | 4,864 / 1,664
Max Pool | $2\times 2$ | 0
Conv + ReLu | $5\times 5\times 64$ | 102, 464
Max Pool | $2\times 2$ | 0
FC + ReLu | $1600\times 1024$ | 1,638,400
FC + ReLu | $1024\times 1024$ | 1,048,576
FC + ReLu | $1024\times 10/100$ | 10,240 / 102,400

Layer Type | Size | # of Params.
---|---|---
FC + ReLu | $784\times 1024$ | 802,816
FC + ReLu | $1024\times 1024$ | 1,048,576
FC + ReLu | $1024\times 1024$ | 1,048,576
FC | $1024\times 10$ | 10,240

Table 4:  The left figure depicts the neural network architecture employed for
the CIFAR10/100 and FashionMNIST experiments. Conversely, the right figure
illustrates the default MLP (Multi-Layer Perceptron) architecture used
specifically for the EMNIST-L experiments.

###  B.4 Training Details

Our experiments were conducted on NVIDIA A100 or V100 GPUs, depending on their
availability in our cluster. The framework was implemented in PyTorch 1.4.0
and torchvision 0.5.0 within a Python 3.8 environment. Our initial code, based
on FedCR Zhang et al. (2023), was refined to include hyper-parameter fine-
tuning. A significant modification was the use of an MLP network with four FC
layers for EMNIST-L performance evaluation. We standardized the experiments to
500 epochs with a local training batch size of 48. The number of local updates
was set at 10 to assess final performance. For the learning rate, we conducted
a grid search, exploring a range from $10^{-5}$ to 0.1, with a fivefold
increase at each step. In adapting FedCR, we used their default settings and
fine-tuned the $\beta$ parameter across values
${0.0001,0.0005,0.001,0.005,0.01}$ for all datasets.

###  B.5 Quantitative Analysis of Reduced Parameters

We provide a quantitative analysis of parameter reduction across four
datasets, as shown in Figure 6. The x-axis represents different global pruning
ratios, and the y-axis indicates the number of parameters. For simplicity, we
consider a scenario where, aside from the final fully-connected layer, each
client trains only one additional layer, akin to the LowerB method used in our
earlier experiments. For instance, the label FC refers to a condition where
only FC2 and the final layer are fully trained, with other layers being pruned
during server-to-client transfer and dropped in server communication.

With a constant global pruning ratio, the left part of the figure shows the
total number of parameters in the locally deployed model post server-to-client
pruning, while the right part illustrates the communication cost for each
scenario. The numbers atop each bar indicate the relative differences between
the largest and smallest elements under various conditions. Across all
datasets, we note that higher global pruning ratios result in progressively
smaller deployed models. For example, at a 0.5 global pruning ratio, the model
size for clients training the Conv1 layer is 57.93% smaller than those
training FC2. Moreover, there is a significant disparity in communication
costs among clients. The ratios of communication costs are 10815 for CIFAR10,
1522.91 for CIFAR100, 13749.46 for FashionMNIST, and 30.23 for EMNIST-L.

(a) CIFAR10

(b) CIFAR100

(c) FashionMNIST

(d) EMNIST-L

Figure 6:  The number of parameters across multiple layers, varying according
to different global pruning ratios, spans across four distinct datasets. For
each global pruning ratio, the left side of the bar graph shows the total
number of parameters in the model after server-to-client pruning when deployed
locally. Conversely, the right side details the communication cost associated
with each scenario. Atop each bar, we indicate the relative ratio between the
layers with the largest and smallest number of parameters, i.e.,
$\mathrm{value}=\nicefrac{{\mathrm{(largest-
smallest)}}}{{\mathrm{smallest}}}$. For (d), since the size of parameters of
FC2 and FC3 are the same, we omit plotting FC3 to avoid overlapping.

##  Appendix C Extended Theoretical Analysis

###  C.1 Analysis of the General FedP3 Theoretical Framework

1: Parameters: learning rate $\gamma>0$, number of iterations $K$, sequence of
global pruning sketches
$\left(\mathbf{P}_{1}^{k},\ldots,\mathbf{P}_{n}^{k}\right)_{k\leq K}$,
aggregation sketches
$\left(\mathbf{S}_{1}^{k},\ldots,\mathbf{S}_{n}^{k}\right)_{k\leq K}$; initial
model $w^{0}\in\mathbb{R}^{d}$

2: for $k=0,1,\cdots,K$ do

3: Conduct global pruning $\mathbf{P}_{i}^{k}w^{k}$ for $i\in[n]$ and
broadcast to all computing nodes

4: for $i=1,\ldots,n$ in parallel do

5: Compute local (stochastic) gradient w.r.t. personalized model:
$\mathbf{P}_{i}^{k}\nabla f_{i}(\mathbf{P}_{i}^{k}w^{k})$

6: Take (maybe multiple) gradient descent step
$u_{i}^{k}=\mathbf{P}_{i}^{k}w^{k}-\gamma\mathbf{P}_{i}^{k}\nabla
f_{i}(\mathbf{P}_{i}^{k}w^{k})$

7: Send $v_{i}^{k}=\mathbf{S}_{i}^{k}u_{i}^{k}$ to the server

8: end for

9: Aggregate received subset of layers:
$w^{k+1}=\frac{1}{n}\sum_{i=1}^{n}v_{i}^{k}$

10: end for

Algorithm 4 FedP3 theoretical framework

We introduce the theoretical foundation of FedP3, detailed in Algorithm 4.
Line 3 demonstrates the global pruning process, employing a biased sketch over
randomized sketches $P_{i}$ for each client $i\in[n]$, as defined in
Definition 1. The procedure from Lines 4 to 8 details the local training
methods, though we exclude further local pruning for brevity. Notably, our
framework could potentially integrate various local pruning techniques, an
aspect that merits future exploration.

Our approach uniquely compresses both the weights $w^{k}$ and their gradients
$\nabla f_{i}(\mathbf{P}^{k}_{i}w^{k})$. For the sake of clarity, we assume in
Line 5 that each client $i$ calculates the pruned full gradient
$\mathbf{P}_{i}^{k}\nabla f_{i}(\mathbf{P}_{i}^{k}w^{k})$, a concept that
could be expanded to encompass stochastic gradient computations.

In alignment with Line 6, our subsequent theoretical analysis presumes that
each client performs a single-step gradient descent. This assumption stems
from observations that local steps have not demonstrated theoretical
efficiency gains in heterogeneous environments until very recent studies, such
as Mishchenko et al. (2022) and its extensions like Malinovsky et al. (2022);
Yi et al. (2023), which required extra control variables not always viable in
settings with limited resources.

Diverging from the method in Shulgin & Richtárik (2023), our model involves
explicitly sending a selected subset of layers $v_{i}^{k}$ from each client
$i$ to the server. The aggregation of these layer subsets is meticulously
described in Line 9.

Our expanded theoretical analysis is structured as follows: Section C.2
focuses on analyzing the convergence rate of our innovative model aggregation
method. In Section C.3, we introduce LDP-FedP3, a novel differential-private
variant of FedP3, and discuss its communication complexity in a local
differential privacy setting. Section C.4 then delves into the analysis of
global pruning, as detailed in Algorithm 4.

###  C.2 Model Aggregation Analysis

In this section, our objective is to examine the potential advantages of model
aggregation and to present the convergence analysis of our proposed FedP3. Our
subsequent analysis adheres to the standard nonconvex optimization framework,
with the goal of identifying an $\epsilon$-stationary point where:

$\displaystyle\mathbb{E}\\!\left[\left\|\nabla
f(w)\right\|^{2}\right]\leq\epsilon,$ (4)

Here, $\mathbb{E}\\!\left[\cdot\right]$ represents the expectation over the
inherent randomness in $w\in\mathbb{R}^{d}$. Moving forward, our analysis will
focus primarily on the convergence rate of our innovative model aggregation
strategy. To begin, we establish the smoothness assumption for each local
client’s model.

######  Assumption 1 (Smoothness).

There exists some $L_{i}\geq 0$, such that for all $i\in[n]$, the function
$f_{i}$ is $L_{i}$-smooth, i.e.,

$\left\|\nabla f_{i}(x)-\nabla f_{i}(y)\right\|\leq
L_{i}\left\|x-y\right\|,\qquad\forall x,y\in\mathbb{R}^{d}.$

This smoothness assumption is very standard for the convergence analysis
(Nesterov, 2003; Ghadimi & Lan, 2013; Mishchenko et al., 2022; Malinovsky et
al., 2022; Li & Li, 2022; Yi et al., 2023). The smoothness of function $f$ is
$\bar{L}=\frac{1}{n}\sum_{i=1}^{n}L_{i}$, we denote
$L_{\max}\coloneqq\max_{i\in n}L_{i}$.

We demonstrate the convergence of our proposed FedP3, with a detailed proof
presented in Section D.1. Here, we restate Theorem 1 for clarity: See 1

Next, we interpret the results. Utilizing the inequality $1+w\leq\exp(w)$ and
assuming $\gamma\leq\frac{1}{\sqrt{\bar{L}L_{\max}K}}$, we derive the
following:

$\displaystyle(1+\bar{L}L_{\max}\gamma^{2})^{K}\leq\exp(\bar{L}L_{\max}\gamma^{2}K)\leq\exp(1)\leq
3.$

Incorporating this into the equation from Theorem 1, we ascertain:

$\displaystyle\min_{0\leq k\leq K-1}\mathbb{E}\\!\left[\left\|\nabla
f(w^{k})\right\|^{2}\right]\leq\frac{6}{\gamma K}\Delta_{0}.$

To ensure the right-hand side of the above equation is less than $\epsilon$,
the condition becomes:

$\displaystyle\frac{6\Delta_{0}}{\gamma K}\leq\epsilon\Rightarrow
K\geq\frac{6\Delta_{0}}{\gamma\epsilon}.$

Given $\gamma\leq\frac{1}{\sqrt{\bar{L}L_{\max}K}}$, it follows that
$K\geq\frac{36(\Delta_{0})^{2}}{\bar{L}L_{\max}\epsilon^{2}}=\mathcal{O}\left(\frac{1}{\epsilon^{2}}\right)$.

Considering the communication cost per iteration is $n\times
v=n\times\frac{d}{n}=d$, the total communication cost is:

$\displaystyle
C_{\mathrm{FedP3}}=\mathcal{O}\left(\frac{d}{\epsilon^{2}}\right).$

We compare this performance with an algorithm lacking our specific model
aggregation design, namely Distributed Gradient Descent (DGD). When DGD
satisfies Assumption 4 with $A=C=0,B=1$ as per Theorem 5, the total iteration
complexity to achieve an $\epsilon$-stationary point is
$\mathcal{O}\left(\frac{1}{\epsilon}\right)$. Given that the communication
cost per iteration is $nd$, the total communication cost for DGD is:

$\displaystyle C_{\mathrm{DGD}}=\mathcal{O}\left(\frac{nd}{\epsilon}\right).$

We observe that the communication cost of FedP3 is more efficient than DGD by
a factor of $\mathcal{O}(n/\epsilon)$. This is particularly advantageous in
practical Federated Learning (FL) scenarios, where a large number of clients
are distributed, highlighting the suitability of our method for such
environments. This efficiency also opens avenues for further exploration in
large language models.

Although we have demonstrated provable advantages in communication costs for
large client numbers, we anticipate that our method’s performance exceeds our
current theoretical predictions. This expectation is based on the comparison
of FedP3 and DGD under Lemma 1. For DGD, with parameters $A=\bar{L},B=C=0$,
the iteration complexity aligns with $\mathcal{O}(\frac{1}{\epsilon^{2}})$,
leading to a communication cost of:

$\displaystyle
C_{\mathrm{DGD}}^{\prime}=\mathcal{O}\left(\frac{nd}{\epsilon^{2}}\right).$

This indicates a significant reduction in communication costs by a factor of
$n$ without additional requirements. It implies that if we could establish a
tighter bound on $\left\|\nabla f_{i}(w)\right\|^{2}$, beyond the scope of
Lemma 1, our theoretical results could be further enhanced.

###  C.3 Differential-Private FedP3 Analysis

The integration of gradient pruning as a privacy preservation method was first
brought to prominence by Zhu et al. (2019). Further studies, such as Huang et
al. (2020), have delved into the effectiveness of DNN pruning in protecting
privacy.

In our setting, we ensure that our training process focuses on extracting
partial features without relying on all layers to memorize local training
data. This is achieved by transmitting only a select subset of layers from the
client to the server in each iteration. By transmitting fewer
layers—effectively implementing greater pruning from clients to the server—we
enhance the privacy-friendliness of our framework.

This section aims to provide a theoretical exploration of the ”privacy-
friendly” aspect of our work. Specifically, we introduce a differential-
private version of our method, LDP-FedP3, and discuss its privacy guarantees,
utility, and communication cost, supported by substantial evidence and
rigorous proof.

Local differential privacy is crucial in our context. We aim not only to train
machine learning models with reduced communication bits but also to preserve
each client’s local privacy, an essential element in FL applications.
Following the principles of local differential privacy (LDP) as outlined in
works like Andrés et al. (2013); Chatzikokolakis et al. (2013); Zhao et al.
(2020); Li et al. (2022), we define two datasets ${D}$ and ${D}^{\prime}$ as
neighbors if they differ by just one entry. We provide the following
definition for LDP:

1: Parameters: learning rate $\gamma>0$, number of iterations $K$, sequence of
aggregation sketches
$\left(\mathbf{S}_{1}^{k},\ldots,\mathbf{S}_{n}^{k}\right)_{k\leq K}$,
perturbation variance $\sigma^{2}$, minibatch size $b$

2: for $k=0,1,2\ldots$ do

3: Server broadcasts $w^{k}$ to all clients

4: for each client $i=1,\ldots,n$ in parallel do

5: Sample a random minibatch $\mathcal{I}_{b}$ with size $b$ from lcoal
dataset $D_{i}$

6: Compute local stochastic gradient
${g}_{i}^{k}=\frac{1}{b}\sum_{j\in{\mathcal{I}}_{b}}\nabla f_{i,j}(w^{k})$

7: Take (maybe multiple) gradient descent step
$u_{i}^{k}=w^{k}-\gamma{g}_{i}^{k}$

8: Gaussian perturbation to achieve LDP:
$\tilde{u}^{k}_{i}=u_{i}^{k}+\zeta_{i}^{k}$, where
$\zeta_{i}^{k}\sim{\mathcal{N}}(\mathbf{0},\sigma^{2}{\mathbf{I}})$

9: Send $v_{i}^{k}=\mathbf{S}_{i}^{k}\tilde{u}_{i}^{k}$ to the server

10: end for

11: Server aggregates received subset of layers:
$w^{k+1}=\frac{1}{n}\sum_{i=1}^{n}v_{i}^{k}$

12: end for

Algorithm 5 Differential-Private FedP3 (LDP-FedP3)

######  Definition 3.

A randomized algorithm $\mathcal{A}:\mathcal{D}\to\mathcal{F}$, where
$\mathcal{D}$ is the dataset domain and $\mathcal{F}$ the domain of possible
outcomes, is $(\epsilon,\delta)$-locally differentially private for client $i$
if, for all neighboring datasets ${D}_{i},{D}_{i}^{\prime}\in\mathcal{D}$ on
client $i$ and for all events $\mathcal{S}\in\mathcal{F}$ within the range of
$\mathcal{A}$, it holds that:

$\displaystyle\mathrm{Pr}{\mathcal{A}(D_{i})\in\mathcal{S}}\leq
e^{\epsilon}\mathrm{Pr}{\mathcal{A}(D^{\prime}_{i})\in\mathcal{S}}+\delta.$

This LDP definition (Definition 3) closely resembles the original concept of
$(\epsilon,\delta)$-DP (Dwork et al., 2014; 2006), but in the FL context, it
emphasizes each client’s responsibility to safeguard its privacy. This is done
by locally encoding and processing sensitive data, followed by transmitting
the encoded information to the server, without any coordination or information
sharing among clients.

Similar to our previous analysis of FedP3, we base our discussion here on the
smoothness assumption outlined in Assumption 1. For simplicity, and because
our primary focus in this section is on privacy concerns, we assume uniform
smoothness across all clients, i.e., $L_{i}\equiv L$.

Our analysis also relies on the bounded gradient assumption, which is a common
consideration in differential privacy analyses:

######  Assumption 2 (Bounded gradient).

There exists some constant $C\geq 0$, such that for all clients $i\in[n]$ and
for any $x\in\mathbb{R}^{d}$, the gradient norm satisfies $\left\|\nabla
f_{i}(x)\right\|\leq C$.

This bounded gradient assumption aligns with standard practices in
differential privacy analysis, as evidenced in works such as (Bassily et al.,
2014; Wang et al., 2017; Iyengar et al., 2019; Feldman et al., 2020; Li et
al., 2022).

We introduce a locally differentially private version of FedP3, termed LDP-
FedP3, with detailed algorithmic steps provided in Algorithm 5. This variant
differs from FedP3 in Algorithm 4 primarily by incorporating the Gaussian
mechanism, as per Abadi et al. (2016), to ensure local differential privacy
(as implemented in Line 8 of Algorithm 5). Another distinction is the
allowance for minibatch sampling per client in LDP-FedP3. Given that our
primary focus in this section is on privacy, we set aside the global pruning
aspect for now, considering it orthogonal to our current analysis and not
central on our privacy considerations. In Theorem 2, we encapsulate the
following theorem: See 2

Table 5: Comparison of communication complexity in LDP Algorithms for nonconvex problems across distributed settings with $n$ nodes. Algorithm | Privacy | Communication Complexity
---|---|---
Q-DPSGD-1 (Ding et al., 2021) |  $(\epsilon,\delta)$-LDP | $\frac{(1+{n}/(m{\tilde{\sigma}^{2}}))m^{2}\epsilon^{2}}{d\log(1/\delta)}$
LDP SVRG/SPIDER (Lowy et al., 2023) |  $(\epsilon,\delta)$-LDP | $\frac{n^{3/2}m\epsilon\sqrt{d}}{\sqrt{\log(1/\delta)}}$
SDM-DSGD (Zhang et al., 2020) |  $(\epsilon,\delta)$-LDP | $\frac{{n^{7/2}}m\epsilon\sqrt{d}}{{(1+\omega)^{3/2}}\sqrt{\log(1/\delta)}}+\frac{{n}m^{2}\epsilon^{2}}{{(1+\omega)}\log(1/\delta)}$
CDP-SGD (Li et al., 2022) |  $(\epsilon,\delta)$-LDP | $\frac{{n^{3/2}}m\epsilon\sqrt{d}}{{(1+\omega)^{3/2}}\sqrt{\log(1/\delta)}}+\frac{{n}m^{2}\epsilon^{2}}{{(1+\omega)}\log(1/\delta)}$
LDP-FedP3 (Ours) |  $(\epsilon,\delta)$-LDP | $\frac{m\epsilon\sqrt{d}}{\sqrt{\log(1/\delta)}}+\frac{m^{2}\epsilon^{2}}{\log(1/\delta)}$

In Section D.2, we provide the proof for our analysis. This section primarily
focuses on analyzing and comparing our results with existing literature. Our
proof pertains to local differentially-private Stochastic Gradient Descent
(SGD). We note that Li et al. (2022) offered a proof for CDP-SGD using a
specific set of compressors. However, our chosen compressor does not fall into
that category, as discussed more comprehensively in Szlendak et al. (2021).
Considering the Rand-t compressor with $t=d/n$, it’s established that:

$\displaystyle\mathbb{E}\\!\left[\left\|\mathcal{R}_{t}(w)-w\right\|^{2}\right]\leq\omega\left\|w\right\|^{2},\quad\text{where}\quad\omega=\frac{d}{t}-1=n-1.$

Setting the same $K$ and $\gamma$ and applying Theorem 1 from Li et al.
(2022), we obtain:

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\\!\left[{\left\lVert\nabla
f(w^{t})\right\rVert}^{2}\right]\leq\frac{5C\sqrt{Lcd\log(1/\sigma)}}{m\epsilon}=\mathcal{O}\left(\frac{C\sqrt{Ld\log(1/\delta)}}{m\epsilon}\right),$

which aligns with our theoretical analysis. Interestingly, we observe that our
bound is tighter by a factor of $2/5$, indicating a more efficient performance
in our approach.

We also compare our proposed LDP-FedP3 with other existing algorithms in
Algorithm 5. An intriguing finding is that our method’s efficiency does not
linearly increase with a higher number of clients, denoted as $n$. Notably,
our communication complexity remains independent of $n$. This implies that in
practical scenarios with a large $n$, our communication costs will not
escalate. We then focus on methods with a similar structure, namely, SDM-DSGD
and CDP-SGD. For these, the communication cost comprises two components.
Considering a specific case, Rand-t, where $t$ is deliberately set to $d/n$,
we derive $\omega=\nicefrac{{d}}{{t}}-1=n-1$. This results in a communication
complexity on par with CDP-SGD, but significantly more efficient than SDM-
DSGD. Moreover, it’s important to note that the compressor in LDP-FedP3
differs from that in CDP-SGD. Our analysis introduces new perspectives and
achieves comparable communication complexity to other well-established
results.

###  C.4 Global Pruning Analysis

Our methodology relates to independent subnetwork training (IST) but
introduces distinctive features such as personalization and explicit layer-
level sampling for aggregation. IST, although conceptually simple, remains
underexplored with only limited studies like Liao & Kyrillidis (2022), which
provides theoretical insights for overparameterized single hidden layer neural
networks with ReLU activations, and Shulgin & Richtárik (2023), which revisits
IST from the perspective of sketch-type compression. In this section, we delve
into the nuances of global pruning as applied in Algorithm 4.

For our analysis here, centered on global pruning, we simplify by assuming
that all personalized model aggregation sketches $\mathbf{S}_{i}$ are
identical matrices, that is, $\mathbf{S}_{i}={\mathbf{I}}$. This
simplification, however, does not trivialize the analysis as the pruning of
both gradients and weights complicates the convergence analysis. Additionally,
we adhere to the design of the global pruning sketch $\mathbf{P}$ as per
Definition 1, which results in a biased estimation, i.e.,
$\mathbb{E}[\mathbf{P}_{i}w]\neq w$. Unbiased estimators, such as Rand-t that
operates over coordinates, are more commonly studied and offer several
advantages in theoretical analysis.

For Rand-t, consider a random subset $\mathcal{S}$ of $[d]$ representing a
proper sampling with probability
$c_{j}\coloneqq\mathrm{Prob}(j\in\mathcal{S})>0$ for every $j\in[d]$.
$\mathcal{R}_{t}\coloneqq\mathrm{Diag}(r_{s}^{1},r_{s}^{2},\cdots,r_{s}^{d})$,
where $r_{s}^{j}=\nicefrac{{1}}{{c_{j}}}$ if $j\in\mathcal{S}$ and $0$
otherwise. In contrast to our case, the value on each selected coordinate in
Rand-t is scaled by the probability $p_{i}$, equivalent to $|\mathcal{S}|/d$.
However, the implications of using a biased estimator like ours are not as
well understood.

Our theoretical focus is on Federated Learning (FL) in the context of
empirical risk minimization, formulated in (1) within quadratic problem
frameworks. This setting involves symmetric matrices $\mathbf{L}_{i}$, as
defined in the following equation:

$\displaystyle f(w)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(w),\quad\text{where}\quad
f_{i}(w)\equiv\frac{1}{2}w^{\top}\mathbf{L}_{i}w-w^{\top}b_{i}.$ (5)

While Equation 5 simplifies the loss function, the quadratic problem paradigm
is extensively used in neural network analysis (Zhang et al., 2019; Zhu et
al., 2022; Shulgin & Richtárik, 2023). Its inherent complexity provides
valuable insights into complex optimization algorithms (Arjevani et al., 2020;
Cunha et al., 2022; Goujaud et al., 2022), thereby serving as a robust model
for both theoretical examination and practical applications. In this
framework, $f(x)$ is $\operatorname{\overline{\mathbf{L}}}$-smooth, and
$\nabla
f(x)=\operatorname{\overline{\mathbf{L}}}x-\operatorname{\overline{b}}$, where
$\operatorname{\overline{\mathbf{L}}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{L}_{i}$,
and $\operatorname{\overline{b}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}b_{i}$.

At this juncture, we introduce a fundamental assumption commonly applied in
the theoretical analysis of coordinate descent-type methods.

######  Assumption 3 (Matrix Smoothness).

Consider a differentiable function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$. We
say that $f$ is $\mathbf{L}$-smooth if there exists a positive semi-definite
matrix $\mathbf{L}\in\mathbb{R}^{d\times d}$ satisfying the following
condition for all $x,h\in\mathbb{R}^{d}$:

$f(x+h)\leq f(x)+\langle\nabla
f(x),h\rangle+\frac{1}{2}\langle\mathbf{L}h,h\rangle.$ (6)

The classical $L$-smoothness condition, where $\mathbf{L}=L\cdot\mathbf{I}$,
is a particular case of Equation equation 6. The concept of matrix smoothness
has been pivotal in the development of gradient sparsification methods,
particularly in scenarios optimizing under communication constraints, as shown
in Safaryan et al. (2021); Wang et al. (2022). We then present our main theory
under the interpolation regime for a quadratic problem (5) with $b_{i}\equiv
0$, as detailed in Theorem 3.

We first provide the theoretical analysis of biased global pruning as
implemented in Algorithm 5. To the best of our knowledge, biased gradient
estimators have rarely been explored in theoretical analysis. However, our
approach of intrinsic submodel training or global pruning is inherently
biased. Shulgin & Richtárik (2023) proposed using the Perm-K (Szlendak et al.,
2021) as the global pruning sketch. Unlike their approach, which assumes a
pruning connection among clients, our method considers the biased Rand-K
compressor over coordinates.

######  Theorem 3 (Global pruning).

In the interpolation regime for a quadratic problem (5) with
$\operatorname{\overline{\mathbf{L}}}\succ 0$ and $b_{i}\equiv 0$, let
$\operatorname{\overline{\mathbf{L}}}^{k}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\mathbf{P}_{i}^{k}\operatorname{\overline{\mathbf{L}}}\mathbf{P}_{i}^{k}$.
Assume that
$\operatorname{\overline{\mathbf{W}}}\coloneqq\frac{1}{2}\mathbb{E}[\mathbf{P}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}+\mathbf{P}^{k}\operatorname{\overline{\mathbf{B}}}^{k}\operatorname{\overline{\mathbf{L}}}]\succeq
0$ and there exists a constant $\theta>0$ such that
$\mathbb{E}[\operatorname{\overline{\mathbf{B}}}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}]\preceq\theta\operatorname{\overline{\mathbf{W}}}$.
Also, assume $f(\mathbf{P}^{k}w^{k})\leq(1+\gamma^{2}h)f(w^{k})-f^{\inf}$ for
some $h>0$. Fixing the number of iterations $K$ and choosing the step size
$\gamma\in\min\left\\{\sqrt{\frac{\log 2}{hK}},\frac{1}{\theta}\right\\}$, the
iterates satisfy:

$\mathbb{E}\left[\|\nabla
f(w^{k})\|^{2}_{\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}}\right]\leq\frac{4\Delta_{0}}{\gamma
K},$

where $\Delta_{0}=f(w^{0})-f^{\inf}$.

By employing the definition of $\gamma$, we demonstrate that the iteration
complexity is $\mathcal{O}(1/\epsilon^{2})$. Compared with the analysis in
Shulgin & Richtárik (2023), we allow personalization and do not constrain the
global pruning per client to be dependent on other clients. Global pruning is
essentially a biased estimator over the global model weights, a concept not
widely understood. Our theorem provides insightful perspectives on the
convergence of global pruning.

Our theory could also extend to the general case by applying the rescaling
trick from Section 3.2 in Shulgin & Richtárik (2023). This conversion of the
biased estimator to an unbiased one leads to a general convergence theory.
However, this is impractical for realistic global pruning analysis, as it
involves pruning the global model without altering each weight’s scale. Given
that IST and biased gradient estimators are relatively new in theoretical
analysis, we hope our analysis could provide some insights.

##  Appendix D Missing Proofs

###  D.1 Proof of Theorem 1

Building on the smoothness assumption of $L_{i}$ outlined in Assumption 1, the
following lemma is established:

######  Lemma 1.

Given that a function $f_{i}$ satisfies Assumption 1 for each $i\in[n]$, then
for any $w\in\mathbb{R}^{d}$, it holds that

$\displaystyle\left\|\nabla f_{i}(w)\right\|^{2}\leq
2L_{i}(f_{i}(w)-f^{\inf}).$ (7)

###### Proof.

Consider $w^{\prime}=w-\frac{1}{L_{i}}\nabla f_{i}(w)$. By applying the
$L_{i}$-smoothness condition of $f$ as per Assumption 1, we obtain

$\displaystyle f_{i}(w^{\prime})$ $\displaystyle\leq f_{i}(w)+\langle\nabla
f_{i}(w),w^{\prime}-w\rangle+\frac{L_{i}}{2}\|\nabla f_{i}(w)\|^{2}.$

Taking into account that $f^{\inf}\leq f_{i}(w^{\prime})$, it follows that

$\displaystyle f^{\inf}$ $\displaystyle\leq f_{i}(w^{\prime})$
$\displaystyle\leq f_{i}(w)-\frac{1}{L_{i}}\|\nabla
f_{i}(w)\|^{2}+\frac{1}{2L_{i}}\|\nabla f_{i}(w)\|^{2}$
$\displaystyle=f_{i}(w)-\frac{1}{2L_{i}}\|\nabla f_{i}(w)\|^{2}.$

Rearranging the terms yields the claimed result. ∎

Since in this section, we are primarily interested in exploring the
convergence of our novel model aggregation design, we set
$\mathbf{P}_{i}^{k}\equiv{\mathbf{I}}$ for all $i\in[n]$ and $k\in[K]$. Our
analysis focuses on exploring the characteristics of $\mathbf{S}$, which leads
to the following theorem.

By the definition of model aggregation sketches in Definition 2, we have
$\frac{1}{n}\sum_{i=1}^{n}\mathbf{S}_{i}={\mathbf{I}}$. Thus, the next iterate
can be represented as

$\displaystyle w^{k+1}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbf{S}_{i}^{k}(w^{k}-\gamma\nabla
f_{i}(w^{k}))$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbf{S}_{i}^{k}w^{k}-\gamma\underbrace{\frac{1}{n}\sum_{i=1}^{n}\mathbf{S}_{i}^{k}\nabla
f_{i}(w^{k})}_{g^{k}}$ (8) $\displaystyle=w^{k}-\gamma g^{k}.$

Bounding $g^{k}$ is a crucial part of our analysis. To align with existing
works on non-convex optimization, numerous critical assumptions are
considered. Extended reading on this can be found in Khaled & Richtárik
(2020). Here, we choose the weakest assumption among all those listed in
Khaled & Richtárik (2020).

######  Assumption 4 (ABC Assumption).

For the second moment of the stochastic gradient, it holds that

$\displaystyle\mathbb{E}\left[\|\mathbf{g}(w)\|^{2}\right]\leq
2A(f(w)-f^{\inf})+B\|\nabla f(w)\|^{2}+C,$ (9)

for certain constants $A,B,C\geq 0$ and for all $w\in\mathbb{R}^{d}$.

Note that in order to accommodate heterogeneous settings, we assume a
localized version of Assumption 4. Specifically, each
$g_{i}^{k}\equiv\mathbf{S}_{i}^{k}\nabla f_{i}(w^{k})$ is bounded for some
constants $A_{i},B_{i},C_{i}\geq 0$ and all $w^{k}\in\mathbb{R}^{d}$.

######  Lemma 2.

The $g^{k}$ defined in Eqn. 8 satisfies Assumption 4 with $A=L_{\max}$,
$B=C=0$.

###### Proof.

The proof is as follows:

$\displaystyle\mathbb{E}_{k}\left[\|g^{k}\|^{2}\right]$
$\displaystyle=\mathbb{E}_{k}\left[\|\frac{1}{n}\sum_{i=1}^{n}S_{i}\nabla
f_{i}(w^{k})\|^{2}\right]$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(w^{k})\|^{2}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}2L_{i}(f_{i}(w^{k})-f^{\inf})$ (10)
$\displaystyle\leq 2L_{\max}(f(w^{k})-f^{\inf}),$

where Equation 10 follows from Lemma 1. ∎

We also recognize certain characteristics of the unbiasedness and upper bound
of model aggregation sketches, as elaborated in Theorem 4.

######  Theorem 4 (Unbiasedness and Upper Bound of Model Aggregation
Sketches).

For any vector $w\in\mathbb{R}^{d}$, the model aggregation sketch
$\mathbf{S}_{i}$, for each $i\in[n]$, is unbiased, meaning
$\mathbb{E}[\mathbf{S}_{i}w]=w$. Moreover, for any set of vectors
$y_{1},y_{2},\ldots,y_{n}\in\mathbb{R}^{d}$, the following inequality is
satisfied:

$\displaystyle\mathbb{E}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathbf{S}_{i}y_{i}\right\|^{2}\right]\leq\frac{1}{n}\sum_{i=1}^{n}\left\|y_{i}\right\|^{2}.$

###### Proof.

Consider a vector $x\in\mathbb{R}^{d}$, where $x_{i}$ denotes the $i$-th
element of $x$. We first establish the unbiasedness of the model aggregation
sketch (Definition 1):

$\mathbb{E}[\mathbf{S}_{i}x]=n\sum_{j=q(i-1)+1}^{qi}\mathbb{E}[x_{\pi_{j}}e_{\pi_{j}}]=n\left(\sum_{j=q(i-1)+1}^{qi}\frac{1}{d}\sum_{i=1}^{d}x_{i}e_{i}\right)=\frac{nq}{d}x=x.$
(11)

Next, we examine the second moment:

$\mathbb{E}\left[\|\mathbf{S}_{i}x\|^{2}\right]=n^{2}\sum_{j=q(i-1)+1}^{qi}\frac{1}{d}\sum_{i=1}^{d}\left\|x_{i}\right\|^{2}=n^{2}\frac{q}{d}\left\|x\right\|^{2}=n\left\|x\right\|^{2}.$

For all vectors $y_{1},y_{2},\ldots,y_{n}\in\mathbb{R}^{d}$, the following
inequality holds:

$\displaystyle\mathbb{E}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathbf{S}_{i}y_{i}\right\|^{2}\right]$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}\mathbb{E}\left[\left\|\mathbf{S}_{i}y_{i}\right\|\right]+\sum_{i\neq
j}\mathbb{E}\left[\langle\mathbf{S}_{i}y_{i},\mathbf{S}_{j}y_{j}\rangle\right]=\frac{1}{n^{2}}\sum_{i=1}^{n}\mathbb{E}\left[\left\|\mathbf{S}_{i}y_{i}\right\|\right]=\frac{1}{n}\sum_{i=1}^{n}\left\|y_{i}\right\|^{2}.$
(12)

Integrating Equation 11 with Equation 12, we also deduce:

$\displaystyle\mathbb{E}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathbf{S}_{i}y_{i}-\frac{1}{n}\sum_{i=1}^{n}y_{i}\right\|^{2}\right]\leq\frac{1}{n}\sum_{i=1}^{n}\left\|y_{i}\right\|^{2}-\left\|\frac{1}{n}\sum_{i=1}^{n}y_{i}\right\|^{2}.$
(13)

∎

We now proceed to prove the main theorem of model aggregation, as presented in
Theorem 1. This theorem is restated below for convenience: See 1

Our proof draws inspiration from the analysis in Theorem 2 of Khaled &
Richtárik (2020) and is reformulated as follows:

######  Theorem 5 (Theorem 2 in Khaled & Richtárik (2020)).

Under the assumptions that Assumption 1 and 4 are satisfied, let us choose a
step size $\gamma>0$ such that $\gamma\leq\frac{1}{\bar{L}B}$. Define
$\Delta\equiv f(w^{0})-f^{\inf}$. Then, it holds that

$\displaystyle\min_{0\leq k\leq K-1}\mathbb{E}\left[\|\nabla
f(w^{k})\|^{2}\right]\leq\bar{L}C\gamma+\frac{2(1+\bar{L}\gamma^{2}A)^{K}}{\gamma
K}\Delta.$

Careful control of the step size is crucial to prevent potential blow-up of
the term and to ensure convergence to an $\epsilon$-stationary point. Our
theory can be seen as a special case with $A=L_{\max},B=0,C=0$, as established
in Lemma 2. Thus, we conclude our proof.

###  D.2 Proof of Theorem 2

To establish the convergence of the proposed method, we begin by presenting a
crucial lemma which describes the mean and variance of the stochastic
gradient. Consider the stochastic gradient
$g_{i}^{k}=\frac{1}{b}\sum_{j\in\mathcal{I}_{b}}\nabla f_{i,j}(w^{k})$ as
outlined in Line 6 of Algorithm 5.

######  Lemma 3 (Lemma 9 in Li et al. (2022)).

Given Assumption 2, for any client $i$, the stochastic gradient estimator
$g_{i}^{k}$ is an unbiased estimator, that is,

$\displaystyle\mathbb{E}_{k}\left[\frac{1}{b}\sum_{j\in\mathcal{I}_{b}}\nabla
f_{i,j}(w^{k})\right]=\nabla f_{i}(w^{k}),$

where $\mathbb{E}_{k}$ denotes the expectation conditioned on all history up
to round $k$. Letting $q=\frac{b}{m}$, the following inequality holds:

$\displaystyle\mathbb{E}_{k}\left[\left\|\frac{1}{b}\sum_{j\in\mathcal{I}_{b}}\nabla
f_{i,j}(w^{k})-\nabla
f_{i}(w^{k})\right\|^{2}\right]\leq\frac{(1-q)C^{2}}{b}.$

Considering the definition of $\mathcal{S}_{i}^{k}$, we observe that
$\frac{1}{n}\sum_{i=1}^{n}\mathcal{S}_{i}^{k}=\mathbf{I}$. According to
Algorithm 5, the next iteration $w^{k+1}$ of the global model is given by:

$w^{k+1}=\frac{1}{n}\sum_{i=1}^{n}\mathcal{S}_{i}^{k}\left(w^{k}-\gamma
g^{k}_{i}+\zeta_{i}^{k}\right)=w^{k}-\underbrace{\frac{1}{n}\sum_{i=1}^{n}\mathcal{S}_{i}^{k}(\gamma
g_{i}^{k}-\zeta_{i}^{k})}_{G^{k}}.$

Employing the smoothness Assumption 1 and taking expectations, we derive:

$\displaystyle\mathbb{E}_{k}[f(w^{k+1})]$ $\displaystyle\leq
f(w^{k})-\mathbb{E}_{k}\left\langle\nabla
f(w^{k}),G^{k}\right\rangle+\frac{L}{2}\mathbb{E}_{k}\left\|G^{k}\right\|^{2}.$
(14)

Given that $\zeta_{i}^{k}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I})$, we
have $\mathbb{E}_{k}[\zeta_{i}^{k}]=0$. Consequently, we can analyze
$\mathbb{E}_{k}\langle\nabla f(w^{k}),G^{k}\rangle$ as follows:

$\displaystyle\mathbb{E}_{k}\langle\nabla f(w^{k}),G^{k}\rangle$
$\displaystyle=\mathbb{E}_{k}\left\langle\nabla
f(w^{k}),\frac{1}{n}\sum_{i=1}^{n}\mathcal{S}_{i}^{k}(\gamma
g_{i}^{k}-\zeta_{i}^{k})\right\rangle$
$\displaystyle\stackrel{{\scriptstyle(\ref{eqn:unbiased_aggregation_sketch})}}{{=}}\mathbb{E}_{k}\left\langle\nabla
f(w^{k}),\frac{1}{n}\sum_{i=1}^{n}(\gamma
g_{i}^{k}-\zeta_{i}^{k})\right\rangle$
$\displaystyle=\mathbb{E}_{k}\left\langle\nabla
f(w^{k}),\gamma\frac{1}{n}\sum_{i=1}^{n}g_{i}^{k}\right\rangle$
$\displaystyle\stackrel{{\scriptstyle(\ref{lem:g_variance})}}{{=}}\gamma\left\|\nabla
f(w^{k})\right\|^{2}.$ (15)

To bound the last term $\mathbb{E}_{k}\left\|G^{k}\right\|^{2}$ in Equation
14, we proceed as follows:

$\displaystyle\mathbb{E}_{k}\left\|G^{k}\right\|^{2}$
$\displaystyle=\mathbb{E}_{k}\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{S}_{i}^{k}(\underbrace{\gamma
g_{i}^{k}-\zeta_{i}^{k}}_{M_{i}^{k}})\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eqn:second_moment_aggregation_sketch})}}{{\leq}}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{k}\left\|M_{i}^{k}\right\|^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{k}\left\|\gamma
g_{i}^{k}-\zeta_{i}^{k}\right\|^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{k}\left\|\gamma
g_{i}^{k}\right\|^{2}+d\sigma^{2}$
$\displaystyle=\gamma^{2}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{k}\left\|g_{i}^{k}-\nabla
f_{i}(w^{k})+\nabla f_{i}(w^{k})\right\|^{2}+d\sigma^{2}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\gamma^{2}\left\|\nabla
f_{i}(w^{k})\right\|^{2}+\gamma^{2}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{k}\left\|g_{i}^{k}-\nabla
f_{i}(w^{k})\right\|^{2}+d\sigma^{2}$
$\displaystyle\stackrel{{\scriptstyle(\ref{lem:g_variance},\ref{asm:bounded_gradient})}}{{\leq}}\gamma^{2}C^{2}+\frac{\gamma^{2}(1-q)C^{2}}{b}+d\sigma^{2}.$
(16)

Incorporating Equations 16 and 15 into Equation 14, we obtain the following
inequality for the expected function value at the next iteration:

$\displaystyle\mathbb{E}_{k}[f(w^{k+1})]$ $\displaystyle\leq
f(w^{k})-\gamma\left\|\nabla
f(w^{k})\right\|^{2}+\frac{L}{2}\left(\gamma^{2}C^{2}+\frac{\gamma^{2}(1-q)C^{2}}{b}+d\sigma^{2}\right).$
(17)

Before proceeding further, it is pertinent to consider the privacy guarantees
of FedP3, which are based on the analysis of SoteriaFL as presented in Theorem
2 of Li et al. (2022). We reformulate this theorem as follows:

######  Theorem 6 (Theorem 2 in Li et al. (2022)).

Assume each client possesses $m$ data points. Under Assumption 3 in Li et al.
(2022) and given two bounding constants $C_{A}$ and $C_{B}$ for the decomposed
gradient estimator, there exist constants $c$ and $c^{\prime}$. For any
$\epsilon<c^{\prime}\frac{b^{2}T}{m^{2}}$ and $\delta\in(0,1)$, SoteriaFL
satisfies $(\epsilon,\delta)$-Local Differential Privacy (LDP) if we choose

$\sigma_{p}^{2}=\frac{c\left(C_{A}^{2}/4+C_{B}^{2}\right)K\log(1/\delta)}{m^{2}\epsilon^{2}}.$

In the absence of gradient shift consideration within SoteriaFL, the
complexity of the gradient estimator can be reduced. We simplify the analysis
by substituting the two bounds $C_{A}$ and $C_{B}$ with a single constant $C$.
Following a similar setting, we derive the privacy guarantee for LDP-FedP3 as:

$\displaystyle\sigma^{2}=\frac{cC^{2}K\log(1/\delta)}{m^{2}\epsilon^{2}},$
(18)

which establishes that LDP-FedP3 is $(\epsilon,\delta)$-LDP compliant under
the above condition.

Substituting $\sigma$ from Equation 18 and telescoping over iterations
$k=1,\ldots,K$, we can demonstrate the following convergence bound:

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\left\|\nabla
f(w^{k})\right\|^{2}\right]$
$\displaystyle\leq\frac{f(w^{0})-f^{\star}}{\gamma K}+\frac{L}{2}\left[\gamma
C^{2}+\frac{\gamma(1-q)C^{2}}{b}+\frac{cdC^{2}T\log(1/\delta)}{\gamma
m^{2}\epsilon^{2}}\right]$ $\displaystyle\leq\frac{\Delta_{0}}{\gamma
K}+\frac{L}{2}\left[\frac{\gamma(b+1-q)}{b}C^{2}+\frac{cdC^{2}K\log(1/\delta)}{\gamma
m^{2}\epsilon^{2}}\right]$ $\displaystyle\leq\frac{\Delta_{0}}{\gamma
K}+\frac{L}{2}\left[\gamma C^{2}+\frac{cdC^{2}K\log(1/\delta)}{\gamma
m^{2}\epsilon^{2}}\right].$

To harmonize our analysis with existing works, such as CDP-SGD proposed by Li
et al. (2022), which compresses the gradient and performs aggregation on the
server over the gradients instead of directly on the weights, we reframe
Algorithm 5 accordingly. The primary modification involves defining
$M_{i}^{k}\coloneqq\gamma g_{i}^{k}-\gamma\zeta_{i}^{k}$, where
$\zeta_{i}^{k}$ is scaled by a factor of $\gamma$. This leads to the following
convergence result:

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\left\|\nabla
f(w^{k})\right\|^{2}\right]$ $\displaystyle\leq\frac{\Delta_{0}}{\gamma
K}+\frac{\gamma
LC^{2}}{2}\left[1+\frac{cdK\log(1/\delta)}{m^{2}\epsilon^{2}}\right].$ (19)

Optimal choices for $K$ and $\gamma$ that align with this convergence result
can be defined as:

$\displaystyle\gamma K$
$\displaystyle=\frac{m\epsilon\sqrt{\Delta_{0}}}{C\sqrt{Lcd\log(1/\delta)}},\quad
K\geq\frac{m^{2}\epsilon^{2}}{cd\log\left(1/\delta\right)}.$ (20)

Adhering to the relationship established in Equation equation 20 and
considering the stepsize constraint $\gamma\leq\frac{1}{L}$, we define:

$\displaystyle K$
$\displaystyle=\max\left\\{\frac{m\epsilon\sqrt{L\Delta_{0}}}{C\sqrt{cd\log(1/\delta)}},\frac{m^{2}\epsilon^{2}}{cd\log(1/\delta)}\right\\},$
$\displaystyle\gamma$
$\displaystyle=\min\left\\{\frac{1}{L},\frac{\sqrt{\Delta_{0}cd\log(1/\delta)}}{Cm\epsilon\sqrt{L}}\right\\}.$

Substituting these into Equation 19, we obtain:

$\displaystyle\frac{1}{K}\sum_{t=1}^{K}\mathbb{E}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]$ $\displaystyle\leq\frac{\Delta_{0}}{\gamma
K}+\frac{\gamma
LC^{2}}{2}\left[1+\frac{cdK\log(1/\delta)}{m^{2}\epsilon^{2}}\right]$
$\displaystyle\leq\frac{\Delta_{0}}{\gamma K}+\frac{\gamma
LC^{2}cdK\log(1/\delta)}{m^{2}\epsilon^{2}}$
$\displaystyle=\frac{\Delta_{0}}{\gamma K}+\frac{\gamma
KLC^{2}cd\log(1/\delta)}{m^{2}\epsilon^{2}}$
$\displaystyle\leq\frac{2C\sqrt{Lcd\log(1/\delta)}}{m\epsilon}$
$\displaystyle=\mathcal{O}\left(\frac{C\sqrt{Ld\log(1/\delta)}}{m\epsilon}\right).$

Neglecting the constant $c$, the total communication cost for LDP-FedP3 is
computed as:

$\displaystyle C_{\text{LDP-FedP3}}$ $\displaystyle=n\frac{d}{n}K=dK$
$\displaystyle=\max\left\\{\frac{m\epsilon\sqrt{dL\Delta_{0}}}{C\sqrt{\log(1/\delta)}},\frac{m^{2}\epsilon^{2}}{\log(1/\delta)}\right\\}$
$\displaystyle=\mathcal{O}\left(\frac{m\epsilon\sqrt{dL\Delta_{0}}}{C\sqrt{\log(1/\delta)}}+\frac{m^{2}\epsilon^{2}}{\log(1/\delta)}\right).$

###  D.3 Proof of Theorem 3

We consider the scenario where $\mathbf{P}_{i}^{k}$ acts as a biased random
sparsifier, and $\mathbf{S}_{i}^{k}\equiv\mathbf{I}$. In this case, the update
rule is given by:

$w^{k+1}=\frac{1}{n}\sum_{i=1}^{n}\left(\mathbf{P}_{i}^{k}w^{k}-\gamma\mathbf{P}_{i}^{k}\nabla
f_{i}(\mathbf{P}_{i}^{k}w^{k})\right).$

Let $w\in\mathbb{R}^{d}$ and let $S$ represent the selected number of
coordinates from $d$. Then, $\mathbf{P}_{i}$ is defined as:

$\mathbf{P}_{i}=\mathrm{Diag}(c_{s}^{1},c_{s}^{2},\cdots,c_{s}^{d}),\quad\text{where}\quad
c_{s}^{j}=\begin{cases}1&\text{if }j\in S,\\\ 0&\text{if }j\notin
S.\end{cases}$

Given that $\mathbf{P}_{i}\preceq\mathbf{I}$, it follows that
$\frac{1}{n}\sum_{i=1}^{n}\mathbf{P}_{i}\preceq\mathbf{I}$.

In the context where $\mathbf{P}_{i}$ is a biased sketch, we introduce
Assumption 5:

######  Assumption 5.

For any learning rate $\gamma>0$, there exists a constant $h>0$ such that, for
any $\mathbf{P}\in\mathbb{R}^{d\times d}$, $w\in\mathbb{R}^{d}$, we have:

$\displaystyle f(\mathbf{P}w)\leq(1+\gamma^{2}h)(f(w)-f^{\inf}).$

Assumption 5 assumes the pruning sketch is bounded. Given that the function
value should remain finite, this assumption is reasonable and applicable.

In this section, for simplicity, we focus on the interpolation case where
$f_{i}(x)=\frac{1}{2}w^{\top}\mathbf{L}_{i}w$. The extension to scenarios with
$b_{i}\neq 0$ is left for future work. By leveraging the
$\operatorname{\overline{\mathbf{L}}}$-smoothness of function $f$ and the
diagonal nature of $\mathbf{P}_{i}$, we derive the following:

$\displaystyle f(w^{k+1})$ $\displaystyle\coloneqq
f\left(\frac{1}{n}\sum_{i=1}^{n}(\mathbf{P}_{i}^{k}w^{k}-\gamma\mathbf{P}_{i}^{k}\nabla
f_{i}(\mathbf{P}_{i}^{k}w^{k}))\right)$ (21)
$\displaystyle=f\left(\underbrace{\frac{1}{n}\sum_{i=1}^{n}\mathbf{P}_{i}^{k}}_{\mathbf{P}^{k}}w^{k}-\gamma\underbrace{\frac{1}{n}\sum_{i=1}^{n}\mathbf{P}_{i}^{k}\operatorname{\overline{\mathbf{L}}}_{i}\mathbf{P}_{i}^{k}}_{\operatorname{\overline{\mathbf{B}}}^{k}}w^{k}\right)$
$\displaystyle\leq f(\mathbf{P}^{k}w^{k})-\gamma\langle\nabla
f(\mathbf{P}^{k}w^{k}),\operatorname{\overline{\mathbf{B}}}^{k}w^{k}\rangle+\frac{\gamma^{2}}{2}\left\|\operatorname{\overline{\mathbf{B}}}^{k}w^{k}\right\|^{2}_{\operatorname{\overline{\mathbf{L}}}}$
$\displaystyle\stackrel{{\scriptstyle(\ref{asm:biased_bound})}}{{\leq}}af(w^{k})-\gamma\langle\operatorname{\overline{\mathbf{L}}}\mathbf{P}^{k}w^{k},\operatorname{\overline{\mathbf{B}}}^{k}w^{k}\rangle+\frac{\gamma^{2}}{2}\left\|\operatorname{\overline{\mathbf{B}}}^{k}w^{k}\right\|^{2}_{\operatorname{\overline{\mathbf{L}}}}$
$\displaystyle=af(w^{k})-\gamma(w^{k})^{\top}\mathbf{P}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}w^{k}+\frac{\gamma^{2}}{2}(w^{k})^{\top}\operatorname{\overline{\mathbf{B}}}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}w^{k}$

Considering the conditional expectation and its linearity, along with the
transformation properties of symmetric matrices, we obtain:

$w^{\top}\operatorname{\overline{\mathbf{L}}}w=\frac{1}{2}w^{\top}\left(\operatorname{\overline{\mathbf{L}}}+\operatorname{\overline{\mathbf{L}}}^{\top}\right)w.$

By defining
$\operatorname{\overline{\mathbf{W}}}\coloneqq\frac{1}{2}\mathbb{E}\\!\left[\mathbf{P}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}+\mathbf{P}^{k}\operatorname{\overline{\mathbf{B}}}^{k}\operatorname{\overline{\mathbf{L}}}\right]$
and setting the stepsize $\gamma$ to be less than or equal to
$\frac{1}{\theta}$, we can derive the following:

$\displaystyle\mathbb{E}\\!\left[f(w^{k+1})|w^{k}\right]$ $\displaystyle\leq
af(w^{k})-\gamma(w^{k})^{\top}\mathbb{E}\\!\left[\mathbf{P}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}\right]w^{k}+\frac{\gamma^{2}}{2}(w^{k})^{\top}\mathbb{E}\\!\left[\operatorname{\overline{\mathbf{B}}}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}\right]w^{k}$
(22)
$\displaystyle=af(w^{k})-\gamma(w^{k})^{\top}\operatorname{\overline{\mathbf{W}}}w^{k}+\frac{\gamma^{2}}{2}(w^{k})^{\top}\mathbb{E}\\!\left[\operatorname{\overline{\mathbf{B}}}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}\right]w^{k}$
$\displaystyle=af(w^{k})-\gamma(\nabla
f(w^{k}))^{\top}\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}\nabla
f(w^{k})+\frac{\gamma^{2}}{2}(\nabla
f(w^{k}))^{\top}\operatorname{\overline{\mathbf{L}}}^{-1}\mathbb{E}\\!\left[\operatorname{\overline{\mathbf{B}}}^{k}\operatorname{\overline{\mathbf{L}}}\operatorname{\overline{\mathbf{B}}}^{k}\right]\operatorname{\overline{\mathbf{L}}}^{-1}\nabla
f(w^{k})$ $\displaystyle\leq af(w^{k})-\gamma(\nabla
f(w^{k}))^{\top}\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}\nabla
f(w^{k})+\frac{\gamma^{2}}{2}(\nabla
f(w^{k}))^{\top}\operatorname{\overline{\mathbf{L}}}^{-1}\theta\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}\nabla
f(w^{k})$ $\displaystyle=af(w^{k})-\gamma\left\|\nabla
f(w^{k})\right\|^{2}_{\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}}+\frac{\theta\gamma^{2}}{2}\left\|\nabla
f(w^{k})\right\|^{2}_{\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}}$
$\displaystyle=af(w^{k})-\gamma(1-\nicefrac{{\theta\gamma}}{{2}})\left\|\nabla
f(w^{k})\right\|^{2}_{\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}}$
$\displaystyle\leq af(w^{k})-\frac{\gamma}{2}\left\|\nabla
f(w^{k})\right\|^{2}_{\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}}.$

Our subsequent analysis relies on the following useful lemma:

######  Lemma 4.

Consider two sequences $\\{X_{k}\\}_{k\geq 0}$ and $\\{Y_{k}\\}_{k\geq 0}$ of
nonnegative real numbers satisfying, for each $k\geq 0$, the recursion

$X_{k+1}\leq aX_{k}-Y_{k}+c,$

where $a>1$ and $c\geq 0$ are constants. Let $K\geq 1$ be fixed. For each
$k=0,1,\ldots,K-1$, define the probabilities

$p_{k}\coloneqq\frac{a^{K-(k+1)}}{S_{K}},\quad\text{where}\quad
S_{K}\coloneqq\sum_{k=0}^{K-1}a^{K-(k+1)}.$

Define a random variable $Y$ such that $Y=Y_{k}$ with probability $p_{k}$.
Then

$\mathbb{E}[Y]\leq\frac{a^{K}X_{0}-X_{K}}{S_{K}}+c\leq\frac{a^{K}}{S_{K}}X_{0}+c.$

###### Proof.

We start by multiplying the inequality $Y_{k}\leq aX_{k}-X_{k+1}+c$ by
$a^{K-(k+1)}$ for each $k$, yielding

$a^{K-(k+1)}Y_{k}\leq a^{K-k}X_{k}-a^{K-(k+1)}X_{k+1}+a^{K-(k+1)}c.$

Summing these inequalities for $k=0,1,\ldots,K-1$, we observe that many terms
cancel out in a telescopic fashion, leading to

$\sum_{k=0}^{K-1}a^{K-(k+1)}Y_{k}\leq
a^{K}X_{0}-X_{K}+\sum_{k=0}^{K-1}a^{K-(k+1)}c=a^{K}X_{0}-X_{K}+S_{K}c.$

Dividing both sides of this inequality by $S_{K}$, we get

$\sum_{k=0}^{K-1}p_{k}Y_{k}\leq\frac{a^{K}X_{0}-X_{K}}{S_{K}}+c,$

where the left-hand side represents $\mathbb{E}[Y]$. ∎

Building upon Lemma 4 and employing the inequality $1+x\leq e^{x}$, which is
valid for all $x\geq 0$, along with the fact that $S_{K}\geq K$, we can
further refine the bound:

$\frac{a^{K}}{S_{K}}\leq\frac{(1+(a-1))^{K}}{K}\leq\frac{e^{(a-1)K}}{K}.$ (23)

To mitigate the exponential growth observed in Eqn 23, we choose
$a=1+\gamma^{2}h$ for some $h>0$. Setting the step size as

$\gamma\leq\sqrt{\frac{\log 2}{hK}},$

ensures that $\gamma^{2}hK\leq\log 2$, leading to

$\frac{a^{K}}{S_{K}}\stackrel{{\scriptstyle\ref{eqn:exp_blowup}}}{{\leq}}\frac{e^{(a-1)K}}{K}\leq\frac{e^{\gamma^{2}hK}}{K}\leq\frac{2}{K}.$

Incorporating Lemma 4 into Eqn 22 and assuming a step size
$\gamma\leq\sqrt{\frac{\log 2}{hK}}$ for some $h>0$, we establish the
following result:

$\displaystyle\mathbb{E}\left[\|\nabla
f(w^{k})\|^{2}_{\operatorname{\overline{\mathbf{L}}}^{-1}\operatorname{\overline{\mathbf{W}}}\operatorname{\overline{\mathbf{L}}}^{-1}}\right]\leq\frac{4\Delta_{0}}{\gamma
K}.$ (24)