# Provable Privacy Advantages of Decentralized Federated Learning via
Distributed Optimization

Wenrui Yu1, Qiongxiu Li12, , Milan Lopuhaä-Zwakenberg, Mads Græsbøll
Christensen, , and Richard Heusdens W. Yu is with the CISPA Helmholtz Center
for Information Security, Germany.Q. Li and M.G. Christensen are with Aalborg
University, Denmark.M. Lopuhaä-Zwakenberg is with University of Twente, the
Netherlands.R. Heusdens is with Netherlands Defence Academy and Delft
University of Technology, the Netherlands.1Equal contribution, 2Corresponding
author: Qiongxiu Li.Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Federated learning (FL) emerged as a paradigm designed to improve data privacy
by enabling data to reside at its source, thus embedding privacy as a core
consideration in FL architectures, whether centralized or decentralized.
Contrasting with recent findings by Pasquini et al., which suggest that
decentralized FL does not empirically offer any additional privacy or security
benefits over centralized models, our study provides compelling evidence to
the contrary. We demonstrate that decentralized FL, when deploying distributed
optimization, provides enhanced privacy protection - both theoretically and
empirically - compared to centralized approaches. The challenge of quantifying
privacy loss through iterative processes has traditionally constrained the
theoretical exploration of FL protocols. We overcome this by conducting a
pioneering in-depth information-theoretical privacy analysis for both
frameworks. Our analysis, considering both eavesdropping and passive adversary
models, successfully establishes bounds on privacy leakage. In particular, we
show information theoretically that the privacy loss in decentralized FL is
upper bounded by the loss in centralized FL. Compared to the centralized case
where local gradients of individual participants are directly revealed, a key
distinction of optimization-based decentralized FL is that the relevant
information includes differences of local gradients over successive iterations
and the aggregated sum of different nodes’ gradients over the network. This
information complicates the adversary’s attempt to infer private data. To
bridge our theoretical insights with practical applications, we present
detailed case studies involving logistic regression and deep neural networks.
These examples demonstrate that while privacy leakage remains comparable in
simpler models, complex models like deep neural networks exhibit lower privacy
risks under decentralized FL. Extensive numerical tests further validate that
decentralized FL is more resistant to privacy attacks, aligning with our
theoretical findings.

###### Index Terms:

Federated learning, privacy preservation, information theory, distribution
optimization, ADMM, PDMM.

##  I Introduction

Federated Learning (FL) enables collaborative model training across multiple
participants/nodes/clients without directly sharing each node’s raw data [1].
FL can operate on either a centralized/star topology or a decentralized
topology, as shown in Figure 1 [2]. The prevalent centralized topology
requires a central server that interacts with each and every node
individually. The main procedure of a centralized FL protocol typically
unfolds in three steps: 1) Nodes train local models based on their own private
dataset and transmit model updates, such as gradients, to the server; 2) The
server aggregates the local models to a global model and redistributes to the
nodes; 3) Nodes update the local models based on the global model and send the
model updates back to the server. The process is iteratively repeated until
convergence. However, a centralized server is not always feasible due to its
high communication demands and the need for universal trust from all nodes. In
addition, it poses a risk of a single point of failure, making the network
vulnerable to targeted attacks. As an alternative, decentralized FL
circumvents these issues by facilitating direct data exchanges between
(locally) connected nodes, thereby eliminating the need for a central server
for model aggregation.

Decentralized FL protocols, also known as peer-to-peer learning protocols,
fall into two main categories. The first involves average-consensus-based
protocols. With these protocols, instead of sending model parameters to a
central server, nodes collaborate together to perform model aggregation nodes
in a distributed manner. The aggregation is typically done by partially
averaging the local updates within a node’s neighborhood. Examples of these
protocols are the empirical methods where the aggregation is done using
average consensus techniques such as gossiping SGD [3], D-PSGD [4], and
variations thereof [5, 6]. The second category comprises protocols that are
based on distributed optimization, referred to as optimization-based
decentralized FL. These (iterative) methods directly formulate the underlying
problem as a constrained optimization problem and employ distributed solvers
like ADMM [7, 8, 9] or PDMM [10, 11, 12] to solve them. The constraints are
formulated in such a way that, upon convergence, the learned models at all
nodes are identical. Hence, there is no explicit separation between updating
local models and the update of the global model, i.e., the three steps in
centralized FL mentioned before are executed simultaneously.

Despite not directly sharing private data with servers or nodes, FL is shown
vulnerable to privacy attacks as the exchanged information, such as gradients
or weights, still poses a risk for privacy leakage. Existing work on privacy
leakage predominantly focuses on the centralized case. A notable example is
the gradient inversion attack [13, 14, 15, 16, 17, 18, 19, 20, 21, 22], an
iterative method for finding input data that produce a gradient similar to the
gradient generated by the private data. Such attacks are based on the
assumption that similar gradients are produced by similar data samples.

Figure 1: Two topologies in federated learning

In exploring the privacy aspects of centralized versus decentralized FL, many
works claim that the decentralized FL is more privacy-preserving than
centralized FL without any privacy argument [23, 24, 25]. The main idea is
that sensitive information, such as private data, model weights, and user
states, can no longer be observed or controlled through a single server.
However, recent empirical findings challenge such a claim, particularly for
average-consensus-based decentralized FL protocols. It is shown in [26] that
these protocols may not inherently offer better privacy protections over
centralized FL, and might even increase susceptibility to privacy breaches.
For instance, it has been shown that an arbitrary colluding client could
potentially obtain the same amount of information as a central server in
centralized FL when inverting input private data via gradients. In contrast,
the privacy implications of optimization-based decentralized FL protocols
have, to the best of our knowledge, been rarely investigated. This research
gap is partly due to the fact that analytically tracking the privacy leakage
in distributed algorithms, particularly over multiple iterations, is very
challenging. The main difficulty lies in distinguishing and comprehending how
information is correlated between these iterations.

###  I-A Paper contribution

In this paper, we take the first step to perform a theoretical privacy
analysis of both centralized and decentralized FL frameworks by analyzing the
information flow within the network. Our key contributions are summarized
below:

  * •

_Analytical privacy bounds of decentralized FL_ : We conduct an information-
theoretical privacy analysis of both centralized and decentralized FL
protocols, using mutual information as a key metric. To the best of our
knowledge, this is the first information-theoretical privacy analysis in this
context. Notably, we derive two privacy bounds for the optimization-based
decentralized FL and show that its privacy loss is upper bounded by the loss
of centralized FL (Theorem 1 in Section V). We further exemplify the derived
privacy gap through two applications, including logistic regression and Deep
Neural Networks (DNNs).

  * •

_Empirical validation through privacy attacks_ : For DNN applications, we show
that in the case of optimization-based decentralized FL, gradient inversion
attacks can be applied to reconstruct the original input data, but the
reconstruction performance is degraded compared to centralized FL due to the
limited amount of information available to the adversary. A similar trend is
also observed when evaluated using membership inference attacks. Overall,
decentralized FL employing distributed optimization is shown to be less
vulnerable to privacy attacks compared to centralized FL, consistent with our
theoretical findings. This finding challenges the previous belief that
decentralized FL offers no privacy advantages compared to centralized FL [26]
(see Section VIII-E for a detailed explanation).

###  I-B Outline and Notation

The paper is organized as follows. Section II reviews necessary fundamentals,
and Section III introduces the involved metrics for quantifying privacy.
Section IV introduces the optimization-based decentralized FL protocol.
Section V analyzes the privacy of both centralized and decentralized FL
protocols and states the main result. Section VI analyzes logistic regression
example. Section VII, VIII analyze the application of DNNs. Conclusions are
given in Section IX.

We use bold lowercase letters to denote vectors $\bm{x}$ and bold uppercase
letters for matrices $\bm{X}$. Calligraphic letters $\mathcal{X}$ denotes
sets. The $i$th entry of a vector $\bm{x}$ is denoted $\bm{x}_{i}$. The
superscript $(\cdot)^{\intercal}$ denotes matrix transposition. $\bm{I}$ is
used to denote the identity matrix of appropriate dimensions. $\bm{0}$ and
$\bm{1}$ are the all-zero and all-one vectors. $\nabla$ denotes the gradient.
The value of the variable $\bm{x}$ at iteration $t$ is denoted as
$\bm{x}^{(t)}$. We use $\|\cdot\|$ to indicate the $\ell_{2}$-norm and
$\mathrm{ran}(\cdot)$ and $\mathrm{ker}(\cdot)$ to denote the range and kernel
of their argument, respectively. For the sake of notational simplicity, we
represent random variables using capital letters, regardless of whether its
outcome is a scalar, a vector, or a matrix.
$M\left(\bm{x},i\right):=\mathbbm{1}\\{(\cdot,\bm{x})\in\mathcal{D}\\}$ is the
indicator variable showing whether $\bm{x}$ is in the dataset $\mathcal{D}$.

##  II Preliminaries

This section reviews the necessary fundamentals for the remainder of the
paper.

###  II-A Centralized FL

Without loss of generality, we focus on classification problems involving $n$
nodes, each with its local dataset
$\\{(\bm{x}_{ik},\ell_{ik}):k=1,\ldots,n_{i}\\}$, where
$\bm{x}_{ik}\in\mathbb{R}^{v}$ represents an input sample,
$\ell_{ik}\in\mathbb{R}$ is the associated label and $n_{i}$ is the number of
input samples. The dimension $v$ of the data samples is application-dependent.
Collecting the $\bm{x}_{ik}$s and $\ell_{ik}$s, we define
$\bm{x}_{i}=(\bm{x}^{\intercal}_{i1},\ldots,\bm{x}^{\intercal}_{in_{i}})^{\intercal}$
and $\bm{\ell}_{i}=(\ell_{i1},\ldots,\ell_{in_{i}})^{\intercal}$. Let
$f_{i}(\bm{w}_{i},(\bm{x}_{i},\bm{\ell}_{i}))$ denote the cost function of
node $i$ where $\bm{w}_{i}\in\mathbb{R}^{u}$ is the model weight to be learned
from the input dataset $(\bm{x}_{i},\bm{\ell}_{i})$, whose dimension, again,
depends on the application. In the remainder of the paper we will omit the
$(\bm{x}_{i},\bm{\ell}_{i})$ dependency for notational convenience when it is
clear from the context and simply write $f_{i}(\bm{w}_{i})$. A typical
centralized FL protocol works as follows:

  1. 1.

Initialization: at iteration $t=0$, the central server randomly initializes
the weights $\bm{w}_{i}^{(0)}$ for each node.

  2. 2.

Local model training: at each iteration $t$, each user $i$ first receives the
model updates from the server and then computes its local gradient, denoted as
$\nabla f_{i}(\bm{w}_{i}^{(t)})$, using its local data $\bm{x}_{i}$.

  3. 3.

Model aggregation: the server collects these local gradients and performs
aggregation to update the global model. The aggregation is often done by
weighted averaging and typically uniform weights are applied, i.e.,
$\frac{1}{n}\operatorname*{\textstyle\sum}_{i=1}^{n}\nabla
f_{i}(\bm{w}_{i}^{(t)})$. Subsequently, each node $i$ then updates its own
model weight by

$\displaystyle\bm{w}_{i}^{(t+1)}=\bm{w}_{i}^{(t)}-\frac{\mu}{n}\operatorname*{\textstyle\sum}_{i=1}^{n}\nabla
f_{i}(\bm{w}_{i}^{(t)}),$ (1)

where $\mu$ is a constant controlling the convergence rate. The last two steps
are repeated until the global model converges or until a predetermined
stopping criterion is reached.

This algorithm is often referred to as the FedAvg [1].

###  II-B Decentralized FL

Decentralized FL works for cases where a trusted centralized server is not
available. In such cases, it works on a so-called distributed network which is
often modeled as an undirected graph: $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
with $\mathcal{V}={\\{1,2,...,n}\\}$ representing the node set and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ representing the edge set.
$\mathcal{N}_{i}=\\{j\,|\,{(i,j)\in\mathcal{E}\\}}$ denotes the set of
neighboring nodes of node $i$. In this decentralized setup, each node $i$ can
only communicate with its neighboring nodes $j\in{\cal N}_{i}$, facilitating
peer-to-peer communication without any centralized coordination.

####  II-B1 Average consensus-based approaches

The model aggregation step requires all nodes’ local gradients. Many
decentralized FL protocols work by deploying distributed average consensus
algorithms to compute the average of local gradients, i.e., computing
$\frac{1}{n}\operatorname*{\textstyle\sum}_{i=1}^{n}\nabla
f_{i}(\bm{w}_{i}^{(t)})$ in Eq. 1 without any centralized coordination.
Example average consensus algorithms are gossip [27] and linear iterations
[28], which allow peer-to-peer communication over distributed networks.

