Differential Privacy

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

• ε = 0: Perfect privacy, but zero utility.
• ε < 1: Strong privacy regime, typical for high-sensitivity data.
• ε > 10: Weak guarantee, minimal protection.

The budget is consumed with each query, enforcing a strict limit on total information leakage.

When multiple differentially private mechanisms are applied to the same dataset, the total privacy loss is the sum of their individual privacy budgets.

• If you run a query with budget ε₁, then another with ε₂, the total guarantee is (ε₁ + ε₂)-differential privacy.
• This property forces a hard limit on the number of analyses permitted on a sensitive dataset.
• It mirrors the intuition that asking too many questions eventually reveals private information.

When differentially private queries are applied to disjoint subsets of a dataset, the total privacy cost is the maximum of the individual budgets, not the sum.

• If a dataset is partitioned by user ID, querying each partition with budget ε results in an overall ε guarantee.
• This property is the foundation of privacy-preserving federated analytics, allowing many simultaneous computations without draining the budget.

Any arbitrary computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. The output is forever safe.

• An adversary cannot 'reverse' the noise by applying a function, no matter how complex.
• This property is crucial for practical systems: you can normalize, round, or visualize DP outputs without fear of compromising the original data.
• It ensures that privacy is a property of the mechanism, not the downstream analysis.

Differential privacy naturally extends to protect groups of size k. A mechanism that is ε-differentially private for a single individual is kε-differentially private for a group of k correlated records.

• This quantifies the increased risk when an adversary targets a family or a cluster of related entries.
• The guarantee degrades linearly with group size, providing a formal way to reason about coalition attacks.

The amount of noise required is determined by the global sensitivity (Δf) of the query function—the maximum change in the output when a single record is added or removed.

• Counting queries: Δf = 1 (low noise).
• Sum queries: Δf = max value in the dataset (potentially high noise).
• Median queries: Δf can be unbounded, requiring alternative smoothing techniques. This calibration ensures the noise masks the presence or absence of any one individual.

The privacy budget quantifies the total allowable privacy loss over a sequence of queries. A smaller epsilon (e.g., ε=0.1) provides stronger privacy but more noise; a larger epsilon (e.g., ε=10) provides weaker privacy but higher accuracy.

• Composition: Budgets accumulate across queries; sequential composition adds epsilons, parallel composition takes the maximum.
• Exhaustion: Once the budget is depleted, no further queries are permitted on that dataset.
• Accounting: Advanced composition theorems and Rényi differential privacy enable tighter budget tracking.

Two deployment models define who injects noise and who is trusted:

• Global DP (Central Model): A trusted curator collects raw data, applies the privacy mechanism, and releases noisy statistics. Provides higher utility at a given epsilon.
• Local DP (LDP): Each user randomizes their own data before sending it to an untrusted aggregator. Used by Apple, Google, and Microsoft for telemetry collection.
• Shuffle Model: An intermediate architecture where a trusted shuffler permutes locally randomized reports to amplify privacy guarantees.

Sensitivity measures the maximum change in a query's output when a single record is added or removed from the dataset. It determines how much noise must be added to achieve a given epsilon.

• L1 Sensitivity (Δf₁): Maximum absolute difference in the query result; used for Laplace mechanism.
• L2 Sensitivity (Δf₂): Maximum Euclidean distance; used for Gaussian mechanism.
• Smooth Sensitivity: A framework for queries where global sensitivity is too large, using local sensitivity with a smoothing function to avoid leaking information.

Rényi differential privacy is a relaxation based on the Rényi divergence that provides tighter composition bounds than pure ε-DP, especially for iterative algorithms like DP-SGD.

• Uses a moment accountant to track privacy loss across training steps.
• Converts to standard (ε, δ)-DP bounds for final reporting.
• Enables practical deep learning with differential privacy by reducing the total noise required for a given privacy guarantee.
• Forms the theoretical backbone of Opacus and TensorFlow Privacy.

The workhorse algorithm for training deep neural networks with differential privacy guarantees. DP-SGD modifies standard SGD in two critical steps:

• Gradient Clipping: Each per-example gradient is clipped to a maximum L2 norm C to bound sensitivity.
• Noise Addition: Gaussian noise calibrated to the clipping norm and privacy budget is added to the averaged gradient before the parameter update.
• Moment Accountant: Tracks cumulative privacy loss across training iterations using Rényi DP composition.

A fundamental property of differential privacy: any computation applied to the output of a differentially private mechanism does not degrade the privacy guarantee. Once noise is injected, an adversary cannot increase privacy loss through arbitrary post-processing.

• Enables safe release of DP statistics for downstream analysis.
• Allows model checkpoints from DP-SGD training to be shared without additional privacy risk.
• Does not apply if the post-processor has access to the original raw data.
• Formally: If M satisfies ε-DP, then f(M(x)) also satisfies ε-DP for any function f.