# Considerations on the Theory of Training Models with Differential Privacy

Marten van Dijk1,2,3 and Phuong Ha Nguyen4
1 CWI Amsterdam, The Netherlands
2 Department of Computer Science, Vrije Universiteit Amsterdam, The
Netherlands
3 Department of Electrical and Computer Engineering, University of
Connecticut, CT, USA
4 eBay, CA, USA

<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

In federated learning collaborative learning takes place by a set of clients
who each want to remain in control of how their local training data is used,
in particular, how can each client’s local training data remain private?
Differential privacy is one method to limit privacy leakage. We provide a
general overview of its framework and provable properties, adopt the more
recent hypothesis based definition called Gaussian DP or $f$-DP, and discuss
Differentially Private Stochastic Gradient Descent (DP-SGD). We stay at a meta
level and attempt intuitive explanations and insights in this book chapter.

00footnotetext: † This is a book chapter

_K_ eywords Stochastic Gradient Descent (SGD) $\cdot$ DP-SGD $\cdot$
Differential Privacy (DP) $\cdot$ Gaussian DP

##  1 Introduction

Privacy leakage is a big problem in the big-data era. Solving a learning task
based on big data intrinsically means that only through a collaborative effort
sufficient data is available for training a global model with sufficient clean
accuracy (utility). Federated learning is a framework where a learning task is
solved by a loose federation of participating devices/clients which are
coordinated by a central server [42, 8, 3, 33, 40, 9, 57, 29, 59, 10, 34, 36,
37, 39, 12, 30]. Clients, who use own local data to participate in a learning
task by training a global model, want to have privacy guarantees for their
local proprietary data. For this reason DP-SGD [1] was introduced as it adapts
distributed Stochastic Gradient Descent (SGD)[55] with Differential Privacy
(DP)[19, 15, 21, 18].

The optimization problem for training many Machine Learning (ML) models using
a training set $\\{\xi_{i}\\}_{i=1}^{m}$ of $m$ samples can be formulated as a
finite-sum minimization problem as follows

$\min_{w\in\mathbb{R}^{d}}\left\\{F(w)=\frac{1}{m}\sum_{i=1}^{m}f(w;\xi_{i})\right\\}.$
(1)

The objective is to minimize a loss function with respect to model parameters
$w$. This problem is known as empirical risk minimization and it covers a wide
range of convex and non-convex problems from the ML domain, including, but not
limited to, logistic regression, multi-kernel learning, conditional random
fields and neural networks.

We want to solve (1) in a distributed setting where many clients have their
own local data sets and the finite-sum minimization problem is over the
collection of all local data sets. A widely accepted approach is to repeatedly
use the SGD [50, 46, 47] recursion

$w_{t+1}=w_{t}-\eta_{t}\nabla f(w_{t};\xi),$ (2)

where $w_{t}$ represents the model after the $t$-th iteration; $w_{t}$ is used
in computing the gradient of $f(w_{t};\xi)$, where $\xi$ is a data sample
randomly selected from the data set $\\{\xi_{i}\\}_{i=1}^{m}$ which comprises
the union of all local data sets.

This approach allows each client to perform local SGD recursions for the data
samples $\xi$ that belong to the client’s local training data set. The updates
as a result of the SGD recursion (2) are sent to a centralized server who
aggregates all received updates and maintains a global model. The server
regularly broadcasts its most recent global model so that clients can use it
in their local SGD computations. This allows each client to use what has been
learned from the local data sets at the other clients. This leads to good
accuracy of the final global model.

Each client performs SGD recursions for a batch of local data. These
recursions together represent a local round and at the end of the local round
a local model update (in the form of an aggregate of computed gradients during
the round) is transmitted to the server. The server in turn adds the received
local update to its global model – and once the server receives new updates
from (a significant portion of) all clients, the global model is broadcast to
each of the clients. When considering privacy, we are concerned about how much
information these local updates reveal about the used local data sets. Each
client wants to keep its local data set as private as possible with respect to
the outside world which observes round communication (the outside world
includes all other clients as well).

Rather than reducing the amount of round communication such that less
sensitive information is leaked, differential privacy [19, 15, 21, 18] offers
a solution in which each client-to-server communication is obfuscated by
noise. If the magnitude of the added noise is not too much, then a good
accuracy of the global model can still be achieved albeit at the price of more
overall SGD iterations needed for convergence. On the other hand, only if the
magnitude of the added noise is large enough, then good differential privacy
guarantees can be given. This leads to a friction between desired differential
privacy and desired utility/accuracy.

Section 2 starts discussing DP-SGD [1], which implements differentially
private mini-batch SGD. Section 3 explains differential privacy with various
(divergence based) measures and properties. Section 4 continues detailing the
state-of-the-art hypothesis testing based differential privacy, called $f$-DP
[13], applied to DP-SGD. We conclude with open questions in Section 5.

##  2 Differential Private SGD (DP-SGD)

We analyse the Gaussian based differential privacy method, called DP-SGD, of
[1] in a distributed setting with many clients and a central aggregating
server. A slightly generalized description of DP-SGD is depicted in Algorithm
1. The main goal of DP-SGD is to hide whether the collection of transmitted
round updates $\bar{U}$ corresponds to data set $d$ versus a neighboring data
set $d^{\prime}$; sets $d$ and $d^{\prime}$ are called neighbors if they
differ in exactly one element. In order to accomplish this, DP-SGD introduces
noise, which we will see comes in two flavors clipping noise and Gaussian
noise.

Algorithm 1 Differential Private SGD

1:procedure DP-SGD

2: $N=$ size training data set $d=\\{\xi_{i}\\}_{i=1}^{N}$

3: $E=$ total number of epochs

4: diminishing step size sequence $\\{\eta_{i}\\}$

5:

6: initialize $w$ as the default initial model

7: Interrupt Service Routine (ISR): Whenever a new global model $\hat{w}$ is
received, computation is interrupted and an ISR is called that replaces
$w\leftarrow\hat{w}$ after which computation is resumed

8:

9: for $e\in\\{1,\ldots,E\\}$ do

10: $\\{S_{b}\\}_{b=1}^{N/m}\leftarrow$ ${\tt Sample}_{m}$ with
$S_{b}\subseteq\\{1,\ldots,N\\}$, $|S_{b}|=m$

11: for $b\in\\{1,\ldots,\frac{N}{m}\\}$ do

12: Start of round $(e-1)\frac{N}{m}+b$:

13: for $h\in S_{b}$ do

14: $a_{h}=\nabla_{w}f(w;\xi_{h})$

15: end for

16: $U=\sum_{h=1}^{m}[a_{h}]_{C}$

17: $\bar{U}\leftarrow U+{\cal N}(0,(2C\sigma)^{2}{\bf I})$

18: Transmit $\bar{U}/m$ to central server

19: Locally update $w\leftarrow w-\eta_{(e-1)\frac{N}{m}+b}\cdot\bar{U}/m$

20: end for

21: end for

22:end procedure

###  2.1 Clipping

Rather than using the gradient $a_{h}=\nabla f(w,\xi_{h})$ itself, DP-SGD uses
its clipped version $[\nabla f(w,\xi_{h})]_{C}$ where

$[x]_{C}=x/\max\\{1,\|x\|/C\\}.$

We call this the individual clipping approach since each computed gradient is
individually clipped. Clipping is needed because in general we cannot assume a
bound $C$ on the gradients (for example, the bounded gradient assumption is in
conflict with strong convexity [46]), yet the added gradients in update $U$
need to be bounded by some constant $C$ in order for the DP analysis of [1] to
go through. The reason is that clipping introduces a bound on how much
$U=\sum_{h=1}^{m}[a_{h}]_{C}$ gets affected if the differentiating sample
between $d$ and $d^{\prime}$ is used in its computation. Clipping forces a
small distance between an update $U$ that does not use the differentiating
sample and an update $U^{\prime}$ that computes the same gradients as $U$
except for one of its gradient computations which uses the differentiating
sample. This means that if Gaussian noise is added to $U$ and $U^{\prime}$,
respectively, then the smaller the distance between $U$ and $U^{\prime}$, the
harder it is to figure out whether the actually observed noised update
originates from $d$ or $d^{\prime}$. This leads to a differential privacy
guarantee.

Suppose that $a_{h}$ influences another gradient computation, e.g., $a_{h+1}$.
Then, if the differentiating sample is used in the computation of $a_{h}$,
this affects not only $a_{h}$ but also $a_{h+1}$. Even though both $a_{h}$ and
$a_{h+1}$ will be clipped, this increases the distance between $U$ and
$U^{\prime}$, hence, this weakens the differential privacy. For this reason,
the different gradient computations $a_{h}$ in $U$ should be independent of
one another. In particular, we do not want to implement classical SGD where
the computation of $a_{h}$ updates the local model $w$ which is used in the
next gradient computation $a_{h+1}$. This is the reason for implementing mini-
batch SGD where each gradient $a_{h}$ is computed for the same $w$.

Clipping introduces clipping noise defined as the difference between the
clipped gradient $[a_{h}]_{C}$ and the original gradient $a_{h}$. This affects
the rate of convergence and leads to clipping bias. If convergence is towards
a (local) minimum $w^{*}$ of (1), then DP-SGD will not get closer and closer
to $w^{*}$, but will converge to some model within a radius around $w^{*}$,
where the radius is composed of a clipping bias and a bias as a result of the
desired DP guarantee by adding Gaussian noise, and the radius is also at least
proportional to the last used step size. We notice that clipping noise may not
reduce from round to round: Even though
$\mathrm{E}_{\xi}[\nabla_{w}f(w^{*};\xi)]$ tends to zero (since we converge to
a local minimum), the expected norm of the gradients
$c(w^{*})=\mathrm{E}_{\xi}[\|\nabla_{w}f(w^{*};\xi)\|]$ generally does not
converge to zero. For this reason, the clipping constant $C$ must be
appropriately set (and cannot be too small). E.g., by using the $C$ of another
previous related learning task, or using a public data set for estimating
$c(w^{*})$ while executing DP-SGD.

###  2.2 Mini-Batch SGD

DP-SGD is constraint to a mini-batch SGD approach where before the start of
the $b$-th local round in epoch $e$ a random min-batch $S_{b}$ of sample size
$|S_{b}|=m$ is selected out of a local data set $d$ of size $|d|=N$: In the
description of Algorithm 1 the sampling is done by a sampling procedure ${\tt
Sample}_{m}$ before the start of epoch $e$ for all rounds together. DP-SGD
implements subsampling which chooses a uniformly random subset $S_{b}\subseteq
d$ of size $m$.

