Adaptive Privacy Composition for Accuracy-first Mechanisms
Authors: Ryan Rogers
Gennady Samorodnitsky
Steven Wu
Aaditya Ramdas
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
brownian motion
composition
martingale
TL;DR: We develop privacy filters that allow an analyst to adaptively switch between differentially private mechanisms and ex-post private mechanisms with an accuracy constraint subject to an overall privacy loss guarantee.

Abstract: Although there has been work to develop ex-post private mechanisms from Ligett et al. '17 and Whitehouse et al '22 that seeks to provide privacy guarantees subject to a target level of accuracy, there was not a way to use them in conjunction with differentially private mechanisms.  Furthermore, there has yet to be work in developing a theory for how these ex-post privacy mechanisms compose, so that we can track the accumulated privacy over several mechanisms.  We develop privacy filters that allow an analyst to adaptively switch between differentially private mechanisms and ex-post private mechanisms subject to an overall privacy loss guarantee. 
 We show that using  a particular ex-post private mechanism --- noise reduction mechanisms --- can substantially outperform baseline approaches that use existing privacy loss composition bounds.  We use the common task of returning as many counts as possible subject to a relative error guarantee and an overall privacy budget as a motivating example.

Adaptive Privacy Composition for Accuracy-firt Mechanisms
Ryan Rogers
Gennady Samorodnitsky
Zhiwei Steven Wu Carnegie Mellon University
LinkedIn
Cornell University
Aaditya Ramdas Carnegie Mellon University
Abstract
In many practical applications of differential privacy, practitioners seek to provide the best privacy guarantees subject to a target level of accuracy. A recent line work by Ligett al. [ Whitchouse et al. [2022 has developed such accuracy- first mechanisms by leveraging the idea of noise reduction that adds correlated noise to the sufficient statistic in private computation and produces sequence of increasingly accurate answers. A major advantage noise reduction mechanisms is that the analysts only pay the privacy cost of the least noisy most accurate answer released. Despite this appealing property in isolation, there has not been systematic study on how use them conjunction with other differentially private mechanisms. A fundamental challenge is that the privacy guarantee for noise reduction mechanisms is (necessarily) formulated ex-post privacy that bounds the privacy loss as a function of the released outcome. Furthermore, there has yet to be any study on how ex ex-post private mechanisms compose, which allows us to track the accumulated privacy over several mechanisms. We develop privacy filters [Rogers et al. 2016 Feldman and Zrnic 202 Whitchouse al. 2023 that allow an analyst to adaptively switch between differentially private and ex ex-post private mechanisms subject an overall differential privacy guarantee.
Introduction
Although differential privacy has been recognized by the research community as the de-facto standard to ensure the privacy of sensitive dataset while still allowing useful insights, it has yet to become widely applied in practice despite its promise to ensure formal privacy guarantees. There are notable applications of differential privacy, including the U.S. Census [Abowd et al. [022] yet few would argue that differential privacy has become quite standard in practice.
One common objection to differential privacy is that it injects noise and can cause spurious results for data analyses. A recent line of work in differential privacy has focused on developing accuracy-firs: mechanisms that aim to ensure a target accuracy guarantee while achieving the best privacy guarantee [Ligett et al., 2017 Whitehouse et al. 2022 In particular, these accuracy-firs/ mechanisms do not ensure predetermined level of privacy, but instead provide ex-post privacy, which allows the resulting privacy loss to depend on the outcome of the mechanism. This is in contrast to the prevalent paradigm differential privacy that fixes the scale of privacy noise in advance and hopes the result is accurate. With accuracy- first mechanisms, practitioners instead specify the levels of accuracy that would ensure useful data analyses and then aim to achieve such utility with the strongest privacy guarantee.
However, one of the limitations of this line of work that it is not clear how ex-post privacy mechanisms compose, so if we combine multiple ex-post privacy mechanisms, what is the overall
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

privacy guarantee? Composition is one of the key properties of differential privacy (when used in a privacy-first manner), so it is important to develop a composition theory for ex-post privacy mechanisms. Moreover, how do we analyze the privacy guarantee when we compose ex-post privacy mechanisms with differentially private mechanisms?
Our work seeks to answer these questions by connecting with another line work in differential privacy on fully adaptive privacy composition. Traditional differential privacy composition results would require the analyst to fix privacy loss parameters, which is then inversely proportional to the scale of noise, for each analysis in advance, prior to any interaction. Knowing that there will be noise, the data scientist may want to select different levels of noise for different analyses, subject to some overall privacy budget. Privacy filters and odometers, introduced in Rogers et al.] [2016], provide a way to bound the overall privacy guarantee despite adaptively selected privacy loss parameters. There have since been other works that have improved on the privacy loss bounds in this adaptive setting, to the point of matching (including constants) what one achieves in a nonadaptive setting (Feldman and Zanc 2021
Whitehouse et al. 2023].
A natural next step would then be to allow an analyst some overall privacy loss budget to interact with the dataset and the analyst can then determine the accuracy metric they want to set with each new query. As a motivating example, consider some accuracy metric of a% relative error to different counts with some overall privacy loss parameters c, 6, so that the entire interaction will be (c, 6)- differentially private. The first true count might be very large, so the amount of noise that needs to be added to ensure the target a% relative error can be huge, and hence very little of the privacy budget should be used for that query, allowing for potentially more results to be returned than an approach that sets an a priori noise level.
A baseline approach to add relative noise would be to add a large amount of noise and then check if the noisy count is within some tolerance based on the scale of noise added, then if the noisy count is deemed good enough we stop, otherwise we scale the privacy loss up by some factor and repeat. We refer to this approach the doubling approach (see Section 7.1 for more details), which was also used in Ligett et al. [017)). The primary issue with this approach is that the accumulated privacy loss needs to combine the privacy loss each time we add noise, even though we are only interested in the outcome when we stopped. Noise reduction mechanisms from Ligett et al. (017)). Whitehouse et al. 2022] show how it is possible to only pay for the privacy of the last noise addition. However, is not clear how the privacy loss will accumulate over several noise reduction mechanisms, since each one ensures ex post privacy, not differential privacy.
We make the following contributions in this work:
We present a general (basic) composition result for ex-post privacy mechanisms that can be used to create a privacy filter when an analyst can select arbitrary ex-post privacy mechanisms and (concentrated) differentially private mechanisms.
We develop a unified privacy filter that combines noise reduction mechanisms - specifically the Brownian Mechanism [Whitchouse et al.) 2022] with traditional (concentrated) differentially private mechanisms.
We apply our results to the task of releasing counts from dataset subject to relative error bound comparing the unified privacy filter and the baseline doubling approach, which uses the privacy filters from Whitehouse et al. (2023].
Our main technical contribution is in the unified privacy filter for noise reduction mechanisms and differentially private mechanisms. Prior work WWhitehouse et al.. 2022] showed that the privacy loss of the Brownian noise reduction can be written in terms of scaled Brownian motion at the time where the noise reduction was stopped. We present a new analysis for the cx-post privacy guarantee of the Brownian mechanism that considers reverse time martingale, based on scaled standard Brownian motion. Composition bounds for differential privacy consider a forward time martingale and apply concentration bound, such as Azuma's 'ss inequality (Dwork et al. 2010). , so we show how we can construct a forward time martingale from the stopped Brownian motions, despite the stopping times being adaptive, not predictable, at each time. See Figure [ for sketch of how combine reverse time martingales into an overall forward time filtration.
There have been other works that have considered adding relative noise subject to differential privacy. In particular, iReduct [Xiao et al., 201T] was developed to release batch of queries subject to a relative error bound. The primary difference between that work and our setting here is that we do not

---

Privacy budget: e
Reverse filtration
Accumulated
Noise reduction
Privacy
Loss
Noise reduction
filtration
Forward
filtration
Number of mechanisms
Figure 1: Our privacy filter tracks an accumulated privacy loss over many different mechanisms (forward filtration, X-axis) and stopping when it exceeds predefined (dotted line). Each mechanism satisfies approximate zCDP (blue dot) or noise reduction mechanism (black dots). The latter itself involves several rounds of interaction in reverse filtration (red arrow) until stopping criterion based on utility is met (red box). Later queries/mechanisms can depend on past ones.
want to fix the number of queries in advance and we want to allow the queries to be selected in an adaptive way. Xiao al. [20TT] consider batch of queries and initially adds a lot of noise each count and iteratively checks whether the noisy counts are good enough. The counts that should have smaller noise are then identified and a Laplace based noise reduction algorithm is used to decrease the noise on the identified set. They continue in this way until either all counts are good enough or a target privacy loss is exhausted. There are two scenarios that might arise: (1) all counts satisfy the relative етrоr condition and we should have tried more counts because some privacy loss budget remains, (2) the procedure stopped before some results had target relative error, so we should have selected fewer queries. In either case, selecting the number of queries becomes parameter that the data analyst would need to select in advance, which would be difficult to do a priori. In our setting, no such parameter arises. Furthermore, they add up the privacy loss parameters for each count to see if it below a target privacy loss bound at each step (based on the Eggeneral sensitivity), however we show that adding up the privacy loss parameters modified the definition of differential privacy to accommodate relative error, e.g. Wang et al. [022]
be significantly improved on. Other works have
Preliminaries
We start with some basic definitions from diffcrential privacy, beginning with the standard definition from Dwork et al. 2006b]a]. We first need define what mean by neighboring datasets, which can mean adding or removing one record to a dataset or changing an entry in a dataset. We will leave the neighboring relation arbitrary, and write x, x' X to be neighbors as x x'.
Definition 2.1. An algorithm A X y (e, diifferrrntl private if, for any measurable E C y and any neighboring imputs x ~ x', Pr(A(z) E E) < e Pr(A(x') E E] + 5. If 0, we say A is e-DP or simply pure DP.
We define statistic's sensitivity as the following: A,()) max 2 (1f(()) {(x'))pp)
central actor our analysis will be the privacy loss an algorithm, which will be a random variable that depends on the outcomes of the algorithm under particular dataset.
Definition 2.2 (Privacy Loss), Let A + y be an algorithm and fix neighbors x x! in X. Let v and pr be the respective densities of A(x) and A(x') on the space y with respect some reference measure. Then, the privacy loss between A(x) and A(x') evaluated at point E y is:
p" p²(())
CA(y) 2') = log
D (1)
3

---

Further, we refer to the privacy loss random variable to be La(a,z') := (A(())); x'). When the algorithm A and the neighboring datasets are clear from context, we drop them from the privacy loss, i.e. L(v) = CAly; x,,x') and & = (A(,,,'')
Many existing privacy composition analyses leverage a variant of DP called (approximate) zero- concentrated DP (zCDP), introduced by Bun and Steinke [2016]. Recall that the Rényi Divergence of order X 2 between two distributions P and Q on the same domain is written as the following where p(-) and g(-) are the respective probability mass/density functions,
1 Dx(PIIQ) X
P(U)
log By-p
(
((v))
Since we study fully adaptive privacy composition (where privacy parameters can be chosen adap- tively), we will use the following conditional extension of approximate zCDP, in which the zCDP parameters of mechanism A can depend on prior outcomes.
Definition 2.3 (Approximate zCDP [Whtchoosee et al., (023]). Suppose A x x 2 + y with outputs in a measurable space (V, 9). Suppose p
R20 We say the algorithm A satisfies conditional ((z "aproxppoo p(z)-zCDP if. for all E Z and any neighboring datasets x', there exist probability transition kernels P', P", Q'Q""= Xxg. 9x-++ + [0, 1] such that the conditional outputs are distributed according to the following mixture distributions:
A(x;2) ~ (1- 0(=) (1)))) A(x'12) ~ (1-
2)) where for all X 2 1, DA(P"(: 2) 2)) s p(z)> and Dx(( =)) | 2)) s p(z) dz E Z.
The following results establish the relationship between zCDP and DP and the composition of zCDP.
Lemma 2.1 (Bun and Steinke (2016)). If M X - y (c, DP.. then M is 8-approximate
8² /2-2CDD. If M 6-approximate p-zCDP, then M (p + 2 log(1/8"), + -DP for 8" >
Lemma 2.2 (Bun and Steinke 2016 If M1 X + y is 61-approximate P1-2CDP and Ma X x y + y" is -p-appoox PDP in its first coordinate. then M : X + Y where ((z) (M (M) (z))) is (01 + 62)-approximan (p1 + P2)-
3 Privacy Filters
In order for to reason about the overall privacy loss of an interaction with sensitive dataset, will use the framework of privacy filters, introduced in Rogers et al. [2016). Privacy filters allow an analyst adaptively select privacy parameters function of previous outcomes until some stopping time that determines whether a target privacy budget has been exhausted. To denote that privacy parameters may depend on previous outcomes, will write Pr (z) to mean the privacy parameter selected at round n that could depend on the previous outcomes A (I), and similarly for (x)). We now state the definition of privacy filters in the context of approximate zCDP mechanisms.
Definition 3.1 (Privacy Filter). Let (An X + V)221 be adaptive sequence of algorithms such that, for all n 2 1, (. ;1:m-11) is (n( -'ppproximette Pa (Him-1)-2CDD for all y1mn- E yn-1 Let 0 and 5 2 be fixed privacy parameters. Then, a functin N y - N an (c, 8) -privacy filter if
1. for all (y1,82,...) yoU, N(y1, .2....) .) stopping time with respect the natural filtration generated by (An(I))n21, and
2. ( is (e, -ddifeereeni private where N(x) = N(A1(x), A2(x),....)
Whitehouse et al. (0233 showed that we can use composition bounds from traditional differential
privacy (which required setting privacy parameters for the interaction prior to any interaction) in the more adaptive setting, where privacy parameters can be set before each query.
Theorem Suppose (A, X - y)221 a sequence of algorithms such that, for any n 2 1,
Ap (1nn-1) is 8n (y1mm-1)) -)--pr)xxppattttee Pn (11nm-1)--2 10mmmmm))CDPPPP for all y1m-1- Let >> 0 and 8 2 0.

---

8" > 0 be fixed privacy parameters. Consider the function N R20 - N given by the following
where 5 < Emgn+1 6m(1)mm-1) for all yi, V2," and
Nyy,, U2. = inf n : c <
log
1 8"
Σ mSn+1
Pm Amlliam-1)+ 1)
Σ
Pu (0rmm-1)
m mS++1
Then, the algorithm A N is an (e, pprivaccy filter.
()) is (c, + DD,, where N(x) =- (=((A(())))))) In other words,
Ex-post Private Mechanisms
Although privacy filters allow lot of flexibility to data analyst in how they interact with a sensitive dataset while still guaranteeing a fixed privacy budget, there are some algorithms that ensure a bound on privacy that is adapted to the dataset. Ex-post private mechanisms define privacy loss probabilistic bound which can depend on the algorithm's 's outcomes, so some outcomes might contain more information about an individual than others [Ligett al., 2017 Whitehouse et al. [022]. Note that ex-post private mechanisms do not have any fixed a priori bound on the privacy loss, so by default they cannot be composed in a similar way differentially private mechanisms.
Definition 4.1. Let A : X x y + Z be algorithm and & Z y + R20 a function. We say A(: : V) is (E(- iy), -ex))-ex-post private for all y E y if. for any neighboring inputs x ~ x', we have Pr (r((((zx))) > E(A(r:)): S 5(y) for all y E y
We next define a single noise reduction mechanism, which will interactively apply sub-mechanisms and stop some time k, which can be random. Each iterate will use a privacy parameter from an increasing sequence of privacy parameters (e(m) n 2 1) set in advance and the overall privacy will only depend on the last privacy parameter (88), despite releasing noisy values with parameters e(i) for i S k. Noise reduction algorithms will allow us to form ex-post private mechanisms because the privacy loss will only depend on the final outcome. We will write M X + 3" to be any algorithm mapping databases to sequences of outputs in V, with intermediate mechanisms written as (kk) X' - y for the k-th element of the sequence and (1:kk)
- y* for the first & elements. Let be a probability measure on y, for each k 2 1 let fi be probability measure on ) and let μ² be probability measure on y" We assume that the law of (() on ) is equivalent to μa, the law of M (x) on y" is equivalent to μ², and the law of (1:kk (z) on )* is equivalent to μe for every k and every x. Furthermore, we will write L to be the privacy loss of M, ((k) be the privacy loss of (R), and [(lsk) to be the privacy loss of the sequence of mechanisms (I:k), We then define noise reduction mechanisms more formally.
Definition 4.2 (Noise Reduction Mechanism). Let M X - you be mechanism mapping sequences of outcomes and x, x' be any neighboring datasets. We say M is a noise reduction mechanism for any k 2 1, C (())
We will assume there is a fixed grid of time values (()) > (2)
(()) > O. We will typically
think of the time values as being inversely proportional to the noise we add, i.c. t(0) = (1)
where e()) 2(2) ..... An analyst will not have a particular stopping time set in advance and will instead want to stop interacting with the dataset as a function of the noisy answers that have been released. It might also the case that the analyst wants to stop based on the outcome and the privatized dataset, but in this work we consider stopping times that can only depend on the noisy outcomes or possibly some public information, not the underlying dataset.
Definition 4.3 (Stopping Function). Let A X - yoo be a noise reduction mechanism. For X, let (FF() kE)) be the filtration given by (() (z) a (A (x) : < k). A function T yo0 N is called a stopping function if for any x E X, T(x) == T(A(x)) is a stopping time with respect to (x)))))))2) Note that this property does not depend on the choice of measures μ. μ*' and pk-
We now recall the noise reduction mechanism with Brownian noise [Whitehouse al. 2022
Definition 4.4 (Brownian Noise Reduction). Let f : X + Rd be a function and (t D821 sequence of time values. Let (B()) be standard d-dimensional Brownian motion and T
)z2) be
5

---

(R + N be stopping function. The Brownian mechanism associated with f. time values )22 and stopping fimction T is the algorithm BM: X + ((0, [4) x R given by
(k), ff(x) B(((A))
BM 2
k5T(2)
We then have the following result.
Lemma 4.1 (Whitehouse et al. (2022). The Brownian Noise Reduction mechanism BM is noise reduction algorithm for a constant stopping function T(x) = k. Furthermore, we have for any
stopping function T yo + +N the noise reduction property still holds, i... C(I:T())) = C(T(x)),
Another noise reduction mechanism uses Laplace noise from Koufogiannis et al. 2017], which we consider in Appendix
2017 Ligett et al.
General Composition of Ex-post Private Mechanisms
We consider combining zCDP mechanisms with mechanisms that satisfy ex-post privacy. We consider a sequence of mechanisms (A, X - +))211 where each mechanism may depend on the previous outcomes. At each round, analyst will either an ex-post private mechanism an approximate zCDP mechanism, in either case the privacy parameters may depend on the previous results as well. We will write (z) == 8n (A1()), ... (x)) (z(z) = p(Ar(z). (z)) and E, (A, == En (An (I); (z)
An-1(z)).
Definition 5.1 (Approximate zCDP and Ex-post Private Sequence). Consider a sequence of mecha- nisms (A,) 2221 where A, X - y. The sequence (An)a21 is called sequence of approximate zCDP and ex-post private mechanisms for each round n, the analyst will select (. to be 6)(())- approximate Pal pa(-)-2CDP given previous outcomes A.(.) for n, or the analyst will select A,(() to be (E,, (-n(-) ()) 5,8 -exx-pot private conditioned on A < n. In rounds where zCDP is selected, we will simply write (,(A.();:)) O, while in rounds where an ex-post private mechanism is selected, we will set px()) 0.
We now state a composition result that allows an analyst to combine ex-post private and zCDP mechanisms adaptively, while still ensuring a target level of privacy. Because we have two different interactive systems that are differentially private, one that uses only zCDP mechanisms and the other that only uses ex-post private mechanisms, we can then use concurrent composition, see Appendix A for more details.
Theorem 2. Let E'',,'',, 8',58,88" > O. Let (An)a21 be sequence of approximate zCDP and ex-post private mechanisms. We require that the ex-post private mechanisms that are selected at each round to have ex-post privacy functions En, that do not exceed the remaining budget from é' Consider the following function N: y -> N as the the following for any sequence of outcomes (yn)n21
(yg))21 (y,)= = =inf (NzcDP((UU) ((1m-1))21)) (ooon),)Noo(()))))aee (yn)n21))
where NECDP ( (yn)nz) is the stopping rule given in Theorem 7 with privacy parameters e, E, 5,8" and N Mpoa((yn) (Un)nz) is the stopping rule where the sum of realized En (y V1.... (n-1)) values cannot go above s' nor can the sum of (y (n-1)) 1) go above 8' (see Lemma B.2 with privacy parameters
e', 8'), Then, the algorithm (-) is E 5 8' -DP, where N N(x) =N ((An(z)))21)
Although we able to leverage advanced composition bounds from traditional differential privacy for the mechanisms that are approximate zCDP, we are simply adding up the ex-post privacy guaran- tees, which seems wasteful. Next, we consider how improve on this composition bound for certain ex ex-post private mechanisms.
6 Brownian Noise Reduction Mechanisms
We now consider composing specific types of ex-post private mechanisms, specifically the Brownian Noise Reduction mechanism. From Theorem 3.4 in Whitehouse et al. [2022], we can decompose the privacy loss as uncentered Brownian motion, even when the stopping time is adaptively selected.

---

