Fast and Memory Efficient Differentially Private-SGD via JL Projections

Introduction

Over the past decade, machine learning algorithms based on (deep) neural architectures have lead to a revolution in applications such as computer vision, speech recognition and natural language processing (NLP). An important factor contributing to this success is the abundance of data. For most of these applications, however, the training data comes from individuals, often containing personal and sensitive information about them. For example, natural language models for applications such as suggested replies for e-mails and dialog systems rely on the training of neural networks on email data of users Chen et al. (2019); Deb et al. (2019), who may be left vulnerable if personal information is revealed. This could happen, for example, when a model generates a sentence or predicts a word that can potentially reveal private information of users in the training set. Many studies have shown successful membership inference attacks on deep learning models Shokri et al. (2017); Carlini et al. (2019). Indeed, in a recent work, Carlini et al. (2019) show that “unintended memorization” in neural networks is both commonplace and hard to prevent. Such memorization is not due to overtraining Tetko et al. (1995); Carlini et al. (2019), and ad hoc techniques such as early-stopping, dropout etc., do not prevent the risk of privacy violations. Moreover, Feldman (2020) shows that memorization is in fact necessary, provably, for some learning tasks. Thus, to prevent unintended privacy breaches one needs a principled approach for private training of deep learning models. In this paper we study training neural networks with differential privacy, a mathematically rigorous notion of privacy introduced in the seminal work of Dwork et al. (2006), and focus on user level privacy.

We say that an algorithm $M$ is $(\varepsilon,\delta)$-DP if for any two neighboring databases $D,D^{\prime}$ and any subset $S$ of outputs, we have $\Pr[M(D)\in S]\leq e^{\varepsilon}\Pr[M(D^{\prime})\in S]+\delta.$

Besides being a provable privacy notion, it has been shown that deep learning models trained with DP protect against leakage of sensitive information; we refer the readers to Carlini et al. (2019); Abadi et al. (2016) for more details.

In a highly influential paper, Abadi et al. (2016) introduced a differentially private version of stochastic gradient descent (DP-SGD) for training deep learning models, and showed that it is possible to achieve reasonable accuracy-vs-privacy tradeoff on common benchmarks such as MNIST and CIFAR10. Since then, there has been a vast body of work building on and extending the algorithm of Abadi et al. (2016); we refer the readers to McMahan et al. (2018); Bu et al. (2019); Carlini et al. (2019); Thakkar et al. (2019); Augenstein et al. (2020); Zhou et al. (2020); Chen et al. (2020); Balle et al. (2020). The DP-SGD and its variations such as DP-Adam differ from their non-private counter parts in two crucial ways:

Adding Noise: Once clipped gradients are averaged across a batch, DP-SGD algorithm adds carefully calibrated noise, typically sampled from the Gaussian distribution, to ensure privacy.

The analysis of DP-SGD in Abadi et al. (2016) then follows from a careful tracking of privacy budget lost in each iteration, for which they introduced a novel technique called moments accountant, which was later generalized as Renyi differential privacy by Mironov (2017). This analysis was further refined and improved using the $f$-DP framework by Dong et al. (2019) and Bu et al. (2019), which lead to better privacy bounds. In this work, we use $f$-DP framework of Dong et al. (2019) for our privacy analysis.

While DP-SGD has been shown to achieve reasonable accuracy-vs-privacy tradeoff Bu et al. (2019); Abadi et al. (2016), and arguably is the only known algorithm for training deep neural networks, its use in real-world deep learning has been rather limited. One of the primary reasons for this is the training time of DP-SGD compared to SGD. In DP-SGD, per-sample gradients are computed at a heavy cost in runtime, especially for large deep learning models. The naive approach of setting the batch size to 1 is too slow to be practical as we completely lose the benefits of parallelization. This problem has attracted significant attention in the community and has been noted in popular implementations of DP-SGD including Tensorflow Privacy and Opacus (Pytorch DP). Many strategies have been proposed to circumvent this issue, and they fall broadly into the following categories:

Microbatching: DP-SGD implementation in Tensorflow Privacy allows dividing a batch into several microbatches and clipping the gradient at the microbatch level; the per-sample gradients in a microbatch are first averaged and then clipped, and finally these clipped gradients are averaged across microbatches. Thus, if each microbatch is of size $L$, then it gives a speedup of $L$ over the usual DP-SGD. Unfortunately, the sensitivity goes up by a factor of $L$, so we need to add $L$ times more noise. In our experiments, we observe that this often leads to poor accuracy even for moderate values of $L$.

Multiple method: In this approach, proposed by Goodfellow and implemented as the vectorized DP-SGD in Tensorflow Privacy , one copies the model as many times as there are samples in a batch. As each copy of the model is used on only one example, we can compute the per-sample gradients in parallel. This approach improves speed at the cost of memory and is impractical for large models.

Outer product method: This strategy was proposed by Goodfellow (2015) for fully-connected networks and later generalized by Rochette et al. (2019) to include convolutional layers. The norms of per-sample gradients are computed exactly using outer products between the activations and backpropagated gradients across adjacent layers. In a very recent work, Lee and Kifer (2021) showed how to extend this approach to recurrent layers. A drawback of this approach is that it does not work for all network architectures in a black-box manner, and needs careful implementation for each network architecture. Furthermore, the current implementations of these methods require significantly more memory than non-private SGD as shown in Subramani et al. (2020).

Compiler Optimization: A completely different approach towards mitigating the problem was suggested by Subramani et al. (2020). They showed that by exploiting language primitives, such as vectorization, just-in-time compilation, and static graph optimization, one can implement DP-SGD algorithm significantly faster. They demonstrated these ideas in two frameworks: JAX and TensorFlow. While we believe this is exciting progress, the ideas in Subramani et al. (2020) are specific to these JAX and TensorFlow implementations (as of today) and present a non-algorithmic approach to this problem.

As summarized in Table 1, none of these approaches for speeding up DP-SGD completely solve the problem and fall short in at least one dimension. In this work, we propose a new algorithmic framework based on JL-projections for fast and memory efficient differentially private training of deep neural networks, which bypasses the expensive step of exactly computing per-sample gradient norms.

To summarize, the key contributions of this paper are:

Our algorithms DP-SGD-JL and DP-Adam-JL are considerably faster than previously known differentially private training algorithms that require exact per sample gradient norms, and work for all network architectures. The privacy-vs-accuracy tradeoff achieved by our algorithms is comparable to the existing state-of-the-art DP-algorithms.

Memory footprint of our algorithms is nearly the same as that of non-private training algorithms. This allows us to work with larger batch sizes (which is crucial for achieving good privacy-vs-accuracy tradeoffs) without resorting to gradient accumulation. This also improves the running time of training.

Compared to DP-SGD, our analysis of privacy is more involved. Since we only approximate the per-sample gradient norms, we cannot precisely bound sensitivity. Therefore the analysis requires significantly new ideas, which could be of independent interest.

We demonstrate these improvements by training an RNN using layers such as bidirectional LSTM, embedding layer, fully connected etc. on the IMDb dataset. As can be seen from Figure 1, our algorithms are significantly faster than current implementations of DP-SGD while achieving similar privacy-vs-accuracy tradeoff.

Our algorithms introduce a new knob, the dimension of JL-projection, which allows us to do a tradeoff between training time and privacy, which was not possible in earlier algorithms. All hyperparameters being the same, smaller JL dimension will give much better running time with an increase in privacy budget. Moreover, our experiments show that although the privacy bounds we could prove for DP-SGD-JL are not so great for very small JL dimensions (see Figure 3), their behavior (accuracy-vs-epoch curve) converges very quickly to that of DP-SGD-Vanilla. Figure 4 shows that DP-SGD-JL(3) is already very close to DP-SGD-Vanilla and DP-SGD-JL(20) is almost indistinguishable. We find these properties of DP-SGD-JL algorithms to be very useful during initial stages of experimentation and hyper-parameter tuning for private training.

DP-SGD-JL Algorithm

In this section we describe our new differentially private optimizers. We will first present DP-SGD-JL, and DP-Adam-JL follows in the same lines and is presented in Appendix A. We begin with an introduction to “Jacobian-vector product” (jvp) which is crucial for our algorithm.

efficiently using forward-mode auto-differentiation (i.e., the required derivatives are calculated during the forward pass of the network). We refer the reader to the survey on automatic differentiation by Baydin et al. (2017) for more details. jvp is implemented using forward-mode auto-differentiation in the recent TensorFlow versions.Supported in tf-nightly$\geq$2.4.0.dev20200924 as tf.autodiff.ForwardAccumulator($\theta$,v).jvp(F). Unfortunately, PyTorch doesn’t have an implementation of forward-mode auto-differentiation. Instead, one can compute jvp using two calls to vjp, this is called the ‘double vjp trick’ (see Townsend ).In Pytorch, an implementation of jvp using the double vjp trick exists and can be invoked as torch.autograd.functional.jvp(F,$\theta$,inputs=v). Define $G(\alpha)=\alpha^{T}\nabla_{\theta}F$, which can be calculated using vjp. Note that $\nabla_{\alpha}G=(\nabla_{\theta}F)^{T}.$ Now we can use vjp again on $G$ to calculate jvp as

In our experiments, we use the efficient implementation of jvp in TensorFlow to compute the Jacobian-vector products as the double vjp trick is a few times slower.

2 Algorithm

By the properties of the standard Gaussian distribution, $\left\langle y,v_{i}\right\rangle$ has the distribution of $\left\lVert y\right\rVert_{2}\mathcal{N}(0,1).$ And $\left\langle y,v_{i}\right\rangle$ are independent for $i=1$ to $r$. Therefore $\sum_{i=1}^{r}\left\langle y,v_{i}\right\rangle^{2}$ has the same distribution as $\left\lVert y\right\rVert_{2}^{2}\chi^{2}_{r}.$ ∎

As shown in Figure 2, as $r$ grows larger, the distribution of $\sqrt{\frac{1}{r}\chi^{2}_{r}}$ concentrates more around 1 and therefore $M_{r}$ becomes a better estimate of $\left\lVert y\right\rVert_{2}.$ Using jvp, we can compute projections of per-sample gradients on to standard Gaussian vectors quickly and therefore get good approximations to their norms. This is the main idea of DP-SGD-JL (Algorithm 1). The privacy analysis of our algorithm is quite involved and is presented in Section 4.

Experiments

In this section, we demonstrate experimentally that compared to existing implementations of DP-SGD with exact per-sample gradient clipping, our optimizers have significant advantages in speed and memory cost while achieving comparable accuracy-vs-privacy tradeoff. Moreover our algorithms perform well on a variety of network architectures. The main goal of this section is to give empirical evidences towards the following three strengths of our algorithm alluded in the introduction:

Our algorithm is significantly faster compared to per-sample gradient computations and works for any network in a black-box way.

Memory footprint of our algorithm is roughly same as non-private SGD.

The DP-SGD-JL algorithms with smaller values of JL dimension exhibit similar behavior as DP-SGD but with orders of magnitude speed up, and hence can be used for hyper-parameter search.

In the following, we write ‘nonDP-SGD’ for the standard non-private SGD and ‘DP-SGD-Vanilla’ for the implementation of DP-SGD in Tensorflow Privacy , nonDP-Adam and DP-Adam-Vanilla are similarly defined. We use Tensorflow and Tensorflow Privacy for all our experiments because Opacus does not support arbitrary network architectures.In Pytorch Opacus github, the LSTM layer is only partially supported, e.g. single directional, single LSTM layer, no dropout layer; other recurrent layers such as GRU are not supported (see Opacus). Moreover Tensorflow has an efficient implementation of jvp while PyTorch doesn’t.

We denote the noise multiplier as $\sigma$, clipping norm as $C$, batch size as $B$, learning rate as $\eta$ and the number of epochs as $E=BT/N$. We fix the privacy parameter $\delta=10^{-5}$, as done by prior work. We denote the JL dimension used by each optimizer in the parentheses. We use one Tesla P100 16GB GPU for all experiments. In all the experiments, we report the time per epoch by averaging over a large number of epochs.

1 Training an LSTM model on IMDb dataset

The goal of these experiments is to demonstrate the first strength of our algorithm: it is significantly faster than per-sample gradient computations and works for any network in a black-box way. We train a bidirectional LSTM with an embedding layer on the IMDb dataset for sentiment analysis. We remark that simpler networks not based on RNNs can achieve good accuracy-vs-privacy tradeoff as shown in Bu et al. (2019) and Pytorch . However, LSTM models based on RNN architectures are widely used in NLP applications, and hence efficient private training of such models remains an important challenge in this area McMahan et al. (2018). Moreover, as we noted in the introduction, extensions of outer product trick to bidirectional LSTMs as described in Lee and Kifer (2021) are significantly more complicated, and require considerable effort to implement. Since authors of Lee and Kifer (2021) did not provide the code, we are unable to compare the improvements. Moreover, as also noted in Lee and Kifer (2021), the outer product method requires significantly more memory and hence will not scale to large batch sizes, which is very important to achieve good privacy vs utility tradeoff.

We implement DP-Adam-JL using jvp method in TensorFlow. We train the same single-layer bidirectional LSTMWe cannot use CuDNNLSTM and instead use LSTM for the following reason. When using CuDNNLSTM (and on GPU), we observe a significant speedup compared to LSTM, but the accuracy is invalid and we further incur a LookupError when computing jvp. as in the Tensorflow tutorial, using the same IMDb dataset with 8k vocabulary. The dataset has binary labels and is preprocessed by zero-padding the sequences to a length of 150 before being fed into the embedding layer.

Table 2 shows the training time per epoch for different algorithms. As expected, we observe that DP-Adam-JL algorithms with smaller values of JL dimension are significantly faster than DP-Adam-Vanilla. However, as we note in the Figure 3 privacy guarantees of DP-Adam-JL algorithm with smaller values of JL dimension are considerably worse than DP-Adam-Vanilla. On the other hand, DP-Adam-JL(30) is $30\times$ faster than DP-Adam-Vanilla while achieving similar privacy guarantees as DP-Adam-Vanilla. When allowed to train for sufficient number of epochs, we observed that all the algorithms achieved same accuracy but with different privacy costs and running times. This three dimensional tradeoff between utility, privacy and speed is depicted in the Figure 1 (see introduction), where we plot the privacy values using a color plot.

As we can see from Table 2, for a batch size of 256, the slowdown of DP-Adam-Vanilla is more than 256 compared to nonDP-Adam. This is counter intuitive as a naive implementation DP-Adam-Vanilla, by setting the batch size equal to 1 and then doing gradient accumulation across 256 batches should only be 256 times slower. As we show below, this is due to the memory issues of DP-Adam-Vanilla in the implementation in Tensorflow Privacy . Indeed the naive implementation of DP-Adam-Vanilla in tensorflow using gradient accumulation takes about 4000 seconds per epoch for the same batch size.

2 Memory footprint

Another key strength of JL based algorithms is their memory consumption, and the goal of this section is to show this aspect of our new algorithms via experiments. As a proxy for memory consumption, we compare the largest batch size each algorithm can handle without running out of memory. It is known that to achieve good privacy-vs-accuracy tradeoffs for DP-SGD, we need to use large batch sizes Abadi et al. (2016). One way to support large batch sizes is via gradient accumulation; however, this has the disadvantage that one loses parallelism, which in turns leads to slower run times. Hence memory footprint of algorithms also indirectly affects the training time.

We compare our JL algorithms with the implementation of DP-SGD-Vanilla in Tensorflow Privacy . We train a convolutional neural network from Tensorflow Privacy tutorial on MNIST dataset, which has 60,000 training samples.We use the implementation and the network from mnist_dpsgd_tutorial_keras.py As we can see from Table 3, DP-SGD-JL algorithm and nonDP-SGD can both run with the maximum possible batch size of 60,000 whereas DP-SGD-Vanilla can only handle a batch size of at most 500. In general, we believe that the memory footprint of DP-SGD-JL algorithm is very close to that of non-private SGD. To show this, we augment the CNN in Tensorflow Privacy tutorial with dense layers to blowup the model size to 17,146,938 parameters, and repeat the experiment. As we see from Table 4, the largest batch size supported by DPSGD-JL(30) is only a factor 2 away from the largest batch size supported by non-DP SGD. On the other hand, we observe that DP-SGD-Vanilla only supports a batch size of 100.

The above experiments also give a possible explanation of why DP-SGD-Vanilla implementation in TFP has a slowdown that is larger than the batch size, as we observed in the LSTM experiments. Even for MNIST, we observe that DP-SGD-Vanilla running time gets better with batch size in the very beginning but as the batch size becomes larger the running time gets worse, and soon after it runs out of memory.

3 Using DP-SGD-JL for hyper-parameter search

As we saw in our experiments summarized in Table 2, our algorithms with small values of JL dimension are orders of magnitude faster than DP-Adam-Vanilla; DP-Adam-JL(1) is about 470x faster and DP-SGD-JL(5) is about 150x faster. However, unfortunately, the privacy bounds we can prove for these algorithms are considerably worse than DP-Adam-Vanilla. Despite this drawback, we observe that behavior of DP-SGD-JL even for small JL dimension is very close to that of DP-Adam-Vanilla. Figure 4 plots the accuracy vs epochs for various algorithms training a CNN from Tensorflow Privacy tutorial on MNIST dataset. We observe that as JL dimension increases, the accuracy vs epoch curve quickly converges to that of DP-SGD-Vanilla. DP-SGD-JL(3) is already very similar to DP-SGD-Vanilla and DP-SGD-JL(20) is nearly indistinguishable. This also lets us hypothesize that the privacy of our algorithms could be much better than what we could prove and that it should converge equally quickly to that of DP-SGD-Vanilla. Thus we believe that DP-SGD-JL(3) or DP-SGD-JL(5) are good candidates for experimentation and hyper-parameter tuning during private training, since their behavior is almost identical to that of DP-SGD-Vanilla while being orders of magnitude faster.

Privacy Analysis

We use the recently proposed $f$-DP framework of Dong et al. (2019) for our privacy analysis. The $f$-DP framework allows us to reason about a collection of $(\varepsilon,\delta)$-privacy guarantees simultaneously which can then be composed to get a much better $(\varepsilon,\delta)$-privacy for the final algorithm. We will first define the notion of $(\varepsilon,\delta)$-DP formally and then define the notion of $f$-DP. We then state a proposition from Dong et al. (2019) which shows that these two notions are dual to each other.

We say that an algorithm $M$ is $(\varepsilon,\delta)$-DP if for any two neighboring databases $D,D^{\prime}$ and any subset $S$ of outputs, we have $\Pr[M(D)\in S]\leq e^{\varepsilon}\Pr[M(D^{\prime})\in S]+\delta.$

Given two random variables $X,Y$, we define $T(X||Y)$ to be $T(P||Q)$ where $P,Q$ are the distributions of $X,Y$ respectively.

Note that if $T(P,Q)=f$, then $T(Q,P)=f^{-1}.$ A tradeoff curve $f$ is called symmetric if $f^{-1}=f.$ Given two functions $f,g$ on the same domain, we say $f\preceq g$ if $f(x)\leq g(x)$ for all $x$ in the domain. $f\succeq g$ is similarly defined.

We say an algorithm $M$ is $f$-differentially private if for every two neighboring databases $D,D^{\prime}$, we have $T(M(D)||M(D^{\prime}))\succeq f$.

If $M$ satisfies $f$-DP where $f$ is symmetric (i.e., $f^{-1}=f$). Let $\alpha^{*}$ be such that $f(\alpha^{*})=\alpha^{*}$. Then $M$ satisfies $(\varepsilon(\alpha),\delta(\alpha))$-DP for every $0\leq\alpha\leq\alpha^{*}$ where:

So the tangent to $f$ at $\alpha$ has slope $-\exp(\varepsilon(\alpha))$ and $y$-intercept $1-\delta(\alpha)$ (see Figure 5).

Let $X,Y$ be two random variables supported on $A$ and let $M:A\to B$ is some randomized function, then $T(X||Y)\preceq T(M(X)||M(Y)).$

Let $(X_{1},Y_{1})$ and $(X_{2},Y_{2})$ be pairs of random variables such that $X_{1}|_{Y_{1}=y}$ has the same distribution as $X_{2}|_{Y_{2}=y}$ for all $y$. Then $T(X_{1},Y_{1}||X_{2},Y_{2})=T(Y_{1}||Y_{2}).$

By post-processing (Proposition 4.2), $T(X_{1},Y_{1}||X_{2},Y_{2})\preceq T(Y_{1}||Y_{2}).$ Let $X(y)$ be a random variable which has the distribution of $X_{1}|_{Y_{1}=y}$ and $X_{2}|_{Y_{2}=y}$. Let $M(y)=(X(y),y).$ Then $M(Y_{1})=(X_{1},Y_{1})$ and $M(Y_{2})=(X_{2},Y_{2})$. Therefore, by post-processing (Proposition 4.2), we have the inequality in the other direction. ∎

Let $X_{1},X_{2},\dots,X_{m}$ be independent random variables and let $Y_{1},Y_{2},\dots,Y_{m}$ be independent random variables. Then

where $\otimes$ is a commutative, associative operation on functions from $\to.$

We will the need the following proposition which explains how subsampling affects the privacy curve.

Though Eqn (1) defining the tradeoff curve requires us to take an infimum over a large class of tests, Neyman-Pearson lemma gives a very simple form for the optimal tests to use.

Let $P,Q$ be two continuous distributions over some domain $X.$ The type I error vs type II error tradeoff function between $P$ and $Q$ is attained by the Neyman-Pearson tests which are a single parameter family of tests of the form $\phi_{t}:X\to$ defined as:

Using the Neyman-Pearson lemma, we will prove the following lemma which is crucial for our privacy analysis.

Let $Z$ be some random variable and let $f=T(Z,N(Z,1)||Z,N(0,1))$. Then $f(\alpha(t))=\beta(t)$ where:

and $\Phi(\cdot)$ is the CDF of standard Gaussian.

Denote $P:=Z\times N(0,1),Q:=Z\times N(Z,1)$. From Neyman-Pearson lemma (Proposition 4.6), the type I/II errors are

We will now prove an other key lemma which is useful for our privacy analysis.

Let $Z,\widetilde{Z}$ be two random variables such that there exists some coupling $(Z,\widetilde{Z})$ with $Z\geq\widetilde{Z}\geq 0.$ Then $T(Z,N(Z,1)||Z,N(0,1))\preceq T(\widetilde{Z},N(\widetilde{Z},1)||\widetilde{Z},N(0,1))$.

We will prove this by post-processing (Proposition 4.2). Define a randomized map

where $\widetilde{z}\sim\widetilde{Z}|_{Z=z}$, i.e., $\widetilde{z}$ is sampled from the conditional distribution of $\widetilde{Z}$ given $Z=z.$ Note that $0\leq\widetilde{z}\leq z$ because the coupling $(Z,\widetilde{Z})$ satisfies $0\leq\widetilde{Z}\leq Z.$ Now it is easy to verify that $M(Z,N(Z,1))=(\widetilde{Z},N(\widetilde{Z},1))$ and $M(Z,N(0,1))=(\widetilde{Z},N(0,1)).$ ∎

2 Proof of privacy for Algorithm 4

We will first analyze the privacy of a crucial subroutine used in Algorithm 4 which is shown in Algorithm 2.

Let $X$ be the output of Algorithm 2 with input $\{g_{0},g_{1},\dots,g_{N}\}$ and let $Y$ be the output of Algorithm 2 with input $\{g_{1},\dots,g_{N}\}$. We want to show that $T(X||Y)\succeq f$. We have

By post-processing property (Proposition 4.2), we have

Because of rotation invariance, $U\cdot\mathcal{N}(0,I_{d})$ has the same distribution as $\mathcal{N}(0,I_{d}).$ So,

The coordinates $(X^{\prime\prime}_{i})_{i\geq 2}$ are independent of each other and $M_{0},X_{1}^{\prime\prime}$. Similarly the coordinates $(Y^{\prime\prime}_{i})_{i\geq 2}$ are also independent of each other and $M_{0},Y_{1}^{\prime\prime}$. Moreover $X^{\prime\prime}_{i}$ and $Y^{\prime\prime}_{i}$ has the same distribution for $i\geq 2.$ Therefore by Proposition 4.4,

Let $\phi(M_{0})=\min\left\{\frac{\left\lVert g_{0}\right\rVert_{2}}{\sigma C},\frac{\left\lVert g_{0}\right\rVert_{2}}{\sigma M_{0}}\right\}$. We can further simplify this using Proposition 4.3 as:

We can simplify $\phi(M_{0})$ further by using the fact that $\frac{\left\lVert g_{0}\right\rVert}{M_{0}}=\left\lVert g_{0}\right\rVert_{2}/\left(\sqrt{\frac{1}{r}\sum_{j=1}^{r}\left\langle g_{0},v_{j}\right\rangle^{2}}\right)$ has the same distribution as $1/\sqrt{\frac{1}{r}\chi^{2}_{r}}$. Therefore $\phi(M_{0})$ has the same distribution as

Therefore, this proves that $T(X||Y)\succeq T(Z_{r},\mathcal{N}(Z_{r}/\sigma,1)||Z_{r},\mathcal{N}(0,1))$ where $Z_{r}=\frac{1}{\sqrt{\frac{1}{r}\chi^{2}_{r}}}.$ The parametrization follows from Lemma 4.1. ∎

Algorithm 1 can be thought of as adaptive composition of $T$ iterations of Algorithm 2, but where the inputs to the Algorithm 2 in each iteration is subsampled from the entire input with sampling probability $p=B/N$. And we already showed in Lemma 4.3 that Algorithm 2 satisfies $f$-DP with $f$ as claimed. The rest of the proof is very similar to Theorem 3 in Bu et al. (2019) which itself builds on a similar theorem in Dong et al. (2019). It proceeds by applying Proposition 4.5 to understand the effect of subsampling and an adaptive version of the composition in Proposition 4.4 to compose the privacy curves in all the $T$ iterations. ∎

One could hope to use the central limit theorem for composition from Dong et al. (2019); Bu et al. (2019) to find an approximate closed form expression for the final privacy curve. Unfortunately, these central limit theorems do not apply in our setting.$\chi^{2}(f)$ diverges Instead, we numerically compute the final privacy curve obtained in Theorem 4.1 making use of Lemma 4.1.

3 Effect of JL dimension on privacy

Since the per-sample gradient norm estimations get more accurate with JL dimension, it is clear that the privacy of DP-SGD-JL should converge to that of DP-SGD-Vanilla for large JL dimension. We also observe that privacy parameter $\varepsilon$ is monotonically decreasing with increasing JL dimension and eventually converges to the $\varepsilon$ for DP-SGD-Vanilla. This can be see from Figure 3.

Acknowledgements

We thank Sergey Yekhanin for his constant support and encouragement during this work. We also thank Lukas Wutschitz and Osman Ramadan for helpful discussions. Finally, we thank the amazing open source community of TensorFlow for their quick response in fixing bugs which was crucial for our experiments (TFissue (43449)).

References

Appendix A DP-SGD and DP-Adam-JL

For completeness, we provide pseudo-code for DP-SGD and DP-Adam-JL used in our experiments. DP-Adam-JL satisfies exactly the same privacy bounds as DP-SGD-JL.