The inner loop computes $m$ gradients $a_{h}=\nabla_{w}f(w;\xi_{h})$. Since
there are $N/m$ rounds within an epoch, each epoch has (indeed) a total
gradient complexity of $N=|d|$. We notice that each gradient is computed based
on $w$ which is the last received global model from the server through the
interrupt service routine. In the original DP-SGD, a client waits at the start
of a round till it receives the global model which includes the aggregated
updates of all previous rounds from all clients. The formulation in Algorithm
1 allows for asynchronous behavior, including dropped (or reordering of)
messages from the server which can lead to a client missing out on receiving
global model versions. More importantly, the server may decide to broadcast
global models at a lower rate than the rate(s) at which clients compute and
communicate their noised round updates. This allows clients with different
compute speeds/resources. Also, the rate at which round updates are computed
is not restricted by the throughput of broadcast messages from the server to
clients (of course, it remains restricted by the network throughput from the
clients through aggregation nodes to the server). This implies that parameter
$m$ can potentially be chosen from the whole range $\\{1,\ldots,N\\}$
including very small $m$ leading to many round updates per epoch or large $m$
leading to only a couple round updates per epoch. We will later discuss the
effect of $m$ on convergence and accuracy and DP guarantee.

We notice that too much asynchronous behavior will hurt convergence of the
mini-batch SGD approach and may lead to worse accuracy of the final global
model. For this reason, before starting a round, a client can check into what
extent the recently received global model deviates from the locally kept
model. If this gets too far apart or if the last received global model
happened too many rounds ago, then the client will want to wait till a new
global model is received and the interrupt service routine is triggered. This
implements the necessary synchronous behavior with respect to convergence and
accuracy.

###  2.3 Gaussian Noise

The clipped gradients $[a_{h}]_{C}$ are summed together in round update $U$.
At the end of each local round the round update $U$ is obfuscated by adding
Gaussian noise

${\cal N}(0,(2C\sigma)^{2})$

to each of $U$’s vector entries. The resulting noised round update $\bar{U}$
divided by the mini-batch size $m$ is transmitted to the server.

For neighboring data sets $d$ and $d^{\prime}$, we have that the sensitivity
measured as the Euclidean distance between $U$ based on $d$ and $U^{\prime}$
based on $d^{\prime}$ (see also Section 2.1) is at most $2C$. An adversary
trying to distinguish whether the observed update is from $d$ or $d^{\prime}$
needs to figure out whether the observation is from

$U+{\cal N}(0,(2C\sigma)^{2}{\bf I})\ \ \mbox{ or }\ \ U^{\prime}+{\cal
N}(0,(2C\sigma)^{2}{\bf I}).$

Since $\|U-U^{\prime}\|\leq 2C$, this is at best (for the adversary)
equivalent to hypothesis testing between ${\cal N}(0,(2C\sigma)^{2})$ and
${\cal N}(2C,(2C\sigma)^{2})$. After dividing by $2C$, this is equivalent to
hypothesis testing

${\cal N}(0,\sigma^{2})\ \ \mbox{ versus }\ \ {\cal N}(1,\sigma^{2}).$ (3)

We see that any differential privacy guarantee for the round update is
characterized by $\sigma$.

The argument above does not depend on the properties of function $f$. In fact,
we are free in how we compute the $a_{h}$ in line 14 of Algorithm 1. These may
in themselves depend on more than one sample as long as we start with $w$ for
each computation of $a_{h}$. E.g., the $a_{h}$ may compute updates coming from
a local SGD approach (as used in federated learning), they may be computed
according to a mini-batch SGD style approach, or some other momentum based
approach.

The attentive reader may notice that the original DP-SGD adds ${\cal
N}(0,(C\sigma)^{2}{\bf I})$, a factor 2 less. This is because its DP analysis
and proof assume a slightly different subsampling method. In the original DP-
SGD we have that each round selects a random mini-batch of exactly $m$
samples; this leads to the factor $2$ since $U$ and $U^{\prime}$ will differ
in one gradient, hence, $U-U^{\prime}$ cancels all gradients except for one in
$U$ and one in $U^{\prime}$, both contributing at most $C$ to the norm
$\|U-U^{\prime}\|$, hence, the factor 2.

However, the software package Opacus [48] implements the sampling of DP-SGD
differently: Mini-batches do not have a fixed size, they have a probabilistic
size. For each sample $\xi\in d$, we flip a coin and with probability $m/N$ we
add $\xi$ to the mini-batch. This means that the expected mini-batch size is
equal to $m$. As a result, the DP analysis of [1] holds true and the factor
$2$ can be eliminated. The reason is that now (in the DP analysis)
$U^{\prime}$ has all the gradients of $U$ together with one extra gradient
based on the single differentiating sample between $d$ and $d^{\prime}$. This
implies that all gradients in $U-U^{\prime}$ cancel except for the one based
on the differentiating sample, hence, $\|U-U^{\prime}\|\leq C$.

In the above argument, we assume that the adversary does not learn the
actually used mini-batch size otherwise we will again need the factor $2$ (see
also Section 4.5). The observed scaled noised update $\bar{U}/m$ scales in
expectation with the expected norm of a single computed gradient times the
used mini-batch size divided by the expected mini-batch size $m$. This shows
how $\bar{U}/m$ depends on the used mini-batch size where, for large $m$ and
$N$, it seems reasonable to assume that the adversary cannot gain significant
knowledge about the used mini-batch size from $\bar{U}/m$. We conclude that a
probabilistic mini-batch size is a DP technique that offers a factor $2$ gain.
This chapter summarizes the $f$-DP framework explained for sampling with fixed
mini-batch size leading to the extra factor 2 (the probabilistic approach can
be added as a complimentary technique).

###  2.4 Aggregation at the Server

The server maintains a global model, which we denote by $\hat{w}$. The server
adds to $\hat{w}$ the received scaled noised round update $\bar{U}/m$ after
multiplying with the round step size111The client transmits $(b,e,\bar{U})$ to
the server and the server knows an a-priori agreed (with the client) round
step size sequence. In practice, the client will only transmit a
sparsification or lossy compression of $\bar{U}$ where small entries are
discarded. for round $b$ of epoch $e$,

$\eta_{(e-1)\frac{N}{m}+b}$

(the same as the local model update of $w$ by the client). This allows a
diminishing222 Due to the added Gaussian noise and clipping bias we can only
converge to within some radius around a local minimum $w^{*}$. Therefore, we
may use a diminishing step size that converges to a constant step size equal
to the anticipated radius. E.g., as a rule of thumb, after every epoch we
evaluate the test accuracy based on a public data set and if not increasing,
then we decrease the step size by 10%. step size sequence. Notice that
dividing by the mini-batch size $m$ corresponds to $U$ representing a mini-
batch computation in mini-batch SGD.

Each client will select its own DP posture with own selected parameters $m$,
$C$, $\sigma$, and own data set $d$ with its own size $N$. It makes sense for
the server to collect the noised round updates from various clients during
consecutive time windows and broadcast updated global models at the end of
each window. Rather than adding all the received $\bar{U}$ within a time
window to the global model $\hat{w}$ (after multiplying with the appropriate
client-specific step sizes and dividing by the appropriate client-specific
mini-batch sizes), the server will add a mix of the various local updates. The
mix is according to some weighing vector giving more weight to those clients
whom the server judges having ‘better’ training data sets for the learning
task at hand. In federated learning the server will ask for each time window a
random subset of clients to participate in the training. In the above context
it makes sense to have the step sizes be diminishing333Continuing the previous
footnote, the central server decides when to reduce the step size based on
regularly evaluating the test accuracy, and broadcasts the new step sizes to
the clients. from time window to time window rather than have these be client
specific.

###  2.5 Interrupt Service Routine

The interrupt service routine will replace the locally kept model $w$ by a
received global model $\hat{w}$. This may happen in the middle of a round. We
notice that $\hat{w}$ depends on previously transmitted noised round updates
by the client and other clients. We will discuss how each of these previous
noised round updates have a DP guarantee. By the so-called post-processing
lemma, these previously transmitted noised round updates can participate in
the current computation of a round update $U$ through its dependency on the
global model $\hat{w}$ (through the gradients in $U$) without weakening the DP
guarantee for $\bar{U}$ (which includes Gaussian noise on top of $U$).

Similarly, the client locally updates model $w$ with $\bar{U}$ at the end of a
round. In next rounds this implies that $w$ still only depends on previously
transmitted noised round updates by the client and other clients, and again by
the post-processing lemma the DP guarantees of future noised round updates do
not degrade. As soon as a new global model $\hat{w}$ is received by the
interrupt service routine it will overwrite $w$, that is, the current local
model is discarded. This is justified because the newly received global model
includes the client’s own previously communicated noised updates $\bar{U}$ (if
the corresponding messages were not dropped and did not suffer too much
latency), hence, the information of its own local updates is incorporated in
the newly received $\hat{w}$.

###  2.6 DP Principles and Utility

The strength of the resulting DP guarantee depends on how much utility we are
okay with sacrificing. The differential privacy guarantee is discussed in
Section 4. The principle of using Gaussian noise bootstraps DP for each round,
see (3); the principle of subsampling in the form of random mini-batches of
size $m$ amplifies DP (because only with probability $m/N$ a round uses the
differentiating sample and can leak privacy in the first place); and the
principle of composition of DP guarantees for each round over multiple epochs
yields the overall DP guarantee.

Utility is measured in terms of the (test) accuracy of the final global model
and secondary metrics are convergence rate, round complexity $(N/m)\cdot E$
calculated as the total number of rounds per client (communication is costly),
total gradient complexity $E\cdot N$ calculated as the total number of
computed gradients per client, information dispersal characterized by the
delay or latency of what is learned from local data sets which is calculated
as the number $m$ of gradient computations between consecutive round
communications to the server, and client’s memory usage.

The final accuracy depends on the amount of clipping noise and Gaussian noise:
Once convergence sets in, the clipping noise will be small and close to zero
if the clipping constant is appropriately chosen (at least a factor larger
than $c(w^{*})$, see Section 2.1). However, each round update $U$ has noise
sampled from ${\cal N}(0,(2C\sigma)^{2}{\bf I})$ added to itself. If this
noise is small relative to the norm of $U$, then we expect accuracy not to
suffer too much if the neural network model is sufficiently robust against
noise (it turns out that deeper neural networks are quite sensitive). When
convergence progresses and the clipping constant is large enough, then $U/m$
behaves like an average of unclipped gradients which is an estimate of
$\mathrm{E}_{\xi}[\nabla_{w}f(w^{*};\xi)]$ which tends to zero. This means
that the Gaussian noise relative to the norm of $U$ becomes larger, which puts
a limit on how much accuracy/utility can be achieved.

Since the DP guarantee depends on $\sigma$ but not on $C$ while the added
Gaussian noise scales with $C\cdot\sigma$, we will want to implement a form of
(differential private) adaptive clipping (we notice that the DP analysis of
DP-SGD holds for clipping constants $C$ that vary from round to round).
Experimentation is needed to fine-tune the parameters $m$, (adaptive) $C$, and
$\sigma$. Despite fine tuning, we remark that the added clipping and Gaussian
noise for differential privacy results in convergence to a final global model
with smaller (test) accuracy (than what otherwise, without DP, can be
achieved).

The following thought experiment shows how the batch size $m$ influences
utility and differential privacy: Suppose we increase $m$ to $am$, a factor
$a$ larger. Then the norm of updates $U$ will become a factor $a$ larger. As a
result, with respect to convergence to the final global model, we should be
able to cope with a factor $a$ larger Gaussian noise. That is, by keeping the
relative amount of noise with respect to the norm of $U$ constant, the new
updates corresponding to batch size $am$ can be noised with

$a\cdot{\cal N}(0,(2C\sigma)^{2}{\bf I})={\cal N}(0,(2C\sigma\cdot a)^{2}{\bf
I}).$

In fact the communicated averaged noised round update $\bar{U}/(am)$ has noise

$a\cdot{\cal N}(0,(2C\sigma)^{2}{\bf I})/(am)={\cal N}(0,(2C\sigma/m)^{2}{\bf
I}),$

the same as the original communicated averaged noised round update (before the
thought experiment). This shows that we can use the factor $a$ for increasing
(1) the clipping constant $C$ (which reduces the clipping noise, which is most
prevalent at the start of DP-SGD, so that convergence can more easily
bootstrap) and/or increasing (2) the standard deviation $\sigma$ (which
improves the DP guarantee); the resulting new clipping constant $C^{\prime}$
and standard deviation $\sigma^{\prime}$ satisfy
$2C^{\prime}\sigma^{\prime}=2C\sigma\cdot a$.

However, the disadvantage of increasing the batch size with a factor $a$ is a
multiplicative factor $a$ increased amount of gradient computations since
overall we will still need the same number of rounds for convergence, or
equivalently, the same number of SGD update steps toward a local minimum
$w^{*}$. This means a factor $a$ larger number of epochs (one epoch measures
$N$ gradient computations, hence, if $m$ is increased to $ma$, we have a
factor $a$ smaller number of rounds per epoch). But this has a direct impact
on the DP guarantee. As we will see in Section 4.5 (when discussing Gaussian
DP), before the thought experiment we have a $G_{\mu}$-DP guarantee, where
$\mu$ is proportional to $\sqrt{Em/(N\sigma^{2})}$ for ‘large $N$ and $E$.’
The thought experiment increases $m$ by $a$ and increases $E$ by $a$. Hence,
for the same $\sigma$ we will now have the significantly worse $\approx
G_{\mu\cdot a}$-DP guarantee. If the factor $a$ is fully used for increasing
$\sigma$ by a factor $a$, then for ‘large $N$ and $E$’ the Gaussian DP
parameter $\mu\cdot a$ decreases back to $\mu$ and the overall DP guarantee
remains the same. Notice that the total number of gradient computations
increases from $E$ to $aE$, while the balance between utility and differential
privacy seems to remain444Here, we notice that a larger $a$ does have the
advantage that $h(a\sigma)$ in Section 4.5 tends to $1/(a\sigma)$ leading to
$\mu$ being proportional to $1/(a\sigma)$ as stated. If $a$ and as a result
$a\sigma$ remains relatively small, then $h(\sigma)$ behaves exponentially
small in $a\sigma$ and $\mu$ is proportional to $e^{1/(2(a\sigma)^{2})}$ which
is a much worse dependency on $a\sigma$ leading to an unacceptable DP
guarantee. the same. The above thought experiment shows that finding the right
hyper parameter setting is not straight forward.

Hyperparameter search depends on the used data set. Either we adopt a
hyperparameter setting from another similar learning task, or we search for
hyperparameters based on the client data sets. In practice, in order to find
good parameters $m$, $C$, and $\sigma$, we basically do a grid search by (1)
fixing some standard settings (from similar learning tasks) for sample size
$m$, e.g., 16, 32, 64, 128 and 256 etc., (2) fixing some standard settings
(from similar learning tasks) for clipping constant $C$, e.g., 0.001, 0.01,
0.1, etc., and then (3) trying some reasonable settings for $\sigma$ (based on
the client data sets). If the grid search indeed uses client data sets, then
we need to make sure that the additional privacy leakage due to the search is
small. This is discussed in Appendix D of [1], see also [27].

###  2.7 Normalization

In practice we will also want to use data normalization [53] as a pre-
processing step. This requires computing the mean and variance over all data
samples from $d$. This makes normalized data samples depend on all samples in
$d$. For this reason we need differential private data normalization. That is,
a differential private noisy mean and noisy variance is revealed a-priori.
This leads to some privacy leakage. The advantage is that we can now rewrite
${\cal A}$ as an algorithm that takes as input $w$, the original data samples
$\\{\xi_{h}\\}_{h\in S_{b}}$ together with the revealed noisy mean and noisy
variance. ${\cal A}$ first normalizes each data sample after which it starts
to compute gradients etc. In the $f$-DP framework, privacy leakage is now
characterized as a trade-off function of the differential private data
normalization pre-processing composed with the trade-off function
corresponding to the DP analysis of DP-SGD (which does not consider data
normalization).

We notice that batch normalization is not compatible with the DP analysis of
DP-SGD with its individual clipping of each gradient (since this introduces
dependencies among the clipped gradients in $U$ and the upper bound of $2C$ on
the sensitivity does not hold). On the other hand layer normalization as well
as group and instance normalization are compatible (because these only concern
single gradient computations). We notice that if $a_{h}$ is computed itself by
using a local mini-batch SGD approach, then batch normalization of the used
mini-batch can be integrated within its computation.

As a final remark, our discussion assumes that we already know how to
represent data samples by extracting features. We can use Principal Component
Analysis (PCA) for dimensionality reduction, that is, learning a set of
features which we want to use to represent data samples. PCA can be made
differentially private [7] in that the resulting feature extraction method
(feature transform) has a DP guarantee with respect to the data samples that
were used for computing the transform. DP-SGD can be seen as a post-processing
after PCA, which is used to represent the local training data samples for
which DP-SGD achieves a DP guarantee. In practice, we often already know how
to represent the data for our learning task and we already know which function
$f(w;\xi)$ to use, i.e., which neural network topology and loss function to
use (due to the success of transfer learning we can adopt data representations
and $f$ from other learning tasks).

##  3 Differential Privacy

In order to prevent data leakage from inference attacks in machine learning
[38] such as the deep leakage from gradients attack [62, 61, 23] or the
membership inference attack [51, 45, 52] a range of privacy-preserving methods
have been proposed. Privacy-preserving solutions for federated learning are
Local Differential Privacy (LDP) solutions [1, 2, 44, 54, 28, 14] and Central
Differential Privacy (CDP) solutions [44, 25, 41, 49, 60]. In LDP, the noise
for achieving differential privacy is computed locally at each client and is
added to the updates before sending to the server – in this chapter we only
consider LDP. In CDP, a trusted server (aka trusted third party) aggregates
received client updates into a global model; in order to achieve differential
privacy the server adds noise to the global model before communicating it to
the clients.

Differential privacy [19, 15, 21, 18], see [16] for an excellent textbook,
defines privacy guarantees for algorithms on databases, in our case a client’s
sequence of mini-batch gradient computations on his/her training data set. The
guarantee quantifies into what extent the output of a client (the collection
of updates communicated to the server) can be used to differentiate among two
adjacent training data sets $d$ and $d^{\prime}$ (i.e., where one set has one
extra element compared to the other set).

###  3.1 Characteristics of a Differential Privacy Measure

In DP-SGD, the client wants to keep its local training data set as private as
possible. Each noised round update $\bar{U}$ leaks privacy. Let us define
round mechanism ${\cal M}_{b}$ as the round computation that outputs $\bar{U}$
for round $b$. The input of ${\cal M}_{b}$ is data set $d$ together with an
updated local model $w$. We have the following recursion

$\bar{U}_{b}\leftarrow{\cal M}_{b}(w_{b};d),$

where $w_{b}$ is a function of received global model updates which themselves
depend on other client’s round updates in combination with own previously
transmitted round updates $\bar{U}_{1},\ldots,\bar{U}_{b-1}$. To express this
dependency, we use the notation

$w_{b}\leftarrow{\sf W}(\bar{U}_{1},\ldots,\bar{U}_{b-1}),$

where ${\tt W}$ receives the global models of the server (and in essence
reflects the interrupt service routine). We define the overall mechanism
${\cal M}$ as the (adaptive) composition of all round mechanisms ${\cal
M}_{b}$, i.e.,

$\\{\bar{U}_{b}\\}\leftarrow{\cal M}(d)\mbox{ with }\bar{U}_{b}\leftarrow{\cal
M}_{b}({\tt W}(\bar{U}_{1},\ldots,\bar{U}_{b-1});d).$

When defining a DP measure, we will want to be able to compose the DP
guarantees for the different round mechanisms ${\cal M}_{b}$: If we can prove
that ${\cal M}_{b}({\tt aux};\cdot)$ has a certain DP guarantee, denoted by
${\tt DP}_{b}$, for all ${\tt aux}$ (that can be output by ${\tt W}(\ldots)$),
then the composition ${\cal M}$ of all round mechanisms ${\cal M}_{b}$ should
have a composed DP guarantee

${\tt DP}_{1}\otimes{\tt DP}_{2}\otimes\ldots\otimes{\tt DP}_{(N/m)\cdot E}$

for some composition tensor $\otimes$ over DP measures.

