Improving Differentially Private Models with Active Learning
Authors: Zhengli Zhao
Nicolas Papernot
Sameer Singh
Neoklis Polyzotis
Augustus Odena
Venue:  (2020)
Keywords: Differential Privacy
Active Learning

Abstract: Broad adoption of machine learning techniques has increased privacy concerns for models trained on sensitive data such as medical records. Existing techniques for training differentially private (DP) models give rigorous privacy guarantees, but applying these techniques to neural networks can severely degrade model performance. This performance reduction is an obstacle to deploying private models in the real world. In this work, we improve the performance of DP models by fine-tuning them through active learning on public data. We introduce two new techniques - DiversePublic and NearPrivate - for doing this fine-tuning in a privacy-aware way. For the MNIST and SVHN datasets, these techniques improve state-of-the-art accuracy for DP models while retaining privacy guarantees.

Under review as a conference paper at ICLR 2020
IMPROVING DIFFERENTIALLY PRIVATE MODELS WITH ACTIVE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Broad adoption of machine learning techniques has increased privacy concerns for models trained sensitive data such medical records. Existing techniques for training differentially private (DP) models give rigorous privacy guarantees, but applying these techniques neural networks can severely degrade model performance. This performance reduction is an obstacle to deploying private models in the real world. In this work, we improve the performance of DP models by fine-tuning them through active learning on public data. We introduce two new techniques- - DIVERSEPUBLIC and NEARPRIVATE in privacy-awars way. For the MNIST and SVHN datasets, these techniques improve state-of-the-art accuracy for DP models while retaining privacy guarantees.
for doing this fine-tuning
INTRODUCTION
Privacy concerns surfaced with the increased adoption of machine learning domains like healthcare (LeCun et al.) 2015). One widely adopted framework for measuring privacy characteristics of randomized al aggorithms, such as machine learning techniques, is differential privacy (Dwork et al., 2006). Abadi et al. (2016) introduced an algorithm for differentially private stochastic gradient descent (DP-SGD), which made it feasible to scale differential privacy guarantees to neural networks. DP-SGD is the de facto algorithm used for training neural networks with privacy guarantees.
There is, however, a crucial problem for models with a large number of parameters: it is difficult to achieve both non-trivial privacy guarantees and good accuracy. The reasons for this are numerous and involved, but the basic intuition is that DP-SGD involves clipping gradients and then adding noise to those gradients. However, gradient clipping has increasing relative effect the number of model parameters grows. This reduces the applicability of differential privacy to deep learning in practice, where strong performance tends to require large number of model parameters
In this work, we propose method to mitigate this problem, making DP learning feasible for modern image classifiers. The method is based the observation that each DP-SGD update consumes privacy budget in proportion to the quotient of the batch size and the training-set size. Thus, by increasing the number of effective training examples, we can improve accuracy while maintaining the same privacy guarantees. Since obtaining more private training samples will generally be nontrivial, we focus on using 'public' data to augment the training set. This involves assuming that there will be unlabeled public data that is sufficiently related our private data to be useful, but think this is a reasonable assumption to make, for two reasons: First, it is an assumption made by most of the semi-supervised learning literature (Oliver et al. 2018). Second, one of our techniques will explicitly address the situation where the "sufficiently related' clause partially breaks down.
In summary, contributions
We introduce an algorithm (DivERSEPUBLiC) ) select diverse representative samples from a public dataset to fine-tune a DP classifier.
For example, the best performing CIFAR-10 classifier from Zagoruyko & Komodakis (2016) has 32.5 million parameters, while the private haseline we describe Section has about thousand.
2 If there is labeled public data, the situation is even better, but this likely to be rare and is not the setting consider here.

---

