Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints
Authors: Justin Whitehouse
Aaditya Ramdas
Steven Wu
Ryan Rogers
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential privacy
Brownian motion
Laplace mechanism
Gaussian mechanism
Confidence sequences
Empirical risk minimization

Abstract: There is a disconnect between how researchers and practitioners handle privacy-utility tradeoffs. Researchers primarily operate from a privacy first perspective, setting strict privacy requirements and minimizing risk subject to these constraints. Practitioners often desire an accuracy first perspective, possibly satisfied with the greatest privacy they can get subject to obtaining sufficiently small error. Ligett et al. have introduced a `"noise reduction" algorithm to address the latter perspective. The authors show that by adding correlated Laplace noise and progressively reducing it on demand, it is possible to produce a sequence of increasingly accurate estimates of a private parameter and only pay a privacy cost for the least noisy iterate released. In this work, we generalize noise reduction to the setting of Gaussian noise, introducing the Brownian mechanism. The Brownian mechanism works by first adding Gaussian noise of high variance corresponding to the final point of a simulated Brownian motion. Then, at the practitioner's discretion, noise is gradually decreased by tracing back along the Brownian path to an earlier time. Our mechanism is more naturally applicable to the common setting of bounded $\ell_2$-sensitivity, empirically outperforms existing work on common statistical tasks, and provides customizable control of privacy loss over the entire interaction with the practitioner. We complement our Brownian mechanism with ReducedAboveThreshold, a generalization of the classical AboveThreshold algorithm that provides adaptive privacy guarantees. Overall, our results demonstrate that one can meet utility constraints while still maintaining strong levels of privacy.

Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints
Justin Whitehouse Carnegie Mellon University jwhi tew.oandroee..... cmu. edu
Zhiwei Steven Wu
Carnegie Mellon University zstevenvu@cmu. edu
Aaditya Ramdas
Ryan Rogers
Carnegie Mellon University aramdas@cmu. edu
LinkedIn Sogges@linkedinn
Abstract
There a disconnect between how researchers and practitioners handle privacy- utility tradeoffs. Researchers primarily operate from a privacy first perspective, setting strict privacy requirements and minimizing risk subject to these constraints. Practitioners often desire accuracy first perspective, possibly satisfied with the greatest privacy they can get subject to obtaining sufficiently small error. Ligett al. [2017] have introduced "noise reduction" algorithm address the latter perspective. The authors show that by adding correlated Laplace noise and progres- sively reducing on demand, it is possible to produce sequence of increasingly accurate estimates of private parameter while only paying privacy cost for the least noisy iterate released. In this work, we generalize noise reduction the setting of Gaussian noise, introducing the Brownian mechanism. The Brownian mechanism works by first adding Gaussian noise of high variance corresponding to the final point of simulated Brownian motion. Then, at the practitioner's s discretion, noise gradually decreased by tracing back along the Brownian path earlier time. Our mechanism is more naturally applicable to the common set- ting of bounded fz-sensitivity, empirically outperforms existing work on common statistical tasks, and provides customizable control of privacy loss over the entire interaction with the practitioner. We complement our Brownian mechanism with ReducedA bove Threshold, generalization of the classical gorithm that provides adaptive privacy guarantees. Overall, our results demonstrate that can meet utility constraints while still maintaining strong levels of privacy.
al-
Introduction
Over the past decade, differential privacy has seen industry-wide adoption as means of protecting sensitive information [Erlingsson al., 2014, Greenberg, 2016). By injecting appropriate amounts of noise, differentially private algorithms allow the computation of population-level quantities of interest while guaranteeing individual-leva privacy. Of the private mechanisms used in industry, those relating to private empirical risk minimization (ERM) are perhaps the most impactful, in part due to their application in machine learning tasks [Abadi et al., 2016, Song et al., 2013]. Researchers have developed many private ERM mechanisms, ranging from least squares minimzation [Sheffet, 2017. Chaudhuri et al., 2011] to subsampled gradient descent [Abadi et al., 2016, Balle and Wang, 2018, Wang et al., 2019]. Despite this vast literature, most existing results take the same broad approach: they aim to minimize error (statistical risk) subject to strict privacy guarantees. While this strict adherence privacy constraints may be necessary in some applications, it often provides weak
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

utility guarantees [Fienberg et al., 2010] and can make some learning tasks impossible [Dwork et al., 2009]. Industry applications of differential privacy may desire an accuracy first perspective, setting desired risk requirements for models used in production. Privacy may still be desirable aspect of computation, but it by no means the only goal; minimizing risk may take center stage.
The main existing approach to this eccuracy-orienter perspective on privacy was given by Ligett al. [2017]. These authors introduce a noise reduction mechanism for gradually releasing a private, high-dimensional parameter. By leveraging a Laplace-based Markov process [Koufogiannis et al., 2017], they construct a mechanism for which the privacy loss of releasing arbitrarily many estimates of a parameter only depends on the privacy loss of the least noisy parameter viewed. This is in contrast results about the composition of private algorithms, in which privacy degrades according to the total number of parameters witnessed [Dwork et al., 2010, Kairouz et al., 2015, Murtagh and Vadhan, 2016]. The authors also demonstrate how to privately query the utility of observed parameters on private data by coupling their sapaace-based mechanism with A Thoeehho,,,,,, classical differentially private algorithm [Dwork and Roth, 2014, Lyu et al., 2017].
While the above mechanism provides significant privacy loss savings over a baseline method that doubles the privacy loss each round, Laplace noise is unfit for many settings in which Eg-sensitivity is used for calibrating noise. Since converting from fz-Sensitivity to & ei-sensitivity! incurs a dimension- dependent cost, it is important develop a noise reduction technique with Gaussian noise.
Contributions and paper outline. We introduce the Brownian mechanism, a novel approach for privately releasing parameter vector subject accuracy constraints. The Brownian mechanism adds correlated Gaussian noise to a risk-minimizing parameter through a Brownian motion. Noise is then iteratively stripped by moving adaptively backwards along the random walk until suitable stopping condition is met, such as meeting target accuracy on a public dataset. In Section 3, we define the Brownian mechanism and characterize its privacy loss. Using machinery from martingale theory, we construct privacy boundaries for the Brownian mechanism - upper bounds on privacy loss that hold simultaneously with high probability. In particular, the failure probability of these bounds does depend on the number of outcomes observed, overcoming seeming need for union bound faced by Ligett et al. [2017]. These privacy boundaries yield provable, probbabbbbbbtyy bounds on privacy loss under deta-dependent stopping conditions.
If private data is used to evaluate risk, then the data-dependent stopping conditions can themselves leak information. To counter this, we introduce Aovee Thresholl Section 5, a generalization of the classical show how to couple Reduced A hooeeT'rreshlle and the Brownian mechanism so that data analyst only ever incurs twice the privacy loss they would incur if they had queried accuracy on public dataset. This is in contrast to the results in Ligett et al. 20. which note that the privacy loss of A AboveTThrehher often dominates the privacy loss incurred from using noise reduction.
Throshold algorithm for privately querying accuracy on sensitive data. We
2. Release naiy parameter
End of interaction
Noise
BM
Pubic Dalaset
5. Repeat
BMG
3. scnuracy sulficiently high?
BM
f0o
"Time"
ReducedAbove Threshold on Dataset
No
1. Simllat Brownian motion started f0)
4. decresse "time" (noise variance)
Figure I: An example of running the Brownian mechanism to gradually release a statistic f f(x) First, very noisy version of the hidden parameter BM (x) is viewed. Then, loss is measured, either public dataset, or on a private dataset using a method such as AboveceddbboTThreeee loss is met, the process stops. Otherwise, noise is removed and the process repeats.
If a target
'The Ep sensitivity of f is defined sup [1f(x) (<)))lp for 2 1.

---

We empirically evaluate the Brownian mechanism and BeduucedAoveTTrresee in Section 6, finding that the Brownian mechanism can offer privacy loss savings over the Laplace noise reduction method introduced by Ligett et al. [2017]. In our view, these results demonstrate that the Brownian mechanism is practical, intuitive mechanism for meeting accuracy requirements private ERM.
Lastly we derive other new mechanisms for noise reduction, of independent interest. We generalize the Laplace process of Koufogiannis al. [2017] to continuous time in Section thus making the Laplace noise reduction mechanism of Ligett et al. [2017] more flexible and adaptive to data- dependent privacy levels. We also briefly mention noise reduction mechanism for Skellam noise in Appendix ??, discrete distribution used in count queries [Agarwal et al., 2021].
2 Preliminaries
Differential privacy, privacy loss, and ex-post privacy. An algorithm A X - y is (c, differentially private if, for any measurable set E C C and any neighboring inputs x x',
P(A(x) E E) e<P(((x') E E") +
In the above [Dwork et al., 2006], ~ denotes some arbitrary neighboring relation. Typically x ~ af indicates and x' differ in one entry, but any other relation suffices. While differential privacy has proven itself a mainstay of private computation, condition (1) is too rigid to allow data analysts to achieve minimum desired accuracy. In other words, it embraces privacy first perspective, fixing strict condition in terms of parameters and ó that must be met. We are interested in the accuracy first perspective, setting target accuracy and correspondingly optimizing privacy parameters.
The above definition of differential privacy is qualitatively focused on bounding the information- theoretic quantity of privacy loss [Dwork et al., 2006, 2010, Dwork and Roth, 2014].
Definition 2.1 (Privacy Loss). Lei A X + y be algorithm, and fix neighbors ~ x' in X. Let D² and v" be the respective densities of A(x) and A(x') the space y with respect to some reference measure?. Then, the privacy loss between A(x) and A(x") is the random variable
p (A(x))
L(x, = log
pd (A(x))
We think of A(x) as the true outcome, and C(x, x²) measures how much more likely this outcome is under the true input versus an alternative x'. Privacy loss provides probabilistic definition of privacy. Namely, is (e, probabiiiiill differentially private if, for all neighbors æ ~ x',
P ()) 6.
>
While probabilistic differential privacy is not equivalent to differential privacy [Kasiviswanathan and Smith, 2014], (c, 6) probbabiiliittlalll differential privacy implies (c, d)-differentia privacy. Prob- abilistic differential privacy emerged means for studying privacy composition, and has been leveraged in proving many results [Kairouz et al., 2015, Murtagh and Vadhan, 2016, Rogers et al., 2016, Whitehouse al., 2022]. A natural extension of privacy to the accuracy-oriented regime is ex-poxt privacy, which allows the bound in condition (2) to depend the observed algorithm output.
Definition 2.2 (Ligett et al. [2017]). Let A: X + y be an algorithm and E y - Rzo a function. We say A is (E,5) -x-xx-oostt private if. for any neighboring inputs z ~ x', we have
PP (C(xxx') > {(A(z))) <
While any algorithm trivially ex ex-post private with ((A(z) == oo, the goal is to make E(A(z)) as small possible. We describe theoretical tools for obtaining ex-post privacy guarantees in Section 3, and empirically compute the ex-post privacy distributions of various mechanisms in Section 6.
Background on Noise Reduction. Heuristically, a noise reduction mechanism allows data analyst to view multiple, increasingly accurate estimates risk minimizing parameter while only paying
For instance, if use and pa are the laws of A(z) and A(w') respectively, the reference measure can be taken be Ma + Hel.
3

---

an ex- ex-post privacy cost for the least noisy iterate observed. More formally, let M : X' + ) be any algorithm mapping databases sequences of outputs. The indices of the sequence denote the rounds of interaction, with smaller indices indicating greater noise. Let Mn X -> y give the nth element of the sequence and Mi.. + ym the first elements.
Definition 2.3 (Noise Reduction Mechanism), We say M : X + y is a noise reduction mecha- nism if. for any 2 1 and any neighboring datasets x ~ x', we have
Lim (2, x') =
where fimn(3r,a)) x') denotes the privacy loss between Min(s) and Mim(1') and xf) is the privacy loss between Mx(x) and M,(x'),
The only noise reduction mechanism in the literature uses a Markov process with Laplace marginals IKoufogiannis et al., 2017] to gradually release a sensitive parameter [Ligett et al., 2017]. As originally presented, this Laplace Noise Reduction mechanism nonadaptive, requiring data analyst to fix finite sequence of privacy parameters (G))n[K) in advance. Instead of presenting this method as background, we describe in Section 4, which we construct an adaptive generalization of this mechanism. We then leverage this generalization as a subroutine in ReducedA LirieedAbooe bove TeweeTerrehhllee a generalization of A AboveThreshold with adaptive privacy guarantees.
Background on Brownian Motion. We now provide brief background on Brownian motion, perhaps the best-known example of continuous time stochastic process [Le Gall, 2016].
Definition 2.4. A continuous time real-valued process (Bt) is called standard Brownian motion (1) Bg = 0, (2) (Be) has continuous sample paths, (3) (B.) has independent increments, i.e.
B++s Bg is independent of B, for all s,t 2 and (4) B, (0, t) for all 2 O.
We say a process (Bi) is d-dimensional standard Brownian motion if each coordinate process is an independent standard Brownian motion.
We use many properties of Brownian motion to construct the Brownian mechanism and analyze its privacy loss in Section 3. One important property of Brownian motion is that it is continuous time martingale. This property allow us to use time-uniform supermartingale concentration to characterize and bound the privacy loss of the Brownian mechanism data-dependent stopping times [Howard et al., 2020, 2021]. We do not go into detail about martingale concentration in this background section, but rather defer it to Appendix A. Additionally, (B,)220 is Markov process. This tells us that if we inspect the Brownian motion at times 0 < f1 < t2 < ... < tn. then B Bi, can be viewed as a randomized post-processing of Br, that does not depend on B, for any t1. This property allows us to show that the privacy loss of the Brownian mechanism - which adds noise to a parameter via Brownian motion- - only depends on the least noisy parameter observed.
The Brownian Mechanism: a Gaussian Noise Reduction Mechanism
The Brownian mechanism works by simulating a Brownian motion starting some multivariate parameter; this parameter should be thought of as the lisk-minimizing output there were no privacy constraints. The data analyst first observes the random walk at some large time. Then, if so desired, the analyst "rewinds" time to an earlier point on the Brownian path, reducing noise to obtain a more accurate estimate. Due to the Markovian nature of Brownian motion, the analyst will only pay privacy cost proportional to variance of the random walk at the earliest inspected time. In what follows, when refer sequence (Tw)221 of time functions, we mean sequence of functions T, (Rd)=-I + R2o such that, for all and Bi.. ERR.)..
T Tn+1(Bua) S (1(mmm-)).
(3)
X Rdd be function and (Tn)a2 sequence of time functions. Let (Bt)220 be a standard d-dimensional Brownian motion. The Brownian mechanism associated with f and (Tn)az1 is the algorithm BM : X + (Red given by
Definition 3.1. Let f X
BM(x) = (f(x) + BT. n21
where we set TT(x) ;= Ta (f(x) + BTi()). ..... f(x) + Br...(t)) with Ti (x) being constant.
4

---

We have chosen Tn, (I)) as indexing notation to denote dependence on even if this is only through observed parameters. In the context of ERM, one can think of as computing a risk minimizing parameter associated with private dataset x E X. The data analyst uses Tn along with the first iterates to determine how far to rewind time to obtain the nith iterate. Due to the Markovian nature of Brownian motion, we get the following lemma. We include proof in Appendix B for completeness.
Lemma 3.2. Let x' be neighbors. For any n 2 L, let Cin (x, denote the privacy loss between 1M (x) and (MMi((')) and CBM (,,x") the privacy loss between BM, (x) and BM, (z'). Then,
(1, x²) LBM 2').
Lemma 3.2 just tells that the Brownian mechanism is noise reduction mechanism, i.e. that the privacy lost by viewing the first n iterates is exactly the privacy lost by viewing the nth iterate in isolation. Thus, we can identify LBM (x,x'' with L (ar x²) going forward.
The Brownian mechanism, as defined above, produces an infinite sequence of parameters. In practice, data analyst will only view finitely many iterates, stopping when some utility condition has been met or minimum privacy level reached. We introduce stopping functions to model how a data analyst adaptively interacts with noise reduction mechanisms.
Definition 3.3 (Stopping Function). Let M X + y be a noise reduction mechanism. For I E X. les (Fn(z))ne (z))neN be the filtration given by Fn(x) == (M((z) : : I n).² A function N y +N is called stopping function for any I E X, N(x) == N (M (M))) is stopping time with respect to (F.(z))n21-
stopping function N is a rule used to decide when to stop viewing parameters that only depends on the observed iterates of the noise reduction mechanism. N could heuristically be "stop at the first time a parameter achieves an accuracy of 95% on a held-out dataset." a data analyst uses stopping function alongside BM, per Definition 2.3, the privacy loss accrued upon stopping is CBM ((x) (zz x²). Recall from Figure I and equation (3) that the later iterations of BM correspond to smaller noise variances, meaning that Tn is a decreasing sequence in the number of iterations n. Further, the filtration F defined above quite different from the usual filtrations considered for Brownian motions. In some cases, an analyst may want the stopping function to depend on the underlying private dataset through more than just the released parameters, e.g. they may want their rule to be "stop at the first time a parameter achieves an accuracy of 95% on the private dataset." In this case, additional privacy may be lost due observing N (x). We detail how to handle this more subtle case in Section 5.
The following theorem characterizes the privacy loss of the Brownian mechanism.
Theorem 3.4. Let BM be the Brownian mechanism associated with (Tn)n21 and function f. For neighbors x ~ w'' the privacy loss between BM (x) and BM (x') is given by
- [1f(x)- f(x')l2 (n
CBM (x, = (B,
Wr,(s)>
(x)
where (We)zg is a standard, univariate Brownian motion. Suppose f has Ez-sensitivity at most Dg- Then, letting at max(0, (0,0) a), we have
A (T(
BB C (,,x')
w
2T,
(a))
Theorem 3.4 also holds when a deterministic time is replaced by N(x), where N is stopping function. The above theorem can be viewed as a process-level equivalent the well-known fact that the privacy loss of the Gaussian mechanism has uncentered Gaussian distribution [Balle and Wang, 2018]. We prove the Theorem 3.4 in Appendix B. Given the clean characterization of privacy loss above, now show how to construct high-probability, privacy boundaries, which map the variance of BM to nigh-probabble
privacy loss bounds. We define bounds on privacy loss.
'The notation (XX) denotes the o-algebra generated by X. N is said to be a stopping time with respect to (X..) if (N < <) E oXX.. m S n) for all n E N. This definition can be extended to allow for N to depend on independent, exteraa randomization, but we omit this for simplicity.
5

---

Definition 3.5. A function vb. Rzz - Rz0 is a ò-privacy boundary for the Brownian mechanism
associated with time functions (T m21 for any neighboring datasets x', we have
P n 1: C (x, x')
(TT()))) S
Since the privacy loss BM a deterministic function of a Brownian motion, we can apply results from martingale theory to construct general families of privacy boundaries.
Theorem 3.6. Assume the same setup as in Theorem 3.4. Let ô 0 and f be a function with Ez-sensitivity 2 The following classes of functions form ô-privacy boundaries.
1. (Mixture boundary) For any p > O, x/ given by
A
2
111+ 8V P
1/
M (1)
+
2(1 + p) log
2t
2. (Linear boundary) For any b >> O such that 2ab log 1og(1/8), who given by
A
A 2 +b) A2a.
Va (1)
We prove Theorem 3.6 in Appendix B. the same appendix, we plot the boundaries in Figure 4.
Privacy boundaries serve a dual purpose for the Brownian mechanism. First, since time-unifone uniform concentration bounds are valid at arbitrary data-dependent times, that need not be stopping times with respect to the standard forward Brownian Motion filtration [Howard et al., 2021], privacy boundaries provide ex ex-post privacy guarantees. Second, in many settings, it may be more natural for data analyst to adaptively specify target privacy levels instead of noise levels. This is, for instance, the case in our experiments in Section 6. By inverting privacy boundaries, data analysts compute the proper amount noise to remove at each step to meet target privacy levels.
We make the above precise in Corollary 3.7. In what follows, when we refer to sequence (En) n2 of privacy functions, we mean sequence of functions E,, (Rd)=-1 R2o such that, for all n and Bi:n E (RRd)" E (B1m) 2 (31mn-1)
Corollary 3.7. Let be a stopping function, as in Definition 3.3. 1f is 8-privacy boundary for BM, we have
sup IP (CMM, (1, x db (Tm())())) S
awa
i.e. the algorithu BM is (T (-)), -ex post private, where (-) denotes a positional argument for an input X. Further, let (En)nz) be sequence of privacy functions, and define
Ta (m(3mm-1) = inf (t 2 0 (tt) 2 En(Bin-11)
Then BMIN(()() is (Ex 8)=ex post private, where E, (x) is defined analogously to T2 (x).
Again, N should be thought of stopping rule based on parameter accuracy. E,, should be thought of as a rule for choosing the rath privacy parameter given 1
4 An Adaptive, Continuous-Time Extension of Laplace Noise Reduction
Here, we generalize the original noise reduction mechanism of Ligett al. [2017], which will be used as subroutine in Algorithm 1 in the following section. We first describe the original Laplace-based Markov process of Koufogiannis et al. [2017]. Fix any positive integer K and any finite, increasing sequence of times (In)ne()) Let (Gn) ( be the d-dimensional process given by Ço 0 and
Cn-1 Ca-1 Lap(t.))
with probability otherwise.
Sn -==
Koufogiannis al. [2017] show that Gn ~ Lap(t,) and that (G.) is Markovian. Ligett al. [2017] use the above process to construct a noise reduction mechanism. Namely, they define the

---

the Laplace Noise Reduction mechanism associated with f : X - R and (tn)ne(K] to be the algorithm LNR: X' - (K given by LNR(2) := (f(z) + (...... (z) + (1). If Ai/en. then releasing nth component L,R,, (x) in isolation equivalent to running the classical Laplace mechanism with privacy level 6n.
We now extend the process (Gn)ne[k] to continuous time process with the same finite dimensional distributions. Let 7) > be arbitrary, and let (Pt) be an inhomogeneous Poisson process with intensity function A(t) == 2. For n 2 I, let Tn in 2 n P. 2 n be the rath jump of (Pt)ezn
and set To :- 1). Noting that Pt must be a nonnegative integer, define the process (Ze)1zn by
P
Ze = Σ Lap(Tx).
(5)
R=U
is immediate that (Ze)e2n is Markovian. We show Appendix D that Z, Tap(t). With (Z))2m one can make LNR. fully adaptive, meaning that the times (En)ne[k] at which it is invoked need not be prespecified, and can depend on the underlying input database x by using time functions.
Definition 4.1. Let f X Rdd be a function and (Tn)a21 a sequence of time functions. Let (Z))2n be the process defined in Equation (5). The Laplace noise reduction mechanism associated with f and (Ta)a21 is the algorithm LNR : X + (Re))oc given by
LNR(x)= = (f(x) + Zrr(z)) n21
where again
+ Z (Tz) ................................ f(x) + ZT. (a)).
the analyst would prefer instead to specify privacy functions (En)221, they can do so by leveraging the corresponding time functions (1) A / (x). where (x) is defined analogously to
Ta (z)). We leverage LNR in our experiments in Section 6 and the process (Zz )220 as a subroutine in
constructing ReducedAbove wow.boorresoolee LNR admits the following trivial ex-post privacy guarantee.
Proposition 4.2. Let LNR be associated with (Tn)a21 and a function f with l -eesiivivvvyyy A1. If N is stopping function, the algorithm (N is (A)/TT())))) -x- post private.
Skellam Noise Reduction. Last, we briefly discuss how to generate noise reduction mechanism for Skellam noise [Agarwal al., 2021]. Recall that random variable X has a Skellam distribution with parameters Xı and Xy if X =a Y1 - Y2, where Y1 ~ Poisson(Ay, A1) and Y2 ~ Poisson (A2) are independent Laplace random variables. For succinetness, we write
Skell(A) .2))
Let (Pi (t)) and (P2())) be two independent, homogeneous Poisson process with rates A and X2 respectively. Observe that the continuous time process (X1)120 given by x Pi (t) P2(() is clearly Markovian, has independent increments, and has X; ~ Skell(t),, tA2). Thus, (X))22 can be used define Skellam noise reduction mechanism by releasing (f(x) +x)x(=))>>1 for some sequence of time functions (Tn (21)
5 Privately Checking if Accuracy is Above Threshold
In Section 3 we presented the Brownian mechanism, characterized its privacy loss, and showed how to obtain ex- ex-post privacy guarantees for arbitrary stopping functions. In particular, these stopping functions could be based on the accuracy of the observed iterates on public held-out data.
However, one may desire to privately check the accuracy of observed iterates on the dataset E X. Ligett et al. [2017] were able to accomplish this goal by coupling LNR with Thoeshhreh a classical algorithm for privately answering threshold queries [Dwork and Roth, 2014]. In the context of ERM, AboveThreehoold iteratively checks if the empirical risk of each parameter is below a target threshold, stopping at the first such occurrence. The downside to AboveTThresil Threshold is that it requires a prefixed privacy level. In empirical studies, Ligett et al. [2017] found this fixed privacy cost dominated the ex-post privacy guarantees, showing little benefit using noise reduction.
bove Aove hoveThreshold. a generalization of Above Thresholl which pro- vides ex-post privacy guarantees. We show how couple BM with Reduced A boveTT Threshold to obtain tighter ex ex-post privacy guarantees than coupling with Aboveohreshold would permit. In particular, if BM is run using parameters (En)m21 and ReducedAbove bove Threshold indicates the Ntth
Below, we construct ReducedA
7

---

parameter obtains sufficiently high accuracy, the privacy loss of the net procedure will be at most 2EN only twice the privacy loss that would be accrued by testing on public data.
Algorithm 1 RReducedAbovveThrsshlll (via Laplace Noise Reduction)
Require: Algorithm Alg X + y parameter emax O, threshold database I E X' utility u D x X + where u(3,-) -) is A-sensitive v3, privacy functions (En)x21 with En S émax Vn.
for 2 do
en == (Alggmmm (x)),
0 Tn == 24/en
Sn == ZI,, where (Z)) 1nn 2n in Eq. (5) defines the LNR mechanism with 17 2A/Emaxx Emax
En ~ Lap 4A
if (Alg,, (z). x) + En 2 T + Sn then
Print and HALT
else
Print 0
r should be seen as target accuracy, Alg as a mechanism for releasing a parameter (e.g. BM, LNR), and u as evaluating the accuracy of Alg, (I) on 6max is an arbitrarily large constant, representing the minimum level of privacy required, used to prevent the user from examining (Z,) at arbitrarily small times. The above generalizes sequences of thresholds (7n)n21 and sequences (un) of functions un : ) x X IR that are A-sensitive in their second argument, but the added generality yields only marginal benefits. When e, for all Algorithm I recovers Above'TThre T'resholdd as special case. The intuition behind ReducedA boveeorrssool is that by gradually removing Laplace noise from the threshold, data analyst ensure that privacy of the whole procedure only depends on the magnitude of Laplace noise added when the algorithm halts. The following characterizes the privacy loss of Algorithm!
Theorem 5.1. For any n 21 1 and neighboring datasets x ~ x', let L (r. x²) denote the privacy between Alg (x) and Alg (z)). For any X. define Nxx) to be the first round where ReducedA bove Threshold run on input x E X outputs 1. that is
(x)) == infin 2 1:
=
Then, the privacy loss between ReducedAAboveThresbbo denoted CRAT (I, x²), is bounded by
and Rednced/Abore
CRAT (z, x') CÅls (z, x') + EEN()) (ABg:
We prove Theorem 5.1 in Appendix C, where we also provide a utility guarantee for ReducedAAboel www.bbooeerrrolleee Aboveohreehood, is in practice weak as it derives from union bound. Using Theorem 5.1, we can simply choose Alg = BM as means of adaptively generating parameters. The following corollary, which follows immediately from the above theorem, provides the ex ex-post privacy guarantees of combining Reduced A A Threshold and BM.
This utility guarantee, much like the utility guarantee for
Corollary 5.2. Let BM be the Brownian mechanism associated with a function f. decreasing time functions (Ta)n21, and 8-privacy boundary v.. Let AaadneedAAooveThreehha be run with privacy functions (TT(T)))2) threshold t, and algorithm BM. Then, Reduced A hooeeThreshole is (2))))))))) -ex post private.
Experiments
We compare the performance of BM and LNR on the tasks of regularized logistic regression via output perturbation [Chaudhuri et al., 2011] and ridge regression via covariance leveraged the KDD-99 dataset [KDD,
Choice of tasks:
perturbation [Smith et al., 2017].* 4 For logistic regression, 1999] with d = 38 features, predicting whether network events can be classified as "normal" or "maliciouss. For ridge regression, we used the Twitter dataset [Kawala al., 2013] with d 77
"The two tasks use the logistic loss fly, 2) ;= log(1 + expp --x)) and the squared loss Elv, 2) == [ 2)
The regularized loss on dataset D> {(., (e) is L(8, D) = E.n E(v, 8 amaln
8

---

USR
0.50
0.44
0.000
L055
0.15
0.000
0.055
0.41
0020
0.6
3.2
02
2.4
1.0
1.2
Privacy Loss
Privacy Loss
(a) Regularized Logistic Regression
(b) Ridge Regression
Figure 2: Privacy loss plotted against loss (respectively regularized logistic and ridge loss) for the statistical tasks of regularized logistic regression and ridge regression.
Medhanism
Mechar Sm
LNF
3.5
2.0
1.0
1.0
05
H80
Heli
Abous Threshol toducestoove/Tweeeee Stopping Mechensm
Stogo rg Rechanam
(a) Regularized Logistic Regression
(b) Ridge Regression
Figure Empirical privacy loss distributions for logistic regression and ridge regression with loss assessed either (left) the training data treated public, held-out dataset, (middle) via Thosshhreshold, or (right) via ReducedA boveeddAhooeTehhhhoo..
features to predict cog-popularity posts. In each case, we ran our experiments on n = 10, 000 randomly sub-sampled data points. In order to guarantee bounded sensitivity, normalized each data point to have unit & norm. We note that this aspect differs from the experimentation conducted by Ligett et al. [2017], who normalized by the maximum &2 norm, non-private operation.
For each task, we conducted two experiments. We discuss the specific parameter settings for these experiments in Appendix E. In the first experiment, plotted guaranteed (in the (in the case of BM) privacy loss on the x-axis against average loss (either logistic ridge) the y-axis. We conduct such comparison probability privacy loss bounds cannot be provided for the Gaussian mechanism. Likewise, adding probability 5 of minimally improves privacy loss for the Laplace mechanism. We computed the average loss curve for each mechanism over 1,000 trials, and have included point-wise wise valid 95% confidence intervals.
Experiments:
case LNR) or
In the second experiment, we plotted the empirical privacy loss distributions for BM and LNR under the stopping conditions of loss being at most 0.41 for logistic regression and 0.025 for ridge regression. For each mechanism, we evaluated this empirical distribution using three approaches for testing empirical loss: treating the training data as held-out dataset, using AboveThreshold, and using mechanism, BeeduueedAbooeTTrrehsolo Threshold. In Above Threshold, we set the privacy parameter to be fixed at e = 0.5. In ReducedA Abvee booeTThreshol. we took the sequence of privacy parameters to be the same the sequence of privacy parameters used by B.M and LNR. We once again computed these empirical distributions over 1,000 runs of each mechanism.
The findings of the two experiments are summarized in Figure 2 and Figure 3. For both tasks, BM obtains significant improvements loss over LNR near the privacy loss level that was optimized for. For both tasks, the privacy loss distribution for BM has lower median privacy loss than that of LNR. addition, the privacy loss distribution for BM is more tightly concentrated around the median, indicating more consistent performance. The privacy loss distribution for LNR has
Findings:

---

heavy tail, demonstrating that many runs do not attain the target loss until high privacy loss costs are incurred. Comparing SeettreedAooveTrreehooooe loss distribution for Reduced A AbveeThreshoe Threshold has higher variance than that of A AboveThrrehold. However, Reduced Above AboveThhrehool attains a significantly lower median level of privacy loss when coupled with BM. This latter point reflects the observations of Ligett et al. [2017]. who note that when AboveTTue Threshold is used to determine stopping conditions on private data, it contributes the bulk of the privacy loss to the empirical distributions. On the other hand, our figures demonstrate that ReducedA Thoeehhreo results in a more mild privacy loss at target stopping conditions.
and AboveThreshold we see that the privacy
7 Conclusion
In this paper, we constructed the Brownian mechanism (BM), a novel approach to noise reduction that adds noise to a hidden parameter via Brownian motion. We not only precisely characterized the privacy loss of the Brownian mechanism, but also bounded it through applying machinery from continuous time martingale theory. We then demonstrated how the utility of the iterates produced by BM can be assessed on private data via ReducedA bovee AboveThreshold algorithm. This was itself accomplished by continuous tiimmumeussssuueeeeeeee generalization of the original Laplace noise reduction (LNR) mechanism. Last, we empirically demonstrated that BM outperforms LNR on common statistical tasks, such as regularized logistic and ridge regression.
a generalization of the classical
We comment on several limitations and open problems related to our work. We considered noise reduction mechanisms in the setting of one-shot privacy, in which only single mechanism is run on private data. Traditional composition results, such as those for fixed privacy parameters [Dwork et al., 2010, Kairouz et al., 2015, Murtagh and Vadhan, 2016] or adaptively selected parameters [Rogers et al., 2016, Feldman and Zrnic, 2021, Whitehouse et al.. 2022] are not directly applicable to algo- rithms satisfying ex- ex-post privacy; additional machinery needs to be developed to handle composition in this case. A naive approach to composition is possible, which involves summing the ex- post privacy guarantees of composed algorithms and summing the corresponding d's, but we expect this approach to be loose. Finally, noise reduction is currently only applicable to output perturbation methods; it remains open to see how to combine noise reduction with other prominent methods for private computation, such as objective perturbation.
Acknowledgements
AR acknowledges support from NSF DMS 1916320 and an ARL IoBT CRA grant. Research reported in this paper was sponsored in part by the DEVCOM Army Research Laboratory under Cooperative Agreement
(ARL IoBT CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
ZSW and JW were supported in part by the NSF CNS2120667, a CyLab 2021 grant, a Google Faculty Research Award, and Mozilla Research Grant.
JW acknowledges support from NSF GRFP grants DGE1745016 and DGE2140739.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016.
Naman Agarwal, Peter Kairouz, and Ziyu Liu. The skellam mechanism for differentially private federated learning. Advances in Neural Information Processing Systems, 34, 2021.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. International Conference on Machine Learning, pages 394-403. PMLR, 2018.
10

---

Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Cynthia Dwork and Aaron Roth. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 93344)211-407, 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pages 265-284, 2006.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 381-390, 2009.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2010.
Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages 1054-1067, 2014.
Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a Rényi filter. Advances in Neural Information Processing Systems, 34, 2021.
Stephen Fienberg, Alessandro Rinaldo, and Xiaolin Yang. Differential privacy and the risk-utility tradeoff for multi-dimensional contingency tables. In International Conference on Privacy in Statistical Databases, pages 187-199. Springer, 2010.
Andy Greenberg. Apple's 'differential privacy' about collecting your data but not your data.
Wired Magazine, 2016.
Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257 - 317,, 2020.
Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, non-
parametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055 1080, 2021.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International Conference on Machine Learning, pages 1376-1385, PMLR, 2015.
Shiva Kasiviswanathan and Adam Smith. On the 'semantics' of differential privacy: a Bayesian formulation. Journal of Privacy and Confilentiality, 6(1), 2014.
Emilie Kaufmann and Wouter M Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246): 1-4,, 2021.
François Kawala, Ahlame Douzal-Chouaker Eric Gaussier, and Eustache Dimert. Prédictions d'activité dans les réseaux sociaux ligne. In 4ième Conférence Sur les Modèles et L L'analyse des Réseaux: Approches Mathématiques et Informatiques, page 16, 2013.
KDD. KDD cup 1999 data, 1999.
Fragkiskos Koufogiannis, Shuo Han, and George Pappas. Gradual release of sensitive data under differential privacy. Journal of Privacy and Confidentiality, 7(2), 2017.
Jean-François Le Gall. Brownian motion, martingales, and stochastic calculus. Springer, 2016.
Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Wu. Accuracy first: Selecting differential privacy level for accuracy constrained ERM. Advances in Neural Information Processing Systems, 30, 2017.
Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proc. VLDB Endow., 1066):637-648, Feb 2017.

---

Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, pages 157-175. Springer, 2016.
Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: pay-as-you-go composition. In Advances in Neural Information Processing Systems, volume 29.
Curran Associates, Inc., 2016.
Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pages 1105-1114, PMLR, 2017.
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. interaction necessary for distributed private learning? In 2017 IEEE Symposium on Security and Privacy (SP), pages 58-77. IEEE, 2017.
Shuang Song, Kamalika Chaudhuri, and Anand Sarwate. Stochastic gradient descent with differen- tially private updates. In 20/3 IEEE Global Conference on Signal and Information Processing, pages 245 248. TEEE, 2013.
Jean Ville. Etude critique de la notion de collectif. Bull. Amer. Math. Soc, 45(11):824, 1939.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR, 2019.
Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Zhiwei Steven Wu. Fully adaptive composi- tion in differential privacy. arXiv preprint arXiv:2203. 255444,0 2022.
12


Reviews:
[{"review_id": "QOynWzqWGgy", "reviewer": "Reviewer_zDCJ", "summary": "The paper introduces a Brownian mechanism for private release, in which an analyst (1) generates a sequence of noise values from a Brownian process up until a certain large time point, (2) starting from this large time point, takes steps back until they find a noise value which incurs acceptable utility, and (3) releases the data with noise at the identified time point. Because of the Markov properties of the process, the privacy loss of such mechanism only depends on the final noise value output. The authors show two ways to compute the epsilon-guarantee of the resulting mechanism in terms of ex-post privacy. Next, the authors extend the existing Laplace-based Markov process mechanism to continuous time. In the final part of the theoretical sections of the paper, the authors introduce a ReducedAboveThreshold mechanism for deciding when to stop the Brownian (or another noise reduction) mechanism when the utility has to be computed on private data. In this algorithm, the utility with added Laplace noise is compared against a noisy threshold, with threshold noises coming from a Laplace-based Markov process which is synchronized with the main (e.g., Brownian) process. Finally, the authors conduct two experiments on private release of the logistic regression parameter vector, and ridge regression via covariance perturbation, finding that the Brownian mechanism on average results in lower privacy loss at the same level of utility threshold, and the privacy loss is more consistent.", "questions": "* How does the proposed mechanism relate to the prior work on fully adaptive composition? Can the results be re-analyzed in the framework of fully adaptive composition?\n* In the experiments, are comparisons of guaranteed privacy loss and high-probability loss fair? How is the privacy loss computed in the experiments (using Theorem 3.6?).\n* Is the continuous-time extension of Laplace-based Markov process mechanism necessary for Algorithm 1? \n* Is there a reason that the Algorithm 1 settles when finding any noise level within the utility threshold, if it seems that it could proceed to actually do the minimization of privacy loss?", "limitations": "The limitations are discussed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper deals with a useful setting in modern data analysis, in which an analyst might want to adaptively pick the best privacy level subject to accuracy constraints. The paper proposes two tools (Brownian mechanism and ReducedAboveThreshold) which formalize an iterative interactive procedure in which the analyst tries several noise levels before settling with a satisfactory one. Unlike the previous work on Laplace-based process mechanism, the proposed Brownian mechanism is calibrated to L2 sensitivity, thus suitable to multi-dimensional vectors. I believe this is a useful contribution to the field, given that the results are correct (I have not verified the proofs.)\n\nThe main issue with the paper is clarity. The notation is obtuse with the generic time functions $T$ which have an unclear definition, stopping functions $N$, privacy boundary functions $\\psi$, privacy functions $\\mathcal{E}$. It took a lot of time and effort to parse. The intended meaning of some functions only become clear at a much later point after its introduction, such as $T_n$ by line 211. In general, the generality of exposition is a hindrance. Corollary 2.7, if I understand the intention correctly, would be better as two algorithms for two usage scenarios (accuracy-first and privacy-first). Section 3 seems to be disconnected from the rest of the text. It is also not fully clear if the results of the paper cannot be achieved using the tools of fully adaptive composition. In the experimental section, although the results are convincing, it is unclear if the comparison of guaranteed privacy and high-probability privacy is fair, and how exactly is the empirical privacy loss computed.\n\nAs ERM is a motivation of the work, it would be interesting to see how the output perturbation with BM compares to objective perturbation at the same accuracy levels.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9KOQudDLoiv", "reviewer": "Reviewer_4Xi3", "summary": "This paper generalizes and improves the framework Ligett et al. for releasing a private\nquery subject to accuracy constraints. In this framework, a query is released\nwith gradually less noise until a desired accuracy constraint is met, and the\nprivacy cost is the cost of the last output.\n\nThey noise the query with a continuous\ndistribution specified by Brownian motion, allowing the fully-adaptive release\nof the query where even the desired epsilon values are allowed to depend\nprevious outputs. Their Brownian Motion Noise Reduction offers improved \nperformance over the Laplace Noise Reduction, the previous state of the art.\n\nFinally, they generalize NoisyAboveThreshold to allow adaptive values of\nepsilon. Combined with the previous results, this enables the accuracy\nconstraints to also depend on the the private database.\n", "questions": "Definition 3 does not make sense. What does the symbol $\\sigma$ mean here? Furthermore,\nwhat precisely is a stopping time with respect to a sequence of mechanism\noutputs?\n\nIs it efficient to produce samples from the Brownian motion algorithm or the Laplace\nNoise Reduction technique? It would help the paper to describe implementation details.\n", "limitations": "Yes - there are no real limitations to this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Results allow fully adaptive release of the query (where epsilon are allowed\nto vary) and apply to functions with bounded l_2 sensitivity.\n\n+ Brownian motion is simpler, more elegant, and offers improved performance over previous work.\n\n+ The generalization of AboveThreshold allows the accuracy constraint to depend\non the private database and have the same privacy cost as releasing the final\noutput. This overcomes a major hurdle of previous work in this area, and makes\nthe accuracy-first framework more practical.\n\n- Some minor writing mistakes, which I will describe.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4GD4YmSkIZe", "reviewer": "Reviewer_Nc8u", "summary": "The paper introduces the theoretical framework for a new noise reduction algorithm for probabilistic differential privacy (DP), namely, the Brownian mechanism (BM), and it also compares it empirically with the Laplace noise reduction (LNR) mechanism on empirical risk minimization (ERM) tasks. The privacy loss (random variable) for BM is characterized, a bound on it is given, and two 'privacy boundaries' are derived for it using results from martingale theory. Additionally, LNR, introduced in [Ligett et al., 2017], is extended in this paper to the continuous-time setting (and it is briefly indicated in the appendices how a Skellam noise reduction mechanism can be derived from the present work).", "questions": "- In Line 495, for $X_t^{\\pi}$ to be well-defined, one at least should require that each $(\\lambda,\\omega) \\mapsto Y_t^\\lambda(\\omega)$ is a Borel function.\n\n- What is $T_1$ in Definition 3.1? It looks like it is a pre-specified constant $T_1$ or function $x\\mapsto T_1(x)$, and it would be good to add this remark. Then, do we require $T_2(f(x)+B_{T_1(x)})\\le T_1$ (or $\\le T_1(x)$), in accordance with the $T_n$ specifying a sequence of time functions? Various instances of such initial parts of a trend have to be carefully specified in the paper, e.g., it is imposed that $\\eta>0$ in Line 227, yet it is mentioned in Line 238 that $(Z_t)_{t\\ge 0}$ (i.e., $\\eta=0$) will be used (perhaps one should define $\\mathrm{Lap}(0)$ as deterministically $0$).\n\n- The term 'density' is loosely mentioned in Definition 2.1 (e.g., density with respect to which measure?). I recommend slightly modifying how the definition is spelled out.\n\n- The paper has superb presentation, but a few typos should be fixed. \n- - English typos include: \"depend [on] the\" in Line 101; delete 'the' in Lines 187 and 222; replace ',' with '.' in Line 235; delete 'instead' in Line 570. \n- - Math typos include: need $\\mathcal{L}_{1:n}^{\\mathrm{Alg}}$ in the last equation after Line 546; $Z(t)$ is used in Line 559, but only defined in Line 593; should probably be $\\mathrm{Lap}(\\tau,\\frac{2\\Delta}{\\epsilon_n})$ in Line 572; the two equations after Line 586 need to be fixed; 'minus' sign missing in penultimate equation after Line 612; also, the wording of Prop. 4.2 might be revised, as ex-post privacy is prefixed with a pair when first defined.\n\nI also recommend that it be mentioned that Fig. 4 is in the appendix (when mentioned in Line 198); also, a comment by the authors on why the variances shown in Fig. 4 are large might be in order.", "limitations": "The authors mention briefly in the conclusion that existing composition results for DP are inapplicable for BM, and that noise reduction is concerned only with output perturbation. Although not a hinderance to the quality of the paper, it would have been nice to see some indication on how composition results can potentially be derived for BM.\n\nThe authors mention that there are \"no negative societal impacts,\" but it can be argued that privacy mechanism can be misused.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Quality: The derived results and the empirical assessment are of high quality and highly non-trivial.\n- Clarity: The paper is extremely well-written.\n\nMore details: The introduction of BM is a natural step after LNR, as Gaussian perturbation is expected to be more private than a Laplace perturbation if one cares about $\\ell_2$-sensitivity. Nevertheless, the authors borrow results from martingale theory that make the introduction of BM a nontrivial analogue of LNR. Further, the results are derived in a highly rigorous manner. Also, the extension of LNR to the continuous setting, besides being rigorously derived in a nice way, yields a significant improvement regarding the privacy problem: querying a utility now can only cause a privacy loss comparable to that incurred by the disclosure of the private parameter. Additionally, a union bound in [Ligett et al., 2017] is disposed of, yielding tighter bounds.\n\n=====\n\nWeaknesses: The following are not detrimental weaknesses of the paper, as it is strong as is; rather, they are rooms for improvement.\n\n- The performance comparison between BM and LNR is largely empirical. The main concern here is that it could be that the chosen datasets and tasks fall within a regime where BM outperforms LNR, but that this regime, as far as the present paper is concerned, is unknown. The authors mention in Line 16: \"[BM] empirically outperforms existing work on common statistical tasks, ....\" Relatedly, in Line 302, the authors write \"... we plotted guaranteed (in the case of LNR) or high-probability (in the case of BM) privacy loss on the x-axis against average loss (either logistic or ridge) on the y-axis.\" In addition, the authors write in Appendix C in Line 579, before proving a utility guarantee for ReducedAboveThreshold, \"... instead of plotting the utility guarantee in our experiments in Section 6, we instead plot empirically observed loss/accuracy.\" In view of these statements, I think the work could be stronger if more aligned comparisons between BM and LNR are presented.\n\n- There are no details about how BM can be incorporated with composition of DP mechanisms; this issue is mentioned only as a limitation in the conclusion of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1TMOCNZkudH", "reviewer": "Reviewer_r5ou", "summary": "The paper considers the Brownian mechanism, a new noise reduction DP scheme that allows for \"stripping off\" the noise gradually until the desired accuracy is satisfied. By leveraging the Markovian nature of the Brownian noise, the privacy guarantee of releasing a sequence of queries (with different epsilons) is the same as releasing the least private one. This improves upon using independent noise, where the privacy needs to be accounted for via composition theorem. In addition, compared to the Laplace-based method [LNRWW 2017], the Brownian mechanism gives an $\\ell_2$ guarantee and hence is more suitable for FL tasks. Finally, the authors combine the Brownian mechanism with ReducedAboveThreshlod, a generalization of the AboveThreshold method in [Dwork 2014], giving an adaptive (ex-post) privacy guarantee that will be at most twice that of the non-adaptive version.", "questions": "1. As in [LNRWW 2017], Lemma 3.2 builds on the Markov property of the Brownian mechanism. However, as in general, the time functions $T_n$ may depend on the future of the Brownian noise, i.e., $T_n = T_n(f(x), B_{T_{n-1}},...,B_{T_1})$, i am not sure whether the Markovian property still holds. In its proof, the authors claim that by using the strong Markov property of Brownian motion, one can replace the time indices with random ones. I am not sure whether this is correct or not, as to my knowledge strong Markov property only ensures $B_{T+t_1},..., B_{T+t_n}$ being Markov for a stopping time $T$. I think the authors need to include more details in the proof, as Lemma 3.2 is the basis of the Brownian mechanism.\n\n2. The notation of the stopping function $N(x)$ is a little confusing, as it gives a false impression that the stopping time can directly depend on the private data set $x$. However, if my understanding is correct, it could only depend on the prefix of the private release $M_{[1:n-1]}(x)$. The notation of $N(x)$ could be misleading and (incorrectly) suggest that the ReducedAbove threshold is unnecessary since one could directly compare $M_n(x)$ with $f(x)$, which would still be a valid stopping time.\n\n==========\nPost rebuttal: the authors' response to Q1 has addressed my main concern, and i have modified my score accordingly.", "limitations": "Yes, the social impact is properly discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n\nThe paper extends the previous noise reduction technique in [LNRWW 2017] to $\\ell_2$ geometry with $(\\varepsilon, \\delta)$-approximate DP. Having an $\\ell_2$ guarantee is always preferable for FL tasks in both theory and practice. In addition, the improved AboveThreshlod method seems to be significant and allows for much tighter privacy accounting.\n\n- Weakness\n\n1. In general, I think the theoretical grounding looks mostly sound. However, I do have a technical question regarding Lemma 3.2 (see the \"Question\" section). As Lemma 3.2 is the basis of almost all results of this paper, I'd appreciate it and will increase the score accordingly if the authors can clearly clarify it.\n\n2. In my opinion, the presentation can be improved by providing more high-level descriptions of how this work compares with [LNRWW 2017]. In particular, in Section 4, the authors extend the LNR scheme in [LNRWW 2017] to the continuous case; however, I don't think I can fully appreciate why extending LNR to the continuous case is important and what is the advantage of doing so.\n\n3. As the privacy of the Brownian Mechanism is ex-post and is determined by the privacy functions $\\mathcal{E}_n$, it seems to be unclear how to set them in practice. It would be good if the authors could briefly discuss it.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept