Differential Privacy › DP-SGD: Training Neural Networks with Privacy

Applying differential privacy to training a neural network is non-trivial because the standard training algorithm, stochastic gradient descent, has unbounded sensitivity. A single outlier training example with a very large loss can produce a very large gradient, pushing model parameters arbitrarily far from where they would have been without that example. If we tried to apply the Gaussian mechanism directly to the gradient of a minibatch without any modification, we would need to add infinite noise to achieve meaningful privacy. The key challenge is bounding the sensitivity.

DP-SGD, introduced by Abadi et al. in 2016, solves this through two modifications to the standard SGD update. Together, these two changes transform the training algorithm from one with potentially unbounded sensitivity into one with precisely bounded sensitivity.

Step 1: Per-example gradient clipping. Before aggregating gradients from a minibatch, DP-SGD clips each individual example's gradient vector to have $\ell_2$ norm at most $C$ (the clipping threshold):

$$\tilde{g}_i = g_i \cdot \min\left(1, \frac{C}{\|g_i\|_2}\right)$$

where:

• $g_i = \nabla_\theta \mathcal{L}(\theta; x_i)$ is the gradient of the loss for training example $x_i$.
• $C$ is the clipping threshold, a hyperparameter chosen before training.
• $\tilde{g}_i$ is the clipped gradient, which satisfies $\|\tilde{g}_i\|_2 \leq C$ by construction.

Clipping bounds the sensitivity of the gradient sum: no single example can shift the aggregate gradient by more than $C$ in $\ell_2$ norm. Without clipping, an example with a large loss would produce a large gradient, making the sensitivity potentially infinite and requiring infinite noise for privacy. After clipping, the sensitivity is exactly $C$, regardless of the data distribution. This is the mechanism that makes DP-SGD work.

To see why clipping achieves sensitivity $C$, consider two neighboring datasets $D$ and $D' = D \cup \{x_\text{new}\}$. The gradient sum on $D'$ differs from the gradient sum on $D$ by exactly the clipped gradient of $x_\text{new}$, which has $\ell_2$ norm at most $C$. Thus $\| f(D') - f(D) \|_2 \leq C$, giving $\Delta_2 f = C$.

Notice that gradient clipping is not the same as gradient norm regularization or weight clipping. It operates per-example, before aggregation, and it scales the entire gradient vector uniformly. A gradient with norm 10 and clipping threshold 1 is scaled by a factor of 0.1; its direction is preserved but its magnitude is reduced to exactly 1.

Step 2: Gaussian noise addition. After clipping and summing gradients, DP-SGD adds Gaussian noise calibrated to the clipping threshold:

$$\hat{g} = \frac{1}{B}\left(\sum_{i=1}^{B} \tilde{g}_i + \mathcal{N}(0, \sigma^2 C^2 \mathbf{I})\right)$$

where:

• $B$ is the minibatch size.
• $\sigma$ is the noise multiplier, the ratio of noise standard deviation to clipping threshold.
• The noise variance $\sigma^2 C^2$ is proportional to the squared clipping threshold, since that is the sensitivity.

The noise multiplier $\sigma$ is the key privacy-utility knob. Setting $\sigma$ larger adds more noise, giving stronger privacy guarantees. Setting it smaller adds less noise, giving better gradient quality but weaker privacy. Given a target privacy budget $(\varepsilon, \delta)$ and a training procedure (number of steps, batch size, dataset size), the minimum $\sigma$ that achieves the budget can be computed using a privacy accountant.

The full DP-SGD update then proceeds as in standard SGD: parameters are updated using this noisy, clipped gradient. The privacy guarantee applies to each step independently, and the total privacy cost after $T$ steps is computed via composition.

The effect of gradient clipping is intuitive to visualize: gradients with large norms are scaled down to lie exactly on the boundary of a ball of radius $C$, while gradients with small norms are left unchanged. The plot below illustrates this with a distribution of gradient norms before and after clipping.

The left panel shows the distribution of per-example gradient norms before clipping. The distribution is right-skewed: most gradients have moderate norms, but a long tail of high-norm gradients exists. These high-norm gradients correspond to training examples with large losses, which are often the most informative but also the most sensitive. Without clipping, these outliers would dominate the aggregate gradient and make the sensitivity unbounded.

The right panel shows what clipping does to each gradient. Every point on or below the diagonal (blue) has a norm below the threshold and is left unchanged. Every point above the threshold (red) is pulled back to exactly $C = 1.0$. After clipping, no single example can contribute a gradient with norm larger than $C$, bounding the sensitivity.

A single DP-SGD step with Poisson subsampling (where each example is independently included in the minibatch with probability $q = B/n$) achieves $(\varepsilon', \delta')$-DP for that step. The privacy cost over $T$ steps accumulates, but thanks to the moments accountant or equivalently Renyi DP accountant, the total privacy cost is tighter than naive composition.

The key insight is that subsampling amplifies privacy: if only a fraction $q$ of the training data participates in each step, an individual example is included in any given step with probability $q$. This "privacy amplification by subsampling" means the effective privacy loss per step is roughly $O(q \varepsilon')$ rather than $\varepsilon'$. Subsampling acts like an extra layer of randomness on top of the noise, making it even harder for an adversary to determine whether a specific record was used.

To see why this amplification occurs, consider the mechanism from the perspective of a single individual's record. If the record is included in the training set, it enters any given minibatch with probability $q$. From the adversary's perspective, most steps look identical whether the record is in the dataset or not (because it simply was not sampled). Only the fraction $q$ of steps where it was sampled carry any information. This dramatically reduces the per-step privacy cost.

The total privacy cost after $T$ steps, at failure probability $\delta$, can be approximated as:

$$\varepsilon_{\text{total}} \approx \sqrt{2T} \cdot q \cdot \sigma^{-1} \cdot \sqrt{\ln(1/\delta)}$$

where:

• $\varepsilon_{\text{total}}$ is the cumulative privacy cost after all $T$ training steps.
• $T$ is the total number of gradient steps, equal to epochs times batches per epoch.
• $q = B/n$ is the subsampling rate, the fraction of training data in each mini-batch.
• $\sigma$ is the noise multiplier; larger $\sigma$ means smaller $\varepsilon_{\text{total}}$.
• $\delta$ is the failure probability in the $(\varepsilon, \delta)$-DP guarantee.

This is a simplified approximation. In practice, tight accounting uses the moments accountant or the PRV accountant (Privacy Random Variable accountant), which numerically compose the per-step privacy guarantees without closed-form approximations.

The formula's implications are direct and practical:

• More training steps $T$ increase privacy cost: training longer spends more budget.
• Larger subsampling rate $q$ (bigger batches relative to dataset size) increases privacy cost per step.
• Less noise $\sigma$ increases privacy cost proportionally.
• The $\sqrt{2T}$ factor reflects the square-root growth from advanced composition rather than the linear growth $O(T)$ that naive composition would give.

This composability is what makes DP practical for machine learning: you can track exactly how much privacy budget each training step consumes, and stop training once the budget is exhausted. A privacy accountant runs alongside training, incrementing the total $\varepsilon$ after each step and triggering early stopping if the budget is reached.