Differentially-Private Sublinear-Time Clustering
  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.
