On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis

1 INTRODUCTION

• OPS offers differential privacy under certain conditions, but has poor asymptotic relative efficiency and often relies on artificial constraints.Its privacy properties are also not typically guaranteed for approximate inference.Source: §1 · p. 1
• A privacy-preserving HMM case study analyzes sensitive Iraq and Afghanistan war records disclosed by Wikileaks.Source: §1 · pp. 1–2
• The paper analyzes the privacy cost of posterior sampling for exponential-family posteriors through OPS.Source: §1 · p. 1
• The paper explores a simple Laplace-mechanism alternative to OPS for exponential-family posteriors.It provides theoretical analysis and empirical validation of the method.Source: §1 · p. 1
• Under weak conditions, the Laplace approach is consistent and more data-efficient than OPS.The paper identifies these as advantages of the proposed method.Source: §1 · p. 2
• The paper extends both OPS and Laplace-mechanism methods to approximate inference via MCMC.Source: §1 · pp. 1–2

2.1 DIFFERENTIAL PRIVACY

• Differential privacy limits how much an algorithm’s output probabilities change when one individual’s data point is modified.Source: §2.1 · p. 2

2.1.1 The Laplace Mechanism

• The Laplace mechanism adds Laplace noise to revealed information, with its amount determined by the privacy parameter and the function’s L1 sensitivity.The mechanism is described as producing an ϵ-differentially private output.Source: §2.1.1 · p. 2

2.1.2 The Exponential Mechanism

• The exponential mechanism uses a utility score to produce random outputs that favor high-utility responses while maintaining privacy.Source: §2.1.2 · p. 2

2.1.3 Composition Theorems

• Differential privacy composes additively: combining mechanisms with (ϵ1, δ1) and (ϵ2, δ2) guarantees (ϵ1 + ϵ2, δ1 + δ2)-differential privacy.Source: §2.1.3 · p. 2

2.2 PRIVACY AND BAYESIAN INFERENCE

• Posterior sampling can be viewed as an exponential mechanism with log Pr(θ, X) as its utility; under a bound C on log-likelihood changes, one sample is 2C-differentially private.When each log likelihood is bounded by B, one posterior sample is 4B-differentially private, the OPS case.Source: §2.2 · pp. 2–3
• The privacy parameter trades privacy against fidelity: at ϵ = 0 sampling is uniform, while ϵ = 2△log Pr(θ, X) recovers posterior sampling.For integer q, a budget ϵ′ ≥ 2q△log Pr(θ, X) permits q posterior samples.Source: §2.2 · p. 3
• The exponential mechanism can also be written as a Boltzmann distribution, where lowering ϵ corresponds to increasing temperature.The passage connects higher temperature with faster Markov-chain movement through the state space.Source: §2.2 · p. 3

3.1 THE EXPONENTIAL MECHANISM

• The exponential mechanism fixes the approximate-posterior temperature for a given privacy cost, and its beta-Bernoulli sensitivity is unbounded without truncation.The beta-Bernoulli example uses a truncation point to control sensitivity; with a0 = 0, the standard untruncated beta distribution has unbounded sensitivity.Source: §3.2 · p. 4, §3.1 · p. 4

3.2 THE LAPLACE MECHANISM

• Laplace noise perturbs aggregate sufficient statistics, and their fixed sensitivity makes the noise smaller relative to the total as N increases.For beta posteriors, the L1 sensitivity is 2; unlike exponential-mechanism sensitivity, it does not depend heavily on a truncation point.Source: §3.2 · pp. 4–5
• L1 error versus N shows Laplace sampling overtakes the exponential mechanism after about N = 10 and approaches true-posterior sampling performance as N grows.The exponential mechanism performs better only when the dataset is very small, approximately N = 10.Source: Figure 2 · p. 5, §3.2 · p. 5

3.3 THEORETICAL RESULTS

