Differentially-Private Sublinear-Time Clustering
This work addresses the need for efficient and private clustering algorithms in machine learning, but it is incremental as it builds directly on prior methods.
The paper tackles the problem of sublinear-time differentially-private clustering by combining existing sublinear-time clustering algorithms with recent private clustering results to develop new algorithms for k-means and k-median via subsampling, and explores privacy benefits for group privacy.
Clustering is an essential primitive in unsupervised machine learning. We bring forth the problem of sublinear-time differentially-private clustering as a natural and well-motivated direction of research. We combine the $k$-means and $k$-median sublinear-time results of Mishra et al. (SODA, 2001) and of Czumaj and Sohler (Rand. Struct. and Algorithms, 2007) with recent results on private clustering of Balcan et al. (ICML 2017), Gupta et al. (SODA, 2010) and Ghazi et al. (NeurIPS, 2020) to obtain sublinear-time private $k$-means and $k$-median algorithms via subsampling. We also investigate the privacy benefits of subsampling for group privacy.