Sensitivity (L1, L2)

L1 sensitivity (Δ₁f) is defined as the maximum absolute change in the output of a function f when a single individual's data is added or removed from the dataset, measured using the L1 norm (Manhattan distance).

• Formula: Δ₁f = max_{D, D'} ||f(D) - f(D')||₁, where D and D' are neighboring datasets.
• Primary Use: Determines the scale of Laplace noise for pure ε-differential privacy. The noise added is drawn from Laplace(Δ₁f / ε).
• Example: For a counting query (e.g., "How many patients have a condition?"), the L1 sensitivity is 1, as adding or removing one patient changes the count by at most 1.

L2 sensitivity (Δ₂f) is the maximum change in the function's output measured using the L2 norm (Euclidean distance).

• Formula: Δ₂f = max_{D, D'} ||f(D) - f(D')||₂.
• Primary Use: Determines the scale of Gaussian noise for (ε, δ)-differential privacy. The noise variance is scaled by (Δ₂f * √(2 log(1.25/δ)) / ε)².
• Key Difference: The L2 norm is influenced by the dimensionality of the output. For a d-dimensional vector, the L2 sensitivity can be up to √d times larger than the L1 sensitivity for the same per-coordinate change.

For unbounded functions like gradient computations, sensitivity must be artificially bounded using clipping. This is a prerequisite for applying differential privacy mechanisms.

• Process: A clip threshold C is chosen. Each individual's contribution (e.g., a gradient vector) is scaled down if its norm exceeds C.
• L2 Clipping: If ||g||₂ > C, the gradient is replaced by g * (C / ||g||₂). This ensures the L2 sensitivity of the per-example gradient is bounded by C.
• Trade-off: Clipping introduces bias but is necessary to define a finite sensitivity and control the variance of the added noise.

In Differentially Private Federated Averaging (DP-FedAvg), sensitivity is defined at the client level. The goal is to hide whether any single client participated in a training round.

• Client Update as Function: The function f maps a client's local dataset to a model update (e.g., weight delta).
• Bounding the Update: Each client clips their local model update to a maximum L2 norm C before adding Gaussian noise. This C becomes the L2 sensitivity for the client's contribution.
• Server-Side Aggregation: The server aggregates the noised updates. The calibrated noise ensures the aggregated model does not reveal any single client's data.

Sensitivity (Δ) and the privacy parameters (ε, δ) have a direct, inverse relationship that governs the noise scale.

• Laplace Mechanism: Noise scale = Δ₁f / ε. For strong privacy (small ε), more noise is required. Sensitivity sets the baseline magnitude.
• Gaussian Mechanism: Noise scale ∝ Δ₂f / ε. The relationship also involves δ, the probability of privacy failure.
• Core Principle: Higher sensitivity necessitates more noise to achieve the same (ε, δ) guarantee, which typically reduces the utility (accuracy) of the released output.

Global sensitivity is the worst-case change over all possible neighboring datasets, as defined above. It is the standard for most DP mechanisms.

• Local sensitivity measures the change for a specific input dataset, not all possible ones. It is often smaller but releasing it directly can leak information about the dataset.
• Smooth Sensitivity is an advanced framework that allows adding noise proportional to a smoothed upper bound of local sensitivity, enabling private release for functions with very low local but high global sensitivity (e.g., median).
• Practical Use: Most federated learning implementations rely on the more conservative global sensitivity derived from clipping.

A counting query asks 'How many individuals in the dataset satisfy property P?' (e.g., 'Have disease X?').

• Function: f(D) = count of records with property P in dataset D.
• Sensitivity Analysis: Adding or removing one person's record can change the count by at most 1.
• Result: The global sensitivity Δf = 1. This is technically L∞ sensitivity, as the output is a scalar. The Laplace mechanism would add noise scaled to 1/ε.

Calculating a mean requires bounding the data domain to achieve finite sensitivity.

• Function: f(D) = (sum of incomes in D) / (number of records in D).
• Assumption: All personal incomes are known to be within a range [a, b] (e.g., $0 to $1,000,000).
• Sensitivity Analysis: The numerator (sum) has sensitivity = (b - a). The denominator (count) has sensitivity = 1. The sensitivity of the ratio is complex, so privacy is typically achieved by making the query vector-valued: f(D) = [sum(D), count(D)]. The L1 sensitivity of this vector is (b - a) + 1.

In DP-FedAvg or DP-SGD, sensitivity bounds the contribution of any one training example or client.

• Function: The model update (e.g., gradient) computed on a client's local dataset.
• Mechanism: Gradient Clipping is applied. Each client's update vector g is replaced with g / max(1, ||g||₂ / C), where C is the clip threshold.
• Sensitivity Analysis: After clipping, the L2 norm of any single client's update is at most C. Therefore, the L2 sensitivity Δ₂f = C. The Gaussian mechanism adds noise scaled to C * σ, where σ is derived from (ε, δ).

