02/02/2021

Differentially Private k-Means via Exponential Mechanism and Max Cover

Huy L. Nguyen, Anamay Chaturvedi, Eric Z Xu

Keywords:

Abstract Paper Similar Papers

Abstract: We introduce a new (ϵₚ, δₚ)-differentially private algorithm for the k-means clustering problem. Given a dataset in Euclidean space, the k-means clustering problem requires one to find k points in that space such that the sum of squares of Euclidean distances between each data point and its closest respective point among the k returned is minimised. Although there exist privacy-preserving methods with good theoretical guarantees to solve this problem, in practice it is seen that it is the additive error which dictates the practical performance of these methods. By reducing the problem to a sequence of instances of maximum coverage on a grid, we are able to derive a new method that achieves lower additive error than previous works. For input datasets with cardinality n and diameter Δ, our algorithm has an O(Δ² (k log² n log(1/δₚ)/ϵₚ + k √(d log(1/δₚ))/ϵₚ)) additive error whilst maintaining constant multiplicative error. We conclude with some experiments and find an improvement over previously implemented work for this problem.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948927
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 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
 14:58 
 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 19:23 
 0
 0
 0
 0
 7:26 
 0
 0
 0
 0
 2:52 
 0
 0
 0
 0
 10:44 
 0
 0
 0
 0
 2:56 
 0
 0
 0
 0
 4:48 
 0
 0
 0
 0
 11:50 
 0
 0
 0
 0
 15:06 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 13:24 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 19:52 
 0
 0
 0
 0
 10:45 
 0
 0
 0
 0
 14:21 
 0
 0
 0
 0
 24:28 
 0
 0
 0
 0
 17:30 
 0
 0
 0
 0
 9:08 
 0
 0
 1
 1
 14:52 
 0
 0
 0
 0
 16:40 
 0
 0
 0
 0
 22:42 
 0
 0
 0
 0
 5:13 
 0
 0
 0
 0
 3:14 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 25:07 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 24:22 
 0
 0
 0
 0
 11:10 
 0
 0
 0
 0
 16:38 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 18:17 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 28:16 
 0
 0
 0
 0
 17:58 
 0
 0
 0
 0
 12:13 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 16:59 
 0
 0
 0
 0
 13:48