# Privacy-preserving Learning via Deep Net Pruning

Yangsibo Huang<EMAIL_ADDRESS>Princeton University. Yushan Su
<EMAIL_ADDRESS>Princeton University. Sachin Ravi
<EMAIL_ADDRESS>Princeton University. Zhao Song<EMAIL_ADDRESS>Princeton University and Institute for Advanced Study. Sanjeev Arora
<EMAIL_ADDRESS>Princeton University. Kai Li<EMAIL_ADDRESS>Princeton University.

This paper attempts to answer the question whether neural network pruning can
be used as a tool to achieve differential privacy without losing much data
utility. As a first step towards understanding the relationship between neural
network pruning and differential privacy, this paper proves that pruning a
given layer of the neural network is equivalent to adding a certain amount of
differentially private noise to its hidden-layer activations. The paper also
presents experimental results to show the practical implications of the
theoretical finding and the key parameter values in a simple practical
setting. These results show that neural network pruning can be an effective
alternative to adding differentially private noise for neural networks.

##  1 Introduction

Data privacy has become one of the top concerns in machine learning with deep
neural networks, since there is an increasing demand to train deep net models
on distributed, private data sets. For example, hospitals are now training
their automated diagnosis systems on private patients’ data [LST+16, LS17,
DFLRP+18]; and advertisement providers are collecting users’ online
trajectories to optimize their learning-based recommendation algorithm [CAS16,
YHC+18]. These private data, however, are usually decentralized in nature, and
policies such as the Health Insurance Portability and Accountability Act
(HIPAA) [Act96] and the California Consumer Privacy Act (CCPA) [Leg18]
restrict the exchange of raw data among distributed users.

Various schemes have been proposed for privacy sensitive deep learning with
distributed private data, where model updates [KMY+16] or hidden-layer
representations [VGSR18] are exchanged instead of the raw data. However,
recent research identified that even if the raw data are kept private, sharing
the model updates or hidden-layer activations can still leak sensitive
information about the input, which we refer to as the victim. Such leakage can
be: the victim’s class, the victim’s feature [FJR15], or even its original
record [MV15, DB16, ZLH19]. Privacy leakage poses a severe threat to
individuals whose private records have been collected to train the deep neural
network.

Differential privacy (DP) [DMNS06] has emerged, during the past few years, as
a standard framework to analyze privacy leakage. The core idea of achieving
differential privacy is to add controlled noise to the output of a
deterministic function. However, there is a long standing trade-off in adding
noise to preserve privacy: as privacy leakage decreases, accuracy decreases
too. For data without strong signals, an alternative that satisfies privacy
guarantees without decreasing accuracy is strongly desired.

(a) 0

(b) 0.1

(c) 0.2

(d) 0.3

(e) 0.4

(f) 0.5

(g) 0.6

(h) 0.7

(i) 0.8

(j) 0.9

Figure 1: Visualization of inverted MNIST inputs from the Conv5 layer of
LeNet-5 using the inversion algorithm in Section 4.2. We prune the network
with different target sparsity, shown in caption (sparsity = the fraction of
weights we set to 0). Pruning with higher sparsity seems to leak less
information about the input.

In this work, we attempt to answer the question whether neural network pruning
can be such an alternative. Two observations motivate this question. First,
pruning perturbs a neural network, which is somewhat similar to adding noise.
Figure 1 shows that neural network pruning makes the inversion from hidden-
layers harder as the sparsity of the pruned network increases. Second, [HMD16,
LKD+17] showed that they were able to prune a large percentage (e.g. 90$\%$)
of the weights in several commonly used neural networks without reducing
accuracy.

The approach taken in this paper is to prove the existence of an equivalence
between pruning and adding differentially private noise. By doing so, one can
analyze privacy leakage of network pruning using the framework of differential
privacy. We have focused on a distributed learning setting in which a hidden-
layer of activations will be used to communicate among distributed sites.
Thus, our study explores the equivalence between neural network pruning and
adding differentially private noise to activations from both theoretical and
experimental perspectives.

The paper makes four contributions. First, to the best of our knowledge, this
is the first work that draws a connection between neural network pruning and
differential privacy from a theoretical perspective.

Second, we show that magnitude-based pruning algorithm is differentially
private, if the width of the neural network is sufficiently wide. (see Section
3).

Third, we show that in a synthetic setting with a practical differential
budget, the width of the neural network needs to be only a few hundreds in
order to make the theoretical equivalence hold (see Section 4).

Finally, our experiments with MNIST and CIFAR-10 show that, with the same
target accuracy, magnitude pruning preserves substantially more privacy than
adding random noise (the classical way to provide differential privacy) to
neural network.

#### Roadmap.

The rest of this paper is organized as follow. Section 2 presents some
backgrounds about differential privacy and neural network pruning. Section 3
states our main theoretical result which shows the equivalence between
differential privacy and magnitude-based pruning. Section 5 covers relevant
work in different privacy and neural network pruning, and also provides the
intuition for possible connections between them from a perspective of sparse
recovery. In Section 4, we run experiments on MNIST and CIFAR-10 datasets and
observe that the experimental results match our theoretical findings. Finally,
we conclude this work in Section 6.

Appendix A presents several basic probability tools. Appendix B states some
applications of concentration inequalities. Appendix C states some anti-
contraction result and its generalization. Appendix D discusses about
sensitivity. Appendix E finally proves our main result. Appendix F show
several more experimental results.

##  2 Backgrounds

#### Notations.

For a positive integer $n$, we use $[n]$ to denote set $\\{1,2,\cdots,n\\}$.
For vector $x\in\operatorname{{\mathbb{R}}}^{n}$, we use $\|x\|_{1}$ to denote
$\sum_{i=1}^{n}|x_{i}|$, $\|x\|_{2}$ to denote
$(\sum_{i=1}^{n}x_{i}^{2})^{1/2}$, $\|x\|_{\infty}$ to denote
$\max_{i\in[n]}|x_{i}|$. We use ${\cal N}(\mu,\sigma^{2})$ to denote random
Gaussian distribution. For a matrix $A$, we use $\|A\|$ to denote its spectral
norm.

This section presents some backgrounds before theoretically establishing the
equivalence between magnitude-based pruning and adding differentially private
noise in Section 3. Section 2.1 revisits the notion of
$(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy. Section
2.2 describes the magnitude pruning algorithm.

###  2.1 Differential privacy

The classical definition of differential privacy is shown as follow:

######  Definition 2.1
($(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy
[DKM+06]).

For a randomized function $h(x)$, we say $h(x)$ is
$(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy if for
all $S\subseteq\mathrm{Range}(h)$ and for all $x,y$ with $\|x-y\|_{1}\leq 1$

$\displaystyle\Pr_{h}[h(x)\in
S]\leq\exp(\epsilon_{\mathrm{dp}})\cdot\Pr_{h}[h(y)\in
S]+\delta_{\mathrm{dp}}.$

Definition 2.1 says that, if there are two otherwise identical records $x$ and
$y$, one with privacy-sensitive information in it, and one without it, and we
normalize them such that $\|x-y\|_{1}\leq 1$. Differential Privacy ensures
that the probability that a statistical query will produce a given result is
nearly the same whether it’s conducted on the first or second record.
Parameters $(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$ are called the
privacy budget, and smaller $\epsilon_{\mathrm{dp}}$ and
$\delta_{\mathrm{dp}}$ provide a better differential privacy protection. One
can think of a setting where both parameters are 0, then the chance of telling
whether a query result is from $x$ or from $y$ is no better than a random
guessing.

A standard strategy to achieve differential privacy is by adding noise to the
the original data $x$ or the function output $h(x)$. In order to analyze it,
we need the following definition:

######  Definition 2.2 (Global Sensitivity [DMNS06]).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{d}$, define $\mathrm{GS}_{p}(f)$,
the $\ell_{p}$ global sensitivity of $f$, for all $x,y$ with $\|x-y\|_{1}\leq
1$ as

$\displaystyle\mathrm{GS}_{p}(f)=\sup_{x,y\in\mathbb{R}^{n}}\|f(x)-f(y)\|_{p}.$

The global sensitivity of a function measures how ‘sensitive’ the function is
to slight changes in input. The noise needed for differential privacy
guarantee is then calibrated using some well-known mechanisms, e.g., Laplace
or Gaussian [DR14], and the amount of noise (the standard deviation of the
noise distribution) is proportional to the sensitivity, but inversely
proportional to the privacy budget $\epsilon_{\mathrm{dp}}$. That is to say,
for a given function with fixed global sensitivity, a larger amount of noise
is required to guarantee a better differential privacy (one with a smaller
budget $\epsilon_{\mathrm{dp}}$).

###  2.2 Magnitude-based pruning

Algorithm 1 Stochastic Gradient Descent with Magnitude-based Pruning,
simplified version of Algorithm 2

1:procedure SGDMagPrune($\cal D$, $a$)

2: $W^{(1)}$ is a random init. of neural network’s weights

3: for $t=1\to T_{\text{train}}+T_{\text{prune}}$ do $\triangleright$ Training
stage

4: Sample $(x,y)\sim{\cal D}$ uniformly at random

5: if $t\in T_{\text{prune}}$ then $\triangleright$ Pruning stage

6: $\widetilde{W}^{(t)}\leftarrow\textsc{ThPrune}(W^{(t)},a^{(t)})$

7: end if

8: Update $W^{(t+1)}$ based on $\widetilde{W}^{(t)}$ and gradient

9: end for

10: $T_{\text{end}}\leftarrow T_{\text{train}}+T_{\text{prune}}$

11:
$\widetilde{W}^{(T_{\text{end}})}\leftarrow\textsc{ThPrune}(W^{(T_{\text{end}})},a^{(T_{\text{end}})})$

12:end procedure

13:procedure ThPrune($W,a$)

14: $(\widetilde{W}_{l})_{i,j}\leftarrow(W_{l})_{i,j}\cdot{\bf
1}_{|(W_{l})_{i,j}|>a}$, $\forall i,j$

15: return $\widetilde{W}$

16:end procedure

Procedure SGDMagPrune (see Algorithm 1) describes the process of training a
deep neural network with stochastic gradient descent and magnitude-based
pruning.

As shown, the procedure begins with a standard training stage of
$T_{\mathrm{train}}$ iterations (line 3 to line 9). After that, the model
enters the pruning stage of $T_{\mathrm{prune}}$ iterations (line 5 to line
9). Inside each iteration of the pruning stage, we firstly perform a layer-
wise threshold pruning (see procedure ThPrune in Algorithm 1) which sets the
weights with magnitudes smaller than $a$ to zero. Then, we run model update
once. At the end of the prune stage, we perform a layer-wise pruning again to
guarantee that the resulted weight matrix achieves a certain sparsity
(fraction of zeros).

Note that inside each pruning iteration above, we perform magnitude pruning
with the threshold $a^{(t)}$. In practice, $a^{(t)}$ is determined by three
factors: the target sparsity of the matrix after pruning, the total number of
pruning iterations $T_{\text{prune}}$, and the current number of pruning
iterations $t$. Since the proof only cares about the final state of the weight
matrix, we leave the details of how to dynamically configure $a^{(t)}$ to the
experiment section.

##  3 Main result

We start by formulating the equivalence between pruning and adding
differentially private noise. We propose the following notion to describe the
closeness between a randomized function and a given function (either
randomized or deterministic).

######  Definition 3.1
($(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-close).

For a pair of functions
$g:\operatorname{{\mathbb{R}}}^{d}\rightarrow\operatorname{{\mathbb{R}}}^{m}$
and
$h:\operatorname{{\mathbb{R}}}^{d}\rightarrow\operatorname{{\mathbb{R}}}^{m}$,
and a fixed input $x$, we say $g(x)$ is $(\epsilon,\delta)$-close to $h(x)$ if
and only if,

$\displaystyle\Pr_{g,h}\left[\frac{1}{\sqrt{m}}\|g(x)-h(x)\|_{2}\leq\epsilon\right]\geq
1-\delta.$

$(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-closeness basically requires
that, the root-mean-square error of two functions’ output with a given input
is small enough.

Now we present our main theoretical result.

######  Theorem 3.2 (Informal of Theorem E.1).

For a fully connected neural network (each layer can be viewed as
$f(x)=\phi(Ax+b)$), where $\|x\|_{2}=1$ and
$x\in\operatorname{{\mathbb{R}}}^{d}_{\geq 0}$. Applying magnitude-based
pruning on the weight $A\in\operatorname{{\mathbb{R}}}^{m\times d}$ (where
each $A_{i,j}\sim{\cal N}(0,\sigma_{A}^{2})$) gives us
$\widetilde{A}\in\operatorname{{\mathbb{R}}}^{m\times d}$. There exists a
function $h(x)$ satisfying two properties :

  1. 1.

$h(x)$ is $(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy
on input $x$;

  2. 2.

$h(x)$ is $(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-close to
$g(x)=\phi(\widetilde{A}x+b)$.

where
$m=\Omega(\operatorname{poly}(1/\epsilon_{\mathrm{ap}},\log(1/\delta_{\mathrm{ap}}),\log(1/\delta_{\mathrm{dp}})))$
and $\sigma_{A}=O(\epsilon_{\mathrm{dp}}\delta_{\mathrm{dp}}/(m^{2}))$.

In the above theorem, we should think of $m$ as the width of the neural
network, and $d$ as the input data dimension. $\phi$ is the activation
function, e.g., $\phi(z)=\max\\{z,0\\}$.

Regarding the two properties of $h(x)$, property 1 requires $h(x)$ to provide
$(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy, and
property 2 requires that $h(x)$ is ‘equivalent’ to magnitude-based pruning
with the predefined $(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-close
notation.

#### Proof Sketch

We use $\widetilde{A}\in\operatorname{{\mathbb{R}}}^{m\times d}$ to denote the
weight matrix after magnitude-based pruning, and
$\overline{A}=\widetilde{A}-A\in\operatorname{{\mathbb{R}}}^{m\times d}$. We
define a noise vector $e\in\operatorname{{\mathbb{R}}}^{m}$ as follows:

$\displaystyle e=\text{Lap}(1,\sigma)^{m}\circ(\overline{A}x).$

The main proof can be split into two parts.

######  Claim 3.3.

Let $h(x)=f(x)+e\in\operatorname{{\mathbb{R}}}^{m}$, we can show that $h(x)$
is $(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy.

######  Claim 3.4.

For sufficiently large $m$, we have

$\displaystyle\Pr\Big{[}\frac{1}{\sqrt{m}}\|e-\overline{A}x\|_{2}\geq\epsilon_{\mathrm{ap}}\Big{]}\leq\delta_{\mathrm{ap}}.$

To prove Claim 3.3, we show by the definition of differential privacy, for any
inputs $x$ and $y$ with $\|x-y\|\leq 1$,

$\Pr_{h}[h(x)\in S]\leq\exp(\epsilon_{\mathrm{dp}})\cdot\Pr[h(y)\in
S]+\delta_{\mathrm{dp}}.$

To be more specific, we use the fact of $e$ sampled from the Laplace
distribution, and bound the ratio $\frac{p_{h}(h(x)=t\in S)}{p_{h}(h(y)=t\in
S)}$, where $p(\cdot)$ denotes probability density. To bound the above ratio:
first we need to derive and upper-bound the global sensitivity (see Appendix
D) of a single-layer neural network. Then, we extend the famous anti-
concentration result by Carbery and Wright [CW01] to a more general setting
(see Appendix C). To the best of our knowledge, this generalization is not
known in literature. Once the densities are bounded, integrating $p(\cdot)$
yields the requirement of differential privacy, thus complete the proof of
part 1.

To prove Claim 3.4, we firstly define $z_{i}=e_{i}-(\overline{A}x)_{i}$. Then
we apply the concentration theorem (see Appendix B) to show that for any
$\|x\|_{2}=1$ and $x\in\operatorname{{\mathbb{R}}}^{d}_{+}$,

$\displaystyle\Pr\Big{[}\frac{1}{m}|\sum_{i=1}^{m}(z_{i}-\operatorname*{{\mathbb{E}}}[z_{i}])|\geq\epsilon_{\mathrm{ap}}^{2}\Big{]}\leq\delta_{\mathrm{ap}},$

which completes the proof of Claim 3.4.

##  4 Experiments

Figure 2: Distribution of weight magnitude (over all LeNet-5 convolution
layers) after training and pruning on MNIST. Figure 3: Distribution of weight
magnitude (over all VGG-19 convolution layers) after training and pruning on
CIFAR-10. Figure 4: Sparsity-step curve during the pruning stage with gradual
pruning mechanism applied.

This section presents experimental results related to our main theoretical
finding in Section 3. The experiments aim to answer the following questions:

  1. 1.

With the same utility (test accuracy) requirement, does neural network pruning
preserve more privacy compared with adding noise? If yes, how much more?

  2. 2.

Given a privacy budget $(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$, how
large $m$ should be to guarantee an
$(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-closeness between neural
network pruning and adding noise?

###  4.1 Experimental setup

#### Datasets and networks.

We have conducted image classification experiments on MNIST [LCB10] and
CIFAR-10 [Kri09] datasets.

The network architectures used are LeNet-5 [LBBH98] for MNIST, and VGG-19
[SZ15] for CIFAR-10. All models are trained on 4 Nvidia Tesla K80 GPUs using
Tensorflow [AAB+16]. We test these two simple and standard architectures in
order to better match the setting described in our theoretical result. A
detailed description of network architectures and hyper-parameters can be
found in the Appendix F.

#### Pruning.

Our experiments have employed the gradual pruning technique introduced in
[ZG17], where over $n$ iterations starting from $t_{0}$ with interval $\Delta
t$, the sparsity is increased from an initial sparsity value $k_{0}$ (0 in our
case) to a target sparsity value $k_{T}$ such that,
for $t\in\left\\{t_{0},t_{0}+\Delta t,\ldots,t_{0}+n\Delta t\right\\}$:

$\displaystyle
k_{t}=k_{T}+\left(k_{0}-k_{T}\right)\left(1-(t-t_{0})/(n\cdot\Delta
t)\right)^{3}\quad$

Figure 4 shows sparsity-step curves to illustrate how to achieve a target
sparsity. Figure 2 and 3 show the final weight distribution across all layers
after applying gradual magnitude-based pruning.

###  4.2 Test of privacy leakage as an inversion attack

Since there is no standard way to quantify privacy preservation, we have used
the method that with a given attack, we will measure how much “privacy
leakage” a particular approach will suffer. We have introduced the following
pipeline to measure the privacy leakage in the neural network.

(a) Test accuracy of LeNet-5 trained on MNIST with different sparsity levels.
(b) Test accuracy of VGG-19 trained on CIFAR-10 with different sparsity
levels.

Figure 5: Demonstration of test accuracy of LeNet-5 on MNIST (a), and test
accuracy of VGG-19 on CIFAR-10 (b).

Let us conceptualize the mapping from the input to the hidden-layer output in
a neural network as a representation function. For a public representation
function
$\Phi:\operatorname{{\mathbb{R}}}^{d}\rightarrow\operatorname{{\mathbb{R}}}^{m}$,
we perturb $\Phi$ to get
$\Phi^{\prime}:\operatorname{{\mathbb{R}}}^{d}\rightarrow\operatorname{{\mathbb{R}}}^{m}$,
and keep $\Phi^{\prime}$ private. We use the following attack [MV15] to test
the potential privacy leakage of using $\Phi^{\prime}$ as the representation
function on any input $x$:

Given a perturbed representation $\Phi^{\prime}_{0}=\Phi^{\prime}(x)$, and the
public function $\Phi$, the attacker’s goal is to find the preimage of
$\Phi^{\prime}(x)$, namely

$\displaystyle x^{*}=\arg\min_{x\in\operatorname{{\mathbb{R}}}^{d}}{\cal
L}(\Phi(x),\Phi^{\prime}_{0})+\lambda{\cal R}(x)$

where the loss function ${\cal L}$ is defined as

$\displaystyle{\cal L}(a,a^{\prime})=\|a-a^{\prime}\|_{2}^{2},$

$\lambda>0$ is the regularization parameter, and the regularization function
$\mathcal{R}$ in our case is the total variation of a 2D signal

$\displaystyle\mathcal{R}(a)=\sum_{i,j}((a_{i+1,j}-a_{i,j})^{2}+(a_{i,j+1}-a_{i,j})^{2})^{1/2}.$

Answering Question 1 requires the testing of the inversion attack against two
different perturbations $\Phi^{\prime}$:

  * •

$\Phi^{\prime}_{\text{noise}}(x)=\Phi(x)+e$, where $e$ is a Laplace noise

  * •

$\Phi^{\prime}_{\text{prune}}(x)=\widetilde{\Phi}(x)$, where
$\widetilde{\Phi}$ stand for magnitude-based pruning on layers of $\Phi$

The following describes how to quantitatively measure the leakage with the
defined inversion attack.

#### Measurements of privacy leakage under attack

Let us denote the preimage of $\Phi^{\prime}(x)$ obtained from the inversion
attack as $x^{*}$, and the original image as $x$. If $\Phi^{\prime}$ has a
strong differential privacy guarantee, namely $\epsilon_{\mathrm{dp}}$ is
sufficiently small, then the attacker’s chance of finding $x$ as the preimage
of $\Phi^{\prime}(x)$ will only be marginally better than random guessing.
This observation motivates us to use the closeness between $x*$ and $x$ as an
indicator for privacy leakage. In experiments, we adopt the following four
metrics to measure the similarity, or closeness between $x^{*}$ and $x$:

  * •

Normalized structural similarity index metric (SSIM). SSIM is a perception-
based metric that considers the similarity between images in structural
information, luminance and contrast. The detailed calculation can be found in
[WBS+04]. We normalize SSIM to take value range $[0,1]$ (original SSIM takes
value range $[-1,1]$).

  * •

SIFT similarity (SIFT). We first calculate SIFT [Low04] keypoints and
descriptors ${\cal K}^{*}$ and ${\cal K}$ based on $x^{*}$ and $x$. Then, we
search for matched pairs between ${\cal K}^{*}$ and ${\cal K}$, and compute
the distance of each matched pair. We then filter the good matched pairs based
on the distance, and calculate $\frac{\text{\\#~{}matched~{}good
pairs}}{\text{\\#~{}matched~{}pairs}}$.

  * •

Normalized complementary pHash distance (HASH). We first use a 64-bit
perceptual hashing [Zau10] function $H(\cdot)$ to get hashes for $x^{*}$ and
$x$. Then we calculate the Hamming distance $d(\cdot)$ between $H(x^{*})$ and
$H(x)$. The normalized complementary pHash distance is then defined to be
$(64-d_{\mathrm{ham}}(H(x^{*}),H(x)))/64$. This metric captures the global
similarity between $x^{*}$ and $x$.

  * •

Inference accuracy (INFE). We run the inference of $f(W,x^{*})$, and then
calculate the accuracy: $\mathbf{1}_{y=f(W,x^{*})}$, where $y$ is the label of
$x$. This metric measures whether $x^{*}$ contains the ‘class’ information of
$x$.

For all four metrics above, a larger value indicates a higher similarity
between $x^{*}$ and $x$.

###  4.3 Magnitude-based pruning vs. differential privacy

Now we report our experimental results that strongly suggest that magnitude-
based pruning preserves more privacy (suffer less leakage) than adding
differentially private noise.

#### Utility of pruned networks.

Figure 5(a) and (b) show the accuracy results on MNIST and CIFAR-10 of
corresponding networks pruned by the gradual magnitude-based pruning algorithm
at different sparsity levels.

The task on MNIST achieves the same level of accuracy as the network model
without pruning when the sparsity level is $\leq 0.5$ ($0.5$ means $50\%$ of
the weights in a network are zeros). Its accuracy gradually decreases as the
sparsity level increases. The test with CIFAR-10 maintains the same accuracy
as or better than the model without pruning when the sparsity level is $\leq
0.8$, and then gradually decreases.

Note that our accuracy results at higher sparsity levels are lower than those
reported in [HMD16]. There are two hypotheses. First, our experiment used a
gradual pruning algorithm for speed which may introduce some accuracy losses.
Second, as suggested by [GEH19], magnitude-based pruning with different layer-
wise sparsity (as [HMD16] did) yields better accuracy than pruning layers with
the same target sparsity as in our case.

However, for answering the question if network pruning achieves better utility
than differential privacy for the same targeted accuracy, our experiments can
be viewed as conservative results.

(a) SIFT similarity (b) SSIM similarity (c) HASH similarity (d) INFE
similarity

(e) Inverted MNIST digit from Conv5 layer with pruning (1st row) or adding
noise (2nd row)

Figure 6: Privacy leakage of pruning and adding noise measured by similarity
between inversion and original images (a) - (d), obtained from Conv5 layer
from LeNet-5 trained on MNIST. Shadow represents the value range (we didn’t
report the value range for INFE, because it always has 0 as minimum and 1 as
maximum). Vertical dashed lines match the accuracy; horizontal dashed lines
match the privacy leakage (similarity between inverted and original images).
Also visualization of inverted digits from layers with pruning or adding noise
(e). Sparsity ($k$) is annotated.

(a) SIFT similarity (b) SSIM similarity (c) HASH similarity (d) INFE
similarity

(e) Inverted CIFAR-10 image from Conv5-1 layer with pruning (1st row) or
adding noise (2nd row)

Figure 7: Privacy leakage of pruning and adding noise measured by similarity
between inversion and original images (a) - (d), obtained from Conv5-1 layer
from VGG-19 trained on CIFAR-10. Shadow represents the value range (we didn’t
report the value range for INFE, because it always has 0 as minimum and 1 as
maximum). Vertical dashed lines match the accuracy; horizontal dashed lines
match the privacy leakage (similarity between inverted and original images).
Also visualization of inverted digits from layers with pruning or noise (e).
Sparsity ($k$) is annotated. Figure 8: Error
($\frac{1}{\sqrt{m}}\|h(x)-g(x)\|_{2}$) with different sparsity $k$ and neural
network width $m$. For each $k$ (each row), the value with blue background
indicates the first time that error goes below 0.05 when we increase $m$, and
the ones with green background is for the first time that error goes below
0.01. Best viewed in color.

#### Relative privacy leakage.

To answer Question 1, we need to compare the privacy leakage of applying
magnitude-based pruning ($\Phi^{\prime}_{\text{prune}}$) and adding
differentially private noise ($\Phi^{\prime}_{\text{noise}}$) while requiring
them to yield the same test accuracy. Specifically, we tune the amount of
noise in $\Phi^{\prime}_{\text{noise}}$ to make applying
$\Phi^{\prime}_{\text{prune}}$ and $\Phi^{\prime}_{\text{noise}}$ yield the
same test accuracy. We then run the inversion attack defined in Section 4.2 on
$\Phi^{\prime}_{\text{prune}}$ and $\Phi^{\prime}_{\text{noise}}$, and measure
the closeness between the inverted sample $x^{*}$ and the original sample $x$.

Figure 6 and Figure 7 show the privacy leakage differences between magnitude-
based pruning and adding differentially private noise for the experiments on
MNIST and CIFAR-10 respectively. Given a certain layer, we have executed the
inversion attack on 100 randomly chosen images, and calculated the average
score of each metric between the original images and the inverted ones. We
also report the value range. The sub-figures (a), (b), (c), and (d) of both
figures show the similarity curves of the four metrics for conv5 layer in the
MNIST and CIFAR-10 experiments. The full version with multiple layers can be
found in Appendix F.

These results show that for the same accuracy, there are substantial gaps
between magnitude-based pruning and adding differential private noise in terms
of the similarity measures between inversion and original images, which
suggest that neural network pruning preserve much more privacy than adding
noise.

Take CIFAR-10 (see Figure 7) as an example. When adding noise and pruning
achieve the same similarity (drawing vertical lines on the graph), the privacy
leakage (measured as similarity) of $\Phi^{\prime}_{\text{prune}}$ is always
smaller than that for $\Phi^{\prime}_{\text{noise}}$, which suggests that with
the same utility requirement, pruning helps preserve more privacy than adding
noise. This observation gives us a clear ‘yes’ to Question 1. If viewed from a
different perspective, say matching the privacy leakage instead of accuracy,
which can be interpreted as drawing horizontal lines on the graph, pruning
always yields a higher accuracy ($\sim 10\%$ as shown in Figure 7) than adding
differentially private noise.

To visually demonstrate the gap between the two approaches, Figure 6(e) and
7(e) show the inversions from $\Phi^{\prime}_{\text{prune}}$ and
$\Phi^{\prime}_{\text{noise}}$ with their accuracy matched. For LeNet-5
trained on MNIST (see Figure 6(e)), inverted digits from
$\Phi^{\prime}_{\text{noise}}$ still leak much structural information of the
original image, while inversion from $\Phi^{\prime}_{\text{prune}}$ are more
vague (see sparsity smaller than 0.5), or even unidentifiable (see sparsity
larger than 0.9). Inverted images from VGG-19 layers trained on CIFAR-10 share
consistent observations. This implies that with the same accuracy, pruning may
preserve more privacy than adding noise.

###  4.4 Width vs accuracy

In this section, we aim to answer Question 2 by testing in a synthetic
setting. We show that an $m$ of order $10^{3}$ may be sufficient to give the
equivalence in Theorem 3.2 with a realistic privacy budget.

Theorem 3.2 indicates that with a sufficiently large $m$, we can always draw
an equivalence between adding differentially private noise and applying
magnitude-based pruning. However, the theorem is based on the worst-case
analysis, and does not provide implications for average cases. Also, it is
usually infeasible to have a large $m$ (say, larger than $10^{5}$) in real-
world applications. In order to bridge the gap between the theory and the
practice, we reproduce the setup of Theorem 3.2, and test how large $m$ needs
to be for a synthetic setting.

Specifically, our test is based on a single layer neural network denoted as
$f(x)=\phi(Ax+b)$, where $A\sim{\cal N}(0,\sigma_{A})^{m\times d}$ and
$\phi(a)=\max(a,0)$ is the ReLU activation function. We generate $x$ from the
folded Gaussian distribution, and normalize them such that $\|x\|_{2}=1$. For
simplicity of test, we set the bias term $b$ to be 0.

Our goal is to figure out that, given a target sparsity $k$, how large $m$
needs to be to guarantee an
$(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-closeness (see Definition 3.1)
between the following two perturbations on $f(x)$:

  * •

Adding $(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differentially private
noise $e$ to $f(x)$: $h(x)=f(x)+e$

  * •

Applying magnitude-based pruning on $A$ and get $\widetilde{A}$:
$g(x)=\phi(\widetilde{A}x+b)$

where $e=\mathrm{Lap}(1,\sigma)^{m}\circ(\widetilde{A}-A)x$.

Usually, an $\epsilon_{\mathrm{dp}}\leq 1$ is sufficient for privacy-sensitive
applications. Thus in the test, we set the privacy budgets to be
$\epsilon_{\mathrm{dp}}=0.5,\delta_{\mathrm{dp}}=0.1$ for simplicity. We run
tests for 9 sparsity levels (from $0.1$ to $0.9$ with interval $0.1$), and
vary $m$ to measure the closeness between $h(x)$ and $g(x)$, namely
$\epsilon_{\mathrm{ap}}=\frac{1}{\sqrt{m}}\|h(x)-g(x)\|_{2}$. The results are
shown in Figure 8. As can be seen, for all sparsity levels, $m=20$ is
sufficient to satisfy an $\epsilon_{\mathrm{ap}}=0.05$. To guarantee a
stronger closeness of $\epsilon_{\mathrm{ap}}=0.01$, we can increase $m$
accordingly to 500 for sparsity levels higher than 0.8, and to 1500 for lower
ones. This suggests that in practice, $m$ of order $10^{3}$ will be sufficient
given the equivalence in Theorem 3.2.

##  5 Related work

#### Pruning algorithms for neural network

Traditional deep neural network models are computationally expensive and
memory intensive, which hinders their deployment in applications with limited
memory resources or strict latency requirements. Many progress has been made
to perform model compression in deep networks, including low-rank
factorization [SKS+13, LGR+15], network pruning [LDS90, SB15, HMD16, LKD+17],
and knowledge distillation [HVD15, CCY+17]. Among them, neural network pruning
has been widely adopted because it is able to reduce model sizes by up to one
order of magnitude without significant accuracy loss. The idea of network
pruning dates back to the Optimal Brain Damage in 1990s [LDS90]. Recently, it
has been shown that removing the weights with low magnitude can also achieve a
highly compressed model [HMD16], which is referred to as ‘magnitude-based
pruning’. A recent work by Zhu, Liu, and Han [ZLH19] empirically observed that
pruning neural network gradients helps alleviate privacy leakage without much
utility loss. However, they did not provide theoretical explanation.

#### Differential privacy for deep learning

The concept of $\epsilon$-differential privacy was originally introduced by
Dwork, McSherry, Nissim and Smith [DMNS06]. Later, it was generalized to a
relaxation of $(\epsilon,\delta)$-differential privacy [DKM+06, Dwo09, DR14].
Differential privacy has been successfully applied to many problems. For more
detailed surveys of the applications of differential privacy, we refer the
readers to [Dwo08, Dwo11].

Applying differential privacy techniques in deep learning is an interesting
but non-trivial task. Previous research have customized differential privacy
for different learning tasks and settings [SS15, ACG+16, PWWD16].

However, most of these approaches still use the standard mechanism of adding
noise to satisfy differential privacy, while this work aims to draw an
interesting connection between differential privacy and neural network
pruning.

#### Neural network inversion and sparse recovery

The problem of inverting a neural network is to find the input data point
$x\in\operatorname{{\mathbb{R}}}^{d}$ that yields a given hidden-layer output
$y\in\operatorname{{\mathbb{R}}}^{m}$ under the assumption that weight matrix
$A\in\operatorname{{\mathbb{R}}}^{m\times d}$ is known. Approaches for neural
network inversion generally fall into two categories: by sampling and back-
propagation [LK94, JRM+99, LKN99, VKR05, MV15], and by learning a decoder
network to invert [Bis95, DB16]. Arora, Liang and Ma [ALM15] suggests from a
theoretical perspective that it is possible to construct and train a
generative model which is the reverse of the feedforward network. [LJDD19]
studied how to invert deep generative model. More specifically, they show that
for some realizable case, single layer inversion can be performed exactly in
polynomial, by solving a linear program. Further, they show that for multiple
layers, inversion is NP-hard.

The task of inverting a single-layer linear neural network is intrinsically
similar to the classic notion of sparse recovery [CRT06, Don06, GLPS10,
HIKP12, IK14, Kap16, Kap17, NS19, NSW19], which aims to reconstruct an
approximately $k$-sparse vector $x\in\operatorname{{\mathbb{R}}}^{d}$ from
linear measurements $y=Ax$, where $A\in\operatorname{{\mathbb{R}}}^{m\times
d}$. Note that in sparse recovery context, sparsity denotes the number of non-
zero entries, which is the opposite to what people use in the pruning
community. To connect neural network inversion with sparser recovery, one can
think of the single-layer linear network’s weight matrix as $A$, the hidden-
layer output as $y$, and the network input as $x$. In the linear case, it is
known that in order to achieve the sparse recovery task, the column sparsity
of the sensing matrix $A$ has non-trivial lower bound [NN13]. That is to say,
for a single-layer linear neural network, given the hidden-layer output
$y=Ax$, we need $A$ to have at least some fraction of non-zero to recover the
input $x$. This naturally motivates us to think that pruning may helps
preserve privacy.

##  6 Conclusions

This paper has presented a theoretical result to show that, if a fully-
connected layer of a neural network is wide enough, magnitude-based neural
network pruning is equivalent to adding differentially private noise.

To understand the gap between the theory and practice, the paper reports
experimental results, in a synthetic setting with a realistic differential
privacy budget, that the width of the neural network needs to be only a few
hundreds in order to make the theoretical equivalence hold.

Our experiments with MNIST and CIFAR-10 show that, with the same target
accuracy, magnitude pruning preserves more privacy than adding random noise
(the classical way to provide differential privacy) to neural network.

These results have strong practical implications for two reasons. First, since
neural network pruning has the property that sparsity can be quite high (e.g.
$>90$%) without reducing inference accuracy, it strongly suggests that network
pruning can be an effective method to achieve differential privacy without any
or much reduction of accuracy. Second, although the result is for a single
layer of a neural network, it is quite natural in a distributed or federated
learning system to use a particular layer to communicate among multiple sites.

Several questions remain open. First, Theorem 3.2 is only for a single-layer
fully connected network, and it would be interesting if one can extend it to
multi-layer settings and also convolutional neural networks.

Second, our theoretical finding is based on the worst case analysis, which
means in most cases, $m$ can be much smaller. How to efficiently determine $m$
for different settings requires more investigation.

Third, this paper has used several similarity measures as metrics for privacy
leakage in the absence of true privacy leakage measure. How to quantify
privacy leakage is a challenging question.

Finally, in order to use network pruning as a mechanism to preserve privacy in
a practical distributed or federated learning system, one needs to consider
many design details including which layers to prune, whether or not to prune
layers with the same sparsity, where the work of pruning should be performed,
and how to coordinate among multiple sites.

## Acknowledgments

This project is funded in part by Princeton University fellowship, Pony Ma
Foundation, Simons Foundation, Schmidt Foundation, NSF, DARPA/SRC, Google and
Amazon.

The authors would like to thank Paul Beame, Xin Yang and Ruizhe Zhang for very
useful discussions about anti-concentration section. The authors would like to
thank Tianren Liu for very useful discussions about cryptography. The authors
would like to thank Inrit Dinur, Xiangru Jian, Gautam Kamath, Adam Klivans,
Zhiyuan Li, Binghui Peng, Nikunj Saunchi, Zhenyu Song, Daniel Suo, Grant
Wallace and Fan Yi for very useful discussions.

## References

  * [AAB+16] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al.  Tensorflow: Large-scale machine learning on heterogeneous distributed systems.  In arXiv preprint. https://arxiv.org/pdf/1603.04467, 2016\.
  * [ABY19] Richard Aoun, Marwa Banna, and Pierre Youssef.  Matrix poincare inequalities and concentration.  In arXiv preprint. https://arxiv.org/1910.13797.pdf, 2019\.
  * [ACG+16] 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, 2016.
  * [Act96] Accountability Act.  Health insurance portability and accountability act of 1996.  Public law, 104:191, 1996.
  * [AK18] Lavrentin M Arutyunyan and Egor D Kosov.  Deviation of polynomials from their expectations and isoperimetry.  Bernoulli, 24(3):2043–2063, 2018.
  * [ALM15] Sanjeev Arora, Yingyu Liang, and Tengyu Ma.  Why are deep nets reversible: A simple theory, with implications for training.  In arXiv preprint. https://arxiv.org/pdf/1511.05653.pdf, 2015\.
  * [Ber24] Sergei Bernstein.  On a modification of chebyshev’s inequality and of the error formula of laplace.  Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38–49, 1924.
  * [Bis95] Christopher M Bishop.  Neural networks for pattern recognition.  Oxford university press, 1995.
  * [CAS16] Paul Covington, Jay Adams, and Emre Sargin.  Deep neural networks for youtube recommendations.  In Proceedings of the 10th ACM conference on recommender systems, 2016.
  * [CCY+17] Guobin Chen, Wongun Choi, Xiang Yu, Tony Han, and Manmohan Chandraker.  Learning efficient object detection models with knowledge distillation.  In NIPS, 2017.
  * [Che52] Herman Chernoff.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, pages 493–507, 1952.
  * [CRT06] Emmanuel J Candes, Justin K Romberg, and Terence Tao.  Stable signal recovery from incomplete and inaccurate measurements.  Communications on pure and applied mathematics, 59(8):1207–1223, 2006.
  * [CTV06] Kevin P Costello, Terence Tao, and Van Vu.  Random symmetric matrices are almost surely nonsingular.  Duke Mathematical Journal, 135(2):395–413, 2006.
  * [CW01] Anthony Carbery and James Wright.  Distributional and ${L}^{q}$ norm inequalities for polynomials over convex bodies in ${R}^{n}$.  Mathematical research letters, 8(3):233–248, 2001.
  * [DB16] Alexey Dosovitskiy and Thomas Brox.  Inverting visual representations with convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pages 4829–4837, 2016.
  * [DFLRP+18] Jeffrey De Fauw, Joseph R Ledsam, Bernardino Romera-Paredes, Stanislav Nikolov, Nenad Tomasev, Sam Blackwell, Harry Askham, Xavier Glorot, Brendan O’Donoghue, Daniel Visentin, et al.  Clinically applicable deep learning for diagnosis and referral in retinal disease.  Nature medicine, 24(9):1342, 2018.
  * [DKM+06] 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, 2006.
  * [DMNS06] 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, 2006\.
  * [Don06] David L. Donoho.  Compressed sensing.  IEEE Trans. Information Theory, 52(4):1289–1306, 2006.
  * [DR14] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [Dwo08] Cynthia Dwork.  Differential privacy: A survey of results.  In International conference on theory and applications of models of computation, pages 1–19. Springer, 2008.
  * [Dwo09] Cynthia Dwork.  The differential privacy frontier.  In Theory of Cryptography Conference, pages 496–502. Springer, 2009\.
  * [Dwo11] Cynthia Dwork.  A firm foundation for private data analysis.  Communications of the ACM, 54(1):86–95, 2011.
  * [Erd45] Paul Erdös.  On a lemma of littlewood and offord.  Bulletin of the American Mathematical Society, 51(12):898–902, 1945\.
  * [FJR15] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In CCS, 2015.
  * [GEH19] Trevor Gale, Erich Elsen, and Sara Hooker.  The state of sparsity in deep neural networks.  In arXiv preprint. https://arxiv.org/pdf/1902.09574.pdf, 2019\.
  * [GLPS10] Anna C Gilbert, Yi Li, Ely Porat, and Martin J Strauss.  Approximate sparse recovery: optimizing time and measurements.  In STOC. https://arxiv.org/pdf/0912.0229.pdf, 2010.
  * [GLSS18] Ankit Garg, Yin-Tat Lee, Zhao Song, and Nikhil Srivastava.  A matrix expander chernoff bound.  In STOC. https://arxiv.org/pdf/1704.03864, 2018.
  * [HIKP12] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price.  Nearly optimal sparse Fourier transform.  In STOC. https://arxiv.org/pdf/1201.2501.pdf, 2012.
  * [HMD16] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  In ICLR. https://arxiv.org/1510.00149.pdf, 2016.
  * [Hoe63] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association, 58(301):13–30, 1963.
  * [HVD15] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  In arXiv preprint. https://arxiv.org/pdf/1503.02531.pdf, 2015\.
  * [IK14] Piotr Indyk and Michael Kapralov.  Sample-optimal Fourier sampling in any constant dimension.  In FOCS. https://arxiv.org/pdf/1403.5804.pdf, 2014.
  * [JRM+99] Craig A Jensen, Russell D Reed, Robert J Marks, Mohamed A El-Sharkawi, Jae-Byung Jung, Robert T Miyamoto, Gregory M Anderson, and Christian J Eggen.  Inversion of feedforward neural networks: algorithms and applications.  Proceedings of the IEEE, 87(9):1536–1549, 1999.
  * [Kap16] Michael Kapralov.  Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time.  In STOC. https://arxiv.org/pdf/1604.00845.pdf, 2016.
  * [Kap17] Michael Kapralov.  Sample efficient estimation and recovery in sparse fft via isolation on average.  In FOCS. https://arxiv.org/pdf/1708.04544, 2017.
  * [KB15] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In ICLR. https://arxiv.org/pdf/1412.6980.pdf, 2015.
  * [KMY+16] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  In arXiv preprint. https://arxiv.org/pdf/1610.05492.pdf, 2016\.
  * [Kri09] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, Citeseer, 2009.
  * [KS18] Rasmus Kyng and Zhao Song.  A matrix chernoff bound for strongly rayleigh distributions and spectral sparsifiers from a few random spanning trees.  In FOCS. https://arxiv.org/pdf/1810.08345, 2018.
  * [LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [LCB10] Yann LeCun, Corinna Cortes, and CJ Burges.  Mnist handwritten digit database.  In ATT Labs, volume 2. http://yann.lecun.com/exdb/mnist, 2010\.
  * [LDS90] Yann LeCun, John S Denker, and Sara A Solla.  Optimal brain damage.  In NIPS, 1990.
  * [Leg18] California State Legislature.  California consumer privacy act (ccpa).  https://oag.ca.gov/privacy/ccpa, 2018.
  * [LGR+15] Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oseledets, and Victor Lempitsky.  Speeding-up convolutional neural networks using fine-tuned cp-decomposition.  In ICLR. https://arxiv.org/pdf/1412.6553.pdf, 2015.
  * [LJDD19] Qi Lei, Ajil Jalal, Inderjit S. Dhillon, and Alexandros G. Dimakis.  Inverting deep generative models, one layer at a time.  In NeurIPS. https://arxiv.org/pdf/1906.07437.pdf, 2019.
  * [LK94] Sukhan Lee and Rhee Man Kil.  Inverse mapping of continuous functions using local and global information.  IEEE transactions on neural networks, 5(3):409–423, 1994.
  * [LKD+17] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf.  Pruning filters for efficient convnets.  In ICLR. https://arxiv.org/pdf/1608.08710.pdf, 2017.
  * [LKN99] Bao-Liang Lu, Hajime Kita, and Yoshikazu Nishikawa.  Inverting feedforward neural networks using linear and nonlinear programming.  IEEE Transactions on Neural networks, 10(6):1271–1290, 1999.
  * [LM00] Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  Annals of Statistics, pages 1302–1338, 2000.
  * [LO43] John Edensor Littlewood and Albert Cyril Offord.  On the number of real roots of a random algebraic equation (iii).  Rec. Math. [Mat. Sbornik] N.S., 12(3):277–286, 1943.
  * [Low04] David G Lowe.  Distinctive image features from scale-invariant keypoints.  International journal of computer vision, 60(2):91–110, 2004.
  * [LS17] Paras Lakhani and Baskaran Sundaram.  Deep learning at chest radiography: automated classification of pulmonary tuberculosis by using convolutional neural networks.  Radiology, 284(2):574–582, 2017.
  * [LST+16] Geert Litjens, Clara I Sánchez, Nadya Timofeeva, Meyke Hermsen, Iris Nagtegaal, Iringo Kovacs, Christina Hulsbergen-Van De Kaa, Peter Bult, Bram Van Ginneken, and Jeroen Van Der Laak.  Deep learning as a tool for increased accuracy and efficiency of histopathological diagnosis.  Scientific reports, 6:26286, 2016.
  * [MNV17] Raghu Meka, Oanh Nguyen, and Van Vu.  Anti-concentration for polynomials of independent random variables.  In Theory Of Computing. https://arxiv.org/pdf/1507.00829, 2017\.
  * [MV15] Aravindh Mahendran and Andrea Vedaldi.  Understanding deep image representations by inverting them.  In CVPR. https://arxiv.org/pdf/1412.0035.pdf, 2015.
  * [NN13] Jelani Nelson and Huy L NguyÅn.  Sparsity lower bounds for dimensionality reducing maps.  In STOC. https://arxiv.org/pdf/1211.0995.pdf, 2013.
  * [NRR19] Assaf Naor, Shravas Rao, and Oded Regev.  Concentration of markov chains with bounded moments.  In arXiv preprint. https://arxiv.org/pdf/1906.07260.pdf, 2019\.
  * [NS19] Vasileios Nakos and Zhao Song.  Stronger L2/L2 compressed sensing; without iterating.  In STOC. https://arxiv.org/pdf/1903.02742, 2019.
  * [NSW19] Vasileios Nakos, Zhao Song, and Zhengyu Wang.  (Nearly) Sample-optimal sparse Fourier transform in any dimension; RIPless and Filterless.  In FOCS, pages 1568–1577. https://arxiv.org/pdf/1909.11123.pdf, 2019.
  * [PWWD16] NhatHai Phan, Yue Wang, Xintao Wu, and Dejing Dou.  Differential privacy preservation for deep auto-encoders: an application of human behavior prediction.  In AAAI, 2016.
  * [Qia99] Ning Qian.  On the momentum term in gradient descent learning algorithms.  Neural networks, 12(1):145–151, 1999.
  * [RV13] Alexander Razborov and Emanuele Viola.  Real advantage.  ACM Trans. Comput. Theory, 5(4), November 2013.
  * [SB15] Suraj Srinivas and R Venkatesh Babu.  Data-free parameter pruning for deep neural networks.  In BMVC. https://arxiv/pdf/1507.06149.pdf, 2015.
  * [SKS+13] Tara N Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhadran.  Low-rank matrix factorization for deep neural network training with high-dimensional output targets.  In IEEE international conference on acoustics, speech and signal processing, pages 6655–6659, 2013.
  * [SS15] Reza Shokri and Vitaly Shmatikov.  Privacy-preserving deep learning.  In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1310–1321. ACM, 2015.
  * [SYZ20] Zhao Song, Xi Yang, and Ruizhe Zhang.  Joint anti-concentration for random gaussian polynomials.  In Manuscript, 2020.
  * [SZ15] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In ICLR. https://arxiv.org/pdf/1409.1556.pdf, 2015.
  * [Tro15] Joel A Tropp.  An introduction to matrix concentration inequalities.  Foundations and Trends® in Machine Learning, 8(1-2):1–230, 2015.
  * [VGSR18] Praneeth Vepakomma, Otkrist Gupta, Tristan Swedish, and Ramesh Raskar.  Split learning for health: Distributed deep learning without sharing raw patient data.  In arXiv preprint. https://arxiv.org/pdf/1812.00564.pdf, 2018\.
  * [VKR05] Annamária R Várkonyi-Kóczy and A Rovid.  Observer based iterative neural network model inversion.  In The 14th IEEE International Conference on Fuzzy Systems, 2005\. FUZZ’05., pages 402–407. IEEE, 2005.
  * [WBS+04] Zhou Wang, Alan C Bovik, Hamid R Sheikh, Eero P Simoncelli, et al.  Image quality assessment: from error visibility to structural similarity.  IEEE transactions on image processing, 13(4):600–612, 2004.
  * [YHC+18] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In KDD, 2018.
  * [Zau10] Christoph Zauner.  Implementation and benchmarking of perceptual image hash functions.  2010\.
  * [ZG17] Michael Zhu and Suyog Gupta.  To prune, or not to prune: exploring the efficacy of pruning for model compression.  In ICLR (Workshop), 2017.
  * [ZLH19] Ligeng Zhu, Zhijian Liu, and Song Han.  Deep leakage from gradients.  In NeurIPS. http://arxiv.org/pdf/1906.08935.pdf, 2019.

##  Appendix A Probability tools

In this section we present a number of classical probability tools used in the
proof. Lemma A.1 (Chernoff), A.2 (Hoeffding) and A.3 (Bernstein) are about
tail bounds for random scalar variables. Lemma A.5 and Lemma A.4 state two
standard results for random Gaussian variable. Lemma A.6 is a probability for
Chi-square distribution. Finally, Lemma A.7 is a concentration result on
random matrices.

We state the classical Chernoff bound which is named after Herman Chernoff but
due to Herman Rubin. It gives exponentially decreasing bounds on tail
distributions of sums of independent random variables.

######  Lemma A.1 (Chernoff bound [Che52]).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}=1$ with probability $p_{i}$ and
$X_{i}=0$ with probability $1-p_{i}$, and all $X_{i}$ are independent. Let
$\mu=\operatorname*{{\mathbb{E}}}[X]=\sum_{i=1}^{n}p_{i}$. Then
1\. $\Pr[X\geq(1+\delta)\mu]\leq\exp(-\delta^{2}\mu/3)$, $\forall\delta>0$ ;
2\. $\Pr[X\leq(1-\delta)\mu]\leq\exp(-\delta^{2}\mu/2)$, $\forall 0<\delta<1$.

We state the Hoeffding bound:

######  Lemma A.2 (Hoeffding bound [Hoe63]).

Let $X_{1},\cdots,X_{n}$ denote $n$ independent bounded variables in
$[a_{i},b_{i}]$. Let $X=\sum_{i=1}^{n}X_{i}$, then we have

$\displaystyle\Pr[|X-\operatorname*{{\mathbb{E}}}[X]|\geq t]\leq
2\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

We state the Bernstein inequality:

######  Lemma A.3 (Bernstein inequality [Ber24]).

Let $X_{1},\cdots,X_{n}$ be independent zero-mean random variables. Suppose
that $|X_{i}|\leq M$ almost surely, for all $i$. Then, for all positive $t$,

$\displaystyle\Pr\left[\sum_{i=1}^{n}X_{i}>t\right]\leq\exp\left(-\frac{t^{2}/2}{\sum_{j=1}^{n}\operatorname*{{\mathbb{E}}}[X_{j}^{2}]+Mt/3}\right).$

We state two bounds for Gaussian random variable:

######  Lemma A.4 (folklore).

Let $X\sim{\cal N}(0,\sigma^{2})$, then for all $t\geq 0$, we have

$\displaystyle\Pr[X\geq t]\leq\exp(-t^{2}/2\sigma^{2}).$

######  Lemma A.5 (folklore).

Let $X\sim{\cal N}(0,\sigma^{2})$, that is, the probability density function
of $X$ is given by
$\phi(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{x^{2}}{2\sigma^{2}}}$. Then

$\displaystyle\Pr[|X|\leq t]\leq\frac{4}{5}\frac{t}{\sigma}.$

We state a tool for Chi-square distribution:

######  Lemma A.6 (Lemma 1 on page 1325 of Laurent and Massart [LM00]).

Let $X\sim{\cal X}_{k}^{2}$ be a chi-squared distributed random variable with
$k$ degrees of freedom. Each one has zero mean and $\sigma^{2}$ variance. Then

$\displaystyle\Pr[X-k\sigma^{2}\geq(2\sqrt{kt}+2t)\sigma^{2}]\leq\exp(-t),$
$\displaystyle\Pr[k\sigma^{2}-X\geq 2\sqrt{kt}\sigma^{2}]\leq\exp(-t).$

Matrix concentration inequalities have a large number of applications, for
more details, we refer the readers to a survey by Tropp [Tro15]. Recently,
there are several non-trivial generalizations, e.g., Expander walk [GLSS18,
NRR19], Strongly Rayleigh distributions [KS18], and matrix Poincare inequality
[ABY19]. Here, we state matrix Bernstein inequality, which can be thought of
as a matrix generalization of Lemma A.3.

######  Lemma A.7 (Matrix Bernstein, Theorem 6.1.1 in [Tro15]).

Consider a set of $m$ i.i.d. matrices
$\\{X_{1},\cdots,X_{m}\\}\subset\operatorname{{\mathbb{R}}}^{n_{1}\times
n_{2}}$. Assume that

$\displaystyle\operatorname*{{\mathbb{E}}}[X_{i}]=0,\forall
i\in[m]~{}~{}~{}\mathrm{and}~{}~{}~{}\|X_{i}\|\leq M,\forall i\in[m].$

Let $X=\sum_{i=1}^{m}X_{i}$. Let $\mathrm{Var}[X]$ be the matrix variance
statistic of sum:

$\displaystyle\mathrm{Var}[X]=\max\left\\{\Big{\|}\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}[X_{i}X_{i}^{\top}]\Big{\|},\Big{\|}\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}[X_{i}^{\top}X_{i}]\Big{\|}\right\\}.$

Then

$\displaystyle\operatorname*{{\mathbb{E}}}[\|X\|]\leq(2\mathrm{Var}[X]\cdot\log(n_{1}+n_{2}))^{1/2}+M\cdot\log(n_{1}+n_{2})/3.$

Furthermore, for all $t\geq 0$,

$\displaystyle\Pr[\|X\|\geq
t]\leq(n_{1}+n_{2})\cdot\exp\left(-\frac{t^{2}/2}{\mathrm{Var}[X]+Mt/3}\right).$

##  Appendix B Application of concentration inequality

###  B.1 Application of concentration inequality, truncated Gaussian

######  Lemma B.1 (Inner product between two vectors).

Let $a>0$. Let $u_{1},\cdots,u_{d}$ denote i.i.d. random variables satisfying
$\forall i\in[d]$ $u_{i}=y_{i}\cdot z_{i}$ where $y_{i}\sim{\cal
N}(0,\sigma^{2})$ and

$\displaystyle z_{i}=\begin{cases}1,&|y_{i}|\leq a;\\\
0,&|y_{i}|>a.\end{cases}$

Then, for any fixed vector $x\in\operatorname{{\mathbb{R}}}^{d}$, for any
failure probability $\delta\in(0,1/10)$, we have

$\displaystyle\Pr_{u}[|\langle u,x\rangle|\geq
10\|x\|_{2}a(\sqrt{a/\sigma}+1)\log(1/\delta)]\leq\delta.$

###### Proof.

First, we can compute can $\operatorname*{{\mathbb{E}}}[u_{i}]$

$\displaystyle\operatorname*{{\mathbb{E}}}[u_{i}]=\operatorname*{{\mathbb{E}}}[u_{i}]=0.$

Second, we can upper bound $\operatorname*{{\mathbb{E}}}[(u_{i})^{2}]$ using
Lemma A.5

$\displaystyle\operatorname*{{\mathbb{E}}}[(u_{i})^{2}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[u_{i}^{2}]$ $\displaystyle\leq$
$\displaystyle~{}a^{2}\cdot\Pr[|u_{i}|\leq a]$ $\displaystyle\leq$
$\displaystyle~{}a^{2}\cdot\frac{4}{5}\frac{a}{\sigma}$ $\displaystyle\leq$
$\displaystyle~{}a^{3}/\sigma.$

Third, we can upper bound $|u_{i}x_{i}|$ by $a\cdot\|x\|_{\infty}$.

Using Bernstein inequality, we have

$\displaystyle\Pr[|\langle u,x\rangle|\geq t]\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{\|x\|_{2}^{2}\operatorname*{{\mathbb{E}}}[u_{i}^{2}]+a\|x\|_{\infty}t/3}\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{\|x\|_{2}^{2}a^{3}/\sigma+a\|x\|_{\infty}t/3}\Big{)}.$

Choosing

$\displaystyle
t=5\|x\|_{2}a^{1.5}\sigma^{-0.5}\sqrt{\log(1/\delta)}+5\|x\|_{\infty}a\log(1/\delta)$

gives us

$\displaystyle\Pr[|\langle u,x\rangle|\geq
10\|x\|_{2}a(\sqrt{a/\sigma}+1)\log(1/\delta)]\leq\delta.$

∎

######  Lemma B.2 (Matrix vector multiplication).

Let $a>0$. Let $A_{i,j}$ denote i.i.d. random variables satisfying $\forall
i\in[m],j\in[d].$ $A_{i,j}=y_{i,j}\cdot z_{i,j}$ where $y_{i,j}\sim{\cal
N}(0,\sigma^{2})$ and

$\displaystyle z_{i,j}=\begin{cases}1,&|y_{i,j}|\leq a;\\\
0,&|y_{i,j}|>a.\end{cases}$

Then, for any fixed vector $x\in\operatorname{{\mathbb{R}}}^{d}$, for any
failure probability $\delta\in(0,1/10)$, we have

$\displaystyle\Pr_{A}\Big{[}|\|Ax\|_{2}^{2}-\operatorname*{{\mathbb{E}}}[\|Ax\|_{2}^{2}]|\geq
1000m\|x\|_{2}^{2}(\sigma^{2}+a^{2})\log^{3}(m/\delta)\Big{]}\leq\delta.$

Further, if
$m=\Omega(\epsilon^{-2}\|x\|_{2}^{2}(1+a^{2}/\sigma^{2})\log^{3}(m/\delta))$,

$\displaystyle\Pr_{A}\Big{[}\frac{1}{m}\big{|}\|Ax\|_{2}^{2}-\operatorname*{{\mathbb{E}}}[\|Ax\|_{2}^{2}]\big{|}\geq\epsilon^{2}\|x\|_{2}^{2}\sigma^{2}\Big{]}\leq\delta.$

###### Proof.

We define random variable $b_{i}=(Ax)_{i}^{2}$. We can upper bound
$\operatorname*{{\mathbb{E}}}[b_{i}]$

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{i}]=\operatorname*{{\mathbb{E}}}[(Ax)_{i}^{2}]\leq\|x\|_{2}^{2}\cdot
a^{3}/\sigma.$

Similarly,

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{i}]=\operatorname*{{\mathbb{E}}}[(Ax)_{i}^{2}]\geq
0.1\|x\|_{2}^{2}\cdot a^{3}/\sigma.$

Next, we want to upper bound $\operatorname*{{\mathbb{E}}}[b_{i}^{2}]$, for
simplicity, let $u$ denote the $i$-th row of matrix $A$,

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{i}^{2}]-(\operatorname*{{\mathbb{E}}}[b_{i}])^{2}=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[\langle
u,x\rangle^{4}]-(\operatorname*{{\mathbb{E}}}[\langle u,x\rangle^{2}])^{2}$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}\Big{[}(\sum_{i=1}^{d}u_{i}x_{i})^{4}\Big{]}-\Big{(}\operatorname*{{\mathbb{E}}}\Big{[}(\sum_{i=1}^{d}u_{i}x_{i})^{2}\Big{]}\Big{)}^{2}.$

For the first term, we have

$\displaystyle\operatorname*{{\mathbb{E}}}\Big{[}(\sum_{i=1}^{d}u_{i}x_{i})^{4}\Big{]}=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}\Big{[}\sum_{i=1}^{d}u_{i}^{4}x_{i}^{4}\Big{]}+3\operatorname*{{\mathbb{E}}}\Big{[}\sum_{i=1}^{d}\sum_{j\in[d]\backslash\\{i\\}}u_{i}^{2}x_{i}^{2}u_{j}^{2}x_{j}^{2}\Big{]}$
$\displaystyle\leq$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[u_{i}^{4}]\cdot\|x\|_{4}^{4}+3(\operatorname*{{\mathbb{E}}}[u_{i}^{2}])^{2}\cdot\|x\|_{2}^{4}$
$\displaystyle\leq$
$\displaystyle~{}4\operatorname*{{\mathbb{E}}}[u_{i}^{4}]\cdot\|x\|_{2}^{4}.$

For the second term, we have

$\displaystyle\Big{(}\operatorname*{{\mathbb{E}}}\Big{[}(\sum_{i=1}^{d}u_{i}x_{i})^{2}\Big{]}\Big{)}^{2}=\Big{(}\sum_{i=1}^{d}\operatorname*{{\mathbb{E}}}[u_{i}^{2}]x_{i}^{2}\Big{)}^{2}=(\operatorname*{{\mathbb{E}}}[u_{i}^{2}])^{2}\cdot\|x\|_{2}^{4}.$

Thus, we have

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{i}^{2}]-(\operatorname*{{\mathbb{E}}}[b_{i}])^{2}\leq
4\operatorname*{{\mathbb{E}}}[u_{i}^{4}]\cdot\|x\|_{2}^{4}\leq
64\sigma^{4}\|x\|_{2}^{4}.$

We also need to upper bound $|b_{i}|$. Apply Lemma B.1, we have, for a fixed
$i\in[m]$,

$\displaystyle|b_{i}|\leq(10\|x\|_{2}a(\sqrt{a/\sigma}+1)\log(m/\delta))^{2}:=b_{\max}$

holds with probability at least $1-\delta/m$.

Taking a union bound over $m$ coordinates, with probability $1-\delta$, we
have : for all $i\in[m]$, $|b_{i}|\leq b_{\max}$.

Applying Bernstein inequality (Lemma A.3) on $\sum_{i=1}^{m}b_{i}$ again

$\displaystyle\Pr\Big{[}\Big{|}\sum_{i=1}^{m}(b_{i}-\operatorname*{{\mathbb{E}}}[b_{i}])\Big{|}\geq
t\Big{]}\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{\sum_{i=1}^{m}\mathrm{Var}[b_{i}]+b_{\max}t/3}\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{64m\sigma^{4}\|x\|_{2}^{4}+b_{\max}t/3}\Big{)}.$

Choosing
$t=50m\sigma^{2}\|x\|_{2}^{2}\log(1/\delta)+50mb_{\max}\log(1/\delta)$, we
complete the proof. ∎

###  B.2 Application of concentration inequalities, classical random Gaussian

######  Lemma B.3 (Inner product between a random guassian vector and a fixed
vector).

Let $a>0$. Let $u_{1},\cdots,u_{d}$ denote i.i.d. random guassian variables
where $u_{i}\sim{\cal N}(0,\sigma_{1}^{2})$.

Then, for any fixed vector $e\in\operatorname{{\mathbb{R}}}^{d}$, for any
failure probability $\delta\in(0,1/10)$, we have

$\displaystyle\Pr_{u}\Big{[}|\langle u,e\rangle|\geq
2\sigma_{1}\|e\|_{2}\sqrt{\log(d/\delta)}+\sigma_{1}\|e\|_{\infty}\log^{1.5}(d/\delta)\Big{]}\leq\delta.$

###### Proof.

First, we can compute $\operatorname*{{\mathbb{E}}}[u_{i}]$

$\displaystyle\operatorname*{{\mathbb{E}}}[u_{i}]=\operatorname*{{\mathbb{E}}}[u_{i}]=0.$

Second, we can compute $\operatorname*{{\mathbb{E}}}[(u_{i})^{2}]$

$\displaystyle\operatorname*{{\mathbb{E}}}[(u_{i})^{2}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[u_{i}^{2}]=\sigma_{1}^{2}.$

Third, we can upper bound $|u_{i}|$ and $|u_{i}e_{i}|$.

$\displaystyle\Pr_{u}[|u_{i}-\operatorname*{{\mathbb{E}}}[u_{i}]|\geq t_{1}]$
$\displaystyle\leq\exp\Big{(}-\frac{t_{1}^{2}}{2\sigma_{1}^{2}}\Big{)}.$

Take $t_{1}=\sqrt{2\log(d/\delta)}\sigma_{1}$, then for each fixed $i\in[d]$,
we have, $|u_{i}|\leq\sqrt{2\log(d/\delta)}\sigma_{1}$ holds with probability
$1-\delta/d$.

Taking a union bound over $d$ coordinates, with probability $1-\delta$, we
have : for all $i\in[d]$, $|u_{i}|\leq\sqrt{2\log(d/\delta)}\sigma_{1}$.

Let $E_{1}$ denote the event that, $\max_{i\in[d]}|u_{i}e_{i}|$ is upper
bounded by $\sqrt{2\log(d/\delta)}\sigma_{1}\|e\|_{\infty}$. $\Pr[E_{1}]\geq
1-\delta$.

Using Bernstein inequality, we have

$\displaystyle\Pr_{u}[|\langle u,e\rangle|\geq t]\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{\|e\|_{2}^{2}\operatorname*{{\mathbb{E}}}[u_{i}^{2}]+\max_{i\in[d]}|u_{i}e_{i}|\cdot
t/3}\Big{)}$ $\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{\|e\|_{2}^{2}\sigma_{1}^{2}+\sqrt{2\log(d/\delta)}\sigma_{1}\|e\|_{\infty}\cdot
t/3}\Big{)}$ $\displaystyle\leq$ $\displaystyle~{}\delta,$

where the second step follows from $\Pr[E_{1}]\geq 1-\delta$ and
$\operatorname*{{\mathbb{E}}}[u_{i}^{2}]=\sigma_{1}^{2}$, and the last step
follows from choice of $t$:

$\displaystyle
t=2\sigma_{1}\|e\|_{2}\sqrt{\log(d/\delta)}+\sigma_{1}\|e\|_{\infty}\log^{1.5}(d/\delta).$

Taking a union with event $E_{1}$, we have

$\displaystyle\Pr[|\langle u,e\rangle|\geq t]\leq 2\delta.$

Rescaling $\delta$ completes the proof.

∎

######  Lemma B.4 (Inner product between two random guassian vectors).

Let $a>0$. Let $u_{1},\cdots,u_{d}$ denote i.i.d. random Gaussian variables
where $u_{i}\sim{\cal N}(0,\sigma_{1}^{2})$ and $e_{1},\cdots,e_{d}$ denote
i.i.d. random Gaussian variables where $e_{i}\sim{\cal N}(0,\sigma_{2}^{2})$

Then, for any failure probability $\delta\in(0,1/10)$, we have

$\displaystyle\Pr_{u,e}\Big{[}|\langle u,e\rangle|\geq
10^{4}\sigma_{1}\sigma_{2}\sqrt{d}\log^{2}(d/\delta)\Big{]}\leq\delta.$

###### Proof.

First, using Lemma A.6, we compute the upper bound for $\|e\|_{2}^{2}$

$\displaystyle\Pr_{e}[\|e\|_{2}^{2}-d\sigma_{2}^{2}\geq(2\sqrt{dt}+2t)\sigma_{2}^{2}]\leq\exp(-t).$

Take $t=\log(1/\delta)$, then with probability $1-\delta$,

$\displaystyle\|e\|_{2}^{2}\leq(d+3\sqrt{d\log(1/\delta)}+2\log(1/\delta))\sigma_{2}^{2}\leq
4d\log(1/\delta)\sigma_{2}^{2}.$

Thus

$\displaystyle\Pr_{e}[\|e\|_{2}\leq 4\sqrt{d\log(1/\delta)}\sigma_{2}]\geq
1-\delta.$

Second, we compute the upper bound for $\|e\|_{\infty}$ (the proof is similar
to Lemma B.3)

$\displaystyle\Pr_{e}[|\|e\|_{\infty}\leq\sqrt{\log(d/\delta)}\sigma_{2}]$
$\displaystyle\geq 1-\delta.$

We define $t$ and $t^{\prime}$ as follows

$\displaystyle t=$
$\displaystyle~{}4\cdot(\sigma_{1}\|e\|_{2}\sqrt{\log(d/\delta)}+\sigma_{1}\|e\|_{\infty}\log^{1.5}(d/\delta))$
$\displaystyle t^{\prime}=$
$\displaystyle~{}8\cdot(\sigma_{1}\sigma_{2}\sqrt{d}\log(d/\delta)+\sigma_{1}\sigma_{2}\log^{2}(d/\delta)).$

From the above calculations, we can show

$\displaystyle\Pr_{e}[t^{\prime}\geq t]\geq 1-2\delta.$

By Lemma B.3, for fixed $e$, we have

$\displaystyle\Pr_{u}[|\langle u,e\rangle|\geq t]\leq\delta.$

Overall, we have

$\displaystyle\Pr_{e,u}[|\langle u,e\rangle|\geq t^{\prime}]\leq 3\delta.$

Rescaling $\delta$ completes the proof. ∎

######  Lemma B.5 (Concentration of folded Gaussian).

Let matrix $A\in\operatorname{{\mathbb{R}}}^{m\times d}$ be defined as each
entry is i.i.d. random variables satisfying $\forall i\in[m]$, $j\in[d]$.
$A_{i,j}=y_{i,j}$ where $y_{i,j}\sim{\cal N}(0,\sigma_{A}^{2})$. Let
$\overline{A}\in\operatorname{{\mathbb{R}}}^{m\times d}$ be defined as,
$\forall i\in[m],j\in[d]$, $\overline{A}_{i,j}=y_{i,j}\cdot z_{i,j}$ where

$\displaystyle z_{i,j}=\begin{cases}1,&\mathrm{~{}if~{}}0\leq y_{i,j}\leq
a;\\\ 0,&\mathrm{~{}otherwise~{}}.\end{cases}$

Let $x\in\operatorname{{\mathbb{R}}}^{d}_{+}$ denote a non-negative vector
where $\sum_{i=1}^{d}x_{i}=1$.

1) For any failure possibility $\delta\in(0,1/10)$, we have

$\displaystyle\Pr\left[\forall i\in[m],(\bar{A}x)_{i}\geq\sigma_{A}\cdot
C\right]>1-\delta,$

where

$\displaystyle
C:=\frac{a^{2}}{6\sigma_{A}^{2}}-(\frac{2a^{3}}{9\sigma_{A}^{3}})^{1/2}\cdot\sqrt{\log(m/\delta)}-\frac{2a}{3\sigma_{A}}\cdot\log(m/\delta).$

2) For any failure possibility $\delta\in(0,1/10)$, if $a/\sigma_{A}\geq
20\log(m/\delta)$, then

$\displaystyle\Pr\left[\forall i\in[m],(\bar{A}x)_{i}\geq\sigma_{A}\cdot
0.02\cdot(a^{2}/\sigma_{A}^{2})\right]>1-\delta.$

###### Proof.

For a fixed $i\in[m]$, for each $j\in[d]$, we define

$\displaystyle b_{j}=\bar{A}_{i,j}x_{j}.$

We first calculate $\operatorname*{{\mathbb{E}}}[b_{j}]$,
$\operatorname*{{\mathbb{E}}}[b_{j}^{2}]$ and
$\operatorname*{\mathrm{Var}}[b_{j}]$.

We provide a lower bound for $\operatorname*{{\mathbb{E}}}[b_{j}]$,

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{j}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[A_{i,j}]x_{j}$ $\displaystyle=$
$\displaystyle~{}x_{j}\int_{0}^{a}\frac{1}{\sigma_{A}\sqrt{2\pi}}\exp(-x/\sigma_{A}^{2})x\mathrm{d}x$
$\displaystyle\geq$
$\displaystyle~{}\frac{a^{2}x_{j}}{2\sigma_{A}\sqrt{2\pi}}$
$\displaystyle\geq$ $\displaystyle~{}\frac{a^{2}x_{j}}{6\sigma_{A}}.$

We give an upper bound for $\operatorname*{{\mathbb{E}}}[b_{j}^{2}]$,

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{j}^{2}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[A_{i,j}^{2}]x_{j}^{2}$
$\displaystyle=$
$\displaystyle~{}x_{j}^{2}\int_{0}^{a}\frac{1}{\sigma_{A}\sqrt{2\pi}}\exp(-x/\sigma_{A}^{2})x^{2}\mathrm{d}x$
$\displaystyle\leq$
$\displaystyle~{}\frac{a^{3}x_{j}^{2}}{3\sigma_{A}\sqrt{2\pi}}$
$\displaystyle\leq$ $\displaystyle~{}\frac{a^{3}x_{j}^{2}}{9\sigma_{A}}.$

We can upper bound $\operatorname*{\mathrm{Var}}[b_{j}]$,

$\displaystyle\operatorname*{\mathrm{Var}}[b_{j}]=$
$\displaystyle\operatorname*{{\mathbb{E}}}[b_{j}^{2}]-\operatorname*{{\mathbb{E}}}[b_{j}]^{2}\leq\operatorname*{{\mathbb{E}}}[b_{j}^{2}]\leq\frac{a^{3}x_{j}^{2}}{9\sigma_{A}}.$

Then, we can lower bound $\sum_{j=1}^{d}\operatorname*{{\mathbb{E}}}[b_{j}]$

$\displaystyle\sum_{j=1}^{d}\operatorname*{{\mathbb{E}}}[b_{j}]\geq\frac{a^{2}}{6\sigma_{A}}\sum_{j=1}^{d}x_{j}=\frac{a^{2}}{6\sigma_{A}},$

where the last step follows from $\sum_{j=1}^{d}x_{j}=1$.

Next, we can upper bound $b_{j}$ and
$\sum_{j=1}^{d}\operatorname*{\mathrm{Var}}[b_{j}]$

$\displaystyle M:=\max_{j\in[d]}b_{j}\leq$
$\displaystyle~{}\max_{j\in[d]}x_{j}a\leq a.$

$\displaystyle\sum_{j=1}^{d}\operatorname*{\mathrm{Var}}[b_{j}]\leq$
$\displaystyle\sum_{j=1}^{d}\frac{a^{3}x_{j}^{2}}{9\sigma_{A}}\leq\sum_{j=1}^{d}\frac{a^{3}x_{j}}{9\sigma_{A}}=\frac{a^{3}}{9\sigma_{A}}.$

Applying Bernstein inequality (Lemma A.3) on
$\sum_{j=1}^{d}(b_{j}-\operatorname*{{\mathbb{E}}}[b_{j}])$

$\displaystyle\Pr\Big{[}\sum_{j=1}^{d}(b_{j}-\operatorname*{{\mathbb{E}}}[b_{j}])\leq-t\Big{]}\leq$
$\displaystyle\exp\Big{(}-\frac{t^{2}/2}{\sum_{j=1}^{d}\operatorname*{\mathrm{Var}}[b_{j}]+Mt/3}\Big{)}$
$\displaystyle\leq$
$\displaystyle\exp\Big{(}-\frac{t^{2}/2}{a^{3}/9\sigma_{A}+at/3}\Big{)}.$

Taking

$\displaystyle
t=\sigma_{A}\cdot(\sqrt{2a^{3}/9\sigma_{A}^{3}\cdot\log(m/\delta)}+2a/3\sigma_{A}\cdot\log(m/\delta)),$

then for any $i\in[m]$,

$\displaystyle\Pr\Big{[}\sum_{j=1}^{d}b_{j}\geq
a^{2}/(6\sigma_{A})-t\Big{]}\geq$
$\displaystyle~{}\Pr\Big{[}\sum_{j=1}^{d}b_{j}\geq\sum_{j=1}^{d}\operatorname*{{\mathbb{E}}}[b_{j}]-t\Big{]}$
$\displaystyle\geq$ $\displaystyle~{}1-\delta,$

where the first step holds because
$\sum_{j=1}^{d}\operatorname*{{\mathbb{E}}}[b_{j}]>a^{2}/(6\sigma_{A})$.

Since $(\bar{A}x)_{i}=\sum_{j=1}^{d}b_{j}$, we have for any $i\in[m]$,

$\displaystyle\Pr\left[(\bar{A}x)_{i}\geq\sigma_{A}\cdot\Big{(}a^{2}/6\sigma_{A}^{2}-\sqrt{(2a^{3}/9\sigma_{A}^{3})\cdot\log(m/\delta)}-(2a/3\sigma_{A})\cdot\log(m/\delta)\Big{)}\right]>1-\delta/m.$

Taking a union bound over all $i\in[m]$ completes the proof. ∎

##  Appendix C Anti-concentration

Given a number of independent random variables, the well-known Central Limit
Theorem (CLT) states that their sum has good concentration under certain
conditions. Such concentration results like the Chernoff bound [Che52] and
Hoeffding’s inequality [Hoe63] are among the central tools in Theoretical
Computer Science (TCS). From the opposite perspective, we can also ask for
_anti-concentration_ results. For example, let $x$ be a Rademacher variable
(choosing $\pm 1$ with probability $1/2$) and let $a$ denote a vector in
$\operatorname{{\mathbb{R}}}^{d}$. The celebrated Littlewood-Offord Lemma
states that any $d$-variate degree-$1$ polynomial
$p(x)=\sum_{i=1}^{d}a_{i}x_{i}$ does not concentrate on any particular value.

######  Theorem C.1 (Littlewood and Offord [LO43]).

Let $C>0$ denote a universal constant. For any linear form $p$ satisfying
$|a_{i}|\geq 1$, $\forall i\in[d]$, and any open interval $I$ of length $1$,
we have

$\displaystyle\Pr_{x\sim\\{-1,+1\\}^{d}}[p(x)\in I]\leq C\cdot\frac{\log
d}{\sqrt{d}}.$

Two years later, Erdös [Erd45] removed the $\log d$ factor in Theorem C.1.
Recently, Theorem C.1 has been generalized to higher degree polynomials by
[CTV06, RV13, MNV17].

Instead of considering $x_{i}$ as $\\{-1,+1\\}$ random variables, Carbery and
Wright [CW01] showed the anti-concentration result for $x_{i}$ chosen as
i.i.d. Gaussians.

######  Theorem C.2 (Carbery and Wright [CW01]).

Let $p:\operatorname{{\mathbb{R}}}^{d}\rightarrow\operatorname{{\mathbb{R}}}$
denote a degree-$k$ polynomial with $d$ variables. There is a universal
constant $C>0$ such that

$\displaystyle\Pr_{x\sim{\cal
N}(0,I_{d})}\Big{[}|p(x)|\leq\delta\sqrt{\operatorname*{\mathrm{Var}}[p(x)]}\Big{]}\leq
C\cdot\delta^{1/k}.$

These are worst-case results in the sense that they hold for arbitrary
polynomials. For example, Theorem C.2 is tight for any polynomial that is a
perfect $k$-th power.

We can generalize Theorem C.2 into the following111The generalization also has
been observed in [SYZ20], for the completeness, we provide the proof here.:

######  Lemma C.3 (An variation of [CW01], Anti-concentration of sum of
truncated Gaussians).

Let $x_{1},\cdots,x_{n}$ be $n$ i.i.d. zero-mean Gaussian random variables
${\cal N}(0,1)$. Let
$p:\operatorname{{\mathbb{R}}}^{n}\rightarrow\operatorname{{\mathbb{R}}}$
denote a degree-1 polynomial defined as

$\displaystyle p(x_{1},\cdots,x_{n})=\sum_{i=1}^{n}\alpha_{i}x_{i}.$

Let $f$ denote a truncation function where $f(x)=x$ if $|x|\leq a$, and
$f(x)=0$ if $|x|>a$. Then we have

$\displaystyle\Pr_{x\sim{\cal
N}(0,I_{d})}\Big{[}|p(f(x))|\leq\min\\{a,0.1\\}\cdot\delta\cdot\|\alpha\|_{2}\Big{]}\geq
C\cdot\delta.$

###### Proof.

Let $\mu:\mathbb{R}^{n}\rightarrow\mathbb{R}_{\geq 0}$ be the truncated
Gaussian distribution. We first argue that $\mu$ is log-concave. Indeed, for
any $x,y\in\mathbb{R}^{n}$ and $\lambda\in[0,1]$, if $\mu(x)=0$ or $\mu(y)=0$,
then we must have

$\displaystyle\mu(\lambda x+(1-\lambda)y)\geq
0=(\mu(x))^{\lambda}\cdot(\mu(y))^{1-\lambda}.$

On the other hand, if $\mu(x)>0$ and $\mu(y)>0$, then we must have
$\mu(\lambda x+(1-\lambda)y)>0$, because

$\displaystyle\|\lambda
x+(1-\lambda)y\|_{2}\leq\lambda\|x\|_{2}+(1-\lambda)\|y\|_{2},$

hence $\mu$ would not truncate at $\lambda x+(1-\lambda)y$. Notice that
Gaussian distribution is log-concave. Let
$\mu^{\prime}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be the density function of
Gaussian distribution, then $\mu(x)=C_{0}\cdot\mu^{\prime}(x)$ for some
universal constant $C_{0}>0$ for all $x$ that is not truncated. so in this
case we still have

$\displaystyle\mu(\lambda x+(1-\lambda)y)=$
$\displaystyle~{}C_{0}\cdot\mu^{\prime}(\lambda x+(1-\lambda)y)$
$\displaystyle\geq$
$\displaystyle~{}C_{0}\cdot(\mu^{\prime}(x))^{\lambda}\cdot(\mu^{\prime}(y))^{1-\lambda}$
$\displaystyle=$
$\displaystyle~{}(C_{0}\mu^{\prime}(x))^{\lambda}\cdot(C_{0}\mu^{\prime}(y))^{1-\lambda}$
$\displaystyle=$
$\displaystyle~{}(\mu(x))^{\lambda}\cdot(\mu(y))^{1-\lambda}.$

So we conclude that $\mu$ is log-concave.

Now we apply Theorem C.5 on $\mu$ and $p$. By setting $q=2$ and $d=1$, we have

$\displaystyle\Big{(}\int_{x\in\mathbb{R}^{n}}|p(x)|^{2}\mathrm{d}\mu\Big{)}^{1/2}\cdot\mu(|p(x)|\leq\alpha)\leq
C\cdot\alpha.$ (1)

Notice that

$\displaystyle\int_{x\in\mathbb{R}^{n}}|p(x)|^{2}\mathrm{d}\mu=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{x\sim\mu}\Big{[}\Big{(}\sum_{i=1}^{n}\alpha_{i}x_{i}\Big{)}^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{n}\alpha_{i}^{2}\operatorname*{{\mathbb{E}}}_{x\sim\mu}[x_{i}^{2}]$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{n}\alpha_{i}^{2}\operatorname*{\mathrm{Var}}_{x_{i}\sim\mu_{i}}[x_{i}],$

where $\mu_{i}:\mathbb{R}\rightarrow\mathbb{R}$ is the distribution on the
$i$-th coordinate, $\forall i\in[n]$. Hence we can rewrite Eq. (1) as

$\displaystyle\Pr_{x\sim{\cal
N}(0,I_{d})}\left[\Big{|}\sum_{i=1}^{n}\alpha_{i}f(x_{i})\Big{|}\leq\delta\left(\sum_{i=1}^{n}\alpha_{i}^{2}\operatorname*{\mathrm{Var}}_{x_{i}\sim\mu_{i}}[x_{i}]\right)^{1/2}\right]\geq
C\cdot\delta.$

By Claim C.4, we have

$\displaystyle\Pr_{x\sim\operatorname{{\mathcal{N}}}(0,I_{d})}\left[|p(f(x))|\leq\delta\left(\sum_{i=1}^{n}\alpha_{i}^{2}\cdot\left(1-\sqrt{\frac{2}{\pi}}\cdot\frac{a\cdot
e^{-a^{2}/2}}{\mathrm{erf}(a/\sqrt{2})}\right)\right)^{1/2}\right]\geq
C\cdot\delta.$

For $0\leq a\ll 1$,

$\displaystyle 1-\sqrt{\frac{2}{\pi}}\cdot\frac{a\cdot
e^{-a^{2}/2}}{\mathrm{erf}(a/\sqrt{2})}=\frac{5}{6}a^{2}+o(a^{3}).$

Hence,

$\displaystyle\Pr_{x\sim\operatorname{{\mathcal{N}}}(0,I_{d})}\Big{[}|p(f(x))|\leq\delta
a\|\alpha\|_{2}\Big{]}\geq C\cdot\delta.$

For $a\geq 1$,

$\displaystyle 1-\sqrt{\frac{2}{\pi}}\cdot\frac{a\cdot
e^{-a^{2}/2}}{\mathrm{erf}(a/\sqrt{2})}=\Theta\left(1-ae^{-a^{2}}-e^{-a^{2}/2}/a\right).$

Hence,

$\displaystyle\Pr_{x\sim\operatorname{{\mathcal{N}}}(0,I_{d})}\left[|p(f(x))|\leq\delta(1-ae^{-a^{2}}-e^{-a^{2}/2}/a)^{1/2}\|\alpha\|_{2}\right]\geq
C\cdot\delta.$

When $a\geq 1$, we have $0.025\leq(1-ae^{-a^{2}}-e^{-a^{2}/2}/a)\leq 1$. So we
can combine the above two cases to get

$\displaystyle\Pr_{x\sim\operatorname{{\mathcal{N}}}(0,I_{d})}\Big{[}|p(f(x))|\leq\min\\{a,0.1\\}\cdot\delta\|\alpha\|_{2}\Big{]}\geq
C\cdot\delta.$

∎

######  Claim C.4.

Let $x\in\operatorname{{\mathbb{R}}}$ be a standard Gaussian random variable
$\operatorname{{\mathcal{N}}}(0,1)$. Let $f$ denote a truncation function
where $f(x)=x$ if $|x|\leq a$, and $f(x)=0$ if $|x|>a$. Then, we have

$\displaystyle\operatorname*{\mathrm{Var}}[f(x)]=~{}1-\sqrt{\frac{2}{\pi}}\cdot\frac{a\cdot
e^{-a^{2}/2}}{\mathrm{erf}(a/\sqrt{2})},$

where $\mathrm{erf}(x)=\frac{2}{\sqrt{\pi}}\int_{0}^{x}e^{-t^{2}}\mathrm{d}t$.

######  Theorem C.5 ([AK18]).

Let $\mu:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a log-concave measure over
$\mathbb{R}^{n}$. Let
$L^{1}(\mu)=\int_{x\in\mathbb{R}^{n}}|\mu(x)|\mathrm{d}x$. For any $q>0$ and
polynomial $p:\mathbb{R}^{n}\rightarrow\mathbb{R}$, define the $\ell_{q}$ norm
of $p$ with respect to the measure $\mu$ as

$\displaystyle\|p\|_{q}=\left(\int p^{q}\mathrm{d}\mu\right)^{1/q}.$

Assume $p$ has degree $d$. Then there exists constant $C(d)>0$ that only
depends on $d$ so that for all $\alpha>0$ and all $q>0$,

$\displaystyle\Big{(}\int|p(x)|^{q/d}\mathrm{d}\mu\Big{)}^{1/q}\cdot\mu(|p(x)|\leq\alpha)\leq
C(d)\cdot\alpha^{1/d}.$

##  Appendix D Sensitivity

###  D.1 Concentration of folded Gaussian

######  Lemma D.1 (concentration of folded gaussian).

Let matrix $A\in\operatorname{{\mathbb{R}}}^{m\times d}$ be defined as each
entry is i.i.d. random variables satisfying $\forall i\in[m]$, $j\in[d]$.
$A_{i,j}=y_{i,j}$ where $y_{i,j}\sim{\cal N}(0,\sigma_{A}^{2})$. Let
$z_{i,j}=|y_{i,j}|$, then $\forall j\in[d]$,

$\displaystyle\Pr\Big{[}\sum_{i=1}^{m}z_{i,j}-\operatorname*{{\mathbb{E}}}[z_{i,j}]>\sigma_{A}m+4\sigma_{A}\sqrt{m}\log^{1.5}(md/\delta)\Big{]}\leq\delta.$

###### Proof.

For a fixed $j$, let $b_{i}=z_{i,j}$. First we calculate
$\operatorname*{{\mathbb{E}}}[b_{i}]$

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{i}]=$
$\displaystyle~{}\int_{0}^{\infty}\frac{2}{\sqrt{2\pi\sigma_{A}^{2}}}\exp(-x^{2}/2\sigma_{A}^{2})x\mathrm{d}x$
$\displaystyle=$ $\displaystyle~{}\sigma_{A}\sqrt{2/\pi}.$

Second, we calculate $\operatorname*{{\mathbb{E}}}[b_{i}^{2}]$

$\displaystyle\operatorname*{{\mathbb{E}}}[b_{i}^{2}]=\operatorname*{{\mathbb{E}}}[z_{i,j}^{2}]=\operatorname*{{\mathbb{E}}}[y_{i,j}^{2}]=\sigma_{A}^{2}.$

According to Lemma A.4, we can upper bound $z_{i,j}$

$\displaystyle\Pr[z_{i,j}>t]=\Pr[|y_{i,j}|>t]\leq\exp(-t/\delta_{2}^{2}).$

Taking $t=\sigma_{A}\sqrt{\log(md/\delta_{1})}:=M$, we have $\forall i\in[m]$,
$j\in[d]$

$\displaystyle\Pr[\max_{i,j}{z_{i,j}}>t]\leq\delta_{2}.$

Applying Bernstein inequality on $\sum_{i=1}^{m}b_{i}$

$\displaystyle\Pr\Big{[}\Big{|}\sum_{i=1}^{m}(b_{i}-\operatorname*{{\mathbb{E}}}[b_{i}])\Big{|}\geq
t\Big{]}\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{\sum_{i=1}^{m}\mathrm{Var}[b_{i}]+b_{\max}t/3}\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}-\frac{t^{2}/2}{m\sigma_{A}^{2}+\sigma_{A}t\sqrt{\log(md/\delta_{2})}/3}\Big{)}.$

Choosing $t=\sigma_{A}m+4\sigma_{A}\sqrt{m}\log^{1.5}(md/\delta)$, we have

$\displaystyle\Pr\Big{[}\sum_{i=1}^{m}z_{i,j}-\operatorname*{{\mathbb{E}}}[z_{i,j}]>t\Big{]}\leq\delta.$

∎

###  D.2 $\ell_{1}$-sensitivity functions of single layer neural network

######  Lemma D.2 ($\ell_{1}$-norm sensitivity of single layer neural
network).

Let $x\in[0,1]^{d}$, fully connected matrix $A\in{\cal
N}(0,\sigma_{A})^{m\times d}$, bias matrix $b\in\mathbb{R}^{m}$, and $\phi$ is
the ReLU activation function. Let $f(x)=\phi(Ax+b)$ denote a single layer
network, then for all neighboring inputs
$x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}$ that differ at most in one
entry, we have