Once a DP guarantee for mechanism ${\cal M}$ is proven, we do not want it to
weaken due to post-processing of the output of ${\cal M}$. In particular, the
central server uses the output of ${\cal M}$ for keeping track of and
computing a final global model for the learning task at hand. This final model
should still have the same (or stronger) differential privacy posture. Let us
denote the post-processing by a procedure ${\tt P}$. If ${\cal M}$ has DP
guarantee ${\tt DP}$, then we want ${\tt P}\circ{\cal M}$ to also have DP
guarantee ${\tt DP}$ (this is called the post-processing lemma),

$[{\tt DP}\mbox{ for }{\cal M}]\ \Rightarrow\ [{\tt DP}\mbox{ for }{\tt
P}\circ{\cal M}].$

We want our DP measure to be compatible with subsampling: We want to be able
to show that if a round mechanism ${\cal M}_{b}$ has guarantee ${\tt DP}$
without subsampling, then ${\cal M}_{b}\circ{\tt Sample}_{m}$ has an ‘easy’ to
characterize amplified guarantee ${\tt DP}^{\prime}$, ‘${\tt
DP}^{\prime}\geq{\tt DP}$.’

Finally, we want a differential privacy measure which fits our intuition, in
particular, how privacy should be characterized and in what circumstances an
attacker can learn private information from observed mechanism outputs.
Differential privacy measures are about the difficulty of distinguishing
whether the observed output $o$ is from the distribution ${\cal M}(d)$ or from
the distribution ${\cal M}(d^{\prime})$, where $d$ and $d^{\prime}$ are
neighboring data sets in that they have all but one differentiating sample in
common. The DP guarantee measures in to what extent

${\tt Pr}[o\sim{\cal M}(d)]\ \ \mbox{ and }\ \ {\tt Pr}[o\sim{\cal
M}(d^{\prime})]$

are alike for all neighboring $d$ and $d^{\prime}$. Here, we want to reflect
the intuition that for more likely observations $o$ the two probabilities
should be close together while for unlikely observations $o$ we care less
whether the two probabilities are close. This reflects how we think about the
adversary: Only in rare unlikely cases, a lot or all privacy may leak, while
in the common case there is very little privacy leakage. In cryptology we
would want to interpret ‘rare’ as a negligible probability in some security
parameter and in the common case we want the two probabilities/distributions
to be ‘statistically close’ with their distance negligible in some security
parameter. Such strong guarantees cannot be extracted from DP analysis where
we control privacy leakage in exchange for utility/accuracy; we cannot make
privacy leakage negligible.

The DP measure is characterized in terms of probabilities and statistics. This
is referred to as static security or information theoretical security and
allows an adversary with unbounded computational resources in order to
differentiate between the hypothesis $o\sim{\cal M}(d)$ and hypothesis
$o\sim{\cal M}(d^{\prime})$. For completeness, in cryptology we also have the
notion of computational security meaning that the difficulty of
differentiating the two hypotheses can be reduced to solving a computational
hard problem (and, since the brightest mathematicians and computer scientists
have not been able to find an algorithm which solves this problem efficiently
with practical computational resources, we believe that the attacker cannot
solve this problem in feasible time). Computational security allows one to
obtain security guarantees where the attackers advantage or success is
negligible in some security parameter.

The above expresses individual privacy. We can generalize towards group
privacy by considering data sets $d$ and $d^{\prime}$ that differ in at most
$g$ samples. In this case we say that a mechanism has a DP guarantee with
respect to a group of $g$ samples.

###  3.2 $(\epsilon,\delta)$-Differential Privacy

A randomized mechanism ${\cal M}:D\rightarrow R$ is $(\epsilon,\delta)$-DP
(Differentially Private) [18] if for any adjacent $d$ and $d^{\prime}$ in $D$
and for any subset $S\subseteq R$ of outputs,

${\tt Pr}[{\cal M}(d)\in S]\leq e^{\epsilon}\cdot{\tt Pr}[{\cal
M}(d^{\prime})\in S]+\delta,$ (4)

where the probabilities are taken over the coin flips of mechanism ${\cal M}$.

Historically, differential privacy was introduced [18] and first defined as
$\epsilon$-DP [19] which is $(\epsilon,\delta)$-DP with $\delta=0$. In order
to achieve $\epsilon$-DP even an unlikely set $S$ of outputs needs to satisfy
(4) for $\delta=0$. This means that the tail distributions of ${\tt Pr}[{\cal
M}(d)\in S]$ and ${\tt Pr}[{\cal M}(d^{\prime})\in S]$ cannot differ more than
a factor $e^{\epsilon}$. This is a much too strong DP requirement, since the
probability to observe an output that corresponds to unlikely tail events is
already very small to begin with. Therefore, $\delta$ was introduced so that
tail distributions with probability $\leq\delta$ do not need to be close
together within a factor $e^{\epsilon}$. This allows one to achieve the more
relaxed $(\epsilon,\delta)$-DP guarantee where an $\epsilon$-DP guarantee
cannot be proven.

The privacy loss incurred by observing an output $o$ is given by

$L^{o}_{{\cal M}(d)\|{\cal M}(d^{\prime})}=\ln\left(\frac{{\tt Pr}[{\cal
M}(d)=o]}{{\tt Pr}[{\cal M}(d^{\prime})=o]}\right).$ (5)

As explained in [21] $(\epsilon,\delta)$-DP ensures that for all adjacent $d$
and $d^{\prime}$ the absolute value of privacy loss will be bounded by
$\epsilon$ with probability at least $1-\delta$ (with probability at most
$\delta$, observation $o$ is part of the tail); $(\epsilon,\delta)$-DP allows
a $\delta$ probability of ‘catastrophic privacy failure’ and from a
cryptographic perspective we want this negligibly small. However, when using
differential privacy in machine learning we typically use $\delta=1/N$ (or
$1/(10N)$) inversely proportional with the data set size $N$ (this seems to
correspond well with the intuition when a local update should cause an
unlikely/tail observation due to the nature of the specific batch of local
data samples that was used in the computation of the local update). Concerning
parameter $\epsilon$, the larger $\epsilon$ the more certain the adversary is
about which of $d$ or $d^{\prime}$ caused observation $o$.

Compared to $(\epsilon,0)$-DP, the relaxation by $\delta$ allows an improved
and asymptotically tight analysis of the cumulative privacy loss incurred by
composition of multiple differentially private mechanisms; [17] states an
advanced composition theorem (a factor half improvement over [20]): For all
$\epsilon,\delta,\delta^{\prime}\geq 0$, the class of
$(\epsilon,\delta^{\prime})$-DP mechanisms satisfies

$(\sqrt{2k\ln(1/\delta)}\cdot\epsilon+k\epsilon(e^{\epsilon}-1)/2,k\delta^{\prime}+\delta)\mbox{-DP}$

under $k$-fold adaptive composition. This means that only for
$k\leq(1-\delta)/\delta^{\prime}$ the privacy failure probability remains
bounded to something smaller than 1.

For group privacy, the literature shows $(g\epsilon,ge^{g-1}\delta)$-DP for
groups of size $g$. Here, we see an exponential dependency in $g$ due to the
$ge^{g-1}$ term in the privacy failure probability. This means that only for
very small $\delta$, the failure probability remains bounded to something
smaller than $1$.

We conclude that $k$-fold composition and group privacy for group size $g$
only lead to useful bounds for relatively small $k$ and $g$. If we restrict
ourselves to a subclass of mechanisms, then we may be able to prove practical
DP bounds for composition and group privacy for much larger and practical $k$
and $g$. We will define such subclasses by imposing properties on the privacy
loss.

###  3.3 Divergence Based DP Measures

In order to get better trade-offs for composition and group privacy we want to
weigh the tail distribution of unlikely observations in such a way that more
unlikely observations are allowed to leak even more privacy. So, rather than
weighing all unlikely observations equally likely, which results in the
privacy failure probability $\delta$, we want to be more careful. This will
allow improved DP bounds for composition and group privacy.

The first idea is to treat the loss function (5) as a random variable $Z$ and
note that in a $k$-fold composition we observe $k$ drawings of random variable
$Z$. Due to the law of large numbers, the average of these drawings will be
concentrated around the mean of the loss function. This leads to the notion of
Concentrated Differential Privacy (CDP) first introduced in [17] by framing
the loss function as a subgaussian random variable after subtracting its mean.
This was re-interpreted and relaxed by using Renyi entropy in [4] and its
authors followed up with the notion zero-CDP (zCDP) in [5]: A mechanism ${\cal
M}$ is $\rho$-zCDP if, for all $\alpha>1$, the Renyi divergence

${\tt D}_{\alpha}({\cal M}(d)\|{\cal
M}(d^{\prime}))=\frac{\ln(\mathbb{E}_{o\sim{\cal
M}(d)}[e^{(1-\alpha)Z}])}{1-\alpha}\mbox{ with }Z=L^{o}_{{\cal M}(d)\|{\cal
M}(d^{\prime})}$

satisfies

${\tt D}_{\alpha}({\cal M}(d)\|{\cal M}(d^{\prime}))\leq\rho\alpha.$ (6)

This DP guarantee requires the tail of $Z$ to be subgaussian, i.e., ${\tt
Pr}[Z>t+\rho]<e^{-t^{2}/(4\rho)}$ for all $t\geq 0$ (the tail behaves like
$Z\sim{\cal N}(\rho,2\rho)$). If the loss function satisfies this property for
a collection of $k$ mechanisms (each of the mechanisms is $\rho$-zCDP), then
their $k$-fold adaptive composition is $k\rho$-zCDP. If a mechanism is
$\rho$-zCDP for individual privacy, then it is $g^{2}\rho$-zCDP for groups of
size $g$. This shows that if we can prove that our DP principles lead to a
subgaussian tail of the loss function $Z$, then we obtain interpretable DP
guarantees even for large $k$ and $g$.

After the introduction of $\rho$-zCDP, Renyi DP (RDP) was introduced by [43];
$(\omega,\tau)$-RDP requires

${\tt D}_{\alpha}({\cal M}(d)\|{\cal M}(d^{\prime}))\leq\tau\mbox{ for all
}\alpha\in(1,\omega).$

