Privacy Budget

A privacy budget is a non-renewable resource that is depleted with every differentially private query. Once the total epsilon (ε) allocation is exhausted, no further queries can be answered with the same privacy guarantee. This forces a strategic trade-off: data scientists must prioritize high-value analyses and avoid wasteful, exploratory queries that burn through the budget without yielding actionable insights. The budget is typically set by a privacy officer or governance board based on regulatory requirements and organizational risk tolerance.

The privacy budget obeys composition theorems that quantify how privacy loss accumulates across multiple queries:

• Basic Composition: Running k mechanisms, each with privacy loss εᵢ, results in a total privacy loss of Σεᵢ (the sum of individual epsilons).
• Advanced Composition: Provides a tighter bound, showing that the total privacy loss grows sublinearly (proportional to √k) under certain conditions, allowing more queries for the same total budget.
• Parallel Composition: When queries operate on disjoint subsets of the data, the total privacy cost is the maximum of the individual epsilons, not their sum.

Understanding these theorems is critical for budget accounting in complex analytical workflows.

The privacy budget is denominated in epsilon (ε), the fundamental unit of privacy loss in differential privacy. A smaller epsilon indicates a stronger privacy guarantee:

• ε = 0: Perfect privacy, but zero utility (output is pure noise).
• ε = 0.1 to 1: Strong privacy, suitable for highly sensitive data like medical records.
• ε = 1 to 10: Moderate privacy, common in industry deployments.
• ε > 10: Weak privacy guarantees; often considered insufficient for sensitive data.

The choice of epsilon is a policy decision that balances the risk of individual re-identification against the analytical utility of the results.

A differentially private system must enforce budget limits by refusing queries once the cumulative privacy loss reaches the predefined threshold. This is implemented through a privacy accountant—a software component that tracks epsilon expenditure in real-time. When a new query is submitted, the accountant:

1. Calculates the privacy cost of the proposed query.
2. Checks if sufficient budget remains.
3. Either approves the query and deducts the cost, or blocks the query with a budget-exhausted error.

This mechanism prevents privacy budget overruns and ensures the system's privacy guarantees remain mathematically valid over its entire operational lifetime.

Organizations must decide how to partition their total privacy budget across different stakeholders and use cases:

• Uniform Allocation: Each analyst or department receives an equal share of the budget.
• Priority-Based Allocation: Critical research questions receive larger allocations; exploratory analyses receive smaller ones.
• Tiered Access: Different user roles have different epsilon thresholds (e.g., senior researchers get ε=1, interns get ε=0.1).
• Time-Based Refresh: The budget resets periodically (e.g., quarterly), allowing new queries while limiting long-term cumulative leakage.

Effective allocation requires governance frameworks that align privacy expenditure with organizational priorities.

In (ε, δ)-differential privacy, the privacy budget includes a second parameter, delta (δ), which represents the probability that the privacy guarantee fails catastrophically. While epsilon bounds the multiplicative privacy loss, delta accounts for rare failure events. A typical setting is δ = 1/n² (where n is the dataset size), ensuring the failure probability is cryptographically negligible. The privacy accountant must track both epsilon and delta expenditure, as delta also composes across queries. This two-parameter model provides a more practical privacy framework than pure ε-differential privacy alone.

Think of the privacy budget as a ledger with a fixed total epsilon (ε). Every differentially private query or model training run withdraws a specific amount of epsilon from this ledger. Once the total budget is exhausted, no further queries can be answered without risking re-identification. This is often enforced by a privacy accountant component in the system.

• Total Budget (ε_total): The maximum privacy loss tolerated (e.g., ε = 1.0).
• Per-Query Cost: The epsilon consumed by a single operation.
• Exhaustion: The system must deny access once the budget is spent.

A fundamental theorem of differential privacy states that privacy loss accumulates linearly under sequential composition. If you run two queries on the same dataset, one with privacy loss ε₁ and another with ε₂, the total privacy loss is simply ε₁ + ε₂. This is the core mechanism that necessitates a budget.

• Rule: Total ε = Σ ε_i for k independent mechanisms.
• Implication: An analyst cannot simply run unlimited queries; each one chips away at the finite budget.

Privacy loss does not accumulate when queries are applied to disjoint subsets of data. If a dataset is partitioned into non-overlapping chunks, and a differentially private mechanism is applied independently to each chunk, the total privacy cost is the maximum of the individual costs, not the sum.

• Rule: Total ε = max(ε_i) for queries on disjoint data.
• Optimization: This allows system architects to partition data by user or institution to maximize utility under a fixed budget.

The simple linear accounting of sequential composition is a loose bound. Advanced composition theorems provide a tighter, sub-linear bound on privacy loss over multiple queries, but introduce a small failure probability (δ). This allows for more queries under a given ε budget at the cost of a slightly relaxed (ε, δ)-differential privacy guarantee.

• Benefit: Enables iterative machine learning with thousands of steps.
• Trade-off: Introduces a δ term, typically cryptographically small (e.g., δ < 1/N).
• Moments Accountant: A modern technique used in DP-SGD to track a tighter bound on privacy loss.

A strict privacy budget acts as a data access expiry mechanism. In a federated learning system, a hospital's data curator might allocate a total budget of ε = 2.0 for a research project. Once the cumulative epsilon spent by the central model's queries reaches 2.0, the node must permanently block further access to that specific data slice for that project.

• Hard Limit: No administrative override should bypass budget exhaustion.
• Reset Policy: Budgets may be reset only with explicit re-consent or a new data use agreement.

The privacy budget is the dial that controls the utility-privacy trade-off. A larger budget (e.g., ε = 10) permits more accurate analytics but provides weaker privacy guarantees. A smaller budget (e.g., ε = 0.1) provides strong deniability but injects so much noise that the data may become useless for precise clinical research.

• High ε: High accuracy, low privacy.
• Low ε: High privacy, low accuracy.
• Goal: Find the minimum ε that still yields statistically significant results.