We propose and analyze a general-purpose dataset-distance-based utility function family, Duff, for differential privacy's exponential mechanism. Given a particular dataset and a statistic (e.g., median, mode), this function family assigns utility to a possible output o based on the number of individuals whose data would have to be added to or removed from the dataset in order for the statistic to take on value o. We show that the exponential mechanism based on Duff often offers provably higher fidelity to the statistic's true value compared to existing differential privacy mechanisms based on smooth sensitivity. In particular, Duff is an affirmative answer to the open question of whether it is possible to have a noise distribution whose variance is proportional to smooth sensitivity and whose tails decay at a faster-than-polynomial rate. We conclude our paper with an empirical evaluation of the practical advantages of Duff for the task of computing medians.
翻译:我们提议并分析一个通用数据集-远程通用功能家庭,Duff, 用于不同隐私指数机制。考虑到一个特定的数据集和统计数据(例如中位数、模式),这个函数家庭将实用性分配给一个可能的输出,其依据是数据组中的数据必须添加或删除的人数,以便统计得出数值。我们表明,基于Duff的指数机制往往比基于光滑敏感度的现有差异隐私机制对统计数据的真正价值具有更准确性。特别是,Duff是对一个开放问题的肯定答案,即是否有可能出现噪音分布,其差异与光滑敏感度成正比,其尾部以比极速速度衰减。我们的文件最后对Duff在计算中位任务方面的实际优势进行了经验评估。