PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Differential Privacy through Posterior Sampling

Christos Dimitrakakis, Blaine Nelson, and Zuhe Zhang, Aikaterini Mitrokotsa, Benjamin Rubinstein

arXiv:1306.1066v5stat.MLcs.LG

TL;DR

The paper asks whether Bayesian inference itself can provide private access to sensitive data. It uses suitable priors and posterior sampling to answer queries, showing that Bayesian inference can be robust and private while privacy and utility can be traded off through the number of samples.

  • Problem

    The paper asks whether Bayesian inference can provide private access to data without modifying the inference procedure.

    Source: §1 · p. 2

  • Method

    It analyzes prior and likelihood conditions for privacy and robustness, then uses posterior sampling to answer queries within a decision-theoretic framework.

    Source: §1 · pp. 3–4, §2.3 · p. 11

  • Results

    Under concentration conditions on the prior, Bayesian inference is robust and private, and posterior sampling supports query responses with privacy and utility traded off by sample count.

    Source: §2.3 · p. 11, §6 · p. 21

  • Takeaways & Limitations

    The framework can guide how much querying access to grant while guaranteeing privacy, and may serve as a building block for private Bayesian inference.

    Source: §6 · p. 21

    Increasing the prior concentration parameter improves privacy but can inhibit learning, so its choice involves a privacy–learning trade-off.

    Source: §6.2 · p. 24

Abstract

from arXiv · show

Differential privacy formalises privacy-preserving mechanisms that provide access to a database. We pose the question of whether Bayesian inference itself can be used directly to provide private access to data, with no modification. The answer is affirmative: under certain conditions on the prior, sampling from the posterior distribution can be used to achieve a desired level of privacy and utility. To do so, we generalise differential privacy to arbitrary dataset metrics, outcome spaces and distribution families. This allows us to also deal with non-i.i.d or non-tabular datasets. We prove bounds on the sensitivity of the posterior to the data, which gives a measure of robustness. We also show how to use posterior sampling to provide differentially private responses to queries, within a decision-theoretic framework. Finally, we provide bounds on the utility and on the distinguishability of datasets. The latter are complemented by a novel use of Le Cam's method to obtain lower bounds. All our general results hold for arbitrary database metrics, including those for the common definition of differential privacy. For specific choices of the metric, we give a number of examples satisfying our assumptions.

1. Introduction

The paper asks whether Bayesian inference can provide differentially private access to sensitive data without modifying the learning framework. It shows that suitable priors and posterior sampling can support private query responses, while connecting privacy to robustness and utility.

1. Introduction

  • The decision-theoretic setting models an untrusted party sending queries and utility functions, with responses chosen to maximize utility using the posterior.The posterior is not released directly.Source: §1 · pp. 2–3
  • An informative prior weakens the posterior’s dependence on data, and suitable priors or likelihood families make small dataset changes yield small posterior changes.The paper characterizes this robustness in terms of KL divergence.Source: §1 · pp. 3–4
  • A single set of posterior samples serves as a private surrogate for the exact posterior and supports arbitrarily many queries with bounded privacy budget and good utility.Responses depend on the posterior through that sample set.Source: §1 · p. 3
  • The framework generalizes differential privacy to arbitrary dataset distances, outcome spaces, and distribution families, including non-i.i.d. and non-tabular data.The paper gives examples including discrete Bayesian networks.Source: §1 · pp. 2, 4
  • Posterior sampling provides private query responses without modifying the Bayesian learning framework.The paper also gives necessary and sufficient conditions for differentially private Bayesian inference.Source: §1 · p. 4
  • The paper bounds how readily an adversary can distinguish nearby datasets and provides finite-sample guidance on the number of posterior samples needed.It also develops lower bounds for distinguishability.Source: §1 · pp. 3–4

2. Problem Setting

The paper studies whether a Bayesian statistician can answer an untrusted party’s queries usefully without revealing sensitive information in the data. It asks whether choosing a prior can protect information from even a computationally unbounded querier.

2. Problem Setting

  • The statistician must balance useful query responses against revealing private information about the original data.The examples contrast population-level queries with whether a particular person has a disease.Source: §2 · p. 4
  • The central question is whether a prior can make decisions derived from the posterior differentially private against a computationally unbounded querier.The querier is untrusted.Source: §2 · pp. 4–5

2.1 Definitions and Notation

The framework treats datasets as elements of an arbitrary space, builds Bayesian posteriors from a prior and observed data, and defines privacy through a dataset pseudometric that also supports composition.

2.1 Definitions and Notation

  • A dataset space S can have arbitrary structure, including observation sequences, social-network data, or mobility traces.The framework does not require datasets to be product spaces.Source: §2.1 · p. 5

2.1.1 Distances Between Datasets

  • A pseudometric ρ measures dataset distance, allowing privacy and robustness guarantees to reflect different notions of dataset similarity.It also supports different notions of attacker knowledge.Source: §2.1.1 · p. 5, §2.1.3 · p. 7

2.1.2 Bayesian Inference

  • Bayesian inference combines a prior ξ over parameters with observed data x to form the posterior distribution ξ(· | x).The paper illustrates the setup with a finite Bernoulli family and a uniform prior.Source: §2.1.2 · pp. 5–6

2.1.3 Privacy

  • Differential privacy under ρ compares output distributions for any dataset pair, and independent private mechanisms compose by adding their ϵ and δ guarantees.The usual Hamming-neighbour definition is a special case of this metric-based formulation.Source: §2.1.3 · p. 7

2.2 Our Main Assumptions

The section uses likelihood smoothness, either uniform across parameters or concentrated under the prior, to obtain posterior guarantees; it also identifies necessary conditions and restrictions on dataset metrics.

2.2 Our Main Assumptions

  • The assumptions require likelihood smoothness across parameters or sufficient prior mass on parameters with smaller Lipschitz constants.Uniform smoothness can be difficult to satisfy, motivating the weaker stochastic Lipschitz condition.Source: §2.2 · p. 8
  • Among the two families, Δ=0.2 has about half the Lipschitz constant of Δ=0.05; using prior ξ(θ) ∝ exp(−ℓ(θ)) shifts both lower bounds upward, corresponding to a higher c in Assumption 2.Source: §2.2 · pp. 9–10

2.2.1 Necessary Conditions

  • Differential privacy requires either the first smoothness condition or a related condition on likelihood marginals for every dataset pair; the second condition alone is insufficient.The first condition is sufficient, whereas the second condition by itself is too weak.Source: §2.2.1 · p. 10

2.2.2 The Choice of Metric and Sufficient Statistics

  • A metric based on a statistic τ must preserve the information needed for inference: equal statistic values imply equal data probabilities, and privacy requires equal posteriors.The paper states that τ must be sufficient for the assumptions and Bayes-sufficient for differential privacy.Source: §2.2.2 · pp. 10–11

2.3 Summary of Results

Under the stated assumptions, the results link posterior robustness and differential privacy to posterior sampling, while also addressing dataset distinguishability and the utility–privacy trade-off.

2.3 Summary of Results

  • Informative priors yield posteriors that are robust in KL-divergence to small changes in the data.The results summary presents this as the first guarantee under the stated assumptions.Source: §2.3 · p. 11
  • The results also characterize utility–privacy trade-offs and bound how easily an adversary can distinguish similar datasets from posterior samples.The summary lists both upper and lower bounds for distinguishability.Source: §2.3 · p. 11
  • With a prior satisfying Assumption 1 and utility bounded in [0, 1], posterior sampling with N samples is 2NL-differentially private.The claim compares B’s prior with A’s preferred prior ξ⋆.Source: §2.3 · p. 11

3. Robustness of the Posterior Distribution

The section establishes posterior robustness by bounding the KL divergence between posteriors for nearby datasets under either of two assumptions.

3. Robustness of the Posterior Distribution

  • Under either of the stated assumptions, the posterior changes little in KL-divergence when the dataset changes slightly.The theorem treats assumptions involving pseudo-metric ρ and either L or c.Source: §3 · pp. 11–12
  • The two robustness bounds use different conditions: one involves a Lipschitz constant L, while the other involves c.The theorem presents the conditions separately.Source: §3 · p. 12
  • Under the second condition, increasing c reduces prior mass on large-L parameters and improves robustness, though it may decrease efficiency.The prior’s mass on maximum-likelihood estimators also affects the bound.Source: §3 · p. 12

4. Privacy and Utility

The section characterizes privacy and utility for posterior distributions and posterior sampling, with guarantees depending on the assumptions and the number of samples. It also bounds dataset distinguishability and develops a prior-and-sample-size trade-off, including a Le Cam approach to lower bounds.

4.1 Differential Privacy of Posterior Distributions

  • Posterior differential privacy depends on which assumption holds, and under Assumption 2 the posterior is also randomly differentially private.The randomized guarantee is stated under pseudo-metric ρ with c > 1 and L ≥ L0 > 0.Source: §4.1 · pp. 12–13

4.2 Posterior Sampling Mechanism

  • Reusing a fixed set of posterior samples supports adaptive queries with a bounded privacy budget, while the returned utility is within O of optimal with probability at least 1 − δ.The number of samples controls the privacy–utility trade-off; the supplied bound does not specify the O term.Source: §4.2 · pp. 13–15

4.3 Distinguishability of Datasets

  • Smoother likelihoods or greater prior concentration on them increase the effort required to distinguish datasets and reduce posterior sensitivity.The section also gives a distinguishability condition in terms of dataset distance, sample count, L, and δ.Source: §4.3 · pp. 15–16

4.4 Trading off Utility and Privacy

  • Privacy can be tuned through the model family, prior, or posterior sample count; with the prior fixed, increasing the sample count trades privacy for utility.Restricting the prior to ΘL yields a 2LN-differential privacy guarantee for N samples.Source: §4.4 · pp. 16–17

4.5 Lower Bounds

  • Le Cam’s method is adapted by treating datasets as the parameter space and posterior measures as the indexed family of probability measures.The resulting bounds depend on the family, prior, and metric; the paper does not work out specific rates here.Source: §4.5 · pp. 17–18

5. Examples Satisfying our Assumptions

The examples give sufficient conditions on priors and likelihood families for privacy guarantees, including cases with non-i.i.d. data and non-product observation spaces. They illustrate how the guarantees vary with the metric, parameter restrictions, and prior.

5. Examples Satisfying our Assumptions

  • The examples give sufficient prior-concentration conditions for privacy, following the pattern of specifying mechanism parameters that guarantee a desired privacy level.The examples conventionally assume bounded data and sometimes use priors trimmed to a parameter interval.Source: §5 · p. 18
  • Trimmed exponential conjugate priors satisfy Assumption 2 for exponential and Laplace likelihoods, with c = λ and L0 = c1.For the exponential example, the mechanism is also (0, δ)-DP classically when x, y ∈ [0, 1].Source: §5 · pp. 18–19
  • A Beta-Binomial pair with α = β > 1 satisfies Assumption 2 and gives (0, δ)-DP without trimming, but δ increases with n.The cited result says direct posterior sampling cannot essentially improve this bound unless the prior is trimmed.Source: §5 · p. 19
  • A multivariate normal model satisfies Assumption 1 under a metric based on differences in xx⊤ and x, yielding (ε, 0)-DP under that metric.For bounded data, the example implies (3ε, 0) classical differential privacy.Source: §5 · p. 20
  • Discrete Bayesian networks achieve (2 ln 1/ε, 0)-DP under a metric incorporating network connectivity and conditional probabilities, implying 2∥v∥∞ln 1/ε-DP classically.For finite-state Markov models, truncated Dirichlet priors bounding multinomial probabilities above ε yield a 4 ln 1/ε-DP mechanism.Source: §5 · p. 20

6. Discussion

The discussion presents posterior inference as both private and robust under concentration conditions on the prior, and frames posterior sampling as a way to trade privacy against utility. It also reviews connections to differential privacy and robustness, practical sampling, and open questions about learning and related mechanisms.

6. Discussion

  • Similar datasets yield posterior distributions with small KL divergence, and the posterior is differentially private under concentration conditions on the prior.The number of posterior samples controls a privacy–utility trade-off for query responses.Source: §6 · p. 21
  • The framework has been applied to analytical expressions for known distribution families and discrete Bayesian networks, and bounds attacker effort to guide posterior access.The authors position the framework as a building block for more sophisticated private Bayesian inference.Source: §6 · p. 21

6.1.1 Differential Privacy

  • Posterior sampling is presented as a Bayesian counterpart to the exponential mechanism, while prior work also uses Bayesian inference to improve private releases or answer queries.The paper contrasts its prior-based conditions with the PAC-Bayesian Gibbs estimator, which obtains its posterior by minimising risk bounds.Source: §6.1.1 · p. 22

