Privacy-preserving Learning via Deep Net Pruning
Authors: Yangsibo Huang
Xiaoxiao Li
Yushan Su
Sachin Ravi
Zhao Song
Sanjeev Arora
Kai Li
Venue:  (2021)
Keywords: Neural Network Pruning
Differential Privacy

Abstract: Neural network pruning has demonstrated its success in significantly improving the computational efficiency of deep models while only introducing a small reduction on final accuracy. In this paper, we explore an extra bonus of neural network pruning in terms of enhancing privacy. Specifically, we show a novel connection between magnitude-based pruning and adding differentially private noise to intermediate layers under the over-parameterized regime. To the best of our knowledge, this is the first work that bridges pruning with the theory of differential privacy. The paper also presents experimental results by running the model inversion attack on two benchmark datasets, which supports the theoretical finding. 

Under review as a conference paper at ICLR 2021
PRIVACY-PRESERVING LEARNING VIA DEEP NET PRUNING
A Anonymous authors Paper under double-blind review
A ABSTRACT
Neural network pruning has demonstrated its success in significantly im- proving the computational efficiency of deep models while only introducing a small reduction on final accuracy. In this paper, we explore an extra bomus of neural network pruning in terms of enhancing privacy. Specifi- cally, we show a novel connoction between magnitude-basood pruning and adding differentially private noise to intermediate layers under the over- parameterized regime. To the best our kuowledge, this the first work that bridges pruning with the theory of differential privacy. The paper also presents experimental results by running the model inversion attack on two benchmark datasets, which supports the theoretical finding.
INTRODUCTION
Data privacy has become one of the top concerns in the application of deep neural networks, since there has been an increasing demand to train deep models on private data sets. For example, hospitals are now training their automated diagnosis systems on private patients' data Litjens et al. (2016); Lakhani & Sundaram (2017); De Fauw et al. (2018); and adver- tisement providers are collecting users' online trajectories recommendation algorithm Covington et al. (2016); Ying et al. (2018). These private data, however, are usually subject to the regulations such as California Consumer Privacy Act (CCPA) Legislature (2018), Health Insurance Portability and Accountability Act (HIPAA) Act. (1996), and General Data Protection Regulation (GDPR) of European Union.
optimize their learning- based
Differential privacy (DP) Dwork et al. (2006b); Dwork (2009); Dwork & Roth (2014) has emerged, during the past few years, as a strong standard to provide theoretical privacy guarantees for algorithms privacy is to add controlled noise to the output of a deterministic function, such that the output cannot be used to infer much about any single individual in the database. Recent years have seen an increasing number of applications that adapt differential privacy mecha- nisms to address privacy concerns in deep learning Shokri & Shmatikov (2015); Abadi et al. (2016); Phan et al. (2016); McMahan et al. (2018).
aggregate databases. The core idea of achieving differential
Neural network pruning (or pruning in short), a seemingly orthogonal field to privacy, has also been the subject of a great amount of work in recent years. Pruming aims to reduce the number of model parameters, such that the compressed model can be applied even under the memory constraints of the edge-devices. Various pruning techniques have succeeded in significantly compressing models with little no loss of accuracy Han al. (2015; 2016a); Li et al. (2016): Ding el. al. (2018); Exci et al. (2019); Tanaka et al. (2020). However, the majority of existing literature only demonstrate the benefits of pruning in terms of energy saving and inference speedup, while in this work, we investigate another interesting bonus of pruning - preserving data privacy.
Our investigation is mainly inspired by the observation that neural network pruning makes the inversion from hidden- layers harder, as the percentage of remained weight decreases (see Figure 1). Motivated by this empirical observation, we build under the verrppaamtterized regime of deep learning theory, and show an interesting connection between neural network pruning and adding differentially private noise to intermediate layers. We believe this con-

---

Under review as a conference paper at ICLR 2021
0%
0%
41.0%
26.2%
8%%
10.7% 86.2
4.5%
Onginnl
93.0
Figure 1: Visualization inverted CIFAR-10 Krizhevsky (2009) inputs from the third bottleneck of ResNet-18 He et. al. (2016) using the inversion algorithm in Section 5.2. We prune the network with different k's, the fraction remained weights. Inverted images from networks with fewer weights visually more different. from the original image.
nection may have important practical implications since the pruned model only incurs small accuracy loss, and we leave that as future work.
We list our contributions as follow:
We explore the benefits of pruned neural networks terms of preserving data privacy, To the best of our knowledge, this is the first step towards drawing thcoretical connection between neural network pruning and differential privacy.
To build the connection between pruming and adding differentially private noise to intermediate layers, generalize the famous anti-concentration inequality due to Carbery and Wright Carbery & Wright (2001). This generalization might find more applications in the theoretical analysis of neural network pruning in the future.
We provide empirical results in support of our theoretical finding. Specifically, we demonstrate on two benchmark datasets that pruned neural networks are more secure in the sense that running the model inversion attack becomes harder.
Roadmap. The rest of this paper is organized as follow. Section 2 covers existing literature in different privacy, neural network pruning, and over-parameterized deep learning theory, Section 3 provides thcoretical preliminaries and Scction 4 presents our main thcoretical result. Section shows empirical results on MNIST and CIFAR-10 benchmarks that are in support of our theoretical findings. We conclude this work in Section 6.
2 RELATED WORK
Neural network pruning 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 Sainath et al. (2013); Lebedev et al. (2015), network pruning LeCun et al. (1990); Srinivas & Babu (2015); Han et al. (2016b); Li et al. (2017), and knowledge distillation Hinton et al. (2015); Chen et al. (2017). Among them, neural network pruning has been widely adopted because it is able to reduce model sizes by up to one order magnitude without significant accuracy loss. The idea of network pruning dates back to the Optimal Brain Damage in 1990s LeCun et al. (1990). Recently, it has been shown that removing the weights with low magnitude can also achieve a highly compressed model Han et al. (2016b), which is referred to as imagnitude-basee pruming'.
Differential privacy The concept of e-differential privacy was originally introduced by Dwork, McSherry, Nissim and Smith Dwork et. al. (2006b). Later, it was generalized to relaxation of (c. 8)ddifferettial privacy Dwork et al. (2006a); Dwork (2009); Dwork & Roth (2014). Differential privacy has been successfully applied to many problems. For more detailed surveys of the applications of differential privacy, we refer the readers to Dwork (2008; 2011). Applying differential privacy techniques in deep learning is an interesting but non-trivial task. Previous rescarch have customized diffcrential privacy for different learning tasks and settings Shokri & Shmatikov (2015); Abadi et al. (2016): Phan et al. (2016).
Although there are existing studies about applying differential privacy in neural network, but there is little exploration presenting differential privacy using prune network yet.
2

---

Under review as a conference paper at ICLR 2021
To the best of our knowledge, this paper is the first work that shows connection between differential privacy and pruned neural network.
pver-parameterized deep learning theory Recently, there is super long line of work focusing showing the convergence of deep ncural network training under over- parameterization regime Li & Liang (2018); Du al. (2019); Allen-Zhu et al. (2019b;c;a;; Arora et al. (2019a;b); Song & Yang (2019); Oymak & Soltanolkotabi (2020); Brand et al. (2020). The theory suggested as long as the neural network sufficiently wide, i... m 2 pnly(n, d, 1/6, L) then rumning (stochastic) gradient descent algorithm is able to find the global minimum, where is the number of imput data points, is the dimension of data, 5 is the minimum l distances between all pairs and L. is the number of layers in neural network.
However, unlike the above classical deep lcarning convergence theory, this work explored the over-parameterized theory in very different perspective, e.g. privacy. Our result not an oplimization result which indicating neural nelwork can learn a set of input data points in certain sense, however our result is suggesting neural network can be private in the differential privacy sense.
3 BACKGROUNDS
Notations. For positive integer n, we use [n]] to denote set {1,2, ... n.. For vector E R", we use ||ж|| to denote Ex [x;]. ||a]|2 to denote (Ei x;) || to denote maxie[n] |z;]- We use (N,, to denote random Gaussian distribution. For a matrix A,
we use ||| to denote its spectral norm.
This section presents some backgrounds before theoretically establishing the equivalence be- tween magnitude- based pruning and adding differentially private noise in Scction Section 3.1 revisits the notion of (Cdp: dap diifferenta privacy. Section 3.2 describes the magnitude pruning algorithm.
3.1 DIFFERENTIAL PRIVACY
The classical definition of differential privacy is shown follow:
Definition 3.1 (Crap= dap) -differennti privacy Dwork et al. (2006a)). For randomized function h(x), we say fu()) is (cap: -difffrrrett privacy if for all C Range(h) and for all x, y with Ix ylli 1 we have
Pr(M(x) E E exp(ea)))) Pr(M(v) E ES] + dap-
h
Definition 3.1 says that, if there are two otherwise identical records and y, one with privacy-sensitive information in it, and one without it, and we normalize them such that | - vll1 < 1. Differential Privacy ensures that the probability that a statistical query will produce given result is nearly the same whether it's conducted on the first second record. Parameters (eap: dap) are called the privacy budget, and smaller edp and dap provide a better differential privacy protection. One can think of a setting where both parameters are 0, then the chance of telling whether query result is from from 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 1(x). In order to analyze it, we need the following definition: Definition 3.2 (Global Sensitivity Dwork et al. (2006b)). Let _ Rd, define GS,(f), the Ep global sensitivity of f, for all x, with ||æ - - <
GS,(f) sup [f(x)) - f())lpp
R.EER"
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
3

---

