Privacy Budget

Epsilon (ε) is the core parameter defining the privacy guarantee. It quantifies the maximum allowable privacy loss for any individual in the dataset. A smaller ε provides a stronger privacy guarantee.

• Interpretation: Formally, it bounds the log of the probability ratio of any output occurring with or without any single individual's data.
• Rule of Thumb: ε values below 1.0 are considered to offer strong privacy, while values above 10.0 offer very weak guarantees for complex queries.
• Trade-off: Lower ε increases noise, reducing data accuracy (utility). The choice of ε is a policy decision balancing risk and utility.

Delta (δ) is a small probability that the strict ε-differential privacy guarantee might fail. It accounts for a tiny chance of catastrophic privacy loss.

• Role: In (ε, δ)-Differential Privacy, δ is typically set to a cryptographically small value (e.g., 10⁻⁵), much smaller than 1/n, where n is the dataset size.
• Pure vs. Approximate DP: When δ = 0, the guarantee is Pure Differential Privacy. When δ > 0, it is Approximate Differential Privacy, which often allows for less noise addition for the same utility.
• Critical Setting: δ must be set extremely carefully, as a large δ effectively voids the privacy guarantee.

Sensitivity measures how much a single individual's data can change the result of a query. It determines how much noise must be added to achieve the (ε, δ) guarantee.

• Global Sensitivity (Δf): The maximum absolute change in a query's output over all possible neighboring datasets. For a counting query, Δf = 1.
• Local Sensitivity: A data-dependent, often smaller measure, but using it directly can leak privacy. Advanced mechanisms like the Propose-Test-Release framework can sometimes leverage it safely.
• Noise Scaling: The amount of noise (e.g., from a Laplace or Gaussian distribution) added to a query's true answer is directly proportional to Δf / ε.

Composition theorems govern how the privacy budget is consumed over multiple queries on the same dataset. They are the accounting rules of differential privacy.

• Sequential Composition: The most straightforward rule. If you run k mechanisms with guarantees (ε₁, δ₁)...(εₖ, δₖ), the total privacy cost is (Σεᵢ, Σδᵢ).
• Advanced Composition: Allows for a tighter, sub-linear growth in ε for many queries (kε² for fixed δ). This is crucial for complex analyses.
• Budget Tracking: A system must track the cumulative (ε, δ) spent against a total allocated budget. Once exhausted, no further queries are permitted without risking privacy violation.

For advanced mechanisms, the privacy loss is not a fixed number ε but a random variable. This leads to more precise accounting methods.

• Privacy Loss Random Variable: Tracks the actual log-ratio of probabilities for a specific output. Its tail bounds define (ε, δ).
• Moments Accountant: Used in training deep learning models with DP-SGD. It bounds the moments of this random variable for tighter composition across many training iterations.
• zCDP (Zero-Concentrated DP): A variant of differential privacy that works with the privacy loss random variable directly, often providing cleaner composition and tighter analysis for Gaussian noise mechanisms.

The mechanism is the randomized algorithm that implements differential privacy by injecting calibrated noise into query results or model training.

• Laplace Mechanism: Adds noise from the Laplace distribution scaled to Δf/ε. Used for pure (ε, 0)-DP on numeric queries.
• Gaussian Mechanism: Adds noise from the Gaussian (Normal) distribution. It naturally provides (ε, δ)-DP and is often more utility-friendly for high-dimensional queries.
• Exponential Mechanism: Used for non-numeric queries (e.g., selecting the best item from a set). It randomly outputs an option with probability proportional to exp(ε * utility score / 2Δutility).
• DP-SGD: The fundamental algorithm for private deep learning, which clips per-example gradients (bounding sensitivity) and adds Gaussian noise during stochastic gradient descent.

Differential privacy is the rigorous mathematical framework that defines and enables the privacy budget. It provides a formal guarantee that the output of a computation (e.g., a query or model training run) does not reveal whether any single individual's data was included in the input dataset. The framework achieves this by injecting calibrated random noise into the process. A system is (ε, δ)-differentially private if, for all neighboring datasets (differing by one record), the probability of any output changes by at most a factor of e^ε, plus a small failure probability δ.

Epsilon (ε) is the primary parameter quantifying the privacy loss or privacy budget. It is a non-negative real number where:

• ε = 0 represents perfect privacy (the output reveals nothing about any individual).
• Smaller ε values (e.g., 0.1, 1.0) provide stronger, more conservative privacy guarantees but require more noise, reducing output utility.
• Larger ε values (e.g., 10.0) allow for more utility/accuracy but offer weaker privacy protection. Choosing ε involves a direct privacy-utility trade-off. Common values in research and industry deployments range from 0.01 to 10, depending on the sensitivity of the application.

Delta (δ) is a secondary parameter in the (ε, δ)-differential privacy definition. It represents a small probability that the strict ε privacy guarantee could fail. For example, δ = 10^-5 means there is a 1 in 100,000 chance that the privacy loss exceeds ε. In practice:

• δ should be cryptographically small, significantly less than 1/(dataset size).
• A non-zero δ is often necessary for complex mechanisms like the Gaussian mechanism used in deep learning.
• The Pure Differential Privacy variant sets δ = 0, using only the Laplace mechanism, but this can be overly restrictive for some analyses.

Privacy loss accumulation refers to the fact that the privacy budget ε is consumed over multiple queries or training steps. If you perform k computations, each with a privacy cost of ε_i, the total privacy cost is typically the sum (ε_total = Σ ε_i) under sequential composition. Advanced composition theorems allow for slightly better bounds. This is why managing the privacy budget is critical:

• Budget tracking is required to prevent exceeding a pre-defined total ε.
• Techniques like the Moments Accountant or Renyi Differential Privacy (RDP) provide tighter bounds on cumulative loss for iterative algorithms like Stochastic Gradient Descent (SGD).

Sensitivity is a measure of how much a single individual's data can change the output of a function. It directly determines how much noise must be added to achieve differential privacy. There are two main types:

• Global Sensitivity (Δf): The maximum possible change in the function's output over any two neighboring datasets. Used for the Laplace Mechanism.
• Local Sensitivity: The change for a specific dataset, which can be lower but requires more complex, data-dependent mechanisms. For example, a counting query ("how many people have disease X?") has a sensitivity of 1, as one person can change the count by at most 1. Higher sensitivity requires more noise to "hide" an individual's contribution.

DP-SGD is the canonical algorithm for training machine learning models with differential privacy guarantees. It modifies standard SGD to consume the privacy budget carefully:

1. Per-example Gradient Clipping: Each training example's gradient is clipped to a maximum norm (bounding sensitivity).
2. Noise Addition: Gaussian noise is added to the average of the clipped gradients in each mini-batch.
3. Privacy Accounting: A tool like the Moments Accountant tracks the cumulative privacy loss (ε) across all training epochs. DP-SGD enables the creation of models with provable privacy guarantees, but the added noise often leads to a utility loss, requiring more data or careful hyperparameter tuning to achieve comparable accuracy to non-private models.