Differentially Private Learning Needs Better Features (or Much More Data)
Authors: Florian Tramer
Dan Boneh
Venue: ICLR 2021 Spotlight (2021)
Keywords: Differential Privacy
Privacy
Deep Learning

Abstract: We demonstrate that differentially private machine learning has not yet reached its ''AlexNet moment'' on many canonical vision tasks: linear models trained on handcrafted features significantly outperform end-to-end deep neural networks for moderate privacy budgets.
To exceed the performance of handcrafted features, we show that private learning requires either much more private data, or access to features learned on public data from a similar domain.
Our work introduces simple yet strong baselines for differentially private learning that can inform the evaluation of future progress in this area.

Published as a conference paper at ICLR 2021
DIFFERENTIALLY PRIVATE LEARNING NEEDS BETTER FEATURES (OR MUCH MORE DATA)
Florian Tramèr Stanford University tramer cs. stanford.edu
Dan Boneh
Stanford University
dabo@cs cs stanford.edu
ABSTRACT
We demonstrate that differentially private machine learning has not yet reached its "AlexNet moment" on many canonical vision tasks: linear models trained on handcrafted features significantly outperform end-to-end deep neural networks for moderate privacy budgets. To exceed the performance of handcrafted features, we show that private learning requires either much more private data, or access features learned on public data from similar domain. Our work introduces simple yet strong baselines for differentially private learning that can inform the evaluation of future progress in this area.
INTRODUCTION
Machine learning (ML) models have been successfully applied to the analysis of sensitive user data such as medical images (Lundervold Lundervold, 2019), text messages (Chen et al., 2019) or social media posts (Wu et al., 2016). Training these ML models under the framework of disferential privacy (DP) (Dwork et al., 2006b; Chaudhuri et al., 201 I; Shokri & Shmatikov, 2015; Abadi et al., 2016) protect deployed classifiers against unintentional leakage of private training data (Shokri et al., 2017: Song et al., 2017; Carlini et al., 2019; 2020).
Yet, training deep neural networks with strong DP guarantees comes at significant cost in util- ity (Abadi et al., 2016; Yu et al., 2020; Bagdasaryan et al., 2019; Feldman, 2020). In fact, on many ML benchmarks the reported accuracy of private deep learning still falls short of "shallow" (non-private) techniques. For example, on CIFAR-10, Papernot et al. (2020b) train a neural network to 66.2% accuracy for large DP budget of 7-53, the highest accuracy we aware of for this privacy budget. Yet, without privacy, higher accuracy is achievable with linear models and non-lcarned "handcrafted" features, e.g., (Coates & Ng. 2012; Oyallon Mallat, 2015). This leads to the central question of our work:
Can differentially private learning benefit from handcrafted features?
We answer this question affirmatively by introducing simple and strong handcrafted baselines for differentially private learning, that significantly improve the privacy-utllity guarantees on canonical vision benchmarks.
Our contributions. We leverage the Scattering Network (ScatterNet) of Oyallon & Mallat (2015)- a non-learned SIFT-like feature extractor (Lowe, 1999)-10 train linear models that improve upon the privacy-utility guarantees of deep learning on MNIST, Rashion-MNIS" and CIFAR-10 (see Table 1). For example, on CIFAR-10 10 we exceed the accuracy reported by Papernot et al. (2020b) while simultaneously improving the provable DP-guarantee by 130x. On MNIST, we match the privacy-utility guarantees obtained with PATE (Papernot et al., 2018) without requiring access to any public data. We find that privately training deeper neural networks handcrafted features also significantly improves over end-to-end deep learning, and even slightly exceeds the simpler linear models CIFAR-10. Our results show that private deep learning remains outperformed by handcrafted priors on many tasks, and thus has yet to reach its "AlexNet moment" (Krizhevsky et al., 2012).
We find that models with handcrafted features outperform end-to-end deep models, despite having more trainable parameters. This is counter-intuitioe the guarantees of private learning degrade

---

Published as a conference paper at ICLR 2021
Table Test accuracy of models with handcrafted ScatterNet features compared prior results with end-to-end CNNs for various DP budgets (c, 0 = 10-9). ). Lower values provide stronger privacy. The end-to-end CNNs with maximal accuracy for each privacy budget are underlined. We select the best ScatterNet model for each DP budget S 3 with hyper-parameter search, and show the mean and standard deviation accuracy for five runs.
Test Accuracy (%)
Data
g-DP
Source
CNN
ScatterNet+linear
ScatterNet-CNN
1.2
Feldman & Zrmie (2020)
96.6
98.1 0.1
97.8 0.1
2.0
Abadi al. (2016)
95.0
98.5
9.1
2.32
Bu et al. (2019)
96.6
98.6 0.0
98.5 + 0.0
MNIST
2.5
Chen & Lee (2020)
90.0
98.7 0.0
98.6 - 0.0
2.93
Papernot et al. (2020a)
98.1
98.7
0.0
98.7 0.1
3.2
Nasr et al. (2020)
96.1
6.78
Yu et al. (2019b)
93.2
2.7
Papernot et al. (2020a)
86.1
89.5 1 0.0
88.7 +
Fashion- -NNIST
3.0
Chen & Lee (2020)
82.3
89.7
89.0 0.1
3.0
Nasr et al. (2020)
55.0
67.0 0.1
69.3 + 0.2
6.78
et al. (2019b)
44.3
CIFAR-10
7.53
Papernot et al. (2020a)
66.2
8.0
Chen Lee (2020)
53.0
with dimensionality in the worst case (Bassily et al., 2014).! We explain the benefits of handcrafted features by analyzing the convergence rate of non-private gradient descent. First, we observe that with low enough learning rates, training converges similarly with or without privacy (both for models with and without handcrafted features). Second, we show that handcrafted features significantly boost the convergence rate of non-private learning at low learning rates. As a result, when training with privacy, handcrafted features lead more accurate models for a fixed privacy budget.
Considering these results, we ask: what is the cost of private learning's 's "AlexNer moment" That is, which additional resources do need in order to outperform our private handcrafted baselines? Following McMahan et al. (2018), we first consider the data complexity of private end-to-end learning. On 10,,R-10, we use an additional 500,000 labeled Tiny Images from Carmon al. (2019) to show that about order of magnitude more private training data is needed for end-to-end deep models to outperform our handcrafted features baselines. The high sample-complexts could be detrimental for tasks that cannot leverage "internet-scale" data collection (e.g., most medical applications).
private deep learning
We further consider private Iearning with access to public data from similar domain. In this setting, handcrafted features can be replaced by features learned from public data via transfer learning (Razavian et al., 2014). While differentially private transfer learning has been studied in prior work (Abadi et al., 2016; Papernot et al., 2020a), we find that its privacy-utility guarantees have been underestimated. We revisit these results and show that with transfer learning, strong privacy comes at only minor cost in accuracy. For example, given public unlabeled ImageNet data, we train a CIFAR- 10 model to 92.7% accuracy for a DP budget of 2.
Our work demonstrates that higher quality data-are of paramount importance for improving the performance of private classifiers in low (private) data regimes.
handcrafted or transferred from public
Code to reproduce our experiments is available at Handcrafted-DP.
www.:oomofftaateeeee ftrmer//
STRONG SHALLOW BASELINES FOR DIFFERENTIALLY PRIVATE LEARNING
We consider the standard central model of differential privacy (DP): trusted party trains ML model f on a private dataset E D. and publicly releases the model. The learning algorithm A
A number of recent works have attempted to circumvent this worst-case dimensionality dependence by leveraging the empirical observation that model gradients lie in low-dimensional subspace (Kairouz et al., 2020; Zhou al., 2020h).
2

---

Published as a conference paper at ICLR 2021
satisfies (e, 8) diffferrntl privacy (Dwork et al., 2006a), if for any datasets D, D' that differ in one record, and any set of models S: Pr(A(D) E S] Pr[A(D)) E S] d.
DP bounds an adversary's ability to infer information about any individual training point from the model. Cryptography can split the trust central party across users (Jayaraman et al., 2018; Bonawitz et al., 2017).
Prior work has trained private deep neural networks "end-to-end" (e.g., from image pixels), with large losses in utility (Shokri & Shmatikov, 2015; Abadi et al., 2016; Papernot et al., 2020b). In contrast, we study the benefits of handcrafted features that encode priors on the learning task's 's public domain (e.g., edge detectors for images). Although end-to-end neural networks outperform such features in the non-private setting, our thesis that handcrafted features result an easier learning task that is more amenable to privacy. We focus computer vision, a canonical domain for private deep learning (Abadi et al., 2016; Yu et al., 2019b; Papernot et al., 2020b; Nasr et al., 2020)), with a rich literature handcrafted features (Lowe, 1999; Dalal & Triggs, 2005; Bruna & Mallat, 2013). Our approach can be extended to handcrafted features in other domains, e.g., text or speech.
2.1 SCATTERING NETWORKS
We use the Scattering Network (ScatterNet) of Oyallon & Mallat (2015), a feature extractor that encodes natural image priors (e.g., invariance to small rotations and translations) using a cascade of wavelet transforms (Bruna & Mallat, 2013). As this cascade of transforms data independent, we can obtain a differentially private classifier by privately fine-tuning a (linear) model on top of locally extracted features. In Appendix A, we discuss other candidate "non-deep" approaches that we believe to be less suitable for differentially private learning.
We use the default parameters in (Oyallon & Mallat, 2015), a ScatterNet ((x) of depth two with wavelets rotated along eight angles. For images of size H x W, this network extracts features of dimension (K, /4, W/ /4), with = 81 for grayscale images, and 243 for RGB images. Note that the transform is thus expansive. More details on ScatterNets are in Appendix C.I.
2.2 DIFFERENTIALLY PRIVATE SCATTERNET CLASSIFIERS
To train private classifiers, we use the DP-SGD algorithm² of Abadi et al. (2016) (see Appendix B). DP-SGD works as follows: (I) batches of expected size B are sampled at random; (2) gradients are clipped to norm C: (3) Gaussian noise of variance /²"*/B² is added to the mean gradient. DP-SGD guarantees privacy for gradients, and is thus oblivious preprocessing applied independently to each data sample, such as the ScatterNet transform.
When training a supervised classifier top of ScatterNet features with gradient descent, find that normalizing the features is crucial to obtain strong performance. We consider two approaches:
Group Normalization (Wu & He, 2018): the channels of S(x) are split into G groups, and each is normalized to zero mean and unit variance. Data points are normalized independently so this step incurs no privacy cost.
Data Normalization: the channels of S(x) are normalized by their mean and variance across the training data. This step incurs privacy cost as the per-channel means and variances need to be privately estimated.
Table 2 shows that normalization significantly accelerates convergence of non-private linear models trained on ScatterNet features, for MNIST, Pashion-MNIST and CIFAR-10. For CIFAR-10, Data
Yuu et al. (2019a) show that DP-SGD outperforms other algorithms for private convex optimization, e.g., logistic regression with output or objective perturbation (Chaudhuri et al., 2011; Bassily et al., 2014; Kifer et al., 2012). In Appendix D.3, we show that DP-SGD also outperforms Privacy Amplification by Iteration (Feldman al., 2018) in our setting.
"Existing DP-SGD implementations (tensorftow/privacyy. 2019; pytorch/opacus, 2020) and many prior works (e.g., (Abadi et al.. 2016; Papernot et al., 2020b)) heuristically split the data into random batches of size exactly B. We use the same heuristic and show in Appendix D.4 that using the correct hatch sampling does not affect results.
3

---

Published as a conference paper at ICLR 2021
Table Effect of feature normalization on the accuracy of non-private ScatterNet models after 20 epochs. We also report the maximal test accuracy upon convergence (mean and standard deviation over five runs).
Normalization (Test accuracy after 20 epochs)
Dataset
None
Group Normalization
Data Normalization
Maximal Accuracy
MNIST
95.9 + 0.0
99.1 + 0.0
99. 1 = 0.0
99.3 + 0.0 91.5 + 0.0
Fashion-MNIST
82.6 0.1
90.9 + 0.1
91.0 0.2
CIFAR-10
58.0 0.1
67.8 + 0.2
70.7 = 0.1
71.1 + 0.0
Normalization performs significantly better than Group Normalization, so the small privacy cost of estimating channel statistics warranted. While the maximal test accuracy of these models falls short of tfateoof-the-ar atrt-artt CNNs, it exceeds all previously reported results for differentially private neural networks (even for large privacy budgets).
EVALUATING PRIVATE SCATTERNET CLASSIFIERS
We compare differentially private ScatterNet classifiers and deep learning models on MNIST (LeCun et al., 2010), Fashion-MNIST (Xiao et al., 2017) and CIFAR-10 (Krizhevsky, 2009). Many prior works have reported improvements over the DP-SGD procedure of Abadi et al. (2016) for these datasets. As we will show, ScatterNet classifiers outperform all prior approaches while making algorithmic changes to DP-SGD. ScatterNet classifiers can thus serve as a strong canonical baseline for evaluating proposed improvements DP-SGD in the future.
3.1 EXPERIMENTAL SETUP
Most prior works find the best model for given DP budget using a hyper-parameter search. As the private training data is re-used many times, this overestimates the privacy guarantees. Private hyper-parameter search is possible
small cost in the DP budget (Liu & Talwar, 2019), but we argue that fully accounting for this privacy leakage is hard as even our choices architectures, optimizers, hyper-parameter ranges, etc. informed by prior analysis of the same data. As in prior work, thus do not account for this privacy leakage, and instead compare ScatterNet models and end-to-end CNNs with similar hyper-parameter searches. Moreover, we find that ScatterNet models are very robust to hyper-parameter changes and achieve near-optimal utility with random hyper-parameter (see Table 3). To evaluate ScatterNet models, we apply the following dyper-parameed search:
We begin by fixing a privacy schedule. We target a moderate differential privacy budget of (s = 3, 8 10-5) and compute the noise scale a of DP-SGD so that the privacy budget is consumed after T' epochs. We try different values of T,, with larger values resulting in training for more steps but with higher noise.
We fix the gradient clipping threshold for DP-SGD C 0.1 for all our experiments. Thakkar et al. (2019) suggest to vary this threshold adaptively, but we did not observe better performance by doing so.
We try various batch sizes B and base learning rates y) with linear learning rate scaling (Goyal et al., 2017).
We try both Group Normalization (Wu & He, 2018) with different choices for the number of groups, and private Data Normalization with different choices of privacy budgets (see Appendix B for details).
We perform grid-search over all parameters as detailed in Appendix C.5. We compare our ScatterNet classifiers to the CNN models of Papernot et al. (2020b) (see Appendix C.2), which achieve the
*Our decision to try various batch sizes is inspired by Abadi (2016) found that this parameter large effect on the performance of DP-SGD. Yet, in Appendix D.I we show empirically, and argue formally that with a linear learning rate scaling (Goyal et al., 2017). DP SGD performs similarly for range of batch sizes. As a result, we recommend following the standard approach for tuning non-private SGD, wherein we fix the batch size and tune the leamning rate.
4

---

Published as a conference paper at ICLR 2021
Test Accuracy (%)
60.7%
96.7% 95.15
67.07
Test Accuracy
Accuracy
50.28
ScaterKit CWN
DP
E-DP
E-DP
(a) MNIST
(b) Aushion-MNIST
(c) CIFAR-10
Figure I: Highest test accuracy achieved for each DP budget (e, 6 10-5) for ScatterNet classifiers and the end-to-end CNNs of Papernot et al. (2020b). We plot the mean and standard deviation across five runs.
highest reported accuracy for our targeted privacy budget for all three datasets. We also perform grid-search for these models, which reproduces the results of Papernot et al. (2020b). We use the ScatterNet implementation from Kymatio (Andreux al., 2020), and the DP-SGD implementation in opacus (pytorch/opacus, 2020) (formerly called pytorch-dp).
We use a NVIDIA Titan Xp GPU with 12GB of RAM for our experiments. To run DP-SGD with large batch sizes B, we use the "virtual batch" approach of opacus: the average of clipped gradients accumulated over multiple "mini-batches"; once gradients have been averaged, we add noise and take a gradient update step. Code to reproduce our experiments is available at https:: /ttp::///ttttt.tt/ com/ ft stramer/ae Etzamer/Handrrfftedd /tt.//aaaaaaaddeeee
3.2 RESULTS
To measure a classifier's accuracy for a range of privacy budgets, we compute the test accuracy as well as the DP budget e after each training epoch (with the last epoch corresponding to == 3). For various DP budgets (c, 10-5) used prior work, Table shows the maximal test accuracy achieved by linear ScatterNet model in our hyper-parameter search, averaged over five runs. We also report results with CNNs trained on ScatterNet models, which are described in more detail below. Figure I further compares the full privacy-accuracy curves of our ScatterNets and of the CNNs of Papernot et al. (2020b). Linear models with handcrafted features significantly outperform prior results with end-to-end CNNs, for all privacy budgets I 3 consider. Even when prior work reports results for larger budgets, they do not exceed the accuracy of our bascline.
In particular, for CIFAR-10, 66.2% for a budget of E = 7.53 with a much smaller budget of æ = 2.6. This an improvement in the DP-guarantee of 4.9 134. On MNIST, significantly improve upon CNN models, and match the results of PATE (Papernot et al., 2018), namely 58.5% accuracy at E = 1.97, in a more restricted setting (PATE uses 5,000 public unlabeled MNIST digits). In Appendix C.5, provide the hyper- parameters that result in the highest test accuracy for our target DP budget of (= 3, 10 10-5), -5-). We did not consider larger privacy budgets for ScatterNet classifiers, the accuracy we achieve at is close to the accuracy of non- non-private ScatterNet models (see Table 2).
match the best CNN accuracy in (Papernot et al., 2020b)-namely
As noted above, our models (and those of most prior work) are the result of a hyper-parameter parameter search. While we do not account for the privacy cost of this search, Table 3 shows that an additional advantage of ScatterNet classifiers is an increased robustness to hyper- paremeer changes. In particular, for CIFAR-10 10 the worst configuration for linear ScatterNet classifiers outperforms the best configuration for end-to-end CNNs. Moreover, on MNIST and -NISS,, the median accuracy of linear ScatterNet models outperforms the best end-to-end CNN.
Training CNNs on Handerafted Features. Since linear models trained on handcrafted features outperform the privacy-utilis guarantees of deep models trained end-to-end, natural question is whether training deeper models on these features achieves even better results. We repeat the above experiment with similar CNN model trained on ScatterNet features (see Appendix C.2). The privacy-accurace curves for these models are in Figure 2. We find that handcrafted features also improve the utility of private deep models, phenomenon which analyze and explain in Section 4. CIFAR- 10. the deeper ScatterNet models even slightly outperform the linear models, while for MNIST and Fashion-MNIST the linear models perform best. This can be explained by the fact that
5

---

