Data Augmentation MCMC for Bayesian Inference from Privatized Data
Authors: Nianqiao Ju
Jordan Awan
Ruobin Gong
Vinayak Rao
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
data augmentation
MCMC
Gibbs sampler

Abstract: Differentially private mechanisms protect privacy by introducing additional randomness into the data. Restricting access to only the privatized data makes it challenging to perform valid statistical inference on parameters underlying the confidential data. Specifically, the likelihood function of the privatized data requires integrating over the large space of confidential databases and is typically intractable. For Bayesian analysis, this results in a posterior distribution that is doubly intractable, rendering traditional MCMC techniques inapplicable. We propose an MCMC framework to perform Bayesian inference from the privatized data, which is applicable to a wide range of statistical models and privacy mechanisms. Our MCMC algorithm augments the model parameters with the unobserved confidential data, and alternately updates each one. For the potentially challenging step of updating the confidential data, we propose a generic approach that exploits the privacy guarantee of the mechanism to ensure efficiency. We give results on the computational complexity, acceptance rate, and mixing properties of our MCMC. We illustrate the efficacy and applicability of our methods on a naïve-Bayes log-linear model and on a linear regression model.

Data Augmentation MCMC for Bayesian Inference from Privatized Data
Nianqiao Phyllis Ju Department of Statistics Purdue University West Lafayette, IN 47907 nianqiaolpurdue. edu
Jordan A. Awan Department of Statistics Purdue University West Lafayette, IN 47907 j jawanfpurdue.. edu
Ruobin Gong
Vinayak A. Rao Department of Statistics Purdue University
Department of Statisties Rutgers University Piscataway, NJ 08854
West Lafayette, IN 47907 varao@purdue. edu
ruobin, ruobin.gong wrr.iiigonngruuggrss.c edu
Abstract
Differentially private mechanisms protect privacy by introducing additional ran- domness into the data. Restricting access to only the privatized data makes it challenging perform valid statistical inference parameters underlying the confidential data. Specifically, the likelihood function of the privatized data re- quires integrating over the large space of confidential databases and is typically intractable. For Bayesian analysis, this results posterior distribution that is doubly intractable, rendering traditional MCMC techniques inapplicable. We pro- pose an MCMC framework to perform Bayesian inference from the privatized data, which is applicable to wide range of statistical models and privacy mecha- nisms. Our MCMC algorithm augments the model parameters with the unobserved confidential data, and alternately updates each one. For the potentially challeng- ing step of updating the confidential data, we propose generic approach that exploits the privacy guarantee of the mechanism to ensure efficiency. We give results on the computational complexity, acceptance rate, and mixing properties of our MCMC. We illustrate the efficacy and applicability of our methods on a naïve-Bayer log-linear model and on a linear regression model.
Introduction
Motivation. Differential privacy [Dwork et al., 2006] presents formal mathematical framework protect the confidentiality of individuals and businesses in aggregate data products. It is the state-of-the-an standard for statistical disclosure limitation (SDL), and has become widely adopted by curators of large-scale scientific, commercial, and official databases. Differentially private data products are produced by probabilistic mechanisms that carry proven privacy guarantees. Generally speaking, these mechanisms work by introducing carefully designed random noise into the query of interest, which is an otherwise deterministic function of the underlying database.
The privatization of data products through noise infusion poses challenge statistical analysis in the downstream. Statistical estimators are typically complex functions of the data. If instead of the confidential data, the analyst only has access probabilistically processed version of them, how can they maintain the statistical validity of the resulting inference?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A crucial statistical advantage of differentially private mechanisms over traditional SDL counterparts, such as swapping [Dalenius, 1977], that their probabilistic design is publicly known. This knowledge allows the data analyst to, at least in theory, accurately account for the privatization mechanism and conduct reliable uncertainty quantification. Nevertheless, it remains a substantial computational challenge to incorporate the privacy procedure into the statistical analysis. The challenge is a wide-spread and varied one, as the extra layer of privacy protection calls for the revision of wide range of existing statistical methodologies that previously operate on the original, non-privatized data, most of which are neither low-dimensional nor simply structured. This is the challenge we address in this work, in which we develop a general computational framework for practitioners to obtain valid statistical inference based on privatized data.
Related literature. Current inferential strategies for privatized data fall into two broad categories. One invokes traditional statistical asymptotics to approximate the sampling distribution of a differ- entially private statistic, on the grounds that the privacy noise is often asymptotically negligible compared to errors due to sampling [e.g. Smith, 2011, Cai et al., 2021]. These approximations are often inaccurate for finite sample sizes [Wang al., 2018] and call for specific handling to incorporate the privacy mechanism [e.g. Gaboardi et al., 2016, Wang et al., 2015, Gaboardi and Rogers, 2018].
The second category recognizes (as Section 2 will explain) that the marginal likelihood of the model parameters in (3) is central to the problem of inference from privatized data. The marginal likelihood/marrinall posterior distribution requires a potentially high-dimensional integral over the space of unobserved confidential databases, and one that is analytically tractable only in few, simple settings (e.g., Awan and Slavković, 2018, 2020]. Typically, one must resort to either approximating it or sampling from it using Monte Carlo methods. Markov chain Monte Carlo (MCMC) techniques have been proposed for specific privacy mechanisms and data generating models. Karwa et al. [2017] propose an MCMC procedure for inference on exponential random graph models, Bernstein and Sheldon [2018, 2019] devise MCMC methods designed to handle the low-dimensional latent sufficient statistics from exponential family models and linear regression, and Schein et al. [2019] design an MCMC algorithm for the Poisson factorization model when data are locally privatized under the double geometric mechanism. Gong [2022] shows that for certain differentially private statistics, approximate Bayesian computation (ABC) can give samples that are exact with respect to the marginal likelihood and the Bayesian posterior. In addition, when the statistical model for the confidential data is fully parametric, the parametric bootstrap may be used to produce inference accompanied by uncertainty quantification with better accuracy than asymptotic approximation [e.g. Gaboardi et al., 2016, Ferrando al., 2022]. Variational Bayesian analysis [Karwa al., 2016] is another alternative which invokes a non-asymptotic approximation to the posterior distribution. These solutions are either approximations or hold only for specific settings.
Our contribution. We develop a general-purpose MCMC framework to perform Bayesian inference on the model parameters underlying the privatized data. Our framework allows to overcome the intractable marginal likelihood resulting from privatization, and is applicable to a wide range of statistical models and privacy mechanisms. The resulting MCMC algorithms are exact, in that they target the posterior distribution precisely, without involving any approximation.
Our approach allows data analysts to leverage existing inferential tools designed for non-private data. It can be viewed as a flexible, user-friendly wrapper that migrates existing MCMC algorithms for non-private data to the setting of privatized data access, requiring no further algorithm design or tuning. The sampler, formally a Metropolis Siiiis--tttii---iiiie Gibbs sampler, is presented in Algorithm 1. It is general-purpoot purrose, requiring only that the analyst can 1) sample from the statistical model for the confidential data and 2) can evaluate the probability density of the noise induced by the privacy mechanism. The algorithm augments the model parameters with the unobserved confidential data, and alternately updates each one conditioned on the other. While the imputation of an entire unobserved database might appear daunting, we demonstrate how knowledge of the privacy mechanism can be exploited to confer performance guarantees to the proposed MCMC algorithm. We provide theoretical results for the computational complexity, Metropolis-Hastingss acceptance rate, and mixing properties. In particular, the higher the privacy, the more rapid is our algorithm's 's exploration of the parameter space. We also identify a common structure present in many popular privacy mechanisms, which we term record additivity. The record additivity of a privacy mechanism ensures that each round of our sampler has the same order of run-time as that of many non-private samplers. We illustrate the efficacy and applicability of our methods on a privatized naïve- log-linear model and linear regression model with clamped and privatized input.
2

---

2
Problem Setup
Let (I,) X denote the confidential database, containing records. We assume these records are independent and identically distributed (i.i.d.) draws from a statistical model f(10), 0), though this can be relaxed. The goal of the analyst is to conduct statistical inference on the unknown model parameter 0 E O A Bayesian analyst represents priori belief's about 0 with a prior probability distribution p (0), and seeks to compute posterior distribution p(0 xx) x p(0) 0) that updates their beliefs in light of the observations z. In many modern applications, this posterior distribution is intractable, and it common for analysts to represent it using samples drawn via some MCMC algorithm. In this work, we will assume access to such a posterior sampling method:
Assumption 1. The analyst has available a Markov kernel that targets p(0 | x) x f( 0), the posterior distribution over the model parameters given the confidential database x.
Differential privacy. Our work here focuses on the following departure from the usual Bayesian setting: instead of observing the database æ, we observe a privatized data product or query, denoted as sdp- The quantity Sdp is typically of much lower dimensionality that the database 2, and is probabilisticall generated based on data x through a privacy mechanism, written as 17 [x)). The privacy mechanism 7) is said be e-differentially private (e-DP) [Dwork al., 2006] if for all values of sap. and for all 'neighboring' databases (x,,a") x') E X x X differing by one record (denoted by d(z,2' S 1), the probability ratio is bounded:
r7 (sap x))
17 (sap) x²) S <x) <>
The parameter e is called the privacy loss budget, and controls how informative sap is about T. Large values of guarantee less privacy, while e = 0 corresponds to perfect privacy. A simple and widely used e-differentially private mechanism is the Laplace mechanism: for a de- terministic query X" + RT the privatized query is defined as Sdp
(z) + u, where u = (uj...., Um) are i.i.d. Laplace variables. The scale parameter of the Laplace distribution is inversely proportional to 6 (more privacy requires more noise), and directly proportional to A (s) = max (2xx"")))x" xx==d(x,2"<( ||s [x) (x')ll the l (global) sensitivity of 8 (the more sensitive the confidential query is to changes in one record of the database, the more noise need).
Our methodology requires that the privacy mechanism 17 is known and can be evaluated. This is true of e- (or pure) DP, well as common variants such as (e, 8)- (or approximate) DP, zeno-concentrated DP (zCDP) [Dwork and Rothblum, 2016, Bun and Steinke, 2016], and Gaussian- DD [Dong et al., 2021]. To ensure computational efficiency, we make the following additional assumption. Assumption 2 (Record Additivity). The privacy mechanism can be written in the form ns(ap x)) = g (Sap: Σ (3,,, Sdp)) for some known and traciable functions g, l,,....,hy Lnn
We refer to privacy mechanisms that satisfy Assumption 2 as record-additive. An implication of record additivity is that after changing one record in z, we do not have to scan the entire database to reevaluate 7) This is satisfied by many commonly used mechanisms, two important examples being: 1) mechanisms that add data-inde independent noise to a query of the form sample mean, sample
Σi=1 (x.)). such as the covarniccce and sufficient statistics of an exponential family distri- bution (see Sections 4 and 5 for examples), and 2) mechanisms designed to optimize empirical risk functions of the form u(xr, 8dp) = E ue uz( Sáp), such as the exponential mechanism [McSherry and Talwar, 2007], K-norm gradient mechanism [Reimherr and Awan, 2019], objective perturbation [Chaudhuri et al., 2011, 1, Kifer et al., 2012], and functional mechanism [Zhang et al., 2012].
Doubly intractable Bayesian inference from privatized data. Without access to the confidential database x, and given only the privatized query Sap. the Bayesian analyst is now concerned with the following posterior distribution:
(0 sap) x p (0) p (sdp 10)
Here, 10) is the marginal likelihood of 0, integrating over all possible confidential databases:
p (sdp () = / g
17 (sap 1)) f (x () dz.
(3)
The marginal likelihood contributes all the information that is available the privatized observation Sap about the parameter 0, and is the foundation to statistical inference using privatized statistics
3

---

[Williams and McSherry, 2010]. The posterior distribution (2) reveals that the inferential uncertainty about the parameter consists of three contributing sources: 1) prior uncertainty as encoded in p(O). 2) sampling (or modeling) uncertainty of the confidential database as reflected in and 3) uncertainty due to privacy as induced by the probabilistic mechanism 17.
We now come to the core challenge to address in this work: the marginal likelihood in (3) calls for an integral over the entire space of possible input databases I E X This is usually computationally challenging, especially if the privacy mechanism is not a function of a low-dimensional sufficient statistic. If the integral underlying the marginal likelihood is intractable. then p(sap analytically evaluated. This makes the corresponding posterior distribution p(0 sap) of (2) doubly intractable [Murray et al., 2012] in the sense that it cannot be analytically evaluated even up to a normalizing constant. Thus, traditional MCMC techniques are inapplicable and inference strategies devised for privatized statistics must tame this possibly high-dimensional integration problem.
()) cannot be
3 Data Augmentation MCMC for Inference from Privatized Data
In this paper, we present a simple, efficient, and general data augmentation MCMC [Tanner and Wong, 1987, Van Dyk and Meng, 2001] framework, allowing practitioners to perform valid Bayesian inference on a wide-range of data models and privacy mechanisms. Our approach is to augment the MCMC state space with the latent confidential database so that the stationary distribution is the joins posterior distribution
(4) Marginally, the samples produced by such an algorithm follow the posterior p(0 sap) in (2). Our sampler is exact, targeting the marginal posterior distribution p(0]sap) without any approximation error, despite the fact that the marginal likelihood (3) is intractable.
p(0, x sap) x p(0) | ())(sap xx)
Our approach of imputing the latent confidential database x is motivated by two factors: 1) we wish our algorithm to be general-purpose, applicable to a wide range of models and privacy mechanisms, and 2) we wish our algorithm to inherit guarantees on mixing performance from guarantees of the privacy mechanism. Towards these ends, we do not assume any specific form of the underlying model of x: and the privacy mechanism beyond Assumptions I and 2 respectively. In this light, our contribution can be viewed as a flexible wrapper that allows existing MCMC algorithms for models of the confidential data to be extended to settings where the data is now protected by some privacy mechanism. Though imputing the confidential dataset might appear to present a sigmificant challenge, show that properties of the mechanism can be exploited to give performance guarantees sampling scheme, and show that it has a runtime of the same order as the non-private sampler.
In what follows, we outline our proposed MCMC algorithm, derive guarantees on the runtime and acceptance rate of the algorithm, and provide mild conditions for the proposed samplers to be ergodic, as well as additional conditions for our sampler to achieve geometric rates of convergence.
3.1 A Privacy-Aware Metropolis Sampler
Our approach to sample from the joint posterior distribution p(0.2z sap) is through a sequence of alternating Gibbs updates. Let (zx(1), ,(()) denote the state of the Gibbs sampler at the 1-th iterations. Each iteration of the Gibbs sampler entails two steps:
(Step 1) sample g(t++) from p(. ,o(*), sap). and (Step 2) sample (++1)) from p(- g(t++), sap))
The conditional distribution in Step I simplifies as (()) sdp) p(8]=(()), highlighting why data- augmentation is useful: this conditional distribution is independent of the privacy mechanism, and we can use existing sampling algorithms (Assumption 1) for the confidential data. We note that with the exception of a few models, such as simple models with conjugate priors, it is usually not possible to directly sample from p(0) 2r). Assumption however only requires that can conditionally simulate value of 9 from Markov kernel that has p(0) (+)) as its stationary distribution. Our overall Gibbs sampler then becomes a Metropolis-winee Senelii-iitii-Giiie sampler [Gilks et al., 1995], that nevertheless targets the joint posterior p(0, 2r|s s-(sap).
Step is the data-augmentattion step, and connects the statistical model and the privacy mechanism on x. Again, we cannot expect to produce conditionally independent sample of the latent database from

---

p(æ 0, Sup), as this is model and mechanism dependent. Instead, we take the much more tractable approach of cycling through the elements of latent database z, sequentially updating z one element of a time. Writing - (I1, , -ii-1: 1, -i........ :in) ) to denote the vector excluding the ith element, step then consists of the sequence of updates p(a1 0, f-,-1, sáp), p(2² 0,, 22 Sdp)..... p(
0, -n sap). The complete sweep can be viewed as dependent update of the latent database ar that targets the conditional distribution p(a 0, sap).
Before we specify our complete sampler in Algorithm 1, we first address the following questions: (Q1) What is the performance loss from updating z one element at a time, rather than jointly? and (Q2) How can we efficiently carry out the conditional updates p(z; 0, 2i: sap), 1....,, n??
Q1 concerns whether the dependence of 2; given (=_1;$5p) is strong exploration of the -spae and cause poor mixing. Here we note that the privacy mechanism limits the change in the likelihood SSpp x) when one element of is changed, and therefore limits the coupling between 2; and x-i-- This suggests a Gibbs sweep through the latent database x will not suffer from poor mixing.
impede efficient
Algorithm 1 One iteration of the privacy-aware Metropolis within-Giiiii sampler
1. Conditional update of p(0 x) using the kernel from Assumption 1.
2. For each = 1,2,.... sequentially update z; x x 0, sdp-
(a) Propose 2 ~ f(- f.)
(b) Update t(x", sap) = t(x, sap) - (x sap) + 1,(27 sap) according to Assumption 2.
(c) Accept the proposed state with probability axx | xis x- given by:
[s(spp]
n7(sap xz) 1 min g(sap. t(x", sap)) g( t(x, sap))
a(x; Ty, 25, 0) = min
1
(5)
Q2 recognizes that the conditionals p(æ; Sdp, x x-4) are model- and mechanism-specifee and simu- lating from these is challenging in most settings. For this, we take the following simple approach in Algorithm I: at each step, we propose x; from the model [x](0), and accept it with the appropriate Metropolis-Hasting acceptance probability (5). Observe that our choice of proposal distribution is independent of the privacy mechanism, and ignores the privatized data 8dp as well as all other elements _ Despite being simple and we can lower-bound the acceptance probability of proposals produced this way by exp(-e). This lower bound is key efficiency: despite the unconstrained nature of the proposal distribution, we can guarantee a minimum acceptance probability. These two facts suggest our sampler will explore the space of databases relatively quickly.
we show in Proposition 3.1 that for DDDP,
Proposition 3.1. For a pure DP privacy mechanism n, the acceptance probability from Equation (5) satisfies (ax) x,,, 0) 2 exp(-c),for all 0, x, Ri, ar..
The privacy loss budget é is usually understood to be a small constant, which privacy experts recommend be between .01 and [Dwork, 2011]. When acceptance rate in Algorithm is no less than 36.7%, and as approaches zero, the bound on the acceptance rate approaches one. Intuitively, this is because as e decreases, the distribution of the privatized data Sip depends less and less on any individual element of the database.
1, Proposition 3.1 ensures that the
The simplicity of our approach arises through a decoupling of the data model from the privacy mechanism: the former is used to update and propose I; 's, while the latter is used to calculate the acceptance probabilities. The next result formalizes the computational efficiency of our approach. Specifically, for any record-ad -ddiiive mechanism, one iteration of our algorithm requires ((n) oper- ations, where is the size of the latent database. Essentially, this arises because of Assumption 2, which allows the acceptance probability in (5) to be calculated in O(1) time.
Proposition 3.2. The Gibbs sampler described in Algorithm I requires O(n) number of operations to update the full latent database according to p( 0, sdp)-
Note that even without privacy, one round of an MCMC procedure typically takes O(n) time. This is because updating 0 given the confidential data requires computing the data likelihood f(x 0) = I f(x; ()), an (n) operation in general. Thus, result of the mild and typical condition that
5

---

is record-additive, our MCMC procedure enjoys the same order of runtime as the original MCMC algorithm for confidential data.
The previous two results are key to understanding the efficiency of our approach. In the next section formally establish geometric ergodicity of the sampler in Theorem 3.3 and 3.4.
Computational complexity. The i.idd assumption on the records ensures that step 2a of Algorithm 1 take (11) time, though this assumption can easily be weakened. Assumption 2 allows steps 2b and 2c to also takes ((1) time. Overall, step 2 of our algorithm then takes ((n) (rather than O(n²)) )) time as
stated in Proposition 3.2. This matches the typical per-iteration cost of samplers for the non- non-private posterior distribution required in step 1. Thus, the overall cost of an iteration of our MCMC sampler is On), which is typical when dealing with datasets of size
3.2 Ergodicity of the Privacy-Aware Sampler
Ergodicity ensures the MCMC chain converges to the posterior distribution in total variation distance. (Tiemney 1994], which is essential for an MCMC sampler consistently estimate functionals of the posterior distribution. In Theorem 3.3, we provide mild and sufficient conditions for our proposed weapliisswitti--iiee
sampler to be ergodie.
Theorem 3.3. Under conditions A1 A3 below, the Melnopolis-wihhin-Giii sampler of Algorithm I on the joint space (X" x O) is ergodic and it admits p(x, 0 88p) as the unique limiting distribution.
AI. The prior distribution is proper and p(0) > f.ror all 0 in θ = {0 fo(x) >> 0 for some r}.
A2. The model is such that the set {x : f(x 0) > 0} does not depend on 0.
A3, The privacy mechanism satisfies n[sap æ)) for all x".
We prove this in the supplementary material by verifying invariance, aperiodicity, and irreducibility. Conditions A A1-A3 concern model specification, prior specification, and privacy noise. These mild assumptions are typically true and are easy to verify. While there are some mechanisms, such as the Aleeaee-one-at-randeee mechanism, which satisfy approximate-DP but which violate A3 [Barber and Duchi, 2014], most privacy mechanisms of interest satisfy A3, It is easy to verify that if satisfies e-DP, concenrrneet DP, or Gaussian-DP? then property A3 is guaranteed.
Next, we establish conditions for Algorithm 1 to be geometrically ergodic [Rosenthal, 1995, Roberts and Rosenthal, 1998]. A chain is said be geometrically ergodic if its total variation distance the target has a geometrically decaying upper bound. Geometric ergodicity is a desirable property since it provides rate convergence to the stationary distribution, guaranteeing central limit theorems, and allowing for the computation of asymptotically valid standard errors.
For simplicity, we focus on the situation where one can directly sample from the conditional posterior p(0 æ). This is an important and common case, relevant when either is oowdiimeniiona or where one can place conjugate priors on 8. Both applications Section 4, and a linear regression model in Section 5, fall under this setting.
present in this work, log- lig-linear model in
Theorem 3.4. Assume that in step of Algorithm 1, one can directly sample from p(0 | x). Under A AI-A3 of Theorem 3.3, the resulting (x. 0) chain, as well as the marginal chains, are geometrically ergodic if satisfies G-DP and there exists < a < b <, oo such that a S f(x () S b v0,
To prove Theorem 3.4, we verify the drift and minorization conditions for component-wise Gibbs samplers in Theorem 8 of [Johnson et al., 2013]. See the supplementary material for details.
Unsurprisingly, geometric ergodicity requires stronger assumptions than just ergodicity. The first assumption concerning the ability to sample directly from p(0|2)) can be avoided, but for the sake of clarity we do not try to relax it, since we are mostly concerned with the interface with the privacy mechanism. The second assumption on the boundedness of the likelihood is stronger, but also typical. A common way to achieve bounded likelihoods is to require the sample space X (and typically also θ) to be bounded. In many real-world settings, such bounds exist, even if they may be very loose.
4 Naïve Bayes Log-Liness Model
Log-linear models are often used to model categorical data, a popular instance being the naive Bayes classifier. Following Karwa et al. [2016]. we consider the following model: x (I ZK)

---

is the imput feature-vector, with each Fa taking values in 21......,JJ. and y is the output class taking values in database, the entire datahase consisting of N i.i.d. copies of (ar, y). The naive Bayes classifier assumes that P(x y) K P(xx y). the model parameters being ptj P(æx- = jly - i)
Each imput-output pair (x, y) forms one record in our confidential
and p. = P(y = i). The sufficient statistics of this model are n #(y = i = j). which count the number of glass-feature co-occurrences. This will form our confidential query s, which we privatize by adding Laplace noise to each of the nig. The resulting quantity Sdp, consisting of the
Lid noisy counts m = n + Lijke is what we release. When Lisk ~ Laplace(0, 2K/c), the output sáp satisfies c-DP. Placing Dirichlet(2.....22 on all parameter vectors, our goal is to obtain the marginal posterior distribution of p, p ddp. While Karwa et al. [2016] approximate this private posterior distribution using variational Bayes methods, our MCMC procedure able to target the exact private posterior distribution.
Simulation setup. We perform several simulation experiments where we apply our MCMC samplers to the log-linear model described above. For the simulation, we set N = 100 (number of records), = 5 (number of classes), K 5 (number of features), and Js 3 for all k 1,...; K (possible values for each feature). We evaluate our sampler for privacy levels corresponding to E {.1, 3, 1, 103.
Posterior mean. We generate one non non-private dataset from the model, and hold it fixed. We then create 100 private queries sdp at each value, and for each Sap iterations. We discard the first 5000 iterations as burn-in. Finally, for each chain, we calculate the posterior mean. Figure la plots the 100 different posterior means for each e-value for the parameters = P(Y = i) for 1, 1.....5. 5. In this plot, the solid horizontal lines indicate the non-private posterior means, and the dashed horizonal lines indicate the prior means for each parameter. We see that as approaches zero, the posterior mean approaches the prior mean, reflecting the intuition that we learn less from the data the privacy budget gets smaller. On the other hand, as increases, we see that the private posterior mean approaches the non non-private posterior mean, which reflects the fact that as e grows, we learn approximately the same from the data as if there were no privacy mechanism.
Algorithm for 10000
p1
p2
p3
p4
p5
1.00
0.6
0.75
postertor moan
0.4
0.50
0.25
0.2
0.00
bound
mean
(a) Posterior means for the log- linear model. The solid horizonal lines indicate the non privvate posterior means, and the dashed lines at indicate the prior means.
(b) Observed acceptance rates for the log-linea model. The blue (above) point clouds indicate the average acceptance rate, and the orange (below) points indicate the observed minimum acceptance each chain. The solid black line is the lower bound of Proposition 1.
Acceptance rate. Using the same simulation setup as for the posterior mean, we calculate the average and minimum acceptance rate of Step in Algorithm 1. Since the privacy mechanism satisfies e-DP, we know that exp(-e) is lower bound on these acceptance rates. In Figure 1b. we confirm this bound, and see that the average acceptance rate is significantly higher than this lower bound. This suggests that the chain mixes even faster than indicated by Proposition 3.
Coverage of credible intervals. For the next experiment, sample set of parameters from the prior, and hold this fixed. Then for each value, we produce 100 non-private datasets (m²)), ), one private dataset (m for each non-private one, and then run chain for 10,000 iterations discarding
7

---

the first 5000 iterations for burn-in. From each chain, we produce 90% credible interval for each pj P(Y = i). and calculate the empirical coverage which reported in Table
P1
.097
P2
.18
.145
P4
.446
Ps
.163
1
.36
1
.3
.97
.59
1
.94
.99
.97
.83
.98
.95
-91
-97
.89
.93
10
.92
.88
-94
.92
.9
Table Coverage p: = P(Y =)) for the log-linear model at different e. Top row the true data generating parameter values. Coverage is based on 100 replicates.
At a sample size of only N 100, we do not expect the coverage of the credible intervals to match the nominal level of 90%, but we see in Table I that most of the coverage values are above .9. Notable exceptions are the coverage of p4 when is small. This may be because when e small, the private posterior is approximately equal to the prior, which is centered at .2; however P4 is significantly further from than the other parameters, which may explain why the coverage is low in this case.
Linear Regression
Next, we consider ordinary linear regression with n subjects and predictors. We write To for the matrix of predictors excluding the intercept columns, x = (1, no) for the matrix including the intercept. and y for the vector of outcomes. We model the explanatory variables zo as záj itd. (m, Σ) for i = i..... n = 100, with y|æ given by N,, (x,3 o²I,). Here In is the n X identity matrix An, denotes the n-dimennional multivariate Normal distribution. The parameters of interest are 8. the (p + 1---iiidddee dimmenssoon vector of regression coefficients, with m and Σ assumed known. We use independent (0, 2²) priors for the components of B3.
To achieve e-DP via the Laplace mechanism, we require a finite global sensitivity. To achieve this, standard practice in the DP literature to bound each predictor and response variable data-independent fashion. The bounds chosen by the privacy expert are [a:, b,] for each instance of zá and (ay, by] for the entries of y, and these values are shared with the analyst.
Definition 5.1. For a real value z, and S define the clamp function [æ]4 == min (max min(max If is a vector of length d, use the same notation to apply entry-wise clamp: [=]] = [[æ1]a [22]a.... [zala)]
2, a}. 6}.
Before adding noise for privacy, we first clamp the predictors and response, and then normalize them to take values in [-1, 1]: Th = (b; a.) (2( - -a)) 1 and ÿ = (by - ayy)
oyy (yy) - Call ã = L 3. 27 ......,..y ..] and = (x J. J. 2). The is the summary statistic to which will add noise for privacy. The ε sensitivity of s (ignoring duplicate entries of x Σ, and the constant entry (7 2) 1,1) is A = p2 + 3p + To satisfy e-DP, we add independent Laplace(O, A/e) noise 2 (p + 1)(p + 2) + (p+1) unique entries of xr which gives our final private summary Sdp- We notice that is an additive function and each individual' 's contribution to is t(2,, v.) = ((*+) J.. J.P (2+) i.). This mechanism producing sáp is record-additive
to each of the
Simulation setup. Our experiments focus posterior inference about 3 based on Sap. For simplicity, we fix other parameters o², m, E at the true data generating parameters (reported in the supplementary materials). When they are unknown, the posterior distributions of these parameters can be estimated by Gibbs sampler as well. Confidential predictors and responses are clamped with bounds 6 = 10 and a = 100. Given a confidential database (x,, y). the posterior distribution of 3 is multivariate Normal and can be sampled directly with a runtime linear in
Posterior mean. We generate one confidential dataset (æ, y) and hold it fixed. At each value, we create 100 private outputs Sdp and run Gibbs samplers for 10,000 iterations targeting the posterior Saps discarding the first 5000 iterations. We plot the 100 different posterior means of 3 in Figure 2. In this plot, the solid horizontal lines indicate posterior means given confidential data (z, y), which

---

we do not expect to fully recover due to clamping. The posterior quantities display the same trend with respect to change in privacy level as observed in Figure 1b. The other experiments from Section 4 were also run on this linear regression model, and produced similar results. Simulation details, plots and discussion are in the supplementary materials.
80
82
0.1
0.1
0.3
0.1
033
Figure 2: Posterior mean for private linear regression || Sdp with fixed confidential data. The solid horizonal lines indicate the confidential data posterior means, and the dashed lines indicate 0.
6
Discussion
We proposed novel, but simple sampling procedure for parameter inference models where one only has access to privatized data. Our approach is an MCMC sampler that targets the posterior distribution p(0 Sap), and which leverages existing samplers for the non-private posterior p(0 zz), as well as the structure of the privacy mechanism. The result is a simple wrapper for practitioners to obtain valid statistical inference from privatized data using the same models for the unobserved confidential data. As side product, our algorithm also produces multiple copies of the confidential database from the posterior p(ar Sáp). These posterior predictive draws could be useful when is interested in inferring properties of x as well. Although we did not discuss this, our data augmentation scheme can also potentially enable frequentist analysis through the Monte Carlo expectation-maxiizaatio algorithm.
We acknowledge some limitations of present work. First, we point out that strong assumptions such as bounded parameter space and sample space X are required to establish geometric ergodicity of the Gibbs sampler in Theorem 3.4. They mostly reflect the current state of MCMC mixing results, and can likely be relaxed, at the cost of a more complex theorem statement and proof. Second, our current proposal for updating vi xr 0, Sdp only tailors the model f(- 0) and it is not customized for &áp yet. In the future, we might be able to design algorithms that also incorporate the privatized output Sdp in these proposals. Third, we point out while our method exploits privacy to control the correlation between the components of æ, it is still susceptible to correlation between x and O. This can potentially cause poor mixing in practice, despite geometric convergence rate. While in simple problems, this can be fixed by reparameterization, we plan to develop MCMC algorithms for this setting in follow-up studies. A similar potential issue is that, as wrapper, our algorithm may be inefficient when the chosen sampler for p(0 z) does not mix well, especially in some dinensinnnii settings. We emphasize though that our method is intended for settings where there currently exists efficient samplers for p(0) x)., and when this is not the case, alternative approaches may be needed.
Finally, while the proposed algorithm converges so long as the privacy mechanism v is known, irrespective of the specific privacy guarantee, we point out that for alternative versions of DP (such as zCDP), the acceptance probability results in Proposition 3.1 may no longer hold, as this result depends on the e-D guarantee. Developing alternatives to Proposition 3. for different privacy definitions is another goal of future work.
Acknowledgments and Disclosure of Funding
R. Gong is supported in part by the National Science Foundation grant 1MS-1916002, V. Rao by the National Science Foundation grants RI-181 11699 and DMSS-812199 and J. Awan by the National Science Foundation grant SE5-2150615.

