Fast and Memory Efficient Differentially Private-SGD via JL Projections
Authors: Zhiqi Bu
Sivakanth Gopi
Janardhan Kulkarni
Yin Tat Lee
Judy Hanwen Shen
Uthaipon Tantipongpipat
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Deep Learning
JL Projections
Per-sample gradients

Abstract: Differentially Private-SGD (DP-SGD) of Abadi et al. and its variations are the only known algorithms for private training of large scale neural networks. This algorithm requires computation of per-sample gradients norms which is extremely slow and memory intensive in practice. In this paper, we present a new framework to design differentially private optimizers called DP-SGD-JL and DP-Adam-JL. Our approach uses Johnson–Lindenstrauss (JL) projections to quickly approximate the per-sample gradient norms without exactly computing them, thus making the training time and memory requirements of our optimizers closer to that of their non-DP versions. Unlike previous attempts to make DP-SGD faster which work only on a subset of network architectures or use compiler techniques, we propose an algorithmic solution which works for any network in a black-box manner which is the main contribution of this paper. To illustrate this, on IMDb dataset, we train a Recurrent Neural Network (RNN) to achieve good privacy-vs-accuracy tradeoff, while being significantly faster than DP-SGD and with a similar memory footprint as non-private SGD. 

Fast and Memory Efficient Differentially Private-SGD via JL Projections*
Zhiqi Bu
Sivakanth Gopi Microsoft Research s sigop pompimmiccm crosoft. com
Janardhan Kulkarni Microsoft Research j jakul @mi @microsoft, com
University of Pennsylvania zbu@sas. upenn. edu
Yin Tat Lee
Judy Hanwen Shen Stanford University jhshen@stanford. edu
Uthaipon Tantipongpipat
University of Washington yintat@ur.cc edu
Twitter uthaipon@gmail.com com
Abstract
Differentially Private-SGD (DP-SGD) of (ACG+16) and its variations the only known algorithms for private training of large scale neural networks. This algorithm requires computation per-sample gradients norms which is extremely slow and memory intensive in practice. In this paper, we present new framework design differentially private optimizers called DP-SGD-JL and DP-Adam-JL. Our approach uses
(JL) projections to quickly approximate the per-sample gradient norms without exactly computing them, thus making the training time and memory requirements of our optimizers closer to that of their non-DP versions. Unlike previous attempts make DP-SGD faster which work only on subset of network architectures or use compiler techniques, we propose an algorithmic solution which works for any network a black-box manner which is the main contribution of this paper. To illustrate this, on IMDb dataset, we train a Recurrent Neural Network (RNN) to achieve good privacy-vs wwwracy-s-accurayy tradeoff, while being significantly faster than DP-SGD and with similar memory footprint as non non-privart private SGD.
1 Introduction
Over the past decade, machine learning algorithms based on (deep) neural architectures have lead to revolution in applications such as computer vision, speech recognition and natural language processing (NLP). 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 email data of users [CLB+19) DBS19, who may be left vulnerable personal information is revealed. This could happen, for example, when model generates sentence or predicts word that can potentially reveal private information users in the training set. Many studies have shown successful membership inference attacks deep learning models [SSSS17] CLE 19]. Indeed, in recent work, neural networks is both commonplace and hard prevent. Such memorization is not due overtraining (T.99 CLE+19) and ad hoc techniques such as early-stopping, dropout etc., do not prevent the risk of privacy violations. Moreover, (Fel20) shows that memorization in fact necessary, provably, for some learning tasks. Thus, prevent unintended privacy breaches one needs a principled approach for private training of deep learning
(CEE* 19] show that "unintended memorization"
Author ordering alphabetical. Work done when the first and the last two authors were interns at Algorithms group, Microsoft Research Redmond.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

