Timezone: »

Locally Private k-Means in One Round
Alisa Chang · Badih Ghazi · Ravi Kumar · Pasin Manurangsi

Thu Jul 22 09:00 AM -- 11:00 AM (PDT) @ Virtual

We provide an approximation algorithm for k-means clustering in the \emph{one-round} (aka \emph{non-interactive}) local model of differential privacy (DP). Our algorithm achieves an approximation ratio arbitrarily close to the best \emph{non private} approximation algorithm, improving upon previously known algorithms that only guarantee large (constant) approximation ratios. Furthermore, ours is the first constant-factor approximation algorithm for k-means that requires only \emph{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.

Author Information

Alisa Chang (Google)
Badih Ghazi (Google)
Ravi Kumar (Google)
Pasin Manurangsi (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors