Optimal differentially private algorithms for k-means clustering

We consider privacy-preserving k-means clustering. For the objective of minimizing the Wasserstein distance between the output and the optimal solution, we show that there is a polynomial-time (,)-differentially private algorithm which, for any sufficiently large² well-separated datasets, outputs k centers that are within Wasserstein distance O(²) from the optimal. This result improves the previous bounds by removing the dependence on, number of centers k, and dimension d. Further, we prove a matching lower bound that no (,)-differentially private algorithm can guarantee Wasserstein distance less than Ω(²) and, thus, our positive result is optimal up to a constant factor. For minimizing the kmeans objective when the dimension d is bounded, we propose a polynomial-time private local search algorithm that outputs an n-additive approximation when the size of the dataset is at least Õk³/² · d ·⁻¹ · poly(⁻¹).