Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification
Authors: Yingxue Zhou
Steven Wu
Arindam Banerjee
Venue: ICLR 2021 Poster (2021)

Abstract: Differentially private SGD (DP-SGD) is one of the most popular methods for solving differentially private empirical risk minimization (ERM). Due to its noisy perturbation on each gradient update, the error rate of DP-SGD scales with the ambient dimension $p$, the number of parameters in the model. Such dependence can be problematic for over-parameterized models where $p \gg n$, the number of training samples. Existing lower bounds on private ERM show that such dependence on $p$ is inevitable in the worst case. In this paper, we circumvent the dependence on the ambient dimension by leveraging a low-dimensional structure of gradient space in deep networks---that is, the stochastic gradients for deep nets usually stay in a low dimensional subspace in the training process. We propose Projected DP-SGD that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace, which is given by the top gradient eigenspace on a small public dataset. We provide a general sample complexity analysis on the public dataset for the gradient subspace identification problem and demonstrate that under certain low-dimensional assumptions the public sample complexity only grows logarithmically in $p$. Finally, we provide a theoretical analysis and empirical evaluations to show that our method can substantially improve the accuracy of DP-SGD in the high privacy regime (corresponding to low privacy loss $\epsilon$).



Published as a conference paper at ICLR 2021
BYPASSING THE AMBIENT DIMENSION: PRIVATE SGD WITH GRADIENT SUBSPACE IDENTIFICATION
Yingxue Zhou', Zhiwei Steven Wul, Arindam Banerjee
f Department of Computer Science & Engineering, University of Minnesota
$ School of Computer Science, Carnegie Mellon University.
$ Department of Computer Science, University of Illinois Libana-Champaign
zhou08 0 7777mm edu, #zstevenwuu cmu edu, $ arindamb3 www.mmbblliiiiie.eeeee.e
.du.
ABSTRACT
Differentially private SGD (DP-SGD) is one of the most popular methods for solv- ing differentially private empirical risk minimization (ERM). Due to its noisy per- turbation on each gradient update, the error rate of DP-SGD scales with the ambi- ent dimension p. the number of parameters in the model. Such dependence can be problematic for over- parammteeeteeeed models where p > n, the number of training samples. Existing lower bounds private ERM show that such dependence on p is inevitable the worst case. In this paper, we circumvent the dependence on the ambient dimension by leveraging a low- oowdimeesioonal structure of gradient space in deep networks that is, the stochastic gradients for deep nets usually stay in low dimensional subspace in the training process. We propose Projected DP-SGD that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace, which is given by the top gradient eigenspace on a small public dataset. We provide a general sample complexity analysis on the public dataset for the gradient subspace identification problem and demonstrate that under certain low- dimensional assumptions the public sample complexity only grows logarithmi- cally in p. Finally, we provide a theoretical analysis and empirical evaluations show that our method can substantially improve the accuracy of DP-SGD in the high privacy regime (corresponding to low privacy loss e).
INTRODUCTION
Many fundamental machine learning tasks involve solving empirical risk minimization (ERM): given a loss function E, find a model w E R that minimizes the empirical risk L, (n) = D f(w, 2;), where 21,...; 2 are i.i.d. examples drawn from distribution P. In many ap- plications, the training data may contain highly sensitive information about some individuals. When the models are given by deep neural networks, their rich representation can potentially reveal fine details of the private data.
Differential privacy (DP) (Dwork al. 2006 has by now become the standard approach provide principled and rigorous privacy guarantees in machine learning. Roughly speaking, DP is stability notion that requires that no individual example has significant influence on the trained model. One of the most commonly used algorithm for solving private ERM is the differentially- stochastic gradient descent (DP-SGD) (Abadi et al. [2016] [assily et al. 20144] [Song et al.) (013) private variant of SGD that perturbs each gradient update with random noise vector drawn from an isotropic Gaussian distribution A (0, I?Ip)). with appropriately chosen variance o².
Due to the gradient perturbation drawn from isotropic Gaussian distribution, the error rate of DP-SGD has a dependence on the ambient dimension p-the number of parameters in the model. In the case of convex loss f, [Bassily et al. (2014) show that DGD achieves the optimal empiri- cal excess risk of Ô (yp/(nc)). For non-convex loss L, which is more common in neural network training, minimizing (w) is in general intractable. However, many (non-private) gradient-based optimization methods shown to be effective in practice and provably find approximate sta-
tionary points with vanishing gradient norm [V... (w)]22 (see e.g. Nesterov 2014) Ghadimi and

---

Published as a conference paper at ICLR 2021
50
400
epoch
epoch
epoch
epoch 10
epoch 10
epoch 10
epoch = 50
spoch
300
epoch 50
egenvalue
digenveluuc
epoch 100
200
20
100
1000
200
300
400
500
100
200
300
400
1,00
300
400
Order of eigenvalues from inrgest smallest
Order of eggnnslues from largest to smallest
Order eigenvalues from largest To smallest
(a) SGD
(b) DP-SGD, = 1.0
(c) DP-SGD, d = 2.0
Figure 1: Top 500 eigen-value spectrum of the gradient second moment matrix along the training trajectory of SGD, DP-SGD with o 2. Dataset: MNIST; model: 2-layer ReLU with 128 nodes each layer. The network has roughly 130,000 parameters and is trained on MNIST dataset. The Y-axis the eigenvalue and X-axis order of eigenvalues from largest to smallest.
Lan 2013 ). Moreover, for a wide family of loss functions in under the Dolyak-Lojasiewice con- dition (Polyak 1963), the minimization of gradient norm implies achieving global optimum. With privacy constraint, Wang and Xu (2019) recently showed that DP-SGD minimize the empirical gra- dient norm down to O (p1/4/ /nc) when the loss function l is smooth. Furthermore, exsiting lower bounds results on private ERM (Bassily et al.) 2014) show that such dependence on i inevitable in the worst case. However, many modern machine learning tasks now involve training extremely large models, with the number of parameters substantially larger than the number of training samples. For these large models, the error dependence on can be a barrier to practical private ERM.
In this paper, we aim to overcome such dependence on the ambient dimension p by leveraging the structure of the gradient space in the training of neural networks. We take inspiration from the empirical observation from Li al. (2020); Gur-Ari al. (2018); PPayyan (2019) that even though the ambient dimension of the gradients is large, the set of sample gradients at most iterations along the optimization trajectory is often contained in a much lover-dimensional subspace. While this observation has been made mostly for non-private SGD algorithm, we also provide our empirical evaluation of this structure (in terms of eigenvalues of the gradient second moments matrix) in Figure [ Based this observation, provide modular private ERM optimization framework with two components. At each iteration t, the algorithm performs the following two steps:
!) Gradient dimension reduction. Let g: be the mini-bater gradient iteration t. In general, this subroutines solves the following problem: given any p, find linear projection V, (1) E B such that the reconstruction error [g. (t) V (gll small. To implement this subroutine, we follow long line of work that studies private data analysis with access to an auxiliary public dataset S₁ drawn from the same distribution P. for which we don't need to provide formal privacy guarantee (Bassily et al. 2019b 2020 Feldman et al.) 2018 Avent et al. 2017, Papernot et al. (017). In our case, compute V& (t) which is given by the top-k eigenspace of the gradients evaluated Sn. Alternatively, this subroutine can potentially be implemented through private subspace identification on the private dataset. However, to our best knowledge, all existing methods have reconstruction error scaling with vpp (Dwork et al. 2014). which will be propagated to the optimization error.
2) Projected DP SGD (PDP-SGD). Given the projection (t).), perturb gradient in the projected subspace: g. V, (I)) b'), where b' is p-dimensional Gaussian vector: The projection mapping provides a large reduction of the noise and enables higher accuracy for PDP-SGD.
Our results. We provide both theoretical analyses and empirical evaluations of PDP-SGD:
Uniform convergence for projections. A key step in our theoretical analysis is to bound the recon- struction error on the gradients from projection of Va (1). This reduces to bounding the deviation (IV&(t) (t)T (t) where V& (t) denotes the top-k eigenspace of the population second moment matrix [[[V/(w:,> (e( T]. To handle the adaptivity of the sequence of iterates, we provide a uniform deviation bound for all w E W, where the set W contains all of the iterates. By leveraging generic chaining techniques, we provide a deviation bound that scales linearly with complexity measure- the "/2 function due to Talagrand (2014)- of the set W. We provide low- complexity examples of W that are supported by empirical observations and show that their ?2 function only scales logarithmically with p.
2

---

Published as a conference paper at ICLR 2021
Convergence for convex and non-convex optimization. Building on the reconstruction error bound, we provide convergence and sample complexity results for our method PDP-SGD in two types of loss functions, including 1) smooth and non-convex, 2) Lipschitz convex. Under suitable assump- tions on the gradient space, our rates only scales logarithmically on p.
Empirical evaluation. We provide empirical evaluation of PDP-SGD on two real datasets. In our experiments, we construct the "public" datasets by taking very small random sub-samples of these two datasets (100 samples). While these two public datasets are not sufficient for training an accurate predictor, we demonstrate that they provide useful gradient subspace projection and substantial accuracy improvement over DP-SGD.
Related work. Beyond the aforementioned work, there has been recent work on private ERM that also leverages the low-dimensional structure of the problem. Jain and Thakurta (2014); Song et al. (2020) show dimension independent excess empirical risk bounds for convex generalized lin- ear problems, when the input data matrix is low-rank. [Kairouz et al.] (2020) study unconstrained convex empirical risk minimization and provide a noisy AdaGrad method that achieves dimension- free excess risk bound, provided that the gradients along the optimization trajectory lie in a low- dimensional subspace. In comparison, our work studies both convex and non-convex problems and our analysis applics to more general diw-dimensional structures that can be characterized by small 72 functions (Talagrand, 2014; Gunasekar al.) 2015) (c.g., low-rank gradients and fast decay in the magnitude of the gradient coordinates). Recently, |Tramer and Boneh (202T) show that private learning with features learned on public data from similar domain can significantly improve the utility. Zhang et al. (2021) leverage the sparsity of the gradients in deep nets to improve the depen- dence on dimension in the error rate. We also note a recent work (Yu et al. 202I] that proposes an algorithm similar to PDP-SGD. However, in addition to perturbing the projected gradient in the top eigenspaces in the public data, their algorithm also adds noise to the residual gradient. Their error rate scales with dimension in general due to the noise added to the full space. To achieve a dimension independent error bound, their analyses require fresh public samples drawn from the same distribution at each step, which consequently requires large public data set with size scaling linearly with T. In comparison, our analysis does not require fresh public samples at each iteration, and our experiments demonstrate that small public data set of size no more than 150 suffices
2 PRELIMINARIES
Given a private dataset S = {21, ..., 2n3 drawn i..d. from the underlying distribution P, we want to solve the following empirical risk minimization (ERM) problem subject to differential privacy D minw L, (w) 1 Σi= l(w, 2:). where the parameter w E R". We optimize this objective with an iterative algorithm. At each step t, we write W, as the algorithm's iterate and use g, to denote the mini-batch gradient, and Vi,,(,)) = 1 E Vf(w;;z.) to denote the empirical gradient. In addition to the private dataset, the algorithm can also firely access to a small public dataset Sr = (2),.... } drawn from the same distribution P, without any privacy constraint.
Notation. We write Mr E RPxP to denote the second moment matrix of gradients evaluated on public dataset Sn. i..., MM- = m E (w,, & Vi (w,, 2) and write Σ, E RPxP to denote the population second moment matrix, i.c., Eg = Ex~P [VL (We, 2) (w,,,)) =) We use Vtt E RRP as the full eigenspace of Σ, We use (1) E Bx as the top-k eigenspace of M, and (z( E Bpxk as the top-k eigenspace of Σ, To present our result the subsequent sections, we introduce the eigen-gap gap notation a, i.e., let (E,) 2 2 (Eg) be the eigenvalue of Σ,, we use a to denote the eigen-gap between A (E.) and 1 i.e., d >x,)) A (E,) 2 az, We also define W E R2 as the set that contains all the possible iterates E W for L E (T). Throughout, for any matrix A and vector v, ||A denotes spectral norm and | denotes lg norm.
Definition 1 (Differential Privacy (Dwork et al. 2006)) A randomized algorithm R is (c, differentially private for any pair of datasets D, D' differ in exactly one data point and for all event
Note that the requirement of large public data set may remove the need of using the private data in the first place, since training with the large public data may already provide accurate model.
'In this paper, we focus on minimizing the empirical risk. However, by relying on the generalization guarantee of (c, diffferrrti privacy, one can also derive a population risk hound that matches the empirical risk hound up term of order O(e 8) (Dwork al. 2015 Bassily et al. 2016 Jung et al. 2020)
3

---

Published as a conference paper at ICLR 2021
Y' S (R) in the output range of R, we have ((R(D) E)} S exp(c)P(R(D) E 3) + + where the probability is taken over the randomness of R.
To establish the privacy guarantee of our algorithm, we will combine three standard tools in differ- ential privacy, including 1) the Gaussian mechanism (Dwork al. 2006) that releases an aggregate statistic (e.g., the empirical average gradient) by Gaussian perturbation, 2) privacy amplification via subsampling Kaasivswanathann al., 2008) that reduces the privacy parameters e and by running the private computation on a random subsample, and 3) advanced composition theorem (Dwork et al. 2010) that tracks the cumulative privacy loss over the course of the algorithm.
We analyze our method under two asumptions on the gradients of L.
Assumption For any w Ip and example z, [[V(W, 2)|12 G.
Assumption 2 For any example z, the gradient (f 2) is p-Lipschitz with respect suitable pseudo-metric d: IRP x IR + R, i.e. [VE(W, - 22)lz S pd(w, w'), Vw, w' E RR.
Note that Assumption I Iimplis that É, (w) is G-Lipschitz and Assumption 2 iimplies that Ln(w (w) is p-smooth when d is the fy-distance. We will discuss additional assumptions regarding the structure of the stochastic gradients and the error rate for different type of functions in Section 3
3 PROJECTED PRIVATE GRADIENT DESCENT
The PDP-SGD follows the classical noisy gradient descent algorithm DP-SGD (Wang et al. 2017 Wang and Xu 2019 Bassily et al. 2014). DP-SGD adds isotropic Gaussian noise by ~ N (0, o oLp pp) to the gradient gr, I.e., each coordinate of the gradient ge is perturbed by the Gaussian noise. Given the dimension of gradient to be p. this method ends up in getting a factor of in the error rate (Bassily et al. 2014: 2019a). Our algorithm is inspired by the recent observations that stochastic gradients stay in a fow-dimensional space in the training of deep nets (Li et al.) 2020 Gur-Ari et al., 2018). Such observation also valid for the private training algorithm, i.e., DP-SGD (Figure (b) and (c)). Intuitively, the most information needed for gradient descent is embedded in the top eigenspace of the stochastic gradients. Thus, PDP-SGD performs noise reduction by projecting the noisy gradient g: b, to an approximation of such a subspace given by public dataset S
Algorithm Projected DP-SGD (PDP-SGD)
1: Input: Training set S, public set Sh, certain loss E(-,, initial point wo
2: Set: Noise parameter o, iteration time T, step size T/,.
3: for = O,..., T do
4: Compute top-k eigenspace (t( of M, [& Exes, V((w,, VE) (W,, T.)..
5: g:
1 = [. ΣxEB, Ve(w,, 21), with B, uniformly sampled from S with replacement.
6: Project noisy gradient using (t): g. = (t) (t)T (g. + b.), where b, ~ oO))
7: Update parameter using projected noisy gradient: W4+1 = W. m7::.
8:
end for
Thus, our algorithm involves two steps at each iteration, i.e., subspace identification and noisy gra- dient projection. The pseudo-code of PDP-SGD is given in Algorithm [ At each iteration i, in order to obtain an approximated subspace without leaking the information of the private dataset S, we evaluate the second moment matrix M, on S₁, and compute the top-k eigenvectors V (t) of Mj (line in Algorithm D. Then we project the noisy gradient g: + b, to the top-k eigenspace, i.e. &. = ( (g. + b,) (line 6 in Algorithm 1 Then PDP-SGD uses the projected noisy gradient g, to update the parameter Wi+1 Wt me Let us first state its privacy guarantee.
Theorem (Privacy) Under Assumption 7 there exist constants 01 and C2 so that given the number of iterations T, for any S "T, where q = [Bel, PDD-SGD (Algorithm) 1 is (c, diffferreettl (2T1n(H) private for any 8 > 0, of 22 n²
For convex problem, we consider the typical constrained optimization problem such that the optimal solu- tion w' is in H. where H (w //l < B) and each step we project Wi+1 back the set H.
4

---

Published as a conference paper at ICLR 2021
10A
109
10"
epoch 1
spach -
spech =
#poch
spach
10
10
epoch
10
epach 50
10
50
1my:01
epoch 100
epoch - 100
[man]
opech
100
20
10"
10
10
10-
80000
50000
100000 110000 120000
00000 300000 110000 320000
Broco
90020
130000 120000
Order (mm6)) langast smallest
Order
(ovlll largest
DPSGD, o 1.0
(b) DPSGD, a 2.0
(c) DP-SGD, a 4.0
Figure 2: Sorted components of population gradients for DP-SGD with = 1.0, 2.0, 4.0. Dataset: MNIST; model: 2-layer ReLU with 128 nodes each layer. The network has roughly 130,000 param- eters. Y-axis is the absolute value of sorted gradient coordinates, i.e., |mr X-axis the order of sorted gradient component.
The privacy proof essentailly follows from the same proof of DP-SGD (Abadi et al., 2016). At each iteration, the update step PDP-SGD is essentially post-processing of Gaussian Mechanism that computes a noisy estimate of the gradient g: + b, Then the privacy guarantee of releasing the sequence of (g: b is exactly the same the privacy proof of Theorem Aba et al. (0116)
3.1 GRADIENT SUBSPACE IDENTIFICATION
We now analyze the gradient deviation between the approximated subspace V (1) (L)T and true (population) subspace Vi (t) i... (t) (t) To bound V
VI(2)V 22. we first bound the deviation between second moment matrix [M, - Eell (Doork et al. 2014 McSherry] 2004). Note that, if Mr = - E V (W., 2,) Ve 2.) is evaluated on fresh public samples, the Σ, is the expectation of M,, and the deviation of Mc from E, can be casily analyzed by the Ahlswede- Wallsede-Winter Inequality (Horn and John- son
2012 Wainwright 2019), i.c., at any iteration t, if we have fresh public sample [21
Zm (t)} drawn l.i.d from the distribution P. with suitable assumptions we have, E [VE(w,, ( (() > u, Vu E [0, 1].
Vl(W,, (.)))
with probability at most p pexp(-mu' /4G) and G is as in Assumption !
However, this concentration bound does not hold for w,, Vt in general, since the public dataset Sn is reused over the iterations and the parameter W; depends on S₁. To handle the dependency issue, we bound |, Eg llz uniformly over all iterations terparts that consider all possible iterates. Our uniform bound analysis is based on generic chaining (GC) (Talagrand) 2014). an advanced tool from probability theory. Eventually, the error bound is expressed in terms of complexity measure called ?2 function (Talagrand] (014). Note that one may consider the idea of sample splitting to bypass the dependency issue by splitting m public sam- ples into T disjoint subsets for each iteration. Based on Ahlswede- -eltteee-Winter Inequality, the deviation error scales with O II) leading to worse trade-off between the subspace construction error and optimization error due to the dependence on T.
[T'] to bound the worst-case coun-
Vm
Definition (7/ function Talagrand, 2014)) For a metric space (A,d) an admissible sequence of A is a collection of subsets of A. r (An n 2 0}, with A = and |An I 22" for all n 2 1, the "/2 functional is defined by (2,,,, = inf, sup Σn 2(, where the infinum is over all admissible sequences of A.
In Theorem we show that the uniform convergence bound of I|M - Exll2 scales with (2W,, d), where d is the pseudo metric as in Assumption and W E RP is the set that contains all possible iterates in the algorithm, i.c., W, E W for all E [T].
Based on the majorizing measure theorem (e.g., Theorem 2.4.1 in Talagrand (014 the metric d is fg-norm, 72 (WW, d) can be expressed as Gaussian width (Vershynin, 2018; Wainwright, 2019) of the set W. i... w(W)- = E., [suppew (w. v)] where v ~ (0) which only depends on the size of the W. In Appendix A.2 we show the complexity measure 72 (WW, d) can be expressed as the 7/ function measure on the gradient space by mapping the parameter space W to the gradient
space, i.e., f W + M, where can be considered as f(w) Ezep [V(w, To simplify the
5

---

Published as a conference paper at ICLR 2021
notation, write m = EzEp population gradient. Considering d(m, m') = |m m'l2 for m, m' E M. (MM d) will be the same order as the Gaussian width w(M)
(V(w,2) as the population gradient at and M as the space of the
To measure the value of 72(M d), we empirically explore the gradient space M for deep nets. Figure2givv
example of the population gradient along the training trajectory of DP-SGD with a = {1,2,44 4} for training a 2-layer ReLU on MNIST dataset. Figure shows that each coordinate of the gradient of small value and gradient components decay very Tast (Li and Banerjee [021), Thus, it is fair that the gradient space M is a union of ellipsoids, i.e., there exists e E Iº' such that M mmmm E RP Σ)= mm)))/((i)² I e. ]. where j denotes the j-th coordinate. Then we have d2) I c1w(M) I c2 calle|12 (Talagrand 2014),, where e1 and C2 are absolute constants. If the elements of e are sorted in decreasing order satisfy e(j) S ca/ va/vj for all E [p], then (2 d) S O (vlog p) 4 Now we give the uniform convergence bound of [ - E,
Theorem (Second Moment Concentration) Under Assumption 2 the second moment matrix of the public gradient M,-
>x Ve(w,, V.)((( T,)T approximates the population second W2, T] uniformly over all iterations, i.e., for any u >> O,
moment matrix D Ex-pl [V Wt. V((,,,
TuGp/Impr2(M d)
sup || M - E,ll 0
(1)
mm with probability at least 1 cexp (-u²/ /4), where e is an absolute constant.
(E[T]
Theorem[ [Jshows that M, approximates the population second moment matrix E, uniformly over all iterations. This uniform bound is derived by the technique GC, which develops sharp upper bounds to suprema of stochastic processes indexed by a set with a metric structure in terms of 722 functions. In our case, ||M, Eell is treated as the stochastic process indexed by the set W R such that W; E W, which is the set of all possible iterates. The metric d is the pseudo-metric d R' x R. + R defined in Assumption 2 To get a more practical bound, following the above discussion, instead of working with W over parameters, one can consider working with the set M of population gradients by defining the pseudo-metric as d (w, w') d (f(w). (w')) = d d(m, m'), where f(w) EgEP [ [V(w, 2]] that maps the parameter space to gradient space. Thus, the complexity measure 722 (W, df can be expressed as the ?2 function measure on the population gradient space, i.e., (2, d). As discussed above, using the f2-norm d, the (,M, d) will be constant if assuming the gradient space a union of ellipsoids and uniform bound only depends on logarithmically on p.
Using the result in Theorem 2 and Davis-Kahan sin-O theorem (MeSherry) 2004), obtain the subspace construction error (o(t)V( - (1) in the following theorem.
Theorem 3 (Subspace Closeness) Under Assumption 7 and with V&(t) to be the top-k eigenvec- tors of the population second moment matrix Σ, and as be the eigen-gap at t-th iterate such that
A (Ex) Au+1 (2,) 2 for the Vx(t) in Algorithm 1 if O(GPvInTsx(W.a)) ming of
we have
E [IV((0)2L()) -V(()) So (GDvInpra(W.d)
(
1I E (T).
onym
Theorem 3 gives the sample complexity of the public sample size and the reconstruction error, i.e., the difference between V/2 (t))tttt))))) evaluated on the public dataset S₁ and Vi. V& given by the population second moment Σ. The sample complexity and the reconstruction error both depend on the 72 function and eigen-gap are, A small eigen-gap a requires larger public sample m.
3.2 EMPIRICAL RISK CONVERGENCE ANALYSIS
In this section, we present the eтror rate of PDP-SGD for non-convex (smooth) functions. The error rate for convex functions deferred to Appendix C For non-convex case, we first give the error rate of the l2- no-norm of the principal component of the gradient, i.c., (t)) ( (w.)lla. Then we show that the gradient norm also converges if the principal component dominates the residual component of the gradient as suggested by Figure T and recent observations (Papyan 2019 Li ct al,
In the appendix, provide more examples M that are consistent with empirical observations of stochastic gradient distributions and have small (2M, d).

---

Published as a conference paper at ICLR 2021
2020
To present our results, introduce some new notations here. We write [ Ln, ( (wa)] (I) (w:) the principal component of the gradient and [Vi.,, (VT.,(..))) (w,))+ Vln (ln))we)
(O (w:) as the residual component.
Theorem (Smooth and Non-convex) For p-smooth function L. (w), under Assumptions
and
Σt= 1/m? for any 6, O, with = (n) and nt VT PDP-SGD achieves:
let A
T Σ T VIVVVVVVVVVVV (w.))) S
1
|AG* (2
+
(3)
ne
m
Additionally, assuming the principal component of the gradient dominates, i.e., there exist 0,
such that Σi [[V c Σ |[ [oFinw))]]] (w.)] we have
kpp
AG AG*p2 lmp))pp)))))))p))
E [V
+
(4)
TE
m
where WR is uniformly sampled from (Wi,... WT].
Theorem shows that PDP-SGD reduces the error rate of a factor of p to k compared to existing results for non-convex and smooth functions (Wang and Xu 2019). The error rate also includes term depending on the ?22 function and the eigen-gap ay i... A Σ L/a./T, This term comes from the subspace reconstruction error. As discussed in the previous section, as the gradients stay in a union of ellipsoids, the ?22 is a constant. The term A depends on the eigen-gap at, i.e, A (Ex) Ak+1 (Ex) 2 at. As shown by the Figure I. along the training trajectory, there a few dominated eigenvalues and the eigen-gap stays significant (even at the last epoch). Then the term A will be a constant and the bound scales logarithmically with p. If one considers the eigen-gap at decays training proceed, e.g., a₁ ş:; for O, then we have A O(VT). In this case, with T n22,, PDP-SGD requires the public data size m O(ne).
EXPERIMENTS
We empirically evaluate PDP-SGD on training neural networks with two datasets: the MNIST (Le- Cun et al.) 1998) and Fashion MNIST (Xiao et al. 2017). We compare the performance of PDP- SGD with the baseline DP-SGD for various privacy levels In addition, we also explore a heuristic method, i.e., DP-SGD with random projection by replacing the projector with a R Gaussian ran- dom projector (Bingham and Mannila 2001; Blocki et al. (2012). We call this method randomly projected DP-SGD (RPDP-SGD). We present the experimental results after discussing the experi- mental setup. More details and additional results are in Appendix [
Datasets and Network Structure. The MNIST and Fashion MNIST datasets both consist of 60,000 training examples and 10,000 test examples. To construct the private training set, we randomly sample 10, 000 samples from the original training set of MNIST and Fashion MNIST, then we randomly sample 100 samples from the rest construct the public dataset. Note that the smaller private datasets make the private learning problem more challenging. For both datasets, we use convolutional neural network that follows the structure in Papernot al. (2020).
Training and Hyper-parameter Setting, Cross-entropy is used as our loss function throughout experiments. The mini-batch size is set be 250 for both MNIST and Fashion MNIST. For the step size, we follow the grid search method with search space and step size used for DP-SGD, PDP-SGD and SPDP-SGD listed in Appendix D For training, fixed budget on the number of epochs i.e.. 30 is assigned for the each task. We repeat each experiments 3 times and report the mean and standard deviation of the accuracy on the training and test set. For PDP-SGI, we use Lanezos algorithm to compute the top i eigen-space of the gradient second moment martix on public dataset. We use = 50 for MNIST and & 70 for Fashion MNIST. For RPDP-SGD we use = 800 for both datasets. Instead of doing the projection for all epochs, we also explored a start point for the projection, i.e., executing the projection from the 1-st epoch, 15-th epoch. We found that for Fashion MNIST, PDP-SGD and RPDP-SGI perform better when starting projection from the 15-th epoch.
Privacy Parameter Setting: We consider different choices the noise scale, i.c., o = (18, 14, 10, 8, 6, 4) for MNIST and {18, 14, 10, 4, 2) for Fashion MNIST. Since gradient

---

Published as a conference paper at ICLR 2021
75
train accuracy
80
test accuracy
train accuracy
70
accuracy
POP-SGD
PDP-SGD
60
DP-SGD
DP-SGD
RPOP-SGD
RPDP-5GD
-55
PDP-SGD
PDP-5GD
40-
DP-SGD
DP-5GD
RPDP-SGD
RPDP-SGD
1.5
0.5
15
2.0
DP-g
DP-g
DP-
DP-8
(a) MNIST
(b) Fashion MNIST
Figure 3: Training and test accuracy for DP-SGD, PDP-SGD and RPDP-SGD with different privacy levels for (a) MNIST and (b) Fashion MNIST. The X-axis is the c, and the Y-axis is the train/test accuracy. For small regime, which is more favorable for privacy, PDP-SGD outperforms DP-SGD.
00
80
train accuracy
60
test accuracy
train accuracy
:50
accuracy
PDP-SGD DP.SGD RPDP-SGD
PDP-SGD DP.
40
40
RPDP-SGD
30
PDP-SGD
PDP-SGD
20
DP-5GD
DP-SGD RPDP-SGD
RPDP-5GD
10
10 20
30
10 20
30
15
20
25
30
15
20
25
30
number of epochs
number of epochs
number of epochs
number of epochs
(a) MNIST, 0.23
(b) Fashion MNIST, = 0.30
Figure 4: Training dynamics of DP-SGD, PDP-SGD and RPDP-SGD for (a) MNIST (e = 0.23) and (b) Fashion MNIST 0.30). The X-axis is the number of epochs, and the Y-axis the train/test accuracy. For Fashion MNIST, PDP-SGD and RPDP-SGD start projection at 15-th epoch.
norm bound G is unknow for deep learning, we follow the gradient clipping method in Abadi et al. (2016) guarantee the privacy. We choose gradient clip size be 1.0 for both datasets. We follow the Moment Accountant (MA) method (Abadi et al., 2016 Bu et al.) 2019) to calcu- late the accumulated privacy cost, which depends on the number of epochs, the batch size, and noise With 30 epochs, batch size 250, 10, 000 training samples, and fixing ó = 10 5 the is (2.41, 1.09, 0.72, 0.42, 0.30, 0.23] for a E (2, 4, 6, 10, 14, 18) for Fashion MNIST. For MNIST, is (1.09, 0.72, 0.53, 0.42, 0.30, 0.23] for presented in this paper is w.r.t a subset i.e., 10, 000 samples from MNIST and Fashion MNIST.
{4, 6. 8, 10, 14, 18). Note that
Experimental Results. The training accuracy and test accuracy for different are reported in Figure 3 For small regime, i.e., é S 0.42 with MNIST (Figure 3 (a)) and e S 0.72 with Fashion MNIST (Figure 3 (b)), PDP-SGD outperforms DP-SGD, For large (small noise scale), we think DP-SGD performs better than PDP-SGD because the subspace reconstruction error dominates the from the injected noise. For most choices of RPDP-SGI fails improve the accuracy over DP-SGD because the subspace reconstruction error introduced by the random projector is larger than the noise error reduced by projection. To the best of our knowledge, we noticed that when < 1 for MNIST, PDP-SGD and DP-SGD perform better than the benchmark reported in Papernot al. (2020) even with subset from MNIST (Figure 3 (a)). We acknowledge that Papernot et al. (2020) report the test accuracy
training dynamic in terms of privacy loss e. Figure 4 provides two examples of the training dynamics, i.e., MNIST with e 0.23 and Fashion MNIST with e 0.30, showing that PDP-SGD outperforms DP-SGD for large noise scale since PDP-SGD efficiently reduces the noise. We also validate this observation on larger training samples in Appendix D
We also study the role of projection dimension & and pubic sample size m. Figure 5 (a) and Figure b)b) present the training and test accuracy for PDP-SGD with k E {10, 20, 30, 50} and PDP-SGD with E {50, 100, 150} for 0.23 for MNIST dataset. Among the choices of k. PDP-SGD with = 50 achieves the best accuracy. DP-SGD with = 10 proceeds slower than the rest, due to the larger reconstruction error introduced by projecting the gradient to much smaller subspace, i..e, 10. However, compared to the gradient dimension p x= 25, 000, it is impressive that PDP-SGD with & 50 can achieve better accuracy than DP-SGD for certain range of Figure (bb) shows
8

---

Published as a conference paper at ICLR 2021
80
70
train accurace
test accuracy
train accuracy
test accurac
60
50
40
PDP-SGD, k-10
PDP-SGD,
PDP SGD, =20
PGD, =20
PDP-SGD, -50
POP-SGD, m -50
20
PDP-SGD, =20
PDP-SGD, k
20
FDP -100
POP:SGD, m -100
10
PDP-SGD,
number of epochs
10
20
number of epochs
20 number of epachs
number epochs
(a) MNIST, e 0.23
(b) MNIST, = 0.23
Figure 5: Training accuracy and test accuracy for (a) PDP-SGD with k {10, 20, 30, 50); (b) PDP-
SGD with m = {50, 100, 150) for MNIST (e = 0.23). The X-axis and Y-axis refer to Figure The performance of PDP-SGD increases as projection dimension le and public sample size increase.
80
train accuracy
test accuracy
train accuracy
50
test accuracy
60
40
POP-SGO, =1
PDP-SGD, =1
PDP-SGD,
PDP-SGD,
PDP-SGO, s =10
PDP-SGD, : =10
PDP-SGD, =10
PDP SGD, : =10
PDP-SGD,
PDP-SGD,
20
DP-SGD
DP-SGD
DP SGD
DP-SGD
10
10
20
30
20
30
20 number of epochs
30
15
25
30
number of epochs
number of epochs
number of epochs
(a) MNIST, 0.23
(b) Fashion MNIST, 0.23
Figure 6: Training and test accuracy for PDP-SGD with different frequency of eigen-space
{1. 10, 20) is the frequency of subspace update, i.e., compute the eigen-space every s iterates. The X-axis and Y-axis refer to Figure For Fashion MNIST, PDP-SGD starts projection at 15-th epoch. PDP-SGD with reduced eigen-space computation also improves the accuracy over DP-SGD.
putation for (a) MNIST (e = 0.23) and (b) Fashion MNIST (e = 0.23).
that the accuracy PDP-SGD improves as the m increases from 50 150. This is consistent with the theoretical analysis that increasing m helps to reduce the subspace reconstruction error. Also, PDP-SGD with m 100 performs similar to PDP-SGD with m 150. The results suggest that while small number of public datasets are not sufficient for training an accurate predictor, they provide useful gradient subspace projection and accuracy improvement over DP-SGD.
To reduce the computation complexity introduced by eigen-value decomposition, we explored PDP- SGD with sparse eigen-space computation, i.e., update the projector every 8 iterates. Note that PDP-SGD with = means computing the top eigen-space every iteration. Figure 6 reports PDP-SGD with = {1, 10, 20) for (a) MNIST and (b) Fashion MNIST showing that PDP-SGD with reduced eigen-space computation also outperforms DP-SGD, though there is mild decay for PDP-SGD with fewer eigen-space computations.
5 CONCLUSION
While DP-SGD and variants have been well studied for private ERM, the rate of DP-SGD depends on the ambient dimension In this paper, we aim to hypass such dependence by leverag- ing the low-dimensional structure of the observed gradients in the training of deep networks. We propose PDP-SGD which projects the noisy gradient to an approximated subspace evaluated on public dataset. We show theoretically that PDP-SGD can obtain (near) dimension-indepere rate. We evaluate the proposed algorithms on two popular deep learning tasks and demonstrate the empirical advantages of PDP-SGD.
error
ACKNOWLEDGEMENT
The research was supported by NSF grants IIS 1908104, 19C-19,4 IIS IIS11563950, a Google Faculty Research Award, a J.P. Morgan Faculty Award, and Mozilla research grant. We would like to thank the Minnesota Super-computing Institute (MSI) for providing computational resources and support.

---

Published as a conference paper at ICLR 2021
REFERENCES
M. Abadi, A. Chu, I. Goodfellow, B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In 23rd ACM Conference on Computer and Communications Security, pages 308-318, 2016. PtRLtttss://aaat org. abs/ /00///607..0 .065000.000 107.000133
B. Avent, A. Korolova, D. Zeber, T. Hovden, and B. Livshits. BLENDER: enabling local search with a hybrid differential privacy model. In 26th USENIX Security Symposium, pages 747- 764, 2017. URL
technical -ewenicall-ssseee Secchiicc_-eeeesltttsppppessaaaa
R. Bassily, A. Smith, and A. Thakurta, Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473. IEEE, 2014.
R. Bassily, K. Nissim, A. D. Smith, Steinke, U. Stemmer, and J. Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 1046-1059, 2016. doi: 10.1145/2895118.889777 28977666.. URL Inttps:/://di
brg/10.1 1111112/27555 211452997518229755555 2897556
R. Bassily, V. Feldman, K. Talwar, and A. G. Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pages 11282-11291, 2019a.
R. Bassily, S. Moran, and N. Alon. Limits of private learning with ac- cess to public data. In Advances in Neural Information Processing Sys- tems. pages 10342-10352, 2019b. URL http://papers. nips 9222 Limits of www.oofppiiieeeeeeeeeeeeeeee -eaentingerriin with access po-piticc-ottaaaa
R. Bassily, A. Cheu, S. Moran, Nikolov, Ullman, and Z. Wu. Private query release assisted by public data. CoRR, abs/2000.10941, 2020.
F. Bingham and H. Mannila. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowl- edge discovery and data mining, pages 245-250, 2001.
Blocki. A. Blum, A. Datta, and Sheffet. The johnson- -indson--iddesstrauss transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410-419. IEEE, 2012.
Z. Bu, J. Dong, Q. Long, and W. J. Su. Deep learning with gaussian differential privacy. arXiv preprint 19111 1600, 2019.
C. Dwork, F. McSherry, K. Nissim, and Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.
C. Dwork, G. N. Rothblum, and S. P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, pages 51-60. IEEE Computer Society, 2010. doi: 10.1 10.1109/FOCS. 2001//00..000..1.. URL /tt.
1109/F0CS..... 2010.
C. Dwork, K. Talwar, A. Thakurta, and L. Zhang. Analyze gauss: optimal bounds for privacy- preserving principal component analysis. In Symposium on Theory of Computing, pages 1- ACM, 2014. doi: 10. 10.1145/2591796.2559 2591883. URL https: :tbp:://dc::
11455
2591796. 2591883
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth. Preserving statisti- cal validity in adaptive data analysis. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, pages 117-126. ACM, 2015. doi: 10.1145/2746539.2746662
URL
https: //doi. orrg/r///o 10. 11 145144//44
V. Feldman, I. Mironov, K. Talwar, and A. Thakurta. Privacy amplification by iteration. In 59th JEEE Anmual Symposium on Foundations of Computer Science, pages 521-532, 2018, doi: 10. 1109/FOCS.200 2018 0.0066...
org. 1009/10000FFC0 2018 00056
10

---

Published as a conference paper at ICLR 2021
S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic pro- gramming. SIAM Journal on Optimization, 23(4):2341 2013. doi: 10. 10.1137/120880811 URL http:////oooooo//11111111222223
G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, third edition, 1996.
S. Gunasckar, A. Banerjee, and J. Ghosh. Unified view of matrix completion under general struc- tural constraints. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 1, pages 1180-1188, 2015.
G. Gur-Ari, D. A. Roberts, and E. Dyer. Gradient descent happens in a tiny subspace. CoRR, abs/1812.04754, 2018. URL
wtt.oogggabbb//////////// 04754
R. A. Horn and C. Johnson. Matrix analysis. Cambridge university press, 2012.
Jain and A. G. Thakurta. (near) dimension independent risk bounds for differentially pri- vate learning. volume 32 of Proceedings of Machine Learning Research, pages jing, China, 22-24 Jun 2014. PMLR. URL http://prooeedi...............ee gain14.htm
Be-
C. Jung, K. Ligett, S. Neel, A. Roth, S. Sharif--Malvjerddi and M. Shenfeld. A new analysis of differential privacy's generalization guarantees, volume 151, pages 31:1-31:17, 2020, doi: 1230LLPPIs.ITTCS.220000 URL https: //do: wog. 0tte//10.423001000 4230/ ITCS. 2020.
31
P. Kairouz, M. Ribero, K. Rush, and A. Thakurta. Dimension independence in unconstrained private ERM via adaptive preconditioning. CoRR, abs/2008.06570 2020. URL htttp:://axxi:
a2g00 06570
S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11)2778-2224 1998.
X. Li and A. Banerjee. Experiments with rich regime training for deep learning. arXiv preprint 11X5v:2102.13522, 2021.
X. Li, Q. Gu, Y. Zhou, T. Chen, and A. Banerjee. Hessian based analysis of SGD for deep nets: Dynamics and generalization. In Proceedings the 2020 SIAM International Conference Data Mining, pages 190-198, SIAM, 2020. doi: 0113/11978111111111
URL https:
7/doi www.rrg/10.0 1137/1 971119919986666.. 22
F. McSherry. Spectral methods for data analysis. PhD thesis, University of Washington, 2004.
Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer Publishing Company, Incorporated, edition, 2014. ISBN 1461346916.
N. Papernot, M. Abadi, Ó. Erlingsson, I. Goodfellow, and K. Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In 5th International Conference on Learning Representations, 2017. URL
N. Papernot, A. Thakurta, S. Song, S. Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy, 2020.
Papyan. Measurements of three-level hierarchical structure the outliers in the spectrum of deepnet hessians. In International Conference Machine Learning, pages 5012-5021,
B. Polyak. Gradient methods for the minimisation of functionals. Ussr Computational Mathematics and Mathematical Physics, 3:864-878. 12 1963. doi: 10. 10.10660001-5553663903335

---

Published as a conference paper at ICLR 2021
S. Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with differentially private updates. In IEEE Global Conference on Signal and Information Processing, pages 245-248. IEEE, 2013. doi: 10.1 10.1109/cioba1SS122033..6666
URL /
Globa STP 2013. 6736861
S. Song, O. Thakkar, and A. Thakurta. Characterizing private clipped gradient descent on convex generalized linear problems. arXiv preprint arXiv:2006.0678. 06700, 2020.
M. Talagrand. Upper and Lower Bounds for Stochastic Processes. Springer, 2014.
Tramer and D. Bonch. Differentially private learning needs better features (or much more data). In International Conference Learning Representations, 2021. URL httpttst////penre..ee
R. Vershynin. High-Dimenne Ligh--Dimensionll Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. doi: 10.101779781108211556
J. Wainwright. High-dimensional statistics: non-asymplotic viewpoint, volume 48. Cambridge University Press, 2019.
D. Wang and J. Xu. Differentially private empirical risk minimization with smooth non-convex loss functions: A non-stationary view. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 33, pages 1182-1189, 2019.
D. Wang, M. Ye, and Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, pages 2722-2731, 2017.
H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint crXiv:1708.07744 2017.
D. Yu, H. Zhang, W. Chen, and T.-Y. Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference Learning Representations, 2021. URL htt.htttss///ppreeeeee
wwt.t/eett/ra////eeeeoa net. forum? hatpmmmddddaoooooooo
H. Zhang, I. Mironov, and M. Hejazinia. Wide network learning with differential privacy. arXiv preprint drX1v:2103.0124, 2021.
12

---

Published as a conference paper at ICLR 2021
A UNIFORM CONVERGENCE FOR SUBSPACES: PROOFS FOR SECTION 3.1
In this section, we provide the proofs for Section 3.1
We first show that the second moment matrix M, converges the population second moment matrix E, uniform
all iterations t [T]. i.e.,
suPιetr || - Drll. Then we show that the top-k subspace of M, uniformly converges to the top-k subspace of E,, i.e., (t) where W is the set of all possible parameters along the training trajectory. In Section (A.2 we show that the bound can be derived by 72(M, d) as well, where M is the set of population gradients along the training trajectory. Then, provide examples of the set M and corresponding value of (2, d).
(+) for all E [T]. Our bound depends on 72 (WW
A.1 UNIFORM CONVERGENCE BOUND
Our proof's of Theorem heavily rely on the advanced probability tool, Generic Chaining (GC) Talagrand, 2014). Typically the results in generic chaining are characterized by the so-called ?2 function (see Dehmition 2). Talagrand (2014) shows that for a process (Xt)er and given metric space (T, d), if (Xt),eT satisties the increment condition
u2
Vu > O,P( x, 2 2 2exp
(5)
2d(ss t)2
then the size of the process can be bounded
E
Ssup X2 I (T, tET
(6)
with e be an absolute constant.
To apply the GC result to establish the Theorem we treat | - Eellz as the process X₁ over the iterations. In detail, since Mt = 1 2i=1 Vi (w,, 2 Ve (We, &)), and M; = Egsp (VL (W,, 2) Ve (W,, 2. the ||M - 122 is a random process indexed by w, E W, with W to be the of all possible iterates obtained by the algorithm.
We first show that the variable |M, - E, 2l satisfies the increment condition as stated in equation in Lemma Before we present the proof of Lemma [] we introduce the Ahlswede Winter Inequal ity (Horn and Johnson] 2012, Wainwright 2019). which will be used in the proof of Lemma Ahlswede- Winter Inequality shows that positive semi-definite random matrix with bounded spectral norm concentrates to its expectation with high probability.
Theorem (Ahlswede- Winter Inequality) Let be random. symmetric. positive semi-definite X P matrix. such that such that ||||]]| < 1. Suppose ||Y||| < R for some fixed scalar R 2 1. Let .Y.....,yT.. be independent copies of Y (i.e., independently sampled matrices with the same distribution as Y). For any u E [0, 1), we have
Y
Y
> u
S 2p exp (-mu² (oRu?/4R).
m
To make the argument clear, we use a more informative notation for M, and E,. Recall the notation of Mj and E, such that
m2 Vl (we.
Mi m
(8)
and
Σ, = EyPP (W(,,,22 V (Ww, (V(,)))
(9)
given the dataset S₁ = (ž,,.., 3 and distribution where ž, ~ P for E [m]] the M, and Σ, are functions of parameter Wa, use M (w:)) and E(w;) for M, and E, interchangeably in the rest of this section, i..c,
M(w) = m
Vl(w,a 2,) VL (w,2) TT)
(10)
13

---

Published as a conference paper at ICLR 2021
and
Σ(w) = Egup [V( Ve (w
(11)
Lemma
With Assumption 2 and hold, for any w, w' E W and Vu > O, we have
P (MM(W)- E(w)ll2 - [IM(w') E(w))l2 2 vm
4GGdd(w, (o)l((ww)))) w')) S 2p exp (-u2/4),
(12)
where d W x W + R is the pseudo-metric Assumption
2
Proof: We consider random variable
X; V((w, VeW 2.)
2,TT + 2Gpd(w, w W'pp.
(13)
where Ip E Rpx is the identity matrix.
Note that 2Gpd(w, w, w') is deterministic and the randomness of X, comes from Vl(w, 2)) and Vi(ww, 2,).
By triangle incquality and the construction of X,, we have
[[W(W) E(w)ll2 - (w')(w)) - E(w')l2
II,((w) (E[M(w)]ll - [[M((')) - RIM (w)]l2
S [] [B[ - (MM(w) RB[M(W 1l
(W)(()) .WW)-- -[) (ww))ll
m
(Vé(w, 2,) Ve(w, T,)T -Ve--V (e(W'&)V((W'.k)
(. 72(W',2)VL 2)
m
Ve(w' V((W TT)T + 2G w')
BlVl(w, &E) V 2 + 2Gpd(w, w')p
Σ x, X
(14)
To apply Theorem 5 for || m - B[x,] Il. we first show that the random symmetric matrix X;
is positive semi-dennite
By Assumption and Assumption and definition
[V[(w, Ve(w, T Vf(w', ())
sup T (V((w, V/( 2.) Ve(w', ((((',&))/ V/(' (()T) x
xx|||||=1
sup x xVV<(w. 2, VV 2)) Tx xTV((w'. & v
x=|||||=1
sup
(x. V((w, 2,)) (x. Ve(w', =
x|||||=1
sup
((x, Vl(w 2)) + (x. ve(w' E))) ((x, Vl(w, z)) (x. ve(w',z))
x|||||=1
< sup 2G ((x, Vl(w, 2.)) - (x. ve(w',2)))
x||x||=1
22GIVV((W, 2,) ve(w',2))l
2Gpdlw,, w')
(15)
14

---

Published as a conference paper at ICLR 2021
For any non-zero vector x E R', have
x X x (Vl(w, 2, Ve(w, (T) - Ve(w', 2, Ve(w 2.) 2Gdd w')
x (V((W, 2, Ve(w, T Ve(w', 2, ( 20)
2 - 1IVe(w, V 2,)T Ve(w', 2,) Ve(w': 11 2
(2Gpd(w, w') - [V((w, V)(( 2 V((w 2/ V(((' |
0,
(16)
where (a) is true because VV((w,,)VV(( V.W T,)T V((w', V((W")))V((WW=)) S 2Gpd(w, w') as shown in equation 15
X, Let Yi aGpd(w.w') with equation 15
we have
| = [Ve(w,
Ve(w', Ve) 22) + 2Gpd( w. w')
4Gp w')
[V[(w, 2.) V.(,,, E
Ve(w', 2. Ve)',, + [|2Gpd(w, p'l
4Gpd(w, w")
2Gpd(w, w') + 2Gpddw, w. w')
1
4Gpd(w,,w
(17)
So that |Xill2 I and ||[|ii]l2 S Then, from Theorem with R = we have for any u E [0,
P (1
[ Y E
< 2p exp (-mu²/44
(18)
Note that >m Y; - E [a]] is always bounded by since ||Villa < 1 and ||E[T]][22 < 1. So the
above inequality holds for any > 1 with probability 0 which is bounded by 2p exp (-mu² 1 /4). So that we have for any 0,
Σ Y E E
>
S 2p exp (-ma² /4).
(19)
So that for any
u >
O.
1 m
P
x,
E
[X.]
< e 4Gpd( w, w') [Gpd(w,
exp (-u²/1)
(20)
m
mm
Combine equation 20 and equation 14 we have
(ww) E(w)ll2 [WM((w) E(w))l2 Vm
4Gpd(w,
[IIM(w) (W) [[M(w') - EEMM('))ll > vm
=P
4Gp w, w')
< IP 1 m Σ X, - E [X,]
> u
4G, w')
mm
< 2p exp (-u² /4)
(21)
That completes the proof.
Based on the above result, now we come to the proof of Theorem Chaining argument, i.e., Chapter 2 of Talagrand (2014).
2
The proof follows the Generic
15

---

Published as a conference paper at ICLR 2021
Theorem (Second Moment Concentration) Under Assumptiio the second moment matrix of the public gradient Mr
1
_x=1 Ve, 2, (.W 2,)JT approximates the population second VL Wx, T uniformly over all iterations, i.e., for any >> 0,
moment matrix E, B V Wt,
uGpv/mpreeW.d d)
sup
M _ell 0
Vm with probability al least cexp (-u² /4), where is an absolute constant.
tE|T]
Proof: Note that equation equation is a uniform bound over iteration t E [T]. To bound sUPte[T] ||M Eg E,12. it is sufficient bound
sup [M((w) - E(w)ll2
(22)
wEW
where W contains the possible trajectorys of Wi,... WT
We consider a sequence of subsets Wn, of W, and
card Wn, s Nn.
(23)
where No = N, = 2 if 1
Let nn (w) Wn be the approximation of any W. We decompose the [|M((w) E(w)ll2 as
[[M(w) E(w)ll2 [l - M(To(w))ll
Σ (II - I(Tr(w)))l - (IM( - I(Tn-1(W))l2))
(24)
n21
which holds since T., (w) for large enough.
Based on Lemma] for any u > 0, we have
[[,((, [(TT(W)))ll |M (=)=((((w)) - ((mn-1()))l22 Vm
[Gpd(TT(()) nn mn-)(w));
(25)
with probability at most 2p expxp(-
For any n > 0 and w E W, the number of possible pairs (T.(W), mn-1 (w)) is
card W. card Wn-1 Na S Nn+1 =22 22--1
(26)
Apply union bound over all the possible pairs of (mw(w), (w)), following Talagrand 2014
(Chapter 2.2), for any n > 0, a >> O, and w E W, we have
4Gp
(Tx, (w)) ((TT(w))) IIM (-n- (w)) - 2In (w))ll2 2 u2n / (w), on (w))
vm
(27)
with probability
exp (-u?2n-2) S dpexp (
42
Σ
2p 22
(-4)
(28)
where c' is a universal constant.
Then we have
(II((T((W)) - E(Tn(w))]l) (.M(T-I(W)) I(Tn-1(w))ll
4Gp
u2 22 12 (w), xn-1(w))
Vm
4Gp
n / Wr)
(29)
vm
20
16

---

Published as a conference paper at ICLR 2021
with probability at most exp (-4).
From Theorem let Y; (((ra())a)1((((m))aaa) that |||||| I and |E|]]] I 1. Then have
G
[ - ([m 2
(30)
Vm
with ptobability at most cxp
Combine equation
24 equation
29
and equation 30
have
4Gp
G
sup weW
[[ E(w)ll2 2 sup
u2n u2n/'d(,, W(w
wEW
/m
m
n20
(4pm2(W) d) + +1)
u
(31)
m
with probability at most (d 2)p exp
(-44)
That completes the proof.
Now we provide the proof Theorem
Theorem (Subspace Closeness) Under Assumption and with (t(t) to be the top-k eigenvec-
tors of the population second moment matrix E, and Oa be the eigen-gap at 1-th iterate such that
if D(s
d (Ex) dut1 (Er) 2 as for the (t) in Algorithm
we have
mine oz
E [1VA00)200) V((() so (GDVImpra(Wd))
11 E (T).
(2)
arym
Proof:
Recall that Va((t) is the top-k eigenspace of Mr. Let (t) be the top-k eigenspace of Σ,, (1 (I 11 (k) + (I M.
(t()) - (a(t)Va(t)
1I (k)
(32)
(I - (t) S | (A) M. (I C. lll |I(T
(33)
where (k) ((( denotes the projection to the top-k subspace of the symmetric PSD M, Mr
and (T (t) denotes the projection the top-k subspace of the symmetric PSD Σ, Then, from Davis-Kahan (Corollary 8 in McSherry (2004)) and using the fact for symmetric PSD matrices eigen-values and singular values are same, we have
I E2112
M (T
12 S (x(Mi \+ (E+)
(34)
| E
[I
(35)
AR (Σx) - AR+ (M)
Recall, from Horn and Johnson 2012) (Section 4.3) and Golub and Van Loan (996) e.g., Corollary 8.1.6, we have
from/Horn
(Section 8.1.2),
(M)) - (x,) < ||M, E,1la
(36)
From Theorem and Lemma with Y = -IMe - -r-l222 A c. and 4Gp.l
we have vm
E BlI Eella] 00 (GDVImpr2(M,d)) (
(37)
Vm
Let co = O (GP/lmpre(Wd))) For m > - we have
Co
01
E M| - Er112] <
<
(38)
Vm
2
17

---

Published as a conference paper at ICLR 2021
Then, for equation 34
we have
I Exl12
12
(M - Ak+1 (Ee)
M (1,) - (Ax(Ee) {x(M))
Exll2
(Ax(Ee) - Au+1
M 1/2
(39)
04 M Eel12
Then, for equation 35 we have
11Me Eell2
[I 12 - (2,)) (M+
1| Eelle
(Ax(Ee) - Ak+1 Ax+1(Ee)) )} + (Ax-1(E() Ax+z((M)))
M E
(40)
04 |
"ill2
Combining these bounds and equation
37 with co =0 ( we have
E (I1
20z
-2
E [[]
Σ, Ex112]
200
vT
(41)
01
mm
Using equation 38 such that
co
S as we have
Vi 2
- 12 so (GDvImpaa(Wdd)
(42)
aaym m
That completes the proof.
Lemma (Lemma 2.2.3 in Talagrand (2014)) Consider a F.V. Y 2 0 which satisfies
u²
Vu 0, P(Y 2 u) S Aexp
(43)
B
for certain numbers A 2 2 and B > 0. Then
EY CB A,
(44)
where C denotes a universal constant.
A.2 GEOMETRY OF GRADIENTS AND FUNCTIONS.
In this section, we provide more intuitions and explanations of 72 functions. We justify our assump- tions about the gradient space and provide more examples of the gradient space structure and the corresponding 7/2 functions.
Ata high level, for metric space (M, (M,, d) is related to Vlog dM,d,e) where N(M, c) is the covering number of M with balls with metric d, but is considerably sharper. Such sharpen- ing has happened two stages in the literature: first, based on chaining, which considers an integral over all yielding the Dudley bound, and subsequently, based on generic chaining, which consid- ers a hierarchical covering, developed by Talagrand and colleagues, and which yields the sharpest bounds of this type. The official perspective of generic chaining is to view 72 72M,, d) (and lower) bound on suprema of Gaussian processes indexed on M and with metric d [Theorem 2.4.1 in Talagrand (2014)).
upper
18

---

Published as a conference paper at ICLR 2021
Considering d to be the bg norm distance, 7/2 (M, d) will be the same order as the Gaussian width of M (Vershynin 2018), which is a scaled version of the mean width of M. Structured sets (of gradients) have small Gaussian widths, e.g., L1 unit ball in R2 has Gaussian width of O(ylog wheras a I/2 unit ball in Re has a Gaussian width of O(yp)-
To utilize the structure of gradients example shown in Figure ? instead of focusing the 72(,, d), we can also derive the uniform convergence bound using the measurement d on the set of population gradient m EzEp [V(w z)]. We consider a mapping f W + M from the param- eter space W to the gradient space M, where f can be considered as f(w) ExEP [V(w, [)] With m, Esep [V(w, 2)] and .M be the space of the population gradient m, M, d(m, m') with REEP [V(w'; 2)]. With such mapping J, the admissible se- corresponds to the admissible quence Tw (W,, n 2 0} of W in the proof of Theorem 2
the pseudo metric d(w, w') can be written as d(w, w') = d(f(w), f(w")
m EZEP [V(w, =)] and m'
sequence I M {M, n 2 0} of M. The 72W, = inff suPwew En 2n/2d (w, W,) = infrm supmEM Emzo 2d/2d (m, = 72(M.d) Considering d(m, m') = || m 112. the (2(M, d) will be the same order as the Gaussian width of M. i..., w(M) = Ev [sup (m, v)]. where N Ip).. Below, we provide more examples of the gradient space structure and the %2 functions.
Ellipsoid. The Gaussian width w(M) depends on the structure of the gradient In Figure 2
observe that, for each coordinates of the gradient is of small value along the training trajectory and
>> m,) ( s e,e R²). Then we have (M, d) I c1w(M) S c2lle|1a Talagrand (2014). where 01 and c are absolute constants. If the elements of sorted in decreasing order satisty e(J) S ca/ vj for all
thus .M includes all gradients living in an ellipsoid, i.e., M {m, R.
j E [p]. then (M, d) I O (vlogp).
Composition. Based on the composition properties of 722 functions Talagrand 2014 one con- struct additional examples of the gradient spaces. If M = MM +M, {m + m2, m, E M1. m2 _22. the Minkowski sum, then (M,, S c(72(M1, d) + (M,, d)) (Theorem 2.4.15 in Talagrand (2014), where is an absolute constant. M is a union of several sub- set, i.e., M
- Mr. then by using an union bound on Theorem 2 we have (2,, S Vlog D max, 72 (M,,, d). Thus, if M is an union of = p" ellipsoids, i.e., polynomial p. then (2( || l12) S O (Vslogp).
B PROOFS FOR SECTION 3.2
In this section, we present the proofs for Section 3.2 Then we present the error rate for convex problems in the subsequent section.
Theorem (Smooth and Non-convex) For p-smooth function i.,, (w), under Assumptions
and
let A Ed
El 1/2. for any e, O, with T Onn²²) and nt. V PDP-SGD achieves:
T (WV z kpp2 +0 AG 22 d))np'
1
(3)
Additionally, assuming the principal component of the gradient dominates, i.e., there exist > 0,
such that + Et [. (w.)) < of Σt= [[ Lin (w.))""l} we have
kpG2
AG (W, Inp
+
(4)
ThE
m
where wa is uniformly sampled from (Wi,..., Wr].
Proof: Recall that g: [..T
1 ExER, Ve(W,, 2,). With B, uniformly sampled from S, we have
E, [g. VL,
(45)
Recall that the update of Algorithm 1
g VAVY (gr by), and w W. -1-
(46)
19

---

Published as a conference paper at ICLR 2021
Let g: g: V.VV bt, and A, V.VV g+ gt.
Then have
A..
(47)
Since b, is a zero mean Gaussian vector, we have
(48)
For p-smooth function In (w). conditioned on We we have
Es Ln (We+z))
- Ln (wi) + E,, [< ((Ln((w)) We+1 w:) P
2 E
||
= Ln (w,) m1 ( (w:) + 4:) + 2 E2
|| 11
= Ln (w,) 7/ (vin (w.). Vin (w:) + E, | +
2 E. || 1
2
= En (w:) 1/6 Vin.
(w.)(w)).,14))) RAA,) + 2 n E.
||::
(49)
Rearrange the above inequality, we have
T/ (w:)
1
+ T/ E, (wn((w))) Ao) I in (w,) - Ee [nn (Wetz))
+ 221
m2 E2
|
(50)
D1,1
Di.2
For Dr,1, let
vL, (w,) = llq. (VL. + lQ [V
(,, (w.)]
(51)
where Qe is (t))) and lQ, is the projection. Q, is the null space of Q+.
Il (inn()) = (L)
(52)
and
11 [Ln [ V2(O)) vin(W:))
(53)
We have
A, TQ. VV (()) g:] +T; (VA()) g:]
-1lt [gr].
(54)
So that we have
D1,1 = E, (LL, (we), 41)
-B, (Ila, V i.m. (w:)) To: Vi.. No: [g:)
-E, (Ha+ (i. [1 ((- gi)
- <[T (10 (is) [I II- V(()) vi:(ww)))
=-Vi. [- V((O)R((OTT (i.))..)
(55)
Bringing the above to equation
50 the right-hand side of equation 50 becomes
nell nell VelVVi,, (w:))1
n.D 17. v L, (w.)T [ (w.) - m/. VL.)(w:) [I- V2(O)R(()T] (in)))
1/t Vi. (w:)T [V (t)
Vi.(w.:)
mh. ( (w:)
(56)
'The Assumption suggests that the i.,, (w) is p-smooth.
20

---

Published as a conference paper at ICLR 2021
So that we have
Te Wl In (we) Ee Ln (wo+1))
+ -
2
Bs
g8
(57)
For Dr., we have
E, 1 1 E,
VAVV B: + V.Va b
|Ivava Bi|1 1|: | b
E,
G2 ko?
(58)
Thus,
D1,2 = R, || 2 | b S G + ko?
(59)
Bringing the upper bound of Da.2 to equation 57 setting ?) vা the expectation over all iterations, we have
using telescoping sum and taking
El| ( S Ln(wi) - Li
p(G² + ko²)
(60)
VT
2VT
With triangle inequality and Theorem we have
2 Va(O)a(OTVin (w.) | s (a(C)v (w.) (w:))l
1|=== +2 +2|(V4(0VV(0
VLn (w:) 122
2
2 ((()) (w:)
G+ G (n
(we)
+0
(61)
arm
With equation 60 we have
Ln(wi)
p(G² -ko2)
(AG* A Inp
+0
vT/2
VT
m
(62)
where A -ET
1 o?
Let Vin((:))
(wa))
VV(I and [in
vin(w.)
Assuming there exist c > 0, we have
113=
(w.) 1
Σ E3
Vin (w:))
s E
vin
(63)
Then have
1
(L
(L.(w))- ii
GCG + koo2)
LG d) lup
E
5 (1+c)
/T/2 VT/2
+
+0
T
vT
t=1
(64)
Take T= n?? with E. (I
= Er' E
V i.,, (w:)12: we have
kpG2
AG (G=+22g(WV d) Imp
E (
+ +0
(65)
where is uniformly sampled from (Wi.... WT).
21

---

Published as a conference paper at ICLR 2021
C ERROR RATE OF CONVEX PROBLEMS
For the convex and Lipschitz functions, we consider the low-rank structure of the gradient space, i.c, the population gradient second momment Σ, is of rank-k, which is special case of the principal gradient dominate assumption when
Theorem 6 (Convex and Lipschitz) For G-Lipschitz and convex function (n),, under Assump-
tions] 2 and assuming E, is of rank-k, let A Σx-1 1/a: for any e, 8 0. with T ( 1, the PDP-SGD achieves
step size 1ht VT"
kG²
(, Imp
[L (w)) - L. 50
+0
(66)
vm
ne
where W Eiz We and w is the minima of La (w).
PDP-SGD also demonstrates an improvement from a factor of p to h compared to the error rate of DP-SGD for convex functions (Bassily et al., 2014, 2019a). PDP-SGD also has the subspace reconstruction error, depending on the "/2 function and eigen-gap term A = 1/or//0// previous discussions, the "22 is constant with suitable assumptions of the gradient structure. For the eigen-gap term, og stays as a constant in the training procedure as shown by Figure A will be a constant and the bound scales logarithmically with p. If assumes the eigen-gap a decays training proceed, e.g., O4 マ47 for 0, then have A O(VT). In this case, with O e), PDP-SGD requires public data size m = O(nc).
From
Recently, Kairouz et al. (2020) propose noisy version of AdaGrad algorithm for unconstrained con- vex empirical risk minimization. Their algorithm operates with only private data and also achieves a dimension-fret excess risk bound, i.e., Ó(r/ne,, by assuming the gradients along the path of optimization lie in a low-dimensional subspace with constant rank The bounds are not directly comparable since the assumptions Kairouz et al. (2020) are different from those in this paper, i.e., Kairouz al. (2020) assume that the accumulated gradients along the training process lie in constant subspace which requires the rank the gradient space does not explode when adding more stochastic gradients. Our work does not impose such constant subspace assumption E, allowing the subspace of E, to be different along the training process. In other words, our bounds hold even when the rank of the accumulated stochastic gradients space increases training proceeds.
Proof of Theorem
By the convexity of i,, (w), we have
L.(w)) (,(ww) S (We w', VLn(w)))
(67)
At iteration I, we have We+1 = W. - Trge, where g: V.VTT + Va V...
Let g: = g: + Vi br, and A, = V.Vi.g ge. Then we have
= B At.
(68)
Recall that g: [B.T Ex,n, Ve(We,
With B, uniformly sampled from S, we have
Ex g Vin (we).
(69)
Since b, is Gaussian vector, have E, [g(B.] gi-
22

---

Published as a conference paper at ICLR 2021
By convexity, conditioned at Wi, have
E (w.,,(w.) Ln (w*)]
E((we - ww, .gi)
Ee(we .')
Ee(we, w", we - Wi+1 - -.
T)
1 E, (I[w; w" 11 1/( 18:12 |e+t - -
21lt
1 E, (l/w:
w" 112 + nH lg || w 1 2( w., (*-))))))
2771
1 E. (I[w; w31 - || (1) + 2h マタ E1111 EA
21tt
Ey (W411 w A1)
(a) 1 Ey (I|w, w0 - + " GG2 + koo) + BE, / Aell,
- w=1
(70)
27/
where (a) is since
Eg gg
< E, g:
IIVe V bell
S G2 + ko²
(71)
and W w*1l2 S B
Let 1/2 taking the expectation over all iterations and sum over / 1 1,.., T, we have
Ln (w)) - En((w') <
Wo
w' w12 +
G2 + ko²
BEL B
(72)
2VT
T
From Theorem
we have
R2 [|] = E
(a(1) - V(IV() g:
$ E (((O)R2()T - V(OV(T G
< GE
(A(t)VA(O) - (t( + -IV
(Gp
0o
(73)
avym
where the last inequality holds because the Dg is of rank A and V(t) = V&(t).
Bring this equation 72 use the fact that || |wo w+
B, with Jensen's inequality we have
E [w) i.,(w') < B² + G + ko²
o AAGp AGG
(74)
2
m
where A -E 1
oee
With o² = GT n422,
let T n222, we have
B2
(AGll Vm
[w) - 50
+0
(75)
me
That completes the proof.
For problem, we consider H. where H {w ||w| B).
23

---

Published as a conference paper at ICLR 2021
D EXPERIMENTAL SETUP AND ADDITIONAL RESULTS
Datasets and Network Structure. The MNIST and Fashion MNIST datasets both consist of 60,000 training examples and 10,000 test examples. To construct the private training set, we randomly sample 10, 000 samples from the original training set of MNIST, then we randomly sample 100 samples from the rest to construct as the public dataser D Details refer to T For both MNIST and Fashion MNIST, jct al. (2020) whose architecture is described in Table T All experiments have been run on NVIDIA Tesla K40 GPUs.
convolutional neural network that follows the structure in Papernot
Table 1: Network architecture for MNIST and Fashion MNIST. Parameters
Layer
Convolution
16 filters of 8 x 8, strides 2 x 2
Max-Pooling
Convolution
32 filters of 4x4, strides 2
Max-Pooling
x 2
Fully connected
32 units
Softmax
10 units
Table 2: Neural network and datasets setup.
Dataset
Model
features
classes
Training size
Public size
Test size
MNIST
CNN
28 28
10
10,000
100
10,000
Fashion MNIST
CNN
28x 28
10
10,000
100
10,000
Hyper-parameter Setting. We consider different choices of the noise scale, i.e., a {18, 14, 10, 8, 6,4) for MNIST and {18, 14, 10, 6,4,2] for Fashion MNIST. Cross-entropy is used as our loss function throughout experiments. The mini-batch size is set to be 250 for both MNIST and Fashion MNIST. For the step size, we follow the grid search method with search space (0.01, 0.05. 0.1,0.2) to tune the step size for MNIST and the search space is (0.01, 0.02, 0.05, 0.1, 0.2) for Fashion MNIST. We choose the step size based on the training accu- racy at the last epoch. The best step sizes for DP-SGD and PDP-SGD for different privacy levels are presented in Table and Table for MNIST and Fashion MNIST, respectively. For training, fixed budget on the number of epochs i.e., 30 is assigned for the each task. We repeat each experiments 3 times and report the mean and standard deviation of the accuracy on the training and test set. For PDP-SGD, the projection dimension & is hyper-pare paremmeerrttr and it illustrates trade-off between the reconstruction error and the noise reduction. A small l implies more noise amount will be reduced, and larger reconstruction error will be introduced. We explored l (20, 30, 50) for MNIST and k = {30, 50, 70} for Fashion MNIST, and we found that & = 50 and A = 70 achieve the best perfor- mance for MNIST and Fashion MNIST respectively among the search space we consider. Instead of doing the projection for all epochs, we also explored start point for the projection, i.c., executing the projection from the 1-th epoch, 15-th epoch. The information of projection dimension and the starting epoch for projection are also given in 3 and Table for MNIST and Fashion MNIST, respectively.
Privacy Parameter Setting. Since gradient norm bound G' is unknow for deep learning, we fol- low the gradient clipping method Abadi et al. (2016) to guarantee the privacy. We implement the micro-batch clipping method in Py ToTch for MNIST and Fashion MNIST, respectively. Note that training with micro-batch clipping will need the noise scaled by micro-batch size to guarantee the same privacy. But it takes less time than training with per-sample clipping, i.e., micro-batch = I. We follow the Moment Accoun- tant (MA) method (Bu al. 2019) to calculate the accumulated privacy cost, which depends on the number of epochs, the batch size, d, and noise variance a. With 30 epochs, batch size 250,
We use micro-batch
and micro-batch
SDD can work with larger training set as well. We randomly sample 10,000 samples due to the limitation of computation resources, c.g., GPUs.
We implement the clipping method based on this repository: htpps//ggtthhhomm//haaaaaeeeeyy
24

---

see that Published as a conference paper at ICLR 2021
Table 3: Hyper-parameter settings for DP-SGD and PDP--GG for MNIST.
a = 18
о = 14
a= 10
0 =
a= 6
0 0= 4
(c = 0.23)
(c = 0.30)
(6 = 0.42)
(c = 0.53)
(c 0.72)
(c 1.09)
DP-SGD
Step size
0.05
0.05
0.05
0.05
0.1
0.1
PDP-SGD
Step size
0.1
0.2
0.2
0.1
0.1
0.2
Starting epoch for projection
15
15
Projection dimension & 50
50
50
50
50
50
10, 000 training samples, and fixing 5 = 10-5, the e is {2.41, 0.4,, 0.23) for E {2, 4, 6, 10, 14, 18} for Fashion MNIST. For MNIST, is {1.09, 0.72, 0.53, 0.42, 0.30, 0.23) corresponding to a {4, 6, 8, 10, 14, 18). Note that the presented in this paper is w.r.. a subset i.e, 10, 000 samples from MNIST and Fashion MNIST. Also, one fix the value of and do search over the epochs, batch size and noise scale to boost the performance for a fixed privacy level We omit such complicated hyper-parameter tuning since it has high risk of privacy leakage.
Table 4: Hyper- settings for DP-SGD and PDP-SGD for Fashion MNIST.
18
14
10
2 (e 2.41)
0.23)
(c 0.30)
(e = 0.42)
(c= 0.72)
(c 1.09)
DP-SGD
Step size
0.01
0.01
0.01
0.02
0.02
0.05
PDP-SGD
Step size Starting epoch for projection
0.01
0.01
0.02
0.02
0.02
0.05
15
15
15
15
15
15
Projection dimension &
70
70
70
70
70
Additional Experimental Results. Training dynamics of DP-SGD and PDP-SGD with different privacy levels are presented in Figure and Figure respectivell for MNIST and Fashion MNIST. The results suggest that for small PDP-SGD can effeciently reduce the noise variance injected to the gradient, which improves the training and test accuracy over DP-SGD.
In order to understand the role of projection dimension k. we run PDP-SGD with projection starting from the first epoch. Figure reports the PDP-SGD with k E {10, 20, 30, 50) for MNIST with 0.53 (Figure 9b)). Among the choice of k. PDP-SGD with A: 50 performs better that the others in terms of the training and test accuracy. PDP-SGD with A: = 10 proceeds slower than PDP-SGD with k 20 and k = 50. This is due the larger reconstruction error introduced by projecting the gradient to much smaller subspace, i..c, = 10. However, compared the gradient dimension p 25, 000, it is impressive that PDP-SGD with & = 50 which projects the gradient to the a much smaller subspace, can achieve better accuracy than DP-SGD.
0.30 (Figure [a)) and
We also empirically evaluate the effect of the public sample size m. Figure 11 (a) and Figure b) present the training and test accuracy for PDP-SGD with E (50, 150, 200) for e 0.23 and 1.09 for Fashion MNIST dataset. The training and test accuracy of PDP-SGD increases as the public sample size increases from 50 to 150. This is consistent with the theoretical analysis that increasing m helps reducing the subspace reconstruction error suggested by the theoretical bound. Also, PDP-SGD with m = 150 and m = 200 performs slightly better that m = 50 in terms of the training and test accuracy. The results suggest that while small amount of public datasets are not sufficient for training an accurate predictor, they provide useful gradient subspace projection and accuracy improvement over DP-SGD.
We also compare PDP-SGD and DP-SGD for different number of training samples, i.c. MNIST with 20,000 samples (Figure a) and Fashion MNIST with 50,000 samples (Figure [2 (100
25

---

Published as a conference paper at ICLR 2021
public samples for both case). The observation that PDP-SGD outperforms DP-SGD for small regime in Figure also holds for other number of training samples.
We also explore PDP-SGD with sparse eigen-space computation, i.c. update the projector every iterates, Note that PDP-SGD with s = means computing the top eigen-space at every iteration. Figure 13 reports PDP-SGD with Fashion MNIST with 50,000 samples showing that there is a mild decay for PDP-SGD with fewer eigen-space computation. PDP-SGD with a reduced eigen-space computation also improves the accuracy over DP-SGD.
{1, 10, 20) for (a) MNIST with 50,000 samples and (b)
80
70
trein accuracy
train accuracy
60
50-
80
PDP-SGD
PDP-SGD
PDP-SGD
DP-SGD
10
30
10
15
20
(a) Training accuracy, 0.23
(b) Training accuracy, 0.30
(c) Training accuracy, 0.42
80
80
best accuracy
test test accuracy
accuracy
80
60
80
80
30
20
DP-5GD
DP-SGD
DP-5CD
10
15
20
15 20
25
25
30
(d) Test accuracy, 0.23
(c) Test accuracy, e 0.30
(f) Test accuracy, 6 0.42
Figure 7: Comparison of DP-SGD and PDP-SGD for MNIST. (a-c) report the training accuracy and (d-f) report the test accuracy for e {0.23, 0.30, 0.42). The X-axis the number of epochs, and the Y-axis is the train/test accuracy. DPD-SGD outperforms DP-SGD for small e.
60
train accuracy
accuracy
50
30
20
PDP-SGD
PDP-SGD
DP-SGD
DP-SGD
10
10.
15.0
17.5
20.0
22.5
25.0
27.5
30
15.0
17.5
20.0
22.5
25.0
27.5 30.
(a) Training accuracy, 0.23
(b) Training accuracy, 0.30
60
test accuracy
50
test accuracy
40
30
PDP-SGD
20
PDP-SGD
DR-SGD
DR-SGD
(c) Test accuracy, E 0.23
(d) Test accuracy, 0.30
Figure 8: Comparison of DP-SGD and PDP-SGD for Fashion MNIST. (a-b) report the training
accuracy and (c-d) report the test accuracy for {0.23, 0.30}. Learning rare is 0.01 for both PDP-SGD and DP-SGD. PDP-SGD starts projection at 15-th epoch. The X-axis is the number of epochs, and the Y-axis is the train/test accuracy. DPD-SGD outperforms DP-SGD for small c.
26

---

Published as a conference paper at ICLR 2021
80
train accuracy
test accuracy
train accuracy
accuracy
40-
PDP-SGD, K =10
PDP-SGD, k -10
80
PDP-SGD, k =10
POP-5GD, k =10
PDP.SGD, =30
PDD k =30
PDR-SAD, =30
POP-S6D, -30
PDP-SGD, k50
PDP-500, =50
PDP-SGD, k =50
PDP =50
of epochs
number epochs
number epachs
number epochs
(a) MNIST, 0.30
(b) MNST, 0.53
Figure 9: Training accuracy and test accuracy for PDP-SGD with k: {10, 20, 30, 50) for (a) MNIST with = 0.30; (h) MNIST with = 0.53. The X-axis and Y-axis refer to Figure 4 PDP- SGD with k 50 performs better that the others in terms of the training and test accuracy.
train accuracy
test accurady
train accuracy
accuracy
80
40-
PDP-SGD, m =50
PDP-SGD, =50
POP-SGD, m =50
PDP-SGD, m =50 PDP-SGD,
20
PDP-SGD.
PDP-SGD,
POP-SGD, -100
PDP SGD,
=150
PDP-SGD, =150
POP-SGD, m =150
PDP-SGD, m =150
20 number of epochs
30
20 number of epochs
30
number epochs
number of epochs
(a) MNIST, 0.30
(b) MNST,
0.42
Figure 10: Training accuracy and test accuracy for PDP-SGD with {50, 100, 150) for (a) MNIST with = 0.30; (b) MNIST with 0.53. The X-axis and Y-axis refer to Figure 4 PDP- SGD with m 150 and 100 perform better that the others in terms of the training and test accuracy.
70
60
train accuracy
test accuracy
train accuracy
accuracy
50
60
40-
POP-SGUD m =50
SUP, m =50
PDP-SGD, -50
PDP-SGD, -0
20
POP-SGD,
PDP-SGD,
PDP-SGD, -150
PDP-SGD, m155
POP-SGD, =200
PDP SGD, =200
PDP-SGD, m -200
PDP-SGD, -00
10
15
20
25
30
15
20
25
30
number of epochs
number of epochs
number epochs
number epochs
(a) MNIST, 0.23
(b) MNST, 1.09
Figure 11: Training accuracy and test accuracy for PDP-SGD with {50, 150, 200) for (a) MNIST with 0.23; (b) MNIST with 0.43. The X-axis and Y-axis refer to Figure 4 PDP- SGD with m = 150 and m 200 performs slightly better that the other one in terms the training and test accuracy.
90
70
accuracy
train accuracy
accuracy
85
test accuracy
68
23
PDP-SGD
PDP-SGD DP-SGD
80
PDP-SGD DP-SGD
PDP-SGD DP-SGD
70-
DP-5GD
45
0.2
DP-E
0.4
0.6
0.2
DP-s
0.4
0.6
0.2
DP-E
BA
0.6
0.2
DP-g
0.6
(a) MNIST
(b) Fashion MNIST
Figure 12: Training and test accuracy for DP-SGD and PDP-SGD with different privacy levels for (a) MNIST with 20,000 samples and (b) Fashion MNIST with 50,000 samples. The X-axis and Y-axis refer Figure For small privacy loss c, PDP-SGG outperforms DP-SGD.
27

---

Published as a conference paper at ICLR 2021
80
train accuracy
70
rest accuRa
train accuracy
test accuracy
60-
PDP-SGD, =5
PDP-SGD, -5
DDP-SGD,
PDP.SGD,
50
PDP-SGD, =10
POP-SGD, =10
80
PDP-SGD, 5 -10
PDP-SGD, : -10
PDP-SGD,
DP-SGD
DP-5GD
DP-5GD
DP-5GD
2
10 number of epochs
14
10 number of epochs
14
number of epachs
number of epochs
(a) MNIST, 0.06
(b) Fashion MNIST, 0.07
Figure 13: Training and test accuracy for PDP-SGD with different frequency of eigen-space computation for (a) MNIST with 50,000 samples and (b) Fashion MNIST with 50,000 samples. {5. 10, 20) the frequency subspace update, i.e., compute the eigen-space every iterates. The X-axis and Y-axis refer to Figure 4 PDP-SGD with a reduced eigen-space computation also improves the accuracy over DP-SGD.
28


Reviews:
[{"review_id": "Y5UNRRaAdfw", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposes a new private SGD method by projecting the noise gradient onto a subspace, which is estimated using some public datasets. The proposed method can improve the utility guarantee by reducing the dependence of the problem dimension p. The idea of the proposed method is interesting, but the assumptions in the current paper seem to be very strong, and the evaluations in the current paper are not convincing to show that the proposed method is beneficial. \n1. It is not always true in practice that we can have access to the public dataset.\n2. In Theorem 4, the assumption about the principal component of the gradient looks very strong. \n3. How will the size of the public dataset affect the performance of the proposed method? It is important to have empirical evaluations on this.\n4. Another issue of the proposed method seems to be the computational barrier. Why can the proposed method only deal with 10000 samples in MNIST dataset compared with DPSGD, which can deal with the whole training dataset?\n5. I think the most valuable thing about the proposed method is to reduce the dependence of the problem dimension p. Therefore, it is very important for the authors to consider larger models such as resnet. If the proposed method can achieve better performance on larger models, I think the proposed method is very convincing. \n\n-----\nAfter reading the author response and other reviews, most of my concerns have been addressed. I would like to increase my score to 6. It would also be interesting to compare the performance of DP-SGD and PDP-SGD when $\\epsilon$ is relatively large as suggested by Figure 7.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EKEjdTzr7bV", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 author proposes an algorithm that improves DPSGD by using public data to identify a lower-dimensional space where the gradients lie in. They show that the algorithm can provide a better convergence guarantee, specifically, p reduced to log(p). They also conducted experiments to show the proposed algorithm outperforms the generic DPSGD especially at small epsilon with a small amount of public data.\n\nThe topic of the paper is interesting, and the presentation is clear. I hope the significance of the paper can be better justified. On the theory side, I think it needs more comparison with prior work and needs a better explanation of some of the key concepts. On the experiment side, to make the results more convincing, it might be better to conduct evaluations on harder datasets.\n\nComments:\n\n- In related work, it is said that \"Kairouz et al. (2020) .... In comparison, our work studies both convex and non-convex problems and our analysis applies for more general low-dimensional structures that can be characterized by small γ2 functions (Talagrand, 2014) (e.g., low-rank gradients and fast decay in the gradient coordinates)\". I believe Kairouz et al was operating on private data only and that might be a major difference. And it might still be interesting to compare the results in more detail, e.g. how do the bounds compare on convex problems, how do the two measurements of dimensionality compare.\n\n- Line 4 of Alg 1: better to say \\tilde{z_i} \\in S_h than enumerating i from 1 to m (m is undefined in the algorithm).\n\n- It is mentioned that if M is evaluated on fresh public samples at each iteration, then the deviation of M from Σ can be analyzed easily. I wonder if it worth discussing what would happen if partition the public data (given that we have more than T samples) into T disjoint subsets for each iteration. Would the tradeoff be worse?\n\n- Since γ(M, d) is the main component in the analysis and the bound, can you provide more intuition and explanation of it, like how large it can get, on what kind of dataset it might be small/large, would model architecture make a difference etc.?\n\n- A question regarding the experiment setup: I didn't quite understand why a subset of 10000, instead of (60000 - 100), of the original data is picked for training. 10000 is definitely a legitimate setting, but I just wonder if there is a reason for picking that number and whether the number of examples has any influence on the results.\n\n- In the experiments in Figure 5, as k=50 (or 70) outperforms DPSGD without projection, it might make more sense to further increase k to demonstrate the tradeoff between the two types of errors.\n\n- A minor point: Sec 4 said \"Papernot et al. (2020) shows the accuracy of DP-SGD is around 80% when ε ≈ 1\", which I'm not sure is accurate. I didn't find Papernot et at (in Table 4) reporting the accuracy for epsilon around 1. If the statement is referring to the leftmost point in Fig 3 of Papernot et al., I believe it is not a fair comparison. The figure basically showed a training process in terms of epsilon instead of steps, so the result is not optimized for epsilon = 1 (but is rather for epsilon = 2.93). On the other hand, the [tensorflow privacy tutorial](https://github.com/tensorflow/privacy/tree/master/tutorials) achieves 95% at epsilon = 1.19.", "extra_scores": {}, "extra_text": {}}, {"review_id": "BpwasAobviN", "reviewer": "AnonReviewer3", "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 considers the problem of solving differentially private empirical risk minimization. To reduce the dependence on dimensionality $p$, they propose Projected DP-SGD (PDP-SGD) that projects the noisy gradients to a low-dimensional subspace computed from a free public dataset at each iteration. They prove that PDP-SGD is differentially private and has only a logarithmic dependence on $p$.\n\nPros:\n1. The paper is well written and easy to follow. \n2. It is very appreciated that authors analyze both convex and non-convex cases. All proof seems correct except for a minor mistake mentioned in the next part. What’s more, The method of uniformly bounding $\\|M_t-\\Sigma_t\\|_2$ by generic chaining techniques may be an independent interest. \n\nCons and some discussion: \n1. The establishment of (28) requires $u$ is larger than a constant (like 3), even though this would not affect the correctness of Theorem 2. The last inequality of (55) should be equality.\n\nThe main concern of mine is that the experiment part is not so good as the theoretical part. \n\n2. The authors propose to reduce dimensionality by projection. The projected space varies for each iteration and is computed from a public dataset. However, I think the author didn’t explain well the necessity of using an extra dataset. If reducing dimensionality is the most important, why not just use a random projection. [1] shows that a Johnson-Lindenstrauss transform preserves differential privacy, so it is natural to use random projection as a baseline (at least in experiments). However, the baseline considered in experiments excludes this easiest method. Besides, it is better to add non-private SGD as a baseline, which would help illustrate how the proposed method degrades accuracy.\n3. The proposed method has a huge space complexity and computation complexity as it requires to formulate $M_t \\in \\mathbb{R}^{p \\times p}$ and compute its top-$k$ eigenvectors at each iteration. It will require $O(p^2)$ space and $O(p^3)$ times. As a remedy, one may hope to reduce the frequency of eigenspace computation. It seems to make sense, since when $w_t$ starts to converge, the difference between consecutive $w_t$ is so small that the difference between consecutive $V(w_t)$ is also small, implying we can reuse the eigenspace estimated in the last iteration. It strikes me that it is better to explore such a heuristic method in experiments to further illustrate the usefulness of the proposed method.\n4. I think more datasets should be considered. The author only considered two image datasets. Real datasets like CIFAR can be considered. \n\n[1] Blocki, Jeremiah, et al. \"The johnson-lindenstrauss transform itself preserves differential privacy.\" 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE, 2012.\n\n\n\n------------------------------------------------------------------------------------------\nI have read the authors’ rebuttal. The authors have addressed most of my concerns. The JL random projection baseline has been added and the heuristic method of reusing the eigenspace for some iterations has been explored, which I appreciate a lot. From the current experiments, the proposed method seems effective, though it will be more convincing if the method can be tested on larger models or harder datasets. \n\nI think the topic of the paper is quite interesting and the idea of bounding $M_t - \\Sigma_t$ uniformly is also interesting. The theory indeed manifests the effectiveness of the proposed method. As a result, I increase my point to 7.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the observation that the stochastic gradients for deep nets often stay in a low dimensional subspace, this paper proposes projected differential private SGD (DP-SGD) that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace. Under certain assumptions, the authors provide a theoretical analysis and empirical evaluations to show that the proposed algorithm can substantially improve the accuracy of DP-SGD in the high privacy regime. There is unanimous support to accept this paper after the author’s response. Thus, I recommend accept.
Decision: Accept (Poster)