models. In this paper we study training neural networks with differential privacy, a mathematically rigorous notion of privacy introduced in the seminal work of [DMNS06]. and focus on user level privacy.
Definition 1.1 ((E, 8)-D), We say that an algorithm M is (E, 6P if for any two neighboring databases D, D' and any subset S of outputs, we have (D) S] S e" (D'M E S] + 6.
Besides being provable privacy notion, it has been shown that deep learning models trained with DP protect against Ieakage of sensitive information; we refer the readers to [CLE* 19 ACG* 16 for more details.
ACG 16) introduced a differentially private In a highly influential line of work, [SCS33 BST14
version of stochastic gradient descent (DP-SGD) for training deep learning models, and showed that is possible to achieve reasonable accuracy-vs -s-pivvacy tradeoff' on common benchmarks such as MNIST and CIFARIO 10. Since then, there has been a vast body of work building and extending
the DP-SGD algorithm: we refer the readers to [MRZZ8 BDLST9) 19, CLE 19 TAM19, AMR 20 ZWB20 CWH20 BKM f 20). The DP-SGD and its variations such as DP-Adam differ from their non-private counter parts in two crucial ways:
In each iteration of DP-SGD, we clip each per-sample gradient to have f2-norm most some fixed parameter C. This step ensures that the sensitivity of the average gradient is bounded, which is crucial for privacy analysis. Computing the norms of per-sample gradients the most expensive step in the algorithm. Efficient implementations of backpropagation such as in TensorFlow and PyTorch only maintain the average of per- sample gradients across a batch by default. Therefore, getting the norm of each per-sample gradient requires significantly more time and memory.
Gradient Clipping:
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 1A then follows from 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 [M Tighter and accurate privacy accountants based on the notion of privacy loss random variables were given in [JH20 KJPH21].
While DP-SGD has been shown to achieve reasonable accuracy-vs-privacy tradeoff [BLSS99 ACG + 16). and arguably is the only known algorithm for training deep neural networks, its use in real-worke deep learning has been rather limited. One of the primary reasons for this is the training time of DP-SGD compared SGD. In DP-SGD, per-sample gradients are computed at 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 inplementations of DP-SGD including [P] and [Opa] (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 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 speedup of L over the usual DP-SGD. Unfortunately, the sensitivity goes up by a factor of L, so we need 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 [Goo] and implemented as the vectorized DP-SGD in .P.. 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 impractical for large models.
Outer product method: This strategy was proposed by [ooo15) for fully-connected net- works and later generalized by (RMT19) to include convolutional layers. The norms of per-sample gradients are computed exactly using outer products between the activations and
2

---

backpropagated gradients across adjacent layers. In very recent work, [LK21] 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 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 [SVK20].
Compiler Optimization: A completely different approach towards mitigating the problem suggested by (SVK20). They showed that by exploiting language primitives, such as vectorization, just-in-time compilation, and static graph optimization, one can implement juniiiatioonjstt-n-tiiiee
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 [SVK20] are specific these JAX and TensorFlow implementations (as of today) and present non-algorithmic approach to this problem.
Table Summary of different methods for DP training of neural networks
Optimizers
Privacy
Speed
Memory
Generalizability
Non-DP SGD
x
V
DP-SGDD-Vami
x
DP-SGD-Multiple
v
DP-SGD-Outer
V
X
X
JAX
DP-SGD-JL
As summarized in Table L 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.
1.1 Our Contributions and Techniques
The main idea of our algorithm is approximate the per-sample gradient norms instead of computing them exactly. l2 norm of a vector; simply project the vector onto a uniformly random direction, the length of the projection (scaled appropriately) is a good approximation to the 22-norm of the vector. By doing more such projections and averaging, we get even better approximation to the true fn-nrmm. Moreover, there is an efficient way to obtain such projections using forward-mode auto-differentiation or Jacobian- vector product (jvp) (see Section 2.1 for details). jvp can be calculated during the forward pass making it very efficient. Since this makes the sensitiviry itself a random variable, the privacy analysis significantly harder than the traditional DP-SGD. Moreover the Moments Accountant and related Renyi DP Accountant are not applicable to analyze the privacy of our algorithm since the associated privacy loss random variables have unbounded moments. Instead, we convolve the privacy loss distributions using Fast Fourier Transform (FFT) as done in [JH200]
(JL) projections provide a convenient way to approximate the
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-accrray tradeoff achieved by our algorithms is comparable to the existing state-of-the-art DP-aloorithms.
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 crucial for achieving good privacy-vs-accurae tradeoffs) without resorting to gradient accumulation. This also improves the running time of training. This because we never need to calculate (and store) all the per-sample gradients simultancously, whereas DP-SGD will need to store all the per-sample gradients simultaneously.
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.
3

---

non
0.9
DF-Adam-Vanills (TFP)
Adam-jLL
Figure 1: Performance of various al- gorithms training an RNN on IMDb dataset using batch size of 256. The privacy parameter is color coded for 10-6, In DP-Adam-JLr, refers to the JL dimension, i.e., the num- ber of JL projections used to approxi- mate per-sample gradient norms. DP- Adam- Mann-anilla (TFP) implemen- tation of DP-Adam in TP library.
Test Accuracy
DP- Adam-jL20
0.8
DP-Adam-JL30
30
0.7
25
20
10
0.5
10a
10a
10a
10a
Time (sec)
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 I our algorithms significantly faster than current implementations of DP-SGD while achieving similar crivacy-vs-accumg tradeoff.
Our algorithms introduce a new knob, the dimension JL-projection, which allows us to do 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 increase in privacy budget.
Our experiments show that although the privacy bounds 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 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) 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-Vanilla.
almost
2 DP-SGD-JL Algorithm
In this section we describe our new differentially private optimizers. We will first present DP-SGD-JL, and DP-Adam-Il follows in the same lines and is presented in the Supplementary Material. We begin with an introduction "Jacobian-vector product" (j)p) which is crucial for our algorithm.
2.1 Jacobian-vector product (jvp)
Given a function f Rd > R, the gradient f with respect to 0, denoted by VeS.
[a 0s 01) 00, 002"
Vof
00
Let F F: of + Rh be some function given by F(0) (F), F2()), ..... Fr. (0)). The Jacobian of F(0), denoted by F, is the matrix:
VaFi
OF 08,
Vo
Jaj
F
Most auto-differentiation packages allow for calculating the vector-Jacobian product (vjp) given by n V = En u, V.F. for any e m efficiently using reverse-mode auto-differentiation. which

---

is the familiar 'backpropagatton
One can also calculate the Jacobian-vector vector product (jvp) given by
Voli. u) VoF2, v)
V Fo=
(VoEms t)
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 [BPRST7] for more details. jvp is implemented using forward-mon -ood dittodiiferenttition the recent TensorFlow versions Unfortunately, Py PyTorch doesn't 't have an implementation of forward- mode suttoddiffrenntation. Instead, one can compute jvp using two calls to vjp. this is called the "double vip trick' (see [Tow) Define G(a) = a VV which can be calculated using vip. Note that V.G (VoF)*. Now we can use vjp again on G calculate jvp as
uu)"
In our experiments, we use the efficient implementation of jvp in TensorFlow compute the Jacobian-vector products as the double vjp trick is few times slower.
2.2 Algorithm
The main idea of our algorithm to approx- imate æ--norms of per-sample gradient norms instead of computing them exactly. And the key tool to achieve this is JL projections.
3.0
F1
Proposition 2.1 (JL projections). Let y E Rd be any vector. U1, U25-..., Vr NO, Ia) are independent standard Gaussian vectors, then
2.5
~ 10
2.0
M, Ei= (v. has the same distri-
1.
bution as 11vll2 V x In particular E[M?) llv12.
0.5
0.0
1.0
1.5
2.5
Proof. By the properties of the standard Gaus- sian distribution, (y, 0z) has the distribution of
/ /1x2 for different r.
W 1). And (y, vi) are independent for
Figure Distribution
1 r. Therefore Em (y. vz) has the same distribution as |1y11 1 x
As shown in Figure as r grows larger, the distribution of v x concentrates more around and therefore M, becomes better estimate of ||ı|| Using jvp, we can compute projections of per-sample gradients to standard Gaussian vectors quickly and therefore get good approximations to their norms. This is the main idea of DP-SGD-JL (Algorithm IT.
2.3 Privacy Analysis
Let us first recall the privacy analysis of DP-SGD in Abadi et al. [ACG+16), which consists of three main arguments: 1) First, they show that each step of the DP-SGD algorithm is differentially private,
"In PyTorch, u V can calculated as autograd, grad (,, .0....dd....ooo outputs=u). In TensorFlow, this is tf. GradientTape () -graddient (F, A, woptput_ggrddeentteeeeeeeeeeeeee 'Supported fE-nightl222444 2.4.0.dev202009244 JAX also has an implementation of jvp.
tf. autodiff Pow.raaaaaaacccccctttoooo (v)
implementation of jvp using the double vjp trick exists and be invoked as torch.autograd aut.aaad. www.oogrr..ffuntiiiioeee wwn.ciionaaltt (F, inputs=v).
'In Pytorch, torch.
2 is the chi-square distribution with degrees of freedom which is the distribution of sum of squares of standard Gaussians.
5

---

