Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms
Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms
复制标题
DOI：
10.48550/arxiv.2204.01132
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Jeremy Seeman;M. Reimherr;Aleksandra B. Slavkovic
中科院分区：
文献类型：
--
作者：
Jeremy Seeman;M. Reimherr;Aleksandra B. Slavkovic
在差分隐私中实现指数机制通常需要从难以处理的分布中采样。当使用马尔可夫链蒙特卡罗（MCMC）等近似过程时，最终结果会在隐私和准确性方面产生成本。现有的工作已经渐近地检验了这些影响，但在实践中需要可实现的有限样本结果，以便用户可以提前指定隐私预算并实现具有精确隐私保证的采样器。本文利用遍历理论和完美模拟的工具，通过引入人工原子修饰的中间目标分布，设计了指数机制的精确有限运行时抽样算法。我们对该采样算法提出了一个额外的修改，以保持其$\epsilon$ -DP保证，并以一些实用程序为代价改进了运行时间。然后，我们在使用标准MCMC技术时可以显式计算$\delta$成本（如$(\epsilon, \delta)$ -DP）的场景中比较这些方法。就像在隐私和实用程序之间存在众所周知的权衡一样，我们证明了隐私保证和运行时之间也存在权衡。
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.