Theorem 3 Whitehouse et al. 2022 Let be the Brownian noise reduction mechanism associated with time values (1>1 and a function f. All reference measures generated by the mechanism are those generated by the Brownian motion without shift (starting at f(x)) = 0). For neighbors a! and stopping function T, the privacy loss between BM)TT())()) and BM (2x) ) is given by
)&21
(1T(()) (x,x)= [15(x') - [())1 + (((T(a))
f(x') - f(x) (T(()) [lf(x') - f()]=) Bllt
This decomposition of the privacy loss will be very useful in analyzing the overall privacy loss of a combination of Brownian noise reduction mechanisms. In Appendix Derendixxwwwwe provide more general analysis than in Whitehouse et al. [2022] to show that both the Laplace noise reduction from Ligett al. 2017) and the Brownian noise reduction Whitehouse et al. [2022] are indeed noise reduction mechanisms and give the form of the privacy loss at an adaptive stopping time.
6.1 Backward Brownian Motion Martingale
We now present key result for analysis of composing Brownian noise reduction mechanisms. Although in Whitehouse et al. [2022]. the ex-post privacy proof of the Brownian mechanism applied Ville's inequality [for proof, cf. HHwward al. 2020 Lemma I] the (unscaled) standard Brownian )
motion (B()),>o it turns out that the scaled standard Brownian motion (B(t) /t) forms backward martingale [ef. Revuz and Yor 2013 Exercise 2.16] and this fact is crucial to our analysis.
Lemma 6.1 1 (Backward martingale). Let (B(") be standard Brownian motion. Define the reverse ; u 2 t). meaning that g 5 (()) if < t.. For every real X, the process filtration g(t) = a (B(();
M == exp(AB()) /t X² (2())) 1> 0
is nonnegative (reverse) martingale with respect the filtration G (g(t). Further, any t 0, E[M(9] 1, M 1 almost surely. and [+] < 1 for any stopping time with respect to G (equality holds with some restrictions). In short, M() is an "e-value" for any stopping time T an e-value is nonnegative random variable with expectation at most one.
Let B₁ = (B(2) B₂ = -BB9))20,.... )ozo,... be independent, standard Brownian motions, with cor- responding backward martingales M1 = (M 1200 M2 = (M1 )120......... and (internal to each Brownian motion) filtrations G1 (0("))220 G2 (o0)))))0 )20.... as defined in the previous lemma. Select time values (t) )221- Let a Brownian noise reduction mechanism BM, be run using B and stopped at 71- Then ( S 1 as per the previous lemma. Based on outputs from the BM, we choose time values (t2 (k)
T)) := F1. Now run the second Brownian noise reduction BM, using Bz, stopping at time T2. Since B, B2 are independent, we still have that E[M! Fil < 1. Let F2 = ((((()) )(2n, (12)) be the updated filtration, based on which we choose time values (t(()) 121- Because B3 independent of the earlier two, at the next step, we
)221 E aBB(";
)22)))
still have ( e-values Em, where
[F2]
< 1. Proceeding in this fashion, it is clear that the product of the stopped
Em
M exp
(I)
T
2
Ts
is itself (forward) nonnegative supermartingale with respect to the filtration F (F,).21 with initial value Eg == 1. Applying the Gaussian mixture method [cf. HHwwad et al. 2021 Proposition
5]. we get that for any 7, > and with (tt:,,,) = v + log
84.
)
Pr
sup m²
2r. + &
Σ
1/T0i
<
SE ml
sE/m]
This then provides alternate way to prove Theorem 3.6 in Whitehouse et al.
2022
7

---

Theorem 4. Let (Ti):21 be sequence of functions, as in Definition 4.3 and a sequence of time values (1, [ki))21 Let BM; denote a Brownian noise reduction with statistic fi that can be adaptively selected based outcomes of previous Brownian noise reductions and has ez-sensitiity 1. We then have, for any 7, 8 > 0,
sup Pr xrwxl
(T) BM.
2 v
1
(1()a) 17 sd (
In other words, BM
(BN,1 (1:T(()))
is
(vb
Ei= 1/4
1/1 (7,6)
ex post private.
121
6.2 Privacy Filters with Brownian Noise Reduction Mechanisms
Given Lemma 6. and the decomposition of the privacy loss for the Brownian mechanism given in Theorem we will be able get tighter composition bounds of multiple Brownian noise reduction mechanisms rather than resorting to the general ex ex-post privacy composition (see Lemma B.2 in the appendix). It will be important to only use time values with the Brownian noise reduction mechanisms that cannot exceed the remaining privacy loss budget. We then make the following condition on the time values (th2) (tl²)/ that used for each Brownian noise reduction given prior outcomes
y1,-.. Un-1 from the earlier Brownian noise reductions with time values (t)
k; and stopping ) j=1
functions T; for i < and overall budget p 0
SP
(ka
21 (T.())))
ien
Lemma 6.2. Let > and consider a sequence of (BM,)n21 each with statistic fn : X - Rd. with l2 sensitivity 1, stopping function T,, and time values (th.) (t(5)) )/=)), which can be adaptively selected and satisfies 2 Consider the function N y - N U {oc} where y contains all possible outcome streams from (BM.)221 as the following for any sequence of outcomes (yn)a21:
((Un)n21)) = inf n: p:
20
(Ti()))))
Then, 8 > O, (-) is (p paoppo/g)1)))) 6DDP where N(x) = (((MM, (x))
One approach to defining a privacy filter for both approximate zCDP and Brownian noise reduction mechanisms would be to use concurrent composition, we did in Lemma B.2 in the appendix. However, this would require us to set separate privacy budgets for approximate zCDP mechanisms and Brownian noise reduction, which is extra (nuissance) parameter to set.
We now show how we can combine Brownian noise reduction and approximate zCDP mechanisms with single privacy budget. We will need a similar condition on the time values selected at each round for the Brownian noise reduction mechanisms as in ( Note that at each round either an approximate zCDP or Brownian noise reduction mechanism will be selected. Given prior outcomes y1...., 1n-1 and previously selected zCDP parameters f11 (2(1)). :Pn Pa((1in-11 at round where BM is selected we have Pr: (1)mm11) 0 or if zCDP mechanism is selected simply set kn = and
noting that
20 = 0 - we have the following condition on Pn. (1(mmm1)) and the time
values (tlf)) kn if we select a BM at round n and have overall budget p > O.
0 (ka) + pn(vin-11) Sp Σ - ((((ons-1)+ +
(T
21
21
Theorem 5. Let p > O and 8 2 O. Let (An)n21 be a sequence of approximate zCDP and ex-post private mechanisms where each ex-post private mechanism round n is a Brownian Mechanism with an adaptively chosen stopping function T,, a statistic fn with fz-sensitivity equal to 1, and
time values (tl2) )/=1 that satisfy the condition in 3h. Consider the function N: y - N as the

---

following for any sequence of outcomes (Jn)n21:
((Va))21)) = inf nnd Σ
6:(1in-1) or pr Σ
A((1)--1++ 20
sE[n+1]
iE(N]
Then for 8 > the algorithm ())()))) is 20++22200 20++2/2plog(//0", DDP, where the stopping
functiin is N(x) (((An(1))
7 Application: Bounding Relative Error
Our motivating application will be returning as many counts as possible subject to each count being within a% relative error, i.e. if is the true count and ÿ is the noisy count, require |///y| - 11 < a. It is common for practitioners to be able to tolerate some relative error to some statistics and would like not be shown counts that predetermined standard deviation to counts, but it would be advantageous to be able to add large noise large counts so that more counts could be returned subject to an overall privacy budget.
outside certain accuracy. Typically, DP requires adding
7.1 Doubling Method
simple baseline approach would be to use the "doubling method", as presented in Ligett et al. (2017). This approach uses differentially private mechanisms and checks whether each outcome satisfies some condition, in which case you stop, or the analyst continues with a larger privacy loss parameter. The downside of this approach is that the analyst needs to pay for the accrued privacy loss of all the rejected values. However, handling composition in this case turns out to be straightforward given Theorem [ due to Whitehouse et al. 2023). We then compare the 'doubling method" against using Brownian noise reduction and applying Theorem 5
We now present the doubling method formally. We take privacy loss parameters c(1) c(2)
where e(++1) (2, Similar to the argument in Claim B.1 in Ligett al. [2017], we use the /2 factor because the privacy loss will depend the sum of square of privacy loss parameters, i.e. (e) ) up to some iterate m, in Theorem
p; ) is the zCDP parameter. This means that if E* is the privacy loss parameter that the algorithm would have halted at, then we might overshoot it by v2s*. Further, the overall sum of square privacy losses will be no more than 4(E*)²² Hence, we refer to the doubling method as doubling the square of the privacy loss parameter.
7.2 Experiments
We perform experiments return as many results subject to a relative error tolerance a and a privacy budget E, 8 > 0. We will generate synthetic data from a Zipf distribution, i.e. from a density f(k) x km for a >> and & e N. We will set max value of the distribution to be 300 and a 0.75. We will assume that a user can modify each count by at most 1, so that the lo-seniitvviyy is 300 and lo -ennsitiivy
See Figure 3 in Appendix B for the data distribution we used.
In our experiments, we will want to first find the top count and then try to add the least amount of noise to while still achieving the target relative error, which we to be a 10%. To find the top count, we apply the Exponential Mechanism [McSherry and Talwar (007)] by adding Gumbel noise with scale 1/ÉEM to each sensitivity 1 count (all 300 elements' counts, even if they are zero in the data) and take the element with the top noisy count. From Cesar and Rogers [202T], we know that the Exponential Mechanism with parameter FEM is 22.//--ZDD which we will use our composition bounds. For the Exponential Mechanism, we select a fixed parameter EEM 0.1.
After we have selected top element via the Exponential Mechanism, we then need add some noise to it in order to return its count. Whether we use the doubling method and apply Theorem for composition the Brownian noise reduction mechanism and apply Theorem [o composition, need& a stopping condition. Note that we cannot use the true count to determine when to stop, but we can use the noisy count and the privacy loss parameter that was used. Hence we use the following condition based on the noisy count ÿ and the corresponding privacy loss parameter e(1) at iterate i:
1 1 < (i + 1/e09)/0 - 1/e(0) < 1 + a
and |51 > 1/e(9.

---

Note that for Brownian noise reduction mechanism at round we use time values ( = 1/(sh²)) ) We also set an overall privacy budget of (e,8") = (10, 10 100-000)))) -). To determine when to stop, we will simply consider the sum of squared privacy parameters and stop if it is more than roughly 2. 2.705, which corresponds to the overall privacy budget of E = 10 with 8" = 10 6, If the noisy value from the largest privacy loss parameter does not satisfy the condition above, we discard the result.
We pick the smallest privacy parameter squared to be (e = 0.0001 for each n in both the noise reduction and the doubling method and the largest value will change as we update the remaining sum of square privacy loss terms that have been used. We then set 1000 equally spaced parameters in noise reduction to select between 0.0001 and the largest value for the square of the privacy loss parameter. We then vary the sample size of the data in {8000, 16000, 32000, 64000, 128000) and see how many results are returned and of those returned, how many satisfy the actual relative error, which we refer to as precision. Note that if results are returned, then we consider the precision to be 1. Our results are given in Figure 2 where we give the empirical average and standard deviation over 1000 trials for each sample size.
Precision with 110,1=-08)-0P
Rewults Relurned with (10,1=-05-DD
3,000
D0M
6,925
6,000
320
6.755
300
0.500
53-
DGM
8100
11000
50700
64000
120100
8002
18:03
$2000)
66020
324930
Samsll
Sumple Size
Figure 2: Precision and number of results returned on Zipfian data for various sample sizes.
We also evaluated our approach on real data from Reddit comments from http://www.......oeee.o.oeeaaaaa aaTS225faesccce02222777722.....
data This data consists of comments from Reddit authors. To find the most frequent words from distinct authors, we take the set of all distinct words contributed by each author, which can be arbitrarily large and form the resulting histogram which has foo -sensitvivy yet unbounded fz-sensitivity. To get a domain of words to select from, we take the top-1000 words from this histogram. We note that this step should also be done with DP, but will not impact the relative performance between using the Brownian noise reduction and the Doubling Gaussian Method.
We then follow the same approach as on the synthetic data, using the Exponential Mechanism with EPM = 0.01, minimum privacy parameter e( = 0.0001, relative error a = 0.01, and overall (s= 1 = 10-6)-DP guarantee. In 1000 trials, the Brownian noise reduction precision (proportion of results that had noisy counts within 1% of the true count) was on average 97% (with minimum 92%) while the Doubling Gaussian Method precision was average 98% (with minimum 93%). Furthermore, the number of results returned by the Brownian noise reduction in 1000 trials was on average 152 (with minimum 151), while the number of results returned by the Doubling Gaussian method was on average 109 (with minimum 108).
8 Conclusion
We have presented a way to combine approximate zCDP mechanisms and ex-post private mechanisms while achieving an overall differential privacy guarantee, allowing for more general and flexible types of interactions between an analyst and a sensitive dataset. Furthermore, we showed how this type of composition can be used to provide overall privacy guarantees subject to outcomes satisfying strict accuracy requirements, like relative error. We hope that that this will help extend the practicality of private data analysis by allowing the release of counts with relative error bounds subject to overall privacy bound.
10

---

Acknowledgements
We would like to thank Adrian Rivera Cardoso and Saikrishna Badrinarayanan for helpful comments. This work done while G.S. visiting scholar at LinkedIn. ZSW was supported in part by the NSF awards 2120667 and 2232693 and a Cisco Research Grant.
References
J. M. Abowd, R. Ashmead, R. Cumings-Menon, S. Garfinkel, M. Heineck, C. Heiss, R. Johns, D. Kifer, P. Leclere, A. Machanavajjhala, B. Moran, W. Sexton, M. Spence, and P. Zhuravlev. The 2020 census disclosure avoidance system topdown algorithm, 2022. arXiv: 2204.08986.
M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography, pages 635-658. Springer Berlin Heidelberg, 2016. URL
ptttps//lindh http://innnnsssiiggrrr... com http:/aaappp/.//c http://appppp/......////33333--3 0111//99788--66--5344----
M. Cesar and R. Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 421-457. PMLR, 2021. URL aattps://proceediiii
mlr. prwss/ v132/ cete//eeaaaaaa. html
C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology EUROCRYPT 2006, pages 486-503. Springer Berlin Heidelberg, 2006a. ISBN
URL https: //www//wwwww////// iacr org/
pdf
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, TCC'06, page 265-284. Springer-Vetie Verlag, 2006b. ISBN 3540327312. doi: 10.1007/11681878_LL URL btttp://ddo.orrg/// 10t.:/00..1107111111181111111
C. Dwork, G. N. Rothblum, and P. Vadhan. Boosting and differential privacy, In 51st Annual Symposium Foundations of Computer Science, pages 51-60, 2010.
V. Feldman and T. Zmic. Individual privacy accounting via a rényi filter. In Advances in Neural Information Processing Systems, 2021. /tpptttt////pperrreiierr. htt.ppareeeeeeeeeeeerrrrrrraaaaa 47ug
R. Howard, A. Ramdas, McAuliffe, and J. Sekhon. nonnegative supermartingales. Probability Surveys, 17:257 317, 2020.
Chernoff bounds via
S. R. Howard, A. Ramdas, J. McAuliffe, and Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055 1080, 2021.
P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. volume 63, pages 4037-4049 2017. doi: 10.110991T22011726555555 URL littps://dot org/10...... 1109/ TIT. 2017. 2685505
F. Koufogiannis, S. Han, and G. J. Pappas. Gradual release of sensitive data under differential privacy. Journal of Privacy and Confidentiality, 7(2), 2017.
K. Ligett, S. Neel, A. Roth, B. Waggoner, and S. Z. Wu. Accuracy first: Selecting differential privacy level for accuracy constrained ERM. In Advances Neural Information Processing Systems, volume 30, 2017. URL htttts::/pproceeinggee http://pwoooengggoooooo.o..cc//p moa.rpps.cc.ppprr//0////i...
.dff
X. Lyu. Composition theorems for interactive differential privacy. In Advances in Neural Information Processing Systems, volume 35. pages 9700-9712, 2022. URL
https://procedding www.:ooceeeiinn....i........... wwwnnne..n..mm www..ip..c.pppppeeeee 3522555577443e555Trreeeeee22222 Paper ceweer-oooffeeeceeeee

---

F. McSherry and K. Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (F)CS'07), pages 94- 1431 2007. doi: 10.1 FOCS,2007.66 URL. http:htt:://x org/ 1109/FOCS. 2007 66
J. Murtagh and S. Vadhan. The complexity of computing the optimal composition of differential privacy. In Proceedings, Part I, of the 13th International Conference on Theory of Cryptography Volume 9562, TCC 2016-A, pages 157-175, Berlin, Heidelberg, 2016. Springer- Verlag. ISBN 978-3-662-49095-2 doi: 10.1007/978 0-1---3-622266 662-49096--9 9_ URL http:: /doii 10..00.007000000077 49062--99969997
D. Revuz and M. Yor. Continuous martingales and Brownian motion, volume 293. Springer Science & Business Media, 2013.
R. M. Rogers, A. Roth, J. Ullman, and S. P. Vadhan. Privacy odometers and fil- ters: Pay-as-you-go composition. In Advances in Neural Information Process- ing Systems, pages 1921-1929, 2016.
URL http://papers.nng wttps//pppppcccppppppp.ppa 6170-privacc--odoeeerrs and filters------- Saaeessppa-aaa pay-as---- as you- toou-go-compae composiiiooononnnn
Vadhan and T. Wang. Concurrent composition of differential privacy. In K. Nissim and B. Waters, editors. Theory of Cryptography, pages 582-604, Cham, 2021. Springer International Publishing. ISBN 778-3-030-90453-11
S. Vadhan and W. Zhang. Concurrent composition theorems for differential privacy. In Proceedings of the 55th Annual ACM Symposium Theory of Computing. ACM, jun 2023. doi: 10.1145/
3564246.3585241. URL httpt:///ooi org 2trg/10.11 10.114572F3564246 35653924
H. Wang, X. Peng, Y. Xiao, Z. Xu, and X. Chen. Differreniallyy private data aggregating with relative eгтor constraint, 2022. URL htttt::t/ooiii ott.://...000///7777000000000000
Whitehouse, A. Ramdas, S. Wu, and R. Rogers. Brownian noise reduction: Maximizing privacy subject to accuracy constraints. In Advances in Neural Information Processing Systems, 2022. http///enrrriee.ete/frrrrreee http:/oruummmd---12210117777
URL
Whitehouse, A. Ramdas, R. Rogers, and Z. S. Wu. Fully adaptive composition in differential privacy. In International Conference Machine Learning. PMLR, 2023.
X. Xiao, G. Bender, M. Hay, and J. Gehrke. Ireduct: Differential privacy with reduced relative errors. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, page 229-240. Association for Computing Machinery, 201 1. doi: 10. 145/1989323 1989348.
12

---

A Concurrent Composition
We will use concurrent composition for differential privacy, introduced by Vadhan and Wang [202] and with subsequent work in Lyu [202)) Vadhan and Zhang 2023]. in our analysis, which we define next. We first define an interactive system.
Definition A.1. An interactive system is randomized algorithm S (Q x ))" x Q + y with input an interactive history (q,y)), (92, v2), (4t,1) 91) E (2 x 3) with a query q++1 E Q. The output
of S is denoted yt+1 ~ S((g: yi Va)ie((): 9(+1)-
Note that an interactive system may also consist of an input dataset x that the queries are evaluated on, which will then induce an interactive system. In particular, we will consider two neighboring datasets (0) and (1(1), which will then induce interactive systems 5!t)) corresponding to input data (b() for E {0, 1} and é E [k.] We will use the concurrent composition definition from Lyu 2022).
Definition A.2 (Coneurrent Composition), Suppose S Sk are interactive systems. The concurrent composition of them is an interactive system CO..(S.......... .Sk) with query domain [K] x Q and response domain y. An adversary is a (possibly randomized) query algorithm ([K) x Q ) + [k] x Q. The interaction between A and COMP(S),... ,S) is stochastic process that runs as follows. first computes a pair (i1,q1) E [k] Q. sends a query q to Si, and gets the response y1- In the 1-th step, A calculates the next puir (ix, q:) based on the history, sends the t-th query qi to St, and receives yt. There is no communication or interaction between the interactive systems. Each system St can only see its own interaction with A. Let (TAA: S1, Sy) denote the random variable recording the transcript of the interaction.
We will be interested in how much the distribution of the transcript of interaction changes for interactive systems with neighboring inputs. We will say COMP(S1, ... .Sk) is (s, 0)-DP if for all neighboring datasets x (0)), x (0),, we have for any outcome set of transcripts E, we have for d E {0, 1}
[I S10)
S (b) )
E
S ef PrIIT(: s(1-b), ..... ((1-b)) E +
We then have the following result from
Lyu 2022].
Theorem 6. Let AI,..., As be k interactive mechanisms that run on the same data set. Suppose that each mechanism A; satisfies (ei, 6.)- Then COMP(A A .Ax) is (e, 8)-DP, where
e. 8 are given by the optimal (sequential) composition theorem Kairouz el al. 2017 Murtagh and Vadhan (2016).
This result is very powerful because we can consider the privacy of each interactive system separately and still be able to provide differential privacy guarantee for the more complex setting that allows an analyst to interweave queries to different interactive systems.
B
Missing Proofs and Figures
B.1 Missing Proofs from Section
We start with a simple result that states that ex-post mechanisms compose by just adding up the ex-post privacy functions. Similar to our notation for privacy filters, we will denote E,, (- ix) as the privacy loss bound for algorithm A,, conditioned on the outcomes of A1))-
Lemma B.1. Fix a sequence ō,,-.. .6, 2 O. Let there be a probability measure pn on Vn, for each n and the product measure on V1 x... Ym- Consider mechanisms An X -II-- Y - Vn
for n E [m] where each An ( (-) is (En(- W1 1), 6, -ex-post private for all prior outcomes Min-1). Then the overall mechanism Atm(()) (-) (2i=1 E,(A.()) ;)) Em 8:)-ex-post private with respect to the product measure.
Proof. We consider neighboring inputs x, x' and write the privacy loss random variable (A(())) for A in terms of the privacy losses (x)) of each A; for i E [m]
Pr La(A(x)) < Σ ((A((()):)) = Pr Σ (((A(())) < Σ (1))))))
13

