Privacy Budget (Epsilon)

Epsilon (ε) provides a mathematically provable upper bound on information leakage. It measures the maximum divergence between the output distributions of a mechanism run on two adjacent datasets differing by a single record.

• ε = 0: Perfect privacy; outputs are completely independent of any individual's data.
• ε = 0.1–1.0: Strong privacy regime; typical for high-sensitivity census or medical data.
• ε = 1.0–10: Moderate privacy; common in commercial machine learning training.
• ε > 10: Weak privacy; the guarantee degrades rapidly, approaching non-private analysis.

The total privacy loss accumulates additively when multiple differentially private queries are performed on the same dataset. If you run mechanism M₁ with budget ε₁ and M₂ with budget ε₂, the total guarantee is ε_total = ε₁ + ε₂.

This property forces architects to track a global ledger of privacy expenditure. If an analyst is granted a total budget of ε = 1.0, they must carefully allocate fractions of epsilon across all queries to avoid exhausting the guarantee prematurely.

When differentially private queries operate on disjoint, independent subsets of data, the privacy cost does not accumulate. The total budget consumed is the maximum epsilon among the parallel operations, not their sum.

• Querying user A's records and user B's records separately: cost = max(ε_A, ε_B).
• This property is critical for scalable systems, allowing concurrent analytics on partitioned data without multiplying the privacy loss.

Any computation applied to the output of a differentially private mechanism does not degrade the privacy guarantee. An adversary cannot increase information leakage by transforming, filtering, or analyzing the released result.

This property ensures that once noise is calibrated to satisfy ε-differential privacy, downstream machine learning models, visualizations, or statistical tests inherit the same guarantee without additional budget consumption. The privacy protection is future-proof against arbitrary post-processing.

The standard definition protects against adversaries distinguishing datasets that differ by one record. For groups of size k, the guarantee degrades linearly: the effective budget becomes k · ε.

• Protecting a family of 4 in a genomic study: effective ε = 4 × individual ε.
• This property quantifies the increased risk when correlated records exist in the dataset.
• Mitigation requires setting a much lower base epsilon to maintain meaningful group-level protection.

While basic composition sums epsilons linearly, advanced composition theorems provide tighter bounds for repeated queries. For k queries each with (ε, δ)-differential privacy, the total privacy loss grows proportionally to √(k) · ε rather than k · ε, under Gaussian mechanisms.

This sub-linear scaling is essential for iterative algorithms like DP-SGD, where thousands of training steps must fit within a reasonable total budget. The trade-off introduces a small failure probability δ, where pure ε-differential privacy relaxes to approximate (ε, δ)-differential privacy.

A probabilistic characterization of how much information is leaked by a single run of a DP mechanism. Rather than relying solely on the worst-case bound of epsilon, privacy accountants track the full distribution of the privacy loss random variable. This enables tight composition—accurately summing the budget consumed across many queries without overestimating total leakage.

• Privacy Loss Random Variable: The log-ratio of output probabilities under adjacent datasets.
• Moments Accountant: A technique for tracking higher moments of the loss distribution to compute tighter overall epsilon bounds, famously used in DP-SGD.

The mathematical rules governing how epsilon values accumulate when multiple differentially private computations are performed on the same dataset. Basic composition states that the total epsilon is simply the sum of individual epsilons. Advanced composition provides a sublinear bound, allowing more queries under a fixed total budget.

• Sequential Composition: ε_total = ε_1 + ε_2 + ... + ε_k
• Parallel Composition: When queries operate on disjoint data partitions, the total cost equals the maximum single-query epsilon, not the sum.
• Privacy accountants use these theorems to enforce a hard cap on total leakage over a system's lifetime.

The dominant training algorithm for deep learning with differential privacy. DP-SGD consumes privacy budget per training step by clipping per-sample gradients to bound sensitivity and adding Gaussian noise to the aggregated gradient. The total epsilon spent over training is computed via a moments accountant tracking the composition across all iterations.

• Gradient Clipping: Limits the influence of any single training example.
• Noise Multiplier: Controls the variance of added noise; higher values yield lower epsilon per step.
• Batch Size Trade-off: Larger batches improve the signal-to-noise ratio but consume budget faster per epoch.

The state where a system's total allocated epsilon has been fully consumed, requiring a halt to all further queries on the sensitive dataset. Budget management strategies include setting a per-user lifetime cap, implementing a privacy budget dashboard for data analysts, and using zero-concentrated differential privacy (zCDP) for tighter composition accounting.

• Budget Exhaustion: No further queries allowed; prevents death-by-a-thousand-cuts attacks.
• Renewal Policies: Some systems refresh budgets periodically or after data refreshes.
• Rényi DP: An alternative privacy definition using Rényi divergence that enables tighter composition than standard (ε, δ)-DP.