Private Lossless Multiple Release
Authors: Joel Daniel Andersson
Lukas Retschmeier
Boel Nelson
Rasmus Pagh
Venue: ICML 2025 poster (2025)
Keywords: algorithms
differential privacy
Primary area: theory
TL;DR: We study how to coordinate private releases for multiple privacy parameter values with no loss in privacy or utility compared to single releases

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.

Private Lossless Multiple Release
Joel Daniel Andersson 12
Lukas Retschmeier
12 Boel Nelson 2
Rasmus Pagh
Abstract
accuracy trade-off is the key object of study in the area. Of specific interest is the privacy budget that determines how much information the output of a differentially private algo- rithm may reveal about its inputs a smaller budget means more private but less accurate results.
Koufogiannis et al. (2016) showed gradual release re- sult for Laplace noise-based differentially private mech- anisms: given an s-DP release, a new release with pri- vacy parameter e' > & can be computed such that the combined privacy loss of both releases is at most e' and the distribution of the latter is the same as a single release with parameter E'. They also showed gradual re- lease techniques for Gaussian noise, later also explored by Whitehouse et al. (2022). In this paper, we consider a more general multiple release setting which analysts hold private releases with different privacy parameters corresponding different access/trust levels. These releases are determined one by one, with privacy param- eters in arbitrary order. A multiple release is 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 large class of additive noise mechanisms. For the Gaussian mech- anism we give simple method for lossless multiple release with a short, self-contained analysis that does not require knowledge of the mathematics of Brown- ian motion. We also present lossless multiple release for the Laplace and Poisson mechanisms. Finally, we consider how efficiently do gradual release of sparse histograms, and present mechanism with running time independent of the number of dimensions.
Motivation. In deployments of differential privacy, it may be hard to determine the appropriate privacy budget to grant analyst since it depends on trust and accuracy assump- tions that may change over time. A system may also have different security clearance levels-a data analyst might have a higher clearance level than a developer, but both might require access to some statistics. Similarly, a com- pany that wants to release, for example, user statistics could make an accurate release for their own data analysts, a less accurate release for external consultants, and include an even less accurate release in report for shareholders or other external actors. A different example setting is users that want to sell their data on data markets: users could let the accuracy of the release depend on how much they are paid, and use different budgets for different releases.
Another usage scenario, relevant in distributed federated settings, is local differential privacy where the data owner could be sharing differentially private function of their data with multiple servers, and the set of servers might change over time. Here the privacy budget might depend on the server: for example, a patient may trust their local hospital more than their national hospitals, but might not trust the hospitals not to collude by sharing data among themselves.
Multiple releases. These scenarios motivate creating multi- ple releases with different privacy budgets aimed at different analysts. However, these releases should be coordinated such that group of analysts who combine their information do not gain more knowledge about the input than the most knowledgeable member of the group. This kind of collusion resilience was first studied by Xiao al. (2009) with a non- DP privacy objective- refer to their work for additional motivation.
1. Introduction
Differential privacy (Dwork et al., 2006) is statistical no- tion that provides provable privacy guarantees. Differen- tially private (DP) algorithms typically introduce inaccuracy through noise to achieve privacy, and the resulting privacy-
Basic Algorithms Research Copenhagen (BARC), Den- mark UUniversity of Copenhagen. Denmark. Correspondence to: Joel Daniel Andersson xjda@di.ku.aa ku..ku.kk>, Lukas Retschmeier <lure @ du. Boel Nelson <bn <bn@dii <bn@di.ku.kk> Rasmus Pagh <pagh @ ku.
A related aspect is that we may want to provide an analyst with a less private, more accurate release after the trust we place in them increases. In this case, we want the accu- racy of the latest release to match the accuracy that can be obtained, given the combined privacy budget of both releases. That is, no additional cost should be incurred for
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Private Lossless Multiple Release
making two releases rather than one. For example, an ex- ternal consultant that later gets employed directly by the company should be able to get access to the more accurate release without constituting a privacy violation or requiring an increased privacy budget to reach the same accuracy.
most private
least private
Po
P1
P2
Pk
P
Pk+1
Pro
4
1
t P
po
p2
Xp
Y
Youss
Figure 1. The idea behind lossless multiple release. For concrete- ness we consider additive noise mechanism and zero-concentrated differential privacy. Each yp, denotes noisy estimate, and release new estimate with p >> O, we can combine the adjacent estimates for pk and ph+1 together with some fresh noise to obtain new release Y, that is exactly p-zCDP. Note that these estimates "e-doubling" by Ligett et al. (2017), and provide each an-
Baseline. It is possible to create multiple releases for any differentially private mechanism if we are willing to in- crease the privacy budget by a constant factor. In particular, we can create a sequence of independent releases with ge- ometrically increasing privacy parameters, referred to as
do not need to be strictly increasing (or decreasing) but can he alyst with the most accurate release they are entitled to. Using composition results, the combined privacy budget for the information given to a set of analysts a constant factor from the highest budget of single analyst in the group. In this paper, we study how to make multiple releases in lossless way without accuracy or privacy penalty.
released in any order. Furthermore, releasing any subset of these estimates is exactly max(S))2CDP, where S is the set of privacy parameters.
releasing a sensitive dataset where each element is kept with probability p. and otherwise sampled uniformly from the universe. Li, Chen, Li, and Zhang (2012) considered pri- vatizing data by additive Gaussian noise of scale a. Both works dealt with arbitrary sequences of parameters (prob- abilities p noise scalings σ), and demonstrated how to correlate releases to guarantee that (1) each release matches the single-release case and, (2) limiting the sensitive infor- mation derived from combining releases. Our method for adaptively producing Gaussian releases deviates from (Li et al., 2012), in that ours does not need to maintain any co- variance matrix for past releases. This makes our approach more time- and space-efficient.
1.1. Related Work
Koufogiannis, Han, and Pappas (2016) introduced the con- cept of (lossless) gradual release, which makes it possible to increase the privacy budget with no loss in accuracy. They also considered privacy tightening for the Laplace mecha- nism, where successive releases are increasingly private. In the journal version of the paper, they also introduce gradual release for the Gaussian mechanism under approximate DP which is based on the machinery of Brownian motion.
This technique was later applied in noise reduction frame- work by Ligett, Neel, Roth, Waggoner, and Wu (2017) with the goal of producing mechanisms with ex-post privacy, i.e., where the privacy budget is set based on what is required to achieve desired accuracy level. Follow-up work by White- house, Ramdas, Wu, and Rogers (2022) gave results for noise reduction under approximate DP using Brownian mo- tion. These works were motivated by work privacy filters and odometers (Rogers et al., 2016), keeping track of pri- vacy budgets over time, rather than multiple release settings. More recently. Pan (2024) demonstrated lossless gradual release for randomized response.
Finally, we mention the classic work of Equitz and Cover (1991) who studied successive refinement of information where a source is encoded once and then refined in later stages without decreasing the rate compared to a one-shot optimal code. They showed that this is possible precisely when the sequence of reconstructions can be written Markov chain. While their work did not focus on privacy, successive refinement is conceptually related to lossless gradual release. Indeed, parts of the mathematical machin- ery was independently re-discovered by subsequent work on lossless gradual release.
Girgis et al. (2020) studied privacy-utilityy randooess trade- offs for multi-analyst setting under local differential pri- vacy. Here each user has sample X; ~ D and makes a single public release of X₁. Each analyst then utilizes the public release (together with shared randomness among the users) to estimate D at a more accurate level than what the public release alone would allow. Later Zhang and He (2023) also used lossless gradual release techniques for the Gaussian mechanism in designing a database system sup- porting analysts with different privilege levels.
1.2. Basic Technique
We illustrate our framework in the setting of addi- tive Gaussian noise and p-zero-concentrated differen- tial privacy (p-zCDP)'. We want to release a private estimate of real-valued query f + R with l-- sensitivity A2 Now consider the simple case where one wants to privately release an estimate with two privacy levels p < p'. Then releasing Y, = f(x) + N(O, 2 together with Yp- = f(x) + N(O, - is p'DzCDP by compo-
using the Gaussian mechanism.
Similar research questions have been investigated outside of the DP literature. Xiao, Tao, and Chen (2009) studied
'see definitions Appendix D
2

---

Private Lossless Multiple Release
sition. Now observe that we can combine these estimates to produce better estimate using inverse variance weighting: Y= p+( Yp p' p+(d'-p) Yp yp yields exactly the same utility as a single release under p' p'ZZDPP. That is, instead of using a privacy budget of p p' for independently releasing both estimates, the overall budget spent is just the maximum of both, which is p'.
instantiations of Gaussian sparse histograms (Section 5.2) and factorization mechanisms (Section 5.1).
2. Threat Model and Goals
Our setting is a multi-user system with a set of ana- lysts/users S, all able to query the same dataset using a differentially private mechanism. User s has their own secu- rity clearance level with corresponding privacy budget Pa- This setting allows for multi-level security where each user belongs to security clearance level, like in the classic Bell- LaPadula model (Bell & La Padula, 1976), where users with high clearance levels have higher values of p. A common example of such clearance levels is using increasing levels with labels such as public, restricted, confidential, and top secret. The user with the highest clearance in the system has a privacy budget of max which we denote Pmax.
To do multiple lossless releases for more general additive noise mechanisms, it turns out that one can always combine existing releases with fresh noise illustrated in Figure 1. In fact, to make any new release with privacy parameter p. suffices to have saved the two "adjacent" releases whose privacy parameters are closest to p. Our approach applies more generally to a class of (independent) additive noise mechanisms that support gradual release, but the releases can be made in any order, and we do not require the set of releases to be known in advance.
.ES
We consider an adversary who gains partial knowledge, that is, adversary that sees some of the releases. Our goal is to design a differentially private mechanism such that an adversary with access to releases from some users S' C S, can learn at most what they could have learned from release with privacy parameter max(p=)) This means .'ES'
Our contributions. We introduce framework for lossless multiple release, generalizing past work on gradual release. In addition to allowing for making multiple private releases and having the privacy loss only scale with the least pri- vate release, we impose no specific ordering on the privacy parameters used. Furthermore, we formalize general theo- rem (Section 4.2) showing that lossless multiple release is possible for large class of mechanisms based on adding i..dd noise to each coordinate whose distribution satisfies a convolution preorder, as defined next.
that even by compromising or colluding with more users, the adversary's 's knowledge may not increase. In case an adversary observes all releases (e.g.. by compromising all users), the privacy loss would be bounded by Pmax.
Definition 1.1 (Convolution preorder). A family of real- valued distributions D(p) parameterized by p E R4 is said to satisfy convolution preorder, if given D(p)) and ((2)) for P1 P2, there exists a distribution C(p2. P1) such that ((p)) C(p2, P1) = D(p1).
However, our goal is to design mechanism where the re- leases are lossless in the sense that the noise distribution from multiple releases with a combined budget Pmax would be indistinguishable from one single release with the pri- vacy budget Pamxx In other words, the privacy loss should be determined by Pmax. while independent releases would usually have privacy parameter Σ Ps due to composition.
This relation is a natural way of stating that the distributions become more noisy as the parameter gets smaller. We are unaware of any existing term in the literature but the definition is closely related to convolution order (Shaked & Shanthikumar, 2007). Examples of noise distributions satisfying Definition 1.1 include the Laplace, Poisson, and the Gaussian mechanisms, parameterized by decreasing function of their variance.
.ES
3. Gaussian Lossless Multiple Release
Extending the work in (Koufogiannis et al., 2016; Li et al., 2012), we demonstrate next that in the case of the Gaussian mechanism, providing lossless multiple release is clean and follows immediately from simple properties of Gaussians. Throughout the paper, we use the symbol Y to be random variable that depends on the private dataset and Z to be one that does not.
Theorem 1.2 (Meta theorem, informal). Let x Rdd be a mechanism that adds indepen- dent, identically distributed noise to coordinates of a function f -> >Rd If the noise distribution of As.e satisfies convolution preorder, then there exists an algorithm enabling lossless multiple release. Also, any invertible post-processing of As.p preserves this property.
We first consider the gradual release setting where an in- creasingly accurate estimate is released, and the overall privacy loss is determined solely by the latest, least private release. In Lemma 3.3, we drop this restriction, allowing releases in any order while still guaranteeing that the overall privacy guarantee is the maximum value provided. For simplicity, we consider the one-dimensional case, where we
For the Gaussian mechanism in particular, we show how to get lossless multiple release by only using basic properties of Gaussians, and we show similar results for the Laplace and Poisson mechanisms from first principles. We give concrete
3

---

Private Lossless Multiple Release
want release some query / X + R. The d-dimensional setting is handled by sampling each coordinate indepen- dently.
Lemma 3.3. For Poo E E2 (possibly Pro -0) and R
let M {{0, o0), (pzo: ypw)) where pp N(3, 2p= Consider a finite subset S C (oo) and the following process that runs for [S] iterations:
Getting started. Foreshadowing the usage of p-zCDP, we initially use 1/p2p) for denoting the variance of a Gaussian. Our inquiry starts with a basic observation about inverse- variance weighting of Gaussians.
Pick an arbitrary P E S and delete it from S;
2. Let (pi, Yo.), (pr, Xp.) E M where p E (pis Pr) and
Lemma 3.1. Let Yp N(9, + and Yp N(3, # where 3 E R and p.pl > 0. Then
Pr Pt minimal;
3. Sample Z ~ N (0. (100///////0))/ let
Y= = popfY y o' Xp ~ N ( Nptor
2(1 ((1-p//p)
Yp 1-Pily
I-piter p. + p
Y + 7,
1-piler
Proof. The mean of immediate by the fact that is weighted-aveeage of y and Ypr, both of mean f3. For the variance, direct computation yields:
and add (p,Yp) to M.
Then the sequence of random variables generated by the pro- cess has the same distribution as described in Lemma 3.2.
Var[M] p²/(22) + /(20022))
(01 + p¹)²
2(p +
Proof sketch. The argument is inductive. Under the hypoth- esis that all values generated up to the given point have the distribution described by Lemma 3.2, we argue that the newly generated value does too. The argument considers the four different cases for Pt. Pr. e.g., Pt 0. Pr + Pao. As the proof involves tedious computation we refer the reader to Appendix B for the formal proof.
As the sum of two Gaussians is itself Gaussian, we are done.
The essence of what is being claimed is that a Gaussian of variance 1 and another Gaussian of variance 1 with 2p the same mean can be combined into a new Gaussian with variance Σل and the same mean. Inspired by this, we can repeatedly invoke the lemma for the following result.
2p"
Formalizing lossless multiple release. Lemma 3.3 will constitute the basis for our implementation of lossless mul- tiple release, but we have yet to formally define this notion. We do so next.
Lemma 3.2. Given 0 < P1 .... < Pm and IR define Y Yp....,, ppm E R where Yp, ~ N(B, ) and Is > 1:
PKIITPK N (B.
1
Y YpR1 _
Definition 3.4 (Lossless multiple release). Let M, : X' + be a family of mechanisms on a do- main X, indexed by a privacy parameter P E R4. We say that M X R4 + y implements MM, with lossless multiple release if for every x E X' it satisfies:
Pa+1
Pa+1
2(px+1 - Pke)
Then for any i E [m] Yp: N(3, ) and for any j E [m] Cov(Y Yp,) m)
Proof. We first show the distribution of Yo, by induction on k. Assume that Yo, ~ N(8, 1 which is true for the base case of 1 = 1. Note that the inductive step follows immediately from invoking Lemma 3.1. For the covariance, note that we can expand the expressions inside the covariance and "throw away" the independent noise added in each recurrence. Assuming i و j we get P Yo.) = Pt Var p:l 2p3 pj
1. Yp: M(z, p) and Ma(r) are identically distributed.
2. For every finite subset S C R4, processed in arbitrary order by M, and E y, conditioned on M(x, max(S)) = y the joint distribution of (M(x, is uniquely determined by y and S.
CY,,Y, Y,,) = Cov(Y,:: pa: implying the stated covariance.
Functionally, a mechanism meets the definition if its outputs can be correlated such that for any set of outputs, their joint distribution can be viewed (randomized) post-procsssing of the least private release. An implementation necessarily has to store information about releases that have been made, i.e., the sequence of inputs to M and the corresponding outputs, to fulfill the requirement that releases for different privacy parameters are correlated. When M only supports outputting releases for a sequence of increasing privacy parameters, we call lossless gradual release.
Pj
Releases in arbitrary order. The Gaussian sequence in Lemma 3.2 will be the basis for our lossless multiple release version of the Gaussian mechanism. What the lemma does not address is generating the sequence in arbitrary order: Statically, given the full sequence (Pm)) we can gener- ate the Gaussians, but what if we receive them one-by-one and in arbitrary order? We will address this next.
4

---

Private Lossless Multiple Release
Algorithm 1 GaussianMuliplleReeees
case each coordinate has independent noise. We begin by proving that given S (ox k E [m]] C R+, where Pr < Pm. it is possible to construct set of releases {Y,,, pz to E [m]] that satisfy Definition 3.4. By Definition 1.1, it is possible to express each Yp, as
Parameters: & sensitivity 2₂
Inputs: Set of releases M. privacy parameter P
1: Find (px, Yoe), (PK+1, Y putr) M such that
2: p Pk-1) and v(pp, .) E M : of & (pks Pk++))
3: Sample 7p ~ N(0,43 U-pe/pi (IL//-1//01)))
211 pa PL++)
m m-1
4: Y, := 2p
Yp = f(x)= + ppm +
W Σ jmn
(I)
1-ps/px11
5: Add M = M U {1)
6: Return Y,
where P ~ D(pm) and W Pst1.0;; ~ C(Ps+1, Pj) are sam- pled independently. To prove that Yp, - Af (x), observe that Yo, is distributed as f(x) plus a random variable drawn from ((pm) *C(pm: Pm-1) +C(p.. Ps) = D(px), ), as needed. For the second property in Definition 3.4, observe that conditioning on Ypm = y we can express every other Yo, for k [m 1] as
Having stated the definition for lossless multiple release, consider Algorithm 1. It implements Lemma 3.3, and the idea is visualized in Figure 1.
Corollary 3.5. With M initialized as M {(0, oo), (o,, f(x)), Algorithm 1 implements the Gaussian mechanism with lossless multiple release.
Proof. Let ppps be the set of outputs produced by Al- gorithm 1 on receiving the set S of privacy parameters in arbitrary order. Observe that the algorithm is implementing the (adaptive) sampling in Lemma 3.3, and so produces outputs with the same distribution as Lemma 3.2. Property 1 of Definition 3.4 follows immediately from observing that Y,, (x)) ).)) For property 2, note that every release in Lemma 3.2 can be viewed as randomized post-pron post-processing of the least private release. One way to see this is to note that for any two releases Y, and Y, where < p', we have that Cov(Y,, ) = Var[Y,r], implying that Y, = Yv + Z for aptly scaled zero-mean Gaussian noise Z.
You +
Σ
W W
As result, the joint distribution on (Yp...... Ypm ) is uniquely determined by y. proving the second property.
We will now argue (inductively) that we can produce these releases adaptively. Let Si C S2.... .... C Sm = S be a sequence of subsets of S where |S = i. For the base case of S1 we can make a single release using As.p- For our inductive hypothesis, assume we have produced releases corresponding to all the privacy parameters in S,, Now, for S.+1. we re-label the privacy parameters such that S.+ {po where P1 < .... < Px+1- For the unique p; E Sn+1 \ Sn, we can conditionally sample it from the joint distribution over (Yp,) ke))kt)))), conditioned on the value of each release made in the previous round. By induction, follows that we can adaptively release S.
LI
4. Extending to Independent Additive Noise
We will next show that lossless multiple release holds for larger class of mechanisms. To proceed we introduce the notion of an independent additive noise mechanism.
Definition 4.1 (Independent Additive Noise Mechanism). We define independent additive noise mechanism Aj. X' + Rd as mechanism of the form
4.1. Sampling in Conerete Settings
Lemma 4.2 proves the existence of a sampling procedure for lossless multiple release. In Section 3 we showed sampling procedure in the particular case of Gaussian noise. In Appendix A we show that the structure of Algorithm I holds for general independent additive noise mechanisms. Namely, if the privacy parameters we support come from a bounded range (po. P C R4, then the corresponding a algorithm has a similar structure (see Algorithm 5).
(x, f(x) + 2 Z ~~77 D(p),
where D(p) is probability distribution parameterized in p. that draws a d-dimensional vector with i.i.d. samples.
turns out that any independent additive noise mechanism Ai satisfying Definition 1.1 supports lossless multiple release
More precisely, consider two neighboring releases Yp, and Y Ype+ with noise parameters Pk and Pt+11 respectively, and new lossless release Y, with parameter p E [Pk, Pk++]). We can use (1) on this set of m + releases and condition on the values of the m previous releases Y, .,...., Y,m.. Next, write W Wp = W1 + W2 where W1 Wi=b Y,- Yp and W₂ = Yp, Yp In Appendix A, we show that sampling
Lemma 4.2. Any independent additive noise mechanism Ai with noise distribution D(p) satisfying convolution preorder can be implemented with lossless multiple release.
Proof. The proof is for the dieedimnnaoonal case, but the same argument can be invoked for the multidimensional
5

---

Private Lossless Multiple Release
Yp can be reduced to the following task:
trivially hold for M' is the second property of Defini-
tion 3.4. For set S C R+, note that to condition on
Sample W1 conditioned on W,+W2= = Yp, - Pa11 (2)
M' max(S)) = is equivalent to conditioning on
H (M' (x, max(5))) M(x, max(S))= = (y) E V. We thus have that conditioning M'(x, max(5)) = implies that the joint distribution over (M(x, p) is fully determined, and consequently so is (H p))) = (M' ()) and we are done.
Example: Poisson mechanism. Consider the independent additive noise mechanism using the Poisson distribution, Poi(A). This mechanism has the property that noise is always non-negative integer, making it a natural noise distribution for integer vectors in settings where negative noise is undesirable. Appendix E states some basic privacy properties of the Poisson mechanism.
Theorem 4.4 (Meta theorem). Let M, :X + y be family of mechanisms on a domain X, indexed by a pri- vacy parameter E R4. Furthermore, assume Mp can be decomposed as M2 = As.p where
The family of Poisson distributions parameterized by p 1/A satisfies convolution preorder since for any X > A2 Poi(Ar) = Poi(A X2) Poi()2). To adaptively perform private lossless multiple release of value f(x) using the Poisson mechanism and parameters A1 >.............. >...> >>>>> Am we no- tice that the "bridging" distribution in the kt term the sum in (1) has distribution Poi(A: - AR+1). Note that without conditioning on Yp...... ................................ pm.. W1 Poi(A- A and W₂ ~ Poi(A - X). By Lemma E.4 in the appendix we have that the sampling in (2) reduces to W1 ~ Binomial(NN, for N = Xp, - Y p and (X - 1 - >x+1).
As. : + Rd is an independent additive noise mechanism for releasing J : + Rd with privacy parameter p and with noise distribution satisfying a convolution preorder (Definition 1.1);
:H:R* >> >Y is an invertible post- post-processing step:
Example: Laplace Mechanism. Koufogiannis et al. (2016) have already shown that the Laplace distribution param- eterized by / = 1/b satisfies convolution preorder for any scale parameters 6, b2. Let LapBridge(bz) b1) be the probability distribution that draws 0 with probability bg /b/ and from Lap(O, b1) with the remaining probabil- ity. Then Lap(O, 62) LapBridge(b2, 6n) = Lap(0, 6n) exactly. To implement lossless release via the sampling in (2), it turns out that the conditional distribution is a mixture W1- ~ LapBridge(h, b2) of three distributions: With some probability Wi equal either 0 or Yp, You.. and oth- erwise it is sampled from the convolution of two Laplace distributions. We also show that the related exponential distribution satisfies convolutionn preorder, see Appendix F for the full details.
Then Mp can be implemented with lossless multiple release.
Proof. The theorem follows from invoking Lemma 4.2 to- gether with Lemma 4.3.
Supporting non-invertible post-processing. To support non-invertible post-processing. we also introduce a weaker notion: weakly lossless multiple release.
Definition 4.5 (Weakly Lossless Multiple Release). A mechanism MM supports weakly lossless multiple release if it can be written as MM = HI o M' where M' sup- ports lossless multiple release and H is an arbitrary function (possibly chosen from some distribution).
We define weakly lossless gradual release analogously. It follows that these classes of mechanisms are closed under all post-processing. While this notion is indeed weaker, any algorithm M(x, p) implementing weakly lossless multiple release for a p-private mechanism Mp(x), will have the property that the set of releases (M(x, PES are max(S)- private, if p-privacy is closed under post-processing Exam- ples of such privacy notions are E- DDD and p-zCDP. We get the following immediate corollary to Theorem 4.4.
4.2. Lossless Multiple Release as a Blackbox
Inspired by Corollary 15 in Koufogiannis et al. (2016), we provide a meta theorem for lossless multiple release based on independent additive noise mechanisms. The central component is the following lemma, showing that the class of lossless multiple release mechanisms is closed under invertible post-processing.
Lemma 4.3. Let Mp X + y satisfy lossless multiple release, and let H y + Y" be an invertible function. Then M¹, = H o Mp also satisfies lossless multiple release.
Corollary 4.6. If the function H in Theorem 4.4 is not invertible, then Mp = H o As. supports weakly lossless multiple release.
Proof. Let M X + y be an implementation of M, satisfying lossless multiple release, and let M' = H o M, which we will argue implements loss- less multiple release. The only property that does not
Weakly lossless multiple release will play a role in the next section, where we consider non innierertible post-processing such as truncation.
6

---

Private Lossless Multiple Release
5. Applications
Algorithm 2 FaetloriiaaiooMMilliiieeeeeeee
Parameters: Factorization = LR, l2 sensitivity A
In this section, we describe two applications supported by our framework for lossless multiple release:
Inputs: Set of releases M. privacy parameter p 1: Find (px, Yoe), (pk-1, Y Yout1) M such that
p [Pks Pk+11) and V(p', E E p & (pks Pk+1)
Factorization mechanisms (Li et al., 2015), where we want to privately release a linear query Ax, and
3: 2p ~ N (0, (Lpp/p))(22p-111p)) 2(1 P(1-Pt/PL+1)
(1-pe/0)Y p2t +(L//p popk/p-plllee Pp-pppppppppp// 1) 1-pe/p2-1
Sparse Gaussian histograms, also known as stability histograms (Wilkins et al., 2024; Google Anonymiza- tion Team, 2020).
4: Let Y = L. 2p +
Set M = M U ((r,Y)))
Return Z
We will make use of both lossless multiple release (Defi- nition 3.4), and its weaker variant (Definition 4.5). This will be necessary since, e.g., the truncation used for sparse Gaussian histograms is not an invertible function, and so not covered by Theorem 4.4.
5.2. Weakly Lossless Multiple Release of Histograms
We will now describe an example where the post-processing is neither linear nor invertible: releasing sparse (Gaussian)
histograms (Korolova et al., 2009; Google Anonymization Team, 2020; Balle & Wang. 2018). Let x = =X,)" be a dataset of n users, and we want to privately release the histogram H(x) E'= X; where X, E {0. 1)dd and a user can contribute to distinct counts and the Gaussian mechanism which scales proportional to vi is preferable. In many natural settings, the domain size d can be very large, and therefore, the resulting histogram is usually very sparse, h = || (x))l) < d. Releasing a noisy histogram where noise has been added to each coordinate would de- stroy the sparsity. One can cope by introducing a thresh- old r 0 where only noisy counts that exceed 7 are re- leased. is usually set high enough such that the noise to a zero count will (after thresholding with high probabil- ity) still be zero. We denote the support of the histogram as (x)) = (i E [d] H(); A 0} as the index of the non-zero coordinates. Define the thresholding function T, Rd + Rd as:
Because the noise generation for histograms on large do- mains is expensive, we give dimension -nnndiinnnn-deedeeent algo- rithm that works in the gradual release setting. Throughout, state our results as post-processings of the Gaussian mechanism, but analogous results hold for any other inde- pendent additive noise mechanism meeting Definition 1.1.
5.1. Lossless Multiple Release Factorization Mechanism
Let A be query matrix and fix public factorization A = LRR. Denote the factorization mechanism (Li et al., 2015) as Fp(x)= = Ax + La= = L(Ix= + 2) on some pri- vate dataset x where Z is a vector drawn from a distribution (p) satisfying Definition 1.1 parameterized by p. typically Gaussian or Laplace noise.
Lemma 5.1. Fo can be implemented with weakly lossless multiple release, and lossless multiple release if L has a left-inverse.
T, = (w)) where y1 = Jis if 27
Proof. Observe that Fx(x) = Lo AR,p for IAN mech- anism (x, = Rx + 7. where 7 ~ D(p) for a D(p) satisfying Definition 1.1. The result follows from Theo- rem 4.4 and Corollary 4.6, and noting that the linear map L is invertible exactly when L has a left-inverse.
0, otherwise
Denote the (independent additive noise) sparse histogram mechanism as H,(x) = (H + 2) where Z ~ D(p) is a distribution satisfying a convolution preorder (Defini- tion 1.1).
Besides proving existence in Lemma 5.1, we also give an explicit instantiation in Algorithm using the Gaussian mechanism.
Lemma 5.3. Hp can be implemented with weakly lossless multiple release.
Lemma 5.2. With initialization M {00, sc), Ax)), Algorithm 2 implements the Gaussian noise factorization mechanism F, with (weakly) lossless multiple release.
Proof. Observe that H.p can be expressed as composite function T, ( for an independent additive noise mechanism Ap, (x) meeting Definition 1.1. The statement thus follows from Corollary 4.6.
Proof sketch. Note that the algorithm is practically copy of Algorithm/ 1, but for the specific sensitive function Rx. The only structural difference is that the linearity of the post-processing L allows for storing correlated Gaussian noise directly in M.
It is straightforward to implement weakly lossless gradual release for stability histograms using our framework with time and space complexity linear in dimension d: see Algo- rithm 3. The following lemma is proved in Appendix C.
LI
7

---

Private Lossless Multiple Release
Algorithm 3 HistogranCGraaullleeeeess
round. Intuitively, all zero counts that have never exceeded the threshold have an equal probability to exceed the thresh- old in any given round, and so the simulation technique in Lemma 5.5 can be used for these counts (with different prob- abilities and conditional distributions). However, once any zero count exceeds the threshold, it will have to be treated the same as non-zero counts in all future rounds.
Parameters: lg sensitivity 2Α
Inputs: histogram H (x), set of releases M, privacy parameter p. threshold r
1: Extract the single element (p', (Z)) E M
2: Sample 7 ~ N (0, -/300-0------0 )
3: Let Z = -z + -2
The utility and privacy of Algorithm 6 is proved by argu- ing that its output distribution matches that of Algorithm 3. A proof sketch for the following lemma is given in Ap- pendix C.
4: for each i E [d] do
5: if (xx); Z; then Y, H(x); + Z
6: else Y; =
7: end for
Lemma 5.6. Let (x) be a histogram over [d], Pl..... be sequence increasing of privacy budgets, TI...., Tm be a sequence of thresholds and 2 O the fz-sensitivity of the histogram. Also let the sequences of outputs (Y(),.... ((m)) and rumning Algorithm 3 and Algorithm 6 respectively with the preceding parameters as imput. Then the sequences ( Y(m)) and (Y..,.... (mm)) are identically dis- tributed.
8: Set M = {(pp 2
9: Return Y
(r(m)) be derived from
Lemma 5.4. With initialization M = 0)}. Algorithm implements Hp with weakly lossless gradual release.
Improving efficiency for weakly lossless gradual release. Korolova, Kenthapadi, Mishra, and Ntoulas (2009) showed that under approximate differential privacy, one can skip the noise generation for zero counts if thresholding is enabled, adding only a small probability for infimite privacy loss if this coordinate is non-zero in a neighboring dataset. Un- fortunately, this approach does not fit our meta theorem, so instead, we apply a technique due to Cormode, Procopiue, Srivastava, and Tran (2012) that efficiently simulates the noise distribution of those zero counts that would exceed the threshold and thus gives an identical distribution to the truncated noisy histogram. The procedure is described in the following lemma.
The benefit of the efficient sampling technique is that the number of sampled Gaussians will never exceed that of the naive approach and can potentially be in the order of the sparsity depending on the parameter regime.
Lemma 5.7. Let с be the number of zero-counts in the histogram output by Algorithm 6 least once over its execu- tion. Then Algorithm 6 will sample (k + c)mm (truncated or otherwise) Gaussians.
We again refer the reader to Appendix C for a proof.
Lemma 5.5. For a fixed noise distribution DD the out- put distribution of releasing (x)) + Z) with Z ~ D are independent noise samples is equal to the fol- lowing process: (a) add noise to every non-zero coor- dinate in Hxx), for i (H)()) and then (b) draw q~ Binomial(d- - k. where p= PrzwD|Z > T]. (c)
6. Empirical Evaluation
To confirm our theoretical claims, empirically evaluate the accuracy of lossless multiple release against a baseline algorithm that uses independent releases. We evaluate the impact by focusing on noise in isolation to avoid capturing the effect of specific queries. The baseline algorithm is simple Gaussian mechanism where noise is drawn inde- pendently for each consecutive release. To showcase our algorithm's 's performance, we demonstrate how the cost in- curred by uncoordinated releases grow with the amount of releases, in contrast to the lossless multiple release where there is no additional cost. We repeat our experiments 106 times, and measure the variance of the noise. The plot (Fig- ure 2) shows, as expected, that our mechanism does not lose any utility from making multiple releases. As we can see, there is expected increase in variance when going from one release to multiple releases-the initial jump is larger the more releases we want to make as the budget used for the second release is the difference between the starting point (p = 0.001) and a constant increase in budget, whereas the subsequent releases all have the same difference in budget.
Sample a subset Q S [d] \. (x)) of size [Q] = uni-
formly at random and (d) set the noise for Hx) to Z ~ D conditioned on being above the threshold T.
Proof sketch. A formal argument can be found in Cormode et al. (2012), here we just provide a sketch. It is clear that every entry in the support gets the correct output distribu- tion. Furthermore, the number of zero counts q whose noise exceeds follows binomial distribution, and can add conditional noise to a uniformly drawn subset of size q- D
Algorithm 6 in Appendix C implements the efficient rou- tine described by Lemma 5.5 under weakly lossless gradual release. The key challenge is that the probability for a his- togram count to exceed the threshold in a given round now depends on whether exceeded the threshold in any prior
8

---

Private Lossless Multiple Release
100 releases
limit.
releases
10a
20 releases
Acknowledgments
10 relcases
Variance
G releases
Andersson, Pagh and Retschmeier carried out this work at Basic Algorithms Research Copenhagen (BARC), which was supported by the VILLUM Investigator grant 54451. Providentia, Data Science Distinguished Investigator grant from the Novo Nordisk Fonden, supported Andersson, Pagh and Retschmeier. Nelson carried out part of this work at Uppsala University. We would like to thank the ICML attendees at our poster presentation for pointing us to Equitz & Cover (1991).
Lossless
10
10
10
10
Cumulated
Figure 2. Accuracy comparison of multiple uncorrelated releases compared to lossless multiple release. Budgets are spaced evenly on a logarithmic scale between p 0.001 and p 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.
Impact Statement
This paper presents work whose goal is to advance the field of private machine learning. There are many potential soci- etal consequences of our work, none which we feel must be specifically highlighted here.
7. Conclusion and Open Questions
References
We have initiated a systematic study of differential privacy with multiple releases, motivated by settings in which many levels of privacy or trust may co-exist. The main message is that it is possible to generalize large class of lossless grad- when releases
Agarwal, N., Suresh, A. T., Yu, X., Kumar, S., and and
McMahan, B. cpSGD: Communication-Efiicn Differentially-Pritn Privvtte Distributed SGD. In Advances in Neural Information Processing Systems, volume 31, pp. 7575-7586, 2018
ual release techniques to this setting, are determined online and in no particular order. For mech- anisms based on Gaussian, Laplace, or Poisson additive noise we give simple and efficient sampling procedures for creating new lossless releases. In particular, we are able to do lossless multiple release for any factorization mechanism using invertible matrices. Finally, we consider algorithmic challenges related to lossless gradual release and show that private sparse histograms may be computed much more effi- ciently than what a direct application of our general results would imply.
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- ceedings of Machine Learning Research, pp. 403-412 PMLR, 2018
Bell, D. E. and La Padula, L. Secure Computer System: Unified Exposition and Multics Interpretation: Techni- cal report, Defense Technical Information Center, Fort Belvoir, VA, mar 1976.
There are still many open questions concerning mechanisms that do not inherit their privacy guarantee from an indepen- dent additive noise mechanism. In particular, it would be interesting determine under which conditions the expo- nential mechanism (MeSherry & Talwar, 2007) supports lossless multiple release. Koufogiannis et al. (2016) con- jecture that this is always possible. Other central private algorithms, such as report noisy max (Dwork et al., 2014) also do not have known lossless multiple release mecha- nisms, even in the gradual release setting. final challenge would like mention is implementing our mechanisms on finite computer, e.g., creating a multiple release ver- sion of the discrete Gaussian mechanism (Canonne et al., 2020). An appealing approach would be to base this on Poisson noise, which meets the technical conditions for our framework and approaches the Gaussian distribution in the
Bun, M. and Steinke, T. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In The- ory of Cryptography, Lecture Notes in Computer Science, pp. 635-66666666 658, Berlin, Heidelberg, 2016. Springer. ISBN 978-3-662-53641- doi: 10. 00.1000/978-3-662-5566 4.24.
Canonne, C. L., Kamath, G., and Steinke, T. The Discrete
Gaussian for Differential Privacy. In Advances in Neural Information Processing Systems, volume 33, pp. 15676- 15688. Curran Associates, Inc., 2020.
Cormode, G., Procopiuc, C. M., Srivastava, D., and Tran, T. T. L. Differentially Private Summaries for Sparse Data.

---

Private Lossless Multiple Release
In 15th International Conference on Database Theory, pp. 299-311, New York, NY, USA, 2012. ACM. ISBN 9781450307918. doi: 10.1145/2274576.22724
Li, Y.,, Chen, M., Li, Q., and Zhang, W. Enabling Multilevel Trust in Privacy Preserving Data Mining. IEEE Trans. Knowl. Data Eng., 2499):598-1611, 2012. doi: 10.1109/
TKDE.2011.124,
Ding, Z., Kifer, D., Saghaian N. E., S. M., Steinke, T., Wang, Y., Xiao, Y., and Zhang. D. 'he Permute-and- Flip Mechanism is Identical to Report-Noisy-Max with 2021.
Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, Z. Accuracy First: Selecting Differential Privacy Level for Accuracy Constrained ERM. In Advances in Neural Information Processing Systems, volume 30, pp. 2566- 2576, 2017.
Exponential Noise. CoRR,
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography, Lecture Notes in Computer Science, pp. 265 -254. Springer Berlin Heidelberg, 2006. ISBN 978-3-540-32732-5 doi: 10.1007/1 1681878_18
McSherry, F. and Talwar, K. Mechanism Design via Dif- ferential Privacy. In IEEE Symposium Foundations of Computer Science, pp. 94-103. IEEE, 2007. doi: 10.1 1..10000SS.000...4
Dwork, C., Roth, A., al. The Algorithmic Foundations of Differential Privacy. Foundations and Trends The- oretical Computer Science, 9(3-4)2211-400 2014. doi: /04000004000
Pan, M. Randomized Response with Gradual Release of Privacy Budget. CoRR, abs/2401.13952,, 2024. doi: 10. 48550WarXi.2201.13333
Rogers, R. M., Vadhan, S. P., Roth, A., and Ullman, J. Privacy Odometers and Filters: Pay-as-you-Go Compo- sition. In Advances in Neural Information Processing Systems, volume 29, pp. 1921-1929, 2016.
Equitz, W. H. R. and Cover, T. M. Successive Refinement of Information. IEEE Trans. Inf. Theory, (7(2))269-22)) 1991. doi: 10. 109/18.75242.
Girgis, A. M., Data, D., Chaudhuri, K., Fragouli, C., and Diggavi, S. N. Successive refinement of privacy. IEEE Journal on Selected Areas in Information Theory, 1(3): 745-759, 2020. doi: 10.1 10.10999/AAT1222030000000
Shaked, M. and Shanthikumar, J. G. (eds.). Univariate Stochastic Orders, pp. 3-79. Springer New York, New York, NY, 2007. ISBN 978-0-387-34675-5 978-0-387-34675-5.11
doi: 10.1007/
Google Anonymization
Team.
Delta for
Whitehouse, J., Ramdas, A., Wu, S., and Rogers, R. M. Brownian Noise Reduction: Maximizing Privacy Sub- ject to Accuracy Constraints. In Advances in Neu- ral Information Processing Systems, volume 35, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 7781713871089
Thresholding.
https://github. com/
googlee//ffferenciaapprvvvbbbbb aTcc26us9174455fhh553baaa4aafff. common_docss Bat.accsDDeeea_o__Teeeeeeee Foobbta_For_Threehhlldiim pdf, 2020.
Korolova, A., Kenthapadi, K., Mishra, N., and Ntoulas, A. Releasing Search Queries and Clicks Privately. In Pro- ceedings of the 18th International Conference on World Wide Web, pp. 171-180, 2009, doi: 10.1 10.1145//526709 1526733.
Wilkins, A., Kifer, D., Zhang. D., and Karrer, B. Exact Pri- vacy Analysis of the Gaussian Sparse Histogram Mecha- nism. Journal of Privacy and Confidentialiry, 14(1), feb 2024. ISSN 2575-8527 doi: 10.2901 2/22001//jpc.23..
Xiao, X., Tao, Y., and Chen, M. Optimal Random Perturba- tion at Multiple Privacy Levels. Proc. VLDB Endow., 2 (1):814 825, 2009. doi: 10.14778/168766711667777
Kotz, S., Kozubowski, J., and Podgórski, The Laplace Distribution and Generalizations. Birkhäuser Boston, 2001. ISBN 100---1-112--661 978-6466447781111121117777- doi: 10.1007/978- 1-4612-0173-1.
Zhang, S. and He. X. DProvDB: Differentially Private Query Processing with Multi-Analyst Provenance. Proc. ACM Manag. Data, 1(4):267:1-2677) 2023. doi: 10. 1145/3626761.
Koufogiannis, F., Han, S., and Pappas, G. Gradual Release of Sensitive Data under Differential Privacy. Journal of Privacy and Confidentiality, 7(2), 2016. ISSN 2575-8527. doi: 1.99012jjcc.v72..cc Number: 2.
Li, C., Miklau, G., Hay, M. McGregor, A., and Rastogi, V. The Matrix Mechanism: Optimizing Linear Counting
Queries under Differential Privacy. VLDB J., 24(6):757- 781, 2015. doi: 10.1077/00078--055003999
10