The common decentralized FL often works similarly to the FedAvg algorithm,
except for the step of model aggregation. For instance, D-PSGD [4, 29] uses
gossip averaging with neighbors to implement the aggregation, i.e.,

$\displaystyle\bm{w}_{i}^{(t+1)}=\bm{w}_{i}^{(t)}-\frac{\mu}{d_{i}}\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\nabla
f_{j}(\bm{w}_{j}^{(t)}),$ (2)

where $d_{i}=|\mathcal{N}_{i}|$ is the degree of node $i$.

####  II-B2 Distributed optimization-based approaches

The goal of optimization-based decentralized FL is to collaboratively learn a
global model, given the local datasets $\\{(\bm{x}_{i},\bm{\ell}_{i}):i\in\cal
V\\}$, without any centralized coordination. The underlying problem can be
posed as a constrained optimization problem given by

$\displaystyle\begin{array}[]{ll}{\min\limits_{\big{\\{}\bm{w}_{i}\,:\,i\in\cal
V\big{\\}}}}&\operatorname*{\textstyle\sum}\limits_{i\in\mathcal{V}}f_{i}(\bm{w}_{i}),\\\
\text{subject to}&\forall(i,j)\in{\cal E}:{\bm{B}_{i\mid
j}}{{\bm{w}}_{i}}+{\bm{B}_{j\mid
i}}{{\bm{w}}_{j}}=\bm{0},\rule[11.38109pt]{0.0pt}{0.0pt}\end{array}$ (5)

where $\bm{B}_{i\mid j}$ and $\bm{B}_{i\mid j}$ define linear edge
constraints. To ensure all nodes share the same model at convergence
(consensus constraints) we have $\bm{B}_{i\mid j}=-\bm{B}_{j\mid
i}=\pm\bm{I}$. In the following, we will use the convention that
$\bm{B}_{i|j}=\bm{I}$ if $i<j$ and $\bm{B}_{i|j}=-\bm{I}$ otherwise.

In what follows we will refer to centralized FL as CFL. While decentralized FL
encompasses both average consensus-based and distributed optimization-based
approaches (recall Section II-B), for simplicity, we will use the abbreviation
DFL to specifically refer to the optimization-based decentralized FL as it is
our main focus. We will differentiate between the two methods in contexts
where such distinction is necessary to avoid confusion.

###  II-C Threat models

We consider two types of adversary models: the eavesdropping and the passive
(also known as honest-but-curious) adversary model. While eavesdropping can
typically be addressed through channel encryption [30], it remains a pertinent
concern in our context. This relevance stems from the nature of iterative
algorithms, where communication channels are utilized repeatedly, continuously
encrypting each and every message incurs high communication overhead.
Therefore, in our framework, we assume that network communication generally
occurs over non-secure channels, except for the initial network setup phase,
details of which will be discussed later (see Section IV). The passive
adversary consists of a number of colluding nodes, referred to as corrupt
nodes, which comply with the algorithm instructions but utilize the received
information to infer the private input data of the other so-called honest
nodes. Consequently, the adversary has access to the following information:
(a) all information gathered by the corrupt nodes, and (b) all messages
transmitted over unsecured (i.e., non-encrypted) channels.

##  III Privacy evaluation

When quantifying privacy, there are mainly two types of metrics: 1) empirical
evaluation which assesses the susceptibility of the protocol against
established privacy attacks, and 2) information-theoretical metrics which
offer a robust theoretical framework independent of empirical attacks. In this
paper, we first evaluate privacy via an information-theoretical metric and
then deploy empirical attacks to validate our theoretical results.

###  III-A Information-theoretical privacy metric

Among the information-theoretical metrics, popular ones include for example 1)
$\epsilon$-differential privacy [31, 32] which guarantees that the posterior
guess of the adversary relating to the private data is only slightly better
(quantified by $\epsilon$) than the prior guess; 2) mutual information [33]
which quantifies statistically how much information about the private data is
revealed given the adversary’s knowledge, In this paper, we choose mutual
information as the information-theoretical privacy metric. The main reasons
are the following. Mutual information has been proven effective in measuring
privacy losses in distributed settings [34], and has been applied in various
applications [35, 36, 37, 38, 39]. Secondly, mutual information is
intrinsically linked to $\epsilon$-differential privacy (see [40] for more
details) and is more feasible to realize in practice [41, 42].

####  III-A1 Fundamentals of mutual information

Given two (discrete) random variables $X$ and $Y$, the mutual information
$I(X;Y)$ between $X$ and $Y$ is defined as

$\displaystyle I(X;Y)=H(X)-H(X|Y),$ (6)

where $H(X)$ represents the Shannon entropy of $X$ and $H(X|Y)$ is the
conditional Shannon entropy, assuming they exist.111In cases of continuous
random variables we substitute both entropies by the differential entropy,
thus $I(X;Y)=h(X)-h(X|Y)$. It follows that $I(X;Y)=0$ when $X$ and $Y$ are
independent, indicating that $Y$ carries no information about $X$. Conversely,
$I(X;Y)$ is maximal when $Y$ and $X$ share a one-to-one correspondence.

Denote $\mathcal{V}_{h}$ and $\mathcal{V}_{c}$ as the set of honest and
corrupt nodes, respectively. Let $\mathcal{O}$ denote the set of information
obtained by the adversary. Hence, the privacy loss, measured by the mutual
information between the private data $\bm{x}_{i}$ of honest node
$i\in\mathcal{V}_{h}$ and the knowledge available to the adversary, is given
by

$\displaystyle I(X_{i};\mathcal{O}).$ (7)

###  III-B Empirical evaluation via privacy attacks

To complement our theoretical analysis, we incorporate empirical privacy
attacks to validate our findings. In machine learning, based on the nature of
the disclosed private data, privacy breaches typically fall into three types:
membership inference [43, 44, 45], the property inference [44, 46] and the
input reconstruction attack [47, 48, 49, 50], where the revealed information
is membership (whether a particular data sample belongs to the training
dataset or not), properties of the input such as age and gender, and the input
training data itself, respectively. Given that Eq. 7 measures how much
information about the input training data is revealed, we align our empirical
evaluation by mainly focusing on input reconstruction attacks. In FL, the
gradient inversion attack has been extensively studied for its effectiveness
in reconstructing input samples (see Section VIII-C for extended results using
membership inference attacks).

####  III-B1 Gradient inversion attack

The gradient inversion attack typically works by iteratively refining an
estimate of the private input data to align with the observed gradients
generated by such data. For each node’s local dataset
$(\bm{x}_{i},\bm{\ell}_{i})$, the goal of the adversary is to recover the
input data $(\bm{x}_{i},\bm{\ell}_{i})$ based on the observed gradient. A
typical setup is given by [13]:

$\displaystyle(\bm{x}_{i}^{\prime*},\bm{\ell}_{i}^{\prime*})=\underset{\bm{x}_{i}^{\prime},\bm{\ell}_{i}^{\prime}}{\arg\min}\big{\|}\nabla
f_{i}(\bm{w}_{i},(\bm{x}^{\prime}_{i},\bm{\ell}^{\prime}_{i}))-\nabla
f_{i}(\bm{w}_{i},(\bm{x}_{i},\bm{\ell}_{i}))\big{\|}^{2},$ (8)

and many variants thereof are proposed [14, 15, 16, 17, 18, 19, 20, 21, 22].
To evaluate the quality of reconstructed inputs, we use the widely adopted
structural similarity index measure (SSIM) [51] to measure the similarity
between the reconstructed images and true inputs. The SSIM index ranges from
$-1$ to $1$, where $\pm 1$ signifies perfect resemblance and $0$ indicates no
correlation.

Analytical label recovery via local gradient: While it appears that both the
input data $\bm{x}_{i}$ and its label $\bm{\ell}_{i}$ in Eq. 8 require
reconstruction through optimization, existing work normally assumes that the
label is already known. This is because the label can often be analytically
inferred from the shared gradients [14, 45]. The main reason is as follows.
Consider a classification task where the neural network has $L$ layers and is
trained with cross-entropy loss. Assume $n_{i}=1$ for simplicity (one data
sample at each node). Let $\bm{y}=(y_{1},\ldots,y_{C})$ denote the outputs
(logits), where $y_{i}$ is the score (confidence) predicted for the $i$th
class. With this, the cross-entropy loss over one-hot labels is given by

$f_{i}(\bm{w}_{i})=-\log\big{(}\frac{e^{y_{\ell_{i}}}}{\operatorname*{\textstyle\sum}_{j}e^{y_{j}}}\big{)}=\log\big{(}\textstyle\operatorname*{\textstyle\sum}_{j}e^{y_{j}}\big{)}-y_{\ell_{i}},$
(9)

where $\log(\cdot)$ denotes the natural logarithm. Let $\bm{w}_{i,L,c}$ denote
the weights in the output layer $L$ corresponding to output $y_{c}$. The
gradient of $f_{i}(\bm{w}_{i})$ with respect to $\bm{w}_{i,L,c}$ can then be
expressed as [14]:

$\displaystyle\nabla^{\prime}f_{i}(\bm{w}_{i,L,c})\triangleq\frac{\partial
f_{i}(\bm{w}_{i})}{\partial\bm{w}_{i,L,c}}=\frac{\partial
f_{i}(\bm{w}_{i})}{\partial y_{c}}\frac{\partial
y_{c}}{\partial\bm{w}_{i,L,c}}=g_{c}\bm{a}_{L-1},$ (10)

where $\bm{a}_{L-1}$ is the activation at layer $L-1$ and $g_{c}$ is the
gradient of the cross entropy Eq. 9 with respect to logit $c$:

$g_{c}=\frac{e^{y_{c}}}{\operatorname*{\textstyle\sum}_{j}e^{y_{j}}}-\delta_{c,\ell_{i}},$
(11)

where $\delta_{c,\ell_{i}}$ is the Kronecker-delta, defined as
$\delta_{c,\ell_{i}}=1$ when $c=\ell_{i}$ and $\delta_{c,\ell_{i}}=0$
otherwise. Consequently, $g_{c}<0$ for $c=\ell_{i}$ and $g_{c}>0$ otherwise.
Since the activation $\bm{a}_{L-1}$ is independent of the class index $c$, the
ground-truth label $\ell_{i}$ can be inferred from the shared gradients since
$\nabla^{\prime\intercal}f_{i}(\bm{w}_{i,L,\ell_{i}})\nabla^{\prime}f_{i}(\bm{w}_{i,L,c})=g_{\ell_{i}}g_{c}\|\bm{a}_{L-1}\|^{2}<0$
for $c\neq\ell_{i}$ and positive only for $c=\ell_{i}$. When dealing with
$n_{i}>1$, recovering labels becomes more challenging, yet feasible approaches
are available. One example approach shown in [45] leverages the fact that the
gradient magnitude is proportional to the label frequency in untrained models.
Hence, in the centralized FL case, label information can often be deduced from
the shared gradients thus improving both the efficiency and accuracy of the
reconstructed input $\bm{x}_{i}^{\prime*}$ when compared to the real private
input $\bm{x}_{i}$ [14]. While for the decentralized FL protocol, we will show
that the label information cannot be analytically computed for certain cases,
thereby inevitably decreasing both the efficiency and reconstruction quality
(see details in Remark 4).

##  IV DFL using distributed optimizers

This section introduces distributed solvers considered in this work, explains
pivotal convergence properties relevant to subsequent privacy analyses, and
gives details of the decentralized protocol using distributed optimization
techniques.

###  IV-A Distributed optimizers

Given the optimization problem Eq. 5, many distributed optimizers, notably
ADMM [52] and PDMM [10, 11] have been proposed. From a monotone operator
theory perspective [53, 11], ADMM can be seen as a $\frac{1}{2}$-averaged
version of PDMM, allowing both to be analyzed within the same theoretical
framework. Due to the averaging, ADMM is generally slower than PDMM, assuming
it converges. Both ADMM and PDMM solve the optimization problem Eq. 5
iteratively, with the update equations for node $i$ given by:

$\displaystyle\bm{w}_{i}^{(t)}=\arg\min_{\bm{w}_{i}}\big{(}f_{i}(\bm{w}_{i})+\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{z}_{i|j}^{(t)\intercal}\bm{B}_{i|j}\bm{w}_{i}+\frac{\rho
d_{i}}{2}\bm{w}_{i}^{2}\big{)},$ (12) $\displaystyle\forall
j\in\mathcal{N}_{i}:\bm{z}_{j|i}^{(t+1)}=(1-\theta)\bm{z}_{j|i}^{(t)}+\theta\big{(}\bm{z}_{i|j}^{(t)}+2\rho\bm{B}_{i|j}\bm{w}_{i}^{(t)}\big{)},$
(13)

