Differential Privacy (DP)

The Laplace Mechanism is the foundational algorithm for achieving pure ε-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 (its variance) is calibrated to the query's L1 sensitivity divided by ε. For a function f with L1 sensitivity Δf, the mechanism releases f(D) + Lap(Δf/ε). This ensures that the probability of any output changes by at most a factor of e^ε when a single individual's data is modified.

The Gaussian Mechanism is used to achieve the relaxed (ε, δ)-differential privacy guarantee. It adds noise drawn from a Gaussian (normal) distribution to the query result. The noise scale is proportional to the query's L2 sensitivity and the desired (ε, δ) parameters. This mechanism is particularly useful for high-dimensional vector outputs, like gradients in machine learning, because the L2 norm is often easier to bound. The Gaussian mechanism enables more practical utility-privacy trade-offs, especially under composition, but introduces the small failure probability δ.

The Exponential Mechanism provides differential privacy for selecting a high-utility item from a discrete set (not just outputting a number). It works by assigning a utility score to each possible output in the set. The mechanism then randomly selects an output with a probability exponentially proportional to its utility score and the privacy parameter ε. Formally, the probability of choosing output r is proportional to exp(ε * u(D, r) / (2Δu)), where u is the utility function and Δu is its sensitivity. This is essential for private decision-making, like choosing the best candidate from a list.

Randomized Response is a simple, classic technique that achieves Local Differential Privacy (LDP). In this client-side model, an individual perturbs their own sensitive binary answer before sending it to an untrusted curator. A common scheme: flip a coin; if heads, answer truthfully; if tails, flip another coin and answer 'Yes' or 'No' randomly. By knowing the randomization probabilities, the analyst can later debias the aggregated statistics. This mechanism is powerful for its simplicity and strong client-side privacy, forming the basis for many LDP data collection systems.

In differentially private machine learning, specifically DP-SGD, the core mechanism involves two steps applied during training:

• Per-Example Gradient Clipping: The L2 norm of each training example's gradient is computed and clipped to a maximum threshold C. This bounds the L2 sensitivity of the batch gradient sum.
• Noisy Aggregation: Calibrated Gaussian noise is added to the sum (or average) of the clipped gradients for the batch. The noise scale is σ * C, where σ is a multiplier determined by the target (ε, δ) and the sampling rate. This process, repeated each iteration, ensures the final model parameters satisfy differential privacy.

Real-world analyses involve multiple queries. Composition Theorems are the mathematical rules that dictate how the overall privacy guarantee degrades when multiple DP mechanisms are applied to the same data. Key types include:

• Basic Composition: The ε parameters simply add up for sequential composition (ε_total = k * ε).
• Advanced Composition: Provides tighter bounds, allowing for ε_total ≈ ε * sqrt(2k log(1/δ')) for (ε, δ)-DP mechanisms. Privacy Accounting (e.g., using the Moment Accountant or Rényi DP) is the process of tracking these cumulative (ε, δ) bounds across an entire training run or set of queries to ensure a pre-defined privacy budget is not exceeded.

Epsilon (ε) is the primary privacy loss parameter in differential privacy. It quantifies the maximum allowable multiplicative difference in the probability of any output between two adjacent datasets (differing by one record). A smaller ε indicates a stronger privacy guarantee, as it tightly bounds how much an adversary can learn about an individual's presence in the data. In practice, ε is a tunable knob: values like 0.1, 1.0, or 8.0 represent different trade-offs between privacy and model utility.

The Laplace Mechanism is a foundational algorithm for achieving pure ε-differential privacy. It works by adding noise drawn from a Laplace distribution to the output of a numeric function (e.g., a query count or average). The scale of the noise is calibrated to the function's L1 sensitivity (Δf), divided by ε: Noise ~ Laplace(0, Δf/ε). This ensures that the noise is just enough to mask the contribution of any single individual. It is the canonical mechanism for releasing private counts and real-valued statistics.

A privacy budget is a finite allocation of ε (and sometimes δ) for an entire analysis. Each query or training step consumes a portion of this budget. Privacy accounting is the rigorous process of tracking this cumulative consumption across multiple, potentially adaptive, operations to ensure the total privacy loss does not exceed the pre-defined budget. Methods like the Basic Composition Theorem (linear budget sum) or the Advanced Composition Theorem (more favorable sqrt(k) scaling for k queries) and the Moment Accountant (used in DP-SGD) are essential for practical deployment.

Differentially Private Stochastic Gradient Descent (DP-SGD) is the standard algorithm for training machine learning models with differential privacy. It modifies standard SGD with two key steps per training batch:

• Per-example Gradient Clipping: Each sample's gradient norm is bounded by a clip threshold (C) to limit its L2 sensitivity.
• Noisy Gradient Averaging: Calibrated Gaussian noise is added to the sum of the clipped batch gradients. The scale of the noise is proportional to C and the chosen privacy parameters (ε, δ). DP-SGD enables the training of private deep learning models, such as those used in federated learning via DP-FedAvg.

These terms define where privacy is applied in the data pipeline.

• Local Differential Privacy (LDP): Each data owner perturbs their own data locally using a DP mechanism (e.g., Randomized Response) before sending it to an untrusted curator. This provides a strong, client-side guarantee but often requires more noise per individual.
• Central Differential Privacy: A trusted curator holds the raw dataset and applies a DP mechanism (like the Laplace or Gaussian mechanism) before releasing any query results or aggregate statistics. This model typically yields higher utility for the same privacy guarantee but requires trust in the central entity. Federated learning often implements a hybrid, applying local noise for an aggregate central guarantee.

Sensitivity is the maximum possible change in the output of a function when a single individual's data is added or removed from the dataset. It is the cornerstone for calibrating noise in DP mechanisms.

• L1 Sensitivity (Δ₁f): The maximum absolute change, used for the Laplace Mechanism.
• L2 Sensitivity (Δ₂f): The maximum Euclidean norm change, used for the Gaussian Mechanism. For example, a counting query ("how many records satisfy property P?") has an L1 sensitivity of 1. Bounding sensitivity via techniques like gradient clipping is a critical step in private ML training.