---

Private Lossless Multiple Release
Algorithm 4 GenericMullipleeReen
Parameters: Noise distribution family D()) satisfying a convolution preorder,
bridging noise distribution C(p:p') where D(p') C(p', p)) = D(p) for O < p < p'.
Inputs: Sensitive value f(x), new privacy parameter Pk: set of past releases M {(ps, nx) : e [m] {b}}
1: if' M 0 then
2: Sample Zpu from (ppx))
3: Set p. = f(x)= 7pp
4: else if k = then
5: Sample Wp 11.PP from C(p++1,
6: Set pp = Y -pp++ + WWWWpas PL+1.Pt
7: else if E m1 then
8: Sample W pe.1..p from C(P++1, Pk)) conditioned W pe + W ph.pp- Y Yp--1 pp111
9: Set p. =Y 1p11 W
Y
10: else if k then
11: Sample Zp, from ((ps) conditioned on Zp. + W Pe.pa-1 YY pa-1 f(x)
12: Set Pc = [xx + Zpx
13:
end if
14:
Set . =MU U (pe, }
Return Pp
A. On Lossless Multiple Release Sampling
Lemma 4.2 makes claim about how easy it is to sample noise from the conditional noise distribution, but guarantees its existence. We will use this section for discussing this sampling in greater detail. Consider the joint distribution of the releases defined by Equation (1) from the proof of Lemma 4.2, re-stated below for convenience:
m
Yo = [(x) + Zpm +
W Wp
A: 1,..., m.,
1:05
j=k
where Yp the Pk Px-private release, Zp... ~ D(pm) and W Wp ~ (())+1-P)). Recall that C(p', )) is the unique distribution where for any < p < p': D(p) = D(p') * C(p'. .p). As argued for in the proof of Lemma 4.2, to make a new p-private release, we consider the joint distribution, and sample the new releases conditioned on all past releases.
Formally, for set of privacy parameters P1 < .... < Pm. are interested in releasing Pk for single k [mm] conditioned on the set of past releases M = ((Pi, y,,) : E [m] (k)). We give pseudocode for this in Algorithm 4, and lemma for its correctness.
Lemma A.1. Initializing M = 0 and then running Algorithm 4 for a set of privacy parameters {p: : E [m]} (processed in arbitrary order), will produce a set of outputs (Yp, : [m]] with distribution given by Equation (1).
Proof. For M = 0, we have that Yp = f((x) + D(p))= As.p (x) on lines 2-3, as expected, where A is our independent additive noise noise mechanism releasing f with p-privacy. For the remaining cases, assume M contains m releases with the correct joint distribution, and we are generating new release at privacy level Pk. We will argue that Algorithm produces Ypu whose joint distribution with the releases in M matches (1). For and so lines 5-6 correct. For 1 k- < m. note that Yp Yp--1 + W Wp and Y Yp__; =Y,, + W pe- which combined allows us to identify the correct conditional distribution. Y,,, is given by Ypu+1 W Wptt..p. conditioned on
1, observe that Yo, Yy, + Wp2.o1
W P.4 + W Pe-PP-1 You_ - Y Y matching lines 8-9. For the final case of k = m, then Ypm. f(x) + Z, and we have that Yom-1 Ypm + W pm-pmm1 It follows that the correct noise distribution is Yp... = f(()) + Zpm conditioned on Lemma 4.2 completes the proof.
Zpm + Wp .m-1 = Ymm-1 - fx),, matching lines 11-12. An inductive argument identical to that given in the proof of
A.1. Simplification and Removing Dependency on the Dataset
Note that fx) is only used in Algorithm 4 when a more accurate release is generated (lines and 10). In the remaining cases we are only adding noise past releases. This already allows us simplify the algorithm, and argue for not having to