where $\rho$ is a constant controlling the rate of convergence. The parameter
$\theta\in(0,1]$ controls the operator averaging with $\theta=\frac{1}{2}$
(Peaceman-Rachford splitting) yielding ADMM and $\theta=1$ (Douglas-Rachford
splitting) leading to PDMM. $\bm{z}$ is called auxiliary variable having
entries indicated by $\bm{z}_{i|j}$ and $\bm{z}_{j|i}$, held by node $i$ and
$j$, respectively, related to edge $(i,j)\in\mathcal{E}$. Eq. 12 updates the
local variables (weights) $\bm{w}_{i}$, whereas Eq. 13 represents the exchange
of data in the network through the auxiliary variables $\bm{z}_{j|i}$.

###  IV-B Differential A/PDMM

The optimality condition for Eq. 12 is given by222Note that ADMM can also be
applied to non-differentiable problems where the optimality condition can be
expressed in terms of subdifferentials: $0\in\partial
f_{i}(\bm{w}_{i}^{(t)})+\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\bm{z}_{i|j}^{(t)}+\rho
d_{i}\bm{w}_{i}^{(t)}$.

$\displaystyle\;\;\bm{0}=\nabla
f_{i}(\bm{w}_{i}^{(t)})+\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\bm{z}_{i|j}^{(t)}+\rho
d_{i}\bm{w}_{i}^{(t)}.$ (14)

Given that the adversary can eavesdrop all communication channels, by
inspection of Eq. 14, transmitting the auxiliary variables $\bm{z}_{j|i}$
would expose $\nabla f_{i}(\bm{w}_{i}^{(t)})$, as $\bm{w}_{i}^{(t)}$ can be
determined from Eq. 13. Encrypting $\bm{z}_{j|i}^{(t)}$ at every iteration
would address this, albeit at prohibitive computational expenses. To
circumvent this, only initial values $\bm{z}_{j|i}^{(0)}$ are securely
transmitted and
$\Delta\bm{z}_{j|i}^{(t+1)}=\bm{z}_{j|i}^{(t+1)}-\bm{z}_{j|i}^{(t)}$ being
unencrypted in subsequent iterations [54, 55]. Consequently, upon receiving
$\Delta\bm{z}_{j|i}^{(t+1)}$, $\bm{z}_{j|i}^{(t+1)}$ is reconstructed as

$\displaystyle\bm{z}_{j|i}^{(t+1)}=\bm{z}_{j|i}^{(t)}+\Delta\bm{z}_{j|i}^{(t+1)}=\operatorname*{\textstyle\sum}_{\tau=1}^{t+1}\Delta\bm{z}_{j|i}^{(\tau)}+\bm{z}_{j|i}^{(0)}.$
(15)

Let $t_{\max}$ denote the maximum number of iteration and denote
$\mathcal{T}=\\{0,1,\ldots,t_{\max}\\}$. Hence, eavesdropping only uncovers

$\big{\\{}\Delta\bm{z}_{j\mid
i}^{(t+1)}:(i,j)\in\mathcal{E},t\in\mathcal{T}\big{\\}},$ (16)

and $\bm{z}_{j|i}^{(t+1)}$ remains undisclosed unless the initialized
$\bm{z}_{j|i}^{(0)}$ is known.

###  IV-C DFL using differential A/PDMM

ADMM is guaranteed to converge to the optimal solution for arbitrary convex,
closed and proper (CCP) objective functions $f_{i}$, whereas PDMM will
converge in the case of differentiable and strongly convex functions [11].
Recently, it has been shown that these solvers are also effective when applied
to non-convex problems like training DNNs [12]. Note that for complex non-
linear applications such as training DNNs, although exact solutions of Eq. 12
are usually unavailable, convergence analysis of approximated solutions has
been extensively investigated. For instance, it is shown in [12] that PDMM,
using quadratic approximations, achieves good performance for non-convex tasks
such as training DNNs. Moreover, convergence guarantees with quantized
variable transmissions are investigated in [56].

Details of DFL using differential A/PDMM solvers are summarized in Algorithm
1. Note that at the initialization it requires that each node randomly
initialize $z_{i|j}^{(0)}$ from independent distributions having variance
$\sigma^{2}_{Z}$ and sends it to neighbor $j\in\mathcal{N}_{i}$ via secure
channels, also referred to as the subspace perturbation technique [57, 55].
The core concept involves introducing noise into the auxiliary variable
$\bm{z}$ to obscure private data from potential exposure, while the
convergence of $\bm{w}$ is not affected. To explain this idea, consider Eq. 13
in a compact form:

$\displaystyle\bm{z}^{(t+1)}$
$\displaystyle=(1-\theta)\bm{z}^{(t)}+\theta\left(\bm{P}\bm{z}^{(t)}+2c\bm{P}\bm{C}\bm{w}^{(t)}\right),$
(17)

where $\bm{C}=[\bm{B}_{+}^{\top},\bm{B}_{-}^{\top}]^{\top}$ and $\bm{B}_{+}$
and $\bm{B}_{-}$ contains the positive and negative entries of $\bm{B}$,
respectively. Additionally, $\bm{P}$ is a permutation matrix that interchanges
the upper half rows and lower half rows of the matrix it multiplies, leading
to $\bm{P}\bm{C}=[\bm{B}_{-}^{\top},\bm{B}_{+}^{\top}]^{\top}$. Denote
$\Psi=\mathrm{ran}(\bm{C})+\mathrm{ran}(\bm{P}\bm{C})$, its orthogonal
complement is denoted by
$\Psi^{\perp}=\ker(\bm{C}^{\top})\cap\ker((\bm{P}\bm{C})^{\top})$. Let
$\bm{\Pi}_{\Psi}$ represent the orthogonal projection. We can then decompose
$\bm{z}$ into components within $\Psi$ and $\Psi^{\perp}$ as
$\bm{z}^{(t)}=\bm{z}_{\Psi}^{(t)}+\bm{z}_{\Psi^{\perp}}^{(t)}$. Note that the
component $\bm{z}_{\Psi^{\perp}}^{(t)}$ is not null, requiring that the number
of edges should be no smaller than the number of nodes. This condition is,
however, not met in CFL with a star topology.

It has been proven in [54] that

$\displaystyle\bm{z}_{\Psi^{\perp}}^{(t)}=\frac{1}{2}\left(\bm{z}_{\Psi^{\perp}}^{(0)}+\bm{P}\bm{z}_{\Psi^{\perp}}^{(0)}\right)+\frac{1}{2}(1-2\theta)^{t}\left(\bm{z}_{\Psi^{\perp}}^{(0)}-\bm{P}\bm{z}_{\Psi^{\perp}}^{(0)}\right).$

Thus, for a given graph structure and $\theta$, $\bm{z}_{\Psi^{\perp}}^{(t)}$
depends solely on the initialization of the auxiliary variable $\bm{z}^{(0)}$.
Consequently, if $\bm{z}_{i|j}^{(0)}$ is not known by the adversary, so does
$\bm{z}_{i|j}^{(t)}$ for subsequent iterations. This is key that privacy
advantages can be provided when compared to centralized FL (in Remark 1 we
will analyze the privacy loss for CFL when applying a similar trick).

Algorithm 1 Decentralized FL via A/PDMM

Each node $i$ randomly initializes $z_{i|j}^{(0)}$ from independent
distributions having variance $\sigma^{2}_{Z}$ and sends to neighbor
$j\in\mathcal{N}_{i}$ via secure channels.

for $t=0,1,...$ do

for each node $i\in\mathcal{V}$ in parallel do

$\bm{w}_{i}^{(t)}=$

$\displaystyle\quad\arg\min_{\bm{w}_{i}}\big{(}f_{i}\big{(}\bm{w}_{i}\big{)}+\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{z}_{i\mid
j}^{(t)\bm{\top}}\bm{B}_{i\mid j}\bm{w}_{i}+\frac{\rho
d_{i}}{2}\bm{w}_{i}^{2}\big{)}$

for each $j\in\mathcal{N}_{i}$ do

$\bm{z}_{j\mid i}^{(t+1)}=(1-\theta)\bm{z}_{j\mid
i}^{(t)}+\theta\big{(}\bm{z}_{i\mid j}^{(t)}+2\rho\bm{B}_{i\mid
j}\bm{w}_{i}^{(t)}\big{)}$

$\Delta\bm{z}_{j\mid i}^{(t+1)}=\bm{z}_{j\mid i}^{(t+1)}-\bm{z}_{j\mid
i}^{(t)}$

end for

end for

for each $i\in\mathcal{V}$, $j\in\mathcal{N}_{i}$ do

$\text{Node}_{j}\leftarrow\text{Node}_{i}(\Delta\bm{z}_{j\mid i}^{(t+1)})$

end for

for each $i\in\mathcal{V}$, $j\in\mathcal{N}_{i}$ do

$\bm{z}_{j\mid i}^{(t+1)}=\bm{z}_{j\mid i}^{(t)}+\Delta\bm{z}_{j\mid
i}^{(t+1)}$

end for

end for

##  V Privacy analysis

In this section, we conduct the comparative analysis of privacy loss in both
CFL and DFL protocols, specifically focusing on the FedAvg algorithm and the
decentralized approach introduced in Algorithm 1. For simplicity, we will
primarily consider the case $\theta=1$, i.e., PDMM, but the results can be
readily extended to arbitrary $\theta\in(0,1]$.

###  V-A Privacy loss of CFL

In CFL, the transmitted messages include the initial model weights
$\bm{w}_{j}^{(0)}$, and the local gradients $\nabla f_{j}(\bm{w}_{j}^{(t)})$
at all iterations $t\in\mathcal{T}$ of all nodes $j\in{\cal V}$. Hence, by
inspection of Eq. 1, we conclude that knowledge of local gradients and initial
weights $\bm{w}_{j}^{(0)}$ is sufficient to compute all updated model weights
$\bm{w}_{j}^{(t)}$ at every $t\in\mathcal{T}$. Hence, the eavesdropping
adversary has the following knowledge

$\displaystyle\\{\nabla
f_{j}(\bm{w}_{j}^{(t)}),\bm{w}_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}}.$
(18)

The passive adversary, on the other hand, has the following knowledge

$\displaystyle\\{\bm{x}_{j},\bm{w}_{j}^{(t)},\nabla
f_{j}(\bm{w}_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}}.$ (19)

Combining both sets, the privacy loss, quantified by the mutual information
between the private data $\bm{x}_{i}$ and the knowledge available to the
adversary (as in Eq. 7), is given by

$\displaystyle I(X_{i};\mathcal{O}_{\rm{CFL}})$
$\displaystyle=I(X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{\nabla
f_{j}(W_{j}^{(t)}),W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}}).$ (20)

######  Remark 1.

We could securely transmit the initialized model weights $\bm{w}_{j}^{(0)}$ in
CFL, analogous to the initial auxiliary variable $\bm{z}_{j|i}^{(0)}$ in DFL.
However, such secure transmission would not reduce the privacy loss in Section
V-A. The main reason is that at convergence all local models will be
identical, i.e., $\bm{w}_{j}^{(t_{\max})}=\bm{w}_{k}^{(t_{\max})}$ for
$(j,k)\in\mathcal{E}$. Thus, as long as there is one corrupt node, the passive
adversary has knowledge of all $\bm{w}_{j}^{(t_{\max})}$s. By inspecting Eq. 1
we can see that the difference $\bm{w}_{j}^{(t+1)}-\bm{w}_{j}^{(t)}$ at every
iteration is known, and thus $\bm{w}_{j}^{(0)}$ for all $j\in{\cal V}$.

###  V-B Privacy loss of DFL

By inspection of Algorithm 1, the eavesdropping adversary can intercept all
messages transmitted along non-secure channels, thus having access to:

$\displaystyle\\{\Delta\bm{z}_{j|k}^{(t+1)}\\}_{(j,k)\in\mathcal{E},t\in\mathcal{T}}.$
(21)

For any edge in the network, the transmitted information will be known by the
passive adversary as long as one end node is corrupt. Accordingly, we define
$\mathcal{E}_{h}=\\{(j,k)\in\mathcal{V}_{h}\times\mathcal{V}_{h}\\}$,
$\mathcal{E}_{c}=\mathcal{E}\setminus\mathcal{E}_{h}$ as the set of honest and
corrupt edges, respectively. Given that the passive adversary can collect all
information obtained by the corrupt nodes, by inspecting Algorithm 1 it thus
has the knowledge of
$\\{\bm{x}_{j}\\}_{j\in\mathcal{V}_{c}}\cup\\{\bm{z}_{j\mid
k}^{(0)},\Delta\bm{z}_{j\mid
k}^{(t+1)}\\}_{(j,k)\in\mathcal{E}_{c},t\in\mathcal{T}}$. Combining this with
the eavesdropping knowledge in Eq. 21 we conclude that the adversary has the
following knowledge:

$\displaystyle\\{\bm{x}_{j}\\}_{j\in\mathcal{V}_{c}}\cup\\{\bm{z}_{j\mid
k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}}\cup\\{\Delta\bm{z}_{j\mid
k}^{(t+1)}\\}_{(j,k)\in\mathcal{E},t\in\mathcal{T}}.$

The information loss of an honest node $i\in\mathcal{V}_{h}$’s private data is
thus given by

$\displaystyle I(X_{i};\mathcal{O}_{\rm{DFL}})$
$\displaystyle=I(X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{Z_{j\mid
k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}},\\{\Delta Z_{j\mid
k}^{(t+1)}\\}_{(j,k)\in\mathcal{E},t\in\mathcal{T}}),$ (22)

We first give some initial results on the information that can be deduced by
the adversary.

######  Proposition 1.

Let $\mathcal{G}_{h}=({\mathcal{V}}_{h},\mathcal{E}_{h})$ be the subgraph of
$\mathcal{G}$ after eliminating all corrupt nodes. Let
$\mathcal{G}_{h,1},\ldots,\mathcal{G}_{h,k_{h}}$ denote the components of
$\mathcal{G}_{h}$ and let ${\mathcal{V}}_{h,k}$ be the vertex set of
$\mathcal{G}_{h,k}$. Without loss of generality, assume the honest nodes $i$
belong to the first honest component, i.e., $i\in\mathcal{V}_{h,1}$. The
adversary has the following knowledge about node $i\in{\cal V}_{h,1}$:

  * i)

Noisy local gradients:

$\displaystyle\forall t\in\mathcal{T}:\nabla
f_{i}(\bm{w}_{i}^{(t)})+\operatorname*{\textstyle\sum}_{k\in\mathcal{N}_{i,h}}\bm{B}_{i|k}\bm{z}_{i|k}^{(0)}$
(23)

  * ii)

Difference of local gradients:

$\displaystyle\forall t\in\mathcal{T}:\nabla f_{i}(\bm{w}_{i}^{(t+1)})-\nabla
f_{i}(\bm{w}_{i}^{(t)}),$ (24)

  * iii)

The aggregated sum of local gradients in honest component $\mathcal{G}_{h,1}$:

$\displaystyle\forall t\in\mathcal{T}:\sum_{j\in\mathcal{V}_{h,1}}\nabla
f_{j}(\bm{w}_{j}^{(t)}).$ (25)

###### Proof.

See Appendix A. ∎

We now proceed to present the main result of this paper. In particular, we
will show that the information loss of DFL is dependent on the variance of
initialized $\bm{z}^{(0)}$, i.e., $\sigma^{2}_{Z}$. Notably, in the special
case where $\sigma^{2}_{Z}=0$, all local gradients will be exposed similar to
the case of centralized FL. In contrast, when $\sigma^{2}_{Z}$ approaches
infinity, the term Eq. 23 contains no information about the private data or
the local gradient, theoretically leading to $I(X_{i};\nabla
f_{i}(W_{i}^{(t)})+\operatorname*{\textstyle\sum}_{k\in\mathcal{N}_{i,h}}\bm{B}_{i|k}Z_{i|k}^{(0)})=0$.
More specifically, we have the following privacy bounds.

######  Theorem 1 (Privacy bounds of DFL).

We have

$\displaystyle I$
$\displaystyle(X_{i};\mathcal{O}_{\rm{CFL}})\stackrel{{\scriptstyle(a)}}{{\geq}}I(X_{i};\mathcal{O}_{\rm{DFL}})$
$\displaystyle=I\big{(}X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{Z_{j\mid
k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}},\\{Z_{j|k}^{(0)}-Z_{k|j}^{(0)}\\}_{(j,k)\in\mathcal{E}_{h}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla
f_{j}(W_{j}^{(t)})+\operatorname*{\textstyle\sum}_{k\in\mathcal{N}_{j,h}}\bm{B}_{j|k}Z_{j|k}^{(0)}\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}\big{)}$
(26)
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}I\big{(}X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla f_{j}(W_{j}^{(t+1)})-\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,l}}\nabla
f_{j}(W_{j}^{(t)})\\}_{1\leq l\leq k_{h},t\in\mathcal{T}}\big{)},$ (27)

where we have equality in $(a)$ if $\sigma^{2}_{Z}=0$, and equality in $(b)$
if $\sigma^{2}_{Z}\rightarrow\infty$.

###### Proof.

See Appendix B. ∎

Hence, by inspecting the lower bound we can see that except for the knowledge
of the corrupt nodes,
i.e.,$\\{\bm{x}_{j}\\}_{j\in\mathcal{V}_{c}},\\{\bm{w}_{j}^{(t)}\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}},\\{f_{j}(\bm{w}_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}}$,
the revealed information includes the model weights of all honest nodes
$\\{\bm{w}_{j}^{(t)}\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}$, gradient
differences of each honest node over successive iterations $\\{\nabla
f_{j}(\bm{w}_{j}^{(t+1)})-\nabla
f_{j}(\bm{w}_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}$ (note that
$\cup_{1\leq l\leq k_{h}}\mathcal{V}_{h,l}=\mathcal{V}_{h}$), and the sum of
local gradients of the honest nodes
$\\{\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,l}}\nabla
f_{j}(\bm{w}_{j}^{(t)})\\}_{1\leq l\leq k_{h},t\in\mathcal{T}}$ in each
component.

Regarding the feasibility of the lower bound, we have the following remark.

######  Remark 2.

It might seem impractical that the lower bound in Theorem1 requires that the
variance $\sigma^{2}_{Z}$ approaches infinity. For practical applications,
however, like DNNs, a relatively small variance is already sufficient to make
the leaked information in the noisy gradients negligible compared to gradient
differences Eq. 24 and the gradient sum Eq. 25 (we will verify this claim in
Section VII-C).

###  V-C Privacy gap between CFL and DFL

Theorem 1 shows that the privacy loss in DFL is either less than or equal to
that in CFL. This naturally leads to key questions: under what circumstances
does this equality or inequality hold? To analyze the privacy gap we have the
following result, showing that the privacy gap between DFL and CFL is
dependent on how much more information about the private data $X_{i}$ can the
local gradients reveal given the knowledge of DFL, e.g., gradient differences
and the gradient sum.

######  Corollary 1.

Privacy gap between CFL and DFL If the lower bound Eq. 27 is achieved, for an
honest node $i\in\mathcal{V}_{h}$’s private data, the privacy gap between CFL
and DFL is given by

$\displaystyle
I(X_{i};\mathcal{O}_{\rm{CFL}})-I(X_{i};\mathcal{O}_{\rm{DFL}})$
$\displaystyle=I\big{(}X_{i};\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}|\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla f_{j}(W_{j}^{(t+1)})-\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,l}}\nabla
f_{j}(W_{j}^{(t)})\\}_{1\leq l\leq k_{h},t\in\mathcal{T}}\big{)}$ (28)

###### Proof.

See Appendix D in Supplementary. ∎

######  Remark 3.

The privacy gap, as defined in (1), depends on the number of corrupt nodes and
narrows notably in the extreme case where only one honest node remains. By
inspecting (1), we can see that the privacy gap is intrinsically linked to the
sum of gradients from honest nodes within each honest component, specifically,
$\\{\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,l}}\nabla
f_{j}(W_{j}^{(t)})\\}_{1\leq l\leq k_{h},t\in\mathcal{T}}$. As the number of
honest nodes diminishes, the specificity of information conveyed by individual
node gradients increases, consequently reducing the privacy gap. In the most
extreme scenario, where only one node is honest, i.e.,
$\mathcal{V}_{h}=\\{i\\}$, the privacy gap reduces to zero since
(1)$=I\big{(}X_{i};\\{\nabla f_{i}(W_{i}^{(t)})\\}_{t\in\mathcal{T}}|\\{\nabla
f_{i}(W_{i}^{(t)})\\}_{t\in\mathcal{T}}\big{)}=0$.

In the following sections, we delve into two distinct cases to further
investigate the privacy gap. First, we examine a straightforward logistic
regression example, where it’s possible to analytically calculate the privacy
loss. In this instance, we find no discernible privacy gap. Next, we shift our
focus to a more conventional application within FL: DNNs. Through extensive
empirical analysis, we observe a notable privacy gap between CFL and DFL. This
gap highlights DFL’s reduced susceptibility to privacy attacks when compared
to CFL.

Figure 2: Privacy comparisons of centralized and decentralized logistic
regression. (a) Training loss and (b) Reconstruction error of input data as a
function of iteration number $(t)$ using CFL (blue color) and DFL (red color).

##  VI Logistic regression

Logistic regression is widely adopted in various applications and serves as a
fundamental building block for complex applications. We will first give
analytical derivations and then demonstrate numerical results.

###  VI-A Theoretical analysis

Consider a logistic model with model parameters $\bm{w}_{i}\in\mathbb{R}^{v}$
(weights) and $b_{i}\in\mathbb{R}$ (bias) where each node has a local dataset
$\\{(\bm{x}_{ik},\ell_{ik}):k=1,\ldots,n_{i}\\}$, where
$\bm{x}_{ik}\in\mathbb{R}^{v}$ is an input sample, $\ell_{ik}\in\\{0,1\\}$ is
the associated label. In addition, let
$y_{ik}=\bm{w}_{i}^{T}\bm{x}_{ik}+b_{i}$ denote the output of the model given
the input $\bm{x}_{ik}$. Note that the bias term can be included in the weight
vector. Here we explicitly separate the bias from the true network weights as
it will lead to more insight into how to reconstruct the input data from the
observed gradient information. Correspondingly, $\bm{z}_{i|j}$ is also
separated into $\bm{z}_{w,i|j}$ and $z_{b,i|j}$. With this, the loss (log-
likelihood) function has the form

$\displaystyle f_{i}(\bm{w}_{i},b_{i})$
$\displaystyle=-\operatorname*{\textstyle\sum}_{k=1}^{n_{i}}\big{(}\ell_{ik}\log\frac{1}{1+e^{-y_{ik}}}$
$\displaystyle\quad+(1-\ell_{ik})\log\frac{e^{-y_{ik}}}{1+e^{-y_{ik}}}\big{)}.$
(29)

With this, Eq. 24 becomes

$\displaystyle\frac{\partial
f_{i}}{\partial\bm{w}_{i}}^{\\!\\!\\!(t+1)}-\frac{\partial
f_{i}}{\partial\bm{w}_{i}}^{\\!\\!\\!(t)}=\operatorname*{\textstyle\sum}_{k=1}^{n_{i}}\big{(}\frac{1}{1+e^{-y^{(t+1)}_{ik}}}-\frac{1}{1+e^{-y^{(t)}_{ik}}}\big{)}\bm{x}_{ik}$
$\displaystyle=-\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\Delta\bm{z}_{w,i|j}^{(t)}+\rho
d_{i}\big{(}\bm{w}_{i}^{(t)}-\bm{w}_{i}^{(t+1)}\big{)},$ (30)

and

$\displaystyle\frac{\partial f_{i}}{\partial
b_{i}}^{\\!\\!\\!(t+1)}-\frac{\partial f_{i}}{\partial
b_{i}}^{\\!\\!\\!(t)}=\operatorname*{\textstyle\sum}_{k=1}^{n_{i}}\big{(}\frac{1}{1+e^{-y^{(t+1)}_{ik}}}-\frac{1}{1+e^{-y^{(t)}_{ik}}}\big{)}$
$\displaystyle=-\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\Delta
z_{b,i|j}^{(t)}+\rho d_{i}\big{(}b_{i}^{(t)}-b_{i}^{(t+1)}\big{)},$ (31)

where all terms in the RHS are known by the adversary as the differences of
the local model $\bm{w}_{i}^{(t+1)}-\bm{w}_{i}^{(t)}$ can be determined from
$\Delta{\bm{z}}_{j|i}^{(t+1)}-\Delta{\bm{z}}_{i|j}^{(t)}$ by considering two
successive $\bm{z}$ updates of Eq. 13. As a special case where $n_{i}=1$, Eq.
30 is just a scaled version of $\bm{x}_{ik}$ where the scaling is given by Eq.
31. Hence, with gradient difference, we can analytically compute $\bm{x}_{ik}$
as

$\displaystyle\bm{x}_{ik}=\frac{-\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\Delta\bm{z}_{w,i|j}^{(t)}+\rho
d_{i}\big{(}\bm{w}_{i}^{(t)}-\bm{w}_{i}^{(t+1)}\big{)}}{-\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\Delta
z_{b,i|j}^{(t)}+\rho d_{i}\big{(}b_{i}^{(t)}-b_{i}^{(t+1)}\big{)}}.$

