Differential Privacy (DP)

The primary parameter controlling the strength of the privacy guarantee. A smaller epsilon represents stronger privacy but lower data utility.

• Definition: The multiplicative bound on the change in output probability when a single record is added or removed.
• Typical Values: ε = 0.1 to 1.0 for strong privacy; ε = 10+ for weak privacy.
• Interpretation: With ε=0.1, an adversary's ability to infer anything about an individual changes by at most ~10%.
• Composition: Epsilon values accumulate across multiple queries, requiring careful privacy accounting to track total expenditure.

A relaxation parameter that allows the pure ε-differential privacy guarantee to fail with probability δ. This defines (ε, δ)-differential privacy or approximate differential privacy.

• Definition: The probability that the privacy loss exceeds the ε bound.
• Requirement: δ must be cryptographically small, typically much less than 1/N where N is the dataset size.
• Gaussian Mechanism: Requires δ > 0; the Laplace mechanism achieves pure ε-differential privacy with δ = 0.
• Practical Impact: Allows much tighter noise calibration, making it the standard for deep learning with DP-SGD.

The maximum influence a single record can have on the output of a query function. Sensitivity determines the noise magnitude required to achieve a given ε.

• Global Sensitivity (GS): The worst-case change over all possible neighboring datasets.
• Local Sensitivity (LS): The maximum change specific to a given dataset instance.
• L1 Sensitivity: Used for calibrating Laplace noise; the maximum L1 norm difference.
• L2 Sensitivity: Used for calibrating Gaussian noise; the maximum L2 norm difference.
• Clipping: In DP-SGD, per-sample gradients are clipped to bound sensitivity before adding noise.

The foundational mechanism for achieving pure ε-differential privacy on numerical queries. It adds noise drawn from the Laplace distribution calibrated to the query's L1 sensitivity.

• Noise Scale: b = Δf / ε, where Δf is the L1 sensitivity.
• Property: Satisfies (ε, 0)-DP with no failure probability.
• Use Case: Ideal for simple aggregate statistics like counts, sums, and histograms.
• Limitation: For high-dimensional outputs, the Gaussian mechanism often provides better utility due to the tail properties of the Laplace distribution.

Adds noise drawn from a Gaussian (normal) distribution to achieve (ε, δ)-approximate differential privacy. It is the workhorse of modern DP machine learning.

• Noise Scale: σ = (Δf * √(2 * ln(1.25/δ))) / ε, where Δf is the L2 sensitivity.
• Advantage: Scales better to high-dimensional outputs than the Laplace mechanism.
• DP-SGD Foundation: The Gaussian mechanism is applied to clipped gradients in Differentially Private Stochastic Gradient Descent.
• Privacy Amplification: Subsampling data batches before applying the Gaussian mechanism amplifies the privacy guarantee.

A critical technique where randomly sampling a subset of data before applying a DP mechanism yields a stronger overall privacy guarantee than processing the full dataset.

• Mechanism: Each individual has only a probability q of participating in any given training step.
• Amplification Effect: Reduces the effective epsilon by a factor proportional to the sampling rate.
• DP-SGD Integration: Standard minibatch SGD naturally provides this amplification when batches are uniformly sampled.
• Poisson Sampling: Preferred over fixed-size shuffling because it provides tighter privacy accounting under Rényi DP.