---

mechanism A is Pr (r()) 2 (A)(
Because each
(E,(-
;.),6,)-ex
post
private,
we
have
or and hence
Pr
Σ ((((()))) s Σ (A)())))))
Pr
n (E(A())))E((A))))))
/E/m
11- - Pr
U (
[E[m]
Σ
Pr
iE(m)
21 8;.
ie(ml
Hence, we have Pr (CA(A())) 2 E &(A(())))) - Eie(m) 6,, as desired.
For general ex-post private mechanisms, this basic composition cannot be improved. We can simply pick & to be the same as the privacy loss LÚ at each round with independently selected mechanisms A; at each round ex-post mechanisms
[m]] We now show how we can obtain a privacy filter from a sequence of long each selected ex- ex-post privacy mechanism selected each round cannot exceed the remaining privacy budget. We will write (x) to denote the parameter ò, selected function of prior outcomes from A1 (1x). An-1(x).
and 5 0 be fixed privacy parameters. Let (An X )),21 be Lemma B.2. Let (xx)-xxxxp private conditioned on prior outcomes 9im-1 = A (x) sequence of (Em(- (-n(-;)) ;1);)),,
where for all yi we have
Σ E(Uax) Se.
Consider the function yo0 - N where
N((U))221) inf n:E= Σ E(())))) or 8< Σ
RE|ml
iE|n+1]
Then the algorithm ())(())) is (5, DD where
N(x) (2)A2))))
Proof. We follow a similar analysis in Whitehouse et al. 22033 where they created a filter for probabilistic DP mechanisms, that is the privacy loss of each mechanism can be bounded with high probability. We will write the corresponding privacy loss variables of A, to be Cn and for the full sequence of algorithms A (A1.... An), the privacy loss is denoted Lin--
Define the events
D = EEn < ((x): L1. Et, and E =: [En < N(2) C. > (2)
Using Bayes rule, we have that
Pr[D]
& Pr[D +
where the last inequality follows from how we defined the stopping function N(x).. Now, we show that Pr[E] < 6. Define the modified privacy loss random variables (Cn))ee by
E. = ff
N(x)
otherwise
14

---

Likewise, define the modified privacy parameter random variables (+;zz and (z) in an identical manner. Then, we can bound Pr the following manner.
Pr[3n S N()): fn
= Pr 3 T:: (((()())
<
Pr
An (An()))
n=1
20
Σ
E
Pr [n (An()));
Fn-1]]
8
$ E (1))
Σ
(x)
=E E
Σ (SN(()
δπ(x))
S..
as desired.
Proof of Thhorrmm 2 We will separate out the approximate zCDP mechanisms, (ARCDP) )=21 from the ex-post private mechanisms (4pc*) n21 form separate interactive systems. In this case, the parameters that are selected can only depend on the outcomes from the respective interactive system, e.g. Pm (ar) can only depend on prior outcomes to mechanisms A:CDP (ax) for n. From Theorem I we know that ArCDP A1:N.cpr(-)) (-) is (E, 8 + -D.. We denote Cpest to be the privacy loss random variable for the ex-post private mechanism at round We will also write the stopping time for the ex-post private mechanisms Noost (z). From Lemma B.2 we know that Apost
post (:) is
From Theorem we know that the concurrent composition, which allows for both A 1:N (-) (.) and
A2CDP I:N.CDe (-) to interact arbitrarily, will still be + 5 65,8+0 + 8'
DDD.
Note that although DP is closed under post-processing. ex-post privacy is not. We typically say that any post prucessing function of DP outcome is also DP with the same parameter. Our privacy analysis depends getting actual outcomes from BM, rather than a post-processed value of it. However, we also say post processing ensures that no one can compromise privacy by taking the outcome and trying learn more about the dataset. With ex-post privacy, are not trying to ensure privacy of each outcome, but rather the full interaction, so the full interaction will still be DP under any post processing of any intermediate outcomes.
Remark 1.
B.2 Missing Remarks from Section 6
We now write out some remarks regarding Theorem 4
Remark 2. We note here that the stopping time of each Brownian noise reduction is with respect to H (H(t)) where H(t) = af((x) B("); u > t). but f(x) is constant so the shifted process is equivalent to the of the non-shifted process G as defined above.
Remark 3. For the multivariate case we have B(u) = [B( nate an independent Brownian motion, and we will write the filtration Gli] to be the natu- ral reverse filtration corresponding to the Brownian motion for index We then define g(t) (B( .B(") [d] 2 t). From Lemma 6.1 have the following for all X E IR i E [d]. and 0 < <<t
where each coordi-
E Elexp(AB(()11/ x²/(2() g S
15

---

We then consider the full d-dimensional Brownian motion so that with unit vector (u[[),....
.vdd) F we have
1a g(.)
E
exp
A
B
[1]/t
21
1=1
X² vfi]2
exp
A. v00l
[
g(s)
21
[00
[0
exp
21
B.3 Missing Proofs from Section
Proof of Lemma 6.2 We use the decomposition of the privacy loss La (1:k) round for Brownian noise reduction in Theorem that is stopped at time value ( to get the following with the natural filtration (Fx (z))n21 generated by (Z))2)))2 Recall that have for the Brownian motion (B%)) DeSu used in the Brownian noise reduction
(
B
((1:k)
L(k)
21
(k)
tn
From Lemma 6.1
we have for all A E R and n 2 1 with time value tn
E
exp
(x
2 (x)
X²
F (x))
11,
where
X(2) = ((k)
21 (R)
1
We then form the following process
n (ki)
X²
M Rn)) = exp
21 (ki)
Hence, with fixed time values (th (a))
n22 for 2 we have for all X,
E
M M (k))
[F- $
We then replace (ks)ken with an adaptive stopping time functions (Ti)ign rather than fixing them in advance, in which case we rename MM (k)) as MMM We know from Lemma 6.1 that MBM is still an e-value for any n. We then apply the optional stopping theorem conclude that with the stopping time (xx) that E MBM ((a)) < 1. By the definition of our stopping time, so that EN1)
((x)
have for all A
N(
E
exp
(A-1)
1)
Σ
L
)
(n(())
< <AAA11330
i=1
2p+2 plog(1/6) get
We then À
2p
(())
Pr
Σ
I
(T(())
2 p
2 2Vplog(110) 5Q.
We then have high probability bound on the overall privacy loss, which then implies differential privacy.
16

---

Proof of Theorem 5 We will show that (I,N())) is 6-approximate p-zCDP and then use Lemma 2.1
to obtain DP guarantee stopping at N (x) as defined in the theorem statement.
We follow similar analysis to the proof of Theorem 1 in Whitchouse al. [2023] Let Pi:n and Qin denote the joint distributions of (AI...., .b.....,AA)) An) with inputs æ and x'. respectively. We overload notation and write Pi (y1....... Vv.) and Oy:......... Vn) for the likelihood of yay.... Un under input x and x' respectively. We similarly write (y Vim-1) 1) and Qn (inn-1) ) for the corresponding conditional densities.
For any n E N, we have
P1n1 -Bn)
II Pm (yo (1:m-1);
Q1n(v1 Mn)
II m=1
Qm 91-m-1).
When then show that the two likelihoods be decomposed weighted mixtures of Pl and p", as well as Q' and Q", respectively such that the mixture weights on P and Q' are at least (1 6), and for all X 2
max (P')I)) sp..
By assumption of approximate zCDP each step n, write the conditional likelihoods of Pa and Qn as the following convex combinations:
(v V1m--) = (1 - 6, (11 P) (Mn 11inn11 + ( P (Nn 11im-11: 1)s Qn Vim-1) 1) = (1 - 8n (y 1)) (yn 91mm-1) + dn (1 1) 11:n-11,
such that for all A 2 1 and all prior outcomes 11.m-1, we have both
Dx (Pa (1m--1) 1) || (- 1)) S Pro(Vimm1))
(5)
Dx (-,( Vim--1) || ( F1m=-1) S Pr Pr.(
(6)
Note that at each round, we either select an approximate zCDP mechanism or select a Brownian noise reduction, and in the latter case 6, (x) = 0 and (x) O, which then means P Pa and 2n = On at those rounds n. We will write the distribution P for any prefix of outcomes from (x))). ... (1) and similarly we will write the distribution Q1., for the prefix of outcomes from A1 ... An (x'). ). We can then write these likelihood as a convex combination of likelihoods, using the fact that Dx (1 1) S 8 for all y1, 1/.-...
Pi (Ur, ... ;n)) (1 5) II P((ddbree-1) +8P". (1i, ,Jn))
Plen (D1 (0.)
Qu = (1- - 8) II (velvree-) (Vi,"". v.)))
(8)
Q (M (M)
For any fixed 2 and &s > 1, consider the following filtration F' = (Fr)nz1 where Fr = oY% Y!), with Y/ P/ Y Pd( Yi), Y. 1ix-1~ ~ (
We will first consider the Brownian noise reduction mechanisms with time values (1 1) 1) be stopped at fixed rounds (k,))21, although not every round will have Brownian noise reduction mechanism selected with Brownian motion (B(²) Jeso- We will write out the privacy loss for the
Brownian noise reduction mechanisms stopped at rounds (kin)2) as c (1:k,) where from Theorem we have,
B (kw)
C (1:k..) _((k))
(km)
1 (k))
17

---

We
will
add the noise reduction outcomes to the filtration, so that Fr 6.1 know for all
oYY, m - (Bm)) )zkk)) From Lemma
12
EB exp
A
(1ikk)) n
Fr
(k(n
(2(kkn)
2(*+1)
E
exp
21
1.
We then replace (kt)ign with an adaptive stopping time functions (Ti)ign with corresponding stopping times (Ti(z) rather than fixing them in advance, in which case we rename Cn (I:R.,) as
CBM, and the same inequality still holds with the filtration F = oY1 ... 1= )B:)) )2)),
Note that we will call Y (f(x) D that F Fm
At rounds n where a Brownian noise reduction mechanism is not selected, we simply have 1/th (km)) = 0 and c. (1=k,)) f where
We also consider the modified privacy losses for the approximate zCDP mechanisms
P., (yal (WnlVen) 2n (yh (Ven)
C (11m)) log
where 31:m Pi
Due to mechanisms being zCDP, then have for any À E eepp ((A - 1) A(A
1))2) F S1.
Because each round n, the mechanism selected is either approximate zCDP Brownian noise reduction with a stopping function, we can write the privacy loss at each round i as the sum C + L so that for all À 2 we have
x(A) = Σ [(
& (pd())) }
CBM > (p(()im-)) C C,N
(9)
M == exp ((A- 1)x
(10)
We know that (M,) is supermartingale with respect to (Fr From the optional stopping theorem, we have
EIM (A) M( S1
This will ensure (4) holds. Although for rounds n where we select Brownian noise reduction we have PK Pn and Q' Q.. we still need to show that for rounds where approximate zCDP mechanisms were selected the original distributions Pa and Qn can be written as weighted mixtures including P'. and Q',, respectively. This follows from the same analysis in Whitehouse al. (2023), so that for all outcomes y1, -2.-..
... where E 8n (81:m-1) < we have
Pin (1 y2. 3n) 2 (1 8) II P' (ym 11im-1), 170
and similarly for Q1:-- As is argued in Whitehouse et al. 2023 it suffices to show that the two likelihoods of the stopped process PI:N and Q1.v can be decomposed as weighted mixtures of Pl. and Pl,y well as Qi.x and Q" respectively such that the weights on PlAN and Q are at least 1 - 8. Note that from our stopping rule, we haven for all À 0
E BM (A)
N(x) < = E [ A NE (CL, + < MA+13p.
We then still need convert DP, which do with the stopping rule N(x) and the conversion lemma between approximate zCDP and DP Lemma 2.1
18

---

Data Distibution
0.07
0.06
0.05
Probabilty
0.04
0.03
0.02
0.01
0.00
50
100
150
200
250
300
Element
Figure 3: Data from a Zipf Distribution with parameter a = 0.75 and max value of 300.
B.4 Data Distribution Plot from Section 7
In Section 7
we generate data from a Zipfian distribution, which we present in Figure 3
C Noise Reduction Mechanisms
We provide more general approach to handle both the Laplace and Brownian noise reduction mechanisms from Koufogiannis et al. [2017]. Ligett et al. [217]] Whitehouse et al. [2022]. Consider a discrete set of times {a with < a < We will allow the stopping time and the number
of steps to be adaptive. We will handle the univariate case and note that the analysis extends to the multivariate case. We will write time functions (d)(4), k 2 1) to satisfy the following
6(1) =b ((k), : :a XR fa60g such that (t)) 2) < for all (t, 2) E {al0) x R and k 2 2.
Consider the noise reduction mechanisms where we have M(1pp) ((1) b, ((1+)))) ((x) (((()) where (t)) is either a standard Brownian motion or Laplace process Koufogiannis et al. 2017 and for h: >> we have
((kx) (x) -MM((MM( ( ((t-
Mika) (x) = f(x) + Z(M((P))
We will then write
M (11 (x)
((M (1) ",M (M1()))) (x))
We then consider the extended mechanism Mx = (T(x), (()T))))) where T(x) is a stopping function. Hence, .M*(x (xr) takes values in X ((0, b) x where ((0,b) Rx collection of all finite sequences of the type ((+() 20)) [k)) for 1,2, and {(x) <..., (1) = b and 20) R for i [k].
Let m * the probability measure on this space generated by M (x*)) where x a point where f(**) 0. Note that x² might be a fake value that needs to be added to make the function equal zero. Let m(r) be the probability measure on this space generated by M (xx). We will then compute densities with respect to m".
19

---

Let A be measurable set in Z x ((0,b) x R) Let AQ) ? A on which the last (smallest) p-coordinate of every point is equal to alه), Then
Pr(
Σ Pr(M A
By construction, M (x) is function of (Z(t) + fzz), 5t5 Therefore, for each j. we have (x) A0) (r(( f()) b) E (MM))'(AA)))
where the set of paths is of the following form for measurable subset D E C((ab), b)) of continuous functions on [a(0), bl:
(M*) = { (v(()) : : 0..0)))) (v(1) : a S1S D
The standard Brownian motion and the Laplace process both have independence of increments, so we have the following with pa as the density for (t)
Pr((Z(() + f(x) : 0 < t S E ((v(t) : st b): (u(t): : a sts E D Pr((Z(()) + f(x) </5 E)
Pais Pato (Z(ali) - f(x))
=E {Z(() a0) sts D
Patsi Patsi (Z(ali))
E 1 (MM("*) e An) PMorana (Z(M 1.9) (Ix) f(x))
(o (Z(((( (x))))
where the second equality follows from the fact that the law of a shifted process with independent increments on (a 6)) is equivalent to the law the non-shifted process and its density is the ratio of the two densities evaluated at its left most point. We then conclude that
E 1 (x") E A} PM (x+ (Z(M((())))) [(x)) ]
Pr(M*(x) E E
Therefore m(x) is absolutely continuous with respect to m.. To write the density (the Radon- Nikodym derivative), recall that the density is evaluated some point Z ((al0) x RR),, Let ((s) be the smallest p-value in s and =()) be the corresponding space value. Then we have
dm(x). dm
(s) (=(s)(((s) f(x))
Ps (.T(1)) (s)
(=())
Similarly, we consider (zg (z) = (T(x), (x)) so that the state space is Z x 0a0 x R. We will write nn* to be the probability measure on this space generated by Mis (x*) and m(xx to be the probability measure on this space generated by (x). We then compute densities with respect to vn.
Let A now a measurable subset of E x {ali) x R and let A0) C A with the p-coordinate equal to ()) Then we follow similar argument to what we have above to show that
PM (Z (0)
Pr [M (x) A] E
{M Mast (x*) E A)
(2M
Hence, for (,2 E Z. {ali)} x IR we have
dm(x) dm=
(k,, 1, Pi(z p=(2-f(0 (x(=)((x))
D T (z)) (k, 1,
Pc(z)
We then consider the privacy loss for both M denoted as (():(())), and Mina denoted as L(T(x))
under neighboring data æ and x'. We have
PM (Z (TM 2/ f(x))
c (1:T(z)) log
PM (MM - f(x')) = c(((())
(11)
20

---

We then instantiate the Brownian noise reduction, in which case
(=(= f(x)) exp 2t (z- (= (x +
1 2² exp
[(x))
[(x)2)
2t
t
21
Without loss of generality, consider the function ((y) = f(y) f(()) so that apply
Pe(= - -(x))) - log
g(x') 19(x')| =1g(x')1 g(x')2
pz(2 -g(x²)))
2t
We then use the Brownian motion (B(1))o20 to get the privacy loss Lan
c(1:((z))
(1:T(=))
(f(x) f(x')²
[f(z) - [(x')| (f(z) f(z') (Mtrtoha)))))
f(x) f(x')
PNN
21
(f(x) f(x')²
(1f(m)) - f(z')) W (MTTO))(())
2t
where (W(1) z B())) is standard Brownian motion for ==|=
There is another noise reduction mechanism based on Laplace noise, originally from Koufogiannis al. [0177] and shown to be ex-post private in Ligett al. (2017). We first show that it indeed noise reduction mechanism with stopping function and consider the resulting privacy loss random variable. We focus on the univariate case, yet the analysis extends the multivariate case.
We construct a Markov process (X(t))220 with (() = 0 such that, for each > 0, x() has the Laplace distribution with parameter f, which has density p(=) = 21 exp (-1zl/t) for R. The process we construct has independent increments, i.e. for any 0 S ((2) < (2) < < ((k) the
following differences are independent,
((t X x(t()) ((()))x(("")))) x((())..-,X(()))) x ())
Hence, the process is Markovian. The idea of constructing such process is that a Laplace random variable with parameter is symmetric, infinitely divisible random variable without Gaussian component whose Lévy measure has density
E -1///
g(;; t)
# O.
|z|
Let U be an infinitely divisible random measure on [0, 00) with Lebesgue control measure and local Lévy density
(²;tt) = t # 0,t 0.
(12)
We define X(t) = U((O,t), f)). where & 2 O. Then (() 0 and for t > O, X() a symmetric, infinitely divisible random variable without Gaussian component, whose Lévy measure has the density equal to
L (=; 2 1 e -= g(2;t).
-11//
That is X(t is a Laplace random variable with parameter and the resulting process has independent increments by construction. Note that the process (X(t)) has infinitely many jumps near 0. On an interval (1(2), ((2)) with (1)) (22), it is flat with probability (1(2) /212)22
We can then describe the Laplace noise reduction algorithm in a way similar to the Brownian Noise Reduction.
Definition C.1 (Laplace Noise Reduction). Let f X + Red be a function and ((2)) a sequence of time values. Let (X (())za be the Markov process described above independently in each coordi- nate and T (Rdy* N be stopping function. The Laplace noise reduction associated with f. time values (+ 121 and stopping function T is the algorithm LNR X ((0, (0)) x Rdy given by
LNR(x)
LNR (NT():T())( (100), (1())(x)) [(x)) + x(((m)) AST(x)
We then aim prove the following
21

---

Lemma C.1. The privacy loss LuR for the Laplace noise reduction associated with f, time values (+(k) J22 and stopping function T can be written as
LLER
L88
((1:T(())
-L88
((((x))
Furthermore we have
(1)T(()) Lua
(x) -Xx(A) (+))
Proof. Because the Laplace process has independent increments, we get the same expression for the privacy loss as in II] where we substitute the Laplace process for [(t), which has the following density
pe(= [(s))//((=) exp (1= 1=11
We will again use g(y) f(y) f(x for neighboring datasets x, x' with f(x') > f(x without loss of generality to get
log (pr(z - (0l3-gg())//((22 g(x1))) (10) - 1-al-1z-oo 12-11=
Therefore, have from [1] that
Cim (1::(())) (x))
(TT()) (IX(MUO))))) (x)) (1)))) s(x))l)
desired.
We now want to show similar result that we had for the Brownian noise reduction mechanism in Lemma but for the Laplace process. Instead of allowing general time step functions gهه)), we will simply look at time values 0 < {(R) < <... < {()) = b so that
(1:T(()) LNR
[(T(T)) (X((TT())) - ((x)))(
This form of the privacy loss for the Laplace noise reduction might be helpful in determining whether we can get similar backward martingale as in the Brownian noise reduction case in Lemma We leave the problem open to try to get a composition bound for Laplace noise reduction mechanisms that improves over simply adding up the ex-post privacy bounds as Theorem B.1
22


Reviews:
[{"review_id": "npLBKWfJrS", "reviewer": "Reviewer_xyZp", "summary": "One of the challenges any attempt to implement DP preserving techniques, is the inherent tradeoff between the level of guaranteed privacy and accuracy levels. While most of the analysis done by privacy experts focused on the perspective of maximizing accuracy subject to an upper bound on the privacy loss, many data scientists might prefer the inverse perspective, e.i., minimizing privacy loss subject to a lower bound on accuracy.\nThis latter perspective was first formalized by [1], who referred to it as \"accuracy first\". They proposed a mechanism that releases a sequence of responses with increasing accuracy and decreasing privacy levels, which - somewhat surprisingly - pays only for the privacy loss of the last released response, which they analyze using \"ex-post privacy\". Later [2] extended these results to Gaussian noise as well using the Brownian mechanism, but since they did not rely on the classical DP notion, they lacked a composition guarantee.\n\nThe authors of the current work resolved this issue, by leveraging the privacy filter toolkit, in which privacy parameters can be adaptively chosen, under the constraint that they will not exceed some pre-defined threshold. Specifically, they use a zCDP filter for the Brownian mechanism which can be used for composing several calls to the mechanism as well as other zCDP mechanisms. They use this technique to analyze a setting where the accuracy goal is defined in terms of relative error rather than additive error, and use empirical evaluation to asses the accuracy improvement achieved by applying their analysis technique.\n\n[1] K. Ligett, S. Neel, A. Roth, B. Waggoner, and S. Z. Wu. Accuracy first: Selecting a differential privacy level for accuracy constrained erm.\n\n[2] J. Whitehouse, A. Ramdas, S. Wu, and R. Rogers. Brownian noise reduction: Maximizing privacy subject to accuracy constraints.", "questions": "I have no additional questions to the authors.", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Providing composition guarantees for ex-post privacy is an important step towered utilizing the accuracy first perspective in the real world, which can help to further extend the usage of differential privacy techniques in the real world. The background and intuition are clearly presented, the results in the body of the paper are formally stated, and the proofs are sound.", "weaknesses": "While the results presented in this paper are not just a simple application of the privacy filter technique to the ex-post privacy framework, as discussed in section 5.1, the novel results are somewhat limited in their scope, as they apply only to the zCDP privacy measure and the Brownian mechanism. The empirical evaluation is limited to a specific use case, and a single $(\\epsilon, \\delta)$ tuple (with $\\epsilon = 10$ which is higher than what is usually considered private).\n\nIn the introduction, the authors also claim to provide a basic composition theorem for arbitrary ex-post privacy mechanisms, which appears only in the supplementary material. Putting aside the fact that the result does not appear in the body of the paper, and the fact the supplementary material is not comprised of appendix but is an extended version of the paper which makes it hard to find the additions, the actual claim (Theorem 3) is somewhat hard to parse, and could probably benefit from removing the zCDP part.\n\nSmall minor comment: It seems like the two references to Whitehouse et al. papers in the abstract were mixed up. The first one should've been the 22 paper and the second the 23.\n\n=======\n\n**Edit after rebuttal discussion:**\n\nThe authors have addressed my concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We removed the basic, yet more general, composition result from the main body of the paper due to space limitations, but it states that the realized privacy parameters add up.  We wanted to highlight the more “advanced” composition bounds that allow for tighter privacy loss bounds but will include the basic composition result in the next revision.  Thank you for pointing out the mixed-up citations in the abstract; we have now corrected this.  We uploaded the full paper+appendices as a single supplement to make it easier to review one file, but in the final version, we will only have the appendices as a supplement. The application setting is meant to show that our theoretical results also improve over existing approaches significantly in practice.  As we mentioned in the general comment to reviewers, we have since ran experiments on real Reddit data and can show similar improvements over the doubling Gaussian approach that we saw on synthetic data even for $(\\epsilon = 1, \\delta = 10^{-6})$-DP.  \n"}, {"review_id": "zaFlHyj2uz", "reviewer": "Reviewer_HnZw", "summary": "This paper focuses on the study of adaptive compositions of ex-post differential privacy, where privacy guarantees depend on the outcome of the algorithm. The utilization of ex-post DP enables analysts to achieve a more favorable privacy-utility trade-off. The paper introduces a tool for composing ex-post DP and traditional DP, providing a unified privacy filter that combines the Brownian Mechanism with traditional DP mechanisms. The authors apply the proposed framework to the task of releasing counts with bounded relative error and demonstrate empirical improvements over existing methods.", "questions": "In Figure 2 left, why is the standard deviation so large? Is this expected?\n", "limitations": "This paper is theoretical and does not have potential negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The propose framework could be useful for DP practitioners to compose traditional DP and ex-post DP mechanisms. The proposed methods provide DP guarantees subject to outcomes satisfying strict accuracy requirements.\n", "weaknesses": "The presentation of this paper is not very clear to me. The first listed contribution seems to be the general composition theorem for ex-post differential privacy; however, it is only mentioned in the appendix. In the main text, I noticed a list of theorems, but there seems to be a lack of intuition provided, such as explanations on why these bounds are tight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We do not have a formal lower bound argument for why these composition bounds are tight, but they at least match the “standard” (non-outcome-dependent) privacy loss composition that depends on the variance of the noise that is added.  In traditional DP, if we add noise with standard deviation $1/\\epsilon_i$ to each count, we would expect the DP privacy loss to scale with $\\sqrt{\\sum_i \\epsilon_i^2}$, which is similar to the privacy loss composition bounds we develop that allow for noise that can depend on the outcomes. We have now added some more explanation to the paper of why we think the bounds are likely to be tight, not by proving a lower bound, but by analogy to the simpler DP advanced composition.\n\nFigure 2 seems to have a higher variance when the data is small.  This is likely due to how one typically defines “precision” — if a run of the algorithm returns no results, the precision is 100% (the error rate is zero).  Furthermore, when the sample size is small, the choice of the privacy parameter used in the Exponential Mechanism will have a larger impact on the results, as the Exponential Mechanism will likely select from many different counts with similar low counts from small datasets.  Then the Brownian noise reduction may occasionally conclude the small counts have decent relative accuracy when in fact they do not.  We think that developing an “ex-post” privacy version of the Exponential Mechanism is an important direction for future work.\n"}, {"review_id": "N9dM0Cb6zI", "reviewer": "Reviewer_hK6N", "summary": "‘Accurary-first’ mechanisms try to achieve the strongest possible privacy guarantee that satisfies a target level of accuracy. One such example is a noise reduction mechanism, which scales up the privacy cost / decreases the noise level until the target utility is achieved. Noise reduction mechanisms only pay the privacy cost of the final noise addition, but provide ex-post privacy guarantees whose composition bounds are unknown and which are not compatible with DP. This paper provides composition bounds for ex-post DP, and develops a unified privacy filter that can switch between DP and ex-post DP mechanisms subject to an overall privacy guarantee.", "questions": "The paper focuses very much on composition bounds for ex-post privacy, but I think that there should also be a discussion on post-processing. The way that Definition 4.1 isn’t defined on sets, it seems like it wouldn’t be closed under post-processing. So I think that converting this into $(\\epsilon, \\delta)$-DP is an important technical detail that should be discussed in the paper.\n\nOn a similar note — why the overloading of notation in Definition 4.1? It was unclear to me which version of ‘ex-post’ was being used throughout the remainder of the paper. And I wasn’t sure of what was the purpose of imposing a bound $\\epsilon^*$ on the ex-post privacy loss. Isn’t that just redefining DP but without sets?", "limitations": "No issues.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "1. Very interesting and strong potential for impact. Seems like it could be a big step towards making DP more practical!\n2. Novel privacy filter and analysis of the ex-post privacy guarantee for a Brownian filter.", "weaknesses": "The paper was very dense and difficult to read, which I feel limits its appeal. (Brownian motion / the Brownian mechanism, for example, are never really explained.) I think the paper would benefit greatly from being gentler to its readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "While formally introduced in Definition 4.4., we will certainly add a gentler introduction to ex-post or noise-reduction mechanisms like the Brownian mechanism to the paper. For now, an informal description is that it is a recently devised generalization of the Gaussian mechanism: one first adds a “large” Brownian motion noise (lowest utility), and decreases the noise progressively (increasing utility) until a utility-privacy tradeoff is reached; the neat fact is that the total privacy loss of the Brownian mechanism is identical to the Gaussian mechanism at the very last step of the interaction (thus being as if no interaction took place, and paying no price for the interaction). \n\nRegarding post-processing, the definition of ex-post privacy depends on the outcome of the algorithm, not outcomes falling into some set.  So if an algorithm is $(\\mathcal{E}(),\\delta)$ ex-post private, that does not mean that any post-processing function of the algorithm is also $(\\mathcal{E}(),\\delta)$, as the post-processing will likely change the outcome distribution.  In general, there is not a generic conversion of ex-post privacy to traditional DP. This is why past papers have either dealt with one notion or the other. Our paper is the first to attempt to bridge this divide and provides an overall DP guarantee even when traditional DP algorithms are used along with ex-post private algorithms.  Our results crucially rely on seeing outcomes of ex-post private mechanisms, not post-processed results, as we need to ensure the privacy loss has the correct distribution.  The analyst may then use the outcomes to determine what to do next (including post-processing it), but the analyst must receive the outcome of the Brownian noise reduction.  The overall DP guarantee of the entire transcript does not get worse if the results of the ex-post private outcomes are post-processed.  The point here is that we are not trying to ensure DP of each outcome, but rather the full interaction.  \n\nIntroducing the third parameter $\\epsilon^*$ to the ex-post private definition does not redefine DP without sets.  It is meant to ensure that the bound on the privacy loss cannot go beyond a certain amount, but the privacy loss still depends on the realized outcome of the algorithm.  This bound on the privacy loss function is important so that no outcome of the algorithm can generate a privacy loss that is very large.  Without the third parameter, $\\epsilon^*$ can be interpreted as infinity, so that the privacy loss function $\\mathcal{E}$ need not be bounded apriori.\n"}, {"review_id": "D8ISS8YYfc", "reviewer": "Reviewer_njjx", "summary": "This paper tries to tackle the following basic question in differential privacy: suppose I desire to answer as many as possible counting queries with low **relative error** with a predetermined privacy budget (\\eps,\\delta). What is the best mechanism I can use?\n\nBuilding on prior works on \"ex-post\" private mechanisms (Whitehouse et al '22), this paper makes the following contributions:\n(1) An improved analysis for ex-post privacy mechanisms (in particular the Brownian Noise Reduction Mechanism);\n(2) A \"Privacy filter\" which allows the user to compose concentrated-DP mechanisms and the Brownian mechanism adaptively.\n(3) An experimental section, demonstrating the improvement of the proposed algorithm, compared with the baseline approach of \"doubling\". It appears that, compared with the baseline approach, the new algorithm can answer twice as many queries with the same privacy budget and accuracy requirement. ", "questions": "* You conjectured the composition for ex-post mechanisms is linear in general. I was wondering why it is the case.\n* How does this ex-post private approach compare with the (private) hyper-parameter selection approach? See, for example, here: https://arxiv.org/abs/2301.00301", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The new analysis for the Brownian mechanism looks nice. It can potentially make the technique more useful.\n* The experiment setup is thoroughly described, and the improvement looks significant.", "weaknesses": "* It looks like the composition for ex-post mechanisms is omitted in the main body. However, you claimed this as one of your main contributions.\n* Why only analyze the composition of concentrated-DP mechanisms with Brownian mechanisms? This seems to make the theory less general.\n* From the practice side, this paper only runs experiments on synthetic data sets, which might not be convincing enough to a broader community.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "As stated as a general takeaway from the reviewer feedback, we will include the results on the basic, yet more general, composition for ex-post private mechanisms in the next revision.  We presented the composition of (approximate) concentrated DP mechanisms with Brownian mechanisms as we feel that is the most general version of our analysis.  In particular, any $(\\epsilon, \\delta)$-DP mechanism can be converted to an approximate zCDP mechanism and our advanced composition results (Theorem 4) crucially rely on the only ex-post privacy mechanisms being Brownian noise reductions.  We have not been able to extend this analysis for more general ex-post privacy mechanisms, so we consider that an open problem for future work, although in the meantime we do have the basic composition result.  \n\nAlthough our empirical results are only evaluated on synthetic data, we generate data from a power law distribution, frequently encountered on real datasets.  The empirical results are used to show that the theoretical results can still outperform existing approaches for various sample sizes.  Any real dataset of counts is likely to exhibit a power law distribution and the results will largely be the same on those datasets.  We verified this on Reddit data (see general reviewer comment), where we state the results that we will include in the next revision.\n\nSince we submitted, we realized that the linear general basic composition is the best one could hope for because the ex-post privacy function $\\\\mathcal{E}_i$ at round $i$ can simply be the actual privacy loss function $L_i$ with independently selected mechanisms $A_i$ at each round, which would lead to the overall ex-post privacy function being the sum of privacy losses. \n\nThank you for pointing out the work in https://arxiv.org/abs/2301.00301  as this seems to have been a separate line of work from the ex-post privacy literature, although there does seem to be some connection.  The main difference is that they define privacy loss based on the input dataset, rather than the outcome of the algorithm that is done is ex-post privacy.  Furthermore, they consider “local sensitivity” which can be drastically different between different datasets, but in our motivating example of “relative accuracy” the local sensitivity is the same for all datasets (removing one user’s data can reduce counts by at most 1 regardless of the dataset).  Lastly, their generalized PTR approach is attempting to find the “goldilocks” noise scale so that the least amount of noise is added without returning a $\\bot$ outcome.  However, the resulting scheme will still satisfy an overall DP guarantee, with predetermined privacy parameters.  There is not a clear way how this could be modified to be composed so that selecting a large noise parameter at some rounds could result in returning more results under an overall DP bound.  "}, {"review_id": "zdHBRNmEwZ", "reviewer": "Reviewer_dJHg", "summary": "This paper presents extensive background on ex-post-privacy as well as some new analysis providing a new method for leveraging this framework for the design of differentially private interactive protocols. Finally, this framework is instantiated in a method for releasing private counts while targeting an accuracy constraint.", "questions": "* IIUC, the final guarantee claimed here is epsilon, delta DP. Is this correct? If so, I think the paper could benefit from a stronger statement of this much earlier. E.g. the abstract uses ‘differentially private’ and ‘ex post private’, but the statement about an overall guarantee just uses the word ‘privacy’. This leaves a reader somewhat confused about which notion of privacy applies here.\n\n* In theorem 3, what _exactly_ do we mean by statistic and its sensitivity? IE, a Brownian motion itself has no data-dependence, but a Brownian noise reduction mechanism does. Is the notion of statistic and sensitivity we are using here something like: the Brownian noise-reduction mechanism is data-dependent, so its path is data-dependent, and the statistic is a function of the path--so for every neighboring $x, x'$, the function $f_i$ of these different paths can differ by no more than 1, _uniformly_ over the randomness in the BM? This would seem to me to be a somewhat different notion than that of usual sensitivity, where there is no randomness involved. Perhaps the term 'statistic' is intended to imply that the randomness has already been integrated out? But if so, what does this mean precisely (e.g. what would an example be)? Further, it seems like the result of Theorem 3 is independent of these statistics $f_i$, unless they are hiding in the stopping times $T_i$ somewhere? NOTE: it is possible that this $f_i$ is intended to recall $f$ of definition 4.4; but if so, I am not quite grokking this relationship--since the $f$ in definition 4.4 can, I guess, be viewed as one _particular_ statistic of the function $BM(x)$ (the limit of the expectation of the second toordinate as $t \\to 0$), but doesn't really provide any immediate pointers to generalizing this notion?\n\n* It's not necessarily clear from the presentation of the paper what relationship there is between ex-post mechanisms, noise-reduction mechanisms, and the Brownian noise reduction mechanism. Meaning, e.g. the statement in definition 4.2 seems to apply to the privacy loss random variable directly, considered as a function of both its inputs and its randomness--at least, this is how I interpret the equality in definition 2, equality of functions. If this is true, seemingly this definition would be applicable to any particular property of the functions $L$; e.g. if $\\cal{L}^{(k)}$ was $(\\epsilon, \\delta)$-DP then $\\cal{L}^{(1:k)}$ would be as well (since it is just a statement about the function $L$, and these functions are equal). But thinking about the domains and ranges, it seems like these functions take values in different spaces. So it's not clear, I suppose, what this equality means? Maybe there is a suppressed relationship to ex-post privacy?\n\n* If I read correctly the definition of $(\\cal{E}, \\delta, \\epsilon^*)$ ex-post-private (internal to definition 2) is equivalent to $(\\epsilon^*, \\delta)$ DP. Is this correct? If so, readers may find it useful to have this explicitly called out, since likely many are more familiar with DP than ex-post privacy.\n\n* Nit on eqn (4): IIUC, choosing the particular functional form here (e.g. $\\frac{1}{2 t_n^{(kn)}}$) doesn't necessarily play an enormous role--we could likely choose some 'other way' of determining how much 'budget is left' and push the same choice into Lemma 5.2 (and Theorem 4). Is this correct, or is there something fundamental about the way this function is expressed? If there is nothing fundamental, I would advocate as a reader to abstract over this function, and clarify what properties are 'actually' needed here.\n\n* Nit on conclusion of Thm 4. Can this be stated as a zCDP guarantee? Or are we doing something _specific_ that forces us to go to $(\\epsilon, \\delta)$-DP?", "limitations": "The major unaddressed limitation is the potential difficulty of designing effective algorithms which leverage this perspective and analysis. That is, it is not entirely clear how fruitful the analysis presented here will be. This paper _could_ be _extremely_ strong with some reasonable extensions, perhaps as a theory paper with associated 'mechanism design paper' that provides many instantiations of this theoretical framework to perform various privacy sensitive tasks. For this reason, the paper reads as somewhat borderline to me--potentially pointing the way to serious applications, but not quite closing the gap entirely yet.\n\nNegative social impacts not immediately applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The theoretical framework presented is quite general and seems to be very strong.\n* Though relaxed notions of privacy are used internally in mechanism design, the main results here are stated for more tradition $(\\epsilon, \\delta)$ DP.\n* The power of the theoretical framework _could_ conceviably lead to quite substantial concrete implementations and applications. ", "weaknesses": "* The generality of the analysis yields an associated weakness: for the vast majority of the main body, the precise methods of application are somewhat unclear. E.g. it is not obvious until the end of the paper that we will not literally be guaranteeing that all of our released values are withing percent, which makes the design of interactive protocols which use this style of mechanism + composition an important and more or less unstated problem space.\n\n* The point above can be restated in more direct terms: if the authors wish to see this analysis and framework have a big impact, it is probably still to much of a lift to ask the community to fill in the gaps between the abstract presentation which dominates here and concrete algorithmic implementations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review.  The goal of the paper is indeed not any particular application to be made precise. Adaptive composition bounds in DP aim to quantify the privacy loss when we make repeated, possibly dependent, private queries (and multiple queries are the norm, nobody would collect a database only so that a single private query can be made of it). The goal in this paper is to generalize the earlier bounds to include ex-post private mechanisms like Brownian noise reduction. This only expands the scope of applicability of the earlier bounds. We are intentionally application-agnostic, and the generality means the results apply to arbitrarily different settings and domains, and they can be adapted to suit the purposes of a variety of companies or situations. The relative error application we write down is a particular natural question of special interest for which the existing solutions are not satisfactory. It is true that one cannot guarantee both a desired level of privacy and a desired level of utility simultaneously, but our methods allow us to tradeoff one against the other and yet bound the privacy loss\n\nIndeed, do note that our final privacy guarantee is in terms of $(\\epsilon,\\delta)$-DP.  We will clarify this in the abstract. In theorem 3, by sensitivity of a statistic $f_i$ we mean the traditional DP definition of sensitivity, i.e. the maximum change between $f_i(x)$ and $f_i(x’)$ where $x$ and $x’$ are neighboring, no randomness included.  We will clarify this in the next revision.  Note that each noise reduction mechanism uses a single statistic $f_i(x)$ (the true answer) to add noise to and then reduces the noise added to it until some stopping condition. Definition 4.4 gives the Brownian noise reduction that applies a Brownian motion to a single statistic (function on the data).\n\nSorry for the confusion between the various privacy definitions.  Ex-post privacy mechanisms are the most general, then noise reduction mechanisms are special cases of ex-post private mechanisms.  Then the Brownian noise reduction is a specific instantiation of a noise reduction mechanism (Laplace Noise Reduction is another example of a noise reduction that ensures ex-post privacy). To help clarify, consider independent Gaussian noise with differing standard deviations $\\sigma^{(1)}, \\cdots, \\sigma^{(k)}$ that is added to statistic $f(x)$, then the privacy loss over all noisy terms $L^{(1:k)}$ would not be the same as the privacy loss $L^{(k)}$ for the last noisy term.  However, if we add noise with standard deviation $\\sigma^{(k)}$ to $f(x)$ to get $\\hat{f}$ we would get privacy loss $L^{(k)}$ and if we then add independent noise terms to $\\hat{f}$ with different $\\sigma^{(1)}, \\cdots, \\sigma^{(k-1)}$, then the privacy loss over all terms $L^{(1:k)}$ would be the same as $L^{(k)}$ (because the rest can be viewed as post-processings of $\\hat{f}$).  \n\nThe definition of $(\\mathcal{E},\\delta, \\epsilon^*)$ ex-post-privacy is not the same as $(\\epsilon^*,\\delta)$-DP.  It is important in our definition that we have both a functional bound on the privacy loss for all of its outcomes and an overall bound on how large the functional bound can get.  Ensuring the $\\epsilon^*$ bound prevents using very small noise when not enough privacy budget exists to actually return such a precise value.  This bound is required in Lemma 5.2 and Theorem 4, otherwise a returned result would surpass the remaining budget.  Theorem 4 can be formulated as an approximate zCDP privacy guarantee.  One easy way to do this is that $(\\epsilon,\\delta)$-DP ensures $\\delta$-approximate $\\epsilon^2/2$-zCDP [Bun Steinke’16].   \n"}]

Author rebuttal:
We thank all the reviewers for their thoughtful comments and helpful suggestions.  Many reviewers pointed out that the main paper should have included the basic, yet more general, composition that included zCDP and ex-post privacy mechanisms, which was instead pushed to the Supplement (where it was hard to find). We agree that the basic composition result is interesting in itself and we would have liked to include it in the main body.  We had decided to omit this result from the main body due to space limitations to focus on the “advanced” privacy loss composition as we think that is the most applicable result.  However, given the feedback, we can state the more general result in the main paper (especially if we have an extra page if the paper is accepted).  

We have since applied our results to real data, specifically Reddit comments from https://github.com/heyyjudes/differentially-private-set-union/tree/ea7b39285dace35cc9e9029692802759f3e1c8e8/data.  We construct a histogram over all words in the data (including punctuation), eliminating duplicate words from each author.  Hence, each author can contribute an arbitrary number of words, but each word can be contributed at most once.  To help simplify our experiments, we use the top-1000 words in the histogram as the domain of words.  Ideally this domain discovery step would also be done with DP, but that is not the main point of these experiments.  We then follow the same approach in our synthetic data experiments, using the Exponential Mechanism to find the top word from the set of 1000 words and either using the Brownian noise reduction or doubling Gaussian noise approach to reduce the noise until a target 1% relative error.  With a conservative $(\epsilon = 1, \delta = 10^{-6})$-DP guarantee, in 1000 independent trials, more than 95% of the results returned by both methods have the target relative error and the Brownian noise reduction returns about 40% more results than the doubling Gaussian mechanism (152 vs 109 results).  We will include these real data results in the next revision.



Meta-review: This paper addresses adaptive compositions of ex-post differential privacy, where privacy guarantees depend on the outcome of the algorithm (as opposed to being fixed in advance). These mechanisms allow the analyst to prioritize achieving a certain accuracy goal at the lowest privacy loss possible. This work adapts the notion of Renyi filter to allow composing Brownian Mechanism which is ex-post DP and traditional DP mechanims. The authors apply the proposed framework to the task of releasing counts with bounded relative error and demonstrate empirical improvements over existing methods.
Decision: Accept (poster)