# Batch Clipping and Adaptive Layerwise Clipping for Differential Private
Stochastic Gradient Descent

Toan N. Nguyen${}^{1^{*}}$, Phuong Ha Nguyen${}^{2^{*}}$, Lam M.
Nguyen3,Marten van Dijk4,5,6

1 Department of Computer Science and Engineering, University of Connecticut,
CT, USA
2 eBay, CA, USA
3 IBM Research, Thomas J. Watson Research Center, Yorktown Heights, NY, USA
4 CWI Amsterdam, The Netherlands
5 Department of Computer Science, Vrije Universiteit Amsterdam, The
Netherlands
6 Department of Electrical and Computer Engineering, University of
Connecticut, CT, USA

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

Each round in Differential Private Stochastic Gradient Descent (DPSGD)
transmits a sum of clipped gradients obfuscated with Gaussian noise to a
central server which uses this to update a global model which often represents
a deep neural network. Since the clipped gradients are computed separately,
which we call Individual Clipping (IC), deep neural networks like resnet-18
cannot use Batch Normalization Layers (BNL) which is a crucial component in
deep neural networks for achieving a high accuracy. To utilize BNL, we
introduce Batch Clipping (BC) where, instead of clipping single gradients as
in the orginal DPSGD, we average and clip batches of gradients. Moreover, the
model entries of different layers have different sensitivities to the added
Gaussian noise. Therefore, Adaptive Layerwise Clipping methods (ALC), where
each layer has its own adaptively finetuned clipping constant, have been
introduced and studied, but so far without rigorous DP proofs. In this paper,
we propose a new ALC and provide rigorous DP proofs for both BC and ALC.
Experiments show that our modified DPSGD with BC and ALC for CIFAR-$10$ with
resnet-$18$ converges while DPSGD with IC and ALC does not.

00footnotetext: ∗ these authors contributed equally.

##  1 Introduction

Differential Private Stochastic Gradient Descent (DPSGD) [1] combines
Stochastic Gradient Decent (SGD) [19] and Differential Privacy (DP)[8] to
train deep neural networks privately. It has been widely studied since its
introduction.

In each round of DPSGD a mini-batch of $m$ samples
$\xi_{i_{1}},\dotsc,\xi_{i_{m}}$ from a larger data set
$d=\\{\xi_{i}\\}_{i=1}^{N}$ of $N$ samples is randomly subsampled:

$\\{i_{1},\ldots,i_{m}\\}\leftarrow{\tt Sample}_{m}(N).$ (1)

The global model $w$ is updated by first computing gradients
$\nabla_{w}f(w;\xi_{i_{j}})$ for each sample $\xi_{i_{j}}$ given loss function
$f$. Each gradient is clipped by using a clipping operation
$[x]_{C}=x/\max\\{1,\|x\|/C\\}$ where $C$ denotes a fixed clipping constant.
The clipped gradients are aggregated in a sum after which a noise vector $n$
drawn from a Gaussian distribution111$\mathbf{I}$ is the identity correlation
matrix of the multivariate Gaussian distribution. The factor $2$ is due to
sampling exactly $m$ data points every round; by using a Poisson process to
probabilistically sample $\xi\in d$ such that in expectation the mini-batch
has size $m$ removes the factor 2 and leads to better DP. This is implemented
in [18]. In order to simplify our exposition we work with deterministic
sampling and keep the factor 2. $\mathcal{N}(0,(2C\sigma\mathbf{I})^{2})$ is
added. The resulting "noised and clipped" update $U$ is transmitted to a
central server where it is averaged over the size $m$ of the used mini-batch
and multiplied by a step-size $\mu$ before subtracting it from the global
model:

$\displaystyle U$ $\displaystyle:=$ $\displaystyle
n+\sum_{j=1}^{m}[\nabla_{w}f(w;\xi_{i_{j}})]_{C}\ \ \ \ \mbox{ and }\ \ \ \
w:=w-\frac{\eta}{m}U.$ (2)

In DPSGD, $\sigma$ translates to a DP guarantee and is chosen carefully by the
designer to balance DP and the accuracy of the final global model.

The global model is represented by a weight vector $w$ which can be written as
a concatenation $(w_{1}|\ldots|w_{L})$ where $w_{h}$ corresponds to the $h$-th
layer in the neural network which is being trained. DPSGD uses a fixed
clipping constant $C$ for clipping gradients

$\nabla_{w}f(w;\xi_{i_{j}})=(\nabla_{w_{1}}f(w;\xi_{i_{j}})|\ldots|\nabla_{w_{L}}f(w;\xi_{i_{j}})).$

In expectation the norms $\|\nabla_{w_{h}}f(w;\xi_{i_{j}})\|$ of different
layers $h$ in a deep neural network model vary layer by layer. This makes
different layers have different sensitivity to the added Gaussian noise. For
this reason, [20, 21, 22] proposed222For completeness, per-layer clipping was
originally introduced in DP-FEDAVG [16] where a clipping budget is evenly (not
customized) distributed among all layers and a DP guarantee is proven based on
the moment accountant from [1]. Adaptive Layerwise Clipping (ALC) which tunes
the added Gaussian noise with respect to the (sensitivity of the) layer. Each
layer of the model has its own customized clipping constant based on
estimating the expectation of the gradient norms of each layer by sampling a
given small public dataset $\mathcal{D}_{pub}$. We notice that [20, 21, 22]
have not provided rigorous DP proofs for ALC. In this paper we prove DP
guarantees for ALC and we enhance the ALC method of [22] for improved test
accuracy.

Besides the enhanced ACL, we introduce Batch Clipping (BC) where (2) is
replaced by

$\displaystyle U$ $\displaystyle:=$ $\displaystyle
n+\left[\frac{1}{m}\sum_{j=1}^{m}\nabla_{w}f(w;\xi_{i_{j}})\right]_{C}\ \ \ \
\mbox{ and }\ \ \ \ w:=w-\eta U.$ (3)

BC allows us to first compute an average of a batch of gradients before
clipping, as opposed to (2) which averages a sum of clipped individual
gradients; for this reason we call (2) the Individual Clipping (IC) approach.
BC gives us the ability to properly train Batch Normalization Layers (BNL)
[13] in a neural network; in very deep neural networks the use of BNLs is
crucial for achieving high accuracy. The BC and ALC techniques are
complimentary and can be implemented in parallel, also BC and ALC do not
require any changes to be made in deep neural networks, i.e., BC and ALC apply
directly without modifications to the neural network that we wish to train.
This makes our training framework with BC and ALC flexible. BC allows us to
use resnet-18[11] (which uses BNLs) in our experiments and have a DP
guarantee. DPSGD without BC cannot properly train BNLs, therefore, DPSGD with
IC (even with ALC) for resnet-18 does not converge and leads to poor accuracy,
while DPSGD with BC and the enhanced ALC does converge. In the context of
DPSGD we are the first to introduce BC together with proving its DP guarantee;
no prior related work on DPSGD with BC exists.

Our main contribution are:

  * •

We propose an enhanced Adaptive Layerwise Clipping method based on [22]. Our
experiments show that DPSGD with our enhanced ALC converges faster to a higher
accuracy.

  * •

We prove and characterize the DP guarantee for ALC by using the $f$-DP
framework [5]. We explain how layerwise clipping degrades DP and we show how
to set the noise parameters of DPSGD without ALC and DPSGD with ALC so that
they have the same DP guarantee and their test accuracy can be fairly
compared.

  * •

We introduce and propose to use Batch Clipping during training. We also define
General Batch Clipping (GBC) of which BC and IC are special cases and notice
that GBC is compatible with any first order optimizers in mini-batch mode. BC
allows us to implement Batch Normalization Layers which are crucial for
attaining high accuracy for deep neural networks (BNLs cannot be trained
properly by the original DPSGD which uses Individual Clipping).

  * •

For proving differential privacy guarantees it is commonly understood that the
privacy argument does not depend on how the gradients in the clipped values in
(2) are computed; the to-be-clipped values may as well be computed as in (3).
This shows that (the original) DPSGD with IC given by (2) and (the new) DPSGD
with BC given by (3) offer the exact same DP guarantee (also if both implement
ALC).

  * •

Our experiments show that DPSGD modified by using our enhanced ACL and using
BC allows us to train the deep neural network resnet-$18$ [11] (which uses
BNL) on CIFAR10 [14] while DPSGD with ALC and IC does not converge. This shows
that BC outperforms IC in practice.

Our main conclusion is that ACL and BC are two techniques that provide a
better balance between DP and accuracy. However, our experiments are for small
$\sigma$ which corresponds to weak differential privacy. We still need
additional techniques beyond ALC and BC for training a deep neural network
like resnet-18 with CIFAR10 in order to achieve a practical balance between
test accuracy and DP guarantee.

Outline: We first provide the necessary background on $f$-DP in Section 2.
Section 3 introduces BC (and GBC), layerwise clipping and our ACL, and proves
DP guarantees in the $f$-DP framework. Experiments are in Section 4. Section 5
concludes our paper.

##  2 Background on $f$-DP

DP literature first introduced $\epsilon$-DP [9], later relaxed to
$(\epsilon,\delta)$-DP [10]. In order to have a better dependency on group
privacy and to improve adaptive composibility, the notion of Concentrated
Differential Privacy (CDP) [7] was introduced. CDP was re-interpreted and
relaxed by using Renyi entropy in [2] and its authors followed up with the
notion of zero-CDP (zCDP) in [3]. This notion admits simple interpretable DP
guarantees for adaptive composition and group privacy. After the introduction
of $\rho$-zCDP, Renyi DP (RDP) was introduced by [17]. Combining the ideas
that give rise to the zCDP and RDP definitions leads naturally to the
definition of $(\rho,\omega)$-tCDP [4] which relaxes zCDP. All of these
various DP measures have been superseded by $f$-DP [6]since (1) $f$-DP can be
transformed/translated into divergence based DP guarantees (but generally not
the other way around) and can be translated into $(\epsilon,\delta)$-DP, and
since (2) $f$-DP analyses the underlying core hypothesis testing problem
directly and derives a tight (or exact) DP guarantee (for the adversarial
model considered in the proofs of DP guarantees in literature). The $f$-DP
framework is tight and contains all the information needed to derive other
known DP metrics. Below we summarize $f$-DP and show how to use $f$-DP to
prove and formulate the DP guarantee of our modified DPSGD algorithm.

We call data sets $d=\\{\xi_{i}\\}_{i=1}^{N}$ and
$d^{\prime}=\\{\xi^{\prime}_{i}\\}_{i=1}^{N}$ neighboring if they differ in
one element; without loss of generality $\xi_{i}=\xi^{\prime}_{i}$ for $1\leq
i\leq N-1$ and $\xi_{N}\neq\xi^{\prime}_{N}$ coined the differentiating
sample. In DP a mechanism ${\cal M}$ is a process that takes either data set
$d$ or data set $d^{\prime}$ as input and outputs a sequence of observables
which the adversary uses to distinguish which of $d$ or $d^{\prime}$ has been
used. DPSGD is a mechanism which outputs a sequence of updates $U$
corresponding to each round, see (2). Below, we adopt the notion and
explanation provided in [5] for our short introduction of $f$-DP. We refer the
reader to [5] for a full description.

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:

$\mbox{versus }\begin{array}[]{l}H_{0}:\mbox{ the underlying data set is }d\\\
H_{1}:\mbox{ the underlying data set is }d^{\prime}.\end{array}$

We define the Type I and Type II errors by

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

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

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

for $\alpha\in[0,1]$, where the infimum is taken over all measurable rejection
rules $\phi$. If the two 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, at least $0$, and $f(x)\leq 1-x$ for
$x\in[0,1]$. We define a mechanism ${\cal M}$ to be $f$-DP if $f$ is a trade-
off function and for all neighboring $d$ and $d^{\prime}$,

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

Gaussian DP: Gaussian DP is defined as a special case of $f$-DP where $f$ is
defined as a trade-off function

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

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

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

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

Subsampling: Besides implementing Gaussian noise which bootstraps DP, DPSGD
also uses ${\tt Sample}_{m}$ for subsampling which amplifies DP. [6] defines a
subsampling operator $C_{m/N}$ and shows that if a mechanism ${\cal M}$ on
data sets of size $N$ is $f$-DP, then the subsampled mechanism ${\cal
M}\circ{\tt Sample}_{m}$ is $C_{m/N}(f)$-DP. We have that the mechanism
corresponding to one round in DPSGD is $C_{m/N}(G_{1/\sigma})$-DP (and this is
a tight analysis).

Composition: If DPSGD implements $T$ rounds, then the privacy leakage across
rounds composes. [6] defines a commutative tensor product $\otimes$ for trade-
off functions and shows this can be used to characterize adaptive
composibility: Let ${\cal M}_{i}$ be the mechanism corresponding to the $i$-th
round with $y_{i}\leftarrow{\cal M}_{i}(\texttt{aux},d)$ where
$\texttt{aux}=(y_{1},\ldots,y_{i-1})$ (this captures adaptivity). If ${\cal
M}_{i}(\texttt{aux},.)$ is $f_{i}$-DP for all aux, then the composed mechanism
${\cal M}$, which applies ${\cal M}_{i}$ in sequential order from $i=1$ to
$i=T$, is $(f_{1}\otimes\ldots\otimes f_{T})$-DP. This leads to a tight
analysis of DPSGD. We have that DPSGD as introduced in [1] is

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

Notice that if DPSGD computes a total of $E$ epochs of gradients, i.e., $EN$
gradient computations in total, then $T=(N/m)\cdot E$ (since each round
computes $m$ gradients). We have

$C_{m/N}(G_{1/\sigma})^{\otimes(N/m)\cdot E}\mbox{-DP}.$ (4)

##  3 Application $f$-DP toward a Modified DPSGD

We discuss two main DPSGD modifications. The first is coined Batch Clipping
(BC) and the second Layerwise Clipping (LC) leading to Adaptive LC (ACL).

###  3.1 Batch Clipping

The presented $f$-DP analysis is more general in that it holds for (2) where
$U$ is not just computed as a noised sum of clipped gradients but computed as

$U:=n+\sum_{j=1}^{m}[g(w;\xi_{i_{j}})]_{C}$ (5)

for some other fixed function $g$.

Suppose that we partition data set $d$ of size $N$ into $N/s$ mini-sets of
size $s$ each. We use this to define a new data set $d_{s}$ which has as
elements the $N/s$ mini-sets, which we denote as $S_{i}$, $1\leq i\leq N/s$.
Data set $d_{s}$ has size $N/s$ and its samples are mini-sets $S_{i}$ of size
$s$. Each $S_{i}$ contains $s$ data points $\xi_{j}$ from $d$. We apply DPSGD
to this new data set $d_{s}$ for the general (5) where we replace $m$ by $k$.
This yields

$U:=n+\sum_{j=1}^{k}[g(w;S_{i_{j}})]_{C}.$ (6)

We call this General Batch Clipping (GBC) since we clip vectors
$g(w;S_{i_{j}})$ which are computed based on a batch (mini-set)
$S_{i_{j}}\subseteq d$ of data points from $d$. Notice that in GBC, $g$ can
implement any moment based SGD type algorithm that iteratively scans the data
points in $S_{i_{j}}$.

