Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies sampling algorithms for the exponential mechanism by using ergodic theory and perfect simulation. They also give an algorithm that provides pure DP at the loss of some utility. 
main_review: The paper has three contributions: (i) an exact algorithm that runs in a finite time and provides approximate DP, (ii) an exact finite time algorithm for pure DP, and (iii) an algorithm that has a faster run time but at an expense of loss of utility. 

The paper makes an assumption that the transition kernel satisfies a minorization property. As an example, they show efficient sampling for two cases: (i) d-dimensional mean with L_1 loss, where they compare pure and approx DP cases, and (ii) ridge regression K-norm gradient mechanism. 

I think the paper is well written and I was able to follow the first 9 pages of the paper. I could not verify the proof in the time, so I cannot vouch for the correctness of the paper. Under the assumption that the proof is fine, there is definite merit. 
limitations_and_societal_impact: I am not entirely sure if the current implementation does not suffer with floating point arthematic. The two examples are interesting, but seems little restrictive.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses an exact finite runtime sampling algorithm for the exponential mechanism by including an artificial atom in the target distribution.

The main contributions are:

1. The paper proposes an exact finite-runtime algorithm (ConfAtomPerfect) for implementing the exponential mechanism with ε-DP guarantees using atomic regeneration.

2. The paper derives a modification of the previous algorithm (RandomAtomPerfect) that satisfies ε-DP but outputs a sample from a modified target distribution with smaller utility and shorter runtime.
main_review: Comments:

1. Lack of experiments. The paper only contains 2 toy examples. Moreover, it also lacks comparative experiments with other related methods. So, it is difficult to evaluate the significance of the contribution.

2. There are too few references for similar/related methods.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Since exponential mechanism, which is important in differential privacy (DP), is usually difficult to sample  because of intractable distribution and existing sampling methods like MCMC cannot guarantee privacy, this work focuses on implementable finite sampling method for exponential mechanism based on ergodic theory with include artificial atoms into target distribution to balance tradeoffs by guaranteeing privacy under DP manner and improving runtime compared with previous methods.
main_review: Pros:
1. Although this work is based on MCMC, this work guarantees \epsilon-DP by using atomic regeneration to introduce an exact finite-runtime algorithm to implement exponential mechanism. And even the modified version can outputs a sample with smaller utility and shorter runtime as well as guarantee for \epsilon-DP, which are crucial tradeoffs.
3.  This work provides rigorous definitions and theorems to theoretically explain the effectiveness and correctness of proposed algorithms.
4. This work carefully states the limitation of the proposed approach and provide potential improvement, such as generic utility for the exponential mechanism.

Cons:
1. Be honest, I work on MPC side and has bare knowledge of DP, so, as far as I am concerned, there is no obivious cons in this work and I am willing to see other reviewers’ comments to make the next move.
limitations_and_societal_impact: No potential negative societal impact has seen.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a MCMC approach to mimicking the DP Exponential Mechanism. Moreover, its main claim to fame is that it gives sufficient conditions for finite-time convergence. These conditions are based on the existence of "atoms" (Def.4), which, in this work's setting, is the optimal state. In addition, the approach is evaluated on two cases (mean estimation and Ridge Rigression on a bounded domain.
main_review: I am a big fan of using MCMC to tackle infeasible problems, ones for which that Exponential Mechanism is too "time consuming." But this paper, I am afraid, does not really give useful bounds for such problems. Instead, it relies heavily on \beta = the infimum of the transition probability between ANY state in the space and the atom (Thm 2, bulletin 1); and \inf{p_accept} -- the expected mass entering any state. Now, if we examine Figure 1, LHS, we see an interesting phenomena: as \epsilon *increases* it takes longer for the chain to get close (in TV-distance) to the stationary distribution (the output distribution of the Exponential Mechanism). This is a direct result of the dependency on the inverse of \inf{p_accept} --- as \eps increases, the probability of transition into a point which is very unlikely to be a solution decreases exponentially, causing the runtime to be longer. But the result is that in many cases -- especially over large state space -- the convergence bound given in this work aren't really useful...