Here, $\alpha=1$ bounds the geometric mean of $e^{Z}$, $\alpha=2$ bounds the
arithmetic mean of $e^{Z}$, $\alpha=3$ bounds the quadratic mean of $e^{Z}$,
etc., and $\alpha=\infty$ bounds the maximum value of $e^{Z}$ which is
equivalent to $(\tau,0)$-DP. RDP also leads to simple computable composition
and group privacy. The advantage of zCDP over RDP is that it covers all
$\alpha$ at once: Larger $\alpha$ put more weight on the tail of $Z$, also the
mean gets larger. This means that $\tau$ in the RDP definition should increase
with $\alpha$ and this is realized by zCDP by setting $\tau=\rho\alpha$ for
all $\alpha\in(1,\infty)$.

The above discussion leads naturally to the definition of $(\rho,\omega)$-tCDP
[6]: A mechanism is $\omega$-truncated $\rho$-CDP if it satisfies (6) only for
$\alpha\in(1,\omega)$. tCDP requires $Z$ to be subgaussian near the origin
(like zCDP), i.e., ${\tt Pr}[Z>t+\rho]<e^{-t^{2}/(4\rho)}$ for all $0\leq
t\leq 2\rho(\omega-1)$, but only subexponential in $Z$’s tail, i.e., we get
the weaker subexponential tail bound ${\tt Pr}[Z>t+\rho]\leq
e^{(\omega-1)^{2}\rho}e^{-(\omega-1)t}$. This relaxes zCDP while still
obtaining interpretable DP guarantees for composition and group privacy, and
also subsampling.

The main concern with each of the divergence based DP measures is a lack of
transparency of how the attacker can best distinguish the hypotheses
$o\sim{\cal M}(d)$ and $o\sim{\cal M}(d^{\prime})$. The next section
introduces the $f$-DP framework which provides a hypothesis testing based
approach. It introduces trade-off functions that capture all the information
needed for fully characterizing privacy leakage; a trade-off function can be
used to derive any divergence based DP guarantee like the ones discussed above
(but not the other way around), see Appendix B in [13]. Rather than extracting
a divergence based DP guarantee from a trade-off function for DP-SGD, we will
keep the trade-off function itself as it has an easy transparent
interpretation.

##  4 Gaussian Differential Privacy

Dong et al. [13] introduced the state-of-the-art DP formulation based on
hypothesis testing. From the attacker’s perspective, it is natural to
formulate the problem of distinguishing two neighboring data sets $d$ and
$d^{\prime}$ based on the output of a DP mechanism ${\cal M}$ as a hypothesis
testing problem:

$H_{0}:\mbox{ the underlying data set is }d\ \ \ \ \mbox{ versus }\ \ \ \
H_{1}:\mbox{ the underlying data set is }d^{\prime}.$

Here, neighboring means that either $|d\setminus d^{\prime}|=1$ or
$|d^{\prime}\setminus d|=1$. More precisely, in the context of mechanism
${\cal M}$, ${\cal M}(d)$ and ${\cal M}(d^{\prime})$ take as input
representations $r$ and $r^{\prime}$ of data sets $d$ and $d^{\prime}$ which
are ‘neighbors.’ The representations are mappings from a set of indices to
data samples with the property that if $r(i)\in d\cap d^{\prime}$ or
$r^{\prime}(i)\in d\cap d^{\prime}$, then $r(i)=r^{\prime}(i)$. This means
that the mapping from indices to data samples in $d\cap d^{\prime}$ is the
same for the representation of $d$ and the representation of $d^{\prime}$. In
other words the mapping from indices to data samples for $d$ and $d^{\prime}$
only differ for indices corresponding to the differentiating data samples in
$(d\setminus d^{\prime})\cup(d^{\prime}\setminus d)$. In this sense the two
mappings (data set representations) are neighbors.

We define the Type I and Type II errors by

$\alpha_{\phi}=\mathbb{E}_{o\sim{\cal M}(d)}[\phi(o)]\mbox{ and
}\beta_{\phi}=1-\mathbb{E}_{o\sim{\cal M}(d^{\prime})}[\phi(o)],$

where $\phi$ in $[0,1]$ denotes the rejection rule which takes the output of
the DP mechanism as input. We flip a coin and reject the null hypothesis with
probability $\phi$. The optimal trade-off between Type I and Type II errors is
given by the trade-off function

$T({\cal M}(d),{\cal M}(d^{\prime}))(\alpha)=\inf_{\phi}\\{\beta_{\phi}\ :\
\alpha_{\phi}\leq\alpha\\},$

for $\alpha\in[0,1]$, where the infimum is taken over all measurable rejection
rules $\phi$. If the two hypotheses are fully indistinguishable, then this
leads to the trade-off function $1-\alpha$. We say a function
$f\in[0,1]\rightarrow[0,1]$ is a trade-off function if and only if it is
convex, continuous, non-increasing, and $0\leq f(x)\leq 1-x$ for $x\in[0,1]$.

We define a mechanism ${\cal M}$ to be $f$-DP if $f$ is a trade-off function
and

$T({\cal M}(d),{\cal M}(d^{\prime}))\geq f$

for all neighboring $d$ and $d^{\prime}$. Proposition 2.5 in [13] is an
adaptation of a result in [58] and states that a mechanism is
$(\epsilon,\delta)$-DP if and only if the mechanism is
$f_{\epsilon,\delta}$-DP, where

$f_{\epsilon,\delta}(\alpha)=\min\\{0,1-\delta-e^{\epsilon}\alpha,(1-\delta-\alpha)e^{-\epsilon}\\}.$

We see that $f$-DP has the $(\epsilon,\delta)$-DP formulation as a special
case. It turns out that the original DP-SGD algorithm can be tightly analysed
by using $f$-DP.

###  4.1 Gaussian DP

In order to proceed, [13] first defines Gaussian DP as another special case of
$f$-DP as follows: We define the trade-off function

$G_{\mu}(\alpha)=T({\cal N}(0,1),{\cal
N}(\mu,1))(\alpha)=\Phi(\Phi^{-1}(1-\alpha)-\mu),$

where $\Phi$ is the standard normal cumulative distribution of ${\cal
N}(0,1)$. We define a mechanism to be $\mu$-Gaussian DP if it is $G_{\mu}$-DP.
Corollary 2.13 in [13] shows that a mechanism is $\mu$-Gaussian DP if and only
if it is $(\epsilon,\delta(\epsilon))$-DP for all $\epsilon\geq 0$, where

$\delta(\epsilon)=\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2})-e^{\epsilon}\Phi(-\frac{\epsilon}{\mu}-\frac{\mu}{2}).$
(7)

Suppose that a mechanism ${\cal M}(d)$ computes some function
$u(d)\in\mathbb{R}^{n}$ and adds Gaussian noise ${\cal N}(0,(c\sigma)^{2}{\bf
I})$, that is, the mechanism outputs $o\sim u(d)+{\cal N}(0,(c\sigma)^{2}{\bf
I})$. Suppose that $c$ denotes the sensitivity of function $u(\cdot)$, that
is,

$\|u(d)-u(d^{\prime})\|\leq c$

for neighboring $d$ and $d^{\prime}$; the mechanism corresponding to one round
update in Algorithm 1 has sensitivity $c=2C$. After projecting the observed
$o$ onto the line that connects $u(d)$ and $u(d^{\prime})$ and after
normalizing by dividing by $c$, we have that differentiating whether $o$
corresponds to $d$ or $d^{\prime}$ is in the best case for the adversary
(i.e., $\|u(d)-u(d^{\prime})\|=c$) equivalent to differentiating whether a
received output is from ${\cal N}(0,\sigma^{2})$ or from ${\cal
N}(1,\sigma^{2})$. Or, equivalently, from ${\cal N}(0,1)$ or from ${\cal
N}(1/\sigma,1)$. This is how the Gaussian trade-off function $G_{\sigma^{-1}}$
comes into the picture.

###  4.2 Subsampling

Besides implementing Gaussian noise, DP-SGD also uses sub-sampling: For a data
set $d$ of $N$ samples, ${\tt Sample}_{m}(d)$ selects a subset of size $m$
from $d$ uniformly at random. We define convex combinations

$f_{p}(\alpha)=pf(\alpha)+(1-p)(1-\alpha)$

with corresponding $p$-sampling operator

$C_{p}(f)=\min\\{f_{p},f_{p}^{-1}\\}^{**},$

where the conjugate $h^{*}$ of a function $h$ is defined as

$h^{*}(y)=\sup_{x}\\{yx-h(x)\\}$

and the inverse $h^{-1}$ of a trade-off function $h$ is defined as

$h^{-1}(\alpha)=\inf\\{t\in[0,1]\ |\ h(t)\leq\alpha\\}$ (8)

and is itself a trade-off function (as an example, we notice that
$G_{\mu}=G_{\mu}^{-1}$ and we say $G_{\mu}$ is symmetric). Theorem 4.2 in [13]
shows that if a mechanism ${\cal M}$ on data sets of size $N$ is $f$-DP, then
the subsampled mechanism ${\cal M}\circ{\tt Sample}_{m}$ is $C_{m/N}(f)$-DP.

The intuition behind operator $C_{p}$ is as follows. First, ${\tt
Sample}_{m}(d)$ samples the differentiating element between $d$ and
$d^{\prime}$ with probability $p$. In this case the computations ${\cal
M}\circ{\tt Sample}_{m}(d)$ and ${\cal M}\circ{\tt Sample}_{m}(d^{\prime})$
are different and hypothesis testing is possible with trade-off function
$f(\alpha)$. With probability $1-p$ no hypothesis testing is possible and we
have trade-off function $1-\alpha$. This leads to the convex combination
$f_{p}$.

Second, we notice if $h=T({\cal M}(d),{\cal M}(d^{\prime}))$, then
$h^{-1}=T({\cal M}(d^{\prime}),{\cal M}(d))$. Therefore, if ${\cal M}$ is
$f$-DP (which holds for all pairs of neighboring data sets, in particular, for
the pairs $(d,d^{\prime})$ and $(d^{\prime},d)$), then both $h\geq f$ and
$h^{-1}\geq f$ and we have a symmetric upper bound $\min\\{h,h^{-1}\\}\geq f$.
Since $f$ is a trade-off function, $f$ is convex and we can compute a tighter
upper bound: $f$ is at most the largest convex function
$\leq\min\\{h,h^{-1}\\}$, which is equal to the double conjugate
$\min\\{h,h^{-1}\\}^{**}$. From this we obtain the definition of operator
$C_{p}$.

###  4.3 Composition

