Sensitivity

The maximum possible difference in a query's output when computed over any two neighboring datasets differing by exactly one record.

• Definition: GS(f) = max ||f(D) - f(D')|| over all neighboring D, D'.
• Data-independent: Depends only on the query function, not the specific dataset.
• Example: A counting query has GS = 1; a sum query bounded by [0, B] has GS = B.
• Role: Directly scales the noise magnitude in the Laplace mechanism.

The maximum change in a query's output when computed on a specific dataset D and all its neighbors.

• Definition: LS(f, D) = max ||f(D) - f(D')|| for D' neighbors of D.
• Data-dependent: Varies based on the actual values in the dataset.
• Risk: Releasing LS directly can leak information about the dataset.
• Mitigation: Use smooth sensitivity frameworks to compute a safe upper bound on LS without revealing private information.

The choice of distance metric determines which differential privacy mechanism is applicable.

• L1 Sensitivity (Manhattan): Sum of absolute differences across output dimensions. Calibrates the Laplace mechanism for pure ε-differential privacy.
• L2 Sensitivity (Euclidean): Square root of sum of squared differences. Calibrates the Gaussian mechanism for (ε, δ)-differential privacy.
• Selection Rule: L2 sensitivity is always less than or equal to L1, making the Gaussian mechanism often more efficient for high-dimensional queries.

A framework introduced by Nissim, Raskhodnikova, and Smith to safely use data-dependent sensitivity without revealing private information.

• Definition: A function S(f, D) that upper-bounds LS(f, D) and varies smoothly—neighboring datasets cannot have wildly different smooth sensitivity values.
• Noise Calibration: Noise is scaled by S(f, D) rather than GS, enabling significantly less noise for queries where local sensitivity is much smaller than global sensitivity.
• Application: Critical for functions like the median, where GS is unbounded but LS is typically small.

In federated learning, sensitivity bounds the contribution of each client's model update before aggregation.

• Per-Client Clipping: Each local gradient vector is clipped to a maximum L2 norm (C), enforcing a bounded sensitivity of C for the aggregation query.
• Noise Addition: Gaussian noise scaled to C is added by the central server after secure aggregation to achieve differential privacy.
• Trade-off: Smaller C reduces sensitivity and noise but may discard useful gradient information, slowing convergence.

When multiple queries are answered, their sensitivities compose to determine total privacy expenditure.

• Sequential Composition: Answering k queries with sensitivities s₁...sₖ on the same dataset consumes a privacy budget proportional to Σ sᵢ.
• Parallel Composition: Queries on disjoint subsets of the data consume budget proportional to max(sᵢ), not the sum.
• Design Implication: Partitioning data and querying partitions independently is a fundamental strategy for privacy budget conservation.