Differential Privacy of Dirichlet Posterior Sampling
Authors: Donlapark Ponnoprat
Venue: NeurIPS 2021 Submitted (2021)
Keywords: differential privacy
Dirichlet distribution
Bayesian inference
Bayesian learning
posterior distribution

Abstract: We study the inherent privacy of releasing a single sample from a Dirichlet posterior distribution. As a complement to the previous study that provides general theories on the differential privacy of posterior sampling from exponential families, this study focuses specifically on the Dirichlet posterior sampling and its privacy guarantees. With the notion of truncated concentrated differential privacy (tCDP), we are able to derive a simple privacy guarantee of the Dirichlet posterior sampling, which effectively allows us to analyze its utility in various settings. Specifically, we provide accuracy guarantees of the Dirichlet posterior sampling in Multinomial-Dirichlet sampling and private normalized histogram publishing.

Differential Privacy of Dirichlet Posterior Sampling
Anonymous Author(s) Affiliation Address
email
Abstract
We study the inherent privacy of releasing a single sample from Dirichlet posterior distribution. As complement to the previous study that provides general theories on the differential privacy posterior sampling from exponential families, this study focuses specifically on the Dirichlet posterior sampling and its privacy guarantees. With the notion of truncated concentrated differential privacy (ICDP), able to derive simple privacy guarantee of the Dirichlet posterior sampling, which effectively allows to analyze its utility in various settings. Specifically, we provide accuracy guarantees of the Dirichlet posterior sampling in Multinomial- Dirichlet sampling and private normalized histogram publishing.
3
Introduction
10
11 The Bayesian framework provides a way to perform statistical analysis by combining prior belief's 12 with real-life evidence. At high level, the belief and the evidence are assumed to be described
13 by probabilistic models. As we receive new data, our belief updated accordingly via the Bayes'
14 theorem, resulting the so-called posterior belicf. The posterior tells us how much we are uncertain
15 about the model's parameters.
18 The Dirichlet distribution is usually chosen as the prior when performing Bayesian analysis on discrete variables, as it conjugate prior to the categorical and multinomial distributions. Specifically, Dirichlet distributions are often used discrete mixture models, where a Dirichlet prior is put on the mixture weights [LW92] MMROS). Such models have applications NLP [B998), biophysical systems [Hin15), accident analysis [de 06), and genetics (BHW0O) PMOT CWS03). In all of these studies, samplings from Dirichlet posteriors arise when performing Markov chain Monte Carlo methods for approximate Bayesian inference.
17
18
19
20
29 Dirichlet posterior sampling also appears other learning tasks. For example, in Bayesian active
24 learning, arises in Gibbs sampling. which used to approximate the posterior of the classifier over the labeled sample (NLYCCI3). In Thompson sampling for multi-armed bandits, one repeatedly draws sample from the Dirichlet posterior of each arm, and picks the arm whose sample maximizes the reward (ZHGSY2) AAFK20 NIK20 And in Bayesian reinforcement learning, state-transition probabilities are sampled from the Dirichlet posterior over past observed states (St00 ORR13).
25
29 Dirichlet posterior sampling can also be used for data synthesis. Suppose that we have a histogram
30 (z),.... rq) of actual data. An approximate discrete distribution of this histogram can be obtained by ......,.4 .td + az), where ai,.... . Odd are prior parameters. Then synthetic data is produced by repeatedly drawing from Multinomial(Y) There many
31 drawing sample Y from Dirichlet(2,, 1 + o,....,
studies on data synthesis that followed this approach AV08 MKAGV08 RWZ14 PG14 SIGLY17
Submitted to 35th Conference Neural Information Processing Systems (NeurIPS 2021). Do distribute.

---

34 In the above examples, the data that we integrate into these tasks might contain sensitive information.
35 Thus is important to ask: how much the information is protected from the Dirichlet samplings? The goal of this study is to find an answer to this question.
36
37
The mathematical framework of differential privacy (DP) (DMNS06) allows to quantify how much the privacy of the Dirichlet posterior sampling is affected by the prior parameters a....... agg. In the definition of DP, the privacy of randomized algorithm is measured by how much its distribution changes upon perturbing a single data point of the input. Nonetheless, this notion might be too strict for the Dirichlet distribution, as a small perturbation of a near-zero parameter can cause a large distribution shift. Thus, it might be more appropriate to rely on one of several relaxed notions of DP, such as approximate differential privacy, Rényi differential privacy, or concentrated differential privacy. It is natural to wonder if the Dirichlet posterior sampling satisfies any of these definitions.
36
39
40
41
42
43
44
45
1.1
Overview of Our results
46
This study focuses on the privacy and utility of Dirichlet posterior sampling. In summary, we provide a closed-form privacy guarantee of the Dirichlet posterior sampling, which in turn allows us to effectively analyze its utility in various settings.
47
48
49 Privacy. We study the role of the prior parameters in the privacy of the Dirichlet posterior sampling. Theorem I our main result, where we provide a guaranteed upper bound for truncated concentrated differential privacy (tCDP) of the Dirichlet posterior sampling. In addition, we convert the 1CDP guarantee into an approximate differential privacy guarantee in Corollary P
50
51
52
58
4 Utility. Using the (CDP guarantee, we investigate the utility of Dirichlet posterior sampling applied in two specific applications:
55
we consider one-time sampling from Multinomial-Drichlee distribution. But instead of directly sampling from this distribution, we sample from another distribution with larger prior parameters. The accuracy is then measured by the KL-divergence between the original and the private distributions.
In Section 4.1
58
59
In Section 4.2 we use the Dirichlet posterior sampling for a private release of normalized histogram. In this case, the accuracy is measured by the mean-squared error between the sample and the original normalized histogram.
80
61
In both tasks, compute the sample size that guarantees the desired level of accuracy. In the case of private histogram publishing, we also compare the Dirichlet posterior sampling the Gaussian mechanism.
64
65
1.2
Related work
There are several studies on the differential privacy of posterior sampling. Wang, Fienberg, and Smola [WFS15) showed that any posterior sampling with the log- likeliioohodd bounded by B is 4B- differentially private. However, the likelihoods that we study are not bounded away from zero; they 69 have the form P which becomes small when one of the P; 's is close to zero. Dimitrakakis, Nelson,
68
70 Zhang. Mitrokotsa, and Rubinstein [DNZMRI7] showed that if the condition on the log- likelihood is
71 relaxed to the Lipschitz continuity with high probability, then one can obtain the approximate DP.
72 Nonetheless, with the Dirichlet density, is difficult compute the probability of events in which the Lipschitz condition is satisfied.
73
74 In the case that the sufficient statistics x has finite L -esesiitiviy Foulds, Geumlek, Welling and
75 Chaudhuri [FWCC16] suggested adding Laplace noises to x. Suppose that y is the output; they
76 showed that sampling from p(fly) is differentially private and as asymptotically efficient as sampling from x())).. However, for a small sample size, the posterior over the noisy statisties might be too
77
78 far away from the actual posterior. Bernstein and Sheldon [BS18) thus proposed approximate the
joint distribution p(0,x,, y) using Gibbs sampling, which is then integrated over to obtain more accurate posterior over y.

