These labels were automatically added by AI and may be inaccurate. For details, see About Literature Database.
Abstract
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.
