# FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 83 references that are in the map.
- First posted on arXiv 3 May 2024.

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

- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning](https://mlsanity.com/paper/2002.04156/) (2020)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [FastSecAgg: Scalable Secure Aggregation for Privacy-Preserving Federated Learning](https://mlsanity.com/paper/2009.11248/) (2020)
- [Diffprivlib: The IBM Differential Privacy Library](https://mlsanity.com/paper/1907.02444/) (2019)
- [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)
- [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)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017)
- [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)
- [Differentially Private Vertical Federated Clustering](https://mlsanity.com/paper/2208.01700/) (2022)
- [Utility-efficient Differentially Private K-means Clustering based on Cluster Merging](https://mlsanity.com/paper/2010.01234/) (2020)
- [Selective MPC: Distributed Computation of Differentially Private Key-Value Statistics](https://mlsanity.com/paper/2107.12407/) (2021)
- [Privacy-Preserving and Outsourced Multi-User k-Means Clustering](https://mlsanity.com/paper/1412.4378/) (2014)
- [Inherit Differential Privacy in Distributed Setting: Multiparty Randomized Function Computation](https://mlsanity.com/paper/1604.03001/) (2016)

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

- [OmniFC: Rethinking Federated Clustering via Lossless and Secure Distance Reconstruction](https://mlsanity.com/paper/2505.13071/) (2025)
- [PE-means: Improved Differentially Private k-means Clustering through Private Evolution](https://mlsanity.com/paper/2606.00342/) (2026)

## Abstract (arXiv)

We study the problem of privacy-preserving k-means clustering in the horizontally federated setting. Existing federated approaches using secure computation suffer from substantial overheads and do not offer output privacy. At the same time, differentially private (DP) k-means algorithms either assume a trusted central curator or significantly degrade utility by adding noise in the local DP model. Naively combining the secure and central DP solutions results in a protocol with impractical overhead. Instead, our work provides enhancements to both the DP and secure computation components, resulting in a design that is faster, more private, and more accurate than previous work. By utilizing the computational DP model, we design a lightweight, secure aggregation-based approach that achieves five orders of magnitude speed-up over state-of-the-art related work. Furthermore, we not only maintain the utility of the state-of-the-art in the central model of DP, but we improve the utility further by designing a new DP clustering mechanism.