The tensor product $f\otimes h$ for trade-off functions $f=T(P,Q)$ and
$h=T(P^{\prime},Q^{\prime})$ is well-defined by

$f\otimes h=T(P\times P^{\prime},Q\times Q^{\prime}).$

Let $y_{i}\leftarrow{\cal M}_{i}(\texttt{aux},d)$ with
$\texttt{aux}=(y_{1},\ldots,y_{i-1})$. Theorem 3.2 in [13] shows that if
${\cal M}_{i}(\texttt{aux},.)$ is $f_{i}$-DP for all aux, then the composed
mechanism ${\cal M}$, which applies ${\cal M}_{i}$ in sequential order from
$i=1$ to $i=T$, is $(f_{1}\otimes\ldots\otimes f_{T})$-DP. The tensor product
is commutative.

As a special case Corollary 3.3 in [13] states that composition of multiple
Gaussian operators $G_{\mu_{i}}$ results in $G_{\mu}$ where

$\mu=\sqrt{\sum_{i}\mu_{i}^{2}}.$

###  4.4 Tight Analysis of DP-SGD

We are now able to formulate the differential privacy guarantee of original
DP-SGD since it is a composition of subsampled Gaussian DP mechanisms. Theorem
5.1 in [13] states that DP-SGD as introduced in [1] is

$C_{m/N}(G_{\sigma^{-1}})^{\otimes T}\mbox{-DP},$

where $T=(N/m)\cdot E$ is the total number of local rounds. Since each of the
theorems and results from [13] enumerated above are exact, we have a tight
analysis. This leads in [63] to a (tight) differential privacy
accountant555The tight analysis has, cited from [13], “the disadvantage is
that the expressions it yields are more unwieldy: they are computer evaluable,
so usable in implementations, but do not admit simple closed form.” For this
reason we need an accountant method. (using complex characteristic functions
for each of the two hypotheses based on taking Fourier transforms), which can
be used by a client to keep track of its current DP guarantee and to
understand when to stop helping the server to learn a global model. Because
the accountant is tight, it improves over the momentum accountant method of
[1].

###  4.5 Strong Adversarial Model

We assume an adversary who knows the differentiating samples in $d\setminus
d^{\prime}$ and $d^{\prime}\setminus d$, but who a-priori (before mechanism
${\cal M}$ is executed) may only know (besides say a 99% characterization of
$d\cap d^{\prime}$) an estimate of the number of samples in the intersection
of $d$ and $d^{\prime}$, i.e., the adversary knows $|d\cap d^{\prime}|+noise$
where the noise is large enough to yield a ‘sufficiently strong’ DP guarantee
with respect to the size of the used data set ($d$ or $d^{\prime}$). Since
${\cal M}$ does not directly reveal the size of the used data set, we assume
(as in prior literature) that the effect of $N=|d|\neq
N^{\prime}=|d^{\prime}|$ contributes at most a very small amount of privacy
leakage, sufficiently small to be discarded in our DP analysis: That is, we
may as well assume $N=N^{\prime}$ in our DP analysis.

This means that the tight $f$-DP analysis of DP-SGD holds, even if we use the
definition of neighboring data sets stating that either $|d\setminus
d^{\prime}|=1$ or $|d^{\prime}\setminus d|=1$; the original $f$-DP analysis
considers the case $|d\setminus d^{\prime}|=|d^{\prime}\setminus d|=1$ and
this requires the factor $2C\sigma$ in Algorithm 1. If we assume no knowledge
about the exact data set sizes (as discussed above) and if we assume
probabilistic sampling (see Section 4.5), then we may only use $C\sigma$
saving a factor 2 (which helps convergence to a higher accuracy).

In the setting of $N=N^{\prime}$ the DP analysis in prior work considers an
adversary ${\cal A}dv$ who can mimic mechanism ${\cal M}\circ{\sf Sample}_{m}$
in that it can replay into large extent how ${\sf Sample}_{m}$ samples the
used data set ($d$ or $d^{\prime}$): We say a round has $k$ differentiating
data samples if ${\sf Sample}_{m}$ sampled a subset of indices which contains
exactly $k$ indices of differentiating data samples from $(d\setminus
d^{\prime})\cup(d^{\prime}\setminus d)$. The adversary knows how ${\sf
Sample}_{m}$ operates and can derive a joint probability distribution
$\mathbb{P}$ of the number of differentiating data samples for each round
within the sequence of rounds that define the series of epochs during which
updates are computed.

Adversary ${\cal A}dv$ does not know the exact instance drawn from
$\mathbb{P}$ but is, in the DP proof, given the ability to realize for each
round the trade-off function $f_{k}(\alpha)$ that corresponds to hypothesis
testing between ${\cal M}\circ{\tt Sample}_{m}(d)$ and ${\cal M}\circ{\tt
Sample}_{m}(d^{\prime})$ if ${\tt Sample}_{m}$ has selected $k$
differentiating samples in that round. In the DP analysis that characterizes
$f_{k}(\alpha)$, adversary ${\cal A}dv$ is given knowledge about the mapping
from indices to values in $d$ or $d^{\prime}$. Here (as discussed before), the
mapping from indices to values in $d\cap d^{\prime}$ is the same for the
mapping from indices to values in $d$ and the mapping from indices to values
in $d^{\prime}$. Furthermore, the adversary can replay how ${\sf Sample}_{m}$
samples a subset of $m$ indices from666By assuming $N=N^{\prime}$ in the DP
analysis, knowledge of how ${\sf Sample}_{m}$ samples a subset of indices
cannot be used to differentiate the hypotheses of $d$ versus $d^{\prime}$
based on their sizes (since the index set corresponding to $d$ is exactly the
same as the index set corresponding to $d^{\prime}$).
$\\{1,\ldots,N=N^{\prime}\\}$, and it knows all the randomness used by ${\cal
M}$ before ${\cal M}$ adds Gaussian noise for differential privacy (this
includes when and how the interrupt service routine overwrites the local
model). This strong adversary represents a worst-case scenario for the
‘defender’ when analyzing the differential privacy of a single round. For DP-
SGD this analysis for neighboring data sets leads to the argument of Section
4.2 where with probability $p$ (i.e., $k=1$) the adversary can achieve trade-
off function $f(\alpha)$ and with probability $1-p$ (i.e., $k=0$) can achieve
trade-off function $1-\alpha$ leading ultimately to operator $C_{p}$. This in
turn leads to the trade-off function $C_{m/N}(G_{\sigma^{-1}})^{\otimes T}$
with $p=m/N$, which is tight for adversary ${\cal A}dv$. Although usually not
explicitly stated, we notice that adversary ${\cal A}dv$ is used in DP
analysis of current literature including the moment accountant method of [1]
for analysing $(\epsilon,\delta)$-DP and analysis of divergence based DP
measures.

In the DP analysis adversary ${\cal A}dv$ is given knowledge about the number
$k$ of differentiating samples when analysing a single round. That is, it is
given an instance of $\mathbb{P}$ projected on a single round. We notice that
in expectation the sensitivity (see Section 4.1) of a single round as observed
by adversary ${\cal A}dv$ for neighboring data sets is equal to $(1-p)\cdot
0+p\cdot 2C=(m/N)\cdot 2C$ and this gives rise to an ‘expected’ trade-off
function $G_{1/(\sigma N/m)}$. Composition over $c^{2}(N/m)^{2}$ rounds gives
$G_{c/\sigma}$. This leads us to believe that
$C_{m/N}(G_{\sigma^{-1}})^{\otimes T}$ converges to $G_{c\cdot h(\sigma)}$ for
$T=c^{2}(N/m)^{2}\rightarrow\infty$ (or, equivalently, $\sqrt{T}\cdot m/N=c$
with $T\rightarrow\infty$ and $N\rightarrow\infty$) where $h(\sigma)$ is some
function that only depends on $\sigma$ (see below). This intuition is
confirmed by Corollary 5.4 in [13], and is also indirectly confirmed by [56]
which shows that DP-SGD is $(\epsilon,\delta)$-DP for
$\sigma=\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$ for a wide range of
parameter settings $N,m,T$ with $T$ at most $\approx\epsilon(N/m)^{2}/2$, and
which matches Corollary 5.4 in [13] in that the upper bound on $T$ can at most
be a constant factor $\approx 8$ larger (without violating the corollary).

By using $T=(N/m)\cdot E$, we have convergence to $G_{c\cdot h(\sigma)}$ for
$c=\sqrt{mE/N}$ with $E\rightarrow\infty$ and $N\rightarrow\infty$. By using a
Taylor series expansion we have

$h(\sigma)=\sqrt{2(e^{\sigma^{-2}}\Phi(\frac{3\sigma^{-1}}{2})+3\Phi(-\frac{\sigma^{-1}}{2})-2)}=\sigma^{-1}\cdot\sqrt{1-\frac{5}{8}\frac{\sigma^{-1}}{\sqrt{2\pi}}+O(\sigma^{-2})}.$

This shows that for ‘large $N$ and $E$’ DP-SGD is approximately $G_{\mu}$-DP
with $\mu=\sqrt{mE/(N\sigma^{2})}$. Notice that $\sigma$ cannot be too small
otherwise $h(\sigma)$ behaves like $e^{1/(2\sigma^{2})}$ which yields a very
weak DP guarantee.

Clearly, a weaker (than ${\cal A}dv$) adversary with less capability (less
knowledge of the used randomness by ${\sf Sample}_{m}$ and ${\cal M}$)
achieves a trade-off function $\geq C_{m/N}(G_{\sigma^{-1}})^{\otimes T}$
closer to the ideal $1-\alpha$. It remains an open problem to characterize
realistic weaker adversaries that lead to larger (lower bounds of) trade-off
functions.

###  4.6 Group Privacy

Theorem 2.14 in [13] analyzes how privacy degrades if $d$ and $d^{\prime}$ do
not differ in just one sample, but differ in $g$ samples. If a mechanism is
$f$-DP, then it is

$[1-(1-f)^{\circ g}]\mbox{-DP}$

for groups of size $g$ (where $\circ g$ denotes the $g$-fold iterative
composition of function $1-f$, where $1$ denotes the constant integer value
$1$ and not the identity function, i.e., $(1-f)(\alpha)=1-f(\alpha)$). This is
a tight statement in that there exist $f$ such that the trade-off function for
groups of size $g$ cannot be bounded better. In particular, for $f=G_{\mu}$ we
have $G_{g\mu}$-DP for groups of size $g$.

