Locally Private k-Means Clustering

By Uri Stemmer. 2019

70 citations recorded by the source corpus.

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 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 $\approx n^{1/2+a}$ additive error for an arbitrarily small constant $a$, whereas all previous algorithms in the local model on had additive error $\approx n^{2/3+a}$. We give a simple lower bound showing that additive error of $\approx\sqrt{n}$ is necessary for $k$-means algorithms in the local model (at least for algorithms with a constant number of interaction rounds, which is the setting we consider in this paper).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

In Computational Theory and Mathematics

Citations in the corpus

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “…algorithmic problems such as heavy hitters (e.g., (Bassily et al., 2017)) as well as unsupervised machine learning tasks such as clustering (e.g., (Stemmer, 2020)); furthermore, computing histogram is intimately related to distribution estimation (e.g., (Kairouz et al., 2016; Acharya & Sun,…”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “The adoption of the local model by major industry players has motivated a line of research in the theory of local di ﬀ erential privacy (e.g., [9, 8, 16, 59, 40, 42, 41]).”
The Power of the Hybrid Model for Mean Estimation (2018, methodology): “Other DP K-means algorithms exist in both the TCM [4, 8, 43, 46, 48, 53] and LM [47, 52, 54, 57] which improve on our two non-hybrid K-means algorithms.”
Heavy Hitters and the Structure of Local Privacy (2017, methodology): “In addition to the intrinsic interest of this problem, LDP algorithms for heavyhitters provide important subroutines for solving many other problems, such as median estimation, convex optimization, and clustering [21, 29, 35, 37].”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, background): “…author(s). with extensions including (private) distributed mean estimation (see, e.g., Biswas et al., 2020; Girgis et al., 2021), stochastic gradient descent (Song et al., 2013; Bassily et al., 2014; Abadi et al., 2016; Agarwal et al., 2018), and clustering (Stemmer & Kaplan, 2018; Stemmer, 2020).”
Locally Private k-Means in One Round (2021, methodology): “This improves upon the protocol of Stemmer (2020), where the additive error grows with n 1 / 2+ a for an arbitrary small positive constant a .”
On the Power of Multiple Anonymous Messages (2019, unknown): “…much less error than what is possible in the local model could lead to more accurate and eﬃcient shuﬄe model protocols for fundamental primitives such as clustering [91] and distribution testing [1], for which current locally diﬀerentially private protocols use frequency estimation as a black box.”