---

81
Geumlek, Song, and Chaudhuri [GSCI7] were the first to study the posterior sampling with the RDP. Even though they provided a general framework to find (A, c)-DP guarantees for exponential families, explicit forms c and the upper bound of À were not given. In contrast, our tCDP guarantees of the Dirichlet posterior sampling imply an explicit expression for e, and also an upper bound for
82
89
84
The privacy of data synthesis via sampling from Multinomial(Y)) where Y is a discrete distri- bution drawn from the Dirichlet posterior, was first studied by Machanavajjhala, Kifer, Abowd, Gehrke, and Vilhuber [MKAGV08]. They showed that the data synthesis is probbabbbbilliittc DP, which implies -aproxximo DP. However, as their privacy analysis includes the sampling from Multinomial(> Y), their privacy guarantee depends on the number of synthetic samples. contrast, we show that the one-time sampling from the Dirichlet posterior is approximate DP, which by the post-processing property allows to sample from Multinomial(Y retaining the same privacy guarantee.
86
87
88
89
90
81
many times as we want while
95
The Dirichlet mechanism was first introduced by Gohari, Wu, Hawkins, Hale, and Topcu [WHHHT2 Originally, the Dirichlet mechanism takes a discrete distribution = (Pi..... .P)) and draws one sample Y Dirichlet (rpi.... TPa). Note the absence the prior parameters, which makes Y an unbiased estimator of p. But this comes with cost, as the worst case of privacy violation occurs when almost all of the parameters are close to zero. The authors avoided this issue by restricting the imput space to a subset of the unit simplex, with some of the p; 's bounded below by fixed positive constant. This results in complicated expressions for the privacy guarantees as they involve minimization problem over the restricted domain. In this study, we take a different approach by adding prior parameters to the Dirichlet mechanism. As a result, we obtain a biased algorithm that requires no assumption on the input space and has simpler forms of privacy guarantees.
94
95
96
97
99
100
101
102
103
1.3
Notations
We let Rdd be the set of d-tuples of non-negative real numbers and IR be the set of d-tuples of positive real numbers. We assume that all vectors are d-dimensional where d 2 2. The notations for
104
105
all vectors are always in bold. Specifically, x == (.i,..., xa) E B consists of sample statistics of the data and == [a1 ............. aa) E RR consists of the prior parameters. The vector p (PL Pa) always satisfies >, 1. The number of observations is always N. We also denote ao == Σ T; and = Σ, 04 For any vectors x, x' and scalar > O, we write x + x' = (I1 + z',..... Id x'1) and rx == (rz1,.... ,Ia)) For any positive reals x and x', the notation x x x' means x = Cx' for
106
109
110
111
some constant > 0, x Rs x' means cæ' S x S Cx' for some e, > 0, and x S x' means x S Cx' for some C Lastly, ||x| max, [2 | is the 0o norm of
112
2
Background
113
114
2.1
Privacy models
115 Definition 2.1 (Pure and Approximate DP [DMNS06)). A randomized mechanism M X"" + y 116 is (e, d)fffferrentt private ((e, 6)-DP) if for any datasets ær, x' differing single entry, and all
events E C V,
(x) e EJ S P(M((2) E E] + If M is (s, D). then we say that it e-differential privacy (s-DP).
118
119
The term pure differential privacy (pure DP) refers to e-differential privacy, while approximate differential privacy (approximate DP) refers to (c, 5)DP when 5 > 0.
120
121
In contrast to pure and approximate DP, the next definitions of differential privacy are defined in terms of the Rényi divergence between M (x) and (z'):
123
Definition 2.2 (Rényi Divergence [Rénol]). J. Let P and Q be probability distributions. For À E (1,
124
the Rényi divergence of order between P and Q is defined as
1 (x[[)) = - log P(y)>Q(w)>>> 1- dy 1 log
P(y) A-1
g~ Q(1) >-1
3

---

125 Definition 2.3 (tCDP and zCDP [DRRSI BSI A randomized mechanism M 2n + y is
126
w-truncated p-concentrated differentially private ((, w)-CDP) if for any datasets x, differing on single entry and for all E (1,w),
127
(x(M()))M(2))) S Xp.
If M is (p. co)-ICDP, then say that it is p-zero- czero-concentratedd differential privacy (p-zCDP).
129
Note that both ICDP and zCDP have the composition and post-processing properties. Intuitively, / con- trols the expectation and standard deviation of the privacy loss random variable: Z = log PTM('")=
([M(a)=Y1
where Y has density (x),, and w controls the number of standard deviations for which concen- trates like Gaussian. A smaller p and larger correspond to stronger privacy guarantee. It turns
131
132
out that tCDP implies approximate DP:
134
Lemma 1 (From ICDP to Approximate DP BDRS18), ). Let > O. If is (p, mechanism, mechhiiinn
135
then it also satisfies (e, 5)-P with
+ 2 p (1/8) pw+ log 1/6)
if log((18) S ( 1)2p if log(1/8) (w 1)2p
138
2.2
Dirichlet distribution
For a E RS the Dirichlet distribution Dirichlet(aL (x) is a continuous distribution of d-dimensional probability vectors i.e. vectors whose coordinate sum is equal to 1. The density function of Y Dirichlet(a) given by:
137
138
139
ply) B(a)
V
where B(xx) is the beta function, which can be written in terms of the gamma function:
B(a) 11,
(1)
a))
2.3 Dirichlet posterior sampling
We consider the prior Dirichlet(a) and the likelihood of the form p(xly) & I v where
142
143 x E R& consists of sample statistics of the dataset. The Dirichlet posterior sampling is one-time
144
sampling:
Dirichlet + a:).
There is a modification of the sampling which introduces concentration parameter 0, and instead we sample from Dirichlet + a)) [GSCI7, GWHHT2T] Smaller values of make the sampling more private, and larger values of r make Y a closer approximation of x. Even though the case is the main focus of this study, our main privacy results can be easily extended to other values of as we will see at the end of Section 3.1
147
148
149
Consider special case where p is empirical distribution derived from the dataset, and want Y to be a private approximation of p; the sampling Y Dirichlet(rp + ax) is called the Dirichlet mechanism [WWHHT2T]] It is interesting to note that the Dirichlet mechanism is form of the exponential mechanism [MT0]]: let r > 0 be the privacy parameter, Dirichlet(c (x) be the prior, and the negative KL-divergence be the score function of the exponential mechanism. Then the output of this mechanism distributed according to the following density function:
153
154
155
exp( DKL (p. y)) (). 04-1
Σ P. log(v//p))
II
x exp
r
f exp(-r DKL (p. R.- 1 dy
II 4.
1/
y
which is exactly the density function of Dirichlet(rp + a

---

157
2.4
Polygamma functions
158
In most of this study, we take advantage of several nice properties of the log-gamma function and its derivatives. Specifically, ((x)== = dz log [(x) is concave and increasing, while its derivative (a) is positive, convex, and decreasing. In addition, vl can be approximated by the reciprocals:
159
180
+ 2x
(z)
< x x2
181
which implies that (x)) 20 23 as x - 0 and (x) ~ as as - oC.
3
Main privacy results
182
163
3.1
Truncated concentrated differential privacy
Theorem 1. Let a E IRSo and am = min; OGe- Let E (0, am). Let D2, A > 0 be constants that satisfy E, - x2²}² I A3 and max; Isg - x/5 I Ax whenever x, x'x's E TR are sample statistics of any two datasets differing on a single entry. The one-time sampling from Dirichlet(x + ax) is
164
185
186
167
(p. WDDDP where w 2 + and
1 A3 (am - ?).
p 2
Note that (p, oc) is not obtainable, the ratio between two Dirichlet densities blows up as 189 + cc. We present here short proof that skips some calculations (see Appendix for full proof).
proof. Consider any X E (1, a +1)=+ Let u = x + a and u' == + a'. Let P(y) the density of Dirichlet(u) and P' P'(y) be the density of Dirichlet(u'). quick calculation shows that:
170
171
Ply)^-11 B(u')~-1 B(u + (A (oluu-u))
Eyy)(y)
(3)
P'(y)~-1
B(u)~-1
B(u)
172 We take the logarithm on both sides and apply the second-orde Taylor expansion to the following
173 G(us, u²) and Huss, u!) terms that appear on the right-hand side. As a result, there exist & between
U; + (A - 1)(u: - ut) and u, and ç between u, and v/ such that
174
G(u,, uf) = (A (log T(u)) - log [(u:))
1
=-( 1)(x; x)))(u))))))))))))))))))())))x + 2 1)(x; (11;--x/) =4))2(((
(4)
H(u,, u() = [ou + (A 1)(44 u/)) log I(us)
= =(A - 1) - =;))(())) + マ - 1)² - 2b (E),
(5)
175 Note that v/d is increasing. If x; > x/. then & and g' are bounded below by uf 2 am On the other hand, if v, S 2/, then and g' are bounded below by u; - (A 1)[u; - rt(l. The condition
176
177 A
2 + guarantees that u, (A 1)lu u²/1 > am y. All cases considered, we have
1
G(u,, u4) + Hu,,, u < ((1 1) + (A - 1)3 2f)2 (am - 7)
2
1
X(> -1/)) 2/ 7).
2
178
Denoting == E, Uj and u/ = E, u// the same argument shows that G(uo, ub) + H(u,, un) > 0.
179
Therefore,
Px(P(y))
Σ (Guu, ut) H(s, u()) G(uo, H(uo: u6)
1-1
Σ GGus, ut) + H(u,, u()))
X
1 (x - 21/2 (am - -7) s AA3z0(am 7))
Σ
< 2
5

