Differentially-Private Clustering of Easy Instances
  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 differentially private clustering
algorithms that provide utility when the data is "easy," e.g., when there
exists a significant separation between the clusters.
  We propose a framework that allows us to apply non-private clustering
algorithms to the easy instances and privately combine the results. We are able
to get improved sample complexity bounds in some cases of Gaussian mixtures and
$k$-means. We complement our theoretical analysis with an empirical evaluation
on synthetic data.