---

References
Jordan Alexander Awan and Aleksandra Slavković. Differentially private uniformly most powerful tests for binomial data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 4208 0288-42111 4218, 2018.
Jordan Alexander Awan and Aleksandra Slavković, Differentially private inference for binomial data. Journal of Privacy and Confidentialiry, 10(1), 2020.
Rina Foygel Barber and John C Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv: 1412.4451, 2014.
Garrett Bernstein and Daniel R Sheldon. Differentially private bayesian inference for exponential families. Advances in Neural Information Processing Systems, 31:2919-2922,, 2018
Garrett Bernstein and Daniel R Sheldon. Differentially private bayesian linear regression. Advances in Neural Information Processing Systemx, 32:525-535, 2019. 2019..
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, pages 635-658. Springer, 2016.
T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 4965):2825-280,, 2021.
Kamalika Chaudhuri, Claire Monteleoni, and D. Sarwate. Differentially private empirical risk minimization. In Journal of Machine Learning Research, volume 12, pages 1069-1109, 2011.
Tore Dalenius. Towards a methodology for statistical disclosure control. Statistik Tidskrift, 15: 429-444, 1977.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society, Series B, 2021.
Cynthia Dwork. A firm foundation for private data analysis. Communications of the ACM, 54(1): 86-95, 2011.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv:1603.01887 2016.
arXiv preprint
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in Springer, 2006.
private data analysis. In Theory of cryptography conference, pages
Cecilia Ferrando, Shufan Wang, and Daniel Sheldon. Parametric bootstrap for differentially private confidence intervals. In International Conference Artificial Intelligence and Statistics, pages 1598-1618 PMLR, 2022.
Marco Gaboardi and Ryan Rogers. Local private hypothesis testing: Chi-square tests. In International Conference on Machine Learning, pages 1635. PMLR, 2018.
Marco Gaboardi, Hyun Lim, Ryan Rogers, and Salil Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In International conference machine learning, pages 2111-2120. PMLR, 2016.
Wally R Gilks, Nicky G Best, and Keith KC Tan. Adaptive rejection Metropolis sampling within Gibbs sampling. Journal of the Royal Statistical Society: Series C (Applied Statistics). 44(4): 455 472, 1995.
Ruobin Gong. Exact inference with approximate computation for differentially private data via perturbations. Journal of Privacy and Confidentiality (to appear), 2022.
Alicia A Johnson, Galin L. Jones, and Ronald C Neath. Component-wise Markov chain Monte Carlo: Uniform and geometric ergodicity under mixing and composition. Statistical Science, 28 (3):360-375, 2013.
10

