Locally Private k-Means Clustering
share
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+a additive error for an arbitrarily small constant a, whereas all previous algorithms in the local model on had additive error ≈ n^2/3+a. We give a simple lower bound showing that additive error of ≈√(n) is necessary for k-means algorithms in the local model (at least for algorithms with a constant number of interaction rounds, which is the setting we consider in this paper).
READ FULL TEXT