Timezone: »

Differentially-Private Clustering of Easy Instances
Edith Cohen · Haim Kaplan · Yishay Mansour · Uri Stemmer · Eliad Tsfadia

Thu Jul 22 07:30 AM -- 07:35 AM (PDT) @

Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify k cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentrially private clustering algorithms when the the data is "easy," e.g., when there exists a significant separation between the clusters.

For the easy instances we consider, we have a simple implementation based on utilizing non-private clustering algorithms, and combining them privately. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and k-means. We complement our theoretical algorithms with experiments of simulated data.

Author Information

Edith Cohen (Google Research and Tel Aviv University)
Haim Kaplan (TAU, GOOGLE)
Yishay Mansour (Google and Tel Aviv University)
Uri Stemmer (Ben-Gurion University)
Eliad Tsfadia (Tel Aviv University and Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors