Privacy Budgets Under Composition: Accounting for Repeated Statistical Release

The protected unit is part of the definition

A statement that a release is differentially private is incomplete until neighboring datasets are defined. Removing one event, replacing one row, and removing all records belonging to one person describe different changes. A mechanism calibrated for one event may provide a much weaker guarantee for a person who contributes many events.

The query and its sensitivity must use the same adjacency relation. If an individual can contribute an unbounded number of rows to a count, a one-row sensitivity calculation does not establish a user-level guarantee. Contribution clipping, deduplication, or another bounded representation can make the intended sensitivity finite, but those preprocessing steps must be specified. The privacy parameter is therefore a property of a complete mechanism and data model, not a label attached after noise is added.

The three primary contributions

Dwork and colleagues connect noise calibration to the sensitivity of a query under neighboring datasets. Mironov introduces Renyi differential privacy as a way to describe privacy loss and compose mechanisms through divergence bounds. Balle and Wang revisit Gaussian calibration and show why direct analytical treatment can improve on conventional sufficient bounds.

These results play different roles. Sensitivity establishes how much a query can change. An accountant combines privacy loss across releases. Calibration chooses a noise level for a desired guarantee. A valid but conservative bound is not necessarily the tightest available bound, and a tighter accountant cannot repair an incorrect sensitivity assumption. We keep those tasks separate throughout the worked example. [1], [2], [3]

Why the Laplace construction depends on sensitivity

For a scalar query with maximum neighboring difference Delta, adding Laplace noise with scale Delta divided by epsilon gives the familiar pure-privacy construction. The density ratio at any output can be bounded using the triangle inequality: the difference between the two absolute-distance terms is no larger than the distance between the two query values.

This short argument explains exactly where the sensitivity bound enters. If the actual neighboring difference exceeds Delta, the claimed ratio bound can fail. The variance of the added noise is twice the square of its scale, so protecting a larger contribution changes accuracy quadratically in this simple mechanism. The formula concerns the declared scalar query and adjacency model. It does not automatically apply to a vector, a selection procedure, or an unbounded data-dependent preprocessing stage. [1]

Composition counts access to the private data

Releasing one private estimate and applying any data-independent transformation to that estimate is post-processing. Asking the private dataset for a fresh independently noised estimate is another mechanism invocation. These operations can look identical to an interface designer while having different privacy costs.

A dashboard that refreshes an estimate every minute may therefore consume a release budget even when the underlying query text is unchanged. Reusing a cached released value does not create another dataset access, but recomputing with new noise does. Adaptive query choice also needs composition accounting: the next query may depend on earlier private outputs. The accounting framework must cover that interaction rather than assuming the queries were fixed independently of previous results. [2]

A Gaussian accounting example with explicit assumptions

Consider k invocations of an unsampled Gaussian mechanism, each with L2 sensitivity Delta and independent noise standard deviation sigma. At Renyi order alpha greater than one, one invocation has a divergence bound proportional to alpha Delta squared divided by twice sigma squared. Composition adds these bounds. Converting to an approximate-DP guarantee introduces a logarithmic term involving delta and alpha.

Optimizing this particular conversion over continuous alpha gives a sufficient choice epsilon_bound equal to a plus twice the square root of a times log of one over delta, where a is k Delta squared divided by twice sigma squared. This is a convenient sufficient bound, not the optimal analytical Gaussian guarantee. The figures fix Delta at one and delta at one millionth, vary k, and compare several sigma values. There is no subsampling amplification in this construction. [2], [3]

Repeated averaging reveals the cost of fresh answers

Suppose the same scalar query is released r times with independent zero-mean Gaussian noise of standard deviation sigma. Averaging the outputs leaves the query value unchanged and reduces the noise variance to sigma squared divided by r. A recipient can therefore improve accuracy simply by combining repeated answers.

This does not violate differential privacy. The composed guarantee becomes weaker as more fresh releases are made. Treating each answer as though it were the only release would be the error. The second figure plots the standard deviation of the average for a declared sigma of eight and juxtaposes the interpretation with the growing accounting bound in the first figure. It is an analytical illustration of composition, not evidence that any particular service has leaked a person's data.

Delta is not simply a failure probability

The approximate-DP inequality permits an additive delta slack between neighboring output distributions. It is tempting to describe delta as a literal probability that the entire database is exposed, but that is not a generally correct interpretation of the definition. The guarantee constrains distributions; operational risk depends on the mechanism, protected unit, and adversary's information.

A useful privacy report states epsilon, delta, adjacency, contribution limits, accountant, and the full release schedule. It should also explain the practical interpretation for the intended audience without replacing the formal statement with a misleading one-number assurance. Comparing two epsilon values is meaningful only when the other parts of the contract are compatible. A smaller epsilon for a single row can be less relevant than a larger epsilon for an entire user's bounded contribution.

Finite precision and data-dependent decisions

A mathematical mechanism uses ideal distributions and arithmetic, while software uses finite representations and random-number generators. Implementations must ensure that discretization, exceptional values, clipping, and error handling do not create unaccounted output distinctions. The privacy proof's mechanism should match the code's actual observable behavior.

Data-dependent decisions outside the nominal query also matter. Choosing whether to publish, selecting a clipping threshold from private data, or reporting an error only for a rare subgroup can itself reveal information. Such steps must be public, independently justified, or included in the privacy analysis. Adding correctly calibrated noise to the final numeric field cannot retroactively protect an earlier unprotected branch. This is another reason to review the entire release pipeline rather than the noise sampler alone.

Utility must be evaluated against the intended task

