# Bringing Differential Private SGD to Practice: On the Independence of
Gaussian Noise and the Number of Training Rounds

Marten van Dijk1,2∗, Nhuong V. Nguyen3†∗, Toan N. Nguyen3†,
Lam M. Nguyen4, Phuong Ha Nguyen5
1 CWI Amsterdam, The Netherlands
2 Department of Electrical and Computer Engineering, University of
Connecticut, CT, USA
3 Department of Computer Science and Engineering, University of Connecticut,
CT, USA
4 IBM Research, Thomas J. Watson Research Center, Yorktown Heights, NY, USA
5 eBay, CA, USA

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

In DP-SGD each round communicates a local SGD update which leaks some new
information about the underlying local data set to the outside world. In order
to provide privacy, Gaussian noise with standard deviation $\sigma$ is added
to local SGD updates after performing a clipping operation. We show that for
attaining $(\epsilon,\delta)$-differential privacy $\sigma$ can be chosen
equal to $\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$ for
$\epsilon=\Omega(T/N^{2})$, where $T$ is the total number of rounds and $N$ is
equal to the size of the local data set. In many existing machine learning
problems, $N$ is always large and $T=O(N)$. Hence, $\sigma$ becomes
“independent” of any $T=O(N)$ choice with $\epsilon=\Omega(1/N)$. This means
that our $\sigma$ only depends on $N$ rather than $T$. As shown in our paper,
this differential privacy characterization allows one to a-priori select
parameters of DP-SGD based on a fixed privacy budget (in terms of $\epsilon$
and $\delta$) in such a way to optimize the anticipated utility (test
accuracy) the most. This ability of planning ahead together with $\sigma$’s
independence of $T$ (which allows local gradient computations to be split
among as many rounds as needed, even for large $T$ as usually happens in
practice) leads to a proactive DP-SGD algorithm that allows a client to
balance its privacy budget with the accuracy of the learned global model based
on local test data. We notice that the current state-of-the art differential
privacy accountant method based on $f$-DP has a closed form for computing the
privacy loss for DP-SGD. However, due to its interpretation complexity, it
cannot be used in a simple way to plan ahead. Instead, accountant methods are
only used for keeping track of how privacy budget has been spent (after the
fact).

00footnotetext: ∗ these authors contributed equally.00footnotetext: †
supported by NSF grant CNS-1413996 “MACS: A Modular Approach to Cloud
Security.”

##  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 [20]. 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)
with Differential Privacy (DP). Here, differential privacy comes from adding
Gaussian noise to local (client-computed) mini-batch SGD updates (called Local
DP) and this wrings with being able to learn an accurate global model; more
Gaussian noise leads to better differential privacy guarantees, but hurts
accuracy. Since the most important mission in machine learning is achieving a
good accuracy, the added Gausian noise cannot be too large and is constrained.
There are two main problems:

$\bullet$ Each client wants to be able to plan ahead meaning that one can
a-priori optimize hyper parameters given a target accuracy (utility) and
target differential privacy budget.

$\bullet$ Each local SGD update with Gaussian DP noise communicated to the
central server leaks privacy about a client’s local data set. If this leakage,
for example, composes linearly over communication rounds, then only a small
number of communication rounds is possible in order to satisfy a target
differential privacy budget. However, smaller number of communication rounds
implies slower convergence to a reduced accuracy and one’s target accuracy may
not be attained. In order to achieve a good accuracy the number of
communication rounds is generally large.

In this paper we introduce theory that allows ahead planning and shows that
the number of rounds can actually be quite large; we address the two main open
problems as described above at the same time.

The current state-of-the-art differential privacy accountant method by [36]
based on the Gaussian differential privacy framework of [5] allows a client to
keep track of how much “differential privacy” has been spent up to the current
round. The client knows when to stop computing and stop sending local SGD
updates to the central server as soon as its “privacy budget” has been
depleted. The accountant method gives a precise characterization of the spent
privacy budget.

However, the accountant method cannot be used to a-priori select parameters
and anticipate whether sufficient accuracy can be achieved within the privacy
budget available for the client. We note that the accountant method and the
precise Gaussian differential privacy theory does give an expression of the
differential privacy guarantee as a function/expression of parameters
representing the local data set size $N$, representing the mini-batch or
sample size $s$ during local SGD iterations, the total number of rounds $T$,
and the added Gaussian noise per communicated SGD update represented by a
standard deviation $\sigma$. Problematic is that this expression is in a sense
unwieldy in that it does not admit simple closed form. A simple closed form
(or a sufficiently tight simple closed form approximation) is needed for
optimizing (with respect to accuracy) the parameters $\sigma$, $s$, and $T$,
given $N$ and given a target differential privacy budget. Our aim is to
a-priori select parameters in order to achieve the best accuracy of the final
global model given the allocated privacy budget.

$\bullet$ We non-trivially improve the analysis of the moment accountant
method in [1] and show for the first time that
$(\epsilon,\delta)$-differential privacy can be achieved for

$\sigma=\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$

in practical parameter settings with (a) a reasonable DP guarantee by choosing
$\delta\leq 1/N$ and $\epsilon$ smaller than $0.5$, where (b) the total number
$K$ of gradient computations over all local rounds performed on the local data
set is at least a constant ($\approx e/2$) times
$\sqrt{\epsilon\ln(1/\delta)}$ epochs (of size $N$), and (c) $T$ is at least
another constant ($\approx 2$) times $(K/N)^{2}/\epsilon$. Condition (c) turns
out to be the limiting constraint, but only shows a lower bound on $T$
suggesting that $T$ can be freely chosen as large as $K$. Analysis of this
constraint shows that, for $\epsilon=\Omega(1/N)$, $\sigma$ is “independent”
of any $T=O(N)$ (see abstract).

$\bullet$ Simulations show a significantly smaller $\epsilon$ compared to
current state of the art. For example, our theory applies to $\epsilon=0.15$
for the non-convex problem of the simple neural network LeNet [17] with cross
entropy loss function for image classification of MNIST [16] at a test
accuracy of 93%, compared to 98% without differential privacy. Notice that [1]
reports for a 60-dimensional PCA projection layer with a single 1,000-unit
ReLU hidden layer for MNIST 90% test accuracy for $\epsilon=0.5$ and 95% test
accuracy for $\epsilon=2$, both for $\delta=10^{-5}=0.6/N$.

$\bullet$ We discuss and detail in Supplemental Material a proactive DP-SGD
framework where the client adapts the added Gaussian noise according to
measured test accuracy in order to achieve the target accuracy while at the
same time being in control not to cross its differential privacy budget. This
provides a blueprint for the engineer who, without a-priori knowledge, wants
to use our adaptive hyper-parameter selection for DP-SGD. Here we use a
varying sample (mini-batch) sequence in DP-SGD (this is covered by our
theory). Also, the framework (and theory) applies to the asynchronous SGD
framework.

Outline: In order to set up the proper background in Section 2, we first
define $(\epsilon,\delta)$-differential privacy in Section 2.1, next discuss
DP-SGD as introduced by [1] in Section 2.2, and finally explain how $f$-DP and
Gaussian DP relates to the results in this paper in Section 2.3. In Section 3
we explain our main theory with in Section 3.1 its usage in realizing planning
ahead with proactive DP-SGD and in Section 3.2 the interpretation of the lower
bound on $T$, where we discuss the independence of $\sigma$ and $T$ (that is,
we explain there is no practical prohibitive limit to the total number of
local training rounds in DP-SGD and that this can be chosen independent of the
required differential privacy with corresponding Gaussian noise according to
our formula). Experiments are in Section 4. The asynchronous SGD framework,
detailed differential privacy proofs and analysis, and additional experiments
with extra details are in Supplemental Material.

##  2 Differential Private SGD (DP-SGD)

###  2.1 Differential Privacy

Differential privacy [9, 7, 10, 8] 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).

######  Definition 1.

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

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

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

When using differential privacy in machine learning we typically use
$\delta=1/N$ (or $1/(10N)$) inversely proportional with the data set size $N$.

In order to prevent data leakage from inference attacks in machine learning
[18] such as the deep leakage from gradients attack [35, 34, 11] or the
membership inference attack [28, 22, 29] a range of privacy-preserving methods
have been proposed. Privacy-preserving solutions for federated learning are
Local Differential Privacy (LDP) solutions [1, 2, 21, 30, 13, 6] and Central
Differential Privacy (CDP) solutions [21, 12, 19, 25, 32]. 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 paper we also
consider LDP. In CDP, a trusted server 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.

###  2.2 DP-SGD

We analyse the Gaussian based differential privacy method, called DP-SGD, of
[1], depicted in Algorithm 1 in a distributed setting (see Appendix A). Rather
than using the gradient $\nabla f(\hat{w},\xi)$ itself, DP-SGD uses its
clipped version $[\nabla f(\hat{w},\xi)]_{C}$ where
$[x]_{C}=x/\max\\{1,\|x\|/C\\}$. 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 [23]), yet the added gradients
need to be bounded by some constant $C$ in order for the DP analysis of [1] to
go through.

Algorithm 1 DP-SGD: Local Model Updates with Differential Privacy

1:procedure LocalSGDwithDP($d$)

2: for $i\in\\{0,\ldots,T-1\\}$ do

3: Receive the current global model $\hat{w}$ from Server.

4: Uniformly sample a random set $\\{\xi_{h}\\}_{h=1}^{s_{i}}\subseteq d$

5: $h=0$, $U=0$

6: while $h<s_{i}$ do

7: $g=[\nabla f(\hat{w},\xi_{h})]_{C}$

8: ${U}={U}+g$

9: $h$++

10: end while

11: $n\leftarrow{\cal N}(0,C^{2}\sigma^{2}\textbf{I})$

12: $U=U+n$

13: Send $(i,U)$ to the Server.

14: end for

15:end procedure

DP-SGD uses a mini-batch approach where before the start of the $i$-th local
round a random min-batch of sample size $s_{i}$ is selected out of a local
data set $d$ of size $|d|=N$. Here, we slighty generalize DP-SGD’s original
formulation which uses a constant $s_{i}=s$ sample size sequence, while our
analysis will hold for a larger class of sample size sequences. The inner loop
maintains the sum $U$ of gradient updates where each of the gradients
correspond to the same local model $\hat{w}$ until it is replaced by a newer
global model at the start of the outer loop. At the end of each local round
the sum of updates $U$ is obfuscated with Gaussian noise ${\cal
N}(0,C^{2}\sigma^{2})$ added to each vector entry, and the result is
transmitted to the server. The server adds $U$ times the round step size
$\bar{\eta}_{i}$ to its global model $\hat{w}$. As soon as all clients have
submitted their updates, the resulting new global model $\hat{w}$ is broadcast
to all clients, who in turn replace their local models with the newly received
global model.

###  2.3 Tight Analysis using Gaussian DP

Appendix C summarizes the recent work by [5] that introduces the $f$-DP
framework based on hypothesis testing. $f$-DP has $(\epsilon,\delta)$-DP as a
special case in that a mechanism is $(\epsilon,\delta)$-DP if and only if it
is $f_{\epsilon,\delta}$-DP with
$f_{\epsilon,\delta}(\alpha)=\min\\{0,1-\delta
e^{\epsilon}\alpha,(1-\delta-\alpha)e^{-\epsilon}\\}$. They prove that DP-SGD
is $C_{s/N}(G_{(\sigma/2)^{-1}})^{\otimes T}$-DP where $C_{s/N}$ is an
operator representing the effect of subsampling, $G_{(\sigma/2)^{-1}}$ is a
Gaussian function characterizing the differential privacy (called Gaussian DP)
due to adding Gaussian noise, and operator $\otimes T$ describes composition
over $T$ rounds. $C_{s/N}(G_{(\sigma/2)^{-1}})^{\otimes T}$-DP can be
translated in a tight $(\epsilon,\delta)$-DP formulation.

This leads in [36] to a differential privacy accountant (using a complex
characteristic function based on taking the Fourier transform) for a client to
understand when to stop helping the server to learn a global model. The goal
of this paper is to a-priori understand how to, given a privacy budget and
given a utility that we wish to achieve, optimize parameters $\sigma$, $s$ and
$T$ for best utility and minimal privacy leakage given a data set of size $N$.
As a method for keeping track (account for) spent privacy budget, differential
privacy accountant does not give us this insight.

Towards understanding how to a-priori set parameters for best utility and
minimal privacy leakage, the tight $f$-DP formulation for DP-SGD can be
translated into sharp privacy guarantees. However, cited from [5], “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." And it is a simple closed form or simple approximation of a
closed form that is needed for an a-priori direct interpretation of how the
different parameters $\sigma$, $s$ and $T$ impact the privacy budget.

The question remains of how to a-priori select concrete parameters $\sigma$,
$s$, and $T$ given concrete parameters for $N$, a given privacy budget and
utility that we wish to achieve. In this paper we decided to generalize the
proof method of [1] rather than working with the complex integrals that
provide the exact characterization of $f$-DP for the DP-SGD algorithm. This
approach, as we will demonstrate, allows us to derive a concrete (non-
asymptotic) simple form which turns out to show into large extent the
independence of the privacy budget on $T$, which is not immediately understood
from [1], see Theorem 2 in Supplemental Material, and the $f$-DP framework
discussed above. The advantage of our result is that it is easy to interpret;
clients do not need to fully rely on an accountant method to keep track of
spent privacy budget, they can use our theory to a-priori set parameters such
that privacy budget will be well-spent. (In addition, our theory holds for
variable sized sample sequences, which is needed in our proactive DP-SGD, see
Appendix E for details.)

##  3 Main Thm: Independence between $\sigma$ and $T$

On the dependence of $\sigma$ on $T$: As discussed in [1], in order to control
privacy leakage over an increasing number of training rounds, we need to
increase the magnitude, or standard deviation $\sigma$, of the added noise per
round. Increasing $\sigma$ makes each round leakage smaller and as a result
the aggregated leakage becomes less. For a fixed privacy leakage budget this
allows us to add more entries, in other words, we may increase $T$. The
maximum possible $T$ increases as $\sigma$ increases.

This dependence of the amount of Gaussian noise $\sigma$ on the number of
training rounds $T$ may impose an impractical upper bound on $T$: First,
$\sigma$ cannot be too large. The global model suffers from aggregated noise
from each local update. In particular, the global model includes $\sigma$
noise from the final training round. If $\sigma$ is too large, then this leads
to a low accuracy global model. Second, if $\sigma$ cannot be too large, then
the number of training rounds $T$ cannot be too large because otherwise
privacy leakage aggregates too much over all training rounds. But this implies
that the global model may receive too few local SGD updates; local SGD updates
from different clients are communicated through the global model to one
another using too few interactions/rounds (frequent exchange is especially
important when local data sets are heterogeneous, hence, different clients
produce distinctive updates that are specific to their local data sets). This
leads again to a low accuracy global model. This intuition/reasoning indicates
that Differential Private SGD (DP-SGD) can only be practical for subtle
parameter settings and data sets that allow ‘fast enough’ training/convergence
to a good accuracy global model. In general, DP-SGD is expected to be much
less competitive compared to using other existing privacy techniques (such as
secure multiparty computation even though this is less efficient and/or
trusted execution environments which impose believe in a larger trusted
computing base).

Main contribution: We show that DP-SGD is actually competitive by non-
trivially improving the analysis of the moment accountant method in [1]. We
state our main theorem below. It shows that $(\epsilon,\delta)$-differential
privacy can be achieved for $\sigma=\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$
in practical parameter settings with (a) a reasonable DP guarantee by choosing
$\delta\leq 1/N$ and $\epsilon$ smaller than $0.5$, where (b) the total number
$K$ of gradient computations over all local rounds performed on the local data
set is at least a small constant times $\sqrt{\epsilon\ln(1/\delta)}$ epochs
(of size $N$), and (c) $T$ is at least another small constant times
$(K/N)^{2}/\epsilon$.

######  Theorem 1.

Let $\sigma$ and $(\epsilon,\delta)$ satisfy the relation

$\sigma=\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}\mbox{ with }\delta\leq
1/N\mbox{ and }\epsilon<0.5.$ (1)

For sample size sequence $\\{s_{i}\\}_{i=0}^{T-1}$ the total number of local
SGD iterations is equal to $K=\sum_{i=0}^{T-1}s_{i}$. We define $k=K/N$ as the
total number of local SGD iterations measured in epochs (of size $N$). Related
to the sample size sequence we define the mean $\bar{s}$ and maximum $s_{max}$
and their quotient $\theta$ as

$\displaystyle\bar{s}=\frac{1}{T}\sum_{i=0}^{T-1}s_{i}=\frac{K}{T},\ \
s_{max}=\max\\{s_{i}\\}\mbox{ and }\ \ \theta=\frac{s_{max}}{\bar{s}}.$

Let $\gamma$ be the smallest solution satisfying

$\displaystyle\gamma$ $\displaystyle\geq$
$\displaystyle\frac{2^{4}\cdot\bar{\alpha}}{1-\bar{\alpha}}\left(\frac{\sigma}{(1-\sqrt{\bar{\alpha}})^{2}}+\frac{1}{\sigma(1-\bar{\alpha})-2e\sqrt{\bar{\alpha}}}\frac{e^{3}}{\sigma}\right)e^{3/\sigma^{2}}$
$\displaystyle+\frac{2}{1-\bar{\alpha}}\ \ \ \ \ \mbox{ with
}\bar{\alpha}=\frac{\epsilon}{\gamma k}.$

Parameter $\gamma=2+O(\bar{\alpha})$, which is close to $2$ for small
$\bar{\alpha}$. We assume data sets of size $N\geq 10000$ and sample size
sequences with $\theta\leq 6.85$. If

$\displaystyle k$ $\displaystyle\geq$
$\displaystyle\sqrt{2\epsilon\ln(1/\delta)}\cdot e/(\gamma\theta)\mbox{ and }$
(2) $\displaystyle T$ $\displaystyle\geq$
$\displaystyle\frac{\gamma\theta^{2}}{\epsilon}\cdot k^{2},$ (3)

then Algorithm 1 is $(\epsilon,\delta)$-differentially private.

All our theory, including the above theorem, holds in the asynchronous SGD
framework of Appendix A. In Appendix A we provide a more general asynchronous
mini-batch SGD algorithm (which follows Hogwild!’s philosophy [26, 4, 33, 23,
15, 24]) with DP. The asynchronous setting allows clients to adapt their
sample sizes to their processing speed and communication latency.

We notice that polynomial increasing sample size sequences $s_{i}\sim qNi^{p}$
have $\bar{s}\approx[qNT^{p+1}/(p+1)]/T$ and $s_{max}=qNT^{p}$, hence,
$\theta=1+p$. This shows that our theory covers e.g. linear increasing sample
size sequences as discussed in [24], where is explained how this implies
reduced round communication – another metric which one may trade-off against
accuracy and total local number $K$ of gradient computations.

The proof of the above theorem is in Appendix B and follows a sequence of
steps: We discuss the analysis of [1] and explain where we will improve. This
leads to an improved analysis with a first generally applicable Theorem 3. As
a consequence we derive a simplified characterization in the form of Theorem
4. Finally, we introduce more coarse bounds in order to extract the more
readable Theorem 1. We notice that the simulations in Section 4 are based on
parameters that satisfy constraints (28, 29, 30, 58) of Theorem 4 as this
leads to slightly better results.

One order of magnitude smaller $\epsilon$: In order to attain an accuracy
comparable to the non-DP setting where no noise is added, the papers cited in
Section 2.1 generally require large $\epsilon$ (such that $\sigma$ can be
small enough) – which gives a weak privacy posture (a weak bound on the
privacy loss). For example, when considering LDP (see Section 2.1), $10\%$
deduction in accuracy yields only $\epsilon=50$ in [2] and $\epsilon=10.7$ in
[21], while [30, 13] show solutions for $\epsilon=0.5$.

The theory presented in this paper allows relatively small Gaussian noise for
small $\epsilon$: We only need to satisfy the main equation (58). For example,
in Section 4 simulations for the LIBSVM data set show
$(\epsilon=0.05,\delta=1/N)$-DP is possible while achieving good accuracy with
$\sigma\approx 20$. Such small $\epsilon$ is a significant improvement over
existing literature and gives us significant more trust in that DP offers
appropriate privacy.

Interpretation of Theorem 1: In Section 3.1 we discuss how we use Theorem 1
and implement planning ahead, that is, a-priori selection of hyper parameters
given a target accuracy and target differential privacy budget. We discuss how
this leads to proactive DP-SGD. In Section 3.2 we interpret and discuss
constraint (3) in detail; here, we explain that $\sigma$ depends on $N$ rather
than $T$. The other requirements need much less discussion: A practical usable
differential privacy budget has $\delta\leq 1/N$ and $\epsilon\leq 0.5$. And
lower bound (2) on $K$ is generally satisfied in practice as usually $K$ is 50
or 100s of epochs.

###  3.1 Planning Ahead

Expression (1) allows us to plan ahead. To see this, we first discuss the
concept of a utility graph where a ‘best-case’ accuracy is depicted as a
function of noise $\sigma$ and clipping constant $C$ in DP-SGD (see Section
4). In DP-SGD the last round of local updates is aggregated into an update of
the global model, after which the global model is finalized. This means that
the Gaussian noise added to a client local update of its last round is
directly added as a perturbation to the final global model. We have a best-
case scenario if we neglect the added noise of all previous rounds. That is,
the ‘best-case’ accuracy for DP-SGD is the accuracy of a global model which is
trained using SGD without DP after which Gaussian noise is added. The utility
graph depicts this ‘best-case’ accuracy.

To generate the graph, we fix a diminishing learning rate $\eta_{t}$ (step
size) from round to round and we fix the total number $K$ of local gradient
computations that will be performed. Based on local training data and a-priori
knowledge, a local client can run SGD locally without any added DP mechanism.
This learns a local model $w^{*}$ and we compare how much accuracy is
sacrificed by adding Gaussian noise $n\sim{\cal N}(0,C^{2}\sigma^{2}{\bf I})$;
that is, we compute and depict the ratio $F(w^{*}+n)/F(w^{*})$. This teaches
us the range of $\sigma$ and $C$ combinations that may lead to sufficient
accuracy (say at most a 10% drop).

We notice that the server may start DP-SGD based on an architecture and model
for another related problem that is already known. This model is used as a
starting point to train the new model for the new problem (transfer learning).
The utility graph of the model for the other related problem can be computed
or is already known and a range of acceptable $\sigma$ and $C$ combinations
can be given to the clients by the server at the start of their DP-SGD. Here,
we assume that the utility graph of the other related problem transfers to the
new problem.

We note that the Gaussian noise scales with the product $C\sigma$ and this
suggests that lowering $C$ allows larger $\sigma$, which leads to a better
differential privacy guarantee according to (1). However, we cannot lower the
clipping constant $C$ arbitrarily: Clipping the gradient implies rescaling its
norm to a lower value and intuitively this can be seen as having a similar
effect when a (factor $C$) lower learning rate (step size) $\eta_{t}$ is used
during SGD updates. In our experiments we implement a diminishing step size
sequence, however, in order to obtain practical convergence we need an initial
step size which is ‘large enough’. Hence, we cannot start local SGD updates
using a ‘very small’ clipping constant $C$. This observation does suggest that
keeping the step size more constant (and not diminishing) over rounds together
with a diminishing clipping constant may allow good convergence leading to
sufficient accuracy/utility. This means that $\sigma$ can increase from round
to round, which implies that the privacy budget is being depleted at a lower
decreasing rate. In this paper, however, we base our analysis on Theorem 3
which we have only been able to prove for constant $\sigma$ from round to
round. For this reason, the theory in this paper needs to start with a
clipping constant $C$ large enough in order to initiate convergence and we do
not decrease $C$ from round to round. This means that both $C$ and $\sigma$
are constant throughout DP-SGD and the range of $\sigma$ and $C$ combinations
learned from the utility graph is limited.

If there exists a $\sigma$ and $C$ combination for which the utility graph
expects good enough accuracy of the final global model and for which formula
(1) indicates an acceptable differential privacy guarantee, then we can choose
parameters $s$ and $T$ freely in that their product $K=sT$, which represents
the total number of local gradient computations over all rounds, is large
enough to establish convergence (given the learning rate / step size sequence
$\eta_{t}$ and used clipping constant $C$). Experiments show that $K$ being in
the order of 50-100s epochs of gradient computations is sufficient. We
optimize $s$ and $T$ for best accuracy of the final model. If all local data
sets are iid, that is, come from the same source distribution, then the larger
$s$ and the smaller $T$ seems best. So, for best accuracy in the iid case, we
suggest to meet condition (3) with equality.

Proactive DP-SGD: The above describes how our main formula (1) can be used to
implement planning ahead, that is, given a local data set size $N$ with DP
budget $(\epsilon_{target},\delta_{target})$ and a prediction/test accuracy
target $acc_{target}$ (of the final global model) we can a-priori derive/set
hyper-parameters $\sigma$, $s$, and $T$. We generalize this towards proactive
DP-SGD in Appendix E where the client uses a private test data set to evaluate
the accuracy of received global models. If the test accuracy does not converge
towards an acceptable value $\geq acc_{target}$ at a noticeable rate from
round to round, then the client adapts $\sigma$ to a slightly smaller value
(if allowed by the DP budget) and recomputes hyper parameters. Our theory is
general enough to accommodate varying (in this case increasing) sample size
sequences (we can use Theorem 4 of which Theorem 1 is a consequence as it has
no concrete restriction on $\theta$). Our proactive DP-SGD is designed to
attain the best DP guarantee given $acc_{target}$ within our framework.

The main advantage of proactive DP-SGD is that without a-prior knowledge
proactive DP-SGD learns how to fine tune parameters itself in order to reach a
target test accuracy while remaining within a target privacy budget. Proactive
DP-SGD does not need one to run other (distributed) experiments that
potentially leak privacy in order to be able to select ‘good’ hyper
parameters.

###  3.2 Interpreting the Limiting Constraint on $T$

Lower bound (3) on $T$ shows that we may increase $T$ without having to
increase $\sigma$ – in this sense $\sigma$ does not depend on $T$ anymore.
This important discovery brings DP-SGD to practice because, in order to make
the trained model have high accuracy even for large $T$ as happens in
practice, $\sigma$ does not need to increase with $T$ as indicated by our
formula (1). In fact $T$ can become as large as $K$ (corresponding to sample
size $s=1$) implying that for $K=T$, lower bound (3) on $T$ translates into
$\epsilon$ at least a small constant $\gamma\theta^{2}$ times $K/N^{2}$
(leading to the interpretation in the abstract). First, this shows that in
theory $\epsilon$ can be chosen very small for large enough data sets $N$ and
practical $K$ (although as explained above, very small $\epsilon$ lead to too
large $\sigma$ implying low accuracy, hence, our requirement on accuracy
likely leads to a more strict lower bound on $\epsilon$). Second, requiring
$\epsilon$ at least a constant $\gamma\theta^{2}$ times $K/N^{2}$ with $K=kN$
(that is, $K$ is equal to $k$ epochs of gradient computations) is equivalent
to requiring $N$ at least a constant $\gamma\theta^{2}$ times $k/\epsilon$.
For typical values of $k$ (100s of epochs), this means

$N=\Omega(1/\epsilon).$

Our $\sigma$ therefore depends on $N$ rather than $T$ because the constraints
on selecting $\epsilon$ and $\delta$ depends only on $N$ as explained above.
For improved differential privacy (smaller $\epsilon$), we need a larger data
set (larger $N$). This observation comes natural since selecting (subsampling)
a random batch of local training data among a larger data set helps in making
round computation less dependent on an a-priori selected single local training
data sample and being able to differentiate whether such a local training data
sample is part of the larger local training data set is what differential
privacy is about.

In Section 3.1 we explained that with respect to achieving good utility
(sufficient clean accuracy) experiments show that reducing the so-called
clipping constant up to some value leads to convergence to a global model that
is less sensitive to noise. Reducing the clipping constant can mean a
magnitude larger $K$ in order for DP-SGD to converge (because a smaller
clipping constant implies that locally computed gradients contribute less to
the global model). This implies a larger number $k$ of epochs of local
gradient computations, hence, the local data set needs to be larger for
differential privacy to hold (as $N$ is required to be at least a constant
$\gamma\theta^{2}$ times $k/\epsilon$, see above).

We stress that in our theory $T$ cannot grow arbitrarily large as it is
restricted by $K=kN$. Also $k$ cannot grow arbitrarily large since
$N\geq\gamma\theta^{2}\cdot k/\epsilon$. This upper bound on $k$ does impose a
constraint after which $(\epsilon,\delta)$-DP cannot be guaranteed – so, $K$
and, hence, $T$ cannot increase indefinitely without violating the privacy
budget. Here we notice that repeated use of the same data set over multiple
learning problems (one after another) is allowed as long as the number of
epochs gradient computing is $k\leq\frac{\epsilon N}{\gamma\theta^{2}}$.
Hence, the larger $N$ the more collaborative learning tasks the client can
participate in. For typical values $\epsilon=0.2$, $\gamma\theta^{2}\approx
2$, and a data set of size $N=10000$ we have $k\leq 1000$, which accommodates
about 10-20 learning tasks.

As a final remark, Section C.2 analyses the tightness of Theorem 1 in an
asymptotic setting: The lower bound on $T$ in Theorem 1 can be reduced by at
most a factor $4\gamma\theta^{2}$.

##  4 Experiments

Our goal is to show that the more general asynchronous differential privacy
framework (asynchronous DP-SGD which includes DP-SGD of Algorithm 1) of
Appendix A ensures a strong privacy guarantee, i.e, can work with very small
$\epsilon$ (and $\delta=1/N$), while having a good convergence rate to good
accuracy. We refer to Appendix D for simulation details and complete parameter
settings.

Objective function. We summarize experimental results of our asynchronous DP-
SGD framework for strongly convex, plain convex and non-convex objective
functions with constant sample size sequences. As the plain convex objective
function we use logistic regression: The weight vector $w$ and bias value $b$
of the logistic function can be learned by minimizing the log-likelihood
function $J$:

$J=-\sum_{i=1}^{N}[y_{i}\cdot\log(\bar{\sigma}_{i})+(1-y_{i})\cdot\log(1-\bar{\sigma}_{i})],$

where $N$ is the number of training samples $(x_{i},y_{i})$ with
$y_{i}\in\\{0,1\\}$, and $\bar{\sigma}_{i}=1/(1+e^{-(w^{\mathrm{T}}x_{i}+b)})$
is the sigmoid function. The goal is to learn a vector/model $w^{*}$ which
represents a pair $\bar{w}=(w,b)$ that minimizes $J$. Function $J$ changes
into a strongly convex problem by adding ridge regularization with a
regularization parameter $\lambda>0$, i.e., we minimize
$\hat{J}=J+\frac{\lambda}{2}\left\|\bar{w}\right\|^{2}$ instead of $J$. For
simulating non-convex problems, we choose a simple neural network (LeNet) [17]
with cross entropy loss function for image classification.

Asynchronous DP-SGD setting. The experiments are conducted with $5$ compute
nodes and $1$ central server. For simplicity, the compute nodes have iid
datasets.

Data sets. All our experiments are conducted on LIBSVM
[3]111https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/binary.html and
MNIST [16] 222http://yann.lecun.com/exdb/mnist/ data sets.

###  4.1 Utility graph

Since we do not have a closed form to describe the relation between the
utility of the model (i.e., prediction accuracy) and $\sigma$, we propose a
heuristic approach to learn the range of $\sigma$ from which we may select
$\sigma$ for finding the best $(\epsilon,\delta)$-DP. The utility graphs –
Figures 1a, 2a and 3a – show the fraction of test accuracy between the model
$F(w+n)$ over the original model $F(w)$ (without noise), where $n\sim{\cal
N}(0,C^{2}\sigma^{2}\textbf{I})$ for various values of the clipping constant
$C$ and noise standard deviation $\sigma$. Intuitively, the closer
$F(w+n)/F(w)$ to 1, the better accuracy wrt to $F(w)$. Note that $w$ can be
any solution and in the utility graphs, we choose $w=w^{*}$ with $w^{*}$ being
near to an optimal solution.

The smaller $C$, the larger $\sigma$ can be, hence, $\epsilon$ can be smaller
which gives stronger privacy. However, the smaller $C$, the more iterations
(larger $K$) are needed for convergence. And if selected too small, no fast
enough convergence is possible.

In next experiments we use clipping constant $C=0.1$, which gives a drop of at
most $10\%$ in test accuracy for $\sigma\leq 20$ for both strongly convex and
plain convex objective functions. To keep the test accuracy loss $\leq$ 10% in
the non-convex case, we choose $C=0.025$ and $\sigma\leq 12$.

###  4.2 Asynchronous DP-SGD with different constant sample size

(a)

(b)

(c)

Figure 1: Strongly convex. (a) Utility graph, (b) Different $s$, (c) Different
$\epsilon$

(a)

(b)

(c)

