Do not Let Privacy Overbill Utility:  Gradient Embedding Perturbation for Private Learning
Authors: Da Yu
Huishuai Zhang
Wei Chen
Tie-Yan Liu
Venue: ICLR 2021 Poster (2021)
Keywords: privacy preserving machine learning
differentially private deep learning
gradient redundancy

Abstract: The privacy leakage of the model about the training data can be bounded in the differential privacy mechanism. However, for meaningful privacy parameters, a differentially private model degrades the utility drastically when the model comprises a large number of trainable parameters.  In this paper, we propose an algorithm  \emph{Gradient Embedding Perturbation (GEP)} towards training differentially private deep models with decent accuracy. Specifically, in each gradient descent step, GEP first projects individual private gradient into a non-sensitive anchor subspace, producing a low-dimensional gradient embedding and a small-norm residual gradient. Then, GEP perturbs the low-dimensional embedding and the residual gradient separately according to the privacy budget. Such a decomposition permits a small perturbation variance, which greatly helps to break the dimensional barrier of private learning. With GEP, we achieve decent accuracy with low computational cost and modest privacy guarantee for deep models.  Especially, with privacy bound $\epsilon=8$, we achieve $74.9\%$ test accuracy on CIFAR10 and $95.1\%$ test accuracy on  SVHN, significantly improving over existing results.

Published as a conference paper at ICLR 2021
Do NOT LET PRIVACY OVERBILL UTILITY: GRADIENT EMBEDDING PERTURBATION FOR PRIVATE LEARNING
Da Yuu.. Huishuai Zhang Wei Chen?, Yan Liu?
1 School of Computer Science and Engineering, Sun Yat-sen University
2 Microsoft Research Asia
yyuda3@ma i 12. sysu. edu. en
2 huzhang, wche, ty Syliu/ mwmicrooof..oomm com
ABSTRACT
The privacy leakage of the model about the training data can be bounded in the differential privacy mechanism. However, for meaningful privacy parameters, differentially private model degrades the utility drastically when the model comprises a large number of trainable parameters. In this paper, we propose an algorithm Gradient Embedding Perturbation (GEP) towards training differentially private deep models with decent accuracy. Specifically, in each gradient descent step, GEP first projects individual private gradient into non-sensitive anchor subspace, producing a low-dimensional gradient embedding and a small-norm residual gradient. Then, GEP perturbs the low-dimensional embedding and the residual gradient separately according to the privacy budget. Such a decomposition permits a small perturbation variance, which greatly helps to break the dimensional barrier of private learning. With GEP, we achieve decent accuracy with reasonable computational cost and modest privacy guarantee for deep models. Especially, with privacy bound 8, achieve 74.9% test accuracy CIFAR1O and 95.1% test accuracy on SVHN, significantly improving over existing results.
INTRODUCTION
Recent works have shown that the trained model may leak/memorize the information of its training
set (Fredrikson al.) 2015 Wu et al., 2016; (hhkri et al. 2017 Hitaj et al. 2017), which raises privacy issue when the models are trained with sensitive data. Differential privacy (DP) mechanism provides a way to quantitatively measure and upper bound such information leakage. It theoretically ensures that the influence of any individual sample is negligible with the DP parameter or (c, (). Moreover, it has been observed that differentially private models can also resist model inversion attack (Carlini et al. ) membership inference attack (Rahman al., 2018 Bernau ct al. 2019
Sablayrolles et al. 2019 Yu et al.. 202I), gradient matching attack (Zhu et al. 2019), and data poisoning attack (Ma et al. 2019).
One popular way to achieve differentially private machine learning is to perturb the training process with noise (Song et al. 2013 Bassily et al., 2014; Shokri & Shmatikov) 2015 Wu et al. 2017 Fukuchi et al. 2017;] Lyngarr et al. [019:] Phan et al. (020). Specifically, gradient perturbation each iteration of (stochastie) gradient descent algorithm and guarantees
perturbs the gradient the privacy of the final model via composition property of DP. It is worthy to note that gradient perturbation does not assume (strongly) convex objective and hence is applicable various settings (Abadi et al. 2016 Wang et al. 2017 Lee & Kifer 2018 Jayaraman et al. [0018] Waag & Gu 2019) Yu et al. 2020). Specifically, for given gradient sensitivity S. general form of gradient perturbation is to add an isotropic Gaussian noise z to the gradient E R independently for each step,
g 2, where z ~ N S Ipxp)
(1)
One can set proper variance 2 to make each update differentially private with parameter (c, 8). It easy to see that the intensity of the added noise [[[|=||?] scales linearly with the model dimension p.
Authorrs contrihute equally this work.

---

Published as a conference paper at ICLR 2021
25
5H-R 5P-R nasse
Input layer, p
First Fist p 138224
10
Linear liyer 640
40 60
50
Hodd Namee
Tra prog
Figure 1: Noise norm vs gradient norm of ResNet20 at initialization. The noise variance is chosen such that SGD sat- isfies (5. 10 10-")-D? DDDP after 90 epochs in Abbdi et al. (2016).
Figure 2: Stable rank ||- 11/ -I (Tropp jet al. 2015) of batch gradient matrix of given groups (with p parameters). The setting is ResNet20 on CIFAR-10. The stable rank is small throughout training.
This indicates that as the model becomes larger, the useful signal, i.e., gradient, would be submerged in the added noise (see Figure This dimensional barrier restricts the utility of deep learning models trained with gradient perturbation.
The dimensional barrier is attributed to the fact that the added noise is isotropic while the gradients live on a very low dimensional manifold, which has been observed in (Gur-Ari et al. (0118) Vogels
et al. 2019; Gooneratne et al. 2020 Li et al. 2020) and is also verified in Figure 2 for the gradients of a 20-layer ResNet (He et al. 2016). Hence to limit the noise energy, it is natural to think
"Can we reduce the dimension of gradients first and then add the isotropic noise onto -ineennnsional gradient embedding?"
The answer is affirmative. We propose new algorithm Gradient Embedding Perturbation (GEP), illustrated in Figure Specifically, we first compute anchor gradients on some non-sensitive auxiliary data, and identify an anchor subspace that is spanned by several top principal components of the anchor gradient matrix. Then we project the private gradients into the anchor subspace and obtain low-dimensional gradient embeddings and amall-norm residual gradients. Finally, we perturb the gradient embedding and residual gradient separately according to the sensitivities and privacy budget.
We intuitively argue why GEP could reduce the perturbation variance and achieve good utility for large models. First, because the gradient embedding has a very low dimension, the added isotropic noise on embedding has small energy that scales linearly only with the subspace dimension. Second, if the anchor subspace can cover most of the gradient information, the residual gradient, though high dimensional, should have small magnitude, which permits smaller added noise to guarantee the same level privacy because of the reduced sensitivity. Overall, we can use much lower perturbation compared with the original gradient perturbation to guarantee the same level of privacy.
We emphasize several properties of GEP. First, the non-sensitive auxiliary data assumption is weak. In fact, GEP only requires a small number of non-sensitiv unlabeled data following a similar feature distribution the private data, which often exist even for learning on sensitive data. In experiments, we use a few unlabeled samples from ImageNet to serve as auxiliary data for MNIST, SVHN, and CIFAR- 10. This assumption is much weaker than the public data assumption in previous works (Papernot et al. 2017 2018 Alon et al. 2019; Wang & Zhou 2020), where the public data should Tollow exactly the same distribution the private data. Second, GEP produces an unbiased estimator of the target gradient because of releasing both the perturbed gradient embedding and the perturbed residual gradient, which turns out be critical for good utility. Third, we use power method to estimate the principal components of anchor gradients, achievable with a few matrix multiplications. The fact that GEP not sensitive to the choices of subspace dimension further allows very efficient implementation.
Compared with existing works of differentially private machine learning, our contribution can be summarized as follows: (1) we propose novel algorithm GEP that achieves good utility for large models with modest differential privacy guarantee; (2) we show that GEP returns an unbiased estimator of target private gradient with much lower perturbation variance than original gradient perturbation; (3) we demonstrate that GEP achieves state-of-the-an utility in differentially private learning with three benchmark datasets. Specifically, for GEP achieves 74.9% test accuracy
2

---

Published as a conference paper at ICLR 2021
Private Gradients R
Gradiient Linductiings B
Aggregation
Perturbed Emloeddi e (RR)
Private citaset
Porturbation
Revusstention i'e
Go!
Biased Estimation (G' W/
Auxilaary data random labels
Projection
Ralease W B +
Anchor Gredien.
PLAvia
Subapace
Residial Gradients (IRlll oc ([G]l])
Aggregation &
Perturbed Gradion:
Power Method
* (8 e ga R p)
Perturbation
(f RP)
Assotattios:
Mer-sensttive
Diforrvtillly cuppte
Figure 3: Overview of the proposed GEP approach. 1) We estimate an anchor subspace on some non-sensitive data; 2) We project the private gradients into the anchor subspace, producing low- dimensional embeddings and residual gradients; 3) We perturb the gradient embedding and residual gradient separately to guarantee differential privacy. The auxiliary data are only required to share similar features the private data. In our experiments, we use 2000 images from ImageNet as auxiliary data for MNIST, SVHN, and CIFAR- 10 datasets.
on CIFAR-10 with a ResNet20 model. To the best of our knowledge, GEP is the first algorithm that can achieve such utility with training deep models from scratch for a "single-digi"" privacy budge
1.1 RELATED WORK
Existing works studying differentially private machine learning in high-dimensional setting can be roughly categorized into two sets. One is treating the optimization of the machine learning objective as whole mechanism and adding noise into this process. The other one is based on the knowledge transfer of machine learning models, which trains a differentially private publishable student model with private signals from teacher models. We review them one by one.
Differentially private convex optimization in high-dimensinn dimensional setting has been studied extensively over the years (Kifer et al., 2012: Thakurta & Smith [2013] Talwar et al., [005 Wang & Xu 2019 Wang & Gu, 2019). Although these methods demonstrate good utility on some convex settings, their analyses can not be directly applied to non-convex setting. Right before the submission, we note two independent and concurrent works (Zhou et al. 2020. Kairouz et al.] 2020) that also leverage the gradient redundancy to reduce the added noise. Specifically, Kairouz et al. (020)) track historical gradients to do dimension reduction for private AdaGrad. Zhou et al. (2020) requires gradients on some public data and then project the noisy gradients into a public subspace at each update. One core difference between these two works and GEP is that we introduce residual gradient perturbation and GEP produces an unbiased estimator of the private gradients, which is essential for achieving the superior utility. Moreover, we weaken the auxiliary data assumption and introduce several designs that significantly boost the efficiency and applicability of GEP.
One recent progress towards training arbitrary models with differential privacy is Private Aggregation of Teacher Ensembles (PATE) (Papernot al. 2017 2018 Jordon et al. 2019). PATE first trains independent teacher models on disjoint shards of private data. Then it trains a student model with privacy guarantee by distilling noisy predictions of teacher models on some public samples. In comparison, GEP only requires some non-sensitive data that have similar natural features as the private data while PATE requires the public data follow exactly the same distribution as the private data and in practice it uses portion of the test data to serve as public data. Moreover, GEP demonstrates better performance than PATE especially for complex datasets, c.g., CIFAR- 10, because GEP can train the model with the whole private data rather than small shard of data.
2 PRELIMINARIES
We introduce some notations and definitions. We use bold lowercase letters, e.g., v, and bold capital letters, e.g., M, to denote vectors and matrices, respectively. The L norm of a vector v is denoted by ||a||. The spectral norm and the Frobenius norm of matrix M are denoted by |M and | [|r. respectively. A sample d = (x, y) consists of feature x and label y. A dataset is a collection of individual samples. A dataset ID' is said to be neighboring dataset of ID if they differ in
Abadi al. 2016) achieve 73% accuracy on CIFAR-10 but they need to pre-train the model CIFAR-100.
3

---

Published as a conference paper at ICLR 2021
single sample, denoted D ~ D'. Differential privacy ensures that the outputs of an algorithm neighboring datasets have approximately indistinguishable distributions.
Definition ((e, 6)-DP (worr et al. 2006a b)). A randomized mechanism M guarantees (c, 6)- differential privacy for any two neighboring input datasets DD ~ TTi and for any subset of outpuas S it holds that PD) E S] S PrPr(((D) E S] + 6.
By its defimition, (c, dDP controls the maximum influence that any individual sample can produce. One can adjust the privacy parameters to trade off between privacy and utility. Differential privacy is immune to post-processing (Dwork et al.) 2014), i.e., any function applied on the output of a differentially private algorithm would not increase the privacy loss long as it does not have new interaction with the private dataset. Differential privacy also allows composition, i.c., the composition of a series of differentially private mechanisms also differentially private but with different parameters. Several variants of (c, 8)-DP have been proposed (Bun & Steinke 2016) Dong al. 2019) to address certain weakness of (c, (e. e.g., they achieve better composition property. In this work, we use Rényi differential privacy (Mironov 2017) to track the privacy loss and then convert to (e,
Suppose that there is a private dataset TD = (m,, U1) }/ with samples. We want to train model learn the mapping D.. Specifically, f takes x as input and outputs a label y, and f has parameter 0 E RP. The training objective is to minimize an empirical risk > Zi=1 (a)())), 21), where ((:-)) a loss function. We further assume that there an auxiliary dataset D)aa) {(ēy, By 3y that ã shares similar features as æ in DD while ÿ could be random.
GRADIENT EMBEDDING PERTURBATION
An overview of GEP is given in Figure GEP has three major ingredients: 1) first, estimate an anchor subspace that contains the principal components of some non-sensitive anchor gradients via power method; 2) then, project private gradients into the anchor subspace and produce low-dimensional embeddings of private gradients and residual gradients; 3) finally, perturb gradient embedding and residual gradient separately to establish differential privacy guarantee. In Section [3.]] we present the GEP algorithm in detail. In Section 3.2. we given analysis the residual gradients. In Section 3.3 we give a differentially private learning algorithm that updates the model with the output of GEP.
3.1 THE GEP ALGORITHM AND ITS PRIVACY ANALYSIS
The pseudocode of GEP is presented in Algorithm I and set of basis vectors as matrices with each row being one gradient/basis vector.
For convenience, we write a set of gradients
The anchor subspace is constructed as follows. We first compute the gradients of the model on an auxiliary dataset ((a)) with m samples, which is referred to as the anchor gradients G(a) E mmxp, We then use the power method to estimate the principal components of ((a) to construct a subspace basis B E kxp,, which is referred to as the anchor subspace. All these matrices are publishable because (aaa) is non-sensitive. We expect that the anchor subspace B can cover most energy of private gradients when the auxiliary data are not far from private data and m, & are reasonably large.
Suppose that the private gradients are G E RaXp, Then, we project the private gradients into the anchor subspace B. The projection produces low-dimensional embeddings W = GBB and residual gradients R G B B. The magnitude of residual gradients is usually much smaller than original gradient even when l is small because of the gradient redundancy.
T
Then, we aggregate the gradient embeddings and the residual gradients, respectively. We perturb the aggregated embedding and the aggregated residual gradient respectively to guarantee certain differential privacy. Finally, we release the perturbed embedding and the perturbed residual gradient and construct an unbiased estimator of the private gradient: ö == (w B + r)/n. This construction process does not resulting in additional privacy loss because of DP's post-processing property. The privacy analysis of the whole process of GEP is given in Theorem 3.1
Theorem 3.1. Let S₁ and S₂ be the sensitivity of w and r, respectively. the output of Algorithm] 7 satisfies (c, D)D for any E (0, 1) and < 2oog(1 /8) if we choose 0n 2 25, /2log(1/5)) and and
02 > 252 log(1/8)/
4

---

Published as a conference paper at ICLR 2021
Algorithm 1: Gradient embedding perturbation
1: Input: anchor gradients ((a) E IP; number of basis vectors k; private gradients G E Ruxp;
clipping thresholds 51, S2; standard deviations 01, σ2; number of power iterations t.
2: I/iistt stage: Compute an orthonormal basis for the anchor subspace.
3: Initialize B E *R* randomly.
4: for 1 to do
5: Compute A G(a) B" and B = A G(a).
6: Orthogonalize B and normalize row vectors.
7: end for
8: Delete G(a) free memory.
9: //Scoon stage: project the private gradients G into anchor subspace B
10: Compute gradient embeddings W GB and clip its rows with S to obtain W.
11: Compute residual gradients R = G - WB B and clip its rows with S₂ to obtain R.
//Third stage: perturb gradient embedding and residual gradient separately
13: Perturb embedding with noise (11) ~ (0, of Ixxk): up = E. W..: vb = w 211.
14: Perturb residual gradient with noise x(2) ~ NN r : Σ, R i ;: r (2)
15: Return e = (wo B + f)/n.
A common practice to control sensitivity is to clip the output with pre-defined threshold. In our experiments, we use different thresholds S₁ and S₂ to clip the gradient embeddings and residual gradients, respectively. The privacy loss of GEP consists of two parts: the privacy loss incurred by releasing the perturbed embedding and the privacy loss incurred by releasing the perturbed residual gradient. We compose these two parts via the Rényi differential privacy and convert it to (e, 8DD.
We highlight several implementation techniques that make GEP widely applicable and implementable with reasonable computational cost. Firstly, auxiliary non-sensitive data do not have to be the same source as the private data and the auxiliary data can be randomly labeled. This non-sensin non-sensitive data assumption is very weak and easy to satisfy in practical scenarios. To understand why random label works, a quick example is that for the least squares regression problem the individual gradient is aligned with the feature vector while the label only scales the length but does not change the direction. This auxiliary data assumption avoids conducting principal component analysis (PCA) on private gradients, which requires releasing private nigh-dimensional basis vectors and hence introduces large privacy loss. Secondly. we use power method (Panjul 2011; Vogels et al. 2019) to approximately estimate the principal components. The new operation we introduce is standard matrix multiplication that enjoys efficient implementation on GPU. The computational complexity of each power iteration 2mkp,, where p is the number of model parameters, m is the number of anchor gradients and is the number of subspace basis vectors. Thirdly, we divide the parameters into different groups and compute one orthonormal basis for each group. This further reduces the computational cost. For example, suppose the parameters are divided into two groups with size P1. P2 and the numbers of basis vectors are k1, k2. the computational complexity of each power iteration is 2m + k2p2), which is smaller than 2m(k; + k2) (p) + P2). In Appendix B analyze the additional computational and memory costs of GEP compared to standard gradient perturbation.
Curious readers may wonder if can use random projection reduce the dimensionality as Dohnsonn-Lindesstraas Lemma (Dasgupta & Gupta 2003) guarantees that one can preserve the pairwise distance between any two points after projecting into a random subspace of much lower dimension. However, preserving the pairwise distance is not sufficient for high quality gradient reconstruction, which is verified by the empirical observation in Appendix
3.2 AN ANALYSIS ON THE RESIDUAL GRADIENTS OF GEP
Let g : - be the target private gradient. For a given anchor subspace B, the residual gradients are defined as R = - GB" B. We then analyze how large the residual gradients could be. The following argument holds for all time steps and we ignore the time step index for simplicity.
5

---

Published as a conference paper at ICLR 2021
For the ease of discussion, introduce E. (G.,)² for i E [n] to denote the the private gradients and the E == ( for j E [m] to denote the anchor gradients. We use (x) to denote the kt largest eigenvalue of a given matrix. We assume that the private gradients E Sn and the anchor gradients Ei,..., S.. are sampled independently from a distribution P. We assume E == E Rexp to be the population gradient (uncentered) covariance matrix. We also consider the (uncentered) empirical gradient covariance matrix S := m 2.=1,:C?
One case is that the population gradient covariance matrix Σ is low-rank k. In this case that the residual gradients are 0 once the number of anchor gradients m > k.
argue
Lemma 3.1. Assume that the population covariance matrix E is with rank k and the distribution P satisfies P(g E F,)= = for all s-flats F, in R2 with O S < k. Let E VAAV, and S = V. be the eigendecompositions of E and the empirical covariance matrix $, respectively, such that Av. (S) > 0 and (5) = 0. Then mm 2 k. we have with probability 1.
= and V|VVV V.V. 1l2 =.
Proof. The proof is based on the non-singularity of covariance matrix. See Appendix D
We note that s-flat is the translate F, x + (0)) of an s-dimensional linear subspace IF Fo) in I& and the normal distribution satisfies such condition (Eaton Perlman 1973] Muirhead (009). Therefore, we have seen that for low-rank case of population covariance matrix, the residual gradients are 0 once m > k. the general case, we measure the expected norm of the residual gradients.
Lemma 3.2. Assume that & ~ P and ||E|I² < T almost surely. Let Σ = VAVT be the eigendecom- position of the population covariance matrix E. Let S = V.AV K be the eigendecomposition of the empirical covariance matrix S. Then we have with probability
2 exp(--)).
BI[g - 11 (5)1 <
(x)
+ kkC/m + T / 20/m,
(3)
where = |E|E|| - EE
16 {3(5) Iv is a projection operator
onto the subspace Vx and the E is taken over the randommess of ~ P.
Proof. The proof is an adaptation of Theorem 3.1 in Blanchard et al. (2007).
From Lemma 3.2 we can the larger the number of anchor gradients and the dimension of the anchor subspace k, the smaller the residual gradients. We can choose m, k properly such that the upper bound the expected residual gradient norm is small. This indicates that may smaller clipping threshold and consequently apply smaller noises with achieving the same privacy guarantee.
We next empirically examine the projection error = Σ, R.,: by training a 20-layer ResNet on CIFARIO dataset. We try two different types of auxiliary data to compute the anchor gradients: 1) samples from the same source as private data with correct labels, i.e., 2000 random samples from the test data; 2) samples from different source with random labels, i.c., 2000 random samples from ImageNet. The relation between the dimension of anchor subspace i and the projection error rate [1 [[ is presented in Figure 4 We can see that the project error is small and decreases with k, and the benefit of increasing l diminishes when is large, which is implied by Lemma 3.2 In practice one can only use small or moderate & because of the memory constraint. GEP needs to store at least A individual gradients and each individual gradient consumes the same amount of memory as the model itself. Moreover, we can see that the projection into anchor subspace of random labeled auxiliary data yiclds comparable projection error, corroborating our argument that unlabeled auxiliary data are sufficient for finding the anchor subspace.
We also verify that the redundancy of residual gradients is small, by plotting the stable rank of residual gradient matrix in Figure 5 The stable rank of residual gradient matrix is order of magnitude higher than the stable rank of original gradient matrix. This implies that it could be hard to further approximate R with oow-dimensional embeddings.
We next compare the GEP with a scheme that simply discards the residual gradients and only outputs the perturbed gradient embedding, i.e., the output is u : th B B/n.

---

Published as a conference paper at ICLR 2021
Random labels
True labels
35
Approumation ener (in 60
== 500
150
25-
8 2000
100
tresttunt)
20-
Map MyJ
10-
500
6- 2000
25 50
75
100
20 40
60
0
20
40
60
Trwining progress
Training progress
Training progress
Figure 5: Stable rank of the residual gradient matrix versus original gradient matrix. The gradients are computed on full batch data for the first stage in ResNet20. The dimension of an- chor subspace is k 1000.
Figure 4: Relative projection error | / (gl))) of the second stage in ResNet20. The number of anchor gradients is 2000. The dimension of anchor subspace is k. The learning rate is decayed by 10 epoch 30. The left plot uses random samples from ImageNet. The right plot uses random samples from test data. The benefit of increasing k becomes smaller when k larger.
Remark 1. Let u w B/n be the reconstructed gradient from noisy gradient embedding and be the outpul of GEP. If ignoring the effect of gradient clipping, we have
E ū g r/n,
D
g.
(4)
where r E, Ru. the aggregated residual gradients, w are given in Algorithm and the expectation is over the added random noises.
This indicates that û contains a systematic error that makes á always deviate from g by the residual gradient. This systematic error the projection error, which is plotted in Figure 4 The systematic error cannot be mitigated by reducing the noise magnitude (e.g.. increasing the privacy budget or collecting more private data). We refer to the algorithm releasing ú directly as Biased-GEP or B-GEP for short, which can be viewed as efficient implementation of the algorithm in (Zhou et al. 2020). In our experiments, B-GEP can outperform standard gradient perturbation when is large but is inferior GEP. We note that the above remark is made with ignoring the clipping effect (or large clipping threshold). In practice, we do apply clipping for the individual gradients at each time step, which makes the expectations in Remark obssure (Chen al. 2020b). We note that the claim that ú is an unbiased estimator of g is not that precise when applying gradient clipping.
3.3 PRIVATE LEARNING WITH GRADIENT EMBEDDING PERTURBATION
GEP (Algorithm) T describes how to release one-step gradient with privacy guarantee. this section, compose the privacy losses at each step establish the privacy guarantee for the whole learning process. The differentially private learning process with GEP is given in Algorithm 2 the privacy analysis is presented in Theorem 3.2
Algorithm 2: Differentially private gradient descent with GEP.
Input: private dataset ID;; auxiliary dataset ID(a); number of updates T; learning rate ry; configuration of GEP C; loss function f; 2: Output: Differentially private model 0T.
3: for = 0 to T 1 do
4: Compute the private gradients G, and anchor gradients G. of loss with respect to 0,.
5: Call GEP with G,, G!") and configuration C to get ör.
6: Update model 0 0: no,-
7:
end for
Theorem 3.2. For any < 2 llg(1/8) and 6 (0,1), 1), the output of Algorithmm 2 satisfies (e, 6)-DP if
> 2 2T log(1/8)/e.
7

---

Published as a conference paper at ICLR 2021
If the private gradients are randomly sampled from the full batch gradients, the privacy guarantee can be strengthened via the privacy amplification by subsampling theorem of DP (Balle et al. 2018))
Wang al. 2019 Zhu & Wang 2019; Mironov et al. 2019). Theorem 3.3 gives the expected excess error of Algorithm 2 Expected excess error measures the distance between the algorithm's output and the optimal solution in expectation.
Theorem 3.3. Suppose the loss T.(0) 1 ((.))eD ((J((r),)) y) is 1-Lipschitz, convex, and 9-
smooth.
If 1
n3e
and O + Or then we have BB[T(()] - I((O)) s
VB'
O of residual gradient at step t.
(18((118)) PVplog where i = 7 Et= ri and = max, (R.l) is the sensitivity
The F term represents the average projection error over the training process. The previous best expected excess error for gradient perturbation is (/////ooo///////// (Wang et al. 2017). As shown in Lemma 3.T if the gradients locate in a k-dimensional subspace over the training process, i = 0 and the excess error is O ((Vk) 1og(1/8)/(ne)) independent of the problem ambient dimension p. When the gradients are in general position, i.e., gradient matrix is not exact low-rank, Lemma 3.2 and the empirical result give a hint on how small the residual gradients could be. However, it is hard to get a good bound on max; [| ((::).:: and the bound in Theorem 3.3 does not explicitly improve over previous result. One possible solution is to use a clipping threshold based on the expected residual gradient norm. Then the output gradient becomes biased because of clipping and the utility/privacy guarantees in Theorem 3.3 3.2 require new elaborate derivation. We leave this for future work.
4 EXPERIMENTS
We conduct experiments MNIST, extended SVHN, and CIFAR-10 datasets. Our implementation is publicly available" The model for MNIST has two convolutional layers with max- max-pooling and one fully connected layer. The model for SVHN and CIFAR-10 is ResNet20 in HH et al. (2016). We replace all batch normalization (loffe & Szegedy 2013) layers with group normalization (Wu & He
2018) layers because batch normalization mixes the representations of different samples and makes the privacy loss cannot be analyzed accurately. The non- non-private accuracy for MNIST, SVHN, and CIFAR- 10 is 99.1 %, 95.9%, and 90.4%, respectively.
We also provide experiments with pre-trained models in Appendix A Tramer & Boneh (020) show that differentially private linear classifier can achieve high accuracy using the features produced by pre-trained models. We examine whether GEP can improve the performance of such private linear classifiers. Notably, using the features produced by a model pre-trained on unlabeled ImageNet, GEP achieves 94.8% validation accuracy CIFARIO 10 with 2.
Evaluated algorithms We use the algorithm in Abadi et al. (2016) as benchmark gradient perturba- tion approach, referred to as "GP". We also compare GEP with PATE (Papernot al.) (017). We run the experiments for PATE using the official implementation. The privacy parameter e of PATE is data-dependent and hence cannot be released directly (see Section 3.3 in Papernot al. (2017)) Nonetheless, we report the results of PATE anyway.
Implementation details At each step, GEP needs to release two vectors: the noisy gradient em- bedding and the noisy residual gradient. The gradient embeddings have a sensitivity of S and the residual gradients have sensitivity of S2 because of the clipping. The output of GEP can be constructed as follows: (1) normalize the gradient embeddings and residual gradients by 1/S, and 1/S², respectively, (2) concatenate the rescaled vectors, (3) release the concatenated vector via gaussian mechanism with sensitivity v2. (4) rescale the two components by S1 and S2. B-GEP only needs to release the normalized noisy gradient embedding. We use the numerical tool in Mironov et al. 2019) to compute the privacy loss. For given privacy budget and sampling probability, a is set to be the smallest value such that the privacy budget is allowable to run desired epochs.
All experiments are run on a single Tesla V100 GPU with 16G memory. For ResNet20, the parameters divided into five groups: input layer, output layer, and three intermediate stages. For given quota of basis vectors, we allocate it to each group according to the square root of the number of parameters in each group. We compute orthonormal subspace basis on each group separately.
httpp::/gitthb.... howp:/ttahooooommauilaalamalllla 1/rrayiill//rrirrea Geradienttt--eerrrre knbeddi Parturrratia
8

---

Published as a conference paper at ICLR 2021
Table 1: Test accuracy (in %) with varying choices of privacy bound denote the improvement over GP baseline.
The numbers under symbol A
Dataset
Algorithm
< 2
A
A
8
A
GP
94.7
+0.0
96.8
+0.0
97.2
+0.0
PATE
98.5
+3.8
98.5
+1.7
98.6
+1.4
MNIST
B-GEP
93.1
-1.6
94.5
-2.3
95.9
-1.3
GEP
96.3
+1.6
97.9
+1.1
98.4
+1.2
GP
87.1
+0.0
91.3
+0.0
91.6
+0.0
PATE
80.7
91.6
+0.3
91.6
SVHN
B-GEP
88.5
+1.4
91.8
+0.5
92.3
+0.7
GEP
92.3
+5.2
94.7
+3.4
95.1
+3.5
GP
43.6
+0.0
52.2
+0.0
56.4
+0.0
CIFAR-10
PATE
34.2
9.4
41.9
-10.3
43.6
-12.8
B-GEP
50.3
+6.7
59.5
+7.3
63.0
GEP
59.7
+16.1
70.1
+17.9
74.9
+18.5
CIFARSD, C-8
SWI C
Syith,
70
55
00
037
180
582
1640
1150
2000
-23
1562
19:8
2003
2003
2002
Figure 6: Test accuracy when varying the dimension of anchor subspace. GEP significantly outper- forms B-GEP for all k. Moreover, the performance of GEP is not that sensitive to k.
Then we concatenate the projections of all groups to construct gradient embeddings. The number of power iterations t is set empirical evaluations suggest more iterations do not improve the performance for GEP and B-GEP.
For all datasets, the anchor gradients are computed 2000 random samples from ImageNet. In Appendix([) C we examine the influence of choosing different numbers of anchor gradients and different sources of auxiliary data. The selected images MNIST) and we label them randomly at each update. For SVHN and CIFAR-10, is chosen from [500, 1000, 1500, 2000]. For MNIST, halve the size k. We use SGD with momentum 0.9 as the optimizer. Initial learning rate and batchsize are 0.1 and 1000, respectively. The learning rate is divided by 10 middle training. Weight decay is set as 1 10 14-4, The clipping threshold for is 10 for original gradients and 2 for residual gradients. The number of training epochs for CIFAR- 10 and MNIST is 50, 100, 200 for privacy parameter 2, 5, 8, respectively. The number of training epochs for SVHN is 5, 10, 20 for privacy parameter = 2, 5. 8, respectively. Privacy parameter 5 is x 10-6 for SVHN and 10-5 for CIFAR-10 and MNIST.
downsampled into size of 32 32 (28 28 for
Results The best accuracy with given is in Table 4 For all datasets, GEP achieves considerable improvement over GP in Abadi et al. (016)). Specifically, GEP achieves 74.9% test accuracy on CIFAR-10 with (8, 10 10-3)-De outperforming GP by 18.5%. PATE achieves best accuracy on MNIST but its performance drops as the dataset becomes more complex.
We also plot the relation between accuracy and k in Figure 6 GEP is less sensitive to the choice of and outperforms B-GEP for all choices of The improvement increasing becomes smaller as becomes larger. We note that the memory cost of choosing large l: is high because need to store least l individual gradients to compute anchor subspace.
CONCLUSION
In this paper, we propose Gradient Embedding Perturbation (GEP) for learning with differential privacy. GEP leverages the gradient redundancy to reduce the added noise and outputs unbiased estimator of target gradient. The several key designs of GEP significantly boost the applicability of GEP. Extensive experiments real world datasets demonstrate the superior utility of GEP.

---

Published as a conference paper at ICLR 2021
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In ACM SIGSAC Conference on Computer and Communications Security, 2016.
Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. In Advances in Neural Information Processing Systems, 2019.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, 2018.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Differentially private empirical risk minimiza- tion: Efficient algorithms and tight error bounds. Anmual Symposium on Foundations of Computer Science, 2014.
Daniel Bernau, Philip-William William Grassal, Jonas Robl, and Florian Kerschbaum. Assessing differentially private deep learning with membership inference. arXiv preprint 1rXXiv/912.11322 2019.
Gilles Blanchard, Olivier Bousquet, and Laurent Zwald. Statistical properties of kernel principal component analysis. Machine Learning, 66(2-3):259-299 2007.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, 2016.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jemnj Kos, and Dawn Song. The secret sharer: Evalu- ating and testing unintended memorization in neural networks. In USENIX Security Symposium, 2019.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self-supervised models are strong semi-supervised learners. arXiv preprint arXiv:2006. 10029, 2020a.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Neural Information Processing Systems, 33, 2020b.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithmss 2003.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arXiv:1905.02388 2019.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. Anmual International Conference on the Theory and Applications of Cryptographic Techniques, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, 2006b.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 2014.
Morris L Eaton and Michael D Perlman. The -inguuauyl of generalized sample covariance matrices. The Annals of Statistics, pp. 710-717, 1973.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. ACM SIGSAC Conference on Computer and Communications Security, 2015.
Kazuto Fukuchi, Quang Khai Tran, and Jun Sakuma. Differentially private empirical risk minimiza- tion with input perturbation. In International Conference Discovery Science, 2017.
10

---

Published as a conference paper at ICLR 2021
Mary Gooneratne, Khe Chai Sim, Petr Zadrazil, Andreas Kabel, Françoise Beaufays. and Giovanni Motta. Low-rank gradient approximation for memory-efficient on-device training of deep neural network. In IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP). IEEE, 2020.
Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. arXiv preprint arXiv: 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Conference on Computer Vision and Pattern Recognition, 2020.
Briland Hitaj, Giuseppe Ateniese, and Fernando Pérez-Cruz. Deep models under the gan: information leakage from collaborative deep learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017.
Sergey Ioffe and Christian Szegedy. Batch normalization: reducing internal covariate shift. In International Conference on Machine Learning, 2015.
Accelerating deep network training by
Roger Iyengar, Joseph Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In IEEE Symposium on Security and Privacy, 2019.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy-preserving empirical risk minimization. In Advances in Neural Information Processing Systems, 2018.
James Jordon, Jinsung Yoon, and Mihaela van der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations, 2019.
Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. Dimension independence in unconstrained private erm via adaptive preconditioning. arXiv preprini arXiv:2008. 06570, 2020.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, 2012.
Jaewoo Lee and Daniel Kifer. Concentrated differentially private gradient descent with adaptive per-iteration privacy budget. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018
Xinyan Li, Qilong Gu, Yingxue Zhou, Tiancong Chen, and Arindam Banerjee. Hessian based analysis of sgd for deep nets: Dynamics and generalization. In SIAM International Conference on Data Mining, 2020.
Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially-prrvate learners: attacks and defenses. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 4732 4738. AAAI Press, 2019.
Ilya Mironov. Rényi differential privacy. IEEE Computer Security Foundations Symposium, 2017.
Iyy Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv, 2019.
Robb J Muirhead, Aspects of multivariate statistical theory, volume 197. John Wiley & Sons, 2009.
Maysum Panju. Iterative methods for computing cigenvalues and eigenvectors. arXiv preprint a05iv:/ 185, 2011.
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 Learning Representations, 2017.
11

---

Published as a conference paper at ICLR 2021
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Ülfar Erlings- son. Scalable private learning with pate. In International Conference on Learning Representatioss 2018.
NhatHai Phan, My Thai, Han Hu, Ruoming Jin, Tong Sun, and Dejing Dou. Scalable differential privacy with certified robustness in adversarial learning. International Conference Machine Learning, 2020.
Md Atiqur Rahman, Tanzila Rahman, Robert Laganiere, Noman Mohammed, and Yang Wang. Membership inference attack against differentially private deep learning model. Transactions on Data Privacy, 2018.
Alexandre Sablayrolles, Matthijs Douze, Yann Ollivier, Cordelia Schmid, and Hervé Jégou. White- box vs black-box: Bayes optimal strategies for membership inference. International Conference on Machine Learning, 2019.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In ACM SIGSAC conference on computer and communications security, 2015.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE Symposium Security and Privacy 2017.
Shuang Song, Kamalika Chaudhuri, and Anand Sarwate. Stochastic gradient descent with differen- tially private updates. In Global Conference Signal and Information Processing (GlobalSIP), 2013.
Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly optimal private lasso. In Advances in Neural Information Processing Systems, 2015.
Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, 2013.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). arXiv preprint arXiv:2011.1 1660, 2020.
Joel Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230 2015.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, 2019.
Di Wang and Jinhui Xu. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, 2019.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances Neural Information Processing Systems, 2017.
Jun Wang and Zhi- Zhou. Differentially private learning with small public data. In AAAI, 2020.
I Lingxiao Wang and Quanquan Gu. Differentially private iterative gradient hard thresholding for sparse learning. International Joint Conference on Artificial Intelligence, 2019.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan, Subsampled rényi differential privacy and analytical moments accountant. In International Conference on Artificial Intelligence and Statistics, 2019.
Xi Wu, Matthew Fredrikson, Somesh Jha, and Jeffrey F Naughton. A methodology for formalizing model-inversion attacks. In IEEE Computer Security Foundations Symposium. 2016.
Xi Wu, Fengan Li. Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient passentt-base analytics. In ACM International Conference Management of Data, 2017.
12

---

Published as a conference paper at ICLR 2021
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference computer vision (ECCV), 2018.
Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie- Liu, Gradient perturbation is underrated for differentially private convex optimization. In Proc. of 29th Int. Joint Conf. Artificial Intelligence, 2020.
Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie- Yan Liu. How does data augmentation affect privacy in machine learning? Proc. of the AAAI Conference on Artificial Intelligence, 2021.
Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. arXiv preprint arXiv:2007.03813, 2020.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, 2019.
Yuqing Zhu and Yu- Xiang Wang. Poission subsampled rényi differential privacy. In International Conference on Machine Learning, 2019.
13

---

Published as a conference paper at ICLR 2021
A EXPERIMENTS WITH PRE-TRAINED MODELS
Recent works have shown that pre-training the models on unlabeled data can be beneficial for subsequent learning tasks (Chen al. 2020a He al. 2020 Tramer & Boneh 2020) demonstrate that differentially private linear classifier can achieve high accuracy using the features produced by those per-trained models. We show that GEP can also benefit from such pre-trained models.
Inspired by Tramer & Bonch (2020), we use the output of the penultimate layer of a pre-trained ResNet152 model as feature to train a private linear classifier. The ResNet152 model is pre-trained on unlabeled ImageNet using SimCLR (Chen et al. 2020a). The feature dimension is 4096.
Implementation Details We choose the privacy parameter from [0.1, 0.5, 1, 2, The privacy param- eter 5 is 1 x 10-5. We run all experiments for 5 times and report the average accuracy. The clipping threshold of residual gradients still one-fifth of the clipping threshold of the original gradients. The dimension of anchor subspace is set 200 vp where p 40960 is the model dimension. We randomly sample 500 samples from the test set as auxiliary data and evaluate performance on the rest test samples. The optimizer is Adam with default momentum coefficients. Other haper-parameters are listed in Table 2
Hyperparameter Learning rate
Values
0.01, 0.05, 0.1
Running steps
50, 100, 400
Clipping threshold
0.01, 0.1.
Table 2: Hyperparameter values used in Appendix A
The experiment results are shown in Table 3 GEP outperforms GP on all values of With privacy bound e 2, GEP achieves 94.8% validation accuracy on CIFARIO dataset, improving over the GP baseline by 1.4%. For very strong privacy guarantee (e = 0.1), B-GEP performs on par with GEP because strong privacy guarantee requires large noise and the useful signal in residual gradient is submerged in the added noise. B-GEP benefits less from larger compared to GP or GEP. For <= 1 and 2, the performance of B-GEP worse than the performance of GP. This because larger can not reduce the systematic error of B-GEP (see Remark I in Section 3.2
Results
Table Validation accuracy (in %) on CIFARIO with varying choices of We train a private linear model on top of the features from 55 model, which is pre-trained on unlabeled ImageNet.
0.1
0.5
e
2
Non private
96.3
96.3
96.3
96.3
GP
88.2 (+:0.16)
91.1 (+00177
93.2 (+:0.19)
93.4 (=:0.12)
B-GEP
91.0 (#0.07)
92.9 (+0.00)
93.1 (#0.10)
93.2 (=0.08)
GEP
90.9 (+
93.5 (+0.06)
94.3 (+0009)
94.8 (+0.06)
B COMPLEXITY ANALYSIS
We provide an analysis of the computational and memory costs of the construction of anchor subspace. The computation of the anchor subspace is the dominant additional cost of GEP compared to conventional gradient perturbation. Notations: k. and are the dimension of anchor subspace, number anchor gradients, number private gradients, and the model dimension, respectively. In order reduce the computational and memory costs, divide the parameters into g groups and compute one orthonormal basis for each group. We refer to this approach as 'parameter grouping', In this section, assume the parameters and the dimension of the anchor subspace are both divided evenly. Table 4 summarizes the additional costs of GEP with/without parameter grouping. Using parameter grouping can reduce the computatiiona//meorry cost significantly.
14

---

Published as a conference paper at ICLR 2021
Table 4: Computational and memory costs of a single power iteration in Algorithm[] The computation cost is measured by the number of floating point operations. The memory cost is measured by the number of floating-point numbers need to store. 'GEP+PG' denotes GEP with parameter grouping and denotes the number of groups. Notations: k. m, and p the dimension of anchor subspace, number of anchor gradients, number of private gradients, and the model dimension, respectively.
Computational Cost
Memory Cost
GEP
2mkp ph²
max
(0, (m n + k) p + mk)
GEP+PG
2mkp/g + pk? /g/
max 0, m n + +) P + mkk
C ABLATION STUDY
The influence of choosing difffrrnt auxiliary datasets. We conduct experiments with different choices of auxiliary datasets, For CIFARIO, we try 2000 random test samples from CIFARIO, 2000 random samples from CIFARI00, and 2000 random samples from ImageNet. When the auxiliary dataset is CIFAR1O, we try both correct labels and random labels. For all choices of auxiliary datasets, the test accuracy evaluated on 8000 test samples CIFARIO that are not used as auxiliary data. Other implementation details are the same in Section 4 The results are shown in Table Surprisingly, using samples from CIFARIO with correct labels yields the worst accuracy. This may because the model 'overfits" the auxiliary data when it has access to correct labels, which makes the anchor subspace contains less information about the private gradients. The best accuracy is achieved using samples from CIFARIO with random labels, this makes of auxiliary data and private data have the same distribution. Using samples from CIFAR 100 or ImageNet auxiliary data has small influence on the test accuracy.
because in this case the features
Table 5: Test accuracy on CIFARIO with different choices of auxiliary datasets. The privacy guarantee is (8, 10 10-P)-DP. We report the average accuracy of five runs with standard deviations in brackets.
Auxiliary Data
Random Label?
Test Accuracy
CIFARTO
No
72.9 (++0.1)
CIFAR10
Yes
75.1 (#0.42)
CIFAR100
Yes
74.7 (+-0.46)
ImageNet
Yes
74.8 (#:0.39)
The influence of the number of anchor gradients. In the main text, the size of auxiliary dataset is m 2000. We conduct more experiments with different sizes of auxiliary dataset examine the influence of m. The auxiliary data is randomly sampled from ImageNet. Table reports the test accuracy on CIFARIO with different choices of m. For both B-GEP and GEP, increasing m leads to slightly improved performance.
Table 6: Test accuracy on CIFARIO with different sizes of auxiliary dataset. The privacy guarantee is -DP. We report the average accuracy of five runs with standard deviations brackets.
(8, 10 5--D.
Algorithm
1000
2000
4000
B-GEP
62.2 (#0.226
62.6 (+.0224)
63.3 (=:0.77)
GEP
74.6 (+00.41)
74.8 (+.0.39)
75.2 (+:0.34)
The projection error of random basis vectors. It tempting to construct the anchor subspace using random basis vectors because Johmson-Lindeensraass Lemma (Dasgupta & Gupta 2003) guarantees that one can preserve the pairwise distance between any two points after projecting into random subspace of much lower dimension. We empirically verify the projection error of Gaussian random basis vectors CIFAR10 and SVHN. The experiment settings projection errors over the training process are plotted in Figure The projection error of random basis vectors is very high (> 95%) throughout training. This is because preserving the pairwise
the same in Section 4 The
15

---

Published as a conference paper at ICLR 2021
CIFAR1
SVMN
20.3
Aw
294
WMW
V (M/mm M
20.5
18.5-
Inm 2030
2000
10.5
20.4
MM
w
10.2
Figure 7: Projection error rate of random basis vectors. The dimension of subspace is denoted by
distance is not sufficient for high quality gradient reconstruction, which requires one to preserve the average 'distance' between any individual gradient and all other gradients.
D MISSING PROOFS
Lemma 3.1. Assume that the population covariance matrix Σ with rank and the distribution P satisfies P(g e F,) = for all s-flats E, in R2 with S Let E VVAVE and $ = Vy AVT be the eigendecoomossiioon of E and the empirical covariance matrix $, respectively, such that Ag. (5) > 0 and (5) = 0. Then if m 2 k. we have with probability 1,
k' = k and VVVV V.V 1| 0.
Proof. We extend the Theorem 3.2 in Eaton & Perlman 1973) to the low-rank case.
Theorem D.1 (Theorem 3.2 in Eaton & Perlman (173)), ). Let X (#), ....... Inn) where the æ;
i..dd random vectors in IR,, n 2 P(x E M) for all proper manifolds M. C IR, then
P(X is non-singular)=-.
We note that the subspace spanned by Vi the space spanned by V2 by definition. Hence k' S k.
Let db; ViT& E. R for E [m]. Then X (#1,..,, )m) is non-singular because of the assump- tion and Theorem D.1 That is rank(X): = k. Therefore rank((É1, Em) 2 k, rank(S)) 2 and k' 2 k. Therefore k' = k and the subspace spanned by V and the subspace spanned by Vi are identical.
Theorem 3.1. Let S1 and S2 be the sensitivity of w and r, respectively, the output of Algorithm 7 satisfies 5c. for any 8 E (0, and S 2 log(1/6) if we choose oı 2 2S, log(/// and 02 2 /2o///oo(1//6//
Proof of Theorem 3.1 We first introduce some background knowledge of Rényi differential privacy
(RDP) Mironov
2017). RDP measures the Rényi divergence between two output distributions.
Definition 2 ((), RDDP), A randomized mechanism f is said guarantee (X.7)-RDD for any neighboring datasets DD, D'' and X > it holds that
(x((()))(((')) Sn.
where Dx(-II-) denotes the Rényi divergence of order X.
We next introduce some useful properties of RDP. Lemma D.2 (Gaussian mechanism of RDP). Let S = maxp [f(D) f(D) be the la sensitiviry, then Gaussian mechanism M -[D + satisfies (x, Ase
20- RDDP, where ~ NO, o Ipxp).
Lemma D.3 (Composition RDP). If M,. M, satisfy (A, RDDP and (A, RDD respectively, then their composition satisfies (2, 71 + -DDP.
16

---

Published as a conference paper at ICLR 2021
Lemma D.4 (Conversion from RDP to (e, M obeys (A.7)-RDP, then M obeys (y
log(1/6)/(A ()))AA-111,))P.. f) all
Now we proof Theorem 3.1, Let W, W be the gradient embeddings two neighboring datasets DD ~ ID' and R. R' be corresponding residual gradients. Without loss of generality, suppose W (R)
has one more row than W (R²'). For given sensitivity S1, S2.
max 1100 D
w'll
W S St, www
max
max || P r'll B-y
max R-R
RR.;il S S2.
Lemma D.2 and and D.3 In order to guarantee (e, 6)-DP, need ]
we set 0i = Sia and S20 for some a, then Algorithm
satisfies (2, // RDD because of
A
log (1/6)
+
S.
(5)
Choose À = 1 2 and rearrange Eq ())
we need
2 (10g(1
(6)
Then using the constraint on concludes the proof.
Theorem 3.2. For any < 2log(1/6) and 5 1). the output of Algorithum satisfies (c, 6D- DP if we set a 2 2 27 (/
Proof Theorem 3.2 From the proof of Theorem 3.1 have each call of GEP satisfies (A,
RDP. Then by the composition property of RDP (Lemma D.3). the output of Algorithm 2 (X, TA RDDP. Plugging IA into Equation 5 and 6 concludes the proof.
satisfies
Theorem 3.3. Suppose the loss I(())
1 E( ((.n)) ((fo(x)))) I-Lipschitz, convex, and B- vp' and 0 I Or. then we have [[[[(O)] T.(O.) s
smooth.
If 1j
3. T
o of residual gradient at step t.
(lg((1888 ne
1/1
where Σt r and rt max, ((. is the sensitivity me
Proof of Theorem 3.3
The f-smooth condition gives
8 |10,41 0.1
I(( S I((0) + 0,-10) +1)+
Based on the update rule GEP we have
(1) B + 2, (2)) 0 = - - -nV - ! (z) 71
0,11
(8)
where 2(1) (N0, o² o2
the perturbation noises and max, [I. is the sensitivity of residual gradients at step t.
x,(2) NO o
Take expectation Eq with respect the perturbation noises.
0n²o² 2n²
E[L(0++1) < ((,().) - (n- - -
16+pr??
(9)
Subtract L(O.) from both sides, we have
3n202
[[[(0++1)) T.(0.) [[L().) I((0.) -n
(k: + pr?)
2n?
37200
EL(L 0.) (
(h: + pr?)
2n²
(10)
17

---

Published as a conference paper at ICLR 2021
The second inequality holds because L is convex. Then choose "y (0, - 00+1)// Bz z1)/n into Eq 10
3 and plug VL(0,)
3 21110 02+1ll]+ σ²
- L(O.) - (E( 01+1. 0, 0+)l
(k + pr?)
2
BnZ
(11)
8 [E]| 0.11²] -:11))-1100---1 0.111)
o²
(k + pri)
Bn
Sum over f = O,.... T 1 and use convexity, we have
T-1 (k
8
B[ - L(O.) -
100
0-1l
Σ
(12)
2T
Bn
T t=0
Then substituting
nde vp
and = O (ttl/llog(/////// yields the desired bound.
18


Reviews:
[{"review_id": "zIFt3PO584P", "reviewer": "AnonReviewer1", "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": "Paper proposes gradient embedding as a potential solution to boost the privacy-utility trade-off in differentially private machine learning via gradient perturbation. Main idea is to project the gradients into a lower-dimensional subspace before adding noise, so that the curse of dimensionality in DPSGD can be somewhat dealt with. \n\nI like the paper and the motivation as high-dimensionality can be considered as a major driver behind the privacy-utility trade-off in DPSGD. Also, the requirement for a public data is much more acceptable in the provided scenario, where it is only required to get anchor gradients. Overall empirical evaluation is adequate, however, it would have been nice to see PATE's numbers on all comparisons, especially given that the implementation is publicly available. I would have also liked the source-code as these type of claims are best verified empirically, especially when we are using gradient projection that can can lead to projection errors and the page limit in the submission is nearly not enough for a thorough evaluation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "yO0OQoDZxI", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "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 paper proposes a simple but highly effective approach to improve differentially private deep learning, by projecting gradients to a small subspace spanned by public data.\nThis idea has been proposed before, but this paper seems to have the unique (and important) insight to release noisy residual gradients, so as to ensure that the final gradient estimation remains unbiased.\nExperiments on MNIST, SVHN and CIFAR-10 show that the proposed approach significantly improves the privacy-utility tradeoff of DP-SGD.\n\nThis paper is excellent. It is well motivated, as the assumption of access to a small amount of public data seems very reasonable in practice. The proposed algorithm is quite natural. The key insight is to release private noisy estimates of both the low-dimensional gradient embedding *and* the residual (low-norm) gradient. This is easily shown to produce an unbiased estimate of the gradient, which is crucial for performance.\nThe experiments convincingly show that this approach leads to strong performance improvements, and I predict that this simple technique will be applied in many subsequent works.\n\nI have a number of (mostly minor) comments and suggestions for improvement: \n\n- In Algorithm 1, and in the main text, it would be good to clarify the clipping applied to both the embedded and residual gradients. It is also worth noting that in practice, the estimated gradient is probably *not* quite unbiased because of this clipping (the same holds for standard DP-SGD of course).\n\n- You mention that you use \"privacy amplification by subsampling\" to compute the DP guarantees. It would be good to clarify this, since some of these theorems apply specifically to a \"subsample + gaussian mechanism\" approach, which your algorithm doesn't quite match (GEP applies two independent Gaussian mechanisms to functions of a subsampled gradient).\nThis seems like it could be resolved as follows:\n- you have embedded gradients Wi clipped to norm C1\n- you have residual gradients Ri clipped to norm C2\n- You can \"stack\" these as gradients gi = [Wi/C1 ri/C2] of norm S=sqrt(2), and then apply a single Gaussian mechanism with sensitivity S to this stacked gradient. After that, you can rescale the two components by C1 and C2 respectively. This seems identical to your proposed approach of applying two Gaussian mechanisms with sensitivities scaled by a factor \\sqrt(2).\n \n\n- Only in Section 4 do you mention that you split the gradient into different groups to fit them in memory. It would be nice to see this discussed earlier on in the paper. E.g., the abstract claims that GEP has \"low computational cost\", which then seems strange when Section 3.1 says that the cost is O(m*k*p), which would be huge even for moderate DNNs. Section 3.2. mentions using a ResNet-20 with k=2000 basis vectors, which wouldn't fit in any GPU memory if it weren't for the grouping. While reading these sections, I was confused about how this could possibly be implemented at a low cost, as described.\nFollowing on this, it would be nice to have some results on the additional computational and memory costs of GEP in the evaluation. \n\n- Papernot et al. show that the choice of architecture can have a large influence on DP-SGD (https://arxiv.org/abs/2007.14191). The results they obtain are sometimes better than your GP baseline. It would be interesting to see if you can get even better results with GEP with such architectures.\n\n- This is somewhat orthogonal to your approach, but do you have a sense of whether 2000 public ImageNet samples could be leveraged in other ways than as gradient basis vectors? E.g., on CIFAR-10, it is well-known that unsupervised dictionaries of data patches can achieve >80% accuracy. So one could also consider using the public data to learn a patch dictionary, and then simply train a small private classifier on top of these features. Maybe this would perform better than GEP?", "extra_scores": {}, "extra_text": {}}, {"review_id": "pMvuMpXMbXS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied how to use the information that the gradient lies in a low dimension space to design more accurate differentially private SGD algorithm. Specifically, the authors proposed a new method which is called Gradient Embedding perturbation method. And they showed that compared with the previous DP-SDG method, their method has higher accuracy. \nActually, I tend to weakly reject the paper due to the following reasons. \n1. As I know and also the authors mentioned in the related work part, there are also two other works study how to use the low dimensional gradient to get higher utilities for the Empirical Risk Minimization problem. However, I can see that in the other two works, they all have theoretical results for the utility, while in this paper there is just a variance analysis, so I wish to see the authors use Theorem 3.2 to get the excess error for their method when the loss functions are convex so that we can see the difference between the other two methods clearly. \n2. In the experimental part, I think it will be better to have a comparison with the above two papers to see the superiority of the method in this paper. just comparing with the base-line is not enough.  Moreover, the authors set $\\delta=10^{-5}$ or $10^{-6}$, I think it will be better to set $\\delta=\\frac{1}{n}$. And I want to see more comments about the number of public data to get the anchor subspace.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-bb4xa9RGI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary: The paper focuses on training deep learning models under differential privacy. The main contribution is a technique based on  projecting the gradient into a non-sensitive anchor subspace and then perturbing the projected gradient (and the residual).\n\nComments:\n\nIt is well-known that a straightforward way of perturbing the gradients for achieving differential privacy requires that the noise magnitude has to scale with the dimensionality of the gradients.\n\nNow to reduce the dependence on dimension the authors use a simple idea: reduce the dimension of the gradients using an embedding and then add noise into the low-dimensional gradients. They assume the presence of non-sensitive data for this purpose. The rough outline is as follows: 1) use the non-sensitive data to compute a subspace using a principal components approach, 2) project the private gradient into this subspace to obtain a low-dimensional gradient embedding and the residual, 3) perturb the gradient embedding and residual gradient separately for DP purposes, d) use the perturbed gradients in a DP-GD iteration.\n\nStrengths:\n1)\tThe problem of reducing noise in differentially private ML is an important practical problem.\n2)\tThe experiments shows benefit of this approach over Abadi et al.\nI think the most interesting part of the paper is the experimental evaluation. There is no strong theoretical component in the paper. \n\nHere are some questions/suggestions:\n1) Can you provide convergence bounds achieved with using gradients produced by GEP (Algorithm 1) in standard convex/nonconvex optimization settings.\n2)  Are there any good bounds on S_1 and S_2?\n3) I did not understand the role of Lemma 3.1? Don’t you require the anchor subspace to be non-sensitive (not depend on sensitive gradients)?\n4) How crucial is the choice of picking the right auxiliary dataset. Providing experimental results with different choices of the auxiliary dataset might help.\n5) Why does not the random projection using JL work? The authors allude to an empirical observation in the text which I did not find.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a method for differentially private deep learning, which the authors term Gradient Embedding Perturbation. This is similar to several (roughly) concurrent works, which project gradients to a subspace based on some auxiliary public data. However, a crucial difference involves the use of the residual gradients, which allows the method to achieve the first significant accuracy gains using subspace projection. The reviewers believe this method will be important for the practice of DP deep learning.
Decision: Accept (Poster)