$\displaystyle\Pr\Big{[}\mathrm{GS}_{1}(f)\leq\sigma_{A}m+4\sigma_{A}\sqrt{m}\log^{1.5}(md/\delta)\Big{]}\geq
1-\delta.$

###### Proof.

Let $k$ denote the index that $x_{1}$ and $x_{2}$ are different.

$\displaystyle\mathrm{GS}_{1}(f)=$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|f(x_{1})-f(x_{2})\|_{1}$
$\displaystyle=$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|\phi(Ax_{1}+b)-\phi(Ax_{2}+b)\|_{1}$
$\displaystyle\leq$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|(Ax_{1}+b)-(Ax_{2}+b)\|_{1}$
$\displaystyle=$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|(A(x_{1}-x_{2})\|_{1}$
$\displaystyle=$ $\displaystyle~{}\|A_{*,k}\|_{1}$ $\displaystyle\leq$
$\displaystyle~{}\sigma_{A}m+4\sigma_{A}\sqrt{m}\log^{1.5}(md/\delta),$

where the fourth step follows that $x_{1}$ and $x_{2}$ differ in the $k$-th
entry, and the fifth step follows Lemma D.1. ∎

###  D.3 $\ell_{2}$-sensitivity functions of single layer neural network

######  Lemma D.3 ($\ell_{2}$-norm sensitivity of single layer neural
network).

Let $x\in[0,1]^{d}$, fully connected matrix $A\in{\cal
N}(0,\sigma_{A})^{m\times d}$, bias matrix $b\in\mathbb{R}^{m}$, and $\phi$ is
the ReLU activation function. Let $f(x)=\phi(Ax+b)$ denote a single layer
network, then for all neighboring inputs
$x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}$ that differ at most in one
entry, we have

$\displaystyle\Pr\Big{[}\mathrm{GS}_{2}(f)\leq
2(\sqrt{md}+\sqrt{\log(1/\delta)})\Big{]}\geq 1-\delta.$

###### Proof.

Let $k$ denote the index that $x_{1}$ and $x_{2}$ are different.

$\displaystyle\mathrm{GS}_{2}(f)=$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|f(x_{1})-f(x_{2})\|_{2}$
$\displaystyle=$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|\phi(Ax_{1}+b)-\phi(Ax_{2}+b)\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|(Ax_{1}+b)-(Ax_{2}+b)\|_{2}$
$\displaystyle=$
$\displaystyle~{}\sup_{x_{1},x_{2}\in\operatorname{{\mathbb{R}}}^{d}}\|(A(x_{1}-x_{2})\|_{2}$
$\displaystyle=$ $\displaystyle~{}\|A_{*,k}\|_{2}$ $\displaystyle\leq$
$\displaystyle~{}\sigma_{A}\left(2\sqrt{md\log(1/\delta)}+2\log(1/\delta)+md\right)^{1/2}$
$\displaystyle\leq$
$\displaystyle~{}\sigma_{A}\left(2\sqrt{2md\log(1/\delta)}+2\log(1/\delta)+md\right)^{1/2}$
$\displaystyle=$ $\displaystyle~{}\sigma_{A}(\sqrt{md}+\sqrt{2\log
1/\delta}),$

where the fourth step follows that $x_{1}$ and $x_{2}$ differ in the $k$-th
entry, and the fifth step follows Lemma A.6. ∎

##  Appendix E Equivalence between pruning and differential privacy

###  E.1 Main results

Table 1: Summary of two results Statement | $\epsilon_{\mathrm{dp}}$ | Comment | Pruning
---|---|---|---
Theorem E.1 | $\mathrm{GS}_{1}(f)/(\sigma\sigma_{A})\cdot(m/\delta_{\mathrm{dp}})$ | General $x$ | Magnitude
Theorem E.2 | $\mathrm{GS}_{1}(f)/(\sigma\sigma_{A})\cdot\log(m/\delta_{\mathrm{dp}})$ | Nonnegative $x$ | Folded Magnitude

######  Theorem E.1 (Main result I).

For a single layer neural network $f(x)=\phi(Ax+b)$ where fully connected
matrix $A\in{\cal N}(0,\sigma_{A}^{2})^{m\times d}$, vector
$b\in\mathbb{R}^{m}$, and $\phi$ is the ReLU activation function. We assume
all the inputs $x\in\operatorname{{\mathbb{R}}}^{d}$ satisfying that
$\|x\|_{2}=1$. If

$\displaystyle
m=\Omega(\operatorname{poly}(\epsilon_{\mathrm{ap}}^{-1},\log(1/\delta_{\mathrm{ap}}),\log(1/\delta_{\mathrm{dp}}),a/\sigma_{A},\sigma\sigma_{A})),$

then applying magnitude pruning with with truncation threshold $a>0$ on
$A\in\operatorname{{\mathbb{R}}}^{m\times d}$ is an
$(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-approximation to applying
$(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy on $x$,
where
$\epsilon_{\mathrm{dp}}=2\mathrm{GS}_{1}(f)(m/\delta_{\mathrm{dp}})/(\sigma\sigma_{A})$.

######  Theorem E.2 (Main result II).

For a single layer network $f(x)=\phi(Ax+b)$ where fully connected matrix
$A\in\mathcal{N}(0,\sigma_{A}^{2})^{m\times d}$, vector $b\in\mathbb{R}^{m}$,
and $\phi$ is the ReLU activation function. We assume all the inputs
$x\in\operatorname{{\mathbb{R}}}^{d}$ satisfying that $\|x\|_{2}=1$ and
$x\in\operatorname{{\mathbb{R}}}^{d}_{+}$. If

$\displaystyle
m=\Omega(\operatorname{poly}(\epsilon_{\mathrm{ap}}^{-1},\log(1/\delta_{\mathrm{ap}}),\log(1/\delta_{\mathrm{dp}}),a/\sigma_{A},\sigma\sigma_{A})),$

then applying folded magnitude pruning with truncation threshold $a>0$ on
$A\in\operatorname{{\mathbb{R}}}^{m\times d}$ is an
$(\epsilon_{\mathrm{ap}},\delta_{\mathrm{ap}})$-approximation to applying
$(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy on
$x\in\operatorname{{\mathbb{R}}}^{d}$, where
$\epsilon_{\mathrm{dp}}=2\mathrm{GS}_{1}(f)\log(m/\delta_{\mathrm{dp}})/(\sigma\sigma_{A})$.

######  Remark E.3.

Note that $\mathrm{GS}_{1}(f)=\Theta(m\sigma_{A})$.
1) if using folded Gaussian and assume $x\in\operatorname{{\mathbb{R}}}_{\geq
0}$,
$\epsilon_{\mathrm{dp}}=2\mathrm{GS}_{1}(f)\cdot\log(m/\delta_{\mathrm{dp}})/(\sigma\sigma_{A})$,
then we need to pick $\sigma=m$, $\sigma_{A}=\Theta(1/\sigma)$ and
$a=\Theta(\sigma_{A})$ .
2) if using Gaussian,
$\epsilon_{\mathrm{dp}}=2\mathrm{GS}_{1}(f)\cdot(m/\delta_{\mathrm{dp}})/(\sigma\sigma_{A})$,
then we need to pick $\sigma=m^{2}$, $\sigma_{A}=\Theta(1/\sigma)$ and
$a=\Theta(\sigma_{A})$.

###  E.2 Differential privacy

######  Definition E.4 (Differential Privacy, Definition.1 in [DMNS06]).

Let $\mathcal{A}:\mathcal{D}^{n}\rightarrow\mathcal{Y}$ be a randomized
algorithm. Let $D_{1},D_{2}\in\mathcal{D}^{n}$ be two databases that differ in
at most one entry (we call these databases neighbors). Let $\epsilon>0.$
Define $\mathcal{A}$ to be $\epsilon$ -differentially private if for all
neighboring databases $D_{1},D_{2},$ and for all (measurable) subsets
$Y\subset\mathcal{Y},$ we have

$\displaystyle\frac{\Pr\left[\mathcal{A}(D_{1})\in
Y\right]}{\Pr\left[\mathcal{A}\left(D_{2}\right)\in
Y\right]}\leq\exp(\epsilon).$

######  Definition E.5 (Global Sensitivity, Definition 2 in [DMNS06]).

Let $f:{\cal D}^{n}\rightarrow\mathbb{R}^{d}$, define $\mathrm{GS}_{p}(f)$,
the $\ell_{p}$ global sensitivity of $f$, for all neighboring databases
$D_{1},D_{2}$ as

$\displaystyle\mathrm{GS}_{p}(f)=\sup_{D_{1},D_{2}\in{\cal
D}^{n}}\|f(D_{1})-f(D_{2})\|_{p}.$

######  Theorem E.6 (Laplace Mechanism [DMNS06]).

Let $f$ be defined as before and $\epsilon>0$. Define randomized algorithm
$\mathcal{A}$ as

$\displaystyle\mathcal{A}(D)=f(D)+(\mathrm{Lap}(\mathrm{GS}_{1}(f)/\epsilon))^{d},$

where the one-dimensional (zero mean) Laplace distribution $\mathrm{Lap}(b)$
has density $p(x;b)=\frac{1}{2b}\exp(-\frac{|x|}{b})$, and
$\mathrm{Lap}(b)^{d}=(l_{1},\dots,l_{d})\in\operatorname{{\mathbb{R}}}^{d}$
where each $l_{i}$ i.i.d. is sampled from $\mathrm{Lap}(b)$. Then
$\mathcal{A}$ is $\epsilon$-differentially private.

######  Theorem E.7 (Gaussian Mechanism [DR14]).

For $c>2\sqrt{\log(1/\delta)}$, the Gaussian Mechanism with parameter
$\sigma\geq c\cdot\mathrm{GS}_{2}(f)/\epsilon$ is
$(\epsilon,\delta)$-differentially private.

###  E.3 Function approximation

######  Definition E.8 ($(\epsilon,\delta)$-approximation).

For a pair of functions $f(x)$ and $g(x)$, we say $f$ is an
$(\epsilon,\delta)$-approximation of $g$ if for any $x$

$\displaystyle\Pr[\|f(x)-g(x)\|_{2}>\epsilon]\leq\delta.$

###  E.4 Proof of Theorem E.2

###### Proof.

Sketch.

The proof can be splitted into two parts. We use
$\widetilde{A}\in\operatorname{{\mathbb{R}}}^{m\times d}$ to denote the weight
matrix after magnitude pruning, and
$\bar{A}=\widetilde{A}-A\in\operatorname{{\mathbb{R}}}^{m\times d}$. We define
vector $e\in\operatorname{{\mathbb{R}}}^{m}$ as follows

$\displaystyle e=\mathrm{Lap}(1,\sigma)^{m}\circ(\bar{A}x).$

  1. 1.

Let $B(x)=f(x)+e\in\operatorname{{\mathbb{R}}}^{m}$, then $B(x)$ is
$(\epsilon_{\mathrm{dp}},\delta_{\mathrm{dp}})$-differential privacy.

  2. 2.

$\Pr[\frac{1}{\sqrt{m}}\|e-\bar{A}x\|_{2}\geq\epsilon_{\mathrm{ap}}]\leq\delta_{\mathrm{ap}}$,
as long as
$m=\Omega(\operatorname{poly}(\epsilon_{\mathrm{ap}}^{-1},\log(1/\delta_{\mathrm{ap}}),a/\sigma_{A},\sigma\sigma_{A}))$.

Part 1.

Let $y\in\mathbb{R}^{m}$ and $x_{1},x_{2}$ be neighbouring inputs. It is
sufficient to bound the ratio $\frac{p(y-f(x_{1}))}{p(y-f(x_{2}))}$ where
$p(\cdot)$ denotes probability density, because once the densities are
bounded, integrating $p(\cdot)$ yields the requirement for differential
privacy as defined in E.2.

Since $e_{i}\sim\mathrm{Lap}(1,\sigma)\cdot(\bar{A}x)_{i}$, then
$p(t:\sigma)=\frac{1}{2\sigma}\exp(-|t/(\bar{A}x)_{i}-1|/\sigma)$

$\displaystyle\frac{p(y-f(x_{1}))}{p(y-f(x_{2}))}=$
$\displaystyle~{}\frac{\prod_{i=1}^{m}\frac{1}{2\sigma}\exp(-|(y_{i}-f(x_{1})_{i})/(\bar{A}x_{1})_{i}-1|/\sigma)}{\prod_{i=1}^{m}\frac{1}{2\sigma}\exp(-|(y_{i}-f(x_{2})_{i})/(\bar{A}x_{2})_{i}-1|/\sigma)}$
$\displaystyle=$
$\displaystyle~{}\frac{\exp(-\sum_{i=1}^{m}|(y_{i}-f(x_{1})_{i})/(\bar{A}x_{1})_{i}-1|/\sigma)}{\exp(-\sum_{i=1}^{m}|(y_{i}-f(x_{2})_{i})/(\bar{A}x_{2})_{i}-1|/\sigma)}$
$\displaystyle=$
$\displaystyle~{}\exp\Big{(}\frac{1}{\sigma}\sum_{i=1}^{m}\Big{|}\frac{y_{i}-f(x_{1})_{i}}{(\bar{A}x_{1})_{i}}-1\Big{|}-\Big{|}\frac{y_{i}-f(x_{2})_{i}}{(\bar{A}x_{2})_{i}}-1\Big{|}\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}\frac{1}{\sigma}\sum_{i=1}^{m}\Big{|}\frac{y_{i}-f(x_{1})_{i}}{(\bar{A}x_{1})_{i}}-\frac{y_{i}-f(x_{2})_{i}}{(\bar{A}x_{2})_{i}}\Big{|}\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}2\sum_{i=1}^{m}\frac{1}{\sigma\min_{i\in[m]}\\{|(\bar{A}x_{1})_{i}|,|(\bar{A}x_{2})_{i}|\\}}|f(x_{2})_{i}-f(x_{1})_{i}|\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}2\mathrm{GS}_{1}(f)/\sigma\min_{i\in[m]}\\{|(\bar{A}x_{1})_{i}|,|(\bar{A}x_{2})_{i}|\\}\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}2\mathrm{GS}_{1}(f)/\sigma_{A}\sigma(1/6\cdot(a/\sigma_{A})^{2}-1/5\cdot(a/\sigma_{A})^{1.5}\log(m/\delta_{dp}))\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}2(\sigma_{A}m+4\sigma_{A}\sqrt{m}\log^{1.5}(md/\delta))/\sigma_{A}\sigma(1/6\cdot(a/\sigma_{A})^{2}-1/5\cdot(a/\sigma_{A})^{1.5}\log(m/\delta_{dp}))\Big{)}$
$\displaystyle\leq$
$\displaystyle~{}\exp\Big{(}2(m+4\sqrt{m}\log^{1.5}(md/\delta))/\sigma(1/6\cdot(a/\sigma_{A})^{2}-1/5\cdot(a/\sigma_{A})^{1.5}\log(m/\delta_{dp}))\Big{)}$

