Private Lossless Multiple Release

Boel Nelson; Joel Daniel Andersson; Lukas Retschmeier; Rasmus Pagh

REVIEW 2 major objections 5 minor 15 references

Private Lossless Multiple Release

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that additive-noise differentially private mechanisms whose noise family satisfies a convolution preorder can issue releases at many privacy levels, in any order, with no extra privacy cost beyond the least private release.

desk verdict Concrete Gaussian/Laplace/Poisson lossless multiple release is new and mostly sound, but the meta-theorem's proof skips a load-bearing marginal-consistency step. read the letter →

arxiv 2505.22449 v1 pith:LT5MXQJ5 submitted 2025-05-28 cs.CR cs.DS

Joel Daniel Andersson , Lukas Retschmeier , Boel Nelson , Rasmus Pagh This is my paper

classification cs.CRcs.DS

keywords differentialprivacylosslessmultiplereleasegradualconvolutionpreorderGaussianmechanismLaplacePoissonsparsehistograms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Organizations and data markets often need to hand out the same statistic at different accuracy levels to different parties, but issuing independent differentially private releases at each level makes the combined privacy loss add up. This paper introduces 'lossless multiple release': correlated releases with different privacy parameters such that any colluding subset of recipients learns no more than the most privileged member, and each release is exactly as accurate as a single release at its own level. The central result is that any mechanism adding independent noise from a family satisfying a convolution preorder — a simple ordering condition the authors verify for Gaussian, Laplace, Poisson, and exponential noise — supports this, with releases generated online in arbitrary order. For Gaussian noise the paper gives an elementary derivation that avoids Brownian motion machinery, and for sparse histograms it gives a gradual-release algorithm whose running time does not depend on the domain dimension. If correct, the paper turns the privacy budget from a consumable resource that shrinks with each release into an access credential set by the least private release.

What carries the argument

The central object is the convolution preorder of Definition 1.1: a family of noise distributions $D(\rho)$ satisfies it when for $\rho_1<\rho_2$ there exists a bridging distribution $C(\rho_2,\rho_1)$ with $D(\rho_1)=D(\rho_2)*C(\rho_2,\rho_1)$. This property makes it possible to write the $\rho_k$-private release as $Y_{\rho_k} = f(x) + Z_{\rho_m} + \sum_{j=k}^{m-1} W_{\rho_{j+1},\rho_j}$, where $Z$ comes from the least private distribution and each $W$ from the corresponding bridging distribution, so every release is a randomized post-processing of the least private release. The proof machinery then reduces the adaptive sampling of any new release to sampling one bridging variable $W_1$ conditioned on the sum $W_1+W_2$ of two bridging variables equaling the difference of two adjacent released values; the paper shows this conditional task is a Binomial for Poisson noise and a three-component mixture for Laplace noise. For Gaussians, the same conditioning is implemented as an inverse-variance-weighted combination of the two neighbouring releases plus fresh Gaussian noise, requiring only the two nearest released pairs to be kept in memory.

What would settle it

Take any candidate noise family $D(\rho)$ (e.g., the discrete Gaussian used in practical DP) and check whether for all $\rho_1<\rho_2$ the ratio of characteristic functions $\varphi_{D(\rho_1)}(t)/\varphi_{D(\rho_2)}(t)$ is a valid characteristic function. If for some pair the ratio fails to correspond to a probability distribution, then that family has no bridging distribution and the meta theorem's construction cannot be applied to it; finding such a pair in a family that is otherwise a valid DP noise would mark exactly where lossless multiple release fails.

Watch

Extended reading notes

Core claim

Lossless multiple release (Definition 3.4) requires two things: each release $M(x,\rho)$ is identically distributed to a single release at parameter $\rho$, and for any finite set $S$ of privacy parameters processed in arbitrary order, conditioned on the least private release in $S$, the joint distribution of all releases in $S$ is uniquely determined. The meta theorem (Theorem 4.4) states that any mechanism of the form $M_\rho = H \circ A_{f,\rho}$, where $A_{f,\rho}$ adds i.i.d. noise from a family $D(\rho)$ satisfying the convolution preorder (Definition 1.1) and $H$ is invertible post-processing, can be implemented with lossless multiple release. The construction represents every release as the least private release plus independent 'bridging' noise drawn from the distributions $C(\rho_{j+1},\rho_j)$, and samples a new release conditioned on its two nearest existing releases; for a bounded parameter range, only those two neighbors need to be stored. For Gaussian noise, Algorithm 1 gives an explicit inverse-variance combination of neighboring releases plus fresh Gaussian noise, and the paper proves the resulting process matches the covariance structure of the gradual Gaussian sequence. For Laplace and Poisson noise, the conditional sampling steps reduce to a three-component mixture and a Binomial distribution respectively. Non-invertible post-processing such as thresholding still yields 'weakly lossless' multiple release, which the paper applies to sparse Gaussian histograms, and a simulation technique reduces the histogram algorithm's running time to depend on the number of released counts rather than the domain size.

Load-bearing premise

The construction rests on the convolution preorder: for every pair of privacy levels $\rho_1<\rho_2$, the more private distribution must factor as the less private distribution convolved with some fixed bridging distribution; the paper verifies this for Gaussian, Laplace, Poisson, and exponential noise, but not for arbitrary mechanisms.

Editorial extensions

If this is right

Any deployment that issues releases at multiple trust levels — clearance hierarchies, data markets, federated servers with different trust — can hand each party the most accurate release they are entitled to while guaranteeing that coalitions learn no more than the highest-privilege member, with no privacy-budget overhead.
Factorization mechanisms for linear queries $A=LR$, including the matrix mechanism, support lossless multiple release when $L$ is left-invertible; otherwise they support weakly lossless release, which still guarantees $\max(S)$-privacy under $\varepsilon$-DP and $\rho$-zCDP.
Sparse Gaussian histograms can be released gradually with the same output distribution as a dense implementation, in per-round time that depends on sparsity and the number of counts that ever cross the threshold, not on the domain dimension.
The Poisson mechanism, whose noise is non-negative and integer valued, inherits lossless multiple release with a simple Binomial sampling step, giving a discrete-noise route to the same guarantees.
The exponential distribution also satisfies the convolution preorder, so any independent additive noise mechanism using exponential noise is covered by the meta theorem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial: the framework suggests a reinterpretation of the privacy budget as an access-control credential rather than a consumable resource: once the least private release exists, all more private levels are derivatives of it, which could simplify policy design in multi-level security hierarchies like the clearance-level models the paper cites.
Editorial: a natural next test is the discrete Gaussian mechanism; since Poisson noise satisfies the convolution preorder and converges to Gaussian, a discretized version of the same conditioning may yield lossless multiple release for discrete Gaussian noise, which the paper lists as an open question.
Editorial: other convolution-closed exponential families, such as binomial or negative-binomial noise, should admit the same construction, with the conditioning step expressible as a known discrete distribution; verifying this would broaden the class of practical mechanisms covered by the meta theorem.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know: (1) the Gaussian, Laplace, and Poisson multiple-release constructions are genuinely new and, for the Gaussian case, much simpler than the Brownian-motion treatment. (2) The meta-theorem (Theorem 4.4) is not actually proved as stated: Lemma 4.2's induction skips the marginal-consistency step. If you insert a new privacy parameter between two existing releases, the old releases must have the same joint distribution under the new Eq. (1) representation as under the old one. That requires splitting the bridge distribution C(ρ_{l+1},ρ_l) into C(ρ_{l+1},ρ)*C(ρ,ρ_l) and conditioning on the sum. The paper never states or proves this. It's not a counterexample—for Gaussian, Laplace, Poisson, and exponential noise the bridges do compose, so the concrete results survive—but the meta-theorem overclaims without an extra consistency condition on the family C.

The good stuff: Lemma 3.3 gives a self-contained Gaussian arbitrary-order procedure with a complete proof in Appendix B. The Laplace and Poisson conditional-sampling lemmas (F.5 and E.4) are explicit and check out. The applications to factorization mechanisms and sparse histograms are natural, and the dimension-independent histogram algorithm is a real improvement if Lemma 5.6's proof sketch can be made rigorous.

Minor things: Lemma 3.2 has the base variance typo (1/ρ1 should be 1/(2ρ1)). The histogram efficiency section leans on a proof sketch in Appendix C; the main claim of identical distribution needs a formal proof. The empirical evaluation is basic but fine.

Who this is for: anyone working on composition, gradual release, or multi-level privacy. It deserves a serious referee, but the referee should ask for a patch to Lemma 4.2—either add a consistency condition to Definition 1.1 or prove the bridge-composition property for each concrete family. With that, it would be a solid paper.

Referee Report

2 major / 5 minor

Summary. The paper studies coordinated multiple releases of a differentially private mechanism at different privacy parameters, with the goal that any subset of releases has the same privacy guarantee as the least private release in the subset and each release matches the single-release distribution. The authors introduce a formal notion of lossless multiple release, prove a meta-theorem (Theorem 4.4) for independent additive noise mechanisms whose noise family satisfies a convolution preorder, and give concrete instantiations for Gaussian, Laplace, Poisson, and exponential noise. They also apply the framework to factorization mechanisms and to sparse histograms, including a dimension-independent gradual-release algorithm. The Gaussian construction is proved in detail in Section 3 and Appendix B; the Laplace and Poisson conditional samplers are worked out in Appendices F and E.

Significance. If the main theorem is sound, the paper provides a useful generalization of gradual release to arbitrary-order, multi-party release, with a clean conceptual framework and explicit algorithms for several standard noise families. The concrete Gaussian, Laplace, and Poisson constructions are valuable and largely self-contained, and the efficient sparse-histogram algorithm addresses a real computational bottleneck. The claim that lossless multiple release holds for every independent additive noise mechanism satisfying Definition 1.1 is, however, stronger than what the written proof establishes; the meta-theorem needs an additional consistency condition or a more careful proof. Because the abstract and title advertise this broad generality, the gap is load-bearing despite the correctness of the concrete constructions.

major comments (2)

