Differential Privacy

The Laplace Mechanism is the foundational algorithm for achieving differential privacy for real-valued queries. It works by adding noise drawn from a Laplace distribution to the true query output. The scale of the noise is calibrated to the sensitivity of the query (Δf) and the desired privacy budget (ε).

• Key Formula: Noisy Output = True Answer + Laplace(Δf / ε)
• Use Case: Ideal for aggregations like counts, sums, and averages where the output is a numeric value.
• Example: Releasing the average salary in a company database while ensuring no individual's data can be inferred. The sensitivity (Δf) is the maximum impact a single record could have on the average.

The Gaussian Mechanism provides (ε, δ)-differential privacy by adding noise drawn from a Gaussian (normal) distribution. It is often used when the Laplace mechanism's noise is too heavy-tailed or when composing many queries.

• Key Difference: Requires a non-zero delta (δ), representing a small probability of privacy failure.
• Noise Scale: The standard deviation of the Gaussian noise is proportional to Δf * sqrt(2 * ln(1.25/δ)) / ε.
• Use Case: Common in deep learning and iterative algorithms like Stochastic Gradient Descent (DP-SGD), where many queries are made on the same dataset.

The Exponential Mechanism is used for queries where the output is not numeric, but a discrete object (e.g., selecting the best option from a set). It works by sampling an output with a probability exponentially weighted by its utility score.

• How it works: Given a set of possible outputs R, the mechanism outputs r ∈ R with probability proportional to exp(ε * utility(r, data) / (2 * Δutility)).
• Sensitivity: Δutility is the maximum change in the utility function from adding or removing one individual's data.
• Use Case: Privately selecting the most frequent item in a dataset, choosing hyperparameters, or releasing a decision rule.

Report Noisy Max is a specific, efficient instance of the Exponential Mechanism used to privately identify the highest-valued option among several candidates. Instead of sampling, it adds noise to each candidate's score and returns the index of the maximum noisy value.

• Process: 1) Calculate a score for each candidate. 2) Add independent Laplace or Gaussian noise to each score. 3) Report the candidate with the highest noisy score.
• Advantage: More computationally efficient than the full Exponential Mechanism when only the top item is needed.
• Use Case: Finding the most common disease diagnosis in a set of patient records or the best-performing model configuration in a private evaluation.

Sensitivity is the core mathematical concept that determines how much noise a mechanism must add. It quantifies the maximum possible change in a query's output when a single individual is added or removed from the dataset.

• Global L1 Sensitivity (Δf): For a function f: Dataset → ℝᵏ, it's defined as Δf = max_{D, D'} ||f(D) - f(D')||₁, where D and D' are neighboring datasets.
• Example: A query counting individuals has a sensitivity of 1. A sum query (e.g., total salary) has a sensitivity equal to the maximum possible salary of one person.
• Role: The noise magnitude in the Laplace and Gaussian mechanisms is directly proportional to Δf. Lower sensitivity allows for less noise and better utility for the same privacy guarantee.

The privacy budget (ε) is a resource that is consumed each time a differentially private mechanism is applied to data. Composition theorems dictate how the budget is spent across multiple queries.

• Sequential Composition: If you run k mechanisms with guarantees (ε₁, δ₁)...(εₖ, δₖ), the total privacy loss is at most (Σεᵢ, Σδᵢ).
• Advanced Composition: Allows for a tighter (better) bound on total epsilon for many queries, often growing with sqrt(k) rather than k.
• Practical Implication: This forces careful budgeting in complex systems like machine learning training, where thousands of gradient updates (queries) are performed. Techniques like the Moment Accountant are used to track the cumulative privacy loss precisely.