# Differential Privacy in Hierarchical Federated Learning: A Formal Analysis
and Evaluation

Frank Po-Chen Lin, and Christopher G. Brinton F. Lin and C. Brinton are with
the School of Electrical and Computer Engineering, Purdue University, IN, USA.
e-mail<EMAIL_ADDRESS>Lin and Brinton acknowledge support from ONR
grants N000142212305 and N000142112472.

###### Abstract

While federated learning (FL) eliminates the transmission of raw data over a
network, it is still vulnerable to privacy breaches from the communicated
model parameters. In this work, we formalize Differentially Private
Hierarchical Federated Learning (DP-HFL), a DP-enhanced FL methodology that
seeks to improve the privacy-utility tradeoff inherent in FL. Building upon
recent proposals for Hierarchical Differential Privacy (HDP), one of the key
concepts of DP-HFL is adapting DP noise injection at different layers of an
established FL hierarchy – edge devices, edge servers, and cloud servers –
according to the trust models within particular subnetworks. We conduct a
comprehensive analysis of the convergence behavior of DP-HFL, revealing
conditions on parameter tuning under which the model training process
converges sublinearly to a stationarity gap, with this gap depending on the
network hierarchy, trust model, and target privacy level. Subsequent numerical
evaluations demonstrate that DP-HFL obtains substantial improvements in
convergence speed over baselines for different privacy budgets, and validate
the impact of network configuration on training.

###### Index Terms:

Federated learning, edge intelligence, differential privacy, convergence
analysis, hierarchical architecture.

##  I Introduction

The concept of privacy has significantly evolved in the digital age,
particularly with regards to data collection, sharing, and utilization in
machine learning (ML) [1, 2, 3, 4, 5]. The ability to extract knowledge from
massive datasets is a double-edged sword; while it empowers ML algorithms, it
simultaneously exposes individuals’ sensitive information to potential misuse.
Therefore, it is crucial to develop ML methods that respect user privacy and
conform to robust data protection standards [6, 7, 8].

To this end, federated learning (FL) has emerged as an attractive paradigm for
distributing ML over networks, as it obviates the need to share raw data by
allowing for the model updates to occur directly on the edge devices where the
data originates [7, 9, 10, 11, 12, 13, 14]. Information transmitted over the
network is in the form of locally trained models for periodic aggregations at
a central server. Nonetheless, as promising as FL may be, it is not
invulnerable to privacy threats: it has been shown that adversaries with
access to model updates can reverse engineer and reconstruct sensitive device-
side data [15, 16, 17, 18].

This has motivated different threads of investigation on privacy preservation
within the FL framework. One common approach has been the introduction of
differential privacy (DP) mechanisms into FL [19, 20, 21, 22, 23, 24, 25]. DP
injects calibrated noise into the data or query responses to prevent the
leakage of individual-level information, offering a privacy-utility tradeoff.
In this work, we are interested in exploring and improving this tradeoff for
DP infusion over practical FL deployments.

###  I-A Related Work

The introduction of DP into FL has mainly followed two paradigms: (i) central
DP (CDP), involving noise addition at the main server [26, 27], and (ii) local
DP (LDP), which adds noise at each edge device [19, 21, 20, 21]. CDP generally
leads to a more accurate final model, but it hinges on the trustworthiness of
the main server. Conversely, LDP forgoes this trust requirement but requires a
higher level of noise addition at each device to compensate [28].

Oftentimes, the network system implementing FL will be hierarchical, i.e.,
with one or more layers of fog computing elements separating the edge devices
from the cloud server. Based on this, more recently, a third paradigm called
hierarchical DP (HDP) has been introduced [23]. HDP assumes that certain
“super-nodes” present within a hierarchy of computing nodes (e.g., edge
servers, intermediate routers, etc.) can be trusted [29] even if the main
server cannot. These super-nodes are entrusted with the task of adding
calibrated DP noise to the aggregated models prior to transmission. Instead of
injecting noise uniformly, HDP enables the tailoring of noise addition to the
varying levels of trust within the system.

There have been a few research efforts dedicated to integrating DP techniques
into hierarchical FL [22, 23, 30, 31]. Both Shi et al. [22] and Zhou [31]
adapted the LDP strategy to the hierarchical FL structure, utilizing moment
accounting to obtain strict privacy guarantees across the system. Wainakh et
al. [30] explored the advantages of flexible decentralized control over the
training process in hierarchical FL and examined its implications on
participant privacy. Chandrasekaran et al. [23] introduced the concept of HDP,
highlighting an opportunity for privacy amplification compared with LDP due to
properties of DP noise injected at the “super-node” level.

Despite these preliminary efforts, none have yet attempted to rigorously
characterize the convergence behavior of DP-infused hierarchical FL. Such
efforts are a crucial part of FL development in general, as they clarify the
evolution of models throughout the system and the rate at which satisfactory
accuracy can be achieved [32, 14]. In the case of HDP specifically, a formal
convergence analysis will offer more precise guidance on parameter selection
and the requisite noise injection for achieving a desired privacy-performance
balance.

Motivated by this, in this work, we fill this gap by formalizing
Differentially Private Hierarchical Federated Learning (DP-HFL), which
complements the flexible trust model of HDP with a comprehensive theoretical
analysis. In doing so, we will illuminate crucial elements necessary for
securing robust convergence guarantees in DP-enhanced hierarchical FL systems.
Owing to these factors, DP-HFL is capable of safeguarding privacy and
simultaneously mitigating the DP noise introduced, thereby enhancing the
efficiency of FL over hierarchical network structures.

###  I-B Outline and Summary of Contributions

  * •

We formalize DP-HFL to codify the impact of HDP trust models in hierarchical
FL (Sec. III). DP-HFL is designed to maintain a specific privacy level
throughout the entire training process, instead of only at individual
aggregations. We show that this allows for a more effective balance between
privacy preservation and model performance, addressing a key issue in privacy-
preserving ML.

  * •

We theoretically characterize the convergence behavior of DP-HFL, providing
insights for non-convex loss functions (Sec. IV). We quantify how factors such
as network configuration, data heterogeneity, and step sizes affect the
performance vs. privacy trade-off. Our analysis (culminating in Theorem 1)
shows that with careful parameter tuning, the cumulative average of the global
gradient can be guaranteed to converge sublinearly with rate
$\mathcal{O}(1/\sqrt{k})$.

  * •

Through numerical evaluations, we demonstrate that DP-HFL obtains substantial
improvements in convergence speed and trained model accuracy relative to
existing DP-based FL algorithms (Sec. V). Our results further corroborate the
impact of the network configuration and trust model on training performance in
our bounds.

##  II Preliminaries and System Model

This section introduces key DP concepts (Sec. II-A), presents our hierarchical
edge network system model (Sec.II-B), and formulates the target ML task
(Sec.II-C).

###  II-A Differential Privacy (DP)

Differential privacy (DP) characterizes a randomization technique according to
parameters $\epsilon,\delta$. Formally, a randomized mechanism $\mathcal{M}$
adheres to ($\epsilon$,$\delta$)-DP if it satisfies the following:

######  Definition 1 (($\epsilon$,$\delta$)-DP [33]).

For all datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$ differing in at most
one element, and for all $\mathcal{S}\subseteq\text{Range}(\mathcal{M})$, it
holds that:

$\displaystyle\Pr[\mathcal{M}(D)\in\mathcal{S}]\leq
e^{\epsilon}\Pr[\mathcal{M}(D^{\prime})\in\mathcal{S}]+\delta,$ (1)

where $\epsilon>0$ and $\delta\in(0,1)$.

$\epsilon$ represents the privacy budget, quantifying the degree of
uncertainty introduced in the privacy mechanism. Smaller $\epsilon$ implies a
stronger privacy guarantee. $\delta$ bounds the probability of the privacy
mechanism being unable to preserve the $\epsilon$-privacy guarantee.

Figure 1:  Three-layer hierarchical network architecture, with edge devices
grouped into two local subnets, $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$.
Devices $j\in\mathcal{S}_{1}$ are associated with the insecure edge server
$n_{1}\in\mathcal{N}_{U}$, while devices $j\in\mathcal{S}_{2}$ connect with
the secure edge server $n_{2}\in\mathcal{N}_{T}$.

Gaussian Mechanism: The Gaussian mechanism is a commonly employed
randomization mechanism compatible with $(\epsilon,\delta)$-DP. In the
Gaussian mechanism, noise sampled from a Gaussian distribution is introduced
to the output of the function being applied to the dataset. This function, in
the case of our learning algorithm, is the computation of gradients.

Formally, to maintain ($\epsilon$,$\delta$)-DP for any query function $f$
processed utilizing the Gaussian mechanism, the following inequality must be
satisfied:

$\displaystyle\Delta^{2}f\leq\frac{2log(1.25/\delta)}{\epsilon^{2}},$ (2)

where $\Delta f$ is the $L_{2}$-sensitivity of $f$, and $\epsilon$ and
$\delta$ are the privacy parameters. This relationship dictates the standard
deviation of the Gaussian noise introduced.

$L_{2}$ Sensitivity: The sensitivity of a function is a measure of how much
the output can change due to the modification of a single record in the input
dataset. Specifically, the $L_{2}$-sensitivity for a function $f$ is defined
as:

$\displaystyle\Delta
f=\max_{\mathcal{D},\mathcal{D}^{\prime}}\|f(\mathcal{D})-f(\mathcal{D}^{\prime})\|_{2},$
(3)

where $\|\cdot\|_{2}$ is the $L_{2}$ norm. In our setting, $L_{2}$ sensitivity
allows calibrating the amount of Gaussian noise to be added to ensure the
desired ($\epsilon$,$\delta$)-differential privacy in FL model training.

###  II-B Edge Network System Model

System Architecture: We consider the hierarchical network architecture
depicted in Fig. 1. The hierarchy, from bottom to top, consists of local edge
devices $\mathcal{I}=\\{1,\cdots,I\\}$, edge servers
$\mathcal{N}=\\{n_{1},\cdots,n_{N}\\}$, and the cloud server. The primary
responsibilities of these layers include local model training (edge devices),
local model aggregation (edge servers), and global model aggregation (cloud
server).

The edge devices are organized into $N$ subnets
$\\{\mathcal{S}_{c}\\}_{c=1}^{N}$, each of which is linked to a specific edge
server for up/downlink model transmissions. Each edge server
$n_{c}\in\mathcal{N}$ is associated with a distinct subnets $\mathcal{S}_{c}$.
We assume these subnets do not overlap, i.e.,
$\mathcal{S}_{c}\cap\mathcal{S}_{c^{\prime}}=\emptyset\leavevmode\nobreak\
\forall c\neq c^{\prime}$. The size of each subnet $\mathcal{S}_{c}$ is
denoted by $s_{c}=|\mathcal{S}_{c}|$, where the total number of devices is
$I=\sum_{c=1}^{N}s_{c}$. This topology can be extended to accommodate dynamic
scenarios such as mobile devices changing subnets.

Threat Model: We further categorize the set of edge servers $\mathcal{N}$ into
(i) secure/trusted edge servers $\mathcal{N}_{T}$ and (ii) insecure/untrusted
edge servers $\mathcal{N}_{U}$. We make no particular assumptions on how this
designation is made; for instance, a network operator may provide service
through a combination of its own infrastructure (trusted/secure) as well as
borrowed infrastructure (untrusted/insecure). With the exception of the
trusted edge servers, i.e., $n_{c}\in\mathcal{N}_{T}$, all participating
entities – namely, the edge devices, i.e., $i\in\mathcal{I}$, the untrusted
edge servers, i.e., $n_{c}\in\mathcal{N}_{U}$, and the cloud server – are
presumed to exhibit semi-honest behavior [34, 17, 18]. In particular, despite
adhering to the hierarchical FL protocol, there is a possibility that these
semi-honest entities may seek to extract sensitive information from the shared
datasets.

###  II-C Machine Learning Model

Each edge device $i\in\mathcal{I}$ has a dataset $\mathcal{D}_{i}$ comprised
of $D_{i}=|\mathcal{D}_{i}|$ data points. Typically, the datasets
$\mathcal{D}_{i}$ exhibit non-i.i.d characteristics, implying statistical
variations across devices.

The loss $\ell(d;\mathbf{w})$ quantifies the fit of the ML model in relation
to the ML task at hand. This value is linked to a data point
$d\in\mathcal{D}_{i}$ and depends on the ML model parameter vector
$\mathbf{w}\in\mathbb{R}^{M}$ (with $M$ representing the model’s dimension).
Consequently, the local loss function for device $i$ is:

$\displaystyle
F_{i}(\mathbf{w})=\frac{1}{D_{i}}\sum\limits_{(\mathbf{x},y)\in\mathcal{D}_{i}}\ell(\mathbf{x},y;\mathbf{w}).$
(4)

Next, the subnet loss function for each $\mathcal{S}_{c}$ represents the
average loss experienced by devices in that subnet:

$\displaystyle\bar{F}_{c}(\mathbf{w})=\sum\limits_{i\in\mathcal{S}_{c}}\rho_{i,c}F_{i}(\mathbf{w}),$
(5)

Here, $\rho_{i,c}=1/s_{c}$ symbolizes the relative weight of edge device
$i\in\mathcal{S}_{c}$ within its subnet. The global loss function, in
contrast, computes the average loss across all subnets:

$\displaystyle
F(\mathbf{w})=\sum\limits_{c=1}^{N}\varrho_{c}\bar{F}_{c}(\mathbf{w}),$ (6)

where the weight associated with each subnet $\mathcal{S}_{c}$, relative to
the entire network, is defined by $\varrho_{c}=1/N$.

The primary objective of ML model training is to pinpoint the optimal global
model parameter vector $\mathbf{w}^{*}\in\mathbb{R}^{M}$ such that
$\mathbf{w}^{*}=\mathop{\operatorname*{arg\,min}_{\mathbf{w}\in\mathbb{R}^{M}}}F(\mathbf{w}).$

##  III Proposed Methodology

In this section, we formalize DP-HFL, including its operation timescales (Sec.
III-A), training process (Sec. III-B), and DP mechanism (Sec. III-C).

Figure 2: Illustration of the learning timescales in DP-HFL. In this example,
$t=\tau_{1}+m_{1}$ marks local aggregation in subnet $\mathcal{S}_{c}$ linked
to insecure edge server $n_{c}\in\mathcal{N}_{U}$, while $t=\tau_{1}+m_{2}$
denotes local aggregation in subnet $\mathcal{S}_{c^{\prime}}$ connected to
secure edge server $n_{c^{\prime}}\in\mathcal{N}_{T}$.

###  III-A Model Training Timescales

Our methodology utilizes a network depicted in slotted-time representation,
depicted in Fig. 2. Each edge device carries out a local model training
iteration via stochastic gradient descent (SGD) at each time index
$t=0,1,\cdots,T$. The duration from $0$ to $T$ is divided into multiple local
model training intervals, denoted by $k=0,1,\cdots,K_{g}-1$. Each interval,
$\mathcal{T}_{k}=\\{t_{k}+1,...,t_{k+1}\\}\subset\\{0,1,\cdots,T\\}$, is of
length $\tau_{k}=|\mathcal{T}_{k}|$.

