Differentially private stochastic gradient descent

Differentially private stochastic gradient descent (DP-SGD) is an algorithmic technique for learning and a refined analysis of privacy costs within the framework of differential privacy. DP-SGD was introduced by Abadi et al. at the 2016 ACM Conference on Computer and Communications Security, where it addresses a fundamental challenge—the privacy-utility trade-off. Stronger privacy requires more noise or larger privacy budgets, which can reduce model accuracy.

DP-SGD has become a de facto standard for privacy-preserving learning from large datasets. It is used in domains with sensitive data, including healthcare and cybersecurity. DP-SGD has been shown to demonstrate that deep neural networks with non-convex objectives can be trained under a modest privacy budget, at a manageable cost in software complexity and model quality. A non-convex objective is one that may have multiple local minima, making optimization more challenging than with convex objectives. Existing approaches require large privacy budgets to train and incur high overheads in computational resources. A privacy budget refers to the total amount of privacy loss allowed over the entire training process.

DP-SGD follows the same steps as standard stochastic gradient descent (SGD) but clips the gradients' norm to a threshold before adding Gaussian noise. Gaussian noise is a type of random noise drawn from a normal distribution. Differential privacy is formally defined using the parameters (ε, δ), which bound the privacy loss of any algorithm. DP-SGD tracks privacy loss by a method called the moments accountant. Current implementations use a method called Rényi differential privacy, which provides an even tighter privacy accounting than the original moments accountant. The moments accountant tracks the privacy loss as a random variable at each step. Another privacy-preserving training method is Private Aggregation of Teacher Ensembles (PATE), which uses an ensemble of teacher models to label public data. A teacher model is a model trained on private data that is used to label or provide guidance to another model (the student model).

Description

Standard SGD computes gradients over mini-batches. A gradient is a mathematical measure of how much the model's error changes, while a mini-batch is a small random subset of the training data. These gradients can then reveal information about individual training examples. DP-SGD can modify this process to provide privacy guarantees. This procedure is formalized as Algorithm 1 in the study by Abadi et al., which provides pseudocode for the training loop (including gradient computation, clipping, and noise addition steps).

It first computes gradients for each training example in the batch. Then, it clips the L2 norm of each gradient to a threshold C. The L2 norm is the straight-line distance from the origin to the point represented by the vector (a mathematical object that has both magnitude and direction). Finally, it adds Gaussian noise to the clipped gradients, before averaging them out.

The pseudocode for Algorithm 1 is presented below:

Algorithm 1: DP-SGD (Abadi et al., 2016)

'''Inputs:''' Examples {x₁, ..., x_N}, loss function L(θ) = (1/N) Σᵢ L(θ, xᵢ)
'''Parameters:''' learning rate ηₜ, noise scale σ, group size L, gradient norm bound C

'''Output:''' θ_T and overall privacy cost (ε, δ)

1.  Initialize θ₀ randomly
2.  '''for''' t ∈ [T] '''do'''
3.      Take a random sample Lₜ with sampling probability L/N
4.      '''for each''' i ∈ Lₜ '''do'''
5.          Compute per-sample gradient: gₜ(xᵢ) ← ∇θₜ L(θₜ, xᵢ)
6.      '''end for'''
7.      Clip each gradient:
8.          ḡₜ(xᵢ) ← gₜ(xᵢ) / max(1, ||gₜ(xᵢ)||₂ / C)
9.      Add noise and average:
10.         g̃ₜ ← (1/L) · (Σᵢ ḡₜ(xᵢ) + 𝒩(0, σ²C²I))
11.     Update model:
12.         θₜ₊₁ ← θₜ − ηₜ g̃ₜ
13. '''end for'''
14. '''return''' θ_T and privacy cost (ε, δ)

A loss function measures how wrong a model's predictions are. The goal of training is to minimise this error.

DP-SGD typically uses Poisson subsampling, where each mini-batch is formed by sampling each example independently with probability q. This provides privacy amplification by subsampling. Subsampling means selecting a random subset of the data for each training step rather than using the full dataset. The privacy parameters include the clipping norm (C) and the noise scale (σ). The clipping norm is the maximum allowed length of a gradient. Any gradient longer than C is scaled down to length C. The noise scale on the other hand controls how much random noise is added to the gradients. These parameters can determine the privacy-utility trade-off. The noise scale σ is calibrated such that the noise variance is proportional to C²σ². Unlike standard SGD, DP-SGD's privacy loss accumulates over multiple training steps, and the moments accountant can track this cumulative loss to determine the overall privacy guarantee, usually denoted as ε (epsilon), δ (delta). An ε controls how information about any single example can be leaked. Likewise, a δ is a small probability that the privacy guarantee fails. Hence, it provides tighter estimates on the overall privacy loss. Privacy loss is a measure of how much information an individual training example can be inferred from the algorithm's output.

Algorithm 1: DP-SGD (Abadi et al., 2016)

