Privacy Accounting

The privacy budget is a finite allocation of privacy parameters—typically epsilon (ε) and delta (δ)—that acts as a resource to be spent. It defines the maximum allowable cumulative privacy loss for an entire analysis pipeline.

• Epsilon (ε): The primary privacy loss parameter. A smaller ε indicates a stronger guarantee.
• Delta (δ): A small probability that the ε guarantee fails, representing a statistical margin of error.
• The system's core function is to ensure total spent (ε_total, δ_total) ≤ budget (ε_target, δ_target).

Composition theorems are the mathematical rules that govern how privacy loss accumulates when multiple differentially private mechanisms are applied to the same dataset. The accounting system uses these to calculate the total cost of a sequence of operations.

• Basic Composition: Provides a simple, linear bound (ε_total = k * ε for k mechanisms). It is conservative.
• Advanced Composition (e.g., for DP-SGD): Provides tighter, sub-linear bounds using tools like the moment accountant or Rényi Differential Privacy (RDP), allowing for more queries within the same budget.

The privacy loss random variable is a foundational concept for advanced accounting. It quantifies the actual privacy cost as a random quantity that depends on the specific dataset and the randomness of the DP mechanism.

• The system tracks a bound on the distribution of this variable (e.g., its moment generating function).
• Methods like the moment accountant and frameworks like Zero-Concentrated DP (zCDP) analyze this variable's tail behavior to derive tight overall (ε, δ) bounds after many compositions.

Privacy amplification occurs when a mechanism's privacy guarantee is strengthened by an intermediate randomized step. The accounting system must correctly model these effects to avoid overestimating privacy loss.

• Amplification by Subsampling: When a DP mechanism is applied to a random subset (e.g., a mini-batch), the effective privacy cost per full dataset individual is reduced. This is critical for DP-SGD.
• Amplification by Shuffling: In federated settings, a secure shuffler between clients and the aggregator can amplify local DP guarantees to stronger central DP guarantees.

In real-world analysis, queries are often adaptive, meaning each new query can depend on the answers to previous ones. The accounting system must provide valid guarantees under this adaptive adversary model.

• It treats the entire sequence of mechanisms as an adaptive composition.
• Advanced theorems (like those for the moment accountant) are designed to hold under adaptive composition, which is more realistic than assuming all queries are fixed in advance.

The audit log is the immutable record of all privacy-releasing operations, their associated privacy parameters, and the cumulative spend. It is essential for compliance, debugging, and transparency.

• Per-Operation Record: Logs the mechanism type, its (ε, δ) cost, and timestamp.
• Running Total: Continuously updates the cumulative (ε_total, δ_total).
• Budget Exhaustion Alerts: Triggers warnings or halts analysis when the budget is nearing depletion.
• Report Generation: Produces verifiable proof of compliance with the declared privacy budget.

Privacy accounting is foundational for training models with Differentially Private Stochastic Gradient Descent (DP-SGD). Each training step consumes a portion of the privacy budget (ε, δ). Accounting tracks this consumption across thousands of iterations to ensure the final model adheres to the total allowed budget.

• Mechanism: Per-example gradient clipping and Gaussian noise addition.
• Key Challenge: Tighter composition bounds (e.g., using Rényi DP) are required for feasible utility.
• Example: Training a deep neural network for 100 epochs with a target of (ε=8, δ=1e-5) requires precise per-iteration noise calibration and budget tracking.

In federated learning, accounting tracks client-level privacy loss across communication rounds. Clients add noise to their updates locally, and the server must account for the composition of these noisy contributions.

• Granularity: Protects the participation and data of any single device (client-level DP).
• Process: Each round of DP-Federated Averaging consumes budget. Advanced accounting must handle random client sampling, which provides privacy amplification.
• Critical for: Healthcare and financial federated learning, where proving a bounded, auditable privacy loss is a regulatory requirement.

Organizations use privacy accounting to safely release aggregate statistics from sensitive databases (e.g., census, medical records). Each query—counts, averages, histograms—consumes budget.

• Workflow: A data curator sets a total privacy budget. An accounting module tracks expenditure as analysts submit queries via the Laplace or Gaussian mechanism.
• Enforcement: The system blocks queries once the budget is exhausted, preventing privacy degradation.
• Example: A health agency releases weekly disease incidence statistics while guaranteeing each patient's record is protected.

Selecting the best model architecture or hyperparameters requires multiple evaluations on private data. Naive evaluation would rapidly deplete the privacy budget.

• Solution: Advanced accounting techniques, like using the exponential mechanism or allocating a dedicated sub-budget for the tuning phase, allow for efficient exploration.
• Trade-off: The budget spent on tuning is not available for final model training, requiring careful allocation.
• Ensures: The final model selection process itself is differentially private and accounted for.

For systems that release updated statistics over time (e.g., daily COVID-19 metrics, real-time economic indicators), accounting must manage an evergreen or replenishing privacy budget.

• Challenge: Data evolves, and releases are correlated, making simple composition overly conservative.
• Advanced Methods: Use pan-private algorithms or privacy filters that allow for adaptive spending while maintaining a lifetime guarantee.
• Application: Smart city dashboards that release traffic or utility usage data without compromising resident privacy over long periods.