[Lemma 4.2 and Appendix A] The adaptive induction in Lemma 4.2 is not justified as written. When a new privacy parameter rho_i is inserted inside an existing interval (rho_l, rho_r), the proof says to conditionally sample it from the joint distribution over S_{n+1} conditioned on the value of each release made in the previous round. This is valid only if the already released values are distributed as the marginal of the Eq. (1) representation for S_{n+1}. For an interior insertion, that marginal-consistency step requires the bridge distributions to satisfy C(rho_r, rho_l) = C(rho_r, rho_i) * C(rho_i, rho_l). Definition 1.1 guarantees only the existence of each bridge separately; it does not imply this convolution identity. The proof never states or proves the identity, and the same assumption is silently made in Algorithm 4, line 8 and Algorithm 5, line 2; the proof of Lemma A.1 repeats the same inductive step. Consequently, Theorem 4.4 is not established for the full class of mechanisms satisfying Definition 1.1. The concrete families do satisfy the identity (Gaussian and Poisson by additivity of variances/rates, Laplace and exponential by telescoping of the characteristic functions in Claims F.3 and F.7), but the paper should either add this splitting condition to Definition 1.1 or prove it for the specific bridge families used in the meta-theorem.
[Algorithm 3, Section 5.2] The update rule on line 3 of Algorithm 3 is inconsistent with the Gaussian gradual-release recursion proved in Lemma 3.1. To combine a saved noise Z' with variance Delta^2/(2 rho') and fresh noise of variance Delta^2/(2(rho-rho')), the fresh noise must be weighted by (rho-rho')/rho, not by 1/rho. As printed, the variance of Z is rho'/(2 rho^2) plus Var(tilde Z)/rho^2, which cannot equal Delta^2/(2 rho) with the natural choice of tilde Z. This affects the correctness of Lemma 5.4 for the algorithm as displayed. The authors should correct the coefficient and state the variance of tilde Z unambiguously, or explain an alternative scaling that still yields the claimed distribution.

minor comments (5)

[Lemma 3.2 and Appendix B] Lemma 3.2 states Y_{rho_1} ~ N(beta, 1/rho_1), but the intended and later-used variance is 1/(2 rho_1); the same factor error appears in the Appendix B base case, where Y_{rho_infty} is written with variance 1/rho_infty and the fresh-noise variance without the leading 1/2. These are typographical but should be corrected because they make the displayed formulas inconsistent with the Gaussian mechanism's zCDP guarantee.
[Algorithm 2] Line 6 of Algorithm 2 returns Z, but the algorithm should return the factorization release Y_rho; the surrounding text and Lemma 5.2 indicate that Y_rho is the intended output.
[Algorithm 3, line 2] The variance expression for tilde Z is printed ambiguously as "1/2 Delta_2^2/(2(rho-rho'))", which mixes a leading 1/2 with a denominator 2. Please rewrite the variance as a single fraction so that the factor of 2 is clear, and ensure it is consistent with the corrected coefficient in line 3.
[Section 5.2 and Appendix C] The proof sketch of Lemma 5.6 is quite terse; in particular, the conditional sampling in lines 13-24 of Algorithm 6 and the claim that the resulting distribution matches the target would benefit from a fuller derivation, because the notation tilde Z^{(k)} is reused for both independent draws and conditional draws.
[General presentation] The paper alternates between the spellings "lossless" and "lossless" in the title and body; please standardize the spelling.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the meta-theorem is a constructive consequence of the stated convolution preorder and concrete bridge distributions; the main caveat is an unproved consistency step in Lemma 4.2's arbitrary-order induction, which is a proof-completeness gap rather than a circular definition.

full rationale

The paper's central result (Theorem 4.4) does not derive its conclusion from itself. It starts from an explicitly stated hypothesis—Definition 1.1's convolution preorder—and constructs releases by Eq. (1): every release is a common most-private (largest-rho) release plus a sum of independent bridge noises. The marginal of Y_{rho_k} equals D(rho_k) by iterating the preorder, and conditioning on the least-private release leaves only the independent bridges, giving property 2 of Definition 3.4. This is a direct, explicit construction, not a renaming or a fit. The concrete preorder checks for Gaussian, Laplace, Poisson, and exponential noise are proved from first principles (Appendices E and F), not imported from a self-citation. Prior work (Koufogiannis et al., Xiao et al., Li et al.) is cited as background and generalization, not as the load-bearing justification; none of the present authors' own papers are cited for the main claim. The only substantive concern is in Lemma 4.2's adaptive-order induction and the corresponding Algorithm 4/5. The proof states 'we can conditionally sample it from the joint distribution over (Y_{rho_k})_{k in [n+1]}, conditioned on the value of each release made in the previous round,' but it never proves that the previously produced S_n-joint is the marginal of the S_{n+1}-joint. For an interior insertion this requires the bridge C(rho_r,rho_l) to split into independent C(rho_r,rho) and C(rho,rho_l) components (or at least that the old bridge can be replaced by the sum of the two sub-bridges). This is a missing proof step—a correctness risk, not a circular step. It does not reduce the theorem to its assumptions; it exposes a possibly hidden assumption in the construction. Since there are no fitted parameters, no self-referential predictions, and no load-bearing self-citations, the circularity score is minimal.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard zCDP composition and post-processing, the Gaussian mechanism guarantee, and the convolution preorder property verified for specific noise families. No free parameters are fitted to data; thresholds and privacy budgets are user inputs. No new physical entities are postulated.

assumptions (5)

standard math zCDP composition: releasing a rho1-private and a rho2-private mechanism together yields (rho1+rho2)-zCDP.
Used in Section 1.2 and Appendix D to argue that independent releases incur additive budget, motivating lossless release.
standard math Post-processing: any function of a rho-zCDP output is rho-zCDP.
Used in Corollary 3.5 and Lemma 4.3 to argue that correlated releases are no more revealing than the least private release in a subset.
standard math Gaussian mechanism: f(x)+N(0, Delta^2/(2*rho)) satisfies rho-zCDP.
Lemma D.4 in Appendix D, used throughout as the base privacy guarantee for the Gaussian noise construction.
domain assumption The specific noise families satisfy the convolution preorder of Definition 1.1.
Definition 1.1 is assumed in the meta-theorem. The paper proves the property constructively for Gaussian, Laplace, Poisson, and exponential noise in Sections 3, 4.1, and Appendices E, F.
standard math Conditional sampling from the joint release distribution is well-defined and measure-theoretically valid.
Appendix A assumes one can sample from the conditional distribution in Algorithm 4. The authors note computational intractability is possible, but existence is sufficient for the privacy guarantee.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Private Lossless Multiple Release." pith.science (2026). https://pith.science/paper/LT5MXQJ5

@misc{pith2026250522449,
  author       = {Pith},
  title        = {Pith review of: Private Lossless Multiple Release},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LT5MXQJ5}},
  note         = {Machine review of arXiv:2505.22449}
}

