# Differentially Private k-Means with Constant Multiplicative Error

arXiv: https://arxiv.org/abs/1804.08001 · HTML: https://mlsanity.com/paper/1804.08001/

## Key facts

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

## Built on by (most cited first, 22 of 22)

- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Improving Federated Learning Face Recognition via Privacy-Agnostic Clusters](https://mlsanity.com/paper/2201.12467/) (2022)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Differentially Private Vertical Federated Clustering](https://mlsanity.com/paper/2208.01700/) (2022)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [Differentially-Private Sublinear-Time Clustering](https://mlsanity.com/paper/2112.13751/) (2021)
- [Differential Privacy for Clustering Under Continual Observation](https://mlsanity.com/paper/2307.03430/) (2023)
- [Improving the Variance of Differentially Private Randomized Experiments through Clustering](https://mlsanity.com/paper/2308.00957/) (2023)
- [FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy](https://mlsanity.com/paper/2405.02437/) (2024)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error](https://mlsanity.com/paper/2105.15007/) (2021)
- [Differentially Private Algorithms for Clustering with Stability Assumptions](https://mlsanity.com/paper/2106.12959/) (2021)
- [DPM: Clustering Sensitive Data through Separation](https://mlsanity.com/paper/2307.02969/) (2023)
- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (2023)
- [Privacy-preserving Continual Federated Clustering via Adaptive Resonance Theory](https://mlsanity.com/paper/2309.03487/) (2023)
- [Contrastive Explainable Clustering with Differential Privacy](https://mlsanity.com/paper/2406.04610/) (2024)
- [Making Old Things New: A Unified Algorithm for Differentially Private Clustering](https://mlsanity.com/paper/2406.11649/) (2024)
- [Personalized Privacy Amplification via Importance Sampling](https://mlsanity.com/paper/2307.10187/) (2023)
- [PE-means: Improved Differentially Private k-means Clustering through Private Evolution](https://mlsanity.com/paper/2606.00342/) (2026)

## 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.