Differentially Private Correlation Clustering
Differentially Private Correlation Clustering
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Mark Bun;Marek Eliáš;Janardhan Kulkarni
中科院分区：
文献类型：
--
作者：
Mark Bun;Marek Eliáš;Janardhan Kulkarni
相关聚类是无监督机器学习中广泛使用的技术。出于个人隐私是一个问题的应用程序，我们开始研究的差异私人相关聚类。我们提出了一种算法，实现次二次加性误差相比，最佳成本。相比之下，现有的非私有算法的直接适应都导致一个微不足道的二次误差。最后，我们给出了一个下界，表明任何纯差分相关聚类算法需要$\Omega（n）$的加性误差。
Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differentially private correlation clustering. We propose an algorithm that achieves subquadratic additive error compared to the optimal cost. In contrast, straightforward adaptations of existing non-private algorithms all lead to a trivial quadratic error. Finally, we give a lower bound showing that any pure differentially private algorithm for correlation clustering requires additive error of $\Omega(n)$.