DP-HFL begins with the cloud server broadcasting the initial global model
$\bar{\mathbf{w}}^{(0)}$ to all devices at $t_{0}=0$. Local training interval
$k$ is book-ended by global aggregations at times $t_{k}$ and $t_{k+1}$. For
$t\in\mathcal{T}_{k}$, each edge device applies SGD iterations on its local
data to minimize its loss function $F_{i}(\cdot)$. Simultaneously, edge server
$c$ performs intermittent local aggregations at times
$t\in\mathcal{T}^{\mathsf{L}}_{k,c}$, where
$\mathcal{T}^{\mathsf{L}}_{k,c}\subset\mathcal{T}_{k}$ with length
$K_{k,c}=|\mathcal{T}^{\mathsf{L}}_{k,c}|$ is the set of instances of local
aggregations for subnet $c$ in interval $k$.

###  III-B DP-HFL Training and Aggregations

We now proceed to formalize the processes of local training, local model
aggregations, and global aggregation.

Local Stochastic Gradient: At time $t\in\mathcal{T}_{k}$, device $i$ randomly
selects a mini-batch $\xi_{i}^{(t)}$ from its local dataset $\mathcal{D}_{i}$.
Using this mini-batch, it calculates the unbiased stochastic gradient estimate
based on its preceding local model $\mathbf{w}_{i}^{(t)}$:

$\displaystyle\widehat{\mathbf{g}}_{i}^{(t)}=\frac{1}{|\xi_{i}^{(t)}|}\sum\limits_{(\mathbf{x},y)\in\xi_{i}^{(t)}}\nabla\ell(\mathbf{x},y;\mathbf{w}_{i}^{(t)}).$
(7)

We assume a uniform selection probability $q$ of each data point, i.e.,
$q=|\xi_{i}^{(t)}|/D_{i},\leavevmode\nobreak\ \forall i$.

Provisional Updated Local Model: Devices employ
$\widehat{\mathbf{g}}_{i}^{(t-1)}$ to determine their provisional updated
local model ${\widetilde{\mathbf{w}}}_{i}^{(t)}$:

$\displaystyle{\widetilde{\mathbf{w}}}_{i}^{(t)}=\mathbf{w}_{i}^{(t-1)}-\eta_{k}\widehat{\mathbf{g}}_{i}^{(t-1)},\leavevmode\nobreak\
t\in\mathcal{T}_{k},$ (8)

Here, $\eta_{k}>0$ signifies the step size. Using
${\widetilde{\mathbf{w}}}_{i}^{(t)}$ as the base, the final updated local
model $\mathbf{w}_{i}^{(t)}$ is determined in one of several ways depending on
the trust model, described next.

Local model update: If a subnet $\mathcal{S}_{c}$ does not perform a local
aggregation at a specific time $t$, i.e.,
$t\in\mathcal{T}_{k}\setminus\mathcal{T}^{\mathsf{L}}_{k,c}$, the updated
model follows ${{\mathbf{w}}}_{i}^{(t)}={\widetilde{\mathbf{w}}}_{i}^{(t)}$ in
(8). On the other hand, if $t\in\mathcal{T}^{\mathsf{L}}_{k,c}$ there are two
possibilities:

(i) Subnets with secure edge servers: In this case, each device $i$ within
subnet $\mathcal{S}_{c}$ sends its accumulated local stochastic gradients
since the last local aggregation, denoted as
$\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}$ to edge
server $n_{c}$, with no additional noise attached. The edge server computes
the local aggregated model $\bar{\mathbf{w}}_{c}^{(t)}$ by determining the
weighted average of the aggregated gradients across all edge devices within
the same subnet, followed by integrating DP noise
$\widetilde{\mathbf{n}}_{c,Loc}^{(t)}\sim\mathcal{N}(0,\bar{\sigma}_{c,Loc}^{2}\mathbf{I}_{M}),\leavevmode\nobreak\
\forall c$. The edge server adjusts the prior local aggregated model
$\bar{\mathbf{w}}_{c}^{(t^{\prime})}$ as follows:

$\displaystyle\bar{\mathbf{w}}_{c}^{(t)}=\bar{\mathbf{w}}_{c}^{(t^{\prime})}-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}+\bar{\mathbf{n}}_{c,Loc}^{(t)},$
(9)

where $t^{\prime}\in\mathcal{T}^{\mathsf{L}}_{k,c}$ is the time index of the
previous aggregation.

(ii) Subnets with insecure edge servers: Conversely, if edge server $n_{c}$ is
considered untrustworthy, device $i$ within subnet $\mathcal{S}_{c}$ injects
DP noise
$\mathbf{n}_{i,Loc}^{(t)}\sim\mathcal{N}(0,\sigma_{i,Loc}^{2}\mathbf{I}_{M})$
within its transmission to edge server $n_{c}$. Upon receipt of the noisy
accumulated gradients, the server computes the local aggregated model
$\bar{\mathbf{w}}_{c}^{(t)}$ by determining the weighted average of the noisy
summed gradients across edge devices in the same subnet. This noisy
accumulated gradient is subsequently employed to refresh the previous local
aggregated model $\bar{\mathbf{w}}_{c}^{(t^{\prime})}$:

$\displaystyle\bar{\mathbf{w}}_{c}^{(t)}=\bar{\mathbf{w}}_{c}^{(t^{\prime})}-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}+\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j,Loc}^{(t)}.$
(10)

Combining with (8), the local aggregation process can be generalized as
follows:

$\bar{\mathbf{w}}_{c}^{(t)}=\sum_{i\in\mathcal{S}_{c}}\rho_{i,c}\tilde{\mathbf{w}}_{i}^{(t)}+\bar{\mathbf{n}}_{c,Loc}^{(t)},$
(11)

where

$\displaystyle\bar{\mathbf{n}}_{c,Loc}^{(t)}=\begin{cases}\widetilde{\mathbf{n}}_{c,Loc}^{(t)},&n_{c}\in\mathcal{N}_{T},\\\
\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j,Loc}^{(t)},&n_{c}\in\mathcal{N}_{U}.\end{cases}$
(12)

Finally, after computing the local aggregated model, the edge server $n_{c}$
broadcasts $\bar{\mathbf{w}}_{c}^{(t)}$ across its subnet. The devices
subsequently obtain their final updated models with local aggregation as
${{\mathbf{w}}}_{i}^{(t)}=\bar{\mathbf{w}}_{c}^{(t)},i\in\mathcal{S}_{c}$.

Following the process described above, a general rule for local model updates
at each device $i\in\mathcal{S}_{c}$ can be established

$\displaystyle\mathbf{w}_{i}^{(t)}=(1-\Theta_{c}^{(t)})\widetilde{\mathbf{w}}_{i}^{(t)}+\Theta_{c}^{(t)}\bar{\mathbf{w}}_{c}^{(t)},\leavevmode\nobreak\
\forall t\in\mathcal{T}_{k},$ (13)

where ${\Theta_{c}^{(t)}}=1$ if $t\in\mathcal{T}^{\mathsf{L}}_{k,c}$, and
${\Theta_{c}^{(t)}}=0$ otherwise, serves as an indicator for local aggregation
at time $t$.

Input: Length of training $T$, number of global aggregations $K_{g}$, length
of local aggregation periods $m_{k}$, length of local model training intervals
$\tau_{k}$, learning rates $\eta_{k}$, minibatch sizes $|\xi_{i}^{(t)}|$

Output: Final global model $\bar{\mathbf{w}}^{(T)}$

1 Initialize $\bar{\mathbf{w}}^{(0)}$ and broadcast it across edge servers and
devices, resulting in
$\bar{\mathbf{w}}_{c}^{(0)}=\bar{\mathbf{w}}^{(0)},\leavevmode\nobreak\
\forall c$ and $\mathbf{w}_{i}^{(0)}=\bar{\mathbf{w}}^{(0)}$,
$i\in\mathcal{I}$.

2 for  _$k=0:K_{g}-1$_ do

3 for  _$t=t_{k}+1:t_{k+1}$_ do

4 for  _$c=1:N$_ do // Procedure at each subnet $\mathcal{S}_{c}$

5 Local SGD update with:
$\widetilde{\mathbf{w}}_{i}^{(t)}=\mathbf{w}_{i}^{(t-1)}-\eta_{t-1}\widehat{\mathbf{g}}_{i}^{(t-1)}$;

6 if  _$t\in\mathcal{T}^{\mathsf{L}}_{k,c}$_ then

7 if  _$n_{c}\in\mathcal{N}_{T}$_ then

8 Edge device $i$ sends accumulated gradients
$\eta_{k}\sum_{\ell=t-m_{k}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}$ via uplink
transmission;

9 Edge server $n_{c}$ conducts local aggregation with:
$\bar{\mathbf{w}}_{c}^{(t)}=\bar{\mathbf{w}}_{c}^{(t-m_{k})}-\eta_{k}\sum\limits_{\ell=t-m_{k}}^{t}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}+\widetilde{\mathbf{n}}_{c,Loc}^{(t)}$
and $\mathbf{w}_{i}^{(t)}=\bar{\mathbf{w}}_{c}^{(t)}$;

10

11 else

12 Edge device $i$ sends noisy accumulated gradients
$\eta_{k}\sum_{\ell=t-m_{k}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}+\mathbf{n}_{i,Loc}^{(t)}$
via uplink transmission;

13 Edge server conducts local aggregation with:
$\bar{\mathbf{w}}_{c}^{(t)}=\bar{\mathbf{w}}_{c}^{(t-m_{k})}-\eta_{k}\sum\limits_{\ell=t-m_{k}}^{t}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}+\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j,Loc}^{(t)}$
and $\mathbf{w}_{i}^{(t)}=\bar{\mathbf{w}}_{c}^{(t)}$;

14

15 end if

16

17 else

18 $\mathbf{w}_{i}^{(t)}=\widetilde{\mathbf{w}}_{i}^{(t)}$.

19 end if

20

21 end for

22 if  _$t=t_{k+1}$_ then

23 for  _$c=1:N$_ do // Procedure at each subnet $\mathcal{S}_{c}$

24 if  _$n_{c}\in\mathcal{N}_{T}$_ then

25 Edge device $i$ sends accumulated gradients
$\eta_{k}\sum_{\ell=t-m_{k}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}$ via uplink
transmission;

26 Edge server $n_{c}$ computes and sends
$\eta_{k}\sum\limits_{\ell=t-m_{k}}^{t}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}+\widetilde{\mathbf{n}}_{c,Glob}^{(t)}$
via uplink transmission;

27

28 else

29 Edge device $i$ sends noisy accumulated gradients
$\eta_{k}\sum_{\ell=t-m_{k}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}+\mathbf{n}_{i,Glob}^{(t)}$
via uplink transmission;

30 Edge server computes and sends
$\eta_{k}\sum\limits_{\ell=t-m_{k}}^{t}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}+\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j,Glob}^{(t)}$
via uplink transmission;

31

32 end if

33

34 end for

35 Main server performs global aggregation via (III-B) and downlink broadcast;

36

37

38 end for

39

40 end for

Algorithm 1 Overall DP-HFL procedure.

Global model aggregation: At the end of each local model training interval
$\mathcal{T}_{k}$, i.e., at $t=t_{k+1}$, the global aggregation occurs. Once
again, devices handle this process according to their subnet security model:

(i) Subnets with secure edge servers: Devices within trusted subnets transmit
their accumulated local stochastic gradients since the last global aggregation
without the addition of extra noise. These edge servers then calculate the
weighted average of these aggregated gradients across all devices within the
same subnet. Following this, they incorporate a differentially private noise
$\widetilde{\mathbf{n}}_{c,Glob}^{(t)}\sim\mathcal{N}(0,\bar{\sigma}_{c,Glob}^{2}\mathbf{I}_{M}),\leavevmode\nobreak\
\forall c$, and dispatch this information to the main server.

(ii) Subnets with insecure edge servers: In the case of untrusted subnets,
each device sends out its cumulative local stochastic gradients from the last
local aggregation, but with an added DP noise
$\mathbf{n}_{i,Glob}^{(t)}\sim\mathcal{N}(0,\sigma_{i,Glob}^{2}\mathbf{I}_{M}),\leavevmode\nobreak\
\forall i$. Upon reception, the edge servers determine the weighted average of
these gradients across devices within the same subnet and relay this to the
main server.

Subsequently, the main server constructs the global model. After computing the
weighted average of the noisy accumulated gradients that have been received
from the edge servers, the full expression for the updated global model is:

$\displaystyle\bar{\mathbf{w}}^{(t_{k+1})}$
$\displaystyle=\bar{\mathbf{w}}^{(t_{k})}-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}$
$\displaystyle+\sum\limits_{\ell\in\mathcal{T}^{\mathsf{L}}_{k,c}}\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Loc}^{(\ell)}+\bar{\mathbf{n}}_{Glob}^{(t_{k+1})},$
(14)

Upon completion of the calculations at the main server, the resulting global
model $\bar{\mathbf{w}}^{(t_{k+1})}$ is employed to synchronize the local
models maintained by the edge devices.

###  III-C DP Mechanisms

We now dictate the procedure for configuring the DP noise variables
$\widetilde{\mathbf{n}}_{c,Loc}^{(t)}$ and
$\widetilde{\mathbf{n}}_{c,Glob}^{(t)}$ introduced by the edge server, along
with $\mathbf{n}_{i,Loc}^{(t)}$ and $\mathbf{n}_{i,Glob}^{(t)}$ incorporated
by the edge devices. In this study, we focus on the Gaussian mechanisms from
Sec. II-A, though DP-HFL can be adjusted to accommodate other DP mechanisms
too.

As stated by the composition rule of DP [33], the design of the DP mechanism
needs to take into account the privacy budget across all aggregations
throughout the training, to ensure cumulative privacy for the complete model
training process, rather than considering each individual aggregation in
isolation. Below, we define the Gaussian mechanisms, incorporating the moment
accountant technique. These mechanisms utilize (20) from Assumption 2 which is
stated in Sec. IV.

######  Proposition 1 (Gaussian Mechanism [35]).

Under Assumption 2, there exists constants $c_{1}$ and $c_{2}$ such that given
the data sampling probability $q$ at each device, and the total number of
aggregations $L$ conducted during the entire model training process in DP-HFL,
for any $\epsilon<c_{1}qL$, Algorithm 1 exhibits
$(\epsilon,\delta)$-differential privacy for any $\delta>0$, so long as the DP
noise follows a distribution
$\mathbf{n}_{DP}^{(t)}\sim\mathcal{N}(0,\sigma_{DP}^{2}\mathbf{I}_{M})$, where

$\displaystyle\sigma_{DP}=c_{2}\frac{q\Delta\sqrt{L\log(1/\delta)}}{\epsilon}.$
(15)

$\Delta$ represent the $L_{2}$-norm sensitivity of the gradients exchanged
during the aggregations.

The characteristics of the DP noises introduced during local and global
aggregations can be established using Proposition 1. The relevant $L_{2}$-norm
sensitivities can be established through the following lemma:

######  Lemma 1.

Under Assumption 2, the $L_{2}$-norm sensitivity of the exchanged gradients
during local aggregations can be obtained as follows:

$\displaystyle\bar{\Delta}_{c,Loc}$
$\displaystyle=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\left(\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\right)\Big{\|}$
$\displaystyle=2\eta_{k}\tau_{k}G/s_{c},$ (16)
$\displaystyle\Delta_{i,Loc}=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=2\eta_{k}\tau_{k}G.$
(17)

Similarly, the $L_{2}$-norm sensitivity of the exchanged gradients during
global aggregations can be obtained as follows:

$\displaystyle\bar{\Delta}_{c,Glob}$
$\displaystyle=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\left(\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\right)\Big{\|}$
$\displaystyle=2\eta_{k}\tau_{k}G/s_{c},$ (18)
$\displaystyle\Delta_{i,Glob}=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=2\eta_{k}\tau_{k}G.$
(19)

