Privacy Budget

Epsilon (ε) is the core parameter defining the strength of the privacy guarantee in differential privacy. It quantifies the maximum allowable multiplicative difference in the probability of any output, with or without any single individual's data. In a privacy budget context, ε is the principal resource that is consumed.

• Interpretation: A smaller ε indicates a stronger privacy guarantee (e.g., ε=0.1 is stronger than ε=1.0).
• Budget Role: Each query or training step consumes a portion of the total ε budget. Once the budget is exhausted, no further private analyses can be performed on that dataset without violating the guarantee.

Delta (δ) is a secondary parameter in (ε, δ)-differential privacy, representing a small probability that the pure ε guarantee might fail. It is typically set to a cryptographically small value, often less than the inverse of the dataset size (e.g., δ < 1e-5).

• Interpretation: A δ of 1e-5 means there is a 1 in 100,000 chance that the privacy loss could exceed ε.
• Budget Role: While ε is actively consumed, δ is usually fixed for the entire analysis. The chosen δ value influences the scale of noise added (e.g., in the Gaussian mechanism) and is part of the overall budget specification.

Privacy accounting is the algorithmic process of meticulously tracking the cumulative privacy loss (ε, δ) across all operations performed on a dataset. It ensures the total expenditure does not exceed the pre-allocated privacy budget.

• Core Function: It applies composition theorems to calculate how privacy parameters degrade when multiple mechanisms are used sequentially.
• Advanced Methods: For iterative processes like DP-SGD, advanced accountants like the moment accountant or Rényi Differential Privacy (RDP) provide tighter, more efficient tracking than basic sequential composition, allowing more utility from the same budget.

Composition theorems are the mathematical rules that govern how privacy guarantees combine when multiple analyses are performed. They define the 'exchange rate' for spending the privacy budget.

• Basic Sequential Composition: The simplest rule: if you run k mechanisms, each with parameters (ε_i, δ_i), the total cost is (Σε_i, Σδ_i). This is often overly conservative.
• Advanced Composition: Provides tighter bounds, especially for many compositions, allowing for a sub-linear growth in ε (e.g., ε_total grows with √k).
• Parallel Composition: If mechanisms are applied to disjoint subsets of the data, the overall ε cost is only the maximum of the individual ε's, not the sum, allowing efficient budget allocation.

Sensitivity is the maximum possible change in the output of a function (like a query or a gradient) when a single data point is added or removed. It is not part of the budget itself but is the critical factor determining how much budget a single operation consumes.

• L1 Sensitivity (Δ1): Used for the Laplace Mechanism. The maximum absolute change in the output vector.
• L2 Sensitivity (Δ2): Used for the Gaussian Mechanism. The maximum Euclidean norm change in the output vector.
• Budget Impact: A higher sensitivity function requires more noise to achieve a given (ε, δ), thereby consuming budget more quickly. Techniques like gradient clipping are used to artificially bound sensitivity in ML.

The allocation strategy determines how the finite privacy budget is partitioned across different stages of an analysis, such as multiple training rounds in federated learning or various queries in a database system.

• Uniform Allocation: Dividing the total ε evenly across all T operations (e.g., ε_per_round = ε_total / T). Simple but often suboptimal.
• Adaptive Allocation: Dynamically allocating more budget to more important queries or later training rounds where gradients are smaller. This requires careful online accounting.
• Optimization Goal: The strategy aims to maximize the overall utility (model accuracy, query answer quality) of the final output while strictly respecting the total budget constraint.

The primary component of a privacy budget is ε (epsilon), which quantifies the maximum allowable privacy loss. In federated learning, this is typically applied at the client level, protecting the participation of any single device. A smaller ε provides a stronger privacy guarantee but consumes the budget faster per training round, forcing a trade-off between model utility and the total number of permissible training iterations.

A core challenge is tracking cumulative privacy loss across multiple rounds. Composition theorems (Basic, Advanced, or via Rényi DP) mathematically define how ε and δ compose. Privacy accounting methods, like the moment accountant used in DP-SGD, provide tight, iterative tracking of the budget's consumption, ensuring the total never exceeds the pre-defined limit. Without rigorous accounting, the budget can be exhausted prematurely or privacy guarantees violated.

The privacy budget creates a fundamental trade-off:

• High Privacy (Low ε/round): Stronger protection per round, but the budget is consumed quickly, limiting the total number of training rounds and potentially harming final model accuracy.
• Lower Privacy (Higher ε/round): Allows for more training iterations and often better utility, but provides weaker per-round and final privacy guarantees. System designers must allocate the total budget strategically across the training lifecycle.

