# Differentially Private Decentralized Deep Learning with Consensus Algorithms

Jasmine Bayrooti, Zhan Gao, Amanda Prorok
Department of Computer Science
University of Cambridge
{jgb52, zg292<EMAIL_ADDRESS>
###### Abstract

Cooperative decentralized deep learning relies on direct information exchange
between communicating agents, each with access to a local dataset which should
be kept private. The goal is for all agents to achieve consensus on model
parameters after training. However, sharing parameters with untrustworthy
neighboring agents could leak exploitable information about local datasets. To
combat this, we introduce differentially private decentralized learning that
secures each agent’s local dataset during and after cooperative training. In
our approach, we generalize Differentially Private Stochastic Gradient Descent
(DP-SGD) – a popular differentially private training method for centralized
deep learning – to practical subgradient- and ADMM-based decentralized
learning methods. Our algorithms’ differential privacy guarantee holds for
arbitrary deep learning objective functions, and we analyze the convergence
properties for strongly convex objective functions. We compare our algorithms
against centrally trained models on standard classification tasks and evaluate
the relationships between performance, privacy budget, graph connectivity, and
degree of training data overlap among agents. We find that differentially
private gradient tracking is resistant to performance degradation under sparse
graphs and non-uniform data distributions. Furthermore, we show that it is
possible to learn a model achieving high accuracies, within 3% of DP-SGD on
MNIST under $(1,10^{-5})$-differential privacy and within 6% of DP-SGD on
CIFAR-100 under $(10,10^{-5})$-differential privacy, without ever sharing raw
data with other agents. Open source code can be found at:
https://github.com/jbayrooti/dp-dec-learning.

##  1 Introduction

Decentralized machine learning methods provide benefits over standard
centralized approaches in aspects such as scalability and data privacy [23,
28]. Most research in this direction has focused on traditional federated
learning, where a central server is used to orchestrate training among
participating agents [4, 31, 8, 23]. However, these learning schemes can be
limited by computational bottlenecks and communication overhead. Fully
decentralized methods do not rely on central components during training and,
hence, unlock potential for large-scale applications in privacy sensitive
domains, such as autonomous driving, analyzing healthcare and finance trends,
and email filtering.

Fully decentralized learning methods involve sharing information with local
neighbors in a communication graph, each with access to a private dataset and
a local model. Decentralized systems of agents can cooperate to exchange
information and eventually consense on system-wide optimal model parameters.
Such works primarily utilize subgradient-based methods [40, 28, 7, 21],
Alternating Direction Method of Multipliers (ADMM) based approaches [54], or a
combination of both, which all typically involve direct parameter passing
among agents. Even though raw data is not exchanged during training, a
determined attacker may be able to extract parts of a local training dataset
from parameter exchanges during model consensus. Centralized and federated
learning models have been shown to be vulnerable to such white-box attacks
[34, 6, 15, 52] and fully decentralized learning methods may be even more at
risk due to the impracticality of vetting many communicating peers. In
practice, agents can gather sensitive information in their local datasets
after interacting with humans, exploring locations, or snapshotting
surroundings. Therefore, it is crucial to protect local agents’ datasets from
outside observers or other agents in the system during fully decentralized
deep learning.

Contributions. To mitigate these privacy risks, we propose using differential
privacy, the established standard for protecting against attacks targeting
individual training samples, to each agent’s training routine. More
specifically, we introduce fully decentralized, first-order, deep learning
algorithms that guarantee differential privacy for each agent’s local dataset
on every step of cooperative training. Our algorithms offer robust protection
against a knowledgeable adversary with full access to the training process and
model parameters. This is attractive for applications of cooperative
decentralized deep learning involving sensitive information where
participating agents are not entirely trustworthy. Moreover, we show
convergence for strongly convex objectives and demonstrate our algorithms’
practicality on challenging image classification tasks, finding reasonable
performance-privacy tradeoffs that have, thus far, not been achieved. In more
detail, our main contributions are:

  * •

We present three new differentially private, decentralized learning algorithms
to protect agents’ local datasets from honest-but-curious agents participating
in a learning system. Our algorithms generalize the popular DP-SGD algorithm
[2] to the decentralized setting and build on both subgradient- and ADMM-based
distributed optimization methods. Our methods’ differential privacy guarantees
apply to any deep learning objective function.

  * •

For each differentially private decentralized learning algorithm, we analyze
the convergence properties and show convergence for strongly convex objective
functions.

  * •

We evaluate the performance disparity between differentially private
decentralized and centralized methods under multiple privacy budgets, using
graphs of various connectivity, and for agents with disparate levels of
training data overlap. We find that differentially private gradient tracking
algorithms are invariant to communication graph connectivity and all
algorithms also achieve consistent performance across graph connectivities
above a threshold value. This insight is valuable as it allows us to relax the
communication graph connectivity in bandwidth-limited situations without
compromising performance.

  * •

We evaluate our algorithms’ performance on two standard image classification
tasks: MNIST and CIFAR100. 111We choose these tasks because both datasets are
publically available and have been used by previous influential works as
benchmarks for differentially private deep learning. Our findings indicate
that achieving privacy protection in decentralized learning comes at a modest
trade-off with performance. Our best differentially private algorithms reach
near DP-SGD levels of accuracy, coming within 3% accuracy on MNIST
classification under $(1,10^{-5})$-differential privacy and 6% accuracy on
CIFAR-100 classification under $(10,10^{-5})$-differential privacy.

##  2 Related Work

In this paper, we introduce decentralized differentially private algorithms
that build on prior research in the fields of decentralized optimization and
differential privacy.

Decentralized Optimization. Decentralized optimization methods typically
involve agents performing iterative computations using subgradients of the
objective function, the ADMM framework, or a combination of both [42, 35, 9,
50, 54]. Subgradient-based distributed learning approaches are especially
suited for non-smooth and non-convex optimization problems [57, 22, 35, 40,
28] and have been successfully applied in [21, 28, 40]. To ultimately reach
consensus on model parameters, these algorithms interleave local gradient
descent steps with averaging over values from neighboring agents. Much effort
has been dedicated to analyzing the rate of convergence to consensus [41, 26,
21, 29, 43]. On the other hand, ADMM-based methods facilitate explicit
constrained optimization [46, 19, 10, 30], thus optimizing for both consensus
and performance. While ADMM was originally designed for convex optimization,
it can also be applied to non-convex settings [54, 39, 51]. DiNNO [54] is one
such algorithm that has recently achieved performance on par with centrally
trained methods (using all data). Similarly, DSGD [28] and DSGT [40] have
become widely adopted methods. In summary, these three algorithms are uniquely
complementary in nature and, hence, we use them as the foundations for our
differentially private approach.

Differential Privacy. Differential privacy applications involve perturbing
messages or objective functions to mask the impact of individual samples on
the output. Such techniques are commonly used in convex problem settings to
secure control systems [11, 37], distributed risk minimization [16, 18, 56,
55], and more [17, 48]. We are interested in neural network optimization to
solve complex tasks and these objectives are rarely convex. The popular DP-SGD
algorithm [2] provides privacy guarantees (quantified by the moments
accountant) while training deep learning models with a practical balance
between privacy and utility. While [38] is another approach for differential
privacy in deep learning, this paper primarily focuses on DP-SGD as it is more
common and has inspired many follow-up works, largely in centralized and
federated learning settings [12, 47, 3, 14]. While differentially private
federated learning focuses on privacy during aggregation at the central server
[3], fully decentralized differentially private learning ensures privacy at
the individual agent level. A few approaches consider differential privacy for
decentralized deep learning problems. For instance, [49, 45] present
differentially private gradient tracking and gossip algorithms, although their
methods protect agents’ objective functions rather than agents’ datasets.
Additionally, the recent work [44] only bounds the privacy loss of a single
training iteration, evaluates on non-standard tasks for differential privacy,
and uses an algorithm similar to DSGD, which we find has low performance
relative to other algorithms. Naive composition leads to an overestimation of
the privacy loss [55, 32], hence, it is crucial to analyze the privacy budget
over all training iterations. In contrast to [44], our work examines the
impact of cumulative privacy budgets, communication graph connectivity, and
data distribution on decentralized differentially private learning for
traditional tasks.

Our paper is the first to develop and study high-accuracy, cooperative,
differentially private learning that secures agents’ local datasets for fully
decentralized, general, deep learning tasks by adapting DP-SGD to a wider
scope.

##  3 Problem Statement

Consider a cooperative deep learning problem involving $N$ agents, each with
access to separate, private datasets and operating in an undirected, connected
communication graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Agents
$i,j\in\mathcal{V}$ can exchange information if they are one-hop neighbors in
the graph i.e. $(i,j)\in\mathcal{E}$. Let
$\mathcal{N}_{i}=\\{i\\}\cup\\{j\in\mathcal{V}\mid(i,j)\in\mathcal{E}\\}$
denote the local neighborhood of agent $i$ and note that agent $i$ is included
in the neighbor set to simplify notation in the following sections. We
parameterize communication links with a symmetric, doubly stochastic mixing
matrix $W\in\mathbb{R}^{N}\times\mathbb{R}^{N}$ with non-negative entries
where $w_{ij}=0$ if and only if nodes $i$ and $j$ are not communicating.

Let $\mathcal{D}_{i}$ be the subset of data that agent $i$ can access and
$l(\cdot)$ be the objective function to be minimized. We aim to optimize a
neural network parameterized by the weights $\theta\in\mathbb{R}^{d}$ over the
aggregate dataset $\mathcal{D}=\cup_{i\in\mathcal{V}}\mathcal{D}_{i}$ where
each agent $i$ stores its own local estimate of the network weights
$\theta_{i}$. We desire the agents to reach consensus on optimal network
parameters $\theta^{*}$ after training. This distributed optimization problem
can be formulated as:

$\theta^{*}=\min_{\theta\in\mathbb{R}^{d}}\sum_{i=1}^{N}l(\theta;\mathcal{D}_{i})=\min\sum_{i=1}^{N}l(\theta_{i};\mathcal{D}_{i})\text{\quad
s.t. \quad$\theta_{1}=\theta_{2}=\dots=\theta_{N}$}$ (1)

Our problem is cooperative in the sense that all agents share the same goal,
i.e., the same objective function. However, some agents may be untrustworthy
and seek to uncover sensitive information about other agents’ private datasets
during network optimization. We assume all agents are honest and communicate
their true parameters.

##  4 Background

We proceed by outlining differential privacy and key decentralized learning
algorithms.

###  4.1 Differential Privacy

Differential privacy ensures that, if two datasets differ by only one
individual’s data, the output of an algorithm does not reveal whether that
individual’s data was used. This property provides a strong privacy guarantee
while allowing useful insights to be extracted from the dataset. We consider
datasets $\mathcal{D}\in\mathcal{X}\times\mathcal{Y}$ where $\mathcal{X}$ is
the feature domain and $\mathcal{Y}$ the label domain. Changes in a dataset
are formalized by a symmetric, binary adjacency relation $Adj(\cdot,\cdot)$.

######  Definition 4.1 (Adjacent Datasets [11]).

Two datasets $\mathcal{D}=\\{(x,y)_{i}\\}_{i=1}^{n}$ and
$\mathcal{D}^{\prime}=\\{(x^{\prime},y^{\prime})_{i}\\}_{i=1}^{n}$ are
adjacent if there exists an index $j$ such that $1\leq j\leq n$ where
$(x,y)_{i}=(x^{\prime},y^{\prime})_{i}$ for all $i\neq j$.

This allows us to state the definition of differential privacy in a machine
learning context.

######  Definition 4.2 (Differential Privacy [20]).

A mechanism $\mathcal{M}:\mathcal{X}\times\mathcal{Y}\rightarrow\mathcal{R}$
is $(\epsilon,\delta)$-differentially private if, for any adjacent datasets
$\mathcal{D},\mathcal{D}^{\prime}$, and every set of outputs
$\mathcal{O}\subseteq\mathcal{R}$, the following holds:

$\mathbb{P}[\mathcal{M}(\mathcal{D})\in O]\leq
e^{\epsilon}\mathbb{P}[\mathcal{M}(\mathcal{D}^{\prime})\in O]+\delta.$ (2)

The privacy budget is quantified by $\epsilon$, which essentially bounds the
log-likelihood ratio of any particular output being obtained when running the
algorithm on two adjacent datasets. The $\delta$ term bounds the occurrence of
outputs that violate the privacy limit.

DP-SGD. Differentially Private Stochastic Gradient Descent (DP-SGD) [2] is a
popular differentially private deep learning algorithm. The authors propose
three modifications from the standard SGD procedure: independently picking
samples in a mini-batch with uniform sampling probability $q$, clipping the
$l_{2}$ norm of each per-sample gradient $\nabla
l(\theta_{i};\mathcal{D}_{i})$ to a maximal norm $C$, and adding Gaussian
noise $\xi$ with variance proportional to $C$ to gradients. Abadi et al. also
introduce the moments accountant to select the noise variance $\sigma$ so that
the algorithm provably satisfies a cumulative $(\epsilon,\delta)$-differential
privacy guarantee [2]. In our experiments, we use the sampled Gaussian
mechanism [33], which is closely related to the moments accountant, for the
same purpose. To formalize the clipping process, we refer to the definition
used in [12].

######  Definition 4.3 (Clipping function).

Define
$\texttt{clip}_{C}:v\in\mathbb{R}^{d}\rightarrow\min\\{1,\frac{C}{||v||_{2}}\\}\cdot
v\in\mathbb{R}^{d}$.

###  4.2 Decentralized Optimization

We develop differentially private decentralized algorithms on top of non-
private, complementary distributed learning algorithms: DSGD, DSGT, and DiNNO.
We select these base methods because DSGD is a popular baseline, DSGT has been
shown to achieve strong performance, and DiNNO is a recently developed and
effective ADMM-based decentralized deep learning method. Moreover, these
algorithms exhibit core similarities with other distributed algorithms.

Distributed Stochastic Gradient Descent (DSGD) [28] extends the SGD algorithm
to the distributed setting with the following update for agent $i$:

$\theta^{k+1}_{i}=\sum_{j\in\mathcal{N}_{i}}w_{ij}\theta^{k}_{j}-\eta^{k}\nabla
l(\theta^{k}_{i};\mathcal{D}_{i})$ (3)

where $\eta^{k}$ is the learning rate at the $k$th iteration. DSGD achieves
consensus across agents in the graph for most objectives and, for strongly
convex objectives, converges to a neighborhood of the global optimum [21, 25].
DSGD has also been shown to be affected by non-IID data among agents [25].

Gradient tracking methods are known for their ability to mitigate the impact
of non-IID data distributions [29, 49, 36] and a convergence rate that can
match that of mini-batch SGD for strongly convex objectives [26]. As in [11],
we select Distributed Stochastic Gradient Tracking (DSGT) [40] from the family
of gradient tracking methods. The DSGT updates include an additional variable
$y_{i}^{k}$ to track the per-agent estimate of the joint loss gradient.

$\theta^{k+1}_{i}=\sum_{j\in\mathcal{N}_{i}}w_{ij}(\theta^{k}_{j}-\eta^{k}y_{j}^{k})$
(4) $y^{k+1}_{i}=\nabla
l(\theta^{k+1}_{i};\mathcal{D}_{i})+\sum_{j\in\mathcal{N}_{i}}w_{ij}y_{j}^{k}-\nabla
l(\theta^{k}_{i};\mathcal{D}_{i})$ (5)

Note that in DSGT, agents share gradient estimates $y^{k}_{i}$ as well as
model parameters $\theta_{i}^{k}$ with neighbors.

Finally, we consider a consensus ADMM-based algorithm DiNNO [11] which
optimizes each agents’ primal variable $\theta_{i}^{k}$ and the dual variable
$y_{i}^{k}$ to enforce agreement between agents:

$y_{i}^{k+1}=y_{i}^{k}+\rho\sum_{j\in\mathcal{N}_{i}}(\theta_{i}^{k}-\theta_{j}^{k})$
(6)
$\theta_{i}^{k+1}=\text{argmin}_{\theta}l(\theta;\mathcal{D}_{i})+\theta^{T}y_{i}^{k+1}+\rho\sum_{j\in\mathcal{N}_{i}}\left\lVert\theta-\frac{\theta_{i}^{k}+\theta_{j}^{k}}{2}\right\rVert_{2}^{2}$
(7)

For strongly convex objectives, [11] shows that DiNNO converges to the unique
global solution.

##  5 Differentially Private Decentralized Learning

In these first-order distributed learning approaches, each agent $i$ updates
its parameters by incorporating information from its neighbors and taking a
step in a direction related to the gradient $\nabla
l(\theta_{i};\mathcal{D}_{i})$ (or a mini-batch gradient) using the local
dataset $\mathcal{D}_{i}$. Agent $i$ then broadcasts the updated values to its
neighbors. However, sharing parameters directly with neighboring agents
presents a privacy risk because local training samples can leave a discernible
trace on the gradients and, transitively, the parameters [34].

To mitigate this privacy risk, we propose differentially private distributed
algorithms: DP-DSGD, DP-DSGT, and DP-DiNNO, which incorporate key elements
from the DP-SGD algorithm into the decentralized setting. We utilize the
sampled Gaussian mechanism [33] to select the suitable standard deviation
$\sigma$ for adding Gaussian noise to gradients, ensuring cumulative
$(\epsilon,\delta)$-differential privacy for each agent. In this section, we
describe each algorithm and state their convergence for strongly convex
objective functions.

###  5.1 DP-DSGD

To design DP-DSGD to be differentially private under the adjacency relation
4.1, we utilize a variation of DP-SGD on each agent in the network that allows
for inter-agent communication via a modified update step. For a single agent
$i$, this entails independently picking a lot
$\mathcal{L}_{i}\subseteq\mathcal{D}_{i}$ of $L$ samples with probability
$q=L/|\mathcal{D}_{i}|$, clipping the $l_{2}$ norm of each per-sample
gradient, averaging the clipped gradients in the batch, adding Gaussian noise
to the aggregate gradient, and taking a step using the perturbed gradient. In
a departure from the original DP-SGD paper, which only considers single agent
learning, agent $i$ takes the final step using its aggregated local estimate
of the parameters $\sum_{j\in\mathcal{N}_{i}}w_{ij}\theta_{j}$ (note that this
includes $\theta_{i}$) and shares the noisy parameters with neighbors.
Algorithm 1 outlines the training procedure.

Algorithm 1 DP-DSGD

1:Require: $\mathcal{G}$, $\mathcal{D}$, $l(\cdot)$, $\mathcal{W}$,
$\theta_{\mathrm{initial}}$, $L$, $C$, $\eta$, $\sigma$, $K$

2:Each agent $i$ does: $\triangleright$ In parallel

3: $\theta_{i}^{0}=\theta_{\mathrm{initial}}$ $\triangleright$ Initialize
parameters

4:For $k=1,2,\dots,K$

5: Communicate: send $\theta^{k}_{i}$ to neighbors $\mathcal{N}_{i}$

6: Each agent $i$ does: $\triangleright$ In parallel

7: Take a random lot of samples $\mathcal{L}_{i}^{k}$ with sampling
probability $L/|\mathcal{D}_{i}|$

8: $\xi\sim N(0,I_{d})$ $\triangleright$ Draw a Gaussian sample

9:
$\tilde{G}(\theta_{i}^{k};\mathcal{D}_{i})=\frac{1}{L}\sum_{d\in\mathcal{L}^{k}_{i}}\texttt{clip}_{C}\left(\nabla
l(\theta^{k}_{i};d)\right)+\frac{\sigma C}{L}\xi$ $\triangleright$ Clip and
add noise

10:
$\theta_{i}^{k+1}=\sum_{j\in\mathcal{N}_{i}}w_{ij}\theta^{k}_{j}-\eta^{k}\tilde{G}(\theta_{i}^{k};\mathcal{D}_{i})$
$\triangleright$ DP version of Equation 3

###  5.2 DP-DSGT

We introduce DP-DSGT, a differentially private gradient tracking approach
based on DSGT. Similar to DP-DSGD, we integrate the key components of DP-SGD
(uniform sampling, gradient clipping, and injecting calibrated Gaussian noise)
during training on each iteration so that the algorithm is differentially
private for all agents. Algorithm 2 describes the training procedure in
detail.

Algorithm 2 DP-DSGT

1:Require: $\mathcal{G}$, $\mathcal{D}$, $l(\cdot)$, $\mathcal{W}$,
$\theta_{\mathrm{initial}}$, $L$, $C$, $\eta$, $\sigma$, $K$

2:Each agent $i$ does: $\triangleright$ In parallel

3: $\theta_{i}^{0}=\theta_{\mathrm{initial}}$ $\triangleright$ Initialize
parameters

4: $\tilde{G}^{0}(\theta_{i}^{0};\mathcal{D}_{i})=0$

5:For $k=1,2,\dots,K$

6: Communicate: send $\theta^{k}_{i}$, $y^{k}_{i}$ to neighbors
$\mathcal{N}_{i}$

7: Each agent $i$ does: $\triangleright$ In parallel

8:
$\theta^{k+1}_{i}=\sum_{j\in\mathcal{N}_{i}}w_{ij}(\theta^{k}_{j}-\eta^{k}y_{j}^{k})$
$\triangleright$ Update model parameters (4)

9: Take a random lot of samples $\mathcal{L}_{i}^{k}$ with sampling
probability $L/|\mathcal{D}_{i}|$

10: $\xi\sim N(0,I_{d})$ $\triangleright$ Draw a Gaussian sample

11:
$\tilde{G}^{k+1}(\theta_{i}^{k+1};\mathcal{D}_{i})=\frac{1}{L}\sum_{d\in\mathcal{L}^{k}_{i}}\texttt{clip}_{C}\left(\nabla
l(\theta^{k+1}_{i};d)\right)+\frac{\sigma C}{L}\xi$ $\triangleright$ Clip and
add noise

12:
$y^{k+1}_{i}=\tilde{G}^{k+1}(\theta_{i}^{k+1};\mathcal{D}_{i})+\left(\sum_{j\in\mathcal{N}_{i}}w_{ij}y_{j}^{k}-\tilde{G}^{k}(\theta_{i}^{k};\mathcal{D}_{i})\right)$
$\triangleright$ DP version of 5

Algorithm 3 DP-DiNNO

1:Require: $\mathcal{G}$, $\mathcal{D}$, $l(\cdot)$,
$\theta_{\mathrm{initial}}$, $L$, $C$, $\rho$, $\eta$, $\sigma$, $K$, $T$

2:Each agent $i$ does: $\triangleright$ In parallel

3: $y_{i}^{0}=0$ $\triangleright$ Dual variable

4: $\theta_{i}^{0}=\theta_{\mathrm{initial}}$ $\triangleright$ Primal variable

5:For $k=1,2,\ldots,K$

6: Communicate: send $\theta^{k}_{i}$ to neighbors $\mathcal{N}_{i}$

7: Each agent $i$ does: $\triangleright$ In parallel

8:
$y_{i}^{k+1}=y_{i}^{k}+\rho\sum_{j\in\mathcal{N}_{i}}(\theta_{i}^{k}-\theta_{j}^{k})$
$\triangleright$ Update the dual

9: $\psi^{0}=\theta_{i}^{k}$ $\triangleright$ Warm start primal optimization

10: For $t=1,2,\ldots,T$

11: Take a random lot of samples $\mathcal{L}_{i}^{k}$ with sampling
probability $L/|\mathcal{D}_{i}|$

12: $\xi\sim N(0,I_{d})$ $\triangleright$ Draw a Gaussian sample

13:
$\tilde{g}(\psi^{t};\mathcal{D}_{i})=\frac{1}{L}\sum_{d\in\mathcal{L}_{i}^{k}}\texttt{clip}_{C}\left(\nabla
l(\psi^{t};d)\right)+\frac{\sigma C}{L}\xi$ $\triangleright$ Clip and add
noise

14:
$\tilde{G}(\psi^{t})=\tilde{g}(\psi^{t};\mathcal{D}_{i})+\nabla\left((\psi^{t})^{T}y_{i}^{k+1}+\rho\sum_{j\in\mathcal{N}_{i}}\left\lVert\psi^{t}-\frac{\theta_{i}^{k}+\theta_{j}^{k}}{2}\right\rVert_{2}^{2}\right)$
$\triangleright$ Aggregate

15: $\psi^{t+1}=\psi^{t}+\tilde{G}(\psi^{t})$ $\triangleright$ Update with an
optimizer step

16: $\theta_{i}^{k+1}=\psi^{T}$ $\triangleright$ Update primal

###  5.3 DP-DiNNO

Finally, we present DP-DiNNO, a differentially private version of the DiNNO
algorithm [54]. Unlike the subgradient algorithms which iteratively calculate
$\nabla l(\theta_{i};\mathcal{D}_{i})$ and take a step in the opposite
direction, consensus-ADMM based algorithms iteratively update primal variables
after solving an optimization problem (7). This solution is difficult to
characterize when $l$ is non-convex. Existing differentially private ADMM-
based methods typically assume the objective function $l$ is convex and bound
the update function’s sensitivity to adjacent datasets using the closed form
solution to the primal optimization problem [18, 55]. We make no assumptions
about the convexity of $l$ and instead solve the primal optimization problem
iteratively, as proposed in [54], while injecting noise for each gradient to
achieve differential privacy.

Once again, we incorporate the core elements of DP-SGD to privatize the DiNNO
algorithm. Note that we do not need to clip the entire gradient of
$l(\theta_{i};\mathcal{D}_{i})+\theta_{i}^{T}y_{i}^{k+1}+\rho\sum_{j\in\mathcal{N}_{i}}\left\lVert\theta_{i}-\frac{\theta_{i}^{k}+\theta_{j}^{k}}{2}\right\rVert_{2}^{2}$
since only $\nabla l(\theta_{i};\mathcal{D}_{i})$ relies on agent $i$’s
private dataset $\mathcal{D}_{i}$. The method is described in detail in
Algorithm 3. The learning rate $\eta^{k}$ decays during training and is used
by a first-order optimizer in line 14. We use the Adam optimizer in this
paper.

###  5.4 Convergence Analysis

We show the convergence of differentially private consensus algorithms for
strongly convex objectives.

######  Theorem 5.1 (Convergence Theorem).

Let the objective function $l$ be strongly convex and $L$-smooth,
$\theta\in\mathbb{R}^{Nd}$ be a vector concatenating local variables
$\\{\theta_{i}\\}_{i=1}^{N}$, $M(\theta)$ be a function of $\theta$ that is of
interest for convergence, and $\sigma$ be the standard deviation of Gaussian
noise for differentially private gradient perturbations. If $M(\theta)$ of the
base decentralized algorithm is Lipschitz w.r.t. a constant $K$, i.e.,
$\|M(\theta)-M(\hat{\theta})\|_{2}\leq K\|\theta-\hat{\theta}\|_{2}$ for any
$\theta$ and $\hat{\theta}$, and converges to the optimal solution
$M(\theta^{*})$ at a linear rate, $M(\theta)$ of the differentially private
decentralized algorithm also converges to the optimal solution $M(\theta^{*})$
at a linear rate within an error neighborhood on the order of
$\mathcal{O}(\sigma)$.

The convergence proof is provided in Appendix A. Theorem 5.1 states that the
proposed differentially private algorithm does not affect the convergence of
the base decentralized algorithm and $M(\cdot)$ can be any function of
interest, i.e., $M(\theta)=\sum_{i=1}^{N}l(\theta_{i},\mathcal{D}_{i})$ is the
overall objective function or $M(\theta)=\theta$ is the variable itself. Note
that the base algorithms we consider, namely DSGD, DSGT, and DiNNO, converge
linearly when the objective function is strongly convex [21, 26, 40, 54]. The
key insight to our proof is that the noise terms are scaled by a diminishing
learning rate $\eta^{k}$ and a linear convergence rate, such that the
cumulative noise is bounded on the order of the standard deviation
$\mathcal{O}(\sigma)$.

##  6 Experiments and Discussion

Figure 1: All algorithms appear relatively invariant to connectivity up to a
normalized Fiedler value of around 0.4. DP-DSGD performance (left) is variable
and decreases for sparse graphs. DP-DSGT (middle) performance is invariant to
connectivity for all privacy budgets. DP-DiNNO (right) performance is only
affected by graph connectivity for sparse graphs and low $\epsilon$ values.
Table 1: Accuracy comparison over algorithms, privacy budgets, and graph
connectivities on MNIST.

Normalized Fiedler Value: $\bm{1}$ (Complete Graph) |  |
---|---|---
Method | Non-Private | $\varepsilon=100$ | $\varepsilon=10$ | $\varepsilon=1$ | $\varepsilon=0.5$
Central | 98.22 $\pm$ 0.19 | 96.16 $\pm$ 0.62 | 94.73 $\pm$ 0.74 | 92.04 $\pm$ 0.84 | 90.82 $\pm$ 1.14
DP-DSGD | 95.38 $\pm$ 0.37 | 92.34 $\pm$ 0.9 | 91.27 $\pm$ 0.92 | 87.26 $\pm$ 1.16 | 84.07 $\pm$ 1.89
DP-DSGT |  98.13 $\pm$ 0.11 |  96.13 $\pm$ 0.84 |  96.54 $\pm$ 0.17 | 89.24 $\pm$ 0.27 | 85.41 $\pm$ 0.54
DP-DiNNO | 97.81 $\pm$ 0.2 | 95.41 $\pm$ 0.36 | 93.21 $\pm$ 0.24 |  89.66 $\pm$ 0.51 |  86.22 $\pm$ 0.58

Normalized Fiedler Value: $\bm{0.7\pm 0.05}$ |  |  |
---|---|---|---
Method | Non-Private | $\varepsilon=100$ | $\varepsilon=10$ | $\varepsilon=1$ | $\varepsilon=0.5$
Central | 98.22 $\pm$ 0.19 | 96.16 $\pm$ 0.62 | 94.73 $\pm$ 0.74 | 92.04 $\pm$ 0.84 | 90.82 $\pm$ 1.14
DP-DSGD | 95.19 $\pm$ 0.37 | 92.03 $\pm$ 0.64 | 91.27 $\pm$ 1.1 | 87.16 $\pm$ 1.58 | 84.09 $\pm$ 2.23
DP-DSGT | 97.76 $\pm$ 0.83 |  96.16 $\pm$ 0.77 |  96.62 $\pm$ 0.11 |  89.75 $\pm$ 0.77 | 84.98 $\pm$ 1.13
DP-DiNNO |  97.94 $\pm$ 0.21 | 95.51 $\pm$ 0.43 | 93.41 $\pm$ 0.37 | 89.13 $\pm$ 0.34 |  85.7 $\pm$ 0.25

Normalized Fiedler Value: $\bm{0.39\pm 0.05}$ |  |  |
---|---|---|---
Method | Non-Private | $\varepsilon=100$ | $\varepsilon=10$ | $\varepsilon=1$ | $\varepsilon=0.5$
Central | 98.22 $\pm$ 0.19 | 96.16 $\pm$ 0.62 | 94.73 $\pm$ 0.74 | 92.04 $\pm$ 0.84 | 90.82 $\pm$ 1.14
DP-DSGD | 94.77 $\pm$ 0.87 | 91.56 $\pm$ 0.68 | 90.61 $\pm$ 0.93 | 87.68 $\pm$ 0.74 | 85.22 $\pm$ 1.21
DP-DSGT | 97.36 $\pm$ 1.43 |  96.28 $\pm$ 0.7 |  96.42 $\pm$ 0.21 |  89.84 $\pm$ 0.39 | 84.79 $\pm$ 1.07
DP-DiNNO |  97.91 $\pm$ 0.25 | 95.6 $\pm$ 0.35 | 93.25 $\pm$ 0.34 | 89.02 $\pm$ 0.35 |  85.91 $\pm$ 0.46

Normalized Fiedler Value: $\bm{0.06\pm 0.05}$ |  |  |
---|---|---|---
Method | Non-Private | $\varepsilon=100$ | $\varepsilon=10$ | $\varepsilon=1$ | $\varepsilon=0.5$
Central | 98.22 $\pm$ 0.19 | 96.16 $\pm$ 0.62 | 94.73 $\pm$ 0.74 | 92.04 $\pm$ 0.84 | 90.82 $\pm$ 1.14
DP-DSGD | 90.55 $\pm$ 2.06 | 88.36 $\pm$ 3.75 | 84.12 $\pm$ 2.49 | 82.49 $\pm$ 1.23 | 80.57 $\pm$ 1.47
DP-DSGT |  97.73 $\pm$ 0.48 |  95.97 $\pm$ 1.67 |  96.26 $\pm$ 0.17 |  89.16 $\pm$ 0.82 |  84.53 $\pm$ 1.29
DP-DiNNO |  97.73 $\pm$ 0.28 | 95.03 $\pm$ 0.79 | 91.99 $\pm$ 0.67 | 85.68 $\pm$ 1.13 | 78.44 $\pm$ 2

In this section, we explore the relationships between accuracy, privacy
budget, communication graph connectivity, and data distribution among agents
based on class labels.

Setup. We consider a system with $N=10$ agents communicating over randomly
selected connected graphs with connectivity measured by the normalized Fiedler
value: the classical Fiedler value divided by the number of agents. Our
baseline for comparison against centrally-trained differentially private
algorithms is the widely-used DP-SGD algorithm. To ensure a fair comparison
between decentralized algorithms, we utilize Ray’s population-based tuning
algorithm [1] and additional manual tuning to select appropriate learning
rates for each method and privacy budget. Throughout all experiments, we use
fixed $\delta=10^{-5}$, gradient clipping threshold of $C=1$ for DP-SGD
training (as in [12]), and $C=10$ for DP-DSGD, DP-DSGT, and DP-DiNNO (since
these algorithms converge slower). See Appendix B and our code for more
information about our experimental setup.

Graph Connectivity. To assess the performance of our algorithms compared to
DP-SGD, we experimentally investigate the critical choice of the underlying
communication graph. Our experiments entail training DP-DSGD, DP-DSGT, and DP-
DiNNO on cooperative MNIST digit classification [13] over multiple graphs of
varying connectivity for numerous privacy budgets. MNIST is a natural choice
of dataset because it is publically available and has been used as a benchmark
for differential privacy with deep learning [2]. Each agent maintains its own
local model, a CNN with two fully connected layers, and is allocated all the
training data corresponding to one random digit. The agents seek to consense
on model parameters that are optimal over the aggregated dataset, with
evaluations on the held out validation set (which includes all digits). We
report the means and standard deviations from five training trials for each
algorithm and multiple privacy budgets on randomly sampled graphs with
connectivity across a range of normalized Fiedler values in Table 1. We
observe that centrally-trained DP-SGD always upper bounds the decentralized
algorithms’ accuracy by a few percentage points. Nevertheless, the results
demonstrate that differentially private decentralized learning can achieve
strong performance on MNIST classification even for low privacy budgets (i.e.,
strong privacy guarantees), with the DP-DSGT accuracy around 3% of the DP-SGD
accuracy under cumulative $(1,10^{-5})$-differential privacy.

Furthermore, we isolate the effects of changing graph connectivity and privacy
budgets on decentralized differentially private classification in Figure 1.
These findings indicate that DP-DSGT is invariant to graph connectivity. This
likely stems from DP-DSGT’s exchange of per-agent global gradient estimates
(in addition to model parameters), which can facilitate more effective
tracking of the global gradient. However, this procedure requires exchanging
twice the message size as in DP-DSGD and DP-DiNNO, which may be infeasible
depending on the application. Figure 1 also demonstrates that DP-DSGD and DP-
DiNNO exhibit graph invariance for normalized Fiedler values above 0.4 and
declining performance below 0.4. The consistent performance of all algorithms
across graph connectivities above a normalized Fiedler value of 0.4 is
significant because it implies that we can relax the connectivity of the
communication graph up to a specific threshold in bandwidth-limited scenarios
without compromising performance.

Data Distribution. Data heterogeneity between agents poses another challenge
in decentralized learning [26]. In this set of experiments, we study how the
data distribution among agents impacts differentially private learning. To
quantify the notion of data distribution, we define the matrix $A(t)$ where
rows correspond to agents and columns correspond to classes in the dataset:

$a_{ij}(t)=\begin{cases}\frac{1-t}{N}\text{\quad$i\neq j$ mod $N$}\\\
1-\sum_{k\neq i}a_{kj}\text{\quad if $i=j$ mod $N$}\end{cases}$ (8)

Data is distributed according to $A(t)$ so that agent $i$ has the fractional
amount $a_{ij}$ of data labeled with class $j$ in its local dataset. Therefore
$t=0$ represents an equal distribution of each data class among all agents,
while $t=1$ signifies that each agent has complete and exclusive access to
specific classes (and no direct information on other classes). We specifically
investigate the impact of varying $t$ on MNIST classification using privacy
budgets $\epsilon=0.5$ and $\epsilon=10$ and a communication graph of
normalized Fiedler value $0.06$ (with means and standard deviations reported
over five trials).

As shown in Table 2, we find that DP-DSGT maintains consistent performance
regardless of the data distribution scheme, which agrees with results for non-
private DSGT [29, 49, 36], making this algorithm a good choice for
applications where agents own non-overlapping data classes. On the other hand,
DP-DSGD and DP-DiNNO benefit more from firsthand experience with each class as
they drop off in performance by 8% and 10% respectively as $t$ goes from $0$
to $1$ when $\epsilon=0.5$. Still, DP-DiNNO is more resilient than DP-DSGD to
changes in data allocation for higher privacy budgets as shown for
$\epsilon=10$.

Further Experiments. We show that our differentially private algorithms scale
to a more complex problem (i.e., CIFAR-100 classification [27] with a deeper
model), while maintaining strong performance, see Appendix C. Notably, DP-DSGT
achieves accuracy within 6% of DP-SGD under $(10,10^{-5})$-differential
privacy after 80 training epochs. Finally, we sanity check our approaches with
membership inference attacks as described in Appendix D.

Table 2: Performance comparison over algorithms and data splits on MNIST.

$\bm{\epsilon=0.5}$ |  |  |  |
---|---|---|---|---
Method | $t=0$ | $t=0.25$ | $t=0.5$ | $t=0.75$ | $t=1$
DP-DSGD | 88.9 $\pm$ 0.99 |  88.3 $\pm$ 0.31 |  87.65 $\pm$ 0.28 |  86.06 $\pm$ 0.24 | 80.57 $\pm$ 1.47
DP-DSGT | 85.78 $\pm$ 0.63 | 86 $\pm$ 0.96 | 85.79 $\pm$ 0.96 | 85.3 $\pm$ 0.9 |  84.53 $\pm$ 1.29
DP-DiNNO |  86.76 $\pm$ 0.96 | 86.19 $\pm$ 0.79 | 85.28 $\pm$ 0.39 | 83.55 $\pm$ 0.71 | 78.44 $\pm$ 2

$\bm{\epsilon=10}$ |  |  |  |
---|---|---|---|---
Method | $t=0$ | $t=0.25$ | $t=0.5$ | $t=0.75$ | $t=1$
DP-DSGD | 94.08 $\pm$ 0.41 | 93.89 $\pm$ 0.35 | 93.63 $\pm$ 0.31 | 92.56 $\pm$ 0.24 | 84.92 $\pm$ 2.26
DP-DSGT |  95.97 $\pm$ 0.35 |  96.04 $\pm$ 0.33 |  95.72 $\pm$ 0.34 |  96.10 $\pm$ 0.41 |  96.06 $\pm$ 0.24
DP-DiNNO | 93.42 $\pm$ 0.53 | 93.34 $\pm$ 0.49 | 93.28 $\pm$ 0.48 | 93.03 $\pm$ 0.33 | 92 $\pm$ 0.54

##  7 Final Remarks

Limitations and Future Work. Throughout experimentation, we found that our
algorithms required tuned learning rates for different tasks and privacy
budgets. We made a best-effort attempt to achieve comparable algorithm
evaluations using Ray’s population-based tuning and additional hand-tuning; we
acknowledge that further extensive tuning (given adequate computing resources)
might lead to different hyperparameter choices. Throughout this work, we
assumed agents could be honest-but-curious, though not deceptive, as this
would invalidate the consensus. Future work could consider non-cooperative and
adversarial threat models. We also focused on classification tasks since these
are the most standard differential privacy benchmarks. It would be interesting
to apply our algorithms to other problems beyond classification, such as
cooperative representation learning (as done in [54] within a non-private
setting). Finally, for all use cases, it would be important to understand and
mitigate our algorithms’ fairness loss when applied to sensitive use cases,
particularly considering that differential privacy has been shown to have a
disparate impact on model accuracy [5].

Conclusion. We introduced differentially private consensus-based learning
algorithms that achieve strong performance on deep learning tasks, regardless
of convexity, while protecting agents’ local datasets from untrustworthy
agents. Our work showcases the feasibility of achieving differential privacy
in fully decentralized settings, even with relaxed communication topologies,
low privacy budgets (i.e., strong privacy guarantees), and non-uniformly
distributed data.

Differential privacy enables the responsible and ethical use of sensitive
data, balancing the societal benefits of data analysis with the protection of
individual privacy. Expanding the scope of differential privacy in deep
learning to encompass decentralized learning algorithms holds significant
importance, and we anticipate that our work will lay the foundation for future
advancements in this area.

##  8 Acknowledgements

J. Bayrooti is supported by a DeepMind scholarship. Z. Gao and A. Prorok are
supported in part by European Research Council (ERC) Project 949940 (gAIa). We
also thank Carl Henrik Ek for insightful conversations and useful feedback on
early drafts of this work. Additionally, we thank George Pappas for discussing
differentially private machine learning with us and Alex Sablayrolles for
helpful information on using the Opacus library.

## References

  * [1] A guide to population based training with tune.  https://docs.ray.io/en/latest/tune/examples/pbt_guide.html.
  * [2] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, oct 2016.
  * [3] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan.  cpsgd: Communication-efficient and differentially-private distributed sgd.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [4] Mohammed Aledhari, Rehma Razzak, Reza M. Parizi, and Fahad Saeed.  Federated learning: A survey on enabling technologies, protocols, and applications.  IEEE Access, 8:140699–140725, 2020.
  * [5] Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov.  Differential privacy has disparate impact on model accuracy.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [6] Borja Balle, Giovanni Cherubin, and Jamie Hayes.  Reconstructing training data with informed adversaries.  In 2022 IEEE Symposium on Security and Privacy (SP), pages 1138–1156, 2022.
  * [7] Aditya Balu, Zhanhong Jiang, Sin Yong Tan, Chinmay Hegde, Young M. Lee, and Soumik Sarkar.  Decentralized deep learning using momentum-accelerated consensus.  arXiv preprint arXiv: 2010.11166, abs/2010.11166, 2020.
  * [8] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander.  Towards federated learning at scale: System design.  In A. Talwalkar, V. Smith, and M. Zaharia, editors, Proceedings of Machine Learning and Systems, volume 1, pages 374–388, 2019.
  * [9] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  IEEE Transactions on Information Theory, 52(6):2508–2530, 2006\.
  * [10] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein.  Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers.  Stanford University, 2011.
  * [11] Jorge Cortés, Geir E. Dullerud, Shuo Han, Jerome Le Ny, Sayan Mitra, and George J. Pappas.  Differential privacy in control and network systems.  In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 4252–4272, 2016.
  * [12] Soham De, Leonard Berrada, Jamie Hayes, Samuel L. Smith, and Borja Balle.  Unlocking high-accuracy differentially private image classification through scale.  arXiv preprint arXiv:2204.13650, 2022.
  * [13] Li Deng.  The mnist database of handwritten digit images for machine learning research [best of the web].  IEEE Signal Processing Magazine, 29(6):141–142, 2012.
  * [14] Xiaofeng Ding, Lin Chen, Pan Zhou, Wenbin Jiang, and Hai Jin.  Differentially private deep learning with iterative gradient descent optimization.  ACM/IMS Trans. Data Sci., 2(4), feb 2022.
  * [15] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1322–1333, 2015.
  * [16] Cristiano Gratton, Naveen K. D. Venkategowda, Reza Arablouei, and Stefan Werner.  Privacy-preserved distributed learning with zeroth-order optimization.  IEEE Transactions on Information Forensics and Security, 17:265–279, 2022.
  * [17] Shuo Han, Ufuk Topcu, and George J. Pappas.  Differentially private distributed constrained optimization.  IEEE Transactions on Automatic Control, 62(1):50–64, jan 2017\.
  * [18] Zonghao Huang and Yanmin Gong.  Differentially private ADMM for convex distributed learning: Improved accuracy via multi-step approximation.  CoRR, abs/2005.07890, 2020.
  * [19] Franck Iutzeler, Pascal Bianchi, Philippe Ciblat, and Walid Hachem.  Asynchronous distributed optimization using a randomized alternating direction method of multipliers.  In 52nd IEEE Conference on Decision and Control, pages 3671–3676, 2013.
  * [20] Matthew Jagielski, Jonathan Ullman, and Alina Oprea.  Auditing differentially private machine learning: How private is private sgd?  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22205–22216. Curran Associates, Inc., 2020.
  * [21] Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar.  Collaborative deep learning in fixed topology networks.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [22] Björn Johansson, Maben Rabi, and Mikael Johansson.  A randomized incremental subgradient method for distributed optimization in networked systems.  SIAM Journal on Optimization, 20(3):1157–1170, 2010.
  * [23] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  Foundations and Trends® in Machine Learning, 14(1–2):1–210, 2021.
  * [24] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  In Proceedings of the 32nd International Conference on Machine Learning, pages 1376–1385. PMLR, 2015.
  * [25] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich.  A unified theory of decentralized SGD with changing topology and local updates.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5381–5393. PMLR, 13–18 Jul 2020\.
  * [26] Anastasiia Koloskova, Tao Lin, and Sebastian U Stich.  An improved analysis of gradient tracking for decentralized machine learning.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 11422–11435. Curran Associates, Inc., 2021.
  * [27] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  University of Toronto, 2009.
  * [28] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu.  Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [29] Paolo Di Lorenzo and Gesualdo Scutari.  Next: In-network nonconvex optimization.  IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016.
  * [30] Gonzalo Mateos, Juan Andrés Bazerque, and Georgios B. Giannakis.  Distributed sparse linear regression.  IEEE Transactions on Signal Processing, 58(10):5262–5276, 2010\.
  * [31] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1273–1282. PMLR, 20–22 Apr 2017.
  * [32] Ilya Mironov.  Rényi differential privacy.  In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263–275, 2017.
  * [33] Ilya Mironov, Kunal Talwar, and Li Zhang.  Rényi differential privacy of the sampled gaussian mechanism.  arXiv preprint arXiv: 1908.10530, 2019.
  * [34] Milad Nasr, Reza Shokri, and Amir Houmansadr.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 739–753, 2019.
  * [35] Angelia Nedic and Asuman Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  IEEE Transactions on Automatic Control, 54(1):48–61, 2009.
  * [36] Angelia Nedić and Alex Olshevsky.  Distributed optimization over time-varying directed graphs.  IEEE Transactions on Automatic Control, 60(3):601–615, 2015.
  * [37] Erfan Nozari, Pavankumar Tallapragada, and Jorge Cortés.  Differentially private distributed convex optimization via functional perturbation.  IEEE Transactions on Control of Network Systems, 5(1):395–408, 2018\.
  * [38] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson.  Scalable private learning with pate.  International Conference on Learning Representations, 2018.
  * [39] Neal Parikh and Stephen Boyd.  Proximal algorithms.  Found. Trends Optim., 1(3):127–239, jan 2014.
  * [40] Shi Pu and Angelia Nedić.  Distributed stochastic gradient tracking methods.  Math. Program., 187:409-457, 2020.
  * [41] Konstantinos I. Tsianos, Sean Lawlor, and Michael G. Rabbat.  Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning.  In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1543–1550, 2012.
  * [42] John Tsitsiklis.  Problems in decentralized decision making and computation.  PhD Thesis, MIT Cambridge Lab for Information and Decision Systems, 1984.
  * [43] Isidoros Tziotis, Constantine Caramanis, and Aryan Mokhtari.  Second order optimality in decentralized non-convex optimization via perturbed gradient tracking.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21162–21173. Curran Associates, Inc., 2020.
  * [44] Yongqiang Wang and Tamer Başar.  Decentralized nonconvex optimization with guaranteed privacy and accuracy.  Automatica, 150:110858, 2023.
  * [45] Yongqiang Wang and Angelia Nedić.  Tailoring gradient methods for differentially-private distributed optimization.  IEEE Transactions on Automatic Control, pages 1–16, 2023.
  * [46] Ermin Wei and Asuman Ozdaglar.  Distributed alternating direction method of multipliers.  In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pages 5445–5450, 2012.
  * [47] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q. S. Quek, and H. Vincent Poor.  Federated learning with differential privacy: Algorithms and performance analysis.  IEEE Transactions on Information Forensics and Security, 15:3454–3469, 2020.
  * [48] Yongyang Xiong, Jinming Xu, Keyou You, Jianxing Liu, and Ligang Wu.  Privacy-preserving distributed online optimization over unbalanced digraphs via subgradient rescaling.  IEEE Transactions on Control of Network Systems, 7(3):1366–1378, 2020.
  * [49] Yu Xuan and Yongqiang Wang.  Gradient-tracking based differentially private distributed optimization with enhanced optimization accuracy.  arXiv preprint arXiv:2212.05364, 2023.
  * [50] Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng, Yiguang Hong, Hong Wang, Zongli Lin, and Karl H. Johansson.  A survey of distributed optimization.  Annual Reviews in Control, 47:278–305, 2019.
  * [51] Yu Yang, Qing-Shan Jia, Zhanbo Xu, Xiaohong Guan, and Costas J. Spanos.  Proximal admm for nonconvex and nonsmooth optimization.  Automatica, 146:110551, 2022.
  * [52] Samuel Yeom, Matt Fredrikson, and Somesh Jha.  The unintended consequences of overfitting: Training data inference attacks.  arXiv preprint arXiv:1709.01604, abs/1709.01604, 2017.
  * [53] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov.  Opacus: User-friendly differential privacy library in pytorch.  Advances in Neural Information Processing Systems, 35, 2021.
  * [54] Javier Yu, Joseph A. Vincent, and Mac Schwager.  Dinno: Distributed neural network optimization for multi-robot collaborative learning.  IEEE Robotics and Automation Letters, 7(2):1896–1903, 2022.
  * [55] Tao Zhang and Quanyan Zhu.  Dynamic differential privacy for admm-based distributed classification learning.  IEEE Transactions on Information Forensics and Security, 12(1):172–187, 2017.
  * [56] Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu.  Improving the privacy and accuracy of ADMM-based distributed algorithms.  In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5796–5805. PMLR, 10–15 Jul 2018\.
  * [57] Minghui Zhu and Sonia Martínez.  Discrete-time dynamic average consensus.  Automatica, 46(2):322–329, 2010.

##  Appendix A Convergence Analysis

In this section, we describe a proof of the Convergence Theorem 5.1, showing
that differentially private algorithms do not affect the convergence
guarantees of the base algorithm. For the sake of the theoretical analysis, we
assume the base algorithm converges linearly for all iterations $k\geq 0$.

Convergence Theorem. Let the objective function $l$ be strongly convex and
$L$-smooth, $\theta\in\mathbb{R}^{Nd}$ be a vector concatenating local
variables $\\{\theta_{i}\\}_{i=1}^{N}$, $M(\theta)$ be a function of $\theta$
that is of interest for convergence, and $\sigma$ be the standard deviation of
Gaussian noise for differentially private gradient perturbations. If
$M(\theta)$ of the base decentralized algorithm is Lipschitz w.r.t. a constant
$K$, i.e., $\|M(\theta)-M(\hat{\theta})\|_{2}\leq
K\|\theta-\hat{\theta}\|_{2}$ for any $\theta$ and $\hat{\theta}$, and
converges to the optimal solution $M(\theta^{*})$ at a linear rate,
$M(\theta)$ of the differentially private decentralized algorithm also
converges to the optimal solution $M(\theta^{*})$ at a linear rate within an
error neighborhood on the order of $\mathcal{O}(\sigma)$.

First, we introduce variables that will be important in the proof. Since
$M(\theta)$ of the base decentralized algorithm converges linearly, there
exists $\rho\in(0,1)$ (the contraction factor) such that

$\displaystyle\|M\big{(}\theta^{(k+1)}\big{)}-M(\theta^{*})\|\leq\rho\|M(\theta^{(k)})-M(\theta^{*})\|$
(9)

for all $k\geq 0$, where $\theta^{(k)}$ denotes the parameters at iteration
$k$ and $\theta^{*}$ is the unique optimal solution.

After the general differential privacy algorithm adds Gaussian noise to the
gradient and then updates the parameters $\theta$ (using the noisy gradient),
we obtain an update of the form:

$\displaystyle\tilde{\theta}^{(k)}=\theta^{(k)}+\eta^{(k)}C_{\sigma}\xi^{(k)}$
(10)

where $\tilde{\theta}^{(k)}$ denotes the differentially private algorithm’s
noisy parameters at iteration $k$, $\theta^{(k)}$ is the differentially
private algorithm’s parameters at iteration $k$ before adding noise,
$\eta^{(k)}$ is the learning rate at iteration $k$, $C_{\sigma}$ is a scaling
constant on the noise depending on specific base algorithms, and $\xi^{(k)}$
is the sampled noise at iteration $k$ which is independent across iterations.

The following lemma will be useful in the proof of the convergence theorem.

######  Lemma A.1.

Consider the differentially private decentralized algorithm. Let
$\tilde{\theta}^{(k)}$ be its noisy parameters at iteration $k$ and
$\theta^{(0)}$ be the initial parameters. Then, it holds that

$\displaystyle\|M\big{(}\tilde{\theta}^{(k)})-M(\theta^{*})\|\leq\rho^{k}\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|+KC_{\sigma}\sum_{i=0}^{k}\rho^{i}\eta^{(k-i)}\|\xi^{(i)}\|$
(11)

where $K$ is the Lipschitz constant of $M(\cdot)$ with respect to $\theta$.

###### Proof.

We use induction to prove the lemma. For the initial iteration $k=0$, we have

$\displaystyle\|M\big{(}\tilde{\theta}^{(0)})-M(\theta^{*})\|$
$\displaystyle=\|M\big{(}\tilde{\theta}^{(0)})-M(\theta^{(0)})+M(\theta^{(0)})-M(\theta^{*})\|$
(12)
$\displaystyle\leq\|M\big{(}\tilde{\theta}^{(0)})-M(\theta^{(0)})\|+\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|$

Since $M(\cdot)$ is Lipschitz on $\theta$ with respect to the constant $K$, it
holds for the noisy variable $\tilde{\theta}^{(0)}$ that

$\displaystyle\|M(\tilde{\theta}^{(0)})-M(\theta^{(0)})\|\leq
K\|\tilde{\theta}^{(0)}-\theta^{(0)}\|=K\eta^{(0)}C_{\sigma}\|\xi^{(0)}\|$
(13)

where (10) is used in the last equality. By substituting (13) into (12), we
get

$\displaystyle\|M\big{(}\tilde{\theta}^{(0)})-M(\theta^{*})\|\leq\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|+K\eta^{(0)}C_{\sigma}\|\xi^{(0)}\|$
(14)

and thus, (11) holds for $t=0$. Next, we assume (11) holds for iteration
$k\geq 0$, i.e.,

$\displaystyle\|M\big{(}\tilde{\theta}^{(k)})-M(\theta^{*})\|\leq\rho^{k}\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|+KC_{\sigma}\sum_{i=0}^{k}\rho^{i}\eta^{(k-i)}\|\xi^{(i)}\|$
(15)

and consider iteration $k+1$. By updating $\tilde{\theta}^{(k)}$ with the base
decentralized algorithm and using (9), we have

$\displaystyle\|M\big{(}\theta^{(k+1)}\big{)}-M(\theta^{*})\|$
$\displaystyle\leq\rho\|M(\tilde{\theta}^{(k)})-M(\theta^{*})\|.$ (16)

By substituting (15) into (16), we have

$\displaystyle\|M\big{(}\theta^{(k+1)}\big{)}-M(\theta^{*})\|$
$\displaystyle\leq\rho\|M(\tilde{\theta}^{(k)})-M(\theta^{(k)})\|+\rho\|M(\theta^{(k)})-M(\theta^{*})\|$
(17)
$\displaystyle=\rho^{k+1}\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|+KC_{\sigma}\sum_{i=1}^{k+1}\rho^{i}\eta^{(k+1-i)}\|\xi^{(i)}\|.$

Further, by the triangle inequality and Lipschitz condition of $M(\cdot)$, we
have

$\displaystyle\|M\big{(}\tilde{\theta}^{(k+1)})-M(\theta^{*})\|$
$\displaystyle\leq\|M\big{(}\tilde{\theta}^{(k+1)})-M(\theta^{(k+1)})\|+\|M\big{(}\theta^{(k+1)}\big{)}-M(\theta^{*})\|$
(18)
$\displaystyle=\|M\big{(}\theta^{(k+1)}\big{)}-M(\theta^{*})\|+K\eta^{(k+1)}C_{\sigma}\|\xi^{(k+1)}\|.$

By substituting (17) into (18), we get

$\displaystyle\|M\big{(}\tilde{\theta}^{(k+1)}\big{)}-M(\theta^{*})\|\leq\rho^{k+1}\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|+KC_{\sigma}\sum_{i=0}^{k+1}\rho^{i}\eta^{(k+1-i)}\xi^{(i)}.$
(19)

By combining (14), (15) and (19), we have proved by induction that

$\displaystyle\|M\big{(}\tilde{\theta}^{(k)}\big{)}-M(\theta^{*})\|\leq\rho^{k}\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|+KC_{\sigma}\sum_{i=0}^{k}\rho^{i}\eta^{(k-i)}\xi^{(i)}.$
(20)

∎

Now we will prove the convergence theorem.

###### Proof.

Since each noise term $\xi^{(k)}$ is independently drawn from a normal
Gaussian distribution, we take the expectation over the result from Lemma A.1
to get:

$\displaystyle\mathbb{E}\big{[}\|M\big{(}\tilde{\theta}^{(k)})-M(\theta^{*})\|\big{]}\leq\rho^{k}\mathbb{E}\big{[}\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|\big{]}+KC_{\sigma}\sum_{i=0}^{k}\rho^{i}\eta^{(k-i)}D$
(21)

where $D=\mathbb{E}\big{[}\|\xi\|\big{]}=\mathcal{O}(\sigma)$ since $\xi$ is
has a standard deviation related to $\sigma$. Since $\sum_{i=0}^{k}\rho^{i}$
is the sum of the geometric series with $\rho\in(0,1)$ and the learning rate
is bounded for all iterations, we have

$\displaystyle\sum_{i=0}^{k}\rho^{i}\leq\frac{1}{1-\rho}~{}\text{and}~{}\eta^{(k)}\leq
C_{\eta},~{}\forall~{}k\geq 0.$ (22)

By substituting (22) into (21), we have

$\displaystyle\mathbb{E}\big{[}\|M\big{(}\tilde{\theta}^{(k)})-M(\theta^{*})\|\big{]}\leq\rho^{k}\mathbb{E}\big{[}\|M\big{(}\theta^{(0)}\big{)}-M(\theta^{*})\|\big{]}+\frac{KC_{\sigma}C_{\eta}}{1-\rho}D.$
(23)

Therefore, we have completed the proof with

$\displaystyle\lim_{k\to\infty}\mathbb{E}\big{[}\|M\big{(}\tilde{\theta}^{k})-M(\theta^{*})\|\big{]}\leq\mathcal{O}(\sigma).$
(24)

∎

Lastly, note we do not need to incorporate gradient clipping into the analysis
since gradient clipping is equivalent to rescaling the learning rate (in the
strongly convex context) and this does not affect the convergence behavior.

##  Appendix B Implementing Differentially Private Decentralized Algorithms

In this section, we provide more information about our implementation and
experimental setup. Our full codebase, including launch scripts and
configuration files for each algorithm and privacy budget, is available at:

https://github.com/jbayrooti/dp-dec-learning

Algorithms. We implement DP-DSGD, DP-DSGT, and DP-DiNNO using PyTorch with the
Opacus library [53] for differential privacy utilities. We utilize Opacus’
GradSampleModule, which computes the per-sample-gradients of a batch so that
they can be individually clipped. Clipping the per-sample gradients ensures
that each sample’s contribution to the batch gradient is limited, thus making
it difficult for an attacker to infer sensitive information about individual
samples based on the batch gradients. We also use the following Opacus
utilities: DPDataLoader to sample batches with replacement from the entire
dataset with probability $q$ on each iteration, DPOptimizer to help clip and
aggregate per-sample gradients before taking an optimizer step, and
RDPAccountant to compute cumulative Renyi Differential Privacy of the additive
sampled Gaussian mechanism during training. Our implementation leverages these
utilities during training and customizes the optimization step to integrate
with each of our base, decentralized algorithms to obtain differentially
private decentralized algorithms as described in Section 5.

MNIST Experimental Setup. For our experiments on MNIST classification, we
train $N=10$ agents using the training dataset of 60,000 samples and evaluate
accuracy on the testing dataset of 10,000 samples. In our baseline approach,
central training with differential privacy involves learning from the entire
training dataset. On the other hand, in decentralized differentially private
learning, participating agents only have direct access to a local dataset,
which is a subset of the training dataset. We run all MNIST experiments for
2,000 iterations with a batch size of $256$ using a model with one
convolutional layer and two linear layers as done in [54]. For DP-DSGD and DP-
DSGT, we use a uniform mixing matrix $W$ and $T=1$ primal iterations for DP-
DiNNO as we find this to give the best performance. To select learning rates
for each algorithm and privacy budget, we use Ray’s population-based tuning
algorithm [1] with additional minor hand tuning. We do this to give a
reasonably fair comparison between the algorithms’ performances.

CIFAR-100 Experimental Setup. For our experiments on CIFAR-100 classification,
we train $N=10$ agents using the overall training dataset of 50,000 samples
and measure accuracy on the testing set of 10,000 samples. Each agent trains
directly on its private, non-overlapping dataset with exposure to data classes
as specified by the matrix $A(t)$. To attain higher accuracies on CIFAR-100,
our agents learn local ResNet-9 models with batch norms replaced with group
norms, as is standard in differentially private deep learning [12]. We train
all CIFAR-100 experiments for 20,000 iterations with a virtual batch size of
250 and physical batch size of 50. It is worth noting that tracking per-sample
gradients for $N=10$ different agent models can be memory intensive and thus
limits the model architectures and physical batch sizes we can reasonably
exploit. For these experiments, we use a uniform mixing matrix $W$, $T=2$
primal iterations for DP-DiNNO, and learning rates slightly hand tuned from
the MNIST learning rates using equivalent effort for all three algorithms.

Computing Resources. All MNIST models were trained using 4 NVIDIA GeForce RTX
2080 GPUs and CIFAR-100 models were trained on 2 NVIDIA A100-PCIE-40GB GPUs.
Our membership inference attack procedure utilized both sets of GPUs. Table 3
breaks down the average hours of wall-clock time to train each algorithm for
all our experiments using $N=10$ agents on both MNIST and CIFAR-100. Note that
differentially private training requires computing per-sample gradients and
hence causes longer runtimes.

Table 3: Average GPU wall-clock time per algorithm over experiments on MNIST
and CIFAR-100.

MNIST Average Training Hours
---
Method | Non-Private | Differentially Private
Central | 0.07 | 0.1
DP-DSGD | 1.1 | 1.25
DP-DSGT | 0.84 | 1.24
DP-DiNNO | 0.9 | 1.24

CIFAR-100 Average Training Hours
---
Method | Non-Private | Differentially Private
Central | 1.2 | 2.1
DP-DSGD | 8.2 | 8.8
DP-DSGT | 11.9 | 12.5
DP-DiNNO | 9.8 | 11.0

##  Appendix C CIFAR-100 Experiments

We evaluate our differentially private algorithms on the CIFAR-100
classification task to demonstrate their generalizability to harder tasks and
further study their performance when varying the data distribution available
to each agent across 100 classes.

Table 4: Performance comparison over algorithms and data splits on CIFAR-100.

$\bm{\epsilon=10}$ |  |  |  |
---|---|---|---|---
Method | $t=0$ | $t=0.25$ | $t=0.5$ | $t=0.75$ | $t=1$
Central | 32.3 $\pm$ 0.14 | 32.3 $\pm$ 0.14 | 32.3 $\pm$ 0.14 | 32.3 $\pm$ 0.14 | 32.3 $\pm$ 0.14
DP-DSGD | 24.76 $\pm$ 0.47 | 24.67 $\pm$ 0.6 | 23.37 $\pm$ 0.15 | 22.15 $\pm$ 0.14 | 21.25 $\pm$ 0.16
DP-DSGT |  28.29 $\pm$ 0.3 |  27.55 $\pm$ 0.49 |  27.69 $\pm$ 0.24 |  27.82 $\pm$ 0.14 |  27.14 $\pm$ 0.14
DP-DiNNO | 20.06 $\pm$ 0.7 | 19.62 $\pm$ 0.35 | 19.66 $\pm$ 0.12 | 19.24 $\pm$ 0.35 | 16.62 $\pm$ 0.5

$\bm{\epsilon=\infty}\textbf{ (Non-Private)}$ |  |  |  |
---|---|---|---|---
Method | $t=0$ | $t=0.25$ | $t=0.5$ | $t=0.75$ | $t=1$
Central | 62.08 $\pm$ 0.37 | 62.08 $\pm$ 0.37 | 62.08 $\pm$ 0.37 | 62.08 $\pm$ 0.37 | 62.08 $\pm$ 0.37
DP-DSGD | 50.57 $\pm$ 1.61 | 49.9 $\pm$ 1.22 | 49.54 $\pm$ 2.14 | 50.7 $\pm$ 0.66 | 49.32 $\pm$ 0.39
DP-DSGT |  56.6 $\pm$ 0.11 |  56.35 $\pm$ 1.26 |  56.9 $\pm$ 0.77 |  56.71 $\pm$ 0.86 |  57.92 $\pm$ 0.08
DP-DiNNO | 52.01 $\pm$ 0.7 | 51.76 $\pm$ 0.67 | 52.16 $\pm$ 0.75 | 51.54 $\pm$ 0.48 | 48.73 $\pm$ 2.3

Figure 2: DP-DSGT is relatively invariant to changes in data distributions in
both non-private (left) and private (right) settings. DP-DiNNO and DP-DSGD
experience performance drops for less overlapping per-agent data
distributions, corroborating our findings on MNIST. Differential privacy
induces a notable performance drop relative to non-private training, yet DP-
DSGT remains within 6% of DP-SGD accuracy which is denoted with a dashed line.

We confirm that our differentially private algorithms perform well, as
demonstrated in Table 4 and visually in Figure 2 where means and standard
deviations are reported over three trials. Most notably, DP-DSGT reaches an
accuracy within 6% of the central-trained DP-SGD baseline accuracy under
$(10,10^{-5})$-differential privacy across all three data distribution values.
These results are also largely consistent with our results on MNIST reported
in Table 2. In particular, we confirm that DP-DSGT is roughly invariant to the
data distribution in this problem context with $\epsilon=10$. We also find
that DP-DSGD is more robust to changes in data distribution than DP-DiNNO for
$\epsilon=10$, despite observing more similar performance between the two
algorithms in the MNIST data distribution experiments. It is possible that DP-
DiNNO’s performance could be improved with longer training time or a more
calibrated balance between optimizing performance and consensus. Additionally,
based on our experimentation, we observe that DP-DSGD and DP-DSGT exhibit high
sensitivity to the learning rate choice. However, once an optimal learning
rate is determined, values close to it tend to yield good results across
various settings. In contrast, identifying suitable learning rates for DP-
DiNNO is less demanding, although the algorithm’s performance is more variable
across tasks.

Finally, while our decentralized algorithms achieve accuracies close to that
of DP-SGD on CIFAR-100 under $(10,10^{-5})$-differential privacy, our work is
not necessarily intended to serve as a benchmark for the best possible
performance of private, decentralized deep learning. A recent study [12]
thoroughly investigates closing the DP-SGD performance gap between non-private
and private deep learning through techniques including weight standardization
after convolutions, training with large batch sizes and models (i.e., batch
size of 4096 and wide ResNets), using multiple augmentations per unique sample
(i.e., 16 augmentations), exponentially averaging model parameters, and pre-
training on public data. When combining these techniques, the authors report
state-of-the-art performance for DP-SGD trained from scratch on CIFAR-10 and
ImageNet [12]. It is likely that these techniques would also boost performance
for our differentially private, decentralized algorithms on CIFAR-100. We
leave this exploration to future work.

##  Appendix D Membership Inference Attacks

Overview. In this section, we empirically evaluate our algorithms’ protection
against membership inference attacks using a standard procedure [20, 12]. This
entails lower bounding our algorithms’ privacy guarantees so that we can
compare with the nominal privacy guarantees. It is important to note that this
test does not verify our algorithms’ differential privacy guarantees, as
finding no violations does not mean no violation exists. Nevertheless, finding
no violations provides a sanity check that our algorithm’s differential
privacy guarantees are not easily refuted.

Attack Experiment. We follow the procedure of [20, 12]. Given a baseline
dataset $D$ and “poisoned“ dataset $D^{\prime}=D\cup\\{z\\}$, a model trained
with differential privacy reduces an attacker’s ability to infer whether or
not $z$ is a training member (i.e., whether the model was trained on $D$ or
$D^{\prime}$). We pick $D$ to be a subset of MNIST of size 300 consisting of
only digits labeled 0, 1, or 2 and $z$ to be a blank image labeled as 0. We
select this small subset of MNIST as $D$ with a blank image $z$ because [12]
found such settings to lead to tight lower bounds.

Figure 3: Non-private SGD performance (left) yields highly separable loss distributions on $z$. DP-SGD (right) protects the privacy of the individual sample $z$ with entangled loss distributions. Table 5: Reporting $\epsilon$ lower bounds on differential privacy guarantees. Method | Nominal $\epsilon$ |  $\epsilon$ lower bound
---|---|---
Central | 1 | 0.230
DP-DSGD | 1 | 0.173
DP-DSGT | 1 | 0.129
DP-DiNNO | 1 | 0.165

For both $D$ and $D^{\prime}$, we assign all the training data for one digit
to one of three agents, each using a shallow CNN model, and carry out
decentralized training for 100 iterations under $(1,10^{-2})$-differential
privacy using a clipping threshold of 10. After training, the agent with
training data for digit 0 records the model loss on $z$. A simulated attacker
then takes the trained model as input, along with the point $z$, and outputs a
binary prediction of whether or not $z$ was included in the model’s training
dataset. Kairouz et al [24] prove that for any
$(\epsilon,\delta)$-differentially private algorithm, one can bound the ratio
between the attacker’s true positive rate (TPR) and false positive rate (FPR)
by

$\displaystyle\frac{TPR-\delta}{FPR}<e^{\epsilon}$ (25)

Taking the natural logarithm of both sides reveals a lower bound on $\epsilon$
in terms of TPR, FPR, and $\delta$, which we can compare to our nominal
$\epsilon=1$ used during training to ensure that the algorithm’s empirical
privacy is no weaker than intended.

We initialize all model parameters to the same starting values so that only
the random noise added to gradients is different between models trained on the
same datasets (either $D$ or $D^{\prime}$). We also train DP-SGD models on the
same aggregate datasets for a baseline comparison with a central system.
Overall, we train 5,000 models on each dataset and record the loss values on
$z$. The losses from the first 1,000 models are used to identify a threshold
that maximizes the $\frac{TPR-\delta}{FPR}$ quantity and the remaining losses
are used to evaluate the lower bounds. As done in [20, 12], we gain
statistical confidence in our lower bounds by computing the lower bound of the
$TPR-\delta$ and upper bound of the $FPR$ using Clopper-Pearson confidence
intervals.

For visual insight into this attack, consider Figure 3. The loss distributions
on $z$ are distinct and well-defined for normal central training with
differential privacy, making it easy for an attacker to infer whether or not
$z$ is a member sample based on the model’s loss. In contrast, DP-SGD with
$\epsilon=1$ introduces noise during training to mask the effect of one
individual training sample, resulting in weak membership inference attacks.

For each algorithm, we report our empirical $\epsilon$ lower bounds (which
hold with 95% confidence) in Table 5. Crucially, we find no violation of our
reported $(\epsilon,\delta)$-differential privacy guarantees. It is possible
that for a wider range of models and better choice of threshold, we can obtain
tighter $\epsilon$ lower bounds for our algorithms. Ultimately, these lower
bounds provide evidence that our differentially private algorithms offer
levels of privacy that are not weaker than we claim.