Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms
Authors: Jeremy Seeman
Matthew Reimherr
Aleksandra Slavkovic
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Markov Chain Monte Carlo
Perfect Simulation

Abstract: Implementations of the exponential mechanism in differential privacy often require sampling from intractable distributions. When approximate procedures like Markov chain Monte Carlo (MCMC) are used, the end result incurs costs to both privacy and accuracy. Existing work has examined these effects asymptotically, but implementable finite sample results are needed in practice so that users can specify privacy budgets in advance and implement samplers with exact privacy guarantees. In this paper, we use tools from ergodic theory and perfect simulation to design exact finite runtime sampling algorithms for the exponential mechanism by introducing an intermediate modified target distribution using artificial atoms. We propose an additional modification of this sampling algorithm that maintains its $\epsilon$-DP guarantee and has improved runtime at the cost of some utility. We then compare these methods in scenarios where we can explicitly calculate a $\delta$ cost (as in $(\epsilon, \delta)$-DP) incurred when using standard MCMC techniques. Much as there is a well known trade-off between privacy and utility, we demonstrate that there is also a trade-off between privacy guarantees and runtime. 

Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms
Jeremy Seeman Department of Statistics Penn State University State College, PA 16803 jhs54968psu. edu edu
Matthew Reimherr Department of Statisties Penn State University State College, PA 16803 mlr360psu. edu
Aleksandra Slavković Department of Statistics Penn State University State College, PA 16803 abs 120psu0puu... edu
Abstract
Implementations of the exponential mechanism in differential privacy often re- quire sampling from intractable distributions. When approximate procedures like Markov chain Monte Carlo (MCMC) are used, the end result incurs costs to both privacy and accuracy. Existing work has examined these effects asymptotically, but implementable finite sample results are needed in practice so that users can specify privacy budgets in advance and implement samplers with exact privacy guarantees. In this paper, we use tools from ergodic theory and perfect simulation design exact finite runtime sampling algorithms for the exponential mechanism by introducing an intermediate modified target distribution using artificial atoms. We propose an additional modification this sampling algorithm that maintains its e-DP guarantee and has improved runtime at the cost of some utility. We then compare these methods in scenarios where we can explicitly calculate a cost (as in (c, 6DDD) incurred when using standard MCMC techniques. Much as there is well known trade-off between privacy and utility, we demonstrate that there is also trade-off between privacy guarantees and runtime.
Introduction
1.1
Problem setup
The exponential mechanism 17 is one of the workhorses of e-differential privacy (e-DP). Many com- mon DP mechanisms, such the Laplace Mechanism (7), K-norm and K-norm gradient mechanisms
22 4]. PMSE mechanism [24). and even posterior sampling under certain regularity conditions 26 can all be viewed as instances of the exponential mechanism. In fact, any mechanism can be equivalently expressed as an instance of the exponential mechanism depending on the choice of loss function and base measure 22. However, the output of the exponential mechanism often has an intractable distribution, making it difficult to sample from in practice. This necessitates using sampling algorithm such as Markov chain Monte Carlo (MCMC) an approximate sample from the distribution. However, methods like these only approximate the target distribution asymptotically, meaning that the resulting sample need not satisfy the originally prescribed privacy guarantees.
computationally generate
In practice, analyzing the privacy cost incurred due sampling is messy problem. Existing approaches rely on analyzing convergence rates of distances between the approximating distribution and the target distribution. While these approaches have produced nice theoretical results, the analyses are usually asymptotic and lack closed form expressions for constants required to determine saite-sample incurred costs. However, for uniformly ergodic chains that admit atoms their state
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

space, these sampling procedures are not only more directly quantifiable but also admit finite runtime algorithms for exact simulation from the target distribution. This suggests that modifying the target distribution of the exponential mechanism to include an artificial atom may eliminate the privacy cost of implementing the sampling algorithm; such modifications are the focus of this paper.
1.2 Contributions
Let [x( be the output density of the exponential mechanism with confidential data X and output space E Y/ (we will fully define this notation the methods section). In this paper, we consider sampling from fx by first sampling from a modified target density as a mixture of the form & [0, 1]:
fx(v) = (1 - k))x(v) (y)
In particular, we introduce two different methods which we will give names and briefly describe:
Conf Poofffeterffttt gx(y) (y) is point mass at the confidential data output, and the target distribution is fx(3) conditioned on NOT releasing the confidential data, yielding an exact draw from fx-
RandomAtoomPerfen 9x (y) is the mass function for an implementation of the discrete exponential mechanism over finite test point space.
Our contributions are as follows:
1. We use classical methods from MCMC theory to derive exact sampling algorithms for instances of the exponential mechanism with (c, 6DD guarantees.
2. We propose an exact finite-runtint algorithm (Conf AtomPerfect) for implementing the exponential mechanism with c-DP guarantees using atomic regeneration.
3. We derive two modifications of the previous algorithm (i.e., RandomAtomPerfee and Conf AmmAndRunt imePerfect) that satisfy e-DP. The first modifies the target distribution and does not resample to sample from fx. and the second allows the implementation to be independent of runtime, offering even stronger privacy guarantees.
4.
We compare the proposed methods for a few explicit examples to demonstrate a new three way trade-off off between, privacy, utility, and runtime.
1.3 Related literature
Results from MCMC theory have addressed privacy loss due to approximation by analyzing conver- gence rates total variational distance (T8) and Rényi divergence (12). In the latter paper, the authors argue against characterizing the distance between the MCMC sampled distribution and the target distribution in terms of total variation because lacks the
compositional properties of Rényi-DP, allowing for the derivation of convergence results with better asymptotic dependence on the dimension the output space. Our work differs in few key directions. First, we require weaker assumptions about the loss function. In particular, V-geometric ergodicity only requires sub-exponential tails, which relaxes strict convexity and/or Lipschitz. assumptions about the loss only require uniform ergodicity of the original chain, which is
function. For our perfect sampler, often achieved by virtue of bounding the database space. Second, we consider simpler classes of base MCMC algorithms that may be sufficient for wide class of problems where the output dimension is smaller than the input dimension. Third, our work derives algorithms with exact implementation steps and exact privacy guarantees. Previous results state their results in terms of asymptotic sample complexities for the Langevin dynamics step size and run time, neither of which are immediately helpful for practitioners who want use these algorithms and calculate their provable guarantees.
Methods
2.1 Notation
We recall some definitions and theorems here:

---

Definition 1 (Differential Privacy [7]. Let M - {px X XEX) be a collection of probability measures over common measurable space ()) F) indexed by elements of X". The mechanism M satisfies (e, 6DDP for all B E F and X, X' E n differing one entry:
(x S (B)
Definition 2 (Exponential Mechanism (.). Let Lx x x + [0, oo] be measurable loss function for each X E X Suppose, for all adjucent X, X,X' x and y E y:
Lx (y) Txx(u)) S As. < 00.
The exponential mechanism the (e, D mechanism defined by the collection of measures each with density:
e<xx(u)
(x(w) (v) x exp
2 (-2A,
with respect to a common base measure vly) over F),
Frequently, v is taken to be the Lebesgue measure over a subset of TRd. Throughout the paper, let {Mm,,X 1.00 m==1 be sequence of probability measures such that Mm,X converges in distribution to μox for all X E Xmm We assume the chain defined by the transition kernel xIx x F + [0, and
the starting value yo E y. Throughout the paper, use the concept of minorization:
Definition 3 (Minorization Condition). Suppose there exists a function 8 y + [0, 1] and probability measure v ().F) such that for all A E F and y E y:
1x A) 2 s(v)v(A).
We call these the minorization function and measure, respectively. Define the associated remainder kernel Ry, y x F + [0, 1] such that:
(x, A) s(y))(A) Rl,,(y))
Our results rely on the existence of minorization functions and measures for our output distribution μх- This assumption will give us uniform ergodicity properties later Note that limitation of our approach is that we cannot apply these methods to exponential mechanisms with unbounded output spaces such R$ but it does work for compact sets of IR* In practice, this limitation is not major barrier to generalizability. as the the output space is often intentionally bounded to control the sensitivity of the loss function, although there are exceptions (e.g.. 24
The following result shows that MCMC sampling from the exponential mechanism induces 6, penalty as a function of the upper bound on the total variation distance
Theorem (18)). A mechanism Mm {pm,x M, at time m 2 7(a) is (c, (aD where & & a(1 + e²)
X) approximating the exponential mechanism,
r(a) sup inf 0 ||pxx - -xxl aa. XEXx
Note that the upper bound on the 8 cost incurred above is specific to the sequence's 's properties (for example, transition probabilities and starting locations for MCMC). However, the upper bound not specific to the confidential data X. Such generality is necessary to preserve (e, 8)-DP, the mixing time can vary based on the confidential data. This means to ensure privacy, one must find realizations of X that are "least favorable" ensure privacy in the worst-case scenario.
One common heuristic here choose < 1/n, so that the relative privacy risk violation affects, in the worst case scenario, all information about one individual in the dataset. One common "fast- mixing" regime for these chains geometric rate, where the total variation distance is O(r²²) for some (0,
Definition 4 (V V--eomeerrcc ergodicity (]). For a Markov chain where Pm.X - μX in distribution oc, say the chain is V V-geometrically ergodic if there exists constants C R , E (0, 1), and a function V oc) such that for all m. E M and starting points yo E W:
[|mm,x - xx llrv S
l| - pxlly S (Vo)))
(1)
When V is constant function, functioo,,
say the chain is uniformly ergodic.
3

---

Many common algorithms, such as MetropoliisHHastingss [ and common variants such as Hybrid Monte Carlo [33 and Hamiltonian Monte Carlo [T6], are geometrically ergodic under mild regularity conditions. For these algorithms, it immediately follows that for any specific realization X E X if we choose m (l)og()))
|mm, - pxllzv S (yo))rroot = -
-oexx-xxllyy
= O(1/n).
(2)
Therefore, up to constant, for a fast mixing sampling algorithm we require at least order log(n) samples achieve a negligible 5 for an empirical privacy guarantee. However, there are two complications to formalizing this idea. First, the constant of proportionality for the rate depends on C, r. V. and C. Second, the mixing time depends on X, and the privacy guarantee depends on fast mixing for all possible X E X".
2.2 Properties of Markov chains whose state spaces admit atoms
The complications above can be alleviated when the target distribution admits an atom, specifically proper accessible atom with respect to the transition kernel llx:
Definition (Proper Accessible Atom). A set y is a proper accessible atom if:
1. (Regeneration measure) There exists measure Pregen on F) such that:
[y A) Pregen (A)
Vy E E, F.
2. (Accessibility criteria)
(xx
V.
3. (Recurrence criteria) the chain returns infinitely often to y with probability
When the state space admits an atom, the constants in Equation I have closed form expressions (see [1] Theorem 4.1] for an example). Furthermore. Markov chains that admit atoms have special split chain representation [20). where the state space is extended with a binary indicator indicating presence in the atom (i.e., V x {0,1}) 1}). For this split chain, let 7 the time takes for the split Markov chain to return to said proper accessible atom after leaving it. Hobert et al. [3] show that the stationary distribution admits an infinite mixture form:
P(r 2 m) m== E[T]
20
px (4)
=
P(Y,, EA m).
If one can sample from the mixture components well the conditional distributions feasibly (i.e., in finite expected time), then one can sample from px. Following [15], the authors focus on the singleton case when y {a} for some E y. Define:
pvv) A IIx (v. {a}).
there exists 3 > such that inf p(v) > 0, then wen can use Algorithm to produce an exact sample from the target distribution.
Because many target distributions do not admit the atom required, Brockwell proposes a way to introduce an artificial atom into new stationary density fx- In our setting, we propose introducing an atom at the confidential response mixed with the c-PP stationary distribution with proportions k and k. respectively, for some i (0, 1):
fx(x) A (1 k))x(() AT (y=a);
with respect to a new base measure:
ú (1- k) kKa
where v is the original base measure and & is the Dirac delta function representing a point mass at the confidential data. In particular, if the Metropolis- qx (y, 3²), then one can construct a new Metropolis- Hastiiss transition kernel with symmetric proposal density:
kernel has symmetric proposal density
1 [9x (v. 3/) + [o]=
aly.

---

Algorithm 1: Exact implementation for sampling from a singleton atom mixture [1]
Result: Y fx
Input: Transition kernel xx,, singleton atom a E y/ minorization 3 0
Sample M Geometric(3), set Y1 a;
for m 2 to M do
Using the Bernoulli factory algorithm [4]. sample:
1 1Ix (m {a})
Zm Bernoulli
1 3
if 7m = then
Sample Y, Rs 1x (-1a)) using rejection:
1. Propose Y ~ 1Ix mY
2. Accept if Y * a, else go back to 1.
else
Y =
end
Release Ya-- end
2.3 Extensions to private sampling
The framework established by 15 requires assumptions that are particularly amenable to privacy preservation. First, the minorization conditions needed to ensure finite runtime are often satisfied by design; most Markov chains are implemented over compact state spaces, where the compactness enforced so that the exponential mechanism's 's loss function has bounded sensitivity. Second, can choose to add an artificial atom at the confidential data, namely any point a Y such that (a) 0 without loss of generality (note that need not be unique). This yields first main result in Theorem 2 and Algorithm 2
Theorem 2 (Conf AtomPeffect). Suppose that y compact subset of R& and let Lx be loss function based on confidential data x E X where Lx(a) = 0 for some E y. Suppose px({a)) O. Let Q be Metropolis-Hastingg transition kernel with symmetric proposals, and let Q and g be as defined above. Then:
1. There exists a constant 3 > such that:
inf (u, {a}) B.
yEY
2. There exists an algorithm (implemented by Algorithm I to sample from density fx that satisfies c-DP with expected number of total proposed samples N Nprop:
48
B[Nprop S
12 - k)2 in Prcccpe (3))
where:
(A) & / (x((.)0) min 1, fx(1') fx(u)
dv(y/).
Proof.
(Sketch; complete proof in appendix) By construction, the Metropolis- Hastingg transition kernel is maximized for the modified chain. Taking B & yields the first result.
For the second result, the runtime is split into four components:
Nouter Number of outer loops in Algorithm [1
Nineer Number of rejection proposals to sample from Y ~ (Y.-(mmm1.))) NBern Number of Bernoulii factory samples to select Zm in Algorithm !
NNomatommic & Number of samples from fx required sample from fx.
5

---

In the complete proof, we show:
E Nouter
6.
E N Inner
S ((1
- k) infyey Prccopt(U))
E N Born 24
E:
E
N Nonatoumii
= -k))-
This yields the desired bound.
Algorithm 2: ConfAtomPerfect:: e-DP exact sample from exponential mechanism
Result: ~ ~5x
Input: Sample space Y' and loss function Le satisfying the conditions of Theorem 2 while TRUE do
Sample Y ~ using Algorithm if y * a then
Release Y.
end end
We make a couple remarks about this result. First, we note that the bound the runtime can depend on the confidential data and does not require this is a nice property, it also assumes that the runtime of the algorithm is not a possible source of side channel information (more this in the discussion). Second, the result above only uses symmetric proposals so that the criteria for transitioning to the confidential data does not depend easily be extended to arbitrary proposals in
take the infimum all possible data sets. While
on the proposal distribution. However, this result cases where the minorizing constant can still be calculated. Third, note that we do not include the case where μx (fa)) > as this corresponds an exact implementation of the algorithm derived in [15]. Finally, we anticipate the expected runtime bound above is very loose; the bounds Nerr and Ninner are generic, and can be much lower for specific implementations. Moreover, Npropp loosely bounded above by the product of the terms in the proof sketch, but in practice not every branch of Algorithm is traversed each time.
Algorithm 2 relies on multiple passes through Algorithm in order to sample from the original target distribution; however, upon failure do so, we could alternatively sample from discrete approximation of the exponential mechanism target distribution. This yields a less computationally expensive method, avoiding the additional (1 k factor in implementing the mechanism with pure e-DP, at the expense of some loss in utility due to the discrete approximation.
Corollary 1 (RandomAtomPerfeed
In the same setup as Theorem
2 let (1 Y and let gx
be the mass density of the exponential mechanism implemented on sampling algorithm (implemented by Algorithm 3 with target density:
(f)
Ji-1 Then there exists
fx(u) = k))x - kg)(
(3)
with respect to the mixture measure:
1 - (1- +
E
with expected number of total proposed samples N Propp"
48
E N Npropl
k2(1 k) inf (sccope
And utility:
(x(S)) k v(S=/2) exp
65 4 (T
keep
(
2A,
E
24, 1og(t) 10g())))
Where S. A (y Lx(v)= 2 E}.

---

Algorithm 3: RandomAtoomPerfeets e-DP sample from mixture of discrete and continuous
exponential mechanisms
Result: ~ fx as Equation 3
Input:
Sample space )' and loss function L. satisfying the conditions of Corollary
Sample Y using Algorithm
it A then
Release Y.
else end
Release Y ~ 9x
One potential issue with both algorithms 2 and 3is is that Niner contains confidential information about X. presenting itself as a potential form of side leakage. However, following [3. we can exploit the memorylessness property of the Geometric distribution release a result whose runtime is independent of the data (at cost due to runtime). This is implemented in Corollary
Corollary 2 modification of Algorithm 2 where:
In the same setting as Theorem there exists
1. The total number of proposed samples (either real or partially artificial) Nprop is indepen- dent of the data (i.e., satisfies O-DP).
2. The expected runtime of the algorithm is upper bounded by:
48
ppropl S k²
Where:
A inf inf PAccopt (v) 7 zEX" yEy
3 Examples
3.1 d-dimensional mean with L loss: comparing c-DP and (c, 8)D guarantees
As first example, let y [0, 1jd, (v(v) | x [| and y be a uniform measure over y This analogous to the multivariate Laplace mechanism but with bounded output space matching the bounded inputs we expect from X. Note that although we can implement exact samplers in this scenario, the goal of this example is to illustrate the effect of proposal choice on runtime and privacy Derivation of all example results are in the appendix.
costs using MCMC versus using Algorithm 2
We consider two different proposals for MCMC. For the first algorithm, derive Metropolis- Hastings Markov chain constructed with proposal independently drawn uniformly over [0, 1)d. The slowest-mixing chain is easily identifiable using results from 11:
||xx. #xxlly (1 wniM
where,
2dd (2d e cnn
BMCMC,Unf
cn
Derivation of this result is in the appendix. implementations of the exponential mechanism. Note that, using the main result in 25], Equation constant-sharp and cannot be improved.
This allows to immediately construet Oe
Similarly, we can use Laplace proposals of the form:
(x v') x exp (-a ly s v/lli,,)
for which we have a new rate of convergence given analogously by:
LMCMC.LOP & (2a)a exp (- (-add + en =)
( (1
7

---

epsilon
logt0(Dett)
-10
0.01
0.02
200
0.1
log log10(ChainLength)
n=100
n=200
n=500
0-
epsilon
(oget(Deetaa
0.02
.000
0.05
-300
12
log 1g(h(nhiineength
Figure 1: Delta costs incurred due to MCMC implementation with uniform independent proposals and symmetric Laplace proposals, top and bottom respectively. Dashed line corresponds to smallest 64-bit double floating point precision; note this does NOT mean the resulting algorithm c-DP, but instead that the 5 incurred is smaller than the smallest floating point value reportable by the machine.
10"
(og10/Nprop)
betas
107
5.11
X- Beta
10'
X- Beta 10,
10'
0.01
0.02
0.25
0.1
0.61
0.02
605
0.51
0.02
0.05
Epsilon
Figure 2: Distribution of realized N Nprop for Example with symmetric Laplace proposals at a = ne nc/2, d = 1, and different distributions on X (line represents median). As expected, run-time increases both and increases.
The runtime for Algorithm 2 depends the confidential data. To demonstrate this, simulate X from three different Beta distributions: one uniform (X Beta(1, 1)), one with unimodal concentration (X ~ Beta(10 10, 10)), and one with concentration at the boundary (X ~ Be and compare the distribution of Nprop across the cases in Figure 2 All simulations are implemented in R [1 and figures were produced using ggplot2 [27] under GNU GPL v3.
The runtime results presented in figures ToaresTaane and illlstrate the phenomena the discussion for Theorem 2 For the MCMC implementations in Figure [ even though we expect the Laplace proposals to mix faster in general, the worst case mixing time actually better for the independent uniform proposals. For example, at n 100 and = .01, we require a Laplace proposal chain 10 times longer than the equivalent uniform proposal chain to achieve a computationally negligible Alternatively for perfect sampler in Figure the runtime for the perfect sampler decreases when the data is more likely be concentrated at the center of the output space (as Beta(10, 10)) as opposed the boundary of the space (as in Beta(.1,.1)).

---

3.2 Ridge regression K-norm gradient mechanism: comparing confidential and random atoms
Next, we consider Ridge regression [T]. We will use the K-norm gradient mechanism following 22]. variant of the original exponential mechanism whose noise asymptotically negligible as co. In the interest of keeping consistent notation, let:
- {y R'
1lvll S B).
Let X [-1, and Z E [[-1, 1]". Define the original loss function &x (t)):
1 || Xyl12
X llvll2
(v(v) =
For any X, X' that differ on one element and y E y: Vix(v) Vix 2 B) sup
||=|| 2 + B)p
=E(0.1|p
This yields a final mechanism given by:
fx(v) x exp (- 4(1 B)p
("(xy-Z)) -2oll1) 1 [I
(5)
Because of similarities between functional forms, the exact sampling procedures will behave the same as the analogues in the previous example. In particular, note that the worst-case runtime calculation does depend on the integration constant in Equation when the proposals 9x are symmetric, since:
exp (- (-HIfBIE XXT(Xy/ - 1/11.))
PAccept (v) =
ax (y. (u, min 1,
du(s))
SB
exp (-u(+BBp || Z) +>ull))
This property is not shared by the MCMC estimator, demonstrating an advantage of this procedure.
Our main goal is compare the utilities of Algorithms and 3 meaning need quantify the utility cost of discretizing the output space with some probability k. To analyze this, we simulate data from Ridge regression model with p 5 and randomly sample É points from the L, ball of radius B = 1 on which to implement the discrete exponential mechanism. By varying and e and repeating the experiment Nexp 1000 times, we calculate:
Err(e, {, & Q.05 [[ ([[[x(x)) (1) 2e)
where Q.os is the 5% quantile across experiment replications. This captures with approximately 95% confidence kind of "worst case" utility bounds by choosing particular discretization at random for our Ridge regression. The results of the experiment are in Figure] with full simulation details in the appendix. Since the discrete exponential mechanism utility Monte Carlo estimate of the continuous exponential mechanism utility, we see as expected that the utility increases to the continuous upper bound as - For our particular example, this suggests that could choose f large enough that the utility of the discrete mechanism close to that of the original exponential mechanism with high probability. However, further investigation is needed understand these effects in higher dimensions or for more complicated loss functions.
Discussion
We proposed some techniques for implementing the exponential mechanism with exact privacy guarantees and some pros and cons of the various approaches above. We hope that techniques like these can be considered when practitioners are either unwilling to incur 8 cost or are otherwise worried about the leakage of sensitive information due to disclosure of implementation details. Additionally, our corollaries and simulations demonstrate new ways of trading off privacy, utility, and now run-time, whereas traditionally only the trade-off between the first two was considered. This can help practitioners quantitatively negotiate the realized costs of implementing more generic DP algorithms.

---

epsilonO011
epsilon
epsilon 10
1.00
ell
0.75
10
0.50
1000
10000
0.00
0.25
0.50
0.75
1.00
1.26.00
0.25
0.50
0.75
1.00
1.28.00
0.25
0.50
0.75
1.00
1.25
s/n
Figure 3: Utility of the discrete exponential mechanism using points sampled uniformly from the support of the distribution in Equation S]
4.1 Limitations
As with any real-valued private computation, we must be careful about the complications of floating- point arithmetic and other side channel vulnerabilities [19). Just because machine cannot report a cost below its floating point precision does not mean the system is invulnerable. In particular, runtime issues pose practical threat to privacy preservation when using these mechanisms; longer runtimes tend to correspond to rarer events, leading to indirect leakage. This implies our methods are best used for non non-interactive data analyses, in which runtime information leakage is lesser concern. Future work could address methods of masking or privatizing the total runtime in a way that masks how much computation time went into sampling from the target distribution.
Additionally, we have restricted our examples to relatively well-hehaved distributions that allow us analytically characterize the constants needed for exact sampling. Numerical analysis of these constants are not the primary focus of the literature on perfect sampling, but understanding additional practical applications estimate otherwise bound these constants would be worth investigating. Additionally, the methods we propose suffer from curse of dimensionality problems and may become prohibitively expensive for large d noted in [2] Still, many common problems fall into the regime where d < and X is not discrete; this is where we believe our work is most applicable.
Finally, reiterate that uniform ergodicity of the original chains is not only sufficient but often necessary for the existence of perfect sampling methods with finite expected runtime [3). However, the minorization constant suffers from of dimensionality effects, meaning the runtime will often suffer for high-dimensiong results. Feasible and efficient algorithms for perfect sampling in high-dimensional settings remains an open challenge in mathematics.
4.2 Future research
First, understanding the utility trade-off between Algorithms 2 and requires deeper understanding of generic utility for the exponential mechanism. Although there has been some of work on asymptotic utility of the exponential mechanism such as 2 10), surprisingly little work has been done on exact finite sample guarantees. In the special case when the loss function is convex, the exponential mechanism's 's target density is log-concave yielding many nice properties in terms of information concentration (5). These should be further investigated to determine when modifications to the target distribution like those proposed here are prohibitive to utility in realized terms.
Additionally, the upper bound provided in Theorem I may be loose in practice, and alternative convergence diagnostics besides total variation distance may be used to better quantify the privacy guarantees up to an approximation (see 9 for a comparison of some Monte Carlo error estimation approaches). We expect there to be cases where Langevin dynamics or other sampling techniques with desirable mixing properties in practice could quickly produce mathematically negligible values; the only open question is turning this heuristic into quantifiable guarantec.
10

---

5 Acknowledgements
This work is supported by NSF SES- Thanks to Jordan Awan and Alexei Novikov for helpful discussions about this topic. We declare no conflicts of interest.
References
[1] Rates of Convergence of the Hastings and Metropolis Algorithms. The Annals of Statistics, 24(1):101-121, 1996.
[2] Jordan Awan, Ana Kenney, Matthew Reimherr, and Aleksandra Slavković. Benefits and pitfalls the exponential mechanism with applications to hilbert spaces and functional pea. In International Conference Machine Learning, pages 374-384. PMLR, 2019.
[3] Jordan Awan and Vinayak Rao. Privacy-aware rejection sampling. arXiv:2 00960 2021.
arXiv preprint
[4] Jordan Awan and Aleksandra Slavković. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. Journal of the American Statistical Association, pages 1-20, 2020.
[5] Sergey Bobkov, Mokshay Madiman, et al. Concentration of the information in data with log-concave distributions. Annals of Probability, 39(4):1528-1543, 2011.
[6] Anthony E. Brockwell and Joseph B Kadane. Identification of regeneration times in meme simulation, with application adaptive schemes. Journal of Computational and Graphical Statistics, 14(2):436 2005.
[7] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[8] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations differential privacy. Founda- tions and Trends in Theoretical Computer Science, 93--4)211-407 2014.
[9] James M Flegal, Murali Haran, and Galin L Jones. Markov chain monte carlo: Can we trust the third significant figure? Statistical Science, pages 250-260, 2008
[10] James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of privacy-preserving bayesian data analysis. arXiv preprint arXiv:
2016.
[11] Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning. volume 1. Springer series statisties New York, 2001.
[12] Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence analysis of discretized langevin meme. 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.
[13] James P Hobert, Christian Robert, al. A mixture representation of π with applications in markov chain monte carlo and perfect sampling. The Annals of Applied Probability, 14(3):1295- 1305, 2004.
[14] Mark Huber. Nearly optimal bernoulli factories for linear functions. Combinatorics, Probubility and Computing, 25(4):577-591, 2016.
[15] Anthony Lee, Arnaud Doucet, and Krzysztof Latuszyúski. Perfect simulation using atomic regeneration with application to sequential monte carlo. arXiv preprint arXiv: 1407.5770. 2014.
[16] Samuel Livingstone, Michael Betancourt, Simon Byrne, Mark Girolami, al. On the geometric ergodicity of hamiltonian monte carlo. Bernoulli, 109-3333319-31388 2019.
[17] 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. IEFF, 2007.
[18] Kentaro Minami, Hitomi Arai, Issei Sato, and Hiroshi Nakagawa. Differential privacy without sensitivity. Advances in Neural Information Processing Systems, pages 956-964, 2016.
[19] Ilya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM conference Computer and communications security, pages 350-661, 2012.

---

[20] Esa Nummelin. A splitting technique for Harris recurrent Markov chains. Zeitschrift für Wabhschhennicckeetttheeeee und verwandte Gebiete, 43(4))309-318, 1978.
[21] Core Team. R: Language and Enviroument for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2021.
[22] Matthew Reimherr and Jordan Awan. KNG: The K-norm gradient mechanism. Advances in Neural Information Processing Systems, 32:10208- 2019.
[23] Gareth Roberts, Jeffrey Rosenthal, et al. Geometric ergodicity and hybrid markov chains. Electronic Communicutions Probability, 2:13-25, 1997.
[24] Joshua Snoke and Aleksandra Slavkovié. PMSE mechanism: differentially private synthetic data with maximal distributional similarity. In International Conference on Privacy in Statistical Dutabases, pages 138-159. Springer, 2018.
[25] Guanyang Wang. Exact convergence rate analysis of the independent cettrpooli-hassting algorithms. arXiv preprint S.Kiv:2008.02555. 2020.
[26] Yu-Xiang Wang. Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference Machine Learning, pages 2493-2502. PMLR, 2015.
[27] Hadley Wickham, g8plot2: Elegant Graphics for Data Analysis. Springer- Springer-Verlag New York. 2016.
12


Reviews:
[{"review_id": "w4TcgxKsHCK", "reviewer": "Reviewer_DMjk", "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).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nAugmenting 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).\n\nHowever, 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].\n\nBesides 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.\n\nMinor comments / typos:\n\n- Line 59: Reyni\n- 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}$\"?\n- Definition 2, B is not used anywhere after it is introduced.\n- Theorem 1, might make sense to include a description of the V-norm.\n-  Line 89: \"common common\"\n- Should there be a minus in front of the $\\log(n)$ in Eq. (2)?\n- Definition 4., missing the cite?\n- Page 4, missing closing parenthesis after \"i.e. $\\mathcal{Y}$ ...\"\n- 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.\n- Theorem 2, I think you should use X instead of x in $x \\in \\mathcal{X}^{n}$ to be more consistent with the notation.\n- 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.\n- Theorem 2, is the expected number of samples the same as expected time of return to the atom?\n- 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?\n- Page 6, last equality. Where does this come from?\n- Font in Figure 1 is way too small.\n- 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?\n- Figure 2, is the y-label \"Err\" correct? I think you mean utility.\n- reference 16, the title of the paper is truncated\n- reference 17, \"HItomi\"\n\nReferences:\n\n[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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "pxLX_-iNQ2D", "reviewer": "Reviewer_Dir6", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nThe 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. \n\nI 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "d4cao-7W954", "reviewer": "Reviewer_Jv9s", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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...\n\nWhat 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...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Irrelevant.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Refuse to time myself"}, "extra_text": {}}, {"review_id": "Tb4gmVmdUxf", "reviewer": "Reviewer_Dxmp", "summary": "This paper focuses an exact finite runtime sampling algorithm for the exponential mechanism by including an artificial atom in the target distribution.\n\nThe main contributions are:\n\n1. The paper proposes an exact finite-runtime algorithm (ConfAtomPerfect) for implementing the exponential mechanism with ε-DP guarantees using atomic regeneration.\n\n2. 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Comments:\n\n1. 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.\n\n2. There are too few references for similar/related methods.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2wwjBSw8Nc", "reviewer": "Reviewer_UUA7", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros:\n1. 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.\n3.  This work provides rigorous definitions and theorems to theoretically explain the effectiveness and correctness of proposed algorithms.\n4. This work carefully states the limitation of the proposed approach and provide potential improvement, such as generic utility for the exponential mechanism.\n\nCons:\n1. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative societal impact has seen.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)