Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning

Introduction

Recent works have shown that the trained model may leak/memorize the information of its training set (Fredrikson et al. 2015; Wu et al. 2016; Shokri et al. 2017; Hitaj et al. 2017), which raises privacy issue when the models are trained with sensitive data. Differential privacy (DP) mechanism provides a way to quantitatively measure and upper bound such information leakage. It theoretically ensures that the influence of any individual sample is negligible with the DP parameter $\epsilon$ or $(\epsilon,\delta)$. Moreover, it has been observed that differentially private models can also resist model inversion attack (Carlini et al. 2019), membership inference attack (Rahman et al. 2018; Bernau et al. 2019; Sablayrolles et al. 2019; Yu et al. 2021), gradient matching attack (Zhu et al. 2019), and data poisoning attack (Ma et al. 2019).

The dimensional barrier is attributed to the fact that the added noise is isotropic while the gradients live on a very low dimensional manifold, which has been observed in (Gur-Ari et al. 2018; Vogels et al. 2019; Gooneratne et al. 2020; Li et al. 2020) and is also verified in Figure 2 for the gradients of a 20-layer ResNet (He et al. 2016). Hence to limit the noise energy, it is natural to think

“Can we reduce the dimension of gradients first and then add the isotropic noise onto a low-dimensional gradient embedding?"

The answer is affirmative. We propose a new algorithm Gradient Embedding Perturbation (GEP), illustrated in Figure 3. Specifically, we first compute anchor gradients on some non-sensitive auxiliary data, and identify an anchor subspace that is spanned by several top principal components of the anchor gradient matrix. Then we project the private gradients into the anchor subspace and obtain low-dimensional gradient embeddings and small-norm residual gradients. Finally, we perturb the gradient embedding and residual gradient separately according to the sensitivities and privacy budget.

We intuitively argue why GEP could reduce the perturbation variance and achieve good utility for large models. First, because the gradient embedding has a very low dimension, the added isotropic noise on embedding has small energy that scales linearly only with the subspace dimension. Second, if the anchor subspace can cover most of the gradient information, the residual gradient, though high dimensional, should have small magnitude, which permits smaller added noise to guarantee the same level privacy because of the reduced sensitivity. Overall, we can use a much lower perturbation compared with the original gradient perturbation to guarantee the same level of privacy.

We emphasize several properties of GEP. First, the non-sensitive auxiliary data assumption is weak. In fact, GEP only requires a small number of non-sensitive unlabeled data following a similar feature distribution as the private data, which often exist even for learning on sensitive data. In our experiments, we use a few unlabeled samples from ImageNet to serve as auxiliary data for MNIST, SVHN, and CIFAR-10. This assumption is much weaker than the public data assumption in previous works (Papernot et al. 2017; Papernot et al. 2018; Alon et al. 2019; Wang & Zhou 2020), where the public data should follow exactly the same distribution as the private data. Second, GEP produces an unbiased estimator of the target gradient because of releasing both the perturbed gradient embedding and the perturbed residual gradient, which turns out to be critical for good utility. Third, we use power method to estimate the principal components of anchor gradients, achievable with a few matrix multiplications. The fact that GEP is not sensitive to the choices of subspace dimension further allows a very efficient implementation.

Compared with existing works of differentially private machine learning, our contribution can be summarized as follows: (1) we propose a novel algorithm GEP that achieves good utility for large models with modest differential privacy guarantee; (2) we show that GEP returns an unbiased estimator of target private gradient with much lower perturbation variance than original gradient perturbation; (3) we demonstrate that GEP achieves state-of-the-art utility in differentially private learning with three benchmark datasets. Specifically, for $\epsilon=8$, GEP achieves $74.9\%$ test accuracy on CIFAR-10 with a ResNet20 model. To the best of our knowledge, GEP is the first algorithm that can achieve such utility with training deep models from scratch for a ‘‘single-digit" privacy budget Abadi et al. 2016 achieve $73\%$ accuracy on CIFAR-10 but they need to pre-train the model on CIFAR-100..

Existing works studying differentially private machine learning in high-dimensional setting can be roughly categorized into two sets. One is treating the optimization of the machine learning objective as a whole mechanism and adding noise into this process. The other one is based on the knowledge transfer of machine learning models, which trains a differentially private publishable student model with private signals from teacher models. We review them one by one.

Differentially private convex optimization in high-dimensional setting has been studied extensively over the years (Kifer et al. 2012; Thakurta & Smith 2013; Talwar et al. 2015; Wang & Xu 2019; Wang & Gu 2019). Although these methods demonstrate good utility on some convex settings, their analyses can not be directly applied to non-convex setting. Right before the submission, we note two independent and concurrent works (Zhou et al. 2020; Kairouz et al. 2020) that also leverage the gradient redundancy to reduce the added noise. Specifically, Kairouz et al. 2020 track historical gradients to do dimension reduction for private AdaGrad. Zhou et al. 2020 requires gradients on some public data and then project the noisy gradients into a public subspace at each update. One core difference between these two works and GEP is that we introduce residual gradient perturbation and GEP produces an unbiased estimator of the private gradients, which is essential for achieving the superior utility. Moreover, we weaken the auxiliary data assumption and introduce several designs that significantly boost the efficiency and applicability of GEP.

One recent progress towards training arbitrary models with differential privacy is Private Aggregation of Teacher Ensembles (PATE) (Papernot et al. 2017; Papernot et al. 2018; Jordon et al. 2019). PATE first trains independent teacher models on disjoint shards of private data. Then it trains a student model with privacy guarantee by distilling noisy predictions of teacher models on some public samples. In comparison, GEP only requires some non-sensitive data that have similar natural features as the private data while PATE requires the public data follow exactly the same distribution as the private data and in practice it uses a portion of the test data to serve as public data. Moreover, GEP demonstrates better performance than PATE especially for complex datasets, e.g., CIFAR-10, because GEP can train the model with the whole private data rather than a small shard of data.

Preliminaries

By its definition, $(\epsilon,\delta)$-DP controls the maximum influence that any individual sample can produce. One can adjust the privacy parameters to trade off between privacy and utility. Differential privacy is immune to post-processing (Dwork et al. 2014), i.e., any function applied on the output of a differentially private algorithm would not increase the privacy loss as long as it does not have new interaction with the private dataset. Differential privacy also allows composition, i.e., the composition of a series of differentially private mechanisms is also differentially private but with different parameters. Several variants of $(\epsilon,\delta)$-DP have been proposed (Bun & Steinke 2016; Dong et al. 2019) to address certain weakness of $(\epsilon,\delta)$-DP, e.g., they achieve better composition property. In this work, we use Rényi differential privacy (Mironov 2017) to track the privacy loss and then convert it to $(\epsilon,\delta)$-DP.

Gradient embedding perturbation

An overview of GEP is given in Figure 3. GEP has three major ingredients: 1) first, estimate an anchor subspace that contains the principal components of some non-sensitive anchor gradients via power method; 2) then, project private gradients into the anchor subspace and produce low-dimensional embeddings of private gradients and residual gradients; 3) finally, perturb gradient embedding and residual gradient separately to establish differential privacy guarantee. In Section 3.1, we present the GEP algorithm in detail. In Section 3.2, we given an analysis on the residual gradients. In Section 3.3, we give a differentially private learning algorithm that updates the model with the output of GEP.

The pseudocode of GEP is presented in Algorithm 1. For convenience, we write a set of gradients and a set of basis vectors as matrices with each row being one gradient/basis vector.

[] Let $S_{1}$ and $S_{2}$ be the sensitivity of ${\bm{w}}$ and ${\bm{r}}$, respectively, the output of Algorithm 1 satisfies $(\epsilon,\delta)$-DP for any $\delta\in(0,1)$ and $\epsilon\leq 2\log(1/\delta)$ if we choose $\sigma_{1}\geq 2S_{1}\sqrt{2\log(1/\delta)}/\epsilon$ and $\sigma_{2}\geq 2S_{2}\sqrt{2\log(1/\delta)}/\epsilon$.

A common practice to control sensitivity is to clip the output with a pre-defined threshold. In our experiments, we use different thresholds $S_{1}$ and $S_{2}$ to clip the gradient embeddings and residual gradients, respectively. The privacy loss of GEP consists of two parts: the privacy loss incurred by releasing the perturbed embedding and the privacy loss incurred by releasing the perturbed residual gradient. We compose these two parts via the Rényi differential privacy and convert it to $(\epsilon,\delta)$-DP.

We highlight several implementation techniques that make GEP widely applicable and implementable with reasonable computational cost. Firstly, auxiliary non-sensitive data do not have to be the same source as the private data and the auxiliary data can be randomly labeled. This non-sensitive data assumption is very weak and easy to satisfy in practical scenarios. To understand why random label works, a quick example is that for the least squares regression problem the individual gradient is aligned with the feature vector while the label only scales the length but does not change the direction. This auxiliary data assumption avoids conducting principal component analysis (PCA) on private gradients, which requires releasing private high-dimensional basis vectors and hence introduces large privacy loss. Secondly, we use power method (Panju 2011; Vogels et al. 2019) to approximately estimate the principal components. The new operation we introduce is standard matrix multiplication that enjoys efficient implementation on GPU. The computational complexity of each power iteration is $2mkp$, where $p$ is the number of model parameters, $m$ is the number of anchor gradients and $k$ is the number of subspace basis vectors. Thirdly, we divide the parameters into different groups and compute one orthonormal basis for each group. This further reduces the computational cost. For example, suppose the parameters are divided into two groups with size $p_{1},p_{2}$ and the numbers of basis vectors are $k_{1},k_{2}$, the computational complexity of each power iteration is $2m(k_{1}p_{1}+k_{2}p_{2})$, which is smaller than $2m(k_{1}+k_{2})(p_{1}+p_{2})$. In Appendix B, we analyze the additional computational and memory costs of GEP compared to standard gradient perturbation.

Curious readers may wonder if we can use random projection to reduce the dimensionality as Johnson–Lindenstrauss Lemma (Dasgupta & Gupta 2003) guarantees that one can preserve the pairwise distance between any two points after projecting into a random subspace of much lower dimension. However, preserving the pairwise distance is not sufficient for high quality gradient reconstruction, which is verified by the empirical observation in Appendix C.

2 An analysis on the residual gradients of GEP

Let ${\bm{g}}:=\frac{1}{n}\sum_{i}{\bm{G}}_{i,:}$ be the target private gradient. For a given anchor subspace ${\bm{B}}$, the residual gradients are defined as ${\bm{R}}:={\bm{G}}-{\bm{G}}{\bm{B}}^{T}{\bm{B}}$. We then analyze how large the residual gradients could be. The following argument holds for all time steps and we ignore the time step index for simplicity.

One case is that the population gradient covariance matrix ${\bm{\Sigma}}$ is low-rank $k$. In this case we can argue that the residual gradients are $0$ once the number of anchor gradients $m>k$.

The proof is based on the non-singularity of covariance matrix. See Appendix D. ∎

Assume that ${\bm{\xi}}\sim{\mathcal{P}}$ and $\|{\bm{\xi}}\|^{2}<T$ almost surely. Let ${\bm{\Sigma}}={\bm{V}}\Lambda{\bm{V}}^{T}$ be the eigendecomposition of the population covariance matrix ${\bm{\Sigma}}$. Let $\hat{{\bm{S}}}=\hat{{\bm{V}}}_{k}\hat{\Lambda}\hat{{\bm{V}}}_{k}^{T}$ be the eigendecomposition of the empirical covariance matrix $\hat{{\bm{S}}}$. Then we have with probability $1-2\exp(-\delta)$,

The proof is an adaptation of Theorem 3.1 in Blanchard et al. 2007. ∎

From Lemma 3.2, we can see the larger the number of anchor gradients and the dimension of the anchor subspace $k$, the smaller the residual gradients. We can choose $m,k$ properly such that the upper bound on the expected residual gradient norm is small. This indicates that we may use a smaller clipping threshold and consequently apply smaller noises with achieving the same privacy guarantee.

We next empirically examine the projection error ${\bm{r}}=\sum_{i}{\bm{R}}_{i,:}$ by training a $20$-layer ResNet on CIFAR10 dataset. We try two different types of auxiliary data to compute the anchor gradients: 1) samples from the same source as private data with correct labels, i.e., $2000$ random samples from the test data; 2) samples from different source with random labels, i.e., $2000$ random samples from ImageNet. The relation between the dimension of anchor subspace $k$ and the projection error rate ($\left\lVert\frac{1}{n}{\bm{r}}\right\rVert/\left\lVert{\bm{g}}\right\rVert$) is presented in Figure 5. We can see that the project error is small and decreases with $k$, and the benefit of increasing $k$ diminishes when $k$ is large, which is implied by Lemma 3.2. In practice one can only use small or moderate $k$ because of the memory constraint. GEP needs to store at least $k$ individual gradients and each individual gradient consumes the same amount of memory as the model itself. Moreover, we can see that the projection into anchor subspace of random labeled auxiliary data yields comparable projection error, corroborating our argument that unlabeled auxiliary data are sufficient for finding the anchor subspace.

We also verify that the redundancy of residual gradients is small, by plotting the stable rank of residual gradient matrix in Figure 5. The stable rank of residual gradient matrix is an order of magnitude higher than the stable rank of original gradient matrix. This implies that it could be hard to further approximate ${\bm{R}}$ with low-dimensional embeddings.

3 Private learning with gradient embedding perturbation

GEP (Algorithm 1) describes how to release one-step gradient with privacy guarantee. In this section, we compose the privacy losses at each step to establish the privacy guarantee for the whole learning process. The differentially private learning process with GEP is given in Algorithm 2 and the privacy analysis is presented in Theorem 3.3.

[] For any $\epsilon<2\log(1/\delta)$ and $\delta\in(0,1)$, the output of Algorithm 2 satisfies $(\epsilon,\delta)$-DP if we set $\sigma\geq 2\sqrt{2T\log(1/\delta)}/\epsilon$.

If the private gradients are randomly sampled from the full batch gradients, the privacy guarantee can be strengthened via the privacy amplification by subsampling theorem of DP (Balle et al. 2018; Wang et al. 2019; Zhu & Wang 2019; Mironov et al. 2019). Theorem 3.3 gives the expected excess error of Algorithm 2. Expected excess error measures the distance between the algorithm’s output and the optimal solution in expectation.

The $\bar{r}$ term represents the average projection error over the training process. The previous best expected excess error for gradient perturbation is $\mathcal{O}(\sqrt{p\log(1/\delta)}/(n\epsilon))$ (Wang et al. 2017). As shown in Lemma 3.1, if the gradients locate in a $k$-dimensional subspace over the training process, $\bar{r}=0$ and the excess error is $\mathcal{O}(\sqrt{k\log(1/\delta)}/(n\epsilon))$, independent of the problem ambient dimension $p$. When the gradients are in general position, i.e., gradient matrix is not exact low-rank, Lemma 3.2 and the empirical result give a hint on how small the residual gradients could be. However, it is hard to get a good bound on $\max_{i}\|({\bm{R}}_{t})_{i,:}\|$ and the bound in Theorem 3.3 does not explicitly improve over previous result. One possible solution is to use a clipping threshold based on the expected residual gradient norm. Then the output gradient becomes biased because of clipping and the utility/privacy guarantees in Theorem 3.3/3.3 require new elaborate derivation. We leave this for future work.

Experiments

We conduct experiments on MNIST, extended SVHN, and CIFAR-10 datasets. Our implementation is publicly available https://github.com/dayu11/Gradient-Embedding-Perturbation. The model for MNIST has two convolutional layers with max-pooling and one fully connected layer. The model for SVHN and CIFAR-10 is ResNet20 in He et al. 2016. We replace all batch normalization (Ioffe & Szegedy 2015) layers with group normalization (Wu & He 2018) layers because batch normalization mixes the representations of different samples and makes the privacy loss cannot be analyzed accurately. The non-private accuracy for MNIST, SVHN, and CIFAR-10 is 99.1%, 95.9%, and 90.4%, respectively.

We also provide experiments with pre-trained models in Appendix A. Tramèr & Boneh 2020 show that differentially private linear classifier can achieve high accuracy using the features produced by pre-trained models. We examine whether GEP can improve the performance of such private linear classifiers. Notably, using the features produced by a model pre-trained on unlabeled ImageNet, GEP achieves 94.8% validation accuracy on CIFAR10 with $\epsilon=2$.

Evaluated algorithms We use the algorithm in Abadi et al. 2016 as benchmark gradient perturbation approach, referred to as “GP”. We also compare GEP with PATE (Papernot et al. 2017). We run the experiments for PATE using the official implementation. The privacy parameter $\epsilon$ of PATE is data-dependent and hence cannot be released directly (see Section 3.3 in Papernot et al. 2017). Nonetheless, we report the results of PATE anyway.

Implementation details At each step, GEP needs to release two vectors: the noisy gradient embedding and the noisy residual gradient. The gradient embeddings have a sensitivity of $S_{1}$ and the residual gradients have a sensitivity of $S_{2}$ because of the clipping. The output of GEP can be constructed as follows: (1) normalize the gradient embeddings and residual gradients by $1/S_{1}$ and $1/S_{2}$, respectively, (2) concatenate the rescaled vectors, (3) release the concatenated vector via gaussian mechanism with sensitivity $\sqrt{2}$, (4) rescale the two components by $S_{1}$ and $S_{2}$. B-GEP only needs to release the normalized noisy gradient embedding. We use the numerical tool in Mironov et al. 2019 to compute the privacy loss. For given privacy budget and sampling probability, $\sigma$ is set to be the smallest value such that the privacy budget is allowable to run desired epochs.

All experiments are run on a single Tesla V100 GPU with 16G memory. For ResNet20, the parameters are divided into five groups: input layer, output layer, and three intermediate stages. For a given quota of basis vectors, we allocate it to each group according to the square root of the number of parameters in each group. We compute an orthonormal subspace basis on each group separately. Then we concatenate the projections of all groups to construct gradient embeddings. The number of power iterations $t$ is set as $1$ as empirical evaluations suggest more iterations do not improve the performance for GEP and B-GEP.

For all datasets, the anchor gradients are computed on $2000$ random samples from ImageNet. In Appendix C, we examine the influence of choosing different numbers of anchor gradients and different sources of auxiliary data. The selected images are downsampled into size of $32\times 32$ ($28\times 28$ for MNIST) and we label them randomly at each update. For SVHN and CIFAR-10, $k$ is chosen from $$. For MNIST, we halve the size of$k$. We use SGD with momentum 0.9 as the optimizer. Initial learning rate and batchsize are$0.1$and$1000$, respectively. The learning rate is divided by$10$at middle of training. Weight decay is set as$1\times 10^{-4}$. The clipping threshold for is$10$for original gradients and$2$for residual gradients. The number of training epochs for CIFAR-10 and MNIST is 50, 100, 200 for privacy parameter$\epsilon=2,5,8$, respectively. The number of training epochs for SVHN is 5, 10, 20 for privacy parameter$\epsilon=2,5,8$, respectively. Privacy parameter$\delta$is$1\times 10^{-6}$for SVHN and$1\times 10^{-5}$ for CIFAR-10 and MNIST.

Results The best accuracy with given $\epsilon$ is in Table 1. For all datasets, GEP achieves considerable improvement over GP in Abadi et al. 2016. Specifically, GEP achieves $74.9\%$ test accuracy on CIFAR-10 with $(8,10^{-5})$-DP, outperforming GP by $18.5\%$. PATE achieves best accuracy on MNIST but its performance drops as the dataset becomes more complex.

We also plot the relation between accuracy and $k$ in Figure 6. GEP is less sensitive to the choice of $k$ and outperforms B-GEP for all choices of $k$. The improvement of increasing $k$ becomes smaller as $k$ becomes larger. We note that the memory cost of choosing large $k$ is high because we need to store at least $k$ individual gradients to compute anchor subspace.

Conclusion

In this paper, we propose Gradient Embedding Perturbation (GEP) for learning with differential privacy. GEP leverages the gradient redundancy to reduce the added noise and outputs an unbiased estimator of target gradient. The several key designs of GEP significantly boost the applicability of GEP. Extensive experiments on real world datasets demonstrate the superior utility of GEP.

References

Appendix A Experiments with pre-trained models

Recent works have shown that pre-training the models on unlabeled data can be beneficial for subsequent learning tasks (Chen et al. 2020a; He et al. 2020). Tramèr & Boneh 2020 demonstrate that differentially private linear classifier can achieve high accuracy using the features produced by those per-trained models. We show that GEP can also benefit from such pre-trained models.

Inspired by Tramèr & Boneh 2020, we use the output of the penultimate layer of a pre-trained ResNet152 model as feature to train a private linear classifier. The ResNet152 model is pre-trained on unlabeled ImageNet using SimCLR (Chen et al. 2020a). The feature dimension is 4096.

Implementation Details We choose the privacy parameter $\epsilon$ from $[0.1,0.5,1,2]$. The privacy parameter $\delta$ is $1\times 10^{-5}$. We run all experiments for 5 times and report the average accuracy. The clipping threshold of residual gradients is still one-fifth of the clipping threshold of the original gradients. The dimension of anchor subspace is set as $200\simeq\sqrt{p}$ where $p=40960$ is the model dimension. We randomly sample $500$ samples from the test set as auxiliary data and evaluate performance on the rest test samples. The optimizer is Adam with default momentum coefficients. Other hyper-parameters are listed in Table 2.

Results The experiment results are shown in Table 3. GEP outperforms GP on all values of $\epsilon$. With privacy bound $\epsilon=2$, GEP achieves 94.8% validation accuracy on CIFAR10 dataset, improving over the GP baseline by 1.4%. For very strong privacy guarantee ($\epsilon=0.1$), B-GEP performs on par with GEP because strong privacy guarantee requires large noise and the useful signal in residual gradient is submerged in the added noise. B-GEP benefits less from larger $\epsilon$ compared to GP or GEP. For $\epsilon=1$ and $2$, the performance of B-GEP is worse than the performance of GP. This is because larger $\epsilon$ can not reduce the systematic error of B-GEP (see Remark 1 in Section 3.2).

Appendix B Complexity Analysis

We provide an analysis of the computational and memory costs of the construction of anchor subspace. The computation of the anchor subspace is the dominant additional cost of GEP compared to conventional gradient perturbation. Notations: $k$, $m$, $n$, and $p$ are the dimension of anchor subspace, number of anchor gradients, number of private gradients, and the model dimension, respectively. In order to reduce the computational and memory costs, we divide the parameters into $g$ groups and compute one orthonormal basis for each group. We refer to this approach as ‘parameter grouping’. In this section, we assume the parameters and the dimension of the anchor subspace are both divided evenly. Table 4 summarizes the additional costs of GEP with/without parameter grouping. Using parameter grouping can reduce the computational/memory cost significantly.

Appendix C Ablation Study

The influence of choosing different auxiliary datasets. We conduct experiments with different choices of auxiliary datasets. For CIFAR10, we try 2000 random test samples from CIFAR10, 2000 random samples from CIFAR100, and 2000 random samples from ImageNet. When the auxiliary dataset is CIFAR10, we try both correct labels and random labels. For all choices of auxiliary datasets, the test accuracy is evaluated on 8000 test samples of CIFAR10 that are not used as auxiliary data. Other implementation details are the same as in Section 4. The results are shown in Table 5. Surprisingly, using samples from CIFAR10 with correct labels yields the worst accuracy. This may because the model ‘overfits’ the auxiliary data when it has access to correct labels, which makes the anchor subspace contains less information about the private gradients. The best accuracy is achieved using samples from CIFAR10 with random labels, this makes sense because in this case the features of auxiliary data and private data have the same distribution. Using samples from CIFAR100 or ImageNet as auxiliary data has a small influence on the test accuracy.

The influence of the number of anchor gradients. In the main text, the size of auxiliary dataset is $m=2000$. We conduct more experiments with different sizes of auxiliary dataset to examine the influence of $m$. The auxiliary data is randomly sampled from ImageNet. Table 6 reports the test accuracy on CIFAR10 with different choices of $m$. For both B-GEP and GEP, increasing $m$ leads to slightly improved performance.

The projection error of random basis vectors. It is tempting to construct the anchor subspace using random basis vectors because Johnson–Lindenstrauss Lemma (Dasgupta & Gupta 2003) guarantees that one can preserve the pairwise distance between any two points after projecting into a random subspace of much lower dimension. We empirically verify the projection error of Gaussian random basis vectors on CIFAR10 and SVHN. The experiment settings are the same as in Section 4. The projection errors over the training process are plotted in Figure 7. The projection error of random basis vectors is very high ($>95\%$) throughout training. This is because preserving the pairwise distance is not sufficient for high quality gradient reconstruction, which requires one to preserve the average ‘distance’ between any individual gradient and all other gradients.

Appendix D Missing Proofs

We extend the Theorem 3.2 in Eaton & Perlman 1973 to the low-rank case.

We note that the subspace spanned by $\hat{{\bm{V}}}_{k^{\prime}}$ is in the space spanned by ${\bm{V}}_{k}$ by definition. Hence $k^{\prime}\leq k$.

We first introduce some background knowledge of Rényi differential privacy (RDP) (Mironov 2017). RDP measures the Rényi divergence between two output distributions.

where $D_{\lambda}(\cdot||\cdot)$ denotes the Rényi divergence of order $\lambda$.

We next introduce some useful properties of RDP.

If $M_{1}$, $M_{2}$ satisfy $(\lambda,\gamma_{1})$-RDP and $(\lambda,\gamma_{2})$-RDP respectively, then their composition satisfies $(\lambda,\gamma_{1}+\gamma_{2})$-RDP.

If $\mathcal{M}$ obeys $(\lambda,\gamma)$-RDP, then $\mathcal{M}$ obeys $(\gamma+\log(1/\delta)/(\lambda-1),\delta)$-DP for all $0<\delta<1$.

If we set $\sigma_{1}=S_{1}\sigma$ and $\sigma_{2}=S_{2}\sigma$ for some $\sigma$, then Algorithm 1 satisfies $(\lambda,\frac{\lambda}{\sigma^{2}})$-RDP because of Lemma D.2 and D.3. In order to guarantee $(\epsilon,\delta)$-DP, we need

Choose $\lambda=1+\frac{2\log(1/\delta)}{\epsilon}$ and rearrange Eq (5), we need

Then using the constraint on $\epsilon$ concludes the proof.

From the proof of Theorem 3.1, we have each call of GEP satisfies $(\lambda,\frac{\lambda}{\sigma^{2}})$-RDP. Then by the composition property of RDP (Lemma D.3), the output of Algorithm 2 satisfies $(\lambda,\frac{T\lambda}{\sigma^{2}})$-RDP. Plugging $\frac{T\lambda}{\sigma^{2}}$ into Equation 5 and 6 concludes the proof.

where ${\bm{z}}^{(1)}_{t}\sim\mathcal{N}(0,\sigma^{2}{\bm{I}}_{k\times k})$, ${\bm{z}}^{(2)}_{t}\sim\mathcal{N}(0,\sigma^{2}r_{t}^{2}{\bm{I}}_{p\times p})$ are the perturbation noises and $r_{t}=\max_{i}\left\lVert({\bm{R}}_{t})_{i,:}\right\rVert$ is the sensitivity of residual gradients at step $t$.

Take expectation on Eq (7) with respect to the perturbation noises.

Subtract $L(\boldsymbol{\theta}_{*})$ from both sides, we have

The second inequality holds because $L$ is convex. Then choose $\eta=\frac{1}{\beta}$ and plug $\nabla L(\boldsymbol{\theta}_{t})=(\boldsymbol{\theta}_{t}-\boldsymbol{\theta}_{t+1})/\eta-({\bm{z}}^{t}_{1}{\bm{B}}+{\bm{z}}^{t}_{2})/n$ into Eq (10).

Sum over $t=0,\ldots,T-1$ and use convexity, we have

Then substituting $T=\frac{n\beta\epsilon}{\sqrt{p}}$ and $\sigma=\mathcal{O}(\sqrt{T\log(1/\delta)}/\epsilon)$ yields the desired bound.