Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error
Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error
复制标题
DOI：
10.1609/aaai.v36i6.20565
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Anamay Chaturvedi;Matthew D. Jones;Huy L. Nguyen
中科院分区：
文献类型：
--
作者：
Anamay Chaturvedi;Matthew D. Jones;Huy L. Nguyen
给定d维欧氏空间中一个大小为n的数据集，k-均值问题要求一组k个点（称为中心），使得数据点与中心集之间的l_2^2-距离之和最小化。以前的工作在这个问题上的局部差分隐私设置显示了如何实现乘法逼近因子任意接近最优，但遭受高的加性误差。加性误差也被认为是在中央和本地设置中的差分私有k均值聚类算法的实现中的一个问题。在这项工作中，我们引入了一个新的局部私有k均值聚类算法，实现了接近最佳的加性误差，同时保持恒定的乘法近似因子和轮复杂度。具体地说，给定任何c> 102，我们的算法实现了O（k^（1 + O（1/（2c^2-1）））<$（d' n）log d' poly log n）的加法误差和O（c^2）的乘法逼近因子。
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.