---

Private Lossless Multiple Release
Algorithm 5
Parameters: Noise distribution family D(p) satisfying a convolution preorder,
bridging noise distribution C(p: p¹) where ((p') C(p', .) = ((p) for 0 < p < p'
Inputs: Privacy parameter P. set of releases M
1: Find Yn.), (08+1, Ypes1) E M such that p E [pk, Pk++1) and v(p', :) E M o & (pksPk+t)
2: Sample W. pe from C() conditioned W puti W ppppz pips = pp Y Yp
3: Set Y, =Ype pet1 + W Wi
4: Set M = MU (p))
5: Return Y,
store (x) in memory indefinitely. The algorithm reduces to the case (see line 7 of Algorithm 4) where only the two closest releases are combined into a new one. Such an algorithm is given in Algorithm 5, together with Lemma A.2.
Lemma A.2. Let M- = {((o, po (Poc: p==) for px = Ap (2), and p = +W pu Then running Algorithm 5 with input M and a set of privacy parameters {or : E [m]] C (oo) (processed in arbitrary order), will produce a set of outputs (Yp, : i e [m]} with distribution given by Equation (1). Moreover, the set M will at all times satisfy Poo privacy.
Proof. The statement follows from carefully comparing to Algorithm 4. Let S = (PI...., pm.) be sequence of noise values from the lemma statement, and let O = (Yp.....,yYuu ) be the outputs. Consider a second sequence S' = (Poc. Pu- . pm), and consider the corresponding sequence of outputs O' = pxx Y%, =(Yp> Yp.....,. from inputting S' and M' = 9 to Algorithm 4. We can directly check that Y,, _ Y and Y Pec Y that just before each algorithm is called, their internal states M and M' are also identically distributed. Now, the fact that each p. E (Po:Psx) implies that the remaining outputs y,,,,.. Y are generated from lines 10-12 in Algorithm 4.
Pas. For the remaining outputs, note
Checking carefully, lines 1-3 in Algorithm 5 are implementing the same routine, and since M - M', it follows that (Yp.....,, Y_.) & (Y,,..... Y and so the statement follows from Lemma A.I. The last statement on the Poe-privacy of M follows from Algorithm implements Equation (1), and so each release in M can at any time during execution be viewed as randomized post-pret pos--processing of Yoo.
Essentially, if we commit to supporting a bounded range of privacy parameters then we get a simpler algorithm. Lemma A.2 also says something more: we commit to supporting a lowest level of privacy Pax, then Algorithm 5 can implemented in such a way that its internal state is -oe-prittte. After initializing M using the sensitive function f(x), we can erase fx) from memory and Yo will contain enough private information generate all future releases. This could prove useful in settings where the time between releases is large, and we want to limit the private information leaked if the state of the algorithm were to be compromised. This can be compared with the gradual release setting, where natural implementations would require consistent access to (xx)
B. Omitted Proof for Gaussian Lossless Multiple Release
Proof of Lemma 3.3. Throughout the proof we will ignore the factor 2 in the denominator of the variance. To argue that the values generated by the process match the distribution Lemma 3.2, we will argue for increasing subsets of releases. Let S. {pk k E [n- }]} where 0 < P1 < ... < Pm. < Poo be the set of values in S for which we have generated Gaussians at the start of the n2th round of the process. Note that we re-label the p's between the rounds such that Pk: E Sn always is the
ttth smallest value in S,, Our argument will proceed by induction: assume that all the Gaussians (Yp. Pv. : k E [m]] generated
after n rounds have the distribution given by Lemma 3.2. Then we will show that (Yp,= k E [n - 1]} U {Y,} has the same distribution as predicted by S, J [p) from invoking Lemma 3.2.
We begin with our base case. For 1, we have that pl and p.- = Poo. and so Y, Yp,. + N(0, 1t1.1//ppp///eeee.ee Since Yp... N(3, 1/ we have that Y, N(8, 1/p), as expected, and so the base case passes.
For 2 2, we first consider the following cases.
Case 1: Pr = 0, Pr = PI E Sn- In this case, y,= =Y,, + +N11pp - 101/p-1/p).. 1/p1). and so Y, ~ N(8, 1/p). Since p < P1, we have that Vi E [n - 1] Cov(Y,, Yp.) = Cov(Y,, 1x) = 1/p,, s, as expected for the release with the smallest value in {p} Sn. and so the case is complete.
12

---

Private Lossless Multiple Release
Case 2: Pt = Pn-1.Pr Poo 00. We have to deal with the case where have set Poo separately, it is bit of trick. Note that we get y (1-
N(0, 1/))) since yp B in this case. The end result is once more sum of Gaussians, with mean 3, and for the variance we can explicitly compute that Var[Y,] = 1/p, as expected. For the covariance, for E [n - 1] Cov(Y,; Yx,) Pr P Cov(Y p.. Yo:) = 1/p, p. as expected for the largest value in {p} U Sn, and so we are done. Now we consider the most general case.
Pn-1 P_Pa-
Pm mn-1p" p
Case 3: PL E Sn-1 and Pr o cc. We begin with computing the variance of Y using the hypothesis Var[Y,.] = 1/p, and Var[Y 1/p1
(p/ p p- (p - + (pj P 1)2 Var[Y, + (0 - 2/ Var(Ypl
Var[Y;]
P1
Pr
(0T pr 1/2
(pi Pr 12 (pt ( -1p0tt1;,'00 MTT - pr)) + Pr ( - 11 + pi
- - 11
1
( 1 - - p -pp 1p---pp-1 1² p
where the third equality follows from applying the identity
(a- -a-bb( bb (a -0) + c(a b)2 + a(b c)² b(aa - -c)²
the expression in the brackets for a = p b p- and c ,, proving the correctness of the variance. Furthermore, Y, is sum of Gaussians and convex combination of two Gaussians with mean 3, so Y N(B, 1/p). What remains to show is that the covariances match up, which we do next.
We start with the case where or + Poo. and so there exists Pk. Pk+1 E Sn such that E (pk, Pk + 1) For j E [n 1]. we therefore have that
(pi 1 - p 1) + 1p-1-pp 2r Yo:
Cov(Y,; = Cov
Pi -pr- PF²
(pr Coov (Ypr, Vo,) + (0- - pr Cov)) Xos) kos)
Pr I
Pi
(pT pp-l-p1) 111 min(p;) , + (p pr min(pi ,p
Pi pr
We consider the cases of) j < l and j > k separately. For j < k, we have that
1
Cov Yoz)
Pi pr - (pT p ))= 1 + (0- - pr pp=
p'
and similarly for j 2 + 1 we get
Cov(Yp:Y Yp,)=
1
(pk) - -p-1)0=² + (p- -ktti)p
Pk Pktt1
Pj
A3 It follows that Cov(Y,, Y2,) 2 max(ppps) for j E [m], and so we are done with this part of the covariances.
For the last step, we consider what happens when Pr Poo < 20. In this case, Pt = Pn-1 and for j E [n 1]:
(1- Pn- pn-)p pmo + (pn-1/p- Pn 1/p M Nps
Cov(Y,,Yo) ) = Cov
1 L-Pn-1/Poe
Pn-1/P Cov(Y, pw:: Vo,) + Pn-1/p Pn- 10-1p-Pn-1/PP- Cov(Y (Ypm-11 Yes)
1 Pn-1/Px0
1 Pn-1/ Poo
1 Pn-1/P + 1/p /30
Pn- 1/ /pp Pool -1
1/p,
Poo - Pa-1
1 - Pn-1/PP Poo
Pso - Pn-1
and now we are done.
13

---

Private Lossless Multiple Release
Algorithm 6 Efficient SrorriiiiiiisoggannnGnaauallllll
Parameters:
lz-sensitivity 2
Inputs: Private histogram (x)), privacy budgets p1 <...< < Pm. thresholds Ti..... Tm
1: Let (()) (x)) // Tracking counts that have already been released
2: Also let ( {0}d and Po 0.
3: Vr E [m]] let distribution Dír) N (0, _03 pr-
4: for each round E [m]] do
5: Initialize (r)) = (0)d
6: for each tracked count in preceding round j Es(r-1) do
7: Draw fresh noise ( ~ D(r)
8: Update aggregate noise 7/²) Pr-1
Pr 2 1) + 1 (())
pr
9:
if (x); + Z17) Tr then
y,!h) (x); + Z (r)
10:
11: end if
12:
end for
// Simulating Noise for zero counts
13:
Let (R)) () for & E [r] be random variables.
Compute p(*) = Pr Σ (()) TrPr (Vl E [r Dk- 2(00 s pete}
14:
15:
Draw g Binomial (d (,p())
16:
Select subset Q [d] \ g(--)) uniformly at random of size q.
17:
for each index j E Q do Initialize 7,-) for k E [r do
18:
19:
Draw fresh noise -1th
(k) conditioned on -7-h S PkT - 2
20:
Update aggregate noise z = - + -Z/0
21:
22:
end for
Draw fresh noise Z//ha (()) conditioned on Z,(11 Tk - 2357)
23:
Update aggregate noise z/(7 z,-) + 2
24:
y Hxx), + 2/-r // Guaranteed be above the threshold.
25:
26:
end for
27:
Set ((r) 1 UQ
28: output private histogram (r)
29:
end for
C. Details on (Efficient) Weakly Lossless Gradual Release of Sparse Gaussian Histograms
Algorithm implements weakly lossless gradual release of private histograms. We prove this next.
Proof of Lemma 5.4. Observe that for any increasing sequence (pk)kem. the corresponding sequence of variables Z on line 3 produced by the algorithm, have the same distribution as in Lemma 3.1 for 3 The Y that is ultimately returned, however, is post-processing of (x)) + Z, which has the same distribution Lemma 3.1 for 3 H(x). Therefore Algorithm 3 is implementing lossless gradual release for the Gaussian mechanism applied to H (x), combined with non-invertible post- post-processing. The lemma statement follows from Corollary 4.6.
Note that only has to store the noisy terms from the preceding round implement Algorithm 3. Nevertheless, it might be infeasible, say, when the domain is really large, to sample the noise for the zero coordinates. Algorithm 6 uses the computational trick in Lemma 5.5 to speed up this computation. The algorithm is static, where the privacy budgets are fixed upfront but can easily be converted to an online algorithm. Recall that (x)( = {i [d] / (x); + 0} is the support of the histogram.
We proceed give proofs for Lemma 5.6 and 5.7.
14

---

Private Lossless Multiple Release
Proof sketch for Lemma 5.6. The claim directly follows an inductive argument. For the base case, note that the first iteration of Algorithm 6 is running the same routine as deseribed by Lemma 5.5, and ÿ must be identically distributed to (L), For our inductive hypothesis, assume that the subsequences (Y ..... (()) and (Y(1),... ,.... (k)) are identically distributed. Note that for the (k + 1)ah release, Algorithm 6 handles all the true nonzero counts and every zero count that has
ever exceeded the threshold in a past round in the same way. These counts in y(++1) and y clearly have the same distribution.
Now, note that each of the remaining zero counts have up to and including the k round been reported as zero in each round, and so their probability of exceeding the threshold, p*++1), should be equal across all of them.
The sampling performed by Algorithm 6 is structured in the same manner as Lemma 5.5, but with sampling probability p(&+1), and the noise terms added for any zero count exceeding the threshold, are different. For the distributions to match, the probability of exceeding the threshold and the noise distribution for an element chosen to exceed the threshold are more complex. The probability of exceeding the threshold is conditioned on prefixes of Gaussians, which correctly simulates the probability of not exceeding the threshold at any prior round until first doing so in the (A: + 1)st one. The noise added once selected to exceed the threshold is sum of truncated Gaussians, which simulate the same event. As the principle is built on ,..., y(k+2) are identically distributed, and so the same logic as Lemma 5.5, we have that (Y ,..., "....,,(++t))) ((++)) and (1) ..... the claim is true by induction.
Proof of Lemma 5.7. Note that each of the k non-zero true counts will, in each round, have fresh noise added on line 7. If non-zero count is selected by the binomial sampling in the htth 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 begin with the most common version of differential privacy.
Definition D.1 ((E, Diifferrrent Privacy (Dwork et al., 2014)). A randomized algorithm M : x y is (c, differentially private if for all S C Range(M) and all pairs of neighboring inputs x,x' E X, it holds that
Pr[M(() S] s exp(e) Pr(M(x')) e 5
where (c, DDDD is referred to s-DP.
Zero-Concentratedd Differential Privacy (zCDP) is notion of differential privacy that provides simple but accurate analysis of privacy loss, particularly under composition.
Definition D.2 (Bun & Steinke (2016), p-ZCDP). Let p 0. An algorithm M X' -> y satisfies p-ZCDP, if for all a >> 1 and all pairs of neighboring inputs x, x' E X, it holds that
Da (M) (x')) S pa;
where D& (M (x) [[M (x')) denotes the a-Rényi divergence between two output distributions of M(x) and M(x'). Lemma D.3 (Bun & Steinke (2016), Composition). If Mi(x) and M2(x) satisfy P1-2CDP and p2-zCDP, respectively,
then (Mi (x), M2(x)) satisfies (p1 + P2)-zCDP
Lemma D.4 (Bun & Steinke (2016), Gaussian Mechanism). Let f X Rd be a query with lz-sensitivity D2. Consider the mechanism Gy.p : X > Rd that, on private input x, releases a sample from f(x) + N (o,
A3
Then gy.p satisfies
2p
p-ZCDP
One way to uniquely describe probability distributions is via their Characteristic Functions. Definition D.5 (Characteristic Function). The characteristic function of random variable X is defined as ypx (t) E]
For proving Lemma F.4 and Claim F.7, we will use a nice property of CF' for the convolution of two random variables:
Lemma D.6 (Convolution of Characteristic Functions). Let X, Y be two independent RVs with CFs (xx(t) and yp (t) respectively, then xx+Y(() (f) = px (t) ()
15

---

Private Lossless Multiple Release
Proof. Furthermore, by linearity of expectation, we have for the of X Y:
Px+y(t) Ele [x*++ Ele" + = (xx(t).
E. The Poisson Mechanism
We are not aware of any explicit statements in the literature the privacy guarantees obtained by adding Poisson distributed noise to a d-dimensional vector of integers. However, since the Poisson distribution is the limiting distribution of binomial distributions with the same mean À = Np, where N is the number of trials, such bounds can be derived from existing bounds on the binomial mechanism. For the sake of completeness, we include such statements based on the following theorem from (Agarwal et al., 2018):
Theorem E.1 (Agarwal et al. (2018)). For any ó, parameters N, p and sensitivity bounds AI, A2, Doo such that
10d
Np(1 - p) 2 max 23 log
24x
the d-dimensional Binomial mechanism (s, 8) -differrentillly private for
= A 2 log 125
22 log 10 + A1b, 5 Np(1 p)(1 8/10)
2 A log
1.25 + Ax dp log 20d
log
à
VNp(1-1 1
Np(1 p)
where
4 (1) bp a 2(p² + (1-p) dp
(p² + (1 (1-p) 3
3 + (1 (1-2p), cp 2 (3p2 + +3(1 - p)² 2pp + - -p)3)
Setting p = A/N and considering the limiting bound when + oo we get:
Theorem E.2 (Privacy guarantees of the Poisson Mechanism). The d-dimensional Poisson mechanism with parameter max log (1d//)), 2A..), is (e, -iiiferreenl private with
A2y 2 log 25
5v2A21
log 10
A
A log
1.25 + 5
4 1 log 20d 10 3
log 5
8
A(1 5/10)
simpler expression can be derived for unit sensitivities by relaxing the constants and assuming that 5 not too large: Corollary E.3 (Simplified upper bound with unit sensitivities). Assume that A = A2 = A.c = 1. Then for ô < 1/100, the d- d-dimensional Poisson mechanism with parameter À > 23 log(10d/6) 8) (e, 6) diffferrentl private for
2og
1.25
20d log
10 log 5
5
We will need the following lemma that determines the sampling step of private lossless multiple release for the Poisson mechanism:
Lemma E.4. Let Xe ~ Poi() and X2 ~ Poi(Az) be independent Poisson random variables. Then, for any nonnegative integer the conditional distribution of X, given X1 + X2 = k is
A1 A1
X1 (X1 X2 k) Binomial
+ 2a
Proof.
Since X1 and X₂ are independent, their joint probability mass function is for all x 0,
(A1+ Xi Ak-r
P = z. X₂ k x]] =
x! (k: x)!
16

---

Private Lossless Multiple Release Moreover, the sum X1 X2 Poisson with parameter A1 Xg, so that
Pr[Xi + X2 = k) e (Ar+t2) (Ar + X2)
k!
Thus, by the definition of conditional probability,
Pr[X, = I, X2 = 2
Pr[Xi = x X + X2 = kj
Pr[X1 + X2 k)
e AA1 +2a) A9 X/ k-D
x! (k: x²
e- (A1 + x2)
k!
k
X
)
A2
k-w
ty
Ao
A2
This is precisely the probability mass function of a Binomial random variable with parameters and A1
F. The Laplace Mechanism
Koufogiannis et al. (2016) showed how to do lossless gradual releases for the Laplace mechanism and supports either tightening the privacy guarantees or loosening them. We will now strengthen this result by exactly showing how to do them in arbitrary order, similar to what was done in Section 4 for the Gaussian mechanism. We will first show that the Laplace distribution satisfies Definition 1.1. This already implies the existence of an algorithm supporting gradual lossless release via Lemma 4.2. After, we will derive how to sample new release with scale parameter given two distinct releases with scaling bg and b < bj.
Definition F.1 (Laplace distribution). The zeno-centered Laplace distribution Lap(0, b) with scale parameter >> has probability density function [b(x) 2/ exp( (x//bb for all x E
Lemma F.2 (Kotz et al., 2001) Characteristic function of Laplace). Let X be Laplace random variable with probability density function as Definition F.I, then for all E R, the characteristic functiooo of X
0
(x 1
itx 1 f
1x//6 dx
1
2b
1 1 1212
Proof. By simple integration:
(j albtiii d da
itz |zl/b 1
F MX
2h
2h
1
2h
1/b + ti 1/b
1 02
We will now show that the zero-centered Laplace distribution with scale parameter b satisfies convolution preorder (Definition 1.1). Note that a larger value of corresponds to more private release by definition. Building this, we will condition on the two closest releases to create new one in the middle, as done in Lemma 3.3 for the Gaussian. The following fact was already shown in Koufogiannis et al. (2016), but we give proof here for completeness using technique based on characteristic functions as done by Equitz& & Cover (1991).
Claim F.3 (Convolution preorder: Laplace). Fix by < b R ler X ~ Lap(0, bz) and draw
0
with probability 63/62
W-
then X + W Lap(0,b))
Lap(O,bl) b1) otherwise
17

---

Private Lossless Multiple Release
Proof. We know that the characteristic function of X is (px(() 1+6372 of independence, the convolution is defined for all as:
and for the convolution Px+W
148,02 Because
sx (xx()) = (()+w(()
1+
b3 +222
+9(1)) 02 61 + bft2)
+
02 bf
b2
(l(() 1 byt2
+
1 + Bft2
is again the The last expression encodes the convex combination of the claimed mixture distribution because 1+ characteristic function of a zero-centered Laplace distribution with scaling parameter b1.
We next prove a simple result about the convolution of two Laplace distributions (compare also eq., 2.3.23 of Kotz et al. (2001)).
Lemma F.4 (Convolution). For two fixed scaling parameters b1 + b2 E RR,, let X1 ~ Lap(O, b1) and X2 ~ Lap(0, b2). Then the density of X1 X2 given by
(fo, * (t))
1 bie (bje-1tl/b 1t///1
b2e b2e-11//2))
2(b} - bī))
Proof. Assume t 2 and note that the other case follows by symmetry. We compute the density of the convolution by a straightforward integration:
(fo, (b)) - L for (z) (((6-x)de x)dx
1
[
t
exp
dx
4b1b2
bj
b2
1
(
e --t=x t-x dr + 1"
000
xut
e-h
by
dr
+
E
b2
dx
4b
0
1
cxp (xxp(x/b/ -tt -t--x)/bb x))bb))
4b, b2
67 + +b²
Texp( -x/b1 - (1 - (1-x)/bbl -2)
exp -x/bi - (x - (2) 00
+
bg bid
-b²- bj
0
1
[cxp(-t/1) exp( exp(-t//b)
exp( +//b2)
+
b1 + b2
01 b2
b1 + b2
(bee-1/0
bae -1/b2)
200
Now, we are ready to show that the Laplace mechanism can be implemented with multiple releases. Lemma F.5 (Multiple release Laplace). For fixed < b2 < b < by let la = 132 f& and μl = D2//2 and D1 ~ Ber((n) and D2 ~ Ber(Hz2. Furthermore, let
0
fD= and X2
10
if D2=1
X1 =
[Tap(,,b)) b2) otherwise
Lap(O.b) otherwise
Then we have that Pr[X1 = X, X2 = 0] 1, and for every real number + the distribution of X, conditioned on
X1 X2 k is:
exp(-1A|//bg
0
with probability - (12) 2h fx,+X, (k)
exp( (1x1/bb)
X1 (X1 + Xx k)) ~
with probability (1 111 422 26 fx, xx (k)
(3)
with probability (1 p1) (1 12) (ʃo (kk
H (b, bz, k))
fxi+x,
18

---

Private Lossless Multiple Release
where O and k denote the constant distributions, Hb, b2, k) is the probability distribution with probability density function fo(x) (k- x)
h(x)= (fb (k)
fx, fxi+X.
11(1 1111-11
- 12
e-1l/bb (1 11-pe 11 e (1-1)(111111 (be (be-1h/66 bye -211//1))))) + #111200(z)) and
2b2
25
2(62 6%)
(ʃb * fb,)())))))))))))))))){))))
1
(bie b2e-1112))
2(12 - -12)
where 6g is the Dirac delta function.
Proof. First we consider Pr(X; = 0|X1 + X₂ = 0). arguing that
Pr[X1 = 0|X, + X2 = 0] Pr[X, = 0J Pr[X2 11
= 1.
Pr[X1 + X
M1P2 +0
To see why the first equality holds split Pr(X1 + X2 = 0] into each of the four combinations of discrete/continuous for X1, X2. The only non-zero contribution to the probability mass comes from the discrete/discrete case, as the remaining cases contribute mass proportional to the probability that a continuous distribution assumes an exact value, which is zero.
Next turn to the distribution of X1 conditioned on X1 + X2 k where k + 0. Denote by fo the probability density function of Lap(O, b). Note that the mixture densities become
fx (x) = (1))(2)) (1 (z) (x) p200(z) f2) (z)
Before analyzing the different cases separately, we compute the convolution X1 + X2.
Convolution fxi+X.'
Note that have to take care of a subtle technicality: The case that both X, and X2 are zero from the discrete part can only happen when we condition on X1 + X₂ = O. We can now give the density of the convolution X1 + X2 at any real point a::
fx)xx(+)=
Σ
fx1-x, D. (x) Pr(D: = d1 ^ D2 = d2l
(2),d2)
p1 (1 (22
for (z) + (1 p1) fo(z) (1 11) p2) - (fo (b) + (2)220(())
(11(11 (1-42) u2) -l01/ba
p )2 e 14//6b + (1 - p1) 122 2(12 b3) be
121/6 -11//
b
1w /b2
2b2
2h
+ (11)20(()))
where the third term follows from Lemma F.4. Note that the last term only contributes when 0.
We can now show how the sampling procedure in the claim is justified. We first assume l * O and analyze three possible cases how X, + X₂ 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
O, analyzed above.)
Case 1: Xı = 0 and X2
X2 = 1: is necessarily from its continuous part. By the definition of conditional probability, we have for k ş 0:
Pr|X1 0 X1 + X₂ k]
Pr[X1 = 0 Pr k-
Pr[Xi = 0|X, + X2 = k. k 0j
Pr[Xi + X2 =k]
Pr[Xi + X2 = k]
(x)(k)
11 112)
1k1/b2 = P1.
=11 fxi+x, (k)
2b,fx,-xx (k)
For the third equality, we simply used definition of a probability density function via its limit:
Pr 2X2 E kk -
A
k
All
(k)
Pr
X
X2
k
A
AJ.
(x)+x,(k)
19

---

Private Lossless Multiple Release
Case 2: x1 k and X2 0
Now assume the flipped case. By similar argument:
Pr[xi kz X1
+ X2 =k]
Pr[X = kj Pr(X2 = =0
(1-M1)6 -1k1/66 P2.
Pr[Xi x| + X2 =A--
Pr + X2
Pr[Xi X2 2bfx,+x,(k)
Case 3: X1 +
In the remaining case, both X1 and X2 are independently sampled from continuous Laplace distributions with probability density functions fa) and ft, (z). Therefore, with the remaining probability 1 (p1 + p2), we know that X₃ is sampled according to the following conditional probability density function:
fx, +=) = (x,, fo(x).o,, (k x)
(Jb (k))
(fo * (k))
where the last line follows from the trivial identity X1 + X2 = k + X2 = k - X2. This is a valid probability density function because f is trivially non-negative due to its parts being non-negative and furthermore
00 fo(z)fb,(z (x k) dx (Fo * foa(() (fo * fon)())
L fo(x)fos(k 2)
(fo x (k.) (fo = [kk)
What is left is verify that the probabilities in Equation (3) indeed add up one for + 0:
mI)(1 - (f (kk (1 11) exp( (asppp1kk/// (kl/bb) 11(1 u2) exp(-11il/b2
fx1+x,
2bfx,+X0 xx, (k)
2b2fx,+X, +x,
-12))( (kk) + (1 m1)22 [xp( - (x|(-11|/b) + 11 (1 p22 exp(- (111))))//b)
(1 (1- (1- (k)+
(2)
c -
26
2b
fx +x2 (k) for Ry60
F.1 Showing Convolution Preorder for Exponential Noise
The exponential distribution closely related to the Laplace distribution, but gives poor differential privacy guarantees.
Nevertheless, it still serves as building block for some private mechanisms, e.g., Repport-Nosy-MMar (Ding et al., 2021).
We show next that it also satisfies convolution preorder.
Definition F.6 (Exponential distribution). The exponential distribution Exp(A) with rate parameter À has probability density function (x) exxxp--X0 Ar)) for all R4. Furthermore, its characteristic function is given by 9 (t)
EleitX] À xx-
Claim F.7 (Convolution preorder: Exponential distribution). Fix A1 < d2 R4,, let X Exp(A2) and draw
0
with probability X1/22 then X W Exp(A1).
W
Exp((1)
otherwise
Proof. Using the same trick as in the proof of Claim F.3, we have that
(t) A1 A2 - it
A
A2 - A1
A1
| A1 ) (x+
Pw (t)
+
(()
A2
A1 il
A2
A il
X2
where the final expression is the characteristic function of the claimed mixture distribution.
20


Reviews:
[{"review_id": "T9awXgKXDM", "reviewer": "Reviewer_YEn2", "summary": "This paper studies the problem of lossless multiple release under differential privacy: we want to release a noisy answers to a query satisfying various levels of privacy such that any subset of the noisy answers contain at most as much information about the statistic as the least private noisy answer.\nThis work builds on results about gradually releasing noisy answers with increasing budget. \nThe authors identify a condition of a noise distribution called convolution preorder that is sufficient for an additive noise mechanism satisfying lossless multiple release. \nThis approach is illustrated through the case of Gaussian noise and applications are given for factorization mechanisms such as the matrix mechanism and sparse histograms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review and the question about the lossless multiple release setting. \n\nRealistic privacy settings could be the military setting itself (which Bell-LaPadula was designed for), or other settings where analysts have different trust levels (here the more trusted analysts would get more accurate releases). Another example is if a company wants to release a statistic, say, user statistics: they could make an accurate release for their own data analysts, a less accurate release for external consultants, and include an even less accurate release in a report for shareholders or other external actors. A benefit of this is that lossless multiple release allows for dynamic updates: an external consultant that later gets employed directly by the company could get the more accurate release without constituting a privacy violation or requiring an increased privacy budget to reach the same accuracy.", "claims_and_evidence": "The claims in this paper are well supported by theoretical results.", "methods_and_evaluation_criteria": "The proposed methods make sense for the problem.", "theoretical_claims": "I checked the main text proofs - but not the appendix proofs - and did not spot any errors.", "experimental_designs_or_analyses": "The empirical evaluation is reasonable and a good sanity check but is unnecessary.", "relation_to_broader_scientific_literature": "This paper deepens our understanding of additive noise mechanisms used in differential privacy beyond the gradual release setting.", "essential_references_not_discussed": "I am not aware of essential references that are not discussed.", "other_strengths_and_weaknesses": "Interesting paper; the organization made the paper clear and easy to follow. Both the sections on Gaussian noise and factorized mechanisms were helpful in looking at specific instances of the general result.", "other_comments_or_suggestions": "In the camera ready version, I don't think the empirical evaluation is necessary. I understand why you added it to the submission though.", "questions_for_authors": "One area of improvement is with regard to motivating the lossless multiple release setting. What is a natural setting that would be analogous to the Bell-LaPadula model for privacy? In what setting would you want one analyst to have a less noisy estimate than another?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "06tXBQMG62", "reviewer": "Reviewer_qwxZ", "summary": "This paper investigates the private lossless multiple release problem and presents a solution for a broad class of mechanisms  (e.g., Gaussian, Laplacian, Poisson) based on additive noise, where the noise distribution satisfies a convolution preorder property. Unlike private gradual release, multiple release does not require an increasing privacy budget. Additionally, this paper explores two applications: one for the factorization mechanism and another for sparse histograms, demonstrating its practicality.\n\n## update after rebuttal\nI will keep my score unchanged.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. \nOur technique applies to additive noise mechanisms as well as to invertible post-processing of additive noise mechanisms. In particular, it applies to factorization mechanisms for which the noise added to queries is correlated. This is a rather large class of mechanisms, but the reviewer is correct that it does not include all mechanisms. For example, we do not know how to do lossless private multiple release of iterative methods such as private SGD.\n\nRegarding the question about factorization mechanisms with multiple strategy matrices this is a general question that is not specific to multiple release. The situation is usually modeled by combining all strategy matrices into one. The workload matrix can be changed freely as long as it can be expressed as a matrix product LR, where R is the strategy matrix.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No. I didn't check the proofs, but the theorems make sense to me.", "experimental_designs_or_analyses": "Yes. The experiment for lossless release demonstrates the correctness of the claims.", "relation_to_broader_scientific_literature": "The method can help save private budgets in application that needs multiple releases.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths: The paper provides a solution for private multiple releases that does not require an increasing order of privacy budget. The theorem generalizing to multiple distributions is well-developed, demonstrating its practicality. Additionally, the approach helps users conserve their privacy budget. The special case of the Gaussian mechanism is particularly easy to understand.\n\nWeaknesses: The solution is limited to independently distributed mechanisms, whereas, in practice, correlated noises are widely used [A]. The paper does not address this limitation. To my knowledge, the composition of correlated Gaussian mechanisms is fundamentally different [B], and lossless multiple release may not be feasible in such cases.\n\n\n[A] Koloskova, Anastasiia, Ryan McKenna, Zachary Charles, John Rush, and H. Brendan McMahan. \"Gradient descent with linearly correlated noise: Theory and applications to differential privacy.\" Advances in Neural Information Processing Systems 36 (2023): 35761-35773.\n\n[B] Xiao, Yingtai, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. \"Answering private linear queries adaptively using the common mechanism.\" arXiv preprint arXiv:2212.00135 (2022).", "other_comments_or_suggestions": "None.", "questions_for_authors": "The application to the factorization mechanism assumes that the strategy matrix R remains the same across all releases. However, in practice, different users may require different strategy matrices. For example, in the gradient descent setting, the workload matrix A may vary due to differences in learning rates and momentum weights. How would the proposed method address the multiple release problem in such cases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pg0HgkZW2o", "reviewer": "Reviewer_Nh7s", "summary": "This paper examines the problem of multiple private data releases with varying privacy parameters, which are assigned sequentially and in arbitrary order. Compared to [LWRR'22], the authors present a simpler analysis that avoids Brownian motion techniques and explicitly provide a sampling method. Their approach extends to additive noise mechanisms whose distributions satisfy a specific convolutional property, termed convolution preorder. As an application, they propose an efficient method for gradually releasing sparse histograms with a runtime independent of the number of dimensions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments on our paper. We address the perceived weaknesses below:\n\n**W1: Relation between Algorithm 1 and the Brownian mechanism.**\nWe agree with the reviewer that Algorithm 1 can be interpreted as the Brownian mechanism combined with Brownian bridge sampling, but we would argue that it is not a trivial translation. Given the focus on ex-post $(\\varepsilon, \\delta)$-DP in [WWRR’22], it is not immediate that the Brownian mechanism as stated can be sampled in arbitrary order and that it is lossless.\n\nSecond, we believe that there is a value in deriving these results from first principles. Avoiding the language of continuous time processes makes for a less technically demanding exposition, increasing the chance that these results see real-world uptake.\n\n**W2: technical contribution.**\nWe emphasize that our Theorem 3.5 makes a statement not only for Gaussian noise but (as the reviewer points out) for any additive noise distribution satisfying Definition 1.1. There are many such distributions, including the Laplace, zero-mean Skellam, and Poisson distributions.\n\nIn an updated version of the manuscript, we include a version of Algorithm 1 for generic noise distributions. We also give privacy guarantees for the Poisson distribution, and use it as an illustrative example of lossless multiple release for discrete probability distributions (which is what can be implemented on discrete computers).", "claims_and_evidence": "The theorems appear to be correct to my best knowledge, and proofs are easy to follow.", "methods_and_evaluation_criteria": "N/A as this is mainly a theory paper.", "theoretical_claims": "The theorems appear to be correct to my best knowledge, and proofs are easy to follow.", "experimental_designs_or_analyses": "N/A as this is mainly a theory paper. The numerical evaluation looks reasonable.", "relation_to_broader_scientific_literature": "See the strength and weakness section below.", "essential_references_not_discussed": "The references look proper to me.", "other_strengths_and_weaknesses": "While the paper presents a simple and explicit method for releasing multiple DP levels of a query, its novelty compared to the Brownian mechanism in [LWRR'22] seems rather limited—though it is worth noting that [LWRR'22] studies ex-post DP, a slightly different notion than the one considered here.  \n\nFor the multiple release problem, the Brownian mechanism provides a natural way to correlate DP noise. While the authors claim to extend [LWRR'22] by allowing arbitrary release orders, this improvement appears to be a straightforward conditioning argument. Given future realizations, the noise distribution follows from a Brownian bridge, making the explicit form and sampling strategy fairly direct. Consequently, the claimed advantages of simpler analysis and explicit sampling seem rather natural, and the postprocessing and factorization theorems also follow in a straightforward manner.  \n\nThus, the main technical contribution of this work lies in its extension to convolutional preorder noise mechanisms and its application to the sparse histogram problem.", "other_comments_or_suggestions": "Post-rebuttal:  I agree that a direct and concise analysis has its merits. While I still feel the core idea is somewhat natural given the Brownian mechanism, I recognize its value in various differential privacy applications, as echoed by other reviewers.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IjpzNameTG", "reviewer": "Reviewer_XD2i", "summary": "This paper introduces a lossless multiple release mechanism for differential privacy (DP), allowing analysts with different trust levels to receive private data releases with distinct privacy guarantees. Unlike previous methods, this approach ensures that multiple releases do not accumulate unnecessary privacy loss while maintaining the same accuracy as a single release at the most relaxed privacy level. Traditional DP mechanisms operate under a fixed privacy budget, and any additional release of the same dataset typically increases cumulative privacy loss. However, real-world applications often involve multiple access levels—such as different levels of trust, security clearance, or evolving accuracy needs over time. The authors propose a model where an analyst initially receives a high-privacy (low-accuracy) release but can later receive a less private, more accurate release without paying an extra privacy cost beyond that of the latest release.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their reading and comments on our paper. We address some of the perceived weaknesses below:\n\n**W1: only applicable to Gaussian additive noise.**\nTheorem 3.5 holds for any additive noise mechanism based on a noise distribution satisfying a convolution preorder (Definition 1.1). Besides the Gaussian distribution, the Laplace, zero-mean Skellam, and Poisson distributions all meet this criterion. In an updated version of the manuscript, we include more details on sampling for general distributions and for the Poisson distribution in particular.\n\nThe exponential mechanism cannot in general be expressed as a noise additive mechanism. Whether it can be implemented to satisfy lossless multiple release is an interesting open problem.\n\n**W2: computational cost.**\nThe computational efficiency of our methods is fairly straightforward, so we did not really discuss it, but we agree with the reviewer that a discussion should be included. Since the additive noise mechanisms we consider add independent noise in each dimension, the space and time complexity of implementing it with lossless multiple release scales linearly with each dimension. We consider one-dimensional noise henceforth. To allow for releases in arbitrary privacy order, we need to store all $k$ past releases when making the $k+1$’st release. For time complexity, note that any release requires drawing one (possibly conditioned) noise sample. The time complexity of the sampling depends on the particular distribution: In the case of Gaussian noise, it always corresponds to a single sample from a Gaussian.\n\n**W3: comparing to mechanisms beyond gradual release, e.g. Renyi-DP.**\nLossless multiple release (Definition 3.1) does not rely on a fixed privacy notion but rather ensures, information-theoretically, that a set of releases contain no more information than the least private release. In particular, for any fixed $\\alpha$, we support $(\\alpha, \\varepsilon)$-RDP lossless multiple release with respect to $\\rho=\\varepsilon$.\n\n**W4: practical deployment requiring careful calibration.**\nGenerally, implementations of differential privacy require carefully choosing privacy parameters. Our contributions in this paper arguably make this easier in some contexts: If multiple releases of a statistic are to be made, we can sometimes (Theorem 3.5) do it dynamically at no cost in the privacy-utility trade-off. Not having to decide on privacy parameters up front saves resources spent on planning.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper presents a framework based on Gaussian noise mechanisms, enabling multiple DP releases while preserving accuracy and privacy guarantees.", "essential_references_not_discussed": "Yes", "other_strengths_and_weaknesses": "Strengths \nThe paper extends the concept of gradual release to a more general multiple release setting, allowing for arbitrary orderings of privacy parameters.\n\nThe proposed framework is well-supported by formal theorems.\n\nNo additional privacy cost beyond the least private release.\n\nThe paper is well-organized, with clear definitions and intuitive explanations.\n\nSupports various data types, including histograms and factorization mechanisms.\n\nWeaknesses\nThe approach is currently applicable only to additive Gaussian noise mechanisms. Requires further exploration for mechanisms like the exponential mechanism.\n\nWhile the theoretical results are strong, the experimental section is relatively limited.\n\nThe computational cost of implementing lossless multiple release is not fully analyzed. A discussion on efficiency, especially for high-dimensional data, would be useful.\n\nThe paper could benefit from a comparison with alternative privacy-preserving mechanisms beyond gradual release, such as Rényi DP-based approaches.\n\nPractical deployment may require careful calibration of noise and privacy budgets.", "other_comments_or_suggestions": "see Weaknesses", "questions_for_authors": "see Weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of lossless multiple release under differential privacy: the goal is to release noisy answers to several queries while satisfying various levels of privacy, under the following constraint: any subset of the noisy answers reveals no more information about the statistic than the least private answer in the subset. This work builds on prior results about gradually releasing noisy answers with increasing privacy budgets, significantly extending them and introducing new applications. All the reviewers are supportive and agree that this paper would be a valuable addition to ICML.
Decision: Accept (poster)