Differential Privacy and Privacy Budgets

Differential privacy bounds how much the probability of released outputs can change when one protected unit is added or removed from the dataset. The guarantee is formal. Its meaning is not. That depends on adjacency, epsilon, delta, mechanism, composition, and how the thing was implemented. Two systems quoting the same epsilon can protect very different things once adjacency and composition are written down. Smaller epsilon generally means a stronger bound. Delta captures a small failure probability in approximate DP. Budgets compose across repeated releases.

In DP-SGD, per-example gradient clipping and calibrated noise combine with sampling and a privacy accountant. What a tighter budget costs is not a matter of opinion. It has been measured on the same data at several budgets. In 2016 Abadi and colleagues reported MNIST test-set accuracy of 90%, 95% and 97% at (0.5, 10^-5), (2, 10^-5) and (8, 10^-5)-differential privacy. The lot size was 600, and each layer's gradient norm was clipped at 4. On CIFAR-10 the same method reached 67%, 70% and 73% at ε = 2, 4 and 8 with δ = 10^-5. Those runs used a larger lot size, 2,000, and clipping values tried between 3 and 10. Two datasets, three budgets each. The accuracy moves with the budget every time.

Their own summary of that result is deliberately modest: “Our implementation and experiments demonstrate that we can train deep neural networks with non-convex objectives, under a modest privacy budget, and at a manageable cost in software complexity, training efficiency, and model quality.”

A modest budget and a manageable cost. Both quantified, neither claimed to be free.

These three are routinely presented as alternatives to each other. They protect against different things, and two of them offer no numerical bound at all.

De-identification attempts to remove identifying information. It is context-dependent and vulnerable to linkage. It carries no universal numerical privacy bound, is often useful before other controls, and is not equivalent to differential privacy. Differential privacy bounds participation influence under a formal model. It supports composition and post-processing, and it requires explicit parameters and assumptions. It can reduce utility for small or complex data, and it does not prevent every harm or misuse. Access control limits who can obtain data or outputs. It is an essential operational safeguard, and it can be revoked and monitored. It does not bound information inside an authorized release, and it complements rather than replaces a formal budget.

The cost of confusing the first with the second has been measured by the agency that paid it. Thirty-four published tables were enough to rebuild the 2010 Census. Working from those aggregates alone, Abowd and colleagues reconstructed block, sex, age, race and ethnicity for the confidential person records: “Ninety-seven million person records (every resident in 70% of all census blocks) are exactly reconstructed with provable certainty using only public information.” Within the blocks reconstructed perfectly, the attack went further. It correctly inferred the actual census race and ethnicity responses of 3.4 million “vulnerable population uniques” — population-unique persons with nonmodal characteristics — with 95% accuracy. The bureau published the study in December 2023.

No one had released a microdata file. Thirty-four tables of aggregates were enough. That is what "no universal numerical bound" means in practice, and why the same bureau moved to a formal budget for 2020.

Apple states its budgets feature by feature and donation by donation. From its own Differential Privacy Overview: “For Lookup Hints, Apple uses a privacy budget with epsilon of 4, and limits user contributions to two donations per day. For emoji, Apple uses a privacy budget with epsilon of 4, and submits one donation per day. For QuickType, Apple uses a privacy budget with epsilon of 8, and submits two donations per day.” Health types carry epsilon 2, one donation per day.

Every one of those numbers is on the record. Their sum is not. In 2017 Tang and Korolova, with three co-authors, reverse-engineered the implementation in macOS Sierra 10.12. They found a per-datum loss of 1 or 2. They also found an overall permitted loss as high as 16 per day, across Emojis, New words, Deeplinks and Lookup Hints, with the budget renewed every day.

This is not a team that failed to run an accountant. It is a shipped deployment with published parameters. The quantity a person would actually want — what my participation costs me, across features, across days — was never stated.

A guarantee is assembled from five decisions. What counts as one unit — adjacency: record, person, device or group. How much that unit can move the result — sensitivity and clipping. How randomness enters — the mechanism. How the budget is tracked — accounting. And what it costs in utility.

The fourth looks like bookkeeping and is not. Take one identical computation from that 2016 DP-SGD work: lot size L = 0.01N, noise scale σ = 4, δ = 10^-5, and T = 10,000 steps. Under the authors' own moments accountant it was reported at ε ≈ 1.26. Under the strong composition theorem, ε ≈ 9.34. Same mechanism, same noise, same number of steps. Two composition analyses, two budgets. As the paper puts it: “In our work, we invent a stronger accounting method, which we call the moments accountant.”

1.26 and 9.34 are not a disagreement about how private the run was. They are the same run, analysed twice. An epsilon quoted without its accountant beside it cannot be compared with anyone else's.

Start where the marketing does not. What exactly does this guarantee promise, and to whom? There is now a numbered public standard to review against, so the checklist need not be a house method.

NIST published SP 800-226, Guidelines for Evaluating Differential Privacy Guarantees, in final form in March 2025. The initial public draft had come out in December 2023. It was issued to fulfil one of NIST's assignments under the Executive Order on Safe, Secure, and Trustworthy Artificial Intelligence. The final publication no longer cites that order.

It organises evaluation around a differential privacy pyramid. At the top sit the privacy parameters: ε, and the unit of privacy. In the middle, the algorithms — correctness, utility and bias. At the bottom, access control, trust models, side channels and data collection. And it refuses to let a reviewer stop at the top: “Evaluating any claim to differential privacy protection requires examining every component of the pyramid.”

Work outward from the protected unit to the budget that governs every future release.

First, define the protected unit. Choose adjacency from the privacy promise and the data relationship. Sensitivity is the amount any single argument can change the output, and there is no such quantity until the unit is fixed.

Second, bound the contribution: clipping, aggregation, sensitivity rules. The DP-SGD authors clipped each layer's gradient norm at 4 on MNIST and tried values between 3 and 10 on CIFAR-10. That is the shape of a decision, not a default.

Third, choose the mechanism and name the accountant. Document sampling, noise, epsilon, delta and composition. 1.26 and 9.34 came from the same run under two composition analyses.

Fourth, evaluate utility and disparity — task performance, rare cases, groups and operational thresholds — across several budgets, not one.

Fifth, govern the budget. Approve releases, track cumulative use, and communicate what remains. A named committee published 19.61, split it 17.14 and 2.47, and let the argument happen in the open.

Privacy budget is spent rather than owned. So the accounting stays visible for as long as releases continue.

Four numbers from this lesson carry the whole argument. 19.61, chosen by a committee on 9 June 2021 and split 17.14 to 2.47, argued over ever since precisely because it was published. 1.26 against 9.34, one identical run under two accountants. 97 million records rebuilt from 34 tables, under the regime that came before. 97% falling to 77% for a class that was already small.

Set in advance the epsilon, utility or disparity result that would force the owner to redesign, restrict, remedy or retire the model. A class gap of at least 20% is a defensible trigger to write down. It is far easier to name before the release than after it.