# Dynamic Differential-Privacy Preserving SGD

Jian Du  Song Li  Xiangyi Chen  Siheng Chen  Mingyi Hong

###### Abstract

The vanilla Differentially-Private Stochastic Gradient Descent (DP-SGD),
including DP-Adam and other variants, ensures the privacy of training data by
uniformly distributing privacy costs across training steps. The equivalent
privacy costs controlled by maintaining the same gradient clipping thresholds
and noise powers in each step result in unstable updates and a lower model
accuracy when compared to the non-DP counterpart. In this paper, we propose
the dynamic DP-SGD (along with dynamic DP-Adam, and others) to reduce the
performance loss gap while maintaining privacy by dynamically adjusting
clipping thresholds and noise powers while adhering to a total privacy budget
constraint. Extensive experiments on a variety of deep learning tasks,
including image classification, natural language processing, and federated
learning, demonstrate that the proposed dynamic DP-SGD algorithm stabilizes
updates and, as a result, significantly improves model accuracy in the strong
privacy protection region when compared to the vanilla DP-SGD. We also conduct
theoretical analysis to better understand the privacy-utility trade-off with
dynamic DP-SGD, as well as to learn why Dynamic DP-SGD can outperform vanilla
DP-SGD.

Machine Learning, ICML

##  1 Introduction

Publishing deep neural networks trained on private datasets poses a
significant risk of data privacy leakage because the model embeds information
about the training data. Zhu & Han (2020) and Zhao et al. (2020), for example,
both provide paradigms for breaching privacy and reconstructing training
examples from published models. As a result, optimizers that protect the
privacy of the model while training it are becoming increasingly important.
Differential Privacy (DP) (Dwork, 2006), a gold-standard method for privacy-
preserving computation that makes it nearly impossible for an adversary to
single out a data record, is growing in importance and must be guaranteed to
protect privacy.

By clipping the per-sample gradient and adding calibrated Gaussian noise in
each step, Differentially-Private SGD (DP-SGD) (Abadi et al., 2016) has been
proposed to protect the model with the corresponding total privacy cost
derived by composing the privacy costs of each step being less than a
predefined privacy budget. The clipping operation, which causes estimation
bias to the true gradient, as well as the random noise, induce instability and
even ramp-up of DP-SGD updates, as illustrated by the test shown in Fig. 1. A
high clipping threshold, intuitively, implies a small bias term, and vice
versa. Under a fixed privacy, thereby, we can reduce bias by using large
clipping thresholds, but at the costs of possible performance degradation due
to increased noise power.

In the vanilla DP-SGD, a constant clipping threshold is used, and choosing the
proper clipping threshold, according to the literature, is more of an art than
a science. This motivates us to study how to adapt to the dynamic of private
gradient updates to adjust the clipping threshold and noise power so as to
narrow the performance gap from both the practical implementation as well as
theoretical understanding point of views. In this paper, we make the following
main contributions:

  * •

We extend the Gaussian DP’s central limit theorem (CLT) to obtain an
analytical composition results for non-uniform distributing privacy costs with
the Gaussian mechanisms. The closed-form expression of the CLT result
facilitates the dynamic clipping and noise calibration along the updates under
a predefined privacy budget constraint. We thereby propose the sensitivity
decay and growing-$\mu_{t}$ methods under this extended Gaussian DP CLT, and
show that combining these two methods leads to a novel dynamic DP-SGD
algorithm with additional performance gain in practice.

  * •

We perform a series of experiments and ablation studies on a variety of neural
network tasks, including image classification, natural language processing,
and federated learning, and show that the proposed dynamic DP-SGD effectively
stabilizes gradient updates and consistently outperforms existing methods.
With a strong privacy guarantee, i.e., at $\epsilon=1.2$, dynamic DP-SGD has a
performance loss of only $2.49\%$ when compared to the non-DP version on MNIST
dataset, and the loss is reduced to $1.72\%$ in the federated learning setting
for a stronger privacy guarantee, i.e., $\epsilon=1$.

  * •

We investigate analytically the impact of varying DP costs along the updates,
and derive the utility guarantee of the proposed DP-SGD method.
Mathematically, we demonstrate the utility on both clipping thresholds and
noise powers over iterations, and we gain insights into the privacy-utility
trade-off with dynamic DP-SGD.

##  2 Differential Privacy and Vanilla DP-SGD

Figure 1: Experiments on MNIST with DP budget
$(\epsilon,\delta)=(0.4,10^{-5})$ after $5\times 10^{3}$ steps for both DP-SGD
and the proposed dynamic DP-SGD with the same corresponding settings as that
in Table 1. In comparison to SGD, DP-SGD is unstable, and the stochastic
gradient (SG) norm has a ramp-up period. However, the SG norm is stabilized by
the dynamic DP-SGD. Additional experiments on the Fashion-MNIST is also
provided in Appendix A.1.

Differential Privacy (DP) defines an upper bound of the privacy level by
computing a pair of $(\epsilon,\delta(\epsilon))$. A lower $\epsilon$ value
leads to better privacy protection, but it potentially also makes the
protected algorithm less useful. The value $\delta$ can be interpreted as the
probability of failing to achieve DP. With the notion of the neighboring data
sets, i.e., $X\sim X^{\prime}$, which differs by one data record, the formal
$(\epsilon,\delta)$-DP definition is given below (Dwork, 2006).

######  Definition 1.

(($\epsilon,\delta(\epsilon)$)-DP Profile) A randomized algorithm $M(\cdot)$
gives $(\epsilon,\delta(\epsilon))$-differential privacy if for any pair of
neighboring datasets $X\sim X^{\prime}$ and any event $E$ belongs to the range
of $M$,

$\mathbb{P}(M(X)\in
E)\leqslant\mathrm{e}^{\epsilon}\mathbb{P}\left(M\left(X^{\prime}\right)\in
E\right)+\delta,$

where the probability $\mathbb{P}(\cdot)$ is taken over the randomness of $M$,
and $\epsilon\geq 0$. When $\delta=0$, the algorithm is $\epsilon$-DP.
Intuitively, this means that we can’t tell whether $M$ was run on $X$ or
$X^{\prime}$ based on the results. Thereby, an adversary will almost never
infer the existence of any specific data record in the input data set.

In a Gaussian DP mechanism, let $Y$ be the random variable following Gaussian
distribution with $Y\sim\mathcal{N}\left(0,\sigma^{2}I_{d}\right)$ and
$f:X^{n}\rightarrow\mathbb{R}^{d}$. The Gaussian mechanism $M(X)=f(X)+Y$
follows the DP profile (Wang et al., 2019):

$\delta(\epsilon;\mu)=\Phi\left(-\frac{\epsilon}{\mu}+\frac{\mu}{2}\right)-\mathrm{e}^{\epsilon}\Phi\left(-\frac{\epsilon}{\mu}-\frac{\mu}{2}\right),$
(1)

where

$\mu=\frac{C}{\sigma},$ (2)

with $C$ the sensitivity of $f(X)$ and $\Phi(\cdot)$ the Gaussian cumulative
distribution function. The DP-SGD, which protects the model from revealing the
training data privacy, is proposed in Abadi et al. (2016) based on the
Gaussian mechanism. Let the model parameters be denoted by $\theta$. and the
loss function be $L(\theta)=\frac{1}{N}\sum_{i=1}^{N}f(\theta,x_{i})$ and the
clipped stochastic gradient at step $t$ as
$g_{t}=\frac{1}{p\left|X\right|}\big{[}\sum_{x\in
X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}$ where
$g_{x}\triangleq\frac{\partial f(\theta_{t},x)}{\partial\theta_{t}}$. To
calibrate the noise required for DP, one can first clip the $\ell_{2}$-norm of
the gradient by computing

$\widetilde{g}_{x}\triangleq\operatorname{CL}\left({g_{x}};C\right)\triangleq
g_{x}\cdot\min\left(1,\frac{C}{\left\|{g_{x}}\right\|}\right),$ (3)

and then add the noise $\xi_{t}\sim\mathcal{N}(0,\sigma^{2})$ with
$\sigma^{2}=\frac{C^{2}}{\mu^{2}}$. That is, the $t$-th step of the DP-SGD
algorithm is given by:

$\displaystyle\text{DP-
SGD:}\quad\begin{split}\theta_{t+1}=\theta_{t}-\eta\frac{1}{\left|X_{t}\right|}\left(\sum_{x\in
X_{t}}\widetilde{g}_{x}+\xi_{t}\right).\end{split}$ (4)

Because of DP’s post-processing property (Dwork et al., 2014, Proposition
2.1), protecting gradients provides the same level of privacy protection on
the output model. A closer examination of the DP-SGD process in (4) reveals
that the clipping-per-sample operator introduces biases to the original
unbiased gradient estimate in the SGD updates if $C$ is not large enough. It
is possible to have an unbiased gradient estimate by increasing $C$, if $C$ is
greater than any $\ell_{2}$ norm of $\frac{\partial f_{x}}{\partial\theta}$.
It does, however, result in an over-calibrated noise power.

Motivations of this work: In standard SGD updates for non-convex optimization,
it has been shown that
$\lim_{T\rightarrow\infty}\mathbb{E}\left[\left\|{\partial
f(\theta_{T},x)}/{\partial\theta_{T}}\right\|^{2}\right]=0$ (Bottou et al.,
2018). However, because the vanilla DP-SGD is followed by fixed clipping
threshold $C$ and constant noise power $\sigma^{2}$ as shown in Eq.(3) and
(4), the ratio of noise power to the true gradient norm in Eq. (4) would
continue to rise if $\lim_{T\rightarrow\infty}\mathbb{E}\left[\left\|{\partial
f(\theta_{T},x)}/{\partial\theta_{T}}\right\|^{2}\right]=0$, resulting in
unstable updates. This hypothesis is supported by the experimental results in
Fig. 1 as well as that displayed in Appendix A.1, which display the average
coordinate stochastic gradient norm for all the data records in each step. It
is worth noting that the stochastic gradient norm has a ramp-up period.
Similar phenomenon also appeared in the experiments in (Thakkar et al., 2019,
Fig. 4). The observation motivates us to investigate a dynamic DP-SGD to
change $C$ and $\sigma^{2}$ along with the stochastic gradient updates in
order to stabilize the iterations. To facilitate the study, in the following
section, we extend the Gaussian DP CLT (Dong et al., 2019) to compose the non-
uniformly DP costs.

##  3 Dynamic DP-SGD

In the following, we evaluate the privacy cost using the Gaussian DP (GDP)
framework (Dong et al., 2019), which measures the privacy profile
$(\epsilon,\delta)$ in terms of $\mu=C/\sigma$ using Eq. (1) and (2). To make
our paper self-contained, we include a preliminary of GDP in Appendix A.2.

###  3.1 Extended CLT for GDP

Existing GDP CLT results (Dong et al., 2019; Bu et al., 2020) assume that each
step satisfies the same $G_{\mu}$-DP, which is insufficient for the dynamic
changing $C$ and $\sigma$ case. We investigate the extended GDP CLT to pave
the way for privacy accounting of dynamic DP-SGD, in which each step $t$ has
different $C_{t}$ and $\sigma_{t}$, resulting in different $G_{\mu_{t}}$-DP
costs to be composed. Let $M_{A}$ and $M_{B}$ denote the compositions of $T$
steps updates of the training data sets $X$ and $X^{\prime}$, respectively,
with $X\sim X^{\prime}$. According to (4), each step consists of sub-sampling,
denoted by $\text{PS}(\cdot)$ and local updates. Then, we express $M_{A}$ and
$M_{B}$ by the composition of $T$-step updates, respectively,

$M_{A}\triangleq M_{T}\circ\operatorname{PS}_{T}(X)\circ\cdots\circ
M_{1}\circ\operatorname{PS}_{1}(X)$ $M_{B}\triangleq
M_{T}\circ\operatorname{PS}_{T}(X^{\prime})\circ\cdots\circ
M_{1}\circ\operatorname{PS}_{1}(X^{\prime}).$

Consider the sampling scheme $\operatorname{PS}(X)$ that each individual data
sample $(x,y)$ is subsampled independently with probability $p$ from the
training set to construct $X_{t}$. It is shown (Bu et al., 2020) that a
particular trade-off function T as defined in Appendix A.2 satisfies:

$\displaystyle{\text{T}}(M_{A},M_{B})\geqslant\otimes_{t=1}^{T}\left(p\cdot
G_{\mu_{t}}+(1-p)\text{ Id }\right),$ (5)

where $G_{\mu_{t}}$ is a function of $\mathcal{N}(0,1)$ and
$\mathcal{N}(\mu_{t},1)$ with $\mu_{t}=C_{t}/\sigma_{t}$ and $\text{ Id
}(\alpha)=1-\alpha$. The details of functions T and $G_{\mu}(\alpha)$ are
given in the appendix. The symbol $\otimes_{t=1}^{T}$ denotes the product of
all the $T$ trade-off functions with the form $p\cdot G_{\mu_{t}}+(1-p)\text{
Id }$, which is far from analytically computable. When all $\mu_{t}$ are the
same, i.e., $\mu_{t}=\mu$, Bu et al. (2020) shows the CLT of the composition
is given by

$\mu_{\text{tot}}=p\sqrt{T(e^{\mu^{2}}-1)}.$ (6)

In the following corollary, we develop an extension of the above GDP CLT with
the proof provided in Appendix A.

######  Corollary 1.

Consider a series of adaptive composition mechanisms $M_{t}$ for $t\in[T]$,
where $M_{t}$ is $G_{\mu_{t}}$-DP, and each mechanism works only on a
subsampled data sets by independent Bernoulli trial with probability $p$. The
trade-off function for $\lim_{T\rightarrow\infty}\otimes_{t=1}^{T}\left(p\cdot
G_{\mu_{t}}+(1-p)\text{ Id }\right)$ in (5) approaches to
$G_{\mu_{\text{tot}}}$-DP when $p\sqrt{T}$ is a constant, where

$\mu_{\text{\rm
tot}}=p\cdot\sqrt{\sum_{t=1}^{T}\left(\mathrm{e}^{\mu_{t}^{2}}-1\right)},$ (7)

and $\mu_{t}=C_{t}/\sigma_{t}$. Notably, when $\mu_{t}=\mu$ is substituted for
$t\in[T]$, Eq. (7) reduces to the CLT result in (6). Similar to the original
GDP CLT (Dong et al., 2019; Bu et al., 2020), $\mu_{\text{\rm tot}}$ is an
approximation of the privacy cost after $T$ steps by CLT-type composition of
Gaussian mechanism. We demonstrate numerically in Fig. 4 later in the
experimental results section that only after hundreds of steps (much less than
an epoch), this approximate result approaches its upper bound computed by
advanced RDP (Balle et al., 2020). For more details about RDP and the
convergence verification of the GDP CLT, please refer to the explanation for
Fig. 4.

Corollary 1 reflects that, given the target privacy budget $(\epsilon,\delta)$
and the corresponding privacy parameter $\mu_{\text{tot}}$ obtained by (1), we
can proactively allocate privacy cost to each step $t\in[T]$ for a predefined
total number of steps $T$, according to (7). We can adjust both $C_{t}$ and
$\sigma_{t}$ to control the privacy budget allocation. Section 3.2-Section 3.4
detail the corresponding algorithms.

###  3.2 Growing-$\mu_{t}$ Method

According to the discussion at the end of Section 2, it is expected that the
stochastic gradient norm decreases in expectation along the updates. However,
vanilla DP-SGD with constant $\sigma$ leads to an increasing noise power to
true gradient ratio with proper $C$, under which the stochastic gradient would
not be clipped after some $t$ if its norm becomes smaller than $C$ in the
ideal case. If so, it is natural to reduce the noise power to stabilize the
gradient updates. Thereby, we investigate a method to reduce the noise power
$\sigma_{t}$ while keeping $C_{t}=C$. According to Eq. (2),
$\mu_{t+1}\geq\mu_{t}$ for all $t\in[T]$ in this case, and we therefore term
this method as Growing-$\mu_{t}$. With (7) in mind, we control the privacy
cost rate by adjusting a hyper-parameter $\rho_{\mu}$ with

$\rho_{\mu}\triangleq\frac{\mu_{T}}{\mu_{0}},\quad\rho_{\mu}\geq 1.$ (8)

Then the dynamic $\mu_{t}$ is given by

$\mu_{t}=(\rho_{\mu})^{t/T}\cdot\mu_{0},\quad\forall t\in[T].$ (9)

Given the total privacy budget $(\epsilon,\delta)$, the equivalent privacy
parameter $\mu_{\text{tot}}$ is obtained according to (1). Then the remaining
problem is to determine the initial state $\mu_{0}$. Once $\mu_{0}$ is
obtained, the entire $\\{\mu_{t}\\}$ sequence can be generated according to
(9). By substituting (9) into (7), we obtain

$\mu^{2}_{\text{tot}}=p^{2}\cdot\sum_{t=1}^{T}\left(\mathrm{exp}\left\\{\left((\rho_{\mu})^{t/T}\cdot\mu_{0}\right)^{2}\right\\}-1\right).$
(10)

Because the above equation is transcendental when $\rho_{\mu}>1$, there is no
closed-form solution for $\mu_{0}$. Nonetheless, the r.h.s of (10) is monotone
increasing w.r.t. $\mu_{0}$, and we can thus solve it efficiently using a
numerical method such as binary search. The computation of $\mu_{t}$ is
summarized in Algorithm 1111The privacy cost rate form in (8) is not the only
one; Trying different forms requires more heuristic work, and it also makes
the theoretical analysis of privacy-utility trade-off later more involved. .
The noise power at iteration $t$ can be calculated using a specific expression
of $\mu_{0}$ and $\rho_{\mu}$:

$\sigma_{t}=\frac{C}{\mu_{0}}(\rho_{\mu})^{-\frac{t}{T}},\quad\rho_{\mu}>1,\;{\forall~{}t\in[T]}.$
(11)

One numerical example is shown in Fig. 2. Given the total DP budget
$\epsilon=1.2$, growing-$\mu_{t}$ gives the freedom to adjust the privacy cost
rate, which is the slope of the curve. In Fig 2, we demonstrate the privacy
budget consumption curve for different $\rho_{\mu}$. The solid line
($\rho_{\mu}=1$) represents vanilla DP-SGD with evenly distributed noise power
along with the step updates. With growing-$\mu_{t}$, we can now realize any
$\mu$ consumption process under the constraint of the total DP budget as shown
by the dashed lines. Specifically, the growing-$\mu_{t}$ slows consumption in
the early rounds and accelerates consumption in the later rounds.

Algorithm 1 $\mu_{t}$ computation

0: privacy budget $(\epsilon,\delta)$, $T$, $\rho_{\mu}$.

1: Compute $\mu_{\text{tot}}$ corresponding to $(\epsilon,\delta)$ according
to (1).

2: Compute $\mu_{0}$ in (10) by binary search.

3: Compute $\sigma_{t}$ according to (11) for all $t\in[T]$.

Figure 2: Consumption of privacy budget with different $\mu_{t}$ increasing
rates; $\epsilon=1.2$.

###  3.3 Sensitivity-Decay Method

When the required level of privacy protection is high, i.e., a small
$\mu_{\text{tot}}$, it requires a large $1/\mu_{t}=\sigma_{t}/C_{t}$ according
to Eq. (7). If $C_{t}$ is larger than the (stochastic) gradient norm, the
noise, which is calibrated by $C_{t}$, will dominate the true gradient and
could lead to unstable DP-SGD updates as shown in Fig. 1. Based on this
observation and considering the previous discussion that the stochastic
gradient norm should be decreased in expectation to ensure the convergence, we
design to reduce $C_{t}$ across the updates. Compare to the constant $C$ case
in vanilla DP-SGD, it will reduce the required noise power after a particular
$t$ when $C_{t}<C$.

Towards this end, we set the sequence of clipping values as follows

$C_{t}=(\rho_{c})^{-\frac{t}{T}}\cdot C_{0},\quad\rho_{c}\geq
1,\;{\forall~{}t\in[T]}.$ (12)

Different from the growing-$\mu_{t}$ method, we fix $\mu_{t}=\mu_{0}$. By
further substituting $\mu_{t}=\mu_{0}$ into (7) in Theorem 1, we have the
closed-form solution:

$\mu_{0}=\sqrt{\log\left(\frac{\mu_{\text{tot}}^{2}}{p^{2}T}+1\right)},\quad
t\in[T].$ (13)

With (12) and (13), we can calibrate the noise power at each step by:

$\sigma_{t}=\frac{C_{0}}{\mu_{0}}(\rho_{c})^{-\frac{t}{T}},\quad\rho_{c}>1,\quad
t\in[T].$ (14)

###  3.4 Dynamic DP-SGD

Algorithm 2 Dynamic DP-SGD Algorithm

0: DP budget $(\epsilon,\delta)$, sampling rate $p$ and hyper-parameters:
$\rho_{\mu}$, $\rho_{c}$ and $C_{0}$.

1: Compute $\mu_{0}$ in Algorithm 1

2: for $t=1,\ldots,T$ do

3: Compute $C_{t}=(\rho_{c})^{-\frac{t}{T}}\cdot C_{0}$ in (12)

4: Calibrate noise :
$\sigma_{t}=\frac{C_{0}}{\mu_{0}}(\rho_{\mu}\cdot\rho_{c})^{-\frac{t}{T}}$

5: Sample $X_{t}\in X$ with sampling rate $p$ and sample noise
$\xi_{t}\sim\mathcal{N}(0,\sigma^{2}_{t}I)$.

6: Compute:
$\theta_{t+1}=\theta_{t}-\frac{\eta}{\left|X_{t}\right|}\big{[}\xi_{t}+$
$\sum_{x\in X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}$ with
$\text{CL}(\cdot)$ given in (3)

7: end for

Because the noise calibration is based on $C_{t}$, we incorporate the
growing-$\mu_{t}$ method into the sensitivity-decay method and refer to this
new one as dynamic DP-SGD. It maintains the same $\mu_{t}$ increasing rate as
the previous growing-$\mu_{t}$ method while having a faster noise decay rate
than the sensitivity-decay method. We summarize the dynamic DP-SGD algorithm
in Algorithm 2 and conduct extensive experiments to show how dynamic DP-SGD
improves performance.

Remark on the dynamic private version of other optimizers: DP version of other
optimizers besides SGD can benefit from the proposed dynamically changing
clipping thresholds and noise powers. A private version of Adam, which is
refer to as dynamic DP-Adam, for example, can be obtained similar by first
computing the average per-sample gradient using Line 6 in Algorithm 2, i.e.,
$\frac{1}{\left|X_{t}\right|}\big{[}\xi_{t}+\sum_{x\in
X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}$. According to the post-
processing property of DP (Dwork et al., 2014, Proposition 2.1), the first and
second moments of the gradient can be computed based on this DP guaranteed
result, and accordingly the DP version of Adam can be computed with details
provided in Appendix A.4. Similarly, we can derive DP version of AdaGrad,
RMSProp, etc.

##  4 Experiments

###  4.1 Datasets, Models and Benchmarks

Datasets: To conduct a comprehensive test of the dynamic DP-SGD performance,
we run experiments with neural network models including MLP, CNN, LSTM,
Federated Learning, and VGG-11 on the following 6 datasets: MNIST,
FashionMNIST, IMDB, NAME, InfiniteMNIST, and chest radiographs from the
Paediatric Pneumonia dataset (Kermany et al., 2018). In Appendix A.9, we
describe each data set, the corresponding neural network model, as well as the
parameter settings for each experiment. We also provide details about the
dynamic DP-SGD federated learning algorithm for the corresponding federated
learning experiments.

Benchmarks: We compare our proposed dynamic DP-SGD, growing-$\mu_{t}$ method,
and sensitivity-decay method to the four benchmarks listed below.

(i) SGD without DP: The SGD method serve as the upper bound of model accuracy
in the absence of clipping and additive noise. For the IMDB data set, we apply
the Adam to compute the performance upper bound.

(ii) Vanilla DP-SGD : Under the same privacy budget constraint, Vannilla DP-
SGD could require different amount of noise due to different DP accounting
methods. It is shown by (Gopi et al., 2021) that the GDP CLT provides a
tighter composition bound for DP-SGD and even underestimate the privacy cost
compared to other methods including the moment accountant method (Abadi et
al., 2016). As a result, the calibrated noise power is lower than that
obtained by moment accountant, resulting in a higher accuracy. Thereby, it
provides the best performance that the vanilla DP-SGD can achieve with a
predefined privacy budget. We therefore have vanilla DP-SGD under the privacy
accounting by GDP CLT to sever as a baseline.

(iii) $\rho$-zCDP-SGD (Yu et al., 2019): This paper is relevant to our work as
it proposes decaying the noise power during the SGD and computing the privacy
loss using the $\rho$-zCDP. However, only parallel composition is considered,
with no regard for DP amplification by subsampling.

(iv) tCDP-SGD (Zhang et al., 2021a): This more recently work proposed decaying
the noise power for DP-SGD training as well as analyzing the DP composition
and subsampling amplification under the truncated concentrated differential
privacy (tCDP) framework.

Parameters: We concentrate on the strong privacy guarantee, with the smallest
$\epsilon$ set to be 0.1. We set different $\epsilon$’s denoted in each table
due to different training data sizes and learning problem hardness; and
$\delta=1/(10|X|)$, where $|X|$ is the training data sample size. It is worth
noting that we observed a significant performance degradation of DP-SGD when
performing IMDB tasks. As a result, we also test a relatively large range of
$\epsilon$, i.e. $\epsilon\in[0.5,9]$. The hyperparameters $\rho_{c}$ and
$\rho_{\mu}$ are swept in the following predefined sets:
$1/\rho_{c},1/\rho_{\mu}\in\\{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8\\}.$ Other
hyper-parameters are detailed in Appendix A.9222The code will be available
shortly at github.com/dynamic-dp..

###  4.2 Results Analysis

Experiment results for the above six different datasets on MLP, CNN, LSTM,
Federated Learning, and VGG models are shown in Table 1-Table 5, along with
the performance of benchmarks and proposed methods. In general, the proposed
extended GDP CLT supports the privacy accounting for dynamic clipping and
noise power decay in dyamic DP-SGD. Separate experiments are carried out with
the proposed growing-$\mu_{t}$ method, sensitivity-decay method, and dynamic
DP-SGD method. The results in Table 1-Table 5 show consistently that all the
three proposed methods improve performance when compared to the static noise
GDP method (Bu et al., 2020). In particular, $\mu_{t}$ grows at the expense of
early convergence speed in order to achieve higher accuracy, while sensitivity
decay ensures more stable convergence. This explains why the sensitivity decay
outperforms that of growing-$\mu_{t}$. The dynamic DP-SGD, a combination of
the two, improves performance while causing no additional privacy loss, as
demonstrated by the Dynamic DP results in each table.

Specifically, experiments with different privacy budgets were conducted, and
the results show that the stronger the privacy protection required (i.e., the
lower $\epsilon$ value), the better the proposed dynamic DP-SGD method
performs. For example, when $\epsilon=0.4$ for the MNIST, (Yu et al., 2019)
and (Zhang et al., 2021b) adopt noise decay, but their model fails to learn
due to large calibrated noise power by the loose DP compositions. Our method,
on the other hand, outperforms the vanilla DP-SGD method by a large margin,
achieving $3.17\%$ when $\epsilon=0.4$ and even $4.6\%$ for the LSTM network
on NAME ($\epsilon=1$) shown in Table 3.

It is worth noting that if the DP accountant is not tight enough, the noise
power required will be overestimated, resulting in the noise dominating the
gradient and causing the network to fail to learn. For example, the
$\rho$-zCDP-SGD method with loose DP compositions performs significantly worse
in the high privacy guarantee region due to overestimated noise. As a result,
we only replicate its CNN model results on the MNIST and FashionMNIST datasets
in Table 1, but omitting the meaningless results on other datasets. The
extended GDP CLT , on the other hand, provides a detailed examination of DP
amplification through subsampling as well as DP composition. As a result, for
the same privacy budget, more precise noise power is calibrated.

###  4.3 Hyper-parameter sensitivity

We then test the robustness of dynamic DP-SGD performance to different values
of $\rho_{\mu}$ and $\rho_{c}$ as shown in Fig. 3. We use grid search to
demonstrate the impact of these parameters on model performance. The dynamic
method can consistently improve model performance across a wide range.

###  4.4 Exact Privacy Cost

Though (Dong et al., 2019) has shown that the GDP CLT approximate the true
privacy cost with negligible error, Gopi et al. (2021) recently discovers that
the GDP CLT may underestimate the privacy cost. The RDP accountant (Wang et
al., 2019), on the other hand, overestimates the true cost. To evaluate the
exact privacy cost, we plot the privacy cost curves for both the proposed
extended GDP CLT and RDP in Fig. 4. Specifically, we set a target training
round and conduct privacy accounting for the dynamic DP-SGD, based on the
extended GDP CLT as well as RDP333For RDP, we use autodp library by (Wang, )
for DP accounting. (Balle et al., 2020). Consequently, the true privacy cost
curve must lie somewhere between these two limits. The result of extended GDP
CLT is reasonable because the privacy cost differences between these two
limits are small, particularly in the high privacy protection region.

It is worth noting that exact accounting can be performed using the recently
proposed methods by (Gopi et al., 2021) and (Zhu et al., 2021), separately.
However, because they both require numerical computation, given a total
privacy budget, the computation of different noise power for the mechanism of
each step becomes much involved.

Table 1: CNN on MNIST and FashionMNIST datasets.

DP Accountant Dynamic Noise MNIST FashionMNIST $\epsilon$ = 0.4 $\epsilon$
=0.6 $\epsilon$ =1.2 $\epsilon$ =0.4 $\epsilon$ =1.2 $\epsilon$ =2.0 Non-
private - 98.83 87.92 $\rho$-zCDP-SGD Noise Decay 10.28 10.12 65.33 9.86 63.30
72.18 tCDP-SGD Noise Decay 26.93 83.28 92.60 53.69 76.48 77.58 Vanilla DP-SGD
- 91.18 93.80 95.50 76.77 80.45 82.55 Ours Growing-$\mu_{t}$ 91.67 94.49 96.06
77.81 80.95 83.10 Sensitivity Decay 93.95 95.17 96.17 78.11 82.83 83.64
Dynamic DP 94.35 95.21 96.34 78.50 83.22 83.81

Table 2: MLP on the IMDB dataset.

DP Accountant Dynamic Noise IMDB $\epsilon$ = 0.5 $\epsilon$ =1 $\epsilon$ =3
$\epsilon$ =6 $\epsilon$ =9 Non-private - 82.85 tCDP-SGD Noise Decay 56.67
58.24 62.15 65.88 70.16 Vanilla DP-SGD - 63.62 69.71 75.64 77.75 78.60 Ours
Growing-$\mu_{t}$ 64.92 69.85 76.00 78.16 78.56 Sensitivity Decay 65.44 70.25
76.23 78.47 79.42 Dynamic GDP 65.63 70.77 76.64 78.61 79.61

Table 3: LSTM on NAME dataset.

DP Framework Dynamic Noise NAME $\epsilon$ = 1 $\epsilon$ =2 $\epsilon$ =4
$\epsilon$ =8 Non-private - 80.14 tCDP-SGD Noise Decay 48.13 51.20 57.67 68.53
Vanilla DP-SGD - 62.71 69.64 73.04 74.15 Extended CLT for GDP (Ours)
growing-$\mu_{t}$ 64.10 71.25 74.68 75.50 Sensitivity Decay 66.66 71.78 73.67
74.78 Dynamic DP 67.30 72.01 75.03 75.75

Table 4: Federated learning on InfiniteMNIST dataset.

DP Framework Dynamic Noise MNIST-250K MNIST-500K $\epsilon$ = 0.1 $\epsilon$
=0.4 $\epsilon$ =1 $\epsilon$ =0.1 $\epsilon$ =0.4 $\epsilon$ = 1 Non-private
- 98.89 98.96 Vanilla DP-SGD - 93.47 95.71 96.02 94.82 96.55 96.89 Ours
growing-$\mu_{t}$ 93.75 95.93 96.13 95.65 96.76 97.05 Sensitivity Decay 94.46
95.90 96.40 95.75 96.83 97.06 Dynamic DP 94.72 96.00 96.55 95.88 96.95 97.22

Table 5: VGG-11 on chest radiographs.

DP Framework Dynamic Noise Chest Xray $\epsilon$ = 0.5 $\epsilon$ =1
$\epsilon$ =1.5 Non-private - 97.02 Vanilla DP-SGD - 92.24 93.18 93.44 Ours
growing-$\mu_{t}$ 92.60 93.65 94.01 Sensitivity Decay 92.89 93.78 94.24
Dynamic DP 93.30 94.01 94.43

Figure 3: Dynamic DP-SGD performance is robust to $\rho_{\mu}$ and $\rho_{c}$.
Figure 4: Upper bound (advanced RDP) and lower bound (extended GDP CLT) of the
dynamic DP-SGD privacy cost curves. The true privacy cost must lie somewhere
between these two limits. The result of extended CLT for GDP is reasonable
because the privacy cost differences between these two limits are small,
especially in the high privacy protection region.

##  5 Theoretical Analysis

In this section, we theoretically examine the impact of varying DP costs on
DP-SGD utility guarantees. To begin with, we state a general form of dynamic
DP-SGD where $C_{t}$ and $\sigma_{t}$ can be arbitrary predefined sequences in
Algorithm 3.

Algorithm 3 General Dynamic DP-SGD Algorithm

0: DP budget $(\epsilon,\delta)$, sampling rate $p$, clipping threshold
$C_{1},...,C_{T}$, and noise power
$\widetilde{\sigma}\cdot\widetilde{\sigma}_{1},\widetilde{\sigma}\cdot\widetilde{\sigma}_{2},...,\widetilde{\sigma}\cdot\widetilde{\sigma}_{T}$.

1: for $t=1,\ldots,T$ do

2: Sample $X_{t}\in X$ with sampling rate $p$ and sample noise
$\xi_{t}\sim\mathcal{N}(0,\widetilde{\sigma}^{2}I)$.

3: Compute:
$\theta_{t+1}=\theta_{t}-\frac{\eta}{p\left|X\right|}\big{[}\sigma_{t}\xi_{t}+$
$\sum_{x\in X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}$ with
$\text{CL}(\cdot)$ in (3)

4: end for

Compared with Algorithm 2, aside from allowing arbitrary sequences
$C_{0},C_{1},...,C_{T}$ and $\sigma_{1},\sigma_{2},...,\sigma_{T}$, we denote
$\sigma_{t}=\widetilde{\sigma}\cdot\widetilde{\sigma}_{t}$ for the convenience
of analysis. Besides, in step 3 of Algorithm 3, we use $p|X|$ to replace
$|X_{t}|$ with the intuition being $\mathbb{E}[|X_{t}|]=p|X|$, where $p$ is
the sampling rate. Such a replacement can also be found in Abadi et al.
(2016), which is one of the most well-known version of DP-SGD. The main
advantage of this form in our situation is that it simplifies the utility
analysis by removing the need to calculate the first and second moments of
$\frac{1}{|X_{t}|}$, which take complicated forms. To proceed with utility
analysis, we first state a corollary of Theorem 1 regarding the requirement of
$\widetilde{\sigma}$ with proof provided in Appendix A.5.

######  Corollary 2.

Algorithm 3 satisfies $G_{\mu_{\text{tot}}}$-DP if

$\displaystyle\widetilde{\sigma}=p\frac{1}{\mu_{\text{tot}}}\sqrt{2\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}_{t}^{2}}},$
(15)

and $\frac{C_{t}}{\widetilde{\sigma}\widetilde{\sigma}_{t}}\leq 1,\forall
t\in[T]$.

Corollary 2 is a direct implication of Theorem 1 with a mild constraint
$\frac{C_{t}}{\widetilde{\sigma}_{t}\widetilde{\sigma}}=\mu_{t}\leq 1$. Note
that $\mu_{t}\leq 1$ is guaranteed for strong privacy as
$\mu_{t}\ll\mu_{\text{tot}}$, and $\mu_{\text{tot}}=1$ is just borderline
private pointed out by Dong et al. (2019). The smaller $\mu_{\text{tot}}$, the
more privacy it preserves.

Denote the objective function as
$L(\theta)=\frac{1}{N}\sum_{i=1}^{N}f(\theta,x_{i})$ and the clipped
stochastic gradient at step $t$ as
$g_{t}=\frac{1}{p\left|X\right|}\big{[}\sum_{x\in
X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}$ where
$g_{x}\triangleq\frac{\partial f(\theta_{t},x)}{\partial\theta_{t}}$. Assume
function $L(\theta)$ is $Q$-smooth, i.e.,
$L(\theta^{\prime})-L(\theta)\leq\langle\nabla
L(\theta),\theta^{\prime}-\theta\rangle+\frac{Q}{2}\|\theta-\theta^{\prime}\|^{2}$),
and each per-sample gradient is upper-bounded, i.e. $\|g_{x}\|\leq G$. We
prove the following theorem to show the privacy-utility trade-off of Algorithm
3 with details in Appendix A.6.

######  Theorem 1.

The dynamic DP-SGD (Algorithm 3) satisfies the following utility guarantee

$\displaystyle\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|^{2}\right]$ $\displaystyle\leq\frac{1}{\eta
T}\mathbb{E}[L(\theta_{1})]-L(\theta_{T+1})]+\frac{Q}{2}\frac{\eta}{T}\sum_{t=1}^{T}\mathbb{E}[\|g_{t}\|^{2}]$
$\displaystyle+\underbrace{\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|P_{t}(C_{t})G\right]}_{\triangleq\text{ bias
term}}+\frac{Q}{2}\frac{\eta}{p^{2}N^{2}}\underbrace{\frac{1}{T}\sum_{t=1}^{T}\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2}}_{\triangleq
D_{1}},$ (16)

where $P_{t}(C_{t})$ is the probability of a per-sample gradient being clipped
with threshold $C_{t}$ at $\theta_{t}$, and the expectations are taken over
all randomness including gradient sampling and noise sampling. Assume
$\sigma_{t}=\Theta(1)$ and $C_{t}=\Theta(1)$, after setting $\eta
T=N\mu_{\text{tot}}$, $\eta=\frac{1}{N\mu_{\text{tot}}}$, and substituting
$\widetilde{\sigma}$ from Corollary 2 into Eq. (1), we have

$\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|^{2}\right]=O\left(\frac{1}{N\mu_{\text{tot}}}\right)+\text{bias
term}.$

Remark on convergence rate: The derived convergence rate is
$O({1}/{(N\mu_{\text{tot}}}))$ ignoring the non-vanishing bias term. This rate
is in the same polynomial order as existing analyses, e.g.,
$\tilde{O}(1/(N\epsilon))$ rate in Theorem 5 of Zhang et al. (2017). The non-
vanishing bias term caused by gradient clipping is unavoidable since it is
proven in Song et al. (2020) that DP-SGD with clipping suffers a constant
regret in the worst case. A similar bound is also observed in Chen et al.
(2020), in which the impact of gradient clipping on symmetric gradient
distibutions is studied. The difference is that our bound is based on Gaussian
DP and the bias term is expressed in a simpler form applicable for arbitrary
distributions. As will be evident later, this simpler form provides intuitions
on why clipping threshold and noise should be adjusted dynamically.

Remark on gradient clipping $C_{t}$: The clipping operation will cause
estimation bias of the true gradient, which could lead to a constant regret
for the algorithm. This fact is reflected by the $bias$ term on the r.h.s. of
(1). And it can be seen from $P_{t}(C_{t})$ (defined as the probability of a
per-sample gradient being clipped with threshold $C_{t}$ at $\theta_{t}$) that
in general, the $bias$ term will be small if $C_{t}$’s are large and vise
versa, given the same distribution of gradients. This means that if we use
large clipping thresholds, we will reduce the $bias$ term, but at the expense
of a larger $D_{1}$ as indicated by Corollary 2 and (1). Thus, one should
choose a sequence of $C_{t}$ that could better balance the bias term and the
variance term $D_{1}$. However, an optimal solution requires knowing the
distribution of the stochastic gradient which is nearly impossible in
practice. Choosing $C_{t}$ is more of an art than a science, according to the
existing literature. One notable practical good choice is to keep
$P_{t}(C_{t})$ roughly constant, as proposed in (Andrew et al., 2021). Under
situations when the gradients are decreasing across iterations, this choice
implies $C_{t}$ should be decreasing to keep $P_{t}(C_{t})$ a constant (see
Figure 4 in (Andrew et al., 2021)). This supports the sensitivity decay method
in our Algorithm 2.

Remark on term $D_{1}$: The first two terms on the RHS of (1) are standard in
SGD analysis. We now focus on the term $D_{1}$ caused by privacy noise, which
becomes

$\displaystyle
p^{2}\frac{2}{\mu_{\text{tot}}^{2}}\frac{1}{T}\sum_{t=1}^{T}\widetilde{\sigma}_{t}^{2}{\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}_{t}^{2}}}$
(17)

after substituting $\widetilde{\sigma}$ from Corollary 2. One can readily
notice that given the sequence of $C_{t}$, this term can be minimized by
choosing $\widetilde{\sigma}_{t}$. This problem also appeared in Pichapati et
al. (2019) and Wu et al. (2021). It turns out that minimizing (17) w.r.t the
sequence $\sigma_{t}$ admits an optimal solution
$\widetilde{\sigma}_{t}=\sqrt{C_{t}}$ (see Appendix A.7 for proof). Combining
with the fact that
$\mu_{t}=\frac{C_{t}}{\widetilde{\sigma}_{t}\widetilde{\sigma}}$ indicates
$\mu_{t}\propto\sqrt{C_{t}}$, which gives a theoretical way to allocate noise
given a sequence of clipping thresholds and support that we should change
$\mu_{t}$ in different iterations. Yet, this particular choice of $\sigma_{t}$
is based on the very simplified assumption that may not reflect the whole
picture of training neural nets. For example, it is widely known that the loss
of training neural nets usually have different curvatures across different
regions reachable by different iterations. If we take into this consideration
and replace the Q-smooth assumption by
$\mathbb{E}[L(\theta_{t+1})]-L(\theta)\leq\langle\nabla
L(\theta_{t}),\mathbb{E}[\theta_{t+1}-\theta_{t}]\rangle+\frac{Q_{t}}{2}\mathbb{E}[\|\theta_{t+1}-\theta_{t}\|^{2}]$
in Theorem 1, we will reach a conclusion that
$\sigma_{t}=\sqrt{C_{t}}Q_{t}^{1/4}$, which indicates the allocation of
privacy noise should also consider the local curvature in different iterations
unknown before training (see Appendix A.8 for a detailed statement and proof).
We thus believe that a good choice of $\sigma_{t}$ and $C_{t}$ should be based
more on empirical performance of a particular choice, like the one provided in
Section 4. Meanwhile, we hope our theoretical analysis can provide some
insights about understanding this problem and inspire future explorations.

##  6 Related Work

DP-SGD Algorithm To improve the model’s accuracy, previous work has
concentrated on designing variations of DP-SGD by estimating the clipping
bound and minimizing the bias introduced by gradient clipping. More precisely,
Abadi et al. (2016) propose norm clipping and per-layer clipping, both of
which select clipping values based on gradient differences between different
layers. Pichapati et al. (2019) study AdaClip, a coordinate-wise clipping
method that could reduce the total amount of noise required. Thakkar et al.
(2019) introduce gradient clipping based on the quantile statistics of the
gradient, which requires additional DP cost to protect those quantiles.
Recently, Chen et al. (2020) analyze the bias introduced by the gradient
clipping operation and propose a method for reducing the bias error by first
adding noise before clipping. In the meantime of this paper, Wu et al. (2021)
propose adaptive DP version of SGD where the random noise added to the
gradient is optimally adapted to the stepsize. This method, however, is
inapplicable for those with stepsizes that being updated on the fly, such as
AdaGrad and Adam, as stated in the paper. It’s worth noting that the proposed
dynamic DP-SGD in this paper is compatible with the methods in Thakkar et al.
(2019); Chen et al. (2020); Wu et al. (2021) and can be used in tandem to
investigate accuracy improvement but involve more details and is one potential
avenue of future work.

Furthermore, Yu et al. (2019) provide a means of reducing noise variance
during the DP-SGD process, thereby improving model performance; and Zhang et
al. (2021b) analyze the DP cost for the same method using the z-CDP privacy
accounting. Due to the loose DP accountings, these methods have a large
performance gap in the high privacy guaranteed region. As demonstrated in the
experiments, the proposed dynamic DP-SGD improves these results significantly
due to the dynamic clipping operation and tight DP composition. Recently, Zhou
et al. (2020); He et al.  study the relationships between generalization and
privacy private learning algorithm.

##  7 Conclusions

In this paper, we have developed the dynamic differentially-private stochastic
gradient descent (dynamic DP-SGD) optimizer, which has varying clipping values
and noise powers across the update. The dynamic privacy cost is tightly
accounted by the extended central limit theorem of Gaussian differential
privacy, allowing dynamic noise to be calibrated for each individual training
step within a predefined privacy budget. In contrast to the vanilla DP-SGD, we
are able to reduce the noise term in the utility upper bound without
compromising privacy as the insight gained according to our theoretical
analysis. Extensive testing on a variety of datasets and models demonstrates
that the dynamic DP-SGD consistently and clearly outperforms existing methods
especially in the strong privacy region.

#### Acknowledgments

We would like to thank Yuxiang Wang for his helpful discussion.

## References

  * Abadi et al. (2016) Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (eds.), _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016_ , pp. 308–318. ACM, 2016.
  * Andrew et al. (2021) Galen Andrew, Om Thakkar, H Brendan McMahan, and Swaroop Ramaswamy.  Differentially private learning with adaptive clipping.  _Advances in Neural Information Processing Systems 34 pre-proceedings_ , 2021.
  * Balle et al. (2020) Borja Balle, Gilles Barthe, and Marco Gaboardi.  Privacy profiles and amplification by subsampling.  _Journal of Privacy and Confidentiality_ , 10(1), 2020.
  * Bottou et al. (2018) Léon Bottou, Frank E Curtis, and Jorge Nocedal.  Optimization methods for large-scale machine learning.  _Siam Review_ , 60(2):223–311, 2018.
  * Bu et al. (2020) Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J. Su.  Deep learning with Gaussian differential privacy.  _Harvard data science review_ , 2020 23, 2020.
  * Chen et al. (2020) Xiangyi Chen, Zhiwei Steven Wu, and Mingyi Hong.  Understanding gradient clipping in private SGD: A geometric perspective.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Dong et al. (2019) Jinshuo Dong, Aaron Roth, and Weijie J Su.  Gaussian differential privacy.  _arXiv preprint arXiv:1905.02383_ , 2019.
  * Dwork (2006) Cynthia Dwork.  Differential privacy.  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (eds.), _Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II_ , volume 4052 of _Lecture Notes in Computer Science_ , pp. 1–12. Springer, 2006.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Gopi et al. (2021) Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz.  Numerical composition of differential privacy.  _arXiv preprint arXiv:2106.02848_ , 2021.
  * (11) Fengxiang He, Bohan Wang, and Dacheng Tao.  Tighter generalization bounds for iterative privacy-preserving algorithms.  In _the 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021)_.
  * Kermany et al. (2018) Daniel S Kermany, Michael Goldbaum, Wenjia Cai, Carolina CS Valentim, Huiying Liang, Sally L Baxter, Alex McKeown, Ge Yang, Xiaokang Wu, Fangbing Yan, et al.  Identifying medical diagnoses and treatable diseases by image-based deep learning.  _Cell_ , 172(5):1122–1131, 2018.
  * Lecun & Bottou (1998) Y. Lecun and L. Bottou.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Pichapati et al. (2019) Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, and Sanjiv Kumar.  Adaclip: Adaptive clipping for private sgd.  _ArXiv_ , abs/1908.07643, 2019.
  * Song et al. (2020) Shuang Song, Om Thakkar, and Abhradeep Thakurta.  Characterizing private clipped gradient descent on convex generalized linear problems.  _arXiv preprint arXiv:2006.06783_ , 2020.
  * Thakkar et al. (2019) Om Thakkar, Galen Andrew, and H. Brendan McMahan.  Differentially private learning with adaptive clipping.  _CoRR_ , abs/1905.03871, 2019.
  * Wang et al. (2019) Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan.  Subsampled Rényi differential privacy and analytical moments accountant.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pp. 1226–1235. PMLR, 2019.
  * (18) Yuxiang Wang.  autodp: A flexible and easy-to-use package for differential privacy.  https://github.com/yuxiangw/autodp.  Accessed: 2021-09-30.
  * Wu et al. (2021) Xiaoxia Wu, Lingxiao Wang, Irina Cristali, Quanquan Gu, and Rebecca Willett.  Adaptive differentially private empirical risk minimization.  _arXiv preprint arXiv:2110.07435_ , 2021.
  * Yu et al. (2019) Lei Yu, Ling Liu, Calton Pu, Mehmet Emre Gursoy, and Stacey Truex.  Differentially private model publishing for deep learning.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , pp. 332–349. IEEE, 2019.
  * Zhang et al. (2017) Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang.  Efficient private erm for smooth objectives.  _arXiv preprint arXiv:1703.09947_ , 2017.
  * Zhang et al. (2021a) Xinyue Zhang, Jiahao Ding, Maoqiang Wu, Stephen T. C. Wong, Hien Van Nguyen, and Miao Pan.  Adaptive privacy preserving deep learning algorithms for medical data.  In _IEEE Winter Conference on Applications of Computer Vision, WACV 2021, Waikoloa, HI, USA, January 3-8, 2021_ , pp. 1168–1177. IEEE, 2021a.
  * Zhang et al. (2021b) Xinyue Zhang, Jiahao Ding, Maoqiang Wu, Stephen TC Wong, Hien Van Nguyen, and Miao Pan.  Adaptive privacy preserving deep learning algorithms for medical data.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pp. 1169–1178, 2021b.
  * Zhao et al. (2020) Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen.  idlg: Improved deep leakage from gradients.  _ArXiv_ , abs/2001.02610, 2020.
  * Zhou et al. (2020) Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee.  Private stochastic non-convex optimization: Adaptive algorithms and tighter generalization bounds.  _arXiv preprint arXiv:2006.13501_ , 2020.
  * Zhu & Han (2020) Ligeng Zhu and Song Han.  Deep leakage from gradients.  In Qiang Yang, Lixin Fan, and Han Yu (eds.), _Federated Learning \- Privacy and Incentive_ , volume 12500 of _Lecture Notes in Computer Science_ , pp. 17–31. Springer, 2020.
  * 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.
  * Ziller et al. (2021) Alexander Ziller, Dmitrii Usynin, Rickmer Braren, Marcus Makowski, Daniel Rueckert, and Georgios Kaissis.  Medical imaging deep learning with differential privacy.  _Scientific Reports_ , 11(1):1–8, 2021.

##  Appendix A Appendix

###  A.1 Unstable Updates

Figure 5: Experiments on Fashion-MNIST for both DP-SGD and the proposed
dynamic DP-SGD with the same corresponding settings as that in Table 1. In
comparison to SGD, DP-SGD is unstable, and the stochastic gradient (SG) norm
has a ramp-up period. However, the SG norm is stabilized by the dynamic DP-
SGD.

###  A.2 GDP Preliminary

We first introduce some background about GDP. Let $P$ and $Q$ denote the
distributions of $M(X)$ and $M\left(X^{\prime}\right)$ with $X\sim
X^{\prime}$, and let $\phi$ be any (possibly randomized) rejection rule for
testing $H_{0}:P$ against $H_{1}:Q$. With these in place, Dong et al. (2019)
defines the trade-off function of $P$ and $Q$ as

$\displaystyle\text{T}(P,Q):[0,1]$ $\displaystyle\mapsto[0,1]$ (18)
$\displaystyle\alpha$
$\displaystyle\mapsto\inf_{\phi}\left\\{1-\mathbb{E}_{Q}[\phi]:\mathbb{E}_{P}[\phi]\leqslant\alpha\right\\}.$

Above, $\mathbb{E}_{P}[\phi]$ and $1-\mathbb{E}_{Q}[\phi]$ are type I and type
II errors of the rejection rule $\phi$, respectively. It is shown that
$\text{T}(P,Q)\geq\text{T}(\mathcal{N}(0,1),\mathcal{N}(\mu,1))\triangleq
G_{\mu}$, which is referred to as $\mu$-GDP.

In each step of the DP-SGD in (4) with the Gaussian mechanism, it achieves
$\mu$-GDP with $\mu=\frac{C}{\sigma}$. Consider the sampling scheme
$\operatorname{PS}(X)$ that each individual data sample $(x,y)$ is subsampled
independently with probability $p$ from the training set to construct $X_{t}$.
It is shown in (Bu et al., 2020) that given two neighboring datasets $X$ and
$X^{\prime}$, if a randomized mechanism $\mathcal{M}$ is $G_{\mu}$-DP, then

