Sensitivity Analysis

L1 Sensitivity, also called Global Sensitivity, is the most common measure. It is defined for a function f that maps a dataset to a real number (e.g., a count or sum). Formally, for any two neighboring datasets D and D' that differ in at most one record, the L1 sensitivity Δf is:

Δf = max_{D, D'} ||f(D) - f(D')||_1

• Key Insight: It represents the worst-case change. For a simple database query like "COUNT the number of patients with a disease," the sensitivity is 1, because adding or removing one patient can change the count by at most 1.
• Determines Noise Scale: In the Laplace Mechanism, noise is drawn from a Laplace distribution with scale Δf / ε. A higher sensitivity requires more noise to obscure the individual's contribution.

L2 Sensitivity is an alternative measure used primarily with the Gaussian Mechanism for achieving (ε, δ)-differential privacy. It is defined similarly but uses the L2 norm (Euclidean distance):

Δ₂f = max_{D, D'} ||f(D) - f(D')||_2

• Use Case: The Gaussian mechanism adds noise scaled to Δ₂f * √(2ln(1.25/δ)) / ε. For queries that output a single real number, L1 and L2 sensitivity are identical. The distinction becomes critical for vector-valued queries (e.g., releasing a histogram or multiple model weights).
• Practical Advantage: For some complex functions, the L2 sensitivity can be significantly lower than the L1 sensitivity, allowing for less noise to be added while achieving the same (ε, δ) privacy guarantee.

A critical distinction in sensitivity analysis is between Global and Local sensitivity.

• Global Sensitivity (Δf): The maximum change over all possible neighboring datasets. This is a worst-case, data-independent bound. It is required for standard mechanisms like Laplace and Gaussian.
• Local Sensitivity (LS_f(D)): The maximum change for a specific input dataset D and its neighbors. It is data-dependent and often much smaller than the global bound.

The Challenge: Using local sensitivity directly can leak information about the underlying dataset. Advanced techniques like the Propose-Test-Release framework or Smooth Sensitivity are used to safely calibrate noise based on local sensitivity without violating the privacy guarantee.

Calculating sensitivity is the first engineering step in applying differential privacy. Here are canonical examples:

• Count Query: f(D) = COUNT(records satisfying condition). Sensitivity = 1.
• Sum Query: f(D) = SUM(values). If each individual's contribution is bounded in [a, b], sensitivity = b - a. For example, if one person's salary contribution is between $0 and $200,000, sensitivity = 200,000.
• Mean / Average Query: The mean is a ratio: SUM / COUNT. It must be computed privately as two separate queries (a private sum and a private count) because its sensitivity can be unbounded.
• Histogram Query: For a histogram over k bins, where each individual contributes to exactly one bin, the sensitivity is 1 in the L1 norm (changing one person moves their count from one bin to another).
• Machine Learning Gradients: For a model trained with DP-SGD, sensitivity is calculated by clipping each per-example gradient to a maximum L2 norm C. The sensitivity for the batch average gradient is then C / batch_size.

The Laplace Mechanism is the canonical algorithm for achieving pure ε-differential privacy on numeric queries. Its operation is directly governed by sensitivity.

Mechanism Definition: Given a function f with L1 sensitivity Δf, the mechanism outputs: M(D) = f(D) + Lap(Δf / ε) where Lap(b) is noise sampled from a Laplace distribution with scale b and mean 0.

• Noise Scaling: The scale parameter b = Δf / ε creates the fundamental privacy-utility trade-off.
  • High Sensitivity or Low Epsilon (strong privacy): Large b means large, utility-destroying noise.
  • Low Sensitivity or High Epsilon (weaker privacy): Small b means less noise and a more accurate answer.
• Example: A count query (Δf=1) with ε=1.0 adds noise from Lap(1). With ε=0.1 (stronger privacy), noise is drawn from Lap(10), which is ten times larger.

Smooth Sensitivity is an advanced framework for using data-dependent local sensitivity safely. Developed by Nissim, Raskhodnikova, and Smith, it allows for adding noise proportional to a smooth upper bound on the local sensitivity, which can be much lower than the global sensitivity.

• Core Idea: Instead of using the global maximum Δf, it uses a smooth function S_f(D) that:
  1. Is an upper bound on the local sensitivity LS_f(D).
  2. Does not change too quickly between neighboring datasets (is "β-smooth").
• Benefit: For functions where local sensitivity varies greatly (e.g., the median of a dataset), smooth sensitivity can enable the addition of far less noise than the global sensitivity approach, while still providing differential privacy.
• Application: It is often used with noise distributions like the Cauchy or Gaussian, rather than Laplace, to achieve the necessary tail properties for the proof of privacy.

The simplest and most common case. A counting query asks 'how many records satisfy property P?'.

• Sensitivity: 1. Adding or removing one record can change the count by at most 1.
• Example: 'How many patients in the dataset were diagnosed with Condition X?' The result can change by at most ±1 if one patient's record is added or removed.
• Noise Scaling: For pure (ε,0)-differential privacy, noise is drawn from a Laplace distribution with scale parameter b = 1/ε.

A summation query calculates the total of a numeric attribute (e.g., total salary, total dosage).