###### Proof.

See Lemma 1 in Appendix C. ∎

Then, in subnets with secure edge servers, $\bar{\sigma}_{c,Loc}$ can be
determined based on Proposition 1 and Lemma 1 by setting $L=\ell_{c}$ and
$\Delta=\bar{\Delta}_{c,Loc}$, where $\ell_{c}=\sum_{k=0}^{K-1}K_{k,c}$
represents the total number of local aggregations performed. Similarly,
$\bar{\sigma}_{c,Glob}$ can be determined by setting $L=K_{g}$ and
$\Delta=\bar{\Delta}_{c,Glob}$. Conversely, in subnets with insecure edge
servers, $\sigma_{i,Loc}$ can be determined by setting $L=\ell_{c}$ and
$\Delta_{DP}=\Delta_{i,Loc}$. Likewise, $\sigma_{i,Glob}$ can be calculated by
setting $L=K_{g}$ and $\Delta=\Delta_{i,Glob}$.

The full DP-HFL procedure is summarized in Algorithm 1.

##  IV Convergence Analysis

###  IV-A Analysis Assumptions

We first establish a few general and commonly employed assumptions that we
will consider throughout our analysis.

######  Assumption 1 (Characteristics of Noise in SGD [9, 20, 36, 37]).

Consider ${\mathbf{n}}_{i}^{(t)}=\widehat{\mathbf{g}}_{i}^{(t)}-\nabla
F_{i}(\mathbf{w}_{i}^{(t)})$ as the noise of the gradient estimate through the
SGD process for device $i$ at time $t$. Given that
$\mathbb{E}_{t}[{\mathbf{n}}_{i}^{(t)}]=\bm{0}$, the noise variance is upper
bounded by $\sigma^{2}>0$ such that
$\mathbb{E}_{t}[\|{\mathbf{n}}_{i}^{(t)}\|^{2}]\leq\sigma^{2}\leavevmode\nobreak\
\forall i,t$.

######  Assumption 2 (General Characteristics of Loss Functions [20],[36],
[37]).

Assumptions applied to loss functions include:

  * •

Bounded gradient: The stochastic gradient norm of loss function $\ell(\cdot)$
is bounded by a constant, i.e.,

$\displaystyle\|\widehat{\mathbf{g}}_{i}^{(t)}\|\leq$ $\displaystyle
G,\leavevmode\nobreak\ \forall i,t.$ (20)

  * •

Smoothness: Each local loss function $F_{i}$ is $\beta$-smooth $\forall
i\in\mathcal{I}$, i.e.,

$\|\nabla F_{i}(\mathbf{w}_{1})-\nabla
F_{i}(\mathbf{w}_{2})\|\leq\beta\|\mathbf{w}_{1}-\mathbf{w}_{2}\|,\leavevmode\nobreak\
\forall\mathbf{w}_{1},\mathbf{w}_{2}\in\mathbb{R}^{M},$

(21)

where $\beta>\mu$. These assumptions imply the $\beta$-smoothness of
$\bar{F}_{c}$ and $F$ as well.

  * •

Inter-Subnet Gradient Diversity: The inter-subnet gradient diversity across
the device subnets is measured via a non-negative constant $\zeta$ such that

$\displaystyle\left\|\nabla\bar{F}_{c}(\mathbf{w})-\nabla
F(\mathbf{w})\right\|\leq\zeta,\leavevmode\nobreak\ \forall c,\mathbf{w}.$
(22)

  * •

Intra-Subnet Gradient Diversity: The intra-subnet gradient diversity across
the devices belonging to subnet $\mathcal{S}_{c}$ is measured via a non-
negative constant $\zeta_{c}$ such that

$\displaystyle\left\|\nabla
F_{i}(\mathbf{w})-\nabla\bar{F}_{c}(\mathbf{w})\right\|\leq\zeta_{c},\leavevmode\nobreak\
\forall i\in\mathcal{S}_{c},\leavevmode\nobreak\ \forall c,\mathbf{w}.$ (23)

###  IV-B Preliminary Quantities and Results

Before proceeding to our main result in Sec. IV-C, we establish a few
quantities and lemmas to facilitate our analysis.

Auxiliary models. We define the auxiliary local aggregated model as

$\bar{\mathbf{w}}_{c}^{(t+1)}=\bar{\mathbf{w}}_{c}^{(t)}-\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(t)}+\Theta_{c}^{(t+1)}\bar{\mathbf{n}}_{c,Loc}^{(t+1)},\leavevmode\nobreak\
\forall t\in\mathcal{T}_{k}\setminus{\\{t_{k}\\}}.$

(24)

Similarly, we define a auxiliary global model within each local model training
interval preceding the global aggregation as:

$\displaystyle\bar{\mathbf{w}}^{(t+1)}=$
$\displaystyle\bar{\mathbf{w}}^{(t)}-\eta_{k}\sum_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(t)}$
$\displaystyle+\sum_{c=1}^{N}\varrho_{c}\Theta_{c}^{(t+1)}\bar{\mathbf{n}}_{c,Loc}^{(t+1)},\leavevmode\nobreak\
\forall t\in\mathcal{T}_{k}\setminus{\\{t_{k}\\}}.$ (25)

The auxiliary global model at the instant of global aggregation is then given
by:

$\displaystyle\bar{\mathbf{w}}^{(t_{k+1})}=\widetilde{\mathbf{w}}^{(t_{k+1})}+\Theta_{c}^{(t_{k+1})}\bar{\mathbf{n}}_{Glob}^{(t_{k+1})}.$
(26)

Here, $\widetilde{\mathbf{w}}^{(t_{k+1})}$ is the auxiliary global model just
before global aggregation, distinguishing it from
$\bar{\mathbf{w}}^{(t_{k+1})}$, which is defined immediately post global
aggregation. We employ the term “auxiliary” because
$\bar{\mathbf{w}}_{c}^{(t)}$ is only realized at the edge server upon
performing a local aggregation at $t\in\mathcal{T}_{k,c}^{\mathsf{L}}$.
Similarly, $\bar{\mathbf{w}}^{(t)}$ is realized upon executing global
aggregations at $t=t_{k+1},\leavevmode\nobreak\ \forall k$.

Edge server security probability. We consider a generic probability $p_{c}$
that each subnet is associated with a secure edge server and a probability
$1-p_{c}$ that it is associated with an insecure one. Consequently,
$\bar{\mathbf{n}}_{c,Loc}^{(t)}$ is a mixture distribution:

$\displaystyle\bar{\mathbf{n}}_{c,Loc}^{(t)}=\begin{cases}\widetilde{\mathbf{n}}_{c,Loc}^{(t)},&\text{with
probability }p_{c},\\\
\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j,Loc}^{(t)},&\text{with
probability }1-p_{c}.\end{cases}$ (27)

For ease of presentation, we assume that $K_{k,c}=K_{\ell}$ (representing the
number of local aggregations within $\mathcal{T}_{k}$) and $\tau_{k}=\tau$
(denoting the duration of the local model training interval) for all $k$.

Model dispersion. We next introduce a series of terms that encapsulate model
characteristics within and across subnets.

####  IV-B1 Expected Intra-Subnet Model Dispersion

$\displaystyle
Z_{1}^{(t)}\triangleq\mathbb{E}\bigg{[}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\|\mathbf{w}_{i}^{(t)}-\bar{\mathbf{w}}_{c}^{(t)}\|^{2}\bigg{]}.$
(28)

$Z_{1}^{(t)}$ captures the average deviation error of local models
$\mathbf{w}_{i}^{(t)}$ within a subnet from the local aggregated model
$\bar{\mathbf{w}}_{c}^{(t)}$.

####  IV-B2 Expected Inter-Subnet Model Dispersion

$\displaystyle
Z_{2}^{(t)}\triangleq\mathbb{E}\bigg{[}\sum\limits_{c=1}^{N}\varrho_{c}\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}\bigg{]}.$
(29)

$Z_{2}^{(t)}$ measures the degree to which the local aggregated model
$\bar{\mathbf{w}}_{c}^{(t)}$ deviates from the global model
$\bar{\mathbf{w}}^{(t)}$ during the local model training interval.

######  Lemma 2 (One-step behavior of intra/inter subnet model deviation).

For $t\in\mathcal{T}_{k}\setminus\\{t_{k+1}\\}$, under Assumptions 1 and 2,
using DP-HFL for ML model training, the one-step behavior of
$\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\|^{2}]}$ and
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|]^{2}}$
can be expressed as

$\displaystyle\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}\leq(1-\Theta_{c}^{(t+1)})\bigg{[}(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\big{\|}^{2}]}$
$\displaystyle+\eta_{k}\beta\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\|^{2}]}+\eta_{k}(2\sigma+\zeta_{c})\bigg{]},$
(30)

and

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}\beta\sum\limits_{d=1}^{N}\varrho_{d}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{d}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}+\eta_{k}(2\beta\max_{t\in\mathcal{T}_{k}}Z_{1}^{(t)}+2\sigma+\zeta)$
$\displaystyle+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\Theta_{c}^{(t+1)}\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}.$
(31)

###### Proof.

See Lemma 2 in Appendix C. ∎

Lemma 2 elucidates the one-step dynamics of
$\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}$ and
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}$
within a local model training interval at $t$. These upper bounds indicate a
complex interplay between
$\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}$ and
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}$
when local model updates are conducted within DP-HFL. Specifically, when local
aggregation is carried out, $\Theta_{c}^{(t+1)}=1$, thus bringing
$\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}=0$. While this in
part decreases
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}$
by reducing the values of $Z_{1}^{(t)}$, it simultaneously inflates it due to
the injection of DP noise.

This result leads us to the following proposition:

######  Proposition 2.

For $t\in\mathcal{T}_{k}\setminus\\{t_{k+1}\\}$, under Assumptions 1 and 2, if
$\eta_{k}\leq\frac{1}{\max\\{\tau,K_{g}\\}\beta}$, using DP-HFL for ML model
training, the subnet model dispersion can be bounded as

$\displaystyle Z_{1}^{(t)}\leq\eta_{k}\tau B_{1}^{2},\qquad
Z_{2}^{(t)}\leq\eta_{k}\tau B_{2}^{2},$ (32)

where
$B_{1}^{2}=(2\sigma+\zeta_{c})^{2}\Big{(}(1+2\eta_{0}\beta)^{\tau-1}+1\Big{)}^{2},$
$B_{2}^{2}=(1+\eta_{0}\beta)^{2(\tau-1)}\sum\limits_{c=1}^{N}\varrho_{c}\Phi_{c}^{2},$
and

$\displaystyle\Phi_{c}=$ $\displaystyle\bigg{[}\frac{2\tau
Gq\sqrt{MK_{\ell}\log(\frac{1}{\delta})}}{\varepsilon
N}\bigg{(}\sqrt{\sum\limits_{c=1}^{N}\Big{(}p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}\Big{)}}$
$\displaystyle+N\sqrt{p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}}\bigg{)}+2B_{1}^{2}+2\sigma+\zeta\bigg{]}$
$\displaystyle\times\Big{(}(1+2\eta_{0}\beta)^{\tau-1}+1\Big{)}+2B_{1}^{2}+2\sigma+\zeta.$

###### Proof.

See Appendix B. ∎

Proposition 2 offers a viewpoint on how subnet configuration impacts the
convergence trajectory of the model training process, by establishing bounds
on the subnet deviation parameters, $Z_{1}^{(t)}$ and $Z_{2}^{(t)}$. It
highlights how SGD noise and intra-subnet data diversity, encapsulated within
$B_{1}$ and $B_{2}$, influence the bounds. Specifically, it indicates an
upward shift in the bound correlating with the increment of $\sigma$,
$\zeta_{c}$, and $\zeta$.

Moreover, the proposition indicates that the network size, both in terms of
individual subnet size, i.e., $s_{c}$, and total number of subnets, i.e., $N$,
significantly influences these bounds and, in turn, model convergence
dynamics. In particular, it reveals an inverse relationship between network
size and these bounds: a larger network results in the need for less DP noise
injection, which in turn results in a decrease in model dispersion.

Furthermore, Proposition 2 illustrates that the progression of the upper
bounds of $Z_{1}^{(t)}$ and $Z_{2}^{(t)}$ across sequential global
synchronization stages is proportional to the step size. This relationship
with the step size is instrumental in steering the convergence pattern of the
global model within the DP-HFL framework, which we establish next.

###  IV-C General Convergence Behavior of DP-HFL

We now present our main result, that the cumulative average of the global loss
gradient attains sublinear convergence.

######  Theorem 1.

Under Assumptions 1 and 2, upon using DP-HFL for ML model training, if
$\eta_{k}=\frac{\gamma}{\sqrt{k+1}}$ with
$\gamma\leq\min\\{\frac{1}{\tau},\frac{1}{K_{g}}\\}$, the cumulative average
of global loss gradients satisfies

$\displaystyle\frac{1}{K_{g}}\sum\limits_{k=0}^{K_{g}-1}\mathbb{E}[\|\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\|^{2}]\leq\underbrace{2\gamma\frac{F(\bar{\mathbf{w}}^{(0)})-F(\mathbf{w}^{*})}{\tau\sqrt{K_{g}+1}}}_{(a_{1})}$
$\displaystyle+\underbrace{\frac{\beta\gamma}{\sqrt{K_{g}+1}}\left[\beta\tau\left(B_{1}^{2}+B_{2}^{2}\right)+G^{2}+\tau\sigma^{2}\right]}_{(a_{2})}$
$\displaystyle+\underbrace{\frac{4\tau(K_{\ell}^{3}+1)Mq^{2}G^{2}\log(1/\delta)}{N^{2}\varepsilon^{2}}\sum\limits_{c=1}^{N}\Big{(}p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}\Big{)}}_{(b)}.$
(33)

###### Proof.

See Appendix A. ∎

The dual nature of noise injection creates a delicate balance between privacy
conservation and model performance. Specifically, as the number of global
aggregations ($K_{g}$) increases, (a1) and (a2) in (1) decrease, while the
overall noise level, embodied by (b), escalates. As suggested by Proposition 1
and Lemma 1, the variance of the DP noise inserted should scale with the total
count of global aggregations, $K_{g}$. To counterbalance the influence of DP
noise accumulation over successive aggregations, we enforce the condition
$\eta_{k}\leq 1/K_{g}$ to scale down the DP noise by a factor of $K_{g}$. This
strategy steers the bound in (1) towards a stable state, denoted by (b),
rather than allowing for constant amplification. At the same time, this
highlights a trade-off between privacy preservation and model performance:
although the condition $\eta_{k}\leq 1/K_{g}$ serves to reduce DP noise, it
simultaneously impacts the convergence velocity of DP-HFL.

In addition, (b) conveys the beneficial influence of secure edge servers. With
a heightened presence of these servers (indicated by a larger $p_{c}$), the
noise level introduced during aggregations is reduced by a factor of
$1/s_{c}^{2}$. This is in contrast to a factor of $1/s_{c}$ for the noise
introduced at insecure edge servers, resulting in an additional noise
reduction by a factor of $s_{c}$. This reduction underscores the rationale
behind the integration of HDP within a hierarchical network structure,
allowing for an effective reduction in the requisite DP noise for preserving a
given privacy level. Consequently, in comparison with hierarchical FL
implementing the LDP strategy [22] – tantamount to setting
$p_{c}=0,\leavevmode\nobreak\ \forall c$ in (1) – DP-HFL noticeably suppresses
the noise impact by an extra factor of $1/s_{c}$. Further, if both $p_{c}=0$
and $B_{1}=0$, the bound reduces to LDP in the non-hierarchical, star-topology
FL system.