The intuition behind the $[1-(1-f)^{\circ g}]$-DP result is that the adversary
can create a sequence of data sets $d_{0}=d$, $d_{1}$, …, $d_{g-1}$,
$d_{g}=d^{\prime}$ such that each two consecutive data sets $d_{i}$ and
$d_{i+1}$ are neighboring. We know that $T({\cal M}(d_{i}),{\cal
M}(d_{i+1}))\geq f$. For each rejection rule we may plot a point (in x and y
coordinates)

$(\mathbb{E}_{o\sim{\cal M}(d_{i})}[\phi(o)],\ \mathbb{E}_{o\sim{\cal
M}(d_{i+1})}[\phi(o)]).$

Since $f(\alpha)$ is a lower bound on the Type I vs Type II error curve, the
resulting collection of points is upper bounded by the curve $1-f(\alpha)$. We
have that $\alpha=\mathbb{E}_{o\sim{\cal M}(d_{i})}[\phi(o)]$ is mapped to

$\mathbb{E}_{o\sim{\cal M}(d_{i+1})}[\phi(o)]\leq 1-f(\alpha)=(1-f)(\alpha).$

By transitivity, we have that $\alpha=\mathbb{E}_{o\sim{\cal
M}(d=d_{0})}[\phi(o)]$ is mapped to

$\mathbb{E}_{o\sim{\cal M}(d^{\prime}=d_{g})}[\phi(o)]\leq(1-f)^{\circ
g}(\alpha).$

This yields the lower bound

$T({\cal M}(d),{\cal M}(d^{\prime}))\geq 1-(1-f)^{\circ g}$

on the Type I vs Type II error curve.

Let $\phi[\alpha]$ denote a rejection rule that realizes the mapping from

$\alpha=\mathbb{E}_{o\sim{\cal M}(d_{i})}[\phi[\alpha](o)]\ \ \mbox{ to }\ \
(1-f)(\alpha)=\mathbb{E}_{o\sim{\cal M}(d_{i+1})}[\phi[\alpha](o)].$

Then the mapping from $(1-f)^{\circ i}(\alpha)=\mathbb{E}_{o\sim{\cal
M}(d_{i})}[\phi(o)]$ to $(1-f)^{\circ(i+1)}(\alpha)=\mathbb{E}_{o\sim{\cal
M}(d_{i+1})}[\phi(o)]$ is realized by $\phi=\phi[(1-f)^{\circ i}(\alpha)]$.
This shows that the lower bound $1-(1-f)^{\circ g}$ is tight only if we can
choose all $\phi[(1-f)^{\circ i}(\alpha)]$ equal to one another. In general,
this may not be the case for DP-SGD and future work may be able to produce an
improved analysis for DP-SGD.

###  4.7 DP-SGD’s Trade-Off Function

We remind the reader that we can directly infer $(\epsilon,\delta)$-DP
guarantees from (7); function $\delta(\epsilon)$ turns out to be completely
independent from the data set size $N$, hence, see Section 3.2, setting
$\delta(\epsilon)=1/N$ favorably biases smaller data sets. Appendix B in [13]
shows how to infer divergence based DP guarantees. In particular, $G_{\mu}$-DP
implies $(\omega,\frac{1}{2\mu^{2}}\cdot\omega)$-RDP (Renyi differential
privacy) for any $\omega>1$, hence, we have

$\frac{1}{2\mu^{2}}\mbox{-zCDP}.$

For group privacy with $g\geq 1$, we have $G_{\mu\cdot g}$-DP and RDP and zCDP
scale with another factor $g^{2}$.

##  5 Future Work

We are still in the midst of bringing DP-SGD to practice where we want to
achieve good convergence to and accuracy of the final global model and where
we have a strong DP guarantee (the trade-off function should be close to
$1-\alpha$ which represents random guessing between the two hypotheses).
Towards finding a good balance between utility and privacy, we discuss a
couple future directions in next subsections.

###  5.1 Using Synthetic Data

One main problem is that local data is used for training models for various
learning tasks. Each application of DP-SGD will leak privacy since the local
data set is being re-used. One way to control and be in charge of the amount
of privacy leakage is to have data samples in local client data expire
according to some expiration date (per sample). This is problematic because in
our current data economy, data is a valuable asset which we do not want to
give a limited lifetime.

In order to cope with this problem, a client may decide to not use its own
local data set in each of these DP-SGD instantiations. Instead, differential
private GAN [26] modeling can be used to learn a distribution model based on a
local data set that generates synthetic data with a similar distribution. Due
to the post-processing lemma, we can freely use the synthetic data in any
optimization algorithm and FL approach. This circumvents multiple use of DP-
SGD, but requires the design of differential private GAN which produces ‘high’
quality synthetic data. This is an open problem: GAN modeling is itself a
learning task which can use the DP-SGD approach for the discriminator (which
is very noise sensitive). Here, we use DP-SGD only once and as soon as a GAN
model is learned, it can be published and transmitted to the central server
who uses the GAN models from all clients to generate synthetic samples on
which it trains a global model for a learning task of its choice. Of course,
as a caveat, working with synthetic data may not lead to a global model with
good test accuracy on real data. Notice that by using synthetic data we avoid
the FL paradigm altogether since the large amounts of data distributed over
clients is now compressed into (relatively short transmittable)
representations that code GAN models.

In the same line of thinking, if differentially private GAN models do not lead
to high quality synthetic data, then we will want to research other general
methods for pre-processing local data that filter or hide features that are
considered privacy sensitive. This brings us back to the basics of how a
membership or inference attack is actually implemented in order to understand
what type of information should be filtered out for making reconstruction of
certain types of private data hard or unreliable.

###  5.2 Adaptive Strategies

We need to fine tune parameters and this can be done during DP-SGD’s
execution: Consecutive segments of multiple rounds may work with their own
$m$, $\sigma$, and $C$. Into what extent does an adaptive approach work, where
the current convergence rate and test accuracy (preferably based on public
data at the server so as not to leak additional privacy) of the current global
model is used to determine $(m,\sigma,C)$ for the next segment?

In Section 2.6 we discussed the benefit of adaptive reducing the clipping
constant $C$ (based on prior rounds or based on using a DP approach within a
round to collect information that influences the choice of the used $C$ in
that round). Similarly, since a smaller $\sigma$ directly reduces the amount
of noise added to the global model and therefore increase the final accuracy,
it makes sense to reduce $\sigma$ once convergence has been achieved. After
reducing $\sigma$, new convergence to an improved global model may start. The
problem is that a lower $\sigma$ leads to more privacy leakage. For this
reason we want to lower $\sigma$ to a smaller $\hat{\sigma}$ only for e.g. the
final epoch.

We may also modify the noise distribution: DP-SGD selects noise $N$ from a
Gaussian distribution. before adding $N$ to the round update, we may replace
$N$ by $a\cdot{\tt arsinh}(a^{-1}\cdot N)$ where ${\tt
arsinh}(x)=\ln(x+\sqrt{x^{2}+1})$ as suggested for tCDP [6]. The result
resembles the same Gaussian but with exponentially faster tail decay and this
may help improving the convergence to and accuracy of the final global model.
Here, we notice that for the same reason of faster tail decay, DP-SGD chooses
to use Gaussian noise over Laplace noise.

Finally, DP-SGD can be placed in a larger algorithmic framework with DP
guarantees for a more general clipping strategy (including clipping a batch of
gradients) which allows more general optimization algorithms (beyond mini-
batch SGD), and more general sampling strategies (in particular a sampling
strategy based on ‘shuffling’).

It remains an open problem to unveil adaptive strategies possibly in a more
general algorithmic framework that optimally balance utility and differential
privacy. Here we prefer to discover adaptive strategies that proactively
provide the DP guarantee based on changed parameter settings, i.e., we do not
want to change parameters based solely on utility and discover later (by using
a differential privacy accountant) that this has violated or is about to
violate our privacy budget.

###  5.3 DP Proof: A Weaker Adversarial Model

Section 4.5 explains the strong adversarial model used in DP analysis under
which the derived DP guarantee is tight. In practice, this is too strong. In
general, we may assume a weaker adversary with less capability in terms of
knowledge about the used randomness by ${\tt Sample}_{m}$ and ${\cal M}$. By
explicitly stating the knowledge of a weaker adversary in combination with
assumptions on the data set itself, we may be able to derive an $f$-DP
guarantee with $f(\alpha)$ closer to $1-\alpha$. It remains an open problem to
exploit such a line of thinking.

###  5.4 Computing Environment with Less Adversarial Capabilities

In order to impose restrictions on adversarial capabilities we may be able to
use confidential computing techniques such as secure processor technology
[11], homomorphic computing with secret sharing and/or secure Multi-Party
Computation (MPC) [32], and possibly even hardware accelerated fully
homomorphic encryption [24, 22]; for a survey see [31, 35]. These techniques
hide round updates in encrypted form. Hence, only the final global model
itself (if it is published) or querying the final global model (if it is kept
private) can leak information about how local data sets shaped the final
model. This means that CDP, see Section 3, is still needed. CDP has a better
trade-off between privacy and utility compared to LDP as discussed in this
chapter. However, confidential computing does not come for free: Either we
need to assume a larger Trusted Computing Base (TCB) in the form of trusted
hardware modules or processors at the clients, intermediate aggregators, and
server or we need a Trusted Third Party (TTP). E.g., in the secure MPC
solution of [32] the generation of Beaver triples is outsourced to a TTP
otherwise impractical additional communication among clients and server is
needed (for an oblivious transfer phase in MPC). We are still studying
balanced and practical combinations of confidential computing techniques
including the use of differential privacy.