---

Vishesh Karwa, Dan Kifer, and Aleksandra Slavković. Private posterior distributions from variational approximations, NIPS 2015 Workshop on Learning and Privacy with Incomplete Data and Weak Supervision, 2016.
Vishesh Karwa, Pavel N Krivitsky, and Aleksandra B Slavković. Sharing social network data: differentially private estimation of exponential family uundom-raphe models. Journal of the Royal Statistical Society: Series C (Applied Statistics), 66(3):481-500 2017.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, Edinburgh, Scotland, 25-27 Jun 2012. PMLR.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 07)), pages 94-103. IEEE, 2007.
lain Murray, Zoubin Ghahramani, and David MacKay. MCMC for doubly-intractable distributions. arXiv preprint 1206::2200666666 2012.
Matthew Reimherr and Jordan Awan. KNG: the k-norm gradient mechanism. Advances in Neural Information Processing Systems, 32, 2019.
Gareth O Roberts and Jeffrey S Rosenthal, Two convergence properties of hybrid samplers. The Annals Applied Probability, 8(2):397-407, 1998.
Jeffrey S Rosenthal. Minorization conditions and convergence rates for Markov chain Monte Carlo. Journal of the American Statistical Association, 90(430):558 1995.
Aaron Schein, Zhiwei Steven Wu, Alexandra Schofield, Mingyuan Zhou, and Hanna Wallach. Locally private Bayesian inference for count models. In Proceedings of the 36th International Conference Machine Learning, Proceedings of Machine Learning Research, pages 5638-5648. PMLR, 09-15 Jun 2019.
Adam Smith. of the forty-third annual ACM symposium Theory computing, pages 813 822, 2011.
statistical estimation with optimal convergence rates. In Proceedings
Martin A Tanner and Wing Hung Wong. The calculation of posterior distributions by data augmenta- tion. Journal of the American statistical Association, 82(398):528-544 1987.
Luke Tiemney Markov chains for exploring posterior distributions. the Annals of Statistics, pages 1701-1728, 1994.
David A Van Dyk and Xiao-Li Meng. The art of data augmentation. Journal of Computational and Graphical Statistics, 10(1):1-50, 2001.
Yue Wang, Jaewoo Lee, and Daniel Kifer. Revisiting differentially private hypothesis tests for categorical data. arXiv preprint 1.X:3:151..03376, 2015.
Yue Wang, Daniel Kifer, Jaewoo Lee, and Vishesh Karwa. Statistical approximating distributions under differential privacy. Journal of Privacy and Confidentiality, 8(1), 2018.
Oliver Williams and Frank McSherry. Probabilistic inference and differential privacy. Advances in Neural Information Processing Systems, 23:2451-2453 2010.
Jun Zhang, Zhenjie Zhang. Xiaokui Xiao, Yin Yang. and Marianne Winslett. Functional mechanism: Regression analysis under differential privacy. Proc. VLDB Endow. 1141)1136411375, July 2012. ISSN 2150-8097. doi: 10. 10.14778/235022922553 23500253
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See details in Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not foresee direct negative socictal impact from the current work. See discussions in Appendix S-1.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices S-2 and S-3.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes] We believe that we have provided sufficient details to replicate our experiments in relevant sections. public GitHub repository prior to the conference.
We will release our code
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We described how the prior hyper-parameters are chosen in relevant sections. In short, we choose proper and conjugate prior distributions for the log-linear and linear regression models. We also avoid informative priors.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No] We directly display all the data points in the figures.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(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]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "lNQCzrkshRg", "reviewer": "Reviewer_5G7A", "summary": "This paper presents a general MCMC algorithm for approximating the joint posterior distribution of model parameters and true/denoised data, given a corrupted data set that has been privatized using an $\\epsilon$-differential privacy mechanism. The algorithm follows the standard approach for Bayesian inference under measurement error; it iterates between re-sampling the true data as a latent variable given parameters, and re-sampling parameters given the true data. The paper proposes a pointwise Metropolis-Hastings step as the transition kernel for re-sampling the true data, and shows that, under some mild conditions on the noise mechanism, the acceptance probability of this step is lower-bounded by $\\exp(-\\epsilon)$, which is non-vacuous for standard choices (e.g., $\\epsilon=1$). The paper also states the $O(n)$ time complexity of this step and presents a derivation of MCMC's ergodicity in this context. Two cases studies, using a Naive Bayes log-Linear model and Bayesian linear regression, substantiate the theoretical claims empirically.", "questions": "* Please see the \"Strengths and Weaknesses\" section for my comments; if I have understated the novelty of any aspect of the paper, please let me know.\n\n* Proposition 3.2 look like it might follow simply from the fact that the M-H algorithm loops over $n$ data points, re-sampling them pointwise---can you provide some intuition why this result is surprising or challenging to obtain?", "limitations": "The paper is forthright about the assumptions and limitations of the general approach, in particular the assumed structure of the noise distribution. The paper also addresses the possible societal implications of providing an algorithm that \"appears\" to de-privatize privatized data; they correctly state that the method cannot \"undo\" the privacy guarantee, it can only obtain the tightest possible uncertainty about the underlying data, subject to that guarantee.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n\nMuch of the theory in this paper has been presented before or follows directly from previous literature.\n\nFirst, this paper seems to miss its connection to the broad category of Bayesian measurement error modeling. The paper presents \"data augmentation MCMC\" (where the true/denoised data is re-sampled as a latent variable in MCMC) as a novel idea, and dedicates lots of space to its exposition and theory (e.g., proving ergodicity in Theorems 3.3-3.4). However, this general idea and the theory about it is already well-known to the applied Bayesian statistics community, having been introduced by Richardson and Gilks (1993) [1] (or perhaps earlier), and since becoming standard in some probabilistic programming packages (for instance, see the [instructions](https://mc-stan.org/docs/2_21/stan-users-guide/bayesian-measurement-error-model.html) in the Stan User's Guide on how to build a Bayesian measurement error model). \n\nEDIT: The authors have responded to this point. Their setting departs from this setting in that the noise in Bayesian measurement models is usually added pointwise to data points independently (i.e., the \"local model\"), whereas here the noise can be added as in the \"central model\".\n\nThe translation from general Bayesian measurement error modeling to differential privacy is also not new. The specific case where the measurement error comes from a known $\\epsilon$-differential privacy mechanism, is given in section 2 of Schein et al. (2019) [2], who formulate the general problem of \"locally private Bayesian inference\" and describe solution of data-augmented MCMC; this paper misses that citation.\n\nFrom what I can tell, the novelty in this paper is restricted to the formulation of an M-H algorithm that is general to different noise mechanisms, and Proposition 3.1 which bounds the acceptance probability. I really appreciate both of these contributions, and encourage the authors to rewrite the paper to center around their practical applications. However, the general conceptual setup, and Theorems 3.4-3.5, which collectively take up the majority of the paper, all follow directly from existing work on Bayesian measurement error modeling.\n\n[1] Richardson, Sylvia, and Walter R. Gilks. \"A Bayesian approach to measurement error problems in epidemiology using conditional independence models.\" American Journal of Epidemiology 138.6 (1993): 430-442.\n\n[2] Schein, Aaron, Zhiwei Steven Wu, Alexandra Schofield, Mingyuan Zhou, and Hanna Wallach. \"Locally private bayesian inference for count models.\" In International Conference on Machine Learning, pp. 5638-5648. PMLR, 2019.\n\n## Quality\n\nI think this paper is completely correct. I read it carefully and checked the proofs. It's only drawback is its missed citations and the fact that many of its proofs and ideas are not new.\n\n## Clarity\n\nThe paper is very well-written and clear. The technical exposition is well-organized and precise. \n\n## Significance\n\nI think the proposed algorithm is elegant and generally applicable. One can easily imagine rolling it in to existing probabilistic programming frameworks (e.g., Stan), and providing a modular option for differentially private Bayesian inference. However, the majority of the paper is dedicated to theory and exposition of ideas that are not new; I don't think the paper in its current form will be significant for that reason. I encourage the authors to rewrite this paper, focusing more on the practical/applied impact of this general algorithm, which I believe could have fairly significant impact.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5jy0ZDjPFCz", "reviewer": "Reviewer_xd2f", "summary": "In this paper, authors propose a method for noise-aware statistical inference under DP. Essentially, the aim is to enable Bayesian inference that can capture the DP induced noise. Authors propose a novel inference method, that handles the unobserved private data as an additional augmented latent variable to the model. Similar to other recent works on the noise-aware DP Bayesian inference (e.g. Bernstein and Sheldon 2018, 2019 and Kulkarni et al. 2021) the method is based on a single round of data collection from which the posterior of the model parameters is inferred. Authors can bypass the exploding computational cost of introducing tons of latent samples by only considering a particular types of DP data collection methods called (satisfying the Record additivity). By experiments, authors show that the posteriors obtained using the proposed method are well calibrated.", "questions": "Some questions:\n- It would be interesting to see, how the method compares against the Bernstein and Sheldon '19 solution for the linear regression. \n- Also, Kulkarni et al. '21 extend the B&S solution for GLMs by using approximate sufficient statistics. It would be a really interesting to see, would it be possible to write say Logistic regression with the record additivity and see how this compares against the approximate solution of Kulkarni et al.\n- What is the number of samples n for the lin. reg. experiment? (I don't think this was mentioned in the manuscript)\n\nTypo: \\\nLine 228: I think there is an extra \".\" in the end of the line.\n\n", "limitations": "In the negatives, I listed a weakness that I think should be better discussed. I think the  potential negative societal impact (or the lack of it) is sufficiently discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\\\nThe problem authors are solving is relevant. There have recently been plenty of works aiming to capture the noise introduced by the DP mechanism into the posterior uncertainty of a parameter of a probabilistic model. The main contribution of this work is to solve the problem of latent sensitive data. In previous attempts of noise-aware DP Bayesian inference, the latent data has been presented in some aggregate form such as sufficient stats. in Bernstein and Sheldon '18 and B&S '19, or by approximate sufficient statistics as in Kulkarni et al. '21. Without this assumption, the computational cost of having N (number of samples) latent variables will make the inference infeasible. In this paper, authors have introduced a definition for a general type of privacy mechanism called Record Additivity. DP mechanisms satisfying record additivity, have likelihood in a form that is factorizable over the latent sensitive data. Thus, when authors use Gibbs sampling to propose new samples for the latent variables, they don't need to update the entire log-likelihood expression but can change only the term in the sum that corresponds to the proposed index. This avoids computing the likelihood from scratch every time a new sample is drawn. Authors show that the proposed Metropolis within Gibbs sampler targets asymptotically the correct distribution, and also show the acceptance probability as a function of DP quarantee $\\epsilon$. \\\n$\\qquad$ I find this solution very clever, and would be really interested on how wide range of models this approach can actually be extended. In the empirical evaluation, authors consider couple of relatively simple models: a Log-Linear model and a linear regression model. The empirical results mainly demonstrate, that the recovered noise-aware posterior is well calibrated and in terms of mean, follows closely the non-DP solution.\n\nWeaknesses:\\\nIf I am not mistaken, the extent of models that can be solved with this methods is bound to the record additivity. Essentially the functions $t_i$ of Assumption 2, are the way to compare the DP released data to the latent samples. Now, I would imagine $t_i$ should be then characteristic in some sense to actually capture the correct model. I think this should be better discussed.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3UwXF0S1cfq", "reviewer": "Reviewer_5yua", "summary": "This paper introduces an MCMC algorithm for private parameters by augmenting the parameters space with the private date. They propose an MH  and Gibbs sampling type sampler that alternatively updates unobserved variables and parameters. They discuss the acceptance rate and mixing properties for the private setting and provide some simulations to support their claims. ", "questions": "- Some justifications regarding the contributions and advantages of this method over others are needed.\n- How does higher privacy results in a better exploration?\n- This algorithm is exact when k->\\infty. How would privacy be affected in practice when we cut it off? \nhow does this method compare in high dimension to fast algorithms such as the one in \"On Connecting Stochastic Gradient MCMC and Differential Privacy\" by Li et al? \n- What is the evaluation metric exactly?\n", "limitations": "- This work suffers from the lack of scalability due to MH step. \n- It seems like it is incremental and there is not enough justification why this method should be chosen over others that are proven to be faster. \n- Even though the arguments for the proofs are sound but it is nothing novel and it is aligned to what is in the literature. \n", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- It is an interesting problem\n- it is easy to follow. \n\nWeakness: \n- Experimental results are not enough and do not comprehensively back up their claims. For instance, for a high dimensional setting (both parameter space and unobserved space), how would complexity be affected? Since this is an MCMC algorithm, it seems that as we go to higher dimensions it suffers from a lack of exploring state space. How would privacy be affected? Also, comparison to other MCMC-based privatized methods is required both from a complexity and performance point of view. Bigger datasets such as MNIST can be used as has been by other papers. Comparison to Differentially private MCMC and Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC.\n- Contribution seems to be very minor and along with the literature. How does it compare to \"Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC\"? \n- The mixing property and acceptance rate proofs are very standard along with that of MH and other privatized MCMC techniques.  \n- This paper is highly incremental and seems to be an application of doubly interactable [Murray 2012]. The privacy addition is a very minor contribution and is aligned with the literature. \n ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept