# on_the_differential_privacy_of_bayesian_inference__016083c6.pdf

On the Differential Privacy of Bayesian Inference

Zuhe Zhang and Benjamin I. P. Rubinstein

School of Mathematics and Statistics, Department of Computing and Information Systems, The University of Melbourne, Australia zhang.zuhe@gmail.com, brubinstein@unimelb.edu.au

Christos Dimitrakakis

Univ-Lille-3, France Chalmers University of Technology, Sweden christos.dimitrakakis@gmail.com

We study how to communicate ﬁndings of Bayesian inference to third parties, while preserving the strong guarantee of differential privacy. Our main contributions are four different algorithms for private Bayesian inference on probabilistic graphical models. These include two mechanisms for adding noise to the Bayesian updates, either directly to the posterior parameters, or to their Fourier transform so as to preserve update consistency. We also utilise a recently introduced posterior sampling mechanism, for which we prove bounds for the speciﬁc but general case of discrete Bayesian networks; and we introduce a maximum-a-posteriori private mechanism. Our analysis includes utility and privacy bounds, with a novel focus on the inﬂuence of graph structure on privacy. Worked examples and experiments with Bayesian naïve Bayes and Bayesian linear regression illustrate the application of our mechanisms.

Introduction We consider the problem faced by a statistician B who analyses data and communicates her ﬁndings to a third party A . While B wants to learn as much as possible from the data, she doesn t want A to learn about any individual datum. This is for example the case where A is an insurance agency, the data are medical records, and B wants to convey the efﬁcacy of drugs to the agency, without revealing the speciﬁc illnesses of individuals in the population. Such requirements of privacy are of growing interest in the learning (Chaudhuri and Hsu 2012; Duchi, Jordan, and Wainwright 2013), theoretical computer science (Dwork and Smith 2009; Mc Sherry and Talwar 2007) and databases communities (Barak et al. 2007; Zhang et al. 2014) due to the impact on individual privacy by real-world data analytics. In our setting, we assume that B is using Bayesian inference to draw conclusions from observations of a system of random variables by updating a prior distribution on parameters (i.e., latent variables) to a posterior. Our goal is to release an approximation to the posterior that preserves privacy. We adopt the formalism of differential privacy to characterise how easy it is for A to discover facts about the individual data from the aggregate posterior. Releasing the posterior permits external parties to make further inferences

Copyright c 2016, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

at will. For example, a third-party pharmaceutical might use the released posterior as a prior on the efﬁcacy of drugs, and update it with their own patient data. Or they could form a predictive posterior for classiﬁcation or regression, all while preserving differential privacy of the original data. Our focus in this paper is Bayesian inference in probabilistic graphical models (PGMs), which are popular as a tool for modelling conditional independence assumptions. Similar to the effect on statistical and computational efﬁciency of non-private inference, a central tenet of this paper is that independence structure should impact privacy. Our mechanisms and theoretical bounds are the ﬁrst to establish such a link between PGM graph structure and privacy.

Main Contributions. We develop the ﬁrst mechanisms for Bayesian inference on the ﬂexible PGM framework (cf. Table 1). We propose two posterior perturbation mechanisms for networks with likelihood functions from exponential families and conjugate priors, that add Laplace noise (Dwork et al. 2006) to posterior parameters (or their Fourier coefﬁcients) to preserve privacy. The latter achieves stealth through consistent posterior updates. For general Bayesian networks, posteriors may be non-parametric. In this case, we explore a mechanism (Dimitrakakis et al. 2014) which samples from the posterior to answer queries no additional noise is injected. We complement our study with a maximum a posteriori estimator that leverages the exponential mechanism (Mc Sherry and Talwar 2007). Our utility and privacy bounds connect privacy and graph/dependency structure, and are complemented by illustrative experiments with Bayesian naïve Bayes and linear regression.

Related Work. Many individual learning algorithms have been adapted to maintain differential privacy, including regularised logistic regression (Chaudhuri and Monteleoni 2008), the SVM (Rubinstein et al. 2012; Chaudhuri, Monteleoni, and Sarwate 2011), PCA (Chaudhuri, Sarwate, and Sinha 2012), the functional mechanism (Zhang et al. 2012) and trees (Jagannathan, Pillaipakkamnatt, and Wright 2009). Probabilistic graphical models have been used to preserve privacy. Zhang et al. (2014) learned a graphical model from data, in order to generate surrogate data for release; while Williams and Mc Sherry (2010) ﬁt a model to the response

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)

of private mechanisms to clean up output and improve accuracy. Xiao and Xiong (2012) similarly used Bayesian credible intervals to increase the utility of query responses. Little attention has been paid to private inference in the Bayesian setting. We seek to adapt Bayesian inference to preserve differential privacy when releasing posteriors. Dimitrakakis et al. (2014; 2015) introduce a differentiallyprivate mechanism for Bayesian inference based on posterior sampling a mechanism on which we build while Zheng (2015) considers further reﬁnements. Wang, Fienberg, and Smola (2015) explore Monte Carlo approaches to Bayesian inference using the same mechanism, while Mir (2012) was the ﬁrst to establish differential privacy of the Gibbs estimator (Mc Sherry and Talwar 2007) by minimising risk bounds. This paper is the ﬁrst to develop mechanisms for differential privacy under the general framework of Bayesian inference on multiple, dependent r.v. s. Our mechanisms consider graph structure and include a purely Bayesian approach that only places conditions on the prior. We show how the (stochastic) Lipschitz assumptions of Dimitrakakis et al. (2014) lift to graphs of r.v. s, and bound KL-divergence when releasing an empirical posterior based on a modiﬁed prior. While Chaudhuri, Monteleoni, and Sarwate (2011) achieve privacy in regularised Empirical Risk Minimisation through objective randomisation, we do so through conditions on priors. We develop an alternate approach that uses the additive-noise mechanism of Dwork et al. (2006) to perturb posterior parameterisations; and we apply techniques due to Barak et al. (2007), who released marginal tables that maintain consistency in addition to privacy, by adding Laplace noise in the Fourier domain. Our motivation is novel: we wish to guarantee privacy against omniscient attackers and stealth against unsuspecting third parties.

Problem Setting Consider a Bayesian statistician B estimating the parameters θ of some family of distributions FΘ = { pθ : θ Θ } on a system of r.v. s X = { Xi : i I }, where I is an index set, with observations denoted xi Xi, where Xi is the sample space of Xi. B has a prior distribution1 ξ on Θ reﬂecting her prior belief, which she updates on an observation x to obtain posterior

B pθ (x) dξ (θ)

φ(x) , B SΘ

Θ pθ (x) dξ (θ). Posterior updates are iterated over an i.i.d. dataset D D = (

i Xi)n to ξ( | D). B s goal is to communicate her posterior distribution to a third party A , while limiting the information revealed about the original data. From the point of view of the data provider, B is a trusted party.2 However, she may still inadvertently reveal information. We assume that A is computationally unbounded, and has knowledge of the prior ξ and the family

1Precisely, a probability measure on a σ-algebra (Θi, SΘi). 2Cryptographic tools for untrusted B do not prevent information leakage to A cf. e.g., (Pagnin et al. 2014).

FΘ. To guarantee that A can gain little additional information about D from their communication, B uses Bayesian inference to learn from the data, and a differentially-private posterior to ensure disclosure to A is carefully controlled.

Probabilistic Graphical Models Our main results focus on PGMs which model conditional independence assumptions with joint factorisation

i I pθ (xi | xπi) , xπi = { xj : j πi } ,

where πi are the parents of the i-th variable in a Bayesian network a directed acyclic graph with r.v. s as nodes. Example 1. For concreteness, we illustrate some of our mechanisms on systems of Bernoulli r.v. s Xi {0, 1}. In that case, we represent the conditional distribution of Xi given its parents as Bernoulli with parameters θi,j [0, 1] :

(Xi | Xπi = j) Bernoulli(θi,j) .

The choice of conjugate prior ξ(θ) = i,j ξi,j(θi,j) has Beta marginals with parameters αi,j, βi,j, so that:

(θi,j | αi,j = α, βi,j = β) Beta(α, β) .

Given observation x, the updated posterior Beta parameters are αi,j := αi,j + xi and βi,j := βi,j + (1 xi) if xπi = j.

Differential Privacy B communicates to A by releasing information about the posterior distribution, via randomised mechanism M that maps dataset D D to a response in set Y. Dwork et al. (2006) characterise when such a mechanism is private: Deﬁnition 1 (Differential Privacy). A randomised mechanism M : D Y is (ϵ, δ)-DP if for any neighbouring D, D D, and measurable B Y:

P[M(D) B] eϵP[M( D) B] + δ,

where D = (xi)n i=1, D = ( xi)n i=1 are neighbouring if xi = xi for at most one i. This deﬁnition requires that neighbouring datasets induce similar response distributions. Consequently, it is impossible for A to identify the true dataset from bounded mechanism query responses. Differential privacy assumes no bounds on adversarial computation or auxiliary knowledge.

Privacy by Posterior Perturbation One approach to differential privacy is to use additive Laplace noise (Dwork et al. 2006). Previous work has focused on the addition of noise directly to the outputs of a non-private mechanism. We are the ﬁrst to apply Laplace noise to the posterior parameter updates.

Laplace Mechanism on Posterior Updates Under the setting of Example 1, we can add Laplace noise to the posterior parameters. Algorithm 1 releases perturbed parameter updates for the Beta posteriors, calculated simply by counting. It then adds zero-mean Laplace-distributed noise

DBN only Privacy Utility type Utility bound

Laplace (ϵ, 0) closeness of posterior O (mn ln n) 1 exp nϵ

O (mn ln n) ln δ

Fourier (ϵ, 0) close posterior params 4|NI|

ϵ 2|πi| log |NI|

Sampler (2L, 0) if Lipschitz; or (0,

M/2) stochastic Lipschitz

expected utility functional wrt posterior

ln(1/δ)/N (Dimitrakakis et al. 2015)

MAP (ϵ, 0) closeness of MAP P(Sc 2t) exp( ϵt)/ξ (St)

Table 1: Summary of the privacy/utility guarantees for this paper s mechanisms. See below for parameter deﬁnitions.

Algorithm 1 Laplace Mechanism on Posterior Updates

1: Input data D; graph I, {πi | i I}; parameter ϵ > 0 2: calculate posterior updates: Δαi,j, Δβi,j for all i I, j {0, 1}|πi|

3: perturb updates: Δα i,j Δαi,j + Lap 2|I|

Δβ i,j Δβi,j + Lap 2|I|

4: truncate: Z(1) i,j 1[0,n](Δα i,j), Z(2) i,j 1[0,n](Δβ i,j)

5: output Zi,j = (Z(1) i,j , Z(2) i,j )

to the updates Δω = ( , Δαi,j, Δβi,j, ). This is the ﬁnal dependence on D. Finally, the perturbed updates Δω are truncated at zero to rule out invalid Beta parameters and are upper truncated at n. This yields an upper bound on the raw updates and facilitates an application of Mc Diarmid s bounded-differences inequality (cf. full report Zhang, Rubinstein, and Dimitrakakis 2015) in our utility analysis. Note that this truncation only improves utility (relative to the utility pre-truncation), and does not affect privacy.

Privacy. To establish differential privacy of our mechanism, we must calculate a Lipschitz condition for the vector Δω called global sensitivity (Dwork et al. 2006).

Lemma 1. For any neighbouring datasets D, D, the corresponding updates Δω, Δ ω satisfy Δω Δ ω 1 2|I|.

Proof. By changing the observations of one datum, at most two counts associated with each Xi can change by 1.

Corollary 1. Algorithm 1 preserves ϵ-differential privacy.

Proof. Based on Lemma 1, the intermediate Δω preserve ϵ-differential privacy (Dwork et al. 2006). Since truncation depends only on Δω , the Z preserves the same privacy.

Utility on Updates. Before bounding the effect on the posterior of the Laplace mechanism, we demonstrate a utility bound on the posterior update counts.

Proposition 1. With probability at least 1 δ, for δ (0, 1), the update counts computed by Algorithm 1 are close to the non-private counts

where m = i I 2|πi|.

This bound states that w.h.p., none of the updates can be perturbed beyond O(|I|2/ϵ). This implies the same bound on the deviation between Δω and the revealed truncated Z.

Utility on Posterior. We derive our main utility bounds for Algorithm 1 in terms of posteriors, proved in the full report (Zhang, Rubinstein, and Dimitrakakis 2015). We abuse notation, and use ξ to refer to the prior density; its meaning will be apparent from context. Given priors ξi,j(θi,j) = Beta (αi,j, βi,j), the posteriors on n observations are

ξi,j(θi,j|D) = Beta(αi,j + Δαi,j, βi,j + Δβi,j) .

The privacy-preserving posterior parametrised by the output of Algorithm 1 is

ξ i,j(θi,j|D) = Beta αi,j + Z(1) i,j , βi,j + Z(2) i,j .

It is natural to measure utility by the KL-divergence between the joint product posteriors ξ(θ|D) and ξ (θ|D), which is the sum of the component-wise divergences, with each having known closed form. In our analysis, the divergence is a random quantity, expressible as the sum m i,j fi,j(Zi,j), where the randomness is due to the added noise. We demonstrate this r.v. is not too big, w.h.p.

Theorem 1. Let m = i I 2|πi|. Assume that Zi,j are independent and f is a mapping from Zm to R: f( , zi,j, )

i,j fi,j(zi,j). Given δ > 0, we have

f(Z) E(f(Z)) +

i,j ci,j ln δ

where ci,j (2n+1) ln[(αi,j +n+1)+(βi,j +n+1)) and E(fi,j(Zi,j)] n ln((αi,j + Δαi,j)(βi,j + Δβi,j)) = U. Moreover, when n b = 2|I|

ϵ , the bound for expectation can be reﬁned as the following

ln[(αi,j + n + 1)(βi,j + n + 1)] n

The loss of utility measured by KL-divergence is no more than

O (mn ln n) 1 exp nϵ

O (mn ln n) ln δ

with probability at least 1 δ. Note that m depends on the structure of the network: bounds are better for networks with an underlying graph having smaller average in-degree.

Laplace Mechanism in the Fourier Domain Algorithm 1 follows Kerckhoffs s Principle (Kerckhoffs 1883) of no security through obscurity : differential privacy defends against a mechanism-aware attacker. However additional stealth may be required in certain circumstances. An oblivious observer will be tipped off to our privacy-preserving activities by our independent perturbations, which are likely inconsistent with one-another (e.g., noisy counts for X1, X2 and X2, X3 will say different things about X2). To achieve differential privacy and stealth, we turn to Barak et al. (2007) s study of consistent marginal contingency table release. This section presents a particularly natural application to Bayesian posterior updates. Denote by h R{0,1}|I| the contingency table over r.v. s I induced by D: i.e., for each combination of variables j {0, 1}|I|, component or cell hj is a non-negative count of the observations in D with characteristic j. Geometrically h is a real-valued function over the |I|-dimensional Boolean hypercube. Then the parameter delta s of our ﬁrst mechanism correspond to cells of (|πi| + 1)-way marginal contingency tables Cπi(h) where vector πi πi + ei and the projection/marginalisation operator is deﬁned as Cj(h)

η: η,j =γ hη . (1)

We wish to release these statistics as before, however we will not represent them under their Euclidean coordinates but instead in the Fourier basis {f j : j {0, 1}|I|} where

f j γ ( 1) γ,j 2 |I|/2 .

Due to this basis structure and linearity of the projection operator, any marginal contingency table must lie in the span of few projections of Fourier basis vectors (Barak et al. 2007):

Theorem 2. For any table h R{0,1}|I| and set of variables j {0, 1}|I|, the marginal table on j satisﬁes Cj(h) =

γ j f γ, h Cj(f γ).

This states that marginal j lies in the span of only those (projected) basis vectors f γ with γ contained in j. The number of values needed to update Xi is then 2|πi|+1, potentially far less than suggested by (1). To release updates for two r.v. s i, j I there may well be signiﬁcant overlap πi, πj ; we need to release once, coefﬁcients f γ, h for γ in the downward closure of variable neighbourhoods:

Privacy. By (Barak et al. 2007, Theorem 6) we can apply Laplace additive noise to release these Fourier coefﬁcients.

Corollary 2. For any ϵ > 0, releasing for each γ NI the Fourier coefﬁcient f γ, h + Lap 2|NI|ϵ 12 |I|/2 (and Algorithm 2) preserves ϵ-differential privacy.

Remark 1. Since |NI| |I|21+maxi I indeg(i), at worst we have noise scale |I|22+maxi indeg(i) |I|/2/ϵ. This compares favourably with Algorithm 1 s noise scale provided no r.v.

is child to more than half the graph. Moreover the denser the graph the more overlap between nodes parents and the less conditional independence assumed the greater the reduction in scale. This is intuitively appealing.

Consistency. What is gained by passing to the Fourier domain, is that the perturbed marginal tables of Corollary 2 are consistent: anything in the span of projected Fourier basis vectors corresponds to some valid contingency table on I with (possibly negative) real-valued cells (Barak et al. 2007).

Algorithm 2 Laplace Mechanism in the Fourier Domain

1: Input data D; graph I, {πi | i I}; prior parameters α, β 0; parameters t, ϵ > 0

2: deﬁne contingency table h R{0,1}|I| on D 3: deﬁne downward closure NI =

j πi j 4: for γ NI do

5: Fourier coefﬁcient zγ = f γ, h + Lap 2|NI| ϵ2|I|/2

6: end for 7: increment ﬁrst coefﬁcient z0 z0 + 4t|NI|2

ϵ2|I|/2 8: for i I do 9: project marginal for Xi as hi =

γ πi zγCπi(f γ) 10: for j πi do 11: output posterior param αij + hi ei+j, βij + hi j

12: end for 13: end for

Non-negativity. So far we have described the ﬁrst stage of Algorithm 2. The remainder yields stealth by guaranteeing releases that are non-negative w.h.p. We adapt an idea of Barak et al. (2007) to increase the coefﬁcient of Fourier basis vector f 0, affecting a small increment to each cell of the contingency table. While there is an exact minimal amount that would guarantee non-negativity, it is data dependent. Thus our efﬁcient O (|NI|)-time approach is randomised.

Corollary 3. For t > 0, adding 4t|NI|2ϵ 12 k/2 to f 0 s coefﬁcient induces a non-negative table w.p. 1 exp( t).

Parameter t trades off between the probability of nonnegativity and the resulting (minor) loss to utility. In the rare event of negativity, re-running Algorithm 2 affords another chance of stealth at the cost of privacy budget ϵ. We could alternatively truncate to achieve validity, sacriﬁcing stealth but not privacy.

Utility. Analogous to Proposition 1, each perturbed marginal is close to its unperturbed version w.h.p.

Theorem 3. For each i I and δ (0, 1), the perturbed tables in Algorithm 2 satisfy with probability at least 1 δ:

Cπi(h) hi 1 4|NI|

2|πi| log |NI|

δ + t|NI| .

Note that the scaling of this bound is reasonable since the table hi involves 2|πi|+1 cells.

Privacy by Posterior Sampling For general Bayesian networks, B can release samples from the posterior (Dimitrakakis et al. 2014) instead of perturbed samples of the posterior s parametrisation. We now develop a calculus of building up (stochastic) Lipschitz properties of systems of r.v. s that are locally (stochastic) Lipschitz. Given smoothness of the entire network, differential privacy and utility of posterior sampling follow.

(Stochastic) Lipschitz Smoothness of Networks The distribution family {pθ : θ Θ} on outcome space S, equipped with pseudo metric3 ρ, is Lipschitz continuous if Assumption 1 (Lipschitz Continuity). Let d( , ) be a metric on R. There exists L > 0 such that, for any θ Θ:

d(pθ(x), pθ(y)) Lρ(x, y), x, y S.

We ﬁx the distance function d to be the absolute log-ratio (cf. differential privacy). Consider a general Bayesian network. The following lemma shows that the individual Lipschitz continuity of the conditional likelihood at every i I implies the global Lipschitz continuity of the network. Lemma 2. If there exists L = (L1, , L|I|) 0 such that i I, x, y X = |I| i=1 Xi we have d(pθ(xi|xπi), pθ(yi|yπi)) Liρi(xi, yi), then d(pθ(x), pθ(y)) L ρ(x, y) where ρ(x, y) = |I| i=1 ρi(xi, yi). Note that while Lipschitz continuity holds uniformly for some families e.g., the exponential distribution, this is not so for many useful distributions such as the Bernoulli. In such cases a relaxed assumption requires that the prior be concentrated on smooth regions. Assumption 2 (Stochastic Lipschitz Continuity). Let the set of L-Lipschitz θ be

ΘL θ Θ : sup x,y S {d(pθ(x), pθ(y)) Lρ(x, y)} 0

Then there exists constants c, L0 > 0 such that, L L0: ξ(ΘL) 1 e c L. Lemma 3. For the conditional likelihood at each node i I, deﬁne the set Θi,L of parameters for which Lipschitz continuity holds with Lipschitz constant L. If c = (c1, , c|I|) such that i, L L0, ξ(Θi,L) 1 e ci L, then ξ(ΘL) 1 e c L, where c = mini I ci ln |I|/L0 when |I| e L0 mini I ci. Therefore, (Dimitrakakis et al. 2015, Theorem 7) asserts differential privacy of the Bayesian network s posterior. Theorem 4. Differential privacy is satisﬁed using the logratio distance, for all B SΘ and x, y X: 1. Under the conditions in Lemma 2:

ξ(B | x) exp{2Lρ(x, y)}ξ(B | y)

i.e., the posterior ξ is (2 L , 0)-differentially private under pseudo-metric ρ(x, y).

3Meaning that ρ(x, y) = 0 does not necessarily imply x = y.

2. Under the conditions in Lemma 3, if ρ(x, y) (1 δ)c uniformly for all x, y for some δ (0, 1):

|ξ(B | x) ξ(B | y)|

2 max{ρ(x, y), 1}

where M = κ

c + L0( 1 1 e ω + 1) + ln C

+ ln e L0δc(e ω(1 δ) e ω) 1 + e L0(1 δ)c C; constants κ = 4.91081 and ω = 1.25643; C = |I| i Ci; and

Ci = sup x X

pθ i,MLE(xi | xπi)

Θi pθi(xi | xπi)dξ(θi) ,

the ratio between the maximum and marginal likelihoods of each likelihood function. Note that M = O 1

c + ln C + L0 C i.e., the posterior ξ

2 -differentially private under pseudo-metric ρ for ρ(x, y) 1.

MAP by the Exponential Mechanism

As an application of the posterior sampler, we now turn to releasing MAP point estimates via the exponential mechanism (Mc Sherry and Talwar 2007), which samples responses from a likelihood exponential in some score function. By selecting a utility function that is maximised by a target nonprivate mechanism, the exponential mechanism can be used to privately approximate that target with high utility. It is natural then to select as our utility u the posterior likelihood ξ ( |D). This u is maximised by the MAP estimate.

Algorithm 3 Mechanism for MAP Point Estimates

1: Input data D; prior ξ ( ); appropriate smoothness parameters c, L, M > 0; parameters distance r > 0, privacy ϵ > 0 2: calculate posterior ξ (θ|D)

Lr , if Lipschitz continuous

0.5M , if stochastic Lipschitz

4: output ˆθ sampled exp ϵξ(θ|D)

Formally, Algorithm 3, under the assumptions of Theorem 4, outputs response θ with probability proportional to exp(ϵu(D, θ)/2Δ) times a base measure μ(θ). Here Δ is a Lipschitz coefﬁcient for u with sup-norm on responses and pseudo-metric ρ on datasets as in the previous section. Providing the base measure is non-trivial in general, but for discrete ﬁnite outcome spaces can be uniform (Mc Sherry and Talwar 2007). For our mechanism to be broadly applicable, we can safely take μ(θ) as ξ (θ).4

Corollary 4. Algorithm 3 preserves ϵ-differential privacy wrt pseudo-metric ρ up to distance r > 0.

4In particular the base measure guarantees we have a proper density function: if u(D, θ) is bounded by M, then we have normalising constant

θ exp(ϵu(D, θ))μ(θ)dθ exp(Mϵ) < .

0.1 0.2 0.5 1.0 2.0 5.0 10.0

0.0 0.2 0.4 0.6 0.8 1.0

Bayesian Discrete Naive Bayes: Synthetic

privacy budget epsilon (log scale)

classifier accuracy

nonprivate laplace fourier sampler

Figure 1: Effect on Bayesian naïve Bayes predictiveposterior accuracy of varying the privacy level.

0 20 40 60 80 100

0.0884 0.0888 0.0892

Bayesian Linear Regression: Census Data

prior precision (proportional to privacy)

regression MSE

nonprivate sampler

Figure 2: Effect on linear regression of varying prior concentration. Bands indicate standard error over repeats.

Proof. The sensitivity of the posterior score function corresponds to the computed Δ (Dimitrakakis et al. 2015, Theorem 6) under either Lipschitz assumptions. The result then follows from (Mc Sherry and Talwar 2007, Theorem 6).

Utility for Algorithm 3 follows from (Mc Sherry and Talwar 2007), and states that the posterior likelihood of responses is likely to be close to that of the MAP.

Lemma 4. Let θ = maxθ ξ (θ|D) with maximizer the MAP estimate, and let St = {θ Θ : ξ (θ|D) > θ t} for t > 0. Then P(Sc 2t) exp( ϵt)/ξ (St).

Experiments Having proposed a number of mechanisms for approximating exact Bayesian inference in the general framework of probabilistic graphical models, we now demonstrate our approaches on two simple, well-known PGMs: the (generative) naïve Bayes classiﬁer, and (discriminative) linear regression. This section, with derivations in the full report (Zhang, Rubinstein, and Dimitrakakis 2015), illustrates how our ap-

proaches are applied, and supports our extensive theoretical results with experimental observation. We focus on the trade-off between privacy and utility (accuracy and MSE respectively), which involves the (private) posterior via a predictive posterior distribution in both case studies.

Bayesian Discrete Naïve Bayes An illustrative example for our mechanisms is a Bayesian naïve Bayes model on Bernoulli class Y and attribute variables Xi, with full conjugate Beta priors. This PGM directly specialises the running Example 1. We synthesised data generated from a naïve Bayes model, with 16 features and 1000 examples. Of these we trained our mechanisms on only 50 examples, with uniform Beta priors. We formed predictive posteriors for Y |X from which we thresholded at 0.5 to make classiﬁcation predictions on the remaining, unseen test data so as to evaluate classiﬁcation accuracy. The results are reported in Figure 1, where average performance is taken over 100 repeats to account for randomness in train/test split, and randomised mechanisms. The small size of this data represents a challenge in our setting, since privacy is more difﬁcult to preserve under smaller samples (Dwork et al. 2006). As expected, privacy incurs a sacriﬁce to accuracy for all private mechanisms. For both Laplace mechanisms that perturb posterior updates, note that the d Boolean attributes and class label (being sole parent to each) yields nodes |I| = d + 1 and downward closure size |NI| = 2d + 2. Following our generic mechanisms, the noise added to sufﬁcient statistics is independent on training set size, and is similar in scale. t was set for the Fourier approach, so that stealth was achieved 90% of the time those times that contributed to the plot. Due to the small increments to cell counts for Fourier, necessary to achieve its additional stealth property, we expect a small decrease to utility which is borne out in Figure 1. For the posterior sampler mechanism, while we can apply Assumption 2 to a Bernoulli-Beta pair to obtain a generalised form of (ϵ, δ)-differential privacy, we wish to compare with our ϵ-differentially-private mechanisms and so choose a route which satisﬁes Assumption 1 as detailed in the full report (Zhang, Rubinstein, and Dimitrakakis 2015). We trim the posterior before sampling, so that probabilities are lower-bounded. Figure 1 demonstrates that for small ϵ, the minimal probability at which to trim is relatively large resulting in a poor approximate posterior. But past a certain threshold, the posterior sampler eventually outperforms the other private mechanisms.

Bayesian Linear Regression We next explore a system of continuous r.v. s in Bayesian linear regression, for which our posterior sampler is most appropriate. We model label Y as i.i.d. Gaussian with knownvariance and mean a linear function of features, and the linear weights endowed with multivariate Gaussian prior with zero mean and spherical covariance. To satisfy Assumption 1 we conservatively truncate the Gaussian prior (cf. the full report Zhang, Rubinstein, and Dimitrakakis 2015), and sample from the resulting truncated posterior; form a predictive posterior; then compute mean squared error. To evaluate

our approach we used the U.S. census records dataset from the Integrated Public Use Microdata Series (Minnesota Population Center 2009) with 370k records and 14 demographic features. To predict Annual Income, we train on 10% data with the remainder for testing. Figure 2 displays MSE under varying prior precision b (inverse of covariance) and weights with bounded norm 10/

b (chosen conservatively). As expected, more concentrated prior (larger b) leads to worse MSE for both mechanisms, as stronger priors reduce data inﬂuence. Compared with linear regression, private regression suffers only slightly worse MSE. At the same time the posterior sampler enjoys increasing privacy (that is proportional to the bounded norm as given in the full report).

Conclusions We have presented a suite of mechanisms for differentiallyprivate inference in graphical models, in a Bayesian framework. The ﬁrst two perturb posterior parameters to achieve privacy. This can be achieved either by performing perturbations in the original parameter domain, or in the frequency domain via a Fourier transform. Our third mechanism relies on the choice of a prior, in combination with posterior sampling. We complement our mechanisms for releasing the posterior, with private MAP point estimators. Throughout we have proved utility and privacy bounds for our mechanisms, which in most cases depend on the graph structure of the Bayesian network: naturally, conditional independence affects privacy. We support our new mechanisms and analysis with applications to two concrete models, with experiments exploring the privacy-utility trade-off.

Acknowledgements. This work was partially supported by the Swiss National Foundation grant Swiss Sense Synergy CRSII2-154458, and by the Australian Research Council (DE160100584).

References Barak, B.; Chaudhuri, K.; Dwork, C.; Kale, S.; Mc Sherry, F.; and Talwar, K. 2007. Privacy, accuracy, and consistency too: A holistic solution to contingency table release. In PODS 07, 273 282. Chaudhuri, K., and Hsu, D. 2012. Convergence rates for differentially private statistical estimation. In ICML 12. Chaudhuri, K., and Monteleoni, C. 2008. Privacy-preserving logistic regression. In NIPS 08, 289 296. Chaudhuri, K.; Monteleoni, C.; and Sarwate, A. D. 2011. Differentially private empirical risk minimization. Journal of Machine Learning Research 12(Mar):1069 1109. Chaudhuri, K.; Sarwate, A.; and Sinha, K. 2012. Nearoptimal differentially private principal components. In NIPS 12, 989 997. Dimitrakakis, C.; Nelson, B.; Mitrokotsa, A.; and Rubinstein, B. 2014. Robust and private Bayesian inference. In ALT 14. Dimitrakakis, C.; Nelson, B.; Zhang, Z.; Mitrokotsa, A.; and Rubinstein, B. 2015. Differential privacy in a

Bayesian setting through posterior sampling. Technical Report 1306.1066, ar Xiv. Duchi, J. C.; Jordan, M. I.; and Wainwright, M. J. 2013. Local privacy and statistical minimax rates. Technical Report 1302.3203, ar Xiv. Dwork, C., and Smith, A. 2009. Differential privacy for statistics: What we know and what we want to learn. Journal of Privacy and Conﬁdentiality 1(2):135 154. Dwork, C.; Mc Sherry, F.; Nissim, K.; and Smith, A. 2006. Calibrating noise to sensitivity in private data analysis. In TCC 06, 265 284. Jagannathan, G.; Pillaipakkamnatt, K.; and Wright, R. 2009. A practical differentially private random decision tree classiﬁer. In ICDM 09, 114 121. Kerckhoffs, A. 1883. La cryptographie militaire. Journal des sciences militaires IX:5 83 January; 161 191, February. Mc Sherry, F., and Talwar, K. 2007. Mechanism design via differential privacy. In FOCS 07, 94 103. Minnesota Population Center. 2009. Integrated public use microdata series - international: Version 5.0. 2009. https: //international.ipums.org accessed 2015-08-30. Mir, D. 2012. Differentially-private learning and information theory. In Proceedings of the 2012 Joint EDBT/ICDT Workshops, 206 210. ACM. Pagnin, E.; Dimitrakakis, C.; Abidin, A.; and Mitrokotsa, A. 2014. On the leakage of information in biometric authentication. In Indocrypt 2014. Rubinstein, B. I. P.; Bartlett, P. L.; Huang, L.; ; and Taft, N. 2012. Learning in a large function space: Privacy-preserving mechanisms for SVM learning. Journal of Privacy and Conﬁdentiality 4(1). Wang, Y.-X.; Fienberg, S.; and Smola, A. 2015. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In Blei, D., and Bach, F., eds., ICML 15, 2493 2502. Williams, O., and Mc Sherry, F. 2010. Probabilistic inference and differential privacy. In NIPS 10, 2451 2459. Xiao, Y., and Xiong, L. 2012. Bayesian inference under differential privacy. ar Xiv preprint ar Xiv:1203.0617. Zhang, J.; Zhang, Z.; Xiao, X.; Yang, Y.; and Winslett, M. 2012. Functional mechanism: regression analysis under differential privacy. Proc. VLDB Endowment 5(11):1364 1375. Zhang, J.; Cormode, G.; Procopiuc, C. M.; Srivastava, D.; and Xiao, X. 2014. Privbayes: Private data release via bayesian networks. In SIGMOD 14, 1423 1434. Zhang, Z.; Rubinstein, B.; and Dimitrakakis, C. 2015. On the differential privacy of Bayesian inference. Technical Report https://hal.inria.fr/hal-01234215, HAL. Zheng, S. 2015. The differential privacy of Bayesian inference. Bachelor s thesis, Harvard College.