18/07/2021

Differentially Private Correlation Clustering

Mark Bun, Marek Elias, Janardhan Kulkarni

Keywords: Deep Learning, Embedding Approaches, Algorithms, Representation Learning; Algorithms, Structured Prediction; Applications, Computational Biology and Bioinform, Social Aspects of Machine Learning, Privacy, Anonymity, and Security

Abstract Paper Similar Papers

Abstract: 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 Ω(n).

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at ICML 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 13:08 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 17:30 
 0
 0
 0
 0
 19:02 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 7:24 
 0
 0
 0
 0
 14:45 
 0
 0
 0
 0
 5:04 
 0
 0
 0
 0
 27:29 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 13:44 
 0
 0
 0
 0
 11:50 
 0
 0
 0
 0
 2:45 
 0
 0
 0
 0
 15:16 
 0
 0
 0
 0
 12:45 
 0
 0
 0
 0
 13:17 
 0
 0
 0
 0
 5:13 
 0
 0
 0
 1
 12:41 
 0
 0
 0
 0
 15:37 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 5:45 
 0
 0
 0
 0
 12:21 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 2:58 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 15:54 
 0
 0
 0
 0
 12:55 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 16:49 
 0
 0
 0
 0
 3:13 
 0
 0
 0
 0
 5:22 
 0
 0
 0
 0
 12:13 
 0
 0
 0
 0
 19:03 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 13:29 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 14:14 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 14:11