Sensitivity

The absolute maximum difference in a query's output over all possible pairs of neighboring datasets. It is a worst-case, data-independent measure.

• Definition: (GS_f = \max_{D \sim D'} ||f(D) - f(D')||)
• Mechanism: Used to calibrate noise in the Laplace Mechanism.
• Example: For a counting query, the global sensitivity is always 1.
• Limitation: Can be very large for unbounded functions like sum, requiring excessive noise.

The maximum change in a query's output for a specific, fixed dataset when one record is added or removed. It is a data-dependent measure.

• Definition: (LS_f(D) = \max_{D'} ||f(D) - f(D')||) where (D') is a neighbor of (D).
• Risk: Directly adding noise proportional to local sensitivity can leak information about the dataset.
• Usage: Forms the basis for more advanced, smooth calibration techniques.

An upper bound on local sensitivity that accounts for how much the local sensitivity itself can vary between neighboring datasets. It prevents the information leakage inherent in raw local sensitivity.

• Framework: Defined as (S^*f(D) = \max{D'} (LS_f(D') \cdot e^{-\beta \cdot d(D, D')})).
• Advantage: Allows adding significantly less noise than global sensitivity for queries where the worst-case is rare.
• Example: Used for privately releasing the median of a dataset.

A specific sensitivity metric for scoring functions used in the Exponential Mechanism. It measures the maximum change in a utility score when a single record is modified.

• Definition: (\Delta u = \max_{r \in R} \max_{D \sim D'} |u(D, r) - u(D', r)|).
• Purpose: Calibrates the probability distribution over candidate outputs.
• Key Insight: A candidate's selection probability is exponentially proportional to its utility score divided by this sensitivity.

The sensitivity of the gradient computed on a single training example in deep learning. It is the foundation of Differentially Private Stochastic Gradient Descent (DP-SGD).

• Mechanism: Per-example gradients are computed, and their norms are clipped to a fixed threshold (C).
• Result: The sensitivity of the averaged gradient query becomes bounded by (C).
• Noise: Gaussian noise proportional to (C) is added to the aggregated gradient to achieve differential privacy.

In the Local Differential Privacy (LDP) model, sensitivity defines the maximum influence a user's true value has on the output distribution of the perturbation mechanism they apply locally.

• Contrast: Unlike the central model, sensitivity is applied to a single user's data transformation, not a database query.
• Example: In Randomized Response, the sensitivity relates to the probability of flipping a binary answer.
• Trade-off: LDP mechanisms often require much larger noise scales due to the lack of a trusted aggregator.

A mechanism that achieves the relaxed (ε, δ)-differential privacy guarantee by adding noise from a Gaussian (normal) distribution.

• It is calibrated using the L2 sensitivity of the query, making it more tolerant to high-dimensional queries where L1 sensitivity can be large.
• The standard deviation of the noise is scaled by Δ₂f * √(2ln(1.25/δ)) / ε*.
• It is the workhorse for DP-SGD because the Gaussian noise composes more tightly under repeated iterations than Laplace noise.

A mechanism designed for non-numeric or discrete outputs where the goal is to select the 'best' item from a set of candidates R while preserving privacy.

• It requires a utility function u(D, r) that scores how good a candidate r is for dataset D.
• The sensitivity of this utility function determines the scaling of the exponential distribution.
• Each candidate is selected with a probability proportional to exp(ε * u(D, r) / (2 * Δu)), ensuring that high-utility outputs are exponentially more likely without revealing private details.

The abstract mathematical construct upon which the entire differential privacy definition rests. Two datasets D and D' are considered neighbors if they differ by the presence or absence of a single record.

• Sensitivity is formally defined as the maximum difference in a query's output over all possible pairs of neighboring datasets.
• The 'unit' of protection—whether a single row, a single user's entire contribution, or an event—is determined by how 'neighboring' is defined.
• Unbounded DP defines neighbors by adding/removing a record, while bounded DP defines them by changing one record's value.

The standard algorithm for training deep neural networks with differential privacy guarantees. It modifies standard SGD with two critical steps that rely on sensitivity:

• Per-example gradient clipping: Each individual gradient is scaled down to have an L2 norm bounded by a clipping threshold C. This enforces a finite sensitivity on the batch gradient.
• Noise addition: Calibrated Gaussian noise is added to the sum of clipped gradients before the model update.
• The noise scale is proportional to C, making the clipping norm a critical hyperparameter that directly controls the sensitivity and the privacy-utility trade-off.

A finite, quantifiable resource representing the total allowable privacy loss across all queries to a sensitive dataset. Sensitivity is the fundamental unit of cost for this budget.

• A query with high sensitivity consumes more of the privacy budget than a low-sensitivity query for the same ε.
• The Composition Theorem dictates that the total ε spent is the sum of the ε values of individual mechanisms applied to the same dataset.
• Managing a privacy budget requires precise knowledge of the sensitivity of every query to ensure the cumulative loss does not exceed the pre-defined threshold.