Under review as a conference paper at ICLR 2020
We then describe another algorithm (NEARPRIVATE that pays privacy cost to reference the private training data when querying the public dataset for representative samples.
We establish new state-of-the-arr results on the MNIST and SVHN datasets by fine-tuning DP models using simple active learning techniques, and then improve upon those results further using DIVERSEPUBLIC and NEARPRIVATE.
We open source all of our experimental code 8
BACKGROUND
2.1
DIFFERENTIAL PRIVACY
We reason about privacy within the framework of differential privacy (Dwork et al. 2006). In this paper, the random algorithm we analyze is the training algorithm, and guarantees are measured with respect the training data.
Informally, an algorithm is said to be differentially private if its behavior is indistinguisaable on pairs of datasets that only differ by one point. That is, an observer cannot tell whether particular point was included in the model's training set simply by observing the output of the training algorithm. Formally, for a training algorithm A to be (s, didiferrennt private, we require that satisfies the following property for all pairs of datasets (d, d') differing in exactly one data point and all possible subsets Range(A):
Pr[A(d) E S) S e Pr[A(d") E +
where ò is a (small) probability for which we tolerate the property not to be satisfied. The parameter e measures the strength of the privacy guarantee: the smaller the value of E is, the stronger the privacy guarantee is.
This guarantee is such that the output of differentially private algorithm can be post-prooee post-processed at no impact to the strength of the guarantee provided. In case privacy needs to be defined at different granularity than invidividual training points, the guarantee degrades by a factor which, naively, the number of points that are included in the granularity considered. See Dwork et al. (2014a) for further information.
2.2 DIFFERENTIALLY PRIVATE STOCHASTIC GRADIENT DESCENT (DP-SGD)
Building on earlier work (Chaudhuri al. 2011 Song et al. 2013 Abadi al. (2016) introduce variant of stochastic gradient descent to train deep neural networks with differential privacy guarantees. Two modifications are made vanilla SGD. First, gradients are computed on a per-example basis and clipped to have maximum known & norm. This bounds the sensitivity of the training procedure with respect to each individual training point. Second, noise calibrated to have a standard deviation proportional to this sensitivity is added to the average gradient. This results in training algorithm known as differentially private SGD (DP-SGD). Unfortunately (as discussed in Section []. DP-SGD does not perform well for models with large parameter counts, which motivates the improvements proposed in the next section.
3 IMPROVING DIFFERENTIALLY PRIVATE MODELS WITH ACTIVE LEARNING
This paper introduces the following high-level process to improve the performance of an existing DP classifier: First, find a public insensitive dataset containing relevant samples. Second, carefully select a subset of public samples that can improve the performance of the classifier. Third, fine-tune the existing classifier on the selected samples with labels. We want to perform the selection and the fine-tuning in way which does not compromise the privacy guarantees of the existing classifier.
The first step can be done using domain knowledge about the classifier, e.g., utilizing relevant public genomic datasets for a DP classifier of genomics data. We assume standard fine-tuning techniques for the last step. Therefore, the problem boils down to efficiently selecting samples from the public dataset while preserving privacy. We also assume a limit on the number of selected samples. This
'RRL blinded for anonymity.
2

---

Under review as a conference paper at ICLR 2020
Algorithm 1 The DIVERSEPUBLIC Algorithm
Input: Map with privacy cost Edp. Duuhlic. Niaheled, k > Maheled, P. Neluster, Neach
Output: Map fine-tuned on selected public data with the same privacy cost Edp
E Euublicc 5- (Ppppup
> Compute "embeddings" of public data Perform PCA on embeddings and get first p PCs
PCA(Fppublic: P PCA Pppuhlic p)
Spublic &- P x DelletUncertain(PPubrlee public; k)
b. Project k most 'uncertain' public data onto PCs
ClusterCenters + K-Means(Spuhlid
D Cluster projected embeddings to get Veluster clusters
Diaheled f 0
for 1 1 N Netuster do
Label Newch data points from each cluster
Dinbeled = Diabeled U ConntterrPoissuuuteeCeCCaat
end for M <- Fine FineTTuneMMaa Diubelea)
limit relevant when the samples are unlabeled, which case it controls the cost of labeling (e.g.. hiring human annotators to process the selected samples).
We introduce two active learning algorithms, DIVERSEPUBLIC and NEARPRIVATE, for sample- selection. These algorithms make different assumptions about access to the private training data but are otherwise drop-in replacements in the end-to-end process.
3.1 PROBLEM STATEMENT AND BASELINE METHODS
We are given a differentially private model Map trained and tested on private sensitive data Prain and Diea respectively. The privacy cost of training Map on Dimin is Sup (we omit 5 for brevity in this paper, but it composes similarly). And we have an extra set of public insensitive unlabeled data pubblcc which can be utilized to further improve Map- Given the number of extra data Ninheled that are allowed to request labels for, and the total privacy budget Fimit of the improved model Māp. we want to efficiently pick Duseeldd C Puuhiic where [Diaheled| = Nahheed using which we can fine-tune Map to Map of better performance on Drest- The simplest baseline method will use is choose Niabeled 'random" samples out of Ppubiic for fine-tuning. The other baseline that we use is Uncertain Sampling (Settles 2009), according to either the 'entropy' of the logits or the 'difference' between the two largest logits. These widely used active learning methods and serve strong baselines.
3.2 THE DIVERSEPUBLIC METHOО
The baseline methods may select many redundant examples to label. To efficiently select diverse representative samples, we propose the DIVERSEPUBLIC method, adapted from clustering based active learning methods (Nguyen & Smeulders 2004). Given DP model Map of cost Edp. obtain the 'embeddings' (the activations betore the logits) Epublic of all D public and perform PCA on Epublic as is done in Raghu et al. (017). Then select number (more than Niaheled) of uncertain points (according to, e.g., the logit entropy of the private model) from Dpublic. project their embeddings onto the top few principal components, and cluster those projections into groups. Finally, we pick a number of samples from each representative group up to Ninbeled in total and fine-tune the DP model with these Disheled- Though this procedure accesses Map. it adds nothing Edp- since there is no private data referenced and the output of DP models can be post-processed at no additional privacy cost. It can be applied even to models for which we cannot access the original training data Algorithm|] 1 presents more details of the DIVERSEPUBLIC method.
3.3 THE NEARPRIVATE METHOD
The DIVERSEPUBLIC method works well under the assumption that D Dpubiic has the same distribution as Drain- However, this may not be reasonable assumption in general (Oliver et al.) 2018). For instance, there may be subset of Doublic about which our pre-trained model has high uncertainty but which cannot improve performance if sampled. This may be because that subset contains corrupted data or it may be due simply to distribution shift. In order to mitigate this issue, we propose to
c.g, models published repository like TeoworFlow Hub: htttp::/www..eenoorff orrg///
3

---

Under review as a conference paper at ICLR 2020
Algorithm 2 The NEARPRIVATE Algorithm
Input: Map with privacy cost Edp. Duublic. Niaheled, k > Maheled P, Drnin EdpPCA and Esupport
Output: Mi fine-tuned on selected public data with privacy cost Eap + EdpPCA + Ssupport
Emain 6- Map [Dmiin]-1]]
> Compute 'embeddings" of private data
P DP-PCA Purain: EdpPCA, P)
D. Perform DP-PCA on embeddings and get first p PCs
Stain + P x SelectUncertain/ Diraio k)
D Project k most 'uncertain' private data onto PCs Project & most 'uncertain' public data onto PCs
Spablic t- P SelectUncertain(D puublic k))
NeighborCounts + 0
for E Swain do Increment Neighbbooni,hh Nearest Spublie)
In PC-spece, assign each private point to exactly one public point
end for
for b E Spuhlic do
> Compute support with Laplacian noise for each public data point N Nuupport (b) f- NeighborCounts(() + LapplaceNoise(//aupol
end for
D Diaheled f wwwtgmaaaPinttsNupppaaar
> Label Ninbeled data points of the highest Naupport
Map FineTTune (MMap Diubeled)
check query points against our private data and decline to label query points that are too far from any training points (in sngrected-embeddinng spacee.......... But doing this check while preserving privacy guarantees nontrivial, since it involves processing the private training data itself in addition to Map. Given a DP model of cost Edp. we obtain the embeddings Eqain of all Dirain and perform differentially private PCA (DP-PCA) (Dwork et al. 2014b) on Esraio at a privacy cost of EdpPCA We select a number of uncertain points from both Perain and public. Then in the space of low dimensional DP-PCA projections, we assign each uncertain private example to exactly one uncertain public example according to Euclidean distance. This yields, for each uncertain public example, count Nupport of 'nearby' uncertain private examples. Finally, we choose Niabeled points with the largest values of Namponn
from the uncertain public data. This sampling procedure differentially private with cost support due to the Laplace mechanism (Dwork et al. (0014)). The total privacy cost of NEARPRI VATE is composed of the budgets expended to perform each of the three operations that depend on the private data: Edp + EdpPCA + support More details in Algorithm
4 EXPERIMENTS
We conduct experiments on the MNIST (LeCun et al. 1998) and SVHN (Netzer et al., 2011) data sets. These may be seen 'toy' data sets in the object recognition literature, but they still challenging for DP object recognizers. In fact, at the time of this writing, there are no published examples of differentially private SVHN classifier with both reasonable accuracy and non-trivial privacy guarantees. The baseline we establish in Section 4.2 is thus a substantial contribution by itself. For both datasets, we use the same model architecture as in the Tensorflow Privacy tutorials We obtain Map by training on Drrain via DP-SGD (Abadi et al. (0166). Unless otherwise specified, we always aggregate results over 5 runs with different random seeds and use error bars to represent the standard deviation. We use the implementation of DP-SGD made available through the TensorFlow Privacy library (McMahan et al. 2018) with d = 10-5
4.1 EXPERIMENTS ON MNIST
We conduct our first set of experiments the MNIST (LeCun al.) 1998) dataset. We use the Q-MNIST (Yadav& & Bottou 2019) dataset as our source of public data. In particular, we use the 50,000 examples from the Q-MIIST dataset that are reconstructions of the lost MNIST testing digits. We perform a hyperparameter optimization and find a baseline model with higher accuracy (97.3% at Eap 3.0, and 97.5% at ddp 3.2) than what is reported as the current of-te-of-the-art in the Tensorflow Privacy tutorial's README file (96.6% at Edp = 3.0).
Figure shows results of our DIVERSEPUBLIC method compared with basclines. Starting from a checkpoint of test accuracy 97.5% (Cap = 3.2), our method can reach 98.8% accuracy with 7,000
TTutorials for TensorFlow Privacy found at: https: http//gittttteet httuut/ccmmmensooffoo/////p////p
4

---

Under review as a conference paper at ICLR 2020
0.9
3.905
1445 arrumyy
tost accunccy
0.000
2,800
PiverspPublle difference
NearPrivate
entrapy
DiversePublic
random
checkpoint
0.970
checkpaint
2,70
checkpoint
2003
4000
0..0
5000
10000
2.00
4000
6000
B00C
10000
number eetra paints
number mottra points
(a) DIVERSEPUBLIC vs baselines
(b) NEARPRIVATE vs DIVERSEPUBLIC
Figure 1: MNIST experiments. All plots show test-set-accuracy the number of extra points labeled. Left: Comparison of our DIVERSEPUBLIC technique with the active learning baselines described above. All models fine-tuned starting from the same baseline ('checkpoint I': test accuracy 97.5% and Edp = 3.2). Active learning improves the performance of the DP-model much as 98.8% in the best case with no increase privacy cost. Right: Comparison of our NEAR PRIVATE technique with the DIVERSEPUBLE technique. Since we spent SApPCA + Esppport = 1.0 on the NEARPRIVATE technique,
fine-tune the NEARPRIVATE model from 'checkpoint O' with privacy cost Edp = 2.2. Thus, both lines have the same privacy cost (Elimit = 3.2), regardless of the number of extra points used.
extra labels. The DIVERSEPUBLIC method yields higher test accuracy than other active learning baselines in the low-query regime, and performs comparably in the high-query regime.
In Figure lb compare NEARPRIVATE against DIVERSEPUBLIC Since NEARPRIVATE adds extra privacy cost, we have to take special care when comparing it to DIVERSEPUBLIC. Therefore, we fine- tune from starting checkpoint at test accuracy 97.0% with lower privacy cost (Cdp 2.2) and make sure its total privacy cost (Ctimi 3.2) in the end the same as the cost for the DIVERSEPUBLIC model. For this reason, NEARPRIVATE takes some number of labeled data points to 'catch up' to DIVERSEPUBLIC for the same DP cost - in this case 2,000. When Niabeled is large enough, NEARPRIVATE outperforms all other methods. This shows that accessing the original training data in privacy-awar way can substantially improve performance.
4.2 EXPERIMENTS ON SVHN
We conduct another set of experiments on the SVHN (Netzer et al. 2011) data. We use the set of '331,131 additional, somewhat less difficult samples' model trained with DP-SGD on the SVHN training set performs quite poorly, we have opted to first pre-train the model rotated images of D public predicting only rotations as in Gidaris et al. (2018).
source of public data. Since baseline
Broadly speaking, the results presented in Sggureeare similar to MNIST results, but three differences stand out. First, the improvement given by active learning the baseline private model is larger. Second, the improvement given by DIVERSEPUBLIC over the basic active learning techniques also larger. Third, NEARPRIVE VATE actually underperforms DIVERSEPUBLIC this case. We hypothesize that the first and second results are due to there being more "headroom' in SVHN accuracy than for MNIST, and that the third result stems from the reported lower difficulty of the extra SVHN data. In the next section, we examine this phenomenon further.
4.3 EXPERIMENTS WITH DATASET POLLUTION
We were intrigued by the perorrnerf of NEARPRIVATE relative to DIVERSEPUBLIC on SVHN. We wondered whether it due to the fact that SVHN and its extra data violate the assumption built into NEARPRIVATE - namely that we need to query the private data to 'throw out' unhelpful public data. Indeed, the SVHN website describes the extra set 'somewhat less
5

---

Under review as a conference paper at ICLR 2020
0622 SCUrSyy
DiverssPublic
difference
NeatPrivale
entropy
DiversePuble
random
checkpoint
chreckpcint
chec couint
(a) DIVERSEPUBLIC vs baselines
(b) NEARPRIVATE DIVERSEPUBLIC
Figure 2: SVHN experiments. Left: Comparison of our DIVERSEPUBLIC technique with the active learning baselines. All models are fine-tuned starting from the same baseline ( ('checkpoint I test ac- curacy 75.0% and Sdp = 6.0). Active learning improves the performance of the DP-model to as much as 85% the best case with no increase in privacy cost. Recall also that the 75.0% number is itself bascline established in this paper. Right: Comparison of NEARPRIVATE with DIVERSEPUBLIC The setup here analogous to the one in the MNIST experiment, but DIVERSEPUBLIC performs better in this case. Since we spent CdpPCA + Eupport = 1.0 on NEARPRIVATE, we fine-tune from "checkpoint O' with test accuracy 73.5% 5% and Edp 5.0.
difficult' than the training data. To this hypothesis, we designed new experiment check if NEARPRIVATE can actually select more helpful samples given a mixture of relevant data and irrelevant data as 'pollution'. We train the DP baseline with 30,000 of the SVHN training images, and treat combination of another 40,000 SVHN training images and 10,000 CIFAR-10 (Krizhevsky et al. 2009) training images as the extra public dataset. These CIFAR- 10 examples act as the unhelpful public data that would hope NEARPRIVATE could learn to discard. As shown in Figure all baselines perform worse than before with polluted public data. DIVERSEPUBLIC does somewhat better than random selection, but not much, achieving a peak performance improvement of around 1%. On the other hand, the difference between NEARPRIVAT and DIVERSEPUBL. is more substantial, 2% accuracy in some cases. This is especially interesting considering that DIVERSEPURLIC actually performed better in the results of Section 4.2 Broadly speaking, the results support our claim that NEARPRIVATE VAATE helps more relative to DIVERSEPUBLIC when there 'unhelpful' data in the public dataset. This is good to know, since having some unhelpful public data and some helpful public data seems like a more realistic problem setting than the one in which all public data useful.
5 ABLATION ANALYSES
In order to better understand how the performance of DIVERSEPUBLIC and NEAR affected by various hyper- ppprr-parameters, we conduct several ablation studies.
5.1 How DO CLUSTERING HYPER-PARAMER PARAMETERS AFFECT ACCURACY?
For DIVERSEPUBLIC there are two parameters that affect the number of extra data points labeled for fine-tuning: the number of clusters we form (Nelster) and the number of points we label per cluster (Nesch). We write Nisbeled Neluster Neuch- To study the relative effects of these, we conduct the experiment depicted in Figure 4a In this experiment, we fine-tune the same DP MNIST model (test accuracy 97% at ddp = 2.2) with varying values of Neluster and Neach We vary Netuster from 100 to 500, which is depicted on the -xaxi.. We vary Nench from 5 to 20, with each value depicted as different line. The general trend one of diminishing returns on extra labeled data, as would be predicted by Hestness et al. (2017). We do not notice strong correspondence between final test accuracy at fixed number of extra labels and the values of N Nelsster and Neuc. This is encouraging, as it suggests techniques without worrying too much about these hyper-parameters..
that practitioners

---

Under review as a conference paper at ICLR 2020
SVHN
0.50
0.80
0.73
0.78
1941 RETUrEE
0621 scursyy
0.74
0.74
0..22
DiverssPublic
0.70
difference
0.70
NeatPrivale
entropy
DiversePuble
0.68
random
0.68
checkpoint
chrecppsint
chec eoiint
0.66
3300
(a) DIVERSEPUBLIC vs baselines
(b) NEARPRIVATE DIVERSEPUBLIC
Figure 3: SVHN experiments with dataset pollution. this experiment, we train the DP baseline with 30,000 of the SVHN training images. The extra public dataset combination of 40,000 SVHN training images and 10,000 CIFAR-10 training images. Left: DIVERSEPUBLIC compared against other active learning baseline techniques as in Figure 2a In this case, the active learning techniques do not outperform random selection by very much. Uncertainty by itself is not sufficient predictor of whether extra data will be helpful here, since the baseline model is also uncertain about the C10AR-10 images. Right: NEARPRIVATE compared against DIVERSEPUBLIC but started from different checkpoints ('checkpoint O' with Edp = 5.0, 'checkpoint with Edp = 6.0) to keep the privacy cost constant in Figure 2b In this case, NEARPRIVATE substantially outperforms DIVERSEPUBEE by selecting less the CIFAR-10 images.
0
D
O
0
0
MNIITT
7
/
1
1
2
2
2
3
0.990
2
2
0
2
2
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
5
5
5
S
5
5
6
6
6
C
U
6
6
6
C
0.355
20cluster
6
6
6
7
7
7
7
>
7
7 8
15/cluster
10/cluster
2
7
&
8
8
8
8
Sicluster
0.070
checkpoint
8
8
6
&
8
7
1
9
9
8
clusters
9
9
9
,
9
9
9
9
(a) DIVERSEPUBLIC with different Netuster and Nesh-
(b) Visualization of chosen public data points.
Figure 4: DIVERSEPUBLIC analysis. Left: We apply DIVERSEPUBLIC to the same DP checkpoint (dashed horizontal line), varying the number of clusters (horizontal axis) and the number of chosen points from each cluster (lines with error bars). Right: For Neluster = 100, Neach = 20, we visualize the most central example from each cluster. Since NEARPRIVATE does not have explicit clustering, we use DIVERSEPUBLIC for this visualization. Green borders mean that the initial checkpoint (dashed horizontal line) predicted correctly: while red bordered examples (originally predicted incorrectly) have dots on the left showing predictions and dots on the right showing true labels.
To address the question of which extra data points are being chosen for labeling, we create Figure 4b showing the most central example from each cluster, computed using Netuster = 100, Neach 20. The chosen examples quite diverse, with similar number of representatives from each class and variations in the thickness and shear of the digits. We can also inspect examples labeled incorrectly by the original checkpoint, such as the digit in Row 8, Col which is 7 that looks lot like '2'.
7

---

Under review as a conference paper at ICLR 2020
4410
3000
60
(a) Fixed extra privacy cost with (b) The initial training privacy cost (c) Fixed total privacy cost with EdpPCA = 0.5, Exppont 0.5. Eap for different checkpoints.
Elimii 5.0, EdpPCc = 0.3.
Figure 5: NEARPRIVATE analysis. We apply NEARPRIVATE to DP checkpoints (horizontal axis) of different privacy cost Edp. The black line with triangle represents those starting checkpoints. Middle: The initial training privacy cost Edp of DP checkpoints at different epochs of single training run. Left: We fix the extra privacy cost EdPPCA Eupport 1.0, but vary the number of labeled public points for each line. We achieve large improvements from 1,000 to 4,000 labeled public points. With even larger Niabeled, the improvements are not significant and it may be better start fine-tuning from a DP checkpoint of lower privacy cost. Right: With EdpPOA set to 0.3, we fix the total privacy cost fimmit 5.0 and vary support- For Mabeled 1000, fine-tuning from the checkpoint Epoch 60 is the best given a total privacy budget of 5.0.
5.2 HOW DOES THE STARTING CHECKPOINT AFFECT RESULTS?
Recall that NEARPRIVATE accrues extra privacy cost by accessing the histogram of neighbor counts. This means that achieving a given accuracy under a constraint on the total privacy cost requires choos- ing how to allocate privacy between NEARPRIVATE and the initial DP-SGD procedure. Making this choice correctly requires a sense of how much benefit can be achieved from applying NEARPRIVATE to different starting checkpoints. Toward that end, we conduct (Figure 5 an ablation experiment on MNIST where we run NEARPRIVATE on many different checkpoints from the same training run. Figure 5a shows the test accuracies resulting from fine-tuning checkpoints different epochs (represented on the r-axis) with fixed extra privacy cost of 1.0. Figure 55 shows the corresponding Eap for each checkpoint. Figure 5c varies other parameters given a fixed total privacy budget of 5.0.
In Figure 5a] the black line with triangle markers shows the initial test accuracies of the checkpoints. The other lines show results with different values of Niabeled from 1,000 to 10,000 respectively. With Niabeled = 1000, improvements are marginal for later checkpoints. In fact, the improvement from using Natbeted = 1000 at checkpoint 80 is not enough to compensate for the additional 1.0 privacy cost spent by NEARPRIVATE, because you could have had the same increase in accuracy by training the original model for 20 more epochs, which costs less than that. On the other hand, the improvements from using Naneeed 4000 higher significant and cannot be mimicked by training for longer.
Given a total privacy budget Eiiitts how should we decide among Edps EdpPCA, and Esupport Empirically, we observe that EdpPCA can be Allocating between Edp and Support is addressed in Figure which varies those parameters with ēimi fixed to 5.0. When the budget for gathering Piabeled is low, say NNibettd is around 1000, it is preferable to pick a later DP checkpoint, consuming higher Edp and lower Esuppon- On the other hand, when allowed label more instances from the public data, we should use an earlier DP checkpoint (with a lower Eap) and choose better public samples with respect to the private data.
small value (e.g., 0.3) without substantially affecting the results.
6 CONCLUSION
In addition to creating new baselines for DP image classifiers by fine-tuning on public data, we introduce two algorithms- DIVERSEPUBLIC and NEARPRIVATE to perform fine-tuning in a privacy- aware way. We conduct experiments showing that these algorithms bring DP object recognition closer to practicality, improving on the aforementioned benchmarks. We hope that this work will encourage further research into techniques for making differential privacy more useful in practice, and we hope that the techniques we propose here will be helpful to existing practitioners.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, 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.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Joumal of Machine Learning Research, 12(Mar):1069-1100) 2011.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations differential privacy. Foundations and R in Theoretical Computer Science, 9(3-4):21 1-407, 2014a.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for
principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 11-20. ACM, 2014b.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference on Learning Representations, 2018. URL
htttps://openreview net, wtt.://neeee//oteeeeemoe worum?iieeeooo................i. 21=
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv: 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 2015.
H. Brendan McMahan, Galen Andrew, Ulfar Erlingsson, Steve Chien, Ilya Mironov, Nicolas Papernot, and Peter Kairouz. A general approach to adding differential privacy to iterative training procedures. arXiv preprint arXiv: 1812.0620,, 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Hicu T Nguyen and Amold Smeulders. Active learning using pre-clustering, In Proceedings of the twenty-first international conference on Machine learning. pp. 79. ACM, 2004.
Avital Oliver, Augustus Odena, Colin A Raffel, Ekin Dogus Cubuk, and Ian Goodfellow. Realistic evaluation of deep semi-supervised learning algorithms. In Advances in Neural Information Processing Systems, pp. 3235-3246, 2018
Maithra Raghu, Justin Gilmer, Jason Yosinski. and Jascha Sohl-Dickstein. Sveca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. In Advances in Neural Information Processing Systems, pp. 6076-6085, 2017.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2009.
Shuang Song. Kamalika Chaudhuri, and Anand Sarwate. Stochastic gradient descent with differen- tially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248. IEEE, 2013.
Chhavi Yadav and Léon Bottou. Cold case: The lost mnist digits. Technical report, arxiv:1905 may 2019, URL
org/ /as///b///// 11t.//99....9999 10498
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv: 2016.


Reviews:
[{"review_id": "ryxQH_TlsH", "reviewer": "AnonReviewer5", "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 considers the problem of how to improve the performance of an existing DP classifier, with the help of the labelled public data. The paper considers the following process: 1. find a public dataset containing relevant samples; 2. carefully select a subset of public samples that can improve the performance of the classifier; 3 fine-tune the existing classifier on the selected samples. Two different techniques from active learning are utilized in order to select representative samples from a public dataset and fine-tune a DP classifier. This paper also conducts some experiments on   the MNIST and SVHN datasets and demonstrates improvement compared with the benchmark.\n\nI vote for rejecting for this paper, because of the following two concerns:\n\n1. I do not think this paper has made a lot of contribution to either differential privacy or active learning. It just \"borrows\" some fine-tuning techniques from active learning and apply it in DP. There is almost no theoretical contribution made by this paper. Besides, from the experimental perspective, neither can I see an obvious improvement compared with the benchmarks.\n\n2. I do not think the privacy analysis of the NearPrivate algorithm (Algorithm 2) is correct. The paper uses private argmax algorithm and claims that it satisfies $eps_{support}$-DP. However, this is only true when $N_{labeled} = 1$. Generally, it should satisfy $eps_{support} \\cdot N_{labeled}$-DP. So if we look at the experimental setting of MNIST, roughly thousand times less noise is added! Since this amount of noise is non-trivial at all, I can not judge the effectiveness of the algorithm.\n------------------------------------------------------------------------------------------\nThanks for the authors' classification. I missed the part that each private sample was only assigned to one public sample. Now I can confirm the correctness of the algorithm and increase my score accordingly.", "extra_scores": {"experience_assessment": "I have published one or two 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 thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1lWF5EAYS", "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": "The paper proposes methods for improving the performance of differentially private models when additional related but public data is available. The authors propose to fine-tune the private model with related but public data. Two heuristics for selecting data to fine-tune with are presented. \n\nI vote for rejecting the paper. My main concerns revolve around the paper's contributions. It neither makes core contributions to differential privacy nor to active learning. What it does instead is present a post-processing procedure which boils down to fine-tuning differentially private models with public data. Arguably the main contribution of the paper is the heuristics for selecting public instances for fine-tuning. These rely on several design choices (why k-means? how are points from within a cluster sampled -- uniformly at random, some other heuristic? how are uncertain private and public points matched, by solving an assignment problem or something else? ) that are not well justified or have missing details and more importantly do not clearly outperform baseline acquisition functions - selecting points based on predictive entropy or the difference between two largest logits. Finally, I am unconvinced that the paper’s premise of having access to related public data is realistic. \n\nThis would likely not change my opinion of the paper, but it would be good to substantiate the claims made in the second paragraph of the paper — the performance of differentially private models degrades with increasing model size. If the relationship is as clear as the paragraph makes it sound, then it would be great to include a graph with the x-axis being the number of parameters and the y-axis being the difference in performance between a regular and a differentially private model. One would expect to see the difference increase with model size.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "S1eIEPFXcS", "reviewer": "AnonReviewer4", "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": "---SUMMARY---\nThis paper gives two methods for improving an existing differentially private model. Both methods assume a source of unlabeled data that requires no privacy guarantees. The two methods make different uses of this public data to augment the original private model. Both preserve (a degree of) privacy for the original model.\n\nThe first method is DiversePublic. DiversePublic only post-processes the original private model M -- in particular, it does not touch the original data -- and so its privacy is immediate. At a high level, DiversePublic works by picking the \"best\" unlabelled data points for augmenting M. First, it applies M to the unlabeled data and then applies PCA to the result. Next, it selects highly \"uncertain\" points, projects them onto the top k principal components, and clusters the results. Finally, it selects samples from each cluster and uses them to augment M. This augmenting process, called FineTune, is left as a black box.\n\nThe second method is NearPrivate. The given motivation for NearPrivate is that the public dataset may have a different distribution than the original private training data. To address this, NearPrivate uses DP-PCA (a pre-existing technique for differentially private PCA) on the private dataset and projects both the private and public data onto the top k principal components. Then it compares uncertain points in the public and private dataset projections and only augments M (again using the black box FineTune) using uncertain public examples with many nearby uncertain private samples. Intuitively, this should select for points that are not too different than the original private training data.\n\nThe paper then evaluates these algorithms with experiments on MNIST and SVHN under reasonable privacy parameters (I think -- see below). These experiments compare the performance of DiversePublic and NearPrivate, where both train M using vanilla DP-SGD [Abadi et al. 2016]. DiversePublic and NearPrivate trade performances on MNIST and SVHN, but NearPrivate does (as might be expected) better when the public dataset is polluted.\n\nIn summary, the paper suggests DiversePublic and NearPrivate as useful ways to augment a given differentially private model M using public data, and their experiments suggest this is reasonable.\n\n---DECISION---\nReject.\n\nThis is an empirical paper. It proposes some algorithms and justifies these algorithms through experiments. However, the paper makes a confusing omission: it does not mention PATE [1, 2].\n\n[1] \"Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data\". Papernot et al. 2017.\n[2] \"Scalable Learning with PATE\". Papernot et al. 2018.\n\nI am more of a pure differential privacy researcher and am therefore less familiar with this line of mostly empirical work. But as far as I can tell PATE works in the same setting as that of this paper: there is a private dataset, a public unlabelled dataset, and the goal is to train a model with a differential privacy guarantee for the private dataset. As a result, PATE seems directly relevant. In particular, the claim that \"there are no published examples of a differentially private SVHN classifier with both reasonable accuracy and non-trivial privacy guarantees\" seems wrong, as the PATE papers include just that.\n\nMoreover, PATE appears at least competitive with the algorithms here. For example, the comparison given as Table 1 in [2] suggests that PATE can get 98-99% accuracy on MNIST for privacy parameters at least as low as those used here with only a few hundred new labelings. In contrast, if I understand the experiments here, they are using thousands of new labelled examples to get the same accuracy and privacy. Similarly, on SVHN the experiments here get to 84% accuracy with 10,000 new labelled examples, whereas the same Table 1 puts PATE at 90% with almost identical privacy parameters and thousands fewer new labelled examples.\n\nThat comparison is my main concern. Perhaps I am missing a reason why PATE is not comparable. If it is, it should certainly appear in the experiments. If PATE is indeed comparable, then the main improvement contributed by this paper is the post-processing aspect: PATE is a way to train a private model from scratch, but these methods work on an existing model. Even then, the question of how exactly the existing model is modified (the FineTune method) is unclear.\n\nMore broadly, there are several parts of this paper that could be much clearer. I am sympathetic to paper length limitations, but I am certain many or all of these issues can be addressed in 8 pages.\n\n1. DiversePublic description: What does it mean to \"obtain the 'embeddings'...E_{public}\"? How is k picked?\n2. How does the private point-public point assignment in NearPrivate work? Is it just random? How many points do we pick? \n3. In general, how is FineTune meant to work? I understand it is meant to be an abstract black box in the algorithm descriptions, but the experiment description doesn't explain it either. How does FineTune work in the experiments?\n4. What does 'headroom' mean in Section 4.2?\n5. The way privacy parameters are specified at various points in the experiment section makes things hard to read. A concise table summarizing privacy parameters, accuracy, and additional labels would help.\n\nBut overall, I am most interested in the PATE comparison. \n\n---EDIT AFTER AUTHOR RESPONSE---\nI missed the data-dependent aspect of PATE's privacy guarantee. That is a point in favor of this paper. As such, I've increased my score from reject to weak reject.\n\nI actually think a revised version of this paper could reasonably appear in ICLR or similar venues. However, I think the necessary revisions are too large/numerous to accept the paper in its current form, even with promises of revisions. Here are a few revisions that I think would make the paper a much better submission to future conferences:\n\n1. Add discussion of PATE. The data-dependence of their privacy guarantees is well-taken. But it is not clear that data-dependent privacy guarantees are as \"trivial\" as the paper currently claims with \"there are no published examples of a differentially private SVHN classifier with both reasonable accuracy and non-trivial privacy guarantees\" suggests. (In fact, I find it confusing that one of the PATE authors agrees with this claim -- they think their own work is trivial?). I agree that data-independent privacy guarantees are preferable, but this should certainly be discussed. As the authors themselves note, the original PATE paper was well-received, so if this paper wants to claim its privacy guarantees are somehow meaningless or even just unsatisfactory, that claim needs to be defended.\n\n2. Elaborate on the fine-tuning process. Perhaps \"fine tuning\" is indeed \"super standard in the object recognition literature\", but as all three reviews here indicate, the presentation of fine tuning is unclear in this paper. The author responses also seem to simultaneously claim that fine tuning is  both \"super standard\" and \"[not] obvious\". \n\n3. To make room for the text above, it's not clear that the material about data pollution or even presenting both methods is necessary. I would prefer to see a thorough explanation of the active learning/post-processing paradigm through one algorithm. The authors seem to want to claim that active learning is a useful private approach because it gets data-independent privacy guarantees and performance similar to algorithms with data-dependent privacy guarantees. A paper that focuses on and thoroughly defends that claim actually sounds pretty good! ", "extra_scores": {"experience_assessment": "I have published one or two 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 thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides an active-learning approach to improve the performance of an existing differentially private classifier with public labeled data. Where the paper provides a new approach, there is a consensus among the reviewers that the paper does not provide a strong enough contribution for acceptance. The authors can potentially improve the submission by including a more comprehensive comparison with the PATE framework and improving its overall presentation.
Decision: Reject