$\text{T}\left(\mathcal{M}\circ\operatorname{PS}(X),\mathcal{M}\circ\operatorname{PS}\left(X^{\prime}\right)\right)\geqslant
pG_{\mu}+(1-p)\mathrm{Id},$ (19)

where $\operatorname{Id}(x)=1-x$. Then after a large enough $T$ steps, a
Berry-Esseen style CLT result is shown by (Bu et al., 2020) that as
$T\to+\infty$ and $p\sqrt{T}\to$ a constant, the composition of the r.h.s. of
(19) converges to a $G_{\mu_{\text{tot}}}$-DP with

$\mu_{\text{tot}}=p\sqrt{T(e^{\mu^{2}}-1)}.$ (20)

###  A.3 Proof of Theorem 1

Following the proof of $f$-DP central limit theorem in (Bu et al., 2020), we
have the following definitions given a function $f$:

$\displaystyle\mathrm{kl}(f)$ $\displaystyle\triangleq$
$\displaystyle-\int_{0}^{1}\log\left|f^{\prime}(x)\right|\mathrm{d}x,$ (21)
$\displaystyle\widetilde{\mathrm{kl}}(f)$ $\displaystyle\triangleq$
$\displaystyle\int_{0}^{1}\left|f^{\prime}(x)\right|\log\left|f^{\prime}(x)\right|\mathrm{d}x,$
(22) $\displaystyle\kappa_{2}(f)$ $\displaystyle\triangleq$
$\displaystyle\int_{0}^{1}\log^{2}\left|f^{\prime}(x)\right|\mathrm{d}x,$ (23)
$\displaystyle\widetilde{\kappa}_{2}(f)$ $\displaystyle\triangleq$
$\displaystyle\int_{0}^{1}\left|f^{\prime}(x)\right|\log^{2}\left|f^{\prime}(x)\right|\mathrm{d}x,$
(24) $\displaystyle\kappa_{3}(f)$ $\displaystyle\triangleq$
$\displaystyle\int_{0}^{1}|\log|f^{\prime}(x)||^{3}\mathrm{d}x,$ (25)
$\displaystyle\widetilde{\kappa}_{3}(f)$ $\displaystyle\triangleq$
$\displaystyle\int_{0}^{1}\left|f^{\prime}(x)\right|\cdot|\log|f^{\prime}(x)||^{3}\mathrm{d}x.$
(26)

Let $\left\\{f_{ni}:1\leqslant i\leqslant n\right\\}_{n=1}^{\infty}$ be a
triangular array of trade-off functions and assume the following limits for
some constants $K\geqslant 0$ and $s>0$ as $n\rightarrow\infty$:

  1. 1.

$\sum_{i=1}^{n}\mathrm{k}\mathrm{l}\left(f_{ni}\right)+\widetilde{\mathrm{k}}\mathrm{l}\left(f_{ni}\right)\rightarrow
K$,

  2. 2.

$\max_{1\leqslant i\leqslant n}\mathrm{kl}\left(f_{ni}\right)\rightarrow
0,\quad\max_{1\leqslant i\leqslant
n}\widetilde{\mathrm{k}}1\left(f_{ni}\right)\rightarrow 0$,

  3. 3.

$\sum_{i=1}^{n}\kappa_{2}\left(f_{ni}\right)\rightarrow
s^{2},\quad\sum_{i=1}^{n}\widetilde{\kappa}_{2}\left(f_{ni}\right)\rightarrow
s^{2}$,

  4. 4.

$\sum_{i=1}^{n}\kappa_{3}\left(f_{ni}\right)\rightarrow
0,\quad\sum_{i=1}^{n}\widetilde{\kappa}_{3}\left(f_{ni}\right)\rightarrow 0$,

it is shown in (Bu et al., 2020) that

$\lim_{n\rightarrow\infty}f_{n1}\otimes f_{n2}\otimes\cdots\otimes
f_{nn}(\alpha)=G_{K/s}(\alpha)$ (27)

uniformly for all $\alpha\in[0,1]$. Let
$g_{t}(x)=-{G}_{\mu_{t}}^{\prime}-1=\left|{G}_{\mu_{t}}^{\prime}\right|-1$,
where the second equation is due to the definition of the tradoff function.
Then by replacing $n$ by $t$, equations from (21) to (26) are reformulated as:

$\displaystyle\mathrm{kl}\left(f_{{p,t}}\right)$ $\displaystyle=$
$\displaystyle-\int_{0}^{1}\log(1+pg_{t}(x))\mathrm{d}x,$ (28)
$\displaystyle\widetilde{\mathrm{kl}}\left(f_{p,t}\right)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}(1+pg_{t}(x))\log(1+pg_{t}(x))\mathrm{d}x,$ (29)
$\displaystyle\kappa_{2}\left(f_{p,t}\right)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}[\log(1+pg_{t}(x))]^{2}\mathrm{d}x,$ (30)
$\displaystyle\widetilde{\kappa}_{2}\left(f_{p,t}\right)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}(1+pg_{t}(x))[\log(1+pg_{t}(x))]^{2}\mathrm{d}x,$
(31) $\displaystyle\kappa_{3}\left(f_{p,t}\right)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}[\log(1+pg_{t}(x))]^{3}\mathrm{d}x,$ (32)
$\displaystyle\widetilde{\kappa}_{3}\left(f_{p,t}\right)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}(1+pg_{t}(x))[\log(1+pg_{t}(x))]^{3}\mathrm{d}x.$
(33)

According to (27), we need to compute
$\sum_{t=1}^{T}\left(\mathrm{kl}\left(f_{p,t}\right)+\widetilde{\mathrm{k}}\mathrm{l}\left(f_{p,t}\right)\right)$
and $\sum_{t=1}^{T}\kappa_{2}\left(f_{p,t}\right)$ to obtain the CLT. Let
$p\sqrt{T}\to v$ and $p\to 0^{+}$, we compute $K$ by

$\begin{split}K=&\lim_{\begin{subarray}{c}p\rightarrow 0^{+}\\\ p\sqrt{T}\to
v\end{subarray}}\sum_{t=1}^{T}\left(\mathrm{kl}\left(f_{p,t}\right)+\widetilde{\mathrm{kl}}\left(f_{p,t}\right)\right)\\\
&=\lim_{\begin{subarray}{c}p\rightarrow 0^{+}\\\ p\sqrt{T}\to
v\end{subarray}}\sum_{t=1}^{T}p\int_{0}^{1}g_{t}(x)\cdot\log(1+pg_{t}(x))\mathrm{d}x\\\
&=\sum_{t=1}^{T}\int_{0}^{1}\frac{v^{2}}{T}\cdot
g_{t}(x)\cdot\lim_{p\rightarrow
0^{+}}\frac{1}{p}\log(1+pg_{t}(x))\mathrm{d}x\\\
&=\frac{v^{2}}{T}\sum_{t=1}^{T}\int_{0}^{1}g_{t}(x)^{2}\mathrm{d}x\\\
&=\frac{v^{2}}{T}\sum_{t=1}^{T}\left(\text{e}^{\mu_{t}^{2}}-1\right).\end{split}$
(34)

We further compute $s$ following the same procedure:

$\begin{split}s^{2}=&\sum_{t=1}^{T}\kappa_{2}\left(f_{p,t}\right)\\\
=&\frac{v^{2}}{T}\sum_{t=1}^{T}\int_{0}^{1}\lim_{p\to
0^{+}}\left[\frac{1}{p}\log(1+pg_{t}(x))\right]^{2}\mathrm{d}x\\\
=&\frac{v^{2}}{T}\sum_{t=1}^{T}\int_{0}^{1}g_{t}(x)^{2}\mathrm{d}x\\\
=&\frac{v^{2}}{T}\sum_{t=1}^{T}\left(\text{e}^{\mu_{t}^{2}}-1\right).\end{split}$
(35)

Substituting (34) and (35) into (27), we have

$\lim_{T\rightarrow\infty}f_{p,t}\otimes_{t=1}^{T}=G_{\mu}$ (36)

with

$\mu=\frac{K}{s}=p\sqrt{\sum_{t=1}^{T}\left(\text{e}^{\mu_{t}^{2}}-1\right)}.$
(37)

###  A.4 Dynamic DP-Adam

Algorithm 4 Dynamic DP-Adam Algorithm

0: DP budget $(\epsilon,\delta)$, sampling rate $p$, momentum parameters
$(\beta_{1},\beta_{2})$, a small constant $z>0$, and hyper-parameters:
$\rho_{\mu}$, $\rho_{c}$ and $C_{0}$.

1: Compute $\mu_{0}$ in Algorithm 1

2: for $t=1,\ldots,T$ do

3: Compute $C_{t}=(\rho_{c})^{-\frac{t}{T}}\cdot C_{0}$ in (12)

4: Calibrate noise :
$\sigma_{t}=\frac{C_{0}}{\mu_{0}}(\rho_{\mu}\cdot\rho_{c})^{-\frac{t}{T}}$

5: Sample $X_{t}\in X$ with sampling rate $p$ and sample noise
$\xi_{t}\sim\mathcal{N}(0,\sigma^{2}_{t}I)$.

6: Compute: $\widetilde{g}_{t}=\frac{1}{\left|X_{t}\right|}\big{[}\xi_{t}+$
$\sum_{x\in X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}$ with
$\text{CL}(\cdot)$ in (3)

7: Compute biased first momentum:
$m_{t}=\beta_{1}m_{t-1}+\left(1-\beta_{1}\right)\tilde{g}_{t}$

8: Compute biased second momentum:
$u_{t}\leftarrow\beta_{2}u_{t-1}+\left(1-\beta_{2}\right)\left(\tilde{g}_{t}\odot\tilde{g}_{t}\right)$

9: Compute bias-corrected first moment:
$\widehat{m}_{t}=m_{t}/\left(1-\beta_{1}^{t}\right)$

10: Compute bias-corrected second moment
$\widehat{v}_{t}=v_{t}/\left(1-\beta_{2}^{t}\right)$

11: Compute: $w_{t}=\widehat{m}_{t}/\left(\sqrt{\widehat{u}_{t}}+z\right)$

12: Compute: $\theta_{t+1}=\theta_{t}-\eta w_{t}$

13: end for

###  A.5 Proof of Corollary 2

From the definition Gaussian DP in Eq.( 2), we know each step in Algorithm 3
is $G_{\mu_{t}}$-DP and

$\displaystyle\mu_{t}=\frac{C_{t}}{\widetilde{\sigma}_{t}\widetilde{\sigma}}.$
(38)

Further, by Theorem 1, we know overall Algorithm 3 is $G_{\mu}$-DP with

$\displaystyle\mu=p\sqrt{\sum_{t=1}^{T}(e^{\mu_{t}^{2}}-1)}.$ (39)

Because $e^{x}<1+2x$ for $0\leq x\leq 1$, we know

$\displaystyle\mu<p\sqrt{2\sum_{t=1}^{T}\mu_{t}^{2},}\quad\text{when
$\mu_{t}^{2}\leq 1$}.$ (40)

Given a total privacy budget $\mu_{\text{tot}}$ that bounds the above $\mu$,
we have

$\displaystyle\mu<p\sqrt{2\sum_{t=1}^{T}\mu_{t}^{2}}=p\sqrt{2\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2}}}\leq\mu_{\text{tot}}.$
(41)

Rearranging the last inequality, we get

$\displaystyle\widetilde{\sigma}\geq
p\frac{1}{\mu_{\text{tot}}}\sqrt{2\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}_{t}^{2}}},$
(42)

which is sufficient to guarantee Algorithm 3 to satisfy
$G_{\mu_{\text{tot}}}$-DP.

###  A.6 Proof of Theorem 1

By the update rule in Algorithm 3, we know

$\displaystyle\theta_{t=1}=\theta_{t}-\frac{\eta}{pN}\widetilde{\sigma}_{t}\xi_{t}-\eta
g_{t}.$ (43)

By the assumption that the objective function $L(\cdot)$ is $Q$-smooth, we
have

$\displaystyle\mathbb{E}_{t}[L(\theta_{t+1})]\leq$ $\displaystyle
L(\theta_{t})+\mathbb{E}_{t}[\langle\nabla
L(\theta_{t}),(\theta_{t+1}-\theta_{t})\rangle]$
$\displaystyle+\mathbb{E}_{t}[\frac{Q}{2}\|\theta_{t+1}-\theta_{t}\|^{2}]$
$\displaystyle\leq$ $\displaystyle L(\theta_{t})-\eta\langle\nabla
L(\theta_{t}),\mathbb{E}_{t}[g_{t}]\rangle+\frac{Q}{2}\eta^{2}\mathbb{E}_{t}[\|g_{t}\|^{2}]$
$\displaystyle+\frac{Q}{2}\frac{\eta^{2}}{N^{2}p^{2}}\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2},$
(44)

where $\mathbb{E}_{t}$ denotes expectation taken over randomness at step $t$,
including gradient sampling and noise sampling. Taking the sum of $t$ from $1$
to $T$ and the expectation of all steps, we get

$\displaystyle\mathbb{E}[L(\theta_{T+1})]-\mathbb{E}[L(\theta_{1})]$
$\displaystyle\leq$
$\displaystyle-\eta\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla
L(\theta_{t}),\mathbb{E}_{t}[g_{t}]\rangle\right]+\frac{Q}{2}\eta^{2}\sum_{t=1}^{T}\mathbb{E}[\|g_{t}\|^{2}]$
$\displaystyle+\sum_{t=1}^{T}\frac{Q}{2}\frac{\eta^{2}}{N^{2}p^{2}}\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2}.$
(45)

Rearranging and dividing both sides by $T\eta$, we have

$\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla
L(\theta_{t}),\mathbb{E}_{t}[g_{t}]\rangle\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{\eta
T}(\mathbb{E}[L(\theta_{1})]-\mathbb{E}[L(\theta_{T+1})])+\frac{1}{T}\frac{Q}{2}\eta\sum_{t=1}^{T}\mathbb{E}[\|g_{t}\|^{2}]$
$\displaystyle+\frac{1}{T}\sum_{t=1}^{T}\frac{Q}{2}\frac{\eta}{N^{2}p^{2}}\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2}.$
(46)

Further, we know

$\displaystyle\mathbb{E}_{t}[g_{t}]=$
$\displaystyle\mathbb{E}[\frac{1}{p\left|X\right|}\big{[}\sum_{x\in
X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{X_{t}}[\frac{1}{p\left|X\right|}\big{[}\sum_{x\in
X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}]$
$\displaystyle\overset{(i)}{=}$
$\displaystyle\frac{1}{p\left|X\right|}p\left|X\right|\mathbb{E}_{x}[\text{CL}\left(g_{x};C_{t}\right)]$
$\displaystyle\overset{(ii)}{=}$
$\displaystyle\sum_{i=1}^{N}\frac{1}{N}\text{CL}\left(g_{x_{i}};C_{t}\right)$
$\displaystyle\overset{(iii)}{=}$
$\displaystyle\sum_{i=1}^{N}\frac{1}{N}\mathbbm{1}\left[\|g_{x_{i}}\|\leq
C_{t}\right]g_{x_{i}}$
$\displaystyle+\sum_{i=1}^{N}\frac{1}{N}\mathbbm{1}\left[\|g_{x_{i}}\|>C_{t}\right]g_{x_{i}}\frac{C_{t}}{\|g_{x_{i}}\|}$
$\displaystyle{=}$ $\displaystyle\sum_{i=1}^{N}\frac{1}{N}g_{x_{i}}$
$\displaystyle+\sum_{i=1}^{N}\frac{1}{N}\mathbbm{1}\left[\|g_{x_{i}}\|>C_{t}\right]g_{x_{i}}\left(\frac{C_{t}}{\|g_{x_{i}}\|}-1\right),$

where $(i)$ is due to each element in $X$ has $p$ probability being in $X_{t}$
and $\mathbb{E}_{x}$ is taken over a uniform distribution of $x\in X$; $(ii)$
is because we assumed that there is $N$ samples of $x$; $(iii)$ is due to the
definition of clipping operation.

Recall the fact that $\nabla L(\theta_{t})=\frac{1}{N}\sum_{i=1}^{N}g_{x_{i}}$
and the assumption $\|g_{x_{i}}\|\leq G$, we have

$\displaystyle\|\mathbb{E}_{t}[g_{t}]-\nabla L(\theta_{t})\|$ $\displaystyle=$
$\displaystyle\left\|\sum_{i=1}^{N}\frac{1}{N}\mathbbm{1}\left[\|g_{x_{i}}\|>C_{t}\right]g_{x_{i}}\left(\frac{C_{t}}{\|g_{x_{i}}\|}-1\right)\right\|$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\frac{1}{N}\mathbbm{1}\left[\|g_{x_{i}}\|>C_{t}\right]G$
$\displaystyle=$ $\displaystyle P_{t}(C_{t})G,$ (48)

where $P_{t}(C_{t})$ denotes the probability of a per-sample gradient being
clipped at step $t$ given $\theta_{t}$ and $X$.

Then we know

$\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla
L(\theta_{t}),\mathbb{E}_{t}[g_{t}]\rangle\right]$ $\displaystyle=$
$\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla
L(\theta_{t}),\nabla L(\theta_{t})-\nabla
L(\theta_{t})+\mathbb{E}_{t}[g_{t}]\rangle\right]$ $\displaystyle\geq$
$\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|^{2}\right]$
$\displaystyle-\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|\|\nabla L(\theta_{t})-\mathbb{E}_{t}[g_{t}]\|\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|^{2}\right]$
$\displaystyle-\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|P_{t}(C_{t})G\right].$ (49)

Substituting (A.6) into the LHS of (A.6), we get

$\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|^{2}\right]$ $\displaystyle\leq$ $\displaystyle\frac{1}{\eta
T}(\mathbb{E}[L(\theta_{1})]-\mathbb{E}[L(\theta_{T+1})])+\frac{1}{T}\frac{Q}{2}\eta\sum_{t=1}^{T}\mathbb{E}[\|g_{t}\|^{2}]$
$\displaystyle+\frac{1}{T}\sum_{t=1}^{T}\frac{Q}{2}\frac{\eta}{N^{2}p^{2}}\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2}+\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|P_{t}(C_{t})G\right],$ (50)

which finish the proof for the first claim.

By substituting
$\widetilde{\sigma}=p\frac{1}{\mu_{\text{tot}}}\sqrt{2\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}_{t}^{2}}}$
from Corollary 2, assume $\widetilde{\sigma}_{t}=\Theta(1)$ and $L$ is lower
bounded, we can further get

$\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|^{2}\right]$ $\displaystyle\leq$ $\displaystyle\frac{1}{\eta
T}(\mathbb{E}[L(\theta_{1})]-\mathbb{E}[L(\theta_{T+1})])+\frac{1}{T}\frac{Q}{2}\eta\sum_{t=1}^{T}\mathbb{E}[\|g_{t}\|^{2}]$
$\displaystyle+{Q}\frac{\eta}{N^{2}\mu_{\text{tot}}^{2}}\frac{1}{T}\sum_{t=1}^{T}\widetilde{\sigma}_{t}^{2}{\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}_{t}^{2}}}$
$\displaystyle+\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|P_{t}(C_{t})G\right]$ $\displaystyle=$
$\displaystyle\mathcal{O}\left(\frac{1}{\eta
T}\right)+\mathcal{O}(\eta)+\mathcal{O}\left(\frac{\eta
T}{N^{2}\mu_{\text{tot}}^{2}}\right)$
$\displaystyle+\underbrace{\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|P_{t}(C_{t})G\right]}_{\text{bias term}}$ (51)

and after setting $\eta T=N\mu_{\text{tot}}$ and
$\eta=\frac{1}{N\mu_{\text{tot}}}$, we can reach the conclusion that the above
bound is $O(\frac{1}{N\mu_{\text{tot}}})+\text{bias term}$ which finishes the
whole proof.

###  A.7 On the optimal solution of minimizing Eq. (17)

The minimization problem is rewritten below ignoring the irrelevant constants

$\displaystyle\min_{\widetilde{\sigma}_{1},...,\widetilde{\sigma}_{T}}\sum_{t=1}^{T}\widetilde{\sigma}_{t}^{2}{\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}_{t}^{2}}}.$
(52)

The above problem can be transformed into an equivalent problem raised in
Theorem 4.2 and Remark 4.1 of Wu et al. (2021) which we restate below

$\displaystyle\min_{a_{1},...,a_{T}}\sum_{t=1}^{T}\frac{a_{t}^{2}}{b_{t}^{2}}\sum_{t=1}^{T}\frac{1}{a_{t}^{2}}$
(53)

And according to Remark 4.1 in Wu et al. (2021), an optimal solution to (53)
is $a_{t}^{2}=b_{t}$ which yields an optimal value of
$(\sum_{t=1}^{T}\frac{1}{b_{t}})^{2}$. Going back to (52), we can define
$a_{t}=\sigma_{t}/C_{t}$ and $b_{t}=1/C_{t}$ to transform (52) into (53).
Thus, we know an optimal solution to (52) would be

$\displaystyle
a_{t}^{2}=\frac{\widetilde{\sigma}_{t}^{2}}{C_{t}^{2}}=b_{t}=\frac{1}{C_{t}},$
(54)

which gives

$\displaystyle\widetilde{\sigma}_{t}=\sqrt{C_{t}}.$ (55)

###  A.8 Extension of Theorem 1 with local curvature assumption

In this section, we present a different version of Theorem 1 with a local
curvature assumption