Certain techniques can effectively 'stretch' a privacy budget. Privacy amplification by subsampling (e.g., randomly selecting a fraction of clients each round) and amplification by shuffling client reports can yield a stronger effective privacy guarantee (smaller effective ε) for the same amount of added noise. This allows for more training rounds or better utility under the same total budget constraint.

In (ε, δ)-differential privacy, δ represents a small probability of the privacy guarantee failing. It is a critical part of the budget for mechanisms using Gaussian noise (like DP-SGD). δ must be set to a cryptographically small value (e.g., < 1e-10 or less than 1/n, where n is the number of clients). Managing the δ budget is essential, as careless composition can cause it to grow unacceptably large.

How the total budget is spent is a system design decision. Common strategies include:

• Uniform Allocation: Equal ε per training round. Simple but may not be optimal.
• Adaptive/Decaying Allocation: Spending more budget early for rapid learning, then less later for fine-tuning, or vice-versa.
• Task-Specific Allocation: Dividing a global budget across multiple model training tasks. The strategy directly impacts final model performance and compliance with long-term privacy policies.

The formal mathematical framework underpinning the privacy budget. It provides a quantifiable guarantee that the output of an algorithm (like a model update) does not reveal whether any single individual's data was included in the input.

• Core Guarantee: An algorithm is (ε, δ)-DP if the probability of any output changes by at most a factor of e^ε when a single data point is altered, plus a small δ probability of failure.
• Privacy-Loss Random Variable: The actual privacy cost for a specific output; ε is a bound on its worst-case magnitude.
• Application: In federated learning, DP is applied at the client-level, protecting the participation and data of any single device.

The systematic process of tracking cumulative privacy loss (ε, δ) across multiple queries or training steps to ensure the total does not exceed the allocated privacy budget.

• Composition: The core challenge is accounting for sequential, adaptive applications of DP mechanisms (e.g., multiple federated averaging rounds).
• Advanced Accountants: Simple sequential composition is loose. Tighter accounting uses:
  • Rényi DP (RDP) / zCDP: Provide cleaner composition for Gaussian mechanisms.
  • Moment Accountant: Used in DP-SGD to tightly bound privacy loss across many iterations.
• Output: Produces a running total (ε_used, δ_used) to compare against the budget (ε_total, δ_total).

Mathematical rules that define how privacy parameters degrade when multiple differentially private mechanisms are composed.

• Basic Sequential Composition: Applying k mechanisms with guarantees (ε_i, δ_i) yields a total guarantee (Σε_i, Σδ_i). This is simple but pessimistic.
• Advanced Composition: Provides tighter bounds, especially for many compositions. For (ε, δ)-DP mechanisms, the total ε grows roughly with √k.
• Parallel Composition: If mechanisms are applied to disjoint subsets of data, the overall ε is the maximum of the individual ε_i, not the sum. This is key for privacy amplification by subsampling in federated learning.

The canonical algorithm for consuming a privacy budget in federated learning. It modifies the standard FedAvg protocol to provide client-level DP.

• Client-Side Steps:
  1. Local Training: Client computes a model update (e.g., gradient).
  2. Gradient Clipping: The update's norm is clipped to a threshold C to bound its sensitivity.
  3. Noise Addition: Calibrated Gaussian (or Laplace) noise is added to the clipped update.
• Server-Side: The server performs a secure aggregation of the noised client updates. The aggregated result is differentially private.
• Budget Consumption: Each communication round consumes a portion of the total privacy budget, tracked via privacy accounting.

The maximum possible change in the output of a function (e.g., a query or a model update) when a single individual's data is added or removed. It is the fundamental determinant of how much noise must be added for DP.

• Mathematical Definition: For a function f, its L2 sensitivity Δf = max_{D, D'} ||f(D) - f(D')||₂, where D and D' are neighboring datasets.
• Role in Noise Scaling: In the Gaussian mechanism, the noise scale σ is proportional to Δf / ε. A lower sensitivity allows for less noise for the same ε.
• Controlling Sensitivity: In ML, gradient clipping is used explicitly to bound the L2 sensitivity of the per-client model update to a predefined clip threshold C.

A set of techniques where the application of a DP mechanism under certain conditions yields a stronger effective privacy guarantee (smaller ε) than its baseline analysis.

• Amplification by Subsampling: When a DP mechanism is applied to a random sample (e.g., a subset of clients in a federated round), the effective privacy loss is reduced. The privacy budget is spent more efficiently.
• Amplification by Shuffling: In local DP models, if user reports are anonymized and shuffled by a trusted intermediary before analysis, the central privacy guarantee can be significantly stronger than the local guarantee.
• Impact on Budget: These techniques allow for more training rounds or lower noise for the same total privacy budget, improving the utility-privacy trade-off.