abstract

Koufogiannis et al. (2016) showed a $\textit{gradual release}$ result for Laplace noise-based differentially private mechanisms: given an $\varepsilon$-DP release, a new release with privacy parameter $\varepsilon' > \varepsilon$ can be computed such that the combined privacy loss of both releases is at most $\varepsilon'$ and the distribution of the latter is the same as a single release with parameter $\varepsilon'$. They also showed gradual release techniques for Gaussian noise, later also explored by Whitehouse et al. (2022). In this paper, we consider a more general $\textit{multiple release}$ setting in which analysts hold private releases with different privacy parameters corresponding to different access/trust levels. These releases are determined one by one, with privacy parameters in arbitrary order. A multiple release is $\textit{lossless}$ if having access to a subset $S$ of the releases has the same privacy guarantee as the least private release in $S$, and each release has the same distribution as a single release with the same privacy parameter. Our main result is that lossless multiple release is possible for a large class of additive noise mechanisms. For the Gaussian mechanism we give a simple method for lossless multiple release with a short, self-contained analysis that does not require knowledge of the mathematics of Brownian motion. We also present lossless multiple release for the Laplace and Poisson mechanisms. Finally, we consider how to efficiently do gradual release of sparse histograms, and present a mechanism with running time independent of the number of dimensions.

Figures

Figures reproduced from arXiv: 2505.22449 by the authors.

**Figure 1.** The idea behind lossless multiple release. For concreteness we consider additive noise mechanism and zero-concentrated differential privacy. Each Yρi denotes a noisy estimate, and to release a new estimate with ρ > 0, we can combine the adjacent estimates for ρk and ρk+1 together with some fresh noise to obtain a new release Yρ that is exactly ρ-zCDP. Note that these estimates do not need to be strictly increasing … view at source ↗

**Figure 2.** Accuracy comparison of multiple uncorrelated releases compared to lossless multiple release. Budgets are spaced evenly on a logarithmic scale between ρ = 0.001 and ρ = 5 on the x-axis. Creating independent releases with a denser set of privacy parameters comes at the cost of increased variance. In the lossless setting we get the best possible variance with no bound on the number of releases. The benefit of the effic… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 10 canonical work pages

[1]

We will need the following lemma that determines the sampling step of private lossless multiple release for the Poisson mechanism: Lemma E.4