Hence, in this case, one gradient difference at an arbitrary iteration is
sufficient to reveal all information about the private data, i.e.,
$I(X_{i};\nabla f_{j}(W_{j}^{(t+1)})-\nabla
f_{j}(W_{j}^{(t)}))=I(X_{i};X_{i})$ which is maximum. Thus, there is no
privacy gap between CFL and DFL, i.e.,
<EMAIL_ADDRESS>For the case of $n_{i}>1$, the input
$\bm{x}_{ik}$ can also be reconstructed by searching for solutions that fit
for given observations, i.e., Eq. 30 and Eq. 31 across iterations.

###  VI-B Convergence behavior

To validate the theory presented above, we consider a toy example of a random
geometric graph of $n=60$ nodes randomly distributed in the unit cube having a
communication radius $r=\sqrt{2\log n/n}$ to ensure connectivity with high
probability [58]. Detailed settings can be found in the Appendix E in
Supplementary. In Figure 2(a) we demonstrate the convergence performances of
both centralized and decentralized protocols, i.e., the loss Section VI-A,
averaged over all nodes, as a function of the iteration $t$. We can see that
both methods have a similar convergence rate.

###  VI-C Privacy gap between CFL and DFL

To evaluate the performance of input reconstruction, we define the
reconstruction error as the average Euclidean distance between the
reconstructed samples, denoted as $\hat{\bm{x}}_{ik}$, and the original data
samples $\bm{x}_{ik}$ given by
$\frac{1}{n}\operatorname*{\textstyle\sum}_{i=1}^{n}\|\bm{\hat{x}}_{ik}-\bm{x}_{ik}\|_{2}$.
The corresponding errors are plotted as a function of iteration number in
Figure 2(b). We can see that, the reconstruction error of DFL, using gradient
differences, has the same level of error as the CFL case across all
iterations. Hence, we conclude that for the logistic regression example, there
is no privacy gap between CFL and DFL, i.e.,
<EMAIL_ADDRESS>aligning with our theoretical result.

##  VII Deep neural networks I: Convergence and gradient inversion attacks

For DNNs, it is challenging to give an analytical analysis like the above
logistic regression example. We resort to empirical assessments of privacy
leakage through privacy attacks. As we shall see, the empirical evaluation
results are consistent with our theoretical claims.

###  VII-A Convergence behavior

To test the performance of the introduced DFL protocol, we make comparison
between the training process of CFL and DFL. The detailed settings and results
are shown in Appendix E in Supplementary. Notably, the performance of the
decentralized protocol closely aligns with that of the centralized approach.
This aligns with previous research findings [12], which suggests that
decentralized protocols perform comparably to centralized ones, particularly
in scenarios with independently and identically distributed data. The
subsequent section will focus on evaluating their privacy via gradient
inversion attack and membership inference attack, highlighting the privacy
advantages inherent in DFL.

###  VII-B Gradient inversion attack in DFL

Recall that in Proposition 1 we identified three types of information directly
related to the honest node’s local gradient: noisy gradients Eq. 23, gradient
differences Eq. 24, and the gradient sum Eq. 25. Similar to the traditional
gradient inversion attack described in Eq. 8, inputs can be inverted from them
as well. As an example with the gradient sum Eq. 25 the corresponding
optimization problem can be formulated as

$\displaystyle\\{(\bm{x}_{i}^{\prime*},\bm{\ell}_{i}^{\prime*})\\}_{i\in\mathcal{V}_{h}}=\underset{\bm{x}_{i}^{\prime},\bm{\ell}_{i}^{\prime}}{\arg\min}\big{\|}\operatorname*{\textstyle\sum}_{i\in\mathcal{V}_{h,1}}\nabla
f_{i}(\bm{w}_{i}^{(t)},(\bm{x}^{\prime}_{i},\bm{\ell}^{\prime}_{i}))$
$\displaystyle\quad-\operatorname*{\textstyle\sum}_{i\in\mathcal{V}_{h,1}}\nabla
f_{i}(\bm{w}_{i}^{(t)},(\bm{x}_{i},\bm{\ell}_{i}))\big{\|}^{2},$ (32)

Although the gradient inversion attack in the decentralized case looks similar
to the traditional centralized case, there are some important differences, in
particular with respect to label recovery and fidelity of reconstructed
inputs, discussed in the following remarks.

Figure 3:  (a) Averaged SSIM of reconstructed inputs by inverting noisy
gradients, gradient differences, and the gradient sum (blue lines) and test
accuracy (red line) for different variances of initialized auxiliary variable
$\bm{z}^{(0)}$: $\sigma^{2}_{Z}=0,10^{-8},10^{-7},2.5\times
10^{-7},10^{-6},10^{-5},2.5\times 10^{-5}$ and $10^{-4}$. (b) Sample examples
of reconstructed inputs for each case.

######  Remark 4.

Analytical label recovery is no longer applicable given gradient differences
Eq. 24. With gradient differences, Eq. 10 explained in Section III-B1 becomes

$\displaystyle\nabla f(\bm{w}_{i,L,c}^{(t)})-\nabla
f(\bm{w}_{i,L,c}^{(t+1)})=g_{c}^{(t)}\bm{a}_{L-1}^{(t)}-g_{c}^{(t+1)}\bm{a}_{L-1}^{(t+1)}$
$\displaystyle=\big{(}\frac{e^{y^{(t)}_{c}}}{\operatorname*{\textstyle\sum}_{j}e^{y^{(t)}_{j}}}-\delta_{c,\ell_{i}}\big{)}\bm{a}_{L-1}^{(t)}-\big{(}\frac{e^{y^{(t+1)}_{c}}}{\operatorname*{\textstyle\sum}_{j}e^{y^{(t+1)}_{j}}}-\delta_{c,\ell_{i}}\big{)}\bm{a}_{L-1}^{(t+1)}.$

Hence, if $c\neq\ell_{i}$, then both $g_{c}^{(t)}<0$ and $g_{c}^{(t+1)}<0$ so
that we cannot use the sign information of $g_{c}$ to recover the correct
label. Therefore, the adversary needs to consider all labels to find out the
best fit, which inevitably increases the computation overhead and degrades the
fidelity of the reconstructed inputs (see Section VIII-A for numerical
validations).

######  Remark 5.

Bigger component size $|\mathcal{V}_{h,1}|$ in the gradient sum Eq. 25 will
make it more challenging to invert inputs. This is due to the fact that Eq. 25
is related to all data samples of all honest nodes in $\mathcal{V}_{h,1}$,
thus inverting input from Section VII-B is analogous to increase the batchsize
or the total number of data samples in Eq. 8 of the centralized case. It has
been empirically shown in many works [13, 15, 16] that increasing batchsize
will degrade the fidelity of reconstructed inputs severely. We will validate
this result in Section VIII-A.

###  VII-C Optimum attack strategy

To test the performance of gradient inversion attack, we consider a random
geometric graph with $n=50$ nodes. Each node randomly selects $n_{i}$ data
samples from the corresponding dataset and uses a two-layer multilayer
perceptron (MLP) to train the local model. For simplicity, in the following
experiments, we set $n_{i}=2$, unless otherwise specified. We use the approach
proposed in DLG [13] to conduct the gradient inversion attack (see Appendix F
in Supplementary for results of using the cosine similarity-based approach
proposed in [15]).

Figure 4: Performance of reconstructed inputs via inverting gradients (CFL)
and gradient differences (DFL) in terms of iterations $t$: (a) Averaged SSIM
(solid lines) of all reconstructed inputs along with the corresponding
standard derivation (shadows), (b) sample examples of reconstructed inputs at
iteration number $t=1,100,\ldots,900$. Figure 5: Performance comparisons of
CFL and DFL via inverting inputs from gradient differences: (a) Samples images
of ground truth and reconstructed inputs, (b) SSIM comparisons of all
reconstructed inputs for different batch size $n_{i}=1,2,4,8$ using two
datasets MNIST (top) and CIFAR-10 (bottom), respectively.

Figure 6: Performance comparisons of CFL and DFL via inverting inputs from the
gradient sum: (a) Sample images of ground truth and reconstructed inputs, (b)
SSIM of all reconstructed samples for three different sizes of honest
component $|\mathcal{V}_{h,1}|=2,~{}4,~{}8$ using two datasets MNIST (top) and
CIFAR-10 (bottom), respectively. Wherein the red box indicates that the
corresponding samples are from the same component.

Noisy gradients vs. gradient differences vs. the gradient sum As highlighted
in Remark 2, the noisy gradient term vanishes in the lower bound Eq. 27 if the
variance $\sigma^{2}_{Z}\rightarrow\infty$. This raises an important question:
in practice how large should $\sigma^{2}_{Z}$ be to ensure that the
effectiveness of reconstructing inputs from noisy gradients is inferior to
that of other variables, namely gradient differences and the gradient sum. To
investigate this, Figure 3(a) presents a comparative analysis of input
reconstruction performances using noisy gradients, gradient differences, and
the gradient sum (considering two honest nodes in the component, i.e.,
$|\mathcal{V}_{h,1}|=2$), along with the test accuracies of learn models for
different choices using the MNIST dataset. The results indicate that, without
loss of test performance, the effectiveness of inverting inputs from noisy
gradient degrades very fast as $\sigma^{2}_{Z}$ increases, performing worse
than inverting inputs using gradient differences and the gradient sum even at
a very low variance of $\sigma^{2}_{Z}=10^{-5}$. This is further illustrated
in plot (b) where the ground truth digit $8$ can hardly be recognized when
inverting noisy gradient for variance $\sigma^{2}_{Z}\geq 10^{-5}$. This
suggests that in practical scenarios, a small variance $\sigma^{2}_{Z}$ is
sufficient to ensure the lower bound is attached. As a consequence, in what
follows we will evaluate the reconstruction performances via inverting
gradient differences and the gradient sum for the case of DFL.

Optimum attack iteration Given that both CFL and DFL protocols are iterative
processes consisting of numerous iterations, in principle the gradient
inversion attack can deploy all iterations’ information for inverting the
input samples. To identify the most effective attack strategy for such an
attack, we first explore which iteration yields the most effective results for
the gradient inversion attack. In Figure 4(a) we demonstrate the attack
performance, quantified by the averaged SSIM of all reconstructed samples
(illustrated by solid lines) along with their standard derivation (shown as
shadows) of CFL and DFL using gradient differences as a function of iteration
number $t$ using the MNIST dataset. We can see that the SSIM of the
centralized case consistently surpasses those in the decentralized case
throughout all iterations. Unlike the centralized case where the
reconstruction performance remains relatively stable across iterations, the
reconstruction performances of the decentralized case degrade significantly in
later iterations. This trend aligns with the expectation that gradient
differences will approach zero at convergence thereby containing very little
information.

To visualize this phenomenon, Figure 4(b) displays illustrative examples of
both cases at every 100 iterations. The SSIM results are in agreement with
these visual examples; for instance, in the later iterations of the
decentralized case, the ground truth digit $9$ can hardly be recognized.
Hence, the effectiveness of gradient inversion attacks is more pronounced in
the initial iterations. As for the case of inverting inputs via the gradient
sum, we observe the reconstruction performance remains relatively stable
across iterations as the phenomenon in CFL (see Figure 10 in Appendix F in
Supplementary). Note that for both CFL and DFL we observe a slightly better
performance at the early stage. This might be due to the fact that at early
iterations the local models contain more information about the local datasets
while at later iterations the models are more fitted to the global dataset.
For this reason, for the forthcoming Fig 5 and 6, we will focus on exploiting
gradients from early iterations to execute the gradient inversion attacks.

##  VIII Deep neural networks II: privacy gap

We now evaluate the privacy gap between CFL and DFL using different settings
and privacy attacks.

###  VIII-A Evaluating the privacy gap between CFL and DFL using gradient
inversion attack

Inverting gradient differences Eq. 24 In Remark 4 we showed that using
gradient differences labels cannot be analytically computed, unlike in CFL. To
assess the impacts of this on the performance of input reconstructions, Figure
5(a) showcases examples of reconstructed inputs for both the MNIST and
CIFAR-10 dataset for four different batch-sizes, i.e., $n_{i}=1,2,4,8$.
Notable disparities exist in the reconstructed samples of CFL and DFL cases.
More specifically, compared to the centralized case, reconstructing inputs via
gradient differences is less efficient and yields lower quality. The
inefficiency is due to the fact that the adversary needs to iterate through
all possible labels to identify the best fit. Furthermore, the quality is
compromised due to the inherently reduced information in gradient differences
compared to the full gradients. To evaluate the quality of reconstructed
inputs, we chose the best-fit samples among iterated inputs for each batch and
computed their averaged SSIM. The comparison results are presented in Figure
5(b), illustrating the quality of reconstructed inputs of CFL are consistently
better than that in DFL for all batchsizes $n_{i}$. This comparison underlines
the inherent challenges in reconstructing high-quality inputs from gradient
differences in DFL.