---

10"
10e
True
a=
(p.2)-CDP upper bound
10-2
a=5
10
10
10
10
10-8
10-10
2
10
14
18
0
4
12
16
20
Figure 1: Left: the actual values of p Y/ (P(P))))) and the worst case (p. 2)-CCDP guarantees
at A3 = Ax 1. Here, P and P' are Dirichlet posterior densities over x = (11, 8, 65, 25, 38, 0), x' (11,8, 65, 25, 38, 1), and (a,...,))) ..). Right: comparison between (s, 8DDD guarantees of
the Dirichlet posterior samplings ( with different uniform priors: a (a,...,
180
The guaranteed upper bound is independent of the sample statistics. As a result, the bound applies even in worst settings i.e., when x; 0 and x Aoo. or vice versa, for some i. As we can see in Figure the upper bound is close approximation to the actual value of p when 26 = 0 and z/ 1. However, being sample independent bound, the difference becomes substantial when all x; 's are large. There is one way to get around this issue: if there is no privacy violation in assuming that the sample statistics are always bounded below by some threshold т, then we can incorporate the threshold into the prior (thus (amm - 7) in 2 is replaced by v (a + T 7)).
181
184
185
186
187
The parameter ? allows to adjust the moment bound w as desired. Even though a higher usually leads to better privacy guarantee, there two downsides to picking y close to O'm in this case. First, note that contains v/ (am - 7): as y - Om. the value of p diverges to co, leading to a weaker privacy guarantee instead. Second, as the Taylor approximation (5) is accurate when tt is close to
190
u + (A 1)( - uf), having a large value of À would push the guaranteed upper bound away from the actual privacy loss. Thus it is recommended to pick so that 7/ 2 1 and amm - 7 > 0.
191
192
193
Alternatively, we can choose the value of y that minimizes when converting from tCDP (c, 5)D
194
using Lemmal D this method will be explored in the next subsection.
195
Theorem can be casily applied to sampling from Dirichlet(rx + a). Replacing x with rx, we have
2 replaced by r22 and Ax replaced by rAxc- Consequently, the sampling is ( + -CCDP, 196
where p = A3 (am - y). In Appendix 4, we analyze the scaling of r in conjunction with am at a fixed privacy budget p.
197
198
199
3.2
Approximate differential privacy
200
We now convert the tCDP guarantee to an approximate DP guarantee, Let 8 E (0, 1). Using Lemma 1 the Dirichlet posterior sampling with Dirichlet(a)) as the prior is (e,6)-DP with
201
p(7) + 2/
if log(1/6) < A2p()//A2 log(1/6) > 72p())/22 p()) 2 + +1) + log(1/5)
p(7) +2/p(7)
(1/8)
=
(6)
where p(y) = 13 77).
202
203 We try to minimize e by adjusting the value of First, we consider the case (1/8) < >
Since p(7) is a strictly increasing function of y, both p(7) + log(1 and >²p(r)/A2 minimized at the minimum possible value of in this case, that is, at the unique YM that satisfies log(1/6) 7
204
205 are both strictly increasing function of 7. Therefore,
2 A330 (am 2

---

208
Now we consider the second case, when >< 2/M. As p(7) is an increasing positive convex function
209
of 7, the function
1 ABv2 (am - 7) (1) +1 (1++1
log(1/
f(7) =
Y (0,
2
A
7
210
is also convex in 7, and thus has a unique minimizer 7m E (0, yM). Comparing to the first case, we have f((m) S f(TM) = p(TMM) + pVD(TN)) (og/))) log(1/6). We then conclude that f((mm)
211
R3,0 and denote am min; aq. Let 22, Ax > 0 be constants that satisfy Ex(r; x²1 < 23 and max; [.; - x I A whenever x, x' E IR are sample statistics of any two datasets differing on single entry. For any ò E (0, 1), let TM be the solution to the equation 214
Theorem 2. Let
log(1/6) = 2 23 A2/0(aa (am - >) The one-time sampling from Dirichlet(x + a) is (E, 6)-DP,
215
216
where
E min f(7).
7E(0,7Ml
Figure shows how & decays function of three different values of Omm
4
Utility
219
Using the results from the previous section, we analyze the Dirichlet posterior sampling's utility in two specific tasks.
220
4.1 Multinomial-Driieee sampling
Suppose that we are observing N trials, each of which has d possible outcomes. For each e 222
223
d}. let x; be the number of times the i-th outcome was observed. Then we have the multinomial likelihood p(xly) x II, y, From this, we sample from the Dirichlet posterior:
224
Dirichlet + a)).
225
Suppose that we want to sample from true distribution Px ~ Dirichlet(x + a).. but for privacy reasons, we instead sample from Qx ~ Dirichlet(x + a') where a' > a; for all i. The utility of the privacy scheme is then measured by the KL-divergence between Px and Qx- Assuming that x is an observation of Multinonial(p). the following Theorem tells us that, on average, the KL-divergence small when the sample size large, and the p are evenly distributed.
226
227
228
229
230
Theorem 3. Let p == (PI.....PPa Pa) where Ps > O for all i and E, 1. Define random
231
variable X ~ Multinomiall()) Let Px ~ Dirichlet + or) and Qx ~ Dirichlet + a') where
232
af 2 a 2 for all i. The following estimate holds:
Ex[Drr. Ex(Drr.(PxI1Q45 [xx]] S N+T E(ol - ai)
(10)
Pi
233
The proof is given in Appendix 2. Let us consider simple privacy scheme where we fix 8 > 0 and
234 let af = a4 + s for all i. Thus (10) becomes:
G(p)s² N+I'
Ex[ [x)]
(1I)
where G(p) = E, 1/p:- Now we take into account the privacy parameters. Let p= 22 (am - 7) 236 and p' A3y0 (a'm 7). where a'm = min; a; a'n = min, a/, and y < am. Here, we approximate
235
the values v (am - 7) and vaaa - 7) under two regimes:
237
238
High-privacy regime: a'n 7 1. We have vi(a'n - 7) ~ 1/(a2n - 77), which implies
239 a'm R A3/p/. .. We also have d'm -7 R p for am 7 2 and Om > (am 77 R A
240 for a - y < 1. Thus we have the following bound for the right-hand side of II]
G(p)s² ((p)(o(, am A)G(p)
1
A3)(p)
N+1 S +1
(12)
N +1
P
OPNN+11
Consequently, we have D D (PIIQ) < e for N 0 AAGlp
241
7

---

242
Low-privacy regime: 1 > dn > 0. This is similar as above, except we have a'y - -y R
2 and O.m 7 ~ 2 22/p1/2 Similar computation as (12) shows that DKL (Pll)) < 6 when
243
N =Ω( ( (p)(p) 244
pC
We observe that, in both regimes, the sample size scales faster with respect to with a higher value of (p)), which is associated with a higher number of outcomes d, and more concentrated multinomial parameter p: this agrees with the result of our simulation in Appendix Moreover, for small p' the sample size scales as 1/p², while for large p' the sample size scales as 1/p/.
248
247
248
249
4.2
Private normalized histograms
Let x (II,..., 2a) be a histogram of N observations and p = x/N. We can privatize p by 251 sampling a probability vector: Y ~ Dirichlet(x + a). Note that Y is biased estimator of
252
Denoting 0gg := Σ: 02 the bias of each component of Y is given by Y Pt- Hence,
[Bis (Y;) = 34 + 04
10,00 - Noa1
No
00
N cuu
Pi
N(N + au)
N(N + ao) N ag
253
Since Y; (et 0la: NN + ag
1; 05) is +[o+oo+1] sub-Gaussian MA17]. we have,
P[|V; pal > f + [Bias (Y:)) s P(|Y. B[ [Bias(Y,) > + [Bias(Yi)]]
P[|Y; || > f]
S 2e 11)
With the union bound, we plug in t t= log(2d/3)
+oo+a++]j for any E (0, 1), to obtain the following
255 accuracy guarantee of the private normalized histogram:
Theorem 4. Let Y Dirichlet (x + ox), where x E RR and a E IR and p x/N. For any
256
3 (0, 1). with probability at least - 3. the following inequality holds:
Y pllo S
+ N 0.00 2(N + 000 +1)
log(2d/B)
av
(13)
Given > 0, we use (3) to find lower bound for N that gives ||Y plaso < w.p. 1 1-1 when
259 Y is sampled with p-ICDP. For simplicity, we consider a uniform prior: ai = > 0 for all i
Thus, = A (a - 7), where y might be chosen according to Corollary We consider the two
260
281
following regimes:
High-privacy regime: a->>~11 1. In this case, (a(a (a--)) -) 1/(a - 7). From p 1/2 A (a y)
we have RJ 23/2p + y. Replacing ag by da in (13 yields the sample size:
N N= st /og(2d/B) () d A
c 2p +7))
(14)
254
for the desired accuracy.
285
Low low-privacy regime: a - < 1. This is the same as above, except now we have ci - 7) x
1/(a - 7)², which implies a A2/(2p)122 1/2 + 7. The sample size that guarantees the desired
286
257
accuracy is:
N = Ω log log(3)/3) d A2 22 +7))
(15)
Let us compare this result to the Gaussian mechanism, which adds a noise Z ~ N(O0 to the normalized histogram p directly. Thus the éz-sensitivity this case is A2/N. We have that the
268
289
270
Gaussian mechanism is p-zCDP where =N [BS16]. Using the same argument as above, with probability at least 1 - 3, the following inequality holds for all i:
271
log (2d/3)22 N2p
Z 00
(16)
8

---

d= p0 0.01
d= d=100, p-11 0.1
d 10,p=1 1
10
10
10a
Dirichet Gaucdion
Difchle Garnsion
Dischle
Chussion
10
10
10
10-3
10-1
10-
10-5
10-5
10
10
10
10
10
10P
10*
10a
10
10*
Sumple size (M)
Sumple size (N)
Sample size (N)
d= 1000, 0.01
d= 1000, 0.1
d= 1000,
Dinchlet Gausiiun
Dinihlet
Gausiin
10-1
Guussian
10
10-2
10-1
10
10
10
10-1
10
10
10 10
10
10 10
10'
10
Somple size (N)
Sample (N)
Sample (N)
Figure 2: The 8 -ccurrcyy mechanisms for private normalized histograms (A3 = 2 and Ax = 1). For each N, d and p. we generated the inputs x1...., X200: where X₃ Multinomial(qu) and qu ~ Dirichlet(5,.... 5).
function of N, of Dirichlet posterior sampling ( = 1) and Gaussian
272 Hence, the sample size of N = 22 (oog(22)) 2d / pe guarantees the desired accuracy. Compar-
273 ing this to (14 if we assume < 1, the AM-GM inequality tells us that
log(2d/3) d
log (2d/5)))
A
log log(2d/ pe
(17)
274
The inequality (17 implies that the Gaussian mechanism requires less sample than the Dirichlet mechanism in order to guarantee the same level of accuracy. The Gaussian mechanism is also better in the low-privacy regime the p in (15) satisfies vp < p and A2 42, leading to the same inequality 17 Nonetheless, the decay in (16) is linear in d, while that in (3) has ag do in the denominators. This observation suggests that, when x is a sparse histogram i.e. when N < d. the 8o -ccurracy of the Dirichlet mechanism is smaller than that of the Gaussian mechanism. This conclusion is supported by our simulation in Figure We see that the ed -ccurrayy of the Dirichlet mechanism is smaller than that of the Gaussian mechanism for small N when d = 1000. The code for all experiments in this study can be found in the supplemental material.
275
276
278
279
280
281
282
Potential negative societal impacts
283
It is important to note that, when p becomes unacceptably large (e.g., 104), the sampling is far away from being private. Thus any organization that deploys the posterior sampling on sensitive data must not vacuously refer to this study and claim that its algorithm is private. It is the organization's ss responsibility to fully publish the prior parameters, and educate its users/customers on differential privacy and how the privacy guarantees are calculated.
286
287
288
289
It is desirable that differentially private algorithms accurate for the task at hand, especially when the data is used for important decision-making Thus, one needs to make sure that there is enough sample to achieve the desired level of accuracy. For a large differentially private system, privacy budgets need to be allocated to the parts that require accurate outputs.
291
292
293
Lastly, one must be careful with the choice of prior parameters; a uniform prior is used, smaller groups will suffer relatively larger statistical bias. As result, private statistics of small populations (such ethnic racial minorities) will be relatively less accurate. One way to get around this issue is to (privately) impose larger prior parameters on larger populations.
294

---

References
297
[AAFK20]
1. Aykin, B. Akgun, M. Feng. and M. Krunz. "MAMBA: A Multi-armed Bandit Framework for Beam Tracking in Millimeter-wave Systems". In: 39th TEEE Conference on Computer Com- munications, INFOCOM 2020, Toronto, ON, Canada, July 6-9, 2020. IEEE, 2020, pp. 1469- 1478.
289
300
301
302
[AVO8]
J. M. Abowd and L. Vilhuber. "How Protective Are Synthetic Data?" In: Privacy in Statistical Databases, UNESCO Chair in Duta Privacy International Conference, PSD 2008, Istan- bul, Turkey, September 24-26, 2008, Proceedings. Ed. by J. Domingo-Ferroe Ferrer and Y. Saygin. Vol. 5262. Lecture Notes in Computer Science. Springer, 2008, pp. 239-246.
303
305
[BDRS18]
M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke. "Composable and versatile privacy via truncated CDP". In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, Ed. by Diakonikolas, D. Kempe, and M. Henzinger. ACM, 2018, pp. 74-86.
307
308
309
310
[BHW00]
R. J. Boys, D. A. Henderson, and D. J. Wilkinson. "Detecting Homogeneous Segments in DNA Sequences by Using Hidden Markov Models". In: Journal of the Royal Statistical Society. Series C (Applied Statistics) 49.2 (2000). pp. 269-285, ISSN: 00359254, 14679876.
311
313
[BS16]
M. Bun and Steinke. "Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds". In: Theory of Cryptography. Ed. by M. Hirt and A. Smith. Berlin, Heidelherg: Springer Berlin Heidelberg. 2016, pp. -35-658.
315
[BS18]
G. Bernstein and D. R. Sheldon. "Differentially Private Bayesian Inference for Exponential Families". In: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada. Ed. by S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett. 2018, pp. 2924-222222 2434.
317
318
319
321
[CWS03]
J. Corander, P. Waldmann, and M. J. Sillanpää. "Bayesian Analysis of Genetic Differentiation Between Populations". In: Genetics 163.1 (Jan. 2003), pp. 367-374. ISSN: 1943-2631.
322
dd 06]
M. de Lapparent. "Empirical Bayesian analysis of accident severity for motorcyelists in large French urban arcas". Accident Analysis & Prevention 38.2 (2006), pp. 260-268. ISSN: 0001 -4575.
324
325
326
[DMNS06]
C. Dwork, F. Mesherry, K. Nissim, and A. Smith, "Calibrating noise to sensitivity private data analysis", In: TCC. 2006.
327
328
[DNZMR17]
C. Dimitrakakis, B. Nelson, 7. Zhang, A. Mitrokotsa, and I. P. Rubinstein. "Differential Privacy for Bayesian Inference through Posterior Sampling". In: J. Mach. Learn. Res. 18 (2017), 11:1-11:39.
329
330
331
[FGWC16]
J. R. Foulds, J. Geumlek, M. Welling, and K. Chaudhuri. "On the Theory and Practice of Crivac--Preeevvin Bayesian Data Analysis". In: Proceedings of the Thirty-Second Conference Uncertainty in Artificial Intelligence, UAI 2016, June 25-29, 2016, New York City, NY, USA. Ed. by A. T. Ihler and D. Janzing. AUAI Press, 2016.
332
333
334
[GSC17]
J. Geumlek, S. Song, and K. Chaudhuri. "Renyi Differential Privacy Mechanisms for Posterior Sampling". " In: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. Fd. by I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett. 2017, pp. 5289-5298.
396
337
338
340
[GWHHT21]
P. Gohari, B. Wu, C. Hawkins, M. T. Hale, and U. Topcu. "Differential Privacy the Unit Simplex via the Dirichlet Mechanism". In: IEEE Trans. Inf. Forensics Secur. 16 (2021), pp. 2326-2340.
342
343
[5in15]
Hines. "A Primer on Bayesian Inference for Biophysical Systems". In: Biophysical Journal 108.9 (2015), pp. 2103-2112 ISSN: 0006-3495.
344
345
[LW92]
M. Lavine and M. West. "A Bayesian method for classification and discrimination". In: Canadian Journal of Statistics 20.4 (1992), pp. 451-461.
346
347
[MA17]
O. Marchal and J. Arbel. "On the Sabb-aussianity the Beta and Dirichlet distributions".. In: Electronic Communications in Probability 22.none (2017), pp. 1 -14.
348
319
[MKAGV08]
A. Machanavajjhala, D. Kifer, J. M. Abowd, J. Gehrke, and L. Vilhuber. "Privacy: Theory meets Practice on the Map". In: Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, April 7-12, 2008, Cancúín Mexico. Fd. by G. Alonso, A. Blakeley, and A. I.. P. Chen. TEER Computer Society, 2008 pp. 277-286.
350
352
[MMR05]
J.- Marin, K. Mengersen, and C. P. Robert. "Bayesian Modelling and Inference on Mixtures of Distributions". In: Bayesian Thinking. Ed. by D. Dey and C. Rao. Vol. 25. Handbook of Statistics. Elsevier, 2005, pp. 459-507.
355
10

---

356
[MT07]
F. McSherry and K. Talwar. "Mechanism Design via Differential Privacy". In: 48th Annual IEEE Symposium Foundations of Computer Science (FOCS 2007). October 20-23, 2007, Providence, RI, USA, Proceedings. IEEE Computer Society, 2007, pp. 94-103.
358
359
[NTK
I. Nasim, A. S. Ihrahim, and S. Kim. "L.carnig- Based Reamforming for Multi-User Vehicular Communications: A Combinatorial Multi-Armed Bandit Approach". In: IEEE Access 8 (2020). pp. 219891-219902.
360
381
362
[NLYCC13]
V. C. Nguyen, W. S. Lee, N. Ye, K. M. A. Chai, and H. L., Chieu. "Active Learning for Prohabilistic Hypotheses Using the Maximum Gibbs Frror Criterion". In: Advances in Neural Information Processing Systems 26: Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United Statex. Ed. by C. J. C. Burges, L. Bottou, Z. Ghahramani, and K. Q. Weinberger. 2013, pp. 1457-1465
363
384
366
367
368
[ORRI3] 13]
I. Oshand, D. Russo, and B. V. Roy. "(More) Efficient Reinforcement I Learning via Poste- rior Sampling". In: Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. Ed. by C. C. Burges, L. Bottou, Z. Ghahramani, and K. Q. Weinberger. 2013, pp. 3003-3011.
389
370
372
[PB98]
T. Pedersen and R. F. Bruce. "Knowledge Lean Word-Sense Disambiguation". In: Proceedings of the Fifleenth National Conference on Artificial Intelligence and Tenth Innovative Appli- cations of Artificial Intelligence Conference, AAAI 98, IAAI 98, July 26-30, 1998, Madison, Wisconsin, USA. Ed. by J. Mostow and C. Rich. AAAI Press / The MIT Press, 1998, pp. 800- 805.
374
375
376
378
[PG14]
Y. Park and J. Ghosh. "PeGS: Perturbed Gibbs Samplers that Generate Crivac-Coomplinn Synthetic Data". In: Trans. Data Priv. 7.3 (2014), pp. 253-282.
380
[PM01]
J. Pella and M. Masuda. "Bayesian methods for analysis of stock mixtures from genetic characters". English. In: Fishery Bulletin 99 (Jan. 2001). p. 151. ISSN: 00900656.
[Rén61]
A. Rényi "On measures of entropy and information". In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability Volume I: Contributions the Theory of Statistics. The Regents the University of California. 1961.
384
385
[RWZ14]
J. Reiter, Q. Wang. and B. Zhang. "Bayesian Estimation of Disclosure Risks for Multiply Imputed, Synthetic Data". In: J. Priv. Confidentiality 6.1 (2014).
386
387
[SIGLY17]
M. J. Schneider, Jagpal, S. Gupta, S. Li, and Yu. "Protecting customer privacy when marketing with second-party data". In: International Journal of Research in Marketing 34.3 (2017), pp. 593-603. ISSN: 0167-81 16.
388
389
390
[St00]]
M. J. A. Strens. "A Bayesian Framework for Reinforcement Learning". In: Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA. USA, June 29 July 2, 2000. Ed. by P. Langley. Morgan Kaufmann, 2000, pp. 943-959
391
383
394
[WFS15]
Y. W.Wang S. F. Fienherg, and A. Smola. "Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo". In: Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015. Ed. by F. R. Bach and D. M. Blei. Vol. 37.
395
396
397
JMLR Workshop and Conference Proceedings. JMLR.org, 2015, pp. 2493-2502.
398
[ZHGSY20]
J. 7hu, X. Huang, X. Gao, Z. Shao, and Y. Yang. "Multi-Interface Channel Allocation in Fog Computing Systems using Thompson Sampling". In: 2020 IEEE International Conference on Communications, ICC 2020, Dublin, Ireland, June 7-1 2020. IEEE, 2020, pp. 1-6.
399
Checklist
401
402
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] We gave a simple guaranteed upper bound of tCDP (2) for the Dirichlet posterior sampling and illustrated how it can be used to derive accuracy guarantees in Section 4
404
405
406
(b) Did you describe the limitations of your work? [Yes] We discussed a limitation of the guaranteed upper bound of tCDP in the paragraph following Theorem [] We also described a situation under which the Gaussian mechanism is preferable to the Dirichlet posterior sampling at the end of Section 4.2
408
409
410
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the section on potential negative socictal impacts at the end of the paper.
11

---

418
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
414
415
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
417
(b) Did you include complete proofs of all theoretical results? [No] The proofs of all theorems are given in the main paper, except that of Theorem which given in Appendix 2.
418
419
420
3. If you ran experiments...
421
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URI.)? [Yes] The code and the instructions for our simulations are included in the supplemental material.
422
423
424
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] We specified the details of our simulations the figures' captions.
425
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We reported the error bars in Figure 2
428
(d) Did you include the total amount compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Our experiments are not computationally intensive.
429
430
431
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
432
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
434
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
435
436
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
437
438
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
440
5. If you used crowdsourcing or conducted research with human subjects...
441
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
442
443
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
444
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "s4UtMUmOJwP", "reviewer": "Reviewer_g7yk", "summary": "Summary: This paper gives a precise analysis of the privacy loss, as measured by differential privacy, from drawing samples from the Dirichlet posterior distribution on multinomial parameters conditioned on a sensitive data set. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper has a single main result, namely a precise analysis of the distribution of the privacy loss—in the sense of differential privacy—of the algorithm which takes a sensitive data set as input and a nonsensitive Dirichlet prior on parameters of a multinomial distribution, constructs a posterior distribution on the parameters, and samples a single value from that distribution. \n\nThe main result (Theorem 1) is stated in terms of truncated concentrated DP, though I think it might be easier to state it in terms of Renyi DP (as a function of the $\\alpha$ vector and the “order” $\\lambda$) and then derive the tCDP and $(\\epsilon,\\delta)$-DP statements as corollaries. (I also think it would be worthwhile, in the corollaries, setting $\\Delta_\\infty$ and $\\Delta_2$ to particular values, say 1, to get clear statements.) \n\nI have very few comments on the writing: the paper is clear and easy to understand and, I think, accurately represents and discusses the contributions. The only question here is significance: the paper is providing updated calculations for a well-know idea. It definitely should be published in an archival and refereed venue. I’m less sure that it meets the bar for NeurIPS. If the committee ultimately decides not to accept the paper, I would encourage the authors to submit to an appropriate journal. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Well addressed in a separate section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9LdA_4EGHlC", "reviewer": "Reviewer_ghaZ", "summary": "The paper studies releasing a single sample from a Dirichlet posterior with several variants of differential privacy in the two specific tasks of Dirichlet sampling and private normalized histogram publishing. Both privacy and utility guarantees are analyzed by the authors. The authors compare the results with Gaussian mechanism theoretically and empirically using a simple simulation.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper is well-organized and easy to follow. The related works are summarized and allow the reader to compare the drawbacks of existing methods relatively to the proposed methods. All the notations and background definitions are clearly stated. While the paper contains a significant amount of theoretical derivations, many of them are accompanied by intuitions and interpretations (such as discussion of low/high privacy regimes or illustrations of  behavior of the computed quantities as a function of parameters, such as Fig. 1). I was not able to thoroughly verify all the derivations, but the math seems sounds. Overall, i believe the paper makes a good contribution and will be interesting to the researchers in the area.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper contains a section on \"Potential negative societal impacts\" which reasonably discussed the implications of the usage of the method in an industrial setting.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7Bd1k1OxCfP", "reviewer": "Reviewer_QwTp", "summary": "\nThis paper studies differential privacy and the dirichlet mechanism.\n", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "\n\nThe paper contains quite some phrases which aren't fully precise.  Often, a minor effort can make the text more precise without taking significantly more space.  In some other cases, the question is whether it is worthwhile to give technical details without giving the reader the context in which he can understand these details.  E.g.,\n* Line 38: \"DP allows us to quantify how much the privacy of the Dirichlet posterior sampling is affected by the prior parameters\" -> what is meant here with \"afect\"?  Maybe you want to analyze how privacy guarantees depend on these parameters, but the cause of the change in privacy is in the publishing of the output so I wouldn't use \"affect\" for the parameters.\n* Line 67: \"any posterior sampling with the log-likelihood bounded by B is 4B-differentially private\" -> which log-likelihood must be bounded by B ?  Do you mean classic \\epsilon-differential privacy here (where you use B instead of \\epsilon for some other reason) ?  Usually a loglikelihood B is a negative value, while \\epsilon=4B must be positive to be able to consider \\epsilon-DP.  Should the loglikelihood be upper bounded or lower bounded by B ?\n* line 70: \"if the condition on the log-likelihood is relaxed to the Lipschitz continuity with high probability,\" -> the uninformed reader reading only your summary may not understand how a log-likelihood bound |log(P(x))| < B (which is typically applied to random variables) can be relaxed to a Lipschitz continuity requirement (which is typically applied to functions).  \n* Line 74: \"the sufficient statistics x\" refers to some not-yet-introduced variables x on which \"the\" sufficient statistics is considered without explaining to the reader which sufficient statistics is being considered.\n* Line 165: The theorem uses expressions involving x and x'.  x and x' are sample statistics of datasets, but it is unclear how they are sampled (e.g., with replacement / without replacement or other sample properties).  Even though we learn that x and x' are sample statistics from two adjacent datasets.\n* Theorem 1, and also a few earlier sentences, use the term \"one-time sampling\", but this concept isn't defined (and also not a hit when provided to Google).  Do you mean \"a single value x drawn from the distribution\" (a single sample) or do you mean \"at one time we draw many values x_1, x_2, x_3 ... without doing other things in between\" (e.g., in contrast to MDP no decision can be made after a first sample to infleunce a later sample), or something else?\n\nThere are some minor language issue, often related to the use of articles where I wouldn't expect them or the absence of articles where I would expect them.  Also,\n* Line 128: \"... privacy\" -> ... private\n\nSome other comments:\n* Line 142 saying \"p(x|y)\" suggests a conditional probability distribution where y is known and the distribution of drawing next x depends on y.  On the other hand, the equation between lines 144 and 145 suggests that we need to know x in order to draw Y.\n* Line 150 discusses \"Consider a special case where x = p\", but p isn't introduced yet at that point: the only thing we know about p already is (from the notations section) that \\sum_i p_i = 1.\n* It turns out that p is an empirical distribution of a dataset.  The paragraph mentions the question how to make a private version of p (a problem which has been solved without using Dirichlet distributions), but doesn't immediately provide an answer.  \n* Figure 2: I guess that instead of \"accuracy\" (typically used in classification problems as the fraction of cases classified correctly, so ideally close to 1) you mean \"norm\" or \"loss\" (ideally small), at least this is what the Y-axis scale suggests.\n\nThe paper doesn't clearly define the problem it is trying to solve.  E.g., What values are sensitive and need to be protected from being revealed?  How does the \"one-time sampling\" differ from earlier work which considered the same problem but without \"one-time sampling\" ?\n\n\nIn conclusion, the paper has numerous minor issues (which individually can probably be easily solved but collectively may form a serious hurdle for a non-expert reader), introduces insufficiently clearly the problem (a problem formulation is the key part of a paper which should be understandable for all Neurips attendees), clarifies insufficiently in which way the contribution is novel and significant, and only in a limited way validates the work through experiments (with a single Gaussian baseline) where it would be possible to compare to other alternatives and discuss limitations and advantages.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nThe text presents a comparison between the Guassian and Dirichlet mechanisms, and highlights around line 280 that the accuracy of the Dirichlet mechanism is better for spartse histograms and small N, but is silent about limitations, e.g., in the cases of dense hisograms and large N.\n\nThe paper doesn't discuss limitations, nor plans for future work where such limitations could be addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "--", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6h7m49J_Bzn", "reviewer": "Reviewer_Qa5w", "summary": "This paper proposes a method for releasing differentially private samples from Dirichlet posterior distribution. Authors present a privacy analysis for their proposed method and demonstrate that the method out performs Gaussian mechanism under certain conditions. Besides the empirical evaluation, authors also derive analytical utility guarantees for the method.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "In this paper authors propose a method that draws a single sample from Dirichlet posterior distribution. The method is rather simple and draws from Dir$(x + \\alpha)$, which is the posterior of multinomial observations $x$ given a Dirichlet prior Dir$(\\alpha)$ for the multinomial probabilities. The privacy of the method is analysed with respect to the prior parameter $\\alpha$ using truncanted CDP. Authors consider two use cases for this method (which I think are rather similar), and derive analytical expressions for the utility of these cases. Finally authors demonstrate that the proposed method outperforms Gaussian method in a histogram release task when the number of samples is small.\n\nThe analysis of the paper seems novel to me. I appreciate the authors' efforts for deriving analytical expressions between the privacy and utility. I can also see a use case for such method (for example the histogram release demonstrated in Sec 4.2), however I think the use cases might be rather limited. Thus I think the method might not be the most striking from usage perspective, but with the analysis it is a solid privacy paper.\n\nPros:\n- (+++) Very clearly written paper\n- (++) Novel privacy analysis in terms of Dirichlet prior parameter $\\alpha$\n- (++) Utility analysis in terms of sample size\n- (+) Emprical results showing improvement over Gaussian mech.\n\nCons:\n- (--) Use case might be limited\n- (--) I'm not sure what is the actual difference between uses in 4.1 and 4.2\n\nMinor comments/questions:\n- Introduction, lines 30-32. Are you talking about drawing from posterior predictive? In that case I think Y should also be drawn for each sample.\n- Theorem 1, proof. Is there really $\\alpha'$ separate from $\\alpha$ or is it a typo?\n- Figure 2, I guess it would make more sense to call the y-axis $\\ell_2$-error instead of $\\ell_2$-accuracy. For me it seems odd to say that \"We see that the $\\ell_2$-accuracy of the Dirichlet mechanism is smaller than that of the Gaussian mechanism for small N when d = 1000.\", when you actually want to point out that your method works better in the small N domain, i.e. it's more \"accurate\".\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers generally appreciated the paper's clean problem formulation, algorithmic result, and analysis. There was consensus that the result is something that should be recorded in the literature. The two main downsides are 1) there is not much conceptual innovation behind the paper's algorithmic approach. Obtaining privacy by sampling once from an updated posterior distribution is a known idea, and the paper's novelty is in the analysis of privacy and utility. 2) Reviewer QwTp pointed out some editorial concerns that should be addressable in a revision of the paper. While the paper is technically sound and should be published, we did not find it exciting enough to meet the bar for NeurIPS.

Technical comment: The authors should justify why they measure utility using expected KL divergence with a particular ordering between P and Q. The way the paper is written, it seems this is just done for mathematical convenience rather than for relevance, e.g., to downstream inference tasks.
Decision: Reject