Epsilon Budget

Epsilon (ε) is a numerical parameter that bounds the privacy loss incurred when releasing a statistical query result. A smaller epsilon (e.g., 0.1) enforces a stronger privacy guarantee by ensuring the output distribution is nearly identical whether or not any single individual's record is included in the dataset. The parameter directly controls the likelihood ratio of observing a specific output on two neighboring datasets.

• ε = 0: Perfect privacy, but zero utility (outputs must be identical).
• ε = 0.1–1: Strong privacy, typical for high-sensitivity use cases.
• ε = 10+: Weak privacy, approaching non-private statistics.

When multiple differentially private queries are executed on the same dataset, the total privacy loss accumulates. Composition theorems provide the mathematical framework for tracking this cumulative spend against the epsilon budget. Basic composition states that the total epsilon is the sum of individual epsilons. Advanced composition offers a tighter bound, showing that the total loss scales with the square root of the number of queries under certain conditions.

• Sequential Composition: ε_total = ε_1 + ε_2 + ... + ε_k
• Parallel Composition: Queries on disjoint data partitions do not sum their epsilon costs.
• Advanced Composition: Introduces a delta (δ) term for a more nuanced, sub-linear bound.

The epsilon budget embodies the fundamental privacy-utility trade-off. To satisfy a strict epsilon constraint, a randomized mechanism (such as the Laplace or Gaussian mechanism) must inject calibrated noise proportional to the sensitivity of the query divided by epsilon. A smaller epsilon forces the injection of more noise, which degrades the accuracy of the output. Managing an epsilon budget is therefore an exercise in allocating a finite privacy resource to maximize data utility.

• Laplace Mechanism: Adds noise drawn from a Laplace distribution scaled by Δf/ε.
• Gaussian Mechanism: Adds noise scaled by Δf * sqrt(2*ln(1.25/δ))/ε, requiring a relaxation term δ.

Once the cumulative privacy loss reaches the predefined epsilon budget, no further queries can be answered on the dataset without violating the privacy guarantee. This requires a privacy accountant—a subsystem that monitors the epsilon spend of each query in real time. The accountant enforces the budget by denying queries that would cause an overflow, effectively locking the dataset to preserve the total privacy guarantee.

• Privacy Accountant: A runtime component that tracks cumulative (ε, δ) spend.
• Moments Accountant: A state-of-the-art method for tracking privacy loss in differentially private stochastic gradient descent (DP-SGD).
• Budget Overflow: The state where a new query is blocked to maintain the total privacy promise.

A randomized algorithm M satisfies ε-differential privacy if for all possible outputs S and for any two neighboring datasets D and D' differing by one record, the probability of observing S is bounded by a multiplicative factor of e^ε. Formally: Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S]. This guarantee holds against an adversary with arbitrary auxiliary information, making it a robust, future-proof privacy definition.

• Neighboring Datasets: Two datasets that differ by the addition or removal of a single record.
• Multiplicative Bound: The output probabilities on D and D' are within a factor of e^ε of each other.

Pure ε-differential privacy can be too strict for complex machine learning tasks. (ε, δ)-differential privacy introduces a relaxation parameter δ, which allows the privacy guarantee to fail with a very small probability (typically cryptographically small, e.g., 10^-5). This relaxation enables more efficient algorithms, such as the Gaussian mechanism, and is the standard framework for training deep learning models with DP-SGD.

• δ Parameter: The probability that the pure ε-guarantee is violated.
• Cryptographic Safety: δ must be much smaller than 1/N, where N is the dataset size.
• DP-SGD: The core algorithm for training neural networks under an (ε, δ) budget.

A mathematical framework that provides provable privacy guarantees by injecting calibrated noise into computations. The epsilon budget is the central parameter controlling the privacy-utility trade-off—lower epsilon values enforce stronger privacy but reduce data utility. Formalized by Dwork et al., it ensures the output of an analysis does not reveal the presence or absence of any single individual in the dataset.

• ε (epsilon): The privacy loss parameter, typically ranging from 0.1 to 10
• δ (delta): The probability of catastrophic privacy failure in (ε, δ)-differential privacy
• Sensitivity: The maximum impact a single record can have on query output

The systematic tracking of cumulative epsilon expenditure across multiple queries against a sensitive dataset. Composition theorems govern how privacy loss accumulates—basic composition sums epsilon values linearly, while advanced composition provides tighter bounds using the square root of the number of queries. Proper accounting prevents privacy budget exhaustion before legitimate analyses complete.

• Sequential composition: ε_total = ε₁ + ε₂ + ... + εₙ
• Parallel composition: Queries on disjoint data partitions do not sum
• Moments accountant: Tracks higher-order moments for tighter privacy bounds in deep learning

A fundamental differential privacy mechanism that adds calibrated Gaussian noise to query outputs. The noise scale is determined by the L2 sensitivity of the query function and the desired epsilon budget. For a given epsilon, higher sensitivity queries require proportionally more noise, consuming more of the privacy budget per query.

• Noise calibrated as: σ = (Δf · √(2·ln(1.25/δ))) / ε
• Δf: The L2 sensitivity of the query function
• Widely used in DP-SGD for differentially private deep learning training

The standard algorithm for training differentially private neural networks. DP-SGD clips per-example gradients to bound sensitivity, then adds Gaussian noise proportional to the clipping norm and inversely proportional to the epsilon budget. Each training step consumes a portion of the total privacy budget, tracked by the moments accountant.

• Gradient clipping: Bounds the influence of any single training example
• Noise multiplier: Derived from target (ε, δ) and number of training steps
• Privacy amplification by subsampling: Random batch selection reduces effective epsilon

A relaxation of standard differential privacy based on Rényi divergence that provides tighter composition bounds. RDP expresses privacy loss in terms of (α, ε)-RDP, where α is the order of the divergence. Converting RDP bounds to standard (ε, δ)-DP often yields significantly smaller epsilon values than direct composition, enabling more efficient use of the privacy budget.

• α → ∞: RDP converges to pure ε-differential privacy
• Enables tighter analysis of subsampled Gaussian mechanisms
• Foundation for the moments accountant used in TensorFlow Privacy and Opacus

A privacy budget optimization technique that answers only queries exceeding a threshold, paying epsilon only for queries that pass the threshold rather than all queries. This enables analysts to run many candidate queries while consuming budget only on statistically significant results. Critical for exploratory data analysis under strict epsilon constraints.

• AboveThreshold algorithm: Pays ε for each query above threshold
• NumericSparse algorithm: Returns noisy values only for above-threshold queries
• Reduces budget consumption by orders of magnitude in selective querying scenarios