Near-Zero-Cost Differentially Private Deep Learning with Teacher Ensembles
Authors: Lichao Sun
Yingbo Zhou
Jia Li
Richard Socher
Philip S. Yu
Caiming Xiong
Venue:  (2020)

Abstract: Ensuring the privacy of sensitive data used to train modern machine learning models is of paramount importance in many areas of practice. One approach to study these concerns is through the lens of differential privacy. In this framework, privacy guarantees are generally obtained by perturbing models in such a way that specifics of data used to train the model are made ambiguous. A particular instance of this approach is through a ``teacher-student'' model, wherein the teacher, who owns the sensitive data, provides the student with useful, but noisy, information, hopefully allowing the student model to perform well on a given task without access to particular features of the sensitive data. Because stronger privacy guarantees generally involve more significant noising on the part of the teacher, deploying existing frameworks fundamentally involves a trade-off between utility and privacy guarantee. One of the most important techniques used in previous work involves an ensemble of teacher models, which return information to a student based on a noisy voting procedure.  In this work, we propose a novel voting mechanism, which we call an Immutable Noisy ArgMax, that, under certain conditions, can bear very large random noising from the teacher without affecting the useful information transferred to the student. Our mechanisms improve over the state-of-the-art methods on all measures, and scale to larger tasks with both higher utility and stronger privacy ($\epsilon \approx 0$).

be guaranteed Under review as a conference paper at ICLR 2020
NEAR-ZERO-COS DIFFERENTIALLY PRIVATE DEEP LEARNING WITH TEACHER ENSEMBLES
Anonymous authors Paper under double-blind review
ABSTRACT
Ensuring the privacy of sensitive data used to train modern machine learning mod- els is of paramount importance in many areas of practice. One approach to study these concerns is through the lens of differential privacy. this framework, pri- vacy guarantees are generally obtained by perturbing models in such a way that specifics of data used to train the model are made ambiguous. particular in- stance of this approach is through "teacher-student" model, wherein the teacher, who owns the sensitive data, provides the student with useful, but noisy, informa- tion, hopefully allowing the student model perform well on given task with- out access to particular features of the sensitive data. Because stronger privacy guarantees generally involve more significant noising the part of the teacher, deploying existing frameworks fundamentally involves a trade-off between util- ity and privacy guarantee. One of the most important techniques used in previous work involves an ensemble of teacher models, which return information to stu- dent based on noisy voting procedure. In this work, we propose a novel voting mechanism, which we call an Immutable Noisy ArgMax, that, under certain con- ditions, can bear very large random noising from the teacher without affecting the useful information transferred to the student. Our mechanisms improve over the ttate-oftthe-ee methods on all measures, and scale larger tasks with both higher utility and stronger privacy (e sz 0).
INTRODUCTION
Recent years have witnessed impressive breakthroughs of deep learning in a wide variety of do- mains, such image classification (He et al., 2016), natural language processing (Devlin er al., 2018), reinforcement learning (Silver et al., 2017), and many more. Many attractive applications involve training models using highly sensitive data, to name few, diagnosis of diseases with med- ical records or genetic sequences (Alipanahi el al., 2015), mobile commerce behavior prediction (Yan, 2017), and location-basse based social network activity recognition (Gong al., 2018). However, recent studies exploiting privacy leakage from deep learning models have demonstrated that private, sensitive training data can be recovered from released models (Nicolas Papernot, 2017). Therefore, privacy protection is a critical issue in this context, and thus developing methods that protect sensi- tive data from being disclosed and exploited is of paramount importance.
In order to protect the privacy of the training data and mitigate the effects of adversarial attacks, various privacy protection works have been proposed in the literature (Michie el al., 1994; Nissim el al., 2007; Samangouei el al., 2018; Ma el al., 2018). The "teacher-student" learning framework with privacy constraints is of particular interest here, since can provide private student model without touching any sensitive data directly (Hamm et al., 2016; Pathak et al., 2010; Papernot et al., 2017). The original purpose of teacher-student framework is to transfer the knowledge from the teacher model to help train student to achieve similar performance with the teacher. To satisfy the privacy-preserving need, knowledge from the teacher model is carefully perturbed with random noise, before being passed to the student model. In this way, one hopes that adversary cannot ascertain the contributions of specific individuals in the original dataset even they have full access to the student model. Using the techniques of differential privacy, such protection in certain settings. However, the current saachersttuden frameworks (c.g. Nicolas Papernot (2017) and (Papernot et al., 2018 1)) involve trade-off between student's performance and privacy. This

---

Under review as a conference paper at ICLR 2020
non-public access
Data
Teacher
sample
Data
Teacher
student
Private
Data
Teacher
Data
Public
Data
Teacher
Label count vector
query
Data
Data Flow
Train Flow
Perturbation Flow
constant
random noise
Figure I: Overview of the proposed approach: firstly, the private data is partition to non-overlapping splits to train the teacher models. To train the student model, the ensemble of teachers then aggregate their predictions the queried example from student, followed by adding large constant the highest counted class vote. The count vector then gets randomly perturbed with noise followed by an ArgMax operation. Finally, the student model is trained by using the returned label from the teacher ensemble.
is because the amount of noise perturbation required is substantial to ensure privacy at the desired level, which leads degraded information passed to student and results in inaccurate models.
In this paper, we develop technique to address the aforementioned problem, which facilitates the deployment of accurate models with near zero privacy cost. Instead of using traditional noisy ArgMax, we propose new approach named immutable noisy ArgMax as describe in Section 2. We redesign the aggregation approach via adding large constant into the current largest count of count vector, which enables immutable noisy ArgMax into teacher-student model. As result, this method improves both privacy and utility over previous teacher- student based methods.
The primary technical contributions of this paper is novel mechanism for aggregating teachers' an- swers that are more immutable against larger noise without changing the consensus of the teachers. We show that our proposed method improves the performance of student model all measures.
PRELIMINARY
In this section, we briefly overview some background related to derive our new methods. We first in- troduce some basics in differential privacy, followed the ArgMax and noisy ArgMax mechanism.
2.1 DIFFERENTIAL PRIVACY
To satisfy the increasing demand for preserving privacy, differential privacy (DP) (Dwork er al., 2006) was proposed as a rigorous principle that guarantees provable privacy protection and has been extensively applied in both industrial and academic settings (Andrés et al., 2013; Friedman and Schuster, 2010; Team, 2017).
Let be a deterministic function that maps the dataset D the real numbers R. This deterministic function f. under the context of differential privacy, is called query function of the dataset D. For example, the query function may request the mean of feature in the dataset, the gender of each sample. The goal in privacy is to ensure that when the query function is applied on different but close dataset D'' the outputs of the query function are indistinguishable comparing that from the dataset D such that the private information of individual entries in the datasct can not be inferred by malicious attacks. Here, two datasets D and are regarded as adjacent datasets when they are identical except for one single item.
Informally speaking, a randomized data release mechanism for query function f is said to ensure DP if "neighboring" inputs induce similar distributions over the possible outputs of the mechanism. DP is particularly useful for quantifying privacy guarantees of queries computed over database with sensitive entries. The formal definition of differential privacy is given below.
2

---

