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

Motivation

• Sensitive-data models can leak private information even through black-box access, motivating differential privacy as a protection framework.The motivation includes medical records, emails, and financial transactions.Source: §1 · p. 1
• Per-example gradient clipping can slow private deep-learning training by up to two orders of magnitude because it limits GPU/TPU batch processing.Naive implementations sequentially process individual records before aggregating clipped gradients.Source: §1 · p. 1

Contributions

• The proposed methods analyze backpropagation to compute per-example gradients efficiently using standard auto-differentiation in TensorFlow and PyTorch, without low-level programming.The implementation uses Python wrappers around layer objects.Source: §1 · pp. 1–2
• The framework extends beyond fully connected networks to convolutional layers, recurrent networks, attention, and residual blocks.This broadens earlier fast clipping work that applied only to fully connected networks [17].Source: §1 · p. 2
• Up to 94x speedups over naive per-example gradient computation make hardware-accelerated private training approach non-private training speed for minibatches of 128.The reported speedup range is 54x–94x, depending on the model.Source: §1 · p. 2

Applications and evaluation

• The authors demonstrate differentially private training of a Transformer encoder block under Rényi differential privacy and evaluate the approach across neural-network types.The experiments are intended to assess effectiveness across varied architectures.Source: §1 · p. 2

Notation

• Neighboring datasets differ by the addition or removal of one record, establishing the adjacency relation used in privacy definitions.The datasets are written D and D′ with D∼D′.Source: §2 · p. 2

2.1 Differential Privacy

• Differential privacy requires randomized mechanisms to make adding or removing one record have little influence on the output distribution.The paper distinguishes pure privacy, δ = 0, from approximate privacy, δ > 0.Source: §2.1 · p. 2

2.2 Rényi Differential Privacy

• Rényi differential privacy bounds Rényi α-divergence by ϵ for datasets differing in one record, using moment α and privacy parameter ϵ.RDP guarantees can be converted to (ϵ, δ)-differential privacy.Source: §2.2 · p. 3

Building Blocks

• The Gaussian mechanism answers numerical aggregate queries by adding Gaussian noise calibrated to query sensitivity.Its noise variance depends on the L2 sensitivity of the query.Source: §2.2 · p. 3

2.2 Rényi Differential Privacy

• RDP supports privacy accounting for iterative algorithms because the privacy losses of composed mechanisms add for a fixed α.The paper converts the resulting RDP parameters to (ϵ, δ)-DP at the end.Source: §2.2 · p. 3

Building Blocks

• Post-processing immunity ensures that applying any algorithm to a private mechanism’s output does not worsen its privacy parameters.This applies to both RDP and (ϵ, δ)-DP as stated in the paper.Source: §2.2 · p. 3

• Per-example gradient clipping bounds each contribution's L2 norm at c before Gaussian noise is added to the mini-batch gradient.The clipped vector retains its direction, while contributions above c are rescaled.Source: §3.2 · p. 4
• Naively computing each example's gradient separately loses GPU matrix parallelism and may require multiple data transfers.Source: §3.3 · pp. 4–5
• Requesting multiple gradients through automatic differentiation is faster than a serial loop but remains significantly slower than non-private training.Source: §3.3 · p. 5
• Per-example gradient norms can be obtained from intermediate auto-differentiation results, converted into weights, and used to reweight the mini-batch loss.Source: §3.3 · p. 5
• The gradient of the reweighted loss is exactly equivalent to per-example clipping, after which noise addition and parameter updates proceed as in the standard private framework.Source: §3.3 · p. 5

• Abadi et al. [2] made private deep-network training practical at ϵ values of 10 or less using gradient clipping and Renyi Differential Privacy.Source: §4 · p. 5
• Subsequent work explored adaptive and layer-wise clipping strategies, while alternative approaches such as PATE require both large private and public datasets.Source: §4 · p. 5
• Gradient-clipping-based methods remain broadly applicable, but general per-example gradient computation was computationally heavy and slowed training substantially.Source: §4 · p. 5
• Goodfellow [17] showed that fully connected per-example gradients can be computed efficiently when parameter gradients decompose into outer products of intermediate quantities.Source: §4 · pp. 5–6
• This work extends that technique beyond fully connected layers by deriving per-example gradients and an efficient integration recipe for other neural-network types.Source: §4 · p. 6

• Algorithm 1 determines Gaussian noise variance with the Moment Accountant from privacy parameters, clipping threshold, batch size, and iteration count.Source: §5 · p. 6
• Each iteration performs a feed-forward pass, computes per-example gradient norms, and uses automatic differentiation to obtain the training gradient.Source: §5 · p. 6
• The resulting noisy gradient is used to update the network parameters within the differentially private training loop.Source: §5 · p. 6

• The key identity expresses a clipped per-example gradient as its original gradient multiplied by a scalar weight ν_i.Source: §16 · p. 7
• Reweighting the loss and then invoking automatic differentiation produces exactly the sum of clipped per-example gradients, without explicitly materializing every gradient.Source: §16 · p. 7
• The layerwise norm calculation uses gradients with respect to pre-activations and layer inputs, whose squared contributions are aggregated across weights and biases.Source: §16 · p. 7

5.1 Fully-connected Layers

• For fully connected layers, per-example parameter gradients are efficiently computed by reshaping batch quantities and using batched matrix multiplication.Source: §5.1 · p. 7

5.2 Convolutional Layers

• The kernel and input are represented as tensors whose dimensions determine the convolutional output and gradient structure.The presentation assumes square filters for simplicity, while noting that arbitrary filter sizes are possible.Source: §5.2 · p. 8
• Per-example convolutional gradients combine the derivative with respect to pre-activation Z and the input image X through convolution.The convolution replaces the outer product used for fully connected layers.Source: §5.2 · p. 8
• im2col converts image patches into matrix rows, enabling per-example convolutional gradients through efficient general matrix-matrix multiplication.The reshaped derivative and im2col representation support the batch computation described in Algorithm 3.Source: §5.2 · pp. 8–9
• The same derivation extends to 3D convolution, where the gradient can likewise be obtained using 3D convolutions.Source: §5.2 · p. 9

5.3 Recurrent Layers

• The recurrent-layer gradient with respect to hidden-state weights W is derived from the time-indexed pre-activations and hidden states.The derivation uses the chain rule for each weight entry across the sequence.Source: §5.3 · p. 9
• Per-example gradients for the input-weight matrix V are obtained similarly from the recurrent-layer derivation.Source: §5.3 · p. 9
• Algorithm 4 computes recurrent per-example gradients from the gradients with respect to pre-activations and the input sequence over T time steps.Source: §5.3 · pp. 9–10

5.4 LSTM Layers

• LSTM gradients can be computed using the same approach as recurrent-layer gradients after stacking the four gate parameters into combined matrices.The combined representation uses W ∈ R4m×m, V ∈ R4m×n, and a bias vector for all gates.Source: §5.4 · p. 10
• LayerNorm per-example gradients are computed as an element-wise product of two matrices after normalizing activations using their mean and variance.LayerNorm controls statistics across activations rather than across minibatches.Source: §5.5 · p. 10
• Multi-head attention applies linear transformations to query, key, and value inputs, computes scaled dot-product attention, and linearly transforms the resulting attention values.The architecture is described for a Transformer encoder block with h attention heads.Source: §5.6 · pp. 10–11
• Attention parameter gradients are formed from inner products between corresponding derivative and input columns.For W, the entry at location (i, j) uses the ith column of the derivative with respect to Q and the jth column of the preceding Q input.Source: §5.6 · p. 11

5.7 Other Layer Types

• Max-pooling and softmax layers are automatically handled through auto-differentiation when derivatives with respect to lower-layer pre-activations are computed.Source: §5.7 · p. 11
• Skip-connections in residual blocks likewise do not outwardly affect the per-example gradient computation approach.Source: §5.7 · p. 11
• PyTorch wrapper classes expose per-example gradient norm computation for built-in layers such as Linear, Conv2D, and RNN through simple layer replacement.The modular implementation is designed for incorporation into existing neural network models.Source: §5.8 · p. 12

6.2 Small Image Performance

• ReweightGP significantly reduces training time across five architectures on MNIST, FMNIST, CIFAR10, and IMDB experiments.Figure 5 uses minibatch size 32 and 100 epochs; LSTM training remains much slower because per-gradient computation accesses layer pre-activations and inputs.Source: §6.2 · p. 13, Figure 5 · p. 13

6.3 Impact of Different Batch Size

• Larger batch sizes reduce per-epoch time for Non-private and ReweightGP, whereas nxBP time remains constant because it back-propagates separately for each example.The batch-size experiment uses MLP, CNN, and RNN models trained on MNIST with batch sizes 16, 32, 64, and 128.Source: §6.3 · p. 14, Figure 6 · p. 14

6.4 Impact of Network Depth

• ReweightGP outperforms naive nxBP across MLP depths from 2 to 8 hidden layers on MNIST, FMNIST, and CIFAR10.With batch size 128, the largest reported gain is a 94x speed-up on FMNIST with two hidden layers.Source: §6.4 · p. 14

6.5 ResNet and VGG Networks

• On ResNet and VGG, ReweightGP consistently outperforms nxBP and multiLoss, with significant improvement at 64x64 images that diminishes at 256x256.The deeper-network experiment uses LSUN and minibatches of 20; multiLoss encounters out-of-memory errors on VGG and resnet101 for large images.Source: §6.5 · p. 14

6.6 Image Size

• ReweightGP’s advantage decreases as image resolution grows because its extra per-layer computation scales quadratically with image dimensions.For very high-resolution images, the paper states that nxBP may be preferable.Source: §6.6 · p. 14, §6.8 · p. 15

6.7 Memory

• ReweightGP uses more memory than non-private training, with up to approximately 25% estimated overhead for large images, but still supports relatively large batches.With ResNet101 and 256x256 images, the first failing batch sizes are 48 for Non-private, 36 for ReweightGP, and 18 for multiLoss.Source: §6.7 · pp. 14–15

• Fast per-example gradient clipping provides a general framework for improving training speed under differential privacy.The framework addresses prior underuse of GPU parallelism and yielded a significant reduction in differentially private model training time.Source: §7 · p. 15
• The empirical evaluation showed a significant reduction in the training time of differentially private models.Source: §7 · p. 15
• Per-example gradient clipping is incompatible with Batch Norm, although other layer-normalization methods can be used instead.Source: §7 · p. 16