Lastly, the network size, represented by the number of subnets $N$ and the
size of each subnet $s_{c}$, is inversely related to the DP noise needed to
uphold a specific privacy level. Specifically, a rise in either $N$ or $s_{c}$
sees (b) decrease.

##  V Experimental Evaluation

Figure 3: Performance comparison between DP-HFL, the HFL-DP baseline from
[22], and an upper bound established by hierarchical FedAvg without DP. We see
that DP-HFL significantly outperforms HFL-DP and is able to leverage trusted
edge servers effectively.

###  V-A Simulation Setup

For numerical experiments, we consider a network of $50$ edge devices evenly
distributed across $10$ subnets. We use two commonly employed datasets for
image classification tasks: the Fashion-MNIST (F-MNIST) and CIFAR-10. Each of
these datasets contains $10$ labels. F-MNIST features 70K images in total, 60K
of which are earmarked for training and the remaining 10K for testing.
Conversely, CIFAR-10 contains a total of 60K images, split into 50K for
training purposes and 10K for testing. Following prior work [12, 9], the
training samples from each dataset are distributed across the edge devices in
a non-i.i.d manner, in which each device exclusively contains datapoints from
$3$ out of $10$ labels, inducing a degree of statistical heterogeneity amongst
the devices.

Our performance evaluation of DP-HFL involves deploying it on convolutional
neural networks (CNNs) accompanied by a softmax function and cross-entropy
loss. The model dimension is set to $M=7840$. This evaluation setup provides
insight into DP-HFL’s performance when handling non-convex loss functions, as
exhibited by CNNs. Lastly, we operate under the assumption that semi-honest
entities – including the edge devices, insecure edge servers, and the main
server – are all governed by the same total privacy budget $\epsilon$, with
$\delta=10^{-5}$.

###  V-B DP-HFL Comparison to Baselines

Figure 4: Impact of varying privacy budgets ($\epsilon$) per entity on the
training performance of DP-HFL. It illustrates that the testing accuracy for
both datasets improves as the allocated privacy budget $\epsilon$ increases.

Our first experiment examines the performance of DP-HFL compared with
baselines. We utilize the conventional hierarchical FedAvg algorithm [38],
which offers no explicit privacy protection, as our upper bound on achievable
accuracy. We implement HFL-DP [22], which employs LDP within the hierarchical
structure, for competitive analysis. DP-HFL, hierarchical FedAvg (HFL (w/o
DP)) and HFL-DP all employ a local model training interval of $\tau_{k}=20$
and conduct local aggregations after every five local SGD iterations.

Fig. 3 demonstrates the results. We see DP-HFL obtains performance
enhancements over HFL-DP by exploiting secure edge servers in the hierarchical
architecture’s middle-layer. This improvement is observed both in terms of
superior testing accuracy and decreased accuracy perturbation as the
probability ($p_{c}$) of a subnet being linked to a secure edge server
escalates. Specifically, when $p_{c}=0.5$, DP-HFL achieves an accuracy gain at
$k=200$ of $12\%$ and $6\%$ for CIFAR-10 and F-MNIST, respectively, and
displays reduced volatility in the accuracy curve compared to HFL-DP. When all
subnets are linked to a secure edge server ($p_{c}=1$), the improvement almost
doubles. Notably, compared to the upper bound benchmark, DP-HFL with $p_{c}=1$
achieves an accuracy within $8\%$ and $3\%$ of the benchmark for CIFAR-10 and
F-MNIST, respectively. The exploitation of secure edge servers into the
middle-layer of the hierarchy significantly mitigates the amount of
supplementary noise required to maintain an equivalent privacy level, thereby
culminating in an improved model performance.

###  V-C Privacy-Utility Tradeoff Performance

Our next two experiments consider the balance between privacy protection and
model performance obtained by DP-HFL. The focus is on understanding how
performance is influenced under various privacy guarantees.

Figure 5: This figure depicts the interplay between privacy and performance in
DP-HFL across various probabilities ($p_{c}$) of a subnet’s linkage to a
secure edge server under different privacy budgets ($\epsilon$) per entity. It
shows a substantial enhancement in the privacy-performance tradeoff as the
value of $p_{c}$ escalates.

Fig 4 presents the training performance of DP-HFL for varying privacy
protection $\epsilon$, with $p_{c}=0.5$. When the privacy budget allocated to
each entity decreases – for instance, moving from $\epsilon=1$ down to
$\epsilon=0.5$ – a corresponding decline in DP-HFL’s accuracy is observed.
This manifests as approximately a $20\%$ and $13\%$ dip in testing accuracy by
$k=200$ for CIFAR-10 and F-MNIST respectively. A consequential side effect of
this lower privacy budget is the enhanced volatility detected in the accuracy
curve, especially when $\epsilon=0.5$. Conversely, when the privacy budget per
entity is escalated (in this case, moving from $\epsilon=1$ to
$\epsilon=1.5$), the DP-HFL algorithm displays a surge in performance. This
improvement equates to a rise in accuracy by about $6.1\%$ for CIFAR-10 and
$8.5\%$ for F-MNIST. In addition, a higher privacy budget appears to stabilize
the volatility in the accuracy curve, leading to a more steady performance
when compared to the setting with a privacy budget of $\epsilon=1$. Naturally,
our benchmark model, which does not incorporate any privacy guarantees,
showcases optimal performance and stability. This stark contrast underscores
the inherent trade-off that exists when incorporating privacy provisions into
FL models.

On the other hand, Fig. 5 showcases the considerable enhancement in the
privacy-performance tradeoff that DP-HFL obtains as the probability of each
subnet being linked to a secure edge server escalates. Specifically, under the
same privacy conditions, DP-HFL exhibits an improvement of at least $20\%$ for
CIFAR-10 and $10\%$ for F-MNIST when all the edge servers in the mid-layer of
the hierarchy can be trusted ($p_{c}=1$) compared to HFL-DP ($p_{c}=0$). For
instance, when $p_{c}=1$ and $\epsilon=0.5$, DP-HFL achieves an accuracy boost
of $40\%$ for CIFAR-10 and $25\%$ for F-MNIST. The enhancement of the privacy-
performance tradeoff illustrated in Fig. 4 and Fig. 5 further accentuates the
advantage of integrating HDP into the hierarchical FL schema.

###  V-D Performance under Varying Network Configurations

For our final experiment, we investigate the impact of different network
configurations on the performance of DP-HFL. Two distinct configurations are
evaluated: (i) Configuration 1, wherein the size of subnets ($s_{c}$) is kept
constant at $5$ as the number of subnets ($N$) increases from $2$ to $10$ in
increments of $2$; (ii) Configuration 2, wherein the number of subnets ($N$)
is fixed at $2$, and the size of each subnet ($s_{c}$) increases from $5$ to
$25$ in increments of $5$. In all cases, $\epsilon=1.0$ and $p_{c}=0.5$.

Fig. 6 gives the results for both datasets. Initially, we consider the effect
of network sizes on model performance. The positive correlation between
network size and model performance is apparent in both configurations.
Specifically, the accuracy gain can be as substantial as $25\%$ and $42\%$ for
CIFAR-10 and F-MNIST respectively, when the network size transitions from
$I=10$ to $I=50$. This enhancement can be attributed to the diminishing
contribution impact of individual devices, as each device’s update is averaged
with an increasing number of updates during the aggregation phase. This
dilution consequently leads to a decrease in the sensitivity of the aggregate
to any particular device’s data. This observation aligns well with Theorem 1,
which quantifies the noise reduction as the network size expands.

Figure 6: Impact of various network configurations on the performance of DP-
HFL. It is evident that the testing accuracy increases alongside the network
size $I$. Moreover, under the same network size, enhancing the size of each
subnet $s_{c}$ yields superior test accuracy compared to merely increasing the
number of subnets $N$.

Subsequently, we examine the influence of varying network configurations on
the model performance, given a constant network size. Config. 2 evidently
leads to superior model performance compared to Config. 1. Interestingly, even
while retaining the same network size, model performance sees an upturn as the
size of each subnet amplifies, which is more beneficial than solely increasing
the quantity of subnets. This pattern highlights the advantages of
incorporating secure edge servers in DP-HFL’s mid-layer hierarchy. This is
consistent with Theorem 1: when subnets are linked to a secure edge server,
the extra noise needed to maintain an equivalent privacy level during
aggregations can be downscaled by the square of the subnet size, i.e.,
$1/s_{c}^{2}$. This effect is generally more pronounced than the reduction
achieved through the augmentation of the subnet number, i.e., $1/N$. These
findings underscore the importance of considering network configuration in
privacy-accuracy trade-off optimization for DP-HFL.

##  VI Conclusion and Future Work

In this work, we developed and analyzed DP-HFL, a DP-enhanced hierarchical FL
methodology. This new methodology significantly decreases the required DP
noise to achieve a specified privacy level, enabling an improved trade-off
between privacy preservation and machine learning model performance. We
provided a comprehensive theoretical exploration of the convergence behavior
of DP-HFL. We identified key factors that critically affect the model’s
performance and the privacy-utility trade-off. Our analysis demonstrated that
with the right parameter tuning, the cumulative average of the global gradient
under our framework is able to sublinearly converge to a minimal optimality
gap with rates $\mathcal{O}(1/\sqrt{k})$ for non-convex loss functions.
Numerical evaluations substantiated the effectiveness of DP-HFL in terms of
convergence speed and privacy-performance trade-off compared with existing DP-
based FL algorithms. Future work will focus on designing an adaptive algorithm
to adjust learning parameters based on privacy-performance trade-offs and
environmental variability.

## References

  * [1] B. Liu, M. Ding, S. Shaham, W. Rahayu, F. Farokhi, and Z. Lin, “When machine learning meets privacy: A survey and outlook,” _ACM Comput. Surveys (CSUR)_ , vol. 54, no. 2, 2021.
  * [2] M. Al-Rubaie and J. M. Chang, “Privacy-preserving machine learning: Threats and solutions,” _IEEE Security Privacy_ , vol. 17, no. 2, pp. 49–58, 2019.
  * [3] E. De Cristofaro, “A critical overview of privacy in machine learning,” _IEEE Security Privacy_ , vol. 19, no. 4, pp. 19–27, 2021.
  * [4] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in _Proc. ACM Conf. Comput. Commun. Security (SIGSAC)_ , 2017, p. 1175–1191.
  * [5] Y. Yang, S. Huang, W. Huang, and X. Chang, “Privacy-preserving cost-sensitive learning,” _IEEE Trans. Neural Netw. Learn. Syst._ , vol. 32, no. 5, pp. 2105–2116, 2021.
  * [6] F. Farokhi, N. Wu, D. Smith, and M. A. Kaafar, “The cost of privacy in asynchronous differentially-private machine learning,” _IEEE Trans. Inf. Forensics Security_ , vol. 16, pp. 2118–2129, 2021.
  * [7] Y.-W. Chu, S. Hosseinalipour, E. Tenorio, L. Cruz, K. A. Douglas, A. S. Lan, and C. G. Brinton, “Mitigating biases in student performance prediction via attention-based personalized federated learning,” _Proc. ACM Int. Conf. Inf. Knowl. Manag._ , 2022.
  * [8] Z.-L. Chang, S. Hosseinalipour, M. Chiang, and C. G. Brinton, “Asynchronous multi-model federated learning over wireless networks: Theory, modeling, and optimization,” 2023.
  * [9] F. P.-C. Lin, S. Hosseinalipour, S. S. Azam, C. G. Brinton, and N. Michelusi, “Semi-decentralized federated learning with cooperative D2D local model aggregations,” _IEEE J. Sel. Areas Commun._ , 2021.
  * [10] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in _Proc. Int. Conf. Artificial Intell. Stat. (AISTATS)_ , 2017.
  * [11] F. Po-Chen Lin, S. Hosseinalipour, C. G. Brinton, and N. Michelusi, “Delay-aware hierarchical federated learning,” _arXiv:2303.12414_ , 2023.
  * [12] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrained edge computing systems,” _IEEE J. Select. Areas Commun._ , vol. 37, no. 6, pp. 1205–1221, 2019.
  * [13] F. Haddadpour and M. Mahdavi, “On the convergence of local descent methods in federated learning,” _arXiv:1910.14425_ , 2019.
  * [14] S. Hosseinalipour, S. Azam, C. Brinton, N. Michelusi, V. Aggarwal, D. Love, and H. Dai, “Multi-stage hybrid federated learning over large-scale D2D-enabled fog networks,” _IEEE/ACM Trans. Netw._ , vol. 30, no. 4, pp. 1569–1584, 2022.
  * [15] W. Wei, L. Liu, M. L. Loper, K. H. Chow, M. E. Gursoy, S. Truex, and Y. Wu, “A framework for evaluating client privacy leakages in federated learning,” in _Computer Security (ESORICS)_ , 2020, pp. 545–566.
  * [16] B. Zhao, K. R. Mopuri, and H. Bilen, “idlg: Improved deep leakage from gradients,” _arXiv:2001.02610_ , 2020.
  * [17] L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” in _Proc. Adva. Neural Inf. Process. Syst._ , 2019.
  * [18] Z. Wang, M. Song, Z. Zhang, Y. Song, Q. Wang, and H. Qi, “Beyond inferring class representatives: User-level privacy leakage from federated learning,” in _Proc. IEEE Int. Conf. Comput. Comun. (INFOCOM)_ , 2019, pp. 2512–2520.
  * [19] K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. S. Quek, and H. Vincent Poor, “Federated learning with differential privacy: Algorithms and performance analysis,” _IEEE Trans. Inf. Forensics Security_ , vol. 15, pp. 3454–3469, 2020.
  * [20] X. Shen, Y. Liu, and Z. Zhang, “Performance-enhanced federated learning with differential privacy for internet of things,” _IEEE Internet Things J._ , vol. 9, no. 23, pp. 24 079–24 094, 2022.
  * [21] Y. Zhao, J. Zhao, M. Yang, T. Wang, N. Wang, L. Lyu, D. Niyato, and K.-Y. Lam, “Local differential privacy-based federated learning for internet of things,” _IEEE Internet Things J._ , vol. 8, no. 11, pp. 8836–8853, 2021.
  * [22] L. Shi, J. Shu, W. Zhang, and Y. Liu, “Hfl-dp: Hierarchical federated learning with differential privacy,” in _Proc. IEEE Int. Glob. Commun. Conf. (GLOBECOM)_ , 2021, pp. 1–7.
  * [23] V. Chandrasekaran, S. Banerjee, D. Perino, and N. Kourtellis, “Hierarchical federated learning with privacy,” _arXiv:2206.05209_ , 2022.
  * [24] J. Wang, S. Guo, X. Xie, and H. Qi, “Protect privacy from gradient leakage attack in federated learning,” in _IEEE Conf. Comput. Commun. (INFOCOM)_ , 2022, pp. 580–589.
  * [25] P. Sun, X. Chen, G. Liao, and J. Huang, “A profit-maximizing model marketplace with differentially private federated learning,” in _IEEE Conf. Comput. Commun. (INFOCOM)_ , 2022, pp. 1439–1448.
  * [26] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv:1610.05492_ , 2017.
  * [27] Z. Xiong, Z. Cai, D. Takabi, and W. Li, “Privacy threat and defense for federated learning with non-i.i.d. data in aiot,” _IEEE Trans. Ind. Informat._ , vol. 18, no. 2, pp. 1310–1321, 2022.
  * [28] M. Naseri, J. Hayes, and E. D. Cristofaro, “Local and central differential privacy for robustness and privacy in federated learning,” _arXiv:2009.03561_ , 2022.
  * [29] P. Liu, D. Willis, and S. Banerjee, “Paradrop: Enabling lightweight multi-tenancy at the network’s extreme edge,” in _IEEE/ACM Symp. Edge Comput. (SEC)_ , 2016, pp. 1–13.
  * [30] A. Wainakh, A. S. Guinea, T. Grube, and M. Mühlhäuser, “Enhancing privacy via hierarchical federated learning,” in _Workshop IEEE European Symp. Security Privacy (EuroSPW)_ , 2020, pp. 344–347.
  * [31] T. Zhou, “Hierarchical federated learning with gaussian differential privacy,” in _Proc. Int. Conf. Advanced Inf. Sci. Syst._ , 2023.
  * [32] F. P.-C. Lin, C. G. Brinton, and N. Michelusi, “Federated learning with communication delay in edge networks,” in _Proc. IEEE Int. Glob. Commun. Conf. (GLOBECOM)_ , 2020, pp. 1–6.
  * [33] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” vol. 9, no. 3-4, p. 211–407, 2014.
  * [34] L. Melis, C. Song, E. De Cristofaro, and V. Shmatikov, “Exploiting unintended feature leakage in collaborative learning,” in _IEEE Symp. Security Privacy (SP)_ , 2019, pp. 691–706.
  * [35] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proc. Conf. on Comput. Commun. Security (SIGSAC)_ , vol. 24. Association for Computing Machinery, 2016, p. 308–318.
  * [36] X. Zhang, X. Chen, M. Hong, S. Wu, and J. Yi, “Understanding clipping for federated learning: Convergence and client-level differential privacy,” in _Proc. Machine Learn._ , vol. 162, 2022, pp. 26 048–26 067.
  * [37] S. J. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and H. B. McMahan, “Adaptive federated optimization,” in _Proc. Int. Conf. Learn. Representations_ , 2021.
  * [38] L. Liu, J. Zhang, S. Song, and K. B. Letaief, “Client-edge-cloud hierarchical federated learning,” in _Proc. IEEE Int. Conf. Commun. (ICC)_ , 2020, pp. 1–6.