Inverting the gradient sum Eq. 25 When inverting inputs from the gradient sum,
it is intuitive that the accuracy of reconstructed inputs tends to diminish as
the size of the honest component $|\mathcal{V}_{h,1}|$ increases, analogous to
the situation of increasing batchsize. This relationship is clearly
illustrated in Figure 6 for the MNIST dataset, showing a direct correlation
between the size of the honest component and the precision of the
reconstructed inputs. It is important to note that while obtaining label
information becomes more challenging in DFL (given the gradient sum), in this
comparison we assume that the label information is known a prior for both CFL
and DFL. However, even with this assumption, the reconstruction performances
of DFL are still notably inferior to that of CFL.

Combining both gradient differences and the gradient sum Since both gradient
differences and the gradient sum are available in DFL, one natural question to
ask is if combining them together will improve the attack performances. We
demonstrate the comparison results in Figure 9 in Appendix F in Supplementary,
showing the SSIM of reconstructed inputs of CFL and DFL across varying
iteration numbers for three different sizes. The results suggest that
combining gradient differences and gradient sum does not amplify the
reconstruction performances. Still, the attack performances of CFL are in
general better than DFL, consistently across all iterations.

###  VIII-B Evaluating privacy gap using other gradient inversion attacks

To determine whether our findings are specific to the type of gradient
inversion attack used, we conducted a comparative analysis using the cosine
similarity-based method proposed in [15]. The comparison results are presented
in Figure 15 and Figure 15 (see Appendix F in Supplementary). From these
results, it’s evident that the performance of DFL is generally inferior to
that of CFL, which is consistent with the findings using DLG [13], as depicted
in Figure 5 and Figure 6. This observation corroborates our theoretical
analysis and suggests that the performance disparity between CFL and DFL is
not dependent on the choice of gradient inversion attack.

###  VIII-C Evaluating privacy gap using membership inference attacks

Apart from gradient inversion attacks, it is also interesting to see if there
is a privacy gap between CFL and DFL when evaluated using membership inference
attacks (MIAs). The attack results and detailed experimental settings are
demonstrated in Fig. 13 in Appendix F in Supplementary. Similar to the case of
using gradient inversion attacks, we can see that CFL leaks more membership
information compared to DFL.

Figure 7: Performance comparisons of CFL and DFL in terms of the portion of
corrupted nodes.

###  VIII-D Privacy gap reduces with more corrupt nodes

We now validate the result presented in Remark 3. As shown in Fig. 7 when
using MNIST datasets, the privacy gap between CFL and DFL predictably narrows
as the number of corrupt nodes increases when using gradient inversion
attacks. Notably, in the case where there is only a single honest node, the
attack performance in DFL converges with that of CFL, effectively closing the
privacy gap. As for the case of using membership inference attacks, we observe
a similar tendency (see Fig.11 in Appendix F in Supplementary). Hence, these
results are consistent with our theoretical findings in Remark 3, thereby
confirming the validity of our analytical approach.

Overall, we conclude that compared to the CFL case, the DFL protocol is less
vulnerable to privacy attacks including gradient inversion attacks and
membership inference attacks.

###  VIII-E Related work

The recent work [26] highlights that prior comparisons between the privacy
implications of CFL and DFL either lack empirical evidence or fail to
comprehensively explore privacy arguments. Consequently, [26] stands as the
only direct and relevant benchmark for our analysis, which contends that DFL
offers no privacy advantages over CFL. However, our study provides a new
perspective and challenges this conclusion. We hypothesize that these
discrepancies may be attributed to the following factors:

  1. 1.

Decentralization Techniques: The decentralization techniques employed are
significantly different. While [26] utilizes average consensus-based
decentralization methods (refer to Section II-B1), our study focuses on
distributed optimization techniques (see Section II-B2). The former approach
separates local and global model updates similar to CFL, whereas the latter
integrates these updates into a joint optimization process.

  2. 2.

Threat Models: [26] examines both passive and active adversary models. In
contrast, our study considers eavesdropping and passive adversary models,
offering a different perspective on potential security risks.

  3. 3.

Theoretical and Empirical Results: While [26] confines its findings to
empirical data, primarily evaluating privacy risks through membership
inference attacks, our research provides a comprehensive analysis includes
both information-theoretical analysis and empirical validations. These
validations encompass gradient inversion attacks as well as membership
inference attacks.

Given these significant methodological divergences, direct comparisons between
our findings and those of [26] are inherently challenging. This highlights the
necessity for more detailed and extensive investigations. We advocate for
continued research in this domain to unravel the complex dynamics that
contribute to these divergent outcomes and to deepen our understanding of
privacy mechanisms within FL frameworks.

##  IX Conclusions

In this paper, we showed that DFL through distributed optimization inherently
provides privacy advantages compared to CFL, particularly in complex settings
like neural networks. We conducted a detailed analysis of the information flow
within the network across various iterations, establishing both upper and
lower bounds for the information loss. The bounds indicate that privacy
leakage in DFL is consistently less than or equal to that in CFL. We further
exemplified our results through two standard applications: logistic regression
and training a DNN. In the case of simple logistic regression, we observed
that the privacy leakage in both CFL and DFL are identical. However, in more
complex scenarios like training DNNs, the privacy loss as measured by the
gradient inversion attack is markedly higher in CFL than in DFL. As expected,
the privacy gap between CFL and DFL is more pronounced in the presence of
numerous honest nodes. Extensive experimental results substantiated our
findings.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proc. Int. Conf. Artif. Intell. Statist., pp. 1273–1282, PMLR, 2017.
  * [2] T. Li, A. K. Sahu, A. Talwalkar and V. Smith, “Federated learning: Challenges, methods, and future directions,” IEEE Signal Process. Mag., vol. 37, no. 3, pp. 50–60, 2020.
  * [3] P. H. Jin, Q. Yuan, F. Iandola, and K. Keutzer, “How to scale distributed deep learning?,” arXiv preprint arXiv:1611.04581, 2016.
  * [4] X. Lian, C. Zhang, H. Zhang, C. Hsieh, W. Zhang and J. Liu, “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,” in Proc. Adv. Neural Inf. Process. Syst., vol. 30, 2017.
  * [5] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu, “D2: Decentralized training over decentralized data,” in Proc. Int. Conf. Mach. Learn., pp. 4848–4856, PMLR, 2018.
  * [6] C. Hu, J. Jiang, and Z. Wang, “Decentralized federated learning: A segmented gossip approach,” arXiv preprint arXiv:1908.07782, 2019.
  * [7] J. M. J. M. Xavier, P. M. Aguiar, and M. Püschel, “D-admm: A communication-efficient distributed algorithm for separable optimization,” IEEE Trans. Signal Process., vol. 61, no. 10, pp. 2718–2723, 2013.
  * [8] W. Li, Y. Liu, Z. Tian, and Q. Ling, “Communication-censored linearized admm for decentralized consensus optimization,” IEEE Trans. Signal Inf. Process. Netw., vol. 6, pp. 18–34, 2019.
  * [9] H. Chen, Y. Ye, M. Xiao, M. Skoglund, and H. Poor, “Coded stochastic admm for decentralized consensus optimization with edge computing,” IEEE Internet Things J., vol. 8, no. 7, pp. 5360–5373, 2021.
  * [10] G. Zhang and R. Heusdens, “Distributed optimization using the primal-dual method of multipliers,” IEEE Trans. Signal Inf. Process. Netw., vol. 4, no. 1, pp. 173–187, 2017.
  * [11] T. Sherson, R. Heusdens, W. B. Kleijn, “Derivation and analysis of the primal-dual method of multipliers based on monotone operator theory,” IEEE Trans. Signal Inf. Process. Netw., vol. 5, no. 2, pp. 334–347, 2018.
  * [12] K. Niwa, N. Harada, G. Zhang, and W. Kleijn, “Edge-consensus learning: Deep learning on p2p networks with nonhomogeneous data,” in Proc. ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, pp. 668–678, 2020.
  * [13] L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” in Proc. Adv. Neural Inf. Process. Syst., vol. 32, 2019.
  * [14] B. Zhao, K. Mopuri, and H. Bilen, “iDLG: Improved deep leakage from gradients,” arXiv preprint arXiv:2001.02610, 2020.
  * [15] J. G. H. Bauermeister, H. Dröge and M. Moeller, “Inverting gradients-how easy is it to break privacy in federated learning?,” in Proc. Adv. Neural Inf. Process. Syst., vol. 33, pp. 16937–16947, 2020.
  * [16] H. Yin, A. Mallya, A. Vahdat, J. Alvarez, J. Kautz, and P. Molchanov, “See through gradients: Image batch recovery via gradinversion,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., pp. 16337–16346, 2021.
  * [17] F. Boenisch, A. Dziedzic, R. Schuster, A. Shamsabadi, I. Shumailov, and N. Papernot, “When the curious abandon honesty: Federated learning is not private,” arXiv preprint arXiv:2112.02918, 2021.
  * [18] J. Geng, Y. Mou, Q. Li, F. Li, O. Beyan, S. Decker, and C. Rong, “Improved gradient inversion attacks and defenses in federated learning,” IEEE Trans. Big Data, 2023.
  * [19] W. Wei, L. Liu, M. Loper, K.-H. Chow, M. Gursoy, S. Truex, and Y. Wu, “A framework for evaluating gradient leakage attacks in federated learning,” arXiv preprint arXiv:2004.10397, 2020.
  * [20] H. Yang, M. Ge, K. Xiang, and J. Li, “Using highly compressed gradients in federated learning for data reconstruction attacks,” IEEE Trans. Inf. Forensics Secur., vol. 18, pp. 818–830, 2022.
  * [21] Z. Zhao, M. Luo, and W. Ding, “Deep leakage from model in federated learning,” arXiv preprint arXiv:2206.04887, 2022.
  * [22] J. Xu, C. Hong, J. Huang, L. Y. Chen, and J. Decouchant, “Agic: Approximate gradient inversion attack on federated learning,” in Proc. 41st Int. Symp. Rel. Distrib. Syst., pp. 12–22, IEEE, 2022.
  * [23] K. Yuan, Q. Ling, and W. Yin, “On the convergence of decentralized gradient descent,” SIAM J. Optim., vol. 26, no. 3, pp. 1835–1854, 2016.
  * [24] H. Cheng, P. Yu, H. Hu, S. Zawad, F. Yan, S. Li, H. Li, and Y. Chen, “Towards decentralized deep learning with differential privacy,” in Proc. Int. Conf. Cloud Comput., pp. 130–145, Springer, 2019.
  * [25] T. Vogels, L. He, A. Koloskova, S. P. Karimireddy, T. Lin, S. U. Stich, and M. Jaggi, “Relaysum for decentralized deep learning on heterogeneous data,” in Proc. Adv. Neural Inf. Process. Syst., vol. 34, pp. 28004–28015, 2021\.
  * [26] D. Pasquini, M. Raynal, and C. Troncoso, “On the (in) security of peer-to-peer decentralized machine learning,” in Proc. IEEE Symp. Secur. Privacy, pp. 418–436, 2023.
  * [27] A. G. Dimakis, S. Kar, J. M. Moura, M. G. Rabbat, and A. Scaglione, “Gossip algorithms for distributed signal processing,” Proc. IEEE, vol. 98, no. 11, pp. 1847–1864, 2010.
  * [28] A. Olshevsky and J. Tsitsiklis, “Convergence speed in distributed consensus and averaging,” SIAM J. Control Optim., vol. 48, no. 1, pp. 33–55, 2009\.
  * [29] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized sgd with changing topology and local updates,” in Proc. Int. Conf. Mach. Learn., p. 5381–5393, PMLR, 2020.
  * [30] D. Dolev, C. Dwork, O. Waarts, M. Yung, “Perfectly secure message transmission,” J. Assoc. Comput. Mach., vol. 40, no. 1, pp. 17-47,, 1993\.
  * [31] C. Dwork, “Differential privacy,” in ICALP, pp. 1–12, 2006.
  * [32] C. Dwork, F. McSherry, K. Nissim, A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Proc. Theory of Cryptography Conf. , pp. 265-284, 2006.
  * [33] T. M. Cover and J. A. Tomas, Elements of information theory.  John Wiley & Sons, 2012.
  * [34] Q. Li, J. S. Gundersen, R. Heusdens and M. G. Christensen, “Privacy-preserving distributed processing: Metrics, bounds, and algorithms,” in IEEE Trans. Inf. Forensics Secur., vol. 16, pp. 2090–2103, 2021.
  * [35] M. Lopuhaä-Zwakenberg, B. $\bm{S}$korić and N. Li, “Information-theoretic metrics for local differential privacy protocols,” arXiv preprint arXiv:1910.07826, 2019.
  * [36] Q. Li, M. Coutino, G. Leus and M. G. Christensen, “Privacy-preserving distributed graph filtering,” in Proc. Eur. Signal Process. Conf., pp. 2155-2159, 2021.
  * [37] S. Yagli, A. Dytso and H.V. Poor, “Information-theoretic bounds on the generalization error and privacy leakage in federated learning,” in Proc. IEEE Int. Workshop Signal Process. Advances Wireless Commun., pp. 1–5, 2020.
  * [38] Y. Bu, S. Zou, and V. V. Veeravalli, “Tightening mutual information-based bounds on generalization error,” IEEE J. Sel. Areas Info. Theory, vol. 1, no. 1, pp. 121–130, 2020.
  * [39] M. L.-Z. Q. Li, J. S. Gundersen and R. Heusdens, “Adaptive differentially quantized subspace perturbation (adqsp): A unified framework for privacy-preserving distributed average consensus,” IEEE Trans. Inf. Forensics Security., 2023.
  * [40] P. Cuff and L. Yu, “Differential privacy as a mutual information constraint,” in Proc. 23rd ACM SIGSAC Conf. Comput. Commun. Secur., pp. 43–54, 2016.
  * [41] M. Gtz, A. Machanavajjhala, G. Wang, X. Xiao, J. Gehrke, “Publishing search logs—a comparative study of privacy guarantees,” IEEE Trans. Knowl. Data Eng., vol. 24, no. 3, pp. 520–532, 2011.
  * [42] A. Haeberlen, B. C. Pierce, A. Narayan, “Differential privacy under fire.,” in Proc. 20th USENIX Conf. Secur., vol. 33, 2011.
  * [43] X. L. M. Xu, “Subject property inference attack in collaborative learning,” in Proc. 12th Int. Conf. Intell. Human Mach. Syst. Cybern., vol. 1, pp. 227–231, IEEE, 2020.
  * [44] L. Melis, C. Song, E. D. Cristofaro, and V. Shmatikov, “Exploiting unintended feature leakage in collaborative learning,” in Proc. IEEE Symp. Secur. Privacy, pp. 691–706, IEEE, 2019.
  * [45] A. Wainakh, F. Ventola, T. Müßig, J. Keim, C. G. Cordero, E. Zimmer, T. Grube, K. Kersting, and M. Mühlhäuser, “User label leakage from gradients in federated learning,” arXiv preprint arXiv:2105.09369, 2021\.
  * [46] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,” in Proc. IEEE Symp. Secur. Privacy, pp. 3–18, 2017.
  * [47] Z. He, T. Zhang, and R. Lee, “Model inversion attacks against collaborative inference,” in 35th Annu. Comput. Secur. Appl. Conf., pp. 148–162, 2019\.
  * [48] 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 IEEE Conf. Comput. Commun., pp. 2512–2520, IEEE, 2019.
  * [49] Z. Yang, J. Zhang, E. Chang, and Z. Liang, “Neural network inversion in adversarial setting via background knowledge alignment,” in 2019 ACM SIGSAC Conf. Comput. Commun. Secur., pp. 225–240, 2019.
  * [50] Y. Zhang, R. Jia, H. Pei, W. Wang, B. Li, and D. Song, “The secret revealer: Generative model-inversion attacks against deep neural networks,” in IEEE/CVF Conf. Comput. Vision Pattern Recognit., pp. 253–261, 2020.
  * [51] Z. Wang, A. Bovik, H. Sheikh, and E. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process., vol. 13, no. 4, pp. 600–612, 2004.
  * [52] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends in Mach. Learn., vol. 3, no. 1, pp. 1–122, 2011.
  * [53] E. Ryu, S. P. Boyd, “Primer on monotone operator methods,” Appl. Comput. Math., vol. 15, no. 1, pp. 3–43, 2016.
  * [54] Q. Li, R. Heusdens and M. G. Christensen, “Communication efficient privacy-preserving distributed optimization using adaptive differential quantization,” Signal Process., 2022.
  * [55] Q. Li, R. Heusdens and M. G. Christensen, “Privacy-preserving distributed optimization via subspace perturbation: A general framework,” in IEEE Trans. Signal Process., vol. 68, pp. 5983 – 5996, 2020.
  * [56] J. A. G. Jonkman, T. Sherson, and R. Heusdens, “Quantisation effects in distributed optimisation,” in Proc. Int. Conf. Acoust., Speech, Signal Process., p. 3649–3653, 2018.
  * [57] Q. Li, R. Heusdens and M. G. Christensen, “Convex optimisation-based privacy-preserving distributed average consensus in wireless sensor networks,” in Proc. Int. Conf. Acoust., Speech, Signal Process., pp. 5895–5899, 2020.
  * [58] J. Dall and M. Christensen, “Random geometric graphs,” Physical Rev. E, vol. 66, no. 1, p. 016121, 2002.
  * [59] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proc. IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
  * [60] L. Deng, “The mnist database of handwritten digit images for machine learning research [best of the web],” IEEE Signal Process. Mag., vol. 29, no. 6, pp. 141–142, 2012.
  * [61] K. Alex, H. Geoffrey, et al., “Learning multiple layers of features from tiny images,” 2009.
  * [62] M. O’Connor, G. Zhang, W. B. Kleijn, and T. D. Abhayapala, “Function splitting and quadratic approximation of the primal-dual method of multipliers for distributed optimization over graphs,” IEEE Trans. Signal Inf. Process. Netw., vol. 4, no. 4, p. 656–666, 2018.
  * [63] J. Li, N. Li, and B. Ribeiro, “Effective passive membership inference attacks in federated learning against overparameterized models,” in Proc. 11th Int. Conf. Learn. Representations, 2022.
  * [64] S. Yeom, I. Giacomelli, M. Fredrikson, and S. Jha, “Privacy risk in machine learning: Analyzing the connection to overfitting,” in IEEE computer security foundations symposium (CSF), pp. 268–282, 2018.
  * [65] L. Song and P. Mittal, “Systematic evaluation of privacy risks of machine learning models,” in USENIX Security Symposium (USENIX), pp. 2615–2632, 2021.