Under review as a conference paper at ICLR 2020
Definition 1 (Differential Privacy Dwork (2011b, Definition 2.4)). A randomized mechanism M is (e, 8)-differentially private if for any adjacent data D, and D', ie D D'Il1 S 1, and any outpu
Y of M, we have
Pr(M(D) = s et Pr(M(D)) = Y +
(1)
If á = O, we say that M is e-differentially private. The parameter represents the privacy bud- get (Dwork, 201 la) that controls the privacy loss of M. larger value of e indicates weaker privacy protection.
Definition (Differential Privacy Dwork (2011b, Definition 2.4)). randomized mechanism M is (e, -ddifferentillly private if for any adjacent data D and D', ie || D'Il2 S 1, and any oulput Y of M, we have
c(o; Mua D, D'D & log Pr[M(aux, D) o]
Pr Pr[M(aux, D') ol*
The privacy loss random variable C(M, ouz, D, D') is defined as c(M((d); M, oux, D, D'),, ) i.e. the random variable defined by evaluating the privacy loss at outcome sampled from MMD).
From the notion of the DP, we know the sensitivity of the deterministic function f (i.e. a query function) about the dataset is important for designing the mechanism for the query function. For different noise mechanisms, it requires different sensitivity estimation. For example, the fn-nrrm sensirivity A of the query function f used for Gaussian mechanism which is defined as A2f = maxp.D' DD' [[f(D) f(D')ll, where D) and D' are two neighboring datasets. For the Lapla- cian mechanism, it uses the & -norm sensitivity Af for random noise sampling. In essence, when the sensitivity is smaller, it means that the query function itself is not very distinguishable given different datasets.
A general method for enforcing a query function f with the (c, difffrretta privacy is to ap- ply additive noise calibrated the sensitivity of f. general method for conveniently ensuring a deterministic query f to be the (r, () diffferrrel privacy is via perturbation mechanisms that add calibrated noise to the query's 's output (Dwork and Roth, 20;4;; Dwork al., 2010; Nissim et al., 2007: Duchi et al., 2013).
Theorem (Dwork and Roth (2014b)). If the fn-norm sensitivity of a deterministic function f is Af. have:
AS
My & ((D) Lap(
(3)
where My preserves (c, diiffferennntt privacy, and Lap(b) is the Laplacian distribution with loca- tion O and scale b.
Theorem 2 (Dwork and Roth (2014b)). the E--norm sensitivity of a deterministic function f is Aaf, we have:
MD) & F(D) + +N0, Defo)),
(4)
where NO, 022 is random variable obeying the Gaussian distribution with mean and standard deviation A2fa. The randomized mechanism My is (c, differentially private a 2 (21n(125//0) and e 1.
2.2 THE ARGMAX MECHANISM
For any dataset D = {Z 3x) The ArgMax Mechanism is widely used as query function when v(xx)) E N is a vector of counts of the dimension same to the number of classes d for sample Zg. This decision-making
mechanism similar to the softmax mechanism of the likelihood for each label, but instead of using the likelihood as the belief of each labels, the ArgMax mechanism uses the counts given by the teacher ensembles. Immediately, from the definition of the ArgMax mechanism, we know that the result given by the Arg mechanism is immutable against constant translation, i..
arg max ((xx)= = arg max 6(FE c)
0(z6, c)2 = (((x); if
i + arg max v((x)
(x(x)) +
otherwise
where we use subscript i index through the vector.
3

---

Under review as a conference paper at ICLR 2020
2.3 THE NOISY ARGMAX MECHANISM
Now, want ensure that the outputs of the given well-trained teacher ensembles are differen- tially private. A simple algorithm is to add independently generated random noise (e.g. independent Laplacian, Gaussian noise, etc.) to each count and return the index of the largest noisy count. This noisy ArgMax mechanism, introduced in (Dwork and Roth, 2014b), is (e, 0)-differentially private for the query given by the Arg mechanism.
OUR APPROACH
In this section, we introduce the specifics of our approach, which is illustrated in Figure 1. We first show the immutable noisy ArgMax mechanism, which is at the core of our framework. We then show how this property of immutable noisy ArgMax can be used in a differential private teacher-student training framework.
3.1 THE IMMUTABLE NOISY ARGMAX MECHANISM
One interesting observation from the Noisy ArgMax mechanism is that when the aggregated results from the teachers are very concentrated (i.e. most of the predictions agrees on certain class) and of high counts (i.e. large number of teachers), the result from the ArgMax will not change even under relatively large random noise. The aforementioned scenario is likely to happen in practice, if all the teacher models have relatively good performance on that task. This observation also hints us that can make the largest count much larger than the rest counts, we can achieve immutability with significant noise.
Let's define the data transformer as function that could convert a dataset into count vector below:
Definition 3 (Data Transformer). Given any dataset D, the output of data transformer is an integer based vector, such as F(D) E Zir), where r is the dimension of the vector.
Definition 4 (Distance-n Data Transformer). Given dataset D and data transformer function f. the distance n means the difference between the first and second largest counts given by the f(D) is larger than
Then we have the following theorem for immutable noisy ArgMax,
Lemma 1. [Noisy ArgMax Immutability] Given any dataset D, fixed noise perturbation vector and transformer function f. the noisy argmax of both f(D) is immutable while add sufficiently large constant into the current largest count of fDD).
Theorem 3. [Disferential private with Noisy ArgMax Immutabiliy]] Given any dataset D, its adja- cent dataset D', fixed noise perturbation vector and transformer function f. while Af 1 or Agf = 1) and the distance of f(D) is larger than 2, the noisy argmax of both f(D) and f(D') is immutable and the same while add sufficiently large constant into the current largest count.
The proof of the above theorems are provided the appendix. essense, when fed with neigh- boring dataset D', if the counts of f(D) is different by n. the output of the ArgMax mechanism remains unchanged. This immutability to the noise or difference in counts due the neighboring datasets, makes the output of the teacher ensemble unchanged, and thus maintain the advantage of higher performance accuracy using the teacher ensembles.
3.2 NEAR ZERO-COST QUERY FRAMEWORK
Now, we are ready to describe our near-zero-cos. (NZC) query framework. To protect the privacy of training data during learning, NZC transfers knowledge from an ensemble of teacher models trained on non-overlapping partitions of the data to a student model. Privacy guarantees may be understood intuitively and expressed rigorously in terms of differential privacy. The NZC framework consists of three key parts: (1) an ensemble of n teacher models, (2) an aggregation and noise perturbation and (3) training of student model.
4

---

Under review as a conference paper at ICLR 2020
Ensemble of teachers; In the scenario of teacher ensembles for classification, first partition the dataset = {(z,, [k)]k=1 into disjoint sub datasets {D;} and train each teacher P, separately on each set, where 1, ,t is the number of the dataset and is the number of the teachers.
Aggregation and noise perturbation mechanism: For each sample Ik, we collect the estimates of the labels given by each teacher, and construct count vector v(rx) E N where each entry by is given by Vj = (xx) = Vi = 1.... ..).. For each mechanism with fixed sample x, before adding random noise, we choose add sufficiently large constant c, then we have new count vector 6x, c). Our motivation is not protect æ from student, but protect the dataset D from the teacher. Basically, if we fix the partition, teacher training and a query x from student, then have data transformer f that transfer the target dataset D into a count vector. To be more clear, x and constant is used define the data transformer fe.e and we query T times, then we have T different data transformer based on each query x. Then, by using a data transformer, we can achieve a count vector ((2 c) (D..
Note that, we uses the following notation that ((z, c). also shorted as è, denotes the data transformer with adding a sufficiently large constant on the largest count, and v(x) denotes the count vector before adding sufficiently large constant.
We add Laplacian random noise to the voting counts ((x; c) to introduce ambiguity:
M(x) _ arg max (o(x, + Lap
where, y is a privacy parameter and Lap(b) the Laplacian distribution with location and scale b. The parameter y influences the privacy guarantee, which we will analyse later.
Gaussian random noise is another choice for perturbing 0(z e) to introduce ambiguity:
M(x) _ arg (6x c) + (0 A²f
where (0,,02) is the Gaussian distribution with mean 0 and variance o².
Intuitively, small y and large lead to strong privacy guarantee, but can degrade the accuracy of the pre-trained teacher model and the size of each label in the dataset, as the noisy maximum f above can differ from the true plurality.
Unlike original noisy argmax, our proposed immutable noisy argmax will not increase privacy cost with increasing the number of queries, if choose sufficiently large constant and large random noise by setting a very small for Laplacian mechanism (or a large a for Gaussian mechanism). Therefore, for each query, would costs almost zero privacy budget. By utilizing the property of immutable noisy argmax, we are allowed to have a very large number of queries with near zero privacy budget (setting + +oc and large random noise for the mechanism).
The final step is to use the returned information from the teacher to train student model. In previous works, due to the limited privacy budget, one only can query very few samples and optionally use semi-supervised learning to learn a better student model. Our proposed approach enables us do a large number of queries from the student with near zero cost privacy budget overall. Like training teacher model, here, the student model also could be trained with any learning techniques.
Student model:
PRIVACY ANALYSIS
We now analyze the differential privacy guarantees of our privacy counting approach. Namely, we keep track of the privacy budget throughout the student's 's training using the moments accountant (Abadi et al., 2016). When teachers reach strong quorum, this allows to bound privacy costs more strictly.
4.1 MOMENT ACCOUNTANT
To better keep track of the privacy cost, recent advances in privacy cost accounting. The moments accountant was introduced by (Abadi et al., 2016), building on previous work (Bun and Steinke, 2016; Dwork and Rothblum, 2016; Mironov, 2016). Definition 3.
5

---

Under review as a conference paper at ICLR 2020
Definition 5. Let M: D R be randomized mechanism and D, D' pair of adjacent databases. Let aux denote an auxiliary input. The moments accountant is defined as:
a.(
max (M; our, D. D').
aus d.d'
where (M; D, D'D log Blerp(AC(MM aux, D, D))] is the moment generating function of the privacy loss random variable.
The moments accountant enjoys good properties of composability and tail bound as given in Abadi al. (2016):
[Composabilityy- Suppose that mechanism M consists of sequence of adaptive mechanisms
M Mg, where M; IT'= R3 x D R,. Then, for any output sequence 01,..., 2 and
any X
(M(AD.,D) S Σ [.m. 10.00001......111111 91-, D, D').
where a. is conditioned on MM''s 's output being for < k.
[Tail bound] For any e 0, the mechanism M is (e, 8) diffferential privacy for
å = min
λe).
By using the above two properties, we can bound the moments of randomized mechanism based on each sub-mechanism, and then convert the moments accountant (e, d-dfffrrrretttaalll privacy based on the tail bound.
4.2 ANALYSIS OF OUR APPROACH
Theorem (Laplacian Mechanism with Teacher Ensembles). Suppose that on neighboring datubases D, 'D' the voting county v(a, c) disfer by at most A in each coordinate. Let Ma be the mechanism that reports arg max, v(x, c) + Lap((Af/)) Then Ma, satisfies (2 d'dfifferettial privacy. Moreover, for any l, aux, D and D',
all; aua, D,D") 27 21(((1+1)
(5)
For each query x, we use the aggregation mechanism with noise Lap(Af/7) which is (2%, DD-DP. 2T'n }, di-fifferlltial privacy (Dwork and Roth, 201 4a).
Thus over 7 queries, we get 24 + 2 choose very small for each mechanism with each query æ, which leads
In our approach, to very small privacy cost for each query and thus a low privacy budget. Overall, we cost near zero privacy budget while 7 O. Note that, 7 is very small number but is not exactly zero, and can set y to be very small that would result in a very large noise scale but still smaller than the constant e that added in é. Meanwhile, similar results are also used in PATE (Papernot et al., 2017), but both our work and PATE is based on the proof of (Dwork and Roth, 2014a), Note that, for neighboring databases D, D'. each teacher gets the same training data partition (that is, the same for the teacher with D and with D', not the same across teachers), with the exception of one teacher whose corresponding training data partition differs.
The Gaussian mechanism is based Renyi differential privacy, and details have been discussed in (Papernot et al., 2018). Similar to the Laplacian mechanism, we also get near zero cost privacy budget overall due to setting large a and an even larger constant c.
In the following, we show the relations between constant e with y and with a in two mechanism while Aʃ (or A2ʃ = 1) We first recall the following basic facts about the Laplacian and Gaussian distributions: if { ~ Lap(1/r) and (0, then for e > 0.
Pr(1c] 2 c) =
and
Pr([g] c) 2e 20

---

Under review as a conference paper at ICLR 2020
Now if each 1sy1 (resp. |5y < c) for j 1,.., L, then the arg max will not change. We can apply a simple union bound to get an upper bound on the probability of these events.
Pr( max
|ss c) Te
jul...,
and
Pr( max j=.....
Ey 2 c) S 2L 2n?
Thus to obtain a failure probability at most т, the Laplacian case we can take c 1 [log(L/7) and in the Gaussian case we can take c v 220² (2./2//
EXPERIMENTS
In this section, we evaluate our proposed method along with previously proposed models.
5.1 EXPERIMENTAL SETUP
We perform our experiments two widely used datasets on differential privacy: SVHN Netzer et al. (2011) and MNIST LeCun et al. (1998). MNIST and SVHN are two well-known digit image datasets consisting of 60K and 73K training samples, respectively. We the same data partition method and train the 250 teacher models as in Papernot es al. (2017). ). In more detail, for MNIST, we 10,000 samples the student dataset, and split it into 9,000 and 1,000 training and testing for experiment. For SVHN, we use 26,032 samples as the student dataset, and split it into 10,000 and 16,032 training and testing set. For both MNIST and SVHN, the teacher uses the same network structure as in Papernot et al. (2017).
Queries answered
Privacy bound
Accuracy Clean Votes
Dataset
Aggregator
Student
Ground Truth
LNMax (7=
100
2.04
63.5%
LNMax (7=20)
1,000
8.03
89.8%
MNIST
LNMax (7=20)
5,000
8.03
94. 1%
94.5%
98.1%%
LNMax (7=20)
9,000
8.03
93.4%
NZC (c = 1et00 y 1e
9,000
R
95.1%
NZC (5 teachers only)
9,000
R
97.8%
97.5%
LNMax (7=20)
500
3.04
54.0%
LNMax (7=20)
1,000
8.19
64.0%
LNMax (n=20)
5,000
8.19
79.5%
85.8%
SVHN
89.3%
LNMax (0=20)
10,000
8.19
84.6%
(eC = 1e y 1)
10,000
0
85.7%
N3C teachers only)
10,000
87.1%
87.1%
Table 1: Classification accuracy and privacy of the students. LNMax refers the method from
Papernot et al. (2017). The number of teachers is set to 250 unless otherwise mentioned. We set 8 = 10-5 to compute values of E (to the exception of SVHN where 10-5). The baselines refers to student that are trained from the noiseless votes from all teachers. Ground truth refers to student that are trained with ground truth query labels.
MNIST
SVHN
LNMax
NZC
Clean 94.37%
LNMax
NZC
Clean 88.06%
93.02%
94.33%
87.11%
88.08% %
Table 2: Label accuracy of teacher ensembles when compared to the ground truth labels from various methods using 250 teachers. Clean denotes the aggregation without adding any noise perturbation.
5.2 RESULTS AND DISCUSSIONS
We primarily compare with Paperno et al. (2017), which also employs teacher student framework and has demonstrated strong performance. We did not compare with work from Papernot et al. (2018) because the improvements
the privacy budget and the improvement of student

---

Under review as a conference paper at ICLR 2020
3002
Parcentagge of Total sammoo
MIST
256
(a) Number of teachers versus Per- formance
(b) Distance-n versus Qualified Samples with 250 Teachers
(c) Distance-2 Qualified Samples versus Number of Teachers
Figure 2: (a) shows the trade-off between number of teachers and the performance of the teacher ensemble; (b) shows the percentage of qualified sample which satisfy the distance-n in whole dataset when using 250 teachers; (c) shows the percentage of distance-2 qualified samples over the dataset.
performance on tasks are marginal.. We used implementation from the official Github", however, we are unable to reproduce the semi-supervised results. Therefore, the following, we compare the result under fully supervised setting for both approaches.
The results on MNIST and SVHN datasets are shown in table 1. It clear that the proposed approach achieves both better accuracy and much better privacy cost. In particular, the results are very close to the baseline results, where the student is trained by using the non-perturbed votes from the teacher ensembles. The main reason is that NZC is more robust against the random perturbations for most of the queries, which helps the student to obtain better quality labels for training. We also achieved strong privacy cost, because our approach allows us to use very large noise scale, as long as the constant с is set to a proper large value. To check if the above intuition is true, we calculate the number of correctly labeled queries from the teacher ensembles, and the result is shown in table 2. It is quite clear that our approach is more robust against noise perturbation as compared to the previous approach.
The number of teachers would have a significant impact on the performance of the student, as the teachers were trained on non-overlapping split of the data. The more number of teachers, the less data a teacher has to train. This leads to less accurate individual teachers, and thus less likely to have correct vote for the query. As can be seen from Fig 2a. the performance of the teacher ensembles decreases as the number of teachers increases. This is more prominent for more challenging datasets (e.g. SVHN performance drops more significantly as compared to MNIST). We would like note that, although the number of qualified samples increases as the number of teachers increase (see Fig 2c), is the cost of increasing the wrongly labeled queries, since the total accuracy of teachers has decreased. Because of this, it is likely to result in worse student performance. However, the previous approach such as PATE (Papernot el al., 2017) or Scale PATE (Papernot et al., 2018) requires large number of teachers due privacy budget constraints. Our approach does not have this limitation. Therefore, we experimented with fewer number of teachers and the results are shown in table 2. The results from using less teachers improved significantll, and approaches closer to the performance when the training student with the ground truth.
6 RELATED WORK
Differential privacy is increasingly regarded as standard privacy principle that guarantees provable privacy protection (Beimel el al., 2014). Early work adopting differential privacy focus on restricted classifiers with convex loss (Bassily al., 2014; Chaudhuri el al., 2011; Hamm al., 2016: Pathak et al., 2010; Song et al., 2013). Abadi et al. (2016) proposed DP-SGD, new optimizer by carefully
'The open source implementation given in https://gituh..com/// com/enssrffooo///rvvayy only generates table the original paper from Papernot et al. (2018) 8), which does not provide any model performance. hhtps://gtuu..co//eere http://ghthhb.oooommeessso///w//
8

---

Under review as a conference paper at ICLR 2020
adding random Gaussian noise into stochastic gradient descent for privacy- preserving for deep learn- ing approaches. At each step of DP-SGD by given a set random of examples, it need to compute the gradient, clip the l2 norm of each gradient, add random Gaussian noise for privacy protection, and updates the model parameters based on the noisy gradient.
Intuitively, DP-SGD could be easily adopted with most existing deep neural network models built on the SGD optimizer. Based on DP-SGD Agarwal et al. (2018) applies differential privacy on dis- tributed stochastic gradient descent achieve both communicate efficiency and privacy-preserving. McMahan et al. (2017) applies differential privacy to LSTM language models by combining feder- ated learning and differential private SGD to guarantee user-level privacy.
Papernot et al. (2017) proposed a general approach by aggregation of teacher ensembles (PATE) that uses the teacher models' aggregate voting decisions to transfer the knowledge for student model training. Our main framework is also inspired by PATE with modification to the aggregation mech- anism. In order solve the privacy issues, PATE adds sarffully-caiibrtted Laplacian noise on the aggregate voting decisions between the communication. To solve the scalability of the original PATE model, Papernot el al. (2018) proposed an advanced version PATE by optimizing the voting be- haviors from teacher models with Gaussian noise. PATE-GAN Jordon el al. (2018) applies PATE to GANs to provide privacy guarantee for generate data over the original data. However, existing PATE Scale PATE have spend much privacy budget and train lots of teacher models. Our new approach overcomes these two limitations and achieved better performance on both accuracy and privacy budget. Compared with PATE and our model, DP-SGD is not teacher-student model.
CONCLUSION
We propose a novel voting mechanism- - the immutable noisy ArgMax, which enables stable output with tolerance to very large noise. Based on this mechanism, we propose simple but effective method for differential privacy under the teacher-student framework. Our method benefits from the noise tolerance property of the immutable noisy ArgMax, which leads to near cost privacy budget. Theoretically, we provide detailed privacy analysis for the proposed approach. Empirically, methods outperforms previous methods both in terms of accuracy and privacy budget.
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, CCS '16, pages 308-318, 2016.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMa- han. cpsgd: Communication-efficenn and differentially-prinn prrivvate distributed sgd. In Advances in Neural Information Processing Systems, pages 7564-7577 2018.
Babak Alipanahi, Andrew Delong, Matthew Weirauch, and Brendan J Frey. Predicting the se- quence specificities of dna-and ma-binding proteins by deep learning. Nature biotechnology, 33(8):831,, 2015.
Miguel E. Andrés, Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. deeo-nnistinnuishaalltty differential privacy for location- based systems. In Proceedings of the 2013 ACM SIGSAC conference on Computer &#38; communications security, CCS 13, pages 901-914, New York, NY, USA, 2013. ACM.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Differentially private empirical risk minimiza- tion: Efficient algorithms and tight error bounds. arXiv preprint aoXiv:1405, 1405.7085, 2014.
Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds the sample complexity for private learning and private data release. Machine Learning, 94(3):401- 437, 2014.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 126MMr):1069-1100 2011.

---

Under review as a conference paper at ICLR 2020
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprins arXiv:1810.04800 2018.
John Duchi, Michael Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In Proc. of IEEE Foundations of Computer Science (FOCS), 2013.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9:21 12107, 2014.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 933-4)211 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 5 Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2010.
Cynthia Dwork. Differential Privacy, pages 338-340. 2011.
Cynthia Dwork. A firm foundation for private data analysis. Communications of the ACM, 54(1):86 95, 2011.
Arik Friedman and Assaf Schuster. Data mining with differential privacy. In Proceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining, pages 493-502. ACM, 2010.
Qingyuan Gong, Yang Chen, Xinlei He, Zhou Zhuang. Tianyi Wang. Hong Huang, Xin Wang, and Xiaoming Fu. Deepscan: Exploiting deep learning for malicious account detection in location- based social networks. IEEE Communications Magazine, (6(11):21-27, 2018
Jihun Hamm, Yingjun Cao, and Mikhail Belkin. Learning privately from multiparty data. In Inter- national Conference Machine Learning, pages 555-563, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
James Jordon, Jinsung Yoon, and Mihaela van der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. 2018.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Geoffrey Hinton. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2778-22,,, 1998.
Xindi Ma, Jianfeng Ma, Hui Li, Qi Jiang. and Sheng Gao. Pdlm: model on cloud with multiple keys. IEEE Transactions on Services Computing, 2018.
deep learning
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint 1Xiv:1710.006633 2017.
Donald Michie, David Spiegelhalter, CC Taylor, et al. Machine learning. Neural and Statistical Classification, 13, 1994.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, and Bo Wu Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In Proceedings of the 24th Interna- tional Conference on Neural Information Processing Systems, NIPS '11 pages 1-9, 2011.
Ulfar Erlingsson Ian Goodfellow Kunal Talwar Nicolas Papernot, Martin Abadi. Semi-sur cumi-supervised knowledge transfer for deep learning from private training data. In 5th International Conference on Learning Representations (ICLR), 2017.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty- anmual ACM symposium on Theory of computing, pages 74. ACM, 2007.
10

---

Under review as a conference paper at ICLR 2020
Nicolas Papernot, Martin Abadi, Ulfar Erlingsson, lan Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. In 5th International Conference Learning Representations, ICLR 17. 2017.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Ulfar Er- lingsson. Scalable private learning with pate. In 6th International Conference Learning Rep- resentations, ICLR '18, 2018.
Manas Pathak, Shantanu Rane, and Bhiksha Raj. Multiparty differential privacy via aggregation of locally trained classifiers. In Advances in Neural Information Processing Systems, pages 1876- 1884, 2010.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan Protecting classifiers against adversarial attacks using generative models. arXiv preprint arXiv: 1805.06055 2018.
David Silver, Julian Schrittwieser, Karen Simonyan, Toannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Mastering the game of go without human knowledge. Nature, 550(7676)3554, 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, pages 245-248. IEEE, 2013.
Apple Differential Privacy Team. Learning with privacy scale, 2017.
Zheng Yan. Mobile phone behavior. Cambridge University Press, 2017.
A APPENDIX
Lemma 1. [Noisy ArgMax Immutability] Given any dataset D, fixed noise perturbation vector and a transformer function f. the noisy argmax of both (DD is immutable while we add a sufficiently large constant into the current largest count of fDD).
Proof. First, let us recall some facts discussed in the main paper. We first recall the following basic facts about the Laplacian and Gaussian distributions: if Ç ~ Lap(1/n) and & ~ N/0 a²), then for 0,
Pr(1 2 c) =
and
2 Pr([[ c) 2e 20
Now if each |4y1 c (resp. K c) for j 1, ..., L, then the arg max will not change. We can apply a simple union bound to get an upper bound on the probability of these events.
Pr( max ISg c) S Le I.....
and
Pr( max I....h
|5,1 2 c) < 2Le 2.2
Thus to obtain a failure probability at most 7, in the Laplacian case we can take 1 loog(L/T) and in the Gaussian case we can take
log(L/TT)
Since have sufficiently large constant minus any sampled noise from either Gaussian or Laplacian distribution is larger than 0 with 1 probability, where we could set 7 as a very small number which close to 0. Then, the largest count of (D) adds positive number which not change the argmax result.
20 or >> 4 LoT)( then
11

---

Under review as a conference paper at ICLR 2020
Theorem 3. [Differential private with Noisy ArgMax Inmusaability] Given any dataset D, its adja- cent dataset D', fixed noise perturbation vector and a transformer function f. while A 1 or 22f = 1) and the distance of f(D) is larger than 2. the noisy argmax of both f(D) and f(D") is immutable and the same while we add a sufficiently large constant into the current largest count.
Proof. First, we have Af (or A2f 1) and the distance of fD) larger than 2. For any adjacent D', arg max J(D) arg max J(D') is immutable, since I(D") can only modify count due to the Aʃ not change the argmax. Assume the argmax will be changed, let use f(D),- presents the largest count and f(D), presents the second largest count:
However, the distance is larger than 2, then any modification of S(D') would
( +1
f(D))--(D)} < 2,
which is conflict the distance- of fDD for any cases.
Then prove that f(D) and f have the same argmax. By using Lemma 2, that after adding a sufficiently large count and noise perturbation will also not change the argmax information for both (D) and f(D'). Then, we have the same argmax return over any D, D' and DP also holds.
12


Reviews:
[{"review_id": "SyeKgE2JqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "To improve the privacy-utility tradeoff, this manuscript proposes a voting mechanism used in a teacher-student model, where there is an ensemble of teachers, from which the student can get gradient information for utility improvement. The main idea of the proposed approach is to add a constant C to the maximum count collected from the ensemble, and then noise is furthermore added to the new counts. I can understand that by adding the large constant C, the identity of the maximum count could be preserved with high probability, leading to a better utility on the student side. However, equivalently, this could also be understood as that the noise is not added uniformly across all the counts, but instead a relatively smaller noise is added to the maximum count. Hence it is not clear to me whether the final composition will still be differentially private?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HkxrciCwtB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 paper proposes an improvement on the PATE framework for achieving near-zero privacy cost, and showed privacy analyses and experimental evaluations of the proposed method. \n\nThe proposed method can be technically flawed. Adding a consent to the max will not guarantee privacy unless you account for the privacy cost for testing whether the distance of f(D) is larger than 2. This is because the distance of f(D) is data-dependent and revealing it violates privacy. Since the whole privacy analysis of PATE is based on the privacy guarantee of the Noisy ArgMax, the epsilon calculated here is voided.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "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."}, "extra_text": {}}, {"review_id": "H1eUlfF_tH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 studies the teacher ensembles setting for differentially private learning. In this setting, each teacher holds part of the training set and trains a local model. The student uses unlabeled examples to query teacher model. Then the student trains a model from scratch using the examples labeled by teachers.\n\nIn order to make the labeling process differentially private, previous work uses noisy argmax mechanism. Each class of label is assigned with a count number. The student first queries the same example to multiple teachers. To guarantee differential privacy, the counts are perturbed by noise before releasing. Then, because of the post-processing property of differential privacy, the argmax operator on such noisy counts are still differentially private.\n\nThis paper proposes to add a constant c to the largest count before perturbing and releasing the counts. The authors argue this would improve the accuracy of the noisy argmax operator and yield the same privacy loss as previous approach. However, adding a constant c would increase the sensitivity and therefore degenerates the privacy guarantee. The added noise cannot guarantee the privacy if all others are the same as previous work. To see this clearer, for example, if c=0, then one sample point can at most change the count by 1. If c>0, then one sample point can change the count by 1+c. Because of this, the proposed method cannot guarantee the amount of differential privacy as the paper claimed.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a differentially private mechanism, called Noisy ArgMax, for privately aggregating predictions from several teacher models. There is a consensus in the discussion that the technique of adding a large constant to the largest vote breaks differential privacy. Given this technical flaw, the paper cannot be accepted.
Decision: Reject