Scaling up Differentially Private Deep Learning with Fast Per-Example Gradient Clipping

Introduction

Machine learning models trained on sensitive datasets, such as medical records, emails, and financial transactions have great value to society but also pose risks to individuals who contributed their information to the training data. Even if the model parameters are not shared, black-box access to the models can leak private information . Differential privacy is a promising framework for mitigating such risks because of its strong mathematical guarantees and because of recent advances in differentially private training of predictive models.

Simple models, such as linear regression and logistic regression, which have convenient mathematical structures (e.g., convexity) and relatively few parameters, have been well-studied in the differentially private literature and many privacy preserving training algorithms have been proposed (e.g., ). These algorithms are generally fast and accurate compared to their non-private counterparts.

However, state-of-the-art prediction results generally come from deep artificial neural networks with millions of parameters. These models are not convex and hence require different fitting algorithms to ensure privacy . In the non-private case, training is generally accomplished using stochastic gradient descent backed by GPU/TPU hardware accelerators that process multiple training records together in a batch. In the privacy-preserving case, the most generally applicable training algorithm is also a variation of stochastic gradient descent . However, its current implementations (e.g., ) are extremely slow because a key step, “per-example gradient clipping”,Essentially, the gradient contribution of each record in a batch must be normalized first (in a nonlinear way), before the contributions are added together. See Section 3 for details. limits the batch-processing capabilities of GPUs/TPUs, resulting in slowdowns of up to two orders of magnitude. This slowdown has a direct impact on differentially-private deep learning research, as it becomes expensive even to experiment with differential privacy and different neural network architectures .

In this paper, we show that most of this slowdown can be avoided. By analyzing how backpropagation computes the gradients, we derive some tricks for fast per-example-gradient clipping that are easy to implement and result in speedups of up to 94x over the naive approach. These methods take advantage of auto-differentiation features of standard deep learning packages (such as TensorFlow and PyTorch ) and do not require any low-level programming (our code consists of Python wrappers around PyTorch layer objects — e.g., a wrapper for fully connected layers, a wrapper for convolutional layers, etc.).

We note that Goodfellow provided a fast per-example gradient clipping method that only applied to fully connected networks. Our results apply to a wider variety of architectures, including convolutional layers, recurrent networks, attention, residual blocks, etc.

In short, our contributions are as follows.

We present methods for efficiently computing per-example gradients for different kinds of deep learning models, achieving a speedup of up to 54x to 94x (depending on the model) compared to naive per-example gradient computation on mini-batches of size 128. This allows hardware-accelerated differentially private training of deep learning models to rival the speed of hardware-accelerated non-private training and thus makes differentially private deep learning possible in practical timeframes.

The proposed methods do not require fundamental changes to GPU parallelization. Instead, they are easy to implement because they take advantage of automatic differentiation capabilities of modern deep learning packages. Our PyTorch wrappers are being prepared for open-source release.

As an application of the proposed framework, we demonstrate how to train (under Rényi differential privacy) a Transformer encoder block , a key component in an architecture that has lead to recent advances in natural language processing.

We perform extensive experiments and empirically show the effectiveness of approach for differentially private training of various kinds of deep neural network models.

The rest of this paper is organized as follows. In Section 2, we define notations and provide background on differential privacy. Building on these concepts, we describe the per-example gradient clipping problem in Section 3. We then discuss related work in Section 4. We present our proposed methods in Section 5, experimental results in Section 6 and conclusions in Section 7.

Preliminaries

In this paper, we use upper-letters (e.g., $W$) to represent matrices, bold-face lower-case (e.g., $\mathbf{x}$) to represent vectors and non-bold lower-case (e.g., $y$) to represent scalars. One exception is that $D$ represents a dataset. Tensors of order 3 or higher (i.e., multidimensional arrays that are indexed by 3 or more variables) are represented in calligraphic font (e.g,. $\mathcal{W}$).

Let $D=\{(\textbf{x}_{1},y_{1}),\ldots,(\textbf{x}_{n},y_{n})\}$ be a set of $n$ records, where $\textbf{x}_{i}\in\mathfrak{X}$ is a feature vector and $y_{i}\in\mathfrak{Y}$ is a target (value we must learn to predict). We say two datasets $D$ and $D^{\prime}$ are neighbors if $D^{\prime}$ can be obtained from $D$ by adding or removing one record and write $D{\sim}D^{\prime}$ to denote this relationship.

Differential privacy is a widely accepted formal privacy definition that requires randomized algorithms (also called mechanisms to process data. The intuition behind it is that the addition/deletion of one record should have very little influence on the output distribution.

Given privacy parameters $\epsilon\geq 0$, $\delta\geq 0$, a randomized mechanism (algorithm) $\mathcal{M}$ satisfies ($\epsilon,\delta$)-differential privacy if for every set $S\subseteq\operatorname{range}(\mathcal{M})$ and for all pairs of neighboring datasets $D{\sim}D^{\prime}$,

The probability only depends to the randomness in $\mathcal{M}$.

The cases $\delta=0$ and $\delta>0$ are respectively referred to as pure and approximate differential privacy.

2 Rényi Differential Privacy

One of the drawbacks of Definition 1 is that accurately tracking privacy loss from multiple noise-infused accesses to the data is difficult. For this reason, most work on differentially private deep learning uses a variant called Rényi Differential Privacy (RDP) to track privacy leakage of an iterative algorithm and then. At the very end, the RDP parameters are converted to the $\epsilon,\delta$ parameters of Definition 1. RDP relies on the concept of Rényi divergence:

Rényi differential privacy requires two parameters: a moment $\alpha$ and a parameter $\epsilon$ that bounds the moment.

Given a privacy parameter $\epsilon\geq 0$ and an $\alpha\in(1,\infty)$, a randomized mechanism $\mathcal{M}$ satisfies $(\alpha,\epsilon)$-Rényi differential privacy (RDP) if for all $D_{1}$ and $D_{2}$ that differ on the value of one record, $\operatorname{\mathfrak{D}}_{\alpha}(\mathcal{M}(D_{1})\;\|\;\mathcal{M}(D_{2}))\leq\epsilon\,.$

While the semantics of RDP are still an area of research, its privacy guarantees are currently being interpreted in terms of $(\epsilon,\delta)$-differential privacy through the following conversion result .

If $\mathcal{M}$ satisfies $(\alpha,\epsilon)$-RDP, it satisfies $(\epsilon^{\prime},\delta^{\prime})$-differential privacy when $\epsilon^{\prime}\geq\epsilon+\frac{\log(1/\delta)}{\alpha-1}$ and $\delta^{\prime}\geq\delta$.

This result implies that $(\alpha,\epsilon)$-RDP can be converted to $(\epsilon^{\prime},\delta^{\prime})$-DP for many different choices of $\epsilon^{\prime}$ and $\delta^{\prime}$. The result can be used in many ways. For example, one may choose a desired $\epsilon^{\prime}$ and set $\delta^{\prime}=e^{-(\epsilon^{\prime}-\epsilon)(\alpha-1)}$, in which case $(\alpha,\epsilon)$-RDP provides more protections than differential privacy with those values of $\epsilon^{\prime}$ and $\delta^{\prime}$. Alternatively, one can pick a $\delta^{\prime}$ and use Lemma 1 to determine the corresponding $\epsilon^{\prime}$.

Building Blocks. One of the simplest methods of creating an algorithm satisfying RDP is called the Gaussian Mechanism. It relies on a concept called $L_{2}$ sensitivity, which measures the largest effect a single record can have on a function. Formally,

Let $q$ be a vector-valued function over datasets. The $L_{2}$ sensitivity of $q$, denoted by $\Delta_{2}(q)$ is defined as $\Delta_{2}(q)=\max_{D{\sim}D^{\prime}}\lVert q(D)-q(D^{\prime})\rVert_{2}\,,$ where the max is over all neighboring pairs.

The Gaussian mechanism for RDP answers a numerical aggregate query $q$ by adding Gaussian noise whose variance depends on the sensitivity of $q$ as follows:

Composition. More complex algorithms for $(\alpha,\epsilon)$-RDP, such as training deep neural networks, can be created by combining together many applications of simpler mechanisms (such as the Gaussian Mechanism) — each one leaks a controlled amount of private information, and the composition theorem explains how to compute the total leakage.

Let $\mathcal{M}_{1},\dots,\mathcal{M}_{k}$ be mechanisms such that each $\mathcal{M}_{i}$ satisfies $(\alpha,\epsilon_{i})$-RDP (that is, the $\alpha$ values are all the same but the $\epsilon$ values can differ). The mechanism that, on input $D$, jointly releases the outputs $\mathcal{M}_{1}(D),\dots,\mathcal{M}_{k}(D)$ satisfies $(\alpha,\sum_{i}\epsilon_{i})$-RDP.

In practice, one keeps track of multiple $\alpha$ values. That is, a mechanism $\mathcal{M}_{1}$ may satisfy $(\alpha_{1},\epsilon_{1})$-RDP, $(\alpha_{2},\epsilon_{2})$-RDP and $(\alpha_{3},\epsilon_{3})$-RDP, while $\mathcal{M}_{2}$ may satisfy $(\alpha_{1},\epsilon^{\prime}_{1})$-RDP, $(\alpha_{2},\epsilon^{\prime}_{2})$-RDP and $(\alpha_{3},\epsilon^{\prime}_{3})$-RDP. The mechanism that releases both of their outputs would satisfy $(\alpha_{1},\epsilon_{1}+\epsilon^{\prime}_{1})$-RDP and also $(\alpha_{2},\epsilon_{2}+\epsilon^{\prime}_{2})$-RDP and $(\alpha_{3},\epsilon_{3}+\epsilon^{\prime}_{3})$-RDP. When converting to $(\epsilon,\delta)$-DP, one applies Lemma 1 to each of these and selects the best $\epsilon,\delta$ values .

Postprocessing Immunity. Another key feature of differential privacy is post-processing immunity. If $\mathcal{M}$ is a mechanism that satisfy $(\alpha,\epsilon)$-RDP (or $(\epsilon^{\prime},\delta^{\prime})$-DP) and $f$ is any algorithm, then the mechanism which, on input $D$, releases $f(\mathcal{M}(D))$, satisfies $(\alpha,\epsilon)$-RDP (or $(\epsilon^{\prime},\delta^{\prime})$-DP) – the privacy parameters do not get worse.

The Problem with Per-Example Gradient Clipping

In this section we briefly describe non-private training of neural networks to explain how GPU mini-batch computation is used to speed up training. We then discuss the most common differentially private deep learning training procedure and explain how its direct implementation loses much of these speed benefits (via a step called gradient clipping). In Section 5 we then explain how to recover the speedup that was lost with a better gradient clipping algorithm.

The function $L$ is called the objective function.

When $M_{\theta}$ is a deep neural network, the above problem is typically solved with an iterative first-order algorithm such as stochastic gradient descent (SGD) or its variants.

2 Mini-batch stochastic gradient descent with privacy.

Abadi et al. addressed this problem by clipping each term in the summation to make sure that no term can get large, even in the worst case. The clipping function has a parameter $c$ (called the clipping threshold) and is defined as follows:

3 The Computational Problem

This approach has several drawbacks. First, it loses the parallelism that GPUs can offer when performing matrix computations. Second, it may result in multiple transfers of data to the GPU (i.e., not taking advantage of bulk transfer capabilities).

Related Work

Deep learning for differential privacy was introduced by Skokri and Shmatikov but required enormous values of the privacy parameters (e.g., $\epsilon$ values in the hundreds or thousands). The first practical approach, which could train deep networks to reasonable accuracy (on the MNIST and CIFAR datasets) with $\epsilon$ values of 10 or less was proposed by Abadi et al. and required the use of gradient clipping and Renyi Differential Privacy (referred to as the Moment Accountant in ).

Followup work relied on this training technique. Also investigated different clipping strategies, such as adaptively changing the clipping threshold or clipping the gradient layer by layer . Specifically, given the global clipping threshold $c$, McMahan et al. clip the gradient of each layer’s parameter using the threshold $c/\sqrt{m}$, where $m$ is the total number of layers. In , the authors extended the idea of per-layer clipping and proposed a joint clipping strategy which applies different amount of clipping to each group of queries. Since our proposed fast per-example clipping framework is able to compute the per-example gradient norm layer-wise (as well as overall norm), our work can be used to accelerate the previously mentioned training algorithms that experimented with more refined clipping ideas.

There are other approaches to differentially private training of deep networks that avoid gradient clipping and adding noise to gradients. One example is PATE which requires a large private dataset but also a large public dataset (and hence is applicable in fewer scenarios). Gradient clipping in specific models can also be avoided, for example Phan et al. perturb the objective function of auto-encoders while Xie et al. show that it is possible to train a differentially private GAN using weight clipping instead of gradient clipping.

Overall, basing differentially private training algorithms on gradient clipping techniques (e.g., ) results in algorithms that are applicable in wider settings. However, despite the popularity of gradient clipping technique in differentially private deep learning, per-example gradient computation for a general neural network was computationally heavy and significantly slowed down training.

where $\otimes$ denotes the outer product of two vectors. In this work, we extend the technique to other types of neural networks, derive equations for per-example gradients, and provide a recipe for efficiently computing them and integrating them into differentially private training.

Recently, at the time of writing, Rochette et al. also made an attempt to extend the technique in to convolutional neural networks. While they also analyzed gradients using the chain rule and made observations similar to those in our work, their work differs with ours in both mathematical derivation and implementation. For simplicity, derives the gradient for 1D convolution operation and claim the same result also holds for higher dimensional cases. In our work, we directly show the derivations for 2D convolution (which is most popularly used in practice) using tensors. Another aspect of their technique is that to compute the per-example gradients for 1-D convolutions, they make use of 2-D convolution operations. Extensions of their techniques to per-example gradients for 2-D convolutions would require 3-D convolutions and extensions of their work to 3-D convolutions would not be efficiently supported (for example, due to lack of efficient support of 4-D convolutions in PyTorch). In contrast, to avoid this problem in our implementation, we convert the same operation into one single batch matrix-matrix multiplication, which can be done efficiently on GPUs. In addition, to smoothly integrating our technique into differentially private training, we indirectly clip gradients by assigning weights to loss values, rather than directly manipulating the gradients.

Faster Deep Learning with Differential Privacy

In this paper, we consider feedforward networks (which include recurrent networks) consisting of layers (e.g., a convolutional layer feeding into a max pooling layer, etc.).

Thus we compute $\nu_{i}$ for each $i$, reweight the loss function, ask the auto-differentiation api to get the gradient, add privacy noise to the gradient, and then update the parameters. The result is exactly the same as per-example gradient clipping, but is much faster.

For completeness, we first describe Goodfellow’s technique for fully connected layers .

By the chain rule, the derivative of $L$ with respect to the entry of $W$ at $i$th row and $j$th column is given by

where $I_{m}$ denotes an identity matrix of size $m\times m$.

2 Convolutional Layers

Suppose we have a convolutional layer with $c_{\text{out}}$ kernels of size $\kappa\times\kappa$ Here we assume the width and height of filter are the same for simplicity. Our result can be generalized to the filters with abitrary size.. Assume input images have size $s_{H}\times s_{W}$ with $c_{\text{in}}$ channels. The kernel $\mathcal{W}$ for the layer can be represented by a 4D tensor with dimensions $[c_{\text{out}},c_{\text{in}},\kappa,\kappa]$, and the input image $\mathcal{X}$ by a 3D tensor with dimensions $[c_{\text{in}},s_{H},s_{W}]$. We denote the entry of tensor $\mathcal{X}$ at location $(i,j,k)$ by $\mathcal{X}_{i,j,k}$ and write $\mathcal{X}_{i,j,*}$ to denote the entries of $\mathcal{X}$ whose indices for the first 2 dimensions are fixed to $(i,j)$. $\mathcal{X}_{i:j}$ denotes the entries with indices from $i$ to $j$.

The pre-activation $\mathcal{Z}$ resulting from performing convolution between $\mathcal{W}$ and $\mathcal{X}$, denoted by $\mathcal{W}*\mathcal{X}$, is expressed as

where $\star$ symbol defines the inner product between two tensors of same order, i.e., $\mathcal{X}\star\mathcal{Y}=\sum_{i,j,k}\mathcal{X}_{i,j,k}\mathcal{Y}_{i,j,k}$. For simplicity, let’s fix $l$ and focus on the $l$th output feature map. See Figure 2 for a graphical depiction of the convolution operation.

and see that the derivative of the $l$th pre-activation with respect to $\mathcal{W}_{l,k,i,j}$ is given by

where $d_{H}=s_{H}-\kappa$ and $d_{W}=s_{W}-\kappa$. Using the chain rule, we get

The above equation implies that the gradient $\frac{\partial L}{\partial\mathcal{W}_{l,k,*,*}}$ is obtained by performing convolution between the derivative of $L$ with respect to the pre-activation $\mathcal{Z}_{l,*,*}$ and input image $\mathcal{X}_{k,*,*}$ (without the bias term). That is,

and $\frac{\partial\mathcal{Z}_{l,*,*,*}}{\partial\mathcal{W}_{l,c,k,i,j}}$ is a 4D tensor. As in (8), an application of chain rule yields

Again, this implies that the gradient of 3D convolution can also be obtained from 3D convolutions.

3 Recurrent Layers

Similarly, the gradient with respect to $V$, weight matrix for input vector, can be obtained as follows:

Algorithm 4 describes how per-example gradients are computed using Equation (12).

4 LSTM Layers

The forward phase of an LSTM layer is described by the following pre-activations

From the above, we see that the gradient of an LSTM layer can be computed in the same way as in a recurrent layer.

5 LayerNorm Layers

As shown in Algorithm 5, the per-example gradient for LayerNorm layer over a minibatch can be obtained by simple element-wise product of two matrices.

6 Multi-head Attention Layers

Multi-head attention mechanism is a core component of Transformer network , the state-of-the-art model for neural language translation (NLT).

The attention weights are computed by the scaled dot product between $Q$ and $K$. The attention values are weighted sums of values $V$.

where $d_{m}=h\times d_{k}$. Finally, the output of layer $Y$ is obtained by applying a linear transformation on the attention values:

Similarly, we can compute the gradients with respect to other parameters:

7 Other Layer Types

Similarly, skip-connections, which are used in residual blocks also do not outwardly affect our approach.

8 Implementation

We implemented the fast per-example gradient clipping technique, described in Section 5, using PyTorch. We encapsulated the per-example gradient norm computation functionality into python wrapper classes for PyTorch’s built-in network layers, e.g., Linear, Conv2D, RNN, and so on. This modular implementation allows users to incorporate the gradient clipping functionality into their existing neural network models by simply replacing their layers with our wrapper classes. Each layer wrapper class maintains references to two tensors: pre-activations $Z$ and input $X$ to the layer. After the feed-forward step, it computes $\partial L/\partial Z$, the gradient with respect to $Z$, using autograd package and combines it with $X$ to derive per-example gradients.

Experiments

To evaluate the efficiency of the proposed framework, we compare the performance of our per-example loss reweighting algorithm to those of two other algorithms, namely Non-private and nxBP, on different types of neural network models. Non-private algorithm takes a minibatch of examples and performs the forward and backward propagation steps only once as in standard training process. nxBP is the baseline differentially private deep learning algorithm that computes per-example gradient clipping using the naive method from Section 3: it uses auto-differentiation to sequentially obtain the gradient for each record, clips it, and then adds the clipped gradients together. multiLoss is an improved version of the naive approach. As described in Section 3, it asks the auto-differentiator to get the gradients for all examples at once (e.g., it calls torch.autograd.grad with first parameter equal to the vector of losses across mini-batch records) and then clips and adds them together. Our algorithm, ReweightGP, performs back-propagation twice, once for computing per-example gradient norms (as explained in Section 5) to determine the weights for individual loss functions and the other for computing the batch gradient of weighted loss function.

We note that accuracy comparisons among the differentially private algorithms are irrelevant, as they all produce the same clipped gradients – the only difference among them is speed.

We have implemented our algorithm using PyTorch framework. We used a differentially private version of Adam optimizer, which is the same with the non-private Adam except it injects Gaussian noise with scale $\sigma$ to gradients. In our experiments, we set the default value for the clipping threshold $C$ to be $1$ and used the default value of $\sigma=0.05$. For all experiments, we set the step size of Adam optimizer to 0.001, $\beta_{1}=0.9$, and $\beta_{2}=0.999$. At each epoch, we randomly shuffle the dataset and partition the data into non-overlapping chunks of size $|B|$. All the experiments were conducted on a machine with Intel Xeon E5-2660 CPU and NVIDIA GeForce 1080 TI GPU.

We tested the effectiveness of our framework on the following 5 different neural network models for classification. All models apply softmax function to the output layers and use the cross entropy loss.

MLP (Multi-layer Perceptron): this is a simple neural network with two hidden layers. The first layer contains 128 and the second layer 256 units. We used sigmoid function as our default activation function.

CNN (Convolution Neural Network): the network consists of 2 convolutional layers, each of which followed by a $2\times 2$ max pooling layer with stride of 2, and one fully connected layer with 128 hidden units. The first convolutional layer has 20 kernels of size $5\times 5$ with stride 1, and the second layer 50 kernels of size $5\times 5$ with stride 1. We didn’t use zero-paddings.

RNN (Recurrent Neural Network): this network was constructed by adding a fully connected layer on top of one vanilla recurrent layer with 128 hidden units. $\tanh$ was used as an activation function.

LSTM (Long Short-term Memory): similar to RNN, there is one LSTM layer with 128 hidden units followed by a fully connected layer for classification.

Transformer: the network contains a word embedding layer, positional encoding layer, a transformer encoder block, and a fully connected layer. Figure 4 describes the architecture of the Transformer network used in our experiments.

1.2 Datasets and Tasks

We used the following five publicly available datasets in our experiments.

MNIST is a grayscale, image dataset of hand-written digits, consisting of 60,000 training and 10,000 test examples. Each image has $28\times 28$ pixels, and there are 10 classes (one for each digit). We trained MLP, CNN, RNN, and LSTM networks for classfication. For RNN and LSTM, we construct a sequence by considering the $i$th row of an image as an input vector for the time step $i$. In other words, we view an image as a sequence of rows.

FMNIST (Fashion-MNIST) is a dataset of fashion article images designed to replace MNIST dataset. It also contains 70,000 grayscale images of size $28\times 28$ (60,000 for training and 10,000 for testing).

CIFAR10 is an image dataset for object classification. It consists of 50,000 training examples of $32\times 32$ RGB images. There are 10 classes, and each class has 5,000 images.

IMDB is a movie review dataset for binary sentiment analysis. We trained the Transformer network on this dataset using 50% of examples. The other 50% of examples were used for testing. For word embedding, rather than training from scratch, we leveraged GloVe embedding vectors of 200 dimensions, pretrained on 6 billions of tokens.

LSUN is a large-scale scene understanding dataset, having over 59 million RGB images of size at least 256$\times$ 256, and 10 different scene categories.

2 Small Image Performance

We first show improvements for each architecture on the smaller image datasets (MNIST, FMNIST, CIFAR10). These datasets are not appropriate for Transformer, so we use IMDB for this architecture. Figure 5 compares the performance of the different gradient clipping computation methods on 5 different neural network models in terms of training time per epoch. For this experiment, the minibatch size $|B|$ was fixed to 32, and the models were trained for 100 epochs. As shown in the Figure 5, the proposed RewieghtGP algorithm significantly reduces the training time on all 5 different architectures. Notice that values on $y$-axis are in log scale. It is worth noting that the training of LSTM network takes significantly longer than that for other networks because the per-gradient computation must access each layer’s pre-activations and input tensor. This prevents us from using highly optimized fast implementation of LSTM such as NVIDIA’s cuDNN LSTM. For RNN, this limitation can be avoided as one can derive the gradient of loss function with respect to pre-activations from the gradient with respect to activations using the chain rule.

3 Impact of Different Batch Size

Figure 6 shows the impact of different batch sizes on the per-epoch training time. For this experiment, we trained the MLP, CNN, and RNN models described in Section 6.1.1 on MNIST dataset by varying the batch size. The batch sizes used for training are 16, 32, 64, and 128. An interesting observation is that for Non-private and ReweightGP per-epoch training time decreases as the batch size increases, while that for nxBP remains constant regardless of batch size. This is because that both Non-private and ReweightGP can take advantage of more parallelism due to the use of larger batch. On the other hand, in nxBP computationally heavy error back-propagation happens for each training example (even if an entire batch is stored in the gpu).

4 Impact of Network Depth

Before experimenting with larger and more complex architectures, we first provide network depth results for smaller architectures, as small networks are most commonly used with differential privacy . We trained multiple MLP models on three datasets (MNIST, FMNIST, and CIFAR10) by using different numbers of hiddne layers: 2, 4, 6, and 8. The batch size $|B|$ is fixed to 128. As shown in Figure 7, ReweightGP algorithm significantly outperforms the naive nxBP algorithm on all three datasets. Especially on FMNIST dataset with 2 hidden layers, the proposed algorithm showed 94x speed-up over the naive nxBP algorithm.

5 ResNet and VGG Networks

We now evaluate the performance on deeper architectures with millions of parameters: ResNet and VGG networks . For this evaluation, we froze the batchnorm parameters at values taken from pre-trained models (since batch-norm parameters do not have per-example gradients). In practice, other types of normalizations could also be used, such as LayerNorm (Section 5.5), group norm , and instance norm . Due to the large memory space requirement, mini-batches of size 20 are used for this experiment. Results on the LSUN dataset are shown in Figure 8. mutiLoss had out-of-memory errors on VGG networks and resnet101 for large images. We still see that ReweightGP consistently outperforms other gradient clipping algorithms (nxBP, multiLoss). The improvement is significant for images of (rescaled) size 64x64 and diminishes for size 256x256.

6 Image Size

Noting that image size played a key role in reducing the speedup, we investigate this further in Figure 9 using ResNet 18 with batch size 32 and image sizes ranging from 32x32 to 256x256. This causes quadratic growth in the width of the network (multiplying each dimension by c results in $c^{2}$ as many pixels) and we see that the advantage over the naive method decreases due to the extra computation per layer that ReweightGP uses.

7 Memory

Due to caching, it is difficult to obtain an accurate estimate of GPU memory requirements. As an alternative, we consider the largest batch size a method can support before running out of memory. For this experiment, we used ResNet 101 with 256x256 input images and varied the batch sizes. The non-private method first failed at batch size 48, ReweightGP at 36, and multiLoss at 18. nxBP operates on one example at a time (even when an entire batch is stored in the GPU). Thus we estimate the GPU memory overhead of ReweightGP compared to nonprivate to be up to $(48-36)/48\approx$ 25% for large images. At the lower end, ReweightGP with ResNet 18 with 32x32 images ran with batch size of 500 without any problems. Note nxBP under-utilizes GPU memory and parallelism (backpropagating through one example at a time). Thus, in practice, the memory overhead is manageable (i.e., allows for relatively large batch sizes) and buys us significant improvements in running time (taking better advantage of GPU parallelism).

8 Limitations

Overall, the experiments have shown that our proposed ReweightGP method outperforms the other methods nxBP and MultiLoss (which is often unreliable). ReweightGP requires more memory and computation per layer than nxBP. As a result, its advantage starts to decline with increased image sizes as this causes a quadratic scaling in the width of the network and consequently in the computations of ReweightGP. For very high resolution images, it may be preferable to use nxBP.

Second, some highly optimized versions of LSTM, such as the ones that use the CuDNN LSTM routines do not expose the internal gate values, so that we cannot obtain the appropriate gradients. However, less optimized versions of LSTM can be implemented in PyTorch/TensorFlow and benefit from our approach.

Conclusions

We presented a general framework for fast per-example gradient clipping which can be used to improve training speed under differential privacy. Prior work underutilized GPU parallelism, leading to slow training times. Our empirical evaluation showed a significant reduction in training time of differentially private models.

Per-example gradient clipping is not compatible with Batch Norm , but other layer normalization methods can be used instead .

References