Figure 2: Plain convex. (a) Utility graph, (b) Different $s$, (c) Different
$\epsilon$

(a)

(b)

(c)

Figure 3: Non-convex. (a) Utility graph, (b) Different $s$, (c) Different
$\epsilon$

Figure 1b and Figure 2b illustrate the test accuracy of our asynchronous DP-
SGD with various constant sample sizes for the strongly convex and plain
convex cases. Here, we use privacy budget $\epsilon=0.04945$ and noise
$\sigma=19.2$. It is clear that with $s=1$, the algorithm shows a bad test
accuracy though this constant sample size has the maximum communication
rounds. When we use a bigger constant sample size $s$, for example, $s=26$,
our algorithm can achieve the desired performance, when compared to other
constant sample sizes.333$s=26$ meets the lower bound on $T$; a larger $s$
would violate this lower bound because of the relatively small data set size.
The experiment is extended to the non-convex case as shown in Figure 3b, where
we can see a similar pattern. Experimental results for other data sets are in
Appendix D in Supplemental Material. This confirms that our DP-SGD framework
can converge to a decent accuracy while achieving a very small privacy budget
$\epsilon$.

###  4.3 Asynchronous DP-SGD with different levels of privacy budget

Figure 1c and Figure 2c show that our DP-SGD framework converges to better
accuracy if $\epsilon$ is slightly larger. E.g., in the strongly convex case,
privacy budget $\epsilon=0.04945$ achieves test accuracy 86% compared to 93%
without differential privacy (hence, no added noise); $\epsilon=0.1$, still
significantly smaller than what is reported in literature, achieves test
accuracy 91%. Figure 3c shows the test accuracy of our asynchronous DP-SGD for
different privacy budgets $\epsilon$ in the non-convex case. For
$\epsilon=0.15$, our framework can achieve the test accuracy about $93\%$,
compared to $98\%$ without differential privacy. These figures again confirm
the effectiveness of our DP-SGD framework, which can obtain a strong
differential privacy guarantee.

##  5 Conclusion

We proved a new differential privacy guarantee for DP-SGD which is into large
extent insensitive to the total number of communication rounds, attains
significantly smaller $\epsilon$ than what has been reported in literature
(implying a sensible privacy guarantee), and does this for reasonable DP noise
such that test accuracy does not suffer much. We showed how the local data set
size $N$ plays an important role; it bounds $\epsilon=\Omega(1/N)$ for $O(1)$
epochs local gradient evaluations. Our theory is general in that it applies to
asynchronous DP-SGD (like Hogwild!) and it analyses arbitrary sequences of
sample sizes. We show how our theory allows planning ahead, i.e., being able
to a-priori optimize hyper parameters given a target accuracy and target
differential privacy budget. In our proactive DP-SGD framework it is possible
for local clients to adaptively trade-off privacy budget with test accuracy.
Clients can also control the privacy leakage of their local data set over
multiple learning tasks. The above indicates that DP-SGD is competitive with
other solutions such as distributed DP which employs a secure function (such
as a secure shuffler) implemented by secure Multi Party Computation (which is
communication intense) and/or a Trusted Execution Environment (which requires
trust in a larger Trusted Computing Base).

## 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.
  * Chang and Lin [2011] Chih-Chung Chang and Chih-Jen Lin.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2:27:1–27:27, 2011.
  * 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 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. [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.
  * 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.
  * Geyer et al. [2018] Robin C. Geyer, Tassilo Klein, and Moin Nabi.  Differentially private federated learning: A client level perspective, 2018.
  * 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.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * Leblond et al. [2018] Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien.  Improved asynchronous parallel optimization analysis for stochastic incremental methods.  _JMLR_ , 19(1):3140–3207, 2018.
  * LeCun and Cortes [2010] Yann LeCun and Corinna Cortes.  MNIST handwritten digit database.  2010\.  URL http://yann.lecun.com/exdb/mnist/.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lyu et al. [2020] Lingjuan Lyu, Han Yu, and Qiang Yang.  Threats to federated learning: A survey, 2020.
  * 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. [2017] H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas.  Communication-efficient learning of deep networks from decentralized data, 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. [2021] Nhuong Nguyen, Toan Nguyen, Phuong Ha Nguyen, Quoc Tran-Dinh, Lam Nguyen, and Marten Dijk.  Hogwild! over distributed local data sets with linearly increasing mini-batch sizes.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1207–1215. PMLR, 2021.
  * 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.
  * Recht et al. [2011] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu.  Hogwild: A lock-free approach to parallelizing stochastic gradient descent.  In _Advances in neural information processing systems_ , pages 693–701, 2011.
  * Roux et al. [2012] Nicolas Roux, Mark Schmidt, and Francis Bach.  A stochastic gradient method with an exponential convergence rate for finite training sets.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * 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.
  * 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.
  * 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.
  * 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.
  * Zhang et al. [2016] Huan Zhang, Cho-Jui Hsieh, and Venkatesh Akella.  Hogwild++: A new mechanism for decentralized asynchronous stochastic gradient descent.  In _2016 IEEE 16th International Conference on Data Mining (ICDM)_ , pages 629–638. IEEE, 2016.
  * 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.  In _Advances in Neural Information Processing Systems_ , volume 32, 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.

Bringing Differential Private SGD to Practice:
On the Independence of Gaussian Noise and the Number of Training Rounds
Appendix

##  Appendix A Asynchronous Mini-Batch DP-SGD

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\\}.$
(4)

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 (4) 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 Stochastic Gradient Descent (SGD) recursion

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

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 $\xi$
that belong to the client’s local data set. The updates as a result of the SGD
recursion (5) 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 is doing SGD recursions for a batch of local data. These
recursions together represent a local round and at the end of the local round
the sum of local model updates, i.e., the addition of computed gradients, is
transmitted to the server. The server in turn adds the received sum of local
updates to its global model – and once the server receives new sums from all
clients, the global model is broadcast to each of the clients. When
considering privacy, we are concerned about how much information these sums of
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 [9, 7, 10, 8] 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 achieving good accuracy. On the other hand, only if the
magnitude of the added noise is large enough, then good differential privacy
guarantees can be given.

When using Gaussian based differential privacy, each local round produces a
sum of locally computed gradients based on the local data set, which is
transmitted to the central server after adding Gaussian noise [1]. Because of
this, each local training round communicates information about the
corresponding local data set. Privacy leakage aggregates over multiple
training rounds, and the total amount of privacy leakage from the local data
set increases as the total number $T$ of local training rounds increases.

Algorithms444Our pseudocode uses the format from [24]. 2, 3, and 4 explain in
pseudo code our asynchronous LDP approach. It is based on the Hogwild! [26]
recursion

$w_{t+1}=w_{t}-\eta_{t}\nabla f(\hat{w}_{t};\xi_{t}),$ (6)

where $\hat{w}_{t}$ represents the vector used in computing the gradient
$\nabla f(\hat{w}_{t};\xi_{t})$ and whose vector entries have been read (one
by one) from an aggregate of a mix of previous updates that led to $w_{j}$,
$j\leq t$. In a single-thread setting where updates are done in a fully
consistent way, i.e. $\hat{w}_{t}=w_{t}$, yields SGD with diminishing step
sizes $\\{\eta_{t}\\}$.

Recursion (6) models asynchronous SGD. The amount of asynchronous behavior
that can be tolerated is given by some function $\tau(t)$, see [23] where this
is analysed for strongly convex objective functions: We say that the sequence
$\\{w_{t}\\}$ is consistent with delay function $\tau$ if, for all $t$, vector
$\hat{w}_{t}$ includes the aggregate of the updates up to and including those
made during the $(t-\tau(t))$-th iteration, i.e.,

$\hat{w}_{t}=w_{0}-\sum_{j\in{\cal U}}\eta_{j}\nabla f(\hat{w}_{j};\xi_{j})$

for some ${\cal U}$ with $\\{0,1,\ldots,t-\tau(t)-1\\}\subseteq{\cal U}$.

In Algorithm 4 the local SGD iterations all compute gradients based on the
same local model $\hat{w}$, which gets substituted by a newer global model
$\hat{v}_{k}$ as soon as it is received by the interrupt service routine
ISRReceive. As explained in ISRReceive $\hat{v}_{k}$ includes all the updates
from all the clients up to and including their local rounds $\leq k$. This
shows that locally the delay $\tau$ can be estimated based on the current
local round $i$ together with $k$. Depending on how much delay can be
tolerated Setup defines $\Upsilon(k,i)$ to indicate whether the combination
$(k,i)$ is permissible (i.e., the corresponding delay aka asynchronous
behavior can be tolerated). It has been shown that for strongly convex
objective functions (without DP enhancement) the convergence rate remains
optimal even if the delay $\tau(t)$ is as large as $\approx\sqrt{t/\ln t}$
[23]. Similar behavior has been reported for plain convex and non-convex
objective functions in [24].

In Algorithm 4 we assume that messages/packets never drop; they will be resent
but can arrive out of order. This guarantees that we get out of the "while
$\Upsilon(k,i)$ is false loop" because at some moment the server receives all
the updates in order to broadcast a new global model $\hat{v}_{k+1}$ and once
received by ISRReceive this will increment $k$ and make $\Upsilon(k,i)$ true
which allows LocalSGDwithDP to exit the wait loop. As soon as the wait loop is
exited we know that all local gradient computations occur when $\Upsilon(k,i)$
is true which reflect that these gradient computations correspond to delays
that are permissible (in that we still expect convergence of the global model
to good accuracy).

Algorithm 2 Client – Local model with Differential Privacy

1:procedure Setup($n$):
Initialize sample size sequence $\\{s_{i}\\}_{i=0}^{T}$, (diminishing) round
step sizes $\\{\bar{\eta}_{i}\\}_{i=0}^{T}$, and a default global model
${\hat{v}}_{0}$ to start with.
Define a permissible delay function
$\Upsilon(k,i)\in\\{\textbf{True},\textbf{False}\\}$ which takes the current
local round number $i$ and the round number $k$ of the last received global
model into account to find out whether local SGD should wait till a more
recent global model is received. $\Upsilon(\cdot,\cdot)$ can also make use of
knowledge of the sample size sequences used by each of the clients.

2:end procedure

Algorithm 3 Client – Local model with Differential Privacy

1:procedure ISRReceive($\hat{v}_{k}$):
This Interrupt Service Routine is called whenever a new broadcast global model
$\hat{v}_{k}$ is received from the server. Once received, the client’s local
model $\hat{w}$ is replaced with $\hat{v}_{k}$ (if no more recent global model
$\hat{v}_{>k}$ was received out of order before receiving this $\hat{v}_{k}$)
The server broadcasts global model $\hat{v}_{k}$ for global round number $k$
once the updates corresponding to local round numbers $\leq k-1$ from all
clients have been received and have been aggregated into the global model. The
server aggregates updates from clients into the current global model as soon
as they come in. This means that $\hat{v}_{k}$ includes all the updates from
all the clients up to and including their local round numbers $\leq k-1$ and
potentially includes updates corresponding to later round numbers from subsets
of clients. The server broadcasts the global round number $k$ together with
$\hat{v}_{k}$.

2:end procedure

Algorithm 4 Client – Local model with Differential Privacy

1:procedure LocalSGDwithDP($d$)

2: $i=0$, $\hat{w}=\hat{v}_{0}$

3: while True do

4: while $\Upsilon(k,i)=\textbf{False}$ do nothing end $\triangleright$ $k$ is
the global round at the server.

5: Uniformly sample a random set $\\{\xi_{h}\\}_{h=1}^{s_{i}}\subseteq d$

6: $h=0$, $U=0$

7: while $h<s_{i}$ do

8: $g=[\nabla f(\hat{w},\xi_{h})]_{C}$

9: ${U}={U}+g$

10: $h$++

11: end while

12: $n\leftarrow{\cal N}(0,C^{2}\sigma_{i}^{2}\textbf{I})$

13: $U=U+n$

14: $\hat{w}=\hat{w}+\bar{\eta}_{i}\cdot U$

15: Send $(i,U)$ to the Server.

16: $i$++

17: end while

18:end procedure

In this paper we analyse the Gaussian based differential privacy method of
[1]. We use their clipping method; rather than using the gradient $\nabla
f(\hat{w},\xi)$ itself, we use its clipped version $[\nabla
f(\hat{w},\xi)]_{C}$ where $[x]_{C}=x/\max\\{1,\|x\|/C\\}$. Also, we use the
same mini-batch approach where before the start of the $i$-th local round a
random min-batch of sample size $s_{i}$ is selected. During the inner loop the
sum of gradient updates is maintained where each of the gradients correspond
to the same local model $\hat{w}$ until it is replaced by a newer global
model. In supplementary material B we show that this is needed for proving DP
guarantees and that generalizing the algorithm by locally implementing the
Hogwild! recursion itself (which updates the local model each iteration) does
not work together with the DP analysis. So, our approach only uses the
Hogwild! concept at a global round by round interaction level.

At the end of each local round the sum of updates $U$ is obfuscated with
Gaussian noise; Gaussian noise ${\cal N}(0,C^{2}\sigma_{i}^{2})$ is added to
each vector entry. In this general description $\sigma_{i}$ is round
dependent, but our DP analysis in Supplementary Material B must from some
point onward assume a constant $\sigma=\sigma_{i}$ over all rounds. The noised
$U$ times the round step size $\bar{\eta}_{i}$ is added to the local model
after which a new local round starts again.

The noised $U$ is also transmitted to the server who adds $U$ times the round
step size $\bar{\eta}_{i}$ to its global model $\hat{v}$. As soon as all
clients have submitted their updates up to and including their local rounds
$\leq k-1$, the global model $\hat{v}$, denoted as $\hat{v}_{k}$, is broadcast
to all clients, who in turn replace their local models with the newly received
global model. Notice that $\hat{v}_{k}$ may include updates from a subset of
clients that correspond to local rounds $\geq k$. We refer to [24] for pseudo
code of these computations at the server.

The presented algorithm adapts to asynchronous behavior in the following two
ways: We explained above that the broadcast global models $\hat{v}_{k}$
themselves include a mix of received updates that correspond to local rounds
$\geq k$ – this is due to asynchronous behavior. Second, the sample size
sequence $\\{s_{i}\\}$ does not necessarily need to be fixed a-priori during
Setup (the round step size sequence $\\{\bar{\eta}_{i}\\}$ does need to be
fixed a-priori). In fact, the client can adapt its sample sizes $s_{i}$ on the
fly to match its speed of computation and communication latency. This allows
the client to adapt its local mini-batch SGD to its asynchronous behavior due
to the scheduling of its own resources. Our DP analysis holds for a wide range
of varying sample size sequences.

We notice that adapting sample size sequences on a per client basis still fits
the same overall objective function as long as all local data sets are iid:
This is because iid implies that the execution of the presented algorithm can
be cast in a single Hogwild! recursion where the $\xi_{h}$ are uniformly
chosen from a common data source distribution ${\cal D}$. This corresponds to
the stochastic optimization problem

$\displaystyle\min_{w\in\mathbb{R}^{d}}\left\\{F(w)=\mathbb{E}_{\xi\sim\mathcal{D}}[f(w;\xi)]\right\\},$

which defines objective function $F$ (independent of the locally used sample
size sequences). Local data sets being iid in the sense that they are all, for
example, drawn from car, train, boat, etc images benefit from DP in that car
details (such as an identifying number plate), boat details, etc. need to
remain private.

##  Appendix B Differential privacy proofs

This appendix provides the proof of Theorem 1. It follows a sequence of steps:
In Section B.1 we discuss the analysis of [1] and explain where we will
improve. This leads in Section B.2 to an improved analysis yielding a first
generally applicable Theorem 3; DP definitions/tools with a key lemma
(generalized from [1]) are discussed in Section B.2.1 and the proof of Theorem
3 is in Section B.2.2. As a consequence we derive in Section B.3 a simplified
characterization in the form of Theorem 4. Finally, we introduce more coarse
bounds in order to extract the more readable Theorem 1 in Section B.4.

###  B.1 DP-SGD Analysis by Abadi et al.

[1] proves the following theorem (rephrased using our notation substituting
$q=s/N$):

######  Theorem 2.

There exist constants $c_{1}$ and $c_{2}$ so that given a sample size sequence
$s_{i}=s$ and number of steps $T$, for any $\epsilon<c_{1}T(s/N)^{2}$,
Algorithm 1 is $(\epsilon,\delta)$-differentially private for any $\delta>0$
if we choose

$\sigma\geq c_{2}\frac{(s/N)\cdot\sqrt{T\ln(1/\delta)}}{\epsilon}.$

