(Epsilon, delta)-differential privacy is the standard formal definition of approximate differential privacy, introduced by Dwork et al. and canonically presented in DWORK2014 (Definition 2.4). It provides a mathematically rigorous guarantee that the output of a randomized algorithm is insensitive to the presence or absence of any single individual’s data in the input database, up to controlled multiplicative and additive factors.
Formally, a randomized algorithm M with domain N^|X| is (epsilon, delta)-differentially private if for all measurable subsets S of Range(M) and for all neighboring databases x, y with ||x - y||_1 ⇐ 1:
Pr[M(x) in S] ⇐ exp(epsilon) * Pr[M(y) in S] + delta.
When delta = 0, this reduces to pure epsilon-differential privacy, where the output distributions on any two neighboring databases are multiplicatively close by a factor of exp(epsilon). The parameter epsilon controls the “privacy budget” — smaller epsilon means stronger privacy. The parameter delta represents the probability of a catastrophic privacy failure: with probability at most delta, the mechanism may produce outputs that completely violate the epsilon-DP guarantee. Typically delta is chosen to be cryptographically small, e.g., delta = n^{-omega(1)} where n is the database size; the standard recommendation is delta << 1/n.
The definition is central to certified approximate unlearning, where the same (epsilon, delta) framework quantifies how closely the distribution of an unlearned model matches that of a model retrained from scratch without the forgotten data. In this context, M(x) represents the unlearned model distribution and M(y) represents the retrained model distribution, and the (epsilon, delta) guarantee ensures statistical indistinguishability.
Key Details
- The privacy loss random variable for a specific output xi is L(xi) = ln(Pr[M(x) = xi] / Pr[M(y) = xi]). Under (epsilon, delta)-DP, |L(xi)| ⇐ epsilon with probability at least 1 - delta.
- Post-processing immunity (Proposition 2.1): if M is (epsilon, delta)-DP, then for any randomized function g, g(M(x)) is also (epsilon, delta)-DP.
- Basic composition (Theorem 3.16): k mechanisms with parameters (epsilon_i, delta_i) compose to (sum epsilon_i, sum delta_i)-DP.
- Advanced composition (Theorem 3.20): k-fold adaptive composition of (epsilon, delta)-DP mechanisms yields (epsilon’, k*delta + delta’)-DP where epsilon’ = sqrt(2k * ln(1/delta’) * epsilon) + k * epsilon * (e^epsilon - 1).
- Group privacy (Theorem 2.2): for groups of size c, an epsilon-DP mechanism provides (cepsilon)-DP; for (epsilon, delta)-DP, the guarantee degrades to (cepsilon, c*e^{(c-1)*epsilon}*delta).
- Equivalent characterization via approximate max-divergence: M is (epsilon, delta)-DP iff D_inf^delta(M(x) || M(y)) ⇐ epsilon for all neighboring x, y.
- Related to hockey-stick divergence: (epsilon, delta)-DP is equivalent to E_epsilon(M(x) || M(y)) ⇐ delta for all neighboring x, y.
- Can be derived from Renyi differential privacy via the RDP to epsilon-delta DP conversion lemma.