Published as a conference paper at ICLR 2021
Table 3: Variability across nyper-parametern. For each model, we report the minimum, maximum,
median and median absolute deviation (MAD) in test accuracy (in %) achieved for DP budget of
= 8 10-6). The maximum accuracy below may exceed those Table and Figure which
are averages of five runs. SN stands for ScatterNet.
MNIST
Fashion-MNIST
CIFAR-10
Model
Min
Max
Median
MAD
Min
Max
Median
MAD
Min
Max
Median
MAD
SN
Linear
96.8
98.8
98.4
0.2
85.3
89.8
88.7
59.5
67.0
65.4
0.9
SN
CNN
95.6
98.8
98.1
0.3
77.8
89.1
87.2
57.3
69.5
66.9
1.6
CNN
86.1
98.2
97.4
0.5
20.2
86.2
83.6
1.8
39.4
59.2
52.5
5.4
Test Accuracy (%)
80.75
Test Accuracy (%8
98.7%
Text Accuracy
$0.0K
07.0%
38.198
66.005
10.2%
Scattehet-- hear Scameohet--774 CMN
30
sDDP
S-DP
E-
(a) MNIST
(b) Fashion- -NNIST
(C) CIFAR-10
Figure 2: Highest test accuracy achieved for each DP budget (s, 5 = 10-5) for linear ScatterNet
classifiers, CNNs top of ScatterNet features, and end-to-end CNNs. Shows mean and standard
deviation across five runs.
in the non-private setting, linear ScatterNet models achieve close to state-of-the-ar accuracy on MNIST and Fashion-MNIST, and thus there is little room for improvement with deeper models (see Table 11). Table 3 further shows that ScatterNet CNNs are also less sensitive to hyper-parameters than end-to-end CNNs.
Note that on each dataset consider, end-to-end CNNs can outperform ScatterNet models when trained without privacy. Thus, end-to-end CNNs trained with DP-SGD must eventually surpass ScatterNet models for large enough privacy budgets. But this currently requires settling for weak provable privacy guarantees. On CIFAR-10 for example, ScatterNet classifiers still outperform end-to-end CNNs for 7.53 (Papernot al., 2020b). While the analysis of DP-SGD might not be tight, Jagielski et al. (2020) suggest that the true & guarantee of DP-SGD is at most one order of magnitude smaller than the current analysis suggests. Thus, surpassing handcrafted features for small privacy budgets on CIFAR-10 may require improvements beyond a tighter analysis of DP-SGD.
4 HOW DO HANDCRAFTED FEATURES HELP?
In this section, we analyze why private models with handcrafted features outperform end-to-end CNNs. We first consider the dimensionality of our models, but show that this does not explain the utility gap. Rather, we find that the higher accuracy of ScatterNet classifiers is due to their faster convergence rate when trained without noise.
Smaller models not easier to train privately. The utility of private learning typically degrades as the model's dimensionality increases (Chaudhuri et al., 2011; Bassily et al., 2014). This is also the case with DP-SGD which adds Gaussian noise, of scale proportional to the gradients, to each model parameter. We thus expect smaller models to be easier to train privately. Yet, as we see from Table for MNIST and Fashion-MNIS" the linear ScatterNet model has more parameters than the CNNs. For CIFAR-I0 10, the end-to-end CNN we used is larger, so we repeat the experiment from Section with CNN of comparable size to the ScatterNet classifiers (see Appendix D.5). This has minor effect on the performance of the CNN, Thus, the dimensionality of ScatterNet classifiers fails explain their better performance.
Models with handcrafted features converge faster without privacy. DP-SGD typically requires a smaller learning rate than noiseless (clipped) SGD, so that the added noise gets averaged out over small steps. We indeed find that the optimal learning rate when training with DP-SGD is order of magnitude lower than the optimal learning rate for training without noise addition (with gradients clipped to the same norm in both cases).

---

Published as a conference paper at ICLR 2021
Table Number of trainable parameters of our models. For CIFAR-10, we consider two different end-to-end CNN architectures (see Appendix C.2), the smaller of which has approximately as many parameters as the linear ScatterNet model.
MNIST & Fashion-MNIST
CIFAR-I
ScatterNet+Linear ScatterNet+CNN CNN
40K
155K
33K
187K
26K
551K
168K
Train Accuracy (%
80
90
60-
00
40-
Scatterfotssl innar
10
ScotterNee+CNN
CNV
Naise
60
40
Epochs
Epochs
Low LR (1) 0.25)
High LR (1) 1.0)
Figure 3: Convergence of DP-SGD with and without noise CIFAR-10, for ScatterNet classifiers and end-to-end CNNs. (Left): low learning rate. (Right): high learning rate.
To understand the impact of gradient noise on the learning process, we conduct the following experiment: we select low learning rate that is near-optimal for training models with gradient noise, and high learning rate that is near-optimal for training without noise. For both learning rates, we train CIFAR- 10 models both with and without noise (with gradient clipping in all cases). Figure shows that with high learning rate, all classifiers converge rapidly when trained without noise, but gradient noise vastly degrades performance. With a low learning rate however, training converges similarly whether add noise not. What distinguishes the ScatterNet models is the faster convergence rate noiseless SGD. The experimental setup and similar qualitative results on MNIST and Fashion-MNIST are in Appendix C.6. Thus, find that handcrafted features beneficial for private learning because they result in a simpler learning task where training converges rapidly even with small update steps. Our analysis suggests avenues towards obtaining higher accuracy with private deep learning:
Faster convergence: Figure 3 suggests that faster convergence non-private training could translate to better private learning. DP-SGD with adaptive updates (e.g., Adam (Kingma & Ba, 2015)) indeed sometimes leads to small improvements (Papernot et al., 2020b; Chen & Lee, 2020; Zhou et al., 2020a). Investigating private variants of second-order optimization methods is an interesting direction for future work.
More training steps (a.k.a a more data): For fixed DP-budget e and noise scale a, increasing the training set size N allows for running more steps of DP-SGD (McMahan et al., 2018). In Section 5. 1, we investigate how the collection of additional private data impacts the utility of private end-to-end models.
TOWARDS BETTER PRIVATE DEEP LEARNING
We have shown that on standard vision tasks, private learning strongly benefits from handcrafted features. Further improving our private baselines seems hard, as they come close to the maximal accuracy of ScatterNet models (see Table 2). We thus turn to other avenues for obtaining stronger privacy-utility guarantees. We focus on CIFAR-10, 10, and discuss two natural paths towards better private models: (1) access to larger private training set, and (2) access to public image dataset from a different distribution (some works also consider access to public unlabeled data from the same distribution the private data (Papernot al., 2017; 2018; Zhu al., 2020)).
7

---

