# Locally Private k-Means Clustering

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2019.

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

- [Orchestra: Unsupervised Federated Learning via Globally Consistent Clustering](https://mlsanity.com/paper/2205.11506/) (2022)
- [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)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Federated Learning Clients Clustering with Adaptation to Data Drifts](https://mlsanity.com/paper/2411.01580/) (2024)
- [Differentially-Private Sublinear-Time Clustering](https://mlsanity.com/paper/2112.13751/) (2021)
- [A Generative Framework for Personalized Learning and Estimation: Theory, Algorithms, and Privacy](https://mlsanity.com/paper/2207.01771/) (2022)
- [FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy](https://mlsanity.com/paper/2405.02437/) (2024)
- [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)
- [Contrastive Explainable Clustering with Differential Privacy](https://mlsanity.com/paper/2406.04610/) (2024)
- [Analysis and mining of low-carbon and energy-saving tourism data characteristics based on machine learning algorithm](https://mlsanity.com/paper/2312.03037/) (2023)
- [Differentially Private Federated Clustering with Random Rebalancing](https://mlsanity.com/paper/2508.06183/) (2025)
- [Breaking Privacy in Federated Clustering: Perfect Input Reconstruction via Temporal Correlations](https://mlsanity.com/paper/2511.07073/) (2025)

## Abstract (arXiv)

We design a new algorithm for the Euclidean k-means problem that operates in the local model of differential privacy. Unlike in the non-private literature, differentially private algorithms for the k-means objective incur both additive and multiplicative errors. Our algorithm significantly reduces the additive error while keeping the multiplicative error the same as in previous state-of-the-art results. Specifically, on a database of size n, our algorithm guarantees O(1) multiplicative error and ≈ n1/2+a additive error for an arbitrarily small constant a>0. All previous algorithms in the local model had additive error ≈ n2/3+a. Our techniques extend to k-median clustering. We show that the additive error we obtain is almost optimal in terms of its dependency on the database size n. Specifically, we give a simple lower bound showing that every locally-private algorithm for the k-means objective must have additive error at least ≈√n.