The theorem suggests a necessary dependence between $\sigma$ and $T$ where
$\sigma$ scales with $\sqrt{T}$ for fixed $s$ and $N$. If this is indeed
necessary, then in order to achieve good accuracy for a given $\sigma$ we need
to increase the number of rounds $T$, but this requires us to increase
$\sigma$, which increases $T$, etc. This reasoning would imply a subtle
setting of $\sigma$ and $T$ for a given privacy budget $(\epsilon,\delta)$
that leads to ‘best’ accuracy. Here, $\sigma$ must be small enough so that it
does not causes too much noise in the final global model. But this implies
that the ‘best’ accuracy is restricted by only being able to use a limited
number of training rounds $T$ (since $T$ cannot be too large for small enough
$\sigma=O(\sqrt{T})$).

The interpretation of Theorem 2, however, is more subtle: The condition on
$\epsilon$ in Theorem 2 is equivalent to

$1/\sqrt{c_{1}}<z\mbox{ where }z=(s/N)\cdot\sqrt{T/\epsilon}.$

Substituting this into the bound for $\sigma$ yields

$\sigma\geq(c_{2}\cdot z)\cdot\sqrt{\frac{\ln(1/\delta)}{\epsilon}}.$ (7)

This formulation only depends on $T$ through the definition of $z$. Notice
that $z$ may be as small as $1/\sqrt{c_{1}}$. In fact, it is unclear how $z$
depends on $T$ since $T$ is equal to the total number $K$ of gradient
computations over all local rounds performed on the local data set divided by
the mini-batch size $s$, i.e., $T=K/s$, hence,
$z=(K/N)\cdot\sqrt{1/(T\epsilon)}$. This shows that for fixed $K$ and $N$, we
can increase $T$ as long as $1/\sqrt{c_{1}}<z$, or equivalently,

$T<c_{1}(K/N)^{2}/\epsilon$ (8)

(notice that the original constraint on $\epsilon$ in Theorem 2 directly
translates into this upper bound on $T$ by using $T=K/s$). Since $\sigma$
cannot be chosen too large (otherwise the final global model has too much
noise), $\epsilon$, see (7), cannot be very small. Therefore, this more
precise analysis still puts an upper bound on $T$ which is in general much
less than $K$ for practically sized large data sets ($K$ equals the maximum
possible number of rounds for mini-batch size $s=1$).

Rather than applying Theorem 2, we can directly use the moment accountant
method of its proof to analyse specific parameter settings. It turns out that
$T$ can be much larger than upper bound (8). In this paper we formalize this
insight (by showing that ‘constants’ $c_{1}$ and $c_{2}$ can be chosen as
functions of $T$ and other parameters) and show a lower bound on $\sigma$
which does not depend on $T$ at all – in fact $z$ in (7) can be characterized
as a constant independent of any parameters. This will show that $\sigma$ can
remain small up to a lower bound that only depends on the privacy budget. We
can freely increase $T$ (up to $K$ if needed) in order to improve accuracy.

###  B.2 A General Improved DP-SGD Analysis

We generalize Theorem 2 [1]:

######  Theorem 3.

We assume that $\sigma=\sigma_{i}$ with $\sigma\geq 216/215$ for all rounds
$i$. Let

$r=r_{0}\cdot
2^{3}\cdot\left(\frac{1}{1-u_{0}}+\frac{1}{1-u_{1}}\frac{e^{3}}{\sigma^{3}}\right)e^{3/\sigma^{2}}\mbox{
with }u_{0}=\frac{2\sqrt{r_{0}\sigma}}{\sigma-r_{0}}\mbox{ and
}u_{1}=\frac{2e\sqrt{r_{0}\sigma}}{(\sigma-r_{0})\sigma},$

where $r_{0}$ is such that it satisfies

$r_{0}\leq 1/e,\ u_{0}<1,\mbox{ and }u_{1}<1.$

Let the sample size sequence satisfy $s_{i}/N\leq r_{0}/\sigma$. For $j=1,2,3$
we define $\hat{S}_{j}$ (resembling an average over the sum of $j$-th powers
of $s_{i}/N$) with related constants $\rho$ and $\hat{\rho}$:

$\hat{S}_{j}=\frac{1}{T}\sum_{i=0}^{T-1}\frac{s_{i}^{j}}{N(N-s_{i})^{j-1}},\ \
\frac{\hat{S}_{1}\hat{S}_{3}}{\hat{S}_{2}^{2}}\leq\rho\mbox{ and
}\frac{\hat{S}_{1}^{2}}{\hat{S}_{2}}\leq\hat{\rho}.$

Let $\epsilon=c_{1}T\hat{S}_{1}^{2}$. Then, Algorithm 4 is
$(\epsilon,\delta)$-differentially private if

$\displaystyle\sigma\geq\frac{2}{\sqrt{c_{0}}}\frac{\sqrt{\hat{S}_{2}T(\epsilon+\ln(1/\delta))}}{\epsilon}\mbox{
where }c_{0}=c(c_{1})\mbox{ with }c(x)=\min\left\\{\frac{\sqrt{2r\rho
x+1}-1}{r\rho x},\frac{2}{\hat{\rho}x}\right\\}.$

This generalizes Theorem 2 where all $s_{i}=s$ are constant. First, Theorem 3
covers a much broader class of sample size sequences that satisfy bounds on
their ’moments’ $\hat{S}_{j}$ (this is more clear as a consequence of Theorem
3). Second, our detailed analysis provides a tighter bound in that it makes
the relation between “constants” $c_{0}$ and $c_{1}$ explicit, contrary to
[1]. Exactly due to this relation $c_{0}=c(c_{1})$ we are able to prove in
Supplemental Material B.3 Theorem 4 as a consequence of Theorem 3 by
considering the case $c(c_{1})=2/(\hat{\rho}c_{1})$.

In order to prove Theorem 3, we first set up the differential privacy
framework of [1] in Appendix B.2.1. Here we enhance a core lemma by proving a
concrete bound rather than an asymptotic bound on the so-called $\lambda$-th
moment which plays a crucial role in the differential privacy analysis. The
concrete bound makes explicit the higher order error term in [1].

In Appendix B.2.2 we generalize Theorem 2 of [1] by proving Theorem 4 using
the core lemma of Appendix B.2.1.

####  B.2.1 Definitions and Main Lemma

We base our proofs on the framework and theory presented in [1]. In order to
be on the same page we repeat and cite word for word their definitions:

For neighboring databases $d$ and $d^{\prime}$, a mechanism ${\cal M}$,
auxiliary input aux, and an outcome $o$, define the privacy loss at $o$ as

$c(o;{\cal M},\texttt{aux},d,d^{\prime})=\ln\frac{Pr[{\cal
M}(\texttt{aux},d)=o]}{Pr[{\cal M}(\texttt{aux},d^{\prime})=o]}.$

For a given mechanism ${\cal M}$, we define the $\lambda$-th moment
$\alpha_{{\cal M}}(\lambda;\texttt{aux},d,d^{\prime})$ as the log of the
moment generating function evaluated at the value $\lambda$:

$\alpha_{{\cal
M}}(\lambda;\texttt{aux},d,d^{\prime})=\ln\textbf{E}_{o\sim{\cal
M}(\texttt{aux},d)}[\exp(\lambda\cdot c(o;{\cal
M},\texttt{aux},d,d^{\prime}))].$

We define

$\alpha_{{\cal M}}(\lambda)=\max_{\texttt{aux},d,d^{\prime}}\alpha_{{\cal
M}}(\lambda;\texttt{aux},d,d^{\prime})$

where the maximum is taken over all possible aux and all the neighboring
databases $d$ and $d^{\prime}$.

We first take Lemma 3 from [1] and make explicit their order term
$O(q^{3}\lambda^{3}/\sigma^{3})$ with $q=s_{i,c}$ and $\sigma=\sigma_{i}$ in
our notation. The lemma considers as mechanism ${\cal M}$ the $i$-th round of
gradient updates and we abbreviate $\alpha_{{\cal M}}(\lambda)$ by
$\alpha_{i}(\lambda)$. The auxiliary input of the mechanism at round $i$
includes all the output of the mechanisms of previous rounds (as in [1]).

For the local mini-batch SGD the mechanism ${\cal M}$ of the $i$-th round is
given by

${\cal M}(\texttt{aux},d)=\sum_{h=0}^{s_{i}-1}[\nabla
f(\hat{w},\xi_{h})]_{C}+{\cal N}(0,C^{2}\sigma_{i}^{2}\textbf{I}),$

where $\hat{w}$ is the local model at the start of round $i$ which is replaced
by a new global model $\hat{v}$ as soon as a new $\hat{v}$ is received from
the server (see ISRReceive), and where $\xi_{h}$ are drawn from training data
$d$, and $[.]_{C}$ denotes clipping (that is
$[x]_{C}=x/\max\\{1,\|x\|_{2}/C\\}$). In order for ${\cal M}$ to be able to
compute its output, it needs to know the global models received in round $i$
and it needs to know the starting local model $\hat{w}$. To make sure ${\cal
M}$ has all this information, aux represents the collection of all outputs
generated by the mechanisms of previous rounds $<i$ together with the global
models received in round $i$ itself.

In the next subsection we will use the framework of [1] and apply its
composition theory to derive bounds on the privacy budget $(\epsilon,\delta)$
for the whole computation consisting of $T$ rounds that reveal the outputs of
the mechanisms for these $T$ rounds as described above.

We remind the reader that $s_{i}/N$ is the probability of selecting a sample
from a sample set (batch) of size $s_{i}$ out of a training data set
$d^{\prime}$ of size $N=|d^{\prime}|$; $\sigma_{i}$ corresponds to the ${\cal
N}(0,C^{2}\sigma_{i}^{2}\textbf{I})$ noise added to the mini-batch gradient
computation in round $i$ (see the mechanism described above).

######  Lemma 1.

Assume a constant $r_{0}<1$ and deviation $\sigma_{i}\geq 216/215$ such that
$s_{i}/N\leq r_{0}/\sigma_{i}$. Suppose that $\lambda$ is a positive integer
with

$\lambda\leq\sigma_{i}^{2}\ln\frac{N}{s_{i}\sigma_{i}}$

and define

$U_{0}(\lambda)=\frac{2\sqrt{\lambda
r_{0}/\sigma_{i}}}{\sigma_{i}-r_{0}}\mbox{ and
}U_{1}(\lambda)=\frac{2e\sqrt{\lambda
r_{0}/\sigma_{i}}}{(\sigma_{i}-r_{0})\sigma_{i}}.$

Suppose $U_{0}(\lambda)\leq u_{0}<1$ and $U_{1}(\lambda)\leq u_{1}<1$ for some
constants $u_{0}$ and $u_{1}$. Define

$\displaystyle r$ $\displaystyle=$ $\displaystyle r_{0}\cdot
2^{3}\left(\frac{1}{1-u_{0}}+\frac{1}{1-u_{1}}\frac{e^{3}}{\sigma_{i}^{3}}\right)\exp(3/\sigma_{i}^{2}).$

Then,

$\alpha_{i}(\lambda)\leq\frac{s_{i}^{2}\lambda(\lambda+1)}{N(N-s_{i})\sigma_{i}^{2}}+\frac{r}{r_{0}}\cdot\frac{s_{i}^{3}\lambda^{2}(\lambda+1)}{N(N-s_{i})^{2}\sigma_{i}^{3}}.$

Proof. The start of the proof of Lemma 3 in [1] implicitly uses the proof of
Theorem A.1 in [10], which up to formula (A.2) shows how the 1-dimensional
case translates into a privacy loss that corresponds to the 1-dimensional
problem defined by $\mu_{0}$ and $\mu_{1}$ in the proof of Lemma 3 in [1], and
which shows at the end of the proof of Theorem A.1 (p. 268 [10]) how the
multi-dimensional problem transforms into the 1-dimensional problem. In the
notation of Theorem A.1, $f(D)+{\cal N}(0,\sigma^{2}\textbf{I})$ represents
the general (random) mechanism ${\cal M}(D)$, which for Lemma 3 in [1]’s
notation should be interpreted as the batch computation

${\cal M}(d)=\sum_{h\in J}f(d_{h})+{\cal N}(0,\sigma^{2}\textbf{I})$

for a random sample/batch $\\{d_{h}\\}_{h\in J}$. Here, $f(d_{h})$ (by abuse
of notation – in this context $f$ does not represent the objective function)
represent clipped gradient computations $\nabla f(\hat{w};d_{h})$ where
$\hat{w}$ is the last received global model with which round $i$ starts (Lemma
3 in [1] uses clipping constant $C=1$, hence ${\cal
N}(0,C^{2}\sigma^{2}\textbf{I})={\cal N}(0,\sigma^{2}\textbf{I})$).

Let us detail the argument of the proof of Lemma 3 in [1] in order to
understand what flexibility is possible: We consider two data sets
$d=\\{d_{1},\ldots,d_{N-1}\\}$ and $d^{\prime}=d+\\{d_{N}\\}$, where
$d_{N}\not\in d$ represents a new data base element so that $d$ and
$d^{\prime}$ differ in exactly one element. The size of $d^{\prime}$ is equal
to $N$. We define vector $x$ as the sum

$x=\sum_{J\setminus\\{N\\}}f(d_{i}).$

Let

$z=f(d_{N}).$

If we consider data set $d$, then sample set $J\subseteq\\{1,\cdots,N-1\\}$
and mechanism ${\cal M}(d)$ returns

${\cal M}(d)=\sum_{h\in J}f(d_{h})+{\cal N}(0,\sigma^{2}\textbf{I})=\sum_{h\in
J\setminus\\{N\\}}f(d_{h})+{\cal N}(0,\sigma^{2}\textbf{I})=x+{\cal
N}(0,\sigma^{2}\textbf{I}).$

If we consider data set $d^{\prime}$, then $J\subseteq\\{1,\cdots,N\\}$
contains $d_{N}$ with probability $q=|J|/N$ ($|J|=s_{i}$ is the sample size
used in round $i$). In this case mechanism ${\cal M}(d^{\prime})$ returns

${\cal M}(d^{\prime})=\sum_{h\in J}f(d_{h})+{\cal
N}(0,\sigma^{2}\textbf{I})=f(d_{N})+\sum_{h\in
J\setminus\\{N\\}}f(d_{h})+{\cal N}(0,\sigma^{2}\textbf{I})=z+x+{\cal
N}(0,\sigma^{2}\textbf{I})$

with probability $q$. It returns

${\cal M}(d^{\prime})=\sum_{h\in J}f(d_{h})+{\cal
N}(0,\sigma^{2}\textbf{I})=\sum_{h\in J\setminus\\{N\\}}f(d_{h})+{\cal
N}(0,\sigma^{2}\textbf{I})=x+{\cal N}(0,\sigma^{2}\textbf{I})$

with probability $1-q$. Combining both cases shows that ${\cal M}(d^{\prime})$
represents a mixture of two Gaussian distributions (shifted over a vector
$x$):

${\cal M}(d^{\prime})=x+(1-q)\cdot{\cal N}(0,\sigma^{2}\textbf{I})+q\cdot{\cal
N}(z,\sigma^{2}\textbf{I}).$

This high dimensional problem is transformed into a single dimensional problem
at the end of the proof of Theorem A.1 (p. 268 [10]) by considering the one
dimensional line from point $x$ into the direction of $z$, i.e., the line
through points $x$ and $x+z$; the one dimensional line maps $x$ to the origin
$0$ and $x+z$ to $\|z\|_{2}$. ${\cal M}(d)$ as wells as ${\cal M}(d^{\prime})$
projected on this line are distributed as

${\cal M}(d)\sim\mu_{0}\mbox{ and }{\cal
M}(d^{\prime})\sim(1-q)\mu_{0}+q\mu_{1},$

where

$\mu_{0}\sim{\cal N}(0,\sigma^{2})\mbox{ and }\mu_{1}\sim{\cal
N}(\|z\|_{2},\sigma^{2}).$

In [1] as well as in this paper the gradients are clipped (their Lemma 3 uses
clipping constant $C=1$) and this implies

$\|z\|_{2}=\|f(d_{N})\|_{2}\leq C=1.$

Their analysis continues by assuming the worst-case in differential privacy,
that is,

$\mu_{1}\sim{\cal N}(1,\sigma^{2}).$

Notice that the above argument analyses a local mini-batch SGD computation.
Rather than using a local mini-batch SGD computation, can we use clipped SGD
iterations which continuously update the local model:

$\hat{w}_{h+1}=\hat{w}_{h}-\eta_{h}\nabla[f(\hat{w}_{h},\xi_{h})]_{C}.$

