mlsanityData to 14 Oct 2026

Differentially Private Clustering: Tight Approximation Ratios

arXiv 2008.08007 ↗First posted 18 Aug 2020cs.LG cs.CR cs.DScited by 34

Not on the map. Why?

Abstract (arXiv)

We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors. Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.

Key facts. Cited by 34 papers in the map (data through 14 Oct 2026). First posted on arXiv 18 Aug 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 6; 2023: 8; 2024: 8; 2025: 5; 2026: 2.

34 papers.

Sort:

  1. 2023Differentially Private Synthetic Data via Foundation Model APIs 1: Imagescited by 65
  2. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  3. 2021Locally Private k-Means in One Roundcited by 19
  4. 2023Replicable Clusteringcited by 19
  5. 2021Differentially-Private Clustering of Easy Instancescited by 17
  6. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  7. 2022Differentially Private Vertical Federated Clusteringcited by 10
  8. 2024Data-adaptive Differentially Private Prompt Synthesis for In-Context Learningcited by 10
  9. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  10. 2022Near-Optimal Correlation Clustering with Privacycited by 6
  11. 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
  12. 2022k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacycited by 4
22 more
  1. 2025Urania: Differentially Private Insights into AI Usecited by 4
  2. 2021Differentially Private Nonparametric Regression Under a Growth Conditioncited by 3
  3. 2025Private Learning of Littlestone Classes, Revisitedcited by 3
  4. 2021Differentially-Private Sublinear-Time Clusteringcited by 2
  5. 2022A Generative Framework for Personalized Learning and Estimation: Theory, Algorithms, and Privacycited by 2
  6. 2023Differential Privacy for Clustering Under Continual Observationcited by 2
  7. 2024A Differentially Private Clustering Algorithm for Well-Clustered Graphscited by 2
  8. 2024FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacycited by 2
  9. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  10. 2024Differentially Private Multi-Sampling from Distributionscited by 2
  11. 2025Differentially Private Wasserstein Barycenterscited by 2
  12. 2022Differentially Private Partial Set Cover with Applications to Facility Locationcited by 1
  13. 2023DPM: Clustering Sensitive Data through Separationcited by 1
  14. 2023Differentially Private Clustering in Data Streamscited by 1
  15. 2024Towards the mathematical foundation of the minimum enclosing ball and related problemscited by 1
  16. 2024Contrastive Explainable Clustering with Differential Privacycited by 1
  17. 2024Making Old Things New: A Unified Algorithm for Differentially Private Clusteringcited by 1
  18. 2023Personalized Privacy Amplification via Importance Samplingcited by 0
  19. 2025Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clusteringcited by 0
  20. 2025Coresets for Clustering Under Stochastic Noisecited by 0
  21. 2026On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clusteringcited by 0
  22. 2026PE-means: Improved Differentially Private k-means Clustering through Private Evolutioncited by 0