Locally Private k-Means in One Round
By Alisa Chang, Badih Ghazi, Ravi Kumar, Pasin Manurangsi. 2021
42 citations recorded by the source corpus.
We provide an approximation algorithm for k-means clustering in the one-round (aka non-interactive) local model of differential privacy (DP). This algorithm achieves an approximation ratio arbitrarily close to the best non private approximation algorithm, improving upon previously known algorithms that only guarantee large (constant) approximation ratios. Furthermore, this is the first constant-factor approximation algorithm for k-means that requires only one round of communication in the local DP model, positively resolving an open question of Stemmer (SODA 2020). Our algorithmic framework is quite flexible; we demonstrate this by showing that it also yields a similar near-optimal approximation algorithm in the (one-round) shuffle DP model.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Pasin Manurangsi
- Badih Ghazi
- Ravi Kumar
- Rasmus Pagh
- Amer Sinha
- Albert Cheu
- David P. Woodruff
- Alisa Chang
Citations in the corpus
- Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, background): “, 2021), as well as k-means clustering (Chang et al., 2021).”