# Differentially private k-means clustering via exponential mechanism and max cover

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2020.

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

- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Clustering and Median Aggregation Improve Differentially Private Inference](https://mlsanity.com/paper/2506.04566/) (2025)
- [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)
- [Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale](https://mlsanity.com/paper/2603.22363/) (2026)
- [Streaming Submodular Maximization with Differential Privacy](https://mlsanity.com/paper/2210.14315/) (2022)

## Abstract (arXiv)

We introduce a new (εp, δp)-differentially private algorithm for the k-means clustering problem. Given a dataset in Euclidean space, the k-means clustering problem requires one to find k points in that space such that the sum of squares of Euclidean distances between each data point and its closest respective point among the k returned is minimised. Although there exist privacy-preserving methods with good theoretical guarantees to solve this problem [Balcan et al., 2017; Kaplan and Stemmer, 2018], in practice it is seen that it is the additive error which dictates the practical performance of these methods. By reducing the problem to a sequence of instances of maximum coverage on a grid, we are able to derive a new method that achieves lower additive error then previous works. For input datasets with cardinality n and diameter Delta, our algorithm has an O(Delta2 (k log2 n log(1/δp)/εp + k√d log(1/δp)/εp)) additive error whilst maintaining constant multiplicative error. We conclude with some experiments and find an improvement over previously implemented work for this problem.