where the first equality is because the noise is independent for each
coordinate, and the first inequality is triangle inequality. The third
inequality holds because of the definition of $\mathrm{GS}_{1}(f)$, and the
fourth holds because of Lemma B.5. holds with probability
$1-\delta_{\mathrm{dp}}$

According to Lemma D.2,

$\displaystyle\Pr\Big{[}\mathrm{GS}_{1}(f)\leq\sigma_{A}m+4\sigma_{A}\sqrt{m}\log^{1.5}(md/\delta)\Big{]}\geq
1-\delta.$

Part 2.

Let $z_{i}=(e_{i}-\bar{A}x_{i})^{2}$, thus
$z_{i}\sim\mathrm{Lap}^{2}(0,b_{i})$, where $b_{i}=\sigma(\bar{A}x)_{i}$ We
first calculate $\operatorname*{{\mathbb{E}}}[z_{i}^{2}]$

$\displaystyle\operatorname*{{\mathbb{E}}}[z_{i}^{2}]=$
$\displaystyle~{}\int_{-\infty}^{\infty}\frac{1}{2b_{i}}\exp(-|x|/b_{i})x^{4}\mathrm{d}x$
$\displaystyle=$
$\displaystyle~{}\int_{0}^{\infty}\frac{1}{b_{i}}\exp(-x/b_{i})x^{4}\mathrm{d}x$
$\displaystyle=$
$\displaystyle~{}b_{i}^{4}\cdot(-\exp(-x)x^{4}-\int_{0}^{\infty}-4\exp(-x)x^{3}\mathrm{d}x)\bigg{|}_{0}^{\infty}$
$\displaystyle=$
$\displaystyle~{}b_{i}^{4}\cdot(-\exp(-x)x^{4}+4(-\exp(-x)x^{3}-3(\exp(-x)x^{2}-2(-\exp(-x)x-\exp(-x)))))|_{0}^{\infty}$
$\displaystyle=$ $\displaystyle~{}24b_{i}^{4}$ $\displaystyle\leq$
$\displaystyle~{}24\sigma^{4}\cdot(10a(\sqrt{a/\sigma_{A}}+1)\log(m/\delta))^{4},$

where both the third step and the fourth step follow integration by parts. The
fifth step follows by plugging in the limits of integration, and the last step
follows by Lemma B.1.

Next, we want to bound $\max(z_{i})$, since
$z_{i}=e_{i}^{2}\sim\mathrm{Lap}^{2}(0,b_{i})$

$\displaystyle\Pr[z_{i}\geq t^{2}]=$ $\displaystyle\Pr[|e_{i}|\geq t]$ $t>0$
$\displaystyle=$ $\displaystyle 2\cdot\frac{1}{2}\exp(-t/b_{i})$
$\displaystyle=$ $\displaystyle\exp(-t/b_{i}),$

where the second step follows by plugging the cumulative distribution function
of Laplace distribution.

Take $t=b_{i}\log(m/\delta)$, then for each fixed $i\in[m]$, we have
$\Pr[z_{i}\leq\sqrt{b_{i}\log(m/\delta)}]=\delta/m$. Thus, with probability
$1-\delta$, we have for all $i\in[m]$,

$\displaystyle
z_{i}\leq\max_{i\in[m]}\sqrt{b_{i}\log(m/\delta)}\leq\sqrt{a^{3}\sigma/\sigma_{A}\cdot\log(m/\delta)}:=M,$

where the second inequality follows by $(\bar{A}x)_{i}$’s upper bound in Lemma
B.2.

