PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo

Yu-Xiang Wang, Stephen E. Fienberg, Alex Smola

arXiv:1502.07645v2stat.MLcs.LG

TL;DR

The paper asks whether Bayesian learning on sensitive data can provide differential privacy without sacrificing statistical utility or computational scalability. It shows that posterior sampling and stochastic-gradient Monte Carlo can supply privacy guarantees, with empirical performance reported as substantially better than earlier privacy mechanisms. The scope is constrained by assumptions such as Bayesian consistency and, for stochastic-gradient methods, trade-offs involving stepsize, mixing, and sample budget.

  • Problem

    Bayesian learning on sensitive datasets needs privacy protection while retaining the utility and scalability of posterior-based inference.

  • Method

    The paper analyzes one-posterior-sample privacy and differential privacy arising from stochastic-gradient Langevin and related Monte Carlo procedures.

  • Results

    The authors report that one posterior sample can be consistent and near optimal under standard statistical conditions, while stochastic-gradient samplers can provide privacy with little or no algorithmic modification.

  • Takeaways & Limitations

    Bayesian posterior sampling can serve as a differentially private mechanism, and stochastic-gradient sampling can support releasing multiple intermediate samples.

  • Takeaways & Limitations

    Consistency is harder to ensure in infinite-dimensional Bayesian models and may depend on the chosen prior; smaller stepsizes also slow mixing and increase sample correlation.

Abstract

from arXiv · show

We consider the problem of Bayesian learning on sensitive datasets and present two simple but somewhat surprising results that connect Bayesian learning to "differential privacy:, a cryptographic approach to protect individual-level privacy while permiting database-level utility. Specifically, we show that that under standard assumptions, getting one single sample from a posterior distribution is differentially private "for free". We will see that estimator is statistically consistent, near optimal and computationally tractable whenever the Bayesian model of interest is consistent, optimal and tractable. Similarly but separately, we show that a recent line of works that use stochastic gradient for Hybrid Monte Carlo (HMC) sampling also preserve differentially privacy with minor or no modifications of the algorithmic procedure at all, these observations lead to an "anytime" algorithm for Bayesian learning under privacy constraint. We demonstrate that it performs much better than the state-of-the-art differential private methods on synthetic and real datasets.

1 Introduction

The paper connects Bayesian posterior sampling with differential privacy, showing that posterior randomness can provide privacy while retaining statistical utility. It also extends privacy guarantees to stochastic-gradient samplers and reports strong empirical performance.

  • Motivation: Bayesian learning combines expert knowledge and statistical evidence through probabilistic models and inherently randomized posterior sampling.Bayesian models support complex dependency structures and uncertainty quantification.
  • Motivation: Differential privacy protects individual information while allowing useful data analysis through appropriate randomization.The paper frames posterior sampling as a potential privacy mechanism rather than adding separate noise.
  • Main results: A single exact or approximate posterior sample is ϵ- or (ϵ, δ)-differentially private under bounded log-likelihood assumptions.The same sample is consistent whenever the Bayesian model is consistent and near optimal under asymptotic normality and maximum-likelihood efficiency.
  • Main results: Stochastic Gradient Langevin Dynamics and extensions satisfy (ϵ, δ)-differential privacy without algorithmic changes when the stepsize is sufficiently small.The procedure can potentially release many correlated samples from an approximate posterior.
  • Empirical findings: The authors report that these Bayesian privacy methods perform as well as or better than state-of-the-art differential-private ERM solvers using objective perturbation.The paper relates its results to earlier privacy mechanisms but defers detailed comparisons to a later section.

2 Notations and Preliminary

The paper formalizes Bayesian posteriors, motivates scalable stochastic-gradient Monte Carlo, and introduces the differential-privacy framework used for later guarantees. These preliminaries emphasize both richer uncertainty outputs and computational challenges at scale.

  • Bayesian notation: The posterior combines a prior belief with likelihood contributions from observed data and can provide credibility intervals in addition to point estimates.The model may be finite-dimensional, graphical, or nonparametric.
  • Computational motivation: When closed-form posteriors are unavailable, MCMC methods generate samples, but standard approaches can be prohibitively expensive for large datasets.Stochastic-gradient Monte Carlo methods scale Bayesian learning by combining gradient estimation with stochastic differential-equation simulations.
  • Differential privacy: Differential privacy compares randomized algorithm outputs on datasets differing in at most one data point.The definition is intended to protect against linkage and identification attacks even with arbitrary side information and unlimited computational power.
  • Differential privacy: Differential privacy is preserved under postprocessing and composes by adding the privacy parameters of multiple algorithms.These properties support privacy analysis when data are accessed more than once or outputs are transformed.

3 Posterior sampling and differential privacy