• Sensitivity: The maximum possible absolute value of the attribute being summed.
• Example: Query: 'Total annual salary of employees in Department Y.' If the maximum possible salary is $500,000, the global sensitivity Δf = 500,000. Adding a new employee with that maximum salary increases the sum by $500k; removing them decreases it by the same amount.
• Critical Note: Sensitivity is a worst-case, global bound, not based on the actual data present. It must be defined by the data curator before analysis.

Calculating a mean (average) is a ratio of a sum and a count. Applying differential privacy directly to the mean is complex and unstable.

• Standard Approach: Compute the differentially private sum and the differentially private count separately, then take their ratio.
• Sensitivity: Inherits from the sum and count components. The sum's sensitivity is the max attribute value; the count's sensitivity is 1.
• Example: 'Average age of participants.' First, get DP total of all ages (sensitivity = max possible age, e.g., 120). Second, get DP count of participants (sensitivity = 1). Divide the noisy results. This two-step process correctly accounts for the privacy cost of both queries via composition theorems.

A histogram is a vector of counts, where each bin counts records falling into a specific category or range.

• Sensitivity: 1 in the L1 norm (sum of absolute changes). Adding/removing one record affects exactly one bin's count by ±1.
• Example: A histogram of patient ages grouped into decades (0-9, 10-19, etc.). One patient belongs to exactly one bin. Their record changes one bin's count by 1, leaving all others unchanged. The total change across the vector is 1.
• Noise Addition: Independent Laplace noise with scale 1/ε is added to each bin. The L1 sensitivity ensures the combined release satisfies ε-differential privacy.

In differentially private stochastic gradient descent (DP-SGD), sensitivity analysis is applied to model gradients during training.

• Per-Example Gradient Clipping: The core mechanism. The gradient vector computed on a single training example is clipped to a maximum L2 norm, C.
• Sensitivity: The clipping norm C becomes the sensitivity bound for the gradient update. A single example's contribution to the averaged gradient is bounded by C.
• Noise Addition: Gaussian noise scaled to C is added to the averaged gradient before the model update step, providing (ε, δ)-privacy. This prevents the model from overfitting to the unique features of any individual's data.

Global Sensitivity (Δf) is the worst-case change over any pair of neighboring datasets. It's safe but often overly conservative.

• Local Sensitivity is the change for the specific dataset at hand, which can be much smaller.
• Problem: Using local sensitivity directly can leak information about the dataset. Solutions like the Propose-Test-Release framework or smooth sensitivity allow for noise addition scaled to a slightly smoothed version of local sensitivity, offering better utility while maintaining formal privacy guarantees.
• Example: A query for 'maximum salary' might have a very high global sensitivity (max possible salary), but on a specific dataset, the local sensitivity might be the gap between the top two salaries. Smooth sensitivity provides a safe way to exploit this smaller bound.

A formal mathematical framework that provides a quantifiable guarantee of privacy. It ensures the output of a data analysis is statistically indistinguishable whether any single individual's data is included or excluded. This is the foundational theory that defines the need for sensitivity analysis.

• Core Property: The algorithm's output distribution is nearly identical on any two datasets differing by one record.
• Quantification: Privacy loss is measured by parameters epsilon (ε) and delta (δ).
• Application: Used in census data release, tech company analytics, and federated learning.

The fundamental algorithm for achieving pure (ε, 0)-differential privacy for numeric queries. It adds noise scaled to the sensitivity of the query.

• Mechanism: For a query f with sensitivity Δf, output f(D) + Lap(Δf/ε).
• Noise Distribution: Uses the Laplace distribution, which is heavy-tailed.
• Direct Dependency: The amount of noise added is directly proportional to the global sensitivity. A higher sensitivity requires more noise for the same ε guarantee.

An algorithm for achieving (ε, δ)-differential privacy, a relaxed form that allows a small probability δ of privacy violation. It adds Gaussian noise.

• Mechanism: Adds noise drawn from N(0, σ²), where σ is scaled to the sensitivity and privacy parameters.
• Trade-off: For the same sensitivity, typically allows for less noise than the Laplace mechanism but introduces the δ parameter.
• Use Case: Preferred for queries where the Laplace noise's heavy tails are problematic, or for deep learning.

A cumulative, trackable limit on the total privacy loss permitted for an individual across multiple analyses on a dataset. Epsilon (ε) is the primary currency of this budget.

• Accounting: Composition theorems track how sequential queries consume the budget.
• Sensitivity's Role: The cost of each query in epsilon is determined by its sensitivity and the noise mechanism used. A high-sensitivity query consumes more budget.
• Management: Systems must track total ε expenditure to prevent privacy exhaustion.

Formal rules that calculate the cumulative privacy loss when multiple differentially private mechanisms are applied to the same dataset.

• Basic Composition: The epsilons of k mechanisms simply add up: ε_total = ε₁ + ε₂ + ... + εₖ.
• Advanced Composition: Provides a tighter (better) bound, allowing for ε_total to grow roughly with √k under certain conditions.
• Critical Function: Enables the design of complex, multi-step data analyses while maintaining a known total privacy guarantee, relying on each step's sensitivity.

The fundamental tension in privacy-preserving analysis: increasing privacy protection (e.g., adding more noise) reduces the accuracy or utility of the released output.

• Central Conflict: Sensitivity is the pivotal variable in this trade-off.
• Low Sensitivity: Allows for strong privacy (low ε) with relatively high utility (less noise).
• High Sensitivity: Forces a difficult choice: accept high noise (low utility) for strong privacy, or accept weaker privacy (higher ε) for usable accuracy.