Publishing a histogram showing counts across multiple categories (e.g., disease prevalence by region) is a common database query.

• Function: f(D) returns a k-dimensional vector where the i-th entry is the count of records in D belonging to category i.
• Sensitivity Analysis: Adding or removing one person's record changes exactly one bin's count by 1. The L1 norm of this change vector is 1 (0+0+...+1+...+0).
• Result: The L1 sensitivity Δ₁f = 1. Independent Laplace noise with scale 1/ε is added to each bin count.

Many queries are linear: f(D) = Q * D, where Q is a query matrix and D is the data vector.

• Example: Calculating total sales per product category from individual transaction data.
• Sensitivity Analysis: The sensitivity depends on the norm used to measure change in D (often L1) and the norm used to measure change in output.
• Key Formula: For a query matrix Q, the L2 sensitivity Δ₂f is the maximum L2 norm of the columns of Q. This directly informs the noise magnitude required for the Gaussian mechanism.

The definition of sensitivity is identical in local and central differential privacy models, but its application differs.

• Central DP: Sensitivity is calculated for the global function f run by the trusted curator on the entire dataset (D). Noise scaled to Δf is added to the true output f(D).
• Local DP (LDP): Each user applies the randomized mechanism M to their own single data point. The sensitivity here is defined for the user's response function, often bounded by the design of the mechanism (e.g., Randomized Response). The privacy guarantee holds for the individual's data release, not a centralized query.

A formal, mathematical framework for quantifying and bounding the privacy loss incurred by an individual when their data is included in a computation. It provides a rigorous worst-case guarantee that the presence or absence of any single record in a dataset does not significantly change the probability distribution of the algorithm's output.

• Core Promise: An adversary, seeing the algorithm's output, should learn roughly the same thing whether any individual's data was included or not.
• Relation to Sensitivity: The sensitivity of the target function (query or gradient) directly determines the magnitude of noise required to achieve a given DP guarantee.

A fundamental algorithm for achieving pure ε-differential privacy. It adds noise drawn from a Laplace distribution to the true output of a numeric function. The scale of the noise is calibrated to the function's L1 sensitivity and the desired privacy parameter ε.

• Mechanism: For a function f with L1 sensitivity Δf, the mechanism releases f(D) + Lap(Δf/ε).
• Use Case: Ideal for queries where the maximum absolute change (L1 norm) is the natural bound, such as counting queries or aggregations where a single record can change multiple coordinates by a fixed amount.

The primary algorithm for achieving (ε, δ)-differential privacy, a slightly relaxed but often more practical guarantee. It adds noise drawn from a Gaussian (normal) distribution to the function's output. The noise variance is proportional to the square of the function's L2 sensitivity and depends on both ε and δ.

• Mechanism: For a function f with L2 sensitivity Δ₂f, the mechanism releases f(D) + N(0, σ²), where σ is calibrated to Δ₂f, ε, and δ.
• Use Case: Ubiquitous in private machine learning (e.g., DP-SGD) because gradient vectors are high-dimensional and their Euclidean norm (L2) is the natural quantity to bound via clipping.

A mandatory preprocessing step in differentially private optimization (like DP-SGD or DP-FedAvg) that enforces a finite sensitivity bound. It limits the influence of any single training example by bounding the norm of its gradient.

• Process: For each per-example gradient g, compute its L2 norm ||g||₂. If ||g||₂ > C, replace g with g * (C / ||g||₂).
• Role: The clip threshold C becomes the effective L2 sensitivity for the gradient-averaging function. This bounded sensitivity (C) is then used to calibrate the Gaussian noise added during aggregation.

A finite resource, quantified by the privacy parameters ε (epsilon) and δ (delta), that is consumed each time a differentially private mechanism accesses the data. The total budget over all analyses must be managed and not exceeded.

• ε (Epsilon): The primary privacy loss parameter. A smaller ε means stronger privacy (less allowed leakage). It directly scales the noise: Noise ∝ Sensitivity / ε.
• δ (Delta): A small probability that the pure ε guarantee might fail. It is typically set to a cryptographically small value (e.g., 1e-5 or less than 1/number_of_samples).
• Relation to Sensitivity: For a fixed budget (ε, δ), a function with higher sensitivity requires more noise, reducing output utility.

The process of meticulously tracking the cumulative privacy loss (ε, δ) across multiple, potentially adaptive, queries or training iterations. It ensures the total expenditure does not surpass the allocated privacy budget.

• Core Challenge: Privacy loss composes; multiple private releases leak more information than a single one. Accounting methods like Advanced Composition, Rényi DP (RDP), or the Moment Accountant provide tight bounds on this composition.
• Dependence on Sensitivity: Every application of a mechanism consumes budget based on the sensitivity of the query and the noise added. Accurate accounting is impossible without a precise, proven bound on sensitivity for each step.