Privacy Odometers

A privacy odometer maintains a running tally of the total privacy loss parameter epsilon (ε) consumed across an adaptive sequence of queries. It applies the composition theorem to sum the privacy cost of each mechanism as it is invoked. Unlike static budget allocation, the odometer does not require pre-specifying the number or type of queries. It simply subtracts the cost of each query from the remaining budget and halts all access when the cumulative loss reaches the global limit ε_total, preventing budget overruns.

The defining feature of a privacy odometer is its ability to handle interactive, adaptive queries where each subsequent question may depend on the results of previous answers. The mechanism must account for this inter-dependency in its privacy loss tracking. Standard composition theorems assume a worst-case adaptive adversary, and the odometer enforces this bound. This allows a data analyst to drill down into a dataset, refine hypotheses, and explore freely, with the odometer acting as a hard circuit breaker that permanently severs access the moment the privacy guarantee would be violated.

Accurate odometry relies on tight numerical composition to avoid prematurely exhausting the budget. Key methods include:

• Moments Accountant: Tracks the log-moments of the privacy loss random variable for tight bounds on DP-SGD.
• Rényi Differential Privacy (RDP): Converts RDP guarantees to standard (ε, δ)-DP for cleaner composition.
• Privacy Loss Distribution (PLD): Uses Fourier transforms to compute the exact distribution of the cumulative loss, providing the tightest known bounds.
• Gaussian Differential Privacy (GDP): Composes via a central limit theorem for Gaussian mechanisms, simplifying accounting.

A privacy odometer is inherently stateful. It must persist the consumed budget across queries, making it a bottleneck in distributed systems. This contrasts with stateless mechanisms that can be independently invoked without coordination. In practice, a centralized odometer service must be hardened against faults and rollbacks. A crash that resets the odometer's state would allow an attacker to reset the privacy budget, violating the guarantee. Implementations often use durable, append-only logs or secure hardware to maintain the integrity of the counter.

In machine learning, the privacy odometer concept is most visible in Differentially Private Stochastic Gradient Descent (DP-SGD). Each training step consumes a small amount of the privacy budget. The odometer tracks the cumulative epsilon across all epochs and training iterations. When the pre-allocated budget is fully consumed, training must stop. This is why DP-SGD models often report a specific (ε, δ)-DP guarantee at a fixed number of epochs—the odometer has enforced a hard stop on optimization to preserve the formal privacy bound.

A privacy odometer can be configured with a threshold function that triggers an action before the total budget is fully exhausted. For example, a system might issue a warning at 90% budget consumption, switch to a coarser but cheaper mechanism, or reject only high-sensitivity queries while allowing low-sensitivity ones. This graceful degradation prevents a sudden, hard cutoff that would disrupt a user's workflow. The odometer's logic can be extended to manage multiple, parallel budgets for different user roles or data partitions.

The formal mathematical basis for a privacy odometer. It quantifies how the total privacy loss parameter ε accumulates when multiple differentially private mechanisms are run on the same dataset.

• Sequential Composition: The total ε is the sum of the ε values of each mechanism.
• Parallel Composition: When queries run on disjoint data subsets, the total ε is the maximum of the individual ε values.
• A privacy odometer enforces these rules adaptively, halting queries when the composed budget is exhausted.

A sophisticated accounting method that tracks the moments of the privacy loss random variable to compute a much tighter bound on total privacy loss than simple linear composition.

• Essential for Differentially Private Stochastic Gradient Descent (DP-SGD) , where noise is added in thousands of iterative steps.
• Enables a privacy odometer to provide a more accurate, less conservative estimate of the remaining budget, allowing for more useful queries before the limit is reached.

A privacy definition based on Rényi divergence that provides a natural framework for composing Gaussian mechanisms with tight bounds.

• An RDP accountant tracks privacy loss as a function of the order α.
• A privacy odometer can use RDP accounting to monitor the cumulative privacy cost and convert the final RDP guarantee back to a standard (ε, δ)-DP guarantee, often yielding a significantly smaller ε than basic composition.

The finite, quantifiable resource that a privacy odometer is designed to manage and enforce. It represents the maximum allowable privacy loss (ε) for all analyses on a dataset.

• The odometer acts as the active gatekeeper, deducting the cost of each query from the budget.
• Once the budget is depleted, the odometer refuses all further queries, ensuring the global ε guarantee is never violated, regardless of the analyst's adaptivity.

A mechanism that answers a stream of threshold queries while consuming privacy budget only for queries that exceed the threshold.

• A privacy odometer is critical here, as the number of above-threshold queries is unknown in advance.
• The odometer tracks the cost of each released answer and halts the stream once the budget is spent, making SVT practical for adaptive monitoring tasks like detecting anomalies in a data stream.

A modern privacy framework that characterizes a mechanism by its trade-off function between Type I and Type II errors in a membership inference attack.

• Composition is elegantly handled by a central limit theorem for privacy, where the composition of many GDP mechanisms converges to a simple GDP mechanism.
• A privacy odometer built on GDP accounting can track privacy loss using a single parameter, μ, and provide a tight, operational interpretation of the final guarantee.