(ε, δ)-Differential Privacy

The parameter δ represents a small, cryptographically negligible probability that the strict ε-differential privacy guarantee is violated. This allows a mechanism to output a result with a privacy loss exceeding ε, but only with probability at most δ. This relaxation is not a bug but a feature, enabling the use of the Gaussian mechanism and tighter composition theorems, which are essential for iterative algorithms like DP-SGD. A typical choice for δ is much smaller than 1/N, where N is the dataset size, ensuring the violation is statistically unlikely to affect any single individual.

The core motivation for (ε, δ)-DP is that pure ε-DP is incompatible with the Gaussian mechanism. Pure ε-DP requires noise from a Laplace distribution, which has a heavier tail. The Gaussian mechanism adds noise calibrated to the L2-sensitivity of a query, but its privacy loss is unbounded. The δ parameter explicitly accounts for the tail probability where this loss exceeds ε. This is the foundational mechanism for Differentially Private Stochastic Gradient Descent (DP-SGD), where Gaussian noise is added to clipped gradients in every training step.

A key property of (ε, δ)-DP is its behavior under composition. When multiple (ε, δ)-DP mechanisms are run on the same dataset, the total privacy loss accumulates. The advanced composition theorem provides a much tighter bound on this accumulation compared to basic composition. For k mechanisms, the total privacy loss is roughly O(√k * ε, kδ + δ'). This sub-linear scaling is critical for training deep learning models over thousands of iterations, allowing a meaningful privacy budget to be tracked and maintained by a moments accountant.

(ε, δ)-DP provides a graceful degradation of privacy for groups. If a mechanism is (ε, δ)-DP for a single record, it is (kε, k * e^(k-1)ε * δ)-DP for a group of size k. This means the privacy guarantee weakens predictably for correlated data or when protecting a user with multiple records. This property is crucial for defining user-level privacy, where all contributions from a single user must be protected, often requiring a larger privacy budget allocation than item-level privacy.

Like pure ε-DP, (ε, δ)-DP is immune to post-processing. Any arbitrary computation applied to the output of an (ε, δ)-DP mechanism cannot weaken the privacy guarantee. An adversary with access to the output cannot increase the ε or δ values, regardless of the auxiliary information they possess or the transformations they apply. This property is vital for system design, as it guarantees that privacy is not compromised by downstream analysis, visualization, or model publishing.

The (ε, δ)-DP guarantee has a powerful operational interpretation in terms of membership inference attacks. An adversary trying to distinguish between two neighboring datasets based on the mechanism's output cannot have both a low false positive rate (Type I error) and a low false negative rate (Type II error). The parameters ε and δ define a trade-off function between these errors, formalized by Gaussian Differential Privacy (GDP). This provides a concrete, semantic meaning to the abstract privacy parameters.