Year: 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 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 lowdimensional 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 ).

heading: 1 INTRODUCTION
text: Many fundamental machine learning tasks involve solving empirical risk minimization (ERM): given a loss function `, find a model w ∈ Rp that minimizes the empirical risk L̂n(w) = 1 n ∑n i=1 `(w, zi), where z1, . . . , zn are i.i.d. examples drawn from a distribution P . In many applications, 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 et al., 2006) has by now become the standard approach to provide principled and rigorous privacy guarantees in machine learning. Roughly speaking, DP is a stability notion that requires that no individual example has a significant influence on the trained model. One of the most commonly used algorithm for solving private ERM is the differentially-private stochastic gradient descent (DP-SGD) (Abadi et al., 2016; Bassily et al., 2014; Song et al., 2013)–a private variant of SGD that perturbs each gradient update with random noise vector drawn from an isotropic Gaussian distribution N (0, σ2Ip), with appropriately chosen variance σ2. Due to the gradient perturbation drawn from an 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 `, Bassily et al. (2014) show that DP-SGD achieves the optimal empirical excess risk of Õ (√ p/(n ) ) . For non-convex loss `, which is more common in neural network
training, minimizing L̂n(w) is in general intractable. However, many (non-private) gradient-based optimization methods are shown to be effective in practice and can provably find approximate stationary points with vanishing gradient norm ‖∇L̂n(w)‖2 (see e.g. Nesterov (2014); Ghadimi and
Lan (2013)). Moreover, for a wide family of loss functions L̂n under the Polyak-Łojasiewicz condition (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 gradient norm down to Õ ( p1/4/ √ n )
when the loss function ` is smooth. Furthermore, exsiting lower bounds results on private ERM (Bassily et al., 2014) show that such dependence on p is 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 p 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 et al. (2020); Gur-Ari et al. (2018); Papyan (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 lower-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 1. Based on this observation, we provide a modular private ERM optimization framework with two components. At each iteration t, the algorithm performs the following two steps:
1) Gradient dimension reduction. Let gt be the mini-batch gradient at iteration t. In general, this subroutines solves the following problem: given any k < p, find a linear projection V̂k(t) ∈ Rp×k such that the reconstruction error ‖gt − V̂k(t)V̂k(t)ᵀgt‖ is small. To implement this subroutine, we follow a long line of work that studies private data analysis with access to an auxiliary public dataset Sh drawn from the same distributionP , 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., 2017). In our case, we compute V̂k(t) which is given by the top-k eigenspace of the gradients evaluated on Sh. 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 √ p (Dwork et al., 2014), which will be propagated to the optimization error.
2) Projected DP-SGD (PDP-SGD). Given the projection V̂k(t), we perturb gradient in the projected subspace: g̃t = V̂k(t)V̂k(t)ᵀ(gt+bt), where bt is a 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 reconstruction error on the gradients from projection of V̂k(t). This reduces to bounding the deviation ‖V̂k(t)V̂k(t)ᵀ − VkVk(t)ᵀ‖2, where Vk(t) denotes the top-k eigenspace of the population second moment matrix E[∇`(wt, z)∇`(wt, z)ᵀ]. To handle the adaptivity of the sequence of iterates, we provide a uniform deviation bound for all w ∈ W , where the set W contains all of the iterates. By leveraging generic chaining techniques, we provide a deviation bound that scales linearly with a complexity measure—the γ2 function due to Talagrand (2014)—of the set W . We provide lowcomplexity examples of W that are supported by empirical observations and show that their γ2 function only scales logarithmically with p.
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 assumptions on the gradient space, our rates only scales logarithmically on p.
Empirical evaluation. We provide an 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 linear 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 dimensionfree excess risk bound, provided that the gradients along the optimization trajectory lie in a lowdimensional subspace. In comparison, our work studies both convex and non-convex problems and our analysis applies to more general low-dimensional structures that can be characterized by small γ2 functions (Talagrand, 2014; Gunasekar et al., 2015) (e.g., low-rank gradients and fast decay in the magnitude of the gradient coordinates). Recently, Tramer and Boneh (2021) show that private learning with features learned on public data from a similar domain can significantly improve the utility. Zhang et al. (2021) leverage the sparsity of the gradients in deep nets to improve the dependence on dimension in the error rate. We also note a recent work (Yu et al., 2021) 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 p 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 a 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 a small public data set of size no more than 150 suffices.1

heading: 2 PRELIMINARIES
text: Given a private dataset S = {z1, ..., zn} drawn i.i.d. from the underlying distribution P , we want to solve the following empirical risk minimization (ERM) problem subject to differential privacy:2 minw L̂n(w) = 1 n ∑n i=1 `(w, zi). where the parameter w ∈ Rp. We optimize this objective with an iterative algorithm. At each step t, we write wt as the algorithm’s iterate and use gt to denote the mini-batch gradient, and ∇L̂n(wt) = 1n ∑n i=1∇`(wt, zi) to denote the empirical gradient. In addition to the private dataset, the algorithm can also freely access to a small public dataset Sh = {z̃1, . . . , z̃m} drawn from the same distribution P , without any privacy constraint. Notation. We write Mt ∈ Rp×p to denote the second moment matrix of gradients evaluated on public dataset Sh, i.e., Mt = 1m ∑m i=1∇` (wt, z̃i)∇` (wt, z̃i)
ᵀ and write Σt ∈ Rp×p to denote the population second moment matrix, i.e., Σt = Ez∼P [∇` (wt, z)∇` (wt, z)ᵀ]. We use V (t) ∈ Rp×p as the full eigenspace of Σt. We use V̂k(t) ∈ Rp×k as the top-k eigenspace ofMt and Vk(t) ∈ Rp×k as the top-k eigenspace of Σt. To present our result in the subsequent sections, we introduce the eigen-gap notation αt, i.e., let λ1(Σt) ≥ ... ≥ λp(Σt) be the eigenvalue of Σt, we use αt to denote the eigen-gap between λk(Σt) and λk+1(Σt), i.e., λk(Σt)−λk+1(Σt) ≥ αt. We also define W ∈ Rp as the set that contains all the possible iterates wt ∈ W for t ∈ [T ]. Throughout, for any matrix A and vector v, ‖A‖2 denotes spectral norm and ‖v‖2 denotes `2 norm.
Definition 1 (Differential Privacy (Dwork et al., 2006)) A randomized algorithm R is ( , δ)differentially private if for any pair of datasetsD,D′ differ in exactly one data point and for all event
1Note that the requirement of a large public data set may remove the need of using the private data in the first place, since training with the large public data set may already provide an accurate model.
2In this paper, we focus on minimizing the empirical risk. However, by relying on the generalization guarantee of ( , δ)-differential privacy, one can also derive a population risk bound that matches the empirical risk bound up to a term of order O( + δ) (Dwork et al., 2015; Bassily et al., 2016; Jung et al., 2020).
Y ⊆ Range(R) in the output range of R, we have P{R(D) ∈ Y} ≤ exp( )P{R(D′) ∈ Y} + δ, where the probability is taken over the randomness ofR.
To establish the privacy guarantee of our algorithm, we will combine three standard tools in differential privacy, including 1) the Gaussian mechanism (Dwork et al., 2006) that releases an aggregate statistic (e.g., the empirical average gradient) by Gaussian perturbation, 2) privacy amplification via subsampling (Kasiviswanathan et al., 2008) that reduces the privacy parameters 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 `.
Assumption 1 For any w ∈ Rp and example z, ‖∇`(w, z)‖2 ≤ G.
Assumption 2 For any example z, the gradient ∇`(w, z) is ρ-Lipschitz with respect to a suitable pseudo-metric d : Rp × Rp 7→ R, i.e., ‖∇`(w, z)−∇`(w′, z)‖2 ≤ ρd(w,w′), ∀w,w′ ∈ Rp.
Note that Assumption 1 implies that L̂n(w) is G-Lipschitz and Assumption 2 implies that L̂n(w) is ρ-smooth when d is the `2-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.