Under review as a conference paper at ICLR 2021
well-known mechanisms, e.g., Laplace or Gaussian Dwork & Roth (2014), and the amount of noise (the standard deviation of the noise distribution) is proportional to the sensitivity, but inversely proportional to the privacy budget Cdp. That is to say, for given function with fixed global sensitivity, a larger amount noise is required to guarantee a better differential privacy (one with smaller budget 6dp)-
3.2 MAGNITUDE-BASED PRUNING
Magnitude- based pruning Han et al. (2016a) compresses a neural network by removing connections with smallest-magnitude weights (usually determined by using a. threshold, say a). The pruning procedure starts with a trained (dense) network f(W1,... WL), where T. is its depth, and W,, E [I. is the weight of its i-th layer. For each layer Wi, it sets the weights with magnitudes smaller than a to zero:
(Wi)as + (Wi)s 1 V
We then run model update after the pruning step.
MAIN RESULT
We start by formulating the connection between pruning and adding differentially private noise. We define the following notions to describe the closeness between randomized function and a given function, which can be either randomized or deterministic.
Definition 4.1
([Eap) (cp)-cc.s)). For pair of functions R² - Rd and h : RR + R".
and a fixed input I, we say g(x) is (c,8)-close h(z) if and only if.
Pr 8.
11(xx) - h(x))22 se m
(<ap: dclosensss basically requires that, E distance between two functions' output with a given input is small enough (llf - glle == ( If(x) (dx)).)) When applying the definition to deep neural network, we view m as the width of deep neural network (e.g. the number of neurons).
Let o(t) denote the activation function. In this work, we focus on ReLU case where @(t) = max(t, 0}. Without loss of generality, techniques can be generalized to other activation functions. We present our main theoretical result in Theorem 4.2. The main message our thcorem is that, as long the neural network is sufficiently wide, pruning neural network has a similar effect to adding differentially private noisc
Theorem 4.2 (Main result, informal Theorem E.1). Let O = O(eap fully connected newral network (each layer can be viewed as f(x) o(Az + b)), where | 1 and x E TR Applying magritude-based pruning the weight A E Rudd (where each A.,; ~ NOO 2 gives us Ā E mmxdd If (ollllpplppeeeeeoolll (1/Eap. log(L16mpp) log (og((/AA)))) then there exists a function h(x) satisfying two properlies:
For
1. h(x)) is (Cdp- diffferenttt privacy on input x;
2. h(x) is (Caps 8ap) -coose to g(x) = o(Ax b).
In the above theorem, we denote as the input data dimension. o is the activation function, e.g., ((2) 0). In this work, we focus one hidden layer neural network."
We would like to emphasize that one hidden layer not just a toy example, but a natural and standard situation to study theory, see Zhong et al. (2017b;a); Li & Yuan (2017); Li & Liang (2018); Du et al. (2019); Song & Yang (2019); Brand et al, (2020); Bubeck et al. (2020) for example. Usually, if proof holds for one-hidden layer, generalizing it to multiple layers is straightforward Zhu al. (2019h;c)

---

Under review as a conference paper at ICLR 2021
Regarding the two properties of h(z), property 1 requires h(x) to provide (cap: ddp)- differential privacy, and property 2 requires that h(x) similar to magnitude- based pruning with the predefined (Caps Sap) -close notation.
Proof Sketch Let A E Rm denole the weight matrix after magnit based pruning, and A A AE gmxd We define a noise vector e IR" as the follow:
e = = a (Az).
The main proof can be split into two parts in correspondence to property and 2 respec- lively: Claim 4.3 and Claim 4.4.
Claim 4.3. Let h(x)== f()) te " we can show that h(x) is
(Edp: dap) differential privacy.
Claim 4.4. For sufficiently large m, have
Pr
|le Azl1e 2 Cap) S 6ap-
Proof sketch of Claim 4.3 To prove Claim 4.3, we anchor from the definition of differ- ential privacy, Recall Def. 3.1, (edp: ddiffferrrn privacy requires that for any inputs æ and with | y/l $ 1,
Pr(h(x) E E] exp(<ap) Pr(h(y)
dap-
To be more specific, we use the fact that the noise e is sampled from the Laplace distribution, and try bound the ratio
pa (h(x)) - S) (h(h(y) e S)
where p(-) denotes the probability density function. 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.
Recall the well-known anti-concentrattion result by Carbery & Wright (2001).
Lemma 4.5 (Carbery and Wright Carbery & Wright (2001)). Let p : E R denote degree-k polynomial with d variables. There is universal constant C. > 0 such that
Pr (0,
[p(x)] s
& Varlp(() C-
Another contribution in this work is that we extend the auti-concentration result Carbery & Wright (2001) to a more general setting, which has not been explored in litcrature. We state our generalization as follows?
Lemma 4.6 (An variation of Carbery & Wright (2001), Anti-concentration of sum of trun- cated Gaussians). Let T', In n i.i.d. zero-mean Gaussian random variables N0, 1). Let p R + R denote degree-1 polynomial defined as
p(E,, ,...".,,))==
Σ 04.4
i=l
Let f denote a truncation function where f(x) = x. if |x] S a, and f(x) = if |x| > a. Then
we have
Pr 20.
[I(f(=))] 0.1) 8 ||al| 2 C.
Once the densitics are bounded, intograting p(-) yields the requirement of differential privacy, thus complete the proof part 1.
for details of the proof, we refer the readers Appendix
5

---

Under review as a conference paper at ICLR 2021
Proof sketch of Claim 4.4 To prove Claim 4.4, we firstly define =, (Ar); Then
we apply the concentration theorem (see Appendix B) to show that for any | = 1 and x E R
Pr
Σ
(2
E[2))|
Sup Sap.
which completes the proof of Claim 4.4.
In certain, the proof is mainly sophisticated combination of the following concentration inqqualities
Lemm B.1 shows the concentration the l norm of a random truncated Gaussian vector
Lemma B.2 shows the concentration of matrix vector multiplication.
Lemm B.3 bounds the inner product between random Guassian vector and a fixed vector
Lemma B.4 bounds inner product between two random Guassian vectors
Lemma B.5 shows the concentration of folded Gaussian random vectors.
EXPERIMENTS
This section presents experimental results in support of our theoretical finding in Section by answering this question: does the pruned model preserve better privacy than the dense one? We describe experimental setups in Section 5.1 and the evaluation for privacy in Section 5.2. We summarize results in Section 5.3.
EXPERIMENTAL SETUP
Datasets and model architectures. We have conducted image classification experi- ments on MNIST LeCun et al. (2010) and CIFAR-10 Krizhevsky (2009) benchmarks.
For network architectures, we have used LeNet-5 LeCun et al. (1998) for MNIST, and ResNet-115 18 He et al. (2016) for CIFAR-10, with PyTorch Paszke et al. (2019) as the experi- ment platform. We have used SGD Qian (1999) with lcarning rate 0.05 and momentum 0.9 for both models, and train LeNet-5 for 20 epochs and ResNet-18 for 150 epochs. All models are trained 8 NVIDIA GeForce RTX 2080 Ti GPUs with batch size 256.
Pruning algorithm. We have employed the iterative pruning technique, which repeatedly prunes and retrains the network over rounds: in each round, we prune p fraction of the weights that survive the previous round and retrain for t epochs. We use to denote the fraction of weights remained in the final sparse model, thus have k = (1 - -p" In our experiments, we set = 20% and t = 5, and vary n E [15] to get pruned networks with different k's.
5.2
TEST OF PRIVACY LEAKAGE AS A MODEL INVERSION ATTACK
We have used the attack-based evaluation to investigate whether pruning could preserve more privacy (i.e., suffer less "privacy leakage" under the attack). We have adopted the model inversion attack Mahendran Vedaldi (2015) to show the privacy leakage of a given l-layer neural network f(W,,- Wi), where W, E [[] is the weight of its i-th layer.
Let us conceptualize the mapping from the f's input to the output its i-th intermediate as a representation function & R -, Rm The model inversion attack captures the potential privacy leakage of & when applied some input x::
Given the representation (2x,, and the weights the public mapping 4 the attacker's 's goal is to find the preimage of ((x), namely
arg min (()(z), (x))) XR(=)
=CR

---

Under review as a conference paper at ICLR 2021
k(%)
100.0
80.0
64.0
51.2
41.0
32.8
26.2
21.0
MNIST
99.0
98.9
99.0
99.0
99.0
99.0
99.0
98.9
CIFAR-10
94.1
93.8
93.6
93.4
93.0
92.5
91.9
90.7
k(%)
16.8
13.4
10.7
8.6
6.9
5.5
4.5
3.5
MNIST
98.8
98.8
98.7
98.4
98.1
98.0
97.5
97.5
CIFAR-10
89.8
88.2
86.3
83.3
75.9
72.4
61.9
10.0
Table 1: Test accuracy (%) achieved on MNIST and CIFAR-10 when pruning a dense network. & is the fraction of weights remained.
k=100 0%
64 .% 39.0
41.0%
28 2% 99.0
8588 98.6
10.7% 98.7
6.9 38.1
4,9% 97.5
Original
Acce88 D
38.0
Convl
9
9
9
9
9
9
9
9
q
Comv2
9
FC1
9
S
FC2
9
FC3
9
(a) MNIST
k=100.0K
0%
1..0%
28.2%
16.8%
10.7%
8.9%
4.5%
Com22.1
Comv2
Comá-11
Convé-1 1 Comv
(b) CIFAR-10
Figure 2: Recovered MNIST digits (a) and CIFAR-10 samples (b) by running the model inversion attack in Section 5.2 on LeNet-5 and ResNet-18 18 models trained with pruning. We test different layers (different rows) and fractions of remained weights (k, different columns). The naming of layers is explained in Scction 3.3.
where the loss function L is defined as L(a, d') = |a - a'113. > is the regularization parameter, and the regularization function R. in our case is the total variation of 2D signal: R(a)) = Eny((att a² + (ai.tt1 - 1///)
5.3
RESULTS
We have evaluated the model inversion attack different representation function 4's by

---

Under review as a conference paper at ICLR 2021
1. Pruning the neural network with different k's, the fraction of remained weights, where l = (1 - 20%)), n E [15]
2. Selecting different intermediate layers to invert. Specifically, for LeNet-5, we run the attack on all 5 layers, namely ('Conv1', 'Conv2', 'FC1', 'FC2', 'FC3"). For ResNet- 18, we pick 5 layers {*Conv2-1', 'Couv2-2', 'Conv3-1', 'Conv3-2', 'Couv4-1',, where 'Convi-j" stands for the j-th convolutional group of the i-th convolutional block.
Now we report that our experimental results strongly suggest that magnitude- based pruming preserves better privacy (suffer less leakage) than its dense counterpart.
Accuracy of network pruning. Table 1 shows the accuracy results of MNIST and CIFAR-10 tasks for the network pruning approach whose networks have different k percent- ages of remaining weights. The task on MNIST achieves the same level of accuracy network model without pruming when k, the fraction of remained weights 2 10%. Its accu- racy gradually decreases as more weights get removed. The test with CIFAR-10 maintains the same accuracy as or better than the model without pruning when k 2 40%, and then gradually decreases as decresos.
the
Note that the model accuracy achieved with the pruning algorithm in our experiments may be lower than that of the SOTA model with the same sparsity. However, for answering the question if network pruning preserves privacy, our experiments can be viewed as conservative results.
Sparser networks suffer less privacy leakage. Figure 2 visualized the inverted samples under different choices of layers and fractions of remained weights. Each column of Figure suggests the increasing difficulty of inverting deeper layers.
A more important observation is that, for all layers, we consistently observe that the privacy leakage gradually decreases as k increases: for deep layers (e.g. 'FC2' for LeNet-5 and 'Conv4-1' for ResNet-18), though the inverted image from the dense model (i.e. may look quite identical to the original image without pruning, it is no longer true when k S 90%). This agrees with Theorem 4.2, which suggests that under the aver-aarameteried regime, pruning yields similar effect to adding differentially private noise and thus preserves better privacy.
100%)
6 CONCLUSIONS
This paper has presented theoretical result to show that, if fully-comeected layer of a neural network is wide enough, there is a connection between magnitude-based noural network pruning and adding differentially private noise to the model's intermediate outputs. Empirical results on two benchmark datasets support our theoretical findings.
These results have strong practical implications for two reasons. First, since neural network pruning has the property that the fraction removed weights 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 distributed or federated learning system to use a particular layer to communicate among multiple sites.
Several questions remain open. First, Theorem 4.2 is only for single-layer fully connected network, and would be interesting if one can extend 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. Finally, in order to use network pruning as a mechanism to preserve privacy in a practical distributed or federated learning system, one needs 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.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, 1lya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM STGSAC Conference on Computer and Communications Security, pp. 308- 318, 2016.
Accountability Act. Health insurance portability and accountability act of 1996. Public low, 104:191, 1996.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overpa- rameterized neural networks, going beyond two layers. In Advonces in neural information processing systems (NeurIPS), pp. 6155-6166, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameetrriztioo.. In ICML. attps://arii org/ http/dff/1ae 03962. pdf, 2019b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In NewrIPS.
org. /df 111001110011 12065 pdf, 2019c.
Richard Aoun, Marwa Banna, and Pierre Youssef. Matrix poincare inequalities and concen- 13797. pdf, 2019.
tration. In orXi preprint. httpp://awxxv..r.////so.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. F'in-ggriine analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning (ICML), pp. 322-332. https: //axxiv. org/pdf
1tt.f//191....000 08584, .df, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitoly wide neural net. arXiv preprint 19Xi::1004.19900 2019b.
Lavrentin M Arutyunyan and Egor D Kosov. Deviation of polynomials from their expecta- tions and isoperimetry. Bernoulli, 24(3):2043- 2063, 2018.
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.
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks in near-linear time. arXiv preprint Xiw:2006611644, 2020.
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks. arXiv preprint ar Xiv: 02855, 2020.
Authony Carbery and James Wright. Distributional and L norm inequalities for polyno- mials over convex bodies in R". Mathematical research letters, 8(3):233 248, 2001.
Guobin Chen, Wongun Choi, Xiang Yu, Tony Han, and Manmohan Chandraker. Learning efficient object detection models with knowledge distillation. In NIPS, 2017.
Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of obscrvations. The Annals of Mathematical Statistics, pp. 493-507, 1952.
Kevin P Costello, Terence Tao, and Van Vu. Random symmetric matrices are almost surely nonsingular. Duke Mathematical Journal, 135(2):395-413 2006.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recom- mendations. In Proceedings of the 10th ACM conference on recommender systems, 2016.
Jeffrey De Fauw, Joseph R Ledsam, Bernardino Romera-Paredes, Stanislav Nikolov, Nenad Tomasev, Sam Blackwell, Harry Askham, Xavier Glorot, Brendan O' O'Donoghue, Daniel Visentin, et al. Clinically applicable deep learning for diagnosis and referral retinal disease. Nature medicine, 2449):132,, 2018.

---

Under review as a conference paper at ICLR 2021
Xiaohan Ding, Guiguang Ding, Jungong Han, and Sheng Tang. Auto-balanced filter pruning for efficient convolutional neural networks. In AAAI, volume 3, pp. 7, 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes per-parameteriiee neural networks. In ICLR. attps://arziiv.org/dff. 02054. pdf, 2019.
Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pp. 1 19. Springer, 2008.
Cynthia Dwork. The differential privacy frontier. In Theory of Cryptography Conference, pp. 496-502. Springer, 2009.
Cynthia Dwork. A firm foundation for private data analysis. Communications of the ACM, 54(1):86-99 95, 2011.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foun- dations and Trends in Theoretical Computer Science, 9(3 (18-4)211-4411 407, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Πly Mironov, and Moni Naor. Our dala, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryplograhhic Techniques, pp. 486 503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryplography conference, pp. 265 284. Springer, 2006b.
Paul Erdös. On a lemma of littlewood and offord. Bulletin of the American Mathematical Sociely, 51(12)8898 902, 1945.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. arXi preprint 191.v:191..1119. 2019.
Ankit Garg, Yin-Tar Lee, Zhao Song, and Nikhil Srivastava. A matrix expander chernoff bound. In STOC. https://arxiv org//dtttt 17704. 03864, 2018
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neu- ral networks with pruning, trained quantization and huffman coding. arXio preprint orXio:1510.0011 2015.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A Horowitz, and William J Dally. Eie: efficient inference engine on compressed deep neural network. In ISCA, 2016a.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffinan coding. In ICLR. https:// arxiv org/1510. 00149.01..... pdf, 2016b.
Kaiming Hc, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. In Xi preprint. https://arxie wwtp://.rgpp/////// /1503////155//...// 02531. 1ff, 2015.
Wassily Hoeffding, Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 30, 1963.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
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: setps://arxix: org/pdf /181f 11810.08458 2018.
10

---

Under review as a conference paper at ICLR 2021
Paras Lakhani and Baskaran Sundaram. Deep learning at chest radiography: automated classification pulmonary tuberculosis by using convolutional neural networks. Radiology, 284(2):574-588) 2017.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pp. 1302-1338, 2000.
Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oscledets, and Victor Lempitsky. Speeding-up convolutional neural networks using fine-tuned cp-decomposition. In ICLR. https://arxivv wtg/pdf////ooooooooogotogpep /112/.11..222 6553, pdf, 2015.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In NIPS, 1990.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-basse learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 22224, 1998.
Yann LeCun, Corinna Corles, and CJ Burges. Mnist. handwritten digit database. In ATT
Labs, volume 2. http: //yann. lerraannneeen...mm com/ exdd/mnist, 2010.
https:://aa.ca...... ca. go.g California State Legislature. California consumer privacy act (cepa). https://oag.c...
privacy/ccpa, 2018
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint arXiv:1605 08710, 2016.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters wwt/oo/gg/////o/////oo/o/////// http//dff/.1....//////////// 08710008000000 pff, 2017.
for efficient convnets. In ICLR.
Yuanzhi Li and Yingyu Liang- Learning overparameterized neural networks via stochas- tic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157 8166, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU activation. In Advances in neural informalion processing systems (NIPS), pp. 597-607. https://arxiv arg/pdf/1706/ 09886, pdf, 2017.
Geert Litjens, Clara I Sánchez, Nadya Timofeeva, Meyke Hermsen, Iris Naglegaal, Iringo Kovacs, Christina Hulsbergen-Van Van De Kaa, Peter Bult, Bram Van Ginneken, and Jeroen Van Der Laak. Deep learning tool for increased accuracy and efficiency of histopatho- logical diagnosis. Scientific reports, 6:26286, 2016.
John Edensor Littleoood and Albert Cyril Offord. On the number of real roots of a random algebraic equation (iii). Rec. Math. [Mal. Sbornikk N.S., 12(3):277 286, 1943.
Aravindh Mahendran and Andrea Vedaldi. Understanding deep image representations by inverting them. In CVPR. https / /atxiv.ivvvv/////////e/////aa wwt/p/o/g//////// /aate.//11...0 0035 pdf, 2015.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representa- tions, 2018
Raghu Meka, Oanh Nguyen, and Van Vu. Auti-connenntaaiion for polynomials of independent random variables. In Theory Of Computing. https: org/
ort/oof/////////oooo//ooooo/ pdfpp/ff/f// /107 .08299, 2017.
Assaf Naor, Shravas Rao, and Oded Regev. Concentration of markov chains with bounded moments. In ar preprint. https: http//axxx...../pp./ 07260 pdf, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization:: global convergence guarantees for training shallow neural networks. In IEFF Journal on Selected Areas in Information. Theory. https: //axxiv...vvv///////// wttg/ddf/190 04674. .df, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imper- ative style, nigh-performance deep learning library. In NewrIPS, pp. 5024-8035, 8035, 2019.
11

---

Under review as a conference paper at ICLR 2021
NaatHai Phan, Yue Wang, Xintao Wu, and Defing Dou. Differential privacy preservation for deep auto-encoders: an application of human behavior prediction. In AAAI, 2016.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural net- works, 12(1):145 151, 1999.
Alexander Razborov and Emanuele Viola. Real advantage. ACM Trans. Comput. Theory, 5(4), November 2013.
Tara N Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhad- ran. Low-rank matrix factorization for deep neural network training with high- dimensional output targets. In IEFE international conference acoustics, speech and signal process- ing, pp. 6655-6659, 2013.
Reza Shokri and Vitaly Shmatikov.
deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1310- 132011 ACM, 2015.
Zhao Song and Xin Yang. Quadratic suffices for over-paramelrriation via matrix chernoff' 03593.pdf. 2019.
bound. In Xix preprind. httpa///aawwww..ppp/////////
Zhao Song, Xi Yang, and Ruizhe Zhang. Joint anti-concentration for random gaussian polynomials. In Monuscript, 2020.
Suraj Srinivas and R. Venkatesh Babu. Data-free parameter pruning for deep neural net- works. In BMVC. httpa////aaxx///////////0 06149.664999.99 .6,49.pdf, 2015.
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruming neu- ral networks without any data by iteratively conserving synaptic flow. arXiv preprint ar Xix: 05467, 2020.
Joel A Tropp. An introduction matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
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.
Kai Zhong, Zhao Song, and Inderjit S Dhillon. Learning non-overlapping convolutional neural networks with multiple kernels. arXiv preprinl arXiw:1711.034440 2017a.
Kai Zhong, Zhao Song, Pratock Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hirden-layer neural networks. In ICML. https://arxiv. org/pdf/ 0716.. pdf, 2017b.
Michacl Zhu and Suyog Gupta. To prune, or not to prunc: exploring the efficacy of pruning for model compression. In ICLR (Workshop). 2017.
12


Reviews:
[{"review_id": "yXux4U8IKki", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper seeks to protect privacy of the dataset involved in learning process. Specifically, it tries to establish some connection between privacy obtained from pruning neural networks and differential privacy. To do this, it generalises the famous anti-concentration inequality by Carbery and Wright. It also provides empirical results to support its empirical findings.\n\nStrengths: Strong mathematical foundation behind the claims. They manage to establish some connection with DP.\n\nWeaknesses: Has the following drawbacks.\n-They seem to overestimate the power of their results.\n-The connection that they establish doesn't provide a path to actually achieving DP. The connection is an L2 norm connection with the output of a possible DP algorithm. That doesn't say much about privacy.\n-The only attack they consider is model inversion attack. What other kinds of attacks is it robust to?\n-On page 8, they claim that for CIFAR-10, the accuracy gradually declines after k=40%. That is just not true. It drops by 30%. So, getting actual privacy is very difficult if accuracy is a desired consequence, too.\n-Their methods only work on 1-layered NN. Do they generalise? Or any intuition to why they would generalise?\n\nI feel that the negatives outweigh the positives here.", "extra_scores": {}, "extra_text": {}}, {"review_id": "qU7BfwWtQfa", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary \n\nThe paper claims to exhibit a connection between differential privacy and neural network pruning. The main result is that, for a single layer network with Gaussian weights that depend on the privacy parameters, there exists a differentially private function which approximates the pruned network in $L_2$ distance. This is proved by bounding the sensitivity of the network and adding Laplace noise so that the resulting function satisfies differential privacy and approximates the function defined by the pruned network. According to the authors, these results mean that “ network pruning can be an effective method to achieve differential privacy”\n\n### Evaluation\n\nThere are multiple serious conceptual issues with this work. Let me list them in order of severity:\n\n* The fact that a differentially private function h approximates another function g has no implications about the extent to which g preserves privacy. Differential (or any) privacy is not a notion that’s in any sense continuous with $L_2$ distance. For example, suppose we have numerical data consisting of n reals $x_1, \\ldots, x_n$ in $[0,1]$, and $g = (x_1 + \\ldots + x_n)/n$ is their average, and let $h(x)= g(x) + e$ where e is $\\mathrm{Lap}(0,1/\\varepsilon)$ noise. Then g and h are very close and, in the authors’ terminology, the average “has a similar effect to adding differentially private noise”. Nevertheless, averages are far from being privacy preserving: for example the exact value can be encoded in the lower order bits of the $x_i$ in a way that is preserved by the average, so that the entire data set $x_1, \\ldots, x_n$ can be read off from $g(x)$. Note that this example is *exactly* analogous to what the authors prove, just simpler. \n\nMore concisely, the authors have gotten things backwards: finding a differentially private approximation h to a function g does not mean that g is in any way privacy preserving. \n\n* The privacy model used here is peculiar, and it is not clear to me when it makes sense to use it. The authors show how to release a *single prediction* of the network on a *single data point* with differential privacy, where differential privacy is defined with respect to two data points being neighboring if they differ in a single coordinate (in the appendix) or have $\\ell_1$ norm at most 1 (in the body of the paper). So what is the data of an individual here? For example, if $x$ is an image, are we preserving “pixel privacy”? And why is it interesting to release a single prediction rather than an entire network, as is more common?\n\n* The theorem is proved for random Gaussian weights, and the variance of the weights depend linearly on the privacy parameters. In particular, the variance of the weights depends linearly on $\\delta_{dp}$, which is a parameter that’s often assumed to be cryptographically small. In that case, it looks like the network’s output would contain essentially no signal about its input.\n\n* The paper is badly written. There are problems with phrasing (e.g. algorithms are called “differential privacy” rather than “differentially private”), with undefined notation (what is $\\circ$ in the proof sketch of the main theorem?), and with inconsistent definitions (neighborhood definitions are different in the body and the appendix), and unexplained assumptions and model choices (the Gaussian weights, the semantics of the privacy model).", "extra_scores": {}, "extra_text": {}}, {"review_id": "eBW7rUs-I-", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overview: This paper aims to establish a theoretical connection between differential privacy and magnitude based pruning. The authors show theoretically that outputs of pruned single layer neural networks have some similarity to outputs of the same network with differential privacy added. The paper then empirically demonstrates that model inversion attacks are harder against magnitude pruned neural networks.\n\nReason for score: \nI tend to vote reject. Overall, I think this paper contains several correct and interesting pieces that are put together the wrong way. The empirical observation that pruned networks are harder to invert is very supported by experiments in this paper; the main theorem 4.2 is (I assume) correctly derived with some new theoretical tools that may be of independent interest. Yet, I am unconvinced about the relation between pruning and differential privacy claimed by this paper due to the concerns that listed below. \n\nPros:\nPaper is well written and mostly concise in presentation. The experiments are convincing in supporting the claim that pruned networks are harder to invert. I have glanced through the supplementary material and the derivations seem correct.\n\nCons:\n1. Statement about the definition of differential privacy is inconsistent: In definition 3.1, the authors define differential privacy with respect to pairs of real vectors x and y with l1 norm less than 1. This definition is incorrect as differential privacy is defined on pairs of databases (set/multiset of vectors or strings), and the neighbouring relationship between pairs of databases should be those which differ by at most one entry. In contrast, the authors appear to use a different definition in appendix D, where x and y now differ by “one entry”, which I presume to mean in one dimension of the vector. This would be analogous to protecting the value of one pixel in a database of a single image, which is a rather useless notion of privacy.\n\n2. Assumption on weights: the main contribution of this paper, which is theorem 4.2, assumes that the network weights are iid drawn from a normal distribution. This assumption seems far fetched since trained neural network weights tend to be strongly correlated rather than independent. I am also not aware of any empirical work who states that magnitudes of trained neural network weights are well approximated by a gaussian. Hence, I am not convinced that the result drawn in theorem 4.2 has real applicability to understanding the relation between DP and pruning (if any such relation exists at all).\n\n3. Conclusion drawn from theorem 4.2: while h(x) satisfies authors’ definition of DP (I discussed by why this definition is problematic in comment 1) and is close to g(x), this should be interpreted as neither adding noise or applying pruning significantly deviates from f(x) in probability. The authors instead use 4.2 to draw similarities between adding noise and applying pruning, which I think is not well supported by their findings.\n\n4. Relationship between Pruning and DP: In DP, the mechanism is required to be stochastic in order to maintain privacy given repeated usage. In contrast, unless the original network is re-trained for each input during inference, the output is deterministic. The idea that we can somehow achieve DP (with respect to inputs during inference) by passing the input through a pruned network is thus unrealistic. \n\nQuestions:\nIf we replaced \\bar{A}x with another matrix B that has upper and lower bounded spectral norm, wouldn’t it be possible to achieve the similar results to claim 4.3 and 4.4? Namely, let e=Lap^m * Bx, then f(x)+e is “private” and ||e - Bx|| is epsilon small?\n\n[Post rebuttal] The rebuttal has not address any of my main concerns, so my rating stays.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Dz34tIDeCdo", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "My summary of the papers main goal:\n\nThe paper aims at drawing a connection between neural network pruning, and privacy of the trained model. More specifically, the authors try to draw similarities between differentially private training of DNNs and pruning. They define a notion of $(\\epsilon, \\delta)$ closeness, to measure how close a function is to a randomized function, and then they show that magnitude-based pruning is close to randomized addition of noise, for large number of parameters in the network. To experimentally evaluate this, they mount a model inversion attack on two pruned set of DNNs. \n\nPros:\n+ The problem they address is interesting and novel. It could help get more out of DNNs and hit two birds (privacy and compression) with one stone. It could also offer some neat insights.\n\n+ I am not a theory person myself, but the proof sketch for the closeness of DP and pruning seems sound. However, I wonder how this approximation effects the individuals' privacy in practice.\n\nCons:\n\n- I am very skeptical about the experimental setup. Here are my main concerns:\n\na) Since the claim in Section 4 is that pruning is close to differential privacy, the experiments in section 5 should also try and depict that. So ideally, what we should see in the experiments is a one-to-one comparison of a DNN trained with DP-SGD, with a DNN pruned using magnitude-based pruning. I think these two sets of models should be compared in terms of accuracy, and their resistance to different set of attacks, such as membership inference and attribute inference/model inversion. However, we do not see a DP-trained model in the results, so we cannot have a conclusive comparison. The authors could use libraries such as Opacus or TF-privacy to train DP models so I think seeing results on that would be interesting. \n\nb) I think a membership inference attack would be a better measure of how close a method is to DP, than model inversion. Based on my own experience w/ differentially private DNNs and both model-inversion and membership inference attacks, I have seen that the notion of privacy that DP protects is close to membership, as reflected in its formulation, than to model inversion. Many average-case privacy mitigations offer protection against model inversion for some samples, but would not be resistant to membership inference attacks.  If DP is to be contended here, mounting membership inference on both a DP and a pruned model would be a better test of privacy, in my opinion. \n\nc) The model inversion attack is also lacking. Visualizing two sets of examples does not really prove anything, especially not DP. DP offers a stringent \"worst-case\" guarantee. This cannot be asserted or evaluated with two image reconstructions. A better evaluation would be to somehow offer a success rate for the attack, and also provide the lowest and highest score per sample. Maybe there is one example that is actually completely reconstructable. Even if out of 10,000 samples, one is reconstructed, the guarantee is voided.\n\n- Apart from the points mentioned above, I am also having some difficulty drawing parallels between pruning and DP-SGD.  From the explanation in the second paragraph of Section 5, it seems as though pruning happens once every $t$ epochs, and then normal re-training takes place. If that is the case, does the closeness still hold? DP-SGD requires that no data is fed in the model without applying noise to the gradients (unless it is public data). If in the case of pruning there are epochs where the pruning isn't happen, then are we really achieving guarantees? \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper claims to draw a connection between pruning and differential privacy. There seem to be conceptual issues with the paper, highlighted by all reviewers (see particularly Reviewer 3's review), which the authors had no response to. For example, a function approximating another does not imply any transfer of differential privacy. This is a fundamental issue that the authors would need to address.

Some papers (suggested by the area chair and reviewers) related to differential privacy and pruning that the authors may wish to be aware of include https://arxiv.org/abs/1503.02031 and https://arxiv.org/abs/2008.13578 
Decision: Reject