Privacy Budget (Epsilon)

A randomized mechanism M satisfies ε-differential privacy if for all adjacent datasets D and D' (differing by one record) and all possible outputs S:

Pr[M(D) ∈ S] ≤ e^ε × Pr[M(D') ∈ S]

This inequality ensures an adversary cannot confidently determine whether a specific individual's data was included. The multiplicative bound e^ε quantifies the maximum privacy loss. When ε = 0, the outputs are identically distributed, providing perfect privacy.

Epsilon operates on a continuous scale where lower values equal stronger privacy:

• ε < 0.1: Extremely strong guarantees. High noise, suitable for highly sensitive public data releases.
• 0.1 < ε < 1: Strong privacy. A common target for federated learning and private analytics.
• 1 < ε < 10: Moderate privacy. Balances utility for model training with meaningful protection.
• ε > 10: Weak guarantee. Often provides negligible protection against determined adversaries.

Apple's initial deployment used ε = 4, later increasing to ε = 8 per day, demonstrating the real-world trade-off between privacy and data utility.

Privacy loss accumulates with repeated queries. This is governed by composition theorems:

• Basic Composition: Querying a dataset k times with privacy parameter ε results in a total privacy loss of k × ε.
• Advanced Composition: Provides a tighter bound, approximating total loss as O(√k × ε) with a small failure probability δ.

This is why ε is called a privacy budget—each analysis deducts from a finite allowance. Once the budget is exhausted, no further queries can be answered without risking re-identification.

Pure ε-differential privacy is often too strict for machine learning. Approximate differential privacy introduces a second parameter, δ, representing a small failure probability:

• δ bounds the probability that the pure ε guarantee is violated.
• Typically set to be cryptographically small (e.g., δ < 1/number of records).
• DP-SGD operates under this (ε, δ) framework, where δ accounts for the rare chance that the Gaussian noise mechanism fails catastrophically.

A common target for DP-SGD training is (ε = 8, δ = 10^-5).

Epsilon alone is meaningless without sensitivity. The amount of noise required to achieve a target ε is directly proportional to the L2 sensitivity (Δ) of the query function:

σ = Δ / ε (for the Laplace mechanism)

• Global Sensitivity: The maximum difference in the query's output across all possible adjacent datasets.
• Per-Sample Clipping in DP-SGD bounds sensitivity by scaling individual gradients to a fixed L2 norm C.

A query with high sensitivity requires more noise, consuming the privacy budget faster for the same ε.

The standard ε guarantee protects against an adversary trying to infer a single record's presence. Group privacy extends this to groups of size k:

• A mechanism that is ε-differentially private for a single record is k × ε differentially private for a group of k correlated records.
• This is critical for genomic data, where an individual's record may reveal information about family members.

Protecting a family of four under ε = 0.1 effectively requires a per-individual budget of ε = 0.025.

The mathematical framework that defines the privacy budget. DP provides provable guarantees that the output of a computation is nearly identical whether or not any single individual's data is included. The epsilon (ε) parameter quantifies the maximum divergence between outputs on neighboring datasets—a lower epsilon means stronger privacy. The framework also includes a delta (δ) parameter that allows for a small probability of catastrophic privacy loss, with pure ε-differential privacy corresponding to δ=0.

Differentially Private Stochastic Gradient Descent is the primary training algorithm that operationalizes the privacy budget in deep learning. It enforces epsilon constraints through two key operations:

• Per-sample gradient clipping: Bounds the L2 norm of each individual gradient to limit sensitivity
• Gaussian noise injection: Adds calibrated noise proportional to the clipping threshold and inversely proportional to the target epsilon Each training iteration consumes a portion of the overall privacy budget, tracked via moment accountant or Rényi DP composition theorems.

The privacy budget is a finite, consumable resource. Each query or training epoch that accesses sensitive data consumes a fraction of epsilon. Once the cumulative privacy loss reaches the pre-defined threshold, the data must be locked down to prevent privacy guarantees from degrading below acceptable levels. Key depletion dynamics include:

• Sequential composition: Querying the same data k times consumes kε budget
• Parallel composition: Queries on disjoint data subsets consume only the maximum single-query epsilon
• Advanced composition: Tighter bounds that account for the probabilistic nature of privacy loss accumulation

An attack that directly targets the protections the privacy budget is designed to provide. Given access to a trained model's parameters and confidence scores, an adversary optimizes an input to maximize the probability of a target class, reconstructing a representative sample of the training data. A sufficiently strict epsilon budget degrades the fidelity of these reconstructions by forcing the model to learn only coarse, population-level patterns rather than memorizing individual training examples.

An attack that determines whether a specific record was present in the training dataset. The adversary exploits differences in model confidence between seen and unseen examples. A properly calibrated privacy budget directly bounds the true positive rate and false positive rate of such attacks. Formally, DP guarantees that an adversary's ability to infer membership is limited by a function of ε—with ε approaching zero, the adversary's advantage over random guessing becomes negligible.

The Private Aggregation of Teacher Ensembles framework provides an alternative mechanism for consuming privacy budget. An ensemble of teacher models is trained on disjoint partitions of sensitive data. A student model is then trained on the noisy aggregated votes of the teachers, with privacy budget consumed only through the aggregation mechanism. Key properties:

• Privacy cost scales with the number of answered queries, not the size of the training data
• The GNMax aggregator adds Gaussian noise to teacher vote counts, calibrated to the target epsilon
• Particularly effective when the number of teachers is large and data partitions are non-overlapping