Algorithm 1: Differentially private SGD using JL projections (DP-SGD-JL)
Input: Examples (#1, 22,,..,, FNN.. ). loss function [()) = E [C0 xx)], initialization 0o.
Parameters: number of iterations T' learning rates (171 ................................ ( noise scale o, batch size B, clipping norms (Ci, C2,..., CT), number of JL projections r. for f
do Sample S {x1. Xy..... .B) C f01. P2........ f2 INt uniformly at random.; Define F(0) (C(0; X1), X2); ( (B):
Sample U1, U2, ...,...,,,,.. Up f- (0, Ia) (where E R:);
// JL projections to estimate per sample gradient norm
for j t do (Pij, ........ PB,) VoF(O1-1)-or
// Computed using ivp
// Note that P. = (VoL(te-1;)))))) x.),
for 1o B do Set Mc, -0-VV-E 1
// M, is estimate for [|Vo(()
1/ Scale the losses to implicitly clip per-sample gradients Define [(0)- :/ EiEB min(1, M, (i);
1/ VoC(0,-1) is the average of clipped gradients, computed by one backprop
// Add noise to VoL(0--1,, the average of clipped gradients 9. -V c.C. Ta);
B
Update 91 + 01-1 m9s Output: O, 01, ..,....,0pp
which follows from the simple observation that norm of the each gradient can be at most C' due to clipping and so each step is Gaussian mechanism. 2) Next, they observe that each mini-batch is a random sample of the dataset, hence can appeal to the privacy amplification by subsampling. 3) Finally, they do a composition across all the iterations of the DP-SGD algorithm. However, existing works at that time did not give tight analysis of the privacy loss in steps 2 and 3, hence (ACG* 16 invented the Moments Accountant (MA) technique.
Unfortunately, analysis of our algorithm is significantly more involved than that of [ACG+ as all the above 3 steps pose new technical challenges. First note that unlike DP-SGD, in our algorithm, we only have rough estimate of the norm of cach gradient; hence, the sensitivity of the gradients is a random variable. This means that the each iteration not a Gaussian mechanism. The Moments Accountant (and the closely related RDP Accountant) cannot be used compute the privacy loss of the composition because the privacy loss random variables for our algorithms do not have exponential moments (for JL dimension r, only moments r/2 exist).
To overcome these challenges, we use the notion of privacy loss random variables (PRVs) DR16 MM18 KJH20 GLW21]. In particular, we use the PRV Accountant from GLW21I Define 8(X) X(XJY) ()) = Pr(Y > E] - ef Pr(X > e). For any DP algorithm M, there exists random variables
(X, Y), called its privacy loss random variables (PRVs) such that the privacy curve of M is given by 8(X YY) i..., M satisfics (a, (({))() -DP for every E.
The following theorem shows lower bound on the privacy curve of each iteration of the DP-SGD-JL algorithm, which is the main technical contribution of this paper.
Theorem 2.2. Let Zy
Tixi where X2 is the chi-square distribution with degrees of freedom.
Each iteration of DP-SGD-JL (before subsampling) satisfies (e, ((,8((]]))))) (()))() where
x=N (- 2 2,,)
Z 22 and Y = ZZ
z
2
From the above theorem, we can prove that the privacy curve of each iteration behaves like 5(e) ~ I for large e. The proof of Theorem 2.2 can be found in the supplementary material. gr7z
If My,.... M2 are DP algorithms such that M, has PRVs (X,, Y,), then the composition of
M1, M2. ... My has PRVs given by (Eh, X1, > Y)) GLW21] If mechanism M has PRVs

---

given by (X, Y), then the subsampled mechanism M o Sample, where Sample, samples p fraction of the data uniformly at random has PRVs given by (Xp, Xp) where:
X, log(1 + p(e* - 1)),
logg(1 + p(e" - 1)) w.p.
Y =
log(1 + +pee* 1)) w.p.
See GLW21] for proof of this fact. Combining these facts about PRVs with Theorem 2.2 we can compute the privacy curve of the DP-SGD-JL algorithm.
Theorem 2.3. Let B/N where B is the batch size and N is the total number of samples. Then DP-SGD-JL run for T iterations satisfies (e, -DD where
T
T
Σ
X
Σ
Yi
P
where X1 X2
p1. ......., are iid copies of Xp and V1 YP yp,....
Y are iid copies Y Xp and Yp
are given by (2 and X, are given by 7
Finally, we numerically compute the distribution of Σ X3 by using Fast Fourier Transform (FFT)
to convolve the distributions of Xp with itself T times. The distribution of Σ Yū is similarly calculated, see [GLW2T] on how to approximate these distributions.
Effect of JL dimension on privacy Figure shows how the JL dimension effects the privacy curve of DP-SGD-JL. As JL dimension increases, DP-SGD-JL becomes more and more private and converges to the privacy of DP-SGD.
Experiments
In this section, demonstrate experimentally that compared existing implementations of DP-SGD with exact per-sample gradient clipping, our optimizers have significant advantages in speed and memory cost while achieving comparable securacy-vs-privane perform well on 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:
tradeoff. Moreover algorithms
1. Our algorithm is significantly faster compared per-sample gradient computations and works for any network in a black-box way.
2. Memory footprint of our algorithm is roughly same as non non-private SGD.
3. 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 search.
In the following, we write 'nonDP-SGDD for the standard non-private SGD and DD-SGGD Vanilla' for the implementation of DP-SGD in [TP, nonDP-Adam and DP-Adam- -d---ml-Vanilla are similarly defined. We use Tensorflow and (TP) for all our experiments because (Opa) does not support arbitrary network architectures 6 Moreover Tensorflow has an efficient implementation of j jvp while Py Torch doesn't t.
Notation: We denote the noise multiplier as clipping norm C. batch size as B, learning rate as and the number of epochs as E = -BTN. We fix the privacy parameter 8 = 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 large number of epochs. The code for our experiments available in the supplementary material.
3.1 Training an LSTM model IMDb dataset
The goal of these experiments is to demonstrate first strength our algorithm: it is significantly faster than per-sample gradient computations and works for any network in a black-box way. We
'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 GRU are not supported (see Opacus).
7

---

Non-Di DP DP- Vanilla
DL(I
DP.J((5)
DP-JL(IO)
DP JL(30)
12
19317
41
128
243
675
Table 2: Seconds per epoch to train our RNN with 598,274 parameters and 25,000 training samples.
We set 31 = 0.9, B2 = 0.999, a = 0.6, C = 1, L. 256, = 0.001, E = 15. We use Adam as the optimizer.
epsilon
32-
Figure 3: Privacy curves for various algorithms while training the LSTM model IMDb dataset. Here 8 10-3 is fixed.
DP-adam(L10
DP-Adam/L20
23
DP L33
13-
epochs
train a bidirectional LSTM with embedding layer on the IMDb dataset for sentiment analysis. We remark that simpler networks not based on RNNs can achieve good accuracy-vs vs-privacy tradeoff as shown in [BLLSI9 and [Pyt]. However, LSTM models based RNN architectures are widely used in NLP applications. and hence efficient private training of such models remains an important challenge in this area [MRTZI8]. Moreover, we noted in the introduction, extensions of outer product trick to bidirectional LSTMs as described in [LK2 are significantly more complicated, and require considerable effort implement. Since authors of (LK21) did not provide the code, we are unable to compare the improvements. Moreover, as also noted in [LK21], 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 LSTM" as in the [Ten] 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, referred simply as DP-JL in the table, algorithms with smaller values of dimension are significantly faster than DP-Adam- Vanilla. We also notice a linear increase in running-time with incresing JL dimension. However, as we note in the Figure privacy guarantees of DP-Adam-JL algorithm with smaller values of JL dimension are considerably worse than DP-Adam-Vanile other hand, DP- -30mmmm-J--33) is 30x faster than DP-Adam- Vanilla while achieving similar privacy guarantees as DP-Adam- -a-aall-Vanilla. When allowed to train for sufficient number of epochs, 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 (sec introduction), where we plot the privacy values using a color plot.
privacy
On the
Remark 3.1. 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-Vee Vanilla, by setting the batch size equal to 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 [TPj. Indeed the naive implementation of D--m-am- Vanilla in tensorflow using gradient accumulation takes about 4000 seconds per epoch for the same batch size.
3.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 cannot use CuDNNLSTM and instead use LSTM for the following reason. When using CuDNNLSTM (and on GPU), we observe significant speedup compared to LSTM, but the accuracy is invalid and we further incur a LookupError when computing jvp.
8

---

Test Accuracy
0.90
Figure 4: Behavior of various private algorithms for MNIST dataset. The test accuracy is averaged over 25 runs. Note that the DP-SGDD-JL20 curve is nearly overlapping with the curve for DP-SGD- Vanilla.
0.85
0.80
nenDP
DP.SGD.
DP Vanilas
DP-SGD-JL10
DF SGDyLL
DP.SCD/L220
5
15
20
25
epochs
we compare the largest batch size each algorithm can handle without running out of memory. is known that to achieve good privacy-vs-accurady tradcoffs for DP-SGD, we need to use large batch sizes 16) One way to support large batch sizes via gradient accumulation; however, this has the disadvantage that one loses parallelism, which in turns leads to slower run times. Hence memory footprint algorithms also indirectly affects the training time.
We compare our JL algorithms with the implementation of DP-SGD-Vanilla in [TP]. We train convolutional neural network from (T) tutorial on MNIST dataset, which has 60,000 training samples
& As we can see from Table 3 (left). DP-SGD-JL algorithm and nonDP-SGD can both run with the maximum possible batch size of 60,000 whereas DP-SGD-Vamee 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 TP tutorial with dense layers to blowup the model size to 17,146,933 44,93,888086 parameters, and repeat the experiment. As we see from Table (rightt, the largest batch size supported by DPSGD-JL(30) is only 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 batch size of 100.
nonDP-SGD
60,000
nonDP-SGD
52,000
DP-SGD- Vanilla
512
DP-SGD- Vanilla
100
DP-SGD-JL(IO)
60,000
DP-SGD-IL(IO)
28,000
DP (3D-)
60,000
DP-SGD-JL(30)
25,000
Table 3: The left table shows the maximum batch size supported by various algorithms CNN with 26,010 parameters trained on MNIST with 60,000 training samples. The right table shows the maximum batch size supported by various algorithms on CNN with 17,146,938 parameters trained on MNIST with 60,000 training samples. Training done on one Tesla P100 16GB GPU.
The above experiments also give 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 very beginning but as the batch size becomes larger the running time gets worse, and soon after runs out of memory.
running time gets better with batch size in the
3.3 Using DP-SGD-JL for hyper-parameter search
As we saw in 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(I) about 470x faster and DP-SGD-JLL prove for these algorithms are considerably worse than DP-Adam- Vanilla. Despite this drawback. observe that behavior of DP-SGD. even for small JL dimension is very close to that of DP- Adam- Vanilla. Figure plots the accuracy vs epochs for various algorithms training a CNN from TP tutorial on MNIST dataset. We observe that as JI. dimension increases, the accuracy epoch
is about 150x faster. However, unfortunately, the privacy bounds can
We use the implementation and the network from mnist_ www.ddpppsddoooooo tutoriall aitooraalkeersspppp

---

curve quickly converges to that of DP-SGD- SP--DD-Vanilla, DP-SGD-JL(33) is already very similar to DP- KGD-Vanille and DP-SGD-JL(20) 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 DD-SGD-VVniill Thus we believe that DP-SGID-JL(3) or DP-SGD-JIL(5) are good candidates for experimentation and hyper-parameter tuning during private training, since their behavior is almost identical to that of DP-SGD-Vaniin while being orders magnitude faster.
Acknowledgments and Disclosure of Funding
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
References
[ACG+ 16] Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308 318, 2016.
[AMR*20) Sean Augenstein, H. Brendan McMahan, Daniel Ramage, Swaroop Ramaswamy, Peter Kairouz, Mingqing Chen, Rajiv Mathews, and Blaise Aguera Arcas. Generative models for effective ML private, decentralized datasets. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[BDLS19] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie Su. Deep learning with gaussian differential privacy, 2019,
[BKM+20] Borja Balle, Peter Kairouz, H. Brendan McMahan, Om Thakkar, and Abhradeep Thakurta. Privacy amplification via random check-ins. CoRR, 24422007706665. 2020.
[BPRS17] Atilım Günes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jef- frey Mark Siskind. Automatic differentiation in machine learning: survey. The Journal of Machine Learning Research, (8()):5595-6637, 2017.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473, IEEE, 2014.
[CLB + 19] Mia Xu Chen, Benjamin N. Lee, Gagan Bansal, Yuan Cao, Shuyuan Zhang, Justin Lu, Jackie Tsay, Yinan Wang, Andrew M. Dai, Zhifeng Chen, Timothy Sohn, and Yonghui Wu. Gmail smart compose: Real-time assisted writing. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis, editors, Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 2287-2295. ACM, 2019.
[CLE+19] Nicholas Carlini, Chang Liu, Úlfar Frlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th (USENIX) Security Symposium ([USENIX) Security /9), pages 267-284, 2019.
[CWH20] Xiangyi Chen, Zhiwei Steven Wu, and Mingyi Hong. Understanding gradient clipping in private SGD: A geometric perspective. CoRR, abs/2006.15429, 2020.
[DBS19] Budhaditya Deb, Peter Bailey, and Milad Shokouhi. Diversifying reply suggestions using matching-conditionn variational autoencoder. In Proceedings of the 2019 Conference of the North Americun Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Industry Pupers), Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
10

---

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.
[DR16] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.0I 00816000.888,,.0 2016.
[DRS19] Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy, 2019.
[Fel20] Vitaly Feldman. Does learning require memorization? short tale about long tail. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 954-959, ACM, 2020.
[GLW21] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differen- tial privacy. arXiv preprint arXiv:2106.02846. 2021.
[Goo] Ian Goodfellow.
issuecomment 290997283
[Goo15] Ian Goodfellow. Efficient per-example gradient computations.
arXiv preprint
arXiv:1510.01799, 2015.
[KJH20] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pages 2560-2569. PMLR, 2020.
[KJPH21] Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft. In International Conference Artificial Intelligence and Statistics, pages 3358-3366 3366. PMLR, 2021.
[LK21] Jaewoo Lee and Daniel Kifer. Scaling up differentially private deep learning with fast per-example gradient clipping. Proceedings on Privacy Enhancing Technologies, 2021()):28-144,, 2021.
[Mir17] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[MM18] Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference Computer and Communications Security, pages 247-264, 2018
[MRTZ18] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning dif- ferentially private recurrent language models. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.net, 2018. 2018.
[Opa]
Library Opacus.
gi rithub. com cotm://tccboooreeeeeccc/grtoooor
[Pyt] Team Pytorch. Dp training on imdb.
htaps:///ithbbs http:///oo////iiooooooooooooooor README. md
[RMT19] Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computations in convolutional neural networks. arXiv preprint arXiv: 2019.
[SCS13] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248. IEEE, 2013.

---

[SSSS17] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. 2017 IEEE Symposium on Security and Privacy (SP), pages 3-18. IEEE, 2017.
[SVK20] Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differ- entially private sgd via just-in-time compilation and vectorization. arXiv preprint arXiv:2010.0906 2020.
[TAM19] Om Thakkar, Galen Andrew, and H. Brendan McMahan. Differentially private learning with adaptive clipping. CoRR, abs/1905.03871, 2019.
[Ten] Team Tensorflow. Text classification with an mn.
[TFi] TFissue43449 Fast per example gradient support.
[TLL95] Igor V. Tetko, David J. Livingstone, and Alexander I. Luik. Neural network studies, 1. comparison of overfitting and overtraining. Chem. Inf. Comput. Sci., 35(5):826-833 -3,-833, 1995.
[Tow]
Jamie Townsend. A new trick for calculating Jacobian vector products. httpa://j-towns http:///......////1///////////// http:////////--e-ttteeeee html
[TP] Library Tensorflow Privacy.
github... conn/teassofffooo//rrryyy
[ZWB200] Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private SGD with gradient subspace identification. CoRR, abs/2007.03813. 2020.
12


Reviews:
[{"review_id": "qVChB9KV4x", "reviewer": "Reviewer_3iUF", "summary": "Differentially private stochastic gradient descent requires clipping the gradient computed on each example before aggregation. That is, we compute the 2-norm of the gradient vector and, if it is too large, we scale it down. Surprisingly, this step entails a significant computational overhead relative to non-private stochastic gradient descent.\nThe reasons for this slowdown are not entirely clear to me. It seems to be a software issue deep in the bowels of TensorFlow and PyTorch -- somewhere between the Python and the Hardware this operation is poorly optimized.\n\nThis paper proposes to alleviate the problem by performing approximate, rather than exact clipping. Specifically, a Johnson-Lindenstrauss sketch is used to approximate the 2-norm of the vector instead of exactly computing it. This JL approximation can be computed more efficiently than the exact norm. However, there is a tradeoff between speed and approximation quality as we can alter the dimension of the JL sketch.\n\nTechnically, the most involved aspect of this work is the privacy analysis. Since the gradients are only approximately bounded, we cannot apply the usual analysis. This algorithm does not satisfy Renyi differential privacy as there is heavy-tailed privacy loss due to the possibility of drastically underestimating the norm. Instead an entirely new analysis is required based on the recent Fourier accounting approach.\n\nExperimental results demonstrate that there is a significant improvement in runtime. However, the privacy parameters also degrade significantly.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper presents a novel approach to accelerating differentially private deep learning. This is accompanied by a thorough theoretical privacy analysis and an experimental evaluation. \n\nComputation is a significant bottleneck in practical implementations of differentially private deep learning. Thus the faster approach in this paper is valuable. However, it comes at the expense of a blowup in the privacy parameters. This tradeoff may be acceptable in some circumstances, but unacceptable in others. In any case, it is a good addition to our toolbox.\n\nOne thing to note is that the problem being solved is, as far as I know, a software issue, rather than a fundamental limitation. Thus the value of the proposed solution may disappear with a future version of the software.\n\n\nA low level comment: Differentially private stochastic gradient descent predates the work of Abadi et al. I believe it was first introduced by Bassily, Smith, & Thakurta in 2014. Abadi et al. however were the first to do it in a practical setting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "iXHwrj9bOSa", "reviewer": "Reviewer_GLcg", "summary": "This paper considers the computation and memory cost problem introduced by per-sample clipping in private gradient descent algorithms. To accelerate per-sample clipping, this paper proposed a new framework using JL projections to estimate the per-sample gradient norms. The authors provide rigorous differential privacy analysis of the proposed framework. They also give empirical evaluations of the proposed algorithms in terms of privacy, utility, and computation time.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n \n- This idea of using JL projections to estimate the gradient norms and using Jacobian-vector product to accelerate computation is new. The framework is potentially useful for training large-scale neural networks. \n- This paper is technically sound. The authors discussed that each iteration of the proposed algorithm is not a Gaussian mechanism due to the estimated clipping norm. Thus, they provided rigorous privacy analysis for the new framework. \n- This paper is well written and clearly presented.\n\nWeaknesses and some discussion: \n- The main concern is that the privacy bound provided in this paper of this framework is larger than that of the standard differentially private SGD algorithms as shown in Figure 1. I am wondering if the privacy bound or the numeric method to compute privacy can be improved?\n\n- In Figure 3, If we further increase the projection dimension r to match the privacy level of DP-Adam, how does the computation time compare with that of DP-Adam/DP-SGD? Will DP-Adam-JL still require less computation time than DP-Adam?\n \n\nOverall, I think this paper is above borderline. The significance can be improved by improving the privacy bound of the proposed framework, so I recommend borderline acceptance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "fQKucPG9921", "reviewer": "Reviewer_SDe9", "summary": "This paper presents a new algorithm to approximate per-sample gradient norms in DP-SGD using Johnson-Lindenstrauss (JL) projection. Experimental results were conducted on IMDb and MNIST datasets showing that the proposed approach is faster with the same memory footprint as the vanilla DP-SGD. \n\n", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Approximating the per-sample gradient norm is new and interesting. The paper presentation is clear and easy to understand. However, there is room for improvement.\nFigure 3 shows that the proposed approach consumes an excessive privacy budget epsilon compared with the vanilla DP-SGD. In the low-value regime of privacy budget (tight privacy protection), it is unclear how the proposed approach can advance the vanilla DP-SGD. This is quite critical in practice since the trade-off between model utility and privacy loss in the low-value regime of the privacy budget is more significant. From that angle, the contribution of the paper is marginal.\nAn extensive study is needed to show the advantages of the proposed approach clearly. Larger datasets are needed since it is hard to draw a convincing conclusion only using the MNIST dataset.\nQuestion: Whether all the algorithms in Figure 4 consume the same privacy budget given the same number of epochs? It appears that they do not consume the same privacy budget given the analysis in Figure 3. As a result, the comparison in Figure 4 is unconvincing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper did not discuss limitations and societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "No concern", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "1ib7Rxgpvcb", "reviewer": "Reviewer_occM", "summary": "To accelerate DP-SGD, this paper uses JL projection to approximate the $\\ell_2$ norm of the per-sample gradients, which can be calculated during the forward pass efficiently. Moreover, the privacy analysis requires new techniques (convolving the privacy loss distributions using FFT) since the standard moment accountant cannot be used in this case.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The proposed method does not explicitly compute nor store the per-sample gradients, unlike DP-SGD.\n- The novelty and technical depth of this paper is limited.\n- The experiments show that the accuracy of the proposed method may be worse than DP-SGD (see Figure 3). although much faster.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission makes significant time and memory efficiency improvements for differentially private SGD using random projections, at the cost of a worse privacy/utility tradeoff when compared with vanilla DPSGD as emphasized by one reviewer. The authors gave a compelling rebuttal however that despite this worse tradeoff, DPSGDJL still has value for fast hyperparameter tuning for private training. The contribution of this submission thus seems strong.
Decision: Accept (Poster)