$\displaystyle\mathbb{E}_{t}[L(\theta_{t+1})]-L(\theta)$ $\displaystyle\leq$
$\displaystyle\langle\nabla
L(\theta_{t}),\mathbb{E}_{t}[\theta_{t+1}-\theta_{t}]\rangle+\frac{Q_{t}}{2}\mathbb{E}[\|\theta_{t+1}-\theta_{t}\|^{2}].$
(56)

This assumption is not standard in optimization but the intuition is quite
straightforward. The assumption can be understood as the neighborhood region
around $\theta_{t}$ has a curvature bounded by $Q_{t}$, and the diameter of
the neighborhood is vaguely defined by some statistics about
$\theta_{t+1}-\theta_{t}$, which in turn depends on the algorithm choice.
Overall, this is an optimistic assumption on both the algorithm and the
problem. The motivation of such an assumption is to take account for the fact
that the local curvatures of different iterates in neural network training are
typically quite different.

With this assumption, we can rework Theorem 1 to obtain Theorem 2.

######  Theorem 2.

Denote the objective function as
$L(\theta)=\frac{1}{N}\sum_{i=1}^{N}f(\theta,x_{i})$ and the clipped
stochastic gradient at step $t$ as
$g_{t}=\frac{1}{p\left|X\right|}\big{[}\sum_{x\in
X_{t}}\text{CL}\left(g_{x};C_{t}\right)\big{]}$ where $g_{x}=\frac{\partial
f(\theta_{t},x)}{\partial\theta_{t}}$.

Assume (A.8) holds and each per-sample gradient is upper-bounded, i.e.
$\|g_{x}\|\leq G,\forall t$. General dynamic DP-SGD (Algorithm 3) satisfies
the following utility guarantee

$\displaystyle\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|^{2}\right]$ $\displaystyle\leq\frac{1}{\eta
T}\mathbb{E}[L(\theta_{1})]-L(\theta_{T+1})]+\frac{\eta}{T}\sum_{t=1}^{T}\frac{Q_{t}}{2}\mathbb{E}[\|g_{t}\|^{2}]$
$\displaystyle+\underbrace{\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}\|\nabla
L(\theta_{t})\|P_{t}(C_{t})G\right]}_{\text{bias
term}}+\frac{\eta}{p^{2}N^{2}}\underbrace{\frac{1}{T}\sum_{t=1}^{T}\frac{Q_{t}}{2}\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2}}_{D_{2}}.$
(57)

where $P_{t}(C_{t})$ is the probability of a per-sample gradient being clipped
with threshold $C_{t}$ at $\theta_{t}$, and the expectations are take over all
randomness including gradient sampling and noise sampling.

Proof: The proof follows the same procedure as that of Theorem 1 with $Q$ in
(A.6) replaced by $Q_{t}$, i.e., we get the following version of (A.6)

$\displaystyle\mathbb{E}_{t}[L(\theta_{t+1})]\leq$ $\displaystyle
L(\theta_{t})+\mathbb{E}_{t}[\langle\nabla
L(\theta_{t}),(\theta_{t+1}-\theta_{t})\rangle]$
$\displaystyle+\mathbb{E}_{t}[\frac{Q_{t}}{2}\|\theta_{t+1}-\theta_{t}\|^{2}]$
$\displaystyle\leq$ $\displaystyle L(\theta_{t})-\eta\langle\nabla
L(\theta_{t}),\mathbb{E}_{t}[g_{t}]\rangle+\frac{Q_{t}}{2}\eta^{2}\mathbb{E}_{t}[\|g_{t}\|^{2}]$
$\displaystyle+\frac{Q_{t}}{2}\frac{\eta^{2}}{N^{2}p^{2}}\widetilde{\sigma}^{2}\widetilde{\sigma}_{t}^{2}.$
(58)

All the remaining steps are the same as those in Theorem 1 with $Q$ replaced
and thus we omit them.

Remark on the variance term $D_{2}$: It is straightforward to see that just
like in Theorem 1, we can minimize the corresponding variance term $D_{2}$ by
substituting the $\widetilde{\sigma}$ expression from Theorem 2 and tuning
$\widetilde{\sigma}_{1},...,\widetilde{\sigma}_{T}$. However, the minimization
problem is slightly different due to $Q_{t}$, the problem is written below
ignoring irrelevant constants

$\displaystyle\min_{\widetilde{\sigma}_{1},...,\widetilde{\sigma}_{T}}\sum_{t=1}^{T}{Q_{t}}\widetilde{\sigma}_{t}^{2}{\sum_{t=1}^{T}\frac{C_{t}^{2}}{\widetilde{\sigma}_{t}^{2}}}.$
(59)

This problem can also be transformed in to the form of 53 by defining
$a_{t}=\sigma_{t}/C_{t}$ and $b_{t}=1/(C_{t}\sqrt{Q_{t}})$. And according to
the optimal solution $a_{t}^{2}=b_{t}$, we have

$\displaystyle
a_{t}^{2}=\frac{\sigma_{t}^{2}}{C_{t}^{2}}=b_{t}=\frac{1}{C_{t}\sqrt{Q_{t}}},$
(60)

which indicates

$\displaystyle\widetilde{\sigma}_{t}=\frac{\sqrt{C_{t}}}{{Q_{t}^{1/4}}},$ (61)

and thus

$\displaystyle\mu_{t}=\frac{C_{t}}{\widetilde{\sigma}\cdot\widetilde{\sigma}_{t}}\propto\sqrt{C_{t}}Q_{t}^{1/4}.$
(62)

Such a result indicates one should also change privacy budget of different
steps according to local curvatures. And if assuming the local curvatures of
different steps follow some general rules or distributions, one could design
corresponding strategies to allocate the privacy budget. Yet, identifying such
rules and distributions is a difficult task and could depend on the
application domains. We hope the theoretical analysis here could help inspire
future exploration in this direction.

###  A.9 Experimental Settings on Different Data Sets

MNIST (Lecun & Bottou, 1998) that contains 60000 training samples and 10,000
testing samples with ten balanced classes. Each gray-scale sample is stored as
a $28\times 28$ matrix. The classification model used in our experiments
consists of two convolution layers and two fully connected layers. Following
each convolution layer is a max-pooling layer with a pooling size of $2\times
2$. For activations, we use ReLU and for classification, we use softmax.
Cross-entropy loss is used.

In the experiment, initial clipping value is set to 1.5 and learning rate is
set to 0.15. We set $p=\frac{250}{60000}$ for the subsampling with independent
Bernoulli trial. All the results are the average over 5 times repeated
experiments.

FashionMNIST is a dataset of Zalando’s article images, serving as an
alternative to MNIST dataset for benchmarking machine learning algorithms. It
shares the same image size and structure of training and testing splits. As a
result, we use the same experimental setup as MNIST. The only difference is
that we specified a clipping value of 4 as the initial value.

IMDB For natural language processing or text analytics, the IMDB dataset
contains 50K movie reviews. This is a binary sentiment classification dataset.
We use a three-layer network with one embedding layer and two fully connected
layers; this can be viewed as an MLP model because the embedding layer is a
special implementation of fully connected layers. We train for 25 epochs with
the DP-Adam optimizer, with the initial clipping value set to be 2.

NAME is a name classification dataset containing person names from 18
countries. It is available on Pytorch NLP
tutorials444https://pytorch.org/tutorials/intermediate/char_rnn_classification_tutorial.html.
We train a LSTM model to determine which country the given name belongs to.
The name is treated as a sequence, and the characters are fed into LSTM one by
one. We use a one-layer LSTM with hidden size 128 and embedding size 64
followed by a fully connected layer, an SGD optimizer with learning rate 2 and
we train 50 epochs for each experiment, and the initial clipping value is set
to be 1.5.

InfiniteMNIST and Federated Learning  InfiniteMNIST is a dataset consisting of
massive training samples derived from origin MNIST by applying different types
of transformations. Such large scale dataset is suitable for a federated
setting. We extract 250K and 500K images as two training data sets and
simulate identical number of clients. Thus each client is not enough to train
the model, but they can cooperatively learn a model via federated learning. We
use the same network structure as in the experiment for MNIST for each client.

Federated Learning Algorithm Fed-SGD algorithm is used for optimization. For
each round, we randomly sample clients with sampling rate $p=1\times 10^{-3}$
for the case of MNIST-250K and $p=5\times 10^{-4}$ for the case of MNIST-500K.
Gradients are computed on each selected client and then sent to the server for
aggregation. In this setting, local DP mechanism is required to protect client
side gradients, and each client apply clipping and additive noise on local
gradients before transmission. The server will aggregate noised gradients,
which achieves central DP. The details is provided in the following Algorithm
5.

Algorithm 5 Federated Dynamic DP-SGD Algorithm

0: Clients set $\mathcal{S}$, DP budget $(\epsilon,\delta)$, client sampling
rate $p$, dataset $X$ = ($X_{1},X_{2}...X_{|\mathcal{S}|}$), training rounds
$T$, hyper-parameters: $\rho_{\mu}$, $\rho_{c}$ and $C_{0}$.

1: Compute $\mu_{0}$ in Algorithm 1

2: for $t=0,\ldots,T-1$ do

3: Compute $C_{t}=(\rho_{c})^{-\frac{t}{T}}\cdot C_{0}$ according to (12)

4: Calibrate noise :
$\sigma_{t}=\frac{C_{0}}{\mu_{0}}(\rho_{\mu}\cdot\rho_{c})^{-\frac{t}{T}}$

5: Sample clients for the $t$-th iteration, i.e.,
$\mathcal{S}_{t}\in\mathcal{S}$ with Poisson sampling rate $p$.

6: for $k\in S_{t}$ do

7:
$g_{k,t}=\frac{1}{\left|\mathcal{S}_{t}\right|}\left(\sum_{x\in\mathcal{S}_{t}}\left(g_{x};C_{t}\right)+\xi_{k,t}\right)$
with $\xi_{k,t}\sim\mathcal{N}(0,\sigma^{2}I)$

8: Send $g_{k,t}$ to the server.

9: end for

10: Server computes:
$\theta_{t+1}=\theta_{t}-\eta\frac{1}{\left|\mathcal{S}_{t}\right|}\left(\sum_{k\in\mathcal{S}_{t}}g_{k}\right)$

11: end for

###  A.10 VGG network and Chest Radiographs

We evaluated VGG on chest radiographs classification task from the Paediatric
Pneumonia dataset described in Ziller et al. (2021), which is a binary
classification task, and the model attempts to predict whether the radiograph
shows signs of pneumonia or not. For the classification task, following that
in Ziller et al. (2021), we utilized the same model architecture in the
private and nonprivate setting, namely a VGG-11 architecture. Following Ziller
et al. (2021), batch normalization layers was disabled for both non-private
and DP training.