Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity
Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity
复制标题
DOI：
--
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Jinshuo Dong;D. Durfee;Ryan M. Rogers
中科院分区：
文献类型：
--
作者：
Jinshuo Dong;D. Durfee;Ryan M. Rogers
组合是差分隐私（DP）最重要的属性之一，因为它允许算法设计者从DP原语构建复杂的隐私算法。我们考虑指数机制（DP中基本机制之一）的总体隐私损失的精确组成界限。我们给出了明确的配方的最佳隐私损失的自适应和非自适应设置。对于非自适应设置中，每个机制具有相同的隐私参数，我们给出了一个有效的计算公式的最佳隐私损失。此外，我们表明，有一个差异的隐私损失时，指数机制的选择自适应与非自适应。据我们所知，这是以前未知的任何DP机制与固定的隐私参数是否存在这样的差距，我们证明了差距广泛使用的一类机制在自然环境中。然后，我们改进了最好的先前已知的自适应组合指数机制的上限与有效的可计算的配方，并显示改进。
Composition is one of the most important properties of differential privacy (DP), as it allows algorithm designers to build complex private algorithms from DP primitives. We consider precise composition bounds of the overall privacy loss for exponential mechanisms, one of the fundamental classes of mechanisms in DP. We give explicit formulations of the optimal privacy loss for both the adaptive and non-adaptive settings. For the non-adaptive setting in which each mechanism has the same privacy parameter, we give an efficiently computable formulation of the optimal privacy loss. Furthermore, we show that there is a difference in the privacy loss when the exponential mechanism is chosen adaptively versus non-adaptively. To our knowledge, it was previously unknown whether such a gap existed for any DP mechanisms with fixed privacy parameters, and we demonstrate the gap for a widely used class of mechanism in a natural setting. We then improve upon the best previously known upper bounds for adaptive composition of exponential mechanisms with efficiently computable formulations and show the improvement.