What this paper does show, is that certain cases can be implemented efficiently. I am, however, a bit on the fence as to how important are these cases. On the one hand, I am very much in favor showing any result one can about the convergence of MCMC into the Exp-Mech, as it is so useful in real life applications; on the other hand, I am not convinced that there's enough "substance" here to be of any true interest to the DP community. I eagerly await the authors' rebuttal and the following discussion to make my final decision, but, as it currently stands, I do not think these results are important enough...
limitations_and_societal_impact: Irrelevant.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper explores the use of finite runtime samplers applied on exponential mechanism (EM). The paper presents two main contributions: (1) an algorithm to produce exact samples from EM under certain conditions, (2) an algorithm to alleviate computational cost of contribution (1) with a loss in utility. There are also experiments that demonstrates the utility tradeoff between (1) and (2).
main_review: Sampling from EM using classical MCMC sampling techniques (such as Metropolis-Hastings) is in general hard, since it has been difficult to guarantee that the chain has actually converged to the target distribution which is mandatory for the privacy guarantee. This paper proposes a method(s) to assert the correctness of the samples by using established techniques from MCMC literature. The main workhorse of this paper is sampling with atoms, that are sort of checkpoints in sampling domain. Samples between visits in the atom can be treated as samples from the target distribution and therefore guarantee the exactness of the method.

Augmenting the original sampling problem (sampling from EM) with a sampling from an atom component, authors are able to provide $\epsilon$-DP for loss functions that have unique zeros. I think this approach is rather novel and compared to the previous work by Ganesh and Talwar [1], the present work quantifies the $\epsilon$-DP instead of pushing the uncertainty in sampling to the $\delta$ privacy parameter. I also like the proposed algorithm in it's simplicity (it's a basic rejection sampler).

However, there are several weaknessess in the approach that make it less appealing. First, authors present the math for only a few very simple transition kernels. I doubt that MCMC methods using these kernels would have any use in any realistic scenarios due to the inefficient sampling. Also, I believe that extending the approach to more complex kernels and loss functions might be very difficult. Second, the assumption of unique zeros for the loss function is rather strong one. I'm not sure if it is any better than the strong convexity assumption in [1] and most certainly it is worse than assuming Lipschitzity as in [1].

Besides the technical limitations, I believe the paper is bit difficult to follow. There are many highly technical concepts that are rushed through which makes it difficult to connect the different parts of the paper.

Minor comments / typos:

- Line 59: Reyni
- Definition 1 is phrased bit oddly in my opinion. I understand what you mean, but for a reader unfamiliar with DP this might be bit difficult to follow. Maybe "for all mechanisms $\mu \in \mathcal{M}$"?
- Definition 2, B is not used anywhere after it is introduced.
- Theorem 1, might make sense to include a description of the V-norm.
-  Line 89: "common common"
- Should there be a minus in front of the $\log(n)$ in Eq. (2)?
- Definition 4., missing the cite?
- Page 4, missing closing parenthesis after "i.e. $\mathcal{Y}$ ..."
- Page 4, before you define $\tilde{f}_X(y)$, is the respectively correct? To me it now reads that (1-k) gets assigned to atom.
- Theorem 2, I think you should use X instead of x in $x \in \mathcal{X}^{n}$ to be more consistent with the notation.
- Theorem 2, claim 2, are the samples really from $f$? I would imagine they are from $\tilde{f}$ as described in the output of Alg. 1.
- Theorem 2, is the expected number of samples the same as expected time of return to the atom?
- Appendix, I don't quite follow the proof for Thm 2. How do you reach the expression after "This implies:"? How is it possible that there is still a Diracs delta (in $\tilde{\eta}$) remaining after the integral?
- Page 6, last equality. Where does this come from?
- Font in Figure 1 is way too small.
- I don't follow Figure 1 at all. What are the subtitles "n=100, n=200, n=500", the sample sizes? What are the axes? How come delta decrease as the chain lenght increases? The right column shows results on simulated data, and I presume the boxes show some kind of standard error. Are these results purely analytical, or are these errors computed over some simulation? If latter, what was the number of repeats/simulations?
- Figure 2, is the y-label "Err" correct? I think you mean utility.
- reference 16, the title of the paper is truncated
- reference 17, "HItomi"

References:

[1] Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence analysis of discretized langevin mcmc. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7222–7233. Curran Associates, Inc., 2020.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The reviewers were overall positive about the paper, modulo the following concerns, which came up during the discussion period.

1. Comparison to prior work, especially to Ganesh and Talwar. In particular, the reviwers will be more satisfied if even just empirically -- one shows that the algorithm outperforms some existing algorithms on some measure (say, runtime), and 
2. Since the assumptions in the paper are different than prior work, it would be important to contrast them with prior work. In particular, w.r.t. curse of dimensionality.
Decision: Accept (Poster)