Differential Privacy

The parameter epsilon (ε) is the privacy loss parameter, quantifying the maximum divergence between outputs on neighboring datasets. A smaller ε provides stronger privacy.

• ε = 0: Perfect privacy, identical output distributions.
• ε = 0.1–1.0: Strong privacy, typical for high-sensitivity data.
• ε > 10: Weak privacy, minimal meaningful guarantee. The budget is consumed with each query, and once exhausted, no further analysis is permitted on the sensitive dataset.

When multiple differentially private mechanisms are applied to the same dataset, their privacy budgets sum linearly. If mechanism M₁ satisfies ε₁-differential privacy and M₂ satisfies ε₂-differential privacy, their combined release satisfies (ε₁ + ε₂)-differential privacy.

• This is the fundamental accounting rule for tracking cumulative privacy loss.
• Enables principled budgeting across complex analytical pipelines.
• Forces a hard trade-off between query volume and per-query accuracy.

When differentially private mechanisms operate on disjoint subsets of the data, the total privacy cost is bounded by the maximum ε of any single mechanism, not the sum.

• If a dataset is partitioned by user ID, querying each partition independently incurs only the cost of a single query.
• This property is critical for scalable systems processing sharded data.
• Enables efficient training of machine learning models on distributed data without multiplying the privacy budget.

Any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Once noise is calibrated and added, no downstream analysis—whether statistical, machine learning, or adversarial—can reverse the privacy protection.

• An attacker with arbitrary auxiliary information gains no advantage from post-processing.
• This is a closure property: DP is robust to arbitrary future computations.
• Enables safe release of DP-sanitized data for unrestricted secondary analysis.

Differential privacy naturally extends to protecting groups of correlated individuals. If a mechanism guarantees ε-differential privacy for a single record, it provides kε-differential privacy for any group of size k.

• Protects against adversaries with background knowledge about family members or cohorts.
• The guarantee degrades linearly with group size, reflecting the inherent difficulty of hiding coordinated signals.
• Critical for genomic datasets where relatives share sensitive attributes.

The core mechanism of DP is the privacy loss random variable, defined as the log-ratio of the probability of observing an output under two neighboring datasets. For a mechanism M:

• Privacy Loss = ln( Pr[M(D)=o] / Pr[M(D')=o] )
• ε-differential privacy bounds this loss by ε with probability 1-δ for approximate DP.
• This formulation enables tight composition theorems like Rényi Differential Privacy and zero-Concentrated DP, which provide sharper accounting than basic composition.

The privacy loss parameter that quantifies the strength of the guarantee. A smaller epsilon (e.g., ε=0.1) provides stronger privacy by limiting the maximum divergence between outputs on neighboring datasets.

• Mechanism: Controls the scale of noise added to a query or gradient.
• Composition: Budgets are consumed additively; querying a dataset multiple times accumulates the total epsilon cost.
• Trade-off: Decreasing epsilon increases privacy but degrades model utility and accuracy.

The standard method for achieving (ε, δ)-differential privacy by adding isotropic Gaussian noise calibrated to the L2-sensitivity of a function.

• Sensitivity: The maximum change in a function's output when a single record is added or removed from the dataset.
• Scale: Noise standard deviation is proportional to sensitivity divided by epsilon.
• Relaxation: Introduces the delta (δ) parameter, representing a small probability that the pure ε-guarantee is violated.

The dominant algorithm for training deep learning models with differential privacy guarantees. It modifies standard SGD by clipping per-example gradients and adding Gaussian noise.

• Clipping: Bounds the influence of any single training example by scaling its gradient to a fixed L2-norm threshold.
• Noise Addition: Gaussian noise is injected into the summed, clipped gradients before the model update.
• Moments Accountant: A privacy accounting technique used to tightly track the total privacy budget spent over many training iterations.

Two distinct trust models defining where noise is injected in the data pipeline.

• Global DP (Central Model): A trusted curator collects raw data, applies the privacy mechanism, and releases sanitized outputs. Provides higher utility for a given epsilon.
• Local DP (LDP): Noise is added by the individual user on their device before data is transmitted. Protects against a compromised server but requires significantly more noise to achieve the same guarantee.
• Shuffler Model: An intermediate architecture using a trusted shuffler to amplify local privacy guarantees into stronger global ones.

A critical technique that boosts the privacy guarantee when training on random subsets of data. By sampling a mini-batch uniformly at random, the probability that any specific individual's data is included is reduced.

• Mechanism: The privacy loss random variable concentrates, effectively multiplying the privacy guarantee.
• Poisson Sampling: The gold-standard method where each example is independently included with a fixed probability, providing tighter amplification than shuffling.
• Benefit: Allows for training with a much lower effective epsilon than the per-iteration noise alone would suggest.

Differential privacy provides a formal upper bound on the success of membership inference attacks, where an adversary attempts to determine if a specific record was used in training.

• Provable Guarantee: An ε-differentially private model limits the adversary's true positive rate and false positive rate to a bounded ratio.
• Empirical Defense: DP-SGD has been shown empirically to drastically reduce attack AUC scores compared to non-private baselines.
• Relation: This is the primary practical security motivation for adopting differential privacy in machine learning.