• The convergence and efficiency results require regularity and asymptotic normality; for beta-Bernoulli models, they apply when 0 < p < 1, but not at p = 0 or 1.Corollary 2 requires finite sufficient-statistic sensitivity and either a minimal exponential family or identifiable parameters.Source: §3.3 · pp. 5–6
• Under Lemma 11’s assumptions, a Laplace-mechanism sample has asymptotic relative efficiency 2, matching posterior sampling; the exponential mechanism’s efficiency is 1 + T.For T > 1, the exponential-mechanism sample remains more spread out than the true posterior as N grows, whereas the Laplace mechanism’s privacy impact on accuracy diminishes.Source: §3.3 · p. 6
• Releasing the full privatized posterior’s mean has asymptotic relative efficiency 1 under Lemma 11’s assumptions.This differs from releasing one sample, whose asymptotic relative efficiency is 2.Source: §3.3 · p. 6

4 PRIVATE GIBBS SAMPLING

• For approximate samplers within L1 distance δ of a private sampler, Wang et al. give a corresponding approximate privacy guarantee, but MCMC convergence is generally not verifiable in practice.The cited results also cover stochastic-gradient MCMC, including SGLD, which converges in distribution to the target posterior.Source: §4 · p. 6
• The section studies Gibbs-sampler privacy under both mechanisms to quantify privacy for real-world MCMC analyses.It obtains the exponential-mechanism guarantee by reinterpreting Gibbs sampling; supplementary materials give guarantees for Metropolis-Hastings and annealed importance sampling.Source: §4 · p. 6

4.1 EXPONENTIAL MECHANISM

• A Gibbs update is an exponential-mechanism instance and is ε-differentially private, with ε determined by the sensitivity of its conditional log probability.The update selects among assignments to the current variable while holding the other variables fixed.Source: §4.1 · p. 7
• When each variable is associated with one data point, a random-sequence Gibbs pass can use parallel composition, while a random scan can benefit from subsampling amplification.These can improve privacy cost over simple additive composition.Source: §4.1 · p. 7

4.2 LAPLACE MECHANISM

• One Laplace-mechanism release of sufficient statistics costs ε and supports the entire MCMC run without further privacy cost or a convergence requirement.This is typically cheaper in privacy budget than paying for every Gibbs update; Figure 3 shows Iraq HMM state assignments at ε = 5.Source: §4.2 · p. 7, Figure 3 · p. 7
• The Laplace approach applies when aggregate sufficient statistics are large relative to noise; latent-variable models typically need many data points per latent variable.The section gives HMMs with multiple emissions per timestep as an example.Source: §4.2 · p. 7

5 CASE STUDY: WIKILEAKS IRAQ & AFGHANISTAN WAR LOGS

• Because the war logs were publicly available, the authors caution that evaluation and other manuscript elements may reveal information even when the models are differentially private.Source: §5 · p. 8
• The HMMs used non-textual war-log fields, with one monthly timestep and one chain per region; the study describes reports spanning Afghanistan and Iraq from 2004–2009.The models were trained for 200 Gibbs iterations, with 100 burn-in iterations; Laplace overhead was paid up front, while OPS roughly doubled runtime.Source: §5 · pp. 7–8
• The privacy-preserving model assigned substantial data to only 2–3 of 10 states, unlike the non-private HMM, which fit all 10.The authors suggest Laplace noise may act as a regularizer, while noting it could provide more regularization than desired.Source: §5 · p. 8
• In Iraq, State 2 predominated across most regions before shifting to State 1 after the 2007 troop surge, typically after troops peaked in September–November.State 1 most often corresponded to friendly action, cache found/cleared, and enemy casualties; State 2 to explosive hazards, IED explosions, and civilian casualties.Source: §5 · p. 8, Figure 4 · p. 8, Figure 5 · p. 8
• For Afghanistan, enemy casualty rates, including detainments, were below friendly/host casualties in every latent state and below civilian casualties in two of three states.Figure 6 compares log-likelihood results for Naive Bayes on Afghanistan and HMMs on Afghanistan and Iraq.Source: §5 · p. 9, Figure 6 · p. 9
• Laplace outperformed OPS for Naive Bayes and for Iraq HMMs, particularly under high privacy; OPS was competitive for the lower-data Afghanistan HMM.The Naive Bayes comparison used corpus-wide counts, a high-data regime; Iraq had more data per timestep than Afghanistan.Source: §5 · p. 9

