Locally Private k -Means Clustering

We design a new algorithm for the Euclidean k -means problem that operates in the local model of differential privacy. Unlike in the non-private literature, differentially private algorithms for the k -means incur both additive and multiplicative errors. Our algorithm significantly reduces the additive error while keeping the multiplicative error the same as in previous state-of-the-art results. Specifically, on a database of size n, our algorithm guarantees O (1) multiplicative error and ≈ n 1/2 + α additive error for an arbitrarily small constant a > 0. All previous algorithms in the local model had additive error ≈ n 2/3+ a. We show that the additive error we obtain is almost optimal in terms of its dependency in the database size n. Specifically, we give a simple lower bound showing that every locally-private algorithm for the k -means must have additive error at least ≈.

Authors

• Uri Stemmer

Keywords

No keywords are indexed for this paper.