Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error

No. 6: AAAI-22 Technical Tracks 6

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Machine Learning I

Given a data set of size n in d'-dimensional Euclidean space, the k-means problem asks for a set of k points (called centers) such that the sum of the l_2^2-distances between the data points and the set of centers is minimized. Previous work on this problem in the local differential privacy setting shows how to achieve multiplicative approximation factors arbitrarily close to optimal, but suffers high additive error. The additive error has also been seen to be an issue in implementations of differentially private k-means clustering algorithms in both the central and local settings. In this work, we introduce a new locally private k-means clustering algorithm that achieves near-optimal additive error whilst retaining constant multiplicative approximation factors and round complexity. Concretely, given any c>√2, our algorithm achieves O(k^(1 + O(1/(2c^2-1))) √(d' n) log d' poly log n) additive error with an O(c^2) multiplicative approximation factor.

10.1609/aaai.v36i6.20565