Differential Privacy

The core parameter epsilon (ε) quantifies the maximum allowable privacy loss. A smaller ε provides stronger privacy guarantees but typically reduces the utility (accuracy) of the output. The mechanism is designed so that the probability of any output changes by at most a factor of e^ε whether any single individual's data is included or excluded from the dataset.

• ε = 0.1: Very strong privacy, low utility.
• ε = 1.0: Common balance for many applications.
• ε = 10.0: Weaker privacy, higher utility. The budget is consumed with each query; once exhausted, no further queries can be answered without violating the guarantee.

These are the primary randomized algorithms for achieving differential privacy by adding calibrated noise to query outputs.

• Laplace Mechanism: Adds noise drawn from a Laplace distribution. Ideal for counting queries and queries with low sensitivity (the maximum change a single record can cause). The scale of the noise is Δf / ε, where Δf is the sensitivity.
• Gaussian Mechanism: Adds noise from a Gaussian (normal) distribution. Used for high-dimensional queries like machine learning gradients. It requires a slightly relaxed (ε, δ)-differential privacy guarantee, where δ is a small probability of privacy failure.

These rules govern how privacy loss accumulates when multiple differentially private analyses are performed on the same dataset.

• Sequential Composition: The epsilons of k sequential queries add up. Total ε = ε₁ + ε₂ + ... + εₖ. This is why a privacy budget must be managed.
• Advanced Composition: Provides a tighter bound for the cumulative privacy loss, especially for many queries (k is large), often yielding a total ε that grows roughly with √k.
• Parallel Composition: If queries are performed on disjoint subsets of the data, the overall privacy loss is only the maximum ε used on any one subset, not the sum.

Differential privacy can be applied in two fundamental architectural models.

• Local Model: Each user adds noise to their own data before sending it to the data collector. Provides the strongest user-side privacy, as the collector never sees raw data. Used in Google's RAPPOR for browser data collection. Typically requires more noise per user, reducing aggregate accuracy.
• Central Model: Users send raw (or encrypted) data to a trusted curator. The curator applies the differentially private algorithm to the complete dataset and releases the noisy result. This model allows for much higher accuracy for the same ε but requires trust in the curator.

The standard algorithm for training machine learning models with differential privacy guarantees.

Key modifications to standard SGD:

1. Per-example Gradient Clipping: The gradient for each training example is clipped to a maximum L2 norm C. This bounds the sensitivity of the model update.
2. Noise Addition: Gaussian noise is added to the average of the clipped gradients in each training batch.
3. Privacy Accounting: A tool like the Moment Accountant or GDP Accountant is used to precisely track the cumulative (ε, δ) privacy budget spent over all training steps. This is foundational for private model training in frameworks like TensorFlow Privacy.

A crucial property that any function applied to the output of a differentially private mechanism cannot weaken its privacy guarantee.

• Implication: Analysts can freely perform additional computations, create visualizations, or build secondary models on top of a differentially private output without needing further privacy analysis.
• Example: A DP query releases a noisy count of patients with a condition. An analyst can then safely calculate a derived statistic, like a percentage of the total (using another DP total), or feed the noisy count into a non-private forecasting model. The final result remains (ε, δ)-differentially private. This property enables flexible and complex data workflows while maintaining the core guarantee.

A quantifiable, cumulative limit on the amount of privacy loss an individual can incur from their data's inclusion in a differentially private analysis. The parameter epsilon (ε) directly controls the strength of the privacy guarantee.

• Mechanism: Each query consumes a portion of the budget. Once exhausted, no further queries are permitted, preventing privacy loss accumulation.
• Engineering Implication: System designers must implement privacy accounting to track budget consumption across all analyses, a critical component of production DP systems.

Two fundamental models defining where noise is added in the data pipeline.

• Local Differential Privacy: Noise is added to an individual's data on their device before it is sent to a central collector. This provides a stronger trust model (untrusted server) but typically requires more noise per individual, reducing aggregate utility.
• Central Differential Privacy: Trusted curator collects raw data and applies noise after aggregation. This provides better utility for the same privacy guarantee but requires trust in the data curator.
• Choice: Dictates system architecture and trust assumptions for multi-agent data collection.