6 CONCLUSION

• The paper studies posterior sampling’s practical limitations and analyzes a Laplace-mechanism alternative theoretically and empirically.Source: §6 · p. 9
• The authors illustrate the Laplace mechanism’s benefits in privacy-preserving Bayesian analysis of sensitive war records.Source: §6 · p. 9
• The paper identifies whether a broad class of private methods is asymptotically efficient as an open question.Source: §6 · p. 9

Supplementary Material

• Figure 8 depicts an adversary greedily adding data points to increase the dataset-specific privacy cost of posterior sampling via the exponential mechanism.Source: Figure 8 · p. 11

A ADVERSARIAL DATA EXPERIMENT

• As observations increase, dataset-specific posterior-sampling privacy cost can approach the exponential mechanism’s worst-case cost in some cases.Source: A ADVERSARIAL DATA EXPERIMENT · p. 11
• A greedy adversary adds Bernoulli successes or failures, selecting the outcome with the highest local privacy cost found by grid search.Source: A ADVERSARIAL DATA EXPERIMENT · p. 11
• The adversary can approach the worst case by manipulating the posterior partition function, which contributes one of the two worst-case privacy-cost terms.The other term comes from the difference between log-likelihoods, for which the worst-case parameter can be drawn.Source: A ADVERSARIAL DATA EXPERIMENT · p. 11

• The section provides proofs for the results presented in Section 3.3.Source: B PROOFS OF THEORETICAL RESULTS · p. 11

B.1 PROOF OF LAPLACE MECHANISM ASYMPTOTIC KL-DIVERGENCE

• For minimal exponential families, the log-normalizer is strictly convex, the mean sufficient statistics identify θ bijectively, and the associated conjugate prior family is also minimal.The proof invokes these standard algebraic properties to establish its later results.Source: §B.1 · p. 12
• A finite perturbation γ yields small KL divergence when the log-normalizer Hessian is small along the parameter segment, and large-data posteriors have low covariance over T(θ).The proof connects low covariance to the Hessian bound needed for the perturbation result.Source: §B.1 · pp. 12–13
• Strict concavity of the conjugate-prior log density makes any interior local mode the unique global mode, which the proof uses in its covariance analysis.The mode is well-defined for natural parameters in the interior of the valid parameter space.Source: §B.1 · p. 13
• The perturbed and noiseless posteriors have KL divergence tending to zero as N grows when the data are i.i.d. from a minimal exponential family and the prior and model satisfy regularity conditions.The conditions include differentiability of A(θ), a positive lower bound on the determinant of the sufficient-statistic covariance near θ0, and an integrable prior supported near the posterior mode; the perturbation distribution is independent of N and has finite covariance.Source: §B.1 · p. 15
• Finite variance of the mechanism randomness γ makes the expectation bound integrable, and Fatou’s Lemma plus nonnegative KL divergence establishes the desired zero limit.The argument extends the fixed-γ result to expectation over γ and the data X.Source: §B.1 · p. 16
• With finite sufficient-statistic sensitivity, the Laplace mechanism meets Lemma 11’s noise requirements when the exponential family is minimal or its parameters are identifiable.For a non-minimal family, the equivalent minimal parameterization preserves noise independent of N and with finite covariance.Source: §B.1 · pp. 16–17
• Under Lemma 11’s assumptions, the Laplace mechanism’s asymptotic posterior is N(θ0, 2I^-1/N), and a single sample has asymptotic relative efficiency 2.The proof establishes convergence in KL to the unperturbed posterior, which converges to the same distribution under the Bernstein–von Mises theorem.Source: §B.1 · p. 17
• Higher-order regularity assumptions yield a uniform bound ||∇²ψ log Fk(ψ/k)|| ≤ C/k for sufficiently large k across a neighborhood of Y0.This adapted Laplace-approximation argument supplies the covariance bounds used in the proof.Source: §B.1 · pp. 18, 20

C PRIVACY PROPERTIES OF OTHER MCMC ALGORITHMS

• The next subsection examines the privacy costs of Metropolis–Hastings and annealed importance sampling, in addition to Gibbs sampling.Gibbs sampling was treated in the main manuscript as an instance of the exponential mechanism.Source: C PRIVACY PROPERTIES OF OTHER MCMC… · p. 20

C.1 METROPOLIS-HASTINGS UPDATES

• A Metropolis update is (ε, δ)-differentially private under the theorem’s stated temperature and rejection-probability conditions.The accept/reject decision prevents bounding rejection-probability ratios across neighboring databases, while rare rejections permit the approximate guarantee.Source: §C.1 · p. 20
• Meaningful privacy requires δ to be very small, so this guarantee may not typically yield a practical privacy-preserving sampling algorithm.Source: §C.1 · pp. 20–21

C.2 ANNEALED IMPORTANCE SAMPLING

• AIS anneals from a high-temperature distribution toward the posterior, trading fidelity against privacy cost while high-temperature chains also mix more rapidly.The intermediate distributions vary ε, and samples receive importance weights to correct for annealing.Source: §C.2 · p. 21
• AIS privacy costs compose across Gibbs updates, with parallel composition available when each update depends on only one data point.Source: §C.2 · p. 21
• At the end of AIS, normalized importance weights have L1 sensitivity at most 2 and can be released with the Laplace mechanism.Alternatively, samples can be resampled according to a protected approximation of the weight distribution.Source: §C.2 · p. 21

D PROOF OF THEOREM C.1

• The proof compares probabilities of the accept and reject outcomes for neighboring databases to establish the Metropolis–Hastings privacy result.It considers the outcomes (accept, reject) together with the new parameter value.Source: D PROOF OF THEOREM C.1 · p. 21

D.1 ACCEPT OUTCOME

• For an accepted move, cancelling the log transition probabilities bounds the full-output probability ratio and gives pure-ε privacy.The proof first bounds the acceptance-probability log ratio by ε for a fixed proposal.Source: §D.1 · p. 22

D.2 REJECT OUTCOME

• The rejection outcome satisfies the (ε, δ)-criterion because its probability is bounded by δ under the stated assumptions.A rejection outcome that would violate ε-differential privacy therefore has probability less than δ.Source: §D.2 · p. 22
• The HMM Gibbs updates marginalize the transition matrix and use transition counts that exclude the state currently being updated.The emission parameters have conjugate updates; α and β are Dirichlet concentration parameters.Source: E DETAILS OF WIKILEAKS WAR LOGS HMM · p. 23

E.1 PRESERVING PRIVACY

• Laplace privatization adds noise to sufficient-statistic count vectors with L1 sensitivity 2, and the resulting private counts can be reused across Gibbs updates.The private counts are computed once at the beginning and used for updates to both latent states and emission parameters.Source: §E.1 · p. 24

E.2 EXPERIMENTAL DETAILS

• Casualty fields are binarized or merged into indicators; Iraq data omit the unavailable fifth month, final year for most regions, and two sparse regions.The omitted regions are MND-S and MND-NE.Source: §E.2 · p. 24
• Held-out log-likelihood is averaged over five splits, each withholding 10% of region/timestep pairs for testing.OPS truncated-Dirichlet Gibbs updates use sequential draws based on truncated Beta distributions.Source: §E.2 · p. 24
• Figures show state assignments for Iraq and Afghanistan under the Laplace mechanism and OPS, with parameters also shown for the OPS models.Figure 9 is identified as held-out log-likelihood results, but the supplied passages do not state comparative values.Source: §E.2 · p. 24, Figure 10 · p. 25, Figure 11 · p. 26