## References

  * Abadi et al. [2016] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , pages 308–318. ACM, 2016.
  * Bhowmick et al. [2019] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers.  Protection against reconstruction and its applications in private federated learning, 2019.
  * Bonawitz et al. [2019] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, et al.  Towards federated learning at scale: System design.  _arXiv preprint arXiv:1902.01046_ , 2019.
  * Bun and Steinke [2016a] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  _arXiv_ , 2016a.
  * Bun and Steinke [2016b] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In Martin Hirt and Adam D. Smith, editors, _TCC_ , volume 9985, pages 635–658, 2016b.
  * Bun et al. [2018] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke.  Composable and versatile privacy via truncated CDP.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, _STOC_. ACM, 2018.
  * Chaudhuri et al. [2013] Kamalika Chaudhuri, Anand D Sarwate, and Kaushik Sinha.  A near-optimal algorithm for differentially-private principal components.  _Journal of Machine Learning Research_ , 14, 2013.
  * Chen et al. [2016] Jianmin Chen, Rajat Monga, Samy Bengio, and Rafal Jozefowicz.  Revisiting distributed synchronous sgd.  _ICLR Workshop Track_ , 2016.
  * Chen et al. [2019a] Yang Chen, Xiaoyan Sun, and Yaochu Jin.  Communication-efficient federated deep learning with asynchronous model update and temporally weighted aggregation.  _arXiv preprint_ , 2019a.  URL https://arxiv.org/pdf/1903.07424.pdf.
  * Chen et al. [2019b] Yang Chen, Xiaoyan Sun, and Yaochu Jin.  Communication-efficient federated deep learning with asynchronous model update and temporally weighted aggregation.  _arXiv preprint_ , 2019b.  URL https://arxiv.org/pdf/1903.07424.pdf.
  * Costan and Devadas [2016] Victor Costan and Srinivas Devadas.  Intel SGX explained.  _IACR Cryptol. ePrint Arch._ , page 86, 2016.
  * De Sa et al. [2015] Christopher M De Sa, Ce Zhang, Kunle Olukotun, and Christopher Ré.  Taming the wild: A unified analysis of hogwild-style algorithms.  In _NIPS_ , pages 2674–2682, 2015.
  * Dong et al. [2021] Jinshuo Dong, Aaron Roth, and Weijie Su.  Gaussian differential privacy.  _Journal of the Royal Statistical Society_ , 2021.
  * Duchi et al. [2014] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright.  Local privacy, data processing inequalities, and statistical minimax rates, 2014.
  * Dwork [2011] Cynthia Dwork.  A firm foundation for private data analysis.  _Communications of the ACM_ , 54(1):86–95, 2011\.
  * Dwork and Roth [2014] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Dwork and Rothblum [2016] Cynthia Dwork and Guy N Rothblum.  Concentrated differential privacy.  _arXiv preprint arXiv:1603.01887_ , 2016.
  * Dwork et al. [2006a] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 486–503. Springer, 2006a.
  * Dwork et al. [2006b] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006b.
  * Dwork et al. [2010] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan.  Boosting and differential privacy.  In _51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA_ , pages 51–60. IEEE Computer Society, 2010.
  * Dwork et al. [2014] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Feldmann et al. [2021] Axel Feldmann, Nikola Samardzic, Aleksandar Krastev, Srini Devadas, Ron Dreslinski, Karim Eldefrawy, Nicholas Genise, Chris Peikert, and Daniel Sanchez.  F1: A fast and programmable accelerator for fully homomorphic encryption (extended version).  _arXiv preprint arXiv:2109.05371_ , 2021.
  * Geiping et al. [2020] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller.  Inverting gradients – how easy is it to break privacy in federated learning?  In _NIPS_ , 2020.
  * Gentry [2009] Craig Gentry.  Fully homomorphic encryption using ideal lattices.  In _STOC_ , 2009.
  * Geyer et al. [2018] Robin C. Geyer, Tassilo Klein, and Moin Nabi.  Differentially private federated learning: A client level perspective, 2018.
  * Goodfellow et al. [2020] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  _Communications of the ACM_ , 63(11):139–144, 2020.
  * Gupta et al. [2009] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar.  Differentially private approximation algorithms.  _CoRR_ , abs/0903.4510, 2009.
  * Hao et al. [2020] Meng Hao, Hongwei Li, Xizhao Luo, Guowen Xu, Haomiao Yang, and Sen Liu.  Efficient and privacy-enhanced federated learning for industrial artificial intelligence.  _IEEE Transactions on Industrial Informatics_ , 16(10):6532–6542, 2020.  doi: 10.1109/TII.2019.2945367.
  * Hsieh et al. [2017] Kevin Hsieh, Aaron Harlap, Nandita Vijaykumar, Dimitris Konomis, Gregory R. Ganger, Phillip B. Gibbons, and Onur Mutlu.  Gaia: Geo-distributed machine learning approaching LAN speeds.  _14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17)._ , 2017.
  * Jie Xu [2020] Fei Wang Jie Xu, Wei Zhang.  Asynchronous decentralized parallel stochastic gradient descent with differential privacy.  _arXiv_ , 2020.
  * Kairouz et al. [2021] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Knott et al. [2021] Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten.  Crypten: Secure multi-party computation meets machine learning.  _Advances in Neural Information Processing Systems_ , 34:4961–4973, 2021.
  * Konečnỳ et al. [2016] Jakub Konečnỳ, H Brendan McMahan, Daniel Ramage, and Peter Richtárik.  Federated optimization: Distributed machine learning for on-device intelligence.  _arXiv preprint arXiv:1610.02527_ , 2016.
  * Li et al. [2019] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.  Federated optimization for heterogeneous networks.  _arXiv preprint_ , 2019.  URL https://arxiv.org/pdf/1812.06127.pdf.
  * Li et al. [2020] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 37(3):50–60, 2020.
  * Lian et al. [2015] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu.  Asynchronous parallel stochastic gradient for nonconvex optimization.  In _Advances in Neural Information Processing Systems_ , pages 2737–2745, 2015.
  * Lian et al. [2017] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu.  Asynchronous decentralized parallel stochastic gradient descent.  _arXiv preprint arXiv:1710.06952_ , 2017.
  * Lyu et al. [2020] Lingjuan Lyu, Han Yu, and Qiang Yang.  Threats to federated learning: A survey, 2020.
  * Mania et al. [2015] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan.  Perturbed Iterate Analysis for Asynchronous Stochastic Optimization.  _SIAM Journal on Optimization_ , pages 2202–2229, 2015.
  * McMahan and Ramage [2017] Brendan McMahan and Daniel Ramage.  Federated learning: Collaborative machine learning without centralized training data, 2017.  URL https://ai.googleblog.com/2017/04/federated-learning-collaborative.html.  Last accessed 09/24/2019.
  * McMahan et al. [2018] Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang.  Learning differentially private recurrent language models.  In _International Conference on Learning Representations (ICLR)_ , 2018.  URL https://openreview.net/pdf?id=BJ0hF1Z0b.
  * McMahan et al. [2016] H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas.  Federated learning of deep networks using model averaging.  _ICLR Workshop Track_ , 2016.
  * Mironov [2017] Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th computer security foundations symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Naseri et al. [2021] Mohammad Naseri, Jamie Hayes, and Emiliano De Cristofaro.  Toward robustness and privacy in federated learning: Experimenting with local and central differential privacy, 2021.
  * Nasr et al. [2019] M. Nasr, R. Shokri, and A. 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.  doi: 10.1109/SP.2019.00065.
  * Nguyen et al. [2018] Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác.  Sgd and hogwild! convergence without the bounded gradients assumption.  In _International Conference on Machine Learning_ , pages 3750–3758. PMLR, 2018.
  * Nguyen et al. [2019] Lam M. Nguyen, Phuong Ha Nguyen, Peter Richtárik, Katya Scheinberg, Martin Takáč, and Marten van Dijk.  New convergence aspects of stochastic gradient algorithms.  _Journal of Machine Learning Research_ , 20(176):1–49, 2019.
  * [48] Opacus.  Opacus pytorch library.  Available from opacus.ai.
  * Papernot et al. [2018] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson.  Scalable private learning with pate.  In _International conference on learning representations_ , 2018.
  * Robbins and Monro [1951] Herbert Robbins and Sutton Monro.  A stochastic approximation method.  _The Annals of Mathematical Statistics_ , 22(3):400–407, 1951.
  * Shokri et al. [2017] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pages 3–18. IEEE, 2017.
  * Song et al. [2019] L. Song, R. Shokri, and P. Mittal.  Membership inference attacks against adversarially robust deep learning models.  In _2019 IEEE Security and Privacy Workshops (SPW)_ , pages 50–56, 2019.  doi: 10.1109/SPW.2019.00021.
  * Starovoitov and Golub [2021] Valery V. Starovoitov and Yu. I. Golub.  Data normalization in machine learning.  _Informatics_ , 2021.
  * Truex et al. [2019] Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou.  A hybrid approach to privacy-preserving federated learning.  In _Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security_ , pages 1–11, 2019.
  * van Dijk et al. [2020] Marten van Dijk, Nhuong V Nguyen, Toan N Nguyen, Lam M Nguyen, Quoc Tran-Dinh, and Phuong Ha Nguyen.  Hogwild! over distributed local data sets with linearly increasing mini-batch sizes.  _arXiv preprint arXiv:2010.14763_ , 2020.
  * van Dijk et al. [2021] Marten van Dijk, Nhuong V. Nguyen, Toan N. Nguyen, Lam M. Nguyen, and Phuong Ha Nguyen.  Differential private hogwild! over distributed local data sets.  _CoRR_ , abs/2102.09030, 2021.
  * Wang et al. [2019] Luping Wang, Wei Wang, and Bo Li.  Cmfl: Mitigating communication overhead for federated learning.  _IEEE International Conference on Distributed Computing Systems._ , 2019.
  * Wasserman and Zhou [2010] Larry Wasserman and Shuheng Zhou.  A statistical framework for differential privacy.  _Journal of the American Statistical Association_ , 105(489):375–389, 2010.
  * Xie et al. [2019] Cong Xie, Sanmi Koyejo, and Indranil Gupta.  Asynchronous federated optimization.  _arXiv preprint_ , 2019.  URL https://arxiv.org/pdf/1903.03934v1.pdf.
  * Yu et al. [2019] Lei Yu, Ling Liu, Calton Pu, Mehmet Emre Gursoy, and Stacey Truex.  Differentially private model publishing for deep learning.  _2019 IEEE Symposium on Security and Privacy (SP)_ , May 2019.  doi: 10.1109/sp.2019.00019.  URL http://dx.doi.org/10.1109/SP.2019.00019.
  * Zhao et al. [2020] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen.  idlg: Improved deep leakage from gradients, 2020.
  * Zhu et al. [2019] Ligeng Zhu, Zhijian Liu, and Song Han.  Deep leakage from gradients.  _Neurips_ , 2019.
  * Zhu et al. [2021] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang.  Optimal accounting of differential privacy via characteristic function.  _arXiv preprint arXiv:2106.08567_ , 2021.