Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification

Introduction

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:

We provide both theoretical analyses and empirical evaluations of PDP-SGD:

where $\gamma_{2}(\mathcal{W},d)$ is the complexity measure of the a set ${\cal W}$ considering metric $d$ (Definition 2). We provide low-complexity examples of ${\cal W}$ that are supported by empirical observations and show that their $\gamma_{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. For smooth and non-convex function, ignoring constants and certain other details, an informal version of the convergence rate is as follows:

where ${\mathbf{w}}_{R}$ is uniformly sampled from $\{{\mathbf{w}}_{1},...,{\mathbf{w}}_{T}\}$ and $m$ is the size of public dataset $S_{h}$. For Lipschitz convex funcntion, ignoring constants and certain other details, an informal version of the convergence rate is as follows:

where $\bar{\mathbf{w}}=\frac{\sum_{t=1}^{T}{\mathbf{w}}_{t}}{T}$, and ${\mathbf{w}}^{\star}$ is the minima of $\hat{L}_{n}({\mathbf{w}})$. Compared to the error rate of DP-SGD for convex functions (Bassily et al., 2014, 2019a) and non-convex and smooth functions (Wang and Xu, 2019). PDP-SGD demonstrates an improvement over the dependence on $p$ to $k$ in the error rate. The error rate of PDP-SGD also involves the subspace reconstruction error which depends on $\gamma_{2}$ function and size of public dataset. As discussed above, $\gamma_{2}$ function only scales logarithmically with $p$ supported by empirical observations and our rates only scale 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 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 known constant rank 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 $\gamma_{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.Note 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.

Preliminaries

We first state the standard definition of differential privacy which requires that no single private example has a significant influence on the algorithm’s output information.

A randomized algorithm $\mathcal{R}$ is $(\epsilon,\delta)$-differentially private if for any pair of datasets $D,D^{\prime}$ differ in exactly one data point and for all event $\mathcal{Y}\subseteq Range(\mathcal{R})$ in the output range of $\mathcal{R}$, we have $P\{\mathcal{R}(D)\in\mathcal{Y}\}\leq\exp(\epsilon)P\{\mathcal{R}(D^{\prime})\in\mathcal{Y}\}+\delta,$ where the probability is taken over the randomness of ${\cal R}$.

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 $\epsilon$ and $\delta$ 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.

Projected Private Gradient Descent

Under Assumption 1, there exist constants $c_{1}$ and $c_{2}$ so that given the number of iterations $T$, for any $\epsilon\leq c_{1}q^{2}T$, where $q=\frac{|B_{t}|}{n}$, PDP-SGD (Algorithm 1) is $(\epsilon,\delta)$-differentially private for any $\delta>0$, if $\sigma^{2}\geq c_{2}\frac{G^{2}T\ln\left(\frac{1}{\delta}\right)}{n^{2}\epsilon^{2}}$.

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 $\mathbf{g}_{t}+\mathbf{b}_{t}$. Then the privacy guarantee of releasing the sequence of $\{\mathbf{g}_{t}+\mathbf{b}_{t}\}_{t}$ is exactly the same as the privacy proof of Theorem 1 of Abadi et al. (2016).

However, this concentration bound does not hold for ${\mathbf{w}}_{t},\forall t>0$ in general, since the public dataset $S_{h}$ is reused over the iterations and the parameter ${\mathbf{w}}_{t}$ depends on $S_{h}$. To handle the dependency issue, we bound $\|M_{t}-\Sigma_{t}\|_{2}$ uniformly over all iterations $t\in[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 $\gamma_{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(\frac{\sqrt{T}}{\sqrt{m}})$ leading to a worse trade-off between the subspace construction error and optimization error due to the dependence on $T$.

For a metric space $({\cal A},d)$, an admissible sequence of ${\cal A}$ is a collection of subsets of ${\cal A}$, $\Gamma=\{{\cal A}_{n}:n\geq 0\}$, with $|{\cal A}_{0}|=1$ and $|{\cal A}_{n}|\leq 2^{2^{n}}$ for all $n\geq 1$, the $\gamma_{2}$ functional is defined by $\gamma_{2}({\cal A},d)=\inf_{\Gamma}\sup_{A\in{\cal A}}\sum_{n\geq 0}2^{n/2}d(A,{\cal A}_{n})~{},$ where the infimum is over all admissible sequences of ${\cal A}$.

with probability at least $1-c\exp\left(-u^{2}/4\right)$, where $c$ is an absolute constant.

Using the result in Theorem 2 and Davis-Kahan sin-$\theta$ theorem (McSherry, 2004), we obtain the subspace construction error $\|\hat{V}_{k}(t)\hat{V}_{k}(t)^{\intercal}-V_{k}(t)V_{k}(t)^{\intercal}\|_{2}$ in the following theorem.

Under Assumption 1 and 2, with $V_{k}(t)$ to be the top-$k$ eigenvectors of the population second moment matrix $\Sigma_{t}$ and $\alpha_{t}$ be the eigen-gap at $t$-th iterate such that $\lambda_{k}\left(\Sigma_{t}\right)-\lambda_{k+1}\left(\Sigma_{t}\right)\geq\alpha_{t}$, for the $\hat{V}_{k}(t)$ in Algorithm 1, if $m\geq\frac{O\left(G\rho\sqrt{\ln p}\gamma_{2}({\cal W},d)\right)^{2}}{\min_{t}{\alpha_{t}^{2}}}$, we have

Theorem 3 gives the sample complexity of the public sample size and the reconstruction error, i.e., the difference between $\hat{V}_{k}(t)\hat{V}_{k}(t)^{\intercal}$ evaluated on the public dataset $S_{h}$ and $V_{k}(t)V_{k}(t)^{\intercal}$ given by the population second moment $\Sigma_{t}$. The sample complexity and the reconstruction error both depend on the $\gamma_{2}$ function and eigen-gap $\alpha_{t}$. A small eigen-gap $\alpha_{t}$ requires larger public sample $m$.

2 Empirical Risk Convergence Analysis

For $\rho$-smooth function $\hat{L}_{n}({\mathbf{w}})$, under Assumptions 1 and 2, let $\Lambda=\frac{\sum_{t=1}^{T}1/\alpha^{2}_{t}}{T}$, for any $\epsilon,\delta>0$, with $T=O(n^{2}\epsilon^{2})$ and $\eta_{t}=\frac{1}{\sqrt{T}}$, PDP-SGD achieves:

Additionally, assuming the principal component of the gradient dominates, i.e., there exist $c>0$, such that $\frac{1}{T}\sum_{t=1}^{T}\|[\nabla\hat{L}_{n}({\mathbf{w}}_{t})]^{\bot}\|_{2}^{2}\leq c\frac{1}{T}\sum_{t=1}^{T}\|[\nabla\hat{L}_{n}({\mathbf{w}}_{t})]^{\parallel}\|_{2}^{2}$, we have

where ${\mathbf{w}}_{R}$ is uniformly sampled from $\{{\mathbf{w}}_{1},...,{\mathbf{w}}_{T}\}$.

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 $\gamma_{2}$ function and the eigen-gap $\alpha_{t}$, i.e., $\Lambda=\sum_{t=1}^{T}1/\alpha^{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 $\gamma_{2}$ is a constant. The term $\Lambda$ depends on the eigen-gap $\alpha_{t}$, i.e, $\lambda_{k}\left(\Sigma_{t}\right)-\lambda_{k+1}\left(\Sigma_{t}\right)\geq\alpha_{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 $\Lambda$ will be a constant and the bound scales logarithmically with $p$. If one considers the eigen-gap $\alpha_{t}$ decays as training proceed, e.g., $\alpha_{t}=\frac{1}{t^{1/4}}$ for $t>0$, then we have $\Lambda=O(\sqrt{T})$. In this case, with $T=n^{2}\epsilon^{2}$, PDP-SGD requires the public data size $m=O(n\epsilon)$.

For the convex and Lipschitz functions, we consider the low-rank structure of the gradient space, i.e, the population gradient second momment $\Sigma_{t}$ is of rank-$k$, which is a special case of the principal gradient dominate assumption when $|[\nabla\hat{L}_{n}({\mathbf{w}}_{t})]^{\bot}\|_{2}=0$. We present the error rate of PDP-SGD for such case in the following theorem.

For $G$-Lipschitz and convex function $\hat{L}_{n}({\mathbf{w}})$, under Assumptions 1,2 and assuming $\Sigma_{t}$ is of rank-$k$, let $\Lambda=\frac{\sum_{t=1}^{T}1/\alpha_{t}}{T}$, for any $\epsilon,\delta>0$, with $T=O(n^{2}\epsilon^{2})$, step size $\eta_{t}=\frac{1}{\sqrt{T}}$, the PDP-SGD achieves

where $\bar{\mathbf{w}}=\frac{\sum_{t=1}^{T}{\mathbf{w}}_{t}}{T}$, and ${\mathbf{w}}^{\star}$ is the minima of $\hat{L}_{n}({\mathbf{w}})$.

Compared to the error rate of DP-SGD for convex functions Bassily et al. (2014, 2019a), PDP-SGD also demonstrates an improvement from a factor of $p$ to $k$. PDP-SGD also involves the subspace reconstruction error, i.e., $O\left(\frac{\Lambda G\rho\gamma_{2}(\mathcal{W},d)\ln p}{\sqrt{m}}\right)$ depending on the $\gamma_{2}$ function and eigen-gap term $\Lambda=\frac{\sum_{t=1}^{T}1/\alpha_{t}}{T}$. Based on the discussion in previous section and a more detailed discussion in Appendix A.2, with suitable assumptions of the gradient structure, e.g., ellipsoids, the $\gamma_{2}$ is a constant. For the eigen-gap term, if $\alpha_{t}$ stays as a constant in the training procedure as shown by Figure 1, $\Lambda$ will be a constant and the bound scales logarithmically with $p$. If we assume the eigen-gap $\alpha_{t}$ decays as training proceed, e.g., $\alpha_{t}=\frac{1}{t^{1/2}}$ for $t>0$, then we have $\Lambda=O(\sqrt{T})$. In this case, with $T=n^{2}\epsilon^{2}$, PDP-SGD requires public data size $m=O(n\epsilon)$.

Experiments

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., $\sigma=\{18,14,10,8,6,4\}$ for MNIST and $\sigma=\{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, $\delta$, and noise $\sigma$. With 30 epochs, batch size $250$, $10,000$ training samples, and fixing $\delta=10^{-5}$, the $\epsilon$ is $\{2.41,~{}1.09,~{}0.72,~{}0.42,~{}0.30,~{}0.23\}$ for $\sigma\in\{2,~{}4,~{}6,~{}10,~{}14,~{}18\}$ for Fashion MNIST. For MNIST, $\epsilon$ is $\{1.09,~{}0.72,~{}0.53,~{}0.42,~{}0.30,~{}0.23\}$ for $\sigma\in\{4,~{}6,~{}8,~{}10,~{}14,~{}18\}$. Note that $\epsilon$ 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 $\epsilon$, are reported in Figure 3. For small $\epsilon$ regime, i.e., $\epsilon\leq 0.42$ with MNIST (Figure 3 (a)) and $\epsilon\leq 0.72$ with Fashion MNIST (Figure 3 (b)), PDP-SGD outperforms DP-SGD. For large $\epsilon$ (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 $\epsilon$, 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 $\epsilon<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 $\epsilon$. Figure 4 provides two examples of the training dynamics, i.e., MNIST with $\epsilon=0.23$ and Fashion MNIST with $\epsilon=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\in\{10,20,30,50\}$ and PDP-SGD with $m\in\{50,100,150\}$ for $\epsilon=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\approx 25,000$, it is impressive that PDP-SGD with $k=50$ can achieve better accuracy than DP-SGD for a certain range of $\epsilon$. 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 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 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.

Conclusion and Future Work

While differentially-private stochastic gradient descent (DP-SGD) algorithms and variants have been well studied for solving differentially private empirical risk minimization (ERM), the error rate of DP-SGD has a dependence on the ambient dimension $p$. In this paper, we aim at bypassing such dependence by leveraging a special structure of gradient space i.e., the stochastic gradients for deep nets usually stay in a low dimensional subspace in the training process. We propose PDP-SGD which projects the noisy gradient to an approximated subspace evaluated on a public dataset. We show that the subspace reconstruction error is small and PDP-SGD reduces the $p$ factor in the error rate to the projection dimension. We evaluate the proposed algorithms on two popular deep learning tasks and demonstrate the empirical advantages of PDP-SGD over DP SGD.

There are several interesting directions for future work. First, it will be interesting to provide an private optimization method that can identify the gradient subspace at each iteration without access to a public dataset. The existing "analyze-Gauss" techniques in Dwork et al. (2014) will give a bound with reconstruction error scaling with $\sqrt{p}$, which will be propagated to the optimization error. More recently, Song et al. (2020) show that, for a class of generalized linear problems, DP gradient descent (without any projection) achieves an excess empirical risk bound depending on the rank of the feature matrix instead of the ambient dimension. It will also be interesting to explore whether their rank-dependent bounds hold for a more general class of problems. Finally, a question that applies both to private and non-private optimization is to characterize the class of optimization problems with low-dimensional gradient subspaces.

Acknowledgement

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.

References

Appendix 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_{t}$ converges to the population second moment matrix $\Sigma_{t}$ uniform over all iterations $t\in[T]$, i.e., $\sup_{t\in[T]}\|M_{t}-\Sigma_{t}\|$. Then we show that the top-$k$ subspace of $M_{t}$ uniformly converges to the top-$k$ subspace of $\Sigma_{t}$, i.e., $\|\hat{V}_{k}(t)\hat{V}_{k}(t)^{\intercal}-V_{k}(t)V_{k}(t)^{\intercal}\|$ for all $t\in[T]$. Our bound depends on $\gamma_{2}({\cal W},d)$ where ${\cal 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 $\gamma_{2}({\cal M},d)$ as well, where ${\cal M}$ is the set of population gradients along the training trajectory. Then, we provide examples of the set ${\cal M}$ and corresponding value of $\gamma_{2}({\cal M},d)$.

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 $\gamma_{2}$ function (see Definition 2). Talagrand shows that for a process $\left(X_{t}\right)_{t\in T}$ and a given metric space $(T,d)$, if $\left(X_{t}\right)_{t\in T}$ satisfies the increment condition

then the size of the process can be bounded as

We first show that the variable $\left\|M_{t}-\Sigma_{t}\right\|_{2}$ satisfies the increment condition as stated in (9) 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.

To make the argument clear, we use a more informative notation for $M_{t}$ and $\Sigma_{t}$. Recall the notation of $M_{t}$ and $\Sigma_{t}$ such that

With Assumption 2 and 1 hold, for any ${\mathbf{w}},{\mathbf{w}}^{\prime}\in{\cal W}$ and $\forall u>0$, we have

By triangle inequality and the construction of $X_{i}$, we have

By Assumption 1 and Assumption 2 and definition

Let $Y_{i}=\frac{X_{i}}{4G\rho d({\mathbf{w}},{\mathbf{w}}^{\prime})}$, with (19), we have

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 .

Note that equation (4) is a uniform bound over iteration $t\in[T]$. To bound $\sup_{t\in[T]}\left\|M_{t}-\Sigma_{t}\right\|_{2}$, it is sufficient to bound

where ${\cal W}$ contains all the possible trajectorys of ${\mathbf{w}}_{1},...,{\mathbf{w}}_{T}$.

We consider a sequence of subsets ${\cal W}_{n}$ of ${\cal W}$, and

where $N_{0}=1;N_{n}=2^{2^{n}}\text{ if }n\geq 1.$

Let $\pi_{n}({\mathbf{w}})\in{\cal W}_{n}$ be the approximation of any ${\mathbf{w}}\in{\cal W}$. We decompose the $\|M({\mathbf{w}})-\Sigma({\mathbf{w}})\|_{2}$ as

which holds since $\pi_{n}({\mathbf{w}})={\mathbf{w}}$ for $n$ large enough.

with probability at most $2p\exp(-\frac{u^{2}}{4})$.

For any $n>0$ and ${\mathbf{w}}\in{\cal W}$, the number of possible pairs $\left(\pi_{n}({\mathbf{w}}),\pi_{n-1}({\mathbf{w}})\right)$ is

Apply union bound over all the possible pairs of $(\pi_{n}({\mathbf{w}}),\pi_{n-1}({\mathbf{w}}))$, following Talagrand (Chapter 2.2), for any $n>0$, $u>0$, and ${\mathbf{w}}\in{\cal W}$, we have

where $c^{\prime}$ is a universal constant.

with probability at most $c^{\prime}p\exp\left(-\frac{u^{2}}{4}\right)$.

with ptobability at most $2p\exp\left(-\frac{u^{2}}{4}\right)$.

with probability at most $(c^{\prime}+2)p\exp\left(-\frac{u^{2}}{4}\right)$.

Recall that $\hat{V}_{k}(t)$ is the top-$k$ eigenspace of $M_{t}$. Let $V_{k}(t)$ be the top-$k$ eigenspace of $\Sigma_{t}$.

where $\Pi_{M_{t}}^{(k)}=\hat{V}_{k}(t)\hat{V}_{k}(t)^{\intercal}$ denotes the projection to the top-$k$ subspace of the symmetric PSD $M_{t}$ and $\Pi_{\Sigma_{t}}^{(k)}=V_{k}(t)V_{k}(t)^{\intercal}$ denotes the projection to the top-$k$ subspace of the symmetric PSD $\Sigma_{t}$. Then, from Davis-Kahan (Corollary 8 in McSherry ) and using the fact for symmetric PSD matrices eigen-values and singular values are the same, we have

Recall, from Horn and Johnson (Section 4.3) and Golub and Van Loan (Section 8.1.2), e.g., Corollary 8.1.6, we have

From Theorem 2 and Lemma 2, with $Y=\|M_{t}-\Sigma_{t}\|_{2}$, $A=c$, and $B=\frac{4G\rho\sqrt{\ln p}\gamma_{2}(\mathcal{W},d)}{\sqrt{m}}$, we have

Let $c_{0}=O\left(G\rho\sqrt{\ln p}\gamma_{2}(\mathcal{W},d)\right)$. For $m\geq\frac{c_{0}^{2}}{\alpha_{t}^{2}}$, we have

Combining these two bounds and (41), with $c_{0}=O\left(G\rho\sqrt{\ln p}\gamma_{2}(\mathcal{W},d)\right)$, we have

Using (42) such that $\frac{c_{0}}{\sqrt{m}}\leq\frac{\alpha_{t}}{2}$, we have

Consider a r.v. $Y\geq 0$ which satisfies

for certain numbers $A\geq 2$ and $B>0$. Then

In this section, we provide more intuitions and explanations of $\gamma_{2}$ functions. We justify our assumptions about the gradient space and provide more examples of the gradient space structure and the corresponding $\gamma_{2}$ functions.

At a high level, for a metric space $(M,d)$, $\gamma_{2}(M,d)$ is related to $\sqrt{\log N(M,d,\epsilon)}$ where $N(M,d,\epsilon)$ is the covering number of $M$ with $\epsilon$ 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 $\epsilon$ 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 $\gamma_{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 ].

Composition. Based on the composition properties of $\gamma_{2}$ functions Talagrand , one can construct additional examples of the gradient spaces. If ${\cal M}={\cal M}_{1}+{\cal M}_{2}=\{\mathbf{m}_{1}+\mathbf{m}_{2},\mathbf{m}_{1}\in{\cal M}_{1},\mathbf{m}_{2}\in{\cal M}_{2}\}$, the Minkowski sum, then $\gamma_{2}({\cal M},d)\leq c(\gamma_{2}({\cal M}_{1},d)+\gamma_{2}({\cal M}_{2},d))$ (Theorem 2.4.15 in Talagrand ), where $c$ is an absolute constant. If ${\cal M}$ is a union of several subset, i.e., ${\cal M}=\cup_{h=1}^{D}M_{h}$, then by using an union bound on Theorem 2, we have $\gamma_{2}({\cal M},d)\leq\sqrt{\log D}\max_{h}\gamma_{2}({\cal M}_{h},d)$. Thus, if ${\cal M}$ is an union of $D=p^{s}$ ellipsoids, i.e., polynomial in $p$, then $\gamma_{2}({\cal M},\|\cdot\|_{2})\leq O\left(\sqrt{s}\log p\right)$.

Appendix 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.

Let $\bar{\mathbf{g}}_{t}=\mathbf{g}_{t}+\hat{V}_{k}\hat{V}_{k}^{\intercal}\mathbf{b}_{t},$ and $\Delta_{t}=\hat{V}_{k}\hat{V}_{k}^{\intercal}\mathbf{g}_{t}-\mathbf{g}_{t}.$ Then we have

Since $\mathbf{b}_{t}$ is a zero mean Gaussian vector, we have

For $\rho$-smooth The Assumption 2 suggests that the $\hat{L}_{n}({\mathbf{w}})$ is $\rho$-smooth. function $\hat{L}_{n}({\mathbf{w}})$, conditioned on ${\mathbf{w}}_{t}$, we have

where $Q_{t}$ is $\hat{V}_{k}(t)\hat{V}_{k}(t)^{\intercal}$ and $\Pi_{Q_{t}}$ is the projection. $Q_{t}^{\bot}$ is the null space of $Q_{t}$.

Bringing the above to (54), the right-hand side of (54) becomes

Bringing the upper bound of $D_{t,2}$ to (61), setting $\eta_{t}=\frac{1}{\sqrt{T}}$, using telescoping sum and taking the expectation over all iterations, we have

With triangle inequality and Theorem 3, we have

where $\Lambda=\sum_{t=1}^{T}\frac{1}{\alpha_{t}^{2}}$.

Let $\left[\nabla\hat{L}_{n}({\mathbf{w}}_{t})\right]^{\parallel}=V_{k}(t)V_{k}(t)^{\intercal}\nabla\hat{L}_{n}({\mathbf{w}}_{t})$ and $\left[\nabla\hat{L}_{n}({\mathbf{w}}_{t})\right]^{\bot}=\nabla\hat{L}_{n}({\mathbf{w}}_{t})-V_{k}(t)V_{k}(t)^{\intercal}\nabla\hat{L}_{n}({\mathbf{w}}_{t})$.

where ${\mathbf{w}}_{R}$ is uniformly sampled from $\{{\mathbf{w}}_{1},...,{\mathbf{w}}_{T}\}$. ∎

Appendix C Error Rate of Convex Problems

For the convex and Lipschitz functions, we consider the low-rank structure of the gradient space, i.e, the population gradient second momment $\Sigma_{t}$ is of rank-$k$, which is a special case of the principal gradient dominate assumption when $|[\nabla\hat{L}_{n}({\mathbf{w}}_{t})]^{\bot}\|_{2}=0$.

Proof: By the convexity of $\hat{L}_{n}({\mathbf{w}})$, we have

Let $\bar{\mathbf{g}}_{t}=\mathbf{g}_{t}+\hat{V}_{k}\hat{V}_{k}^{\intercal}\mathbf{b}_{t},$ and $\Delta_{t}=\hat{V}_{k}\hat{V}_{k}^{\intercal}\mathbf{g}_{t}-\mathbf{g}_{t}.$ Then we have

By convexity, conditioned at ${\mathbf{w}}_{t}$, we have

and $\|{\mathbf{w}}_{t+1}-{\mathbf{w}}^{\star}\|_{2}\leq B$ For convex problem, we consider ${\mathbf{w}}\in{\cal H}$, where ${\cal H}=\{{\mathbf{w}}:\|{\mathbf{w}}\|\leq B\}$..

Let $\eta_{t}=\frac{1}{\sqrt{T}}$, taking the expectation over all iterations and sum over $t=1,..,T$, we have

where the last inequality holds because the $\Sigma_{t}$ is of rank $k$ and $V(t)=V_{k}(t)$.

Bring this to (75), use the fact that $\|{\mathbf{w}}_{0}-{\mathbf{w}}^{\star}\|<B$, with Jensen’s inequality we have

where $\Lambda=\sum_{t=1}^{\intercal}\frac{1}{\alpha_{t}}$.

With $\sigma^{2}=\frac{G^{2}T}{n^{2}\epsilon^{2}}$, let $T=n^{2}\epsilon^{2}$, we have

Appendix 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 dataset PDP-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. . 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. 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., $\sigma=\{18,14,10,8,6,4\}$ for MNIST and $\sigma=\{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. to guarantee the privacy. We implement the micro-batch clipping method in PyTorch We implement the clipping method based on this repository: https://github.com/ChrisWaites/pyvacy.. 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, $\delta$, and noise variance $\sigma$. With 30 epochs, batch size $250$, $10,000$ training samples, and fixing $\delta=10^{-5}$, the $\epsilon$ is $\{2.41,1.09,0.72,0.42,0.30,0.23\}$ for $\sigma\in\{2,4,6,10,14,18\}$ for Fashion MNIST. For MNIST, $\epsilon$ is $\{1.09,0.72,0.53,0.42,0.30,0.23\}$ corresponding to $\sigma=\{4,6,8,10,14,18\}$. Note that the $\epsilon$ 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 $\epsilon$ and do a search over the epochs, batch size and noise scale to boost the performance for a fixed privacy level $\epsilon$. 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 $\epsilon$, 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\in\{10,20,30,50\}$ for MNIST with $\epsilon=0.30$ (Figure 9(a)) and $\epsilon=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\approx 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\in\{50,150,200\}$ for $\epsilon=0.23$ and $\epsilon=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 $\epsilon$ 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.