Scalable Differentially Private Clustering via Hierarchically Separated Trees
We study the private $k$-median and $k$-means clustering problem in $d$
dimensional Euclidean space. By leveraging tree embeddings, we give an
efficient and easy to implement algorithm, that is empirically competitive with
state of the art non private methods. We prove that our method computes a
solution with cost at most $O(d^{3/2}\log n)\cdot OPT + O(k d^2 \log^2 n /
\epsilon^2)$, where $\epsilon$ is the privacy guarantee. (The dimension term,
$d$, can be replaced with $O(\log k)$ using standard dimension reduction
techniques.) Although the worst-case guarantee is worse than that of state of
the art private clustering methods, the algorithm we propose is practical, runs
in near-linear, $\tilde{O}(nkd)$, time and scales to tens of millions of
points. We also show that our method is amenable to parallelization in
large-scale distributed computing environments. In particular we show that our
private algorithms can be implemented in logarithmic number of MPC rounds in
the sublinear memory regime. Finally, we complement our theoretical analysis
with an empirical evaluation demonstrating the algorithm's efficiency and
accuracy in comparison to other privacy clustering baselines.