This should lead to faster convergence to good accuracy compared to a local
minibatch computation. However, the above arguments cannot proceed555Unless we
assume a general upper bound on the norm of the Hessian of the objective
function which should be large enough to cover a wide class of objective
functions and small enough in order to be able to derive practical
differential privacy guarantees. because (in the notation used above where the
$d_{h}$, $h\in J$, are the $\xi_{h}$, $h\in\\{0,\ldots,s_{i}-1=|J|-1\\}$)
selecting sample $d_{N}$ in iteration $h$ does not only influence the update
computed in iteration $h$ but also influences all iterations after $h$ till
the end of the round (because $f(d_{N})$ updates the local model in iteration
$h$ which is used in the iterations that come after). Hence, the dependency on
$d_{N}$ is directly felt by $f(d_{N})$ in iteration $h$ and indirectly felt in
the $f(d_{j})$ that are computed after iteration $h$. This means that we
cannot represent distribution ${\cal M}(d^{\prime})$ as a clean mix of
Gaussian distributions with a mean $z$, whose norm is bounded by the clipping
constant.

The freedom which we do have is replacing the local model by a newly received
global model. This is because the updates $f(d_{h})$, $h\in J$, computed
locally in round $i$ have not yet been transmitted to the server and, hence,
have not been aggregated into the global model that was received. In a way the
mechanism ${\cal M}(d)$ is composed of two (or multiple if more newer and
newer global models are received during the round) sums

${\cal M}(d)=\sum_{h\in J_{0}}f_{0}(d_{h})+\sum_{h\in J_{1}}f_{1}(d_{h})+{\cal
N}(0,\sigma^{2}\textbf{I}),$

where $J=J_{0}\cup J_{1}$ and $J_{0}$ represent local gradient computations,
shown by $f_{0}(.)$, based on the initial local model $\hat{w}$ and $J_{1}$
represent the local gradient computations, shown by $f_{1}(.)$, based on the
newly received global model $\hat{v}$ which replaces $\hat{w}$. As one can
verify, the above arguments are still valid for this slight adaptation. As in
Lemma 3 in [1] we can now translate our privacy loss to the 1-dimensional
problem defined by $\mu_{0}\sim{\cal N}(0,C^{2}\sigma^{2})$ and
$\mu_{1}\sim{\cal N}(C,C^{2}\sigma^{2})$ for $\|\nabla f(.,.)\|_{2}\leq C$ as
in the proof of Lemma 3 (which after normalization with respect to $C$ gives
the formulation of Lemma 3 in [1] for $C=1$).

The remainder of the proof of Lemma 3 analyses $\mu_{0}$ and the mix
$\mu=(1-q)\mu_{0}+q\mu_{1}$ leading to bounds for the expectations (3) and (4)
in [1] which only depend on $\mu_{0}$ and $\mu_{1}$. Here, $q$ is the
probability of having a special data sample $\xi$ (written as $d_{N}$ in the
arguments above) in the batch. In our algorithm $q=s_{i}/N$. So, we may adopt
the statement of Lemma 3 and conclude for the $i$-th batch computation

$\alpha_{i}(\lambda)\leq\frac{s_{i}^{2}\lambda(\lambda+1)}{N(N-s_{i})\sigma_{i}^{2}}+O\left(\frac{s_{i}^{3}\lambda^{3}}{N^{3}\sigma_{i}^{3}}\right).$

In order to find an exact expression for the higher order term we look into
the details of Lemma 3 of [1]. It computes an upper bound for the binomial
tail

$\sum_{t=3}^{\lambda+1}{\lambda+1\choose
t}\mathbb{E}_{z\sim\nu_{1}}[((\nu_{0}(z)-\nu_{1}(z))/\nu_{1}(z))^{t}],$ (9)

where

$\displaystyle\mathbb{E}_{z\sim\nu_{1}}[((\nu_{0}(z)-\nu_{1}(z))/\nu_{1}(z))^{t}]$
(10) $\displaystyle\leq$
$\displaystyle\frac{(2q)^{t}(t-1)!!}{2(1-q)^{t-1}\sigma^{t}}+\frac{q^{t}}{(1-q)^{t}\sigma^{2t}}+\frac{(2q)^{t}\exp((t^{2}-t)/(2\sigma^{2}))(\sigma^{t}(t-1)!!+t^{t})}{2(1-q)^{t-1}\sigma^{2t}}$
$\displaystyle=$
$\displaystyle\frac{(2q)^{t}(t-1)!!(1+\exp((t^{2}-t)/(2\sigma^{2})))}{2(1-q)^{t-1}\sigma^{t}}+\frac{q^{t}(1+(1-q)2^{t}\exp((t^{2}-t)/(2\sigma^{2}))t^{t})}{2(1-q)^{t}\sigma^{2t}}$

Since $t\geq 3$, we have the coarse upper bounds

$1\leq\frac{\exp((t^{2}-t)/(2\sigma^{2}))}{\exp((3^{2}-3)/(2\sigma^{2}))}\mbox{
and
}1\leq\frac{(1-q)2^{t}\exp((t^{2}-t)/(2\sigma^{2}))t^{t}}{(1-q)2^{3}\exp((3^{2}-3)/(2\sigma^{2}))3^{3}}.$

By defining $c$ as $1$ plus the maximum of these two bounds,

$c=1+\frac{\max\left\\{1,1/((1-q)\cdot 216)\right\\}}{\exp(3/\sigma^{2})},$

we have (10) at most

$\leq\frac{(2q)^{t}(t-1)!!c\exp((t^{2}-t)/(2\sigma^{2}))}{2(1-q)^{t-1}\sigma^{t}}+\frac{q^{t}c(1-q)2^{t}\exp((t^{2}-t)/(2\sigma^{2}))t^{t}}{2(1-q)^{t}\sigma^{2t}}.$
(11)

Generally (for practical parameter settings as we will find out), $q\leq
1-1/216$ which makes $c\leq 2$. In the remainder of this proof, we use $c=2$
and assume $q\leq 215/216$. In fact, assume in the statement of the lemma that
$\sigma=\sigma_{i}\geq 216/215$ which together with $q=s_{i}/N\leq
r_{0}/\sigma_{i}$ and $r_{0}<1$ implies $q\leq 215/216$.

After multiplying (11) with the upper bound for

${\lambda+1\choose t}\leq\frac{\lambda+1}{\lambda}\frac{\lambda^{t}}{t!}$

and noticing that $(t-1)!!/t!\leq 1$ and $t^{t}/t!\leq e^{t}$ we get the
addition of the following two terms

$\displaystyle\frac{\lambda+1}{\lambda}\frac{\lambda^{t}(2q)^{t}\exp((t^{2}-t)/(2\sigma^{2}))}{(1-q)^{t-1}\sigma^{t}}+\frac{\lambda+1}{\lambda}\frac{\lambda^{t}q^{t}(1-q)2^{t}\exp((t^{2}-t)/(2\sigma^{2}))e^{t}}{(1-q)^{t}\sigma^{2t}}.$

This is equal to

$\displaystyle(1-q)\frac{\lambda+1}{\lambda}\left(\frac{\lambda
2q\exp((t-1)/(2\sigma^{2}))}{(1-q)\sigma}\right)^{t}$ $\displaystyle\hskip
56.9055pt+(1-q)\frac{\lambda+1}{\lambda}\left(\frac{\lambda
q2\exp(1+(t-1)/(2\sigma^{2}))}{(1-q)\sigma^{2}}\right)^{t}.$ (12)

We notice that by using $t\leq\lambda+1$,
$\lambda/\sigma^{2}\leq\ln(1/(q\sigma))$ (assumption), and
$q=s_{i,c}/N_{c}\leq r_{0}/\sigma$ we obtain

$\displaystyle\frac{\lambda 2q\exp((t-1)/(2\sigma^{2}))}{(1-q)\sigma}$
$\displaystyle\leq$ $\displaystyle\frac{\lambda
2q\exp(\lambda/(2\sigma^{2}))}{(1-q)\sigma}\leq\frac{2\sqrt{\lambda
q}}{(1-q)\sigma}=\frac{2\sqrt{\lambda r_{0}/\sigma}}{\sigma-
r_{0}}=U_{0}(\lambda)$

and

$\displaystyle\frac{\lambda q2\exp(1+(t-1)/(2\sigma^{2}))}{(1-q)\sigma^{2}}$
$\displaystyle\leq$ $\displaystyle\frac{\lambda
q2e\exp(\lambda/(2\sigma^{2}))}{(1-q)\sigma^{2}}\leq\frac{2e\sqrt{\lambda
q}}{(1-q)\sigma^{2}}=\frac{2e\sqrt{\lambda r_{0}/\sigma}}{(\sigma-
r_{0})\sigma}=U_{1}(\lambda).$

Together with our assumption on $U_{0}(\lambda)$ and $U_{1}(\lambda)$, this
means that the binomial tail (9) is upper bounded by the two terms in (12)
after substituting $t=3$, with the two terms multiplied by

$\sum_{j=0}^{\infty}U_{0}(\lambda)^{j}=\frac{1}{1-U_{0}(\lambda)}\leq\frac{1}{1-u_{0}}\mbox{
and
}\sum_{j=0}^{\infty}U_{1}(\lambda)^{j}=\frac{1}{1-U_{1}(\lambda)}\leq\frac{1}{1-u_{1}}$

respectively. For (9) this yields the upper bound

$\displaystyle\frac{1}{1-u_{0}}(1-q)\frac{\lambda+1}{\lambda}\left(\frac{\lambda
2q\exp(1/\sigma^{2})}{(1-q)\sigma}\right)^{3}+\frac{1}{1-u_{1}}(1-q)\frac{\lambda+1}{\lambda}\left(\frac{\lambda
q2\exp(1+1/\sigma^{2})}{(1-q)\sigma^{2}}\right)^{3}$ $\displaystyle\leq$
$\displaystyle\left(\frac{1}{1-u_{0}}2^{3}\exp(3/\sigma^{2})+\frac{1}{1-u_{1}}\frac{2^{3}\exp(3+3/\sigma^{2})}{\sigma^{3}}\right)\cdot\frac{\lambda^{2}(\lambda+1)q^{3}}{(1-q)^{2}\sigma^{3}}.$

By the definition of $r$, we obtain the bound

$\displaystyle\leq$
$\displaystyle\frac{r}{r_{0}}\cdot\frac{\lambda^{2}(1+\lambda)q^{3}}{(1-q)^{2}\sigma^{3}},$

which finalizes the proof.

####  B.2.2 Proof of Theorem 3

The proof Theorem 3 follows the line of thinking in the proof of Theorem 1 in
[1]. Our theorem applies to varying sample/batch sizes and for this reason
introduces moments $\hat{S}_{j}$. Our theorem explicitly defines the constant
used in the lower bound of $\sigma$ – this is important for proving our second
(main) theorem in the next subsection.

Theorem 3 assumes $\sigma=\sigma_{i}$ for all rounds $i$ with $\sigma\geq
216/215$; constant $r_{0}\leq 1/e$ such that $s_{i}/N\leq r_{0}/\sigma$;
constant

$\displaystyle r$ $\displaystyle=$ $\displaystyle r_{0}\cdot
2^{3}\left(\frac{1}{1-u_{0}}+\frac{1}{1-u_{1}}\frac{e^{3}}{\sigma^{3}}\right)\exp(3/\sigma^{2}),$
(13)

where

$u_{0}=\frac{2\sqrt{r_{0}\sigma}}{\sigma-r_{0}}\mbox{ and
}u_{1}=\frac{2e\sqrt{r_{0}\sigma}}{(\sigma-r_{0})\sigma}$

are both assumed $<1$.

For $j=1,2,3$ we define666$s_{i}^{j}$ denotes the $j$-th power $(s_{i})^{j}$.

$\hat{S}_{j}=\frac{1}{T}\sum_{i=0}^{T-1}\frac{s_{i}^{j}}{N(N-s_{i})^{j-1}}\mbox{
with }\frac{\hat{S}_{1}\hat{S}_{3}}{\hat{S}_{2}^{2}}\leq\rho,\
\frac{\hat{S}_{1}^{2}}{\hat{S}_{2}}\leq\hat{\rho}.$

Based on these constants we define

$c(x)=\min\left\\{\frac{\sqrt{2r\rho x+1}-1}{r\rho
x},\frac{2}{\hat{\rho}x}\right\\}.$

Let $\epsilon=c_{1}T\hat{S}_{1}^{2}$. We want to prove Algorithm 4 is
$(\epsilon,\delta)$-differentially private if

$\sigma\geq\frac{2}{\sqrt{c_{0}}}\frac{\sqrt{\hat{S}_{2}T(\epsilon+\ln(1/\delta))}}{\epsilon}\mbox{
where }c_{0}=c(c_{1}).$

Proof. For $j=1,2,3$, we define

$S_{j}=\sum_{i=0}^{T-1}\frac{s_{i}^{j}}{N(N-s_{i})^{j-1}\sigma_{i}^{j}}\mbox{
and
}S^{\prime}_{j}=\frac{1}{T}\sum_{i=0}^{T-1}\frac{s_{i}^{j}\sigma_{i}^{j}}{N(N-s_{i})^{j-1}}.$

(Notice that $S^{\prime}_{1}\leq r_{0}$.) Translating Lemma 1 in this notation
yields (we will verify the requirement/assumptions of Lemma 1 on the fly
below)

$\sum_{i=0}^{T-1}\alpha_{i}(\lambda)\leq
S_{2}\lambda(\lambda+1)+\frac{r}{r_{0}}S_{3}\lambda^{2}(\lambda+1).$

The composition Theorem 2 in [1] shows that our algorithm for client $c$ is
$(\epsilon,\delta)$-differentially private for

$\displaystyle\delta$ $\displaystyle\geq$
$\displaystyle\min_{\lambda}\exp\left(\sum_{i=0}^{T-1}\alpha_{i}(\lambda)-\lambda\epsilon\right),$

where $T$ indicates the total number of batch computations and the minimum is
over positive integers $\lambda$. Similar to their proof we choose $\lambda$
such that

$S_{2}\lambda(\lambda+1)+\frac{r}{r_{0}}S_{3}\lambda^{2}(\lambda+1)-\lambda\epsilon\leq-\lambda\epsilon/2.$
(14)

This implies that we can choose $\delta$ as small as
$\exp(-\lambda\epsilon/2)$, i.e., if

$\delta\geq\exp(-\lambda\epsilon/2),$ (15)

then we have $(\epsilon,\delta)$-differential privacy. After dividing by the
positive integer $\lambda$, inequality (14) is equivalent to the inequality

$S_{2}(\lambda+1)+\frac{r}{r_{0}}S_{3}\lambda(1+\lambda)\leq\epsilon/2,$

which is equivalent to

$(\lambda+1)\left(1+\frac{r}{r_{0}}\frac{S_{3}}{S_{2}}\lambda\right)\leq\frac{\epsilon}{2S_{2}}.$

This is in turn implied by

$\lambda+1\leq c_{0}\frac{\epsilon}{2S_{2}}$ (16)

together with

$c_{0}\frac{\epsilon}{2S_{2}}\left(1+\frac{r}{r_{0}}\frac{S_{3}}{S_{2}}c_{0}\frac{\epsilon}{2S_{2}}\right)\leq\frac{\epsilon}{2S_{2}},$

or equivalently,

$c_{0}\left(1+\frac{r}{2r_{0}}\cdot
c_{0}\cdot\frac{S_{3}}{S_{2}^{2}}\epsilon\right)\leq 1.$ (17)

We use

$\epsilon=c_{1}\cdot T\hat{S}_{1}^{2}=c_{1}\cdot S_{1}S^{\prime}_{1}$ (18)

(for constant $\sigma_{i}=\sigma$). This translates our requirements (16) and
(17) into

$\lambda+1\leq\frac{c_{0}c_{1}}{2}\frac{S_{1}S^{\prime}_{1}}{S_{2}}\mbox{ and
}$ (19) $c_{0}\left(1+\frac{r}{2r_{0}}\cdot
c_{0}c_{1}\frac{S_{1}S_{3}}{S_{2}^{2}}S^{\prime}_{1}\right)\leq 1.$ (20)

Since we assume

$\frac{S_{1}S_{3}}{S_{2}^{2}}=\frac{\hat{S}_{1}\hat{S}_{3}}{\hat{S}_{2}^{2}}\leq\rho$

and since we know that $S^{\prime}_{1}\leq r_{0}$, requirement (20) is implied
by

$c_{0}(1+\frac{r\rho}{2}\cdot c_{0}c_{1})\leq 1,$

or equivalently