Applying the $f$-DP analysis for DPSGD for a data set $d_{s}$ of size $N/s$
with ${\tt Sample}_{k}$, see (6), yields $C_{k/(N/s)}(G_{1/\sigma})^{\otimes
T}\mbox{-DP}$, see Section 2. By setting $m=sk$, we conclude
$C_{m/N}(G_{1/\sigma})^{\otimes T}\mbox{-DP}$. Notice that if the modified
DPSGD with GBC computes a total of $E$ epochs of gradients, then again
$T=(N/m)\cdot E$ since each round still computes $m=sk$ gradients. For GBC
with $m=sk$ we conclude the exact same DP guarantee as the one for (4).

In our experiments we use the special case

$g(w;S_{i_{j}})=\frac{1}{s}\sum_{\xi\in S_{i_{1}}}\nabla_{w}f(w;\xi)$ (7)

with $k=1$ and $s=m$ in GBC (with $m=sk$). We refer to this as (non-general)
Batch Clipping (BC) (since we clip $g(w;S_{i_{1}})$ which computes and
averages a batch of gradients), see (3). We call the original DPSGD
formulation (2) Individual Clipping (IC) since single/individual gradients are
clipped; for completeness, this is the case $s=1$ with $k=m$ in GBC (with
$m=sk$).

###  3.2 Layerwise Clipping

Layerwise Clipping (LC) [16, 20, 21, 22] splits vectors $g=g(w;S_{i,j})$ in
parts $g=(g_{1}|\ldots|g_{L})$ (i.e., $g$ is equal to the concatenation of
parts $g_{1}$, $\ldots$, $g_{L}$) and clip each part $g_{h}$ separately, i.e.,
we define

$[g]_{(C_{1},\ldots,C_{L})}=([g_{1}]_{C_{1}}|\ldots|[g_{L}]_{C_{L}}).$

The different $g_{i}$ correspond to the different layers in the neural
network. We compute noise $n$ in (6) as the concatenation

$n=(n_{1}|\ldots|n_{L})\ \ \ \ \mbox{ with }\ \ \ \ n_{h}\sim{\cal
N}(0,(2C_{h}\sigma){\bf I}),$

where the different matrices ${\bf I}$ have sizes that correspond to the
number of entries in the various $g_{h}$.

In order to understand how the DP guarantee is affected, we rewrite (6) as
follows:

$U:=(U_{1}|\ldots|U_{L})\ \ \ \ \mbox{ where }\ \ \ \
U_{h}=n_{h}+\sum_{j=1}^{k}[g_{h}(w;S_{i_{j}})]_{C_{h}}.$

In other words, transmission of $U$ is equal to transmitting $U_{h}$, $1\leq
h\leq L$. Each $U_{h}$ can be considered as a round update where we use
clipping constant $C_{h}$ and noise ${\cal N}(0,(2C_{h}\sigma){\bf I})$. The
$f$-DP analysis shows that such a round is $G_{1/\sigma}$-DP (see the
explanation of Gaussian DP with sensitivity $c=2C_{h}$). We have $L$ such sub-
rounds that make up the whole transmission of $U$. By composition, we have
that this gives $G_{1/\sigma}^{\otimes L}$-DP. [6] shows that333We can also
vary the noise from layer to layer and use $\sigma/p_{h}$ instead of $\sigma$.
This leads to $G_{p_{1}/\sigma}\otimes\ldots\otimes
G_{p_{L}/\sigma}=G_{\sqrt{\sum_{h=1}^{L}p_{h}^{2}}/\sigma}$.
$G_{1/\sigma}^{\otimes L}=G_{\sqrt{L}/\sigma}$.

We conclude that in the DP guarantee (4) we need to replace $\sigma$ by
$\sigma/\sqrt{L}$ for the modified DPSGD with BC/IC and LC. If we want to
compare this in a fair way with the modified DPSGD with BC/IC and no LC (we
keep the original gradient clipping approach), then we should use

$\bar{\sigma}:=\sigma/\sqrt{L}$

as the privacy parameter $\sigma$ in the modified DPSGD (as this will result
in the same (4) with $\sigma$ replaced by $\bar{\sigma}=\sigma/\sqrt{L}$).

Clearly, we want to be careful about the number of layers $L$ we can handle
since the privacy parameter $\sigma$ is divided by $\sqrt{L}$. We notice that
we can group layers together and split vectors $g=g(w;S_{i,j})$ into a smaller
number of parts giving a smaller $L$ which leads to a better DP guarantee.

###  3.3 Adaptive LC

Figure 1: resnet-18 model layerwise gradient norms. We grouped the lines by
the layer’s type: "conv" is convolutional layer, "bn" is the batch
normalization layer, "shortcut" is the shortcut connecting non-adjacent two
layers, "linear" is the fully connected layer (in this case this layer
corresponds to a softmax layer)

The Adaptive LC (ALC) of [22] uses a public dataset $\mathcal{D}_{pub}$ to
estimate expectations of the layer gradient norms
$\|\nabla_{w_{h}}f(w;\xi)\|$. These estimates are used as the layerwise
clipping constants $C_{h}$. For standard SGD without DP, [12] explains that
even if model $w$ converges, the gradient norms of different layers may not
decrease throughout the training. We confirm this in Figure 1, which depicts
layer gradient norms of resnet-18 trained without DP over 50 epochs. We
observe that most layer gradient norms only slowly decrease from epoch to
epoch. Therefore, most of the $C_{h}$ in the ALC of [22] are only slightly
adapted from epoch to epoch. This implies that, for such a layer $h$, the
distribution ${\cal N}(0,(2C_{h}\sigma)^{2}{\bf I})$ of the Gaussian noise
added to each of the weight entries in layer $h$ does not change much either.
This setup does not allow the designer to optimize the clipping constants
$C_{1},\dotsc,C_{L}$ to make convergence faster.

We enhance the adaptive clipping strategy of [22]: First, we determine a
master clipping constant $C$ for each round. We do not impose a restriction on
how $C$ is chosen, i.e., it can diminish from epoch to epoch or $C$ can be the
same constant for all rounds. In our experiments $C$ is a constant throughout
the whole training. Second, we use $C$ to derive clipping values
$(C_{1},C_{2},...,C_{L})$ for the corresponding round. This has the property
that each $C_{h}$ scales linearly with $C$.

Given a master clipping constant $C$ at the beginning of each round, we use a
public dataset $\mathcal{D}_{pub}$ to derive clipping constants
$(C_{1},C_{2},...,C_{L})$. The reason for using a public dataset is that we do
not need to worry about privacy leakage revealed by $(C_{1},C_{2},...,C_{L})$;
DP analysis/proofs, where the adversary knows $(C_{1},C_{2},...,C_{L})$, may
proceed as before. We estimate the expectation $e=(e_{1},\ldots,e_{L})$ of the
layer gradient norms
$(\|\nabla_{w_{1}}f(w;\xi)\|,\ldots,\|\nabla_{w_{L}}f(w;\xi)\|)$ over
$\xi\in\mathcal{D}_{pub}$ for $w=(w_{1}|\ldots|w_{L})$. We compute the maximum
gradient norm among all layers, i.e., $M=\max_{h=1}^{L}e_{h}$. Then, for each
layer $h$ we define $C_{h}=C\cdot e_{h}/M$. See Section 4.4, Figure 4 shows
that our enhanced ALC allows DPSGD with BC to converge faster to a higher
accuracy compared to DPSGD with BC and the original ALC of [22].

###  3.4 Sparsification

We notice that the public data set $\mathcal{D}_{pub}$ in adaptive clipping
can also be used to find out whether certain weight entries in $w$ have
converged sufficiently. That is, we say a weight entry has converged if, over
a large number of recent rounds, it hoovers around an average with standard
deviation corresponding to the added DP noise. As soon as this is the case, we
may fix the weight entry to this average in all future computations/rounds
(since this is a form of post processing, no additional DP leakage occurs).
This reduces the number of weight entries over which we need to compute
gradients and each level gets less weight entries as soon as convergence sets
in. This allows us to use even smaller clipping constants per layer (depending
on the number of active weight entries in the layers). We leave this
optimization as an open problem.

##  4 Experiments

###  4.1 Setup

Data preprocessing: We perform experiments on the CIFAR-10 dataset which
consists of 50,000 training examples and 10,000 test examples, divided into 10
classes, with each example being a 32x32 image with three color channels
(RGB)([14]). In our experiments, we perform data augmentation and data
normalization independently. Specifically, for each training image, we crop a
$32\times 32$ region from it with padding of 4, apply a random horizontal flip
to the image, and then normalize it with

$(mean,std)=((0.4914,0.4822,0.4465),(0.2023,0.1994,0.2010)).$

Next, we divide the CIFAR-10 dataset $\mathcal{D}$ into two dataset
$\mathcal{D}_{pub}$ and $\mathcal{D}_{train}$ where
$|\mathcal{D}_{pub}|=\frac{1}{10}|\mathcal{D}|$ and
$|\mathcal{D}_{train}|=\frac{9}{10}|\mathcal{D}|$.

As explained in Section 3.3, we estimate the expectation
$(e_{1},\ldots,e_{L})$ of the layer gradient norms
$(\|\nabla_{w_{1}}f(w;\xi)\|,\ldots,\|\nabla_{w_{L}}f(w;\xi)\|)$ over444We
notice that we may not need a large sized ${\cal D}_{pub}$ for a good
estimate. $\xi\in{\cal D}_{pub}$, where $w=(w_{1}|\ldots|w_{L})$ is the
current model. We compute the layerwise clipping constants $(C_{1}=C\cdot
e_{1}/M,\dots,C_{L}=C\cdot e_{L}/M)$ with $M=\max_{h=1}^{L}e_{h}$ and master
clipping constant $C$ .

We sample the $m$-sized training data batches with replacement from
$\mathcal{D}_{train}$ at the beginning of each epoch and feed them to the
machine learning model to train the model.

Diminishing Learning Rate and Fixed Master Clipping Constant: We fix the
master clipping constant $C$ throughout the training process and after each
epoch we update the learning rate $\eta$ as

$\displaystyle\eta$ $\displaystyle:=$ $\displaystyle\eta\cdot\eta_{decay},$

where $\eta_{decay}$ is a decaying factor. After each epoch, we re-compute the
layerwise clipping constants $(C_{1},C_{2},\dots,C_{L})$ as explained above.
In our experiments, we set $\eta_{decay}=0.9$, $C=0.095$ and $\sigma=0.01875$.

Model Update: resnet-18 is updated by our modified DPSGD with BC and ALC,
i.e., for a batch (mini-set) $\\{\xi_{i_{1}},\ldots,\xi_{i_{m}}\\}$ we compute

$\displaystyle U$ $\displaystyle:=$ $\displaystyle
n+\left[\frac{1}{m}\sum_{j=1}^{m}\nabla_{w}f(w;\xi_{i_{j}})\right]_{(C_{1},\dotsc,C_{L})}\
\ \ \ \mbox{ and }\ \ \ \ w:=w-\eta U$

with $n\sim{\cal N}(0,(2C_{1}\sigma)^{2}{\bf I})\times\ldots\times{\cal
N}(0,(2C_{L}\sigma)^{2}{\bf I})$.

###  4.2 Benchmark versus BC

We compare our DPSGD with BC and ALC versus mini-batch SGD without DP, i.e.,
without clipping and without adding Gaussian noise. In both cases, we train
resnet-18 on the CIFAR-10 dataset.

For mini-batch SGD with diminishing learning rate without DP we experiment
with mini-batch sizes $m=(64,128,256,512,1024)$ and initial learning rate
$\eta=0.025$. The best test accuracy at epochs 20 and 50 is realized by mini-
batch size $m=64$ and achieves $88.31\%$ and $90.24\%$ (see Figure 2). The
results of our DPSGD with BC and ALC and diminishing learning rate, with fixed
master clipping constant $C=0.0095$, with standard deviation $\sigma=0.01875$,
and with $m=(64,128,256,512,1024)$ and initial learning rate $\eta=0.025$ are
presented in Figure 3. We achieve $60\%$ and $67\%$ at epochs 20 and 50 for
$m=64$.

Figure 2:  Test accuracies of mini-batch SGD without DP for different mini-
batch sizes $m=(64,128,256,512,1024)$ Figure 3:  Test accuracies of
DPSGD+BC+ALC vs mini-batch SGD without DP for different mini-batch sizes
$m=(64,128,256,512,1024)$

###  4.3 IC versus BC

We compare our DPSGD with BC and ALC versus DPSGD with IC and the same ALC.
The latter is the original DPSGD [1] combined with ALC. Based on the result
from Section 4.2, we choose $m=64$ which gives the best test accuracy for
fixed master clipping constant $C=0.0095$ and initial learning rate
$\eta=0.025$. We report the test accuracies after $E=50$ epochs for
$\sigma=0.01875$ in Figure 4. We observe that BC converges while IC does not.

###  4.4 Zhang’s ALC versus ours

As discussed in Section 3.3, the layerwise clipping constants
$C_{1},\dotsc,C_{L}$ in [22] may not change from epoch to epoch because the
layer gradient norms of resnet18 do not significantly change throughout the
training process as depicted in Figure 1. We explained that this may hurt the
convergence if $C_{1},\dotsc,C_{L}$ are not optimized. Based on this
observation, our proposed enhanced ALC implements a master clipping constant
$C$ which allows us to optimize layer clipping constants $C_{1},\dotsc,C_{L}$.
By tuning the initial/fixed master clipping constant $C$, DPSGD with BC and
our enhanced ALC offers a better performance compared to DPSGD with BC and the
ALC method of [22].

We run DPSGD with BC and the our enhanced ALC method with initial learning
rate $\eta=0.025$, fixed master clipping constant $C=0.0095$, and $m=64$ over
50 epochs for resnet-18 and CIFAR-10. We run DPSGD with BC and the ALC of [22]
with the same learning rate $\eta=0.025$ and $m=64$ over 50 epochs for
resnet-18 and CIFAR-10. The results are shown in Figure 4.

Figure 4: Comparison of the test accuracies between our enhanced ALC and the
ALC method of [22], both with BC. Moreover, we run our enhanced ALC in IC mode
so that we can also compare BC versus IC. ("Zhang et al." denotes DPSGD + BC +
ALC of [22]; "BC" denotes DPSGD + BC + our enhanced ALC; "IC" denotes DPSGD +
IC + our enhanced ALC)

###  4.5 Different noises

Figure 5: The test accuracy of the modified DPSGD with BC and enhanced ALC for
different $\sigma$ over 10 epochs.

We study the relationship between the test accuracy and $\sigma$ for DPSGD
with BC and the enhanced ALC with $\eta=0.025$, $m=64$, and $C=0.095$ over 10
epochs. The result is depicted in Figure 5 and shows that for convergence
resnet-18 needs a relatively small $\sigma$ and as a consequence can only
achieve a weak DP guarantee. This shows that a proper balance between test
accuracy and DP guarantee for very deep neural networks with complex datasets
is still an open problem. Our BC and ALC techniques help towards achieving a
practical balance, but more complimentary tricks and methods are still needed.

##  5 Conclusion

We have proposed a new adaptive layerwise clipping method as well as a new
batch clipping method for DPSGD. Our experiments show that DPSGD with BC and
new ALC can achieve faster convergence and higher accuracy compared to DPSGD
with IC. We have provided rigorous DP proofs for ALC and BC.

Our experiments are for small $\sigma$ which leads to weak differential
privacy. We still need additional techniques beyond (optimizing) ALC and BC
for training a deep neural network like resnet-18 with CIFAR10 in order to
achieve a practical balance between test accuracy and DP guarantee.

## 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.
  * Bun and Steinke [2016a] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  _arXiv_ , 2016a.
  * Bun and Steinke [2016b] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In Martin Hirt and Adam D. Smith, editors, _TCC_ , volume 9985, pages 635–658, 2016b.
  * Bun et al. [2018] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke.  Composable and versatile privacy via truncated CDP.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, _STOC_. ACM, 2018.
  * Dong et al. [2019] Jinshuo Dong, Aaron Roth, and Weijie J. Su.  Gaussian differential privacy, 2019.
  * Dong et al. [2021] Jinshuo Dong, Aaron Roth, and Weijie Su.  Gaussian differential privacy.  _Journal of the Royal Statistical Society_ , 2021.
  * Dwork and Rothblum [2016] Cynthia Dwork and Guy N Rothblum.  Concentrated differential privacy.  _arXiv preprint arXiv:1603.01887_ , 2016.
  * Dwork et al. [2006a] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 486–503. Springer, 2006a.
  * Dwork et al. [2006b] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006b.
  * Dwork et al. [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.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * Hu [2022] Kai Hu.  Revisiting Exploding Gradient: A Ghost That Never Leaves.  2022\.  URL https://www.andrew.cmu.edu/user/kaihu/Revisiting_Exploding_Gradient.pdf.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift, 2015.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  2009\.
  * Lecun et al. [1998] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.  doi: 10.1109/5.726791.
  * McMahan et al. [2018] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang.  Learning differentially private recurrent language models, 2018.
  * Mironov [2017] Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th computer security foundations symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * [18] Opacus.  Opacus PyTorch library.  Available from opacus.ai.
  * Robbins and Monro [1951] Herbert Robbins and Sutton Monro.  A stochastic approximation method.  _The Annals of Mathematical Statistics_ , 22(3):400–407, 1951.
  * van der Veen et al. [2018] Koen Lennart van der Veen, Ruben Seggers, Peter Bloem, and Giorgio Patrini.  Three tools for practical differential privacy.  _arXiv preprint arXiv:1812.02890_ , 2018.
  * Xu et al. [2021] Depeng Xu, Wei Du, and Xintao Wu.  Removing disparate impact on model accuracy in differentially private stochastic gradient descent.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’21, page 1924–1932, New York, NY, USA, 2021\. Association for Computing Machinery.  ISBN 9781450383325.  doi: 10.1145/3447548.3467268.  URL https://doi.org/10.1145/3447548.3467268.
  * Zhang et al. [2018] Xinyang Zhang, Shouling Ji, and Ting Wang.  Differentially private releasing via deep generative model.  _CoRR_ , abs/1801.01594, 2018.  URL http://arxiv.org/abs/1801.01594.

##  Appendix A Supplementary Material

As shown in the main paper, the training of resnet-18 for DP-SGD with BC and
ALC converges when the added Gaussian noise is small enough. We suspect that
this is related to the size of the networks and the complexity of the training
dataset. In Section A.1, we work with shallow networks and see if the training
of shallow networks on CIFAR10 can converge for larger Gaussian noise. In
Section A.2 we train a simple network on the simpler dataset MNIST and
investigate whether the Gaussian noise can even be larger. (We remind the
reader that the larger the added Gaussian noise, the better the DP guarantee.)
In Section A.3, we give evidence that DPSGD with batch clipping preserves the
merits of using batch normalization layers in convolutional neural networks.
To complete the work, Section A.4 compares ALC with Full Gradient Clipping
(FGC) showing that ALC outperforms FGC.

###  A.1 Lightweight Network on a Complex Dataset: convnet with CIFAR10

We conduct the same experiments as for resnet-18 on the CIFAR10 dataset with a
lightweight network (convnet) which consists of 5 layers. The first 4 layers
are the combination of a convolutional layer, a batch normalization layer and
an average pooling layer followed by CONV-BN-POOLING order. The last layer is
a softmax layer. The convent model architecture is defined in Table 1.

Operation Layer | #Filters | Kernel size | Stride | Padding | Output size | Activation function
---|---|---|---|---|---|---
$Conv2D$ | $32$ | $3\times 3$ | $1\times 1$ | $1\times 1$ | $16\times 16\times 3$ | ReLu
$BatchnNorm2d$ |  | $32\times 32$ |  |  |
$AvgPool2d$ |  | $2\times 2$ | $2\times 2$ |  |
$Conv2D$ | $64$ | $3\times 3$ | $1\times 1$ | $1\times 1$ | $8\times 8\times 32$ | ReLu
$BatchnNorm2d$ |  | $64\times 64$ |  |  |
$AvgPool2d$ |  | $2\times 2$ | $2\times 2$ |  |
$Conv2D$ | $64$ | $3\times 3$ | $1\times 1$ | $1\times 1$ | $4\times 4\times 64$ | ReLu
$BatchnNorm2d$ |  | $64\times 64$ |  |  |
$AvgPool2d$ |  | $2\times 2$ | $2\times 2$ |  |
$Conv2D$ | $128$ | $3\times 3$ | $1\times 1$ | $1\times 1$ | $1\times 1\times 128$ | ReLu
$BatchnNorm2d$ |  | $128\times 128$ |  |  |
$AdaptiveAvgPool2d$ |  | $1\times 1$ | $1\times 1$ |  |
$FC2$ | $-$ | $-$ | $-$ | $-$ | $10$ | $softmax$

Table 1: convnet model architecture with batch normalization layers Figure 6:
Test accuracy of DP-SGD with BC and ALC for convnet with CIFAR10 with respect
to various master clipping values $C$ and fixed $\sigma=0.01875$.

In our first experiment we choose the noise multiplier $\sigma=0.01875$, batch
size $m=1024$, diminishing learning rate $\eta=0.025$ with decay value
$\eta_{decay}=0.9$. We vary the master clipping value $C$ as shown in Figure
6. For $C=0.9$, we achieve $59.02\%$ test accuracy after 50 epochs, which is
less than the $67\%$ test accuracy achieved by the resnet-18 model. We observe
that the test accuracy increases significantly for $0<C\leq 0.2$, is stable
with some fluctuations for $0.2<C<0.9$, and decreases slightly for $C>0.9$. We
conclude that, for noise multiplier $\sigma=0.01875$, there is a range of $C$
where we see stable performance in terms of test accuracy.

Figure 7: Test accuracy of DP-SGD with BC and ALC for convnet with CIFAR10
with respect to various master clipping values $C$, fixed $\sigma=0.5$ and
$m=1024$

In our second experiment we want to push the lightweight convnet model to the
limit where we choose a relatively large $\sigma=0.5$ with all other hyper-
parameters remaining the same. As shown in figure 7, we only achieve $40.58\%$
test accuracy for $C=0.1$ and we observe that the test accuracy decreases for
$C>0.1$.

Figure 8:  Test accuracies of mini-batch SGD without DP for different mini-
batch sizes $m=(64,128,256,512,1024)$

See Figure 8, our third experiment studies mini-batch SGD without DP for
convnet with CIFAR10 as our benchmark. We see that smaller batch sizes yield
better accuracy. Specifically, we achieve $80.55\%$ test accuracy for batch
size $m=64$ and $61.19\%$ for batch size $m=1024$.

(a) Varying $C$

(b) Varying $\sigma$

Figure 9: Test accuracy of DP-SGD with BC and ALC for convnet with CIFAR10
with respect to various master clipping values $C$ and noise multiplier
$\sigma$ with batch size $m=64$

This leads us to the fourth experiment, where, by choosing a smaller batch
size, we try to increase the test accuracy of DP-SGD with BC and ALC for
convnet and CIFAR10 with $\sigma=0.5$. For example, in Fig 9.a we choose
$m=64$ and vary the master clipping constant $C$ to find the value which gives
best test accuracy: We achieve $43.42\%$ test accuracy for $C=0.14$. Moreover,
we also vary the noise multiplier value $\sigma$ with fixed master clipping
value $C=0.14$ to see whether our model can sustain larger noise. The Figure
9.a shows that the testing accuracy drops $\approx 15\%$ when we increase
$\sigma$ from $0.01$ to $0.2$ and decreases $\approx 10\%$ more from
$\sigma=0.2$ to $\sigma=0.6$. Therefore, we choose $\sigma=0.5$ for the next
experiments, where we can achieve $\approx 35\%$ testing accuracy and have
better DP guarantee than our resnet-18 experiment.

Figure 10:  Test accuracies of DPSGD+BC+ALC vs mini-batch SGD without DP for
different mini-batch sizes $m=(64,128,256,512,1024)$

Our final experiment uses DP-SGD with BC and ALC to train convnet with CIFAR10
for different batch sizes $m=(64,128,256,512,1024)$; We use master clipping
constant $C=0.14$, initial learning rate $\eta=0.025$ with decay rate
$\eta_{decay}=0.9$, noise multiplier $\sigma=0.5$, and number of epochs
$E=50$. We compare with mini-batch SGD without DP with $m=64$ in Figure 10.
Although the accuracy is hurt badly by the Gaussian noise, the lightweight
convnet model is still able to converge to $\approx 40\%$ test accuracy while
the test accuracy for resnet-18 starts to fall below $40\%$ for $\sigma\geq
0.2$ and only achieves $\approx 20\%$ test accuracy for $\sigma=0.5$.

Our experiments show that the deep resnet-18 network is more sensitive to the
added Gaussian noise than the lightweight convnet network. This observation
opens a new research direction where we want to simplify the neural network
model as much as possible for a given dataset type (and corresponding learning
task) while maintaining test accuracy and allowing a large enough $\sigma$ for
a reasonable DP guarantee. We expect (given our experiments) to be able to
train simpler network models with a larger noise multiplier $\sigma$ and this
yields better privacy. The network simplification should not be too much in
that the test accuracy of a trained model with DP noise should still be "good
enough."

###  A.2 Lightweight Network on a Simple Dataset: BN-LeNet-5 with MNIST

We investigate how well our method performs on a simpler dataset compared to
CIFAR-10. For this reason we conduct the same experiments of Section A.1 on
the MNIST dataset.

MNIST consists of 60,000 training examples and 10,000 testing examples of
handwritten digits [15]. Each example is a 28x28 gray-level image. For
training, we use the modified version of LeNet-5 [15], where we add a batch
normalization layer after each convolutional layer. The details of the
modified LeNet-5 architecture (BN-LeNet-5) are described in Table 2. For each
training image, we crop a $32\times 32$ region from it with padding of 4,
apply a random horizontal flip to the image, and then normalize it with

$(mean,std)=(0.1307,0.3081).$

Operation Layer | #Filters | Kernel size | Stride | Padding | Output size | Activation function
---|---|---|---|---|---|---
$Conv2D$ | $6$ | $5\times 5$ | $1\times 1$ | $0$ | $28\times 28\times 6$ | $tanh$
$BatchnNorm2d$ |  | $6\times 6$ |  |  |  |
$AvgPool2d$ |  | $2\times 2$ | $2\times 2$ |  | $14\times 14\times 6$ |
$Conv2D$ | $16$ | $5\times 5$ | $1\times 1$ | $0$ | $10\times 10\times 16$ | $tanh$
$BatchnNorm2d$ |  | $16\times 16$ |  |  |  |
$AvgPool2d$ |  | $2\times 2$ | $2\times 2$ |  | $10\times 10\times 16$ |
$Conv2D$ | $120$ | $5\times 5$ | $1\times 1$ | $0$ | $5\times 5\times 120$ | $tanh$
$BatchnNorm2d$ |  | $120\times 120$ |  |  |  |
$FC1$ | $-$ | $-$ | $-$ | $-$ | $84$ | $tanh$
$FC2$ | $-$ | $-$ | $-$ | $-$ | $10$ | $softmax$

Table 2: BN-LeNet-5 model architecture

As before, we fix the noise multiplier $\sigma=0.5$ and search for a good
master clipping constant $C$. We use DP-SGD with BC and ALC to train the BN-
LeNet-5 model with batch size $m=64$, diminishing step size $\eta=0.025$ with
decaying value $\eta_{decay}=0.9$ in 50 epochs. See Figure 11, we achieve the
best test accuracy $84.80\%$ for $C=0.2$.

Figure 11:  Test accuracy of DP-SGD with BC and ALC for BN-LeNet-5 with MNIST
with respect to various master clipping values $C$, fixed $\sigma=0.5$ and
$m=64$

Given $C=0.2$, we push the BN-LeNet-5 model to the limit by choosing a
relatively large noise multiplier $\sigma$ for which the test accuracy does
not drop below $50\%$. This allows us to see the effect of having a simpler
dataset by comparing to the experiments in Section A.1. We achieve $50.38\%$
test accuracy for $\sigma=2.5$ as shown in Figure 12.b.

(a) Varying $C$

(b) Varying $\sigma$

Figure 12:  Test accuracy of DP-SGD with BC and ALC for BN-LeNet-5 with MNIST
with respect to various noise multiplier values $\sigma$ and master clipping
values $C=0.2$ with batch size $m=64$

Let $C=0.2$ and $\sigma=2.5$, we train the BN-Lenet-5 model with various batch
size $m=(64,128,256,512,1024)$. As shown in Figure 12.a, the test accuracy
decreases from $50.38\%$ to $45.11\%$ when we increase the batch size from
$m=64$ to $m=1024$.

Our main conclusion is that the BN-LeNet-5 model still converges for the large
noise multiplier $\sigma=2.5$ when training on the MNIST dataset. Therefore,
the simpler dataset allows us to use more Gaussian noise for differential
privacy and this yields an improved Differential Privacy guarantee.

###  A.3 Batch clipping and Batch Normalization Layer

The concept of a Batch Normalization Layer (BNL) has been introduced in [13]
to improve the training speed and testing accuracy for convolutional neural
networks. Figure 13 shows that indeed for normal training with SGD without DP
batch normalization layers allow a high test accuracy. In this section we
investigate how using BNLs helps attaining a higher test accuracy when using
DP-SGD with BC and ALC.

(a) convnet with batch normalization layer

(b) convnet without batch normalization layer

Figure 13: Comparison of the test accuracy of training CIFAR10 with and
without BNLs for convnet using SGD without DP.

We compare training convnet 1 with and without BNLs for CIFAR10 by using DP-
SGD with BC and ALC. Figure 14 shows that we achieve $\approx 5\%$ higher test
accuracy for DP-SGD with batch size $m=64$, diminishing step size $\eta=0.025$
with decaying value $\eta_{decay}=0.9$, master clipping constant $C=0.14$,
noise multiplier $\sigma=0.5$ and total number of epochs $E=50$.

(a) convnet with batch normalization layer

(b) convnet without batch normalization layer

Figure 14: Comparison of the test accuracy of training CIFAR10 with and
without BNLs for convnet using DP-SGD with BC and ALC.

We also run experiments with convnet and resnet18 after removing all BNLs for
the set-up in Table 3 (as in Section 4 in the main body) where we also
consider a diminishing master clipping constant with initial value $C=0.095$
decaying with rate $C_{decay}=0.9$ after each epoch.

Learning Rate $\eta$ | $0.025$
---|---
Master Clipping value ($C$) | $0.095$
Noise multiplier $\sigma$ | $0.01875$
Learning rate decay ($\eta_{decay})$ | $0.9$
Clipping value decay ($C_{decay}$) | $0.9$
Batch size ($m$) | $[64,128,256,512,1028]$
Epochs ($E$) | $50$

Table 3: Hyperparameter settings

Figure 15 is for convnet with IC+ALC (as compared to Figure 14 which is for
BC+ALC). After removing batch normalization layers in the convnet model, the
testing accuracy for IC cannot converge to an acceptable value. After 50
epochs, we only achieve $21.12\%$ test accuracy if we train the model with
constant step size and constant master clipping value $C$ for mini-batch size
$m=64$. This shows that batch clipping outperforms individual clipping for
convnet without BNLs.

(a) css,constant $C$

(b) css,diminishing $C$

(c) dss,constant $C$

(d) dss,diminishing $C$

Figure 15:  Test accuracy of training CIFAR10 for convnet without BNLs using
DP-SGD with IC and ALC. Here, css and dss denote constant step size and
diminishing step size, respectively.

Next, we ask ourselves whether batch clipping still outperforms individual
clipping for the more complicated model such resnet18 without BNLs. As shown
in Figure 16, we achieve $30\%\sim 40\%$ test accuracy for the various
combinations of constant and diminishing step size and master constant,
respectively (with the best test accuracy close to $40\%$ for constant step
size and non-decaying master constant). On the other hand, we only achieve
$18\%\sim 22\%$ test accuracy for individual clipping as shown in Figure 17.

(a) css,constant $C$

(b) css,diminishing $C$

(c) dss,constant $C$

(d) dss,diminishing $C$

Figure 16:  Test accuracy of training CIFAR10 for resnet18 without BNLs using
DP-SGD with BC and ALC. Here, css and dss denote constant step size and
diminishing step size, respectively.

(a) css,constant $C$

(b) css,diminishing $C$

(c) dss,constant $C$

(d) dss,diminishing $C$

Figure 17:  Test accuracy of training CIFAR10 for resnet18 without BNLs using
DP-SGD with IC and ALC. Here, css and dss denote constant step size and
diminishing step size, respectively.

###  A.4 ALC versus FGC

We investigate how ALC compares with Full Gradient Clipping (FGC) under the
same Gaussian Noise $N(0,(2C\sigma)^{2})$. (FGC means that we clip the full
gradient and do not separately clip layers as in ALC.) As shown in Figure 18,
we used DP-SGD with BC for 50 epochs in order to train resnet18 with CIFAR10;
we use a non-decaying master clipping constant $C=0.095$, noise multiplier
$\sigma=0.01875$, mini-batch size $m=64$ and diminishing step size
$\eta=0.025$ with $\eta_{decay}=0.9$. We achieve $66.66\%$ with ALC and
$46.35\%$ with FGC method. This shows evidence that training with ALC leads to
better convergence rate as well as better test accuracy.

However, in the above experiment the privacy budget is not the same for ALC
versus FGC: See Section 3.2 in ALC we have an extra factor $\sqrt{L}$ in the
DP guarantee, where $L$ is the number of layers in the neural network model.
Therefore, we also run the same experiment for FGC with discounted noise
multiplier $\bar{\sigma}=\sigma/\sqrt{L}=\sigma/\sqrt{62}$ so that both ALC
and FGC correspond to the same DP guarantee. The result is shown in Figure 18
and shows that ALC outperforms FGC.

(a) Under the same Gaussian noise

(b) Discounted noise multiplier

Figure 18: Test accuracy of DP-SGD of resnet18 with CIFAR10 for BC+ALC versus
BC+FGC.

##  Appendix B Towards Balancing DP Guarantees and Accuracy

In this paper we have discussed how ALC and BC can bring us closer to
balancing DP with accuracy. In particular, the focus of this paper is on the
ALC and BC techniques for improving robustness against added Gaussian noise
for differential privacy. However, we still need additional techniques in
order to achieve a practical balance which allows a reasonable accuracy (say
at most 10% or 20% drop) together with a DP guarantee which shows a trade-off
curve reasonably close to the ideal $1-\alpha$ curve which represents perfect
security.

In Section B.1 we show that ALC+BC as discussed in this paper is not yet
sufficient on themselves to find a practical balance: Even though ALC+BC allow
us to be significantly more robust against added Gaussian noise for
bootstrapping DP, just using these techniques will not yet make training of
even lightweight neural network models with less complex training datasets
sufficiently robust against the required DP noise for good/solid differential
privacy.

One direction of tackling this problem is to enhance and/or optimize the
ALC+BC techniques. In Section B.2 we offer suggestions that focus on improving
the presented ALC+BC. We leave it to future work to empirically study these
possible improvements and optimizations. And we leave it to future work to
find altogether new techniques that are complimentary and go beyond ALC+BL.

###  B.1 Lightweight Neural Network Model with Less Complex Training Dataset

We show that even moving to a lightweight neural network with a less complex
training data set still requires additional techniques beyond our BC+ALC
and/or improvements of the BC+ALC techniques. We show that BC+ALC as presented
in this paper is on its own not yet sufficient even though they make the gap
between DP guarantee and accuracy significantly smaller:

We notice that Corollary 5.4 in [6] shows that, for $c>$, if $E=(N/m)\cdot
c^{2}\rightarrow\infty$, then (4) is asymptotically $G_{\mu}$-DP with
$\mu=\sqrt{2}\cdot c\cdot h(\sigma)$ for

$h(\sigma)=\sqrt{e^{\sigma^{-2}}\Phi(3\sigma^{-1}/2)+3\Phi(-\sigma^{-1}/2)-2}.$

By using their interpretation of their result, we may conclude that (4) is
approximately $G_{\sqrt{2}\cdot c\cdot h(\sigma)}$ for $c=\sqrt{Em/N}$ for
concrete large $N$ and relatively small $E$ and $m$. Including ALC means that
we need to substitute $\sigma/\sqrt{L}$ for $\sigma$.

For $\sigma=0.01875$, we have
$h(\sigma/\sqrt{L})\approx\sqrt{e^{(\sigma/\sqrt{L})^{-2}}}=e^{L\sigma^{-2}/2}$,
i.e., a very very large number leading to no useful DP guarantee even for
large datasets (with large $N$). In other words, $\sigma$ cannot be too small.
Even $\sigma=0.5$ with $L=62$ for resnet-18 leads to
$h(\sigma/\sqrt{L})=\sqrt{e^{62\cdot
4}\Phi(3\cdot\sqrt{62})+3\Phi(-\sqrt{62})-2}$ which is prohibitively large for
achieving a good DP guarantee. Figure 5 shows that choosing a larger
$\sigma>0.5$ for obtaining a better DP guarantee gives too much noise
resulting in a poor test accuracy of at most $20\%$, which is unacceptable. We
conclude that resnet-18 and CIFAR10 represent a too deep neural network and
complex dataset for a good balance between test accuracy and DP guarantee when
using DP-SGD with our BC and ALC improvements. For now, we see that BC and ALC
are two steps toward a better balance (after we are able to achieve
convergence where this was not possible before for the original DP-SGD with
IC) and that more techniques are needed for deep neural network models with
complex training datasets.

Section A.1 shows experiments for the lightweight convnet model with the
complex CIFAR10 dataset which achieves a better $\approx 40\%$ test accuracy –
this demonstrates that a lightweight neural network model is more robust
against noise and is better suitable for training with DP-SGD with BC and ALC.
Section A.2 shows experiments for the lightweight BN-LeNet-5 model with the
simple MNIST dataset which, if restricted to $50\%$ accuracy (for proper
comparison with the $40\%$ test accuracy for convnet with CIFAR10), allows a
much larger $\sigma=2.5$ resulting in a much improved $G_{0.52}$-DP guarantee
($h(\sigma/\sqrt{L})=1.513$ with $L=8$; $m=64$, $N=\frac{9}{10}\cdot 60000$,
$E=50$).

A smaller $\sigma=1.5$ (see Figure 12.b in Section A.2) achieves a better
balance of $\approx 67\%$ test accuracy with $\approx G_{1.99}$-DP
($h(\sigma/\sqrt{L})=5.783$). For a factor 15 larger dataset we would be able
to improve $G_{1.99}$-DP to the better $G_{0.51}$-DP guarantee. We conclude
that a more lightweight model and/or less complex (and larger) training
dataset can potentially lead to a better balance between test accuracy and DP
guarantee using the proposed BC and ALC techniques. Nevertheless, we will even
want to improve $G_{0.51}$ to some trade-off function more like $G_{0.01}$
such that hypothesis testing indeed resembles a random guess. To date, this
remains an open problem – our ALC+BC techniques provide a step forward, but
more complimentary techniques are needed.

###  B.2 Towards Improving/Optimizing ALC+BC

From an accuracy perspective we see that $\sigma=1.5$ (as mentioned above) or
larger $\sigma$ may be needed even for a more lightweight network model with a
less complex training dataset. For large $\sigma$, we notice that a Taylor
series expansion of $h(\sigma)$ shows a linear dependency on $1/\sigma$. This
shows that $\mu$ in a $G_{\mu}$-DP guarantee for ALC scales with $\sqrt{L}$
(since, as discussed before, ALC requires a factor $\sqrt{L}$ smaller $\sigma$
if we want to keep the same $G_{\mu}$-DP guarantee). The linear dependency of
$\mu$ on $\sqrt{L}$ is due to the fact that there is no subsampling effect for
the separate layers within a gradient computation; the leakage is directly
composed over all the layers for a single gradient computation (without using
a subsampling operator as is done in the general analysis leading to (4)). For
this reason, it is advantageous to group layers that have similar clipping
constant and clip the group rather than the individual layers within the
group. E.g., Figure 1 indicates we may use about 4 groups of layers
representing a very small norm, to medium and larger norms. This reduces
$L=62$ down to $L=4$ for resnet-18. Also, notice that the unexplored
sparsification trick mentioned in Section 3.4 may offer another improvement.

Our discussion shows that as future work, we need to further optimize the
promising ALC technique. One tempting direction is to not use a single
training sample $\xi$ for updating all the layer gradients, but to use $\xi$
for a single layer gradient. So, rather than using a data sample $\xi$ for
computing updates for all the layer gradients, we can think of using a data
sample $\xi$ for updating just one of the layer gradients. Together with $\xi$
we choose one of the $L$ layers at random. In this way we still train all the
layers. We notice that this approach means that we have subsampling for each
layer gradient and we do not pay the composition price of $\sqrt{L}$ as
explained in 3.2. However, one can think of this as $L$ separate learning
tasks, each costing the same amount of training as the original learning task
which learn the full weight vector across all layers at once. This means a
composition of $L$ leakages and we again pay the price of $\sqrt{L}$ since
$G_{\mu}^{\otimes L}=G_{\sqrt{L}\cdot\mu}$. Or, equivalently, one can argue
that we need $L$ times more rounds in order to train the full weight vector,
i.e., a factor $L$ more epochs, hence, the $\sqrt{L}$ factor penalty after
composing over all the epochs. So, this idea still does not improve the
sought-after balance between DP guarantee and accuracy since we now have
proper amplification from subsampling but at the price of $L$ times more
rounds, and this cancels out, that is, no improvement.

Based on the above discussion we would like to somehow only clip the overall
full gradient while still keeping the better robustness against DP noise of
ALC which requires layerwise clipping. Suppose that we associate a
multiplication factor $m_{j}\geq 1$ to each layer $j$. We proceed as follows:

  1. 1.

As before, we first compute the full gradient composed of layer gradients:

$\nabla_{w}f(w;\xi)=(\nabla_{w_{1}}f(w;\xi)||....||\nabla_{w_{L}}f(w;\xi)).$

  2. 2.

We use the multiplication factors $m_{j}$, $1\leq j\leq L$, to compute

$\\{\nabla_{w}f(w;\xi)\\}_{m_{1},...,m_{L}}=(m_{1}\cdot\nabla_{w_{1}}f(w;xi)||....||m_{L}\cdot\nabla_{w_{L}}f(w;\xi)).$

  3. 3.

Now we perform full gradient clipping (FGC) with clipping constant $C$:

$[\\{\nabla_{w}f(w;\xi)\\}_{m_{1},...,m_{L}}]_{C}.$

We use this in computing formulas (the $a_{h}$) leading to the noised update
$U$. Notice again that we can use the IC or BC approach in these formulas.

The differential privacy argument follows the line of thinking of our analysis
of BC in Section 3.1. Since we use FGC, we do not pay the $\sqrt{L}$ penalty.
This will significantly improve the trade-off function as discussed in Section
B.1.

What about robustness against the added Gaussian DP noise? The server receives
a noised update of the form

$U=(U_{1}||...||U_{L}).$

The server divides by the multiplication factors and computes

$(U_{1}/m_{1}||...||U_{L}/m_{L})$

with which the global model is updated. The effect of the proposed trick using
multiplication factors $m_{j}$ is that dividing by the multiplication factors
retrieves the original layer gradients – if there is no clipping noise. In
this process we reduce the added Gaussian noise, since the noises are divided
by the factor $m_{j}\geq 1$. In our ALC we estimate the expected norm of each
layer $j$ denoted by $e_{j}$. We equate $M$ to the maximum of all $e_{j}$. We
compute layer clipping constants $C\cdot e_{j}/M$. In the above approach based
on multiplication factors we may define $m_{j}=M/e_{j}$. Since this will
increase each layer norm to $M$ in expectation, we will want to choose a
higher overall clipping constant $C$ in FGC (as compared555We can use the same
collecting-layers-into-4-groups argument for resnet18 with which we started
this section and conclude that the clipping constant corresponding to the use
of multiplication factors is about $\sqrt{4}=2$ larger. to the master clipping
constant $C$ used in ALC). We see that the proposed new trick on one hand
remains robust to Gaussian noise added to layers that have a small norm
compared to other layers. On the other hand $C$ needs to be fine-tuned and may
be larger than the $C$ of ALC, which means that the overall added noise is
larger and makes this solution less robust. Concluding, we have the original
DP guarantee without $\sqrt{L}$ penalty, while we make sure that layer
gradients with small norms get multiplied by a large $m_{j}$ so that the
effect of the added noise for that layer is not going to be overpowering. This
is also the goal which ALC wants to achieve. We leave it to future work to
experiment with multiplication factors and in this sense optimize over ALC
and/or find a better balance between DP guarantee and test accuracy.

As a final remark, we notice that we do not need to restrict ourselves to
using BC, we may use GBC which allows momentum based update rules. We leave it
to future work to find out whether this can lead to more robustness against
added Gaussian DP noise.