Differential Privacy

Imagine a hospital runs a statistical analysis on its patient database and publishes the result: "42% of patients in this dataset have hypertension." Now imagine you can run the same query after adding or removing one specific patient's record. If the result changes noticeably, you have learned something about that individual patient. Differential privacy prevents this.

A differentially private mechanism makes the output look roughly the same whether any one individual is in the dataset or not. It does this by adding carefully calibrated random noise to the result. The noise is not random in the sense of "whatever," it is mathematically tuned so that an observer cannot reliably tell which of two similar datasets produced a given output.

The key word is "reliably." Differential privacy does not make it impossible to learn anything. It makes the probability of learning something about a specific individual bounded by a small, measurable amount. That bound is epsilon.

Differential privacy was introduced by Dwork, McSherry, Nissim, and Smith in 2006. The formal definition is short, but each word matters.

The inequality says: the probability of any output S when the mechanism runs on D is at most exp(epsilon) times the probability of that same output when the mechanism runs on D'. Since exp(epsilon) is close to 1 for small epsilon, this means the two probability distributions are nearly identical.

The guarantee applies to every possible output S and every possible adjacent pair D and D'. There are no exceptions for unusual outputs or specific individuals. This universality is what makes the guarantee strong and composable.

Epsilon is the privacy loss parameter. Think of it as the price of admission: every query or training step costs some epsilon, and the total epsilon across all operations tells you how much privacy was consumed overall. A smaller epsilon means stronger privacy but also more noise added to achieve it, which reduces accuracy.

Delta adds a small failure probability to the guarantee. A mechanism that satisfies (epsilon, delta)-DP means the pure epsilon-DP guarantee holds for all but a delta fraction of cases. Delta must be cryptographically small, typically set to 1 divided by the dataset size squared, to be meaningful. If delta is too large the guarantee is vacuous.

Real deployments from major technology companies: Apple uses local DP with epsilon between 2 and 8 for collecting typing statistics on iOS. Google uses epsilon around 0.5 to 2 for Chrome usage statistics. The US Census Bureau used epsilon of 17.14 for the 2020 Census, which generated significant debate about whether it was strong enough.

Before you can add noise to achieve differential privacy, you need to know how much noise to add. The answer depends on the sensitivity of the computation: how much can the output change when one record is added or removed?

Global sensitivity is the maximum possible change in the output across all pairs of adjacent datasets. It is a property of the query function, not the data. If you know global sensitivity, you can add the right amount of noise to achieve the target epsilon without looking at the actual data.

High-sensitivity queries require more noise for the same epsilon, which means lower accuracy. The practical implication: design your queries and model training to have low sensitivity. This is why gradient clipping is central to DP-SGD: it artificially caps the sensitivity of the gradient computation at the clipping norm C, making the amount of noise needed predictable and bounded regardless of what individual training examples look like.

The Laplace mechanism is the original noise-adding mechanism for differential privacy, introduced by Dwork et al. in 2006. It achieves pure epsilon-DP by adding noise drawn from a Laplace distribution, scaled to the query's sensitivity.

A worked example: a hospital wants to release the count of patients with a specific diagnosis. The sensitivity is 1 (one record changes the count by at most 1). With epsilon of 0.5, the noise scale is 1/0.5 = 2. Noise is drawn from Lap(2): typically small values, occasionally larger ones. The true count of 342 might be released as 340, 344, or occasionally 338.

The Laplace mechanism produces pure epsilon-DP with no delta term needed. This is the strongest form of the guarantee. The cost is that Laplace noise is heavy-tailed, meaning occasionally large noise values will be added, which can hurt accuracy on individual queries.

The Gaussian mechanism replaces Laplace noise with Gaussian (normal distribution) noise. It provides (epsilon, delta)-DP rather than pure epsilon-DP: the guarantee holds with a failure probability of delta. In exchange for this slightly weaker guarantee, Gaussian noise has lighter tails than Laplace noise, which is more useful for high-dimensional data like gradient vectors in machine learning.

This matters because gradient vectors can have thousands or millions of dimensions. For high-dimensional outputs, the L2 sensitivity (Euclidean distance) is more natural than the L1 sensitivity used by the Laplace mechanism. The Gaussian mechanism adds noise proportional to the L2 sensitivity, and each dimension gets noise independently from the same Gaussian distribution.

The Gaussian mechanism is the noise-adding technique used in DP-SGD. During training, gradients are high-dimensional vectors. The L2 clipping norm C bounds the L2 sensitivity of each per-sample gradient. The Gaussian noise added after clipping has standard deviation C times sigma, where sigma is the noise multiplier chosen to achieve the target (epsilon, delta) privacy guarantee.

Epsilon is a budget. Every differentially private operation you run on a dataset spends some of that budget. When the budget runs out, further queries would reveal too much about individuals. Understanding how epsilons combine across multiple operations is critical for designing systems that stay within acceptable privacy bounds.

Basic composition is the simplest rule: k queries of epsilon each cost k times epsilon in total. It is always safe to apply. The problem is that it can be very conservative: the true privacy loss from multiple queries is often much less than the basic composition bound.

Advanced composition gives tighter bounds. For k queries each satisfying (epsilon, delta)-DP, the total cost under advanced composition is approximately epsilon times the square root of 2k times ln(1/delta) plus k times epsilon times (exp(epsilon) minus 1), with a delta term that accumulates. This grows slower than linearly in k, which matters a lot for DP-SGD where you run thousands of gradient steps.

Privacy amplification by subsampling is an additional tool. If you apply a mechanism to a random sample of fraction q from the full dataset, the effective epsilon for the full dataset is approximately q times epsilon. This is why mini-batch training in DP-SGD provides much better privacy than running the full gradient: each step touches only a small fraction of the training set.

Renyi differential privacy (RDP) provides the tightest composition bounds and is the basis of modern privacy accountants. It replaces the single epsilon number with a function over a parameter alpha, which gives more information about the exact privacy loss distribution and allows tighter addition across composition steps.

DP-SGD (Differentially Private Stochastic Gradient Descent) was introduced by Abadi, Chu, Goodfellow, McMahan, Mironov, Talwar, and Zhang in 2016. It modified standard mini-batch gradient descent to provide differential privacy guarantees on the trained model. This means any output of the trained model, including all its parameters, satisfies (epsilon, delta)-DP with respect to any individual training example.

The modification has two parts added to each gradient step. Both are necessary. Neither alone is sufficient.

Each step of DP-SGD spends some privacy budget. The privacy accountant tracks exactly how much has been spent, so training can stop before the total epsilon exceeds the target. Getting the accounting right matters: overly conservative accounting wastes the budget and forces you to stop training early; overly optimistic accounting produces false guarantees.

The moments accountant was introduced in the original DP-SGD paper. It tracks the moment-generating function of the privacy loss random variable rather than just the epsilon bound. This gives tighter bounds than basic or advanced composition, especially for the large number of gradient steps typical in deep learning training.

Renyi differential privacy (RDP), introduced by Mironov in 2017, provides an even tighter framework. RDP parameterises privacy loss by an order alpha and measures the Renyi divergence between the output distributions on adjacent datasets. RDP composes exactly: add the RDP values from each step. At the end of training, convert the accumulated RDP bound to a standard (epsilon, delta) guarantee. Modern privacy accountants, including those in TensorFlow Privacy and Opacus, use RDP.

In practice, a privacy accountant takes three inputs: the noise multiplier sigma, the sampling rate q = B/N, and the number of steps. It returns the (epsilon, delta) guarantee for those parameters. You can use it before training to find the sigma that achieves your target epsilon in your planned number of steps, or during training to decide when to stop.

Differential privacy costs accuracy. The noise added to gradients during DP-SGD slows learning and introduces bias in the gradient estimates. Understanding the magnitude of this cost is essential for deciding whether DP is appropriate for a given application.

Four factors determine how large the accuracy cost is. Dataset size is the most important: larger datasets have a higher signal-to-noise ratio, so the same amount of noise hurts less. Epsilon value: smaller epsilon means more noise. Model capacity: larger models can absorb more noise in their many parameters. Number of epochs: more training epochs spend more budget, requiring either more noise per step or stopping earlier.

These numbers are from public benchmarks on relatively small datasets. On large datasets with millions of examples, the accuracy gap narrows dramatically. Google trained a language model with epsilon of 0.56 and delta of 10 to the power of 10 and achieved near-parity with the non-private baseline on several NLP tasks. The key insight: with enough data, the signal overwhelms the noise even at low epsilon.

For most practical applications, epsilon between 1 and 10 provides a meaningful but not extreme privacy guarantee while keeping accuracy within a few percentage points of the non-private baseline. Epsilon below 1 should be considered for high-stakes applications like medical records or financial data, accepting the accuracy cost as a necessary price for strong protection.

Differential privacy has two deployment models that differ in where the noise is added and how much trust is required from the data aggregator.

The accuracy gap between local and global DP can be large. Achieving the same statistical accuracy under local DP as under global DP requires roughly the square root of n more users, where n is the dataset size. For a dataset of 1 million users, local DP might require 1000 times as many users to achieve the same accuracy as global DP.

Apple uses local DP with the RAPPOR protocol for collecting information about which emoji keyboards users prefer and which websites trigger crashes. Google Chrome uses local DP for collecting statistics about web browsing patterns. These systems work because the populations are enormous (hundreds of millions of users) and the queries are simple, so the accuracy loss from local DP is acceptable.

PATE is an alternative to DP-SGD for training differentially private models. It was introduced by Papernot, Abadi, Erlingsson, Goodfellow, and Talwar in 2017. Rather than adding noise to gradients during training, PATE achieves privacy by controlling what labelled data the student model learns from.

PATE is particularly useful when you have a large amount of unlabelled public data and a smaller amount of sensitive private labelled data. Instead of training one model on the private data with DP-SGD, PATE trains many teacher models on disjoint subsets of the private data, then uses their aggregate knowledge to label public data with privacy guarantees.

PATE has two advantages over DP-SGD. First, the privacy budget is spent only on the labelling steps, not on every gradient step of training. If the teachers strongly agree on labels (low entropy of votes), very few public examples need to be labelled and the total epsilon is very small. Second, the student model is trained without any DP noise on its own gradients, so it can be a large, high-capacity model trained to convergence.

The limitation is the requirement for unlabelled public data in the same domain as the private data. In many applications, no such public data exists or it would itself be sensitive.

Two mature open-source libraries implement DP-SGD for production use. Both handle per-sample gradient computation, clipping, noise addition, and privacy accounting. Both use RDP-based privacy accountants for tight epsilon bounds.