$c_{1}\leq\frac{1-c_{0}}{\frac{r\rho}{2}c_{0}^{2}}.$ (21)

Also notice that for constant $\sigma_{i}=\sigma$ we have
$S^{\prime}_{1}=S_{1}\sigma^{2}/T$. Together with

$\frac{S_{1}^{2}}{S_{2}}=\frac{\hat{S}_{1}^{2}}{\hat{S}_{2}}T\leq\hat{\rho}T$

we obtain from (19)

$\lambda+1\leq\frac{c_{0}c_{1}}{2}\frac{S_{1}S^{\prime}_{1}}{S_{2}}\leq\frac{c_{0}c_{1}}{2}\hat{\rho}\sigma^{2}.$
(22)

Generally, if

$c_{1}\leq\frac{2}{\hat{\rho}c_{0}},$ (23)

then (22) implies $\lambda\leq\sigma^{2}$: Hence, (a) for our choice of
$u_{0}$ and $u_{1}$ in this theorem, $U_{0}(\lambda)\leq u_{0}$ and
$U_{1}(\lambda)\leq u_{1}$ as defined in Lemma 1, and (b) the condition
$\lambda\leq\sigma_{i}^{2}\ln\frac{N_{c}}{s_{i,c}\sigma_{i}}$ is satisfied (by
assumption, $\frac{N_{c}}{s_{i,c}\sigma_{i}}\geq 1/r_{0}\geq e$). This implies
that Lemma 1 is indeed applicable.

For the above reasons we strengthen the requirement on $\epsilon$ (conditions
(21) and (23) with (18)) to

$\epsilon\leq\min\left\\{\frac{1-c_{0}}{\frac{r\rho}{2}c_{0}^{2}},\frac{2}{\hat{\rho}c_{0}}\right\\}\cdot
S_{1}S^{\prime}_{1}$

For constant $\sigma_{i}=\sigma$, we have

$S_{1}S^{\prime}_{1}=T\hat{S}_{1}^{2},$

hence, we need

$\epsilon\leq\min\left\\{\frac{1-c_{0}}{\frac{r\rho}{2}c_{0}^{2}},\frac{2}{\hat{\rho}c_{0}}\right\\}\cdot
T\hat{S}_{1}^{2}$ (24)

Summarizing (24), (16), and (15) for some positive integer $\lambda$ proves
$(\epsilon,\delta)$-differential privacy.

Condition (15) (i.e., $\exp(-\lambda\epsilon/2)\leq\delta$) is equivalent to

$\ln(1/\delta)\leq\frac{\lambda\epsilon}{2}$ (25)

If

$\lambda=\lfloor c_{0}\frac{\epsilon}{2S_{2}}\rfloor-1$ (26)

is positive, then it satisfies (16) and we may use this $\lambda$ in (25).
This yields the condition

$\ln(1/\delta)\leq\left(\lfloor
c_{0}\frac{\epsilon}{2S_{2}}\rfloor-1\right)\frac{\epsilon}{2},$

which is implied by

$\ln(1/\delta)\leq\left(c_{0}\frac{\epsilon}{2S_{2}}-2\right)\frac{\epsilon}{2}=\frac{c_{0}}{4S_{2}}\epsilon^{2}-\epsilon.$

For constant $\sigma_{i}=\sigma$ we have $S_{2}=\hat{S}_{2}T/\sigma^{2}$ and
the latter inequality is equivalent to

$\sigma\geq\frac{2}{\sqrt{c_{0}}}\frac{\sqrt{\hat{S}_{2}}\sqrt{T(\epsilon+\ln(1/\delta))}}{\epsilon}.$
(27)

Summarizing, if (24), (27), and the lambda value (26) is positive, then this
shows $(\epsilon,\delta)$-differential privacy.

The condition (26) being positive follows from

$\frac{4S_{2}}{c_{0}}\leq\epsilon.$

Substituting $S_{2}=\hat{S}_{2}T/\sigma^{2}$ yields the equivalent condition

$\frac{4T\hat{S}_{2}}{\sigma^{2}c_{0}}\leq\epsilon$

or

$\sigma\geq\frac{2}{\sqrt{c_{0}}}\sqrt{\hat{S}_{2}}\frac{\sqrt{T\epsilon}}{\epsilon},$

which is implied by (27). Summarizing, if (24) and (27), then this shows
$(\epsilon,\delta)$-differential privacy. Notice that (27) corresponds to
Theorem 1 in [1] where all $s_{i}$ are constant implying
$\sqrt{\hat{S}_{2}}=q/\sqrt{1-q}$ in their notation.

We are interested in a slightly different formulation: Given

$c_{1}=\min\left\\{\frac{1-c_{0}}{\frac{r\rho}{2}c_{0}^{2}},\frac{2}{\hat{\rho}c_{0}}\right\\}$

what is the maximum possible $c_{0}$ (which minimizes $\sigma$ implying more
fast convergence to an accurate solution). We need to satisfy $c_{0}\leq
2/(\hat{\rho}c_{1})$ and

$\frac{r\rho}{2}c_{1}c_{0}^{2}+c_{0}-1\leq 0,$

that is,

$(c_{0}+1/(r\rho c_{1}))^{2}\leq 1/\left(\frac{r\rho}{2}c_{1}\right)+1/(r\rho
c_{1})^{2},$

or

$c_{0}\leq\sqrt{1/\left(\frac{r\rho}{2}c_{1}\right)+1/\left(r\rho
c_{1}\right)^{2}}-1/(r\rho c_{1})=\frac{\sqrt{2r\rho c_{1}+1}-1}{r\rho
c_{1}}.$

We have

$c_{0}=\min\left\\{\frac{\sqrt{2r\rho c_{1}+1}-1}{r\rho
c_{1}},2/(\hat{\rho}c_{1})\right\\}=c(c_{1}).$

This finishes the proof.

###  B.3 A Simplified Characterization

So far, we have generalized Theorem 2 in Appendix B in a non-trivial way by
analysing increasing sample size sequences, by making explicit the higher
order error term in [1], and by providing a precise functional relationship
among the constants $c_{1}$ and $c_{2}$ in Theorem 2. The resulting Theorem 3
is still hard to interpret. The next theorem is a consequence of Theorem 3 and
brings us the interpretation we look for.

######  Theorem 4.

For sample size sequence $\\{s_{i}\\}_{i=0}^{T-1}$ the total number of local
SGD iterations is equal to $K=\sum_{i=0}^{T-1}s_{i}$. We define the mean
$\bar{s}$ and maximum $s_{max}$ and their quotient $\theta$ as

$\displaystyle\bar{s}=\frac{1}{T}\sum_{i=0}^{T-1}s_{i}=\frac{K}{T},\ \
s_{max}=\max\\{s_{0},\ldots,s_{T-1}\\},\ \mbox{ and }\ \
\theta=\frac{s_{max}}{\bar{s}}.$

We define

$\displaystyle h(x)$ $\displaystyle=\left(\sqrt{1+(e/x)^{2}}-e/x\right)^{2},\
\ g(x)=\min\left\\{\frac{1}{ex},h(x)\right\\},$

and denote by $\gamma$ the smallest solution satisfying

$\displaystyle\gamma\geq\frac{2}{1-\bar{\alpha}}+\frac{2^{4}\cdot\bar{\alpha}}{1-\bar{\alpha}}\left(\frac{\sigma}{(1-\sqrt{\bar{\alpha}})^{2}}+\frac{1}{\sigma(1-\bar{\alpha})-2e\sqrt{\bar{\alpha}}}\frac{e^{3}}{\sigma}\right)e^{3/\sigma^{2}}\mbox{
with }\bar{\alpha}=\frac{\epsilon N}{\gamma K}.$

If the following requirements are satisfied:

$\displaystyle\bar{s}$ $\displaystyle\leq$
$\displaystyle\frac{g\left(\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}\right)}{\theta}\cdot
N,$ (28) $\displaystyle\epsilon$ $\displaystyle\leq$ $\displaystyle\gamma
h(\sigma)\cdot\frac{K}{N},$ (29) $\displaystyle\epsilon$ $\displaystyle\geq$
$\displaystyle\gamma\theta^{2}\cdot\frac{K}{N}\cdot\frac{\bar{s}}{N},\mbox{
and}$ (30) $\displaystyle\sigma$ $\displaystyle\geq$
$\displaystyle\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon},$ (31)

then Algorithm 4 is $(\epsilon,\delta)$-differentially private.

Its proof follows from analysing the requirements stated in Theorem 3. We will
focus on the case where $c(x)=\frac{2}{\hat{\rho}x}$, which turns out to lead
to practical parameter settings as discussed in the main body of the paper.

Requirement on $r$ – (34): In Theorem 3 we use

$r=r_{0}\cdot
2^{3}\cdot\left(\frac{1}{1-u_{0}}+\frac{1}{1-u_{1}}\frac{e^{3}}{\sigma^{3}}\right)e^{3/\sigma^{2}}$

with

$u_{0}=\frac{2\sqrt{r_{0}\sigma}}{\sigma-r_{0}}\mbox{ and
}u_{1}=\frac{2e\sqrt{r_{0}\sigma}}{(\sigma-r_{0})\sigma},$

where $r_{0}$ is such that it satisfies

$r_{0}\leq 1/e,\ u_{0}<1,\mbox{ and }u_{1}<1.$ (32)

In our application of Theorem 3 we substitute $r_{0}=\alpha\sigma$. This
translates the requirements of (32) into

$\alpha\leq\frac{1}{e\sigma},\ \alpha<1,\mbox{ and
}\sigma>\frac{2e\sqrt{\alpha}}{1-\alpha}.$ (33)

As we will see in our derivation, we will require another lower bound (38) on
$\sigma$. We will use (38) together with

$\alpha\leq\frac{1}{e\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}},\alpha<1,\mbox{
and
}\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}>\frac{2e\sqrt{\alpha}}{1-\alpha}$

to imply the needed requirement (33). These new bounds on $\alpha$ are in turn
equivalent to

$\displaystyle\alpha\leq g(\epsilon,\delta)\mbox{ where }$ (34) $\displaystyle
g(\epsilon,\delta)=\min\left\\{\frac{\sqrt{\epsilon}}{e\sqrt{2(\epsilon+\ln(1/\delta))}},\left(\sqrt{1+\frac{e^{2}\epsilon}{2(\epsilon+\ln(1/\delta))}}-\frac{e\sqrt{\epsilon}}{\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}}\right)^{2}\right\\}$

(notice that this implies $\alpha<1$).

Substituting $r_{0}=\alpha\sigma$ in the formula for $r$ yields the expression

$\displaystyle r$ $\displaystyle=$ $\displaystyle
2^{3}\cdot\left(\frac{\sigma}{(1-\sqrt{\alpha})^{2}}+\frac{1}{\sigma(1-\alpha)-2e\sqrt{\alpha}}\frac{e^{3}}{\sigma}\right)\cdot
e^{3/\sigma^{2}}(1-\alpha)\alpha.$ (35)

Requirement on $s_{i}/N$ – (36): In Theorem 3 we also require $s_{i}/N\leq
r_{0}/\sigma$ which translates into

$s_{i}/N\leq\alpha.$ (36)

Requirement on $\sigma$ – (38) and (39): In Theorem 3 we restrict ourselves to
the case where function $c(x)$ attains the minimum $c(x)=2/(\hat{\rho}x)$.
This happens when

$\frac{\sqrt{2r\rho x+1}-1}{r\rho x}\geq\frac{2}{\hat{\rho}x}.$

This is equivalent to

$x\geq 2r\frac{\rho}{\hat{\rho}^{2}}+\frac{2}{\hat{\rho}}.$ (37)

Notice that in the lower bound for $\sigma$ in Theorem 3 we use $c_{0}=c(x)$
for $x=c_{1}$, where $c_{1}$ is implicitly defined by

$\epsilon=c_{1}T\hat{S}_{1}^{2}$

or equivalently

$c_{1}=\frac{\epsilon}{T\hat{S}_{1}^{2}}.$

To minimize $\epsilon$, we want to minimize $c_{1}=x$. That is, we want
$c_{1}=x$ to match the lower bound (37). This lower bound is smallest if we
choose the smallest possible $\rho$ (due to the linear dependency of the lower
bound on $\rho$). Given the constraint on $\rho$ this means we choose

$\rho=\frac{\hat{S}_{1}\hat{S}_{3}}{\hat{S}_{2}^{2}}.$

For $c_{1}=x$ satisfying (37) we have

$c_{0}=c(c_{1})=\frac{2}{\hat{\rho}x}.$

Substituting this in the lower bound for $\sigma$ attains

$\sigma\geq\frac{2}{\sqrt{c(c_{1})}}\frac{\sqrt{\hat{S}_{2}T(\epsilon+\ln(1/\delta))}}{\epsilon}=\sqrt{\frac{\hat{\rho}\hat{S}_{2}}{\hat{S}_{1}^{2}}}\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}.$

In order to yield the best test accuracy we want to choose the smallest
possible $\sigma$. Hence, we want to minimize the lower bound for $\sigma$ and
therefore choose the smallest $\hat{\rho}$ given its constraints, i.e.,

$\hat{\rho}=\frac{\hat{S}_{1}^{2}}{\hat{S}_{2}}.$

This gives

$\sigma\geq\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}.$ (38)

Notice that this lower bound implies $\sigma\geq 216/215$ and for this reason
we do not state this as an extra requirement.

Our expressions for $\rho$, $\hat{\rho}$, and $c_{1}$ with $x=c_{1}$ shows
that lower bound (37) holds if and only if

$\epsilon\geq\left(2r\frac{\hat{S}_{3}}{\hat{S}_{1}}+2\hat{S}_{2}\right)T.$
(39)

Requirement implying (39): The definition of moments $\hat{S}_{j}$ imply

$\hat{S}_{1}=\frac{K}{TN}$

and, since $s_{i}/N\leq\alpha<1$,

$\hat{S}_{j}\leq\alpha^{j}/(1-\alpha)^{j-1}.$

Lower bound (39) on $\epsilon$ is therefore implied by

$\epsilon\geq
2r\frac{\alpha^{3}}{(1-\alpha)^{2}}\frac{T^{2}N}{K}+2\frac{\alpha^{2}}{1-\alpha}T.$
(40)

We substitute

$T=\beta\frac{K}{N}$ (41)

in (40) which yields the requirement

$\epsilon\frac{N}{K}\geq\frac{2r}{\alpha(1-\alpha)^{2}}(\alpha^{2}\beta)^{2}+\frac{2}{1-\alpha}(\alpha^{2}\beta).$
(42)

This inequality is implied by the combination of the following two
inequalities:

$\alpha^{2}\beta\leq\frac{\epsilon N}{\gamma K}$ (43)

and

$1\geq\frac{2r}{\alpha(1-\alpha)^{2}}\frac{\epsilon
N}{K}\frac{1}{\gamma^{2}}+\frac{2}{1-\alpha}\frac{1}{\gamma}.$ (44)

Inequality (44) is equivalent to

$\gamma\geq\frac{2r}{\alpha(1-\alpha)^{2}}\frac{\epsilon N}{\gamma
K}+\frac{2}{1-\alpha}.$ (45)

This implies

$\gamma\geq\frac{2}{1-\alpha}\geq 2.$

Also notice that

$\frac{1}{\beta}=\frac{K}{TN}=\hat{S}_{1}\leq\alpha$

from which we obtain

$1\leq\alpha\beta.$

Let us define

$\bar{\alpha}=\frac{\epsilon N}{\gamma K}.$ (46)

Inequalities $\gamma\geq 2$ and $1\leq\alpha\beta$ together with (43) and the
definition of $\bar{\alpha}$ imply

$\alpha\leq\alpha^{2}\beta\leq\frac{\epsilon N}{\gamma
K}=\bar{\alpha}\leq\frac{\epsilon N}{2K}.$ (47)

We will require

$\bar{\alpha}<1$ (48)

and also $\sigma(1-\bar{\alpha})-2e\sqrt{\bar{\alpha}}>0$ i.e,

$\sigma>\frac{2e\sqrt{\bar{\alpha}}}{1-\bar{\alpha}}.$ (49)

Bounds (48) and (49) are equivalent to

$\bar{\alpha}\leq h(\sigma)\mbox{ where
}h(\sigma)=\left(\sqrt{1+(e/\sigma)^{2}}-e/\sigma\right)^{2}.$ (50)

With condition (50) in place we may derive the upper bound

$\displaystyle\frac{2r}{\alpha(1-\alpha)^{2}}$ $\displaystyle=$
$\displaystyle\frac{2^{4}}{1-\alpha}\left(\frac{\sigma}{(1-\sqrt{\alpha})^{2}}+\frac{1}{\sigma(1-\alpha)-2e\sqrt{\alpha}}\frac{e^{3}}{\sigma}\right)e^{3/\sigma^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{2^{4}}{1-\bar{\alpha}}\left(\frac{\sigma}{(1-\sqrt{\bar{\alpha}})^{2}}+\frac{1}{\sigma(1-\bar{\alpha})-2e\sqrt{\bar{\alpha}}}\frac{e^{3}}{\sigma}\right)e^{3/\sigma^{2}}$

because all denominators are decreasing functions in $\alpha$ and remain
positive for $\alpha\leq\bar{\alpha}$. Similarly,

$\frac{2}{1-\alpha}\leq\frac{2}{1-\bar{\alpha}}.$

These two upper bounds combined with (46) show that (45) is implied by
choosing

$\gamma=\gamma(\sigma,\epsilon N/K),$

where $\gamma(\sigma,\epsilon N/K)$ is defined as the smallest solution of
$\gamma$ satisfying

$\displaystyle\gamma$ $\displaystyle\geq\frac{2}{1-\bar{\alpha}}+$
$\displaystyle\frac{2^{4}\cdot\bar{\alpha}}{1-\bar{\alpha}}\left(\frac{\sigma}{(1-\sqrt{\bar{\alpha}})^{2}}+\frac{1}{\sigma(1-\bar{\alpha})-2e\sqrt{\bar{\alpha}}}\frac{e^{3}}{\sigma}\right)e^{3/\sigma^{2}},$

where $\bar{\alpha}=(\epsilon N/K)/\gamma$. The smallest solution $\gamma$
will meet (B.3) with equality. For this reason the minimal solution $\gamma$
will be at most the right hand side of (B.3) where $\gamma$ is replaced by its
lower bound $2$; this is allowed because this increases $\bar{\alpha}$ to the
upper bound in (47) and we know that the right hand side of (B.3) increases in
$\bar{\alpha}$ up to the upper bound in (47) if the upper bound satisfies

$\frac{\epsilon N}{2K}\leq h(\sigma).$

This makes requirement (50) slightly stronger – but in practice this stronger
requirement is already satisfied because $K$ is several epochs of $N$
iterations making $\frac{\epsilon N}{2K}\ll 1$ while $\sigma\gg 1$ for small
$\epsilon$ implying that $h(\sigma)$ is close to $1$.

Notice that $\gamma=2+O(\bar{\alpha})$, hence, for small $\bar{\alpha}$ we
have $\gamma\approx 2$. A more precise asymptotic analysis reveals

$\gamma=2+(2+2^{4}\cdot\left(\sigma+\frac{e^{3}}{\sigma^{2}}\right)e^{3/\sigma^{2}})\bar{\alpha}+O(\bar{\alpha}^{3/2}).$

Relatively large $\bar{\alpha}$ closer to $1$ will yield $\gamma\gg 2$.

Summarizing

$\\{(\ref{Tbeta}),(\ref{loweps3a}),(\ref{baradef}),(\ref{bara3}),(\ref{gamma})\\}\Rightarrow(\ref{loweps}).$

Combining all requirements – resulting in (53), (54), and (38), or
equivalently (56), (57), and (38): The combination of requirements (41) and
(43) is equivalent to

$\alpha\leq\sqrt{\frac{\epsilon}{\gamma T}}$ (52)

(notice that $T$ and $\beta$ are not involved in any of the other requirements
including those discussed earlier in this discussion, hence, we can discard
(41) and substitute this in (43)). The combination of (46), (50), and (B.3) is
equivalent to

$\frac{\epsilon N}{\gamma K}\leq h(\sigma)\mbox{ with
}\gamma=\gamma\left(\sigma,\frac{\epsilon N}{K}\right)$ (53)

(for the definition of $h(.)$ see (50) and for $\gamma(.,.)$ see (B.3)).

We may now combine (52), (34), and (36) into a single requirement

$s_{i}/N\leq\min\left\\{g(\epsilon,\delta),\sqrt{\frac{\epsilon}{\gamma
T}}\right\\}$ (54)

(for the definition of $g(.,.)$ see (34)). This shows that (53), (54), and
(38) (we remind the reader that the last condition is the lower bound on
$\sigma\geq\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$) implies
$(\epsilon,\delta)$-DP by Theorem 3.

Let us rewrite these conditions. We introduce the mean $\bar{s}$ of all
$s_{i}$ defined by

$\bar{s}=\frac{1}{T}\sum_{i=0}^{T-1}s_{i}=\frac{K}{T}$

and we introduce the maximum $s_{max}$ of all $s_{i}$ defined by

$s_{max}=\max\\{s_{0},\ldots,s_{T-1}\\}.$

We define $\theta$ as the fraction

$\theta=\frac{s_{max}}{\bar{s}}.$ (55)

This notation allows us to rewrite

$s_{i}/N\leq\sqrt{\frac{\epsilon}{\gamma T}}$

from (54) as

$\gamma\frac{K}{N}\frac{\bar{s}}{N}\theta^{2}\leq\epsilon.$

From this we obtain that the requirements (53) and (54) are equivalent to

$\gamma\left(\sigma,\frac{\epsilon
N}{K}\right)\cdot\frac{K}{N}\frac{\bar{s}}{N}\theta^{2}\leq\epsilon\leq\gamma\left(\sigma,\frac{\epsilon
N}{K}\right)\cdot h(\sigma)\frac{K}{N}$ (56)

and

$\theta\bar{s}\leq g(\epsilon,\delta)N.$ (57)

This alternative description shows that (56), (57), and (38) with definitions
for $h(.)$, $\gamma(.,.)$, $g(.,.)$, and $\theta$ in (50), (B.3), (34), and
(55) implies $(\epsilon,\delta)$-DP. This proves Theorem 4 (after a slight
rewrite of the definitions of functions $h(.)$ and $g(.,.)$).

###  B.4 Proof of the Main Theorem

Theorem 4 can already be used to a-priori set hyperparameters given DP and
accuracy targets. Still, as discussed below, by making slight approximations
(leading to slightly stronger constraints) we obtain the easy to interpret
Theorem 1 discussed in Section 3.

We set $\sigma$ as large as possible with respect to the accuracy we wish to
have. Given this $\sigma$ we want to max out on our privacy budget. That is,
we satisfy (31) with equality,

$\sigma=\sqrt{\frac{2(\epsilon+\ln(1/\delta))}{\epsilon}}.$ (58)

We discuss (58) with constraints (28), (29), and (30) below:

Replacing (28) and (29): In practice, we need a sufficiently strong DP
guarantee, hence, $\delta\leq 1/N$ and $\epsilon$ is small enough, typically
$\leq 0.5$. This means that we will stretch $\sigma$ to at least $\sqrt{2+4\ln
N}$. A local data set of size $N=10000$ requires $\sigma\geq 6.23$; a local
data set of size $N=100000$ requires $\sigma\geq 6.93$. For such $\sigma\geq
6$ we have $h(\sigma)\geq h(6)=0.42$ (since $h(\sigma)$ is increasing in
$\sigma$). (For reference, $h(10)=0.58$, and for $\sigma\gg 1$ we have
$h(\sigma)\approx 1$.) From (58) we infer that
$g(\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon})=g(\sigma)=\min\\{1/(e\sigma),h(\sigma)\\}$.
One can verify that $h(\sigma)-1/(e\sigma)$ is positive and increasing for
$\sigma\geq 2.5$, hence, $g(\sigma)=1/(e\sigma)$ for $\sigma\geq 6$. This
reduces requirement (28) to $\bar{s}\leq N/(e\sigma\theta)$ and requirement
(29) to $\epsilon\leq 0.42\cdot\gamma K/N$. Notice that (30) in combination
with $\epsilon\leq\frac{\gamma\theta}{e\sigma}K/N$ implies condition
$\bar{s}\leq N/(e\sigma\theta)$. This implies that (28) and (29) are satisfied
for
$\epsilon\leq\min\\{0.42\cdot\gamma,\gamma\theta/(e\sigma)\\}\cdot\frac{K}{N}$
or, equivalently,
$K\geq\epsilon\cdot\max\\{2.4/\gamma,e\sigma/(\gamma\theta)\\}$ epochs of size
$N$. If $\theta\leq 6.85$, then $\sigma\geq 6\geq
0.88\cdot\theta=2.4\cdot\theta/e$, hence,
$\max\\{2.4/\gamma,e\sigma/(\gamma\theta)\\}=e\sigma/(\gamma\theta)$ and this
reduces the condition on $K$ to

$K\geq\epsilon\sigma\cdot\frac{e}{\gamma\theta}=\sqrt{2\epsilon(\epsilon+\ln(1/\delta))}\cdot
e/(\gamma\theta)\mbox{ epochs of size }N,$

where the equality follows from (58). In practical settings, $K$ consists of
multiple (think 50 or 100s of) epochs (of size $N$) computation and this is
generally true. We conclude that (28) and (29) are automatically satisfied by
(30) for general practical settings with $\delta\leq 1/N$, $\epsilon$
typically smaller than $0.5$, $N\geq 10000$, $\theta\leq 6.85$, and
$K\geq\sqrt{2\epsilon(\epsilon+\ln(1/\delta))}\cdot e/(\gamma\theta)$ epochs.

Remaining constraint (30): By using (58), (30) can be equivalently recast as
an upper bound on $\sigma$,

$\sigma\leq\sqrt{\frac{2(\epsilon+\ln(1/\delta))}{\gamma\theta^{2}\cdot(K/N)\cdot(\bar{s}/N)}}.$

Here, $\gamma$ is a function of $\sigma$ because $\gamma$ depends on
$\epsilon$ in $\bar{\alpha}$ which is a function of $\sigma$ through (58).
However, the definition of $\gamma$ shows that for small $\epsilon$, $\gamma$
is close to 2 and this gives
$\sqrt{\ln(1/\delta)/(\theta^{2}\cdot(K/N)\cdot(\bar{s}/N))}$ as a good
approximation of the upper bound. Substituting $\bar{s}=K/T$ yields

$\sigma\leq\frac{N\sqrt{T}}{K}\sqrt{\frac{2(\epsilon+\ln(1/\delta))}{\gamma\theta^{2}}}.$
(59)

For $\gamma\approx 2$ and $\theta=1$ (constant sample size), this upper bound
compares to taking $c_{2}z\approx\sqrt{2}$ in (7); we go beyond the analysis
presented in [1] in a non-trivial way.

If $N\sqrt{T}/K$ is large enough, larger than the relatively small
$\sigma\sqrt{\theta^{2}(\gamma/2)/(\epsilon+\ln(1/\delta))}$, then upper bound
(59) is satisfied. That is, for given $K$ and $N$, we need $T$ to be large
enough, or equivalently the mean sample/mini-batch size $\bar{s}=K/T$ small
enough. Squaring both sides of (59) and moving terms yields the equivalent
lower bound

$T\geq\frac{\gamma}{2}\frac{\sigma^{2}\theta^{2}}{\epsilon+\ln(1/\delta)}\cdot(K/N)^{2},$

which after substituting (58) gives

$T\geq\frac{\gamma\theta^{2}}{\epsilon}\cdot(K/N)^{2}.$

In other words $T$ is at least a factor $\gamma\theta^{2}/\epsilon$ larger
than the square of the overall amount of local SGD computations measured in
epochs (of size $N$). Notice that we have a lower bound on $T$ rather than an
upper bound as in (8) from the theorem presented in [1].

##  Appendix C Tight Analysis using Gaussian DP

[5] explain an elegant alternative 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}.$

We define the Type I and Type II errors by

$\alpha_{\phi}=\textbf{E}_{o\sim{\cal M}(d)}[\phi(o)]\mbox{ and
}\beta_{\phi}=1-\textbf{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 hypothesis 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 $f(x)\leq 1-x$ for $x\in[0,1]$. We
define a mechanism ${\cal M}$ to be $f$-DP if

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

for all neighboring $d$ and $d^{\prime}$. Proposition 2.5 in [5] is an
adaptation of a result in [31] 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 DP-SGD algorithm can be tightly analysed by using
$f$-DP.

Gaussian DP: In order to proceed [5] 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 [5] 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}).$
(60)

Subsampling: Besides implementing Gaussian noise, DP-SGD also uses sub-
sampling: For a data set $d$ of $N$ samples, ${\tt Sample}_{s}(d)$ selects a
subset of size $s$ 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 $g^{*}$ of a function $g$ is defined as

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

Theorem 4.2 in [5] 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}_{s}$
is $C_{s/N}(f)$-DP.

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

$f\otimes g=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 [5] shows that if ${\cal
M}_{i}(\texttt{aux},.)$ is $f$-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^{\otimes T}$-DP.

Tight Analysis DP-SGD: We are now able to formulate the differential privacy
guarantee of DP-SGD since it is a composition of subsampled Gaussian DP
mechanisms. Theorem 5.1 in [5] states that DP-SGD in Algorithm 1 is777Their
DP-SGD algorithm uses noise ${\cal N}(0,C^{2}(2\sigma)^{2}{\bf I})$ compared
to ${\cal N}(0,C^{2}\sigma^{2}{\bf I})$ in our version of the DP-SGD
algorithm.

$C_{s/N}(G_{(\sigma/2)^{-1}})^{\otimes T}\mbox{-DP}.$

Since each of the theorems and results from [5] enumerated above are exact, we
have a tight analysis.

Our Goal: We want to understand the behavior of the DP guarantee in terms of
$s$, $N$, $T$, and $\sigma$. Our goal is to have an easy interpretation of the
DP guarantee so that we can select “good" parameters $s$, $N$, $T$, and
$\sigma$ a-priori; good in terms of achieving at least our target accuracy
without depleting our privacy budget. If we know how the differential privacy
budget is being depleted over DP-SGD iterations, then we can optimize
parameter settings in order to attain best performance, that is, best accuracy
of the final global model (the most important target when we work with machine
learning modelling). According to our best knowledge, all the current-state-
of-the art privacy accountants do not allow us to achieve this goal because
they are only privacy loss accountants and do not offer ahead-planning. It is
not sufficient to only rely on a differential privacy accountant (see e.g.,
[36] as follow-up work of [5]) for a client to understand when to stop helping
the server to learn a global model.

When talking about accuracy, we mean how much loss in prediction/test accuracy
is sacrificed by fixing a $\sigma$ (and clipping constant $C$). Our theory
maps $\sigma$ directly to an $(\epsilon,\delta)$-DP guarantee independent of
the number of rounds $T$. This allows use to characterize the trade-off
between accuracy and privacy budget. All the current-state-of-the art privacy
loss frameworks do not offer this property.

We notice that [5] makes an effort to interpret the
$C_{s/N}(G_{(\sigma/2)^{-1}})^{\otimes T}$-DP guarantee. Their Corollary 5.6
provides a precise expression based on integrals, themselves again depending
on $p=s/N$ and $\mu=(\sigma/2)^{-1}$ in our notation. This still does not lead
to the intuition we seek as we cannot extract how to select parameters
$\sigma$, $s$ and $T$ given a data set of size $N$, given a privacy budget,
and given a utility that we wish to achieve. We further explain this point in
next paragraphs.

In what follows, we seek a relationship between $\sigma$, $s$, $T$,
$\epsilon$, $\delta$, and $N$ for Gaussian DP based on Corollary 5.4 in [5].
Corollary 5.4 in [5] provides an asymptotic analysis which is a step forward
to the kind of easy to understand interpretation we seek for: It states that
if both $T\rightarrow\infty$ and $N\rightarrow\infty$ such that
$s\sqrt{T}/N\rightarrow c$ for some constant $c>0$ (and where $s$ is a
function of $N$ that may tend to $\infty$ as well), then the DP-SGD algorithm
(in this paper with the factor 2 differing $\sigma$) is $\mu$-Gaussian DP for

$\mu=(c/2)\cdot\tau^{-1}\mbox{ with
}\tau^{-1}=\sqrt{8}\cdot\sqrt{e^{(\sigma/2)^{-2}}\Phi(3(\sigma/2)^{-1}/2)+3\Phi(-(\sigma/2)^{-1}/2)-2}.$

In Section C.1 we show that $\tau^{-1}=\sigma^{-1}+O(\sigma^{-2})$ and we show
that for $\mu\leq\epsilon\leq 1$, $\mu$-Gaussian DP translates to the DP-SGD
algorithm being $(\epsilon,\delta)$-DP for $\delta\ll\epsilon\ll 1$ if

$\displaystyle\tau$ $\displaystyle\approx$
$\displaystyle\frac{(c/2)\sqrt{2(\ln(1/\delta)+\ln(\epsilon)-O(\ln\ln(1/\delta)))}}{\epsilon}\mbox{
with }s\sqrt{T}/N\rightarrow c.$

We see a similar $s\sqrt{T}/N$ dependency in Theorem 2 by [1]. The difference
is that Theorem 2 holds in a non-asymptotic setting. That is, $T$ and $N$ do
not need to tend to $\infty$ whereas the expression above does require taking
such a limit. Of course, one can analyse the convergence rate of achieving the
limit $\mu$ given $T$ and $N$ tending to infinity. When doing such an analysis
one may find expressions of Gaussian DP guarantees as a function of $T$ and
$N$ that hold for all concrete values of $T$ and $N$. This may lead to results
that strengthen our Theorem 2 (we leave this as an open problem). It is clear
that the above asymptotic result is still insufficient for our purpose: How do
we a-priori select concrete parameters $\sigma$, $s$, and $T$ given concrete
parameters for $N$, a given privacy budget and utility that we wish to
achieve?

In this paper we decided to generalize the proof method of Theorem 2 rather
than working with the complex integrals that provide the exact
characterization of $f$-DP for the DP-SGD algorithm as stated above. This
approach allows us to obtain the non-asymptotic result of Theorem 1 which
shows into large extent the independence of $T$, which is not immediately
understood from Theorem 2 and the corollary discussed above. As future work we
propose to use the $f$-DP framework to figure out how tight the presented
analysis is in this paper – since the discussed corollary above and Theorem 2
are up to constants equivalent (in the asymptotic setting) and since our
generalization makes constants in Theorem 2 explicit as function of parameters
$s$, $T$, and $N$, we expect our analysis to be tight up to a small constant
factor. Section C.2 shows a first result on the tightness of our Theorem 1.
The advantage of our result is that it is easy to interpret and we do not need
to fully rely on an accountant method to keep track of spent privacy budget
while participating in learning a global model based on local data.

###  C.1 Translation to $(\epsilon,\delta)$-DP

We first observe that by using $e^{x}=1+x+O(x^{2})$ and
$\Phi(x)=\frac{1}{2}+\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}(x+O(x^{3}))=\frac{1}{2}+\frac{x}{\sqrt{2\pi}}+O(x^{3})$,
a first order approximation of $\tau^{-1}$ is equal to
$\sigma^{-1}+O(\sigma^{-2})$ (hence, $\tau^{-1}\approx\sigma^{-1}$ for large
$\sigma$).

For $x\geq 0$, we have the approximation

$\Phi(-x)=\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}\left(\frac{1}{x}-\frac{1}{x^{3}}+O(\frac{1}{x^{5}})\right).$

Let $y\leq x$. Together with $-(x-y)^{2}/2=2xy-(x+y)^{2}/2$ we derive

$\displaystyle\Phi(-x+y)-e^{2xy}\Phi(-x-y)$ $\displaystyle=$
$\displaystyle\frac{e^{-(x-y)^{2}/2}}{\sqrt{2\pi}}(\frac{1}{x-y}-\frac{1}{(x-y)^{3}}+O(\frac{1}{(x-y)^{5}})$
$\displaystyle-\frac{e^{-(x-y)^{2}/2}}{\sqrt{2\pi}}(\frac{1}{x+y}-\frac{1}{(x+y)^{3}}+O(\frac{1}{(x+y)^{5}}))$
$\displaystyle=$
$\displaystyle\frac{e^{-(x-y)^{2}/2}}{\sqrt{2\pi}}(\frac{2y}{x^{2}-y^{2}}-\frac{6yx^{2}+2y^{3}}{(x^{2}-y^{2})^{3}}+O(\frac{1}{x^{5}}))$
$\displaystyle=$
$\displaystyle\frac{e^{-x^{2}(1-y/x)^{2}/2}}{\sqrt{2\pi}}(\frac{2y}{x^{2}(1-(y/x)^{2})}+O(\frac{y}{x^{4}}+\frac{1}{x^{5}}))$

If we assume

$\mu\leq\epsilon\leq 1,$

then $(\mu/2)/(\epsilon/\mu)=\mu^{2}/(2\epsilon)\leq\epsilon/2\leq 1$,
$\epsilon/\mu\geq 1$, and $\epsilon\leq 1$. We can use the above formulas and
approximate (60) as follows:

$\displaystyle\delta$ $\displaystyle=$
$\displaystyle\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2})-e^{\epsilon}\Phi(-\frac{\epsilon}{\mu}-\frac{\mu}{2})$
$\displaystyle=$
$\displaystyle\frac{e^{-(\epsilon/\mu)^{2}(1-\mu^{2}/(2\epsilon))^{2}/2}}{\sqrt{2\pi}}\left(\frac{\mu^{3}}{\epsilon^{2}(1-(\mu^{2}/(2\epsilon))^{2})}+O(\frac{\mu^{5}}{\epsilon^{5}})\right).$

This gives

$1/\mu=\frac{\sqrt{2(\ln(1/\delta)+\ln(\frac{\mu^{3}}{\sqrt{2\pi}(\epsilon^{2}-\mu^{4}/4)}+O((\frac{\mu}{\epsilon})^{5})))}}{\epsilon-\mu^{2}/2},$

hence,

$\tau=\frac{(c/2)\sqrt{2(\ln(1/\delta)+\ln(\frac{\mu^{3}}{\sqrt{2\pi}(\epsilon^{2}-\mu^{4}/4)}+O((\frac{\mu}{\epsilon})^{5})))}}{\epsilon-\mu^{2}/2}\mbox{
with }s\sqrt{T}/N\rightarrow c\mbox{ and
}\tau^{-1}=\sigma^{-1}+O(\sigma^{-2}).$

For small $\epsilon$, we can approximate $\tau$ as

$\tau\approx\frac{(c/2)\sqrt{2(\ln(1/\delta)+\ln(\frac{\epsilon}{\sqrt{2\pi}}(\frac{\mu}{\epsilon})^{3}+O((\frac{\mu}{\epsilon})^{5})))}}{\epsilon}.$

Since $(c/2)\tau^{-1}=\mu\leq\epsilon$, we may write $\mu=\epsilon/b$ for some
$b\geq 1$. Notice that $(c/2)/\epsilon=\tau/b$. This leads to the
approximation

$b\approx\sqrt{2(\ln(1/\delta)+\ln(\frac{\epsilon}{\sqrt{2\pi}}\frac{1}{b^{3}}+O(\frac{1}{b^{5}})))}.$

By default $\delta=1/N$ and, see Section 3.2, $N=\Omega(1/\epsilon)$, that is,
$\epsilon=\Omega(1/N)$ (also notice that good accuracy can only be achieved
for $\sigma$ small enough, that is, $\epsilon$ is generally orders of
magnitude larger than $1/N$). So, we may assume $\epsilon\gg\delta$. Then
substituting $\sqrt{2\ln(1/\delta)}$ for $b$ at the right hand side yields

$b\approx\sqrt{2(\ln(1/\delta)+\ln(\epsilon)-O(\ln\ln(1/\delta)))}.$

Substituting back in the expression for $\tau$ proves for
$\delta\ll\epsilon\ll 1$,

$\tau\approx\frac{(c/2)\sqrt{2(\ln(1/\delta)+\ln(\epsilon)-O(\ln\ln(1/\delta)))}}{\epsilon}\mbox{
with }s\sqrt{T}/N\rightarrow c\mbox{ and
}\tau^{-1}=\sigma^{-1}+O(\sigma^{-2}).$

###  C.2 On the Tightness of the Lower Bound on $T$

We consider the special case where $T$ meets its lower bound (3):
$T=\frac{\gamma\theta^{2}}{\epsilon}\cdot k^{2}$. Notice that our experiments
show that this is a good setting for best accuracy; we also target this in our
adaptive DP-SGD. We wonder into what extent we can relax the constraint on $T$
in Theorem 1. That is, how much can the lower bound on $T$ be reduced?

To answer this question, let

$T=\frac{a}{\epsilon}\cdot k^{2}$

and let’s define

$c:=\sqrt{\frac{\epsilon}{a}}=\frac{k}{\sqrt{T}}=\frac{K}{\sqrt{T}N}=\frac{s\sqrt{T}}{N},$

where we consider a constant step size $s$ (hence, $\theta=1$). Substituting
this in the final formula for $\tau$ of Section C.1 yields for
$\epsilon\gg\delta$

$\tau\approx\sqrt{\frac{\ln(1/\delta)+\ln(\epsilon)-O(\ln\ln(1/\delta))}{2a\epsilon}}.$
(61)

Here, $\tau\approx\sigma$ for $\sigma\gg 1$. Since Section C.1 provides a
tight analysis, we know that for $\epsilon\gg\delta$ and $\sigma\gg 1$ with
$s\sqrt{T}/N\rightarrow c$ for $N\rightarrow\infty$ and $T\rightarrow\infty$,
we cannot achieve a $\sigma$ smaller than the right hand side of (61). If
Theorem 1 holds true for $T\geq\frac{a}{\epsilon}\cdot k^{2}$, then
$\sigma=\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$ can be achieved. According
to the previous argument this must be at least the right hand side of (61) and
we conclude that $2\geq 1/(2a)$. This shows that $a\geq 1/4$ and at best
Theorem 1 holds for $T\geq\frac{1}{4\epsilon}\cdot k^{2}$, hence, at most a
factor $4\gamma\theta^{2}$ smaller than the current lower bound on $T$ for
which Theorem 1 is proven. We conclude that the lower bound on $T$ is tight up
to at most a factor $4\gamma\theta^{2}$.

This raises the question, can we prove a lower $\sigma$ for
$(\epsilon,\delta)$ than the one of Theorem 1 if we require a more restrictive
lower bound on $T$, that is, $T\geq\frac{a}{\epsilon}\cdot k^{2}$ where
$a\geq\gamma\theta^{2}$ (a larger lower bound)? That is, can we prove a lower
$\sigma$ for larger $a\geq 1$; the current theorem proves the current
$\sigma=\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$ for $a=1$. It may very well
be the case that we can prove a $\sigma$ characterization less than
$\sqrt{2(\epsilon+\ln(1/\delta))/\epsilon}$ if $a>1$. We do not know into what
extent our formula for $\sigma$ can be improved (made smaller) for larger
$T\geq\frac{a}{\epsilon}\cdot k^{2}$. We hypothesize that such an improvement
will transform the current simple formula into a complex one in order to
account for the dependency on $a$ (which may restrict our capability of being
able to plan ahead). We expect that Theorem 1 provides a good first order
approximation of the dependency on $a$. We leave the above question as an open
problem.

##  Appendix D Experiments

We provide experiments to support our theoretical findings, i.e., convergence
of our proposed asynchronous distributed learning framework with differential
privacy (DP) to a sufficiently accurate solution. We cover strongly convex,
plain convex and non-convex objective functions over iid local data sets.

We introduce our experimental set up in Section D.1. Section D.2 provides
utility graphs for different data sets and objective functions. A utility
graph helps choosing the maximum possible noise $\sigma$, in relation to the
value of the clipping constant $C$, for which decent accuracy can be achieved.
Section D.3 provides detailed experiments for our asynchronous differential
privacy SGD framework (asynchronous DP-SGD) with different types of objective
functions (i.e., strongly convex, plain convex and non-convex objective
functions), different types of constant sample size sequences and different
levels of privacy guarantees (i.e., different privacy budgets $\epsilon$).

All our experiments are conducted on LIBSVM [3]888https://www.csie.ntu.edu.tw/
cjlin/libsvmtools/datasets/binary.html , MNIST [16]
999http://yann.lecun.com/exdb/mnist/, and
CIFAR$10$101010https://www.cs.toronto.edu/ kriz/cifar.html data sets.

###  D.1 Experiment settings

Simulation environment. For simulating the asynchronous DP-SGD framework, we
use multiple threads where each thread represents one compute node joining the
training process. The experiments are conducted on Linux-64bit OS, with $16$
cpu processors, and 32Gb RAM.

Objective functions. Equation (62) defines the plain convex logistic
regression problem. The weight vector $w$ and the bias value $b$ of the
logistic function can be learned by minimizing the log-likelihood function
$J$:

$J=-\sum_{i=1}^{N}[y_{i}\cdot\log(\bar{\sigma}_{i})+(1-y_{i})\cdot\log(1-\bar{\sigma}_{i})],\text{
(plain convex)}$ (62)

where $N$ is the number of training samples $(x_{i},y_{i})$ with
$y_{i}\in\\{0,1\\}$ and $\bar{\sigma}_{i}$ is defined by

$\bar{\sigma}_{i}=\frac{1}{1+e^{-(w^{\mathrm{T}}x_{i}+b)}},$

which is the sigmoid function with parameters $w$ and $b$. Our goal is to
learn a vector $w^{*}$ which represents a pair $\bar{w}=(w,b)$ that minimizes
$J$.

Function $J$ can be changed into a strongly convex problem $\hat{J}$ by adding
a regularization parameter $\lambda>0$:

$\hat{J}=-\sum_{i=1}^{N}[y_{i}\cdot\log(\sigma_{i})+(1-y_{i})\cdot\log(1-\sigma_{i})]+\frac{\lambda}{2}\left\|w\right\|^{2},\text{
(strongly convex).}$

where $\bar{w}=(w,b)$ is vector $w$ concatenated with bias value $b$. In
practice, the regularization parameter $\lambda$ is set to $1/N$ [27].

For simulating non-convex problems, we choose a simple neural network (Letnet)
[17] for MNIST data set and AlexNet [14] for CIFAR$10$ data set with cross
entropy loss function for image classification.

The loss functions for the strong, plain, and non-convex problems represent
the objective function $F(.)$.

Parameter selection. The parameters used for our distributed algorithm with
Gaussian based differential privacy for strongly convex, plain convex and non-
convex objective functions are described in Table 1. The clipping constant $C$
is set to $0.1$ for strongly convex and plain convex problems and $0.025$ for
non-convex problem (this turns out to provide good utility).

Table 1: Common parameters of asynchronous DP-SGD framework with differential
privacy

|  # of clients $n$ |  Diminishing step size $\bar{\eta_{t}}$ |  Regular $\lambda$ |  Clipping constant $C$
---|---|---|---|---
Strongly convex | 5 | $\frac{\eta_{0}}{1+\beta{t}}{\textsuperscript{\textdaggerdbl}}$ | $\frac{1}{N}$ | 0.1
Plain convex | 5 |  $\frac{\eta_{0}}{1+\beta{t}}$ or $\frac{\eta_{0}}{1+\beta\sqrt{t}}$ | $N/A$ | 0.1
Non-convex | 5 | $\frac{\eta_{0}}{1+\beta\sqrt{t}}$ | $N/A$ | 0.025

  * •

${\ddagger}$ The $i$-th round step size $\bar{\eta}_{i}$ is computed by
substituting $t=\sum_{j=0}^{i-1}s_{j}$ into the diminishing step size formula.

For the plain convex case, we can use diminishing step size schemes
$\frac{\eta_{0}}{1+\beta\cdot t}$ or $\frac{\eta_{0}}{1+\beta\cdot\sqrt{t}}$.
In this paper, we focus our experiments for the plain convex case on
$\frac{\eta_{0}}{1+\beta\cdot\sqrt{t}}$. Here, $\eta_{0}$ is the initial step
size and we perform a systematic grid search on parameter $\beta=0.001$ for
strongly convex case and $\beta=0.01$ for both plain convex and non-convex
cases. Moreover, most of the experiments are conducted with $5$ compute nodes
and $1$ central server. When we talk about accuracy (from Figure 7 and
onward), we mean test accuracy defined as the fraction of samples from a test
data set that get accurately labeled by the classifier (as a result of
training on a training data set by minimizing a corresponding objective
function).

###  D.2 Utility graph

The purpose of a utility graph is to help us choose, given the value of the
clipping constant $C$, the maximum possible noise $\sigma$ for which decent
accuracy can be achieved. A utility graph depicts the test accuracy of model
$F(w^{*}+n)$ over $F(w^{*})$, denotes as accuracy fraction, where $w^{*}$ is a
near optimal global model and $n\sim{\cal N}(0,C^{2}\sigma^{2}{\bf I})$ is
Gaussian noise. This shows which maximum $\sigma$ can be chosen with respect
to allowed loss in expected test accuracy, clipping constant $C$ and standard
deviation $\sigma$.

(a) Strong convex.

(b) Plain convex.

Figure 4: Utility graph with various gradient norm $C$ and noise level
$\sigma$

(a) Strong convex.

(b) Plain convex.