(ε, δ)-Differential Privacy

The parameter δ represents a small probability that the pure ε-DP guarantee is violated. Formally, for neighboring datasets D and D', a mechanism M satisfies (ε, δ)-DP if: Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S] + δ for all output sets S.

• δ is typically chosen to be cryptographically small (e.g., 10^-5 or smaller)
• δ should be much smaller than 1/N, where N is the dataset size
• This relaxation enables the Gaussian mechanism, which is impossible under pure ε-DP
• The failure event is not a catastrophic privacy breach but a bounded relaxation of the multiplicative bound

A fundamental property extending the guarantee to groups of k records. If a mechanism is (ε, δ)-DP for single-record changes, it provides (kε, k·e^{(k-1)ε}·δ)-DP for groups of size k.

• Privacy degrades linearly in ε but exponentially in δ for group size
• Critical for understanding protection when an individual contributes multiple records
• Contrasts with pure ε-DP where group privacy is simply kε-DP
• The exponential blowup in δ motivates keeping δ extremely small in practice

The Advanced Composition Theorem provides a tighter bound on cumulative privacy loss when applying k mechanisms sequentially. For k-fold adaptive composition of (ε, δ)-DP mechanisms, the total guarantee is approximately (ε_total, δ_total)-DP where:

• ε_total ≈ √(2k ln(1/δ')) · ε + kε(e^ε - 1)
• δ_total = kδ + δ' (for any chosen δ' > 0)
• The √k dependence on ε is a dramatic improvement over the naive kε bound
• This is the theoretical foundation enabling DP-SGD to train over thousands of iterations

Any arbitrary computation applied to the output of an (ε, δ)-DP mechanism cannot weaken the privacy guarantee. This property is inherited directly from pure ε-DP.

• An adversary with unlimited auxiliary information gains no advantage from post-processing
• Enables safe publishing of DP-protected statistics for arbitrary downstream analysis
• Critical for differentially private synthetic data: once generated, the data can be used freely
• Contrasts with anonymization techniques like k-anonymity, which are vulnerable to linkage attacks

The privacy loss incurred by observing output y from mechanism M on neighboring datasets D and D' is defined as: L = ln(Pr[M(D)=y] / Pr[M(D')=y]).

• (ε, δ)-DP guarantees that |L| ≤ ε holds with probability at least 1 - δ
• The privacy loss distribution can have heavy tails, which δ accounts for
• This formulation connects to concentrated DP and Rényi DP
• Understanding the loss distribution is essential for privacy accounting and moments accountant techniques

The Gaussian mechanism achieves (ε, δ)-DP by adding noise with standard deviation σ = (Δ₂f · √(2 ln(1.25/δ))) / ε, where Δ₂f is the L2 sensitivity of query f.

• Requires ε ≤ 1 for the standard calibration to hold
• The L2 sensitivity is typically much smaller than L1 sensitivity, enabling less noise
• For high-dimensional queries, the Gaussian mechanism is asymptotically optimal
• This mechanism is the workhorse behind DP-SGD and most practical DP deployments

The primary mechanism for achieving (ε, δ)-differential privacy. It adds noise drawn from a Gaussian (normal) distribution calibrated to the L2 sensitivity of a query.

• Noise scale: Standard deviation σ = (Δ₂f * √(2*ln(1.25/δ))) / ε
• Why Gaussian?: The additive nature of Gaussian noise and its tail bounds naturally introduce the δ failure probability.
• Use case: Essential for DP-SGD, where gradients are high-dimensional and L2 sensitivity is easier to bound than L1.

A core concept for understanding the δ parameter. For a mechanism M, the privacy loss on an outcome o is ln(Pr[M(D)=o] / Pr[M(D')=o]).

• Pure ε-DP: The absolute value of this loss is bounded by ε with probability 1.
• (ε, δ)-DP: The absolute value is bounded by ε with probability at least 1 - δ.
• δ as failure probability: δ represents the probability that the privacy loss exceeds the ε bound, meaning a catastrophic privacy breach is possible but extremely unlikely.

A formal rule that quantifies how the total privacy budget degrades when multiple (ε, δ)-differentially private mechanisms are applied sequentially.

• k-fold composition: Applying k mechanisms, each (ε, δ)-DP, yields an overall guarantee of approximately (√(2k ln(1/δ'))ε + kε(e^ε - 1), kδ + δ').
• Sublinear growth: The ε term grows with √k, not k, which is a significant improvement over basic composition.
• Foundation: This theorem underpins the entire practice of iterative private training, where a model may undergo thousands of noisy gradient updates.

A phenomenon where randomly sampling a subset of data before applying a differentially private mechanism results in a stronger overall privacy guarantee.

• Amplification effect: If a mechanism is (ε, δ)-DP on the full dataset, applying it to a random q-fraction sample amplifies the guarantee to roughly (O(qε), qδ)-DP.
• Critical for DP-SGD: Minibatch sampling in stochastic gradient descent provides this amplification for free, dramatically reducing the per-step privacy cost.
• Poisson vs. fixed-size: Poisson subsampling (each record included independently) provides the strongest amplification and is the standard in privacy accounting.