mlsanityData to 14 Oct 2026

Differentially Private k-Means with Constant Multiplicative Error

arXiv 1804.08001 ↗First posted 21 Apr 2018cs.DScited by 22

Not on the map. Why?

Abstract (arXiv)

We design new differentially private algorithms for the Euclidean k-means problem, both in the centralized model and in the local model of differential privacy. In both models, our algorithms achieve significantly improved error guarantees than the previous state-of-the-art. In addition, in the local model, our algorithm significantly reduces the number of interaction rounds. Although the problem has been widely studied in the context of differential privacy, all of the existing constructions achieve only super constant approximation factors. We present, for the first time, efficient private algorithms for the problem with constant multiplicative error. Furthermore, we show how to modify our algorithms so they compute private corsets for k-means clustering in both models.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Apr 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 4; 2023: 7; 2024: 3; 2025: 1; 2026: 1.

22 papers.

Sort:

  1. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  2. 2021Locally Private k-Means in One Roundcited by 19
  3. 2022Improving Federated Learning Face Recognition via Privacy-Agnostic Clusterscited by 18
  4. 2021Differentially-Private Clustering of Easy Instancescited by 17
  5. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  6. 2022Differentially Private Vertical Federated Clusteringcited by 10
  7. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  8. 2022k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacycited by 4
  9. 2021Differentially-Private Sublinear-Time Clusteringcited by 2
  10. 2023Differential Privacy for Clustering Under Continual Observationcited by 2
  11. 2023Improving the Variance of Differentially Private Randomized Experiments through Clusteringcited by 2
  12. 2024FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacycited by 2
10 more
  1. 2025Differentially Private Wasserstein Barycenterscited by 2
  2. 2021Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Errorcited by 1
  3. 2021Differentially Private Algorithms for Clustering with Stability Assumptionscited by 1
  4. 2023DPM: Clustering Sensitive Data through Separationcited by 1
  5. 2023Differentially Private Clustering in Data Streamscited by 1
  6. 2023Privacy-preserving Continual Federated Clustering via Adaptive Resonance Theorycited by 1
  7. 2024Contrastive Explainable Clustering with Differential Privacycited by 1
  8. 2024Making Old Things New: A Unified Algorithm for Differentially Private Clusteringcited by 1
  9. 2023Personalized Privacy Amplification via Importance Samplingcited by 0
  10. 2026PE-means: Improved Differentially Private k-means Clustering through Private Evolutioncited by 0