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.
翻译:从一个限定的组合中产生一种差别化的私人选择算法输出,它大约使数据依赖性质量功能最大化。处理这项任务的最广泛采用的机制是开创性的指数机制以及极速和倾斜机制,它们可以为指数机制提供多达两个系数的效用改进。这项工作为私人选择引入一个新的差别化私营机制,并与上述机制进行理论和实验性比较。对于合理的常见假设,我们的机制可以提供比指数和倾斜和倾斜机制大得多的两种因素的效用改进。由于这种效用在特定情况下会恶化,我们建议分析师使用我们的机制,因为分析师能够容忍某些数据集的较低效用。