Using Bernstein inequality, we have

$\displaystyle\Pr\left[\Big{|}\sum_{i=1}^{m}(z_{i}-\operatorname*{{\mathbb{E}}}[z_{i}])\Big{|}\geq
t\right]\leq$
$\displaystyle\exp\Big{(}-\frac{t^{2}/2}{\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}[z_{i}^{2}]+Mt/3}\Big{)}$
$\displaystyle\leq$
$\displaystyle\exp\Big{(}-\frac{t^{2}/2}{24m\sigma^{4}\cdot(10a(\sqrt{a/\sigma_{A}}+1)\log(m/\delta))^{4}+a^{3}\sigma/\sigma_{A}\cdot\log(m/\delta)t/3}\Big{)}.$

Since $Mt/3$ is dominated by
$\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}[z_{i}^{2}]$, we choose

$\displaystyle t=m\epsilon^{2},$

then as long as

$\displaystyle
m\geq\epsilon^{-4}\log(1/\delta)\Big{(}48\cdot(10a/\sigma_{A}(\sqrt{a/\sigma_{A}}+1)\log(m/\delta))^{4}\Big{)}(\sigma^{4}\sigma_{A}^{4}+\sigma\sigma_{A}^{2}),$

we have

$\displaystyle\Pr\left[\frac{1}{m}\Big{|}\sum_{i=1}^{m}(z_{i}-\operatorname*{{\mathbb{E}}}[z_{i}])\Big{|}\geq\epsilon^{2}\right]\leq\delta.$

which is

$\displaystyle\Pr\left[\frac{1}{\sqrt{m}}\|e-\bar{A}x\|_{2}\geq\epsilon\right]\leq\delta.$

Note that we need to pick $\sigma=m$, then we need to pick $\sigma_{A}=1/m$. ∎

##  Appendix F Experiment details

###  F.1 Network architecture and hyperparameters

Table 2 provides implementation details of the deep neural networks we use in
experiments. Most of our experiments are conducted on 8 Nvidia Tesla K80 GPUs.
Experiment scripts are written in Python 3.6.

Table 2: Implementation details of network architectures and training schemes. |  MNIST [LCB10] |  CIFAR-10 [Kri09]
---|---|---
$\\#$Epoch | 20 | 200
Network architecture | LeNet-5 [LBBH98] | VGG-19 [SZ15]
Optimizer | SGD (momentum = 0.9) [Qia99] | Adam [KB15]
Initial learning rate | 0.1 | 0.001
Batch size | 64 | 64

###  F.2 Pruning algorithm

Algorithm 2 provides the full version of Algorithm 1. The pruning procedure
decides $a^{(t)}$, the magnitude threshold at time $t$, by the gradual pruning
technique [ZG17], which we have discussed in Section 4 (see Figure 4).

Algorithm 2 Stochastic Gradient Descent with Magnitude-based Pruning, detailed
version of Algorithm 1

1:procedure SGDMagPrune($\\{x_{i},y_{i}\\}_{i\in[n]},a,\eta$)

2: $\triangleright$ Loss function
$\mathcal{L}:\operatorname{{\mathbb{R}}}^{d_{o}}\times\operatorname{{\mathbb{R}}}^{d_{o}}\rightarrow[0,1]$

3: Let $W^{(1)}$ denote a random initialization of neural network’s weights,
and $f(W,x)$ denotes the neural network.

4: Let ${\cal
D}=\\{(x_{1},y_{1}),\cdots,(x_{n},y_{n})\\}\subset\operatorname{{\mathbb{R}}}^{d}\times\operatorname{{\mathbb{R}}}^{d_{o}}$

5: for $t=1\to T_{\text{train}}$ do $\triangleright$ Training stage

6: Sample $(x,y)\sim{\cal D}$ uniformly at random

7: $W^{(t+1)}\leftarrow
W^{(t)}-\eta\cdot\frac{\partial\mathcal{L}(f(W,x),y)}{\partial
W}|_{W=W^{(t)}}$

8: end for

9: for $t=T_{\text{train}}\to T_{\text{train}}+T_{\text{prune}}$ do
$\triangleright$ Pruning stage

10: Sample a data $(x,y)$ from ${\cal D}$ uniformly at random

11: $\widetilde{W}^{(t)}\leftarrow\textsc{ThresholdPrune}(W^{(t)},a^{(t)})$

12:
$W^{(t+1)}=\widetilde{W}^{(t)}-\eta\cdot\frac{\partial\mathcal{L}(f(W,x),y)}{\partial
W}|_{W=\widetilde{W}^{(t)}}$

13: end for

14: $T_{\text{end}}\leftarrow T_{\text{train}}+T_{\text{prune}}$

15:
$\widetilde{W}^{(T_{\text{end}})}\leftarrow\textsc{ThPrune}(W^{(T_{\text{end}})},a^{(T_{\text{end}})})$

16:end procedure

17:procedure ThPrune($W,a$)

18: for $l\in[L]$ do

19: for $i,j$ do

20:
$(\widetilde{W}_{l})_{i,j}\leftarrow\begin{cases}(W_{l})_{i,j},&\text{~{}if~{}}|(W_{l})_{i,j}|>a;\\\
0,&\text{~{}otherwise~{}}.\end{cases}$

21: end for

22: end for

23: return $\widetilde{W}$

24:end procedure

###  F.3 Visualization of inverted images

#### Inversion from different layers.

Figure 9 and Figure 10 visualize the inverted images obtained by running the
attack (see Section 4.2) on $\Phi^{\prime}_{\text{prune}}$ from different
layers with different target sparsities of magnitude pruning. Each column
implies the increasing difficulty of inverting deeper layers. Each row
indicates that with a given layer, running inversion to generate $x$ becomes
harder as the model is pruned with a higher target sparsity. As shown, for
layer ‘Conv5’ in LeNet-5, if we prune the model with sparsity $0.9$, then the
attack fails by producing an almost all-black inversion. Similar phenomenon is
observed when inverting layer ‘Conv5-1’ in VGG-19 with sparsity $0.9$.

Figure 9: Inverted MNIST digits (a digit 2) from different layers with
different sparsity levels. $k$ stands for sparsity. Figure 10: Inverted
CIFAR-10 images (a dog) from different layers with different sparsity levels.
$k$ stands for sparsity.

#### Inversion from the same layer.

Figure 11 and Figure 12 show inverted images obtained by running multiple
inversion attacks on the same layer (we show one sample from each class).
Increasing the target sparsity of pruning makes the inversion attack harder
for all classes.

Figure 11: Inversion from layer ‘Conv5’ of LeNet-5 (MNIST). Each row shows a
sample from each class. Figure 12: Inversion from layer ‘Conv5-1’ of VGG-19
(CIFAR-10). Each row shows a sample from each class.

###  F.4 More on relative privacy leakage of pruning and adding noise

Figure 13 and Figure 14 show the privacy leakage differences between
magnitude-based pruning and adding differentially private noise for the
experiments on MNIST and CIFAR-10 respectively (full version of Figure 6 and
Figure 7). As shown, given the same accuracy requirement, pruning helps
preserve more privacy than adding noise. When accuracy decreases from 0.9 to
0.1, the similarity curves of pruning and adding noise ‘converge’. This is
because when the majority of the network parameters are 0’s, or the hidden-
layer output is dominated by the noise, running the inversion attack will
hardly succeed in obtaining information about the original input.

Note that we did not provide the range for INFE similarity results because
they all have minimum 0 and maximum 1 (even random guessing can make a correct
prediction) and thus not informative.

(a)  (b)  (c)  (d)

Figure 13: Similarity between inversion and original images by applying
pruning and adding noise on different layers (LeNet-5 + MNIST). Shadow
represents value range.

(a)  (b)  (c)  (d)

Figure 14: Similarity between inversion and original images by applying
pruning and adding noise on different layers (VGG-19 + CIFAR-10). Shadow
represents value range.