Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms
Year: 2021

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 -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 ( , δ)-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.

heading: 1 Introduction

heading: 1.1 Problem setup
text: The exponential mechanism [17] is one of the workhorses of -differential privacy ( -DP). Many common DP mechanisms, such as 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 [2]. However, the output of the exponential mechanism often has an intractable distribution, making it difficult to sample from in practice. This necessitates using a sampling algorithm such as Markov chain Monte Carlo (MCMC) to computationally generate 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.
In practice, analyzing the privacy cost incurred due to sampling is a 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 finite-sample incurred costs. However, for uniformly ergodic chains that admit atoms in their state
35th Conference on Neural Information Processing Systems (NeurIPS 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.

heading: 1.2 Contributions
text: Let fX(y) be the output density of the exponential mechanism with confidential data X and output space y ∈ Y (we will fully define this notation in 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 k ∈ [0, 1]:
f̃X(y) = (1− k)fX(y) + kgX(y).
In particular, we introduce two different methods which we will give names and briefly describe:
• ConfAtomPerfect gX(y) is a point mass at the confidential data output, and the target distribution is f̃X(y) conditioned on NOT releasing the confidential data, yielding an exact draw from fX .
• RandomAtomPerfect gX(y) is the mass function for an implementation of the discrete exponential mechanism over a 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 ( , δ)-DP guarantees.
2. We propose an exact finite-runtime algorithm (ConfAtomPerfect) for implementing the exponential mechanism with -DP guarantees using atomic regeneration.
3. We derive two modifications of the previous algorithm (i.e., RandomAtomPerfect and ConfAtomAndRuntimePerfect) that satisfy -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 between, privacy, utility, and runtime.

heading: 1.3 Related literature
text: Results from MCMC theory have addressed privacy loss due to approximation by analyzing convergence rates of total variational distance [18] 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 it lacks the privacy-preserving compositional properties of Rényi-DP, allowing for the derivation of convergence results with better asymptotic dependence on the dimension of the output space. Our work differs in a 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 function. For our perfect sampler, we only require uniform ergodicity of the original chain, which is often achieved by virtue of bounding the database space. Second, we consider simpler classes of base MCMC algorithms that may be sufficient for a 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 to use these algorithms and calculate their provable guarantees.

heading: 2 Methods

heading: 2.1 Notation
text: We recall some definitions and theorems here:
Definition 1 (Differential Privacy [7]). LetM , {µX | X ∈ Xn} be a collection of probability measures over a common measurable space (Y,F) indexed by elements of Xn. The mechanismM satisfies ( , δ)-DP if, for all B ∈ F and X,X ′ ∈ Xn differing on one entry:
µX(B) ≤ e µX′(B) + δ.
Definition 2 (Exponential Mechanism [17]). Let LX : Xn × Y 7→ [0,∞] be a measurable loss function for each X ∈ Xn. Suppose, for all adjacent X,X ′ ∈ Xn and y ∈ Y:
|LX(y)− LX′(y)| ≤ ∆L <∞.
The exponential mechanism is the ( , 0)-DP mechanism defined by the collection of measures each with density: fX(y) ∝ exp ( − LX(y)
2∆L
) ,
with respect to a common base measure ν(y) over (Y,F).
Frequently, ν is taken to be the Lebesgue measure over a subset of Rd. Throughout the paper, let {µm,X}∞m=1 be a sequence of probability measures such that µm,X converges in distribution to µX for all X ∈ Xn. We assume the chain is defined by the transition kernel ΠX : Y × F 7→ [0, 1] and the starting value y0 ∈ Y . Throughout the paper, we use the concept of minorization: Definition 3 (Minorization Condition). Suppose there exists a function s : Y 7→ [0, 1] and probability measure ν on (Y,F) such that for all A ∈ F and y ∈ Y:
ΠX(y,A) ≥ s(y)ν(A).
We call these the minorization function and measure, respectively. Define the associated remainder kernel Rν,s : Y × F 7→ [0, 1] such that:
ΠX(y,A) = s(y)ν(A) + (1− s(y))Rν,s(y,A).
Our results rely on the existence of minorization functions and measures for our output distribution µX . This assumption will give us uniform ergodicity properties later on. Note that a limitation of our approach is that we cannot apply these methods to exponential mechanisms with unbounded output spaces such as Rk, but it does work for compact sets of Rk. In practice, this limitation is not a 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 a δα penalty as a function of the upper bound on the total variation distance α:
Theorem 1 ([18]). A mechanismMm , {µm,X | x ∈ X} approximating the exponential mechanism, M, at time m ≥ τ(α) is ( , δα)-DP where δα , α(1 + e ) if
τ(α) , sup X∈Xn inf{t ≥ 0 | ‖µt,X − µX‖TV ≤ α}.
Note that the upper bound on the δ cost incurred above is specific to the sequence’s properties (for example, transition probabilities and starting locations for MCMC). However, the upper bound is not specific to the confidential data X . Such generality is necessary to preserve ( , δ)-DP, as 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" to ensure privacy in the worst-case scenario.
One common heuristic here is to 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 “fastmixing" regime for these chains is a geometric rate, where the total variation distance is O(rm) for some r ∈ (0, 1): Definition 4 (V -geometric ergodicity [1]). For a Markov chain where µm,X → µX in distribution as m→∞, we say the chain is V -geometrically ergodic if there exists constants C ∈ R+, r ∈ (0, 1), and a function V : Y 7→ [1,∞) such that for all m ∈ N and starting points y0 ∈ Y:
‖µm,X − µX‖TV ≤ ‖µm,X − µX‖V ≤ CV (y0)r −m. (1)
When V is a constant function, we say the chain is uniformly ergodic.
Many common algorithms, such as Metropolis-Hastings [1] and common variants such as Hybrid Monte Carlo [23] and Hamiltonian Monte Carlo [16], are geometrically ergodic under mild regularity conditions. For these algorithms, it immediately follows that for any specific realization X ∈ Xn, if we choose m = Ω(log(n)):
‖µm,X − µX‖TV ≤ CV (y0)r log(n) =⇒ δα = O(1/n). (2)
Therefore, up to a constant, for a fast mixing sampling algorithm we require at least order log(n) samples to achieve a negligible δ for an empirical privacy guarantee. However, there are two complications to formalizing this idea. First, the constant of proportionality for the rate depends on , r, V , and C. Second, the mixing time depends on X , and the privacy guarantee depends on fast mixing for all possible X ∈ Xn.

heading: 2.2 Properties of Markov chains whose state spaces admit atoms
text: The complications above can be alleviated when the target distribution admits an atom, specifically a proper accessible atom with respect to the transition kernel ΠX : Definition 5 (Proper Accessible Atom). A set γ ∈ F is a proper accessible atom if:
1. (Regeneration measure) There exists a measure µregen on (Y,F) such that: ΠX(y,A) = µregen(A) ∀y ∈ γ,A ∈ F .
2. (Accessibility criteria) ΠX(y, γ) > 0 ∀y ∈ Y.
3. (Recurrence criteria) the chain returns infinitely often to γ with probability 1.
When the state space admits an atom, the constants in Equation 1 have closed form expressions (see [1, Theorem 4.1] for an example). Furthermore, Markov chains that admit atoms have a special split chain representation [20], where the state space is extended with a binary indicator indicating presence in the atom (i.e., Y × {0, 1}). For this split chain, let τ be the time it takes for the split Markov chain to return to said proper accessible atom after leaving it. Hobert et al. [13] show that the stationary distribution admits an infinite mixture form:
µX(A) = ∞∑ m=1 P(τ ≥ m) E[τ ] P(Ym ∈ A | τ ≥ m).
If one can sample from the mixture components as well as the conditional distributions feasibly (i.e., in finite expected time), then one can sample from µX . Following [15], the authors focus on the singleton case when γ = {a} for some a ∈ Y . Define:
p(y) , ΠX(y, {a}). If there exists β > 0 such that infy∈Y p(y) > β > 0, then wen can use Algorithm 1 to produce an exact sample from the target distribution.
Because many target distributions do not admit the atom required, Brockwell [6] proposes a way to introduce an artificial atom into a new stationary density f̃X . In our setting, we propose introducing an atom at the confidential response mixed with the -DP stationary distribution with proportions k and 1− k, respectively, for some k ∈ (0, 1):
f̃X(y) , (1− k)fX(y) + k1{y=a}, with respect to a new base measure:
ν̃ , (1− k)ν + kξa, where ν is the original base measure and ξa is the Dirac delta function representing a point mass at the confidential data. In particular, if the Metropolis-Hastings kernel has symmetric proposal density qX(y, y
′), then one can construct a new Metropolis-Hastings transition kernel Π̃ with symmetric proposal density:
q̃(y, y′) = 1
2
[ qX(y, y ′) + 1{y′=a} ] .
Algorithm 1: Exact implementation for sampling from a singleton atom mixture [15] Result: Y ∼ µ̃X Input: Transition kernel ΠX , singleton atom a ∈ Y , minorization β > 0 Sample M ∼ Geometric(β), set Y1 = a ; for m = 2 to M do
Using the Bernoulli factory algorithm [14], sample:
Zm ∼ Bernoulli
( 1− Π̃X(Ym−1, {a})
1− β ) if Zm = 1 then
Sample Ym ∼ Rξa,Π̃X(·,{a})(Ym−1, ·) using rejection: 1. Propose Y ∗m ∼ Π̃X(Ym−1, ·). 2. Accept if Y ∗m 6= a, else go back to 1.
else Ym = a end Release YM .
end

heading: 2.3 Extensions to private sampling
text: 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 is enforced so that the exponential mechanism’s loss function has bounded sensitivity. Second, we can choose to add an artificial atom at the confidential data, namely any point a ∈ Y such that Lx(a) = 0 without loss of generality (note that a need not be unique). This yields our first main result in Theorem 2, and Algorithm 2. Theorem 2 (ConfAtomPerfect). Suppose that Y is a compact subset of Rd and let LX be a loss function based on confidential data x ∈ Xn where LX(a) = 0 for some a ∈ Y . Suppose µX({a}) = 0. Let Q be a Metropolis-Hastings transition kernel with symmetric proposals, and let Q̃ and q̃ be as defined above. Then:
1. There exists a constant β > 0 such that:
inf y∈Y
Π̃X(y, {a}) > β.
2. There exists an algorithm (implemented by Algorithm 1) to sample from density fX that satisfies -DP with expected number of total proposed samples Nprop:
E[Nprop] ≤ 48
k2(1− k)2 infy∈Y pAccept(y) ,
where:
pAccept(y) , ∫ Y qX(y, y ′) min { 1, fX(y ′) fX(y) } dν(y′).
Proof. (Sketch; see complete proof in appendix) By construction, the Metropolis-Hastings transition kernel is maximized at a for the modified chain. Taking β , k2 yields the first result.
For the second result, the runtime is split into four components: NOuter , Number of outer loops in Algorithm 1, NInner , Number of rejection proposals to sample from Y ∗m ∼ Ra,p(Ym−1, ·), NBern , Number of Bernoulli factory samples to select Zm in Algorithm 1, NNonatommic , Number of samples from f̃X required to sample from fX .
In the complete proof, we show: E[NOuter] = 2k , E[NInner] ≤ ((1− k) infy∈Y pAccept(y))−1 , E[NBern] ≤ 24k , E[NNonatommic] = (1− k)−1.
This yields the desired bound.
Algorithm 2: ConfAtomPerfect: -DP exact sample from exponential mechanism Result: Y ∼ fX Input: Sample space Y and loss function Lx satisfying the conditions of Theorem 2 while TRUE do
Sample Ỹ ∼ f̃x using Algorithm 1. if Ỹ 6= a then Release Ỹ .
end end
We make a couple remarks about this result. First, we note that the bound in the runtime can depend on the confidential data and does not require us to take the infimum over all possible data sets. While this is a nice property, it also assumes that the runtime of the algorithm is not a possible source of side channel information (more on 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 on the proposal distribution. However, this result can easily be extended to arbitrary proposals in cases where the minorizing constant can still be calculated. Third, note that we do not include the case where µX({a}) > 0, as this corresponds to an exact implementation of the algorithm derived in [15]. Finally, we anticipate the expected runtime bound above is very loose; the bounds NBern and NInner are generic, and can be much lower for specific implementations. Moreover, Nprop is loosely bounded above by the product of the terms in the proof sketch, but in practice not every branch of Algorithm 1 is traversed each time.
Algorithm 2 relies on multiple passes through Algorithm 1 in order to sample from the original target distribution; however, upon failure to do so, we could alternatively sample from a discrete approximation of the exponential mechanism target distribution. This yields a less computationally expensive method, avoiding the additional (1− k)−1 factor in implementing the mechanism with pure -DP, at the expense of some loss in utility due to the discrete approximation.
Corollary 1 (RandomAtomPerfect). In the same setup as Theorem 2, let {y(l)}`l=1 ⊂ Y and let gX be the mass density of the exponential mechanism implemented on {y(l)}`l=1. Then there exists a sampling algorithm (implemented by Algorithm 3) with target density:
f̃X(y) = (1− k)fX(y) + kgX(y), (3)
with respect to the mixture measure:
η̃ = (1− k)ν + k ` ∑̀ l=1 ξl,
with expected number of total proposed samples Nprop:
E[Nprop] ≤ 48
k2(1− k) infy∈Y pAccept(y) ,
And utility:
µX(Sε) ≤ 1− k ν(Sε/2) exp
( − ε
4∆L
) + k exp ( −
2∆L
( ε− 2∆L log(`) )) ,
Where Sε , {y ∈ Y | LX(y) ≥ ε}.
Algorithm 3: RandomAtomPerfect: -DP sample from mixture of discrete and continuous exponential mechanisms
Result: Y ∼ f̃X as in Equation 3 Input: Sample space Y and loss function Lx satisfying the conditions of Corollary 1 Sample Ỹ using Algorithm 1. if Ỹ 6= a then
Release Ỹ . else
Release Y ∼ gX end
One potential issue with both algorithms 2 and 3 is that NInner 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 to release a result whose runtime is independent of the data (at a cost due to runtime). This is implemented in Corollary 2. Corollary 2 (ConfAtomAndRuntimePerfect). In the same setting as Theorem 2, there exists a modification of Algorithm 2 where:
1. The total number of proposed samples (either real or partially artificial) Nprop is independent of the data (i.e., satisfies 0-DP).
2. The expected runtime of the algorithm is upper bounded by:
E[Nprop] ≤ 48
k2(1− k)2η ,
Where: η , 1
2 inf x∈Xn inf y∈Y pAccept(y)

heading: 3 Examples
text: 3.1 d-dimensional mean with L1 loss: comparing -DP and ( , δ)-DP guarantees As a first example, let Y = [0, 1]d, LX(y) , ∥∥y −X∥∥
1 , and ν be a uniform measure over Y . This
is 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 costs using MCMC versus using Algorithm 2. Derivation of all example results are in the appendix.
We consider two different proposals for MCMC. For the first algorithm, we derive a MetropolisHastings Markov chain constructed with proposal independently drawn uniformly over [0, 1]d. The slowest-mixing chain is easily identifiable using results from [1]:
‖µX,m − µX‖TV ≤ (1− βMCMC,unif) m, (4)
where,
βMCMC,Unif ,
( 2d
n (1− e− n/2d)
)d .
Derivation of this result is in the appendix. This allows us to immediately construct ( , δ)-DP implementations of the exponential mechanism. Note that, using the main result in [25], Equation 4 is constant-sharp and cannot be improved.
Similarly, we can use Laplace proposals of the form:
qX(y, y ′) ∝ exp ( −α ‖y − y′‖L1 ) ,
for which we have a new rate of convergence given analogously by:
βMCMC,Lap , (2α) d exp ( − ( αd+ n
2 ))( 1 α (1− e−α) )d .
The runtime for Algorithm 2 depends on the confidential data. To demonstrate this, we simulate X from three different Beta distributions: one uniform (X ∼ Beta(1, 1)), one with unimodal concentration (X ∼ Beta(10, 10)), and one with concentration at the boundary (X ∼ Beta(.1, .1)) and compare the distribution of Nprop across the cases in Figure 2. All simulations are implemented in R [21] and figures were produced using ggplot2 [27] under GNU GPL v3.
The runtime results presented in figures 1 and 2 illustrate the phenomena in the discussion for Theorem 2. For the MCMC implementations in Figure 1, even though we expect the Laplace proposals to mix faster in general, the worst case mixing time is 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 the perfect sampler in Figure 2, the runtime for the perfect sampler decreases when the data is more likely to be concentrated at the center of the output space (as in Beta(10, 10)) as opposed to the boundary of the space (as in Beta(.1, .1)).

heading: 3.2 Ridge regression K-norm gradient mechanism: comparing confidential and random atoms
text: Next, we consider Ridge regression [11]. We will use the K-norm gradient mechanism following [22], a variant of the original exponential mechanism whose noise is asymptotically negligible as n→∞. In the interest of keeping consistent notation, let:
Y , {y ∈ Rp | ‖y‖1 ≤ B}.
Let X ∈ [−1, 1]n×p and Z ∈ [−1, 1]n. Define the original loss function `X(y):
`X(y) = 1
2 ‖Z −Xy‖22 +
λ 2 ‖y‖22 .
For any two X,X ′ that differ on one element and all y ∈ Y:
‖∇`X(y)−∇`X′(y)‖1 ≤ 2(1 +B) sup x∈[0,1]p ‖x‖1 ≤ 2(1 +B)p
This yields a final mechanism given by: fX(y) ∝ exp ( −
4(1 +B)p
∥∥XT (Xy − Z) + λy∥∥ 1 ) 1{‖y‖1≤B}. (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 not depend on the integration constant in Equation 5 when the proposals qX are symmetric, since:
pAccept(y) = ∫ ‖y‖1≤B qX(y, y ′) min 1, exp ( − 4(1+B)p ∥∥XT (Xy′ − Z) + λy′∥∥ 1 ) exp ( − 4(1+B)p ‖XT (Xy − Z) + λy‖1 )  dν(y′).
This property is not shared by the MCMC estimator, demonstrating an advantage of this procedure.
Our main goal is to compare the utilities of Algorithms 2 and 3, meaning we need to quantify the utility cost of discretizing the output space with some probability k. To analyze this, we simulate data from a Ridge regression model with p = 5 and randomly sample ` points from the L1 ball of radius B = 1 on which to implement the discrete exponential mechanism. By varying ` and and repeating the experiment Nexp = 1000 times, we calculate:
Err( , `, ε) , Q.05{P (LX(y)(nexp, ,`) ≥ ε)}.
where Q.05 is the 5% quantile across experiment replications. This captures with approximately 95% confidence a kind of “worst case" utility bounds by choosing a particular discretization at random for our Ridge regression. The results of the experiment are in Figure 3 with full simulation details in the appendix. Since the discrete exponential mechanism utility is a 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 we could choose ` large enough that the utility of the discrete mechanism is close to that of the original exponential mechanism with high probability. However, further investigation is needed to understand these effects in higher dimensions or for more complicated loss functions.

heading: 4 Discussion
text: 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 a δ 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.

heading: 4.1 Limitations
text: As with any real-valued private computation, we must be careful about the complications of floatingpoint arithmetic and other side channel vulnerabilities [19]. Just because a machine cannot report a δ cost below its floating point precision does not mean the system is invulnerable. In particular, runtime issues pose a 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-interactive data analyses, in which runtime information leakage is a 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-behaved distributions that allow us to 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 to estimate or 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 as noted in [12]. Still, many common problems fall into the regime where d n and Xn is not discrete; this is where we believe our work is most applicable. Finally, we 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 [15]. However, the minorization constant suffers from curse of dimensionality effects, meaning the runtime will often suffer for high-dimensional results. Feasible and efficient algorithms for perfect sampling in high-dimensional settings remains an open challenge in mathematics.

heading: 4.2 Future research
text: First, understanding the utility trade-off between Algorithms 2 and 3 requires a deeper understanding of generic utility for the exponential mechanism. Although there has been some of work on the 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 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 1 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 a quantifiable guarantee.

heading: 5 Acknowledgements
text: This work is supported by NSF SES-1853209. Thanks to Jordan Awan and Alexei Novikov for helpful discussions about this topic. We declare no conflicts of interest.

Review summaries:
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).

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.

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.