Locally Private k-Means in One Round

About

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.

Alisa Chang, Badih Ghazi, Ravi Kumar, Pasin Manurangsi · 2021

Related benchmarks

Task	Dataset	Result
Clustering	Blobs	Running Time (ms)7.72	5
Clustering	Crash	Running Time0.00257	5
Clustering	Cabs tiny	Running Time1.14	5
Clustering	circles	Running Time (ms)10.1	5
Clustering	moons	Running Time (ms)9.78	5
Clustering	Cluto t5	Running Time (ms)33.7	5
Clustering	Cluto t4	Running Time (ms)33.6	5
Clustering	Cluto t7	Running Time (ms)34.3	5
Clustering	HAR70+	Running Time334	4
Clustering	circles	ARI0	4