论文标题
指数随机响应：在差异私有选择中提高实用程序
Exponential Randomized Response: Boosting Utility in Differentially Private Selection
论文作者
论文摘要
从有限的差异选择算法输出的算法设置了近似数据依赖数据质量函数的项目。解决此任务的最广泛采用的机制是开创性的指数机制和置入式纤维，这可以为指数机制提供多达两倍的效用。这项工作引入了一种新的私人机制，用于私人选择，并与上述机制进行了理论和经验比较。对于相当常见的情况，我们的机制可以在指数和倒翼机制上提供大于两个因素的实用性改进。由于该公用事业在利基方案中可能会恶化，因此我们建议我们的机制来忍受某些数据集的较低实用程序的分析师。
A differentially private selection algorithm outputs from a finite set the item that approximately maximizes a data-dependent quality function. The most widely adopted mechanisms tackling this task are the pioneering exponential mechanism and permute-and-flip, which can offer utility improvements of up to a factor of two over the exponential mechanism. This work introduces a new differentially private mechanism for private selection and conducts theoretical and empirical comparisons with the above mechanisms. For reasonably common scenarios, our mechanism can provide utility improvements of factors significantly larger than two over the exponential and permute-and-flip mechanisms. Because the utility can deteriorate in niche scenarios, we recommend our mechanism to analysts who can tolerate lower utility for some datasets.
