Differential Privacy › Formal Definition

Let $\mathcal{M}$ be a randomized mechanism (such as a training algorithm) that takes a dataset $D$ as input and produces some output (such as model parameters $\theta$). Two datasets $D$ and $D'$ are called neighboring if they differ in exactly one record: one dataset is obtained from the other by adding or removing a single individual's data.

The mechanism $\mathcal{M}$ satisfies $(\varepsilon, \delta)$-differential privacy if for all pairs of neighboring datasets $D, D'$ and all subsets of outputs $S \subseteq \text{Range}(\mathcal{M})$:

$$\Pr[\mathcal{M}(D) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{M}(D') \in S] + \delta$$

where:

• $\varepsilon \geq 0$ is the privacy loss parameter, sometimes called the privacy budget. Smaller values give stronger privacy.
• $\delta \geq 0$ is the failure probability. With probability at most $\delta$, the guarantee may fail entirely.
• $e^{\varepsilon}$ is the maximum multiplicative ratio between output probabilities for neighboring datasets.

Let's unpack what this inequality is saying. The ratio $\Pr[\mathcal{M}(D) \in S] / \Pr[\mathcal{M}(D') \in S]$ measures how differently the mechanism behaves when one record is included versus excluded. The $(\varepsilon, \delta)$ guarantee says this ratio can never exceed $e^\varepsilon$ (with probability at least $1 - \delta$). If $\varepsilon = 0$ and $\delta = 0$, the distributions are identical: the mechanism's output looks the same regardless of whether any particular record is present, which is perfect privacy but typically useless utility. As $\varepsilon$ increases, the mechanism is allowed to reveal more about its input, enabling better utility.

When $\delta = 0$, the definition is called pure or $\varepsilon$-DP. When $\delta > 0$, it is called approximate or $(\varepsilon, \delta)$-DP. The $\delta$ term allows for a small probability that the guarantee fails altogether, which is conceptually unsatisfying but mathematically useful: it permits tighter bounds and is more practical for machine learning applications. Typically $\delta$ is set to a value much smaller than $1/n$, where $n$ is the training set size, making sure the failure event is rare enough not to matter in practice. For a dataset of 100,000 training examples, $\delta = 10^{-6}$ is a common choice.

The parameter $\varepsilon$ controls how much the output distributions can differ between neighboring datasets. When $\varepsilon = 0$, the outputs are identical regardless of whether a record is included, giving perfect privacy but typically zero utility. As $\varepsilon$ grows, the mechanism can "reveal" more about the training data and achieve higher utility.

A useful way to think about $\varepsilon$: it bounds the log-odds ratio. If you observe the output of the mechanism, your posterior belief about whether a specific record was included can shift by at most a multiplicative factor of $e^{\varepsilon}$ from your prior. For $\varepsilon = 1$, this factor is approximately 2.72. If a record had a 50% prior probability of being in the dataset, the posterior after seeing the model output is at most $e^1 / (1 + e^1) \approx 73\%$. For $\varepsilon = \ln(2) \approx 0.69$, the maximum posterior would be 67%. The smaller $\varepsilon$ is, the harder it is for any analysis of the model output to update your beliefs about membership.

This log-odds interpretation also makes composability natural. When you run two DP mechanisms sequentially, the log-odds can shift by up to $\varepsilon_1$ from the first and up to $\varepsilon_2$ from the second, for a total of $\varepsilon_1 + \varepsilon_2$. The privacy budgets simply add.

In practice, $\varepsilon$ values used in deployed systems vary widely:

• Academic DP-SGD papers often report $\varepsilon \in [1, 10]$ for reasonable model utility.
• Apple's on-device differential privacy for emoji statistics uses $\varepsilon = 14$.
• The US Census Bureau's deployment for the 2020 Census used $\varepsilon \approx 17.14$ for person-level records.
• For LLM fine-tuning, $\varepsilon \in [3, 8]$ is a common practical range.

There is no universally agreed "safe" threshold. The appropriate $\varepsilon$ depends on the sensitivity of the data, the size of the population, and the threat model. A value that is privacy-preserving for a database of 10 million people may be inadequate for a database of 1,000 people, because the adversary's prior is much more concentrated in the small dataset case.

$\varepsilon$ is sometimes criticized as an opaque parameter: what observable privacy risk does $\varepsilon = 3$ represent in terms of observable privacy risk? Researchers have developed more interpretable translations. For example, if $\varepsilon = \ln(3)$, it means that even with perfect knowledge of the algorithm, an adversary cannot increase their probability of correctly guessing any binary fact about a specific individual by more than a factor of 3. This "hypothesis testing" interpretation gives practitioners a more direct sense of the protection level.

One of differential privacy's most powerful properties is composability. If you run two differentially private mechanisms on the same dataset, the combined result is still differentially private, with privacy loss that accumulates. This composability is what allows DP to be applied to complex multi-step processes like neural network training.

Basic composition: If mechanism $\mathcal{M}_1$ satisfies $(\varepsilon_1, \delta_1)$-DP and $\mathcal{M}_2$ satisfies $(\varepsilon_2, \delta_2)$-DP, then running both on the same dataset satisfies $(\varepsilon_1 + \varepsilon_2, \delta_1 + \delta_2)$-DP. Privacy budgets add linearly.

Advanced composition: Tighter bounds are achievable when running many mechanisms. The privacy loss does not grow as fast as the naive linear sum suggests. Moments accountant and Renyi differential privacy (RDP) techniques provide these tighter bounds and are essential for training neural networks over many gradient steps.

To understand why advanced composition is tighter, think about it probabilistically. Each individual mechanism step contributes a small privacy loss, but these losses are random variables, not fixed worst-case values. When you compose many steps, the losses are unlikely to all land on their worst-case simultaneously. The moments accountant exploits this by tracking the distribution of privacy loss across compositions, rather than just the maximum. Under RDP composition, after running $k$ independent $(\varepsilon, \delta)$-DP mechanisms, the total privacy cost grows approximately as $O(\sqrt{k})$ rather than $O(k)$ in favorable regimes, giving much better bounds for the hundreds of thousands of gradient steps in neural network training.

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.

The composition theorem also explains why releasing multiple queries about the same sensitive dataset degrades privacy cumulatively. Each SQL query, each model checkpoint, each evaluation metric computed on the private data is a mechanism that spends budget. Organizations deploying DP systems must track all these interactions carefully, including intermediate releases as well as the final model. A privacy accountant is the bookkeeping system that logs each expenditure and ensures the total remains within the authorized budget. Failing to count all interactions is one of the most common mistakes in real DP deployments.

To understand how to make a concrete algorithm differentially private, you need the concept of sensitivity. The sensitivity of a function measures how much its output can change when one record in the input dataset is modified. If a function has low sensitivity, only a small amount of noise is needed to hide the influence of any single record. If a function has high sensitivity, more noise is required.

There are two common notions of sensitivity. The $\ell_1$ sensitivity measures the maximum change in the output's $\ell_1$ norm, and the $\ell_2$ sensitivity measures the maximum change in the $\ell_2$ norm:

$$\Delta_1 f = \max_{D, D' \text{ neighboring}} \| f(D) - f(D') \|_1$$ $$\Delta_2 f = \max_{D, D' \text{ neighboring}} \| f(D) - f(D') \|_2$$

The Laplace mechanism (which adds Laplace-distributed noise scaled to $\Delta_1 f / \varepsilon$) achieves pure $\varepsilon$-DP and is preferred for scalar or low-dimensional outputs. The Gaussian mechanism (which adds Gaussian noise scaled to $\Delta_2 f$) achieves approximate $(\varepsilon, \delta)$-DP and is preferred for high-dimensional vector outputs like neural network gradients, because Gaussian noise has better properties in high dimensions. We will focus on the Gaussian mechanism for the rest of this chapter.