TY - JOUR
AU - Chaturvedi, Anamay
AU - Jones, Matthew
AU - Nguyễn, Huy Lê
PY - 2022/06/28
Y2 - 2024/09/12
TI - Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 36
IS - 6
SE - AAAI Technical Track on Machine Learning I
DO - 10.1609/aaai.v36i6.20565
UR - https://ojs.aaai.org/index.php/AAAI/article/view/20565
SP - 6167-6174
AB - 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.
ER -