##  Appendix A Proof of Proposition 1

With Eq. 15, the optimality condition Eq. 14 can be expressed as $\forall
i\in\mathcal{V}_{h}$:

$\displaystyle-(\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i,c}}\bm{B}_{i|j}\bm{z}_{i|j}^{(t)}+\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i,h}}\bm{B}_{i|j}\operatorname*{\textstyle\sum}_{\tau=1}^{t}\Delta\bm{z}_{i|j}^{(\tau)}+\rho
d_{i}\bm{w}_{i}^{(t)})$ $\displaystyle=\nabla
f_{i}(\bm{w}_{i}^{(t)})+\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i,h}}\bm{B}_{i|j}\bm{z}_{i|j}^{(0)}.$
(33)

Since all terms in the LHS of (A) are known by the adversary, the noisy
gradient (RHS of (A)) is known by the adversary, proving claim $i)$. As for
Eq. 24, since the noise term the RHS of (A) does not depend on $t$, the
difference

$\displaystyle\nabla f(\bm{w}_{i}^{(t+\ell)})-\nabla f(\bm{w}_{i}^{(t)}),$

is known for any $\ell\geq 1$, hence proving claim $ii)$. Moreover, by summing
up the RHS of Appendix A over all honest nodes in $\mathcal{V}_{h,1}$, we have

$\displaystyle\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,1}}\left(\nabla
f_{j}(\bm{w}_{j}^{(t)})+\operatorname*{\textstyle\sum}_{k\in\mathcal{N}_{j,h}}\bm{B}_{j|k}\bm{z}_{j|k}^{(0)}\right)$
$\displaystyle=\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,1}}\nabla
f_{j}(\bm{w}_{j}^{(t)})+\operatorname*{\textstyle\sum}_{(j,k)\in\mathcal{E}_{h,1}}\bm{B}_{j|k}(\bm{z}_{j|k}^{(0)}-\bm{z}_{k|j}^{(0)}),$
(34)

since $\bm{B}_{k|j}=-\bm{B}_{j|k}$.

The difference between two successive $\bm{z}$ updates of Eq. 13 is given by

$\displaystyle\Delta{\bm{z}}_{j|i}^{(t+1)}-\Delta{\bm{z}}_{i|j}^{(t)}=2\rho\bm{B}_{i|j}(\bm{w}_{i}^{(t)}-\bm{w}_{i}^{(t-1)}).$
(35)

Hence, given the fact that at convergence we have
$\bm{w}_{j}^{(t_{\max})}=\bm{w}_{k}^{(t_{\max})}$ for all $(j,k)\in{\cal E}$,
the adversary has knowledge of all $\bm{w}_{j}^{(t)},j\in{\cal V},t\in{\cal
T}$. Moreover, again from Eq. 13, we have

$\displaystyle\Delta{\bm{z}}_{j|i}^{(t+1)}$
$\displaystyle=\bm{z}_{i|j}^{(t)}-\bm{z}_{j|i}^{(t)}+2\rho\bm{B}_{i|j}\bm{w}_{i}^{(t)}$
$\displaystyle=\sum_{\tau=1}^{t}\left(\Delta{\bm{z}}_{i|j}^{(\tau)}-\Delta{\bm{z}}_{j|i}^{(\tau)}\right)+\bm{z}_{i|j}^{(0)}-\bm{z}_{j|i}^{(0)},$
(36)

showing that knowing the $\Delta{\bm{z}}_{i|j}^{(t+1)}$s is equivalent to
knowing the differences $\bm{z}_{i|j}^{(0)}-\bm{z}_{j|i}^{(0)}$ for all
$(i,j)\in{\cal E}$.

Hence, the last term in the RHS of (34) is known to the adversary, the sum of
gradients is thus known which completes the proof of claim $iii)$.

##  Appendix B Proof of Theorem 1

We have

$\displaystyle I(X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{Z_{j\mid
k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}},\\{\Delta Z_{j\mid
k}^{(t+1)}\\}_{(j,k)\in\mathcal{E},t\in\mathcal{T}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}I\big{(}X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{Z_{j\mid
k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}},\\{W_{j}^{(t)},\big{.}$
$\displaystyle\quad\big{.}Z_{j|k}^{(0)}-Z_{k|j}^{(0)}\\}_{(j,k)\in\mathcal{E},t\in\mathcal{T}}\big{)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}I\big{(}X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{Z_{j\mid
k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}},\\{W_{j}^{(t)},\big{.}$
$\displaystyle\quad\big{.}\nabla
f_{j}(W_{j}^{(t)})+\operatorname*{\textstyle\sum}_{k\in\mathcal{N}_{j}}\bm{B}_{j|k}Z_{j|k}^{(0)},Z_{j|k}^{(0)}-Z_{k|j}^{(0)}\\}_{(j,k)\in\mathcal{E},t\in\mathcal{T}}\big{)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}I\big{(}X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{Z_{j\mid
k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}},\\{Z_{j|k}^{(0)}-Z_{k|j}^{(0)}\\}_{(j,k)\in\mathcal{E}_{h}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla
f_{j}(W_{j}^{(t)})+\operatorname*{\textstyle\sum}_{k\in\mathcal{N}_{j,h}}\bm{B}_{j|k}Z_{j|k}^{(0)}\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}\big{)}$

where (a) follows from (35) and (36), and (b) follows from Appendix A; (c)
follows from Appendix A and the fact that all terms in (b) are sufficient to
compute all terms in (c) and vice versa. Hence, the proof of Theorem 1 is now
complete. Clearly, when $\sigma_{Z}^{2}=0$, the above (c) reduces to (V-A),
thereby showing that the privacy loss in DFL is upper bounded by the loss of
CFL.

Before proving the lower bound, we first present the following lemma necessary
for the coming proof.

######  Lemma 1.

Let $X_{1},\ldots X_{n}$ and $R_{1},\ldots R_{n}$ be independent random
variables, and let $g(\cdot)$ be an arbitrary function. If they satisfy
$\forall i\colon I(X_{i};g(X_{i})+R_{i})=0$. Then

$\displaystyle\forall i:$ $\displaystyle
I(X_{i};g(X_{1})+R_{1},\ldots,g(X_{n})+R_{n},\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j})$
$\displaystyle=I(X_{i};\operatorname*{\textstyle\sum}_{j=1}^{n}g(X_{j})).$

###### Proof.

See Appendix C in Supplementary.

∎

When $\sigma^{2}_{Z}\rightarrow\infty$, Theorem 1 becomes