## Introduction to Notations and Preliminaries used in the Proofs

We define the auxiliary local aggregated model within each local model
training interval before the global aggregation as:

$\displaystyle\bar{\mathbf{w}}_{c}^{(t+1)}=\bar{\mathbf{w}}_{c}^{(t)}-\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(t)}+\Theta_{c}^{(t+1)}\bar{\mathbf{n}}_{c,Loc}^{(t+1)},\leavevmode\nobreak\
\forall t\in\mathcal{T}_{k}\setminus{\\{t_{k}\\}}.$ (34)

Similarly, we define the auxiliary global model within each local model
training interval preceding the global aggregation as

$\displaystyle\bar{\mathbf{w}}^{(t+1)}=$
$\displaystyle\bar{\mathbf{w}}^{(t)}-\eta_{k}\sum_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(t)}+\sum_{c=1}^{N}\varrho_{c}\Theta_{c}^{(t+1)}\bar{\mathbf{n}}_{c,Loc}^{(t+1)},\leavevmode\nobreak\
\forall t\in\mathcal{T}_{k}\setminus{\\{t_{k}\\}}.$ (35)

with the auxiliary global model at global aggregation defined as

$\displaystyle\bar{\mathbf{w}}^{(t_{k+1})}=\widetilde{\mathbf{w}}^{(t_{k+1})}+\Theta_{c}^{(t_{k+1})}\bar{\mathbf{n}}_{Glob}^{(t_{k+1})}.$
(36)

Here, $\widetilde{\mathbf{w}}^{(t_{k+1})}$ is the virtual global model just
before global aggregation, distinguishing it from
$\bar{\mathbf{w}}^{(t_{k+1})}$, which is defined immediately post global
aggregation.

##  Appendix A Proof of Theorem 1

######  Theorem 1.

Under Assumptions 1 and 2, upon using DP-HFL for ML model training, if
$\eta_{k}=\frac{\gamma}{\sqrt{k+1}}$ with
$\gamma\leq\min\\{\frac{1}{\tau},\frac{1}{K_{g}}\\}/\beta$, the cumulative
average of global loss gradients satisfies

$\displaystyle\frac{1}{K_{g}}\sum\limits_{k=0}^{K_{g}-1}\mathbb{E}[\|\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\|^{2}]\leq
2\gamma\frac{F(\bar{\mathbf{w}}^{(0)})-F(\mathbf{w}^{*})}{\tau\sqrt{K_{g}+1}}+\frac{\beta\gamma}{\sqrt{K_{g}+1}}\left[\beta\tau\left(B_{1}^{2}+B_{2}^{2}\right)+G^{2}+\tau\sigma^{2}\right]$
$\displaystyle+\frac{4\tau(K_{\ell}^{3}+1)Mq^{2}G^{2}\log(1/\delta)}{N^{2}\varepsilon^{2}}\sum\limits_{c=1}^{N}\Big{(}p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}\Big{)}.$

###### Proof.

Considering $t\in\mathcal{T}_{k}$, using the definition of
$\bar{\mathbf{w}}^{(t_{k+1})}$ given in Definition III-B, the global average
of the local models follows the following dynamics:

$\displaystyle\bar{\mathbf{w}}^{(t_{k+1})}=$
$\displaystyle\bar{\mathbf{w}}^{(t_{k})}-\eta_{k}\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\frac{1}{s_{c}}\sum\limits_{j\in\mathcal{S}_{c}}\left(\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})-\mathbf{n}_{j}^{{(\ell)}}\right)$
$\displaystyle+\sum\limits_{\ell\in\mathcal{T}^{\mathsf{L}}_{k,c}}\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Loc}^{(\ell)}+\bar{\mathbf{n}}_{Glob}^{(t_{k+1})},$
(37)

where ${\mathbf{n}}_{j}^{{(\ell)}}=\widehat{\mathbf{g}}^{(\ell)}_{j}-\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})$. On the other hand, the $\beta$-smoothness of
the global function $F$ implies

$\displaystyle F(\bar{\mathbf{w}}^{(t_{k+1})})\leq
F(\bar{\mathbf{w}}^{(t_{k})})$ $\displaystyle+\nabla
F(\bar{\mathbf{w}}^{(t_{k})})^{\top}(\bar{\mathbf{w}}^{(t_{k+1})}-\bar{\mathbf{w}}^{(t_{k})})+\frac{\beta}{2}\Big{\|}\bar{\mathbf{w}}^{(t_{k+1})}-\bar{\mathbf{w}}^{(t_{k})}\Big{\|}^{2}.$
(38)

Replacing the result of (A) in the above inequality, taking the expectation on
the both hand sides, and using the fact that
$\mathbb{E}[{\mathbf{n}}^{(\ell)}_{j}]=\bf 0$ and
$\mathbb{E}[\bar{\mathbf{n}}^{(t_{k+1})}_{Glob}]=\bf 0$ yields:

$\displaystyle\mathbb{E}\left[F(\bar{\mathbf{w}}^{(t_{k+1})})-F(\bar{\mathbf{w}}^{(t_{k})})\right]\leq-\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\mathbb{E}\bigg{[}\underbrace{\eta_{k}\nabla
F(\bar{\mathbf{w}}^{(t_{k})})^{\top}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})}_{(a)}\bigg{]}$
$\displaystyle+\frac{\eta_{k}^{2}\beta}{2}\mathbb{E}\bigg{[}\underbrace{\Big{\|}\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}}_{(b_{1})}\bigg{]}+\frac{\eta_{k}^{2}\beta}{2}\mathbb{E}\bigg{[}\underbrace{\Big{\|}\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{{(\ell)}}\Big{\|}^{2}}_{(b_{2})}\bigg{]}$
$\displaystyle+\frac{\beta}{2}\mathbb{E}\bigg{[}\underbrace{\Big{\|}\bar{\mathbf{n}}_{Glob}^{{(t_{k+1})}}\Big{\|}^{2}}_{(c_{1})}\bigg{]}+\frac{\beta}{2}\mathbb{E}\bigg{[}\underbrace{\Big{\|}\sum\limits_{\ell\in\mathcal{T}^{\mathsf{L}}_{k,c}}\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Loc}^{(t+1)}\Big{\|}^{2}}_{(c_{2})}\bigg{]}.$
(39)

To bound $(a)$, we apply Lemma 3 (see Appendix C) to get

$\displaystyle-\eta_{k}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\left[\nabla
F(\bar{\mathbf{w}}^{(t_{k})})^{\top}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\right]\leq-\frac{\eta_{k}\tau}{2}\Big{\|}\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\Big{\|}^{2}$
$\displaystyle-\frac{\eta_{k}}{2}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}+\frac{\eta_{k}\beta^{2}}{2}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\bar{\mathbf{w}}^{(\ell)}-\mathbf{w}_{j}^{(\ell)}\Big{\|}^{2}+\frac{\eta_{k}^{3}\beta^{2}\tau^{2}G^{2}}{2},$
(40)

To bound $(b_{1})$ and $(b_{2})$, we use the Cauchy-Schwartz inequality (i.e.,
$\|\sum_{n=1}^{N}\mathbf{a}_{n}\|^{2}\leq
N\sum_{n=1}^{N}\|\mathbf{a}_{n}\|^{2}$ holds for any real-values set of
vectors $\\{\mathbf{a}_{n}\\}_{n=1}^{N}$) to get

$\displaystyle\Big{\|}\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}\leq\tau\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}.$ (41)

and

$\displaystyle\Big{\|}\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(\ell)}\Big{\|}^{2}\leq\tau\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(\ell)}\Big{\|}^{2}\leq\tau\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\mathbf{n}_{j}^{(\ell)}\Big{\|}^{2}.$
(42)

To bound $(c_{1})$, we first show that

$\displaystyle\bar{\mathbf{n}}_{Glob}^{(t)}=\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Glob}^{(t)}.$
(43)

Since $\bar{\mathbf{n}}_{c,\text{Glob}}^{(t)}$ are i.i.d. random variables for
$c=1,2,\dots,N$, we get

$\displaystyle\mathbb{E}[\|\bar{\mathbf{n}}_{Glob}^{(t)}\|^{2}]=\mathbb{E}\Big{[}\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Glob}^{(t)}\Big{\|}^{2}\Big{]}=\sum\limits_{c=1}^{N}\varrho_{c}^{2}\underbrace{\mathbb{E}[\|\bar{\mathbf{n}}_{c,Glob}^{(t)}\|^{2}]}_{(d)},$
(44)

To bound $(d)$, we apply the law of total expectation and get

$\displaystyle\mathbb{E}[\|\bar{\mathbf{n}}_{c,Glob}^{(t)}\|^{2}]$
$\displaystyle=p_{c}\cdot\mathbb{E}\Big{[}\Big{\|}\widetilde{\mathbf{n}}_{c,Glob}^{(t)}\Big{\|}^{2}\Big{|}\widetilde{\mathbf{n}}_{c,Glob}^{(t)}\sim\mathcal{N}(0,\bar{\sigma}_{Glob}^{2})\Big{]}+(1-p_{c})\cdot\mathbb{E}\Big{[}\Big{\|}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j,Glob}^{(t)}\Big{\|}^{2}\Big{|}\mathbf{n}_{j,Glob}^{(t)}\sim\mathcal{N}(0,\sigma_{Glob}^{2})\Big{]}$
$\displaystyle\overset{(i)}{=}p_{c}\underbrace{\mathbb{E}\Big{[}\Big{\|}\widetilde{\mathbf{n}}_{c,Glob}^{(t)}\Big{\|}^{2}\Big{|}\widetilde{\mathbf{n}}_{c,Glob}^{(t)}\sim\mathcal{N}(0,\bar{\sigma}_{Glob}^{2})\Big{]}}_{(d_{1})}+(1-p_{c})\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\underbrace{\mathbb{E}\Big{[}\Big{\|}\mathbf{n}_{j,Glob}^{(t)}\Big{\|}^{2}\Big{|}\mathbf{n}_{j,Glob}^{(t)}\sim\mathcal{N}(0,\sigma_{Glob}^{2})\Big{]}}_{(d_{2})}.$
(45)

where $(i)$ comes from the fact that $\mathbf{n}_{j,Glob}^{(t)}$ are i.i.d.
random variables for $j\in\mathcal{S}_{c}$ and
$\mathbb{E}[\mathbf{n}_{j,Glob}^{(t)}]=0,\leavevmode\nobreak\ \forall
j\in\mathcal{S}_{c}$. To bound $(d_{1})$ in the above inequality, we show that

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\widetilde{\mathbf{n}}_{c,Glob}^{(t)}\Big{\|}^{2}\Big{|}\widetilde{\mathbf{n}}_{c,Glob}^{(t)}\sim\mathcal{N}(0,\bar{\sigma}_{Glob}^{2})\Big{]}=\mathbb{E}\left[\sum\limits_{n=0}^{M-1}(\bar{n}_{\\{c,n\\},Glob}^{(t)})^{2}\right]=\sum\limits_{n=0}^{M-1}\mathbb{E}\left[(\bar{n}_{\\{c,n\\},Glob}^{(t)})^{2}\right]=M\bar{\sigma}_{Glob}^{2},$
(46)

where
$\bar{\mathbf{n}}_{c,Glob}^{(t)}=(\bar{n}_{\\{c,0\\},Glob}^{(t)},\bar{n}_{\\{c,1\\},Glob}^{(t)},\cdots,\bar{n}_{\\{c,M-1\\},Glob}^{(t)})$.
Similarly, to bound $(d_{2})$, we show that

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\mathbf{n}_{j,Glob}^{(t)}\Big{\|}^{2}\Big{|}\mathbf{n}_{j,Glob}^{(t)}\sim\mathcal{N}(0,\sigma_{Glob}^{2})\Big{]}=\mathbb{E}\left[\sum\limits_{n=0}^{M-1}(n_{\\{j,n\\},Glob}^{(t)})^{2}\right]=\sum\limits_{n=0}^{M-1}\mathbb{E}\left[(n_{\\{j,n\\},Glob}^{(t)})^{2}\right]=M\sigma_{Glob}^{2},$
(47)

where
$\mathbf{n}_{j,Glob}^{(t)}=(n_{\\{j,0\\},Glob}^{(t)},n_{\\{j,1\\},Glob}^{(t)},\cdots,n_{\\{j,M-1\\},Glob}^{(t)})$.
Replacing (46) and (47) into (A) gives us

$\displaystyle\mathbb{E}[\|\bar{\mathbf{n}}_{c,Glob}\|^{2}]=M\Big{(}p_{c}\bar{\sigma}_{Glob}^{2}+(1-p_{c})\sigma_{Glob}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}.$
(48)

Utilize the result above in (44) yields

$\displaystyle\mathbb{E}[\|\bar{\mathbf{n}}_{Glob}^{(t)}\|^{2}]=M\sum\limits_{c=1}^{N}\varrho_{c}^{2}\Big{(}p_{c}\bar{\sigma}_{Glob}^{2}+(1-p_{c})\sigma_{Glob}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}.$
(49)

To bound $(c_{2})$, we first apply the Cauchy-Schwartz inequality as follows:

$\displaystyle\mathbb{E}\bigg{[}\Big{\|}\sum\limits_{\ell\in\mathcal{T}^{\mathsf{L}}_{k,c}}\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Loc}^{(\ell)}\Big{\|}^{2}\bigg{]}\leq
K_{\ell}\sum\limits_{\ell\in\mathcal{T}^{\mathsf{L}}_{k,c}}\mathbb{E}\bigg{[}\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Loc}^{(\ell)}\Big{\|}^{2}\bigg{]}.$
(50)

Applying the result from (C) in Lemma 2, we get

$\displaystyle\mathbb{E}\bigg{[}\Big{\|}\sum\limits_{\ell\in\mathcal{T}^{\mathsf{L}}_{k,c}}\sum\limits_{c=1}^{N}\varrho_{c}\bar{\mathbf{n}}_{c,Loc}^{(\ell)}\Big{\|}^{2}\bigg{]}$
$\displaystyle\leq
K_{\ell}M\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}$
$\displaystyle=K_{\ell}^{2}M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}.$
(51)

Substituting (A), (41) (42), and (A) into (A), using the facts
$\mathbb{E}[\|\mathbf{n}_{j}^{{(\ell)}}\|_{2}^{2}]\leq\sigma^{2}$, and Cauchy-
Schwartz inequality yields

$\displaystyle\mathbb{E}\left[F(\bar{\mathbf{w}}^{(t_{k+1})})-F(\bar{\mathbf{w}}^{(t_{k})})\right]\leq-\frac{\eta_{k}\tau}{2}\mathbb{E}[\|\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\|^{2}]+\frac{\eta_{k}\beta^{2}}{2}\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\left[Z_{1}^{(\ell)}+Z_{2}^{(\ell)}\right]$
$\displaystyle+\frac{\eta_{k}^{2}\beta\tau(G^{2}+\tau\sigma^{2})}{2}+\frac{\beta
M}{2}\sum\limits_{c=1}^{N}\varrho_{c}^{2}\Big{(}p_{c}\bar{\sigma}_{Glob}^{2}+(1-p_{c})\sigma_{Glob}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}$
$\displaystyle+\frac{\beta
K_{\ell}^{2}M}{2}\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}.$
(52)

Applying Proposition 1 into the inequality above yields

$\displaystyle\mathbb{E}\left[F(\bar{\mathbf{w}}^{(t_{k+1})})-F(\bar{\mathbf{w}}^{(t_{k})})\right]\leq-\frac{\eta_{k}\tau}{2}\mathbb{E}[\|\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\|^{2}]+\frac{\eta_{k}^{2}\beta^{2}}{2}\tau^{2}\left(B_{1}^{2}+B_{2}^{2}\right)+\frac{\eta_{k}^{2}\beta\tau(G^{2}+\tau\sigma^{2})}{2}$
$\displaystyle+\frac{\beta
K_{\ell}^{3}K_{g}Mq^{2}\log(1/\delta)}{2N^{2}\varepsilon^{2}}\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}c_{2}^{2}\Delta_{Edge,Loc}^{2}+(1-p_{d})\frac{v_{2}^{2}}{s_{c}}\Delta_{Device,Loc}^{2}\Big{)}$
$\displaystyle+\frac{\beta
Mq^{2}K_{g}\log(1/\delta)}{2N^{2}\varepsilon^{2}}\sum\limits_{c=1}^{N}\Big{(}p_{c}c_{2}^{2}\Delta_{Edge,Glob}^{2}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}\Delta_{Device,Glob}^{2}\Big{)}.$
(53)

Replacing the bound on $\Delta_{Edge,Glob}$ and $\Delta_{Device,Glob}$ from
Lemma 1 into (A) and using the fact that
$\eta_{k}\leq\frac{1}{\max\\{\tau,K_{g}\\}\beta}$ gives us

$\displaystyle\frac{\eta_{k}\tau}{2}\mathbb{E}[\|\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\|^{2}]\leq\mathbb{E}\left[F(\bar{\mathbf{w}}^{(t_{k})})-F(\bar{\mathbf{w}}^{(t_{k+1})})\right]+\frac{\eta_{k}^{2}\beta\tau}{2}\left[\beta\tau\left(B_{1}^{2}+B_{2}^{2}\right)+G^{2}+\tau\sigma^{2}\right]$
$\displaystyle+\eta_{k}(K_{\ell}^{3}+1)\frac{2\tau^{2}Mq^{2}G^{2}\log(1/\delta)}{N^{2}\varepsilon^{2}}\sum\limits_{c=1}^{N}\Big{(}p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}\Big{)}.$
(54)

Dividing both hand sides by $\frac{\eta_{k}\tau}{2}$ and averaging across
global aggregations yields

$\displaystyle\frac{1}{K_{g}}\sum\limits_{k=0}^{K_{g}-1}\mathbb{E}[\|\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\|^{2}]\leq\frac{1}{K_{g}}\sum\limits_{k=0}^{K_{g}-1}\bigg{[}\frac{2}{\eta_{k}\tau}\mathbb{E}\left[F(\bar{\mathbf{w}}^{(t_{k})})-F(\bar{\mathbf{w}}^{(t_{k+1})})\right]\bigg{]}$
$\displaystyle+\frac{1}{K_{g}}\sum\limits_{k=0}^{K_{g}-1}\bigg{[}\eta_{k}\beta\left[\beta\tau\left(B_{1}^{2}+B_{2}^{2}\right)+G^{2}+\tau\sigma^{2}\right]\bigg{]}+\frac{4\tau(K_{\ell}^{3}+1)Mq^{2}G^{2}\log(1/\delta)}{N^{2}\varepsilon^{2}}\sum\limits_{c=1}^{N}\Big{(}p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}\Big{)}$
$\displaystyle\leq
2\gamma\frac{F(\bar{\mathbf{w}}^{(0)})-F(\mathbf{w}^{*})}{\tau\sqrt{K_{g}+1}}+\frac{\beta\gamma}{\sqrt{K_{g}+1}}\left[\beta\tau\left(B_{1}^{2}+B_{2}^{2}\right)+G^{2}+\tau\sigma^{2}\right]$
$\displaystyle+\frac{4\tau(K_{\ell}^{3}+1)Mq^{2}G^{2}\log(1/\delta)}{N^{2}\varepsilon^{2}}\sum\limits_{c=1}^{N}\Big{(}p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}\Big{)}.$
(55)

∎

##  Appendix B Proof of Proposition 1

######  Proposition 1.

For $t\in\mathcal{T}_{k}\setminus\\{t_{k+1}\\}$, under Assumptions 1 and 2, if
$\eta_{k}\leq\frac{1}{\max\\{\tau,K_{g}\\}\beta}$, using DP-HFL for ML model
training, the model dispersion can be bounded as

$\displaystyle Z_{1}^{(t)}\leq\eta_{k}\tau B_{1}^{2},$ (56)

and

$\displaystyle Z_{2}^{(t)}\leq\eta_{k}\tau B_{2}^{2}.$ (57)

where

$\displaystyle B_{1}=$
$\displaystyle\Big{(}(1+2\eta_{0}\beta)^{\tau-1}+1\Big{)}^{2}\sum\limits_{c=1}^{N}\varrho_{c}\Big{(}2\sigma+\zeta_{c}\Big{)}^{2},$
(58) $\displaystyle
B_{2}=(1+\eta_{k}\beta)^{2(\tau-1)}\sum\limits_{c=1}^{N}\varrho_{c}\Phi_{c}^{2},$
(59)

and

$\displaystyle\Phi_{c}=$
$\displaystyle\bigg{[}\frac{2Cq\sqrt{M\log(1/\delta)}}{\varepsilon}\bigg{(}\sqrt{\sum\limits_{c=1}^{N}\Big{(}p_{c}\frac{c_{2}^{2}}{N^{2}s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{N^{2}s_{c}}\Big{)}}+\sqrt{p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}}\bigg{)}$
$\displaystyle+2\beta\epsilon_{k}+2\sigma+\zeta\bigg{]}\Big{(}(1+\eta_{0}(\beta-\mu))^{\tau-1}+1\Big{)}+\beta(\epsilon_{c,k}+\epsilon_{k})+2\sigma+\zeta.$
(60)

###### Proof.

###  B-A Obtaining bound of $Z_{1}^{(t)}$.

Applying the one-step behavior of
$\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}$ from (83) in Lemma
2, we get

$\displaystyle\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}\leq$
$\displaystyle(1-\Theta_{c}^{(t+1)})\bigg{[}(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\big{\|}^{2}]}+\eta_{k}\beta\underbrace{\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\|^{2}]}}_{(a)}+\eta_{k}(2\sigma+\zeta_{c})\bigg{]}.$
(61)

We first bound $(a)$ by taking the weighted sum
$\sum_{i\in\mathcal{S}_{c}}\rho_{i,c}$ on the both hand sides of (61) and
obtain

$\displaystyle\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{j}^{(t+1)}\big{\|}^{2}]}\leq(1-\Theta_{c}^{(t+1)})\bigg{[}(1+2\eta_{k}\beta)\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{j}^{(t)}\big{\|}^{2}]}+\eta_{k}(2\sigma+\zeta_{c})\bigg{]}$
$\displaystyle\leq(1+2\eta_{k}\beta)\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{j}^{(t)}\big{\|}^{2}]}+\eta_{k}(2\sigma+\zeta_{c}).$
(62)

Recursively expanding across the interval $t\in\mathcal{T}_{k}$, the above
inequality gives us

$\displaystyle\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{j}^{(t)}\|^{2}]}\leq\eta_{k}(2\sigma+\zeta_{c})\sum_{\ell={t_{k-1}}}^{t-1}(1+2\eta_{k}\beta)^{t-\ell-1}$
$\displaystyle=\eta_{k}(2\sigma+\zeta_{c})\frac{(1+2\eta_{k}\beta)^{t-t_{k}}-1}{(1+2\eta_{k}\beta)-1}$
$\displaystyle\overset{(i)}{\leq}\eta_{k}(2\sigma+\zeta_{c})\frac{2\eta_{k}\beta\tau(1+2\eta_{k}\beta)^{\tau-1}}{2\eta_{k}\beta}$
$\displaystyle\leq\eta_{k}(2\sigma+\zeta_{c})\tau(1+2\eta_{k}\beta)^{\tau-1}.$
(63)

where $(i)$ utilizes Fact 2. Replacing the bound on $(a)$ into (61) gives us

$\displaystyle\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}\leq(1-\Theta_{c}^{(t+1)})\bigg{[}(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\big{\|}^{2}]}+\eta_{k}^{2}\beta\tau(2\sigma+\zeta_{c})(1+2\eta_{k}\beta)^{\tau-1}+\eta_{k}(2\sigma+\zeta_{c})\bigg{]}$
$\displaystyle\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\big{\|}^{2}]}+\eta_{k}\left[(2\sigma+\zeta_{c})\Big{(}(1+2\eta_{k}\beta)^{\tau-1}+1\Big{)}\right].$
(64)

Recursively expanding the above inequality across the interval
$t\in\mathcal{T}_{k}$ results in

$\displaystyle\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\|^{2}]}\leq\eta_{k}\left[(2\sigma+\zeta_{c})\Big{(}(1+2\eta_{k}\beta)^{\tau-1}+1\Big{)}\right]\sum_{\ell={t_{k}}}^{t-1}(1+\eta_{k}\beta)^{t-\ell-1}\prod_{m=\ell+1}^{t}(1-\Theta_{c}^{(m)})$
$\displaystyle=\eta_{k}\left[(2\sigma+\zeta_{c})\Big{(}(1+2\eta_{k}\beta)^{\tau-1}+1\Big{)}\right]\frac{(1+\eta_{k}\beta\mu)^{t-t_{k}}-1}{(1+\eta_{k}\beta)-1}$
$\displaystyle\leq\eta_{k}\left[(2\sigma+\zeta_{c})\Big{(}(1+2\eta_{k}\beta)^{\tau-1}+1\Big{)}\right]\frac{\eta_{k}\beta\tau(1+\eta_{k}\beta)^{\tau-1}}{\eta_{k}\beta}$
$\displaystyle\leq\eta_{k}\tau\left[(2\sigma+\zeta_{c})\Big{(}(1+2\eta_{k}\beta)^{\tau-1}+1\Big{)}\right].$
(65)

Taking square of both hand sides followed by taking the weighted sum
$\sum_{c=1}^{N}\varrho_{c}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}$ gives us

$\displaystyle Z_{1}^{(t)}$
$\displaystyle\leq\eta_{k}^{2}\tau^{2}B_{1}^{2}\leq\eta_{k}\tau B_{1}^{2}$
(66)

###  B-B Obtaining bound of $Z_{2}^{(t)}$.

Applying the one-step behavior of
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}$
from (2) in Lemma 2, we get

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}+\eta_{k}\beta\underbrace{\sum\limits_{d=1}^{N}\varrho_{d}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{d}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}}_{(b)}$
$\displaystyle+\eta_{k}\beta\epsilon_{c,k}+\eta_{k}\beta\epsilon_{k}+\eta_{k}(2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\Theta_{c}^{(t+1)}\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}.$
(67)

We first bound $(b)$ by taking the weighted sum $\sum_{c=1}^{N}\varrho_{c}$ on
the both hand sides of (B-B) and get

$\displaystyle\sum\limits_{c=1}^{N}\varrho_{c}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+2\eta_{k}\beta)\sum\limits_{c=1}^{N}\varrho_{c}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\Theta_{c}^{(t+1)}\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}$
$\displaystyle\leq(1+2\eta_{k}\beta)\sum\limits_{c=1}^{N}\varrho_{c}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}+\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)$
$\displaystyle+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}.$
(68)

Recursively expanding across the interval $t\in\mathcal{T}_{k}$, the above
inequality yields

$\displaystyle\sum\limits_{c=1}^{N}\varrho_{c}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle\leq\Bigg{(}\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}\Bigg{)}\sum_{\ell={t_{k}}}^{t-1}(1+2\eta_{k}\beta)^{t-\ell-1}$
$\displaystyle=\Bigg{(}\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}\Bigg{)}\frac{(1+2\eta_{k}\beta)^{t-t_{k}}-1}{(1+2\eta_{k}\beta)-1}$
$\displaystyle\overset{(iii)}{\leq}\Bigg{(}\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}\Bigg{)}\frac{2\eta_{k}\beta\tau(1+2\eta_{k}\beta)^{t-t_{k}-1}}{2\eta_{k}\beta}$
$\displaystyle\leq\tau\Bigg{(}\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}\Bigg{)}(1+2\eta_{k}\beta)^{\tau-1},$
(69)

where $(iii)$ is resulted from Fact. 2. Replacing the bound on $(b)$ above
into (B-B) yields

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1-\eta_{k}\mu)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}\beta\tau\Bigg{(}\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}\Bigg{)}(1+2\eta_{k}\beta)^{\tau-1}+\eta_{k}(\beta(\epsilon_{c,k}+\epsilon_{k})+2\sigma+\zeta)$
$\displaystyle+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\Theta_{c}^{(t+1)}\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}$
$\displaystyle\leq(1-\eta_{k}\mu)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}\beta\tau\Bigg{(}\eta_{k}(2\beta\epsilon_{k}+2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}\Bigg{)}(1+2\eta_{k}\beta)^{\tau-1}+\eta_{k}(\beta(\epsilon_{c,k}+\epsilon_{k})+2\sigma+\zeta)$
$\displaystyle+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}+\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}.$
(70)