Published as a conference paper at ICLR 2021
Test Accuracy (%
Test Accuracy (%
100
92.7%
70
90
60
80
80.0%
ScatterNett+Linen ScatterNet+
30-
SimCLRv2 (unlabeled Imagelett)
CNN
ResNiXx (laboled CIFAR-100)
40
10K
25K
50K
100K
250K
550K
0.5
1.0
1.5
2.0
Training Set Size N
E-DP
Figure 4: CIFAR-10 10 test accuracy for training set size N and a DP budget of (s = 3, = 1/2N). For N > 50K, we augment CIFAR- 10 with pseudo-labeled Tiny Images collected by Carmon et al. (2019).
Figure 5: Privacy-utilityy tradeoffs for trans- fer learning on CIFAR-IO. We fine-tune lin- models on features from ResNeXt model trained on CIFAR- 100, and from a SimCLR model trained unlabeled ImageNet.
5.1 IMPROVING PRIVACY BY COLLECTING MORE DATA
We first analyze the benefits of additional private labeled data on the utility of private models. Since the privacy budget consumed by DP-SGD scales inversely with the size of the training data N, collecting more data allows either to train for more steps, or lower the amount of noise added per step-for a fixed DP budget
To obtain larger dataset comparable to CIFAR-10, we use 500K pseudo-labeled Tiny Images (Tor- ralba et al., 2008) collected by Carmon et al. (2019). 6 We then train private models on subsets of size 10,000 N < 550,000 from this dataset. Figure 4 reports the highest test accuracy achieved for a privacy budget of (e = 3, 5 = 1/2N) (see Appendix C.7 for the experimental setup). We find that need about order for end-to-end CNNs to outperform ScatterNet features. As we show in Appendix C.7, larger datasets allow DP-SGD to be run for more steps at fixed privacy budget and noise level (as also observed in (McMahan et al.. (018))-thereby overcoming the slow convergence rate we uncovered in Section 4. While the increased sample complexity of private deep learning might be viable for "internet-scale applications (e.g.. language modeling across mobile devices), it is detrimental for sensitive applications with more stringent data collection requirements, such as healthcare.
increase in the size of the private training dataset in
5.2 TRANSFER LEARNING: BETTER FEATURES FROM PUBLIC DATA
Transfer learning a natural candidate for on public image data often significantly outperform handerafted features (Razavian et al., 201 4). We first consider transfer learning from CIFAR-100 to CIFAR- 10, where the labeled CIFAR-100 data is assumed public. We extract features from the penultimate layer of a ResNeXt (Xie et al., 2017) model trained on CIFAR-100. A non-private linear model trained on these features achieves 84% accuracy on CIFAR-10. When training linear models with DP-SGD, curve in Figure (see Appendix C.8 for details). We reach an accuracy of 80.0% at a budget of (c 2, = 10-5), significant improvement over prior work for the same setting and privacy budget, e.g., 67% accuracy in (Abadi et al., 2016) and 72% accuracy in (Papernot et al., 2020a). The large gap between our results and prior work is mainly attributed to better choice of source model (e.g.. the transfer learning setup in (Papernot et al., 2020a) achieves 75% accuracy on CIFAR-10 in the non-private setting). Mirroring the work of Kornblith al. (2019) non-private transfer learning, we thus find that the heuristic rule "better models transfer better" also holds with differential privacy.
computer vision, features learned
get the privacy-utiligg
'The Tiny Images dataset has been withdrawn after the discovery of offensive class labels (Prabhu & Birhane, 2020). The subset used by Carmon al. (2019) is filtered match the CIFAR- 10 labels, and is thus unlikely contain offensive content.
'The privacy guarantees obtained with this dataset could be slightly overestimated, the pseudo-labels of Carmon et al. (2019) obtained using model pre-trained CIFAR- 10, thus introducing dependencies hetween private data points.
8

---

Published as a conference paper at ICLR 2021
We further consider access to a public dataset of unlabeled images. We extract features from the penultimate layer of a SimCLR model (Chen et al., 2020a) trained on unlabeled ImageNet. A non- private linear model trained on these features achieves 95% accuracy CIFAR- 10 (using labeled ImageNet data marginally improves non-private transfer learning to CIFAR- 10 (Chen et al., 2020a)). With the same setup for CIFAR-100 100 (see Appendix C.8), train linear model to 92. 7% accuracy for DP budget of (E = 2, c = 10 5) (see Figure 5).
CONCLUSION AND OPEN PROBLEMS
We have demonstrated that differentially private learning benefits from "handcrafted" features that encode priors on the learning task's s domain. In particular, we have shown that private ScatterNet classifiers outperform end-to-end CNNs on MNIST, Fashion-MNIST and CIFAR-I0. We have further found that handcrafted features can be surpassed when given access to more data, either a larger private training set, or a public dataset from a related domain. In addition to introducing strong baselines for evaluating future improvements to private deep learning and DP-SGD, our work suggests a number of open problems and directions for future work:
Improving DP by accelerating convergence: Our analysis in Section 4 shows that a limiting factor of private deep learning is the slow convergence of end-to-end deep models. While the existing literature on second-order optimization for deep learning has mainly focused on improving the overall wall-clock time of training, it suffices for DP reduce the number of private training steps- possibly at an increase in computational cost.
Federated learning: While we have focused on standard centralized setting for DP, our techniques can be extended decentralized training schemes such as Federated Learning (McMahan et al., 2017; Bonawitz et al., 2017; Kairouz et al., 2019). DP has been considered for Federated Learning (Geyer et al., 2017; McMahan et al., 2018), but has also been found to significantly degrade performance in some settings (Yu et al., 2020).
Handcrafted features for ImageNet and non-vision domains: To our knowledge, there have not yet been any attempts to train ImageNet models with DP-SGD, partly due to the cost of computing per-sample gradients. While linear classifiers are unlikely be competitive ImageNet, handcrafted features can also help private learning by accelerating the convergence of CNNs, as we have shown in Figure 2. Notably, Oyallon et al. (2018) match the (non-private) accuracy of AlexNet (Krizhevsky et al., 2012) on ImageNet with a small six six-layer CNN trained on ScatterNet features. Another interesting direction to extend our results to domains beyond vision, e.g., with handcrafted features for text (Manning & Schutze, 1 1999) or speech (Andén & Mallat, 2014).
ACKNOWLEDGEMENTS
We thank: Mani Malek, Ilya Mironov, Vaishaal Shankar and Ludwig Schmidt for fruitful discussions about differential privacy and computer vision baselines, and comments early drafts of this paper; Nicolas Papernot and Shuang Song for helping us reproduce the results in (Papernot et al., 2020b); Nicolas Papernot for comments early drafts of this paper, Edouard Oyallon for enlightening discussions about Scattering networks.
REFERENCES
lensorflow/privacy, 2019. URL /ttp:/ppe///tttt...o////sssrrs/p
pytorch/opacus, 2020. URL httttp////ggttub..om//ooo/o//o//
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
Joakim Andén and Stéphane Mallat. Deep scattering spectrum. IEFF Transactions Signal Processing, 62 (16):4114 14-41114 2014.

---

Published as a conference paper at ICLR 2021
Mathieu Andreux. Tomás Angles, Georgios Exarchakis. Roberto Leonarduzzi, Gaspar Rochette, Louis Thiry. John Zarka, Stéphane Mallat, Joakim Andén, Eugene Belilovsky, Joan Bruna, Vineent Lostanlen, Matthew J. Him, Edouard Oyallon, Sixin Zhang, Carmine Cella, and Michael Eickenberg. Kymatio: Scattering transforms in Python. Journal of Machine Learning Research, (1 6. 2020.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang. and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations (ICLR), 2020.
Eugene Bagdasaryan, Omid Poursaced, and Vitaly Shmatikov. Differcntial privacy has disparate impact on model accuracy. In Advances Neural Information Processing Systems, pp. 15479-15488, 2019.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp- 464-473. 473, IEEE, 2014.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for In ACM SIGSAC Conference Computer and Communications Security (CCS), pp. 1175-1191. ACM, 2017.
machine learning.
Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE transactions on pattrrn analysis and machine intelligence, 35(8):1872-I5 1886, 2013.
Zhiqi Bu, Jinshuo Dong. Qi Long, and Weijie J Su. Deep learning with Gaussian differential privacy. arXiv preprint arXiv:1911.11607 2019.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernjj Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization neural networks. In 28th USENIX Security Symposium, pp. 284, 2019.
Nicholas Carlini, Florian Tramer. Eric Wallace, Matthe Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. arXiv preprint urXi::2012.07803 2020.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, pp. 11192-11203, 2019.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimiza- tion. Journal of Machine Learning Research, 12(3), 2011.
Chen Chen and Jaewoo Lee. Stochastic adaptive line search for differentially private optimization. arXiv preprint arXiv:2008.07977 2020.
Mia Xu Chen, Benjamin N Lee, Gagan Bansal, Yuan Cao, Shuyuan Zhang, Justin Lu, Jackie Tsay. Yinan Wang, Andrew M Dai, Zhifeng Chen, et al. Gmail smart compose: Real-time assisted writing. Pruceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2287-2294 2019.
Ting Chen, Simon Korbblihh, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint 2002::2002.05709, 2020a.
Ting Chen, Simon Komblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big supe-supe models strong semi-supervised learners. arXiv preprint arXiv:2006. 2020b.
Adam Coates and Andrew Y Ng. Learning feature representations with k-means. In Neural networks: Tricks of the trade. pp. 561-580. Springer, 2012.
Navneet Dalal and Bill Triggs. Histograms of oriented gradients for human detection. In 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR 05), volume 1, pp. 886 893, IEEE, 2005.
Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Conference on Computer Vision and Pattern Recognition (CVPR), pp. 248-255. IEEE, 2009.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006a.
10

---

Published as a conference paper at ICLR 2021
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitivity in private data analysis. Theory of cryptography conference, pp. 284. Springer, 2006b.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserv- ing statistical validity in adaptive data analysis. In Proceedings of the sorty-seventh annual ACM symposium on Theory of computing, pp. 117-126, 2015.
Vitaly Feldman. Does learning require memorization? short tale about a long tail. Proceedings of the 52nd Annual ACM SIGACT' Symposium on Theory of Computing, pp. 954-959, 2020.
Vitaly Feldman and Tijana Zmic. Individual privacy accounting via Rényi filter. arXiv preprint
arXiv:2008. //000 193, 2020.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532 IEEE, 2018.
Robin C Geyer. Tassilo Klein, and Moin Nabi. Differentially private federated learning:: A client level perspective. arXiv preprint (eXXiv:712.075355 2017.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training ImageNet in 1 hour. arXiv preprint arXiv:
2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571 17880, 2018.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private SGD? arXiv preprint arXiv:2006. 07709, 2020.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy- Privacy-preserving empirical risk minimization, Advances in Neural Information Processing Systems, pp- 6343-6354, 2018.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachol Cummings, et al. Advances and open problems in federated learning. arXiv preprint
2019.
Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. Dimension independence in unconstrained private erm via adaptive preconditioning. arXiv preprint arXhv:2008.06570 2020.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high- dimensional regression. In Conference Learning Theory, pp. 2, 2012.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Simon Komblith, Jonathon Shlens, and Quoc V Le. Do better imagenet models transfer better? In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2661 16611,67,120 2019.
Alex Krizhevsky, Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs, 2010.
Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora.
Enhanced convolutional neural tangent kemels. arXiv preprint arXiv: 19t.10911.0009 2019.
Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory Computing, pp. 298-309, 2019.
David G Lowe. Object recognition from local scale-invariant features. In Proceedings of the seventh IEEE international conference on computer vision, volume 2, pp. 1150-1157. Ieee, 1999.
Alexander Selvikvåg Lundervold and Arvid Lundervold. An overview of deep learning in medical imaging focusing on MRI. Zeitschrift für Medizinische Physik, 29(2):102-127, 2019.
Christopher Manning and Hinrich Schutze. Foundations of statistical natural language processing. 1999.

---

Published as a conference paper at ICLR 2021
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp. 1273-1282, PMLR, 2017.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations (ICI.R), 2018.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. IEEE, 2017.
Iyy Mironov, Kunal Talwar, and Zhang. Rényi differential privacy of the sampled Gaussian mechanism. arXiv preprint arXiv: 10530, 2019.
Milad Nasr, Reza Shokri, and Amir houmansadr. Improving deep learning with differential privacy using gradient encoding and denoising. arXiv preprint arXiv:2007.11524 2020.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75-84, 2007.
Edouard Oyallon and Stéphane Mallat. Deep roto-translation scattering for ohject classification. Proceedings of the IÉEE Conference on Computer Vision and Puttern Recognition, pp. 2865-2873, 2015.
Edouard Oyallon, Sergey Zagoruyko, Gabriel Huang, Nikos Komodakis, Simon Lacoste-Julien, Matthew Blaschko, and Eugene Belilovsky. Scattering networks for hybrid representation learning. JEEE transactions on pattern analysis and machine intelligence, 41(9):2208 2221, 2018.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In International Conference on Learning Representations (ICLR), 2017.
Nicolas Papernot, Shuang Song, Tlya Mironow, Ananth Raghunathan, Kunal Talwar, and Úlfar Frlingsson. Scalable private learning with PATE. In International Conference Learning Reprexentations (ICLR). 2018.
Nicolas Papernot, Steve Chien, Shuang Song, Abhradeep Thakurta, and Ulfar Erlingsson. Making the shoe fit: Architectures, initializations, and tuning for learning with privacy, 2020a. URL httpt:t/////ett //tppr/ve////peeiiie.. net/ forumm 1d--dgg-111111
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. Theory and Pructice of Disferential Privacy, 2020b.
Vinay Uday Prabhu and Abeba Birhane. Large image datasets: A pyrrhic win for computer vision? arXiv preprint arXiv:2006. 16923, 2020.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 188, 2008
Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, and Stefan Carlsson. CNN features off-the-shelf: an astounding baseline for recognition. In Computer Vision and Pottern Recognition Workshops (CVPRW), 2014 IEEE Conference on, pp. 512-519. IEEE, 2014.
Benjamin Recht, Rehecca Roelofs, Ludwig Schmidt, and Vaishnal Shankar. Do CIFAR-10 classifiers generalize to CIFAR-10? arXiv preprint 1rXiv:1806.0000 1806.0041,, 2018.
Benjamin Rubinstein, Peter Bartlett, Ling Huang, and Nina Taft. Learning in a large function space: Privacy- preserving mechanisms for SVM learning. Journal of Privacy and Confidentiality, 4(1):65-100, 2012.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Keil, Ludwig Schmidt, Jonathan Tagan-Kellcy, and Benjamin Recht. Neural kernels without tangents. In International Conference on Machine Learning (ICML.), 2020.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In Procedingg of the 22nd ACM SIGSAC conference computer and communications security, pp. 1310-1321, 2015. 2015.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium Security and Privacy (SP), pp. 3-18. IEEE, 2017.
Congzheng Song, Thomas Ristenpart, and Vitaly Shmatikov. Machine learning models that remember too much. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 5887-001 2017.
12

---

Published as a conference paper at ICLR 2021
Om Thakkar, Galen Andrew, and HI Brendan McMahan. Differentially private learning with adaptive clipping. arXiv preprint 3Xiv:/905..000 03871, 2019.
Antonio Torralba, Rob Fergus, and William T Freeman. 80 million tiny images: A large data set for nonparametric object scene recognition. IEEE transactions on pattern analysis and machine intelligence, 30(11):1955) 19:1988- 1970, 2008.
Yu- Hi-Xi Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. Proceedings of Machine Learning Research, 89:1226-1233 16-18 Apr 2019.
Shaomei Wu, Hermes Pique, and Jeffrey Wieland. Using artificial intelligence to help blind people 'see"
Faccbook. https: /about. com news/ 22066 0//1////////////// (4/using-arttiii inttrratiiiiaaa i -etpeeppppppeeeeeeeeeeeeeeeeeeee
co-help-bling letplpp--iidd-ppee-e-eeeee wwwppp-ppppeeeeeee see- facebook/, 2016.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pp. 3-19, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. reshion-mmist a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 17Xiv:1708,0720 2017.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on compuder vision and puttern recognition. pp. 1192-1500. 2017.
Da Yu. Huishuai Zhang, Wei Chen, Tie Yan Liu, and Jian Yin. Gradient perturbation is underrated for differentially private convex optimization. arXiv preprint 11Xiv.191..11363, 2019a.
Lei Yu, Ling Liu, Calton Pu, Mehmet Emre Gursoy, and Stacey Truex. Differentially private model publishing for deep learning. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 332 349, IEEE, 2019b.
Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adaptation. arXiv preprint 0rXiv:2002.04758, 2020.
Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee. Private stochastic non- convex optimization: Adaptive algorithms and tighter generalization bounds. arXiv preprinnt.rXX1.22200..5555 2020a.
Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private SGD with gradient subspace identification. arXiv preprint arXiv:2007.0388 03311, 2020b.
Yuqing Zhu, Xiang Yu, Manmohan Chandraker, and Yu-Xiang Wang. Private-KNN: Practical differential privacy for computer vision. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11854-11862, 2020.
13

---

Published as a conference paper at ICLR 2021
A WHY SCATTERNETS?
In this paper, we propose to use the ScatterNet features of Oyallon & Mallat (2015) as a basis for shallow differentially private vision classifiers. We briefly discuss number of other shallow approaches that produce competitive results for canonical vision tasks, but which appear less suitable for private learning.
Unsupervised feature dictionaries. Coates & Ng (2012) achieve above 80% test accuracy on CIFAR-I0 with linear models trained on top of a dictionary features extracted from a mixture of image patches. Their approach relies on a combination of many "tricks", including data normalization, data whitening, tweaks to standard Gaussian Maaussian-Miture---- Mixture-Moode -Model (GMM) algorithms, feature selection, etc. While is conceivable that each of these steps could be made differentially private, opt here for a much simpler unlearned baseline that is easier to analyze and to apply to variety of different tasks. We note that existing work on differentially-prriatee learning of mixtures (e.g., (Nissim et al., 2007)) has mainly focused on asymptotic guarantees, and we are not aware of any exiting algorithms that have been evaluated on nigh-dimensional datasets such as CIFAR-10.
Kernel Machines. Recent work Neural Tangent Kernels (Jacot et al., 2018) has shown that performance deep neural networks on CIFAR-10 could matched by specialized kernel methods (Li et al., 2019; Arora et al., 2020; Shankar et al., 2020). Unfortunately, private learning with non-linear kernels is intractable in general (Chaudhuri et al., 2011; Rubinstein et al., 2012). Chaudhuri et al. (2011) propose obtain private classifiers by approximating kernels using random features (Rahimi & Recht, 2008), but the very high dimensionality of the resulting learning problem makes it challenging to outperform our handcrafted features baseline. Indeed, we had originally con- sidered a differentially-prieee
variant of the random-feature CIFAR-10 classifier proposed in (Recht al., 2018), but found the model's 's high dimensionality (over 10 million features) to be detrimental to private learning.
B DP-SGD, RDP AND PRIVATE DATA NORMALIZATION
Throughout this work, we use the DP-SGD algorithm of Abadi et al. (2016):
Algorithm 1: DP-SGD (Abadi et al., 2016)
input Data {x) ..., ENN) learning rate 17, noise scale batch size B, gradient norm bound epochs Initialize O, randomly
for E [T N/B] do Sample batch B, by selecting each æ; independently with probability 8/x
// compute per-sample gradients // clip gradients g. (2 9 (w.) ( NN,, // add noise to average gradient with
each æ; E Br: (x.) Ve, L(O.,x.))
(w, < gi (a:) min(1, (/(ac(ts))la))
Gaussian mechanism
8.11 + 0, ng: ng:
// SGD step
Sntput:0rnjaa
The tightest known privacy analysis of the DP-SGD algorithm is based on the notion of Rényi differential privacy (RDP) from Mironov (2017), which recall next.
14

---

Published as a conference paper at ICLR 2021
Definition B.1 (Rényi Divergence). For two probability distributions P and Q defined range R, the Rényi divergence of order a > 1
Da(PIQ) = 1
P(a) ((x)
log E x>QQ
Definition B.2 ((a,e) RDD (Mironov, 2017)). A randomized mechanism f D said have e-Rényi differential privacy of order or (a, (RD for short, if for any adjacent D, D' E D it holds that
Da(f(D))(((') S
To analyze the privacy guarantees of DP-SGD, we numerically compute (D()()))((())) for range of orders (Mironov et al., 2019; Wang et al., 2019) in each training step, where D and D' are training sets that differ a single element. To obtain privacy guarantees for training steps, we use the composition properties of RDP:
Lemma B.3 (Adaptive composition of RDP (Mironov et al., 2019)). Let f D R₁ be (1, and g R1 x D + R2 be (a, (o,82)-RDDD) then the mechanism defined as (X,Y) (X,)) where ~ F(D) and Y g X, D), satisfies (a, RRPP
Finally, the RDP guarantees of the full DP-SGD procedure can be converted into (s,0)-DP guarantee:
Lemma B.4 (From RDP to (c, DD (Mironov et al., 2019)), If is an (a, RD- mechanism, also satisfies (s + log 1/8 8)- for any 0 < 8 <.
Private Data Normalization. In order to apply Data Normalization the ScatterNet features (which greatly improves convergence, especially on CIFAR-IO), we use the P PrivDataNe procedure Algorithm compute private estimates of the per-channel mean and variance of the ScatterNet features.
Algorithm Private Data Normalization
Function PrivChanne (data E N nor bound C, noise scale dwom.) S μ. Er,0 (DGn)t)) R // compute per-channel means for each sample
p. < p4 min(1, %/lmslaa
// clip each sample's per-channel
means
j +- [.[ + NO, oonn C)r) // private mean using Gaussian mechanism
return j
Function PrivDataNoss (data D, norm bounds Ci, Cz. noise scale Jane threshold
+- PwwwChanneleeanlllalaaaaaaa C1, mnxm)
11 private per-channel
upa P-PrivChannelMeaan D2 Cz, Grom)
11 private per-channel mean-square private per-channel variance
Var +- max(āp= ;),
For cach 1 liiiN, D: + (D: p)// Var
// normalizo each sample
independently
return D
In order to obtain tight privacy guarantees for the full training procedure (i.e., privacy-preserving Data Normalization followed by DP-SGD), first derive the RDP guarantees of PrivDat aDo
Claim B.5. The Pri PrivDaaaNors procedure is 2
for any 1.
The above claim follows from the RDP guarantees of the Gaussian mechanism in (Mironov, 2017),
together with the composition properties of RDP in Lemma B.3 above.
Finally, given RDP guarantee of (a, E1) for PrivDataNorm. and RDP guarantee of (a, E2) for SP-SG,, we apply Lemma B.3 to obtain an RDP guarantee of (a, Ei + E2), and convert to a DP guarantee using Lemma B.4.
15

---

Published as a conference paper at ICLR 2021
C EXPERIMENTAL SETUP
C.I SCATTERING NETWORKS
We briefly review the scattering network (ScatterNet) of Oyallon Mallat (2015). Consider an input The output of scattering network of depth J is feature vector given by
S(x) = A, W2 W1 z:|
(1)
where the operators W1 and W22 are complex-valuee valued wavelet transforms, each followed by a non-linear complex modulus, and the final operator A performs spatial averaging over patches of 2 features. Both wavelet transforms W and W2 are linear operators that compute a cascade convolutions with filters from a fixed family of wavelets. For an input image of spatial dimensions H x W, each of the image's color channels independently to yield an output
the ScatterNet applied H W ). The channel dimensionality K depends on the network depth J and the granularity of the wavelet filters, and is chosen so that K/220 = ((1) (i.e., the ScatterNet approximately preserves the data dimensionality).
tensor of dimension (K, 27 27
For all experiments, we use the default parameters proposed by Oyallon & Mallat (2015), namely 2, consisting wavelet filters rotated along eight angles. For an
Scattering Network of depth an input image of spatial dimensions H x W, this configuration produces output of dimension (K, B/1, W/ /1), with = 81 for grayscale images, and 243 for RGB images.
C.2 MODEL ARCHITECTURES
Below, we describe the ScatterNet+Lineatt ScatterNet+CNN and end-to-end CNN architectures used in Section 3 and Section 4. The CNN architectures adapted from Papernot al. (2020b).
Linear ScatterNet Classifiers. The default Scattering Network of Oyallon & Mallat (2015) extracts feature vectors of size (81, 7, 7) for MNIST and Fashion-MNIs and of size (243, 8, 8) for CIFAR- 100 We then train standard logistic regression classifier (with per-class bias) on top of these features, as summarized below:
Table 5: Size of linear ScatterNet classifiers.
Dataset
Image size
Linear ScatterNet size
MNIST
28 x 28
3969 x 10
Fashion-MNIST
28
3969
CIFAR-I
32 x
15552
End-to-end CNNs. We the CNN architectures proposed by Papernot et al. (2020b), which were found as a result of an architecture search tailored to DP-SGD," Notably, these CNNs are quite small (since the noise of DP-SGD grows with the model's dimensionality) and Tanh activations, which Papernot et al. (2020b) found to outperform the more common ReLU activations. For the experiments Section 4, we also consider a smaller CIFAR-I1 model, with a dimensionality comparable to the linear ScatterNet classifier. While the standard model has six convolutional layers of size 12-32-64-64-125 10--128--222 128, the smaller model has five convolutional layers of size 16- 16-16-32-32-64 (with max-pooling after the 2nd 4th and 5th convolution).
'The CNN architecture for CIFAR-10 10 in Table 7 differs slightly from that described in (Papernot et al.. 2020b). Based discussions with the authors of (Papernot al., 2020b), the architecture in Table 7 is the correct reproduce their best results.
16

---

Published as a conference paper at ICLR 2021
Table 6: End-to-end CNN model for MNIST and Fashion-MNIST, with Tanh activations (Papernot al., 2020b).
Table 7: End-to-end CNN model for CIFAR-IO, with Tanh activations (Papernot et al., 2020b). Section 4, we also use smaller variant of this architecture with five convolutional layers of 16- (6-16-32-32-64 filters.
Layer
Parameters
Convolution
16 filters 8x8,, stride padding 2
Max-Pooling
2x2, stride
Layer
Parameters
Convolution
32 filters of 4x4, stride 2, padding 0
Convolution
filters of 3x3, stride 1, padding
Max-Pooling
2x2, stride I
Max-Pooling
2x2, stride
Fully connected
32 units
Convolution x2
64 filters of 3x3, stride 1, padding
Fully connected
10 units
Max-Pooling
2x2, stride 2
Convolution x2
128 filters of 3x3, stride 1, padding
Max-Pooling.
2x2, stride 2
Fully connected
128 units
Fully connected
10 units
ScatterNet CNNs. To fine-tune CNNs top of ScatterNet features, adapt the CNNs from Table 6 and Table 7. As the ScatterNet feature vector larger than the input image (784 - 3969 features for MNIST and Fashion-MNIST, and 3072 15552 features for CIFAR-10), CNN models. For MNIST and Fashion MNIST, we reduce the number of convolutional filters. For CIFAR-IO, reduce the network depth from many parameters as the linear ScatterNet classifier.
smaller
which results in model with approximately as
Table 8: CNN model fine-tuned on ScatterNet features for MNIST and Fashion-MNIST, with Tanh activations.
Table 9: CNN model on ScatterNet features for CIFAR- 10, with Tanh activations. In Section 4, we also use a smaller variant of this model with four convolutional layers of 16-16-32-32 filters.
Layer
Parameters
Convolution
16 filters 3x3,, stride 2, padding
Layer
Parameters
Max-Pooling
2x2, stride 1
Convolution
64 filters of 3x3, stride 1, padding
Convolution
32 filters 3x3, stride padding 1
Max-Pooling
2x2, stride
Max-Pooling
2x2, stride I
Convolution
64 filters of 3x3, stride 1, padding
Fully connected
32 units
Max-Pooling
2x2, stride
Fully connected
10 units
Fully connected
10 units
17

---

Published as a conference paper at ICLR 2021
C.3 EFFECT OF NORMALIZATION
To evaluate the effect of feature normalization Table 2, we train linear models on ScatterNet features using DP-SGD without noise 0). We train one model without feature normalization, one with Data Normalization, and three with Group Normalization (Wu & He, 2018) with G E {9, 27, 81} groups. For Group Normalization, Table reports results for the best choice of groups. The remaining hyper-parameters are given below.
Table 10: Hlper-parameters parameters for evaluating the effect of feature normalization in Table 2.
Parameter
MNIST
Fashion-MNISS
CIFAR-10
Gradient clipping norm C
0.1
0.1
0.1
Momentum
0.9
0.9
0.9
Epochs ''
20
20
20
Batch size B
512
512
512
Learning rate 1
2
4
2
Best choice groups G
27
81
27
C.4 NON-PRIVATE MODEL PERFORMANCE
For each of the model architectures described in Appendix C.2, report the best achieved test accuracy without privacy, and without any other form of explicit regularization. For MNIST and Fashion-MNIST, fine-tuning linear model CNN top of ScatterNet features results similar performance, whereas on CIFAR-10, the CNN performs slightly better. For Mushion-MNISS the end-to-end CNN performs slightly worse than the linear model (mainly due a lack of regularization). For CIFAR- 10, the end-to-end CNN significantly outperforms the ScatterNet models.
Table 11:
Test accuracy (in %) for models trained without privacy. Average and standard deviation are computed over five runs.
Dataset MNIST
SeatterNet+Linear
ScatterNet+CNN
CNN
99.3 = 0.0
99.2 + 0.0
99.2 - 0.0
Aashion-MNIST
91.5 - 0.0
91.5 + 0.2
90.1
+ 0.2
CIFAR-10
71.1 + 0.0
73.8 1 0.3
80.0 1 0.1
C.5 EVALUATING PRIVATE SCATTERNET CLASSIFIERS
We use DP-SGD with momentum for all experiments. Prior work found that the use of adaptive optimizers (c.g.. Adam (Kingma & Ba, 2015)) provided only marginal benefits for private learning (Pa- pernot et al., 2020a). Moreover, we use no data augmentation, weight decay, or other mechanisms aimed at preventing overfitting. The reason is that differential privacy is itself powerful regularizer (informally, differential privacy implies low generalization error (Dwork et al., 2015)), so our models all underfit the training data.
The table below lists the ranges syper-parameted used for the experiments in Section 3, to train linear ScatterNet classifiers, end-to-end CNNs, and CNNs fine-tuned ScatterNet features.
18

---

Published as a conference paper at ICLR 2021
Table 12: Hyper-paramettrs for the evaluation of private linear classifiers fine-tuned on ScatterNet features, CNNs fine-tuned on ScatterNet features, and end-to-end CNNs in Section 3.
Parameter
MNIST
Fashion-MNIST
CIFAR-II 10
DP guarantee (s, 6)
(3, 10
(3, 9)
(3, 10
Gradient clipping norm C
0.1
0.1
0.1
Momentum
0.9
0.9
0.9
Batch size B
{512, 1024, 16384} (14, 1. 1. 8/612
{512, 1024, 16384]
{512, 1024, 16384)
Learning rate ?)
{/4 1/2 1, 8/512
{//, 1/4 1/2, 1) B/612
Epochs T
(15, 25, 103
(15,25, 103
[30, 60, 120}
DP-SGD noise scale o
calculated numerically so that DP budget of (s, 6) is spent after 7 epochs
Group Norm. groups G Data Norm. (C1, C2, aseem)
(9. 27, 81) (0.2, 0.05, (6,8))
(9, (9,27.81 81) (0.3, 0.15, (6,8))
(9. (9,27, 21,27,11 81) (1.0, 1.5, {6,8))
In Table 13, give the set of hyper-parameters that resulted in the maximal accuracy for target DP budget of (e = 3, = 10- For each model, we report the base learning rate, before re-scaling by B/512. We find that some hyper-parameters that result in the best performance are at the boundary of our search range. Yet, as we show in Figure 8, modifying these hyper-paranne parameters results in no significant upward trend,
refrained from further increasing our search space.
Table 13: Set of paree--arameters resulting in the highest test accuracy for a privacy budget of (s = 3, 10-5). Note that we report the base learning rate (LR), before scaling by factor of B//12. SN stands for ScatterNet.
MNIST
CIFAR-10
Parameter
SN+Linear
SN+CNN
CNN SN+Linear SN+CNN CNN SN+Linear
SN+CNN
CNN
Batch size
4096
1024
512
8192
2048
2048
8192
8192
1024
Base LR 77
1/2
1/4
1/4
Epochs T
40
25
40
40
40
40
60
60
30
Groups G
27
27
Data Norm. Fnorm
8
8
C.6 MEASURING MODEL CONVERGENCE SPEED
For the experiments in Section 4, we compare the convergence of the models from Appendix C.2 when trained with and without noise, and with either low or high learning rate. The table below lists the arper-parameters for the CIFAR-10 experiment in Figure 3, as well as for the corresponding experiments for MNIST and Fashion-MNIS: clip gradients to a maximal norm of C 0.1, but omit the noise addition step of DP-SGD (and we also omit the noise when using Data Normalization).
Figure 11. When training without privacy, we still
Table 14: Plyper-parametent for the experiments on model convergence rates in Figure 3 and Figure 11.
Learning y (low, high)
Dataset
Batch size B
Gradient Norm C
Epochs T
Normalization
MNIST
512
0.1
(1/2 8)
40
Data Norm. (Fnoms 8)
Fashion-MNIST
512
0.1
(1. 16)
40
Group Norm. (G 81)
CIFAR-10
512
0.1
(14, 4)
60
Data Norm. (Anana = 8)
C.7 PRIVATE LEARNING ON LARGER DATASETS
For the experiment in Section 5.1. dataset (Torralba et al., 2008), which were collected and labeled by Carmon et al. (2019) using pre-trained CIFAR-10 classifier (see (Carmon et al., 2019, Appendix B.6) for details on the selec-
additional 500K images from the Tiny Images
19

---

Published as a conference paper at ICLR 2021
tion process for this dataset). We create datasets of size N E {10K, 25K, 50K, 100K, 250K, 550K) by taking subsets of this larger dataset. We only use the data of Carmon et al. (2019) to complement the CIFAR-10 R-10 dataset when N > 50K. As noted by Carmon et al. (2019), the additional 500K images do not entirely match the distribution of CIFAR-10 10. Nevertheless, we find that training our classifiers without privacy augmented datasets of size N 50K does not negatively impact the test accuracy on CIFAR-10.
For each training set size, we re-train our models with a hyper-parameter search. To limit computa- tional cost, and informed by our prior experiments, we fix some parameters, as shown in Table 15, When applying Data Normalization ScatterNet features, we compute the per-channel statistics only over the original CIFAR-10 samples, and compute the privacy guarantees of P Prive siivDataooo the Rényi DP analysis of the sampled Gaussian mechanism (Mironov al., 2019; Wang et al., 2019).
using
Table 15: Hyper- peppee-rrameters for the evaluation of private classifiers on larger datasets in Section 5.1.
Parameter
Value for dataset of size
DP guarantce (c,
(3, 1/2N) 0.1
Gradient norm C
Momentum
0.9
Batch size
8192
Learning rate 7)
{1/s, 1/4, 1/2, 2} 8192/512
Epochs T
{15, 30, 60, 120} 50000/N
Data Norm. params (C1, C2 Fnurm)
(1,,
The only hyper-parameters are thus the number of epochs (normalized by the size of the original CIFAR-10 data) and the learning rate y, The optimal values we found for these parameters are given below in Table 16. As we increase the dataset size, obtain better accuracy by training for more steps and with higher learning rates. Figure reports the final accuracy for these best-performing models.
Table 16: Set of hyper-parameters resulting in the highest test accuracy for privacy budget of (c = 3, = 1/2N). The test accuracy for these models are in Figure 4. Epochs are normalized by the size of the original CIFAR-10 10 dataset, so training for T epochs corresponds to training T 50,000 examples. Note that we report the base learning rate, before scaling by a factor of 8192/512.
ScatterNet+L.nng
ScatteNNa+CCN
CNN
N
Epochs T
Learning rate 1
Epochs T
Learning rate 17
Epochs T Learning rate
10K
30
1/s
60
30
25K
30
60
60
50K
60
60
60
100K
60
120
120
250K
120
120
550K
120
1
120
I
120
I
C.8
EVALUATION PRIVATE TRANSFER LEARNING
For the transfer learning experiments in Figure 5, we ResNeXt-29 model pre-trained on CIFAR-100," and a ResNet-50 model trained on unlabeled ImageNet (Deng et al., 2009) using SimCLRv2 (Chen et al., 2020b)."
To train private linear classifiers on CIFAR-10, we first extract features from the penultimate layer of the above pre-trained models. For the ResNeXt model, we obtain features of dimension 1024, and for
'The full Tiny Images dataset was recently withdrawn by its curators, following the discovery of a large number of offensive class labels (Prabhu & Birhane, 2020). The subset collected by Carmon et al. (2019) contains images that most closely match the original CIFAR-10 labels, and is thus unlikely to contain offensive content.
Pttpps: / / www.b..ww.b......eeee/aeeeeaeaaa wttpb...oo/bbbeaa/////terreeeeee "https: / // thub. com wtt.c/oo/ooooeeeeeoococoe
assi fication. neir.
20

---

Published as a conference paper at ICLR 2021
the SimCLRy2 ResNet, obtain features of dimension 4096. We then DP-SGD with a similar setup as for the linear ScatterNet classifiers, except that we do not normalize the extracted features. We also target a tighter privacy budget of (= 2, é 10 10-5). We then run tyyper-paramee search as listed below Table 17. Figure 5 shows the best test accuracy achieved for each DP budget, averaged across five runs. We further report the set of haramenassmeterss that resulted in the maximal
accuracy for the targeted privacy budget of = 2, 8 = 10 ))
Table 17: Hyper-pane sepeer-prraettrs for the evaluation of private transfer learning from CIFAR-100 (using ResNeXt model) and from unlabeled ImageNet (using a SimCLR v2 model) in Section 5.2.
Parameter
Values
Best for ResNeXt
Best for SimCLRv2
DP guarantee (s,
(2, 10
Gradient norm C
0.1
Momentum
0.9
Batch size
(512, 1024, .... 16384)
2048 2 2048/s12
1024
Learning rate
{122, 1, 2, B/612
1024/512
Epochs T
(15, 25, 403
40
40
D ADDITIONAL EXPERIMENTS AND FIGURES
D.1 ON THE EFFECT BATCH SIZES IN DP-SGD
In this section, we revisit the question of the selection of an optimal batch size for DP-SGD. their seminal work, Abadi et al. (2016) already investigated this question, and noted that the choice of batch size can have large influence on the privacy-utility tradeoff. They empirically found that for dataset of size a batch size of size approximately vN produced the best results. However, their experiments measured the effect of the batch size while keeping other parameters, including the noise multiplier a and the learning rate 7), fixed.
When training without privacy, it has been shown empirically that the choice of batch size has little effect on the convergence rate of SGD, as long as the learning rate 17 is scaled linearly with the batch argue formally and demonstrate empirically that if we use
size (Goyal et al., 2017). Hereafter, linear learning rate scaling, and fix the number of training epochs T for a target privacy budget e, then the choice of batch size also has minimal influence the performance of DP-SGD.
We first consider the effect of the sampling rate 8/vv on the noise scale required to attain a fixed privacy budget of after T epochs. There is known closed form expression for a,, it is usually estimated numerically. We empirically establish the following claim, and verify numerically that holds for our setting Figure 6: Claim D.1. Given a fixed DP budget (e, 6) to be reached after T epochs, the noise scale a as a
function of the sampling rate R/N is given by (B//N) (B/N) se c. /B/N, for some constant e 2 0.
Numerical estimate
Noise Scale
8-
18 /BJN
2-
2 2 2
2 2
2-1
Sample Rate B/N
Figure 6: Noise scale a for DP-SGD that results in a privacy guarantec of (5 = =3,6 = 10-5) after 60 training epochs, for different batch sampling rates B/N.
21

---

Published as a conference paper at ICLR 2021
Given this relation between batch size and noise scale, we proceed with similar analysis in (Goyal et al., 2017), for the case DP-SGD. Given some initial weight 0,, performing steps of DP-SGD with clipping norm C 1, batch size B, learning rate and noise scale yields:
0 = 0. -1 ΣV
<E
ge+s(x)) +N(00,021)
B
J<k
= =(0. (0.
B
Σ
g(ts(z)) + +N(0, jKK JERBEBI
E
knp² 0²
B
B
If we instead take single step of DP-SGD with larger batch size kB, linearly scaled learning rate of kn,, and an adjusted noise scale Vko (by Claim D.1), get:
O1t1 0.
Ki] kB
Σ
(x(x)) + +N(00
jek BI-
= -B:-"B 1
-
a((z)) + (N(0, 21f00² J-h B
Σ
13 I
Thus, find that the total noise in both updates is identical. Under the same heuristic assumption as in (Goyal et al., 2017) that ğr (a: ~ (t+)((r)))))))))))(()) for all j < k, the two DP-SGD updates above are thus similar. This analysis suggests that as in the non-private case (Goyal et al., 2017), increasing the batch size and linearly scaling the learning rate should have only a small effect on a model's learning curve.
We now verify this claim empirically. We follow the experimental setup in Section 3, and set a privacy budget of (s 3, 10 10-5) be reached after a fixed number of epochs T. For different choices of batch size B, we numerically compute the noise scale a that fits this "privacy schedule". For the initial batch size Bg 512, we select base learning rate v that maximizes test accuracy at epoch T. As we increase the batch size to B Bo. we linearly scale the learning rate to km.. The concrete parameters are given below:
Table 18: Hyper-parameters for comparing the convergence rate DP-SGD with different batch sizes in Figure 7.
Epochs
Batch size B
Learning rate 7
MNIST
40
(512, 1024, 2048, 4096)
1/2 8/112
Fashion-MNIST
40
[112, 1024, 2048, 4096) (512, 1024, 2048, 1096)
1. 8/12
CIFAR-10
60
1/4 8/512
As we can see in Figure 7, the training curves for CNNs trained with DP-SGD are indeed near identical across a variety of batch sizes.
Train Accuracy (%)
100
65
Train Accuracy
Train Accuracy
Batch Size
S0
904
512
40
1024
85
2048
39
4006
10
21
10
20
40
Epochs
Epochs
Epochs
(a) MNIST
(b) Fashion-MNISS
(c) CIFAR-10
Figure 7: Convergence rate of DP-SGD for different batch sizes, with fixed targeted privacy budget
of (s = 3, 30 after T 40 or T 60 epochs, and linear scaling of the learning rate 1) B B/512.
We make small simplification to our analysis here and assume that one batch of DP-SGD sampled with selection probability BB/N is identical l batches sampled with selection probability B/v.
22

---

Published as a conference paper at ICLR 2021
D.2 ANALYSIS OF PAPER-PARAMETERS
To understand the effect of varying the different parameaarseterss of DP-SGD, Figure 8 shows the median and maximum model performance for different choices of a single parameter. The median and maximum are computed over all choices for the other hyper-parameter parameters in Table 12. As we can see, the maximal achievable accuracy is remarkably stable when fixing one the algorithm' hyper-parametery parameters, with the exception of overly large batch sizes or overly low learning rates for end-to-end CNNs.
Tost Accuracy (9%
Test Accuracy (99
Test Acairacy (%0
Text Accuracy
Seateffst (wwe)
(awdee)
(M) (serler)
512
1EM
344
609
3054
05
29
b
G Geill
Batch Size
Base Learning Rate
Training Epochs
Normalization
(a) MNIST
Tedt Accuracy (%6
Test Accuracy (16)
Teat Acaurcy (1%)
Test Accuracy
R
(ma) CMR (mer))
[sedia))
18594
Base Learning Rate
Training Epochs
Normalization
Coen
Beshion-MNISS
Test Accuracy (%)
lest Accuracy (16
Test Acaracy (%)
Accuracy
Sertorke [meilr]
$15
10
Batch Size
Base Learning Rate
Training Epochs
Normalization
(c) CIFAR-10
Figure 8: Median and maximum test accuracy of linear ScatterNet classifiers and end-to-end CNNs
when we fix one hyper- syper-parameter in Table 12 and run grid-search over all others (for privacy budget of (E = 3, 6 = 10 5)).
D.3 COMPARING DP-SGD AND PRIVACY AMPLIFICATION BY ITERATION
While DP-SGD is the algorithm choice for differentially private non-convex learning, it is unclear why it should be the best choice for learning private linear models. Indeed, starting with the work of Chaudhuri et al. (2011). there have been many other proposals of algorithms for private convex optimization with provable utility guarantees, e.g., (Bassily al., 2014; Kifer al., 2012: Feldman et al., 2018). Yet, Yu et al. (2019a) show that DP-SGD can achieve higher utility than many of these approaches, both asymptotically and empirically.
Here, we take closer look at the "Privacy Amplification by Iteration" work of (Feldman et al., 2018). Feldman al. (2018) observe that DP-SGD guarantees differential privacy for every gradient update step. Under the assumption that intermediate model updates can be hidden from the adversary, they propose different analysis of DP-SGD for convex optimization problems that has a number of conceptual advantages. First, the algorithm of Feldman al. (2018) does not require the training indices selected for each batch B, do be hidden from the adversary. Second, their approach can support much smaller privacy budgets than DP-SGD.
However, we show that these benefits come at cost in practice: for the range of privacy budgets we consider in this work, DPD requires adding less noise than Privacy Amplification by Iteration (PAD). To compare the two approaches, we proceed as follows: We analytically compute the noise scale that results in privacy guarantee of (e, 5 10-5) after 10 training epochs with batch sampling rate of 512 /5000.0 12 Figure 9 shows that DP-SGD requires adding less noise, except for large
12ehe guarantees of Privacy Amplification by Iteration apply unevenly the elements of the training data. We choose the noise scale that least 99% of the data elements enjoy (s, 5)-DP.
23

---

Published as a conference paper at ICLR 2021
privacy budgets (e 40), very small ones (5 < 0.2). In the latter case, both algorithms require adding excessively large amounts of noise. We observe a qualitatively similar behavior for other sampling rates.
For completeness, we evaluate the PAI algorithm of Feldman et al. (2018) for training linear ScatterNet classifiers on CIFAR-10 10.. We evaluate broader range of paree--arameeers, including different clipping thresholds C' E {0.1, 1, 10) (PAI clips the data rather than the gradients), a wider range of batch sizes B {32, 64, .... 2048), and wider range of base learning rates 7) E {2-3, 2-22. ..... 2) We find that for privacy budgets S e S 3, the optimal hyper-parametie similar, but the analysis of PAI requires larger noise scale As a result, PAI performs worse than DP-SGD, as shown in Figure 10.
for PAI and DP-SGD are
Test Accuracy (%)
DP-SCD
70
Noise Scale
10P
PAI
60
10f
DP-5GD
PAI
10- 107
40
3
c-DP
6-DP
Figure 9: Gradient noise scale a required for a privacy guarantee of (s, 0 = 10 after 10 train- ing epochs with batch sampling rate 512 3500000.. Privacy Amplification by Iteration (PAT) (Feld- man et al., 2018) requires less noise than DP- SGD only for very small or very large privacy budgets.
Figure 10: Comparison of DP-SGD (Abadi et al., 2016) and Privacy Amplification by Iteration (PAI) (Feldman et al., 2018) 8) for training private linear ScatterNet classifier on CIFAR-10. Shows the maxinium accuracy achieved for each privacy budget, averaged over five runs.
D.4 DP-SGD WITH POISSON SAMPLING
The analysis of DP-SGD (Abadi et al., 2016; Mironov et al., 2019) assumes that each batch B, is created by independently selecting each training sample with probability B/v. This is in contrast to typical implementations of SGD, where the training data is randomly shuffled once per epoch, and divided into successive batches of size exactly B. The latter "random shuffle" approach has been used in most implementations of DP-SGD (e.g., (tensorflow/privaccy 2019; pytorch/opacus, 2020)) as well as in prior work (e.g., (Abadi et al., 2016; Papernot et al., 2020b)), with the (implicit) assumption that this difference in batch sampling strategies will not affect model performance. We verify that this assumption is indeed valid in our setting. We re-train the linear ScatterNet and end-to-end CNN models that achieved the highest accuracy for a DP budget of (e = 3, = 10-5) (with the syper-parameters detailed in Table 13), using the correct "Poisson sampling" strategy. The test accuracy of these models (averaged over five runs) are shown in Table 19. For all datasets and models, the sampling schemes achieve similar accuracy when averaged over five runs.
Table 19:
Comparison of DP-SGD with two different batch sampling schemes: (1) Poisson sampling. where batch is formed by selecting each data point independently with probability B/N; (2) Random shuffle, where the training set randomly shuffled at the beginning of each epoch, and split into consecutive batches of size B. For both sampling schemes, report the best test accuracy (in %) at a DP budget of (s = 3,5 = 10-3 10-5), with means and standard deviations over five runs.
ScatterNet
CNN
Dataset MNIST Fashion-MNe -NIIS CIFAR-10
Poisson Sampling
Random Shuffle
Poisson Sampling
Random Shuffic
98.6 + 0.1 89.6 + 0.1
98.7 = 0.0
98.0 + 0.1
98.1 +: 0.0 86.0 + 0.1
89.7 = 0.0
86.1 1 + 0.2
66.8 + 0.2
67.0 + 0.0
59.0 + 0.4
59.2 + 0.1
D.5 EXPERIMENTS WITH SMALLER END-TO-END CNN MODEL ON CIFAR-10
In Section 4, we investigate whether the dimensionality of different classifiers has a noticeable impact on their privacy-utility tradeoffs. To this end, repeat the CIFAR-10 experiments from
24

---

Published as a conference paper at ICLR 2021
Section 3 with smaller end-to-end CNN architecture. Specifically, take the end-to-end CNN architecture from Table 7 and reduce the number of filters in each convolutional layer by a factor of two and remove the last convolutional layer). This results in CNN model with comparable number of trainable parameters as the linear ScatterNet classifier (see Table 4). In Table 20, we compare the privacy-utility of this smaller CNN models with the original larger CNN model evaluated in Section 3. While the change of model architecture does affect the model accuracy. the effect is minor, and the accuracy remains far below that of the ScatterNet classifiers with a comparable number of parameters.
Table 20: Best test accuracy (in %) for two different model sizes on CIFAR-10 for DP budget of (s = 3, = 10 We compare two variants of the end-to-end CNN architecture from Table 7, with respectively 551 K and 168K parameters. Average and standard deviation computed over five runs.
Model
Parameters
Accuracy
168K
60.7 + 0.3
CNN
551K
59.2 + 0.1
D.6 MODEL CONVERGENCE SPEED ON MNIST AND FASHION-MNIST
We run the same experiment as in Figure 3 for MNIST and Fashion-MNIST, to compare the con- vergence rate of different classifiers with and without privacy, for different learning rates. The experimental setup is described in Appendix C.6. Figure 11 shows qualitatively similar results as Figure 3: with a high learning rate, all models converge quickly when trained without gradient noise, but the addition of noise is detrimental the learning process. In contrast, with much lower learning rate the training curves for DP-SGD are nearly identical, whether we add noise or not. In this regime, the ScatterNet classifiers converge significantly faster than end-to-end CNNs when trained without privacy.
Train Accuracy (%
100
100
96
04
SeatterNee-
54
NNN
92
CNN
No Noice
20
40
20
40
Epochs
Epochs
Low LR (17 = 0.5)
High LR (17 = 8.0)
(a) MNIST
Train Accuracy (%)
N
CNW
CNN
20
40
0
20
411
Epochs
Epochs
Low LR (1 = 1.0)
High LR (n = 16.0)
(b) Fashion-MNIST
Figure 11: Comparison of convergence rates of linear classifiers fine-tuned on ScatterNet features, CNNs fine-tuned on ScatterNet features), and end-to-end CNNs with and without noise addition in DP-SGD. (Left): low learning rate. (Right): high learning rate. See Figure for results on CIFAR-10.
25


Reviews:
[{"review_id": "uSXag5Z679O", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This article is about a topical issue: performance degradation of of deep learning models trained with differential privacy (DP). Clipping of the gradients and addition of the noise, required to obtain DP guarantees, blur the models such that for moderate privacy guarantees (eps~7.0) CIFAR-10 test accuracy baseline is currently ~66% (Papernot et al., 2020b).\n\nLower bounds for this degradation have been shown theoretically (e.g. Bassily et al., 2014), and there has recently been also work on circumventing this issue, see e.g.\n\nKairouz, P., Ribero, M., Rush, K. and Thakurta, A., 2020. Dimension Independence in Unconstrained Private ERM via Adaptive Preconditioning. arXiv preprint arXiv:2008.06570,\nYingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. arXiv preprint arXiv:2007.03813, 2020\n(these references are not included in the paper). \n\nAlthough this paper does not introduce fundamentally anything new for DP learning (DP-SGD + Rényi DP accountant for obtaining eps,delta-guarantees are used), it does clearly beat the state-of-the-art for small epsilon values (eps up to 3.0) for MNIST, Fashion-MNIST and CIFAR-10. This is obtained by using so called Scattering Networks (Oyallon and Mallat, 2015), which have the property of converging very fast without privacy. This phenomenon is transferred to DP learning and thus high accuracies for shorter DP-SGD runs (i.e. smaller epsilons) are obtained. \n\nAs expected, these 'handcrafted data-independent feature extractors' of Scatter Networks cannot beat CNN+DP-SGD when more private data is available, or when features can be extracted from public image data.\n\nAll in all, although I think the gist of the paper is simply combining these handcrafted feature extractors (ScatterNets) and DP-SGD, it does improve the baseline for DP CIFAR-10 for small / moderate eps-values (up to 3.0) and does provide new ideas / questions on how to improve DP learning (e.g. by accelerated convergence) also outside of image domain (handcrafted feature extraction for non-vision tasks).\n\nThe paper is very well written. A tiny remark:\nYou write \"Gaussian noise of variance sigma^2 C^2 is added to the mean gradient.\"\nNotice that sigma^2 C^2 - noise is added to the summed gradients, and sigma^2 C^2 / B^2 to the mean.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "qiypVXHx8FG", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 considers ways of improving private versions of SGD in the context of image classification. The main finding is that providing \"hand crafted\" features can significantly improve the privacy/accuracy trade-off. In some cases, even a linear model built on top of such features (like those produced by ScatterNet), can improve over differentially private SGD. A plausible explanation for this phenomenon is that extra features can reduce the number of iterations required in SGD, resulting in better privacy and/or less noise. (It is also argued that having much more data similarly improves the trade-off, but this is unsurprising and, it seems, has been observed before by McMahan et al.)\n\nThe paper is quite well-written, and I found it easy to follow even though this is not my area of expertise. I also like that it presents a number of possible directions for further improving private SGD, including transfer learning from related, public data sets, and second-order optimization.\n\nA possible criticism is that in principle the \"hand crafted\" features may have been built based on empirical work on MNIST and CIFAR-10, and the same goes for the architecture choices, so in theory there could be some privacy leakage from these choices. It would have been more impressive to demonstrate effectiveness of a newer data set, not known when ScatterNet and the used CNN architectures were proposed.\n\nTwo final comments:\n- \"Unlearned\" usually means that you have (deliberately) forgotten something, so it is not the same as \"not learned\".\n- It would be interesting to consider the setting where just the image *label* is private. Has DP SGD been considered in that setting?", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZYyQCdSCMT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 shows that linear model on top of ScatterNet can outperform CNN for DPSGD training on a few generic image classification tasks. It analyzed the results, provides hypotheses to explain it, and concludes that more data / better feature is needed for DPSGD training.\n\nPeople have been searching for good models for DPSGD training, so it is nice to see a new baseline (ScatterNet + linear model) that is simple but performs better. This can be pretty valuable for researchers and practitioners in the field.\nThe paper also did some quite interesting experiments to explain the advantage of ScatterNet + linear model and to suggest directions to improve DPSGD training. The experiments and discussions on the learning rate are quite interesting and inspiring to me. However, I feel like the results for having more data / transfer learning is not so surprising, though the experiments with models different from previous work are valuable.\n\nMore detailed comments:\n- In Sec 4 \"smaller models are not easier to train privately\", you mentioned that the CNN is smaller than the linear model, so dimensionality is not an explanation for ScatterNet + linear's better performance. But I guess convex model (or maybe shallow model) might have some fundamental difference from nonconvex (or maybe deeper model). Maybe you could try something deeper than linear but shallower than the CNN to see if there is a sweet spot in between.\n- In Sec 4 \"Models with handcrafted features converge faster without privacy\", I guess the results can be explained by the fact that simpler model (linear) has a lower capacity than more complicated model (CNN) so requires less training time even with lower learning rate. So maybe again it would worth trying something in between linear and CNN.\n- In Sec 5.2, you showed results that are much better than previous results with transfer learning. It seems like the main difference is the model architecture. Is that the case? Do you have any comment on that?\n\nThe presentation is clear in general. I would love to see more details about ScatterNet as that is the important component of the proposed method.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "U5WeIre4ggR", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an analysis of differential privacy in machine learning, with a focus on neural networks trained via differentially private stochastic gradient descent (DPSGD). The main focus and the message in the paper is that the handcrafted features work better compared to learned features during training of NNs and having more training data results in better outcomes (i.e. a better privacy-utility trade-off).\n\nStarting with the latter, this is apparent from the noise formulation in DPSGD, where the noise is reduced via sampling probability, which decreases as the data size grows. Hence, I do not consider this as a new insight or a contribution. Unless, I have misunderstood something, in which case, please do explain.\n\nFor the former, as the final model used (Table 3 and Figure 1) is a linear classifier, it outperforming an end-to-end CNN based model is intuitive, as it has far fewer number of parameters (which improve the noise scale, due to smaller gradient norm). This is slightly touched upon in subsection \"Training CNNs on handcrafted features\", where the comparison is made using CNNs on the handcrafted features, however there are no detailed results presented in the paper, I would have liked to see a similar table and figures as earlier.\n\nThe presentation of results (Table 3) is a bit strange. I would have further liked to see the comparison of both models on the *same* set of hyperparameters. Also, instead of stating that hyperparameter search's privacy budget was not accounted for as in prior works, it would have been nice to see some analysis, such as the section D(Appendix) in Abadi et al.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a very interesting investigation. While deep neural networks are typically best in non-private settings, the authors show that linear models with handcrafted features (ScatterNets) perform better in certain settings of the privacy parameter. The reviewers all found this to be important and insightful, with a thorough investigation, and I tend to agree, recommending acceptance.
Decision: Accept (Spotlight)