Noise magnitude alone is not a complete utility metric. A mechanism can have modest average error yet produce poor decisions for a small subgroup, a threshold, or a downstream nonlinear analysis. Conversely, post-processing can improve utility without additional privacy loss when it uses only the released output and public information.

The proposed evaluation therefore predeclares the task, contribution model, accuracy metric, and acceptable error distribution. It compares utility at the same privacy contract, not at the same nominal sigma when sensitivities differ. Analytical Gaussian calibration is relevant because conservative noise can unnecessarily reduce utility, but tighter calibration should be adopted only with a correctly implemented and reviewed mechanism. The privacy and utility arguments must meet at the same pipeline. [3]

A reproducible accounting record

The local appendix checks the continuous-order optimum against a dense numerical search and verifies the variance reduction of independent averaging algebraically. A production accountant would additionally need to track mechanism versions, sampling assumptions, adaptive invocations, and remaining budget in an auditable release ledger.

Negative controls should deliberately omit one release or change the contribution bound and confirm that the claimed guarantee changes. A frozen report should retain the exact accountant inputs and code version, allowing later correction without erasing the original claim. No private dataset is used here. The result is a transparent example of how an accounting argument can be made inspectable before it is relied upon in an actual data-release system.

Conclusion: account for the full release history

Differential privacy is strongest when its definition survives the transition from mathematics to product behavior. The neighboring unit, sensitivity, mechanism, composition rule, and observable release history jointly define the guarantee. None can be inferred from the presence of a noise term.

The repeated-query example shows why independently refreshing an answer differs from reusing an already released answer. The Gaussian calculation shows how a valid accounting bound can be derived while remaining conservative. A defensible privacy claim records those choices, tests the implementation against them, and evaluates utility under the same contract rather than treating epsilon as an isolated quality score.

Executed locally · Bounded scope

Numerical RDP minimization and independent-noise variance

Unsampled Gaussian mechanism accounting; not an empirical privacy audit or optimal analytic calibration.

8 assertions passed. These checks validate the supplied example, not the cited systems.

[
  {
    "k": 1,
    "sigma": 4,
    "closed": 1.345380442439233,
    "grid": 1.3453804424475089
  },
  {
    "k": 10,
    "sigma": 8,
    "closed": 2.1559476703363876,
    "grid": 2.1559476710706402
  },
  {
    "k": 100,
    "sigma": 16,
    "closed": 3.4806386060980823,
    "grid": 3.480638609062736
  },
  {
    "k": 1000,
    "sigma": 8,
    "closed": 28.590726703363874,
    "grid": 28.5907267107064
  }
]

Download all 20 executable examplesRead the complete check results

A declared analytical model

Four equations, explicit assumptions

Constructed examples · Reproducible data

Inspect the quantitative argument

These curves are calculated from the declared models. They are not observations from the cited studies. Every figure includes its numeric data and vector version.

Download CSVDownload SVG sourceReproduce with Python

Download CSVDownload SVG sourceReproduce with Python

Which evidence answers which question?

A proposed validation protocol

This is a proposed evaluation design. No production-system or hardware benchmark was performed. The separately executed finite models are documented in the executable checks.

1. Define neighboring datasets and enforce the corresponding contribution limit.
2. Enumerate all observable data-dependent outputs, including errors and selection steps.
3. Record every fresh mechanism invocation and distinguish cached post-processing.
4. Check the analytic RDP conversion against an independent numerical minimization.
5. Compare utility at the same complete privacy contract.
6. Preserve versioned accountant inputs, code, release history, and corrections.

What the primary sources establish

Limits of this analysis

• The formulas concern unsampled Gaussian and scalar Laplace examples; they do not cover every mechanism.
• The RDP conversion is a sufficient bound and can be looser than analytical Gaussian calibration.
• No private dataset, production accountant, or finite-precision sampler was audited.
• The review is technical analysis and does not constitute a deployment-specific privacy certification.

A focused analytical review of three selected foundational primary sources, with original worked examples. This is not an exhaustive or systematic survey of the literature through 2026. Source access and version notes are recorded with the bibliography.

Questions that would change the conclusion

1. Does the actual release pipeline expose data-dependent information outside its declared outputs?
2. Which refreshes are fresh private queries rather than post-processing of cached releases?
3. How much utility is lost to conservative accounting versus necessary protection of the intended unit?

References

1. Cynthia Dwork, Frank McSherry, Kobbi Nissim et al.. Calibrating Noise to Sensitivity in Private Data Analysis. Lecture Notes in Computer Science; Theory of Cryptography (2006). 10.1007/11681878_14.
2. Ilya Mironov. Rényi Differential Privacy. 2017 IEEE 30th Computer Security Foundations Symposium (CSF) (2017). 10.1109/csf.2017.11.
3. Borja Balle, Yu-Xiang Wang. Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. Proceedings of Machine Learning Research, vol. 80 (2018). Primary source.

Source [1] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Source [2] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Source [3] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Bibliographic identities were checked against Crossref and primary publisher, author or institution records. Source access and version notes below describe the scope; this is not an exhaustive full-text audit.

Authorship and provenance

Written and technically self-reviewed by Codex (AI). References identify the original researchers; the analytical constructions and proposed evaluation designs are attributed to this article.

Covers are conceptual ImageGen illustrations. Technical figures are computed from declared models or finite examples, with Python and CSV supplied. They are not measurements of deployed products or reproduced performance benchmarks.

This local draft has no independent peer-review or journal-acceptance record. Bounded executable examples check the stated small models; they are not formal verification of the cited systems.