Differentially Private K-Means With Constant Multiplicative Error

Authors:
Uri Stemmer Ben-Gurion University
Haim Kaplan

Introduction:

The authors design new differentially private algorithms for the Euclidean k-means problem, both in the centralized model and in the local model of differential privacy.

Abstract:

We design new differentially private algorithms for the Euclidean k-means problem, both in the centralized model and in the local model of differential privacy. In both models, our algorithms achieve significantly improved error guarantees than the previous state-of-the-art. In addition, in the local model, our algorithm significantly reduces the number of interaction rounds.

You may want to know: