2021/05/31 by Chaturvedi, Anamay, Jones, Matthew, Nguyen, Huy L.
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2105.15007
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) so that the sum of the ℓ22-distances between points of a given data set of size n and the set of k centers is minimized. Recent work on this problem in the locally private setting achieves constant multiplicative approximation with additive error O (n1/2 + a ⋅ k ⋅ max \√(d), √(k) \) and proves a lower bound of Ω(√(n)) on the additive error for any solution with a constant number of rounds. In this work we bridge the gap between the exponents of n in the upper and lower bounds on the additive error with two new algorithms. Given any α>0, our first algorithm achieves a multiplicative approximation guarantee which is at most a (1+α) factor greater than that of any non-private k-means clustering algorithm with k^O(1/α2) √(d' n) polylog n additive error. Given any c>√(2), our second algorithm achieves O(k^1 + O(1/(2c2-1)) √(d' n) poly log n) additive error with constant multiplicative approximation. Both algorithms go beyond the Ω(n1/2 + a) factor that occurs in the additive error for arbitrarily small parameters a in previous work, and the second algorithm in particular shows for the first time that it is possible to solve the locally private k-means problem in a constant number of rounds with constant factor multiplicative approximation and polynomial dependence on k in the additive error arbitrarily close to linear.