# Locally Private k-Means in One Round

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 72 references that are in the map.
- First posted on arXiv 20 Apr 2021.

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

- [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)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017)
- [Separating Local & Shuffled Differential Privacy via Histograms](https://mlsanity.com/paper/1911.06879/) (2019)
- [Locally Private k-Means Clustering](https://mlsanity.com/paper/1907.02513/) (2019)
- [Private Aggregation from Fewer Anonymous Messages](https://mlsanity.com/paper/1909.11073/) (2019)
- [Pure Differentially Private Summation from Anonymous Messages](https://mlsanity.com/paper/2002.01919/) (2020)
- [Connecting Robust Shuffle Privacy and Pan-Privacy](https://mlsanity.com/paper/2004.09481/) (2020)
- [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)
- [On Distributed Differential Privacy and Counting Distinct Elements](https://mlsanity.com/paper/2009.09604/) (2020)
- [k-variates++: more pluses in the k-means++](https://mlsanity.com/paper/1602.01198/) (2016)

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

- [Orchestra: Unsupervised Federated Learning via Globally Consistent Clustering](https://mlsanity.com/paper/2205.11506/) (2022)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Differentially Private Vertical Federated Clustering](https://mlsanity.com/paper/2208.01700/) (2022)
- [Towards Unbiased Training in Federated Open-world Semi-supervised Learning](https://mlsanity.com/paper/2305.00771/) (2023)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Graph Generative Model for Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2207.04396/) (2022)
- [Urania: Differentially Private Insights into AI Use](https://mlsanity.com/paper/2506.04681/) (2025)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Multi-Message Shuffled Privacy in Federated Learning](https://mlsanity.com/paper/2302.11152/) (2023)
- [Differential Privacy for Clustering Under Continual Observation](https://mlsanity.com/paper/2307.03430/) (2023)
- [FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy](https://mlsanity.com/paper/2405.02437/) (2024)
- [Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error](https://mlsanity.com/paper/2105.15007/) (2021)
- [DPM: Clustering Sensitive Data through Separation](https://mlsanity.com/paper/2307.02969/) (2023)
- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (2023)
- [Making Old Things New: A Unified Algorithm for Differentially Private Clustering](https://mlsanity.com/paper/2406.11649/) (2024)
- [Differentially Private In-Context Learning with Nearest Neighbor Search](https://mlsanity.com/paper/2511.04332/) (2025)
- [Improving the Utility of Differentially Private Clustering through Dynamical Processing](https://mlsanity.com/paper/2304.13886/) (2023)
- [Differentially Private Federated Clustering with Random Rebalancing](https://mlsanity.com/paper/2508.06183/) (2025)
- [On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clustering](https://mlsanity.com/paper/2603.26963/) (2026)

## Abstract (arXiv)

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.