# Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 31 May 2021.

## Builds on (most cited first, 13 of 13)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017)
- [Locally Private k-Means Clustering](https://mlsanity.com/paper/1907.02513/) (2019)
- [Differentially Private Clustering via Maximum Coverage](https://mlsanity.com/paper/2008.12388/) (2020)
- [Differentially private k-means clustering via exponential mechanism and max cover](https://mlsanity.com/paper/2009.01220/) (2020)
- [Clustering High Dimensional Dynamic Data Streams](https://mlsanity.com/paper/1706.03887/) (2017)

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

- [Making Old Things New: A Unified Algorithm for Differentially Private Clustering](https://mlsanity.com/paper/2406.11649/) (2024)

## Abstract (arXiv)

Given a data set of size n in d'-dimensional Euclidean space, the k-means problem asks for a set of k points (called centers) so that the sum of the ℓ22-distances between points of a given data set of size n and the set of k centers is minimized. Recent work on this problem in the locally private setting achieves constant multiplicative approximation with additive error tildeO (n1/2 + a · k · max √d, √k ) and proves a lower bound of Omega(√n) on the additive error for any solution with a constant number of rounds. In this work we bridge the gap between the exponents of n in the upper and lower bounds on the additive error with two new algorithms. Given any α>0, our first algorithm achieves a multiplicative approximation guarantee which is at most a (1+α) factor greater than that of any non-private k-means clustering algorithm with k^tildeO(1/α2) √d' n mboxpolylog n additive error. Given any c>√2, our second algorithm achieves O(k^1 + tildeO(1/(2c2-1)) √d' n mboxpoly log n) additive error with constant multiplicative approximation. Both algorithms go beyond the Omega(n1/2 + a) factor that occurs in the additive error for arbitrarily small parameters a in previous work, and the second algorithm in particular shows for the first time that it is possible to solve the locally private k-means problem in a constant number of rounds with constant factor multiplicative approximation and polynomial dependence on k in the additive error arbitrarily close to linear.