Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:
- It is an interesting problem
- it is easy to follow. 

Weakness: 
- 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.
- 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"? 
- The mixing property and acceptance rate proofs are very standard along with that of MH and other privatized MCMC techniques.  
- 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. 
 
questions: - Some justifications regarding the contributions and advantages of this method over others are needed.
- How does higher privacy results in a better exploration?
- This algorithm is exact when k->\infty. How would privacy be affected in practice when we cut it off? 
how 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? 
- What is the evaluation metric exactly?

limitations: - This work suffers from the lack of scalability due to MH step. 
- 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. 
- Even though the arguments for the proofs are sound but it is nothing novel and it is aligned to what is in the literature.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: ## Originality

Much of the theory in this paper has been presented before or follows directly from previous literature.

First, 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). 

EDIT: 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".

The 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.

From 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.

[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.

[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.

## Quality

I 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.

## Clarity

The paper is very well-written and clear. The technical exposition is well-organized and precise. 

## Significance

I 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.
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.

* 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:\
The 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$. \
$\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.

Weaknesses:\
If 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.
questions: Some questions:
- It would be interesting to see, how the method compares against the Bernstein and Sheldon '19 solution for the linear regression. 
- 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.
- What is the number of samples n for the lin. reg. experiment? (I don't think this was mentioned in the manuscript)

Typo: \
Line 228: I think there is an extra "." in the end of the line.


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.
review_title: null

Meta-review: metareview: This paper presents a general MCMC algorithm for approximating the joint posterior distribution of model parameters and private data, given output from a differentially private algorithm. The paper provides new tools for Bayesian inference under privacy constraints, which can be useful for the differential privacy community. There are a few suggestions from the reviewers/discussion. First, even though the authors claimed their results are fully general, they should consider toning it down or at least clarifying upfront their "Record Additivity" assumption, which seems non-trivial. As one of the reviewers remarked, one of the limitations of this approach is that it will not scale well with high-dimensional data. The AC suggests the authors add this limitation in the discussion of the paper.

Other comments:
While not critical, the AC also has a question regarding the following part:
- In line 105: the assumption is that the density of the mechanism's output distribution is known. This has nothing to do with what privacy variant you use to analyze the mechanism. 
confidence: Less certain
Decision: Accept