mlsanityData to 7 Oct 2026

Differentially-Private Clustering of Easy Instances

arXiv 2112.14445 ↗First posted 29 Dec 2021cs.LG cs.CR cs.DScited by 17

Not on the map. Why?

Abstract (arXiv)

Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify k cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentially private clustering algorithms that provide utility when the data is "easy," e.g., when there exists a significant separation between the clusters. We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and k-means. We complement our theoretical analysis with an empirical evaluation on synthetic data.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 25 of its 60 references that are in the map. First posted on arXiv 29 Dec 2021.

Builds on

25 of 60 references.

References · 25

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  2. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  3. 2018Privately Learning High-Dimensional Distributionscited by 103
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  6. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  7. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  8. 2019Private Hypothesis Selectioncited by 60
  9. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  10. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  11. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  12. 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
13 more
  1. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  2. 2015Differentially Private k-Means Clusteringcited by 27
  3. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  4. 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
  5. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  6. 2018Differentially Private k-Means with Constant Multiplicative Errorcited by 22
  7. 2016Locating a Small Cluster Privatelycited by 20
  8. 2017Clustering Algorithms for the Centralized and Local Modelscited by 18
  9. 2019Locally Private k-Means Clusteringcited by 15
  10. 2013A Two-round Variant of EM for Gaussian Mixturescited by 11
  11. 2016k-variates++: more pluses in the k-means++cited by 6
  12. 2018Graph-based Clustering under Differential Privacycited by 4
  13. 2020A note on differentially private clustering with large additive errorcited by 4

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 11; 2024: 3; 2025: 1.

17 papers.

Sort:

  1. 2022Orchestra: Unsupervised Federated Learning via Globally Consistent Clusteringcited by 45
  2. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  3. 2023Replicable Clusteringcited by 19
  4. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  5. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  6. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  7. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  8. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  9. 2024Private Geometric Mediancited by 3
  10. 2023Improving the Variance of Differentially Private Randomized Experiments through Clusteringcited by 2
  11. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  12. 2023DPM: Clustering Sensitive Data through Separationcited by 1
5 more
  1. 2023Differentially Private Clustering in Data Streamscited by 1
  2. 2025Private Geometric Median in Nearly-Linear Timecited by 1
  3. 2022Differentially-Private Bayes Consistencycited by 0
  4. 2023Improving the Utility of Differentially Private Clustering through Dynamical Processingcited by 0
  5. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0