Apply Proposition 1 and Lemma 1 into the above inequality yields

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}^{2}\beta\tau\Bigg{[}\frac{2Cq\sqrt{MK_{\ell}K_{g}\log(1/\delta)}}{\varepsilon}\bigg{(}\sqrt{\sum\limits_{d=1}^{N}\Big{(}p_{d}\frac{c_{2}^{2}}{N^{2}s_{d}^{2}}+(1-p_{d})\frac{v_{2}^{2}}{N^{2}s_{d}}\Big{)}}+\sqrt{p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}}\bigg{)}$
$\displaystyle+2\beta\epsilon_{k}+2\sigma+\zeta\Bigg{]}(1+2\eta_{k}\beta)^{\tau-1}+\eta_{k}(\beta(\epsilon_{c,k}+\epsilon_{k})+2\sigma+\zeta)$
$\displaystyle+\eta_{k}^{2}\frac{2Cq\sqrt{MK_{\ell}K_{g}\log(1/\delta)}}{\varepsilon}\bigg{(}\sqrt{\sum\limits_{d=1}^{N}\Big{(}p_{d}\frac{c_{2}^{2}}{N^{2}s_{d}^{2}}+(1-p_{d})\frac{v_{2}^{2}}{N^{2}s_{d}}\Big{)}}+\sqrt{p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}}\bigg{)}.$
(71)

Using the fact that $\eta_{k}\leq\frac{1}{\max\\{\tau,K_{g}\\}\beta}$ on the
above inequality, we obtain

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}\Bigg{[}\frac{2Cq\sqrt{M\log(1/\delta)}}{\varepsilon}\bigg{(}\sqrt{\sum\limits_{d=1}^{N}\Big{(}p_{d}\frac{c_{2}^{2}}{N^{2}s_{d}^{2}}+(1-p_{d})\frac{v_{2}^{2}}{N^{2}s_{d}}\Big{)}}+\sqrt{p_{c}\frac{c_{2}^{2}}{s_{c}^{2}}+(1-p_{c})\frac{v_{2}^{2}}{s_{c}}}\bigg{)}$
$\displaystyle+2\beta\epsilon_{k}+2\sigma+\zeta\Bigg{]}\Big{(}(1+2\eta_{0}\beta)^{\tau-1}+1\Big{)}+\eta_{k}(\beta(\epsilon_{c,k}+\epsilon_{k})+2\sigma+\zeta)$
$\displaystyle=(1-\eta_{k}\mu)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}+\eta_{k}\Phi_{c}.$
(72)

Recursively expanding across the interval $t\in\mathcal{T}_{k}$, the above
inequality yields

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}\leq\eta_{k}\Phi_{c}\sum_{\ell={t_{k}}}^{t-1}(1+\eta_{k}\beta)^{t-\ell-1}$
$\displaystyle=\eta_{k}\Phi_{c}\frac{(1+\eta_{k}\beta)^{t-t_{k}}-1}{(1+\eta_{k}\beta)-1}$
$\displaystyle=\eta_{k}\Phi_{c}\frac{\eta_{k}\beta\tau(1+\eta_{k}\beta)^{\tau-1}}{\eta_{k}\beta}$
$\displaystyle\leq\eta_{k}\tau\Phi_{c}(1+\eta_{k}\beta)^{\tau-1}.$ (73)

Taking square of both hand sides followed by taking the weighted sum
$\sum_{c=1}^{N}\varrho_{c}$ gives us

$\displaystyle Z_{2}^{(t)}\leq\eta_{k}^{2}\tau^{2}B_{2}^{2}\leq\eta_{k}\tau
B_{2}^{2}.$ (74)

This concludes the proof. ∎

##  Appendix C Lemmas and Auxiliary Results

To improve the tractability of the proofs, we provide a set of lemmas in the
following, which will be used to obtain the main results of the paper.

######  Lemma 1.

Under Assumption 2, the $L_{2}$-norm sensitivity of the exchanged gradients
during local aggregations can be obtained as follows:

$\displaystyle\bar{\Delta}_{c,Loc}=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=2\eta_{k}\tau_{k}G/s_{c},$
(75)

and

$\displaystyle\Delta_{i,Loc}=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=2\eta_{k}\tau_{k}G.$
(76)

Similarly, the $L_{2}$-norm sensitivity of the exchanged gradients during
global aggregations can be obtained as follows:

$\displaystyle\bar{\Delta}_{c,Glob}=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=2\eta_{k}\tau_{k}G/s_{c},$
(77)

and

$\displaystyle\Delta_{i,Glob}=\max_{\mathcal{D},\mathcal{D}^{\prime}}\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=2\eta_{k}\tau_{k}G.$
(78)

###### Proof.

Upper bounding
$\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
yields

$\displaystyle\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
$\displaystyle=\eta_{k}\sum_{\ell=t^{\prime}}^{t}\Big{\|}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
$\displaystyle=\eta_{k}\rho_{j,c}\sum_{\ell=t^{\prime}}^{t}\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\leq\eta_{k}/s_{c}\sum_{\ell=t^{\prime}}^{t}\left(\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})\Big{\|}+\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\right)$
$\displaystyle\leq\eta_{k}/s_{c}\sum_{\ell=t_{k}}^{t_{k+1}}\left(\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})\Big{\|}+\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\right)\leq\eta_{k}\tau_{k}G/s_{c},$
(79)

giving us the result in (75). Similarly, upper bounding
$\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$,
we get

$\displaystyle\Big{\|}\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=\eta_{k}\Big{\|}\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\sum_{\ell=t^{\prime}}^{t}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
$\displaystyle=\eta_{k}\sum_{\ell=t^{\prime}}^{t}\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\leq\eta_{k}\sum_{\ell=t^{\prime}}^{t}\left(\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})\Big{\|}+\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\right)$
$\displaystyle\leq\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\left(\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})\Big{\|}+\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\right)\leq\eta_{k}\tau_{k}G,$
(80)

giving us the result in (76).

Likewise, upper bounding
$\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
yields

$\displaystyle\bar{\Delta}_{c,Loc}=\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
$\displaystyle=\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\Big{\|}\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\sum_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=\eta_{k}\rho_{j,c}\sum_{\ell=t_{k}}^{t_{k+1}}\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})-\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
$\displaystyle\leq\eta_{k}/s_{c}\sum_{\ell=t_{k}}^{t_{k+1}}\left(\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D})\Big{\|}+\Big{\|}\widehat{\mathbf{g}}_{j}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\right)\leq\eta_{k}\tau_{k}G/s_{c},$
(81)

giving us the result in (77). Finally, upper bounding
$\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$,
we get

$\displaystyle\Big{\|}\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}=\eta_{k}\Big{\|}\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\sum_{\ell=t_{k}}^{t_{k+1}}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}$
$\displaystyle=\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})-\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\leq\eta_{k}\sum_{\ell=t_{k}}^{t_{k+1}}\left(\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D})\Big{\|}+\Big{\|}\widehat{\mathbf{g}}_{i}^{(\ell)}(\mathcal{D}^{\prime})\Big{\|}\right)\leq\eta_{k}\tau_{k}G,$
(82)

giving us the result in (78). ∎

######  Lemma 2.

For $t\in\mathcal{T}_{k}\setminus\\{t_{k+1}\\}$, under Assumptions 1 and 2,
using DFL for ML model training, the one-step behavior of
$\sqrt{\mathbb{E}[\|\mathbf{e}_{j}^{(t)}\|^{2}]}$ and
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|]^{2}}$
can be expressed as

$\displaystyle\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}\leq$
$\displaystyle(1-\Theta_{c}^{(t+1)})\bigg{[}(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\big{\|}^{2}]}+\eta_{k}\beta\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\|^{2}]}+\eta_{k}(2\sigma+\zeta_{c})\bigg{]},$
(83)

and

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}+\eta_{k}\beta\sum\limits_{d=1}^{N}\varrho_{d}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{d}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}\beta\epsilon_{c,k}+\eta_{k}\beta\epsilon_{k}+\eta_{k}(2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\Theta_{c}^{(t+1)}\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}.$
(84)

###### Proof.

First, note that if $\Theta_{c}^{(t+1)}=1$, we have
$\mathbf{e}_{i}^{(t+1)}=0$. Consider $\Theta_{c}^{(t+1)}=0$, to bound
$\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\|^{2}]}$, we first use the
definition of $\mathbf{w}_{i}^{(t)}$ given in (13) and
$\bar{\mathbf{w}}_{c}^{(t)}$ in (9) to get

$\displaystyle\mathbf{w}_{i}^{(t+1)}-\bar{\mathbf{w}}_{c}^{(t+1)}=\big{[}{\mathbf{w}}_{i}^{(t)}-\bar{\mathbf{w}}_{c}^{(t)}\big{]}-\eta_{k}\mathbf{n}_{i}^{(t)}+\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(t)}$
$\displaystyle-\eta_{k}\Big{[}\nabla F_{i}({\mathbf{w}}_{i}^{(t)})-\nabla
F_{i}(\bar{\mathbf{w}}_{c}^{(t)})\Big{]}+\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{[}\nabla
F_{j}({\mathbf{w}}_{j}^{(t)})-\nabla F_{j}(\bar{\mathbf{w}}_{c}^{(t)})\Big{]}$
$\displaystyle-\eta_{k}\Big{[}\nabla
F_{i}(\bar{\mathbf{w}}_{c}^{(t)})-\nabla\bar{F}_{c}(\bar{\mathbf{w}}_{c}^{(t)})\Big{]}.$
(85)

Taking the norm-2 from the both hand sides of the above equality gives us

$\displaystyle\big{\|}\mathbf{e}_{i}^{(t+1)}\big{\|}\leq\|{\mathbf{w}}_{i}^{(t)}-\bar{\mathbf{w}}_{c}^{(t)}\|+\eta_{k}\|\nabla
F_{i}({\mathbf{w}}_{i}^{(t)})-\nabla
F_{i}(\bar{\mathbf{w}}_{c}^{(t)})\|+\eta_{k}\|\mathbf{n}_{i}^{(t)}\|+\eta_{k}\|\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(t)}\|$
$\displaystyle+\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\|\nabla
F_{j}({\mathbf{w}}_{j}^{(t)})-\nabla
F_{j}(\bar{\mathbf{w}}_{c}^{(t)})\|+\eta_{k}\|\nabla
F_{i}(\bar{\mathbf{w}}_{c}^{(t)})-\nabla\bar{F}_{c}(\bar{\mathbf{w}}_{c}^{(t)})\|.$
(86)

Using $\beta$-smoothness of $F_{i}(\cdot)$, $\forall i$, Assumption 2 and
Jensen’s inequality, we further bound the right hand side of (C) as

$\displaystyle\big{\|}\mathbf{e}_{i}^{(t+1)}\big{\|}\leq(1+\eta_{k}\beta)\|\mathbf{e}_{i}^{(t)}\|+\eta_{k}\beta\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\|\mathbf{e}_{j}^{(t)}\|+\eta_{k}\|\mathbf{n}_{i}^{(t)}\|+\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\|\mathbf{n}_{j}^{(t)}\|+\eta_{k}\zeta_{c}.$
(87)

Taking square and expectation of both hand sides of the above inequality and
using Fact 1 (See Page 1) gives us

$\displaystyle\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t+1)}\big{\|}^{2}]}\leq$
$\displaystyle(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\big{\|}^{2}]}+\eta_{k}\beta\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\sqrt{\mathbb{E}[\|\mathbf{e}_{i}^{(t)}\|^{2}]}+\eta_{k}(2\sigma+\zeta_{c}).$
(88)

Next, we establish an upper bound on
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|]^{2}}$.
To determine the bound, we first express $\bar{\mathbf{w}}_{c}^{(t+1)}$ as

$\displaystyle\bar{\mathbf{w}}_{c}^{(t+1)}=\bar{\mathbf{w}}_{c}^{(t)}-\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(t)})-\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(t)}+\Theta_{c}^{(t+1)}\bar{\mathbf{n}}_{c,Loc}^{(t+1)}.$
(89)

Also, $\bar{\mathbf{w}}^{(t+1)}$ can be written as

$\displaystyle\bar{\mathbf{w}}^{(t+1)}=\bar{\mathbf{w}}^{(t)}-\eta_{k}\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\nabla
F_{j}(\mathbf{w}_{j}^{(t)})-\eta_{k}\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\mathbf{n}_{j}^{(t)}+\sum\limits_{c=1}^{N}\varrho_{c}\Theta_{c}^{(t+1)}\bar{\mathbf{n}}_{c,Loc}^{(t+1)}.$
(90)

Subtracting (89) from (90) and performing some algebraic manipulations gives
us

$\displaystyle\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}=\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}-\eta_{k}\Big{[}\nabla\bar{F}_{c}(\bar{\mathbf{w}}_{c}^{(t)})-\nabla\bar{F}_{c}(\bar{\mathbf{w}}^{(t)})\Big{]}$
$\displaystyle-\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(t)}+\eta_{k}\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\mathbf{n}_{j}^{(t)}-\sum\limits_{d=1}^{N}\varrho_{d}\Theta_{d}^{(t+1)}\bar{\mathbf{n}}_{d,Loc}^{(t+1)}+\Theta_{c}^{(t+1)}\bar{\mathbf{n}}_{c,Loc}^{(t+1)}$
$\displaystyle-\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{[}\nabla
F_{j}(\mathbf{w}_{j}^{(t)})-\nabla
F_{j}(\bar{\mathbf{w}}_{c}^{(t)})\Big{]}+\eta_{k}\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\Big{[}\nabla
F_{j}(\mathbf{w}_{j}^{(t)})-\nabla F_{j}(\bar{\mathbf{w}}_{d}^{(t)})\Big{]}$
$\displaystyle+\eta_{k}\sum\limits_{d=1}^{N}\varrho_{d}\Big{[}\nabla\bar{F}_{d}(\bar{\mathbf{w}}_{d}^{(t)})-\nabla\bar{F}_{d}(\bar{\mathbf{w}}^{(t)})\Big{]}-\eta_{k}\Big{[}\nabla\bar{F}_{c}(\bar{\mathbf{w}}^{(t)})-\nabla
F(\bar{\mathbf{w}}^{(t)})\Big{]}.$ (91)

Taking the norm-2 of both hand sides of the above equality along with applying
the triangle inequality results in

$\displaystyle\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|\leq\left\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\right\|+\eta_{t}\left\|\nabla\bar{F}_{c}(\bar{\mathbf{w}}_{c}^{(t)})-\nabla\bar{F}_{c}(\bar{\mathbf{w}}^{(t)})\right\|$
$\displaystyle+\eta_{k}\|\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(t)}\|+\eta_{k}\|\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\mathbf{n}_{j}^{(t)}\|+\|\sum\limits_{d=1}^{N}\varrho_{d}\Theta_{d}^{(t+1)}\bar{\mathbf{n}}_{d,Loc}^{(t+1)}\|+\Theta_{c}^{(t+1)}\|\bar{\mathbf{n}}_{c,Loc}^{(t+1)}\|$
$\displaystyle+\eta_{k}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\|\nabla
F_{j}(\mathbf{w}_{j}^{(t)})-\nabla
F_{j}(\bar{\mathbf{w}}_{c}^{(t)})\|+\eta_{k}\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\|\nabla
F_{j}(\mathbf{w}_{j}^{(t)})-\nabla F_{j}(\bar{\mathbf{w}}_{d}^{(t)}))\|$
$\displaystyle+\eta_{k}\sum\limits_{d=1}^{N}\varrho_{d}\|\nabla\bar{F}_{d}(\bar{\mathbf{w}}_{d}^{(t)})-\nabla\bar{F}_{d}(\bar{\mathbf{w}}^{(t)})\|+\eta_{k}\|\nabla\bar{F}_{c}(\bar{\mathbf{w}}^{(t)})-\nabla
F(\bar{\mathbf{w}}^{(t)})\|.$ (92)

Using Assumption 2 and Jensen’s inequality, we further bound the right hand
side of (C) to get

$\displaystyle\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|\leq(1+\eta_{k}\beta)\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|+\eta_{k}\beta\sum\limits_{d=1}^{N}\varrho_{d}\|\bar{\mathbf{w}}_{d}^{(t)}-\bar{\mathbf{w}}^{(t)}\|+\eta_{k}\|\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j}^{(t)}\|$
$\displaystyle+\eta_{k}\|\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\mathbf{n}_{j}^{(t)}\|+\|\sum\limits_{d=1}^{N}\varrho_{d}\Theta_{d}^{(t+1)}\bar{\mathbf{n}}_{d,Loc}^{(t+1)}\|+\Theta_{c}^{(t+1)}\|\bar{\mathbf{n}}_{c,Loc}^{(t+1)}\|$
$\displaystyle+\eta_{k}\beta\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\|\mathbf{e}_{j}^{(t)}\|+\eta_{k}\beta\sum\limits_{d=1}^{N}\varrho_{d}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}\|\mathbf{e}_{j}^{(t)}\|+\eta_{k}\zeta.$
(93)

To obtain the one-step behavior of
$\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}$,
we take square and expectation from both hand sides of the above inequality
and using Fact 1 (See Page 1) to get

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}+\eta_{k}\beta\sum\limits_{d=1}^{N}\varrho_{d}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{d}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}\beta\epsilon_{c,k}+\eta_{k}\beta\epsilon_{k}+\eta_{k}(2\sigma+\zeta)+\sqrt{\mathbb{E}\|\sum\limits_{d=1}^{N}\varrho_{d}\Theta_{d}^{(t+1)}\bar{\mathbf{n}}_{d,Loc}^{(t+1)}\|^{2}}+\Theta_{c}^{(t+1)}\sqrt{\mathbb{E}\|\bar{\mathbf{n}}_{c,Loc}^{(t+1)}\|^{2}}.$
(94)

To bound
$\sqrt{\mathbb{E}\|\sum\limits_{d=1}^{N}\varrho_{d}\Theta_{d}^{(t)}\bar{\mathbf{n}}_{d,Loc}^{(t+1)}\|^{2}}$
and $\sqrt{\mathbb{E}\|\bar{\mathbf{n}}_{c,Loc}^{(t+1)}\|^{2}}$ above, we
first apply the law of total expectation to obtain

$\displaystyle\mathbb{E}[\|\bar{\mathbf{n}}_{c,Loc}^{(t+1)}\|^{2}]$
$\displaystyle=p_{c}\cdot\mathbb{E}\Big{[}\Big{\|}\widetilde{\mathbf{n}}_{c,Loc}^{(t+1)}\Big{\|}^{2}\Big{|}\widetilde{\mathbf{n}}_{c,Loc}^{(t+1)}\sim\mathcal{N}(0,\bar{\sigma}_{Loc}^{2})\Big{]}+(1-p_{c})\cdot\mathbb{E}\Big{[}\Big{\|}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\mathbf{n}_{j,Loc}^{(t+1)}\Big{\|}^{2}\Big{|}\mathbf{n}_{j,Loc}^{(t+1)}\sim\mathcal{N}(0,\sigma_{Loc}^{2})\Big{]}$
$\displaystyle\overset{(i)}{=}p_{c}\underbrace{\mathbb{E}\Big{[}\Big{\|}\widetilde{\mathbf{n}}_{c,Loc}^{(t+1)}\Big{\|}^{2}\Big{|}\widetilde{\mathbf{n}}_{c,Loc}^{(t+1)}\sim\mathcal{N}(0,\bar{\sigma}_{Loc}^{2})\Big{]}}_{(a_{1})}+(1-p_{c})\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\underbrace{\mathbb{E}\Big{[}\Big{\|}\mathbf{n}_{j,Loc}^{(t+1)}\Big{\|}^{2}\Big{|}\mathbf{n}_{j,Loc}^{(t+1)}\sim\mathcal{N}(0,\sigma_{Loc}^{2})\Big{]}}_{(a_{2})}.$
(95)

where $(i)$ comes from the fact that $\mathbf{n}_{j,Loc}^{(t)}$ are i.i.d.
random variables for $j\in\mathcal{S}_{c}$. To bound $(a_{1})$ in the above
inequality, we show that

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\widetilde{\mathbf{n}}_{c,Loc}^{(t+1)}\Big{\|}^{2}\Big{|}\widetilde{\mathbf{n}}_{c,Loc}^{(t+1)}\sim\mathcal{N}(0,\bar{\sigma}_{Loc}^{2})\Big{]}=\mathbb{E}\left[\sum\limits_{n=0}^{M-1}(\bar{n}_{\\{c,n\\},Loc}^{(t+1)})^{2}\right]=\sum\limits_{n=0}^{M-1}\mathbb{E}\left[(\bar{n}_{\\{c,n\\},Loc}^{(t+1)})^{2}\right]=M\bar{\sigma}_{Loc}^{2},$
(96)

where
$\bar{\mathbf{n}}_{c,Loc}^{(t+1)}=(\bar{n}_{\\{c,0\\},Loc}^{(t+1)},\bar{n}_{\\{c,1\\},Loc}^{(t+1)},\cdots,\bar{n}_{\\{c,M-1\\},Loc}^{(t+1)})$.
Similarly, to bound $(a_{2})$, we show that

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\mathbf{n}_{j,Loc}^{(t)}\Big{\|}^{2}\Big{|}\mathbf{n}_{j,Loc}^{(t+1)}\sim\mathcal{N}(0,\sigma_{Loc}^{2})\Big{]}=\mathbb{E}\left[\sum\limits_{n=0}^{M-1}(n_{\\{j,n\\},Loc}^{(t+1)})^{2}\right]=\sum\limits_{n=0}^{M-1}\mathbb{E}\left[(n_{\\{j,n\\},Loc}^{(t+1)})^{2}\right]=M\sigma_{Loc}^{2},$
(97)

where
$\mathbf{n}_{j,Loc}^{(t+1)}=(n_{\\{j,0\\},Loc}^{(t+1)},n_{\\{j,1\\},Loc}^{(t+1)},\cdots,n_{\\{j,M-1\\},Loc}^{(t+1)})$.
Replacing (46) and (47) into (C) gives us

$\displaystyle\mathbb{E}[\|\bar{\mathbf{n}}_{c,Loc}^{(t+1)}\|^{2}]=M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}.$
(98)

Similarly, we can also use (96), (97) and the fact that
$\bar{\mathbf{n}}_{c,Loc}^{(t)}$ are i.i.d. random variables for
$c=1,2,\cdots,N$ to obtain

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\sum\limits_{d=1}^{N}\varrho_{d}\Theta_{d}^{(t+1)}\bar{\mathbf{n}}_{d,Loc}^{(t+1)}\Big{\|}^{2}\Big{]}$
$\displaystyle=\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\mathbb{E}[\|\bar{\mathbf{n}}_{d,Loc}^{(t+1)}\|^{2}]$
$\displaystyle=M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)},$
(99)

Replacing (98) and (C) into (C) yields

$\displaystyle\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t+1)}-\bar{\mathbf{w}}^{(t+1)}\|^{2}]}\leq(1+\eta_{k}\beta)\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{c}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}+\eta_{k}\beta\sum\limits_{d=1}^{N}\varrho_{d}\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{d}^{(t)}-\bar{\mathbf{w}}^{(t)}\|^{2}]}$
$\displaystyle+\eta_{k}\beta\epsilon_{c,k}+\eta_{k}\beta\epsilon_{k}+\eta_{k}(2\sigma+\zeta)+\sqrt{M\sum\limits_{d=1}^{N}\varrho_{d}^{2}\Theta_{d}^{(t+1)}\Big{(}p_{d}\bar{\sigma}_{Loc}^{2}+(1-p_{d})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{d}}\rho_{j,d}^{2}\Big{)}}$
$\displaystyle+\Theta_{c}^{(t+1)}\sqrt{M\Big{(}p_{c}\bar{\sigma}_{Loc}^{2}+(1-p_{c})\sigma_{Loc}^{2}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}^{2}\Big{)}}.$
(100)

∎

######  Lemma 3.

Under Assumption 2, we have

$\displaystyle-\eta_{k}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\left[\nabla
F(\bar{\mathbf{w}}^{(t_{k})})^{\top}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\right]\leq-\frac{\eta_{k}\tau}{2}\Big{\|}\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\Big{\|}^{2}$
$\displaystyle-\frac{\eta_{k}}{2}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}+\frac{\eta_{k}\beta^{2}}{2}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\bar{\mathbf{w}}^{(\ell)}-\mathbf{w}_{j}^{(\ell)}\Big{\|}^{2}+\frac{\eta_{k}^{3}\beta^{2}\tau^{2}G^{2}}{2}.$

###### Proof.

Since
$-2\mathbf{a}^{\top}\mathbf{b}=-\|\mathbf{a}\|^{2}-\|\mathbf{b}\|^{2}+\|\mathbf{a}-\mathbf{b}\|^{2}$
holds for any two vectors $\mathbf{a}$ and $\mathbf{b}$ with real elements, we
have

$\displaystyle-\eta_{k}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\left[\nabla
F(\bar{\mathbf{w}}^{(t_{k})})^{\top}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\right]$
$\displaystyle=\frac{\eta_{k}}{2}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\bigg{[}-\Big{\|}\nabla
F(\bar{\mathbf{w}}^{(t_{k})})\Big{\|}^{2}-\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}$
$\displaystyle+\underbrace{\Big{\|}\nabla
F(\bar{\mathbf{w}}^{(t_{k})})-\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}}_{(a)}\bigg{]}.$ (101)

Applying Assumption 2, we further bound $(a)$ above as

$\displaystyle\Big{\|}\nabla
F(\bar{\mathbf{w}}^{(t_{k})})-\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}$
$\displaystyle\overset{(i)}{\leq}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\nabla
F_{j}(\bar{\mathbf{w}}^{(t_{k})})-\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}$
$\displaystyle\overset{(ii)}{\leq}\beta^{2}\underbrace{\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\bar{\mathbf{w}}^{(t_{k})}-\mathbf{w}_{j}^{(\ell)}\Big{\|}^{2}}_{(b)},$
(102)

where $(i)$ involves the application of Jensen’s inequality, and $(ii)$
utilizes the $\beta$-smoothness of $F_{i}(\cdot)$ as described in Assumption
2. We further upper bound term $(b)$ as follows:

$\displaystyle\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\bar{\mathbf{w}}^{(t_{k})}-\mathbf{w}_{j}^{(\ell)}\Big{\|}^{2}=\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\bar{\mathbf{w}}^{(t_{k})}-\bar{\mathbf{w}}^{(\ell)}+\bar{\mathbf{w}}^{(\ell)}-\mathbf{w}_{j}^{(\ell)}\Big{\|}^{2}$
$\displaystyle\leq\Big{\|}\bar{\mathbf{w}}^{(t_{k})}-\bar{\mathbf{w}}^{(\ell)}\Big{\|}^{2}+\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\bar{\mathbf{w}}^{(\ell)}-\mathbf{w}_{j}^{(\ell)}\Big{\|}^{2},$
(103)

where, in the last step, we used the fact that
$\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}(\bar{\mathbf{w}}^{(t_{k})}-\bar{\mathbf{w}}^{(\ell)})^{\top}(\bar{\mathbf{w}}^{(\ell)}-\mathbf{w}_{j}^{(\ell)})=0$.
Upper bound (C) with (C) and (C) yields

$\displaystyle-\eta_{k}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\left[\nabla
F(\bar{\mathbf{w}}^{(t_{k})})^{\top}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\right]\leq-\tau\mu\eta_{k}(F(\bar{\mathbf{w}}^{(t_{k})})-F(\mathbf{w}^{*}))$
$\displaystyle-\frac{\eta_{k}}{2}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\Big{\|}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\nabla
F_{j}(\mathbf{w}_{j}^{(\ell)})\Big{\|}^{2}+\frac{\eta_{k}\beta^{2}}{2}\underbrace{\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\Big{\|}\bar{\mathbf{w}}^{(t_{k})}-\bar{\mathbf{w}}^{(\ell)}\Big{\|}^{2}}_{(c)}$
$\displaystyle+\frac{\eta_{k}\beta^{2}}{2}\sum\limits_{\ell={t_{k}}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\Big{\|}\bar{\mathbf{w}}^{(\ell)}-\mathbf{w}_{j}^{(\ell)}\Big{\|}^{2}.$
(104)

We can further upper bound $(c)$ as follows:

$\displaystyle\sum\limits_{\ell=t_{k}}^{t_{k+1}-1}\Big{\|}\bar{\mathbf{w}}^{(t_{k})}-\bar{\mathbf{w}}^{(\ell)}\Big{\|}^{2}\leq\eta_{k}^{2}\tau\left\|\sum\limits_{m=t_{k}}^{t_{k+1}-1}\sum\limits_{c=1}^{N}\varrho_{c}\sum\limits_{j\in\mathcal{S}_{c}}\rho_{j,c}\widehat{\mathbf{g}}_{j}^{(m)}\right\|^{2}\overset{(c-i)}{\leq}\eta_{k}^{2}\tau^{2}G^{2},$
(105)

where last step results from the clipping operation. Replacing the result of
(105) into (C) concludes the proof. ∎

######  Fact 1.

Consider $n$ random real-valued vectors
$\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\in\mathbb{R}^{m}$, the following
inequality holds:

$\sqrt{\mathbb{E}\left[\Big{\|}\sum\limits_{i=1}^{n}\mathbf{x}_{i}\Big{\|}^{2}\right]}\leq\sum\limits_{i=1}^{n}\sqrt{\mathbb{E}[\|\mathbf{x}_{i}\|^{2}]}.$
(106)

###### Proof.

Note that

$\displaystyle\sqrt{\mathbb{E}\left[\Big{\|}\sum\limits_{i=1}^{n}\mathbf{x}_{i}\Big{\|}^{2}\right]}=\sqrt{\sum\limits_{i,j=1}^{n}\mathbb{E}[\mathbf{x}_{i}^{\top}\mathbf{x}_{j}]}\overset{(a)}{\leq}\sum\limits_{i,j=1}^{n}\sqrt{\mathbb{E}[\|\mathbf{x}_{i}\|^{2}]\mathbb{E}[\|\mathbf{x}_{j}\|^{2}]]}=\sum\limits_{i=1}^{n}\sqrt{\mathbb{E}[\|\mathbf{x}_{i}\|^{2}]},$
(107)

where $(a)$ follows from Holder’s inequality,
$\mathbb{E}[|XY|]\leq\sqrt{\mathbb{E}[|X|^{2}]\mathbb{E}[|Y|^{2}]}$. ∎

######  Fact 2.

Let $a\geq 0$, $b\geq 0$ and $n\geq 1$ (or $n\geq 0$ if $n$ integer). Then, it
follows $a^{n}-b^{n}\leq(a-b)na^{n-1}$.

###### Proof.

Let $\phi(x)\triangleq a^{n}-(a+x)^{n}$. Since $\phi(x)$ is a concave function
of $x\geq-a$, it follows that
$a^{n}-b^{n}=\phi(b-a)\leq\phi(0)+\phi^{\prime}(0)(b-a)=(a-b)na^{n-1}$. ∎