Step	Description
1	Initialize model parameters θ₀ randomly.
2	Sample a random mini-batch of training examples.
3	For each example, compute its per-sample gradient.
4	Clip each gradient to a maximum L₂ norm, C.
5	Add Gaussian noise to the sum of the clipped gradients.
6	Average the noisy gradients and update the model parameters.
7	Output the trained model θ_T and the privacy cost (ε, δ).

Privacy accounting

Unlike standard SGD, DP-SGD's privacy loss accumulates over every gradient step over multiple epochs. An epoch is one complete pass through the entire training dataset. To provide a formal guarantee, it must account for these steps combined:

Moments accountant

The moments accountant tracks the privacy loss as a random variable at each step. It keeps track of a bound in the moments of the privacy loss random variable. Rather than just tracking the average privacy loss, it also tracks higher-order moments, which are statistical measures such as variance, kurtosis and skewness that describe the shape of the privacy loss distribution. Skewness is a measure of how asymmetrical a distribution is, while kurtosis is a measure of a tail probability. These higher-order moments can allow it to bound the tail probability of the privacy loss distribution more tightly. A tail probability is the probability that a variable takes a value in the extreme end of its distribution. Therefore, it yields a much tighter estimate for the overall privacy guarantee (ε, δ) than methods that only track the average privacy loss. An alternative to the moments accountant is Rényi differential privacy (RDP), which provides tighter privacy bounds by tracking Rényi divergences of order α. Rényi divergence is a mathematical measure of how different two probability distributions are. RDP accounting has become the standard method in modern implementations.

Implications

The moments accountant allows practitioners to train deep neural networks under a single-digit privacy budget. It can also allow the noise scale σ to be calibrated to achieve a desired (ε, δ) guarantee. Without the moments accountant, the privacy budget would be consumed much faster, forcing practitioners to use more noise or train for fewer steps, which would harm accuracy and performance.

Software implementations

There are three software implementations that are based on DP-SGD, including Opacus, TensorFlow Privacy, and JAX-Privacy.

Opacus

Opacus is a PyTorch library that provides batched per-sample gradient computation, automatic gradient clipping, and Rényi Differential Privacy (RDP) accounting. This allows users to train models with DP-SGD by making minimal changes to existing PyTorch training loops.

TensorFlow Privacy

TensorFlow Privacy is developed by Google Research that provides TensorFlow optimizers for training machine learning models with differential privacy. An optimizer is the algorithm that updates the model's parameters during training to reduce error. It was also evaluated alongside Opacus and other tools in a comparative study of open-source privacy libraries.

JAX-Privacy

JAX-Privacy is a library built on JAX (a Python library) designed to simplify the deployment of robust and performant mechanisms for differentially private machine learning. It provides primitives for critical components of DP-SGD including batch selection, gradient clipping, noise addition, accounting, and auditing.

Applications and challenges

Applications

DP-SGD is used in domains where training data contains sensitive personal information. Examples of these kinds of datasets include healthcare and cybersecurity.

Healthcare

In a study conducted by Tanveer et al., DP-SGD was integrated into the training pipeline to protect patient data. It achieved a 93% accuracy on stroke risk prediction, while producing a final privacy budget of ε = 0.69. This shows that meaningful clinical utility can be obtained under a strict privacy guarantee.

Cybersecurity

In a study conducted by Machooka et al., DP-SGD was used to train deep learning models, specifically long short-term memory (LSTM) and multilayer perceptron (MLP) networks to detect cyberattacks in cyber-physical systems. This study compared DP-SGD with the Private Aggregation of Teacher Ensembles (PATE) framework, evaluating model performance (accuracy, precision, recall and F1-score) alongside privacy budget consumption. An F1-score is a measure of the model's accuracy that balances two measures—the precision and the recall. The results showed that DP-SGD can balance privacy and detection performance.

Challenges

Challenges include large privacy budgets, computational and memory overhead, and privacy-utility trade-offs. A memory overhead is the extra memory required by DP-SGD compared to standard SGD. Training accurate models often consumes large amounts of privacy budget, which degrades utility. There are also significant computational and memory overheads, since per-sample gradient computation is computation-heavy and there is always a trade-off between protection and model accuracy.

An alternative privacy-preserving training method includes Private Aggregation of Teacher Ensembles (PATE). PATE trains an ensemble of teacher models on subsets of private data, then uses that ensemble to label a public dataset for training a student model.

Research directions

The research directions of DP-SGD include adaptive techniques such as clipping threshold, learning rate, or budget allocation to improve the trade-off. A learning rate controls how much the model's parameters change in response to each gradient update, while a budget allocation refers to how the total privacy budget is distributed across training steps. A second direction is individualized privacy, which allows different users to have different privacy requirements. It also includes benchmarking, which compares different approaches head-to-head on common datasets. Empirical privacy auditing has also emerged as a method for testing whether a privacy-preserving algorithm actually provides the privacy protection it claims.