We study the problem of differentially private clustering under
input-stability assumptions. Despite the ever-growing volume of works on
differential privacy in general and differentially private clustering in
particular, only three works (Nissim et al. 2007, Wang et al. 2015, Huang et
al. 2018) looked at the problem of privately clustering "nice" k-means
instances, all three relying on the sample-and-aggregate framework and all
three measuring utility in terms of Wasserstein distance between the true
cluster centers and the centers returned by the private algorithm. In this work
we improve upon this line of works on multiple axes. We present a far simpler
algorithm for clustering stable inputs (not relying on the sample-and-aggregate
framework), and analyze its utility in both the Wasserstein distance and the
k-means cost. Moreover, our algorithm has straight-forward analogues for "nice"
k-median instances and for the local-model of differential privacy.

本文研究了在输入稳定性假设下的差分隐私聚类问题，提出了一种简单的算法，分析了其在 Wasserstein 距离和 k-means 代价等方面的效用，可直接应用于 “好” 的 k - 中位数实例和本地模型的差分隐私。