Privacy Budget

Epsilon (ε) is the core parameter defining the strength of the privacy guarantee in differential privacy. It quantifies the maximum allowable privacy loss for any individual in the dataset. A smaller ε provides a stronger privacy guarantee but requires adding more noise, which degrades data utility. Common values range from 0.01 (very strong privacy) to 10 (weaker privacy, higher utility), depending on the application's sensitivity.

• Interpretation: Loosely, ε represents the log of the probability ratio of seeing any output with or without an individual's data. An ε of 1 means this ratio is bounded by ~2.718.
• Role in Budgeting: Each query consumes a portion of the total ε. Once the cumulative ε is exhausted, no further queries can be answered with a formal guarantee.

Delta (δ) is a secondary parameter in (ε, δ)-differential privacy that represents a small probability the strict ε guarantee might fail. It accounts for extremely low-probability events where the privacy loss could exceed ε. For pure differential privacy, δ is set to 0.

• Typical Values: δ should be cryptographically small, significantly less than 1/n (where n is the dataset size). Values like 1e-5 or 1e-10 are common.
• Purpose: Allows for the use of more efficient mechanisms like the Gaussian mechanism, which adds noise from a normal distribution instead of a Laplace distribution, often providing better utility for the same privacy cost.

Privacy accounting is the method for tracking cumulative privacy loss (ε, δ) across multiple queries or analyses on the same dataset. Composition theorems provide the mathematical rules for how budgets add up.

• Basic Composition: The naive approach where ε budgets sum linearly (ε_total = ε1 + ε2 + ...). This is simple but pessimistic.
• Advanced Composition: Provides tighter bounds, allowing for sub-linear growth of ε under certain conditions, enabling more queries for the same total budget.
• Zero-Concentrated DP (zCDP) & Rényi DP: More sophisticated accounting frameworks that often give tighter composition bounds, allowing for more accurate tracking of privacy loss over complex, adaptive sequences of queries common in machine learning training.

The sensitivity of a query function determines how much noise must be added to its output to achieve differential privacy. It measures the maximum possible change in the query's output when a single individual's data is added or removed from the dataset.

• Global Sensitivity (Δf): The worst-case change over all possible neighboring datasets. Used to calibrate the Laplace and Gaussian mechanisms. For a counting query, Δf = 1. For an average, sensitivity depends on the data bounds.
• Local Sensitivity & Smoothing: Sometimes global sensitivity is too large. Techniques like propose-test-release or smooth sensitivity can allow for less noise by analyzing the specific dataset, though they require more complex mechanisms.
• Role: The noise scale in the Laplace mechanism is Δf/ε. Higher sensitivity or a lower ε (stronger privacy) requires more noise.

These are the fundamental randomized algorithms that implement differential privacy by adding calibrated noise to query outputs.

• Laplace Mechanism: Used for pure (ε, 0)-DP. Adds noise drawn from a Laplace distribution with scale Δf/ε. Ideal for numeric queries like counts, sums, and averages.
• Gaussian Mechanism: Used for (ε, δ)-DP. Adds noise drawn from a Gaussian (normal) distribution. The noise scale σ is proportional to Δf * √(2log(1.25/δ))/ε. Often provides better utility for high-dimensional queries like machine learning gradients.
• Exponential Mechanism: Used for non-numeric queries (e.g., selecting the best item from a set). It randomly chooses an output where the probability is exponentially weighted by a utility score.

How an organization strategically spends its finite privacy budget across analyses is a critical engineering decision.

• Uniform Allocation: Dividing the total ε equally among a predetermined number of queries. Simple but inefficient.
• Adaptive Allocation: Allowing later queries to consume remaining budget based on the results of earlier ones. More flexible but requires careful accounting.
• Hierarchical Allocation: Reserving portions of the budget for different departments or project phases, akin to financial budgeting.
• Optimization for Workloads: Using algorithms to minimize total budget consumption for a set of planned queries or for iterative processes like differentially private stochastic gradient descent (DP-SGD) in machine learning, where noise is added to gradients each epoch.

The mathematical framework that defines the privacy budget (ε). It provides a rigorous, quantifiable guarantee that the output of an algorithm (e.g., a statistical query or a machine learning model) does not reveal whether any specific individual's data was in the input dataset. The framework's strength lies in its composition theorems, which formally govern how privacy budgets are consumed across multiple queries.

A variant where data is randomized at the source (e.g., on a user's device) before being sent to a central aggregator. This eliminates the need for a trusted data curator. Each user applies their own local privacy budget to their data, providing strong protection even if the aggregator is malicious. It's foundational for privacy in federated learning and analytics on user devices.

The canonical algorithm for achieving ε-differential privacy for numeric queries. It adds carefully calibrated noise, drawn from a Laplace distribution, to the true query result. The scale of the noise is set by the query's sensitivity (maximum change a single record can cause) divided by the privacy budget (ε). A smaller ε (tighter budget) requires more noise, directly trading accuracy for privacy.

The mathematical rules that dictate how a total privacy budget is depleted when multiple differentially private analyses are performed on the same dataset.

• Sequential Composition: The ε values of individual queries sum up. If you run a query with ε=0.5 and another with ε=0.3, the total privacy loss is ε=0.8.
• Advanced Composition: Provides tighter bounds for many queries, allowing for a sub-linear growth in total ε under certain conditions. These theorems are essential for budgeting and auditing privacy consumption in complex systems.

The overarching field that utilizes techniques like differential privacy (and its budget) to train and infer with models on sensitive data. PPML integrates the privacy budget into the training loop itself, such as in Differentially Private Stochastic Gradient Descent, where noise is added to gradients, and the total training epochs consume a predefined global budget. It ensures the final model does not memorize individual training examples.

A critical operational concept: a privacy budget is finite and non-renewable for a fixed dataset and analysis goal. Once exhausted, no further queries with formal ε-differential privacy guarantees can be answered. To continue analysis, an organization must:

• Acquire new, independent data (e.g., from new users) to which a fresh budget applies.
• Use weaker privacy guarantees (larger ε) for future queries, accepting higher risk.
• This imposes a fundamental constraint on how frequently and granularly private data can be interrogated.