Privacy Loss Accounting

Differential privacy is usually introduced as noise added to a query result. That framing is where most implementations go wrong, because the guarantee is not a property of a query. It is a property of everything ever released from the data.

Ask for a count, add noise, publish. Ask a slightly different question, add noise, publish again. Repeat enough times and the noise averages out: an attacker who can pose many related queries recovers the underlying values with arbitrary precision. The formal guarantee survives this only because composition is accounted for — each release consumes part of a fixed budget, and when the budget is exhausted, the dataset stops answering.

Privacy loss accounting is the bookkeeping that makes the guarantee real, and it is the part teams skip because it is infrastructure rather than mathematics.

Why it matters

Without accounting, a differentially private system provides a strong-sounding guarantee it does not have. The noise is genuinely applied; the bound is not enforced; and the publication is defensible only until someone counts the queries.

Accounting also converts an unbounded argument into a design decision with a shape. The budget is a fixed quantity divided among the statistics you intend to publish, so the decisions become concrete: which statistics matter, at what accuracy, over which populations, and what is left out in order to afford them.

Implementation patterns

• Set the budget for the publication, not for the query, and record every release against it in a ledger that survives staff turnover.
• Work backwards from an accuracy requirement. The US Census Bureau's 2020 approach is the model: state the target in operational terms — the largest racial or ethnic group in a geography of 500 or more people within 5 percentage points at least 95% of the time — then allocate budget to meet it, rather than arguing about epsilon in the abstract.
• Allocate deliberately across the query set, because it is a division problem: the more statistics, the less budget each, and noise per statistic rises as its allocation falls.
• Use the tighter composition accountants where the tooling supports them; naive summation overstates loss and wastes budget that could have bought accuracy.
• Post-process freely. Enforcing non-negativity and hierarchical consistency does not consume budget, though it redistributes error — typically onto small cells, which is what generated most of the criticism of the 2020 Census outputs.
• Enforce at the boundary. The accountant must sit in the only path by which results leave; an analyst with direct query access to the raw data bypasses it entirely.

Industry example

The 2020 US Census is the largest deployment with a public record of its reasoning. The Bureau published demonstration products in April 2021 at global epsilon values of 4.5 and 12.2 for the person-level data — real numbers chosen under sustained public scrutiny rather than a universal recommendation — and applied the mechanism to the August 2021 redistricting data and the subsequent detailed demographic file.

The public argument that followed is the instructive part. Users of small-area data objected that the noise, redistributed by consistency enforcement, made neighbourhood-level analysis unreliable. Both sides were right, and the disagreement is the trade-off made visible: a formal guarantee buys defensibility and pays in small-cell accuracy, and no amount of engineering removes that.

Failure scenarios

• Per-query budgets. Each release is "private" and the cumulative loss is unbounded, which is the most common implementation error and the one that voids the guarantee entirely.
• An unenforced ledger. Accounting exists in a document while analysts hold direct access, so the recorded loss and the actual loss diverge silently.
• Budget exhaustion mid-programme, discovered when a required statistic can no longer be published — a governance failure, since the allocation should have reserved for it.
• Small cells published at any budget, producing numbers that are formally private and practically meaningless, which erodes trust in the whole publication.
• The wrong unit of privacy. Protecting a record when a person contributes many records gives a much weaker guarantee than the label suggests; the unit must be the individual, not the row.
• Re-running a pipeline on the same data and treating it as free, when each run is a release.

Trade-offs

When not to use it

Inside a trust boundary, this is the wrong tool. For internal analytics on data that never leaves, with logged access and contractual purpose limits, access control and purpose limitation deliver more protection per unit of effort, and the noise degrades the analysis the environment exists to enable.

It is also the wrong answer when the use case genuinely needs small-cell precision. If decisions depend on counts of 10 to 50 people, differential privacy will either fail the use case or fail the guarantee, and the right response is a different access model — a controlled research environment under agreement — rather than a public release with more noise.

Interview question

Q: A team proposes publishing statistics under differential privacy, with epsilon set per query so each release is provably private. Explain what is wrong, and describe what you would put in place instead — including how you would decide the budget.

What a strong answer covers: composition, and that repeated related queries average the noise away so a per-query bound gives no overall guarantee; a single publication budget with an enforced ledger at the only egress path; working backwards from a stated accuracy target rather than arguing epsilon, with the Census target as the shape of such a statement; allocation as a division problem where the smallest cells bind; that post-processing is free but redistributes error onto small cells; the unit-of-privacy question when one person contributes many rows; and the honest statement that small-cell use cases need a controlled environment instead.

Quick check

Quiz: Why does setting epsilon per query fail? — Noise averages out across repeated related queries, so an attacker posing enough of them recovers the underlying values; the guarantee only holds if cumulative loss across all releases is bounded and tracked.

Flashcard: How should a privacy budget be decided? — Backwards from an operational accuracy target for the statistics that matter, as the 2020 Census did, then allocated across the intended query set — not by arguing about epsilon in the abstract.