Privacy accounting provides the verifiable proof needed for compliance with regulations like GDPR, HIPAA, or the EU AI Act. It generates an audit log of all privacy-releasing operations.

• Output: A certified report detailing the initial budget, consumption per operation (with timestamps and parameters), and remaining budget.
• Essential for: Demonstrating due diligence and privacy by design to regulators and auditors.
• Function: Translates abstract mathematical guarantees (ε, δ) into a concrete, inspectable record of system behavior.

Composition theorems are the mathematical rules that govern how privacy guarantees degrade when multiple differentially private mechanisms are applied to the same dataset. They are the foundation of all privacy accounting.

• Basic Composition: States that the privacy parameters (ε, δ) add linearly for a sequence of mechanisms. If you run k mechanisms each satisfying (ε, δ)-DP, the total guarantee is (kε, kδ)-DP. This is simple but often overly pessimistic.
• Advanced Composition: Provides a tighter bound, showing that the ε parameter grows roughly with the square root of the number of compositions (√k) for a fixed δ. This is critical for iterative algorithms like DP-SGD that may run for thousands of steps.
• Heterogeneous Composition: Accounts for composing mechanisms with different (ε_i, δ_i) guarantees, which is common in adaptive query settings.

Rényi Differential Privacy is a relaxation of (ε, δ)-DP defined using Rényi divergence. It is not a directly interpretable guarantee for end-users but is a powerful analytical tool for tight composition.

• Mechanism: A randomized mechanism M satisfies (α, ε)-RDP if the Rényi divergence of order α between the outputs on any two neighboring datasets is at most ε.
• Key Advantage: RDP often yields much tighter bounds on the overall privacy loss after many compositions compared to basic or advanced composition theorems. The final RDP guarantee can be converted back to a standard (ε, δ)-DP guarantee for reporting.
• Primary Use Case: It is the preferred accounting method for Gaussian noise-based mechanisms like DP-SGD, as the composition of Gaussian mechanisms is naturally expressed and analyzed in the RDP framework.

The moment accountant is a specific privacy loss tracking method introduced for DP-SGD. It is an implementation of Rényi DP accounting that provides state-of-the-art privacy bounds for iterative training algorithms.

• Process: Instead of tracking a fixed (ε, δ), it tracks a privacy loss random variable. It bounds the log moments of this variable at each training step (e.g., each gradient update with noise).
• Composition: The bounds on these moments compose linearly and easily across steps. After all compositions, the tail bound of the privacy loss random variable is used to derive the final (ε, δ) guarantee.
• Result: This method typically allows for training models with the same final privacy guarantee using significantly less noise per step compared to using advanced composition directly, or for achieving a much stronger privacy guarantee for a fixed noise level.

A privacy budget is a finite, pre-allocated amount of allowable privacy loss (ε, and sometimes δ) for a data analysis pipeline. Privacy accounting is the process of ensuring this budget is not exceeded.

• Allocation: Set by policy or regulation (e.g., ε=1.0, δ=1e-5). It represents the total "privacy currency" available to spend on queries or model training.
• Consumption: Each differentially private operation (a query, a training epoch) consumes a portion of this budget, as calculated by composition theorems. The accountant tracks the remaining budget.
• Exhaustion: Once the budget is spent, no further analyses on the sensitive dataset should be performed, as the cumulative privacy loss would violate the pre-defined guarantee. This enforces a hard limit on data usage.

Privacy amplification refers to techniques that strengthen a privacy guarantee (result in a smaller effective ε) by introducing randomness in the data access pattern itself. It is a crucial tool for making high-privacy iterative training feasible.

• Amplification by Subsampling: The most common form. When a DP mechanism is applied to a random subset (e.g., a mini-batch) of the dataset, the effective privacy guarantee is stronger than if it were applied to the full dataset. The privacy loss is reduced by a factor roughly proportional to the sampling probability.
• Amplification by Shuffling: In federated/local DP settings, if client reports are collected and then randomly shuffled before analysis, the privacy guarantee can be amplified because it becomes harder to link a report to a specific individual.
• Impact on Accounting: Any rigorous privacy accounting system for algorithms like DP-SGD must incorporate amplification by subsampling to report accurate, non-pessimistic (ε, δ) values.

Zero-Concentrated Differential Privacy is a variant of DP that sits between pure DP and RDP. It is designed for clean and simple composition of Gaussian-based mechanisms.

• Definition: A mechanism satisfies ρ-zCDP if the privacy loss random variable is subgaussian with a variance of ρ. A smaller ρ means stronger privacy.
• Composition Simplicity: zCDP composes linearly: running two mechanisms satisfying ρ1-zCDP and ρ2-zCDP gives a mechanism satisfying (ρ1+ρ2)-zCDP. This is simpler than RDP composition across orders (α).
• Relationship to (ε, δ): A ρ-zCDP guarantee can be converted to a family of (ε, δ)-DP guarantees for any δ > 0. It is particularly well-suited for analyzing the Gaussian mechanism and its compositions, often providing tight bounds.