$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}I\big{(}X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}},\\{Z_{j|k}^{(0)}-Z_{k|j}^{(0)}\\}_{(j,k)\in\mathcal{E}_{h}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla
f_{j}(W_{j}^{(t)})+\operatorname*{\textstyle\sum}_{k\in\mathcal{N}_{j,h}}\bm{B}_{j|k}Z_{j|k}^{(0)}\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}\big{)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}I\big{(}X_{i};\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla f_{j}(W_{j}^{(t+1)})-\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,l}}\nabla
f_{j}(W_{j}^{(t)})\\}_{1\leq l\leq k_{h},t\in\mathcal{T}}\big{)}$

where (a) uses the fact that $\sigma^{2}_{Z}\rightarrow\infty$, i.e.,
$\\{Z_{j\mid k}^{(0)}\\}_{(j,k)\in\mathcal{E}_{c}}$ is asymptotically
independent of all other terms; (d) uses Lemma 1 and the fact that for all
honest components $\mathcal{G}_{h,1},\ldots,\mathcal{G}_{h,k_{h}}$ the last
term in Eq. 34 is known: the gradient of honest nodes can be seen as the term
$g(X_{i})$’s and $Z_{j|k}^{(0)}-Z_{k|j}^{(0)}$’s can be seen as noise
$R_{i}$’s in Lemma 1. Hence, proof of lower bound is complete.

Supplement

##  Appendix C Proof of Lemma 1

We first present the following equality:

$\displaystyle\begin{bmatrix}1&1&\cdots&1&1\\\ 0&1&\cdots&1&1\\\
\vdots&\ddots&\ddots&\vdots&\vdots\\\ 0&\cdots&0&1&1\\\
0&\cdots&\cdots&0&1\end{bmatrix}\begin{bmatrix}g(X_{1})+R_{1}\\\
g(X_{2})+R_{2}\\\ \vdots\\\ g(X_{n})+R_{n}\\\
-\operatorname*{\textstyle\sum}_{i=1}^{n}R_{i}\end{bmatrix}$ (37)
$\displaystyle=\begin{bmatrix}\operatorname*{\textstyle\sum}_{i=1}^{n}g(X_{i})\\\
\operatorname*{\textstyle\sum}_{i=2}^{n}g(X_{i})-R_{1}\\\ \vdots\\\
X_{n}-\operatorname*{\textstyle\sum}_{i=1}^{n-1}R_{i}\\\
-\operatorname*{\textstyle\sum}_{i=1}^{n}R_{i}\end{bmatrix}.$

Thus

$\displaystyle
I(X_{i};g(X_{1})+R_{1},\ldots,g(X_{n})+R_{n},\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}I(X_{i};\operatorname*{\textstyle\sum}_{j=1}^{n}g(X_{j}),\operatorname*{\textstyle\sum}_{j=2}^{n}g(X_{j})-R_{1},\ldots,g(X_{n})$
$\displaystyle\quad-\operatorname*{\textstyle\sum}_{j=1}^{n-1}R_{j},\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j})$
$\displaystyle=I(X_{i};\operatorname*{\textstyle\sum}_{j=1}^{n}g(X_{j})).$

where (a) follows from the fact that the linear map in Eq. 37 is bijective; by
observing the linear map we note that the difference of the $k$’th and
$(k+1)$’th rows in RHS of Eq. 37 is $g(X_{k})+R_{k}$. This difference is
independent of all $X_{i}$s and the $k$’th row of Eq. 37, thus
$X_{i}\rightarrow\operatorname*{\textstyle\sum}_{j=1}^{n}g(X_{j})\rightarrow\operatorname*{\textstyle\sum}_{j=2}^{n}g(X_{j})-R_{1}\rightarrow\ldots\rightarrow
g(X_{n})-\operatorname*{\textstyle\sum}_{j=1}^{n-1}R_{i}\rightarrow\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j}$
forms a Markov chain. Which establishes the second equality, thereby
completing the proof.

##  Appendix D Proof of Corollary 1

$\displaystyle
I(X_{i};\mathcal{O}_{\rm{CFL}})-I(X_{i};\mathcal{O}_{\rm{DFL}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}I(X_{i};\mathcal{O}_{\rm{CFL}},\mathcal{O}_{\rm{DFL}})-I(X_{i};\mathcal{O}_{\rm{DFL}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}I(X_{i};\mathcal{O}_{\rm{CFL}},\mathcal{O}_{\rm{DFL}}|\mathcal{O}_{\rm{DFL}})$
$\displaystyle=I(X_{i};\mathcal{O}_{\rm{CFL}}|\mathcal{O}_{\rm{DFL}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}I\big{(}X_{i};\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}|\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{c},t\in\mathcal{T}},\\{\nabla
f_{j}(W_{j}^{(t+1)})-\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,l}}\nabla
f_{j}(W_{j}^{(t)})\\}_{1\leq l\leq k_{h},t\in\mathcal{T}}\big{)}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}I\big{(}X_{i};\\{\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}}|\\{X_{j}\\}_{j\in\mathcal{V}_{c}},\\{W_{j}^{(t)}\\}_{j\in\mathcal{V},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\nabla f_{j}(W_{j}^{(t+1)})-\nabla
f_{j}(W_{j}^{(t)})\\}_{j\in\mathcal{V}_{h},t\in\mathcal{T}},\big{.}$
$\displaystyle\quad\big{.}\\{\operatorname*{\textstyle\sum}_{j\in\mathcal{V}_{h,l}}\nabla
f_{j}(W_{j}^{(t)})\\}_{1\leq l\leq k_{h},t\in\mathcal{T}}\big{)}$

where (a) holds as
$I(X_{i};\mathcal{O}_{\rm{CFL}})=I(X_{i};\mathcal{O}_{\rm{CFL}},\mathcal{O}_{\rm{DFL}})$
since all terms in Section V-A of CFL are sufficient to compute all terms in
Eq. 27 in DFL; (b) and (c) follow from the definition of conditional mutual
information; (d) holds as $X_{j}$ and $W_{j}^{(t)}$ can determine $\nabla
f_{j}(W_{j}^{(t)})$;

##  Appendix E Convergence behavior

###  E-A Setting of logistic regression

We assume each node $i$ holds $n_{i}=1$ data sample
$\bm{x}_{ik}\in\mathbb{R}^{2}$ and binary labels $\ell_{i}\in\\{0,1\\}$. For
two labels, the input training samples are randomly drawn from a unit variance
Gaussian distribution having mean ${\bm{\mu}}_{0}=(-1,-1)^{\intercal}$
($\ell_{ik}=0$) and mean ${\bm{\mu}}_{1}=(1,1)^{\intercal}$ ($\ell_{ik}=1$),
respectively. We utilize PDMM for the decentralized protocol, i.e., $\theta=1$
in Algorithm 1, and the convergence parameter $\rho$ is set as $0.4$. A
single-step gradient descent with learning rate $\mu=0.1$ is employed for
updating Eq. 12. With this, the bound Eq. 30 becomes

$\displaystyle\frac{\partial
f_{i}}{\partial\bm{w}_{i}}^{\\!\\!\\!(t+1)}-\frac{\partial
f_{i}}{\partial\bm{w}_{i}}^{\\!\\!\\!(t)}=\operatorname*{\textstyle\sum}_{k=1}^{n_{i}}\big{(}\frac{1}{1+e^{-y^{(t+1)}_{ik}}}-\frac{1}{1+e^{-y^{(t)}_{ik}}}\big{)}\bm{x}_{ik}$
$\displaystyle=-\operatorname*{\textstyle\sum}_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\Delta\bm{z}_{w,i|j}^{(t)}+\frac{1}{\mu}\big{(}\bm{w}_{i}^{(t)}-\bm{w}_{i}^{(t+1)}\big{)}$
$\displaystyle\quad+\big{(}\rho
d_{i}-\frac{1}{\mu}\big{)}\big{(}\bm{w}_{i}^{(t-1)}-\bm{w}_{i}^{(t)}\big{)},$
(38)

and similar modification follows for Eq. 31. As for the CFL protocol, the same
learning rate is applied for a fair comparison, i.e., $\mu$ in Eq. 1 is also
set to $0.4$.

###  E-B Setting and convergence behavior of DNNs

To test the performance of the introduced DFL protocol, we generated a random
geometric graph with $n=10$ nodes. LeNet architecture [59] is used for
training and two datasets, the MNIST [60] and CIFAR-10 [61] datasets, are used
for evaluation. MNIST and CIFAR-10 contain 60,000 images of size 28 $\times$
28 and 50,000 images of size 32 $\times$ 32 from 10 classes, respectively. We
randomly split each dataset into 10 folds, allocating each node one fold. For
the decentralized protocol, we also use PDMM with the convergence parameter
$\rho$ set to $0.4$. We use the quadratic approximation technique [62, 12] to
solve the sub-problems approximately with $\mu=\frac{1}{30}$. For the
centralized protocol, the constant $\mu$ in Eq. 1 is also set to
$\mu=\frac{1}{30}$. In Figure 8 we demonstrate the training loss (in blue) and
test accuracy (in red) for both protocols, applied on MNIST and CIFA-10
datasets, respectively.

Figure 8: Training loss and test accuracy in terms of iteration number of both
CFL and DFL for two datasets: (a) MNIST and (b) CIFAR-10.

##  Appendix F Supplementary attack results

Figure 9: Performance comparisons of CFL and DFL via a combination strategy
using MNIST dataset: SSIM of all reconstructed samples of CFL and DFL by
combining gradient differences with the gradient sum for three different sizes
of honest component $|\mathcal{V}_{h,1}|=2,4,8$ ((a)-(c), respectively).
Figure 10: Performance of reconstructed inputs via inverting gradients (CFL)
and the gradient sum of three different sizes $|\mathcal{V}_{h,1}|=2,4$ and
$8$ (DFL) in terms of iterations $t$ :(a) Averaged SSIM (solid lines) of all
reconstructed inputs along with the corresponding standard derivation
(shadows), (b) sample examples of reconstructed inputs at iteration number
$t=1,100,\ldots,900$. Figure 11: Performance comparisons of CFL and DFL in
terms of the portion of corrupted nodes via membership inference attacks.
Figure 12: Performance comparison of CFL and DFL using two MLPs: Averaged SSIM
of all reconstructed inputs using CFL and DFL with three settings: inverting
gradient difference, gradient sum, and their combination.  Figure 13:
Membership inference attack results comparisons of CFL and DFL with gradient
sum using the gradient-based approach [63]

Figure 14: Performance comparisons of CFL and DFL via inverting inputs from
gradient differences using cosine similarity based gradient inversion attack
[15]: (a) Samples images of ground truth and reconstructed inputs, (b) SSIM
comparisons of all reconstructed inputs for different batch size
$n_{i}=1,2,4,8$, respectively.

Figure 15: Performance comparisons of CFL and DFL via inverting inputs from
gradient sums using cosine similarity based gradient inversion attack [15]:
(a) Samples images of ground truth and reconstructed inputs, (b) SSIM of all
reconstructed samples for three different sizes of honest component
$|\mathcal{V}_{h,1}|=2,~{}4,~{}8$, respectively.

Experimental setting of membership inference attack results: We deployed the
gradient-based membership inference attacks proposed in [63] which are
specially designed for FL and are shown optimum compared to previously
proposed MIAs such as the so-called loss-based [64] and modified entropy-based
approaches [65]. The former uses cosine similarity of model updates and
instance gradients, expressed as

$\displaystyle M\left(\bm{x}^{\prime},i\right)$
$\displaystyle=\operatorname*{\textstyle\sum}_{l^{\prime}\in\mathbb{R}}\mathbbm{1}\left\\{\operatorname{cosim}\left(\nabla
f_{i}(\bm{w}_{i},(\bm{x}^{\prime},l^{\prime})),\nabla
f_{i}(\bm{w}_{i},(\bm{x}_{i},\bm{\ell}_{i}))\right)\geq\gamma\right\\}.$

The latter one uses the indicator shown as

$\displaystyle M\left(\bm{x}^{\prime},i\right)$
$\displaystyle=\mathbbm{1}\\{\left\|\nabla
f_{i}(\bm{w}_{i},(\bm{x}_{i},\bm{\ell}_{i}))\right\|_{2}^{2}$
$\displaystyle-\|\nabla
f_{i}(\bm{w}_{i},(\bm{x}_{i},\bm{\ell}_{i}))-\sum_{l^{\prime}\in\mathbb{R}}\nabla
f_{i}(\bm{w}_{i},(\bm{x}_{i},\bm{\ell}_{i}))\|_{2}^{2}>0\\}.$

Following similar settings in [63], we randomly select 4000 samples in
Purchase dataset [46] as the training sets and distribute them to $n=10$
nodes. For our experiments, we adopt the fully connected neural network
architecture proposed by [63], comprising four perceptron layers: the first
layer (FC1) contains 512 neurons, followed by the second layer (FC2) with 256
neurons, the third layer (FC3) with 128 neurons, and the final layer (FC4)
with 100 neurons.