The paper shows that posterior sampling can provide differential privacy under bounded log-likelihood assumptions, while retaining statistical consistency, near-optimality, and computational tractability under corresponding Bayesian properties.

  • Implicit privacy: A single exact posterior sample is 4B-differentially private when the log-likelihood is bounded by B.With bounded data domain and L-Lipschitz log-likelihood, the guarantee becomes 4LR-differential privacy.
  • Scope and limitations: Consistency is harder to establish in infinite-dimensional parameter spaces and can depend on the choice of prior.The paper leaves formal extensions to fully agnostic and non-iid settings as future work.
  • Consistency and near-optimality: The one-posterior sample estimator is consistent if and only if the Bayesian model is posterior consistent.The result connects private posterior sampling to standard Bayesian consistency theory.
  • Consistency and near-optimality: Under Bernstein-von Mises regularity conditions, the one-posterior sample estimator has asymptotic relative efficiency of 2.The paper also states that, for many parametric models, it is asymptotically near optimal.
  • Consistency and near-optimality: For arbitrary privacy level ϵ, OPS is only a factor of (1+4B/ϵ) away from optimality for bounded log-likelihood models.The scaled likelihood can be viewed as a misspecified model while preserving the MLE target under the stated argument.
  • Implicit privacy: Approximate posterior sampling inherits an (ϵ, δ)-privacy guarantee whose approximation level matches the sampling distribution’s approximation.This extends the privacy result beyond exact posterior samplers.
  • Efficiency and comparison: OPS remains computationally tractable whenever the underlying Bayesian learning model is computationally tractable because the sampling algorithm’s form is unchanged.Compared with objective perturbation, OPS permits arbitrary bounded loss functions and priors, whereas objective perturbation requires restrictive assumptions.

4 Stochastic Gradient MCMC and (ϵ, δ)-Differential privacy

The section shows that stochastic-gradient MCMC methods can provide differential privacy while approximating posterior sampling, with privacy-accuracy trade-offs and practical limitations.

  • Privacy mechanism: Stochastic Gradient MCMC methods can be differentially private for free when their parameters are chosen appropriately.The approach privately releases stochastic-gradient estimates and uses advanced composition and subsampling results to control privacy.
  • SGLD mechanism: SGLD updates parameters using perturbed minibatch stochastic gradients of the negative log-posterior objective.Noise is added at every iteration, preventing convergence to a deterministic maximum a posteriori estimate.
  • SGLD mechanism: As η_t → 0, SGLD converges in distribution to the posterior because minibatch-gradient error vanishes faster than injected Gaussian noise.This supports using SGLD to approximate posterior means and other estimators.
  • Privacy guarantee: Algorithm 2 preserves (ϵ, δ)-differential privacy under data-independent initialization, L-smooth log-likelihoods, and a sufficient iteration condition.The stated condition is T ≥ ϵ^2N^3/(2τ) log(2/δ).
  • Practical trade-offs: Larger minibatches improve gradient accuracy but reduce the number of posterior samples obtainable under the data-pass budget.The recommended choice T = 2N reflects a convergence-versus-sampling trade-off.
  • Comparison and caveats: DP-SGLD releases the entire update sequence and remains private even if its internal state is compromised, but its samples are usually worse than OPS.Its random-walk behavior slows mixing, whereas indefinite SGLD can yield a valid posterior sample without the stronger internal-privacy requirement.
  • Comparison and caveats: Smaller η improves both privacy and posterior-sampling accuracy, but limits the number of samples that can be collected.Privacy noise scales as O(η^2), while posterior-sampling noise scales as O(η).
  • Comparison and caveats: SGNHT adaptivity breaks down when the privacy parameter becomes too small because excessive noise forces tiny stepsizes or destabilizes the stochastic differential equation.The method may then fail to search the parameter space effectively or diverge.

5 Experiments

Experiments evaluate OPS and a hybrid private sampler on two UCI logistic-regression tasks, finding strong performance for the proposed methods but weaker results without OPS initialization.

  • Illustration: At ϵ = 10, the stochastic gradient thermostat produces more accurate and unbiased results, with negligible apparent differential-privacy impact.Figure 1 illustrates convergence toward a basin before posterior sampling in a randomly generated linear-regression model.
  • Experimental setup: The experiments compare OPS and a hybrid algorithm with ObjPert on the Abalone and Adult binary-classification datasets.The evaluation uses privacy-constrained logistic regression under varying privacy levels.
  • Results: Plain DP-SGLD and DP-SGNHT without OPS initialization often perform equally or slightly worse than output perturbation.The authors attribute this behavior to the previously discussed caveats, especially conservative numerical constants.

6 Related work

The paper situates posterior-sampling privacy and private stochastic gradients among prior Bayesian, differential-privacy, and optimization-based approaches, emphasizing broader statistical and computational analysis.

  • Posterior sampling: Earlier posterior-sampling privacy results focused on conjugate priors, bounded probabilistic log-likelihoods, or generalized privacy under Lipschitz and bounded-data assumptions.The paper distinguishes its work by also studying statistical and computational properties.
  • Posterior sampling: Other Bayesian differential-privacy work developed inference tools such as conditional probabilities and credibility intervals, or used posterior inference to denoise privately obfuscated data.The latter is described as a different problem from the paper’s privacy mechanism.
  • Private stochastic gradients: Private stochastic-gradient methods predate this work, including private SGD and private multi-party training.The paper’s Theorem 16 is described as a simple modification of a prior private-SGD theorem.
  • Private stochastic gradients: Bassily et al. showed Gaussian-mechanism private SGD with τ = 1 matches a lower bound up to constant and logarithmic factors.The paper uses this result to motivate the difficulty of substantially improving Algorithm 2.
  • Comparison with prior methods: Prior private-gradient methods can have different data-pass trade-offs: disjoint-minibatch methods suit few passes, whereas the paper’s method targets settings covered by its iteration condition.The cited comparison also notes that disjoint-minibatch methods may have better constants in small-pass regimes.
  • Comparison with objective perturbation: Unlike objective perturbation, the paper’s OPS mechanism tolerates approximate posterior samples, while DP-SGLD releases every intermediate iterate privately.Objective perturbation’s privacy guarantee requires an exact optimal solution.

7 Conclusion and future work

The paper presents Bayesian learning as inherently differentially private through posterior sampling and stochastic-gradient procedures, with preliminary evidence of practical utility and privacy in intermediate steps.

  • One posterior sample is an instance of the exponential mechanism and is near-optimal for parametric learning.
  • Stochastic Gradient Langevin Dynamics and related variants provide differential privacy as a byproduct of posterior sampling.
  • The One-Posterior-Sample mechanism substantially outperforms earlier privacy mechanisms in logistic regression in preliminary experiments.
  • The second method remains theoretically and practically meaningful despite suffering from a large constant, because it protects privacy during intermediate steps.
  • Future work includes exploiting randomness in hashing, sketching, dropout, neural networks, and private movie recommendation.

A.1 Fisher Scoring and Stochastic Gradient Fisher Scoring

Fisher scoring solves maximum-likelihood equations through iterative linearization, while stochastic-gradient Fisher scoring replaces full-data computations with stochastic estimates and acts as a Quasi-Newton method.

  • A.1 Fisher Scoring and Stochastic Gradient Fisher Scoring: Fisher scoring applies Newton’s method to solve the maximum-likelihood estimation problem using the score function.The score function is the gradient of the log-likelihood, and solving S(θ) = 0 yields the maximum-likelihood estimate.
  • A.1 Fisher Scoring and Stochastic Gradient Fisher Scoring: Taylor expansion at the current point linearizes the nonlinear score equation and produces an iterative update.The update searches for θ* by using the local quadratic approximation of the likelihood.
  • A.1 Fisher Scoring and Stochastic Gradient Fisher Scoring: The update θ* = θ0 + I^-1(θ0)S(θ0) is a fixed-point iteration and is often equivalent to Newton iterations.This follows because I^-1 is related to the Hessian of the log-likelihood under mild regularity conditions.
  • A.1 Fisher Scoring and Stochastic Gradient Fisher Scoring: Stochastic Gradient Fisher Scoring replaces the full-data score with a stochastic gradient and estimates Fisher information to avoid passing the entire dataset each iteration.The method can be viewed as a Quasi-Newton method.

A.2 Privacy extension

The privacy extension modifies stochastic-gradient Fisher scoring with non-spherical Gaussian noise under directional smoothness assumptions, while retaining SGFS behavior in a small-stepsize regime and providing formal privacy guarantees.

  • A.2 Privacy extension: When η_t is small, the private algorithm becomes exactly the same as SGFS; when η_t is large, it samples from a higher-variance normal approximation.The modified method is designed to preserve asymptotic properties.
  • A.2 Privacy extension: The privacy analysis assumes the gradient polytope lies within an ellipsoid transformed by a public matrix F, allowing direction-dependent sensitivity.This supports use of a non-spherical Gaussian mechanism.
  • A.2 Privacy extension: DP-SGFS operates on minibatches, adds Gaussian noise, privately estimates the stochastic gradient and covariance, and updates the Fisher-information estimate.The algorithm specifies minibatch size, data passes, stepsize, and initial parameter as inputs.
  • A.2 Privacy extension: Algorithm 4 guarantees (2ϵ, 2δ)-differential privacy when T ≥ ϵ^2N^3/(2τ log(2/δ)) under the stated conditions.
  • A.2 Privacy extension: The proof combines sensitivity bounds, the Gaussian mechanism, subsampling, advanced composition, and simple composition.The covariance release is treated as a private release before composing the gradient and covariance guarantees.
Loading 1502.07645v2…