Differentially Private Clustering: Tight Approximation Ratios

Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

Authors

Badih Ghazi, Ravi Kumar, Pasin Manurangsi

Abstract

<p>We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors. </p> <p>Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.</p>