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
36
39
40
41
42
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.
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, (xx)== = 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": "eVWYB8KVhBt", "reviewer": "Reviewer_pz6h", "summary": "This paper studies the privacy of releasing a sample from the Dirichlet posterior. The paper shows for the Dirichlet posterior sampling with prior set to be $\\mathrm{Dirichlet}(\\alpha)$, that Dirichlet posterior sampling  satisfies a version of truncated concentrated Differential Privacy(tCDP). Now, using the relationship between tCDP and approximate DP established in Bun et al. (2018), the paper derives the approximate differential privacy of the Dirichlet Posterior sampling. \n\nGiven the result, the paper studies the utility of Dirichlet posterior sampling in 2 contexts:\n1. One is interested in sampling for the posterior but changing the prior from $Dirichlet (\\alpha)$ to $Dirichlet (\\alpha’)$, such that $\\alpha_i' > \\alpha_i$ so as to increase the privacy preserving properties of the the posterior sampling. In this context, the paper derives sample complexity bounds such that $D_{KL}(\\mathrm{Dirichlet}(\\mathbf{x} + \\alpha)|| \\mathrm{Dirichlet}(\\mathbf{x} + \\alpha') )<\\varepsilon$.\n2. One is interested in releasing the normalized histogram $\\mathbf{p} = \\mathbf{x}/N$. One can privately release it by sampling from the Dirichlet posterior $Y \\sim \\mathrm{Dirichlet}(\\mathbf{x}+ \\alpha)$. The paper derives sample complexity bounds to incur small error $\\ell_\\infty$ norm. Authors also point out that one can get better sample complexity with Gaussian mechanism where Dirichlet posterior sampling outperforms Gaussian mechanism in small data regime.  \n\n", "questions": "", "limitations": "", "rating": 4, "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": "\nThe key technical contribution of the paper is the derivation of privacy properties which is Theorem 1. The result follows by taking the second order Taylor approximation of the Renyi divergence of the Dirichlet distribution which is cleverly written so as to express the result as a polygamma function which can later be bounded. \n\nOverall I believe that this paper is still a work in progress where authors need to find away to better interpret privacy preserving properties of the Dirichlet Posterior sampling. The main result is difficult to interpret, even when written in terms of approximate differential privacy $(\\varepsilon, \\delta)$-DP. The right plot in Figure 1, where the authors plot how $\\delta$ changes as a function of $\\varepsilon$, I can find a prior that actually preserves privacy with high probability and both $\\varepsilon$ and $\\delta$ are large. Authors need to add a discussion on how large the contribution from the prior needs to be for the privacy to be preserved. \n\nI also had difficulty understanding the utlity and privacy tradeoff discussed in the section 4.1. The sample complexity result is just a function of the parameter of the prior $\\alpha'$ and $\\alpha$ which is typically chosen a-priori. I don't see the utility in approximating $\\alpha_m' - \\alpha_m$ by privacy parameters when I can explicitly compute it. I am not sure how I am supposed to interpret the high-privacy and low-privacy regime.\n\nFinally, for the problem of releasing normalized histograms, perhaps the authors should compute the error in terms of $\\ell_1$ norm as it would measure the total variation distance between the two distributions, where reading $\\ell_\\infty$ is a bit unnatural when comparing two probability distributions. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes authors have addressed the limitations and potential societal impacts of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "L5D3y9dFfU", "reviewer": "Reviewer_9me5", "summary": "This paper focuses specifically on the Dirichlet posterior sampling of the differential privacy and its privacy guarantees. The authors derive a simple privacy guarantee of the Dirichlet posterior sampling which effectively allows to analyze its utility in various settings and provides accuracy guarantees of the Dirichlet posterior sampling.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 written. Theorem 1 clearly characterizes the conditions and the Dirichlet sampling for a valid truncated concentrated differential privacy. In addition, the guaranteed upper bound is simply defined by a log-gamma function (derivative), which independent of the sample statistics. In Theorem 2, the authors convert the tCDP guarantee to an approximate DP guarantee. In Theorem 3, it proves that in the case of multinomial, the KL-divergence between true distribution and the sampled distribution is small when the sample size is large, and the pi’s are evenly distributed. In Theorem 4, the accuracy guarantee of the private normalized histogram is bounded. Both high-privacy and low-privacy regimes are analyzed for Theorem 3 and 4.\n\nTo be honest, I didn't actively follow the research of the area in DP for many years. I would like to see the comments from other experienced reviewers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "36Y0X7XT1fA", "reviewer": "Reviewer_ZYMd", "summary": "This paper provides a posterior sampling mechanism for the Dirichlet distribution achieving tCDP and approximate DP privacy, relying on modifying the alpha parameters. It includes an application on histogram release.\n\nThe response addressed my comments.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "This paper provides a posterior sampling mechanism for the Dirichlet distribution achieving tCDP and approximate DP privacy, relying on modifying the alpha parameters. It includes an application on histogram release.\n\nAlthough the contribution is somewhat narrow, the paper is well-written and the results are interesting enough to be published. Dirichlet sampling for DP has remained an open problem for some years, so this paper is welcome. On the negative side, some more complex applications might have been good to look at. Some detailed comments:\n\nl.72 DNZMR17 does give (0,\\delta)-DP for the Beta distribution, which should be easily extensible to the Dirichlet. To quote the paper:\n> as Zheng (2015) shows, this result is essentially unimprovable with direct posterior sampling unless the prior is trimmed.\n\nThis seems to be the approach you are essentially using in your paper, but instead of trimming the prior you just add something to the prior parameters.\n\nl.81 the posterior sampling with the RDP > posterior sampling for RDP\n\nl.89 The critique of MKAGV08 wrt the number of samples is imprecise. Do you mean the number of samples from the Dirichlet  the multinomial, or both?\n\nl. 208-216. It is a bit confusing that $\\gamma, \\delta$ are functions of each other and $f$ is a function of $\\gamma$ only. In particular, in (7), do you assume that $\\delta = exp(-\\gamma^2/2 \\Delta^2_2 \\psi'(\\alpha_m - \\gamma) / \\Delta_\\infty^2)$?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As the authors note, the formal privacy guarantees of any given algorithm must be carefully evaluated for practical evaluation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proves differential privacy of posterior sampling from a Dirichlet distribution. The reviewers had somewhat different opinions of the paper, with scores of 4, 6, 7. All reviewers found the results to be correct and claims well supported. Reviewer pz6h primarily criticized the interpretability of the theoretical results and felt the paper was a work in progress. Reviewer ZYMd felt the paper was well-written and interesting enough to be published, but found the scope of the contribution narrow and felt more complex applications could have been considered. The meta-reviewer agrees Reviewer ZYMd that the results seem correct and publishable, but finds the significance relatively low given the narrow scope of the problem. Thus, given the extremely high bar for acceptance to this year's NeurIPS conference, I recommend reject.
Decision: Reject