6.1.2 Robustness and Privacy

  • The paper relates its results to robustness work: unlike private plug-in estimators, its Bayesian estimators use a suitably defined prior rather than private views of the data.The discussion also connects prior concentration to algorithmic stability and reviews robust-statistics approaches to privacy.Source: §6.1.2 · p. 23

6.1.3 Previous Versions and Follow Up Work

  • The revised work replaces its earlier mechanism with fixed sampling, adds utility bounds, and uses Le Cam’s method for lower bounds on indistinguishability.The authors also report that privacy and robustness can imply one another under specified conditions, alongside shared sufficient conditions for both.Source: §6.1.3 · pp. 23–24

6.2 Future Directions

  • The authors have not examined how setting the prior for privacy affects learning; larger c improves privacy but can inhibit learning through stronger prior concentration.They identify choosing c to balance privacy and learning as a possible direction.Source: §6.2 · p. 24
  • The authors propose studying whether adjusting both the exponential mechanism’s ε and its base measure, corresponding here to the prior, may be advantageous.They note that privacy and efficiency can be gained together in some cases.Source: §6.2 · p. 24

Appendix A. Proofs of Main Results

The appendix proofs support the paper’s posterior-sensitivity and privacy results, then use those bounds to analyze utility and distinguishability. They also establish a sampling-based utility guarantee and bound an adversary’s ability to distinguish posterior distributions.

Posterior bounds

  • For larger dataset distances, the proof extends its bound by chaining intermediate datasets whose pairwise distances are below c − 1.The proof requires a complete metric dataset space for the intermediate points to exist.Source: Appendix A · p. 27
  • Under the stated likelihood-ratio bound, the proof combines likelihood and marginal-likelihood bounds to control posterior probabilities across datasets.The passage gives the posterior comparison in terms of exp{2Lρ(x, y)}.Source: Appendix A · p. 27
  • The proof applies the posterior KL bound and Pinsker’s inequality to obtain a bound on posterior distance.The extracted bound is proportional to ρ(x, y).Source: Appendix A · pp. 27–28

Utility and distinguishability

  • The proof of the utility estimate uses N posterior samples and Hoeffding’s inequality to show the estimate is at most 2ε from optimal.The argument relies on bounded utility.Source: Appendix A · p. 28
  • For posterior sampling, the proof bounds an adversary’s empirical-distribution error and uses data processing and Pinsker’s inequality in its distinguishability argument.The supplied passages give the proof steps but not the final distinguishability bound.Source: Appendix A · p. 28
  • The regret proof compares optimal responses under two beliefs and uses bounded utility plus the optimality of the response under the second belief.The proof also bounds an expected KL divergence between posteriors using an η-bound.Source: Appendix A · pp. 25, 29

Appendix B. Proofs of Examples

The appendix checks the paper’s prior and likelihood conditions in several distributional examples, including exponential, beta-binomial, Gaussian, and graphical-model settings. The excerpts provide specific feasible-parameter and bound results for some of these examples.

Exponential-family examples

  • For the exponential-family example, the proof identifies feasible parameters as ΘL = (c1, L) for L > c1 under the stated distance.It uses a renormalized exponential prior on [c1, c2].Source: Appendix B · p. 30

Binomial and beta-binomial examples

  • For a binomial likelihood under the distance |k1 − k2|, the log-likelihood ratio’s boundary extrema are ln n and −ln n.The proof uses these extrema to evaluate the supremum appearing in its feasibility condition.Source: Appendix B · p. 31
  • For the beta-binomial example, the proof studies the mass of the truncated prior using the incomplete Beta function and establishes monotonicity claims used in its bound.The supplied passages state H(p) ≤ 0 and that related functions are monotonic, but do not provide the resulting bound in full.Source: Appendix B · pp. 32–33

Gaussian example

  • For a Gaussian likelihood, the proof gives a feasible choice c = 2λ max{|μ|, 1} for the trimmed exponential prior.The example uses the absolute log-ratio distance of Gaussian densities.Source: Appendix B · pp. 33–34

Graphical-model example

  • For independent draws, the proof finds c = λ for the trimmed exponential prior; in the graphical-model setting, its distance weights differing variables by one plus their degree.The stated graphical-model distance is ρ(x, y) = v⊤δ(x, y), with vk = 1 + deg(k).Source: Appendix B · pp. 30, 35
Loading 1306.1066v5…