Sensitivity

The maximum possible difference in a query's output over all possible neighboring datasets, regardless of the specific data distribution.

• Definition: GS(f) = max ||f(D) - f(D')|| over all adjacent D, D'
• Worst-case bound: Provides a guarantee that holds for any possible dataset
• Noise calibration: The Laplace mechanism scales noise directly to GS/ε
• Example: For a counting query, GS = 1; for a sum query with values bounded in [0, B], GS = B

The maximum change in query output for a specific, fixed dataset D, considering only its immediate neighbors.

• Definition: LS(f, D) = max ||f(D) - f(D')|| for D' adjacent to D
• Data-dependent: Can be much smaller than global sensitivity for well-behaved datasets
• Direct use is unsafe: Releasing LS itself can leak information about the data
• Smooth sensitivity is a refined variant that adds a safety margin to LS to prevent leakage

The choice of norm used to measure sensitivity directly determines which noise distribution is appropriate.

• L1 Sensitivity: Sum of absolute differences across all output dimensions. Used with the Laplace mechanism for pure ε-DP
• L2 Sensitivity: Euclidean (root sum-of-squares) distance. Used with the Gaussian mechanism for (ε, δ)-DP
• Practical impact: L2 sensitivity is often smaller in high-dimensional outputs, requiring less noise
• Example: For a histogram query, L1 sensitivity = 2 (one entry removed, one added); L2 sensitivity = √2

Understanding the sensitivity of standard database operations is critical for practical implementation.

• Count queries: GS = 1 — adding or removing one record changes a count by at most 1
• Sum queries: GS = B, where B is the upper bound on individual contributions
• Average queries: GS = B/n, but requires knowing n in advance; often decomposed into noisy sum / noisy count
• Histogram queries: GS = 1 for disjoint bins (L1); each record affects exactly one bin
• Gradient queries (DP-SGD): Sensitivity controlled by gradient clipping to a fixed L2 norm C

Sensitivity is the multiplier that translates privacy budget ε into noise magnitude, directly governing the privacy-utility frontier.

• Noise scale: Laplace noise ~ GS/ε; Gaussian noise ~ GS · √(2 ln(1.25/δ)) / ε
• High sensitivity → high noise: Queries with large GS require more noise, degrading accuracy
• Mitigation strategies:
  • Clipping: Bound per-record contributions to reduce sensitivity
  • Query decomposition: Break complex queries into lower-sensitivity sub-queries
  • Relaxing to (ε, δ)-DP: Allows L2 sensitivity and Gaussian noise, often more efficient

When differential privacy is applied repeatedly, sensitivity compounds according to the composition theorem.

• Sequential composition: Total privacy cost = sum of individual ε values; sensitivity bounds apply per-iteration
• DP-SGD: Per-example gradient clipping bounds the L2 sensitivity of each training step to C
• Moments accountant: Tracks cumulative privacy loss more tightly than simple composition, critical for deep learning
• Amplification by subsampling: Randomly sampling a batch reduces effective sensitivity, strengthening the privacy guarantee