Differential Privacy

The parameter epsilon (ε) is the privacy loss parameter, quantifying the maximum divergence between outputs on neighboring datasets. A smaller ε provides stronger privacy.

• ε = 0: Perfect privacy, outputs are identical regardless of any single record's presence.
• ε ≈ 0.1–1: Strong privacy, typical for high-sensitivity applications like census data.
• ε > 10: Weak privacy, minimal meaningful protection.

The budget is consumed cumulatively across queries. Once exhausted, no further analysis is permitted without risking re-identification.

Global sensitivity measures the maximum impact a single record can have on a query's output. This determines the scale of noise required.

• Counting queries: Sensitivity of 1 (adding a person changes count by at most 1).
• Sum queries: Sensitivity equals the maximum absolute value in the data domain.
• Median queries: Can have unbounded sensitivity, requiring careful algorithm design.

Noise is typically drawn from a Laplace distribution (for ε-differential privacy) or a Gaussian distribution (for (ε, δ)-relaxed differential privacy), scaled proportionally to sensitivity divided by ε.

Delta (δ) is a relaxation parameter in (ε, δ)-differential privacy that allows a small probability of catastrophic privacy failure.

• δ = 0: Pure ε-differential privacy, the gold standard.
• δ ≈ 10⁻⁶ to 10⁻⁹: Approximate differential privacy, typical for Gaussian noise mechanisms.
• δ must be cryptographically small: Smaller than the inverse of the dataset size to prevent membership inference.

This relaxation enables the use of advanced composition theorems and the Gaussian mechanism, which is essential for differentially private stochastic gradient descent (DP-SGD) in federated learning.

The composition theorem quantifies how privacy degrades when multiple differentially private analyses are performed on the same dataset.

• Basic Composition: Running k mechanisms each with εᵢ privacy results in a total privacy loss of Σ εᵢ.
• Advanced Composition: For (ε, δ)-differential privacy, the total privacy loss grows sub-linearly, proportional to √(k) * ε rather than k * ε.

This is critical for iterative algorithms like DP-SGD, where noise is added at every training step. Without advanced composition, the privacy budget would be exhausted after a handful of iterations.

A defining property of differential privacy is resilience to post-processing. Any arbitrary computation applied to the output of a differentially private mechanism cannot degrade the privacy guarantee.

• An adversary with unlimited auxiliary information about all but one record still cannot infer that record's presence.
• Arbitrary transformations: Averaging, thresholding, or feeding the output into another model does not weaken the ε guarantee.
• This ensures that privacy is preserved even if the output is published publicly or subjected to adversarial analysis.

This property makes differential privacy composable with other systems without requiring trust in downstream consumers.

Differential privacy naturally extends to protect groups of correlated records. If a mechanism provides ε-differential privacy for a single record, it provides k·ε-differential privacy for a group of size k.

• Family privacy: Protects households in census data where multiple members share attributes.
• Time-series protection: Safeguards sequences of location pings from a single device.
• Trade-off: Protecting larger groups requires proportionally more noise, reducing utility.

This property is essential for federated wireless learning, where a single device may contribute multiple correlated updates over time, and the privacy guarantee must account for the entire contribution history.

An encryption scheme that permits computation directly on ciphertexts, generating an encrypted result that, when decrypted, matches the output of operations performed on the original plaintext data. In federated learning, this allows the server to aggregate model updates without ever decrypting them. Unlike differential privacy, which adds noise to obscure individual contributions, homomorphic encryption provides exact computation on encrypted data, making them complementary tools for different threat models.

A privacy attack where an adversary exploits access to a trained model to reconstruct sensitive features or representative samples of the private training data. For example, an attacker might recover recognizable facial images from a facial recognition model. Differential privacy provides a provable defense against such attacks by bounding the influence of any single training record on the model's outputs, making reconstruction statistically impossible beyond a guaranteed threshold.

A communication efficiency technique that reduces the size of model updates transmitted from clients to the server by applying lossy compression methods like sparsification or quantization to gradients. While primarily designed to reduce bandwidth, gradient compression can interact with differential privacy mechanisms. The sparsification process itself introduces randomness that can amplify or interfere with calibrated noise injection, requiring careful joint design of compression and privacy budgets.

The property of a distributed learning system that enables it to converge to a correct global model despite the presence of faulty or malicious clients exhibiting arbitrary behavior. While differential privacy protects against privacy leakage from honest-but-curious participants, Byzantine resilience defends against active adversaries uploading corrupted updates. Production federated systems often require both properties simultaneously to ensure both privacy and robustness.

A communication-efficient approach where clients exchange model outputs (logits) on a public dataset instead of model weights, using knowledge distillation to aggregate knowledge. This paradigm offers natural compatibility with differential privacy because noise can be added to the shared logits rather than to high-dimensional gradient vectors. The lower dimensionality of logits compared to model weights often results in better privacy-utility trade-offs under the same privacy budget.