Winning Privately: The Differentially Private Lottery Ticket Mechanism
Authors: Lovedeep Gondara
Ke Wang
Ricardo Silva Carvalho
Venue:  (2020)
Keywords: Differentially private neural networks
lottery ticket hypothesis
differential privacy

Abstract: We propose the differentially private lottery ticket mechanism (DPLTM). An end-to-end differentially private training paradigm based on the lottery ticket hypothesis. Using ``high-quality winners", selected via our custom score function, DPLTM significantly outperforms state-of-the-art. We show that DPLTM converges faster, allowing for early stopping with reduced privacy budget consumption. We further show that the tickets from DPLTM are transferable across datasets, domains, and architectures. Our extensive evaluation on several public datasets provides evidence to our claims. 

Under review as a conference paper at ICLR 2020
WINNING PRIVATELY: THE DIFFERENTIALLY PRIVATE LOTTERY TICKET MECHANISM
Anonymous authors Paper under double-blind review
ABSTRACT
We propose the differentially private lottery ticket mechanism (DPLTM). An end-to-end differentially private training paradigm based on the lottery ticket hypothesis. Using "high-quality winners", selected via our custom score func- tion, DPLTM significantly outperforms state-of-the-art. We show that DPLTM converges faster, allowing for early stopping with reduced privacy budget con- sumption. We further show that the tickets from DPLTM are transferable across datasets, domains, and architectures. Our extensive evaluation on several public datasets provides evidence to our claims.
INTRODUCTION
Learning while preserving the privacy of the contributing users is a priority for neural networks trained on sensitive data. Especially, when it is known that neural networks tend to "remember" training data instances (such as patient's 's healthcare information) (Carlini et al.] 2018 Fredrikson let al. 2015: [Song et al. 2017 Wu et al., 2016). Differential privacy (Dwork al. [2006) has be- come the de facto standard for protecting an individual's 's privacy in machine learning. Differentially private training of neural networks ensures that the model does not unduly disclose any sensitive information. The most often used approach to achieve this goal is the method of gradient perturba- tion, where we add controlled noise to the gradients during the training phase. Differentially Private Stochastic Gradient Descent (DPSGD) (Abadi et al.] 2016) is the current tate-of-the-aa used exten- sively for training srivacy-preservee front, the main reason for which we discuss below.
neural networks. DPSGD, however, falls short on the utility
DPSGD, for given minibatch, first computes the per-observation gradient, g(x:),, and then clips g(x;) in l2 norm, g(xx)/max(1 (s(c))))))))) (Line 6 in (bbaaii et al. (2016), Algorithm 1). We can see that the norm will be large (proportional to the number of model parameters), especially for a multi-layer neural network, leading to a large "clipping impact" on the gradient, resulting in "smaller" clipped- gradient magnitude, easily overwhelmed by noise, required for preserving differential privacy. This leads to diminished utility, especially, for scenarios where require tight privacy (large noise).
An obvious solution is to minimize the number of model parameters while maximizing the model's utility. This, however, non-trivial for differentially private neural networks, especially when need to balance privacy and utility. Recently, it has been shown that there exist smaller sub-networks within large neural networks, which when trained in isolation provide similar utility as the large net- works (Frankle & Carbin (2018) 8 Frankle et al. 2019). The phenomenon, known as the lottery ticket hypothesis an encouraging step towards finding small, high-utility architectures. But, directly using the lottery ticket hypothesis with differential privacy is non-trivial as we need to ensure the complete process (from ticket selection to training the winning ticket) end-to-end differentially private.
As a potential solution to improve the privacy-utility bottleneck in differentially private neural net- works, we propose the Differentially Private Lottery Ticket Mechanism (DPLTM). To ensure differ- ential privacy in DPLTM, we use a three-tiered approach. In phase 1, we create the lottery tickets following the principles of the lottery ticket mechanism. In phase 2, we select the winning ticket with differential privacy, making sure that we pick the ticket with a small number of parameters and with high utility via our custom score function (details in Section B.3.1). After differentially private selection of the winning ticket, our phase 3 trains the winning architecture with differential privacy. In summary, main contributions in this work follows:

---

Under review as a conference paper at ICLR 2020
1. We propose DPLTM, the differentially private lottery ticket mechanism. An end-to-end differentially private extension of the lottery ticket hypothesis. We design a custom score function to ensure the differentially private selection of "best" winners, which aids DPLTM to significantly improve the privacy-utilic trade-off for differentially private neural net- works.
2. Due to the reduced noise impact in DPLTM, we show that DPLTM converges at faster rate compared to DPSGD, leading to consumption of smaller privacy budget and better utility if early stopping is desired.
3. We show that the winning tickets in DPLTM are "transferable" across datasets, domains, and model architectures. Leading to the possibility of ticket generation and selection on any public dataset, resulting in lower privacy cost,
4. Using five real-life datasets, we show that DPLTM significantly outperforms DPSGD on all datasets, and for all privacy budgets.
PRELIMINARIES
We use this section to introduce differential privacy and the lottery ticket hypothesis.
2.1 DIFFERENTIAL PRIVACY
Differential privacy (Dwork et al. 2006) provides us with formal and provable privacy guarantees, with the intuition that a randomized algorithm behaves similarly on "similar" input datasets, for- mally
Definition 1. (Differential privacy (Dwork et al. 2006)) A randomized mechanism M: : D + Rd
preserves (c, diiffferenet privacy if for any pair of neighbouring databases (I., y D") such
that d(x, 8) = 1, and for all sets S of possible outputs:
Pr[M(z) E S] e Pr(M(y) SS++
Intuitively, Definition D states that for any pair of two neighboring datasets, x; y. differing on any row, randomized mechanism M's outcome does not change by more than multiplicative factor of e²_ Moreover, the guarantee fails with probability no larger than If ā = O, we have pure-c differential privacy.
The Exponential Mechanism (EM) (McSherry & Talwar 2007) is a well-known tool for providing differential privacy. Defined by a range R. privacy parameter e, and score function X x R. R that maps a dataset to the utility scores, given a dataset D E X the EM defines probability distribution over R according the utility score. In other words, the EM is more likely to output some r R with higher utility scores, formally
Definition 2. (Exponential Mechanism (McSherry & Talwar 2007)) The exponential mechanism M(D, u, R) selects and outputs an element r E R with probability proportional to
(e((Dr))
exp
2Au
where Au is the sensitivity (Au- max X (uX,)) -XX,'))(X'X,,) u(X',r))) of the score function.
In terms of privacy guarantees, the exponential Mechanism provides c- differential privacy (McSh- erry& & Talwar 2007)
2.2 LOTTERY TICKET HYPOTHESTS
The Lottery Ticket Hypothesis was proposed by Frankle & Carbin (008), where interestingly, it was shown that randomly initialized neural networks contain small subnetworks, which when trained in isolation, can provide similar utility as the full network. To get the subnetworks, we train a network for I iterations, prune p% of its weights (of smallest magnitude), and reset the weights of the pruned network to original initialization, to be trained again. This process ensures that for n rounds, each round prunes pl /n% of the weights. Such pruned, small subnetworks, with high utility are known "winning tickets" from the lottery mechanism.
2

---

Under review as a conference paper at ICLR 2020
3 DIFFERENTIALLY PRIVATE LOTTERY TICKET MECHANISM
3.1 OVERVIEW
We start by providing overview of DPLTM. Using the input dataset, X, we generate and store multiple "lottery-tickets", each with a varying number of model parameters. Then we use ex- ponential mechanism (McSherry & Talwar 2007) to pick winning ticket using custom utility function (details follow), that provides us with the desired balance between the number of model parameters and the model utility. After selecting the winner, differential privacy. Our total privacy cost, hence, is composed of two separate parts, selecting the winning ticket and training the winning ticket. We present the complete process succinetly as Algorithm I followed by a walk-through.
train the winning architecture with
Algorithm Differentially Private Lottery Ticket Mechanism (DPLTM)
Require:
Dataset: X, Total privacy budget: (e, 6), Pruning percent: Number of tickets: T.
Ticket training iterations: I, final model training iterations: I, Neural Network: f. Initial model parameters: fu. Initial mask: m, Privacy budget for ticket selection: Privacy budget for ticket
training: E2, 6, Constant for score function: 2, Minibatch size: L, Clipping factor: C, Learning
rate:
Phase Generating Lottery Tickets
1: procedure LTH(f,m .,, Ou)
2: Randomly initialize f(X, m O bn); 11%
b m the initial mask
3: for i do
4: Train f(X, m @ 0p) for I iterations, to get S(X, m @ 0z) Prune p% of parameters from 0z, creating new mask m'
m'[l] [i] where Og is
pruned
6:
Reset the remaining parameters their values in Og
7:
f(X, m' O 0n) is the lottery ticket Store the mask m', initial parameters 6n
8:
9:
Store the proportion of remaining model parameters, in the lottery ticket Store the performance Let m'
lottery ticket, a, on test set
11:
12:
end for return C,A,, M, 0o The collection of parameter proportions, model utilities, masks, and initial parameters, G E C. E A, m E M; i E [1,7] end procedure
13:
Phase 2 Selecting a Winning Ticket
procedure DPWT(C.A, 61)
16: Calculate score SiC, = A(1 -c)
exp( 95 23
Select a winning ticket, T, with probability,
Σx exp( (xpp(50) 5 24
return
The winning ticket
19:
end procedure
Phase
Training the Winning Ticket
20:
procedure DPTWT(T)
21:
Initialize the network.f. with mask and initial values from the winning ticket
for / do
23:
Take a minibatch with sampling probability 1/N
D N is the total dataset size
For each F; L, compute gradient gle (2,,) Vo, L(Br, 9k I (E, 92 (v.) (axx(//x() (1,) N ((2
25:
26:
0x-1 + 0s na
end for
28:
end procedure
3

---

Under review as a conference paper at ICLR 2020
3.2 DPLTM WALKTHROUGH
Next we provide phase by phase walkthrough of DPLTM.
Phase 1 (Generating lottery lickets): We start with generating lottery tickets required for DLPTM. At this stage, we are not yet concerned about privacy. So we use the non-private lottery ticket mechanism with our input dataset X, and generate T number of lottery tickets (f E [1,-.. .T. Specifically, we use iterative pruning version of the lottery ticket mechanism, where using the prun- ing parameter, p. each ticket iteration, we remove p% of model parameters with the smallest magnitude. This results in T tickets with a successively smaller number of parameters. Results from each ticket (accuracy on the test set, A,, i E [1, TD are stored along with the fraction of parameters (C,, i E [1, T') remaining in the model. For further use, we also store the mask my from each ticket and the randomly initialized initial parameters 8g-
Phase 2 (Selecting winning ticket with differentially privacy): After generating candidate tickets, we need to select a winning ticket that can be subsequently trained with differential privacy. But, picking winner is non-trivial for two reasons, first the tickets generated using sensitive data, we cannot directly pick a winner, that is, we need differential privacy for selecting the winning ticket, second, we need to pick winner such that the winner has adequate balance between the number of model parameters (smaller the better) and the model performance (higher the better). As solution, use the Exponential Mechanism (EM) (McSherry & Talwar (007)) to pick our winner with differential privacy. And to balance the number of model parameters and the utility, we define our custom score function using the combination of the accuracy achieved by the ticket on the test set and the proportion of parameters left in the network (more details in Sections 3.3.1 and 3.4.
Phase 3 (Training the winning ticket with differential privacy): After we select our winning ticket with differential privacy in phase 2, now we need to train our "winner" architecture so the final model differentially private. We do so by using the method similar to the differentially private stochastic gradient descent (DPSGD) (Abadi et al. 2016) for the training of our winning ticket. This, in contrast to DPSGD's naive implementation, now only trains a "sub-network" with a significantly small number of parameters. And hence provides significantly better utility, reasons for which discussed at length in the Introduction. Our extensive empirical evaluation in Section provides evidence for this claim.
Next, we provide formal privacy guarantees for DPLTM. We start with introducing the EM for DPLTM with our custom score function.
3.3 DIFFERENTIAL PRIVACY GUARANTEES OF DPLTM
As seen in Algorithm our first phase of generating candidate tickets is non-private. Differential privacy comes into play in phase 2, where we pick winning ticket with differential privacy. Hence, we start with privacy guarantees of phase 2.
3.3. SELECTING WINNING TICKET
For the Exponential Mechanism (EM), as discussed in preliminaries, we need to define a score/utility function that assigns higher score to "good" outputs. For DPLTM, define the score function as follows
(1- (vC))
(1)
where A is the classification accuracy on the test set for the given network configuration (ticket), is the proportion of remaining weights in the network, and v a constant. We discuss some properties of the score function in detail in the following section (Section 3.4).
After defining the score function, we sample our winning ticket with probability
exp( (1
P
ΣE exp S ZA
where P is the probability of picking ticket, 61 is the privacy budget for EM, and A is the sensitivity of the score/utility function. Tickets with "higher" score function have a higher probability of getting selected compared to the tickets with lower score.
Lemma 1. Sensitivity (A) of the score function,S, is directly proportional to
4

---

Under review as a conference paper at ICLR 2020
Proof. Sketch: The classification accuracy (AA), and the proportion of remaining parameters in the model (C) are bounded by [0, 1]. The change of a single record can "at-worse" impact the product of (A, C) by 1. Hence the overall sensitivity is proportional to the constant, Full, formal proof is provided in the Appendix for space constraints.
Theorem 1. Phase 2 (Selecting a winning ticket) is (E1) - -differentialllly private.
Proof. Sketch: We get the proof using our custom score function with an instantiation of EMM is provided in the Appendix for space constraints.
3.3.2 TRAINING THE WINNING TICKET
After we select our winning ticket with differential privacy in phase 2. Our next step is train the winning architecture in a differentially private fashion. For this step, we use the training process similar DPSGD (Abadi et al. 2016). Specifically, after calculating the per-observation gradients for a minibatch, we clip the gradients (line 25 in Algorithm D by their la norm, scaled by a constant C. to enforce sensitivity, and then add appropriate Gaussian noise to ensure differential privacy, formally
Theorem 2. Phase 3 (Training the winning ticket) is (e2, 5) differentially private, if we chose L/N (lgg(1/))
42
Proof. Proof is argued in the same way DPSGD (Abadi et al. 2016) using 62 and T. is omitted here for space constraints.
3.3.3 PUTTING IT ALL TOGETHER
After generating the lottery tickets, selecting the winner with differential privacy, and the differen- tially private training of the winning ticket, we now ready "put it all together" and state the overall privacy guarantees of our proposed method (DPLTM).
Theorem 3. Algorithm 7 is (c, 5) differentially private, with e > 0,5 >
Proof. We have already seen that phase is 61 --differentially private and phase 3 is 622 5- differentially private. Using the "naive" composition (Dwork et al. 2006 it is easy to see that the Algorithm Dis e, d-differentially private, with e = 61 + E2 and ò.
3.4 DISCUSSION
We use this section to discuss some interesting properties of DPLTM. first observation is the seamless integration of differential privacy with the lottery ticket mechanism in DPLTM, making it accessible for implementation, while providing significantly better utility compared the "naive" DPSGD (Experiments in Section support this claim). As per earlier discussions, the success of our method is hinged on the existence of a winning ticket fewer number of model parameters and high utility. So it is vital that out of all available tickets, the probability of selecting the winner with a small number of model parameters and high accuracy high. Our custom utility function S strives to achieve this goal by ensuring that the selection process does not degenerate to uniform random sampling. In particular, the utility function assigns more weight to the models with high accuracy and low number of model parameters, which we modulate using the constant v. Large assigns more weight to C (proportion of model parameters in the ticket). For good utility with tight privacy, we advocate using large values for v.
As we observe from Theorem 3, total privacy budget for our method is composed of two parts. The privacy budget from the EM phase used select the winning ticket and the privacy budget train the winning ticket. Hence, we need to decide on the overall privacy budget split. That is, the portion of the budget to allocate to the drawing of the winning ticket and the portion of the privacy budget for
As we are only composing two mechanisms, advanced composition is not necessary. If most tickets performing similarly, which is often the case, it is of hest interest to pick the ticket with the smallest number of model parameters.
5

---

Under review as a conference paper at ICLR 2020
the training of the winning ticket. We advocate dedicating large proportion of the privacy budget to the training of the winning ticket and small portion for selecting the winning ticket. With defined utility function, small privacy budget suffices for selecting "good" ticket (empirical evidence provided in Section 4 A question a reader might ask: Why can't we train the full network differentially privately when generating tickets? That is, why do we produce non-private tickets first and then train differentially private model? The answer is simple, as differential privacy composes by iteration, training multiple networks using the methodology described in Algorithm [ would result in large privacy budget, and hence, noisier models, providing worse utility compared to our proposed method.
4 EXPERIMENTS
Here we provide empirical evidence on various datasets support our claim that our proposed method (DPLTM) outperforms DPSGD. We begin by describing the datasets.
4.1
DATASETS
For our empirical evaluation, five publicly available datasets. Dataset details are provided in Table
Dataset
Attributes
Observations
Class
MNIST
784
60000
10
HAR
521
10299
6
Fashion- -NNIST
784
60000
10
Kuzushiji-MNIST
784
60000
10
ISOLET
617
7797
26
Table 1: Dataset details, Attributes is the dataset dimensionality, Observations are the number of rows, and Class the number of classes in the classification target.
4.2 SETUP
For generating lottery tickets (phase 1), our implementation is based on the publicly available source code Our underlying base model is a fully connected neural network with three layers. Hidden layers use ReLU (Nair & Hinton] 2010) as the activation function. Learning rate is kept fixed at 0.1 and minibatch size kept fixed at 400. We set the pruning percent, p. at 30% for the first two layers and 20% for the last layer. Which means that for each subsequent ticket, the model will prune 30% of the weights compared to the previous ticket for the first two layers and 20% the weights for the final layer. To generate lottery tickets, the mechanism is run for 5000 iterations (Z) for each ticket. Differentially private training of the winning ticket is run for 50 epochs.
DPSGD's implementation is based on the publicly available source code Clipping norm for DPSGD and DPLTM is set at constant of for all experiments. All the rest of the hyperpa- rameters, including the underlying model architecture, are the same for DPSGD in DPLTM to ensure a fair comparison.
If the input dataset does not have predefined train/test partition, the dataset used as the test set. All models are run for 10 iterations and we report the average results. For privacy, d is kept fixed at 10-5 with e varied required and reported. For our model, the privacy budget split is set at 90/10. That is, we reserve 90% of the privacy budget for the differentially private training of the winning ticket and 10% for the differentially private selection of the winning ticket. v is kept fixed at 50 for all experiments. Source code for our method is made publicly available"
80/20 split, with 20% of
https: http:////ttttoooooooooorrrrttttt
https: : thub. httptthc...oeeeoooooooo/////r/ee
Link available after de-anonymization

---

Under review as a conference paper at ICLR 2020
MNIST
HAR
Fashion-MNNSS
100
90
85
Accuracy
90
Accuracy
70
Accuracy
80
80
DYLIM
50
75
DPSGD
70
NP
30
70
1.0
0.5
0.25
0.2
1.0
0.5
0.25
0.2
1.0
0.5
0.25
0.2
(a)
(c)
KuzushijiMMNSST
ISOLET
85
100
Accuracy
Accuracy
75
70
50
65
25
40
1.0
0.5
0.25
0.2
1.0
0.5
0.25
0.2
(d)
(e)
Figure I: Main comparison: Our proposed method, DPLTM (red line) significantly outperforms our competitor, DPSGD (blue line) on all datasets and for all privacy budgets. The non-noisy model (provided as an upper bound on the performance achievable using this architecture) presented as the green line. Error bars on the plot represent the standard deviation.
4.3 MAIN COMPARISON
Figure I shows the results of our main comparison with DPSGD. First and the obvious observation is that our proposed model (DPLTM, red line) significantly outperforms our competitor (DPSGD, blue line). This provides evidence for our earlier claim that our proposed method provides better utility than DPSGD. The second observation is as the privacy budget gets tighter (e decreases), the performance gap between our proposed method (DPLTM) and DPSGD increases. That is, DPLTM is "robust" compared to DPSGD. The performance gap is specifically larger for small datasets (HAR and ISOLET), as naive DPSGD suffers from worse utility degradation when dataset size is small, due to the interplay between the clipping and sampling probability (See Algorithm and Theorem 1 of Abadi et al. (2016)).
We observe this utility boost due the reasons discussed in the introduction. That is, in DPLTM, the number of model parameters is "small" compared to the full model used for DPSGE Hence the "clipping" has relatively diminished impact DPLTM's performance compared to DPSGD. Leading to overall better utility and robust models.
4.4 CONVERGENCE AND EARLY STOPPING
As we briefly mentioned earlier, DPLTM provides faster convergence compared to DPSGD, and hence allows for early stopping with reduced consumption of the total privacy budget. This is made possible by keeping track of the privacy loss at each iteration and stopping when the desired accu- racy/privacy budget is reached. Here investigate the claim in detail. We keep the experimental setup the same as in the previous section, with the privacy budget fixed at < = 1, = 10-5 Figure 2 shows the results. Main plots show the accuracy on the test set as function of the number of epochs. To focus on the convergence during earlier iterations (when privacy consumption is low), we have provided "inset" plots that are the zoomed version of the highlighted area on the main plot (including first 15 epochs).
We observe that irrespective of the dataset, DPLTM converges faster compared DPSGD. The highlighted area in the plots shows the scenario if we were to use early stopping, at the point when the total privacy consumption c = 0.3. In the inset plot, the black dots represent the points where both models (DPLTM and DPSGD) will consume that privacy budget. As DPLTM has extra privacy
DPLTTM consistently selects winning tickets with total parameters S 10% of the full model.

---

Under review as a conference paper at ICLR 2020
Nodel 2P3TH DFSGO
Model DPLTM DP5GD
Nodel CEPTN DFSCO
20.95
2 290m
4000
7005
2000
2000
50.00
40.0%
23.05
2005
200%
28.50
11.0%
2006
Epach
13
2000
20.5
Epacl
Epoch
(a) MNIST
(b) HAR
(c) Fashion-MNISS
Modil
OPTTH
DPSGO
Model DP
DPS6O
$3:35
33.25
644
243.95
3 100%
500%
20.00
10.00
3000
Epoch
Epach
Epoc1
(d) Kuzushiji-NNIST MNIST
(e) ISOLET
Figure 2: Convergence vs the number of epochs for DPLTM and DPSGD. Red line our proposed method (DPLTM), the blue line is the competitor (DPSGD). The X-axis shows the number of epochs and Y-axis shows the accuracy on the test set. "Inset" plots show the zoomed version the high- lighted area focus on the plot region when privacy consumption is low. Black dots on the zoomed version signify the points where both models have consumed privacy, = 0.3. We can observe that DPLTM converges much faster compared to DPSGD with significant performance difference.
cost of picking the winner, we see that DPLTM will run for "fewer" epochs compared to DPSGD. But, irrespective of the fact that DPLTM runs for fewer epochs, still outperforms DPSGD by margin on average of >> 17%. which is sometimes greater than 50% (in case of ISOLET). A brief insight into this performance gain is as follows, as the updates in DPLTM are inherently "less noisy" due to reduced number of model parameters, DPLTM converges much faster, using less number of iterations compared to DPSGD.
4.5 TICKET TRANSFER
So far, have seen that our proposed method significantly outperforms DPSGD on all datasets and for all privacy budgets. We use this section to further explore DPLTM. Mainly, we answer the question: As is recently discovered for generic lottery mechanism (Morcos et al. (20T9)), that a winning ticket can generalize across datasets, can we extend this notion to DPLTM? Where we can use a publicly available dataset get winning ticket in non-private setting, and then use that winning ticket to train a differentially private model on our sensitive dataset. This has a unique advantage of allowing us to "get rid"' of the privacy cost related to the differentially private selection of the winning ticket using EM, and allows us to focus our full privacy budget on the training of the winning ticket. But, sometimes the publicly available datasets are not similar to the sensitive data (different input dimensionality, different domain, different number of outcome classes, etc.). For these scenarios, we investigate the feasibility of using conn-compttible" public datasets for generating lottery tickets. We start with exploring the case where transfer tickets across the similar architectures (i.e. same dimensionality and outcome classes), and then move on to transfer across non-compatible datasets.
A detailed evaluation is provided in the Appendix. In both cases (Transfer across similar archi- tectures and Transfer across different architectures), DPLTM significantly outperforms DPSGD, especially for tight privacy (small e).
5 RELATED WORK
Our related work mainly falls into two categories. First is the prior work related to the lottery ticket mechanism, and second is related the differential privacy in neural networks. The lottery
8

---

Under review as a conference paper at ICLR 2020
ticket hypothesis was introduced in Frankle & Carbin (018) and provides evidence that there exist subnetworks within a large network, which when trained in isolation, can perform at-par with the large network. This work was further extended in Frankle et al. (2019), where the initial idea was improved to work on larger, deeper networks. Lottery ticket mechanism since has been further explored, it has been shown that the winning tickets be used across datasets (Morcos et al.) 2019) and that the tickets occur in other domains as well, such as in NLP (Yu et al. 2019).
Perturbing the learning process to provide differential privacy has been studied in various contexts (Rajkumar & Agarwal 2012 Song el al. 2013) Abadi et al.) 2016 Shokri & Shmatikov 2015). Where gradients are perturbed during the gradient descent, so the resulting weight updates, and hence the model itself is differentially private. Differentially private stochastic gradient descent (DPSGD), proposed in Abadi et al. (2016), is the most popular and most often used method for differentially private training for wide variety of neural networks (Xie et al. 201 8, [Beaulieu-Jones jet al., 2017, McMahan et al. 2017). DPSGD, however, falls short on the utility front, as the noise required for preserving privacy in DPSGD scales up proportional to the model size, discussed at length in the Introduction.
CONCLUSION
We have proposed DPLTM, an end-to-end differentially private version of the lottery ticket mech- anism. Using our custom score function to "pick" differentially private winning tickets, have shown that DPLTM significantly outperforms DPSGD on a variety of datasets, tasks, and privacy budgets. We have shown that DPLTM converges faster compared to DPSGD, leading to reduced pri- vacy budget consumption with improved utility if early stopping is desired. We have further shown that tickets in DPLTM to focus our future work on the detailed study of the mechanism when used for differentially private "transfer-learning" and to further improve the utility guarantees along with the extensions to various "other" models such as the Generative Adversarial Networks (Goodfellow et al. 2014)).
transferable across datasets, architectures, and domains. We would like
REFERENCES
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, pp. 308-318, ACM, 2016.
Brett K Beaulieu-Jones, Zhiwei Steven Wu, Chris Williams, and Casey S Greene. Privacy- preserving generative deep neural networks support clinical data sharing. BioRxiv, pp. 159756, 2017.
Nicholas Carlini, Chang Liu, Jernej Kos, Úlfar Erlingsson, and Dawn Song. The secret sharer: Measuring unintended neural network memorization & extracting secrets. arXiv preprini vrXiv:1802.08232. 2018
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitiv- ity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptogra- phy, TCC 06, pp. 265-284, Berlin, Heidelberg, 2006. Springer- ISBN 3-540-32731- 978-3-540-32731-88 doi: 10. 10.1007/11681888.114 URL http:://xxx dww...oci..ooo org 10.
11681878 14.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint S5t.::8803036333 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. The lottery ticket hypothesis at scale. arXiv preprint arXiv:1903.01611 2019.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Confer- ence on Computer and Communications Security, pp. 5322-1333. ACM, 2015.

---

Under review as a conference paper at ICLR 2020
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. (672-2680, 2014.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06963 2017.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 07), pp. 94 103. IEEE, 2007.
Ari S Morcos, Haonan Yu, Michela Pagannii, and Yuandong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. arXiv preprint arXiv:1906.0221 027773, 2019.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference machine learning (ICML-I0), pp- 807-814, 2010.
Arun Rajkumar and Shivani Agarwal. A differentially private stochastic gradient descent algorithm for multiparty classification. Artificial Intelligence and Statistics, pp. 933-941, 2012.
Reza Shokri and Vitaly Shmatikov. Privacy-prees srracc-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1310-1321. ACM, 2015.
Congzheng Song, Thomas Ristenpart, and Vitaly Shmatikov. Machine learning models that re- member too much. In Proceedings of the 2017 ACM SIGSAC Conference Computer and Communications Security, pp. 587- ACM, 2017.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE Global Conference Signal and Information Processing, pp. 245-248. IEEE, 2013.
Xi Wu, Matthew Fredrikson, Somesh Jha, and Jeffrey F Naughton. A methodology for formalizing model-inversion attacks. In 2016 IEEE 29th Computer Security Foundations Symposium (CSF), pp. 355-370. IEEE, 2016.
Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv:1802.000
2018.
Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in rl and nlp. arXiv preprint 1906 2019.
A APPENDIX
A.1 TICKET TRANSFER
A.1.1 TRANSFER ACROSS SIMILAR ARCHITECTURES
To test the transfer across similar architectures, winning ticke | and then use the winning ticket to train a differentially private model for MNIST and MNSS.. 3 the results. We observe that in the beginning, when the privacy is "loose", that is, in case of less noise, DPLTM trained on a ticket from "another" similar dataset performs similar DPSGD. But, as the privacy gets tight (decreasing e), DPLTM outperforms DPSGD by significant margin.
the Kuzushij-MNNIST dataset to select
Winning ticket, in this case, is the smallest model closest to the test accuracy the full model, such that the model parameters in the small model are 10% of the full model.
10

---

Under review as a conference paper at ICLR 2020
MNIST
Fashion-MNIST
95
85
Accuracy
90
Accuracy
80
85
DPLTM
75
80
DPSGD
75
70
1.0
0.5
0.25
0.2
1.0
0.5
0.25
0.2
6
E
(a)
Figure 3: DPLTM transfer across similar architectures. Red line (DPLTM) is our method, whereas blue line (DPSGD) is the competitor. We can see as the privacy cost increases, our method, trained on a ticket from Kuzushij-MNIST, outperforms DPSGD by significant margin.
A.1.2 TRANSFER ACROSS DIFFERENT ARCHITECTURES
Now we investigate an interesting case, where the publicly available dataset is "quite" different from sensitive data. Not only in the terms of the domain but also the dimensionality and outcome. To test this scenario, we use the same, Kuzushiji-MNIST dataset to create a winning ticket, and we the winning ticket train differentially private models for HAR and ISOLET datasets. As the dimensionality and the output are different between Kuzushiji-MNIS. an extra layer to the network during ticket generation, which acts as projection layer match the dimensionality of HAR or ISOLET. Then during the differentially private training, we remove the top-most layer (projection layer) and the output layer from the selected ticket.
HAR, and ISOLET, we add
Figure shows the results of this evaluation. We observe a similar trend before, where we observe similar performance between DPLTM and DPSGD when privacy is "loose", but DPLTM significantly outperforms DPSGD as we decrease (tight privacy). The performance, however, is not "as good" as in the case transfer across similar datasets. Which intuitive as we loose some "signal" by crossing the domain and dropping layers from the winning ticket. We leave further exploration of this idea for future studies.
HAR
ISOLET
75
90
Accuracy
Accuracy
70
55
50
DPLTM
45
30
DPSGD
35
10
1.0
0.5
0.25
0.2
1.0
0.5
0.25
0.2
6
Figure 4: DPLTM transfer across different datasets and domains. We observe that as the privacy cost increases, our method (DPLTM, red line), significantly outperforms DPSGD (blue line)
A.2 COMPARISON WITH RANDOM TICKETS
One of the questions reader might have is "What is the impact of using score function for selecting a winning ticket?". That is, are we doing much better than using a randomly selected ticket. We this section to explore this question empirically. We use the tightest reported privacy budget (e 0.2). and we compare the average accuracy achieved by our proposed method using the "winning tickets" compared randomly selected ticket.
11

---

Under review as a conference paper at ICLR 2020
Table
shows the results. We observe that using the winning ticket via method has signifi-
Dataset
Accuracy (Winning Ticket)
Accuracy (Random Ticket)
MNIST
0.84
0.79
HAR
0.61
0.56
Fashion-MNISS 0.77
0.73
Kuzushiji-MNIN
0.60
0.54
ISOLET
0.58
0.33
Table 2: Comparing accuracy of our winning ticket and a randomly sampled ticket. We observe that using the winning ticket has significant advantage over the use of randomly sampled ticket.
cant advantage the of randomly sampled ticket, with winning ticket outperforming the randomly sampled ticket on every dataset.
A.3 PROOFS
Lemma 1. Sensitivity (A) of the score function, directly proportional to
Proof. We can write the score function as
S(C. A) Ax (1-(vC)) A Ave
(3)
Sensitivity is defined as
Max((A-AuC))) (A' - A'vCC'))
(4)
where A',C "neighbouring" A,C.
max(AA AvC A' + A'vC')I
max(AA - A' - ArC + A'uC')l
(5)
mmxx(1 vlAC A'C'))
which for the worse case scenario, get S(C,A) = - ml
Theorem 1. Phase 2 (Selecting winning ticket) is (E1) differentially private.
12

---

Under review as a conference paper at ICLR 2020
Proof. We consider the scenario where the EM outputs some element datasets, X,
R on two neighbouring
()((X,r)
exp(
2du
<lu(X,r)
Pr[M(X, u, R) =r
EE exp(
2Au
Pr|M(X' R. =
(uu(X', .r) exp(
2A
c1u(X',
EMER expl
2Au
61 (ru(X.r) X,r)
cIu(X,r))
expl
ENER exp(
2 2Au
2Au
(1u (X', .r)
(10(X', r')
exp(
ΣMER exp(
2Au
2Au
(u((Xrr) r')
((((X,r)) u(x', (+))
EE exp(
2A cl
exp
2Au
(uu(X,,
X .r))
ΣNER exp(
2Au
EXER exp( <Iu(X,r)
S xexp( exp( )
2A
'Iu(X',
ΣVER exp(
2Au
<epp(()
13


Reviews:
[{"review_id": "HyxUS1_aKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposes a differentially private version of the lottery ticket mechanism using the exponential mechanism, thus improving the utility of DPSGD by reducing the number of parameters. It provides the privacy guarantee of the proposed algorithm and shows experimentally that the proposed algorithm outperforms DPSGD across datasets and privacy parameters.\n\nThe proposed algorithm seems quite interesting. Though it is more of a simple combination of the non-private lottery ticket mechanism and the exponential mechanism, improving utility for DPSGD is a very important topic in differentially private machine learning. The experimental results seem pretty strong. \n\nMy only concern is on the aspect of privacy, specially Lemma 1. I think if you’re only using the fact that A and C are in [0, 1], then A*(1-nu*C) can change by 1 if you go from (A=0, C=0) to (A=1, C=0). In the last step of equation (5), you replaced A-A’ by 1, which I think needs to be double-checked since there is the absolute value outside (and I guess the equality should  be <=). \nIf the calculation is correct, I’m still a bit concerned that the sensitivity is a bit too high compared to the signal. A and C are in [0, 1], and it seems like the sensitivity may not be much smaller than 1, which means the exponential mechanism can be pretty random. To that end, I think you may consider experimentally comparing with DPSGD with a randomly selected ticket, or a ticket with a moderate number of parameters kept.\n\n\n----- Post-rebuttal response -----\nI still don't see why the sensitivity is |1-\\nu|. (Doesn't that mean sensitivity is 0 when \\nu=1?) If we have (A=1, C=0) and (A'=0, C'=0), we have S(A,C)-S(A',C')=1-0=1; if we have (A=1, C=0) and (A'=1, C'=1), we have S(A,C)-S(A',C')=1-(1-\\nu)=\\nu. Yet for \\nu<1, |1-\\nu|<1 and for \\nu>1, |\\nu-1|<\\nu. I believe the sensitivity should be something like max(\\nu, 1). You may want to further check that. And I still think this is because the last step in (5) is not correct. Since you have absolute sign, you can't do |A-A'-X| \\leq ||A-A'|-X|.\n\nI'm also confused by the range of \\nu I should think of. \nIf \\nu <= 1, then in the example you give (A = 0.8, C=0.9,0.7,0.4,0.1, eps=0.1), I think the probability distribution used by exponential mechanism is not much higher for 0.9 than 0.1 (I think it's roughly 0.22 vs. 0.29?) with sensitivity |1-\\nu|.\nIf \\nu > 1, then I don't quite understand the score function S(A,C) = A*(1-\\nu*C), since for C > 1/\\nu, (1-\\nu*C) is negative and S would thus penalize higher A. The higher \\nu is, the wider the range of C that S will penalize. I can sort of understand this as setting a threshold such that any C above that threshold is just considered useless, but I still think it's a bit unreasonable to penalize higher accuracy, even for very complex model. You may want to explain more on that end.\n\nThanks for the experiments! They're very useful in supporting your proposed algorithm.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkeCIYs2tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 is a mash-up of recent work on differentially private stochastic gradient descent (DPSGD) and the lottery ticket hypothesis. Differential privacy is a paradigm for ensuring that statistical models learned from a large dataset do not disclose any particulars of individual elements of that dataset. DPSGD is a technique that applies differential privacy ideas to models trained with stochastic gradient descent, where privacy is guaranteed by clipping and adding noise to gradients. On the other hand, the lottery ticket hypothesis is a method for finding sparse sub-networks contained in larger dense neural network models that are at least as accurate as the underlying dense model. The authors propose and demonstrate that by combining DPSGD with the lottery ticket hypothesis that they can train end-to-end differentially private models that outperform the DPSGD technique.\n\nI am up in the air about whether or not to accept this paper. I have trouble assessing the originality and significance of this work, the former since it seems to be a simple combination of two recent ideas, and the latter because I don't really have a context for how important the development of differentially-private optimization strategies are. I also didn't really find the experimental results to be that extensive, but I don't have a real sense of what state of the art is for differential privacy. Perhaps some of these issues could be mitigated by some additional exposition? I think one of my problems is that most of the paper is written to show that this new technique is superior to DPSGD, but I don't really have a good sense if either of them are sufficient as a practical solution of this problem.\n\nSome additional questions I had are as follows:\n\n1) One of the reasons given for combining the lottery ticket hypothesis with DPSGD is that DPSGD scales poorly as models get larger due to clipping by the norm of the gradient. Could you not compensate for this by scaling the norm by the number of parameters, or does that mess up the differential-privacy calculation?\n\n2) I don't understand how the winning ticket selection portion is differentially privacy. I understand that they use the exponential mechanism, but I would have assumed that the dataset needs to be varied in addition to the model. Is there an intuitive explanation for how privacy is achieved essentially just by varying the initialization and not actually adding noise to the data?\n\n3) Are there any datasets or methods where the effectiveness of the differential privacy technique could be directly assessed? For example, is there a way of testing whether the model is memorizing specific data elements, and then further showing that these differential privacy techniques mitigate this? This would be a nice check to have in addition to the plots of accuracy vs. privacy budget.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1x69C46tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "The existing differentially private training mechanism of deep neural networks includes a step that applies L2 normalization to gradient vectors. The authors argued that such norm clipping could lead to a small norm model parameter at the end, and the noise can thus overwhelm the accumulated gradient, leading to a substantial loss in terms of utility. To mitigate such utility loss, the authors proposed to use the lottery ticket mechanism to train a smaller network with similar utility and design an end-to-end differentially private mechanism for the whole process, including the selection of sub-network and the re-training of the selected sub-network. The general idea is quite interesting, but I have the following concerns.\n\n-   From Algorithm 1 of Abadi et al. 2016, one could see that the norm of per instance gradient is at least C, and the added noise has standard deviation of \\sigma C. Furthermore, since the final gradient step is an accumulation of all the per instance gradient in the mini-batch, this means that the scale of the final gradient is roughly $B\\cdot C$, where $B$ is the batch size. Note that since the noise is added to the accumulation gradient, so the scale of the noise should be roughly 1/B of the accumulated gradient. It seems to me that in this case the injected noise shouldn't overwhelm the gradient vector. Could the authors have a comment on this? \n\n-   The overall algorithm can be understood as a simple composition of the Exponential Mechanism algorithm and the DPSGD algorithm. Both of them satisfy differential privacy, so by a simple composition theorem argument the whole process also satisfies DP. This all makes sense, but the novelty is quite limited. The authors claim that the proposed mechanism is \n\"different from DPSGD's naive implementation\". This is not true, since at the end the original DPSGD algorithm is still used, just on a subnetwork. \n\n-   If the goal is to train a model with fewer parameters and comparable utility, why not simply starting from a small model with DPSGD and then use the large model as a teaching model? This simple strategy naturally gives DP guarantee without worrying about the LTH, hence you can also get same privacy guarantee with less injected noise.\n\n-   The experimental results basically confirm the expectation that with less injected noise, the model achieves better utility as compared with the DPSGD applied on the original large model.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides an approach to improve the differentially private SGD method by leveraging a differentially private version of the lottery mechanism, which reduces the number of parameters in the gradient update (and the dimension of the noise vectors). While this combination appears to be interesting, there is a non-trivial technical issue raised by Reviewer 3 on the sensitivity analysis in the paper. (R3 brought up this issue even after the rebuttal.) This issue needs to be resolved or clarified for the paper to be published.
Decision: Reject