Differentially-Private Sublinear-Time Clustering
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 10 of its 37 references that are in the map. First posted on arXiv 27 Dec 2021.
Builds on
10 of 37 references.
References · 10
- 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
- 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 237
- 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
- 2017Prochlo: Strong Privacy for Analytics in the Crowdcited by 51
- 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
- 2015Differentially Private k-Means Clusteringcited by 27
- 2018Differentially Private k-Means with Constant Multiplicative Errorcited by 22
- 2017Clustering Algorithms for the Centralized and Local Modelscited by 18
- 2019Locally Private k-Means Clusteringcited by 15
- 2020Guidelines for Implementing and Auditing Differentially Private Systemscited by 10
Built on by
Citing papers per year: 2022: 1; 2023: 1.
2 papers.