heading: 3 PROJECTED PRIVATE GRADIENT DESCENT
text: 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 bt ∼ N (0, σ2Ip) to the gradient gt, i.e., each coordinate of the gradient gt is perturbed by the Gaussian noise. Given the dimension of gradient to be p, this method ends up in getting a factor of p in the error rate (Bassily et al., 2014; 2019a). Our algorithm is inspired by the recent observations that stochastic gradients stay in a low-dimensional space in the training of deep nets (Li et al., 2020; Gur-Ari et al., 2018). Such observation is also valid for the private training algorithm, i.e., DP-SGD (Figure 1 (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 gt + bt to an approximation of such a subspace given by a public dataset Sh.
Algorithm 1 Projected DP-SGD (PDP-SGD) 1: Input: Training set S, public set Sh, certain loss `(·), initial point w0 2: Set: Noise parameter σ, iteration time T , step size ηt. 3: for t = 0, ..., T do 4: Compute top-k eigenspace V̂k(t) of Mt = 1|Sh| ∑ z̃i∈Sh ∇`(wt, z̃i)∇`(wt, z̃i)
ᵀ. 5: gt =
1 |Bt| ∑ zi∈Bt ∇`(wt, zi), with Bt uniformly sampled from S with replacement.
6: Project noisy gradient using V̂k(t): g̃t = V̂k(t)V̂k(t)ᵀ (gt + bt), where bt ∼ N (0, σ2Ip). 7: Update parameter using projected noisy gradient: wt+1 = wt − ηtg̃t. 8: end for
Thus, our algorithm involves two steps at each iteration, i.e., subspace identification and noisy gradient projection. The pseudo-code of PDP-SGD is given in Algorithm 1. At each iteration t, in order to obtain an approximated subspace without leaking the information of the private dataset S, we evaluate the second moment matrix Mt on Sh and compute the top-k eigenvectors V̂k(t) of Mt (line 4 in Algorithm 1). Then we project the noisy gradient gt + bt to the top-k eigenspace, i.e., g̃t = V̂k(t)V̂k(t)ᵀ (gt + bt) (line 6 in Algorithm 1). Then PDP-SGD uses the projected noisy gradient g̃t to update the parameter wt+1 = wt − ηtg̃t.3 Let us first state its privacy guarantee. Theorem 1 (Privacy) Under Assumption 1, there exist constants c1 and c2 so that given the number of iterations T , for any ≤ c1q2T , where q = |Bt|n , PDP-SGD (Algorithm 1) is ( , δ)-differentially private for any δ > 0, if σ2 ≥ c2 G2T ln( 1δ )
n2 2 .
3For convex problem, we consider the typical constrained optimization problem such that the optimal solution w? is in a setH, whereH = {w : ‖w‖ ≤ B} and each step we project wt+1 back to the setH.
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 gt + bt. Then the privacy guarantee of releasing the sequence of {gt+bt}t is exactly the same as the privacy proof of Theorem 1 of Abadi et al. (2016).

heading: 3.1 GRADIENT SUBSPACE IDENTIFICATION
text: We now analyze the gradient deviation between the approximated subspace V̂k(t)V̂k(t)ᵀ and true (population) subspace Vk(t)Vk(t)ᵀ, i.e., ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖2. To bound ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)
ᵀ‖2, we first bound the deviation between second moment matrix ‖Mt − Σt‖ (Dwork et al., 2014; McSherry, 2004). Note that, if Mt = 1m ∑m i=1∇` (wt, z̃i)∇` (wt, z̃i)
ᵀ is evaluated on fresh public samples, the Σt is the expectation of Mt, and the deviation of Mt from Σt can be easily analyzed by the Ahlswede-Winter Inequality (Horn and Johnson, 2012; Wainwright, 2019), i.e., at any iteration t, if we have fresh public sample {z̃1(t), ..., z̃m(t)} drawn i.i.d. from the distribution P , with suitable assumptions we have,∥∥ 1 m ∑m i=1∇`(wt, z̃i(t))∇`(wt, z̃i(t))ᵀ − E [∇`(wt, z̃i(t))∇`(wt, z̃i(t))ᵀ] ∥∥ 2 > u, ∀u ∈ [0, 1], with probability at most p exp(−mu2/4G) and G is as in Assumption 1. However, this concentration bound does not hold for wt,∀t > 0 in general, since the public dataset Sh is reused over the iterations and the parameter wt depends on Sh. To handle the dependency issue, we bound ‖Mt − Σt‖2 uniformly over all iterations t ∈ [T ] to bound the worst-case counterparts 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 a complexity measure called γ2 function (Talagrand, 2014). Note that one may consider the idea of sample splitting to bypass the dependency issue by splitting m public samples into T disjoint subsets for each iteration. Based on Ahlswede-Winter Inequality, the deviation error scales with O(
√ T√ m
) leading to a worse trade-off between the subspace construction error and optimization error due to the dependence on T .
Definition 2 (γ2 function (Talagrand, 2014)) For a metric space (A, d), an admissible sequence of A is a collection of subsets of A, Γ = {An : n ≥ 0}, with |A0| = 1 and |An| ≤ 22 n
for all n ≥ 1, the γ2 functional is defined by γ2(A, d) = infΓ supA∈A ∑ n≥0 2
n/2d(A,An) , where the infimum is over all admissible sequences of A.
In Theorem 2, we show that the uniform convergence bound of ‖Mt − Σt‖2 scales with γ2(W, d), where d is the pseudo metric as in Assumption 2 and W ∈ Rp is the set that contains all possible iterates in the algorithm, i.e., wt ∈ W for all t ∈ [T ]. Based on the majorizing measure theorem (e.g., Theorem 2.4.1 in Talagrand (2014)), if the metric d is `2-norm, γ2(W, d) can be expressed as Gaussian width (Vershynin, 2018; Wainwright, 2019) of the setW , i.e., w(W) = Ev[supw∈W〈w,v〉] where v ∼ N (0, Ip), which only depends on the size of the W . In Appendix A.2, we show the complexity measure γ2(W, d) can be expressed as the γ2 function measure on the gradient space by mapping the parameter space W to the gradient space, i.e., f : W 7→ M, where f can be considered as f(w) = Ez∈P [∇(w, z)]. To simplify the
notation, we write m = Ez∈P [∇(w, z)] as the population gradient at w andM as the space of the population gradient. Considering d(m,m′) = ‖m −m′‖2 for m,m′ ∈ M, γ2(M, d) will be the same order as the Gaussian width w(M). To measure the value of γ2(M, d), we empirically explore the gradient space M for deep nets. Figure 2 gives an example of the population gradient along the training trajectory of DP-SGD with σ = {1, 2, 4} for training a 2-layer ReLU on MNIST dataset. Figure 2 shows that each coordinate of the gradient is of small value and gradient components decay very fast (Li and Banerjee, 2021). Thus, it is fair that the gradient spaceM is a union of ellipsoids, i.e., there exists e ∈ Rp such that M = {m ∈ Rp | ∑p j=1 m(j)
2/e(j)2 ≤ 1, e ∈ Rp}, where j denotes the j-th coordinate. Then we have γ2(M, d) ≤ c1w(M) ≤ c2‖e‖2 (Talagrand, 2014), where c1 and c2 are absolute constants. If the elements of e are sorted in a decreasing order satisfy e(j) ≤ c3/ √ j for all j ∈ [p], then
γ2(M, d) ≤ O (√ log p ) .4 Now we give the uniform convergence bound of ‖Mt − Σt‖2.
Theorem 2 (Second Moment Concentration) Under Assumption 1, 2, the second moment matrix of the public gradient Mt = 1m ∑m i=1∇`(wt, z̃i)∇`(wt, z̃i)ᵀ approximates the population second moment matrix Σt = Ez∼P [∇`(wt, z)∇`(wt, z)ᵀ] uniformly over all iterations, i.e., for any u > 0,
sup t∈[T ]
‖Mt − Σt‖2 ≤ O ( uGρ √ ln pγ2(W, d)√ m ) , (1)
with probability at least 1− c exp ( −u2/4 ) , where c is an absolute constant.
Theorem 2 shows thatMt approximates the population second moment matrix Σt 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 γ2 functions. In our case, ‖Mt − Σt‖ is treated as the stochastic process indexed by the set W ∈ Rp such that wt ∈ W , which is the set of all possible iterates. The metric d is the pseudo-metric d : Rp × Rp 7→ R defined in Assumption 2. To get a more practical bound, following the above discussion, instead of working withW over parameters, one can consider working with the setM of population gradients by defining the pseudo-metric as d (w,w′) = d (f(w), f (w′)) = d (m,m′), where f(w) = Ez∈P [∇(w, z)] that maps the parameter space to gradient space. Thus, the complexity measure γ2(W, d) can be expressed as the γ2 function measure on the population gradient space, i.e., γ2(M, d). As discussed above, using the `2-norm as d, the γ2(M, d) will be a constant if assuming the gradient space is a union of ellipsoids and uniform bound only depends on logarithmically on p.
Using the result in Theorem 2 and Davis-Kahan sin-θ theorem (McSherry, 2004), we obtain the subspace construction error ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖2 in the following theorem.
Theorem 3 (Subspace Closeness) Under Assumption 1 and 2, with Vk(t) to be the top-k eigenvectors of the population second moment matrix Σt and αt be the eigen-gap at t-th iterate such that λk (Σt)− λk+1 (Σt) ≥ αt, for the V̂k(t) in Algorithm 1, if m ≥ O(Gρ √ ln pγ2(W,d)) 2
mint α2t , we have
E [ ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖2 ] ≤ O ( Gρ √
ln pγ2(W, d) αt √ m
) ,∀t ∈ [T ]. (2)
Theorem 3 gives the sample complexity of the public sample size and the reconstruction error, i.e., the difference between V̂k(t)V̂k(t)ᵀ evaluated on the public dataset Sh and Vk(t)Vk(t)ᵀ given by the population second moment Σt. The sample complexity and the reconstruction error both depend on the γ2 function and eigen-gap αt. A small eigen-gap αt requires larger public sample m.

heading: 3.2 EMPIRICAL RISK CONVERGENCE ANALYSIS
text: In this section, we present the error rate of PDP-SGD for non-convex (smooth) functions. The error rate for convex functions is deferred to Appendix C. For non-convex case, we first give the error rate of the `2-norm of the principal component of the gradient, i.e., ‖Vk(t)Vk(t)ᵀ∇L̂n(wt)‖2. Then we show that the gradient norm also converges if the principal component dominates the residual component of the gradient as suggested by Figure 1 and recent observations (Papyan, 2019; Li et al.,
4In the appendix, we provide more examplesM that are consistent with empirical observations of stochastic gradient distributions and have small γ2(M, d).
2020). To present our results, we introduce some new notations here. We write [∇L̂n(wt)]‖ = Vk(t)Vk(t)
ᵀ∇L̂n(wt) as the principal component of the gradient and [∇L̂n(wt)]⊥ = ∇L̂n(wt)− Vk(t)Vk(t) ᵀ∇L̂n(wt) as the residual component.
Theorem 4 (Smooth and Non-convex) For ρ-smooth function L̂n(w), under Assumptions 1 and 2, let Λ = ∑T t=1 1/α 2 t
T , for any , δ > 0, with T = O(n 2 2) and ηt = 1√T , PDP-SGD achieves:
1
T T∑ t=1 E‖Vk(t)Vk(t)ᵀ∇L̂n(wt)‖22 ≤ Õ ( kρG2 n ) +O ( ΛG4ρ2γ22(W, d) ln p m ) . (3)
Additionally, assuming the principal component of the gradient dominates, i.e., there exist c > 0, such that 1T ∑T t=1 ‖[∇L̂n(wt)]⊥‖22 ≤ c 1 T ∑T t=1 ‖[∇L̂n(wt)]‖‖22, we have
E‖∇L̂n(wR)‖22 ≤ Õ ( kρG2
n
) +O ( ΛG4ρ2γ22(W, d) ln p
m
) , (4)
where wR is uniformly sampled from {w1, ...,wT }.
Theorem 4 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 a term depending on the γ2 function and the eigen-gap αt, i.e., Λ = ∑T t=1 1/α 2 t /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 γ2 is a constant. The term Λ depends on the eigen-gap αt, i.e, λk (Σt)− λk+1 (Σt) ≥ αt. As shown by the Figure 1, along the training trajectory, there are a few dominated eigenvalues and the eigen-gap stays significant (even at the last epoch). Then the term Λ will be a constant and the bound scales logarithmically with p. If one considers the eigen-gap αt decays as training proceed, e.g., αt = 1t1/4 for t > 0, then we have Λ = O( √ T ). In this case, with T = n2 2, PDP-SGD requires the public data size m = O(n ).

heading: 4 EXPERIMENTS
text: We empirically evaluate PDP-SGD on training neural networks with two datasets: the MNIST (LeCun et al., 1998) and Fashion MNIST (Xiao et al., 2017). We compare the performance of PDPSGD 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 Rk×p Gaussian random 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 experimental setup. More details and additional results are in Appendix D.
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 to construct the public dataset. Note that the smaller private datasets make the private learning problem more challenging. For both datasets, we use a convolutional neural network that follows the structure in Papernot et al. (2020).
Training and Hyper-parameter Setting. 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 and step size used for DP-SGD, PDP-SGD and RPDP-SGD listed in Appendix D. For training, a 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, we use Lanczos algorithm to compute the top k eigen-space of the gradient second moment martix on public dataset. We use k = 50 for MNIST and k = 70 for Fashion MNIST. For RPDP-SGD, we use k = 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-SGD perform better when starting projection from the 15-th epoch.
Privacy Parameter Setting: We consider different choices of the noise scale, i.e., σ = {18, 14, 10, 8, 6, 4} for MNIST and σ = {18, 14, 10, 6, 4, 2} for Fashion MNIST. Since gradient
norm bound G is unknow for deep learning, we follow the gradient clipping method in Abadi et al. (2016) to guarantee the privacy. We choose gradient clip size to be 1.0 for both datasets. We follow the Moment Accountant (MA) method (Abadi et al., 2016; Bu et al., 2019) to calculate 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 σ ∈ {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 σ ∈ {4, 6, 8, 10, 14, 18}. Note that presented in this paper is w.r.t. a subset i.e., 10, 000 samples from MNIST and Fashion MNIST.
Experimental Results. The training accuracy and test accuracy for different , are reported in Figure 3. For small regime, i.e., ≤ 0.42 with MNIST (Figure 3 (a)) and ≤ 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 error from the injected noise. For most choices of , RPDP-SGD fails to 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 et al. (2020) even with a subset from MNIST (Figure 3 (a)). We acknowledge that Papernot et al. (2020) report the test accuracy as a training dynamic in terms of privacy loss . Figure 4 provides two examples of the training dynamics, i.e., MNIST with = 0.23 and Fashion MNIST with = 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 k and pubic sample size m. Figure 5(a) and Figure 5(b) present the training and test accuracy for PDP-SGD with k ∈ {10, 20, 30, 50} and PDP-SGD with m ∈ {50, 100, 150} for = 0.23 for MNIST dataset. Among the choices of k, PDP-SGD with k = 50 achieves the best accuracy. DP-SGD with k = 10 proceeds slower than the rest, due to the larger reconstruction error introduced by projecting the gradient to a much smaller subspace, i..e, k = 10. However, compared to the gradient dimension p ≈ 25, 000, it is impressive that PDP-SGD with k = 50 can achieve better accuracy than DP-SGD for a certain range of . Figure 5(b) shows
that the accuracy of PDP-SGD improves as the m increases from 50 to 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 a 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 PDPSGD with sparse eigen-space computation, i.e., update the projector every s iterates. Note that PDP-SGD with s = 1 means computing the top eigen-space at every iteration. Figure 6 reports PDP-SGD with s = {1, 10, 20} for (a) MNIST and (b) Fashion MNIST showing that PDP-SGD with a reduced eigen-space computation also outperforms DP-SGD, even though there is a mild decay for PDP-SGD with fewer eigen-space computations.

heading: 5 CONCLUSION
text: While DP-SGD and variants have been well studied for private ERM, the error rate of DP-SGD depends on the ambient dimension p. In this paper, we aim to bypass such dependence by leveraging 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 a public dataset. We show theoretically that PDP-SGD can obtain (near) dimension-independent error rate. We evaluate the proposed algorithms on two popular deep learning tasks and demonstrate the empirical advantages of PDP-SGD.

heading: ACKNOWLEDGEMENT
text: The research was supported by NSF grants IIS-1908104, OAC-1934634, IIS-1563950, a Google Faculty Research Award, a J.P. Morgan Faculty Award, and a Mozilla research grant. We would like to thank the Minnesota Super-computing Institute (MSI) for providing computational resources and support.

heading: A UNIFORM CONVERGENCE FOR SUBSPACES: PROOFS FOR SECTION 3.1
text: In this section, we provide the proofs for Section 3.1. We first show that the second moment matrix Mt converges to the population second moment matrix Σt uniform over all iterations t ∈ [T ], i.e., supt∈[T ] ‖Mt−Σt‖. Then we show that the top-k subspace of Mt uniformly converges to the top-k subspace of Σt, i.e., ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖ for all t ∈ [T ]. Our bound depends on γ2(W, d) whereW is the set of all possible parameters along the training trajectory. In Section A.2, we show that the bound can be derived by γ2(M, d) as well, where M is the set of population gradients along the training trajectory. Then, we provide examples of the setM and corresponding value of γ2(M, d).
A.1 UNIFORM CONVERGENCE BOUND
Our proofs of Theorem 2 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 Definition 2). Talagrand (2014) shows that for a process (Xt)t∈T and a given metric space (T, d), if (Xt)t∈T satisfies the increment condition
∀u > 0,P (|Xs −Xt| ≥ u) ≤ 2 exp ( − u 2
2d(s, t)2
) , (5)
then the size of the process can be bounded as
E sup t∈T Xt ≤ cγ2(T, d), (6)
with c to be an absolute constant.
To apply the GC result to establish the Theorem 2, we treat ‖Mt − Σt‖2 as the process Xt over the iterations. In detail, since Mt = 1m ∑m i=1∇` (wt, z̃i)∇` (wt, z̃i) ᵀ , and Σt = Ez∼P [∇` (wt, z)∇` (wt, z)ᵀ], the ‖Mt − Σt‖2 is a random process indexed by wt ∈ W , with W to be the set of all possible iterates obtained by the algorithm. We first show that the variable ‖Mt − Σt‖2 satisfies the increment condition as stated in equation 5 in Lemma 1. Before we present the proof of Lemma 1, we introduce the Ahlswede-Winter Inequality (Horn and Johnson, 2012; Wainwright, 2019), which will be used in the proof of Lemma 1. Ahlswede-Winter Inequality shows that positive semi-definite random matrix with bounded spectral norm concentrates to its expectation with high probability.
Theorem 5 (Ahlswede-Winter Inequality) Let Y be a random, symmetric, positive semi-definite p × p matrix. such that such that ‖E[Y ]‖ ≤ 1. Suppose ‖Y ‖ ≤ R for some fixed scalar R ≥ 1. Let {Y1, . . . , Ym} be independent copies of Y (i.e., independently sampled matrices with the same distribution as Y ). For any u ∈ [0, 1], we have
P (∥∥∥∥∥ 1m m∑ i=1 Yi − E [Yi] ∥∥∥∥∥ 2 > u ) ≤ 2p · exp ( −mu2/4R ) . (7)
To make the argument clear, we use a more informative notation for Mt and Σt. Recall the notation of Mt and Σt such that
Mt = 1
m m∑ i=1 ∇` (wt, z̃i)∇` (wt, z̃i)ᵀ , (8)
and Σt = Ez∼P [∇` (wt, z)∇` (wt, z)ᵀ] , (9)
given the dataset Sh = {z̃1, .., z̃m} and distribution P where z̃i ∼ P for i ∈ [m], the Mt and Σt are functions of parameter wt, so we use M(wt) and Σ(wt) for Mt and Σt interchangeably in the rest of this section, i..e,
M(w) = 1
m m∑ i=1 ∇` (w, z̃i)∇` (w, z̃i)ᵀ (10)
and Σ(w) = Ez∼P [∇` (w, z)∇` (w, z)ᵀ] . (11)
Lemma 1 With Assumption 2 and 1 hold, for any w,w′ ∈ W and ∀u > 0, we have
P ( ‖M(w)− Σ(w)‖2 − ‖M(w
′)− Σ(w′)‖2 ≥ u√ m · 4Gρd(w,w′)
) ≤ 2p · exp ( −u2/4 ) ,
(12)
where d :W ×W 7→ R is the pseudo-metric in Assumption 2.
Proof: We consider random variable
Xi = ∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ + 2Gρd(w,w′)Ip, (13)
where Ip ∈ Rp×p is the identity matrix. Note that 2Gρd(w,w′) is deterministic and the randomness of Xi comes from ∇`(w, z̃i) and ∇`(w′, z̃i). By triangle inequality and the construction of Xi, we have
‖M(w)− Σ(w)‖2 − ‖M(w ′)− Σ(w′)‖2 = ‖M(w)− E[M(w)]‖2 − ‖M(w ′)− E[M(w′)]‖2 ≤ ‖M(w)− E[M(w)]− (M(w′)− E[M(w′)])‖2 = ‖M(w)−M(w′)− E[(M(w)−M(w′))]‖2
= ∥∥∥∥∥ 1m m∑ i=1 (∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ)− E [∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ] ∥∥∥∥∥ 2
= ∥∥∥∥ 1m m∑ i=1 (∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ + 2Gρd(w,w′)Ip)
− E [∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ + 2Gρd(w,w′)Ip] ∥∥∥∥
2
= ∥∥∥∥ 1m∑Xi − E[Xi] ∥∥∥∥
2
(14)
To apply Theorem 5 for ∥∥ 1 m ∑ Xi − E[Xi] ∥∥ 2 , we first show that the random symmetric matrix Xi is positive semi-definite.
By Assumption 1 and Assumption 2 and definition
‖∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ‖2 = sup
x:‖x‖=1 xᵀ (∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ)x
= sup x:‖x‖=1
xᵀ∇`(w, z̃i)∇`(w, z̃i)ᵀx− xᵀ∇`(w′, z̃i)∇`(w′, z̃i)ᵀx
= sup x:‖x‖=1
〈x,∇`(w, z̃i)〉2 − 〈x,∇`(w′, z̃i)〉2
= sup x:‖x‖=1
(〈x,∇`(w, z̃i)〉+ 〈x,∇`(w′, z̃i)〉) (〈x,∇`(w, z̃i)〉 − 〈x,∇`(w′, z̃i)〉)
≤ sup x:‖x‖=1 2G (〈x,∇`(w, z̃i)〉 − 〈x,∇`(w′, z̃i)〉)
= 2G‖∇`(w, z̃i)−∇`(w′, z̃i)‖2 ≤ 2Gρd(w,w′) (15)
For any non-zero vector x ∈ Rp, we have
xᵀXix = x ᵀ (∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ + 2Gρd(w,w′)Ip)x
= xᵀ (∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ)x + 2Gρd(w,w′)‖x‖22 ≥ −‖∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ‖2 ‖x‖ 2 2 + 2Gρd(w,w
′)‖x‖22 = (2Gρd(w,w′)− ‖∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ‖2) ‖x‖ 2 2
(a) ≥ 0, (16)
where (a) is true because ‖∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ‖2 ≤ 2Gρd(w,w′) as shown in equation 15.
Let Yi = Xi4Gρd(w,w′) , with equation 15, we have
‖Yi‖2 = ‖∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ + 2Gρd(w,w′)Ip‖2
4Gρd(w,w′)
≤ ‖∇`(w, z̃i)∇`(w, z̃i)ᵀ −∇`(w′, z̃i)∇`(w′, z̃i)ᵀ‖2 + ‖2Gρd(w,w′)Ip‖2
4Gρd(w,w′)
≤ 2Gρd(w,w ′) + 2Gρd(w,w′)
4Gρd(w,w′)
= 1. (17)
So that ‖Yi‖2 ≤ 1 and ‖E[Yi]‖2 ≤ 1. Then, from Theorem 5, withR = 1, we have for any u ∈ [0, 1]
P (∥∥∥∥∥ 1m m∑ i=1 Yi − E [Yi] ∥∥∥∥∥ > u ) ≤ 2p · exp ( −mu2/4 ) . (18)
Note that ∥∥ 1 m ∑m i=1 Yi − E [Yi] ∥∥ is always bounded by 1 since ‖Yi‖2 ≤ 1 and ‖E[Yi]‖2 ≤ 1. So the above inequality holds for any u > 1 with probability 0 which is bounded by 2p · exp ( −mu2/4 ) . So that we have for any u > 0,
P (∥∥∥∥∥ 1m m∑ i=1 Yi − E [Yi] ∥∥∥∥∥ > u ) ≤ 2p · exp ( −mu2/4 ) . (19)
So that for any u > 0,
P (∥∥∥∥∥ 1m m∑ i=1 Xi − E [Xi] ∥∥∥∥∥ > u√m · 4Gρd(w,w′) ) ≤ 2p · exp ( −u2/4 ) . (20)
Combine equation 20 and equation 14, we have P ( ‖M(w)− Σ(w)‖2 − ‖M(w
′)− Σ(w′)‖2 ≥ u√ m · 4Gρd(w,w′) ) = P ( ‖M(w)− E[M(w)]‖2 − ‖M(w
′)− E[M(w′)]‖2 > u√ m · 4Gρd(w,w′) ) ≤ P
(∥∥∥∥∥ 1m m∑ i=1 Xi − E [Xi] ∥∥∥∥∥ > u√m · 4Gρd(w,w′) )
≤ 2p · exp ( −u2/4 ) (21)
That completes the proof.
Based on the above result, now we come to the proof of Theorem 2. The proof follows the Generic Chaining argument, i.e., Chapter 2 of Talagrand (2014).
Theorem 2 (Second Moment Concentration) Under Assumption 1, 2, the second moment matrix of the public gradient Mt = 1m ∑m i=1∇`(wt, z̃i)∇`(wt, z̃i)ᵀ approximates the population second moment matrix Σt = Ez∼P [∇`(wt, z)∇`(wt, z)ᵀ] uniformly over all iterations, i.e., for any u > 0,
sup t∈[T ]
‖Mt − Σt‖2 ≤ O ( uGρ √ ln pγ2(W, d)√ m ) , (1)
with probability at least 1− c exp ( −u2/4 ) , where c is an absolute constant.
Proof: Note that equation equation 1 is a uniform bound over iteration t ∈ [T ]. To bound supt∈[T ] ‖Mt − Σt‖2, it is sufficient to bound
sup w∈W ‖M(w)− Σ(w)‖2 , (22)
whereW contains all the possible trajectorys of w1, ...,wT . We consider a sequence of subsetsWn ofW , and
cardWn ≤ Nn, (23)
where N0 = 1;Nn = 22 n
if n ≥ 1. Let πn(w) ∈ Wn be the approximation of any w ∈ W . We decompose the ‖M(w)− Σ(w)‖2 as
‖M(w)− Σ(w)‖2 − ‖M(π0(w))− Σ(π0(w))‖2 = ∑ n≥1 (‖M(πn(w))− Σ(πn(w))‖2 − ‖M(πn−1(w))− Σ(πn−1(w))‖2) , (24)
which holds since πn(w) = w for n large enough.
Based on Lemma 1, for any u > 0, we have
‖M(πn(w))− Σ(πn(w))‖2 − ‖M(πn−1(w))− Σ(πn−1(w))‖2 ≥ u√ m · 4Gρd(πn(w), πn−1(w)),
(25)
with probability at most 2p exp(−u 2
4 ).
For any n > 0 and w ∈ W , the number of possible pairs (πn(w), πn−1(w)) is
cardWn · cardWn−1 ≤ NnNn−1 ≤ Nn+1 = 22 n+1 . (26)
Apply union bound over all the possible pairs of (πn(w), πn−1(w)), following Talagrand (2014) (Chapter 2.2), for any n > 0, u > 0, and w ∈ W , we have
‖M(πn(w))− Σ(πn(w))‖2−‖M(πn−1(w))−Σ(πn−1(w))‖2 ≥ u2 n/2d(πn(w), πn−1(w))· 4Gρ√ m (27) with probability ∑
n≥1
2p · 22 n+1 exp ( −u22n−2 ) ≤ c′p exp ( −u 2
4
) , (28)
where c′ is a universal constant.
Then we have∑ n≥1 (‖M(πn(w))− Σ(πn(w))‖2 − ‖M(πn−1(w))− Σ(πn−1(w))‖2)
≥ ∑ n≥1 u2n/2d(πn(w), πn−1(w)) · 4Gρ√ m
≥ ∑ n≥0 u2n/2d(w,Wn) · 4Gρ√ m
(29)
with probability at most c′p exp ( −u 2
4
) .
From Theorem 5, let Yi = ∇`(π0(w),z̃i)∇`(π0(w),z̃i)ᵀ
G , so that ‖Yi‖ ≤ 1 and ‖E[Yi]‖ ≤ 1. Then we have
‖M(π0(w))− Σ(π0(w))‖2 ≥ u G√ m , (30)
with ptobability at most 2p exp ( −u 2
4
) .
Combine equation 24, equation 29 and equation 30, we have
sup w∈W ‖M(w)− Σ(w)‖2 ≥ sup w∈W ∑ n≥0 u2n/2d(w,Wn) · 4Gρ√ m + u G√ m
= u ( G (4ργ2(W, d) + 1)√
m
) (31)
with probability at most (c′ + 2)p exp ( −u 2
4
) .
That completes the proof.
Now we provide the proof of Theorem 3.
Theorem 3 (Subspace Closeness) Under Assumption 1 and 2, with Vk(t) to be the top-k eigenvectors of the population second moment matrix Σt and αt be the eigen-gap at t-th iterate such that λk (Σt)− λk+1 (Σt) ≥ αt, for the V̂k(t) in Algorithm 1, if m ≥ O(Gρ √ ln pγ2(W,d)) 2
mint α2t , we have
E [ ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖2 ] ≤ O ( Gρ √
ln pγ2(W, d) αt √ m
) ,∀t ∈ [T ]. (2)
Proof: Recall that V̂k(t) is the top-k eigenspace of Mt. Let Vk(t) be the top-k eigenspace of Σt.
V̂k(t)V̂k(t) ᵀ − Vk(t)Vk(t)ᵀ = Π(k)Mt(I−Π (k) Σt ) + (I−Π(k)Mt)Π (k) Σt
(32)
⇒ ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖2 ≤ ‖Π(k)Mt(I−Π (k) Σt )‖2 + ‖(I−Π(k)Mt)Π (k) Σt ‖2 . (33)
where Π(k)Mt = V̂k(t)V̂k(t) ᵀ denotes the projection to the top-k subspace of the symmetric PSD Mt and Π(k)Σt = Vk(t)Vk(t) ᵀ denotes the projection to the top-k subspace of the symmetric PSD Σt. Then, from Davis-Kahan (Corollary 8 in McSherry (2004)) and using the fact for symmetric PSD matrices eigen-values and singular values are the same, we have
‖Π(k)Mt(I−Π (k) Σt )‖2 ≤ ‖Mt − Σt‖2
λk(Mt)− λk+1(Σt) (34)
‖(I−Π(k)Mt)Π (k) Σt ‖2 ≤ ‖Mt − Σt‖2 λk(Σt)− λk+1(Mt) . (35)
Recall, from Horn and Johnson (2012) (Section 4.3) and Golub and Van Loan (1996) (Section 8.1.2), e.g., Corollary 8.1.6, we have
|λk(Mt)− λk(Σt)| ≤ ‖Mt − Σt‖2 . (36)
From Theorem 2 and Lemma 2, with Y = ‖Mt−Σt‖2, A = c, and B = 4Gρ √ ln pγ2(W,d)√ m , we have
E [‖Mt − Σt‖2] ≤ O ( Gρ √
ln pγ2(W, d)√ m
) . (37)
Let c0 = O ( Gρ √ ln pγ2(W, d) ) . For m ≥ c 2 0
α2t , we have
E [‖Mt − Σt‖2] ≤ c0√ m ≤ αt 2 . (38)
Then, for equation 34, we have
‖Π(k)Mt(I−Π (k) Σt )‖2 ≤ ‖Mt − Σt‖2
λk(Mt)− λk+1(Σt)
= ‖Mt − Σt‖2
(λk(Σt)− λk+1(Σt))− (λk(Σt)− λk(Mt))
≤ ‖Mt − Σt‖2 αt − ‖Mt − Σt‖2 . (39)
Then, for equation 35, we have
‖(I−Π(k)Mt)Π (k) Σt ‖2 ≤ ‖Mt − Σt‖2 λk(Σt)− λk+1(Mt)
= ‖Mt − Σt‖2
(λk(Σt)− λk+1(Σt)) + (λk+1(Σt)− λk+1(Mt))
≤ ‖Mt − Σt‖2 αt − ‖Mt − Σt‖2 . (40)
Combining these two bounds and equation 37, with c0 = O ( Gρ √ ln pγ2(W, d) ) , we have
E [ ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖2 ] ≤ 2αt αt − E [‖Mt − Σt‖2] − 2
≤ 2c0√ m
αt − c0√m (41)
Using equation 38 such that c0√ m ≤ αt2 , we have
E [ ‖V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ‖2 ] ≤ O ( Gρ √
ln pγ2(W, d) αt √ m
) . (42)
That completes the proof.
Lemma 2 (Lemma 2.2.3 in Talagrand (2014)) Consider a r.v. Y ≥ 0 which satisfies ∀u > 0,P(Y ≥ u) ≤ A exp ( − u 2
B2
) (43)
for certain numbers A ≥ 2 and B > 0. Then EY ≤ CB √ logA, (44)
where C denotes a universal constant.
A.2 GEOMETRY OF GRADIENTS AND γ2 FUNCTIONS.
In this section, we provide more intuitions and explanations of γ2 functions. We justify our assumptions about the gradient space and provide more examples of the gradient space structure and the corresponding γ2 functions.
At a high level, for a metric space (M,d), γ2(M,d) is related to √
logN(M,d, ) whereN(M,d, ) is the covering number ofM with balls with metric d, but it is considerably sharper. Such sharpening has happened in 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 considers 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 γ2(M,d) as an upper (and lower) bound on suprema of Gaussian processes indexed on M and with metric d [Theorem 2.4.1 in Talagrand (2014)].
Considering d to be the `2 norm distance, γ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., a L1 unit ball in Rp has a Gaussian width of O( √ log p, wheras a L2 unit ball in Rp has a Gaussian width of O( √ p).
To utilize the structure of gradients as example shown in Figure 2, instead of focusing on the γ2(W, d), we can also derive the uniform convergence bound using the measurement d on the set of population gradient m = Ez∈P [∇(w, z)]. We consider a mapping f : W 7→ M from the parameter space W to the gradient space M, where f can be considered as f(w) = Ez∈P [∇(w, z)]. With mt = Ez∈P [∇(w, z)] and M to be the space of the population gradient mt ∈ M, the pseudo metric d(w,w′) can be written as d(w,w′) = d(f(w), f(w′)) = d(m,m′) with m = Ez∈P [∇(w, z)] and m′ = Ez∈P [∇(w′, z)]. With such a mapping f , the admissible sequence ΓW = {Wn : n ≥ 0} of W in the proof of Theorem 2 corresponds to the admissible sequence ΓM = {Mn : n ≥ 0} ofM. The γ2(W, d) = infΓW supw∈W ∑ n≥0 2
n/2d (w,Wn) = infΓM supm∈M ∑ n≥0 2
n/2d (m,Mn) = γ2(M, d). Considering d(m,m′) = ‖m −m′‖2, the γ2(M, d) will be the same order as the Gaussian width ofM, i.e., w(M) = Ev [supm∈M〈m,v〉], where v ∼ N (0, 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 m. In Figure 2, we observe that, for each coordinates of the gradient is of small value along the training trajectory and thusM includes all gradients living in an ellipsoid, i.e.,M = {mt ∈ Rp | ∑p j=1 mt(j)
2/e(j)2 ≤ 1, e ∈ Rp}. Then we have γ2(M, d) ≤ c1w(M) ≤ c2‖e‖2 Talagrand (2014), where c1 and c2 are absolute constants. If the elements of e sorted in decreasing order satisfy e(j) ≤ c3/ √ j for all
j ∈ [p], then γ2(M, d) ≤ O (√ log p ) .
Composition. Based on the composition properties of γ2 functions Talagrand (2014), one can construct additional examples of the gradient spaces. If M = M1 + M2 = {m1 + m2,m1 ∈ M1,m2 ∈ M2}, the Minkowski sum, then γ2(M, d) ≤ c(γ2(M1, d) + γ2(M2, d)) (Theorem 2.4.15 in Talagrand (2014)), where c is an absolute constant. If M is a union of several subset, i.e., M = ∪Dh=1Mh, then by using an union bound on Theorem 2, we have γ2(M, d) ≤√
logDmaxh γ2(Mh, d). Thus, ifM is an union of D = ps ellipsoids, i.e., polynomial in p, then γ2(M, ‖ · ‖2) ≤ O ( √ s log p).

heading: B PROOFS FOR SECTION 3.2
text: 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 4 (Smooth and Non-convex) For ρ-smooth function L̂n(w), under Assumptions 1 and 2, let Λ = ∑T t=1 1/α 2 t
T , for any , δ > 0, with T = O(n 2 2) and ηt = 1√T , PDP-SGD achieves:
1
T T∑ t=1 E‖Vk(t)Vk(t)ᵀ∇L̂n(wt)‖22 ≤ Õ ( kρG2 n ) +O ( ΛG4ρ2γ22(W, d) ln p m ) . (3)
Additionally, assuming the principal component of the gradient dominates, i.e., there exist c > 0, such that 1T ∑T t=1 ‖[∇L̂n(wt)]⊥‖22 ≤ c 1 T ∑T t=1 ‖[∇L̂n(wt)]‖‖22, we have
E‖∇L̂n(wR)‖22 ≤ Õ ( kρG2
n
) +O ( ΛG4ρ2γ22(W, d) ln p
m
) , (4)
where wR is uniformly sampled from {w1, ...,wT }. Proof: Recall that gt = 1|Bt| ∑ zi∈Bt ∇`(wt, zi). With Bt uniformly sampled from S, we have
Et[gt] = ∇L̂n(wt). (45)
Recall that the update of Algorithm 1 is
g̃t = V̂kV̂ ᵀ k (gt + bt) , and wt+1 = wt − ηtg̃t. (46)
Let ḡt = gt + V̂kV̂ ᵀ k bt, and ∆t = V̂kV̂ ᵀ k gt − gt. Then we have
g̃t = ḡt + ∆t. (47)
Since bt is a zero mean Gaussian vector, we have
Et[ḡt] = gt. (48)
For ρ-smooth 5 function L̂n(w), conditioned on wt, we have Et [ L̂n (wt+1) ] ≤ L̂n (wt) + Et [〈 ∇L̂n(wt),wt+1 −wt 〉] + ρ
2 η2tEt
[ ‖g̃t‖22 ] = L̂n (wt)− ηtEt [〈 ∇L̂n(wt), ḡt + ∆t 〉] + ρ
2 η2tEt
[ ‖g̃t‖22 ] = L̂n (wt)− ηt 〈 ∇L̂n(wt),∇L̂n(wt) + Et[∆t] 〉 + ρ
2 η2tEt
[ ‖g̃t‖22 ] = L̂n (wt)− ηt ∥∥∥∇L̂n(wt)∥∥∥2 2 − ηt 〈 ∇L̂n(wt),Et[∆t] 〉 + ρ 2 η2tEt [ ‖g̃t‖22 ] (49)
Rearrange the above inequality, we have
ηt ∥∥∥∇L̂n(wt)∥∥∥2 2 + ηt Et 〈 ∇L̂n(wt),∆t 〉 ︸ ︷︷ ︸
Dt,1
≤ L̂n (wt)− Et [ L̂n (wt+1) ] + ρ
2 η2t Et
[ ‖g̃t‖22 ] ︸ ︷︷ ︸
Dt,2
(50)
For Dt,1, let
∇L̂n(wt) = ΠQt [∇L̂n(wt)] + ΠQ⊥t [∇L̂n(wt)] (51)
where Qt is V̂k(t)V̂k(t)ᵀ and ΠQt is the projection. Q ⊥ t is the null space of Qt.
ΠQt [∇L̂n(wt)] = V̂k(t)V̂k(t)ᵀ∇L̂n(wt) (52) and
ΠQ⊥t [∇L̂n(wt)] = [ I− V̂k(t)V̂k(t)ᵀ ] ∇L̂n(wt). (53)
We have
∆t = ΠQt [V̂k(t)V̂k(t) ᵀgt − gt] + ΠQ⊥t [V̂k(t)V̂k(t) ᵀgt − gt] = −ΠQ⊥t [gt]. (54)
So that we have Dt,1 = Et 〈 ∇L̂n(wt),∆t 〉 = −Et 〈 ΠQt [∇L̂n(wt)] + ΠQ⊥t [∇L̂n(wt)], ΠQ⊥t [gt]
〉 = −Et 〈 ΠQ⊥t [∇L̂n(wt)], [ I− V̂k(t)V̂k(t)ᵀ ] gt
〉 = − 〈[ I− V̂k(t)V̂k(t)ᵀ ] ∇L̂n(wt), [ I− V̂k(t)V̂k(t)ᵀ ] ∇L̂n(wt)
〉 = −∇L̂n(wt)ᵀ [ I− V̂k(t)V̂k(t)ᵀ ] ∇L̂n(wt) . (55)
Bringing the above to equation 50, the right-hand side of equation 50 becomes ηt‖∇L̂n(wt)‖22 + ηtDt,1 = ηt∇L̂n(wt)ᵀ [I]∇L̂n(wt)− ηt∇L̂n(wt)ᵀ [ I− V̂k(t)V̂k(t)ᵀ ] ∇L̂n(wt)
= ηt∇L̂n(wt)ᵀ [ V̂k(t)V̂k(t) ᵀ ] ∇L̂n(wt)
= ηt‖V̂k(t)V̂k(t)ᵀ∇L̂n(wt)‖22 . (56) 5The Assumption 2 suggests that the L̂n(w) is ρ-smooth.
So that we have ηt‖V̂k(t)V̂k(t)ᵀ∇L̂n(wt)‖22 ≤ L̂n (wt)− Et [ L̂n (wt+1) ] + ρ
2 η2t Et
[ ‖g̃t‖22 ] ︸ ︷︷ ︸
Dt,2
. (57)
For Dt,2, we have
Et ‖g̃t‖22 = Et [∥∥∥V̂kV̂ Tk gt + V̂kV̂ Tk bt∥∥∥2
2 ] = Et [∥∥∥V̂kV̂ Tk gt∥∥∥2 2 + ∥∥∥V̂kV̂ Tk bt∥∥∥2 2
] ≤ G2 + kσ2. (58)
Thus, Dt,2 = Et [ ‖ḡt‖22 + ‖∆t‖22 ] ≤ G2 + kσ2. (59) Bringing the upper bound ofDt,2 to equation 57, setting ηt = 1√T , using telescoping sum and taking the expectation over all iterations, we have
1
T T∑ t=1 E‖V̂k(t)V̂k(t)ᵀ∇L̂n(wt)‖22 ≤ L̂n(w1)− L̂?n√ T + ρ(G2 + kσ2) 2 √ T
(60)
With triangle inequality and Theorem 3, we have∥∥∥Vk(t)Vk(t)ᵀ∇L̂n (wt)∥∥∥2 2 ≤ 2 ∥∥∥V̂k(t)V̂k(t)ᵀ∇L̂n (wt)∥∥∥2 2 + 2 ∥∥∥(Vk(t)Vk(t)ᵀ − V̂k(t)V̂k(t)ᵀ)∇L̂n (wt)∥∥∥2 2
≤ 2 ∥∥∥V̂k(t)V̂k(t)ᵀ∇L̂n (wt)∥∥∥2
2 +O
( G4ρ2 ln pγ22(W, d)
α2tm
) . (61)
With equation 60, we have
1
T T∑ t=1 E‖Vk(t)Vk(t)ᵀ∇L̂n(wt)‖22 ≤ L̂n(w1)− L̂?n√ T/2 + ρ(G2 + kσ2)√ T +O ( ΛG4Lρ2γ22(W, d) ln p m ) .
(62) where Λ = ∑T t=1
1 α2t .
Let [ ∇L̂n(wt) ]‖ = Vk(t)Vk(t) ᵀ∇L̂n(wt) and [ ∇L̂n(wt) ]⊥ = ∇L̂n(wt) −
Vk(t)Vk(t) ᵀ∇L̂n(wt).
Assuming there exist c > 0, we have T∑ t=1 E ∥∥∥∥[∇L̂n(wt)]⊥∥∥∥∥2 2 ≤ c T∑ t=1 E ∥∥∥∥[∇L̂n(wt)]‖∥∥∥∥2 2 . (63)
Then we have
1
T T∑ t=1 E‖∇L̂n(wt)‖22 ≤ (1 + c)
( L̂n(w1)− L̂?n√
T/2 + ρ(G2 + kσ2)√ T +O
( ΛG4Lρ2γ22(W, d) ln p
m
)) .
(64)
Take T = n2 2, with E [ ‖∇L̂n(wR)‖22 ] = 1T ∑T t=1 E‖∇L̂n(wt)‖22, we have
E‖∇L̂n(wR)‖22 ≤ Õ ( kρG2
n
) +O ( ΛG4ρ2γ22(W, d) ln p
m
) , (65)
where wR is uniformly sampled from {w1, ...,wT }.

heading: C ERROR RATE OF CONVEX PROBLEMS
text: For the convex and Lipschitz functions, we consider the low-rank structure of the gradient space, i.e, the population gradient second momment Σt is of rank-k, which is a special case of the principal gradient dominate assumption when |[∇L̂n(wt)]⊥‖2 = 0.
Theorem 6 (Convex and Lipschitz) For G-Lipschitz and convex function L̂n(w), under Assumptions 1,2 and assuming Σt is of rank-k, let Λ = ∑T t=1 1/αt T , for any , δ > 0, with T = O(n
2 2), step size ηt = 1√T , the PDP-SGD achieves
E [ L̂n(w̄) ] − L̂n(w?) ≤ O ( kG2
n
) +O ( ΛGργ2(W, d) ln p√
m
) , (66)
where w̄ = ∑T t=1 wt T , and w ? is the minima of L̂n(w).
PDP-SGD also demonstrates an improvement from a factor of p to k 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 Λ = ∑T t=1 1/αt/T . From previous discussions, the γ2 is a constant with suitable assumptions of the gradient structure. For the eigen-gap term, if αt stays as a constant in the training procedure as shown by Figure 1, Λ will be a constant and the bound scales logarithmically with p. If one assumes the eigen-gap αt decays as training proceed, e.g., αt = 1t1/2 for t > 0, then we have Λ = O( √ T ). In this case, with T = O(n2 2), PDP-SGD requires public data size m = O(n ).
Recently, Kairouz et al. (2020) propose a noisy version of AdaGrad algorithm for unconstrained convex empirical risk minimization. Their algorithm operates with only private data and also achieves a dimension-free excess risk bound, i.e., Õ(r/n ), by assuming the gradients along the path of optimization lie in a low-dimensional subspace with constant rank r. The bounds are not directly comparable since the assumptions in Kairouz et al. (2020) are different from those in this paper, i.e., Kairouz et al. (2020) assume that the accumulated gradients along the training process lie in a constant subspace which requires the rank of the gradient space does not explode when adding more stochastic gradients. Our work does not impose such a constant subspace assumption on Σt allowing the subspace of Σt to be different along the training process. In other words, our bounds hold even when the rank of the accumulated stochastic gradients space increases as training proceeds.
Proof of Theorem 6: By the convexity of L̂n(w), we have
L̂n(wt)− L̂n(w?) ≤ 〈wt −w?,∇L̂n(wt)〉. (67)
At iteration t, we have wt+1 = wt − ηtg̃t, where g̃t = V̂kV̂ ᵀk gt + V̂kV̂ ᵀ k bt.
Let ḡt = gt + V̂kV̂ ᵀ k bt, and ∆t = V̂kV̂ ᵀ k gt − gt. Then we have
g̃t = ḡt + ∆t. (68)
Recall that gt = 1|Bt| ∑ zi∈Bt ∇`(wt, zi). With Bt uniformly sampled from S, we have
Et[gt] = ∇L̂n(wt). (69)
Since bt is a zero mean Gaussian vector, we have Et[ḡt] = gt.
By convexity, conditioned at wt, we have
Et[L̂n(wt)− L̂n(w?)] ≤ Et〈wt −w?,gt〉 = Et〈wt −w?, ḡt〉
= 1
ηt Et〈wt −w?,wt −wt+1 − ηt∆t〉
= 1 2ηt Et ( ‖wt −w?‖22 + η2t ‖ḡt‖22 − ‖wt+1 −w? − ηt∆t‖22 ) = 1
2ηt Et ( ‖wt −w?‖22 + η2t ‖ḡt‖22 − ‖wt+1 −w?‖22 − η2t ‖∆t‖22 + 2〈wt+1 −w?, ηt∆t〉 ) = 1
2ηt Et ( ‖wt −w?‖22 − ‖wt+1 −w?‖22 ) + ηt 2 Et[‖ḡt‖22]− ηt 2 Et[‖∆t‖22]
+ Et〈wt+1 −w?,∆t〉 (a) ≤ 1 2ηt Et ( ‖wt −w?‖22 − ‖wt+1 −w?‖22 ) + ηt 2 ( G2 + kσ2 ) +BEt‖∆t‖2, (70)
where (a) is true since
Et‖ḡt‖22 ≤ Et[‖gt‖22 + ‖V̂kV̂ ᵀ k bt‖ 2 2]
≤ G2 + kσ2, (71)
and ‖wt+1 −w?‖2 ≤ B 6. Let ηt = 1√T , taking the expectation over all iterations and sum over t = 1, .., T , we have
1 T E [∑T t=1 L̂n(wt)− L̂n(w?) ] ≤ ‖w0 −w ?‖22 +G2 + kσ2 2 √ T + B ∑ᵀ t=1 Et‖∆t‖2 T . (72)
From Theorem 3, we have
Et [‖∆t‖2] = E [∥∥∥V̂k(t)V̂k(t)ᵀgt − V (t)V (t)ᵀgt∥∥∥
2 ] ≤ E [∥∥∥V̂k(t)V̂k(t)ᵀ − V (t)V (t)ᵀ∥∥∥ 2 G ]
≤ GE [∥∥∥V̂k(t)V̂k(t)ᵀ − Vk(t)Vk(t)ᵀ∥∥∥
2 + ‖Vk(t)Vk(t)ᵀ − V (t)V (t)ᵀ‖2 ] ≤ O ( Gρ ln pγ2(W, d)
αt √ m
) , (73)
where the last inequality holds because the Σt is of rank k and V (t) = Vk(t).
Bring this to equation 72, use the fact that ‖w0 −w?‖ < B, with Jensen’s inequality we have
E [ L̂n(w̄) ] − L̂n(w?) ≤ B2 +G2 + kσ2
2 √ T
+O ( ΛGρ ln pγ2(W, d)√
m
) . (74)
where Λ = ∑ᵀ t=1 1 αt .
With σ2 = G 2T
n2 2 , let T = n 2 2, we have
E [ L̂n(w̄) ] − L̂n(w?) ≤ O ( kG2B2
n
) +O ( ΛGρ ln pγ2(W, d)√
m
) . (75)
That completes the proof.
6For convex problem, we consider w ∈ H, whereH = {w : ‖w‖ ≤ B}.

heading: D EXPERIMENTAL SETUP AND ADDITIONAL RESULTS
text: 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 dataset 7. Details refer to Table 2. For both MNIST and Fashion MNIST, we use a convolutional neural network that follows the structure in Papernot et al. (2020) whose architecture is described in Table 1. All experiments have been run on NVIDIA Tesla K40 GPUs.
Hyper-parameter Setting. We consider different choices of the noise scale, i.e., σ = {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 accuracy at the last epoch. The best step sizes for DP-SGD and PDP-SGD for different privacy levels are presented in Table 3 and Table 4 for MNIST and Fashion MNIST, respectively. For training, a 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 k is a hyper-parameter and it illustrates a trade-off between the reconstruction error and the noise reduction. A small k implies more noise amount will be reduced, and a larger reconstruction error will be introduced. We explored k = {20, 30, 50} for MNIST and k = {30, 50, 70} for Fashion MNIST, and we found that k = 50 and k = 70 achieve the best performance for MNIST and Fashion MNIST respectively among the search space we consider. 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-th epoch, 15-th epoch. The information of projection dimension k and the starting epoch for projection are also given in Table 3 and Table 4 for MNIST and Fashion MNIST, respectively.
Privacy Parameter Setting. Since gradient norm bound G is unknow for deep learning, we follow the gradient clipping method in Abadi et al. (2016) to guarantee the privacy. We implement the micro-batch clipping method in PyTorch 8. We use micro-batch = 1 and micro-batch = 5 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 = 1. We follow the Moment Accountant (MA) method (Bu et al., 2019) to calculate the accumulated privacy cost, which depends on the number of epochs, the batch size, δ, and noise variance σ. With 30 epochs, batch size 250,
7PDP-SGD can work with larger training set as well. We randomly sample 10,000 samples due to the limitation of computation resources, e.g., GPUs.
8We implement the clipping method based on this repository: https://github.com/ChrisWaites/pyvacy.
10, 000 training samples, and fixing δ = 10−5, the is {2.41, 1.09, 0.72, 0.42, 0.30, 0.23} for σ ∈ {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 σ = {4, 6, 8, 10, 14, 18}. Note that the presented in this paper is w.r.t. a subset i.e., 10, 000 samples from MNIST and Fashion MNIST. Also, one can fix the value of and do a search over the epochs, batch size and noise scale to boost the performance for a fixed privacy level . We omit such a complicated hyper-parameter tuning since it has a high risk of privacy leakage.
Additional Experimental Results. Training dynamics of DP-SGD and PDP-SGD with different privacy levels are presented in Figure 7 and Figure 8 respectively 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 9 reports the PDP-SGD with k ∈ {10, 20, 30, 50} for MNIST with = 0.30 (Figure 9(a)) and = 0.53 (Figure 9(b)). Among the choice of k, we can see that PDP-SGD with k = 50 performs better that the others in terms of the training and test accuracy. PDP-SGD with k = 10 proceeds slower than PDP-SGD with k = 20 and k = 50. This is due to the larger reconstruction error introduced by projecting the gradient to a much smaller subspace, i..e, k = 10. However, compared to the gradient dimension p ≈ 25, 000, it is impressive that PDP-SGD with k = 50 which projects the gradient to the a much smaller subspace, can achieve better accuracy than DP-SGD.
We also empirically evaluate the effect of the public sample size m. Figure 11(a) and Figure 11(b) present the training and test accuracy for PDP-SGD with m ∈ {50, 150, 200} for = 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 as 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 a 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.e., MNIST with 20,000 samples (Figure 12(a)) and Fashion MNIST with 50,000 samples (Figure 12(a)) (100
public samples for both case). The observation that PDP-SGD outperforms DP-SGD for small regime in Figure 3 also holds for other number of training samples.
We also explore PDP-SGD with sparse eigen-space computation, i.e., update the projector every s iterates. Note that PDP-SGD with s = 1 means computing the top eigen-space at every iteration. Figure 13 reports PDP-SGD with s = {1, 10, 20} for (a) MNIST with 50,000 samples and (b) 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.

Review summaries:
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$.

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.