Differentially-Private Sublinear-Time Clustering

Authors: Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
Published: 2021-12-27

Source: https://arxiv.org/abs/2112.13751

PDF: https://arxiv.org/pdf/2112.13751

AIにより推定されたラベル

サンプリング手法 収束保証 プライバシーリスク管理

※ こちらのラベルはAIによって自動的に追加されました。そのため、正確でないことがあります。
詳細は文献データベースについてをご覧ください。

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.