Then for δ <1/100, the d-dimensional Poisson mechanism with parameter λ >23 log(10d/δ) is (ε, δ)-differentially private for ε = q 2 log 1.25 δ √ λ + 2 log 20d δ log 10 δ λ . We will need the following lemma that determines the sampling step of private lossless multiple release for the Poisson mechanism: Lemma E.4. Let X1 ∼ Poi(λ1) and X2 ∼ Poi(λ2) be inde...

work page 2016
[7]

doi: 10.29012/jpc.v7i2.649

ISSN 2575-8527. doi: 10.29012/jpc.v7i2.649. Number:

doi:10.29012/jpc.v7i2.649
[9]

Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, Z

doi: 10.1109/ TKDE.2011.124. Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, Z. S. Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. In Advances in Neural Information Processing Systems, volume 30, pp. 2566– 2576,

work page 2011
[10]

Randomized Response with Gradual Release of Privacy Budget

48550/arXiv.2401.13952. Rogers, R. M., Vadhan, S. P., Roth, A., and Ullman, J. R. Privacy Odometers and Filters: Pay-as-you-Go Compo- sition. In Advances in Neural Information Processing Systems, volume 29, pp. 1921–1929,

work page Pith review arXiv 1921
[13]

doi: 10.14778/1687627.1687719. 10 Private Lossless Multiple Release Algorithm 4 GenericMultipleRelease Parameters: Noise distribution family D(ρ) satisfying a convolution preorder, bridging noise distribution C(ρ, ρ′) where D(ρ′) ∗ C(ρ′, ρ) = D(ρ) for 0 < ρ < ρ′. Inputs: Sensitive value f (x), new privacy parameter ρk, set of past releases M = {(ρi, Yρi )...

arXiv
[14]

It follows that non-zero entries contribute km samples, and zero counts exceeding the threshold contribute cm samples

If a non-zero count is selected by the binomial sampling in the kth round, the for-loop starting on line 17 will result in sampling k noise terms, after which for future rounds it will get treated as a non-zero count. It follows that non-zero entries contribute km samples, and zero counts exceeding the threshold contribute cm samples. D. Definitions We be...

work page 2016
[16]

We first assumek ̸= 0 and analyze three possible cases how X1 + X2 is built up: Either both of them are drawn from the (continuous) Laplace distribution or exactly one

We can now show how the sampling procedure in the claim is justified. We first assumek ̸= 0 and analyze three possible cases how X1 + X2 is built up: Either both of them are drawn from the (continuous) Laplace distribution or exactly one. (The case where both are from their respective discrete parts can only happen if k = 0, analyzed above.) Case 1: X1 = ...

work page 2021
[2006]

doi: 10.1007/11681878

ISBN 978-3-540-32732-5. doi: 10.1007/11681878

doi:10.1007/11681878

Show all 15 references

[2009]

doi: 10.1145/1526709. 1526733. Kotz, S., Kozubowski, T. J., and Podg´orski, K. The Laplace Distribution and Generalizations . Birkh ¨auser Boston. ISBN 978-1-4612-6646-4 978-1-4612-0173-1. doi:

doi
[2012]

ISBN 9781450307918

ACM. ISBN 9781450307918. doi: 10.1145/2274576.2274608. Ding, Z., Kifer, D., Saghaian N. E., S. M., Steinke, T., Wang, Y ., Xiao, Y ., and Zhang, D. The Permute-and- Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise. CoRR, abs/2105.07260,
[2014]

Google Anonymization Team

doi: 10.1561/0400000042. Google Anonymization Team. Delta for Thresholding. https://github.com/ google/differential-privacy/blob/ 9 Private Lossless Multiple Release a7cc26ad91f74756fbe39bab44af6d655b37cc61/ common_docs/Delta_For_Thresholding. pdf,

doi
[2015]

Li, Y ., Chen, M., Li, Q., and Zhang, W

doi: 10.1007/s00778-015-0398-x. Li, Y ., Chen, M., Li, Q., and Zhang, W. Enabling Multilevel Trust in Privacy Preserving Data Mining. IEEE Trans. Knowl. Data Eng., 24(9):1598–1612,

doi
[2016]

ISBN 978-3-662-53641-4

Springer. ISBN 978-3-662-53641-4. doi: 10.1007/978-3-662-53641- 4

doi
[2018]

and Wang, Y

Balle, B. and Wang, Y . Improving the Gaussian Mecha- nism for Differential Privacy: Analytical Calibration and Optimal Denoising. In Proceedings of the 35th Inter- national Conference on Machine Learning, ICML 2018, Stockholm, Sweden, July 10-15, 2018, volume 80 of Pro- ceedi...

2018
[2024]

doi: 10.29012/jpc.823

ISSN 2575-8527. doi: 10.29012/jpc.823. Xiao, X., Tao, Y ., and Chen, M. Optimal Random Perturba- tion at Multiple Privacy Levels. Proc. VLDB Endow., 2 (1):814–825,

doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

We will need the following lemma that determines the sampling step of private lossless multiple release for the Poisson mechanism: Lemma E.4

Then for δ <1/100, the d-dimensional Poisson mechanism with parameter λ >23 log(10d/δ) is (ε, δ)-differentially private for ε = q 2 log 1.25 δ √ λ + 2 log 20d δ log 10 δ λ . We will need the following lemma that determines the sampling step of private lossless multiple release for the Poisson mechanism: Lemma E.4. Let X1 ∼ Poi(λ1) and X2 ∼ Poi(λ2) be inde...

work page 2016

[2] [7]

doi: 10.29012/jpc.v7i2.649

ISSN 2575-8527. doi: 10.29012/jpc.v7i2.649. Number:

doi:10.29012/jpc.v7i2.649

[3] [9]

Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, Z

doi: 10.1109/ TKDE.2011.124. Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, Z. S. Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. In Advances in Neural Information Processing Systems, volume 30, pp. 2566– 2576,

work page 2011

[4] [10]

Randomized Response with Gradual Release of Privacy Budget

48550/arXiv.2401.13952. Rogers, R. M., Vadhan, S. P., Roth, A., and Ullman, J. R. Privacy Odometers and Filters: Pay-as-you-Go Compo- sition. In Advances in Neural Information Processing Systems, volume 29, pp. 1921–1929,

work page Pith review arXiv 1921

[5] [13]

doi: 10.14778/1687627.1687719. 10 Private Lossless Multiple Release Algorithm 4 GenericMultipleRelease Parameters: Noise distribution family D(ρ) satisfying a convolution preorder, bridging noise distribution C(ρ, ρ′) where D(ρ′) ∗ C(ρ′, ρ) = D(ρ) for 0 < ρ < ρ′. Inputs: Sensitive value f (x), new privacy parameter ρk, set of past releases M = {(ρi, Yρi )...

arXiv

[6] [14]

It follows that non-zero entries contribute km samples, and zero counts exceeding the threshold contribute cm samples

If a non-zero count is selected by the binomial sampling in the kth round, the for-loop starting on line 17 will result in sampling k noise terms, after which for future rounds it will get treated as a non-zero count. It follows that non-zero entries contribute km samples, and zero counts exceeding the threshold contribute cm samples. D. Definitions We be...

work page 2016

[7] [16]

We first assumek ̸= 0 and analyze three possible cases how X1 + X2 is built up: Either both of them are drawn from the (continuous) Laplace distribution or exactly one

We can now show how the sampling procedure in the claim is justified. We first assumek ̸= 0 and analyze three possible cases how X1 + X2 is built up: Either both of them are drawn from the (continuous) Laplace distribution or exactly one. (The case where both are from their respective discrete parts can only happen if k = 0, analyzed above.) Case 1: X1 = ...

work page 2021

[8] [2006]

doi: 10.1007/11681878

ISBN 978-3-540-32732-5. doi: 10.1007/11681878

doi:10.1007/11681878