论文标题
通过规范Lipschitz机制选择私人私人的TOP-K选择
Differentially Private Top-k Selection via Canonical Lipschitz Mechanism
论文作者
论文摘要
在差异隐私（DP）下，选择最高得分的最高评分项目是许多应用程序的基本任务。这项工作提出了三个新结果。首先，指数机制，置入式和报告 - 噪声 - 最大及其Oneshot变体被统一到Lipschitz机制中，Lipschitz机制是一种添加噪声机制，具有通过强制性的Lipschitz属性进行噪声分布，具有单个DP-PROFFECHING。其次，这种新的广义机制与规范损耗功能配对，以获得规范的Lipschitz机制，该机构可以直接从$ O（DK+D \ log D）$时间中直接选择$ D $项目的K-Subsets。规范损失函数通过为子集更改以成为最高$ K $的用户评估子集。第三，与通过顺序组成的一对一选择相比，这种无需组合选择的方法可改善$ω（\ log k）$因子的保证，而我们对合成和现实世界数据的实验表明了实用性改进。
Selecting the top-$k$ highest scoring items under differential privacy (DP) is a fundamental task with many applications. This work presents three new results. First, the exponential mechanism, permute-and-flip and report-noisy-max, as well as their oneshot variants, are unified into the Lipschitz mechanism, an additive noise mechanism with a single DP-proof via a mandated Lipschitz property for the noise distribution. Second, this new generalized mechanism is paired with a canonical loss function to obtain the canonical Lipschitz mechanism, which can directly select k-subsets out of $d$ items in $O(dk+d \log d)$ time. The canonical loss function assesses subsets by how many users must change for the subset to become top-$k$. Third, this composition-free approach to subset selection improves utility guarantees by an $Ω(\log k)$ factor compared to one-by-one selection via sequential composition, and our experiments on synthetic and real-world data indicate substantial utility improvements.
